src/jit/loopcloning.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                            LoopCloning                                    XX
   9 XX                                                                           XX
  10 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  11 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  12 */
  13
  14 #include "jitpch.h"
  15
  16 //--------------------------------------------------------------------------------------------------
  17 // ToGenTree - Convert an arrLen operation into a gentree node.
  18 //
  19 // Arguments:
  20 //      comp    Compiler instance to allocate trees
  21 //
  22 // Return Values:
  23 //      Returns the gen tree representation for arrLen or MD Array node as defined by
  24 //      the "type" member
  25 //
  26 // Notes:
  27 //      This tree produces GT_INDEX node, the caller is supposed to morph it appropriately
  28 //      so it can be codegen'ed.
  29 //
  30 GenTree* LC_Array::ToGenTree(Compiler* comp)
  31 {
  32     // If jagged array
  33     if (type == Jagged)
  34     {
  35         // Create a a[i][j][k].length type node.
  36         GenTree* arr  = comp->gtNewLclvNode(arrIndex->arrLcl, comp->lvaTable[arrIndex->arrLcl].lvType);
  37         int      rank = GetDimRank();
  38         for (int i = 0; i < rank; ++i)
  39         {
  40             arr = comp->gtNewIndexRef(TYP_REF, arr, comp->gtNewLclvNode(arrIndex->indLcls[i],
  41                                                                         comp->lvaTable[arrIndex->indLcls[i]].lvType));
  42         }
  43         // If asked for arrlen invoke arr length operator.
  44         if (oper == ArrLen)
  45         {
  46             GenTree* arrLen = comp->gtNewArrLen(TYP_INT, arr, offsetof(CORINFO_Array, length));
  47             return arrLen;
  48         }
  49         else
  50         {
  51             assert(oper == None);
  52             return arr;
  53         }
  54     }
  55     else
  56     {
  57         // TODO-CQ: Optimize for MD Array.
  58         assert(!"Optimize for MD Array");
  59     }
  60     return nullptr;
  61 }
  62
  63 //--------------------------------------------------------------------------------------------------
  64 // ToGenTree - Convert an "identifier" into a gentree node.
  65 //
  66 // Arguments:
  67 //      comp    Compiler instance to allocate trees
  68 //
  69 // Return Values:
  70 //      Returns the gen tree representation for either a constant or a variable or an arrLen operation
  71 //      defined by the "type" member
  72 //
  73 GenTree* LC_Ident::ToGenTree(Compiler* comp)
  74 {
  75     // Convert to GenTree nodes.
  76     switch (type)
  77     {
  78         case Const:
  79             assert(constant <= INT32_MAX);
  80             return comp->gtNewIconNode(constant);
  81         case Var:
  82             return comp->gtNewLclvNode(constant, comp->lvaTable[constant].lvType);
  83         case ArrLen:
  84             return arrLen.ToGenTree(comp);
  85         case Null:
  86             return comp->gtNewIconNode(0, TYP_REF);
  87         default:
  88             assert(!"Could not convert LC_Ident to GenTree");
  89             unreached();
  90             break;
  91     }
  92 }
  93
  94 //--------------------------------------------------------------------------------------------------
  95 // ToGenTree - Convert an "expression" into a gentree node.
  96 //
  97 // Arguments:
  98 //      comp    Compiler instance to allocate trees
  99 //
 100 // Return Values:
 101 //      Returns the gen tree representation for either a constant or a variable or an arrLen operation
 102 //      defined by the "type" member
 103 //
 104 GenTree* LC_Expr::ToGenTree(Compiler* comp)
 105 {
 106     // Convert to GenTree nodes.
 107     switch (type)
 108     {
 109         case Ident:
 110             return ident.ToGenTree(comp);
 111         default:
 112             assert(!"Could not convert LC_Expr to GenTree");
 113             unreached();
 114             break;
 115     }
 116 }
 117
 118 //--------------------------------------------------------------------------------------------------
 119 // ToGenTree - Convert a "condition" into a gentree node.
 120 //
 121 // Arguments:
 122 //      comp    Compiler instance to allocate trees
 123 //
 124 // Return Values:
 125 //      Returns the gen tree representation for the conditional operator on lhs and rhs trees
 126 //
 127 GenTree* LC_Condition::ToGenTree(Compiler* comp)
 128 {
 129     GenTree* op1Tree = op1.ToGenTree(comp);
 130     GenTree* op2Tree = op2.ToGenTree(comp);
 131     assert(genTypeSize(genActualType(op1Tree->TypeGet())) == genTypeSize(genActualType(op2Tree->TypeGet())));
 132     return comp->gtNewOperNode(oper, TYP_INT, op1Tree, op2Tree);
 133 }
 134
 135 //--------------------------------------------------------------------------------------------------
 136 // Evaluates - Evaluate a given loop cloning condition if it can be statically evaluated.
 137 //
 138 // Arguments:
 139 //      pResult     The evaluation result
 140 //
 141 // Return Values:
 142 //      Returns true if the condition can be statically evaluated. If the condition's result
 143 //      is statically unknown then return false. In other words, true if "pResult" is valid.
 144 //
 145 bool LC_Condition::Evaluates(bool* pResult)
 146 {
 147     switch (oper)
 148     {
 149         case GT_EQ:
 150         case GT_GE:
 151         case GT_LE:
 152             // If op1 == op2 then equality should result in true.
 153             if (op1 == op2)
 154             {
 155                 *pResult = true;
 156                 return true;
 157             }
 158             break;
 159
 160         case GT_GT:
 161         case GT_LT:
 162         case GT_NE:
 163             // If op1 == op2 then inequality should result in false.
 164             if (op1 == op2)
 165             {
 166                 *pResult = false;
 167                 return true;
 168             }
 169             break;
 170
 171         default:
 172             // for all other 'oper' kinds, we will return false
 173             break;
 174     }
 175     return false;
 176 }
 177
 178 //--------------------------------------------------------------------------------------------------
 179 // Combines - Check whether two conditions would combine to yield a single new condition.
 180 //
 181 // Arguments:
 182 //      cond        The condition that is checked if it would combine with "*this" condition.
 183 //      newCond     The resulting combined condition.
 184 //
 185 // Return Values:
 186 //      Returns true if "cond" combines with the "this" condition.
 187 //      "newCond" contains the combines condition.
 188 //
 189 // Operation:
 190 //      Check if both conditions are equal. If so, return just 1 of them.
 191 //      Reverse their operators and check if their reversed operands match. If so, return either of them.
 192 //
 193 // Notes:
 194 //      This is not a full-fledged expression optimizer, it is supposed
 195 //      to remove redundant conditions that are generated for optimization
 196 //      opportunities. Anything further should be implemented as needed.
 197 //      For example, for (i = beg; i < end; i += inc) a[i]. Then, the conditions
 198 //      would be: "beg >= 0, end <= a.len, inc > 0"
 199 bool LC_Condition::Combines(const LC_Condition& cond, LC_Condition* newCond)
 200 {
 201     if (oper == cond.oper && op1 == cond.op1 && op2 == cond.op2)
 202     {
 203         *newCond = *this;
 204         return true;
 205     }
 206     else if ((oper == GT_LT || oper == GT_LE || oper == GT_GT || oper == GT_GE) &&
 207              GenTree::ReverseRelop(oper) == cond.oper && op1 == cond.op2 && op2 == cond.op1)
 208     {
 209         *newCond = *this;
 210         return true;
 211     }
 212     return false;
 213 }
 214
 215 //--------------------------------------------------------------------------------------------------
 216 // GetLoopOptInfo - Retrieve the loop opt info candidate array.
 217 //
 218 // Arguments:
 219 //      loopNum     the loop index.
 220 //
 221 // Return Values:
 222 //      Return the optInfo array member. The method doesn't allocate memory.
 223 //
 224 JitExpandArrayStack<LcOptInfo*>* LoopCloneContext::GetLoopOptInfo(unsigned loopNum)
 225 {
 226     return optInfo[loopNum];
 227 }
 228
 229 //--------------------------------------------------------------------------------------------------
 230 // CancelLoopOptInfo - Cancel loop cloning optimization for this loop.
 231 //
 232 // Arguments:
 233 //      loopNum     the loop index.
 234 //
 235 // Return Values:
 236 //      None.
 237 //
 238 void LoopCloneContext::CancelLoopOptInfo(unsigned loopNum)
 239 {
 240     JITDUMP("Cancelling loop cloning for loop L_%02u\n", loopNum);
 241     optInfo[loopNum] = nullptr;
 242     if (conditions[loopNum] != nullptr)
 243     {
 244         conditions[loopNum]->Reset();
 245         conditions[loopNum] = nullptr;
 246     }
 247 }
 248
 249 //--------------------------------------------------------------------------------------------------
 250 // EnsureLoopOptInfo - Retrieve the loop opt info candidate array, if it is not present, allocate
 251 //      memory.
 252 //
 253 // Arguments:
 254 //      loopNum     the loop index.
 255 //
 256 // Return Values:
 257 //      The array of optimization candidates for the loop.
 258 //
 259 JitExpandArrayStack<LcOptInfo*>* LoopCloneContext::EnsureLoopOptInfo(unsigned loopNum)
 260 {
 261     if (optInfo[loopNum] == nullptr)
 262     {
 263         optInfo[loopNum] = new (alloc) JitExpandArrayStack<LcOptInfo*>(alloc, 4);
 264     }
 265     return optInfo[loopNum];
 266 }
 267
 268 //--------------------------------------------------------------------------------------------------
 269 // EnsureLoopOptInfo - Retrieve the loop cloning conditions candidate array,
 270 //      if it is not present, allocate memory.
 271 //
 272 // Arguments:
 273 //      loopNum     the loop index.
 274 //
 275 // Return Values:
 276 //      The array of cloning conditions for the loop.
 277 //
 278 JitExpandArrayStack<LC_Condition>* LoopCloneContext::EnsureConditions(unsigned loopNum)
 279 {
 280     if (conditions[loopNum] == nullptr)
 281     {
 282         conditions[loopNum] = new (alloc) JitExpandArrayStack<LC_Condition>(alloc, 4);
 283     }
 284     return conditions[loopNum];
 285 }
 286
 287 //--------------------------------------------------------------------------------------------------
 288 // GetConditions - Get the cloning conditions array for the loop, no allocation.
 289 //
 290 // Arguments:
 291 //      loopNum     the loop index.
 292 //
 293 // Return Values:
 294 //      The array of cloning conditions for the loop.
 295 //
 296 JitExpandArrayStack<LC_Condition>* LoopCloneContext::GetConditions(unsigned loopNum)
 297 {
 298     return conditions[loopNum];
 299 }
 300
 301 //--------------------------------------------------------------------------------------------------
 302 // EnsureDerefs - Ensure an array of dereferences is created if it doesn't exist.
 303 //
 304 // Arguments:
 305 //      loopNum     the loop index.
 306 //
 307 // Return Values:
 308 //      The array of dereferences for the loop.
 309 //
 310 JitExpandArrayStack<LC_Array>* LoopCloneContext::EnsureDerefs(unsigned loopNum)
 311 {
 312     if (derefs[loopNum] == nullptr)
 313     {
 314         derefs[loopNum] = new (alloc) JitExpandArrayStack<LC_Array>(alloc, 4);
 315     }
 316     return derefs[loopNum];
 317 }
 318
 319 //--------------------------------------------------------------------------------------------------
 320 // HasBlockConditions - Check if there are block level conditions for the loop.
 321 //
 322 // Arguments:
 323 //      loopNum     the loop index.
 324 //
 325 // Return Values:
 326 //      Return true if there are any block level conditions.
 327 //
 328 bool LoopCloneContext::HasBlockConditions(unsigned loopNum)
 329 {
 330     JitExpandArrayStack<JitExpandArrayStack<LC_Condition>*>* levelCond = blockConditions[loopNum];
 331     if (levelCond == nullptr)
 332     {
 333         return false;
 334     }
 335
 336     // Walk through each block to check if any of them has conditions.
 337     for (unsigned i = 0; i < levelCond->Size(); ++i)
 338     {
 339         if ((*levelCond)[i]->Size() > 0)
 340         {
 341             return true;
 342         }
 343     }
 344     return false;
 345 }
 346
 347 //--------------------------------------------------------------------------------------------------
 348 // GetBlockConditions - Return block level conditions for the loop.
 349 //
 350 // Arguments:
 351 //      loopNum     the loop index.
 352 //
 353 // Return Values:
 354 //      Return block conditions.
 355 //
 356 JitExpandArrayStack<JitExpandArrayStack<LC_Condition>*>* LoopCloneContext::GetBlockConditions(unsigned loopNum)
 357 {
 358     assert(HasBlockConditions(loopNum));
 359     return blockConditions[loopNum];
 360 }
 361
 362 //--------------------------------------------------------------------------------------------------
 363 // EnsureBlockConditions - Allocate block level conditions for the loop if not exists.
 364 //
 365 // Arguments:
 366 //      loopNum     the loop index.
 367 //      condBlocks  the number of block-level conditions for each loop, corresponding to the blocks
 368 //                  created.
 369 //
 370 // Return Values:
 371 //      Return block conditions.
 372 //
 373 JitExpandArrayStack<JitExpandArrayStack<LC_Condition>*>* LoopCloneContext::EnsureBlockConditions(unsigned loopNum,
 374                                                                                                  unsigned condBlocks)
 375 {
 376     if (blockConditions[loopNum] == nullptr)
 377     {
 378         blockConditions[loopNum] =
 379             new (alloc) JitExpandArrayStack<JitExpandArrayStack<LC_Condition>*>(alloc, condBlocks);
 380     }
 381     JitExpandArrayStack<JitExpandArrayStack<LC_Condition>*>* levelCond = blockConditions[loopNum];
 382     for (unsigned i = 0; i < condBlocks; ++i)
 383     {
 384         levelCond->Set(i, new (alloc) JitExpandArrayStack<LC_Condition>(alloc));
 385     }
 386     return levelCond;
 387 }
 388
 389 #ifdef DEBUG
 390 void LoopCloneContext::PrintBlockConditions(unsigned loopNum)
 391 {
 392     JitExpandArrayStack<JitExpandArrayStack<LC_Condition>*>* levelCond = blockConditions[loopNum];
 393     if (levelCond == nullptr || levelCond->Size() == 0)
 394     {
 395         JITDUMP("No block conditions\n");
 396         return;
 397     }
 398
 399     for (unsigned i = 0; i < levelCond->Size(); ++i)
 400     {
 401         JITDUMP("%d = {", i);
 402         for (unsigned j = 0; j < ((*levelCond)[i])->Size(); ++j)
 403         {
 404             if (j != 0)
 405             {
 406                 JITDUMP(" & ");
 407             }
 408             (*((*levelCond)[i]))[j].Print();
 409         }
 410         JITDUMP("}\n");
 411     }
 412 }
 413 #endif
 414
 415 //--------------------------------------------------------------------------------------------------
 416 // EvaluateConditions - Evaluate the loop cloning conditions statically, if it can be evaluated.
 417 //
 418 // Arguments:
 419 //      loopNum     the loop index.
 420 //      pAllTrue    all the cloning conditions evaluated to "true" statically.
 421 //      pAnyFalse   some cloning condition evaluated to "false" statically.
 422 //      verbose     verbose logging required.
 423 //
 424 // Return Values:
 425 //      None.
 426 //
 427 // Operation:
 428 //      For example, a condition like "V02 >= V02" statically evaluates to true. Caller should detect such
 429 //      conditions and remove them from the "conditions" array.
 430 //
 431 //      Similarly, conditions like "V02 > V02" will evaluate to "false". In this case caller has to abort
 432 //      loop cloning optimization for the loop. Note that the assumption for conditions is that they will
 433 //      all be "AND"ed, so statically we know we will never take the fast path.
 434 //
 435 //      Sometimes we simply can't say statically whether "V02 > V01.length" is true or false.
 436 //      In that case, the "pAllTrue" will be false because this condition doesn't evaluate to "true" and
 437 //      "pAnyFalse" could be false if no other condition statically evaluates to "false".
 438 void LoopCloneContext::EvaluateConditions(unsigned loopNum, bool* pAllTrue, bool* pAnyFalse DEBUGARG(bool verbose))
 439 {
 440     bool allTrue  = true;
 441     bool anyFalse = false;
 442
 443     JitExpandArrayStack<LC_Condition>& conds = *conditions[loopNum];
 444
 445     JITDUMP("Evaluating %d loop cloning conditions for loop %d\n", conds.Size(), loopNum);
 446
 447     assert(conds.Size() > 0);
 448     for (unsigned i = 0; i < conds.Size(); ++i)
 449     {
 450 #ifdef DEBUG
 451         if (verbose)
 452         {
 453             printf("Considering condition %d: (", i);
 454             conds[i].Print();
 455         }
 456 #endif
 457
 458         bool res = false;
 459         // Check if this condition evaluates to true or false.
 460         if (conds[i].Evaluates(&res))
 461         {
 462             JITDUMP(") evaluates to %d\n", res);
 463             if (!res)
 464             {
 465                 anyFalse = true;
 466                 return;
 467             }
 468         }
 469         else
 470         {
 471             JITDUMP("), could not be evaluated\n");
 472             allTrue = false;
 473         }
 474     }
 475
 476     JITDUMP("Evaluation result allTrue = %d, anyFalse = %d\n", allTrue, anyFalse);
 477     *pAllTrue  = allTrue;
 478     *pAnyFalse = anyFalse;
 479 }
 480
 481 //--------------------------------------------------------------------------------------------------
 482 // OptimizeConditions - Evaluate the loop cloning conditions statically, if they can be evaluated
 483 //      then optimize the "conditions" array accordingly.
 484 //
 485 // Arguments:
 486 //      conds   The conditions array to optimize.
 487 //
 488 // Return Values:
 489 //      None.
 490 //
 491 // Operation:
 492 //      For example, a condition like "V02 >= V02" statically evaluates to true. Remove such conditions
 493 //      from the "conditions" array.
 494 //
 495 //      Similarly, conditions like "V02 > V02" will evaluate to "false". In this case abort loop cloning
 496 //      optimization for the loop.
 497 //
 498 //      Sometimes, two conditions will combine together to yield a single condition, then remove a
 499 //      duplicate condition.
 500 void LoopCloneContext::OptimizeConditions(JitExpandArrayStack<LC_Condition>& conds)
 501 {
 502     for (unsigned i = 0; i < conds.Size(); ++i)
 503     {
 504         // Check if the conditions evaluate.
 505         bool result = false;
 506         if (conds[i].Evaluates(&result))
 507         {
 508             // If statically known to be true, then remove this condition.
 509             if (result)
 510             {
 511                 conds.Remove(i);
 512                 --i;
 513                 continue;
 514             }
 515             else
 516             {
 517                 // Some condition is statically false, then simply indicate
 518                 // not to clone this loop.
 519                 CancelLoopOptInfo(i);
 520                 break;
 521             }
 522         }
 523
 524         // Check for all other conditions[j], if it would combine with
 525         // conditions[i].
 526         for (unsigned j = i + 1; j < conds.Size(); ++j)
 527         {
 528             LC_Condition newCond;
 529             if (conds[i].Combines(conds[j], &newCond))
 530             {
 531                 conds.Remove(j);
 532                 conds[i] = newCond;
 533                 i        = -1;
 534                 break;
 535             }
 536         }
 537     }
 538 #ifdef DEBUG
 539     // Make sure we didn't miss some combining.
 540     for (unsigned i = 0; i < conds.Size(); ++i)
 541     {
 542         for (unsigned j = 0; j < conds.Size(); ++j)
 543         {
 544             LC_Condition newCond;
 545             if ((i != j) && conds[i].Combines(conds[j], &newCond))
 546             {
 547                 assert(!"Loop cloning conditions can still be optimized further.");
 548             }
 549         }
 550     }
 551 #endif
 552 }
 553
 554 //--------------------------------------------------------------------------------------------------
 555 // OptimizeBlockConditions - Optimize block level conditions.
 556 //
 557 // Arguments:
 558 //      loopNum     the loop index.
 559 //
 560 // Operation:
 561 //       Calls OptimizeConditions helper on block level conditions.
 562 //
 563 // Return Values:
 564 //      None.
 565 //
 566 void LoopCloneContext::OptimizeBlockConditions(unsigned loopNum DEBUGARG(bool verbose))
 567 {
 568     if (!HasBlockConditions(loopNum))
 569     {
 570         return;
 571     }
 572     JitExpandArrayStack<JitExpandArrayStack<LC_Condition>*>* levelCond = blockConditions[loopNum];
 573     for (unsigned i = 0; i < levelCond->Size(); ++i)
 574     {
 575         OptimizeConditions(*((*levelCond)[i]));
 576     }
 577 #ifdef DEBUG
 578     if (verbose)
 579     {
 580         printf("After optimizing block-level cloning conditions\n\t");
 581         PrintConditions(loopNum);
 582         printf("\n");
 583     }
 584 #endif
 585 }
 586
 587 //--------------------------------------------------------------------------------------------------
 588 // OptimizeConditions - Optimize cloning conditions.
 589 //
 590 // Arguments:
 591 //      loopNum     the loop index.
 592 //      verbose     verbose logging required.
 593 //
 594 // Operation:
 595 //       Calls OptimizeConditions helper on cloning conditions.
 596 //
 597 // Return Values:
 598 //      None.
 599 //
 600 void LoopCloneContext::OptimizeConditions(unsigned loopNum DEBUGARG(bool verbose))
 601 {
 602 #ifdef DEBUG
 603     if (verbose)
 604     {
 605         printf("Before optimizing cloning conditions\n\t");
 606         PrintConditions(loopNum);
 607         printf("\n");
 608     }
 609 #endif
 610     JitExpandArrayStack<LC_Condition>& conds = *conditions[loopNum];
 611     OptimizeConditions(conds);
 612
 613 #ifdef DEBUG
 614     if (verbose)
 615     {
 616         printf("After optimizing cloning conditions\n\t");
 617         PrintConditions(loopNum);
 618         printf("\n");
 619     }
 620 #endif
 621 }
 622
 623 #ifdef DEBUG
 624 //--------------------------------------------------------------------------------------------------
 625 // PrintConditions - Print loop cloning conditions necessary to clone the loop.
 626 //
 627 // Arguments:
 628 //      loopNum     the loop index.
 629 //
 630 // Return Values:
 631 //      None.
 632 //
 633 void LoopCloneContext::PrintConditions(unsigned loopNum)
 634 {
 635     if (conditions[loopNum] == nullptr)
 636     {
 637         JITDUMP("NO conditions");
 638         return;
 639     }
 640     if (conditions[loopNum]->Size() == 0)
 641     {
 642         JITDUMP("Conditions were optimized away! Will always take cloned path.");
 643     }
 644     for (unsigned i = 0; i < conditions[loopNum]->Size(); ++i)
 645     {
 646         if (i != 0)
 647         {
 648             JITDUMP(" & ");
 649         }
 650         (*conditions[loopNum])[i].Print();
 651     }
 652 }
 653 #endif
 654
 655 //--------------------------------------------------------------------------------------------------
 656 // CondToStmtInBlock - Convert an array of conditions. Evaluate them into a JTRUE stmt and add it to
 657 //      the block
 658 //
 659 // Arguments:
 660 //      comp    Compiler instance
 661 //      conds   Array of conditions to evaluate into a JTRUE stmt
 662 //      block   Block to insert the stmt into
 663 //      reverse Reverse conditions if true.
 664 //
 665 // Note:
 666 //      The condition that will be generated: jmpTrue(cond1 & cond2 ... == 0)
 667 //
 668 // Return Values:
 669 //      None.
 670 //
 671 void LoopCloneContext::CondToStmtInBlock(Compiler*                          comp,
 672                                          JitExpandArrayStack<LC_Condition>& conds,
 673                                          BasicBlock*                        block,
 674                                          bool                               reverse)
 675 {
 676     noway_assert(conds.Size() > 0);
 677
 678     // Get the first condition.
 679     GenTree* cond = conds[0].ToGenTree(comp);
 680     for (unsigned i = 1; i < conds.Size(); ++i)
 681     {
 682         // Append all conditions using AND operator.
 683         cond = comp->gtNewOperNode(GT_AND, TYP_INT, cond, conds[i].ToGenTree(comp));
 684     }
 685
 686     // Add "cond == 0" node
 687     cond = comp->gtNewOperNode(reverse ? GT_NE : GT_EQ, TYP_INT, cond, comp->gtNewIconNode(0));
 688
 689     // Add jmpTrue "cond == 0" to slow path.
 690     GenTree* stmt = comp->fgNewStmtFromTree(comp->gtNewOperNode(GT_JTRUE, TYP_VOID, cond));
 691
 692     // Add stmt to the block.
 693     comp->fgInsertStmtAtEnd(block, stmt);
 694
 695     // Remorph.
 696     comp->fgMorphBlockStmt(block, stmt->AsStmt() DEBUGARG("Loop cloning condition"));
 697 }
 698
 699 //--------------------------------------------------------------------------------------------------
 700 // Lcl - the current node's local variable.
 701 //
 702 // Arguments:
 703 //      None.
 704 //
 705 // Operation:
 706 //      If level is 0, then just return the array base. Else return the index variable on dim 'level'
 707 //
 708 // Return Values:
 709 //      The local variable in the node's level.
 710 //
 711 unsigned LC_Deref::Lcl()
 712 {
 713     unsigned lvl = level;
 714     if (lvl == 0)
 715     {
 716         return array.arrIndex->arrLcl;
 717     }
 718     lvl--;
 719     return array.arrIndex->indLcls[lvl];
 720 }
 721
 722 //--------------------------------------------------------------------------------------------------
 723 // HasChildren - Check if there are children to 'this' node.
 724 //
 725 // Arguments:
 726 //      None.
 727 //
 728 // Return Values:
 729 //      Return true if children are present.
 730 //
 731 bool LC_Deref::HasChildren()
 732 {
 733     return children != nullptr && children->Size() > 0;
 734 }
 735
 736 //--------------------------------------------------------------------------------------------------
 737 // DeriveLevelConditions - Generate conditions for each level of the tree.
 738 //
 739 // Arguments:
 740 //      conds       An array of conditions for each level i.e., (level x conditions). This array will
 741 //                  contain the conditions for the tree at the end of the method.
 742 //
 743 // Operation:
 744 //      level0 yields only (a != null) condition. All other levels yield two conditions:
 745 //      (level < a[...].length && a[...][level] != null)
 746 //
 747 // Return Values:
 748 //      None
 749 //
 750 void LC_Deref::DeriveLevelConditions(JitExpandArrayStack<JitExpandArrayStack<LC_Condition>*>* conds)
 751 {
 752     if (level == 0)
 753     {
 754         // For level 0, just push (a != null).
 755         (*conds)[level]->Push(
 756             LC_Condition(GT_NE, LC_Expr(LC_Ident(Lcl(), LC_Ident::Var)), LC_Expr(LC_Ident(LC_Ident::Null))));
 757     }
 758     else
 759     {
 760         // Adjust for level0 having just 1 condition and push condition (i < a.len).
 761         LC_Array arrLen = array;
 762         arrLen.oper     = LC_Array::ArrLen;
 763         arrLen.dim      = level - 1;
 764         (*conds)[level * 2 - 1]->Push(
 765             LC_Condition(GT_LT, LC_Expr(LC_Ident(Lcl(), LC_Ident::Var)), LC_Expr(LC_Ident(arrLen))));
 766
 767         // Push condition (a[i] != null)
 768         LC_Array arrTmp = array;
 769         arrTmp.dim      = level;
 770         (*conds)[level * 2]->Push(LC_Condition(GT_NE, LC_Expr(LC_Ident(arrTmp)), LC_Expr(LC_Ident(LC_Ident::Null))));
 771     }
 772
 773     // Invoke on the children recursively.
 774     if (HasChildren())
 775     {
 776         for (unsigned i = 0; i < children->Size(); ++i)
 777         {
 778             (*children)[i]->DeriveLevelConditions(conds);
 779         }
 780     }
 781 }
 782
 783 //--------------------------------------------------------------------------------------------------
 784 // EnsureChildren - Create an array of child nodes if nullptr.
 785 //
 786 // Arguments:
 787 //      alloc   CompAllocator instance
 788 //
 789 // Return Values:
 790 //      None
 791 //
 792 void LC_Deref::EnsureChildren(CompAllocator* alloc)
 793 {
 794     if (children == nullptr)
 795     {
 796         children = new (alloc) JitExpandArrayStack<LC_Deref*>(alloc);
 797     }
 798 }
 799
 800 //--------------------------------------------------------------------------------------------------
 801 // Find - Find the node representing the local variable in child nodes of the 'this' node.
 802 //
 803 // Arguments:
 804 //      lcl     the local to find in the children array
 805 //
 806 // Return Values:
 807 //      The child node if found or nullptr.
 808 //
 809 LC_Deref* LC_Deref::Find(unsigned lcl)
 810 {
 811     return Find(children, lcl);
 812 }
 813
 814 //--------------------------------------------------------------------------------------------------
 815 // Find - Find the node representing the local variable in a list of nodes.
 816 //
 817 // Arguments:
 818 //      lcl          the local to find.
 819 //      children     the list of nodes to find the node representing the lcl.
 820 //
 821 // Return Values:
 822 //      The node if found or nullptr.
 823 //
 824
 825 // static
 826 LC_Deref* LC_Deref::Find(JitExpandArrayStack<LC_Deref*>* children, unsigned lcl)
 827 {
 828     if (children == nullptr)
 829     {
 830         return nullptr;
 831     }
 832     for (unsigned i = 0; i < children->Size(); ++i)
 833     {
 834         if ((*children)[i]->Lcl() == lcl)
 835         {
 836             return (*children)[i];
 837         }
 838     }
 839     return nullptr;
 840 }