irgwalk.c 20.2 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * 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.
 *
 * 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.
 */

Götz Lindenmaier's avatar
Götz Lindenmaier committed
20
/**
Matthias Braun's avatar
Matthias Braun committed
21
22
23
24
25
26
27
28
 * @file
 * @brief   Functions for traversing ir graphs
 * @author  Boris Boesler, Goetz Lindenmaier, Michael Beck
 * @version $Id$
 * @summary
 *  traverse an ir graph
 *  - execute the pre function before recursion
 *  - execute the post function after recursion
Michael Beck's avatar
Michael Beck committed
29
 */
Boris Boesler's avatar
added    
Boris Boesler committed
30
#ifdef HAVE_CONFIG_H
Michael Beck's avatar
Michael Beck committed
31
# include "config.h"
Boris Boesler's avatar
added    
Boris Boesler committed
32
33
#endif

Michael Beck's avatar
Michael Beck committed
34
35
36
#ifdef HAVE_STDLIB_H
# include <stdlib.h>
#endif
37

38
#include "irnode_t.h"
39
#include "irgraph_t.h"
40
41
#include "irprog.h"
#include "irgwalk.h"
42
#include "irhooks.h"
43
#include "ircgcons.h"
44
#include "entity_t.h"
Christian Schäfer's avatar
Christian Schäfer committed
45

46
#include "error.h"
Matthias Braun's avatar
Matthias Braun committed
47
#include "pset_new.h"
48
#include "array.h"
49

Michael Beck's avatar
Michael Beck committed
50
51
52
53
/**
 * Walk over an interprocedural graph (callgraph).
 * Visits only graphs in irg_set.
 */
Matthias Braun's avatar
Matthias Braun committed
54
55
56
static void irg_walk_cg(ir_node * node, unsigned long visited,
                        pset_new_t *irg_set, irg_walk_func *pre,
                        irg_walk_func *post, void * env) {
Michael Beck's avatar
Michael Beck committed
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
	int i;
	ir_graph * rem = current_ir_graph;
	ir_node * pred;

	assert(node && node->kind == k_ir_node);
	if (get_irn_visited(node) >= visited) return;

	set_irn_visited(node, visited);

	if (pre) pre(node, env);

	pred = skip_Proj(node);
	if (get_irn_op(pred) == op_CallBegin
		|| get_irn_op(pred) == op_EndReg
		|| get_irn_op(pred) == op_EndExcept) {
			current_ir_graph = get_irn_irg(pred);
	}

	if (is_no_Block(node)) { /* not block */
		irg_walk_cg(get_nodes_block(node), visited, irg_set, pre, post, env);
	}

	if (get_irn_op(node) == op_Block) { /* block */
		for (i = get_irn_arity(node) - 1; i >= 0; --i) {
			ir_node * exec = get_irn_n(node, i);
			ir_node * pred = skip_Proj(exec);
			if ((get_irn_op(pred) != op_CallBegin
				&& get_irn_op(pred) != op_EndReg
				&& get_irn_op(pred) != op_EndExcept)
				|| pset_new_contains(irg_set, get_irn_irg(pred))) {
					irg_walk_cg(exec, visited, irg_set, pre, post, env);
			}
		}
	} else if (get_irn_op(node) == op_Filter) { /* filter */
		for (i = get_irn_arity(node) - 1; i >= 0; --i) {
			ir_node * pred = get_irn_n(node, i);
			if (get_irn_op(pred) == op_Unknown || get_irn_op(pred) == op_Bad) {
				irg_walk_cg(pred, visited, irg_set, pre, post, env);
			} else {
				ir_node * exec;
				exec = skip_Proj(get_Block_cfgpred(get_nodes_block(node), i));

				if (op_Bad == get_irn_op (exec)) {
					continue;
				}

				assert(get_irn_op(exec) == op_CallBegin
					|| get_irn_op(exec) == op_EndReg
					|| get_irn_op(exec) == op_EndExcept);
				if (pset_new_contains(irg_set, get_irn_irg(exec))) {
					current_ir_graph = get_irn_irg(exec);
					irg_walk_cg(pred, visited, irg_set, pre, post, env);
					current_ir_graph = rem;
				}
			}
		}
	} else {                      /* everything else */
		for (i = get_irn_arity(node) - 1; i >= 0; --i) {
			irg_walk_cg(get_irn_n(node, i), visited, irg_set, pre, post, env);
		}
	}

	if (post) post(node, env);

	current_ir_graph = rem;
122
123
124
}


