ref: 58d89cfed95d30bcd7fdfed4973237121803ad70
dir: /mi/cfg.c/
#include <stdlib.h>
#include <stdio.h>
#include <inttypes.h>
#include <stdarg.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include "parse.h"
#include "mi.h"
static Bb *mkbb(Cfg *cfg)
{
Bb *bb;
bb = zalloc(sizeof(Bb));
bb->id = cfg->nextbbid++;
bb->pred = mkbs();
bb->succ = mkbs();
lappend(&cfg->bb, &cfg->nbb, bb);
return bb;
}
static char *lblstr(Node *n)
{
assert(exprop(n) == Olit);
assert(n->expr.args[0]->type == Nlit);
assert(n->expr.args[0]->lit.littype == Llbl);
return n->expr.args[0]->lit.lblval;
}
static void strlabel(Cfg *cfg, char *lbl, Bb *bb)
{
htput(cfg->lblmap, lbl, bb);
lappend(&bb->lbls, &bb->nlbls, lbl);
}
static void label(Cfg *cfg, Node *lbl, Bb *bb)
{
strlabel(cfg, lblstr(lbl), bb);
}
static int isnonretcall(Node *fn)
{
Node *dcl;
if (exprop(fn) != Ovar)
return 0;
dcl = decls[fn->expr.did];
return dcl->decl.isnoret;
}
static int addnode(Cfg *cfg, Bb *bb, Node *n)
{
switch (exprop(n)) {
case Ojmp:
case Ocjmp:
case Oret:
lappend(&bb->nl, &bb->nnl, n);
lappend(&cfg->fixjmp, &cfg->nfixjmp, n);
lappend(&cfg->fixblk, &cfg->nfixblk, bb);
return 1;
break;
case Ocall:
lappend(&bb->nl, &bb->nnl, n);
return isnonretcall(n->expr.args[0]);
break;
default:
lappend(&bb->nl, &bb->nnl, n);
break;
}
return 0;
}
static int islabel(Node *n)
{
Node *l;
if (n->type != Nexpr)
return 0;
if (exprop(n) != Olit)
return 0;
l = n->expr.args[0];
if (l->type != Nlit)
return 0;
if (l->lit.littype != Llbl)
return 0;
return 1;
}
static Bb *addlabel(Cfg *cfg, Bb *bb, Node **nl, size_t i, Srcloc loc)
{
/* if the current block assumes fall-through, insert an explicit jump */
if (i > 0 && nl[i - 1]->type == Nexpr) {
if (exprop(nl[i - 1]) != Ocjmp && exprop(nl[i - 1]) != Ojmp)
addnode(cfg, bb, mkexpr(loc, Ojmp, mklbl(loc, lblstr(nl[i])), NULL));
}
if (bb->nnl)
bb = mkbb(cfg);
label(cfg, nl[i], bb);
return bb;
}
void delete(Cfg *cfg, Bb *bb)
{
size_t i, j;
if (bb == cfg->start || bb == cfg->end)
return;
for (i = 0; bsiter(bb->pred, &i); i++) {
bsunion(cfg->bb[i]->succ, bb->succ);
bsdel(cfg->bb[i]->succ, bb->id);
}
for (i = 0; bsiter(bb->succ, &i); i++) {
bsunion(cfg->bb[i]->pred, bb->pred);
bsdel(cfg->bb[i]->pred, bb->id);
for (j = 0; j < bb->nlbls; j++)
strlabel(cfg, bb->lbls[j], cfg->bb[i]);
}
cfg->bb[bb->id] = NULL;
}
void noexit(Cfg *cfg, Bb *bb)
{
size_t i;
for (i = 0; bsiter(bb->succ, &i); i++)
bsdel(cfg->bb[i]->pred, bb->id);
bsclear(bb->succ);
}
void trimdead(Cfg *cfg, Bb *bb)
{
size_t i;
if (!bb)
return;
for (i = 0; i < bb->nnl; i++) {
switch (exprop(bb->nl[i])) {
/* if we're jumping, we can't keep going
* within this BB */
case Ojmp:
case Ocjmp:
case Oret:
bb->nnl = i + 1;
return;
case Odead:
noexit(cfg, bb);
bb->nnl = i + 1;
return;
case Ocall:
if (isnonretcall(bb->nl[i]->expr.args[0])) {
noexit(cfg, bb);
bb->nnl = i + 1;
return;
}
break;
default:
/* nothing */
break;
}
}
}
void trim(Cfg *cfg)
{
Bb *bb;
size_t i;
int deleted;
deleted = 1;
while (deleted) {
deleted = 0;
for (i = 0; i < cfg->nbb; i++) {
bb = cfg->bb[i];
if (bb == cfg->start || bb == cfg->end)
continue;
trimdead(cfg, bb);
if (bb && bsisempty(bb->pred)) {
delete(cfg, bb);
deleted = 1;
}
}
}
}
Cfg *mkcfg(Node *fn, Node **nl, size_t nn)
{
Cfg *cfg;
Bb *pre, *post;
Bb *bb, *targ;
Node *a, *b;
static int nextret;
char buf[32];
size_t i;
cfg = zalloc(sizeof(Cfg));
cfg->fn = fn;
cfg->lblmap = mkht(strhash, streq);
pre = mkbb(cfg);
bb = mkbb(cfg);
for (i = 0; i < nn; i++) {
switch (nl[i]->type) {
case Nexpr:
if (islabel(nl[i]))
bb = addlabel(cfg, bb, nl, i, nl[i]->loc);
else if (addnode(cfg, bb, nl[i]))
bb = mkbb(cfg);
break;
break;
case Ndecl:
break;
default:
die("Invalid node type %s in mkcfg", nodestr[nl[i]->type]);
}
}
post = mkbb(cfg);
bprintf(buf, sizeof buf, ".R%d", nextret++);
label(cfg, mklbl(fn->loc, buf), post);
cfg->start = pre;
cfg->end = post;
bsput(pre->succ, cfg->bb[1]->id);
bsput(cfg->bb[1]->pred, pre->id);
bsput(cfg->bb[cfg->nbb - 2]->succ, post->id);
bsput(post->pred, cfg->bb[cfg->nbb - 2]->id);
for (i = 0; i < cfg->nfixjmp; i++) {
bb = cfg->fixblk[i];
switch (exprop(cfg->fixjmp[i])) {
case Ojmp:
a = cfg->fixjmp[i]->expr.args[0];
b = NULL;
break;
case Ocjmp:
a = cfg->fixjmp[i]->expr.args[1];
b = cfg->fixjmp[i]->expr.args[2];
break;
case Oret:
a = mklbl(cfg->fixjmp[i]->loc, cfg->end->lbls[0]);
b = NULL;
break;
default:
die("Bad jump fix thingy");
break;
}
if (a) {
targ = htget(cfg->lblmap, lblstr(a));
if (!targ)
die("No bb with label \"%s\"", lblstr(a));
bsput(bb->succ, targ->id);
bsput(targ->pred, bb->id);
}
if (b) {
targ = htget(cfg->lblmap, lblstr(b));
if (!targ)
die("No bb with label \"%s\"", lblstr(b));
bsput(bb->succ, targ->id);
bsput(targ->pred, bb->id);
}
}
trim(cfg);
return cfg;
}
void dumpcfg(Cfg *cfg, FILE *fd)
{
size_t i, j;
Bb *bb;
char *sep;
for (j = 0; j < cfg->nbb; j++) {
bb = cfg->bb[j];
if (!bb)
continue;
fprintf(fd, "\n");
fprintf(fd, "Bb: %d labels=(", bb->id);
sep = "";
for (i = 0; i < bb->nlbls; i++) {;
fprintf(fd, "%s%s", bb->lbls[i], sep);
sep = ",";
}
fprintf(fd, ")\n");
/* in edges */
fprintf(fd, "Pred: ");
sep = "";
for (i = 0; i < bsmax(bb->pred); i++) {
if (bshas(bb->pred, i)) {
fprintf(fd, "%s%zd", sep, i);
sep = ",";
}
}
fprintf(fd, "\n");
/* out edges */
fprintf(fd, "Succ: ");
sep = "";
for (i = 0; i < bsmax(bb->succ); i++) {
if (bshas(bb->succ, i)) {
fprintf(fd, "%s%zd", sep, i);
sep = ",";
}
}
fprintf(fd, "\n");
for (i = 0; i < bb->nnl; i++)
dump(bb->nl[i], fd);
fprintf(fd, "\n");
}
}