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
40 /*------------------------------------------------------------------*/
41 /* We represent the fields in entities/types by hashmaps. */
42 /*------------------------------------------------------------------*/
44 static pmap *entity_access_map = NULL;
45 static pmap *entity_reference_map = NULL;
46 static pmap *type_alloc_map = NULL;
47 static pmap *type_cast_map = NULL;
48 static pmap *type_pointertype_map = NULL;
49 static pmap *type_arraytype_map = NULL;
52 * Return a flexible array containing all IR-nodes
53 * that access a given entity.
55 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) {
70 ir_node **old = pmap_get(entity_access_map, ent);
72 pmap_insert(entity_access_map, ent, (void *)accs);
76 * Return a flexible array containing all IR-nodes
77 * that reference a given entity.
79 static ir_node **get_entity_reference_array(const ir_entity *ent) {
81 if (!entity_reference_map) entity_reference_map = pmap_create();
83 if (pmap_contains(entity_reference_map, ent)) {
84 res = (ir_node **) pmap_get(entity_reference_map, ent);
86 res = NEW_ARR_F(ir_node *, 0);
87 pmap_insert(entity_reference_map, ent, (void *)res);
93 static void set_entity_reference_array(const ir_entity *ent, ir_node **refs) {
94 ir_node **old = pmap_get(entity_reference_map, ent);
96 pmap_insert(entity_reference_map, ent, (void *)refs);
100 * Return a flexible array containing all IR-nodes
101 * that allocate a given type.
103 static ir_node **get_type_alloc_array(const ir_type *tp) {
105 if (!type_alloc_map) type_alloc_map = pmap_create();
107 if (pmap_contains(type_alloc_map, tp)) {
108 res = (ir_node **) pmap_get(type_alloc_map, tp);
110 res = NEW_ARR_F(ir_node *, 0);
111 pmap_insert(type_alloc_map, tp, (void *)res);
117 static void set_type_alloc_array(const ir_type *tp, ir_node **alls) {
118 ir_node **old = pmap_get(type_alloc_map, tp);
120 pmap_insert(type_alloc_map, tp, (void *)alls);
124 * Return a flexible array containing all Cast-nodes
125 * that "create" a given type.
127 static ir_node **get_type_cast_array(const ir_type *tp) {
129 if (!type_cast_map) type_cast_map = pmap_create();
131 if (pmap_contains(type_cast_map, tp)) {
132 res = (ir_node **) pmap_get(type_cast_map, tp);
134 res = NEW_ARR_F(ir_node *, 0);
135 pmap_insert(type_cast_map, tp, (void *)res);
140 static void set_type_cast_array(const ir_type *tp, ir_node **alls) {
141 ir_node **old = pmap_get(type_cast_map, tp);
143 pmap_insert(type_cast_map, tp, (void *)alls);
147 * Return a flexible array containing all pointer
148 * types that points-to a given type.
150 static ir_type **get_type_pointertype_array(const ir_type *tp) {
152 if (!type_pointertype_map) type_pointertype_map = pmap_create();
154 if (pmap_contains(type_pointertype_map, tp)) {
155 res = (ir_type **) pmap_get(type_pointertype_map, tp);
157 res = NEW_ARR_F(ir_type *, 0);
158 pmap_insert(type_pointertype_map, tp, (void *)res);
164 static void set_type_pointertype_array(const ir_type *tp, ir_type **pts) {
165 ir_type **old = pmap_get(type_pointertype_map, tp);
167 pmap_insert(type_pointertype_map, tp, (void *)pts);
171 * Return a flexible array containing all array
172 * types that have a given type as element type.
174 static ir_type **get_type_arraytype_array(const ir_type *tp) {
176 if (!type_arraytype_map) type_arraytype_map = pmap_create();
178 if (pmap_contains(type_arraytype_map, tp)) {
179 res = (ir_type **) pmap_get(type_arraytype_map, tp);
181 res = NEW_ARR_F(ir_type *, 0);
182 pmap_insert(type_arraytype_map, tp, (void *)res);
188 void set_type_arraytype_array(const ir_type *tp, ir_type **pts) {
189 ir_type **old = pmap_get(type_arraytype_map, tp);
191 pmap_insert(type_arraytype_map, tp, (void *)pts);
194 /*------------------------------------------------------------------*/
195 /* Accessing the out data structures. */
196 /* These routines only work properly if firm is in state */
197 /* trouts_consistent or trouts_inconsistent. */
198 /*------------------------------------------------------------------*/
200 /**------------------------------------------------------------------*/
201 /* Access routines for entities */
202 /**------------------------------------------------------------------*/
204 int get_entity_n_accesses(const ir_entity *ent) {
207 assert(ent && is_entity(ent));
209 accs = get_entity_access_array(ent);
210 return ARR_LEN(accs);
213 ir_node *get_entity_access(const ir_entity *ent, int pos) {
216 assert(0 <= pos && pos < get_entity_n_accesses(ent));
218 accs = get_entity_access_array(ent);
222 static void add_entity_access(const ir_entity *ent, ir_node *n) {
225 assert(ent && is_entity(ent));
226 assert(n && is_ir_node(n));
228 accs = get_entity_access_array(ent);
229 ARR_APP1(ir_node *, accs, n);
230 set_entity_access_array(ent, accs);
233 void set_entity_access(const ir_entity *ent, int pos, ir_node *n) {
236 assert(0 <= pos && pos < get_entity_n_accesses(ent));
237 assert(n && is_ir_node(n));
239 accs = get_entity_access_array(ent);
243 /*------------------------------------------------------------------*/
245 int get_entity_n_references(const ir_entity *ent) {
248 assert(ent && is_entity(ent));
250 refs = get_entity_reference_array(ent);
251 return ARR_LEN(refs);
254 ir_node *get_entity_reference(const ir_entity *ent, int pos) {
257 assert(0 <= pos && pos < get_entity_n_references(ent));
259 refs = get_entity_reference_array(ent);
263 static void add_entity_reference(const ir_entity *ent, ir_node *n) {
266 assert(ent && is_entity(ent));
267 assert(n && is_ir_node(n));
269 refs = get_entity_reference_array(ent);
270 ARR_APP1(ir_node *, refs, n);
271 set_entity_reference_array(ent, refs);
274 void set_entity_reference(const ir_entity *ent, int pos, ir_node *n) {
277 assert(0 <= pos && pos < get_entity_n_references(ent));
278 assert(n && is_ir_node(n));
280 refs = get_entity_reference_array(ent);
285 /**------------------------------------------------------------------*/
286 /* Access routines for types */
287 /**------------------------------------------------------------------*/
289 /* Number of Alloc nodes that create an instance of this type */
290 int get_type_n_allocs(const ir_type *tp) {
293 assert(tp && is_type(tp));
295 allocs = get_type_alloc_array(tp);
296 return ARR_LEN(allocs);
299 /* Alloc node that creates an instance of this type */
300 ir_node *get_type_alloc(const ir_type *tp, int pos) {
302 assert(0 <= pos && pos < get_type_n_allocs(tp));
304 allocs = get_type_alloc_array(tp);
308 static void add_type_alloc(const ir_type *tp, ir_node *n) {
311 assert(tp && is_type(tp));
312 assert(n && is_ir_node(n));
314 allocs = get_type_alloc_array(tp);
315 ARR_APP1(ir_node *, allocs, n);
316 set_type_alloc_array(tp, allocs);
319 void set_type_alloc(const ir_type *tp, int pos, ir_node *n) {
322 assert(0 <= pos && pos < get_type_n_allocs(tp));
323 assert(n && is_ir_node(n));
325 allocs = get_type_alloc_array(tp);
329 /* Number of Cast nodes that create an instance of this type */
330 int get_type_n_casts(const ir_type *tp) {
333 assert(tp && is_type(tp));
335 casts = get_type_cast_array(tp);
336 return ARR_LEN(casts);
340 int get_class_n_upcasts(const ir_type *clss) {
341 int i, n_casts = get_type_n_casts(clss);
343 for (i = 0; i < n_casts; ++i) {
344 ir_node *cast = get_type_cast(clss, i);
345 if (is_Cast_upcast(cast))
351 int get_class_n_downcasts(const ir_type *clss) {
352 int i, n_casts = get_type_n_casts(clss);
354 for (i = 0; i < n_casts; ++i) {
355 ir_node *cast = get_type_cast(clss, i);
356 if (is_Cast_downcast(cast))
362 /* Cast node that creates an instance of this type */
363 ir_node *get_type_cast(const ir_type *tp, int pos) {
365 assert(0 <= pos && pos < get_type_n_casts(tp));
367 casts = get_type_cast_array(tp);
371 void add_type_cast(const ir_type *tp, ir_node *n) {
374 assert(tp && is_type(tp));
375 assert(n && is_ir_node(n));
377 casts = get_type_cast_array(tp);
378 ARR_APP1(ir_node *, casts, n);
379 set_type_cast_array(tp, casts);
382 void set_type_cast(const ir_type *tp, int pos, ir_node *n) {
385 assert(0 <= pos && pos < get_type_n_casts(tp));
386 assert(n && is_ir_node(n));
388 casts = get_type_cast_array(tp);
392 /*------------------------------------------------------------------*/
394 int get_type_n_pointertypes_to(const ir_type *tp) {
397 assert(tp && is_type(tp));
399 pts = get_type_pointertype_array(tp);
403 ir_type *get_type_pointertype_to(const ir_type *tp, int pos) {
406 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
408 pts = get_type_pointertype_array(tp);
412 void add_type_pointertype_to(const ir_type *tp, ir_type *ptp) {
415 assert(tp && is_type(tp));
416 assert(ptp && is_Pointer_type(ptp));
418 pts = get_type_pointertype_array(tp);
419 ARR_APP1(ir_node *, pts, ptp);
420 set_type_pointertype_array(tp, pts);
423 void set_type_pointertype_to(const ir_type *tp, int pos, ir_type *ptp) {
426 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
427 assert(ptp && is_Pointer_type(ptp));
429 pts = get_type_pointertype_array(tp);
434 /*------------------------------------------------------------------*/
436 int get_type_n_arraytypes_of(const ir_type *tp) {
439 assert(tp && is_type(tp));
441 pts = get_type_arraytype_array(tp);
445 ir_type *get_type_arraytype_of(const ir_type *tp, int pos) {
448 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
450 pts = get_type_arraytype_array(tp);
454 void add_type_arraytype_of(const ir_type *tp, ir_type *atp) {
457 assert(tp && is_type(tp));
458 assert(atp && is_Array_type(atp));
460 pts = get_type_arraytype_array(tp);
461 ARR_APP1(ir_node *, pts, atp);
462 set_type_arraytype_array(tp, pts);
465 void set_type_arraytype_of(const ir_type *tp, int pos, ir_type *atp) {
468 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
469 assert(atp && is_Array_type(atp));
471 pts = get_type_arraytype_array(tp);
475 /*------------------------------------------------------------------*/
476 /* Building and Removing the out datastructure */
477 /*------------------------------------------------------------------*/
479 /** Initialize the trouts handling. */
480 static void init_trouts(void) {
483 /** The number of entities that can be accessed by this Sel node. */
484 static int get_Sel_n_accessed_entities(const ir_node *sel) {
489 /** The entity that cat be accessed by this Sel node. */
490 static ir_entity *get_Sel_accessed_entity(const ir_node *sel) {
491 return get_Sel_entity(sel);
494 /** An addr node is a SymConst or a Sel. */
495 static int get_addr_n_entities(const ir_node *addr) {
496 switch (get_irn_opcode(addr)) {
498 /* Treat jack array sels? */
499 return get_Sel_n_accessed_entities(addr);
501 if (get_SymConst_kind(addr) == symconst_addr_ent)
509 /** An addr node is a SymConst or a Sel.
510 If Sel follow to outermost of compound. */
511 static ir_entity *get_addr_entity(const ir_node *addr, int pos) {
515 switch (get_irn_opcode(addr)) {
517 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
518 ptr = get_Sel_ptr(addr);
519 while (is_Sel(ptr)) {
521 ptr = get_Sel_ptr(addr);
523 assert(0 <= pos && pos < get_Sel_n_accessed_entities(addr));
524 return get_Sel_accessed_entity(addr);
526 if (get_SymConst_kind(addr) == symconst_addr_ent) {
528 return get_SymConst_entity(addr);
536 static void chain_accesses(ir_node *n, void *env) {
542 add_type_alloc(get_Alloc_type(n), n);
544 } else if (is_Cast(n)) {
545 add_type_cast(get_Cast_type(n), n);
547 } else if (is_Sel(n)) {
548 add_entity_reference(get_Sel_entity(n), n);
550 } else if (is_SymConst_addr_ent(n)) {
551 add_entity_reference(get_SymConst_entity(n), n);
553 } else if (is_memop(n)) {
554 addr = get_memop_ptr(n);
555 } else if (is_Call(n)) {
556 addr = get_Call_ptr(n);
557 if (! is_Sel(addr)) return; /* Sels before Calls mean a Load / polymorphic Call. */
562 n_ents = get_addr_n_entities(addr); /* == 1 */
563 for (i = 0; i < n_ents; ++i) {
564 ir_entity *ent = get_addr_entity(addr, i);
566 add_entity_access(ent, n);
568 //add_unrecognized_access(n);
573 * Handle chain types (pointer, array) by adding them to
576 static void chain_types(ir_type *tp) {
577 if (is_Pointer_type(tp)) {
578 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
579 } else if (is_Array_type(tp)) {
580 add_type_arraytype_of(get_array_element_type(tp), tp);
584 irg_outs_state get_trouts_state(void) {
585 return irp->trouts_state;
588 void set_trouts_inconsistent(void) {
589 if (irp->trouts_state == outs_consistent)
590 irp->trouts_state = outs_inconsistent;
593 /* compute the trouts data structures. */
594 void compute_trouts(void) {
600 /* Compute outs for IR nodes. */
601 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
602 irg_walk_graph(get_irp_irg(i), NULL, chain_accesses, NULL);
604 walk_const_code(NULL, chain_accesses, NULL);
606 /* Compute outs for types */
607 for (i = get_irp_n_types() - 1; i >= 0; --i) {
608 chain_types(get_irp_type(i));
611 irp->trouts_state = outs_consistent;
614 void free_trouts(void) {
615 if (entity_access_map) {
617 for (accs = (ir_node **)pmap_first(entity_access_map);
619 accs = (ir_node **)pmap_next(entity_access_map))
621 pmap_destroy(entity_access_map);
622 entity_access_map = NULL;
625 if (entity_reference_map) {
627 for (refs = (ir_node **)pmap_first(entity_reference_map);
629 refs = (ir_node **)pmap_next(entity_reference_map))
631 pmap_destroy(entity_reference_map);
632 entity_reference_map = NULL;
635 if (type_alloc_map) {
637 for (alls = (ir_node **)pmap_first(type_alloc_map);
639 alls = (ir_node **)pmap_next(type_alloc_map))
641 pmap_destroy(type_alloc_map);
642 type_alloc_map = NULL;
647 for (casts = (ir_node **)pmap_first(type_cast_map);
649 casts = (ir_node **)pmap_next(type_cast_map))
651 pmap_destroy(type_cast_map);
652 type_cast_map = NULL;
655 if (type_pointertype_map) {
657 for (pts = (ir_node **)pmap_first(type_pointertype_map);
659 pts = (ir_node **)pmap_next(type_pointertype_map))
661 pmap_destroy(type_pointertype_map);
662 type_pointertype_map = NULL;
665 if (type_arraytype_map) {
667 for (pts = (ir_node **)pmap_first(type_arraytype_map);
669 pts = (ir_node **)pmap_next(type_arraytype_map))
671 pmap_destroy(type_arraytype_map);
672 type_arraytype_map = NULL;
675 irp->trouts_state = outs_none;