Michael Beck's avatar
Michael Beck committed
125
126
127
/**
 * Insert all ir_graphs in irg_set, that are (transitive) reachable.
 */
Matthias Braun's avatar
Matthias Braun committed
128
static void collect_irgs(ir_node * node, pset_new_t *irg_set) {
Michael Beck's avatar
Michael Beck committed
129
130
131
132
133
134
135
136
137
138
139
	if (is_Call(node)) {
		int i;
		for (i = get_Call_n_callees(node) - 1; i >= 0; --i) {
			ir_entity * ent = get_Call_callee(node, i);
			ir_graph * irg = get_entity_irg(ent);
			if (irg && !pset_new_contains(irg_set, irg)) {
				pset_new_insert(irg_set, irg);
				irg_walk_graph(irg, (irg_walk_func *) collect_irgs, NULL, irg_set);
			}
		}
	}
140
141
}

142
143
/**
 * specialized version of irg_walk_2, called if only pre callback exists
144
145
 *
 * @return number of visited nodes
146
 */
147
static unsigned
148
irg_walk_2_pre(ir_node *node, irg_walk_func *pre, void * env) {
Michael Beck's avatar
Michael Beck committed
149
150
151
152
153
154
155
156
157
	int i;
	unsigned cnt = 1;
	ir_graph *irg = current_ir_graph;

	set_irn_visited(node, irg->visited);

	pre(node, env);

	if (node->op != op_Block) {
158
		ir_node *pred = get_irn_n(node, -1);
Michael Beck's avatar
Michael Beck committed
159
160
161
162
163
164
165
166
167
		if (pred->visited < irg->visited)
			cnt += irg_walk_2_pre(pred, pre, env);
	}
	for (i = get_irn_arity(node) - 1; i >= 0; --i) {
		ir_node *pred = get_irn_n(node, i);
		if (pred->visited < irg->visited)
			cnt += irg_walk_2_pre(pred, pre, env);
	}
	return cnt;
168
169
}

170
171
/**
 * specialized version of irg_walk_2, called if only post callback exists
172
173
 *
 * @return number of visited nodes
174
 */
175
static unsigned
176
irg_walk_2_post(ir_node *node, irg_walk_func *post, void * env) {
Michael Beck's avatar
Michael Beck committed
177
178
179
180
181
182
183
	int i;
	unsigned cnt = 1;
	ir_graph *irg = current_ir_graph;

	set_irn_visited(node, irg->visited);

	if (node->op != op_Block) {
184
		ir_node *pred = get_irn_n(node, -1);
Michael Beck's avatar
Michael Beck committed
185
186
187
188
189
190
191
192
193
194
195
196
		if (pred->visited < irg->visited)
			cnt += irg_walk_2_post(pred, post, env);
	}
	for (i = get_irn_arity(node) - 1; i >= 0; --i) {
		ir_node *pred = get_irn_n(node, i);
		if (pred->visited < irg->visited)
			cnt += irg_walk_2_post(pred, post, env);
	}

	post(node, env);

	return cnt;
197
198
}

199
200
/**
 * specialized version of irg_walk_2, called if pre and post callbacks exist
201
202
 *
 * @return number of visited nodes
203
 */
204
static unsigned
205
irg_walk_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void * env) {
Michael Beck's avatar
Michael Beck committed
206
207
208
	int i;
	unsigned cnt = 1;
	ir_graph *irg = current_ir_graph;
209

Michael Beck's avatar
Michael Beck committed
210
	set_irn_visited(node, irg->visited);
211

Michael Beck's avatar
Michael Beck committed
212
	pre(node, env);
213

Michael Beck's avatar
Michael Beck committed
214
	if (node->op != op_Block) {
215
		ir_node *pred = get_irn_n(node, -1);
Michael Beck's avatar
Michael Beck committed
216
217
218
219
220
221
222
223
		if (pred->visited < irg->visited)
			cnt += irg_walk_2_both(pred, pre, post, env);
	}
	for (i = get_irn_arity(node) - 1; i >= 0; --i) {
		ir_node *pred = get_irn_n(node, i);
		if (pred->visited < irg->visited)
			cnt += irg_walk_2_both(pred, pre, post, env);
	}
224

Michael Beck's avatar
Michael Beck committed
225
	post(node, env);
226

Michael Beck's avatar
Michael Beck committed
227
	return cnt;
228
229
}

