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;
 750   poly_uint64 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   /* Handle the most common case first.  */
 791   if (type1 == type2)
 792     return 1;
 793
 794   /* If we would have to do structural comparison bail out.  */
 795   if (TYPE_STRUCTURAL_EQUALITY_P (type1)
 796       || TYPE_STRUCTURAL_EQUALITY_P (type2))
 797     return -1;
 798
 799   /* Compare the canonical types.  */
 800   if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
 801     return 1;
 802
 803   /* ??? Array types are not properly unified in all cases as we have
 804      spurious changes in the index types for example.  Removing this
 805      causes all sorts of problems with the Fortran frontend.  */
 806   if (TREE_CODE (type1) == ARRAY_TYPE
 807       && TREE_CODE (type2) == ARRAY_TYPE)
 808     return -1;
 809
 810   /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
 811      object of one of its constrained subtypes, e.g. when a function with an
 812      unconstrained parameter passed by reference is called on an object and
 813      inlined.  But, even in the case of a fixed size, type and subtypes are
 814      not equivalent enough as to share the same TYPE_CANONICAL, since this
 815      would mean that conversions between them are useless, whereas they are
 816      not (e.g. type and subtypes can have different modes).  So, in the end,
 817      they are only guaranteed to have the same alias set.  */
 818   if (get_alias_set (type1) == get_alias_set (type2))
 819     return -1;
 820
 821   /* The types are known to be not equal.  */
 822   return 0;
 823 }
 824
 825 /* Return true if TYPE is a composite type (i.e. we may apply one of handled
 826    components on it).  */
 827
 828 static bool
 829 type_has_components_p (tree type)
 830 {
 831   return AGGREGATE_TYPE_P (type) || VECTOR_TYPE_P (type)
 832          || TREE_CODE (type) == COMPLEX_TYPE;
 833 }
 834
 835 /* Determine if the two component references REF1 and REF2 which are
 836    based on access types TYPE1 and TYPE2 and of which at least one is based
 837    on an indirect reference may alias.  REF2 is the only one that can
 838    be a decl in which case REF2_IS_DECL is true.
 839    REF1_ALIAS_SET, BASE1_ALIAS_SET, REF2_ALIAS_SET and BASE2_ALIAS_SET
 840    are the respective alias sets.  */
 841
 842 static bool
 843 aliasing_component_refs_p (tree ref1,
 844                            alias_set_type ref1_alias_set,
 845                            alias_set_type base1_alias_set,
 846                            poly_int64 offset1, poly_int64 max_size1,
 847                            tree ref2,
 848                            alias_set_type ref2_alias_set,
 849                            alias_set_type base2_alias_set,
 850                            poly_int64 offset2, poly_int64 max_size2,
 851                            bool ref2_is_decl)
 852 {
 853   /* If one reference is a component references through pointers try to find a
 854      common base and apply offset based disambiguation.  This handles
 855      for example
 856        struct A { int i; int j; } *q;
 857        struct B { struct A a; int k; } *p;
 858      disambiguating q->i and p->a.j.  */
 859   tree base1, base2;
 860   tree type1, type2;
 861   tree *refp;
 862   int same_p1 = 0, same_p2 = 0;
 863   bool maybe_match = false;
 864
 865   /* Choose bases and base types to search for.  */
 866   base1 = ref1;
 867   while (handled_component_p (base1))
 868     base1 = TREE_OPERAND (base1, 0);
 869   type1 = TREE_TYPE (base1);
 870   base2 = ref2;
 871   while (handled_component_p (base2))
 872     base2 = TREE_OPERAND (base2, 0);
 873   type2 = TREE_TYPE (base2);
 874
 875   /* Now search for the type1 in the access path of ref2.  This
 876      would be a common base for doing offset based disambiguation on.
 877      This however only makes sense if type2 is big enough to hold type1.  */
 878   int cmp_outer = compare_type_sizes (type2, type1);
 879   if (cmp_outer >= 0)
 880     {
 881       refp = &ref2;
 882       while (true)
 883         {
 884           /* We walk from inner type to the outer types. If type we see is
 885              already too large to be part of type1, terminate the search.  */
 886           int cmp = compare_type_sizes (type1, TREE_TYPE (*refp));
 887           if (cmp < 0)
 888             break;
 889           /* If types may be of same size, see if we can decide about their
 890              equality.  */
 891           if (cmp == 0)
 892             {
 893               same_p2 = same_type_for_tbaa (TREE_TYPE (*refp), type1);
 894               if (same_p2 == 1)
 895                 break;
 896               /* In case we can't decide whether types are same try to
 897                  continue looking for the exact match.
 898                  Remember however that we possibly saw a match
 899                  to bypass the access path continuations tests we do later.  */
 900               if (same_p2 == -1)
 901                 maybe_match = true;
 902             }
 903           if (!handled_component_p (*refp))
 904             break;
 905           refp = &TREE_OPERAND (*refp, 0);
 906         }
 907       if (same_p2 == 1)
 908         {
 909           poly_int64 offadj, sztmp, msztmp;
 910           bool reverse;
 911
 912           /* We assume that arrays can overlap by multiple of their elements
 913              size as tested in gcc.dg/torture/alias-2.c.
 914              This partial overlap happen only when both arrays are bases of
 915              the access and not contained within another component ref.
 916              To be safe we also assume partial overlap for VLAs.  */
 917           if (TREE_CODE (TREE_TYPE (base1)) == ARRAY_TYPE
 918               && (!TYPE_SIZE (TREE_TYPE (base1))
 919                   || TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) != INTEGER_CST
 920                   || (*refp == base2 && !ref2_is_decl)))
 921             {
 922               ++alias_stats.aliasing_component_refs_p_may_alias;
 923               return true;
 924             }
 925
 926           get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse);
 927           offset2 -= offadj;
 928           get_ref_base_and_extent (base1, &offadj, &sztmp, &msztmp, &reverse);
 929           offset1 -= offadj;
 930           if (ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
 931             {
 932               ++alias_stats.aliasing_component_refs_p_may_alias;
 933               return true;
 934             }
 935           else
 936             {
 937               ++alias_stats.aliasing_component_refs_p_no_alias;
 938               return false;
 939             }
 940         }
 941     }
 942
 943   /* If we didn't find a common base, try the other way around.  */
 944   if (cmp_outer <= 0)
 945     {
 946       refp = &ref1;
 947       while (true)
 948         {
 949           int cmp = compare_type_sizes (type2, TREE_TYPE (*refp));
 950           if (cmp < 0)
 951             break;
 952           /* If types may be of same size, see if we can decide about their
 953              equality.  */
 954           if (cmp == 0)
 955             {
 956               same_p1 = same_type_for_tbaa (TREE_TYPE (*refp), type2);
 957               if (same_p1 == 1)
 958                 break;
 959               if (same_p1 == -1)
 960                 maybe_match = true;
 961             }
 962           if (!handled_component_p (*refp))
 963             break;
 964           refp = &TREE_OPERAND (*refp, 0);
 965         }
 966       if (same_p1 == 1)
 967         {
 968           poly_int64 offadj, sztmp, msztmp;
 969           bool reverse;
 970
 971           if (TREE_CODE (TREE_TYPE (base2)) == ARRAY_TYPE
 972               && (!TYPE_SIZE (TREE_TYPE (base2))
 973                   || TREE_CODE (TYPE_SIZE (TREE_TYPE (base2))) != INTEGER_CST
 974                   || (*refp == base1 && !ref2_is_decl)))
 975             {
 976               ++alias_stats.aliasing_component_refs_p_may_alias;
 977               return true;
 978             }
 979
 980           get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse);
 981           offset1 -= offadj;
 982           get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp, &reverse);
 983           offset2 -= offadj;
 984           if (ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
 985             {
 986               ++alias_stats.aliasing_component_refs_p_may_alias;
 987               return true;
 988             }
 989           else
 990             {
 991               ++alias_stats.aliasing_component_refs_p_no_alias;
 992               return false;
 993             }
 994         }
 995     }
 996
 997   /* In the following code we make an assumption that the types in access
 998      paths do not overlap and thus accesses alias only if one path can be
 999      continuation of another.  If we was not able to decide about equivalence,
1000      we need to give up.  */
1001   if (maybe_match)
1002     return true;
1003
1004   /* If we have two type access paths B1.path1 and B2.path2 they may
1005      only alias if either B1 is in B2.path2 or B2 is in B1.path1.
1006      But we can still have a path that goes B1.path1...B2.path2 with
1007      a part that we do not see.  So we can only disambiguate now
1008      if there is no B2 in the tail of path1 and no B1 on the
1009      tail of path2.  */
1010   if (compare_type_sizes (TREE_TYPE (ref2), type1) >= 0
1011       && type_has_components_p (TREE_TYPE (ref2))
1012       && (base1_alias_set == ref2_alias_set
1013           || alias_set_subset_of (base1_alias_set, ref2_alias_set)))
1014     {
1015       ++alias_stats.aliasing_component_refs_p_may_alias;
1016       return true;
1017     }
1018   /* If this is ptr vs. decl then we know there is no ptr ... decl path.  */
1019   if (!ref2_is_decl
1020       && compare_type_sizes (TREE_TYPE (ref1), type2) >= 0
1021       && type_has_components_p (TREE_TYPE (ref1))
1022       && (base2_alias_set == ref1_alias_set
1023           || alias_set_subset_of (base2_alias_set, ref1_alias_set)))
1024     {
1025       ++alias_stats.aliasing_component_refs_p_may_alias;
1026       return true;
1027     }
1028   ++alias_stats.aliasing_component_refs_p_no_alias;
1029   return false;
1030 }
1031
1032 /* Return true if we can determine that component references REF1 and REF2,
1033    that are within a common DECL, cannot overlap.  */
1034
1035 static bool
1036 nonoverlapping_component_refs_of_decl_p (tree ref1, tree ref2)
1037 {
1038   auto_vec<tree, 16> component_refs1;
1039   auto_vec<tree, 16> component_refs2;
1040
1041   /* Create the stack of handled components for REF1.  */
1042   while (handled_component_p (ref1))
1043     {
1044       component_refs1.safe_push (ref1);
1045       ref1 = TREE_OPERAND (ref1, 0);
1046     }
1047   if (TREE_CODE (ref1) == MEM_REF)
1048     {
1049       if (!integer_zerop (TREE_OPERAND (ref1, 1)))
1050         return false;
1051       ref1 = TREE_OPERAND (TREE_OPERAND (ref1, 0), 0);
1052     }
1053
1054   /* Create the stack of handled components for REF2.  */
1055   while (handled_component_p (ref2))
1056     {
1057       component_refs2.safe_push (ref2);
1058       ref2 = TREE_OPERAND (ref2, 0);
1059     }
1060   if (TREE_CODE (ref2) == MEM_REF)
1061     {
1062       if (!integer_zerop (TREE_OPERAND (ref2, 1)))
1063         return false;
1064       ref2 = TREE_OPERAND (TREE_OPERAND (ref2, 0), 0);
1065     }
1066
1067   /* Bases must be either same or uncomparable.  */
1068   gcc_checking_assert (ref1 == ref2
1069                        || (DECL_P (ref1) && DECL_P (ref2)
1070                            && compare_base_decls (ref1, ref2) != 0));
1071
1072   /* Pop the stacks in parallel and examine the COMPONENT_REFs of the same
1073      rank.  This is sufficient because we start from the same DECL and you
1074      cannot reference several fields at a time with COMPONENT_REFs (unlike
1075      with ARRAY_RANGE_REFs for arrays) so you always need the same number
1076      of them to access a sub-component, unless you're in a union, in which
1077      case the return value will precisely be false.  */
1078   while (true)
1079     {
1080       do
1081         {
1082           if (component_refs1.is_empty ())
1083             return false;
1084           ref1 = component_refs1.pop ();
1085         }
1086       while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref1, 0))));
1087
1088       do
1089         {
1090           if (component_refs2.is_empty ())
1091              return false;
1092           ref2 = component_refs2.pop ();
1093         }
1094       while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref2, 0))));
1095
1096       /* Beware of BIT_FIELD_REF.  */
1097       if (TREE_CODE (ref1) != COMPONENT_REF
1098           || TREE_CODE (ref2) != COMPONENT_REF)
1099         return false;
1100
1101       tree field1 = TREE_OPERAND (ref1, 1);
1102       tree field2 = TREE_OPERAND (ref2, 1);
1103
1104       /* ??? We cannot simply use the type of operand #0 of the refs here
1105          as the Fortran compiler smuggles type punning into COMPONENT_REFs
1106          for common blocks instead of using unions like everyone else.  */
1107       tree type1 = DECL_CONTEXT (field1);
1108       tree type2 = DECL_CONTEXT (field2);
1109
1110       /* We cannot disambiguate fields in a union or qualified union.  */
1111       if (type1 != type2 || TREE_CODE (type1) != RECORD_TYPE)
1112          return false;
1113
1114       if (field1 != field2)
1115         {
1116           /* A field and its representative need to be considered the
1117              same.  */
1118           if (DECL_BIT_FIELD_REPRESENTATIVE (field1) == field2
1119               || DECL_BIT_FIELD_REPRESENTATIVE (field2) == field1)
1120             return false;
1121           /* Different fields of the same record type cannot overlap.
1122              ??? Bitfields can overlap at RTL level so punt on them.  */
1123           if (DECL_BIT_FIELD (field1) && DECL_BIT_FIELD (field2))
1124             return false;
1125           return true;
1126         }
1127     }
1128
1129   return false;
1130 }
1131
1132 /* qsort compare function to sort FIELD_DECLs after their
1133    DECL_FIELD_CONTEXT TYPE_UID.  */
1134
1135 static inline int
1136 ncr_compar (const void *field1_, const void *field2_)
1137 {
1138   const_tree field1 = *(const_tree *) const_cast <void *>(field1_);
1139   const_tree field2 = *(const_tree *) const_cast <void *>(field2_);
1140   unsigned int uid1 = TYPE_UID (DECL_FIELD_CONTEXT (field1));
1141   unsigned int uid2 = TYPE_UID (DECL_FIELD_CONTEXT (field2));
1142   if (uid1 < uid2)
1143     return -1;
1144   else if (uid1 > uid2)
1145     return 1;
1146   return 0;
1147 }
1148
1149 /* Return true if we can determine that the fields referenced cannot
1150    overlap for any pair of objects.  */
1151
1152 static bool
1153 nonoverlapping_component_refs_p (const_tree x, const_tree y)
1154 {
1155   if (!flag_strict_aliasing
1156       || !x || !y
1157       || TREE_CODE (x) != COMPONENT_REF
1158       || TREE_CODE (y) != COMPONENT_REF)
1159     return false;
1160
1161   auto_vec<const_tree, 16> fieldsx;
1162   while (TREE_CODE (x) == COMPONENT_REF)
1163     {
1164       tree field = TREE_OPERAND (x, 1);
1165       tree type = DECL_FIELD_CONTEXT (field);
1166       if (TREE_CODE (type) == RECORD_TYPE)
1167         fieldsx.safe_push (field);
1168       x = TREE_OPERAND (x, 0);
1169     }
1170   if (fieldsx.length () == 0)
1171     return false;
1172   auto_vec<const_tree, 16> fieldsy;
1173   while (TREE_CODE (y) == COMPONENT_REF)
1174     {
1175       tree field = TREE_OPERAND (y, 1);
1176       tree type = DECL_FIELD_CONTEXT (field);
1177       if (TREE_CODE (type) == RECORD_TYPE)
1178         fieldsy.safe_push (TREE_OPERAND (y, 1));
1179       y = TREE_OPERAND (y, 0);
1180     }
1181   if (fieldsy.length () == 0)
1182     return false;
1183
1184   /* Most common case first.  */
1185   if (fieldsx.length () == 1
1186       && fieldsy.length () == 1)
1187     return ((DECL_FIELD_CONTEXT (fieldsx[0])
1188              == DECL_FIELD_CONTEXT (fieldsy[0]))
1189             && fieldsx[0] != fieldsy[0]
1190             && !(DECL_BIT_FIELD (fieldsx[0]) && DECL_BIT_FIELD (fieldsy[0])));
1191
1192   if (fieldsx.length () == 2)
1193     {
1194       if (ncr_compar (&fieldsx[0], &fieldsx[1]) == 1)
1195         std::swap (fieldsx[0], fieldsx[1]);
1196     }
1197   else
1198     fieldsx.qsort (ncr_compar);
1199
1200   if (fieldsy.length () == 2)
1201     {
1202       if (ncr_compar (&fieldsy[0], &fieldsy[1]) == 1)
1203         std::swap (fieldsy[0], fieldsy[1]);
1204     }
1205   else
1206     fieldsy.qsort (ncr_compar);
1207
1208   unsigned i = 0, j = 0;
1209   do
1210     {
1211       const_tree fieldx = fieldsx[i];
1212       const_tree fieldy = fieldsy[j];
1213       tree typex = DECL_FIELD_CONTEXT (fieldx);
1214       tree typey = DECL_FIELD_CONTEXT (fieldy);
1215       if (typex == typey)
1216         {
1217           /* We're left with accessing different fields of a structure,
1218              no possible overlap.  */
1219           if (fieldx != fieldy)
1220             {
1221               /* A field and its representative need to be considered the
1222                  same.  */
1223               if (DECL_BIT_FIELD_REPRESENTATIVE (fieldx) == fieldy
1224                   || DECL_BIT_FIELD_REPRESENTATIVE (fieldy) == fieldx)
1225                 return false;
1226               /* Different fields of the same record type cannot overlap.
1227                  ??? Bitfields can overlap at RTL level so punt on them.  */
1228               if (DECL_BIT_FIELD (fieldx) && DECL_BIT_FIELD (fieldy))
1229                 return false;
1230               return true;
1231             }
1232         }
1233       if (TYPE_UID (typex) < TYPE_UID (typey))
1234         {
1235           i++;
1236           if (i == fieldsx.length ())
1237             break;
1238         }
1239       else
1240         {
1241           j++;
1242           if (j == fieldsy.length ())
1243             break;
1244         }
1245     }
1246   while (1);
1247
1248   return false;
1249 }
1250
1251
1252 /* Return true if two memory references based on the variables BASE1
1253    and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
1254    [OFFSET2, OFFSET2 + MAX_SIZE2) may alias.  REF1 and REF2
1255    if non-NULL are the complete memory reference trees.  */
1256
1257 static bool
1258 decl_refs_may_alias_p (tree ref1, tree base1,
1259                        poly_int64 offset1, poly_int64 max_size1,
1260                        tree ref2, tree base2,
1261                        poly_int64 offset2, poly_int64 max_size2)
1262 {
1263   gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
1264
1265   /* If both references are based on different variables, they cannot alias.  */
1266   if (compare_base_decls (base1, base2) == 0)
1267     return false;
1268
1269   /* If both references are based on the same variable, they cannot alias if
1270      the accesses do not overlap.  */
1271   if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
1272     return false;
1273
1274   /* For components with variable position, the above test isn't sufficient,
1275      so we disambiguate component references manually.  */
1276   if (ref1 && ref2
1277       && handled_component_p (ref1) && handled_component_p (ref2)
1278       && nonoverlapping_component_refs_of_decl_p (ref1, ref2))
1279     return false;
1280
1281   return true;
1282 }
1283
1284 /* Return true if an indirect reference based on *PTR1 constrained
1285    to [OFFSET1, OFFSET1 + MAX_SIZE1) may alias a variable based on BASE2
1286    constrained to [OFFSET2, OFFSET2 + MAX_SIZE2).  *PTR1 and BASE2 have
1287    the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
1288    in which case they are computed on-demand.  REF1 and REF2
1289    if non-NULL are the complete memory reference trees.  */
1290
1291 static bool
1292 indirect_ref_may_alias_decl_p (tree ref1 ATTRIBUTE_UNUSED, tree base1,
1293                                poly_int64 offset1, poly_int64 max_size1,
1294                                alias_set_type ref1_alias_set,
1295                                alias_set_type base1_alias_set,
1296                                tree ref2 ATTRIBUTE_UNUSED, tree base2,
1297                                poly_int64 offset2, poly_int64 max_size2,
1298                                alias_set_type ref2_alias_set,
1299                                alias_set_type base2_alias_set, bool tbaa_p)
1300 {
1301   tree ptr1;
1302   tree ptrtype1, dbase2;
1303
1304   gcc_checking_assert ((TREE_CODE (base1) == MEM_REF
1305                         || TREE_CODE (base1) == TARGET_MEM_REF)
1306                        && DECL_P (base2));
1307
1308   ptr1 = TREE_OPERAND (base1, 0);
1309   poly_offset_int moff = mem_ref_offset (base1) << LOG2_BITS_PER_UNIT;
1310
1311   /* If only one reference is based on a variable, they cannot alias if
1312      the pointer access is beyond the extent of the variable access.
1313      (the pointer base cannot validly point to an offset less than zero
1314      of the variable).
1315      ???  IVOPTs creates bases that do not honor this restriction,
1316      so do not apply this optimization for TARGET_MEM_REFs.  */
1317   if (TREE_CODE (base1) != TARGET_MEM_REF
1318       && !ranges_maybe_overlap_p (offset1 + moff, -1, offset2, max_size2))
1319     return false;
1320   /* They also cannot alias if the pointer may not point to the decl.  */
1321   if (!ptr_deref_may_alias_decl_p (ptr1, base2))
1322     return false;
1323
1324   /* Disambiguations that rely on strict aliasing rules follow.  */
1325   if (!flag_strict_aliasing || !tbaa_p)
1326     return true;
1327
1328   ptrtype1 = TREE_TYPE (TREE_OPERAND (base1, 1));
1329
1330   /* If the alias set for a pointer access is zero all bets are off.  */
1331   if (base1_alias_set == 0)
1332     return true;
1333
1334   /* When we are trying to disambiguate an access with a pointer dereference
1335      as base versus one with a decl as base we can use both the size
1336      of the decl and its dynamic type for extra disambiguation.
1337      ???  We do not know anything about the dynamic type of the decl
1338      other than that its alias-set contains base2_alias_set as a subset
1339      which does not help us here.  */
1340   /* As we know nothing useful about the dynamic type of the decl just
1341      use the usual conflict check rather than a subset test.
1342      ???  We could introduce -fvery-strict-aliasing when the language
1343      does not allow decls to have a dynamic type that differs from their
1344      static type.  Then we can check
1345      !alias_set_subset_of (base1_alias_set, base2_alias_set) instead.  */
1346   if (base1_alias_set != base2_alias_set
1347       && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
1348     return false;
1349   /* If the size of the access relevant for TBAA through the pointer
1350      is bigger than the size of the decl we can't possibly access the
1351      decl via that pointer.  */
1352   if (/* ???  This in turn may run afoul when a decl of type T which is
1353          a member of union type U is accessed through a pointer to
1354          type U and sizeof T is smaller than sizeof U.  */
1355       TREE_CODE (TREE_TYPE (ptrtype1)) != UNION_TYPE
1356       && TREE_CODE (TREE_TYPE (ptrtype1)) != QUAL_UNION_TYPE
1357       && compare_sizes (DECL_SIZE (base2),
1358                         TYPE_SIZE (TREE_TYPE (ptrtype1))) < 0)
1359     return false;
1360
1361   if (!ref2)
1362     return true;
1363
1364   /* If the decl is accessed via a MEM_REF, reconstruct the base
1365      we can use for TBAA and an appropriately adjusted offset.  */
1366   dbase2 = ref2;
1367   while (handled_component_p (dbase2))
1368     dbase2 = TREE_OPERAND (dbase2, 0);
1369   poly_int64 doffset1 = offset1;
1370   poly_offset_int doffset2 = offset2;
1371   if (TREE_CODE (dbase2) == MEM_REF
1372       || TREE_CODE (dbase2) == TARGET_MEM_REF)
1373     doffset2 -= mem_ref_offset (dbase2) << LOG2_BITS_PER_UNIT;
1374
1375   /* If either reference is view-converted, give up now.  */
1376   if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) != 1
1377       || same_type_for_tbaa (TREE_TYPE (dbase2), TREE_TYPE (base2)) != 1)
1378     return true;
1379
1380   /* If both references are through the same type, they do not alias
1381      if the accesses do not overlap.  This does extra disambiguation
1382      for mixed/pointer accesses but requires strict aliasing.
1383      For MEM_REFs we require that the component-ref offset we computed
1384      is relative to the start of the type which we ensure by
1385      comparing rvalue and access type and disregarding the constant
1386      pointer offset.
1387
1388      But avoid treating variable length arrays as "objects", instead assume they
1389      can overlap by an exact multiple of their element size.
1390      See gcc.dg/torture/alias-2.c.  */
1391   if ((TREE_CODE (base1) != TARGET_MEM_REF
1392        || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
1393       && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (dbase2)) == 1
1394       && (TREE_CODE (TREE_TYPE (base1)) != ARRAY_TYPE
1395           || (TYPE_SIZE (TREE_TYPE (base1))
1396               && TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) == INTEGER_CST)))
1397     return ranges_maybe_overlap_p (doffset1, max_size1, doffset2, max_size2);
1398
1399   if (ref1 && ref2
1400       && nonoverlapping_component_refs_p (ref1, ref2))
1401     return false;
1402
1403   /* Do access-path based disambiguation.  */
1404   if (ref1 && ref2
1405       && (handled_component_p (ref1) || handled_component_p (ref2)))
1406     return aliasing_component_refs_p (ref1,
1407                                       ref1_alias_set, base1_alias_set,
1408                                       offset1, max_size1,
1409                                       ref2,
1410                                       ref2_alias_set, base2_alias_set,
1411                                       offset2, max_size2, true);
1412
1413   return true;
1414 }
1415
1416 /* Return true if two indirect references based on *PTR1
1417    and *PTR2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
1418    [OFFSET2, OFFSET2 + MAX_SIZE2) may alias.  *PTR1 and *PTR2 have
1419    the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
1420    in which case they are computed on-demand.  REF1 and REF2
1421    if non-NULL are the complete memory reference trees. */
1422
1423 static bool
1424 indirect_refs_may_alias_p (tree ref1 ATTRIBUTE_UNUSED, tree base1,
1425                            poly_int64 offset1, poly_int64 max_size1,
1426                            alias_set_type ref1_alias_set,
1427                            alias_set_type base1_alias_set,
1428                            tree ref2 ATTRIBUTE_UNUSED, tree base2,
1429                            poly_int64 offset2, poly_int64 max_size2,
1430                            alias_set_type ref2_alias_set,
1431                            alias_set_type base2_alias_set, bool tbaa_p)
1432 {
1433   tree ptr1;
1434   tree ptr2;
1435   tree ptrtype1, ptrtype2;
1436
1437   gcc_checking_assert ((TREE_CODE (base1) == MEM_REF
1438                         || TREE_CODE (base1) == TARGET_MEM_REF)
1439                        && (TREE_CODE (base2) == MEM_REF
1440                            || TREE_CODE (base2) == TARGET_MEM_REF));
1441
1442   ptr1 = TREE_OPERAND (base1, 0);
1443   ptr2 = TREE_OPERAND (base2, 0);
1444
1445   /* If both bases are based on pointers they cannot alias if they may not
1446      point to the same memory object or if they point to the same object
1447      and the accesses do not overlap.  */
1448   if ((!cfun || gimple_in_ssa_p (cfun))
1449       && operand_equal_p (ptr1, ptr2, 0)
1450       && (((TREE_CODE (base1) != TARGET_MEM_REF
1451             || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
1452            && (TREE_CODE (base2) != TARGET_MEM_REF
1453                || (!TMR_INDEX (base2) && !TMR_INDEX2 (base2))))
1454           || (TREE_CODE (base1) == TARGET_MEM_REF
1455               && TREE_CODE (base2) == TARGET_MEM_REF
1456               && (TMR_STEP (base1) == TMR_STEP (base2)
1457                   || (TMR_STEP (base1) && TMR_STEP (base2)
1458                       && operand_equal_p (TMR_STEP (base1),
1459                                           TMR_STEP (base2), 0)))
1460               && (TMR_INDEX (base1) == TMR_INDEX (base2)
1461                   || (TMR_INDEX (base1) && TMR_INDEX (base2)
1462                       && operand_equal_p (TMR_INDEX (base1),
1463                                           TMR_INDEX (base2), 0)))
1464               && (TMR_INDEX2 (base1) == TMR_INDEX2 (base2)
1465                   || (TMR_INDEX2 (base1) && TMR_INDEX2 (base2)
1466                       && operand_equal_p (TMR_INDEX2 (base1),
1467                                           TMR_INDEX2 (base2), 0))))))
1468     {
1469       poly_offset_int moff1 = mem_ref_offset (base1) << LOG2_BITS_PER_UNIT;
1470       poly_offset_int moff2 = mem_ref_offset (base2) << LOG2_BITS_PER_UNIT;
1471       return ranges_maybe_overlap_p (offset1 + moff1, max_size1,
1472                                      offset2 + moff2, max_size2);
1473     }
1474   if (!ptr_derefs_may_alias_p (ptr1, ptr2))
1475     return false;
1476
1477   /* Disambiguations that rely on strict aliasing rules follow.  */
1478   if (!flag_strict_aliasing || !tbaa_p)
1479     return true;
1480
1481   ptrtype1 = TREE_TYPE (TREE_OPERAND (base1, 1));
1482   ptrtype2 = TREE_TYPE (TREE_OPERAND (base2, 1));
1483
1484   /* If the alias set for a pointer access is zero all bets are off.  */
1485   if (base1_alias_set == 0
1486       || base2_alias_set == 0)
1487     return true;
1488
1489   /* Do type-based disambiguation.  */
1490   if (base1_alias_set != base2_alias_set
1491       && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
1492     return false;
1493
1494   /* If either reference is view-converted, give up now.  */
1495   if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) != 1
1496       || same_type_for_tbaa (TREE_TYPE (base2), TREE_TYPE (ptrtype2)) != 1)
1497     return true;
1498
1499   /* If both references are through the same type, they do not alias
1500      if the accesses do not overlap.  This does extra disambiguation
1501      for mixed/pointer accesses but requires strict aliasing.  */
1502   if ((TREE_CODE (base1) != TARGET_MEM_REF
1503        || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
1504       && (TREE_CODE (base2) != TARGET_MEM_REF
1505           || (!TMR_INDEX (base2) && !TMR_INDEX2 (base2)))
1506       && same_type_for_tbaa (TREE_TYPE (ptrtype1),
1507                              TREE_TYPE (ptrtype2)) == 1
1508       /* But avoid treating arrays as "objects", instead assume they
1509          can overlap by an exact multiple of their element size.
1510          See gcc.dg/torture/alias-2.c.  */
1511       && TREE_CODE (TREE_TYPE (ptrtype1)) != ARRAY_TYPE)
1512     return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2);
1513
1514   if (ref1 && ref2
1515       && nonoverlapping_component_refs_p (ref1, ref2))
1516     return false;
1517
1518   /* Do access-path based disambiguation.  */
1519   if (ref1 && ref2
1520       && (handled_component_p (ref1) || handled_component_p (ref2)))
1521     return aliasing_component_refs_p (ref1,
1522                                       ref1_alias_set, base1_alias_set,
1523                                       offset1, max_size1,
1524                                       ref2,
1525                                       ref2_alias_set, base2_alias_set,
1526                                       offset2, max_size2, false);
1527
1528   return true;
1529 }
1530
1531 /* Return true, if the two memory references REF1 and REF2 may alias.  */
1532
1533 static bool
1534 refs_may_alias_p_2 (ao_ref *ref1, ao_ref *ref2, bool tbaa_p)
1535 {
1536   tree base1, base2;
1537   poly_int64 offset1 = 0, offset2 = 0;
1538   poly_int64 max_size1 = -1, max_size2 = -1;
1539   bool var1_p, var2_p, ind1_p, ind2_p;
1540
1541   gcc_checking_assert ((!ref1->ref
1542                         || TREE_CODE (ref1->ref) == SSA_NAME
1543                         || DECL_P (ref1->ref)
1544                         || TREE_CODE (ref1->ref) == STRING_CST
1545                         || handled_component_p (ref1->ref)
1546                         || TREE_CODE (ref1->ref) == MEM_REF
1547                         || TREE_CODE (ref1->ref) == TARGET_MEM_REF)
1548                        && (!ref2->ref
1549                            || TREE_CODE (ref2->ref) == SSA_NAME
1550                            || DECL_P (ref2->ref)
1551                            || TREE_CODE (ref2->ref) == STRING_CST
1552                            || handled_component_p (ref2->ref)
1553                            || TREE_CODE (ref2->ref) == MEM_REF
1554                            || TREE_CODE (ref2->ref) == TARGET_MEM_REF));
1555
1556   /* Decompose the references into their base objects and the access.  */
1557   base1 = ao_ref_base (ref1);
1558   offset1 = ref1->offset;
1559   max_size1 = ref1->max_size;
1560   base2 = ao_ref_base (ref2);
1561   offset2 = ref2->offset;
1562   max_size2 = ref2->max_size;
1563
1564   /* We can end up with registers or constants as bases for example from
1565      *D.1663_44 = VIEW_CONVERT_EXPR<struct DB_LSN>(__tmp$B0F64_59);
1566      which is seen as a struct copy.  */
1567   if (TREE_CODE (base1) == SSA_NAME
1568       || TREE_CODE (base1) == CONST_DECL
1569       || TREE_CODE (base1) == CONSTRUCTOR
1570       || TREE_CODE (base1) == ADDR_EXPR
1571       || CONSTANT_CLASS_P (base1)
1572       || TREE_CODE (base2) == SSA_NAME
1573       || TREE_CODE (base2) == CONST_DECL
1574       || TREE_CODE (base2) == CONSTRUCTOR
1575       || TREE_CODE (base2) == ADDR_EXPR
1576       || CONSTANT_CLASS_P (base2))
1577     return false;
1578
1579   /* We can end up referring to code via function and label decls.
1580      As we likely do not properly track code aliases conservatively
1581      bail out.  */
1582   if (TREE_CODE (base1) == FUNCTION_DECL
1583       || TREE_CODE (base1) == LABEL_DECL
1584       || TREE_CODE (base2) == FUNCTION_DECL
1585       || TREE_CODE (base2) == LABEL_DECL)
1586     return true;
1587
1588   /* Two volatile accesses always conflict.  */
1589   if (ref1->volatile_p
1590       && ref2->volatile_p)
1591     return true;
1592
1593   /* Defer to simple offset based disambiguation if we have
1594      references based on two decls.  Do this before defering to
1595      TBAA to handle must-alias cases in conformance with the
1596      GCC extension of allowing type-punning through unions.  */
1597   var1_p = DECL_P (base1);
1598   var2_p = DECL_P (base2);
1599   if (var1_p && var2_p)
1600     return decl_refs_may_alias_p (ref1->ref, base1, offset1, max_size1,
1601                                   ref2->ref, base2, offset2, max_size2);
1602
1603   /* Handle restrict based accesses.
1604      ???  ao_ref_base strips inner MEM_REF [&decl], recover from that
1605      here.  */
1606   tree rbase1 = base1;
1607   tree rbase2 = base2;
1608   if (var1_p)
1609     {
1610       rbase1 = ref1->ref;
1611       if (rbase1)
1612         while (handled_component_p (rbase1))
1613           rbase1 = TREE_OPERAND (rbase1, 0);
1614     }
1615   if (var2_p)
1616     {
1617       rbase2 = ref2->ref;
1618       if (rbase2)
1619         while (handled_component_p (rbase2))
1620           rbase2 = TREE_OPERAND (rbase2, 0);
1621     }
1622   if (rbase1 && rbase2
1623       && (TREE_CODE (base1) == MEM_REF || TREE_CODE (base1) == TARGET_MEM_REF)
1624       && (TREE_CODE (base2) == MEM_REF || TREE_CODE (base2) == TARGET_MEM_REF)
1625       /* If the accesses are in the same restrict clique... */
1626       && MR_DEPENDENCE_CLIQUE (base1) == MR_DEPENDENCE_CLIQUE (base2)
1627       /* But based on different pointers they do not alias.  */
1628       && MR_DEPENDENCE_BASE (base1) != MR_DEPENDENCE_BASE (base2))
1629     return false;
1630
1631   ind1_p = (TREE_CODE (base1) == MEM_REF
1632             || TREE_CODE (base1) == TARGET_MEM_REF);
1633   ind2_p = (TREE_CODE (base2) == MEM_REF
1634             || TREE_CODE (base2) == TARGET_MEM_REF);
1635
1636   /* Canonicalize the pointer-vs-decl case.  */
1637   if (ind1_p && var2_p)
1638     {
1639       std::swap (offset1, offset2);
1640       std::swap (max_size1, max_size2);
1641       std::swap (base1, base2);
1642       std::swap (ref1, ref2);
1643       var1_p = true;
1644       ind1_p = false;
1645       var2_p = false;
1646       ind2_p = true;
1647     }
1648
1649   /* First defer to TBAA if possible.  */
1650   if (tbaa_p
1651       && flag_strict_aliasing
1652       && !alias_sets_conflict_p (ao_ref_alias_set (ref1),
1653                                  ao_ref_alias_set (ref2)))
1654     return false;
1655
1656   /* If the reference is based on a pointer that points to memory
1657      that may not be written to then the other reference cannot possibly
1658      clobber it.  */
1659   if ((TREE_CODE (TREE_OPERAND (base2, 0)) == SSA_NAME
1660        && SSA_NAME_POINTS_TO_READONLY_MEMORY (TREE_OPERAND (base2, 0)))
1661       || (ind1_p
1662           && TREE_CODE (TREE_OPERAND (base1, 0)) == SSA_NAME
1663           && SSA_NAME_POINTS_TO_READONLY_MEMORY (TREE_OPERAND (base1, 0))))
1664     return false;
1665
1666   /* Dispatch to the pointer-vs-decl or pointer-vs-pointer disambiguators.  */
1667   if (var1_p && ind2_p)
1668     return indirect_ref_may_alias_decl_p (ref2->ref, base2,
1669                                           offset2, max_size2,
1670                                           ao_ref_alias_set (ref2),
1671                                           ao_ref_base_alias_set (ref2),
1672                                           ref1->ref, base1,
1673                                           offset1, max_size1,
1674                                           ao_ref_alias_set (ref1),
1675                                           ao_ref_base_alias_set (ref1),
1676                                           tbaa_p);
1677   else if (ind1_p && ind2_p)
1678     return indirect_refs_may_alias_p (ref1->ref, base1,
1679                                       offset1, max_size1,
1680                                       ao_ref_alias_set (ref1),
1681                                       ao_ref_base_alias_set (ref1),
1682                                       ref2->ref, base2,
1683                                       offset2, max_size2,
1684                                       ao_ref_alias_set (ref2),
1685                                       ao_ref_base_alias_set (ref2),
1686                                       tbaa_p);
1687
1688   gcc_unreachable ();
1689 }
1690
1691 /* Return true, if the two memory references REF1 and REF2 may alias
1692    and update statistics.  */
1693
1694 bool
1695 refs_may_alias_p_1 (ao_ref *ref1, ao_ref *ref2, bool tbaa_p)
1696 {
1697   bool res = refs_may_alias_p_2 (ref1, ref2, tbaa_p);
1698   if (res)
1699     ++alias_stats.refs_may_alias_p_may_alias;
1700   else
1701     ++alias_stats.refs_may_alias_p_no_alias;
1702   return res;
1703 }
1704
1705 static bool
1706 refs_may_alias_p (tree ref1, ao_ref *ref2, bool tbaa_p)
1707 {
1708   ao_ref r1;
1709   ao_ref_init (&r1, ref1);
1710   return refs_may_alias_p_1 (&r1, ref2, tbaa_p);
1711 }
1712
1713 bool
1714 refs_may_alias_p (tree ref1, tree ref2, bool tbaa_p)
1715 {
1716   ao_ref r1, r2;
1717   ao_ref_init (&r1, ref1);
1718   ao_ref_init (&r2, ref2);
1719   return refs_may_alias_p_1 (&r1, &r2, tbaa_p);
1720 }
1721
1722 /* Returns true if there is a anti-dependence for the STORE that
1723    executes after the LOAD.  */
1724
1725 bool
1726 refs_anti_dependent_p (tree load, tree store)
1727 {
1728   ao_ref r1, r2;
1729   ao_ref_init (&r1, load);
1730   ao_ref_init (&r2, store);
1731   return refs_may_alias_p_1 (&r1, &r2, false);
1732 }
1733
1734 /* Returns true if there is a output dependence for the stores
1735    STORE1 and STORE2.  */
1736
1737 bool
1738 refs_output_dependent_p (tree store1, tree store2)
1739 {
1740   ao_ref r1, r2;
1741   ao_ref_init (&r1, store1);
1742   ao_ref_init (&r2, store2);
1743   return refs_may_alias_p_1 (&r1, &r2, false);
1744 }
1745
1746 /* If the call CALL may use the memory reference REF return true,
1747    otherwise return false.  */
1748
1749 static bool
1750 ref_maybe_used_by_call_p_1 (gcall *call, ao_ref *ref, bool tbaa_p)
1751 {
1752   tree base, callee;
1753   unsigned i;
1754   int flags = gimple_call_flags (call);
1755
1756   /* Const functions without a static chain do not implicitly use memory.  */
1757   if (!gimple_call_chain (call)
1758       && (flags & (ECF_CONST|ECF_NOVOPS)))
1759     goto process_args;
1760
1761   base = ao_ref_base (ref);
1762   if (!base)
1763     return true;
1764
1765   /* A call that is not without side-effects might involve volatile
1766      accesses and thus conflicts with all other volatile accesses.  */
1767   if (ref->volatile_p)
1768     return true;
1769
1770   /* If the reference is based on a decl that is not aliased the call
1771      cannot possibly use it.  */
1772   if (DECL_P (base)
1773       && !may_be_aliased (base)
1774       /* But local statics can be used through recursion.  */
1775       && !is_global_var (base))
1776     goto process_args;
1777
1778   callee = gimple_call_fndecl (call);
1779
1780   /* Handle those builtin functions explicitly that do not act as
1781      escape points.  See tree-ssa-structalias.c:find_func_aliases
1782      for the list of builtins we might need to handle here.  */
1783   if (callee != NULL_TREE
1784       && gimple_call_builtin_p (call, BUILT_IN_NORMAL))
1785     switch (DECL_FUNCTION_CODE (callee))
1786       {
1787         /* All the following functions read memory pointed to by
1788            their second argument.  strcat/strncat additionally
1789            reads memory pointed to by the first argument.  */
1790         case BUILT_IN_STRCAT:
1791         case BUILT_IN_STRNCAT:
1792           {
1793             ao_ref dref;
1794             ao_ref_init_from_ptr_and_size (&dref,
1795                                            gimple_call_arg (call, 0),
1796                                            NULL_TREE);
1797             if (refs_may_alias_p_1 (&dref, ref, false))
1798               return true;
1799           }
1800           /* FALLTHRU */
1801         case BUILT_IN_STRCPY:
1802         case BUILT_IN_STRNCPY:
1803         case BUILT_IN_MEMCPY:
1804         case BUILT_IN_MEMMOVE:
1805         case BUILT_IN_MEMPCPY:
1806         case BUILT_IN_STPCPY:
1807         case BUILT_IN_STPNCPY:
1808         case BUILT_IN_TM_MEMCPY:
1809         case BUILT_IN_TM_MEMMOVE:
1810           {
1811             ao_ref dref;
1812             tree size = NULL_TREE;
1813             if (gimple_call_num_args (call) == 3)
1814               size = gimple_call_arg (call, 2);
1815             ao_ref_init_from_ptr_and_size (&dref,
1816                                            gimple_call_arg (call, 1),
1817                                            size);
1818             return refs_may_alias_p_1 (&dref, ref, false);
1819           }
1820         case BUILT_IN_STRCAT_CHK:
1821         case BUILT_IN_STRNCAT_CHK:
1822           {
1823             ao_ref dref;
1824             ao_ref_init_from_ptr_and_size (&dref,
1825                                            gimple_call_arg (call, 0),
1826                                            NULL_TREE);
1827             if (refs_may_alias_p_1 (&dref, ref, false))
1828               return true;
1829           }
1830           /* FALLTHRU */
1831         case BUILT_IN_STRCPY_CHK:
1832         case BUILT_IN_STRNCPY_CHK:
1833         case BUILT_IN_MEMCPY_CHK:
1834         case BUILT_IN_MEMMOVE_CHK:
1835         case BUILT_IN_MEMPCPY_CHK:
1836         case BUILT_IN_STPCPY_CHK:
1837         case BUILT_IN_STPNCPY_CHK:
1838           {
1839             ao_ref dref;
1840             tree size = NULL_TREE;
1841             if (gimple_call_num_args (call) == 4)
1842               size = gimple_call_arg (call, 2);
1843             ao_ref_init_from_ptr_and_size (&dref,
1844                                            gimple_call_arg (call, 1),
1845                                            size);
1846             return refs_may_alias_p_1 (&dref, ref, false);
1847           }
1848         case BUILT_IN_BCOPY:
1849           {
1850             ao_ref dref;
1851             tree size = gimple_call_arg (call, 2);
1852             ao_ref_init_from_ptr_and_size (&dref,
1853                                            gimple_call_arg (call, 0),
1854                                            size);
1855             return refs_may_alias_p_1 (&dref, ref, false);
1856           }
1857
1858         /* The following functions read memory pointed to by their
1859            first argument.  */
1860         CASE_BUILT_IN_TM_LOAD (1):
1861         CASE_BUILT_IN_TM_LOAD (2):
1862         CASE_BUILT_IN_TM_LOAD (4):
1863         CASE_BUILT_IN_TM_LOAD (8):
1864         CASE_BUILT_IN_TM_LOAD (FLOAT):
1865         CASE_BUILT_IN_TM_LOAD (DOUBLE):
1866         CASE_BUILT_IN_TM_LOAD (LDOUBLE):
1867         CASE_BUILT_IN_TM_LOAD (M64):
1868         CASE_BUILT_IN_TM_LOAD (M128):
1869         CASE_BUILT_IN_TM_LOAD (M256):
1870         case BUILT_IN_TM_LOG:
1871         case BUILT_IN_TM_LOG_1:
1872         case BUILT_IN_TM_LOG_2:
1873         case BUILT_IN_TM_LOG_4:
1874         case BUILT_IN_TM_LOG_8:
1875         case BUILT_IN_TM_LOG_FLOAT:
1876         case BUILT_IN_TM_LOG_DOUBLE:
1877         case BUILT_IN_TM_LOG_LDOUBLE:
1878         case BUILT_IN_TM_LOG_M64:
1879         case BUILT_IN_TM_LOG_M128:
1880         case BUILT_IN_TM_LOG_M256:
1881           return ptr_deref_may_alias_ref_p_1 (gimple_call_arg (call, 0), ref);
1882
1883         /* These read memory pointed to by the first argument.  */
1884         case BUILT_IN_STRDUP:
1885         case BUILT_IN_STRNDUP:
1886         case BUILT_IN_REALLOC:
1887           {
1888             ao_ref dref;
1889             tree size = NULL_TREE;
1890             if (gimple_call_num_args (call) == 2)
1891               size = gimple_call_arg (call, 1);
1892             ao_ref_init_from_ptr_and_size (&dref,
1893                                            gimple_call_arg (call, 0),
1894                                            size);
1895             return refs_may_alias_p_1 (&dref, ref, false);
1896           }
1897         /* These read memory pointed to by the first argument.  */
1898         case BUILT_IN_INDEX:
1899         case BUILT_IN_STRCHR:
1900         case BUILT_IN_STRRCHR:
1901           {
1902             ao_ref dref;
1903             ao_ref_init_from_ptr_and_size (&dref,
1904                                            gimple_call_arg (call, 0),
1905                                            NULL_TREE);
1906             return refs_may_alias_p_1 (&dref, ref, false);
1907           }
1908         /* These read memory pointed to by the first argument with size
1909            in the third argument.  */
1910         case BUILT_IN_MEMCHR:
1911           {
1912             ao_ref dref;
1913             ao_ref_init_from_ptr_and_size (&dref,
1914                                            gimple_call_arg (call, 0),
1915                                            gimple_call_arg (call, 2));
1916             return refs_may_alias_p_1 (&dref, ref, false);
1917           }
1918         /* These read memory pointed to by the first and second arguments.  */
1919         case BUILT_IN_STRSTR:
1920         case BUILT_IN_STRPBRK:
1921           {
1922             ao_ref dref;
1923             ao_ref_init_from_ptr_and_size (&dref,
1924                                            gimple_call_arg (call, 0),
1925                                            NULL_TREE);
1926             if (refs_may_alias_p_1 (&dref, ref, false))
1927               return true;
1928             ao_ref_init_from_ptr_and_size (&dref,
1929                                            gimple_call_arg (call, 1),
1930                                            NULL_TREE);
1931             return refs_may_alias_p_1 (&dref, ref, false);
1932           }
1933
1934         /* The following builtins do not read from memory.  */
1935         case BUILT_IN_FREE:
1936         case BUILT_IN_MALLOC:
1937         case BUILT_IN_POSIX_MEMALIGN:
1938         case BUILT_IN_ALIGNED_ALLOC:
1939         case BUILT_IN_CALLOC:
1940         CASE_BUILT_IN_ALLOCA:
1941         case BUILT_IN_STACK_SAVE:
1942         case BUILT_IN_STACK_RESTORE:
1943         case BUILT_IN_MEMSET:
1944         case BUILT_IN_TM_MEMSET:
1945         case BUILT_IN_MEMSET_CHK:
1946         case BUILT_IN_FREXP:
1947         case BUILT_IN_FREXPF:
1948         case BUILT_IN_FREXPL:
1949         case BUILT_IN_GAMMA_R:
1950         case BUILT_IN_GAMMAF_R:
1951         case BUILT_IN_GAMMAL_R:
1952         case BUILT_IN_LGAMMA_R:
1953         case BUILT_IN_LGAMMAF_R:
1954         case BUILT_IN_LGAMMAL_R:
1955         case BUILT_IN_MODF:
1956         case BUILT_IN_MODFF:
1957         case BUILT_IN_MODFL:
1958         case BUILT_IN_REMQUO:
1959         case BUILT_IN_REMQUOF:
1960         case BUILT_IN_REMQUOL:
1961         case BUILT_IN_SINCOS:
1962         case BUILT_IN_SINCOSF:
1963         case BUILT_IN_SINCOSL:
1964         case BUILT_IN_ASSUME_ALIGNED:
1965         case BUILT_IN_VA_END:
1966           return false;
1967         /* __sync_* builtins and some OpenMP builtins act as threading
1968            barriers.  */
1969 #undef DEF_SYNC_BUILTIN
1970 #define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
1971 #include "sync-builtins.def"
1972 #undef DEF_SYNC_BUILTIN
1973         case BUILT_IN_GOMP_ATOMIC_START:
1974         case BUILT_IN_GOMP_ATOMIC_END:
1975         case BUILT_IN_GOMP_BARRIER:
1976         case BUILT_IN_GOMP_BARRIER_CANCEL:
1977         case BUILT_IN_GOMP_TASKWAIT:
1978         case BUILT_IN_GOMP_TASKGROUP_END:
1979         case BUILT_IN_GOMP_CRITICAL_START:
1980         case BUILT_IN_GOMP_CRITICAL_END:
1981         case BUILT_IN_GOMP_CRITICAL_NAME_START:
1982         case BUILT_IN_GOMP_CRITICAL_NAME_END:
1983         case BUILT_IN_GOMP_LOOP_END:
1984         case BUILT_IN_GOMP_LOOP_END_CANCEL:
1985         case BUILT_IN_GOMP_ORDERED_START:
1986         case BUILT_IN_GOMP_ORDERED_END:
1987         case BUILT_IN_GOMP_SECTIONS_END:
1988         case BUILT_IN_GOMP_SECTIONS_END_CANCEL:
1989         case BUILT_IN_GOMP_SINGLE_COPY_START:
1990         case BUILT_IN_GOMP_SINGLE_COPY_END:
1991           return true;
1992
1993         default:
1994           /* Fallthru to general call handling.  */;
1995       }
1996
1997   /* Check if base is a global static variable that is not read
1998      by the function.  */
1999   if (callee != NULL_TREE && VAR_P (base) && TREE_STATIC (base))
2000     {
2001       struct cgraph_node *node = cgraph_node::get (callee);
2002       bitmap not_read;
2003
2004       /* FIXME: Callee can be an OMP builtin that does not have a call graph
2005          node yet.  We should enforce that there are nodes for all decls in the
2006          IL and remove this check instead.  */
2007       if (node
2008           && (not_read = ipa_reference_get_not_read_global (node))
2009           && bitmap_bit_p (not_read, ipa_reference_var_uid (base)))
2010         goto process_args;
2011     }
2012
2013   /* Check if the base variable is call-used.  */
2014   if (DECL_P (base))
2015     {
2016       if (pt_solution_includes (gimple_call_use_set (call), base))
2017         return true;
2018     }
2019   else if ((TREE_CODE (base) == MEM_REF
2020             || TREE_CODE (base) == TARGET_MEM_REF)
2021            && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
2022     {
2023       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0));
2024       if (!pi)
2025         return true;
2026
2027       if (pt_solutions_intersect (gimple_call_use_set (call), &pi->pt))
2028         return true;
2029     }
2030   else
2031     return true;
2032
2033   /* Inspect call arguments for passed-by-value aliases.  */
2034 process_args:
2035   for (i = 0; i < gimple_call_num_args (call); ++i)
2036     {
2037       tree op = gimple_call_arg (call, i);
2038       int flags = gimple_call_arg_flags (call, i);
2039
2040       if (flags & EAF_UNUSED)
2041         continue;
2042
2043       if (TREE_CODE (op) == WITH_SIZE_EXPR)
2044         op = TREE_OPERAND (op, 0);
2045
2046       if (TREE_CODE (op) != SSA_NAME
2047           && !is_gimple_min_invariant (op))
2048         {
2049           ao_ref r;
2050           ao_ref_init (&r, op);
2051           if (refs_may_alias_p_1 (&r, ref, tbaa_p))
2052             return true;
2053         }
2054     }
2055
2056   return false;
2057 }
2058
2059 static bool
2060 ref_maybe_used_by_call_p (gcall *call, ao_ref *ref, bool tbaa_p)
2061 {
2062   bool res;
2063   res = ref_maybe_used_by_call_p_1 (call, ref, tbaa_p);
2064   if (res)
2065     ++alias_stats.ref_maybe_used_by_call_p_may_alias;
2066   else
2067     ++alias_stats.ref_maybe_used_by_call_p_no_alias;
2068   return res;
2069 }
2070
2071
2072 /* If the statement STMT may use the memory reference REF return
2073    true, otherwise return false.  */
2074
2075 bool
2076 ref_maybe_used_by_stmt_p (gimple *stmt, ao_ref *ref, bool tbaa_p)
2077 {
2078   if (is_gimple_assign (stmt))
2079     {
2080       tree rhs;
2081
2082       /* All memory assign statements are single.  */
2083       if (!gimple_assign_single_p (stmt))
2084         return false;
2085
2086       rhs = gimple_assign_rhs1 (stmt);
2087       if (is_gimple_reg (rhs)
2088           || is_gimple_min_invariant (rhs)
2089           || gimple_assign_rhs_code (stmt) == CONSTRUCTOR)
2090         return false;
2091
2092       return refs_may_alias_p (rhs, ref, tbaa_p);
2093     }
2094   else if (is_gimple_call (stmt))
2095     return ref_maybe_used_by_call_p (as_a <gcall *> (stmt), ref, tbaa_p);
2096   else if (greturn *return_stmt = dyn_cast <greturn *> (stmt))
2097     {
2098       tree retval = gimple_return_retval (return_stmt);
2099       if (retval
2100           && TREE_CODE (retval) != SSA_NAME
2101           && !is_gimple_min_invariant (retval)
2102           && refs_may_alias_p (retval, ref, tbaa_p))
2103         return true;
2104       /* If ref escapes the function then the return acts as a use.  */
2105       tree base = ao_ref_base (ref);
2106       if (!base)
2107         ;
2108       else if (DECL_P (base))
2109         return is_global_var (base);
2110       else if (TREE_CODE (base) == MEM_REF
2111                || TREE_CODE (base) == TARGET_MEM_REF)
2112         return ptr_deref_may_alias_global_p (TREE_OPERAND (base, 0));
2113       return false;
2114     }
2115
2116   return true;
2117 }
2118
2119 bool
2120 ref_maybe_used_by_stmt_p (gimple *stmt, tree ref, bool tbaa_p)
2121 {
2122   ao_ref r;
2123   ao_ref_init (&r, ref);
2124   return ref_maybe_used_by_stmt_p (stmt, &r, tbaa_p);
2125 }
2126
2127 /* If the call in statement CALL may clobber the memory reference REF
2128    return true, otherwise return false.  */
2129
2130 bool
2131 call_may_clobber_ref_p_1 (gcall *call, ao_ref *ref)
2132 {
2133   tree base;
2134   tree callee;
2135
2136   /* If the call is pure or const it cannot clobber anything.  */
2137   if (gimple_call_flags (call)
2138       & (ECF_PURE|ECF_CONST|ECF_LOOPING_CONST_OR_PURE|ECF_NOVOPS))
2139     return false;
2140   if (gimple_call_internal_p (call))
2141     switch (gimple_call_internal_fn (call))
2142       {
2143         /* Treat these internal calls like ECF_PURE for aliasing,
2144            they don't write to any memory the program should care about.
2145            They have important other side-effects, and read memory,
2146            so can't be ECF_NOVOPS.  */
2147       case IFN_UBSAN_NULL:
2148       case IFN_UBSAN_BOUNDS:
2149       case IFN_UBSAN_VPTR:
2150       case IFN_UBSAN_OBJECT_SIZE:
2151       case IFN_UBSAN_PTR:
2152       case IFN_ASAN_CHECK:
2153         return false;
2154       default:
2155         break;
2156       }
2157
2158   base = ao_ref_base (ref);
2159   if (!base)
2160     return true;
2161
2162   if (TREE_CODE (base) == SSA_NAME
2163       || CONSTANT_CLASS_P (base))
2164     return false;
2165
2166   /* A call that is not without side-effects might involve volatile
2167      accesses and thus conflicts with all other volatile accesses.  */
2168   if (ref->volatile_p)
2169     return true;
2170
2171   /* If the reference is based on a decl that is not aliased the call
2172      cannot possibly clobber it.  */
2173   if (DECL_P (base)
2174       && !may_be_aliased (base)
2175       /* But local non-readonly statics can be modified through recursion
2176          or the call may implement a threading barrier which we must
2177          treat as may-def.  */
2178       && (TREE_READONLY (base)
2179           || !is_global_var (base)))
2180     return false;
2181
2182   /* If the reference is based on a pointer that points to memory
2183      that may not be written to then the call cannot possibly clobber it.  */
2184   if ((TREE_CODE (base) == MEM_REF
2185        || TREE_CODE (base) == TARGET_MEM_REF)
2186       && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME
2187       && SSA_NAME_POINTS_TO_READONLY_MEMORY (TREE_OPERAND (base, 0)))
2188     return false;
2189
2190   callee = gimple_call_fndecl (call);
2191
2192   /* Handle those builtin functions explicitly that do not act as
2193      escape points.  See tree-ssa-structalias.c:find_func_aliases
2194      for the list of builtins we might need to handle here.  */
2195   if (callee != NULL_TREE
2196       && gimple_call_builtin_p (call, BUILT_IN_NORMAL))
2197     switch (DECL_FUNCTION_CODE (callee))
2198       {
2199         /* All the following functions clobber memory pointed to by
2200            their first argument.  */
2201         case BUILT_IN_STRCPY:
2202         case BUILT_IN_STRNCPY:
2203         case BUILT_IN_MEMCPY:
2204         case BUILT_IN_MEMMOVE:
2205         case BUILT_IN_MEMPCPY:
2206         case BUILT_IN_STPCPY:
2207         case BUILT_IN_STPNCPY:
2208         case BUILT_IN_STRCAT:
2209         case BUILT_IN_STRNCAT:
2210         case BUILT_IN_MEMSET:
2211         case BUILT_IN_TM_MEMSET:
2212         CASE_BUILT_IN_TM_STORE (1):
2213         CASE_BUILT_IN_TM_STORE (2):
2214         CASE_BUILT_IN_TM_STORE (4):
2215         CASE_BUILT_IN_TM_STORE (8):
2216         CASE_BUILT_IN_TM_STORE (FLOAT):
2217         CASE_BUILT_IN_TM_STORE (DOUBLE):
2218         CASE_BUILT_IN_TM_STORE (LDOUBLE):
2219         CASE_BUILT_IN_TM_STORE (M64):
2220         CASE_BUILT_IN_TM_STORE (M128):
2221         CASE_BUILT_IN_TM_STORE (M256):
2222         case BUILT_IN_TM_MEMCPY:
2223         case BUILT_IN_TM_MEMMOVE:
2224           {
2225             ao_ref dref;
2226             tree size = NULL_TREE;
2227             /* Don't pass in size for strncat, as the maximum size
2228                is strlen (dest) + n + 1 instead of n, resp.
2229                n + 1 at dest + strlen (dest), but strlen (dest) isn't
2230                known.  */
2231             if (gimple_call_num_args (call) == 3
2232                 && DECL_FUNCTION_CODE (callee) != BUILT_IN_STRNCAT)
2233               size = gimple_call_arg (call, 2);
2234             ao_ref_init_from_ptr_and_size (&dref,
2235                                            gimple_call_arg (call, 0),
2236                                            size);
2237             return refs_may_alias_p_1 (&dref, ref, false);
2238           }
2239         case BUILT_IN_STRCPY_CHK:
2240         case BUILT_IN_STRNCPY_CHK:
2241         case BUILT_IN_MEMCPY_CHK:
2242         case BUILT_IN_MEMMOVE_CHK:
2243         case BUILT_IN_MEMPCPY_CHK:
2244         case BUILT_IN_STPCPY_CHK:
2245         case BUILT_IN_STPNCPY_CHK:
2246         case BUILT_IN_STRCAT_CHK:
2247         case BUILT_IN_STRNCAT_CHK:
2248         case BUILT_IN_MEMSET_CHK:
2249           {
2250             ao_ref dref;
2251             tree size = NULL_TREE;
2252             /* Don't pass in size for __strncat_chk, as the maximum size
2253                is strlen (dest) + n + 1 instead of n, resp.
2254                n + 1 at dest + strlen (dest), but strlen (dest) isn't
2255                known.  */
2256             if (gimple_call_num_args (call) == 4
2257                 && DECL_FUNCTION_CODE (callee) != BUILT_IN_STRNCAT_CHK)
2258               size = gimple_call_arg (call, 2);
2259             ao_ref_init_from_ptr_and_size (&dref,
2260                                            gimple_call_arg (call, 0),
2261                                            size);
2262             return refs_may_alias_p_1 (&dref, ref, false);
2263           }
2264         case BUILT_IN_BCOPY:
2265           {
2266             ao_ref dref;
2267             tree size = gimple_call_arg (call, 2);
2268             ao_ref_init_from_ptr_and_size (&dref,
2269                                            gimple_call_arg (call, 1),
2270                                            size);
2271             return refs_may_alias_p_1 (&dref, ref, false);
2272           }
2273         /* Allocating memory does not have any side-effects apart from
2274            being the definition point for the pointer.  */
2275         case BUILT_IN_MALLOC:
2276         case BUILT_IN_ALIGNED_ALLOC:
2277         case BUILT_IN_CALLOC:
2278         case BUILT_IN_STRDUP:
2279         case BUILT_IN_STRNDUP:
2280           /* Unix98 specifies that errno is set on allocation failure.  */
2281           if (flag_errno_math
2282               && targetm.ref_may_alias_errno (ref))
2283             return true;
2284           return false;
2285         case BUILT_IN_STACK_SAVE:
2286         CASE_BUILT_IN_ALLOCA:
2287         case BUILT_IN_ASSUME_ALIGNED:
2288           return false;
2289         /* But posix_memalign stores a pointer into the memory pointed to
2290            by its first argument.  */
2291         case BUILT_IN_POSIX_MEMALIGN:
2292           {
2293             tree ptrptr = gimple_call_arg (call, 0);
2294             ao_ref dref;
2295             ao_ref_init_from_ptr_and_size (&dref, ptrptr,
2296                                            TYPE_SIZE_UNIT (ptr_type_node));
2297             return (refs_may_alias_p_1 (&dref, ref, false)
2298                     || (flag_errno_math
2299                         && targetm.ref_may_alias_errno (ref)));
2300           }
2301         /* Freeing memory kills the pointed-to memory.  More importantly
2302            the call has to serve as a barrier for moving loads and stores
2303            across it.  */
2304         case BUILT_IN_FREE:
2305         case BUILT_IN_VA_END:
2306           {
2307             tree ptr = gimple_call_arg (call, 0);
2308             return ptr_deref_may_alias_ref_p_1 (ptr, ref);
2309           }
2310         /* Realloc serves both as allocation point and deallocation point.  */
2311         case BUILT_IN_REALLOC:
2312           {
2313             tree ptr = gimple_call_arg (call, 0);
2314             /* Unix98 specifies that errno is set on allocation failure.  */
2315             return ((flag_errno_math
2316                      && targetm.ref_may_alias_errno (ref))
2317                     || ptr_deref_may_alias_ref_p_1 (ptr, ref));
2318           }
2319         case BUILT_IN_GAMMA_R:
2320         case BUILT_IN_GAMMAF_R:
2321         case BUILT_IN_GAMMAL_R:
2322         case BUILT_IN_LGAMMA_R:
2323         case BUILT_IN_LGAMMAF_R:
2324         case BUILT_IN_LGAMMAL_R:
2325           {
2326             tree out = gimple_call_arg (call, 1);
2327             if (ptr_deref_may_alias_ref_p_1 (out, ref))
2328               return true;
2329             if (flag_errno_math)
2330               break;
2331             return false;
2332           }
2333         case BUILT_IN_FREXP:
2334         case BUILT_IN_FREXPF:
2335         case BUILT_IN_FREXPL:
2336         case BUILT_IN_MODF:
2337         case BUILT_IN_MODFF:
2338         case BUILT_IN_MODFL:
2339           {
2340             tree out = gimple_call_arg (call, 1);
2341             return ptr_deref_may_alias_ref_p_1 (out, ref);
2342           }
2343         case BUILT_IN_REMQUO:
2344         case BUILT_IN_REMQUOF:
2345         case BUILT_IN_REMQUOL:
2346           {
2347             tree out = gimple_call_arg (call, 2);
2348             if (ptr_deref_may_alias_ref_p_1 (out, ref))
2349               return true;
2350             if (flag_errno_math)
2351               break;
2352             return false;
2353           }
2354         case BUILT_IN_SINCOS:
2355         case BUILT_IN_SINCOSF:
2356         case BUILT_IN_SINCOSL:
2357           {
2358             tree sin = gimple_call_arg (call, 1);
2359             tree cos = gimple_call_arg (call, 2);
2360             return (ptr_deref_may_alias_ref_p_1 (sin, ref)
2361                     || ptr_deref_may_alias_ref_p_1 (cos, ref));
2362           }
2363         /* __sync_* builtins and some OpenMP builtins act as threading
2364            barriers.  */
2365 #undef DEF_SYNC_BUILTIN
2366 #define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
2367 #include "sync-builtins.def"
2368 #undef DEF_SYNC_BUILTIN
2369         case BUILT_IN_GOMP_ATOMIC_START:
2370         case BUILT_IN_GOMP_ATOMIC_END:
2371         case BUILT_IN_GOMP_BARRIER:
2372         case BUILT_IN_GOMP_BARRIER_CANCEL:
2373         case BUILT_IN_GOMP_TASKWAIT:
2374         case BUILT_IN_GOMP_TASKGROUP_END:
2375         case BUILT_IN_GOMP_CRITICAL_START:
2376         case BUILT_IN_GOMP_CRITICAL_END:
2377         case BUILT_IN_GOMP_CRITICAL_NAME_START:
2378         case BUILT_IN_GOMP_CRITICAL_NAME_END:
2379         case BUILT_IN_GOMP_LOOP_END:
2380         case BUILT_IN_GOMP_LOOP_END_CANCEL:
2381         case BUILT_IN_GOMP_ORDERED_START:
2382         case BUILT_IN_GOMP_ORDERED_END:
2383         case BUILT_IN_GOMP_SECTIONS_END:
2384         case BUILT_IN_GOMP_SECTIONS_END_CANCEL:
2385         case BUILT_IN_GOMP_SINGLE_COPY_START:
2386         case BUILT_IN_GOMP_SINGLE_COPY_END:
2387           return true;
2388         default:
2389           /* Fallthru to general call handling.  */;
2390       }
2391
2392   /* Check if base is a global static variable that is not written
2393      by the function.  */
2394   if (callee != NULL_TREE && VAR_P (base) && TREE_STATIC (base))
2395     {
2396       struct cgraph_node *node = cgraph_node::get (callee);
2397       bitmap not_written;
2398
2399       if (node
2400           && (not_written = ipa_reference_get_not_written_global (node))
2401           && bitmap_bit_p (not_written, ipa_reference_var_uid (base)))
2402         return false;
2403     }
2404
2405   /* Check if the base variable is call-clobbered.  */
2406   if (DECL_P (base))
2407     return pt_solution_includes (gimple_call_clobber_set (call), base);
2408   else if ((TREE_CODE (base) == MEM_REF
2409             || TREE_CODE (base) == TARGET_MEM_REF)
2410            && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
2411     {
2412       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0));
2413       if (!pi)
2414         return true;
2415
2416       return pt_solutions_intersect (gimple_call_clobber_set (call), &pi->pt);
2417     }
2418
2419   return true;
2420 }
2421
2422 /* If the call in statement CALL may clobber the memory reference REF
2423    return true, otherwise return false.  */
2424
2425 bool
2426 call_may_clobber_ref_p (gcall *call, tree ref)
2427 {
2428   bool res;
2429   ao_ref r;
2430   ao_ref_init (&r, ref);
2431   res = call_may_clobber_ref_p_1 (call, &r);
2432   if (res)
2433     ++alias_stats.call_may_clobber_ref_p_may_alias;
2434   else
2435     ++alias_stats.call_may_clobber_ref_p_no_alias;
2436   return res;
2437 }
2438
2439
2440 /* If the statement STMT may clobber the memory reference REF return true,
2441    otherwise return false.  */
2442
2443 bool
2444 stmt_may_clobber_ref_p_1 (gimple *stmt, ao_ref *ref, bool tbaa_p)
2445 {
2446   if (is_gimple_call (stmt))
2447     {
2448       tree lhs = gimple_call_lhs (stmt);
2449       if (lhs
2450           && TREE_CODE (lhs) != SSA_NAME)
2451         {
2452           ao_ref r;
2453           ao_ref_init (&r, lhs);
2454           if (refs_may_alias_p_1 (ref, &r, tbaa_p))
2455             return true;
2456         }
2457
2458       return call_may_clobber_ref_p_1 (as_a <gcall *> (stmt), ref);
2459     }
2460   else if (gimple_assign_single_p (stmt))
2461     {
2462       tree lhs = gimple_assign_lhs (stmt);
2463       if (TREE_CODE (lhs) != SSA_NAME)
2464         {
2465           ao_ref r;
2466           ao_ref_init (&r, lhs);
2467           return refs_may_alias_p_1 (ref, &r, tbaa_p);
2468         }
2469     }
2470   else if (gimple_code (stmt) == GIMPLE_ASM)
2471     return true;
2472
2473   return false;
2474 }
2475
2476 bool
2477 stmt_may_clobber_ref_p (gimple *stmt, tree ref, bool tbaa_p)
2478 {
2479   ao_ref r;
2480   ao_ref_init (&r, ref);
2481   return stmt_may_clobber_ref_p_1 (stmt, &r, tbaa_p);
2482 }
2483
2484 /* Return true if store1 and store2 described by corresponding tuples
2485    <BASE, OFFSET, SIZE, MAX_SIZE> have the same size and store to the same
2486    address.  */
2487
2488 static bool
2489 same_addr_size_stores_p (tree base1, poly_int64 offset1, poly_int64 size1,
2490                          poly_int64 max_size1,
2491                          tree base2, poly_int64 offset2, poly_int64 size2,
2492                          poly_int64 max_size2)
2493 {
2494   /* Offsets need to be 0.  */
2495   if (maybe_ne (offset1, 0)
2496       || maybe_ne (offset2, 0))
2497     return false;
2498
2499   bool base1_obj_p = SSA_VAR_P (base1);
2500   bool base2_obj_p = SSA_VAR_P (base2);
2501
2502   /* We need one object.  */
2503   if (base1_obj_p == base2_obj_p)
2504     return false;
2505   tree obj = base1_obj_p ? base1 : base2;
2506
2507   /* And we need one MEM_REF.  */
2508   bool base1_memref_p = TREE_CODE (base1) == MEM_REF;
2509   bool base2_memref_p = TREE_CODE (base2) == MEM_REF;
2510   if (base1_memref_p == base2_memref_p)
2511     return false;
2512   tree memref = base1_memref_p ? base1 : base2;
2513
2514   /* Sizes need to be valid.  */
2515   if (!known_size_p (max_size1)
2516       || !known_size_p (max_size2)
2517       || !known_size_p (size1)
2518       || !known_size_p (size2))
2519     return false;
2520
2521   /* Max_size needs to match size.  */
2522   if (maybe_ne (max_size1, size1)
2523       || maybe_ne (max_size2, size2))
2524     return false;
2525
2526   /* Sizes need to match.  */
2527   if (maybe_ne (size1, size2))
2528     return false;
2529
2530
2531   /* Check that memref is a store to pointer with singleton points-to info.  */
2532   if (!integer_zerop (TREE_OPERAND (memref, 1)))
2533     return false;
2534   tree ptr = TREE_OPERAND (memref, 0);
2535   if (TREE_CODE (ptr) != SSA_NAME)
2536     return false;
2537   struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
2538   unsigned int pt_uid;
2539   if (pi == NULL
2540       || !pt_solution_singleton_or_null_p (&pi->pt, &pt_uid))
2541     return false;
2542
2543   /* Be conservative with non-call exceptions when the address might
2544      be NULL.  */
2545   if (cfun->can_throw_non_call_exceptions && pi->pt.null)
2546     return false;
2547
2548   /* Check that ptr points relative to obj.  */
2549   unsigned int obj_uid = DECL_PT_UID (obj);
2550   if (obj_uid != pt_uid)
2551     return false;
2552
2553   /* Check that the object size is the same as the store size.  That ensures us
2554      that ptr points to the start of obj.  */
2555   return (DECL_SIZE (obj)
2556           && poly_int_tree_p (DECL_SIZE (obj))
2557           && known_eq (wi::to_poly_offset (DECL_SIZE (obj)), size1));
2558 }
2559
2560 /* If STMT kills the memory reference REF return true, otherwise
2561    return false.  */
2562
2563 bool
2564 stmt_kills_ref_p (gimple *stmt, ao_ref *ref)
2565 {
2566   if (!ao_ref_base (ref))
2567     return false;
2568
2569   if (gimple_has_lhs (stmt)
2570       && TREE_CODE (gimple_get_lhs (stmt)) != SSA_NAME
2571       /* The assignment is not necessarily carried out if it can throw
2572          and we can catch it in the current function where we could inspect
2573          the previous value.
2574          ???  We only need to care about the RHS throwing.  For aggregate
2575          assignments or similar calls and non-call exceptions the LHS
2576          might throw as well.  */
2577       && !stmt_can_throw_internal (cfun, stmt))
2578     {
2579       tree lhs = gimple_get_lhs (stmt);
2580       /* If LHS is literally a base of the access we are done.  */
2581       if (ref->ref)
2582         {
2583           tree base = ref->ref;
2584           tree innermost_dropped_array_ref = NULL_TREE;
2585           if (handled_component_p (base))
2586             {
2587               tree saved_lhs0 = NULL_TREE;
2588               if (handled_component_p (lhs))
2589                 {
2590                   saved_lhs0 = TREE_OPERAND (lhs, 0);
2591                   TREE_OPERAND (lhs, 0) = integer_zero_node;
2592                 }
2593               do
2594                 {
2595                   /* Just compare the outermost handled component, if
2596                      they are equal we have found a possible common
2597                      base.  */
2598                   tree saved_base0 = TREE_OPERAND (base, 0);
2599                   TREE_OPERAND (base, 0) = integer_zero_node;
2600                   bool res = operand_equal_p (lhs, base, 0);
2601                   TREE_OPERAND (base, 0) = saved_base0;
2602                   if (res)
2603                     break;
2604                   /* Remember if we drop an array-ref that we need to
2605                      double-check not being at struct end.  */
2606                   if (TREE_CODE (base) == ARRAY_REF
2607                       || TREE_CODE (base) == ARRAY_RANGE_REF)
2608                     innermost_dropped_array_ref = base;
2609                   /* Otherwise drop handled components of the access.  */
2610                   base = saved_base0;
2611                 }
2612               while (handled_component_p (base));
2613               if (saved_lhs0)
2614                 TREE_OPERAND (lhs, 0) = saved_lhs0;
2615             }
2616           /* Finally check if the lhs has the same address and size as the
2617              base candidate of the access.  Watch out if we have dropped
2618              an array-ref that was at struct end, this means ref->ref may
2619              be outside of the TYPE_SIZE of its base.  */
2620           if ((! innermost_dropped_array_ref
2621                || ! array_at_struct_end_p (innermost_dropped_array_ref))
2622               && (lhs == base
2623                   || (((TYPE_SIZE (TREE_TYPE (lhs))
2624                         == TYPE_SIZE (TREE_TYPE (base)))
2625                        || (TYPE_SIZE (TREE_TYPE (lhs))
2626                            && TYPE_SIZE (TREE_TYPE (base))
2627                            && operand_equal_p (TYPE_SIZE (TREE_TYPE (lhs)),
2628                                                TYPE_SIZE (TREE_TYPE (base)),
2629                                                0)))
2630                       && operand_equal_p (lhs, base,
2631                                           OEP_ADDRESS_OF
2632                                           | OEP_MATCH_SIDE_EFFECTS))))
2633             return true;
2634         }
2635
2636       /* Now look for non-literal equal bases with the restriction of
2637          handling constant offset and size.  */
2638       /* For a must-alias check we need to be able to constrain
2639          the access properly.  */
2640       if (!ref->max_size_known_p ())
2641         return false;
2642       poly_int64 size, offset, max_size, ref_offset = ref->offset;
2643       bool reverse;
2644       tree base = get_ref_base_and_extent (lhs, &offset, &size, &max_size,
2645                                            &reverse);
2646       /* We can get MEM[symbol: sZ, index: D.8862_1] here,
2647          so base == ref->base does not always hold.  */
2648       if (base != ref->base)
2649         {
2650           /* Try using points-to info.  */
2651           if (same_addr_size_stores_p (base, offset, size, max_size, ref->base,
2652                                        ref->offset, ref->size, ref->max_size))
2653             return true;
2654
2655           /* If both base and ref->base are MEM_REFs, only compare the
2656              first operand, and if the second operand isn't equal constant,
2657              try to add the offsets into offset and ref_offset.  */
2658           if (TREE_CODE (base) == MEM_REF && TREE_CODE (ref->base) == MEM_REF
2659               && TREE_OPERAND (base, 0) == TREE_OPERAND (ref->base, 0))
2660             {
2661               if (!tree_int_cst_equal (TREE_OPERAND (base, 1),
2662                                        TREE_OPERAND (ref->base, 1)))
2663                 {
2664                   poly_offset_int off1 = mem_ref_offset (base);
2665                   off1 <<= LOG2_BITS_PER_UNIT;
2666                   off1 += offset;
2667                   poly_offset_int off2 = mem_ref_offset (ref->base);
2668                   off2 <<= LOG2_BITS_PER_UNIT;
2669                   off2 += ref_offset;
2670                   if (!off1.to_shwi (&offset) || !off2.to_shwi (&ref_offset))
2671                     size = -1;
2672                 }
2673             }
2674           else
2675             size = -1;
2676         }
2677       /* For a must-alias check we need to be able to constrain
2678          the access properly.  */
2679       if (known_eq (size, max_size)
2680           && known_subrange_p (ref_offset, ref->max_size, offset, size))
2681         return true;
2682     }
2683
2684   if (is_gimple_call (stmt))
2685     {
2686       tree callee = gimple_call_fndecl (stmt);
2687       if (callee != NULL_TREE
2688           && gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
2689         switch (DECL_FUNCTION_CODE (callee))
2690           {
2691           case BUILT_IN_FREE:
2692             {
2693               tree ptr = gimple_call_arg (stmt, 0);
2694               tree base = ao_ref_base (ref);
2695               if (base && TREE_CODE (base) == MEM_REF
2696                   && TREE_OPERAND (base, 0) == ptr)
2697                 return true;
2698               break;
2699             }
2700
2701           case BUILT_IN_MEMCPY:
2702           case BUILT_IN_MEMPCPY:
2703           case BUILT_IN_MEMMOVE:
2704           case BUILT_IN_MEMSET:
2705           case BUILT_IN_MEMCPY_CHK:
2706           case BUILT_IN_MEMPCPY_CHK:
2707           case BUILT_IN_MEMMOVE_CHK:
2708           case BUILT_IN_MEMSET_CHK:
2709           case BUILT_IN_STRNCPY:
2710           case BUILT_IN_STPNCPY:
2711             {
2712               /* For a must-alias check we need to be able to constrain
2713                  the access properly.  */
2714               if (!ref->max_size_known_p ())
2715                 return false;
2716               tree dest = gimple_call_arg (stmt, 0);
2717               tree len = gimple_call_arg (stmt, 2);
2718               if (!poly_int_tree_p (len))
2719                 return false;
2720               tree rbase = ref->base;
2721               poly_offset_int roffset = ref->offset;
2722               ao_ref dref;
2723               ao_ref_init_from_ptr_and_size (&dref, dest, len);
2724               tree base = ao_ref_base (&dref);
2725               poly_offset_int offset = dref.offset;
2726               if (!base || !known_size_p (dref.size))
2727                 return false;
2728               if (TREE_CODE (base) == MEM_REF)
2729                 {
2730                   if (TREE_CODE (rbase) != MEM_REF)
2731                     return false;
2732                   // Compare pointers.
2733                   offset += mem_ref_offset (base) << LOG2_BITS_PER_UNIT;
2734                   roffset += mem_ref_offset (rbase) << LOG2_BITS_PER_UNIT;
2735                   base = TREE_OPERAND (base, 0);
2736                   rbase = TREE_OPERAND (rbase, 0);
2737                 }
2738               if (base == rbase
2739                   && known_subrange_p (roffset, ref->max_size, offset,
2740                                        wi::to_poly_offset (len)
2741                                        << LOG2_BITS_PER_UNIT))
2742                 return true;
2743               break;
2744             }
2745
2746           case BUILT_IN_VA_END:
2747             {
2748               tree ptr = gimple_call_arg (stmt, 0);
2749               if (TREE_CODE (ptr) == ADDR_EXPR)
2750                 {
2751                   tree base = ao_ref_base (ref);
2752                   if (TREE_OPERAND (ptr, 0) == base)
2753                     return true;
2754                 }
2755               break;
2756             }
2757
2758           default:;
2759           }
2760     }
2761   return false;
2762 }
2763
2764 bool
2765 stmt_kills_ref_p (gimple *stmt, tree ref)
2766 {
2767   ao_ref r;
2768   ao_ref_init (&r, ref);
2769   return stmt_kills_ref_p (stmt, &r);
2770 }
2771
2772
2773 /* Walk the virtual use-def chain of VUSE until hitting the virtual operand
2774    TARGET or a statement clobbering the memory reference REF in which
2775    case false is returned.  The walk starts with VUSE, one argument of PHI.  */
2776
2777 static bool
2778 maybe_skip_until (gimple *phi, tree &target, basic_block target_bb,
2779                   ao_ref *ref, tree vuse, unsigned int &limit, bitmap *visited,
2780                   bool abort_on_visited,
2781                   void *(*translate)(ao_ref *, tree, void *, bool *),
2782                   void *data)
2783 {
2784   basic_block bb = gimple_bb (phi);
2785
2786   if (!*visited)
2787     *visited = BITMAP_ALLOC (NULL);
2788
2789   bitmap_set_bit (*visited, SSA_NAME_VERSION (PHI_RESULT (phi)));
2790
2791   /* Walk until we hit the target.  */
2792   while (vuse != target)
2793     {
2794       gimple *def_stmt = SSA_NAME_DEF_STMT (vuse);
2795       /* If we are searching for the target VUSE by walking up to
2796          TARGET_BB dominating the original PHI we are finished once
2797          we reach a default def or a definition in a block dominating
2798          that block.  Update TARGET and return.  */
2799       if (!target
2800           && (gimple_nop_p (def_stmt)
2801               || dominated_by_p (CDI_DOMINATORS,
2802                                  target_bb, gimple_bb (def_stmt))))
2803         {
2804           target = vuse;
2805           return true;
2806         }
2807
2808       /* Recurse for PHI nodes.  */
2809       if (gimple_code (def_stmt) == GIMPLE_PHI)
2810         {
2811           /* An already visited PHI node ends the walk successfully.  */
2812           if (bitmap_bit_p (*visited, SSA_NAME_VERSION (PHI_RESULT (def_stmt))))
2813             return !abort_on_visited;
2814           vuse = get_continuation_for_phi (def_stmt, ref, limit,
2815                                            visited, abort_on_visited,
2816                                            translate, data);
2817           if (!vuse)
2818             return false;
2819           continue;
2820         }
2821       else if (gimple_nop_p (def_stmt))
2822         return false;
2823       else
2824         {
2825           /* A clobbering statement or the end of the IL ends it failing.  */
2826           if ((int)limit <= 0)
2827             return false;
2828           --limit;
2829           if (stmt_may_clobber_ref_p_1 (def_stmt, ref))
2830             {
2831               bool disambiguate_only = true;
2832               if (translate
2833                   && (*translate) (ref, vuse, data, &disambiguate_only) == NULL)
2834                 ;
2835               else
2836                 return false;
2837             }
2838         }
2839       /* If we reach a new basic-block see if we already skipped it
2840          in a previous walk that ended successfully.  */
2841       if (gimple_bb (def_stmt) != bb)
2842         {
2843           if (!bitmap_set_bit (*visited, SSA_NAME_VERSION (vuse)))
2844             return !abort_on_visited;
2845           bb = gimple_bb (def_stmt);
2846         }
2847       vuse = gimple_vuse (def_stmt);
2848     }
2849   return true;
2850 }
2851
2852
2853 /* Starting from a PHI node for the virtual operand of the memory reference
2854    REF find a continuation virtual operand that allows to continue walking
2855    statements dominating PHI skipping only statements that cannot possibly
2856    clobber REF.  Decrements LIMIT for each alias disambiguation done
2857    and aborts the walk, returning NULL_TREE if it reaches zero.
2858    Returns NULL_TREE if no suitable virtual operand can be found.  */
2859
2860 tree
2861 get_continuation_for_phi (gimple *phi, ao_ref *ref,
2862                           unsigned int &limit, bitmap *visited,
2863                           bool abort_on_visited,
2864                           void *(*translate)(ao_ref *, tree, void *, bool *),
2865                           void *data)
2866 {
2867   unsigned nargs = gimple_phi_num_args (phi);
2868
2869   /* Through a single-argument PHI we can simply look through.  */
2870   if (nargs == 1)
2871     return PHI_ARG_DEF (phi, 0);
2872
2873   /* For two or more arguments try to pairwise skip non-aliasing code
2874      until we hit the phi argument definition that dominates the other one.  */
2875   basic_block phi_bb = gimple_bb (phi);
2876   tree arg0, arg1;
2877   unsigned i;
2878
2879   /* Find a candidate for the virtual operand which definition
2880      dominates those of all others.  */
2881   /* First look if any of the args themselves satisfy this.  */
2882   for (i = 0; i < nargs; ++i)
2883     {
2884       arg0 = PHI_ARG_DEF (phi, i);
2885       if (SSA_NAME_IS_DEFAULT_DEF (arg0))
2886         break;
2887       basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (arg0));
2888       if (def_bb != phi_bb
2889           && dominated_by_p (CDI_DOMINATORS, phi_bb, def_bb))
2890         break;
2891       arg0 = NULL_TREE;
2892     }
2893   /* If not, look if we can reach such candidate by walking defs
2894      until we hit the immediate dominator.  maybe_skip_until will
2895      do that for us.  */
2896   basic_block dom = get_immediate_dominator (CDI_DOMINATORS, phi_bb);
2897
2898   /* Then check against the (to be) found candidate.  */
2899   for (i = 0; i < nargs; ++i)
2900     {
2901       arg1 = PHI_ARG_DEF (phi, i);
2902       if (arg1 == arg0)
2903         ;
2904       else if (! maybe_skip_until (phi, arg0, dom, ref, arg1, limit, visited,
2905                                    abort_on_visited,
2906                                    /* Do not translate when walking over
2907                                       backedges.  */
2908                                    dominated_by_p
2909                                      (CDI_DOMINATORS,
2910                                       gimple_bb (SSA_NAME_DEF_STMT (arg1)),
2911                                       phi_bb)
2912                                    ? NULL : translate, data))
2913         return NULL_TREE;
2914     }
2915
2916   return arg0;
2917 }
2918
2919 /* Based on the memory reference REF and its virtual use VUSE call
2920    WALKER for each virtual use that is equivalent to VUSE, including VUSE
2921    itself.  That is, for each virtual use for which its defining statement
2922    does not clobber REF.
2923
2924    WALKER is called with REF, the current virtual use and DATA.  If
2925    WALKER returns non-NULL the walk stops and its result is returned.
2926    At the end of a non-successful walk NULL is returned.
2927
2928    TRANSLATE if non-NULL is called with a pointer to REF, the virtual
2929    use which definition is a statement that may clobber REF and DATA.
2930    If TRANSLATE returns (void *)-1 the walk stops and NULL is returned.
2931    If TRANSLATE returns non-NULL the walk stops and its result is returned.
2932    If TRANSLATE returns NULL the walk continues and TRANSLATE is supposed
2933    to adjust REF and *DATA to make that valid.
2934
2935    VALUEIZE if non-NULL is called with the next VUSE that is considered
2936    and return value is substituted for that.  This can be used to
2937    implement optimistic value-numbering for example.  Note that the
2938    VUSE argument is assumed to be valueized already.
2939
2940    LIMIT specifies the number of alias queries we are allowed to do,
2941    the walk stops when it reaches zero and NULL is returned.  LIMIT
2942    is decremented by the number of alias queries (plus adjustments
2943    done by the callbacks) upon return.
2944
2945    TODO: Cache the vector of equivalent vuses per ref, vuse pair.  */
2946
2947 void *
2948 walk_non_aliased_vuses (ao_ref *ref, tree vuse,
2949                         void *(*walker)(ao_ref *, tree, void *),
2950                         void *(*translate)(ao_ref *, tree, void *, bool *),
2951                         tree (*valueize)(tree),
2952                         unsigned &limit, void *data)
2953 {
2954   bitmap visited = NULL;
2955   void *res;
2956   bool translated = false;
2957
2958   timevar_push (TV_ALIAS_STMT_WALK);
2959
2960   do
2961     {
2962       gimple *def_stmt;
2963
2964       /* ???  Do we want to account this to TV_ALIAS_STMT_WALK?  */
2965       res = (*walker) (ref, vuse, data);
2966       /* Abort walk.  */
2967       if (res == (void *)-1)
2968         {
2969           res = NULL;
2970           break;
2971         }
2972       /* Lookup succeeded.  */
2973       else if (res != NULL)
2974         break;
2975
2976       if (valueize)
2977         {
2978           vuse = valueize (vuse);
2979           if (!vuse)
2980             {
2981               res = NULL;
2982               break;
2983             }
2984         }
2985       def_stmt = SSA_NAME_DEF_STMT (vuse);
2986       if (gimple_nop_p (def_stmt))
2987         break;
2988       else if (gimple_code (def_stmt) == GIMPLE_PHI)
2989         vuse = get_continuation_for_phi (def_stmt, ref, limit,
2990                                          &visited, translated, translate, data);
2991       else
2992         {
2993           if ((int)limit <= 0)
2994             {
2995               res = NULL;
2996               break;
2997             }
2998           if (stmt_may_clobber_ref_p_1 (def_stmt, ref))
2999             {
3000               if (!translate)
3001                 break;
3002               bool disambiguate_only = false;
3003               res = (*translate) (ref, vuse, data, &disambiguate_only);
3004               /* Failed lookup and translation.  */
3005               if (res == (void *)-1)
3006                 {
3007                   res = NULL;
3008                   break;
3009                 }
3010               /* Lookup succeeded.  */
3011               else if (res != NULL)
3012                 break;
3013               /* Translation succeeded, continue walking.  */
3014               translated = translated || !disambiguate_only;
3015             }
3016           vuse = gimple_vuse (def_stmt);
3017         }
3018     }
3019   while (vuse);
3020
3021   if (visited)
3022     BITMAP_FREE (visited);
3023
3024   timevar_pop (TV_ALIAS_STMT_WALK);
3025
3026   return res;
3027 }
3028
3029
3030 /* Based on the memory reference REF call WALKER for each vdef which
3031    defining statement may clobber REF, starting with VDEF.  If REF
3032    is NULL_TREE, each defining statement is visited.
3033
3034    WALKER is called with REF, the current vdef and DATA.  If WALKER
3035    returns true the walk is stopped, otherwise it continues.
3036
3037    If function entry is reached, FUNCTION_ENTRY_REACHED is set to true.
3038    The pointer may be NULL and then we do not track this information.
3039
3040    At PHI nodes walk_aliased_vdefs forks into one walk for reach
3041    PHI argument (but only one walk continues on merge points), the
3042    return value is true if any of the walks was successful.
3043
3044    The function returns the number of statements walked or -1 if
3045    LIMIT stmts were walked and the walk was aborted at this point.
3046    If LIMIT is zero the walk is not aborted.  */
3047
3048 static int
3049 walk_aliased_vdefs_1 (ao_ref *ref, tree vdef,
3050                       bool (*walker)(ao_ref *, tree, void *), void *data,
3051                       bitmap *visited, unsigned int cnt,
3052                       bool *function_entry_reached, unsigned limit)
3053 {
3054   do
3055     {
3056       gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
3057
3058       if (*visited
3059           && !bitmap_set_bit (*visited, SSA_NAME_VERSION (vdef)))
3060         return cnt;
3061
3062       if (gimple_nop_p (def_stmt))
3063         {
3064           if (function_entry_reached)
3065             *function_entry_reached = true;
3066           return cnt;
3067         }
3068       else if (gimple_code (def_stmt) == GIMPLE_PHI)
3069         {
3070           unsigned i;
3071           if (!*visited)
3072             *visited = BITMAP_ALLOC (NULL);
3073           for (i = 0; i < gimple_phi_num_args (def_stmt); ++i)
3074             {
3075               int res = walk_aliased_vdefs_1 (ref,
3076                                               gimple_phi_arg_def (def_stmt, i),
3077                                               walker, data, visited, cnt,
3078                                               function_entry_reached, limit);
3079               if (res == -1)
3080                 return -1;
3081               cnt = res;
3082             }
3083           return cnt;
3084         }
3085
3086       /* ???  Do we want to account this to TV_ALIAS_STMT_WALK?  */
3087       cnt++;
3088       if (cnt == limit)
3089         return -1;
3090       if ((!ref
3091            || stmt_may_clobber_ref_p_1 (def_stmt, ref))
3092           && (*walker) (ref, vdef, data))
3093         return cnt;
3094
3095       vdef = gimple_vuse (def_stmt);
3096     }
3097   while (1);
3098 }
3099
3100 int
3101 walk_aliased_vdefs (ao_ref *ref, tree vdef,
3102                     bool (*walker)(ao_ref *, tree, void *), void *data,
3103                     bitmap *visited,
3104                     bool *function_entry_reached, unsigned int limit)
3105 {
3106   bitmap local_visited = NULL;
3107   int ret;
3108
3109   timevar_push (TV_ALIAS_STMT_WALK);
3110
3111   if (function_entry_reached)
3112     *function_entry_reached = false;
3113
3114   ret = walk_aliased_vdefs_1 (ref, vdef, walker, data,
3115                               visited ? visited : &local_visited, 0,
3116                               function_entry_reached, limit);
3117   if (local_visited)
3118     BITMAP_FREE (local_visited);
3119
3120   timevar_pop (TV_ALIAS_STMT_WALK);
3121
3122   return ret;
3123 }
3124