2 * Copyright (C) 1995-2008 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
42 /*------------------------------------------------------------------*/
43 /* We represent the fields in entities/types by hashmaps. */
44 /*------------------------------------------------------------------*/
46 static pmap *entity_access_map = NULL;
47 static pmap *entity_reference_map = NULL;
48 static pmap *type_alloc_map = NULL;
49 static pmap *type_cast_map = NULL;
50 static pmap *type_pointertype_map = NULL;
51 static pmap *type_arraytype_map = NULL;
54 * Return a flexible array containing all IR-nodes
55 * that access a given entity.
57 static ir_node **get_entity_access_array(const ir_entity *ent) {
59 if (!entity_access_map) entity_access_map = pmap_create();
61 if (pmap_contains(entity_access_map, ent)) {
62 res = (ir_node **) pmap_get(entity_access_map, ent);
64 res = NEW_ARR_F(ir_node *, 0);
65 pmap_insert(entity_access_map, ent, (void *)res);
71 static void set_entity_access_array(const ir_entity *ent, ir_node **accs) {
72 ir_node **old = 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) {
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) {
96 ir_node **old = pmap_get(entity_reference_map, ent);
98 pmap_insert(entity_reference_map, ent, (void *)refs);
102 * Return a flexible array containing all IR-nodes
103 * that allocate a given type.
105 static ir_node **get_type_alloc_array(const ir_type *tp) {
107 if (!type_alloc_map) type_alloc_map = pmap_create();
109 if (pmap_contains(type_alloc_map, tp)) {
110 res = (ir_node **) pmap_get(type_alloc_map, tp);
112 res = NEW_ARR_F(ir_node *, 0);
113 pmap_insert(type_alloc_map, tp, (void *)res);
119 static void set_type_alloc_array(const ir_type *tp, ir_node **alls) {
120 ir_node **old = pmap_get(type_alloc_map, tp);
122 pmap_insert(type_alloc_map, tp, (void *)alls);
126 * Return a flexible array containing all Cast-nodes
127 * that "create" a given type.
129 static ir_node **get_type_cast_array(const ir_type *tp) {
131 if (!type_cast_map) type_cast_map = pmap_create();
133 if (pmap_contains(type_cast_map, tp)) {
134 res = (ir_node **) pmap_get(type_cast_map, tp);
136 res = NEW_ARR_F(ir_node *, 0);
137 pmap_insert(type_cast_map, tp, (void *)res);
142 static void set_type_cast_array(const ir_type *tp, ir_node **alls) {
143 ir_node **old = pmap_get(type_cast_map, tp);
145 pmap_insert(type_cast_map, tp, (void *)alls);
149 * Return a flexible array containing all pointer
150 * types that points-to a given type.
152 static ir_type **get_type_pointertype_array(const ir_type *tp) {
154 if (!type_pointertype_map) type_pointertype_map = pmap_create();
156 if (pmap_contains(type_pointertype_map, tp)) {
157 res = (ir_type **) pmap_get(type_pointertype_map, tp);
159 res = NEW_ARR_F(ir_type *, 0);
160 pmap_insert(type_pointertype_map, tp, (void *)res);
166 static void set_type_pointertype_array(const ir_type *tp, ir_type **pts) {
167 ir_type **old = pmap_get(type_pointertype_map, tp);
169 pmap_insert(type_pointertype_map, tp, (void *)pts);
173 * Return a flexible array containing all array
174 * types that have a given type as element type.
176 static ir_type **get_type_arraytype_array(const ir_type *tp) {
178 if (!type_arraytype_map) type_arraytype_map = pmap_create();
180 if (pmap_contains(type_arraytype_map, tp)) {
181 res = (ir_type **) pmap_get(type_arraytype_map, tp);
183 res = NEW_ARR_F(ir_type *, 0);
184 pmap_insert(type_arraytype_map, tp, (void *)res);
190 void set_type_arraytype_array(const ir_type *tp, ir_type **pts) {
191 ir_type **old = pmap_get(type_arraytype_map, tp);
193 pmap_insert(type_arraytype_map, tp, (void *)pts);
196 /*------------------------------------------------------------------*/
197 /* Accessing the out data structures. */
198 /* These routines only work properly if firm is in state */
199 /* trouts_consistent or trouts_inconsistent. */
200 /*------------------------------------------------------------------*/
202 /**------------------------------------------------------------------*/
203 /* Access routines for entities */
204 /**------------------------------------------------------------------*/
206 int get_entity_n_accesses(const ir_entity *ent) {
209 assert(ent && is_entity(ent));
211 accs = get_entity_access_array(ent);
212 return ARR_LEN(accs);
215 ir_node *get_entity_access(const ir_entity *ent, int pos) {
218 assert(0 <= pos && pos < get_entity_n_accesses(ent));
220 accs = get_entity_access_array(ent);
224 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);
235 void set_entity_access(const ir_entity *ent, int pos, ir_node *n) {
238 assert(0 <= pos && pos < get_entity_n_accesses(ent));
239 assert(n && is_ir_node(n));
241 accs = get_entity_access_array(ent);
245 /*------------------------------------------------------------------*/
247 int get_entity_n_references(const ir_entity *ent) {
250 assert(ent && is_entity(ent));
252 refs = get_entity_reference_array(ent);
253 return ARR_LEN(refs);
256 ir_node *get_entity_reference(const ir_entity *ent, int pos) {
259 assert(0 <= pos && pos < get_entity_n_references(ent));
261 refs = get_entity_reference_array(ent);
265 static void add_entity_reference(const ir_entity *ent, ir_node *n) {
268 assert(ent && is_entity(ent));
269 assert(n && is_ir_node(n));
271 refs = get_entity_reference_array(ent);
272 ARR_APP1(ir_node *, refs, n);
273 set_entity_reference_array(ent, refs);
276 void set_entity_reference(const ir_entity *ent, int pos, ir_node *n) {
279 assert(0 <= pos && pos < get_entity_n_references(ent));
280 assert(n && is_ir_node(n));
282 refs = get_entity_reference_array(ent);
287 /**------------------------------------------------------------------*/
288 /* Access routines for types */
289 /**------------------------------------------------------------------*/
291 /* Number of Alloc nodes that create an instance of this type */
292 int get_type_n_allocs(const ir_type *tp) {
295 assert(tp && is_type(tp));
297 allocs = get_type_alloc_array(tp);
298 return ARR_LEN(allocs);
301 /* Alloc node that creates an instance of this type */
302 ir_node *get_type_alloc(const ir_type *tp, int pos) {
304 assert(0 <= pos && pos < get_type_n_allocs(tp));
306 allocs = get_type_alloc_array(tp);
310 static void add_type_alloc(const ir_type *tp, ir_node *n) {
313 assert(tp && is_type(tp));
314 assert(n && is_ir_node(n));
316 allocs = get_type_alloc_array(tp);
317 ARR_APP1(ir_node *, allocs, n);
318 set_type_alloc_array(tp, allocs);
321 void set_type_alloc(const ir_type *tp, int pos, ir_node *n) {
324 assert(0 <= pos && pos < get_type_n_allocs(tp));
325 assert(n && is_ir_node(n));
327 allocs = get_type_alloc_array(tp);
331 /* Number of Cast nodes that create an instance of this type */
332 int get_type_n_casts(const ir_type *tp) {
335 assert(tp && is_type(tp));
337 casts = get_type_cast_array(tp);
338 return ARR_LEN(casts);
342 int get_class_n_upcasts(const ir_type *clss) {
343 int i, n_casts = get_type_n_casts(clss);
345 for (i = 0; i < n_casts; ++i) {
346 ir_node *cast = get_type_cast(clss, i);
347 if (is_Cast_upcast(cast))
353 int get_class_n_downcasts(const ir_type *clss) {
354 int i, n_casts = get_type_n_casts(clss);
356 for (i = 0; i < n_casts; ++i) {
357 ir_node *cast = get_type_cast(clss, i);
358 if (is_Cast_downcast(cast))
364 /* Cast node that creates an instance of this type */
365 ir_node *get_type_cast(const ir_type *tp, int pos) {
367 assert(0 <= pos && pos < get_type_n_casts(tp));
369 casts = get_type_cast_array(tp);
373 void add_type_cast(const ir_type *tp, ir_node *n) {
376 assert(tp && is_type(tp));
377 assert(n && is_ir_node(n));
379 casts = get_type_cast_array(tp);
380 ARR_APP1(ir_node *, casts, n);
381 set_type_cast_array(tp, casts);
384 void set_type_cast(const ir_type *tp, int pos, ir_node *n) {
387 assert(0 <= pos && pos < get_type_n_casts(tp));
388 assert(n && is_ir_node(n));
390 casts = get_type_cast_array(tp);
394 /*------------------------------------------------------------------*/
396 int get_type_n_pointertypes_to(const ir_type *tp) {
399 assert(tp && is_type(tp));
401 pts = get_type_pointertype_array(tp);
405 ir_type *get_type_pointertype_to(const ir_type *tp, int pos) {
408 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
410 pts = get_type_pointertype_array(tp);
414 void add_type_pointertype_to(const ir_type *tp, ir_type *ptp) {
417 assert(tp && is_type(tp));
418 assert(ptp && is_Pointer_type(ptp));
420 pts = get_type_pointertype_array(tp);
421 ARR_APP1(ir_node *, pts, ptp);
422 set_type_pointertype_array(tp, pts);
425 void set_type_pointertype_to(const ir_type *tp, int pos, ir_type *ptp) {
428 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
429 assert(ptp && is_Pointer_type(ptp));
431 pts = get_type_pointertype_array(tp);
436 /*------------------------------------------------------------------*/
438 int get_type_n_arraytypes_of(const ir_type *tp) {
441 assert(tp && is_type(tp));
443 pts = get_type_arraytype_array(tp);
447 ir_type *get_type_arraytype_of(const ir_type *tp, int pos) {
450 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
452 pts = get_type_arraytype_array(tp);
456 void add_type_arraytype_of(const ir_type *tp, ir_type *atp) {
459 assert(tp && is_type(tp));
460 assert(atp && is_Array_type(atp));
462 pts = get_type_arraytype_array(tp);
463 ARR_APP1(ir_node *, pts, atp);
464 set_type_arraytype_array(tp, pts);
467 void set_type_arraytype_of(const ir_type *tp, int pos, ir_type *atp) {
470 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
471 assert(atp && is_Array_type(atp));
473 pts = get_type_arraytype_array(tp);
477 /*------------------------------------------------------------------*/
478 /* Building and Removing the out datastructure */
479 /*------------------------------------------------------------------*/
481 /** Initialize the trouts handling. */
482 static void init_trouts(void) {
485 /** The number of entities that can be accessed by this Sel node. */
486 static int get_Sel_n_accessed_entities(const ir_node *sel) {
491 /** The entity that cat be accessed by this Sel node. */
492 static ir_entity *get_Sel_accessed_entity(const ir_node *sel) {
493 return get_Sel_entity(sel);
496 /** An addr node is a SymConst or a Sel. */
497 static int get_addr_n_entities(const ir_node *addr) {
500 switch (get_irn_opcode(addr)) {
502 /* Treat jack array sels? */
503 n_ents = get_Sel_n_accessed_entities(addr);
506 if (get_SymConst_kind(addr) == symconst_addr_ent) {
511 //assert(0 && "unexpected address expression");
518 /** An addr node is a SymConst or a Sel.
519 If Sel follow to outermost of compound. */
520 static ir_entity *get_addr_entity(const ir_node *addr, int pos) {
524 switch (get_irn_opcode(addr)) {
526 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
527 while (is_Sel(get_Sel_ptr(addr))) {
528 addr = get_Sel_ptr(addr);
530 assert (0 <= pos && pos < get_Sel_n_accessed_entities(addr));
531 ent = get_Sel_accessed_entity(addr);
534 if (get_SymConst_kind(addr) == symconst_addr_ent) {
536 ent = get_SymConst_entity(addr);
546 static void chain_accesses(ir_node *n, void *env) {
552 add_type_alloc(get_Alloc_type(n), n);
554 } else if (is_Cast(n)) {
555 add_type_cast(get_Cast_type(n), n);
557 } else if (is_Sel(n)) {
558 add_entity_reference(get_Sel_entity(n), n);
560 } else if (is_SymConst_addr_ent(n)) {
561 add_entity_reference(get_SymConst_entity(n), n);
563 } else if (is_memop(n)) {
564 addr = get_memop_ptr(n);
565 } else if (is_Call(n)) {
566 addr = get_Call_ptr(n);
567 if (! is_Sel(addr)) return; /* Sels before Calls mean a Load / polymorphic Call. */
572 n_ents = get_addr_n_entities(addr); /* == 1 */
573 for (i = 0; i < n_ents; ++i) {
574 ir_entity *ent = get_addr_entity(addr, i);
576 add_entity_access(ent, n);
578 //add_unrecognized_access(n);
583 * Handle chain types (pointer, array) by adding them to
586 static void chain_types(ir_type *tp) {
587 if (is_Pointer_type(tp)) {
588 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
589 } else if (is_Array_type(tp)) {
590 add_type_arraytype_of(get_array_element_type(tp), tp);
594 irg_outs_state get_trouts_state(void) {
595 return irp->trouts_state;
598 void set_trouts_inconsistent(void) {
599 if (irp->trouts_state == outs_consistent)
600 irp->trouts_state = outs_inconsistent;
603 /* compute the trouts data structures. */
604 void compute_trouts(void) {
610 /* Compute outs for IR nodes. */
611 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
612 irg_walk_graph(get_irp_irg(i), NULL, chain_accesses, NULL);
614 walk_const_code(NULL, chain_accesses, NULL);
616 /* Compute outs for types */
617 for (i = get_irp_n_types() - 1; i >= 0; --i) {
618 chain_types(get_irp_type(i));
621 irp->trouts_state = outs_consistent;
624 void free_trouts(void) {
625 if (entity_access_map) {
627 for (accs = (ir_node **)pmap_first(entity_access_map);
629 accs = (ir_node **)pmap_next(entity_access_map))
631 pmap_destroy(entity_access_map);
632 entity_access_map = NULL;
635 if (entity_reference_map) {
637 for (refs = (ir_node **)pmap_first(entity_reference_map);
639 refs = (ir_node **)pmap_next(entity_reference_map))
641 pmap_destroy(entity_reference_map);
642 entity_reference_map = NULL;
645 if (type_alloc_map) {
647 for (alls = (ir_node **)pmap_first(type_alloc_map);
649 alls = (ir_node **)pmap_next(type_alloc_map))
651 pmap_destroy(type_alloc_map);
652 type_alloc_map = NULL;
657 for (casts = (ir_node **)pmap_first(type_cast_map);
659 casts = (ir_node **)pmap_next(type_cast_map))
661 pmap_destroy(type_cast_map);
662 type_cast_map = NULL;
665 if (type_pointertype_map) {
667 for (pts = (ir_node **)pmap_first(type_pointertype_map);
669 pts = (ir_node **)pmap_next(type_pointertype_map))
671 pmap_destroy(type_pointertype_map);
672 type_pointertype_map = NULL;
675 if (type_arraytype_map) {
677 for (pts = (ir_node **)pmap_first(type_arraytype_map);
679 pts = (ir_node **)pmap_next(type_arraytype_map))
681 pmap_destroy(type_arraytype_map);
682 type_arraytype_map = NULL;
685 irp->trouts_state = outs_none;