230
231
/**
 * Intraprozedural graph walker.
232
233
 *
 * @return number of visited nodes
234
 */
235
static unsigned
236
irg_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void * env)
Christian Schäfer's avatar
Christian Schäfer committed
237
{
Michael Beck's avatar
Michael Beck committed
238
239
240
241
242
243
	if (node->visited < current_ir_graph->visited) {
		if      (!post) return irg_walk_2_pre (node, pre, env);
		else if (!pre)  return irg_walk_2_post(node, post, env);
		else            return irg_walk_2_both(node, pre, post, env);
	}
	return 0;
Christian Schäfer's avatar
Christian Schäfer committed
244
245
}

246
247
248
/* a counter */
static unsigned nodes_touched = 0;

249
250
251
/*
 * generic graph walker
 */
252
void irg_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
Christian Schäfer's avatar
Christian Schäfer committed
253
{
Michael Beck's avatar
Michael Beck committed
254
255
	assert(is_ir_node(node));

256
#ifdef INTERPROCEDURAL_VIEW
Michael Beck's avatar
Michael Beck committed
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
	if (get_interprocedural_view()) {
		pset_new_t           irg_set;
		pset_new_iterator_t  iter;
		unsigned long        visited;
		ir_graph            *irg;
		assert(get_irp_ip_view_state() == ip_view_valid);

		pset_new_init(&irg_set);
		set_interprocedural_view(0);
		pset_new_insert(&irg_set, current_ir_graph);
		irg_walk(node, (irg_walk_func *) collect_irgs, NULL, &irg_set);
		set_interprocedural_view(1);
		visited = get_max_irg_visited() + 1;

		foreach_pset_new(&irg_set, irg, iter) {
			set_irg_visited(irg, visited);
		}
		irg_walk_cg(node, visited, &irg_set, pre, post, env);
		pset_new_destroy(&irg_set);
	} else {
277
#endif
278
		set_using_irn_visited(current_ir_graph);
Michael Beck's avatar
Michael Beck committed
279
280
		inc_irg_visited(current_ir_graph);
		nodes_touched = irg_walk_2(node, pre, post, env);
281
		clear_using_irn_visited(current_ir_graph);
282
#ifdef INTERPROCEDURAL_VIEW
Michael Beck's avatar
Michael Beck committed
283
	}
284
#endif
Michael Beck's avatar
Michael Beck committed
285
	return;
Christian Schäfer's avatar
Christian Schäfer committed
286
287
}

Michael Beck's avatar
Michael Beck committed
288
289
290
/*
 * walk over a graph
 */
291
void irg_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env) {
Michael Beck's avatar
Michael Beck committed
292
	ir_graph * rem = current_ir_graph;
Michael Beck's avatar
Michael Beck committed
293

Michael Beck's avatar
Michael Beck committed
294
295
296
297
298
	hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
	current_ir_graph = irg;
	irg_walk(get_irg_end(irg), pre, post, env);
	irg->estimated_node_count = nodes_touched;
	current_ir_graph = rem;
299
300
}

301
302
303
/* Executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
   Sets current_ir_graph properly for each walk.  Conserves current
   current_ir_graph. */
304
void all_irg_walk(irg_walk_func *pre, irg_walk_func *post, void *env) {
Michael Beck's avatar
Michael Beck committed
305
306
	int i, n;
	ir_graph *irg;
307

Michael Beck's avatar
Michael Beck committed
308
309
310
311
	for (i = 0, n = get_irp_n_irgs(); i < n; i++) {
		irg = get_irp_irg(i);
		irg_walk_graph(irg, pre, post, env);
	}
312
313
}

314
315
/***************************************************************************/

