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