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
39 /*------------------------------------------------------------------*/
40 /* We represent the fields in entities/types by hashmaps. */
41 /*------------------------------------------------------------------*/
43 static pmap *entity_access_map = NULL;
44 static pmap *entity_reference_map = NULL;
45 static pmap *type_alloc_map = NULL;
46 static pmap *type_cast_map = NULL;
47 static pmap *type_pointertype_map = NULL;
48 static pmap *type_arraytype_map = NULL;
51 * Return a flexible array containing all IR-nodes
52 * that access a given entity.
54 static ir_node **get_entity_access_array(const ir_entity *ent)
57 if (!entity_access_map) entity_access_map = pmap_create();
59 if (pmap_contains(entity_access_map, ent)) {
60 res = (ir_node **) pmap_get(entity_access_map, ent);
62 res = NEW_ARR_F(ir_node *, 0);
63 pmap_insert(entity_access_map, ent, (void *)res);
69 static void set_entity_access_array(const ir_entity *ent, ir_node **accs)
71 pmap_insert(entity_access_map, ent, (void *)accs);
75 * Return a flexible array containing all IR-nodes
76 * that reference a given entity.
78 static ir_node **get_entity_reference_array(const ir_entity *ent)
81 if (!entity_reference_map) entity_reference_map = pmap_create();
83 if (pmap_contains(entity_reference_map, ent)) {
84 res = (ir_node **) pmap_get(entity_reference_map, ent);
86 res = NEW_ARR_F(ir_node *, 0);
87 pmap_insert(entity_reference_map, ent, (void *)res);
93 static void set_entity_reference_array(const ir_entity *ent, ir_node **refs)
95 pmap_insert(entity_reference_map, ent, (void *)refs);
99 * Return a flexible array containing all IR-nodes
100 * that allocate a given type.
102 static ir_node **get_type_alloc_array(const ir_type *tp)
105 if (!type_alloc_map) type_alloc_map = pmap_create();
107 if (pmap_contains(type_alloc_map, tp)) {
108 res = (ir_node **) pmap_get(type_alloc_map, tp);
110 res = NEW_ARR_F(ir_node *, 0);
111 pmap_insert(type_alloc_map, tp, (void *)res);
117 static void set_type_alloc_array(const ir_type *tp, ir_node **alls)
119 pmap_insert(type_alloc_map, tp, (void *)alls);
123 * Return a flexible array containing all Cast-nodes
124 * that "create" a given type.
126 static ir_node **get_type_cast_array(const ir_type *tp)
129 if (!type_cast_map) type_cast_map = pmap_create();
131 if (pmap_contains(type_cast_map, tp)) {
132 res = (ir_node **) pmap_get(type_cast_map, tp);
134 res = NEW_ARR_F(ir_node *, 0);
135 pmap_insert(type_cast_map, tp, (void *)res);
140 static void set_type_cast_array(const ir_type *tp, ir_node **alls)
142 pmap_insert(type_cast_map, tp, (void *)alls);
146 * Return a flexible array containing all pointer
147 * types that points-to a given type.
149 static ir_type **get_type_pointertype_array(const ir_type *tp)
152 if (!type_pointertype_map) type_pointertype_map = pmap_create();
154 if (pmap_contains(type_pointertype_map, tp)) {
155 res = (ir_type **) pmap_get(type_pointertype_map, tp);
157 res = NEW_ARR_F(ir_type *, 0);
158 pmap_insert(type_pointertype_map, tp, (void *)res);
164 static void set_type_pointertype_array(const ir_type *tp, ir_type **pts)
166 pmap_insert(type_pointertype_map, tp, (void *)pts);
170 * Return a flexible array containing all array
171 * types that have a given type as element type.
173 static ir_type **get_type_arraytype_array(const ir_type *tp)
176 if (!type_arraytype_map) type_arraytype_map = pmap_create();
178 if (pmap_contains(type_arraytype_map, tp)) {
179 res = (ir_type **) pmap_get(type_arraytype_map, tp);
181 res = NEW_ARR_F(ir_type *, 0);
182 pmap_insert(type_arraytype_map, tp, (void *)res);
188 static void set_type_arraytype_array(const ir_type *tp, ir_type **pts)
190 pmap_insert(type_arraytype_map, tp, (void *)pts);
193 /*------------------------------------------------------------------*/
194 /* Accessing the out data structures. */
195 /* These routines only work properly if firm is in state */
196 /* trouts_consistent or trouts_inconsistent. */
197 /*------------------------------------------------------------------*/
199 /**------------------------------------------------------------------*/
200 /* Access routines for entities */
201 /**------------------------------------------------------------------*/
203 size_t get_entity_n_accesses(const ir_entity *ent)
207 assert(ent && is_entity(ent));
209 accs = get_entity_access_array(ent);
210 return ARR_LEN(accs);
213 ir_node *get_entity_access(const ir_entity *ent, size_t pos)
217 assert(pos < get_entity_n_accesses(ent));
219 accs = get_entity_access_array(ent);
223 static void add_entity_access(const ir_entity *ent, ir_node *n)
227 assert(ent && is_entity(ent));
228 assert(n && is_ir_node(n));
230 accs = get_entity_access_array(ent);
231 ARR_APP1(ir_node *, accs, n);
232 set_entity_access_array(ent, accs);
236 void set_entity_access(const ir_entity *ent, int pos, ir_node *n)
240 assert(0 <= pos && pos < get_entity_n_accesses(ent));
241 assert(n && is_ir_node(n));
243 accs = get_entity_access_array(ent);
248 /*------------------------------------------------------------------*/
250 size_t get_entity_n_references(const ir_entity *ent)
254 assert(ent && is_entity(ent));
256 refs = get_entity_reference_array(ent);
257 return ARR_LEN(refs);
260 ir_node *get_entity_reference(const ir_entity *ent, size_t pos)
264 assert( pos < get_entity_n_references(ent));
266 refs = get_entity_reference_array(ent);
270 static void add_entity_reference(const ir_entity *ent, ir_node *n)
274 assert(ent && is_entity(ent));
275 assert(n && is_ir_node(n));
277 refs = get_entity_reference_array(ent);
278 ARR_APP1(ir_node *, refs, n);
279 set_entity_reference_array(ent, refs);
283 void set_entity_reference(const ir_entity *ent, int pos, ir_node *n)
287 assert(0 <= pos && pos < get_entity_n_references(ent));
288 assert(n && is_ir_node(n));
290 refs = get_entity_reference_array(ent);
295 /**------------------------------------------------------------------*/
296 /* Access routines for types */
297 /**------------------------------------------------------------------*/
299 /* Number of Alloc nodes that create an instance of this type */
300 size_t get_type_n_allocs(const ir_type *tp)
304 assert(tp && is_type(tp));
306 allocs = get_type_alloc_array(tp);
307 return ARR_LEN(allocs);
310 /* Alloc node that creates an instance of this type */
311 ir_node *get_type_alloc(const ir_type *tp, size_t pos)
314 assert( pos < get_type_n_allocs(tp));
316 allocs = get_type_alloc_array(tp);
320 static void add_type_alloc(const ir_type *tp, ir_node *n)
324 assert(tp && is_type(tp));
325 assert(n && is_ir_node(n));
327 allocs = get_type_alloc_array(tp);
328 ARR_APP1(ir_node *, allocs, n);
329 set_type_alloc_array(tp, allocs);
333 void set_type_alloc(const ir_type *tp, int pos, ir_node *n)
337 assert(0 <= pos && pos < get_type_n_allocs(tp));
338 assert(n && is_ir_node(n));
340 allocs = get_type_alloc_array(tp);
345 /* Number of Cast nodes that create an instance of this type */
346 size_t get_type_n_casts(const ir_type *tp)
350 assert(tp && is_type(tp));
352 casts = get_type_cast_array(tp);
353 return ARR_LEN(casts);
357 size_t get_class_n_upcasts(const ir_type *clss)
359 size_t i, n_casts = get_type_n_casts(clss);
360 size_t n_instances = 0;
361 for (i = 0; i < n_casts; ++i) {
362 ir_node *cast = get_type_cast(clss, i);
363 if (is_Cast_upcast(cast))
369 size_t get_class_n_downcasts(const ir_type *clss)
371 size_t i, n_casts = get_type_n_casts(clss);
372 size_t n_instances = 0;
373 for (i = 0; i < n_casts; ++i) {
374 ir_node *cast = get_type_cast(clss, i);
375 if (is_Cast_downcast(cast))
381 ir_node *get_type_cast(const ir_type *tp, size_t pos)
384 assert(pos < get_type_n_casts(tp));
386 casts = get_type_cast_array(tp);
390 void add_type_cast(const ir_type *tp, ir_node *n)
394 assert(tp && is_type(tp));
395 assert(n && is_ir_node(n));
397 casts = get_type_cast_array(tp);
398 ARR_APP1(ir_node *, casts, n);
399 set_type_cast_array(tp, casts);
403 void set_type_cast(const ir_type *tp, size_t pos, ir_node *n)
407 assert(pos < get_type_n_casts(tp));
408 assert(n && is_ir_node(n));
410 casts = get_type_cast_array(tp);
415 /*------------------------------------------------------------------*/
417 size_t get_type_n_pointertypes_to(const ir_type *tp)
421 assert(tp && is_type(tp));
423 pts = get_type_pointertype_array(tp);
427 ir_type *get_type_pointertype_to(const ir_type *tp, size_t pos)
431 assert(pos < get_type_n_pointertypes_to(tp));
433 pts = get_type_pointertype_array(tp);
437 void add_type_pointertype_to(const ir_type *tp, ir_type *ptp)
441 assert(tp && is_type(tp));
442 assert(ptp && is_Pointer_type(ptp));
444 pts = get_type_pointertype_array(tp);
445 ARR_APP1(ir_type*, pts, ptp);
446 set_type_pointertype_array(tp, pts);
450 void set_type_pointertype_to(const ir_type *tp, int pos, ir_type *ptp)
454 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
455 assert(ptp && is_Pointer_type(ptp));
457 pts = get_type_pointertype_array(tp);
462 /*------------------------------------------------------------------*/
464 size_t get_type_n_arraytypes_of(const ir_type *tp)
468 assert(tp && is_type(tp));
470 pts = get_type_arraytype_array(tp);
474 ir_type *get_type_arraytype_of(const ir_type *tp, size_t pos)
478 assert(pos < get_type_n_arraytypes_of(tp));
480 pts = get_type_arraytype_array(tp);
484 void add_type_arraytype_of(const ir_type *tp, ir_type *atp)
488 assert(tp && is_type(tp));
489 assert(atp && is_Array_type(atp));
491 pts = get_type_arraytype_array(tp);
492 ARR_APP1(ir_type*, pts, atp);
493 set_type_arraytype_array(tp, pts);
497 void set_type_arraytype_of(const ir_type *tp, int pos, ir_type *atp)
501 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
502 assert(atp && is_Array_type(atp));
504 pts = get_type_arraytype_array(tp);
509 /*------------------------------------------------------------------*/
510 /* Building and Removing the out datastructure */
511 /*------------------------------------------------------------------*/
513 /** Initialize the trouts handling. */
514 static void init_trouts(void)
518 /** The number of entities that can be accessed by this Sel node. */
519 static int get_Sel_n_accessed_entities(const ir_node *sel)
525 /** The entity that cat be accessed by this Sel node. */
526 static ir_entity *get_Sel_accessed_entity(const ir_node *sel)
528 return get_Sel_entity(sel);
531 /** An addr node is a SymConst or a Sel. */
532 static int get_addr_n_entities(const ir_node *addr)
534 switch (get_irn_opcode(addr)) {
536 /* Treat jack array sels? */
537 return get_Sel_n_accessed_entities(addr);
539 if (get_SymConst_kind(addr) == symconst_addr_ent)
547 /** An addr node is a SymConst or a Sel.
548 If Sel follow to outermost of compound. */
549 static ir_entity *get_addr_entity(const ir_node *addr, int pos)
554 switch (get_irn_opcode(addr)) {
556 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
557 ptr = get_Sel_ptr(addr);
558 while (is_Sel(ptr)) {
560 ptr = get_Sel_ptr(addr);
562 assert(0 <= pos && pos < get_Sel_n_accessed_entities(addr));
563 return get_Sel_accessed_entity(addr);
565 if (get_SymConst_kind(addr) == symconst_addr_ent) {
567 return get_SymConst_entity(addr);
575 static void chain_accesses(ir_node *n, void *env)
582 add_type_alloc(get_Alloc_type(n), n);
584 } else if (is_Cast(n)) {
585 add_type_cast(get_Cast_type(n), n);
587 } else if (is_Sel(n)) {
588 add_entity_reference(get_Sel_entity(n), n);
590 } else if (is_SymConst_addr_ent(n)) {
591 add_entity_reference(get_SymConst_entity(n), n);
593 } else if (is_Store(n)) {
594 addr = get_Store_ptr(n);
595 } else if (is_Load(n)) {
596 addr = get_Load_ptr(n);
597 } else if (is_Call(n)) {
598 addr = get_Call_ptr(n);
599 if (! is_Sel(addr)) return; /* Sels before Calls mean a Load / polymorphic Call. */
604 n_ents = get_addr_n_entities(addr); /* == 1 */
605 for (i = 0; i < n_ents; ++i) {
606 ir_entity *ent = get_addr_entity(addr, i);
608 add_entity_access(ent, n);
610 //add_unrecognized_access(n);
615 * Handle chain types (pointer, array) by adding them to
618 static void chain_types(ir_type *tp)
620 if (is_Pointer_type(tp)) {
621 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
622 } else if (is_Array_type(tp)) {
623 add_type_arraytype_of(get_array_element_type(tp), tp);
627 void compute_trouts(void)
634 /* Compute outs for IR nodes. */
635 for (i = get_irp_n_irgs(); i > 0;) {
636 ir_graph *irg = get_irp_irg(--i);
637 irg_walk_graph(irg, NULL, chain_accesses, NULL);
639 walk_const_code(NULL, chain_accesses, NULL);
641 /* Compute outs for types */
642 for (i = get_irp_n_types(); i > 0;) {
643 ir_type *type = get_irp_type(--i);
648 void free_trouts(void)
650 if (entity_access_map) {
652 for (accs = (ir_node **)pmap_first(entity_access_map);
654 accs = (ir_node **)pmap_next(entity_access_map)) {
655 /* DEL_ARR_F(accs); */
657 pmap_destroy(entity_access_map);
658 entity_access_map = NULL;
661 if (entity_reference_map) {
663 for (refs = (ir_node **)pmap_first(entity_reference_map);
665 refs = (ir_node **)pmap_next(entity_reference_map)) {
666 /* DEL_ARR_F(refs); */
668 pmap_destroy(entity_reference_map);
669 entity_reference_map = NULL;
672 if (type_alloc_map) {
674 for (alls = (ir_node **)pmap_first(type_alloc_map);
676 alls = (ir_node **)pmap_next(type_alloc_map)) {
677 /* DEL_ARR_F(alls); */
679 pmap_destroy(type_alloc_map);
680 type_alloc_map = NULL;
685 for (casts = (ir_node **)pmap_first(type_cast_map);
687 casts = (ir_node **)pmap_next(type_cast_map)) {
688 /* DEL_ARR_F(alls); */
690 pmap_destroy(type_cast_map);
691 type_cast_map = NULL;
694 if (type_pointertype_map) {
696 for (pts = (ir_node **)pmap_first(type_pointertype_map);
698 pts = (ir_node **)pmap_next(type_pointertype_map)) {
699 /* DEL_ARR_F(pts); */
701 pmap_destroy(type_pointertype_map);
702 type_pointertype_map = NULL;
705 if (type_arraytype_map) {
707 for (pts = (ir_node **)pmap_first(type_arraytype_map);
709 pts = (ir_node **)pmap_next(type_arraytype_map)) {
710 /* DEL_ARR_F(pts); */
712 pmap_destroy(type_arraytype_map);
713 type_arraytype_map = NULL;