316
317
318
319
320
321
322
/**
 * specialized version of irg_walk_in_or_dep_2, called if only pre callback exists
 *
 * @return number of visited nodes
 */
static unsigned
irg_walk_in_or_dep_2_pre(ir_node *node, irg_walk_func *pre, void *env) {
Michael Beck's avatar
Michael Beck committed
323
324
325
326
327
328
329
330
331
	int i;
	unsigned cnt = 1;
	ir_graph *irg = current_ir_graph;

	set_irn_visited(node, irg->visited);

	pre(node, env);

	if (node->op != op_Block) {
332
		ir_node *pred = get_irn_n(node, -1);
Michael Beck's avatar
Michael Beck committed
333
334
335
336
337
338
339
340
341
		if (pred->visited < irg->visited)
			cnt += irg_walk_in_or_dep_2_pre(pred, pre, env);
	}
	for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
		ir_node *pred = get_irn_in_or_dep(node, i);
		if (pred->visited < irg->visited)
			cnt += irg_walk_in_or_dep_2_pre(pred, pre, env);
	}
	return cnt;
342
343
344
345
346
347
348
349
350
}

/**
 * specialized version of irg_walk_in_or_dep_2, called if only post callback exists
 *
 * @return number of visited nodes
 */
static unsigned
irg_walk_in_or_dep_2_post(ir_node *node, irg_walk_func *post, void *env) {
Michael Beck's avatar
Michael Beck committed
351
352
353
354
355
356
357
	int i;
	unsigned cnt = 1;
	ir_graph *irg = current_ir_graph;

	set_irn_visited(node, irg->visited);

	if (node->op != op_Block) {
358
		ir_node *pred = get_irn_n(node, -1);
Michael Beck's avatar
Michael Beck committed
359
360
361
362
363
364
365
366
367
368
369
370
		if (pred->visited < irg->visited)
			cnt += irg_walk_in_or_dep_2_post(pred, post, env);
	}
	for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
		ir_node *pred = get_irn_in_or_dep(node, i);
		if (pred->visited < irg->visited)
			cnt += irg_walk_in_or_dep_2_post(pred, post, env);
	}

	post(node, env);

	return cnt;
371
372
373
374
375
376
377
378
379
}

/**
 * specialized version of irg_walk_in_or_dep_2, called if pre and post callbacks exist
 *
 * @return number of visited nodes
 */
static unsigned
irg_walk_in_or_dep_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env) {
Michael Beck's avatar
Michael Beck committed
380
381
382
	int i;
	unsigned cnt = 1;
	ir_graph *irg = current_ir_graph;
383

Michael Beck's avatar
Michael Beck committed
384
	set_irn_visited(node, irg->visited);
385

Michael Beck's avatar
Michael Beck committed
386
	pre(node, env);
387

Michael Beck's avatar
Michael Beck committed
388
	if (node->op != op_Block) {
389
		ir_node *pred = get_irn_n(node, -1);
Michael Beck's avatar
Michael Beck committed
390
391
392
393
394
395
396
397
		if (pred->visited < irg->visited)
			cnt += irg_walk_in_or_dep_2_both(pred, pre, post, env);
	}
	for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
		ir_node *pred = get_irn_in_or_dep(node, i);
		if (pred->visited < irg->visited)
			cnt += irg_walk_in_or_dep_2_both(pred, pre, post, env);
	}
398

Michael Beck's avatar
Michael Beck committed
399
	post(node, env);
400

Michael Beck's avatar
Michael Beck committed
401
	return cnt;
402
403
404
405
406
407
408
409
410
411
}

/**
 * Intraprozedural graph walker. Follows dependency edges as well.
 *
 * @return number of visited nodes
 */
static unsigned
irg_walk_in_or_dep_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
{
Michael Beck's avatar
Michael Beck committed
412
413
414
415
416
417
	if (node->visited < current_ir_graph->visited) {
		if      (! post) return irg_walk_in_or_dep_2_pre (node, pre, env);
		else if (! pre)  return irg_walk_in_or_dep_2_post(node, post, env);
		else             return irg_walk_in_or_dep_2_both(node, pre, post, env);
	}
	return 0;
418
419
420
421
422
423
424
}

/*
 * Generic graph walker. Follows dependency edges as well.
 */
