irgwalk.c 10.2 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

Götz Lindenmaier's avatar
Götz Lindenmaier committed
6
/**
Matthias Braun's avatar
Matthias Braun committed
7
8
9
 * @file
 * @brief   Functions for traversing ir graphs
 * @author  Boris Boesler, Goetz Lindenmaier, Michael Beck
yb9976's avatar
yb9976 committed
10
 * @brief
Matthias Braun's avatar
Matthias Braun committed
11
12
13
 *  traverse an ir graph
 *  - execute the pre function before recursion
 *  - execute the post function after recursion
Michael Beck's avatar
Michael Beck committed
14
 */
15
#include <stdlib.h>
16

17
#include "irnode_t.h"
18
#include "irgraph_t.h"
19
20
#include "irprog.h"
#include "irgwalk.h"
21
#include "irhooks.h"
22
#include "entity_t.h"
23
#include "ircons.h"
Christian Schäfer's avatar
Christian Schäfer committed
24

25
#include "error.h"
Matthias Braun's avatar
Matthias Braun committed
26
#include "pset_new.h"
27
#include "array.h"
28

29
30
31
/**
 * specialized version of irg_walk_2, called if only pre callback exists
 */
32
static void irg_walk_2_pre(ir_node *node, irg_walk_func *pre, void *env)
33
{
34
	ir_graph *irg = get_irn_irg(node);
Michael Beck's avatar
Michael Beck committed
35
36
37
38
39

	set_irn_visited(node, irg->visited);

	pre(node, env);

40
	if (!is_Block(node)) {
41
		ir_node *pred = get_nodes_block(node);
Michael Beck's avatar
Michael Beck committed
42
		if (pred->visited < irg->visited)
43
			irg_walk_2_pre(pred, pre, env);
Michael Beck's avatar
Michael Beck committed
44
	}
45
	foreach_irn_in_r(node, i, pred) {
Michael Beck's avatar
Michael Beck committed
46
		if (pred->visited < irg->visited)
47
			irg_walk_2_pre(pred, pre, env);
Michael Beck's avatar
Michael Beck committed
48
	}
49
50
}

51
52
53
/**
 * specialized version of irg_walk_2, called if only post callback exists
 */
54
static void irg_walk_2_post(ir_node *node, irg_walk_func *post, void *env)
55
{
56
	ir_graph *irg = get_irn_irg(node);
Michael Beck's avatar
Michael Beck committed
57
58
59

	set_irn_visited(node, irg->visited);

60
	if (!is_Block(node)) {
61
		ir_node *pred = get_nodes_block(node);
Michael Beck's avatar
Michael Beck committed
62
		if (pred->visited < irg->visited)
63
			irg_walk_2_post(pred, post, env);
Michael Beck's avatar
Michael Beck committed
64
	}
65
	foreach_irn_in_r(node, i, pred) {
Michael Beck's avatar
Michael Beck committed
66
		if (pred->visited < irg->visited)
67
			irg_walk_2_post(pred, post, env);
Michael Beck's avatar
Michael Beck committed
68
69
70
	}

	post(node, env);
71
72
}

73
74
75
/**
 * specialized version of irg_walk_2, called if pre and post callbacks exist
 */
76
static void irg_walk_2_both(ir_node *node, irg_walk_func *pre,
77
                                irg_walk_func *post, void *env)
78
{
79
	ir_graph *irg = get_irn_irg(node);
80

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

Michael Beck's avatar
Michael Beck committed
83
	pre(node, env);
84

85
	if (!is_Block(node)) {
86
		ir_node *pred = get_nodes_block(node);
Michael Beck's avatar
Michael Beck committed
87
		if (pred->visited < irg->visited)
88
			irg_walk_2_both(pred, pre, post, env);
Michael Beck's avatar
Michael Beck committed
89
	}
90
	foreach_irn_in_r(node, i, pred) {
Michael Beck's avatar
Michael Beck committed
91
		if (pred->visited < irg->visited)
92
			irg_walk_2_both(pred, pre, post, env);
Michael Beck's avatar
Michael Beck committed
93
	}
94

Michael Beck's avatar
Michael Beck committed
95
	post(node, env);
96
97
}

98
99
void 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
100
{
101
	if (irn_visited(node))
102
		return;
103

104
105
106
	if      (!post) irg_walk_2_pre (node, pre, env);
	else if (!pre)  irg_walk_2_post(node, post, env);
	else            irg_walk_2_both(node, pre, post, env);
Christian Schäfer's avatar
Christian Schäfer committed
107
108
}

109
110
void irg_walk_core(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
                   void *env)
Christian Schäfer's avatar
Christian Schäfer committed
111
{
Michael Beck's avatar
Michael Beck committed
112
	assert(is_ir_node(node));
113
	irg_walk_2(node, pre, post, env);
Christian Schäfer's avatar
Christian Schäfer committed
114
115
}

116
117
118
void irg_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
              void *env)
{
119
120
121
122
123
124
	ir_graph *irg = get_irn_irg(node);
	ir_graph *rem = current_ir_graph;

	current_ir_graph = irg;
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
	inc_irg_visited(irg);
125
	irg_walk_core(node, pre, post, env);
126
127
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
	current_ir_graph = rem;
128
129
}

