3 * File name: ir/ana/trouts.c
4 * Purpose: Reverse edges that reference types/entities.
5 * Author: Goetz Lindenmaier
9 * Copyright: (c) 2004 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
28 /*------------------------------------------------------------------*/
29 /* We represent the fields in entities/types by hashmaps. */
30 /*------------------------------------------------------------------*/
32 static pmap *entity_access_map = NULL;
33 static pmap *entity_reference_map = NULL;
34 static pmap *type_alloc_map = NULL;
35 static pmap *type_cast_map = NULL;
36 static pmap *type_pointertype_map = NULL;
37 static pmap *type_arraytype_map = NULL;
40 * Return a flexible array containing all IR-nodes
41 * that access a given entity.
43 static ir_node **get_entity_access_array(ir_entity *ent) {
45 if (!entity_access_map) entity_access_map = pmap_create();
47 if (pmap_contains(entity_access_map, (void *)ent)) {
48 res = (ir_node **) pmap_get(entity_access_map, (void *)ent);
50 res = NEW_ARR_F(ir_node *, 0);
51 pmap_insert(entity_access_map, (void *)ent, (void *)res);
56 void set_entity_access_array(ir_entity *ent, ir_node **accs) {
57 ir_node **old = pmap_get(entity_access_map, (void *)ent);
59 pmap_insert(entity_access_map, (void *)ent, (void *)accs);
63 * Return a flexible array containing all IR-nodes
64 * that reference a given entity.
66 static ir_node **get_entity_reference_array(ir_entity *ent) {
68 if (!entity_reference_map) entity_reference_map = pmap_create();
70 if (pmap_contains(entity_reference_map, (void *)ent)) {
71 res = (ir_node **) pmap_get(entity_reference_map, (void *)ent);
73 res = NEW_ARR_F(ir_node *, 0);
74 pmap_insert(entity_reference_map, (void *)ent, (void *)res);
79 void set_entity_reference_array(ir_entity *ent, ir_node **refs) {
80 ir_node **old = pmap_get(entity_reference_map, (void *)ent);
82 pmap_insert(entity_reference_map, (void *)ent, (void *)refs);
86 * Return a flexible array containing all IR-nodes
87 * that allocate a given type.
89 static ir_node **get_type_alloc_array(ir_type *tp) {
91 if (!type_alloc_map) type_alloc_map = pmap_create();
93 if (pmap_contains(type_alloc_map, (void *)tp)) {
94 res = (ir_node **) pmap_get(type_alloc_map, (void *)tp);
96 res = NEW_ARR_F(ir_node *, 0);
97 pmap_insert(type_alloc_map, (void *)tp, (void *)res);
102 void set_type_alloc_array(ir_type *tp, ir_node **alls) {
103 ir_node **old = pmap_get(type_alloc_map, (void *)tp);
105 pmap_insert(type_alloc_map, (void *)tp, (void *)alls);
109 * Return a flexible array containing all Cast-nodes
110 * that "create" a given type.
112 static ir_node **get_type_cast_array(ir_type *tp) {
114 if (!type_cast_map) type_cast_map = pmap_create();
116 if (pmap_contains(type_cast_map, (void *)tp)) {
117 res = (ir_node **) pmap_get(type_cast_map, (void *)tp);
119 res = NEW_ARR_F(ir_node *, 0);
120 pmap_insert(type_cast_map, (void *)tp, (void *)res);
125 void set_type_cast_array(ir_type *tp, ir_node **alls) {
126 ir_node **old = pmap_get(type_cast_map, (void *)tp);
128 pmap_insert(type_cast_map, (void *)tp, (void *)alls);
132 * Return a flexible array containing all pointer
133 * types that points-to a given type.
135 static ir_type **get_type_pointertype_array(ir_type *tp) {
137 if (!type_pointertype_map) type_pointertype_map = pmap_create();
139 if (pmap_contains(type_pointertype_map, (void *)tp)) {
140 res = (ir_type **) pmap_get(type_pointertype_map, (void *)tp);
142 res = NEW_ARR_F(ir_type *, 0);
143 pmap_insert(type_pointertype_map, (void *)tp, (void *)res);
148 void set_type_pointertype_array(ir_type *tp, ir_type **pts) {
149 ir_type **old = pmap_get(type_pointertype_map, (void *)tp);
151 pmap_insert(type_pointertype_map, (void *)tp, (void *)pts);
155 * Return a flexible array containing all array
156 * types that have a given type as element type.
158 static ir_type **get_type_arraytype_array(ir_type *tp) {
160 if (!type_arraytype_map) type_arraytype_map = pmap_create();
162 if (pmap_contains(type_arraytype_map, (void *)tp)) {
163 res = (ir_type **) pmap_get(type_arraytype_map, (void *)tp);
165 res = NEW_ARR_F(ir_type *, 0);
166 pmap_insert(type_arraytype_map, (void *)tp, (void *)res);
172 void set_type_arraytype_array(ir_type *tp, ir_type **pts) {
173 ir_type **old = pmap_get(type_arraytype_map, (void *)tp);
175 pmap_insert(type_arraytype_map, (void *)tp, (void *)pts);
178 /*------------------------------------------------------------------*/
179 /* Accessing the out data structures. */
180 /* These routines only work properly if firm is in state */
181 /* trouts_consistent or trouts_inconsistent. */
182 /*------------------------------------------------------------------*/
184 /**------------------------------------------------------------------*/
185 /* Access routines for entities */
186 /**------------------------------------------------------------------*/
188 int get_entity_n_accesses(ir_entity *ent) {
191 assert(ent && is_entity(ent));
193 accs = get_entity_access_array(ent);
194 return ARR_LEN(accs);
197 ir_node *get_entity_access(ir_entity *ent, int pos) {
200 assert(0 <= pos && pos < get_entity_n_accesses(ent));
202 accs = get_entity_access_array(ent);
206 void add_entity_access(ir_entity *ent, ir_node *n) {
209 assert(ent && is_entity(ent));
210 assert(n && is_ir_node(n));
212 accs = get_entity_access_array(ent);
213 ARR_APP1(ir_node *, accs, n);
214 set_entity_access_array(ent, accs);
217 void set_entity_access(ir_entity *ent, int pos, ir_node *n) {
220 assert(0 <= pos && pos < get_entity_n_accesses(ent));
221 assert(n && is_ir_node(n));
223 accs = get_entity_access_array(ent);
227 /**------------------------------------------------------------------*/
229 int get_entity_n_references(ir_entity *ent) {
232 assert(ent && is_entity(ent));
234 refs = get_entity_reference_array(ent);
235 return ARR_LEN(refs);
238 ir_node *get_entity_reference(ir_entity *ent, int pos) {
241 assert(0 <= pos && pos < get_entity_n_references(ent));
243 refs = get_entity_reference_array(ent);
247 void add_entity_reference(ir_entity *ent, ir_node *n) {
250 assert(ent && is_entity(ent));
251 assert(n && is_ir_node(n));
253 refs = get_entity_reference_array(ent);
254 ARR_APP1(ir_node *, refs, n);
255 set_entity_reference_array(ent, refs);
258 void set_entity_reference(ir_entity *ent, int pos, ir_node *n) {
261 assert(0 <= pos && pos < get_entity_n_references(ent));
262 assert(n && is_ir_node(n));
264 refs = get_entity_reference_array(ent);
269 /**------------------------------------------------------------------*/
270 /* Access routines for types */
271 /**------------------------------------------------------------------*/
273 /* Number of Alloc nodes that create an instance of this type */
274 int get_type_n_allocs(ir_type *tp) {
277 assert(tp && is_type(tp));
279 allocs = get_type_alloc_array(tp);
280 return ARR_LEN(allocs);
283 /* Alloc node that creates an instance of this type */
284 ir_node *get_type_alloc(ir_type *tp, int pos) {
286 assert(0 <= pos && pos < get_type_n_allocs(tp));
288 allocs = get_type_alloc_array(tp);
292 void add_type_alloc(ir_type *tp, ir_node *n) {
295 assert(tp && is_type(tp));
296 assert(n && is_ir_node(n));
298 allocs = get_type_alloc_array(tp);
299 ARR_APP1(ir_node *, allocs, n);
300 set_type_alloc_array(tp, allocs);
303 void set_type_alloc(ir_type *tp, int pos, ir_node *n) {
306 assert(0 <= pos && pos < get_type_n_allocs(tp));
307 assert(n && is_ir_node(n));
309 allocs = get_type_alloc_array(tp);
313 /* Number of Cast nodes that create an instance of this type */
314 int get_type_n_casts(ir_type *tp) {
317 assert(tp && is_type(tp));
319 casts = get_type_cast_array(tp);
320 return ARR_LEN(casts);
324 int get_class_n_upcasts(ir_type *clss) {
325 int i, n_casts = get_type_n_casts(clss);
327 for (i = 0; i < n_casts; ++i) {
328 ir_node *cast = get_type_cast(clss, i);
329 if (is_Cast_upcast(cast)) n_instances ++;
334 int get_class_n_downcasts(ir_type *clss) {
335 int i, n_casts = get_type_n_casts(clss);
337 for (i = 0; i < n_casts; ++i) {
338 ir_node *cast = get_type_cast(clss, i);
339 if (is_Cast_downcast(cast)) n_instances ++;
345 /* Cast node that creates an instance of this type */
346 ir_node *get_type_cast(ir_type *tp, int pos) {
348 assert(0 <= pos && pos < get_type_n_casts(tp));
350 casts = get_type_cast_array(tp);
354 void add_type_cast(ir_type *tp, ir_node *n) {
357 assert(tp && is_type(tp));
358 assert(n && is_ir_node(n));
360 casts = get_type_cast_array(tp);
361 ARR_APP1(ir_node *, casts, n);
362 set_type_cast_array(tp, casts);
365 void set_type_cast(ir_type *tp, int pos, ir_node *n) {
368 assert(0 <= pos && pos < get_type_n_casts(tp));
369 assert(n && is_ir_node(n));
371 casts = get_type_cast_array(tp);
375 /**------------------------------------------------------------------*/
377 int get_type_n_pointertypes_to(ir_type *tp) {
380 assert(tp && is_type(tp));
382 pts = get_type_pointertype_array(tp);
386 ir_type *get_type_pointertype_to(ir_type *tp, int pos) {
389 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
391 pts = get_type_pointertype_array(tp);
395 void add_type_pointertype_to(ir_type *tp, ir_type *ptp) {
398 assert(tp && is_type(tp));
399 assert(ptp && is_Pointer_type(ptp));
401 pts = get_type_pointertype_array(tp);
402 ARR_APP1(ir_node *, pts, ptp);
403 set_type_pointertype_array(tp, pts);
406 void set_type_pointertype_to(ir_type *tp, int pos, ir_type *ptp) {
409 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
410 assert(ptp && is_Pointer_type(ptp));
412 pts = get_type_pointertype_array(tp);
417 /**------------------------------------------------------------------*/
419 int get_type_n_arraytypes_of(ir_type *tp) {
422 assert(tp && is_type(tp));
424 pts = get_type_arraytype_array(tp);
428 ir_type *get_type_arraytype_of(ir_type *tp, int pos) {
431 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
433 pts = get_type_arraytype_array(tp);
437 void add_type_arraytype_of(ir_type *tp, ir_type *atp) {
440 assert(tp && is_type(tp));
441 assert(atp && is_Array_type(atp));
443 pts = get_type_arraytype_array(tp);
444 ARR_APP1(ir_node *, pts, atp);
445 set_type_arraytype_array(tp, pts);
448 void set_type_arraytype_of(ir_type *tp, int pos, ir_type *atp) {
451 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
452 assert(atp && is_Array_type(atp));
454 pts = get_type_arraytype_array(tp);
458 /*------------------------------------------------------------------*/
459 /* Building and Removing the out datastructure */
460 /*------------------------------------------------------------------*/
462 static void init_trouts(void) {
466 /** The number of entities that can be accessed by this Sel node. */
467 static int get_Sel_n_accessed_entities(ir_node *sel) {
471 /** The entity that cat be accessed by this Sel node. */
472 static ir_entity *get_Sel_accessed_entity(ir_node *sel) {
473 return get_Sel_entity(sel);
476 /** An addr node is a SymConst or a Sel. */
477 static int get_addr_n_entities(ir_node *addr) {
480 switch (get_irn_opcode(addr)) {
482 /* Treat jack array sels? */
483 n_ents = get_Sel_n_accessed_entities(addr);
486 if (get_SymConst_kind(addr) == symconst_addr_ent) {
491 //assert(0 && "unexpected address expression");
498 /** An addr node is a SymConst or a Sel.
499 If Sel follow to outermost of compound. */
500 static ir_entity *get_addr_entity(ir_node *addr, int pos) {
503 switch (get_irn_opcode(addr)) {
505 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
506 while (is_Sel(get_Sel_ptr(addr))) {
507 addr = get_Sel_ptr(addr);
509 assert (0 <= pos && pos < get_Sel_n_accessed_entities(addr));
510 ent = get_Sel_accessed_entity(addr);
513 if (get_SymConst_kind(addr) == symconst_addr_ent) {
515 ent = get_SymConst_entity(addr);
525 static void chain_accesses(ir_node *n, void *env) {
529 if (get_irn_op(n) == op_Alloc) {
530 add_type_alloc(get_Alloc_type(n), n);
534 if (get_irn_op(n) == op_Cast) {
535 add_type_cast(get_Cast_type(n), n);
539 if (get_irn_op(n) == op_Sel) {
540 add_entity_reference(get_Sel_entity(n), n);
542 } else if (get_irn_op(n) == op_SymConst && (get_SymConst_kind(n) == symconst_addr_ent)) {
543 add_entity_reference(get_SymConst_entity(n), n);
548 addr = get_memop_ptr(n);
549 } else if (get_irn_op(n) == op_Call) {
550 addr = get_Call_ptr(n);
551 if (! is_Sel(addr)) return; /* Sels before Calls mean a Load / polymorphic Call. */
556 n_ents = get_addr_n_entities(addr); /* == 1 */
557 for (i = 0; i < n_ents; ++i) {
558 ir_entity *ent = get_addr_entity(addr, i);
560 add_entity_access(ent, n);
562 //add_unrecognized_access(n);
566 static void chain_types(ir_type *tp) {
567 if (is_Pointer_type(tp)) {
568 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
569 } else if (is_Array_type(tp)) {
570 add_type_arraytype_of(get_array_element_type(tp), tp);
574 irg_outs_state get_trouts_state(void) {
575 return irp->trouts_state;
577 void set_trouts_inconsistent(void) {
578 if (irp->trouts_state == outs_consistent)
579 irp->trouts_state = outs_inconsistent;
583 /* compute the field temperature. */
584 void compute_trouts(void) {
586 n_irgs = get_irp_n_irgs(),
587 n_types = get_irp_n_types();
592 /* Compute outs for irnodes. */
593 for (i = 0; i < n_irgs; i++) {
594 irg_walk_graph(get_irp_irg(i), NULL, chain_accesses, NULL);
596 walk_const_code(NULL, chain_accesses, NULL);
598 /* Compute outs for types */
599 for (i = 0; i < n_types; ++i) {
600 chain_types(get_irp_type(i));
603 irp->trouts_state = outs_consistent;
607 void free_trouts(void) {
609 if (entity_access_map) {
611 for (accs = (ir_node **)pmap_first(entity_access_map);
613 accs = (ir_node **)pmap_next(entity_access_map))
615 pmap_destroy(entity_access_map);
616 entity_access_map = NULL;
619 if (entity_reference_map) {
621 for (refs = (ir_node **)pmap_first(entity_reference_map);
623 refs = (ir_node **)pmap_next(entity_reference_map))
625 pmap_destroy(entity_reference_map);
626 entity_reference_map = NULL;
629 if (type_alloc_map) {
631 for (alls = (ir_node **)pmap_first(type_alloc_map);
633 alls = (ir_node **)pmap_next(type_alloc_map))
635 pmap_destroy(type_alloc_map);
636 type_alloc_map = NULL;
641 for (casts = (ir_node **)pmap_first(type_cast_map);
643 casts = (ir_node **)pmap_next(type_cast_map))
645 pmap_destroy(type_cast_map);
646 type_cast_map = NULL;
649 if (type_pointertype_map) {
651 for (pts = (ir_node **)pmap_first(type_pointertype_map);
653 pts = (ir_node **)pmap_next(type_pointertype_map))
655 pmap_destroy(type_pointertype_map);
656 type_pointertype_map = NULL;
659 if (type_arraytype_map) {
661 for (pts = (ir_node **)pmap_first(type_arraytype_map);
663 pts = (ir_node **)pmap_next(type_arraytype_map))
665 pmap_destroy(type_arraytype_map);
666 type_arraytype_map = NULL;
669 irp->trouts_state = outs_none;