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