Line 30... |
Line 30... |
/* prints out bb string */
|
/* prints out bb string */
|
void print_bb_num (int num)
|
void print_bb_num (int num)
|
{
|
{
|
if (num < 0) printf ("*");
|
if (num < 0) printf ("*");
|
else if (num == BBID_END) printf ("END");
|
else if (num == BBID_END) printf ("END");
|
|
else if (num == BBID_START) printf ("START");
|
else printf ("%2x", num);
|
else printf ("%2x", num);
|
}
|
}
|
|
|
/* Print out basic blocks */
|
/* Print out basic blocks */
|
void print_cuc_bb (cuc_func *f, char *s)
|
void print_cuc_bb (cuc_func *f, char *s)
|
Line 305... |
Line 306... |
assert (f->bb[t].prev[1] < 0);
|
assert (f->bb[t].prev[1] < 0);
|
f->bb[t].prev[1] = i;
|
f->bb[t].prev[1] = i;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
/* Add START marker */
|
|
assert (f->bb[0].prev[0] < 0);
|
|
f->bb[0].prev[0]= BBID_START;
|
|
|
/* Add END marker */
|
/* Add END marker */
|
for (i = 0; i < f->num_bb; i++)
|
for (i = 0; i < f->num_bb; i++)
|
if (f->bb[i].type & BB_END) {
|
if (f->bb[i].type & BB_END) {
|
assert (f->bb[i].next[0] < 0);
|
assert (f->bb[i].next[0] < 0);
|
f->bb[i].next[0] = BBID_END;
|
f->bb[i].next[0] = BBID_END;
|
Line 643... |
Line 648... |
cucdebug (4, "-lrbb %x.%x\n", i, j);
|
cucdebug (4, "-lrbb %x.%x\n", i, j);
|
|
|
/* Change to add LRBB, 0, 0 */
|
/* Change to add LRBB, 0, 0 */
|
change_insn_type (&f->bb[i].insn[j], II_ADD);
|
change_insn_type (&f->bb[i].insn[j], II_ADD);
|
f->bb[i].insn[j].type &= ~IT_VOLATILE;
|
f->bb[i].insn[j].type &= ~IT_VOLATILE;
|
t = &f->bb[f->bb[i].prev[0]].insn[f->bb[f->bb[i].prev[0]].ninsn - 1];
|
|
f->bb[i].insn[j].opt[1] = f->bb[i].insn[j].opt[2] = OPT_CONST;
|
f->bb[i].insn[j].opt[1] = f->bb[i].insn[j].opt[2] = OPT_CONST;
|
f->bb[i].insn[j].op[1] = f->bb[i].insn[j].op[2] = 0; /* always use left block */
|
f->bb[i].insn[j].op[1] = f->bb[i].insn[j].op[2] = 0; /* always use left block */
|
f->bb[i].insn[j].opt[3] = OPT_NONE;
|
f->bb[i].insn[j].opt[3] = OPT_NONE;
|
modified = 1;
|
modified = 1;
|
|
if (f->bb[i].prev[0] != BBID_START) {
|
|
t = &f->bb[f->bb[i].prev[0]].insn[f->bb[f->bb[i].prev[0]].ninsn - 1];
|
|
|
/* If the predecessor still has a conditional jump instruction, we must be careful.
|
/* If the predecessor still has a conditional jump instruction, we must be careful.
|
If next[0] == next[1] join them. Now we will link lrbb and correct the situation */
|
If next[0] == next[1] join them. Now we will link lrbb and correct the situation */
|
if (t->type & IT_BRANCH) { /* We must set a reference to branch result */
|
if (t->type & IT_BRANCH) { /* We must set a reference to branch result */
|
f->bb[i].insn[j].opt[1] = t->opt[1];
|
f->bb[i].insn[j].opt[1] = t->opt[1];
|
Line 660... |
Line 666... |
if (f->bb[f->bb[i].prev[0]].next[1] < 0) change_insn_type (t, II_NOP);
|
if (f->bb[f->bb[i].prev[0]].next[1] < 0) change_insn_type (t, II_NOP);
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
}
|
|
}
|
|
|
/* Ordering of joining types is cruical -- we should concat all directly connected BBs
|
/* Ordering of joining types is cruical -- we should concat all directly connected BBs
|
together first, so when we do a type != 1 joining, we can remove LRBB, directly by
|
together first, so when we do a type != 1 joining, we can remove LRBB, directly by
|
looking at number of its predeccessors */
|
looking at number of its predeccessors */
|
|
|
/* Type 1 joining
|
/* Type 1 joining
|
1. link between pred & succ
|
1. link between pred & succ
|
2. no other pred's successors
|
2. no other pred's successors
|
3. no other succ's predecessors, except if pred has max one */
|
3. no other succ's predecessors, except if pred has max one */
|
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)) {
|
|
int p = f->bb[i].prev[0];
|
|
if (p < 0 || p == BBID_START) continue;
|
/* one successor and max sum of 3 predecessors */
|
/* one successor and max sum of 3 predecessors */
|
if (f->bb[f->bb[i].prev[0]].next[0] >= 0 && f->bb[f->bb[i].prev[0]].next[1] < 0
|
if (f->bb[p].next[0] >= 0 && f->bb[p].next[1] < 0
|
&& (f->bb[f->bb[i].prev[0]].prev[1] < 0 || f->bb[i].prev[1] < 0)) {
|
&& (f->bb[p].prev[1] < 0 || f->bb[i].prev[1] < 0)) {
|
/* First we will move all predecessors from succ to pred, and then we will do
|
/* First we will move all predecessors from succ to pred, and then we will do
|
real type 1 joining */
|
real type 1 joining */
|
if (f->bb[i].prev[1] >= 0) {
|
if (f->bb[i].prev[1] >= 0 && f->bb[i].prev[1] != BBID_START) {
|
|
int p1 = f->bb[i].prev[1];
|
/* joining is surely not worth another extra memory access */
|
/* joining is surely not worth another extra memory access */
|
if (f->bb[f->bb[i].prev[0]].nmemory) continue;
|
if (f->bb[p].nmemory) continue;
|
if (f->bb[f->bb[i].prev[0]].prev[0] >= 0) {
|
if (f->bb[p].prev[0] >= 0) {
|
assert (f->bb[f->bb[i].prev[0]].prev[1] < 0);
|
assert (f->bb[p].prev[1] < 0);
|
f->bb[f->bb[i].prev[0]].prev[1] = f->bb[i].prev[1];
|
f->bb[p].prev[1] = p1;
|
} else f->bb[f->bb[i].prev[0]].prev[0] = f->bb[i].prev[1];
|
} else f->bb[p].prev[0] = p1;
|
if (f->bb[f->bb[i].prev[1]].next[0] == i)
|
if (f->bb[p1].next[0] == i) f->bb[p1].next[0] = p;
|
f->bb[f->bb[i].prev[1]].next[0] = f->bb[i].prev[0];
|
else if (f->bb[p1].next[1] == i) f->bb[p1].next[1] = p;
|
else if (f->bb[f->bb[i].prev[1]].next[1] == i)
|
|
f->bb[f->bb[i].prev[1]].next[1] = f->bb[i].prev[0];
|
|
else assert (0);
|
else assert (0);
|
f->bb[i].prev[1] = -1;
|
f->bb[i].prev[1] = -1;
|
}
|
}
|
assert (f->bb[i].prev[0] >= 0 && f->bb[i].prev[1] < 0); /* one predecessor */
|
assert (p >= 0 && f->bb[i].prev[1] < 0); /* one predecessor */
|
join_bb (f, f->bb[i].prev[0], i, 1);
|
join_bb (f, p, i, 1);
|
modified = 1;
|
modified = 1;
|
goto remove_lrbb;
|
goto remove_lrbb;
|
}
|
}
|
|
}
|
|
|
/* Type 0 joining
|
/* Type 0 joining
|
1. link between pred & succ
|
1. link between pred & succ
|
2. no memory accesses in succ
|
2. no memory accesses in succ
|
3. optional pred's second successors
|
3. optional pred's second successors
|
4. max. one succ's successors */
|
4. max. one succ's successors */
|
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[0] != BBID_START
|
|
&& f->bb[i].prev[1] < 0 /* one predecessor */
|
&& f->bb[i].next[1] < 0 /* max. one successor */
|
&& f->bb[i].next[1] < 0 /* max. one successor */
|
&& f->bb[i].nmemory == 0) { /* and no memory acceses */
|
&& f->bb[i].nmemory == 0) { /* and no memory acceses */
|
join_bb (f, f->bb[i].prev[0], i, 0);
|
join_bb (f, f->bb[i].prev[0], i, 0);
|
modified = 1;
|
modified = 1;
|
goto remove_lrbb;
|
goto remove_lrbb;
|
Line 717... |
Line 727... |
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 (p == BBID_START) continue;
|
#if 0 /* not yet supported */
|
#if 0 /* not yet supported */
|
if (f->bb[p].next[0] == i
|
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[1]
|
|| f->bb[i].next[1] == f->bb[p].next[0])) {
|
|| f->bb[i].next[1] == f->bb[p].next[0])) {
|
join_bb (f, p, i, 2);
|
join_bb (f, p, i, 2);
|
Line 760... |
Line 771... |
|
|
/* repair references */
|
/* repair references */
|
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)) {
|
printf ("%x %x %x %x %x\n", i, f->bb[i].prev[0], f->bb[i].prev[1], f->bb[i].next[0], f->bb[i].next[1]);
|
printf ("%x %x %x %x %x\n", i, f->bb[i].prev[0], f->bb[i].prev[1], f->bb[i].next[0], f->bb[i].next[1]);
|
fflush (stdout);
|
fflush (stdout);
|
if (f->bb[i].prev[0] >= 0) assert ((f->bb[i].prev[0] = reloc[f->bb[i].prev[0]]) >= 0);
|
if (f->bb[i].prev[0] >= 0 && f->bb[i].prev[0] != BBID_START)
|
if (f->bb[i].prev[1] >= 0) assert ((f->bb[i].prev[1] = reloc[f->bb[i].prev[1]]) >= 0);
|
assert ((f->bb[i].prev[0] = reloc[f->bb[i].prev[0]]) >= 0);
|
|
if (f->bb[i].prev[1] >= 0 && f->bb[i].prev[1] != BBID_START)
|
|
assert ((f->bb[i].prev[1] = reloc[f->bb[i].prev[1]]) >= 0);
|
if (f->bb[i].next[0] >= 0 && f->bb[i].next[0] != BBID_END)
|
if (f->bb[i].next[0] >= 0 && f->bb[i].next[0] != BBID_END)
|
assert ((f->bb[i].next[0] = reloc[f->bb[i].next[0]]) >= 0);
|
assert ((f->bb[i].next[0] = reloc[f->bb[i].next[0]]) >= 0);
|
if (f->bb[i].next[1] >= 0 && f->bb[i].next[1] != BBID_END)
|
if (f->bb[i].next[1] >= 0 && f->bb[i].next[1] != BBID_END)
|
assert ((f->bb[i].next[1] = reloc[f->bb[i].next[1]]) >= 0);
|
assert ((f->bb[i].next[1] = reloc[f->bb[i].next[1]]) >= 0);
|
if (f->bb[i].prev[0] == f->bb[i].prev[1]) f->bb[i].prev[1] = -1;
|
if (f->bb[i].prev[0] == f->bb[i].prev[1]) f->bb[i].prev[1] = -1;
|
Line 837... |
Line 850... |
int min = 3, minb;
|
int min = 3, minb;
|
|
|
/* search though all non-visited for minimum number of unvisited predecessors */
|
/* search though all non-visited for minimum number of unvisited predecessors */
|
for (b = 0; b < f->num_bb; b++) if (!f->bb[b].tmp) {
|
for (b = 0; b < f->num_bb; b++) if (!f->bb[b].tmp) {
|
int tmp = 0;
|
int tmp = 0;
|
if (f->bb[b].prev[0] >= 0 && !f->bb[f->bb[b].prev[0]].tmp) tmp++;
|
if (f->bb[b].prev[0] >= 0 && f->bb[b].prev[0] != BBID_START
|
if (f->bb[b].prev[1] >= 0 && !f->bb[f->bb[b].prev[1]].tmp) tmp++;
|
&& !f->bb[f->bb[b].prev[0]].tmp) tmp++;
|
|
if (f->bb[b].prev[1] >= 0 && f->bb[b].prev[1] != BBID_START
|
|
&& !f->bb[f->bb[b].prev[1]].tmp) tmp++;
|
if (tmp < min) {
|
if (tmp < min) {
|
minb = b;
|
minb = b;
|
min = tmp;
|
min = tmp;
|
if (tmp == 0) break; /* We already have the best one */
|
if (tmp == 0) break; /* We already have the best one */
|
}
|
}
|
Line 860... |
Line 875... |
for (i = 1; i < MAX_REGS - 1; i++) {
|
for (i = 1; i < MAX_REGS - 1; i++) {
|
int pa, pb;
|
int pa, pb;
|
assert (f->bb[b].insn[i].index == II_CMOV);
|
assert (f->bb[b].insn[i].index == II_CMOV);
|
assert (f->bb[b].insn[i].opt[0] == OPT_REGISTER | OPT_DEST);
|
assert (f->bb[b].insn[i].opt[0] == OPT_REGISTER | OPT_DEST);
|
assert (f->bb[b].insn[i].op[0] == i);
|
assert (f->bb[b].insn[i].op[0] == i);
|
if (f->bb[b].prev[0] < 0) pa = -1;
|
if (f->bb[b].prev[0] < 0 || f->bb[b].prev[0] == BBID_START) pa = -1;
|
else pa = f->bb[f->bb[b].prev[0]].last_used_reg[i];
|
else pa = f->bb[f->bb[b].prev[0]].last_used_reg[i];
|
if (f->bb[b].prev[1] < 0) pb = -1;
|
if (f->bb[b].prev[1] < 0 || f->bb[b].prev[1] == BBID_START) pb = -1;
|
else pb = f->bb[f->bb[b].prev[1]].last_used_reg[i];
|
else pb = f->bb[f->bb[b].prev[1]].last_used_reg[i];
|
|
|
/* We do some very simple optimizations right away to make things more readable */
|
/* We do some very simple optimizations right away to make things more readable */
|
if (pa < 0 && pb < 0) {
|
if (pa < 0 && pb < 0) {
|
/* Was not used at all */
|
/* Was not used at all */
|