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

20
/**
Michael Beck's avatar
Michael Beck committed
21
22
23
24
25
 * @file    typewalk.c
 * @brief   Functionality to modify the type graph.
 * @author  Goetz Lindenmaier
 * @version $Id$
 * @summary
26
27
 *
 * Traverse the type information.  The walker walks the whole ir graph
28
29
30
31
 * to find the distinct type trees in the type graph forest.
 * - execute the pre function before recursion
 * - execute the post function after recursion
 */
Matthias Braun's avatar
Matthias Braun committed
32
#include "config.h"
Michael Beck's avatar
Michael Beck committed
33

34
#include <stdlib.h>
Götz Lindenmaier's avatar
Götz Lindenmaier committed
35
#include <stdio.h>
Christian Schäfer's avatar
Christian Schäfer committed
36

Boris Boesler's avatar
Boris Boesler committed
37
#include "entity_t.h"
38
#include "type_t.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
39
40
41
42
43

#include "irprog_t.h"
#include "irgraph_t.h"
#include "irnode_t.h"
#include "irgwalk.h"
44
#include "error.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
45

46
47
48
/**
 * The walker environment
 */
Christian Schäfer's avatar
Christian Schäfer committed
49
typedef struct type_walk_env {
Michael Beck's avatar
Michael Beck committed
50
51
52
	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
53
54
} type_walk_env;

55
56
/* a walker for irn's */
static void irn_type_walker(
Michael Beck's avatar
Michael Beck committed
57
	ir_node *node, type_walk_func *pre, type_walk_func *post, void *env);
Christian Schäfer's avatar
Christian Schäfer committed
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
static void walk_initializer(ir_initializer_t *initializer,
                             type_walk_func *pre, type_walk_func *post,
                             void *env)
{
	switch(initializer->kind) {
	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: {
		size_t i;
		for(i = 0; i < initializer->compound.n_initializers; ++i) {
			ir_initializer_t *subinitializer
				= initializer->compound.initializers[i];
			walk_initializer(subinitializer, pre, post, env);
		}
		return;
	}
	}
	panic("invalid initializer found");
}

84
85
86
87
/**
 * Main walker: walks over all used types/entities of a
 * type entity.
 */
88
static void do_type_walk(type_or_ent tore,
Michael Beck's avatar
Michael Beck committed
89
90
91
                         type_walk_func *pre,
                         type_walk_func *post,
                         void *env)
