scc.c

   1 #include <string.h>
   2 #include <stdlib.h>
   3
   4 #include "ast.h"
   5 #include "list.h"
   6 #include "tarjan.h"
   7
   8 int iddeclcmp(const void *l, const void *r)
   9 {
  10         return strcmp((char *)l, (*(struct decl **)r)->data.dfun->ident);
  11 }
  12
  13 struct list *edges_expr(int ndecls, struct decl **decls, void *parent,
  14         struct expr *expr, struct list *l)
  15 {
  16         if (expr == NULL)
  17                 return l;
  18         switch(expr->type) {
  19         case ebinop:
  20                 l = edges_expr(ndecls, decls, parent, expr->data.ebinop.l, l);
  21                 l = edges_expr(ndecls, decls, parent, expr->data.ebinop.r, l);
  22                 break;
  23         case ebool:
  24                 break;
  25         case echar:
  26                 break;
  27         case efuncall:
  28                 for(int i = 0; i<expr->data.efuncall.nargs; i++)
  29                         l = edges_expr(ndecls, decls, parent,
  30                                 expr->data.efuncall.args[i], l);
  31                 struct decl **to = bsearch(expr->data.efuncall.ident, decls,
  32                         ndecls, sizeof(struct decl *), iddeclcmp);
  33                 if (to == NULL) {
  34                         fprintf(stderr, "calling an unknown function\n");
  35                 } else {
  36                         struct edge *edge = safe_malloc(sizeof(struct edge));
  37                         edge->from = parent;
  38                         edge->to = (void *)*to;
  39                         l = list_cons(edge, l);
  40                 }
  41                 break;
  42         case eint:
  43                 break;
  44         case eident:
  45                 break;
  46         case enil:
  47                 break;
  48         case etuple:
  49                 l = edges_expr(ndecls, decls, parent,
  50                         expr->data.etuple.left, l);
  51                 l = edges_expr(ndecls, decls, parent,
  52                         expr->data.etuple.right, l);
  53                 break;
  54         case estring:
  55                 break;
  56         case eunop:
  57                 l = edges_expr(ndecls, decls, parent, expr->data.eunop.l, l);
  58                 break;
  59         default:
  60                 die("Unsupported expr node\n");
  61         }
  62         return l;
  63 }
  64
  65 struct list *edges_stmt(int ndecls, struct decl **decls, void *parent,
  66                 struct stmt *stmt, struct list *l)
  67 {
  68         switch(stmt->type) {
  69         case sassign:
  70                 l = edges_expr(ndecls, decls, parent,
  71                         stmt->data.sassign.expr, l);
  72                 break;
  73         case sif:
  74                 l = edges_expr(ndecls, decls, parent, stmt->data.sif.pred, l);
  75                 for (int i = 0; i<stmt->data.sif.nthen; i++)
  76                         l = edges_stmt(ndecls, decls, parent,
  77                                 stmt->data.sif.then[i], l);
  78                 for (int i = 0; i<stmt->data.sif.nels; i++)
  79                         l = edges_stmt(ndecls, decls, parent,
  80                                 stmt->data.sif.els[i], l);
  81                 break;
  82         case sreturn:
  83                 l = edges_expr(ndecls, decls, parent, stmt->data.sreturn, l);
  84                 break;
  85         case sexpr:
  86                 l = edges_expr(ndecls, decls, parent, stmt->data.sexpr, l);
  87                 break;
  88         case svardecl:
  89                 l = edges_expr(ndecls, decls, parent,
  90                         stmt->data.svardecl->expr, l);
  91                 break;
  92         case swhile:
  93                 l = edges_expr(ndecls, decls, parent,
  94                         stmt->data.swhile.pred, l);
  95                 for (int i = 0; i<stmt->data.swhile.nbody; i++)
  96                         l = edges_stmt(ndecls, decls, parent,
  97                                 stmt->data.swhile.body[i], l);
  98                 break;
  99         default:
 100                 die("Unsupported stmt node\n");
 101         }
 102         return l;
 103 }
 104
 105 int declcmp(const void *l, const void *r)
 106 {
 107         return (*(struct decl **)l)->type - (*(struct decl **)r)->type;
 108 }
 109
 110 struct ast *ast_scc(struct ast *ast)
 111 {
 112         //Sort so that the functions are at the end
 113         qsort(ast->decls, ast->ndecls, sizeof(struct decl *), declcmp);
 114         //Index of the first function
 115         int ffun;
 116         for (ffun = 0; ffun<ast->ndecls; ffun++)
 117                 if (ast->decls[ffun]->type == dfundecl)
 118                         break;
 119         //Number of functions
 120         int nfun = ast->ndecls-ffun;
 121
 122         //Calculate the edges
 123         struct decl **fundecls = ast->decls+ffun;
 124         struct list *edges = NULL;
 125         for (int i = 0; i<nfun; i++)
 126                 for (int j = 0; j<fundecls[i]->data.dfun->nbody; j++)
 127                         edges = edges_stmt(nfun, fundecls, fundecls[i],
 128                                 fundecls[i]->data.dfun->body[j], edges);
 129         int nedges;
 130         struct edge **edgedata = (struct edge **)
 131                 list_to_array(edges, &nedges, false);
 132
 133         // Do tarjan's and convert back into the declaration list
 134         int err;
 135         struct components *cs = tarjans(nfun, (void **)fundecls, nedges, edgedata, &err);
 136         if (cs == NULL) {
 137                 if (err == 1)
 138                         die("malformed edges in tarjan's????");
 139                 else
 140                         pdie("malloc");
 141         }
 142
 143         int i = ffun;
 144         FOREACHCOMP(c, cs) {
 145                 struct decl *d = safe_malloc(sizeof(struct decl));
 146                 if (c->nnodes > 1) {
 147                         d->type = dcomp;
 148                         d->data.dcomp.ndecls = c->nnodes;
 149                         d->data.dcomp.decls = safe_malloc(
 150                                 c->nnodes*sizeof(struct fundecl *));
 151                         for (int i = 0; i<c->nnodes; i++)
 152                                 d->data.dcomp.decls[i] =
 153                                         ((struct decl *)c->nodes[i])->data.dfun;
 154                 } else {
 155                         d->type = dfundecl;
 156                         d->data.dfun = ((struct decl *)c->nodes[0])->data.dfun;
 157                 }
 158                 ast->decls[i++] = d;
 159         }
 160         ast->ndecls = i;
 161
 162         //Cleanup
 163         for (int i = 0; i<nedges; i++)
 164                 free(edgedata[i]);
 165         free(edgedata);
 166         components_free(cs, free);
 167         return ast;
 168 }