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 ir_node **old = (ir_node**)pmap_get(entity_access_map, ent);
73 pmap_insert(entity_access_map, ent, (void *)accs);
77 * Return a flexible array containing all IR-nodes
78 * that reference a given entity.
80 static ir_node **get_entity_reference_array(const ir_entity *ent)
83 if (!entity_reference_map) entity_reference_map = pmap_create();
85 if (pmap_contains(entity_reference_map, ent)) {
86 res = (ir_node **) pmap_get(entity_reference_map, ent);
88 res = NEW_ARR_F(ir_node *, 0);
89 pmap_insert(entity_reference_map, ent, (void *)res);
95 static void set_entity_reference_array(const ir_entity *ent, ir_node **refs)
97 ir_node **old = (ir_node**)pmap_get(entity_reference_map, ent);
99 pmap_insert(entity_reference_map, ent, (void *)refs);
103 * Return a flexible array containing all IR-nodes
104 * that allocate a given type.
106 static ir_node **get_type_alloc_array(const ir_type *tp)
109 if (!type_alloc_map) type_alloc_map = pmap_create();
111 if (pmap_contains(type_alloc_map, tp)) {
112 res = (ir_node **) pmap_get(type_alloc_map, tp);
114 res = NEW_ARR_F(ir_node *, 0);
115 pmap_insert(type_alloc_map, tp, (void *)res);
121 static void set_type_alloc_array(const ir_type *tp, ir_node **alls)
123 ir_node **old = (ir_node**)pmap_get(type_alloc_map, tp);
125 pmap_insert(type_alloc_map, tp, (void *)alls);
129 * Return a flexible array containing all Cast-nodes
130 * that "create" a given type.
132 static ir_node **get_type_cast_array(const ir_type *tp)
135 if (!type_cast_map) type_cast_map = pmap_create();
137 if (pmap_contains(type_cast_map, tp)) {
138 res = (ir_node **) pmap_get(type_cast_map, tp);
140 res = NEW_ARR_F(ir_node *, 0);
141 pmap_insert(type_cast_map, tp, (void *)res);
146 static void set_type_cast_array(const ir_type *tp, ir_node **alls)
148 ir_node **old = (ir_node**)pmap_get(type_cast_map, tp);
150 pmap_insert(type_cast_map, tp, (void *)alls);
154 * Return a flexible array containing all pointer
155 * types that points-to a given type.
157 static ir_type **get_type_pointertype_array(const ir_type *tp)
160 if (!type_pointertype_map) type_pointertype_map = pmap_create();
162 if (pmap_contains(type_pointertype_map, tp)) {
163 res = (ir_type **) pmap_get(type_pointertype_map, tp);
165 res = NEW_ARR_F(ir_type *, 0);
166 pmap_insert(type_pointertype_map, tp, (void *)res);
172 static void set_type_pointertype_array(const ir_type *tp, ir_type **pts)
174 ir_type **old = (ir_type**)pmap_get(type_pointertype_map, tp);
176 pmap_insert(type_pointertype_map, tp, (void *)pts);
180 * Return a flexible array containing all array
181 * types that have a given type as element type.
183 static ir_type **get_type_arraytype_array(const ir_type *tp)
186 if (!type_arraytype_map) type_arraytype_map = pmap_create();
188 if (pmap_contains(type_arraytype_map, tp)) {
189 res = (ir_type **) pmap_get(type_arraytype_map, tp);
191 res = NEW_ARR_F(ir_type *, 0);
192 pmap_insert(type_arraytype_map, tp, (void *)res);
198 static void set_type_arraytype_array(const ir_type *tp, ir_type **pts)
200 ir_type **old = (ir_type**)pmap_get(type_arraytype_map, tp);
202 pmap_insert(type_arraytype_map, tp, (void *)pts);
205 /*------------------------------------------------------------------*/
206 /* Accessing the out data structures. */
207 /* These routines only work properly if firm is in state */
208 /* trouts_consistent or trouts_inconsistent. */
209 /*------------------------------------------------------------------*/
211 /**------------------------------------------------------------------*/
212 /* Access routines for entities */
213 /**------------------------------------------------------------------*/
215 size_t get_entity_n_accesses(const ir_entity *ent)
219 assert(ent && is_entity(ent));
221 accs = get_entity_access_array(ent);
222 return ARR_LEN(accs);
225 ir_node *get_entity_access(const ir_entity *ent, size_t pos)
229 assert(pos < get_entity_n_accesses(ent));
231 accs = get_entity_access_array(ent);
235 static void add_entity_access(const ir_entity *ent, ir_node *n)
239 assert(ent && is_entity(ent));
240 assert(n && is_ir_node(n));
242 accs = get_entity_access_array(ent);
243 ARR_APP1(ir_node *, accs, n);
244 set_entity_access_array(ent, accs);
248 void set_entity_access(const ir_entity *ent, int pos, ir_node *n)
252 assert(0 <= pos && pos < get_entity_n_accesses(ent));
253 assert(n && is_ir_node(n));
255 accs = get_entity_access_array(ent);
260 /*------------------------------------------------------------------*/
262 size_t get_entity_n_references(const ir_entity *ent)
266 assert(ent && is_entity(ent));
268 refs = get_entity_reference_array(ent);
269 return ARR_LEN(refs);
272 ir_node *get_entity_reference(const ir_entity *ent, size_t pos)
276 assert( pos < get_entity_n_references(ent));
278 refs = get_entity_reference_array(ent);
282 static void add_entity_reference(const ir_entity *ent, ir_node *n)
286 assert(ent && is_entity(ent));
287 assert(n && is_ir_node(n));
289 refs = get_entity_reference_array(ent);
290 ARR_APP1(ir_node *, refs, n);
291 set_entity_reference_array(ent, refs);
295 void set_entity_reference(const ir_entity *ent, int pos, ir_node *n)
299 assert(0 <= pos && pos < get_entity_n_references(ent));
300 assert(n && is_ir_node(n));
302 refs = get_entity_reference_array(ent);
307 /**------------------------------------------------------------------*/
308 /* Access routines for types */
309 /**------------------------------------------------------------------*/
311 /* Number of Alloc nodes that create an instance of this type */
312 size_t get_type_n_allocs(const ir_type *tp)
316 assert(tp && is_type(tp));
318 allocs = get_type_alloc_array(tp);
319 return ARR_LEN(allocs);
322 /* Alloc node that creates an instance of this type */
323 ir_node *get_type_alloc(const ir_type *tp, size_t pos)
326 assert( pos < get_type_n_allocs(tp));
328 allocs = get_type_alloc_array(tp);
332 static void add_type_alloc(const ir_type *tp, ir_node *n)
336 assert(tp && is_type(tp));
337 assert(n && is_ir_node(n));
339 allocs = get_type_alloc_array(tp);
340 ARR_APP1(ir_node *, allocs, n);
341 set_type_alloc_array(tp, allocs);
345 void set_type_alloc(const ir_type *tp, int pos, ir_node *n)
349 assert(0 <= pos && pos < get_type_n_allocs(tp));
350 assert(n && is_ir_node(n));
352 allocs = get_type_alloc_array(tp);
357 /* Number of Cast nodes that create an instance of this type */
358 size_t get_type_n_casts(const ir_type *tp)
362 assert(tp && is_type(tp));
364 casts = get_type_cast_array(tp);
365 return ARR_LEN(casts);
369 size_t get_class_n_upcasts(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_upcast(cast))
381 size_t get_class_n_downcasts(const ir_type *clss)
383 size_t i, n_casts = get_type_n_casts(clss);
384 size_t n_instances = 0;
385 for (i = 0; i < n_casts; ++i) {
386 ir_node *cast = get_type_cast(clss, i);
387 if (is_Cast_downcast(cast))
393 /* Cast node that creates an instance of this type */
394 ir_node *get_type_cast(const ir_type *tp, size_t pos)
397 assert(pos < get_type_n_casts(tp));
399 casts = get_type_cast_array(tp);
403 void add_type_cast(const ir_type *tp, ir_node *n)
407 assert(tp && is_type(tp));
408 assert(n && is_ir_node(n));
410 casts = get_type_cast_array(tp);
411 ARR_APP1(ir_node *, casts, n);
412 set_type_cast_array(tp, casts);
416 void set_type_cast(const ir_type *tp, size_t pos, ir_node *n)
420 assert(pos < get_type_n_casts(tp));
421 assert(n && is_ir_node(n));
423 casts = get_type_cast_array(tp);
428 /*------------------------------------------------------------------*/
430 size_t get_type_n_pointertypes_to(const ir_type *tp)
434 assert(tp && is_type(tp));
436 pts = get_type_pointertype_array(tp);
440 ir_type *get_type_pointertype_to(const ir_type *tp, size_t pos)
444 assert(pos < get_type_n_pointertypes_to(tp));
446 pts = get_type_pointertype_array(tp);
450 void add_type_pointertype_to(const ir_type *tp, ir_type *ptp)
454 assert(tp && is_type(tp));
455 assert(ptp && is_Pointer_type(ptp));
457 pts = get_type_pointertype_array(tp);
458 ARR_APP1(ir_type*, pts, ptp);
459 set_type_pointertype_array(tp, pts);
463 void set_type_pointertype_to(const ir_type *tp, int pos, ir_type *ptp)
467 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
468 assert(ptp && is_Pointer_type(ptp));
470 pts = get_type_pointertype_array(tp);
475 /*------------------------------------------------------------------*/
477 size_t get_type_n_arraytypes_of(const ir_type *tp)
481 assert(tp && is_type(tp));
483 pts = get_type_arraytype_array(tp);
487 ir_type *get_type_arraytype_of(const ir_type *tp, size_t pos)
491 assert(pos < get_type_n_arraytypes_of(tp));
493 pts = get_type_arraytype_array(tp);
497 void add_type_arraytype_of(const ir_type *tp, ir_type *atp)
501 assert(tp && is_type(tp));
502 assert(atp && is_Array_type(atp));
504 pts = get_type_arraytype_array(tp);
505 ARR_APP1(ir_type*, pts, atp);
506 set_type_arraytype_array(tp, pts);
510 void set_type_arraytype_of(const ir_type *tp, int pos, ir_type *atp)
514 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
515 assert(atp && is_Array_type(atp));
517 pts = get_type_arraytype_array(tp);
522 /*------------------------------------------------------------------*/
523 /* Building and Removing the out datastructure */
524 /*------------------------------------------------------------------*/
526 /** Initialize the trouts handling. */
527 static void init_trouts(void)
531 /** The number of entities that can be accessed by this Sel node. */
532 static int get_Sel_n_accessed_entities(const ir_node *sel)
538 /** The entity that cat be accessed by this Sel node. */
539 static ir_entity *get_Sel_accessed_entity(const ir_node *sel)
541 return get_Sel_entity(sel);
544 /** An addr node is a SymConst or a Sel. */
545 static int get_addr_n_entities(const ir_node *addr)
547 switch (get_irn_opcode(addr)) {
549 /* Treat jack array sels? */
550 return get_Sel_n_accessed_entities(addr);
552 if (get_SymConst_kind(addr) == symconst_addr_ent)
560 /** An addr node is a SymConst or a Sel.
561 If Sel follow to outermost of compound. */
562 static ir_entity *get_addr_entity(const ir_node *addr, int pos)
567 switch (get_irn_opcode(addr)) {
569 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
570 ptr = get_Sel_ptr(addr);
571 while (is_Sel(ptr)) {
573 ptr = get_Sel_ptr(addr);
575 assert(0 <= pos && pos < get_Sel_n_accessed_entities(addr));
576 return get_Sel_accessed_entity(addr);
578 if (get_SymConst_kind(addr) == symconst_addr_ent) {
580 return get_SymConst_entity(addr);
588 static void chain_accesses(ir_node *n, void *env)
595 add_type_alloc(get_Alloc_type(n), n);
597 } else if (is_Cast(n)) {
598 add_type_cast(get_Cast_type(n), n);
600 } else if (is_Sel(n)) {
601 add_entity_reference(get_Sel_entity(n), n);
603 } else if (is_SymConst_addr_ent(n)) {
604 add_entity_reference(get_SymConst_entity(n), n);
606 } else if (is_memop(n)) {
607 addr = get_memop_ptr(n);
608 } else if (is_Call(n)) {
609 addr = get_Call_ptr(n);
610 if (! is_Sel(addr)) return; /* Sels before Calls mean a Load / polymorphic Call. */
615 n_ents = get_addr_n_entities(addr); /* == 1 */
616 for (i = 0; i < n_ents; ++i) {
617 ir_entity *ent = get_addr_entity(addr, i);
619 add_entity_access(ent, n);
621 //add_unrecognized_access(n);
626 * Handle chain types (pointer, array) by adding them to
629 static void chain_types(ir_type *tp)
631 if (is_Pointer_type(tp)) {
632 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
633 } else if (is_Array_type(tp)) {
634 add_type_arraytype_of(get_array_element_type(tp), tp);
638 /* compute the trouts data structures. */
639 void compute_trouts(void)
646 /* Compute outs for IR nodes. */
647 for (i = get_irp_n_irgs(); i > 0;) {
648 ir_graph *irg = get_irp_irg(--i);
649 irg_walk_graph(irg, NULL, chain_accesses, NULL);
651 walk_const_code(NULL, chain_accesses, NULL);
653 /* Compute outs for types */
654 for (i = get_irp_n_types(); i > 0;) {
655 ir_type *type = get_irp_type(--i);
660 void free_trouts(void)
662 if (entity_access_map) {
664 for (accs = (ir_node **)pmap_first(entity_access_map);
666 accs = (ir_node **)pmap_next(entity_access_map)) {
667 /* DEL_ARR_F(accs); */
669 pmap_destroy(entity_access_map);
670 entity_access_map = NULL;
673 if (entity_reference_map) {
675 for (refs = (ir_node **)pmap_first(entity_reference_map);
677 refs = (ir_node **)pmap_next(entity_reference_map)) {
678 /* DEL_ARR_F(refs); */
680 pmap_destroy(entity_reference_map);
681 entity_reference_map = NULL;
684 if (type_alloc_map) {
686 for (alls = (ir_node **)pmap_first(type_alloc_map);
688 alls = (ir_node **)pmap_next(type_alloc_map)) {
689 /* DEL_ARR_F(alls); */
691 pmap_destroy(type_alloc_map);
692 type_alloc_map = NULL;
697 for (casts = (ir_node **)pmap_first(type_cast_map);
699 casts = (ir_node **)pmap_next(type_cast_map)) {
700 /* DEL_ARR_F(alls); */
702 pmap_destroy(type_cast_map);
703 type_cast_map = NULL;
706 if (type_pointertype_map) {
708 for (pts = (ir_node **)pmap_first(type_pointertype_map);
710 pts = (ir_node **)pmap_next(type_pointertype_map)) {
711 /* DEL_ARR_F(pts); */
713 pmap_destroy(type_pointertype_map);
714 type_pointertype_map = NULL;
717 if (type_arraytype_map) {
719 for (pts = (ir_node **)pmap_first(type_arraytype_map);
721 pts = (ir_node **)pmap_next(type_arraytype_map)) {
722 /* DEL_ARR_F(pts); */
724 pmap_destroy(type_arraytype_map);
725 type_arraytype_map = NULL;