-#include <stdbool.h>
-#include <stddef.h>
-#include <stdint.h>
+#include <string.h>
#include <stdlib.h>
+#include "ast.h"
#include "list.h"
-#include "util.h"
-#include "scc.h"
+#include "tarjan.h"
-struct node {
- int lowlink;
- int index;
- bool onStack;
- void *data;
-};
-
-int ptrcmp(const void *l, const void *r)
+int iddeclcmp(const void *l, const void *r)
{
- return ((ptrdiff_t)((struct node *)l)->data)
- -((ptrdiff_t)((struct node *)r)->data);
+ return strcmp((char *)l, (*(struct decl **)r)->data.dfun->ident);
}
-int nodecmp(const void *l, const void *r)
+struct list *edges_expr(int ndecls, struct decl **decls, void *parent,
+ struct expr *expr, struct list *l)
{
- return ((ptrdiff_t)l) -((ptrdiff_t)((struct node *)r)->data);
+ if (expr == NULL)
+ return l;
+ switch(expr->type) {
+ case ebinop:
+ l = edges_expr(ndecls, decls, parent, expr->data.ebinop.l, l);
+ l = edges_expr(ndecls, decls, parent, expr->data.ebinop.r, l);
+ break;
+ case ebool:
+ break;
+ case echar:
+ break;
+ case efuncall:
+ for(int i = 0; i<expr->data.efuncall.nargs; i++)
+ l = edges_expr(ndecls, decls, parent,
+ expr->data.efuncall.args[i], l);
+ struct decl **to = bsearch(expr->data.efuncall.ident, decls,
+ ndecls, sizeof(struct decl *), iddeclcmp);
+ if (to == NULL) {
+ fprintf(stderr, "calling an unknown function\n");
+ } else {
+ struct edge *edge = safe_malloc(sizeof(struct edge));
+ edge->from = parent;
+ edge->to = (void *)*to;
+ l = list_cons(edge, l);
+ }
+ break;
+ case eint:
+ break;
+ case eident:
+ break;
+ case enil:
+ break;
+ case etuple:
+ l = edges_expr(ndecls, decls, parent,
+ expr->data.etuple.left, l);
+ l = edges_expr(ndecls, decls, parent,
+ expr->data.etuple.right, l);
+ break;
+ case estring:
+ break;
+ case eunop:
+ l = edges_expr(ndecls, decls, parent, expr->data.eunop.l, l);
+ break;
+ default:
+ die("Unsupported expr node\n");
+ }
+ return l;
}
-struct components *strongconnect(struct node *v, struct node **stack, int *sp,
- int *index, int nedges, struct edge *edges, struct components *components)
+struct list *edges_stmt(int ndecls, struct decl **decls, void *parent,
+ struct stmt *stmt, struct list *l)
{
- struct node *w;
- v->index = *index;
- v->lowlink = *index;
- (*index)++;
- stack[(*sp)++] = v;
- v->onStack = true;
-
- for (int i = 0; i<nedges; i++) {
- if (edges[i].from != v)
- continue;
- w = edges[i].to;
- if (w->index == -1) {
- components = strongconnect(w, stack, sp, index,
- nedges, edges, components);
- } else if (w->onStack) {
- v->lowlink = min(v->lowlink, w->index);
- }
+ switch(stmt->type) {
+ case sassign:
+ l = edges_expr(ndecls, decls, parent,
+ stmt->data.sassign.expr, l);
+ break;
+ case sif:
+ l = edges_expr(ndecls, decls, parent, stmt->data.sif.pred, l);
+ for (int i = 0; i<stmt->data.sif.nthen; i++)
+ l = edges_stmt(ndecls, decls, parent,
+ stmt->data.sif.then[i], l);
+ for (int i = 0; i<stmt->data.sif.nels; i++)
+ l = edges_stmt(ndecls, decls, parent,
+ stmt->data.sif.els[i], l);
+ break;
+ case sreturn:
+ l = edges_expr(ndecls, decls, parent, stmt->data.sreturn, l);
+ break;
+ case sexpr:
+ l = edges_expr(ndecls, decls, parent, stmt->data.sexpr, l);
+ break;
+ case svardecl:
+ l = edges_expr(ndecls, decls, parent,
+ stmt->data.svardecl->expr, l);
+ break;
+ case swhile:
+ l = edges_expr(ndecls, decls, parent,
+ stmt->data.swhile.pred, l);
+ for (int i = 0; i<stmt->data.swhile.nbody; i++)
+ l = edges_stmt(ndecls, decls, parent,
+ stmt->data.swhile.body[i], l);
+ break;
+ default:
+ die("Unsupported stmt node\n");
}
+ return l;
+}
- if (v->lowlink == v->index) {
- struct list *res = NULL;
- do {
- w = stack[--*sp];
- w->onStack = false;
- res = list_cons(w->data, res);
- } while (w != v);
- struct components *ng = safe_malloc(sizeof(struct components));
- ng->next = components;
- ng->nodes = list_to_array(res, &ng->nnodes, false);
- components = ng;
- }
- return components;
+int declcmp(const void *l, const void *r)
+{
+ return (*(struct decl **)l)->type - (*(struct decl **)r)->type;
}
-struct components *scc(int nnodes, void **nodedata, int nedges, struct edge *edgedata)
+struct ast *ast_scc(struct ast *ast)
{
- struct components *res = NULL;
- struct node *nodes = safe_malloc(nnodes*sizeof(struct node));
- for (int i = 0; i<nnodes; i++)
- nodes[i] = (struct node){.lowlink=-1, .index=-1,
- .onStack=false, .data=nodedata[i]};
- qsort(nodes, nnodes, sizeof(struct node), ptrcmp);
+ //Sort so that the functions are at the end
+ qsort(ast->decls, ast->ndecls, sizeof(struct decl *), declcmp);
+ //Index of the first function
+ int ffun;
+ for (ffun = 0; ffun<ast->ndecls; ffun++)
+ if (ast->decls[ffun]->type == dfundecl)
+ break;
+ //Number of functions
+ int nfun = ast->ndecls-ffun;
- struct edge *edges = safe_malloc(nedges*sizeof(struct edge));
- for (int i = 0; i<nedges; i++) {
- struct node *from = bsearch(edgedata[i].from, nodes, nnodes,
- sizeof(struct node), nodecmp);
- if (from == NULL) {
- fprintf(stderr, "edge from references unknown node\n");
- goto end;
- }
- struct node *to = bsearch(edgedata[i].to, nodes, nnodes,
- sizeof(struct node), nodecmp);
- if (to == NULL) {
- fprintf(stderr, "edge to references unknown node\n");
- goto end;
+ //Calculate the edges
+ struct decl **fundecls = ast->decls+ffun;
+ struct list *edges = NULL;
+ for (int i = 0; i<nfun; i++)
+ for (int j = 0; j<fundecls[i]->data.dfun->nbody; j++)
+ edges = edges_stmt(nfun, fundecls, fundecls[i],
+ fundecls[i]->data.dfun->body[j], edges);
+ int nedges;
+ struct edge **edgedata = (struct edge **)
+ list_to_array(edges, &nedges, false);
+
+ // Do tarjan's and convert back into the declaration list
+ struct components *cs = scc(nfun, (void **)fundecls, nedges, edgedata);
+ int i = ffun;
+ FOREACHCOMP(c, cs) {
+ struct decl *d = safe_malloc(sizeof(struct decl));
+ if (c->nnodes > 1) {
+ d->type = dcomp;
+ d->data.dcomp.ndecls = c->nnodes;
+ d->data.dcomp.decls = safe_malloc(
+ c->nnodes*sizeof(struct fundecl *));
+ for (int i = 0; i<c->nnodes; i++)
+ d->data.dcomp.decls[i] =
+ ((struct decl *)c->nodes[i])->data.dfun;
+ } else {
+ d->type = dfundecl;
+ d->data.dfun = ((struct decl *)c->nodes[0])->data.dfun;
}
- edges[i] = (struct edge){.from=from, .to=to};
+ ast->decls[i++] = d;
}
+ ast->ndecls = i;
- struct node **stack = safe_malloc(nnodes*sizeof(struct node *));
- int sp = 0;
- int index = 0;
- for (int i = 0; i < nnodes; i++)
- if (nodes[i].index == -1)
- res = strongconnect(&nodes[i], stack, &sp, &index,
- nedges, edges, res);
-end:
- free(stack);
- free(nodes);
- free(edges);
- return res;
-}
-
-void components_free(struct components *cs, void (*freefun)(void *))
-{
- while (cs != NULL) {
- if (freefun != NULL)
- for (int i = 0; i<cs->nnodes; i++)
- freefun(cs->nodes[i]);
- free(cs->nodes);
- struct components *t = cs->next;
- free(cs);
- cs = t;
- }
+ //Cleanup
+ for (int i = 0; i<nedges; i++)
+ free(edgedata[i]);
+ free(edgedata);
+ components_free(cs, free);
+ return ast;
}
-//
-//int main ()
-//{
-// void *nodes[] = {(void *)1, (void *)2, (void *)3};
-// struct edge edges[] = {{(void *)1, (void *)2}, {(void *)2, (void *)1}};
-// struct components *cs = scc(3, &nodes[0], 2, &edges[0]);
-// FOREACHCOMP(c, cs) {
-// fprintf(stderr, "comp: ");
-// for (int i = 0; i<c->nnodes; i++)
-// fprintf(stderr, "%d, ", c->nodes[i]);
-// fprintf(stderr, "\n");
-// }
-// components_free(cs, NULL);
-//}
repositories / ccc.git / blobdiff