1 /*
2 * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
3 *
4 * This file is part of libFirm.
5 *
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.
10 *
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.
14 *
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
17 * PURPOSE.
18 */
19
20 /**
21 * @file typewalk.c
22 * @brief Functionality to modify the type graph.
23 * @author Goetz Lindenmaier
24 * @brief
25 *
26 * Traverse the type information. The walker walks the whole ir graph
27 * to find the distinct type trees in the type graph forest.
28 * - execute the pre function before recursion
29 * - execute the post function after recursion
30 */
31 #include "config.h"
32
33 #include <stdlib.h>
34 #include <stdio.h>
35
36 #include "entity_t.h"
37 #include "type_t.h"
38
39 #include "irprog_t.h"
40 #include "irgraph_t.h"
41 #include "irnode_t.h"
42 #include "irgwalk.h"
43 #include "error.h"
44 #include "ircons.h"
45
46 /**
47 * The walker environment
48 */
49 typedef struct type_walk_env {
50 type_walk_func *pre; /**< Pre-walker function */
51 type_walk_func *post; /**< Post-walker function */
52 void *env; /**< environment for walker functions */
53 } type_walk_env;
54
55 /* a walker for irn's */
56 static void irn_type_walker(
57 ir_node *node, type_walk_func *pre, type_walk_func *post, void *env);
58
walk_initializer(ir_initializer_t * initializer,type_walk_func * pre,type_walk_func * post,void * env)59 static void walk_initializer(ir_initializer_t *initializer,
60 type_walk_func *pre, type_walk_func *post,
61 void *env)
62 {
63 switch (initializer->kind) {
64 case IR_INITIALIZER_CONST:
65 irn_type_walker(initializer->consti.value, pre, post, env);
66 return;
67 case IR_INITIALIZER_TARVAL:
68 case IR_INITIALIZER_NULL:
69 return;
70
71 case IR_INITIALIZER_COMPOUND: {
72 size_t i;
73 for (i = 0; i < initializer->compound.n_initializers; ++i) {
74 ir_initializer_t *subinitializer
75 = initializer->compound.initializers[i];
76 walk_initializer(subinitializer, pre, post, env);
77 }
78 return;
79 }
80 }
81 panic("invalid initializer found");
82 }
83
84 /**
85 * Main walker: walks over all used types/entities of a
86 * type entity.
87 */
do_type_walk(type_or_ent tore,type_walk_func * pre,type_walk_func * post,void * env)88 static void do_type_walk(type_or_ent tore,
89 type_walk_func *pre,
90 type_walk_func *post,
91 void *env)
92 {
93 size_t i, n_types, n_mem;
94 ir_entity *ent = NULL;
95 ir_type *tp = NULL;
96 type_or_ent cont;
97
98 /* marked? */
99 switch (get_kind(tore.ent)) {
100 case k_entity:
101 ent = tore.ent;
102 if (entity_visited(ent))
103 return;
104 mark_entity_visited(ent);
105 break;
106 case k_type:
107 tp = tore.typ;
108 if (type_visited(tp))
109 return;
110 mark_type_visited(tp);
111 break;
112 default:
113 break;
114 }
115
116 /* execute pre method */
117 if (pre)
118 pre(tore, env);
119
120 /* iterate */
121 switch (get_kind(tore.ent)) {
122 case k_entity:
123 cont.typ = get_entity_owner(ent);
124 do_type_walk(cont, pre, post, env);
125 cont.typ = get_entity_type(ent);
126 do_type_walk(cont, pre, post, env);
127
128 /* walk over the value types */
129 if (ent->initializer != NULL) {
130 walk_initializer(ent->initializer, pre, post, env);
131 }
132 break;
133 case k_type:
134 switch (get_type_tpop_code(tp)) {
135 case tpo_class:
136 n_types = get_class_n_supertypes(tp);
137 for (i = 0; i < n_types; ++i) {
138 cont.typ = get_class_supertype(tp, i);
139 do_type_walk(cont, pre, post, env);
140 }
141 n_mem = get_class_n_members(tp);
142 for (i = 0; i < n_mem; ++i) {
143 cont.ent = get_class_member(tp, i);
144 do_type_walk(cont, pre, post, env);
145 }
146 n_types = get_class_n_subtypes(tp);
147 for (i = 0; i < n_types; ++i) {
148 cont.typ = get_class_subtype(tp, i);
149 do_type_walk(cont, pre, post, env);
150 }
151 break;
152
153 case tpo_struct:
154 n_mem = get_struct_n_members(tp);
155 for (i = 0; i < n_mem; ++i) {
156 cont.ent = get_struct_member(tp, i);
157 do_type_walk(cont, pre, post, env);
158 }
159 break;
160
161 case tpo_method:
162 n_mem = get_method_n_params(tp);
163 for (i = 0; i < n_mem; ++i) {
164 cont.typ = get_method_param_type(tp, i);
165 do_type_walk(cont, pre, post, env);
166 }
167 n_mem = get_method_n_ress(tp);
168 for (i = 0; i < n_mem; ++i) {
169 cont.typ = get_method_res_type(tp, i);
170 do_type_walk(cont, pre, post, env);
171 }
172 break;
173
174 case tpo_union:
175 n_mem = get_union_n_members(tp);
176 for (i = 0; i < n_mem; ++i) {
177 cont.ent = get_union_member(tp, i);
178 do_type_walk(cont, pre, post, env);
179 }
180 break;
181
182 case tpo_array:
183 cont.typ = get_array_element_type(tp);
184 do_type_walk(cont, pre, post, env);
185 cont.ent = get_array_element_entity(tp);
186 do_type_walk(cont, pre, post, env);
187 break;
188
189 case tpo_enumeration:
190 /* a leave */
191 break;
192
193 case tpo_pointer:
194 cont.typ = get_pointer_points_to_type(tp);
195 do_type_walk(cont, pre, post, env);
196 break;
197
198 case tpo_code:
199 case tpo_primitive:
200 case tpo_none:
201 case tpo_unknown:
202 /* a leave. */
203 break;
204 case tpo_uninitialized:
205 assert(0 && "Faulty type");
206 break;
207 }
208 break; /* end case k_type */
209
210 default:
211 printf(" *** Faulty type or entity! \n");
212 break;
213 }
214
215 /* execute post method */
216 if (post)
217 post(tore, env);
218 }
219
220 /** Check whether node contains types or entities as an attribute.
221 If so start a walk over that information. */
irn_type_walker(ir_node * node,type_walk_func * pre,type_walk_func * post,void * env)222 static void irn_type_walker(
223 ir_node *node, type_walk_func *pre, type_walk_func *post, void *env)
224 {
225 type_or_ent cont;
226
227 assert(node);
228
229 cont.ent = get_irn_entity_attr(node);
230 if (cont.ent)
231 do_type_walk(cont, pre, post, env);
232 cont.typ = get_irn_type_attr(node);
233 if (cont.typ)
234 do_type_walk(cont, pre, post, env);
235 }
236
237 /** Check whether node contains types or entities as an attribute.
238 If so start a walk over that information. */
start_type_walk(ir_node * node,void * ctx)239 static void start_type_walk(ir_node *node, void *ctx)
240 {
241 type_walk_env *env = (type_walk_env*)ctx;
242 type_walk_func *pre;
243 type_walk_func *post;
244 void *envi;
245
246 pre = env->pre;
247 post = env->post;
248 envi = env->env;
249
250 irn_type_walker(node, pre, post, envi);
251 }
252
type_walk(type_walk_func * pre,type_walk_func * post,void * env)253 void type_walk(type_walk_func *pre, type_walk_func *post, void *env)
254 {
255 size_t i, n_types = get_irp_n_types();
256 type_or_ent cont;
257
258 irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
259 inc_master_type_visited();
260 for (i = 0; i < n_types; ++i) {
261 cont.typ = get_irp_type(i);
262 do_type_walk(cont, pre, post, env);
263 }
264 cont.typ = get_glob_type();
265 do_type_walk(cont, pre, post, env);
266 irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
267 }
268
type_walk_irg(ir_graph * irg,type_walk_func * pre,type_walk_func * post,void * env)269 void type_walk_irg(ir_graph *irg,
270 type_walk_func *pre,
271 type_walk_func *post,
272 void *env)
273 {
274 ir_graph *rem = current_ir_graph;
275 /* this is needed to pass the parameters to the walker that actually
276 walks the type information */
277 type_walk_env type_env;
278 type_or_ent cont;
279
280 type_env.pre = pre;
281 type_env.post = post;
282 type_env.env = env;
283
284 current_ir_graph = irg;
285
286 /* We walk over the irg to find all IR-nodes that contain an attribute
287 with type information. If we find one we call a type walker to
288 touch the reachable type information.
289 The same type can be referenced by several IR-nodes. To avoid
290 repeated visits of the same type node we must decrease the
291 type visited flag for each walk. This is done in start_type_walk().
292 Here we initially increase the flag. We only call do_type_walk that does
293 not increase the flag.
294 */
295 irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
296 inc_master_type_visited();
297 irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);
298
299 cont.ent = get_irg_entity(irg);
300 do_type_walk(cont, pre, post, env);
301
302 cont.typ = get_irg_frame_type(irg);
303 do_type_walk(cont, pre, post, env);
304
305 current_ir_graph = rem;
306 irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
307 }
308
type_walk_s2s_2(type_or_ent tore,type_walk_func * pre,type_walk_func * post,void * env)309 static void type_walk_s2s_2(type_or_ent tore,
310 type_walk_func *pre,
311 type_walk_func *post,
312 void *env)
313 {
314 type_or_ent cont;
315
316 /* marked? */
317 switch (get_kind(tore.ent)) {
318 case k_entity:
319 if (entity_visited(tore.ent)) return;
320 break;
321 case k_type:
322 if (type_visited(tore.typ)) return;
323 break;
324 default:
325 break;
326 }
327
328 /* iterate */
329 switch (get_kind(tore.typ)) {
330 case k_type:
331 {
332 ir_type *tp = tore.typ;
333 mark_type_visited(tp);
334 switch (get_type_tpop_code(tp)) {
335 case tpo_class:
336 {
337 size_t i, n;
338
339 n = get_class_n_supertypes(tp);
340 for (i = 0; i < n; ++i) {
341 cont.typ = get_class_supertype(tp, i);
342 type_walk_s2s_2(cont, pre, post, env);
343 }
344 /* execute pre method */
345 if (pre)
346 pre(tore, env);
347
348 n = get_class_n_subtypes(tp);
349 for (i = 0; i < n; ++i) {
350 cont.typ = get_class_subtype(tp, i);
351 type_walk_s2s_2(cont, pre, post, env);
352 }
353
354 /* execute post method */
355 if (post)
356 post(tore, env);
357 }
358 break;
359 case tpo_struct:
360 case tpo_method:
361 case tpo_union:
362 case tpo_array:
363 case tpo_enumeration:
364 case tpo_pointer:
365 case tpo_primitive:
366 /* dont care */
367 break;
368 default:
369 printf(" *** Faulty type! \n");
370 break;
371 }
372 } break; /* end case k_type */
373 case k_entity:
374 /* don't care */
375 break;
376 default:
377 printf(" *** Faulty type or entity! \n");
378 break;
379 }
380 }
381
type_walk_super2sub(type_walk_func * pre,type_walk_func * post,void * env)382 void type_walk_super2sub(type_walk_func *pre,
383 type_walk_func *post,
384 void *env)
385 {
386 type_or_ent cont;
387 size_t i, n_types = get_irp_n_types();
388
389 irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
390 inc_master_type_visited();
391 cont.typ = get_glob_type();
392 type_walk_s2s_2(cont, pre, post, env);
393 for (i = 0; i < n_types; ++i) {
394 cont.typ = get_irp_type(i);
395 type_walk_s2s_2(cont, pre, post, env);
396 }
397 irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
398 }
399
400 /*****************************************************************************/
401
type_walk_super_2(type_or_ent tore,type_walk_func * pre,type_walk_func * post,void * env)402 static void type_walk_super_2(type_or_ent tore, type_walk_func *pre,
403 type_walk_func *post, void *env)
404 {
405 type_or_ent cont;
406
407 /* marked? */
408 switch (get_kind(tore.ent)) {
409 case k_entity:
410 if (entity_visited(tore.ent))
411 return;
412 break;
413 case k_type:
414 if (type_visited(tore.typ))
415 return;
416 break;
417 default:
418 break;
419 }
420
421 /* iterate */
422 switch (get_kind(tore.typ)) {
423 case k_type:
424 {
425 ir_type *tp = tore.typ;
426 mark_type_visited(tp);
427 switch (get_type_tpop_code(tp)) {
428 case tpo_class:
429 {
430 size_t i, n;
431
432 /* execute pre method */
433 if (pre)
434 pre(tore, env);
435
436 n = get_class_n_supertypes(tp);
437 for (i = 0; i < n; ++i) {
438 cont.typ = get_class_supertype(tp, i);
439 type_walk_super_2(cont, pre, post, env);
440 }
441
442 /* execute post method */
443 if (post)
444 post(tore, env);
445 }
446 break;
447 case tpo_struct:
448 case tpo_method:
449 case tpo_union:
450 case tpo_array:
451 case tpo_enumeration:
452 case tpo_pointer:
453 case tpo_primitive:
454 /* don't care */
455 break;
456 default:
457 printf(" *** Faulty type! \n");
458 break;
459 }
460 } break; /* end case k_type */
461 case k_entity:
462 /* don't care */
463 break;
464 default:
465 printf(" *** Faulty type or entity! \n");
466 break;
467 }
468 }
469
type_walk_super(type_walk_func * pre,type_walk_func * post,void * env)470 void type_walk_super(type_walk_func *pre, type_walk_func *post, void *env)
471 {
472 size_t i, n_types = get_irp_n_types();
473 type_or_ent cont;
474
475 irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
476 inc_master_type_visited();
477 cont.typ = get_glob_type();
478 type_walk_super_2(cont, pre, post, env);
479 for (i = 0; i < n_types; ++i) {
480 cont.typ = get_irp_type(i);
481 type_walk_super_2(cont, pre, post, env);
482 }
483 irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
484 }
485
486 /*****************************************************************************/
487
488
class_walk_s2s_2(ir_type * tp,class_walk_func * pre,class_walk_func * post,void * env)489 static void class_walk_s2s_2(ir_type *tp, class_walk_func *pre,
490 class_walk_func *post, void *env)
491 {
492 size_t i, n;
493
494 /* marked? */
495 if (type_visited(tp)) return;
496
497 assert(is_Class_type(tp));
498 /* Assure all supertypes are visited before */
499 n = get_class_n_supertypes(tp);
500 for (i = 0; i < n; ++i) {
501 if (type_not_visited(get_class_supertype(tp, i)))
502 return;
503 }
504
505 mark_type_visited(tp);
506
507 /* execute pre method */
508 if (pre)
509 pre(tp, env);
510
511 n = get_class_n_subtypes(tp);
512 for (i = 0; i < n; ++i) {
513 class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
514 }
515 /* execute post method */
516 if (post)
517 post(tp, env);
518 }
519
class_walk_super2sub(class_walk_func * pre,class_walk_func * post,void * env)520 void class_walk_super2sub(class_walk_func *pre,
521 class_walk_func *post,
522 void *env)
523 {
524 size_t i, n_types = get_irp_n_types();
525 ir_type *tp;
526
527 irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
528 inc_master_type_visited();
529 for (i = 0; i < n_types; i++) {
530 tp = get_irp_type(i);
531 if (is_Class_type(tp) &&
532 (get_class_n_supertypes(tp) == 0) &&
533 type_not_visited(tp) &&
534 (! is_frame_type(tp)) &&
535 (tp != get_glob_type())) {
536 class_walk_s2s_2(tp, pre, post, env);
537 }
538 }
539 irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
540 }
541
542
walk_types_entities(ir_type * tp,entity_walk_func * doit,void * env)543 void walk_types_entities(ir_type *tp,
544 entity_walk_func *doit,
545 void *env)
546 {
547 size_t i, n;
548
549 switch (get_type_tpop_code(tp)) {
550 case tpo_class:
551 n = get_class_n_members(tp);
552 for (i = 0; i < n; ++i)
553 doit(get_class_member(tp, i), env);
554 break;
555 case tpo_struct:
556 n = get_struct_n_members(tp);
557 for (i = 0; i < n; ++i)
558 doit(get_struct_member(tp, i), env);
559 break;
560 case tpo_union:
561 n = get_union_n_members(tp);
562 for (i = 0; i < n; ++i)
563 doit(get_union_member(tp, i), env);
564 break;
565 case tpo_array:
566 doit(get_array_element_entity(tp), env);
567 break;
568 case tpo_method:
569 case tpo_enumeration:
570 case tpo_pointer:
571 case tpo_primitive:
572 default:
573 break;
574 }
575 }
576