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#pragma once
6#pragma warning(disable : 4503) // 'identifier' : decorated name length exceeded, name was truncated
7
8#undef SSA_FEATURE_DOMARR
9
10#include "compiler.h"
11
12struct SsaRenameState;
13
14typedef int LclVarNum;
15
16// Pair of a local var name eg: V01 and Ssa number; eg: V01_01
17typedef jitstd::pair<LclVarNum, int> SsaVarName;
18
19class SsaBuilder
20{
21private:
22 inline void EndPhase(Phases phase)
23 {
24 m_pCompiler->EndPhase(phase);
25 }
26
27 bool IncludeInSsa(unsigned lclNum);
28
29public:
30 // Constructor
31 SsaBuilder(Compiler* pCompiler);
32
33 // Requires stmt nodes to be already sequenced in evaluation order. Analyzes the graph
34 // for introduction of phi-nodes as GT_PHI tree nodes at the beginning of each block.
35 // Each GT_LCL_VAR is given its ssa number through its gtSsaNum field in the node.
36 // Each GT_PHI node will have gtOp1 set to lhs of the phi node and the gtOp2 to be a
37 // GT_LIST of GT_PHI_ARG. Each use or def is denoted by the corresponding GT_LCL_VAR
38 // tree. For example, to get all uses of a particular variable fully defined by its
39 // lclNum and ssaNum, one would use m_uses and look up all the uses. Similarly, a single
40 // def of an SSA variable can be looked up similarly using m_defs member.
41 void Build();
42
43 // Requires "bbIDom" of each block to be computed. Requires "domTree" to be allocated
44 // and can be updated, i.e., by adding mapping from a block to it's dominated children.
45 // Using IDom of each basic block, compute the whole domTree. If a block "b" has IDom "i",
46 // then, block "b" is dominated by "i". The mapping then is i -> { ..., b, ... }, in
47 // other words, "domTree" is a tree represented by nodes mapped to their children.
48 static void ComputeDominators(Compiler* pCompiler, BlkToBlkVectorMap* domTree);
49
50private:
51 // Ensures that the basic block graph has a root for the dominator graph, by ensuring
52 // that there is a first block that is not in a try region (adding an empty block for that purpose
53 // if necessary). Eventually should move to Compiler.
54 void SetupBBRoot();
55
56 // Requires "postOrder" to be an array of size "count". Requires "count" to at least
57 // be the size of the flow graph. Sorts the current compiler's flow-graph and places
58 // the blocks in post order (i.e., a node's children first) in the array. Returns the
59 // number of nodes visited while sorting the graph. In other words, valid entries in
60 // the output array.
61 int TopologicalSort(BasicBlock** postOrder, int count);
62
63 // Requires "postOrder" to hold the blocks of the flowgraph in topologically sorted
64 // order. Requires count to be the valid entries in the "postOrder" array. Computes
65 // each block's immediate dominator and records it in the BasicBlock in bbIDom.
66 void ComputeImmediateDom(BasicBlock** postOrder, int count);
67
68#ifdef SSA_FEATURE_DOMARR
69 // Requires "curBlock" to be the first basic block at the first step of the recursion.
70 // Requires "domTree" to be a adjacency list (actually, a set of blocks with a set of blocks
71 // as children.) Requires "preIndex" and "postIndex" to be initialized to 0 at entry into recursion.
72 // Computes arrays "m_pDomPreOrder" and "m_pDomPostOrder" of block indices such that the blocks of a
73 // "domTree" are in pre and postorder respectively.
74 void DomTreeWalk(BasicBlock* curBlock, BlkToBlkVectorMap* domTree, int* preIndex, int* postIndex);
75#endif
76
77 // Requires all blocks to have computed "bbIDom." Requires "domTree" to be a preallocated BlkToBlkVectorMap.
78 // Helper to compute "domTree" from the pre-computed bbIDom of the basic blocks.
79 static void ConstructDomTreeForBlock(Compiler* pCompiler, BasicBlock* block, BlkToBlkVectorMap* domTree);
80
81 // Requires "postOrder" to hold the blocks of the flowgraph in topologically sorted order. Requires
82 // count to be the valid entries in the "postOrder" array. Computes "domTree" as a adjacency list
83 // like object, i.e., a set of blocks with a set of blocks as children defining the DOM relation.
84 void ComputeDominators(BasicBlock** postOrder, int count, BlkToBlkVectorMap* domTree);
85
86#ifdef DEBUG
87 // Display the dominator tree.
88 static void DisplayDominators(BlkToBlkVectorMap* domTree);
89#endif // DEBUG
90
91 // Compute flow graph dominance frontiers.
92 void ComputeDominanceFrontiers(BasicBlock** postOrder, int count, BlkToBlkVectorMap* mapDF);
93
94 // Compute the iterated dominance frontier for the specified block.
95 void ComputeIteratedDominanceFrontier(BasicBlock* b, const BlkToBlkVectorMap* mapDF, BlkVector* bIDF);
96
97 // Requires "postOrder" to hold the blocks of the flowgraph in topologically sorted order. Requires
98 // count to be the valid entries in the "postOrder" array. Inserts GT_PHI nodes at the beginning
99 // of basic blocks that require them like so:
100 // GT_ASG(GT_LCL_VAR, GT_PHI(GT_PHI_ARG(GT_LCL_VAR, Block*), GT_LIST(GT_PHI_ARG(GT_LCL_VAR, Block*), NULL));
101 void InsertPhiFunctions(BasicBlock** postOrder, int count);
102
103 // Requires "domTree" to be the dominator tree relation defined by a DOM b.
104 // Requires "pRenameState" to have counts and stacks at their initial state.
105 // Assigns gtSsaNames to all variables.
106 void RenameVariables(BlkToBlkVectorMap* domTree, SsaRenameState* pRenameState);
107
108 // Requires "block" to be any basic block participating in variable renaming, and has at least a
109 // definition that pushed a ssa number into the rename stack for a variable. Requires "pRenameState"
110 // to have variable stacks that have counts pushed into them for the block while assigning def
111 // numbers. Pops the stack for any local variable that has an entry for block on top.
112 void BlockPopStacks(BasicBlock* block, SsaRenameState* pRenameState);
113
114 // Requires "block" to be non-NULL; and is searched for defs and uses to assign ssa numbers.
115 // Requires "pRenameState" to be non-NULL and be currently used for variables renaming.
116 void BlockRenameVariables(BasicBlock* block, SsaRenameState* pRenameState);
117
118 // Requires "tree" (assumed to be a statement in "block") to be searched for defs and uses to assign ssa numbers.
119 // Requires "pRenameState" to be non-NULL and be currently used for variables renaming. Assumes that "isPhiDefn"
120 // implies that any definition occurring within "tree" is a phi definition.
121 void TreeRenameVariables(GenTree* tree, BasicBlock* block, SsaRenameState* pRenameState, bool isPhiDefn);
122
123 // Assumes that "block" contains a definition for local var "lclNum", with SSA number "count".
124 // IF "block" is within one or more try blocks,
125 // and the local variable is live at the start of the corresponding handlers,
126 // add this SSA number "count" to the argument list of the phi for the variable in the start
127 // block of those handlers.
128 void AddDefToHandlerPhis(BasicBlock* block, unsigned lclNum, unsigned count);
129
130 // Same as above, for memory.
131 void AddMemoryDefToHandlerPhis(MemoryKind memoryKind, BasicBlock* block, unsigned count);
132
133 // Requires "block" to be non-NULL. Requires "pRenameState" to be non-NULL and be currently used
134 // for variables renaming. Assigns the rhs arguments to the phi, i.e., block's phi node arguments.
135 void AssignPhiNodeRhsVariables(BasicBlock* block, SsaRenameState* pRenameState);
136
137#ifdef DEBUG
138 void Print(BasicBlock** postOrder, int count);
139#endif
140
141private:
142 Compiler* m_pCompiler;
143 CompAllocator m_allocator;
144
145 // Bit vector used by TopologicalSort and ComputeImmediateDom to track already visited blocks.
146 BitVecTraits m_visitedTraits;
147 BitVec m_visited;
148
149#ifdef SSA_FEATURE_DOMARR
150 // To answer queries of type a DOM b.
151 // Do not move these outside of this class, use accessors/interface methods.
152 int* m_pDomPreOrder;
153 int* m_pDomPostOrder;
154#endif
155};
156