1 /* Alias analysis for trees.
2    Copyright (C) 2004-2018 Free Software Foundation, Inc.
3    Contributed by Diego Novillo <dnovillo@redhat.com>
4 
5 This file is part of GCC.
6 
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 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; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20 
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "backend.h"
25 #include "target.h"
26 #include "rtl.h"
27 #include "tree.h"
28 #include "gimple.h"
29 #include "timevar.h"	/* for TV_ALIAS_STMT_WALK */
30 #include "ssa.h"
31 #include "cgraph.h"
32 #include "tree-pretty-print.h"
33 #include "alias.h"
34 #include "fold-const.h"
35 #include "langhooks.h"
36 #include "dumpfile.h"
37 #include "tree-eh.h"
38 #include "tree-dfa.h"
39 #include "ipa-reference.h"
40 #include "varasm.h"
41 
42 /* Broad overview of how alias analysis on gimple works:
43 
44    Statements clobbering or using memory are linked through the
45    virtual operand factored use-def chain.  The virtual operand
46    is unique per function, its symbol is accessible via gimple_vop (cfun).
47    Virtual operands are used for efficiently walking memory statements
48    in the gimple IL and are useful for things like value-numbering as
49    a generation count for memory references.
50 
51    SSA_NAME pointers may have associated points-to information
52    accessible via the SSA_NAME_PTR_INFO macro.  Flow-insensitive
53    points-to information is (re-)computed by the TODO_rebuild_alias
54    pass manager todo.  Points-to information is also used for more
55    precise tracking of call-clobbered and call-used variables and
56    related disambiguations.
57 
58    This file contains functions for disambiguating memory references,
59    the so called alias-oracle and tools for walking of the gimple IL.
60 
61    The main alias-oracle entry-points are
62 
63    bool stmt_may_clobber_ref_p (gimple *, tree)
64 
65      This function queries if a statement may invalidate (parts of)
66      the memory designated by the reference tree argument.
67 
68    bool ref_maybe_used_by_stmt_p (gimple *, tree)
69 
70      This function queries if a statement may need (parts of) the
71      memory designated by the reference tree argument.
72 
73    There are variants of these functions that only handle the call
74    part of a statement, call_may_clobber_ref_p and ref_maybe_used_by_call_p.
75    Note that these do not disambiguate against a possible call lhs.
76 
77    bool refs_may_alias_p (tree, tree)
78 
79      This function tries to disambiguate two reference trees.
80 
81    bool ptr_deref_may_alias_global_p (tree)
82 
83      This function queries if dereferencing a pointer variable may
84      alias global memory.
85 
86    More low-level disambiguators are available and documented in
87    this file.  Low-level disambiguators dealing with points-to
88    information are in tree-ssa-structalias.c.  */
89 
90 
91 /* Query statistics for the different low-level disambiguators.
92    A high-level query may trigger multiple of them.  */
93 
94 static struct {
95   unsigned HOST_WIDE_INT refs_may_alias_p_may_alias;
96   unsigned HOST_WIDE_INT refs_may_alias_p_no_alias;
97   unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_may_alias;
98   unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_no_alias;
99   unsigned HOST_WIDE_INT call_may_clobber_ref_p_may_alias;
100   unsigned HOST_WIDE_INT call_may_clobber_ref_p_no_alias;
101 } alias_stats;
102 
103 void
dump_alias_stats(FILE * s)104 dump_alias_stats (FILE *s)
105 {
106   fprintf (s, "\nAlias oracle query stats:\n");
107   fprintf (s, "  refs_may_alias_p: "
108 	   HOST_WIDE_INT_PRINT_DEC" disambiguations, "
109 	   HOST_WIDE_INT_PRINT_DEC" queries\n",
110 	   alias_stats.refs_may_alias_p_no_alias,
111 	   alias_stats.refs_may_alias_p_no_alias
112 	   + alias_stats.refs_may_alias_p_may_alias);
113   fprintf (s, "  ref_maybe_used_by_call_p: "
114 	   HOST_WIDE_INT_PRINT_DEC" disambiguations, "
115 	   HOST_WIDE_INT_PRINT_DEC" queries\n",
116 	   alias_stats.ref_maybe_used_by_call_p_no_alias,
117 	   alias_stats.refs_may_alias_p_no_alias
118 	   + alias_stats.ref_maybe_used_by_call_p_may_alias);
119   fprintf (s, "  call_may_clobber_ref_p: "
120 	   HOST_WIDE_INT_PRINT_DEC" disambiguations, "
121 	   HOST_WIDE_INT_PRINT_DEC" queries\n",
122 	   alias_stats.call_may_clobber_ref_p_no_alias,
123 	   alias_stats.call_may_clobber_ref_p_no_alias
124 	   + alias_stats.call_may_clobber_ref_p_may_alias);
125   dump_alias_stats_in_alias_c (s);
126 }
127 
128 
129 /* Return true, if dereferencing PTR may alias with a global variable.  */
130 
131 bool
ptr_deref_may_alias_global_p(tree ptr)132 ptr_deref_may_alias_global_p (tree ptr)
133 {
134   struct ptr_info_def *pi;
135 
136   /* If we end up with a pointer constant here that may point
137      to global memory.  */
138   if (TREE_CODE (ptr) != SSA_NAME)
139     return true;
140 
141   pi = SSA_NAME_PTR_INFO (ptr);
142 
143   /* If we do not have points-to information for this variable,
144      we have to punt.  */
145   if (!pi)
146     return true;
147 
148   /* ???  This does not use TBAA to prune globals ptr may not access.  */
149   return pt_solution_includes_global (&pi->pt);
150 }
151 
152 /* Return true if dereferencing PTR may alias DECL.
153    The caller is responsible for applying TBAA to see if PTR
154    may access DECL at all.  */
155 
156 static bool
ptr_deref_may_alias_decl_p(tree ptr,tree decl)157 ptr_deref_may_alias_decl_p (tree ptr, tree decl)
158 {
159   struct ptr_info_def *pi;
160 
161   /* Conversions are irrelevant for points-to information and
162      data-dependence analysis can feed us those.  */
163   STRIP_NOPS (ptr);
164 
165   /* Anything we do not explicilty handle aliases.  */
166   if ((TREE_CODE (ptr) != SSA_NAME
167        && TREE_CODE (ptr) != ADDR_EXPR
168        && TREE_CODE (ptr) != POINTER_PLUS_EXPR)
169       || !POINTER_TYPE_P (TREE_TYPE (ptr))
170       || (!VAR_P (decl)
171 	  && TREE_CODE (decl) != PARM_DECL
172 	  && TREE_CODE (decl) != RESULT_DECL))
173     return true;
174 
175   /* Disregard pointer offsetting.  */
176   if (TREE_CODE (ptr) == POINTER_PLUS_EXPR)
177     {
178       do
179 	{
180 	  ptr = TREE_OPERAND (ptr, 0);
181 	}
182       while (TREE_CODE (ptr) == POINTER_PLUS_EXPR);
183       return ptr_deref_may_alias_decl_p (ptr, decl);
184     }
185 
186   /* ADDR_EXPR pointers either just offset another pointer or directly
187      specify the pointed-to set.  */
188   if (TREE_CODE (ptr) == ADDR_EXPR)
189     {
190       tree base = get_base_address (TREE_OPERAND (ptr, 0));
191       if (base
192 	  && (TREE_CODE (base) == MEM_REF
193 	      || TREE_CODE (base) == TARGET_MEM_REF))
194 	ptr = TREE_OPERAND (base, 0);
195       else if (base
196 	       && DECL_P (base))
197 	return compare_base_decls (base, decl) != 0;
198       else if (base
199 	       && CONSTANT_CLASS_P (base))
200 	return false;
201       else
202 	return true;
203     }
204 
205   /* Non-aliased variables can not be pointed to.  */
206   if (!may_be_aliased (decl))
207     return false;
208 
209   /* If we do not have useful points-to information for this pointer
210      we cannot disambiguate anything else.  */
211   pi = SSA_NAME_PTR_INFO (ptr);
212   if (!pi)
213     return true;
214 
215   return pt_solution_includes (&pi->pt, decl);
216 }
217 
218 /* Return true if dereferenced PTR1 and PTR2 may alias.
219    The caller is responsible for applying TBAA to see if accesses
220    through PTR1 and PTR2 may conflict at all.  */
221 
222 bool
ptr_derefs_may_alias_p(tree ptr1,tree ptr2)223 ptr_derefs_may_alias_p (tree ptr1, tree ptr2)
224 {
225   struct ptr_info_def *pi1, *pi2;
226 
227   /* Conversions are irrelevant for points-to information and
228      data-dependence analysis can feed us those.  */
229   STRIP_NOPS (ptr1);
230   STRIP_NOPS (ptr2);
231 
232   /* Disregard pointer offsetting.  */
233   if (TREE_CODE (ptr1) == POINTER_PLUS_EXPR)
234     {
235       do
236 	{
237 	  ptr1 = TREE_OPERAND (ptr1, 0);
238 	}
239       while (TREE_CODE (ptr1) == POINTER_PLUS_EXPR);
240       return ptr_derefs_may_alias_p (ptr1, ptr2);
241     }
242   if (TREE_CODE (ptr2) == POINTER_PLUS_EXPR)
243     {
244       do
245 	{
246 	  ptr2 = TREE_OPERAND (ptr2, 0);
247 	}
248       while (TREE_CODE (ptr2) == POINTER_PLUS_EXPR);
249       return ptr_derefs_may_alias_p (ptr1, ptr2);
250     }
251 
252   /* ADDR_EXPR pointers either just offset another pointer or directly
253      specify the pointed-to set.  */
254   if (TREE_CODE (ptr1) == ADDR_EXPR)
255     {
256       tree base = get_base_address (TREE_OPERAND (ptr1, 0));
257       if (base
258 	  && (TREE_CODE (base) == MEM_REF
259 	      || TREE_CODE (base) == TARGET_MEM_REF))
260 	return ptr_derefs_may_alias_p (TREE_OPERAND (base, 0), ptr2);
261       else if (base
262 	       && DECL_P (base))
263 	return ptr_deref_may_alias_decl_p (ptr2, base);
264       else
265 	return true;
266     }
267   if (TREE_CODE (ptr2) == ADDR_EXPR)
268     {
269       tree base = get_base_address (TREE_OPERAND (ptr2, 0));
270       if (base
271 	  && (TREE_CODE (base) == MEM_REF
272 	      || TREE_CODE (base) == TARGET_MEM_REF))
273 	return ptr_derefs_may_alias_p (ptr1, TREE_OPERAND (base, 0));
274       else if (base
275 	       && DECL_P (base))
276 	return ptr_deref_may_alias_decl_p (ptr1, base);
277       else
278 	return true;
279     }
280 
281   /* From here we require SSA name pointers.  Anything else aliases.  */
282   if (TREE_CODE (ptr1) != SSA_NAME
283       || TREE_CODE (ptr2) != SSA_NAME
284       || !POINTER_TYPE_P (TREE_TYPE (ptr1))
285       || !POINTER_TYPE_P (TREE_TYPE (ptr2)))
286     return true;
287 
288   /* We may end up with two empty points-to solutions for two same pointers.
289      In this case we still want to say both pointers alias, so shortcut
290      that here.  */
291   if (ptr1 == ptr2)
292     return true;
293 
294   /* If we do not have useful points-to information for either pointer
295      we cannot disambiguate anything else.  */
296   pi1 = SSA_NAME_PTR_INFO (ptr1);
297   pi2 = SSA_NAME_PTR_INFO (ptr2);
298   if (!pi1 || !pi2)
299     return true;
300 
301   /* ???  This does not use TBAA to prune decls from the intersection
302      that not both pointers may access.  */
303   return pt_solutions_intersect (&pi1->pt, &pi2->pt);
304 }
305 
306 /* Return true if dereferencing PTR may alias *REF.
307    The caller is responsible for applying TBAA to see if PTR
308    may access *REF at all.  */
309 
310 static bool
ptr_deref_may_alias_ref_p_1(tree ptr,ao_ref * ref)311 ptr_deref_may_alias_ref_p_1 (tree ptr, ao_ref *ref)
312 {
313   tree base = ao_ref_base (ref);
314 
315   if (TREE_CODE (base) == MEM_REF
316       || TREE_CODE (base) == TARGET_MEM_REF)
317     return ptr_derefs_may_alias_p (ptr, TREE_OPERAND (base, 0));
318   else if (DECL_P (base))
319     return ptr_deref_may_alias_decl_p (ptr, base);
320 
321   return true;
322 }
323 
324 /* Returns true if PTR1 and PTR2 compare unequal because of points-to.  */
325 
326 bool
ptrs_compare_unequal(tree ptr1,tree ptr2)327 ptrs_compare_unequal (tree ptr1, tree ptr2)
328 {
329   /* First resolve the pointers down to a SSA name pointer base or
330      a VAR_DECL, PARM_DECL or RESULT_DECL.  This explicitely does
331      not yet try to handle LABEL_DECLs, FUNCTION_DECLs, CONST_DECLs
332      or STRING_CSTs which needs points-to adjustments to track them
333      in the points-to sets.  */
334   tree obj1 = NULL_TREE;
335   tree obj2 = NULL_TREE;
336   if (TREE_CODE (ptr1) == ADDR_EXPR)
337     {
338       tree tem = get_base_address (TREE_OPERAND (ptr1, 0));
339       if (! tem)
340 	return false;
341       if (VAR_P (tem)
342 	  || TREE_CODE (tem) == PARM_DECL
343 	  || TREE_CODE (tem) == RESULT_DECL)
344 	obj1 = tem;
345       else if (TREE_CODE (tem) == MEM_REF)
346 	ptr1 = TREE_OPERAND (tem, 0);
347     }
348   if (TREE_CODE (ptr2) == ADDR_EXPR)
349     {
350       tree tem = get_base_address (TREE_OPERAND (ptr2, 0));
351       if (! tem)
352 	return false;
353       if (VAR_P (tem)
354 	  || TREE_CODE (tem) == PARM_DECL
355 	  || TREE_CODE (tem) == RESULT_DECL)
356 	obj2 = tem;
357       else if (TREE_CODE (tem) == MEM_REF)
358 	ptr2 = TREE_OPERAND (tem, 0);
359     }
360 
361   /* Canonicalize ptr vs. object.  */
362   if (TREE_CODE (ptr1) == SSA_NAME && obj2)
363     {
364       std::swap (ptr1, ptr2);
365       std::swap (obj1, obj2);
366     }
367 
368   if (obj1 && obj2)
369     /* Other code handles this correctly, no need to duplicate it here.  */;
370   else if (obj1 && TREE_CODE (ptr2) == SSA_NAME)
371     {
372       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr2);
373       /* We may not use restrict to optimize pointer comparisons.
374          See PR71062.  So we have to assume that restrict-pointed-to
375 	 may be in fact obj1.  */
376       if (!pi
377 	  || pi->pt.vars_contains_restrict
378 	  || pi->pt.vars_contains_interposable)
379 	return false;
380       if (VAR_P (obj1)
381 	  && (TREE_STATIC (obj1) || DECL_EXTERNAL (obj1)))
382 	{
383 	  varpool_node *node = varpool_node::get (obj1);
384 	  /* If obj1 may bind to NULL give up (see below).  */
385 	  if (! node
386 	      || ! node->nonzero_address ()
387 	      || ! decl_binds_to_current_def_p (obj1))
388 	    return false;
389 	}
390       return !pt_solution_includes (&pi->pt, obj1);
391     }
392 
393   /* ???  We'd like to handle ptr1 != NULL and ptr1 != ptr2
394      but those require pt.null to be conservatively correct.  */
395 
396   return false;
397 }
398 
399 /* Returns whether reference REF to BASE may refer to global memory.  */
400 
401 static bool
ref_may_alias_global_p_1(tree base)402 ref_may_alias_global_p_1 (tree base)
403 {
404   if (DECL_P (base))
405     return is_global_var (base);
406   else if (TREE_CODE (base) == MEM_REF
407 	   || TREE_CODE (base) == TARGET_MEM_REF)
408     return ptr_deref_may_alias_global_p (TREE_OPERAND (base, 0));
409   return true;
410 }
411 
412 bool
ref_may_alias_global_p(ao_ref * ref)413 ref_may_alias_global_p (ao_ref *ref)
414 {
415   tree base = ao_ref_base (ref);
416   return ref_may_alias_global_p_1 (base);
417 }
418 
419 bool
ref_may_alias_global_p(tree ref)420 ref_may_alias_global_p (tree ref)
421 {
422   tree base = get_base_address (ref);
423   return ref_may_alias_global_p_1 (base);
424 }
425 
426 /* Return true whether STMT may clobber global memory.  */
427 
428 bool
stmt_may_clobber_global_p(gimple * stmt)429 stmt_may_clobber_global_p (gimple *stmt)
430 {
431   tree lhs;
432 
433   if (!gimple_vdef (stmt))
434     return false;
435 
436   /* ???  We can ask the oracle whether an artificial pointer
437      dereference with a pointer with points-to information covering
438      all global memory (what about non-address taken memory?) maybe
439      clobbered by this call.  As there is at the moment no convenient
440      way of doing that without generating garbage do some manual
441      checking instead.
442      ???  We could make a NULL ao_ref argument to the various
443      predicates special, meaning any global memory.  */
444 
445   switch (gimple_code (stmt))
446     {
447     case GIMPLE_ASSIGN:
448       lhs = gimple_assign_lhs (stmt);
449       return (TREE_CODE (lhs) != SSA_NAME
450 	      && ref_may_alias_global_p (lhs));
451     case GIMPLE_CALL:
452       return true;
453     default:
454       return true;
455     }
456 }
457 
458 
459 /* Dump alias information on FILE.  */
460 
461 void
dump_alias_info(FILE * file)462 dump_alias_info (FILE *file)
463 {
464   unsigned i;
465   tree ptr;
466   const char *funcname
467     = lang_hooks.decl_printable_name (current_function_decl, 2);
468   tree var;
469 
470   fprintf (file, "\n\nAlias information for %s\n\n", funcname);
471 
472   fprintf (file, "Aliased symbols\n\n");
473 
474   FOR_EACH_LOCAL_DECL (cfun, i, var)
475     {
476       if (may_be_aliased (var))
477 	dump_variable (file, var);
478     }
479 
480   fprintf (file, "\nCall clobber information\n");
481 
482   fprintf (file, "\nESCAPED");
483   dump_points_to_solution (file, &cfun->gimple_df->escaped);
484 
485   fprintf (file, "\n\nFlow-insensitive points-to information\n\n");
486 
487   FOR_EACH_SSA_NAME (i, ptr, cfun)
488     {
489       struct ptr_info_def *pi;
490 
491       if (!POINTER_TYPE_P (TREE_TYPE (ptr))
492 	  || SSA_NAME_IN_FREE_LIST (ptr))
493 	continue;
494 
495       pi = SSA_NAME_PTR_INFO (ptr);
496       if (pi)
497 	dump_points_to_info_for (file, ptr);
498     }
499 
500   fprintf (file, "\n");
501 }
502 
503 
504 /* Dump alias information on stderr.  */
505 
506 DEBUG_FUNCTION void
debug_alias_info(void)507 debug_alias_info (void)
508 {
509   dump_alias_info (stderr);
510 }
511 
512 
513 /* Dump the points-to set *PT into FILE.  */
514 
515 void
dump_points_to_solution(FILE * file,struct pt_solution * pt)516 dump_points_to_solution (FILE *file, struct pt_solution *pt)
517 {
518   if (pt->anything)
519     fprintf (file, ", points-to anything");
520 
521   if (pt->nonlocal)
522     fprintf (file, ", points-to non-local");
523 
524   if (pt->escaped)
525     fprintf (file, ", points-to escaped");
526 
527   if (pt->ipa_escaped)
528     fprintf (file, ", points-to unit escaped");
529 
530   if (pt->null)
531     fprintf (file, ", points-to NULL");
532 
533   if (pt->vars)
534     {
535       fprintf (file, ", points-to vars: ");
536       dump_decl_set (file, pt->vars);
537       if (pt->vars_contains_nonlocal
538 	  || pt->vars_contains_escaped
539 	  || pt->vars_contains_escaped_heap
540 	  || pt->vars_contains_restrict)
541 	{
542 	  const char *comma = "";
543 	  fprintf (file, " (");
544 	  if (pt->vars_contains_nonlocal)
545 	    {
546 	      fprintf (file, "nonlocal");
547 	      comma = ", ";
548 	    }
549 	  if (pt->vars_contains_escaped)
550 	    {
551 	      fprintf (file, "%sescaped", comma);
552 	      comma = ", ";
553 	    }
554 	  if (pt->vars_contains_escaped_heap)
555 	    {
556 	      fprintf (file, "%sescaped heap", comma);
557 	      comma = ", ";
558 	    }
559 	  if (pt->vars_contains_restrict)
560 	    {
561 	      fprintf (file, "%srestrict", comma);
562 	      comma = ", ";
563 	    }
564 	  if (pt->vars_contains_interposable)
565 	    fprintf (file, "%sinterposable", comma);
566 	  fprintf (file, ")");
567 	}
568     }
569 }
570 
571 
572 /* Unified dump function for pt_solution.  */
573 
574 DEBUG_FUNCTION void
debug(pt_solution & ref)575 debug (pt_solution &ref)
576 {
577   dump_points_to_solution (stderr, &ref);
578 }
579 
580 DEBUG_FUNCTION void
debug(pt_solution * ptr)581 debug (pt_solution *ptr)
582 {
583   if (ptr)
584     debug (*ptr);
585   else
586     fprintf (stderr, "<nil>\n");
587 }
588 
589 
590 /* Dump points-to information for SSA_NAME PTR into FILE.  */
591 
592 void
dump_points_to_info_for(FILE * file,tree ptr)593 dump_points_to_info_for (FILE *file, tree ptr)
594 {
595   struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
596 
597   print_generic_expr (file, ptr, dump_flags);
598 
599   if (pi)
600     dump_points_to_solution (file, &pi->pt);
601   else
602     fprintf (file, ", points-to anything");
603 
604   fprintf (file, "\n");
605 }
606 
607 
608 /* Dump points-to information for VAR into stderr.  */
609 
610 DEBUG_FUNCTION void
debug_points_to_info_for(tree var)611 debug_points_to_info_for (tree var)
612 {
613   dump_points_to_info_for (stderr, var);
614 }
615 
616 
617 /* Initializes the alias-oracle reference representation *R from REF.  */
618 
619 void
ao_ref_init(ao_ref * r,tree ref)620 ao_ref_init (ao_ref *r, tree ref)
621 {
622   r->ref = ref;
623   r->base = NULL_TREE;
624   r->offset = 0;
625   r->size = -1;
626   r->max_size = -1;
627   r->ref_alias_set = -1;
628   r->base_alias_set = -1;
629   r->volatile_p = ref ? TREE_THIS_VOLATILE (ref) : false;
630 }
631 
632 /* Returns the base object of the memory reference *REF.  */
633 
634 tree
ao_ref_base(ao_ref * ref)635 ao_ref_base (ao_ref *ref)
636 {
637   bool reverse;
638 
639   if (ref->base)
640     return ref->base;
641   ref->base = get_ref_base_and_extent (ref->ref, &ref->offset, &ref->size,
642 				       &ref->max_size, &reverse);
643   return ref->base;
644 }
645 
646 /* Returns the base object alias set of the memory reference *REF.  */
647 
648 alias_set_type
ao_ref_base_alias_set(ao_ref * ref)649 ao_ref_base_alias_set (ao_ref *ref)
650 {
651   tree base_ref;
652   if (ref->base_alias_set != -1)
653     return ref->base_alias_set;
654   if (!ref->ref)
655     return 0;
656   base_ref = ref->ref;
657   while (handled_component_p (base_ref))
658     base_ref = TREE_OPERAND (base_ref, 0);
659   ref->base_alias_set = get_alias_set (base_ref);
660   return ref->base_alias_set;
661 }
662 
663 /* Returns the reference alias set of the memory reference *REF.  */
664 
665 alias_set_type
ao_ref_alias_set(ao_ref * ref)666 ao_ref_alias_set (ao_ref *ref)
667 {
668   if (ref->ref_alias_set != -1)
669     return ref->ref_alias_set;
670   ref->ref_alias_set = get_alias_set (ref->ref);
671   return ref->ref_alias_set;
672 }
673 
674 /* Init an alias-oracle reference representation from a gimple pointer
675    PTR and a gimple size SIZE in bytes.  If SIZE is NULL_TREE then the
676    size is assumed to be unknown.  The access is assumed to be only
677    to or after of the pointer target, not before it.  */
678 
679 void
ao_ref_init_from_ptr_and_size(ao_ref * ref,tree ptr,tree size)680 ao_ref_init_from_ptr_and_size (ao_ref *ref, tree ptr, tree size)
681 {
682   poly_int64 t, size_hwi, extra_offset = 0;
683   ref->ref = NULL_TREE;
684   if (TREE_CODE (ptr) == SSA_NAME)
685     {
686       gimple *stmt = SSA_NAME_DEF_STMT (ptr);
687       if (gimple_assign_single_p (stmt)
688 	  && gimple_assign_rhs_code (stmt) == ADDR_EXPR)
689 	ptr = gimple_assign_rhs1 (stmt);
690       else if (is_gimple_assign (stmt)
691 	       && gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
692 	       && ptrdiff_tree_p (gimple_assign_rhs2 (stmt), &extra_offset))
693 	{
694 	  ptr = gimple_assign_rhs1 (stmt);
695 	  extra_offset *= BITS_PER_UNIT;
696 	}
697     }
698 
699   if (TREE_CODE (ptr) == ADDR_EXPR)
700     {
701       ref->base = get_addr_base_and_unit_offset (TREE_OPERAND (ptr, 0), &t);
702       if (ref->base)
703 	ref->offset = BITS_PER_UNIT * t;
704       else
705 	{
706 	  size = NULL_TREE;
707 	  ref->offset = 0;
708 	  ref->base = get_base_address (TREE_OPERAND (ptr, 0));
709 	}
710     }
711   else
712     {
713       ref->base = build2 (MEM_REF, char_type_node,
714 			  ptr, null_pointer_node);
715       ref->offset = 0;
716     }
717   ref->offset += extra_offset;
718   if (size
719       && poly_int_tree_p (size, &size_hwi)
720       && coeffs_in_range_p (size_hwi, 0, HOST_WIDE_INT_MAX / BITS_PER_UNIT))
721     ref->max_size = ref->size = size_hwi * BITS_PER_UNIT;
722   else
723     ref->max_size = ref->size = -1;
724   ref->ref_alias_set = 0;
725   ref->base_alias_set = 0;
726   ref->volatile_p = false;
727 }
728 
729 /* Return 1 if TYPE1 and TYPE2 are to be considered equivalent for the
730    purpose of TBAA.  Return 0 if they are distinct and -1 if we cannot
731    decide.  */
732 
733 static inline int
same_type_for_tbaa(tree type1,tree type2)734 same_type_for_tbaa (tree type1, tree type2)
735 {
736   type1 = TYPE_MAIN_VARIANT (type1);
737   type2 = TYPE_MAIN_VARIANT (type2);
738 
739   /* If we would have to do structural comparison bail out.  */
740   if (TYPE_STRUCTURAL_EQUALITY_P (type1)
741       || TYPE_STRUCTURAL_EQUALITY_P (type2))
742     return -1;
743 
744   /* Compare the canonical types.  */
745   if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
746     return 1;
747 
748   /* ??? Array types are not properly unified in all cases as we have
749      spurious changes in the index types for example.  Removing this
750      causes all sorts of problems with the Fortran frontend.  */
751   if (TREE_CODE (type1) == ARRAY_TYPE
752       && TREE_CODE (type2) == ARRAY_TYPE)
753     return -1;
754 
755   /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
756      object of one of its constrained subtypes, e.g. when a function with an
757      unconstrained parameter passed by reference is called on an object and
758      inlined.  But, even in the case of a fixed size, type and subtypes are
759      not equivalent enough as to share the same TYPE_CANONICAL, since this
760      would mean that conversions between them are useless, whereas they are
761      not (e.g. type and subtypes can have different modes).  So, in the end,
762      they are only guaranteed to have the same alias set.  */
763   if (get_alias_set (type1) == get_alias_set (type2))
764     return -1;
765 
766   /* The types are known to be not equal.  */
767   return 0;
768 }
769 
770 /* Determine if the two component references REF1 and REF2 which are
771    based on access types TYPE1 and TYPE2 and of which at least one is based
772    on an indirect reference may alias.  REF2 is the only one that can
773    be a decl in which case REF2_IS_DECL is true.
774    REF1_ALIAS_SET, BASE1_ALIAS_SET, REF2_ALIAS_SET and BASE2_ALIAS_SET
775    are the respective alias sets.  */
776 
777 static bool
aliasing_component_refs_p(tree ref1,alias_set_type ref1_alias_set,alias_set_type base1_alias_set,poly_int64 offset1,poly_int64 max_size1,tree ref2,alias_set_type ref2_alias_set,alias_set_type base2_alias_set,poly_int64 offset2,poly_int64 max_size2,bool ref2_is_decl)778 aliasing_component_refs_p (tree ref1,
779 			   alias_set_type ref1_alias_set,
780 			   alias_set_type base1_alias_set,
781 			   poly_int64 offset1, poly_int64 max_size1,
782 			   tree ref2,
783 			   alias_set_type ref2_alias_set,
784 			   alias_set_type base2_alias_set,
785 			   poly_int64 offset2, poly_int64 max_size2,
786 			   bool ref2_is_decl)
787 {
788   /* If one reference is a component references through pointers try to find a
789      common base and apply offset based disambiguation.  This handles
790      for example
791        struct A { int i; int j; } *q;
792        struct B { struct A a; int k; } *p;
793      disambiguating q->i and p->a.j.  */
794   tree base1, base2;
795   tree type1, type2;
796   tree *refp;
797   int same_p;
798 
799   /* Choose bases and base types to search for.  */
800   base1 = ref1;
801   while (handled_component_p (base1))
802     base1 = TREE_OPERAND (base1, 0);
803   type1 = TREE_TYPE (base1);
804   base2 = ref2;
805   while (handled_component_p (base2))
806     base2 = TREE_OPERAND (base2, 0);
807   type2 = TREE_TYPE (base2);
808 
809   /* Now search for the type1 in the access path of ref2.  This
810      would be a common base for doing offset based disambiguation on.  */
811   refp = &ref2;
812   while (handled_component_p (*refp)
813 	 && same_type_for_tbaa (TREE_TYPE (*refp), type1) == 0)
814     refp = &TREE_OPERAND (*refp, 0);
815   same_p = same_type_for_tbaa (TREE_TYPE (*refp), type1);
816   /* If we couldn't compare types we have to bail out.  */
817   if (same_p == -1)
818     return true;
819   else if (same_p == 1)
820     {
821       poly_int64 offadj, sztmp, msztmp;
822       bool reverse;
823       get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse);
824       offset2 -= offadj;
825       get_ref_base_and_extent (base1, &offadj, &sztmp, &msztmp, &reverse);
826       offset1 -= offadj;
827       return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2);
828     }
829   /* If we didn't find a common base, try the other way around.  */
830   refp = &ref1;
831   while (handled_component_p (*refp)
832 	 && same_type_for_tbaa (TREE_TYPE (*refp), type2) == 0)
833     refp = &TREE_OPERAND (*refp, 0);
834   same_p = same_type_for_tbaa (TREE_TYPE (*refp), type2);
835   /* If we couldn't compare types we have to bail out.  */
836   if (same_p == -1)
837     return true;
838   else if (same_p == 1)
839     {
840       poly_int64 offadj, sztmp, msztmp;
841       bool reverse;
842       get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse);
843       offset1 -= offadj;
844       get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp, &reverse);
845       offset2 -= offadj;
846       return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2);
847     }
848 
849   /* If we have two type access paths B1.path1 and B2.path2 they may
850      only alias if either B1 is in B2.path2 or B2 is in B1.path1.
851      But we can still have a path that goes B1.path1...B2.path2 with
852      a part that we do not see.  So we can only disambiguate now
853      if there is no B2 in the tail of path1 and no B1 on the
854      tail of path2.  */
855   if (base1_alias_set == ref2_alias_set
856       || alias_set_subset_of (base1_alias_set, ref2_alias_set))
857     return true;
858   /* If this is ptr vs. decl then we know there is no ptr ... decl path.  */
859   if (!ref2_is_decl)
860     return (base2_alias_set == ref1_alias_set
861 	    || alias_set_subset_of (base2_alias_set, ref1_alias_set));
862   return false;
863 }
864 
865 /* Return true if we can determine that component references REF1 and REF2,
866    that are within a common DECL, cannot overlap.  */
867 
868 static bool
nonoverlapping_component_refs_of_decl_p(tree ref1,tree ref2)869 nonoverlapping_component_refs_of_decl_p (tree ref1, tree ref2)
870 {
871   auto_vec<tree, 16> component_refs1;
872   auto_vec<tree, 16> component_refs2;
873 
874   /* Create the stack of handled components for REF1.  */
875   while (handled_component_p (ref1))
876     {
877       component_refs1.safe_push (ref1);
878       ref1 = TREE_OPERAND (ref1, 0);
879     }
880   if (TREE_CODE (ref1) == MEM_REF)
881     {
882       if (!integer_zerop (TREE_OPERAND (ref1, 1)))
883 	return false;
884       ref1 = TREE_OPERAND (TREE_OPERAND (ref1, 0), 0);
885     }
886 
887   /* Create the stack of handled components for REF2.  */
888   while (handled_component_p (ref2))
889     {
890       component_refs2.safe_push (ref2);
891       ref2 = TREE_OPERAND (ref2, 0);
892     }
893   if (TREE_CODE (ref2) == MEM_REF)
894     {
895       if (!integer_zerop (TREE_OPERAND (ref2, 1)))
896 	return false;
897       ref2 = TREE_OPERAND (TREE_OPERAND (ref2, 0), 0);
898     }
899 
900   /* Bases must be either same or uncomparable.  */
901   gcc_checking_assert (ref1 == ref2
902 		       || (DECL_P (ref1) && DECL_P (ref2)
903 			   && compare_base_decls (ref1, ref2) != 0));
904 
905   /* Pop the stacks in parallel and examine the COMPONENT_REFs of the same
906      rank.  This is sufficient because we start from the same DECL and you
907      cannot reference several fields at a time with COMPONENT_REFs (unlike
908      with ARRAY_RANGE_REFs for arrays) so you always need the same number
909      of them to access a sub-component, unless you're in a union, in which
910      case the return value will precisely be false.  */
911   while (true)
912     {
913       do
914 	{
915 	  if (component_refs1.is_empty ())
916 	    return false;
917 	  ref1 = component_refs1.pop ();
918 	}
919       while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref1, 0))));
920 
921       do
922 	{
923 	  if (component_refs2.is_empty ())
924 	     return false;
925 	  ref2 = component_refs2.pop ();
926 	}
927       while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref2, 0))));
928 
929       /* Beware of BIT_FIELD_REF.  */
930       if (TREE_CODE (ref1) != COMPONENT_REF
931 	  || TREE_CODE (ref2) != COMPONENT_REF)
932 	return false;
933 
934       tree field1 = TREE_OPERAND (ref1, 1);
935       tree field2 = TREE_OPERAND (ref2, 1);
936 
937       /* ??? We cannot simply use the type of operand #0 of the refs here
938 	 as the Fortran compiler smuggles type punning into COMPONENT_REFs
939 	 for common blocks instead of using unions like everyone else.  */
940       tree type1 = DECL_CONTEXT (field1);
941       tree type2 = DECL_CONTEXT (field2);
942 
943       /* We cannot disambiguate fields in a union or qualified union.  */
944       if (type1 != type2 || TREE_CODE (type1) != RECORD_TYPE)
945 	 return false;
946 
947       if (field1 != field2)
948 	{
949 	  /* A field and its representative need to be considered the
950 	     same.  */
951 	  if (DECL_BIT_FIELD_REPRESENTATIVE (field1) == field2
952 	      || DECL_BIT_FIELD_REPRESENTATIVE (field2) == field1)
953 	    return false;
954 	  /* Different fields of the same record type cannot overlap.
955 	     ??? Bitfields can overlap at RTL level so punt on them.  */
956 	  if (DECL_BIT_FIELD (field1) && DECL_BIT_FIELD (field2))
957 	    return false;
958 	  return true;
959 	}
960     }
961 
962   return false;
963 }
964 
965 /* qsort compare function to sort FIELD_DECLs after their
966    DECL_FIELD_CONTEXT TYPE_UID.  */
967 
968 static inline int
ncr_compar(const void * field1_,const void * field2_)969 ncr_compar (const void *field1_, const void *field2_)
970 {
971   const_tree field1 = *(const_tree *) const_cast <void *>(field1_);
972   const_tree field2 = *(const_tree *) const_cast <void *>(field2_);
973   unsigned int uid1 = TYPE_UID (DECL_FIELD_CONTEXT (field1));
974   unsigned int uid2 = TYPE_UID (DECL_FIELD_CONTEXT (field2));
975   if (uid1 < uid2)
976     return -1;
977   else if (uid1 > uid2)
978     return 1;
979   return 0;
980 }
981 
982 /* Return true if we can determine that the fields referenced cannot
983    overlap for any pair of objects.  */
984 
985 static bool
nonoverlapping_component_refs_p(const_tree x,const_tree y)986 nonoverlapping_component_refs_p (const_tree x, const_tree y)
987 {
988   if (!flag_strict_aliasing
989       || !x || !y
990       || TREE_CODE (x) != COMPONENT_REF
991       || TREE_CODE (y) != COMPONENT_REF)
992     return false;
993 
994   auto_vec<const_tree, 16> fieldsx;
995   while (TREE_CODE (x) == COMPONENT_REF)
996     {
997       tree field = TREE_OPERAND (x, 1);
998       tree type = DECL_FIELD_CONTEXT (field);
999       if (TREE_CODE (type) == RECORD_TYPE)
1000 	fieldsx.safe_push (field);
1001       x = TREE_OPERAND (x, 0);
1002     }
1003   if (fieldsx.length () == 0)
1004     return false;
1005   auto_vec<const_tree, 16> fieldsy;
1006   while (TREE_CODE (y) == COMPONENT_REF)
1007     {
1008       tree field = TREE_OPERAND (y, 1);
1009       tree type = DECL_FIELD_CONTEXT (field);
1010       if (TREE_CODE (type) == RECORD_TYPE)
1011 	fieldsy.safe_push (TREE_OPERAND (y, 1));
1012       y = TREE_OPERAND (y, 0);
1013     }
1014   if (fieldsy.length () == 0)
1015     return false;
1016 
1017   /* Most common case first.  */
1018   if (fieldsx.length () == 1
1019       && fieldsy.length () == 1)
1020     return ((DECL_FIELD_CONTEXT (fieldsx[0])
1021 	     == DECL_FIELD_CONTEXT (fieldsy[0]))
1022 	    && fieldsx[0] != fieldsy[0]
1023 	    && !(DECL_BIT_FIELD (fieldsx[0]) && DECL_BIT_FIELD (fieldsy[0])));
1024 
1025   if (fieldsx.length () == 2)
1026     {
1027       if (ncr_compar (&fieldsx[0], &fieldsx[1]) == 1)
1028 	std::swap (fieldsx[0], fieldsx[1]);
1029     }
1030   else
1031     fieldsx.qsort (ncr_compar);
1032 
1033   if (fieldsy.length () == 2)
1034     {
1035       if (ncr_compar (&fieldsy[0], &fieldsy[1]) == 1)
1036 	std::swap (fieldsy[0], fieldsy[1]);
1037     }
1038   else
1039     fieldsy.qsort (ncr_compar);
1040 
1041   unsigned i = 0, j = 0;
1042   do
1043     {
1044       const_tree fieldx = fieldsx[i];
1045       const_tree fieldy = fieldsy[j];
1046       tree typex = DECL_FIELD_CONTEXT (fieldx);
1047       tree typey = DECL_FIELD_CONTEXT (fieldy);
1048       if (typex == typey)
1049 	{
1050 	  /* We're left with accessing different fields of a structure,
1051 	     no possible overlap.  */
1052 	  if (fieldx != fieldy)
1053 	    {
1054 	      /* A field and its representative need to be considered the
1055 		 same.  */
1056 	      if (DECL_BIT_FIELD_REPRESENTATIVE (fieldx) == fieldy
1057 		  || DECL_BIT_FIELD_REPRESENTATIVE (fieldy) == fieldx)
1058 		return false;
1059 	      /* Different fields of the same record type cannot overlap.
1060 		 ??? Bitfields can overlap at RTL level so punt on them.  */
1061 	      if (DECL_BIT_FIELD (fieldx) && DECL_BIT_FIELD (fieldy))
1062 		return false;
1063 	      return true;
1064 	    }
1065 	}
1066       if (TYPE_UID (typex) < TYPE_UID (typey))
1067 	{
1068 	  i++;
1069 	  if (i == fieldsx.length ())
1070 	    break;
1071 	}
1072       else
1073 	{
1074 	  j++;
1075 	  if (j == fieldsy.length ())
1076 	    break;
1077 	}
1078     }
1079   while (1);
1080 
1081   return false;
1082 }
1083 
1084 
1085 /* Return true if two memory references based on the variables BASE1
1086    and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
1087    [OFFSET2, OFFSET2 + MAX_SIZE2) may alias.  REF1 and REF2
1088    if non-NULL are the complete memory reference trees.  */
1089 
1090 static bool
decl_refs_may_alias_p(tree ref1,tree base1,poly_int64 offset1,poly_int64 max_size1,tree ref2,tree base2,poly_int64 offset2,poly_int64 max_size2)1091 decl_refs_may_alias_p (tree ref1, tree base1,
1092 		       poly_int64 offset1, poly_int64 max_size1,
1093 		       tree ref2, tree base2,
1094 		       poly_int64 offset2, poly_int64 max_size2)
1095 {
1096   gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
1097 
1098   /* If both references are based on different variables, they cannot alias.  */
1099   if (compare_base_decls (base1, base2) == 0)
1100     return false;
1101 
1102   /* If both references are based on the same variable, they cannot alias if
1103      the accesses do not overlap.  */
1104   if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
1105     return false;
1106 
1107   /* For components with variable position, the above test isn't sufficient,
1108      so we disambiguate component references manually.  */
1109   if (ref1 && ref2
1110       && handled_component_p (ref1) && handled_component_p (ref2)
1111       && nonoverlapping_component_refs_of_decl_p (ref1, ref2))
1112     return false;
1113 
1114   return true;
1115 }
1116 
1117 /* Return true if an indirect reference based on *PTR1 constrained
1118    to [OFFSET1, OFFSET1 + MAX_SIZE1) may alias a variable based on BASE2
1119    constrained to [OFFSET2, OFFSET2 + MAX_SIZE2).  *PTR1 and BASE2 have
1120    the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
1121    in which case they are computed on-demand.  REF1 and REF2
1122    if non-NULL are the complete memory reference trees.  */
1123 
1124 static bool
indirect_ref_may_alias_decl_p(tree ref1 ATTRIBUTE_UNUSED,tree base1,poly_int64 offset1,poly_int64 max_size1,alias_set_type ref1_alias_set,alias_set_type base1_alias_set,tree ref2 ATTRIBUTE_UNUSED,tree base2,poly_int64 offset2,poly_int64 max_size2,alias_set_type ref2_alias_set,alias_set_type base2_alias_set,bool tbaa_p)1125 indirect_ref_may_alias_decl_p (tree ref1 ATTRIBUTE_UNUSED, tree base1,
1126 			       poly_int64 offset1, poly_int64 max_size1,
1127 			       alias_set_type ref1_alias_set,
1128 			       alias_set_type base1_alias_set,
1129 			       tree ref2 ATTRIBUTE_UNUSED, tree base2,
1130 			       poly_int64 offset2, poly_int64 max_size2,
1131 			       alias_set_type ref2_alias_set,
1132 			       alias_set_type base2_alias_set, bool tbaa_p)
1133 {
1134   tree ptr1;
1135   tree ptrtype1, dbase2;
1136 
1137   gcc_checking_assert ((TREE_CODE (base1) == MEM_REF
1138 			|| TREE_CODE (base1) == TARGET_MEM_REF)
1139 		       && DECL_P (base2));
1140 
1141   ptr1 = TREE_OPERAND (base1, 0);
1142   poly_offset_int moff = mem_ref_offset (base1) << LOG2_BITS_PER_UNIT;
1143 
1144   /* If only one reference is based on a variable, they cannot alias if
1145      the pointer access is beyond the extent of the variable access.
1146      (the pointer base cannot validly point to an offset less than zero
1147      of the variable).
1148      ???  IVOPTs creates bases that do not honor this restriction,
1149      so do not apply this optimization for TARGET_MEM_REFs.  */
1150   if (TREE_CODE (base1) != TARGET_MEM_REF
1151       && !ranges_maybe_overlap_p (offset1 + moff, -1, offset2, max_size2))
1152     return false;
1153   /* They also cannot alias if the pointer may not point to the decl.  */
1154   if (!ptr_deref_may_alias_decl_p (ptr1, base2))
1155     return false;
1156 
1157   /* Disambiguations that rely on strict aliasing rules follow.  */
1158   if (!flag_strict_aliasing || !tbaa_p)
1159     return true;
1160 
1161   ptrtype1 = TREE_TYPE (TREE_OPERAND (base1, 1));
1162 
1163   /* If the alias set for a pointer access is zero all bets are off.  */
1164   if (base1_alias_set == 0)
1165     return true;
1166 
1167   /* When we are trying to disambiguate an access with a pointer dereference
1168      as base versus one with a decl as base we can use both the size
1169      of the decl and its dynamic type for extra disambiguation.
1170      ???  We do not know anything about the dynamic type of the decl
1171      other than that its alias-set contains base2_alias_set as a subset
1172      which does not help us here.  */
1173   /* As we know nothing useful about the dynamic type of the decl just
1174      use the usual conflict check rather than a subset test.
1175      ???  We could introduce -fvery-strict-aliasing when the language
1176      does not allow decls to have a dynamic type that differs from their
1177      static type.  Then we can check
1178      !alias_set_subset_of (base1_alias_set, base2_alias_set) instead.  */
1179   if (base1_alias_set != base2_alias_set
1180       && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
1181     return false;
1182   /* If the size of the access relevant for TBAA through the pointer
1183      is bigger than the size of the decl we can't possibly access the
1184      decl via that pointer.  */
1185   if (DECL_SIZE (base2) && COMPLETE_TYPE_P (TREE_TYPE (ptrtype1))
1186       && poly_int_tree_p (DECL_SIZE (base2))
1187       && poly_int_tree_p (TYPE_SIZE (TREE_TYPE (ptrtype1)))
1188       /* ???  This in turn may run afoul when a decl of type T which is
1189 	 a member of union type U is accessed through a pointer to
1190 	 type U and sizeof T is smaller than sizeof U.  */
1191       && TREE_CODE (TREE_TYPE (ptrtype1)) != UNION_TYPE
1192       && TREE_CODE (TREE_TYPE (ptrtype1)) != QUAL_UNION_TYPE
1193       && known_lt (wi::to_poly_widest (DECL_SIZE (base2)),
1194 		   wi::to_poly_widest (TYPE_SIZE (TREE_TYPE (ptrtype1)))))
1195     return false;
1196 
1197   if (!ref2)
1198     return true;
1199 
1200   /* If the decl is accessed via a MEM_REF, reconstruct the base
1201      we can use for TBAA and an appropriately adjusted offset.  */
1202   dbase2 = ref2;
1203   while (handled_component_p (dbase2))
1204     dbase2 = TREE_OPERAND (dbase2, 0);
1205   poly_int64 doffset1 = offset1;
1206   poly_offset_int doffset2 = offset2;
1207   if (TREE_CODE (dbase2) == MEM_REF
1208       || TREE_CODE (dbase2) == TARGET_MEM_REF)
1209     doffset2 -= mem_ref_offset (dbase2) << LOG2_BITS_PER_UNIT;
1210 
1211   /* If either reference is view-converted, give up now.  */
1212   if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) != 1
1213       || same_type_for_tbaa (TREE_TYPE (dbase2), TREE_TYPE (base2)) != 1)
1214     return true;
1215 
1216   /* If both references are through the same type, they do not alias
1217      if the accesses do not overlap.  This does extra disambiguation
1218      for mixed/pointer accesses but requires strict aliasing.
1219      For MEM_REFs we require that the component-ref offset we computed
1220      is relative to the start of the type which we ensure by
1221      comparing rvalue and access type and disregarding the constant
1222      pointer offset.  */
1223   if ((TREE_CODE (base1) != TARGET_MEM_REF
1224        || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
1225       && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (dbase2)) == 1)
1226     return ranges_maybe_overlap_p (doffset1, max_size1, doffset2, max_size2);
1227 
1228   if (ref1 && ref2
1229       && nonoverlapping_component_refs_p (ref1, ref2))
1230     return false;
1231 
1232   /* Do access-path based disambiguation.  */
1233   if (ref1 && ref2
1234       && (handled_component_p (ref1) || handled_component_p (ref2)))
1235     return aliasing_component_refs_p (ref1,
1236 				      ref1_alias_set, base1_alias_set,
1237 				      offset1, max_size1,
1238 				      ref2,
1239 				      ref2_alias_set, base2_alias_set,
1240 				      offset2, max_size2, true);
1241 
1242   return true;
1243 }
1244 
1245 /* Return true if two indirect references based on *PTR1
1246    and *PTR2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
1247    [OFFSET2, OFFSET2 + MAX_SIZE2) may alias.  *PTR1 and *PTR2 have
1248    the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
1249    in which case they are computed on-demand.  REF1 and REF2
1250    if non-NULL are the complete memory reference trees. */
1251 
1252 static bool
indirect_refs_may_alias_p(tree ref1 ATTRIBUTE_UNUSED,tree base1,poly_int64 offset1,poly_int64 max_size1,alias_set_type ref1_alias_set,alias_set_type base1_alias_set,tree ref2 ATTRIBUTE_UNUSED,tree base2,poly_int64 offset2,poly_int64 max_size2,alias_set_type ref2_alias_set,alias_set_type base2_alias_set,bool tbaa_p)1253 indirect_refs_may_alias_p (tree ref1 ATTRIBUTE_UNUSED, tree base1,
1254 			   poly_int64 offset1, poly_int64 max_size1,
1255 			   alias_set_type ref1_alias_set,
1256 			   alias_set_type base1_alias_set,
1257 			   tree ref2 ATTRIBUTE_UNUSED, tree base2,
1258 			   poly_int64 offset2, poly_int64 max_size2,
1259 			   alias_set_type ref2_alias_set,
1260 			   alias_set_type base2_alias_set, bool tbaa_p)
1261 {
1262   tree ptr1;
1263   tree ptr2;
1264   tree ptrtype1, ptrtype2;
1265 
1266   gcc_checking_assert ((TREE_CODE (base1) == MEM_REF
1267 			|| TREE_CODE (base1) == TARGET_MEM_REF)
1268 		       && (TREE_CODE (base2) == MEM_REF
1269 			   || TREE_CODE (base2) == TARGET_MEM_REF));
1270 
1271   ptr1 = TREE_OPERAND (base1, 0);
1272   ptr2 = TREE_OPERAND (base2, 0);
1273 
1274   /* If both bases are based on pointers they cannot alias if they may not
1275      point to the same memory object or if they point to the same object
1276      and the accesses do not overlap.  */
1277   if ((!cfun || gimple_in_ssa_p (cfun))
1278       && operand_equal_p (ptr1, ptr2, 0)
1279       && (((TREE_CODE (base1) != TARGET_MEM_REF
1280 	    || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
1281 	   && (TREE_CODE (base2) != TARGET_MEM_REF
1282 	       || (!TMR_INDEX (base2) && !TMR_INDEX2 (base2))))
1283 	  || (TREE_CODE (base1) == TARGET_MEM_REF
1284 	      && TREE_CODE (base2) == TARGET_MEM_REF
1285 	      && (TMR_STEP (base1) == TMR_STEP (base2)
1286 		  || (TMR_STEP (base1) && TMR_STEP (base2)
1287 		      && operand_equal_p (TMR_STEP (base1),
1288 					  TMR_STEP (base2), 0)))
1289 	      && (TMR_INDEX (base1) == TMR_INDEX (base2)
1290 		  || (TMR_INDEX (base1) && TMR_INDEX (base2)
1291 		      && operand_equal_p (TMR_INDEX (base1),
1292 					  TMR_INDEX (base2), 0)))
1293 	      && (TMR_INDEX2 (base1) == TMR_INDEX2 (base2)
1294 		  || (TMR_INDEX2 (base1) && TMR_INDEX2 (base2)
1295 		      && operand_equal_p (TMR_INDEX2 (base1),
1296 					  TMR_INDEX2 (base2), 0))))))
1297     {
1298       poly_offset_int moff1 = mem_ref_offset (base1) << LOG2_BITS_PER_UNIT;
1299       poly_offset_int moff2 = mem_ref_offset (base2) << LOG2_BITS_PER_UNIT;
1300       return ranges_maybe_overlap_p (offset1 + moff1, max_size1,
1301 				     offset2 + moff2, max_size2);
1302     }
1303   if (!ptr_derefs_may_alias_p (ptr1, ptr2))
1304     return false;
1305 
1306   /* Disambiguations that rely on strict aliasing rules follow.  */
1307   if (!flag_strict_aliasing || !tbaa_p)
1308     return true;
1309 
1310   ptrtype1 = TREE_TYPE (TREE_OPERAND (base1, 1));
1311   ptrtype2 = TREE_TYPE (TREE_OPERAND (base2, 1));
1312 
1313   /* If the alias set for a pointer access is zero all bets are off.  */
1314   if (base1_alias_set == 0
1315       || base2_alias_set == 0)
1316     return true;
1317 
1318   /* If both references are through the same type, they do not alias
1319      if the accesses do not overlap.  This does extra disambiguation
1320      for mixed/pointer accesses but requires strict aliasing.  */
1321   if ((TREE_CODE (base1) != TARGET_MEM_REF
1322        || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
1323       && (TREE_CODE (base2) != TARGET_MEM_REF
1324 	  || (!TMR_INDEX (base2) && !TMR_INDEX2 (base2)))
1325       && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) == 1
1326       && same_type_for_tbaa (TREE_TYPE (base2), TREE_TYPE (ptrtype2)) == 1
1327       && same_type_for_tbaa (TREE_TYPE (ptrtype1),
1328 			     TREE_TYPE (ptrtype2)) == 1
1329       /* But avoid treating arrays as "objects", instead assume they
1330          can overlap by an exact multiple of their element size.  */
1331       && TREE_CODE (TREE_TYPE (ptrtype1)) != ARRAY_TYPE)
1332     return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2);
1333 
1334   /* Do type-based disambiguation.  */
1335   if (base1_alias_set != base2_alias_set
1336       && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
1337     return false;
1338 
1339   /* If either reference is view-converted, give up now.  */
1340   if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) != 1
1341       || same_type_for_tbaa (TREE_TYPE (base2), TREE_TYPE (ptrtype2)) != 1)
1342     return true;
1343 
1344   if (ref1 && ref2
1345       && nonoverlapping_component_refs_p (ref1, ref2))
1346     return false;
1347 
1348   /* Do access-path based disambiguation.  */
1349   if (ref1 && ref2
1350       && (handled_component_p (ref1) || handled_component_p (ref2)))
1351     return aliasing_component_refs_p (ref1,
1352 				      ref1_alias_set, base1_alias_set,
1353 				      offset1, max_size1,
1354 				      ref2,
1355 				      ref2_alias_set, base2_alias_set,
1356 				      offset2, max_size2, false);
1357 
1358   return true;
1359 }
1360 
1361 /* Return true, if the two memory references REF1 and REF2 may alias.  */
1362 
1363 bool
refs_may_alias_p_1(ao_ref * ref1,ao_ref * ref2,bool tbaa_p)1364 refs_may_alias_p_1 (ao_ref *ref1, ao_ref *ref2, bool tbaa_p)
1365 {
1366   tree base1, base2;
1367   poly_int64 offset1 = 0, offset2 = 0;
1368   poly_int64 max_size1 = -1, max_size2 = -1;
1369   bool var1_p, var2_p, ind1_p, ind2_p;
1370 
1371   gcc_checking_assert ((!ref1->ref
1372 			|| TREE_CODE (ref1->ref) == SSA_NAME
1373 			|| DECL_P (ref1->ref)
1374 			|| TREE_CODE (ref1->ref) == STRING_CST
1375 			|| handled_component_p (ref1->ref)
1376 			|| TREE_CODE (ref1->ref) == MEM_REF
1377 			|| TREE_CODE (ref1->ref) == TARGET_MEM_REF)
1378 		       && (!ref2->ref
1379 			   || TREE_CODE (ref2->ref) == SSA_NAME
1380 			   || DECL_P (ref2->ref)
1381 			   || TREE_CODE (ref2->ref) == STRING_CST
1382 			   || handled_component_p (ref2->ref)
1383 			   || TREE_CODE (ref2->ref) == MEM_REF
1384 			   || TREE_CODE (ref2->ref) == TARGET_MEM_REF));
1385 
1386   /* Decompose the references into their base objects and the access.  */
1387   base1 = ao_ref_base (ref1);
1388   offset1 = ref1->offset;
1389   max_size1 = ref1->max_size;
1390   base2 = ao_ref_base (ref2);
1391   offset2 = ref2->offset;
1392   max_size2 = ref2->max_size;
1393 
1394   /* We can end up with registers or constants as bases for example from
1395      *D.1663_44 = VIEW_CONVERT_EXPR<struct DB_LSN>(__tmp$B0F64_59);
1396      which is seen as a struct copy.  */
1397   if (TREE_CODE (base1) == SSA_NAME
1398       || TREE_CODE (base1) == CONST_DECL
1399       || TREE_CODE (base1) == CONSTRUCTOR
1400       || TREE_CODE (base1) == ADDR_EXPR
1401       || CONSTANT_CLASS_P (base1)
1402       || TREE_CODE (base2) == SSA_NAME
1403       || TREE_CODE (base2) == CONST_DECL
1404       || TREE_CODE (base2) == CONSTRUCTOR
1405       || TREE_CODE (base2) == ADDR_EXPR
1406       || CONSTANT_CLASS_P (base2))
1407     return false;
1408 
1409   /* We can end up referring to code via function and label decls.
1410      As we likely do not properly track code aliases conservatively
1411      bail out.  */
1412   if (TREE_CODE (base1) == FUNCTION_DECL
1413       || TREE_CODE (base1) == LABEL_DECL
1414       || TREE_CODE (base2) == FUNCTION_DECL
1415       || TREE_CODE (base2) == LABEL_DECL)
1416     return true;
1417 
1418   /* Two volatile accesses always conflict.  */
1419   if (ref1->volatile_p
1420       && ref2->volatile_p)
1421     return true;
1422 
1423   /* Defer to simple offset based disambiguation if we have
1424      references based on two decls.  Do this before defering to
1425      TBAA to handle must-alias cases in conformance with the
1426      GCC extension of allowing type-punning through unions.  */
1427   var1_p = DECL_P (base1);
1428   var2_p = DECL_P (base2);
1429   if (var1_p && var2_p)
1430     return decl_refs_may_alias_p (ref1->ref, base1, offset1, max_size1,
1431 				  ref2->ref, base2, offset2, max_size2);
1432 
1433   /* Handle restrict based accesses.
1434      ???  ao_ref_base strips inner MEM_REF [&decl], recover from that
1435      here.  */
1436   tree rbase1 = base1;
1437   tree rbase2 = base2;
1438   if (var1_p)
1439     {
1440       rbase1 = ref1->ref;
1441       if (rbase1)
1442 	while (handled_component_p (rbase1))
1443 	  rbase1 = TREE_OPERAND (rbase1, 0);
1444     }
1445   if (var2_p)
1446     {
1447       rbase2 = ref2->ref;
1448       if (rbase2)
1449 	while (handled_component_p (rbase2))
1450 	  rbase2 = TREE_OPERAND (rbase2, 0);
1451     }
1452   if (rbase1 && rbase2
1453       && (TREE_CODE (base1) == MEM_REF || TREE_CODE (base1) == TARGET_MEM_REF)
1454       && (TREE_CODE (base2) == MEM_REF || TREE_CODE (base2) == TARGET_MEM_REF)
1455       /* If the accesses are in the same restrict clique... */
1456       && MR_DEPENDENCE_CLIQUE (base1) == MR_DEPENDENCE_CLIQUE (base2)
1457       /* But based on different pointers they do not alias.  */
1458       && MR_DEPENDENCE_BASE (base1) != MR_DEPENDENCE_BASE (base2))
1459     return false;
1460 
1461   ind1_p = (TREE_CODE (base1) == MEM_REF
1462 	    || TREE_CODE (base1) == TARGET_MEM_REF);
1463   ind2_p = (TREE_CODE (base2) == MEM_REF
1464 	    || TREE_CODE (base2) == TARGET_MEM_REF);
1465 
1466   /* Canonicalize the pointer-vs-decl case.  */
1467   if (ind1_p && var2_p)
1468     {
1469       std::swap (offset1, offset2);
1470       std::swap (max_size1, max_size2);
1471       std::swap (base1, base2);
1472       std::swap (ref1, ref2);
1473       var1_p = true;
1474       ind1_p = false;
1475       var2_p = false;
1476       ind2_p = true;
1477     }
1478 
1479   /* First defer to TBAA if possible.  */
1480   if (tbaa_p
1481       && flag_strict_aliasing
1482       && !alias_sets_conflict_p (ao_ref_alias_set (ref1),
1483 				 ao_ref_alias_set (ref2)))
1484     return false;
1485 
1486   /* Dispatch to the pointer-vs-decl or pointer-vs-pointer disambiguators.  */
1487   if (var1_p && ind2_p)
1488     return indirect_ref_may_alias_decl_p (ref2->ref, base2,
1489 					  offset2, max_size2,
1490 					  ao_ref_alias_set (ref2),
1491 					  ao_ref_base_alias_set (ref2),
1492 					  ref1->ref, base1,
1493 					  offset1, max_size1,
1494 					  ao_ref_alias_set (ref1),
1495 					  ao_ref_base_alias_set (ref1),
1496 					  tbaa_p);
1497   else if (ind1_p && ind2_p)
1498     return indirect_refs_may_alias_p (ref1->ref, base1,
1499 				      offset1, max_size1,
1500 				      ao_ref_alias_set (ref1),
1501 				      ao_ref_base_alias_set (ref1),
1502 				      ref2->ref, base2,
1503 				      offset2, max_size2,
1504 				      ao_ref_alias_set (ref2),
1505 				      ao_ref_base_alias_set (ref2),
1506 				      tbaa_p);
1507 
1508   gcc_unreachable ();
1509 }
1510 
1511 static bool
refs_may_alias_p(tree ref1,ao_ref * ref2)1512 refs_may_alias_p (tree ref1, ao_ref *ref2)
1513 {
1514   ao_ref r1;
1515   ao_ref_init (&r1, ref1);
1516   return refs_may_alias_p_1 (&r1, ref2, true);
1517 }
1518 
1519 bool
refs_may_alias_p(tree ref1,tree ref2)1520 refs_may_alias_p (tree ref1, tree ref2)
1521 {
1522   ao_ref r1, r2;
1523   bool res;
1524   ao_ref_init (&r1, ref1);
1525   ao_ref_init (&r2, ref2);
1526   res = refs_may_alias_p_1 (&r1, &r2, true);
1527   if (res)
1528     ++alias_stats.refs_may_alias_p_may_alias;
1529   else
1530     ++alias_stats.refs_may_alias_p_no_alias;
1531   return res;
1532 }
1533 
1534 /* Returns true if there is a anti-dependence for the STORE that
1535    executes after the LOAD.  */
1536 
1537 bool
refs_anti_dependent_p(tree load,tree store)1538 refs_anti_dependent_p (tree load, tree store)
1539 {
1540   ao_ref r1, r2;
1541   ao_ref_init (&r1, load);
1542   ao_ref_init (&r2, store);
1543   return refs_may_alias_p_1 (&r1, &r2, false);
1544 }
1545 
1546 /* Returns true if there is a output dependence for the stores
1547    STORE1 and STORE2.  */
1548 
1549 bool
refs_output_dependent_p(tree store1,tree store2)1550 refs_output_dependent_p (tree store1, tree store2)
1551 {
1552   ao_ref r1, r2;
1553   ao_ref_init (&r1, store1);
1554   ao_ref_init (&r2, store2);
1555   return refs_may_alias_p_1 (&r1, &r2, false);
1556 }
1557 
1558 /* If the call CALL may use the memory reference REF return true,
1559    otherwise return false.  */
1560 
1561 static bool
ref_maybe_used_by_call_p_1(gcall * call,ao_ref * ref)1562 ref_maybe_used_by_call_p_1 (gcall *call, ao_ref *ref)
1563 {
1564   tree base, callee;
1565   unsigned i;
1566   int flags = gimple_call_flags (call);
1567 
1568   /* Const functions without a static chain do not implicitly use memory.  */
1569   if (!gimple_call_chain (call)
1570       && (flags & (ECF_CONST|ECF_NOVOPS)))
1571     goto process_args;
1572 
1573   base = ao_ref_base (ref);
1574   if (!base)
1575     return true;
1576 
1577   /* A call that is not without side-effects might involve volatile
1578      accesses and thus conflicts with all other volatile accesses.  */
1579   if (ref->volatile_p)
1580     return true;
1581 
1582   /* If the reference is based on a decl that is not aliased the call
1583      cannot possibly use it.  */
1584   if (DECL_P (base)
1585       && !may_be_aliased (base)
1586       /* But local statics can be used through recursion.  */
1587       && !is_global_var (base))
1588     goto process_args;
1589 
1590   callee = gimple_call_fndecl (call);
1591 
1592   /* Handle those builtin functions explicitly that do not act as
1593      escape points.  See tree-ssa-structalias.c:find_func_aliases
1594      for the list of builtins we might need to handle here.  */
1595   if (callee != NULL_TREE
1596       && gimple_call_builtin_p (call, BUILT_IN_NORMAL))
1597     switch (DECL_FUNCTION_CODE (callee))
1598       {
1599 	/* All the following functions read memory pointed to by
1600 	   their second argument.  strcat/strncat additionally
1601 	   reads memory pointed to by the first argument.  */
1602 	case BUILT_IN_STRCAT:
1603 	case BUILT_IN_STRNCAT:
1604 	  {
1605 	    ao_ref dref;
1606 	    ao_ref_init_from_ptr_and_size (&dref,
1607 					   gimple_call_arg (call, 0),
1608 					   NULL_TREE);
1609 	    if (refs_may_alias_p_1 (&dref, ref, false))
1610 	      return true;
1611 	  }
1612 	  /* FALLTHRU */
1613 	case BUILT_IN_STRCPY:
1614 	case BUILT_IN_STRNCPY:
1615 	case BUILT_IN_MEMCPY:
1616 	case BUILT_IN_MEMMOVE:
1617 	case BUILT_IN_MEMPCPY:
1618 	case BUILT_IN_STPCPY:
1619 	case BUILT_IN_STPNCPY:
1620 	case BUILT_IN_TM_MEMCPY:
1621 	case BUILT_IN_TM_MEMMOVE:
1622 	  {
1623 	    ao_ref dref;
1624 	    tree size = NULL_TREE;
1625 	    if (gimple_call_num_args (call) == 3)
1626 	      size = gimple_call_arg (call, 2);
1627 	    ao_ref_init_from_ptr_and_size (&dref,
1628 					   gimple_call_arg (call, 1),
1629 					   size);
1630 	    return refs_may_alias_p_1 (&dref, ref, false);
1631 	  }
1632 	case BUILT_IN_STRCAT_CHK:
1633 	case BUILT_IN_STRNCAT_CHK:
1634 	  {
1635 	    ao_ref dref;
1636 	    ao_ref_init_from_ptr_and_size (&dref,
1637 					   gimple_call_arg (call, 0),
1638 					   NULL_TREE);
1639 	    if (refs_may_alias_p_1 (&dref, ref, false))
1640 	      return true;
1641 	  }
1642 	  /* FALLTHRU */
1643 	case BUILT_IN_STRCPY_CHK:
1644 	case BUILT_IN_STRNCPY_CHK:
1645 	case BUILT_IN_MEMCPY_CHK:
1646 	case BUILT_IN_MEMMOVE_CHK:
1647 	case BUILT_IN_MEMPCPY_CHK:
1648 	case BUILT_IN_STPCPY_CHK:
1649 	case BUILT_IN_STPNCPY_CHK:
1650 	  {
1651 	    ao_ref dref;
1652 	    tree size = NULL_TREE;
1653 	    if (gimple_call_num_args (call) == 4)
1654 	      size = gimple_call_arg (call, 2);
1655 	    ao_ref_init_from_ptr_and_size (&dref,
1656 					   gimple_call_arg (call, 1),
1657 					   size);
1658 	    return refs_may_alias_p_1 (&dref, ref, false);
1659 	  }
1660 	case BUILT_IN_BCOPY:
1661 	  {
1662 	    ao_ref dref;
1663 	    tree size = gimple_call_arg (call, 2);
1664 	    ao_ref_init_from_ptr_and_size (&dref,
1665 					   gimple_call_arg (call, 0),
1666 					   size);
1667 	    return refs_may_alias_p_1 (&dref, ref, false);
1668 	  }
1669 
1670 	/* The following functions read memory pointed to by their
1671 	   first argument.  */
1672 	CASE_BUILT_IN_TM_LOAD (1):
1673 	CASE_BUILT_IN_TM_LOAD (2):
1674 	CASE_BUILT_IN_TM_LOAD (4):
1675 	CASE_BUILT_IN_TM_LOAD (8):
1676 	CASE_BUILT_IN_TM_LOAD (FLOAT):
1677 	CASE_BUILT_IN_TM_LOAD (DOUBLE):
1678 	CASE_BUILT_IN_TM_LOAD (LDOUBLE):
1679 	CASE_BUILT_IN_TM_LOAD (M64):
1680 	CASE_BUILT_IN_TM_LOAD (M128):
1681 	CASE_BUILT_IN_TM_LOAD (M256):
1682 	case BUILT_IN_TM_LOG:
1683 	case BUILT_IN_TM_LOG_1:
1684 	case BUILT_IN_TM_LOG_2:
1685 	case BUILT_IN_TM_LOG_4:
1686 	case BUILT_IN_TM_LOG_8:
1687 	case BUILT_IN_TM_LOG_FLOAT:
1688 	case BUILT_IN_TM_LOG_DOUBLE:
1689 	case BUILT_IN_TM_LOG_LDOUBLE:
1690 	case BUILT_IN_TM_LOG_M64:
1691 	case BUILT_IN_TM_LOG_M128:
1692 	case BUILT_IN_TM_LOG_M256:
1693 	  return ptr_deref_may_alias_ref_p_1 (gimple_call_arg (call, 0), ref);
1694 
1695 	/* These read memory pointed to by the first argument.  */
1696 	case BUILT_IN_STRDUP:
1697 	case BUILT_IN_STRNDUP:
1698 	case BUILT_IN_REALLOC:
1699 	  {
1700 	    ao_ref dref;
1701 	    tree size = NULL_TREE;
1702 	    if (gimple_call_num_args (call) == 2)
1703 	      size = gimple_call_arg (call, 1);
1704 	    ao_ref_init_from_ptr_and_size (&dref,
1705 					   gimple_call_arg (call, 0),
1706 					   size);
1707 	    return refs_may_alias_p_1 (&dref, ref, false);
1708 	  }
1709 	/* These read memory pointed to by the first argument.  */
1710 	case BUILT_IN_INDEX:
1711 	case BUILT_IN_STRCHR:
1712 	case BUILT_IN_STRRCHR:
1713 	  {
1714 	    ao_ref dref;
1715 	    ao_ref_init_from_ptr_and_size (&dref,
1716 					   gimple_call_arg (call, 0),
1717 					   NULL_TREE);
1718 	    return refs_may_alias_p_1 (&dref, ref, false);
1719 	  }
1720 	/* These read memory pointed to by the first argument with size
1721 	   in the third argument.  */
1722 	case BUILT_IN_MEMCHR:
1723 	  {
1724 	    ao_ref dref;
1725 	    ao_ref_init_from_ptr_and_size (&dref,
1726 					   gimple_call_arg (call, 0),
1727 					   gimple_call_arg (call, 2));
1728 	    return refs_may_alias_p_1 (&dref, ref, false);
1729 	  }
1730 	/* These read memory pointed to by the first and second arguments.  */
1731 	case BUILT_IN_STRSTR:
1732 	case BUILT_IN_STRPBRK:
1733 	  {
1734 	    ao_ref dref;
1735 	    ao_ref_init_from_ptr_and_size (&dref,
1736 					   gimple_call_arg (call, 0),
1737 					   NULL_TREE);
1738 	    if (refs_may_alias_p_1 (&dref, ref, false))
1739 	      return true;
1740 	    ao_ref_init_from_ptr_and_size (&dref,
1741 					   gimple_call_arg (call, 1),
1742 					   NULL_TREE);
1743 	    return refs_may_alias_p_1 (&dref, ref, false);
1744 	  }
1745 
1746 	/* The following builtins do not read from memory.  */
1747 	case BUILT_IN_FREE:
1748 	case BUILT_IN_MALLOC:
1749 	case BUILT_IN_POSIX_MEMALIGN:
1750 	case BUILT_IN_ALIGNED_ALLOC:
1751 	case BUILT_IN_CALLOC:
1752 	CASE_BUILT_IN_ALLOCA:
1753 	case BUILT_IN_STACK_SAVE:
1754 	case BUILT_IN_STACK_RESTORE:
1755 	case BUILT_IN_MEMSET:
1756 	case BUILT_IN_TM_MEMSET:
1757 	case BUILT_IN_MEMSET_CHK:
1758 	case BUILT_IN_FREXP:
1759 	case BUILT_IN_FREXPF:
1760 	case BUILT_IN_FREXPL:
1761 	case BUILT_IN_GAMMA_R:
1762 	case BUILT_IN_GAMMAF_R:
1763 	case BUILT_IN_GAMMAL_R:
1764 	case BUILT_IN_LGAMMA_R:
1765 	case BUILT_IN_LGAMMAF_R:
1766 	case BUILT_IN_LGAMMAL_R:
1767 	case BUILT_IN_MODF:
1768 	case BUILT_IN_MODFF:
1769 	case BUILT_IN_MODFL:
1770 	case BUILT_IN_REMQUO:
1771 	case BUILT_IN_REMQUOF:
1772 	case BUILT_IN_REMQUOL:
1773 	case BUILT_IN_SINCOS:
1774 	case BUILT_IN_SINCOSF:
1775 	case BUILT_IN_SINCOSL:
1776 	case BUILT_IN_ASSUME_ALIGNED:
1777 	case BUILT_IN_VA_END:
1778 	  return false;
1779 	/* __sync_* builtins and some OpenMP builtins act as threading
1780 	   barriers.  */
1781 #undef DEF_SYNC_BUILTIN
1782 #define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
1783 #include "sync-builtins.def"
1784 #undef DEF_SYNC_BUILTIN
1785 	case BUILT_IN_GOMP_ATOMIC_START:
1786 	case BUILT_IN_GOMP_ATOMIC_END:
1787 	case BUILT_IN_GOMP_BARRIER:
1788 	case BUILT_IN_GOMP_BARRIER_CANCEL:
1789 	case BUILT_IN_GOMP_TASKWAIT:
1790 	case BUILT_IN_GOMP_TASKGROUP_END:
1791 	case BUILT_IN_GOMP_CRITICAL_START:
1792 	case BUILT_IN_GOMP_CRITICAL_END:
1793 	case BUILT_IN_GOMP_CRITICAL_NAME_START:
1794 	case BUILT_IN_GOMP_CRITICAL_NAME_END:
1795 	case BUILT_IN_GOMP_LOOP_END:
1796 	case BUILT_IN_GOMP_LOOP_END_CANCEL:
1797 	case BUILT_IN_GOMP_ORDERED_START:
1798 	case BUILT_IN_GOMP_ORDERED_END:
1799 	case BUILT_IN_GOMP_SECTIONS_END:
1800 	case BUILT_IN_GOMP_SECTIONS_END_CANCEL:
1801 	case BUILT_IN_GOMP_SINGLE_COPY_START:
1802 	case BUILT_IN_GOMP_SINGLE_COPY_END:
1803 	  return true;
1804 
1805 	default:
1806 	  /* Fallthru to general call handling.  */;
1807       }
1808 
1809   /* Check if base is a global static variable that is not read
1810      by the function.  */
1811   if (callee != NULL_TREE && VAR_P (base) && TREE_STATIC (base))
1812     {
1813       struct cgraph_node *node = cgraph_node::get (callee);
1814       bitmap not_read;
1815 
1816       /* FIXME: Callee can be an OMP builtin that does not have a call graph
1817 	 node yet.  We should enforce that there are nodes for all decls in the
1818 	 IL and remove this check instead.  */
1819       if (node
1820 	  && (not_read = ipa_reference_get_not_read_global (node))
1821 	  && bitmap_bit_p (not_read, ipa_reference_var_uid (base)))
1822 	goto process_args;
1823     }
1824 
1825   /* Check if the base variable is call-used.  */
1826   if (DECL_P (base))
1827     {
1828       if (pt_solution_includes (gimple_call_use_set (call), base))
1829 	return true;
1830     }
1831   else if ((TREE_CODE (base) == MEM_REF
1832 	    || TREE_CODE (base) == TARGET_MEM_REF)
1833 	   && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
1834     {
1835       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0));
1836       if (!pi)
1837 	return true;
1838 
1839       if (pt_solutions_intersect (gimple_call_use_set (call), &pi->pt))
1840 	return true;
1841     }
1842   else
1843     return true;
1844 
1845   /* Inspect call arguments for passed-by-value aliases.  */
1846 process_args:
1847   for (i = 0; i < gimple_call_num_args (call); ++i)
1848     {
1849       tree op = gimple_call_arg (call, i);
1850       int flags = gimple_call_arg_flags (call, i);
1851 
1852       if (flags & EAF_UNUSED)
1853 	continue;
1854 
1855       if (TREE_CODE (op) == WITH_SIZE_EXPR)
1856 	op = TREE_OPERAND (op, 0);
1857 
1858       if (TREE_CODE (op) != SSA_NAME
1859 	  && !is_gimple_min_invariant (op))
1860 	{
1861 	  ao_ref r;
1862 	  ao_ref_init (&r, op);
1863 	  if (refs_may_alias_p_1 (&r, ref, true))
1864 	    return true;
1865 	}
1866     }
1867 
1868   return false;
1869 }
1870 
1871 static bool
ref_maybe_used_by_call_p(gcall * call,ao_ref * ref)1872 ref_maybe_used_by_call_p (gcall *call, ao_ref *ref)
1873 {
1874   bool res;
1875   res = ref_maybe_used_by_call_p_1 (call, ref);
1876   if (res)
1877     ++alias_stats.ref_maybe_used_by_call_p_may_alias;
1878   else
1879     ++alias_stats.ref_maybe_used_by_call_p_no_alias;
1880   return res;
1881 }
1882 
1883 
1884 /* If the statement STMT may use the memory reference REF return
1885    true, otherwise return false.  */
1886 
1887 bool
ref_maybe_used_by_stmt_p(gimple * stmt,ao_ref * ref)1888 ref_maybe_used_by_stmt_p (gimple *stmt, ao_ref *ref)
1889 {
1890   if (is_gimple_assign (stmt))
1891     {
1892       tree rhs;
1893 
1894       /* All memory assign statements are single.  */
1895       if (!gimple_assign_single_p (stmt))
1896 	return false;
1897 
1898       rhs = gimple_assign_rhs1 (stmt);
1899       if (is_gimple_reg (rhs)
1900 	  || is_gimple_min_invariant (rhs)
1901 	  || gimple_assign_rhs_code (stmt) == CONSTRUCTOR)
1902 	return false;
1903 
1904       return refs_may_alias_p (rhs, ref);
1905     }
1906   else if (is_gimple_call (stmt))
1907     return ref_maybe_used_by_call_p (as_a <gcall *> (stmt), ref);
1908   else if (greturn *return_stmt = dyn_cast <greturn *> (stmt))
1909     {
1910       tree retval = gimple_return_retval (return_stmt);
1911       if (retval
1912 	  && TREE_CODE (retval) != SSA_NAME
1913 	  && !is_gimple_min_invariant (retval)
1914 	  && refs_may_alias_p (retval, ref))
1915 	return true;
1916       /* If ref escapes the function then the return acts as a use.  */
1917       tree base = ao_ref_base (ref);
1918       if (!base)
1919 	;
1920       else if (DECL_P (base))
1921 	return is_global_var (base);
1922       else if (TREE_CODE (base) == MEM_REF
1923 	       || TREE_CODE (base) == TARGET_MEM_REF)
1924 	return ptr_deref_may_alias_global_p (TREE_OPERAND (base, 0));
1925       return false;
1926     }
1927 
1928   return true;
1929 }
1930 
1931 bool
ref_maybe_used_by_stmt_p(gimple * stmt,tree ref)1932 ref_maybe_used_by_stmt_p (gimple *stmt, tree ref)
1933 {
1934   ao_ref r;
1935   ao_ref_init (&r, ref);
1936   return ref_maybe_used_by_stmt_p (stmt, &r);
1937 }
1938 
1939 /* If the call in statement CALL may clobber the memory reference REF
1940    return true, otherwise return false.  */
1941 
1942 bool
call_may_clobber_ref_p_1(gcall * call,ao_ref * ref)1943 call_may_clobber_ref_p_1 (gcall *call, ao_ref *ref)
1944 {
1945   tree base;
1946   tree callee;
1947 
1948   /* If the call is pure or const it cannot clobber anything.  */
1949   if (gimple_call_flags (call)
1950       & (ECF_PURE|ECF_CONST|ECF_LOOPING_CONST_OR_PURE|ECF_NOVOPS))
1951     return false;
1952   if (gimple_call_internal_p (call))
1953     switch (gimple_call_internal_fn (call))
1954       {
1955 	/* Treat these internal calls like ECF_PURE for aliasing,
1956 	   they don't write to any memory the program should care about.
1957 	   They have important other side-effects, and read memory,
1958 	   so can't be ECF_NOVOPS.  */
1959       case IFN_UBSAN_NULL:
1960       case IFN_UBSAN_BOUNDS:
1961       case IFN_UBSAN_VPTR:
1962       case IFN_UBSAN_OBJECT_SIZE:
1963       case IFN_UBSAN_PTR:
1964       case IFN_ASAN_CHECK:
1965 	return false;
1966       default:
1967 	break;
1968       }
1969 
1970   base = ao_ref_base (ref);
1971   if (!base)
1972     return true;
1973 
1974   if (TREE_CODE (base) == SSA_NAME
1975       || CONSTANT_CLASS_P (base))
1976     return false;
1977 
1978   /* A call that is not without side-effects might involve volatile
1979      accesses and thus conflicts with all other volatile accesses.  */
1980   if (ref->volatile_p)
1981     return true;
1982 
1983   /* If the reference is based on a decl that is not aliased the call
1984      cannot possibly clobber it.  */
1985   if (DECL_P (base)
1986       && !may_be_aliased (base)
1987       /* But local non-readonly statics can be modified through recursion
1988          or the call may implement a threading barrier which we must
1989 	 treat as may-def.  */
1990       && (TREE_READONLY (base)
1991 	  || !is_global_var (base)))
1992     return false;
1993 
1994   callee = gimple_call_fndecl (call);
1995 
1996   /* Handle those builtin functions explicitly that do not act as
1997      escape points.  See tree-ssa-structalias.c:find_func_aliases
1998      for the list of builtins we might need to handle here.  */
1999   if (callee != NULL_TREE
2000       && gimple_call_builtin_p (call, BUILT_IN_NORMAL))
2001     switch (DECL_FUNCTION_CODE (callee))
2002       {
2003 	/* All the following functions clobber memory pointed to by
2004 	   their first argument.  */
2005 	case BUILT_IN_STRCPY:
2006 	case BUILT_IN_STRNCPY:
2007 	case BUILT_IN_MEMCPY:
2008 	case BUILT_IN_MEMMOVE:
2009 	case BUILT_IN_MEMPCPY:
2010 	case BUILT_IN_STPCPY:
2011 	case BUILT_IN_STPNCPY:
2012 	case BUILT_IN_STRCAT:
2013 	case BUILT_IN_STRNCAT:
2014 	case BUILT_IN_MEMSET:
2015 	case BUILT_IN_TM_MEMSET:
2016 	CASE_BUILT_IN_TM_STORE (1):
2017 	CASE_BUILT_IN_TM_STORE (2):
2018 	CASE_BUILT_IN_TM_STORE (4):
2019 	CASE_BUILT_IN_TM_STORE (8):
2020 	CASE_BUILT_IN_TM_STORE (FLOAT):
2021 	CASE_BUILT_IN_TM_STORE (DOUBLE):
2022 	CASE_BUILT_IN_TM_STORE (LDOUBLE):
2023 	CASE_BUILT_IN_TM_STORE (M64):
2024 	CASE_BUILT_IN_TM_STORE (M128):
2025 	CASE_BUILT_IN_TM_STORE (M256):
2026 	case BUILT_IN_TM_MEMCPY:
2027 	case BUILT_IN_TM_MEMMOVE:
2028 	  {
2029 	    ao_ref dref;
2030 	    tree size = NULL_TREE;
2031 	    /* Don't pass in size for strncat, as the maximum size
2032 	       is strlen (dest) + n + 1 instead of n, resp.
2033 	       n + 1 at dest + strlen (dest), but strlen (dest) isn't
2034 	       known.  */
2035 	    if (gimple_call_num_args (call) == 3
2036 		&& DECL_FUNCTION_CODE (callee) != BUILT_IN_STRNCAT)
2037 	      size = gimple_call_arg (call, 2);
2038 	    ao_ref_init_from_ptr_and_size (&dref,
2039 					   gimple_call_arg (call, 0),
2040 					   size);
2041 	    return refs_may_alias_p_1 (&dref, ref, false);
2042 	  }
2043 	case BUILT_IN_STRCPY_CHK:
2044 	case BUILT_IN_STRNCPY_CHK:
2045 	case BUILT_IN_MEMCPY_CHK:
2046 	case BUILT_IN_MEMMOVE_CHK:
2047 	case BUILT_IN_MEMPCPY_CHK:
2048 	case BUILT_IN_STPCPY_CHK:
2049 	case BUILT_IN_STPNCPY_CHK:
2050 	case BUILT_IN_STRCAT_CHK:
2051 	case BUILT_IN_STRNCAT_CHK:
2052 	case BUILT_IN_MEMSET_CHK:
2053 	  {
2054 	    ao_ref dref;
2055 	    tree size = NULL_TREE;
2056 	    /* Don't pass in size for __strncat_chk, as the maximum size
2057 	       is strlen (dest) + n + 1 instead of n, resp.
2058 	       n + 1 at dest + strlen (dest), but strlen (dest) isn't
2059 	       known.  */
2060 	    if (gimple_call_num_args (call) == 4
2061 		&& DECL_FUNCTION_CODE (callee) != BUILT_IN_STRNCAT_CHK)
2062 	      size = gimple_call_arg (call, 2);
2063 	    ao_ref_init_from_ptr_and_size (&dref,
2064 					   gimple_call_arg (call, 0),
2065 					   size);
2066 	    return refs_may_alias_p_1 (&dref, ref, false);
2067 	  }
2068 	case BUILT_IN_BCOPY:
2069 	  {
2070 	    ao_ref dref;
2071 	    tree size = gimple_call_arg (call, 2);
2072 	    ao_ref_init_from_ptr_and_size (&dref,
2073 					   gimple_call_arg (call, 1),
2074 					   size);
2075 	    return refs_may_alias_p_1 (&dref, ref, false);
2076 	  }
2077 	/* Allocating memory does not have any side-effects apart from
2078 	   being the definition point for the pointer.  */
2079 	case BUILT_IN_MALLOC:
2080 	case BUILT_IN_ALIGNED_ALLOC:
2081 	case BUILT_IN_CALLOC:
2082 	case BUILT_IN_STRDUP:
2083 	case BUILT_IN_STRNDUP:
2084 	  /* Unix98 specifies that errno is set on allocation failure.  */
2085 	  if (flag_errno_math
2086 	      && targetm.ref_may_alias_errno (ref))
2087 	    return true;
2088 	  return false;
2089 	case BUILT_IN_STACK_SAVE:
2090 	CASE_BUILT_IN_ALLOCA:
2091 	case BUILT_IN_ASSUME_ALIGNED:
2092 	  return false;
2093 	/* But posix_memalign stores a pointer into the memory pointed to
2094 	   by its first argument.  */
2095 	case BUILT_IN_POSIX_MEMALIGN:
2096 	  {
2097 	    tree ptrptr = gimple_call_arg (call, 0);
2098 	    ao_ref dref;
2099 	    ao_ref_init_from_ptr_and_size (&dref, ptrptr,
2100 					   TYPE_SIZE_UNIT (ptr_type_node));
2101 	    return (refs_may_alias_p_1 (&dref, ref, false)
2102 		    || (flag_errno_math
2103 			&& targetm.ref_may_alias_errno (ref)));
2104 	  }
2105 	/* Freeing memory kills the pointed-to memory.  More importantly
2106 	   the call has to serve as a barrier for moving loads and stores
2107 	   across it.  */
2108 	case BUILT_IN_FREE:
2109 	case BUILT_IN_VA_END:
2110 	  {
2111 	    tree ptr = gimple_call_arg (call, 0);
2112 	    return ptr_deref_may_alias_ref_p_1 (ptr, ref);
2113 	  }
2114 	/* Realloc serves both as allocation point and deallocation point.  */
2115 	case BUILT_IN_REALLOC:
2116 	  {
2117 	    tree ptr = gimple_call_arg (call, 0);
2118 	    /* Unix98 specifies that errno is set on allocation failure.  */
2119 	    return ((flag_errno_math
2120 		     && targetm.ref_may_alias_errno (ref))
2121 		    || ptr_deref_may_alias_ref_p_1 (ptr, ref));
2122 	  }
2123 	case BUILT_IN_GAMMA_R:
2124 	case BUILT_IN_GAMMAF_R:
2125 	case BUILT_IN_GAMMAL_R:
2126 	case BUILT_IN_LGAMMA_R:
2127 	case BUILT_IN_LGAMMAF_R:
2128 	case BUILT_IN_LGAMMAL_R:
2129 	  {
2130 	    tree out = gimple_call_arg (call, 1);
2131 	    if (ptr_deref_may_alias_ref_p_1 (out, ref))
2132 	      return true;
2133 	    if (flag_errno_math)
2134 	      break;
2135 	    return false;
2136 	  }
2137 	case BUILT_IN_FREXP:
2138 	case BUILT_IN_FREXPF:
2139 	case BUILT_IN_FREXPL:
2140 	case BUILT_IN_MODF:
2141 	case BUILT_IN_MODFF:
2142 	case BUILT_IN_MODFL:
2143 	  {
2144 	    tree out = gimple_call_arg (call, 1);
2145 	    return ptr_deref_may_alias_ref_p_1 (out, ref);
2146 	  }
2147 	case BUILT_IN_REMQUO:
2148 	case BUILT_IN_REMQUOF:
2149 	case BUILT_IN_REMQUOL:
2150 	  {
2151 	    tree out = gimple_call_arg (call, 2);
2152 	    if (ptr_deref_may_alias_ref_p_1 (out, ref))
2153 	      return true;
2154 	    if (flag_errno_math)
2155 	      break;
2156 	    return false;
2157 	  }
2158 	case BUILT_IN_SINCOS:
2159 	case BUILT_IN_SINCOSF:
2160 	case BUILT_IN_SINCOSL:
2161 	  {
2162 	    tree sin = gimple_call_arg (call, 1);
2163 	    tree cos = gimple_call_arg (call, 2);
2164 	    return (ptr_deref_may_alias_ref_p_1 (sin, ref)
2165 		    || ptr_deref_may_alias_ref_p_1 (cos, ref));
2166 	  }
2167 	/* __sync_* builtins and some OpenMP builtins act as threading
2168 	   barriers.  */
2169 #undef DEF_SYNC_BUILTIN
2170 #define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
2171 #include "sync-builtins.def"
2172 #undef DEF_SYNC_BUILTIN
2173 	case BUILT_IN_GOMP_ATOMIC_START:
2174 	case BUILT_IN_GOMP_ATOMIC_END:
2175 	case BUILT_IN_GOMP_BARRIER:
2176 	case BUILT_IN_GOMP_BARRIER_CANCEL:
2177 	case BUILT_IN_GOMP_TASKWAIT:
2178 	case BUILT_IN_GOMP_TASKGROUP_END:
2179 	case BUILT_IN_GOMP_CRITICAL_START:
2180 	case BUILT_IN_GOMP_CRITICAL_END:
2181 	case BUILT_IN_GOMP_CRITICAL_NAME_START:
2182 	case BUILT_IN_GOMP_CRITICAL_NAME_END:
2183 	case BUILT_IN_GOMP_LOOP_END:
2184 	case BUILT_IN_GOMP_LOOP_END_CANCEL:
2185 	case BUILT_IN_GOMP_ORDERED_START:
2186 	case BUILT_IN_GOMP_ORDERED_END:
2187 	case BUILT_IN_GOMP_SECTIONS_END:
2188 	case BUILT_IN_GOMP_SECTIONS_END_CANCEL:
2189 	case BUILT_IN_GOMP_SINGLE_COPY_START:
2190 	case BUILT_IN_GOMP_SINGLE_COPY_END:
2191 	  return true;
2192 	default:
2193 	  /* Fallthru to general call handling.  */;
2194       }
2195 
2196   /* Check if base is a global static variable that is not written
2197      by the function.  */
2198   if (callee != NULL_TREE && VAR_P (base) && TREE_STATIC (base))
2199     {
2200       struct cgraph_node *node = cgraph_node::get (callee);
2201       bitmap not_written;
2202 
2203       if (node
2204 	  && (not_written = ipa_reference_get_not_written_global (node))
2205 	  && bitmap_bit_p (not_written, ipa_reference_var_uid (base)))
2206 	return false;
2207     }
2208 
2209   /* Check if the base variable is call-clobbered.  */
2210   if (DECL_P (base))
2211     return pt_solution_includes (gimple_call_clobber_set (call), base);
2212   else if ((TREE_CODE (base) == MEM_REF
2213 	    || TREE_CODE (base) == TARGET_MEM_REF)
2214 	   && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
2215     {
2216       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0));
2217       if (!pi)
2218 	return true;
2219 
2220       return pt_solutions_intersect (gimple_call_clobber_set (call), &pi->pt);
2221     }
2222 
2223   return true;
2224 }
2225 
2226 /* If the call in statement CALL may clobber the memory reference REF
2227    return true, otherwise return false.  */
2228 
2229 bool
call_may_clobber_ref_p(gcall * call,tree ref)2230 call_may_clobber_ref_p (gcall *call, tree ref)
2231 {
2232   bool res;
2233   ao_ref r;
2234   ao_ref_init (&r, ref);
2235   res = call_may_clobber_ref_p_1 (call, &r);
2236   if (res)
2237     ++alias_stats.call_may_clobber_ref_p_may_alias;
2238   else
2239     ++alias_stats.call_may_clobber_ref_p_no_alias;
2240   return res;
2241 }
2242 
2243 
2244 /* If the statement STMT may clobber the memory reference REF return true,
2245    otherwise return false.  */
2246 
2247 bool
stmt_may_clobber_ref_p_1(gimple * stmt,ao_ref * ref)2248 stmt_may_clobber_ref_p_1 (gimple *stmt, ao_ref *ref)
2249 {
2250   if (is_gimple_call (stmt))
2251     {
2252       tree lhs = gimple_call_lhs (stmt);
2253       if (lhs
2254 	  && TREE_CODE (lhs) != SSA_NAME)
2255 	{
2256 	  ao_ref r;
2257 	  ao_ref_init (&r, lhs);
2258 	  if (refs_may_alias_p_1 (ref, &r, true))
2259 	    return true;
2260 	}
2261 
2262       return call_may_clobber_ref_p_1 (as_a <gcall *> (stmt), ref);
2263     }
2264   else if (gimple_assign_single_p (stmt))
2265     {
2266       tree lhs = gimple_assign_lhs (stmt);
2267       if (TREE_CODE (lhs) != SSA_NAME)
2268 	{
2269 	  ao_ref r;
2270 	  ao_ref_init (&r, lhs);
2271 	  return refs_may_alias_p_1 (ref, &r, true);
2272 	}
2273     }
2274   else if (gimple_code (stmt) == GIMPLE_ASM)
2275     return true;
2276 
2277   return false;
2278 }
2279 
2280 bool
stmt_may_clobber_ref_p(gimple * stmt,tree ref)2281 stmt_may_clobber_ref_p (gimple *stmt, tree ref)
2282 {
2283   ao_ref r;
2284   ao_ref_init (&r, ref);
2285   return stmt_may_clobber_ref_p_1 (stmt, &r);
2286 }
2287 
2288 /* Return true if store1 and store2 described by corresponding tuples
2289    <BASE, OFFSET, SIZE, MAX_SIZE> have the same size and store to the same
2290    address.  */
2291 
2292 static bool
same_addr_size_stores_p(tree base1,poly_int64 offset1,poly_int64 size1,poly_int64 max_size1,tree base2,poly_int64 offset2,poly_int64 size2,poly_int64 max_size2)2293 same_addr_size_stores_p (tree base1, poly_int64 offset1, poly_int64 size1,
2294 			 poly_int64 max_size1,
2295 			 tree base2, poly_int64 offset2, poly_int64 size2,
2296 			 poly_int64 max_size2)
2297 {
2298   /* Offsets need to be 0.  */
2299   if (maybe_ne (offset1, 0)
2300       || maybe_ne (offset2, 0))
2301     return false;
2302 
2303   bool base1_obj_p = SSA_VAR_P (base1);
2304   bool base2_obj_p = SSA_VAR_P (base2);
2305 
2306   /* We need one object.  */
2307   if (base1_obj_p == base2_obj_p)
2308     return false;
2309   tree obj = base1_obj_p ? base1 : base2;
2310 
2311   /* And we need one MEM_REF.  */
2312   bool base1_memref_p = TREE_CODE (base1) == MEM_REF;
2313   bool base2_memref_p = TREE_CODE (base2) == MEM_REF;
2314   if (base1_memref_p == base2_memref_p)
2315     return false;
2316   tree memref = base1_memref_p ? base1 : base2;
2317 
2318   /* Sizes need to be valid.  */
2319   if (!known_size_p (max_size1)
2320       || !known_size_p (max_size2)
2321       || !known_size_p (size1)
2322       || !known_size_p (size2))
2323     return false;
2324 
2325   /* Max_size needs to match size.  */
2326   if (maybe_ne (max_size1, size1)
2327       || maybe_ne (max_size2, size2))
2328     return false;
2329 
2330   /* Sizes need to match.  */
2331   if (maybe_ne (size1, size2))
2332     return false;
2333 
2334 
2335   /* Check that memref is a store to pointer with singleton points-to info.  */
2336   if (!integer_zerop (TREE_OPERAND (memref, 1)))
2337     return false;
2338   tree ptr = TREE_OPERAND (memref, 0);
2339   if (TREE_CODE (ptr) != SSA_NAME)
2340     return false;
2341   struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
2342   unsigned int pt_uid;
2343   if (pi == NULL
2344       || !pt_solution_singleton_or_null_p (&pi->pt, &pt_uid))
2345     return false;
2346 
2347   /* Be conservative with non-call exceptions when the address might
2348      be NULL.  */
2349   if (cfun->can_throw_non_call_exceptions && pi->pt.null)
2350     return false;
2351 
2352   /* Check that ptr points relative to obj.  */
2353   unsigned int obj_uid = DECL_PT_UID (obj);
2354   if (obj_uid != pt_uid)
2355     return false;
2356 
2357   /* Check that the object size is the same as the store size.  That ensures us
2358      that ptr points to the start of obj.  */
2359   return (DECL_SIZE (obj)
2360 	  && poly_int_tree_p (DECL_SIZE (obj))
2361 	  && known_eq (wi::to_poly_offset (DECL_SIZE (obj)), size1));
2362 }
2363 
2364 /* If STMT kills the memory reference REF return true, otherwise
2365    return false.  */
2366 
2367 bool
stmt_kills_ref_p(gimple * stmt,ao_ref * ref)2368 stmt_kills_ref_p (gimple *stmt, ao_ref *ref)
2369 {
2370   if (!ao_ref_base (ref))
2371     return false;
2372 
2373   if (gimple_has_lhs (stmt)
2374       && TREE_CODE (gimple_get_lhs (stmt)) != SSA_NAME
2375       /* The assignment is not necessarily carried out if it can throw
2376 	 and we can catch it in the current function where we could inspect
2377 	 the previous value.
2378 	 ???  We only need to care about the RHS throwing.  For aggregate
2379 	 assignments or similar calls and non-call exceptions the LHS
2380 	 might throw as well.  */
2381       && !stmt_can_throw_internal (stmt))
2382     {
2383       tree lhs = gimple_get_lhs (stmt);
2384       /* If LHS is literally a base of the access we are done.  */
2385       if (ref->ref)
2386 	{
2387 	  tree base = ref->ref;
2388 	  tree innermost_dropped_array_ref = NULL_TREE;
2389 	  if (handled_component_p (base))
2390 	    {
2391 	      tree saved_lhs0 = NULL_TREE;
2392 	      if (handled_component_p (lhs))
2393 		{
2394 		  saved_lhs0 = TREE_OPERAND (lhs, 0);
2395 		  TREE_OPERAND (lhs, 0) = integer_zero_node;
2396 		}
2397 	      do
2398 		{
2399 		  /* Just compare the outermost handled component, if
2400 		     they are equal we have found a possible common
2401 		     base.  */
2402 		  tree saved_base0 = TREE_OPERAND (base, 0);
2403 		  TREE_OPERAND (base, 0) = integer_zero_node;
2404 		  bool res = operand_equal_p (lhs, base, 0);
2405 		  TREE_OPERAND (base, 0) = saved_base0;
2406 		  if (res)
2407 		    break;
2408 		  /* Remember if we drop an array-ref that we need to
2409 		     double-check not being at struct end.  */
2410 		  if (TREE_CODE (base) == ARRAY_REF
2411 		      || TREE_CODE (base) == ARRAY_RANGE_REF)
2412 		    innermost_dropped_array_ref = base;
2413 		  /* Otherwise drop handled components of the access.  */
2414 		  base = saved_base0;
2415 		}
2416 	      while (handled_component_p (base));
2417 	      if (saved_lhs0)
2418 		TREE_OPERAND (lhs, 0) = saved_lhs0;
2419 	    }
2420 	  /* Finally check if the lhs has the same address and size as the
2421 	     base candidate of the access.  Watch out if we have dropped
2422 	     an array-ref that was at struct end, this means ref->ref may
2423 	     be outside of the TYPE_SIZE of its base.  */
2424 	  if ((! innermost_dropped_array_ref
2425 	       || ! array_at_struct_end_p (innermost_dropped_array_ref))
2426 	      && (lhs == base
2427 		  || (((TYPE_SIZE (TREE_TYPE (lhs))
2428 			== TYPE_SIZE (TREE_TYPE (base)))
2429 		       || (TYPE_SIZE (TREE_TYPE (lhs))
2430 			   && TYPE_SIZE (TREE_TYPE (base))
2431 			   && operand_equal_p (TYPE_SIZE (TREE_TYPE (lhs)),
2432 					       TYPE_SIZE (TREE_TYPE (base)),
2433 					       0)))
2434 		      && operand_equal_p (lhs, base,
2435 					  OEP_ADDRESS_OF
2436 					  | OEP_MATCH_SIDE_EFFECTS))))
2437 	    return true;
2438 	}
2439 
2440       /* Now look for non-literal equal bases with the restriction of
2441          handling constant offset and size.  */
2442       /* For a must-alias check we need to be able to constrain
2443 	 the access properly.  */
2444       if (!ref->max_size_known_p ())
2445 	return false;
2446       poly_int64 size, offset, max_size, ref_offset = ref->offset;
2447       bool reverse;
2448       tree base = get_ref_base_and_extent (lhs, &offset, &size, &max_size,
2449 					   &reverse);
2450       /* We can get MEM[symbol: sZ, index: D.8862_1] here,
2451 	 so base == ref->base does not always hold.  */
2452       if (base != ref->base)
2453 	{
2454 	  /* Try using points-to info.  */
2455 	  if (same_addr_size_stores_p (base, offset, size, max_size, ref->base,
2456 				       ref->offset, ref->size, ref->max_size))
2457 	    return true;
2458 
2459 	  /* If both base and ref->base are MEM_REFs, only compare the
2460 	     first operand, and if the second operand isn't equal constant,
2461 	     try to add the offsets into offset and ref_offset.  */
2462 	  if (TREE_CODE (base) == MEM_REF && TREE_CODE (ref->base) == MEM_REF
2463 	      && TREE_OPERAND (base, 0) == TREE_OPERAND (ref->base, 0))
2464 	    {
2465 	      if (!tree_int_cst_equal (TREE_OPERAND (base, 1),
2466 				       TREE_OPERAND (ref->base, 1)))
2467 		{
2468 		  poly_offset_int off1 = mem_ref_offset (base);
2469 		  off1 <<= LOG2_BITS_PER_UNIT;
2470 		  off1 += offset;
2471 		  poly_offset_int off2 = mem_ref_offset (ref->base);
2472 		  off2 <<= LOG2_BITS_PER_UNIT;
2473 		  off2 += ref_offset;
2474 		  if (!off1.to_shwi (&offset) || !off2.to_shwi (&ref_offset))
2475 		    size = -1;
2476 		}
2477 	    }
2478 	  else
2479 	    size = -1;
2480 	}
2481       /* For a must-alias check we need to be able to constrain
2482 	 the access properly.  */
2483       if (known_eq (size, max_size)
2484 	  && known_subrange_p (ref_offset, ref->max_size, offset, size))
2485 	return true;
2486     }
2487 
2488   if (is_gimple_call (stmt))
2489     {
2490       tree callee = gimple_call_fndecl (stmt);
2491       if (callee != NULL_TREE
2492 	  && gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
2493 	switch (DECL_FUNCTION_CODE (callee))
2494 	  {
2495 	  case BUILT_IN_FREE:
2496 	    {
2497 	      tree ptr = gimple_call_arg (stmt, 0);
2498 	      tree base = ao_ref_base (ref);
2499 	      if (base && TREE_CODE (base) == MEM_REF
2500 		  && TREE_OPERAND (base, 0) == ptr)
2501 		return true;
2502 	      break;
2503 	    }
2504 
2505 	  case BUILT_IN_MEMCPY:
2506 	  case BUILT_IN_MEMPCPY:
2507 	  case BUILT_IN_MEMMOVE:
2508 	  case BUILT_IN_MEMSET:
2509 	  case BUILT_IN_MEMCPY_CHK:
2510 	  case BUILT_IN_MEMPCPY_CHK:
2511 	  case BUILT_IN_MEMMOVE_CHK:
2512 	  case BUILT_IN_MEMSET_CHK:
2513 	  case BUILT_IN_STRNCPY:
2514 	  case BUILT_IN_STPNCPY:
2515 	    {
2516 	      /* For a must-alias check we need to be able to constrain
2517 		 the access properly.  */
2518 	      if (!ref->max_size_known_p ())
2519 		return false;
2520 	      tree dest = gimple_call_arg (stmt, 0);
2521 	      tree len = gimple_call_arg (stmt, 2);
2522 	      if (!poly_int_tree_p (len))
2523 		return false;
2524 	      tree rbase = ref->base;
2525 	      poly_offset_int roffset = ref->offset;
2526 	      ao_ref dref;
2527 	      ao_ref_init_from_ptr_and_size (&dref, dest, len);
2528 	      tree base = ao_ref_base (&dref);
2529 	      poly_offset_int offset = dref.offset;
2530 	      if (!base || !known_size_p (dref.size))
2531 		return false;
2532 	      if (TREE_CODE (base) == MEM_REF)
2533 		{
2534 		  if (TREE_CODE (rbase) != MEM_REF)
2535 		    return false;
2536 		  // Compare pointers.
2537 		  offset += mem_ref_offset (base) << LOG2_BITS_PER_UNIT;
2538 		  roffset += mem_ref_offset (rbase) << LOG2_BITS_PER_UNIT;
2539 		  base = TREE_OPERAND (base, 0);
2540 		  rbase = TREE_OPERAND (rbase, 0);
2541 		}
2542 	      if (base == rbase
2543 		  && known_subrange_p (roffset, ref->max_size, offset,
2544 				       wi::to_poly_offset (len)
2545 				       << LOG2_BITS_PER_UNIT))
2546 		return true;
2547 	      break;
2548 	    }
2549 
2550 	  case BUILT_IN_VA_END:
2551 	    {
2552 	      tree ptr = gimple_call_arg (stmt, 0);
2553 	      if (TREE_CODE (ptr) == ADDR_EXPR)
2554 		{
2555 		  tree base = ao_ref_base (ref);
2556 		  if (TREE_OPERAND (ptr, 0) == base)
2557 		    return true;
2558 		}
2559 	      break;
2560 	    }
2561 
2562 	  default:;
2563 	  }
2564     }
2565   return false;
2566 }
2567 
2568 bool
stmt_kills_ref_p(gimple * stmt,tree ref)2569 stmt_kills_ref_p (gimple *stmt, tree ref)
2570 {
2571   ao_ref r;
2572   ao_ref_init (&r, ref);
2573   return stmt_kills_ref_p (stmt, &r);
2574 }
2575 
2576 
2577 /* Walk the virtual use-def chain of VUSE until hitting the virtual operand
2578    TARGET or a statement clobbering the memory reference REF in which
2579    case false is returned.  The walk starts with VUSE, one argument of PHI.  */
2580 
2581 static bool
maybe_skip_until(gimple * phi,tree target,ao_ref * ref,tree vuse,unsigned int * cnt,bitmap * visited,bool abort_on_visited,void * (* translate)(ao_ref *,tree,void *,bool *),void * data)2582 maybe_skip_until (gimple *phi, tree target, ao_ref *ref,
2583 		  tree vuse, unsigned int *cnt, bitmap *visited,
2584 		  bool abort_on_visited,
2585 		  void *(*translate)(ao_ref *, tree, void *, bool *),
2586 		  void *data)
2587 {
2588   basic_block bb = gimple_bb (phi);
2589 
2590   if (!*visited)
2591     *visited = BITMAP_ALLOC (NULL);
2592 
2593   bitmap_set_bit (*visited, SSA_NAME_VERSION (PHI_RESULT (phi)));
2594 
2595   /* Walk until we hit the target.  */
2596   while (vuse != target)
2597     {
2598       gimple *def_stmt = SSA_NAME_DEF_STMT (vuse);
2599       /* Recurse for PHI nodes.  */
2600       if (gimple_code (def_stmt) == GIMPLE_PHI)
2601 	{
2602 	  /* An already visited PHI node ends the walk successfully.  */
2603 	  if (bitmap_bit_p (*visited, SSA_NAME_VERSION (PHI_RESULT (def_stmt))))
2604 	    return !abort_on_visited;
2605 	  vuse = get_continuation_for_phi (def_stmt, ref, cnt,
2606 					   visited, abort_on_visited,
2607 					   translate, data);
2608 	  if (!vuse)
2609 	    return false;
2610 	  continue;
2611 	}
2612       else if (gimple_nop_p (def_stmt))
2613 	return false;
2614       else
2615 	{
2616 	  /* A clobbering statement or the end of the IL ends it failing.  */
2617 	  ++*cnt;
2618 	  if (stmt_may_clobber_ref_p_1 (def_stmt, ref))
2619 	    {
2620 	      bool disambiguate_only = true;
2621 	      if (translate
2622 		  && (*translate) (ref, vuse, data, &disambiguate_only) == NULL)
2623 		;
2624 	      else
2625 		return false;
2626 	    }
2627 	}
2628       /* If we reach a new basic-block see if we already skipped it
2629          in a previous walk that ended successfully.  */
2630       if (gimple_bb (def_stmt) != bb)
2631 	{
2632 	  if (!bitmap_set_bit (*visited, SSA_NAME_VERSION (vuse)))
2633 	    return !abort_on_visited;
2634 	  bb = gimple_bb (def_stmt);
2635 	}
2636       vuse = gimple_vuse (def_stmt);
2637     }
2638   return true;
2639 }
2640 
2641 
2642 /* Starting from a PHI node for the virtual operand of the memory reference
2643    REF find a continuation virtual operand that allows to continue walking
2644    statements dominating PHI skipping only statements that cannot possibly
2645    clobber REF.  Increments *CNT for each alias disambiguation done.
2646    Returns NULL_TREE if no suitable virtual operand can be found.  */
2647 
2648 tree
get_continuation_for_phi(gimple * phi,ao_ref * ref,unsigned int * cnt,bitmap * visited,bool abort_on_visited,void * (* translate)(ao_ref *,tree,void *,bool *),void * data)2649 get_continuation_for_phi (gimple *phi, ao_ref *ref,
2650 			  unsigned int *cnt, bitmap *visited,
2651 			  bool abort_on_visited,
2652 			  void *(*translate)(ao_ref *, tree, void *, bool *),
2653 			  void *data)
2654 {
2655   unsigned nargs = gimple_phi_num_args (phi);
2656 
2657   /* Through a single-argument PHI we can simply look through.  */
2658   if (nargs == 1)
2659     return PHI_ARG_DEF (phi, 0);
2660 
2661   /* For two or more arguments try to pairwise skip non-aliasing code
2662      until we hit the phi argument definition that dominates the other one.  */
2663   basic_block phi_bb = gimple_bb (phi);
2664   tree arg0, arg1;
2665   unsigned i;
2666 
2667   /* Find a candidate for the virtual operand which definition
2668      dominates those of all others.  */
2669   /* First look if any of the args themselves satisfy this.  */
2670   for (i = 0; i < nargs; ++i)
2671     {
2672       arg0 = PHI_ARG_DEF (phi, i);
2673       if (SSA_NAME_IS_DEFAULT_DEF (arg0))
2674 	break;
2675       basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (arg0));
2676       if (def_bb != phi_bb
2677 	  && dominated_by_p (CDI_DOMINATORS, phi_bb, def_bb))
2678 	break;
2679       arg0 = NULL_TREE;
2680     }
2681   /* If not, look if we can reach such candidate by walking defs
2682      of a PHI arg without crossing other PHIs.  */
2683   if (! arg0)
2684     for (i = 0; i < nargs; ++i)
2685       {
2686 	arg0 = PHI_ARG_DEF (phi, i);
2687 	gimple *def = SSA_NAME_DEF_STMT (arg0);
2688 	/* Backedges can't work.  */
2689 	if (dominated_by_p (CDI_DOMINATORS,
2690 			    gimple_bb (def), phi_bb))
2691 	  continue;
2692 	/* See below.  */
2693 	if (gimple_code (def) == GIMPLE_PHI)
2694 	  continue;
2695 	while (! dominated_by_p (CDI_DOMINATORS,
2696 				 phi_bb, gimple_bb (def)))
2697 	  {
2698 	    arg0 = gimple_vuse (def);
2699 	    if (SSA_NAME_IS_DEFAULT_DEF (arg0))
2700 	      break;
2701 	    def = SSA_NAME_DEF_STMT (arg0);
2702 	    if (gimple_code (def) == GIMPLE_PHI)
2703 	      {
2704 		/* Do not try to look through arbitrarily complicated
2705 		   CFGs.  For those looking for the first VUSE starting
2706 		   from the end of the immediate dominator of phi_bb
2707 		   is likely faster.  */
2708 		arg0 = NULL_TREE;
2709 		goto next;
2710 	      }
2711 	  }
2712 	break;
2713 next:;
2714       }
2715   if (! arg0)
2716     return NULL_TREE;
2717 
2718   /* Then check against the found candidate.  */
2719   for (i = 0; i < nargs; ++i)
2720     {
2721       arg1 = PHI_ARG_DEF (phi, i);
2722       if (arg1 == arg0)
2723 	;
2724       else if (! maybe_skip_until (phi, arg0, ref, arg1, cnt, visited,
2725 				   abort_on_visited, translate, data))
2726 	return NULL_TREE;
2727     }
2728 
2729   return arg0;
2730 }
2731 
2732 /* Based on the memory reference REF and its virtual use VUSE call
2733    WALKER for each virtual use that is equivalent to VUSE, including VUSE
2734    itself.  That is, for each virtual use for which its defining statement
2735    does not clobber REF.
2736 
2737    WALKER is called with REF, the current virtual use and DATA.  If
2738    WALKER returns non-NULL the walk stops and its result is returned.
2739    At the end of a non-successful walk NULL is returned.
2740 
2741    TRANSLATE if non-NULL is called with a pointer to REF, the virtual
2742    use which definition is a statement that may clobber REF and DATA.
2743    If TRANSLATE returns (void *)-1 the walk stops and NULL is returned.
2744    If TRANSLATE returns non-NULL the walk stops and its result is returned.
2745    If TRANSLATE returns NULL the walk continues and TRANSLATE is supposed
2746    to adjust REF and *DATA to make that valid.
2747 
2748    VALUEIZE if non-NULL is called with the next VUSE that is considered
2749    and return value is substituted for that.  This can be used to
2750    implement optimistic value-numbering for example.  Note that the
2751    VUSE argument is assumed to be valueized already.
2752 
2753    TODO: Cache the vector of equivalent vuses per ref, vuse pair.  */
2754 
2755 void *
walk_non_aliased_vuses(ao_ref * ref,tree vuse,void * (* walker)(ao_ref *,tree,unsigned int,void *),void * (* translate)(ao_ref *,tree,void *,bool *),tree (* valueize)(tree),void * data)2756 walk_non_aliased_vuses (ao_ref *ref, tree vuse,
2757 			void *(*walker)(ao_ref *, tree, unsigned int, void *),
2758 			void *(*translate)(ao_ref *, tree, void *, bool *),
2759 			tree (*valueize)(tree),
2760 			void *data)
2761 {
2762   bitmap visited = NULL;
2763   void *res;
2764   unsigned int cnt = 0;
2765   bool translated = false;
2766 
2767   timevar_push (TV_ALIAS_STMT_WALK);
2768 
2769   do
2770     {
2771       gimple *def_stmt;
2772 
2773       /* ???  Do we want to account this to TV_ALIAS_STMT_WALK?  */
2774       res = (*walker) (ref, vuse, cnt, data);
2775       /* Abort walk.  */
2776       if (res == (void *)-1)
2777 	{
2778 	  res = NULL;
2779 	  break;
2780 	}
2781       /* Lookup succeeded.  */
2782       else if (res != NULL)
2783 	break;
2784 
2785       if (valueize)
2786 	vuse = valueize (vuse);
2787       def_stmt = SSA_NAME_DEF_STMT (vuse);
2788       if (gimple_nop_p (def_stmt))
2789 	break;
2790       else if (gimple_code (def_stmt) == GIMPLE_PHI)
2791 	vuse = get_continuation_for_phi (def_stmt, ref, &cnt,
2792 					 &visited, translated, translate, data);
2793       else
2794 	{
2795 	  cnt++;
2796 	  if (stmt_may_clobber_ref_p_1 (def_stmt, ref))
2797 	    {
2798 	      if (!translate)
2799 		break;
2800 	      bool disambiguate_only = false;
2801 	      res = (*translate) (ref, vuse, data, &disambiguate_only);
2802 	      /* Failed lookup and translation.  */
2803 	      if (res == (void *)-1)
2804 		{
2805 		  res = NULL;
2806 		  break;
2807 		}
2808 	      /* Lookup succeeded.  */
2809 	      else if (res != NULL)
2810 		break;
2811 	      /* Translation succeeded, continue walking.  */
2812 	      translated = translated || !disambiguate_only;
2813 	    }
2814 	  vuse = gimple_vuse (def_stmt);
2815 	}
2816     }
2817   while (vuse);
2818 
2819   if (visited)
2820     BITMAP_FREE (visited);
2821 
2822   timevar_pop (TV_ALIAS_STMT_WALK);
2823 
2824   return res;
2825 }
2826 
2827 
2828 /* Based on the memory reference REF call WALKER for each vdef which
2829    defining statement may clobber REF, starting with VDEF.  If REF
2830    is NULL_TREE, each defining statement is visited.
2831 
2832    WALKER is called with REF, the current vdef and DATA.  If WALKER
2833    returns true the walk is stopped, otherwise it continues.
2834 
2835    If function entry is reached, FUNCTION_ENTRY_REACHED is set to true.
2836    The pointer may be NULL and then we do not track this information.
2837 
2838    At PHI nodes walk_aliased_vdefs forks into one walk for reach
2839    PHI argument (but only one walk continues on merge points), the
2840    return value is true if any of the walks was successful.
2841 
2842    The function returns the number of statements walked or -1 if
2843    LIMIT stmts were walked and the walk was aborted at this point.
2844    If LIMIT is zero the walk is not aborted.  */
2845 
2846 static int
walk_aliased_vdefs_1(ao_ref * ref,tree vdef,bool (* walker)(ao_ref *,tree,void *),void * data,bitmap * visited,unsigned int cnt,bool * function_entry_reached,unsigned limit)2847 walk_aliased_vdefs_1 (ao_ref *ref, tree vdef,
2848 		      bool (*walker)(ao_ref *, tree, void *), void *data,
2849 		      bitmap *visited, unsigned int cnt,
2850 		      bool *function_entry_reached, unsigned limit)
2851 {
2852   do
2853     {
2854       gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
2855 
2856       if (*visited
2857 	  && !bitmap_set_bit (*visited, SSA_NAME_VERSION (vdef)))
2858 	return cnt;
2859 
2860       if (gimple_nop_p (def_stmt))
2861 	{
2862 	  if (function_entry_reached)
2863 	    *function_entry_reached = true;
2864 	  return cnt;
2865 	}
2866       else if (gimple_code (def_stmt) == GIMPLE_PHI)
2867 	{
2868 	  unsigned i;
2869 	  if (!*visited)
2870 	    *visited = BITMAP_ALLOC (NULL);
2871 	  for (i = 0; i < gimple_phi_num_args (def_stmt); ++i)
2872 	    {
2873 	      int res = walk_aliased_vdefs_1 (ref,
2874 					      gimple_phi_arg_def (def_stmt, i),
2875 					      walker, data, visited, cnt,
2876 					      function_entry_reached, limit);
2877 	      if (res == -1)
2878 		return -1;
2879 	      cnt = res;
2880 	    }
2881 	  return cnt;
2882 	}
2883 
2884       /* ???  Do we want to account this to TV_ALIAS_STMT_WALK?  */
2885       cnt++;
2886       if (cnt == limit)
2887 	return -1;
2888       if ((!ref
2889 	   || stmt_may_clobber_ref_p_1 (def_stmt, ref))
2890 	  && (*walker) (ref, vdef, data))
2891 	return cnt;
2892 
2893       vdef = gimple_vuse (def_stmt);
2894     }
2895   while (1);
2896 }
2897 
2898 int
walk_aliased_vdefs(ao_ref * ref,tree vdef,bool (* walker)(ao_ref *,tree,void *),void * data,bitmap * visited,bool * function_entry_reached,unsigned int limit)2899 walk_aliased_vdefs (ao_ref *ref, tree vdef,
2900 		    bool (*walker)(ao_ref *, tree, void *), void *data,
2901 		    bitmap *visited,
2902 		    bool *function_entry_reached, unsigned int limit)
2903 {
2904   bitmap local_visited = NULL;
2905   int ret;
2906 
2907   timevar_push (TV_ALIAS_STMT_WALK);
2908 
2909   if (function_entry_reached)
2910     *function_entry_reached = false;
2911 
2912   ret = walk_aliased_vdefs_1 (ref, vdef, walker, data,
2913 			      visited ? visited : &local_visited, 0,
2914 			      function_entry_reached, limit);
2915   if (local_visited)
2916     BITMAP_FREE (local_visited);
2917 
2918   timevar_pop (TV_ALIAS_STMT_WALK);
2919 
2920   return ret;
2921 }
2922 
2923