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,
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 for (i = 0; i < get_compound_ent_n_values(ent); ++i) {
103 n = get_compound_ent_value(ent, i);
104 irn_type_walker(n, pre, post, env);
110 mark_type_visited(tp);
111 switch (get_type_tpop_code(tp)) {
114 for (i = 0; i < get_class_n_supertypes(tp); i++)
115 do_type_walk((type_or_ent *)get_class_supertype(tp, i), pre, post, env);
116 for (i = 0; i < get_class_n_members(tp); i++)
117 do_type_walk((type_or_ent *)get_class_member(tp, i), pre, post, env);
118 for (i = 0; i < get_class_n_subtypes(tp); i++)
119 do_type_walk((type_or_ent *)get_class_subtype(tp, i), pre, post, env);
123 for (i = 0; i<get_struct_n_members(tp); i++)
124 do_type_walk((type_or_ent *)get_struct_member(tp, i), pre, post, env);
128 for (i = 0; i < get_method_n_params(tp); i++)
129 do_type_walk((type_or_ent *)get_method_param_type(tp, i), pre, post, env);
130 for (i = 0; i < get_method_n_ress(tp); i++)
131 do_type_walk((type_or_ent *)get_method_res_type(tp, i), pre, post, env);
135 for (i = 0; i < get_union_n_members(tp); i++)
136 do_type_walk((type_or_ent *)get_union_member(tp, i), pre, post, env);
140 do_type_walk((type_or_ent *)get_array_element_type(tp),
142 do_type_walk((type_or_ent *)get_array_element_entity(tp),
146 case tpo_enumeration:
151 do_type_walk((type_or_ent *)get_pointer_points_to_type(tp),
162 assert(0 && "Faulty type");
165 break; /* end case k_type */
168 printf(" *** Faulty type or entity! \n");
172 /* execute post method */
179 /** Check whether node contains types or entities as an attribute.
180 If so start a walk over that information. */
181 static void irn_type_walker(
182 ir_node *node, type_walk_func *pre, type_walk_func *post, void *env)
188 switch (get_irn_opcode(node)) { /* node label */
190 kind = get_SymConst_kind(node);
191 if (kind == symconst_type_tag || kind == symconst_size)
192 do_type_walk((type_or_ent *)get_SymConst_type(node), pre, post, env);
193 else if (kind == symconst_addr_ent)
194 do_type_walk((type_or_ent *)get_SymConst_entity(node), pre, post, env);
197 do_type_walk((type_or_ent *)get_Sel_entity(node), pre, post, env);
200 do_type_walk((type_or_ent *)get_Call_type(node), pre, post, env);
203 do_type_walk((type_or_ent *)get_Alloc_type(node), pre, post, env);
206 do_type_walk((type_or_ent *)get_Free_type(node), pre, post, env);
209 do_type_walk((type_or_ent *)get_Cast_type(node), pre, post, env);
216 /** Check whether node contains types or entities as an attribute.
217 If so start a walk over that information. */
218 static void start_type_walk(ir_node *node, void *ctx) {
219 type_walk_env *env = ctx;
221 type_walk_func *post;
228 irn_type_walker(node, pre, post, envi);
231 /* walker: walks over all types */
232 void type_walk(type_walk_func *pre, type_walk_func *post, void *env) {
233 int i, n_types = get_irp_n_types();
236 for (i = 0; i < n_types; i++) {
237 do_type_walk((type_or_ent *)get_irp_type(i), pre, post, env);
239 do_type_walk((type_or_ent *)get_glob_type(), pre, post, env);
242 void type_walk_irg (ir_graph *irg,
243 void (*pre)(type_or_ent*, void*),
244 void (*post)(type_or_ent*, void*),
247 ir_graph *rem = current_ir_graph;
248 /* this is needed to pass the parameters to the walker that actually
249 walks the type information */
250 type_walk_env type_env;
253 type_env.post = post;
256 current_ir_graph = irg;
258 /* We walk over the irg to find all irnodes that contain an attribute
259 with type information. If we find one we call a type walker to
260 touch the reachable type information.
261 The same type can be referenced by several irnodes. To avoid
262 repeated visits of the same type node we must decrease the
263 type visited flag for each walk. This is done in start_type_walk().
264 Here we initially increase the flag. We only call do_type_walk that does
265 not increase the flag.
267 inc_master_type_visited();
268 irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);
270 do_type_walk((type_or_ent *)get_irg_entity(irg), pre, post, env);
272 do_type_walk((type_or_ent *)get_irg_frame_type(irg), pre, post, env);
274 current_ir_graph = rem;
278 static void type_walk_s2s_2(type_or_ent *tore,
279 void (*pre)(type_or_ent*, void*),
280 void (*post)(type_or_ent*, void*),
286 switch (get_kind(tore)) {
288 if (((entity *)tore)->visit >= type_visited) return;
291 if(type_id == get_type_tpop((type*)tore)) {
292 type_walk_s2s_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
295 if (((type *)tore)->visit >= type_visited) return;
302 switch (get_kind(tore)) {
305 type *tp = (type *)tore;
306 mark_type_visited(tp);
307 switch (get_type_tpop_code(tp)) {
310 for (i = 0; i < get_class_n_supertypes(tp); i++) {
311 type_walk_s2s_2((type_or_ent *)get_class_supertype(tp, i), pre,
314 /* execute pre method */
317 tp = skip_tid((type*)tore);
319 for (i = 0; i < get_class_n_subtypes(tp); i++) {
320 type_walk_s2s_2((type_or_ent *)get_class_subtype(tp, i), pre,
324 /* execute post method */
333 case tpo_enumeration:
340 printf(" *** Faulty type! \n");
343 } break; /* end case k_type */
348 printf(" *** Faulty type or entity! \n");
354 void type_walk_super2sub(
355 void (*pre)(type_or_ent*, void*),
356 void (*post)(type_or_ent*, void*),
359 int i, n_types = get_irp_n_types();
362 type_walk_s2s_2((type_or_ent *)get_glob_type(), pre, post, env);
363 for (i = 0; i < n_types; i++) {
364 tp = get_irp_type(i);
365 type_walk_s2s_2((type_or_ent *)tp, pre, post, env);
369 /*****************************************************************************/
372 type_walk_super_2(type_or_ent *tore,
373 void (*pre)(type_or_ent*, void*),
374 void (*post)(type_or_ent*, void*),
380 switch (get_kind(tore)) {
382 if (((entity *)tore)->visit >= type_visited) return;
385 if(type_id == get_type_tpop((type*)tore)) {
386 type_walk_super_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
389 if (((type *)tore)->visit >= type_visited) return;
396 switch (get_kind(tore)) {
399 type *tp = (type *)tore;
400 mark_type_visited(tp);
401 switch (get_type_tpop_code(tp)) {
404 /* execute pre method */
407 tp = skip_tid((type*)tore);
409 for (i = 0; i < get_class_n_supertypes(tp); i++) {
410 type_walk_super_2((type_or_ent *)get_class_supertype(tp, i), pre,
414 /* execute post method */
423 case tpo_enumeration:
430 printf(" *** Faulty type! \n");
433 } break; /* end case k_type */
438 printf(" *** Faulty type or entity! \n");
444 void type_walk_super(
445 void (*pre)(type_or_ent*, void*),
446 void (*post)(type_or_ent*, void*),
448 int i, n_types = get_irp_n_types();
451 type_walk_super_2((type_or_ent *)get_glob_type(), pre, post, env);
452 for (i = 0; i < n_types; i++) {
453 tp = get_irp_type(i);
454 type_walk_super_2((type_or_ent *)tp, pre, post, env);
458 /*****************************************************************************/
462 class_walk_s2s_2(type *tp,
463 void (*pre)(type*, void*),
464 void (*post)(type*, void*),
470 if (tp->visit >= type_visited) return;
472 assert(is_Class_type(tp));
473 /* Assure all supertypes are visited before */
474 for (i=0; i < get_class_n_supertypes(tp); i++) {
475 if (get_type_visited(get_class_supertype(tp, i)) < type_visited)
479 mark_type_visited(tp);
481 /* execute pre method */
485 tp = skip_tid((type*)tp);
486 for (i=0; i<get_class_n_subtypes(tp); i++) {
487 class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
489 /* execute post method */
496 void class_walk_super2sub(
497 void (*pre)(type*, void*),
498 void (*post)(type*, void*),
501 int i, n_types = get_irp_n_types();
505 for (i = 0; i < n_types; i++) {
506 tp = get_irp_type(i);
507 if (is_Class_type(tp) &&
508 (get_class_n_supertypes(tp) == 0) &&
509 (tp->visit < type_visited)) {
510 assert(!is_frame_type(tp));
511 assert(tp != get_glob_type());
512 class_walk_s2s_2(tp, pre, post, env);
518 /* Walks over all entities in the type */
519 void walk_types_entities(
521 void (*doit)(entity*, void*),
525 switch(get_type_tpop_code(tp)) {
527 for (i=0; i<get_class_n_members(tp); i++)
528 doit(get_class_member(tp, i), env);
531 for (i=0; i<get_struct_n_members(tp); i++)
532 doit(get_struct_member(tp, i), env);
535 for (i = 0; i < get_union_n_members(tp); i++)
536 doit(get_union_member(tp, i), env);
539 doit(get_array_element_entity(tp), env);
542 case tpo_enumeration: