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)
56 if (!entity_access_map) entity_access_map = pmap_create();
58 ir_node **res = pmap_get(ir_node*, entity_access_map, ent);
60 res = NEW_ARR_F(ir_node *, 0);
61 pmap_insert(entity_access_map, ent, (void *)res);
67 static void set_entity_access_array(const ir_entity *ent, ir_node **accs)
69 pmap_insert(entity_access_map, ent, (void *)accs);
73 * Return a flexible array containing all IR-nodes
74 * that reference a given entity.
76 static ir_node **get_entity_reference_array(const ir_entity *ent)
78 if (!entity_reference_map) entity_reference_map = pmap_create();
80 ir_node **res = pmap_get(ir_node*, entity_reference_map, ent);
82 res = NEW_ARR_F(ir_node *, 0);
83 pmap_insert(entity_reference_map, ent, (void *)res);
89 static void set_entity_reference_array(const ir_entity *ent, ir_node **refs)
91 pmap_insert(entity_reference_map, ent, (void *)refs);
95 * Return a flexible array containing all IR-nodes
96 * that allocate a given type.
98 static ir_node **get_type_alloc_array(const ir_type *tp)
100 if (!type_alloc_map) type_alloc_map = pmap_create();
102 ir_node **res = pmap_get(ir_node*, type_alloc_map, tp);
104 res = NEW_ARR_F(ir_node *, 0);
105 pmap_insert(type_alloc_map, tp, (void *)res);
111 static void set_type_alloc_array(const ir_type *tp, ir_node **alls)
113 pmap_insert(type_alloc_map, tp, (void *)alls);
117 * Return a flexible array containing all Cast-nodes
118 * that "create" a given type.
120 static ir_node **get_type_cast_array(const ir_type *tp)
122 if (!type_cast_map) type_cast_map = pmap_create();
124 ir_node **res = pmap_get(ir_node*, type_cast_map, tp);
126 res = NEW_ARR_F(ir_node *, 0);
127 pmap_insert(type_cast_map, tp, (void *)res);
132 static void set_type_cast_array(const ir_type *tp, ir_node **alls)
134 pmap_insert(type_cast_map, tp, (void *)alls);
138 * Return a flexible array containing all pointer
139 * types that points-to a given type.
141 static ir_type **get_type_pointertype_array(const ir_type *tp)
143 if (!type_pointertype_map) type_pointertype_map = pmap_create();
145 ir_type **res = pmap_get(ir_type*, type_pointertype_map, tp);
147 res = NEW_ARR_F(ir_type *, 0);
148 pmap_insert(type_pointertype_map, tp, (void *)res);
154 static void set_type_pointertype_array(const ir_type *tp, ir_type **pts)
156 pmap_insert(type_pointertype_map, tp, (void *)pts);
160 * Return a flexible array containing all array
161 * types that have a given type as element type.
163 static ir_type **get_type_arraytype_array(const ir_type *tp)
165 if (!type_arraytype_map) type_arraytype_map = pmap_create();
167 ir_type **res = pmap_get(ir_type*, type_arraytype_map, tp);
169 res = NEW_ARR_F(ir_type *, 0);
170 pmap_insert(type_arraytype_map, tp, (void *)res);
176 static void set_type_arraytype_array(const ir_type *tp, ir_type **pts)
178 pmap_insert(type_arraytype_map, tp, (void *)pts);
181 /*------------------------------------------------------------------*/
182 /* Accessing the out data structures. */
183 /* These routines only work properly if firm is in state */
184 /* trouts_consistent or trouts_inconsistent. */
185 /*------------------------------------------------------------------*/
187 /**------------------------------------------------------------------*/
188 /* Access routines for entities */
189 /**------------------------------------------------------------------*/
191 size_t get_entity_n_accesses(const ir_entity *ent)
195 assert(ent && is_entity(ent));
197 accs = get_entity_access_array(ent);
198 return ARR_LEN(accs);
201 ir_node *get_entity_access(const ir_entity *ent, size_t pos)
205 assert(pos < get_entity_n_accesses(ent));
207 accs = get_entity_access_array(ent);
211 static void add_entity_access(const ir_entity *ent, ir_node *n)
215 assert(ent && is_entity(ent));
216 assert(n && is_ir_node(n));
218 accs = get_entity_access_array(ent);
219 ARR_APP1(ir_node *, accs, n);
220 set_entity_access_array(ent, accs);
223 /*------------------------------------------------------------------*/
225 size_t get_entity_n_references(const ir_entity *ent)
229 assert(ent && is_entity(ent));
231 refs = get_entity_reference_array(ent);
232 return ARR_LEN(refs);
235 ir_node *get_entity_reference(const ir_entity *ent, size_t pos)
239 assert( pos < get_entity_n_references(ent));
241 refs = get_entity_reference_array(ent);
245 static void add_entity_reference(const ir_entity *ent, ir_node *n)
249 assert(ent && is_entity(ent));
250 assert(n && is_ir_node(n));
252 refs = get_entity_reference_array(ent);
253 ARR_APP1(ir_node *, refs, n);
254 set_entity_reference_array(ent, refs);
257 /**------------------------------------------------------------------*/
258 /* Access routines for types */
259 /**------------------------------------------------------------------*/
261 /* Number of Alloc nodes that create an instance of this type */
262 size_t get_type_n_allocs(const ir_type *tp)
266 assert(tp && is_type(tp));
268 allocs = get_type_alloc_array(tp);
269 return ARR_LEN(allocs);
272 /* Alloc node that creates an instance of this type */
273 ir_node *get_type_alloc(const ir_type *tp, size_t pos)
276 assert( pos < get_type_n_allocs(tp));
278 allocs = get_type_alloc_array(tp);
282 static void add_type_alloc(const ir_type *tp, ir_node *n)
286 assert(tp && is_type(tp));
287 assert(n && is_ir_node(n));
289 allocs = get_type_alloc_array(tp);
290 ARR_APP1(ir_node *, allocs, n);
291 set_type_alloc_array(tp, allocs);
294 /* Number of Cast nodes that create an instance of this type */
295 size_t get_type_n_casts(const ir_type *tp)
299 assert(tp && is_type(tp));
301 casts = get_type_cast_array(tp);
302 return ARR_LEN(casts);
306 size_t get_class_n_upcasts(const ir_type *clss)
308 size_t i, n_casts = get_type_n_casts(clss);
309 size_t n_instances = 0;
310 for (i = 0; i < n_casts; ++i) {
311 ir_node *cast = get_type_cast(clss, i);
312 if (is_Cast_upcast(cast))
318 size_t get_class_n_downcasts(const ir_type *clss)
320 size_t i, n_casts = get_type_n_casts(clss);
321 size_t n_instances = 0;
322 for (i = 0; i < n_casts; ++i) {
323 ir_node *cast = get_type_cast(clss, i);
324 if (is_Cast_downcast(cast))
330 ir_node *get_type_cast(const ir_type *tp, size_t pos)
333 assert(pos < get_type_n_casts(tp));
335 casts = get_type_cast_array(tp);
339 void add_type_cast(const ir_type *tp, ir_node *n)
343 assert(tp && is_type(tp));
344 assert(n && is_ir_node(n));
346 casts = get_type_cast_array(tp);
347 ARR_APP1(ir_node *, casts, n);
348 set_type_cast_array(tp, casts);
351 /*------------------------------------------------------------------*/
353 size_t get_type_n_pointertypes_to(const ir_type *tp)
357 assert(tp && is_type(tp));
359 pts = get_type_pointertype_array(tp);
363 ir_type *get_type_pointertype_to(const ir_type *tp, size_t pos)
367 assert(pos < get_type_n_pointertypes_to(tp));
369 pts = get_type_pointertype_array(tp);
373 void add_type_pointertype_to(const ir_type *tp, ir_type *ptp)
377 assert(tp && is_type(tp));
378 assert(ptp && is_Pointer_type(ptp));
380 pts = get_type_pointertype_array(tp);
381 ARR_APP1(ir_type*, pts, ptp);
382 set_type_pointertype_array(tp, pts);
385 /*------------------------------------------------------------------*/
387 size_t get_type_n_arraytypes_of(const ir_type *tp)
391 assert(tp && is_type(tp));
393 pts = get_type_arraytype_array(tp);
397 ir_type *get_type_arraytype_of(const ir_type *tp, size_t pos)
401 assert(pos < get_type_n_arraytypes_of(tp));
403 pts = get_type_arraytype_array(tp);
407 void add_type_arraytype_of(const ir_type *tp, ir_type *atp)
411 assert(tp && is_type(tp));
412 assert(atp && is_Array_type(atp));
414 pts = get_type_arraytype_array(tp);
415 ARR_APP1(ir_type*, pts, atp);
416 set_type_arraytype_array(tp, pts);
419 /*------------------------------------------------------------------*/
420 /* Building and Removing the out datastructure */
421 /*------------------------------------------------------------------*/
423 /** Initialize the trouts handling. */
424 static void init_trouts(void)
428 /** The number of entities that can be accessed by this Sel node. */
429 static int get_Sel_n_accessed_entities(const ir_node *sel)
435 /** The entity that cat be accessed by this Sel node. */
436 static ir_entity *get_Sel_accessed_entity(const ir_node *sel)
438 return get_Sel_entity(sel);
441 /** An addr node is a SymConst or a Sel. */
442 static int get_addr_n_entities(const ir_node *addr)
444 switch (get_irn_opcode(addr)) {
446 /* Treat jack array sels? */
447 return get_Sel_n_accessed_entities(addr);
449 if (get_SymConst_kind(addr) == symconst_addr_ent)
457 /** An addr node is a SymConst or a Sel.
458 If Sel follow to outermost of compound. */
459 static ir_entity *get_addr_entity(const ir_node *addr, int pos)
464 switch (get_irn_opcode(addr)) {
466 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
467 ptr = get_Sel_ptr(addr);
468 while (is_Sel(ptr)) {
470 ptr = get_Sel_ptr(addr);
472 assert(0 <= pos && pos < get_Sel_n_accessed_entities(addr));
473 return get_Sel_accessed_entity(addr);
475 if (get_SymConst_kind(addr) == symconst_addr_ent) {
477 return get_SymConst_entity(addr);
485 static void chain_accesses(ir_node *n, void *env)
492 add_type_alloc(get_Alloc_type(n), n);
494 } else if (is_Cast(n)) {
495 add_type_cast(get_Cast_type(n), n);
497 } else if (is_Sel(n)) {
498 add_entity_reference(get_Sel_entity(n), n);
500 } else if (is_SymConst_addr_ent(n)) {
501 add_entity_reference(get_SymConst_entity(n), n);
503 } else if (is_Store(n)) {
504 addr = get_Store_ptr(n);
505 } else if (is_Load(n)) {
506 addr = get_Load_ptr(n);
507 } else if (is_Call(n)) {
508 addr = get_Call_ptr(n);
509 if (! is_Sel(addr)) return; /* Sels before Calls mean a Load / polymorphic Call. */
514 n_ents = get_addr_n_entities(addr); /* == 1 */
515 for (i = 0; i < n_ents; ++i) {
516 ir_entity *ent = get_addr_entity(addr, i);
518 add_entity_access(ent, n);
520 //add_unrecognized_access(n);
525 * Handle chain types (pointer, array) by adding them to
528 static void chain_types(ir_type *tp)
530 if (is_Pointer_type(tp)) {
531 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
532 } else if (is_Array_type(tp)) {
533 add_type_arraytype_of(get_array_element_type(tp), tp);
537 void compute_trouts(void)
544 /* Compute outs for IR nodes. */
545 for (i = get_irp_n_irgs(); i > 0;) {
546 ir_graph *irg = get_irp_irg(--i);
547 irg_walk_graph(irg, NULL, chain_accesses, NULL);
549 walk_const_code(NULL, chain_accesses, NULL);
551 /* Compute outs for types */
552 for (i = get_irp_n_types(); i > 0;) {
553 ir_type *type = get_irp_type(--i);
558 void free_trouts(void)
560 if (entity_access_map) {
562 for (accs = (ir_node **)pmap_first(entity_access_map);
564 accs = (ir_node **)pmap_next(entity_access_map)) {
565 /* DEL_ARR_F(accs); */
567 pmap_destroy(entity_access_map);
568 entity_access_map = NULL;
571 if (entity_reference_map) {
573 for (refs = (ir_node **)pmap_first(entity_reference_map);
575 refs = (ir_node **)pmap_next(entity_reference_map)) {
576 /* DEL_ARR_F(refs); */
578 pmap_destroy(entity_reference_map);
579 entity_reference_map = NULL;
582 if (type_alloc_map) {
584 for (alls = (ir_node **)pmap_first(type_alloc_map);
586 alls = (ir_node **)pmap_next(type_alloc_map)) {
587 /* DEL_ARR_F(alls); */
589 pmap_destroy(type_alloc_map);
590 type_alloc_map = NULL;
595 for (casts = (ir_node **)pmap_first(type_cast_map);
597 casts = (ir_node **)pmap_next(type_cast_map)) {
598 /* DEL_ARR_F(alls); */
600 pmap_destroy(type_cast_map);
601 type_cast_map = NULL;
604 if (type_pointertype_map) {
606 for (pts = (ir_node **)pmap_first(type_pointertype_map);
608 pts = (ir_node **)pmap_next(type_pointertype_map)) {
609 /* DEL_ARR_F(pts); */
611 pmap_destroy(type_pointertype_map);
612 type_pointertype_map = NULL;
615 if (type_arraytype_map) {
617 for (pts = (ir_node **)pmap_first(type_arraytype_map);
619 pts = (ir_node **)pmap_next(type_arraytype_map)) {
620 /* DEL_ARR_F(pts); */
622 pmap_destroy(type_arraytype_map);
623 type_arraytype_map = NULL;