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 ir_node *get_type_cast(const ir_type *tp, size_t pos)
396 assert(pos < get_type_n_casts(tp));
398 casts = get_type_cast_array(tp);
402 void add_type_cast(const ir_type *tp, ir_node *n)
406 assert(tp && is_type(tp));
407 assert(n && is_ir_node(n));
409 casts = get_type_cast_array(tp);
410 ARR_APP1(ir_node *, casts, n);
411 set_type_cast_array(tp, casts);
415 void set_type_cast(const ir_type *tp, size_t pos, ir_node *n)
419 assert(pos < get_type_n_casts(tp));
420 assert(n && is_ir_node(n));
422 casts = get_type_cast_array(tp);
427 /*------------------------------------------------------------------*/
429 size_t get_type_n_pointertypes_to(const ir_type *tp)
433 assert(tp && is_type(tp));
435 pts = get_type_pointertype_array(tp);
439 ir_type *get_type_pointertype_to(const ir_type *tp, size_t pos)
443 assert(pos < get_type_n_pointertypes_to(tp));
445 pts = get_type_pointertype_array(tp);
449 void add_type_pointertype_to(const ir_type *tp, ir_type *ptp)
453 assert(tp && is_type(tp));
454 assert(ptp && is_Pointer_type(ptp));
456 pts = get_type_pointertype_array(tp);
457 ARR_APP1(ir_type*, pts, ptp);
458 set_type_pointertype_array(tp, pts);
462 void set_type_pointertype_to(const ir_type *tp, int pos, ir_type *ptp)
466 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
467 assert(ptp && is_Pointer_type(ptp));
469 pts = get_type_pointertype_array(tp);
474 /*------------------------------------------------------------------*/
476 size_t get_type_n_arraytypes_of(const ir_type *tp)
480 assert(tp && is_type(tp));
482 pts = get_type_arraytype_array(tp);
486 ir_type *get_type_arraytype_of(const ir_type *tp, size_t pos)
490 assert(pos < get_type_n_arraytypes_of(tp));
492 pts = get_type_arraytype_array(tp);
496 void add_type_arraytype_of(const ir_type *tp, ir_type *atp)
500 assert(tp && is_type(tp));
501 assert(atp && is_Array_type(atp));
503 pts = get_type_arraytype_array(tp);
504 ARR_APP1(ir_type*, pts, atp);
505 set_type_arraytype_array(tp, pts);
509 void set_type_arraytype_of(const ir_type *tp, int pos, ir_type *atp)
513 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
514 assert(atp && is_Array_type(atp));
516 pts = get_type_arraytype_array(tp);
521 /*------------------------------------------------------------------*/
522 /* Building and Removing the out datastructure */
523 /*------------------------------------------------------------------*/
525 /** Initialize the trouts handling. */
526 static void init_trouts(void)
530 /** The number of entities that can be accessed by this Sel node. */
531 static int get_Sel_n_accessed_entities(const ir_node *sel)
537 /** The entity that cat be accessed by this Sel node. */
538 static ir_entity *get_Sel_accessed_entity(const ir_node *sel)
540 return get_Sel_entity(sel);
543 /** An addr node is a SymConst or a Sel. */
544 static int get_addr_n_entities(const ir_node *addr)
546 switch (get_irn_opcode(addr)) {
548 /* Treat jack array sels? */
549 return get_Sel_n_accessed_entities(addr);
551 if (get_SymConst_kind(addr) == symconst_addr_ent)
559 /** An addr node is a SymConst or a Sel.
560 If Sel follow to outermost of compound. */
561 static ir_entity *get_addr_entity(const ir_node *addr, int pos)
566 switch (get_irn_opcode(addr)) {
568 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
569 ptr = get_Sel_ptr(addr);
570 while (is_Sel(ptr)) {
572 ptr = get_Sel_ptr(addr);
574 assert(0 <= pos && pos < get_Sel_n_accessed_entities(addr));
575 return get_Sel_accessed_entity(addr);
577 if (get_SymConst_kind(addr) == symconst_addr_ent) {
579 return get_SymConst_entity(addr);
587 static void chain_accesses(ir_node *n, void *env)
594 add_type_alloc(get_Alloc_type(n), n);
596 } else if (is_Cast(n)) {
597 add_type_cast(get_Cast_type(n), n);
599 } else if (is_Sel(n)) {
600 add_entity_reference(get_Sel_entity(n), n);
602 } else if (is_SymConst_addr_ent(n)) {
603 add_entity_reference(get_SymConst_entity(n), n);
605 } else if (is_Store(n)) {
606 addr = get_Store_ptr(n);
607 } else if (is_Load(n)) {
608 addr = get_Load_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 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;