summaryrefslogtreecommitdiff
path: root/src/jit/ssabuilder.h
blob: 7a97375fb71470c956fc1d13f03a11d3cf04240f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.

// ==++==
//

//

//
// ==--==

/*XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX                                                                           XX
XX                                  SSA                                      XX
XX                                                                           XX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
*/

#pragma once
#pragma warning(disable : 4503) // 'identifier' : decorated name length exceeded, name was truncated

#undef SSA_FEATURE_USEDEF
#undef SSA_FEATURE_DOMARR

#include "compiler.h"

struct SsaRenameState;

typedef int LclVarNum;

// Pair of a local var name eg: V01 and Ssa number; eg: V01_01
typedef jitstd::pair<LclVarNum, int> SsaVarName;

class SsaBuilder
{
private:
    struct SsaVarNameHasher
    {
        /**
         * Hash functor used in maps to hash a given key.
         *
         * @params key SsaVarName which is a pair of lclNum and ssaNum which defines a variable.
         * @return Hash value corresponding to a key.
         */
        size_t operator()(const SsaVarName& key) const
        {
            return jitstd::hash<__int64>()((((__int64)key.first) << sizeof(int)) | key.second);
        }
    };

    // Used to maintain a map of a given SSA numbering to its use or def.
    typedef jitstd::unordered_map<SsaVarName, jitstd::vector<GenTree*>, SsaVarNameHasher> VarToUses;
    typedef jitstd::unordered_map<SsaVarName, GenTree*, SsaVarNameHasher>                 VarToDef;

    inline void EndPhase(Phases phase)
    {
        m_pCompiler->EndPhase(phase);
    }

public:
    // Constructor
    SsaBuilder(Compiler* pCompiler, CompAllocator* pAllocator);

    // Requires stmt nodes to be already sequenced in evaluation order. Analyzes the graph
    // for introduction of phi-nodes as GT_PHI tree nodes at the beginning of each block.
    // Each GT_LCL_VAR is given its ssa number through its gtSsaNum field in the node.
    // Each GT_PHI node will have gtOp1 set to lhs of the phi node and the gtOp2 to be a
    // GT_LIST of GT_PHI_ARG. Each use or def is denoted by the corresponding GT_LCL_VAR
    // tree. For example, to get all uses of a particular variable fully defined by its
    // lclNum and ssaNum, one would use m_uses and look up all the uses. Similarly, a single
    // def of an SSA variable can be looked up similarly using m_defs member.
    void Build();

    // Requires "bbIDom" of each block to be computed. Requires "domTree" to be allocated
    // and can be updated, i.e., by adding mapping from a block to it's dominated children.
    // Using IDom of each basic block, compute the whole domTree. If a block "b" has IDom "i",
    // then, block "b" is dominated by "i". The mapping then is i -> { ..., b, ... }, in
    // other words, "domTree" is a tree represented by nodes mapped to their children.
    static void ComputeDominators(Compiler* pCompiler, BlkToBlkSetMap* domTree);

private:
    // Ensures that the basic block graph has a root for the dominator graph, by ensuring
    // that there is a first block that is not in a try region (adding an empty block for that purpose
    // if necessary).  Eventually should move to Compiler.
    void SetupBBRoot();

    // Requires "postOrder" to be an array of size "count". Requires "count" to at least
    // be the size of the flow graph. Sorts the current compiler's flow-graph and places
    // the blocks in post order (i.e., a node's children first) in the array. Returns the
    // number of nodes visited while sorting the graph. In other words, valid entries in
    // the output array.
    int TopologicalSort(BasicBlock** postOrder, int count);

    // Requires "postOrder" to hold the blocks of the flowgraph in topologically sorted
    // order. Requires count to be the valid entries in the "postOrder" array. Computes
    // each block's immediate dominator and records it in the BasicBlock in bbIDom.
    void ComputeImmediateDom(BasicBlock** postOrder, int count);

#ifdef SSA_FEATURE_DOMARR
    // Requires "curBlock" to be the first basic block at the first step of the recursion.
    // Requires "domTree" to be a adjacency list (actually, a set of blocks with a set of blocks
    // as children.) Requires "preIndex" and "postIndex" to be initialized to 0 at entry into recursion.
    // Computes arrays "m_pDomPreOrder" and "m_pDomPostOrder" of block indices such that the blocks of a
    // "domTree" are in pre and postorder respectively.
    void DomTreeWalk(BasicBlock* curBlock, const BlkToBlkSetMap& domTree, int* preIndex, int* postIndex);
#endif

    // Requires all blocks to have computed "bbIDom." Requires "domTree" to be a preallocated BlkToBlkSetMap.
    // Helper to compute "domTree" from the pre-computed bbIDom of the basic blocks.
    static void ConstructDomTreeForBlock(Compiler* pCompiler, BasicBlock* block, BlkToBlkSetMap* domTree);

    // Requires "postOrder" to hold the blocks of the flowgraph in topologically sorted order. Requires
    // count to be the valid entries in the "postOrder" array. Computes "domTree" as a adjacency list
    // like object, i.e., a set of blocks with a set of blocks as children defining the DOM relation.
    void ComputeDominators(BasicBlock** postOrder, int count, BlkToBlkSetMap* domTree);

#ifdef DEBUG
    // Display the dominator tree.
    static void DisplayDominators(BlkToBlkSetMap* domTree);
#endif // DEBUG