130
131
void irg_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
{
Michael Beck's avatar
Michael Beck committed
132
	ir_graph * rem = current_ir_graph;
Michael Beck's avatar
Michael Beck committed
133

Michael Beck's avatar
Michael Beck committed
134
135
136
137
	hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
	current_ir_graph = irg;
	irg_walk(get_irg_end(irg), pre, post, env);
	current_ir_graph = rem;
138
139
}

140
141
void all_irg_walk(irg_walk_func *pre, irg_walk_func *post, void *env)
{
Michael Beck's avatar
Michael Beck committed
142
	size_t i, n;
Michael Beck's avatar
Michael Beck committed
143
	ir_graph *irg;
144

Michael Beck's avatar
Michael Beck committed
145
146
147
148
	for (i = 0, n = get_irp_n_irgs(); i < n; i++) {
		irg = get_irp_irg(i);
		irg_walk_graph(irg, pre, post, env);
	}
149
150
}

151
152
153
/**
 * specialized version of irg_walk_in_or_dep_2, called if only pre callback exists
 */
154
static void irg_walk_in_or_dep_2_pre(ir_node *node, irg_walk_func *pre, void *env)
155
{
Michael Beck's avatar
Michael Beck committed
156
	int i;
157
	ir_graph *irg = get_irn_irg(node);
Michael Beck's avatar
Michael Beck committed
158
159
160
161
162

	set_irn_visited(node, irg->visited);

	pre(node, env);

163
	if (!is_Block(node)) {
164
		ir_node *pred = get_nodes_block(node);
Michael Beck's avatar
Michael Beck committed
165
		if (pred->visited < irg->visited)
166
			irg_walk_in_or_dep_2_pre(pred, pre, env);
Michael Beck's avatar
Michael Beck committed
167
168
169
170
	}
	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)
171
			irg_walk_in_or_dep_2_pre(pred, pre, env);
Michael Beck's avatar
Michael Beck committed
172
	}
173
174
175
176
177
}

/**
 * specialized version of irg_walk_in_or_dep_2, called if only post callback exists
 */
178
static void irg_walk_in_or_dep_2_post(ir_node *node, irg_walk_func *post, void *env)
179
{
Michael Beck's avatar
Michael Beck committed
180
	int i;
181
	ir_graph *irg = get_irn_irg(node);
Michael Beck's avatar
Michael Beck committed
182
183
184

	set_irn_visited(node, irg->visited);

185
	if (!is_Block(node)) {
186
		ir_node *pred = get_nodes_block(node);
Michael Beck's avatar
Michael Beck committed
187
		if (pred->visited < irg->visited)
188
			irg_walk_in_or_dep_2_post(pred, post, env);
Michael Beck's avatar
Michael Beck committed
189
190
191
192
	}
	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)
193
			irg_walk_in_or_dep_2_post(pred, post, env);
Michael Beck's avatar
Michael Beck committed
194
195
196
	}

	post(node, env);
197
198
199
200
201
}

/**
 * specialized version of irg_walk_in_or_dep_2, called if pre and post callbacks exist
 */
202
static void irg_walk_in_or_dep_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
203
{
Michael Beck's avatar
Michael Beck committed
204
	int i;
205
	ir_graph *irg = get_irn_irg(node);
206

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

Michael Beck's avatar
Michael Beck committed
209
	pre(node, env);
210

211
	if (!is_Block(node)) {
212
		ir_node *pred = get_nodes_block(node);
Michael Beck's avatar
Michael Beck committed
213
		if (pred->visited < irg->visited)
214
			irg_walk_in_or_dep_2_both(pred, pre, post, env);
Michael Beck's avatar
Michael Beck committed
215
216
217
218
	}
	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)
219
			irg_walk_in_or_dep_2_both(pred, pre, post, env);
Michael Beck's avatar
Michael Beck committed
220
	}
221

Michael Beck's avatar
Michael Beck committed
222
	post(node, env);
223
224
225
226
227
}

/**
 * Intraprozedural graph walker. Follows dependency edges as well.
 */
228
static void irg_walk_in_or_dep_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
229
{
230
	if (irn_visited(node))
231
		return;
232

233
234
235
	if      (! post) irg_walk_in_or_dep_2_pre (node, pre, env);
	else if (! pre)  irg_walk_in_or_dep_2_post(node, post, env);
	else             irg_walk_in_or_dep_2_both(node, pre, post, env);
236
237
238
239
}

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
240
241
	assert(is_ir_node(node));

242
243
244
	ir_graph *const irg = get_irn_irg(node);
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
	inc_irg_visited(irg);
245
	irg_walk_in_or_dep_2(node, pre, post, env);
246
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
247
248
}

249
250
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
251
	ir_graph * rem = current_ir_graph;
252

Michael Beck's avatar
Michael Beck committed
253
254
255
256
	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);
	current_ir_graph = rem;
257
258
}