void irg_walk_in_or_dep(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
{
Michael Beck's avatar
Michael Beck committed
425
426
427
428
429
	assert(is_ir_node(node));

	if (get_interprocedural_view()) {
		assert(0 && "This is not yet implemented.");
	} else {
430
		set_using_irn_visited(current_ir_graph);
Michael Beck's avatar
Michael Beck committed
431
432
		inc_irg_visited(current_ir_graph);
		nodes_touched = irg_walk_in_or_dep_2(node, pre, post, env);
433
		clear_using_irn_visited(current_ir_graph);
Michael Beck's avatar
Michael Beck committed
434
435
	}
	return;
436
437
438
439
440
441
}

/*
 * Walk over a graph. Follow all edges (including dependencies)
 */
void irg_walk_in_or_dep_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env) {
Michael Beck's avatar
Michael Beck committed
442
	ir_graph * rem = current_ir_graph;
443

Michael Beck's avatar
Michael Beck committed
444
445
446
447
448
	hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
	current_ir_graph = irg;
	irg_walk_in_or_dep(get_irg_end(irg), pre, post, env);
	irg->estimated_node_count = nodes_touched;
	current_ir_graph = rem;
449
450
451
452
}

/***************************************************************************/

453
454
455
456
/**
 * Returns current_ir_graph and sets it to the irg of predecessor index
 * of node n.
 */
457
static INLINE ir_graph *
Michael Beck's avatar
Michael Beck committed
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
switch_irg(ir_node *n, int index) {
	ir_graph *old_current = current_ir_graph;

	if (get_interprocedural_view()) {
		/* Only Filter and Block nodes can have predecessors in other graphs. */
		if (get_irn_op(n) == op_Filter)
			n = get_nodes_block(n);
		if (get_irn_op(n) == op_Block) {
			ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index));
			if (is_ip_cfop(cfop)) {
				current_ir_graph = get_irn_irg(cfop);
			}
		}
	}

	return old_current;
474
475
}

476
477
static void
cg_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void * env)
478
{
Michael Beck's avatar
Michael Beck committed
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
	int i;
	ir_graph *rem = NULL;
	assert(node);

	if (get_irn_visited(node) < get_irg_visited(current_ir_graph)) {
		set_irn_visited(node, get_irg_visited(current_ir_graph));

		if (pre) pre(node, env);

		if (is_no_Block(node))
			cg_walk_2(get_nodes_block(node), pre, post, env);
		for (i = get_irn_arity(node) - 1; i >= 0; --i) {
			rem = switch_irg(node, i);  /* @@@ AS: Is this wrong? We do have to
						    switch to the irg of the predecessor, don't we? */
			cg_walk_2(get_irn_n(node, i), pre, post, env);
			current_ir_graph = rem;
		}

		if (post) post(node, env);
	}
	return;
500
501
}

502
#ifdef INTERPROCEDURAL_VIEW
503
/* Walks all irgs in interprocedural view.  Visits each node only once. */
504
void cg_walk(irg_walk_func *pre, irg_walk_func *post, void *env) {
Michael Beck's avatar
Michael Beck committed
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
	int i;
	ir_graph *rem = current_ir_graph;
	int rem_view = get_interprocedural_view();

	set_interprocedural_view(1);

	inc_max_irg_visited();
	/* Fix all irg_visited flags */
	for (i = 0; i < get_irp_n_irgs(); i++)
		set_irg_visited(get_irp_irg(i), get_max_irg_visited());

	/* Walk starting at unreachable procedures. Only these
	 * have End blocks visible in interprocedural view. */
	for (i = 0; i < get_irp_n_irgs(); i++) {
		ir_node *sb;
		current_ir_graph = get_irp_irg(i);

		sb = get_irg_start_block(current_ir_graph);

		if ((get_Block_n_cfgpreds(sb) > 1) ||
			(get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;

		cg_walk_2(get_irg_end(current_ir_graph), pre, post, env);
	}

	/* Check whether we walked all procedures: there could be procedures
	   with cyclic calls but no call from the outside. */
	for (i = 0; i < get_irp_n_irgs(); i++) {
		ir_node *sb;
		current_ir_graph = get_irp_irg(i);

		/* Test start block: if inner procedure end and end block are not
		* visible and therefore not marked. */
		sb = get_irg_start_block(current_ir_graph);
		if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) {
			cg_walk_2(sb, pre, post, env);
		}
	}

	/* Walk all endless loops in inner procedures.
	 * We recognize an inner procedure if the End node is not visited. */
	for (i = 0; i < get_irp_n_irgs(); i++) {
		ir_node *e;
		current_ir_graph = get_irp_irg(i);
		e = get_irg_end(current_ir_graph);
		if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
			int j;
			/* Don't visit the End node. */
			for (j = 0; j < get_End_n_keepalives(e); j++)
				cg_walk_2(get_End_keepalive(e, j), pre, post, env);
		}
	}

	set_interprocedural_view(rem_view);
	current_ir_graph = rem;
560
}
561
#endif
562
563


