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