1 /*
2 * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
3 *
4 * This file is part of libFirm.
5 *
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.
10 *
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.
14 *
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
17 * PURPOSE.
18 */
19
20 /**
21 * @file
22 * @brief Reverse edges that reference types/entities.
23 * @author Goetz Lindenmaier
24 * @date 29.10.2004
25 */
26 #include "config.h"
27
28 #include "trouts_t.h"
29
30 #include "array.h"
31 #include "pmap.h"
32
33 #include "irnode_t.h"
34 #include "irprog_t.h"
35 #include "irgwalk.h"
36 #include "irnode.h"
37
38
39 /*------------------------------------------------------------------*/
40 /* We represent the fields in entities/types by hashmaps. */
41 /*------------------------------------------------------------------*/
42
43 static pmap *entity_access_map = NULL;
44 static pmap *entity_reference_map = NULL;
45 static pmap *type_alloc_map = NULL;
46 static pmap *type_cast_map = NULL;
47 static pmap *type_pointertype_map = NULL;
48 static pmap *type_arraytype_map = NULL;
49
50 /**
51 * Return a flexible array containing all IR-nodes
52 * that access a given entity.
53 */
get_entity_access_array(const ir_entity * ent)54 static ir_node **get_entity_access_array(const ir_entity *ent)
55 {
56 if (!entity_access_map) entity_access_map = pmap_create();
57
58 ir_node **res = pmap_get(ir_node*, entity_access_map, ent);
59 if (!res) {
60 res = NEW_ARR_F(ir_node *, 0);
61 pmap_insert(entity_access_map, ent, (void *)res);
62 }
63
64 return res;
65 }
66
set_entity_access_array(const ir_entity * ent,ir_node ** accs)67 static void set_entity_access_array(const ir_entity *ent, ir_node **accs)
68 {
69 pmap_insert(entity_access_map, ent, (void *)accs);
70 }
71
72 /**
73 * Return a flexible array containing all IR-nodes
74 * that reference a given entity.
75 */
get_entity_reference_array(const ir_entity * ent)76 static ir_node **get_entity_reference_array(const ir_entity *ent)
77 {
78 if (!entity_reference_map) entity_reference_map = pmap_create();
79
80 ir_node **res = pmap_get(ir_node*, entity_reference_map, ent);
81 if (!res) {
82 res = NEW_ARR_F(ir_node *, 0);
83 pmap_insert(entity_reference_map, ent, (void *)res);
84 }
85
86 return res;
87 }
88
set_entity_reference_array(const ir_entity * ent,ir_node ** refs)89 static void set_entity_reference_array(const ir_entity *ent, ir_node **refs)
90 {
91 pmap_insert(entity_reference_map, ent, (void *)refs);
92 }
93
94 /**
95 * Return a flexible array containing all IR-nodes
96 * that allocate a given type.
97 */
get_type_alloc_array(const ir_type * tp)98 static ir_node **get_type_alloc_array(const ir_type *tp)
99 {
100 if (!type_alloc_map) type_alloc_map = pmap_create();
101
102 ir_node **res = pmap_get(ir_node*, type_alloc_map, tp);
103 if (!res) {
104 res = NEW_ARR_F(ir_node *, 0);
105 pmap_insert(type_alloc_map, tp, (void *)res);
106 }
107
108 return res;
109 }
110
set_type_alloc_array(const ir_type * tp,ir_node ** alls)111 static void set_type_alloc_array(const ir_type *tp, ir_node **alls)
112 {
113 pmap_insert(type_alloc_map, tp, (void *)alls);
114 }
115
116 /**
117 * Return a flexible array containing all Cast-nodes
118 * that "create" a given type.
119 */
get_type_cast_array(const ir_type * tp)120 static ir_node **get_type_cast_array(const ir_type *tp)
121 {
122 if (!type_cast_map) type_cast_map = pmap_create();
123
124 ir_node **res = pmap_get(ir_node*, type_cast_map, tp);
125 if (!res) {
126 res = NEW_ARR_F(ir_node *, 0);
127 pmap_insert(type_cast_map, tp, (void *)res);
128 }
129 return res;
130 }
131
set_type_cast_array(const ir_type * tp,ir_node ** alls)132 static void set_type_cast_array(const ir_type *tp, ir_node **alls)
133 {
134 pmap_insert(type_cast_map, tp, (void *)alls);
135 }
136
137 /**
138 * Return a flexible array containing all pointer
139 * types that points-to a given type.
140 */
get_type_pointertype_array(const ir_type * tp)141 static ir_type **get_type_pointertype_array(const ir_type *tp)
142 {
143 if (!type_pointertype_map) type_pointertype_map = pmap_create();
144
145 ir_type **res = pmap_get(ir_type*, type_pointertype_map, tp);
146 if (!res) {
147 res = NEW_ARR_F(ir_type *, 0);
148 pmap_insert(type_pointertype_map, tp, (void *)res);
149 }
150
151 return res;
152 }
153
set_type_pointertype_array(const ir_type * tp,ir_type ** pts)154 static void set_type_pointertype_array(const ir_type *tp, ir_type **pts)
155 {
156 pmap_insert(type_pointertype_map, tp, (void *)pts);
157 }
158
159 /**
160 * Return a flexible array containing all array
161 * types that have a given type as element type.
162 */
get_type_arraytype_array(const ir_type * tp)163 static ir_type **get_type_arraytype_array(const ir_type *tp)
164 {
165 if (!type_arraytype_map) type_arraytype_map = pmap_create();
166
167 ir_type **res = pmap_get(ir_type*, type_arraytype_map, tp);
168 if (!res) {
169 res = NEW_ARR_F(ir_type *, 0);
170 pmap_insert(type_arraytype_map, tp, (void *)res);
171 }
172
173 return res;
174 }
175
set_type_arraytype_array(const ir_type * tp,ir_type ** pts)176 static void set_type_arraytype_array(const ir_type *tp, ir_type **pts)
177 {
178 pmap_insert(type_arraytype_map, tp, (void *)pts);
179 }
180
181 /*------------------------------------------------------------------*/
182 /* Accessing the out data structures. */
183 /* These routines only work properly if firm is in state */
184 /* trouts_consistent or trouts_inconsistent. */
185 /*------------------------------------------------------------------*/
186
187 /**------------------------------------------------------------------*/
188 /* Access routines for entities */
189 /**------------------------------------------------------------------*/
190
get_entity_n_accesses(const ir_entity * ent)191 size_t get_entity_n_accesses(const ir_entity *ent)
192 {
193 ir_node ** accs;
194
195 assert(ent && is_entity(ent));
196
197 accs = get_entity_access_array(ent);
198 return ARR_LEN(accs);
199 }
200
get_entity_access(const ir_entity * ent,size_t pos)201 ir_node *get_entity_access(const ir_entity *ent, size_t pos)
202 {
203 ir_node ** accs;
204
205 assert(pos < get_entity_n_accesses(ent));
206
207 accs = get_entity_access_array(ent);
208 return accs[pos];
209 }
210
add_entity_access(const ir_entity * ent,ir_node * n)211 static void add_entity_access(const ir_entity *ent, ir_node *n)
212 {
213 ir_node ** accs;
214
215 assert(ent && is_entity(ent));
216 assert(n && is_ir_node(n));
217
218 accs = get_entity_access_array(ent);
219 ARR_APP1(ir_node *, accs, n);
220 set_entity_access_array(ent, accs);
221 }
222
223 #if 0
224 void set_entity_access(const ir_entity *ent, int pos, ir_node *n)
225 {
226 ir_node ** accs;
227
228 assert(0 <= pos && pos < get_entity_n_accesses(ent));
229 assert(n && is_ir_node(n));
230
231 accs = get_entity_access_array(ent);
232 accs[pos] = n;
233 }
234 #endif
235
236 /*------------------------------------------------------------------*/
237
get_entity_n_references(const ir_entity * ent)238 size_t get_entity_n_references(const ir_entity *ent)
239 {
240 ir_node ** refs;
241
242 assert(ent && is_entity(ent));
243
244 refs = get_entity_reference_array(ent);
245 return ARR_LEN(refs);
246 }
247
get_entity_reference(const ir_entity * ent,size_t pos)248 ir_node *get_entity_reference(const ir_entity *ent, size_t pos)
249 {
250 ir_node ** refs;
251
252 assert( pos < get_entity_n_references(ent));
253
254 refs = get_entity_reference_array(ent);
255 return refs[pos];
256 }
257
add_entity_reference(const ir_entity * ent,ir_node * n)258 static void add_entity_reference(const ir_entity *ent, ir_node *n)
259 {
260 ir_node ** refs;
261
262 assert(ent && is_entity(ent));
263 assert(n && is_ir_node(n));
264
265 refs = get_entity_reference_array(ent);
266 ARR_APP1(ir_node *, refs, n);
267 set_entity_reference_array(ent, refs);
268 }
269
270 #if 0
271 void set_entity_reference(const ir_entity *ent, int pos, ir_node *n)
272 {
273 ir_node ** refs;
274
275 assert(0 <= pos && pos < get_entity_n_references(ent));
276 assert(n && is_ir_node(n));
277
278 refs = get_entity_reference_array(ent);
279 refs[pos] = n;
280 }
281 #endif
282
283 /**------------------------------------------------------------------*/
284 /* Access routines for types */
285 /**------------------------------------------------------------------*/
286
287 /* Number of Alloc nodes that create an instance of this type */
get_type_n_allocs(const ir_type * tp)288 size_t get_type_n_allocs(const ir_type *tp)
289 {
290 ir_node **allocs;
291
292 assert(tp && is_type(tp));
293
294 allocs = get_type_alloc_array(tp);
295 return ARR_LEN(allocs);
296 }
297
298 /* Alloc node that creates an instance of this type */
get_type_alloc(const ir_type * tp,size_t pos)299 ir_node *get_type_alloc(const ir_type *tp, size_t pos)
300 {
301 ir_node **allocs;
302 assert( pos < get_type_n_allocs(tp));
303
304 allocs = get_type_alloc_array(tp);
305 return allocs[pos];
306 }
307
add_type_alloc(const ir_type * tp,ir_node * n)308 static void add_type_alloc(const ir_type *tp, ir_node *n)
309 {
310 ir_node **allocs;
311
312 assert(tp && is_type(tp));
313 assert(n && is_ir_node(n));
314
315 allocs = get_type_alloc_array(tp);
316 ARR_APP1(ir_node *, allocs, n);
317 set_type_alloc_array(tp, allocs);
318 }
319
320 #if 0
321 void set_type_alloc(const ir_type *tp, int pos, ir_node *n)
322 {
323 ir_node **allocs;
324
325 assert(0 <= pos && pos < get_type_n_allocs(tp));
326 assert(n && is_ir_node(n));
327
328 allocs = get_type_alloc_array(tp);
329 allocs[pos] = n;
330 }
331 #endif
332
333 /* Number of Cast nodes that create an instance of this type */
get_type_n_casts(const ir_type * tp)334 size_t get_type_n_casts(const ir_type *tp)
335 {
336 ir_node **casts;
337
338 assert(tp && is_type(tp));
339
340 casts = get_type_cast_array(tp);
341 return ARR_LEN(casts);
342 }
343
344
get_class_n_upcasts(const ir_type * clss)345 size_t get_class_n_upcasts(const ir_type *clss)
346 {
347 size_t i, n_casts = get_type_n_casts(clss);
348 size_t n_instances = 0;
349 for (i = 0; i < n_casts; ++i) {
350 ir_node *cast = get_type_cast(clss, i);
351 if (is_Cast_upcast(cast))
352 ++n_instances;
353 }
354 return n_instances;
355 }
356
get_class_n_downcasts(const ir_type * clss)357 size_t get_class_n_downcasts(const ir_type *clss)
358 {
359 size_t i, n_casts = get_type_n_casts(clss);
360 size_t n_instances = 0;
361 for (i = 0; i < n_casts; ++i) {
362 ir_node *cast = get_type_cast(clss, i);
363 if (is_Cast_downcast(cast))
364 ++n_instances;
365 }
366 return n_instances;
367 }
368
get_type_cast(const ir_type * tp,size_t pos)369 ir_node *get_type_cast(const ir_type *tp, size_t pos)
370 {
371 ir_node **casts;
372 assert(pos < get_type_n_casts(tp));
373
374 casts = get_type_cast_array(tp);
375 return casts[pos];
376 }
377
add_type_cast(const ir_type * tp,ir_node * n)378 void add_type_cast(const ir_type *tp, ir_node *n)
379 {
380 ir_node **casts;
381
382 assert(tp && is_type(tp));
383 assert(n && is_ir_node(n));
384
385 casts = get_type_cast_array(tp);
386 ARR_APP1(ir_node *, casts, n);
387 set_type_cast_array(tp, casts);
388 }
389
390 #if 0
391 void set_type_cast(const ir_type *tp, size_t pos, ir_node *n)
392 {
393 ir_node **casts;
394
395 assert(pos < get_type_n_casts(tp));
396 assert(n && is_ir_node(n));
397
398 casts = get_type_cast_array(tp);
399 casts[pos] = n;
400 }
401 #endif
402
403 /*------------------------------------------------------------------*/
404
get_type_n_pointertypes_to(const ir_type * tp)405 size_t get_type_n_pointertypes_to(const ir_type *tp)
406 {
407 ir_type ** pts;
408
409 assert(tp && is_type(tp));
410
411 pts = get_type_pointertype_array(tp);
412 return ARR_LEN(pts);
413 }
414
get_type_pointertype_to(const ir_type * tp,size_t pos)415 ir_type *get_type_pointertype_to(const ir_type *tp, size_t pos)
416 {
417 ir_type ** pts;
418
419 assert(pos < get_type_n_pointertypes_to(tp));
420
421 pts = get_type_pointertype_array(tp);
422 return pts[pos];
423 }
424
add_type_pointertype_to(const ir_type * tp,ir_type * ptp)425 void add_type_pointertype_to(const ir_type *tp, ir_type *ptp)
426 {
427 ir_type ** pts;
428
429 assert(tp && is_type(tp));
430 assert(ptp && is_Pointer_type(ptp));
431
432 pts = get_type_pointertype_array(tp);
433 ARR_APP1(ir_type*, pts, ptp);
434 set_type_pointertype_array(tp, pts);
435 }
436
437 #if 0
438 void set_type_pointertype_to(const ir_type *tp, int pos, ir_type *ptp)
439 {
440 ir_type ** pts;
441
442 assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
443 assert(ptp && is_Pointer_type(ptp));
444
445 pts = get_type_pointertype_array(tp);
446 pts[pos] = ptp;
447 }
448 #endif
449
450 /*------------------------------------------------------------------*/
451
get_type_n_arraytypes_of(const ir_type * tp)452 size_t get_type_n_arraytypes_of(const ir_type *tp)
453 {
454 ir_type ** pts;
455
456 assert(tp && is_type(tp));
457
458 pts = get_type_arraytype_array(tp);
459 return ARR_LEN(pts);
460 }
461
get_type_arraytype_of(const ir_type * tp,size_t pos)462 ir_type *get_type_arraytype_of(const ir_type *tp, size_t pos)
463 {
464 ir_type ** pts;
465
466 assert(pos < get_type_n_arraytypes_of(tp));
467
468 pts = get_type_arraytype_array(tp);
469 return pts[pos];
470 }
471
add_type_arraytype_of(const ir_type * tp,ir_type * atp)472 void add_type_arraytype_of(const ir_type *tp, ir_type *atp)
473 {
474 ir_type ** pts;
475
476 assert(tp && is_type(tp));
477 assert(atp && is_Array_type(atp));
478
479 pts = get_type_arraytype_array(tp);
480 ARR_APP1(ir_type*, pts, atp);
481 set_type_arraytype_array(tp, pts);
482 }
483
484 #if 0
485 void set_type_arraytype_of(const ir_type *tp, int pos, ir_type *atp)
486 {
487 ir_type ** pts;
488
489 assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
490 assert(atp && is_Array_type(atp));
491
492 pts = get_type_arraytype_array(tp);
493 pts[pos] = atp;
494 }
495 #endif
496
497 /*------------------------------------------------------------------*/
498 /* Building and Removing the out datastructure */
499 /*------------------------------------------------------------------*/
500
501 /** Initialize the trouts handling. */
init_trouts(void)502 static void init_trouts(void)
503 {
504 }
505
506 /** The number of entities that can be accessed by this Sel node. */
get_Sel_n_accessed_entities(const ir_node * sel)507 static int get_Sel_n_accessed_entities(const ir_node *sel)
508 {
509 (void) sel;
510 return 1;
511 }
512
513 /** The entity that cat be accessed by this Sel node. */
get_Sel_accessed_entity(const ir_node * sel)514 static ir_entity *get_Sel_accessed_entity(const ir_node *sel)
515 {
516 return get_Sel_entity(sel);
517 }
518
519 /** An addr node is a SymConst or a Sel. */
get_addr_n_entities(const ir_node * addr)520 static int get_addr_n_entities(const ir_node *addr)
521 {
522 switch (get_irn_opcode(addr)) {
523 case iro_Sel:
524 /* Treat jack array sels? */
525 return get_Sel_n_accessed_entities(addr);
526 case iro_SymConst:
527 if (get_SymConst_kind(addr) == symconst_addr_ent)
528 return 1;
529 return 0;
530 default:
531 return 0;
532 }
533 }
534
535 /** An addr node is a SymConst or a Sel.
536 If Sel follow to outermost of compound. */
get_addr_entity(const ir_node * addr,int pos)537 static ir_entity *get_addr_entity(const ir_node *addr, int pos)
538 {
539 ir_node *ptr;
540 (void) pos;
541
542 switch (get_irn_opcode(addr)) {
543 case iro_Sel:
544 /* Treat jack array sels? They are compounds! Follow to outermost entity. */
545 ptr = get_Sel_ptr(addr);
546 while (is_Sel(ptr)) {
547 addr = ptr;
548 ptr = get_Sel_ptr(addr);
549 }
550 assert(0 <= pos && pos < get_Sel_n_accessed_entities(addr));
551 return get_Sel_accessed_entity(addr);
552 case iro_SymConst:
553 if (get_SymConst_kind(addr) == symconst_addr_ent) {
554 assert(pos == 0);
555 return get_SymConst_entity(addr);
556 }
557 return NULL;
558 default:
559 return NULL;
560 }
561 }
562
chain_accesses(ir_node * n,void * env)563 static void chain_accesses(ir_node *n, void *env)
564 {
565 int i, n_ents;
566 ir_node *addr;
567
568 (void) env;
569 if (is_Alloc(n)) {
570 add_type_alloc(get_Alloc_type(n), n);
571 return;
572 } else if (is_Cast(n)) {
573 add_type_cast(get_Cast_type(n), n);
574 return;
575 } else if (is_Sel(n)) {
576 add_entity_reference(get_Sel_entity(n), n);
577 return;
578 } else if (is_SymConst_addr_ent(n)) {
579 add_entity_reference(get_SymConst_entity(n), n);
580 return;
581 } else if (is_Store(n)) {
582 addr = get_Store_ptr(n);
583 } else if (is_Load(n)) {
584 addr = get_Load_ptr(n);
585 } else if (is_Call(n)) {
586 addr = get_Call_ptr(n);
587 if (! is_Sel(addr)) return; /* Sels before Calls mean a Load / polymorphic Call. */
588 } else {
589 return;
590 }
591
592 n_ents = get_addr_n_entities(addr); /* == 1 */
593 for (i = 0; i < n_ents; ++i) {
594 ir_entity *ent = get_addr_entity(addr, i);
595 if (ent)
596 add_entity_access(ent, n);
597 //else
598 //add_unrecognized_access(n);
599 }
600 }
601
602 /**
603 * Handle chain types (pointer, array) by adding them to
604 * its "inner" type.
605 */
chain_types(ir_type * tp)606 static void chain_types(ir_type *tp)
607 {
608 if (is_Pointer_type(tp)) {
609 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
610 } else if (is_Array_type(tp)) {
611 add_type_arraytype_of(get_array_element_type(tp), tp);
612 }
613 }
614
compute_trouts(void)615 void compute_trouts(void)
616 {
617 size_t i;
618
619 free_trouts();
620 init_trouts();
621
622 /* Compute outs for IR nodes. */
623 for (i = get_irp_n_irgs(); i > 0;) {
624 ir_graph *irg = get_irp_irg(--i);
625 irg_walk_graph(irg, NULL, chain_accesses, NULL);
626 }
627 walk_const_code(NULL, chain_accesses, NULL);
628
629 /* Compute outs for types */
630 for (i = get_irp_n_types(); i > 0;) {
631 ir_type *type = get_irp_type(--i);
632 chain_types(type);
633 }
634 }
635
free_trouts(void)636 void free_trouts(void)
637 {
638 if (entity_access_map) {
639 ir_node **accs;
640 for (accs = (ir_node **)pmap_first(entity_access_map);
641 accs;
642 accs = (ir_node **)pmap_next(entity_access_map)) {
643 /* DEL_ARR_F(accs); */
644 }
645 pmap_destroy(entity_access_map);
646 entity_access_map = NULL;
647 }
648
649 if (entity_reference_map) {
650 ir_node **refs;
651 for (refs = (ir_node **)pmap_first(entity_reference_map);
652 refs;
653 refs = (ir_node **)pmap_next(entity_reference_map)) {
654 /* DEL_ARR_F(refs); */
655 }
656 pmap_destroy(entity_reference_map);
657 entity_reference_map = NULL;
658 }
659
660 if (type_alloc_map) {
661 ir_node **alls;
662 for (alls = (ir_node **)pmap_first(type_alloc_map);
663 alls;
664 alls = (ir_node **)pmap_next(type_alloc_map)) {
665 /* DEL_ARR_F(alls); */
666 }
667 pmap_destroy(type_alloc_map);
668 type_alloc_map = NULL;
669 }
670
671 if (type_cast_map) {
672 ir_node **casts;
673 for (casts = (ir_node **)pmap_first(type_cast_map);
674 casts;
675 casts = (ir_node **)pmap_next(type_cast_map)) {
676 /* DEL_ARR_F(alls); */
677 }
678 pmap_destroy(type_cast_map);
679 type_cast_map = NULL;
680 }
681
682 if (type_pointertype_map) {
683 ir_node **pts;
684 for (pts = (ir_node **)pmap_first(type_pointertype_map);
685 pts;
686 pts = (ir_node **)pmap_next(type_pointertype_map)) {
687 /* DEL_ARR_F(pts); */
688 }
689 pmap_destroy(type_pointertype_map);
690 type_pointertype_map = NULL;
691 }
692
693 if (type_arraytype_map) {
694 ir_node **pts;
695 for (pts = (ir_node **)pmap_first(type_arraytype_map);
696 pts;
697 pts = (ir_node **)pmap_next(type_arraytype_map)) {
698 /* DEL_ARR_F(pts); */
699 }
700 pmap_destroy(type_arraytype_map);
701 type_arraytype_map = NULL;
702 }
703 }
704