OSDN Git Service

1619c5e47c0c85f8316ffb80903d141adb1cd1c0
[pf3gnuchains/gcc-fork.git] / gcc / ipa-type-escape.c
1 /* Type based alias analysis.
2    Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
3    Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
21
22 /* This pass determines which types in the program contain only
23    instances that are completely encapsulated by the compilation unit.
24    Those types that are encapsulated must also pass the further
25    requirement that there be no bad operations on any instances of
26    those types.
27
28    A great deal of freedom in compilation is allowed for the instances
29    of those types that pass these conditions.
30 */
31
32 /* The code in this module is called by the ipa pass manager. It
33    should be one of the later passes since its information is used by
34    the rest of the compilation. */
35
36 #include "config.h"
37 #include "system.h"
38 #include "coretypes.h"
39 #include "tm.h"
40 #include "tree.h"
41 #include "tree-flow.h"
42 #include "tree-inline.h"
43 #include "tree-pass.h"
44 #include "langhooks.h"
45 #include "pointer-set.h"
46 #include "ggc.h"
47 #include "ipa-utils.h"
48 #include "ipa-type-escape.h"
49 #include "c-common.h"
50 #include "tree-gimple.h"
51 #include "cgraph.h"
52 #include "output.h"
53 #include "flags.h"
54 #include "timevar.h"
55 #include "diagnostic.h"
56 #include "langhooks.h"
57
58 /* Some of the aliasing is called very early, before this phase is
59    called.  To assure that this is not a problem, we keep track of if
60    this phase has been run.  */
61 static bool initialized = false;
62
63 /* Scratch bitmap for avoiding work. */
64 static bitmap been_there_done_that;
65 static bitmap bitmap_tmp;
66
67 /* There are two levels of escape that types can undergo.
68
69    EXPOSED_PARAMETER - some instance of the variable is
70    passed by value into an externally visible function or some
71    instance of the variable is passed out of an externally visible
72    function as a return value.  In this case any of the fields of the
73    variable that are pointer types end up having their types marked as
74    FULL_ESCAPE.
75
76    FULL_ESCAPE - when bad things happen to good types. One of the
77    following things happens to the type: (a) either an instance of the
78    variable has its address passed to an externally visible function,
79    (b) the address is taken and some bad cast happens to the address
80    or (c) explicit arithmetic is done to the address.
81 */
82
83 enum escape_t
84 {
85   EXPOSED_PARAMETER,
86   FULL_ESCAPE
87 };
88
89 /* The following two bit vectors global_types_* correspond to
90    previous cases above.  During the analysis phase, a bit is set in
91    one of these vectors if an operation of the offending class is
92    discovered to happen on the associated type.  */
93  
94 static bitmap global_types_exposed_parameter;
95 static bitmap global_types_full_escape;
96
97 /* All of the types seen in this compilation unit. */
98 static bitmap global_types_seen;
99 /* Reverse map to take a canon uid and map it to a canon type.  Uid's
100    are never manipulated unless they are associated with a canon
101    type.  */
102 static splay_tree uid_to_canon_type;
103
104 /* Internal structure of type mapping code.  This maps a canon type
105    name to its canon type.  */
106 static splay_tree all_canon_types;
107
108 /* Map from type clones to the single canon type.  */
109 static splay_tree type_to_canon_type;
110
111 /* A splay tree of bitmaps.  An element X in the splay tree has a bit
112    set in its bitmap at TYPE_UID (TYPE_MAIN_VARIANT (Y)) if there was
113    an operation in the program of the form "&X.Y".  */
114 static splay_tree uid_to_addressof_down_map;
115
116 /* A splay tree of bitmaps.  An element Y in the splay tree has a bit
117    set in its bitmap at TYPE_UID (TYPE_MAIN_VARIANT (X)) if there was
118    an operation in the program of the form "&X.Y".  */
119 static splay_tree uid_to_addressof_up_map;
120
121 /* Tree to hold the subtype maps used to mark subtypes of escaped
122    types.  */
123 static splay_tree uid_to_subtype_map;
124
125 /* Records tree nodes seen in cgraph_create_edges.  Simply using
126    walk_tree_without_duplicates doesn't guarantee each node is visited
127    once because it gets a new htab upon each recursive call from
128    scan_for_refs.  */
129 static struct pointer_set_t *visited_nodes;
130
131 /* Visited stmts by walk_use_def_chains function because it's called
132    recursively.  */
133 static struct pointer_set_t *visited_stmts;
134
135 static bitmap_obstack ipa_obstack;
136
137 /* Static functions from this file that are used 
138    before being defined.  */
139 static unsigned int look_for_casts (tree lhs ATTRIBUTE_UNUSED, tree);
140 static bool is_cast_from_non_pointer (tree, tree, void *);
141
142 /* Get the name of TYPE or return the string "<UNNAMED>".  */
143 static char*
144 get_name_of_type (tree type)
145 {
146   tree name = TYPE_NAME (type);
147   
148   if (!name)
149     /* Unnamed type, do what you like here.  */
150     return (char*)"<UNNAMED>";
151   
152   /* It will be a TYPE_DECL in the case of a typedef, otherwise, an
153      identifier_node */
154   if (TREE_CODE (name) == TYPE_DECL)
155     {
156       /*  Each DECL has a DECL_NAME field which contains an
157           IDENTIFIER_NODE.  (Some decls, most often labels, may have
158           zero as the DECL_NAME).  */
159       if (DECL_NAME (name))
160         return (char*)IDENTIFIER_POINTER (DECL_NAME (name));
161       else
162         /* Unnamed type, do what you like here.  */
163         return (char*)"<UNNAMED>";
164     }
165   else if (TREE_CODE (name) == IDENTIFIER_NODE)
166     return (char*)IDENTIFIER_POINTER (name);
167   else 
168     return (char*)"<UNNAMED>";
169 }
170
171 struct type_brand_s 
172 {
173   char* name;
174   int seq;
175 };
176
177 /* Splay tree comparison function on type_brand_s structures.  */
178
179 static int 
180 compare_type_brand (splay_tree_key sk1, splay_tree_key sk2)
181 {
182   struct type_brand_s * k1 = (struct type_brand_s *) sk1;
183   struct type_brand_s * k2 = (struct type_brand_s *) sk2;
184
185   int value = strcmp(k1->name, k2->name);
186   if (value == 0)
187     return k2->seq - k1->seq;
188   else 
189     return value;
190 }
191
192 /* All of the "unique_type" code is a hack to get around the sleazy
193    implementation used to compile more than file.  Currently gcc does
194    not get rid of multiple instances of the same type that have been
195    collected from different compilation units.  */
196 /* This is a trivial algorithm for removing duplicate types.  This
197    would not work for any language that used structural equivalence as
198    the basis of its type system.  */
199 /* Return TYPE if no type compatible with TYPE has been seen so far,
200    otherwise return a type compatible with TYPE that has already been
201    processed.  */
202
203 static tree
204 discover_unique_type (tree type)
205 {
206   struct type_brand_s * brand = XNEW (struct type_brand_s);
207   int i = 0;
208   splay_tree_node result;
209
210   brand->name = get_name_of_type (type);
211
212   while (1)
213     {
214       brand->seq = i++;
215       result = splay_tree_lookup (all_canon_types, (splay_tree_key) brand);
216
217       if (result)
218         {
219           /* Create an alias since this is just the same as
220              other_type.  */
221           tree other_type = (tree) result->value;
222           if (lang_hooks.types_compatible_p (type, other_type) == 1)
223             {
224               free (brand);
225               /* Insert this new type as an alias for other_type.  */
226               splay_tree_insert (type_to_canon_type,
227                                  (splay_tree_key) type,
228                                  (splay_tree_value) other_type);
229               return other_type;
230             }
231           /* Not compatible, look for next instance with same name.  */
232         }
233       else
234         {
235           /* No more instances, create new one since this is the first
236              time we saw this type.  */
237           brand->seq = i++;
238           /* Insert the new brand.  */
239           splay_tree_insert (all_canon_types,
240                              (splay_tree_key) brand,
241                              (splay_tree_value) type);
242
243           /* Insert this new type as an alias for itself.  */
244           splay_tree_insert (type_to_canon_type,
245                              (splay_tree_key) type,
246                              (splay_tree_value) type);
247
248           /* Insert the uid for reverse lookup; */
249           splay_tree_insert (uid_to_canon_type,
250                              (splay_tree_key) TYPE_UID (type),
251                              (splay_tree_value) type);
252
253           bitmap_set_bit (global_types_seen, TYPE_UID (type));
254           return type;
255         }
256     }
257 }
258
259 /* Return true if TYPE is one of the type classes that we are willing
260    to analyze.  This skips the goofy types like arrays of pointers to
261    methods. */
262 static bool
263 type_to_consider (tree type)
264 {
265   /* Strip the *'s off.  */
266   type = TYPE_MAIN_VARIANT (type);
267   while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE)
268     type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
269
270   switch (TREE_CODE (type))
271     {
272     case BOOLEAN_TYPE:
273     case COMPLEX_TYPE:
274     case ENUMERAL_TYPE:
275     case INTEGER_TYPE:
276     case QUAL_UNION_TYPE:
277     case REAL_TYPE:
278     case RECORD_TYPE:
279     case UNION_TYPE:
280     case VECTOR_TYPE:
281     case VOID_TYPE:
282       return true;
283   
284     default:
285       return false;
286     }
287 }
288
289 /* Get the canon type of TYPE.  If SEE_THRU_PTRS is true, remove all
290    the POINTER_TOs and if SEE_THRU_ARRAYS is true, remove all of the
291    ARRAY_OFs and POINTER_TOs.  */
292
293 static tree 
294 get_canon_type (tree type, bool see_thru_ptrs, bool see_thru_arrays)
295 {
296   splay_tree_node result;
297   /* Strip the *'s off.  */
298   if (!type || !type_to_consider (type))
299     return NULL;
300
301   type = TYPE_MAIN_VARIANT (type);
302   if (see_thru_arrays) 
303     while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE)
304       type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
305
306   else if (see_thru_ptrs) 
307     while (POINTER_TYPE_P (type))
308         type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
309
310   result = splay_tree_lookup(type_to_canon_type, (splay_tree_key) type);
311   
312   if (result == NULL)
313     return discover_unique_type (type);
314   else return (tree) result->value;
315 }
316
317 /* Same as GET_CANON_TYPE, except return the TYPE_ID rather than the
318    TYPE.  */
319
320 static int
321 get_canon_type_uid (tree type, bool see_thru_ptrs, bool see_thru_arrays)
322 {
323   type = get_canon_type (type, see_thru_ptrs, see_thru_arrays);
324   if (type)
325     return TYPE_UID(type);
326   else return 0;
327 }
328
329 /* Return 0 if TYPE is a record or union type.  Return a positive
330    number if TYPE is a pointer to a record or union.  The number is
331    the number of pointer types stripped to get to the record or union
332    type.  Return -1 if TYPE is none of the above.  */
333  
334 int
335 ipa_type_escape_star_count_of_interesting_type (tree type) 
336 {
337   int count = 0;
338   /* Strip the *'s off.  */
339   if (!type)
340     return -1;
341   type = TYPE_MAIN_VARIANT (type);
342   while (POINTER_TYPE_P (type))
343     {
344       type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
345       count++;
346     }
347
348   /* We are interested in records, and unions only.  */
349   if (TREE_CODE (type) == RECORD_TYPE 
350       || TREE_CODE (type) == QUAL_UNION_TYPE 
351       || TREE_CODE (type) == UNION_TYPE)
352     return count;
353   else 
354     return -1;
355
356
357
358 /* Return 0 if TYPE is a record or union type.  Return a positive
359    number if TYPE is a pointer to a record or union.  The number is
360    the number of pointer types stripped to get to the record or union
361    type.  Return -1 if TYPE is none of the above.  */
362  
363 int
364 ipa_type_escape_star_count_of_interesting_or_array_type (tree type) 
365 {
366   int count = 0;
367   /* Strip the *'s off.  */
368   if (!type)
369     return -1;
370   type = TYPE_MAIN_VARIANT (type);
371   while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE)
372     {
373       type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
374       count++;
375     }
376
377   /* We are interested in records, and unions only.  */
378   if (TREE_CODE (type) == RECORD_TYPE 
379       || TREE_CODE (type) == QUAL_UNION_TYPE 
380       || TREE_CODE (type) == UNION_TYPE)
381     return count;
382   else 
383     return -1;
384
385  
386  
387 /* Return true if the record, or union TYPE passed in escapes this
388    compilation unit. Note that all of the pointer-to's are removed
389    before testing since these may not be correct.  */
390
391 bool
392 ipa_type_escape_type_contained_p (tree type)
393 {
394   if (!initialized)
395     return false;
396   return !bitmap_bit_p (global_types_full_escape, 
397                         get_canon_type_uid (type, true, false));
398 }
399
400 /* Return true if a modification to a field of type FIELD_TYPE cannot
401    clobber a record of RECORD_TYPE.  */
402
403 bool 
404 ipa_type_escape_field_does_not_clobber_p (tree record_type, tree field_type)
405
406   splay_tree_node result;
407   int uid;
408   
409   if (!initialized)
410     return false;
411
412   /* Strip off all of the pointer tos on the record type.  Strip the
413      same number of pointer tos from the field type.  If the field
414      type has fewer, it could not have been aliased. */
415   record_type = TYPE_MAIN_VARIANT (record_type);
416   field_type = TYPE_MAIN_VARIANT (field_type);
417   while (POINTER_TYPE_P (record_type))
418     {
419       record_type = TYPE_MAIN_VARIANT (TREE_TYPE (record_type));
420       if (POINTER_TYPE_P (field_type)) 
421         field_type = TYPE_MAIN_VARIANT (TREE_TYPE (field_type));
422       else 
423         /* However, if field_type is a union, this quick test is not
424            correct since one of the variants of the union may be a
425            pointer to type and we cannot see across that here.  So we
426            just strip the remaining pointer tos off the record type
427            and fall thru to the more precise code.  */
428         if (TREE_CODE (field_type) == QUAL_UNION_TYPE 
429             || TREE_CODE (field_type) == UNION_TYPE)
430           {
431             while (POINTER_TYPE_P (record_type))
432               record_type = TYPE_MAIN_VARIANT (TREE_TYPE (record_type));
433             break;
434           } 
435         else 
436           return true;
437     }
438   
439   record_type = get_canon_type (record_type, true, true);
440   /* The record type must be contained.  The field type may
441      escape.  */
442   if (!ipa_type_escape_type_contained_p (record_type))
443     return false;
444
445   uid = TYPE_UID (record_type);
446   result = splay_tree_lookup (uid_to_addressof_down_map, (splay_tree_key) uid);
447   
448   if (result) 
449     {
450       bitmap field_type_map = (bitmap) result->value;
451       uid = get_canon_type_uid (field_type, true, true);
452       /* If the bit is there, the address was taken. If not, it
453          wasn't.  */
454       return !bitmap_bit_p (field_type_map, uid);
455     }
456   else
457     /* No bitmap means no addresses were taken.  */
458     return true;
459 }
460
461
462 /* Add TYPE to the suspect type set. Return true if the bit needed to
463    be marked.  */
464
465 static tree
466 mark_type (tree type, enum escape_t escape_status)
467 {
468   bitmap map = NULL;
469   int uid;
470
471   type = get_canon_type (type, true, true);
472   if (!type) 
473     return NULL;
474
475   switch (escape_status) 
476     {
477     case EXPOSED_PARAMETER:
478       map = global_types_exposed_parameter;
479       break;
480     case FULL_ESCAPE:
481       map = global_types_full_escape;
482       break;
483     }
484
485   uid = TYPE_UID (type);
486   if (bitmap_bit_p (map, uid))
487     return type;
488   else
489     {
490       bitmap_set_bit (map, uid);
491       if (escape_status == FULL_ESCAPE)
492         {
493           /* Efficiency hack. When things are bad, do not mess around
494              with this type anymore.  */
495           bitmap_set_bit (global_types_exposed_parameter, uid);
496         }      
497     }
498   return type;
499 }
500
501 /* Add interesting TYPE to the suspect type set. If the set is
502    EXPOSED_PARAMETER and the TYPE is a pointer type, the set is
503    changed to FULL_ESCAPE.  */
504
505 static void 
506 mark_interesting_type (tree type, enum escape_t escape_status)
507 {
508   if (!type) return;
509   if (ipa_type_escape_star_count_of_interesting_type (type) >= 0)
510     {
511       if ((escape_status == EXPOSED_PARAMETER)
512           && POINTER_TYPE_P (type))
513         /* EXPOSED_PARAMETERs are only structs or unions are passed by
514            value.  Anything passed by reference to an external
515            function fully exposes the type.  */
516         mark_type (type, FULL_ESCAPE);
517       else
518         mark_type (type, escape_status);
519     }
520 }
521
522 /* Return true if PARENT is supertype of CHILD.  Both types must be
523    known to be structures or unions. */
524  
525 static bool
526 parent_type_p (tree parent, tree child)
527 {
528   int i;
529   tree binfo, base_binfo;
530   if (TYPE_BINFO (parent)) 
531     for (binfo = TYPE_BINFO (parent), i = 0;
532          BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
533       {
534         tree binfotype = BINFO_TYPE (base_binfo);
535         if (binfotype == child) 
536           return true;
537         else if (parent_type_p (binfotype, child))
538           return true;
539       }
540   if (TREE_CODE (parent) == UNION_TYPE
541       || TREE_CODE (parent) == QUAL_UNION_TYPE) 
542     {
543       tree field;
544       /* Search all of the variants in the union to see if one of them
545          is the child.  */
546       for (field = TYPE_FIELDS (parent);
547            field;
548            field = TREE_CHAIN (field))
549         {
550           tree field_type;
551           if (TREE_CODE (field) != FIELD_DECL)
552             continue;
553           
554           field_type = TREE_TYPE (field);
555           if (field_type == child) 
556             return true;
557         }
558
559       /* If we did not find it, recursively ask the variants if one of
560          their children is the child type.  */
561       for (field = TYPE_FIELDS (parent);
562            field;
563            field = TREE_CHAIN (field))
564         {
565           tree field_type;
566           if (TREE_CODE (field) != FIELD_DECL)
567             continue;
568           
569           field_type = TREE_TYPE (field);
570           if (TREE_CODE (field_type) == RECORD_TYPE 
571               || TREE_CODE (field_type) == QUAL_UNION_TYPE 
572               || TREE_CODE (field_type) == UNION_TYPE)
573             if (parent_type_p (field_type, child)) 
574               return true;
575         }
576     }
577   
578   if (TREE_CODE (parent) == RECORD_TYPE)
579     {
580       tree field;
581       for (field = TYPE_FIELDS (parent);
582            field;
583            field = TREE_CHAIN (field))
584         {
585           tree field_type;
586           if (TREE_CODE (field) != FIELD_DECL)
587             continue;
588           
589           field_type = TREE_TYPE (field);
590           if (field_type == child) 
591             return true;
592           /* You can only cast to the first field so if it does not
593              match, quit.  */
594           if (TREE_CODE (field_type) == RECORD_TYPE 
595               || TREE_CODE (field_type) == QUAL_UNION_TYPE 
596               || TREE_CODE (field_type) == UNION_TYPE)
597             {
598               if (parent_type_p (field_type, child)) 
599                 return true;
600               else 
601                 break;
602             }
603         }
604     }
605   return false;
606 }
607
608 /* Return the number of pointer tos for TYPE and return TYPE with all
609    of these stripped off.  */
610
611 static int 
612 count_stars (tree* type_ptr)
613 {
614   tree type = *type_ptr;
615   int i = 0;
616   type = TYPE_MAIN_VARIANT (type);
617   while (POINTER_TYPE_P (type))
618     {
619       type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
620       i++;
621     }
622
623   *type_ptr = type;
624   return i;
625 }
626
627 enum cast_type {
628   CT_UP = 0x1,
629   CT_DOWN = 0x2,
630   CT_SIDEWAYS = 0x4,
631   CT_USELESS = 0x8,
632   CT_FROM_P_BAD = 0x10,
633   CT_FROM_NON_P = 0x20,
634   CT_TO_NON_INTER = 0x40,
635   CT_FROM_MALLOC = 0x80,
636   CT_NO_CAST = 0x100
637 };
638
639 /* Check the cast FROM_TYPE to TO_TYPE.  This function requires that
640    the two types have already passed the
641    ipa_type_escape_star_count_of_interesting_type test.  */
642
643 static enum cast_type
644 check_cast_type (tree to_type, tree from_type)
645 {
646   int to_stars = count_stars (&to_type);
647   int from_stars = count_stars (&from_type);
648   if (to_stars != from_stars) 
649     return CT_SIDEWAYS;
650
651   if (to_type == from_type)
652     return CT_USELESS;
653
654   if (parent_type_p (to_type, from_type)) return CT_UP;
655   if (parent_type_p (from_type, to_type)) return CT_DOWN;
656   return CT_SIDEWAYS;
657 }     
658
659 /* This function returns non-zero if VAR is result of call 
660    to malloc function.  */
661
662 static bool
663 is_malloc_result (tree var)
664 {
665   tree def_stmt;
666   tree rhs;
667   int flags;
668
669   if (!var)
670     return false;
671   
672   if (SSA_NAME_IS_DEFAULT_DEF (var))
673     return false;
674
675   def_stmt = SSA_NAME_DEF_STMT (var);
676   
677   if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT)
678     return false;
679
680   if (var != GIMPLE_STMT_OPERAND (def_stmt, 0))
681     return false;
682
683   rhs = get_call_expr_in (def_stmt);
684
685   if (!rhs)
686     return false;
687
688   flags = call_expr_flags (rhs);
689     
690   return ((flags & ECF_MALLOC) != 0);
691
692 }
693
694 /* Check a cast FROM this variable, TO_TYPE.  Mark the escaping types
695    if appropriate. Returns cast_type as detected.  */
696  
697 static enum cast_type
698 check_cast (tree to_type, tree from) 
699 {
700   tree from_type = get_canon_type (TREE_TYPE (from), false, false);
701   bool to_interesting_type, from_interesting_type;
702   enum cast_type cast = CT_NO_CAST;
703
704   to_type = get_canon_type (to_type, false, false);
705   if (!from_type || !to_type || from_type == to_type)
706     return cast;
707
708   to_interesting_type = 
709     ipa_type_escape_star_count_of_interesting_type (to_type) >= 0;
710   from_interesting_type = 
711     ipa_type_escape_star_count_of_interesting_type (from_type) >= 0;
712
713   if (to_interesting_type) 
714     if (from_interesting_type)
715       {
716         /* Both types are interesting. This can be one of four types
717            of cast: useless, up, down, or sideways.  We do not care
718            about up or useless.  Sideways casts are always bad and
719            both sides get marked as escaping.  Downcasts are not
720            interesting here because if type is marked as escaping, all
721            of its subtypes escape.  */
722         cast = check_cast_type (to_type, from_type);
723         switch (cast) 
724           {
725           case CT_UP:
726           case CT_USELESS:
727           case CT_DOWN:
728             break;
729
730           case CT_SIDEWAYS:
731             mark_type (to_type, FULL_ESCAPE);
732             mark_type (from_type, FULL_ESCAPE);
733             break;
734
735           default:
736             break;
737           }
738       }
739     else
740       {
741         /* This code excludes two cases from marking as escaped:
742            
743         1. if this is a cast of index of array of structures/unions
744         that happens before accessing array element, we should not 
745         mark it as escaped.
746         2. if this is a cast from the local that is a result from a
747         call to malloc, do not mark the cast as bad.  
748
749         */
750         
751         if (POINTER_TYPE_P (to_type) && !POINTER_TYPE_P (from_type))
752           cast = CT_FROM_NON_P;
753         else if (TREE_CODE (from) == SSA_NAME 
754                  && is_malloc_result (from))
755           cast = CT_FROM_MALLOC;
756         else
757           {
758             cast = CT_FROM_P_BAD;
759             mark_type (to_type, FULL_ESCAPE);
760           }
761       }
762   else if (from_interesting_type)
763     {
764       mark_type (from_type, FULL_ESCAPE);
765       cast = CT_TO_NON_INTER;
766     }
767
768   return cast;
769 }
770
771 typedef struct cast 
772 {
773   int type;
774   tree stmt;
775 }cast_t;
776
777 /* This function is a callback for walk_tree called from 
778    is_cast_from_non_pointer. The data->type is set to be:
779
780    0      - if there is no cast
781    number - the number of casts from non-pointer type
782    -1     - if there is a cast that makes the type to escape
783
784    If data->type = number, then data->stmt will contain the 
785    last casting stmt met in traversing.  */
786
787 static tree
788 is_cast_from_non_pointer_1 (tree *tp, int *walk_subtrees, void *data)
789 {
790   tree def_stmt = *tp;
791
792
793   if (pointer_set_insert (visited_stmts, def_stmt))
794     {
795       *walk_subtrees = 0;
796       return NULL;
797     }
798   
799   switch (TREE_CODE (def_stmt))
800     {
801     case GIMPLE_MODIFY_STMT:
802       {
803         use_operand_p use_p; 
804         ssa_op_iter iter;
805         tree lhs = GIMPLE_STMT_OPERAND (def_stmt, 0);
806         tree rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
807
808         unsigned int cast = look_for_casts (lhs, rhs);
809         /* Check that only one cast happened, and it's of 
810            non-pointer type.  */
811         if ((cast & CT_FROM_NON_P) == (CT_FROM_NON_P) 
812             && (cast & ~(CT_FROM_NON_P)) == 0)
813           {
814             ((cast_t *)data)->stmt = def_stmt;
815             ((cast_t *)data)->type++;
816
817             FOR_EACH_SSA_USE_OPERAND (use_p, def_stmt, iter, SSA_OP_ALL_USES)
818               {
819                 walk_use_def_chains (USE_FROM_PTR (use_p), is_cast_from_non_pointer, 
820                                      data, false);
821                 if (((cast_t*)data)->type == -1)
822                   return def_stmt;
823               }
824           }
825
826         /* Check that there is no cast, or cast is not harmful. */
827         else if ((cast & CT_NO_CAST) == (CT_NO_CAST)
828                  || (cast & CT_DOWN) == (CT_DOWN)
829                  || (cast & CT_UP) == (CT_UP)
830                  || (cast & CT_USELESS) == (CT_USELESS)
831                  || (cast & CT_FROM_MALLOC) == (CT_FROM_MALLOC))
832           {
833             FOR_EACH_SSA_USE_OPERAND (use_p, def_stmt, iter, SSA_OP_ALL_USES)
834               {
835                 walk_use_def_chains (USE_FROM_PTR (use_p), is_cast_from_non_pointer, 
836                                      data, false);
837                 if (((cast_t*)data)->type == -1)
838                   return def_stmt;
839               }     
840           }
841
842         /* The cast is harmful.  */
843         else
844           {
845             ((cast_t *)data)->type = -1;
846             return def_stmt;
847           }
848
849         *walk_subtrees = 0;
850       }     
851       break;
852
853     default:
854       {
855         *walk_subtrees = 0;
856         break;
857       }
858     }
859
860   return NULL;
861 }
862
863 /* This function is a callback for walk_use_def_chains function called 
864    from is_array_access_through_pointer_and_index.  */
865
866 static bool
867 is_cast_from_non_pointer (tree var, tree def_stmt, void *data)
868 {
869
870   if (!def_stmt || !var)
871     return false;
872   
873   if (TREE_CODE (def_stmt) == PHI_NODE)
874     return false;
875
876   if (SSA_NAME_IS_DEFAULT_DEF (var))
877       return false;
878
879   walk_tree (&def_stmt, is_cast_from_non_pointer_1, data, NULL);
880   if (((cast_t*)data)->type == -1)
881     return true;
882   
883   return false;
884 }
885
886 /* When array element a_p[i] is accessed through the pointer a_p 
887    and index i, it's translated into the following sequence
888    in gimple:
889
890   i.1_5 = (unsigned int) i_1;
891   D.1605_6 = i.1_5 * 16;
892   D.1606_7 = (struct str_t *) D.1605_6;
893   a_p.2_8 = a_p;
894   D.1608_9 = D.1606_7 + a_p.2_8;
895
896   OP0 and OP1 are of the same pointer types and stand for 
897   D.1606_7 and a_p.2_8 or vise versa.
898
899   This function checks that:
900
901   1. one of OP0 and OP1 (D.1606_7) has passed only one cast from 
902   non-pointer type (D.1606_7 = (struct str_t *) D.1605_6;).
903
904   2. one of OP0 and OP1 which has passed the cast from 
905   non-pointer type (D.1606_7), is actually generated by multiplication of 
906   index by size of type to which both OP0 and OP1 point to
907   (in this case D.1605_6 = i.1_5 * 16; ).
908
909   3. an address of def of the var to which was made cast (D.1605_6) 
910   was not taken.(How can it happen?)
911
912   The following items are checked implicitly by the end of algorithm:
913
914   4. one of OP0 and OP1 (a_p.2_8) have never been cast 
915   (because if it was cast to pointer type, its type, that is also 
916   the type of OP0 and OP1, will be marked as escaped during 
917   analysis of casting stmt (when check_cast() is called 
918   from scan_for_refs for this stmt)).   
919
920   5. defs of OP0 and OP1 are not passed into externally visible function
921   (because if they are passed then their type, that is also the type of OP0
922   and OP1, will be marked and escaped during check_call function called from 
923   scan_for_refs with call stmt).
924
925   In total, 1-5 guaranty that it's an access to array by pointer and index. 
926
927 */
928
929 static bool
930 is_array_access_through_pointer_and_index (tree op0, tree op1)
931 {
932   tree base, offset, offset_cast_stmt;
933   tree before_cast, before_cast_def_stmt;
934   cast_t op0_cast, op1_cast;
935
936   /* Check 1.  */
937
938   /* Init data for walk_use_def_chains function.  */
939   op0_cast.type = op1_cast.type = 0;
940   op0_cast.stmt = op1_cast.stmt = NULL;
941
942   visited_stmts = pointer_set_create ();
943   walk_use_def_chains (op0, is_cast_from_non_pointer,(void *)(&op0_cast), false);
944   pointer_set_destroy (visited_stmts);
945
946   visited_stmts = pointer_set_create ();  
947   walk_use_def_chains (op1, is_cast_from_non_pointer,(void *)(&op1_cast), false);
948   pointer_set_destroy (visited_stmts);
949
950   if (op0_cast.type == 1 && op1_cast.type == 0)
951     {
952       base = op1;
953       offset = op0;
954       offset_cast_stmt = op0_cast.stmt;
955     }
956   else if (op0_cast.type == 0 && op1_cast.type == 1)
957     {
958       base = op0;
959       offset = op1;      
960       offset_cast_stmt = op1_cast.stmt;
961     }
962   else
963     return false;
964
965   /* Check 2.  
966      offset_cast_stmt is of the form: 
967      D.1606_7 = (struct str_t *) D.1605_6;  */
968
969   before_cast = SINGLE_SSA_TREE_OPERAND (offset_cast_stmt, SSA_OP_USE);
970   if (!before_cast)
971     return false;
972   
973   if (SSA_NAME_IS_DEFAULT_DEF(before_cast))
974     return false;
975   
976   before_cast_def_stmt = SSA_NAME_DEF_STMT (before_cast);
977   if (!before_cast_def_stmt)
978     return false;
979
980   /* before_cast_def_stmt should be of the form:
981      D.1605_6 = i.1_5 * 16; */
982   
983   if (TREE_CODE (before_cast_def_stmt) == GIMPLE_MODIFY_STMT)
984     {
985       tree lhs = GIMPLE_STMT_OPERAND (before_cast_def_stmt,0);
986       tree rhs = GIMPLE_STMT_OPERAND (before_cast_def_stmt,1);
987
988       /* We expect temporary here.  */
989       if (!is_gimple_reg (lhs)) 
990         return false;
991
992       if (TREE_CODE (rhs) == MULT_EXPR)
993         {
994           tree arg0 = TREE_OPERAND (rhs, 0);
995           tree arg1 = TREE_OPERAND (rhs, 1);
996           tree unit_size = 
997             TYPE_SIZE_UNIT (TREE_TYPE (TYPE_MAIN_VARIANT (TREE_TYPE (op0))));
998
999           if (!(CONSTANT_CLASS_P (arg0) 
1000               && simple_cst_equal (arg0,unit_size))
1001               && !(CONSTANT_CLASS_P (arg1) 
1002               && simple_cst_equal (arg1,unit_size)))
1003             return false;                          
1004         }
1005       else
1006         return false;
1007     }
1008   else
1009     return false;
1010
1011   /* Check 3.
1012      check that address of D.1605_6 was not taken.
1013      FIXME: if D.1605_6 is gimple reg than it cannot be addressable.  */
1014
1015   return true;
1016 }
1017
1018 /* Register the parameter and return types of function FN.  The type
1019    ESCAPES if the function is visible outside of the compilation
1020    unit.  */
1021 static void 
1022 check_function_parameter_and_return_types (tree fn, bool escapes) 
1023 {
1024   tree arg;
1025   
1026   if (TYPE_ARG_TYPES (TREE_TYPE (fn)))
1027     {
1028       for (arg = TYPE_ARG_TYPES (TREE_TYPE (fn));
1029            arg && TREE_VALUE (arg) != void_type_node;
1030            arg = TREE_CHAIN (arg))
1031         {
1032           tree type = get_canon_type (TREE_VALUE (arg), false, false);
1033           if (escapes)
1034             mark_interesting_type (type, EXPOSED_PARAMETER);
1035         }
1036     }
1037   else
1038     {
1039       /* FIXME - According to Geoff Keating, we should never have to
1040          do this; the front ends should always process the arg list
1041          from the TYPE_ARG_LIST. However, Geoff is wrong, this code
1042          does seem to be live.  */
1043
1044       for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg))
1045         {
1046           tree type = get_canon_type (TREE_TYPE (arg), false, false);
1047           if (escapes)
1048             mark_interesting_type (type, EXPOSED_PARAMETER);
1049         }
1050     }
1051   if (escapes)
1052     {
1053       tree type = get_canon_type (TREE_TYPE (TREE_TYPE (fn)), false, false);
1054       mark_interesting_type (type, EXPOSED_PARAMETER); 
1055     }
1056 }
1057
1058 /* Return true if the variable T is the right kind of static variable to
1059    perform compilation unit scope escape analysis.  */
1060
1061 static inline void
1062 has_proper_scope_for_analysis (tree t)
1063 {
1064   /* If the variable has the "used" attribute, treat it as if it had a
1065      been touched by the devil.  */
1066   tree type = get_canon_type (TREE_TYPE (t), false, false);
1067   if (!type) return;
1068
1069   if (lookup_attribute ("used", DECL_ATTRIBUTES (t)))
1070     {
1071       mark_interesting_type (type, FULL_ESCAPE);
1072       return;
1073     }
1074
1075   /* Do not want to do anything with volatile except mark any
1076      function that uses one to be not const or pure.  */
1077   if (TREE_THIS_VOLATILE (t)) 
1078     return;
1079
1080   /* Do not care about a local automatic that is not static.  */
1081   if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
1082     return;
1083
1084   if (DECL_EXTERNAL (t) || TREE_PUBLIC (t))
1085     {
1086       /* If the front end set the variable to be READONLY and
1087          constant, we can allow this variable in pure or const
1088          functions but the scope is too large for our analysis to set
1089          these bits ourselves.  */
1090       
1091       if (TREE_READONLY (t)
1092           && DECL_INITIAL (t)
1093           && is_gimple_min_invariant (DECL_INITIAL (t)))
1094         ; /* Read of a constant, do not change the function state.  */
1095       else 
1096         {
1097           /* The type escapes for all public and externs. */
1098           mark_interesting_type (type, FULL_ESCAPE);
1099         }
1100     }
1101 }
1102
1103 /* If T is a VAR_DECL for a static that we are interested in, add the
1104    uid to the bitmap.  */
1105
1106 static void
1107 check_operand (tree t)
1108 {
1109   if (!t) return;
1110
1111   /* This is an assignment from a function, register the types as
1112      escaping.  */
1113   if (TREE_CODE (t) == FUNCTION_DECL)
1114     check_function_parameter_and_return_types (t, true);
1115
1116   else if (TREE_CODE (t) == VAR_DECL)
1117     has_proper_scope_for_analysis (t); 
1118 }
1119
1120 /* Examine tree T for references.   */
1121
1122 static void
1123 check_tree (tree t)
1124 {
1125   if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR))
1126     return;
1127
1128   /* We want to catch here also REALPART_EXPR and IMAGEPART_EXPR,
1129      but they already included in handled_component_p.  */
1130   while (handled_component_p (t))
1131     {
1132       if (TREE_CODE (t) == ARRAY_REF)
1133         check_operand (TREE_OPERAND (t, 1));
1134       t = TREE_OPERAND (t, 0);
1135     }
1136
1137   if (INDIRECT_REF_P (t))
1138 /*  || TREE_CODE (t) == MEM_REF) */
1139     check_tree (TREE_OPERAND (t, 0));
1140
1141   if (SSA_VAR_P (t) || (TREE_CODE (t) == FUNCTION_DECL))
1142     check_operand (t);
1143 }
1144
1145 /* Create an address_of edge FROM_TYPE.TO_TYPE.  */
1146 static void
1147 mark_interesting_addressof (tree to_type, tree from_type)
1148 {
1149   int from_uid;
1150   int to_uid;
1151   bitmap type_map;
1152   splay_tree_node result; 
1153
1154   from_type = get_canon_type (from_type, false, false);
1155   to_type = get_canon_type (to_type, false, false);
1156   
1157   if (!from_type || !to_type)
1158     return;
1159
1160   from_uid = TYPE_UID (from_type);
1161   to_uid = TYPE_UID (to_type);
1162
1163   gcc_assert (ipa_type_escape_star_count_of_interesting_type (from_type) == 0);
1164   
1165   /* Process the Y into X map pointer.  */
1166   result = splay_tree_lookup (uid_to_addressof_down_map, 
1167                               (splay_tree_key) from_uid);
1168   
1169   if (result) 
1170     type_map = (bitmap) result->value;  
1171   else 
1172     {
1173       type_map = BITMAP_ALLOC (&ipa_obstack);
1174       splay_tree_insert (uid_to_addressof_down_map,
1175                          from_uid, 
1176                          (splay_tree_value)type_map);
1177     }
1178   bitmap_set_bit (type_map, TYPE_UID (to_type));
1179   
1180   /* Process the X into Y reverse map pointer.  */
1181   result = 
1182     splay_tree_lookup (uid_to_addressof_up_map, (splay_tree_key) to_uid);
1183   
1184   if (result) 
1185     type_map = (bitmap) result->value;  
1186   else 
1187     {
1188       type_map = BITMAP_ALLOC (&ipa_obstack);
1189       splay_tree_insert (uid_to_addressof_up_map,
1190                          to_uid, 
1191                          (splay_tree_value)type_map);
1192     }
1193   bitmap_set_bit (type_map, TYPE_UID (from_type)); 
1194 }
1195
1196 /* Scan tree T to see if there are any addresses taken in within T.  */
1197
1198 static void 
1199 look_for_address_of (tree t)
1200 {
1201   if (TREE_CODE (t) == ADDR_EXPR)
1202     {
1203       tree x = get_base_var (t);
1204       tree cref = TREE_OPERAND (t, 0);
1205
1206       /* If we have an expression of the form "&a.b.c.d", mark a.b,
1207          b.c and c.d. as having its address taken.  */ 
1208       tree fielddecl = NULL_TREE;
1209       while (cref!= x)
1210         {
1211           if (TREE_CODE (cref) == COMPONENT_REF)
1212             {
1213               fielddecl =  TREE_OPERAND (cref, 1);
1214               mark_interesting_addressof (TREE_TYPE (fielddecl), 
1215                                           DECL_FIELD_CONTEXT (fielddecl));
1216             }
1217           else if (TREE_CODE (cref) == ARRAY_REF)
1218             get_canon_type (TREE_TYPE (cref), false, false);
1219
1220           cref = TREE_OPERAND (cref, 0);
1221         }
1222
1223       if (TREE_CODE (x) == VAR_DECL) 
1224         has_proper_scope_for_analysis (x);
1225     }
1226 }
1227
1228
1229 /* Scan tree T to see if there are any casts within it.
1230    LHS Is the LHS of the expression involving the cast.  */
1231
1232 static unsigned int 
1233 look_for_casts (tree lhs ATTRIBUTE_UNUSED, tree t)
1234 {
1235   unsigned int cast = 0;
1236
1237
1238   if (is_gimple_cast (t) || TREE_CODE (t) == VIEW_CONVERT_EXPR)
1239     {
1240       tree castfromvar = TREE_OPERAND (t, 0);
1241       cast = cast | check_cast (TREE_TYPE (t), castfromvar);
1242     }
1243   else 
1244     while (handled_component_p (t))
1245       {
1246         t = TREE_OPERAND (t, 0);
1247         if (TREE_CODE (t) == VIEW_CONVERT_EXPR)
1248           {
1249             /* This may be some part of a component ref.
1250                IE it may be a.b.VIEW_CONVERT_EXPR<weird_type>(c).d, AFAIK.
1251                castfromref will give you a.b.c, not a. */
1252             tree castfromref = TREE_OPERAND (t, 0);
1253             cast = cast | check_cast (TREE_TYPE (t), castfromref);
1254           }
1255         else if (TREE_CODE (t) == COMPONENT_REF)
1256           get_canon_type (TREE_TYPE (TREE_OPERAND (t, 1)), false, false);
1257       }
1258
1259   if (!cast)
1260     cast = CT_NO_CAST;
1261   return cast;
1262
1263
1264 /* Check to see if T is a read or address of operation on a static var
1265    we are interested in analyzing.  */
1266
1267 static void
1268 check_rhs_var (tree t)
1269 {
1270   look_for_address_of (t);
1271   check_tree(t);
1272 }
1273
1274 /* Check to see if T is an assignment to a static var we are
1275    interested in analyzing.  */
1276
1277 static void
1278 check_lhs_var (tree t)
1279 {
1280   check_tree(t);
1281 }
1282
1283 /* This is a scaled down version of get_asm_expr_operands from
1284    tree_ssa_operands.c.  The version there runs much later and assumes
1285    that aliasing information is already available. Here we are just
1286    trying to find if the set of inputs and outputs contain references
1287    or address of operations to local.  FN is the function being
1288    analyzed and STMT is the actual asm statement.  */
1289
1290 static void
1291 get_asm_expr_operands (tree stmt)
1292 {
1293   int noutputs = list_length (ASM_OUTPUTS (stmt));
1294   const char **oconstraints
1295     = (const char **) alloca ((noutputs) * sizeof (const char *));
1296   int i;
1297   tree link;
1298   const char *constraint;
1299   bool allows_mem, allows_reg, is_inout;
1300   
1301   for (i=0, link = ASM_OUTPUTS (stmt); link; ++i, link = TREE_CHAIN (link))
1302     {
1303       oconstraints[i] = constraint
1304         = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1305       parse_output_constraint (&constraint, i, 0, 0,
1306                                &allows_mem, &allows_reg, &is_inout);
1307       
1308       check_lhs_var (TREE_VALUE (link));
1309     }
1310
1311   for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
1312     {
1313       constraint
1314         = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1315       parse_input_constraint (&constraint, 0, 0, noutputs, 0,
1316                               oconstraints, &allows_mem, &allows_reg);
1317       
1318       check_rhs_var (TREE_VALUE (link));
1319     }
1320   
1321   /* There is no code here to check for asm memory clobbers.  The
1322      casual maintainer might think that such code would be necessary,
1323      but that appears to be wrong.  In other parts of the compiler,
1324      the asm memory clobbers are assumed to only clobber variables
1325      that are addressable.  All types with addressable instances are
1326      assumed to already escape.  So, we are protected here.  */
1327 }
1328
1329 /* Check the parameters of a function call to CALL_EXPR to mark the
1330    types that pass across the function boundary.  Also check to see if
1331    this is either an indirect call, a call outside the compilation
1332    unit.  */
1333
1334 static void
1335 check_call (tree call_expr) 
1336 {
1337   tree operand;
1338   tree callee_t = get_callee_fndecl (call_expr);
1339   struct cgraph_node* callee;
1340   enum availability avail = AVAIL_NOT_AVAILABLE;
1341   call_expr_arg_iterator iter;
1342
1343   FOR_EACH_CALL_EXPR_ARG (operand, iter, call_expr)
1344     check_rhs_var (operand);
1345   
1346   if (callee_t)
1347     {
1348       tree arg_type;
1349       tree last_arg_type = NULL;
1350       callee = cgraph_node(callee_t);
1351       avail = cgraph_function_body_availability (callee);
1352       
1353       /* Check that there are no implicit casts in the passing of
1354          parameters.  */
1355       if (TYPE_ARG_TYPES (TREE_TYPE (callee_t)))
1356         {
1357           for (arg_type = TYPE_ARG_TYPES (TREE_TYPE (callee_t)),
1358                  operand = first_call_expr_arg (call_expr, &iter);
1359                arg_type && TREE_VALUE (arg_type) != void_type_node;
1360                arg_type = TREE_CHAIN (arg_type),
1361                  operand = next_call_expr_arg (&iter))
1362             {
1363               if (operand)
1364                 {
1365                   last_arg_type = TREE_VALUE(arg_type);
1366                   check_cast (last_arg_type, operand);
1367                 }
1368               else 
1369                 /* The code reaches here for some unfortunate
1370                    builtin functions that do not have a list of
1371                    argument types.  */
1372                 break; 
1373             }
1374         } 
1375       else  
1376         { 
1377           /* FIXME - According to Geoff Keating, we should never
1378              have to do this; the front ends should always process
1379              the arg list from the TYPE_ARG_LIST. */
1380           for (arg_type = DECL_ARGUMENTS (callee_t),
1381                  operand = first_call_expr_arg (call_expr, &iter);
1382                arg_type;
1383                arg_type = TREE_CHAIN (arg_type),
1384                  operand = next_call_expr_arg (&iter))
1385             {
1386               if (operand)
1387                 {
1388                   last_arg_type = TREE_TYPE(arg_type);
1389                   check_cast (last_arg_type, operand);
1390                 } 
1391               else 
1392                 /* The code reaches here for some unfortunate
1393                    builtin functions that do not have a list of
1394                    argument types.  */
1395                 break; 
1396             }
1397         }
1398       
1399       /* In the case where we have a var_args function, we need to
1400          check the remaining parameters against the last argument.  */
1401       arg_type = last_arg_type;
1402       for (;
1403            operand != NULL_TREE;
1404            operand = next_call_expr_arg (&iter))
1405         {
1406           if (arg_type)
1407             check_cast (arg_type, operand);
1408           else 
1409             {
1410               /* The code reaches here for some unfortunate
1411                  builtin functions that do not have a list of
1412                  argument types.  Most of these functions have
1413                  been marked as having their parameters not
1414                  escape, but for the rest, the type is doomed.  */
1415               tree type = get_canon_type (TREE_TYPE (operand), false, false);
1416               mark_interesting_type (type, FULL_ESCAPE);
1417             }
1418         }
1419     }
1420
1421   /* The callee is either unknown (indirect call) or there is just no
1422      scannable code for it (external call) .  We look to see if there
1423      are any bits available for the callee (such as by declaration or
1424      because it is builtin) and process solely on the basis of those
1425      bits. */
1426
1427   if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
1428     {
1429       /* If this is a direct call to an external function, mark all of
1430          the parameter and return types.  */
1431       FOR_EACH_CALL_EXPR_ARG (operand, iter, call_expr)
1432         {
1433           tree type = get_canon_type (TREE_TYPE (operand), false, false);
1434           mark_interesting_type (type, EXPOSED_PARAMETER);
1435     }
1436           
1437       if (callee_t) 
1438         {
1439           tree type = 
1440             get_canon_type (TREE_TYPE (TREE_TYPE (callee_t)), false, false);
1441           mark_interesting_type (type, EXPOSED_PARAMETER);
1442         }
1443     }
1444 }
1445
1446 /* CODE is the operation on OP0 and OP1.  OP0 is the operand that we
1447    *know* is a pointer type.  OP1 may be a pointer type.  */
1448 static bool 
1449 okay_pointer_operation (enum tree_code code, tree op0, tree op1)
1450 {
1451   tree op0type = TYPE_MAIN_VARIANT (TREE_TYPE (op0));
1452   tree op1type = TYPE_MAIN_VARIANT (TREE_TYPE (op1));
1453
1454   switch (code)
1455     {
1456     case MULT_EXPR:
1457       /* Multiplication does not change alignment.  */
1458       return true;
1459       break;
1460     case MINUS_EXPR:
1461     case PLUS_EXPR:
1462       {
1463         if (POINTER_TYPE_P (op1type)
1464             && TREE_CODE (op0) == SSA_NAME 
1465             && TREE_CODE (op1) == SSA_NAME 
1466             && is_array_access_through_pointer_and_index (op0, op1))
1467           return true;
1468         else
1469           {
1470             tree size_of_op0_points_to = TYPE_SIZE_UNIT (TREE_TYPE (op0type));
1471             
1472             if (CONSTANT_CLASS_P (op1)
1473                 && size_of_op0_points_to
1474                 && multiple_of_p (TREE_TYPE (size_of_op0_points_to), 
1475                                   op1, size_of_op0_points_to))
1476               return true;
1477
1478             if (CONSTANT_CLASS_P (op0) 
1479                 && size_of_op0_points_to
1480                 && multiple_of_p (TREE_TYPE (size_of_op0_points_to), 
1481                                   op0, size_of_op0_points_to))
1482               return true;          
1483           }
1484       }
1485       break;
1486     default:
1487       return false;
1488     }
1489   return false;
1490 }
1491
1492 /* TP is the part of the tree currently under the microscope.
1493    WALK_SUBTREES is part of the walk_tree api but is unused here.
1494    DATA is cgraph_node of the function being walked.  */
1495
1496 /* FIXME: When this is converted to run over SSA form, this code
1497    should be converted to use the operand scanner.  */
1498
1499 static tree
1500 scan_for_refs (tree *tp, int *walk_subtrees, void *data)
1501 {
1502   struct cgraph_node *fn = data;
1503   tree t = *tp;
1504
1505   switch (TREE_CODE (t))  
1506     {
1507     case VAR_DECL:
1508       if (DECL_INITIAL (t))
1509         walk_tree (&DECL_INITIAL (t), scan_for_refs, fn, visited_nodes);
1510       *walk_subtrees = 0;
1511       break;
1512
1513     case GIMPLE_MODIFY_STMT:
1514       {
1515         /* First look on the lhs and see what variable is stored to */
1516         tree lhs = GIMPLE_STMT_OPERAND (t, 0);
1517         tree rhs = GIMPLE_STMT_OPERAND (t, 1);
1518
1519         check_lhs_var (lhs);
1520         check_cast (TREE_TYPE (lhs), rhs);
1521
1522         /* For the purposes of figuring out what the cast affects */
1523
1524         /* Next check the operands on the rhs to see if they are ok. */
1525         switch (TREE_CODE_CLASS (TREE_CODE (rhs))) 
1526           {
1527           case tcc_binary:          
1528             {
1529               tree op0 = TREE_OPERAND (rhs, 0);
1530               tree type0 = get_canon_type (TREE_TYPE (op0), false, false);
1531               tree op1 = TREE_OPERAND (rhs, 1);
1532               tree type1 = get_canon_type (TREE_TYPE (op1), false, false);
1533  
1534               /* If this is pointer arithmetic of any bad sort, then
1535                  we need to mark the types as bad.  For binary
1536                  operations, no binary operator we currently support
1537                  is always "safe" in regard to what it would do to
1538                  pointers for purposes of determining which types
1539                  escape, except operations of the size of the type.
1540                  It is possible that min and max under the right set
1541                  of circumstances and if the moon is in the correct
1542                  place could be safe, but it is hard to see how this
1543                  is worth the effort.  */
1544  
1545               if (type0 && POINTER_TYPE_P (type0)
1546                   && !okay_pointer_operation (TREE_CODE (rhs), op0, op1))
1547                 mark_interesting_type (type0, FULL_ESCAPE);
1548               if (type1 && POINTER_TYPE_P (type1)
1549                   && !okay_pointer_operation (TREE_CODE (rhs), op1, op0))
1550                 mark_interesting_type (type1, FULL_ESCAPE);
1551               
1552               look_for_casts (lhs, op0);
1553               look_for_casts (lhs, op1);
1554               check_rhs_var (op0);
1555               check_rhs_var (op1);
1556             }
1557             break;
1558           case tcc_unary:
1559             {
1560               tree op0 = TREE_OPERAND (rhs, 0);
1561               tree type0 = get_canon_type (TREE_TYPE (op0), false, false);
1562               /* For unary operations, if the operation is NEGATE or
1563                  ABS on a pointer, this is also considered pointer
1564                  arithmetic and thus, bad for business.  */
1565               if (type0 && (TREE_CODE (op0) == NEGATE_EXPR
1566                    || TREE_CODE (op0) == ABS_EXPR)
1567                   && POINTER_TYPE_P (type0))
1568                 {
1569                   mark_interesting_type (type0, FULL_ESCAPE);
1570                 }
1571               check_rhs_var (op0);
1572               look_for_casts (lhs, op0);
1573               look_for_casts (lhs, rhs);
1574             }
1575
1576             break;
1577           case tcc_reference:
1578             look_for_casts (lhs, rhs);
1579             check_rhs_var (rhs);
1580             break;
1581           case tcc_declaration:
1582             check_rhs_var (rhs);
1583             break;
1584           case tcc_expression:
1585             switch (TREE_CODE (rhs)) 
1586               {
1587               case ADDR_EXPR:
1588                 look_for_casts (lhs, TREE_OPERAND (rhs, 0));
1589                 check_rhs_var (rhs);
1590                 break;
1591               default:
1592                 break;
1593               }
1594             break;
1595           case tcc_vl_exp:
1596             switch (TREE_CODE (rhs))
1597               {
1598               case CALL_EXPR:
1599                 /* If this is a call to malloc, squirrel away the
1600                    result so we do mark the resulting cast as being
1601                    bad.  */
1602                 check_call (rhs);
1603                 break;
1604               default:
1605                 break;
1606               }
1607             break;
1608           default:
1609             break;
1610           }
1611         *walk_subtrees = 0;
1612       }
1613       break;
1614
1615     case ADDR_EXPR:
1616       /* This case is here to find addresses on rhs of constructors in
1617          decl_initial of static variables. */
1618       check_rhs_var (t);
1619       *walk_subtrees = 0;
1620       break;
1621
1622     case CALL_EXPR: 
1623       check_call (t);
1624       *walk_subtrees = 0;
1625       break;
1626       
1627     case ASM_EXPR:
1628       get_asm_expr_operands (t);
1629       *walk_subtrees = 0;
1630       break;
1631       
1632     default:
1633       break;
1634     }
1635   return NULL;
1636 }
1637
1638
1639 /* The init routine for analyzing global static variable usage.  See
1640    comments at top for description.  */
1641 static void 
1642 ipa_init (void) 
1643 {
1644   bitmap_obstack_initialize (&ipa_obstack);
1645   global_types_exposed_parameter = BITMAP_ALLOC (&ipa_obstack);
1646   global_types_full_escape = BITMAP_ALLOC (&ipa_obstack);
1647   global_types_seen = BITMAP_ALLOC (&ipa_obstack);
1648
1649   uid_to_canon_type = splay_tree_new (splay_tree_compare_ints, 0, 0);
1650   all_canon_types = splay_tree_new (compare_type_brand, 0, 0);
1651   type_to_canon_type = splay_tree_new (splay_tree_compare_pointers, 0, 0);
1652   uid_to_subtype_map = splay_tree_new (splay_tree_compare_ints, 0, 0);
1653   uid_to_addressof_down_map = splay_tree_new (splay_tree_compare_ints, 0, 0);
1654   uid_to_addressof_up_map = splay_tree_new (splay_tree_compare_ints, 0, 0);
1655
1656   /* There are some shared nodes, in particular the initializers on
1657      static declarations.  We do not need to scan them more than once
1658      since all we would be interested in are the addressof
1659      operations.  */
1660   visited_nodes = pointer_set_create ();
1661   initialized = true;
1662 }
1663
1664 /* Check out the rhs of a static or global initialization VNODE to see
1665    if any of them contain addressof operations.  Note that some of
1666    these variables may not even be referenced in the code in this
1667    compilation unit but their right hand sides may contain references
1668    to variables defined within this unit.  */
1669
1670 static void 
1671 analyze_variable (struct varpool_node *vnode)
1672 {
1673   tree global = vnode->decl;
1674   tree type = get_canon_type (TREE_TYPE (global), false, false);
1675
1676   /* If this variable has exposure beyond the compilation unit, add
1677      its type to the global types.  */
1678
1679   if (vnode->externally_visible)
1680     mark_interesting_type (type, FULL_ESCAPE);
1681
1682   gcc_assert (TREE_CODE (global) == VAR_DECL);
1683
1684   if (DECL_INITIAL (global))
1685     walk_tree (&DECL_INITIAL (global), scan_for_refs, NULL, visited_nodes);
1686 }
1687
1688 /* This is the main routine for finding the reference patterns for
1689    global variables within a function FN.  */
1690
1691 static void
1692 analyze_function (struct cgraph_node *fn)
1693 {
1694   tree decl = fn->decl;
1695   check_function_parameter_and_return_types (decl, 
1696                                              fn->local.externally_visible);
1697   if (dump_file)
1698     fprintf (dump_file, "\n local analysis of %s", cgraph_node_name (fn));
1699   
1700   {
1701     struct function *this_cfun = DECL_STRUCT_FUNCTION (decl);
1702     basic_block this_block;
1703
1704     FOR_EACH_BB_FN (this_block, this_cfun)
1705       {
1706         block_stmt_iterator bsi;
1707         for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
1708           walk_tree (bsi_stmt_ptr (bsi), scan_for_refs, 
1709                      fn, visited_nodes);
1710       }
1711   }
1712
1713   /* There may be const decls with interesting right hand sides.  */
1714   if (DECL_STRUCT_FUNCTION (decl))
1715     {
1716       tree step;
1717       for (step = DECL_STRUCT_FUNCTION (decl)->unexpanded_var_list;
1718            step;
1719            step = TREE_CHAIN (step))
1720         {
1721           tree var = TREE_VALUE (step);
1722           if (TREE_CODE (var) == VAR_DECL 
1723               && DECL_INITIAL (var)
1724               && !TREE_STATIC (var))
1725             walk_tree (&DECL_INITIAL (var), scan_for_refs, 
1726                        fn, visited_nodes);
1727           get_canon_type (TREE_TYPE (var), false, false);
1728         }
1729     }
1730 }
1731
1732 \f
1733
1734 /* Convert a type_UID into a type.  */
1735 static tree
1736 type_for_uid (int uid)
1737 {
1738   splay_tree_node result = 
1739     splay_tree_lookup (uid_to_canon_type, (splay_tree_key) uid);
1740   
1741   if (result)
1742     return (tree) result->value;  
1743   else return NULL;
1744 }
1745
1746 /* Return the a bitmap with the subtypes of the type for UID.  If it
1747    does not exist, return either NULL or a new bitmap depending on the
1748    value of CREATE.  */ 
1749
1750 static bitmap
1751 subtype_map_for_uid (int uid, bool create)
1752 {
1753   splay_tree_node result = splay_tree_lookup (uid_to_subtype_map, 
1754                               (splay_tree_key) uid);
1755   
1756   if (result) 
1757     return (bitmap) result->value;  
1758   else if (create)
1759     {
1760       bitmap subtype_map = BITMAP_ALLOC (&ipa_obstack);
1761       splay_tree_insert (uid_to_subtype_map,
1762                          uid, 
1763                          (splay_tree_value)subtype_map);
1764       return subtype_map;
1765     }
1766   else return NULL;
1767 }
1768
1769 /* Mark all of the supertypes and field types of TYPE as being seen.
1770    Also accumulate the subtypes for each type so that
1771    close_types_full_escape can mark a subtype as escaping if the
1772    supertype escapes.  */
1773
1774 static void
1775 close_type_seen (tree type)
1776 {
1777   tree field;
1778   int i, uid;
1779   tree binfo, base_binfo;
1780
1781   /* See thru all pointer tos and array ofs. */
1782   type = get_canon_type (type, true, true);
1783   if (!type)
1784     return;
1785
1786   uid = TYPE_UID (type);
1787
1788   if (bitmap_bit_p (been_there_done_that, uid))
1789     return;
1790   bitmap_set_bit (been_there_done_that, uid);
1791
1792   /* If we are doing a language with a type hierarchy, mark all of
1793      the superclasses.  */
1794   if (TYPE_BINFO (type)) 
1795     for (binfo = TYPE_BINFO (type), i = 0;
1796          BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
1797       {
1798         tree binfo_type = BINFO_TYPE (base_binfo);
1799         bitmap subtype_map = subtype_map_for_uid 
1800           (TYPE_UID (TYPE_MAIN_VARIANT (binfo_type)), true);
1801         bitmap_set_bit (subtype_map, uid);
1802         close_type_seen (get_canon_type (binfo_type, true, true));
1803       }
1804       
1805   /* If the field is a struct or union type, mark all of the
1806      subfields.  */
1807   for (field = TYPE_FIELDS (type);
1808        field;
1809        field = TREE_CHAIN (field))
1810     {
1811       tree field_type;
1812       if (TREE_CODE (field) != FIELD_DECL)
1813         continue;
1814
1815       field_type = TREE_TYPE (field);
1816       if (ipa_type_escape_star_count_of_interesting_or_array_type (field_type) >= 0)
1817         close_type_seen (get_canon_type (field_type, true, true));
1818     }
1819 }
1820
1821 /* Take a TYPE that has been passed by value to an external function
1822    and mark all of the fields that have pointer types as escaping. For
1823    any of the non pointer types that are structures or unions,
1824    recurse.  TYPE is never a pointer type.  */ 
1825
1826 static void
1827 close_type_exposed_parameter (tree type)
1828 {
1829   tree field;
1830   int uid;
1831
1832   type = get_canon_type (type, false, false);
1833   if (!type)
1834     return;
1835   uid = TYPE_UID (type);
1836   gcc_assert (!POINTER_TYPE_P (type));
1837
1838   if (bitmap_bit_p (been_there_done_that, uid))
1839     return;
1840   bitmap_set_bit (been_there_done_that, uid);
1841
1842   /* If the field is a struct or union type, mark all of the
1843      subfields.  */
1844   for (field = TYPE_FIELDS (type);
1845        field;
1846        field = TREE_CHAIN (field))
1847     {
1848       tree field_type;
1849
1850       if (TREE_CODE (field) != FIELD_DECL)
1851         continue;
1852
1853       field_type = get_canon_type (TREE_TYPE (field), false, false);
1854       mark_interesting_type (field_type, EXPOSED_PARAMETER);
1855
1856       /* Only recurse for non pointer types of structures and unions.  */
1857       if (ipa_type_escape_star_count_of_interesting_type (field_type) == 0) 
1858         close_type_exposed_parameter (field_type);
1859     }
1860 }
1861
1862 /* The next function handles the case where a type fully escapes.
1863    This means that not only does the type itself escape, 
1864
1865    a) the type of every field recursively escapes
1866    b) the type of every subtype escapes as well as the super as well
1867    as all of the pointer to types for each field.
1868
1869    Note that pointer to types are not marked as escaping.  If the
1870    pointed to type escapes, the pointer to type also escapes.
1871
1872    Take a TYPE that has had the address taken for an instance of it
1873    and mark all of the types for its fields as having their addresses
1874    taken. */ 
1875
1876 static void
1877 close_type_full_escape (tree type)
1878 {
1879   tree field;
1880   unsigned int i;
1881   int uid;
1882   tree binfo, base_binfo;
1883   bitmap_iterator bi;
1884   bitmap subtype_map;
1885   splay_tree_node address_result; 
1886
1887   /* Strip off any pointer or array types.  */
1888   type = get_canon_type (type, true, true);
1889   if (!type)
1890     return;
1891   uid = TYPE_UID (type);
1892
1893   if (bitmap_bit_p (been_there_done_that, uid))
1894     return;
1895   bitmap_set_bit (been_there_done_that, uid);
1896
1897   subtype_map = subtype_map_for_uid (uid, false);
1898
1899   /* If we are doing a language with a type hierarchy, mark all of
1900      the superclasses.  */
1901   if (TYPE_BINFO (type)) 
1902     for (binfo = TYPE_BINFO (type), i = 0;
1903          BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
1904       {
1905         tree binfotype = BINFO_TYPE (base_binfo);
1906         binfotype = mark_type (binfotype, FULL_ESCAPE);
1907         close_type_full_escape (binfotype);
1908       }
1909       
1910   /* Mark as escaped any types that have been down casted to
1911      this type. */
1912   if (subtype_map)
1913     EXECUTE_IF_SET_IN_BITMAP (subtype_map, 0, i, bi)
1914       {
1915         tree subtype = type_for_uid (i); 
1916         subtype = mark_type (subtype, FULL_ESCAPE);
1917         close_type_full_escape (subtype);
1918       }
1919
1920   /* If the field is a struct or union type, mark all of the
1921      subfields.  */
1922   for (field = TYPE_FIELDS (type);
1923        field;
1924        field = TREE_CHAIN (field))
1925     {
1926       tree field_type;
1927       if (TREE_CODE (field) != FIELD_DECL)
1928         continue;
1929
1930       field_type = TREE_TYPE (field);
1931       if (ipa_type_escape_star_count_of_interesting_or_array_type (field_type) >= 0)
1932         {
1933           field_type = mark_type (field_type, FULL_ESCAPE);
1934           close_type_full_escape (field_type);
1935         }
1936     }
1937
1938   /* For all of the types A that contain this type B and were part of
1939      an expression like "&...A.B...", mark the A's as escaping.  */
1940   address_result = splay_tree_lookup (uid_to_addressof_up_map, 
1941                                       (splay_tree_key) uid);
1942   if (address_result)
1943     {
1944       bitmap containing_classes = (bitmap) address_result->value;
1945       EXECUTE_IF_SET_IN_BITMAP (containing_classes, 0, i, bi)
1946         {
1947           close_type_full_escape (type_for_uid (i));
1948         }
1949     }
1950 }
1951
1952 /* Transitively close the addressof bitmap for the type with UID.
1953    This means that if we had a.b and b.c, a would have both b and c in
1954    its maps.  */ 
1955
1956 static bitmap
1957 close_addressof_down (int uid) 
1958 {
1959   bitmap_iterator bi;
1960   splay_tree_node result = 
1961     splay_tree_lookup (uid_to_addressof_down_map, (splay_tree_key) uid);
1962   bitmap map = NULL;
1963   bitmap new_map;
1964   unsigned int i;
1965   
1966   if (result) 
1967     map = (bitmap) result->value;
1968   else 
1969     return NULL;
1970
1971   if (bitmap_bit_p (been_there_done_that, uid))
1972     return map;
1973   bitmap_set_bit (been_there_done_that, uid);
1974
1975   /* If the type escapes, get rid of the addressof map, it will not be
1976      needed.  */
1977   if (bitmap_bit_p (global_types_full_escape, uid))
1978     {
1979       BITMAP_FREE (map);
1980       splay_tree_remove (uid_to_addressof_down_map, (splay_tree_key) uid);
1981       return NULL;
1982     }
1983
1984   /* The new_map will have all of the bits for the enclosed fields and
1985      will have the unique id version of the old map.  */
1986   new_map = BITMAP_ALLOC (&ipa_obstack);
1987
1988   EXECUTE_IF_SET_IN_BITMAP (map, 0, i, bi)
1989     {
1990       bitmap submap = close_addressof_down (i);
1991       bitmap_set_bit (new_map, i);
1992       if (submap) 
1993         bitmap_ior_into (new_map, submap);
1994     }      
1995   result->value = (splay_tree_value) new_map;
1996
1997   BITMAP_FREE (map);
1998   return new_map;
1999 }
2000
2001 \f
2002 /* The main entry point for type escape analysis.  */
2003
2004 static unsigned int
2005 type_escape_execute (void)
2006 {
2007   struct cgraph_node *node;
2008   struct varpool_node *vnode;
2009   unsigned int i;
2010   bitmap_iterator bi;
2011   splay_tree_node result;
2012
2013   ipa_init ();
2014
2015   /* Process all of the variables first.  */
2016   FOR_EACH_STATIC_VARIABLE (vnode)
2017     analyze_variable (vnode);
2018
2019   /* Process all of the functions. next
2020
2021      We do not want to process any of the clones so we check that this
2022      is a master clone.  However, we do need to process any
2023      AVAIL_OVERWRITABLE functions (these are never clones) because
2024      they may cause a type variable to escape.  
2025   */
2026   for (node = cgraph_nodes; node; node = node->next)
2027     if (node->analyzed 
2028         && (cgraph_is_master_clone (node)
2029             || (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE)))
2030       analyze_function (node);
2031
2032
2033   pointer_set_destroy (visited_nodes);
2034   visited_nodes = NULL;
2035
2036   /* Do all of the closures to discover which types escape the
2037      compilation unit.  */
2038
2039   been_there_done_that = BITMAP_ALLOC (&ipa_obstack);
2040   bitmap_tmp = BITMAP_ALLOC (&ipa_obstack);
2041
2042   /* Examine the types that we have directly seen in scanning the code
2043      and add to that any contained types or superclasses.  */
2044
2045   bitmap_copy (bitmap_tmp, global_types_seen);
2046   EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi)
2047     {
2048       tree type = type_for_uid (i);
2049       /* Only look at records and unions and pointer tos.  */
2050       if (ipa_type_escape_star_count_of_interesting_or_array_type (type) >= 0)
2051         close_type_seen (type);
2052     }
2053   bitmap_clear (been_there_done_that);
2054
2055   /* Examine all of the types passed by value and mark any enclosed
2056      pointer types as escaping.  */
2057   bitmap_copy (bitmap_tmp, global_types_exposed_parameter);
2058   EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi)
2059     {
2060       close_type_exposed_parameter (type_for_uid (i));
2061     }
2062   bitmap_clear (been_there_done_that);
2063
2064   /* Close the types for escape.  If something escapes, then any
2065      enclosed types escape as well as any subtypes.  */
2066   bitmap_copy (bitmap_tmp, global_types_full_escape);
2067   EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi)
2068     {
2069       close_type_full_escape (type_for_uid (i));
2070     }
2071   bitmap_clear (been_there_done_that);
2072
2073   /* Before this pass, the uid_to_addressof_down_map for type X
2074      contained an entry for Y if there had been an operation of the
2075      form &X.Y.  This step adds all of the fields contained within Y
2076      (recursively) to X's map.  */
2077   
2078   result = splay_tree_min (uid_to_addressof_down_map);
2079   while (result)
2080     {
2081       int uid = result->key;
2082       /* Close the addressof map, i.e. copy all of the transitive
2083          substructures up to this level.  */
2084       close_addressof_down (uid);
2085       result = splay_tree_successor (uid_to_addressof_down_map, uid);
2086     }
2087
2088   /* Do not need the array types and pointer types in the persistent
2089      data structures.  */
2090   result = splay_tree_min (all_canon_types);
2091   while (result)
2092     {
2093       tree type = (tree) result->value;
2094       tree key = (tree) result->key;
2095       if (POINTER_TYPE_P (type) 
2096           || TREE_CODE (type) == ARRAY_TYPE)
2097         {
2098           splay_tree_remove (all_canon_types, (splay_tree_key) result->key);
2099           splay_tree_remove (type_to_canon_type, (splay_tree_key) type);
2100           splay_tree_remove (uid_to_canon_type, (splay_tree_key) TYPE_UID (type));
2101           bitmap_clear_bit (global_types_seen, TYPE_UID (type));
2102         }
2103       result = splay_tree_successor (all_canon_types, (splay_tree_key) key);
2104     }
2105
2106   if (dump_file)
2107     { 
2108       EXECUTE_IF_SET_IN_BITMAP (global_types_seen, 0, i, bi)
2109         {
2110           /* The pointer types are in the global_types_full_escape
2111              bitmap but not in the backwards map.  They also contain
2112              no useful information since they are not marked.  */
2113           tree type = type_for_uid (i);
2114           fprintf(dump_file, "type %d ", i);
2115           print_generic_expr (dump_file, type, 0);
2116           if (bitmap_bit_p (global_types_full_escape, i))
2117             fprintf(dump_file, " escaped\n");
2118           else 
2119             fprintf(dump_file, " contained\n");
2120         }
2121     }
2122
2123   /* Get rid of uid_to_addressof_up_map and its bitmaps.  */
2124   result = splay_tree_min (uid_to_addressof_up_map);
2125   while (result)
2126     {
2127       int uid = (int)result->key;
2128       bitmap bm = (bitmap)result->value;
2129
2130       BITMAP_FREE (bm);
2131       splay_tree_remove (uid_to_addressof_up_map, (splay_tree_key) uid);
2132       result = splay_tree_successor (uid_to_addressof_up_map, uid);
2133     }
2134
2135   /* Get rid of the subtype map.  */
2136   result = splay_tree_min (uid_to_subtype_map);
2137   while (result)
2138     {
2139       bitmap b = (bitmap)result->value;
2140       BITMAP_FREE(b);
2141       splay_tree_remove (uid_to_subtype_map, result->key);
2142       result = splay_tree_min (uid_to_subtype_map);
2143     }
2144   splay_tree_delete (uid_to_subtype_map);
2145   uid_to_subtype_map = NULL;
2146
2147   BITMAP_FREE (global_types_exposed_parameter);
2148   BITMAP_FREE (been_there_done_that);
2149   BITMAP_FREE (bitmap_tmp);
2150   return 0;
2151 }
2152
2153 static bool
2154 gate_type_escape_vars (void)
2155 {
2156   return (flag_unit_at_a_time != 0 && flag_ipa_type_escape
2157           /* Don't bother doing anything if the program has errors.  */
2158           && !(errorcount || sorrycount));
2159 }
2160
2161 struct tree_opt_pass pass_ipa_type_escape =
2162 {
2163   "type-escape-var",                    /* name */
2164   gate_type_escape_vars,                /* gate */
2165   type_escape_execute,                  /* execute */
2166   NULL,                                 /* sub */
2167   NULL,                                 /* next */
2168   0,                                    /* static_pass_number */
2169   TV_IPA_TYPE_ESCAPE,                   /* tv_id */
2170   0,                                    /* properties_required */
2171   0,                                    /* properties_provided */
2172   0,                                    /* properties_destroyed */
2173   0,                                    /* todo_flags_start */
2174   0,                                    /* todo_flags_finish */
2175   0                                     /* letter */
2176 };
2177