diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | alias.c | 154 | ||||
| -rw-r--r-- | all.h | 29 |
3 files changed, 183 insertions, 2 deletions
diff --git a/Makefile b/Makefile index 64531ea..19bf777 100644 --- a/Makefile +++ b/Makefile @@ -4,7 +4,7 @@ ABI = sysv V = @ OBJDIR = obj -SRC = main.c util.c parse.c cfg.c mem.c ssa.c copy.c fold.c live.c $(ABI).c isel.c spill.c rega.c emit.c +SRC = main.c util.c parse.c cfg.c mem.c ssa.c alias.c copy.c fold.c live.c $(ABI).c isel.c spill.c rega.c emit.c OBJ = $(SRC:%.c=$(OBJDIR)/%.o) CFLAGS += -Wall -Wextra -std=c99 -g -pedantic diff --git a/alias.c b/alias.c new file mode 100644 index 0000000..3d1d00c --- /dev/null +++ b/alias.c @@ -0,0 +1,154 @@ +#include "all.h" + +static void +getalias(Alias *a, Ref r, Fn *fn) +{ + Con *c; + + switch (rtype(r)) { + default: + die("unreachable"); + case RTmp: + *a = fn->tmp[r.val].alias; + assert(a->type != ABot); + break; + case RCon: + c = &fn->con[r.val]; + if (c->type == CAddr) { + a->type = ASym; + strcpy(a->label, c->label); + } else + a->type = ACon; + a->offset = c->bits.i; + break; + } +} + +int +alias(Ref p, int sp, Ref q, int sq, int *delta, Fn *fn) +{ + Alias ap, aq; + int ovlap; + + getalias(&ap, p, fn); + getalias(&aq, q, fn); + *delta = ap.offset - aq.offset; + ovlap = ap.offset < aq.offset + sq && aq.offset < ap.offset + sp; + + if (ap.type & aq.type & 1) { + /* if both are offsets of the same + * stack slot, they alias iif they + * overlap */ + if (req(ap.base, aq.base) && ovlap) + return MustAlias; + return NoAlias; + } + + if (ap.type == ASym && aq.type == ASym) { + /* they conservatively alias if the + * symbols are different, or they + * alias for sure if they overlap */ + if (strcmp(ap.label, aq.label) != 0) + return MayAlias; + if (ovlap) + return MustAlias; + return NoAlias; + } + + if ((ap.type == ACon && aq.type == ACon) + || (ap.type == aq.type && req(ap.base, aq.base))) { + assert(ap.type == ACon || ap.type == AUnk); + /* if they have the same base, we + * can rely on the offsets only */ + if (ovlap) + return MustAlias; + return NoAlias; + } + + /* if one of the two is unknown + * there may be aliasing unless + * the other is provably local */ + if (ap.type == AUnk && aq.type != ALoc) + return MayAlias; + if (aq.type == AUnk && ap.type != ALoc) + return MayAlias; + + return NoAlias; +} + +int +escapes(Ref r, Fn *fn) +{ + if (rtype(r) != RTmp) + return 1; + return fn->tmp[r.val].alias.type != ALoc; +} + +static void +esc(Ref r, Fn *fn) +{ + Alias *a; + + assert(rtype(r) <= RType); + if (rtype(r) == RTmp) { + a = &fn->tmp[r.val].alias; + assert(a->type != ABot); + if (a->type == ALoc) + a->type = AEsc; + } +} + +void +fillalias(Fn *fn) +{ + int n; + Blk *b; + Phi *p; + Ins *i; + Alias *a, a0, a1; + + for (n=0; n<fn->nblk; ++n) { + b = fn->rpo[n]; + for (p=b->phi; p; p=p->link) { + assert(rtype(p->to) == RTmp); + a = &fn->tmp[p->to.val].alias; + assert(a->type == ABot); + a->type = AUnk; + a->base = p->to; + a->offset = 0; + } + for (i=b->ins; i<&b->ins[b->nins]; ++i) { + a = 0; + if (!req(i->to, R)) { + assert(rtype(i->to) == RTmp); + a = &fn->tmp[i->to.val].alias; + assert(a->type == ABot); + if (Oalloc <= i->op && i->op <= Oalloc1) + a->type = ALoc; + else + a->type = AUnk; + a->base = i->to; + a->offset = 0; + } + if (i->op == Oadd) { + getalias(&a0, i->arg[0], fn); + getalias(&a1, i->arg[1], fn); + if (a0.type == ACon) { + *a = a1; + a->offset += a0.offset; + } + else if (a1.type == ACon) { + *a = a0; + a->offset += a1.offset; + } + } + if (req(i->to, R) || a->type == AUnk) { + if (!isload(i->op)) + esc(i->arg[0], fn); + if (!isstore(i->op)) + esc(i->arg[1], fn); + } + } + esc(b->jmp.arg, fn); + } +} diff --git a/all.h b/all.h index 6b1951d..943480a 100644 --- a/all.h +++ b/all.h @@ -20,6 +20,7 @@ typedef struct Ins Ins; typedef struct Phi Phi; typedef struct Blk Blk; typedef struct Use Use; +typedef struct Alias Alias; typedef struct Tmp Tmp; typedef struct Con Con; typedef struct Addr Mem; @@ -104,8 +105,8 @@ struct Ref { enum { RTmp, RCon, - RSlot, RType, + RSlot, RCall, RMem, }; @@ -362,6 +363,26 @@ struct Use { } u; }; +enum { + NoAlias, + MayAlias, + MustAlias +}; + +struct Alias { + enum { + ABot = 0, + ALoc = 1, /* stack local */ + ACon = 2, + AEsc = 3, /* stack escaping */ + ASym = 4, + AUnk = 6, + } type; + Ref base; + char label[NString]; + int64_t offset; +}; + struct Tmp { char name[NString]; Use *use; @@ -374,6 +395,7 @@ struct Tmp { bits m; } hint; int phi; + Alias alias; int visit; }; @@ -534,6 +556,11 @@ void fillfron(Fn *); /* mem.c */ void memopt(Fn *); +/* alias.c */ +void fillalias(Fn *); +int alias(Ref, int, Ref, int, int *, Fn *); +int escapes(Ref, Fn *); + /* ssa.c */ void filluse(Fn *); void fillpreds(Fn *); |