src/jit/ssabuilder.cpp

   1 // Licensed to the .NET Foundation under one or more agreements.
   2 // The .NET Foundation licenses this file to you under the MIT license.
   3 // See the LICENSE file in the project root for more information.
   4
   5 // ==++==
   6 //
   7
   8 //
   9
  10 //
  11 // ==--==
  12
  13 /*XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  14 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  15 XX                                                                           XX
  16 XX                                  SSA                                      XX
  17 XX                                                                           XX
  18 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  19 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  20 */
  21
  22 #include "jitpch.h"
  23 #include "ssaconfig.h"
  24 #include "ssarenamestate.h"
  25 #include "ssabuilder.h"
  26
  27 namespace
  28 {
  29 /**
  30  * Method that finds a common IDom parent, much like least common ancestor.
  31  *
  32  * @param finger1 A basic block that might share IDom ancestor with finger2.
  33  * @param finger2 A basic block that might share IDom ancestor with finger1.
  34  *
  35  * @see "A simple, fast dominance algorithm" by Keith D. Cooper, Timothy J. Harvey, Ken Kennedy.
  36  *
  37  * @return A basic block whose IDom is the dominator for finger1 and finger2,
  38  * or else NULL.  This may be called while immediate dominators are being
  39  * computed, and if the input values are members of the same loop (each reachable from the other),
  40  * then one may not yet have its immediate dominator computed when we are attempting
  41  * to find the immediate dominator of the other.  So a NULL return value means that the
  42  * the two inputs are in a cycle, not that they don't have a common dominator ancestor.
  43  */
  44 static inline BasicBlock* IntersectDom(BasicBlock* finger1, BasicBlock* finger2)
  45 {
  46     while (finger1 != finger2)
  47     {
  48         if (finger1 == nullptr || finger2 == nullptr)
  49         {
  50             return nullptr;
  51         }
  52         while (finger1 != nullptr && finger1->bbPostOrderNum < finger2->bbPostOrderNum)
  53         {
  54             finger1 = finger1->bbIDom;
  55         }
  56         if (finger1 == nullptr)
  57         {
  58             return nullptr;
  59         }
  60         while (finger2 != nullptr && finger2->bbPostOrderNum < finger1->bbPostOrderNum)
  61         {
  62             finger2 = finger2->bbIDom;
  63         }
  64     }
  65     return finger1;
  66 }
  67
  68 } // end of anonymous namespace.
  69
  70 // =================================================================================
  71 //                                      SSA
  72 // =================================================================================
  73
  74 void Compiler::fgSsaBuild()
  75 {
  76     IAllocator* pIAllocator = new (this, CMK_SSA) CompAllocator(this, CMK_SSA);
  77
  78     // If this is not the first invocation, reset data structures for SSA.
  79     if (fgSsaPassesCompleted > 0)
  80     {
  81         fgResetForSsa();
  82     }
  83
  84     SsaBuilder builder(this, pIAllocator);
  85     builder.Build();
  86     fgSsaPassesCompleted++;
  87 #ifdef DEBUG
  88     JitTestCheckSSA();
  89 #endif // DEBUG
  90
  91 #ifdef DEBUG
  92     if (verbose)
  93     {
  94         JITDUMP("\nAfter fgSsaBuild:\n");
  95         fgDispBasicBlocks(/*dumpTrees*/ true);
  96     }
  97 #endif // DEBUG
  98 }
  99
 100 void Compiler::fgResetForSsa()
 101 {
 102     for (unsigned i = 0; i < lvaCount; ++i)
 103     {
 104         lvaTable[i].lvPerSsaData.Reset();
 105     }
 106     lvMemoryPerSsaData.Reset();
 107     for (MemoryKind memoryKind : allMemoryKinds())
 108     {
 109         m_memorySsaMap[memoryKind] = nullptr;
 110     }
 111
 112     for (BasicBlock* blk = fgFirstBB; blk != nullptr; blk = blk->bbNext)
 113     {
 114         // Eliminate phis.
 115         for (MemoryKind memoryKind : allMemoryKinds())
 116         {
 117             blk->bbMemorySsaPhiFunc[memoryKind] = nullptr;
 118         }
 119         if (blk->bbTreeList != nullptr)
 120         {
 121             GenTreePtr last = blk->bbTreeList->gtPrev;
 122             blk->bbTreeList = blk->FirstNonPhiDef();
 123             if (blk->bbTreeList != nullptr)
 124             {
 125                 blk->bbTreeList->gtPrev = last;
 126             }
 127         }
 128
 129         // Clear post-order numbers and SSA numbers; SSA construction will overwrite these,
 130         // but only for reachable code, so clear them to avoid analysis getting confused
 131         // by stale annotations in unreachable code.
 132         blk->bbPostOrderNum = 0;
 133         for (GenTreeStmt* stmt = blk->firstStmt(); stmt != nullptr; stmt = stmt->getNextStmt())
 134         {
 135             for (GenTreePtr tree = stmt->gtStmt.gtStmtList; tree != nullptr; tree = tree->gtNext)
 136             {
 137                 if (tree->IsLocal())
 138                 {
 139                     tree->gtLclVarCommon.SetSsaNum(SsaConfig::RESERVED_SSA_NUM);
 140                     continue;
 141                 }
 142
 143                 Compiler::IndirectAssignmentAnnotation* pIndirAssign = nullptr;
 144                 if ((tree->OperGet() != GT_ASG) || !GetIndirAssignMap()->Lookup(tree, &pIndirAssign) ||
 145                     (pIndirAssign == nullptr))
 146                 {
 147                     continue;
 148                 }
 149
 150                 pIndirAssign->m_defSsaNum = SsaConfig::RESERVED_SSA_NUM;
 151                 pIndirAssign->m_useSsaNum = SsaConfig::RESERVED_SSA_NUM;
 152             }
 153         }
 154     }
 155 }
 156
 157 /**
 158  *  Constructor for the SSA builder.
 159  *
 160  *  @param pCompiler Current compiler instance.
 161  *
 162  *  @remarks Initializes the class and member pointers/objects that use constructors.
 163  */
 164 SsaBuilder::SsaBuilder(Compiler* pCompiler, IAllocator* pIAllocator)
 165     : m_pCompiler(pCompiler)
 166     , m_allocator(pIAllocator)
 167
 168 #ifdef SSA_FEATURE_DOMARR
 169     , m_pDomPreOrder(NULL)
 170     , m_pDomPostOrder(NULL)
 171 #endif
 172 #ifdef SSA_FEATURE_USEDEF
 173     , m_uses(jitstd::allocator<void>(pIAllocator))
 174     , m_defs(jitstd::allocator<void>(pIAllocator))
 175 #endif
 176 {
 177 }
 178
 179 //------------------------------------------------------------------------
 180 //  TopologicalSort: Topologically sort the graph and return the number of nodes visited.
 181 //
 182 //  Arguments:
 183 //     postOrder - The array in which the arranged basic blocks have to be returned.
 184 //     count - The size of the postOrder array.
 185 //
 186 //  Return Value:
 187 //     The number of nodes visited while performing DFS on the graph.
 188
 189 int SsaBuilder::TopologicalSort(BasicBlock** postOrder, int count)
 190 {
 191     Compiler* comp = m_pCompiler;
 192
 193     BitVecTraits traits(comp->fgBBNumMax + 1, comp);
 194     BitVec       BITVEC_INIT_NOCOPY(visited, BitVecOps::MakeEmpty(&traits));
 195
 196     // Display basic blocks.
 197     DBEXEC(VERBOSE, comp->fgDispBasicBlocks());
 198     DBEXEC(VERBOSE, comp->fgDispHandlerTab());
 199
 200     // Compute order.
 201     int         postIndex = 0;
 202     BasicBlock* block     = comp->fgFirstBB;
 203     BitVecOps::AddElemD(&traits, visited, block->bbNum);
 204
 205     ArrayStack<BasicBlock*>      blocks(comp);
 206     ArrayStack<AllSuccessorIter> iterators(comp);
 207     ArrayStack<AllSuccessorIter> ends(comp);
 208
 209     // there are three stacks used here and all should be same height
 210     // the first is for blocks
 211     // the second is the iterator to keep track of what succ of the block we are looking at
 212     // and the third is the end marker iterator
 213     blocks.Push(block);
 214     iterators.Push(block->GetAllSuccs(comp).begin());
 215     ends.Push(block->GetAllSuccs(comp).end());
 216
 217     while (blocks.Height() > 0)
 218     {
 219         block = blocks.Top();
 220
 221 #ifdef DEBUG
 222         if (comp->verboseSsa)
 223         {
 224             printf("[SsaBuilder::TopologicalSort] Visiting BB%02u: ", block->bbNum);
 225             printf("[");
 226             unsigned numSucc = block->NumSucc(comp);
 227             for (unsigned i = 0; i < numSucc; ++i)
 228             {
 229                 printf("BB%02u, ", block->GetSucc(i, comp)->bbNum);
 230             }
 231             EHSuccessorIter end = block->GetEHSuccs(comp).end();
 232             for (EHSuccessorIter ehsi = block->GetEHSuccs(comp).begin(); ehsi != end; ++ehsi)
 233             {
 234                 printf("[EH]BB%02u, ", (*ehsi)->bbNum);
 235             }
 236             printf("]\n");
 237         }
 238 #endif
 239
 240         if (iterators.TopRef() != ends.TopRef())
 241         {
 242             // if the block on TOS still has unreached successors, visit them
 243             AllSuccessorIter& iter = iterators.TopRef();
 244             BasicBlock*       succ = *iter;
 245             ++iter;
 246
 247             // push the children
 248             if (!BitVecOps::IsMember(&traits, visited, succ->bbNum))
 249             {
 250                 blocks.Push(succ);
 251                 iterators.Push(succ->GetAllSuccs(comp).begin());
 252                 ends.Push(succ->GetAllSuccs(comp).end());
 253                 BitVecOps::AddElemD(&traits, visited, succ->bbNum);
 254             }
 255         }
 256         else
 257         {
 258             // all successors have been visited
 259             blocks.Pop();
 260             iterators.Pop();
 261             ends.Pop();
 262
 263             postOrder[postIndex]  = block;
 264             block->bbPostOrderNum = postIndex;
 265             postIndex += 1;
 266
 267             DBG_SSA_JITDUMP("postOrder[%d] = [%p] and BB%02u\n", postIndex, dspPtr(block), block->bbNum);
 268         }
 269     }
 270
 271     // In the absence of EH (because catch/finally have no preds), this should be valid.
 272     // assert(postIndex == (count - 1));
 273
 274     return postIndex;
 275 }
 276
 277 /**
 278  * Computes the immediate dominator IDom for each block iteratively.
 279  *
 280  * @param postOrder The array of basic blocks arranged in postOrder.
 281  * @param count The size of valid elements in the postOrder array.
 282  *
 283  * @see "A simple, fast dominance algorithm." paper.
 284  */
 285 void SsaBuilder::ComputeImmediateDom(BasicBlock** postOrder, int count)
 286 {
 287     JITDUMP("[SsaBuilder::ComputeImmediateDom]\n");
 288
 289     // TODO-Cleanup: We currently have two dominance computations happening.  We should unify them; for
 290     // now, at least forget the results of the first.
 291     for (BasicBlock* blk = m_pCompiler->fgFirstBB; blk != nullptr; blk = blk->bbNext)
 292     {
 293         blk->bbIDom = nullptr;
 294     }
 295
 296     // Add entry point to processed as its IDom is NULL.
 297     BitVecTraits traits(m_pCompiler->fgBBNumMax + 1, m_pCompiler);
 298     BitVec       BITVEC_INIT_NOCOPY(processed, BitVecOps::MakeEmpty(&traits));
 299
 300     BitVecOps::AddElemD(&traits, processed, m_pCompiler->fgFirstBB->bbNum);
 301     assert(postOrder[count - 1] == m_pCompiler->fgFirstBB);
 302
 303     bool changed = true;
 304     while (changed)
 305     {
 306         changed = false;
 307
 308         // In reverse post order, except for the entry block (count - 1 is entry BB).
 309         for (int i = count - 2; i >= 0; --i)
 310         {
 311             BasicBlock* block = postOrder[i];
 312
 313             DBG_SSA_JITDUMP("Visiting in reverse post order: BB%02u.\n", block->bbNum);
 314
 315             // Find the first processed predecessor block.
 316             BasicBlock* predBlock = nullptr;
 317             for (flowList* pred = m_pCompiler->BlockPredsWithEH(block); pred; pred = pred->flNext)
 318             {
 319                 if (BitVecOps::IsMember(&traits, processed, pred->flBlock->bbNum))
 320                 {
 321                     predBlock = pred->flBlock;
 322                     break;
 323                 }
 324             }
 325
 326             // There could just be a single basic block, so just check if there were any preds.
 327             if (predBlock != nullptr)
 328             {
 329                 DBG_SSA_JITDUMP("Pred block is BB%02u.\n", predBlock->bbNum);
 330             }
 331
 332             // Intersect DOM, if computed, for all predecessors.
 333             BasicBlock* bbIDom = predBlock;
 334             for (flowList* pred = m_pCompiler->BlockPredsWithEH(block); pred; pred = pred->flNext)
 335             {
 336                 if (predBlock != pred->flBlock)
 337                 {
 338                     BasicBlock* domAncestor = IntersectDom(pred->flBlock, bbIDom);
 339                     // The result may be NULL if "block" and "pred->flBlock" are part of a
 340                     // cycle -- neither is guaranteed ordered wrt the other in reverse postorder,
 341                     // so we may be computing the IDom of "block" before the IDom of "pred->flBlock" has
 342                     // been computed.  But that's OK -- if they're in a cycle, they share the same immediate
 343                     // dominator, so the contribution of "pred->flBlock" is not necessary to compute
 344                     // the result.
 345                     if (domAncestor != nullptr)
 346                     {
 347                         bbIDom = domAncestor;
 348                     }
 349                 }
 350             }
 351
 352             // Did we change the bbIDom value?  If so, we go around the outer loop again.
 353             if (block->bbIDom != bbIDom)
 354             {
 355                 changed = true;
 356
 357                 // IDom has changed, update it.
 358                 DBG_SSA_JITDUMP("bbIDom of BB%02u becomes BB%02u.\n", block->bbNum, bbIDom ? bbIDom->bbNum : 0);
 359                 block->bbIDom = bbIDom;
 360             }
 361
 362             // Mark the current block as processed.
 363             BitVecOps::AddElemD(&traits, processed, block->bbNum);
 364
 365             DBG_SSA_JITDUMP("Marking block BB%02u as processed.\n", block->bbNum);
 366         }
 367     }
 368 }
 369
 370 #ifdef SSA_FEATURE_DOMARR
 371 /**
 372  * Walk the DOM tree and compute pre and post-order arrangement of the tree.
 373  *
 374  * @param curBlock The current block being operated on at some recursive level.
 375  * @param domTree The DOM tree as a map (block -> set of child blocks.)
 376  * @param preIndex The initial index given to the first block visited in pre order.
 377  * @param postIndex The initial index given to the first block visited in post order.
 378  *
 379  * @remarks This would help us answer queries such as "a dom b?" in constant time.
 380  *          For example, if a dominated b, then Pre[a] < Pre[b] but Post[a] > Post[b]
 381  */
 382 void SsaBuilder::DomTreeWalk(BasicBlock* curBlock, BlkToBlkSetMap* domTree, int* preIndex, int* postIndex)
 383 {
 384     JITDUMP("[SsaBuilder::DomTreeWalk] block [%p], BB%02u:\n", dspPtr(curBlock), curBlock->bbNum);
 385
 386     // Store the order number at the block number in the pre order list.
 387     m_pDomPreOrder[curBlock->bbNum] = *preIndex;
 388     ++(*preIndex);
 389
 390     BlkSet* pBlkSet;
 391     if (domTree->Lookup(curBlock, &pBlkSet))
 392     {
 393         for (BlkSet::KeyIterator ki = pBlkSet->Begin(); !ki.Equal(pBlkSet->End()); ++ki)
 394         {
 395             if (curBlock != ki.Get())
 396             {
 397                 DomTreeWalk(ki.Get(), domTree, preIndex, postIndex);
 398             }
 399         }
 400     }
 401
 402     // Store the order number at the block number in the post order list.
 403     m_pDomPostOrder[curBlock->bbNum] = *postIndex;
 404     ++(*postIndex);
 405 }
 406 #endif
 407
 408 /**
 409  * Using IDom of each basic block, add a mapping from block->IDom -> block.
 410  * @param pCompiler Compiler instance
 411  * @param block The basic block that will become the child node of it's iDom.
 412  * @param domTree The output domTree which will hold the mapping "block->bbIDom" -> "block"
 413  *
 414  */
 415 /* static */
 416 void SsaBuilder::ConstructDomTreeForBlock(Compiler* pCompiler, BasicBlock* block, BlkToBlkSetMap* domTree)
 417 {
 418     BasicBlock* bbIDom = block->bbIDom;
 419
 420     // bbIDom for (only) fgFirstBB will be NULL.
 421     if (bbIDom == nullptr)
 422     {
 423         return;
 424     }
 425
 426     // If the bbIDom map key doesn't exist, create one.
 427     BlkSet* pBlkSet;
 428     if (!domTree->Lookup(bbIDom, &pBlkSet))
 429     {
 430         pBlkSet = new (pCompiler->getAllocator()) BlkSet(pCompiler->getAllocator());
 431         domTree->Set(bbIDom, pBlkSet);
 432     }
 433
 434     DBG_SSA_JITDUMP("Inserting BB%02u as dom child of BB%02u.\n", block->bbNum, bbIDom->bbNum);
 435     // Insert the block into the block's set.
 436     pBlkSet->Set(block, true);
 437 }
 438
 439 /**
 440  * Using IDom of each basic block, compute the whole tree. If a block "b" has IDom "i",
 441  * then, block "b" is dominated by "i". The mapping then is i -> { ..., b, ... }, in
 442  * other words, "domTree" is a tree represented by nodes mapped to their children.
 443  *
 444  * @param pCompiler Compiler instance
 445  * @param domTree The output domTree which will hold the mapping "block->bbIDom" -> "block"
 446  *
 447  */
 448 /* static */
 449 void SsaBuilder::ComputeDominators(Compiler* pCompiler, BlkToBlkSetMap* domTree)
 450 {
 451     JITDUMP("*************** In SsaBuilder::ComputeDominators(Compiler*, ...)\n");
 452
 453     // Construct the DOM tree from bbIDom
 454     for (BasicBlock* block = pCompiler->fgFirstBB; block != nullptr; block = block->bbNext)
 455     {
 456         ConstructDomTreeForBlock(pCompiler, block, domTree);
 457     }
 458
 459     DBEXEC(pCompiler->verboseSsa, DisplayDominators(domTree));
 460 }
 461
 462 /**
 463  * Compute the DOM tree into a map(block -> set of blocks) adjacency representation.
 464  *
 465  * Using IDom of each basic block, compute the whole tree. If a block "b" has IDom "i",
 466  * then, block "b" is dominated by "i". The mapping then is i -> { ..., b, ... }
 467  *
 468  * @param postOrder The array of basic blocks arranged in postOrder.
 469  * @param count The size of valid elements in the postOrder array.
 470  * @param domTree A map of (block -> set of blocks) tree representation that is empty.
 471  *
 472  */
 473 void SsaBuilder::ComputeDominators(BasicBlock** postOrder, int count, BlkToBlkSetMap* domTree)
 474 {
 475     JITDUMP("*************** In SsaBuilder::ComputeDominators(BasicBlock** postOrder, int count, ...)\n");
 476
 477     // Construct the DOM tree from bbIDom
 478     for (int i = 0; i < count; ++i)
 479     {
 480         ConstructDomTreeForBlock(m_pCompiler, postOrder[i], domTree);
 481     }
 482
 483     DBEXEC(m_pCompiler->verboseSsa, DisplayDominators(domTree));
 484
 485 #ifdef SSA_FEATURE_DOMARR
 486     // Allocate space for constant time computation of (a DOM b?) query.
 487     unsigned bbArrSize = m_pCompiler->fgBBNumMax + 1; // We will use 1-based bbNums as indices into these arrays, so
 488                                                       // add 1.
 489     m_pDomPreOrder  = jitstd::utility::allocate<int>(m_allocator, bbArrSize);
 490     m_pDomPostOrder = jitstd::utility::allocate<int>(m_allocator, bbArrSize);
 491
 492     // Initial counters.
 493     int preIndex  = 0;
 494     int postIndex = 0;
 495
 496     // Populate the pre and post order of the tree.
 497     DomTreeWalk(m_pCompiler->fgFirstBB, domTree, &preIndex, &postIndex);
 498 #endif
 499 }
 500
 501 #ifdef DEBUG
 502
 503 /**
 504  * Display the DOM tree.
 505  *
 506  * @param domTree A map of (block -> set of blocks) tree representation.
 507  */
 508 /* static */
 509 void SsaBuilder::DisplayDominators(BlkToBlkSetMap* domTree)
 510 {
 511     printf("After computing dominator tree: \n");
 512     for (BlkToBlkSetMap::KeyIterator nodes = domTree->Begin(); !nodes.Equal(domTree->End()); ++nodes)
 513     {
 514         printf("BB%02u := {", nodes.Get()->bbNum);
 515
 516         BlkSet* pBlkSet = nodes.GetValue();
 517         for (BlkSet::KeyIterator ki = pBlkSet->Begin(); !ki.Equal(pBlkSet->End()); ++ki)
 518         {
 519             if (!ki.Equal(pBlkSet->Begin()))
 520             {
 521                 printf(",");
 522             }
 523             printf("BB%02u", ki.Get()->bbNum);
 524         }
 525         printf("}\n");
 526     }
 527 }
 528
 529 #endif // DEBUG
 530
 531 // (Spec comment at declaration.)
 532 // See "A simple, fast dominance algorithm", by Cooper, Harvey, and Kennedy.
 533 // First we compute the dominance frontier for each block, then we convert these to iterated
 534 // dominance frontiers by a closure operation.
 535 BlkToBlkSetMap* SsaBuilder::ComputeIteratedDominanceFrontier(BasicBlock** postOrder, int count)
 536 {
 537     BlkToBlkSetMap* frontier = new (m_pCompiler->getAllocator()) BlkToBlkSetMap(m_pCompiler->getAllocator());
 538
 539     DBG_SSA_JITDUMP("Computing IDF: First computing DF.\n");
 540
 541     for (int i = 0; i < count; ++i)
 542     {
 543         BasicBlock* block = postOrder[i];
 544
 545         DBG_SSA_JITDUMP("Considering block BB%02u.\n", block->bbNum);
 546
 547         // Recall that B3 is in the dom frontier of B1 if there exists a B2
 548         // such that B1 dom B2, !(B1 dom B3), and B3 is an immediate successor
 549         // of B2.  (Note that B1 might be the same block as B2.)
 550         // In that definition, we're considering "block" to be B3, and trying
 551         // to find B1's.  To do so, first we consider the predecessors of "block",
 552         // searching for candidate B2's -- "block" is obviously an immediate successor
 553         // of its immediate predecessors.  If there are zero or one preds, then there
 554         // is no pred, or else the single pred dominates "block", so no B2 exists.
 555
 556         flowList* blockPreds = m_pCompiler->BlockPredsWithEH(block);
 557
 558         // If block has more 0/1 predecessor, skip.
 559         if (blockPreds == nullptr || blockPreds->flNext == nullptr)
 560         {
 561             DBG_SSA_JITDUMP("   Has %d preds; skipping.\n", blockPreds == nullptr ? 0 : 1);
 562             continue;
 563         }
 564
 565         // Otherwise, there are > 1 preds.  Each is a candidate B2 in the definition --
 566         // *unless* it dominates "block"/B3.
 567
 568         for (flowList* pred = blockPreds; pred; pred = pred->flNext)
 569         {
 570             DBG_SSA_JITDUMP("   Considering predecessor BB%02u.\n", pred->flBlock->bbNum);
 571
 572             // If we've found a B2, then consider the possible B1's.  We start with
 573             // B2, since a block dominates itself, then traverse upwards in the dominator
 574             // tree, stopping when we reach the root, or the immediate dominator of "block"/B3.
 575             // (Note that we are guaranteed to encounter this immediate dominator of "block"/B3:
 576             // a predecessor must be dominated by B3's immediate dominator.)
 577             // Along this way, make "block"/B3 part of the dom frontier of the B1.
 578             // When we reach this immediate dominator, the definition no longer applies, since this
 579             // potential B1 *does* dominate "block"/B3, so we stop.
 580             for (BasicBlock* b1 = pred->flBlock; (b1 != nullptr) && (b1 != block->bbIDom); // !root && !loop
 581                  b1             = b1->bbIDom)
 582             {
 583                 DBG_SSA_JITDUMP("      Adding BB%02u to dom frontier of pred dom BB%02u.\n", block->bbNum, b1->bbNum);
 584                 BlkSet* pBlkSet;
 585                 if (!frontier->Lookup(b1, &pBlkSet))
 586                 {
 587                     pBlkSet = new (m_pCompiler->getAllocator()) BlkSet(m_pCompiler->getAllocator());
 588                     frontier->Set(b1, pBlkSet);
 589                 }
 590                 pBlkSet->Set(block, true);
 591             }
 592         }
 593     }
 594
 595 #ifdef DEBUG
 596     if (m_pCompiler->verboseSsa)
 597     {
 598         printf("\nComputed DF:\n");
 599         for (int i = 0; i < count; ++i)
 600         {
 601             BasicBlock* block = postOrder[i];
 602             printf("Block BB%02u := {", block->bbNum);
 603
 604             bool    first = true;
 605             BlkSet* blkDf;
 606             if (frontier->Lookup(block, &blkDf))
 607             {
 608                 for (BlkSet::KeyIterator blkDfIter = blkDf->Begin(); !blkDfIter.Equal(blkDf->End()); blkDfIter++)
 609                 {
 610                     if (!first)
 611                     {
 612                         printf(",");
 613                     }
 614                     printf("BB%02u", blkDfIter.Get()->bbNum);
 615                     first = false;
 616                 }
 617             }
 618             printf("}\n");
 619         }
 620     }
 621 #endif
 622
 623     // Now do the closure operation to make the dominance frontier into an IDF.
 624     // There's probably a better way to do this...
 625     BlkToBlkSetMap* idf = new (m_pCompiler->getAllocator()) BlkToBlkSetMap(m_pCompiler->getAllocator());
 626     for (BlkToBlkSetMap::KeyIterator kiFrontBlks = frontier->Begin(); !kiFrontBlks.Equal(frontier->End());
 627          kiFrontBlks++)
 628     {
 629         // Create IDF(b)
 630         BlkSet* blkIdf = new (m_pCompiler->getAllocator()) BlkSet(m_pCompiler->getAllocator());
 631         idf->Set(kiFrontBlks.Get(), blkIdf);
 632
 633         // Keep track of what got newly added to the IDF, so we can go after their DFs.
 634         BlkSet* delta = new (m_pCompiler->getAllocator()) BlkSet(m_pCompiler->getAllocator());
 635         delta->Set(kiFrontBlks.Get(), true);
 636
 637         // Now transitively add DF+(delta) to IDF(b), each step gathering new "delta."
 638         while (delta->GetCount() > 0)
 639         {
 640             // Extract a block x to be worked on.
 641             BlkSet::KeyIterator ki     = delta->Begin();
 642             BasicBlock*         curBlk = ki.Get();
 643             // TODO-Cleanup: Remove(ki) doesn't work correctly in SimplerHash.
 644             delta->Remove(curBlk);
 645
 646             // Get DF(x).
 647             BlkSet* blkDf;
 648             if (frontier->Lookup(curBlk, &blkDf))
 649             {
 650                 // Add DF(x) to IDF(b) and update "delta" i.e., new additions to IDF(b).
 651                 for (BlkSet::KeyIterator ki = blkDf->Begin(); !ki.Equal(blkDf->End()); ki++)
 652                 {
 653                     if (!blkIdf->Lookup(ki.Get()))
 654                     {
 655                         delta->Set(ki.Get(), true);
 656                         blkIdf->Set(ki.Get(), true);
 657                     }
 658                 }
 659             }
 660         }
 661     }
 662
 663 #ifdef DEBUG
 664     if (m_pCompiler->verboseSsa)
 665     {
 666         printf("\nComputed IDF:\n");
 667         for (int i = 0; i < count; ++i)
 668         {
 669             BasicBlock* block = postOrder[i];
 670             printf("Block BB%02u := {", block->bbNum);
 671
 672             bool    first = true;
 673             BlkSet* blkIdf;
 674             if (idf->Lookup(block, &blkIdf))
 675             {
 676                 for (BlkSet::KeyIterator ki = blkIdf->Begin(); !ki.Equal(blkIdf->End()); ki++)
 677                 {
 678                     if (!first)
 679                     {
 680                         printf(",");
 681                     }
 682                     printf("BB%02u", ki.Get()->bbNum);
 683                     first = false;
 684                 }
 685             }
 686             printf("}\n");
 687         }
 688     }
 689 #endif
 690
 691     return idf;
 692 }
 693
 694 /**
 695  * Returns the phi GT_PHI node if the variable already has a phi node.
 696  *
 697  * @param block The block for which the existence of a phi node needs to be checked.
 698  * @param lclNum The lclNum for which the occurrence of a phi node needs to be checked.
 699  *
 700  * @return If there is a phi node for the lclNum, returns the GT_PHI tree, else NULL.
 701  */
 702 static GenTree* GetPhiNode(BasicBlock* block, unsigned lclNum)
 703 {
 704     // Walk the statements for phi nodes.
 705     for (GenTreePtr stmt = block->bbTreeList; stmt; stmt = stmt->gtNext)
 706     {
 707         // A prefix of the statements of the block are phi definition nodes. If we complete processing
 708         // that prefix, exit.
 709         if (!stmt->IsPhiDefnStmt())
 710         {
 711             break;
 712         }
 713
 714         GenTreePtr tree = stmt->gtStmt.gtStmtExpr;
 715
 716         GenTreePtr phiLhs = tree->gtOp.gtOp1;
 717         assert(phiLhs->OperGet() == GT_LCL_VAR);
 718         if (phiLhs->gtLclVarCommon.gtLclNum == lclNum)
 719         {
 720             return tree->gtOp.gtOp2;
 721         }
 722     }
 723     return nullptr;
 724 }
 725
 726 /**
 727  * Inserts phi functions at DF(b) for variables v that are live after the phi
 728  * insertion point i.e., v in live-in(b).
 729  *
 730  * To do so, the function computes liveness, dominance frontier and inserts a phi node,
 731  * if we have var v in def(b) and live-in(l) and l is in DF(b).
 732  *
 733  * @param postOrder The array of basic blocks arranged in postOrder.
 734  * @param count The size of valid elements in the postOrder array.
 735  */
 736 void SsaBuilder::InsertPhiFunctions(BasicBlock** postOrder, int count)
 737 {
 738     JITDUMP("*************** In SsaBuilder::InsertPhiFunctions()\n");
 739
 740     // Compute liveness on the graph.
 741     m_pCompiler->fgLocalVarLiveness();
 742     EndPhase(PHASE_BUILD_SSA_LIVENESS);
 743
 744     // Compute dominance frontier.
 745     BlkToBlkSetMap* frontier = ComputeIteratedDominanceFrontier(postOrder, count);
 746     EndPhase(PHASE_BUILD_SSA_IDF);
 747
 748     JITDUMP("Inserting phi functions:\n");
 749
 750     for (int i = 0; i < count; ++i)
 751     {
 752         BasicBlock* block = postOrder[i];
 753         DBG_SSA_JITDUMP("Considering dominance frontier of block BB%02u:\n", block->bbNum);
 754
 755         // If the block's dominance frontier is empty, go on to the next block.
 756         BlkSet* blkIdf;
 757         if (!frontier->Lookup(block, &blkIdf))
 758         {
 759             continue;
 760         }
 761
 762         // For each local var number "lclNum" that "block" assigns to...
 763         VARSET_ITER_INIT(m_pCompiler, defVars, block->bbVarDef, varIndex);
 764         while (defVars.NextElem(m_pCompiler, &varIndex))
 765         {
 766             unsigned lclNum = m_pCompiler->lvaTrackedToVarNum[varIndex];
 767             DBG_SSA_JITDUMP("  Considering local var V%02u:\n", lclNum);
 768
 769             if (m_pCompiler->fgExcludeFromSsa(lclNum))
 770             {
 771                 DBG_SSA_JITDUMP("  Skipping because it is excluded.\n");
 772                 continue;
 773             }
 774
 775             // For each block "bbInDomFront" that is in the dominance frontier of "block"...
 776             for (BlkSet::KeyIterator iterBlk = blkIdf->Begin(); !iterBlk.Equal(blkIdf->End()); ++iterBlk)
 777             {
 778                 BasicBlock* bbInDomFront = iterBlk.Get();
 779                 DBG_SSA_JITDUMP("     Considering BB%02u in dom frontier of BB%02u:\n", bbInDomFront->bbNum,
 780                                 block->bbNum);
 781
 782                 // Check if variable "lclNum" is live in block "*iterBlk".
 783                 if (!VarSetOps::IsMember(m_pCompiler, bbInDomFront->bbLiveIn, varIndex))
 784                 {
 785                     continue;
 786                 }
 787
 788                 // Check if we've already inserted a phi node.
 789                 if (GetPhiNode(bbInDomFront, lclNum) == nullptr)
 790                 {
 791                     // We have a variable i that is defined in block j and live at l, and l belongs to dom frontier of
 792                     // j. So insert a phi node at l.
 793                     JITDUMP("Inserting phi definition for V%02u at start of BB%02u.\n", lclNum, bbInDomFront->bbNum);
 794
 795                     GenTreePtr phiLhs = m_pCompiler->gtNewLclvNode(lclNum, m_pCompiler->lvaTable[lclNum].TypeGet());
 796
 797                     // Create 'phiRhs' as a GT_PHI node for 'lclNum', it will eventually hold a GT_LIST of GT_PHI_ARG
 798                     // nodes. However we have to construct this list so for now the gtOp1 of 'phiRhs' is a nullptr.
 799                     // It will get replaced with a GT_LIST of GT_PHI_ARG nodes in
 800                     // SsaBuilder::AssignPhiNodeRhsVariables() and in SsaBuilder::AddDefToHandlerPhis()
 801
 802                     GenTreePtr phiRhs =
 803                         m_pCompiler->gtNewOperNode(GT_PHI, m_pCompiler->lvaTable[lclNum].TypeGet(), nullptr);
 804
 805                     GenTreePtr phiAsg = m_pCompiler->gtNewAssignNode(phiLhs, phiRhs);
 806
 807                     GenTreePtr stmt = m_pCompiler->fgInsertStmtAtBeg(bbInDomFront, phiAsg);
 808                     m_pCompiler->gtSetStmtInfo(stmt);
 809                     m_pCompiler->fgSetStmtSeq(stmt);
 810                 }
 811             }
 812         }
 813
 814         // Now make a similar phi definition if the block defines memory.
 815         if (block->bbMemoryDef != 0)
 816         {
 817             // For each block "bbInDomFront" that is in the dominance frontier of "block".
 818             for (BlkSet::KeyIterator iterBlk = blkIdf->Begin(); !iterBlk.Equal(blkIdf->End()); ++iterBlk)
 819             {
 820                 BasicBlock* bbInDomFront = iterBlk.Get();
 821                 DBG_SSA_JITDUMP("     Considering BB%02u in dom frontier of BB%02u for Memory phis:\n",
 822                                 bbInDomFront->bbNum, block->bbNum);
 823
 824                 for (MemoryKind memoryKind : allMemoryKinds())
 825                 {
 826                     if ((memoryKind == GcHeap) && m_pCompiler->byrefStatesMatchGcHeapStates)
 827                     {
 828                         // Share the PhiFunc with ByrefExposed.
 829                         assert(memoryKind > ByrefExposed);
 830                         bbInDomFront->bbMemorySsaPhiFunc[memoryKind] = bbInDomFront->bbMemorySsaPhiFunc[ByrefExposed];
 831                         continue;
 832                     }
 833
 834                     // Check if this memoryKind is defined in this block.
 835                     if ((block->bbMemoryDef & memoryKindSet(memoryKind)) == 0)
 836                     {
 837                         continue;
 838                     }
 839
 840                     // Check if memoryKind is live into block "*iterBlk".
 841                     if ((bbInDomFront->bbMemoryLiveIn & memoryKindSet(memoryKind)) == 0)
 842                     {
 843                         continue;
 844                     }
 845
 846                     // Check if we've already inserted a phi node.
 847                     if (bbInDomFront->bbMemorySsaPhiFunc[memoryKind] == nullptr)
 848                     {
 849                         // We have a variable i that is defined in block j and live at l, and l belongs to dom frontier
 850                         // of
 851                         // j. So insert a phi node at l.
 852                         JITDUMP("Inserting phi definition for %s at start of BB%02u.\n", memoryKindNames[memoryKind],
 853                                 bbInDomFront->bbNum);
 854                         bbInDomFront->bbMemorySsaPhiFunc[memoryKind] = BasicBlock::EmptyMemoryPhiDef;
 855                     }
 856                 }
 857             }
 858         }
 859     }
 860     EndPhase(PHASE_BUILD_SSA_INSERT_PHIS);
 861 }
 862
 863 #ifdef SSA_FEATURE_USEDEF
 864 /**
 865  * Record a use point of a variable.
 866  *
 867  * The use point is just the tree that is a local variable use.
 868  *
 869  * @param tree Tree node where an SSA variable is used.
 870  *
 871  * @remarks The result is in the m_uses map :: [lclNum, ssaNum] -> tree.
 872  */
 873 void SsaBuilder::AddUsePoint(GenTree* tree)
 874 {
 875     assert(tree->IsLocal());
 876     SsaVarName          key(tree->gtLclVarCommon.gtLclNum, tree->gtLclVarCommon.gtSsaNum);
 877     VarToUses::iterator iter = m_uses.find(key);
 878     if (iter == m_uses.end())
 879     {
 880         iter = m_uses.insert(key, VarToUses::mapped_type(m_uses.get_allocator()));
 881     }
 882     (*iter).second.push_back(tree);
 883 }
 884 #endif // !SSA_FEATURE_USEDEF
 885
 886 /**
 887  * Record a def point of a variable.
 888  *
 889  * The def point is just the tree that is a local variable def.
 890  *
 891  * @param tree Tree node where an SSA variable is def'ed.
 892  *
 893  * @remarks The result is in the m_defs map :: [lclNum, ssaNum] -> tree.
 894  */
 895 void SsaBuilder::AddDefPoint(GenTree* tree, BasicBlock* blk)
 896 {
 897     Compiler::IndirectAssignmentAnnotation* pIndirAnnot;
 898     // In the case of an "indirect assignment", where the LHS is IND of a byref to the local actually being assigned,
 899     // we make the ASG tree the def point.
 900     assert(tree->IsLocal() || IsIndirectAssign(tree, &pIndirAnnot));
 901     unsigned lclNum;
 902     unsigned defSsaNum;
 903     if (tree->IsLocal())
 904     {
 905         lclNum    = tree->gtLclVarCommon.gtLclNum;
 906         defSsaNum = m_pCompiler->GetSsaNumForLocalVarDef(tree);
 907     }
 908     else
 909     {
 910         bool b = m_pCompiler->GetIndirAssignMap()->Lookup(tree, &pIndirAnnot);
 911         assert(b);
 912         lclNum    = pIndirAnnot->m_lclNum;
 913         defSsaNum = pIndirAnnot->m_defSsaNum;
 914     }
 915 #ifdef DEBUG
 916     // Record that there's a new SSA def.
 917     m_pCompiler->lvaTable[lclNum].lvNumSsaNames++;
 918 #endif
 919     // Record where the defn happens.
 920     LclSsaVarDsc* ssaDef    = m_pCompiler->lvaTable[lclNum].GetPerSsaData(defSsaNum);
 921     ssaDef->m_defLoc.m_blk  = blk;
 922     ssaDef->m_defLoc.m_tree = tree;
 923
 924 #ifdef SSA_FEATURE_USEDEF
 925     SsaVarName         key(lclNum, defSsaNum);
 926     VarToDef::iterator iter = m_defs.find(key);
 927     if (iter == m_defs.end())
 928     {
 929         iter = m_defs.insert(key, tree);
 930         return;
 931     }
 932     // There can only be a single definition for an SSA var.
 933     unreached();
 934 #endif
 935 }
 936
 937 bool SsaBuilder::IsIndirectAssign(GenTreePtr tree, Compiler::IndirectAssignmentAnnotation** ppIndirAssign)
 938 {
 939     return tree->OperGet() == GT_ASG && m_pCompiler->m_indirAssignMap != nullptr &&
 940            m_pCompiler->GetIndirAssignMap()->Lookup(tree, ppIndirAssign);
 941 }
 942
 943 /**
 944  * Rename the local variable tree node.
 945  *
 946  * If the given tree node is a local variable, then for a def give a new count, if use,
 947  * then give the count in the top of stack, i.e., current count (used for last def.)
 948  *
 949  * @param tree Tree node where an SSA variable is used or def'ed.
 950  * @param pRenameState The incremental rename information stored during renaming process.
 951  *
 952  * @remarks This method has to maintain parity with TreePopStacks corresponding to pushes
 953  *          it makes for defs.
 954  */
 955 void SsaBuilder::TreeRenameVariables(GenTree* tree, BasicBlock* block, SsaRenameState* pRenameState, bool isPhiDefn)
 956 {
 957     // This is perhaps temporary -- maybe should be done elsewhere.  Label GT_INDs on LHS of assignments, so we
 958     // can skip these during (at least) value numbering.
 959     if (tree->OperIsAssignment())
 960     {
 961         GenTreePtr lhs     = tree->gtOp.gtOp1->gtEffectiveVal(/*commaOnly*/ true);
 962         GenTreePtr trueLhs = lhs->gtEffectiveVal(/*commaOnly*/ true);
 963         if (trueLhs->OperIsIndir())
 964         {
 965             trueLhs->gtFlags |= GTF_IND_ASG_LHS;
 966         }
 967         else if (trueLhs->OperGet() == GT_CLS_VAR)
 968         {
 969             trueLhs->gtFlags |= GTF_CLS_VAR_ASG_LHS;
 970         }
 971     }
 972
 973     // Figure out if "tree" may make a new GC heap state (if we care for this block).
 974     if ((block->bbMemoryHavoc & memoryKindSet(GcHeap)) == 0)
 975     {
 976         if (tree->OperIsAssignment() || tree->OperIsBlkOp())
 977         {
 978             if (m_pCompiler->ehBlockHasExnFlowDsc(block))
 979             {
 980                 GenTreeLclVarCommon* lclVarNode;
 981
 982                 bool isLocal            = tree->DefinesLocal(m_pCompiler, &lclVarNode);
 983                 bool isAddrExposedLocal = isLocal && m_pCompiler->lvaVarAddrExposed(lclVarNode->gtLclNum);
 984                 bool hasByrefHavoc      = ((block->bbMemoryHavoc & memoryKindSet(ByrefExposed)) != 0);
 985                 if (!isLocal || (isAddrExposedLocal && !hasByrefHavoc))
 986                 {
 987                     // It *may* define byref memory in a non-havoc way.  Make a new SSA # -- associate with this node.
 988                     unsigned count = pRenameState->CountForMemoryDef();
 989                     if (!hasByrefHavoc)
 990                     {
 991                         pRenameState->PushMemory(ByrefExposed, block, count);
 992                         m_pCompiler->GetMemorySsaMap(ByrefExposed)->Set(tree, count);
 993 #ifdef DEBUG
 994                         if (JitTls::GetCompiler()->verboseSsa)
 995                         {
 996                             printf("Node ");
 997                             Compiler::printTreeID(tree);
 998                             printf(" (in try block) may define memory; ssa # = %d.\n", count);
 999                         }
1000 #endif // DEBUG
1001
1002                         // Now add this SSA # to all phis of the reachable catch blocks.
1003                         AddMemoryDefToHandlerPhis(ByrefExposed, block, count);
1004                     }
1005
1006                     if (!isLocal)
1007                     {
1008                         // Add a new def for GcHeap as well
1009                         if (m_pCompiler->byrefStatesMatchGcHeapStates)
1010                         {
1011                             // GcHeap and ByrefExposed share the same stacks, SsaMap, and phis
1012                             assert(!hasByrefHavoc);
1013                             assert(pRenameState->CountForMemoryUse(GcHeap) == count);
1014                             assert(*m_pCompiler->GetMemorySsaMap(GcHeap)->LookupPointer(tree) == count);
1015                             assert(block->bbMemorySsaPhiFunc[GcHeap] == block->bbMemorySsaPhiFunc[ByrefExposed]);
1016                         }
1017                         else
1018                         {
1019                             if (!hasByrefHavoc)
1020                             {
1021                                 // Allocate a distinct defnum for the GC Heap
1022                                 count = pRenameState->CountForMemoryDef();
1023                             }
1024
1025                             pRenameState->PushMemory(GcHeap, block, count);
1026                             m_pCompiler->GetMemorySsaMap(GcHeap)->Set(tree, count);
1027                             AddMemoryDefToHandlerPhis(GcHeap, block, count);
1028                         }
1029                     }
1030                 }
1031             }
1032         }
1033     }
1034
1035     Compiler::IndirectAssignmentAnnotation* pIndirAssign = nullptr;
1036     if (!tree->IsLocal() && !IsIndirectAssign(tree, &pIndirAssign))
1037     {
1038         return;
1039     }
1040
1041     if (pIndirAssign != nullptr)
1042     {
1043         unsigned lclNum = pIndirAssign->m_lclNum;
1044         // Is this a variable we exclude from SSA?
1045         if (m_pCompiler->fgExcludeFromSsa(lclNum))
1046         {
1047             pIndirAssign->m_defSsaNum = SsaConfig::RESERVED_SSA_NUM;
1048             return;
1049         }
1050         // Otherwise...
1051         if (!pIndirAssign->m_isEntire)
1052         {
1053             pIndirAssign->m_useSsaNum = pRenameState->CountForUse(lclNum);
1054         }
1055         unsigned count            = pRenameState->CountForDef(lclNum);
1056         pIndirAssign->m_defSsaNum = count;
1057         pRenameState->Push(block, lclNum, count);
1058         AddDefPoint(tree, block);
1059     }
1060     else
1061     {
1062         unsigned lclNum = tree->gtLclVarCommon.gtLclNum;
1063         // Is this a variable we exclude from SSA?
1064         if (m_pCompiler->fgExcludeFromSsa(lclNum))
1065         {
1066             tree->gtLclVarCommon.SetSsaNum(SsaConfig::RESERVED_SSA_NUM);
1067             return;
1068         }
1069
1070         if (tree->gtFlags & GTF_VAR_DEF)
1071         {
1072             if (tree->gtFlags & GTF_VAR_USEASG)
1073             {
1074                 // This the "x" in something like "x op= y"; it is both a use (first), then a def.
1075                 // The def will define a new SSA name, and record that in "x".  If we need the SSA
1076                 // name of the use, we record it in a map reserved for that purpose.
1077                 unsigned count = pRenameState->CountForUse(lclNum);
1078                 tree->gtLclVarCommon.SetSsaNum(count);
1079 #ifdef SSA_FEATURE_USEDEF
1080                 AddUsePoint(tree);
1081 #endif
1082             }
1083
1084             // Give a count and increment.
1085             unsigned count = pRenameState->CountForDef(lclNum);
1086             if (tree->gtFlags & GTF_VAR_USEASG)
1087             {
1088                 m_pCompiler->GetOpAsgnVarDefSsaNums()->Set(tree, count);
1089             }
1090             else
1091             {
1092                 tree->gtLclVarCommon.SetSsaNum(count);
1093             }
1094             pRenameState->Push(block, lclNum, count);
1095             AddDefPoint(tree, block);
1096
1097             // If necessary, add "lclNum/count" to the arg list of a phi def in any
1098             // handlers for try blocks that "block" is within.  (But only do this for "real" definitions,
1099             // not phi definitions.)
1100             if (!isPhiDefn)
1101             {
1102                 AddDefToHandlerPhis(block, lclNum, count);
1103             }
1104         }
1105         else if (!isPhiDefn) // Phi args already have ssa numbers.
1106         {
1107             // This case is obviated by the short-term "early-out" above...but it's in the right direction.
1108             // Is it a promoted struct local?
1109             if (m_pCompiler->lvaTable[lclNum].lvPromoted)
1110             {
1111                 assert(tree->TypeGet() == TYP_STRUCT);
1112                 LclVarDsc* varDsc = &m_pCompiler->lvaTable[lclNum];
1113                 // If has only a single field var, treat this as a use of that field var.
1114                 // Otherwise, we don't give SSA names to uses of promoted struct vars.
1115                 if (varDsc->lvFieldCnt == 1)
1116                 {
1117                     lclNum = varDsc->lvFieldLclStart;
1118                 }
1119                 else
1120                 {
1121                     tree->gtLclVarCommon.SetSsaNum(SsaConfig::RESERVED_SSA_NUM);
1122                     return;
1123                 }
1124             }
1125             // Give the count as top of stack.
1126             unsigned count = pRenameState->CountForUse(lclNum);
1127             tree->gtLclVarCommon.SetSsaNum(count);
1128 #ifdef SSA_FEATURE_USEDEF
1129             AddUsePoint(tree);
1130 #endif
1131         }
1132     }
1133 }
1134
1135 void SsaBuilder::AddDefToHandlerPhis(BasicBlock* block, unsigned lclNum, unsigned count)
1136 {
1137     assert(m_pCompiler->lvaTable[lclNum].lvTracked); // Precondition.
1138     unsigned lclIndex = m_pCompiler->lvaTable[lclNum].lvVarIndex;
1139
1140     EHblkDsc* tryBlk = m_pCompiler->ehGetBlockExnFlowDsc(block);
1141     if (tryBlk != nullptr)
1142     {
1143         DBG_SSA_JITDUMP(
1144             "Definition of local V%02u/d:%d in block BB%02u has exn handler; adding as phi arg to handlers.\n", lclNum,
1145             count, block->bbNum);
1146         while (true)
1147         {
1148             BasicBlock* handler = tryBlk->ExFlowBlock();
1149
1150             // Is "lclNum" live on entry to the handler?
1151             if (VarSetOps::IsMember(m_pCompiler, handler->bbLiveIn, lclIndex))
1152             {
1153 #ifdef DEBUG
1154                 bool phiFound = false;
1155 #endif
1156                 // A prefix of blocks statements will be SSA definitions.  Search those for "lclNum".
1157                 for (GenTreePtr stmt = handler->bbTreeList; stmt; stmt = stmt->gtNext)
1158                 {
1159                     // If the tree is not an SSA def, break out of the loop: we're done.
1160                     if (!stmt->IsPhiDefnStmt())
1161                     {
1162                         break;
1163                     }
1164
1165                     GenTreePtr tree = stmt->gtStmt.gtStmtExpr;
1166
1167                     assert(tree->IsPhiDefn());
1168
1169                     if (tree->gtOp.gtOp1->gtLclVar.gtLclNum == lclNum)
1170                     {
1171                         // It's the definition for the right local.  Add "count" to the RHS.
1172                         GenTreePtr      phi  = tree->gtOp.gtOp2;
1173                         GenTreeArgList* args = nullptr;
1174                         if (phi->gtOp.gtOp1 != nullptr)
1175                         {
1176                             args = phi->gtOp.gtOp1->AsArgList();
1177                         }
1178 #ifdef DEBUG
1179                         // Make sure it isn't already present: we should only add each definition once.
1180                         for (GenTreeArgList* curArgs = args; curArgs != nullptr; curArgs = curArgs->Rest())
1181                         {
1182                             GenTreePhiArg* phiArg = curArgs->Current()->AsPhiArg();
1183                             assert(phiArg->gtSsaNum != count);
1184                         }
1185 #endif
1186                         var_types      typ = m_pCompiler->lvaTable[lclNum].TypeGet();
1187                         GenTreePhiArg* newPhiArg =
1188                             new (m_pCompiler, GT_PHI_ARG) GenTreePhiArg(typ, lclNum, count, block);
1189
1190                         phi->gtOp.gtOp1 = new (m_pCompiler, GT_LIST) GenTreeArgList(newPhiArg, args);
1191                         m_pCompiler->gtSetStmtInfo(stmt);
1192                         m_pCompiler->fgSetStmtSeq(stmt);
1193 #ifdef DEBUG
1194                         phiFound = true;
1195 #endif
1196                         DBG_SSA_JITDUMP("   Added phi arg u:%d for V%02u to phi defn in handler block BB%02u.\n", count,
1197                                         lclNum, handler->bbNum);
1198                         break;
1199                     }
1200                 }
1201                 assert(phiFound);
1202             }
1203
1204             unsigned nextTryIndex = tryBlk->ebdEnclosingTryIndex;
1205             if (nextTryIndex == EHblkDsc::NO_ENCLOSING_INDEX)
1206             {
1207                 break;
1208             }
1209
1210             tryBlk = m_pCompiler->ehGetDsc(nextTryIndex);
1211         }
1212     }
1213 }
1214
1215 void SsaBuilder::AddMemoryDefToHandlerPhis(MemoryKind memoryKind, BasicBlock* block, unsigned count)
1216 {
1217     if (m_pCompiler->ehBlockHasExnFlowDsc(block))
1218     {
1219         // Don't do anything for a compiler-inserted BBJ_ALWAYS that is a "leave helper".
1220         if (block->bbJumpKind == BBJ_ALWAYS && (block->bbFlags & BBF_INTERNAL) && (block->bbPrev->isBBCallAlwaysPair()))
1221         {
1222             return;
1223         }
1224
1225         // Otherwise...
1226         DBG_SSA_JITDUMP("Definition of %s/d:%d in block BB%02u has exn handler; adding as phi arg to handlers.\n",
1227                         memoryKindNames[memoryKind], count, block->bbNum);
1228         EHblkDsc* tryBlk = m_pCompiler->ehGetBlockExnFlowDsc(block);
1229         while (true)
1230         {
1231             BasicBlock* handler = tryBlk->ExFlowBlock();
1232
1233             // Is memoryKind live on entry to the handler?
1234             if ((handler->bbMemoryLiveIn & memoryKindSet(memoryKind)) != 0)
1235             {
1236                 assert(handler->bbMemorySsaPhiFunc != nullptr);
1237
1238                 // Add "count" to the phi args of memoryKind.
1239                 BasicBlock::MemoryPhiArg*& handlerMemoryPhi = handler->bbMemorySsaPhiFunc[memoryKind];
1240
1241 #if DEBUG
1242                 if (m_pCompiler->byrefStatesMatchGcHeapStates)
1243                 {
1244                     // When sharing phis for GcHeap and ByrefExposed, callers should ask to add phis
1245                     // for ByrefExposed only.
1246                     assert(memoryKind != GcHeap);
1247                     if (memoryKind == ByrefExposed)
1248                     {
1249                         // The GcHeap and ByrefExposed phi funcs should always be in sync.
1250                         assert(handlerMemoryPhi == handler->bbMemorySsaPhiFunc[GcHeap]);
1251                     }
1252                 }
1253 #endif
1254
1255                 if (handlerMemoryPhi == BasicBlock::EmptyMemoryPhiDef)
1256                 {
1257                     handlerMemoryPhi = new (m_pCompiler) BasicBlock::MemoryPhiArg(count);
1258                 }
1259                 else
1260                 {
1261 #ifdef DEBUG
1262                     BasicBlock::MemoryPhiArg* curArg = handler->bbMemorySsaPhiFunc[memoryKind];
1263                     while (curArg != nullptr)
1264                     {
1265                         assert(curArg->GetSsaNum() != count);
1266                         curArg = curArg->m_nextArg;
1267                     }
1268 #endif // DEBUG
1269                     handlerMemoryPhi = new (m_pCompiler) BasicBlock::MemoryPhiArg(count, handlerMemoryPhi);
1270                 }
1271
1272                 DBG_SSA_JITDUMP("   Added phi arg u:%d for %s to phi defn in handler block BB%02u.\n", count,
1273                                 memoryKindNames[memoryKind], memoryKind, handler->bbNum);
1274
1275                 if ((memoryKind == ByrefExposed) && m_pCompiler->byrefStatesMatchGcHeapStates)
1276                 {
1277                     // Share the phi between GcHeap and ByrefExposed.
1278                     handler->bbMemorySsaPhiFunc[GcHeap] = handlerMemoryPhi;
1279                 }
1280             }
1281             unsigned tryInd = tryBlk->ebdEnclosingTryIndex;
1282             if (tryInd == EHblkDsc::NO_ENCLOSING_INDEX)
1283             {
1284                 break;
1285             }
1286             tryBlk = m_pCompiler->ehGetDsc(tryInd);
1287         }
1288     }
1289 }
1290
1291 /**
1292  * Walk the block's tree in the evaluation order and give var definitions and uses their
1293  * SSA names.
1294  *
1295  * @param block Block for which SSA variables have to be renamed.
1296  * @param pRenameState The incremental rename information stored during renaming process.
1297  *
1298  */
1299 void SsaBuilder::BlockRenameVariables(BasicBlock* block, SsaRenameState* pRenameState)
1300 {
1301     // Walk the statements of the block and rename the tree variables.
1302
1303     // First handle the incoming memory states.
1304     for (MemoryKind memoryKind : allMemoryKinds())
1305     {
1306         if ((memoryKind == GcHeap) && m_pCompiler->byrefStatesMatchGcHeapStates)
1307         {
1308             // ByrefExposed and GcHeap share any phi this block may have,
1309             assert(block->bbMemorySsaPhiFunc[memoryKind] == block->bbMemorySsaPhiFunc[ByrefExposed]);
1310             // so we will have already allocated a defnum for it if needed.
1311             assert(memoryKind > ByrefExposed);
1312             assert(pRenameState->CountForMemoryUse(memoryKind) == pRenameState->CountForMemoryUse(ByrefExposed));
1313         }
1314         else
1315         {
1316             // Is there an Phi definition for memoryKind at the start of this block?
1317             if (block->bbMemorySsaPhiFunc[memoryKind] != nullptr)
1318             {
1319                 unsigned count = pRenameState->CountForMemoryDef();
1320                 pRenameState->PushMemory(memoryKind, block, count);
1321
1322                 DBG_SSA_JITDUMP("Ssa # for %s phi on entry to BB%02u is %d.\n", memoryKindNames[memoryKind],
1323                                 block->bbNum, count);
1324             }
1325         }
1326
1327         // Record the "in" Ssa # for memoryKind.
1328         block->bbMemorySsaNumIn[memoryKind] = pRenameState->CountForMemoryUse(memoryKind);
1329     }
1330
1331     // We need to iterate over phi definitions, to give them SSA names, but we need
1332     // to know which are which, so we don't add phi definitions to handler phi arg lists.
1333     // Statements are phi defns until they aren't.
1334     bool       isPhiDefn   = true;
1335     GenTreePtr firstNonPhi = block->FirstNonPhiDef();
1336     for (GenTreePtr stmt = block->bbTreeList; stmt; stmt = stmt->gtNext)
1337     {
1338         if (stmt == firstNonPhi)
1339         {
1340             isPhiDefn = false;
1341         }
1342
1343         for (GenTreePtr tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext)
1344         {
1345             TreeRenameVariables(tree, block, pRenameState, isPhiDefn);
1346         }
1347     }
1348
1349     // Now handle the final memory states.
1350     for (MemoryKind memoryKind : allMemoryKinds())
1351     {
1352         MemoryKindSet memorySet = memoryKindSet(memoryKind);
1353
1354         // If the block defines memory, allocate an SSA variable for the final memory state in the block.
1355         // (This may be redundant with the last SSA var explicitly created, but there's no harm in that.)
1356         if ((memoryKind == GcHeap) && m_pCompiler->byrefStatesMatchGcHeapStates)
1357         {
1358             // We've already allocated the SSA num and propagated it to shared phis, if needed,
1359             // when processing ByrefExposed.
1360             assert(memoryKind > ByrefExposed);
1361             assert(((block->bbMemoryDef & memorySet) != 0) ==
1362                    ((block->bbMemoryDef & memoryKindSet(ByrefExposed)) != 0));
1363             assert(pRenameState->CountForMemoryUse(memoryKind) == pRenameState->CountForMemoryUse(ByrefExposed));
1364         }
1365         else
1366         {
1367             if ((block->bbMemoryDef & memorySet) != 0)
1368             {
1369                 unsigned count = pRenameState->CountForMemoryDef();
1370                 pRenameState->PushMemory(memoryKind, block, count);
1371                 AddMemoryDefToHandlerPhis(memoryKind, block, count);
1372             }
1373         }
1374
1375         // Record the "out" Ssa" # for memoryKind.
1376         block->bbMemorySsaNumOut[memoryKind] = pRenameState->CountForMemoryUse(memoryKind);
1377
1378         DBG_SSA_JITDUMP("Ssa # for %s on entry to BB%02u is %d; on exit is %d.\n", memoryKindNames[memoryKind],
1379                         block->bbNum, block->bbMemorySsaNumIn[memoryKind], block->bbMemorySsaNumOut[memoryKind]);
1380     }
1381 }
1382
1383 /**
1384  * Walk through the phi nodes of a given block and assign rhs variables to them.
1385  *
1386  * Also renumber the rhs variables from top of the stack.
1387  *
1388  * @param block Block for which phi nodes have to be assigned their rhs arguments.
1389  * @param pRenameState The incremental rename information stored during renaming process.
1390  *
1391  */
1392 void SsaBuilder::AssignPhiNodeRhsVariables(BasicBlock* block, SsaRenameState* pRenameState)
1393 {
1394     BasicBlock::AllSuccs allSuccs    = block->GetAllSuccs(m_pCompiler);
1395     AllSuccessorIter     allSuccsEnd = allSuccs.end();
1396     for (AllSuccessorIter allSuccsIter = allSuccs.begin(); allSuccsIter != allSuccsEnd; ++allSuccsIter)
1397     {
1398         BasicBlock* succ = (*allSuccsIter);
1399         // Walk the statements for phi nodes.
1400         for (GenTreePtr stmt = succ->bbTreeList; stmt != nullptr && stmt->IsPhiDefnStmt(); stmt = stmt->gtNext)
1401         {
1402             GenTreePtr tree = stmt->gtStmt.gtStmtExpr;
1403             assert(tree->IsPhiDefn());
1404
1405             // Get the phi node from GT_ASG.
1406             GenTreePtr phiNode = tree->gtOp.gtOp2;
1407             assert(phiNode->gtOp.gtOp1 == nullptr || phiNode->gtOp.gtOp1->OperGet() == GT_LIST);
1408
1409             unsigned lclNum = tree->gtOp.gtOp1->gtLclVar.gtLclNum;
1410             unsigned ssaNum = pRenameState->CountForUse(lclNum);
1411             // Search the arglist for an existing definition for ssaNum.
1412             // (Can we assert that its the head of the list?  This should only happen when we add
1413             // during renaming for a definition that occurs within a try, and then that's the last
1414             // value of the var within that basic block.)
1415             GenTreeArgList* argList = (phiNode->gtOp.gtOp1 == nullptr ? nullptr : phiNode->gtOp.gtOp1->AsArgList());
1416             bool            found   = false;
1417             while (argList != nullptr)
1418             {
1419                 if (argList->Current()->AsLclVarCommon()->GetSsaNum() == ssaNum)
1420                 {
1421                     found = true;
1422                     break;
1423                 }
1424                 argList = argList->Rest();
1425             }
1426             if (!found)
1427             {
1428                 GenTreePtr newPhiArg =
1429                     new (m_pCompiler, GT_PHI_ARG) GenTreePhiArg(tree->gtOp.gtOp1->TypeGet(), lclNum, ssaNum, block);
1430                 argList             = (phiNode->gtOp.gtOp1 == nullptr ? nullptr : phiNode->gtOp.gtOp1->AsArgList());
1431                 phiNode->gtOp.gtOp1 = new (m_pCompiler, GT_LIST) GenTreeArgList(newPhiArg, argList);
1432                 DBG_SSA_JITDUMP("  Added phi arg u:%d for V%02u from BB%02u in BB%02u.\n", ssaNum, lclNum, block->bbNum,
1433                                 succ->bbNum);
1434             }
1435
1436             m_pCompiler->gtSetStmtInfo(stmt);
1437             m_pCompiler->fgSetStmtSeq(stmt);
1438         }
1439
1440         // Now handle memory.
1441         for (MemoryKind memoryKind : allMemoryKinds())
1442         {
1443             BasicBlock::MemoryPhiArg*& succMemoryPhi = succ->bbMemorySsaPhiFunc[memoryKind];
1444             if (succMemoryPhi != nullptr)
1445             {
1446                 if ((memoryKind == GcHeap) && m_pCompiler->byrefStatesMatchGcHeapStates)
1447                 {
1448                     // We've already propagated the "out" number to the phi shared with ByrefExposed,
1449                     // but still need to update bbMemorySsaPhiFunc to be in sync between GcHeap and ByrefExposed.
1450                     assert(memoryKind > ByrefExposed);
1451                     assert(block->bbMemorySsaNumOut[memoryKind] == block->bbMemorySsaNumOut[ByrefExposed]);
1452                     assert((succ->bbMemorySsaPhiFunc[ByrefExposed] == succMemoryPhi) ||
1453                            (succ->bbMemorySsaPhiFunc[ByrefExposed]->m_nextArg ==
1454                             (succMemoryPhi == BasicBlock::EmptyMemoryPhiDef ? nullptr : succMemoryPhi)));
1455                     succMemoryPhi = succ->bbMemorySsaPhiFunc[ByrefExposed];
1456
1457                     continue;
1458                 }
1459
1460                 if (succMemoryPhi == BasicBlock::EmptyMemoryPhiDef)
1461                 {
1462                     succMemoryPhi = new (m_pCompiler) BasicBlock::MemoryPhiArg(block->bbMemorySsaNumOut[memoryKind]);
1463                 }
1464                 else
1465                 {
1466                     BasicBlock::MemoryPhiArg* curArg = succMemoryPhi;
1467                     unsigned                  ssaNum = block->bbMemorySsaNumOut[memoryKind];
1468                     bool                      found  = false;
1469                     // This is a quadratic algorithm.  We might need to consider some switch over to a hash table
1470                     // representation for the arguments of a phi node, to make this linear.
1471                     while (curArg != nullptr)
1472                     {
1473                         if (curArg->m_ssaNum == ssaNum)
1474                         {
1475                             found = true;
1476                             break;
1477                         }
1478                         curArg = curArg->m_nextArg;
1479                     }
1480                     if (!found)
1481                     {
1482                         succMemoryPhi = new (m_pCompiler) BasicBlock::MemoryPhiArg(ssaNum, succMemoryPhi);
1483                     }
1484                 }
1485                 DBG_SSA_JITDUMP("  Added phi arg for %s u:%d from BB%02u in BB%02u.\n", memoryKindNames[memoryKind],
1486                                 block->bbMemorySsaNumOut[memoryKind], block->bbNum, succ->bbNum);
1487             }
1488         }
1489
1490         // If "succ" is the first block of a try block (and "block" is not also in that try block)
1491         // then we must look at the vars that have phi defs in the corresponding handler;
1492         // the current SSA name for such vars must be included as an argument to that phi.
1493         if (m_pCompiler->bbIsTryBeg(succ))
1494         {
1495             assert(succ->hasTryIndex());
1496             unsigned tryInd = succ->getTryIndex();
1497
1498             while (tryInd != EHblkDsc::NO_ENCLOSING_INDEX)
1499             {
1500                 // Check if the predecessor "block" is within the same try block.
1501                 if (block->hasTryIndex())
1502                 {
1503                     for (unsigned blockTryInd = block->getTryIndex(); blockTryInd != EHblkDsc::NO_ENCLOSING_INDEX;
1504                          blockTryInd          = m_pCompiler->ehGetEnclosingTryIndex(blockTryInd))
1505                     {
1506                         if (blockTryInd == tryInd)
1507                         {
1508                             // It is; don't execute the loop below.
1509                             tryInd = EHblkDsc::NO_ENCLOSING_INDEX;
1510                             break;
1511                         }
1512                     }
1513
1514                     // The loop just above found that the predecessor "block" is within the same
1515                     // try block as "succ."  So we don't need to process this try, or any
1516                     // further outer try blocks here, since they would also contain both "succ"
1517                     // and "block".
1518                     if (tryInd == EHblkDsc::NO_ENCLOSING_INDEX)
1519                     {
1520                         break;
1521                     }
1522                 }
1523
1524                 EHblkDsc* succTry = m_pCompiler->ehGetDsc(tryInd);
1525                 // This is necessarily true on the first iteration, but not
1526                 // necessarily on the second and subsequent.
1527                 if (succTry->ebdTryBeg != succ)
1528                 {
1529                     break;
1530                 }
1531
1532                 // succ is the first block of this try.  Look at phi defs in the handler.
1533                 // For a filter, we consider the filter to be the "real" handler.
1534                 BasicBlock* handlerStart = succTry->ExFlowBlock();
1535
1536                 for (GenTreePtr stmt = handlerStart->bbTreeList; stmt; stmt = stmt->gtNext)
1537                 {
1538                     GenTreePtr tree = stmt->gtStmt.gtStmtExpr;
1539
1540                     // Check if the first n of the statements are phi nodes. If not, exit.
1541                     if (tree->OperGet() != GT_ASG || tree->gtOp.gtOp2 == nullptr ||
1542                         tree->gtOp.gtOp2->OperGet() != GT_PHI)
1543                     {
1544                         break;
1545                     }
1546
1547                     // Get the phi node from GT_ASG.
1548                     GenTreePtr lclVar = tree->gtOp.gtOp1;
1549                     unsigned   lclNum = lclVar->gtLclVar.gtLclNum;
1550
1551                     // If the variable is live-out of "blk", and is therefore live on entry to the try-block-start
1552                     // "succ", then we make sure the current SSA name for the
1553                     // var is one of the args of the phi node.  If not, go on.
1554                     LclVarDsc* lclVarDsc = &m_pCompiler->lvaTable[lclNum];
1555                     if (!lclVarDsc->lvTracked ||
1556                         !VarSetOps::IsMember(m_pCompiler, block->bbLiveOut, lclVarDsc->lvVarIndex))
1557                     {
1558                         continue;
1559                     }
1560
1561                     GenTreePtr phiNode = tree->gtOp.gtOp2;
1562                     assert(phiNode->gtOp.gtOp1 == nullptr || phiNode->gtOp.gtOp1->OperGet() == GT_LIST);
1563                     GenTreeArgList* argList = reinterpret_cast<GenTreeArgList*>(phiNode->gtOp.gtOp1);
1564
1565                     // What is the current SSAName from the predecessor for this local?
1566                     unsigned ssaNum = pRenameState->CountForUse(lclNum);
1567
1568                     // See if this ssaNum is already an arg to the phi.
1569                     bool alreadyArg = false;
1570                     for (GenTreeArgList* curArgs = argList; curArgs != nullptr; curArgs = curArgs->Rest())
1571                     {
1572                         if (curArgs->Current()->gtPhiArg.gtSsaNum == ssaNum)
1573                         {
1574                             alreadyArg = true;
1575                             break;
1576                         }
1577                     }
1578                     if (!alreadyArg)
1579                     {
1580                         // Add the new argument.
1581                         GenTreePtr newPhiArg =
1582                             new (m_pCompiler, GT_PHI_ARG) GenTreePhiArg(lclVar->TypeGet(), lclNum, ssaNum, block);
1583                         phiNode->gtOp.gtOp1 = new (m_pCompiler, GT_LIST) GenTreeArgList(newPhiArg, argList);
1584
1585                         DBG_SSA_JITDUMP("  Added phi arg u:%d for V%02u from BB%02u in BB%02u.\n", ssaNum, lclNum,
1586                                         block->bbNum, handlerStart->bbNum);
1587
1588                         m_pCompiler->gtSetStmtInfo(stmt);
1589                         m_pCompiler->fgSetStmtSeq(stmt);
1590                     }
1591                 }
1592
1593                 // Now handle memory.
1594                 for (MemoryKind memoryKind : allMemoryKinds())
1595                 {
1596                     BasicBlock::MemoryPhiArg*& handlerMemoryPhi = handlerStart->bbMemorySsaPhiFunc[memoryKind];
1597                     if (handlerMemoryPhi != nullptr)
1598                     {
1599                         if ((memoryKind == GcHeap) && m_pCompiler->byrefStatesMatchGcHeapStates)
1600                         {
1601                             // We've already added the arg to the phi shared with ByrefExposed if needed,
1602                             // but still need to update bbMemorySsaPhiFunc to stay in sync.
1603                             assert(memoryKind > ByrefExposed);
1604                             assert(block->bbMemorySsaNumOut[memoryKind] == block->bbMemorySsaNumOut[ByrefExposed]);
1605                             assert(handlerStart->bbMemorySsaPhiFunc[ByrefExposed]->m_ssaNum ==
1606                                    block->bbMemorySsaNumOut[memoryKind]);
1607                             handlerMemoryPhi = handlerStart->bbMemorySsaPhiFunc[ByrefExposed];
1608
1609                             continue;
1610                         }
1611
1612                         if (handlerMemoryPhi == BasicBlock::EmptyMemoryPhiDef)
1613                         {
1614                             handlerMemoryPhi =
1615                                 new (m_pCompiler) BasicBlock::MemoryPhiArg(block->bbMemorySsaNumOut[memoryKind]);
1616                         }
1617                         else
1618                         {
1619                             // This path has a potential to introduce redundant phi args, due to multiple
1620                             // preds of the same try-begin block having the same live-out memory def, and/or
1621                             // due to nested try-begins each having preds with the same live-out memory def.
1622                             // Avoid doing quadratic processing on handler phis, and instead live with the
1623                             // occasional redundancy.
1624                             handlerMemoryPhi = new (m_pCompiler)
1625                                 BasicBlock::MemoryPhiArg(block->bbMemorySsaNumOut[memoryKind], handlerMemoryPhi);
1626                         }
1627                         DBG_SSA_JITDUMP("  Added phi arg for %s u:%d from BB%02u in BB%02u.\n",
1628                                         memoryKindNames[memoryKind], block->bbMemorySsaNumOut[memoryKind], block->bbNum,
1629                                         handlerStart->bbNum);
1630                     }
1631                 }
1632
1633                 tryInd = succTry->ebdEnclosingTryIndex;
1634             }
1635         }
1636     }
1637 }
1638
1639 /**
1640  * Walk the block's tree in the evaluation order and reclaim rename stack for var definitions.
1641  *
1642  * @param block Block for which SSA variables have to be renamed.
1643  * @param pRenameState The incremental rename information stored during renaming process.
1644  *
1645  */
1646 void SsaBuilder::BlockPopStacks(BasicBlock* block, SsaRenameState* pRenameState)
1647 {
1648     // Pop the names given to the non-phi nodes.
1649     pRenameState->PopBlockStacks(block);
1650
1651     // And for memory.
1652     for (MemoryKind memoryKind : allMemoryKinds())
1653     {
1654         if ((memoryKind == GcHeap) && m_pCompiler->byrefStatesMatchGcHeapStates)
1655         {
1656             // GcHeap and ByrefExposed share a rename stack, so don't try
1657             // to pop it a second time.
1658             continue;
1659         }
1660         pRenameState->PopBlockMemoryStack(memoryKind, block);
1661     }
1662 }
1663
1664 /**
1665  * Perform variable renaming.
1666  *
1667  * Walks the blocks and renames all var defs with ssa numbers and all uses with the
1668  * current count that is in the top of the stack. Assigns phi node rhs variables
1669  * (i.e., the arguments to the phi.) Then, calls the function recursively on child
1670  * nodes in the DOM tree to continue the renaming process.
1671  *
1672  * @param block Block for which SSA variables have to be renamed.
1673  * @param pRenameState The incremental rename information stored during renaming process.
1674  *
1675  * @remarks At the end of the method, m_uses and m_defs should be populated linking the
1676  *          uses and defs.
1677  *
1678  * @see Briggs, Cooper, Harvey and Simpson "Practical Improvements to the Construction
1679  *      and Destruction of Static Single Assignment Form."
1680  */
1681
1682 void SsaBuilder::RenameVariables(BlkToBlkSetMap* domTree, SsaRenameState* pRenameState)
1683 {
1684     JITDUMP("*************** In SsaBuilder::RenameVariables()\n");
1685
1686     // The first thing we do is treat parameters and must-init variables as if they have a
1687     // virtual definition before entry -- they start out at SSA name 1.
1688     for (unsigned i = 0; i < m_pCompiler->lvaCount; i++)
1689     {
1690         LclVarDsc* varDsc = &m_pCompiler->lvaTable[i];
1691
1692 #ifdef DEBUG
1693         varDsc->lvNumSsaNames = SsaConfig::UNINIT_SSA_NUM; // Start off fresh...
1694 #endif
1695
1696         if (varDsc->lvIsParam || m_pCompiler->info.compInitMem || varDsc->lvMustInit ||
1697             (varDsc->lvTracked &&
1698              VarSetOps::IsMember(m_pCompiler, m_pCompiler->fgFirstBB->bbLiveIn, varDsc->lvVarIndex)))
1699         {
1700             unsigned count = pRenameState->CountForDef(i);
1701
1702             // In ValueNum we'd assume un-inited variables get FIRST_SSA_NUM.
1703             assert(count == SsaConfig::FIRST_SSA_NUM);
1704 #ifdef DEBUG
1705             varDsc->lvNumSsaNames++;
1706 #endif
1707             pRenameState->Push(nullptr, i, count);
1708         }
1709     }
1710
1711     // In ValueNum we'd assume un-inited memory gets FIRST_SSA_NUM.
1712     // The memory is a parameter.  Use FIRST_SSA_NUM as first SSA name.
1713     unsigned initMemoryCount = pRenameState->CountForMemoryDef();
1714     assert(initMemoryCount == SsaConfig::FIRST_SSA_NUM);
1715     for (MemoryKind memoryKind : allMemoryKinds())
1716     {
1717         if ((memoryKind == GcHeap) && m_pCompiler->byrefStatesMatchGcHeapStates)
1718         {
1719             // GcHeap shares its stack with ByrefExposed; don't re-push.
1720             continue;
1721         }
1722         pRenameState->PushMemory(memoryKind, m_pCompiler->fgFirstBB, initMemoryCount);
1723     }
1724
1725     // Initialize the memory ssa numbers for unreachable blocks. ValueNum expects
1726     // memory ssa numbers to have some intitial value.
1727     for (BasicBlock* block = m_pCompiler->fgFirstBB; block; block = block->bbNext)
1728     {
1729         if (block->bbIDom == nullptr)
1730         {
1731             for (MemoryKind memoryKind : allMemoryKinds())
1732             {
1733                 block->bbMemorySsaNumIn[memoryKind]  = initMemoryCount;
1734                 block->bbMemorySsaNumOut[memoryKind] = initMemoryCount;
1735             }
1736         }
1737     }
1738
1739     struct BlockWork
1740     {
1741         BasicBlock* m_blk;
1742         bool        m_processed; // Whether the this block have already been processed: its var renamed, and children
1743                                  // processed.
1744                                  // If so, awaiting only BlockPopStacks.
1745         BlockWork(BasicBlock* blk, bool processed = false) : m_blk(blk), m_processed(processed)
1746         {
1747         }
1748     };
1749     typedef jitstd::vector<BlockWork> BlockWorkStack;
1750     BlockWorkStack*                   blocksToDo =
1751         new (jitstd::utility::allocate<BlockWorkStack>(m_allocator), jitstd::placement_t()) BlockWorkStack(m_allocator);
1752
1753     blocksToDo->push_back(BlockWork(m_pCompiler->fgFirstBB)); // Probably have to include other roots of dom tree.
1754
1755     while (blocksToDo->size() != 0)
1756     {
1757         BlockWork blockWrk = blocksToDo->back();
1758         blocksToDo->pop_back();
1759         BasicBlock* block = blockWrk.m_blk;
1760
1761         DBG_SSA_JITDUMP("[SsaBuilder::RenameVariables](BB%02u, processed = %d)\n", block->bbNum, blockWrk.m_processed);
1762
1763         if (!blockWrk.m_processed)
1764         {
1765             // Push the block back on the stack with "m_processed" true, to record the fact that when its children have
1766             // been (recursively) processed, we still need to call BlockPopStacks on it.
1767             blocksToDo->push_back(BlockWork(block, true));
1768
1769             // Walk the block give counts to DEFs and give top of stack count for USEs.
1770             BlockRenameVariables(block, pRenameState);
1771
1772             // Assign arguments to the phi node of successors, corresponding to the block's index.
1773             AssignPhiNodeRhsVariables(block, pRenameState);
1774
1775             // Recurse with the block's DOM children.
1776             BlkSet* pBlkSet;
1777             if (domTree->Lookup(block, &pBlkSet))
1778             {
1779                 for (BlkSet::KeyIterator child = pBlkSet->Begin(); !child.Equal(pBlkSet->End()); ++child)
1780                 {
1781                     DBG_SSA_JITDUMP("[SsaBuilder::RenameVariables](pushing dom child BB%02u)\n", child.Get()->bbNum);
1782                     blocksToDo->push_back(BlockWork(child.Get()));
1783                 }
1784             }
1785         }
1786         else
1787         {
1788             // Done, pop all the stack count, if there is one for this block.
1789             BlockPopStacks(block, pRenameState);
1790             DBG_SSA_JITDUMP("[SsaBuilder::RenameVariables] done with BB%02u\n", block->bbNum);
1791         }
1792     }
1793
1794     // Remember the number of memory SSA names.
1795     m_pCompiler->lvMemoryNumSsaNames = pRenameState->MemoryCount();
1796 }
1797
1798 #ifdef DEBUG
1799 /**
1800  * Print the blocks, the phi nodes get printed as well.
1801  * @example:
1802  * After SSA BB02:
1803  *                [0027CC0C] -----------                 stmtExpr  void  (IL 0x019...0x01B)
1804  * N001 (  1,  1)       [0027CB70] -----------                 const     int    23
1805  * N003 (  3,  3)    [0027CBD8] -A------R--                 =         int
1806  * N002 (  1,  1)       [0027CBA4] D------N---                 lclVar    int    V01 arg1         d:5
1807  *
1808  * After SSA BB04:
1809  *                [0027D530] -----------                 stmtExpr  void  (IL   ???...  ???)
1810  * N002 (  0,  0)       [0027D4C8] -----------                 phi       int
1811  *                            [0027D8CC] -----------                 lclVar    int    V01 arg1         u:5
1812  *                            [0027D844] -----------                 lclVar    int    V01 arg1         u:4
1813  * N004 (  2,  2)    [0027D4FC] -A------R--                 =         int
1814  * N003 (  1,  1)       [0027D460] D------N---                 lclVar    int    V01 arg1         d:3
1815  */
1816 void SsaBuilder::Print(BasicBlock** postOrder, int count)
1817 {
1818     for (int i = count - 1; i >= 0; --i)
1819     {
1820         printf("After SSA BB%02u:\n", postOrder[i]->bbNum);
1821         m_pCompiler->gtDispTreeList(postOrder[i]->bbTreeList);
1822     }
1823 }
1824 #endif // DEBUG
1825
1826 /**
1827  * Build SSA form.
1828  *
1829  * Sorts the graph topologically.
1830  *   - Collects them in postOrder array.
1831  *
1832  * Identifies each block's immediate dominator.
1833  *   - Computes this in bbIDom of each BasicBlock.
1834  *
1835  * Computes DOM tree relation.
1836  *   - Computes domTree as block -> set of blocks.
1837  *   - Computes pre/post order traversal of the DOM tree.
1838  *
1839  * Inserts phi nodes.
1840  *   - Computes dominance frontier as block -> set of blocks.
1841  *   - Allocates block use/def/livein/liveout and computes it.
1842  *   - Inserts phi nodes with only rhs at the beginning of the blocks.
1843  *
1844  * Renames variables.
1845  *   - Walks blocks in evaluation order and gives uses and defs names.
1846  *   - Gives empty phi nodes their rhs arguments as they become known while renaming.
1847  *
1848  * @return true if successful, for now, this must always be true.
1849  *
1850  * @see "A simple, fast dominance algorithm" by Keith D. Cooper, Timothy J. Harvey, Ken Kennedy.
1851  * @see Briggs, Cooper, Harvey and Simpson "Practical Improvements to the Construction
1852  *      and Destruction of Static Single Assignment Form."
1853  */
1854 void SsaBuilder::Build()
1855 {
1856 #ifdef DEBUG
1857     if (m_pCompiler->verbose)
1858     {
1859         printf("*************** In SsaBuilder::Build()\n");
1860     }
1861 #endif
1862
1863     // Ensure that there's a first block outside a try, so that the dominator tree has a unique root.
1864     SetupBBRoot();
1865
1866     // Just to keep block no. & index same add 1.
1867     int blockCount = m_pCompiler->fgBBNumMax + 1;
1868
1869     JITDUMP("[SsaBuilder] Max block count is %d.\n", blockCount);
1870
1871     // Allocate the postOrder array for the graph.
1872
1873     BasicBlock** postOrder;
1874
1875     if (blockCount > DEFAULT_MIN_OPTS_BB_COUNT)
1876     {
1877         postOrder = new (m_pCompiler->getAllocator()) BasicBlock*[blockCount];
1878     }
1879     else
1880     {
1881         postOrder = (BasicBlock**)alloca(blockCount * sizeof(BasicBlock*));
1882     }
1883
1884     // Topologically sort the graph.
1885     int count = TopologicalSort(postOrder, blockCount);
1886     JITDUMP("[SsaBuilder] Topologically sorted the graph.\n");
1887     EndPhase(PHASE_BUILD_SSA_TOPOSORT);
1888
1889     // Compute IDom(b).
1890     ComputeImmediateDom(postOrder, count);
1891
1892     // Compute the dominator tree.
1893     BlkToBlkSetMap* domTree = new (m_pCompiler->getAllocator()) BlkToBlkSetMap(m_pCompiler->getAllocator());
1894     ComputeDominators(postOrder, count, domTree);
1895     EndPhase(PHASE_BUILD_SSA_DOMS);
1896
1897     // Insert phi functions.
1898     InsertPhiFunctions(postOrder, count);
1899
1900     // Rename local variables and collect UD information for each ssa var.
1901     SsaRenameState* pRenameState = new (jitstd::utility::allocate<SsaRenameState>(m_allocator), jitstd::placement_t())
1902         SsaRenameState(m_allocator, m_pCompiler->lvaCount, m_pCompiler->byrefStatesMatchGcHeapStates);
1903     RenameVariables(domTree, pRenameState);
1904     EndPhase(PHASE_BUILD_SSA_RENAME);
1905
1906 #ifdef DEBUG
1907     // At this point we are in SSA form. Print the SSA form.
1908     if (m_pCompiler->verboseSsa)
1909     {
1910         Print(postOrder, count);
1911     }
1912 #endif
1913 }
1914
1915 void SsaBuilder::SetupBBRoot()
1916 {
1917     // Allocate a bbroot, if necessary.
1918     // We need a unique block to be the root of the dominator tree.
1919     // This can be violated if the first block is in a try, or if it is the first block of
1920     // a loop (which would necessarily be an infinite loop) -- i.e., it has a predecessor.
1921
1922     // If neither condition holds, no reason to make a new block.
1923     if (!m_pCompiler->fgFirstBB->hasTryIndex() && m_pCompiler->fgFirstBB->bbPreds == nullptr)
1924     {
1925         return;
1926     }
1927
1928     BasicBlock* bbRoot = m_pCompiler->bbNewBasicBlock(BBJ_NONE);
1929     bbRoot->bbFlags |= BBF_INTERNAL;
1930
1931     // May need to fix up preds list, so remember the old first block.
1932     BasicBlock* oldFirst = m_pCompiler->fgFirstBB;
1933
1934     // Copy the liveness information from the first basic block.
1935     if (m_pCompiler->fgLocalVarLivenessDone)
1936     {
1937         VarSetOps::Assign(m_pCompiler, bbRoot->bbLiveIn, oldFirst->bbLiveIn);
1938         VarSetOps::Assign(m_pCompiler, bbRoot->bbLiveOut, oldFirst->bbLiveIn);
1939     }
1940
1941     // Copy the bbWeight.  (This is technically wrong, if the first block is a loop head, but
1942     // it shouldn't matter...)
1943     bbRoot->inheritWeight(oldFirst);
1944
1945     // There's an artifical incoming reference count for the first BB.  We're about to make it no longer
1946     // the first BB, so decrement that.
1947     assert(oldFirst->bbRefs > 0);
1948     oldFirst->bbRefs--;
1949
1950     m_pCompiler->fgInsertBBbefore(m_pCompiler->fgFirstBB, bbRoot);
1951
1952     assert(m_pCompiler->fgFirstBB == bbRoot);
1953     if (m_pCompiler->fgComputePredsDone)
1954     {
1955         m_pCompiler->fgAddRefPred(oldFirst, bbRoot);
1956     }
1957 }
1958
1959 #ifdef DEBUG
1960 // This method asserts that SSA name constraints specified are satisfied.
1961 void Compiler::JitTestCheckSSA()
1962 {
1963     struct SSAName
1964     {
1965         unsigned m_lvNum;
1966         unsigned m_ssaNum;
1967
1968         static unsigned GetHashCode(SSAName ssaNm)
1969         {
1970             return ssaNm.m_lvNum << 16 | ssaNm.m_ssaNum;
1971         }
1972
1973         static bool Equals(SSAName ssaNm1, SSAName ssaNm2)
1974         {
1975             return ssaNm1.m_lvNum == ssaNm2.m_lvNum && ssaNm1.m_ssaNum == ssaNm2.m_ssaNum;
1976         }
1977     };
1978
1979     typedef SimplerHashTable<ssize_t, SmallPrimitiveKeyFuncs<ssize_t>, SSAName, JitSimplerHashBehavior>
1980         LabelToSSANameMap;
1981     typedef SimplerHashTable<SSAName, SSAName, ssize_t, JitSimplerHashBehavior> SSANameToLabelMap;
1982
1983     // If we have no test data, early out.
1984     if (m_nodeTestData == nullptr)
1985     {
1986         return;
1987     }
1988
1989     NodeToTestDataMap* testData = GetNodeTestData();
1990
1991     // First we have to know which nodes in the tree are reachable.
1992     NodeToIntMap* reachable = FindReachableNodesInNodeTestData();
1993
1994     LabelToSSANameMap* labelToSSA = new (getAllocatorDebugOnly()) LabelToSSANameMap(getAllocatorDebugOnly());
1995     SSANameToLabelMap* ssaToLabel = new (getAllocatorDebugOnly()) SSANameToLabelMap(getAllocatorDebugOnly());
1996
1997     if (verbose)
1998     {
1999         printf("\nJit Testing: SSA names.\n");
2000     }
2001     for (NodeToTestDataMap::KeyIterator ki = testData->Begin(); !ki.Equal(testData->End()); ++ki)
2002     {
2003         TestLabelAndNum tlAndN;
2004         GenTreePtr      node = ki.Get();
2005         bool            b    = testData->Lookup(node, &tlAndN);
2006         assert(b);
2007         if (tlAndN.m_tl == TL_SsaName)
2008         {
2009             if (node->OperGet() != GT_LCL_VAR)
2010             {
2011                 printf("SSAName constraint put on non-lcl-var expression ");
2012                 printTreeID(node);
2013                 printf(" (of type %s).\n", varTypeName(node->TypeGet()));
2014                 unreached();
2015             }
2016             GenTreeLclVarCommon* lcl = node->AsLclVarCommon();
2017
2018             int dummy;
2019             if (!reachable->Lookup(lcl, &dummy))
2020             {
2021                 printf("Node ");
2022                 printTreeID(lcl);
2023                 printf(" had a test constraint declared, but has become unreachable at the time the constraint is "
2024                        "tested.\n"
2025                        "(This is probably as a result of some optimization -- \n"
2026                        "you may need to modify the test case to defeat this opt.)\n");
2027                 unreached();
2028             }
2029
2030             if (verbose)
2031             {
2032                 printf("  Node: ");
2033                 printTreeID(lcl);
2034                 printf(", SSA name = <%d, %d> -- SSA name class %d.\n", lcl->gtLclNum, lcl->gtSsaNum, tlAndN.m_num);
2035             }
2036             SSAName ssaNm;
2037             if (labelToSSA->Lookup(tlAndN.m_num, &ssaNm))
2038             {
2039                 if (verbose)
2040                 {
2041                     printf("      Already in hash tables.\n");
2042                 }
2043                 // The mapping(s) must be one-to-one: if the label has a mapping, then the ssaNm must, as well.
2044                 ssize_t num2;
2045                 bool    b = ssaToLabel->Lookup(ssaNm, &num2);
2046                 // And the mappings must be the same.
2047                 if (tlAndN.m_num != num2)
2048                 {
2049                     printf("Node: ");
2050                     printTreeID(lcl);
2051                     printf(", SSA name = <%d, %d> was declared in SSA name class %d,\n", lcl->gtLclNum, lcl->gtSsaNum,
2052                            tlAndN.m_num);
2053                     printf(
2054                         "but this SSA name <%d,%d> has already been associated with a different SSA name class: %d.\n",
2055                         ssaNm.m_lvNum, ssaNm.m_ssaNum, num2);
2056                     unreached();
2057                 }
2058                 // And the current node must be of the specified SSA family.
2059                 if (!(lcl->gtLclNum == ssaNm.m_lvNum && lcl->gtSsaNum == ssaNm.m_ssaNum))
2060                 {
2061                     printf("Node: ");
2062                     printTreeID(lcl);
2063                     printf(", SSA name = <%d, %d> was declared in SSA name class %d,\n", lcl->gtLclNum, lcl->gtSsaNum,
2064                            tlAndN.m_num);
2065                     printf("but that name class was previously bound to a different SSA name: <%d,%d>.\n",
2066                            ssaNm.m_lvNum, ssaNm.m_ssaNum);
2067                     unreached();
2068                 }
2069             }
2070             else
2071             {
2072                 ssaNm.m_lvNum  = lcl->gtLclNum;
2073                 ssaNm.m_ssaNum = lcl->gtSsaNum;
2074                 ssize_t num;
2075                 // The mapping(s) must be one-to-one: if the label has no mapping, then the ssaNm may not, either.
2076                 if (ssaToLabel->Lookup(ssaNm, &num))
2077                 {
2078                     printf("Node: ");
2079                     printTreeID(lcl);
2080                     printf(", SSA name = <%d, %d> was declared in SSA name class %d,\n", lcl->gtLclNum, lcl->gtSsaNum,
2081                            tlAndN.m_num);
2082                     printf("but this SSA name has already been associated with a different name class: %d.\n", num);
2083                     unreached();
2084                 }
2085                 // Add to both mappings.
2086                 labelToSSA->Set(tlAndN.m_num, ssaNm);
2087                 ssaToLabel->Set(ssaNm, tlAndN.m_num);
2088                 if (verbose)
2089                 {
2090                     printf("      added to hash tables.\n");
2091                 }
2092             }
2093         }
2094     }
2095 }
2096 #endif // DEBUG