irextbb.c 11.3 KB
Newer Older
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Matthias Braun's avatar
Matthias Braun committed
3
4
 *
 * This file is part of libFirm.
5
 *
Matthias Braun's avatar
Matthias Braun committed
6
7
8
9
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
10
 *
Matthias Braun's avatar
Matthias Braun committed
11
12
13
14
15
16
17
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
18
 */
19

Matthias Braun's avatar
Matthias Braun committed
20
21
22
23
24
25
26
/**
 * @file
 * @brief    Extended basis block support.
 * @author   Michael Beck
 * @date     5.2005
 * @version  $Id$
 */
Matthias Braun's avatar
Matthias Braun committed
27
#include "config.h"
28

29
30
31
#include "irextbb_t.h"
#include "irgwalk.h"
#include "irnode_t.h"
32
#include "irgraph_t.h"
Michael Beck's avatar
Michael Beck committed
33
34
#include "iredges_t.h"
#include "irouts.h"
35
36
37
#include "xmalloc.h"
#include "irprintf.h"

Michael Beck's avatar
Michael Beck committed
38
39
40
/**
 * Environment for extbb construction.
 */
41
typedef struct env {
Michael Beck's avatar
Michael Beck committed
42
43
44
	struct obstack *obst;   /**< the obstack where allocations took place */
	ir_extblk *head;        /**< head of the list of all extended blocks */
	ir_node *start_block;   /**< the start block of the current graph */
45
46
} env_t;

47
48
int (is_ir_extbb)(const void *thing)
{
Michael Beck's avatar
Michael Beck committed
49
	return _is_ir_extbb(thing);
Michael Beck's avatar
Michael Beck committed
50
51
}

52
53
54
/**
 * allocate a new extended block header.
 */
55
56
static void allocate_extblk(ir_node *block, env_t *env)
{
57
	ir_extblk *extblk = OALLOC(env->obst, ir_extblk);
58

Michael Beck's avatar
Michael Beck committed
59
60
61
62
63
	extblk->kind    = k_ir_extblk;
	extblk->visited = 1;
	extblk->blks    = (ir_node **)env->head;
	extblk->link    = block;
	env->head       = extblk;
64

Michael Beck's avatar
Michael Beck committed
65
66
	set_Block_extbb(block, extblk);
	set_irn_link(block, NULL);
67
68
}

Michael Beck's avatar
Michael Beck committed
69
70
71
72
/**
 * Returns the number of block successors.
 * we are interested only in 1, 2 and >2.
 */
73
74
static int get_block_n_succs(ir_node *block)
{
Michael Beck's avatar
Michael Beck committed
75
76
77
78
79
80
81
82
83
84
85
86
87
	if (edges_activated(current_ir_graph)) {
		const ir_edge_t *edge;

		edge = get_block_succ_first(block);
		if (! edge)
			return 0;
		edge = get_block_succ_next(block, edge);
		if (! edge)
			return 1;
		edge = get_block_succ_next(block, edge);
		return edge ? 3 : 2;
	}
	return get_Block_n_cfg_outs(block);
Michael Beck's avatar
Michael Beck committed
88
}
89
90
91
92

/**
 * Pre block-walker. Calculates the extended block info.
 */
93
94
static void pre_walk_calc_extbb(ir_node *block, void *ctx)
{
Michael Beck's avatar
Michael Beck committed
95
	int n = get_Block_n_cfgpreds(block);
96
	env_t *env = (env_t*) ctx;
Michael Beck's avatar
Michael Beck committed
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

	if (n <= 0 || n > 1 || block == env->start_block) {
		/*
		 * block is a JOIN-node ie the control flow from
		 * many other blocks joins here. block is a leader.
		 * Note that we handle unreachable blocks (n <= 0) here too.
		 */
		allocate_extblk(block, env);
	}
	else {    /* we have only one control flow predecessor */
		ir_node *add_to = get_Block_cfgpred_block(block, 0);

		/* blocks with only one BAD predecessors are leaders too */
		if (is_Bad(add_to)) {
			allocate_extblk(block, env);
		} else {
			/*
			 * Only one control flow predecessor. This block belongs
			 * to the same extended basic block as its predecessor.
			 */
			ir_node *cf_op = skip_Proj(get_Block_cfgpred(block, 0));

119
			if (!irn_visited_else_mark(cf_op)) {
Michael Beck's avatar
Michael Beck committed
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
				ir_node *pred_bl = get_nodes_block(cf_op);
				if (get_block_n_succs(pred_bl) > 2) {
					/* More than two successors means we have a jump table.
					 * we cannot include a jump target into the current extended
					 * basic block, so create a new one here.
					 */
					allocate_extblk(block, env);
				} else {
					/* either the previous block has only one successor or
					 * this is the first successor after an if, include it.
					 */
					set_Block_extbb(block, NULL);
				}
			} else {
				/* already marked, so begin a new extended block here */
				allocate_extblk(block, env);
			}
		}
	}
139
140
}

