scc

  1#include <assert.h>
  2#include <stdlib.h>
  3#include <string.h>
  4
  5#include <scc/scc.h>
  6
  7#include "cc2.h"
  8
  9struct cfg {
 10	int nr;
 11	Block *entryb, *exitb;
 12	Block *cur;
 13	Block *blocks;
 14};
 15
 16static struct cfg cfg;
 17static int modjmp;
 18
 19static Node *
 20jtarget(Node *np)
 21{
 22	return np->u.sym->u.stmt;
 23}
 24
 25static Block *
 26jtargetbb(Node *np)
 27{
 28	return jtarget(np)->bb;
 29}
 30
 31#ifndef NDEBUG
 32#include <stdio.h>
 33
 34static void
 35prbb(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->btrue) {
 47		fprintf(stderr,
 48		        "\t%d -> %d [label=\"true\"]\n",
 49		        bb->id, bb->btrue->id);
 50	}
 51	if (bb->bfalse) {
 52		fprintf(stderr,
 53		        "\t%d -> %d [label=\"false\"]\n",
 54		        bb->id, bb->bfalse->id);
 55	}
 56	prbb(bb->btrue);
 57	prbb(bb->bfalse);
 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
 82static void
 83prcfg(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
110static Block *
111newbb(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->btrue = bb->bfalse = NULL;
120	bb->id = cfg.nr++;
121	bb->visited = 0;
122	cfg.cur = bb;
123
124	return bb;
125}
126
127static Node *
128mkcfg(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->btrue = 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->btrue = laststmt->bb;
150		break;
151	case OBSWITCH:
152		cfg.cur->swtch = np->u.swtch;
153		cfg.cur->btrue = NULL;
154		break;
155	case OBRANCH:
156		cfg.cur->bfalse = np->next->bb;
157	case OJMP:
158		cfg.cur->btrue = jtargetbb(np);
159		break;
160	}
161
162	return np;
163}
164
165static Node *
166mkbb(Node *np)
167{
168	if (np->flags & BBENTRY)
169		newbb(np);
170	np->bb = cfg.cur;
171
172	return np;
173}
174
175static void
176newentry(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
188static Node *
189markbb(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
219static void
220visit(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->btrue);
229	visit(bb->bfalse);
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
241static void
242trimcfg(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
256static void
257buildcfg(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
275static int
276negop(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
290static Node *
291skipnop(Node *np, Node *target)
292{
293	for ( ; np->op == ONOP && np != target; np = np->next)
294		;
295	return np;
296}
297
298static Node *
299optjmps_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
357static void
358optjmps(void)
359{
360	do {
361		modjmp = 0;
362		apply(optjmps_helper);
363		PRTREE("after_modjmp");
364	} while (modjmp == 1);
365}
366
367void
368gencfg(void)
369{
370	optjmps();
371	DBG("new cfg");
372	buildcfg();
373	trimcfg();
374
375	PRTREE("after_gencfg");
376}
377
378void
379cleancfg(void)
380{
381	free(cfg.blocks);
382	memset(&cfg, 0, sizeof(cfg));
383}