Line 77... |
Line 77... |
const char *cuc_insn_name (cuc_insn *ii) {
|
const char *cuc_insn_name (cuc_insn *ii) {
|
if (ii->index < 0 || ii->index > II_LAST) return "???";
|
if (ii->index < 0 || ii->index > II_LAST) return "???";
|
else return known[ii->index].name;
|
else return known[ii->index].name;
|
}
|
}
|
|
|
No newline at end of file
|
No newline at end of file
|
|
/* CSE -- common subexpression elimination */
|
|
void cse (cuc_func *f)
|
|
{
|
|
int b, i, j, b1, i1, b2, i2, j2;
|
|
for (b1 = 0; b1 < f->num_bb; b1++)
|
|
for (i1 = 0; i1 < f->bb[b1].ninsn; i1++)
|
|
for (b2 = 0; b2 < f->num_bb; b2++)
|
|
for (i2 = 0; i2 < f->bb[b2].ninsn; i2++) {
|
|
cuc_insn *ii1 = &f->bb[b1].insn[i1];
|
|
cuc_insn *ii2 = &f->bb[b2].insn[i2];
|
|
|
|
/* Do we have an exact match? */
|
|
if (ii1->index == ii2->index) continue;
|
|
if (ii1->type & IT_VOLATILE) continue;
|
|
|
|
if (ii1->op[1] != ii2->op[1] || ii1->opt[1] != ii2->opt[1]) continue;
|
|
if (ii1->op[2] != ii2->op[2] || ii1->opt[2] != ii2->opt[2]) continue;
|
|
if (ii1->opt[3] != ii2->opt[3]) continue;
|
|
if (ii1->opt[3] != OPT_NONE && ii1->op[3] != ii2->op[3]) continue;
|
|
|
|
/* Check if we drive outputs? */
|
|
if ((ii1->opt[0] & OPT_REGISTER) && ii1->op[0] >= 0)
|
|
if ((ii2->opt[0] & OPT_REGISTER) && ii2->op[0] >= 0) continue;
|
|
else ii2->op[0] = ii1->op[0];
|
|
|
|
/* remove duplicated instruction and relink the references */
|
|
change_insn_type (ii2, II_NOP);
|
|
for (b = 0; b < f->num_bb; b++)
|
|
for (i = 0; i < f->bb[b].ninsn; i++)
|
|
for (j = 0; j < MAX_OPERANDS; j++)
|
|
if (f->bb[b].insn[i].opt[j] & OPT_REF && f->bb[b].insn[i].op[j] == REF (b2, i2))
|
|
f->bb[b].insn[i].op[j] = REF (b1, i1);
|
|
}
|
|
}
|
|
|
|
static int count_cmovs (cuc_insn *ii, int match)
|
|
{
|
|
int c = 0, j;
|
|
if (match & 2) {
|
|
for (j = 0; j < MAX_OPERANDS; j++)
|
|
if (ii->opt[j] & OPT_DEST) c++;
|
|
}
|
|
if (match & 1) {
|
|
for (j = 0; j < MAX_OPERANDS; j++)
|
|
if (!(ii->opt[j] & OPT_DEST) && ii->opt[j] & OPT_REF) c++;
|
|
} else {
|
|
for (j = 0; j < MAX_OPERANDS; j++)
|
|
if (!(ii->opt[j] & OPT_DEST) && ii->opt[j] != OPT_NONE) c++;
|
|
}
|
|
return c;
|
|
}
|
|
|
|
static void search_csm (int iter, cuc_func *f, cuc_shared *list);
|
|
static cuc_shared *main_list;
|
|
static int *iteration;
|
|
|
|
/* CSM -- common subexpression matching -- resource sharing */
|
|
void csm (cuc_func *f)
|
|
{
|
|
int b, i, j;
|
|
int cnt;
|
|
cuc_shared *list;
|
|
cuc_timings timings;
|
|
|
|
analyse_timings (f, &timings);
|
|
main_list = NULL;
|
|
for (b = 0; b < f->num_bb; b++) {
|
|
assert (iteration = (int *)malloc (sizeof (int) * f->bb[b].ninsn));
|
|
for (i = 0; i < f->bb[b].ninsn; i++) {
|
|
int cnt = 0, cntc = 0;
|
|
double size = 0., sizec = 0.;
|
|
int j2 = 0;
|
|
for (j = 0; j < f->bb[b].ninsn; j++)
|
|
if (f->bb[b].insn[i].index == f->bb[b].insn[j].index) {
|
|
int ok = 1;
|
|
for (j2 = 0; j2 < MAX_OPERANDS; j2++) if (!(f->bb[b].insn[j].opt[j2] & OPT_REF))
|
|
if (f->bb[b].insn[j].opt[j2] != f->bb[b].insn[i].opt[j2]
|
|
|| f->bb[b].insn[j].op[j2] != f->bb[b].insn[i].opt[j2]) {
|
|
ok = 0;
|
|
break;
|
|
}
|
|
if (ok) {
|
|
cntc++;
|
|
sizec = sizec + insn_size (&f->bb[b].insn[j]);
|
|
} else {
|
|
cnt++;
|
|
size = size + insn_size (&f->bb[b].insn[j]);
|
|
}
|
|
iteration[j] = 0;
|
|
} else iteration[j] = -1;
|
|
if (cntc > 1) {
|
|
assert (list = (cuc_shared *)malloc (sizeof (cuc_shared)));
|
|
list->next = main_list;
|
|
list->from = NULL;
|
|
list->ref = REF (b, i);
|
|
list->cnt = cnt;
|
|
list->cmatch = 1;
|
|
list->cmovs = count_cmovs (&f->bb[b].insn[i], 3);
|
|
list->osize = sizec;
|
|
list->size = ii_size (f->bb[b].insn[i].index, 1);
|
|
main_list = list;
|
|
search_csm (0, f, list);
|
|
}
|
|
if (cnt > 1) {
|
|
assert (list = (cuc_shared *)malloc (sizeof (cuc_shared)));
|
|
list->next = main_list;
|
|
list->from = NULL;
|
|
list->ref = REF (b, i);
|
|
list->cnt = cnt + cntc;
|
|
list->cmatch = 0;
|
|
list->cmovs = count_cmovs (&f->bb[b].insn[i], 2);
|
|
list->osize = size + sizec;
|
|
list->size = ii_size (f->bb[b].insn[i].index, 0);
|
|
main_list = list;
|
|
search_csm (0, f, list);
|
|
}
|
|
}
|
|
free (iteration);
|
|
}
|
|
|
|
for (list = main_list; list; list = list->next) list->dead = 0;
|
|
cnt = 0;
|
|
for (list = main_list; list; list = list->next) if (!list->dead) cnt++;
|
|
cucdebug (1, "noptions = %i\n", cnt);
|
|
|
|
/* Now we will check the real size of the 'improvements'; if the size
|
|
actually increases, we abandom the option */
|
|
for (list = main_list; list; list = list->next)
|
|
if (list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size >= list->osize) list->dead = 1;
|
|
|
|
cnt = 0;
|
|
for (list = main_list; list; list = list->next) if (!list->dead) cnt++;
|
|
cucdebug (1, "noptions = %i\n", cnt);
|
|
|
|
/* Count number of instructions grouped */
|
|
for (list = main_list; list; list = list->next) {
|
|
cuc_shared *l = list;
|
|
int c = 0;
|
|
while (l) {
|
|
c++;
|
|
if (f->INSN(l->ref).type & (IT_VOLATILE | IT_MEMORY | IT_MEMADD)) list->dead = 1;
|
|
l = l->from;
|
|
}
|
|
list->ninsn = c;
|
|
}
|
|
|
|
cnt = 0;
|
|
for (list = main_list; list; list = list->next)
|
|
if (!list->dead) cnt++;
|
|
cucdebug (1, "noptions = %i\n", cnt);
|
|
|
|
#if 1
|
|
/* We can get a lot of options here, so we will delete duplicates */
|
|
for (list = main_list; list; list = list->next) if (!list->dead) {
|
|
cuc_shared *l;
|
|
for (l = list->next; l; l = l->next) if (!l->dead) {
|
|
int ok = 1;
|
|
cuc_shared *t1 = list;
|
|
cuc_shared *t2 = l;
|
|
while (ok && t1 && t2) {
|
|
if (f->INSN(t1->ref).index == f->INSN(t2->ref).index) {
|
|
/* If other operands are matching, we must check for them also */
|
|
if (t1->cmatch) {
|
|
int j;
|
|
for (j = 0; j < MAX_OPERANDS; j++)
|
|
if (!(f->INSN(t1->ref).opt[j] & OPT_REF) || !(f->INSN(t2->ref).opt[j] & OPT_REF)
|
|
|| f->INSN(t1->ref).opt[j] != f->INSN(t2->ref).opt[j]
|
|
|| f->INSN(t1->ref).op[j] != f->INSN(t2->ref).op[j]) {
|
|
ok = 0;
|
|
break;
|
|
}
|
|
}
|
|
|
|
/* This option is duplicate, remove */
|
|
if (ok) t1->dead = 1;
|
|
}
|
|
t1 = t1->from;
|
|
t2 = t2->from;
|
|
}
|
|
}
|
|
}
|
|
cnt = 0;
|
|
for (list = main_list; list; list = list->next) if (!list->dead) cnt++;
|
|
cucdebug (1, "noptions = %i\n", cnt);
|
|
#endif
|
|
/* Print out */
|
|
for (list = main_list; list; list = list->next) if (!list->dead) {
|
|
cuc_shared *l = list;
|
|
cucdebug (1, "%-4s cnt %3i ninsn %3i size %8.1f osize %8.1f cmovs %3i @",
|
|
cuc_insn_name (&f->INSN(list->ref)), list->cnt, list->ninsn,
|
|
list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size, list->osize, list->cmovs);
|
|
while (l) {
|
|
cucdebug (1, "%c%x,", l->cmatch ? '.' : '!', l->ref);
|
|
l = l->from;
|
|
}
|
|
cucdebug (1, "\n");
|
|
}
|
|
|
|
/* Calculate estimated timings */
|
|
for (b = 0; b < f->num_bb; b++) {
|
|
cnt = 0;
|
|
for (list = main_list; list; list = list->next)
|
|
if (!list->dead && REF_BB(list->ref) == b) cnt++;
|
|
|
|
f->bb[b].ntim = cnt;
|
|
if (!cnt) {
|
|
f->bb[b].tim = NULL;
|
|
continue;
|
|
}
|
|
assert (f->bb[b].tim = (cuc_timings *)malloc (sizeof (cuc_timings) * cnt));
|
|
|
|
cnt = 0;
|
|
for (list = main_list; list; list = list->next) if (!list->dead && REF_BB(list->ref) == b) {
|
|
cuc_shared *l = list;
|
|
f->bb[b].tim[cnt].b = b;
|
|
f->bb[b].tim[cnt].preroll = f->bb[b].tim[cnt].unroll = 1;
|
|
f->bb[b].tim[cnt].nshared = list->ninsn;
|
|
assert (f->bb[b].tim[cnt].shared = (int *) malloc (sizeof(int) * list->ninsn));
|
|
for (i = 0; i < list->ninsn; i++, l = l->from) f->bb[b].tim[cnt].shared[i] = l->ref;
|
|
f->bb[b].tim[cnt].new_time = timings.new_time + f->bb[b].cnt * (list->cnt - 1);
|
|
f->bb[b].tim[cnt].size = timings.size + list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size - list->osize;
|
|
cnt++;
|
|
}
|
|
}
|
|
}
|
|
|
|
/* Recursive function for searching through instruction graph */
|
|
static void search_csm (int iter, cuc_func *f, cuc_shared *list)
|
|
{
|
|
int b, i, j, i1;
|
|
cuc_shared *l;
|
|
b = REF_BB(list->ref);
|
|
i = REF_I(list->ref);
|
|
|
|
for (j = 0; j < MAX_OPERANDS; j++) if (f->bb[b].insn[i].opt[j] & OPT_REF) {
|
|
int t = f->bb[b].insn[i].op[j];
|
|
int cnt = 0, cntc = 0;
|
|
double size = 0., sizec = 0.;
|
|
|
|
/* Mark neighbours */
|
|
for (i1 = 0; i1 < f->bb[b].ninsn; i1++) {
|
|
if (iteration[i1] == iter && f->bb[b].insn[i1].opt[j] & OPT_REF) {
|
|
int t2 = f->bb[b].insn[i1].op[j];
|
|
if (f->INSN(t).index == f->INSN(t2).index && f->INSN(t2).opt[j] & OPT_REF) {
|
|
int j2;
|
|
int ok = 1;
|
|
iteration[REF_I(t2)] = iter + 1;
|
|
for (j2 = 0; j2 < MAX_OPERANDS; j2++) if (!(f->bb[b].insn[i1].opt[j2] & OPT_REF))
|
|
if (f->bb[b].insn[i1].opt[j2] != f->bb[b].insn[i].opt[j2]
|
|
|| f->bb[b].insn[i1].op[j2] != f->bb[b].insn[i].opt[j2]) {
|
|
ok = 0;
|
|
break;
|
|
}
|
|
if (ok) {
|
|
cntc++;
|
|
sizec = sizec + insn_size (&f->bb[b].insn[i1]);
|
|
} else {
|
|
cnt++;
|
|
size = size + insn_size (&f->bb[b].insn[i1]);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
if (cntc > 1) {
|
|
assert (l = (cuc_shared *)malloc (sizeof (cuc_shared)));
|
|
l->next = main_list;
|
|
main_list = l;
|
|
l->from = list;
|
|
l->ref = t;
|
|
l->cnt = cnt;
|
|
l->cmatch = 1;
|
|
l->cmovs = list->cmovs + count_cmovs (&f->bb[b].insn[i], 1) - 1;
|
|
l->size = list->size + ii_size (f->bb[b].insn[i].index, 1);
|
|
l->osize = sizec;
|
|
search_csm (iter + 1, f, l);
|
|
}
|
|
if (cnt > 1) {
|
|
assert (l = (cuc_shared *)malloc (sizeof (cuc_shared)));
|
|
l->next = main_list;
|
|
main_list = l;
|
|
l->from = list;
|
|
l->ref = t;
|
|
l->cnt = cnt + cntc;
|
|
l->cmatch = 0;
|
|
l->osize = size + sizec;
|
|
l->cmovs = list->cmovs + count_cmovs (&f->bb[b].insn[i], 0) - 1;
|
|
l->size = list->size + ii_size (f->bb[b].insn[i].index, 0);
|
|
search_csm (iter + 1, f, l);
|
|
}
|
|
|
|
/* Unmark them back */
|
|
for (i1 = 0; i1 < f->bb[b].ninsn; i1++) if (iteration[i1] > iter) iteration[i1] = -1;
|
|
}
|
|
}
|
|
|
|
|
No newline at end of file
|
No newline at end of file
|