Michael Beck's avatar
Michael Beck committed
141
/** A special extended block used as sentinel */
Matthias Braun's avatar
Matthias Braun committed
142
static ir_extblk _sentinel = { k_ir_extblk, 0xFEA1DEAD, NULL, NULL };
143

144
145
146
147
148
/**
 * Post block-walker. Calculates the extended block info.
 * During construction, we use the (free) block input of all basic blocks
 * to point to there previous block.
 */
149
static void post_walk_calc_extbb(ir_node *block, void *ctx)
150
{
Michael Beck's avatar
Michael Beck committed
151
	ir_extblk *extbb = get_Block_extbb(block);
152
	env_t *env = (env_t*) ctx;
Michael Beck's avatar
Michael Beck committed
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
	ir_extblk *sentinel = &_sentinel;

	if (! extbb) {
		ir_node *curr, *prev, *list;

		/*
		 * Search the leader. It can happen, that we fall into an endless
		 * loop, because we enter an unreachable loop that is not yet detected.
		 * We break the loop using a sentinel.
		 */
		for (curr = block; !extbb; curr = prev) {
			prev = get_Block_cfgpred_block(curr, 0);
			extbb = get_Block_extbb(prev);
			set_Block_extbb(curr, sentinel);
		}

		if (extbb == sentinel) {
			/* We detect a dead loop. We fix this by allocating a
			 * special Extended block
			 */
			ir_printf("Dead loop detected starting with %+F::%+F\n", get_irg_entity(current_ir_graph), block);

			allocate_extblk(block, env);
			extbb = get_Block_extbb(block);
			set_Block_extbb(block, sentinel);
		}

		/* replace all sentinels by the extbb info */
		prev = block;
		list = NULL;
183
		for (;;) {
Michael Beck's avatar
Michael Beck committed
184
185
186
187
188
189
190
191
			if (get_Block_extbb(prev) != sentinel)
				break;
			set_irn_link(prev, list);
			list = prev;
			prev = get_Block_cfgpred_block(prev, 0);
		}
		/* arg, the list is in wrong order, turn around and add to the extbb list */
		for (curr = list; curr; curr = prev) {
192
			prev = (ir_node*) get_irn_link(curr);
Michael Beck's avatar
Michael Beck committed
193
194
195
196
197
198
			set_irn_link(curr, extbb->link);
			extbb->link = curr;
			set_Block_extbb(curr, extbb);
			++extbb->visited;
		}
	}
199
200
201
202
203
}

/*
 * Compute the extended basic blocks for a graph
 */