Christian Schäfer's avatar
Christian Schäfer committed
92
{
93
94
95
96
97
	int         i, n_types, n_mem;
	ir_entity   *ent = NULL;
	ir_type     *tp = NULL;
	ir_node     *n;
	type_or_ent cont;
Michael Beck's avatar
Michael Beck committed
98
99

	/* marked? */
100
	switch (get_kind(tore.ent)) {
Michael Beck's avatar
Michael Beck committed
101
	case k_entity:
102
103
104
		ent = tore.ent;
		if (entity_visited(ent))
			return;
Michael Beck's avatar
Michael Beck committed
105
106
		break;
	case k_type:
107
108
109
		tp = skip_tid(tore.typ);
		if (type_visited(tp))
			return;
Michael Beck's avatar
Michael Beck committed
110
111
112
113
114
115
116
117
118
119
		break;
	default:
		break;
	}

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

	/* iterate */
120
	switch (get_kind(tore.ent)) {
Michael Beck's avatar
Michael Beck committed
121
122
	case k_entity:
		mark_entity_visited(ent);
123
124
125
126
		cont.typ = get_entity_owner(ent);
		do_type_walk(cont, pre, post, env);
		cont.typ = get_entity_type(ent);
		do_type_walk(cont, pre, post, env);
Michael Beck's avatar
Michael Beck committed
127
128
129

		if (get_entity_variability(ent) != variability_uninitialized) {
			/* walk over the value types */
130
131
132
			if (ent->has_initializer) {
				walk_initializer(ent->attr.initializer, pre, post, env);
			} else if (is_atomic_entity(ent)) {
Michael Beck's avatar
Michael Beck committed
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
				n = get_atomic_ent_value(ent);
				irn_type_walker(n, pre, post, env);
			} else {
				n_mem = get_compound_ent_n_values(ent);
				for (i = 0; i < n_mem; ++i) {
					n = get_compound_ent_value(ent, i);
					irn_type_walker(n, pre, post, env);
				}
			}
		}
		break;
	case k_type:
		mark_type_visited(tp);
		switch (get_type_tpop_code(tp)) {

		case tpo_class:
			n_types = get_class_n_supertypes(tp);
150
151
152
153
			for (i = 0; i < n_types; ++i) {
				cont.typ = get_class_supertype(tp, i);
				do_type_walk(cont, pre, post, env);
			}
Michael Beck's avatar
Michael Beck committed
154
			n_mem = get_class_n_members(tp);
155
156
157
158
			for (i = 0; i < n_mem; ++i) {
				cont.ent = get_class_member(tp, i);
				do_type_walk(cont, pre, post, env);
			}
Michael Beck's avatar
Michael Beck committed
159
			n_types = get_class_n_subtypes(tp);
160
161
162
163
			for (i = 0; i < n_types; ++i) {
				cont.typ = get_class_subtype(tp, i);
				do_type_walk(cont, pre, post, env);
			}
Michael Beck's avatar
Michael Beck committed
164
165
166
167
			break;

		case tpo_struct:
			n_mem = get_struct_n_members(tp);
168
169
170
171
			for (i = 0; i < n_mem; ++i) {
				cont.ent = get_struct_member(tp, i);
				do_type_walk(cont, pre, post, env);
			}
Michael Beck's avatar
Michael Beck committed
172
173
174
175
			break;

		case tpo_method:
			n_mem = get_method_n_params(tp);
176
177
178
179
			for (i = 0; i < n_mem; ++i) {
				cont.typ = get_method_param_type(tp, i);
				do_type_walk(cont, pre, post, env);
			}
Michael Beck's avatar
Michael Beck committed
180
			n_mem = get_method_n_ress(tp);
181
182
183
184
			for (i = 0; i < n_mem; ++i) {
				cont.typ = get_method_res_type(tp, i);
				do_type_walk(cont, pre, post, env);
			}
Michael Beck's avatar
Michael Beck committed
185
186
187
188
			break;

		case tpo_union:
			n_mem = get_union_n_members(tp);
189
190
191
192
			for (i = 0; i < n_mem; ++i) {
				cont.ent = get_union_member(tp, i);
				do_type_walk(cont, pre, post, env);
			}
Michael Beck's avatar
Michael Beck committed
193
194
195
			break;

		case tpo_array:
196
197
198
199
			cont.typ = get_array_element_type(tp);
			do_type_walk(cont, pre, post, env);
			cont.ent = get_array_element_entity(tp);
			do_type_walk(cont, pre, post, env);
Michael Beck's avatar
Michael Beck committed
200
201
202
203
204
205
206
			break;

		case tpo_enumeration:
			/* a leave */
			break;

		case tpo_pointer:
207
208
			cont.typ = get_pointer_points_to_type(tp);
			do_type_walk(cont, pre, post, env);
Michael Beck's avatar
Michael Beck committed
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
			break;

		case tpo_primitive:
		case tpo_id:
		case tpo_none:
		case tpo_unknown:
			/* a leave. */
			break;
		default:
			assert(0 && "Faulty type");
			break;
		}
		break; /* end case k_type */

	default:
		printf(" *** Faulty type or entity! \n");
		break;
	}

	/* execute post method */
	if (post)
		post(tore, env);
Christian Schäfer's avatar
Christian Schäfer committed
231
232
}

233
/**  Check whether node contains types or entities as an attribute.
234
     If so start a walk over that information. */
235
236
237
static void irn_type_walker(
  ir_node *node, type_walk_func *pre, type_walk_func *post, void *env)
{
238
	type_or_ent cont;
Christian Schäfer's avatar
Christian Schäfer committed
239

Michael Beck's avatar
Michael Beck committed
240
	assert(node);
Christian Schäfer's avatar
Christian Schäfer committed
241

242
243
244
245
246
247
	cont.ent = get_irn_entity_attr(node);
	if (cont.ent)
		do_type_walk(cont, pre, post, env);
	cont.typ = get_irn_type_attr(node);
	if (cont.typ)
		do_type_walk(cont, pre, post, env);
Christian Schäfer's avatar
Christian Schäfer committed
248
249
}

250
251
252
/**  Check whether node contains types or entities as an attribute.
     If so start a walk over that information. */
static void start_type_walk(ir_node *node, void *ctx) {
Michael Beck's avatar
Michael Beck committed
253
254
255
256
	type_walk_env *env = ctx;
	type_walk_func *pre;
	type_walk_func *post;
	void *envi;
257

Michael Beck's avatar
Michael Beck committed
258
259
260
	pre  = env->pre;
	post = env->post;
	envi = env->env;
261

Michael Beck's avatar
Michael Beck committed
262
	irn_type_walker(node, pre, post, envi);
263
264
265
}

/* walker: walks over all types */
266
void type_walk(type_walk_func *pre, type_walk_func *post, void *env) {
267
268
	int         i, n_types = get_irp_n_types();
	type_or_ent cont;
269

Michael Beck's avatar
Michael Beck committed
270
271
	inc_master_type_visited();
	for (i = 0; i < n_types; ++i) {
272
273
		cont.typ = get_irp_type(i);
		do_type_walk(cont, pre, post, env);
Michael Beck's avatar
Michael Beck committed
274
	}
275
276
	cont.typ = get_glob_type();
	do_type_walk(cont, pre, post, env);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
277
278
}

279
280
281
282
283
284
285
286
287
288
void type_walk_plus_frames(type_walk_func *pre, type_walk_func *post, void *env) {
	int i, n_irgs = get_irp_n_irgs();
	type_or_ent cont;

	type_walk(pre, post, env);

	for (i = 0; i < n_irgs; ++i) {
		ir_graph *irg = get_irp_irg(i);
		cont.typ = get_irg_frame_type(irg);
		do_type_walk(cont, pre, post, env);
289
290
291
292

		cont.typ = get_method_value_param_type(get_entity_type(get_irg_entity(irg)));
		if(cont.typ)
			do_type_walk(cont, pre, post, env);
293
294
295
	}
}

Michael Beck's avatar
Michael Beck committed
296
297
298
299
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
300
{
Michael Beck's avatar
Michael Beck committed
301
302
303
304
	ir_graph *rem = current_ir_graph;
	/* this is needed to pass the parameters to the walker that actually
	   walks the type information */
	type_walk_env type_env;
305
	type_or_ent   cont;
Michael Beck's avatar
Michael Beck committed
306
307
308
309
310
311
312

	type_env.pre  = pre;
	type_env.post = post;
	type_env.env  = env;

	current_ir_graph = irg;

313
	/* We walk over the irg to find all IR-nodes that contain an attribute
Michael Beck's avatar
Michael Beck committed
314
315
	   with type information.  If we find one we call a type walker to
	   touch the reachable type information.
316
	   The same type can be referenced by several IR-nodes.  To avoid
Michael Beck's avatar
Michael Beck committed
317
318
319
320
321
322
323
324
	   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.
	*/
	inc_master_type_visited();
	irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);

325
326
	cont.ent = get_irg_entity(irg);
	do_type_walk(cont, pre, post, env);
Michael Beck's avatar
Michael Beck committed
327

328
329
	cont.typ = get_irg_frame_type(irg);
	do_type_walk(cont, pre, post, env);
Michael Beck's avatar
Michael Beck committed
330
331

	current_ir_graph = rem;
Christian Schäfer's avatar
Christian Schäfer committed
332
}
333

334
static void type_walk_s2s_2(type_or_ent tore,
Michael Beck's avatar
Michael Beck committed
335
336
337
                            type_walk_func *pre,
                            type_walk_func *post,
                            void *env)
