OSDN Git Service

fa47ce6cda0c4befcaf7e3cdea86dbcb9d56e8ea
[pf3gnuchains/gcc-fork.git] / gcc / tree-alias-common.c
1 /* Tree based points-to analysis
2    Copyright (C) 2002, 2003 Free Software Foundation, Inc.
3    Contributed by Daniel Berlin <dberlin@dberlin.org>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; if not, write to the Free Software
19 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
20 */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "ggc.h"
27 #include "tree-alias-type.h"
28 #include "bitmap.h"
29 #include "tree-alias-common.h"
30
31 /* If we have andersen's points-to analysis, include it.  */
32 #ifdef HAVE_BANSHEE
33 #include "tree-alias-ander.h"
34 #endif
35
36 #include "flags.h"
37 #include "rtl.h"
38 #include "tm_p.h"
39 #include "hard-reg-set.h"
40 #include "basic-block.h"
41 #include "output.h"
42 #include "errors.h"
43 #include "expr.h"
44 #include "diagnostic.h"
45 #include "tree.h"
46 #include "c-common.h"
47 #include "tree-flow.h"
48 #include "tree-inline.h"
49 #include "varray.h"
50 #include "c-tree.h"
51 #include "tree-gimple.h"
52 #include "hashtab.h"
53 #include "function.h"
54 #include "cgraph.h"
55 #include "tree-pass.h"
56 #include "timevar.h"
57
58 /* Reduce ifdefery later.  */
59 #ifndef HAVE_BANSHEE
60 #define HAVE_BANSHEE 0
61 #endif
62
63 /*  This file contains the implementation of the common parts of the
64     tree points-to analysis infrastructure.
65     
66     Overview:
67     
68     This file contains the points-to analysis driver.  It does two main things:
69     1. Keeps track of the PTA data for each variable (IE the data each
70     specific PTA implementation wants to keep associated with a
71     variable).
72     2. Walks the function trees, calling the appropriate functions that
73     each PTA implementation has implemented.
74     
75     In order to speed up PTA queries, the PTA specific data is stored
76     in the tree for *_DECL's, in DECL_PTA_ALIASVAR.  This way, we only
77     need to use the hash table for non-DECL's.  */
78 #define FIELD_BASED 0
79
80 /*  Array of all created alias_vars.
81     Note that this should contain all the alias_vars we wanted
82     marked during GC.  */
83 static GTY((param_is (union alias_var_def))) varray_type alias_vars = NULL;
84 struct tree_alias_ops *current_alias_ops;
85
86 /*  Array of local (to a function) alias_vars.
87     Note that this should contain all the alias_vars that are
88     local to this function.  We delete these from alias_vars before
89     collection.  */
90 static GTY(()) varray_type local_alias_vars;
91 static GTY(()) varray_type local_alias_varnums;
92 tree pta_global_var;
93 static bitmap addrargs;                                          
94 static alias_var get_alias_var_decl (tree);
95 static alias_var get_alias_var (tree);
96 static void find_func_aliases (tree);
97 static void deal_with_call_aliasing (tree, alias_var);
98 static alias_var create_fun_alias_var_ptf (tree, tree);
99 static alias_var create_fun_alias_var (tree, int);
100 static alias_var create_alias_var (tree);
101 static void intra_function_call (varray_type);
102 static void get_values_from_constructor (tree, varray_type *, bitmap, int *);
103 static bool call_may_clobber (tree);
104 static bool call_may_return (tree);
105
106 /* Return true if a EXPR, which is a CALL_EXPR, may clobber variables.  */
107
108 static bool
109 call_may_clobber (tree expr)
110 {
111   int flags;
112
113   if (TREE_CODE (expr) != CALL_EXPR)
114     return false;
115
116   flags = call_expr_flags (expr);
117   return (! (flags & (ECF_CONST | ECF_PURE | ECF_NORETURN)));
118 }
119
120 /* Return true if a EXPR, which is a CALL_EXPR, may return.  */
121
122 static bool
123 call_may_return (tree expr)
124 {
125   int flags;
126   
127   if (TREE_CODE (expr) != CALL_EXPR)
128     return false;
129
130   flags = call_expr_flags (expr);
131   return ! (flags & ECF_NORETURN);
132 }
133
134 /*  Get the alias_var for DECL.  
135     Creates the alias_var if it does not exist already. Also
136     handles FUNCTION_DECL properly.  */
137
138 static alias_var
139 get_alias_var_decl (tree decl)
140 {
141   alias_var newvar;
142   if (TREE_CODE (decl) == FIELD_DECL)
143     abort ();
144   if (DECL_P (decl))
145     {
146       if (DECL_PTA_ALIASVAR (decl))
147         return DECL_PTA_ALIASVAR (decl);
148     }
149
150   if (TREE_CODE (decl) == FUNCTION_DECL)
151     newvar = create_fun_alias_var  (decl, 0);
152   else
153     {
154       newvar = create_alias_var (decl);
155       /* Assign globals to global var for purposes of intraprocedural
156          analysis.  */
157       if (TREE_STATIC (decl) && decl != pta_global_var)
158         {
159           current_alias_ops->addr_assign (current_alias_ops, 
160                                           get_alias_var (pta_global_var), 
161                                           newvar);
162           /* If the global has some DECL_INITIAL, we need to process
163              it here.  */
164           if (DECL_INITIAL (decl))
165             find_func_aliases (decl);
166         }
167     }
168
169   if (!current_alias_ops->ip)
170     {
171       if (!current_alias_ops->ip_partial
172           || (TREE_CODE (decl) != FUNCTION_DECL
173               && TREE_CODE (decl) != PARM_DECL))
174         {
175           VARRAY_PUSH_INT (local_alias_varnums, ALIAS_VAR_VARNUM (newvar));
176           VARRAY_PUSH_TREE (local_alias_vars, decl);
177         }
178     }
179   return newvar;
180 }
181
182 /* Get the alias_var for an expression EXPR.
183    Note that this function expects to only be handed a RHS or LHS, not
184    a MODIFY_EXPR.  */
185
186 static alias_var
187 get_alias_var (tree expr)
188 {
189   /* If it's a decl, get the alias var of the decl. We farm this off
190      to get_alias_var_decl so it can abort if the alias var doesn't
191      exist, and in case something else *knows* it has a decl, and
192      wants the alias var.  */
193
194   if (DECL_P (expr))
195     return get_alias_var_decl (expr);
196
197   /* True constants have no aliases (unless modifiable strings are on,
198      in which case i don't think we'll end up with a STRING_CST anyway) */
199   if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c')
200     return NULL;
201
202
203   switch (TREE_CODE (expr))
204     {
205     case ARRAY_REF:
206     case ARRAY_RANGE_REF:
207       {
208         /* Find the first non-array ref, and return its alias variable.  */
209         tree p;
210
211         for (p = expr;
212              TREE_CODE (p) == ARRAY_REF || TREE_CODE (p) == ARRAY_RANGE_REF;
213              p = TREE_OPERAND (p, 0))
214           ;
215         return get_alias_var (p);
216       }
217       break;
218     case COMPONENT_REF:
219       {
220 #if FIELD_BASED
221         bool safe = true;
222         tree p;
223         for (p = expr; 
224              TREE_CODE (p) == COMPONENT_REF || TREE_CODE (p) == INDIRECT_REF;
225              p = TREE_OPERAND (p, 0))
226           {
227             if (TREE_CODE (TREE_TYPE (p)) == UNION_TYPE 
228                 || TREE_CODE (TREE_TYPE (p)) == QUAL_UNION_TYPE)
229               {
230                 safe = false;
231                 break;
232               }
233           }
234         if (!safe)
235           {
236             for (p = expr; TREE_CODE (p) == COMPONENT_REF;
237                  p = TREE_OPERAND (p, 0));
238             return get_alias_var (p);
239           }
240         else
241           {
242             return get_alias_var (TREE_OPERAND (expr, 1));
243           }
244 #else
245         /* Find the first non-component ref, and return its alias variable.  */
246         tree p;
247         for (p = expr; TREE_CODE (p) == COMPONENT_REF;
248              p = TREE_OPERAND (p, 0));
249         return get_alias_var (p);
250 #endif
251       }
252       break;
253     case REALPART_EXPR:
254     case IMAGPART_EXPR:
255     case NOP_EXPR:
256     case CONVERT_EXPR:
257     case FIX_TRUNC_EXPR:
258     case FIX_CEIL_EXPR:
259     case FIX_FLOOR_EXPR:
260     case FIX_ROUND_EXPR:
261     case ADDR_EXPR:
262     case INDIRECT_REF:
263     case BIT_FIELD_REF:
264       /* If it's a ref or cast or conversion of something, get the
265          alias var of the something.  */
266       return get_alias_var (TREE_OPERAND (expr, 0));
267       break;
268
269     default:
270       return NULL;
271     }
272 }
273
274 /*  Perform conservative aliasing for an intraprocedural mode function
275     call.  ARGS are the arguments that were passed to that function
276     call.  */
277
278 static void
279 intra_function_call (varray_type args)
280 {
281   size_t l = VARRAY_ACTIVE_SIZE (args);
282   size_t i;
283   alias_var av = get_alias_var (pta_global_var);
284
285   /* We assume assignments among the actual parameters.  */
286   for (i = 0; i < l; i++)
287     {
288       alias_var argi = VARRAY_GENERIC_PTR (args, i);
289       size_t j;
290       for (j = 0; j < l; j++)
291         {
292           alias_var argj;
293           if (i == j)
294             continue;
295           argj = VARRAY_GENERIC_PTR (args, j);
296           /* Restricted pointers can't be aliased with other
297              restricted pointers.  */
298           if (!TYPE_RESTRICT (TREE_TYPE (ALIAS_VAR_DECL (argi)))
299               || !TYPE_RESTRICT (TREE_TYPE (ALIAS_VAR_DECL (argj))))
300             /* Do a bit of TBAA to avoid pointless assignments.  */
301             if (alias_sets_conflict_p (get_alias_set (ALIAS_VAR_DECL (argi)),
302                                        get_alias_set (ALIAS_VAR_DECL (argj))))        
303               current_alias_ops->simple_assign (current_alias_ops, argi, argj);
304         }
305     }
306   /* We assume that an actual parameter can point to any global.  */
307   for (i = 0; i < l; i++)
308     {
309       alias_var argav = VARRAY_GENERIC_PTR (args, i);
310       /* Restricted pointers can't be aliased with other
311          restricted pointers.  */
312       if (!TYPE_RESTRICT (TREE_TYPE (ALIAS_VAR_DECL (argav)))
313           || !TYPE_RESTRICT (TREE_TYPE (ALIAS_VAR_DECL (av))))
314         {
315           /* Arguments can alias globals, and whatever they point to
316              can point to a global as well.  */
317           current_alias_ops->simple_assign (current_alias_ops, argav, av);
318         }
319     }
320 }
321
322 /* Put all pointers in a constructor in an array.  */
323
324 static void
325 get_values_from_constructor (tree constructor, varray_type *vals, 
326                              bitmap addrargs, int *i)
327 {
328   tree elt_list;
329   switch (TREE_CODE (constructor))
330     {
331     case CONSTRUCTOR:
332       {
333         for (elt_list = CONSTRUCTOR_ELTS (constructor);
334              elt_list;
335              elt_list = TREE_CHAIN (elt_list))
336           {
337             tree value = TREE_VALUE (elt_list);
338             if (TREE_CODE (value) == TREE_LIST
339                 || TREE_CODE (value) == CONSTRUCTOR)
340               {
341                 get_values_from_constructor (value, vals, addrargs, i);                       }
342             else
343               {
344                 alias_var aav;
345                 aav = get_alias_var (value);
346                 if (aav)
347                   VARRAY_PUSH_GENERIC_PTR (*vals, aav);
348                 if (TREE_CODE (value) == ADDR_EXPR)
349                   bitmap_set_bit (addrargs, *i);
350                 *i = *i + 1;
351               }
352           }
353       }
354       break;
355     case TREE_LIST:
356       for (elt_list = constructor;
357            elt_list;
358            elt_list = TREE_CHAIN (elt_list))
359         {
360           get_values_from_constructor (TREE_VALUE (elt_list), vals, addrargs, i);
361         }
362       break;
363     default:
364       abort();
365     }
366 }
367
368 /* Deal with the possible return values of a call that we don't have
369    actual PTA info about.  */
370
371 static void
372 deal_with_call_aliasing (tree callargs, alias_var lhsAV)
373 {
374   tree arg, argp;
375   
376   for (argp = callargs;
377        argp;
378        argp = TREE_CHAIN (argp))
379     {
380       arg = TREE_VALUE (argp);
381       /* If we take the address of a variable directly in the
382          argument, the return value could be the address of that
383          variable.  */ 
384       if (TREE_CODE (arg) == ADDR_EXPR)
385         current_alias_ops->addr_assign (current_alias_ops, lhsAV,
386                                         get_alias_var (arg));
387       /* If we pass in a pointer, we could return that pointer.  */
388       else if (POINTER_TYPE_P (TREE_TYPE (arg)))
389         {
390           alias_var argtv = get_alias_var (arg);
391           if (argtv)
392             current_alias_ops->simple_assign (current_alias_ops, lhsAV,
393                                               argtv);
394         }
395     }
396 }
397
398 /* Find the operand of the component ref that actually is doing
399    something to the DECL  */
400 static tree
401 find_op_of_decl (tree cref)
402 {
403   while (!DECL_P (TREE_OPERAND (cref, 0)))
404     {
405       cref = TREE_OPERAND (cref, 0);
406     }
407   return cref;
408 }
409
410
411 /*  Tree walker that is the heart of the aliasing infrastructure.
412     TP is a pointer to the current tree.
413     WALK_SUBTREES specifies whether to continue traversing subtrees or
414     not.
415     Returns NULL_TREE when we should stop.
416     
417     This function is the main part of the aliasing infrastructure. It
418     walks the trees, calling the appropriate alias analyzer functions to process
419     various statements.  */
420
421 static void
422 find_func_aliases (tree stp)
423 {
424   if (TREE_CODE (stp) == RETURN_EXPR)
425     {
426       stp = TREE_OPERAND (stp, 0);
427       if (!stp)
428         return;
429     }
430   
431   if (TREE_CODE (stp) == MODIFY_EXPR
432       || (DECL_P (stp) && DECL_INITIAL (stp) != NULL_TREE ))
433     {
434       tree op0, op1;
435       alias_var lhsAV = NULL;
436       alias_var rhsAV = NULL;
437
438       if (DECL_P (stp))
439         {
440           op0 = stp;
441           op1 = DECL_INITIAL (stp);
442         }
443       else
444         {
445           op0 = TREE_OPERAND (stp, 0);
446           op1 = TREE_OPERAND (stp, 1);
447           if (TREE_CODE (op1) == WITH_SIZE_EXPR)
448             op1 = TREE_OPERAND (op1, 0);
449         }
450
451       /* lhsAV should always have an alias variable */
452       lhsAV = get_alias_var (op0);
453       if (!lhsAV)
454         return;
455       /* rhsAV might not have one, c.f. c = 5 */
456       rhsAV = get_alias_var (op1);
457 #if !FIELD_BASED
458       while (TREE_CODE (op1) == COMPONENT_REF 
459              && TREE_CODE (TREE_OPERAND (op1, 0)) == COMPONENT_REF)
460         {
461           op1 = TREE_OPERAND (op1, 0);
462         }
463       while (TREE_CODE (op1) == BIT_FIELD_REF)
464         {
465           op1 = TREE_OPERAND (op1, 0);
466         }
467       /* Take care of fact that we may have multi-level component
468          refs.  */ 
469       if (TREE_CODE (op1) == COMPONENT_REF)
470         op1 = find_op_of_decl (op1);
471 #endif
472       
473       /* You would think we could test rhsAV at the top, rather than
474          50 separate times, but we can't, because it can be NULL for
475          operator assignments, where we'd still collect the individual
476          alias vars for the operator.  */
477
478       /* Note that structures are treated as a single alias
479          variable, since we can disambiguate based on TBAA first,
480          and fall back on points-to.  */
481       /* x = <something> */
482       if (is_gimple_variable (op0))
483         {
484           /* x = y */
485           if (is_gimple_variable (op1))
486             {
487               if (rhsAV != NULL)
488                 current_alias_ops->simple_assign (current_alias_ops, lhsAV,
489                                                   rhsAV);
490             }
491           /* x = foo.y */
492           else if (TREE_CODE (op1) == COMPONENT_REF 
493                    && DECL_P (TREE_OPERAND (op1, 0)))
494             {
495                  if (rhsAV != NULL)
496                 current_alias_ops->simple_assign (current_alias_ops, lhsAV,
497                                                   rhsAV);
498             }
499           /* x = (cast) [maybe-addr-expr] y */
500           else if (is_gimple_cast (op1))
501             {
502               tree stripped_op1 = op1;
503               STRIP_NOPS (stripped_op1);
504               if (rhsAV != NULL)
505                 {
506                   if (TREE_CODE (stripped_op1) == ADDR_EXPR)
507                     current_alias_ops->addr_assign (current_alias_ops, lhsAV, 
508                                                     rhsAV);
509                   else
510                     current_alias_ops->simple_assign (current_alias_ops, lhsAV,
511                                                       rhsAV);
512                 }
513             }
514           /* x = *y or x = foo->y */
515           else if (TREE_CODE (op1) == INDIRECT_REF 
516                    || TREE_CODE (op1) == ARRAY_REF
517                    || (TREE_CODE (op1) == COMPONENT_REF
518                        && TREE_CODE (TREE_OPERAND (op1, 0)) == INDIRECT_REF))
519             {
520               if (rhsAV != NULL)
521                 current_alias_ops->ptr_assign (current_alias_ops, lhsAV,
522                                                rhsAV);
523             }
524           /* x = &y = x = &foo.y */
525           else if (TREE_CODE (op1) == ADDR_EXPR)
526             {
527               if (rhsAV != NULL)
528                 current_alias_ops->addr_assign (current_alias_ops, lhsAV,
529                                                 rhsAV);
530             }
531           /* x = func(...) */
532           else if (TREE_CODE (op1) == CALL_EXPR)
533             {
534               /* Heap assignment. These are __attribute__ malloc or
535                  something, I'll deal with it later.  */
536               if (0)
537                 {}
538               else
539                 {
540                   
541                   /* NORETURN functions have no effect on aliasing.  */
542                   if (call_may_return (op1))
543                     {                 
544                       varray_type args;
545                       tree arg;
546                       tree callop0, callop1;
547                       int argnum;
548                       
549                       /* Collect the arguments */
550                       VARRAY_GENERIC_PTR_INIT (args, 1, "Arguments");
551                       bitmap_clear (addrargs);
552                       callop1 = TREE_OPERAND (op1, 1);
553                       callop0 = TREE_OPERAND (op1, 0);
554                       for (arg = callop1, argnum = 0;
555                            arg;
556                            arg = TREE_CHAIN (arg), argnum++)
557                         {
558                           alias_var aav = get_alias_var (TREE_VALUE (arg));
559                           if (aav)
560                             {
561                               VARRAY_PUSH_GENERIC_PTR (args, aav);
562                               if (TREE_CODE (TREE_VALUE (arg)) == ADDR_EXPR)
563                                 bitmap_set_bit (addrargs, argnum);
564                             }
565                         }
566                       /* Simulate the call */
567                       if (current_alias_ops->function_call (current_alias_ops, lhsAV,
568                                                             get_alias_var (callop0),
569                                                             args, addrargs))
570                         { 
571                           if (call_may_clobber (op1)
572                               && !current_alias_ops->ip
573                               && flag_argument_noalias != 2)
574                             {
575                               intra_function_call (args);
576                             }
577                           if (POINTER_TYPE_P (TREE_TYPE (op0)))
578                             deal_with_call_aliasing (callop1, lhsAV);
579                         }
580                     }
581                 }
582             }
583           /* x = op (...) */
584           else
585             {
586               bitmap_clear (addrargs);
587               if (TREE_CODE (op1) == CONSTRUCTOR)
588                 {
589                   varray_type ops;
590                   int i = 0;
591                   VARRAY_GENERIC_PTR_INIT (ops, 1, "Operands");
592                   get_values_from_constructor (op1, &ops, addrargs, &i);
593                   current_alias_ops->op_assign (current_alias_ops, lhsAV,
594                                                 ops, op1, addrargs);
595                 }
596               else
597                 switch (TREE_CODE_CLASS (TREE_CODE (op1)))
598                   {
599                   case 'e':  /* an expression */
600                   case 's':  /* an expression with side effects */
601                   case '<':  /* a comparison expression */
602                   case '1':  /* a unary arithmetic expression */
603                   case 'r':  /* a reference */
604                   case '2':  /* a binary arithmetic expression */
605                     {
606                       tree op;
607                       varray_type ops;
608                       int i;
609                       VARRAY_GENERIC_PTR_INIT (ops, 1, "Operands");
610                       for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (op1)); i++)
611                         {
612                           alias_var aav;
613                           op = TREE_OPERAND (op1, i);
614                           aav = get_alias_var (op);
615                           if (aav)
616                             VARRAY_PUSH_GENERIC_PTR (ops, aav);
617                           if (TREE_CODE (op) == ADDR_EXPR)
618                             bitmap_set_bit (addrargs, i);
619                         }
620                       current_alias_ops->op_assign (current_alias_ops, lhsAV,
621                                                     ops, op1, addrargs);
622                     }
623                     break;
624                   default:
625                     break;
626                   }
627             }
628         }
629       /* *x = <something> */
630       else
631         {
632           /* x.f = y  or x->f = y */
633           if ((TREE_CODE (op0) == COMPONENT_REF 
634                || TREE_CODE (op0) == BIT_FIELD_REF)
635               && is_gimple_variable (op1))
636             {
637               if (rhsAV != NULL)
638                 current_alias_ops->simple_assign (current_alias_ops, lhsAV,
639                                                   rhsAV);
640             }
641           /* x.f = &y or x->f = &y */
642           else if (TREE_CODE (op0) == COMPONENT_REF 
643                    && TREE_CODE (op1) == ADDR_EXPR)
644             {
645               if (rhsAV != NULL)
646                 current_alias_ops->addr_assign (current_alias_ops, lhsAV,
647                                                 rhsAV);
648             }
649           /* *x.f = y or *x->f = y */
650           else if ((TREE_CODE (op0) == INDIRECT_REF 
651                     || TREE_CODE (op0) == ARRAY_REF)
652                    && TREE_CODE (TREE_OPERAND (op0, 0)) == COMPONENT_REF
653                    && is_gimple_variable (op1))
654             {
655               if (rhsAV != NULL)
656                 current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
657                                                rhsAV);
658             }
659           /* *x = &y */
660           else if ((TREE_CODE (op0) == INDIRECT_REF
661                     || TREE_CODE (op0) == ARRAY_REF)
662                    && TREE_CODE (op1) == ADDR_EXPR)
663             {
664               /* This becomes temp = &y and *x = temp .  */
665               alias_var tempvar;
666               tree temp = create_tmp_var_raw (void_type_node, "aliastmp");
667               tempvar = current_alias_ops->add_var (current_alias_ops, temp);
668               current_alias_ops->addr_assign (current_alias_ops, tempvar,
669                                               rhsAV);
670               current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
671                                              tempvar);
672             }
673
674           /* *x = *y */
675           else if ((TREE_CODE (op0) == INDIRECT_REF 
676                     || TREE_CODE (op0) == ARRAY_REF)
677                    && (TREE_CODE (op1) == INDIRECT_REF
678                        || TREE_CODE (op1) == ARRAY_REF))
679             {
680               /* This becomes temp = *y and *x = temp .  */
681               alias_var tempvar;
682               tree temp;
683               temp = create_tmp_var_raw (void_type_node, "aliastmp");
684               tempvar = current_alias_ops->add_var (current_alias_ops, temp);
685               current_alias_ops->ptr_assign (current_alias_ops, tempvar,
686                                              rhsAV);
687               current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
688                                              tempvar);
689             }
690
691           /* *x = (cast) y */
692           else if ((TREE_CODE (op0) == INDIRECT_REF 
693                     || TREE_CODE (op0) == ARRAY_REF)
694                    && is_gimple_cast (op1))
695             {
696               if (rhsAV != NULL)
697                 {
698                   /* This becomes temp = (cast) y and  *x = temp.  */
699                   alias_var tempvar;
700                   tree temp;
701                   temp = create_tmp_var_raw (void_type_node, "aliastmp");
702                   tempvar = current_alias_ops->add_var (current_alias_ops,
703                                                         temp);
704                   current_alias_ops->simple_assign (current_alias_ops,
705                                                     tempvar, rhsAV);
706                   current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
707                                                  tempvar);
708                 }
709             }
710           /* *x = <something else> */
711           else
712             {
713               if (rhsAV != NULL)
714                 current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
715                                                rhsAV);
716             }
717         }
718     }
719   /* Calls without return values.  */
720   else if (TREE_CODE (stp) == CALL_EXPR)
721     {
722       alias_var callvar;
723       varray_type args;
724       tree arg;
725       callvar = get_alias_var (TREE_OPERAND (stp, 0));
726       if (callvar != NULL)
727         {
728         
729           /* NORETURN and CONST functions with no return value
730              have no effect on aliasing (as may be seen above,
731              const functions that return a value might have an
732              effect on aliasing, since the return value can point
733              to one of the arguments.  */
734           if (call_may_clobber (stp))
735             {
736               int argnum;
737               VARRAY_GENERIC_PTR_INIT (args, 1, "Arguments");
738               bitmap_clear (addrargs);
739               for (arg = TREE_OPERAND (stp, 1), argnum=0; 
740                    arg; 
741                    arg = TREE_CHAIN (arg), argnum++)
742                 {
743                   alias_var aav = get_alias_var (TREE_VALUE (arg));
744                   if (aav)
745                     {
746                       VARRAY_PUSH_GENERIC_PTR (args, aav);
747                       if (TREE_CODE (TREE_VALUE (arg)) == ADDR_EXPR)
748                         bitmap_set_bit (addrargs, argnum);
749                     }
750                   
751                 }
752               
753               if (current_alias_ops->function_call (current_alias_ops, NULL,
754                                                     callvar, args, addrargs))
755                 if (!current_alias_ops->ip && flag_argument_noalias != 2)
756                   intra_function_call (args);
757             }
758         }
759   }
760 }
761
762 /*  Create the alias_var for a function definition DECL, it's
763     arguments, and it's return value. If FORCE is true, we force 
764     creation of the alias_var, regardless of whether one exists already.
765     
766     This includes creation of alias_var's for
767     - The function itself.
768     - The arguments.
769     - The return value.  */
770
771 static alias_var
772 create_fun_alias_var (tree decl, int force)
773 {
774   alias_var avar, retvar;
775   tree rdecl;
776   varray_type params = NULL;
777
778   if (!force)
779     {
780       if (DECL_PTA_ALIASVAR (decl))
781         return DECL_PTA_ALIASVAR (decl);
782     }
783
784   VARRAY_GENERIC_PTR_INIT (params, 1, "Arguments");
785   if (DECL_ARGUMENTS (decl) != NULL)
786     {
787       tree arg;
788       for (arg = DECL_ARGUMENTS (decl); arg; arg = TREE_CHAIN (arg))
789         {
790           alias_var var = get_alias_var (arg);
791           VARRAY_PUSH_GENERIC_PTR (params, var);
792           /* Incoming pointers can point to pta_global_var, unless
793              either we are interprocedural, or we can do ip on all
794              statics + this function has been defined + it's not an
795              external function.  */
796           if (POINTER_TYPE_P (TREE_TYPE (arg))
797               && !current_alias_ops->ip
798               /* FIXME: Need to let analyzer decide in partial case.  */
799               && (!current_alias_ops->ip_partial
800                   || !cgraph_local_info (decl)->local))
801             current_alias_ops->simple_assign (current_alias_ops, var,
802                                               get_alias_var (pta_global_var));
803         }
804     }
805   else if (TYPE_ARG_TYPES (TREE_TYPE (decl)) != NULL)
806     {
807       tree arg;
808       /* FIXME: Handle varargs */
809       for (arg = TYPE_ARG_TYPES (TREE_TYPE (decl));
810            arg && TREE_VALUE (arg) != void_type_node;
811            arg = TREE_CHAIN (arg))
812         {
813           tree fakedecl = create_tmp_var_raw (TREE_VALUE (arg), "normarg");
814           alias_var var;
815           DECL_CONTEXT (fakedecl) = current_function_decl; 
816           var = get_alias_var (fakedecl);
817           VARRAY_PUSH_GENERIC_PTR (params, var);
818
819           /* Incoming pointers can point to pta_global_var, unless
820              either we are interprocedural, or we can do ip on all
821              statics + this function has been defined + it's not an
822              external function.  */
823           if (POINTER_TYPE_P (TREE_TYPE (fakedecl))
824               && !current_alias_ops->ip
825               /* FIXME: need to let analyzer decide in partial case.  */
826               && (!current_alias_ops->ip_partial
827                   || !TREE_STATIC (decl)
828                   || TREE_PUBLIC (decl)))
829             current_alias_ops->simple_assign (current_alias_ops, var,
830                                               get_alias_var (pta_global_var));
831         }
832     }
833   /* Functions declared like void f() are *not* equivalent to void
834      f(void). You can pass an argument to them. Thus, we need to
835      create some fake argument that would alias any actuals that get
836      passed to our function.  */
837   else
838     {
839       tree fakedecl = create_tmp_var_raw (void_type_node, "fakearg");
840       alias_var fakevar;
841       DECL_CONTEXT (fakedecl) = current_function_decl;
842       fakevar = get_alias_var (fakedecl);
843       VARRAY_PUSH_GENERIC_PTR (params, fakevar);
844     }
845
846   if (!DECL_RESULT (decl))
847     {
848       rdecl = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (decl)), "_rv_");
849       retvar = current_alias_ops->add_var (current_alias_ops, rdecl);
850       DECL_PTA_ALIASVAR (rdecl) = retvar;
851     }
852   else
853     {
854       retvar = current_alias_ops->add_var (current_alias_ops,
855                                            DECL_RESULT (decl));
856       DECL_PTA_ALIASVAR (DECL_RESULT (decl)) = retvar;
857     }
858   VARRAY_PUSH_GENERIC_PTR (alias_vars, retvar);
859   ALIAS_VAR_VARNUM (retvar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
860   avar = current_alias_ops->add_var (current_alias_ops, decl);
861   VARRAY_PUSH_GENERIC_PTR (alias_vars, avar);
862   ALIAS_VAR_VARNUM (avar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
863
864   current_alias_ops->function_def (current_alias_ops, avar, params, retvar);
865   DECL_PTA_ALIASVAR (decl) = avar;
866
867   /* FIXME: Also, if this is a defining declaration then add the annotation
868      to all extern definitions of the function.  */
869   return avar;
870 }
871
872 /*  Create an alias variable for a pointer-to-member function DECL of 
873     type TYPE, it's arguments, and it's return value.
874     Returns the alias_var for the PTF.
875     
876     This includes creating alias_var's for
877     - The function itself.
878     - The arguments.
879     - The return value.  */
880
881 static alias_var
882 create_fun_alias_var_ptf (tree decl, tree type)
883 {
884   alias_var avar, retvar;
885   tree rdecl;
886   varray_type params = NULL;
887
888   if (DECL_PTA_ALIASVAR (decl))
889     return DECL_PTA_ALIASVAR (decl);
890
891   VARRAY_GENERIC_PTR_INIT (params, 1, "Arguments");
892
893   if (TYPE_ARG_TYPES  (type) != NULL)
894     {
895       tree arg;
896       /* FIXME: Handle varargs */
897       for (arg = TYPE_ARG_TYPES (type);
898            arg && TREE_VALUE (arg) != void_type_node;
899            arg = TREE_CHAIN (arg))
900         {
901           tree fakedecl = create_tmp_var_raw (TREE_VALUE (arg), "ptfarg");
902           alias_var var;
903           DECL_CONTEXT (fakedecl) = DECL_CONTEXT (decl);
904           var = get_alias_var (fakedecl);
905           VARRAY_PUSH_GENERIC_PTR (params, var);
906         }
907     }
908   /* Functions declared like void f() are *not* equivalent to void
909      f(void). You can pass an argument to them. Thus, we need to
910      create some fake argument that would alias any actuals that get
911      passed to our function.  */
912   else
913     {
914       tree fakedecl = create_tmp_var_raw (void_type_node, "fakearg");
915       alias_var fakevar;
916       DECL_CONTEXT (fakedecl) = DECL_CONTEXT (decl);
917       fakevar = get_alias_var (fakedecl);
918       VARRAY_PUSH_GENERIC_PTR (params, fakevar);
919     }
920
921   rdecl = create_tmp_var_raw (TREE_TYPE (type), "_rv_");
922   retvar = current_alias_ops->add_var (current_alias_ops, rdecl);
923   VARRAY_PUSH_GENERIC_PTR (alias_vars, retvar);
924   ALIAS_VAR_VARNUM (retvar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
925
926   avar = current_alias_ops->add_var (current_alias_ops, decl);
927   VARRAY_PUSH_GENERIC_PTR (alias_vars, avar);
928   ALIAS_VAR_VARNUM (avar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
929
930   current_alias_ops->function_def (current_alias_ops, avar, params, retvar);
931   DECL_PTA_ALIASVAR (decl) = avar;
932
933   return avar;
934 }
935
936 /*  Create the alias_var for a *_DECL node DECL.
937     Returns the alias_var for DECL.
938     
939     This function also handles creation of alias_var's for PTF 
940     variables.  */
941
942 static alias_var
943 create_alias_var (tree decl)
944 {
945   alias_var avar;
946
947   if (!DECL_P (decl))
948     abort ();
949   
950   if (DECL_P (decl))
951     {
952       if (DECL_PTA_ALIASVAR (decl))
953         return DECL_PTA_ALIASVAR (decl);
954     }
955
956   if (POINTER_TYPE_P (TREE_TYPE (decl))
957       && TREE_CODE (TREE_TYPE (TREE_TYPE (decl))) == FUNCTION_TYPE)
958     {
959       avar = create_fun_alias_var_ptf (decl, TREE_TYPE (TREE_TYPE (decl)));
960     }
961   else
962     avar = current_alias_ops->add_var (current_alias_ops, decl);
963
964   if (DECL_P (decl))
965     {
966       DECL_PTA_ALIASVAR (decl) = avar;
967     }
968
969   VARRAY_PUSH_GENERIC_PTR (alias_vars, avar);
970   ALIAS_VAR_VARNUM (avar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
971   return avar;
972 }
973
974 /* Create points-to sets for the current function.  */
975
976 static void
977 create_alias_vars (void)
978 {
979   basic_block bb;
980 #if HAVE_BANSHEE
981   if (flag_tree_points_to == PTA_ANDERSEN)
982     current_alias_ops = andersen_alias_ops;
983   else
984 #endif
985    {
986      current_alias_ops = NULL;
987      flag_tree_points_to = PTA_NONE;
988      return;
989    }
990
991   pta_global_var = build_decl (VAR_DECL, get_identifier (".pta_global_var"),
992                                size_type_node);
993   DECL_ARTIFICIAL (pta_global_var) = 1;
994   TREE_READONLY (pta_global_var) = 1;
995   DECL_EXTERNAL (pta_global_var) = 0;
996   TREE_STATIC (pta_global_var) = 1;
997   TREE_USED (pta_global_var) = 1;
998   DECL_CONTEXT (pta_global_var) = current_function_decl; 
999   TREE_THIS_VOLATILE (pta_global_var) = 1;
1000   TREE_ADDRESSABLE (pta_global_var) = 0;
1001
1002   init_alias_vars ();
1003
1004   DECL_PTA_ALIASVAR (current_function_decl) = NULL;
1005   get_alias_var (current_function_decl);
1006
1007   /* First, walk the variables and their DECL_INITIAL's */
1008   if (cfun->unexpanded_var_list)
1009     {
1010       tree vars, var;
1011       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
1012         {
1013           var = TREE_VALUE (vars);
1014           if (TREE_CODE (var) != LABEL_DECL
1015               && TREE_STATIC (var)
1016               && DECL_INITIAL (var))
1017             find_func_aliases (var);
1018         }
1019     }
1020
1021   /* Now walk all statements and derive aliases.  */
1022   FOR_EACH_BB (bb)
1023     {
1024       block_stmt_iterator bsi; 
1025       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1026         find_func_aliases (bsi_stmt (bsi));
1027     }
1028
1029   pta_global_var = NULL_TREE;
1030 }
1031
1032 static bool
1033 gate_pta (void)
1034 {
1035 #ifdef HAVE_BANSHEE
1036   return flag_tree_points_to != PTA_NONE;
1037 #else
1038   return false;
1039 #endif
1040 }
1041
1042 struct tree_opt_pass pass_build_pta = 
1043 {
1044   "pta",                                /* name */
1045   gate_pta,                             /* gate */
1046   create_alias_vars,                    /* execute */
1047   NULL,                                 /* sub */
1048   NULL,                                 /* next */
1049   0,                                    /* static_pass_number */
1050   TV_TREE_PTA,                          /* tv_id */
1051   PROP_cfg,                             /* properties_required */
1052   PROP_pta,                             /* properties_provided */
1053   0,                                    /* properties_destroyed */
1054   0,                                    /* todo_flags_start */
1055   0,                                    /* todo_flags_finish */
1056   0                                     /* letter */
1057 };
1058  
1059
1060 /* Delete created points-to sets.  */
1061
1062 static void
1063 delete_alias_vars (void)
1064 {
1065   size_t i;
1066
1067   for (i = 0; i < VARRAY_ACTIVE_SIZE (local_alias_vars); i++)
1068     {
1069       tree key = VARRAY_TREE (local_alias_vars, i);
1070       if (DECL_P (key))
1071         DECL_PTA_ALIASVAR (key) = NULL;
1072       else
1073         abort ();
1074     }
1075
1076   for (i = 0; i < VARRAY_ACTIVE_SIZE (local_alias_varnums); i ++)
1077     VARRAY_GENERIC_PTR (alias_vars, VARRAY_INT (local_alias_varnums, i)) = NULL;
1078   if (!current_alias_ops->ip && !current_alias_ops->ip_partial)
1079     {
1080       /*      VARRAY_CLEAR (alias_vars); */
1081       VARRAY_CLEAR (local_alias_vars);
1082       VARRAY_CLEAR (local_alias_varnums);
1083     }
1084   BITMAP_XFREE (addrargs);
1085   current_alias_ops->cleanup (current_alias_ops);
1086 }
1087
1088 struct tree_opt_pass pass_del_pta = 
1089 {
1090   "pta",                                /* name */
1091   gate_pta,                             /* gate */
1092   delete_alias_vars,                    /* execute */
1093   NULL,                                 /* sub */
1094   NULL,                                 /* next */
1095   0,                                    /* static_pass_number */
1096   TV_TREE_PTA,                          /* tv_id */
1097   PROP_pta,                             /* properties_required */
1098   0,                                    /* properties_provided */
1099   PROP_pta,                             /* properties_destroyed */
1100   0,                                    /* todo_flags_start */
1101   0,                                    /* todo_flags_finish */
1102   0                                     /* letter */
1103 };
1104  
1105
1106 /*  Initialize points-to analysis machinery.  */
1107
1108 void
1109 init_alias_vars (void)
1110 {
1111   current_alias_ops->init (current_alias_ops);
1112   addrargs = BITMAP_XMALLOC ();
1113   VARRAY_TREE_INIT (local_alias_vars, 10, "Local alias vars");
1114   VARRAY_INT_INIT (local_alias_varnums, 10, "Local alias varnums");
1115   if ((!current_alias_ops->ip && !current_alias_ops->ip_partial)
1116       || alias_vars == NULL)
1117     VARRAY_GENERIC_PTR_INIT (alias_vars, 10, "Alias vars");
1118 }
1119
1120 /* Return true if PTR can't point to anything (i.e. it has an empty
1121    points-to set.  */
1122 bool 
1123 empty_points_to_set (tree ptr)
1124 {
1125  alias_var ptrtv;
1126   
1127 #if !FIELD_BASED
1128 #else
1129   if (TREE_CODE (ptr) == COMPONENT_REF)
1130     ptr = TREE_OPERAND (ptr, 1);
1131 #endif
1132
1133   if (DECL_P (ptr))
1134     {
1135       ptrtv = DECL_PTA_ALIASVAR (ptr);
1136       if (!ptrtv)
1137         return true;
1138     }
1139   else
1140     abort ();
1141
1142   return current_alias_ops->empty_points_to_set (current_alias_ops, ptrtv);
1143 }
1144
1145 /* Return true if PTR and VAR have the same points-to set.  */
1146
1147 bool
1148 same_points_to_set (tree ptr, tree var)
1149 {
1150   alias_var ptrtv, vartv;
1151   
1152 #if !FIELD_BASED
1153 #else
1154   if (TREE_CODE (ptr) == COMPONENT_REF)
1155     ptr = TREE_OPERAND (ptr, 1);
1156   if (TREE_CODE (var) == COMPONENT_REF)
1157     var = TREE_OPERAND (var, 1);
1158 #endif
1159
1160   if (ptr == var)
1161     return true;
1162
1163   if (DECL_P (ptr))
1164     {
1165       ptrtv = DECL_PTA_ALIASVAR (ptr);
1166       if (!ptrtv)
1167         return false;
1168     }
1169   else
1170     abort ();
1171
1172   if (DECL_P (var))
1173     {
1174       vartv = DECL_PTA_ALIASVAR (var);
1175       if (!vartv)
1176         return false;
1177     }
1178   else
1179     abort ();
1180
1181   return current_alias_ops->same_points_to_set (current_alias_ops, vartv, ptrtv);
1182 }
1183
1184 /*  Determine whether two variables (PTR and VAR) may-alias.
1185     Returns TRUE if PTR may-alias VAR.  */
1186
1187 bool
1188 ptr_may_alias_var (tree ptr, tree var)
1189 {
1190   alias_var ptrtv, vartv;
1191
1192 #if !FIELD_BASED
1193 #else
1194   if (TREE_CODE (ptr) == COMPONENT_REF)
1195     ptr = TREE_OPERAND (ptr, 1);
1196   if (TREE_CODE (var) == COMPONENT_REF)
1197     var = TREE_OPERAND (var, 1);
1198 #endif
1199
1200   if (ptr == var)
1201     return true;
1202
1203   if (DECL_P (ptr))
1204     {
1205       ptrtv = DECL_PTA_ALIASVAR (ptr);
1206       if (!ptrtv)
1207         return false;
1208     }
1209   else
1210     abort ();
1211
1212   if (DECL_P (var))
1213     {
1214       vartv = DECL_PTA_ALIASVAR (var);
1215       if (!vartv)
1216         return false;
1217     }
1218   else
1219     abort ();
1220
1221   return current_alias_ops->may_alias (current_alias_ops, ptrtv, vartv);
1222 }
1223
1224 #define MASK_POINTER(P) ((unsigned)((unsigned long)(P) & 0xffff))
1225
1226 const char *
1227 alias_get_name (tree t)
1228 {
1229   const char *name;
1230
1231 #if FIELD_BASED
1232   if (TREE_CODE (t) == FIELD_DECL)
1233     {
1234       /* First get the name of the field, then the prefix, then smash them
1235          together.  */
1236       const char *fieldname = IDENTIFIER_POINTER (DECL_NAME (t));
1237       const char *prefix = alias_get_name (DECL_CONTEXT (t));
1238       char *smashed;
1239       size_t neededlen = strlen (fieldname) + strlen (prefix) + 2;
1240       smashed = ggc_alloc (neededlen);
1241       sprintf (smashed, "%s.%s", prefix, fieldname);
1242       name = smashed;
1243
1244     }
1245   else if (TYPE_P (t))
1246     {
1247       if (TYPE_NAME (t) && IDENTIFIER_POINTER (TYPE_NAME (t)))
1248         name = IDENTIFIER_POINTER (TYPE_NAME (t));
1249       else
1250         name = "<unnamed type>";
1251     }
1252   else
1253 #endif
1254     {
1255       if (TREE_CODE (t) == FUNCTION_DECL)
1256         name = IDENTIFIER_POINTER (DECL_NAME (t));
1257       else if (TREE_CODE (t) == RESULT_DECL)
1258         name = "<return value>";
1259       else
1260         name = get_name (t);
1261     }
1262
1263   if (!name)
1264     {
1265       char *namep;
1266       /* 2 = UF
1267          4 = the masked pointer
1268          2 = the <> around it
1269          1 = the terminator.  */
1270       namep = ggc_alloc (2 + 4 + 2 + 1);
1271       sprintf (namep, "<UV%x>", MASK_POINTER (t));
1272       return namep;
1273     }
1274
1275   return name;
1276 }
1277
1278 #include "gt-tree-alias-common.h"