3 * File name: ir/ana/trouts.c
4 * Purpose: Reverse edges that reference types/entities.
5 * Author: Goetz Lindenmaier
9 * Copyright: (c) 2004 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
22 /*------------------------------------------------------------------*/
23 /* We represent the fields in entities/types by hashmaps. */
24 /*------------------------------------------------------------------*/
26 static pmap *entity_access_map = NULL;
27 static pmap *entity_reference_map = NULL;
28 static pmap *type_alloc_map = NULL;
29 static pmap *type_cast_map = NULL;
30 static pmap *type_pointertype_map = NULL;
31 static pmap *type_arraytype_map = NULL;
33 static ir_node **get_entity_access_array(entity *ent) {
35 if (!entity_access_map) entity_access_map = pmap_create();
37 if (pmap_contains(entity_access_map, (void *)ent)) {
38 res = (ir_node **) pmap_get(entity_access_map, (void *)ent);
40 res = NEW_ARR_F(ir_node *, 0);
41 pmap_insert(entity_access_map, (void *)ent, (void *)res);
46 void set_entity_access_array(entity *ent, ir_node **accs) {
47 ir_node **old = pmap_get(entity_access_map, (void *)ent);
49 pmap_insert(entity_access_map, (void *)ent, (void *)accs);
52 static ir_node **get_entity_reference_array(entity *ent) {
54 if (!entity_reference_map) entity_reference_map = pmap_create();
56 if (pmap_contains(entity_reference_map, (void *)ent)) {
57 res = (ir_node **) pmap_get(entity_reference_map, (void *)ent);
59 res = NEW_ARR_F(ir_node *, 0);
60 pmap_insert(entity_reference_map, (void *)ent, (void *)res);
65 void set_entity_reference_array(entity *ent, ir_node **refs) {
66 ir_node **old = pmap_get(entity_reference_map, (void *)ent);
68 pmap_insert(entity_reference_map, (void *)ent, (void *)refs);
71 static ir_node **get_type_alloc_array(ir_type *tp) {
73 if (!type_alloc_map) type_alloc_map = pmap_create();
75 if (pmap_contains(type_alloc_map, (void *)tp)) {
76 res = (ir_node **) pmap_get(type_alloc_map, (void *)tp);
78 res = NEW_ARR_F(ir_node *, 0);
79 pmap_insert(type_alloc_map, (void *)tp, (void *)res);
84 void set_type_alloc_array(ir_type *tp, ir_node **alls) {
85 ir_node **old = pmap_get(type_alloc_map, (void *)tp);
87 pmap_insert(type_alloc_map, (void *)tp, (void *)alls);
90 static ir_node **get_type_cast_array(ir_type *tp) {
92 if (!type_cast_map) type_cast_map = pmap_create();
94 if (pmap_contains(type_cast_map, (void *)tp)) {
95 res = (ir_node **) pmap_get(type_cast_map, (void *)tp);
97 res = NEW_ARR_F(ir_node *, 0);
98 pmap_insert(type_cast_map, (void *)tp, (void *)res);
103 void set_type_cast_array(ir_type *tp, ir_node **alls) {
104 ir_node **old = pmap_get(type_cast_map, (void *)tp);
106 pmap_insert(type_cast_map, (void *)tp, (void *)alls);
109 static ir_type **get_type_pointertype_array(ir_type *tp) {
111 if (!type_pointertype_map) type_pointertype_map = pmap_create();
113 if (pmap_contains(type_pointertype_map, (void *)tp)) {
114 res = (ir_type **) pmap_get(type_pointertype_map, (void *)tp);
116 res = NEW_ARR_F(ir_type *, 0);
117 pmap_insert(type_pointertype_map, (void *)tp, (void *)res);
122 void set_type_pointertype_array(ir_type *tp, ir_type **pts) {
123 ir_type **old = pmap_get(type_pointertype_map, (void *)tp);
125 pmap_insert(type_pointertype_map, (void *)tp, (void *)pts);
128 static ir_type **get_type_arraytype_array(ir_type *tp) {
130 if (!type_arraytype_map) type_arraytype_map = pmap_create();
132 if (pmap_contains(type_arraytype_map, (void *)tp)) {
133 res = (ir_type **) pmap_get(type_arraytype_map, (void *)tp);
135 res = NEW_ARR_F(ir_type *, 0);
136 pmap_insert(type_arraytype_map, (void *)tp, (void *)res);
142 void set_type_arraytype_array(ir_type *tp, ir_type **pts) {
143 ir_type **old = pmap_get(type_arraytype_map, (void *)tp);
145 pmap_insert(type_arraytype_map, (void *)tp, (void *)pts);
148 /*------------------------------------------------------------------*/
149 /* Accessing the out data structures. */
150 /* These routines only work properly if firm is in state */
151 /* trouts_consistent or trouts_inconsistent. */
152 /*------------------------------------------------------------------*/
154 /**------------------------------------------------------------------*/
155 /* Access routines for entities */
156 /**------------------------------------------------------------------*/
158 int get_entity_n_accesses(entity *ent) {
161 assert(ent && is_entity(ent));
163 accs = get_entity_access_array(ent);
164 return ARR_LEN(accs);
167 ir_node *get_entity_access(entity *ent, int pos) {
170 assert(0 <= pos && pos < get_entity_n_accesses(ent));
172 accs = get_entity_access_array(ent);
176 void add_entity_access(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 void set_entity_access(entity *ent, int pos, ir_node *n) {
190 assert(0 <= pos && pos < get_entity_n_accesses(ent));
191 assert(n && is_ir_node(n));
193 accs = get_entity_access_array(ent);
197 /**------------------------------------------------------------------*/
199 int get_entity_n_references(entity *ent) {
202 assert(ent && is_entity(ent));
204 refs = get_entity_reference_array(ent);
205 return ARR_LEN(refs);
208 ir_node *get_entity_reference(entity *ent, int pos) {
211 assert(0 <= pos && pos < get_entity_n_references(ent));
213 refs = get_entity_reference_array(ent);
217 void add_entity_reference(entity *ent, ir_node *n) {
220 assert(ent && is_entity(ent));
221 assert(n && is_ir_node(n));
223 refs = get_entity_reference_array(ent);
224 ARR_APP1(ir_node *, refs, n);
225 set_entity_reference_array(ent, refs);
228 void set_entity_reference(entity *ent, int pos, ir_node *n) {
231 assert(0 <= pos && pos < get_entity_n_references(ent));
232 assert(n && is_ir_node(n));
234 refs = get_entity_reference_array(ent);
239 /**------------------------------------------------------------------*/
240 /* Access routines for types */
241 /**------------------------------------------------------------------*/
243 /* Number of Alloc nodes that create an instance of this type */
244 int get_type_n_allocs(ir_type *tp) {
247 assert(tp && is_type(tp));
249 allocs = get_type_alloc_array(tp);
250 return ARR_LEN(allocs);
253 /* Alloc node that creates an instance of this type */
254 ir_node *get_type_alloc(ir_type *tp, int pos) {
256 assert(0 <= pos && pos < get_type_n_allocs(tp));
258 allocs = get_type_alloc_array(tp);
262 void add_type_alloc(ir_type *tp, ir_node *n) {
265 assert(tp && is_type(tp));
266 assert(n && is_ir_node(n));
268 allocs = get_type_alloc_array(tp);
269 ARR_APP1(ir_node *, allocs, n);
270 set_type_alloc_array(tp, allocs);
273 void set_type_alloc(ir_type *tp, int pos, ir_node *n) {
276 assert(0 <= pos && pos < get_type_n_allocs(tp));
277 assert(n && is_ir_node(n));
279 allocs = get_type_alloc_array(tp);
283 /* Number of Cast nodes that create an instance of this type */
284 int get_type_n_casts(ir_type *tp) {
287 assert(tp && is_type(tp));
289 casts = get_type_cast_array(tp);
290 return ARR_LEN(casts);
294 int get_class_n_upcasts(ir_type *clss) {
295 int i, n_casts = get_type_n_casts(clss);
297 for (i = 0; i < n_casts; ++i) {
298 ir_node *cast = get_type_cast(clss, i);
299 if (is_Cast_upcast(cast)) n_instances ++;
304 int get_class_n_downcasts(ir_type *clss) {
305 int i, n_casts = get_type_n_casts(clss);
307 for (i = 0; i < n_casts; ++i) {
308 ir_node *cast = get_type_cast(clss, i);
309 if (is_Cast_downcast(cast)) n_instances ++;
315 /* Cast node that creates an instance of this type */
316 ir_node *get_type_cast(ir_type *tp, int pos) {
318 assert(0 <= pos && pos < get_type_n_casts(tp));
320 casts = get_type_cast_array(tp);
324 void add_type_cast(ir_type *tp, ir_node *n) {
327 assert(tp && is_type(tp));
328 assert(n && is_ir_node(n));
330 casts = get_type_cast_array(tp);
331 ARR_APP1(ir_node *, casts, n);
332 set_type_cast_array(tp, casts);
335 void set_type_cast(ir_type *tp, int pos, ir_node *n) {
338 assert(0 <= pos && pos < get_type_n_casts(tp));
339 assert(n && is_ir_node(n));
341 casts = get_type_cast_array(tp);
345 /**------------------------------------------------------------------*/
347 int get_type_n_pointertypes_to(ir_type *tp) {
350 assert(tp && is_type(tp));
352 pts = get_type_pointertype_array(tp);
356 ir_type *get_type_pointertype_to(ir_type *tp, int pos) {
359 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
361 pts = get_type_pointertype_array(tp);
365 void add_type_pointertype_to(ir_type *tp, ir_type *ptp) {
368 assert(tp && is_type(tp));
369 assert(ptp && is_Pointer_type(ptp));
371 pts = get_type_pointertype_array(tp);
372 ARR_APP1(ir_node *, pts, ptp);
373 set_type_pointertype_array(tp, pts);
376 void set_type_pointertype_to(ir_type *tp, int pos, ir_type *ptp) {
379 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
380 assert(ptp && is_Pointer_type(ptp));
382 pts = get_type_pointertype_array(tp);
387 /**------------------------------------------------------------------*/
389 int get_type_n_arraytypes_of(ir_type *tp) {
392 assert(tp && is_type(tp));
394 pts = get_type_arraytype_array(tp);
398 ir_type *get_type_arraytype_of(ir_type *tp, int pos) {
401 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
403 pts = get_type_arraytype_array(tp);
407 void add_type_arraytype_of(ir_type *tp, ir_type *atp) {
410 assert(tp && is_type(tp));
411 assert(atp && is_Array_type(atp));
413 pts = get_type_arraytype_array(tp);
414 ARR_APP1(ir_node *, pts, atp);
415 set_type_arraytype_array(tp, pts);
418 void set_type_arraytype_of(ir_type *tp, int pos, ir_type *atp) {
421 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
422 assert(atp && is_Array_type(atp));
424 pts = get_type_arraytype_array(tp);
428 /*------------------------------------------------------------------*/
429 /* Building and Removing the out datastructure */
430 /*------------------------------------------------------------------*/
432 static void init_trouts(void) {
436 /* The entities that can be accessed by this Sel node. */
437 static int get_Sel_n_accessed_entities(ir_node *sel) {
441 static entity *get_Sel_accessed_entity(ir_node *sel) {
442 return get_Sel_entity(sel);
445 /* An addr node is a SymConst or a Sel. */
446 static int get_addr_n_entities(ir_node *addr) {
449 switch (get_irn_opcode(addr)) {
451 /* Treat jack array sels? */
452 n_ents = get_Sel_n_accessed_entities(addr);
455 if (get_SymConst_kind(addr) == symconst_addr_ent) {
460 //assert(0 && "unexpected address expression");
467 /* An addr node is a SymConst or a Sel.
468 If Sel follow to outermost of compound. */
469 static entity *get_addr_entity(ir_node *addr, int pos) {
472 switch (get_irn_opcode(addr)) {
474 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
475 while (is_Sel(get_Sel_ptr(addr))) {
476 addr = get_Sel_ptr(addr);
478 assert (0 <= pos && pos < get_Sel_n_accessed_entities(addr));
479 ent = get_Sel_accessed_entity(addr);
482 if (get_SymConst_kind(addr) == symconst_addr_ent) {
484 ent = get_SymConst_entity(addr);
494 static void chain_accesses(ir_node *n, void *env) {
498 if (get_irn_op(n) == op_Alloc) {
499 add_type_alloc(get_Alloc_type(n), n);
503 if (get_irn_op(n) == op_Cast) {
504 add_type_cast(get_Cast_type(n), n);
508 if (get_irn_op(n) == op_Sel) {
509 add_entity_reference(get_Sel_entity(n), n);
511 } else if (get_irn_op(n) == op_SymConst && (get_SymConst_kind(n) == symconst_addr_ent)) {
512 add_entity_reference(get_SymConst_entity(n), n);
517 addr = get_memop_ptr(n);
518 } else if (get_irn_op(n) == op_Call) {
519 addr = get_Call_ptr(n);
520 if (! is_Sel(addr)) return; /* Sels before Calls mean a Load / polymorphic Call. */
525 n_ents = get_addr_n_entities(addr); /* == 1 */
526 for (i = 0; i < n_ents; ++i) {
527 entity *ent = get_addr_entity(addr, i);
529 add_entity_access(ent, n);
531 //add_unrecognized_access(n);
535 static void chain_types(ir_type *tp) {
536 if (is_Pointer_type(tp)) {
537 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
538 } else if (is_Array_type(tp)) {
539 add_type_arraytype_of(get_array_element_type(tp), tp);
543 irg_outs_state get_trouts_state(void) {
544 return irp->trouts_state;
546 void set_trouts_inconsistent(void) {
547 if (irp->trouts_state == outs_consistent)
548 irp->trouts_state = outs_inconsistent;
552 /* compute the field temperature. */
553 void compute_trouts(void) {
555 n_irgs = get_irp_n_irgs(),
556 n_types = get_irp_n_types();
561 /* Compute outs for irnodes. */
562 for (i=0; i < n_irgs; i++) {
563 current_ir_graph = get_irp_irg(i);
564 irg_walk_graph(current_ir_graph, NULL, chain_accesses, NULL);
566 walk_const_code(NULL, chain_accesses, NULL);
568 /* Compute outs for types */
569 for (i = 0; i < n_types; ++i) {
570 chain_types(get_irp_type(i));
573 irp->trouts_state = outs_consistent;
577 void free_trouts(void) {
579 if (entity_access_map) {
581 for (accs = (ir_node **)pmap_first(entity_access_map);
583 accs = (ir_node **)pmap_next(entity_access_map))
585 pmap_destroy(entity_access_map);
586 entity_access_map = NULL;
589 if (entity_reference_map) {
591 for (refs = (ir_node **)pmap_first(entity_reference_map);
593 refs = (ir_node **)pmap_next(entity_reference_map))
595 pmap_destroy(entity_reference_map);
596 entity_reference_map = NULL;
599 if (type_alloc_map) {
601 for (alls = (ir_node **)pmap_first(type_alloc_map);
603 alls = (ir_node **)pmap_next(type_alloc_map))
605 pmap_destroy(type_alloc_map);
606 type_alloc_map = NULL;
611 for (casts = (ir_node **)pmap_first(type_cast_map);
613 casts = (ir_node **)pmap_next(type_cast_map))
615 pmap_destroy(type_cast_map);
616 type_cast_map = NULL;
619 if (type_pointertype_map) {
621 for (pts = (ir_node **)pmap_first(type_pointertype_map);
623 pts = (ir_node **)pmap_next(type_pointertype_map))
625 pmap_destroy(type_pointertype_map);
626 type_pointertype_map = NULL;
629 if (type_arraytype_map) {
631 for (pts = (ir_node **)pmap_first(type_arraytype_map);
633 pts = (ir_node **)pmap_next(type_arraytype_map))
635 pmap_destroy(type_arraytype_map);
636 type_arraytype_map = NULL;
639 irp->trouts_state = outs_none;