typewalk.c 11.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
 */

6
/**
7
 * @file
Michael Beck's avatar
Michael Beck committed
8
9
 * @brief   Functionality to modify the type graph.
 * @author  Goetz Lindenmaier
yb9976's avatar
yb9976 committed
10
 * @brief
11
12
 *
 * Traverse the type information.  The walker walks the whole ir graph
13
14
15
16
 * to find the distinct type trees in the type graph forest.
 * - execute the pre function before recursion
 * - execute the post function after recursion
 */
17
#include <stdlib.h>
Götz Lindenmaier's avatar
Götz Lindenmaier committed
18
#include <stdio.h>
Christian Schäfer's avatar
Christian Schäfer committed
19

Boris Boesler's avatar
Boris Boesler committed
20
#include "entity_t.h"
21
#include "type_t.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
22
23
24
25
26

#include "irprog_t.h"
#include "irgraph_t.h"
#include "irnode_t.h"
#include "irgwalk.h"
Matthias Braun's avatar
Matthias Braun committed
27
#include "panic.h"
28
#include "ircons.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
29

30
31
32
/**
 * The walker environment
 */
Christian Schäfer's avatar
Christian Schäfer committed
33
typedef struct type_walk_env {
Michael Beck's avatar
Michael Beck committed
34
35
36
	type_walk_func *pre;    /**< Pre-walker function */
	type_walk_func *post;   /**< Post-walker function */
	void *env;              /**< environment for walker functions */
Christian Schäfer's avatar
Christian Schäfer committed
37
38
} type_walk_env;

39
40
/* a walker for irn's */
static void irn_type_walker(
Michael Beck's avatar
Michael Beck committed
41
	ir_node *node, type_walk_func *pre, type_walk_func *post, void *env);
Christian Schäfer's avatar
Christian Schäfer committed
42

43
44
45
46
static void walk_initializer(ir_initializer_t *initializer,
                             type_walk_func *pre, type_walk_func *post,
                             void *env)
{
47
	switch (initializer->kind) {
48
49
50
51
52
53
54
55
	case IR_INITIALIZER_CONST:
		irn_type_walker(initializer->consti.value, pre, post, env);
		return;
	case IR_INITIALIZER_TARVAL:
	case IR_INITIALIZER_NULL:
		return;

	case IR_INITIALIZER_COMPOUND: {
Matthias Braun's avatar
Matthias Braun committed
56
		for (size_t i = 0; i < initializer->compound.n_initializers; ++i) {
57
58
59
60
61
62
63
64
65
66
			ir_initializer_t *subinitializer
				= initializer->compound.initializers[i];
			walk_initializer(subinitializer, pre, post, env);
		}
		return;
	}
	}
	panic("invalid initializer found");
}

67
68
69
70
/**
 * Main walker: walks over all used types/entities of a
 * type entity.
 */
Christoph Mallon's avatar
Christoph Mallon committed
71
static void do_type_walk(ir_type *const tp, ir_entity *const ent,
Michael Beck's avatar
Michael Beck committed
72
73
74
                         type_walk_func *pre,
                         type_walk_func *post,
                         void *env)
