gcc/tree-ssa-alias.c

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