| Line 293... |
Line 293... |
}
|
}
|
}
|
}
|
if (cuc_debug >= 3) print_cuc_bb (f, "AFTER_PREV");
|
if (cuc_debug >= 3) print_cuc_bb (f, "AFTER_PREV");
|
}
|
}
|
|
|
|
/* We do a quick check if there are some anomalies with references */
|
|
void cuc_check (cuc_func *f)
|
|
{
|
|
int i, j, k;
|
|
for (i = 0; i < f->num_bb; i++) {
|
|
if (!f->bb[i].insn && f->bb[i].ninsn) {
|
|
printf ("Anomaly detected at BB%x (insn NULL)\n", i);
|
|
print_cuc_bb (f, "ANOMALY");
|
|
exit (1);
|
|
}
|
|
for (j = 0; j < f->bb[i].ninsn; j++)
|
|
for (k = 0; k < MAX_OPERANDS; k++)
|
|
if (f->bb[i].insn[j].opt[k] & OPT_REF) {
|
|
int t = f->bb[i].insn[j].op[k];
|
|
if (REF_BB(t) >= f->num_bb || REF_I (t) >= f->bb[REF_BB(t)].ninsn) {
|
|
printf ("Anomaly detected at %x.%x[%i]\n", i, j, k);
|
|
print_cuc_bb (f, "ANOMALY");
|
|
exit (1);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
/* Build basic blocks */
|
/* Build basic blocks */
|
void build_bb (cuc_func *f)
|
void build_bb (cuc_func *f)
|
{
|
{
|
int i, j, k;
|
int i, j, k;
|
for (i = 0; i < f->num_bb; i++) {
|
for (i = 0; i < f->num_bb; i++) {
|
| Line 340... |
Line 363... |
f->bb[i].insn[j].op[k] = REF (b1, f->bb[i].insn[j].op[k] - f->bb[b1].first + MAX_REGS - 1);
|
f->bb[i].insn[j].op[k] = REF (b1, f->bb[i].insn[j].op[k] - f->bb[b1].first + MAX_REGS - 1);
|
}
|
}
|
if (f->bb[i].insn[j].type & IT_MEMORY) f->bb[i].nmemory++;
|
if (f->bb[i].insn[j].type & IT_MEMORY) f->bb[i].nmemory++;
|
}
|
}
|
}
|
}
|
|
cuc_check (f);
|
/* We do a quick check if there are some anomalies */
|
|
for (i = 0; i < f->num_bb; i++)
|
|
for (j = 0; j < f->bb[i].ninsn; j++)
|
|
for (k = 0; k < MAX_OPERANDS; k++)
|
|
if (f->bb[i].insn[j].opt[k] & OPT_REF) {
|
|
int t = f->bb[i].insn[j].op[k];
|
|
if (REF_I (t) >= f->bb[REF_BB(t)].ninsn) {
|
|
printf ("Anomaly detected at %x.%x[%i]\n", i, j, k);
|
|
print_cuc_bb (f, "ANOMALY");
|
|
exit (1);
|
|
}
|
|
}
|
|
}
|
}
|
|
|
/* type == 0; keep predecessor condition
|
/* type == 0; keep predecessor condition
|
* type == 1; keep successor condition
|
* type == 1; keep successor condition
|
* type == 2; join loop unrolled blocks */
|
* type == 2; join loop unrolled blocks */
|
static void join_bb (cuc_func *f, int pred, int succ, int type)
|
static void join_bb (cuc_func *f, int pred, int succ, int type)
|
{
|
{
|
int i, j, k, add, ninsn, add_cond = 0;
|
int i, j, k, n1, n2, ninsn, add_cond = 0;
|
unsigned long cond_op, cond_opt;
|
unsigned long cond_op, cond_opt;
|
cuc_insn *insn;
|
cuc_insn *insn;
|
|
|
|
if (cuc_debug) cuc_check (f);
|
cucdebug (3, "%x <= %x+%x (%i)\n", pred, pred, succ, type);
|
cucdebug (3, "%x <= %x+%x (%i)\n", pred, pred, succ, type);
|
cucdebug (3, "%x %x\n", f->bb[pred].ninsn, f->bb[succ].ninsn);
|
cucdebug (3, "%x %x\n", f->bb[pred].ninsn, f->bb[succ].ninsn);
|
if (cuc_debug >= 3) fflush (stdout);
|
if (cuc_debug >= 3) fflush (stdout);
|
|
|
add = f->bb[pred].ninsn;
|
n1 = f->bb[pred].ninsn;
|
if (f->bb[pred].ninsn <= 0
|
n2 = f->bb[succ].ninsn;
|
|| !(f->bb[pred].insn[f->bb[pred].ninsn - 1].type & IT_BRANCH)) type = 1;
|
if (n1 <= 0
|
|
|| !(f->bb[pred].insn[n1 - 1].type & IT_BRANCH)) type = 1;
|
if (type == 0 && f->bb[succ].prev[0] == f->bb[succ].next[0]) add_cond = 1;
|
if (type == 0 && f->bb[succ].prev[0] == f->bb[succ].next[0]) add_cond = 1;
|
|
if (type == 2) add_cond = 1;
|
|
|
ninsn = f->bb[pred].ninsn + f->bb[succ].ninsn + (type == 0 ? 1 : type == 1 ? 0 : 2)
|
assert (f->bb[pred].next[0] == f->bb[succ].next[0] || type != 2); /* not supported */
|
+ (add_cond ? MAX_REGS : 0);
|
|
|
ninsn = n1 + n2 + (type == 1 ? 0 : 1) + (add_cond ? MAX_REGS : 0);
|
|
|
insn = (cuc_insn *) malloc (ninsn * sizeof (cuc_insn));
|
insn = (cuc_insn *) malloc (ninsn * sizeof (cuc_insn));
|
for (i = 0; i < add; i++) insn[i] = f->bb[pred].insn[i];
|
for (i = 0; i < n1; i++) insn[i] = f->bb[pred].insn[i];
|
/* when type == 0, we copy the last (jump) instruction to the end */
|
/* when type == 0, we move the last (jump) instruction to the end */
|
if (type == 0 || type == 2) {
|
if (type == 0 || type == 2) {
|
insn[ninsn - 1] = insn[add - 1];
|
/* Move first branch instruction to the end */
|
cond_op = insn[add - 1].op[1];
|
assert (insn[n1 - 1].type & IT_BRANCH);
|
cond_opt = insn[add - 1].opt[1];
|
insn[ninsn - 1] = insn[n1 - 1];
|
change_insn_type (&insn[add - 1], II_NOP);
|
cond_op = insn[n1 - 1].op[1];
|
|
cond_opt = insn[n1 - 1].opt[1];
|
|
|
|
/* Remove old branch */
|
|
change_insn_type (&insn[n1 - 1], II_NOP);
|
}
|
}
|
/* Copy second block */
|
/* Copy second block */
|
for (i = 0; i < f->bb[succ].ninsn; i++) insn[i + f->bb[pred].ninsn] = f->bb[succ].insn[i];
|
for (i = 0; i < n2; i++) insn[i + n1] = f->bb[succ].insn[i];
|
|
|
|
|
/* and when type == 2, we may need to add sfor instruction, to quit when either is true */
|
/* and when type == 2, we may need to add sfor instruction, to quit when either is true */
|
if (type == 2) {
|
if (type == 2) {
|
assert (0);
|
/* Move second branch instruction to the end */
|
|
if (insn[n1 + n2 - 1].type & IT_BRANCH) {
|
|
insn[ninsn - 1] = insn[n1 + n2 - 1];
|
|
|
|
/* Use conditional from cmov FLAG_REG, c_p, c_s, c_p */
|
|
insn[ninsn - 1].op[1] = REF (pred, n1 + n2 + FLAG_REG); insn[ninsn - 1].opt[1] = OPT_REF;
|
|
|
|
/* Remove old one */
|
|
change_insn_type (&insn[n1 + n2 - 1], II_NOP);
|
|
} else change_insn_type (&insn[ninsn - 1], II_NOP); /* do not use branch slot */
|
}
|
}
|
|
|
|
#if 1
|
/* LRBB at start of succ BB is not valid, it should be set when */
|
/* LRBB at start of succ BB is not valid, it should be set when */
|
if (insn[add].index == II_LRBB) {
|
if (insn[n1].index == II_LRBB) {
|
assert (0); /* not tested yet */
|
assert (0); /* not tested yet */
|
change_insn_type (&insn[add], II_NOP);
|
change_insn_type (&insn[n1], II_NOP);
|
for (i = add; i < ninsn; i++)
|
for (i = n1; i < ninsn; i++)
|
if (insn[i].index == II_CMOV && insn[i].op[3] == REF (succ, add)) {
|
if (insn[i].index == II_CMOV && insn[i].op[3] == REF (pred, n1)) {
|
assert (insn[i].opt[3] == OPT_REF);
|
assert (insn[i].opt[3] == OPT_REF);
|
insn[i].op[3] = cond_op;
|
insn[i].op[3] = cond_op;
|
insn[i].opt[3] = cond_opt;
|
insn[i].opt[3] = cond_opt;
|
if (f->bb[pred].next[0] != succ) {
|
if (f->bb[pred].next[0] != succ) {
|
unsigned long t; /* negate conditional -- exchange */
|
unsigned long t; /* negate conditional -- exchange */
|
| Line 415... |
Line 443... |
insn[i].opt[1] = insn[i].opt[2];
|
insn[i].opt[1] = insn[i].opt[2];
|
insn[i].opt[2] = t;
|
insn[i].opt[2] = t;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
#endif
|
|
|
for (i = 0; i < ninsn; i++) reloc[i] = -1;
|
for (i = 0; i < ninsn; i++) reloc[i] = -1;
|
|
|
/* Add conditional instructions if required */
|
/* Add conditional instructions if required */
|
if (add_cond) {
|
if (add_cond) {
|
recalc_last_used_reg (f, pred);
|
recalc_last_used_reg (f, pred);
|
recalc_last_used_reg (f, succ);
|
recalc_last_used_reg (f, succ);
|
|
|
/* r0 -- add nop for it */
|
/* r0 -- add nop for it */
|
change_insn_type (&insn[add + f->bb[succ].ninsn], II_NOP);
|
change_insn_type (&insn[n1 + n2], II_NOP);
|
for (i = 1; i < MAX_REGS; i++) {
|
for (i = 1; i < MAX_REGS; i++) {
|
cuc_insn *ii = &insn[add + f->bb[succ].ninsn + i];
|
cuc_insn *ii = &insn[n1 + n2 + i];
|
int a = f->bb[pred].last_used_reg[i];
|
int a = f->bb[pred].last_used_reg[i];
|
int b = f->bb[succ].last_used_reg[i];
|
int b = f->bb[succ].last_used_reg[i];
|
|
|
if (b < 0) change_insn_type (ii, II_NOP);
|
if (b < 0) change_insn_type (ii, II_NOP);
|
else if (a < 0) {
|
else if (a < 0) {
|
| Line 438... |
Line 467... |
ii->type = 0;
|
ii->type = 0;
|
ii->dep = NULL;
|
ii->dep = NULL;
|
ii->op[0] = i; ii->opt[0] = OPT_REGISTER | OPT_DEST;
|
ii->op[0] = i; ii->opt[0] = OPT_REGISTER | OPT_DEST;
|
ii->op[1] = b; ii->opt[1] = OPT_REF;
|
ii->op[1] = b; ii->opt[1] = OPT_REF;
|
ii->op[2] = 0; ii->opt[2] = OPT_CONST;
|
ii->op[2] = 0; ii->opt[2] = OPT_CONST;
|
ii->op[3] = OPT_NONE;
|
ii->opt[3] = OPT_NONE;
|
|
if (i == FLAG_REG) ii->type |= IT_COND;
|
} else if (b >= 0) {
|
} else if (b >= 0) {
|
change_insn_type (ii, II_CMOV);
|
change_insn_type (ii, II_CMOV);
|
ii->type = 0;
|
ii->type = 0;
|
ii->dep = NULL;
|
ii->dep = NULL;
|
ii->op[0] = i; ii->opt[0] = OPT_REGISTER | OPT_DEST;
|
ii->op[0] = i; ii->opt[0] = OPT_REGISTER | OPT_DEST;
|
ii->op[1] = a; ii->opt[1] = OPT_REF;
|
ii->op[1] = a; ii->opt[1] = OPT_REF;
|
ii->op[2] = b; ii->opt[2] = OPT_REF;
|
ii->op[2] = b; ii->opt[2] = OPT_REF;
|
ii->op[3] = cond_op; ii->opt[3] = cond_opt;
|
ii->op[3] = cond_op; ii->opt[3] = cond_opt;
|
reloc[REF_I(a)] = REF (pred, add + f->bb[succ].ninsn + i);
|
reloc[REF_I(a)] = REF (pred, n1 + n2 + i);
|
|
if (i == FLAG_REG) ii->type |= IT_COND;
|
}
|
}
|
sprintf (ii->disasm, "cmov (join BB)");
|
sprintf (ii->disasm, "cmov (join BB)");
|
}
|
}
|
}
|
}
|
|
|
|
if (cuc_debug) cuc_check (f);
|
f->bb[pred].type |= f->bb[succ].type;
|
f->bb[pred].type |= f->bb[succ].type;
|
i = 0;
|
i = 0;
|
assert (f->bb[pred].next[0] >= 0);
|
assert (f->bb[pred].next[0] >= 0);
|
switch (type) {
|
switch (type) {
|
case 0:
|
case 0:
|
| Line 466... |
Line 498... |
break;
|
break;
|
case 1:
|
case 1:
|
f->bb[pred].next[0] = f->bb[succ].next[0];
|
f->bb[pred].next[0] = f->bb[succ].next[0];
|
f->bb[pred].next[1] = f->bb[succ].next[1];
|
f->bb[pred].next[1] = f->bb[succ].next[1];
|
break;
|
break;
|
|
case 2:
|
|
f->bb[pred].next[0] = f->bb[succ].next[0];
|
|
f->bb[pred].next[1] = f->bb[succ].next[1];
|
|
break;
|
}
|
}
|
if (f->bb[pred].next[0] == f->bb[pred].next[1]) f->bb[pred].next[1] = -1;
|
if (f->bb[pred].next[0] == f->bb[pred].next[1]) f->bb[pred].next[1] = -1;
|
f->bb[succ].type = BB_DEAD;
|
f->bb[succ].type = BB_DEAD;
|
|
/* remove branch instruction, if there is only one successor */
|
|
if (f->bb[pred].next[1] < 0 && insn[ninsn - 1].type & IT_BRANCH
|
|
&& f->bb[pred].next[0] != pred) /* not when end BB, loop */
|
|
change_insn_type (&insn[ninsn - 1], II_NOP);
|
|
|
/* Set max count */
|
/* Set max count */
|
if (f->bb[pred].cnt < f->bb[succ].cnt) f->bb[pred].cnt = f->bb[succ].cnt;
|
if (f->bb[pred].cnt < f->bb[succ].cnt) f->bb[pred].cnt = f->bb[succ].cnt;
|
f->bb[pred].ninsn = ninsn;
|
f->bb[pred].ninsn = ninsn;
|
|
f->bb[succ].ninsn = 0;
|
free (f->bb[pred].insn); f->bb[pred].insn = NULL;
|
free (f->bb[pred].insn); f->bb[pred].insn = NULL;
|
free (f->bb[succ].insn); f->bb[succ].insn = NULL;
|
free (f->bb[succ].insn); f->bb[succ].insn = NULL;
|
f->bb[pred].insn = insn;
|
f->bb[pred].insn = insn;
|
for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD)) {
|
for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD)) {
|
if (f->bb[i].prev[0] == succ) f->bb[i].prev[0] = pred;
|
if (f->bb[i].prev[0] == succ) f->bb[i].prev[0] = pred;
|
| Line 486... |
Line 527... |
for (k = 0; k < MAX_OPERANDS; k++)
|
for (k = 0; k < MAX_OPERANDS; k++)
|
if (f->bb[i].insn[j].opt[k] & OPT_REF) {
|
if (f->bb[i].insn[j].opt[k] & OPT_REF) {
|
/* Check if we are referencing successor BB -> relocate to second part of
|
/* Check if we are referencing successor BB -> relocate to second part of
|
the new block */
|
the new block */
|
if (REF_BB (f->bb[i].insn[j].op[k]) == succ) {
|
if (REF_BB (f->bb[i].insn[j].op[k]) == succ) {
|
if (type == 0 && f->bb[i].insn[j].op[j] == REF (succ, ninsn - 1))
|
|
f->bb[i].insn[j].op[j] = REF (pred, f->bb[pred].ninsn);
|
|
else {
|
|
int t = f->bb[i].insn[j].op[k];
|
int t = f->bb[i].insn[j].op[k];
|
int ndest = REF (pred, REF_I (t) + add);
|
int ndest = REF (pred, REF_I (t) + n1);
|
|
//printf ("%x: %x %x\n", REF(i, j), t, ndest);
|
|
|
/* We've found a reference to succ. block, being removed, relocate */
|
/* We've found a reference to succ. block, being removed, relocate */
|
if (add_cond && i != succ && !(i == pred && j >= ninsn - MAX_REGS)) {
|
f->bb[i].insn[j].op[k] = ndest;
|
//printf ("%x!\n", t);
|
|
//printf ("%x!\n", f->INSN(ndest).op[0]);
|
|
/* interblock dependency should have physical register attached */
|
|
assert (f->INSN(ndest).opt[0] == OPT_DEST | OPT_REGISTER);
|
|
assert (f->INSN(ndest).op[0] >= 0);
|
|
f->bb[i].insn[j].op[k] = REF (pred, add + f->bb[succ].ninsn + f->INSN(ndest).op[0]);
|
|
} else f->bb[i].insn[j].op[k] = ndest;
|
|
}
|
|
} else if (REF_BB(f->bb[i].insn[j].op[k]) == pred) {
|
} else if (REF_BB(f->bb[i].insn[j].op[k]) == pred) {
|
if (i != pred && reloc[REF_I(f->bb[i].insn[j].op[k])] >= 0) {
|
if (i != pred && reloc[REF_I(f->bb[i].insn[j].op[k])] >= 0) {
|
f->bb[i].insn[j].op[k] = reloc[REF_I(f->bb[i].insn[j].op[k])];
|
f->bb[i].insn[j].op[k] = reloc[REF_I(f->bb[i].insn[j].op[k])];
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
|
if (cuc_debug) cuc_check (f);
|
if (cuc_debug >= 3) print_cuc_bb (f, "join");
|
if (cuc_debug >= 3) print_cuc_bb (f, "join");
|
}
|
}
|
|
|
/* Optimize basic blocks */
|
/* Optimize basic blocks */
|
void optimize_bb (cuc_func *f)
|
void optimize_bb (cuc_func *f)
|
| Line 579... |
Line 611... |
3. pred & succ share common successor
|
3. pred & succ share common successor
|
4. optional succ's second successor */
|
4. optional succ's second successor */
|
for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD))
|
for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD))
|
if (f->bb[i].prev[0] >= 0 && f->bb[i].prev[1] < 0) { /* one predecessor */
|
if (f->bb[i].prev[0] >= 0 && f->bb[i].prev[1] < 0) { /* one predecessor */
|
int p = f->bb[i].prev[0];
|
int p = f->bb[i].prev[0];
|
if (f->bb[p].next[0] == i && f->bb[p].next[1] == f->bb[p].next[1]) {
|
#if 0 /* not yet supported */
|
join_bb (f, f->bb[i].prev[0], i, 2);
|
if (f->bb[p].next[0] == i
|
|
&& (f->bb[i].next[1] == f->bb[p].next[1]
|
|
|| f->bb[i].next[1] == f->bb[p].next[0])) {
|
|
join_bb (f, p, i, 2);
|
|
goto remove_lrbb;
|
|
}
|
|
#endif
|
|
if (f->bb[p].next[1] == i
|
|
&& (f->bb[i].next[0] == f->bb[p].next[1]
|
|
|| f->bb[i].next[0] == f->bb[p].next[0])) {
|
|
join_bb (f, p, i, 2);
|
goto remove_lrbb;
|
goto remove_lrbb;
|
}
|
}
|
}
|
}
|
#endif
|
#endif
|
}
|
}
|