Christian Schäfer's avatar
Christian Schäfer committed
75
{
Michael Beck's avatar
Michael Beck committed
76
	/* marked? */
Christoph Mallon's avatar
Christoph Mallon committed
77
	if (ent) {
78
79
		if (entity_visited(ent))
			return;
80
		mark_entity_visited(ent);
Christoph Mallon's avatar
Christoph Mallon committed
81
	} else {
82
83
		if (type_visited(tp))
			return;
84
		mark_type_visited(tp);
Michael Beck's avatar
Michael Beck committed
85
86
87
88
	}

	/* execute pre method */
	if (pre)
Christoph Mallon's avatar
Christoph Mallon committed
89
		pre(tp, ent, env);
Michael Beck's avatar
Michael Beck committed
90
91

	/* iterate */
Christoph Mallon's avatar
Christoph Mallon committed
92
93
94
	if (ent) {
		do_type_walk(get_entity_owner(ent), NULL, pre, post, env);
		do_type_walk(get_entity_type(ent),  NULL, pre, post, env);
Michael Beck's avatar
Michael Beck committed
95

96
		switch (get_entity_kind(ent)) {
Christoph Mallon's avatar
Christoph Mallon committed
97
98
99
100
		case IR_ENTITY_ALIAS: {
			ir_entity *const e = get_entity_alias(ent);
			if (e)
				do_type_walk(NULL, e, pre, post, env);
101
			break;
Christoph Mallon's avatar
Christoph Mallon committed
102
103
		}

104
		case IR_ENTITY_NORMAL: {
105
			/* walk over the value types */
106
107
108
			ir_initializer_t *const init = get_entity_initializer(ent);
			if (init)
				walk_initializer(init, pre, post, env);
109
			break;
110
		}
111
112

		case IR_ENTITY_METHOD:
113
114
115
116
117
		case IR_ENTITY_UNKNOWN:
		case IR_ENTITY_PARAMETER:
		case IR_ENTITY_LABEL:
		case IR_ENTITY_COMPOUND_MEMBER:
			break;
Michael Beck's avatar
Michael Beck committed
118
		}
Christoph Mallon's avatar
Christoph Mallon committed
119
	} else {
Michael Beck's avatar
Michael Beck committed
120
121
		switch (get_type_tpop_code(tp)) {
		case tpo_class:
Matthias Braun's avatar
Matthias Braun committed
122
123
			for (size_t i = 0, n_types = get_class_n_supertypes(tp);
			     i < n_types; ++i) {
Christoph Mallon's avatar
Christoph Mallon committed
124
				do_type_walk(get_class_supertype(tp, i), NULL, pre, post, env);
125
			}
Matthias Braun's avatar
Matthias Braun committed
126
127
			for (size_t i = 0, n_mem = get_class_n_members(tp);
			     i < n_mem; ++i) {
Christoph Mallon's avatar
Christoph Mallon committed
128
				do_type_walk(NULL, get_class_member(tp, i), pre, post, env);
129
			}
Matthias Braun's avatar
Matthias Braun committed
130
131
			for (size_t i = 0, n_types = get_class_n_subtypes(tp);
			     i < n_types; ++i) {
Christoph Mallon's avatar
Christoph Mallon committed
132
				do_type_walk(get_class_subtype(tp, i), NULL, pre, post, env);
133
			}
Michael Beck's avatar
Michael Beck committed
134
135
136
			break;

		case tpo_struct:
Matthias Braun's avatar
Matthias Braun committed
137
138
			for (size_t i = 0, n_mem = get_struct_n_members(tp);
			     i < n_mem; ++i) {
Christoph Mallon's avatar
Christoph Mallon committed
139
				do_type_walk(NULL, get_struct_member(tp, i), pre, post, env);
140
			}
Michael Beck's avatar
Michael Beck committed
141
142
143
			break;

		case tpo_method:
Matthias Braun's avatar
Matthias Braun committed
144
145
			for (size_t i = 0, n_params = get_method_n_params(tp);
			     i < n_params; ++i) {
Christoph Mallon's avatar
Christoph Mallon committed
146
				do_type_walk(get_method_param_type(tp, i), NULL, pre, post, env);
147
			}
Matthias Braun's avatar
Matthias Braun committed
148
			for (size_t i = 0, n_res = get_method_n_ress(tp); i < n_res; ++i) {
Christoph Mallon's avatar
Christoph Mallon committed
149
				do_type_walk(get_method_res_type(tp, i), NULL, pre, post, env);
150
			}
Michael Beck's avatar
Michael Beck committed
151
152
153
			break;

		case tpo_union:
Matthias Braun's avatar
Matthias Braun committed
154
155
			for (size_t i = 0, n_members = get_union_n_members(tp);
			     i < n_members; ++i) {
Christoph Mallon's avatar
Christoph Mallon committed
156
				do_type_walk(NULL, get_union_member(tp, i), pre, post, env);
157
			}
Michael Beck's avatar
Michael Beck committed
158
159
160
			break;

		case tpo_array:
Christoph Mallon's avatar
Christoph Mallon committed
161
			do_type_walk(get_array_element_type(tp), NULL, pre, post, env);
Michael Beck's avatar
Michael Beck committed
162
163
164
			break;

		case tpo_pointer:
Christoph Mallon's avatar
Christoph Mallon committed
165
			do_type_walk(get_pointer_points_to_type(tp), NULL, pre, post, env);
Michael Beck's avatar
Michael Beck committed
166
167
			break;

168
		case tpo_code:
Michael Beck's avatar
Michael Beck committed
169
170
171
172
		case tpo_primitive:
		case tpo_unknown:
			/* a leave. */
			break;
173
		case tpo_uninitialized:
174
			panic("faulty type");
Michael Beck's avatar
Michael Beck committed
175
176
177
178
179
		}
	}

	/* execute post method */
	if (post)
Christoph Mallon's avatar
Christoph Mallon committed
180
		post(tp, ent, env);
Christian Schäfer's avatar
Christian Schäfer committed
181
182
}