338
{
339
340
	type_or_ent cont;
	int         i, n;
Michael Beck's avatar
Michael Beck committed
341
342

	/* marked? */
343
	switch (get_kind(tore.ent)) {
Michael Beck's avatar
Michael Beck committed
344
	case k_entity:
345
		if (entity_visited(tore.ent)) return;
Michael Beck's avatar
Michael Beck committed
346
347
		break;
	case k_type:
348
349
350
		if (type_id == get_type_tpop(tore.typ)) {
			cont.typ = skip_tid(tore.typ);
			type_walk_s2s_2(cont, pre, post, env);
Michael Beck's avatar
Michael Beck committed
351
352
			return;
		}
353
		if (type_visited(tore.typ)) return;
Michael Beck's avatar
Michael Beck committed
354
355
356
357
358
359
		break;
	default:
		break;
	}

	/* iterate */
360
	switch (get_kind(tore.typ)) {
Michael Beck's avatar
Michael Beck committed
361
362
	case k_type:
		{
363
			ir_type *tp = tore.typ;
Michael Beck's avatar
Michael Beck committed
364
365
366
367
368
369
			mark_type_visited(tp);
			switch (get_type_tpop_code(tp)) {
			case tpo_class:
				{
					n = get_class_n_supertypes(tp);
					for (i = 0; i < n; ++i) {
370
371
						cont.typ = get_class_supertype(tp, i);
						type_walk_s2s_2(cont, pre, post, env);
Michael Beck's avatar
Michael Beck committed
372
373
374
375
					}
					/* execute pre method */
					if (pre)
						pre(tore, env);
376
					tp = skip_tid(tp);
Michael Beck's avatar
Michael Beck committed
377
378
379

					n = get_class_n_subtypes(tp);
					for (i = 0; i < n; ++i) {
380
381
						cont.typ = get_class_subtype(tp, i);
						type_walk_s2s_2(cont, pre, post, env);
Michael Beck's avatar
Michael Beck committed
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
					}

					/* execute post method */
					if (post)
						post(tore, env);
				}
				break;
			case tpo_struct:
			case tpo_method:
			case tpo_union:
			case tpo_array:
			case tpo_enumeration:
			case tpo_pointer:
			case tpo_primitive:
			case tpo_id:
				/* dont care */
				break;
			default:
				printf(" *** Faulty type! \n");
				break;
			}
		} break; /* end case k_type */
	case k_entity:
405
		/* don't care */
Michael Beck's avatar
Michael Beck committed
406
407
408
409
410
		break;
	default:
		printf(" *** Faulty type or entity! \n");
		break;
	}
411
412
}

Michael Beck's avatar
Michael Beck committed
413
414
415
void type_walk_super2sub(type_walk_func *pre,
                         type_walk_func *post,
                         void *env)
416
{
417
418
	type_or_ent cont;
	int         i, n_types = get_irp_n_types();
Michael Beck's avatar
Michael Beck committed
419
420

	inc_master_type_visited();
421
422
	cont.typ = get_glob_type();
	type_walk_s2s_2(cont, pre, post, env);
Michael Beck's avatar
Michael Beck committed
423
	for (i = 0; i < n_types; ++i) {
424
425
		cont.typ = get_irp_type(i);
		type_walk_s2s_2(cont, pre, post, env);
Michael Beck's avatar
Michael Beck committed
426
	}
427
428
429
430
}

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

431
static void
432
type_walk_super_2(type_or_ent tore,
Michael Beck's avatar
Michael Beck committed
433
434
435
                  type_walk_func *pre,
                  type_walk_func *post,
                  void *env) {
436
437
	type_or_ent cont;
	int         i, n;
Michael Beck's avatar
Michael Beck committed
438
439

	/* marked? */
440
	switch (get_kind(tore.ent)) {
Michael Beck's avatar
Michael Beck committed
441
	case k_entity:
442
443
		if (entity_visited(tore.ent))
			return;
Michael Beck's avatar
Michael Beck committed
444
445
		break;
	case k_type:
446
447
448
		if (type_id == get_type_tpop(tore.typ)) {
			cont.typ = skip_tid(tore.typ);
			type_walk_super_2(cont, pre, post, env);
Michael Beck's avatar
Michael Beck committed
449
450
			return;
		}
451
452
		if (type_visited(tore.typ))
			return;
Michael Beck's avatar
Michael Beck committed
453
454
455
456
457
458
		break;
	default:
		break;
	}

	/* iterate */
459
	switch (get_kind(tore.typ)) {
Michael Beck's avatar
Michael Beck committed
460
461
	case k_type:
		{
462
			ir_type *tp = tore.typ;
Michael Beck's avatar
Michael Beck committed
463
464
465
466
467
468
469
			mark_type_visited(tp);
			switch (get_type_tpop_code(tp)) {
			case tpo_class:
				{
					/* execute pre method */
					if (pre)
						pre(tore, env);
470
					tp = skip_tid(tp);
Michael Beck's avatar
Michael Beck committed
471
472
473

					n = get_class_n_supertypes(tp);
					for (i = 0; i < n; ++i) {
474
475
						cont.typ = get_class_supertype(tp, i);
						type_walk_super_2(cont, pre, post, env);
Michael Beck's avatar
Michael Beck committed
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
					}

					/* execute post method */
					if (post)
						post(tore, env);
				}
				break;
			case tpo_struct:
			case tpo_method:
			case tpo_union:
			case tpo_array:
			case tpo_enumeration:
			case tpo_pointer:
			case tpo_primitive:
			case tpo_id:
491
				/* don't care */
Michael Beck's avatar
Michael Beck committed
492
493
494
495
496
497
498
				break;
			default:
				printf(" *** Faulty type! \n");
				break;
			}
		} break; /* end case k_type */
	case k_entity:
499
		/* don't care */
Michael Beck's avatar
Michael Beck committed
500
501
502
503
504
		break;
	default:
		printf(" *** Faulty type or entity! \n");
		break;
	}
Boris Boesler's avatar
Boris Boesler committed
505
506
}