564
565
/***************************************************************************/

566
/* Walks back from n until it finds a real cf op. */
567
static ir_node *get_cf_op(ir_node *n) {
568
569
570
571
572
573
	while (!is_cfop(n) && !is_fragile_op(n) && !is_Bad(n)) {
		n = skip_Id(n);
		n = skip_Tuple(n);
		n = skip_Proj(n);
	}
	return n;
574
575
}

576
static void irg_block_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
Christian Schäfer's avatar
Christian Schäfer committed
577
{
Michael Beck's avatar
Michael Beck committed
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
	int i;

	if (Block_not_block_visited(node)) {
		mark_Block_block_visited(node);

		if(pre) pre(node, env);

		for(i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
			/* find the corresponding predecessor block. */
			ir_node *pred = get_cf_op(get_Block_cfgpred(node, i));
			pred = get_nodes_block(pred);
			if(get_irn_opcode(pred) == iro_Block) {
				/* recursion */
				irg_block_walk_2(pred, pre, post, env);
			}
			else {
				assert(get_irn_opcode(pred) == iro_Bad);
			}
		}

		if(post) post(node, env);
	}
Christian Schäfer's avatar
Christian Schäfer committed
600
601
602
603
604
}


/* walks only over Block nodes in the graph.  Has it's own visited
   flag, so that it can be interleaved with the other walker.         */
