OSDN Git Service

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