3 * File name: ir/tr/typewalk.c
4 * Purpose: Traverse the type information.
5 * Author: Goetz Lindenmaier
9 * Copyright: (c) 1999-2003 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
16 * Traverse the type information. The walker walks the whole ir graph
17 * to find the distinct type trees in the type graph forest.
18 * - execute the pre function before recursion
19 * - execute the post function after recursion
35 #include "type_or_entity.h"
39 #include "irgraph_t.h"
44 * The walker environment
46 typedef struct type_walk_env {
47 type_walk_func *pre; /**< Pre-walker function */
48 type_walk_func *post; /**< Post-walker function */
49 void *env; /**< environment for walker functions */
52 /* a walker for irn's */
53 static void irn_type_walker(
54 ir_node *node, type_walk_func *pre, type_walk_func *post, void *env);
57 * Main walker: walks over all used types/entities of a
60 static void do_type_walk(type_or_ent *tore,
65 int i, n_types, n_mem;
66 ir_entity *ent = NULL;
71 switch (get_kind(tore)) {
73 ent = (ir_entity *)tore;
74 if (entity_visited(ent)) return;
77 tp = skip_tid((ir_type *)tore);
78 if (type_visited(tp)) return;
84 /* execute pre method */
89 switch (get_kind(tore)) {
91 mark_entity_visited(ent);
92 do_type_walk((type_or_ent *)get_entity_owner(ent), pre, post, env);
93 do_type_walk((type_or_ent *)get_entity_type(ent), pre, post, env);
95 if (get_entity_variability(ent) != variability_uninitialized) {
96 /* walk over the value types */
97 if (is_atomic_entity(ent)) {
98 n = get_atomic_ent_value(ent);
99 irn_type_walker(n, pre, post, env);
102 n_mem = get_compound_ent_n_values(ent);
103 for (i = 0; i < n_mem; ++i) {
104 n = get_compound_ent_value(ent, i);
105 irn_type_walker(n, pre, post, env);
111 mark_type_visited(tp);
112 switch (get_type_tpop_code(tp)) {
115 n_types = get_class_n_supertypes(tp);
116 for (i = 0; i < n_types; ++i)
117 do_type_walk((type_or_ent *)get_class_supertype(tp, i), pre, post, env);
119 n_mem = get_class_n_members(tp);
120 for (i = 0; i < n_mem; ++i)
121 do_type_walk((type_or_ent *)get_class_member(tp, i), pre, post, env);
123 n_types = get_class_n_subtypes(tp);
124 for (i = 0; i < n_types; ++i)
125 do_type_walk((type_or_ent *)get_class_subtype(tp, i), pre, post, env);
129 n_mem = get_struct_n_members(tp);
130 for (i = 0; i < n_mem; ++i)
131 do_type_walk((type_or_ent *)get_struct_member(tp, i), pre, post, env);
135 n_mem = get_method_n_params(tp);
136 for (i = 0; i < n_mem; ++i)
137 do_type_walk((type_or_ent *)get_method_param_type(tp, i), pre, post, env);
139 n_mem = get_method_n_ress(tp);
140 for (i = 0; i < n_mem; ++i)
141 do_type_walk((type_or_ent *)get_method_res_type(tp, i), pre, post, env);
145 n_mem = get_union_n_members(tp);
146 for (i = 0; i < n_mem; ++i)
147 do_type_walk((type_or_ent *)get_union_member(tp, i), pre, post, env);
151 do_type_walk((type_or_ent *)get_array_element_type(tp),
153 do_type_walk((type_or_ent *)get_array_element_entity(tp),
157 case tpo_enumeration:
162 do_type_walk((type_or_ent *)get_pointer_points_to_type(tp),
173 assert(0 && "Faulty type");
176 break; /* end case k_type */
179 printf(" *** Faulty type or entity! \n");
183 /* execute post method */
190 /** Check whether node contains types or entities as an attribute.
191 If so start a walk over that information. */
192 static void irn_type_walker(
193 ir_node *node, type_walk_func *pre, type_walk_func *post, void *env)
200 ent = get_irn_entity_attr(node);
202 do_type_walk((type_or_ent *)ent, pre, post, env);
203 tp = get_irn_type_attr(node);
205 do_type_walk((type_or_ent *)tp, pre, post, env);
208 /** Check whether node contains types or entities as an attribute.
209 If so start a walk over that information. */
210 static void start_type_walk(ir_node *node, void *ctx) {
211 type_walk_env *env = ctx;
213 type_walk_func *post;
220 irn_type_walker(node, pre, post, envi);
223 /* walker: walks over all types */
224 void type_walk(type_walk_func *pre, type_walk_func *post, void *env) {
225 int i, n_types = get_irp_n_types();
227 inc_master_type_visited();
228 for (i = 0; i < n_types; ++i) {
229 do_type_walk((type_or_ent *)get_irp_type(i), pre, post, env);
231 do_type_walk((type_or_ent *)get_glob_type(), pre, post, env);
234 void type_walk_irg (ir_graph *irg,
235 void (*pre)(type_or_ent*, void*),
236 void (*post)(type_or_ent*, void*),
239 ir_graph *rem = current_ir_graph;
240 /* this is needed to pass the parameters to the walker that actually
241 walks the type information */
242 type_walk_env type_env;
245 type_env.post = post;
248 current_ir_graph = irg;
250 /* We walk over the irg to find all irnodes that contain an attribute
251 with type information. If we find one we call a type walker to
252 touch the reachable type information.
253 The same type can be referenced by several irnodes. To avoid
254 repeated visits of the same type node we must decrease the
255 type visited flag for each walk. This is done in start_type_walk().
256 Here we initially increase the flag. We only call do_type_walk that does
257 not increase the flag.
259 inc_master_type_visited();
260 irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);
262 do_type_walk((type_or_ent *)get_irg_entity(irg), pre, post, env);
264 do_type_walk((type_or_ent *)get_irg_frame_type(irg), pre, post, env);
266 current_ir_graph = rem;
270 static void type_walk_s2s_2(type_or_ent *tore,
271 void (*pre)(type_or_ent*, void*),
272 void (*post)(type_or_ent*, void*),
278 switch (get_kind(tore)) {
280 if (entity_visited((ir_entity *)tore)) return;
283 if (type_id == get_type_tpop((ir_type*)tore)) {
284 type_walk_s2s_2((type_or_ent *)skip_tid((ir_type *)tore), pre, post, env);
287 if (type_visited((ir_type *)tore)) return;
294 switch (get_kind(tore)) {
297 ir_type *tp = (ir_type *)tore;
298 mark_type_visited(tp);
299 switch (get_type_tpop_code(tp)) {
302 n = get_class_n_supertypes(tp);
303 for (i = 0; i < n; ++i) {
304 type_walk_s2s_2((type_or_ent *)get_class_supertype(tp, i), pre,
307 /* execute pre method */
310 tp = skip_tid((ir_type*)tore);
312 n = get_class_n_subtypes(tp);
313 for (i = 0; i < n; ++i) {
314 type_walk_s2s_2((type_or_ent *)get_class_subtype(tp, i), pre,
318 /* execute post method */
327 case tpo_enumeration:
334 printf(" *** Faulty type! \n");
337 } break; /* end case k_type */
342 printf(" *** Faulty type or entity! \n");
348 void type_walk_super2sub(
349 void (*pre)(type_or_ent*, void*),
350 void (*post)(type_or_ent*, void*),
353 int i, n_types = get_irp_n_types();
356 inc_master_type_visited();
357 type_walk_s2s_2((type_or_ent *)get_glob_type(), pre, post, env);
358 for (i = 0; i < n_types; ++i) {
359 tp = get_irp_type(i);
360 type_walk_s2s_2((type_or_ent *)tp, pre, post, env);
364 /*****************************************************************************/
367 type_walk_super_2(type_or_ent *tore,
368 void (*pre)(type_or_ent*, void*),
369 void (*post)(type_or_ent*, void*),
375 switch (get_kind(tore)) {
377 if (entity_visited((ir_entity *)tore)) return;
380 if (type_id == get_type_tpop((ir_type*)tore)) {
381 type_walk_super_2((type_or_ent *)skip_tid((ir_type *)tore), pre, post, env);
384 if (type_visited((ir_type *)tore)) return;
391 switch (get_kind(tore)) {
394 ir_type *tp = (ir_type *)tore;
395 mark_type_visited(tp);
396 switch (get_type_tpop_code(tp)) {
399 /* execute pre method */
402 tp = skip_tid((ir_type*)tore);
404 n = get_class_n_supertypes(tp);
405 for (i = 0; i < n; ++i) {
406 type_walk_super_2((type_or_ent *)get_class_supertype(tp, i), pre,
410 /* execute post method */
419 case tpo_enumeration:
426 printf(" *** Faulty type! \n");
429 } break; /* end case k_type */
434 printf(" *** Faulty type or entity! \n");
440 void type_walk_super(
441 void (*pre)(type_or_ent*, void*),
442 void (*post)(type_or_ent*, void*),
444 int i, n_types = get_irp_n_types();
447 inc_master_type_visited();
448 type_walk_super_2((type_or_ent *)get_glob_type(), pre, post, env);
449 for (i = 0; i < n_types; ++i) {
450 tp = get_irp_type(i);
451 type_walk_super_2((type_or_ent *)tp, pre, post, env);
455 /*****************************************************************************/
459 class_walk_s2s_2(ir_type *tp,
460 void (*pre)(ir_type*, void*),
461 void (*post)(ir_type*, void*),
467 if (type_visited(tp)) return;
469 assert(is_Class_type(tp));
470 /* Assure all supertypes are visited before */
471 n = get_class_n_supertypes(tp);
472 for (i = 0; i < n; ++i) {
473 if (type_not_visited(get_class_supertype(tp, i)))
477 mark_type_visited(tp);
479 /* execute pre method */
484 n = get_class_n_subtypes(tp);
485 for (i = 0; i < n; ++i) {
486 class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
488 /* execute post method */
495 void class_walk_super2sub(
496 void (*pre)(ir_type*, void*),
497 void (*post)(ir_type*, void*),
500 int i, n_types = get_irp_n_types();
503 inc_master_type_visited();
504 for (i = 0; i < n_types; i++) {
505 tp = get_irp_type(i);
506 if (is_Class_type(tp) &&
507 (get_class_n_supertypes(tp) == 0) &&
508 type_not_visited(tp)) {
509 assert(! is_frame_type(tp));
510 assert(tp != get_glob_type());
511 class_walk_s2s_2(tp, pre, post, env);
517 /* Walks over all entities in the type */
518 void walk_types_entities(
520 void (*doit)(ir_entity*, void*),
525 switch (get_type_tpop_code(tp)) {
527 n = get_class_n_members(tp);
528 for (i = 0; i < n; ++i)
529 doit(get_class_member(tp, i), env);
532 n = get_struct_n_members(tp);
533 for (i = 0; i < n; ++i)
534 doit(get_struct_member(tp, i), env);
537 n = get_union_n_members(tp);
538 for (i = 0; i < n; ++i)
539 doit(get_union_member(tp, i), env);
542 doit(get_array_element_entity(tp), env);
545 case tpo_enumeration: