2 * Copyright (C) 1995-2007 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(ir_entity *ent) {
59 if (!entity_access_map) entity_access_map = pmap_create();
61 if (pmap_contains(entity_access_map, (void *)ent)) {
62 res = (ir_node **) pmap_get(entity_access_map, (void *)ent);
64 res = NEW_ARR_F(ir_node *, 0);
65 pmap_insert(entity_access_map, (void *)ent, (void *)res);
70 void set_entity_access_array(ir_entity *ent, ir_node **accs) {
71 ir_node **old = pmap_get(entity_access_map, (void *)ent);
73 pmap_insert(entity_access_map, (void *)ent, (void *)accs);
77 * Return a flexible array containing all IR-nodes
78 * that reference a given entity.
80 static ir_node **get_entity_reference_array(ir_entity *ent) {
82 if (!entity_reference_map) entity_reference_map = pmap_create();
84 if (pmap_contains(entity_reference_map, (void *)ent)) {
85 res = (ir_node **) pmap_get(entity_reference_map, (void *)ent);
87 res = NEW_ARR_F(ir_node *, 0);
88 pmap_insert(entity_reference_map, (void *)ent, (void *)res);
93 void set_entity_reference_array(ir_entity *ent, ir_node **refs) {
94 ir_node **old = pmap_get(entity_reference_map, (void *)ent);
96 pmap_insert(entity_reference_map, (void *)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(ir_type *tp) {
105 if (!type_alloc_map) type_alloc_map = pmap_create();
107 if (pmap_contains(type_alloc_map, (void *)tp)) {
108 res = (ir_node **) pmap_get(type_alloc_map, (void *)tp);
110 res = NEW_ARR_F(ir_node *, 0);
111 pmap_insert(type_alloc_map, (void *)tp, (void *)res);
116 void set_type_alloc_array(ir_type *tp, ir_node **alls) {
117 ir_node **old = pmap_get(type_alloc_map, (void *)tp);
119 pmap_insert(type_alloc_map, (void *)tp, (void *)alls);
123 * Return a flexible array containing all Cast-nodes
124 * that "create" a given type.
126 static ir_node **get_type_cast_array(ir_type *tp) {
128 if (!type_cast_map) type_cast_map = pmap_create();
130 if (pmap_contains(type_cast_map, (void *)tp)) {
131 res = (ir_node **) pmap_get(type_cast_map, (void *)tp);
133 res = NEW_ARR_F(ir_node *, 0);
134 pmap_insert(type_cast_map, (void *)tp, (void *)res);
139 void set_type_cast_array(ir_type *tp, ir_node **alls) {
140 ir_node **old = pmap_get(type_cast_map, (void *)tp);
142 pmap_insert(type_cast_map, (void *)tp, (void *)alls);
146 * Return a flexible array containing all pointer
147 * types that points-to a given type.
149 static ir_type **get_type_pointertype_array(ir_type *tp) {
151 if (!type_pointertype_map) type_pointertype_map = pmap_create();
153 if (pmap_contains(type_pointertype_map, (void *)tp)) {
154 res = (ir_type **) pmap_get(type_pointertype_map, (void *)tp);
156 res = NEW_ARR_F(ir_type *, 0);
157 pmap_insert(type_pointertype_map, (void *)tp, (void *)res);
162 void set_type_pointertype_array(ir_type *tp, ir_type **pts) {
163 ir_type **old = pmap_get(type_pointertype_map, (void *)tp);
165 pmap_insert(type_pointertype_map, (void *)tp, (void *)pts);
169 * Return a flexible array containing all array
170 * types that have a given type as element type.
172 static ir_type **get_type_arraytype_array(ir_type *tp) {
174 if (!type_arraytype_map) type_arraytype_map = pmap_create();
176 if (pmap_contains(type_arraytype_map, (void *)tp)) {
177 res = (ir_type **) pmap_get(type_arraytype_map, (void *)tp);
179 res = NEW_ARR_F(ir_type *, 0);
180 pmap_insert(type_arraytype_map, (void *)tp, (void *)res);
186 void set_type_arraytype_array(ir_type *tp, ir_type **pts) {
187 ir_type **old = pmap_get(type_arraytype_map, (void *)tp);
189 pmap_insert(type_arraytype_map, (void *)tp, (void *)pts);
192 /*------------------------------------------------------------------*/
193 /* Accessing the out data structures. */
194 /* These routines only work properly if firm is in state */
195 /* trouts_consistent or trouts_inconsistent. */
196 /*------------------------------------------------------------------*/
198 /**------------------------------------------------------------------*/
199 /* Access routines for entities */
200 /**------------------------------------------------------------------*/
202 int get_entity_n_accesses(ir_entity *ent) {
205 assert(ent && is_entity(ent));
207 accs = get_entity_access_array(ent);
208 return ARR_LEN(accs);
211 ir_node *get_entity_access(ir_entity *ent, int pos) {
214 assert(0 <= pos && pos < get_entity_n_accesses(ent));
216 accs = get_entity_access_array(ent);
220 void add_entity_access(ir_entity *ent, ir_node *n) {
223 assert(ent && is_entity(ent));
224 assert(n && is_ir_node(n));
226 accs = get_entity_access_array(ent);
227 ARR_APP1(ir_node *, accs, n);
228 set_entity_access_array(ent, accs);
231 void set_entity_access(ir_entity *ent, int pos, ir_node *n) {
234 assert(0 <= pos && pos < get_entity_n_accesses(ent));
235 assert(n && is_ir_node(n));
237 accs = get_entity_access_array(ent);
241 /**------------------------------------------------------------------*/
243 int get_entity_n_references(ir_entity *ent) {
246 assert(ent && is_entity(ent));
248 refs = get_entity_reference_array(ent);
249 return ARR_LEN(refs);
252 ir_node *get_entity_reference(ir_entity *ent, int pos) {
255 assert(0 <= pos && pos < get_entity_n_references(ent));
257 refs = get_entity_reference_array(ent);
261 void add_entity_reference(ir_entity *ent, ir_node *n) {
264 assert(ent && is_entity(ent));
265 assert(n && is_ir_node(n));
267 refs = get_entity_reference_array(ent);
268 ARR_APP1(ir_node *, refs, n);
269 set_entity_reference_array(ent, refs);
272 void set_entity_reference(ir_entity *ent, int pos, ir_node *n) {
275 assert(0 <= pos && pos < get_entity_n_references(ent));
276 assert(n && is_ir_node(n));
278 refs = get_entity_reference_array(ent);
283 /**------------------------------------------------------------------*/
284 /* Access routines for types */
285 /**------------------------------------------------------------------*/
287 /* Number of Alloc nodes that create an instance of this type */
288 int get_type_n_allocs(ir_type *tp) {
291 assert(tp && is_type(tp));
293 allocs = get_type_alloc_array(tp);
294 return ARR_LEN(allocs);
297 /* Alloc node that creates an instance of this type */
298 ir_node *get_type_alloc(ir_type *tp, int pos) {
300 assert(0 <= pos && pos < get_type_n_allocs(tp));
302 allocs = get_type_alloc_array(tp);
306 void add_type_alloc(ir_type *tp, ir_node *n) {
309 assert(tp && is_type(tp));
310 assert(n && is_ir_node(n));
312 allocs = get_type_alloc_array(tp);
313 ARR_APP1(ir_node *, allocs, n);
314 set_type_alloc_array(tp, allocs);
317 void set_type_alloc(ir_type *tp, int pos, ir_node *n) {
320 assert(0 <= pos && pos < get_type_n_allocs(tp));
321 assert(n && is_ir_node(n));
323 allocs = get_type_alloc_array(tp);
327 /* Number of Cast nodes that create an instance of this type */
328 int get_type_n_casts(ir_type *tp) {
331 assert(tp && is_type(tp));
333 casts = get_type_cast_array(tp);
334 return ARR_LEN(casts);
338 int get_class_n_upcasts(ir_type *clss) {
339 int i, n_casts = get_type_n_casts(clss);
341 for (i = 0; i < n_casts; ++i) {
342 ir_node *cast = get_type_cast(clss, i);
343 if (is_Cast_upcast(cast)) n_instances ++;
348 int get_class_n_downcasts(ir_type *clss) {
349 int i, n_casts = get_type_n_casts(clss);
351 for (i = 0; i < n_casts; ++i) {
352 ir_node *cast = get_type_cast(clss, i);
353 if (is_Cast_downcast(cast)) n_instances ++;
359 /* Cast node that creates an instance of this type */
360 ir_node *get_type_cast(ir_type *tp, int pos) {
362 assert(0 <= pos && pos < get_type_n_casts(tp));
364 casts = get_type_cast_array(tp);
368 void add_type_cast(ir_type *tp, ir_node *n) {
371 assert(tp && is_type(tp));
372 assert(n && is_ir_node(n));
374 casts = get_type_cast_array(tp);
375 ARR_APP1(ir_node *, casts, n);
376 set_type_cast_array(tp, casts);
379 void set_type_cast(ir_type *tp, int pos, ir_node *n) {
382 assert(0 <= pos && pos < get_type_n_casts(tp));
383 assert(n && is_ir_node(n));
385 casts = get_type_cast_array(tp);
389 /**------------------------------------------------------------------*/
391 int get_type_n_pointertypes_to(ir_type *tp) {
394 assert(tp && is_type(tp));
396 pts = get_type_pointertype_array(tp);
400 ir_type *get_type_pointertype_to(ir_type *tp, int pos) {
403 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
405 pts = get_type_pointertype_array(tp);
409 void add_type_pointertype_to(ir_type *tp, ir_type *ptp) {
412 assert(tp && is_type(tp));
413 assert(ptp && is_Pointer_type(ptp));
415 pts = get_type_pointertype_array(tp);
416 ARR_APP1(ir_node *, pts, ptp);
417 set_type_pointertype_array(tp, pts);
420 void set_type_pointertype_to(ir_type *tp, int pos, ir_type *ptp) {
423 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
424 assert(ptp && is_Pointer_type(ptp));
426 pts = get_type_pointertype_array(tp);
431 /**------------------------------------------------------------------*/
433 int get_type_n_arraytypes_of(ir_type *tp) {
436 assert(tp && is_type(tp));
438 pts = get_type_arraytype_array(tp);
442 ir_type *get_type_arraytype_of(ir_type *tp, int pos) {
445 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
447 pts = get_type_arraytype_array(tp);
451 void add_type_arraytype_of(ir_type *tp, ir_type *atp) {
454 assert(tp && is_type(tp));
455 assert(atp && is_Array_type(atp));
457 pts = get_type_arraytype_array(tp);
458 ARR_APP1(ir_node *, pts, atp);
459 set_type_arraytype_array(tp, pts);
462 void set_type_arraytype_of(ir_type *tp, int pos, ir_type *atp) {
465 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
466 assert(atp && is_Array_type(atp));
468 pts = get_type_arraytype_array(tp);
472 /*------------------------------------------------------------------*/
473 /* Building and Removing the out datastructure */
474 /*------------------------------------------------------------------*/
476 static void init_trouts(void) {
480 /** The number of entities that can be accessed by this Sel node. */
481 static int get_Sel_n_accessed_entities(ir_node *sel) {
486 /** The entity that cat be accessed by this Sel node. */
487 static ir_entity *get_Sel_accessed_entity(ir_node *sel) {
488 return get_Sel_entity(sel);
491 /** An addr node is a SymConst or a Sel. */
492 static int get_addr_n_entities(ir_node *addr) {
495 switch (get_irn_opcode(addr)) {
497 /* Treat jack array sels? */
498 n_ents = get_Sel_n_accessed_entities(addr);
501 if (get_SymConst_kind(addr) == symconst_addr_ent) {
506 //assert(0 && "unexpected address expression");
513 /** An addr node is a SymConst or a Sel.
514 If Sel follow to outermost of compound. */
515 static ir_entity *get_addr_entity(ir_node *addr, int pos) {
518 switch (get_irn_opcode(addr)) {
520 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
521 while (is_Sel(get_Sel_ptr(addr))) {
522 addr = get_Sel_ptr(addr);
524 assert (0 <= pos && pos < get_Sel_n_accessed_entities(addr));
525 ent = get_Sel_accessed_entity(addr);
528 if (get_SymConst_kind(addr) == symconst_addr_ent) {
530 ent = get_SymConst_entity(addr);
540 static void chain_accesses(ir_node *n, void *env) {
545 if (get_irn_op(n) == op_Alloc) {
546 add_type_alloc(get_Alloc_type(n), n);
550 if (get_irn_op(n) == op_Cast) {
551 add_type_cast(get_Cast_type(n), n);
555 if (get_irn_op(n) == op_Sel) {
556 add_entity_reference(get_Sel_entity(n), n);
558 } else if (get_irn_op(n) == op_SymConst && (get_SymConst_kind(n) == symconst_addr_ent)) {
559 add_entity_reference(get_SymConst_entity(n), n);
564 addr = get_memop_ptr(n);
565 } else if (get_irn_op(n) == op_Call) {
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);
582 static void chain_types(ir_type *tp) {
583 if (is_Pointer_type(tp)) {
584 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
585 } else if (is_Array_type(tp)) {
586 add_type_arraytype_of(get_array_element_type(tp), tp);
590 irg_outs_state get_trouts_state(void) {
591 return irp->trouts_state;
593 void set_trouts_inconsistent(void) {
594 if (irp->trouts_state == outs_consistent)
595 irp->trouts_state = outs_inconsistent;
599 /* compute the field temperature. */
600 void compute_trouts(void) {
602 n_irgs = get_irp_n_irgs(),
603 n_types = get_irp_n_types();
608 /* Compute outs for irnodes. */
609 for (i = 0; i < n_irgs; i++) {
610 irg_walk_graph(get_irp_irg(i), NULL, chain_accesses, NULL);
612 walk_const_code(NULL, chain_accesses, NULL);
614 /* Compute outs for types */
615 for (i = 0; i < n_types; ++i) {
616 chain_types(get_irp_type(i));
619 irp->trouts_state = outs_consistent;
623 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;