aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--mips.c2
-rw-r--r--semantics.c1
-rw-r--r--semantics.h1
-rw-r--r--ssa.c103
-rw-r--r--ssa.h4
5 files changed, 87 insertions, 24 deletions
diff --git a/mips.c b/mips.c
index 9b08344..ba81456 100644
--- a/mips.c
+++ b/mips.c
@@ -482,7 +482,7 @@ void mips_generate(void) {
{
COpr_t opr = p->opr;
if (opr->reg != -1 &&
- (opr->kind == TMP || opr->info.var->loc <= 0) &&
+ (opr->kind == TMP || !(opr->info.var->loc > 0)) &&
overlap_with_beg(opr, i->id))
used_reg[opr->reg] = 1;
}
diff --git a/semantics.c b/semantics.c
index b1afee2..a431e25 100644
--- a/semantics.c
+++ b/semantics.c
@@ -273,6 +273,7 @@ CVar_t cvar_create(char *name, CType_t type, CNode *ast) {
cv->defsite = NULL;
cv->loc = 0;
cv->weight = 0;
+ cv->reload = 0;
return cv;
}
diff --git a/semantics.h b/semantics.h
index 151ca5d..37cffb3 100644
--- a/semantics.h
+++ b/semantics.h
@@ -48,6 +48,7 @@ struct CVar {
CNode *initr;
CBList_t defsite;
int loc;
+ int reload;
/* the following fields are used for renaming */
int cnt;
int weight;
diff --git a/ssa.c b/ssa.c
index bab4ffe..82c865d 100644
--- a/ssa.c
+++ b/ssa.c
@@ -24,6 +24,7 @@ COpr_t copr_create(void) {
COpr_t opr = NEW(COpr);
opr->type = NULL;
opr->cval = NULL;
+ opr->same = opr;
opr->dep = 0;
opr->mod = 0;
opr->par = opr;
@@ -269,8 +270,6 @@ void cinst_print(FILE *f, CInst_t inst) {
case GT: op = ">"; break;
case LE: op = "<="; break;
case GE: op = ">="; break;
- case LOR: op = "||"; break;
- case LAND: op = "&&"; break;
case EQ: op = "=="; break;
case NE: op = "!="; break;
case NOR: op = "nor"; break;
@@ -1004,8 +1003,6 @@ COpr_t ssa_exp_(CNode *p, CBlock_t *cur, CInst_t lval, CBlock_t succ) {/*{{{*/
inst->src2 = rhs;
switch (op)
{
- case OPT_OR: inst->op = LOR; break;
- case OPT_AND: inst->op = LAND; break;
case OPT_SHL: inst->op = SHL; break;
case OPT_SHR: inst->op = SHR; break;
case '|': inst->op = OR; break;
@@ -1651,7 +1648,7 @@ void renaming_vars(COList_t oprs) {
CInst_t ld = cinst_create();
CVar_t var = p->opr->info.var;
var->cnt = 0;
- p->opr->mod = var->loc > 0 && var->type->type != CARR;
+ var->reload = var->loc > 0 && var->type->type != CARR;
ld->op = LOAD;
ld->dest = copr_create();
ld->dest->kind = VAR;
@@ -2158,6 +2155,7 @@ void register_alloc(void) {
}
void const_propagation(void) {
+#define IS_STATIC(opr) (!((opr)->mod || (opr)->info.var->reload))
int i;
for (i = bcnt - 1; i >= 0; i--)
{
@@ -2169,13 +2167,13 @@ void const_propagation(void) {
COpr_t t;
if (i->op == ADDR)
i->src1->mod = 1;
- if (i->src1 && i->src1->cval && !i->src1->mod)
+ if (i->src1 && i->src1->cval && IS_STATIC(i->src1))
{
t = i->src1->cval;
i->src1 = copr_create();
*(i->src1) = *t;
}
- if (i->src2 && i->src2->cval && !i->src2->mod)
+ if (i->src2 && i->src2->cval && IS_STATIC(i->src2))
{
t = i->src2->cval;
i->src2 = copr_create();
@@ -2215,8 +2213,6 @@ void const_propagation(void) {
case AND: immd = imm1 & imm2; break;
case XOR: immd = imm1 ^ imm2; break;
case OR: immd = imm1 | imm2; break;
- case LOR: immd = imm1 || imm2; break;
- case LAND: immd = imm1 && imm2; break;
case NOR: immd = ~(imm1 | imm2); break;
case EQ: immd = imm1 == imm2; break;
case NE: immd = imm1 != imm2; break;
@@ -2302,11 +2298,41 @@ void strength_reduction(void) {
}
}
+unsigned int copr_hash(COpr_t opr) {
+ if (!opr) return 0;
+ switch (opr->kind)
+ {
+ case VAR:
+ case TMP:
+ return (unsigned long)opr;
+ default:
+ return (unsigned int)opr->info.imm;
+ }
+}
+
+int copr_eq(COpr_t a, COpr_t b) {
+ if (a->kind != b->kind) return 0;
+ switch (a->kind)
+ {
+ case VAR:
+ case TMP:
+ return a == b;
+ case IMM:
+ return a->info.imm == b->info.imm;
+ case IMMS:
+ return a->info.cstr == b->info.cstr;
+ case IMMF:
+ return !strcmp(a->info.str, b->info.str);
+ default:
+ return 0;
+ }
+}
+
unsigned int cexpmap_hash(CInst_t exp) {
unsigned int res = 0;
res = ((unsigned int)exp->op) << 10;
- res ^= (unsigned long)exp->src1;
- res = (res << 1) ^ (unsigned long)exp->src2;
+ res ^= copr_hash(exp->src1);
+ res = (res << 1) ^ copr_hash(exp->src2);
return res;
}
@@ -2318,8 +2344,8 @@ CExpMap_t cexpmap_create(void) {
int cexpmap_comp(CInst_t exp1, CInst_t exp2) {
if (exp1->op != exp2->op) return 0;
- if (exp1->src1 != exp2->src1) return 0;
- return exp1->src2 == exp2->src2;
+ if (!copr_eq(exp1->src1, exp2->src1)) return 0;
+ return copr_eq(exp1->src2, exp2->src2);
}
void cexpmap_insert(CExpMap_t cem, CInst_t exp) {
@@ -2327,7 +2353,7 @@ void cexpmap_insert(CExpMap_t cem, CInst_t exp) {
CENode *np = NEW(CENode);
np->exp = exp;
np->next = cem->head[hv];
- cem->head[hv] = np->next;
+ cem->head[hv] = np;
}
CInst_t cexpmap_lookup(CExpMap_t cem, CInst_t exp) {
@@ -2345,7 +2371,7 @@ void cexpmap_clear(CExpMap_t cem) {
for (i = 0; i < MAX_TABLE_SIZE; cem->head[i++] = NULL)
for (p = cem->head[i]; p; p = np)
{
- np = p;
+ np = p->next;
free(p);
}
}
@@ -2354,6 +2380,11 @@ void cexpmap_destroy(CExpMap_t cem) {
cexpmap_clear(cem);
free(cem);
}
+void copr_shortcut(COpr_t *opr) {
+ COpr_t t = *opr;
+ if (!t) return;
+ *opr = t->same;
+}
void subexp_elimination(void) {
int i;
@@ -2361,15 +2392,45 @@ void subexp_elimination(void) {
for (i = bcnt - 1; i >= 0; i--)
{
CBlock_t b = blks[vis[i]];
- CInst_t i, ni, ih = b->insts;
- for (i = ih->next; i != ih; i = ni)
+ CInst_t i, ih = b->insts;
+ for (i = ih->next; i != ih; i = i->next)
{
- ni = i->next;
- switch (i->op)
+ CInst_t t;
+ if (i->op == MOVE)
{
- default: ;
+ i->dest->same = i->src1->same;
+ continue;
+ }
+ else if (i->op == CALL)
+ {
+ cexpmap_clear(cem);
+ continue;
+ }
+ copr_shortcut(&i->src1);
+ copr_shortcut(&i->src2);
+ t = cexpmap_lookup(cem, i);
+ if (t)
+ {
+ i->op = MOVE;
+ i->src1 = t->dest;
+ i->src2 = NULL;
+ i->dest->same = i->src1;
+ }
+ else
+ {
+ switch (i->op)
+ {
+ case MUL: case DIV: case MOD: case ADD: case SUB:
+ case SHL: case SHR: case AND: case XOR: case OR: case NOR:
+ case EQ: case NE: case LT: case GT: case LE: case GE:
+ case NEG:
+ cexpmap_insert(cem, i);
+ break;
+ default: ;
+ }
}
}
+ cexpmap_clear(cem);
}
cexpmap_destroy(cem);
}
@@ -2449,7 +2510,7 @@ void ssa_func(CType_t func) {
renaming_vars(oprs);
/* optimization on SSA */
const_propagation();
- subexp_elimination();
+/* subexp_elimination(); */
strength_reduction();
/* out of SSA */
mark_insts();
diff --git a/ssa.h b/ssa.h
index 307328b..0507a5c 100644
--- a/ssa.h
+++ b/ssa.h
@@ -32,15 +32,16 @@ struct COpr {
int sub;
int dep;
- int mod;
int reg; /* -1 for spilled, -2 for discarded */
int begin, end; /* for reg allocation */
+ int mod;
CType_t type;
CInst_t def;
CRange_t range;
COpr_t par; /* union-find */
COpr_t cval;
COpr_t spill; /* check this reference if spilled */
+ COpr_t same; /* for common exp elimination */
};
typedef struct COList COList;
@@ -67,7 +68,6 @@ struct CInst {
ADDR, /* get address */
MUL, DIV, MOD, ADD, SUB,
SHL, SHR, AND, XOR, OR, NOR,
- LOR, LAND,
EQ, NE, LT, GT, LE, GE,
NEG
} op;