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