2 * Copyright (C) 1995-2007 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"
51 * The walker environment
53 typedef struct type_walk_env {
54 type_walk_func *pre; /**< Pre-walker function */
55 type_walk_func *post; /**< Post-walker function */
56 void *env; /**< environment for walker functions */
59 /* a walker for irn's */
60 static void irn_type_walker(
61 ir_node *node, type_walk_func *pre, type_walk_func *post, void *env);
64 * Main walker: walks over all used types/entities of a
67 static void do_type_walk(type_or_ent *tore,
72 int i, n_types, n_mem;
73 ir_entity *ent = NULL;
78 switch (get_kind(tore)) {
80 ent = (ir_entity *)tore;
81 if (entity_visited(ent)) return;
84 tp = skip_tid((ir_type *)tore);
85 if (type_visited(tp)) return;
91 /* execute pre method */
96 switch (get_kind(tore)) {
98 mark_entity_visited(ent);
99 do_type_walk((type_or_ent *)get_entity_owner(ent), pre, post, env);
100 do_type_walk((type_or_ent *)get_entity_type(ent), pre, post, env);
102 if (get_entity_variability(ent) != variability_uninitialized) {
103 /* walk over the value types */
104 if (is_atomic_entity(ent)) {
105 n = get_atomic_ent_value(ent);
106 irn_type_walker(n, pre, post, env);
108 n_mem = get_compound_ent_n_values(ent);
109 for (i = 0; i < n_mem; ++i) {
110 n = get_compound_ent_value(ent, i);
111 irn_type_walker(n, pre, post, env);
117 mark_type_visited(tp);
118 switch (get_type_tpop_code(tp)) {
121 n_types = get_class_n_supertypes(tp);
122 for (i = 0; i < n_types; ++i)
123 do_type_walk((type_or_ent *)get_class_supertype(tp, i), pre, post, env);
125 n_mem = get_class_n_members(tp);
126 for (i = 0; i < n_mem; ++i)
127 do_type_walk((type_or_ent *)get_class_member(tp, i), pre, post, env);
129 n_types = get_class_n_subtypes(tp);
130 for (i = 0; i < n_types; ++i)
131 do_type_walk((type_or_ent *)get_class_subtype(tp, i), pre, post, env);
135 n_mem = get_struct_n_members(tp);
136 for (i = 0; i < n_mem; ++i)
137 do_type_walk((type_or_ent *)get_struct_member(tp, i), pre, post, env);
141 n_mem = get_method_n_params(tp);
142 for (i = 0; i < n_mem; ++i)
143 do_type_walk((type_or_ent *)get_method_param_type(tp, i), pre, post, env);
145 n_mem = get_method_n_ress(tp);
146 for (i = 0; i < n_mem; ++i)
147 do_type_walk((type_or_ent *)get_method_res_type(tp, i), pre, post, env);
151 n_mem = get_union_n_members(tp);
152 for (i = 0; i < n_mem; ++i)
153 do_type_walk((type_or_ent *)get_union_member(tp, i), pre, post, env);
157 do_type_walk((type_or_ent *)get_array_element_type(tp),
159 do_type_walk((type_or_ent *)get_array_element_entity(tp),
163 case tpo_enumeration:
168 do_type_walk((type_or_ent *)get_pointer_points_to_type(tp),
179 assert(0 && "Faulty type");
182 break; /* end case k_type */
185 printf(" *** Faulty type or entity! \n");
189 /* execute post method */
196 /** Check whether node contains types or entities as an attribute.
197 If so start a walk over that information. */
198 static void irn_type_walker(
199 ir_node *node, type_walk_func *pre, type_walk_func *post, void *env)
206 ent = get_irn_entity_attr(node);
208 do_type_walk((type_or_ent *)ent, pre, post, env);
209 tp = get_irn_type_attr(node);
211 do_type_walk((type_or_ent *)tp, pre, post, env);
214 /** Check whether node contains types or entities as an attribute.
215 If so start a walk over that information. */
216 static void start_type_walk(ir_node *node, void *ctx) {
217 type_walk_env *env = ctx;
219 type_walk_func *post;
226 irn_type_walker(node, pre, post, envi);
229 /* walker: walks over all types */
230 void type_walk(type_walk_func *pre, type_walk_func *post, void *env) {
231 int i, n_types = get_irp_n_types();
233 inc_master_type_visited();
234 for (i = 0; i < n_types; ++i) {
235 do_type_walk((type_or_ent *)get_irp_type(i), pre, post, env);
237 do_type_walk((type_or_ent *)get_glob_type(), pre, post, env);
240 void type_walk_irg(ir_graph *irg,
242 type_walk_func *post,
245 ir_graph *rem = current_ir_graph;
246 /* this is needed to pass the parameters to the walker that actually
247 walks the type information */
248 type_walk_env type_env;
251 type_env.post = post;
254 current_ir_graph = irg;
256 /* We walk over the irg to find all irnodes that contain an attribute
257 with type information. If we find one we call a type walker to
258 touch the reachable type information.
259 The same type can be referenced by several irnodes. To avoid
260 repeated visits of the same type node we must decrease the
261 type visited flag for each walk. This is done in start_type_walk().
262 Here we initially increase the flag. We only call do_type_walk that does
263 not increase the flag.
265 inc_master_type_visited();
266 irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);
268 do_type_walk((type_or_ent *)get_irg_entity(irg), pre, post, env);
270 do_type_walk((type_or_ent *)get_irg_frame_type(irg), pre, post, env);
272 current_ir_graph = rem;
276 static void type_walk_s2s_2(type_or_ent *tore,
278 type_walk_func *post,
284 switch (get_kind(tore)) {
286 if (entity_visited((ir_entity *)tore)) return;
289 if (type_id == get_type_tpop((ir_type*)tore)) {
290 type_walk_s2s_2((type_or_ent *)skip_tid((ir_type *)tore), pre, post, env);
293 if (type_visited((ir_type *)tore)) return;
300 switch (get_kind(tore)) {
303 ir_type *tp = (ir_type *)tore;
304 mark_type_visited(tp);
305 switch (get_type_tpop_code(tp)) {
308 n = get_class_n_supertypes(tp);
309 for (i = 0; i < n; ++i) {
310 type_walk_s2s_2((type_or_ent *)get_class_supertype(tp, i), pre, post, env);
312 /* execute pre method */
315 tp = skip_tid((ir_type*)tore);
317 n = get_class_n_subtypes(tp);
318 for (i = 0; i < n; ++i) {
319 type_walk_s2s_2((type_or_ent *)get_class_subtype(tp, i), pre, post, env);
322 /* execute post method */
331 case tpo_enumeration:
338 printf(" *** Faulty type! \n");
341 } break; /* end case k_type */
346 printf(" *** Faulty type or entity! \n");
352 void type_walk_super2sub(type_walk_func *pre,
353 type_walk_func *post,
356 int i, n_types = get_irp_n_types();
359 inc_master_type_visited();
360 type_walk_s2s_2((type_or_ent *)get_glob_type(), pre, post, env);
361 for (i = 0; i < n_types; ++i) {
362 tp = get_irp_type(i);
363 type_walk_s2s_2((type_or_ent *)tp, pre, post, env);
367 /*****************************************************************************/
370 type_walk_super_2(type_or_ent *tore,
372 type_walk_func *post,
377 switch (get_kind(tore)) {
379 if (entity_visited((ir_entity *)tore)) return;
382 if (type_id == get_type_tpop((ir_type*)tore)) {
383 type_walk_super_2((type_or_ent *)skip_tid((ir_type *)tore), pre, post, env);
386 if (type_visited((ir_type *)tore)) return;
393 switch (get_kind(tore)) {
396 ir_type *tp = (ir_type *)tore;
397 mark_type_visited(tp);
398 switch (get_type_tpop_code(tp)) {
401 /* execute pre method */
404 tp = skip_tid((ir_type*)tore);
406 n = get_class_n_supertypes(tp);
407 for (i = 0; i < n; ++i) {
408 type_walk_super_2((type_or_ent *)get_class_supertype(tp, i), pre,
412 /* execute post method */
421 case tpo_enumeration:
428 printf(" *** Faulty type! \n");
431 } break; /* end case k_type */
436 printf(" *** Faulty type or entity! \n");
442 void type_walk_super(type_walk_func *pre,
443 type_walk_func *post,
445 int i, n_types = get_irp_n_types();
448 inc_master_type_visited();
449 type_walk_super_2((type_or_ent *)get_glob_type(), pre, post, env);
450 for (i = 0; i < n_types; ++i) {
451 tp = get_irp_type(i);
452 type_walk_super_2((type_or_ent *)tp, pre, post, env);
456 /*****************************************************************************/
460 class_walk_s2s_2(ir_type *tp,
461 class_walk_func *pre,
462 class_walk_func *post,
468 if (type_visited(tp)) return;
470 assert(is_Class_type(tp));
471 /* Assure all supertypes are visited before */
472 n = get_class_n_supertypes(tp);
473 for (i = 0; i < n; ++i) {
474 if (type_not_visited(get_class_supertype(tp, i)))
478 mark_type_visited(tp);
480 /* execute pre method */
485 n = get_class_n_subtypes(tp);
486 for (i = 0; i < n; ++i) {
487 class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
489 /* execute post method */
496 void class_walk_super2sub(class_walk_func *pre,
497 class_walk_func *post,
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(ir_type *tp,
519 entity_walk_func *doit,
524 switch (get_type_tpop_code(tp)) {
526 n = get_class_n_members(tp);
527 for (i = 0; i < n; ++i)
528 doit(get_class_member(tp, i), env);
531 n = get_struct_n_members(tp);
532 for (i = 0; i < n; ++i)
533 doit(get_struct_member(tp, i), env);
536 n = get_union_n_members(tp);
537 for (i = 0; i < n; ++i)
538 doit(get_union_member(tp, i), env);
541 doit(get_array_element_entity(tp), env);
544 case tpo_enumeration: