9 #define min(x, y) ((x)<(y) ? (x) : (y))
20 struct components
*next
;
36 struct components
*head
;
37 struct components
*tail
;
40 static int nodecmp(const void *l
, const void *r
)
42 return (ptrdiff_t)l
-(ptrdiff_t)((struct node
*)r
)->data
;
45 static int strongconnect(struct node
*v
, struct tjstate
*tj
)
49 /* Set the depth index for v to the smallest unused index */
51 v
->lowlink
= tj
->index
;
53 tj
->stack
[tj
->sp
] = v
;
57 for (int i
= 0; i
<tj
->nedges
; i
++) {
58 /* Only consider nodes reachable from v */
59 if (tj
->edges
[i
].from
!= v
)
62 /* Successor w has not yet been visited; recurse on it */
64 int r
= strongconnect(w
, tj
);
67 v
->lowlink
= min(v
->lowlink
, w
->lowlink
);
68 /* Successor w is in stack S and hence in the current SCC */
69 } else if (w
->onStack
) {
70 v
->lowlink
= min(v
->lowlink
, w
->index
);
74 /* If v is a root node, pop the stack and generate an SCC */
75 if (v
->lowlink
== v
->index
) {
76 struct components
*ng
= safe_malloc(sizeof(struct components
));
86 w
= tj
->stack
[tj
->sp
];
90 ng
->nodes
= safe_malloc(ng
->nnodes
*sizeof(void *));
91 for (int i
= 0; i
<ng
->nnodes
; i
++)
92 ng
->nodes
[i
] = tj
->stack
[tj
->sp
+i
]->data
;
97 static int ptrcmp(const void *l
, const void *r
)
99 return (ptrdiff_t)((struct node
*)l
)->data
100 - (ptrdiff_t)((struct node
*)r
)->data
;
104 * Calculate the strongly connected components using Tarjan's algorithm:
105 * en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
107 * Returns NULL when there are invalid edges
109 * @param number of nodes
110 * @param data of the nodes
111 * @param number of edges
112 * @param data of edges
114 struct components
*tarjans(
115 int nnodes
, void *nodedata
[],
116 int nedges
, struct edge
*edgedata
[])
118 struct node nodes
[nnodes
];
119 struct edge edges
[nedges
];
120 struct node
*stack
[nnodes
];
121 struct node
*from
, *to
;
122 struct tjstate tj
= {0, 0, nedges
, edges
, stack
, NULL
, .tail
=NULL
};
124 // Populate the nodes
125 for (int i
= 0; i
<nnodes
; i
++)
126 nodes
[i
] = (struct node
){-1, -1, false, nodedata
[i
]};
127 qsort(nodes
, nnodes
, sizeof(struct node
), ptrcmp
);
129 // Populate the edges
130 for (int i
= 0; i
<nedges
; i
++) {
131 from
= bsearch(edgedata
[i
]->from
, nodes
, nnodes
,
132 sizeof(struct node
), nodecmp
);
134 die("malformed from component of edge\n");
135 to
= bsearch(edgedata
[i
]->to
, nodes
, nnodes
,
136 sizeof(struct node
), nodecmp
);
138 die("malformed to component of edge\n");
139 edges
[i
] = (struct edge
){.from
=from
, .to
=to
};
143 for (int i
= 0; i
< nnodes
; i
++)
144 if (nodes
[i
].index
== -1)
145 strongconnect(&nodes
[i
], &tj
);
149 int iddeclcmp(const void *l
, const void *r
)
151 return strcmp((char *)l
, (*(struct decl
**)r
)->data
.dfun
->ident
);
154 struct list
*edges_expr(int ndecls
, struct decl
**decls
, void *parent
,
155 struct expr
*expr
, struct list
*l
)
161 l
= edges_expr(ndecls
, decls
, parent
, expr
->data
.ebinop
.l
, l
);
162 l
= edges_expr(ndecls
, decls
, parent
, expr
->data
.ebinop
.r
, l
);
169 for(int i
= 0; i
<expr
->data
.efuncall
.nargs
; i
++)
170 l
= edges_expr(ndecls
, decls
, parent
,
171 expr
->data
.efuncall
.args
[i
], l
);
172 struct decl
**to
= bsearch(expr
->data
.efuncall
.ident
, decls
,
173 ndecls
, sizeof(struct decl
*), iddeclcmp
);
175 die("calling an unknown function\n");
177 struct edge
*edge
= safe_malloc(sizeof(struct edge
));
179 edge
->to
= (void *)*to
;
180 l
= list_cons(edge
, l
);
190 l
= edges_expr(ndecls
, decls
, parent
,
191 expr
->data
.etuple
.left
, l
);
192 l
= edges_expr(ndecls
, decls
, parent
,
193 expr
->data
.etuple
.right
, l
);
198 l
= edges_expr(ndecls
, decls
, parent
, expr
->data
.eunop
.l
, l
);
201 die("Unsupported expr node\n");
206 struct list
*edges_stmt(int ndecls
, struct decl
**decls
, void *parent
,
207 struct stmt
*stmt
, struct list
*l
)
211 l
= edges_expr(ndecls
, decls
, parent
,
212 stmt
->data
.sassign
.expr
, l
);
215 l
= edges_expr(ndecls
, decls
, parent
, stmt
->data
.sif
.pred
, l
);
216 for (int i
= 0; i
<stmt
->data
.sif
.nthen
; i
++)
217 l
= edges_stmt(ndecls
, decls
, parent
,
218 stmt
->data
.sif
.then
[i
], l
);
219 for (int i
= 0; i
<stmt
->data
.sif
.nels
; i
++)
220 l
= edges_stmt(ndecls
, decls
, parent
,
221 stmt
->data
.sif
.els
[i
], l
);
224 l
= edges_expr(ndecls
, decls
, parent
, stmt
->data
.sreturn
, l
);
227 l
= edges_expr(ndecls
, decls
, parent
, stmt
->data
.sexpr
, l
);
230 l
= edges_expr(ndecls
, decls
, parent
,
231 stmt
->data
.svardecl
->expr
, l
);
234 l
= edges_expr(ndecls
, decls
, parent
,
235 stmt
->data
.swhile
.pred
, l
);
236 for (int i
= 0; i
<stmt
->data
.swhile
.nbody
; i
++)
237 l
= edges_stmt(ndecls
, decls
, parent
,
238 stmt
->data
.swhile
.body
[i
], l
);
241 die("Unsupported stmt node\n");
246 int declcmp(const void *l
, const void *r
)
248 return (*(struct decl
**)l
)->type
- (*(struct decl
**)r
)->type
;
251 struct ast
*ast_scc(struct ast
*ast
)
253 //Sort so that the functions are at the end
254 qsort(ast
->decls
, ast
->ndecls
, sizeof(struct decl
*), declcmp
);
255 //Index of the first function
257 for (ffun
= 0; ffun
<ast
->ndecls
; ffun
++)
258 if (ast
->decls
[ffun
]->type
== dfundecl
)
260 //Number of functions
261 int nfun
= ast
->ndecls
-ffun
;
263 //Calculate the edges
264 struct decl
**fundecls
= ast
->decls
+ffun
;
265 struct list
*edges
= NULL
;
266 for (int i
= 0; i
<nfun
; i
++)
267 for (int j
= 0; j
<fundecls
[i
]->data
.dfun
->nbody
; j
++)
268 edges
= edges_stmt(nfun
, fundecls
, fundecls
[i
],
269 fundecls
[i
]->data
.dfun
->body
[j
], edges
);
271 struct edge
**edata
= (struct edge
**)
272 list_to_array(edges
, &nedges
, false);
274 // Do tarjan's and convert back into the declaration list
275 struct components
*cs
= tarjans(nfun
, (void **)fundecls
, nedges
, edata
);
277 die("malformed edges in tarjan's????");
280 for (struct components
*c
= cs
; c
!= NULL
; c
= c
->next
) {
281 struct decl
*d
= safe_malloc(sizeof(struct decl
));
284 d
->data
.dcomp
.ndecls
= c
->nnodes
;
285 d
->data
.dcomp
.decls
= safe_malloc(
286 c
->nnodes
*sizeof(struct fundecl
*));
287 for (int i
= 0; i
<c
->nnodes
; i
++)
288 d
->data
.dcomp
.decls
[i
] =
289 ((struct decl
*)c
->nodes
[i
])->data
.dfun
;
292 d
->data
.dfun
= ((struct decl
*)c
->nodes
[0])->data
.dfun
;
299 for (int i
= 0; i
<nedges
; i
++)
303 struct components
*t
;
305 for (int i
= 0; i
<cs
->nnodes
; i
++)