src/jit/assertionprop.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 /*XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
   6 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
   7 XX                                                                           XX
   8 XX                          AssertionProp                                    XX
   9 XX                                                                           XX
  10 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  11 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  12 */
  13
  14 #include "jitpch.h"
  15 #ifdef _MSC_VER
  16 #pragma hdrstop
  17 #endif
  18
  19 /*****************************************************************************
  20  *
  21  *  Helper passed to Compiler::fgWalkTreePre() to find the Asgn node for optAddCopies()
  22  */
  23
  24 /* static */
  25 Compiler::fgWalkResult Compiler::optAddCopiesCallback(GenTree** pTree, fgWalkData* data)
  26 {
  27     GenTree* tree = *pTree;
  28
  29     if (tree->OperIsAssignment())
  30     {
  31         GenTree*  op1  = tree->gtOp.gtOp1;
  32         Compiler* comp = data->compiler;
  33
  34         if ((op1->gtOper == GT_LCL_VAR) && (op1->gtLclVarCommon.gtLclNum == comp->optAddCopyLclNum))
  35         {
  36             comp->optAddCopyAsgnNode = tree;
  37             return WALK_ABORT;
  38         }
  39     }
  40     return WALK_CONTINUE;
  41 }
  42
  43 /*****************************************************************************
  44  *
  45  *  Add new copies before Assertion Prop.
  46  */
  47
  48 void Compiler::optAddCopies()
  49 {
  50     unsigned   lclNum;
  51     LclVarDsc* varDsc;
  52
  53 #ifdef DEBUG
  54     if (verbose)
  55     {
  56         printf("\n*************** In optAddCopies()\n\n");
  57     }
  58     if (verboseTrees)
  59     {
  60         printf("Blocks/Trees at start of phase\n");
  61         fgDispBasicBlocks(true);
  62     }
  63 #endif
  64
  65     // Don't add any copies if we have reached the tracking limit.
  66     if (lvaHaveManyLocals())
  67     {
  68         return;
  69     }
  70
  71     for (lclNum = 0, varDsc = lvaTable; lclNum < lvaCount; lclNum++, varDsc++)
  72     {
  73         var_types typ = varDsc->TypeGet();
  74
  75         // We only add copies for non temp local variables
  76         // that have a single def and that can possibly be enregistered
  77
  78         if (varDsc->lvIsTemp || !varDsc->lvSingleDef || !varTypeCanReg(typ))
  79         {
  80             continue;
  81         }
  82
  83         /* For lvNormalizeOnLoad(), we need to add a cast to the copy-assignment
  84            like "copyLclNum = int(varDsc)" and optAssertionGen() only
  85            tracks simple assignments. The same goes for lvNormalizedOnStore as
  86            the cast is generated in fgMorphSmpOpAsg. This boils down to not having
  87            a copy until optAssertionGen handles this*/
  88         if (varDsc->lvNormalizeOnLoad() || varDsc->lvNormalizeOnStore() || typ == TYP_BOOL)
  89         {
  90             continue;
  91         }
  92
  93         if (varTypeIsSmall(varDsc->TypeGet()) || typ == TYP_BOOL)
  94         {
  95             continue;
  96         }
  97
  98         // If locals must be initialized to zero, that initialization counts as a second definition.
  99         // VB in particular allows usage of variables not explicitly initialized.
 100         // Note that this effectively disables this optimization for all local variables
 101         // as C# sets InitLocals all the time starting in Whidbey.
 102
 103         if (!varDsc->lvIsParam && info.compInitMem)
 104         {
 105             continue;
 106         }
 107
 108         // On x86 we may want to add a copy for an incoming double parameter
 109         // because we can ensure that the copy we make is double aligned
 110         // where as we can never ensure the alignment of an incoming double parameter
 111         //
 112         // On all other platforms we will never need to make a copy
 113         // for an incoming double parameter
 114
 115         bool isFloatParam = false;
 116
 117 #ifdef _TARGET_X86_
 118         isFloatParam = varDsc->lvIsParam && varTypeIsFloating(typ);
 119 #endif
 120
 121         if (!isFloatParam && !varDsc->lvVolatileHint)
 122         {
 123             continue;
 124         }
 125
 126         // We don't want to add a copy for a variable that is part of a struct
 127         if (varDsc->lvIsStructField)
 128         {
 129             continue;
 130         }
 131
 132         // We require that the weighted ref count be significant.
 133         if (varDsc->lvRefCntWtd <= (BB_LOOP_WEIGHT * BB_UNITY_WEIGHT / 2))
 134         {
 135             continue;
 136         }
 137
 138         // For parameters, we only want to add a copy for the heavier-than-average
 139         // uses instead of adding a copy to cover every single use.
 140         // 'paramImportantUseDom' is the set of blocks that dominate the
 141         // heavier-than-average uses of a parameter.
 142         // Initial value is all blocks.
 143
 144         BlockSet paramImportantUseDom(BlockSetOps::MakeFull(this));
 145
 146         // This will be threshold for determining heavier-than-average uses
 147         unsigned paramAvgWtdRefDiv2 = (varDsc->lvRefCntWtd + varDsc->lvRefCnt / 2) / (varDsc->lvRefCnt * 2);
 148
 149         bool paramFoundImportantUse = false;
 150
 151 #ifdef DEBUG
 152         if (verbose)
 153         {
 154             printf("Trying to add a copy for V%02u %s, avg_wtd = %s\n", lclNum,
 155                    varDsc->lvIsParam ? "an arg" : "a local", refCntWtd2str(paramAvgWtdRefDiv2));
 156         }
 157 #endif
 158
 159         //
 160         // We must have a ref in a block that is dominated only by the entry block
 161         //
 162
 163         if (BlockSetOps::MayBeUninit(varDsc->lvRefBlks))
 164         {
 165             // No references
 166             continue;
 167         }
 168
 169         bool isDominatedByFirstBB = false;
 170
 171         BlockSetOps::Iter iter(this, varDsc->lvRefBlks);
 172         unsigned          bbNum = 0;
 173         while (iter.NextElem(&bbNum))
 174         {
 175             /* Find the block 'bbNum' */
 176             BasicBlock* block = fgFirstBB;
 177             while (block && (block->bbNum != bbNum))
 178             {
 179                 block = block->bbNext;
 180             }
 181             noway_assert(block && (block->bbNum == bbNum));
 182
 183             bool     importantUseInBlock = (varDsc->lvIsParam) && (block->getBBWeight(this) > paramAvgWtdRefDiv2);
 184             bool     isPreHeaderBlock    = ((block->bbFlags & BBF_LOOP_PREHEADER) != 0);
 185             BlockSet blockDom(BlockSetOps::UninitVal());
 186             BlockSet blockDomSub0(BlockSetOps::UninitVal());
 187
 188             if (block->bbIDom == nullptr && isPreHeaderBlock)
 189             {
 190                 // Loop Preheader blocks that we insert will have a bbDom set that is nullptr
 191                 // but we can instead use the bNext successor block's dominator information
 192                 noway_assert(block->bbNext != nullptr);
 193                 BlockSetOps::AssignNoCopy(this, blockDom, fgGetDominatorSet(block->bbNext));
 194             }
 195             else
 196             {
 197                 BlockSetOps::AssignNoCopy(this, blockDom, fgGetDominatorSet(block));
 198             }
 199
 200             if (!BlockSetOps::IsEmpty(this, blockDom))
 201             {
 202                 BlockSetOps::Assign(this, blockDomSub0, blockDom);
 203                 if (isPreHeaderBlock)
 204                 {
 205                     // We must clear bbNext block number from the dominator set
 206                     BlockSetOps::RemoveElemD(this, blockDomSub0, block->bbNext->bbNum);
 207                 }
 208                 /* Is this block dominated by fgFirstBB? */
 209                 if (BlockSetOps::IsMember(this, blockDomSub0, fgFirstBB->bbNum))
 210                 {
 211                     isDominatedByFirstBB = true;
 212                 }
 213             }
 214
 215 #ifdef DEBUG
 216             if (verbose)
 217             {
 218                 printf("        Referenced in BB%02u, bbWeight is %s", bbNum, refCntWtd2str(block->getBBWeight(this)));
 219
 220                 if (isDominatedByFirstBB)
 221                 {
 222                     printf(", which is dominated by BB01");
 223                 }
 224
 225                 if (importantUseInBlock)
 226                 {
 227                     printf(", ImportantUse");
 228                 }
 229
 230                 printf("\n");
 231             }
 232 #endif
 233
 234             /* If this is a heavier-than-average block, then track which
 235                blocks dominate this use of the parameter. */
 236             if (importantUseInBlock)
 237             {
 238                 paramFoundImportantUse = true;
 239                 BlockSetOps::IntersectionD(this, paramImportantUseDom,
 240                                            blockDomSub0); // Clear blocks that do not dominate
 241             }
 242         }
 243
 244         // We should have found at least one heavier-than-averageDiv2 block.
 245         if (varDsc->lvIsParam)
 246         {
 247             if (!paramFoundImportantUse)
 248             {
 249                 continue;
 250             }
 251         }
 252
 253         // For us to add a new copy:
 254         // we require that we have a floating point parameter
 255         // or a lvVolatile variable that is always reached from the first BB
 256         // and we have at least one block available in paramImportantUseDom
 257         //
 258         bool doCopy = (isFloatParam || (isDominatedByFirstBB && varDsc->lvVolatileHint)) &&
 259                       !BlockSetOps::IsEmpty(this, paramImportantUseDom);
 260
 261         // Under stress mode we expand the number of candidates
 262         // to include parameters of any type
 263         // or any variable that is always reached from the first BB
 264         //
 265         if (compStressCompile(STRESS_GENERIC_VARN, 30))
 266         {
 267             // Ensure that we preserve the invariants required by the subsequent code.
 268             if (varDsc->lvIsParam || isDominatedByFirstBB)
 269             {
 270                 doCopy = true;
 271             }
 272         }
 273
 274         if (!doCopy)
 275         {
 276             continue;
 277         }
 278
 279         GenTree* stmt;
 280         unsigned copyLclNum = lvaGrabTemp(false DEBUGARG("optAddCopies"));
 281
 282         // Because lvaGrabTemp may have reallocated the lvaTable, ensure varDsc
 283         // is still in sync with lvaTable[lclNum];
 284         varDsc = &lvaTable[lclNum];
 285
 286         // Set lvType on the new Temp Lcl Var
 287         lvaTable[copyLclNum].lvType = typ;
 288
 289 #ifdef DEBUG
 290         if (verbose)
 291         {
 292             printf("\n    Finding the best place to insert the assignment V%02i=V%02i\n", copyLclNum, lclNum);
 293         }
 294 #endif
 295
 296         if (varDsc->lvIsParam)
 297         {
 298             noway_assert(varDsc->lvDefStmt == nullptr || varDsc->lvIsStructField);
 299
 300             // Create a new copy assignment tree
 301             GenTree* copyAsgn = gtNewTempAssign(copyLclNum, gtNewLclvNode(lclNum, typ));
 302
 303             /* Find the best block to insert the new assignment     */
 304             /* We will choose the lowest weighted block, and within */
 305             /* those block, the highest numbered block which        */
 306             /* dominates all the uses of the local variable         */
 307
 308             /* Our default is to use the first block */
 309             BasicBlock* bestBlock  = fgFirstBB;
 310             unsigned    bestWeight = bestBlock->getBBWeight(this);
 311             BasicBlock* block      = bestBlock;
 312
 313 #ifdef DEBUG
 314             if (verbose)
 315             {
 316                 printf("        Starting at BB%02u, bbWeight is %s", block->bbNum,
 317                        refCntWtd2str(block->getBBWeight(this)));
 318
 319                 printf(", bestWeight is %s\n", refCntWtd2str(bestWeight));
 320             }
 321 #endif
 322
 323             /* We have already calculated paramImportantUseDom above. */
 324             BlockSetOps::Iter iter(this, paramImportantUseDom);
 325             unsigned          bbNum = 0;
 326             while (iter.NextElem(&bbNum))
 327             {
 328                 /* Advance block to point to 'bbNum' */
 329                 /* This assumes that the iterator returns block number is increasing lexical order. */
 330                 while (block && (block->bbNum != bbNum))
 331                 {
 332                     block = block->bbNext;
 333                 }
 334                 noway_assert(block && (block->bbNum == bbNum));
 335
 336 #ifdef DEBUG
 337                 if (verbose)
 338                 {
 339                     printf("        Considering BB%02u, bbWeight is %s", block->bbNum,
 340                            refCntWtd2str(block->getBBWeight(this)));
 341
 342                     printf(", bestWeight is %s\n", refCntWtd2str(bestWeight));
 343                 }
 344 #endif
 345
 346                 // Does this block have a smaller bbWeight value?
 347                 if (block->getBBWeight(this) > bestWeight)
 348                 {
 349 #ifdef DEBUG
 350                     if (verbose)
 351                     {
 352                         printf("bbWeight too high\n");
 353                     }
 354 #endif
 355                     continue;
 356                 }
 357
 358                 // Don't use blocks that are exception handlers because
 359                 // inserting a new first statement will interface with
 360                 // the CATCHARG
 361
 362                 if (handlerGetsXcptnObj(block->bbCatchTyp))
 363                 {
 364 #ifdef DEBUG
 365                     if (verbose)
 366                     {
 367                         printf("Catch block\n");
 368                     }
 369 #endif
 370                     continue;
 371                 }
 372
 373                 // Don't use the BBJ_ALWAYS block marked with BBF_KEEP_BBJ_ALWAYS. These
 374                 // are used by EH code. The JIT can not generate code for such a block.
 375
 376                 if (block->bbFlags & BBF_KEEP_BBJ_ALWAYS)
 377                 {
 378 #if FEATURE_EH_FUNCLETS
 379                     // With funclets, this is only used for BBJ_CALLFINALLY/BBJ_ALWAYS pairs. For x86, it is also used
 380                     // as the "final step" block for leaving finallys.
 381                     assert((block->bbPrev != nullptr) && block->bbPrev->isBBCallAlwaysPair());
 382 #endif // FEATURE_EH_FUNCLETS
 383 #ifdef DEBUG
 384                     if (verbose)
 385                     {
 386                         printf("Internal EH BBJ_ALWAYS block\n");
 387                     }
 388 #endif
 389                     continue;
 390                 }
 391
 392                 // This block will be the new candidate for the insert point
 393                 // for the new assignment
 394                 CLANG_FORMAT_COMMENT_ANCHOR;
 395
 396 #ifdef DEBUG
 397                 if (verbose)
 398                 {
 399                     printf("new bestBlock\n");
 400                 }
 401 #endif
 402
 403                 bestBlock  = block;
 404                 bestWeight = block->getBBWeight(this);
 405             }
 406
 407             // If there is a use of the variable in this block
 408             // then we insert the assignment at the beginning
 409             // otherwise we insert the statement at the end
 410             CLANG_FORMAT_COMMENT_ANCHOR;
 411
 412 #ifdef DEBUG
 413             if (verbose)
 414             {
 415                 printf("        Insert copy at the %s of BB%02u\n",
 416                        (BlockSetOps::IsEmpty(this, paramImportantUseDom) ||
 417                         BlockSetOps::IsMember(this, varDsc->lvRefBlks, bestBlock->bbNum))
 418                            ? "start"
 419                            : "end",
 420                        bestBlock->bbNum);
 421             }
 422 #endif
 423
 424             if (BlockSetOps::IsEmpty(this, paramImportantUseDom) ||
 425                 BlockSetOps::IsMember(this, varDsc->lvRefBlks, bestBlock->bbNum))
 426             {
 427                 stmt = fgInsertStmtAtBeg(bestBlock, copyAsgn);
 428             }
 429             else
 430             {
 431                 stmt = fgInsertStmtNearEnd(bestBlock, copyAsgn);
 432             }
 433
 434             /* Increment its lvRefCnt and lvRefCntWtd */
 435             lvaTable[lclNum].incRefCnts(fgFirstBB->getBBWeight(this), this);
 436
 437             /* Increment its lvRefCnt and lvRefCntWtd */
 438             lvaTable[copyLclNum].incRefCnts(fgFirstBB->getBBWeight(this), this);
 439         }
 440         else
 441         {
 442             noway_assert(varDsc->lvDefStmt != nullptr);
 443
 444             /* Locate the assignment to varDsc in the lvDefStmt */
 445             stmt = varDsc->lvDefStmt;
 446             noway_assert(stmt->gtOper == GT_STMT);
 447
 448             optAddCopyLclNum   = lclNum;  // in
 449             optAddCopyAsgnNode = nullptr; // out
 450
 451             fgWalkTreePre(&stmt->gtStmt.gtStmtExpr, Compiler::optAddCopiesCallback, (void*)this, false);
 452
 453             noway_assert(optAddCopyAsgnNode);
 454
 455             GenTree* tree = optAddCopyAsgnNode;
 456             GenTree* op1  = tree->gtOp.gtOp1;
 457
 458             noway_assert(tree && op1 && tree->OperIsAssignment() && (op1->gtOper == GT_LCL_VAR) &&
 459                          (op1->gtLclVarCommon.gtLclNum == lclNum));
 460
 461             /*  TODO-Review: BB_UNITY_WEIGHT is not the correct block weight */
 462             unsigned blockWeight = BB_UNITY_WEIGHT;
 463
 464             /* Increment its lvRefCnt and lvRefCntWtd twice */
 465             lvaTable[copyLclNum].incRefCnts(blockWeight, this);
 466             lvaTable[copyLclNum].incRefCnts(blockWeight, this);
 467
 468             /* Assign the old expression into the new temp */
 469
 470             GenTree* newAsgn = gtNewTempAssign(copyLclNum, tree->gtOp.gtOp2);
 471
 472             /* Copy the new temp to op1 */
 473
 474             GenTree* copyAsgn = gtNewAssignNode(op1, gtNewLclvNode(copyLclNum, typ));
 475
 476             /* Change the tree to a GT_COMMA with the two assignments as child nodes */
 477
 478             tree->gtBashToNOP();
 479             tree->ChangeOper(GT_COMMA);
 480
 481             tree->gtOp.gtOp1 = newAsgn;
 482             tree->gtOp.gtOp2 = copyAsgn;
 483
 484             tree->gtFlags |= (newAsgn->gtFlags & GTF_ALL_EFFECT);
 485             tree->gtFlags |= (copyAsgn->gtFlags & GTF_ALL_EFFECT);
 486         }
 487
 488 #ifdef DEBUG
 489         if (verbose)
 490         {
 491             printf("\nIntroducing a new copy for V%02u\n", lclNum);
 492             gtDispTree(stmt->gtStmt.gtStmtExpr);
 493             printf("\n");
 494         }
 495 #endif
 496     }
 497 }
 498
 499 //------------------------------------------------------------------------------
 500 // GetAssertionDep: Retrieve the assertions on this local variable
 501 //
 502 // Arguments:
 503 //    lclNum - The local var id.
 504 //
 505 // Return Value:
 506 //    The dependent assertions (assertions using the value of the local var)
 507 //    of the local var.
 508 //
 509
 510 ASSERT_TP& Compiler::GetAssertionDep(unsigned lclNum)
 511 {
 512     JitExpandArray<ASSERT_TP>& dep = *optAssertionDep;
 513     if (dep[lclNum] == nullptr)
 514     {
 515         dep[lclNum] = BitVecOps::MakeEmpty(apTraits);
 516     }
 517     return dep[lclNum];
 518 }
 519
 520 /*****************************************************************************
 521  *
 522  *  Initialize the assertion prop bitset traits and the default bitsets.
 523  */
 524
 525 void Compiler::optAssertionTraitsInit(AssertionIndex assertionCount)
 526 {
 527     apTraits = new (this, CMK_AssertionProp) BitVecTraits(assertionCount, this);
 528     apFull   = BitVecOps::MakeFull(apTraits);
 529 }
 530
 531 /*****************************************************************************
 532  *
 533  *  Initialize the assertion prop tracking logic.
 534  */
 535
 536 void Compiler::optAssertionInit(bool isLocalProp)
 537 {
 538     // Use a function countFunc to determine a proper maximum assertion count for the
 539     // method being compiled. The function is linear to the IL size for small and
 540     // moderate methods. For large methods, considering throughput impact, we track no
 541     // more than 64 assertions.
 542     // Note this tracks at most only 256 assertions.
 543     static const AssertionIndex countFunc[] = {64, 128, 256, 64};
 544     static const unsigned       lowerBound  = 0;
 545     static const unsigned       upperBound  = _countof(countFunc) - 1;
 546     const unsigned              codeSize    = info.compILCodeSize / 512;
 547     optMaxAssertionCount                    = countFunc[isLocalProp ? lowerBound : min(upperBound, codeSize)];
 548
 549     optLocalAssertionProp  = isLocalProp;
 550     optAssertionTabPrivate = new (this, CMK_AssertionProp) AssertionDsc[optMaxAssertionCount];
 551     optComplementaryAssertionMap =
 552         new (this, CMK_AssertionProp) AssertionIndex[optMaxAssertionCount + 1](); // zero-inited (NO_ASSERTION_INDEX)
 553     assert(NO_ASSERTION_INDEX == 0);
 554
 555     if (!isLocalProp)
 556     {
 557         optValueNumToAsserts = new (getAllocator()) ValueNumToAssertsMap(getAllocator());
 558     }
 559
 560     if (optAssertionDep == nullptr)
 561     {
 562         optAssertionDep = new (this, CMK_AssertionProp) JitExpandArray<ASSERT_TP>(getAllocator(), max(1, lvaCount));
 563     }
 564
 565     optAssertionTraitsInit(optMaxAssertionCount);
 566     optAssertionCount      = 0;
 567     optAssertionPropagated = false;
 568     bbJtrueAssertionOut    = nullptr;
 569 }
 570
 571 #ifdef DEBUG
 572 void Compiler::optPrintAssertion(AssertionDsc* curAssertion, AssertionIndex assertionIndex /* =0 */)
 573 {
 574     if (curAssertion->op1.kind == O1K_EXACT_TYPE)
 575     {
 576         printf("Type     ");
 577     }
 578     else if (curAssertion->op1.kind == O1K_ARR_BND)
 579     {
 580         printf("ArrBnds  ");
 581     }
 582     else if (curAssertion->op1.kind == O1K_SUBTYPE)
 583     {
 584         printf("Subtype  ");
 585     }
 586     else if (curAssertion->op2.kind == O2K_LCLVAR_COPY)
 587     {
 588         printf("Copy     ");
 589     }
 590     else if ((curAssertion->op2.kind == O2K_CONST_INT) || (curAssertion->op2.kind == O2K_CONST_LONG) ||
 591              (curAssertion->op2.kind == O2K_CONST_DOUBLE))
 592     {
 593         printf("Constant ");
 594     }
 595     else if (curAssertion->op2.kind == O2K_SUBRANGE)
 596     {
 597         printf("Subrange ");
 598     }
 599     else
 600     {
 601         printf("?assertion classification? ");
 602     }
 603     printf("Assertion: ");
 604     if (!optLocalAssertionProp)
 605     {
 606         printf("(%d, %d) ", curAssertion->op1.vn, curAssertion->op2.vn);
 607     }
 608
 609     if (!optLocalAssertionProp)
 610     {
 611         printf("(" STR_VN "%x," STR_VN "%x) ", curAssertion->op1.vn, curAssertion->op2.vn);
 612     }
 613
 614     if ((curAssertion->op1.kind == O1K_LCLVAR) || (curAssertion->op1.kind == O1K_EXACT_TYPE) ||
 615         (curAssertion->op1.kind == O1K_SUBTYPE))
 616     {
 617         printf("V%02u", curAssertion->op1.lcl.lclNum);
 618         if (curAssertion->op1.lcl.ssaNum != SsaConfig::RESERVED_SSA_NUM)
 619         {
 620             printf(".%02u", curAssertion->op1.lcl.ssaNum);
 621         }
 622     }
 623     else if (curAssertion->op1.kind == O1K_ARR_BND)
 624     {
 625         printf("[idx:");
 626         vnStore->vnDump(this, curAssertion->op1.bnd.vnIdx);
 627         printf(";len:");
 628         vnStore->vnDump(this, curAssertion->op1.bnd.vnLen);
 629         printf("]");
 630     }
 631     else if (curAssertion->op1.kind == O1K_BOUND_OPER_BND)
 632     {
 633         printf("Oper_Bnd");
 634         vnStore->vnDump(this, curAssertion->op1.vn);
 635     }
 636     else if (curAssertion->op1.kind == O1K_BOUND_LOOP_BND)
 637     {
 638         printf("Loop_Bnd");
 639         vnStore->vnDump(this, curAssertion->op1.vn);
 640     }
 641     else if (curAssertion->op1.kind == O1K_CONSTANT_LOOP_BND)
 642     {
 643         printf("Loop_Bnd");
 644         vnStore->vnDump(this, curAssertion->op1.vn);
 645     }
 646     else if (curAssertion->op1.kind == O1K_VALUE_NUMBER)
 647     {
 648         printf("Value_Number");
 649         vnStore->vnDump(this, curAssertion->op1.vn);
 650     }
 651     else
 652     {
 653         printf("?op1.kind?");
 654     }
 655
 656     if (curAssertion->assertionKind == OAK_SUBRANGE)
 657     {
 658         printf(" in ");
 659     }
 660     else if (curAssertion->assertionKind == OAK_EQUAL)
 661     {
 662         if (curAssertion->op1.kind == O1K_LCLVAR)
 663         {
 664             printf(" == ");
 665         }
 666         else
 667         {
 668             printf(" is ");
 669         }
 670     }
 671     else if (curAssertion->assertionKind == OAK_NO_THROW)
 672     {
 673         printf(" in range ");
 674     }
 675     else if (curAssertion->assertionKind == OAK_NOT_EQUAL)
 676     {
 677         if (curAssertion->op1.kind == O1K_LCLVAR)
 678         {
 679             printf(" != ");
 680         }
 681         else
 682         {
 683             printf(" is not ");
 684         }
 685     }
 686     else
 687     {
 688         printf(" ?assertionKind? ");
 689     }
 690
 691     if (curAssertion->op1.kind != O1K_ARR_BND)
 692     {
 693         switch (curAssertion->op2.kind)
 694         {
 695             case O2K_LCLVAR_COPY:
 696                 printf("V%02u", curAssertion->op2.lcl.lclNum);
 697                 if (curAssertion->op1.lcl.ssaNum != SsaConfig::RESERVED_SSA_NUM)
 698                 {
 699                     printf(".%02u", curAssertion->op1.lcl.ssaNum);
 700                 }
 701                 break;
 702
 703             case O2K_CONST_INT:
 704             case O2K_IND_CNS_INT:
 705                 if (curAssertion->op1.kind == O1K_EXACT_TYPE)
 706                 {
 707                     printf("Exact Type MT(%08X)", dspPtr(curAssertion->op2.u1.iconVal));
 708                     assert(curAssertion->op2.u1.iconFlags != 0);
 709                 }
 710                 else if (curAssertion->op1.kind == O1K_SUBTYPE)
 711                 {
 712                     printf("MT(%08X)", dspPtr(curAssertion->op2.u1.iconVal));
 713                     assert(curAssertion->op2.u1.iconFlags != 0);
 714                 }
 715                 else if (curAssertion->op1.kind == O1K_BOUND_OPER_BND)
 716                 {
 717                     assert(!optLocalAssertionProp);
 718                     vnStore->vnDump(this, curAssertion->op2.vn);
 719                 }
 720                 else if (curAssertion->op1.kind == O1K_BOUND_LOOP_BND)
 721                 {
 722                     assert(!optLocalAssertionProp);
 723                     vnStore->vnDump(this, curAssertion->op2.vn);
 724                 }
 725                 else if (curAssertion->op1.kind == O1K_CONSTANT_LOOP_BND)
 726                 {
 727                     assert(!optLocalAssertionProp);
 728                     vnStore->vnDump(this, curAssertion->op2.vn);
 729                 }
 730                 else
 731                 {
 732                     var_types op1Type;
 733
 734                     if (curAssertion->op1.kind == O1K_VALUE_NUMBER)
 735                     {
 736                         op1Type = vnStore->TypeOfVN(curAssertion->op1.vn);
 737                     }
 738                     else
 739                     {
 740                         unsigned lclNum = curAssertion->op1.lcl.lclNum;
 741                         assert(lclNum < lvaCount);
 742                         LclVarDsc* varDsc = lvaTable + lclNum;
 743                         op1Type           = varDsc->lvType;
 744                     }
 745
 746                     if (op1Type == TYP_REF)
 747                     {
 748                         assert(curAssertion->op2.u1.iconVal == 0);
 749                         printf("null");
 750                     }
 751                     else
 752                     {
 753                         if ((curAssertion->op2.u1.iconFlags & GTF_ICON_HDL_MASK) != 0)
 754                         {
 755                             printf("[%08p]", dspPtr(curAssertion->op2.u1.iconVal));
 756                         }
 757                         else
 758                         {
 759                             printf("%d", curAssertion->op2.u1.iconVal);
 760                         }
 761                     }
 762                 }
 763                 break;
 764
 765             case O2K_CONST_LONG:
 766                 printf("0x%016llx", curAssertion->op2.lconVal);
 767                 break;
 768
 769             case O2K_CONST_DOUBLE:
 770                 if (*((__int64*)&curAssertion->op2.dconVal) == (__int64)I64(0x8000000000000000))
 771                 {
 772                     printf("-0.00000");
 773                 }
 774                 else
 775                 {
 776                     printf("%#lg", curAssertion->op2.dconVal);
 777                 }
 778                 break;
 779
 780             case O2K_SUBRANGE:
 781                 printf("[%d..%d]", curAssertion->op2.u2.loBound, curAssertion->op2.u2.hiBound);
 782                 break;
 783
 784             default:
 785                 printf("?op2.kind?");
 786                 break;
 787         }
 788     }
 789
 790     if (assertionIndex > 0)
 791     {
 792         printf(" index=#%02u, mask=", assertionIndex);
 793         printf("%s", BitVecOps::ToString(apTraits, BitVecOps::MakeSingleton(apTraits, assertionIndex - 1)));
 794     }
 795     printf("\n");
 796 }
 797 #endif // DEBUG
 798
 799 /******************************************************************************
 800  *
 801  * Helper to retrieve the "assertIndex" assertion. Note that assertIndex 0
 802  * is NO_ASSERTION_INDEX and "optAssertionCount" is the last valid index.
 803  *
 804  */
 805 Compiler::AssertionDsc* Compiler::optGetAssertion(AssertionIndex assertIndex)
 806 {
 807     assert(NO_ASSERTION_INDEX == 0);
 808     assert(assertIndex != NO_ASSERTION_INDEX);
 809     assert(assertIndex <= optAssertionCount);
 810     AssertionDsc* assertion = &optAssertionTabPrivate[assertIndex - 1];
 811 #ifdef DEBUG
 812     optDebugCheckAssertion(assertion);
 813 #endif
 814
 815     return assertion;
 816 }
 817
 818 /*****************************************************************************
 819  *
 820  * A simple helper routine so not all callers need to supply a AssertionDsc*
 821  * if they don't care about it. Refer overloaded method optCreateAssertion.
 822  *
 823  */
 824 AssertionIndex Compiler::optCreateAssertion(GenTree* op1, GenTree* op2, optAssertionKind assertionKind)
 825 {
 826     AssertionDsc assertionDsc;
 827     return optCreateAssertion(op1, op2, assertionKind, &assertionDsc);
 828 }
 829
 830 /*****************************************************************************
 831  *
 832  *  We attempt to create the following assertion:
 833  *
 834  *     op1 assertionKind op2
 835  *
 836  *  If we can create the assertion then update 'assertion' if we are
 837  *  unsuccessful assertion->assertionKind will be OAK_INVALID. If we are
 838  *  successful in creating the assertion we call optAddAssertion which adds
 839  *  the assertion to our assertion table.
 840  *
 841  *  If we are able to create the assertion the return value is the
 842  *  assertionIndex for this assertion otherwise the return value is
 843  *  NO_ASSERTION_INDEX and we could not create the assertion.
 844  *
 845  */
 846 AssertionIndex Compiler::optCreateAssertion(GenTree*         op1,
 847                                             GenTree*         op2,
 848                                             optAssertionKind assertionKind,
 849                                             AssertionDsc*    assertion)
 850 {
 851     memset(assertion, 0, sizeof(AssertionDsc));
 852     //
 853     // If we cannot create an assertion using op1 and op2 then the assertionKind
 854     // must be OAK_INVALID, so we initialize it to OAK_INVALID and only change it
 855     // to a valid assertion when everything is good.
 856     //
 857     assertion->assertionKind = OAK_INVALID;
 858     bool      haveArgs       = false;
 859     var_types toType;
 860
 861     if (op1->gtOper == GT_ARR_BOUNDS_CHECK)
 862     {
 863         if (assertionKind == OAK_NO_THROW)
 864         {
 865             GenTreeBoundsChk* arrBndsChk = op1->AsBoundsChk();
 866             assertion->assertionKind     = assertionKind;
 867             assertion->op1.kind          = O1K_ARR_BND;
 868             assertion->op1.bnd.vnIdx     = arrBndsChk->gtIndex->gtVNPair.GetConservative();
 869             assertion->op1.bnd.vnLen     = arrBndsChk->gtArrLen->gtVNPair.GetConservative();
 870             goto DONE_ASSERTION;
 871         }
 872     }
 873
 874     //
 875     // Did we receive Helper call args?
 876     //
 877     if (op1->gtOper == GT_LIST)
 878     {
 879         if (op2->gtOper != GT_LIST)
 880         {
 881             goto DONE_ASSERTION; // Don't make an assertion
 882         }
 883         op1      = op1->gtOp.gtOp1;
 884         op2      = op2->gtOp.gtOp1;
 885         haveArgs = true;
 886     }
 887
 888     //
 889     // Are we trying to make a non-null assertion?
 890     //
 891     if (op2 == nullptr)
 892     {
 893         assert(haveArgs == false);
 894         //
 895         // Must an OAK_NOT_EQUAL assertion
 896         //
 897         noway_assert(assertionKind == OAK_NOT_EQUAL);
 898
 899         //
 900         // Set op1 to the instance pointer of the indirection
 901         //
 902
 903         ssize_t offset = 0;
 904         while ((op1->gtOper == GT_ADD) && (op1->gtType == TYP_BYREF))
 905         {
 906             if (op1->gtGetOp2()->IsCnsIntOrI())
 907             {
 908                 offset += op1->gtGetOp2()->gtIntCon.gtIconVal;
 909                 op1 = op1->gtGetOp1();
 910             }
 911             else if (op1->gtGetOp1()->IsCnsIntOrI())
 912             {
 913                 offset += op1->gtGetOp1()->gtIntCon.gtIconVal;
 914                 op1 = op1->gtGetOp2();
 915             }
 916             else
 917             {
 918                 break;
 919             }
 920         }
 921
 922         if (fgIsBigOffset(offset) || op1->gtOper != GT_LCL_VAR)
 923         {
 924             goto DONE_ASSERTION; // Don't make an assertion
 925         }
 926
 927         unsigned lclNum = op1->gtLclVarCommon.gtLclNum;
 928         noway_assert(lclNum < lvaCount);
 929         LclVarDsc* lclVar = &lvaTable[lclNum];
 930
 931         ValueNum vn;
 932
 933         //
 934         // We only perform null-checks on GC refs
 935         // so only make non-null assertions about GC refs
 936         //
 937         if (lclVar->TypeGet() != TYP_REF)
 938         {
 939             if (optLocalAssertionProp || (lclVar->TypeGet() != TYP_BYREF))
 940             {
 941                 goto DONE_ASSERTION; // Don't make an assertion
 942             }
 943
 944             vn = op1->gtVNPair.GetConservative();
 945             VNFuncApp funcAttr;
 946
 947             // Try to get value number corresponding to the GC ref of the indirection
 948             while (vnStore->GetVNFunc(vn, &funcAttr) && (funcAttr.m_func == (VNFunc)GT_ADD) &&
 949                    (vnStore->TypeOfVN(vn) == TYP_BYREF))
 950             {
 951                 if (vnStore->IsVNConstant(funcAttr.m_args[1]) &&
 952                     varTypeIsIntegral(vnStore->TypeOfVN(funcAttr.m_args[1])))
 953                 {
 954                     offset += vnStore->CoercedConstantValue<ssize_t>(funcAttr.m_args[1]);
 955                     vn = funcAttr.m_args[0];
 956                 }
 957                 else if (vnStore->IsVNConstant(funcAttr.m_args[0]) &&
 958                          varTypeIsIntegral(vnStore->TypeOfVN(funcAttr.m_args[0])))
 959                 {
 960                     offset += vnStore->CoercedConstantValue<ssize_t>(funcAttr.m_args[0]);
 961                     vn = funcAttr.m_args[1];
 962                 }
 963                 else
 964                 {
 965                     break;
 966                 }
 967             }
 968
 969             if (fgIsBigOffset(offset) || (vnStore->TypeOfVN(vn) != TYP_REF))
 970             {
 971                 goto DONE_ASSERTION; // Don't make an assertion
 972             }
 973
 974             assertion->op1.kind = O1K_VALUE_NUMBER;
 975         }
 976         else
 977         {
 978             //  If the local variable has its address exposed then bail
 979             if (lclVar->lvAddrExposed)
 980             {
 981                 goto DONE_ASSERTION; // Don't make an assertion
 982             }
 983
 984             assertion->op1.kind       = O1K_LCLVAR;
 985             assertion->op1.lcl.lclNum = lclNum;
 986             assertion->op1.lcl.ssaNum = op1->AsLclVarCommon()->GetSsaNum();
 987             vn                        = op1->gtVNPair.GetConservative();
 988         }
 989
 990         assertion->op1.vn           = vn;
 991         assertion->assertionKind    = assertionKind;
 992         assertion->op2.kind         = O2K_CONST_INT;
 993         assertion->op2.vn           = ValueNumStore::VNForNull();
 994         assertion->op2.u1.iconVal   = 0;
 995         assertion->op2.u1.iconFlags = 0;
 996 #ifdef _TARGET_64BIT_
 997         assertion->op2.u1.iconFlags |= 1; // Signify that this is really TYP_LONG
 998 #endif                                    // _TARGET_64BIT_
 999     }
1000     //
1001     // Are we making an assertion about a local variable?
1002     //
1003     else if (op1->gtOper == GT_LCL_VAR)
1004     {
1005         unsigned lclNum = op1->gtLclVarCommon.gtLclNum;
1006         noway_assert(lclNum < lvaCount);
1007         LclVarDsc* lclVar = &lvaTable[lclNum];
1008
1009         //  If the local variable has its address exposed then bail
1010         if (lclVar->lvAddrExposed)
1011         {
1012             goto DONE_ASSERTION; // Don't make an assertion
1013         }
1014
1015         if (haveArgs)
1016         {
1017             //
1018             // Must either be an OAK_EQUAL or an OAK_NOT_EQUAL assertion
1019             //
1020             if ((assertionKind != OAK_EQUAL) && (assertionKind != OAK_NOT_EQUAL))
1021             {
1022                 goto DONE_ASSERTION; // Don't make an assertion
1023             }
1024
1025             if (op2->gtOper == GT_IND)
1026             {
1027                 op2                 = op2->gtOp.gtOp1;
1028                 assertion->op2.kind = O2K_IND_CNS_INT;
1029             }
1030             else
1031             {
1032                 assertion->op2.kind = O2K_CONST_INT;
1033             }
1034
1035             if (op2->gtOper != GT_CNS_INT)
1036             {
1037                 goto DONE_ASSERTION; // Don't make an assertion
1038             }
1039
1040             //
1041             // TODO-CQ: Check for Sealed class and change kind to O1K_EXACT_TYPE
1042             //          And consider the special cases, like CORINFO_FLG_SHAREDINST or CORINFO_FLG_VARIANCE
1043             //          where a class can be sealed, but they don't behave as exact types because casts to
1044             //          non-base types sometimes still succeed.
1045             //
1046             assertion->op1.kind         = O1K_SUBTYPE;
1047             assertion->op1.lcl.lclNum   = lclNum;
1048             assertion->op1.vn           = op1->gtVNPair.GetConservative();
1049             assertion->op1.lcl.ssaNum   = op1->AsLclVarCommon()->GetSsaNum();
1050             assertion->op2.u1.iconVal   = op2->gtIntCon.gtIconVal;
1051             assertion->op2.vn           = op2->gtVNPair.GetConservative();
1052             assertion->op2.u1.iconFlags = op2->GetIconHandleFlag();
1053
1054             //
1055             // Ok everything has been set and the assertion looks good
1056             //
1057             assertion->assertionKind = assertionKind;
1058         }
1059         else // !haveArgs
1060         {
1061             /* Skip over a GT_COMMA node(s), if necessary */
1062             while (op2->gtOper == GT_COMMA)
1063             {
1064                 op2 = op2->gtOp.gtOp2;
1065             }
1066
1067             assertion->op1.kind       = O1K_LCLVAR;
1068             assertion->op1.lcl.lclNum = lclNum;
1069             assertion->op1.vn         = op1->gtVNPair.GetConservative();
1070             assertion->op1.lcl.ssaNum = op1->AsLclVarCommon()->GetSsaNum();
1071
1072             switch (op2->gtOper)
1073             {
1074                 optOp2Kind op2Kind;
1075                 //
1076                 //  No Assertion
1077                 //
1078                 default:
1079                     goto DONE_ASSERTION; // Don't make an assertion
1080
1081                 //
1082                 //  Constant Assertions
1083                 //
1084                 case GT_CNS_INT:
1085                     op2Kind = O2K_CONST_INT;
1086                     goto CNS_COMMON;
1087
1088                 case GT_CNS_LNG:
1089                     op2Kind = O2K_CONST_LONG;
1090                     goto CNS_COMMON;
1091
1092                 case GT_CNS_DBL:
1093                     op2Kind = O2K_CONST_DOUBLE;
1094                     goto CNS_COMMON;
1095
1096                 CNS_COMMON:
1097                 {
1098                     //
1099                     // Must either be an OAK_EQUAL or an OAK_NOT_EQUAL assertion
1100                     //
1101                     if ((assertionKind != OAK_EQUAL) && (assertionKind != OAK_NOT_EQUAL))
1102                     {
1103                         goto DONE_ASSERTION; // Don't make an assertion
1104                     }
1105
1106                     // If the LclVar is a TYP_LONG then we only make
1107                     // assertions where op2 is also TYP_LONG
1108                     //
1109                     if ((lclVar->TypeGet() == TYP_LONG) && (op2->TypeGet() != TYP_LONG))
1110                     {
1111                         goto DONE_ASSERTION; // Don't make an assertion
1112                     }
1113
1114                     assertion->op2.kind    = op2Kind;
1115                     assertion->op2.lconVal = 0;
1116                     assertion->op2.vn      = op2->gtVNPair.GetConservative();
1117
1118                     if (op2->gtOper == GT_CNS_INT)
1119                     {
1120 #ifdef _TARGET_ARM_
1121                         // Do not Constant-Prop large constants for ARM
1122                         if (!codeGen->validImmForMov(op2->gtIntCon.gtIconVal))
1123                         {
1124                             goto DONE_ASSERTION; // Don't make an assertion
1125                         }
1126 #endif // _TARGET_ARM_
1127                         assertion->op2.u1.iconVal   = op2->gtIntCon.gtIconVal;
1128                         assertion->op2.u1.iconFlags = op2->GetIconHandleFlag();
1129 #ifdef _TARGET_64BIT_
1130                         if (op2->TypeGet() == TYP_LONG || op2->TypeGet() == TYP_BYREF)
1131                         {
1132                             assertion->op2.u1.iconFlags |= 1; // Signify that this is really TYP_LONG
1133                         }
1134 #endif // _TARGET_64BIT_
1135                     }
1136                     else if (op2->gtOper == GT_CNS_LNG)
1137                     {
1138                         assertion->op2.lconVal = op2->gtLngCon.gtLconVal;
1139                     }
1140                     else
1141                     {
1142                         noway_assert(op2->gtOper == GT_CNS_DBL);
1143                         /* If we have an NaN value then don't record it */
1144                         if (_isnan(op2->gtDblCon.gtDconVal))
1145                         {
1146                             goto DONE_ASSERTION; // Don't make an assertion
1147                         }
1148                         assertion->op2.dconVal = op2->gtDblCon.gtDconVal;
1149                     }
1150
1151                     //
1152                     // Ok everything has been set and the assertion looks good
1153                     //
1154                     assertion->assertionKind = assertionKind;
1155                 }
1156                 break;
1157
1158                 //
1159                 //  Copy Assertions
1160                 //
1161                 case GT_LCL_VAR:
1162                 {
1163                     //
1164                     // Must either be an OAK_EQUAL or an OAK_NOT_EQUAL assertion
1165                     //
1166                     if ((assertionKind != OAK_EQUAL) && (assertionKind != OAK_NOT_EQUAL))
1167                     {
1168                         goto DONE_ASSERTION; // Don't make an assertion
1169                     }
1170
1171                     unsigned lclNum2 = op2->gtLclVarCommon.gtLclNum;
1172                     noway_assert(lclNum2 < lvaCount);
1173                     LclVarDsc* lclVar2 = &lvaTable[lclNum2];
1174
1175                     // If the two locals are the same then bail
1176                     if (lclNum == lclNum2)
1177                     {
1178                         goto DONE_ASSERTION; // Don't make an assertion
1179                     }
1180
1181                     // If the types are different then bail */
1182                     if (lclVar->lvType != lclVar2->lvType)
1183                     {
1184                         goto DONE_ASSERTION; // Don't make an assertion
1185                     }
1186
1187                     //  If the local variable has its address exposed then bail
1188                     if (lclVar2->lvAddrExposed)
1189                     {
1190                         goto DONE_ASSERTION; // Don't make an assertion
1191                     }
1192
1193                     assertion->op2.kind       = O2K_LCLVAR_COPY;
1194                     assertion->op2.lcl.lclNum = lclNum2;
1195                     assertion->op2.vn         = op2->gtVNPair.GetConservative();
1196                     assertion->op2.lcl.ssaNum = op2->AsLclVarCommon()->GetSsaNum();
1197
1198                     //
1199                     // Ok everything has been set and the assertion looks good
1200                     //
1201                     assertion->assertionKind = assertionKind;
1202                 }
1203                 break;
1204
1205                 //  Subrange Assertions
1206                 case GT_EQ:
1207                 case GT_NE:
1208                 case GT_LT:
1209                 case GT_LE:
1210                 case GT_GT:
1211                 case GT_GE:
1212
1213                     /* Assigning the result of a RELOP, we can add a boolean subrange assertion */
1214
1215                     toType = TYP_BOOL;
1216                     goto SUBRANGE_COMMON;
1217
1218                 case GT_CLS_VAR:
1219
1220                     /* Assigning the result of an indirection into a LCL_VAR, see if we can add a subrange assertion */
1221
1222                     toType = op2->gtType;
1223                     goto SUBRANGE_COMMON;
1224
1225                 case GT_ARR_ELEM:
1226
1227                     /* Assigning the result of an indirection into a LCL_VAR, see if we can add a subrange assertion */
1228
1229                     toType = op2->gtType;
1230                     goto SUBRANGE_COMMON;
1231
1232                 case GT_LCL_FLD:
1233
1234                     /* Assigning the result of an indirection into a LCL_VAR, see if we can add a subrange assertion */
1235
1236                     toType = op2->gtType;
1237                     goto SUBRANGE_COMMON;
1238
1239                 case GT_IND:
1240
1241                     /* Assigning the result of an indirection into a LCL_VAR, see if we can add a subrange assertion */
1242
1243                     toType = op2->gtType;
1244                     goto SUBRANGE_COMMON;
1245
1246                 case GT_CAST:
1247                 {
1248                     if (lvaTable[lclNum].lvIsStructField && lvaTable[lclNum].lvNormalizeOnLoad())
1249                     {
1250                         // Keep the cast on small struct fields.
1251                         goto DONE_ASSERTION; // Don't make an assertion
1252                     }
1253
1254                     toType = op2->CastToType();
1255                 SUBRANGE_COMMON:
1256                     if ((assertionKind != OAK_SUBRANGE) && (assertionKind != OAK_EQUAL))
1257                     {
1258                         goto DONE_ASSERTION; // Don't make an assertion
1259                     }
1260
1261                     if (varTypeIsFloating(op1->TypeGet()))
1262                     {
1263                         // We don't make assertions on a cast from floating point
1264                         goto DONE_ASSERTION;
1265                     }
1266
1267                     switch (toType)
1268                     {
1269                         case TYP_BOOL:
1270                         case TYP_BYTE:
1271                         case TYP_UBYTE:
1272                         case TYP_SHORT:
1273                         case TYP_USHORT:
1274 #ifdef _TARGET_64BIT_
1275                         case TYP_UINT:
1276                         case TYP_INT:
1277 #endif // _TARGET_64BIT_
1278                             assertion->op2.u2.loBound = AssertionDsc::GetLowerBoundForIntegralType(toType);
1279                             assertion->op2.u2.hiBound = AssertionDsc::GetUpperBoundForIntegralType(toType);
1280                             break;
1281
1282                         default:
1283                             goto DONE_ASSERTION; // Don't make an assertion
1284                     }
1285                     assertion->op2.kind      = O2K_SUBRANGE;
1286                     assertion->assertionKind = OAK_SUBRANGE;
1287                 }
1288                 break;
1289             }
1290         } // else // !haveArgs
1291     }     // if (op1->gtOper == GT_LCL_VAR)
1292
1293     //
1294     // Are we making an IsType assertion?
1295     //
1296     else if (op1->gtOper == GT_IND)
1297     {
1298         op1 = op1->gtOp.gtOp1;
1299         //
1300         // Is this an indirection of a local variable?
1301         //
1302         if (op1->gtOper == GT_LCL_VAR)
1303         {
1304             unsigned lclNum = op1->gtLclVarCommon.gtLclNum;
1305             noway_assert(lclNum < lvaCount);
1306             LclVarDsc* lclVar = &lvaTable[lclNum];
1307
1308             //  If the local variable has its address exposed then bail
1309             if (fgExcludeFromSsa(lclNum))
1310             {
1311                 goto DONE_ASSERTION;
1312             }
1313
1314             // If we have an typeHnd indirection then op1 must be a TYP_REF
1315             //  and the indirection must produce a TYP_I
1316             //
1317             if (op1->gtType != TYP_REF)
1318             {
1319                 goto DONE_ASSERTION; // Don't make an assertion
1320             }
1321
1322             assertion->op1.kind       = O1K_EXACT_TYPE;
1323             assertion->op1.lcl.lclNum = lclNum;
1324             assertion->op1.vn         = op1->gtVNPair.GetConservative();
1325             assertion->op1.lcl.ssaNum = op1->AsLclVarCommon()->GetSsaNum();
1326             assert(assertion->op1.lcl.ssaNum == SsaConfig::RESERVED_SSA_NUM ||
1327                    assertion->op1.vn ==
1328                        lvaTable[lclNum].GetPerSsaData(assertion->op1.lcl.ssaNum)->m_vnPair.GetConservative());
1329
1330             ssize_t  cnsValue  = 0;
1331             unsigned iconFlags = 0;
1332             // Ngen case
1333             if (op2->gtOper == GT_IND)
1334             {
1335                 if (!optIsTreeKnownIntValue(!optLocalAssertionProp, op2->gtOp.gtOp1, &cnsValue, &iconFlags))
1336                 {
1337                     goto DONE_ASSERTION; // Don't make an assertion
1338                 }
1339
1340                 assertion->assertionKind  = assertionKind;
1341                 assertion->op2.kind       = O2K_IND_CNS_INT;
1342                 assertion->op2.u1.iconVal = cnsValue;
1343                 assertion->op2.vn         = op2->gtOp.gtOp1->gtVNPair.GetConservative();
1344                 /* iconFlags should only contain bits in GTF_ICON_HDL_MASK */
1345                 assert((iconFlags & ~GTF_ICON_HDL_MASK) == 0);
1346                 assertion->op2.u1.iconFlags = iconFlags;
1347 #ifdef _TARGET_64BIT_
1348                 if (op2->gtOp.gtOp1->TypeGet() == TYP_LONG)
1349                 {
1350                     assertion->op2.u1.iconFlags |= 1; // Signify that this is really TYP_LONG
1351                 }
1352 #endif // _TARGET_64BIT_
1353             }
1354             // JIT case
1355             else if (optIsTreeKnownIntValue(!optLocalAssertionProp, op2, &cnsValue, &iconFlags))
1356             {
1357                 assertion->assertionKind  = assertionKind;
1358                 assertion->op2.kind       = O2K_IND_CNS_INT;
1359                 assertion->op2.u1.iconVal = cnsValue;
1360                 assertion->op2.vn         = op2->gtVNPair.GetConservative();
1361                 /* iconFlags should only contain bits in GTF_ICON_HDL_MASK */
1362                 assert((iconFlags & ~GTF_ICON_HDL_MASK) == 0);
1363                 assertion->op2.u1.iconFlags = iconFlags;
1364 #ifdef _TARGET_64BIT_
1365                 if (op2->TypeGet() == TYP_LONG)
1366                 {
1367                     assertion->op2.u1.iconFlags |= 1; // Signify that this is really TYP_LONG
1368                 }
1369 #endif // _TARGET_64BIT_
1370             }
1371             else
1372             {
1373                 goto DONE_ASSERTION; // Don't make an assertion
1374             }
1375         }
1376     }
1377
1378 DONE_ASSERTION:
1379     if (assertion->assertionKind == OAK_INVALID)
1380     {
1381         return NO_ASSERTION_INDEX;
1382     }
1383
1384     if (!optLocalAssertionProp)
1385     {
1386         if ((assertion->op1.vn == ValueNumStore::NoVN) || (assertion->op2.vn == ValueNumStore::NoVN) ||
1387             (assertion->op1.vn == ValueNumStore::VNForVoid()) || (assertion->op2.vn == ValueNumStore::VNForVoid()))
1388         {
1389             return NO_ASSERTION_INDEX;
1390         }
1391
1392         // TODO: only copy assertions rely on valid SSA number so we could generate more assertions here
1393         if ((assertion->op1.kind != O1K_VALUE_NUMBER) && (assertion->op1.lcl.ssaNum == SsaConfig::RESERVED_SSA_NUM))
1394         {
1395             return NO_ASSERTION_INDEX;
1396         }
1397     }
1398
1399     // Now add the assertion to our assertion table
1400     noway_assert(assertion->op1.kind != O1K_INVALID);
1401     noway_assert(assertion->op1.kind == O1K_ARR_BND || assertion->op2.kind != O2K_INVALID);
1402     return optAddAssertion(assertion);
1403 }
1404
1405 /*****************************************************************************
1406  *
1407  * If tree is a constant node holding an integral value, retrieve the value in
1408  * pConstant. If the method returns true, pConstant holds the appropriate
1409  * constant. Set "vnBased" to true to indicate local or global assertion prop.
1410  * "pFlags" indicates if the constant is a handle marked by GTF_ICON_HDL_MASK.
1411  */
1412 bool Compiler::optIsTreeKnownIntValue(bool vnBased, GenTree* tree, ssize_t* pConstant, unsigned* pFlags)
1413 {
1414     // Is Local assertion prop?
1415     if (!vnBased)
1416     {
1417         if (tree->OperGet() == GT_CNS_INT)
1418         {
1419             *pConstant = tree->gtIntCon.IconValue();
1420             *pFlags    = tree->GetIconHandleFlag();
1421             return true;
1422         }
1423 #ifdef _TARGET_64BIT_
1424         // Just to be clear, get it from gtLconVal rather than
1425         // overlapping gtIconVal.
1426         else if (tree->OperGet() == GT_CNS_LNG)
1427         {
1428             *pConstant = tree->gtLngCon.gtLconVal;
1429             *pFlags    = tree->GetIconHandleFlag();
1430             return true;
1431         }
1432 #endif
1433         return false;
1434     }
1435
1436     // Global assertion prop
1437     if (!vnStore->IsVNConstant(tree->gtVNPair.GetConservative()))
1438     {
1439         return false;
1440     }
1441
1442     ValueNum  vn     = tree->gtVNPair.GetConservative();
1443     var_types vnType = vnStore->TypeOfVN(vn);
1444     if (vnType == TYP_INT)
1445     {
1446         *pConstant = vnStore->ConstantValue<int>(vn);
1447         *pFlags    = vnStore->IsVNHandle(vn) ? vnStore->GetHandleFlags(vn) : 0;
1448         return true;
1449     }
1450 #ifdef _TARGET_64BIT_
1451     else if (vnType == TYP_LONG)
1452     {
1453         *pConstant = vnStore->ConstantValue<INT64>(vn);
1454         *pFlags    = vnStore->IsVNHandle(vn) ? vnStore->GetHandleFlags(vn) : 0;
1455         return true;
1456     }
1457 #endif
1458     return false;
1459 }
1460
1461 #ifdef DEBUG
1462 /*****************************************************************************
1463  *
1464  * Print the assertions related to a VN for all VNs.
1465  *
1466  */
1467 void Compiler::optPrintVnAssertionMapping()
1468 {
1469     printf("\nVN Assertion Mapping\n");
1470     printf("---------------------\n");
1471     for (ValueNumToAssertsMap::KeyIterator ki = optValueNumToAsserts->Begin(); !ki.Equal(optValueNumToAsserts->End());
1472          ++ki)
1473     {
1474         printf("(%d => ", ki.Get());
1475         printf("%s)\n", BitVecOps::ToString(apTraits, ki.GetValue()));
1476     }
1477 }
1478 #endif
1479
1480 /*****************************************************************************
1481  *
1482  * Maintain a map "optValueNumToAsserts" i.e., vn -> to set of assertions
1483  * about that VN. Given "assertions" about a "vn" add it to the previously
1484  * mapped assertions about that "vn."
1485  */
1486 void Compiler::optAddVnAssertionMapping(ValueNum vn, AssertionIndex index)
1487 {
1488     ASSERT_TP* cur = optValueNumToAsserts->LookupPointer(vn);
1489     if (cur == nullptr)
1490     {
1491         optValueNumToAsserts->Set(vn, BitVecOps::MakeSingleton(apTraits, index - 1));
1492     }
1493     else
1494     {
1495         BitVecOps::AddElemD(apTraits, *cur, index - 1);
1496     }
1497 }
1498
1499 /*****************************************************************************
1500  * Statically if we know that this assertion's VN involves a NaN don't bother
1501  * wasting an assertion table slot.
1502  */
1503 bool Compiler::optAssertionVnInvolvesNan(AssertionDsc* assertion)
1504 {
1505     if (optLocalAssertionProp)
1506     {
1507         return false;
1508     }
1509
1510     static const int SZ      = 2;
1511     ValueNum         vns[SZ] = {assertion->op1.vn, assertion->op2.vn};
1512     for (int i = 0; i < SZ; ++i)
1513     {
1514         if (vnStore->IsVNConstant(vns[i]))
1515         {
1516             var_types type = vnStore->TypeOfVN(vns[i]);
1517             if ((type == TYP_FLOAT && _isnan(vnStore->ConstantValue<float>(vns[i])) != 0) ||
1518                 (type == TYP_DOUBLE && _isnan(vnStore->ConstantValue<double>(vns[i])) != 0))
1519             {
1520                 return true;
1521             }
1522         }
1523     }
1524     return false;
1525 }
1526
1527 /*****************************************************************************
1528  *
1529  *  Given an assertion add it to the assertion table
1530  *
1531  *  If it is already in the assertion table return the assertionIndex that
1532  *  we use to refer to this element.
1533  *  Otherwise add it to the assertion table ad return the assertionIndex that
1534  *  we use to refer to this element.
1535  *  If we need to add to the table and the table is full return the value zero
1536  */
1537 AssertionIndex Compiler::optAddAssertion(AssertionDsc* newAssertion)
1538 {
1539     noway_assert(newAssertion->assertionKind != OAK_INVALID);
1540
1541     // Even though the propagation step takes care of NaN, just a check
1542     // to make sure there is no slot involving a NaN.
1543     if (optAssertionVnInvolvesNan(newAssertion))
1544     {
1545         JITDUMP("Assertion involved Nan not adding\n");
1546         return NO_ASSERTION_INDEX;
1547     }
1548
1549     // Check if exists already, so we can skip adding new one. Search backwards.
1550     for (AssertionIndex index = optAssertionCount; index >= 1; index--)
1551     {
1552         AssertionDsc* curAssertion = optGetAssertion(index);
1553         if (curAssertion->Equals(newAssertion, !optLocalAssertionProp))
1554         {
1555             return index;
1556         }
1557     }
1558
1559     // Check if we are within max count.
1560     if (optAssertionCount >= optMaxAssertionCount)
1561     {
1562         return NO_ASSERTION_INDEX;
1563     }
1564
1565     optAssertionTabPrivate[optAssertionCount] = *newAssertion;
1566     optAssertionCount++;
1567
1568 #ifdef DEBUG
1569     if (verbose)
1570     {
1571         printf("GenTreeNode creates assertion:\n");
1572         gtDispTree(optAssertionPropCurrentTree, nullptr, nullptr, true);
1573         printf(optLocalAssertionProp ? "In BB%02u New Local " : "In BB%02u New Global ", compCurBB->bbNum);
1574         optPrintAssertion(newAssertion, optAssertionCount);
1575     }
1576 #endif // DEBUG
1577
1578     // Assertion mask bits are [index + 1].
1579     if (optLocalAssertionProp)
1580     {
1581         assert(newAssertion->op1.kind == O1K_LCLVAR);
1582
1583         // Mark the variables this index depends on
1584         unsigned lclNum = newAssertion->op1.lcl.lclNum;
1585         BitVecOps::AddElemD(apTraits, GetAssertionDep(lclNum), optAssertionCount - 1);
1586         if (newAssertion->op2.kind == O2K_LCLVAR_COPY)
1587         {
1588             lclNum = newAssertion->op2.lcl.lclNum;
1589             BitVecOps::AddElemD(apTraits, GetAssertionDep(lclNum), optAssertionCount - 1);
1590         }
1591     }
1592     else
1593     // If global assertion prop, then add it to the dependents map.
1594     {
1595         optAddVnAssertionMapping(newAssertion->op1.vn, optAssertionCount);
1596         if (newAssertion->op2.kind == O2K_LCLVAR_COPY)
1597         {
1598             optAddVnAssertionMapping(newAssertion->op2.vn, optAssertionCount);
1599         }
1600     }
1601
1602 #ifdef DEBUG
1603     optDebugCheckAssertions(optAssertionCount);
1604 #endif
1605     return optAssertionCount;
1606 }
1607
1608 #ifdef DEBUG
1609 void Compiler::optDebugCheckAssertion(AssertionDsc* assertion)
1610 {
1611     assert(assertion->assertionKind < OAK_COUNT);
1612     assert(assertion->op1.kind < O1K_COUNT);
1613     assert(assertion->op2.kind < O2K_COUNT);
1614     // It would be good to check that op1.vn and op2.vn are valid value numbers.
1615
1616     switch (assertion->op1.kind)
1617     {
1618         case O1K_LCLVAR:
1619         case O1K_EXACT_TYPE:
1620         case O1K_SUBTYPE:
1621             assert(assertion->op1.lcl.lclNum < lvaCount);
1622             assert(optLocalAssertionProp || ((assertion->op1.lcl.ssaNum - SsaConfig::UNINIT_SSA_NUM) <
1623                                              lvaTable[assertion->op1.lcl.lclNum].lvNumSsaNames));
1624             break;
1625         case O1K_ARR_BND:
1626             // It would be good to check that bnd.vnIdx and bnd.vnLen are valid value numbers.
1627             break;
1628         case O1K_BOUND_OPER_BND:
1629         case O1K_BOUND_LOOP_BND:
1630         case O1K_CONSTANT_LOOP_BND:
1631         case O1K_VALUE_NUMBER:
1632             assert(!optLocalAssertionProp);
1633             break;
1634         default:
1635             break;
1636     }
1637     switch (assertion->op2.kind)
1638     {
1639         case O2K_IND_CNS_INT:
1640         case O2K_CONST_INT:
1641         {
1642             // The only flags that can be set are those in the GTF_ICON_HDL_MASK, or bit 0, which is
1643             // used to indicate a long constant.
1644             assert((assertion->op2.u1.iconFlags & ~(GTF_ICON_HDL_MASK | 1)) == 0);
1645             switch (assertion->op1.kind)
1646             {
1647                 case O1K_EXACT_TYPE:
1648                 case O1K_SUBTYPE:
1649                     assert(assertion->op2.u1.iconFlags != 0);
1650                     break;
1651                 case O1K_LCLVAR:
1652                 case O1K_ARR_BND:
1653                     assert((lvaTable[assertion->op1.lcl.lclNum].lvType != TYP_REF) || (assertion->op2.u1.iconVal == 0));
1654                     break;
1655                 case O1K_VALUE_NUMBER:
1656                     assert((vnStore->TypeOfVN(assertion->op1.vn) != TYP_REF) || (assertion->op2.u1.iconVal == 0));
1657                     break;
1658                 default:
1659                     break;
1660             }
1661         }
1662         break;
1663
1664         default:
1665             // for all other 'assertion->op2.kind' values we don't check anything
1666             break;
1667     }
1668 }
1669
1670 /*****************************************************************************
1671  *
1672  *  Verify that assertion prop related assumptions are valid. If "index"
1673  *  is 0 (i.e., NO_ASSERTION_INDEX) then verify all assertions in the table.
1674  *  If "index" is between 1 and optAssertionCount, then verify the assertion
1675  *  desc corresponding to "index."
1676  */
1677 void Compiler::optDebugCheckAssertions(AssertionIndex index)
1678 {
1679     AssertionIndex start = (index == NO_ASSERTION_INDEX) ? 1 : index;
1680     AssertionIndex end   = (index == NO_ASSERTION_INDEX) ? optAssertionCount : index;
1681     for (AssertionIndex ind = start; ind <= end; ++ind)
1682     {
1683         AssertionDsc* assertion = optGetAssertion(ind);
1684         optDebugCheckAssertion(assertion);
1685     }
1686 }
1687 #endif
1688
1689 /*****************************************************************************
1690  *
1691  * Given a "candidateAssertion", and the assertion operands op1 and op2,
1692  * create a complementary assertion and add it to the assertion table,
1693  * which can be retrieved using optFindComplementary(index)
1694  *
1695  */
1696
1697 void Compiler::optCreateComplementaryAssertion(AssertionIndex assertionIndex, GenTree* op1, GenTree* op2)
1698 {
1699     if (assertionIndex == NO_ASSERTION_INDEX)
1700     {
1701         return;
1702     }
1703
1704     AssertionDsc& candidateAssertion = *optGetAssertion(assertionIndex);
1705     if (candidateAssertion.op1.kind == O1K_BOUND_OPER_BND || candidateAssertion.op1.kind == O1K_BOUND_LOOP_BND ||
1706         candidateAssertion.op1.kind == O1K_CONSTANT_LOOP_BND)
1707     {
1708         AssertionDsc dsc  = candidateAssertion;
1709         dsc.assertionKind = dsc.assertionKind == OAK_EQUAL ? OAK_NOT_EQUAL : OAK_EQUAL;
1710         optAddAssertion(&dsc);
1711         return;
1712     }
1713
1714     if (candidateAssertion.assertionKind == OAK_EQUAL)
1715     {
1716         AssertionIndex index = optCreateAssertion(op1, op2, OAK_NOT_EQUAL);
1717         optMapComplementary(index, assertionIndex);
1718     }
1719     else if (candidateAssertion.assertionKind == OAK_NOT_EQUAL)
1720     {
1721         AssertionIndex index = optCreateAssertion(op1, op2, OAK_EQUAL);
1722         optMapComplementary(index, assertionIndex);
1723     }
1724
1725     // Are we making a subtype or exact type assertion?
1726     if ((candidateAssertion.op1.kind == O1K_SUBTYPE) || (candidateAssertion.op1.kind == O1K_EXACT_TYPE))
1727     {
1728         // Did we recieve helper call args?
1729         if (op1->gtOper == GT_LIST)
1730         {
1731             op1 = op1->gtOp.gtOp1;
1732         }
1733         optCreateAssertion(op1, nullptr, OAK_NOT_EQUAL);
1734     }
1735 }
1736
1737 /*****************************************************************************
1738  *
1739  * Create assertions for jtrue operands. Given operands "op1" and "op2" that
1740  * are used in a conditional evaluation of a jtrue stmt, create assertions
1741  * for the operands.
1742  */
1743
1744 AssertionIndex Compiler::optCreateJtrueAssertions(GenTree* op1, GenTree* op2, Compiler::optAssertionKind assertionKind)
1745 {
1746     AssertionDsc   candidateAssertion;
1747     AssertionIndex assertionIndex = optCreateAssertion(op1, op2, assertionKind, &candidateAssertion);
1748     // Don't bother if we don't have an assertion on the JTrue False path. Current implementation
1749     // allows for a complementary only if there is an assertion on the False path (tree->HasAssertion()).
1750     if (assertionIndex != NO_ASSERTION_INDEX)
1751     {
1752         optCreateComplementaryAssertion(assertionIndex, op1, op2);
1753     }
1754     return assertionIndex;
1755 }
1756
1757 AssertionInfo Compiler::optCreateJTrueBoundsAssertion(GenTree* tree)
1758 {
1759     GenTree* relop = tree->gtGetOp1();
1760     if ((relop->OperKind() & GTK_RELOP) == 0)
1761     {
1762         return NO_ASSERTION_INDEX;
1763     }
1764     GenTree* op1 = relop->gtGetOp1();
1765     GenTree* op2 = relop->gtGetOp2();
1766
1767     ValueNum vn = op1->gtVNPair.GetConservative();
1768
1769     ValueNumStore::UnsignedCompareCheckedBoundInfo unsignedCompareBnd;
1770     // Cases where op1 holds the upper bound arithmetic and op2 is 0.
1771     // Loop condition like: "i < bnd +/-k == 0"
1772     // Assertion: "i < bnd +/- k == 0"
1773     if (vnStore->IsVNCompareCheckedBoundArith(vn) &&
1774         op2->gtVNPair.GetConservative() == vnStore->VNZeroForType(op2->TypeGet()) &&
1775         (relop->gtOper == GT_EQ || relop->gtOper == GT_NE))
1776     {
1777         AssertionDsc dsc;
1778         dsc.assertionKind    = relop->gtOper == GT_EQ ? OAK_EQUAL : OAK_NOT_EQUAL;
1779         dsc.op1.kind         = O1K_BOUND_OPER_BND;
1780         dsc.op1.vn           = vn;
1781         dsc.op2.kind         = O2K_CONST_INT;
1782         dsc.op2.vn           = vnStore->VNZeroForType(op2->TypeGet());
1783         dsc.op2.u1.iconVal   = 0;
1784         dsc.op2.u1.iconFlags = 0;
1785         AssertionIndex index = optAddAssertion(&dsc);
1786         optCreateComplementaryAssertion(index, nullptr, nullptr);
1787         return index;
1788     }
1789     // Cases where op1 holds the upper bound and op2 is 0.
1790     // Loop condition like: "i < bnd == 0"
1791     // Assertion: "i < bnd == false"
1792     else if (vnStore->IsVNCompareCheckedBound(vn) &&
1793              (op2->gtVNPair.GetConservative() == vnStore->VNZeroForType(op2->TypeGet())) &&
1794              (relop->gtOper == GT_EQ || relop->gtOper == GT_NE))
1795     {
1796         AssertionDsc dsc;
1797         dsc.assertionKind    = relop->gtOper == GT_EQ ? OAK_EQUAL : OAK_NOT_EQUAL;
1798         dsc.op1.kind         = O1K_BOUND_LOOP_BND;
1799         dsc.op1.vn           = vn;
1800         dsc.op2.kind         = O2K_CONST_INT;
1801         dsc.op2.vn           = vnStore->VNZeroForType(op2->TypeGet());
1802         dsc.op2.u1.iconVal   = 0;
1803         dsc.op2.u1.iconFlags = 0;
1804         AssertionIndex index = optAddAssertion(&dsc);
1805         optCreateComplementaryAssertion(index, nullptr, nullptr);
1806         return index;
1807     }
1808     // Cases where op1 holds the lhs of the condition op2 holds the bound.
1809     // Loop condition like "i < bnd"
1810     // Assertion: "i < bnd != 0"
1811     else if (vnStore->IsVNCompareCheckedBound(relop->gtVNPair.GetConservative()))
1812     {
1813         AssertionDsc dsc;
1814         dsc.assertionKind    = OAK_NOT_EQUAL;
1815         dsc.op1.kind         = O1K_BOUND_LOOP_BND;
1816         dsc.op1.vn           = relop->gtVNPair.GetConservative();
1817         dsc.op2.kind         = O2K_CONST_INT;
1818         dsc.op2.vn           = vnStore->VNZeroForType(TYP_INT);
1819         dsc.op2.u1.iconVal   = 0;
1820         dsc.op2.u1.iconFlags = 0;
1821         AssertionIndex index = optAddAssertion(&dsc);
1822         optCreateComplementaryAssertion(index, nullptr, nullptr);
1823         return index;
1824     }
1825     // Loop condition like "(uint)i < (uint)bnd" or equivalent
1826     // Assertion: "no throw" since this condition guarantees that i is both >= 0 and < bnd (on the appropiate edge)
1827     else if (vnStore->IsVNUnsignedCompareCheckedBound(relop->gtVNPair.GetConservative(), &unsignedCompareBnd))
1828     {
1829         assert(unsignedCompareBnd.vnIdx != ValueNumStore::NoVN);
1830         assert((unsignedCompareBnd.cmpOper == VNF_LT_UN) || (unsignedCompareBnd.cmpOper == VNF_GE_UN));
1831         assert(vnStore->IsVNCheckedBound(unsignedCompareBnd.vnBound));
1832
1833         AssertionDsc dsc;
1834         dsc.assertionKind = OAK_NO_THROW;
1835         dsc.op1.kind      = O1K_ARR_BND;
1836         dsc.op1.vn        = relop->gtVNPair.GetConservative();
1837         dsc.op1.bnd.vnIdx = unsignedCompareBnd.vnIdx;
1838         dsc.op1.bnd.vnLen = unsignedCompareBnd.vnBound;
1839         dsc.op2.kind      = O2K_INVALID;
1840         dsc.op2.vn        = ValueNumStore::NoVN;
1841
1842         AssertionIndex index = optAddAssertion(&dsc);
1843         if (unsignedCompareBnd.cmpOper == VNF_GE_UN)
1844         {
1845             // By default JTRUE generated assertions hold on the "jump" edge. We have i >= bnd but we're really
1846             // after i < bnd so we need to change the assertion edge to "next".
1847             return AssertionInfo::ForNextEdge(index);
1848         }
1849         return index;
1850     }
1851     // Cases where op1 holds the condition bound check and op2 is 0.
1852     // Loop condition like: "i < 100 == 0"
1853     // Assertion: "i < 100 == false"
1854     else if (vnStore->IsVNConstantBound(vn) &&
1855              (op2->gtVNPair.GetConservative() == vnStore->VNZeroForType(op2->TypeGet())) &&
1856              (relop->gtOper == GT_EQ || relop->gtOper == GT_NE))
1857     {
1858         AssertionDsc dsc;
1859         dsc.assertionKind    = relop->gtOper == GT_EQ ? OAK_EQUAL : OAK_NOT_EQUAL;
1860         dsc.op1.kind         = O1K_CONSTANT_LOOP_BND;
1861         dsc.op1.vn           = vn;
1862         dsc.op2.kind         = O2K_CONST_INT;
1863         dsc.op2.vn           = vnStore->VNZeroForType(op2->TypeGet());
1864         dsc.op2.u1.iconVal   = 0;
1865         dsc.op2.u1.iconFlags = 0;
1866         AssertionIndex index = optAddAssertion(&dsc);
1867         optCreateComplementaryAssertion(index, nullptr, nullptr);
1868         return index;
1869     }
1870     // Cases where op1 holds the lhs of the condition op2 holds rhs.
1871     // Loop condition like "i < 100"
1872     // Assertion: "i < 100 != 0"
1873     else if (vnStore->IsVNConstantBound(relop->gtVNPair.GetConservative()))
1874     {
1875         AssertionDsc dsc;
1876         dsc.assertionKind    = OAK_NOT_EQUAL;
1877         dsc.op1.kind         = O1K_CONSTANT_LOOP_BND;
1878         dsc.op1.vn           = relop->gtVNPair.GetConservative();
1879         dsc.op2.kind         = O2K_CONST_INT;
1880         dsc.op2.vn           = vnStore->VNZeroForType(TYP_INT);
1881         dsc.op2.u1.iconVal   = 0;
1882         dsc.op2.u1.iconFlags = 0;
1883         AssertionIndex index = optAddAssertion(&dsc);
1884         optCreateComplementaryAssertion(index, nullptr, nullptr);
1885         return index;
1886     }
1887
1888     return NO_ASSERTION_INDEX;
1889 }
1890
1891 /*****************************************************************************
1892  *
1893  *  Compute assertions for the JTrue node.
1894  */
1895 AssertionInfo Compiler::optAssertionGenJtrue(GenTree* tree)
1896 {
1897     // Only create assertions for JTRUE when we are in the global phase
1898     if (optLocalAssertionProp)
1899     {
1900         return NO_ASSERTION_INDEX;
1901     }
1902
1903     GenTree* relop = tree->gtOp.gtOp1;
1904     if ((relop->OperKind() & GTK_RELOP) == 0)
1905     {
1906         return NO_ASSERTION_INDEX;
1907     }
1908
1909     Compiler::optAssertionKind assertionKind = OAK_INVALID;
1910
1911     GenTree* op1 = relop->gtOp.gtOp1;
1912     GenTree* op2 = relop->gtOp.gtOp2;
1913
1914     AssertionInfo info = optCreateJTrueBoundsAssertion(tree);
1915     if (info.HasAssertion())
1916     {
1917         return info;
1918     }
1919
1920     // Find assertion kind.
1921     switch (relop->gtOper)
1922     {
1923         case GT_EQ:
1924             assertionKind = OAK_EQUAL;
1925             break;
1926         case GT_NE:
1927             assertionKind = OAK_NOT_EQUAL;
1928             break;
1929         default:
1930             // TODO-CQ: add other relop operands. Disabled for now to measure perf
1931             // and not occupy assertion table slots. We'll add them when used.
1932             return NO_ASSERTION_INDEX;
1933     }
1934
1935     // Check for op1 or op2 to be lcl var and if so, keep it in op1.
1936     if ((op1->gtOper != GT_LCL_VAR) && (op2->gtOper == GT_LCL_VAR))
1937     {
1938         jitstd::swap(op1, op2);
1939     }
1940     // If op1 is lcl and op2 is const or lcl, create assertion.
1941     if ((op1->gtOper == GT_LCL_VAR) &&
1942         ((op2->OperKind() & GTK_CONST) || (op2->gtOper == GT_LCL_VAR))) // Fix for Dev10 851483
1943     {
1944         return optCreateJtrueAssertions(op1, op2, assertionKind);
1945     }
1946
1947     // Check op1 and op2 for an indirection of a GT_LCL_VAR and keep it in op1.
1948     if (((op1->gtOper != GT_IND) || (op1->gtOp.gtOp1->gtOper != GT_LCL_VAR)) &&
1949         ((op2->gtOper == GT_IND) && (op2->gtOp.gtOp1->gtOper == GT_LCL_VAR)))
1950     {
1951         jitstd::swap(op1, op2);
1952     }
1953     // If op1 is ind, then extract op1's oper.
1954     if ((op1->gtOper == GT_IND) && (op1->gtOp.gtOp1->gtOper == GT_LCL_VAR))
1955     {
1956         return optCreateJtrueAssertions(op1, op2, assertionKind);
1957     }
1958
1959     // Look for a call to an IsInstanceOf helper compared to a nullptr
1960     if ((op2->gtOper != GT_CNS_INT) && (op1->gtOper == GT_CNS_INT))
1961     {
1962         jitstd::swap(op1, op2);
1963     }
1964     // Validate op1 and op2
1965     if ((op1->gtOper != GT_CALL) || (op1->gtCall.gtCallType != CT_HELPER) || (op1->TypeGet() != TYP_REF) || // op1
1966         (op2->gtOper != GT_CNS_INT) || (op2->gtIntCon.gtIconVal != 0))                                      // op2
1967     {
1968         return NO_ASSERTION_INDEX;
1969     }
1970     if (op1->gtCall.gtCallMethHnd != eeFindHelper(CORINFO_HELP_ISINSTANCEOFINTERFACE) &&
1971         op1->gtCall.gtCallMethHnd != eeFindHelper(CORINFO_HELP_ISINSTANCEOFARRAY) &&
1972         op1->gtCall.gtCallMethHnd != eeFindHelper(CORINFO_HELP_ISINSTANCEOFCLASS) &&
1973         op1->gtCall.gtCallMethHnd != eeFindHelper(CORINFO_HELP_ISINSTANCEOFANY))
1974     {
1975         return NO_ASSERTION_INDEX;
1976     }
1977
1978     op2 = op1->gtCall.gtCallLateArgs->gtOp.gtOp2;
1979     op1 = op1->gtCall.gtCallLateArgs;
1980
1981     // Reverse the assertion
1982     assert(assertionKind == OAK_EQUAL || assertionKind == OAK_NOT_EQUAL);
1983     assertionKind = (assertionKind == OAK_EQUAL) ? OAK_NOT_EQUAL : OAK_EQUAL;
1984
1985     if (op1->gtOp.gtOp1->gtOper == GT_LCL_VAR)
1986     {
1987         return optCreateJtrueAssertions(op1, op2, assertionKind);
1988     }
1989
1990     return NO_ASSERTION_INDEX;
1991 }
1992
1993 /*****************************************************************************
1994  *
1995  *  Create an assertion on the phi node if some information can be gleaned
1996  *  from all of the constituent phi operands.
1997  *
1998  */
1999 AssertionIndex Compiler::optAssertionGenPhiDefn(GenTree* tree)
2000 {
2001     if (!tree->IsPhiDefn())
2002     {
2003         return NO_ASSERTION_INDEX;
2004     }
2005
2006     GenTree* phi = tree->gtOp.gtOp2;
2007
2008     // Try to find if all phi arguments are known to be non-null.
2009     bool isNonNull = true;
2010     for (GenTreeArgList* args = phi->gtOp.gtOp1->AsArgList(); args != nullptr; args = args->Rest())
2011     {
2012         if (!vnStore->IsKnownNonNull(args->Current()->gtVNPair.GetConservative()))
2013         {
2014             isNonNull = false;
2015             break;
2016         }
2017     }
2018
2019     // All phi arguments are non-null implies phi rhs is non-null.
2020     if (isNonNull)
2021     {
2022         return optCreateAssertion(tree->gtOp.gtOp1, nullptr, OAK_NOT_EQUAL);
2023     }
2024     return NO_ASSERTION_INDEX;
2025 }
2026
2027 /*****************************************************************************
2028  *
2029  *  If this statement creates a value assignment or assertion
2030  *  then assign an index to the given value assignment by adding
2031  *  it to the lookup table, if necessary.
2032  */
2033 void Compiler::optAssertionGen(GenTree* tree)
2034 {
2035     tree->ClearAssertion();
2036
2037     if (tree->gtFlags & GTF_COLON_COND)
2038     {
2039         return;
2040     }
2041
2042 #ifdef DEBUG
2043     optAssertionPropCurrentTree = tree;
2044 #endif
2045
2046     // For most of the assertions that we create below
2047     // the assertion is true after the tree is processed
2048     bool          assertionProven = true;
2049     AssertionInfo assertionInfo;
2050     switch (tree->gtOper)
2051     {
2052         case GT_ASG:
2053             // VN takes care of non local assertions for assignments and data flow.
2054             if (optLocalAssertionProp)
2055             {
2056                 assertionInfo = optCreateAssertion(tree->gtOp.gtOp1, tree->gtOp.gtOp2, OAK_EQUAL);
2057             }
2058             else
2059             {
2060                 assertionInfo = optAssertionGenPhiDefn(tree);
2061             }
2062             break;
2063
2064         case GT_OBJ:
2065         case GT_BLK:
2066         case GT_DYN_BLK:
2067         case GT_IND:
2068         case GT_NULLCHECK:
2069             // All indirections create non-null assertions
2070             assertionInfo = optCreateAssertion(tree->AsIndir()->Addr(), nullptr, OAK_NOT_EQUAL);
2071             break;
2072
2073         case GT_ARR_LENGTH:
2074             // An array length is an indirection (but doesn't derive from GenTreeIndir).
2075             assertionInfo = optCreateAssertion(tree->AsArrLen()->ArrRef(), nullptr, OAK_NOT_EQUAL);
2076             break;
2077
2078         case GT_ARR_BOUNDS_CHECK:
2079             if (!optLocalAssertionProp)
2080             {
2081                 assertionInfo = optCreateAssertion(tree, nullptr, OAK_NO_THROW);
2082             }
2083             break;
2084
2085         case GT_ARR_ELEM:
2086             // An array element reference can create a non-null assertion
2087             assertionInfo = optCreateAssertion(tree->gtArrElem.gtArrObj, nullptr, OAK_NOT_EQUAL);
2088             break;
2089
2090         case GT_CALL:
2091             // A virtual call can create a non-null assertion. We transform some virtual calls into non-virtual calls
2092             // with a GTF_CALL_NULLCHECK flag set.
2093             if ((tree->gtFlags & GTF_CALL_NULLCHECK) || tree->AsCall()->IsVirtual())
2094             {
2095                 //  Retrieve the 'this' arg
2096                 GenTree* thisArg = gtGetThisArg(tree->AsCall());
2097 #if defined(_TARGET_X86_) || defined(_TARGET_AMD64_) || defined(_TARGET_ARM_)
2098                 if (thisArg == nullptr)
2099                 {
2100                     // For tail calls we lose the this pointer in the argument list but that's OK because a null check
2101                     // was made explicit, so we get the assertion when we walk the GT_IND in the argument list.
2102                     noway_assert(tree->gtCall.IsTailCall());
2103                     break;
2104                 }
2105 #endif // _TARGET_X86_ || _TARGET_AMD64_ || _TARGET_ARM_
2106                 noway_assert(thisArg != nullptr);
2107                 assertionInfo = optCreateAssertion(thisArg, nullptr, OAK_NOT_EQUAL);
2108             }
2109             break;
2110
2111         case GT_CAST:
2112             // We only create this assertion for global assertion prop
2113             if (!optLocalAssertionProp)
2114             {
2115                 // This represets an assertion that we would like to prove to be true. It is not actually a true
2116                 // assertion.
2117                 // If we can prove this assertion true then we can eliminate this cast.
2118                 assertionInfo   = optCreateAssertion(tree->gtOp.gtOp1, tree, OAK_SUBRANGE);
2119                 assertionProven = false;
2120             }
2121             break;
2122
2123         case GT_JTRUE:
2124             assertionInfo = optAssertionGenJtrue(tree);
2125             break;
2126
2127         default:
2128             // All other gtOper node kinds, leave 'assertionIndex' = NO_ASSERTION_INDEX
2129             break;
2130     }
2131
2132     // For global assertion prop we must store the assertion number in the tree node
2133     if (assertionInfo.HasAssertion() && assertionProven && !optLocalAssertionProp)
2134     {
2135         tree->SetAssertionInfo(assertionInfo);
2136     }
2137 }
2138
2139 /*****************************************************************************
2140  *
2141  * Maps a complementary assertion to its original assertion so it can be
2142  * retrieved faster.
2143  */
2144 void Compiler::optMapComplementary(AssertionIndex assertionIndex, AssertionIndex index)
2145 {
2146     if (assertionIndex == NO_ASSERTION_INDEX || index == NO_ASSERTION_INDEX)
2147     {
2148         return;
2149     }
2150
2151     assert(assertionIndex <= optMaxAssertionCount);
2152     assert(index <= optMaxAssertionCount);
2153
2154     optComplementaryAssertionMap[assertionIndex] = index;
2155     optComplementaryAssertionMap[index]          = assertionIndex;
2156 }
2157
2158 /*****************************************************************************
2159  *
2160  *  Given an assertion index, return the assertion index of the complementary
2161  *  assertion or 0 if one does not exist.
2162  */
2163 AssertionIndex Compiler::optFindComplementary(AssertionIndex assertIndex)
2164 {
2165     if (assertIndex == NO_ASSERTION_INDEX)
2166     {
2167         return NO_ASSERTION_INDEX;
2168     }
2169     AssertionDsc* inputAssertion = optGetAssertion(assertIndex);
2170
2171     // Must be an equal or not equal assertion.
2172     if (inputAssertion->assertionKind != OAK_EQUAL && inputAssertion->assertionKind != OAK_NOT_EQUAL)
2173     {
2174         return NO_ASSERTION_INDEX;
2175     }
2176
2177     AssertionIndex index = optComplementaryAssertionMap[assertIndex];
2178     if (index != NO_ASSERTION_INDEX && index <= optAssertionCount)
2179     {
2180         return index;
2181     }
2182
2183     optAssertionKind complementaryAssertionKind =
2184         (inputAssertion->assertionKind == OAK_EQUAL) ? OAK_NOT_EQUAL : OAK_EQUAL;
2185     for (AssertionIndex index = 1; index <= optAssertionCount; ++index)
2186     {
2187         // Make sure assertion kinds are complementary and op1, op2 kinds match.
2188         AssertionDsc* curAssertion = optGetAssertion(index);
2189         if (curAssertion->Complementary(inputAssertion, !optLocalAssertionProp))
2190         {
2191             optMapComplementary(assertIndex, index);
2192             return index;
2193         }
2194     }
2195     return NO_ASSERTION_INDEX;
2196 }
2197
2198 /*****************************************************************************
2199  *
2200  *  Given a lclNum and a toType, return assertion index of the assertion that
2201  *  claims that a variable's value is always a valid subrange of toType.
2202  *  Thus we can discard or omit a cast to toType. Returns NO_ASSERTION_INDEX
2203  *  if one such assertion could not be found in "assertions."
2204  */
2205
2206 AssertionIndex Compiler::optAssertionIsSubrange(GenTree* tree, var_types toType, ASSERT_VALARG_TP assertions)
2207 {
2208     if (!optLocalAssertionProp && BitVecOps::IsEmpty(apTraits, assertions))
2209     {
2210         return NO_ASSERTION_INDEX;
2211     }
2212
2213     for (AssertionIndex index = 1; index <= optAssertionCount; index++)
2214     {
2215         AssertionDsc* curAssertion = optGetAssertion(index);
2216         if ((optLocalAssertionProp ||
2217              BitVecOps::IsMember(apTraits, assertions, index - 1)) && // either local prop or use propagated assertions
2218             (curAssertion->assertionKind == OAK_SUBRANGE) &&
2219             (curAssertion->op1.kind == O1K_LCLVAR))
2220         {
2221             // For local assertion prop use comparison on locals, and use comparison on vns for global prop.
2222             bool isEqual = optLocalAssertionProp ? (curAssertion->op1.lcl.lclNum == tree->AsLclVarCommon()->GetLclNum())
2223                                                  : (curAssertion->op1.vn == tree->gtVNPair.GetConservative());
2224             if (!isEqual)
2225             {
2226                 continue;
2227             }
2228
2229             // Make sure the toType is within current assertion's bounds.
2230             switch (toType)
2231             {
2232                 case TYP_BYTE:
2233                 case TYP_UBYTE:
2234                 case TYP_SHORT:
2235                 case TYP_USHORT:
2236                     if ((curAssertion->op2.u2.loBound < AssertionDsc::GetLowerBoundForIntegralType(toType)) ||
2237                         (curAssertion->op2.u2.hiBound > AssertionDsc::GetUpperBoundForIntegralType(toType)))
2238                     {
2239                         continue;
2240                     }
2241                     break;
2242
2243                 case TYP_UINT:
2244                     if (curAssertion->op2.u2.loBound < AssertionDsc::GetLowerBoundForIntegralType(toType))
2245                     {
2246                         continue;
2247                     }
2248                     break;
2249
2250                 case TYP_INT:
2251                     break;
2252
2253                 default:
2254                     continue;
2255             }
2256             return index;
2257         }
2258     }
2259     return NO_ASSERTION_INDEX;
2260 }
2261
2262 /**********************************************************************************
2263  *
2264  * Given a "tree" that is usually arg1 of a isinst/cast kind of GT_CALL (a class
2265  * handle), and "methodTableArg" which is a const int (a class handle), then search
2266  * if there is an assertion in "assertions", that asserts the equality of the two
2267  * class handles and then returns the index of the assertion. If one such assertion
2268  * could not be found, then it returns NO_ASSERTION_INDEX.
2269  *
2270  */
2271 AssertionIndex Compiler::optAssertionIsSubtype(GenTree* tree, GenTree* methodTableArg, ASSERT_VALARG_TP assertions)
2272 {
2273     if (!optLocalAssertionProp && BitVecOps::IsEmpty(apTraits, assertions))
2274     {
2275         return NO_ASSERTION_INDEX;
2276     }
2277     for (AssertionIndex index = 1; index <= optAssertionCount; index++)
2278     {
2279         if (!optLocalAssertionProp && !BitVecOps::IsMember(apTraits, assertions, index - 1))
2280         {
2281             continue;
2282         }
2283
2284         AssertionDsc* curAssertion = optGetAssertion(index);
2285         if (curAssertion->assertionKind != OAK_EQUAL ||
2286             (curAssertion->op1.kind != O1K_SUBTYPE && curAssertion->op1.kind != O1K_EXACT_TYPE))
2287         {
2288             continue;
2289         }
2290
2291         // If local assertion prop use "lcl" based comparison, if global assertion prop use vn based comparison.
2292         if ((optLocalAssertionProp) ? (curAssertion->op1.lcl.lclNum != tree->AsLclVarCommon()->GetLclNum())
2293                                     : (curAssertion->op1.vn != tree->gtVNPair.GetConservative()))
2294         {
2295             continue;
2296         }
2297
2298         if (curAssertion->op2.kind == O2K_IND_CNS_INT)
2299         {
2300             if (methodTableArg->gtOper != GT_IND)
2301             {
2302                 continue;
2303             }
2304             methodTableArg = methodTableArg->gtOp.gtOp1;
2305         }
2306         else if (curAssertion->op2.kind != O2K_CONST_INT)
2307         {
2308             continue;
2309         }
2310
2311         ssize_t  methodTableVal = 0;
2312         unsigned iconFlags      = 0;
2313         if (!optIsTreeKnownIntValue(!optLocalAssertionProp, methodTableArg, &methodTableVal, &iconFlags))
2314         {
2315             continue;
2316         }
2317
2318         if (curAssertion->op2.u1.iconVal == methodTableVal)
2319         {
2320             return index;
2321         }
2322     }
2323     return NO_ASSERTION_INDEX;
2324 }
2325
2326 //------------------------------------------------------------------------------
2327 // optVNConstantPropOnTree: Substitutes tree with an evaluated constant while
2328 //                          managing ref-counts and side-effects.
2329 //
2330 // Arguments:
2331 //    block -  The block containing the tree.
2332 //    stmt  -  The statement in the block containing the tree.
2333 //    tree  -  The tree node whose value is known at compile time.
2334 //             The tree should have a constant value number.
2335 //
2336 // Return Value:
2337 //    Returns a potentially new or a transformed tree node.
2338 //    Returns nullptr when no transformation is possible.
2339 //
2340 // Description:
2341 //    Transforms a tree node if its result evaluates to a constant. The
2342 //    transformation can be a "ChangeOper" to a constant or a new constant node
2343 //    with extracted side-effects.
2344 //
2345 //    Before replacing or substituting the "tree" with a constant, extracts any
2346 //    side effects from the "tree" and creates a comma separated side effect list
2347 //    and then appends the transformed node at the end of the list.
2348 //    This comma separated list is then returned.
2349 //
2350 //    For JTrue nodes, side effects are not put into a comma separated list. If
2351 //    the relop will evaluate to "true" or "false" statically, then the side-effects
2352 //    will be put into new statements, presuming the JTrue will be folded away.
2353 //
2354 //    The ref-counts of any variables in the tree being replaced, will be
2355 //    appropriately decremented. The ref-counts of variables in the side-effect
2356 //    nodes will be retained.
2357 //
2358 GenTree* Compiler::optVNConstantPropOnTree(BasicBlock* block, GenTree* stmt, GenTree* tree)
2359 {
2360     if (tree->OperGet() == GT_JTRUE)
2361     {
2362         // Treat JTRUE separately to extract side effects into respective statements rather
2363         // than using a COMMA separated op1.
2364         return optVNConstantPropOnJTrue(block, stmt, tree);
2365     }
2366     // If relop is part of JTRUE, this should be optimized as part of the parent JTRUE.
2367     // Or if relop is part of QMARK or anything else, we simply bail here.
2368     else if (tree->OperIsCompare() && (tree->gtFlags & GTF_RELOP_JMP_USED))
2369     {
2370         return nullptr;
2371     }
2372
2373     ValueNum vnCns = tree->gtVNPair.GetConservative();
2374     ValueNum vnLib = tree->gtVNPair.GetLiberal();
2375
2376     // Check if node evaluates to a constant.
2377     if (!vnStore->IsVNConstant(vnCns))
2378     {
2379         return nullptr;
2380     }
2381
2382     GenTree* newTree     = tree;
2383     GenTree* sideEffList = nullptr;
2384     switch (vnStore->TypeOfVN(vnCns))
2385     {
2386         case TYP_FLOAT:
2387         {
2388             float value = vnStore->ConstantValue<float>(vnCns);
2389
2390             if (tree->TypeGet() == TYP_INT)
2391             {
2392                 // Same sized reinterpretation of bits to integer
2393                 newTree = optPrepareTreeForReplacement(tree, tree);
2394                 tree->ChangeOperConst(GT_CNS_INT);
2395                 tree->gtIntCon.gtIconVal = *(reinterpret_cast<int*>(&value));
2396                 tree->gtVNPair           = ValueNumPair(vnLib, vnCns);
2397             }
2398             else
2399             {
2400                 // Implicit assignment conversion to float or double
2401                 assert(varTypeIsFloating(tree->TypeGet()));
2402
2403                 newTree = optPrepareTreeForReplacement(tree, tree);
2404                 tree->ChangeOperConst(GT_CNS_DBL);
2405                 tree->gtDblCon.gtDconVal = value;
2406                 tree->gtVNPair           = ValueNumPair(vnLib, vnCns);
2407             }
2408             break;
2409         }
2410
2411         case TYP_DOUBLE:
2412         {
2413             double value = vnStore->ConstantValue<double>(vnCns);
2414
2415             if (tree->TypeGet() == TYP_LONG)
2416             {
2417                 // Same sized reinterpretation of bits to long
2418                 newTree = optPrepareTreeForReplacement(tree, tree);
2419                 tree->ChangeOperConst(GT_CNS_NATIVELONG);
2420                 tree->gtIntConCommon.SetLngValue(*(reinterpret_cast<INT64*>(&value)));
2421                 tree->gtVNPair = ValueNumPair(vnLib, vnCns);
2422             }
2423             else
2424             {
2425                 // Implicit assignment conversion to float or double
2426                 assert(varTypeIsFloating(tree->TypeGet()));
2427
2428                 newTree = optPrepareTreeForReplacement(tree, tree);
2429                 tree->ChangeOperConst(GT_CNS_DBL);
2430                 tree->gtDblCon.gtDconVal = value;
2431                 tree->gtVNPair           = ValueNumPair(vnLib, vnCns);
2432             }
2433             break;
2434         }
2435
2436         case TYP_LONG:
2437         {
2438             INT64 value = vnStore->ConstantValue<INT64>(vnCns);
2439 #ifdef _TARGET_64BIT_
2440             if (vnStore->IsVNHandle(vnCns))
2441             {
2442                 // Don't perform constant folding that involves a handle that needs
2443                 // to be recorded as a relocation with the VM.
2444                 if (!opts.compReloc)
2445                 {
2446                     newTree           = gtNewIconHandleNode(value, vnStore->GetHandleFlags(vnCns));
2447                     newTree->gtVNPair = ValueNumPair(vnLib, vnCns);
2448                     newTree           = optPrepareTreeForReplacement(tree, newTree);
2449                 }
2450             }
2451             else
2452 #endif
2453             {
2454                 switch (tree->TypeGet())
2455                 {
2456                     case TYP_INT:
2457                         // Implicit assignment conversion to smaller integer
2458                         newTree = optPrepareTreeForReplacement(tree, tree);
2459                         tree->ChangeOperConst(GT_CNS_INT);
2460                         tree->gtIntCon.gtIconVal = (int)value;
2461                         tree->gtVNPair           = ValueNumPair(vnLib, vnCns);
2462                         break;
2463
2464                     case TYP_LONG:
2465                         // Same type no conversion required
2466                         newTree = optPrepareTreeForReplacement(tree, tree);
2467                         tree->ChangeOperConst(GT_CNS_NATIVELONG);
2468                         tree->gtIntConCommon.SetLngValue(value);
2469                         tree->gtVNPair = ValueNumPair(vnLib, vnCns);
2470                         break;
2471
2472                     case TYP_FLOAT:
2473                         // No implicit conversions from long to float and value numbering will
2474                         // not propagate through memory reinterpretations of different size.
2475                         unreached();
2476                         break;
2477
2478                     case TYP_DOUBLE:
2479                         // Same sized reinterpretation of bits to double
2480                         newTree = optPrepareTreeForReplacement(tree, tree);
2481                         tree->ChangeOperConst(GT_CNS_DBL);
2482                         tree->gtDblCon.gtDconVal = *(reinterpret_cast<double*>(&value));
2483                         tree->gtVNPair           = ValueNumPair(vnLib, vnCns);
2484                         break;
2485
2486                     default:
2487                         return nullptr;
2488                 }
2489             }
2490         }
2491         break;
2492
2493         case TYP_REF:
2494             if (tree->TypeGet() != TYP_REF)
2495             {
2496                 return nullptr;
2497             }
2498
2499             assert(vnStore->ConstantValue<size_t>(vnCns) == 0);
2500             newTree = optPrepareTreeForReplacement(tree, tree);
2501             tree->ChangeOperConst(GT_CNS_INT);
2502             tree->gtIntCon.gtIconVal = 0;
2503             tree->ClearIconHandleMask();
2504             tree->gtVNPair = ValueNumPair(vnLib, vnCns);
2505             break;
2506
2507         case TYP_INT:
2508         {
2509             int value = vnStore->ConstantValue<int>(vnCns);
2510 #ifndef _TARGET_64BIT_
2511             if (vnStore->IsVNHandle(vnCns))
2512             {
2513                 // Don't perform constant folding that involves a handle that needs
2514                 // to be recorded as a relocation with the VM.
2515                 if (!opts.compReloc)
2516                 {
2517                     newTree           = gtNewIconHandleNode(value, vnStore->GetHandleFlags(vnCns));
2518                     newTree->gtVNPair = ValueNumPair(vnLib, vnCns);
2519                     newTree           = optPrepareTreeForReplacement(tree, newTree);
2520                 }
2521             }
2522             else
2523 #endif
2524             {
2525                 switch (tree->TypeGet())
2526                 {
2527                     case TYP_REF:
2528                     case TYP_INT:
2529                         // Same type no conversion required
2530                         newTree = optPrepareTreeForReplacement(tree, tree);
2531                         tree->ChangeOperConst(GT_CNS_INT);
2532                         tree->gtIntCon.gtIconVal = value;
2533                         tree->ClearIconHandleMask();
2534                         tree->gtVNPair = ValueNumPair(vnLib, vnCns);
2535                         break;
2536
2537                     case TYP_LONG:
2538                         // Implicit assignment conversion to larger integer
2539                         newTree = optPrepareTreeForReplacement(tree, tree);
2540                         tree->ChangeOperConst(GT_CNS_NATIVELONG);
2541                         tree->gtIntConCommon.SetLngValue(value);
2542                         tree->gtVNPair = ValueNumPair(vnLib, vnCns);
2543                         break;
2544
2545                     case TYP_FLOAT:
2546                         // Same sized reinterpretation of bits to float
2547                         newTree = optPrepareTreeForReplacement(tree, tree);
2548                         tree->ChangeOperConst(GT_CNS_DBL);
2549                         tree->gtDblCon.gtDconVal = *(reinterpret_cast<float*>(&value));
2550                         tree->gtVNPair           = ValueNumPair(vnLib, vnCns);
2551                         break;
2552
2553                     case TYP_DOUBLE:
2554                         // No implicit conversions from int to double and value numbering will
2555                         // not propagate through memory reinterpretations of different size.
2556                         unreached();
2557                         break;
2558
2559                     default:
2560                         return nullptr;
2561                 }
2562             }
2563         }
2564         break;
2565
2566         default:
2567             return nullptr;
2568     }
2569     return newTree;
2570 }
2571
2572 /*******************************************************************************************************
2573  *
2574  * Perform constant propagation on a tree given the "curAssertion" is true at the point of the "tree."
2575  *
2576  */
2577 GenTree* Compiler::optConstantAssertionProp(AssertionDsc* curAssertion,
2578                                             GenTree*      tree,
2579                                             GenTree* stmt DEBUGARG(AssertionIndex index))
2580 {
2581     unsigned lclNum = tree->gtLclVarCommon.gtLclNum;
2582
2583     if (lclNumIsCSE(lclNum))
2584     {
2585         return nullptr;
2586     }
2587
2588     GenTree* newTree = tree;
2589
2590     // Update 'newTree' with the new value from our table
2591     // Typically newTree == tree and we are updating the node in place
2592     switch (curAssertion->op2.kind)
2593     {
2594         case O2K_CONST_DOUBLE:
2595             // There could be a positive zero and a negative zero, so don't propagate zeroes.
2596             if (curAssertion->op2.dconVal == 0.0)
2597             {
2598                 return nullptr;
2599             }
2600             newTree->ChangeOperConst(GT_CNS_DBL);
2601             newTree->gtDblCon.gtDconVal = curAssertion->op2.dconVal;
2602             break;
2603
2604         case O2K_CONST_LONG:
2605             if (newTree->gtType == TYP_LONG)
2606             {
2607                 newTree->ChangeOperConst(GT_CNS_NATIVELONG);
2608                 newTree->gtIntConCommon.SetLngValue(curAssertion->op2.lconVal);
2609             }
2610             else
2611             {
2612                 newTree->ChangeOperConst(GT_CNS_INT);
2613                 newTree->gtIntCon.gtIconVal = (int)curAssertion->op2.lconVal;
2614                 newTree->gtType             = TYP_INT;
2615             }
2616             break;
2617
2618         case O2K_CONST_INT:
2619             if (curAssertion->op2.u1.iconFlags & GTF_ICON_HDL_MASK)
2620             {
2621                 // Here we have to allocate a new 'large' node to replace the old one
2622                 newTree = gtNewIconHandleNode(curAssertion->op2.u1.iconVal,
2623                                               curAssertion->op2.u1.iconFlags & GTF_ICON_HDL_MASK);
2624             }
2625             else
2626             {
2627                 bool isArrIndex = ((tree->gtFlags & GTF_VAR_ARR_INDEX) != 0);
2628                 // If we have done constant propagation of a struct type, it is only valid for zero-init,
2629                 // and we have to ensure that we have the right zero for the type.
2630                 if (varTypeIsStruct(tree))
2631                 {
2632                     assert(curAssertion->op2.u1.iconVal == 0);
2633                 }
2634 #ifdef FEATURE_SIMD
2635                 if (varTypeIsSIMD(tree))
2636                 {
2637                     var_types simdType = tree->TypeGet();
2638                     tree->ChangeOperConst(GT_CNS_DBL);
2639                     GenTree* initVal = tree;
2640                     initVal->gtType  = TYP_FLOAT;
2641                     newTree =
2642                         gtNewSIMDNode(simdType, initVal, nullptr, SIMDIntrinsicInit, TYP_FLOAT, genTypeSize(simdType));
2643                 }
2644                 else
2645 #endif // FEATURE_SIMD
2646                 {
2647                     newTree->ChangeOperConst(GT_CNS_INT);
2648                     newTree->gtIntCon.gtIconVal = curAssertion->op2.u1.iconVal;
2649                     newTree->ClearIconHandleMask();
2650                 }
2651                 // If we're doing an array index address, assume any constant propagated contributes to the index.
2652                 if (isArrIndex)
2653                 {
2654                     newTree->gtIntCon.gtFieldSeq =
2655                         GetFieldSeqStore()->CreateSingleton(FieldSeqStore::ConstantIndexPseudoField);
2656                 }
2657                 newTree->gtFlags &= ~GTF_VAR_ARR_INDEX;
2658             }
2659
2660             // Constant ints are of type TYP_INT, not any of the short forms.
2661             if (varTypeIsIntegral(newTree->TypeGet()))
2662             {
2663 #ifdef _TARGET_64BIT_
2664                 var_types newType = (var_types)((curAssertion->op2.u1.iconFlags & 1) ? TYP_LONG : TYP_INT);
2665                 if (newTree->TypeGet() != newType)
2666                 {
2667                     noway_assert(newTree->gtType != TYP_REF);
2668                     newTree->gtType = newType;
2669                 }
2670 #else
2671                 if (newTree->TypeGet() != TYP_INT)
2672                 {
2673                     noway_assert(newTree->gtType != TYP_REF && newTree->gtType != TYP_LONG);
2674                     newTree->gtType = TYP_INT;
2675                 }
2676 #endif
2677             }
2678             break;
2679
2680         default:
2681             return nullptr;
2682     }
2683
2684     if (!optLocalAssertionProp)
2685     {
2686         assert(newTree->OperIsConst());                      // We should have a simple Constant node for newTree
2687         assert(vnStore->IsVNConstant(curAssertion->op2.vn)); // The value number stored for op2 should be a valid
2688                                                              // VN representing the constant
2689         newTree->gtVNPair.SetBoth(curAssertion->op2.vn);     // Set the ValueNumPair to the constant VN from op2
2690                                                              // of the assertion
2691     }
2692
2693 #ifdef DEBUG
2694     if (verbose)
2695     {
2696         printf("\nAssertion prop in BB%02u:\n", compCurBB->bbNum);
2697         optPrintAssertion(curAssertion, index);
2698         gtDispTree(newTree, nullptr, nullptr, true);
2699     }
2700 #endif
2701     if (lvaLocalVarRefCounted)
2702     {
2703         lvaTable[lclNum].decRefCnts(compCurBB->getBBWeight(this), this);
2704     }
2705
2706     return optAssertionProp_Update(newTree, tree, stmt);
2707 }
2708
2709 /*******************************************************************************************************
2710  *
2711  *  Called in the context of an existing copy assertion which makes an "==" assertion on "lclVar" and
2712  *  "copyVar." Before substituting "copyVar" for "lclVar", we make sure using "copy" doesn't widen access.
2713  *
2714  */
2715 bool Compiler::optAssertionProp_LclVarTypeCheck(GenTree* tree, LclVarDsc* lclVarDsc, LclVarDsc* copyVarDsc)
2716 {
2717     /*
2718         Small struct field locals are stored using the exact width and loaded widened
2719         (i.e. lvNormalizeOnStore==false   lvNormalizeOnLoad==true),
2720         because the field locals might end up embedded in the parent struct local with the exact width.
2721
2722             In other words, a store to a short field local should always done using an exact width store
2723
2724                 [00254538] 0x0009 ------------               const     int    0x1234
2725             [002545B8] 0x000B -A--G--NR---               =         short
2726                 [00254570] 0x000A D------N----               lclVar    short  V43 tmp40
2727
2728             mov   word  ptr [L_043], 0x1234
2729
2730         Now, if we copy prop, say a short field local V43, to another short local V34
2731         for the following tree:
2732
2733                 [04E18650] 0x0001 ------------               lclVar    int   V34 tmp31
2734             [04E19714] 0x0002 -A----------               =         int
2735                 [04E196DC] 0x0001 D------N----               lclVar    int   V36 tmp33
2736
2737         We will end with this tree:
2738
2739                 [04E18650] 0x0001 ------------               lclVar    int   V43 tmp40
2740             [04E19714] 0x0002 -A-----NR---               =         int
2741                 [04E196DC] 0x0001 D------N----               lclVar    int   V36 tmp33    EAX
2742
2743         And eventually causing a fetch of 4-byte out from [L_043] :(
2744             mov     EAX, dword ptr [L_043]
2745
2746         The following check is to make sure we only perform the copy prop
2747         when we don't retrieve the wider value.
2748     */
2749
2750     if (copyVarDsc->lvIsStructField)
2751     {
2752         var_types varType = (var_types)copyVarDsc->lvType;
2753         // Make sure we don't retrieve the wider value.
2754         return !varTypeIsSmall(varType) || (varType == tree->TypeGet());
2755     }
2756     // Called in the context of a single copy assertion, so the types should have been
2757     // taken care by the assertion gen logic for other cases. Just return true.
2758     return true;
2759 }
2760
2761 /**********************************************************************************
2762  *
2763  *  Perform copy assertion propagation when the lclNum and ssaNum of the "tree" match
2764  *  the "curAssertion."
2765  *
2766  */
2767 GenTree* Compiler::optCopyAssertionProp(AssertionDsc* curAssertion,
2768                                         GenTree*      tree,
2769                                         GenTree* stmt DEBUGARG(AssertionIndex index))
2770 {
2771     const AssertionDsc::AssertionDscOp1& op1 = curAssertion->op1;
2772     const AssertionDsc::AssertionDscOp2& op2 = curAssertion->op2;
2773
2774     noway_assert(op1.lcl.lclNum != op2.lcl.lclNum);
2775
2776     unsigned lclNum = tree->gtLclVarCommon.GetLclNum();
2777
2778     // Make sure one of the lclNum of the assertion matches with that of the tree.
2779     if (op1.lcl.lclNum != lclNum && op2.lcl.lclNum != lclNum)
2780     {
2781         return nullptr;
2782     }
2783
2784     // Extract the matching lclNum and ssaNum.
2785     unsigned copyLclNum = (op1.lcl.lclNum == lclNum) ? op2.lcl.lclNum : op1.lcl.lclNum;
2786     unsigned copySsaNum = BAD_VAR_NUM;
2787     if (!optLocalAssertionProp)
2788     {
2789         // Extract the ssaNum of the matching lclNum.
2790         unsigned ssaNum = (op1.lcl.lclNum == lclNum) ? op1.lcl.ssaNum : op2.lcl.ssaNum;
2791         copySsaNum      = (op1.lcl.lclNum == lclNum) ? op2.lcl.ssaNum : op1.lcl.ssaNum;
2792
2793         if (ssaNum != tree->AsLclVarCommon()->GetSsaNum())
2794         {
2795             return nullptr;
2796         }
2797     }
2798
2799     LclVarDsc* copyVarDsc = &lvaTable[copyLclNum];
2800     LclVarDsc* lclVarDsc  = &lvaTable[lclNum];
2801
2802     // Make sure the types are compatible.
2803     if (!optAssertionProp_LclVarTypeCheck(tree, lclVarDsc, copyVarDsc))
2804     {
2805         return nullptr;
2806     }
2807
2808     // Make sure we can perform this copy prop.
2809     if (optCopyProp_LclVarScore(lclVarDsc, copyVarDsc, curAssertion->op1.lcl.lclNum == lclNum) <= 0)
2810     {
2811         return nullptr;
2812     }
2813
2814     // If global assertion prop, by now we should have ref counts, fix them.
2815     if (lvaLocalVarRefCounted)
2816     {
2817         lvaTable[lclNum].decRefCnts(compCurBB->getBBWeight(this), this);
2818         lvaTable[copyLclNum].incRefCnts(compCurBB->getBBWeight(this), this);
2819         tree->gtLclVarCommon.SetSsaNum(copySsaNum);
2820     }
2821     tree->gtLclVarCommon.SetLclNum(copyLclNum);
2822
2823 #ifdef DEBUG
2824     if (verbose)
2825     {
2826         printf("\nAssertion prop in BB%02u:\n", compCurBB->bbNum);
2827         optPrintAssertion(curAssertion, index);
2828         gtDispTree(tree, nullptr, nullptr, true);
2829     }
2830 #endif
2831
2832     // Update and morph the tree.
2833     return optAssertionProp_Update(tree, tree, stmt);
2834 }
2835
2836 /*****************************************************************************
2837  *
2838  *  Given a tree consisting of a just a LclVar and a set of available assertions
2839  *  we try to propagate an assertion and modify the LclVar tree if we can.
2840  *  We pass in the root of the tree via 'stmt', for local copy prop 'stmt' will
2841  *  be nullptr. Returns the modified tree, or nullptr if no assertion prop took place.
2842  */
2843
2844 GenTree* Compiler::optAssertionProp_LclVar(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
2845 {
2846     assert(tree->gtOper == GT_LCL_VAR);
2847     // If we have a var definition then bail or
2848     // If this is the address of the var then it will have the GTF_DONT_CSE
2849     // flag set and we don't want to to assertion prop on it.
2850     if (tree->gtFlags & (GTF_VAR_DEF | GTF_DONT_CSE))
2851     {
2852         return nullptr;
2853     }
2854
2855     BitVecOps::Iter iter(apTraits, assertions);
2856     unsigned        index = 0;
2857     while (iter.NextElem(&index))
2858     {
2859         AssertionIndex assertionIndex = GetAssertionIndex(index);
2860         if (assertionIndex > optAssertionCount)
2861         {
2862             break;
2863         }
2864         // See if the variable is equal to a constant or another variable.
2865         AssertionDsc* curAssertion = optGetAssertion(assertionIndex);
2866         if (curAssertion->assertionKind != OAK_EQUAL || curAssertion->op1.kind != O1K_LCLVAR)
2867         {
2868             continue;
2869         }
2870
2871         // Copy prop.
2872         if (curAssertion->op2.kind == O2K_LCLVAR_COPY)
2873         {
2874             // Cannot do copy prop during global assertion prop because of no knowledge
2875             // of kill sets. We will still make a == b copy assertions during the global phase to allow
2876             // for any implied assertions that can be retrieved. Because implied assertions look for
2877             // matching SSA numbers (i.e., if a0 == b1 and b1 == c0 then a0 == c0) they don't need kill sets.
2878             if (optLocalAssertionProp)
2879             {
2880                 // Perform copy assertion prop.
2881                 GenTree* newTree = optCopyAssertionProp(curAssertion, tree, stmt DEBUGARG(assertionIndex));
2882                 if (newTree == nullptr)
2883                 {
2884                     // Skip and try next assertion.
2885                     continue;
2886                 }
2887                 return newTree;
2888             }
2889         }
2890         // Constant prop (for local assertion prop.)
2891         // The case where the tree type could be different than the LclVar type is caused by
2892         // gtFoldExpr, specifically the case of a cast, where the fold operation changes the type of the LclVar
2893         // node.  In such a case is not safe to perform the substitution since later on the JIT will assert mismatching
2894         // types between trees.
2895         else if (curAssertion->op1.lcl.lclNum == tree->gtLclVarCommon.GetLclNum() &&
2896                  tree->gtType == lvaTable[tree->gtLclVarCommon.GetLclNum()].lvType)
2897         {
2898             // If local assertion prop just, perform constant prop.
2899             if (optLocalAssertionProp)
2900             {
2901                 return optConstantAssertionProp(curAssertion, tree, stmt DEBUGARG(assertionIndex));
2902             }
2903             // If global assertion, perform constant propagation only if the VN's match and the lcl is non-CSE.
2904             else if (curAssertion->op1.vn == tree->gtVNPair.GetConservative())
2905             {
2906 #if FEATURE_ANYCSE
2907                 // Don't perform constant prop for CSE LclVars
2908                 if (!lclNumIsCSE(tree->AsLclVarCommon()->GetLclNum()))
2909 #endif
2910                 {
2911                     return optConstantAssertionProp(curAssertion, tree, stmt DEBUGARG(assertionIndex));
2912                 }
2913             }
2914         }
2915     }
2916     return nullptr;
2917 }
2918
2919 /*****************************************************************************
2920  *
2921  *  Given a set of "assertions" to search, find an assertion that matches
2922  *  op1Kind and lclNum, op2Kind and the constant value and is either equal or
2923  *  not equal assertion.
2924  */
2925 AssertionIndex Compiler::optLocalAssertionIsEqualOrNotEqual(
2926     optOp1Kind op1Kind, unsigned lclNum, optOp2Kind op2Kind, ssize_t cnsVal, ASSERT_VALARG_TP assertions)
2927 {
2928     noway_assert((op1Kind == O1K_LCLVAR) || (op1Kind == O1K_EXACT_TYPE) || (op1Kind == O1K_SUBTYPE));
2929     noway_assert((op2Kind == O2K_CONST_INT) || (op2Kind == O2K_IND_CNS_INT));
2930     if (!optLocalAssertionProp && BitVecOps::IsEmpty(apTraits, assertions))
2931     {
2932         return NO_ASSERTION_INDEX;
2933     }
2934
2935     for (AssertionIndex index = 1; index <= optAssertionCount; ++index)
2936     {
2937         AssertionDsc* curAssertion = optGetAssertion(index);
2938         if (optLocalAssertionProp || BitVecOps::IsMember(apTraits, assertions, index - 1))
2939         {
2940             if ((curAssertion->assertionKind != OAK_EQUAL) && (curAssertion->assertionKind != OAK_NOT_EQUAL))
2941             {
2942                 continue;
2943             }
2944
2945             if ((curAssertion->op1.kind == op1Kind) && (curAssertion->op1.lcl.lclNum == lclNum) &&
2946                 (curAssertion->op2.kind == op2Kind))
2947             {
2948                 bool constantIsEqual  = (curAssertion->op2.u1.iconVal == cnsVal);
2949                 bool assertionIsEqual = (curAssertion->assertionKind == OAK_EQUAL);
2950
2951                 if (constantIsEqual || assertionIsEqual)
2952                 {
2953                     return index;
2954                 }
2955             }
2956         }
2957     }
2958     return NO_ASSERTION_INDEX;
2959 }
2960
2961 /*****************************************************************************
2962  *
2963  *  Given a set of "assertions" to search for, find an assertion that is either
2964  *  "op1" == "op2" or "op1" != "op2." Does a value number based comparison.
2965  *
2966  */
2967 AssertionIndex Compiler::optGlobalAssertionIsEqualOrNotEqual(ASSERT_VALARG_TP assertions, GenTree* op1, GenTree* op2)
2968 {
2969     if (BitVecOps::IsEmpty(apTraits, assertions))
2970     {
2971         return NO_ASSERTION_INDEX;
2972     }
2973     BitVecOps::Iter iter(apTraits, assertions);
2974     unsigned        index = 0;
2975     while (iter.NextElem(&index))
2976     {
2977         AssertionIndex assertionIndex = GetAssertionIndex(index);
2978         if (assertionIndex > optAssertionCount)
2979         {
2980             break;
2981         }
2982         AssertionDsc* curAssertion = optGetAssertion(assertionIndex);
2983         if ((curAssertion->assertionKind != OAK_EQUAL && curAssertion->assertionKind != OAK_NOT_EQUAL))
2984         {
2985             continue;
2986         }
2987
2988         if (curAssertion->op1.vn == op1->gtVNPair.GetConservative() &&
2989             curAssertion->op2.vn == op2->gtVNPair.GetConservative())
2990         {
2991             return assertionIndex;
2992         }
2993     }
2994     return NO_ASSERTION_INDEX;
2995 }
2996
2997 /*****************************************************************************
2998  *
2999  *  Given a tree consisting of a RelOp and a set of available assertions
3000  *  we try to propagate an assertion and modify the RelOp tree if we can.
3001  *  We pass in the root of the tree via 'stmt', for local copy prop 'stmt' will be nullptr
3002  *  Returns the modified tree, or nullptr if no assertion prop took place
3003  */
3004
3005 GenTree* Compiler::optAssertionProp_RelOp(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
3006 {
3007     assert(tree->OperKind() & GTK_RELOP);
3008
3009     //
3010     // Currently only GT_EQ or GT_NE are supported Relops for AssertionProp
3011     //
3012     if ((tree->gtOper != GT_EQ) && (tree->gtOper != GT_NE))
3013     {
3014         return nullptr;
3015     }
3016
3017     if (!optLocalAssertionProp)
3018     {
3019         // If global assertion prop then use value numbering.
3020         return optAssertionPropGlobal_RelOp(assertions, tree, stmt);
3021     }
3022     else
3023     {
3024         // If local assertion prop then use variable based prop.
3025         return optAssertionPropLocal_RelOp(assertions, tree, stmt);
3026     }
3027 }
3028
3029 /*************************************************************************************
3030  *
3031  *  Given the set of "assertions" to look up a relop assertion about the relop "tree",
3032  *  perform Value numbering based relop assertion propagation on the tree.
3033  *
3034  */
3035 GenTree* Compiler::optAssertionPropGlobal_RelOp(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
3036 {
3037     assert(tree->OperGet() == GT_EQ || tree->OperGet() == GT_NE);
3038
3039     GenTree* newTree = tree;
3040     GenTree* op1     = tree->gtOp.gtOp1;
3041     GenTree* op2     = tree->gtOp.gtOp2;
3042
3043     if (op1->gtOper != GT_LCL_VAR)
3044     {
3045         return nullptr;
3046     }
3047
3048     // Find an equal or not equal assertion involving "op1" and "op2".
3049     AssertionIndex index = optGlobalAssertionIsEqualOrNotEqual(assertions, op1, op2);
3050     if (index == NO_ASSERTION_INDEX)
3051     {
3052         return nullptr;
3053     }
3054
3055     AssertionDsc* curAssertion = optGetAssertion(index);
3056
3057     // Allow or not to reverse condition for OAK_NOT_EQUAL assertions.
3058     bool allowReverse = true;
3059
3060     // If the assertion involves "op2" and it is a constant, then check if "op1" also has a constant value.
3061     if (vnStore->IsVNConstant(op2->gtVNPair.GetConservative()))
3062     {
3063         ValueNum vnCns = op2->gtVNPair.GetConservative();
3064 #ifdef DEBUG
3065         if (verbose)
3066         {
3067             printf("\nVN relop based constant assertion prop in BB%02u:\n", compCurBB->bbNum);
3068             printf("Assertion index=#%02u: ", index);
3069             printTreeID(op1);
3070             printf(" %s ", (curAssertion->assertionKind == OAK_EQUAL) ? "==" : "!=");
3071             if (genActualType(op1->TypeGet()) == TYP_INT)
3072             {
3073                 printf("%d\n", vnStore->ConstantValue<int>(vnCns));
3074             }
3075             else if (op1->TypeGet() == TYP_LONG)
3076             {
3077                 printf("%I64d\n", vnStore->ConstantValue<INT64>(vnCns));
3078             }
3079             else if (op1->TypeGet() == TYP_DOUBLE)
3080             {
3081                 printf("%f\n", vnStore->ConstantValue<double>(vnCns));
3082             }
3083             else if (op1->TypeGet() == TYP_FLOAT)
3084             {
3085                 printf("%f\n", vnStore->ConstantValue<float>(vnCns));
3086             }
3087             else if (op1->TypeGet() == TYP_REF)
3088             {
3089                 // The only constant of TYP_REF that ValueNumbering supports is 'null'
3090                 assert(vnStore->ConstantValue<size_t>(vnCns) == 0);
3091                 printf("null\n");
3092             }
3093             else
3094             {
3095                 printf("??unknown\n");
3096             }
3097             gtDispTree(tree, nullptr, nullptr, true);
3098         }
3099 #endif
3100         // Decrement the ref counts, before we change the oper.
3101         lvaTable[op1->gtLclVar.gtLclNum].decRefCnts(compCurBB->getBBWeight(this), this);
3102
3103         // Change the oper to const.
3104         if (genActualType(op1->TypeGet()) == TYP_INT)
3105         {
3106             op1->ChangeOperConst(GT_CNS_INT);
3107             op1->gtIntCon.gtIconVal = vnStore->ConstantValue<int>(vnCns);
3108         }
3109         else if (op1->TypeGet() == TYP_LONG)
3110         {
3111             op1->ChangeOperConst(GT_CNS_NATIVELONG);
3112             op1->gtIntConCommon.SetLngValue(vnStore->ConstantValue<INT64>(vnCns));
3113         }
3114         else if (op1->TypeGet() == TYP_DOUBLE)
3115         {
3116             double constant = vnStore->ConstantValue<double>(vnCns);
3117             op1->ChangeOperConst(GT_CNS_DBL);
3118             op1->gtDblCon.gtDconVal = constant;
3119
3120             // Nothing can be equal to NaN. So if IL had "op1 == NaN", then we already made op1 NaN,
3121             // which will yield a false correctly. Instead if IL had "op1 != NaN", then we already
3122             // made op1 NaN which will yield a true correctly. Note that this is irrespective of the
3123             // assertion we have made.
3124             allowReverse = (_isnan(constant) == 0);
3125         }
3126         else if (op1->TypeGet() == TYP_FLOAT)
3127         {
3128             float constant = vnStore->ConstantValue<float>(vnCns);
3129             op1->ChangeOperConst(GT_CNS_DBL);
3130             op1->gtDblCon.gtDconVal = constant;
3131             // See comments for TYP_DOUBLE.
3132             allowReverse = (_isnan(constant) == 0);
3133         }
3134         else if (op1->TypeGet() == TYP_REF)
3135         {
3136             op1->ChangeOperConst(GT_CNS_INT);
3137             // The only constant of TYP_REF that ValueNumbering supports is 'null'
3138             noway_assert(vnStore->ConstantValue<size_t>(vnCns) == 0);
3139             op1->gtIntCon.gtIconVal = 0;
3140         }
3141         else
3142         {
3143             noway_assert(!"unknown type in Global_RelOp");
3144         }
3145
3146         op1->gtVNPair.SetBoth(vnCns); // Preserve the ValueNumPair, as ChangeOperConst/SetOper will clear it.
3147     }
3148     // If the assertion involves "op2" and "op1" is also a local var, then just morph the tree.
3149     else if (op2->gtOper == GT_LCL_VAR)
3150     {
3151 #ifdef DEBUG
3152         if (verbose)
3153         {
3154             printf("\nVN relop based copy assertion prop in BB%02u:\n", compCurBB->bbNum);
3155             printf("Assertion index=#%02u: V%02d.%02d %s V%02d.%02d\n", index, op1->gtLclVar.gtLclNum,
3156                    op1->gtLclVar.gtSsaNum, (curAssertion->assertionKind == OAK_EQUAL) ? "==" : "!=",
3157                    op2->gtLclVar.gtLclNum, op2->gtLclVar.gtSsaNum);
3158             gtDispTree(tree, nullptr, nullptr, true);
3159         }
3160 #endif
3161         lvaTable[op1->gtLclVar.gtLclNum].decRefCnts(compCurBB->getBBWeight(this), this);
3162
3163         // If floating point, don't just substitute op1 with op2, this won't work if
3164         // op2 is NaN. Just turn it into a "true" or "false" yielding expression.
3165         if (op1->TypeGet() == TYP_DOUBLE || op1->TypeGet() == TYP_FLOAT)
3166         {
3167             // Note we can't trust the OAK_EQUAL as the value could end up being a NaN
3168             // violating the assertion. However, we create OAK_EQUAL assertions for floating
3169             // point only on JTrue nodes, so if the condition held earlier, it will hold
3170             // now. We don't create OAK_EQUAL assertion on floating point from GT_ASG
3171             // because we depend on value num which would constant prop the NaN.
3172             lvaTable[op2->gtLclVar.gtLclNum].decRefCnts(compCurBB->getBBWeight(this), this);
3173             op1->ChangeOperConst(GT_CNS_DBL);
3174             op1->gtDblCon.gtDconVal = 0;
3175             op2->ChangeOperConst(GT_CNS_DBL);
3176             op2->gtDblCon.gtDconVal = 0;
3177         }
3178         // Change the op1 LclVar to the op2 LclVar
3179         else
3180         {
3181             noway_assert(varTypeIsIntegralOrI(op1->TypeGet()));
3182             lvaTable[op2->gtLclVar.gtLclNum].incRefCnts(compCurBB->getBBWeight(this), this);
3183             op1->AsLclVarCommon()->SetLclNum(op2->AsLclVarCommon()->GetLclNum());
3184             op1->AsLclVarCommon()->SetSsaNum(op2->AsLclVarCommon()->GetSsaNum());
3185         }
3186     }
3187     else
3188     {
3189         return nullptr;
3190     }
3191
3192     // Finally reverse the condition, if we have a not equal assertion.
3193     if (allowReverse && curAssertion->assertionKind == OAK_NOT_EQUAL)
3194     {
3195         gtReverseCond(tree);
3196     }
3197
3198     newTree = fgMorphTree(tree);
3199
3200 #ifdef DEBUG
3201     if (verbose)
3202     {
3203         gtDispTree(newTree, nullptr, nullptr, true);
3204     }
3205 #endif
3206
3207     return optAssertionProp_Update(newTree, tree, stmt);
3208 }
3209
3210 /*************************************************************************************
3211  *
3212  *  Given the set of "assertions" to look up a relop assertion about the relop "tree",
3213  *  perform local variable name based relop assertion propagation on the tree.
3214  *
3215  */
3216 GenTree* Compiler::optAssertionPropLocal_RelOp(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
3217 {
3218     assert(tree->OperGet() == GT_EQ || tree->OperGet() == GT_NE);
3219
3220     GenTree* op1 = tree->gtOp.gtOp1;
3221     GenTree* op2 = tree->gtOp.gtOp2;
3222
3223     // For Local AssertionProp we only can fold when op1 is a GT_LCL_VAR
3224     if (op1->gtOper != GT_LCL_VAR)
3225     {
3226         return nullptr;
3227     }
3228
3229     // For Local AssertionProp we only can fold when op2 is a GT_CNS_INT
3230     if (op2->gtOper != GT_CNS_INT)
3231     {
3232         return nullptr;
3233     }
3234
3235     optOp1Kind op1Kind = O1K_LCLVAR;
3236     optOp2Kind op2Kind = O2K_CONST_INT;
3237     ssize_t    cnsVal  = op2->gtIntCon.gtIconVal;
3238     var_types  cmpType = op1->TypeGet();
3239
3240     // Don't try to fold/optimize Floating Compares; there are multiple zero values.
3241     if (varTypeIsFloating(cmpType))
3242     {
3243         return nullptr;
3244     }
3245
3246     // Find an equal or not equal assertion about op1 var.
3247     unsigned lclNum = op1->gtLclVarCommon.gtLclNum;
3248     noway_assert(lclNum < lvaCount);
3249     AssertionIndex index = optLocalAssertionIsEqualOrNotEqual(op1Kind, lclNum, op2Kind, cnsVal, assertions);
3250
3251     if (index == NO_ASSERTION_INDEX)
3252     {
3253         return nullptr;
3254     }
3255
3256     AssertionDsc* curAssertion = optGetAssertion(index);
3257
3258     bool assertionKindIsEqual = (curAssertion->assertionKind == OAK_EQUAL);
3259     bool constantIsEqual      = false;
3260
3261     if (genTypeSize(cmpType) == TARGET_POINTER_SIZE)
3262     {
3263         constantIsEqual = (curAssertion->op2.u1.iconVal == cnsVal);
3264     }
3265 #ifdef _TARGET_64BIT_
3266     else if (genTypeSize(cmpType) == sizeof(INT32))
3267     {
3268         // Compare the low 32-bits only
3269         constantIsEqual = (((INT32)curAssertion->op2.u1.iconVal) == ((INT32)cnsVal));
3270     }
3271 #endif
3272     else
3273     {
3274         // We currently don't fold/optimze when the GT_LCL_VAR has been cast to a small type
3275         return nullptr;
3276     }
3277
3278     noway_assert(constantIsEqual || assertionKindIsEqual);
3279
3280 #ifdef DEBUG
3281     if (verbose)
3282     {
3283         printf("\nAssertion prop for index #%02u in BB%02u:\n", index, compCurBB->bbNum);
3284         gtDispTree(tree, nullptr, nullptr, true);
3285     }
3286 #endif
3287
3288     // Return either CNS_INT 0 or CNS_INT 1.
3289     bool foldResult = (constantIsEqual == assertionKindIsEqual);
3290     if (tree->gtOper == GT_NE)
3291     {
3292         foldResult = !foldResult;
3293     }
3294
3295     op2->gtIntCon.gtIconVal = foldResult;
3296     op2->gtType             = TYP_INT;
3297
3298     return optAssertionProp_Update(op2, tree, stmt);
3299 }
3300
3301 /*****************************************************************************
3302  *
3303  *  Given a tree consisting of a Cast and a set of available assertions
3304  *  we try to propagate an assertion and modify the Cast tree if we can.
3305  *  We pass in the root of the tree via 'stmt', for local copy prop 'stmt'
3306  *  will be nullptr.
3307  *
3308  *  Returns the modified tree, or nullptr if no assertion prop took place.
3309  */
3310 GenTree* Compiler::optAssertionProp_Cast(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
3311 {
3312     assert(tree->gtOper == GT_CAST);
3313
3314     var_types toType = tree->gtCast.gtCastType;
3315     GenTree*  op1    = tree->gtCast.CastOp();
3316
3317     // If we have a cast involving floating point types, then bail.
3318     if (varTypeIsFloating(toType) || varTypeIsFloating(op1->TypeGet()))
3319     {
3320         return nullptr;
3321     }
3322
3323     // Skip over a GT_COMMA node(s), if necessary to get to the lcl.
3324     GenTree* lcl = op1;
3325     while (lcl->gtOper == GT_COMMA)
3326     {
3327         lcl = lcl->gtOp.gtOp2;
3328     }
3329
3330     // If we don't have a cast of a LCL_VAR then bail.
3331     if (lcl->gtOper != GT_LCL_VAR)
3332     {
3333         return nullptr;
3334     }
3335
3336     AssertionIndex index = optAssertionIsSubrange(lcl, toType, assertions);
3337     if (index != NO_ASSERTION_INDEX)
3338     {
3339         LclVarDsc* varDsc = &lvaTable[lcl->gtLclVarCommon.gtLclNum];
3340         if (varDsc->lvNormalizeOnLoad() || varTypeIsLong(varDsc->TypeGet()))
3341         {
3342             // For normalize on load variables it must be a narrowing cast to remove
3343             if (genTypeSize(toType) > genTypeSize(varDsc->TypeGet()))
3344             {
3345                 // Can we just remove the GTF_OVERFLOW flag?
3346                 if ((tree->gtFlags & GTF_OVERFLOW) == 0)
3347                 {
3348                     return nullptr;
3349                 }
3350                 else
3351                 {
3352
3353 #ifdef DEBUG
3354                     if (verbose)
3355                     {
3356                         printf("\nSubrange prop for index #%02u in BB%02u:\n", index, compCurBB->bbNum);
3357                         gtDispTree(tree, nullptr, nullptr, true);
3358                     }
3359 #endif
3360                     tree->gtFlags &= ~GTF_OVERFLOW; // This cast cannot overflow
3361                     return optAssertionProp_Update(tree, tree, stmt);
3362                 }
3363             }
3364
3365             //             GT_CAST   long -> uint -> int
3366             //                |
3367             //           GT_LCL_VAR long
3368             //
3369             // Where the lclvar is known to be in the range of [0..MAX_UINT]
3370             //
3371             // A load of a 32-bit unsigned int is the same as a load of a 32-bit signed int
3372             //
3373             if (toType == TYP_UINT)
3374             {
3375                 toType = TYP_INT;
3376             }
3377
3378             // Change the "lcl" type to match what the cast wanted, by propagating the type
3379             // change down the comma nodes leading to the "lcl", if we skipped them earlier.
3380             GenTree* tmp = op1;
3381             while (tmp->gtOper == GT_COMMA)
3382             {
3383                 tmp->gtType = toType;
3384                 tmp         = tmp->gtOp.gtOp2;
3385             }
3386             noway_assert(tmp == lcl);
3387             tmp->gtType = toType;
3388         }
3389
3390 #ifdef DEBUG
3391         if (verbose)
3392         {
3393             printf("\nSubrange prop for index #%02u in BB%02u:\n", index, compCurBB->bbNum);
3394             gtDispTree(tree, nullptr, nullptr, true);
3395         }
3396 #endif
3397         return optAssertionProp_Update(op1, tree, stmt);
3398     }
3399     return nullptr;
3400 }
3401
3402 /*****************************************************************************
3403  *
3404  *  Given a tree with an array bounds check node, eliminate it because it was
3405  *  checked already in the program.
3406  */
3407 GenTree* Compiler::optAssertionProp_Comma(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
3408 {
3409     // Remove the bounds check as part of the GT_COMMA node since we need parent pointer to remove nodes.
3410     // When processing visits the bounds check, it sets the throw kind to None if the check is redundant.
3411     if ((tree->gtGetOp1()->OperGet() == GT_ARR_BOUNDS_CHECK) &&
3412         ((tree->gtGetOp1()->gtFlags & GTF_ARR_BOUND_INBND) != 0))
3413     {
3414         optRemoveRangeCheck(tree, stmt);
3415         return optAssertionProp_Update(tree, tree, stmt);
3416     }
3417     return nullptr;
3418 }
3419
3420 /*****************************************************************************
3421  *
3422  *  Given a tree consisting of a Ind and a set of available assertions, we try
3423  *  to propagate an assertion and modify the Ind tree if we can. We pass in the
3424  *  root of the tree via 'stmt', for local copy prop 'stmt' will be nullptr.
3425  *
3426  *  Returns the modified tree, or nullptr if no assertion prop took place.
3427  *
3428  */
3429
3430 GenTree* Compiler::optAssertionProp_Ind(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
3431 {
3432     assert(tree->OperIsIndir());
3433
3434     if (!(tree->gtFlags & GTF_EXCEPT))
3435     {
3436         return nullptr;
3437     }
3438
3439     // Check for add of a constant.
3440     GenTree* op1 = tree->AsIndir()->Addr();
3441     if ((op1->gtOper == GT_ADD) && (op1->gtOp.gtOp2->gtOper == GT_CNS_INT))
3442     {
3443         op1 = op1->gtOp.gtOp1;
3444     }
3445
3446     if (op1->gtOper != GT_LCL_VAR)
3447     {
3448         return nullptr;
3449     }
3450
3451     unsigned lclNum = op1->gtLclVarCommon.gtLclNum;
3452
3453 #ifdef DEBUG
3454     bool           vnBased = false;
3455     AssertionIndex index   = NO_ASSERTION_INDEX;
3456 #endif
3457     if (optAssertionIsNonNull(op1, assertions DEBUGARG(&vnBased) DEBUGARG(&index)))
3458     {
3459 #ifdef DEBUG
3460         if (verbose)
3461         {
3462             (vnBased) ? printf("\nVN based non-null prop in BB%02u:\n", compCurBB->bbNum)
3463                       : printf("\nNon-null prop for index #%02u in BB%02u:\n", index, compCurBB->bbNum);
3464             gtDispTree(tree, nullptr, nullptr, true);
3465         }
3466 #endif
3467         tree->gtFlags &= ~GTF_EXCEPT;
3468         tree->gtFlags |= GTF_IND_NONFAULTING;
3469
3470         // Set this flag to prevent reordering
3471         tree->gtFlags |= GTF_ORDER_SIDEEFF;
3472
3473         return optAssertionProp_Update(tree, tree, stmt);
3474     }
3475
3476     return nullptr;
3477 }
3478
3479 /*****************************************************************************
3480  *  Check if a non-null assertion can be made about the input operand "op"
3481  *  from the set of "assertions," or implicitly from the value number on "op."
3482  *
3483  *  Sets "pVnBased" if the assertion is value number based. If no matching
3484  *  assertions are found from the table, then returns "NO_ASSERTION_INDEX."
3485  *
3486  *  Note: If both VN and assertion table yield a matching assertion, "pVnBased"
3487  *  is only set and the return value is "NO_ASSERTION_INDEX."
3488  */
3489 bool Compiler::optAssertionIsNonNull(GenTree*         op,
3490                                      ASSERT_VALARG_TP assertions DEBUGARG(bool* pVnBased)
3491                                          DEBUGARG(AssertionIndex* pIndex))
3492 {
3493     bool vnBased = (!optLocalAssertionProp && vnStore->IsKnownNonNull(op->gtVNPair.GetConservative()));
3494 #ifdef DEBUG
3495     *pVnBased = vnBased;
3496 #endif
3497
3498     if (vnBased)
3499     {
3500 #ifdef DEBUG
3501         *pIndex = NO_ASSERTION_INDEX;
3502 #endif
3503         return true;
3504     }
3505
3506     AssertionIndex index = optAssertionIsNonNullInternal(op, assertions);
3507 #ifdef DEBUG
3508     *pIndex = index;
3509 #endif
3510     return index != NO_ASSERTION_INDEX;
3511 }
3512
3513 /*****************************************************************************
3514  *  Check if a non-null assertion can be made about the input operand "op"
3515  *  from the set of "assertions."
3516  *
3517  */
3518 AssertionIndex Compiler::optAssertionIsNonNullInternal(GenTree* op, ASSERT_VALARG_TP assertions)
3519 {
3520     // If local assertion prop use lcl comparison, else use VN comparison.
3521     if (!optLocalAssertionProp)
3522     {
3523         if (BitVecOps::MayBeUninit(assertions) || BitVecOps::IsEmpty(apTraits, assertions))
3524         {
3525             return NO_ASSERTION_INDEX;
3526         }
3527
3528         ValueNum vn = op->gtVNPair.GetConservative();
3529
3530         // Check each assertion to find if we have a vn == or != null assertion.
3531         BitVecOps::Iter iter(apTraits, assertions);
3532         unsigned        index = 0;
3533         while (iter.NextElem(&index))
3534         {
3535             AssertionIndex assertionIndex = GetAssertionIndex(index);
3536             if (assertionIndex > optAssertionCount)
3537             {
3538                 break;
3539             }
3540             AssertionDsc* curAssertion = optGetAssertion(assertionIndex);
3541             if (curAssertion->assertionKind != OAK_NOT_EQUAL)
3542             {
3543                 continue;
3544             }
3545             if (curAssertion->op1.vn != vn || curAssertion->op2.vn != ValueNumStore::VNForNull())
3546             {
3547                 continue;
3548             }
3549             return assertionIndex;
3550         }
3551     }
3552     else
3553     {
3554         unsigned lclNum = op->AsLclVarCommon()->GetLclNum();
3555         // Check each assertion to find if we have a variable == or != null assertion.
3556         for (AssertionIndex index = 1; index <= optAssertionCount; index++)
3557         {
3558             AssertionDsc* curAssertion = optGetAssertion(index);
3559             if ((curAssertion->assertionKind == OAK_NOT_EQUAL) && // kind
3560                 (curAssertion->op1.kind == O1K_LCLVAR) &&         // op1
3561                 (curAssertion->op2.kind == O2K_CONST_INT) &&      // op2
3562                 (curAssertion->op1.lcl.lclNum == lclNum) && (curAssertion->op2.u1.iconVal == 0))
3563             {
3564                 return index;
3565             }
3566         }
3567     }
3568     return NO_ASSERTION_INDEX;
3569 }
3570 /*****************************************************************************
3571  *
3572  *  Given a tree consisting of a call and a set of available assertions, we
3573  *  try to propagate a non-null assertion and modify the Call tree if we can.
3574  *  Returns the modified tree, or nullptr if no assertion prop took place.
3575  *
3576  */
3577 GenTree* Compiler::optNonNullAssertionProp_Call(ASSERT_VALARG_TP assertions, GenTreeCall* call, GenTree* stmt)
3578 {
3579     if ((call->gtFlags & GTF_CALL_NULLCHECK) == 0)
3580     {
3581         return nullptr;
3582     }
3583     GenTree* op1 = gtGetThisArg(call);
3584     noway_assert(op1 != nullptr);
3585     if (op1->gtOper != GT_LCL_VAR)
3586     {
3587         return nullptr;
3588     }
3589
3590 #ifdef DEBUG
3591     bool           vnBased = false;
3592     AssertionIndex index   = NO_ASSERTION_INDEX;
3593 #endif
3594     if (optAssertionIsNonNull(op1, assertions DEBUGARG(&vnBased) DEBUGARG(&index)))
3595     {
3596 #ifdef DEBUG
3597         if (verbose)
3598         {
3599             (vnBased) ? printf("\nVN based non-null prop in BB%02u:\n", compCurBB->bbNum)
3600                       : printf("\nNon-null prop for index #%02u in BB%02u:\n", index, compCurBB->bbNum);
3601             gtDispTree(call, nullptr, nullptr, true);
3602         }
3603 #endif
3604         call->gtFlags &= ~GTF_CALL_NULLCHECK;
3605         call->gtFlags &= ~GTF_EXCEPT;
3606         noway_assert(call->gtFlags & GTF_SIDE_EFFECT);
3607         return call;
3608     }
3609     return nullptr;
3610 }
3611
3612 /*****************************************************************************
3613  *
3614  *  Given a tree consisting of a call and a set of available assertions, we
3615  *  try to propagate an assertion and modify the Call tree if we can. Our
3616  *  current modifications are limited to removing the nullptrCHECK flag from
3617  *  the call.
3618  *  We pass in the root of the tree via 'stmt', for local copy prop 'stmt'
3619  *  will be nullptr. Returns the modified tree, or nullptr if no assertion prop
3620  *  took place.
3621  *
3622  */
3623
3624 GenTree* Compiler::optAssertionProp_Call(ASSERT_VALARG_TP assertions, GenTreeCall* call, GenTree* stmt)
3625 {
3626     if (optNonNullAssertionProp_Call(assertions, call, stmt))
3627     {
3628         return optAssertionProp_Update(call, call, stmt);
3629     }
3630     else if (!optLocalAssertionProp && (call->gtCallType == CT_HELPER))
3631     {
3632         if (call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_ISINSTANCEOFINTERFACE) ||
3633             call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_ISINSTANCEOFARRAY) ||
3634             call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_ISINSTANCEOFCLASS) ||
3635             call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_ISINSTANCEOFANY) ||
3636             call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_CHKCASTINTERFACE) ||
3637             call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_CHKCASTARRAY) ||
3638             call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_CHKCASTCLASS) ||
3639             call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_CHKCASTANY) ||
3640             call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_CHKCASTCLASS_SPECIAL))
3641         {
3642             GenTree* arg1 = gtArgEntryByArgNum(call, 1)->node;
3643             if (arg1->gtOper != GT_LCL_VAR)
3644             {
3645                 return nullptr;
3646             }
3647
3648             GenTree* arg2 = gtArgEntryByArgNum(call, 0)->node;
3649
3650             unsigned index = optAssertionIsSubtype(arg1, arg2, assertions);
3651             if (index != NO_ASSERTION_INDEX)
3652             {
3653 #ifdef DEBUG
3654                 if (verbose)
3655                 {
3656                     printf("\nDid VN based subtype prop for index #%02u in BB%02u:\n", index, compCurBB->bbNum);
3657                     gtDispTree(call, nullptr, nullptr, true);
3658                 }
3659 #endif
3660                 GenTree* list = nullptr;
3661                 gtExtractSideEffList(call, &list, GTF_SIDE_EFFECT, true);
3662                 if (list != nullptr)
3663                 {
3664                     arg1 = gtNewOperNode(GT_COMMA, call->TypeGet(), list, arg1);
3665                     fgSetTreeSeq(arg1);
3666                 }
3667
3668                 return optAssertionProp_Update(arg1, call, stmt);
3669             }
3670         }
3671     }
3672
3673     return nullptr;
3674 }
3675
3676 /*****************************************************************************
3677  *
3678  *  Given a tree consisting of a comma node with a bounds check, remove any
3679  *  redundant bounds check that has already been checked in the program flow.
3680  */
3681 GenTree* Compiler::optAssertionProp_BndsChk(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
3682 {
3683     if (optLocalAssertionProp)
3684     {
3685         return nullptr;
3686     }
3687
3688     assert(tree->gtOper == GT_ARR_BOUNDS_CHECK);
3689
3690 #ifdef FEATURE_ENABLE_NO_RANGE_CHECKS
3691     if (JitConfig.JitNoRangeChks())
3692     {
3693 #ifdef DEBUG
3694         if (verbose)
3695         {
3696             printf("\nFlagging check redundant due to JitNoRangeChks in BB%02u:\n", compCurBB->bbNum);
3697             gtDispTree(tree, nullptr, nullptr, true);
3698         }
3699 #endif // DEBUG
3700         tree->gtFlags |= GTF_ARR_BOUND_INBND;
3701         return nullptr;
3702     }
3703 #endif // FEATURE_ENABLE_NO_RANGE_CHECKS
3704
3705     BitVecOps::Iter iter(apTraits, assertions);
3706     unsigned        index = 0;
3707     while (iter.NextElem(&index))
3708     {
3709         AssertionIndex assertionIndex = GetAssertionIndex(index);
3710         if (assertionIndex > optAssertionCount)
3711         {
3712             break;
3713         }
3714         // If it is not a nothrow assertion, skip.
3715         AssertionDsc* curAssertion = optGetAssertion(assertionIndex);
3716         if (!curAssertion->IsBoundsCheckNoThrow())
3717         {
3718             continue;
3719         }
3720
3721         GenTreeBoundsChk* arrBndsChk = tree->AsBoundsChk();
3722
3723         // Set 'isRedundant' to true if we can determine that 'arrBndsChk' can be
3724         // classified as a redundant bounds check using 'curAssertion'
3725         bool isRedundant = false;
3726 #ifdef DEBUG
3727         const char* dbgMsg = "Not Set";
3728 #endif
3729
3730         // Do we have a previous range check involving the same 'vnLen' upper bound?
3731         if (curAssertion->op1.bnd.vnLen == arrBndsChk->gtArrLen->gtVNPair.GetConservative())
3732         {
3733             ValueNum vnCurIdx = arrBndsChk->gtIndex->gtVNPair.GetConservative();
3734
3735             // Do we have the exact same lower bound 'vnIdx'?
3736             //       a[i] followed by a[i]
3737             if (curAssertion->op1.bnd.vnIdx == vnCurIdx)
3738             {
3739                 isRedundant = true;
3740 #ifdef DEBUG
3741                 dbgMsg = "a[i] followed by a[i]";
3742 #endif
3743             }
3744             // Are we using zero as the index?
3745             // It can always be considered as redundant with any previous value
3746             //       a[*] followed by a[0]
3747             else if (vnCurIdx == vnStore->VNZeroForType(arrBndsChk->gtIndex->TypeGet()))
3748             {
3749                 isRedundant = true;
3750 #ifdef DEBUG
3751                 dbgMsg = "a[*] followed by a[0]";
3752 #endif
3753             }
3754             // Do we have two constant indexes?
3755             else if (vnStore->IsVNConstant(curAssertion->op1.bnd.vnIdx) && vnStore->IsVNConstant(vnCurIdx))
3756             {
3757                 // Make sure the types match.
3758                 var_types type1 = vnStore->TypeOfVN(curAssertion->op1.bnd.vnIdx);
3759                 var_types type2 = vnStore->TypeOfVN(vnCurIdx);
3760
3761                 if (type1 == type2 && type1 == TYP_INT)
3762                 {
3763                     int index1 = vnStore->ConstantValue<int>(curAssertion->op1.bnd.vnIdx);
3764                     int index2 = vnStore->ConstantValue<int>(vnCurIdx);
3765
3766                     // the case where index1 == index2 should have been handled above
3767                     assert(index1 != index2);
3768
3769                     // It can always be considered as redundant with any previous higher constant value
3770                     //       a[K1] followed by a[K2], with K2 >= 0 and K1 >= K2
3771                     if (index2 >= 0 && index1 >= index2)
3772                     {
3773                         isRedundant = true;
3774 #ifdef DEBUG
3775                         dbgMsg = "a[K1] followed by a[K2], with K2 >= 0 and K1 >= K2";
3776 #endif
3777                     }
3778                 }
3779             }
3780             // Extend this to remove additional redundant bounds checks:
3781             // i.e.  a[i+1] followed by a[i]  by using the VN(i+1) >= VN(i)
3782             //       a[i]   followed by a[j]  when j is known to be >= i
3783             //       a[i]   followed by a[5]  when i is known to be >= 5
3784         }
3785
3786         if (!isRedundant)
3787         {
3788             continue;
3789         }
3790
3791 #ifdef DEBUG
3792         if (verbose)
3793         {
3794             printf("\nVN based redundant (%s) bounds check assertion prop for index #%02u in BB%02u:\n", dbgMsg,
3795                    assertionIndex, compCurBB->bbNum);
3796             gtDispTree(tree, nullptr, nullptr, true);
3797         }
3798 #endif
3799
3800         // Defer actually removing the tree until processing reaches its parent comma, since
3801         // optRemoveRangeCheck needs to rewrite the whole comma tree.
3802         arrBndsChk->gtFlags |= GTF_ARR_BOUND_INBND;
3803         return nullptr;
3804     }
3805     return nullptr;
3806 }
3807
3808 /*****************************************************************************
3809  *
3810  *  Called when we have a successfully performed an assertion prop. We have
3811  *  the newTree in hand. This method will replace the existing tree in the
3812  *  stmt with the newTree.
3813  *
3814  */
3815
3816 GenTree* Compiler::optAssertionProp_Update(GenTree* newTree, GenTree* tree, GenTree* stmt)
3817 {
3818     noway_assert(newTree != nullptr);
3819
3820     if (stmt == nullptr)
3821     {
3822         noway_assert(optLocalAssertionProp);
3823     }
3824     else
3825     {
3826         noway_assert(!optLocalAssertionProp);
3827
3828         // If newTree == tree then we modified the tree in-place otherwise we have to
3829         // locate our parent node and update it so that it points to newTree
3830         if (newTree != tree)
3831         {
3832             GenTree** link = gtFindLink(stmt, tree);
3833 #ifdef DEBUG
3834             if (link == nullptr)
3835             {
3836                 noway_assert(!"gtFindLink failed!");
3837                 printf("\nCould not find parent of:\n");
3838                 gtDispTree(tree);
3839                 printf("\nIn this stmt:\n");
3840                 gtDispTree(stmt);
3841             }
3842 #endif
3843             noway_assert(link != nullptr);
3844             noway_assert(tree != nullptr);
3845             if (link != nullptr)
3846             {
3847                 // Replace the old operand with the newTree
3848                 *link = newTree;
3849
3850                 // We only need to ensure that the gtNext field is set as it is used to traverse
3851                 // to the next node in the tree. We will re-morph this entire statement in
3852                 // optAssertionPropMain(). It will reset the gtPrev and gtNext links for all nodes.
3853
3854                 newTree->gtNext = tree->gtNext;
3855             }
3856         }
3857     }
3858
3859     // Record that we propagated the assertion.
3860     optAssertionPropagated            = true;
3861     optAssertionPropagatedCurrentStmt = true;
3862
3863     return newTree;
3864 }
3865
3866 /*****************************************************************************
3867  *
3868  *  Given a tree and a set of available assertions we try to propagate an
3869  *  assertion and modify 'tree' if we can. We pass in the root of the tree
3870  *  via 'stmt', for local copy prop 'stmt' will be nullptr.
3871  *
3872  *  Returns the modified tree, or nullptr if no assertion prop took place.
3873  */
3874
3875 GenTree* Compiler::optAssertionProp(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
3876 {
3877     switch (tree->gtOper)
3878     {
3879         case GT_LCL_VAR:
3880             return optAssertionProp_LclVar(assertions, tree, stmt);
3881
3882         case GT_OBJ:
3883         case GT_BLK:
3884         case GT_DYN_BLK:
3885         case GT_IND:
3886         case GT_NULLCHECK:
3887             return optAssertionProp_Ind(assertions, tree, stmt);
3888
3889         case GT_ARR_BOUNDS_CHECK:
3890             return optAssertionProp_BndsChk(assertions, tree, stmt);
3891
3892         case GT_COMMA:
3893             return optAssertionProp_Comma(assertions, tree, stmt);
3894
3895         case GT_CAST:
3896             return optAssertionProp_Cast(assertions, tree, stmt);
3897
3898         case GT_CALL:
3899             return optAssertionProp_Call(assertions, tree->AsCall(), stmt);
3900
3901         case GT_EQ:
3902         case GT_NE:
3903         case GT_LT:
3904         case GT_LE:
3905         case GT_GT:
3906         case GT_GE:
3907
3908             return optAssertionProp_RelOp(assertions, tree, stmt);
3909
3910         default:
3911             return nullptr;
3912     }
3913 }
3914
3915 //------------------------------------------------------------------------
3916 // optImpliedAssertions: Given a tree node that makes an assertion this
3917 //                       method computes the set of implied assertions
3918 //                       that are also true. The updated assertions are
3919 //                       maintained on the Compiler object.
3920 //
3921 // Arguments:
3922 //      assertionIndex   : The id of the assertion.
3923 //      activeAssertions : The assertions that are already true at this point.
3924
3925 void Compiler::optImpliedAssertions(AssertionIndex assertionIndex, ASSERT_TP& activeAssertions)
3926 {
3927     noway_assert(!optLocalAssertionProp);
3928     noway_assert(assertionIndex != 0);
3929     noway_assert(assertionIndex <= optAssertionCount);
3930
3931     AssertionDsc* curAssertion = optGetAssertion(assertionIndex);
3932     if (!BitVecOps::IsEmpty(apTraits, activeAssertions))
3933     {
3934         const ASSERT_TP mappedAssertions = optGetVnMappedAssertions(curAssertion->op1.vn);
3935         if (mappedAssertions == nullptr)
3936         {
3937             return;
3938         }
3939
3940         ASSERT_TP chkAssertions = BitVecOps::MakeCopy(apTraits, mappedAssertions);
3941
3942         if (curAssertion->op2.kind == O2K_LCLVAR_COPY)
3943         {
3944             const ASSERT_TP op2Assertions = optGetVnMappedAssertions(curAssertion->op2.vn);
3945             if (op2Assertions != nullptr)
3946             {
3947                 BitVecOps::UnionD(apTraits, chkAssertions, op2Assertions);
3948             }
3949         }
3950         BitVecOps::IntersectionD(apTraits, chkAssertions, activeAssertions);
3951
3952         if (BitVecOps::IsEmpty(apTraits, chkAssertions))
3953         {
3954             return;
3955         }
3956
3957         // Check each assertion in chkAssertions to see if it can be applied to curAssertion
3958         BitVecOps::Iter chkIter(apTraits, chkAssertions);
3959         unsigned        chkIndex = 0;
3960         while (chkIter.NextElem(&chkIndex))
3961         {
3962             AssertionIndex chkAssertionIndex = GetAssertionIndex(chkIndex);
3963             if (chkAssertionIndex > optAssertionCount)
3964             {
3965                 break;
3966             }
3967             if (chkAssertionIndex == assertionIndex)
3968             {
3969                 continue;
3970             }
3971
3972             // Determine which one is a copy assertion and use the other to check for implied assertions.
3973             AssertionDsc* iterAssertion = optGetAssertion(chkAssertionIndex);
3974             if (curAssertion->IsCopyAssertion())
3975             {
3976                 optImpliedByCopyAssertion(curAssertion, iterAssertion, activeAssertions);
3977             }
3978             else if (iterAssertion->IsCopyAssertion())
3979             {
3980                 optImpliedByCopyAssertion(iterAssertion, curAssertion, activeAssertions);
3981             }
3982         }
3983     }
3984     // Is curAssertion a constant assignment of a 32-bit integer?
3985     // (i.e  GT_LVL_VAR X  == GT_CNS_INT)
3986     else if ((curAssertion->assertionKind == OAK_EQUAL) && (curAssertion->op1.kind == O1K_LCLVAR) &&
3987              (curAssertion->op2.kind == O2K_CONST_INT))
3988     {
3989         optImpliedByConstAssertion(curAssertion, activeAssertions);
3990     }
3991 }
3992
3993 /*****************************************************************************
3994  *
3995  *   Given a set of active assertions this method computes the set
3996  *   of non-Null implied assertions that are also true
3997  */
3998
3999 void Compiler::optImpliedByTypeOfAssertions(ASSERT_TP& activeAssertions)
4000 {
4001     if (BitVecOps::IsEmpty(apTraits, activeAssertions))
4002     {
4003         return;
4004     }
4005
4006     // Check each assertion in activeAssertions to see if it can be applied to constAssertion
4007     BitVecOps::Iter chkIter(apTraits, activeAssertions);
4008     unsigned        chkIndex = 0;
4009     while (chkIter.NextElem(&chkIndex))
4010     {
4011         AssertionIndex chkAssertionIndex = GetAssertionIndex(chkIndex);
4012         if (chkAssertionIndex > optAssertionCount)
4013         {
4014             break;
4015         }
4016         // chkAssertion must be Type/Subtype is equal assertion
4017         AssertionDsc* chkAssertion = optGetAssertion(chkAssertionIndex);
4018         if ((chkAssertion->op1.kind != O1K_SUBTYPE && chkAssertion->op1.kind != O1K_EXACT_TYPE) ||
4019             (chkAssertion->assertionKind != OAK_EQUAL))
4020         {
4021             continue;
4022         }
4023
4024         // Search the assertion table for a non-null assertion on op1 that matches chkAssertion
4025         for (AssertionIndex impIndex = 1; impIndex <= optAssertionCount; impIndex++)
4026         {
4027             AssertionDsc* impAssertion = optGetAssertion(impIndex);
4028
4029             //  The impAssertion must be different from the chkAssertion
4030             if (impIndex == chkAssertionIndex)
4031             {
4032                 continue;
4033             }
4034
4035             // impAssertion must be a Non Null assertion on lclNum
4036             if ((impAssertion->assertionKind != OAK_NOT_EQUAL) ||
4037                 ((impAssertion->op1.kind != O1K_LCLVAR) && (impAssertion->op1.kind != O1K_VALUE_NUMBER)) ||
4038                 (impAssertion->op2.kind != O2K_CONST_INT) || (impAssertion->op1.vn != chkAssertion->op1.vn))
4039             {
4040                 continue;
4041             }
4042
4043             // The bit may already be in the result set
4044             if (!BitVecOps::IsMember(apTraits, activeAssertions, impIndex - 1))
4045             {
4046                 BitVecOps::AddElemD(apTraits, activeAssertions, impIndex - 1);
4047 #ifdef DEBUG
4048                 if (verbose)
4049                 {
4050                     printf("\nCompiler::optImpliedByTypeOfAssertions: %s Assertion #%02d, implies assertion #%02d",
4051                            (chkAssertion->op1.kind == O1K_SUBTYPE) ? "Subtype" : "Exact-type", chkAssertionIndex,
4052                            impIndex);
4053                 }
4054 #endif
4055             }
4056
4057             // There is at most one non-null assertion that is implied by the current chkIndex assertion
4058             break;
4059         }
4060     }
4061 }
4062
4063 //------------------------------------------------------------------------
4064 // optGetVnMappedAssertions: Given a value number, get the assertions
4065 //                           we have about the value number.
4066 //
4067 // Arguments:
4068 //      vn - The given value number.
4069 //
4070 // Return Value:
4071 //      The assertions we have about the value number.
4072 //
4073
4074 ASSERT_VALRET_TP Compiler::optGetVnMappedAssertions(ValueNum vn)
4075 {
4076     ASSERT_TP set = BitVecOps::UninitVal();
4077     if (optValueNumToAsserts->Lookup(vn, &set))
4078     {
4079         return set;
4080     }
4081     return BitVecOps::UninitVal();
4082 }
4083
4084 /*****************************************************************************
4085  *
4086  *   Given a const assertion this method computes the set of implied assertions
4087  *   that are also true
4088  */
4089
4090 void Compiler::optImpliedByConstAssertion(AssertionDsc* constAssertion, ASSERT_TP& result)
4091 {
4092     noway_assert(constAssertion->assertionKind == OAK_EQUAL);
4093     noway_assert(constAssertion->op1.kind == O1K_LCLVAR);
4094     noway_assert(constAssertion->op2.kind == O2K_CONST_INT);
4095
4096     ssize_t iconVal = constAssertion->op2.u1.iconVal;
4097
4098     const ASSERT_TP chkAssertions = optGetVnMappedAssertions(constAssertion->op1.vn);
4099     if (chkAssertions == nullptr || BitVecOps::IsEmpty(apTraits, chkAssertions))
4100     {
4101         return;
4102     }
4103
4104     // Check each assertion in chkAssertions to see if it can be applied to constAssertion
4105     BitVecOps::Iter chkIter(apTraits, chkAssertions);
4106     unsigned        chkIndex = 0;
4107     while (chkIter.NextElem(&chkIndex))
4108     {
4109         AssertionIndex chkAssertionIndex = GetAssertionIndex(chkIndex);
4110         if (chkAssertionIndex > optAssertionCount)
4111         {
4112             break;
4113         }
4114         // The impAssertion must be different from the const assertion.
4115         AssertionDsc* impAssertion = optGetAssertion(chkAssertionIndex);
4116         if (impAssertion == constAssertion)
4117         {
4118             continue;
4119         }
4120
4121         // The impAssertion must be an assertion about the same local var.
4122         if (impAssertion->op1.vn != constAssertion->op1.vn)
4123         {
4124             continue;
4125         }
4126
4127         bool usable = false;
4128         switch (impAssertion->op2.kind)
4129         {
4130             case O2K_SUBRANGE:
4131                 // Is the const assertion's constant, within implied assertion's bounds?
4132                 usable = ((iconVal >= impAssertion->op2.u2.loBound) && (iconVal <= impAssertion->op2.u2.hiBound));
4133                 break;
4134
4135             case O2K_CONST_INT:
4136                 // Is the const assertion's constant equal/not equal to the implied assertion?
4137                 usable = ((impAssertion->assertionKind == OAK_EQUAL) && (impAssertion->op2.u1.iconVal == iconVal)) ||
4138                          ((impAssertion->assertionKind == OAK_NOT_EQUAL) && (impAssertion->op2.u1.iconVal != iconVal));
4139                 break;
4140
4141             default:
4142                 // leave 'usable' = false;
4143                 break;
4144         }
4145
4146         if (usable)
4147         {
4148             BitVecOps::AddElemD(apTraits, result, chkIndex);
4149 #ifdef DEBUG
4150             if (verbose)
4151             {
4152                 AssertionDsc* firstAssertion = optGetAssertion(1);
4153                 printf("\nCompiler::optImpliedByConstAssertion: constAssertion #%02d , implies assertion #%02d",
4154                        (constAssertion - firstAssertion) + 1, (impAssertion - firstAssertion) + 1);
4155             }
4156 #endif
4157         }
4158     }
4159 }
4160
4161 /*****************************************************************************
4162  *
4163  *  Given a copy assertion and a dependent assertion this method computes the
4164  *  set of implied assertions that are also true.
4165  *  For copy assertions, exact SSA num and LCL nums should match, because
4166  *  we don't have kill sets and we depend on their value num for dataflow.
4167  */
4168
4169 void Compiler::optImpliedByCopyAssertion(AssertionDsc* copyAssertion, AssertionDsc* depAssertion, ASSERT_TP& result)
4170 {
4171     noway_assert(copyAssertion->IsCopyAssertion());
4172
4173     // Get the copyAssert's lcl/ssa nums.
4174     unsigned copyAssertLclNum = BAD_VAR_NUM;
4175     unsigned copyAssertSsaNum = SsaConfig::RESERVED_SSA_NUM;
4176
4177     // Check if copyAssertion's op1 or op2 matches the depAssertion's op1.
4178     if (depAssertion->op1.lcl.lclNum == copyAssertion->op1.lcl.lclNum)
4179     {
4180         copyAssertLclNum = copyAssertion->op2.lcl.lclNum;
4181         copyAssertSsaNum = copyAssertion->op2.lcl.ssaNum;
4182     }
4183     else if (depAssertion->op1.lcl.lclNum == copyAssertion->op2.lcl.lclNum)
4184     {
4185         copyAssertLclNum = copyAssertion->op1.lcl.lclNum;
4186         copyAssertSsaNum = copyAssertion->op1.lcl.ssaNum;
4187     }
4188     // Check if copyAssertion's op1 or op2 matches the depAssertion's op2.
4189     else if (depAssertion->op2.kind == O2K_LCLVAR_COPY)
4190     {
4191         if (depAssertion->op2.lcl.lclNum == copyAssertion->op1.lcl.lclNum)
4192         {
4193             copyAssertLclNum = copyAssertion->op2.lcl.lclNum;
4194             copyAssertSsaNum = copyAssertion->op2.lcl.ssaNum;
4195         }
4196         else if (depAssertion->op2.lcl.lclNum == copyAssertion->op2.lcl.lclNum)
4197         {
4198             copyAssertLclNum = copyAssertion->op1.lcl.lclNum;
4199             copyAssertSsaNum = copyAssertion->op1.lcl.ssaNum;
4200         }
4201     }
4202
4203     if (copyAssertLclNum == BAD_VAR_NUM || copyAssertSsaNum == SsaConfig::RESERVED_SSA_NUM)
4204     {
4205         return;
4206     }
4207
4208     // Get the depAssert's lcl/ssa nums.
4209     unsigned depAssertLclNum = BAD_VAR_NUM;
4210     unsigned depAssertSsaNum = SsaConfig::RESERVED_SSA_NUM;
4211     if ((depAssertion->op1.kind == O1K_LCLVAR) && (depAssertion->op2.kind == O2K_LCLVAR_COPY))
4212     {
4213         if ((depAssertion->op1.lcl.lclNum == copyAssertion->op1.lcl.lclNum) ||
4214             (depAssertion->op1.lcl.lclNum == copyAssertion->op2.lcl.lclNum))
4215         {
4216             depAssertLclNum = depAssertion->op2.lcl.lclNum;
4217             depAssertSsaNum = depAssertion->op2.lcl.ssaNum;
4218         }
4219         else if ((depAssertion->op2.lcl.lclNum == copyAssertion->op1.lcl.lclNum) ||
4220                  (depAssertion->op2.lcl.lclNum == copyAssertion->op2.lcl.lclNum))
4221         {
4222             depAssertLclNum = depAssertion->op1.lcl.lclNum;
4223             depAssertSsaNum = depAssertion->op1.lcl.ssaNum;
4224         }
4225     }
4226
4227     if (depAssertLclNum == BAD_VAR_NUM || depAssertSsaNum == SsaConfig::RESERVED_SSA_NUM)
4228     {
4229         return;
4230     }
4231
4232     // Is depAssertion a constant assignment of a 32-bit integer?
4233     // (i.e  GT_LVL_VAR X == GT_CNS_INT)
4234     bool depIsConstAssertion = ((depAssertion->assertionKind == OAK_EQUAL) && (depAssertion->op1.kind == O1K_LCLVAR) &&
4235                                 (depAssertion->op2.kind == O2K_CONST_INT));
4236
4237     // Search the assertion table for an assertion on op1 that matches depAssertion
4238     // The matching assertion is the implied assertion.
4239     for (AssertionIndex impIndex = 1; impIndex <= optAssertionCount; impIndex++)
4240     {
4241         AssertionDsc* impAssertion = optGetAssertion(impIndex);
4242
4243         //  The impAssertion must be different from the copy and dependent assertions
4244         if (impAssertion == copyAssertion || impAssertion == depAssertion)
4245         {
4246             continue;
4247         }
4248
4249         if (!AssertionDsc::SameKind(depAssertion, impAssertion))
4250         {
4251             continue;
4252         }
4253
4254         bool op1MatchesCopy =
4255             (copyAssertLclNum == impAssertion->op1.lcl.lclNum) && (copyAssertSsaNum == impAssertion->op1.lcl.ssaNum);
4256
4257         bool usable = false;
4258         switch (impAssertion->op2.kind)
4259         {
4260             case O2K_SUBRANGE:
4261                 usable = op1MatchesCopy && ((impAssertion->op2.u2.loBound <= depAssertion->op2.u2.loBound) &&
4262                                             (impAssertion->op2.u2.hiBound >= depAssertion->op2.u2.hiBound));
4263                 break;
4264
4265             case O2K_CONST_LONG:
4266                 usable = op1MatchesCopy && (impAssertion->op2.lconVal == depAssertion->op2.lconVal);
4267                 break;
4268
4269             case O2K_CONST_DOUBLE:
4270                 // Exact memory match because of positive and negative zero
4271                 usable = op1MatchesCopy &&
4272                          (memcmp(&impAssertion->op2.dconVal, &depAssertion->op2.dconVal, sizeof(double)) == 0);
4273                 break;
4274
4275             case O2K_IND_CNS_INT:
4276                 // This is the ngen case where we have an indirection of an address.
4277                 noway_assert((impAssertion->op1.kind == O1K_EXACT_TYPE) || (impAssertion->op1.kind == O1K_SUBTYPE));
4278
4279                 __fallthrough;
4280
4281             case O2K_CONST_INT:
4282                 usable = op1MatchesCopy && (impAssertion->op2.u1.iconVal == depAssertion->op2.u1.iconVal);
4283                 break;
4284
4285             case O2K_LCLVAR_COPY:
4286                 // Check if op1 of impAssertion matches copyAssertion and also op2 of impAssertion matches depAssertion.
4287                 if (op1MatchesCopy && (depAssertLclNum == impAssertion->op2.lcl.lclNum &&
4288                                        depAssertSsaNum == impAssertion->op2.lcl.ssaNum))
4289                 {
4290                     usable = true;
4291                 }
4292                 else
4293                 {
4294                     // Otherwise, op2 of impAssertion should match copyAssertion and also op1 of impAssertion matches
4295                     // depAssertion.
4296                     usable = ((copyAssertLclNum == impAssertion->op2.lcl.lclNum &&
4297                                copyAssertSsaNum == impAssertion->op2.lcl.ssaNum) &&
4298                               (depAssertLclNum == impAssertion->op1.lcl.lclNum &&
4299                                depAssertSsaNum == impAssertion->op1.lcl.ssaNum));
4300                 }
4301                 break;
4302
4303             default:
4304                 // leave 'usable' = false;
4305                 break;
4306         }
4307
4308         if (usable)
4309         {
4310             BitVecOps::AddElemD(apTraits, result, impIndex - 1);
4311
4312 #ifdef DEBUG
4313             if (verbose)
4314             {
4315                 AssertionDsc* firstAssertion = optGetAssertion(1);
4316                 printf("\nCompiler::optImpliedByCopyAssertion: copyAssertion #%02d and depAssertion #%02d, implies "
4317                        "assertion #%02d",
4318                        (copyAssertion - firstAssertion) + 1, (depAssertion - firstAssertion) + 1,
4319                        (impAssertion - firstAssertion) + 1);
4320             }
4321 #endif
4322             // If the depAssertion is a const assertion then any other assertions that it implies could also imply a
4323             // subrange assertion.
4324             if (depIsConstAssertion)
4325             {
4326                 optImpliedByConstAssertion(impAssertion, result);
4327             }
4328         }
4329     }
4330 }
4331
4332 #include "dataflow.h"
4333
4334 /*****************************************************************************
4335  *
4336  * Dataflow visitor like callback so that all dataflow is in a single place
4337  *
4338  */
4339 class AssertionPropFlowCallback
4340 {
4341 private:
4342     ASSERT_TP preMergeOut;
4343     ASSERT_TP preMergeJumpDestOut;
4344
4345     ASSERT_TP* mJumpDestOut;
4346     ASSERT_TP* mJumpDestGen;
4347
4348     Compiler*     m_pCompiler;
4349     BitVecTraits* apTraits;
4350
4351 public:
4352     AssertionPropFlowCallback(Compiler* pCompiler, ASSERT_TP* jumpDestOut, ASSERT_TP* jumpDestGen)
4353         : preMergeOut(BitVecOps::UninitVal())
4354         , preMergeJumpDestOut(BitVecOps::UninitVal())
4355         , mJumpDestOut(jumpDestOut)
4356         , mJumpDestGen(jumpDestGen)
4357         , m_pCompiler(pCompiler)
4358         , apTraits(pCompiler->apTraits)
4359     {
4360     }
4361
4362     // At the start of the merge function of the dataflow equations, initialize premerge state (to detect change.)
4363     void StartMerge(BasicBlock* block)
4364     {
4365         JITDUMP("AssertionPropCallback::StartMerge: BB%02d in -> %s\n", block->bbNum,
4366                 BitVecOps::ToString(apTraits, block->bbAssertionIn));
4367         BitVecOps::Assign(apTraits, preMergeOut, block->bbAssertionOut);
4368         BitVecOps::Assign(apTraits, preMergeJumpDestOut, mJumpDestOut[block->bbNum]);
4369     }
4370
4371     // During merge, perform the actual merging of the predecessor's (since this is a forward analysis) dataflow flags.
4372     void Merge(BasicBlock* block, BasicBlock* predBlock, flowList* preds)
4373     {
4374         ASSERT_TP pAssertionOut = ((predBlock->bbJumpKind == BBJ_COND) && (predBlock->bbJumpDest == block))
4375                                       ? mJumpDestOut[predBlock->bbNum]
4376                                       : predBlock->bbAssertionOut;
4377         JITDUMP("AssertionPropCallback::Merge     : BB%02d in -> %s, predBlock BB%02d out -> %s\n", block->bbNum,
4378                 BitVecOps::ToString(apTraits, block->bbAssertionIn), predBlock->bbNum,
4379                 BitVecOps::ToString(apTraits, predBlock->bbAssertionOut));
4380         BitVecOps::IntersectionD(apTraits, block->bbAssertionIn, pAssertionOut);
4381     }
4382
4383     // At the end of the merge store results of the dataflow equations, in a postmerge state.
4384     bool EndMerge(BasicBlock* block)
4385     {
4386         JITDUMP("AssertionPropCallback::EndMerge  : BB%02d in -> %s\n\n", block->bbNum,
4387                 BitVecOps::ToString(apTraits, block->bbAssertionIn));
4388
4389         BitVecOps::DataFlowD(apTraits, block->bbAssertionOut, block->bbAssertionGen, block->bbAssertionIn);
4390         BitVecOps::DataFlowD(apTraits, mJumpDestOut[block->bbNum], mJumpDestGen[block->bbNum], block->bbAssertionIn);
4391
4392         bool changed = (!BitVecOps::Equal(apTraits, preMergeOut, block->bbAssertionOut) ||
4393                         !BitVecOps::Equal(apTraits, preMergeJumpDestOut, mJumpDestOut[block->bbNum]));
4394
4395         if (changed)
4396         {
4397             JITDUMP("AssertionPropCallback::Changed   : BB%02d before out -> %s; after out -> %s;\n"
4398                     "\t\tjumpDest before out -> %s; jumpDest after out -> %s;\n\n",
4399                     block->bbNum, BitVecOps::ToString(apTraits, preMergeOut),
4400                     BitVecOps::ToString(apTraits, block->bbAssertionOut),
4401                     BitVecOps::ToString(apTraits, preMergeJumpDestOut),
4402                     BitVecOps::ToString(apTraits, mJumpDestOut[block->bbNum]));
4403         }
4404         else
4405         {
4406             JITDUMP("AssertionPropCallback::Unchanged  : BB%02d out -> %s; \t\tjumpDest out -> %s\n\n", block->bbNum,
4407                     BitVecOps::ToString(apTraits, block->bbAssertionOut),
4408                     BitVecOps::ToString(apTraits, mJumpDestOut[block->bbNum]));
4409         }
4410
4411         return changed;
4412     }
4413 };
4414
4415 /*****************************************************************************
4416  *
4417  *   Compute the assertions generated by each block.
4418  */
4419 ASSERT_TP* Compiler::optComputeAssertionGen()
4420 {
4421     ASSERT_TP* jumpDestGen = fgAllocateTypeForEachBlk<ASSERT_TP>();
4422
4423     for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
4424     {
4425         ASSERT_TP valueGen = BitVecOps::MakeEmpty(apTraits);
4426         GenTree*  jtrue    = nullptr;
4427
4428         // Walk the statement trees in this basic block.
4429         for (GenTree* stmt = block->bbTreeList; stmt; stmt = stmt->gtNext)
4430         {
4431             noway_assert(stmt->gtOper == GT_STMT);
4432
4433             for (GenTree* tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext)
4434             {
4435                 if (tree->gtOper == GT_JTRUE)
4436                 {
4437                     // A GT_TRUE is always the last node in a tree, so we can break here
4438                     assert((tree->gtNext == nullptr) && (stmt->gtNext == nullptr));
4439                     jtrue = tree;
4440                     break;
4441                 }
4442
4443                 if (tree->GeneratesAssertion())
4444                 {
4445                     AssertionInfo info = tree->GetAssertionInfo();
4446                     optImpliedAssertions(info.GetAssertionIndex(), valueGen);
4447                     BitVecOps::AddElemD(apTraits, valueGen, info.GetAssertionIndex() - 1);
4448                 }
4449             }
4450         }
4451
4452         if (jtrue != nullptr)
4453         {
4454             // Copy whatever we have accumulated into jumpDest edge's valueGen.
4455             ASSERT_TP jumpDestValueGen = BitVecOps::MakeCopy(apTraits, valueGen);
4456
4457             if (jtrue->GeneratesAssertion())
4458             {
4459                 AssertionInfo  info = jtrue->GetAssertionInfo();
4460                 AssertionIndex valueAssertionIndex;
4461                 AssertionIndex jumpDestAssertionIndex;
4462
4463                 if (info.IsNextEdgeAssertion())
4464                 {
4465                     valueAssertionIndex    = info.GetAssertionIndex();
4466                     jumpDestAssertionIndex = optFindComplementary(info.GetAssertionIndex());
4467                 }
4468                 else // is jump edge assertion
4469                 {
4470                     valueAssertionIndex    = optFindComplementary(info.GetAssertionIndex());
4471                     jumpDestAssertionIndex = info.GetAssertionIndex();
4472                 }
4473
4474                 if (valueAssertionIndex != NO_ASSERTION_INDEX)
4475                 {
4476                     // Update valueGen if we have an assertion for the bbNext edge
4477                     optImpliedAssertions(valueAssertionIndex, valueGen);
4478                     BitVecOps::AddElemD(apTraits, valueGen, valueAssertionIndex - 1);
4479                 }
4480
4481                 if (jumpDestAssertionIndex != NO_ASSERTION_INDEX)
4482                 {
4483                     // Update jumpDestValueGen if we have an assertion for the bbJumpDest edge
4484                     optImpliedAssertions(jumpDestAssertionIndex, jumpDestValueGen);
4485                     BitVecOps::AddElemD(apTraits, jumpDestValueGen, jumpDestAssertionIndex - 1);
4486                 }
4487             }
4488
4489             jumpDestGen[block->bbNum] = jumpDestValueGen;
4490         }
4491         else
4492         {
4493             jumpDestGen[block->bbNum] = BitVecOps::MakeEmpty(apTraits);
4494         }
4495
4496         block->bbAssertionGen = valueGen;
4497
4498 #ifdef DEBUG
4499         if (verbose)
4500         {
4501             printf("\nBB%02u valueGen = %s", block->bbNum, BitVecOps::ToString(apTraits, block->bbAssertionGen));
4502             if (block->bbJumpKind == BBJ_COND)
4503             {
4504                 printf(" => BB%02u valueGen = %s,", block->bbJumpDest->bbNum,
4505                        BitVecOps::ToString(apTraits, jumpDestGen[block->bbNum]));
4506             }
4507         }
4508 #endif
4509     }
4510     return jumpDestGen;
4511 }
4512
4513 /*****************************************************************************
4514  *
4515  *   Initialize the assertion data flow flags that will be propagated.
4516  */
4517
4518 ASSERT_TP* Compiler::optInitAssertionDataflowFlags()
4519 {
4520     ASSERT_TP* jumpDestOut = fgAllocateTypeForEachBlk<ASSERT_TP>();
4521
4522     // The local assertion gen phase may have created unreachable blocks.
4523     // They will never be visited in the dataflow propagation phase, so they need to
4524     // be initialized correctly. This means that instead of setting their sets to
4525     // apFull (i.e. all possible bits set), we need to set the bits only for valid
4526     // assertions (note that at this point we are not creating any new assertions).
4527     // Also note that assertion indices start from 1.
4528     ASSERT_TP apValidFull = BitVecOps::MakeEmpty(apTraits);
4529     for (int i = 1; i <= optAssertionCount; i++)
4530     {
4531         BitVecOps::AddElemD(apTraits, apValidFull, i - 1);
4532     }
4533
4534     // Initially estimate the OUT sets to everything except killed expressions
4535     // Also set the IN sets to 1, so that we can perform the intersection.
4536     // Also, zero-out the flags for handler blocks, as we could be in the
4537     // handler due to an exception bypassing the regular program flow which
4538     // actually generates assertions along the bbAssertionOut/jumpDestOut
4539     // edges.
4540     for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
4541     {
4542         if (bbIsHandlerBeg(block))
4543         {
4544             block->bbAssertionIn = BitVecOps::MakeEmpty(apTraits);
4545         }
4546         else
4547         {
4548             block->bbAssertionIn = BitVecOps::MakeCopy(apTraits, apValidFull);
4549         }
4550         block->bbAssertionGen     = BitVecOps::MakeEmpty(apTraits);
4551         block->bbAssertionOut     = BitVecOps::MakeCopy(apTraits, apValidFull);
4552         jumpDestOut[block->bbNum] = BitVecOps::MakeCopy(apTraits, apValidFull);
4553     }
4554     // Compute the data flow values for all tracked expressions
4555     // IN and OUT never change for the initial basic block B1
4556     BitVecOps::ClearD(apTraits, fgFirstBB->bbAssertionIn);
4557     return jumpDestOut;
4558 }
4559
4560 // Callback data for the VN based constant prop visitor.
4561 struct VNAssertionPropVisitorInfo
4562 {
4563     Compiler*   pThis;
4564     GenTree*    stmt;
4565     BasicBlock* block;
4566     VNAssertionPropVisitorInfo(Compiler* pThis, BasicBlock* block, GenTree* stmt)
4567         : pThis(pThis), stmt(stmt), block(block)
4568     {
4569     }
4570 };
4571
4572 //------------------------------------------------------------------------------
4573 // optPrepareTreeForReplacement
4574 //    Updates ref counts and extracts side effects from a tree so it can be
4575 //    replaced with a comma separated list of side effects + a new tree.
4576 //
4577 // Note:
4578 //    The old and new trees may be the same. In this case, the tree will be
4579 //    appended to the side-effect list (if present) and returned.
4580 //
4581 // Arguments:
4582 //    oldTree  - The tree node to be dropped from the stmt expr.
4583 //    newTree  - The tree node to append to the side effect list from "oldTree".
4584 //
4585 // Return Value:
4586 //    Returns a comma separated list of side-effects present in the "oldTree".
4587 //    When "newTree" is non-null:
4588 //      1. When side-effects are present in oldTree, newTree will be appended to the
4589 //         comma separated list.
4590 //      2. When no side effects are present, then returns the "newTree" without
4591 //         any list.
4592 //    When "newTree" is null:
4593 //      1. Returns the extracted side-effects from "oldTree"
4594 //      2. When no side-effects are present, returns null.
4595 //
4596 // Description:
4597 //    Decrements ref counts for the "oldTree" that is going to be replaced. If there
4598 //    are side effects in the tree, then ref counts for variables in the side effects
4599 //    are incremented because they need to be kept in the stmt expr.
4600 //
4601 //    Either the "newTree" is returned when no side effects are present or a comma
4602 //    separated side effect list with "newTree" is returned.
4603 //
4604 GenTree* Compiler::optPrepareTreeForReplacement(GenTree* oldTree, GenTree* newTree)
4605 {
4606     // If we have side effects, extract them and append newTree to the list.
4607     GenTree* sideEffList = nullptr;
4608     if (oldTree->gtFlags & GTF_PERSISTENT_SIDE_EFFECTS)
4609     {
4610         gtExtractSideEffList(oldTree, &sideEffList, GTF_PERSISTENT_SIDE_EFFECTS_IN_CSE);
4611     }
4612     if (sideEffList)
4613     {
4614         noway_assert(sideEffList->gtFlags & GTF_SIDE_EFFECT);
4615
4616         // Increment the ref counts as we want to keep the side effects.
4617         lvaRecursiveIncRefCounts(sideEffList);
4618
4619         if (newTree)
4620         {
4621             newTree = gtNewOperNode(GT_COMMA, newTree->TypeGet(), sideEffList, newTree);
4622         }
4623         else
4624         {
4625             newTree = sideEffList;
4626         }
4627     }
4628
4629     // Decrement the ref counts as the oldTree is going to be dropped.
4630     lvaRecursiveDecRefCounts(oldTree);
4631     return newTree;
4632 }
4633
4634 //------------------------------------------------------------------------------
4635 // optVNConstantPropOnJTrue
4636 //    Constant propagate on the JTrue node by extracting side effects and moving
4637 //    them into their own statements. The relop node is then modified to yield
4638 //    true or false, so the branch can be folded.
4639 //
4640 // Arguments:
4641 //    block - The block that contains the JTrue.
4642 //    stmt  - The JTrue stmt which can be evaluated to a constant.
4643 //    tree  - The JTrue node whose relop evaluates to 0 or non-zero value.
4644 //
4645 // Return Value:
4646 //    The jmpTrue tree node that has relop of the form "0 =/!= 0".
4647 //    If "tree" evaluates to "true" relop is "0 == 0". Else relop is "0 != 0".
4648 //
4649 // Description:
4650 //    Special treatment for JTRUE nodes' constant propagation. This is because
4651 //    for JTRUE(1) or JTRUE(0), if there are side effects they need to be put
4652 //    in separate statements. This is to prevent relop's constant
4653 //    propagation from doing a simple minded conversion from
4654 //    (1) STMT(JTRUE(RELOP(COMMA(sideEffect, OP1), OP2)), S.T. op1 =/!= op2 to
4655 //    (2) STMT(JTRUE(COMMA(sideEffect, 1/0)).
4656 //
4657 //    fgFoldConditional doesn't fold (2), a side-effecting JTRUE's op1. So, let us,
4658 //    here, convert (1) as two statements: STMT(sideEffect), STMT(JTRUE(1/0)),
4659 //    so that the JTRUE will get folded by fgFoldConditional.
4660 //
4661 //  Note: fgFoldConditional is called from other places as well, which may be
4662 //  sensitive to adding new statements. Hence the change is not made directly
4663 //  into fgFoldConditional.
4664 //
4665 GenTree* Compiler::optVNConstantPropOnJTrue(BasicBlock* block, GenTree* stmt, GenTree* test)
4666 {
4667     GenTree* relop = test->gtGetOp1();
4668
4669     // VN based assertion non-null on this relop has been performed.
4670     if (!relop->OperIsCompare())
4671     {
4672         return nullptr;
4673     }
4674
4675     //
4676     // Make sure GTF_RELOP_JMP_USED flag is set so that we can later skip constant
4677     // prop'ing a JTRUE's relop child node for a second time in the pre-order
4678     // tree walk.
4679     //
4680     assert((relop->gtFlags & GTF_RELOP_JMP_USED) != 0);
4681
4682     if (!vnStore->IsVNConstant(relop->gtVNPair.GetConservative()))
4683     {
4684         return nullptr;
4685     }
4686
4687     // Prepare the tree for replacement so any side effects can be extracted.
4688     GenTree* sideEffList = optPrepareTreeForReplacement(test, nullptr);
4689
4690     while (sideEffList)
4691     {
4692         GenTree* newStmt;
4693         if (sideEffList->OperGet() == GT_COMMA)
4694         {
4695             newStmt     = fgInsertStmtNearEnd(block, sideEffList->gtGetOp1());
4696             sideEffList = sideEffList->gtGetOp2();
4697         }
4698         else
4699         {
4700             newStmt     = fgInsertStmtNearEnd(block, sideEffList);
4701             sideEffList = nullptr;
4702         }
4703
4704         fgMorphBlockStmt(block, newStmt->AsStmt() DEBUGARG(__FUNCTION__));
4705     }
4706
4707     // Transform the relop's operands to be both zeroes.
4708     ValueNum vnZero             = vnStore->VNZeroForType(TYP_INT);
4709     relop->gtOp.gtOp1           = gtNewIconNode(0);
4710     relop->gtOp.gtOp1->gtVNPair = ValueNumPair(vnZero, vnZero);
4711     relop->gtOp.gtOp2           = gtNewIconNode(0);
4712     relop->gtOp.gtOp2->gtVNPair = ValueNumPair(vnZero, vnZero);
4713
4714     // Update the oper and restore the value numbers.
4715     ValueNum vnCns       = relop->gtVNPair.GetConservative();
4716     ValueNum vnLib       = relop->gtVNPair.GetLiberal();
4717     bool     evalsToTrue = vnStore->CoercedConstantValue<INT64>(vnCns) != 0;
4718     relop->SetOper(evalsToTrue ? GT_EQ : GT_NE);
4719     relop->gtVNPair = ValueNumPair(vnLib, vnCns);
4720
4721     return test;
4722 }
4723
4724 //------------------------------------------------------------------------------
4725 // optVNConstantPropCurStmt
4726 //    Performs constant prop on the current statement's tree nodes.
4727 //
4728 // Assumption:
4729 //    This function is called as part of a pre-order tree walk.
4730 //
4731 // Arguments:
4732 //    tree  - The currently visited tree node.
4733 //    stmt  - The statement node in which the "tree" is present.
4734 //    block - The block that contains the statement that contains the tree.
4735 //
4736 // Return Value:
4737 //    Returns the standard visitor walk result.
4738 //
4739 // Description:
4740 //    Checks if a node is an R-value and evaluates to a constant. If the node
4741 //    evaluates to constant, then the tree is replaced by its side effects and
4742 //    the constant node.
4743 //
4744 Compiler::fgWalkResult Compiler::optVNConstantPropCurStmt(BasicBlock* block, GenTree* stmt, GenTree* tree)
4745 {
4746     // Don't propagate floating-point constants into a TYP_STRUCT LclVar
4747     // This can occur for HFA return values (see hfa_sf3E_r.exe)
4748     if (tree->TypeGet() == TYP_STRUCT)
4749     {
4750         return WALK_CONTINUE;
4751     }
4752
4753     switch (tree->OperGet())
4754     {
4755         // Make sure we have an R-value.
4756         case GT_ADD:
4757         case GT_SUB:
4758         case GT_DIV:
4759         case GT_MOD:
4760         case GT_UDIV:
4761         case GT_UMOD:
4762         case GT_EQ:
4763         case GT_NE:
4764         case GT_LT:
4765         case GT_LE:
4766         case GT_GE:
4767         case GT_GT:
4768         case GT_OR:
4769         case GT_XOR:
4770         case GT_AND:
4771         case GT_LSH:
4772         case GT_RSH:
4773         case GT_RSZ:
4774         case GT_NEG:
4775 #ifdef LEGACY_BACKEND
4776         case GT_CHS:
4777 #endif
4778         case GT_CAST:
4779         case GT_INTRINSIC:
4780             break;
4781
4782         case GT_MULHI:
4783             assert(false && "Unexpected GT_MULHI node encountered before lowering");
4784             break;
4785
4786         case GT_JTRUE:
4787             break;
4788
4789         case GT_MUL:
4790             // Don't transform long multiplies.
4791             if (tree->gtFlags & GTF_MUL_64RSLT)
4792             {
4793                 return WALK_SKIP_SUBTREES;
4794             }
4795             break;
4796
4797         case GT_LCL_VAR:
4798             // Make sure the local variable is an R-value.
4799             if ((tree->gtFlags & (GTF_VAR_DEF | GTF_DONT_CSE)))
4800             {
4801                 return WALK_CONTINUE;
4802             }
4803 #if FEATURE_ANYCSE
4804             // Let's not conflict with CSE (to save the movw/movt).
4805             if (lclNumIsCSE(tree->AsLclVarCommon()->GetLclNum()))
4806             {
4807                 return WALK_CONTINUE;
4808             }
4809 #endif
4810             break;
4811
4812         default:
4813             // Unknown node, continue to walk.
4814             return WALK_CONTINUE;
4815     }
4816
4817     // Perform the constant propagation
4818     GenTree* newTree = optVNConstantPropOnTree(block, stmt, tree);
4819     if (newTree == nullptr)
4820     {
4821         // Not propagated, keep going.
4822         return WALK_CONTINUE;
4823     }
4824
4825     // Successful propagation, mark as assertion propagated and skip
4826     // sub-tree (with side-effects) visits.
4827     optAssertionProp_Update(newTree, tree, stmt);
4828
4829     JITDUMP("After constant propagation on [%06u]:\n", tree->gtTreeID);
4830     DBEXEC(VERBOSE, gtDispTree(stmt));
4831
4832     return WALK_SKIP_SUBTREES;
4833 }
4834
4835 //------------------------------------------------------------------------------
4836 // optVnNonNullPropCurStmt
4837 //    Performs VN based non-null propagation on the tree node.
4838 //
4839 // Assumption:
4840 //    This function is called as part of a pre-order tree walk.
4841 //
4842 // Arguments:
4843 //    block - The block that contains the statement that contains the tree.
4844 //    stmt  - The statement node in which the "tree" is present.
4845 //    tree  - The currently visited tree node.
4846 //
4847 // Return Value:
4848 //    None.
4849 //
4850 // Description:
4851 //    Performs value number based non-null propagation on GT_CALL and
4852 //    indirections. This is different from flow based assertions and helps
4853 //    unify VN based constant prop and non-null prop in a single pre-order walk.
4854 //
4855 void Compiler::optVnNonNullPropCurStmt(BasicBlock* block, GenTree* stmt, GenTree* tree)
4856 {
4857     ASSERT_TP empty   = BitVecOps::UninitVal();
4858     GenTree*  newTree = nullptr;
4859     if (tree->OperGet() == GT_CALL)
4860     {
4861         newTree = optNonNullAssertionProp_Call(empty, tree->AsCall(), stmt);
4862     }
4863     else if (tree->OperIsIndir())
4864     {
4865         newTree = optAssertionProp_Ind(empty, tree, stmt);
4866     }
4867     if (newTree)
4868     {
4869         assert(newTree == tree);
4870         optAssertionProp_Update(newTree, tree, stmt);
4871     }
4872 }
4873
4874 //------------------------------------------------------------------------------
4875 // optVNAssertionPropCurStmtVisitor
4876 //    Unified Value Numbering based assertion propagation visitor.
4877 //
4878 // Assumption:
4879 //    This function is called as part of a pre-order tree walk.
4880 //
4881 // Return Value:
4882 //    WALK_RESULTs.
4883 //
4884 // Description:
4885 //    An unified value numbering based assertion prop visitor that
4886 //    performs non-null and constant assertion propagation based on
4887 //    value numbers.
4888 //
4889 /* static */
4890 Compiler::fgWalkResult Compiler::optVNAssertionPropCurStmtVisitor(GenTree** ppTree, fgWalkData* data)
4891 {
4892     VNAssertionPropVisitorInfo* pData = (VNAssertionPropVisitorInfo*)data->pCallbackData;
4893     Compiler*                   pThis = pData->pThis;
4894
4895     pThis->optVnNonNullPropCurStmt(pData->block, pData->stmt, *ppTree);
4896
4897     return pThis->optVNConstantPropCurStmt(pData->block, pData->stmt, *ppTree);
4898 }
4899
4900 /*****************************************************************************
4901  *
4902  *   Perform VN based i.e., data flow based assertion prop first because
4903  *   even if we don't gen new control flow assertions, we still propagate
4904  *   these first.
4905  *
4906  *   Returns the skipped next stmt if the current statement or next few
4907  *   statements got removed, else just returns the incoming stmt.
4908  */
4909 GenTree* Compiler::optVNAssertionPropCurStmt(BasicBlock* block, GenTree* stmt)
4910 {
4911     // TODO-Review: EH successor/predecessor iteration seems broken.
4912     // See: SELF_HOST_TESTS_ARM\jit\Directed\ExcepFilters\fault\fault.exe
4913     if (block->bbCatchTyp == BBCT_FAULT)
4914     {
4915         return stmt;
4916     }
4917
4918     // Preserve the prev link before the propagation and morph.
4919     GenTree* prev = (stmt == block->firstStmt()) ? nullptr : stmt->gtPrev;
4920
4921     // Perform VN based assertion prop first, in case we don't find
4922     // anything in assertion gen.
4923     optAssertionPropagatedCurrentStmt = false;
4924
4925     VNAssertionPropVisitorInfo data(this, block, stmt);
4926     fgWalkTreePre(&stmt->gtStmt.gtStmtExpr, Compiler::optVNAssertionPropCurStmtVisitor, &data);
4927
4928     if (optAssertionPropagatedCurrentStmt)
4929     {
4930         fgMorphBlockStmt(block, stmt->AsStmt() DEBUGARG("optVNAssertionPropCurStmt"));
4931     }
4932
4933     // Check if propagation removed statements starting from current stmt.
4934     // If so, advance to the next good statement.
4935     GenTree* nextStmt = (prev == nullptr) ? block->firstStmt() : prev->gtNext;
4936     return nextStmt;
4937 }
4938
4939 /*****************************************************************************
4940  *
4941  *   The entry point for assertion propagation
4942  */
4943
4944 void Compiler::optAssertionPropMain()
4945 {
4946     if (fgSsaPassesCompleted == 0)
4947     {
4948         return;
4949     }
4950 #ifdef DEBUG
4951     if (verbose)
4952     {
4953         printf("*************** In optAssertionPropMain()\n");
4954         printf("Blocks/Trees at start of phase\n");
4955         fgDispBasicBlocks(true);
4956     }
4957 #endif
4958
4959     optAssertionInit(false);
4960
4961     noway_assert(optAssertionCount == 0);
4962
4963     // First discover all value assignments and record them in the table.
4964     for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
4965     {
4966         compCurBB = block;
4967
4968         fgRemoveRestOfBlock = false;
4969
4970         GenTree* stmt = block->bbTreeList;
4971         while (stmt)
4972         {
4973             // We need to remove the rest of the block.
4974             if (fgRemoveRestOfBlock)
4975             {
4976                 fgRemoveStmt(block, stmt);
4977                 stmt = stmt->gtNext;
4978                 continue;
4979             }
4980             else
4981             {
4982                 // Perform VN based assertion prop before assertion gen.
4983                 GenTree* nextStmt = optVNAssertionPropCurStmt(block, stmt);
4984
4985                 // Propagation resulted in removal of the remaining stmts, perform it.
4986                 if (fgRemoveRestOfBlock)
4987                 {
4988                     stmt = stmt->gtNext;
4989                     continue;
4990                 }
4991
4992                 // Propagation removed the current stmt or next few stmts, so skip them.
4993                 if (stmt != nextStmt)
4994                 {
4995                     stmt = nextStmt;
4996                     continue;
4997                 }
4998             }
4999
5000             // Perform assertion gen for control flow based assertions.
5001             for (GenTree* tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext)
5002             {
5003                 optAssertionGen(tree);
5004             }
5005
5006             // Advance the iterator
5007             stmt = stmt->gtNext;
5008         }
5009     }
5010
5011     if (!optAssertionCount)
5012     {
5013         return;
5014     }
5015
5016 #ifdef DEBUG
5017     fgDebugCheckLinks();
5018 #endif
5019
5020     // Allocate the bits for the predicate sensitive dataflow analysis
5021     bbJtrueAssertionOut    = optInitAssertionDataflowFlags();
5022     ASSERT_TP* jumpDestGen = optComputeAssertionGen();
5023
5024     // Modified dataflow algorithm for available expressions.
5025     DataFlow                  flow(this);
5026     AssertionPropFlowCallback ap(this, bbJtrueAssertionOut, jumpDestGen);
5027     flow.ForwardAnalysis(ap);
5028
5029     for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
5030     {
5031         // Compute any implied non-Null assertions for block->bbAssertionIn
5032         optImpliedByTypeOfAssertions(block->bbAssertionIn);
5033     }
5034
5035 #ifdef DEBUG
5036     if (verbose)
5037     {
5038         printf("\n");
5039         for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
5040         {
5041             printf("\nBB%02u", block->bbNum);
5042             printf(" valueIn  = %s", BitVecOps::ToString(apTraits, block->bbAssertionIn));
5043             printf(" valueOut = %s", BitVecOps::ToString(apTraits, block->bbAssertionOut));
5044             if (block->bbJumpKind == BBJ_COND)
5045             {
5046                 printf(" => BB%02u", block->bbJumpDest->bbNum);
5047                 printf(" valueOut= %s", BitVecOps::ToString(apTraits, bbJtrueAssertionOut[block->bbNum]));
5048             }
5049         }
5050         printf("\n");
5051     }
5052 #endif // DEBUG
5053
5054     ASSERT_TP assertions = BitVecOps::MakeEmpty(apTraits);
5055
5056     // Perform assertion propagation (and constant folding)
5057     for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
5058     {
5059         BitVecOps::Assign(apTraits, assertions, block->bbAssertionIn);
5060
5061         // TODO-Review: EH successor/predecessor iteration seems broken.
5062         // SELF_HOST_TESTS_ARM\jit\Directed\ExcepFilters\fault\fault.exe
5063         if (block->bbCatchTyp == BBCT_FAULT)
5064         {
5065             continue;
5066         }
5067
5068         // Make the current basic block address available globally.
5069         compCurBB           = block;
5070         fgRemoveRestOfBlock = false;
5071
5072         // Walk the statement trees in this basic block
5073         GenTree* stmt = block->FirstNonPhiDef();
5074         while (stmt)
5075         {
5076             noway_assert(stmt->gtOper == GT_STMT);
5077
5078             // Propagation tells us to remove the rest of the block. Remove it.
5079             if (fgRemoveRestOfBlock)
5080             {
5081                 fgRemoveStmt(block, stmt);
5082                 stmt = stmt->gtNext;
5083                 continue;
5084             }
5085
5086             // Preserve the prev link before the propagation and morph, to check if propagation
5087             // removes the current stmt.
5088             GenTree* prev = (stmt == block->firstStmt()) ? nullptr : stmt->gtPrev;
5089
5090             optAssertionPropagatedCurrentStmt = false; // set to true if a assertion propagation took place
5091                                                        // and thus we must morph, set order, re-link
5092             for (GenTree* tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext)
5093             {
5094                 if (tree->OperIs(GT_JTRUE))
5095                 {
5096                     // A GT_TRUE is always the last node in a tree, so we can break here
5097                     assert((tree->gtNext == nullptr) && (stmt->gtNext == nullptr));
5098                     break;
5099                 }
5100
5101                 JITDUMP("Propagating %s assertions for BB%02d, stmt [%06d], tree [%06d], tree -> %d\n",
5102                         BitVecOps::ToString(apTraits, assertions), block->bbNum, dspTreeID(stmt), dspTreeID(tree),
5103                         tree->GetAssertionInfo().GetAssertionIndex());
5104
5105                 GenTree* newTree = optAssertionProp(assertions, tree, stmt);
5106                 if (newTree)
5107                 {
5108                     assert(optAssertionPropagatedCurrentStmt == true);
5109                     tree = newTree;
5110                 }
5111
5112                 // If this tree makes an assertion - make it available.
5113                 if (tree->GeneratesAssertion())
5114                 {
5115                     AssertionInfo info = tree->GetAssertionInfo();
5116                     optImpliedAssertions(info.GetAssertionIndex(), assertions);
5117                     BitVecOps::AddElemD(apTraits, assertions, info.GetAssertionIndex() - 1);
5118                 }
5119             }
5120
5121             if (optAssertionPropagatedCurrentStmt)
5122             {
5123 #ifdef DEBUG
5124                 if (verbose)
5125                 {
5126                     printf("Re-morphing this stmt:\n");
5127                     gtDispTree(stmt);
5128                     printf("\n");
5129                 }
5130 #endif
5131                 // Re-morph the statement.
5132                 fgMorphBlockStmt(block, stmt->AsStmt() DEBUGARG("optAssertionPropMain"));
5133             }
5134
5135             // Check if propagation removed statements starting from current stmt.
5136             // If so, advance to the next good statement.
5137             GenTree* nextStmt = (prev == nullptr) ? block->firstStmt() : prev->gtNext;
5138             stmt              = (stmt == nextStmt) ? stmt->gtNext : nextStmt;
5139         }
5140         optAssertionPropagatedCurrentStmt = false; // clear it back as we are done with stmts.
5141     }
5142
5143 #ifdef DEBUG
5144     fgDebugCheckBBlist();
5145     fgDebugCheckLinks();
5146 #endif
5147
5148     // Assertion propagation may have changed the reference counts
5149     // We need to resort the variable table
5150
5151     if (optAssertionPropagated)
5152     {
5153         lvaSortAgain = true;
5154     }
5155 }