src/jit/rangecheck.h

   1 // Licensed to the .NET Foundation under one or more agreements.
   2 // The .NET Foundation licenses this file to you under the MIT license.
   3 // See the LICENSE file in the project root for more information.
   4
   5 //
   6 //
   7 //  We take the following approach to range check analysis:
   8 //
   9 //  Consider the following loop:
  10 //  for (int i = 0; i < a.len; ++i) {
  11 //      a[i] = 0;
  12 //  }
  13 //
  14 //  This would be represented as:
  15 //              i_0 = 0; BB0
  16 //               /        ______  a[i_1] = 0;     BB2
  17 //              /        /        i_2 = i_1 + 1;
  18 //             /        /          ^
  19 //  i_1 = phi(i_0, i_2); BB1       |
  20 //  i_1 < a.len -------------------+
  21 //
  22 //  BB0 -> BB1
  23 //  BB1 -> (i_1 < a.len) ? BB2 : BB3
  24 //  BB2 -> BB1
  25 //  BB3 -> return
  26 //
  27 //  **Step 1. Walk the statements in the method checking if there is a bounds check.
  28 //  If there is a bounds check, ask the range of the index variable.
  29 //  In the above example i_1's range.
  30 //
  31 //  **Step 2. Follow the defs and the dependency chain:
  32 //  i_1 is a local, so go to its definition which is i_1 = phi(i_0, i_2).
  33 //
  34 //  Since rhs is a phi, we ask the range for i_0 and i_2 in the hopes of merging
  35 //  the resulting ranges for i_1.
  36 //
  37 //  The range of i_0 follows immediately when going to its definition.
  38 //  Ask for the range of i_2, which leads to i_1 + 1.
  39 //  Ask for the range of i_1 and figure we are looping. Call the range of i_1 as
  40 //  "dependent" and quit looping further. The range of "1" is just <1, 1>.
  41 //
  42 //  Now we have exhausted all the variables for which the range can be determined.
  43 //  The others are either "unknown" or "dependent."
  44 //
  45 //  We also merge assertions from its pred block's edges for a phi argument otherwise
  46 //  from the block's assertionIn. This gives us an upper bound for i_1 as a.len.
  47 //
  48 //  **Step 3. Check if an overflow occurs in the dependency chain (loop.)
  49 //  In the above case, we want to make sure there is no overflow in the definitions
  50 //  involving i_1 and i_2. Merge assertions from the block's edges whenever possible.
  51 //
  52 //  **Step 4. Check if the dependency chain is monotonic.
  53 //
  54 //  **Step 5. If monotonic is true, then perform a widening step, where we assume, the
  55 //  SSA variables that are "dependent" get their values from the definitions in the
  56 //  dependency loop and their initial values must be the definitions that are not in
  57 //  the dependency loop, in this case i_0's value which is 0.
  58 //
  59
  60 #pragma once
  61 #include "compiler.h"
  62
  63 static bool IntAddOverflows(int max1, int max2)
  64 {
  65     if (max1 > 0 && max2 > 0 && INT_MAX - max1 < max2)
  66     {
  67         return true;
  68     }
  69     if (max1 < 0 && max2 < 0 && max1 < INT_MIN - max2)
  70     {
  71         return true;
  72     }
  73     return false;
  74 }
  75
  76 struct Limit
  77 {
  78     enum LimitType
  79     {
  80         keUndef, // The limit is yet to be computed.
  81         keBinOpArray,
  82         keConstant,
  83         keDependent, // The limit is dependent on some other value.
  84         keUnknown,   // The limit could not be determined.
  85     };
  86
  87     Limit() : type(keUndef)
  88     {
  89     }
  90
  91     Limit(LimitType type) : type(type)
  92     {
  93     }
  94
  95     Limit(LimitType type, int cns) : cns(cns), vn(ValueNumStore::NoVN), type(type)
  96     {
  97         assert(type == keConstant);
  98     }
  99
 100     Limit(LimitType type, ValueNum vn, int cns) : cns(cns), vn(vn), type(type)
 101     {
 102         assert(type == keBinOpArray);
 103     }
 104
 105     bool IsUndef()
 106     {
 107         return type == keUndef;
 108     }
 109     bool IsDependent()
 110     {
 111         return type == keDependent;
 112     }
 113     bool IsUnknown()
 114     {
 115         return type == keUnknown;
 116     }
 117     bool IsConstant()
 118     {
 119         return type == keConstant;
 120     }
 121     int GetConstant()
 122     {
 123         return cns;
 124     }
 125     bool IsBinOpArray()
 126     {
 127         return type == keBinOpArray;
 128     }
 129     bool AddConstant(int i)
 130     {
 131         switch (type)
 132         {
 133             case keDependent:
 134                 return true;
 135             case keBinOpArray:
 136                 if (IntAddOverflows(cns, i))
 137                 {
 138                     return false;
 139                 }
 140                 cns += i;
 141                 return true;
 142
 143             case keConstant:
 144                 if (IntAddOverflows(cns, i))
 145                 {
 146                     return false;
 147                 }
 148                 cns += i;
 149                 return true;
 150
 151             case keUndef:
 152             case keUnknown:
 153                 // For these values of 'type', conservatively return false
 154                 break;
 155         }
 156
 157         return false;
 158     }
 159
 160     bool Equals(Limit& l)
 161     {
 162         switch (type)
 163         {
 164             case keUndef:
 165             case keUnknown:
 166             case keDependent:
 167                 return l.type == type;
 168
 169             case keBinOpArray:
 170                 return l.type == type && l.vn == vn && l.cns == cns;
 171
 172             case keConstant:
 173                 return l.type == type && l.cns == cns;
 174         }
 175         return false;
 176     }
 177 #ifdef DEBUG
 178     const char* ToString(CompAllocator* alloc)
 179     {
 180         unsigned size = 64;
 181         char*    buf  = (char*)alloc->Alloc(size);
 182         switch (type)
 183         {
 184             case keUndef:
 185                 return "Undef";
 186
 187             case keUnknown:
 188                 return "Unknown";
 189
 190             case keDependent:
 191                 return "Dependent";
 192
 193             case keBinOpArray:
 194                 sprintf_s(buf, size, "VN%04X + %d", vn, cns);
 195                 return buf;
 196
 197             case keConstant:
 198                 sprintf_s(buf, size, "%d", cns);
 199                 return buf;
 200         }
 201         unreached();
 202     }
 203 #endif
 204     int       cns;
 205     ValueNum  vn;
 206     LimitType type;
 207 };
 208
 209 // Range struct contains upper and lower limit.
 210 struct Range
 211 {
 212     Limit uLimit;
 213     Limit lLimit;
 214
 215     Range(const Limit& limit) : uLimit(limit), lLimit(limit)
 216     {
 217     }
 218
 219     Range(const Limit& lLimit, const Limit& uLimit) : uLimit(uLimit), lLimit(lLimit)
 220     {
 221     }
 222
 223     Limit& UpperLimit()
 224     {
 225         return uLimit;
 226     }
 227
 228     Limit& LowerLimit()
 229     {
 230         return lLimit;
 231     }
 232
 233 #ifdef DEBUG
 234     char* ToString(CompAllocator* alloc)
 235     {
 236         size_t size = 64;
 237         char*  buf  = (char*)alloc->Alloc(size);
 238         sprintf_s(buf, size, "<%s, %s>", lLimit.ToString(alloc), uLimit.ToString(alloc));
 239         return buf;
 240     }
 241 #endif
 242 };
 243
 244 // Helpers for operations performed on ranges
 245 struct RangeOps
 246 {
 247     // Given a constant limit in "l1", add it to l2 and mutate "l2".
 248     static Limit AddConstantLimit(Limit& l1, Limit& l2)
 249     {
 250         assert(l1.IsConstant());
 251         Limit l = l2;
 252         if (l.AddConstant(l1.GetConstant()))
 253         {
 254             return l;
 255         }
 256         else
 257         {
 258             return Limit(Limit::keUnknown);
 259         }
 260     }
 261
 262     // Given two ranges "r1" and "r2", perform an add operation on the
 263     // ranges.
 264     static Range Add(Range& r1, Range& r2)
 265     {
 266         Limit& r1lo = r1.LowerLimit();
 267         Limit& r1hi = r1.UpperLimit();
 268         Limit& r2lo = r2.LowerLimit();
 269         Limit& r2hi = r2.UpperLimit();
 270
 271         Range result = Limit(Limit::keUnknown);
 272
 273         // Check lo ranges if they are dependent and not unknown.
 274         if ((r1lo.IsDependent() && !r1lo.IsUnknown()) || (r2lo.IsDependent() && !r2lo.IsUnknown()))
 275         {
 276             result.lLimit = Limit(Limit::keDependent);
 277         }
 278         // Check hi ranges if they are dependent and not unknown.
 279         if ((r1hi.IsDependent() && !r1hi.IsUnknown()) || (r2hi.IsDependent() && !r2hi.IsUnknown()))
 280         {
 281             result.uLimit = Limit(Limit::keDependent);
 282         }
 283
 284         if (r1lo.IsConstant())
 285         {
 286             result.lLimit = AddConstantLimit(r1lo, r2lo);
 287         }
 288         if (r2lo.IsConstant())
 289         {
 290             result.lLimit = AddConstantLimit(r2lo, r1lo);
 291         }
 292         if (r1hi.IsConstant())
 293         {
 294             result.uLimit = AddConstantLimit(r1hi, r2hi);
 295         }
 296         if (r2hi.IsConstant())
 297         {
 298             result.uLimit = AddConstantLimit(r2hi, r1hi);
 299         }
 300         return result;
 301     }
 302
 303     // Given two ranges "r1" and "r2", do a Phi merge. If "monotonic" is true,
 304     // then ignore the dependent variables.
 305     static Range Merge(Range& r1, Range& r2, bool monotonic)
 306     {
 307         Limit& r1lo = r1.LowerLimit();
 308         Limit& r1hi = r1.UpperLimit();
 309         Limit& r2lo = r2.LowerLimit();
 310         Limit& r2hi = r2.UpperLimit();
 311
 312         // Take care of lo part.
 313         Range result = Limit(Limit::keUnknown);
 314         if (r1lo.IsUnknown() || r2lo.IsUnknown())
 315         {
 316             result.lLimit = Limit(Limit::keUnknown);
 317         }
 318         // Uninitialized, just copy.
 319         else if (r1lo.IsUndef())
 320         {
 321             result.lLimit = r2lo;
 322         }
 323         else if (r1lo.IsDependent() || r2lo.IsDependent())
 324         {
 325             if (monotonic)
 326             {
 327                 result.lLimit = r1lo.IsDependent() ? r2lo : r1lo;
 328             }
 329             else
 330             {
 331                 result.lLimit = Limit(Limit::keDependent);
 332             }
 333         }
 334
 335         // Take care of hi part.
 336         if (r1hi.IsUnknown() || r2hi.IsUnknown())
 337         {
 338             result.uLimit = Limit(Limit::keUnknown);
 339         }
 340         else if (r1hi.IsUndef())
 341         {
 342             result.uLimit = r2hi;
 343         }
 344         else if (r1hi.IsDependent() || r2hi.IsDependent())
 345         {
 346             if (monotonic)
 347             {
 348                 result.uLimit = r1hi.IsDependent() ? r2hi : r1hi;
 349             }
 350             else
 351             {
 352                 result.uLimit = Limit(Limit::keDependent);
 353             }
 354         }
 355
 356         if (r1lo.IsConstant() && r2lo.IsConstant())
 357         {
 358             result.lLimit = Limit(Limit::keConstant, min(r1lo.GetConstant(), r2lo.GetConstant()));
 359         }
 360         if (r1hi.IsConstant() && r2hi.IsConstant())
 361         {
 362             result.uLimit = Limit(Limit::keConstant, max(r1hi.GetConstant(), r2hi.GetConstant()));
 363         }
 364         if (r2hi.Equals(r1hi))
 365         {
 366             result.uLimit = r2hi;
 367         }
 368         if (r2lo.Equals(r1lo))
 369         {
 370             result.lLimit = r1lo;
 371         }
 372         // Widen Upper Limit => Max(k, (a.len + n)) yields (a.len + n),
 373         // This is correct if k >= 0 and n >= k, since a.len always >= 0
 374         // (a.len + n) could overflow, but the result (a.len + n) also
 375         // preserves the overflow.
 376         if (r1hi.IsConstant() && r1hi.GetConstant() >= 0 && r2hi.IsBinOpArray() &&
 377             r2hi.GetConstant() >= r1hi.GetConstant())
 378         {
 379             result.uLimit = r2hi;
 380         }
 381         if (r2hi.IsConstant() && r2hi.GetConstant() >= 0 && r1hi.IsBinOpArray() &&
 382             r1hi.GetConstant() >= r2hi.GetConstant())
 383         {
 384             result.uLimit = r1hi;
 385         }
 386         if (r1hi.IsBinOpArray() && r2hi.IsBinOpArray() && r1hi.vn == r2hi.vn)
 387         {
 388             result.uLimit = r1hi;
 389             // Widen the upper bound if the other constant is greater.
 390             if (r2hi.GetConstant() > r1hi.GetConstant())
 391             {
 392                 result.uLimit = r2hi;
 393             }
 394         }
 395         return result;
 396     }
 397 };
 398
 399 class RangeCheck
 400 {
 401 public:
 402     // Constructor
 403     RangeCheck(Compiler* pCompiler);
 404
 405     typedef JitHashTable<GenTree*, JitPtrKeyFuncs<GenTree>, bool>        OverflowMap;
 406     typedef JitHashTable<GenTree*, JitPtrKeyFuncs<GenTree>, Range*>      RangeMap;
 407     typedef JitHashTable<GenTree*, JitPtrKeyFuncs<GenTree>, BasicBlock*> SearchPath;
 408
 409 #ifdef DEBUG
 410     // TODO-Cleanup: This code has been kept around just to ensure that the SSA data is still
 411     // valid when RangeCheck runs. It should be removed at some point (and perhaps replaced
 412     // by a proper SSA validity checker).
 413
 414     // Location information is used to map where the defs occur in the method.
 415     struct Location
 416     {
 417         BasicBlock*          block;
 418         GenTree*             stmt;
 419         GenTreeLclVarCommon* tree;
 420         GenTree*             parent;
 421         Location(BasicBlock* block, GenTree* stmt, GenTreeLclVarCommon* tree, GenTree* parent)
 422             : block(block), stmt(stmt), tree(tree), parent(parent)
 423         {
 424         }
 425
 426     private:
 427         Location();
 428     };
 429
 430     typedef JitHashTable<INT64, JitLargePrimitiveKeyFuncs<INT64>, Location*> VarToLocMap;
 431
 432     // Generate a hashcode unique for this ssa var.
 433     UINT64 HashCode(unsigned lclNum, unsigned ssaNum);
 434
 435     // Add a location of the definition of ssa var to the location map.
 436     // Requires "hash" to be computed using HashCode.
 437     // Requires "location" to be the local definition.
 438     void SetDef(UINT64 hash, Location* loc);
 439
 440     // Given a tree node that is a local, return the Location defining the local.
 441     Location* GetDef(GenTreeLclVarCommon* lcl);
 442     Location* GetDef(unsigned lclNum, unsigned ssaNum);
 443
 444     // Given a statement, check if it is a def and add its locations in a map.
 445     void MapStmtDefs(const Location& loc);
 446
 447     // Given the CFG, check if it has defs and add their locations in a map.
 448     void MapMethodDefs();
 449 #endif
 450
 451     int GetArrLength(ValueNum vn);
 452
 453     // Check whether the computed range is within lower and upper bounds. This function
 454     // assumes that the lower range is resolved and upper range is symbolic as in an
 455     // increasing loop.
 456     // TODO-CQ: This is not general enough.
 457     bool BetweenBounds(Range& range, int lower, GenTree* upper);
 458
 459     // Entry point to optimize range checks in the block. Assumes value numbering
 460     // and assertion prop phases are completed.
 461     void OptimizeRangeChecks();
 462
 463     // Given a "tree" node, check if it contains array bounds check node and
 464     // optimize to remove it, if possible. Requires "stmt" and "block" that
 465     // contain the tree.
 466     void OptimizeRangeCheck(BasicBlock* block, GenTree* stmt, GenTree* tree);
 467
 468     // Given the index expression try to find its range.
 469     // The range of a variable depends on its rhs which in turn depends on its constituent variables.
 470     // The "path" is the path taken in the search for the rhs' range and its constituents' range.
 471     // If "monotonic" is true, the calculations are made more liberally assuming initial values
 472     // at phi definitions.
 473     Range GetRange(BasicBlock* block, GenTree* expr, bool monotonic DEBUGARG(int indent));
 474
 475     // Given the local variable, first find the definition of the local and find the range of the rhs.
 476     // Helper for GetRange.
 477     Range ComputeRangeForLocalDef(BasicBlock* block, GenTreeLclVarCommon* lcl, bool monotonic DEBUGARG(int indent));
 478
 479     // Compute the range, rather than retrieve a cached value. Helper for GetRange.
 480     Range ComputeRange(BasicBlock* block, GenTree* expr, bool monotonic DEBUGARG(int indent));
 481
 482     // Compute the range for the op1 and op2 for the given binary operator.
 483     Range ComputeRangeForBinOp(BasicBlock* block, GenTreeOp* binop, bool monotonic DEBUGARG(int indent));
 484
 485     // Merge assertions from AssertionProp's flags, for the corresponding "phiArg."
 486     // Requires "pRange" to contain range that is computed partially.
 487     void MergeAssertion(BasicBlock* block, GenTree* phiArg, Range* pRange DEBUGARG(int indent));
 488
 489     // Inspect the "assertions" and extract assertions about the given "phiArg" and
 490     // refine the "pRange" value.
 491     void MergeEdgeAssertions(GenTreeLclVarCommon* lcl, ASSERT_VALARG_TP assertions, Range* pRange);
 492
 493     // The maximum possible value of the given "limit." If such a value could not be determined
 494     // return "false." For example: ARRLEN_MAX for array length.
 495     bool GetLimitMax(Limit& limit, int* pMax);
 496
 497     // Does the addition of the two limits overflow?
 498     bool AddOverflows(Limit& limit1, Limit& limit2);
 499
 500     // Does the binary operation between the operands overflow? Check recursively.
 501     bool DoesBinOpOverflow(BasicBlock* block, GenTreeOp* binop);
 502
 503     // Does the phi operands involve an assignment that could overflow?
 504     bool DoesPhiOverflow(BasicBlock* block, GenTree* expr);
 505
 506     // Find the def of the "expr" local and recurse on the arguments if any of them involve a
 507     // calculation that overflows.
 508     bool DoesVarDefOverflow(GenTreeLclVarCommon* lcl);
 509
 510     bool ComputeDoesOverflow(BasicBlock* block, GenTree* expr);
 511
 512     // Does the current "expr" which is a use involve a definition, that overflows.
 513     bool DoesOverflow(BasicBlock* block, GenTree* tree);
 514
 515     // Widen the range by first checking if the induction variable is monotonic. Requires "pRange"
 516     // to be partially computed.
 517     void Widen(BasicBlock* block, GenTree* tree, Range* pRange);
 518
 519     // Is the binary operation increasing the value.
 520     bool IsBinOpMonotonicallyIncreasing(GenTreeOp* binop);
 521
 522     // Given an "expr" trace its rhs and their definitions to check if all the assignments
 523     // are monotonically increasing.
 524     //
 525     bool IsMonotonicallyIncreasing(GenTree* tree, bool rejectNegativeConst);
 526
 527     // We allocate a budget to avoid walking long UD chains. When traversing each link in the UD
 528     // chain, we decrement the budget. When the budget hits 0, then no more range check optimization
 529     // will be applied for the currently compiled method.
 530     bool IsOverBudget();
 531
 532 private:
 533     // Given a lclvar use, try to find the lclvar's defining assignment and its containing block.
 534     GenTreeOp* GetSsaDefAsg(GenTreeLclVarCommon* lclUse, BasicBlock** asgBlock);
 535
 536     GenTreeBoundsChk* m_pCurBndsChk;
 537
 538     // Get the cached overflow values.
 539     OverflowMap* GetOverflowMap();
 540     OverflowMap* m_pOverflowMap;
 541
 542     // Get the cached range values.
 543     RangeMap* GetRangeMap();
 544     RangeMap* m_pRangeMap;
 545
 546     SearchPath* m_pSearchPath;
 547
 548 #ifdef DEBUG
 549     bool         m_fMappedDefs;
 550     VarToLocMap* m_pDefTable;
 551 #endif
 552
 553     Compiler*     m_pCompiler;
 554     CompAllocator m_alloc;
 555
 556     // The number of nodes for which range is computed throughout the current method.
 557     // When this limit is zero, we have exhausted all the budget to walk the ud-chain.
 558     int m_nVisitBudget;
 559 };