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