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