183
/**  Check whether node contains types or entities as an attribute.
184
     If so start a walk over that information. */
Matthias Braun's avatar
Matthias Braun committed
185
186
static void irn_type_walker(ir_node *node, type_walk_func *pre,
                            type_walk_func *post, void *env)
187
{
Christoph Mallon's avatar
Christoph Mallon committed
188
189
190
191
192
193
	ir_entity *const ent = get_irn_entity_attr(node);
	if (ent)
		do_type_walk(NULL, ent, pre, post, env);
	ir_type *const typ = get_irn_type_attr(node);
	if (typ)
		do_type_walk(typ, NULL, pre, post, env);
Christian Schäfer's avatar
Christian Schäfer committed
194
195
}

196
197
/**  Check whether node contains types or entities as an attribute.
     If so start a walk over that information. */
198
199
static void start_type_walk(ir_node *node, void *ctx)
{
Matthias Braun's avatar
Matthias Braun committed
200
201
202
203
	type_walk_env  *env  = (type_walk_env*)ctx;
	type_walk_func *pre  = env->pre;
	type_walk_func *post = env->post;
	void           *envi = env->env;
Michael Beck's avatar
Michael Beck committed
204
	irn_type_walker(node, pre, post, envi);
205
206
}

207
208
void type_walk(type_walk_func *pre, type_walk_func *post, void *env)
{
209
	irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
Michael Beck's avatar
Michael Beck committed
210
	inc_master_type_visited();
Matthias Braun's avatar
Matthias Braun committed
211
	for (size_t i = 0, n_types = get_irp_n_types(); i < n_types; ++i) {
Christoph Mallon's avatar
Christoph Mallon committed
212
		do_type_walk(get_irp_type(i), NULL, pre, post, env);
Michael Beck's avatar
Michael Beck committed
213
	}
Christoph Mallon's avatar
Christoph Mallon committed
214
	do_type_walk(get_glob_type(), NULL, pre, post, env);
215
	irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
216
217
}

Michael Beck's avatar
Michael Beck committed
218
219
220
221
void type_walk_irg(ir_graph *irg,
                   type_walk_func *pre,
                   type_walk_func *post,
                   void *env)
Christian Schäfer's avatar
Christian Schäfer committed
222
{
Michael Beck's avatar
Michael Beck committed
223
224
225
226
227
228
229
	/* this is needed to pass the parameters to the walker that actually
	   walks the type information */
	type_walk_env type_env;
	type_env.pre  = pre;
	type_env.post = post;
	type_env.env  = env;

230
	/* We walk over the irg to find all IR-nodes that contain an attribute
Michael Beck's avatar
Michael Beck committed
231
232
	   with type information.  If we find one we call a type walker to
	   touch the reachable type information.
233
	   The same type can be referenced by several IR-nodes.  To avoid
Michael Beck's avatar
Michael Beck committed
234
235
236
237
238
	   repeated visits of the same type node we must decrease the
	   type visited flag for each walk.  This is done in start_type_walk().
	   Here we initially increase the flag.  We only call do_type_walk that does
	   not increase the flag.
	*/
239
	irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
Michael Beck's avatar
Michael Beck committed
240
241
242
	inc_master_type_visited();
	irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);

Christoph Mallon's avatar
Christoph Mallon committed
243
	do_type_walk(NULL, get_irg_entity(irg), pre, post, env);
Michael Beck's avatar
Michael Beck committed
244

Christoph Mallon's avatar
Christoph Mallon committed
245
	do_type_walk(get_irg_frame_type(irg), NULL, pre, post, env);
Matthias Braun's avatar
Matthias Braun committed
246
	irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
Christian Schäfer's avatar
Christian Schäfer committed
247
}
248

