From ef1e2ab328087c61a6878c1e84f4fc5d710aebce Mon Sep 17 00:00:00 2001 From: dotnet-bot Date: Fri, 30 Jan 2015 14:14:42 -0800 Subject: Initial commit to populate CoreCLR repo [tfs-changeset: 1407945] --- src/jit/ssabuilder.h | 219 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 219 insertions(+) create mode 100644 src/jit/ssabuilder.h (limited to 'src/jit/ssabuilder.h') diff --git a/src/jit/ssabuilder.h b/src/jit/ssabuilder.h new file mode 100644 index 0000000000..c75c15eb51 --- /dev/null +++ b/src/jit/ssabuilder.h @@ -0,0 +1,219 @@ +// +// Copyright (c) Microsoft. All rights reserved. +// Licensed under the MIT license. See LICENSE file in the project root for full license 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 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, SsaVarNameHasher> VarToUses; + typedef jitstd::unordered_map VarToDef; + + inline void EndPhase(Phases phase) + { + m_pCompiler->EndPhase(phase); + } + +public: + + // Constructor + SsaBuilder(Compiler* pCompiler, IAllocator* pIAllocator); + + // 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 "Heap". + void AddHeapDefToHandlerPhis(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 -> 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 -> 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 m_allocator; +}; -- cgit v1.2.3