commit f98725c44ba9e0107206fe692d57cc8d6ca4f454
parent 6ed7b3405e9d0358f51a4092496c3c08678bd627
Author: m21c <ho*******@gmail.com>
Date: Thu, 2 Feb 2023 05:05:15 +0100
worked on data-flow analysis
Diffstat:
| M | compiler.c | | | 521 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 521 insertions(+), 0 deletions(-)
diff --git a/compiler.c b/compiler.c
@@ -46,6 +46,15 @@ struct Env Env;
+typedef
+struct Gist Gist;
+
+typedef
+struct Conduct Conduct;
+
+typedef
+struct Block Block;
+
/* SECTION: - node kind table - */
@@ -395,6 +404,18 @@ enum Qualifier {
} Qualifier;
+typedef
+enum BlockKind {
+ BTOPLEVEL = 0,
+ BFUNCTION = 1,
+ BSCOPE = 2,
+ BIF = 3,
+ BLOOP = 4,
+ BWHILELOOP = 5,
+ BLOOPUNTIL = 6,
+ BFORLOOP = 7,
+ BELSE = 8
+} BlockKind;
@@ -522,6 +543,61 @@ struct Source {
} Source;
+struct Gist {
+ Decl *decl;
+ Conduct *parent;
+
+ bool init;
+ Node *where;
+
+ /* for other declarations */
+ Gist *prev, *next;
+};
+
+struct Block {
+ BlockKind kind;
+
+ Env *env;
+
+ /* Conduct-Sequence list*/
+ Conduct *head, *tail, *parent;
+
+ /* Neighbooring Blocks */
+ Block *prev, *next;
+};
+
+struct Conduct {
+ ConductKind kind;
+ uint id;
+
+ Node *label, *branch;
+ Node *first, *last;
+
+ bool doesbreak;
+ bool doescontinue;
+ bool doesreturn;
+ bool doesjump;
+
+ struct ConductGists {
+ Gist *head, *tail;
+ } gists;
+
+ struct ConductBranches {
+ /* Branch-relation from child to parents */
+ Conduct *head, *tail;
+
+ /* Branch-parent list */
+ Conduct *next, *prev;
+ } branches;
+
+ /* Block-stack */
+ Block *head, *tail, *parent;
+
+ /* Conduct-sequence list */
+ Conduct *next, *prev;
+};
+
+
/* SECTION: - global-vars - */
@@ -3889,6 +3965,445 @@ foldexpr(Env *env, Node *expr)
+/* SECTION: - data-flow analysis - */
+
+/*
+In order to do DFA, we divide the code of a scope into sections.
+For each section there will be a DF-Conduct associated with it.
+
+*/
+
+Block blockbuf[1024*8];
+int blocktop;
+
+Conduct conductbuf[1024*8];
+int conducttop;
+
+Gist gistbuf[1024*8];
+int gisttop;
+
+static Block *
+makeblock(BlockKind kind, Env *env)
+{
+ Block *block;
+
+ assert(blocktop < lengthof(blockbuf));
+
+ block = blockbuf + blocktop++;
+
+ memset(block, 0, sizeof(*block));
+
+ block->kind = kind;
+ block->env = env;
+
+ return block;
+}
+
+static Conduct *
+makeconduct(ConductKind kind, Node *label)
+{
+ Conduct *conduct;
+
+ assert(conducttop < lengthof(conductbuf));
+
+ conduct = conductbuf + conducttop++;
+
+ memset(conduct, 0, sizeof(*conduct));
+
+ conduct->kind = kind;
+ conduct->label = label;
+
+ return conduct;
+}
+
+static void
+transfergists(Conduct *source, Conduct *dest);
+
+static void
+appendconduct(Block *parent, ConductKind kind, Node *label)
+{
+ Conduct *conduct = makeconduct(kind, label);
+
+ if (!parent)
+ return;
+
+ conduct->parent = parent;
+
+ listappend(parent, conduct);
+
+ if (conduct->prev)
+ transfergists(conduct->prev, conduct);
+}
+
+static void
+appendblock(Conduct *parent, BlockKind kind, Env *env)
+{
+ Block *block = makeblock(kind, env);
+
+ appendconduct(block, CSCOPE, NULL);
+
+ if (!parent)
+ return;
+
+ block->parent = parent;
+
+ listappend(parent, block);
+
+ transfergists(parent, block->tail);
+}
+
+static Gist *
+makegist(Decl *decl, Node *where, bool init)
+{
+ Gist *gist;
+ assert(gisttop < lengthof(gistbuf));
+
+ gist = gistbuf + gisttop++;
+
+ memset(gist, 0, sizeof(*gist));
+
+ gist->decl = decl;
+ gist->where = where;
+ gist->init = init;
+
+ return gist;
+}
+
+static void
+appendgist(Conduct *conduct, Gist *info)
+{
+ info->parent = conduct;
+
+ listappendex(conduct, info, gists.head, gists.tail, prev, next);
+}
+
+static void
+transfergists(Conduct *source, Conduct *dest)
+{
+ Gist *info;
+
+ for (info = source->gists.head; info; info = info->next) {
+ Gist *copy = makegist(NULL, NULL, false);
+
+ *copy = *info;
+
+ appendgist(dest, copy);
+ }
+}
+
+static Gist *
+getgist(Conduct *conduct, Decl *decl)
+{
+ Gist *probe;
+ assert(conduct);
+
+ for (probe = conduct->gists.head; probe; probe = probe->next) {
+ if (probe->decl == decl)
+ return probe;
+ }
+
+ return NULL;
+}
+
+static void
+gistread(Conduct *conduct, Node *node)
+{
+ const char *name;
+ Decl *decl;
+ Gist *info;
+
+ if (!node || (node->kind != ADECLREF && node->kind != ADECL))
+ return;
+
+ decl = node->u.declref;
+
+ /* NOTE(m21c): additional checks require that this moves
+ * somewhere else. */
+ if ( decl->kind == DPARAM ||
+ (decl->kind == DVAR &&
+ decl->parentenv &&
+ decl->parentenv->kind == STOPLEVEL))
+ return;
+
+ name = getstring(idents, decl->key);
+ info = getgist(conduct, decl);
+
+ if (info) {
+ Node *where = info->where;
+
+ if (info->init)
+ return;
+
+ assert(where);
+ error(&node->loc, "use of un-initialized '%s'.", name);
+ /* TODO(m21c): change to notice or similiar,
+ * instead of warn */
+ warn(&where->loc, "last use of '%s' was here.", name);
+ } else {
+ error(&node->loc, "use of un-initialized '%s'.", name);
+ }
+}
+
+static void
+gistwrite(Conduct *conduct, Node *node, bool init)
+{
+ Decl *decl;
+ Gist *info;
+
+ if (!node || (node->kind != ADECLREF && node->kind != ADECL))
+ return;
+
+ decl = node->u.declref;
+
+ info = getgist(conduct, decl);
+ if (!info) {
+ info = makegist(decl, node, init);
+ appendgist(conduct, info);
+ return;
+ }
+
+ info->init = init;
+ info->where = node;
+}
+
+static void
+fetchblocks(Block *block, Node *expr);
+
+static void
+fetchscoped(Conduct *conduct, Node *expr, BlockKind kind)
+{
+ if (expr && expr->kind == ASCOPE) {
+ appendblock(conduct, kind, expr->u.env);
+ fetchblocks(conduct->tail, expr->lhs);
+
+ } else if (expr) {
+ assert(conduct->parent);
+ assert(conduct->parent->env);
+
+ appendblock(conduct, kind, conduct->parent->env);
+ fetchblocks(conduct->tail, expr);
+ }
+}
+
+static void
+fetchblocks(Block *block, Node *expr)
+{
+ Node *lhs, *rhs;
+
+ assert(expr);
+ assert(block);
+ assert(block->tail);
+
+ lhs = expr->lhs;
+ rhs = expr->rhs;
+
+ switch (expr->kind) {
+ /* unary read */
+ case ODEREF:
+ case OPLUS: case OMINUS:
+ case OBNOT:
+ case OLNOT:
+ case OCAST:
+ fetchblocks(block, lhs);
+ gistread(block->tail, lhs);
+ return;
+
+ /* unary read/write */
+ case OINC: case ODEC:
+ case OSUFINC: case OSUFDEC:
+ fetchblocks(block, lhs);
+ gistread(block->tail, lhs);
+ gistwrite(block->tail, lhs, true);
+ return;
+
+ /* binary read */
+ case OMUL: case ODIV: case OMOD:
+ case OADD: case OSUB:
+ case OBAND: case OBOR: case OXOR:
+ case OLSH: case ORSH: case OARSH:
+ case OEQU: case ONEQ:
+ case OLET: case OLEQ:
+ case OGRT: case OGEQ:
+ case OLAND: case OLOR:
+ fetchblocks(block, lhs);
+ gistread(block->tail, lhs);
+
+ fetchblocks(block, rhs);
+ gistread(block->tail, rhs);
+ return;
+
+
+ /* binary write */
+ case OASS:
+ fetchblocks(block, rhs);
+ gistread(block->tail, rhs);
+
+ fetchblocks(block, lhs);
+ gistwrite(block->tail, lhs, true);
+ return;
+
+ /* binary read/write */
+ case OMULA: case ODIVA: case OMODA:
+ case OADDA: case OSUBA:
+ case OLSHA: case ORSHA: case OARSHA:
+ case OANDA:
+ case OORA: case OXORA:
+ fetchblocks(block, rhs);
+ gistread(block->tail, rhs);
+
+ fetchblocks(block, lhs);
+ gistread(block->tail, lhs);
+ gistwrite(block->tail, lhs, true);
+ return;
+
+ case ASTMT:
+ advancestmt:
+ assert(lhs);
+
+ fetchblocks(block, lhs);
+
+ if (expr->rhs) {
+ assert(expr->rhs->kind == ASTMT);
+ expr = expr->rhs, lhs = expr->lhs;
+ goto advancestmt;
+ }
+ return;
+
+ case ADECL:
+ assert(expr->u.declref);
+ lhs = expr->u.declref->u.content;
+
+ if (expr->u.declref->kind == DFUNCTION) {
+ fetchscoped(block->tail, lhs, BFUNCTION);
+ appendconduct(block, CSCOPE, NULL);
+ } else if (lhs) {
+ appendblock(block->tail, BSCOPE, expr->u.env);
+ fetchblocks(block->tail->tail, lhs);
+ appendconduct(block, CSCOPE, NULL);
+ }
+
+ gistwrite(block->tail, expr, !!lhs);
+ return;
+
+ case ASCOPE:
+ assert(lhs);
+
+ appendblock(block->tail, BSCOPE, expr->u.env);
+ fetchblocks(block->tail->tail, lhs);
+ appendconduct(block, CSCOPE, NULL);
+ return;
+
+ case KIF:
+ assert(lhs);
+ assert(expr->u.payload);
+
+ fetchscoped(block->tail, lhs, BIF);
+ if (rhs)
+ fetchscoped(block->tail, rhs, BELSE);
+
+ appendconduct(block, CSCOPE, NULL);
+ return;
+
+ case KDO:
+ return;
+
+ case KLOOP:
+ return;
+
+ case ALOOPUNTIL:
+ return;
+
+ case KBREAK:
+ block->tail->doesbreak = true;
+ goto joinctrltransfer;
+
+ case KCONTINUE:
+ block->tail->doescontinue = true;
+ goto joinctrltransfer;
+
+ case KRETURN:
+ block->tail->doesreturn = true;
+ goto joinctrltransfer;
+
+ case KGOTO:
+ block->tail->doesjump = true;
+ joinctrltransfer:
+ appendconduct(block, CUNREACH, NULL);
+ return;
+
+ default:
+ case OADDR:
+ return;
+ }
+}
+
+static void
+debugprintconduct(Conduct *conduct, int indent);
+
+static void
+debugprintblock(Block *block, int indent)
+{
+ Block *curr;
+ assert(block);
+
+ for (curr = block; curr; curr = curr->next) {
+ int i;
+
+ for (i = 0; i < indent; ++i) {
+ printf("\t");
+ }
+
+ switch (curr->kind) {
+ case BTOPLEVEL: printf("\x1b[31mblock<toplevel>\x1b[0m\n"); break;
+ case BFUNCTION: printf("\x1b[31mblock<function>\x1b[0m\n"); break;
+ case BSCOPE: printf("\x1b[31mblock<scope>\x1b[0m\n"); break;
+ case BIF: printf("\x1b[31mblock<if>\x1b[0m\n"); break;
+ case BLOOP: printf("\x1b[31mblock<loop>\x1b[0m\n"); break;
+ case BWHILELOOP: printf("\x1b[31mblock<while-loop>\x1b[0m\n"); break;
+ case BLOOPUNTIL: printf("\x1b[31mblock<loop-until>\x1b[0m\n"); break;
+ case BFORLOOP: printf("\x1b[31mblock<for-loop>\x1b[0m\n"); break;
+ case BELSE: printf("\x1b[31mblock<else>\x1b[0m\n"); break;
+ }
+
+ if (curr->head)
+ debugprintconduct(curr->head, indent);
+ }
+}
+
+static void
+debugprintconduct(Conduct *conduct, int indent)
+{
+ Conduct *curr;
+ assert(conduct);
+
+ for (curr = conduct; curr; curr = curr->next) {
+ int i;
+
+ for (i = 0; i < indent; ++i) {
+ printf("\t");
+ }
+
+ switch (curr->kind) {
+ case CUNREACH: printf("\x1b[34mconduct<unreach>\x1b[0m\n"); break;
+ case CSCOPE: printf("\x1b[34mconduct<scope>\x1b[0m\n"); break;
+ case CLABEL: printf("\x1b[34mconduct<label>\x1b[0m\n"); break;
+ }
+
+ if (curr->head)
+ debugprintblock(curr->head, indent + 1);
+ }
+}
+
+static void
+dataflow(Block *block, Node *expr)
+{
+ assert(expr);
+
+ fetchblocks(block, expr);
+
+ debugprintblock(block, 0);
+}
+
/* SECTION: - print ast - */
@@ -4850,6 +5365,7 @@ int
main(int argc, char **argv)
{
Env *p;
+ Block *block;
Source *source = &testsource;
source->tabwidth = 8;
@@ -4871,6 +5387,8 @@ main(int argc, char **argv)
}
pushenv(source, STOPLEVEL);
+ block = makeblock(BTOPLEVEL, source->currenv);
+ appendconduct(block, CSCOPE, NULL);
while (getkind(source) != 0) {
/* printf("token:%i:%i: %c '%.*s'\n", lastline, lastcol + 1,
tok.u.id, currcol - lastcol, line + lastcol);*/
@@ -4888,6 +5406,7 @@ main(int argc, char **argv)
{
ast = typecheck(source->currenv, ast);
ast = foldexpr(source->currenv, ast);
+ dataflow(block, ast);
}
if (source->filein == stdin) {
@@ -4952,6 +5471,7 @@ main(int argc, char **argv)
if (p->stmts) {
p->stmts = typecheck(source->currenv, p->stmts);
p->stmts = foldexpr(source->currenv, p->stmts);
+ dataflow(block, p->stmts);
/* debug prints: */
highlight(stdout, HLINFO);
@@ -4968,6 +5488,7 @@ main(int argc, char **argv)
}
}
+ /* dfpopconduct(); */
popenv(source);
highlight(stdout, HLINFO);