Christoph Mallon's avatar
Christoph Mallon committed
249
static void type_walk_s2s_2(ir_type *const tp,
Michael Beck's avatar
Michael Beck committed
250
251
252
                            type_walk_func *pre,
                            type_walk_func *post,
                            void *env)
253
{
Christoph Mallon's avatar
Christoph Mallon committed
254
255
	if (type_visited(tp))
		return;
Michael Beck's avatar
Michael Beck committed
256
257

	/* iterate */
Christoph Mallon's avatar
Christoph Mallon committed
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
	mark_type_visited(tp);
	switch (get_type_tpop_code(tp)) {
	case tpo_class: {
		for (size_t i = 0, n = get_class_n_supertypes(tp); i < n; ++i) {
			type_walk_s2s_2(get_class_supertype(tp, i), pre, post, env);
		}
		/* execute pre method */
		if (pre)
			pre(tp, NULL, env);

		for (size_t i = 0, n = get_class_n_subtypes(tp); i < n; ++i) {
			type_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
		}

		/* execute post method */
		if (post)
			post(tp, NULL, env);
		break;
	}
	case tpo_struct:
	case tpo_method:
	case tpo_union:
	case tpo_array:
	case tpo_pointer:
	case tpo_primitive:
		/* dont care */
Michael Beck's avatar
Michael Beck committed
284
285
		break;
	default:
Christoph Mallon's avatar
Christoph Mallon committed
286
		printf(" *** Faulty type! \n");
Michael Beck's avatar
Michael Beck committed
287
288
		break;
	}
289
290
}

Michael Beck's avatar
Michael Beck committed
291
292
293
void type_walk_super2sub(type_walk_func *pre,
                         type_walk_func *post,
                         void *env)
294
{
295
	irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
Michael Beck's avatar
Michael Beck committed
296
	inc_master_type_visited();
Christoph Mallon's avatar
Christoph Mallon committed
297
	type_walk_s2s_2(get_glob_type(), pre, post, env);
Matthias Braun's avatar
Matthias Braun committed
298
	for (size_t i = 0, n_types = get_irp_n_types(); i < n_types; ++i) {
Christoph Mallon's avatar
Christoph Mallon committed
299
		type_walk_s2s_2(get_irp_type(i), pre, post, env);
Michael Beck's avatar
Michael Beck committed
300
	}
301
	irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
302
303
304
305
}

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

Christoph Mallon's avatar
Christoph Mallon committed
306
static void type_walk_super_2(ir_type *const tp, type_walk_func *pre,
307
308
                              type_walk_func *post, void *env)
{
Christoph Mallon's avatar
Christoph Mallon committed
309
310
	if (type_visited(tp))
		return;
Michael Beck's avatar
Michael Beck committed
311
312

	/* iterate */
Christoph Mallon's avatar
Christoph Mallon committed
313
314
315
316
317
318
319
320
321
	mark_type_visited(tp);
	switch (get_type_tpop_code(tp)) {
	case tpo_class:
		/* execute pre method */
		if (pre)
			pre(tp, NULL, env);

		for (size_t i = 0, n = get_class_n_supertypes(tp); i < n; ++i) {
			type_walk_super_2(get_class_supertype(tp, i), pre, post, env);
Matthias Braun's avatar
Matthias Braun committed
322
		}
Christoph Mallon's avatar
Christoph Mallon committed
323
324
325
326

		/* execute post method */
		if (post)
			post(tp, NULL, env);
Matthias Braun's avatar
Matthias Braun committed
327
		break;
Christoph Mallon's avatar
Christoph Mallon committed
328
329
330
331
332
333
	case tpo_struct:
	case tpo_method:
	case tpo_union:
	case tpo_array:
	case tpo_pointer:
	case tpo_primitive:
334
		/* don't care */
Michael Beck's avatar
Michael Beck committed
335
336
		break;
	default:
Christoph Mallon's avatar
Christoph Mallon committed
337
		printf(" *** Faulty type! \n");
Michael Beck's avatar
Michael Beck committed
338
339
		break;
	}
Boris Boesler's avatar
Boris Boesler committed
340
341
}