204
205
void compute_extbb(ir_graph *irg)
{
Michael Beck's avatar
Michael Beck committed
206
207
208
209
210
211
	env_t env;
	ir_extblk *extbb, *next;

	if (irg->extbb_obst)
		obstack_free(irg->extbb_obst, NULL);
	else
212
		irg->extbb_obst = XMALLOC(struct obstack);
Michael Beck's avatar
Michael Beck committed
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
	obstack_init(irg->extbb_obst);

	env.obst        = irg->extbb_obst;
	env.head        = NULL;
	env.start_block = get_irg_start_block(irg);

	if (! edges_activated(irg)) {
		/* we don't have edges */
		assure_irg_outs(irg);
	}

	/* we must mark nodes, so increase the visited flag */
	inc_irg_visited(irg);
	irg_block_walk_graph(irg, pre_walk_calc_extbb, post_walk_calc_extbb, &env);

	/*
	 * Ok, we have now the list of all extended blocks starting with env.head
	 * every extended block "knowns" the number of blocks in visited and
	 * the blocks are linked in link.
	 * Now we can create arrays that hold the blocks, some kind of "out" edges
	 * for the extended block
	 */
	for (extbb = env.head; extbb; extbb = next) {
		int i, len = (int)extbb->visited;
		ir_node *block;

		next = (ir_extblk *)extbb->blks;

		extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);

243
244
		for (block = (ir_node*) extbb->link, i = 0; i < len; ++i) {
			ir_node *nblock = (ir_node*) get_irn_link(block);
Michael Beck's avatar
Michael Beck committed
245
246
247
248
249
250

			/* ensure that the leader is the first one */
			extbb->blks[len - 1 - i] = block;
			set_irn_link(block, NULL);
			block = nblock;
		}
251

252
#ifndef NDEBUG
Michael Beck's avatar
Michael Beck committed
253
254
255
256
257
258
259
260
261
262
		/* check it */
		for (i = len - 1; i > 0; --i) {
			ir_node *blk = extbb->blks[i];

			if (get_Block_n_cfgpreds(blk) != 1) {
				assert(!"Block for more than one predecessors is no leader");
			} else if (get_Block_cfgpred_block(blk, 0) != extbb->blks[i - 1]) {
				assert(!"extbb block order wrong");
			}
		}
Michael Beck's avatar
Michael Beck committed
263
#endif
264

Michael Beck's avatar
Michael Beck committed
265
266
267
		extbb->link    = NULL;
		extbb->visited = 0;
	}
268

269
	set_irg_state(irg, IR_GRAPH_STATE_VALID_EXTENDED_BLOCKS);
270
271
272
}

/* free all extended block info. */
273
274
void free_extbb(ir_graph *irg)
{
Michael Beck's avatar
Michael Beck committed
275
276
277
278
279
	if (irg->extbb_obst) {
		obstack_free(irg->extbb_obst, NULL);
		xfree(irg->extbb_obst);
		irg->extbb_obst = NULL;
	}
280
	clear_irg_state(irg, IR_GRAPH_STATE_VALID_EXTENDED_BLOCKS);
281
282
283
}

/* Return the extended block of a node. */
284
285
ir_extblk *get_nodes_extbb(const ir_node *node)
{
Michael Beck's avatar
Michael Beck committed
286
	const ir_node *block = is_Block(node) ? node : get_nodes_block(node);
Michael Beck's avatar
Michael Beck committed
287
	return get_Block_extbb(block);
288
289
290
}

/* Gets the visited counter of an extended block. */
291
292
ir_visited_t (get_extbb_visited)(const ir_extblk *blk)
{
Michael Beck's avatar
Michael Beck committed
293
	return _get_extbb_visited(blk);
294
295
296
}

/* Sets the visited counter of an extended block. */
297
298
void (set_extbb_visited)(ir_extblk *blk, ir_visited_t visited)
{
Michael Beck's avatar
Michael Beck committed
299
	_set_extbb_visited(blk, visited);
300
301
302
}

/* Mark an extended block as visited in a graph. */
303
304
void (mark_extbb_visited)(ir_extblk *blk)
{
Michael Beck's avatar
Michael Beck committed
305
	_mark_extbb_visited(blk);
306
307
308
}

/* Returns non-zero if an extended was visited. */
309
310
int (extbb_visited)(const ir_extblk *blk)
{
Michael Beck's avatar
Michael Beck committed
311
	return _extbb_visited(blk);
312
313
314
}

/* Returns non-zero if an extended block was NOT visited. */
315
316
int (extbb_not_visited)(const ir_extblk *blk)
{
Michael Beck's avatar
Michael Beck committed
317
	return _extbb_not_visited(blk);
318
319
320
}

/* Returns the link field of an extended block. */
321
322
void *(get_extbb_link)(const ir_extblk *blk)
{
Michael Beck's avatar
Michael Beck committed
323
	return _get_extbb_link(blk);
324
325
326
}

