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
45 #include "type_or_entity.h"
49 #include "irgraph_t.h"
54 * The walker environment
56 typedef struct type_walk_env {
57 type_walk_func *pre; /**< Pre-walker function */
58 type_walk_func *post; /**< Post-walker function */
59 void *env; /**< environment for walker functions */
62 /* a walker for irn's */
63 static void irn_type_walker(
64 ir_node *node, type_walk_func *pre, type_walk_func *post, void *env);
67 * Main walker: walks over all used types/entities of a
70 static void do_type_walk(type_or_ent *tore,
75 int i, n_types, n_mem;
76 ir_entity *ent = NULL;
81 switch (get_kind(tore)) {
83 ent = (ir_entity *)tore;
84 if (entity_visited(ent)) return;
87 tp = skip_tid((ir_type *)tore);
88 if (type_visited(tp)) return;
94 /* execute pre method */
99 switch (get_kind(tore)) {
101 mark_entity_visited(ent);
102 do_type_walk((type_or_ent *)get_entity_owner(ent), pre, post, env);
103 do_type_walk((type_or_ent *)get_entity_type(ent), pre, post, env);
105 if (get_entity_variability(ent) != variability_uninitialized) {
106 /* walk over the value types */
107 if (is_atomic_entity(ent)) {
108 n = get_atomic_ent_value(ent);
109 irn_type_walker(n, pre, post, env);
111 n_mem = get_compound_ent_n_values(ent);
112 for (i = 0; i < n_mem; ++i) {
113 n = get_compound_ent_value(ent, i);
114 irn_type_walker(n, pre, post, env);
120 mark_type_visited(tp);
121 switch (get_type_tpop_code(tp)) {
124 n_types = get_class_n_supertypes(tp);
125 for (i = 0; i < n_types; ++i)
126 do_type_walk((type_or_ent *)get_class_supertype(tp, i), pre, post, env);
128 n_mem = get_class_n_members(tp);
129 for (i = 0; i < n_mem; ++i)
130 do_type_walk((type_or_ent *)get_class_member(tp, i), pre, post, env);
132 n_types = get_class_n_subtypes(tp);
133 for (i = 0; i < n_types; ++i)
134 do_type_walk((type_or_ent *)get_class_subtype(tp, i), pre, post, env);
138 n_mem = get_struct_n_members(tp);
139 for (i = 0; i < n_mem; ++i)
140 do_type_walk((type_or_ent *)get_struct_member(tp, i), pre, post, env);
144 n_mem = get_method_n_params(tp);
145 for (i = 0; i < n_mem; ++i)
146 do_type_walk((type_or_ent *)get_method_param_type(tp, i), pre, post, env);
148 n_mem = get_method_n_ress(tp);
149 for (i = 0; i < n_mem; ++i)
150 do_type_walk((type_or_ent *)get_method_res_type(tp, i), pre, post, env);
154 n_mem = get_union_n_members(tp);
155 for (i = 0; i < n_mem; ++i)
156 do_type_walk((type_or_ent *)get_union_member(tp, i), pre, post, env);
160 do_type_walk((type_or_ent *)get_array_element_type(tp),
162 do_type_walk((type_or_ent *)get_array_element_entity(tp),
166 case tpo_enumeration:
171 do_type_walk((type_or_ent *)get_pointer_points_to_type(tp),
182 assert(0 && "Faulty type");
185 break; /* end case k_type */
188 printf(" *** Faulty type or entity! \n");
192 /* execute post method */
199 /** Check whether node contains types or entities as an attribute.
200 If so start a walk over that information. */
201 static void irn_type_walker(
202 ir_node *node, type_walk_func *pre, type_walk_func *post, void *env)
209 ent = get_irn_entity_attr(node);
211 do_type_walk((type_or_ent *)ent, pre, post, env);
212 tp = get_irn_type_attr(node);
214 do_type_walk((type_or_ent *)tp, pre, post, env);
217 /** Check whether node contains types or entities as an attribute.
218 If so start a walk over that information. */
219 static void start_type_walk(ir_node *node, void *ctx) {
220 type_walk_env *env = ctx;
222 type_walk_func *post;
229 irn_type_walker(node, pre, post, envi);
232 /* walker: walks over all types */
233 void type_walk(type_walk_func *pre, type_walk_func *post, void *env) {
234 int i, n_types = get_irp_n_types();
236 inc_master_type_visited();
237 for (i = 0; i < n_types; ++i) {
238 do_type_walk((type_or_ent *)get_irp_type(i), pre, post, env);
240 do_type_walk((type_or_ent *)get_glob_type(), pre, post, env);
243 void type_walk_irg(ir_graph *irg,
245 type_walk_func *post,
248 ir_graph *rem = current_ir_graph;
249 /* this is needed to pass the parameters to the walker that actually
250 walks the type information */
251 type_walk_env type_env;
254 type_env.post = post;
257 current_ir_graph = irg;
259 /* We walk over the irg to find all irnodes that contain an attribute
260 with type information. If we find one we call a type walker to
261 touch the reachable type information.
262 The same type can be referenced by several irnodes. To avoid
263 repeated visits of the same type node we must decrease the
264 type visited flag for each walk. This is done in start_type_walk().
265 Here we initially increase the flag. We only call do_type_walk that does
266 not increase the flag.
268 inc_master_type_visited();
269 irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);
271 do_type_walk((type_or_ent *)get_irg_entity(irg), pre, post, env);
273 do_type_walk((type_or_ent *)get_irg_frame_type(irg), pre, post, env);
275 current_ir_graph = rem;
279 static void type_walk_s2s_2(type_or_ent *tore,
281 type_walk_func *post,
287 switch (get_kind(tore)) {
289 if (entity_visited((ir_entity *)tore)) return;
292 if (type_id == get_type_tpop((ir_type*)tore)) {
293 type_walk_s2s_2((type_or_ent *)skip_tid((ir_type *)tore), pre, post, env);
296 if (type_visited((ir_type *)tore)) return;
303 switch (get_kind(tore)) {
306 ir_type *tp = (ir_type *)tore;
307 mark_type_visited(tp);
308 switch (get_type_tpop_code(tp)) {
311 n = get_class_n_supertypes(tp);
312 for (i = 0; i < n; ++i) {
313 type_walk_s2s_2((type_or_ent *)get_class_supertype(tp, i), pre, post, env);
315 /* execute pre method */
318 tp = skip_tid((ir_type*)tore);
320 n = get_class_n_subtypes(tp);
321 for (i = 0; i < n; ++i) {
322 type_walk_s2s_2((type_or_ent *)get_class_subtype(tp, i), pre, post, env);
325 /* execute post method */
334 case tpo_enumeration:
341 printf(" *** Faulty type! \n");
344 } break; /* end case k_type */
349 printf(" *** Faulty type or entity! \n");
355 void type_walk_super2sub(type_walk_func *pre,
356 type_walk_func *post,
359 int i, n_types = get_irp_n_types();
362 inc_master_type_visited();
363 type_walk_s2s_2((type_or_ent *)get_glob_type(), pre, post, env);
364 for (i = 0; i < n_types; ++i) {
365 tp = get_irp_type(i);
366 type_walk_s2s_2((type_or_ent *)tp, pre, post, env);
370 /*****************************************************************************/
373 type_walk_super_2(type_or_ent *tore,
375 type_walk_func *post,
380 switch (get_kind(tore)) {
382 if (entity_visited((ir_entity *)tore)) return;
385 if (type_id == get_type_tpop((ir_type*)tore)) {
386 type_walk_super_2((type_or_ent *)skip_tid((ir_type *)tore), pre, post, env);
389 if (type_visited((ir_type *)tore)) return;
396 switch (get_kind(tore)) {
399 ir_type *tp = (ir_type *)tore;
400 mark_type_visited(tp);
401 switch (get_type_tpop_code(tp)) {
404 /* execute pre method */
407 tp = skip_tid((ir_type*)tore);
409 n = get_class_n_supertypes(tp);
410 for (i = 0; i < n; ++i) {
411 type_walk_super_2((type_or_ent *)get_class_supertype(tp, i), pre,
415 /* execute post method */
424 case tpo_enumeration:
431 printf(" *** Faulty type! \n");
434 } break; /* end case k_type */
439 printf(" *** Faulty type or entity! \n");
445 void type_walk_super(type_walk_func *pre,
446 type_walk_func *post,
448 int i, n_types = get_irp_n_types();
451 inc_master_type_visited();
452 type_walk_super_2((type_or_ent *)get_glob_type(), pre, post, env);
453 for (i = 0; i < n_types; ++i) {
454 tp = get_irp_type(i);
455 type_walk_super_2((type_or_ent *)tp, pre, post, env);
459 /*****************************************************************************/
463 class_walk_s2s_2(ir_type *tp,
464 class_walk_func *pre,
465 class_walk_func *post,
471 if (type_visited(tp)) return;
473 assert(is_Class_type(tp));
474 /* Assure all supertypes are visited before */
475 n = get_class_n_supertypes(tp);
476 for (i = 0; i < n; ++i) {
477 if (type_not_visited(get_class_supertype(tp, i)))
481 mark_type_visited(tp);
483 /* execute pre method */
488 n = get_class_n_subtypes(tp);
489 for (i = 0; i < n; ++i) {
490 class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
492 /* execute post method */
499 void class_walk_super2sub(class_walk_func *pre,
500 class_walk_func *post,
503 int i, n_types = get_irp_n_types();
506 inc_master_type_visited();
507 for (i = 0; i < n_types; i++) {
508 tp = get_irp_type(i);
509 if (is_Class_type(tp) &&
510 (get_class_n_supertypes(tp) == 0) &&
511 type_not_visited(tp)) {
512 assert(! is_frame_type(tp));
513 assert(tp != get_glob_type());
514 class_walk_s2s_2(tp, pre, post, env);
520 /* Walks over all entities in the type */
521 void walk_types_entities(ir_type *tp,
522 entity_walk_func *doit,
527 switch (get_type_tpop_code(tp)) {
529 n = get_class_n_members(tp);
530 for (i = 0; i < n; ++i)
531 doit(get_class_member(tp, i), env);
534 n = get_struct_n_members(tp);
535 for (i = 0; i < n; ++i)
536 doit(get_struct_member(tp, i), env);
539 n = get_union_n_members(tp);
540 for (i = 0; i < n; ++i)
541 doit(get_union_member(tp, i), env);
544 doit(get_array_element_entity(tp), env);
547 case tpo_enumeration: