OSDN Git Service

54badda17723fee264ce9861e951d191ec1080d4
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-alias.c
1 /* Alias analysis for trees.
2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
3    Free Software Foundation, Inc.
4    Contributed by Diego Novillo <dnovillo@redhat.com>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "tm_p.h"
28 #include "target.h"
29 #include "basic-block.h"
30 #include "timevar.h"
31 #include "ggc.h"
32 #include "langhooks.h"
33 #include "flags.h"
34 #include "function.h"
35 #include "tree-pretty-print.h"
36 #include "tree-dump.h"
37 #include "gimple.h"
38 #include "tree-flow.h"
39 #include "tree-inline.h"
40 #include "tree-pass.h"
41 #include "convert.h"
42 #include "params.h"
43 #include "vec.h"
44 #include "bitmap.h"
45 #include "vecprim.h"
46 #include "pointer-set.h"
47 #include "alloc-pool.h"
48 #include "tree-ssa-alias.h"
49
50 /* Broad overview of how alias analysis on gimple works:
51
52    Statements clobbering or using memory are linked through the
53    virtual operand factored use-def chain.  The virtual operand
54    is unique per function, its symbol is accessible via gimple_vop (cfun).
55    Virtual operands are used for efficiently walking memory statements
56    in the gimple IL and are useful for things like value-numbering as
57    a generation count for memory references.
58
59    SSA_NAME pointers may have associated points-to information
60    accessible via the SSA_NAME_PTR_INFO macro.  Flow-insensitive
61    points-to information is (re-)computed by the TODO_rebuild_alias
62    pass manager todo.  Points-to information is also used for more
63    precise tracking of call-clobbered and call-used variables and
64    related disambiguations.
65
66    This file contains functions for disambiguating memory references,
67    the so called alias-oracle and tools for walking of the gimple IL.
68
69    The main alias-oracle entry-points are
70
71    bool stmt_may_clobber_ref_p (gimple, tree)
72
73      This function queries if a statement may invalidate (parts of)
74      the memory designated by the reference tree argument.
75
76    bool ref_maybe_used_by_stmt_p (gimple, tree)
77
78      This function queries if a statement may need (parts of) the
79      memory designated by the reference tree argument.
80
81    There are variants of these functions that only handle the call
82    part of a statement, call_may_clobber_ref_p and ref_maybe_used_by_call_p.
83    Note that these do not disambiguate against a possible call lhs.
84
85    bool refs_may_alias_p (tree, tree)
86
87      This function tries to disambiguate two reference trees.
88
89    bool ptr_deref_may_alias_global_p (tree)
90
91      This function queries if dereferencing a pointer variable may
92      alias global memory.
93
94    More low-level disambiguators are available and documented in
95    this file.  Low-level disambiguators dealing with points-to
96    information are in tree-ssa-structalias.c.  */
97
98
99 /* Query statistics for the different low-level disambiguators.
100    A high-level query may trigger multiple of them.  */
101
102 static struct {
103   unsigned HOST_WIDE_INT refs_may_alias_p_may_alias;
104   unsigned HOST_WIDE_INT refs_may_alias_p_no_alias;
105   unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_may_alias;
106   unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_no_alias;
107   unsigned HOST_WIDE_INT call_may_clobber_ref_p_may_alias;
108   unsigned HOST_WIDE_INT call_may_clobber_ref_p_no_alias;
109 } alias_stats;
110
111 void
112 dump_alias_stats (FILE *s)
113 {
114   fprintf (s, "\nAlias oracle query stats:\n");
115   fprintf (s, "  refs_may_alias_p: "
116            HOST_WIDE_INT_PRINT_DEC" disambiguations, "
117            HOST_WIDE_INT_PRINT_DEC" queries\n",
118            alias_stats.refs_may_alias_p_no_alias,
119            alias_stats.refs_may_alias_p_no_alias
120            + alias_stats.refs_may_alias_p_may_alias);
121   fprintf (s, "  ref_maybe_used_by_call_p: "
122            HOST_WIDE_INT_PRINT_DEC" disambiguations, "
123            HOST_WIDE_INT_PRINT_DEC" queries\n",
124            alias_stats.ref_maybe_used_by_call_p_no_alias,
125            alias_stats.refs_may_alias_p_no_alias
126            + alias_stats.ref_maybe_used_by_call_p_may_alias);
127   fprintf (s, "  call_may_clobber_ref_p: "
128            HOST_WIDE_INT_PRINT_DEC" disambiguations, "
129            HOST_WIDE_INT_PRINT_DEC" queries\n",
130            alias_stats.call_may_clobber_ref_p_no_alias,
131            alias_stats.call_may_clobber_ref_p_no_alias
132            + alias_stats.call_may_clobber_ref_p_may_alias);
133 }
134
135
136 /* Return true, if dereferencing PTR may alias with a global variable.  */
137
138 bool
139 ptr_deref_may_alias_global_p (tree ptr)
140 {
141   struct ptr_info_def *pi;
142
143   /* If we end up with a pointer constant here that may point
144      to global memory.  */
145   if (TREE_CODE (ptr) != SSA_NAME)
146     return true;
147
148   pi = SSA_NAME_PTR_INFO (ptr);
149
150   /* If we do not have points-to information for this variable,
151      we have to punt.  */
152   if (!pi)
153     return true;
154
155   /* ???  This does not use TBAA to prune globals ptr may not access.  */
156   return pt_solution_includes_global (&pi->pt);
157 }
158
159 /* Return true if dereferencing PTR may alias DECL.
160    The caller is responsible for applying TBAA to see if PTR
161    may access DECL at all.  */
162
163 static bool
164 ptr_deref_may_alias_decl_p (tree ptr, tree decl)
165 {
166   struct ptr_info_def *pi;
167
168   /* Conversions are irrelevant for points-to information and
169      data-dependence analysis can feed us those.  */
170   STRIP_NOPS (ptr);
171
172   /* Anything we do not explicilty handle aliases.  */
173   if ((TREE_CODE (ptr) != SSA_NAME
174        && TREE_CODE (ptr) != ADDR_EXPR
175        && TREE_CODE (ptr) != POINTER_PLUS_EXPR)
176       || !POINTER_TYPE_P (TREE_TYPE (ptr))
177       || (TREE_CODE (decl) != VAR_DECL
178           && TREE_CODE (decl) != PARM_DECL
179           && TREE_CODE (decl) != RESULT_DECL))
180     return true;
181
182   /* Disregard pointer offsetting.  */
183   if (TREE_CODE (ptr) == POINTER_PLUS_EXPR)
184     {
185       do
186         {
187           ptr = TREE_OPERAND (ptr, 0);
188         }
189       while (TREE_CODE (ptr) == POINTER_PLUS_EXPR);
190       return ptr_deref_may_alias_decl_p (ptr, decl);
191     }
192
193   /* ADDR_EXPR pointers either just offset another pointer or directly
194      specify the pointed-to set.  */
195   if (TREE_CODE (ptr) == ADDR_EXPR)
196     {
197       tree base = get_base_address (TREE_OPERAND (ptr, 0));
198       if (base
199           && (TREE_CODE (base) == MEM_REF
200               || TREE_CODE (base) == TARGET_MEM_REF))
201         ptr = TREE_OPERAND (base, 0);
202       else if (base
203                && DECL_P (base))
204         return base == decl;
205       else if (base
206                && CONSTANT_CLASS_P (base))
207         return false;
208       else
209         return true;
210     }
211
212   /* Non-aliased variables can not be pointed to.  */
213   if (!may_be_aliased (decl))
214     return false;
215
216   /* If we do not have useful points-to information for this pointer
217      we cannot disambiguate anything else.  */
218   pi = SSA_NAME_PTR_INFO (ptr);
219   if (!pi)
220     return true;
221
222   return pt_solution_includes (&pi->pt, decl);
223 }
224
225 /* Return true if dereferenced PTR1 and PTR2 may alias.
226    The caller is responsible for applying TBAA to see if accesses
227    through PTR1 and PTR2 may conflict at all.  */
228
229 bool
230 ptr_derefs_may_alias_p (tree ptr1, tree ptr2)
231 {
232   struct ptr_info_def *pi1, *pi2;
233
234   /* Conversions are irrelevant for points-to information and
235      data-dependence analysis can feed us those.  */
236   STRIP_NOPS (ptr1);
237   STRIP_NOPS (ptr2);
238
239   /* Anything we do not explicilty handle aliases.  */
240   if ((TREE_CODE (ptr1) != SSA_NAME
241        && TREE_CODE (ptr1) != ADDR_EXPR
242        && TREE_CODE (ptr1) != POINTER_PLUS_EXPR)
243       || (TREE_CODE (ptr2) != SSA_NAME
244           && TREE_CODE (ptr2) != ADDR_EXPR
245           && TREE_CODE (ptr2) != POINTER_PLUS_EXPR)
246       || !POINTER_TYPE_P (TREE_TYPE (ptr1))
247       || !POINTER_TYPE_P (TREE_TYPE (ptr2)))
248     return true;
249
250   /* Disregard pointer offsetting.  */
251   if (TREE_CODE (ptr1) == POINTER_PLUS_EXPR)
252     {
253       do
254         {
255           ptr1 = TREE_OPERAND (ptr1, 0);
256         }
257       while (TREE_CODE (ptr1) == POINTER_PLUS_EXPR);
258       return ptr_derefs_may_alias_p (ptr1, ptr2);
259     }
260   if (TREE_CODE (ptr2) == POINTER_PLUS_EXPR)
261     {
262       do
263         {
264           ptr2 = TREE_OPERAND (ptr2, 0);
265         }
266       while (TREE_CODE (ptr2) == POINTER_PLUS_EXPR);
267       return ptr_derefs_may_alias_p (ptr1, ptr2);
268     }
269
270   /* ADDR_EXPR pointers either just offset another pointer or directly
271      specify the pointed-to set.  */
272   if (TREE_CODE (ptr1) == ADDR_EXPR)
273     {
274       tree base = get_base_address (TREE_OPERAND (ptr1, 0));
275       if (base
276           && (TREE_CODE (base) == MEM_REF
277               || TREE_CODE (base) == TARGET_MEM_REF))
278         ptr1 = TREE_OPERAND (base, 0);
279       else if (base
280                && DECL_P (base))
281         return ptr_deref_may_alias_decl_p (ptr2, base);
282       else
283         return true;
284     }
285   if (TREE_CODE (ptr2) == ADDR_EXPR)
286     {
287       tree base = get_base_address (TREE_OPERAND (ptr2, 0));
288       if (base
289           && (TREE_CODE (base) == MEM_REF
290               || TREE_CODE (base) == TARGET_MEM_REF))
291         ptr2 = TREE_OPERAND (base, 0);
292       else if (base
293                && DECL_P (base))
294         return ptr_deref_may_alias_decl_p (ptr1, base);
295       else
296         return true;
297     }
298
299   /* We may end up with two empty points-to solutions for two same pointers.
300      In this case we still want to say both pointers alias, so shortcut
301      that here.  */
302   if (ptr1 == ptr2)
303     return true;
304
305   /* If we do not have useful points-to information for either pointer
306      we cannot disambiguate anything else.  */
307   pi1 = SSA_NAME_PTR_INFO (ptr1);
308   pi2 = SSA_NAME_PTR_INFO (ptr2);
309   if (!pi1 || !pi2)
310     return true;
311
312   /* ???  This does not use TBAA to prune decls from the intersection
313      that not both pointers may access.  */
314   return pt_solutions_intersect (&pi1->pt, &pi2->pt);
315 }
316
317 /* Return true if dereferencing PTR may alias *REF.
318    The caller is responsible for applying TBAA to see if PTR
319    may access *REF at all.  */
320
321 static bool
322 ptr_deref_may_alias_ref_p_1 (tree ptr, ao_ref *ref)
323 {
324   tree base = ao_ref_base (ref);
325
326   if (TREE_CODE (base) == MEM_REF
327       || TREE_CODE (base) == TARGET_MEM_REF)
328     return ptr_derefs_may_alias_p (ptr, TREE_OPERAND (base, 0));
329   else if (DECL_P (base))
330     return ptr_deref_may_alias_decl_p (ptr, base);
331
332   return true;
333 }
334
335
336 /* Dump alias information on FILE.  */
337
338 void
339 dump_alias_info (FILE *file)
340 {
341   size_t i;
342   const char *funcname
343     = lang_hooks.decl_printable_name (current_function_decl, 2);
344   referenced_var_iterator rvi;
345   tree var;
346
347   fprintf (file, "\n\nAlias information for %s\n\n", funcname);
348
349   fprintf (file, "Aliased symbols\n\n");
350
351   FOR_EACH_REFERENCED_VAR (cfun, var, rvi)
352     {
353       if (may_be_aliased (var))
354         dump_variable (file, var);
355     }
356
357   fprintf (file, "\nCall clobber information\n");
358
359   fprintf (file, "\nESCAPED");
360   dump_points_to_solution (file, &cfun->gimple_df->escaped);
361
362   fprintf (file, "\n\nFlow-insensitive points-to information\n\n");
363
364   for (i = 1; i < num_ssa_names; i++)
365     {
366       tree ptr = ssa_name (i);
367       struct ptr_info_def *pi;
368
369       if (ptr == NULL_TREE
370           || SSA_NAME_IN_FREE_LIST (ptr))
371         continue;
372
373       pi = SSA_NAME_PTR_INFO (ptr);
374       if (pi)
375         dump_points_to_info_for (file, ptr);
376     }
377
378   fprintf (file, "\n");
379 }
380
381
382 /* Dump alias information on stderr.  */
383
384 DEBUG_FUNCTION void
385 debug_alias_info (void)
386 {
387   dump_alias_info (stderr);
388 }
389
390
391 /* Dump the points-to set *PT into FILE.  */
392
393 void
394 dump_points_to_solution (FILE *file, struct pt_solution *pt)
395 {
396   if (pt->anything)
397     fprintf (file, ", points-to anything");
398
399   if (pt->nonlocal)
400     fprintf (file, ", points-to non-local");
401
402   if (pt->escaped)
403     fprintf (file, ", points-to escaped");
404
405   if (pt->ipa_escaped)
406     fprintf (file, ", points-to unit escaped");
407
408   if (pt->null)
409     fprintf (file, ", points-to NULL");
410
411   if (pt->vars)
412     {
413       fprintf (file, ", points-to vars: ");
414       dump_decl_set (file, pt->vars);
415       if (pt->vars_contains_global)
416         fprintf (file, " (includes global vars)");
417     }
418 }
419
420 /* Dump points-to information for SSA_NAME PTR into FILE.  */
421
422 void
423 dump_points_to_info_for (FILE *file, tree ptr)
424 {
425   struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
426
427   print_generic_expr (file, ptr, dump_flags);
428
429   if (pi)
430     dump_points_to_solution (file, &pi->pt);
431   else
432     fprintf (file, ", points-to anything");
433
434   fprintf (file, "\n");
435 }
436
437
438 /* Dump points-to information for VAR into stderr.  */
439
440 DEBUG_FUNCTION void
441 debug_points_to_info_for (tree var)
442 {
443   dump_points_to_info_for (stderr, var);
444 }
445
446
447 /* Initializes the alias-oracle reference representation *R from REF.  */
448
449 void
450 ao_ref_init (ao_ref *r, tree ref)
451 {
452   r->ref = ref;
453   r->base = NULL_TREE;
454   r->offset = 0;
455   r->size = -1;
456   r->max_size = -1;
457   r->ref_alias_set = -1;
458   r->base_alias_set = -1;
459   r->volatile_p = ref ? TREE_THIS_VOLATILE (ref) : false;
460 }
461
462 /* Returns the base object of the memory reference *REF.  */
463
464 tree
465 ao_ref_base (ao_ref *ref)
466 {
467   if (ref->base)
468     return ref->base;
469   ref->base = get_ref_base_and_extent (ref->ref, &ref->offset, &ref->size,
470                                        &ref->max_size);
471   return ref->base;
472 }
473
474 /* Returns the base object alias set of the memory reference *REF.  */
475
476 static alias_set_type
477 ao_ref_base_alias_set (ao_ref *ref)
478 {
479   tree base_ref;
480   if (ref->base_alias_set != -1)
481     return ref->base_alias_set;
482   if (!ref->ref)
483     return 0;
484   base_ref = ref->ref;
485   while (handled_component_p (base_ref))
486     base_ref = TREE_OPERAND (base_ref, 0);
487   ref->base_alias_set = get_alias_set (base_ref);
488   return ref->base_alias_set;
489 }
490
491 /* Returns the reference alias set of the memory reference *REF.  */
492
493 alias_set_type
494 ao_ref_alias_set (ao_ref *ref)
495 {
496   if (ref->ref_alias_set != -1)
497     return ref->ref_alias_set;
498   ref->ref_alias_set = get_alias_set (ref->ref);
499   return ref->ref_alias_set;
500 }
501
502 /* Init an alias-oracle reference representation from a gimple pointer
503    PTR and a gimple size SIZE in bytes.  If SIZE is NULL_TREE the the
504    size is assumed to be unknown.  The access is assumed to be only
505    to or after of the pointer target, not before it.  */
506
507 void
508 ao_ref_init_from_ptr_and_size (ao_ref *ref, tree ptr, tree size)
509 {
510   HOST_WIDE_INT t1, t2;
511   ref->ref = NULL_TREE;
512   if (TREE_CODE (ptr) == ADDR_EXPR)
513     ref->base = get_ref_base_and_extent (TREE_OPERAND (ptr, 0),
514                                          &ref->offset, &t1, &t2);
515   else
516     {
517       ref->base = build2 (MEM_REF, char_type_node,
518                           ptr, null_pointer_node);
519       ref->offset = 0;
520     }
521   if (size
522       && host_integerp (size, 0)
523       && TREE_INT_CST_LOW (size) * 8 / 8 == TREE_INT_CST_LOW (size))
524     ref->max_size = ref->size = TREE_INT_CST_LOW (size) * 8;
525   else
526     ref->max_size = ref->size = -1;
527   ref->ref_alias_set = 0;
528   ref->base_alias_set = 0;
529   ref->volatile_p = false;
530 }
531
532 /* Return 1 if TYPE1 and TYPE2 are to be considered equivalent for the
533    purpose of TBAA.  Return 0 if they are distinct and -1 if we cannot
534    decide.  */
535
536 static inline int
537 same_type_for_tbaa (tree type1, tree type2)
538 {
539   type1 = TYPE_MAIN_VARIANT (type1);
540   type2 = TYPE_MAIN_VARIANT (type2);
541
542   /* If we would have to do structural comparison bail out.  */
543   if (TYPE_STRUCTURAL_EQUALITY_P (type1)
544       || TYPE_STRUCTURAL_EQUALITY_P (type2))
545     return -1;
546
547   /* Compare the canonical types.  */
548   if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
549     return 1;
550
551   /* ??? Array types are not properly unified in all cases as we have
552      spurious changes in the index types for example.  Removing this
553      causes all sorts of problems with the Fortran frontend.  */
554   if (TREE_CODE (type1) == ARRAY_TYPE
555       && TREE_CODE (type2) == ARRAY_TYPE)
556     return -1;
557
558   /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
559      object of one of its constrained subtypes, e.g. when a function with an
560      unconstrained parameter passed by reference is called on an object and
561      inlined.  But, even in the case of a fixed size, type and subtypes are
562      not equivalent enough as to share the same TYPE_CANONICAL, since this
563      would mean that conversions between them are useless, whereas they are
564      not (e.g. type and subtypes can have different modes).  So, in the end,
565      they are only guaranteed to have the same alias set.  */
566   if (get_alias_set (type1) == get_alias_set (type2))
567     return -1;
568
569   /* The types are known to be not equal.  */
570   return 0;
571 }
572
573 /* Determine if the two component references REF1 and REF2 which are
574    based on access types TYPE1 and TYPE2 and of which at least one is based
575    on an indirect reference may alias.  REF2 is the only one that can
576    be a decl in which case REF2_IS_DECL is true.
577    REF1_ALIAS_SET, BASE1_ALIAS_SET, REF2_ALIAS_SET and BASE2_ALIAS_SET
578    are the respective alias sets.  */
579
580 static bool
581 aliasing_component_refs_p (tree ref1,
582                            alias_set_type ref1_alias_set,
583                            alias_set_type base1_alias_set,
584                            HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1,
585                            tree ref2,
586                            alias_set_type ref2_alias_set,
587                            alias_set_type base2_alias_set,
588                            HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2,
589                            bool ref2_is_decl)
590 {
591   /* If one reference is a component references through pointers try to find a
592      common base and apply offset based disambiguation.  This handles
593      for example
594        struct A { int i; int j; } *q;
595        struct B { struct A a; int k; } *p;
596      disambiguating q->i and p->a.j.  */
597   tree base1, base2;
598   tree type1, type2;
599   tree *refp;
600   int same_p;
601
602   /* Choose bases and base types to search for.  */
603   base1 = ref1;
604   while (handled_component_p (base1))
605     base1 = TREE_OPERAND (base1, 0);
606   type1 = TREE_TYPE (base1);
607   base2 = ref2;
608   while (handled_component_p (base2))
609     base2 = TREE_OPERAND (base2, 0);
610   type2 = TREE_TYPE (base2);
611
612   /* Now search for the type1 in the access path of ref2.  This
613      would be a common base for doing offset based disambiguation on.  */
614   refp = &ref2;
615   while (handled_component_p (*refp)
616          && same_type_for_tbaa (TREE_TYPE (*refp), type1) == 0)
617     refp = &TREE_OPERAND (*refp, 0);
618   same_p = same_type_for_tbaa (TREE_TYPE (*refp), type1);
619   /* If we couldn't compare types we have to bail out.  */
620   if (same_p == -1)
621     return true;
622   else if (same_p == 1)
623     {
624       HOST_WIDE_INT offadj, sztmp, msztmp;
625       get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
626       offset2 -= offadj;
627       get_ref_base_and_extent (base1, &offadj, &sztmp, &msztmp);
628       offset1 -= offadj;
629       return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
630     }
631   /* If we didn't find a common base, try the other way around.  */
632   refp = &ref1;
633   while (handled_component_p (*refp)
634          && same_type_for_tbaa (TREE_TYPE (*refp), type2) == 0)
635     refp = &TREE_OPERAND (*refp, 0);
636   same_p = same_type_for_tbaa (TREE_TYPE (*refp), type2);
637   /* If we couldn't compare types we have to bail out.  */
638   if (same_p == -1)
639     return true;
640   else if (same_p == 1)
641     {
642       HOST_WIDE_INT offadj, sztmp, msztmp;
643       get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
644       offset1 -= offadj;
645       get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp);
646       offset2 -= offadj;
647       return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
648     }
649
650   /* If we have two type access paths B1.path1 and B2.path2 they may
651      only alias if either B1 is in B2.path2 or B2 is in B1.path1.
652      But we can still have a path that goes B1.path1...B2.path2 with
653      a part that we do not see.  So we can only disambiguate now
654      if there is no B2 in the tail of path1 and no B1 on the
655      tail of path2.  */
656   if (base1_alias_set == ref2_alias_set
657       || alias_set_subset_of (base1_alias_set, ref2_alias_set))
658     return true;
659   /* If this is ptr vs. decl then we know there is no ptr ... decl path.  */
660   if (!ref2_is_decl)
661     return (base2_alias_set == ref1_alias_set
662             || alias_set_subset_of (base2_alias_set, ref1_alias_set));
663   return false;
664 }
665
666 /* Return true if two memory references based on the variables BASE1
667    and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
668    [OFFSET2, OFFSET2 + MAX_SIZE2) may alias.  */
669
670 static bool
671 decl_refs_may_alias_p (tree base1,
672                        HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1,
673                        tree base2,
674                        HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2)
675 {
676   gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
677
678   /* If both references are based on different variables, they cannot alias.  */
679   if (base1 != base2)
680     return false;
681
682   /* If both references are based on the same variable, they cannot alias if
683      the accesses do not overlap.  */
684   return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
685 }
686
687 /* Return true if an indirect reference based on *PTR1 constrained
688    to [OFFSET1, OFFSET1 + MAX_SIZE1) may alias a variable based on BASE2
689    constrained to [OFFSET2, OFFSET2 + MAX_SIZE2).  *PTR1 and BASE2 have
690    the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
691    in which case they are computed on-demand.  REF1 and REF2
692    if non-NULL are the complete memory reference trees.  */
693
694 static bool
695 indirect_ref_may_alias_decl_p (tree ref1 ATTRIBUTE_UNUSED, tree base1,
696                                HOST_WIDE_INT offset1,
697                                HOST_WIDE_INT max_size1 ATTRIBUTE_UNUSED,
698                                alias_set_type ref1_alias_set,
699                                alias_set_type base1_alias_set,
700                                tree ref2 ATTRIBUTE_UNUSED, tree base2,
701                                HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2,
702                                alias_set_type ref2_alias_set,
703                                alias_set_type base2_alias_set, bool tbaa_p)
704 {
705   tree ptr1;
706   tree ptrtype1, dbase2;
707   HOST_WIDE_INT offset1p = offset1, offset2p = offset2;
708   HOST_WIDE_INT doffset1, doffset2;
709   double_int moff;
710
711   gcc_checking_assert ((TREE_CODE (base1) == MEM_REF
712                         || TREE_CODE (base1) == TARGET_MEM_REF)
713                        && DECL_P (base2));
714
715   ptr1 = TREE_OPERAND (base1, 0);
716
717   /* The offset embedded in MEM_REFs can be negative.  Bias them
718      so that the resulting offset adjustment is positive.  */
719   moff = mem_ref_offset (base1);
720   moff = double_int_lshift (moff,
721                             BITS_PER_UNIT == 8
722                             ? 3 : exact_log2 (BITS_PER_UNIT),
723                             HOST_BITS_PER_DOUBLE_INT, true);
724   if (double_int_negative_p (moff))
725     offset2p += double_int_neg (moff).low;
726   else
727     offset1p += moff.low;
728
729   /* If only one reference is based on a variable, they cannot alias if
730      the pointer access is beyond the extent of the variable access.
731      (the pointer base cannot validly point to an offset less than zero
732      of the variable).
733      ???  IVOPTs creates bases that do not honor this restriction,
734      so do not apply this optimization for TARGET_MEM_REFs.  */
735   if (TREE_CODE (base1) != TARGET_MEM_REF
736       && !ranges_overlap_p (MAX (0, offset1p), -1, offset2p, max_size2))
737     return false;
738   /* They also cannot alias if the pointer may not point to the decl.  */
739   if (!ptr_deref_may_alias_decl_p (ptr1, base2))
740     return false;
741
742   /* Disambiguations that rely on strict aliasing rules follow.  */
743   if (!flag_strict_aliasing || !tbaa_p)
744     return true;
745
746   ptrtype1 = TREE_TYPE (TREE_OPERAND (base1, 1));
747
748   /* If the alias set for a pointer access is zero all bets are off.  */
749   if (base1_alias_set == -1)
750     base1_alias_set = get_deref_alias_set (ptrtype1);
751   if (base1_alias_set == 0)
752     return true;
753   if (base2_alias_set == -1)
754     base2_alias_set = get_alias_set (base2);
755
756   /* When we are trying to disambiguate an access with a pointer dereference
757      as base versus one with a decl as base we can use both the size
758      of the decl and its dynamic type for extra disambiguation.
759      ???  We do not know anything about the dynamic type of the decl
760      other than that its alias-set contains base2_alias_set as a subset
761      which does not help us here.  */
762   /* As we know nothing useful about the dynamic type of the decl just
763      use the usual conflict check rather than a subset test.
764      ???  We could introduce -fvery-strict-aliasing when the language
765      does not allow decls to have a dynamic type that differs from their
766      static type.  Then we can check 
767      !alias_set_subset_of (base1_alias_set, base2_alias_set) instead.  */
768   if (base1_alias_set != base2_alias_set
769       && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
770     return false;
771   /* If the size of the access relevant for TBAA through the pointer
772      is bigger than the size of the decl we can't possibly access the
773      decl via that pointer.  */
774   if (DECL_SIZE (base2) && COMPLETE_TYPE_P (TREE_TYPE (ptrtype1))
775       && TREE_CODE (DECL_SIZE (base2)) == INTEGER_CST
776       && TREE_CODE (TYPE_SIZE (TREE_TYPE (ptrtype1))) == INTEGER_CST
777       /* ???  This in turn may run afoul when a decl of type T which is
778          a member of union type U is accessed through a pointer to
779          type U and sizeof T is smaller than sizeof U.  */
780       && TREE_CODE (TREE_TYPE (ptrtype1)) != UNION_TYPE
781       && TREE_CODE (TREE_TYPE (ptrtype1)) != QUAL_UNION_TYPE
782       && tree_int_cst_lt (DECL_SIZE (base2), TYPE_SIZE (TREE_TYPE (ptrtype1))))
783     return false;
784
785   if (!ref2)
786     return true;
787
788   /* If the decl is accessed via a MEM_REF, reconstruct the base
789      we can use for TBAA and an appropriately adjusted offset.  */
790   dbase2 = ref2;
791   while (handled_component_p (dbase2))
792     dbase2 = TREE_OPERAND (dbase2, 0);
793   doffset1 = offset1;
794   doffset2 = offset2;
795   if (TREE_CODE (dbase2) == MEM_REF
796       || TREE_CODE (dbase2) == TARGET_MEM_REF)
797     {
798       double_int moff = mem_ref_offset (dbase2);
799       moff = double_int_lshift (moff,
800                                 BITS_PER_UNIT == 8
801                                 ? 3 : exact_log2 (BITS_PER_UNIT),
802                                 HOST_BITS_PER_DOUBLE_INT, true);
803       if (double_int_negative_p (moff))
804         doffset1 -= double_int_neg (moff).low;
805       else
806         doffset2 -= moff.low;
807     }
808
809   /* If either reference is view-converted, give up now.  */
810   if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) != 1
811       || same_type_for_tbaa (TREE_TYPE (dbase2),
812                              TREE_TYPE (reference_alias_ptr_type (dbase2))) != 1)
813     return true;
814
815   /* If both references are through the same type, they do not alias
816      if the accesses do not overlap.  This does extra disambiguation
817      for mixed/pointer accesses but requires strict aliasing.
818      For MEM_REFs we require that the component-ref offset we computed
819      is relative to the start of the type which we ensure by
820      comparing rvalue and access type and disregarding the constant
821      pointer offset.  */
822   if ((TREE_CODE (base1) != TARGET_MEM_REF
823        || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
824       && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (dbase2)) == 1)
825     return ranges_overlap_p (doffset1, max_size1, doffset2, max_size2);
826
827   /* Do access-path based disambiguation.  */
828   if (ref1 && ref2
829       && (handled_component_p (ref1) || handled_component_p (ref2)))
830     return aliasing_component_refs_p (ref1,
831                                       ref1_alias_set, base1_alias_set,
832                                       offset1, max_size1,
833                                       ref2,
834                                       ref2_alias_set, base2_alias_set,
835                                       offset2, max_size2, true);
836
837   return true;
838 }
839
840 /* Return true if two indirect references based on *PTR1
841    and *PTR2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
842    [OFFSET2, OFFSET2 + MAX_SIZE2) may alias.  *PTR1 and *PTR2 have
843    the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
844    in which case they are computed on-demand.  REF1 and REF2
845    if non-NULL are the complete memory reference trees. */
846
847 static bool
848 indirect_refs_may_alias_p (tree ref1 ATTRIBUTE_UNUSED, tree base1,
849                            HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1,
850                            alias_set_type ref1_alias_set,
851                            alias_set_type base1_alias_set,
852                            tree ref2 ATTRIBUTE_UNUSED, tree base2,
853                            HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2,
854                            alias_set_type ref2_alias_set,
855                            alias_set_type base2_alias_set, bool tbaa_p)
856 {
857   tree ptr1;
858   tree ptr2;
859   tree ptrtype1, ptrtype2;
860
861   gcc_checking_assert ((TREE_CODE (base1) == MEM_REF
862                         || TREE_CODE (base1) == TARGET_MEM_REF)
863                        && (TREE_CODE (base2) == MEM_REF
864                            || TREE_CODE (base2) == TARGET_MEM_REF));
865
866   ptr1 = TREE_OPERAND (base1, 0);
867   ptr2 = TREE_OPERAND (base2, 0);
868
869   /* If both bases are based on pointers they cannot alias if they may not
870      point to the same memory object or if they point to the same object
871      and the accesses do not overlap.  */
872   if ((!cfun || gimple_in_ssa_p (cfun))
873       && operand_equal_p (ptr1, ptr2, 0)
874       && (((TREE_CODE (base1) != TARGET_MEM_REF
875             || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
876            && (TREE_CODE (base2) != TARGET_MEM_REF
877                || (!TMR_INDEX (base2) && !TMR_INDEX2 (base2))))
878           || (TREE_CODE (base1) == TARGET_MEM_REF
879               && TREE_CODE (base2) == TARGET_MEM_REF
880               && (TMR_STEP (base1) == TMR_STEP (base2)
881                   || (TMR_STEP (base1) && TMR_STEP (base2)
882                       && operand_equal_p (TMR_STEP (base1),
883                                           TMR_STEP (base2), 0)))
884               && (TMR_INDEX (base1) == TMR_INDEX (base2)
885                   || (TMR_INDEX (base1) && TMR_INDEX (base2)
886                       && operand_equal_p (TMR_INDEX (base1),
887                                           TMR_INDEX (base2), 0)))
888               && (TMR_INDEX2 (base1) == TMR_INDEX2 (base2)
889                   || (TMR_INDEX2 (base1) && TMR_INDEX2 (base2)
890                       && operand_equal_p (TMR_INDEX2 (base1),
891                                           TMR_INDEX2 (base2), 0))))))
892     {
893       double_int moff;
894       /* The offset embedded in MEM_REFs can be negative.  Bias them
895          so that the resulting offset adjustment is positive.  */
896       moff = mem_ref_offset (base1);
897       moff = double_int_lshift (moff,
898                                 BITS_PER_UNIT == 8
899                                 ? 3 : exact_log2 (BITS_PER_UNIT),
900                                 HOST_BITS_PER_DOUBLE_INT, true);
901       if (double_int_negative_p (moff))
902         offset2 += double_int_neg (moff).low;
903       else
904         offset1 += moff.low;
905       moff = mem_ref_offset (base2);
906       moff = double_int_lshift (moff,
907                                 BITS_PER_UNIT == 8
908                                 ? 3 : exact_log2 (BITS_PER_UNIT),
909                                 HOST_BITS_PER_DOUBLE_INT, true);
910       if (double_int_negative_p (moff))
911         offset1 += double_int_neg (moff).low;
912       else
913         offset2 += moff.low;
914       return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
915     }
916   if (!ptr_derefs_may_alias_p (ptr1, ptr2))
917     return false;
918
919   /* Disambiguations that rely on strict aliasing rules follow.  */
920   if (!flag_strict_aliasing || !tbaa_p)
921     return true;
922
923   ptrtype1 = TREE_TYPE (TREE_OPERAND (base1, 1));
924   ptrtype2 = TREE_TYPE (TREE_OPERAND (base2, 1));
925
926   /* If the alias set for a pointer access is zero all bets are off.  */
927   if (base1_alias_set == -1)
928     base1_alias_set = get_deref_alias_set (ptrtype1);
929   if (base1_alias_set == 0)
930     return true;
931   if (base2_alias_set == -1)
932     base2_alias_set = get_deref_alias_set (ptrtype2);
933   if (base2_alias_set == 0)
934     return true;
935
936   /* If both references are through the same type, they do not alias
937      if the accesses do not overlap.  This does extra disambiguation
938      for mixed/pointer accesses but requires strict aliasing.  */
939   if ((TREE_CODE (base1) != TARGET_MEM_REF
940        || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
941       && (TREE_CODE (base2) != TARGET_MEM_REF
942           || (!TMR_INDEX (base2) && !TMR_INDEX2 (base2)))
943       && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) == 1
944       && same_type_for_tbaa (TREE_TYPE (base2), TREE_TYPE (ptrtype2)) == 1
945       && same_type_for_tbaa (TREE_TYPE (ptrtype1),
946                              TREE_TYPE (ptrtype2)) == 1)
947     return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
948
949   /* Do type-based disambiguation.  */
950   if (base1_alias_set != base2_alias_set
951       && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
952     return false;
953
954   /* Do access-path based disambiguation.  */
955   if (ref1 && ref2
956       && (handled_component_p (ref1) || handled_component_p (ref2))
957       && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) == 1
958       && same_type_for_tbaa (TREE_TYPE (base2), TREE_TYPE (ptrtype2)) == 1)
959     return aliasing_component_refs_p (ref1,
960                                       ref1_alias_set, base1_alias_set,
961                                       offset1, max_size1,
962                                       ref2,
963                                       ref2_alias_set, base2_alias_set,
964                                       offset2, max_size2, false);
965
966   return true;
967 }
968
969 /* Return true, if the two memory references REF1 and REF2 may alias.  */
970
971 bool
972 refs_may_alias_p_1 (ao_ref *ref1, ao_ref *ref2, bool tbaa_p)
973 {
974   tree base1, base2;
975   HOST_WIDE_INT offset1 = 0, offset2 = 0;
976   HOST_WIDE_INT max_size1 = -1, max_size2 = -1;
977   bool var1_p, var2_p, ind1_p, ind2_p;
978
979   gcc_checking_assert ((!ref1->ref
980                         || TREE_CODE (ref1->ref) == SSA_NAME
981                         || DECL_P (ref1->ref)
982                         || TREE_CODE (ref1->ref) == STRING_CST
983                         || handled_component_p (ref1->ref)
984                         || TREE_CODE (ref1->ref) == MEM_REF
985                         || TREE_CODE (ref1->ref) == TARGET_MEM_REF)
986                        && (!ref2->ref
987                            || TREE_CODE (ref2->ref) == SSA_NAME
988                            || DECL_P (ref2->ref)
989                            || TREE_CODE (ref2->ref) == STRING_CST
990                            || handled_component_p (ref2->ref)
991                            || TREE_CODE (ref2->ref) == MEM_REF
992                            || TREE_CODE (ref2->ref) == TARGET_MEM_REF));
993
994   /* Decompose the references into their base objects and the access.  */
995   base1 = ao_ref_base (ref1);
996   offset1 = ref1->offset;
997   max_size1 = ref1->max_size;
998   base2 = ao_ref_base (ref2);
999   offset2 = ref2->offset;
1000   max_size2 = ref2->max_size;
1001
1002   /* We can end up with registers or constants as bases for example from
1003      *D.1663_44 = VIEW_CONVERT_EXPR<struct DB_LSN>(__tmp$B0F64_59);
1004      which is seen as a struct copy.  */
1005   if (TREE_CODE (base1) == SSA_NAME
1006       || TREE_CODE (base1) == CONST_DECL
1007       || TREE_CODE (base1) == CONSTRUCTOR
1008       || TREE_CODE (base1) == ADDR_EXPR
1009       || CONSTANT_CLASS_P (base1)
1010       || TREE_CODE (base2) == SSA_NAME
1011       || TREE_CODE (base2) == CONST_DECL
1012       || TREE_CODE (base2) == CONSTRUCTOR
1013       || TREE_CODE (base2) == ADDR_EXPR
1014       || CONSTANT_CLASS_P (base2))
1015     return false;
1016
1017   /* We can end up refering to code via function and label decls.
1018      As we likely do not properly track code aliases conservatively
1019      bail out.  */
1020   if (TREE_CODE (base1) == FUNCTION_DECL
1021       || TREE_CODE (base1) == LABEL_DECL
1022       || TREE_CODE (base2) == FUNCTION_DECL
1023       || TREE_CODE (base2) == LABEL_DECL)
1024     return true;
1025
1026   /* Two volatile accesses always conflict.  */
1027   if (ref1->volatile_p
1028       && ref2->volatile_p)
1029     return true;
1030
1031   /* Defer to simple offset based disambiguation if we have
1032      references based on two decls.  Do this before defering to
1033      TBAA to handle must-alias cases in conformance with the
1034      GCC extension of allowing type-punning through unions.  */
1035   var1_p = DECL_P (base1);
1036   var2_p = DECL_P (base2);
1037   if (var1_p && var2_p)
1038     return decl_refs_may_alias_p (base1, offset1, max_size1,
1039                                   base2, offset2, max_size2);
1040
1041   ind1_p = (TREE_CODE (base1) == MEM_REF
1042             || TREE_CODE (base1) == TARGET_MEM_REF);
1043   ind2_p = (TREE_CODE (base2) == MEM_REF
1044             || TREE_CODE (base2) == TARGET_MEM_REF);
1045
1046   /* Canonicalize the pointer-vs-decl case.  */
1047   if (ind1_p && var2_p)
1048     {
1049       HOST_WIDE_INT tmp1;
1050       tree tmp2;
1051       ao_ref *tmp3;
1052       tmp1 = offset1; offset1 = offset2; offset2 = tmp1;
1053       tmp1 = max_size1; max_size1 = max_size2; max_size2 = tmp1;
1054       tmp2 = base1; base1 = base2; base2 = tmp2;
1055       tmp3 = ref1; ref1 = ref2; ref2 = tmp3;
1056       var1_p = true;
1057       ind1_p = false;
1058       var2_p = false;
1059       ind2_p = true;
1060     }
1061
1062   /* First defer to TBAA if possible.  */
1063   if (tbaa_p
1064       && flag_strict_aliasing
1065       && !alias_sets_conflict_p (ao_ref_alias_set (ref1),
1066                                  ao_ref_alias_set (ref2)))
1067     return false;
1068
1069   /* Dispatch to the pointer-vs-decl or pointer-vs-pointer disambiguators.  */
1070   if (var1_p && ind2_p)
1071     return indirect_ref_may_alias_decl_p (ref2->ref, base2,
1072                                           offset2, max_size2,
1073                                           ao_ref_alias_set (ref2), -1,
1074                                           ref1->ref, base1,
1075                                           offset1, max_size1,
1076                                           ao_ref_alias_set (ref1),
1077                                           ao_ref_base_alias_set (ref1),
1078                                           tbaa_p);
1079   else if (ind1_p && ind2_p)
1080     return indirect_refs_may_alias_p (ref1->ref, base1,
1081                                       offset1, max_size1,
1082                                       ao_ref_alias_set (ref1), -1,
1083                                       ref2->ref, base2,
1084                                       offset2, max_size2,
1085                                       ao_ref_alias_set (ref2), -1,
1086                                       tbaa_p);
1087
1088   /* We really do not want to end up here, but returning true is safe.  */
1089 #ifdef ENABLE_CHECKING
1090   gcc_unreachable ();
1091 #else
1092   return true;
1093 #endif
1094 }
1095
1096 bool
1097 refs_may_alias_p (tree ref1, tree ref2)
1098 {
1099   ao_ref r1, r2;
1100   bool res;
1101   ao_ref_init (&r1, ref1);
1102   ao_ref_init (&r2, ref2);
1103   res = refs_may_alias_p_1 (&r1, &r2, true);
1104   if (res)
1105     ++alias_stats.refs_may_alias_p_may_alias;
1106   else
1107     ++alias_stats.refs_may_alias_p_no_alias;
1108   return res;
1109 }
1110
1111 /* Returns true if there is a anti-dependence for the STORE that
1112    executes after the LOAD.  */
1113
1114 bool
1115 refs_anti_dependent_p (tree load, tree store)
1116 {
1117   ao_ref r1, r2;
1118   ao_ref_init (&r1, load);
1119   ao_ref_init (&r2, store);
1120   return refs_may_alias_p_1 (&r1, &r2, false);
1121 }
1122
1123 /* Returns true if there is a output dependence for the stores
1124    STORE1 and STORE2.  */
1125
1126 bool
1127 refs_output_dependent_p (tree store1, tree store2)
1128 {
1129   ao_ref r1, r2;
1130   ao_ref_init (&r1, store1);
1131   ao_ref_init (&r2, store2);
1132   return refs_may_alias_p_1 (&r1, &r2, false);
1133 }
1134
1135 /* If the call CALL may use the memory reference REF return true,
1136    otherwise return false.  */
1137
1138 static bool
1139 ref_maybe_used_by_call_p_1 (gimple call, ao_ref *ref)
1140 {
1141   tree base, callee;
1142   unsigned i;
1143   int flags = gimple_call_flags (call);
1144
1145   /* Const functions without a static chain do not implicitly use memory.  */
1146   if (!gimple_call_chain (call)
1147       && (flags & (ECF_CONST|ECF_NOVOPS)))
1148     goto process_args;
1149
1150   base = ao_ref_base (ref);
1151   if (!base)
1152     return true;
1153
1154   /* A call that is not without side-effects might involve volatile
1155      accesses and thus conflicts with all other volatile accesses.  */
1156   if (ref->volatile_p)
1157     return true;
1158
1159   /* If the reference is based on a decl that is not aliased the call
1160      cannot possibly use it.  */
1161   if (DECL_P (base)
1162       && !may_be_aliased (base)
1163       /* But local statics can be used through recursion.  */
1164       && !is_global_var (base))
1165     goto process_args;
1166
1167   callee = gimple_call_fndecl (call);
1168
1169   /* Handle those builtin functions explicitly that do not act as
1170      escape points.  See tree-ssa-structalias.c:find_func_aliases
1171      for the list of builtins we might need to handle here.  */
1172   if (callee != NULL_TREE
1173       && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
1174     switch (DECL_FUNCTION_CODE (callee))
1175       {
1176         /* All the following functions read memory pointed to by
1177            their second argument.  strcat/strncat additionally
1178            reads memory pointed to by the first argument.  */
1179         case BUILT_IN_STRCAT:
1180         case BUILT_IN_STRNCAT:
1181           {
1182             ao_ref dref;
1183             ao_ref_init_from_ptr_and_size (&dref,
1184                                            gimple_call_arg (call, 0),
1185                                            NULL_TREE);
1186             if (refs_may_alias_p_1 (&dref, ref, false))
1187               return true;
1188           }
1189           /* FALLTHRU */
1190         case BUILT_IN_STRCPY:
1191         case BUILT_IN_STRNCPY:
1192         case BUILT_IN_MEMCPY:
1193         case BUILT_IN_MEMMOVE:
1194         case BUILT_IN_MEMPCPY:
1195         case BUILT_IN_STPCPY:
1196         case BUILT_IN_STPNCPY:
1197         case BUILT_IN_TM_MEMCPY:
1198         case BUILT_IN_TM_MEMMOVE:
1199           {
1200             ao_ref dref;
1201             tree size = NULL_TREE;
1202             if (gimple_call_num_args (call) == 3)
1203               size = gimple_call_arg (call, 2);
1204             ao_ref_init_from_ptr_and_size (&dref,
1205                                            gimple_call_arg (call, 1),
1206                                            size);
1207             return refs_may_alias_p_1 (&dref, ref, false);
1208           }
1209         case BUILT_IN_STRCAT_CHK:
1210         case BUILT_IN_STRNCAT_CHK:
1211           {
1212             ao_ref dref;
1213             ao_ref_init_from_ptr_and_size (&dref,
1214                                            gimple_call_arg (call, 0),
1215                                            NULL_TREE);
1216             if (refs_may_alias_p_1 (&dref, ref, false))
1217               return true;
1218           }
1219           /* FALLTHRU */
1220         case BUILT_IN_STRCPY_CHK:
1221         case BUILT_IN_STRNCPY_CHK:
1222         case BUILT_IN_MEMCPY_CHK:
1223         case BUILT_IN_MEMMOVE_CHK:
1224         case BUILT_IN_MEMPCPY_CHK:
1225         case BUILT_IN_STPCPY_CHK:
1226         case BUILT_IN_STPNCPY_CHK:
1227           {
1228             ao_ref dref;
1229             tree size = NULL_TREE;
1230             if (gimple_call_num_args (call) == 4)
1231               size = gimple_call_arg (call, 2);
1232             ao_ref_init_from_ptr_and_size (&dref,
1233                                            gimple_call_arg (call, 1),
1234                                            size);
1235             return refs_may_alias_p_1 (&dref, ref, false);
1236           }
1237         case BUILT_IN_BCOPY:
1238           {
1239             ao_ref dref;
1240             tree size = gimple_call_arg (call, 2);
1241             ao_ref_init_from_ptr_and_size (&dref,
1242                                            gimple_call_arg (call, 0),
1243                                            size);
1244             return refs_may_alias_p_1 (&dref, ref, false);
1245           }
1246
1247         /* The following functions read memory pointed to by their
1248            first argument.  */
1249         CASE_BUILT_IN_TM_LOAD (1):
1250         CASE_BUILT_IN_TM_LOAD (2):
1251         CASE_BUILT_IN_TM_LOAD (4):
1252         CASE_BUILT_IN_TM_LOAD (8):
1253         CASE_BUILT_IN_TM_LOAD (FLOAT):
1254         CASE_BUILT_IN_TM_LOAD (DOUBLE):
1255         CASE_BUILT_IN_TM_LOAD (LDOUBLE):
1256         CASE_BUILT_IN_TM_LOAD (M64):
1257         CASE_BUILT_IN_TM_LOAD (M128):
1258         CASE_BUILT_IN_TM_LOAD (M256):
1259         case BUILT_IN_TM_LOG:
1260         case BUILT_IN_TM_LOG_1:
1261         case BUILT_IN_TM_LOG_2:
1262         case BUILT_IN_TM_LOG_4:
1263         case BUILT_IN_TM_LOG_8:
1264         case BUILT_IN_TM_LOG_FLOAT:
1265         case BUILT_IN_TM_LOG_DOUBLE:
1266         case BUILT_IN_TM_LOG_LDOUBLE:
1267         case BUILT_IN_TM_LOG_M64:
1268         case BUILT_IN_TM_LOG_M128:
1269         case BUILT_IN_TM_LOG_M256:
1270           return ptr_deref_may_alias_ref_p_1 (gimple_call_arg (call, 0), ref);
1271
1272         /* These read memory pointed to by the first argument.  */
1273         case BUILT_IN_STRDUP:
1274         case BUILT_IN_STRNDUP:
1275           {
1276             ao_ref dref;
1277             tree size = NULL_TREE;
1278             if (gimple_call_num_args (call) == 2)
1279               size = gimple_call_arg (call, 1);
1280             ao_ref_init_from_ptr_and_size (&dref,
1281                                            gimple_call_arg (call, 0),
1282                                            size);
1283             return refs_may_alias_p_1 (&dref, ref, false);
1284           }
1285         /* The following builtins do not read from memory.  */
1286         case BUILT_IN_FREE:
1287         case BUILT_IN_MALLOC:
1288         case BUILT_IN_CALLOC:
1289         case BUILT_IN_ALLOCA:
1290         case BUILT_IN_ALLOCA_WITH_ALIGN:
1291         case BUILT_IN_STACK_SAVE:
1292         case BUILT_IN_STACK_RESTORE:
1293         case BUILT_IN_MEMSET:
1294         case BUILT_IN_TM_MEMSET:
1295         case BUILT_IN_MEMSET_CHK:
1296         case BUILT_IN_FREXP:
1297         case BUILT_IN_FREXPF:
1298         case BUILT_IN_FREXPL:
1299         case BUILT_IN_GAMMA_R:
1300         case BUILT_IN_GAMMAF_R:
1301         case BUILT_IN_GAMMAL_R:
1302         case BUILT_IN_LGAMMA_R:
1303         case BUILT_IN_LGAMMAF_R:
1304         case BUILT_IN_LGAMMAL_R:
1305         case BUILT_IN_MODF:
1306         case BUILT_IN_MODFF:
1307         case BUILT_IN_MODFL:
1308         case BUILT_IN_REMQUO:
1309         case BUILT_IN_REMQUOF:
1310         case BUILT_IN_REMQUOL:
1311         case BUILT_IN_SINCOS:
1312         case BUILT_IN_SINCOSF:
1313         case BUILT_IN_SINCOSL:
1314         case BUILT_IN_ASSUME_ALIGNED:
1315         case BUILT_IN_VA_END:
1316           return false;
1317         /* __sync_* builtins and some OpenMP builtins act as threading
1318            barriers.  */
1319 #undef DEF_SYNC_BUILTIN
1320 #define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
1321 #include "sync-builtins.def"
1322 #undef DEF_SYNC_BUILTIN
1323         case BUILT_IN_GOMP_ATOMIC_START:
1324         case BUILT_IN_GOMP_ATOMIC_END:
1325         case BUILT_IN_GOMP_BARRIER:
1326         case BUILT_IN_GOMP_TASKWAIT:
1327         case BUILT_IN_GOMP_CRITICAL_START:
1328         case BUILT_IN_GOMP_CRITICAL_END:
1329         case BUILT_IN_GOMP_CRITICAL_NAME_START:
1330         case BUILT_IN_GOMP_CRITICAL_NAME_END:
1331         case BUILT_IN_GOMP_LOOP_END:
1332         case BUILT_IN_GOMP_ORDERED_START:
1333         case BUILT_IN_GOMP_ORDERED_END:
1334         case BUILT_IN_GOMP_PARALLEL_END:
1335         case BUILT_IN_GOMP_SECTIONS_END:
1336         case BUILT_IN_GOMP_SINGLE_COPY_START:
1337         case BUILT_IN_GOMP_SINGLE_COPY_END:
1338           return true;
1339
1340         default:
1341           /* Fallthru to general call handling.  */;
1342       }
1343
1344   /* Check if base is a global static variable that is not read
1345      by the function.  */
1346   if (callee != NULL_TREE
1347       && TREE_CODE (base) == VAR_DECL
1348       && TREE_STATIC (base))
1349     {
1350       struct cgraph_node *node = cgraph_get_node (callee);
1351       bitmap not_read;
1352
1353       /* FIXME: Callee can be an OMP builtin that does not have a call graph
1354          node yet.  We should enforce that there are nodes for all decls in the
1355          IL and remove this check instead.  */
1356       if (node
1357           && (not_read = ipa_reference_get_not_read_global (node))
1358           && bitmap_bit_p (not_read, DECL_UID (base)))
1359         goto process_args;
1360     }
1361
1362   /* Check if the base variable is call-used.  */
1363   if (DECL_P (base))
1364     {
1365       if (pt_solution_includes (gimple_call_use_set (call), base))
1366         return true;
1367     }
1368   else if ((TREE_CODE (base) == MEM_REF
1369             || TREE_CODE (base) == TARGET_MEM_REF)
1370            && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
1371     {
1372       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0));
1373       if (!pi)
1374         return true;
1375
1376       if (pt_solutions_intersect (gimple_call_use_set (call), &pi->pt))
1377         return true;
1378     }
1379   else
1380     return true;
1381
1382   /* Inspect call arguments for passed-by-value aliases.  */
1383 process_args:
1384   for (i = 0; i < gimple_call_num_args (call); ++i)
1385     {
1386       tree op = gimple_call_arg (call, i);
1387       int flags = gimple_call_arg_flags (call, i);
1388
1389       if (flags & EAF_UNUSED)
1390         continue;
1391
1392       if (TREE_CODE (op) == WITH_SIZE_EXPR)
1393         op = TREE_OPERAND (op, 0);
1394
1395       if (TREE_CODE (op) != SSA_NAME
1396           && !is_gimple_min_invariant (op))
1397         {
1398           ao_ref r;
1399           ao_ref_init (&r, op);
1400           if (refs_may_alias_p_1 (&r, ref, true))
1401             return true;
1402         }
1403     }
1404
1405   return false;
1406 }
1407
1408 static bool
1409 ref_maybe_used_by_call_p (gimple call, tree ref)
1410 {
1411   ao_ref r;
1412   bool res;
1413   ao_ref_init (&r, ref);
1414   res = ref_maybe_used_by_call_p_1 (call, &r);
1415   if (res)
1416     ++alias_stats.ref_maybe_used_by_call_p_may_alias;
1417   else
1418     ++alias_stats.ref_maybe_used_by_call_p_no_alias;
1419   return res;
1420 }
1421
1422
1423 /* If the statement STMT may use the memory reference REF return
1424    true, otherwise return false.  */
1425
1426 bool
1427 ref_maybe_used_by_stmt_p (gimple stmt, tree ref)
1428 {
1429   if (is_gimple_assign (stmt))
1430     {
1431       tree rhs;
1432
1433       /* All memory assign statements are single.  */
1434       if (!gimple_assign_single_p (stmt))
1435         return false;
1436
1437       rhs = gimple_assign_rhs1 (stmt);
1438       if (is_gimple_reg (rhs)
1439           || is_gimple_min_invariant (rhs)
1440           || gimple_assign_rhs_code (stmt) == CONSTRUCTOR)
1441         return false;
1442
1443       return refs_may_alias_p (rhs, ref);
1444     }
1445   else if (is_gimple_call (stmt))
1446     return ref_maybe_used_by_call_p (stmt, ref);
1447   else if (gimple_code (stmt) == GIMPLE_RETURN)
1448     {
1449       tree retval = gimple_return_retval (stmt);
1450       tree base;
1451       if (retval
1452           && TREE_CODE (retval) != SSA_NAME
1453           && !is_gimple_min_invariant (retval)
1454           && refs_may_alias_p (retval, ref))
1455         return true;
1456       /* If ref escapes the function then the return acts as a use.  */
1457       base = get_base_address (ref);
1458       if (!base)
1459         ;
1460       else if (DECL_P (base))
1461         return is_global_var (base);
1462       else if (TREE_CODE (base) == MEM_REF
1463                || TREE_CODE (base) == TARGET_MEM_REF)
1464         return ptr_deref_may_alias_global_p (TREE_OPERAND (base, 0));
1465       return false;
1466     }
1467
1468   return true;
1469 }
1470
1471 /* If the call in statement CALL may clobber the memory reference REF
1472    return true, otherwise return false.  */
1473
1474 static bool
1475 call_may_clobber_ref_p_1 (gimple call, ao_ref *ref)
1476 {
1477   tree base;
1478   tree callee;
1479
1480   /* If the call is pure or const it cannot clobber anything.  */
1481   if (gimple_call_flags (call)
1482       & (ECF_PURE|ECF_CONST|ECF_LOOPING_CONST_OR_PURE|ECF_NOVOPS))
1483     return false;
1484
1485   base = ao_ref_base (ref);
1486   if (!base)
1487     return true;
1488
1489   if (TREE_CODE (base) == SSA_NAME
1490       || CONSTANT_CLASS_P (base))
1491     return false;
1492
1493   /* A call that is not without side-effects might involve volatile
1494      accesses and thus conflicts with all other volatile accesses.  */
1495   if (ref->volatile_p)
1496     return true;
1497
1498   /* If the reference is based on a decl that is not aliased the call
1499      cannot possibly clobber it.  */
1500   if (DECL_P (base)
1501       && !may_be_aliased (base)
1502       /* But local non-readonly statics can be modified through recursion
1503          or the call may implement a threading barrier which we must
1504          treat as may-def.  */
1505       && (TREE_READONLY (base)
1506           || !is_global_var (base)))
1507     return false;
1508
1509   callee = gimple_call_fndecl (call);
1510
1511   /* Handle those builtin functions explicitly that do not act as
1512      escape points.  See tree-ssa-structalias.c:find_func_aliases
1513      for the list of builtins we might need to handle here.  */
1514   if (callee != NULL_TREE
1515       && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
1516     switch (DECL_FUNCTION_CODE (callee))
1517       {
1518         /* All the following functions clobber memory pointed to by
1519            their first argument.  */
1520         case BUILT_IN_STRCPY:
1521         case BUILT_IN_STRNCPY:
1522         case BUILT_IN_MEMCPY:
1523         case BUILT_IN_MEMMOVE:
1524         case BUILT_IN_MEMPCPY:
1525         case BUILT_IN_STPCPY:
1526         case BUILT_IN_STPNCPY:
1527         case BUILT_IN_STRCAT:
1528         case BUILT_IN_STRNCAT:
1529         case BUILT_IN_MEMSET:
1530         case BUILT_IN_TM_MEMSET:
1531         CASE_BUILT_IN_TM_STORE (1):
1532         CASE_BUILT_IN_TM_STORE (2):
1533         CASE_BUILT_IN_TM_STORE (4):
1534         CASE_BUILT_IN_TM_STORE (8):
1535         CASE_BUILT_IN_TM_STORE (FLOAT):
1536         CASE_BUILT_IN_TM_STORE (DOUBLE):
1537         CASE_BUILT_IN_TM_STORE (LDOUBLE):
1538         CASE_BUILT_IN_TM_STORE (M64):
1539         CASE_BUILT_IN_TM_STORE (M128):
1540         CASE_BUILT_IN_TM_STORE (M256):
1541         case BUILT_IN_TM_MEMCPY:
1542         case BUILT_IN_TM_MEMMOVE:
1543           {
1544             ao_ref dref;
1545             tree size = NULL_TREE;
1546             /* Don't pass in size for strncat, as the maximum size
1547                is strlen (dest) + n + 1 instead of n, resp.
1548                n + 1 at dest + strlen (dest), but strlen (dest) isn't
1549                known.  */
1550             if (gimple_call_num_args (call) == 3
1551                 && DECL_FUNCTION_CODE (callee) != BUILT_IN_STRNCAT)
1552               size = gimple_call_arg (call, 2);
1553             ao_ref_init_from_ptr_and_size (&dref,
1554                                            gimple_call_arg (call, 0),
1555                                            size);
1556             return refs_may_alias_p_1 (&dref, ref, false);
1557           }
1558         case BUILT_IN_STRCPY_CHK:
1559         case BUILT_IN_STRNCPY_CHK:
1560         case BUILT_IN_MEMCPY_CHK:
1561         case BUILT_IN_MEMMOVE_CHK:
1562         case BUILT_IN_MEMPCPY_CHK:
1563         case BUILT_IN_STPCPY_CHK:
1564         case BUILT_IN_STPNCPY_CHK:
1565         case BUILT_IN_STRCAT_CHK:
1566         case BUILT_IN_STRNCAT_CHK:
1567         case BUILT_IN_MEMSET_CHK:
1568           {
1569             ao_ref dref;
1570             tree size = NULL_TREE;
1571             /* Don't pass in size for __strncat_chk, as the maximum size
1572                is strlen (dest) + n + 1 instead of n, resp.
1573                n + 1 at dest + strlen (dest), but strlen (dest) isn't
1574                known.  */
1575             if (gimple_call_num_args (call) == 4
1576                 && DECL_FUNCTION_CODE (callee) != BUILT_IN_STRNCAT_CHK)
1577               size = gimple_call_arg (call, 2);
1578             ao_ref_init_from_ptr_and_size (&dref,
1579                                            gimple_call_arg (call, 0),
1580                                            size);
1581             return refs_may_alias_p_1 (&dref, ref, false);
1582           }
1583         case BUILT_IN_BCOPY:
1584           {
1585             ao_ref dref;
1586             tree size = gimple_call_arg (call, 2);
1587             ao_ref_init_from_ptr_and_size (&dref,
1588                                            gimple_call_arg (call, 1),
1589                                            size);
1590             return refs_may_alias_p_1 (&dref, ref, false);
1591           }
1592         /* Allocating memory does not have any side-effects apart from
1593            being the definition point for the pointer.  */
1594         case BUILT_IN_MALLOC:
1595         case BUILT_IN_CALLOC:
1596         case BUILT_IN_STRDUP:
1597         case BUILT_IN_STRNDUP:
1598           /* Unix98 specifies that errno is set on allocation failure.  */
1599           if (flag_errno_math
1600               && targetm.ref_may_alias_errno (ref))
1601             return true;
1602           return false;
1603         case BUILT_IN_STACK_SAVE:
1604         case BUILT_IN_ALLOCA:
1605         case BUILT_IN_ALLOCA_WITH_ALIGN:
1606         case BUILT_IN_ASSUME_ALIGNED:
1607           return false;
1608         /* Freeing memory kills the pointed-to memory.  More importantly
1609            the call has to serve as a barrier for moving loads and stores
1610            across it.  */
1611         case BUILT_IN_FREE:
1612         case BUILT_IN_VA_END:
1613           {
1614             tree ptr = gimple_call_arg (call, 0);
1615             return ptr_deref_may_alias_ref_p_1 (ptr, ref);
1616           }
1617         case BUILT_IN_GAMMA_R:
1618         case BUILT_IN_GAMMAF_R:
1619         case BUILT_IN_GAMMAL_R:
1620         case BUILT_IN_LGAMMA_R:
1621         case BUILT_IN_LGAMMAF_R:
1622         case BUILT_IN_LGAMMAL_R:
1623           {
1624             tree out = gimple_call_arg (call, 1);
1625             if (ptr_deref_may_alias_ref_p_1 (out, ref))
1626               return true;
1627             if (flag_errno_math)
1628               break;
1629             return false;
1630           }
1631         case BUILT_IN_FREXP:
1632         case BUILT_IN_FREXPF:
1633         case BUILT_IN_FREXPL:
1634         case BUILT_IN_MODF:
1635         case BUILT_IN_MODFF:
1636         case BUILT_IN_MODFL:
1637           {
1638             tree out = gimple_call_arg (call, 1);
1639             return ptr_deref_may_alias_ref_p_1 (out, ref);
1640           }
1641         case BUILT_IN_REMQUO:
1642         case BUILT_IN_REMQUOF:
1643         case BUILT_IN_REMQUOL:
1644           {
1645             tree out = gimple_call_arg (call, 2);
1646             if (ptr_deref_may_alias_ref_p_1 (out, ref))
1647               return true;
1648             if (flag_errno_math)
1649               break;
1650             return false;
1651           }
1652         case BUILT_IN_SINCOS:
1653         case BUILT_IN_SINCOSF:
1654         case BUILT_IN_SINCOSL:
1655           {
1656             tree sin = gimple_call_arg (call, 1);
1657             tree cos = gimple_call_arg (call, 2);
1658             return (ptr_deref_may_alias_ref_p_1 (sin, ref)
1659                     || ptr_deref_may_alias_ref_p_1 (cos, ref));
1660           }
1661         /* __sync_* builtins and some OpenMP builtins act as threading
1662            barriers.  */
1663 #undef DEF_SYNC_BUILTIN
1664 #define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
1665 #include "sync-builtins.def"
1666 #undef DEF_SYNC_BUILTIN
1667         case BUILT_IN_GOMP_ATOMIC_START:
1668         case BUILT_IN_GOMP_ATOMIC_END:
1669         case BUILT_IN_GOMP_BARRIER:
1670         case BUILT_IN_GOMP_TASKWAIT:
1671         case BUILT_IN_GOMP_CRITICAL_START:
1672         case BUILT_IN_GOMP_CRITICAL_END:
1673         case BUILT_IN_GOMP_CRITICAL_NAME_START:
1674         case BUILT_IN_GOMP_CRITICAL_NAME_END:
1675         case BUILT_IN_GOMP_LOOP_END:
1676         case BUILT_IN_GOMP_ORDERED_START:
1677         case BUILT_IN_GOMP_ORDERED_END:
1678         case BUILT_IN_GOMP_PARALLEL_END:
1679         case BUILT_IN_GOMP_SECTIONS_END:
1680         case BUILT_IN_GOMP_SINGLE_COPY_START:
1681         case BUILT_IN_GOMP_SINGLE_COPY_END:
1682           return true;
1683         default:
1684           /* Fallthru to general call handling.  */;
1685       }
1686
1687   /* Check if base is a global static variable that is not written
1688      by the function.  */
1689   if (callee != NULL_TREE
1690       && TREE_CODE (base) == VAR_DECL
1691       && TREE_STATIC (base))
1692     {
1693       struct cgraph_node *node = cgraph_get_node (callee);
1694       bitmap not_written;
1695
1696       if (node
1697           && (not_written = ipa_reference_get_not_written_global (node))
1698           && bitmap_bit_p (not_written, DECL_UID (base)))
1699         return false;
1700     }
1701
1702   /* Check if the base variable is call-clobbered.  */
1703   if (DECL_P (base))
1704     return pt_solution_includes (gimple_call_clobber_set (call), base);
1705   else if ((TREE_CODE (base) == MEM_REF
1706             || TREE_CODE (base) == TARGET_MEM_REF)
1707            && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
1708     {
1709       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0));
1710       if (!pi)
1711         return true;
1712
1713       return pt_solutions_intersect (gimple_call_clobber_set (call), &pi->pt);
1714     }
1715
1716   return true;
1717 }
1718
1719 /* If the call in statement CALL may clobber the memory reference REF
1720    return true, otherwise return false.  */
1721
1722 bool
1723 call_may_clobber_ref_p (gimple call, tree ref)
1724 {
1725   bool res;
1726   ao_ref r;
1727   ao_ref_init (&r, ref);
1728   res = call_may_clobber_ref_p_1 (call, &r);
1729   if (res)
1730     ++alias_stats.call_may_clobber_ref_p_may_alias;
1731   else
1732     ++alias_stats.call_may_clobber_ref_p_no_alias;
1733   return res;
1734 }
1735
1736
1737 /* If the statement STMT may clobber the memory reference REF return true,
1738    otherwise return false.  */
1739
1740 bool
1741 stmt_may_clobber_ref_p_1 (gimple stmt, ao_ref *ref)
1742 {
1743   if (is_gimple_call (stmt))
1744     {
1745       tree lhs = gimple_call_lhs (stmt);
1746       if (lhs
1747           && TREE_CODE (lhs) != SSA_NAME)
1748         {
1749           ao_ref r;
1750           ao_ref_init (&r, lhs);
1751           if (refs_may_alias_p_1 (ref, &r, true))
1752             return true;
1753         }
1754
1755       return call_may_clobber_ref_p_1 (stmt, ref);
1756     }
1757   else if (gimple_assign_single_p (stmt))
1758     {
1759       tree lhs = gimple_assign_lhs (stmt);
1760       if (TREE_CODE (lhs) != SSA_NAME)
1761         {
1762           ao_ref r;
1763           ao_ref_init (&r, lhs);
1764           return refs_may_alias_p_1 (ref, &r, true);
1765         }
1766     }
1767   else if (gimple_code (stmt) == GIMPLE_ASM)
1768     return true;
1769
1770   return false;
1771 }
1772
1773 bool
1774 stmt_may_clobber_ref_p (gimple stmt, tree ref)
1775 {
1776   ao_ref r;
1777   ao_ref_init (&r, ref);
1778   return stmt_may_clobber_ref_p_1 (stmt, &r);
1779 }
1780
1781 /* If STMT kills the memory reference REF return true, otherwise
1782    return false.  */
1783
1784 static bool
1785 stmt_kills_ref_p_1 (gimple stmt, ao_ref *ref)
1786 {
1787   /* For a must-alias check we need to be able to constrain
1788      the access properly.  */
1789   ao_ref_base (ref);
1790   if (ref->max_size == -1)
1791     return false;
1792
1793   if (gimple_has_lhs (stmt)
1794       && TREE_CODE (gimple_get_lhs (stmt)) != SSA_NAME
1795       /* The assignment is not necessarily carried out if it can throw
1796          and we can catch it in the current function where we could inspect
1797          the previous value.
1798          ???  We only need to care about the RHS throwing.  For aggregate
1799          assignments or similar calls and non-call exceptions the LHS
1800          might throw as well.  */
1801       && !stmt_can_throw_internal (stmt))
1802     {
1803       tree base, lhs = gimple_get_lhs (stmt);
1804       HOST_WIDE_INT size, offset, max_size;
1805       base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
1806       /* We can get MEM[symbol: sZ, index: D.8862_1] here,
1807          so base == ref->base does not always hold.  */
1808       if (base == ref->base)
1809         {
1810           /* For a must-alias check we need to be able to constrain
1811              the access properly.  */
1812           if (size != -1 && size == max_size)
1813             {
1814               if (offset <= ref->offset
1815                   && offset + size >= ref->offset + ref->max_size)
1816                 return true;
1817             }
1818         }
1819     }
1820
1821   if (is_gimple_call (stmt))
1822     {
1823       tree callee = gimple_call_fndecl (stmt);
1824       if (callee != NULL_TREE
1825           && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
1826         switch (DECL_FUNCTION_CODE (callee))
1827           {
1828           case BUILT_IN_MEMCPY:
1829           case BUILT_IN_MEMPCPY:
1830           case BUILT_IN_MEMMOVE:
1831           case BUILT_IN_MEMSET:
1832           case BUILT_IN_MEMCPY_CHK:
1833           case BUILT_IN_MEMPCPY_CHK:
1834           case BUILT_IN_MEMMOVE_CHK:
1835           case BUILT_IN_MEMSET_CHK:
1836             {
1837               tree dest = gimple_call_arg (stmt, 0);
1838               tree len = gimple_call_arg (stmt, 2);
1839               tree base = NULL_TREE;
1840               HOST_WIDE_INT offset = 0;
1841               if (!host_integerp (len, 0))
1842                 return false;
1843               if (TREE_CODE (dest) == ADDR_EXPR)
1844                 base = get_addr_base_and_unit_offset (TREE_OPERAND (dest, 0),
1845                                                       &offset);
1846               else if (TREE_CODE (dest) == SSA_NAME)
1847                 base = dest;
1848               if (base
1849                   && base == ao_ref_base (ref))
1850                 {
1851                   HOST_WIDE_INT size = TREE_INT_CST_LOW (len);
1852                   if (offset <= ref->offset / BITS_PER_UNIT
1853                       && (offset + size
1854                           >= ((ref->offset + ref->max_size + BITS_PER_UNIT - 1)
1855                               / BITS_PER_UNIT)))
1856                     return true;
1857                 }
1858               break;
1859             }
1860
1861           case BUILT_IN_VA_END:
1862             {
1863               tree ptr = gimple_call_arg (stmt, 0);
1864               if (TREE_CODE (ptr) == ADDR_EXPR)
1865                 {
1866                   tree base = ao_ref_base (ref);
1867                   if (TREE_OPERAND (ptr, 0) == base)
1868                     return true;
1869                 }
1870               break;
1871             }
1872
1873           default:;
1874           }
1875     }
1876   return false;
1877 }
1878
1879 bool
1880 stmt_kills_ref_p (gimple stmt, tree ref)
1881 {
1882   ao_ref r;
1883   ao_ref_init (&r, ref);
1884   return stmt_kills_ref_p_1 (stmt, &r);
1885 }
1886
1887
1888 /* Walk the virtual use-def chain of VUSE until hitting the virtual operand
1889    TARGET or a statement clobbering the memory reference REF in which
1890    case false is returned.  The walk starts with VUSE, one argument of PHI.  */
1891
1892 static bool
1893 maybe_skip_until (gimple phi, tree target, ao_ref *ref,
1894                   tree vuse, bitmap *visited)
1895 {
1896   basic_block bb = gimple_bb (phi);
1897
1898   if (!*visited)
1899     *visited = BITMAP_ALLOC (NULL);
1900
1901   bitmap_set_bit (*visited, SSA_NAME_VERSION (PHI_RESULT (phi)));
1902
1903   /* Walk until we hit the target.  */
1904   while (vuse != target)
1905     {
1906       gimple def_stmt = SSA_NAME_DEF_STMT (vuse);
1907       /* Recurse for PHI nodes.  */
1908       if (gimple_code (def_stmt) == GIMPLE_PHI)
1909         {
1910           /* An already visited PHI node ends the walk successfully.  */
1911           if (bitmap_bit_p (*visited, SSA_NAME_VERSION (PHI_RESULT (def_stmt))))
1912             return true;
1913           vuse = get_continuation_for_phi (def_stmt, ref, visited);
1914           if (!vuse)
1915             return false;
1916           continue;
1917         }
1918       /* A clobbering statement or the end of the IL ends it failing.  */
1919       else if (gimple_nop_p (def_stmt)
1920                || stmt_may_clobber_ref_p_1 (def_stmt, ref))
1921         return false;
1922       /* If we reach a new basic-block see if we already skipped it
1923          in a previous walk that ended successfully.  */
1924       if (gimple_bb (def_stmt) != bb)
1925         {
1926           if (!bitmap_set_bit (*visited, SSA_NAME_VERSION (vuse)))
1927             return true;
1928           bb = gimple_bb (def_stmt);
1929         }
1930       vuse = gimple_vuse (def_stmt);
1931     }
1932   return true;
1933 }
1934
1935 /* For two PHI arguments ARG0 and ARG1 try to skip non-aliasing code
1936    until we hit the phi argument definition that dominates the other one.
1937    Return that, or NULL_TREE if there is no such definition.  */
1938
1939 static tree
1940 get_continuation_for_phi_1 (gimple phi, tree arg0, tree arg1,
1941                             ao_ref *ref, bitmap *visited)
1942 {
1943   gimple def0 = SSA_NAME_DEF_STMT (arg0);
1944   gimple def1 = SSA_NAME_DEF_STMT (arg1);
1945   tree common_vuse;
1946
1947   if (arg0 == arg1)
1948     return arg0;
1949   else if (gimple_nop_p (def0)
1950            || (!gimple_nop_p (def1)
1951                && dominated_by_p (CDI_DOMINATORS,
1952                                   gimple_bb (def1), gimple_bb (def0))))
1953     {
1954       if (maybe_skip_until (phi, arg0, ref, arg1, visited))
1955         return arg0;
1956     }
1957   else if (gimple_nop_p (def1)
1958            || dominated_by_p (CDI_DOMINATORS,
1959                               gimple_bb (def0), gimple_bb (def1)))
1960     {
1961       if (maybe_skip_until (phi, arg1, ref, arg0, visited))
1962         return arg1;
1963     }
1964   /* Special case of a diamond:
1965        MEM_1 = ...
1966        goto (cond) ? L1 : L2
1967        L1: store1 = ...    #MEM_2 = vuse(MEM_1)
1968            goto L3
1969        L2: store2 = ...    #MEM_3 = vuse(MEM_1)
1970        L3: MEM_4 = PHI<MEM_2, MEM_3>
1971      We were called with the PHI at L3, MEM_2 and MEM_3 don't
1972      dominate each other, but still we can easily skip this PHI node
1973      if we recognize that the vuse MEM operand is the same for both,
1974      and that we can skip both statements (they don't clobber us).
1975      This is still linear.  Don't use maybe_skip_until, that might
1976      potentially be slow.  */
1977   else if ((common_vuse = gimple_vuse (def0))
1978            && common_vuse == gimple_vuse (def1))
1979     {
1980       if (!stmt_may_clobber_ref_p_1 (def0, ref)
1981           && !stmt_may_clobber_ref_p_1 (def1, ref))
1982         return common_vuse;
1983     }
1984
1985   return NULL_TREE;
1986 }
1987
1988
1989 /* Starting from a PHI node for the virtual operand of the memory reference
1990    REF find a continuation virtual operand that allows to continue walking
1991    statements dominating PHI skipping only statements that cannot possibly
1992    clobber REF.  Returns NULL_TREE if no suitable virtual operand can
1993    be found.  */
1994
1995 tree
1996 get_continuation_for_phi (gimple phi, ao_ref *ref, bitmap *visited)
1997 {
1998   unsigned nargs = gimple_phi_num_args (phi);
1999
2000   /* Through a single-argument PHI we can simply look through.  */
2001   if (nargs == 1)
2002     return PHI_ARG_DEF (phi, 0);
2003
2004   /* For two or more arguments try to pairwise skip non-aliasing code
2005      until we hit the phi argument definition that dominates the other one.  */
2006   else if (nargs >= 2)
2007     {
2008       tree arg0, arg1;
2009       unsigned i;
2010
2011       /* Find a candidate for the virtual operand which definition
2012          dominates those of all others.  */
2013       arg0 = PHI_ARG_DEF (phi, 0);
2014       if (!SSA_NAME_IS_DEFAULT_DEF (arg0))
2015         for (i = 1; i < nargs; ++i)
2016           {
2017             arg1 = PHI_ARG_DEF (phi, i);
2018             if (SSA_NAME_IS_DEFAULT_DEF (arg1))
2019               {
2020                 arg0 = arg1;
2021                 break;
2022               }
2023             if (dominated_by_p (CDI_DOMINATORS,
2024                                 gimple_bb (SSA_NAME_DEF_STMT (arg0)),
2025                                 gimple_bb (SSA_NAME_DEF_STMT (arg1))))
2026               arg0 = arg1;
2027           }
2028
2029       /* Then pairwise reduce against the found candidate.  */
2030       for (i = 0; i < nargs; ++i)
2031         {
2032           arg1 = PHI_ARG_DEF (phi, i);
2033           arg0 = get_continuation_for_phi_1 (phi, arg0, arg1, ref, visited);
2034           if (!arg0)
2035             return NULL_TREE;
2036         }
2037
2038       return arg0;
2039     }
2040
2041   return NULL_TREE;
2042 }
2043
2044 /* Based on the memory reference REF and its virtual use VUSE call
2045    WALKER for each virtual use that is equivalent to VUSE, including VUSE
2046    itself.  That is, for each virtual use for which its defining statement
2047    does not clobber REF.
2048
2049    WALKER is called with REF, the current virtual use and DATA.  If
2050    WALKER returns non-NULL the walk stops and its result is returned.
2051    At the end of a non-successful walk NULL is returned.
2052
2053    TRANSLATE if non-NULL is called with a pointer to REF, the virtual
2054    use which definition is a statement that may clobber REF and DATA.
2055    If TRANSLATE returns (void *)-1 the walk stops and NULL is returned.
2056    If TRANSLATE returns non-NULL the walk stops and its result is returned.
2057    If TRANSLATE returns NULL the walk continues and TRANSLATE is supposed
2058    to adjust REF and *DATA to make that valid.
2059
2060    TODO: Cache the vector of equivalent vuses per ref, vuse pair.  */
2061
2062 void *
2063 walk_non_aliased_vuses (ao_ref *ref, tree vuse,
2064                         void *(*walker)(ao_ref *, tree, void *),
2065                         void *(*translate)(ao_ref *, tree, void *), void *data)
2066 {
2067   bitmap visited = NULL;
2068   void *res;
2069
2070   timevar_push (TV_ALIAS_STMT_WALK);
2071
2072   do
2073     {
2074       gimple def_stmt;
2075
2076       /* ???  Do we want to account this to TV_ALIAS_STMT_WALK?  */
2077       res = (*walker) (ref, vuse, data);
2078       if (res)
2079         break;
2080
2081       def_stmt = SSA_NAME_DEF_STMT (vuse);
2082       if (gimple_nop_p (def_stmt))
2083         break;
2084       else if (gimple_code (def_stmt) == GIMPLE_PHI)
2085         vuse = get_continuation_for_phi (def_stmt, ref, &visited);
2086       else
2087         {
2088           if (stmt_may_clobber_ref_p_1 (def_stmt, ref))
2089             {
2090               if (!translate)
2091                 break;
2092               res = (*translate) (ref, vuse, data);
2093               /* Failed lookup and translation.  */
2094               if (res == (void *)-1)
2095                 {
2096                   res = NULL;
2097                   break;
2098                 }
2099               /* Lookup succeeded.  */
2100               else if (res != NULL)
2101                 break;
2102               /* Translation succeeded, continue walking.  */
2103             }
2104           vuse = gimple_vuse (def_stmt);
2105         }
2106     }
2107   while (vuse);
2108
2109   if (visited)
2110     BITMAP_FREE (visited);
2111
2112   timevar_pop (TV_ALIAS_STMT_WALK);
2113
2114   return res;
2115 }
2116
2117
2118 /* Based on the memory reference REF call WALKER for each vdef which
2119    defining statement may clobber REF, starting with VDEF.  If REF
2120    is NULL_TREE, each defining statement is visited.
2121
2122    WALKER is called with REF, the current vdef and DATA.  If WALKER
2123    returns true the walk is stopped, otherwise it continues.
2124
2125    At PHI nodes walk_aliased_vdefs forks into one walk for reach
2126    PHI argument (but only one walk continues on merge points), the
2127    return value is true if any of the walks was successful.
2128
2129    The function returns the number of statements walked.  */
2130
2131 static unsigned int
2132 walk_aliased_vdefs_1 (ao_ref *ref, tree vdef,
2133                       bool (*walker)(ao_ref *, tree, void *), void *data,
2134                       bitmap *visited, unsigned int cnt)
2135 {
2136   do
2137     {
2138       gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
2139
2140       if (*visited
2141           && !bitmap_set_bit (*visited, SSA_NAME_VERSION (vdef)))
2142         return cnt;
2143
2144       if (gimple_nop_p (def_stmt))
2145         return cnt;
2146       else if (gimple_code (def_stmt) == GIMPLE_PHI)
2147         {
2148           unsigned i;
2149           if (!*visited)
2150             *visited = BITMAP_ALLOC (NULL);
2151           for (i = 0; i < gimple_phi_num_args (def_stmt); ++i)
2152             cnt += walk_aliased_vdefs_1 (ref, gimple_phi_arg_def (def_stmt, i),
2153                                          walker, data, visited, 0);
2154           return cnt;
2155         }
2156
2157       /* ???  Do we want to account this to TV_ALIAS_STMT_WALK?  */
2158       cnt++;
2159       if ((!ref
2160            || stmt_may_clobber_ref_p_1 (def_stmt, ref))
2161           && (*walker) (ref, vdef, data))
2162         return cnt;
2163
2164       vdef = gimple_vuse (def_stmt);
2165     }
2166   while (1);
2167 }
2168
2169 unsigned int
2170 walk_aliased_vdefs (ao_ref *ref, tree vdef,
2171                     bool (*walker)(ao_ref *, tree, void *), void *data,
2172                     bitmap *visited)
2173 {
2174   bitmap local_visited = NULL;
2175   unsigned int ret;
2176
2177   timevar_push (TV_ALIAS_STMT_WALK);
2178
2179   ret = walk_aliased_vdefs_1 (ref, vdef, walker, data,
2180                               visited ? visited : &local_visited, 0);
2181   if (local_visited)
2182     BITMAP_FREE (local_visited);
2183
2184   timevar_pop (TV_ALIAS_STMT_WALK);
2185
2186   return ret;
2187 }
2188