2 * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief Reverse edges that reference types/entities.
23 * @author Goetz Lindenmaier
40 /*------------------------------------------------------------------*/
41 /* We represent the fields in entities/types by hashmaps. */
42 /*------------------------------------------------------------------*/
44 static pmap *entity_access_map = NULL;
45 static pmap *entity_reference_map = NULL;
46 static pmap *type_alloc_map = NULL;
47 static pmap *type_cast_map = NULL;
48 static pmap *type_pointertype_map = NULL;
49 static pmap *type_arraytype_map = NULL;
52 * Return a flexible array containing all IR-nodes
53 * that access a given entity.
55 static ir_node **get_entity_access_array(const ir_entity *ent)
58 if (!entity_access_map) entity_access_map = pmap_create();
60 if (pmap_contains(entity_access_map, ent)) {
61 res = (ir_node **) pmap_get(entity_access_map, ent);
63 res = NEW_ARR_F(ir_node *, 0);
64 pmap_insert(entity_access_map, ent, (void *)res);
70 static void set_entity_access_array(const ir_entity *ent, ir_node **accs)
72 ir_node **old = (ir_node**)pmap_get(entity_access_map, ent);
74 pmap_insert(entity_access_map, ent, (void *)accs);
78 * Return a flexible array containing all IR-nodes
79 * that reference a given entity.
81 static ir_node **get_entity_reference_array(const ir_entity *ent)
84 if (!entity_reference_map) entity_reference_map = pmap_create();
86 if (pmap_contains(entity_reference_map, ent)) {
87 res = (ir_node **) pmap_get(entity_reference_map, ent);
89 res = NEW_ARR_F(ir_node *, 0);
90 pmap_insert(entity_reference_map, ent, (void *)res);
96 static void set_entity_reference_array(const ir_entity *ent, ir_node **refs)
98 ir_node **old = (ir_node**)pmap_get(entity_reference_map, ent);
100 pmap_insert(entity_reference_map, ent, (void *)refs);
104 * Return a flexible array containing all IR-nodes
105 * that allocate a given type.
107 static ir_node **get_type_alloc_array(const ir_type *tp)
110 if (!type_alloc_map) type_alloc_map = pmap_create();
112 if (pmap_contains(type_alloc_map, tp)) {
113 res = (ir_node **) pmap_get(type_alloc_map, tp);
115 res = NEW_ARR_F(ir_node *, 0);
116 pmap_insert(type_alloc_map, tp, (void *)res);
122 static void set_type_alloc_array(const ir_type *tp, ir_node **alls)
124 ir_node **old = (ir_node**)pmap_get(type_alloc_map, tp);
126 pmap_insert(type_alloc_map, tp, (void *)alls);
130 * Return a flexible array containing all Cast-nodes
131 * that "create" a given type.
133 static ir_node **get_type_cast_array(const ir_type *tp)
136 if (!type_cast_map) type_cast_map = pmap_create();
138 if (pmap_contains(type_cast_map, tp)) {
139 res = (ir_node **) pmap_get(type_cast_map, tp);
141 res = NEW_ARR_F(ir_node *, 0);
142 pmap_insert(type_cast_map, tp, (void *)res);
147 static void set_type_cast_array(const ir_type *tp, ir_node **alls)
149 ir_node **old = (ir_node**)pmap_get(type_cast_map, tp);
151 pmap_insert(type_cast_map, tp, (void *)alls);
155 * Return a flexible array containing all pointer
156 * types that points-to a given type.
158 static ir_type **get_type_pointertype_array(const ir_type *tp)
161 if (!type_pointertype_map) type_pointertype_map = pmap_create();
163 if (pmap_contains(type_pointertype_map, tp)) {
164 res = (ir_type **) pmap_get(type_pointertype_map, tp);
166 res = NEW_ARR_F(ir_type *, 0);
167 pmap_insert(type_pointertype_map, tp, (void *)res);
173 static void set_type_pointertype_array(const ir_type *tp, ir_type **pts)
175 ir_type **old = (ir_type**)pmap_get(type_pointertype_map, tp);
177 pmap_insert(type_pointertype_map, tp, (void *)pts);
181 * Return a flexible array containing all array
182 * types that have a given type as element type.
184 static ir_type **get_type_arraytype_array(const ir_type *tp)
187 if (!type_arraytype_map) type_arraytype_map = pmap_create();
189 if (pmap_contains(type_arraytype_map, tp)) {
190 res = (ir_type **) pmap_get(type_arraytype_map, tp);
192 res = NEW_ARR_F(ir_type *, 0);
193 pmap_insert(type_arraytype_map, tp, (void *)res);
199 static void set_type_arraytype_array(const ir_type *tp, ir_type **pts)
201 ir_type **old = (ir_type**)pmap_get(type_arraytype_map, tp);
203 pmap_insert(type_arraytype_map, tp, (void *)pts);
206 /*------------------------------------------------------------------*/
207 /* Accessing the out data structures. */
208 /* These routines only work properly if firm is in state */
209 /* trouts_consistent or trouts_inconsistent. */
210 /*------------------------------------------------------------------*/
212 /**------------------------------------------------------------------*/
213 /* Access routines for entities */
214 /**------------------------------------------------------------------*/
216 size_t get_entity_n_accesses(const ir_entity *ent)
220 assert(ent && is_entity(ent));
222 accs = get_entity_access_array(ent);
223 return ARR_LEN(accs);
226 ir_node *get_entity_access(const ir_entity *ent, size_t pos)
230 assert(pos < get_entity_n_accesses(ent));
232 accs = get_entity_access_array(ent);
236 static void add_entity_access(const ir_entity *ent, ir_node *n)
240 assert(ent && is_entity(ent));
241 assert(n && is_ir_node(n));
243 accs = get_entity_access_array(ent);
244 ARR_APP1(ir_node *, accs, n);
245 set_entity_access_array(ent, accs);
249 void set_entity_access(const ir_entity *ent, int pos, ir_node *n)
253 assert(0 <= pos && pos < get_entity_n_accesses(ent));
254 assert(n && is_ir_node(n));
256 accs = get_entity_access_array(ent);
261 /*------------------------------------------------------------------*/
263 size_t get_entity_n_references(const ir_entity *ent)
267 assert(ent && is_entity(ent));
269 refs = get_entity_reference_array(ent);
270 return ARR_LEN(refs);
273 ir_node *get_entity_reference(const ir_entity *ent, size_t pos)
277 assert( pos < get_entity_n_references(ent));
279 refs = get_entity_reference_array(ent);
283 static void add_entity_reference(const ir_entity *ent, ir_node *n)
287 assert(ent && is_entity(ent));
288 assert(n && is_ir_node(n));
290 refs = get_entity_reference_array(ent);
291 ARR_APP1(ir_node *, refs, n);
292 set_entity_reference_array(ent, refs);
296 void set_entity_reference(const ir_entity *ent, int pos, ir_node *n)
300 assert(0 <= pos && pos < get_entity_n_references(ent));
301 assert(n && is_ir_node(n));
303 refs = get_entity_reference_array(ent);
308 /**------------------------------------------------------------------*/
309 /* Access routines for types */
310 /**------------------------------------------------------------------*/
312 /* Number of Alloc nodes that create an instance of this type */
313 size_t get_type_n_allocs(const ir_type *tp)
317 assert(tp && is_type(tp));
319 allocs = get_type_alloc_array(tp);
320 return ARR_LEN(allocs);
323 /* Alloc node that creates an instance of this type */
324 ir_node *get_type_alloc(const ir_type *tp, size_t pos)
327 assert( pos < get_type_n_allocs(tp));
329 allocs = get_type_alloc_array(tp);
333 static void add_type_alloc(const ir_type *tp, ir_node *n)
337 assert(tp && is_type(tp));
338 assert(n && is_ir_node(n));
340 allocs = get_type_alloc_array(tp);
341 ARR_APP1(ir_node *, allocs, n);
342 set_type_alloc_array(tp, allocs);
346 void set_type_alloc(const ir_type *tp, int pos, ir_node *n)
350 assert(0 <= pos && pos < get_type_n_allocs(tp));
351 assert(n && is_ir_node(n));
353 allocs = get_type_alloc_array(tp);
358 /* Number of Cast nodes that create an instance of this type */
359 size_t get_type_n_casts(const ir_type *tp)
363 assert(tp && is_type(tp));
365 casts = get_type_cast_array(tp);
366 return ARR_LEN(casts);
370 size_t get_class_n_upcasts(const ir_type *clss)
372 size_t i, n_casts = get_type_n_casts(clss);
373 size_t n_instances = 0;
374 for (i = 0; i < n_casts; ++i) {
375 ir_node *cast = get_type_cast(clss, i);
376 if (is_Cast_upcast(cast))
382 size_t get_class_n_downcasts(const ir_type *clss)
384 size_t i, n_casts = get_type_n_casts(clss);
385 size_t n_instances = 0;
386 for (i = 0; i < n_casts; ++i) {
387 ir_node *cast = get_type_cast(clss, i);
388 if (is_Cast_downcast(cast))
394 /* Cast node that creates an instance of this type */
395 ir_node *get_type_cast(const ir_type *tp, size_t pos)
398 assert(pos < get_type_n_casts(tp));
400 casts = get_type_cast_array(tp);
404 void add_type_cast(const ir_type *tp, ir_node *n)
408 assert(tp && is_type(tp));
409 assert(n && is_ir_node(n));
411 casts = get_type_cast_array(tp);
412 ARR_APP1(ir_node *, casts, n);
413 set_type_cast_array(tp, casts);
417 void set_type_cast(const ir_type *tp, size_t pos, ir_node *n)
421 assert(pos < get_type_n_casts(tp));
422 assert(n && is_ir_node(n));
424 casts = get_type_cast_array(tp);
429 /*------------------------------------------------------------------*/
431 size_t get_type_n_pointertypes_to(const ir_type *tp)
435 assert(tp && is_type(tp));
437 pts = get_type_pointertype_array(tp);
441 ir_type *get_type_pointertype_to(const ir_type *tp, size_t pos)
445 assert(pos < get_type_n_pointertypes_to(tp));
447 pts = get_type_pointertype_array(tp);
451 void add_type_pointertype_to(const ir_type *tp, ir_type *ptp)
455 assert(tp && is_type(tp));
456 assert(ptp && is_Pointer_type(ptp));
458 pts = get_type_pointertype_array(tp);
459 ARR_APP1(ir_type*, pts, ptp);
460 set_type_pointertype_array(tp, pts);
464 void set_type_pointertype_to(const ir_type *tp, int pos, ir_type *ptp)
468 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
469 assert(ptp && is_Pointer_type(ptp));
471 pts = get_type_pointertype_array(tp);
476 /*------------------------------------------------------------------*/
478 size_t get_type_n_arraytypes_of(const ir_type *tp)
482 assert(tp && is_type(tp));
484 pts = get_type_arraytype_array(tp);
488 ir_type *get_type_arraytype_of(const ir_type *tp, size_t pos)
492 assert(pos < get_type_n_arraytypes_of(tp));
494 pts = get_type_arraytype_array(tp);
498 void add_type_arraytype_of(const ir_type *tp, ir_type *atp)
502 assert(tp && is_type(tp));
503 assert(atp && is_Array_type(atp));
505 pts = get_type_arraytype_array(tp);
506 ARR_APP1(ir_type*, pts, atp);
507 set_type_arraytype_array(tp, pts);
511 void set_type_arraytype_of(const ir_type *tp, int pos, ir_type *atp)
515 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
516 assert(atp && is_Array_type(atp));
518 pts = get_type_arraytype_array(tp);
523 /*------------------------------------------------------------------*/
524 /* Building and Removing the out datastructure */
525 /*------------------------------------------------------------------*/
527 /** Initialize the trouts handling. */
528 static void init_trouts(void)
532 /** The number of entities that can be accessed by this Sel node. */
533 static int get_Sel_n_accessed_entities(const ir_node *sel)
539 /** The entity that cat be accessed by this Sel node. */
540 static ir_entity *get_Sel_accessed_entity(const ir_node *sel)
542 return get_Sel_entity(sel);
545 /** An addr node is a SymConst or a Sel. */
546 static int get_addr_n_entities(const ir_node *addr)
548 switch (get_irn_opcode(addr)) {
550 /* Treat jack array sels? */
551 return get_Sel_n_accessed_entities(addr);
553 if (get_SymConst_kind(addr) == symconst_addr_ent)
561 /** An addr node is a SymConst or a Sel.
562 If Sel follow to outermost of compound. */
563 static ir_entity *get_addr_entity(const ir_node *addr, int pos)
568 switch (get_irn_opcode(addr)) {
570 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
571 ptr = get_Sel_ptr(addr);
572 while (is_Sel(ptr)) {
574 ptr = get_Sel_ptr(addr);
576 assert(0 <= pos && pos < get_Sel_n_accessed_entities(addr));
577 return get_Sel_accessed_entity(addr);
579 if (get_SymConst_kind(addr) == symconst_addr_ent) {
581 return get_SymConst_entity(addr);
589 static void chain_accesses(ir_node *n, void *env)
596 add_type_alloc(get_Alloc_type(n), n);
598 } else if (is_Cast(n)) {
599 add_type_cast(get_Cast_type(n), n);
601 } else if (is_Sel(n)) {
602 add_entity_reference(get_Sel_entity(n), n);
604 } else if (is_SymConst_addr_ent(n)) {
605 add_entity_reference(get_SymConst_entity(n), n);
607 } else if (is_memop(n)) {
608 addr = get_memop_ptr(n);
609 } else if (is_Call(n)) {
610 addr = get_Call_ptr(n);
611 if (! is_Sel(addr)) return; /* Sels before Calls mean a Load / polymorphic Call. */
616 n_ents = get_addr_n_entities(addr); /* == 1 */
617 for (i = 0; i < n_ents; ++i) {
618 ir_entity *ent = get_addr_entity(addr, i);
620 add_entity_access(ent, n);
622 //add_unrecognized_access(n);
627 * Handle chain types (pointer, array) by adding them to
630 static void chain_types(ir_type *tp)
632 if (is_Pointer_type(tp)) {
633 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
634 } else if (is_Array_type(tp)) {
635 add_type_arraytype_of(get_array_element_type(tp), tp);
639 irg_outs_state get_trouts_state(void)
641 return irp->trouts_state;
644 void set_trouts_inconsistent(void)
646 if (irp->trouts_state == outs_consistent)
647 irp->trouts_state = outs_inconsistent;
650 /* compute the trouts data structures. */
651 void compute_trouts(void)
658 /* Compute outs for IR nodes. */
659 for (i = get_irp_n_irgs(); i > 0;) {
660 ir_graph *irg = get_irp_irg(--i);
661 irg_walk_graph(irg, NULL, chain_accesses, NULL);
663 walk_const_code(NULL, chain_accesses, NULL);
665 /* Compute outs for types */
666 for (i = get_irp_n_types(); i > 0;) {
667 ir_type *type = get_irp_type(--i);
671 irp->trouts_state = outs_consistent;
674 void free_trouts(void)
676 if (entity_access_map) {
678 for (accs = (ir_node **)pmap_first(entity_access_map);
680 accs = (ir_node **)pmap_next(entity_access_map)) {
681 /* DEL_ARR_F(accs); */
683 pmap_destroy(entity_access_map);
684 entity_access_map = NULL;
687 if (entity_reference_map) {
689 for (refs = (ir_node **)pmap_first(entity_reference_map);
691 refs = (ir_node **)pmap_next(entity_reference_map)) {
692 /* DEL_ARR_F(refs); */
694 pmap_destroy(entity_reference_map);
695 entity_reference_map = NULL;
698 if (type_alloc_map) {
700 for (alls = (ir_node **)pmap_first(type_alloc_map);
702 alls = (ir_node **)pmap_next(type_alloc_map)) {
703 /* DEL_ARR_F(alls); */
705 pmap_destroy(type_alloc_map);
706 type_alloc_map = NULL;
711 for (casts = (ir_node **)pmap_first(type_cast_map);
713 casts = (ir_node **)pmap_next(type_cast_map)) {
714 /* DEL_ARR_F(alls); */
716 pmap_destroy(type_cast_map);
717 type_cast_map = NULL;
720 if (type_pointertype_map) {
722 for (pts = (ir_node **)pmap_first(type_pointertype_map);
724 pts = (ir_node **)pmap_next(type_pointertype_map)) {
725 /* DEL_ARR_F(pts); */
727 pmap_destroy(type_pointertype_map);
728 type_pointertype_map = NULL;
731 if (type_arraytype_map) {
733 for (pts = (ir_node **)pmap_first(type_arraytype_map);
735 pts = (ir_node **)pmap_next(type_arraytype_map)) {
736 /* DEL_ARR_F(pts); */
738 pmap_destroy(type_arraytype_map);
739 type_arraytype_map = NULL;
742 irp->trouts_state = outs_none;