2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Reverse edges that reference types/entities.
9 * @author Goetz Lindenmaier
25 /*------------------------------------------------------------------*/
26 /* We represent the fields in entities/types by hashmaps. */
27 /*------------------------------------------------------------------*/
29 static pmap *entity_access_map = NULL;
30 static pmap *entity_reference_map = NULL;
31 static pmap *type_alloc_map = NULL;
32 static pmap *type_pointertype_map = NULL;
33 static pmap *type_arraytype_map = NULL;
36 * Return a flexible array containing all IR-nodes
37 * that access a given entity.
39 static ir_node **get_entity_access_array(const ir_entity *ent)
41 if (!entity_access_map) entity_access_map = pmap_create();
43 ir_node **res = pmap_get(ir_node*, entity_access_map, ent);
45 res = NEW_ARR_F(ir_node *, 0);
46 pmap_insert(entity_access_map, ent, (void *)res);
52 static void set_entity_access_array(const ir_entity *ent, ir_node **accs)
54 pmap_insert(entity_access_map, ent, (void *)accs);
58 * Return a flexible array containing all IR-nodes
59 * that reference a given entity.
61 static ir_node **get_entity_reference_array(const ir_entity *ent)
63 if (!entity_reference_map) entity_reference_map = pmap_create();
65 ir_node **res = pmap_get(ir_node*, entity_reference_map, ent);
67 res = NEW_ARR_F(ir_node *, 0);
68 pmap_insert(entity_reference_map, ent, (void *)res);
74 static void set_entity_reference_array(const ir_entity *ent, ir_node **refs)
76 pmap_insert(entity_reference_map, ent, (void *)refs);
80 * Return a flexible array containing all IR-nodes
81 * that allocate a given type.
83 static ir_node **get_type_alloc_array(const ir_type *tp)
85 if (!type_alloc_map) type_alloc_map = pmap_create();
87 ir_node **res = pmap_get(ir_node*, type_alloc_map, tp);
89 res = NEW_ARR_F(ir_node *, 0);
90 pmap_insert(type_alloc_map, tp, (void *)res);
96 static void set_type_alloc_array(const ir_type *tp, ir_node **alls)
98 pmap_insert(type_alloc_map, tp, (void *)alls);
102 * Return a flexible array containing all pointer
103 * types that points-to a given type.
105 static ir_type **get_type_pointertype_array(const ir_type *tp)
107 if (!type_pointertype_map) type_pointertype_map = pmap_create();
109 ir_type **res = pmap_get(ir_type*, type_pointertype_map, tp);
111 res = NEW_ARR_F(ir_type *, 0);
112 pmap_insert(type_pointertype_map, tp, (void *)res);
118 static void set_type_pointertype_array(const ir_type *tp, ir_type **pts)
120 pmap_insert(type_pointertype_map, tp, (void *)pts);
124 * Return a flexible array containing all array
125 * types that have a given type as element type.
127 static ir_type **get_type_arraytype_array(const ir_type *tp)
129 if (!type_arraytype_map) type_arraytype_map = pmap_create();
131 ir_type **res = pmap_get(ir_type*, type_arraytype_map, tp);
133 res = NEW_ARR_F(ir_type *, 0);
134 pmap_insert(type_arraytype_map, tp, (void *)res);
140 static void set_type_arraytype_array(const ir_type *tp, ir_type **pts)
142 pmap_insert(type_arraytype_map, tp, (void *)pts);
145 /*------------------------------------------------------------------*/
146 /* Accessing the out data structures. */
147 /* These routines only work properly if firm is in state */
148 /* trouts_consistent or trouts_inconsistent. */
149 /*------------------------------------------------------------------*/
151 /**------------------------------------------------------------------*/
152 /* Access routines for entities */
153 /**------------------------------------------------------------------*/
155 size_t get_entity_n_accesses(const ir_entity *ent)
159 assert(ent && is_entity(ent));
161 accs = get_entity_access_array(ent);
162 return ARR_LEN(accs);
165 ir_node *get_entity_access(const ir_entity *ent, size_t pos)
169 assert(pos < get_entity_n_accesses(ent));
171 accs = get_entity_access_array(ent);
175 static void add_entity_access(const ir_entity *ent, ir_node *n)
179 assert(ent && is_entity(ent));
180 assert(n && is_ir_node(n));
182 accs = get_entity_access_array(ent);
183 ARR_APP1(ir_node *, accs, n);
184 set_entity_access_array(ent, accs);
187 /*------------------------------------------------------------------*/
189 size_t get_entity_n_references(const ir_entity *ent)
193 assert(ent && is_entity(ent));
195 refs = get_entity_reference_array(ent);
196 return ARR_LEN(refs);
199 ir_node *get_entity_reference(const ir_entity *ent, size_t pos)
203 assert( pos < get_entity_n_references(ent));
205 refs = get_entity_reference_array(ent);
209 static void add_entity_reference(const ir_entity *ent, ir_node *n)
213 assert(ent && is_entity(ent));
214 assert(n && is_ir_node(n));
216 refs = get_entity_reference_array(ent);
217 ARR_APP1(ir_node *, refs, n);
218 set_entity_reference_array(ent, refs);
221 /**------------------------------------------------------------------*/
222 /* Access routines for types */
223 /**------------------------------------------------------------------*/
225 /* Number of Alloc nodes that create an instance of this type */
226 size_t get_type_n_allocs(const ir_type *tp)
230 assert(tp && is_type(tp));
232 allocs = get_type_alloc_array(tp);
233 return ARR_LEN(allocs);
236 /* Alloc node that creates an instance of this type */
237 ir_node *get_type_alloc(const ir_type *tp, size_t pos)
240 assert( pos < get_type_n_allocs(tp));
242 allocs = get_type_alloc_array(tp);
246 static void add_type_alloc(const ir_type *tp, ir_node *n)
250 assert(tp && is_type(tp));
251 assert(n && is_ir_node(n));
253 allocs = get_type_alloc_array(tp);
254 ARR_APP1(ir_node *, allocs, n);
255 set_type_alloc_array(tp, allocs);
258 /*------------------------------------------------------------------*/
260 size_t get_type_n_pointertypes_to(const ir_type *tp)
264 assert(tp && is_type(tp));
266 pts = get_type_pointertype_array(tp);
270 ir_type *get_type_pointertype_to(const ir_type *tp, size_t pos)
274 assert(pos < get_type_n_pointertypes_to(tp));
276 pts = get_type_pointertype_array(tp);
280 void add_type_pointertype_to(const ir_type *tp, ir_type *ptp)
284 assert(tp && is_type(tp));
285 assert(ptp && is_Pointer_type(ptp));
287 pts = get_type_pointertype_array(tp);
288 ARR_APP1(ir_type*, pts, ptp);
289 set_type_pointertype_array(tp, pts);
292 /*------------------------------------------------------------------*/
294 size_t get_type_n_arraytypes_of(const ir_type *tp)
298 assert(tp && is_type(tp));
300 pts = get_type_arraytype_array(tp);
304 ir_type *get_type_arraytype_of(const ir_type *tp, size_t pos)
308 assert(pos < get_type_n_arraytypes_of(tp));
310 pts = get_type_arraytype_array(tp);
314 void add_type_arraytype_of(const ir_type *tp, ir_type *atp)
318 assert(tp && is_type(tp));
319 assert(atp && is_Array_type(atp));
321 pts = get_type_arraytype_array(tp);
322 ARR_APP1(ir_type*, pts, atp);
323 set_type_arraytype_array(tp, pts);
326 /*------------------------------------------------------------------*/
327 /* Building and Removing the out datastructure */
328 /*------------------------------------------------------------------*/
330 /** Initialize the trouts handling. */
331 static void init_trouts(void)
335 /** The number of entities that can be accessed by this Sel node. */
336 static int get_Sel_n_accessed_entities(const ir_node *sel)
342 /** The entity that cat be accessed by this Sel node. */
343 static ir_entity *get_Sel_accessed_entity(const ir_node *sel)
345 return get_Sel_entity(sel);
348 /** An addr node is a SymConst or a Sel. */
349 static int get_addr_n_entities(const ir_node *addr)
351 switch (get_irn_opcode(addr)) {
353 /* Treat jack array sels? */
354 return get_Sel_n_accessed_entities(addr);
356 if (get_SymConst_kind(addr) == symconst_addr_ent)
364 /** An addr node is a SymConst or a Sel.
365 If Sel follow to outermost of compound. */
366 static ir_entity *get_addr_entity(const ir_node *addr, int pos)
371 switch (get_irn_opcode(addr)) {
373 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
374 ptr = get_Sel_ptr(addr);
375 while (is_Sel(ptr)) {
377 ptr = get_Sel_ptr(addr);
379 assert(0 <= pos && pos < get_Sel_n_accessed_entities(addr));
380 return get_Sel_accessed_entity(addr);
382 if (get_SymConst_kind(addr) == symconst_addr_ent) {
384 return get_SymConst_entity(addr);
392 static void chain_accesses(ir_node *n, void *env)
399 add_type_alloc(get_Alloc_type(n), n);
401 } else if (is_Sel(n)) {
402 add_entity_reference(get_Sel_entity(n), n);
404 } else if (is_SymConst_addr_ent(n)) {
405 add_entity_reference(get_SymConst_entity(n), n);
407 } else if (is_Store(n)) {
408 addr = get_Store_ptr(n);
409 } else if (is_Load(n)) {
410 addr = get_Load_ptr(n);
411 } else if (is_Call(n)) {
412 addr = get_Call_ptr(n);
413 if (! is_Sel(addr)) return; /* Sels before Calls mean a Load / polymorphic Call. */
418 n_ents = get_addr_n_entities(addr); /* == 1 */
419 for (i = 0; i < n_ents; ++i) {
420 ir_entity *ent = get_addr_entity(addr, i);
422 add_entity_access(ent, n);
424 //add_unrecognized_access(n);
429 * Handle chain types (pointer, array) by adding them to
432 static void chain_types(ir_type *tp)
434 if (is_Pointer_type(tp)) {
435 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
436 } else if (is_Array_type(tp)) {
437 add_type_arraytype_of(get_array_element_type(tp), tp);
441 void compute_trouts(void)
448 /* Compute outs for IR nodes. */
449 for (i = get_irp_n_irgs(); i > 0;) {
450 ir_graph *irg = get_irp_irg(--i);
451 irg_walk_graph(irg, NULL, chain_accesses, NULL);
453 walk_const_code(NULL, chain_accesses, NULL);
455 /* Compute outs for types */
456 for (i = get_irp_n_types(); i > 0;) {
457 ir_type *type = get_irp_type(--i);
462 void free_trouts(void)
464 if (entity_access_map) {
466 for (accs = (ir_node **)pmap_first(entity_access_map);
468 accs = (ir_node **)pmap_next(entity_access_map)) {
469 /* DEL_ARR_F(accs); */
471 pmap_destroy(entity_access_map);
472 entity_access_map = NULL;
475 if (entity_reference_map) {
477 for (refs = (ir_node **)pmap_first(entity_reference_map);
479 refs = (ir_node **)pmap_next(entity_reference_map)) {
480 /* DEL_ARR_F(refs); */
482 pmap_destroy(entity_reference_map);
483 entity_reference_map = NULL;
486 if (type_alloc_map) {
488 for (alls = (ir_node **)pmap_first(type_alloc_map);
490 alls = (ir_node **)pmap_next(type_alloc_map)) {
491 /* DEL_ARR_F(alls); */
493 pmap_destroy(type_alloc_map);
494 type_alloc_map = NULL;
497 if (type_pointertype_map) {
499 for (pts = (ir_node **)pmap_first(type_pointertype_map);
501 pts = (ir_node **)pmap_next(type_pointertype_map)) {
502 /* DEL_ARR_F(pts); */
504 pmap_destroy(type_pointertype_map);
505 type_pointertype_map = NULL;
508 if (type_arraytype_map) {
510 for (pts = (ir_node **)pmap_first(type_arraytype_map);
512 pts = (ir_node **)pmap_next(type_arraytype_map)) {
513 /* DEL_ARR_F(pts); */
515 pmap_destroy(type_arraytype_map);
516 type_arraytype_map = NULL;