src/jit/ssabuilder.h

   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_USEDEF
   9 #undef SSA_FEATURE_DOMARR
  10
  11 #include "compiler.h"
  12
  13 struct SsaRenameState;
  14
  15 typedef int LclVarNum;
  16
  17 // Pair of a local var name eg: V01 and Ssa number; eg: V01_01
  18 typedef jitstd::pair<LclVarNum, int> SsaVarName;
  19
  20 class SsaBuilder
  21 {
  22 private:
  23     struct SsaVarNameHasher
  24     {
  25         /**
  26          * Hash functor used in maps to hash a given key.
  27          *
  28          * @params key SsaVarName which is a pair of lclNum and ssaNum which defines a variable.
  29          * @return Hash value corresponding to a key.
  30          */
  31         size_t operator()(const SsaVarName& key) const
  32         {
  33             return jitstd::hash<__int64>()((((__int64)key.first) << sizeof(int)) | key.second);
  34         }
  35     };
  36
  37     // Used to maintain a map of a given SSA numbering to its use or def.
  38     typedef jitstd::unordered_map<SsaVarName, jitstd::vector<GenTree*>, SsaVarNameHasher> VarToUses;
  39     typedef jitstd::unordered_map<SsaVarName, GenTree*, SsaVarNameHasher>                 VarToDef;
  40
  41     inline void EndPhase(Phases phase)
  42     {
  43         m_pCompiler->EndPhase(phase);
  44     }
  45
  46 public:
  47     // Constructor
  48     SsaBuilder(Compiler* pCompiler);
  49
  50     // Requires stmt nodes to be already sequenced in evaluation order. Analyzes the graph
  51     // for introduction of phi-nodes as GT_PHI tree nodes at the beginning of each block.
  52     // Each GT_LCL_VAR is given its ssa number through its gtSsaNum field in the node.
  53     // Each GT_PHI node will have gtOp1 set to lhs of the phi node and the gtOp2 to be a
  54     // GT_LIST of GT_PHI_ARG. Each use or def is denoted by the corresponding GT_LCL_VAR
  55     // tree. For example, to get all uses of a particular variable fully defined by its
  56     // lclNum and ssaNum, one would use m_uses and look up all the uses. Similarly, a single
  57     // def of an SSA variable can be looked up similarly using m_defs member.
  58     void Build();
  59
  60     // Requires "bbIDom" of each block to be computed. Requires "domTree" to be allocated
  61     // and can be updated, i.e., by adding mapping from a block to it's dominated children.
  62     // Using IDom of each basic block, compute the whole domTree. If a block "b" has IDom "i",
  63     // then, block "b" is dominated by "i". The mapping then is i -> { ..., b, ... }, in
  64     // other words, "domTree" is a tree represented by nodes mapped to their children.
  65     static void ComputeDominators(Compiler* pCompiler, BlkToBlkSetMap* domTree);
  66
  67 private:
  68     // Ensures that the basic block graph has a root for the dominator graph, by ensuring
  69     // that there is a first block that is not in a try region (adding an empty block for that purpose
  70     // if necessary).  Eventually should move to Compiler.
  71     void SetupBBRoot();
  72
  73     // Requires "postOrder" to be an array of size "count". Requires "count" to at least
  74     // be the size of the flow graph. Sorts the current compiler's flow-graph and places
  75     // the blocks in post order (i.e., a node's children first) in the array. Returns the
  76     // number of nodes visited while sorting the graph. In other words, valid entries in
  77     // the output array.
  78     int TopologicalSort(BasicBlock** postOrder, int count);
  79
  80     // Requires "postOrder" to hold the blocks of the flowgraph in topologically sorted
  81     // order. Requires count to be the valid entries in the "postOrder" array. Computes
  82     // each block's immediate dominator and records it in the BasicBlock in bbIDom.
  83     void ComputeImmediateDom(BasicBlock** postOrder, int count);
  84
  85 #ifdef SSA_FEATURE_DOMARR
  86     // Requires "curBlock" to be the first basic block at the first step of the recursion.
  87     // Requires "domTree" to be a adjacency list (actually, a set of blocks with a set of blocks
  88     // as children.) Requires "preIndex" and "postIndex" to be initialized to 0 at entry into recursion.
  89     // Computes arrays "m_pDomPreOrder" and "m_pDomPostOrder" of block indices such that the blocks of a
  90     // "domTree" are in pre and postorder respectively.
  91     void DomTreeWalk(BasicBlock* curBlock, BlkToBlkSetMap* domTree, int* preIndex, int* postIndex);
  92 #endif
  93
  94     // Requires all blocks to have computed "bbIDom." Requires "domTree" to be a preallocated BlkToBlkSetMap.
  95     // Helper to compute "domTree" from the pre-computed bbIDom of the basic blocks.
  96     static void ConstructDomTreeForBlock(Compiler* pCompiler, BasicBlock* block, BlkToBlkSetMap* domTree);
  97
  98     // Requires "postOrder" to hold the blocks of the flowgraph in topologically sorted order. Requires
  99     // count to be the valid entries in the "postOrder" array. Computes "domTree" as a adjacency list
 100     // like object, i.e., a set of blocks with a set of blocks as children defining the DOM relation.
 101     void ComputeDominators(BasicBlock** postOrder, int count, BlkToBlkSetMap* domTree);
 102
 103 #ifdef DEBUG
 104     // Display the dominator tree.
 105     static void DisplayDominators(BlkToBlkSetMap* domTree);
 106 #endif // DEBUG
 107
 108     // Requires "postOrder" to hold the blocks of the flowgraph in topologically sorted order. Requires
 109     // count to be the valid entries in the "postOrder" array.  Returns a mapping from blocks to their
 110     // iterated dominance frontiers.  (Recall that the dominance frontier of a block B is the set of blocks
 111     // B3 such that there exists some B2 s.t. B3 is a successor of B2, and B dominates B2.  Note that this dominance
 112     // need not be strict -- B2 and B may be the same node.  The iterated dominance frontier is formed by a closure
 113     // operation: the IDF of B is the smallest set that includes B's dominance frontier, and also includes the dominance
 114     // frontier of all elements of the set.)
 115     BlkToBlkVectorMap* ComputeIteratedDominanceFrontier(BasicBlock** postOrder, int count);
 116
 117     // Requires "postOrder" to hold the blocks of the flowgraph in topologically sorted order. Requires
 118     // count to be the valid entries in the "postOrder" array. Inserts GT_PHI nodes at the beginning
 119     // of basic blocks that require them like so:
 120     // GT_ASG(GT_LCL_VAR, GT_PHI(GT_PHI_ARG(GT_LCL_VAR, Block*), GT_LIST(GT_PHI_ARG(GT_LCL_VAR, Block*), NULL));
 121     void InsertPhiFunctions(BasicBlock** postOrder, int count);
 122
 123     // Requires "domTree" to be the dominator tree relation defined by a DOM b.
 124     // Requires "pRenameState" to have counts and stacks at their initial state.
 125     // Assigns gtSsaNames to all variables.
 126     void RenameVariables(BlkToBlkSetMap* domTree, SsaRenameState* pRenameState);
 127
 128     // Requires "block" to be any basic block participating in variable renaming, and has at least a
 129     // definition that pushed a ssa number into the rename stack for a variable. Requires "pRenameState"
 130     // to have variable stacks that have counts pushed into them for the block while assigning def
 131     // numbers. Pops the stack for any local variable that has an entry for block on top.
 132     void BlockPopStacks(BasicBlock* block, SsaRenameState* pRenameState);
 133
 134     // Requires "block" to be non-NULL; and is searched for defs and uses to assign ssa numbers.
 135     // Requires "pRenameState" to be non-NULL and be currently used for variables renaming.
 136     void BlockRenameVariables(BasicBlock* block, SsaRenameState* pRenameState);
 137
 138     // Requires "tree" (assumed to be a statement in "block") to be searched for defs and uses to assign ssa numbers.
 139     // Requires "pRenameState" to be non-NULL and be currently used for variables renaming.  Assumes that "isPhiDefn"
 140     // implies that any definition occurring within "tree" is a phi definition.
 141     void TreeRenameVariables(GenTree* tree, BasicBlock* block, SsaRenameState* pRenameState, bool isPhiDefn);
 142
 143     // Assumes that "block" contains a definition for local var "lclNum", with SSA number "count".
 144     // IF "block" is within one or more try blocks,
 145     // and the local variable is live at the start of the corresponding handlers,
 146     // add this SSA number "count" to the argument list of the phi for the variable in the start
 147     // block of those handlers.
 148     void AddDefToHandlerPhis(BasicBlock* block, unsigned lclNum, unsigned count);
 149
 150     // Same as above, for memory.
 151     void AddMemoryDefToHandlerPhis(MemoryKind memoryKind, BasicBlock* block, unsigned count);
 152
 153     // Requires "block" to be non-NULL.  Requires "pRenameState" to be non-NULL and be currently used
 154     // for variables renaming. Assigns the rhs arguments to the phi, i.e., block's phi node arguments.
 155     void AssignPhiNodeRhsVariables(BasicBlock* block, SsaRenameState* pRenameState);
 156
 157     // Requires "tree" to be a local variable node. Maintains a map of <lclNum, ssaNum> -> tree
 158     // information in m_defs.
 159     void AddDefPoint(GenTree* tree, BasicBlock* blk);
 160 #ifdef SSA_FEATURE_USEDEF
 161     // Requires "tree" to be a local variable node. Maintains a map of <lclNum, ssaNum> -> tree
 162     // information in m_uses.
 163     void AddUsePoint(GenTree* tree);
 164 #endif
 165
 166     // Returns true, and sets "*ppIndirAssign", if "tree" has been recorded as an indirect assignment.
 167     // (If the tree is an assignment, it's a definition only if it's labeled as an indirect definition, where
 168     // we took the address of the local elsewhere in the extended tree.)
 169     bool IsIndirectAssign(GenTreePtr tree, Compiler::IndirectAssignmentAnnotation** ppIndirAssign);
 170
 171 #ifdef DEBUG
 172     void Print(BasicBlock** postOrder, int count);
 173 #endif
 174
 175 private:
 176     Compiler*     m_pCompiler;
 177     CompAllocator m_allocator;
 178
 179     // Bit vector used by TopologicalSort and ComputeImmediateDom to track already visited blocks.
 180     BitVecTraits m_visitedTraits;
 181     BitVec       m_visited;
 182
 183 #ifdef SSA_FEATURE_DOMARR
 184     // To answer queries of type a DOM b.
 185     // Do not move these outside of this class, use accessors/interface methods.
 186     int* m_pDomPreOrder;
 187     int* m_pDomPostOrder;
 188 #endif
 189
 190 #ifdef SSA_FEATURE_USEDEF
 191     // Use Def information after SSA. To query the uses and def of a given ssa var,
 192     // probe these data structures.
 193     // Do not move these outside of this class, use accessors/interface methods.
 194     VarToUses m_uses;
 195     VarToDef  m_defs;
 196 #endif
 197 };