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.
22 /*------------------------------------------------------------------*/
23 /* We represent the fields in entities/types by hashmaps. */
24 /*------------------------------------------------------------------*/
26 static pmap *entity_access_map = NULL;
27 static pmap *entity_reference_map = NULL;
28 static pmap *type_alloc_map = NULL;
29 static pmap *type_cast_map = NULL;
30 static pmap *type_pointertype_map = NULL;
31 static pmap *type_arraytype_map = NULL;
34 * Return a flexible array containing all IR-nodes
35 * that access a given entity.
37 static ir_node **get_entity_access_array(entity *ent) {
39 if (!entity_access_map) entity_access_map = pmap_create();
41 if (pmap_contains(entity_access_map, (void *)ent)) {
42 res = (ir_node **) pmap_get(entity_access_map, (void *)ent);
44 res = NEW_ARR_F(ir_node *, 0);
45 pmap_insert(entity_access_map, (void *)ent, (void *)res);
50 void set_entity_access_array(entity *ent, ir_node **accs) {
51 ir_node **old = pmap_get(entity_access_map, (void *)ent);
53 pmap_insert(entity_access_map, (void *)ent, (void *)accs);
57 * Return a flexible array containing all IR-nodes
58 * that reference a given entity.
60 static ir_node **get_entity_reference_array(entity *ent) {
62 if (!entity_reference_map) entity_reference_map = pmap_create();
64 if (pmap_contains(entity_reference_map, (void *)ent)) {
65 res = (ir_node **) pmap_get(entity_reference_map, (void *)ent);
67 res = NEW_ARR_F(ir_node *, 0);
68 pmap_insert(entity_reference_map, (void *)ent, (void *)res);
73 void set_entity_reference_array(entity *ent, ir_node **refs) {
74 ir_node **old = pmap_get(entity_reference_map, (void *)ent);
76 pmap_insert(entity_reference_map, (void *)ent, (void *)refs);
80 * Return a flexible array containing all IR-nodes
81 * that allocate a given type.
83 static ir_node **get_type_alloc_array(ir_type *tp) {
85 if (!type_alloc_map) type_alloc_map = pmap_create();
87 if (pmap_contains(type_alloc_map, (void *)tp)) {
88 res = (ir_node **) pmap_get(type_alloc_map, (void *)tp);
90 res = NEW_ARR_F(ir_node *, 0);
91 pmap_insert(type_alloc_map, (void *)tp, (void *)res);
96 void set_type_alloc_array(ir_type *tp, ir_node **alls) {
97 ir_node **old = pmap_get(type_alloc_map, (void *)tp);
99 pmap_insert(type_alloc_map, (void *)tp, (void *)alls);
103 * Return a flexible array containing all Cast-nodes
104 * that "create" a given type.
106 static ir_node **get_type_cast_array(ir_type *tp) {
108 if (!type_cast_map) type_cast_map = pmap_create();
110 if (pmap_contains(type_cast_map, (void *)tp)) {
111 res = (ir_node **) pmap_get(type_cast_map, (void *)tp);
113 res = NEW_ARR_F(ir_node *, 0);
114 pmap_insert(type_cast_map, (void *)tp, (void *)res);
119 void set_type_cast_array(ir_type *tp, ir_node **alls) {
120 ir_node **old = pmap_get(type_cast_map, (void *)tp);
122 pmap_insert(type_cast_map, (void *)tp, (void *)alls);
126 * Return a flexible array containing all pointer
127 * types that points-to a given type.
129 static ir_type **get_type_pointertype_array(ir_type *tp) {
131 if (!type_pointertype_map) type_pointertype_map = pmap_create();
133 if (pmap_contains(type_pointertype_map, (void *)tp)) {
134 res = (ir_type **) pmap_get(type_pointertype_map, (void *)tp);
136 res = NEW_ARR_F(ir_type *, 0);
137 pmap_insert(type_pointertype_map, (void *)tp, (void *)res);
142 void set_type_pointertype_array(ir_type *tp, ir_type **pts) {
143 ir_type **old = pmap_get(type_pointertype_map, (void *)tp);
145 pmap_insert(type_pointertype_map, (void *)tp, (void *)pts);
149 * Return a flexible array containing all array
150 * types that have a given type as element type.
152 static ir_type **get_type_arraytype_array(ir_type *tp) {
154 if (!type_arraytype_map) type_arraytype_map = pmap_create();
156 if (pmap_contains(type_arraytype_map, (void *)tp)) {
157 res = (ir_type **) pmap_get(type_arraytype_map, (void *)tp);
159 res = NEW_ARR_F(ir_type *, 0);
160 pmap_insert(type_arraytype_map, (void *)tp, (void *)res);
166 void set_type_arraytype_array(ir_type *tp, ir_type **pts) {
167 ir_type **old = pmap_get(type_arraytype_map, (void *)tp);
169 pmap_insert(type_arraytype_map, (void *)tp, (void *)pts);
172 /*------------------------------------------------------------------*/
173 /* Accessing the out data structures. */
174 /* These routines only work properly if firm is in state */
175 /* trouts_consistent or trouts_inconsistent. */
176 /*------------------------------------------------------------------*/
178 /**------------------------------------------------------------------*/
179 /* Access routines for entities */
180 /**------------------------------------------------------------------*/
182 int get_entity_n_accesses(entity *ent) {
185 assert(ent && is_entity(ent));
187 accs = get_entity_access_array(ent);
188 return ARR_LEN(accs);
191 ir_node *get_entity_access(entity *ent, int pos) {
194 assert(0 <= pos && pos < get_entity_n_accesses(ent));
196 accs = get_entity_access_array(ent);
200 void add_entity_access(entity *ent, ir_node *n) {
203 assert(ent && is_entity(ent));
204 assert(n && is_ir_node(n));
206 accs = get_entity_access_array(ent);
207 ARR_APP1(ir_node *, accs, n);
208 set_entity_access_array(ent, accs);
211 void set_entity_access(entity *ent, int pos, ir_node *n) {
214 assert(0 <= pos && pos < get_entity_n_accesses(ent));
215 assert(n && is_ir_node(n));
217 accs = get_entity_access_array(ent);
221 /**------------------------------------------------------------------*/
223 int get_entity_n_references(entity *ent) {
226 assert(ent && is_entity(ent));
228 refs = get_entity_reference_array(ent);
229 return ARR_LEN(refs);
232 ir_node *get_entity_reference(entity *ent, int pos) {
235 assert(0 <= pos && pos < get_entity_n_references(ent));
237 refs = get_entity_reference_array(ent);
241 void add_entity_reference(entity *ent, ir_node *n) {
244 assert(ent && is_entity(ent));
245 assert(n && is_ir_node(n));
247 refs = get_entity_reference_array(ent);
248 ARR_APP1(ir_node *, refs, n);
249 set_entity_reference_array(ent, refs);
252 void set_entity_reference(entity *ent, int pos, ir_node *n) {
255 assert(0 <= pos && pos < get_entity_n_references(ent));
256 assert(n && is_ir_node(n));
258 refs = get_entity_reference_array(ent);
263 /**------------------------------------------------------------------*/
264 /* Access routines for types */
265 /**------------------------------------------------------------------*/
267 /* Number of Alloc nodes that create an instance of this type */
268 int get_type_n_allocs(ir_type *tp) {
271 assert(tp && is_type(tp));
273 allocs = get_type_alloc_array(tp);
274 return ARR_LEN(allocs);
277 /* Alloc node that creates an instance of this type */
278 ir_node *get_type_alloc(ir_type *tp, int pos) {
280 assert(0 <= pos && pos < get_type_n_allocs(tp));
282 allocs = get_type_alloc_array(tp);
286 void add_type_alloc(ir_type *tp, ir_node *n) {
289 assert(tp && is_type(tp));
290 assert(n && is_ir_node(n));
292 allocs = get_type_alloc_array(tp);
293 ARR_APP1(ir_node *, allocs, n);
294 set_type_alloc_array(tp, allocs);
297 void set_type_alloc(ir_type *tp, int pos, ir_node *n) {
300 assert(0 <= pos && pos < get_type_n_allocs(tp));
301 assert(n && is_ir_node(n));
303 allocs = get_type_alloc_array(tp);
307 /* Number of Cast nodes that create an instance of this type */
308 int get_type_n_casts(ir_type *tp) {
311 assert(tp && is_type(tp));
313 casts = get_type_cast_array(tp);
314 return ARR_LEN(casts);
318 int get_class_n_upcasts(ir_type *clss) {
319 int i, n_casts = get_type_n_casts(clss);
321 for (i = 0; i < n_casts; ++i) {
322 ir_node *cast = get_type_cast(clss, i);
323 if (is_Cast_upcast(cast)) n_instances ++;
328 int get_class_n_downcasts(ir_type *clss) {
329 int i, n_casts = get_type_n_casts(clss);
331 for (i = 0; i < n_casts; ++i) {
332 ir_node *cast = get_type_cast(clss, i);
333 if (is_Cast_downcast(cast)) n_instances ++;
339 /* Cast node that creates an instance of this type */
340 ir_node *get_type_cast(ir_type *tp, int pos) {
342 assert(0 <= pos && pos < get_type_n_casts(tp));
344 casts = get_type_cast_array(tp);
348 void add_type_cast(ir_type *tp, ir_node *n) {
351 assert(tp && is_type(tp));
352 assert(n && is_ir_node(n));
354 casts = get_type_cast_array(tp);
355 ARR_APP1(ir_node *, casts, n);
356 set_type_cast_array(tp, casts);
359 void set_type_cast(ir_type *tp, int pos, ir_node *n) {
362 assert(0 <= pos && pos < get_type_n_casts(tp));
363 assert(n && is_ir_node(n));
365 casts = get_type_cast_array(tp);
369 /**------------------------------------------------------------------*/
371 int get_type_n_pointertypes_to(ir_type *tp) {
374 assert(tp && is_type(tp));
376 pts = get_type_pointertype_array(tp);
380 ir_type *get_type_pointertype_to(ir_type *tp, int pos) {
383 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
385 pts = get_type_pointertype_array(tp);
389 void add_type_pointertype_to(ir_type *tp, ir_type *ptp) {
392 assert(tp && is_type(tp));
393 assert(ptp && is_Pointer_type(ptp));
395 pts = get_type_pointertype_array(tp);
396 ARR_APP1(ir_node *, pts, ptp);
397 set_type_pointertype_array(tp, pts);
400 void set_type_pointertype_to(ir_type *tp, int pos, ir_type *ptp) {
403 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
404 assert(ptp && is_Pointer_type(ptp));
406 pts = get_type_pointertype_array(tp);
411 /**------------------------------------------------------------------*/
413 int get_type_n_arraytypes_of(ir_type *tp) {
416 assert(tp && is_type(tp));
418 pts = get_type_arraytype_array(tp);
422 ir_type *get_type_arraytype_of(ir_type *tp, int pos) {
425 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
427 pts = get_type_arraytype_array(tp);
431 void add_type_arraytype_of(ir_type *tp, ir_type *atp) {
434 assert(tp && is_type(tp));
435 assert(atp && is_Array_type(atp));
437 pts = get_type_arraytype_array(tp);
438 ARR_APP1(ir_node *, pts, atp);
439 set_type_arraytype_array(tp, pts);
442 void set_type_arraytype_of(ir_type *tp, int pos, ir_type *atp) {
445 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
446 assert(atp && is_Array_type(atp));
448 pts = get_type_arraytype_array(tp);
452 /*------------------------------------------------------------------*/
453 /* Building and Removing the out datastructure */
454 /*------------------------------------------------------------------*/
456 static void init_trouts(void) {
460 /** The number of entities that can be accessed by this Sel node. */
461 static int get_Sel_n_accessed_entities(ir_node *sel) {
465 /** The entity that cat be accessed by this Sel node. */
466 static entity *get_Sel_accessed_entity(ir_node *sel) {
467 return get_Sel_entity(sel);
470 /** An addr node is a SymConst or a Sel. */
471 static int get_addr_n_entities(ir_node *addr) {
474 switch (get_irn_opcode(addr)) {
476 /* Treat jack array sels? */
477 n_ents = get_Sel_n_accessed_entities(addr);
480 if (get_SymConst_kind(addr) == symconst_addr_ent) {
485 //assert(0 && "unexpected address expression");
492 /** An addr node is a SymConst or a Sel.
493 If Sel follow to outermost of compound. */
494 static entity *get_addr_entity(ir_node *addr, int pos) {
497 switch (get_irn_opcode(addr)) {
499 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
500 while (is_Sel(get_Sel_ptr(addr))) {
501 addr = get_Sel_ptr(addr);
503 assert (0 <= pos && pos < get_Sel_n_accessed_entities(addr));
504 ent = get_Sel_accessed_entity(addr);
507 if (get_SymConst_kind(addr) == symconst_addr_ent) {
509 ent = get_SymConst_entity(addr);
519 static void chain_accesses(ir_node *n, void *env) {
523 if (get_irn_op(n) == op_Alloc) {
524 add_type_alloc(get_Alloc_type(n), n);
528 if (get_irn_op(n) == op_Cast) {
529 add_type_cast(get_Cast_type(n), n);
533 if (get_irn_op(n) == op_Sel) {
534 add_entity_reference(get_Sel_entity(n), n);
536 } else if (get_irn_op(n) == op_SymConst && (get_SymConst_kind(n) == symconst_addr_ent)) {
537 add_entity_reference(get_SymConst_entity(n), n);
542 addr = get_memop_ptr(n);
543 } else if (get_irn_op(n) == op_Call) {
544 addr = get_Call_ptr(n);
545 if (! is_Sel(addr)) return; /* Sels before Calls mean a Load / polymorphic Call. */
550 n_ents = get_addr_n_entities(addr); /* == 1 */
551 for (i = 0; i < n_ents; ++i) {
552 entity *ent = get_addr_entity(addr, i);
554 add_entity_access(ent, n);
556 //add_unrecognized_access(n);
560 static void chain_types(ir_type *tp) {
561 if (is_Pointer_type(tp)) {
562 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
563 } else if (is_Array_type(tp)) {
564 add_type_arraytype_of(get_array_element_type(tp), tp);
568 irg_outs_state get_trouts_state(void) {
569 return irp->trouts_state;
571 void set_trouts_inconsistent(void) {
572 if (irp->trouts_state == outs_consistent)
573 irp->trouts_state = outs_inconsistent;
577 /* compute the field temperature. */
578 void compute_trouts(void) {
580 n_irgs = get_irp_n_irgs(),
581 n_types = get_irp_n_types();
586 /* Compute outs for irnodes. */
587 for (i = 0; i < n_irgs; i++) {
588 irg_walk_graph(get_irp_irg(i), NULL, chain_accesses, NULL);
590 walk_const_code(NULL, chain_accesses, NULL);
592 /* Compute outs for types */
593 for (i = 0; i < n_types; ++i) {
594 chain_types(get_irp_type(i));
597 irp->trouts_state = outs_consistent;
601 void free_trouts(void) {
603 if (entity_access_map) {
605 for (accs = (ir_node **)pmap_first(entity_access_map);
607 accs = (ir_node **)pmap_next(entity_access_map))
609 pmap_destroy(entity_access_map);
610 entity_access_map = NULL;
613 if (entity_reference_map) {
615 for (refs = (ir_node **)pmap_first(entity_reference_map);
617 refs = (ir_node **)pmap_next(entity_reference_map))
619 pmap_destroy(entity_reference_map);
620 entity_reference_map = NULL;
623 if (type_alloc_map) {
625 for (alls = (ir_node **)pmap_first(type_alloc_map);
627 alls = (ir_node **)pmap_next(type_alloc_map))
629 pmap_destroy(type_alloc_map);
630 type_alloc_map = NULL;
635 for (casts = (ir_node **)pmap_first(type_cast_map);
637 casts = (ir_node **)pmap_next(type_cast_map))
639 pmap_destroy(type_cast_map);
640 type_cast_map = NULL;
643 if (type_pointertype_map) {
645 for (pts = (ir_node **)pmap_first(type_pointertype_map);
647 pts = (ir_node **)pmap_next(type_pointertype_map))
649 pmap_destroy(type_pointertype_map);
650 type_pointertype_map = NULL;
653 if (type_arraytype_map) {
655 for (pts = (ir_node **)pmap_first(type_arraytype_map);
657 pts = (ir_node **)pmap_next(type_arraytype_map))
659 pmap_destroy(type_arraytype_map);
660 type_arraytype_map = NULL;
663 irp->trouts_state = outs_none;