2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Functionality to modify the type graph.
23 * @author Goetz Lindenmaier
27 * Traverse the type information. The walker walks the whole ir graph
28 * to find the distinct type trees in the type graph forest.
29 * - execute the pre function before recursion
30 * - execute the post function after recursion
46 #include "irgraph_t.h"
52 * The walker environment
54 typedef struct type_walk_env {
55 type_walk_func *pre; /**< Pre-walker function */
56 type_walk_func *post; /**< Post-walker function */
57 void *env; /**< environment for walker functions */
60 /* a walker for irn's */
61 static void irn_type_walker(
62 ir_node *node, type_walk_func *pre, type_walk_func *post, void *env);
64 static void walk_initializer(ir_initializer_t *initializer,
65 type_walk_func *pre, type_walk_func *post,
68 switch(initializer->kind) {
69 case IR_INITIALIZER_CONST:
70 irn_type_walker(initializer->consti.value, pre, post, env);
72 case IR_INITIALIZER_TARVAL:
73 case IR_INITIALIZER_NULL:
76 case IR_INITIALIZER_COMPOUND: {
78 for(i = 0; i < initializer->compound.n_initializers; ++i) {
79 ir_initializer_t *subinitializer
80 = initializer->compound.initializers[i];
81 walk_initializer(subinitializer, pre, post, env);
86 panic("invalid initializer found");
90 * Main walker: walks over all used types/entities of a
93 static void do_type_walk(type_or_ent tore,
98 int i, n_types, n_mem;
99 ir_entity *ent = NULL;
105 switch (get_kind(tore.ent)) {
108 if (entity_visited(ent))
112 tp = skip_tid(tore.typ);
113 if (type_visited(tp))
120 /* execute pre method */
125 switch (get_kind(tore.ent)) {
127 mark_entity_visited(ent);
128 cont.typ = get_entity_owner(ent);
129 do_type_walk(cont, pre, post, env);
130 cont.typ = get_entity_type(ent);
131 do_type_walk(cont, pre, post, env);
133 if (get_entity_variability(ent) != variability_uninitialized) {
134 /* walk over the value types */
135 if (ent->has_initializer) {
136 walk_initializer(ent->attr.initializer, pre, post, env);
137 } else if (is_atomic_entity(ent)) {
138 n = get_atomic_ent_value(ent);
139 irn_type_walker(n, pre, post, env);
141 n_mem = get_compound_ent_n_values(ent);
142 for (i = 0; i < n_mem; ++i) {
143 n = get_compound_ent_value(ent, i);
144 irn_type_walker(n, pre, post, env);
150 mark_type_visited(tp);
151 switch (get_type_tpop_code(tp)) {
154 n_types = get_class_n_supertypes(tp);
155 for (i = 0; i < n_types; ++i) {
156 cont.typ = get_class_supertype(tp, i);
157 do_type_walk(cont, pre, post, env);
159 n_mem = get_class_n_members(tp);
160 for (i = 0; i < n_mem; ++i) {
161 cont.ent = get_class_member(tp, i);
162 do_type_walk(cont, pre, post, env);
164 n_types = get_class_n_subtypes(tp);
165 for (i = 0; i < n_types; ++i) {
166 cont.typ = get_class_subtype(tp, i);
167 do_type_walk(cont, pre, post, env);
172 n_mem = get_struct_n_members(tp);
173 for (i = 0; i < n_mem; ++i) {
174 cont.ent = get_struct_member(tp, i);
175 do_type_walk(cont, pre, post, env);
180 n_mem = get_method_n_params(tp);
181 for (i = 0; i < n_mem; ++i) {
182 cont.typ = get_method_param_type(tp, i);
183 do_type_walk(cont, pre, post, env);
185 n_mem = get_method_n_ress(tp);
186 for (i = 0; i < n_mem; ++i) {
187 cont.typ = get_method_res_type(tp, i);
188 do_type_walk(cont, pre, post, env);
193 n_mem = get_union_n_members(tp);
194 for (i = 0; i < n_mem; ++i) {
195 cont.ent = get_union_member(tp, i);
196 do_type_walk(cont, pre, post, env);
201 cont.typ = get_array_element_type(tp);
202 do_type_walk(cont, pre, post, env);
203 cont.ent = get_array_element_entity(tp);
204 do_type_walk(cont, pre, post, env);
207 case tpo_enumeration:
212 cont.typ = get_pointer_points_to_type(tp);
213 do_type_walk(cont, pre, post, env);
223 assert(0 && "Faulty type");
226 break; /* end case k_type */
229 printf(" *** Faulty type or entity! \n");
233 /* execute post method */
238 /** Check whether node contains types or entities as an attribute.
239 If so start a walk over that information. */
240 static void irn_type_walker(
241 ir_node *node, type_walk_func *pre, type_walk_func *post, void *env)
247 cont.ent = get_irn_entity_attr(node);
249 do_type_walk(cont, pre, post, env);
250 cont.typ = get_irn_type_attr(node);
252 do_type_walk(cont, pre, post, env);
255 /** Check whether node contains types or entities as an attribute.
256 If so start a walk over that information. */
257 static void start_type_walk(ir_node *node, void *ctx) {
258 type_walk_env *env = ctx;
260 type_walk_func *post;
267 irn_type_walker(node, pre, post, envi);
270 /* walker: walks over all types */
271 void type_walk(type_walk_func *pre, type_walk_func *post, void *env) {
272 int i, n_types = get_irp_n_types();
275 inc_master_type_visited();
276 for (i = 0; i < n_types; ++i) {
277 cont.typ = get_irp_type(i);
278 do_type_walk(cont, pre, post, env);
280 cont.typ = get_glob_type();
281 do_type_walk(cont, pre, post, env);
284 void type_walk_irg(ir_graph *irg,
286 type_walk_func *post,
289 ir_graph *rem = current_ir_graph;
290 /* this is needed to pass the parameters to the walker that actually
291 walks the type information */
292 type_walk_env type_env;
296 type_env.post = post;
299 current_ir_graph = irg;
301 /* We walk over the irg to find all IR-nodes that contain an attribute
302 with type information. If we find one we call a type walker to
303 touch the reachable type information.
304 The same type can be referenced by several IR-nodes. To avoid
305 repeated visits of the same type node we must decrease the
306 type visited flag for each walk. This is done in start_type_walk().
307 Here we initially increase the flag. We only call do_type_walk that does
308 not increase the flag.
310 inc_master_type_visited();
311 irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);
313 cont.ent = get_irg_entity(irg);
314 do_type_walk(cont, pre, post, env);
316 cont.typ = get_irg_frame_type(irg);
317 do_type_walk(cont, pre, post, env);
319 current_ir_graph = rem;
322 static void type_walk_s2s_2(type_or_ent tore,
324 type_walk_func *post,
331 switch (get_kind(tore.ent)) {
333 if (entity_visited(tore.ent)) return;
336 if (type_id == get_type_tpop(tore.typ)) {
337 cont.typ = skip_tid(tore.typ);
338 type_walk_s2s_2(cont, pre, post, env);
341 if (type_visited(tore.typ)) return;
348 switch (get_kind(tore.typ)) {
351 ir_type *tp = tore.typ;
352 mark_type_visited(tp);
353 switch (get_type_tpop_code(tp)) {
356 n = get_class_n_supertypes(tp);
357 for (i = 0; i < n; ++i) {
358 cont.typ = get_class_supertype(tp, i);
359 type_walk_s2s_2(cont, pre, post, env);
361 /* execute pre method */
366 n = get_class_n_subtypes(tp);
367 for (i = 0; i < n; ++i) {
368 cont.typ = get_class_subtype(tp, i);
369 type_walk_s2s_2(cont, pre, post, env);
372 /* execute post method */
381 case tpo_enumeration:
388 printf(" *** Faulty type! \n");
391 } break; /* end case k_type */
396 printf(" *** Faulty type or entity! \n");
401 void type_walk_super2sub(type_walk_func *pre,
402 type_walk_func *post,
406 int i, n_types = get_irp_n_types();
408 inc_master_type_visited();
409 cont.typ = get_glob_type();
410 type_walk_s2s_2(cont, pre, post, env);
411 for (i = 0; i < n_types; ++i) {
412 cont.typ = get_irp_type(i);
413 type_walk_s2s_2(cont, pre, post, env);
417 /*****************************************************************************/
420 type_walk_super_2(type_or_ent tore,
422 type_walk_func *post,
428 switch (get_kind(tore.ent)) {
430 if (entity_visited(tore.ent))
434 if (type_id == get_type_tpop(tore.typ)) {
435 cont.typ = skip_tid(tore.typ);
436 type_walk_super_2(cont, pre, post, env);
439 if (type_visited(tore.typ))
447 switch (get_kind(tore.typ)) {
450 ir_type *tp = tore.typ;
451 mark_type_visited(tp);
452 switch (get_type_tpop_code(tp)) {
455 /* execute pre method */
460 n = get_class_n_supertypes(tp);
461 for (i = 0; i < n; ++i) {
462 cont.typ = get_class_supertype(tp, i);
463 type_walk_super_2(cont, pre, post, env);
466 /* execute post method */
475 case tpo_enumeration:
482 printf(" *** Faulty type! \n");
485 } break; /* end case k_type */
490 printf(" *** Faulty type or entity! \n");
495 void type_walk_super(type_walk_func *pre,
496 type_walk_func *post,
498 int i, n_types = get_irp_n_types();
501 inc_master_type_visited();
502 cont.typ = get_glob_type();
503 type_walk_super_2(cont, pre, post, env);
504 for (i = 0; i < n_types; ++i) {
505 cont.typ = get_irp_type(i);
506 type_walk_super_2(cont, pre, post, env);
510 /*****************************************************************************/
514 class_walk_s2s_2(ir_type *tp,
515 class_walk_func *pre,
516 class_walk_func *post,
522 if (type_visited(tp)) return;
524 assert(is_Class_type(tp));
525 /* Assure all supertypes are visited before */
526 n = get_class_n_supertypes(tp);
527 for (i = 0; i < n; ++i) {
528 if (type_not_visited(get_class_supertype(tp, i)))
532 mark_type_visited(tp);
534 /* execute pre method */
539 n = get_class_n_subtypes(tp);
540 for (i = 0; i < n; ++i) {
541 class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
543 /* execute post method */
548 void class_walk_super2sub(class_walk_func *pre,
549 class_walk_func *post,
552 int i, n_types = get_irp_n_types();
555 inc_master_type_visited();
556 for (i = 0; i < n_types; i++) {
557 tp = get_irp_type(i);
558 if (is_Class_type(tp) &&
559 (get_class_n_supertypes(tp) == 0) &&
560 type_not_visited(tp)) {
561 assert(! is_frame_type(tp));
562 assert(tp != get_glob_type());
563 class_walk_s2s_2(tp, pre, post, env);
569 /* Walks over all entities in the type */
570 void walk_types_entities(ir_type *tp,
571 entity_walk_func *doit,
576 switch (get_type_tpop_code(tp)) {
578 n = get_class_n_members(tp);
579 for (i = 0; i < n; ++i)
580 doit(get_class_member(tp, i), env);
583 n = get_struct_n_members(tp);
584 for (i = 0; i < n; ++i)
585 doit(get_struct_member(tp, i), env);
588 n = get_union_n_members(tp);
589 for (i = 0; i < n; ++i)
590 doit(get_union_member(tp, i), env);
593 doit(get_array_element_entity(tp), env);
596 case tpo_enumeration: