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_pointertype_map = NULL;
47 static pmap *type_arraytype_map = NULL;
50 * Return a flexible array containing all IR-nodes
51 * that access a given entity.
53 static ir_node **get_entity_access_array(const ir_entity *ent)
55 if (!entity_access_map) entity_access_map = pmap_create();
57 ir_node **res = pmap_get(ir_node*, entity_access_map, ent);
59 res = NEW_ARR_F(ir_node *, 0);
60 pmap_insert(entity_access_map, ent, (void *)res);
66 static void set_entity_access_array(const ir_entity *ent, ir_node **accs)
68 pmap_insert(entity_access_map, ent, (void *)accs);
72 * Return a flexible array containing all IR-nodes
73 * that reference a given entity.
75 static ir_node **get_entity_reference_array(const ir_entity *ent)
77 if (!entity_reference_map) entity_reference_map = pmap_create();
79 ir_node **res = pmap_get(ir_node*, entity_reference_map, ent);
81 res = NEW_ARR_F(ir_node *, 0);
82 pmap_insert(entity_reference_map, ent, (void *)res);
88 static void set_entity_reference_array(const ir_entity *ent, ir_node **refs)
90 pmap_insert(entity_reference_map, ent, (void *)refs);
94 * Return a flexible array containing all IR-nodes
95 * that allocate a given type.
97 static ir_node **get_type_alloc_array(const ir_type *tp)
99 if (!type_alloc_map) type_alloc_map = pmap_create();
101 ir_node **res = pmap_get(ir_node*, type_alloc_map, tp);
103 res = NEW_ARR_F(ir_node *, 0);
104 pmap_insert(type_alloc_map, tp, (void *)res);
110 static void set_type_alloc_array(const ir_type *tp, ir_node **alls)
112 pmap_insert(type_alloc_map, tp, (void *)alls);
116 * Return a flexible array containing all pointer
117 * types that points-to a given type.
119 static ir_type **get_type_pointertype_array(const ir_type *tp)
121 if (!type_pointertype_map) type_pointertype_map = pmap_create();
123 ir_type **res = pmap_get(ir_type*, type_pointertype_map, tp);
125 res = NEW_ARR_F(ir_type *, 0);
126 pmap_insert(type_pointertype_map, tp, (void *)res);
132 static void set_type_pointertype_array(const ir_type *tp, ir_type **pts)
134 pmap_insert(type_pointertype_map, tp, (void *)pts);
138 * Return a flexible array containing all array
139 * types that have a given type as element type.
141 static ir_type **get_type_arraytype_array(const ir_type *tp)
143 if (!type_arraytype_map) type_arraytype_map = pmap_create();
145 ir_type **res = pmap_get(ir_type*, type_arraytype_map, tp);
147 res = NEW_ARR_F(ir_type *, 0);
148 pmap_insert(type_arraytype_map, tp, (void *)res);
154 static void set_type_arraytype_array(const ir_type *tp, ir_type **pts)
156 pmap_insert(type_arraytype_map, tp, (void *)pts);
159 /*------------------------------------------------------------------*/
160 /* Accessing the out data structures. */
161 /* These routines only work properly if firm is in state */
162 /* trouts_consistent or trouts_inconsistent. */
163 /*------------------------------------------------------------------*/
165 /**------------------------------------------------------------------*/
166 /* Access routines for entities */
167 /**------------------------------------------------------------------*/
169 size_t get_entity_n_accesses(const ir_entity *ent)
173 assert(ent && is_entity(ent));
175 accs = get_entity_access_array(ent);
176 return ARR_LEN(accs);
179 ir_node *get_entity_access(const ir_entity *ent, size_t pos)
183 assert(pos < get_entity_n_accesses(ent));
185 accs = get_entity_access_array(ent);
189 static void add_entity_access(const ir_entity *ent, ir_node *n)
193 assert(ent && is_entity(ent));
194 assert(n && is_ir_node(n));
196 accs = get_entity_access_array(ent);
197 ARR_APP1(ir_node *, accs, n);
198 set_entity_access_array(ent, accs);
201 /*------------------------------------------------------------------*/
203 size_t get_entity_n_references(const ir_entity *ent)
207 assert(ent && is_entity(ent));
209 refs = get_entity_reference_array(ent);
210 return ARR_LEN(refs);
213 ir_node *get_entity_reference(const ir_entity *ent, size_t pos)
217 assert( pos < get_entity_n_references(ent));
219 refs = get_entity_reference_array(ent);
223 static void add_entity_reference(const ir_entity *ent, ir_node *n)
227 assert(ent && is_entity(ent));
228 assert(n && is_ir_node(n));
230 refs = get_entity_reference_array(ent);
231 ARR_APP1(ir_node *, refs, n);
232 set_entity_reference_array(ent, refs);
235 /**------------------------------------------------------------------*/
236 /* Access routines for types */
237 /**------------------------------------------------------------------*/
239 /* Number of Alloc nodes that create an instance of this type */
240 size_t get_type_n_allocs(const ir_type *tp)
244 assert(tp && is_type(tp));
246 allocs = get_type_alloc_array(tp);
247 return ARR_LEN(allocs);
250 /* Alloc node that creates an instance of this type */
251 ir_node *get_type_alloc(const ir_type *tp, size_t pos)
254 assert( pos < get_type_n_allocs(tp));
256 allocs = get_type_alloc_array(tp);
260 static void add_type_alloc(const ir_type *tp, ir_node *n)
264 assert(tp && is_type(tp));
265 assert(n && is_ir_node(n));
267 allocs = get_type_alloc_array(tp);
268 ARR_APP1(ir_node *, allocs, n);
269 set_type_alloc_array(tp, allocs);
272 /*------------------------------------------------------------------*/
274 size_t get_type_n_pointertypes_to(const ir_type *tp)
278 assert(tp && is_type(tp));
280 pts = get_type_pointertype_array(tp);
284 ir_type *get_type_pointertype_to(const ir_type *tp, size_t pos)
288 assert(pos < get_type_n_pointertypes_to(tp));
290 pts = get_type_pointertype_array(tp);
294 void add_type_pointertype_to(const ir_type *tp, ir_type *ptp)
298 assert(tp && is_type(tp));
299 assert(ptp && is_Pointer_type(ptp));
301 pts = get_type_pointertype_array(tp);
302 ARR_APP1(ir_type*, pts, ptp);
303 set_type_pointertype_array(tp, pts);
306 /*------------------------------------------------------------------*/
308 size_t get_type_n_arraytypes_of(const ir_type *tp)
312 assert(tp && is_type(tp));
314 pts = get_type_arraytype_array(tp);
318 ir_type *get_type_arraytype_of(const ir_type *tp, size_t pos)
322 assert(pos < get_type_n_arraytypes_of(tp));
324 pts = get_type_arraytype_array(tp);
328 void add_type_arraytype_of(const ir_type *tp, ir_type *atp)
332 assert(tp && is_type(tp));
333 assert(atp && is_Array_type(atp));
335 pts = get_type_arraytype_array(tp);
336 ARR_APP1(ir_type*, pts, atp);
337 set_type_arraytype_array(tp, pts);
340 /*------------------------------------------------------------------*/
341 /* Building and Removing the out datastructure */
342 /*------------------------------------------------------------------*/
344 /** Initialize the trouts handling. */
345 static void init_trouts(void)
349 /** The number of entities that can be accessed by this Sel node. */
350 static int get_Sel_n_accessed_entities(const ir_node *sel)
356 /** The entity that cat be accessed by this Sel node. */
357 static ir_entity *get_Sel_accessed_entity(const ir_node *sel)
359 return get_Sel_entity(sel);
362 /** An addr node is a SymConst or a Sel. */
363 static int get_addr_n_entities(const ir_node *addr)
365 switch (get_irn_opcode(addr)) {
367 /* Treat jack array sels? */
368 return get_Sel_n_accessed_entities(addr);
370 if (get_SymConst_kind(addr) == symconst_addr_ent)
378 /** An addr node is a SymConst or a Sel.
379 If Sel follow to outermost of compound. */
380 static ir_entity *get_addr_entity(const ir_node *addr, int pos)
385 switch (get_irn_opcode(addr)) {
387 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
388 ptr = get_Sel_ptr(addr);
389 while (is_Sel(ptr)) {
391 ptr = get_Sel_ptr(addr);
393 assert(0 <= pos && pos < get_Sel_n_accessed_entities(addr));
394 return get_Sel_accessed_entity(addr);
396 if (get_SymConst_kind(addr) == symconst_addr_ent) {
398 return get_SymConst_entity(addr);
406 static void chain_accesses(ir_node *n, void *env)
413 add_type_alloc(get_Alloc_type(n), n);
415 } else if (is_Sel(n)) {
416 add_entity_reference(get_Sel_entity(n), n);
418 } else if (is_SymConst_addr_ent(n)) {
419 add_entity_reference(get_SymConst_entity(n), n);
421 } else if (is_Store(n)) {
422 addr = get_Store_ptr(n);
423 } else if (is_Load(n)) {
424 addr = get_Load_ptr(n);
425 } else if (is_Call(n)) {
426 addr = get_Call_ptr(n);
427 if (! is_Sel(addr)) return; /* Sels before Calls mean a Load / polymorphic Call. */
432 n_ents = get_addr_n_entities(addr); /* == 1 */
433 for (i = 0; i < n_ents; ++i) {
434 ir_entity *ent = get_addr_entity(addr, i);
436 add_entity_access(ent, n);
438 //add_unrecognized_access(n);
443 * Handle chain types (pointer, array) by adding them to
446 static void chain_types(ir_type *tp)
448 if (is_Pointer_type(tp)) {
449 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
450 } else if (is_Array_type(tp)) {
451 add_type_arraytype_of(get_array_element_type(tp), tp);
455 void compute_trouts(void)
462 /* Compute outs for IR nodes. */
463 for (i = get_irp_n_irgs(); i > 0;) {
464 ir_graph *irg = get_irp_irg(--i);
465 irg_walk_graph(irg, NULL, chain_accesses, NULL);
467 walk_const_code(NULL, chain_accesses, NULL);
469 /* Compute outs for types */
470 for (i = get_irp_n_types(); i > 0;) {
471 ir_type *type = get_irp_type(--i);
476 void free_trouts(void)
478 if (entity_access_map) {
480 for (accs = (ir_node **)pmap_first(entity_access_map);
482 accs = (ir_node **)pmap_next(entity_access_map)) {
483 /* DEL_ARR_F(accs); */
485 pmap_destroy(entity_access_map);
486 entity_access_map = NULL;
489 if (entity_reference_map) {
491 for (refs = (ir_node **)pmap_first(entity_reference_map);
493 refs = (ir_node **)pmap_next(entity_reference_map)) {
494 /* DEL_ARR_F(refs); */
496 pmap_destroy(entity_reference_map);
497 entity_reference_map = NULL;
500 if (type_alloc_map) {
502 for (alls = (ir_node **)pmap_first(type_alloc_map);
504 alls = (ir_node **)pmap_next(type_alloc_map)) {
505 /* DEL_ARR_F(alls); */
507 pmap_destroy(type_alloc_map);
508 type_alloc_map = NULL;
511 if (type_pointertype_map) {
513 for (pts = (ir_node **)pmap_first(type_pointertype_map);
515 pts = (ir_node **)pmap_next(type_pointertype_map)) {
516 /* DEL_ARR_F(pts); */
518 pmap_destroy(type_pointertype_map);
519 type_pointertype_map = NULL;
522 if (type_arraytype_map) {
524 for (pts = (ir_node **)pmap_first(type_arraytype_map);
526 pts = (ir_node **)pmap_next(type_arraytype_map)) {
527 /* DEL_ARR_F(pts); */
529 pmap_destroy(type_arraytype_map);
530 type_arraytype_map = NULL;