    // Requires "postOrder" to hold the blocks of the flowgraph in topologically sorted order. Requires
    // count to be the valid entries in the "postOrder" array.  Returns a mapping from blocks to their
    // iterated dominance frontiers.  (Recall that the dominance frontier of a block B is the set of blocks
    // B3 such that there exists some B2 s.t. B3 is a successor of B2, and B dominates B2.  Note that this dominance
    // need not be strict -- B2 and B may be the same node.  The iterated dominance frontier is formed by a closure
    // operation: the IDF of B is the smallest set that includes B's dominance frontier, and also includes the dominance
    // frontier of all elements of the set.)
    BlkToBlkSetMap* ComputeIteratedDominanceFrontier(BasicBlock** postOrder, int count);

    // Requires "postOrder" to hold the blocks of the flowgraph in topologically sorted order. Requires
    // count to be the valid entries in the "postOrder" array. Inserts GT_PHI nodes at the beginning
    // of basic blocks that require them like so:
    // GT_ASG(GT_LCL_VAR, GT_PHI(GT_PHI_ARG(GT_LCL_VAR, Block*), GT_LIST(GT_PHI_ARG(GT_LCL_VAR, Block*), NULL));
    void InsertPhiFunctions(BasicBlock** postOrder, int count);

    // Requires "domTree" to be the dominator tree relation defined by a DOM b.
    // Requires "pRenameState" to have counts and stacks at their initial state.
    // Assigns gtSsaNames to all variables.
    void RenameVariables(BlkToBlkSetMap* domTree, SsaRenameState* pRenameState);

    // Requires "block" to be any basic block participating in variable renaming, and has at least a
    // definition that pushed a ssa number into the rename stack for a variable. Requires "pRenameState"
    // to have variable stacks that have counts pushed into them for the block while assigning def
    // numbers. Pops the stack for any local variable that has an entry for block on top.
    void BlockPopStacks(BasicBlock* block, SsaRenameState* pRenameState);

    // Requires "block" to be non-NULL; and is searched for defs and uses to assign ssa numbers.
    // Requires "pRenameState" to be non-NULL and be currently used for variables renaming.
    void BlockRenameVariables(BasicBlock* block, SsaRenameState* pRenameState);

    // Requires "tree" (assumed to be a statement in "block") to be searched for defs and uses to assign ssa numbers.
    // Requires "pRenameState" to be non-NULL and be currently used for variables renaming.  Assumes that "isPhiDefn"
    // implies that any definition occurring within "tree" is a phi definition.
    void TreeRenameVariables(GenTree* tree, BasicBlock* block, SsaRenameState* pRenameState, bool isPhiDefn);

    // Assumes that "block" contains a definition for local var "lclNum", with SSA number "count".
    // IF "block" is within one or more try blocks,
    // and the local variable is live at the start of the corresponding handlers,
    // add this SSA number "count" to the argument list of the phi for the variable in the start
    // block of those handlers.
    void AddDefToHandlerPhis(BasicBlock* block, unsigned lclNum, unsigned count);

    // Same as above, for memory.
    void AddMemoryDefToHandlerPhis(MemoryKind memoryKind, BasicBlock* block, unsigned count);

    // Requires "block" to be non-NULL.  Requires "pRenameState" to be non-NULL and be currently used
    // for variables renaming. Assigns the rhs arguments to the phi, i.e., block's phi node arguments.
    void AssignPhiNodeRhsVariables(BasicBlock* block, SsaRenameState* pRenameState);

    // Requires "tree" to be a local variable node. Maintains a map of <lclNum, ssaNum> -> tree
    // information in m_defs.
    void AddDefPoint(GenTree* tree, BasicBlock* blk);
#ifdef SSA_FEATURE_USEDEF
    // Requires "tree" to be a local variable node. Maintains a map of <lclNum, ssaNum> -> tree
    // information in m_uses.
    void AddUsePoint(GenTree* tree);
#endif

    // Returns true, and sets "*ppIndirAssign", if "tree" has been recorded as an indirect assignment.
    // (If the tree is an assignment, it's a definition only if it's labeled as an indirect definition, where
    // we took the address of the local elsewhere in the extended tree.)
    bool IsIndirectAssign(GenTreePtr tree, Compiler::IndirectAssignmentAnnotation** ppIndirAssign);

#ifdef DEBUG
    void Print(BasicBlock** postOrder, int count);
#endif

private:
#ifdef SSA_FEATURE_USEDEF
    // Use Def information after SSA. To query the uses and def of a given ssa var,
    // probe these data structures.
    // Do not move these outside of this class, use accessors/interface methods.
    VarToUses m_uses;
    VarToDef  m_defs;
#endif

#ifdef SSA_FEATURE_DOMARR
    // To answer queries of type a DOM b.
    // Do not move these outside of this class, use accessors/interface methods.
    int* m_pDomPreOrder;
    int* m_pDomPostOrder;
#endif

    Compiler* m_pCompiler;

    // Used to allocate space for jitstd data structures.
    jitstd::allocator<void> m_allocator;
};