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.
27 /*------------------------------------------------------------------*/
28 /* We represent the fields in entities/types by hashmaps. */
29 /*------------------------------------------------------------------*/
31 static pmap *entity_access_map = NULL;
32 static pmap *entity_reference_map = NULL;
33 static pmap *type_alloc_map = NULL;
34 static pmap *type_cast_map = NULL;
35 static pmap *type_pointertype_map = NULL;
36 static pmap *type_arraytype_map = NULL;
39 * Return a flexible array containing all IR-nodes
40 * that access a given entity.
42 static ir_node **get_entity_access_array(ir_entity *ent) {
44 if (!entity_access_map) entity_access_map = pmap_create();
46 if (pmap_contains(entity_access_map, (void *)ent)) {
47 res = (ir_node **) pmap_get(entity_access_map, (void *)ent);
49 res = NEW_ARR_F(ir_node *, 0);
50 pmap_insert(entity_access_map, (void *)ent, (void *)res);
55 void set_entity_access_array(ir_entity *ent, ir_node **accs) {
56 ir_node **old = pmap_get(entity_access_map, (void *)ent);
58 pmap_insert(entity_access_map, (void *)ent, (void *)accs);
62 * Return a flexible array containing all IR-nodes
63 * that reference a given entity.
65 static ir_node **get_entity_reference_array(ir_entity *ent) {
67 if (!entity_reference_map) entity_reference_map = pmap_create();
69 if (pmap_contains(entity_reference_map, (void *)ent)) {
70 res = (ir_node **) pmap_get(entity_reference_map, (void *)ent);
72 res = NEW_ARR_F(ir_node *, 0);
73 pmap_insert(entity_reference_map, (void *)ent, (void *)res);
78 void set_entity_reference_array(ir_entity *ent, ir_node **refs) {
79 ir_node **old = pmap_get(entity_reference_map, (void *)ent);
81 pmap_insert(entity_reference_map, (void *)ent, (void *)refs);
85 * Return a flexible array containing all IR-nodes
86 * that allocate a given type.
88 static ir_node **get_type_alloc_array(ir_type *tp) {
90 if (!type_alloc_map) type_alloc_map = pmap_create();
92 if (pmap_contains(type_alloc_map, (void *)tp)) {
93 res = (ir_node **) pmap_get(type_alloc_map, (void *)tp);
95 res = NEW_ARR_F(ir_node *, 0);
96 pmap_insert(type_alloc_map, (void *)tp, (void *)res);
101 void set_type_alloc_array(ir_type *tp, ir_node **alls) {
102 ir_node **old = pmap_get(type_alloc_map, (void *)tp);
104 pmap_insert(type_alloc_map, (void *)tp, (void *)alls);
108 * Return a flexible array containing all Cast-nodes
109 * that "create" a given type.
111 static ir_node **get_type_cast_array(ir_type *tp) {
113 if (!type_cast_map) type_cast_map = pmap_create();
115 if (pmap_contains(type_cast_map, (void *)tp)) {
116 res = (ir_node **) pmap_get(type_cast_map, (void *)tp);
118 res = NEW_ARR_F(ir_node *, 0);
119 pmap_insert(type_cast_map, (void *)tp, (void *)res);
124 void set_type_cast_array(ir_type *tp, ir_node **alls) {
125 ir_node **old = pmap_get(type_cast_map, (void *)tp);
127 pmap_insert(type_cast_map, (void *)tp, (void *)alls);
131 * Return a flexible array containing all pointer
132 * types that points-to a given type.
134 static ir_type **get_type_pointertype_array(ir_type *tp) {
136 if (!type_pointertype_map) type_pointertype_map = pmap_create();
138 if (pmap_contains(type_pointertype_map, (void *)tp)) {
139 res = (ir_type **) pmap_get(type_pointertype_map, (void *)tp);
141 res = NEW_ARR_F(ir_type *, 0);
142 pmap_insert(type_pointertype_map, (void *)tp, (void *)res);
147 void set_type_pointertype_array(ir_type *tp, ir_type **pts) {
148 ir_type **old = pmap_get(type_pointertype_map, (void *)tp);
150 pmap_insert(type_pointertype_map, (void *)tp, (void *)pts);
154 * Return a flexible array containing all array
155 * types that have a given type as element type.
157 static ir_type **get_type_arraytype_array(ir_type *tp) {
159 if (!type_arraytype_map) type_arraytype_map = pmap_create();
161 if (pmap_contains(type_arraytype_map, (void *)tp)) {
162 res = (ir_type **) pmap_get(type_arraytype_map, (void *)tp);
164 res = NEW_ARR_F(ir_type *, 0);
165 pmap_insert(type_arraytype_map, (void *)tp, (void *)res);
171 void set_type_arraytype_array(ir_type *tp, ir_type **pts) {
172 ir_type **old = pmap_get(type_arraytype_map, (void *)tp);
174 pmap_insert(type_arraytype_map, (void *)tp, (void *)pts);
177 /*------------------------------------------------------------------*/
178 /* Accessing the out data structures. */
179 /* These routines only work properly if firm is in state */
180 /* trouts_consistent or trouts_inconsistent. */
181 /*------------------------------------------------------------------*/
183 /**------------------------------------------------------------------*/
184 /* Access routines for entities */
185 /**------------------------------------------------------------------*/
187 int get_entity_n_accesses(ir_entity *ent) {
190 assert(ent && is_entity(ent));
192 accs = get_entity_access_array(ent);
193 return ARR_LEN(accs);
196 ir_node *get_entity_access(ir_entity *ent, int pos) {
199 assert(0 <= pos && pos < get_entity_n_accesses(ent));
201 accs = get_entity_access_array(ent);
205 void add_entity_access(ir_entity *ent, ir_node *n) {
208 assert(ent && is_entity(ent));
209 assert(n && is_ir_node(n));
211 accs = get_entity_access_array(ent);
212 ARR_APP1(ir_node *, accs, n);
213 set_entity_access_array(ent, accs);
216 void set_entity_access(ir_entity *ent, int pos, ir_node *n) {
219 assert(0 <= pos && pos < get_entity_n_accesses(ent));
220 assert(n && is_ir_node(n));
222 accs = get_entity_access_array(ent);
226 /**------------------------------------------------------------------*/
228 int get_entity_n_references(ir_entity *ent) {
231 assert(ent && is_entity(ent));
233 refs = get_entity_reference_array(ent);
234 return ARR_LEN(refs);
237 ir_node *get_entity_reference(ir_entity *ent, int pos) {
240 assert(0 <= pos && pos < get_entity_n_references(ent));
242 refs = get_entity_reference_array(ent);
246 void add_entity_reference(ir_entity *ent, ir_node *n) {
249 assert(ent && is_entity(ent));
250 assert(n && is_ir_node(n));
252 refs = get_entity_reference_array(ent);
253 ARR_APP1(ir_node *, refs, n);
254 set_entity_reference_array(ent, refs);
257 void set_entity_reference(ir_entity *ent, int pos, ir_node *n) {
260 assert(0 <= pos && pos < get_entity_n_references(ent));
261 assert(n && is_ir_node(n));
263 refs = get_entity_reference_array(ent);
268 /**------------------------------------------------------------------*/
269 /* Access routines for types */
270 /**------------------------------------------------------------------*/
272 /* Number of Alloc nodes that create an instance of this type */
273 int get_type_n_allocs(ir_type *tp) {
276 assert(tp && is_type(tp));
278 allocs = get_type_alloc_array(tp);
279 return ARR_LEN(allocs);
282 /* Alloc node that creates an instance of this type */
283 ir_node *get_type_alloc(ir_type *tp, int pos) {
285 assert(0 <= pos && pos < get_type_n_allocs(tp));
287 allocs = get_type_alloc_array(tp);
291 void add_type_alloc(ir_type *tp, ir_node *n) {
294 assert(tp && is_type(tp));
295 assert(n && is_ir_node(n));
297 allocs = get_type_alloc_array(tp);
298 ARR_APP1(ir_node *, allocs, n);
299 set_type_alloc_array(tp, allocs);
302 void set_type_alloc(ir_type *tp, int pos, ir_node *n) {
305 assert(0 <= pos && pos < get_type_n_allocs(tp));
306 assert(n && is_ir_node(n));
308 allocs = get_type_alloc_array(tp);
312 /* Number of Cast nodes that create an instance of this type */
313 int get_type_n_casts(ir_type *tp) {
316 assert(tp && is_type(tp));
318 casts = get_type_cast_array(tp);
319 return ARR_LEN(casts);
323 int get_class_n_upcasts(ir_type *clss) {
324 int i, n_casts = get_type_n_casts(clss);
326 for (i = 0; i < n_casts; ++i) {
327 ir_node *cast = get_type_cast(clss, i);
328 if (is_Cast_upcast(cast)) n_instances ++;
333 int get_class_n_downcasts(ir_type *clss) {
334 int i, n_casts = get_type_n_casts(clss);
336 for (i = 0; i < n_casts; ++i) {
337 ir_node *cast = get_type_cast(clss, i);
338 if (is_Cast_downcast(cast)) n_instances ++;
344 /* Cast node that creates an instance of this type */
345 ir_node *get_type_cast(ir_type *tp, int pos) {
347 assert(0 <= pos && pos < get_type_n_casts(tp));
349 casts = get_type_cast_array(tp);
353 void add_type_cast(ir_type *tp, ir_node *n) {
356 assert(tp && is_type(tp));
357 assert(n && is_ir_node(n));
359 casts = get_type_cast_array(tp);
360 ARR_APP1(ir_node *, casts, n);
361 set_type_cast_array(tp, casts);
364 void set_type_cast(ir_type *tp, int pos, ir_node *n) {
367 assert(0 <= pos && pos < get_type_n_casts(tp));
368 assert(n && is_ir_node(n));
370 casts = get_type_cast_array(tp);
374 /**------------------------------------------------------------------*/
376 int get_type_n_pointertypes_to(ir_type *tp) {
379 assert(tp && is_type(tp));
381 pts = get_type_pointertype_array(tp);
385 ir_type *get_type_pointertype_to(ir_type *tp, int pos) {
388 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
390 pts = get_type_pointertype_array(tp);
394 void add_type_pointertype_to(ir_type *tp, ir_type *ptp) {
397 assert(tp && is_type(tp));
398 assert(ptp && is_Pointer_type(ptp));
400 pts = get_type_pointertype_array(tp);
401 ARR_APP1(ir_node *, pts, ptp);
402 set_type_pointertype_array(tp, pts);
405 void set_type_pointertype_to(ir_type *tp, int pos, ir_type *ptp) {
408 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
409 assert(ptp && is_Pointer_type(ptp));
411 pts = get_type_pointertype_array(tp);
416 /**------------------------------------------------------------------*/
418 int get_type_n_arraytypes_of(ir_type *tp) {
421 assert(tp && is_type(tp));
423 pts = get_type_arraytype_array(tp);
427 ir_type *get_type_arraytype_of(ir_type *tp, int pos) {
430 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
432 pts = get_type_arraytype_array(tp);
436 void add_type_arraytype_of(ir_type *tp, ir_type *atp) {
439 assert(tp && is_type(tp));
440 assert(atp && is_Array_type(atp));
442 pts = get_type_arraytype_array(tp);
443 ARR_APP1(ir_node *, pts, atp);
444 set_type_arraytype_array(tp, pts);
447 void set_type_arraytype_of(ir_type *tp, int pos, ir_type *atp) {
450 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
451 assert(atp && is_Array_type(atp));
453 pts = get_type_arraytype_array(tp);
457 /*------------------------------------------------------------------*/
458 /* Building and Removing the out datastructure */
459 /*------------------------------------------------------------------*/
461 static void init_trouts(void) {
465 /** The number of entities that can be accessed by this Sel node. */
466 static int get_Sel_n_accessed_entities(ir_node *sel) {
470 /** The entity that cat be accessed by this Sel node. */
471 static ir_entity *get_Sel_accessed_entity(ir_node *sel) {
472 return get_Sel_entity(sel);
475 /** An addr node is a SymConst or a Sel. */
476 static int get_addr_n_entities(ir_node *addr) {
479 switch (get_irn_opcode(addr)) {
481 /* Treat jack array sels? */
482 n_ents = get_Sel_n_accessed_entities(addr);
485 if (get_SymConst_kind(addr) == symconst_addr_ent) {
490 //assert(0 && "unexpected address expression");
497 /** An addr node is a SymConst or a Sel.
498 If Sel follow to outermost of compound. */
499 static ir_entity *get_addr_entity(ir_node *addr, int pos) {
502 switch (get_irn_opcode(addr)) {
504 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
505 while (is_Sel(get_Sel_ptr(addr))) {
506 addr = get_Sel_ptr(addr);
508 assert (0 <= pos && pos < get_Sel_n_accessed_entities(addr));
509 ent = get_Sel_accessed_entity(addr);
512 if (get_SymConst_kind(addr) == symconst_addr_ent) {
514 ent = get_SymConst_entity(addr);
524 static void chain_accesses(ir_node *n, void *env) {
528 if (get_irn_op(n) == op_Alloc) {
529 add_type_alloc(get_Alloc_type(n), n);
533 if (get_irn_op(n) == op_Cast) {
534 add_type_cast(get_Cast_type(n), n);
538 if (get_irn_op(n) == op_Sel) {
539 add_entity_reference(get_Sel_entity(n), n);
541 } else if (get_irn_op(n) == op_SymConst && (get_SymConst_kind(n) == symconst_addr_ent)) {
542 add_entity_reference(get_SymConst_entity(n), n);
547 addr = get_memop_ptr(n);
548 } else if (get_irn_op(n) == op_Call) {
549 addr = get_Call_ptr(n);
550 if (! is_Sel(addr)) return; /* Sels before Calls mean a Load / polymorphic Call. */
555 n_ents = get_addr_n_entities(addr); /* == 1 */
556 for (i = 0; i < n_ents; ++i) {
557 ir_entity *ent = get_addr_entity(addr, i);
559 add_entity_access(ent, n);
561 //add_unrecognized_access(n);
565 static void chain_types(ir_type *tp) {
566 if (is_Pointer_type(tp)) {
567 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
568 } else if (is_Array_type(tp)) {
569 add_type_arraytype_of(get_array_element_type(tp), tp);
573 irg_outs_state get_trouts_state(void) {
574 return irp->trouts_state;
576 void set_trouts_inconsistent(void) {
577 if (irp->trouts_state == outs_consistent)
578 irp->trouts_state = outs_inconsistent;
582 /* compute the field temperature. */
583 void compute_trouts(void) {
585 n_irgs = get_irp_n_irgs(),
586 n_types = get_irp_n_types();
591 /* Compute outs for irnodes. */
592 for (i = 0; i < n_irgs; i++) {
593 irg_walk_graph(get_irp_irg(i), NULL, chain_accesses, NULL);
595 walk_const_code(NULL, chain_accesses, NULL);
597 /* Compute outs for types */
598 for (i = 0; i < n_types; ++i) {
599 chain_types(get_irp_type(i));
602 irp->trouts_state = outs_consistent;
606 void free_trouts(void) {
608 if (entity_access_map) {
610 for (accs = (ir_node **)pmap_first(entity_access_map);
612 accs = (ir_node **)pmap_next(entity_access_map))
614 pmap_destroy(entity_access_map);
615 entity_access_map = NULL;
618 if (entity_reference_map) {
620 for (refs = (ir_node **)pmap_first(entity_reference_map);
622 refs = (ir_node **)pmap_next(entity_reference_map))
624 pmap_destroy(entity_reference_map);
625 entity_reference_map = NULL;
628 if (type_alloc_map) {
630 for (alls = (ir_node **)pmap_first(type_alloc_map);
632 alls = (ir_node **)pmap_next(type_alloc_map))
634 pmap_destroy(type_alloc_map);
635 type_alloc_map = NULL;
640 for (casts = (ir_node **)pmap_first(type_cast_map);
642 casts = (ir_node **)pmap_next(type_cast_map))
644 pmap_destroy(type_cast_map);
645 type_cast_map = NULL;
648 if (type_pointertype_map) {
650 for (pts = (ir_node **)pmap_first(type_pointertype_map);
652 pts = (ir_node **)pmap_next(type_pointertype_map))
654 pmap_destroy(type_pointertype_map);
655 type_pointertype_map = NULL;
658 if (type_arraytype_map) {
660 for (pts = (ir_node **)pmap_first(type_arraytype_map);
662 pts = (ir_node **)pmap_next(type_arraytype_map))
664 pmap_destroy(type_arraytype_map);
665 type_arraytype_map = NULL;
668 irp->trouts_state = outs_none;