259
/* Walks back from n until it finds a real cf op. */
260
261
static ir_node *get_cf_op(ir_node *n)
{
262
263
264
265
266
	while (!is_cfop(n) && !is_fragile_op(n) && !is_Bad(n)) {
		n = skip_Tuple(n);
		n = skip_Proj(n);
	}
	return n;
267
268
}

269
270
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
271
{
Michael Beck's avatar
Michael Beck committed
272
273
	int i;

274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
	if (Block_block_visited(node))
		return;
	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);
Michael Beck's avatar
Michael Beck committed
290
291
		}
	}
292
293
294

	if (post)
		post(node, env);
Christian Schäfer's avatar
Christian Schäfer committed
295
296
}

297
298
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
299
{
300
301
	ir_graph *irg   = get_irn_irg(node);
	ir_node  *block = is_Block(node) ? node : get_nodes_block(node);
Michael Beck's avatar
Michael Beck committed
302

303
	hook_irg_block_walk(irg, node, (generic_func *)pre, (generic_func *)post);
Michael Beck's avatar
Michael Beck committed
304

305
306
	ir_reserve_resources(irg, IR_RESOURCE_BLOCK_VISITED);
	inc_irg_block_visited(irg);
Michael Beck's avatar
Michael Beck committed
307
308
	irg_block_walk_2(block, pre, post, env);

309
	/* Some blocks might be only reachable through keep-alive edges */
310
	if (is_End(node)) {
311
		foreach_irn_in(node, i, pred) {
312
			if (!is_Block(pred))
313
				continue;
314
			irg_block_walk_2(pred, pre, post, env);
Michael Beck's avatar
Michael Beck committed
315
316
317
		}
	}

318
	ir_free_resources(irg, IR_RESOURCE_BLOCK_VISITED);
Christian Schäfer's avatar
Christian Schäfer committed
319
}
320

321
void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre,
322
323
                          irg_walk_func *post, void *env)
{
Michael Beck's avatar
Michael Beck committed
324
325
326
327
	ir_graph * rem = current_ir_graph;
	current_ir_graph = irg;
	irg_block_walk(get_irg_end(irg), pre, post, env);
	current_ir_graph = rem;
328
}
329

330
331
void irg_walk_anchors(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
{
Matthias Braun's avatar
Matthias Braun committed
332
	irg_walk(irg->anchor, pre, post, env);
333
334
}

335
typedef struct walk_env {
Michael Beck's avatar
Michael Beck committed
336
337
338
	irg_walk_func *pre;
	irg_walk_func *post;
	void *env;
339
340
} walk_env;

341
342
static void walk_initializer(ir_initializer_t *initializer, walk_env *env)
{
343
	switch (initializer->kind) {
344
    case IR_INITIALIZER_CONST:
345
		irg_walk(initializer->consti.value, env->pre, env->post, env->env);
346
347
348
349
350
351
352
        return;
    case IR_INITIALIZER_TARVAL:
    case IR_INITIALIZER_NULL:
        return;

    case IR_INITIALIZER_COMPOUND: {
        size_t i;
353
        for (i = 0; i < initializer->compound.n_initializers; ++i) {
354
355
356
357
358
359
360
361
362
363
            ir_initializer_t *subinitializer
                = initializer->compound.initializers[i];
            walk_initializer(subinitializer, env);
        }
        return;
    }
	}
	panic("invalid initializer found");
}

Michael Beck's avatar
Michael Beck committed
364
365
366
/**
 * Walk to all constant expressions in this entity.
 */
367
static void walk_entity(ir_entity *ent, void *env)
368
{
Michael Beck's avatar
Michael Beck committed
369
370
	walk_env *my_env = (walk_env *)env;

Matthias Braun's avatar
Matthias Braun committed
371
372
	if (ent->initializer != NULL) {
		walk_initializer(ent->initializer, my_env);
Michael Beck's avatar
Michael Beck committed
373
	}
374
}
375

376
377
void walk_const_code(irg_walk_func *pre, irg_walk_func *post, void *env)
{
Michael Beck's avatar
Michael Beck committed
378
	walk_env my_env;
379
	ir_segment_t s;
Matthias Braun's avatar
Matthias Braun committed
380
381
	size_t i;
	size_t n_types;
Michael Beck's avatar
Michael Beck committed
382
383
384
385
386
387
388
389
390
391

	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.  */
392
	for (s = IR_SEGMENT_FIRST; s <= IR_SEGMENT_LAST; ++s)
393
		walk_types_entities(get_segment_type(s), &walk_entity, &my_env);
394
395
	n_types = get_irp_n_types();
	for (i = 0; i < n_types; i++)
Michael Beck's avatar
Michael Beck committed
396
397
398
399
400
		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. */
401
	for (i = 0; i < n_types; i++) {
Michael Beck's avatar
Michael Beck committed
402
403
		ir_type *tp = get_irp_type(i);
		if (is_Array_type(tp)) {
404
405
406
			ir_node *size = get_array_size(tp);
			if (size != NULL)
				irg_walk(size, pre, post, env);
Michael Beck's avatar
Michael Beck committed
407
408
409
410
		}
	}

	current_ir_graph = rem;
411
}