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;
32 static ir_node **get_entity_access_array(entity *ent) {
34 if (!entity_access_map) entity_access_map = pmap_create();
36 if (pmap_contains(entity_access_map, (void *)ent)) {
37 res = (ir_node **) pmap_get(entity_access_map, (void *)ent);
39 res = NEW_ARR_F(ir_node *, 0);
40 pmap_insert(entity_access_map, (void *)ent, (void *)res);
45 void set_entity_access_array(entity *ent, ir_node **accs) {
46 ir_node **old = pmap_get(entity_access_map, (void *)ent);
48 pmap_insert(entity_access_map, (void *)ent, (void *)accs);
51 static ir_node **get_entity_reference_array(entity *ent) {
53 if (!entity_reference_map) entity_reference_map = pmap_create();
55 if (pmap_contains(entity_reference_map, (void *)ent)) {
56 res = (ir_node **) pmap_get(entity_reference_map, (void *)ent);
58 res = NEW_ARR_F(ir_node *, 0);
59 pmap_insert(entity_reference_map, (void *)ent, (void *)res);
64 void set_entity_reference_array(entity *ent, ir_node **refs) {
65 ir_node **old = pmap_get(entity_reference_map, (void *)ent);
67 pmap_insert(entity_reference_map, (void *)ent, (void *)refs);
70 static ir_node **get_type_alloc_array(type *tp) {
72 if (!type_alloc_map) type_alloc_map = pmap_create();
74 if (pmap_contains(type_alloc_map, (void *)tp)) {
75 res = (ir_node **) pmap_get(type_alloc_map, (void *)tp);
77 res = NEW_ARR_F(ir_node *, 0);
78 pmap_insert(type_alloc_map, (void *)tp, (void *)res);
83 void set_type_alloc_array(type *tp, ir_node **alls) {
84 ir_node **old = pmap_get(type_alloc_map, (void *)tp);
86 pmap_insert(type_alloc_map, (void *)tp, (void *)alls);
89 static ir_node **get_type_cast_array(type *tp) {
91 if (!type_cast_map) type_cast_map = pmap_create();
93 if (pmap_contains(type_cast_map, (void *)tp)) {
94 res = (ir_node **) pmap_get(type_cast_map, (void *)tp);
96 res = NEW_ARR_F(ir_node *, 0);
97 pmap_insert(type_cast_map, (void *)tp, (void *)res);
102 void set_type_cast_array(type *tp, ir_node **alls) {
103 ir_node **old = pmap_get(type_cast_map, (void *)tp);
105 pmap_insert(type_cast_map, (void *)tp, (void *)alls);
108 static type **get_type_pointertype_array(type *tp) {
110 if (!type_pointertype_map) type_pointertype_map = pmap_create();
112 if (pmap_contains(type_pointertype_map, (void *)tp)) {
113 res = (type **) pmap_get(type_pointertype_map, (void *)tp);
115 res = NEW_ARR_F(type *, 0);
116 pmap_insert(type_pointertype_map, (void *)tp, (void *)res);
121 void set_type_pointertype_array(type *tp, type **pts) {
122 type **old = pmap_get(type_pointertype_map, (void *)tp);
124 pmap_insert(type_pointertype_map, (void *)tp, (void *)pts);
127 /*------------------------------------------------------------------*/
128 /* Accessing the out data structures. */
129 /* These routines only work properly if firm is in state */
130 /* trouts_consistent or trouts_inconsistent. */
131 /*------------------------------------------------------------------*/
133 /**------------------------------------------------------------------*/
134 /* Access routines for entities */
135 /**------------------------------------------------------------------*/
137 int get_entity_n_accesses(entity *ent) {
140 assert(ent && is_entity(ent));
142 accs = get_entity_access_array(ent);
143 return ARR_LEN(accs);
146 ir_node *get_entity_access(entity *ent, int pos) {
149 assert(0 <= pos && pos < get_entity_n_accesses(ent));
151 accs = get_entity_access_array(ent);
155 void add_entity_access(entity *ent, ir_node *n) {
158 assert(ent && is_entity(ent));
159 assert(n && is_ir_node(n));
161 accs = get_entity_access_array(ent);
162 ARR_APP1(ir_node *, accs, n);
163 set_entity_access_array(ent, accs);
166 void set_entity_access(entity *ent, int pos, ir_node *n) {
169 assert(0 <= pos && pos < get_entity_n_accesses(ent));
170 assert(n && is_ir_node(n));
172 accs = get_entity_access_array(ent);
176 /**------------------------------------------------------------------*/
178 int get_entity_n_references(entity *ent) {
181 assert(ent && is_entity(ent));
183 refs = get_entity_reference_array(ent);
184 return ARR_LEN(refs);
187 ir_node *get_entity_reference(entity *ent, int pos) {
190 assert(0 <= pos && pos < get_entity_n_references(ent));
192 refs = get_entity_reference_array(ent);
196 void add_entity_reference(entity *ent, ir_node *n) {
199 assert(ent && is_entity(ent));
200 assert(n && is_ir_node(n));
202 refs = get_entity_reference_array(ent);
203 ARR_APP1(ir_node *, refs, n);
204 set_entity_reference_array(ent, refs);
207 void set_entity_reference(entity *ent, int pos, ir_node *n) {
210 assert(0 <= pos && pos < get_entity_n_references(ent));
211 assert(n && is_ir_node(n));
213 refs = get_entity_reference_array(ent);
218 /**------------------------------------------------------------------*/
219 /* Access routines for types */
220 /**------------------------------------------------------------------*/
222 /* Number of Alloc nodes that create an instance of this type */
223 int get_type_n_allocs(type *tp) {
226 assert(tp && is_type(tp));
228 allocs = get_type_alloc_array(tp);
229 return ARR_LEN(allocs);
232 /* Alloc node that creates an instance of this type */
233 ir_node *get_type_alloc(type *tp, int pos) {
235 assert(0 <= pos && pos < get_type_n_allocs(tp));
237 allocs = get_type_alloc_array(tp);
241 void add_type_alloc(type *tp, ir_node *n) {
244 assert(tp && is_type(tp));
245 assert(n && is_ir_node(n));
247 allocs = get_type_alloc_array(tp);
248 ARR_APP1(ir_node *, allocs, n);
249 set_type_alloc_array(tp, allocs);
252 void set_type_alloc(type *tp, int pos, ir_node *n) {
255 assert(0 <= pos && pos < get_type_n_allocs(tp));
256 assert(n && is_ir_node(n));
258 allocs = get_type_alloc_array(tp);
262 /* Number of Cast nodes that create an instance of this type */
263 int get_type_n_casts(type *tp) {
266 assert(tp && is_type(tp));
268 casts = get_type_cast_array(tp);
269 return ARR_LEN(casts);
273 int get_class_n_upcasts(type *clss) {
274 int i, n_casts = get_type_n_casts(clss);
276 for (i = 0; i < n_casts; ++i) {
277 ir_node *cast = get_type_cast(clss, i);
278 if (is_Cast_upcast(cast)) n_instances ++;
283 int get_class_n_downcasts(type *clss) {
284 int i, n_casts = get_type_n_casts(clss);
286 for (i = 0; i < n_casts; ++i) {
287 ir_node *cast = get_type_cast(clss, i);
288 if (is_Cast_downcast(cast)) n_instances ++;
294 /* Cast node that creates an instance of this type */
295 ir_node *get_type_cast(type *tp, int pos) {
297 assert(0 <= pos && pos < get_type_n_casts(tp));
299 casts = get_type_cast_array(tp);
303 void add_type_cast(type *tp, ir_node *n) {
306 assert(tp && is_type(tp));
307 assert(n && is_ir_node(n));
309 casts = get_type_cast_array(tp);
310 ARR_APP1(ir_node *, casts, n);
311 set_type_cast_array(tp, casts);
314 void set_type_cast(type *tp, int pos, ir_node *n) {
317 assert(0 <= pos && pos < get_type_n_casts(tp));
318 assert(n && is_ir_node(n));
320 casts = get_type_cast_array(tp);
324 /**------------------------------------------------------------------*/
326 int get_type_n_pointertypes_to(type *tp) {
329 assert(tp && is_type(tp));
331 pts = get_type_pointertype_array(tp);
335 type *get_type_pointertype_to(type *tp, int pos) {
338 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
340 pts = get_type_pointertype_array(tp);
344 void add_type_pointertype_to(type *tp, type *ptp) {
347 assert(tp && is_type(tp));
348 assert(ptp && is_Pointer_type(ptp));
350 pts = get_type_pointertype_array(tp);
351 ARR_APP1(ir_node *, pts, ptp);
352 set_type_pointertype_array(tp, pts);
355 void set_type_pointertype_to(type *tp, int pos, type *ptp) {
358 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
359 assert(ptp && is_Pointer_type(ptp));
361 pts = get_type_pointertype_array(tp);
365 /*------------------------------------------------------------------*/
366 /* Building and Removing the out datastructure */
367 /*------------------------------------------------------------------*/
369 static void init_trouts(void) {
373 /* The entities that can be accessed by this Sel node. */
374 static int get_Sel_n_accessed_entities(ir_node *sel) {
378 static entity *get_Sel_accessed_entity(ir_node *sel) {
379 return get_Sel_entity(sel);
382 /* An addr node is a SymConst or a Sel. */
383 static int get_addr_n_entities(ir_node *addr) {
386 switch (get_irn_opcode(addr)) {
388 /* Treat jack array sels? */
389 n_ents = get_Sel_n_accessed_entities(addr);
392 if (get_SymConst_kind(addr) == symconst_addr_ent) {
397 //assert(0 && "unexpected address expression");
404 /* An addr node is a SymConst or a Sel.
405 If Sel follow to outermost of compound. */
406 static entity *get_addr_entity(ir_node *addr, int pos) {
409 switch (get_irn_opcode(addr)) {
411 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
412 while (get_irn_op(get_Sel_ptr(addr)) == op_Sel) {
413 addr = get_Sel_ptr(addr);
415 assert (0 <= pos && pos < get_Sel_n_accessed_entities(addr));
416 ent = get_Sel_accessed_entity(addr);
419 if (get_SymConst_kind(addr) == symconst_addr_ent) {
421 ent = get_SymConst_entity(addr);
431 static void chain_accesses(ir_node *n, void *env) {
435 if (get_irn_op(n) == op_Alloc) {
436 add_type_alloc(get_Alloc_type(n), n);
440 if (get_irn_op(n) == op_Cast) {
441 add_type_cast(get_Cast_type(n), n);
445 if (get_irn_op(n) == op_Sel) {
446 add_entity_reference(get_Sel_entity(n), n);
448 } else if (get_irn_op(n) == op_SymConst && (get_SymConst_kind(n) == symconst_addr_ent)) {
449 add_entity_reference(get_SymConst_entity(n), n);
454 addr = get_memop_ptr(n);
455 } else if (get_irn_op(n) == op_Call) {
456 addr = get_Call_ptr(n);
457 if (get_irn_op(addr) != op_Sel) return; /* Sels before Calls mean a Load / polymorphic Call. */
462 n_ents = get_addr_n_entities(addr); /* == 1 */
463 for (i = 0; i < n_ents; ++i) {
464 entity *ent = get_addr_entity(addr, i);
466 add_entity_access(ent, n);
468 //add_unrecognized_access(n);
472 static void chain_types(type *tp) {
473 if (is_Pointer_type(tp)) {
474 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
478 irg_outs_state get_trouts_state(void) {
479 return irp->trouts_state;
481 void set_trouts_inconsistent(void) {
482 irp->trouts_state = outs_inconsistent;
486 /* compute the field temperature. */
487 void compute_trouts(void) {
489 n_irgs = get_irp_n_irgs(),
490 n_types = get_irp_n_types();
495 /* Compute outs for irnodes. */
496 for (i=0; i < n_irgs; i++) {
497 current_ir_graph = get_irp_irg(i);
498 irg_walk_graph(current_ir_graph, NULL, chain_accesses, NULL);
500 walk_const_code(NULL, chain_accesses, NULL);
502 /* Compute outs for types */
503 for (i = 0; i < n_types; ++i) {
504 chain_types(get_irp_type(i));
507 irp->trouts_state = outs_consistent;
511 void free_trouts(void) {
513 if (entity_access_map) {
515 for (accs = (ir_node **)pmap_first(entity_access_map);
517 accs = (ir_node **)pmap_next(entity_access_map))
519 pmap_destroy(entity_access_map);
520 entity_access_map = NULL;
523 if (entity_reference_map) {
525 for (refs = (ir_node **)pmap_first(entity_reference_map);
527 refs = (ir_node **)pmap_next(entity_reference_map))
529 pmap_destroy(entity_reference_map);
530 entity_reference_map = NULL;
533 if (type_alloc_map) {
535 for (alls = (ir_node **)pmap_first(type_alloc_map);
537 alls = (ir_node **)pmap_next(type_alloc_map))
539 pmap_destroy(type_alloc_map);
540 type_alloc_map = NULL;
545 for (casts = (ir_node **)pmap_first(type_cast_map);
547 casts = (ir_node **)pmap_next(type_cast_map))
549 pmap_destroy(type_cast_map);
550 type_cast_map = NULL;
553 if (type_pointertype_map) {
555 for (pts = (ir_node **)pmap_first(type_pointertype_map);
557 pts = (ir_node **)pmap_next(type_pointertype_map))
559 pmap_destroy(type_pointertype_map);
560 type_pointertype_map = NULL;
562 irp->trouts_state = outs_none;