Michael Beck's avatar
Michael Beck committed
507
508
509
void type_walk_super(type_walk_func *pre,
                     type_walk_func *post,
                     void *env) {
510
511
	int         i, n_types = get_irp_n_types();
	type_or_ent cont;
Michael Beck's avatar
Michael Beck committed
512
513

	inc_master_type_visited();
514
515
	cont.typ = get_glob_type();
	type_walk_super_2(cont, pre, post, env);
Michael Beck's avatar
Michael Beck committed
516
	for (i = 0; i < n_types; ++i) {
517
518
		cont.typ = get_irp_type(i);
		type_walk_super_2(cont, pre, post, env);
Michael Beck's avatar
Michael Beck committed
519
	}
Boris Boesler's avatar
Boris Boesler committed
520
521
522
523
}

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

524

525
static void
Michael Beck's avatar
Michael Beck committed
526
class_walk_s2s_2(ir_type *tp,
Michael Beck's avatar
Michael Beck committed
527
528
529
                 class_walk_func *pre,
                 class_walk_func *post,
                 void *env)
530
{
Michael Beck's avatar
Michael Beck committed
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
	int i, n;

	/* marked? */
	if (type_visited(tp)) return;

	assert(is_Class_type(tp));
	/* Assure all supertypes are visited before */
	n = get_class_n_supertypes(tp);
	for (i = 0; i < n; ++i) {
		if (type_not_visited(get_class_supertype(tp, i)))
			return;
	}

	mark_type_visited(tp);

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

	tp = skip_tid(tp);
	n = get_class_n_subtypes(tp);
	for (i = 0; i < n; ++i) {
		class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
	}
	/* execute post method */
	if (post)
		post(tp, env);
558
559
}

Michael Beck's avatar
Michael Beck committed
560
561
562
void class_walk_super2sub(class_walk_func *pre,
                          class_walk_func *post,
                          void *env)
563
{
Michael Beck's avatar
Michael Beck committed
564
565
566
567
568
569
570
571
572
573
574
575
576
577
	int i, n_types = get_irp_n_types();
	ir_type *tp;

	inc_master_type_visited();
	for (i = 0; i < n_types; i++) {
		tp = get_irp_type(i);
		if (is_Class_type(tp) &&
		    (get_class_n_supertypes(tp) == 0) &&
		    type_not_visited(tp)) {
			assert(! is_frame_type(tp));
			assert(tp != get_glob_type());
			class_walk_s2s_2(tp, pre, post, env);
		}
	}
578
}
579
580
581


/* Walks over all entities in the type */
Michael Beck's avatar
Michael Beck committed
582
583
584
void walk_types_entities(ir_type *tp,
                         entity_walk_func *doit,
                         void *env)
585
{
Michael Beck's avatar
Michael Beck committed
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
	int i, n;

	switch (get_type_tpop_code(tp)) {
	case tpo_class:
		n = get_class_n_members(tp);
		for (i = 0; i < n; ++i)
			doit(get_class_member(tp, i), env);
		break;
	case tpo_struct:
		n = get_struct_n_members(tp);
		for (i = 0; i < n; ++i)
			doit(get_struct_member(tp, i), env);
		break;
	case tpo_union:
		n = get_union_n_members(tp);
		for (i = 0; i < n; ++i)
			doit(get_union_member(tp, i), env);
		break;
	case tpo_array:
		doit(get_array_element_entity(tp), env);
		break;
	case tpo_method:
	case tpo_enumeration:
	case tpo_pointer:
	case tpo_primitive:
	case tpo_id:
	default:
		break;
	}
615
}