605
void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
Christian Schäfer's avatar
Christian Schäfer committed
606
{
Michael Beck's avatar
Michael Beck committed
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
	ir_node *block, *pred;
	int i;

	hook_irg_block_walk(current_ir_graph, node, (generic_func *)pre, (generic_func *)post);

	assert(node);
	assert(!get_interprocedural_view());   /* interprocedural_view not implemented, because it
					       * interleaves with irg_walk */
	set_using_block_visited(current_ir_graph);
	inc_irg_block_visited(current_ir_graph);
	block = is_Block(node) ? node : get_nodes_block(node);
	assert(get_irn_op(block) == op_Block);
	irg_block_walk_2(block, pre, post, env);

	/* keepalive: the endless loops ... */
	if (get_irn_op(node) == op_End) {
		int arity = get_irn_arity(node);
		for (i = 0; i < arity; i++) {
			pred = get_irn_n(node, i);
			if (get_irn_op(pred) == op_Block)
				irg_block_walk_2(pred, pre, post, env);
		}
		/* Sometimes the blocks died, but are still reachable through Phis.
		* Make sure the algorithms that try to remove these reach them. */
		for (i = 0; i < arity; i++) {
			pred = get_irn_n(node, i);
			if (get_irn_op(pred) == op_Phi) {
				ir_node *block = get_nodes_block(pred);

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

	clear_using_block_visited(current_ir_graph);
Christian Schäfer's avatar
Christian Schäfer committed
643
}
644

Michael Beck's avatar
Michael Beck committed
645
646
647
/*
 * walk over a graph block wise
 */
648
void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre,
649
              irg_walk_func *post, void *env) {
Michael Beck's avatar
Michael Beck committed
650
651
652
653
	ir_graph * rem = current_ir_graph;
	current_ir_graph = irg;
	irg_block_walk(get_irg_end(irg), pre, post, env);
	current_ir_graph = rem;
654
}
655

656
657
658
659
/*
 * Additionally walk over all anchors. Do NOT increase the visit flag.
 */
void irg_walk_anchors(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env) {
Michael Beck's avatar
Michael Beck committed
660
661
	ir_graph * rem = current_ir_graph;
	current_ir_graph = irg;
662

663
664
	inc_irg_visited(irg);
	irg_walk_2(irg->anchor, pre, post, env);
665

Michael Beck's avatar
Michael Beck committed
666
	current_ir_graph = rem;
667
668
}

669
670
671
/********************************************************************/

typedef struct walk_env {
Michael Beck's avatar
Michael Beck committed
672
673
674
	irg_walk_func *pre;
	irg_walk_func *post;
	void *env;
675
676
} walk_env;

677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
static void walk_initializer(ir_initializer_t *initializer, walk_env *env)
{
	switch(initializer->kind) {
    case IR_INITIALIZER_CONST:
    	irg_walk(initializer->consti.value, env->pre, env->post, env->env);
        return;
    case IR_INITIALIZER_TARVAL:
    case IR_INITIALIZER_NULL:
        return;

    case IR_INITIALIZER_COMPOUND: {
        size_t i;
        for(i = 0; i < initializer->compound.n_initializers; ++i) {
            ir_initializer_t *subinitializer
                = initializer->compound.initializers[i];
            walk_initializer(subinitializer, env);
        }
        return;
    }
	}
	panic("invalid initializer found");
}

Michael Beck's avatar
Michael Beck committed
700
701
702
/**
 * Walk to all constant expressions in this entity.
 */
703
static void walk_entity(ir_entity *ent, void *env)
704
{
Michael Beck's avatar
Michael Beck committed
705
706
707
	walk_env *my_env = (walk_env *)env;

	if (get_entity_variability(ent) != variability_uninitialized) {
708
709
710
		if (ent->has_initializer) {
			walk_initializer(ent->attr.initializer, my_env);
		} else if (is_atomic_entity(ent)) {
Michael Beck's avatar
Michael Beck committed
711
712
713
714
715
716
717
718
			irg_walk(get_atomic_ent_value(ent), my_env->pre, my_env->post, my_env->env);
		} else {
			int i, n_vals = get_compound_ent_n_values(ent);

			for (i = 0; i < n_vals; i++)
				irg_walk(get_compound_ent_value(ent, i), my_env->pre, my_env->post, my_env->env);
		}
	}
719
}
720

721
/* Walks over all code in const_code_irg. */
722
void walk_const_code(irg_walk_func *pre, irg_walk_func *post, void *env) {
723
	int i, j, n_types;
Michael Beck's avatar
Michael Beck committed
724
725
726
727
728
729
730
731
732
733
734
735
	walk_env my_env;

	ir_graph *rem = current_ir_graph;
	current_ir_graph = get_const_code_irg();
	inc_irg_visited(current_ir_graph);

	my_env.pre = pre;
	my_env.post = post;
	my_env.env = env;

	/* Walk all types that can contain constant entities.  */
	walk_types_entities(get_glob_type(), &walk_entity, &my_env);
736
737
	n_types = get_irp_n_types();
	for (i = 0; i < n_types; i++)
Michael Beck's avatar
Michael Beck committed
738
739
740
741
742
		walk_types_entities(get_irp_type(i), &walk_entity, &my_env);
	for (i = 0; i < get_irp_n_irgs(); i++)
		walk_types_entities(get_irg_frame_type(get_irp_irg(i)), &walk_entity, &my_env);

	/* Walk constant array bounds. */
743
	for (i = 0; i < n_types; i++) {
Michael Beck's avatar
Michael Beck committed
744
745
		ir_type *tp = get_irp_type(i);
		if (is_Array_type(tp)) {
746
747
			int n_dim = get_array_n_dimensions(tp);
			for (j = 0; j < n_dim; j++) {
Michael Beck's avatar
Michael Beck committed
748
749
750
751
752
753
754
755
756
				ir_node *n = get_array_lower_bound(tp, j);
				if (n) irg_walk(n, pre, post, env);
				n = get_array_upper_bound(tp, j);
				if (n) irg_walk(n, pre, post, env);
			}
		}
	}

	current_ir_graph = rem;
757
}