gcc/gimple-ssa-warn-restrict.c

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