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;
71 switch (get_kind(tore)) {
74 if (entity_visited(ent)) return;
77 tp = skip_tid((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)
199 switch (get_irn_opcode(node)) { /* node label */
201 kind = get_SymConst_kind(node);
202 if (kind == symconst_type_tag || kind == symconst_size)
203 do_type_walk((type_or_ent *)get_SymConst_type(node), pre, post, env);
204 else if (kind == symconst_addr_ent)
205 do_type_walk((type_or_ent *)get_SymConst_entity(node), pre, post, env);
208 do_type_walk((type_or_ent *)get_Sel_entity(node), pre, post, env);
211 do_type_walk((type_or_ent *)get_Call_type(node), pre, post, env);
214 do_type_walk((type_or_ent *)get_Alloc_type(node), pre, post, env);
217 do_type_walk((type_or_ent *)get_Free_type(node), pre, post, env);
220 do_type_walk((type_or_ent *)get_Cast_type(node), pre, post, env);
227 /** Check whether node contains types or entities as an attribute.
228 If so start a walk over that information. */
229 static void start_type_walk(ir_node *node, void *ctx) {
230 type_walk_env *env = ctx;
232 type_walk_func *post;
239 irn_type_walker(node, pre, post, envi);
242 /* walker: walks over all types */
243 void type_walk(type_walk_func *pre, type_walk_func *post, void *env) {
244 int i, n_types = get_irp_n_types();
246 inc_master_type_visited();
247 for (i = 0; i < n_types; ++i) {
248 do_type_walk((type_or_ent *)get_irp_type(i), pre, post, env);
250 do_type_walk((type_or_ent *)get_glob_type(), pre, post, env);
253 void type_walk_irg (ir_graph *irg,
254 void (*pre)(type_or_ent*, void*),
255 void (*post)(type_or_ent*, void*),
258 ir_graph *rem = current_ir_graph;
259 /* this is needed to pass the parameters to the walker that actually
260 walks the type information */
261 type_walk_env type_env;
264 type_env.post = post;
267 current_ir_graph = irg;
269 /* We walk over the irg to find all irnodes that contain an attribute
270 with type information. If we find one we call a type walker to
271 touch the reachable type information.
272 The same type can be referenced by several irnodes. To avoid
273 repeated visits of the same type node we must decrease the
274 type visited flag for each walk. This is done in start_type_walk().
275 Here we initially increase the flag. We only call do_type_walk that does
276 not increase the flag.
278 inc_master_type_visited();
279 irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);
281 do_type_walk((type_or_ent *)get_irg_entity(irg), pre, post, env);
283 do_type_walk((type_or_ent *)get_irg_frame_type(irg), pre, post, env);
285 current_ir_graph = rem;
289 static void type_walk_s2s_2(type_or_ent *tore,
290 void (*pre)(type_or_ent*, void*),
291 void (*post)(type_or_ent*, void*),
297 switch (get_kind(tore)) {
299 if (entity_visited((entity *)tore)) return;
302 if (type_id == get_type_tpop((type*)tore)) {
303 type_walk_s2s_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
306 if (type_visited((type *)tore)) return;
313 switch (get_kind(tore)) {
316 type *tp = (type *)tore;
317 mark_type_visited(tp);
318 switch (get_type_tpop_code(tp)) {
321 n = get_class_n_supertypes(tp);
322 for (i = 0; i < n; ++i) {
323 type_walk_s2s_2((type_or_ent *)get_class_supertype(tp, i), pre,
326 /* execute pre method */
329 tp = skip_tid((type*)tore);
331 n = get_class_n_subtypes(tp);
332 for (i = 0; i < n; ++i) {
333 type_walk_s2s_2((type_or_ent *)get_class_subtype(tp, i), pre,
337 /* execute post method */
346 case tpo_enumeration:
353 printf(" *** Faulty type! \n");
356 } break; /* end case k_type */
361 printf(" *** Faulty type or entity! \n");
367 void type_walk_super2sub(
368 void (*pre)(type_or_ent*, void*),
369 void (*post)(type_or_ent*, void*),
372 int i, n_types = get_irp_n_types();
375 inc_master_type_visited();
376 type_walk_s2s_2((type_or_ent *)get_glob_type(), pre, post, env);
377 for (i = 0; i < n_types; ++i) {
378 tp = get_irp_type(i);
379 type_walk_s2s_2((type_or_ent *)tp, pre, post, env);
383 /*****************************************************************************/
386 type_walk_super_2(type_or_ent *tore,
387 void (*pre)(type_or_ent*, void*),
388 void (*post)(type_or_ent*, void*),
394 switch (get_kind(tore)) {
396 if (entity_visited((entity *)tore)) return;
399 if (type_id == get_type_tpop((type*)tore)) {
400 type_walk_super_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
403 if (type_visited((type *)tore)) return;
410 switch (get_kind(tore)) {
413 type *tp = (type *)tore;
414 mark_type_visited(tp);
415 switch (get_type_tpop_code(tp)) {
418 /* execute pre method */
421 tp = skip_tid((type*)tore);
423 n = get_class_n_supertypes(tp);
424 for (i = 0; i < n; ++i) {
425 type_walk_super_2((type_or_ent *)get_class_supertype(tp, i), pre,
429 /* execute post method */
438 case tpo_enumeration:
445 printf(" *** Faulty type! \n");
448 } break; /* end case k_type */
453 printf(" *** Faulty type or entity! \n");
459 void type_walk_super(
460 void (*pre)(type_or_ent*, void*),
461 void (*post)(type_or_ent*, void*),
463 int i, n_types = get_irp_n_types();
466 inc_master_type_visited();
467 type_walk_super_2((type_or_ent *)get_glob_type(), pre, post, env);
468 for (i = 0; i < n_types; ++i) {
469 tp = get_irp_type(i);
470 type_walk_super_2((type_or_ent *)tp, pre, post, env);
474 /*****************************************************************************/
478 class_walk_s2s_2(type *tp,
479 void (*pre)(type*, void*),
480 void (*post)(type*, void*),
486 if (type_visited(tp)) return;
488 assert(is_Class_type(tp));
489 /* Assure all supertypes are visited before */
490 n = get_class_n_supertypes(tp);
491 for (i = 0; i < n; ++i) {
492 if (type_not_visited(get_class_supertype(tp, i)))
496 mark_type_visited(tp);
498 /* execute pre method */
503 n = get_class_n_subtypes(tp);
504 for (i = 0; i < n; ++i) {
505 class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
507 /* execute post method */
514 void class_walk_super2sub(
515 void (*pre)(type*, void*),
516 void (*post)(type*, void*),
519 int i, n_types = get_irp_n_types();
522 inc_master_type_visited();
523 for (i = 0; i < n_types; i++) {
524 tp = get_irp_type(i);
525 if (is_Class_type(tp) &&
526 (get_class_n_supertypes(tp) == 0) &&
527 type_not_visited(tp)) {
528 assert(! is_frame_type(tp));
529 assert(tp != get_glob_type());
530 class_walk_s2s_2(tp, pre, post, env);
536 /* Walks over all entities in the type */
537 void walk_types_entities(
539 void (*doit)(entity*, void*),
544 switch (get_type_tpop_code(tp)) {
546 n = get_class_n_members(tp);
547 for (i = 0; i < n; ++i)
548 doit(get_class_member(tp, i), env);
551 n = get_struct_n_members(tp);
552 for (i = 0; i < n; ++i)
553 doit(get_struct_member(tp, i), env);
556 n = get_union_n_members(tp);
557 for (i = 0; i < n; ++i)
558 doit(get_union_member(tp, i), env);
561 doit(get_array_element_entity(tp), env);
564 case tpo_enumeration: