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.
26 /*------------------------------------------------------------------*/
27 /* We represent the fields in entities/types by hashmaps. */
28 /*------------------------------------------------------------------*/
30 static pmap *entity_access_map = NULL;
31 static pmap *entity_reference_map = NULL;
32 static pmap *type_alloc_map = NULL;
33 static pmap *type_cast_map = NULL;
34 static pmap *type_pointertype_map = NULL;
35 static pmap *type_arraytype_map = NULL;
38 * Return a flexible array containing all IR-nodes
39 * that access a given entity.
41 static ir_node **get_entity_access_array(ir_entity *ent) {
43 if (!entity_access_map) entity_access_map = pmap_create();
45 if (pmap_contains(entity_access_map, (void *)ent)) {
46 res = (ir_node **) pmap_get(entity_access_map, (void *)ent);
48 res = NEW_ARR_F(ir_node *, 0);
49 pmap_insert(entity_access_map, (void *)ent, (void *)res);
54 void set_entity_access_array(ir_entity *ent, ir_node **accs) {
55 ir_node **old = pmap_get(entity_access_map, (void *)ent);
57 pmap_insert(entity_access_map, (void *)ent, (void *)accs);
61 * Return a flexible array containing all IR-nodes
62 * that reference a given entity.
64 static ir_node **get_entity_reference_array(ir_entity *ent) {
66 if (!entity_reference_map) entity_reference_map = pmap_create();
68 if (pmap_contains(entity_reference_map, (void *)ent)) {
69 res = (ir_node **) pmap_get(entity_reference_map, (void *)ent);
71 res = NEW_ARR_F(ir_node *, 0);
72 pmap_insert(entity_reference_map, (void *)ent, (void *)res);
77 void set_entity_reference_array(ir_entity *ent, ir_node **refs) {
78 ir_node **old = pmap_get(entity_reference_map, (void *)ent);
80 pmap_insert(entity_reference_map, (void *)ent, (void *)refs);
84 * Return a flexible array containing all IR-nodes
85 * that allocate a given type.
87 static ir_node **get_type_alloc_array(ir_type *tp) {
89 if (!type_alloc_map) type_alloc_map = pmap_create();
91 if (pmap_contains(type_alloc_map, (void *)tp)) {
92 res = (ir_node **) pmap_get(type_alloc_map, (void *)tp);
94 res = NEW_ARR_F(ir_node *, 0);
95 pmap_insert(type_alloc_map, (void *)tp, (void *)res);
100 void set_type_alloc_array(ir_type *tp, ir_node **alls) {
101 ir_node **old = pmap_get(type_alloc_map, (void *)tp);
103 pmap_insert(type_alloc_map, (void *)tp, (void *)alls);
107 * Return a flexible array containing all Cast-nodes
108 * that "create" a given type.
110 static ir_node **get_type_cast_array(ir_type *tp) {
112 if (!type_cast_map) type_cast_map = pmap_create();
114 if (pmap_contains(type_cast_map, (void *)tp)) {
115 res = (ir_node **) pmap_get(type_cast_map, (void *)tp);
117 res = NEW_ARR_F(ir_node *, 0);
118 pmap_insert(type_cast_map, (void *)tp, (void *)res);
123 void set_type_cast_array(ir_type *tp, ir_node **alls) {
124 ir_node **old = pmap_get(type_cast_map, (void *)tp);
126 pmap_insert(type_cast_map, (void *)tp, (void *)alls);
130 * Return a flexible array containing all pointer
131 * types that points-to a given type.
133 static ir_type **get_type_pointertype_array(ir_type *tp) {
135 if (!type_pointertype_map) type_pointertype_map = pmap_create();
137 if (pmap_contains(type_pointertype_map, (void *)tp)) {
138 res = (ir_type **) pmap_get(type_pointertype_map, (void *)tp);
140 res = NEW_ARR_F(ir_type *, 0);
141 pmap_insert(type_pointertype_map, (void *)tp, (void *)res);
146 void set_type_pointertype_array(ir_type *tp, ir_type **pts) {
147 ir_type **old = pmap_get(type_pointertype_map, (void *)tp);
149 pmap_insert(type_pointertype_map, (void *)tp, (void *)pts);
153 * Return a flexible array containing all array
154 * types that have a given type as element type.
156 static ir_type **get_type_arraytype_array(ir_type *tp) {
158 if (!type_arraytype_map) type_arraytype_map = pmap_create();
160 if (pmap_contains(type_arraytype_map, (void *)tp)) {
161 res = (ir_type **) pmap_get(type_arraytype_map, (void *)tp);
163 res = NEW_ARR_F(ir_type *, 0);
164 pmap_insert(type_arraytype_map, (void *)tp, (void *)res);
170 void set_type_arraytype_array(ir_type *tp, ir_type **pts) {
171 ir_type **old = pmap_get(type_arraytype_map, (void *)tp);
173 pmap_insert(type_arraytype_map, (void *)tp, (void *)pts);
176 /*------------------------------------------------------------------*/
177 /* Accessing the out data structures. */
178 /* These routines only work properly if firm is in state */
179 /* trouts_consistent or trouts_inconsistent. */
180 /*------------------------------------------------------------------*/
182 /**------------------------------------------------------------------*/
183 /* Access routines for entities */
184 /**------------------------------------------------------------------*/
186 int get_entity_n_accesses(ir_entity *ent) {
189 assert(ent && is_entity(ent));
191 accs = get_entity_access_array(ent);
192 return ARR_LEN(accs);
195 ir_node *get_entity_access(ir_entity *ent, int pos) {
198 assert(0 <= pos && pos < get_entity_n_accesses(ent));
200 accs = get_entity_access_array(ent);
204 void add_entity_access(ir_entity *ent, ir_node *n) {
207 assert(ent && is_entity(ent));
208 assert(n && is_ir_node(n));
210 accs = get_entity_access_array(ent);
211 ARR_APP1(ir_node *, accs, n);
212 set_entity_access_array(ent, accs);
215 void set_entity_access(ir_entity *ent, int pos, ir_node *n) {
218 assert(0 <= pos && pos < get_entity_n_accesses(ent));
219 assert(n && is_ir_node(n));
221 accs = get_entity_access_array(ent);
225 /**------------------------------------------------------------------*/
227 int get_entity_n_references(ir_entity *ent) {
230 assert(ent && is_entity(ent));
232 refs = get_entity_reference_array(ent);
233 return ARR_LEN(refs);
236 ir_node *get_entity_reference(ir_entity *ent, int pos) {
239 assert(0 <= pos && pos < get_entity_n_references(ent));
241 refs = get_entity_reference_array(ent);
245 void add_entity_reference(ir_entity *ent, ir_node *n) {
248 assert(ent && is_entity(ent));
249 assert(n && is_ir_node(n));
251 refs = get_entity_reference_array(ent);
252 ARR_APP1(ir_node *, refs, n);
253 set_entity_reference_array(ent, refs);
256 void set_entity_reference(ir_entity *ent, int pos, ir_node *n) {
259 assert(0 <= pos && pos < get_entity_n_references(ent));
260 assert(n && is_ir_node(n));
262 refs = get_entity_reference_array(ent);
267 /**------------------------------------------------------------------*/
268 /* Access routines for types */
269 /**------------------------------------------------------------------*/
271 /* Number of Alloc nodes that create an instance of this type */
272 int get_type_n_allocs(ir_type *tp) {
275 assert(tp && is_type(tp));
277 allocs = get_type_alloc_array(tp);
278 return ARR_LEN(allocs);
281 /* Alloc node that creates an instance of this type */
282 ir_node *get_type_alloc(ir_type *tp, int pos) {
284 assert(0 <= pos && pos < get_type_n_allocs(tp));
286 allocs = get_type_alloc_array(tp);
290 void add_type_alloc(ir_type *tp, ir_node *n) {
293 assert(tp && is_type(tp));
294 assert(n && is_ir_node(n));
296 allocs = get_type_alloc_array(tp);
297 ARR_APP1(ir_node *, allocs, n);
298 set_type_alloc_array(tp, allocs);
301 void set_type_alloc(ir_type *tp, int pos, ir_node *n) {
304 assert(0 <= pos && pos < get_type_n_allocs(tp));
305 assert(n && is_ir_node(n));
307 allocs = get_type_alloc_array(tp);
311 /* Number of Cast nodes that create an instance of this type */
312 int get_type_n_casts(ir_type *tp) {
315 assert(tp && is_type(tp));
317 casts = get_type_cast_array(tp);
318 return ARR_LEN(casts);
322 int get_class_n_upcasts(ir_type *clss) {
323 int i, n_casts = get_type_n_casts(clss);
325 for (i = 0; i < n_casts; ++i) {
326 ir_node *cast = get_type_cast(clss, i);
327 if (is_Cast_upcast(cast)) n_instances ++;
332 int get_class_n_downcasts(ir_type *clss) {
333 int i, n_casts = get_type_n_casts(clss);
335 for (i = 0; i < n_casts; ++i) {
336 ir_node *cast = get_type_cast(clss, i);
337 if (is_Cast_downcast(cast)) n_instances ++;
343 /* Cast node that creates an instance of this type */
344 ir_node *get_type_cast(ir_type *tp, int pos) {
346 assert(0 <= pos && pos < get_type_n_casts(tp));
348 casts = get_type_cast_array(tp);
352 void add_type_cast(ir_type *tp, ir_node *n) {
355 assert(tp && is_type(tp));
356 assert(n && is_ir_node(n));
358 casts = get_type_cast_array(tp);
359 ARR_APP1(ir_node *, casts, n);
360 set_type_cast_array(tp, casts);
363 void set_type_cast(ir_type *tp, int pos, ir_node *n) {
366 assert(0 <= pos && pos < get_type_n_casts(tp));
367 assert(n && is_ir_node(n));
369 casts = get_type_cast_array(tp);
373 /**------------------------------------------------------------------*/
375 int get_type_n_pointertypes_to(ir_type *tp) {
378 assert(tp && is_type(tp));
380 pts = get_type_pointertype_array(tp);
384 ir_type *get_type_pointertype_to(ir_type *tp, int pos) {
387 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
389 pts = get_type_pointertype_array(tp);
393 void add_type_pointertype_to(ir_type *tp, ir_type *ptp) {
396 assert(tp && is_type(tp));
397 assert(ptp && is_Pointer_type(ptp));
399 pts = get_type_pointertype_array(tp);
400 ARR_APP1(ir_node *, pts, ptp);
401 set_type_pointertype_array(tp, pts);
404 void set_type_pointertype_to(ir_type *tp, int pos, ir_type *ptp) {
407 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
408 assert(ptp && is_Pointer_type(ptp));
410 pts = get_type_pointertype_array(tp);
415 /**------------------------------------------------------------------*/
417 int get_type_n_arraytypes_of(ir_type *tp) {
420 assert(tp && is_type(tp));
422 pts = get_type_arraytype_array(tp);
426 ir_type *get_type_arraytype_of(ir_type *tp, int pos) {
429 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
431 pts = get_type_arraytype_array(tp);
435 void add_type_arraytype_of(ir_type *tp, ir_type *atp) {
438 assert(tp && is_type(tp));
439 assert(atp && is_Array_type(atp));
441 pts = get_type_arraytype_array(tp);
442 ARR_APP1(ir_node *, pts, atp);
443 set_type_arraytype_array(tp, pts);
446 void set_type_arraytype_of(ir_type *tp, int pos, ir_type *atp) {
449 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
450 assert(atp && is_Array_type(atp));
452 pts = get_type_arraytype_array(tp);
456 /*------------------------------------------------------------------*/
457 /* Building and Removing the out datastructure */
458 /*------------------------------------------------------------------*/
460 static void init_trouts(void) {
464 /** The number of entities that can be accessed by this Sel node. */
465 static int get_Sel_n_accessed_entities(ir_node *sel) {
469 /** The entity that cat be accessed by this Sel node. */
470 static ir_entity *get_Sel_accessed_entity(ir_node *sel) {
471 return get_Sel_entity(sel);
474 /** An addr node is a SymConst or a Sel. */
475 static int get_addr_n_entities(ir_node *addr) {
478 switch (get_irn_opcode(addr)) {
480 /* Treat jack array sels? */
481 n_ents = get_Sel_n_accessed_entities(addr);
484 if (get_SymConst_kind(addr) == symconst_addr_ent) {
489 //assert(0 && "unexpected address expression");
496 /** An addr node is a SymConst or a Sel.
497 If Sel follow to outermost of compound. */
498 static ir_entity *get_addr_entity(ir_node *addr, int pos) {
501 switch (get_irn_opcode(addr)) {
503 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
504 while (is_Sel(get_Sel_ptr(addr))) {
505 addr = get_Sel_ptr(addr);
507 assert (0 <= pos && pos < get_Sel_n_accessed_entities(addr));
508 ent = get_Sel_accessed_entity(addr);
511 if (get_SymConst_kind(addr) == symconst_addr_ent) {
513 ent = get_SymConst_entity(addr);
523 static void chain_accesses(ir_node *n, void *env) {
527 if (get_irn_op(n) == op_Alloc) {
528 add_type_alloc(get_Alloc_type(n), n);
532 if (get_irn_op(n) == op_Cast) {
533 add_type_cast(get_Cast_type(n), n);
537 if (get_irn_op(n) == op_Sel) {
538 add_entity_reference(get_Sel_entity(n), n);
540 } else if (get_irn_op(n) == op_SymConst && (get_SymConst_kind(n) == symconst_addr_ent)) {
541 add_entity_reference(get_SymConst_entity(n), n);
546 addr = get_memop_ptr(n);
547 } else if (get_irn_op(n) == op_Call) {
548 addr = get_Call_ptr(n);
549 if (! is_Sel(addr)) return; /* Sels before Calls mean a Load / polymorphic Call. */
554 n_ents = get_addr_n_entities(addr); /* == 1 */
555 for (i = 0; i < n_ents; ++i) {
556 ir_entity *ent = get_addr_entity(addr, i);
558 add_entity_access(ent, n);
560 //add_unrecognized_access(n);
564 static void chain_types(ir_type *tp) {
565 if (is_Pointer_type(tp)) {
566 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
567 } else if (is_Array_type(tp)) {
568 add_type_arraytype_of(get_array_element_type(tp), tp);
572 irg_outs_state get_trouts_state(void) {
573 return irp->trouts_state;
575 void set_trouts_inconsistent(void) {
576 if (irp->trouts_state == outs_consistent)
577 irp->trouts_state = outs_inconsistent;
581 /* compute the field temperature. */
582 void compute_trouts(void) {
584 n_irgs = get_irp_n_irgs(),
585 n_types = get_irp_n_types();
590 /* Compute outs for irnodes. */
591 for (i = 0; i < n_irgs; i++) {
592 irg_walk_graph(get_irp_irg(i), NULL, chain_accesses, NULL);
594 walk_const_code(NULL, chain_accesses, NULL);
596 /* Compute outs for types */
597 for (i = 0; i < n_types; ++i) {
598 chain_types(get_irp_type(i));
601 irp->trouts_state = outs_consistent;
605 void free_trouts(void) {
607 if (entity_access_map) {
609 for (accs = (ir_node **)pmap_first(entity_access_map);
611 accs = (ir_node **)pmap_next(entity_access_map))
613 pmap_destroy(entity_access_map);
614 entity_access_map = NULL;
617 if (entity_reference_map) {
619 for (refs = (ir_node **)pmap_first(entity_reference_map);
621 refs = (ir_node **)pmap_next(entity_reference_map))
623 pmap_destroy(entity_reference_map);
624 entity_reference_map = NULL;
627 if (type_alloc_map) {
629 for (alls = (ir_node **)pmap_first(type_alloc_map);
631 alls = (ir_node **)pmap_next(type_alloc_map))
633 pmap_destroy(type_alloc_map);
634 type_alloc_map = NULL;
639 for (casts = (ir_node **)pmap_first(type_cast_map);
641 casts = (ir_node **)pmap_next(type_cast_map))
643 pmap_destroy(type_cast_map);
644 type_cast_map = NULL;
647 if (type_pointertype_map) {
649 for (pts = (ir_node **)pmap_first(type_pointertype_map);
651 pts = (ir_node **)pmap_next(type_pointertype_map))
653 pmap_destroy(type_pointertype_map);
654 type_pointertype_map = NULL;
657 if (type_arraytype_map) {
659 for (pts = (ir_node **)pmap_first(type_arraytype_map);
661 pts = (ir_node **)pmap_next(type_arraytype_map))
663 pmap_destroy(type_arraytype_map);
664 type_arraytype_map = NULL;
667 irp->trouts_state = outs_none;