/* Sets the link field of an extended block. */
327
328
void (set_extbb_link)(ir_extblk *blk, void *link)
{
Michael Beck's avatar
Michael Beck committed
329
	_set_extbb_link(blk, link);
330
331
}

Michael Beck's avatar
Michael Beck committed
332
/* Return the number of basic blocks of an extended block */
333
334
int (get_extbb_n_blocks)(const ir_extblk *blk)
{
Michael Beck's avatar
Michael Beck committed
335
	return _get_extbb_n_blocks(blk);
336
337
}

Michael Beck's avatar
Michael Beck committed
338
/* Return the i'th basic block of an extended block */
339
340
ir_node *(get_extbb_block)(const ir_extblk *blk, int pos)
{
Michael Beck's avatar
Michael Beck committed
341
	return _get_extbb_block(blk, pos);
342
}
343
344

/* Return the leader basis block of an extended block. */
345
346
ir_node *(get_extbb_leader)(const ir_extblk *blk)
{
Michael Beck's avatar
Michael Beck committed
347
	return _get_extbb_leader(blk);
348
349
350
}

/* Return the node number of an extended block. */
351
352
long get_extbb_node_nr(const ir_extblk *blk)
{
Michael Beck's avatar
Michael Beck committed
353
	return get_irn_node_nr(get_extbb_leader(blk));
354
}
355

356
357
static void irg_extblock_walk_2(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env)
{
Michael Beck's avatar
Michael Beck committed
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
	int i;
	ir_node *node;

	if (extbb_not_visited(blk)) {
		mark_extbb_visited(blk);

		if (pre) pre(blk, env);

		node = get_extbb_leader(blk);
		for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
			/* find the corresponding predecessor block. */
			ir_node *pred = get_Block_cfgpred_block(node, i);
			if (is_Block(pred)) {
				/* recursion */
				irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env);
			}
			else {
				assert(is_Bad(pred));
			}
		}

		if (post) post(blk, env);
	}
381
382
}

383
/* walks only over extended Block nodes in the graph.  Has its own visited
384
   flag, so that it can be interleaved with the other walker.         */
385
386
void irg_extblock_walk(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env)
{
Michael Beck's avatar
Michael Beck committed
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
	ir_node *pred, *start_bl = get_irg_start_block(current_ir_graph);
	ir_extblk *start_blk = get_Block_extbb(start_bl);
	int i;

	assert(blk);
	inc_irg_block_visited(current_ir_graph);

	/* assure the start block is the first one */
	mark_extbb_visited(start_blk);
	if (post)
		post(start_blk, env);
	irg_extblock_walk_2(blk, pre, post, env);

	/* keepalive: the endless loops ... */
	if (blk == get_Block_extbb(get_irg_end_block(current_ir_graph))) {
		ir_node *node = get_irg_end(current_ir_graph);
		int arity = get_irn_arity(node);
		for (i = 0; i < arity; i++) {
			pred = get_irn_n(node, i);
			if (is_Block(pred))
				irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env);
			else if (is_Phi(pred)) {
				/* Sometimes the blocks died, but are still reachable through Phis.
				 * Make sure the algorithms that try to remove these reach them. */
				ir_node *block = get_nodes_block(pred);

				if (! is_Bad(block))
					irg_extblock_walk_2(get_Block_extbb(block), pre, post, env);
			}
		}
	}

	if (pre)
		pre(start_blk, env);
421
422
423
}

/* Walks only over reachable Extended Basic Block nodes in the graph. */
424
425
void irg_extblock_walk_graph(ir_graph *irg, extbb_walk_func *pre, extbb_walk_func *post, void *env)
{
Michael Beck's avatar
Michael Beck committed
426
427
428
429
430
431
	ir_node *endbl = get_irg_end_block(irg);
	ir_extblk *blk = get_Block_extbb(endbl);
	ir_graph *rem  = current_ir_graph;
	current_ir_graph = irg;
	irg_extblock_walk(blk, pre, post, env);
	current_ir_graph = rem;
432
}