src/jit/rangecheck.cpp

   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 #include "jitpch.h"
   8 #include "rangecheck.h"
   9
  10 // Max stack depth (path length) in walking the UD chain.
  11 static const int MAX_SEARCH_DEPTH = 100;
  12
  13 // Max nodes to visit in the UD chain for the current method being compiled.
  14 static const int MAX_VISIT_BUDGET = 8192;
  15
  16 // RangeCheck constructor.
  17 RangeCheck::RangeCheck(Compiler* pCompiler)
  18     : m_pOverflowMap(nullptr)
  19     , m_pRangeMap(nullptr)
  20     , m_pSearchPath(nullptr)
  21 #ifdef DEBUG
  22     , m_fMappedDefs(false)
  23     , m_pDefTable(nullptr)
  24 #endif
  25     , m_pCompiler(pCompiler)
  26     , m_alloc(pCompiler, CMK_RangeCheck)
  27     , m_nVisitBudget(MAX_VISIT_BUDGET)
  28 {
  29 }
  30
  31 bool RangeCheck::IsOverBudget()
  32 {
  33     return (m_nVisitBudget <= 0);
  34 }
  35
  36 // Get the range map in which computed ranges are cached.
  37 RangeCheck::RangeMap* RangeCheck::GetRangeMap()
  38 {
  39     if (m_pRangeMap == nullptr)
  40     {
  41         m_pRangeMap = new (&m_alloc) RangeMap(&m_alloc);
  42     }
  43     return m_pRangeMap;
  44 }
  45
  46 // Get the overflow map in which computed overflows are cached.
  47 RangeCheck::OverflowMap* RangeCheck::GetOverflowMap()
  48 {
  49     if (m_pOverflowMap == nullptr)
  50     {
  51         m_pOverflowMap = new (&m_alloc) OverflowMap(&m_alloc);
  52     }
  53     return m_pOverflowMap;
  54 }
  55
  56 // Get the length of the array vn, if it is new.
  57 int RangeCheck::GetArrLength(ValueNum vn)
  58 {
  59     ValueNum arrRefVN = m_pCompiler->vnStore->GetArrForLenVn(vn);
  60     return m_pCompiler->vnStore->GetNewArrSize(arrRefVN);
  61 }
  62
  63 // Check if the computed range is within bounds.
  64 bool RangeCheck::BetweenBounds(Range& range, int lower, GenTree* upper)
  65 {
  66 #ifdef DEBUG
  67     if (m_pCompiler->verbose)
  68     {
  69         printf("%s BetweenBounds <%d, ", range.ToString(m_pCompiler->getAllocatorDebugOnly()), lower);
  70         Compiler::printTreeID(upper);
  71         printf(">\n");
  72     }
  73 #endif // DEBUG
  74
  75     ValueNumStore* vnStore = m_pCompiler->vnStore;
  76
  77     // Get the VN for the upper limit.
  78     ValueNum uLimitVN = upper->gtVNPair.GetConservative();
  79
  80 #ifdef DEBUG
  81     JITDUMP("VN%04X upper bound is: ", uLimitVN);
  82     if (m_pCompiler->verbose)
  83     {
  84         vnStore->vnDump(m_pCompiler, uLimitVN);
  85     }
  86     JITDUMP("\n");
  87 #endif
  88
  89     int arrSize = 0;
  90
  91     if (vnStore->IsVNConstant(uLimitVN))
  92     {
  93         ssize_t  constVal  = -1;
  94         unsigned iconFlags = 0;
  95
  96         if (m_pCompiler->optIsTreeKnownIntValue(true, upper, &constVal, &iconFlags))
  97         {
  98             arrSize = (int)constVal;
  99         }
 100     }
 101     else if (vnStore->IsVNArrLen(uLimitVN))
 102     {
 103         // Get the array reference from the length.
 104         ValueNum arrRefVN = vnStore->GetArrForLenVn(uLimitVN);
 105         // Check if array size can be obtained.
 106         arrSize = vnStore->GetNewArrSize(arrRefVN);
 107     }
 108     else if (!vnStore->IsVNCheckedBound(uLimitVN))
 109     {
 110         // If the upper limit is not length, then bail.
 111         return false;
 112     }
 113
 114     JITDUMP("Array size is: %d\n", arrSize);
 115
 116     // Upper limit: len + ucns (upper limit constant).
 117     if (range.UpperLimit().IsBinOpArray())
 118     {
 119         if (range.UpperLimit().vn != uLimitVN)
 120         {
 121             return false;
 122         }
 123
 124         int ucns = range.UpperLimit().GetConstant();
 125
 126         // Upper limit: Len + [0..n]
 127         if (ucns >= 0)
 128         {
 129             return false;
 130         }
 131
 132         // Since upper limit is bounded by the array, return true if lower bound is good.
 133         if (range.LowerLimit().IsConstant() && range.LowerLimit().GetConstant() >= 0)
 134         {
 135             return true;
 136         }
 137
 138         // Check if we have the array size allocated by new.
 139         if (arrSize <= 0)
 140         {
 141             return false;
 142         }
 143
 144         // At this point,
 145         // upper limit = len + ucns. ucns < 0
 146         // lower limit = len + lcns.
 147         if (range.LowerLimit().IsBinOpArray())
 148         {
 149             int lcns = range.LowerLimit().GetConstant();
 150             if (lcns >= 0 || -lcns > arrSize)
 151             {
 152                 return false;
 153             }
 154             return (range.LowerLimit().vn == uLimitVN && lcns <= ucns);
 155         }
 156     }
 157     // If upper limit is constant
 158     else if (range.UpperLimit().IsConstant())
 159     {
 160         if (arrSize <= 0)
 161         {
 162             return false;
 163         }
 164         int ucns = range.UpperLimit().GetConstant();
 165         if (ucns >= arrSize)
 166         {
 167             return false;
 168         }
 169         if (range.LowerLimit().IsConstant())
 170         {
 171             int lcns = range.LowerLimit().GetConstant();
 172             // Make sure lcns < ucns which is already less than arrSize.
 173             return (lcns >= 0 && lcns <= ucns);
 174         }
 175         if (range.LowerLimit().IsBinOpArray())
 176         {
 177             int lcns = range.LowerLimit().GetConstant();
 178             // len + lcns, make sure we don't subtract too much from len.
 179             if (lcns >= 0 || -lcns > arrSize)
 180             {
 181                 return false;
 182             }
 183             // Make sure a.len + lcns <= ucns.
 184             return (range.LowerLimit().vn == uLimitVN && (arrSize + lcns) <= ucns);
 185         }
 186     }
 187
 188     return false;
 189 }
 190
 191 void RangeCheck::OptimizeRangeCheck(BasicBlock* block, GenTree* stmt, GenTree* treeParent)
 192 {
 193     // Check if we are dealing with a bounds check node.
 194     if (treeParent->OperGet() != GT_COMMA)
 195     {
 196         return;
 197     }
 198
 199     // If we are not looking at array bounds check, bail.
 200     GenTree* tree = treeParent->gtOp.gtOp1;
 201     if (!tree->OperIsBoundsCheck())
 202     {
 203         return;
 204     }
 205
 206     GenTreeBoundsChk* bndsChk = tree->AsBoundsChk();
 207     m_pCurBndsChk             = bndsChk;
 208     GenTree* treeIndex        = bndsChk->gtIndex;
 209
 210     // Take care of constant index first, like a[2], for example.
 211     ValueNum idxVn    = treeIndex->gtVNPair.GetConservative();
 212     ValueNum arrLenVn = bndsChk->gtArrLen->gtVNPair.GetConservative();
 213     int      arrSize  = 0;
 214
 215     if (m_pCompiler->vnStore->IsVNConstant(arrLenVn))
 216     {
 217         ssize_t  constVal  = -1;
 218         unsigned iconFlags = 0;
 219
 220         if (m_pCompiler->optIsTreeKnownIntValue(true, bndsChk->gtArrLen, &constVal, &iconFlags))
 221         {
 222             arrSize = (int)constVal;
 223         }
 224     }
 225     else
 226 #ifdef FEATURE_SIMD
 227         if (tree->gtOper != GT_SIMD_CHK
 228 #ifdef FEATURE_HW_INTRINSICS
 229             && tree->gtOper != GT_HW_INTRINSIC_CHK
 230 #endif // FEATURE_HW_INTRINSICS
 231             )
 232 #endif // FEATURE_SIMD
 233     {
 234         arrSize = GetArrLength(arrLenVn);
 235     }
 236
 237     JITDUMP("ArrSize for lengthVN:%03X = %d\n", arrLenVn, arrSize);
 238     if (m_pCompiler->vnStore->IsVNConstant(idxVn) && (arrSize > 0))
 239     {
 240         ssize_t  idxVal    = -1;
 241         unsigned iconFlags = 0;
 242         if (!m_pCompiler->optIsTreeKnownIntValue(true, treeIndex, &idxVal, &iconFlags))
 243         {
 244             return;
 245         }
 246
 247         JITDUMP("[RangeCheck::OptimizeRangeCheck] Is index %d in <0, arrLenVn VN%X sz:%d>.\n", idxVal, arrLenVn,
 248                 arrSize);
 249         if ((idxVal < arrSize) && (idxVal >= 0))
 250         {
 251             JITDUMP("Removing range check\n");
 252             m_pCompiler->optRemoveRangeCheck(treeParent, stmt);
 253             return;
 254         }
 255     }
 256
 257     GetRangeMap()->RemoveAll();
 258     GetOverflowMap()->RemoveAll();
 259     m_pSearchPath = new (&m_alloc) SearchPath(&m_alloc);
 260
 261     // Get the range for this index.
 262     Range range = GetRange(block, treeIndex, false DEBUGARG(0));
 263
 264     // If upper or lower limit is found to be unknown (top), or it was found to
 265     // be unknown because of over budget or a deep search, then return early.
 266     if (range.UpperLimit().IsUnknown() || range.LowerLimit().IsUnknown())
 267     {
 268         // Note: If we had stack depth too deep in the GetRange call, we'd be
 269         // too deep even in the DoesOverflow call. So return early.
 270         return;
 271     }
 272
 273     if (DoesOverflow(block, treeIndex))
 274     {
 275         JITDUMP("Method determined to overflow.\n");
 276         return;
 277     }
 278
 279     JITDUMP("Range value %s\n", range.ToString(m_pCompiler->getAllocatorDebugOnly()));
 280     m_pSearchPath->RemoveAll();
 281     Widen(block, treeIndex, &range);
 282
 283     // If upper or lower limit is unknown, then return.
 284     if (range.UpperLimit().IsUnknown() || range.LowerLimit().IsUnknown())
 285     {
 286         return;
 287     }
 288
 289     // Is the range between the lower and upper bound values.
 290     if (BetweenBounds(range, 0, bndsChk->gtArrLen))
 291     {
 292         JITDUMP("[RangeCheck::OptimizeRangeCheck] Between bounds\n");
 293         m_pCompiler->optRemoveRangeCheck(treeParent, stmt);
 294     }
 295     return;
 296 }
 297
 298 void RangeCheck::Widen(BasicBlock* block, GenTree* tree, Range* pRange)
 299 {
 300 #ifdef DEBUG
 301     if (m_pCompiler->verbose)
 302     {
 303         printf("[RangeCheck::Widen] BB%02d, \n", block->bbNum);
 304         Compiler::printTreeID(tree);
 305         printf("\n");
 306     }
 307 #endif // DEBUG
 308
 309     Range& range = *pRange;
 310
 311     // Try to deduce the lower bound, if it is not known already.
 312     if (range.LowerLimit().IsDependent() || range.LowerLimit().IsUnknown())
 313     {
 314         // To determine the lower bound, ask if the loop increases monotonically.
 315         bool increasing = IsMonotonicallyIncreasing(tree, false);
 316         JITDUMP("IsMonotonicallyIncreasing %d", increasing);
 317         if (increasing)
 318         {
 319             GetRangeMap()->RemoveAll();
 320             *pRange = GetRange(block, tree, true DEBUGARG(0));
 321         }
 322     }
 323 }
 324
 325 bool RangeCheck::IsBinOpMonotonicallyIncreasing(GenTreeOp* binop)
 326 {
 327 #ifdef LEGACY_BACKEND
 328     assert(binop->OperIs(GT_ADD, GT_ASG_ADD));
 329 #else
 330     assert(binop->OperIs(GT_ADD));
 331 #endif
 332
 333     GenTree* op1 = binop->gtGetOp1();
 334     GenTree* op2 = binop->gtGetOp2();
 335
 336     JITDUMP("[RangeCheck::IsBinOpMonotonicallyIncreasing] [%06d], [%06d]\n", Compiler::dspTreeID(op1),
 337             Compiler::dspTreeID(op2));
 338     // Check if we have a var + const.
 339     if (op2->OperGet() == GT_LCL_VAR)
 340     {
 341         jitstd::swap(op1, op2);
 342     }
 343     if (op1->OperGet() != GT_LCL_VAR)
 344     {
 345         JITDUMP("Not monotonic because op1 is not lclVar.\n");
 346         return false;
 347     }
 348     switch (op2->OperGet())
 349     {
 350         case GT_LCL_VAR:
 351             // When adding two local variables, we also must ensure that any constant is non-negative.
 352             return IsMonotonicallyIncreasing(op1, true) && IsMonotonicallyIncreasing(op2, true);
 353
 354         case GT_CNS_INT:
 355             return (op2->AsIntConCommon()->IconValue() >= 0) && IsMonotonicallyIncreasing(op1, false);
 356
 357         default:
 358             JITDUMP("Not monotonic because expression is not recognized.\n");
 359             return false;
 360     }
 361 }
 362
 363 // The parameter rejectNegativeConst is true when we are adding two local vars (see above)
 364 bool RangeCheck::IsMonotonicallyIncreasing(GenTree* expr, bool rejectNegativeConst)
 365 {
 366     JITDUMP("[RangeCheck::IsMonotonicallyIncreasing] [%06d]\n", Compiler::dspTreeID(expr));
 367
 368     // Add hashtable entry for expr.
 369     bool alreadyPresent = m_pSearchPath->Set(expr, nullptr);
 370     if (alreadyPresent)
 371     {
 372         return true;
 373     }
 374
 375     // Remove hashtable entry for expr when we exit the present scope.
 376     auto                                         code = [this, expr] { m_pSearchPath->Remove(expr); };
 377     jitstd::utility::scoped_code<decltype(code)> finally(code);
 378
 379     if (m_pSearchPath->GetCount() > MAX_SEARCH_DEPTH)
 380     {
 381         return false;
 382     }
 383
 384     // If expr is constant, then it is not part of the dependency
 385     // loop which has to increase monotonically.
 386     ValueNum vn = expr->gtVNPair.GetConservative();
 387     if (m_pCompiler->vnStore->IsVNInt32Constant(vn))
 388     {
 389         if (rejectNegativeConst)
 390         {
 391             int cons = m_pCompiler->vnStore->ConstantValue<int>(vn);
 392             return (cons >= 0);
 393         }
 394         else
 395         {
 396             return true;
 397         }
 398     }
 399     // If the rhs expr is local, then try to find the def of the local.
 400     else if (expr->IsLocal())
 401     {
 402         BasicBlock* asgBlock;
 403         GenTreeOp*  asg = GetSsaDefAsg(expr->AsLclVarCommon(), &asgBlock);
 404         if (asg == nullptr)
 405         {
 406             return false;
 407         }
 408
 409         switch (asg->OperGet())
 410         {
 411             case GT_ASG:
 412                 return IsMonotonicallyIncreasing(asg->gtGetOp2(), rejectNegativeConst);
 413
 414 #ifdef LEGACY_BACKEND
 415             case GT_ASG_ADD:
 416                 return IsBinOpMonotonicallyIncreasing(asg);
 417 #endif
 418
 419             default:
 420 #ifndef LEGACY_BACKEND
 421                 noway_assert(false);
 422 #endif
 423                 // All other 'asg->OperGet()' kinds, return false
 424                 break;
 425         }
 426         JITDUMP("Unknown local definition type\n");
 427         return false;
 428     }
 429     else if (expr->OperGet() == GT_ADD)
 430     {
 431         return IsBinOpMonotonicallyIncreasing(expr->AsOp());
 432     }
 433     else if (expr->OperGet() == GT_PHI)
 434     {
 435         for (GenTreeArgList* args = expr->gtOp.gtOp1->AsArgList(); args != nullptr; args = args->Rest())
 436         {
 437             // If the arg is already in the path, skip.
 438             if (m_pSearchPath->Lookup(args->Current()))
 439             {
 440                 continue;
 441             }
 442             if (!IsMonotonicallyIncreasing(args->Current(), rejectNegativeConst))
 443             {
 444                 JITDUMP("Phi argument not monotonic\n");
 445                 return false;
 446             }
 447         }
 448         return true;
 449     }
 450     JITDUMP("Unknown tree type\n");
 451     return false;
 452 }
 453
 454 // Given a lclvar use, try to find the lclvar's defining assignment and its containing block.
 455 GenTreeOp* RangeCheck::GetSsaDefAsg(GenTreeLclVarCommon* lclUse, BasicBlock** asgBlock)
 456 {
 457     unsigned ssaNum = lclUse->GetSsaNum();
 458
 459     if (ssaNum == SsaConfig::RESERVED_SSA_NUM)
 460     {
 461         return nullptr;
 462     }
 463
 464     LclSsaVarDsc* ssaData = m_pCompiler->lvaTable[lclUse->GetLclNum()].GetPerSsaData(ssaNum);
 465     GenTree*      lclDef  = ssaData->m_defLoc.m_tree;
 466
 467     if (lclDef == nullptr)
 468     {
 469         return nullptr;
 470     }
 471
 472     // We have the def node but we also need the assignment node to get its source.
 473     // gtGetParent can be used to get the assignment node but it's rather expensive
 474     // and not strictly necessary here, there shouldn't be any other node between
 475     // the assignment node and its destination node.
 476     GenTree* asg = lclDef->gtNext;
 477
 478     if (!asg->OperIsAssignment() || (asg->gtGetOp1() != lclDef))
 479     {
 480         return nullptr;
 481     }
 482
 483 #ifdef DEBUG
 484     Location* loc = GetDef(lclUse);
 485     assert(loc->parent == asg);
 486     assert(loc->block == ssaData->m_defLoc.m_blk);
 487 #endif
 488
 489     *asgBlock = ssaData->m_defLoc.m_blk;
 490     return asg->AsOp();
 491 }
 492
 493 #ifdef DEBUG
 494 UINT64 RangeCheck::HashCode(unsigned lclNum, unsigned ssaNum)
 495 {
 496     assert(ssaNum != SsaConfig::RESERVED_SSA_NUM);
 497     return UINT64(lclNum) << 32 | ssaNum;
 498 }
 499
 500 // Get the def location of a given variable.
 501 RangeCheck::Location* RangeCheck::GetDef(unsigned lclNum, unsigned ssaNum)
 502 {
 503     Location* loc = nullptr;
 504     if (ssaNum == SsaConfig::RESERVED_SSA_NUM)
 505     {
 506         return nullptr;
 507     }
 508     if (!m_fMappedDefs)
 509     {
 510         MapMethodDefs();
 511     }
 512     // No defs.
 513     if (m_pDefTable == nullptr)
 514     {
 515         return nullptr;
 516     }
 517     m_pDefTable->Lookup(HashCode(lclNum, ssaNum), &loc);
 518     return loc;
 519 }
 520
 521 RangeCheck::Location* RangeCheck::GetDef(GenTreeLclVarCommon* lcl)
 522 {
 523     return GetDef(lcl->GetLclNum(), lcl->GetSsaNum());
 524 }
 525
 526 // Add the def location to the hash table.
 527 void RangeCheck::SetDef(UINT64 hash, Location* loc)
 528 {
 529     if (m_pDefTable == nullptr)
 530     {
 531         m_pDefTable = new (&m_alloc) VarToLocMap(&m_alloc);
 532     }
 533 #ifdef DEBUG
 534     Location* loc2;
 535     if (m_pDefTable->Lookup(hash, &loc2))
 536     {
 537         JITDUMP("Already have BB%02d, [%06d], [%06d] for hash => %0I64X", loc2->block->bbNum,
 538                 Compiler::dspTreeID(loc2->stmt), Compiler::dspTreeID(loc2->tree), hash);
 539         assert(false);
 540     }
 541 #endif
 542     m_pDefTable->Set(hash, loc);
 543 }
 544 #endif
 545
 546 // Merge assertions on the edge flowing into the block about a variable.
 547 void RangeCheck::MergeEdgeAssertions(GenTreeLclVarCommon* lcl, ASSERT_VALARG_TP assertions, Range* pRange)
 548 {
 549     if (BitVecOps::IsEmpty(m_pCompiler->apTraits, assertions))
 550     {
 551         return;
 552     }
 553
 554     if (lcl->gtSsaNum == SsaConfig::RESERVED_SSA_NUM)
 555     {
 556         return;
 557     }
 558     // Walk through the "assertions" to check if the apply.
 559     BitVecOps::Iter iter(m_pCompiler->apTraits, assertions);
 560     unsigned        index = 0;
 561     while (iter.NextElem(&index))
 562     {
 563         AssertionIndex assertionIndex = GetAssertionIndex(index);
 564
 565         Compiler::AssertionDsc* curAssertion = m_pCompiler->optGetAssertion(assertionIndex);
 566
 567         Limit      limit(Limit::keUndef);
 568         genTreeOps cmpOper = GT_NONE;
 569
 570         // Current assertion is of the form (i < len - cns) != 0
 571         if (curAssertion->IsCheckedBoundArithBound())
 572         {
 573             ValueNumStore::CompareCheckedBoundArithInfo info;
 574
 575             // Get i, len, cns and < as "info."
 576             m_pCompiler->vnStore->GetCompareCheckedBoundArithInfo(curAssertion->op1.vn, &info);
 577
 578             if (m_pCompiler->lvaTable[lcl->gtLclNum].GetPerSsaData(lcl->gtSsaNum)->m_vnPair.GetConservative() !=
 579                 info.cmpOp)
 580             {
 581                 continue;
 582             }
 583
 584             if ((info.arrOper != GT_ADD) && (info.arrOper != GT_SUB))
 585             {
 586                 continue;
 587             }
 588
 589             // If the operand that operates on the bound is not constant, then done.
 590             if (!m_pCompiler->vnStore->IsVNInt32Constant(info.arrOp))
 591             {
 592                 continue;
 593             }
 594
 595             int cons = m_pCompiler->vnStore->ConstantValue<int>(info.arrOp);
 596             limit    = Limit(Limit::keBinOpArray, info.vnBound, info.arrOper == GT_SUB ? -cons : cons);
 597             cmpOper  = (genTreeOps)info.cmpOper;
 598         }
 599         // Current assertion is of the form (i < len) != 0
 600         else if (curAssertion->IsCheckedBoundBound())
 601         {
 602             ValueNumStore::CompareCheckedBoundArithInfo info;
 603
 604             // Get the info as "i", "<" and "len"
 605             m_pCompiler->vnStore->GetCompareCheckedBound(curAssertion->op1.vn, &info);
 606
 607             ValueNum lclVn =
 608                 m_pCompiler->lvaTable[lcl->gtLclNum].GetPerSsaData(lcl->gtSsaNum)->m_vnPair.GetConservative();
 609             // If we don't have the same variable we are comparing against, bail.
 610             if (lclVn != info.cmpOp)
 611             {
 612                 continue;
 613             }
 614             limit   = Limit(Limit::keBinOpArray, info.vnBound, 0);
 615             cmpOper = (genTreeOps)info.cmpOper;
 616         }
 617         // Current assertion is of the form (i < 100) != 0
 618         else if (curAssertion->IsConstantBound())
 619         {
 620             ValueNumStore::ConstantBoundInfo info;
 621
 622             // Get the info as "i", "<" and "100"
 623             m_pCompiler->vnStore->GetConstantBoundInfo(curAssertion->op1.vn, &info);
 624
 625             ValueNum lclVn =
 626                 m_pCompiler->lvaTable[lcl->gtLclNum].GetPerSsaData(lcl->gtSsaNum)->m_vnPair.GetConservative();
 627
 628             // If we don't have the same variable we are comparing against, bail.
 629             if (lclVn != info.cmpOpVN)
 630             {
 631                 continue;
 632             }
 633
 634             limit   = Limit(Limit::keConstant, info.constVal);
 635             cmpOper = (genTreeOps)info.cmpOper;
 636         }
 637         // Current assertion is not supported, ignore it
 638         else
 639         {
 640             continue;
 641         }
 642
 643         assert(limit.IsBinOpArray() || limit.IsConstant());
 644
 645         // Make sure the assertion is of the form != 0 or == 0.
 646         if (curAssertion->op2.vn != m_pCompiler->vnStore->VNZeroForType(TYP_INT))
 647         {
 648             continue;
 649         }
 650 #ifdef DEBUG
 651         if (m_pCompiler->verbose)
 652         {
 653             m_pCompiler->optPrintAssertion(curAssertion, assertionIndex);
 654         }
 655 #endif
 656
 657         ValueNum arrLenVN = m_pCurBndsChk->gtArrLen->gtVNPair.GetConservative();
 658
 659         if (m_pCompiler->vnStore->IsVNConstant(arrLenVN))
 660         {
 661             // Set arrLenVN to NoVN; this will make it match the "vn" recorded on
 662             // constant limits (where we explicitly track the constant and don't
 663             // redundantly store its VN in the "vn" field).
 664             arrLenVN = ValueNumStore::NoVN;
 665         }
 666
 667         // During assertion prop we add assertions of the form:
 668         //
 669         //      (i < length) == 0
 670         //      (i < length) != 0
 671         //      (i < 100) == 0
 672         //      (i < 100) != 0
 673         //
 674         // At this point, we have detected that op1.vn is (i < length) or (i < length + cns) or
 675         // (i < 100) and the op2.vn is 0.
 676         //
 677         // Now, let us check if we are == 0 (i.e., op1 assertion is false) or != 0 (op1 assertion
 678         // is true.),
 679         //
 680         // If we have an assertion of the form == 0 (i.e., equals false), then reverse relop.
 681         // The relop has to be reversed because we have: (i < length) is false which is the same
 682         // as (i >= length).
 683         if (curAssertion->assertionKind == Compiler::OAK_EQUAL)
 684         {
 685             cmpOper = GenTree::ReverseRelop(cmpOper);
 686         }
 687
 688         // Bounds are inclusive, so add -1 for upper bound when "<". But make sure we won't overflow.
 689         if (cmpOper == GT_LT && !limit.AddConstant(-1))
 690         {
 691             continue;
 692         }
 693         // Bounds are inclusive, so add +1 for lower bound when ">". But make sure we won't overflow.
 694         if (cmpOper == GT_GT && !limit.AddConstant(1))
 695         {
 696             continue;
 697         }
 698
 699         // Doesn't tighten the current bound. So skip.
 700         if (pRange->uLimit.IsConstant() && limit.vn != arrLenVN)
 701         {
 702             continue;
 703         }
 704
 705         // Check if the incoming limit from assertions tightens the existing upper limit.
 706         if (pRange->uLimit.IsBinOpArray() && (pRange->uLimit.vn == arrLenVN))
 707         {
 708             // We have checked the current range's (pRange's) upper limit is either of the form:
 709             //      length + cns
 710             //      and length == the bndsChkCandidate's arrLen
 711             //
 712             // We want to check if the incoming limit tightens the bound, and for that
 713             // we need to make sure that incoming limit is also on the same length (or
 714             // length + cns) and not some other length.
 715
 716             if (limit.vn != arrLenVN)
 717             {
 718                 JITDUMP("Array length VN did not match cur=$%x, assert=$%x\n", arrLenVN, limit.vn);
 719                 continue;
 720             }
 721
 722             int curCns = pRange->uLimit.cns;
 723             int limCns = (limit.IsBinOpArray()) ? limit.cns : 0;
 724
 725             // Incoming limit doesn't tighten the existing upper limit.
 726             if (limCns >= curCns)
 727             {
 728                 JITDUMP("Bound limit %d doesn't tighten current bound %d\n", limCns, curCns);
 729                 continue;
 730             }
 731         }
 732         else
 733         {
 734             // Current range's upper bound is not "length + cns" and the
 735             // incoming limit is not on the same length as the bounds check candidate.
 736             // So we could skip this assertion. But in cases, of Dependent or Unknown
 737             // type of upper limit, the incoming assertion still tightens the upper
 738             // bound to a saner value. So do not skip the assertion.
 739         }
 740
 741         // cmpOp (loop index i) cmpOper len +/- cns
 742         switch (cmpOper)
 743         {
 744             case GT_LT:
 745                 pRange->uLimit = limit;
 746                 break;
 747
 748             case GT_GT:
 749                 pRange->lLimit = limit;
 750                 break;
 751
 752             case GT_GE:
 753                 pRange->lLimit = limit;
 754                 break;
 755
 756             case GT_LE:
 757                 pRange->uLimit = limit;
 758                 break;
 759
 760             default:
 761                 // All other 'cmpOper' kinds leave lLimit/uLimit unchanged
 762                 break;
 763         }
 764         JITDUMP("The range after edge merging:");
 765         JITDUMP(pRange->ToString(m_pCompiler->getAllocatorDebugOnly()));
 766         JITDUMP("\n");
 767     }
 768 }
 769
 770 // Merge assertions from the pred edges of the block, i.e., check for any assertions about "op's" value numbers for phi
 771 // arguments. If not a phi argument, check if we assertions about local variables.
 772 void RangeCheck::MergeAssertion(BasicBlock* block, GenTree* op, Range* pRange DEBUGARG(int indent))
 773 {
 774     JITDUMP("Merging assertions from pred edges of BB%02d for op [%06d] $%03x\n", block->bbNum, Compiler::dspTreeID(op),
 775             op->gtVNPair.GetConservative());
 776     ASSERT_TP assertions = BitVecOps::UninitVal();
 777
 778     // If we have a phi arg, we can get to the block from it and use its assertion out.
 779     if (op->gtOper == GT_PHI_ARG)
 780     {
 781         GenTreePhiArg* arg  = (GenTreePhiArg*)op;
 782         BasicBlock*    pred = arg->gtPredBB;
 783         if (pred->bbFallsThrough() && pred->bbNext == block)
 784         {
 785             assertions = pred->bbAssertionOut;
 786             JITDUMP("Merge assertions from pred BB%02d edge: %s\n", pred->bbNum,
 787                     BitVecOps::ToString(m_pCompiler->apTraits, assertions));
 788         }
 789         else if ((pred->bbJumpKind == BBJ_COND || pred->bbJumpKind == BBJ_ALWAYS) && pred->bbJumpDest == block)
 790         {
 791             if (m_pCompiler->bbJtrueAssertionOut != nullptr)
 792             {
 793                 assertions = m_pCompiler->bbJtrueAssertionOut[pred->bbNum];
 794                 JITDUMP("Merge assertions from pred BB%02d JTrue edge: %s\n", pred->bbNum,
 795                         BitVecOps::ToString(m_pCompiler->apTraits, assertions));
 796             }
 797         }
 798     }
 799     // Get assertions from bbAssertionIn.
 800     else if (op->IsLocal())
 801     {
 802         assertions = block->bbAssertionIn;
 803     }
 804
 805     if (!BitVecOps::MayBeUninit(assertions))
 806     {
 807         // Perform the merge step to fine tune the range value.
 808         MergeEdgeAssertions(op->AsLclVarCommon(), assertions, pRange);
 809     }
 810 }
 811
 812 // Compute the range for a binary operation.
 813 Range RangeCheck::ComputeRangeForBinOp(BasicBlock* block, GenTreeOp* binop, bool monotonic DEBUGARG(int indent))
 814 {
 815 #ifdef LEGACY_BACKEND
 816     assert(binop->OperIs(GT_ADD, GT_ASG_ADD));
 817 #else
 818     assert(binop->OperIs(GT_ADD));
 819 #endif
 820
 821     GenTree* op1 = binop->gtGetOp1();
 822     GenTree* op2 = binop->gtGetOp2();
 823
 824     Range* op1RangeCached = nullptr;
 825     Range  op1Range       = Limit(Limit::keUndef);
 826     // Check if the range value is already cached.
 827     if (!GetRangeMap()->Lookup(op1, &op1RangeCached))
 828     {
 829         // If we already have the op in the path, then, just rely on assertions, else
 830         // find the range.
 831         if (m_pSearchPath->Lookup(op1))
 832         {
 833             op1Range = Range(Limit(Limit::keDependent));
 834         }
 835         else
 836         {
 837             op1Range = GetRange(block, op1, monotonic DEBUGARG(indent));
 838         }
 839         MergeAssertion(block, op1, &op1Range DEBUGARG(indent + 1));
 840     }
 841     else
 842     {
 843         op1Range = *op1RangeCached;
 844     }
 845
 846     Range* op2RangeCached;
 847     Range  op2Range = Limit(Limit::keUndef);
 848     // Check if the range value is already cached.
 849     if (!GetRangeMap()->Lookup(op2, &op2RangeCached))
 850     {
 851         // If we already have the op in the path, then, just rely on assertions, else
 852         // find the range.
 853         if (m_pSearchPath->Lookup(op2))
 854         {
 855             op2Range = Range(Limit(Limit::keDependent));
 856         }
 857         else
 858         {
 859             op2Range = GetRange(block, op2, monotonic DEBUGARG(indent));
 860         }
 861         MergeAssertion(block, op2, &op2Range DEBUGARG(indent + 1));
 862     }
 863     else
 864     {
 865         op2Range = *op2RangeCached;
 866     }
 867
 868     Range r = RangeOps::Add(op1Range, op2Range);
 869     JITDUMP("BinOp add ranges %s %s = %s\n", op1Range.ToString(m_pCompiler->getAllocatorDebugOnly()),
 870             op2Range.ToString(m_pCompiler->getAllocatorDebugOnly()), r.ToString(m_pCompiler->getAllocatorDebugOnly()));
 871     return r;
 872 }
 873
 874 // Compute the range for a local var definition.
 875 Range RangeCheck::ComputeRangeForLocalDef(BasicBlock*          block,
 876                                           GenTreeLclVarCommon* lcl,
 877                                           bool monotonic DEBUGARG(int indent))
 878 {
 879     BasicBlock* asgBlock;
 880     GenTreeOp*  asg = GetSsaDefAsg(lcl, &asgBlock);
 881     if (asg == nullptr)
 882     {
 883         return Range(Limit(Limit::keUnknown));
 884     }
 885 #ifdef DEBUG
 886     if (m_pCompiler->verbose)
 887     {
 888         JITDUMP("----------------------------------------------------\n");
 889         m_pCompiler->gtDispTree(asg);
 890         JITDUMP("----------------------------------------------------\n");
 891     }
 892 #endif
 893     switch (asg->OperGet())
 894     {
 895         // If the operator of the definition is assignment, then compute the range of the rhs.
 896         case GT_ASG:
 897         {
 898             Range range = GetRange(asgBlock, asg->gtGetOp2(), monotonic DEBUGARG(indent));
 899             if (!BitVecOps::MayBeUninit(block->bbAssertionIn))
 900             {
 901                 JITDUMP("Merge assertions from BB%02d:%s for assignment about [%06d]\n", block->bbNum,
 902                         BitVecOps::ToString(m_pCompiler->apTraits, block->bbAssertionIn),
 903                         Compiler::dspTreeID(asg->gtGetOp1()));
 904                 MergeEdgeAssertions(asg->gtGetOp1()->AsLclVarCommon(), block->bbAssertionIn, &range);
 905                 JITDUMP("done merging\n");
 906             }
 907             return range;
 908         }
 909
 910 #ifdef LEGACY_BACKEND
 911         case GT_ASG_ADD:
 912             // If the operator of the definition is +=, then compute the range of the operands of +.
 913             // Note that gtGetOp1 will return op1 to be the lhs; in the formulation of ssa, we have
 914             // a side table for defs and the lhs of a += is considered to be a use for SSA numbering.
 915             return ComputeRangeForBinOp(asgBlock, asg, monotonic DEBUGARG(indent));
 916 #endif
 917
 918         default:
 919 #ifndef LEGACY_BACKEND
 920             noway_assert(false);
 921 #endif
 922             // All other 'asg->OperGet()' kinds, return Limit::keUnknown
 923             break;
 924     }
 925     return Range(Limit(Limit::keUnknown));
 926 }
 927
 928 // https://msdn.microsoft.com/en-us/windows/apps/hh285054.aspx
 929 // CLR throws IDS_EE_ARRAY_DIMENSIONS_EXCEEDED if array length is > INT_MAX.
 930 // new byte[INT_MAX]; still throws OutOfMemoryException on my system with 32 GB RAM.
 931 // I believe practical limits are still smaller than this number.
 932 #define ARRLEN_MAX (0x7FFFFFFF)
 933
 934 // Get the limit's maximum possible value, treating array length to be ARRLEN_MAX.
 935 bool RangeCheck::GetLimitMax(Limit& limit, int* pMax)
 936 {
 937     int& max1 = *pMax;
 938     switch (limit.type)
 939     {
 940         case Limit::keConstant:
 941             max1 = limit.GetConstant();
 942             break;
 943
 944         case Limit::keBinOpArray:
 945         {
 946             int tmp = GetArrLength(limit.vn);
 947             if (tmp <= 0)
 948             {
 949                 tmp = ARRLEN_MAX;
 950             }
 951             if (IntAddOverflows(tmp, limit.GetConstant()))
 952             {
 953                 return false;
 954             }
 955             max1 = tmp + limit.GetConstant();
 956         }
 957         break;
 958
 959         default:
 960             return false;
 961     }
 962     return true;
 963 }
 964
 965 // Check if the arithmetic overflows.
 966 bool RangeCheck::AddOverflows(Limit& limit1, Limit& limit2)
 967 {
 968     int max1;
 969     if (!GetLimitMax(limit1, &max1))
 970     {
 971         return true;
 972     }
 973
 974     int max2;
 975     if (!GetLimitMax(limit2, &max2))
 976     {
 977         return true;
 978     }
 979
 980     return IntAddOverflows(max1, max2);
 981 }
 982
 983 // Does the bin operation overflow.
 984 bool RangeCheck::DoesBinOpOverflow(BasicBlock* block, GenTreeOp* binop)
 985 {
 986     GenTree* op1 = binop->gtGetOp1();
 987     GenTree* op2 = binop->gtGetOp2();
 988
 989     if (!m_pSearchPath->Lookup(op1) && DoesOverflow(block, op1))
 990     {
 991         return true;
 992     }
 993
 994     if (!m_pSearchPath->Lookup(op2) && DoesOverflow(block, op2))
 995     {
 996         return true;
 997     }
 998
 999     // Get the cached ranges of op1
1000     Range* op1Range = nullptr;
1001     if (!GetRangeMap()->Lookup(op1, &op1Range))
1002     {
1003         return true;
1004     }
1005     // Get the cached ranges of op2
1006     Range* op2Range = nullptr;
1007     if (!GetRangeMap()->Lookup(op2, &op2Range))
1008     {
1009         return true;
1010     }
1011
1012     // If dependent, check if we can use some assertions.
1013     if (op1Range->UpperLimit().IsDependent())
1014     {
1015         MergeAssertion(block, op1, op1Range DEBUGARG(0));
1016     }
1017
1018     // If dependent, check if we can use some assertions.
1019     if (op2Range->UpperLimit().IsDependent())
1020     {
1021         MergeAssertion(block, op2, op2Range DEBUGARG(0));
1022     }
1023
1024     JITDUMP("Checking bin op overflow %s %s\n", op1Range->ToString(m_pCompiler->getAllocatorDebugOnly()),
1025             op2Range->ToString(m_pCompiler->getAllocatorDebugOnly()));
1026
1027     if (!AddOverflows(op1Range->UpperLimit(), op2Range->UpperLimit()))
1028     {
1029         return false;
1030     }
1031     return true;
1032 }
1033
1034 // Check if the var definition the rhs involves arithmetic that overflows.
1035 bool RangeCheck::DoesVarDefOverflow(GenTreeLclVarCommon* lcl)
1036 {
1037     BasicBlock* asgBlock;
1038     GenTreeOp*  asg = GetSsaDefAsg(lcl, &asgBlock);
1039     if (asg == nullptr)
1040     {
1041         return true;
1042     }
1043
1044     switch (asg->OperGet())
1045     {
1046         case GT_ASG:
1047             return DoesOverflow(asgBlock, asg->gtGetOp2());
1048
1049 #ifdef LEGACY_BACKEND
1050         case GT_ASG_ADD:
1051             // For GT_ASG_ADD, op2 is use, op1 is also use since we side table for defs in useasg case.
1052             return DoesBinOpOverflow(asgBlock, asg);
1053 #endif
1054
1055         default:
1056 #ifndef LEGACY_BACKEND
1057             noway_assert(false);
1058 #endif
1059             // All other 'asg->OperGet()' kinds, conservatively return true
1060             break;
1061     }
1062     return true;
1063 }
1064
1065 bool RangeCheck::DoesPhiOverflow(BasicBlock* block, GenTree* expr)
1066 {
1067     for (GenTreeArgList* args = expr->gtOp.gtOp1->AsArgList(); args != nullptr; args = args->Rest())
1068     {
1069         GenTree* arg = args->Current();
1070         if (m_pSearchPath->Lookup(arg))
1071         {
1072             continue;
1073         }
1074         if (DoesOverflow(block, arg))
1075         {
1076             return true;
1077         }
1078     }
1079     return false;
1080 }
1081
1082 bool RangeCheck::DoesOverflow(BasicBlock* block, GenTree* expr)
1083 {
1084     bool overflows = false;
1085     if (!GetOverflowMap()->Lookup(expr, &overflows))
1086     {
1087         overflows = ComputeDoesOverflow(block, expr);
1088     }
1089     return overflows;
1090 }
1091
1092 bool RangeCheck::ComputeDoesOverflow(BasicBlock* block, GenTree* expr)
1093 {
1094     JITDUMP("Does overflow [%06d]?\n", Compiler::dspTreeID(expr));
1095     m_pSearchPath->Set(expr, block);
1096
1097     bool overflows = true;
1098
1099     if (m_pSearchPath->GetCount() > MAX_SEARCH_DEPTH)
1100     {
1101         overflows = true;
1102     }
1103     // If the definition chain resolves to a constant, it doesn't overflow.
1104     else if (m_pCompiler->vnStore->IsVNConstant(expr->gtVNPair.GetConservative()))
1105     {
1106         overflows = false;
1107     }
1108     // Check if the var def has rhs involving arithmetic that overflows.
1109     else if (expr->IsLocal())
1110     {
1111         overflows = DoesVarDefOverflow(expr->AsLclVarCommon());
1112     }
1113     // Check if add overflows.
1114     else if (expr->OperGet() == GT_ADD)
1115     {
1116         overflows = DoesBinOpOverflow(block, expr->AsOp());
1117     }
1118     // Walk through phi arguments to check if phi arguments involve arithmetic that overflows.
1119     else if (expr->OperGet() == GT_PHI)
1120     {
1121         overflows = DoesPhiOverflow(block, expr);
1122     }
1123     GetOverflowMap()->Set(expr, overflows);
1124     m_pSearchPath->Remove(expr);
1125     return overflows;
1126 }
1127
1128 // Compute the range recursively by asking for the range of each variable in the dependency chain.
1129 // eg.: c = a + b; ask range of "a" and "b" and add the results.
1130 // If the result cannot be determined i.e., the dependency chain does not terminate in a value,
1131 // but continues to loop, which will happen with phi nodes. We end the looping by calling the
1132 // value as "dependent" (dep).
1133 // If the loop is proven to be "monotonic", then make liberal decisions while merging phi node.
1134 // eg.: merge((0, dep), (dep, dep)) = (0, dep)
1135 Range RangeCheck::ComputeRange(BasicBlock* block, GenTree* expr, bool monotonic DEBUGARG(int indent))
1136 {
1137     bool  newlyAdded = !m_pSearchPath->Set(expr, block);
1138     Range range      = Limit(Limit::keUndef);
1139
1140     ValueNum vn = expr->gtVNPair.GetConservative();
1141     // If newly added in the current search path, then reduce the budget.
1142     if (newlyAdded)
1143     {
1144         // Assert that we are not re-entrant for a node which has been
1145         // visited and resolved before and not currently on the search path.
1146         noway_assert(!GetRangeMap()->Lookup(expr));
1147         m_nVisitBudget--;
1148     }
1149     // Prevent quadratic behavior.
1150     if (IsOverBudget())
1151     {
1152         // Set to unknown, since an Unknown range resolution, will stop further
1153         // searches. This is because anything that merges with Unknown will
1154         // yield Unknown. Unknown is lattice top.
1155         range = Range(Limit(Limit::keUnknown));
1156         JITDUMP("GetRange not tractable within max node visit budget.\n");
1157     }
1158     // Prevent unbounded recursion.
1159     else if (m_pSearchPath->GetCount() > MAX_SEARCH_DEPTH)
1160     {
1161         // Unknown is lattice top, anything that merges with Unknown will yield Unknown.
1162         range = Range(Limit(Limit::keUnknown));
1163         JITDUMP("GetRange not tractable within max stack depth.\n");
1164     }
1165     // TODO-CQ: The current implementation is reliant on integer storage types
1166     // for constants. It could use INT64. Still, representing ULONG constants
1167     // might require preserving the var_type whether it is a un/signed 64-bit.
1168     // JIT64 doesn't do anything for "long" either. No asm diffs.
1169     else if (expr->TypeGet() == TYP_LONG || expr->TypeGet() == TYP_ULONG)
1170     {
1171         range = Range(Limit(Limit::keUnknown));
1172         JITDUMP("GetRange long or ulong, setting to unknown value.\n");
1173     }
1174     // If VN is constant return range as constant.
1175     else if (m_pCompiler->vnStore->IsVNConstant(vn))
1176     {
1177         range = (m_pCompiler->vnStore->TypeOfVN(vn) == TYP_INT)
1178                     ? Range(Limit(Limit::keConstant, m_pCompiler->vnStore->ConstantValue<int>(vn)))
1179                     : Limit(Limit::keUnknown);
1180     }
1181     // If local, find the definition from the def map and evaluate the range for rhs.
1182     else if (expr->IsLocal())
1183     {
1184         range = ComputeRangeForLocalDef(block, expr->AsLclVarCommon(), monotonic DEBUGARG(indent + 1));
1185         MergeAssertion(block, expr, &range DEBUGARG(indent + 1));
1186     }
1187     // If add, then compute the range for the operands and add them.
1188     else if (expr->OperGet() == GT_ADD)
1189     {
1190         range = ComputeRangeForBinOp(block, expr->AsOp(), monotonic DEBUGARG(indent + 1));
1191     }
1192     // If phi, then compute the range for arguments, calling the result "dependent" when looping begins.
1193     else if (expr->OperGet() == GT_PHI)
1194     {
1195         for (GenTreeArgList* args = expr->gtOp.gtOp1->AsArgList(); args != nullptr; args = args->Rest())
1196         {
1197             Range argRange = Range(Limit(Limit::keUndef));
1198             if (m_pSearchPath->Lookup(args->Current()))
1199             {
1200                 JITDUMP("PhiArg [%06d] is already being computed\n", Compiler::dspTreeID(args->Current()));
1201                 argRange = Range(Limit(Limit::keDependent));
1202             }
1203             else
1204             {
1205                 argRange = GetRange(block, args->Current(), monotonic DEBUGARG(indent + 1));
1206             }
1207             assert(!argRange.LowerLimit().IsUndef());
1208             assert(!argRange.UpperLimit().IsUndef());
1209             MergeAssertion(block, args->Current(), &argRange DEBUGARG(indent + 1));
1210             JITDUMP("Merging ranges %s %s:", range.ToString(m_pCompiler->getAllocatorDebugOnly()),
1211                     argRange.ToString(m_pCompiler->getAllocatorDebugOnly()));
1212             range = RangeOps::Merge(range, argRange, monotonic);
1213             JITDUMP("%s\n", range.ToString(m_pCompiler->getAllocatorDebugOnly()));
1214         }
1215     }
1216     else
1217     {
1218         // The expression is not recognized, so the result is unknown.
1219         range = Range(Limit(Limit::keUnknown));
1220     }
1221
1222     GetRangeMap()->Set(expr, new (&m_alloc) Range(range));
1223     m_pSearchPath->Remove(expr);
1224     return range;
1225 }
1226
1227 #ifdef DEBUG
1228 void Indent(int indent)
1229 {
1230     for (int i = 0; i < indent; ++i)
1231     {
1232         JITDUMP("   ");
1233     }
1234 }
1235 #endif
1236
1237 // Get the range, if it is already computed, use the cached range value, else compute it.
1238 Range RangeCheck::GetRange(BasicBlock* block, GenTree* expr, bool monotonic DEBUGARG(int indent))
1239 {
1240 #ifdef DEBUG
1241     if (m_pCompiler->verbose)
1242     {
1243         Indent(indent);
1244         JITDUMP("[RangeCheck::GetRange] BB%02d", block->bbNum);
1245         m_pCompiler->gtDispTree(expr);
1246         Indent(indent);
1247         JITDUMP("{\n", expr);
1248     }
1249 #endif
1250
1251     Range* pRange = nullptr;
1252     Range  range =
1253         GetRangeMap()->Lookup(expr, &pRange) ? *pRange : ComputeRange(block, expr, monotonic DEBUGARG(indent));
1254
1255 #ifdef DEBUG
1256     if (m_pCompiler->verbose)
1257     {
1258         Indent(indent);
1259         JITDUMP("   %s Range [%06d] => %s\n", (pRange == nullptr) ? "Computed" : "Cached", Compiler::dspTreeID(expr),
1260                 range.ToString(m_pCompiler->getAllocatorDebugOnly()));
1261         Indent(indent);
1262         JITDUMP("}\n", expr);
1263     }
1264 #endif
1265     return range;
1266 }
1267
1268 #ifdef DEBUG
1269 // If this is a tree local definition add its location to the def map.
1270 void RangeCheck::MapStmtDefs(const Location& loc)
1271 {
1272     GenTreeLclVarCommon* tree = loc.tree;
1273
1274     unsigned lclNum = tree->GetLclNum();
1275     unsigned ssaNum = tree->GetSsaNum();
1276     if (ssaNum == SsaConfig::RESERVED_SSA_NUM)
1277     {
1278         return;
1279     }
1280
1281     // If useasg then get the correct ssaNum to add to the map.
1282     if (tree->gtFlags & GTF_VAR_USEASG)
1283     {
1284         unsigned ssaNum = m_pCompiler->GetSsaNumForLocalVarDef(tree);
1285         if (ssaNum != SsaConfig::RESERVED_SSA_NUM)
1286         {
1287             // To avoid ind(addr) use asgs
1288             if (loc.parent->OperIsAssignment())
1289             {
1290                 SetDef(HashCode(lclNum, ssaNum), new (&m_alloc) Location(loc));
1291             }
1292         }
1293     }
1294     // If def get the location and store it against the variable's ssaNum.
1295     else if (tree->gtFlags & GTF_VAR_DEF)
1296     {
1297         if (loc.parent->OperGet() == GT_ASG)
1298         {
1299             SetDef(HashCode(lclNum, ssaNum), new (&m_alloc) Location(loc));
1300         }
1301     }
1302 }
1303
1304 struct MapMethodDefsData
1305 {
1306     RangeCheck* rc;
1307     BasicBlock* block;
1308     GenTree*    stmt;
1309
1310     MapMethodDefsData(RangeCheck* rc, BasicBlock* block, GenTree* stmt) : rc(rc), block(block), stmt(stmt)
1311     {
1312     }
1313 };
1314
1315 Compiler::fgWalkResult MapMethodDefsVisitor(GenTree** ptr, Compiler::fgWalkData* data)
1316 {
1317     GenTree*           tree = *ptr;
1318     MapMethodDefsData* rcd  = ((MapMethodDefsData*)data->pCallbackData);
1319
1320     if (tree->IsLocal())
1321     {
1322         rcd->rc->MapStmtDefs(RangeCheck::Location(rcd->block, rcd->stmt, tree->AsLclVarCommon(), data->parent));
1323     }
1324
1325     return Compiler::WALK_CONTINUE;
1326 }
1327
1328 void RangeCheck::MapMethodDefs()
1329 {
1330     // First, gather where all definitions occur in the program and store it in a map.
1331     for (BasicBlock* block = m_pCompiler->fgFirstBB; block; block = block->bbNext)
1332     {
1333         for (GenTree* stmt = block->bbTreeList; stmt; stmt = stmt->gtNext)
1334         {
1335             MapMethodDefsData data(this, block, stmt);
1336             m_pCompiler->fgWalkTreePre(&stmt->gtStmt.gtStmtExpr, MapMethodDefsVisitor, &data, false, true);
1337         }
1338     }
1339     m_fMappedDefs = true;
1340 }
1341 #endif
1342
1343 // Entry point to range check optimizations.
1344 void RangeCheck::OptimizeRangeChecks()
1345 {
1346     if (m_pCompiler->fgSsaPassesCompleted == 0)
1347     {
1348         return;
1349     }
1350 #ifdef DEBUG
1351     if (m_pCompiler->verbose)
1352     {
1353         JITDUMP("*************** In OptimizeRangeChecks()\n");
1354         JITDUMP("Blocks/trees before phase\n");
1355         m_pCompiler->fgDispBasicBlocks(true);
1356     }
1357 #endif
1358
1359     // Walk through trees looking for arrBndsChk node and check if it can be optimized.
1360     for (BasicBlock* block = m_pCompiler->fgFirstBB; block; block = block->bbNext)
1361     {
1362         for (GenTree* stmt = block->bbTreeList; stmt; stmt = stmt->gtNext)
1363         {
1364             for (GenTree* tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext)
1365             {
1366                 if (IsOverBudget())
1367                 {
1368                     return;
1369                 }
1370                 OptimizeRangeCheck(block, stmt, tree);
1371             }
1372         }
1373     }
1374 }