342
343
void type_walk_super(type_walk_func *pre, type_walk_func *post, void *env)
{
344
	irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
Michael Beck's avatar
Michael Beck committed
345
	inc_master_type_visited();
Christoph Mallon's avatar
Christoph Mallon committed
346
	type_walk_super_2(get_glob_type(), pre, post, env);
Matthias Braun's avatar
Matthias Braun committed
347
	for (size_t i = 0, n_types = get_irp_n_types(); i < n_types; ++i) {
Christoph Mallon's avatar
Christoph Mallon committed
348
		type_walk_super_2(get_irp_type(i), pre, post, env);
Michael Beck's avatar
Michael Beck committed
349
	}
350
	irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
Boris Boesler's avatar
Boris Boesler committed
351
352
353
354
}

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

355

356
357
static void class_walk_s2s_2(ir_type *tp, class_walk_func *pre,
                             class_walk_func *post, void *env)
358
{
Michael Beck's avatar
Michael Beck committed
359
	/* marked? */
Matthias Braun's avatar
Matthias Braun committed
360
361
	if (type_visited(tp))
		return;
Michael Beck's avatar
Michael Beck committed
362
363

	/* Assure all supertypes are visited before */
Matthias Braun's avatar
Matthias Braun committed
364
	for (size_t i = 0, n = get_class_n_supertypes(tp); i < n; ++i) {
365
		if (!type_visited(get_class_supertype(tp, i)))
Michael Beck's avatar
Michael Beck committed
366
367
368
369
370
371
372
373
374
			return;
	}

	mark_type_visited(tp);

	/* execute pre method */
	if (pre)
		pre(tp, env);

Matthias Braun's avatar
Matthias Braun committed
375
	for (size_t i = 0, n = get_class_n_subtypes(tp); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
376
377
378
379
380
		class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
	}
	/* execute post method */
	if (post)
		post(tp, env);
381
382
}

Michael Beck's avatar
Michael Beck committed
383
384
385
void class_walk_super2sub(class_walk_func *pre,
                          class_walk_func *post,
                          void *env)
386
{
387
	irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
Michael Beck's avatar
Michael Beck committed
388
	inc_master_type_visited();
Matthias Braun's avatar
Matthias Braun committed
389
390
	for (size_t i = 0, n_types = get_irp_n_types(); i < n_types; i++) {
		ir_type *tp = get_irp_type(i);
Michael Beck's avatar
Michael Beck committed
391
392
		if (is_Class_type(tp) &&
		    (get_class_n_supertypes(tp) == 0) &&
393
		    !type_visited(tp) &&
Andreas Zwinkau's avatar
Andreas Zwinkau committed
394
		    (! is_frame_type(tp)) &&
Andreas Zwinkau's avatar
Andreas Zwinkau committed
395
		    (tp != get_glob_type())) {
Michael Beck's avatar
Michael Beck committed
396
397
398
			class_walk_s2s_2(tp, pre, post, env);
		}
	}
399
	irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
400
}
401
402


Michael Beck's avatar
Michael Beck committed
403
404
405
void walk_types_entities(ir_type *tp,
                         entity_walk_func *doit,
                         void *env)
406
{
Michael Beck's avatar
Michael Beck committed
407
408
	switch (get_type_tpop_code(tp)) {
	case tpo_class:
Matthias Braun's avatar
Matthias Braun committed
409
		for (size_t i = 0, n = get_class_n_members(tp); i < n; ++i)
Michael Beck's avatar
Michael Beck committed
410
411
412
			doit(get_class_member(tp, i), env);
		break;
	case tpo_struct:
Matthias Braun's avatar
Matthias Braun committed
413
		for (size_t i = 0, n = get_struct_n_members(tp); i < n; ++i)
Michael Beck's avatar
Michael Beck committed
414
415
416
			doit(get_struct_member(tp, i), env);
		break;
	case tpo_union:
Matthias Braun's avatar
Matthias Braun committed
417
		for (size_t i = 0, n = get_union_n_members(tp); i < n; ++i)
Michael Beck's avatar
Michael Beck committed
418
419
420
			doit(get_union_member(tp, i), env);
		break;
	case tpo_array:
421
	case tpo_code:
Michael Beck's avatar
Michael Beck committed
422
423
424
	case tpo_method:
	case tpo_pointer:
	case tpo_primitive:
425
426
	case tpo_uninitialized:
	case tpo_unknown:
Michael Beck's avatar
Michael Beck committed
427
428
		break;
	}
429
}