cfg.c - scc - simple c99 compiler
(HTM) git clone git://git.simple-cc.org/scc
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) Submodules
(DIR) README
(DIR) LICENSE
---
cfg.c (5828B)
---
1 #include <assert.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 #include <scc/scc.h>
6
7 #include "cc2.h"
8
9 struct cfg {
10 int nr;
11 Block *entryb, *exitb;
12 Block *cur;
13 Block *blocks;
14 };
15
16 static struct cfg cfg;
17 static int modjmp;
18
19 static Node *
20 jtarget(Node *np)
21 {
22 return np->u.sym->u.stmt;
23 }
24
25 static Block *
26 jtargetbb(Node *np)
27 {
28 return jtarget(np)->bb;
29 }
30
31 #ifndef NDEBUG
32 #include <stdio.h>
33
34 static void
35 prbb(Block *bb)
36 {
37 Swtch *swt;
38 Block *casebb;
39 Node **cases, **bp;
40
41 if (!bb || bb->printed)
42 return;
43
44 assert(bb->id != -1);
45 bb->printed = 1;
46 if (bb->true) {
47 fprintf(stderr,
48 "\t%d -> %d [label=\"true\"]\n",
49 bb->id, bb->true->id);
50 }
51 if (bb->false) {
52 fprintf(stderr,
53 "\t%d -> %d [label=\"false\"]\n",
54 bb->id, bb->false->id);
55 }
56 prbb(bb->true);
57 prbb(bb->false);
58
59 swt = bb->swtch;
60 if (!swt)
61 return;
62 cases = swt->cases;
63
64 for (bp = cases; bp < &cases[swt->nr]; ++bp) {
65 casebb = jtargetbb(*bp);
66 fprintf(stderr,
67 "\t%d -> %d [label=\"case %lld\"]\n",
68 bb->id,
69 casebb->id,
70 (*bp)->left->u.i);
71 prbb(casebb);
72 }
73
74 casebb = jtargetbb(swtchdefault(swt));
75 fprintf(stderr,
76 "\t%d -> %d [label=\"default\"]\n",
77 bb->id,
78 casebb->id);
79 prbb(casebb);
80 }
81
82 static void
83 prcfg(char *msg)
84 {
85 Block *bb;
86 Node *np;
87
88 fprintf(stderr, "{digraph %s_%d {\n", msg, curfun->id);
89
90 for (bb = cfg.blocks; bb < &cfg.blocks[cfg.nr]; ++bb) {
91 if (bb->id == -1)
92 continue;
93 bb->printed = 0;
94
95 fprintf(stderr, "\t%d [shape=box;label=\"", bb->id);
96 for (np = bb->entryp; np; np = np->next) {
97 prtree(np);
98 putc('\n', stderr);
99 if (np == bb->exitp)
100 break;
101 }
102 fputs("\"]\n", stderr);
103 }
104
105 prbb(cfg.entryb);
106 fputs("}}\n", stderr);
107 }
108 #endif
109
110 static Block *
111 newbb(Node *np)
112 {
113 Block *bb;
114
115 bb = &cfg.blocks[cfg.nr];
116 bb->entryp = np;
117 bb->exitp = NULL;
118 bb->swtch = NULL;
119 bb->true = bb->false = NULL;
120 bb->id = cfg.nr++;
121 bb->visited = 0;
122 cfg.cur = bb;
123
124 return bb;
125 }
126
127 static Node *
128 mkcfg(Node *np)
129 {
130 if ((np->flags & (BBENTRY|BBEXIT)) == 0)
131 return np;
132
133 if (np->flags & BBENTRY)
134 cfg.cur = np->bb;
135
136 if (np->flags & BBEXIT) {
137 cfg.cur->exitp = np;
138 cfg.cur->true = np->next->bb;
139 }
140
141 switch (np->op) {
142 case OBFUN:
143 cfg.entryb = cfg.cur;
144 break;
145 case OEFUN:
146 cfg.exitb = cfg.cur;
147 break;
148 case ORET:
149 cfg.cur->true = laststmt->bb;
150 break;
151 case OBSWITCH:
152 cfg.cur->swtch = np->u.swtch;
153 cfg.cur->true = NULL;
154 break;
155 case OBRANCH:
156 cfg.cur->false = np->next->bb;
157 case OJMP:
158 cfg.cur->true = jtargetbb(np);
159 break;
160 }
161
162 return np;
163 }
164
165 static Node *
166 mkbb(Node *np)
167 {
168 if (np->flags & BBENTRY)
169 newbb(np);
170 np->bb = cfg.cur;
171
172 return np;
173 }
174
175 static void
176 newentry(Node *np)
177 {
178 if (np->flags & BBENTRY)
179 return;
180
181 np->flags |= BBENTRY;
182 if (np->prev)
183 np->prev->flags |= BBEXIT;
184 cfg.nr++;
185 DBG("new entry point %d", cfg.nr);
186 }
187
188 static Node *
189 markbb(Node *np)
190 {
191 Swtch *swt;
192 Node **cases, **bp;
193
194 switch (np->op) {
195 case OBFUN:
196 newentry(np);
197 break;
198 case ORET:
199 newentry(laststmt);
200 newentry(np->next);
201 break;
202 case OBSWITCH:
203 np->flags |= BBEXIT;
204 swt = np->u.swtch;
205 cases = swt->cases;
206 for (bp = cases; bp < &cases[swt->nr]; ++bp)
207 newentry(jtarget((*bp)));
208 newentry(jtarget(swtchdefault(swt)));
209 break;
210 case OBRANCH:
211 case OJMP:
212 newentry(jtarget(np));
213 newentry(np->next);
214 break;
215 }
216 return np;
217 }
218
219 static void
220 visit(Block *bb)
221 {
222 Swtch *swt;
223 Node **cases, **bp, *p;
224
225 if (!bb || bb->visited)
226 return;
227 bb->visited = 1;
228 visit(bb->true);
229 visit(bb->false);
230
231 swt = bb->swtch;
232 if (!swt)
233 return;
234 cases = swt->cases;
235
236 for (bp = swt->cases; bp < &cases[swt->nr]; ++bp)
237 visit(jtargetbb(*bp));
238 visit(jtargetbb(swtchdefault(swt)));
239 }
240
241 static void
242 trimcfg(void)
243 {
244 Block *bb, *prev, *next;
245
246 visit(cfg.entryb);
247 for (bb = cfg.blocks; bb < &cfg.blocks[cfg.nr]; ++bb) {
248 if (bb->visited)
249 continue;
250 delrange(bb->entryp, bb->exitp);
251 bb->id = -1;
252 }
253 PRCFG("trimmed_cfg");
254 }
255
256 static void
257 buildcfg(void)
258 {
259 int nr;
260
261 apply(markbb);
262 PRTREE("bb_mark");
263
264 cfg.blocks = xcalloc(cfg.nr, sizeof(Block));
265 nr = cfg.nr;
266 cfg.nr = 0;
267 apply(mkbb);
268 assert(cfg.nr == nr);
269
270 PRTREE("bb_mk");
271 apply(mkcfg);
272 PRCFG("cfg");
273 }
274
275 static int
276 negop(int op)
277 {
278 switch (op) {
279 case OEQ: return ONE;
280 case ONE: return OEQ;
281 case OLT: return OGE;
282 case OGE: return OLT;
283 case OLE: return OGT;
284 case OGT: return OLE;
285 default: abort();
286 }
287 return op;
288 }
289
290 static Node *
291 skipnop(Node *np, Node *target)
292 {
293 for ( ; np->op == ONOP && np != target; np = np->next)
294 ;
295 return np;
296 }
297
298 static Node *
299 optjmps_helper(Node *np)
300 {
301 Symbol *label;
302 Node *p, *stmt, *next;
303
304 switch (np->op) {
305 case ONOP:
306 if (np->label->refcnt == 0) {
307 modjmp = 1;
308 return NULL;
309 }
310 break;
311 case OBRANCH:
312 branch:
313 label = np->u.sym;
314 stmt = label->u.stmt;
315 next = np->next;
316
317 /* avoid branch over jump */
318 if (next->op == OJMP && next->next->label == label &&
319 (!next->label || next->label->refcnt == 0)) {
320 Node *left = np->left;
321 np->u.sym = next->u.sym;
322 label->refcnt--;
323 left->op = negop(left->op);
324 delstmt(next);
325 modjmp = 1;
326 goto branch;
327 }
328 goto chain_jumps;
329 case OJMP:
330 label = np->u.sym;
331 stmt = label->u.stmt;
332
333 /* avoid jump over a set of NOPs */
334 p = skipnop(np->next, stmt);
335 if (p == stmt) {
336 label->refcnt--;
337 modjmp = 1;
338 return NULL;
339 }
340
341 chain_jumps:
342 /* avoid chain of jumps to jumps */
343 p = skipnop(stmt, NULL);
344 if (p != np && p->op == OJMP) {
345 label->refcnt--;
346 label = p->u.sym;
347 stmt = label->u.stmt;
348 np->u.sym = label;
349 modjmp = 1;
350 goto chain_jumps;
351 }
352 }
353
354 return np;
355 }
356
357 static void
358 optjmps(void)
359 {
360 do {
361 modjmp = 0;
362 apply(optjmps_helper);
363 PRTREE("after_modjmp");
364 } while (modjmp == 1);
365 }
366
367 void
368 gencfg(void)
369 {
370 optjmps();
371 DBG("new cfg");
372 buildcfg();
373 trimcfg();
374
375 PRTREE("after_gencfg");
376 }
377
378 void
379 cleancfg(void)
380 {
381 free(cfg.blocks);
382 memset(&cfg, 0, sizeof(cfg));
383 }