gcc/gimple-ssa-warn-restrict.c

   1 /* Pass to detect and issue warnings for violations of the restrict
   2    qualifier.
   3    Copyright (C) 2017 Free Software Foundation, Inc.
   4    Contributed by Martin Sebor <msebor@redhat.com>.
   5
   6    This file is part of GCC.
   7
   8    GCC is free software; you can redistribute it and/or modify it under
   9    the terms of the GNU General Public License as published by the Free
  10    Software Foundation; either version 3, or (at your option) any later
  11    version.
  12
  13    GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14    WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15    FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16    for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with GCC; see the file COPYING3.  If not see
  20    <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "backend.h"
  26 #include "tree.h"
  27 #include "gimple.h"
  28 #include "domwalk.h"
  29 #include "tree-pass.h"
  30 #include "builtins.h"
  31 #include "ssa.h"
  32 #include "gimple-pretty-print.h"
  33 #include "gimple-ssa-warn-restrict.h"
  34 #include "diagnostic-core.h"
  35 #include "fold-const.h"
  36 #include "gimple-iterator.h"
  37 #include "tree-dfa.h"
  38 #include "tree-ssa.h"
  39 #include "params.h"
  40 #include "tree-cfg.h"
  41 #include "tree-object-size.h"
  42 #include "calls.h"
  43 #include "cfgloop.h"
  44 #include "intl.h"
  45
  46 namespace {
  47
  48 const pass_data pass_data_wrestrict = {
  49   GIMPLE_PASS,
  50   "wrestrict",
  51   OPTGROUP_NONE,
  52   TV_NONE,
  53   PROP_cfg, /* Properties_required.  */
  54   0,        /* properties_provided.  */
  55   0,        /* properties_destroyed.  */
  56   0,        /* properties_start */
  57   0,        /* properties_finish */
  58 };
  59
  60 /* Pass to detect violations of strict aliasing requirements in calls
  61    to built-in string and raw memory functions.  */
  62 class pass_wrestrict : public gimple_opt_pass
  63 {
  64  public:
  65   pass_wrestrict (gcc::context *ctxt)
  66     : gimple_opt_pass (pass_data_wrestrict, ctxt)
  67     { }
  68
  69   opt_pass *clone () { return new pass_wrestrict (m_ctxt); }
  70
  71   virtual bool gate (function *);
  72   virtual unsigned int execute (function *);
  73 };
  74
  75 bool
  76 pass_wrestrict::gate (function *fun ATTRIBUTE_UNUSED)
  77 {
  78   return warn_array_bounds != 0 || warn_restrict != 0;
  79 }
  80
  81 /* Class to walk the basic blocks of a function in dominator order.  */
  82 class wrestrict_dom_walker : public dom_walker
  83 {
  84  public:
  85   wrestrict_dom_walker () : dom_walker (CDI_DOMINATORS) {}
  86
  87   edge before_dom_children (basic_block) FINAL OVERRIDE;
  88   bool handle_gimple_call (gimple_stmt_iterator *);
  89
  90  private:
  91   void check_call (gcall *);
  92 };
  93
  94 edge
  95 wrestrict_dom_walker::before_dom_children (basic_block bb)
  96 {
  97   /* Iterate over statements, looking for function calls.  */
  98   for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
  99        gsi_next (&si))
 100     {
 101       gimple *stmt = gsi_stmt (si);
 102       if (!is_gimple_call (stmt))
 103         continue;
 104
 105       if (gcall *call = as_a <gcall *> (stmt))
 106         check_call (call);
 107     }
 108
 109   return NULL;
 110 }
 111
 112 /* Execute the pass for function FUN, walking in dominator order.  */
 113
 114 unsigned
 115 pass_wrestrict::execute (function *fun)
 116 {
 117   calculate_dominance_info (CDI_DOMINATORS);
 118
 119   wrestrict_dom_walker walker;
 120   walker.walk (ENTRY_BLOCK_PTR_FOR_FN (fun));
 121
 122   return 0;
 123 }
 124
 125 /* Description of a memory reference by a built-in function.  This
 126    is similar to ao_ref but made especially suitable for -Wrestrict
 127    and not for optimization.  */
 128 struct builtin_memref
 129 {
 130   /* The original pointer argument to the built-in function.  */
 131   tree ptr;
 132   /* The referenced subobject or NULL if not available, and the base
 133      object of the memory reference or NULL.  */
 134   tree ref;
 135   tree base;
 136
 137   /* The size of the BASE object, PTRDIFF_MAX if indeterminate,
 138      and negative until (possibly lazily) initialized.  */
 139   offset_int basesize;
 140
 141   /* The non-negative offset of the referenced subobject.  Used to avoid
 142      warnings for (apparently) possibly but not definitively overlapping
 143      accesses to member arrays.  Negative when unknown/invalid.  */
 144   offset_int refoff;
 145
 146   /* The offset range relative to the base.  */
 147   offset_int offrange[2];
 148   /* The size range of the access to this reference.  */
 149   offset_int sizrange[2];
 150
 151   /* True for "bounded" string functions like strncat, and strncpy
 152      and their variants that specify either an exact or upper bound
 153      on the size of the accesses they perform.  For strncat both
 154      the source and destination references are bounded.  For strncpy
 155      only the destination reference is.  */
 156   bool strbounded_p;
 157
 158   builtin_memref (tree, tree);
 159
 160   tree offset_out_of_bounds (int, offset_int[2]) const;
 161 };
 162
 163 /* Description of a memory access by a raw memory or string built-in
 164    function involving a pair of builtin_memref's.  */
 165 class builtin_access
 166 {
 167  public:
 168   /* Destination and source memory reference.  */
 169   builtin_memref* const dstref;
 170   builtin_memref* const srcref;
 171   /* The size range of the access.  It's the greater of the accesses
 172      to the two references.  */
 173   HOST_WIDE_INT sizrange[2];
 174
 175   /* The minimum and maximum offset of an overlap of the access
 176      (if it does, in fact, overlap), and the size of the overlap.  */
 177   HOST_WIDE_INT ovloff[2];
 178   HOST_WIDE_INT ovlsiz[2];
 179
 180   /* True to consider valid only accesses to the smallest subobject
 181      and false for raw memory functions.  */
 182   bool strict () const
 183   {
 184     return detect_overlap != &builtin_access::generic_overlap;
 185   }
 186
 187   builtin_access (gcall *, builtin_memref &, builtin_memref &);
 188
 189   /* Entry point to determine overlap.  */
 190   bool overlap ();
 191
 192  private:
 193   /* Implementation functions used to determine overlap.  */
 194   bool generic_overlap ();
 195   bool strcat_overlap ();
 196   bool strcpy_overlap ();
 197
 198   bool no_overlap ()
 199   {
 200     return false;
 201   }
 202
 203   offset_int overlap_size (const offset_int [2], const offset_int[2],
 204                            offset_int [2]);
 205
 206  private:
 207   /* Temporaries used to compute the final result.  */
 208   offset_int dstoff[2];
 209   offset_int srcoff[2];
 210   offset_int dstsiz[2];
 211   offset_int srcsiz[2];
 212
 213   /* Pointer to a member function to call to determine overlap.  */
 214   bool (builtin_access::*detect_overlap) ();
 215 };
 216
 217 /* Initialize a memory reference representation from a pointer EXPR and
 218    a size SIZE in bytes.  If SIZE is NULL_TREE then the size is assumed
 219    to be unknown.  */
 220
 221 builtin_memref::builtin_memref (tree expr, tree size)
 222 : ptr (expr),
 223   ref (),
 224   base (),
 225   basesize (-1),
 226   refoff (HOST_WIDE_INT_MIN),
 227   offrange (),
 228   sizrange (),
 229   strbounded_p ()
 230 {
 231   /* Unfortunately, wide_int default ctor is a no-op so array members
 232      of the type must be set individually.  */
 233   offrange[0] = offrange[1] = 0;
 234   sizrange[0] = sizrange[1] = 0;
 235
 236   const offset_int maxobjsize = tree_to_shwi (max_object_size ());
 237
 238   if (TREE_CODE (expr) == SSA_NAME)
 239     {
 240       /* Try to tease the offset out of the pointer.  */
 241       gimple *stmt = SSA_NAME_DEF_STMT (expr);
 242       if (gimple_assign_single_p (stmt)
 243           && gimple_assign_rhs_code (stmt) == ADDR_EXPR)
 244         expr = gimple_assign_rhs1 (stmt);
 245       else if (is_gimple_assign (stmt))
 246         {
 247           tree_code code = gimple_assign_rhs_code (stmt);
 248           if (code == NOP_EXPR)
 249             {
 250               tree rhs = gimple_assign_rhs1 (stmt);
 251               if (POINTER_TYPE_P (TREE_TYPE (rhs)))
 252                 expr = gimple_assign_rhs1 (stmt);
 253             }
 254           else if (code == POINTER_PLUS_EXPR)
 255             {
 256               expr = gimple_assign_rhs1 (stmt);
 257
 258               tree offset = gimple_assign_rhs2 (stmt);
 259               if (TREE_CODE (offset) == INTEGER_CST)
 260                 {
 261                   offset_int off = int_cst_value (offset);
 262                   offrange[0] = off;
 263                   offrange[1] = off;
 264
 265                   if (TREE_CODE (expr) == SSA_NAME)
 266                     {
 267                       gimple *stmt = SSA_NAME_DEF_STMT (expr);
 268                       if (gimple_assign_single_p (stmt)
 269                           && gimple_assign_rhs_code (stmt) == ADDR_EXPR)
 270                         expr = gimple_assign_rhs1 (stmt);
 271                     }
 272                 }
 273               else if (TREE_CODE (offset) == SSA_NAME)
 274                 {
 275                   wide_int min, max;
 276                   value_range_type rng = get_range_info (offset, &min, &max);
 277                   if (rng == VR_RANGE)
 278                     {
 279                       offrange[0] = min.to_shwi ();
 280                       offrange[1] = max.to_shwi ();
 281                     }
 282                   else if (rng == VR_ANTI_RANGE)
 283                     {
 284                       offrange[0] = (max + 1).to_shwi ();
 285                       offrange[1] = (min - 1).to_shwi ();
 286                     }
 287                   else
 288                     {
 289                       gimple *stmt = SSA_NAME_DEF_STMT (offset);
 290                       if (is_gimple_assign (stmt)
 291                           && gimple_assign_rhs_code (stmt) == NOP_EXPR)
 292                         {
 293                           /* Use the bounds of the type of the NOP_EXPR operand
 294                              even if it's signed.  The result doesn't trigger
 295                              warnings but makes their output more readable.  */
 296                           tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
 297                           offrange[0] = wi::to_offset (TYPE_MIN_VALUE (type));
 298                           offrange[1] = wi::to_offset (TYPE_MAX_VALUE (type));
 299                         }
 300                       else
 301                         offrange[1] = maxobjsize;
 302                     }
 303                 }
 304               else
 305                 offrange[1] = maxobjsize;
 306             }
 307         }
 308     }
 309
 310   if (TREE_CODE (expr) == ADDR_EXPR)
 311     {
 312       HOST_WIDE_INT off;
 313       tree oper = TREE_OPERAND (expr, 0);
 314
 315       /* Determine the base object or pointer of the reference
 316          and its constant offset from the beginning of the base.  */
 317       base = get_addr_base_and_unit_offset (oper, &off);
 318
 319       if (base)
 320         {
 321           offrange[0] += off;
 322           offrange[1] += off;
 323
 324           /* Stash the reference for offset validation.  */
 325           ref = oper;
 326
 327           /* Also stash the constant offset for offset validation.  */
 328           tree_code code = TREE_CODE (oper);
 329           if (code == COMPONENT_REF)
 330             {
 331               tree field = TREE_OPERAND (ref, 1);
 332               tree fldoff = DECL_FIELD_OFFSET (field);
 333               if (TREE_CODE (fldoff) == INTEGER_CST)
 334                 refoff = off + wi::to_offset (fldoff);
 335             }
 336         }
 337       else
 338         {
 339           size = NULL_TREE;
 340           base = get_base_address (TREE_OPERAND (expr, 0));
 341         }
 342     }
 343
 344   if (!base)
 345     base = build2 (MEM_REF, char_type_node, expr, null_pointer_node);
 346
 347   if (TREE_CODE (base) == MEM_REF)
 348     {
 349       offset_int off = mem_ref_offset (base);
 350       refoff += off;
 351       offrange[0] += off;
 352       offrange[1] += off;
 353       base = TREE_OPERAND (base, 0);
 354     }
 355
 356   if (TREE_CODE (base) == SSA_NAME)
 357     if (gimple *stmt = SSA_NAME_DEF_STMT (base))
 358       {
 359         enum gimple_code code = gimple_code (stmt);
 360         if (code == GIMPLE_ASSIGN)
 361           if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
 362             {
 363               base = gimple_assign_rhs1 (stmt);
 364
 365               tree offset = gimple_assign_rhs2 (stmt);
 366               if (TREE_CODE (offset) == INTEGER_CST)
 367                 {
 368                   offset_int off = int_cst_value (offset);
 369                   refoff += off;
 370                   offrange[0] += off;
 371                   offrange[1] += off;
 372                 }
 373             }
 374
 375         if (TREE_CODE (base) == SSA_NAME && SSA_NAME_VAR (base))
 376           base = SSA_NAME_VAR (base);
 377       }
 378
 379   if (size)
 380     {
 381       tree range[2];
 382       /* Determine the size range, allowing for the result to be [0, 0]
 383          for SIZE in the anti-range ~[0, N] where N >= PTRDIFF_MAX.  */
 384       get_size_range (size, range, true);
 385       sizrange[0] = wi::to_offset (range[0]);
 386       sizrange[1] = wi::to_offset (range[1]);
 387       /* get_size_range returns SIZE_MAX for the maximum size.
 388          Constrain it to the real maximum of PTRDIFF_MAX.  */
 389       if (sizrange[1] > maxobjsize)
 390         sizrange[1] = maxobjsize;
 391     }
 392   else
 393     sizrange[1] = maxobjsize;
 394 }
 395
 396 /* Return error_mark_node if the signed offset exceeds the bounds
 397    of the address space (PTRDIFF_MAX).  Otherwise, return either
 398    BASE or REF when the offset exceeds the bounds of the BASE or
 399    REF object, and set OOBOFF to the past-the-end offset formed
 400    by the reference, including its size.  When STRICT is non-zero
 401    use REF size, when available, otherwise use BASE size.  When
 402    STRICT is greater than 1, use the size of the last array member
 403    as the bound, otherwise treat such a member as a flexible array
 404    member.  Return NULL when the offset is in bounds.  */
 405
 406 tree
 407 builtin_memref::offset_out_of_bounds (int strict, offset_int ooboff[2]) const
 408 {
 409   const offset_int maxobjsize = tree_to_shwi (max_object_size ());
 410
 411   /* A temporary, possibly adjusted, copy of the offset range.  */
 412   offset_int offrng[2] = { offrange[0], offrange[1] };
 413
 414   if (DECL_P (base) && TREE_CODE (TREE_TYPE (base)) == ARRAY_TYPE)
 415     {
 416       /* Check for offset in an anti-range with a negative lower bound.
 417          For such a range, consider only the non-negative subrange.  */
 418       if (offrng[1] < offrng[0] && offrng[1] < 0)
 419         offrng[1] = maxobjsize;
 420     }
 421
 422   /* Conservative offset of the last byte of the referenced object.  */
 423   offset_int endoff;
 424
 425   /* The bounds need not be ordered.  Set HIB to use as the index
 426      of the larger of the bounds and LOB as the opposite.  */
 427   bool hib = wi::les_p (offrng[0], offrng[1]);
 428   bool lob = !hib;
 429
 430   if (basesize < 0)
 431     {
 432       endoff = offrng[lob] + sizrange[0];
 433
 434       /* For a reference through a pointer to an object of unknown size
 435          all initial offsets are considered valid, positive as well as
 436          negative, since the pointer itself can point past the beginning
 437          of the object.  However, the sum of the lower bound of the offset
 438          and that of the size must be less than or equal than PTRDIFF_MAX.  */
 439       if (endoff > maxobjsize)
 440         return error_mark_node;
 441
 442       return NULL_TREE;
 443     }
 444
 445   /* A reference to an object of known size must be within the bounds
 446      of the base object.  */
 447   if (offrng[hib] < 0 || offrng[lob] > basesize)
 448     return base;
 449
 450   /* The extent of the reference must also be within the bounds of
 451      the base object (if known) or the maximum object size otherwise.  */
 452   endoff = wi::smax (offrng[lob], 0) + sizrange[0];
 453   if (endoff > maxobjsize)
 454     return error_mark_node;
 455
 456   offset_int size = basesize;
 457   tree obj = base;
 458
 459   if (strict
 460       && DECL_P (obj)
 461       && ref
 462       && refoff >= 0
 463       && TREE_CODE (ref) == COMPONENT_REF
 464       && (strict > 1
 465           || !array_at_struct_end_p (ref)))
 466     {
 467       /* If the reference is to a member subobject, the offset must
 468          be within the bounds of the subobject.  */
 469       tree field = TREE_OPERAND (ref, 1);
 470       tree type = TREE_TYPE (field);
 471       if (tree sz = TYPE_SIZE_UNIT (type))
 472         if (TREE_CODE (sz) == INTEGER_CST)
 473           {
 474             size = refoff + wi::to_offset (sz);
 475             obj = ref;
 476           }
 477     }
 478
 479   if (endoff <= size)
 480     return NULL_TREE;
 481
 482   /* Set the out-of-bounds offset range to be one greater than
 483      that delimited by the reference including its size.  */
 484   ooboff[lob] = size + 1;
 485
 486   if (endoff > ooboff[lob])
 487     ooboff[hib] = endoff;
 488   else
 489     ooboff[hib] = wi::smax (offrng[lob], 0) + sizrange[1];
 490
 491   return obj;
 492 }
 493
 494 /* Create an association between the memory references DST and SRC
 495    for access by a call EXPR to a memory or string built-in funtion.  */
 496
 497 builtin_access::builtin_access (gcall *call, builtin_memref &dst,
 498                                 builtin_memref &src)
 499 : dstref (&dst), srcref (&src), sizrange (), ovloff (), ovlsiz (),
 500   dstoff (), srcoff (), dstsiz (), srcsiz ()
 501 {
 502   /* Zero out since the offset_int ctors invoked above are no-op.  */
 503   dstoff[0] = dstoff[1] = 0;
 504   srcoff[0] = srcoff[1] = 0;
 505   dstsiz[0] = dstsiz[1] = 0;
 506   srcsiz[0] = srcsiz[1] = 0;
 507
 508   /* Object Size Type to use to determine the size of the destination
 509      and source objects.  Overridden below for raw memory functions.  */
 510   int ostype = 1;
 511
 512   /* True when the size of one reference depends on the offset of
 513      itself or the other.  */
 514   bool depends_p = true;
 515
 516   /* True when the size of the destination reference DSTREF has been
 517      determined from SRCREF and so needs to be adjusted by the latter's
 518      offset.  Only meaningful for bounded string functions like strncpy.  */
 519   bool dstadjust_p = false;
 520
 521   /* The size argument number (depends on the built-in).  */
 522   unsigned sizeargno = 2;
 523   if (gimple_call_with_bounds_p (call))
 524     sizeargno += 2;
 525
 526   tree func = gimple_call_fndecl (call);
 527   switch (DECL_FUNCTION_CODE (func))
 528     {
 529     case BUILT_IN_MEMCPY:
 530     case BUILT_IN_MEMCPY_CHK:
 531     case BUILT_IN_MEMCPY_CHKP:
 532     case BUILT_IN_MEMCPY_CHK_CHKP:
 533     case BUILT_IN_MEMPCPY:
 534     case BUILT_IN_MEMPCPY_CHK:
 535     case BUILT_IN_MEMPCPY_CHKP:
 536     case BUILT_IN_MEMPCPY_CHK_CHKP:
 537       ostype = 0;
 538       depends_p = false;
 539       detect_overlap = &builtin_access::generic_overlap;
 540       break;
 541
 542     case BUILT_IN_MEMMOVE:
 543     case BUILT_IN_MEMMOVE_CHK:
 544     case BUILT_IN_MEMMOVE_CHKP:
 545     case BUILT_IN_MEMMOVE_CHK_CHKP:
 546       /* For memmove there is never any overlap to check for.  */
 547       ostype = 0;
 548       depends_p = false;
 549       detect_overlap = &builtin_access::no_overlap;
 550       break;
 551
 552     case BUILT_IN_STPNCPY:
 553     case BUILT_IN_STPNCPY_CHK:
 554     case BUILT_IN_STRNCPY:
 555     case BUILT_IN_STRNCPY_CHK:
 556       dstref->strbounded_p = true;
 557       detect_overlap = &builtin_access::strcpy_overlap;
 558       break;
 559
 560     case BUILT_IN_STPCPY:
 561     case BUILT_IN_STPCPY_CHK:
 562     case BUILT_IN_STPCPY_CHKP:
 563     case BUILT_IN_STPCPY_CHK_CHKP:
 564     case BUILT_IN_STRCPY:
 565     case BUILT_IN_STRCPY_CHK:
 566     case BUILT_IN_STRCPY_CHKP:
 567     case BUILT_IN_STRCPY_CHK_CHKP:
 568       detect_overlap = &builtin_access::strcpy_overlap;
 569       break;
 570
 571     case BUILT_IN_STRCAT:
 572     case BUILT_IN_STRCAT_CHK:
 573     case BUILT_IN_STRCAT_CHKP:
 574     case BUILT_IN_STRCAT_CHK_CHKP:
 575       detect_overlap = &builtin_access::strcat_overlap;
 576       break;
 577
 578     case BUILT_IN_STRNCAT:
 579     case BUILT_IN_STRNCAT_CHK:
 580       dstref->strbounded_p = true;
 581       srcref->strbounded_p = true;
 582       detect_overlap = &builtin_access::strcat_overlap;
 583       break;
 584
 585     default:
 586       /* Handle other string functions here whose access may need
 587          to be validated for in-bounds offsets and non-overlapping
 588          copies.  (Not all _chkp functions have BUILT_IN_XXX_CHKP
 589          macros so they need to be handled here.)  */
 590       return;
 591     }
 592
 593   const offset_int maxobjsize = tree_to_shwi (max_object_size ());
 594
 595   /* Try to determine the size of the base object.  compute_objsize
 596      expects a pointer so create one if BASE is a non-pointer object.  */
 597   tree addr;
 598   if (dst.basesize < 0)
 599     {
 600       addr = dst.base;
 601       if (!POINTER_TYPE_P (TREE_TYPE (addr)))
 602         addr = build1 (ADDR_EXPR, (TREE_TYPE (addr)), addr);
 603
 604       if (tree dstsize = compute_objsize (addr, ostype))
 605         dst.basesize = wi::to_offset (dstsize);
 606       else if (POINTER_TYPE_P (TREE_TYPE (addr)))
 607         dst.basesize = HOST_WIDE_INT_MIN;
 608       else
 609         dst.basesize = maxobjsize;
 610     }
 611
 612   if (src.basesize < 0)
 613     {
 614       addr = src.base;
 615       if (!POINTER_TYPE_P (TREE_TYPE (addr)))
 616         addr = build1 (ADDR_EXPR, (TREE_TYPE (addr)), addr);
 617
 618       if (tree srcsize = compute_objsize (addr, ostype))
 619         src.basesize = wi::to_offset (srcsize);
 620       else if (POINTER_TYPE_P (TREE_TYPE (addr)))
 621         src.basesize = HOST_WIDE_INT_MIN;
 622       else
 623         src.basesize = maxobjsize;
 624     }
 625
 626   /* If there is no dependency between the references or the base
 627      objects of the two references aren't the same there's nothing
 628      else to do.  */
 629   if (depends_p && dstref->base != srcref->base)
 630     return;
 631
 632   /* ...otherwise, make adjustments for references to the same object
 633      by string built-in functions to reflect the constraints imposed
 634      by the function.  */
 635
 636   /* For bounded string functions determine the range of the bound
 637      on the access.  For others, the range stays unbounded.  */
 638   offset_int bounds[2] = { maxobjsize, maxobjsize };
 639   if (dstref->strbounded_p)
 640     {
 641       tree size = gimple_call_arg (call, sizeargno);
 642       tree range[2];
 643       if (get_size_range (size, range, true))
 644         {
 645           bounds[0] = wi::to_offset (range[0]);
 646           bounds[1] = wi::to_offset (range[1]);
 647         }
 648
 649       /* If both references' size ranges are indeterminate use the last
 650          (size) argument from the function call as a substitute.  This
 651          may only be necessary for strncpy (but not for memcpy where
 652          the size range would have been already determined this way).  */
 653       if (dstref->sizrange[0] == 0 && dstref->sizrange[1] == maxobjsize
 654           && srcref->sizrange[0] == 0 && srcref->sizrange[1] == maxobjsize)
 655         {
 656           dstref->sizrange[0] = bounds[0];
 657           dstref->sizrange[1] = bounds[1];
 658         }
 659     }
 660
 661   /* The size range of one reference involving the same base object
 662      can be determined from the size range of the other reference.
 663      This makes it possible to compute accurate offsets for warnings
 664      involving functions like strcpy where the length of just one of
 665      the two arguments is known (determined by tree-ssa-strlen).  */
 666   if (dstref->sizrange[0] == 0 && dstref->sizrange[1] == maxobjsize)
 667     {
 668       /* When the destination size is unknown set it to the size of
 669          the source.  */
 670       dstref->sizrange[0] = srcref->sizrange[0];
 671       dstref->sizrange[1] = srcref->sizrange[1];
 672     }
 673   else if (srcref->sizrange[0] == 0 && srcref->sizrange[1] == maxobjsize)
 674     {
 675       /* When the source size is unknown set it to the size of
 676          the destination.  */
 677       srcref->sizrange[0] = dstref->sizrange[0];
 678       srcref->sizrange[1] = dstref->sizrange[1];
 679
 680       if (depends_p)
 681         {
 682           if (dstref->strbounded_p)
 683             {
 684               /* Read access by strncpy is bounded.  */
 685               if (bounds[0] < srcref->sizrange[0])
 686                 srcref->sizrange[0] = bounds[0];
 687               if (bounds[1] < srcref->sizrange[1])
 688                 srcref->sizrange[1] = bounds[1];
 689             }
 690
 691           /* For string functions, adjust the size range of the source
 692              reference by the inverse boundaries of the offset (because
 693              the higher  the offset into the string the shorter its
 694              length).  */
 695           if (srcref->offrange[1] < srcref->sizrange[0])
 696             srcref->sizrange[0] -= srcref->offrange[1];
 697           else
 698             srcref->sizrange[0] = 0;
 699
 700           if (srcref->offrange[0] > 0)
 701             {
 702               if (srcref->offrange[0] < srcref->sizrange[1])
 703                 srcref->sizrange[1] -= srcref->offrange[0];
 704               else
 705                 srcref->sizrange[1] = 0;
 706             }
 707
 708           dstadjust_p = true;
 709         }
 710     }
 711
 712   if (detect_overlap == &builtin_access::generic_overlap)
 713     {
 714       if (dstref->strbounded_p)
 715         {
 716           dstref->sizrange[0] = bounds[0];
 717           dstref->sizrange[1] = bounds[1];
 718
 719           if (dstref->sizrange[0] < srcref->sizrange[0])
 720             srcref->sizrange[0] = dstref->sizrange[0];
 721
 722           if (dstref->sizrange[1] < srcref->sizrange[1])
 723             srcref->sizrange[1] = dstref->sizrange[1];
 724         }
 725     }
 726   else if (detect_overlap == &builtin_access::strcpy_overlap)
 727     {
 728       if (!dstref->strbounded_p)
 729         {
 730           /* For strcpy, adjust the destination size range to match that
 731              of the source computed above.  */
 732           if (depends_p && dstadjust_p)
 733             {
 734               dstref->sizrange[0] = srcref->sizrange[0];
 735               dstref->sizrange[1] = srcref->sizrange[1];
 736             }
 737         }
 738     }
 739
 740   if (dstref->strbounded_p)
 741     {
 742       /* For strncpy, adjust the destination size range to match that
 743          of the source computed above.  */
 744       dstref->sizrange[0] = bounds[0];
 745       dstref->sizrange[1] = bounds[1];
 746
 747       if (bounds[0] < srcref->sizrange[0])
 748         srcref->sizrange[0] = bounds[0];
 749
 750       if (bounds[1] < srcref->sizrange[1])
 751         srcref->sizrange[1] = bounds[1];
 752     }
 753 }
 754
 755 offset_int
 756 builtin_access::overlap_size (const offset_int a[2], const offset_int b[2],
 757                               offset_int *off)
 758 {
 759   const offset_int *p = a;
 760   const offset_int *q = b;
 761
 762   /* Point P at the bigger of the two ranges and Q at the smaller.  */
 763   if (wi::lts_p (a[1] - a[0], b[1] - b[0]))
 764     {
 765       p = b;
 766       q = a;
 767     }
 768
 769   if (p[0] < q[0])
 770     {
 771       if (p[1] < q[0])
 772         return 0;
 773
 774       *off = q[0];
 775       return wi::smin (p[1], q[1]) - q[0];
 776     }
 777
 778   if (q[1] < p[0])
 779     return 0;
 780
 781   off[0] = p[0];
 782   return q[1] - p[0];
 783 }
 784
 785 /* Return true if the bounded mempry (memcpy amd similar) or string function
 786    access (strncpy and similar) ACS overlaps.  */
 787
 788 bool
 789 builtin_access::generic_overlap ()
 790 {
 791   builtin_access &acs = *this;
 792   const builtin_memref *dstref = acs.dstref;
 793   const builtin_memref *srcref = acs.srcref;
 794
 795   gcc_assert (dstref->base == srcref->base);
 796
 797   const offset_int maxobjsize = tree_to_shwi (max_object_size ());
 798
 799   offset_int maxsize = dstref->basesize < 0 ? maxobjsize : dstref->basesize;
 800   gcc_assert (maxsize <= maxobjsize);
 801
 802   /* Adjust the larger bounds of the offsets (which may be the first
 803      element if the lower bound is larger than the upper bound) to
 804      make them valid for the smallest access (if possible) but no smaller
 805      than the smaller bounds.  */
 806   gcc_assert (wi::les_p (acs.dstoff[0], acs.dstoff[1]));
 807
 808   if (maxsize < acs.dstoff[1] + acs.dstsiz[0])
 809     acs.dstoff[1] = maxsize - acs.dstsiz[0];
 810   if (acs.dstoff[1] < acs.dstoff[0])
 811     acs.dstoff[1] = acs.dstoff[0];
 812
 813   gcc_assert (wi::les_p (acs.srcoff[0], acs.srcoff[1]));
 814
 815   if (maxsize < acs.srcoff[1] + acs.srcsiz[0])
 816     acs.srcoff[1] = maxsize - acs.srcsiz[0];
 817   if (acs.srcoff[1] < acs.srcoff[0])
 818     acs.srcoff[1] = acs.srcoff[0];
 819
 820   /* Determine the minimum and maximum space for the access given
 821      the offsets.  */
 822   offset_int space[2];
 823   space[0] = wi::abs (acs.dstoff[0] - acs.srcoff[0]);
 824   space[1] = space[0];
 825
 826   offset_int d = wi::abs (acs.dstoff[0] - acs.srcoff[1]);
 827   if (acs.srcsiz[0] > 0)
 828     {
 829       if (d < space[0])
 830         space[0] = d;
 831
 832       if (space[1] < d)
 833         space[1] = d;
 834     }
 835   else
 836     space[1] = acs.dstsiz[1];
 837
 838   d = wi::abs (acs.dstoff[1] - acs.srcoff[0]);
 839   if (d < space[0])
 840     space[0] = d;
 841
 842   if (space[1] < d)
 843     space[1] = d;
 844
 845   /* Treat raw memory functions both of whose references are bounded
 846      as special and permit uncertain overlaps to go undetected.  For
 847      all kinds of constant offset and constant size accesses, if
 848      overlap isn't certain it is not possible.  */
 849   bool overlap_possible = space[0] < acs.dstsiz[1];
 850   if (!overlap_possible)
 851     return false;
 852
 853   bool overlap_certain = space[1] < acs.dstsiz[0];
 854
 855   /* True when the size of one reference depends on the offset of
 856      the other.  */
 857   bool depends_p = detect_overlap != &builtin_access::generic_overlap;
 858
 859   if (!overlap_certain
 860       && !dstref->strbounded_p
 861       && !depends_p)
 862     return false;
 863
 864   /* True for stpcpy and strcpy.  */
 865   bool stxcpy_p = (!dstref->strbounded_p
 866                    && detect_overlap == &builtin_access::strcpy_overlap);
 867
 868   if (dstref->refoff >= 0
 869       && srcref->refoff >= 0
 870       && dstref->refoff != srcref->refoff
 871       && (stxcpy_p || dstref->strbounded_p || srcref->strbounded_p))
 872     return false;
 873
 874   offset_int siz[2] = { maxobjsize + 1, 0 };
 875
 876   ovloff[0] = HOST_WIDE_INT_MAX;
 877   ovloff[1] = HOST_WIDE_INT_MIN;
 878
 879   /* Adjustment to the lower bound of the offset of the overlap to
 880      account for a subset of unbounded string calls where the size
 881      of the destination string depends on the length of the source
 882      which in turn depends on the offset into it.  */
 883   bool sub1;
 884
 885   if (stxcpy_p)
 886     {
 887       sub1 = acs.dstoff[0] <= acs.srcoff[0];
 888
 889       /* Iterate over the extreme locations (on the horizontal axis formed
 890          by their offsets) and sizes of two regions and find their smallest
 891          and largest overlap and the corresponding offsets.  */
 892       for (unsigned i = 0; i != 2; ++i)
 893         {
 894           const offset_int a[2] = {
 895             acs.dstoff[i], acs.dstoff[i] + acs.dstsiz[!i]
 896           };
 897
 898           const offset_int b[2] = {
 899             acs.srcoff[i], acs.srcoff[i] + acs.srcsiz[!i]
 900           };
 901
 902           offset_int off;
 903           offset_int sz = overlap_size (a, b, &off);
 904           if (sz < siz[0])
 905             siz[0] = sz;
 906
 907           if (siz[1] <= sz)
 908             siz[1] = sz;
 909
 910           if (sz != 0)
 911             {
 912               if (wi::lts_p (off, ovloff[0]))
 913                 ovloff[0] = off.to_shwi ();
 914               if (wi::lts_p (ovloff[1], off))
 915                 ovloff[1] = off.to_shwi ();
 916             }
 917         }
 918     }
 919   else
 920     {
 921       sub1 = !depends_p;
 922
 923       /* Iterate over the extreme locations (on the horizontal axis
 924          formed by their offsets) and sizes of two regions and find
 925          their smallest and largest overlap and the corresponding
 926          offsets.  */
 927
 928       for (unsigned io = 0; io != 2; ++io)
 929         for (unsigned is = 0; is != 2; ++is)
 930           {
 931             const offset_int a[2] = {
 932               acs.dstoff[io], acs.dstoff[io] + acs.dstsiz[is]
 933             };
 934
 935             for (unsigned jo = 0; jo != 2; ++jo)
 936               for (unsigned js = 0; js != 2; ++js)
 937                 {
 938                   if (depends_p)
 939                     {
 940                       /* For st{p,r}ncpy the size of the source sequence
 941                          depends on the offset into it.  */
 942                       if (js)
 943                         break;
 944                       js = !jo;
 945                     }
 946
 947                   const offset_int b[2] = {
 948                     acs.srcoff[jo], acs.srcoff[jo] + acs.srcsiz[js]
 949                   };
 950
 951                   offset_int off;
 952                   offset_int sz = overlap_size (a, b, &off);
 953                   if (sz < siz[0])
 954                     siz[0] = sz;
 955
 956                   if (siz[1] <= sz)
 957                     siz[1] = sz;
 958
 959                   if (sz != 0)
 960                     {
 961                       if (wi::lts_p (off, ovloff[0]))
 962                         ovloff[0] = off.to_shwi ();
 963                       if (wi::lts_p (ovloff[1], off))
 964                         ovloff[1] = off.to_shwi ();
 965                     }
 966                 }
 967           }
 968     }
 969
 970   ovlsiz[0] = siz[0].to_shwi ();
 971   ovlsiz[1] = siz[1].to_shwi ();
 972
 973   if (ovlsiz[0] == 0 && ovlsiz[1] > 1)
 974     ovloff[0] = ovloff[1] + ovlsiz[1] - 1 - sub1;
 975
 976   return true;
 977 }
 978
 979 /* Return true if the strcat-like access overlaps.  */
 980
 981 bool
 982 builtin_access::strcat_overlap ()
 983 {
 984   builtin_access &acs = *this;
 985   const builtin_memref *dstref = acs.dstref;
 986   const builtin_memref *srcref = acs.srcref;
 987
 988   gcc_assert (dstref->base == srcref->base);
 989
 990   const offset_int maxobjsize = tree_to_shwi (max_object_size ());
 991
 992   gcc_assert (dstref->base && dstref->base == srcref->base);
 993
 994   /* Adjust for strcat-like accesses.  */
 995
 996   /* As a special case for strcat, set the DSTREF offsets to the length
 997      of the source string since the function starts writing at the first
 998      nul, and set the size to 1 for the length of the nul.  */
 999   acs.dstoff[0] += acs.dstsiz[0];
1000   acs.dstoff[1] += acs.dstsiz[1];
1001
1002   bool strfunc_unknown_args = acs.dstsiz[0] == 0 && acs.dstsiz[1] != 0;
1003
1004   /* The lower bound is zero when the size is unknown because then
1005      overlap is not certain.  */
1006   acs.dstsiz[0] = strfunc_unknown_args ? 0 : 1;
1007   acs.dstsiz[1] = 1;
1008
1009   offset_int maxsize = dstref->basesize < 0 ? maxobjsize : dstref->basesize;
1010   gcc_assert (maxsize <= maxobjsize);
1011
1012   /* For references to the same base object, determine if there's a pair
1013      of valid offsets into the two references such that access between
1014      them doesn't overlap.  Adjust both upper bounds to be valid for
1015      the smaller size (i.e., at most MAXSIZE - SIZE).  */
1016
1017   if (maxsize < acs.dstoff[1] + acs.dstsiz[0])
1018     acs.dstoff[1] = maxsize - acs.dstsiz[0];
1019
1020   if (maxsize < acs.srcoff[1] + acs.srcsiz[0])
1021     acs.srcoff[1] = maxsize - acs.srcsiz[0];
1022
1023   /* Check to see if there's enough space for both accesses without
1024      overlap.  Determine the optimistic (maximum) amount of available
1025      space.  */
1026   offset_int space;
1027   if (acs.dstoff[0] <= acs.srcoff[0])
1028     {
1029       if (acs.dstoff[1] < acs.srcoff[1])
1030         space = acs.srcoff[1] + acs.srcsiz[0] - acs.dstoff[0];
1031       else
1032         space = acs.dstoff[1] + acs.dstsiz[0] - acs.srcoff[0];
1033     }
1034   else
1035     space = acs.dstoff[1] + acs.dstsiz[0] - acs.srcoff[0];
1036
1037   /* Overlap is certain if the distance between the farthest offsets
1038      of the opposite accesses is less than the sum of the lower bounds
1039      of the sizes of the two accesses.  */
1040   bool overlap_certain = space < acs.dstsiz[0] + acs.srcsiz[0];
1041
1042   /* For a constant-offset, constant size access, consider the largest
1043      distance between the offset bounds and the lower bound of the access
1044      size.  If the overlap isn't certain return success.  */
1045   if (!overlap_certain
1046       && acs.dstoff[0] == acs.dstoff[1]
1047       && acs.srcoff[0] == acs.srcoff[1]
1048       && acs.dstsiz[0] == acs.dstsiz[1]
1049       && acs.srcsiz[0] == acs.srcsiz[1])
1050     return false;
1051
1052   /* Overlap is not certain but may be possible.  */
1053
1054   offset_int access_min = acs.dstsiz[0] + acs.srcsiz[0];
1055
1056   /* Determine the conservative (minimum) amount of space.  */
1057   space = wi::abs (acs.dstoff[0] - acs.srcoff[0]);
1058   offset_int d = wi::abs (acs.dstoff[0] - acs.srcoff[1]);
1059   if (d < space)
1060     space = d;
1061   d = wi::abs (acs.dstoff[1] - acs.srcoff[0]);
1062   if (d < space)
1063     space = d;
1064
1065   /* For a strict test (used for strcpy and similar with unknown or
1066      variable bounds or sizes), consider the smallest distance between
1067      the offset bounds and either the upper bound of the access size
1068      if known, or the lower bound otherwise.  */
1069   if (access_min <= space && (access_min != 0 || !strfunc_unknown_args))
1070     return false;
1071
1072   /* When strcat overlap is certain it is always a single byte:
1073      the terminatinn NUL, regardless of offsets and sizes.  When
1074      overlap is only possible its range is [0, 1].  */
1075   acs.ovlsiz[0] = dstref->sizrange[0] == dstref->sizrange[1] ? 1 : 0;
1076   acs.ovlsiz[1] = 1;
1077   acs.ovloff[0] = (dstref->sizrange[0] + dstref->offrange[0]).to_shwi ();
1078   acs.ovloff[1] = (dstref->sizrange[1] + dstref->offrange[1]).to_shwi ();
1079
1080   acs.sizrange[0] = wi::smax (acs.dstsiz[0], srcref->sizrange[0]).to_shwi ();
1081   acs.sizrange[1] = wi::smax (acs.dstsiz[1], srcref->sizrange[1]).to_shwi ();
1082   return true;
1083 }
1084
1085 /* Return true if the strcpy-like access overlaps.  */
1086
1087 bool
1088 builtin_access::strcpy_overlap ()
1089 {
1090   return generic_overlap ();
1091 }
1092
1093
1094 /* Return true if DSTREF and SRCREF describe accesses that either overlap
1095    one another or that, in order not to overlap, would imply that the size
1096    of the referenced object(s) exceeds the maximum size of an object.  Set
1097    Otherwise, if DSTREF and SRCREF do not definitely overlap (even though
1098    they may overlap in a way that's not apparent from the available data),
1099    return false.  */
1100
1101 bool
1102 builtin_access::overlap ()
1103 {
1104   builtin_access &acs = *this;
1105
1106   const offset_int maxobjsize = tree_to_shwi (max_object_size ());
1107
1108   acs.sizrange[0] = wi::smax (dstref->sizrange[0],
1109                               srcref->sizrange[0]).to_shwi ();
1110   acs.sizrange[1] = wi::smax (dstref->sizrange[1],
1111                               srcref->sizrange[1]).to_shwi ();
1112
1113   /* Check to see if the two references refer to regions that are
1114      too large not to overlap in the address space (whose maximum
1115      size is PTRDIFF_MAX).  */
1116   offset_int size = dstref->sizrange[0] + srcref->sizrange[0];
1117   if (maxobjsize < size)
1118     {
1119       acs.ovloff[0] = (maxobjsize - dstref->sizrange[0]).to_shwi ();
1120       acs.ovlsiz[0] = (size - maxobjsize).to_shwi ();
1121       return true;
1122     }
1123
1124   /* If both base objects aren't known return the maximum possible
1125      offset that would make them not overlap.  */
1126   if (!dstref->base || !srcref->base)
1127     return false;
1128
1129   /* If the base object is an array adjust the lower bound of the offset
1130      to be non-negative.  */
1131   if (dstref->base
1132       && TREE_CODE (TREE_TYPE (dstref->base)) == ARRAY_TYPE)
1133     acs.dstoff[0] = wi::smax (dstref->offrange[0], 0);
1134   else
1135     acs.dstoff[0] = dstref->offrange[0];
1136
1137   acs.dstoff[1] = dstref->offrange[1];
1138
1139   if (srcref->base
1140       && TREE_CODE (TREE_TYPE (srcref->base)) == ARRAY_TYPE)
1141     acs.srcoff[0] = wi::smax (srcref->offrange[0], 0);
1142   else
1143     acs.srcoff[0] = srcref->offrange[0];
1144
1145   acs.srcoff[1] = srcref->offrange[1];
1146
1147   /* When the lower bound of the offset is less that the upper bound
1148      disregard it and use the inverse of the maximum object size
1149      instead.  The upper bound is the result of a negative offset
1150      being represented as a large positive value.  */
1151   if (acs.dstoff[1] < acs.dstoff[0])
1152     acs.dstoff[0] = -maxobjsize;
1153
1154   /* Validate the offset and size of each reference on its own first.
1155      This is independent of whether or not the base objects are the
1156      same.  Normally, this would have already been detected and
1157      diagnosed by -Warray-bounds, unless it has been disabled.  */
1158   offset_int maxoff = acs.dstoff[0] + dstref->sizrange[0];
1159   if (maxobjsize < maxoff)
1160     {
1161       acs.ovlsiz[0] = (maxoff - maxobjsize).to_shwi ();
1162       acs.ovloff[0] = acs.dstoff[0].to_shwi () - acs.ovlsiz[0];
1163       return true;
1164     }
1165
1166   /* Repeat the same as above but for the source offsets.  */
1167   if (acs.srcoff[1] < acs.srcoff[0])
1168     acs.srcoff[0] = -maxobjsize;
1169
1170   maxoff = acs.srcoff[0] + srcref->sizrange[0];
1171   if (maxobjsize < maxoff)
1172     {
1173       acs.ovlsiz[0] = (maxoff - maxobjsize).to_shwi ();
1174       acs.ovlsiz[1] = (acs.srcoff[0] + srcref->sizrange[1]
1175                        - maxobjsize).to_shwi ();
1176       acs.ovloff[0] = acs.srcoff[0].to_shwi () - acs.ovlsiz[0];
1177       return true;
1178     }
1179
1180   if (dstref->base != srcref->base)
1181     return false;
1182
1183   acs.dstsiz[0] = dstref->sizrange[0];
1184   acs.dstsiz[1] = dstref->sizrange[1];
1185
1186   acs.srcsiz[0] = srcref->sizrange[0];
1187   acs.srcsiz[1] = srcref->sizrange[1];
1188
1189   /* Call the appropriate function to determine the overlap.  */
1190   if ((this->*detect_overlap) ())
1191     {
1192       sizrange[0] = wi::smax (acs.dstsiz[0], srcref->sizrange[0]).to_shwi ();
1193       sizrange[1] = wi::smax (acs.dstsiz[1], srcref->sizrange[1]).to_shwi ();
1194       return true;
1195     }
1196
1197   return false;
1198 }
1199
1200 /* Attempt to detect and diagnose an overlapping copy in a call expression
1201    EXPR involving an an access ACS to a built-in memory or string function.
1202    Return true when one has been detected, false otherwise.  */
1203
1204 static bool
1205 maybe_diag_overlap (location_t loc, gcall *call, builtin_access &acs)
1206 {
1207   if (!acs.overlap ())
1208     return false;
1209
1210   /* For convenience.  */
1211   const builtin_memref &dstref = *acs.dstref;
1212   const builtin_memref &srcref = *acs.srcref;
1213
1214   /* Determine the range of offsets and sizes of the overlap if it
1215      exists and issue diagnostics.  */
1216   HOST_WIDE_INT *ovloff = acs.ovloff;
1217   HOST_WIDE_INT *ovlsiz = acs.ovlsiz;
1218   HOST_WIDE_INT *sizrange = acs.sizrange;
1219
1220   tree func = gimple_call_fndecl (call);
1221
1222   /* To avoid a combinatorial explosion of diagnostics format the offsets
1223      or their ranges as strings and use them in the warning calls below.  */
1224   char offstr[3][64];
1225
1226   if (dstref.offrange[0] == dstref.offrange[1]
1227       || dstref.offrange[1] > HOST_WIDE_INT_MAX)
1228     sprintf (offstr[0], "%lli", (long long) dstref.offrange[0].to_shwi ());
1229   else
1230     sprintf (offstr[0], "[%lli, %lli]",
1231              (long long) dstref.offrange[0].to_shwi (),
1232              (long long) dstref.offrange[1].to_shwi ());
1233
1234   if (srcref.offrange[0] == srcref.offrange[1]
1235       || srcref.offrange[1] > HOST_WIDE_INT_MAX)
1236     sprintf (offstr[1], "%lli", (long long) srcref.offrange[0].to_shwi ());
1237   else
1238     sprintf (offstr[1], "[%lli, %lli]",
1239              (long long) srcref.offrange[0].to_shwi (),
1240              (long long) srcref.offrange[1].to_shwi ());
1241
1242   if (ovloff[0] == ovloff[1] || !ovloff[1])
1243     sprintf (offstr[2], "%lli", (long long) ovloff[0]);
1244   else
1245     sprintf (offstr[2], "[%lli, %lli]",
1246              (long long) ovloff[0], (long long) ovloff[1]);
1247
1248   const offset_int maxobjsize = tree_to_shwi (max_object_size ());
1249   bool must_overlap = ovlsiz[0] > 0;
1250
1251   if (ovlsiz[1] == 0)
1252     ovlsiz[1] = ovlsiz[0];
1253
1254   if (must_overlap)
1255     {
1256       /* Issue definitive "overlaps" diagnostic in this block.  */
1257
1258       if (sizrange[0] == sizrange[1])
1259         {
1260           if (ovlsiz[0] == ovlsiz[1])
1261             warning_at (loc, OPT_Wrestrict,
1262                         sizrange[0] == 1
1263                         ? (ovlsiz[0] == 1
1264                            ? G_("%G%qD accessing %wu byte at offsets %s "
1265                                 "and %s overlaps %wu byte at offset %s")
1266                            :  G_("%G%qD accessing %wu byte at offsets %s "
1267                                  "and %s overlaps %wu bytes at offset "
1268                                  "%s"))
1269                         : (ovlsiz[0] == 1
1270                            ? G_("%G%qD accessing %wu bytes at offsets %s "
1271                                 "and %s overlaps %wu byte at offset %s")
1272                            : G_("%G%qD accessing %wu bytes at offsets %s "
1273                                 "and %s overlaps %wu bytes at offset "
1274                                 "%s")),
1275                         call, func, sizrange[0],
1276                         offstr[0], offstr[1], ovlsiz[0], offstr[2]);
1277           else if (ovlsiz[1] >= 0 && ovlsiz[1] < maxobjsize.to_shwi ())
1278             warning_at (loc, OPT_Wrestrict,
1279                         sizrange[0] == 1
1280                         ? G_("%G%qD accessing %wu byte at offsets %s "
1281                              "and %s overlaps between %wu and %wu bytes "
1282                              "at offset %s")
1283                         : G_("%G%qD accessing %wu bytes at offsets %s "
1284                              "and %s overlaps between %wu and %wu bytes "
1285                              "at offset %s"),
1286                         call, func, sizrange[0],
1287                         offstr[0], offstr[1], ovlsiz[0], ovlsiz[1],
1288                         offstr[2]);
1289           else
1290             warning_at (loc, OPT_Wrestrict,
1291                         sizrange[0] == 1
1292                         ? G_("%G%qD accessing %wu byte at offsets %s and "
1293                              "%s overlaps %wu or more bytes at offset %s")
1294                         : G_("%G%qD accessing %wu bytes at offsets %s and "
1295                              "%s overlaps %wu or more bytes at offset %s"),
1296                         call, func, sizrange[0],
1297                         offstr[0], offstr[1], ovlsiz[0], offstr[2]);
1298           return true;
1299         }
1300
1301       if (sizrange[1] >= 0 && sizrange[1] < maxobjsize.to_shwi ())
1302         {
1303           if (ovlsiz[0] == ovlsiz[1])
1304             warning_at (loc, OPT_Wrestrict,
1305                         ovlsiz[0] == 1
1306                         ? G_("%G%qD accessing between %wu and %wu bytes "
1307                              "at offsets %s and %s overlaps %wu byte at "
1308                              "offset %s")
1309                         : G_("%G%qD accessing between %wu and %wu bytes "
1310                              "at offsets %s and %s overlaps %wu bytes "
1311                              "at offset %s"),
1312                         call, func, sizrange[0], sizrange[1],
1313                         offstr[0], offstr[1], ovlsiz[0], offstr[2]);
1314           else if (ovlsiz[1] >= 0 && ovlsiz[1] < maxobjsize.to_shwi ())
1315             warning_at (loc, OPT_Wrestrict,
1316                         "%G%qD accessing between %wu and %wu bytes at "
1317                         "offsets %s and %s overlaps between %wu and %wu "
1318                         "bytes at offset %s",
1319                         call, func, sizrange[0], sizrange[1],
1320                         offstr[0], offstr[1], ovlsiz[0], ovlsiz[1],
1321                         offstr[2]);
1322           else
1323             warning_at (loc, OPT_Wrestrict,
1324                         "%G%qD accessing between %wu and %wu bytes at "
1325                         "offsets %s and %s overlaps %wu or more bytes "
1326                         "at offset %s",
1327                         call, func, sizrange[0], sizrange[1],
1328                         offstr[0], offstr[1], ovlsiz[0], offstr[2]);
1329           return true;
1330         }
1331
1332       if (ovlsiz[0] != ovlsiz[1])
1333         ovlsiz[1] = maxobjsize.to_shwi ();
1334
1335       if (ovlsiz[0] == ovlsiz[1])
1336         warning_at (loc, OPT_Wrestrict,
1337                     ovlsiz[0] == 1
1338                     ? G_("%G%qD accessing %wu or more bytes at offsets "
1339                          "%s and %s overlaps %wu byte at offset %s")
1340                     :  G_("%G%qD accessing %wu or more bytes at offsets "
1341                           "%s and %s overlaps %wu bytes at offset %s"),
1342                     call, func, sizrange[0], offstr[0], offstr[1],
1343                     ovlsiz[0], offstr[2]);
1344       else if (ovlsiz[1] >= 0 && ovlsiz[1] < maxobjsize.to_shwi ())
1345         warning_at (loc, OPT_Wrestrict,
1346                     "%G%qD accessing %wu or more bytes at offsets %s "
1347                     "and %s overlaps between %wu and %wu bytes "
1348                     "at offset %s",
1349                     call, func, sizrange[0], offstr[0], offstr[1],
1350                     ovlsiz[0], ovlsiz[1], offstr[2]);
1351       else
1352         warning_at (loc, OPT_Wrestrict,
1353                     "%G%qD accessing %wu or more bytes at offsets %s "
1354                     "and %s overlaps %wu or more bytes at offset %s",
1355                     call, func, sizrange[0], offstr[0], offstr[1],
1356                     ovlsiz[0], offstr[2]);
1357       return true;
1358     }
1359
1360   /* Issue "may overlap" diagnostics below.  */
1361   gcc_assert (ovlsiz[0] == 0
1362               && ovlsiz[1] > 0
1363               && ovlsiz[1] <= maxobjsize.to_shwi ());
1364
1365   /* Use more concise wording when one of the offsets is unbounded
1366      to avoid confusing the user with large and mostly meaningless
1367      numbers.  */
1368   bool open_range = ((dstref.offrange[0] == -maxobjsize - 1
1369                       && dstref.offrange[1] == maxobjsize)
1370                      || (srcref.offrange[0] == -maxobjsize - 1
1371                          && srcref.offrange[1] == maxobjsize));
1372
1373   if (sizrange[0] == sizrange[1] || sizrange[1] == 1)
1374     {
1375       if (ovlsiz[1] == 1)
1376         {
1377           if (open_range)
1378             warning_at (loc, OPT_Wrestrict,
1379                         sizrange[1] == 1
1380                         ? G_("%G%qD accessing %wu byte may overlap "
1381                              "%wu byte")
1382                         : G_("%G%qD accessing %wu bytes may overlap "
1383                              "%wu byte"),
1384                         call, func, sizrange[1], ovlsiz[1]);
1385           else
1386             warning_at (loc, OPT_Wrestrict,
1387                         sizrange[1] == 1
1388                         ? G_("%G%qD accessing %wu byte at offsets %s "
1389                              "and %s may overlap %wu byte at offset %s")
1390                         : G_("%G%qD accessing %wu bytes at offsets %s "
1391                              "and %s may overlap %wu byte at offset %s"),
1392                         call, func, sizrange[1], offstr[0], offstr[1],
1393                         ovlsiz[1], offstr[2]);
1394           return true;
1395         }
1396
1397       if (open_range)
1398         warning_at (loc, OPT_Wrestrict,
1399                     sizrange[1] == 1
1400                     ? G_("%G%qD accessing %wu byte may overlap "
1401                          "up to %wu bytes")
1402                     : G_("%G%qD accessing %wu bytes may overlap "
1403                          "up to %wu bytes"),
1404                     call, func, sizrange[1], ovlsiz[1]);
1405       else
1406         warning_at (loc, OPT_Wrestrict,
1407                     sizrange[1] == 1
1408                     ? G_("%G%qD accessing %wu byte at offsets %s and "
1409                          "%s may overlap up to %wu bytes at offset %s")
1410                     : G_("%G%qD accessing %wu bytes at offsets %s and "
1411                          "%s may overlap up to %wu bytes at offset %s"),
1412                     call, func, sizrange[1], offstr[0], offstr[1],
1413                     ovlsiz[1], offstr[2]);
1414       return true;
1415     }
1416
1417   if (sizrange[1] >= 0 && sizrange[1] < maxobjsize.to_shwi ())
1418     {
1419       if (open_range)
1420         warning_at (loc, OPT_Wrestrict,
1421                     ovlsiz[1] == 1
1422                     ? G_("%G%qD accessing between %wu and %wu bytes "
1423                          "may overlap %wu byte")
1424                     : G_("%G%qD accessing between %wu and %wu bytes "
1425                          "may overlap up to %wu bytes"),
1426                     call, func, sizrange[0], sizrange[1], ovlsiz[1]);
1427       else
1428         warning_at (loc, OPT_Wrestrict,
1429                     ovlsiz[1] == 1
1430                     ? G_("%G%qD accessing between %wu and %wu bytes "
1431                          "at offsets %s and %s may overlap %wu byte "
1432                          "at offset %s")
1433                     : G_("%G%qD accessing between %wu and %wu bytes "
1434                          "at offsets %s and %s may overlap up to %wu "
1435                          "bytes at offset %s"),
1436                     call, func, sizrange[0], sizrange[1],
1437                     offstr[0], offstr[1], ovlsiz[1], offstr[2]);
1438       return true;
1439     }
1440
1441   warning_at (loc, OPT_Wrestrict,
1442               ovlsiz[1] == 1
1443               ? G_("%G%qD accessing %wu or more bytes at offsets %s "
1444                    "and %s may overlap %wu byte at offset %s")
1445               : G_("%G%qD accessing %wu or more bytes at offsets %s "
1446                    "and %s may overlap up to %wu bytes at offset %s"),
1447               call, func, sizrange[0], offstr[0], offstr[1],
1448               ovlsiz[1], offstr[2]);
1449
1450   return true;
1451 }
1452
1453 /* Validate REF offsets in an EXPRession passed as an argument to a CALL
1454    to a built-in function FUNC to make sure they are within the bounds
1455    of the referenced object if its size is known, or PTRDIFF_MAX otherwise.
1456    Both initial values of the offsets and their final value computed by
1457    the function by incrementing the initial value by the size are
1458    validated.  Return true if the offsets are not valid and a diagnostic
1459    has been issued.  */
1460
1461 static bool
1462 maybe_diag_offset_bounds (location_t loc, gcall *call, tree func, int strict,
1463                           tree expr, const builtin_memref &ref)
1464 {
1465   if (!warn_array_bounds)
1466     return false;
1467
1468   offset_int ooboff[] = { ref.offrange[0], ref.offrange[1] };
1469   tree oobref = ref.offset_out_of_bounds (strict, ooboff);
1470   if (!oobref)
1471     return false;
1472
1473   if (EXPR_HAS_LOCATION (expr))
1474     loc = EXPR_LOCATION (expr);
1475
1476   loc = expansion_point_location_if_in_system_header (loc);
1477
1478   tree type;
1479
1480   char rangestr[2][64];
1481   if (ooboff[0] == ooboff[1]
1482       || (ooboff[0] != ref.offrange[0]
1483           && ooboff[0].to_shwi () >= ooboff[1].to_shwi ()))
1484     sprintf (rangestr[0], "%lli", (long long) ooboff[0].to_shwi ());
1485   else
1486     sprintf (rangestr[0], "[%lli, %lli]",
1487              (long long) ooboff[0].to_shwi (),
1488              (long long) ooboff[1].to_shwi ());
1489
1490   if (oobref == error_mark_node)
1491     {
1492       if (ref.sizrange[0] == ref.sizrange[1])
1493         sprintf (rangestr[1], "%lli", (long long) ref.sizrange[0].to_shwi ());
1494       else
1495         sprintf (rangestr[1], "[%lli, %lli]",
1496                  (long long) ref.sizrange[0].to_shwi (),
1497                  (long long) ref.sizrange[1].to_shwi ());
1498
1499       if (DECL_P (ref.base)
1500           && TREE_CODE (type = TREE_TYPE (ref.base)) == ARRAY_TYPE)
1501         {
1502           if (warning_at (loc, OPT_Warray_bounds,
1503                           "%G%qD pointer overflow between offset %s "
1504                           "and size %s accessing array %qD with type %qT",
1505                           call, func, rangestr[0], rangestr[1], ref.base, type))
1506             inform (DECL_SOURCE_LOCATION (ref.base),
1507                     "array %qD declared here", ref.base);
1508           else
1509             warning_at (loc, OPT_Warray_bounds,
1510                         "%G%qD pointer overflow between offset %s "
1511                         "and size %s",
1512                         call, func, rangestr[0], rangestr[1]);
1513         }
1514       else
1515         warning_at (loc, OPT_Warray_bounds,
1516                     "%G%qD pointer overflow between offset %s "
1517                     "and size %s",
1518                     call, func, rangestr[0], rangestr[1]);
1519     }
1520   else if (oobref == ref.base)
1521     {
1522       const offset_int maxobjsize = tree_to_shwi (max_object_size ());
1523
1524       /* True when the offset formed by an access to the reference
1525          is out of bounds, rather than the initial offset wich is
1526          in bounds.  This implies access past the end.  */
1527       bool form = ooboff[0] != ref.offrange[0];
1528
1529       if (DECL_P (ref.base))
1530         {
1531           if ((ref.basesize < maxobjsize
1532                && warning_at (loc, OPT_Warray_bounds,
1533                               form
1534                               ? G_("%G%qD forming offset %s is out of "
1535                                    "the bounds [0, %wu] of object %qD with "
1536                                    "type %qT")
1537                               : G_("%G%qD offset %s is out of the bounds "
1538                                    "[0, %wu] of object %qD with type %qT"),
1539                               call, func, rangestr[0], ref.basesize.to_uhwi (),
1540                               ref.base, TREE_TYPE (ref.base)))
1541               || warning_at (loc, OPT_Warray_bounds,
1542                              form
1543                              ? G_("%G%qD forming offset %s is out of "
1544                                   "the bounds of object %qD with type %qT")
1545                              : G_("%G%qD offset %s is out of the bounds "
1546                                   "of object %qD with type %qT"),
1547                              call, func, rangestr[0],
1548                              ref.base, TREE_TYPE (ref.base)))
1549             inform (DECL_SOURCE_LOCATION (ref.base),
1550                     "%qD declared here", ref.base);
1551         }
1552       else if (ref.basesize < maxobjsize)
1553         warning_at (loc, OPT_Warray_bounds,
1554                     form
1555                     ? G_("%G%qD forming offset %s is out of the bounds "
1556                          "[0, %wu]")
1557                     : G_("%G%qD offset %s is out of the bounds [0, %wu]"),
1558                     call, func, rangestr[0], ref.basesize.to_uhwi ());
1559       else
1560         warning_at (loc, OPT_Warray_bounds,
1561                     form
1562                     ? G_("%G%qD forming offset %s is out of bounds")
1563                     : G_("%G%qD offset %s is out of bounds"),
1564                     call, func, rangestr[0]);
1565     }
1566   else if (TREE_CODE (ref.ref) == MEM_REF)
1567     {
1568       tree type = TREE_TYPE (TREE_OPERAND (ref.ref, 0));
1569       if (POINTER_TYPE_P (type))
1570         type = TREE_TYPE (type);
1571       type = TYPE_MAIN_VARIANT (type);
1572
1573       warning_at (loc, OPT_Warray_bounds,
1574                   "%G%qD offset %s from the object at %qE is out "
1575                   "of the bounds of %qT",
1576                   call, func, rangestr[0], ref.base, type);
1577     }
1578   else
1579     {
1580       type = TYPE_MAIN_VARIANT (TREE_TYPE (ref.ref));
1581
1582       warning_at (loc, OPT_Warray_bounds,
1583                 "%G%qD offset %s from the object at %qE is out "
1584                 "of the bounds of referenced subobject %qD with type %qT "
1585                 "at offset %wu",
1586                 call, func, rangestr[0], ref.base, TREE_OPERAND (ref.ref, 1),
1587                 type, ref.refoff.to_uhwi ());
1588     }
1589
1590   return true;
1591 }
1592
1593 /* Check a CALL statement for restrict-violations and issue warnings
1594    if/when appropriate.  */
1595
1596 void
1597 wrestrict_dom_walker::check_call (gcall *call)
1598 {
1599   /* Avoid checking the call if it has already been diagnosed for
1600      some reason.  */
1601   if (gimple_no_warning_p (call))
1602     return;
1603
1604   tree func = gimple_call_fndecl (call);
1605   if (!func || DECL_BUILT_IN_CLASS (func) != BUILT_IN_NORMAL)
1606     return;
1607
1608   bool with_bounds = gimple_call_with_bounds_p (call);
1609
1610   /* Argument number to extract from the call (depends on the built-in
1611      and its kind).  */
1612   unsigned dst_idx = -1;
1613   unsigned src_idx = -1;
1614   unsigned bnd_idx = -1;
1615
1616   /* Is this CALL to a string function (as opposed to one to a raw
1617      memory function).  */
1618   bool strfun = true;
1619
1620   switch (DECL_FUNCTION_CODE (func))
1621     {
1622     case BUILT_IN_MEMCPY:
1623     case BUILT_IN_MEMCPY_CHK:
1624     case BUILT_IN_MEMCPY_CHKP:
1625     case BUILT_IN_MEMCPY_CHK_CHKP:
1626     case BUILT_IN_MEMPCPY:
1627     case BUILT_IN_MEMPCPY_CHK:
1628     case BUILT_IN_MEMPCPY_CHKP:
1629     case BUILT_IN_MEMPCPY_CHK_CHKP:
1630     case BUILT_IN_MEMMOVE:
1631     case BUILT_IN_MEMMOVE_CHK:
1632     case BUILT_IN_MEMMOVE_CHKP:
1633     case BUILT_IN_MEMMOVE_CHK_CHKP:
1634       strfun = false;
1635       /* Fall through.  */
1636
1637     case BUILT_IN_STPNCPY:
1638     case BUILT_IN_STPNCPY_CHK:
1639     case BUILT_IN_STRNCAT:
1640     case BUILT_IN_STRNCAT_CHK:
1641     case BUILT_IN_STRNCPY:
1642     case BUILT_IN_STRNCPY_CHK:
1643       dst_idx = 0;
1644       src_idx = 1 + with_bounds;
1645       bnd_idx = 2 + 2 * with_bounds;
1646       break;
1647
1648     case BUILT_IN_STPCPY:
1649     case BUILT_IN_STPCPY_CHK:
1650     case BUILT_IN_STPCPY_CHKP:
1651     case BUILT_IN_STPCPY_CHK_CHKP:
1652     case BUILT_IN_STRCPY:
1653     case BUILT_IN_STRCPY_CHK:
1654     case BUILT_IN_STRCPY_CHKP:
1655     case BUILT_IN_STRCPY_CHK_CHKP:
1656     case BUILT_IN_STRCAT:
1657     case BUILT_IN_STRCAT_CHK:
1658     case BUILT_IN_STRCAT_CHKP:
1659     case BUILT_IN_STRCAT_CHK_CHKP:
1660       dst_idx = 0;
1661       src_idx = 1 + with_bounds;
1662       break;
1663
1664     default:
1665       /* Handle other string functions here whose access may need
1666          to be validated for in-bounds offsets and non-overlapping
1667          copies.  (Not all _chkp functions have BUILT_IN_XXX_CHKP
1668          macros so they need to be handled here.)  */
1669       return;
1670     }
1671
1672   unsigned nargs = gimple_call_num_args (call);
1673
1674   tree dst = dst_idx < nargs ? gimple_call_arg (call, dst_idx) : NULL_TREE;
1675   tree src = src_idx < nargs ? gimple_call_arg (call, src_idx) : NULL_TREE;
1676   tree dstwr = bnd_idx < nargs ? gimple_call_arg (call, bnd_idx) : NULL_TREE;
1677
1678   /* For string functions with an unspecified or unknown bound,
1679      assume the size of the access is one.  */
1680   if (!dstwr && strfun)
1681     dstwr = size_one_node;
1682
1683   if (check_bounds_or_overlap (call, dst, src, dstwr, NULL_TREE))
1684     return;
1685
1686   /* Avoid diagnosing the call again.  */
1687   gimple_set_no_warning (call, true);
1688 }
1689
1690 } /* anonymous namespace */
1691
1692 /* Attempt to detect and diagnose invalid offset bounds and (except for
1693    memmove) overlapping copy in a call expression EXPR from SRC to DST
1694    and DSTSIZE and SRCSIZE bytes, respectively.  Both DSTSIZE and
1695    SRCSIZE may be NULL.  Return false when one or the other has been
1696    detected and diagnosed, true otherwise.  */
1697
1698 bool
1699 check_bounds_or_overlap (gcall *call, tree dst, tree src, tree dstsize,
1700                          tree srcsize, bool bounds_only /* = false */)
1701 {
1702   location_t loc = gimple_location (call);
1703
1704   if (tree block = gimple_block (call))
1705     if (location_t *pbloc = block_nonartificial_location (block))
1706       loc = *pbloc;
1707
1708   loc = expansion_point_location_if_in_system_header (loc);
1709
1710   tree func = gimple_call_fndecl (call);
1711
1712   builtin_memref dstref (dst, dstsize);
1713   builtin_memref srcref (src, srcsize);
1714
1715   builtin_access acs (call, dstref, srcref);
1716
1717   /* Set STRICT to the value of the -Warray-bounds=N argument for
1718      string functions or when N > 1.  */
1719   int strict = (acs.strict () || warn_array_bounds > 1 ? warn_array_bounds : 0);
1720
1721   /* Validate offsets first to make sure they are within the bounds
1722      of the destination object if its size is known, or PTRDIFF_MAX
1723      otherwise.  */
1724   if (maybe_diag_offset_bounds (loc, call, func, strict, dst, dstref)
1725       || maybe_diag_offset_bounds (loc, call, func, strict, src, srcref))
1726     {
1727       gimple_set_no_warning (call, true);
1728       return false;
1729     }
1730
1731   bool check_overlap
1732     = (warn_restrict
1733        && (bounds_only
1734            || (DECL_FUNCTION_CODE (func) != BUILT_IN_MEMMOVE
1735                && DECL_FUNCTION_CODE (func) != BUILT_IN_MEMMOVE_CHK)));
1736
1737   if (!check_overlap)
1738     return true;
1739
1740   if (operand_equal_p (dst, src, 0))
1741     {
1742       warning_at (loc, OPT_Wrestrict,
1743                   "%G%qD source argument is the same as destination",
1744                   call, func);
1745       gimple_set_no_warning (call, true);
1746       return false;
1747     }
1748
1749   /* Return false when overlap has been detected.  */
1750   if (maybe_diag_overlap (loc, call, acs))
1751     {
1752       gimple_set_no_warning (call, true);
1753       return false;
1754     }
1755
1756   return true;
1757 }
1758
1759 gimple_opt_pass *
1760 make_pass_warn_restrict (gcc::context *ctxt)
1761 {
1762   return new pass_wrestrict (ctxt);
1763 }