| OLD | NEW |
| 1 //===- subzero/src/IceLiveness.cpp - Liveness analysis implementation -----===// | 1 //===- subzero/src/IceLiveness.cpp - Liveness analysis implementation -----===// |
| 2 // | 2 // |
| 3 // The Subzero Code Generator | 3 // The Subzero Code Generator |
| 4 // | 4 // |
| 5 // This file is distributed under the University of Illinois Open Source | 5 // This file is distributed under the University of Illinois Open Source |
| 6 // License. See LICENSE.TXT for details. | 6 // License. See LICENSE.TXT for details. |
| 7 // | 7 // |
| 8 //===----------------------------------------------------------------------===// | 8 //===----------------------------------------------------------------------===// |
| 9 /// | 9 /// |
| 10 /// \file | 10 /// \file |
| 11 /// This file provides some of the support for the Liveness class. In | 11 /// This file provides some of the support for the Liveness class. In |
| 12 /// particular, it handles the sparsity representation of the mapping | 12 /// particular, it handles the sparsity representation of the mapping between |
| 13 /// between Variables and CfgNodes. The idea is that since most | 13 /// Variables and CfgNodes. The idea is that since most variables are used only |
| 14 /// variables are used only within a single basic block, we can | 14 /// within a single basic block, we can partition the variables into "local" and |
| 15 /// partition the variables into "local" and "global" sets. Instead of | 15 /// "global" sets. Instead of sizing and indexing vectors according to |
| 16 /// sizing and indexing vectors according to Variable::Number, we | 16 /// Variable::Number, we create a mapping such that global variables are mapped |
| 17 /// create a mapping such that global variables are mapped to low | 17 /// to low indexes that are common across nodes, and local variables are mapped |
| 18 /// indexes that are common across nodes, and local variables are | 18 /// to a higher index space that is shared across nodes. |
| 19 /// mapped to a higher index space that is shared across nodes. | |
| 20 /// | 19 /// |
| 21 //===----------------------------------------------------------------------===// | 20 //===----------------------------------------------------------------------===// |
| 22 | 21 |
| 23 #include "IceLiveness.h" | 22 #include "IceLiveness.h" |
| 24 | 23 |
| 25 #include "IceCfg.h" | 24 #include "IceCfg.h" |
| 26 #include "IceCfgNode.h" | 25 #include "IceCfgNode.h" |
| 27 #include "IceDefs.h" | 26 #include "IceDefs.h" |
| 28 #include "IceInst.h" | 27 #include "IceInst.h" |
| 29 #include "IceOperand.h" | 28 #include "IceOperand.h" |
| 30 | 29 |
| 31 namespace Ice { | 30 namespace Ice { |
| 32 | 31 |
| 33 // Initializes the basic liveness-related data structures for full liveness | 32 // Initializes the basic liveness-related data structures for full liveness |
| 34 // analysis (IsFullInit=true), or for incremental update after phi lowering | 33 // analysis (IsFullInit=true), or for incremental update after phi lowering |
| 35 // (IsFullInit=false). In the latter case, FirstNode points to the first node | 34 // (IsFullInit=false). In the latter case, FirstNode points to the first node |
| 36 // added since starting phi lowering, and FirstVar points to the first Variable | 35 // added since starting phi lowering, and FirstVar points to the first Variable |
| 37 // added since starting phi lowering. | 36 // added since starting phi lowering. |
| 38 void Liveness::initInternal(NodeList::const_iterator FirstNode, | 37 void Liveness::initInternal(NodeList::const_iterator FirstNode, |
| 39 VarList::const_iterator FirstVar, bool IsFullInit) { | 38 VarList::const_iterator FirstVar, bool IsFullInit) { |
| 40 // Initialize most of the container sizes. | 39 // Initialize most of the container sizes. |
| 41 SizeT NumVars = Func->getVariables().size(); | 40 SizeT NumVars = Func->getVariables().size(); |
| 42 SizeT NumNodes = Func->getNumNodes(); | 41 SizeT NumNodes = Func->getNumNodes(); |
| 43 VariablesMetadata *VMetadata = Func->getVMetadata(); | 42 VariablesMetadata *VMetadata = Func->getVMetadata(); |
| 44 Nodes.resize(NumNodes); | 43 Nodes.resize(NumNodes); |
| 45 VarToLiveMap.resize(NumVars); | 44 VarToLiveMap.resize(NumVars); |
| 46 | 45 |
| 47 // Count the number of globals, and the number of locals for each block. | 46 // Count the number of globals, and the number of locals for each block. |
| 48 SizeT TmpNumGlobals = 0; | 47 SizeT TmpNumGlobals = 0; |
| 49 for (auto I = FirstVar, E = Func->getVariables().end(); I != E; ++I) { | 48 for (auto I = FirstVar, E = Func->getVariables().end(); I != E; ++I) { |
| 50 Variable *Var = *I; | 49 Variable *Var = *I; |
| 51 if (VMetadata->isMultiBlock(Var)) { | 50 if (VMetadata->isMultiBlock(Var)) { |
| 52 ++TmpNumGlobals; | 51 ++TmpNumGlobals; |
| 53 } else { | 52 } else { |
| 54 SizeT Index = VMetadata->getLocalUseNode(Var)->getIndex(); | 53 SizeT Index = VMetadata->getLocalUseNode(Var)->getIndex(); |
| 55 ++Nodes[Index].NumLocals; | 54 ++Nodes[Index].NumLocals; |
| 56 } | 55 } |
| 57 } | 56 } |
| 58 if (IsFullInit) | 57 if (IsFullInit) |
| 59 NumGlobals = TmpNumGlobals; | 58 NumGlobals = TmpNumGlobals; |
| 60 else | 59 else |
| 61 assert(TmpNumGlobals == 0); | 60 assert(TmpNumGlobals == 0); |
| 62 | 61 |
| 63 // Resize each LivenessNode::LiveToVarMap, and the global LiveToVarMap. Reset | 62 // Resize each LivenessNode::LiveToVarMap, and the global LiveToVarMap. Reset |
| 64 // the counts to 0. | 63 // the counts to 0. |
| 65 for (auto I = FirstNode, E = Func->getNodes().end(); I != E; ++I) { | 64 for (auto I = FirstNode, E = Func->getNodes().end(); I != E; ++I) { |
| 66 LivenessNode &N = Nodes[(*I)->getIndex()]; | 65 LivenessNode &N = Nodes[(*I)->getIndex()]; |
| 67 N.LiveToVarMap.assign(N.NumLocals, nullptr); | 66 N.LiveToVarMap.assign(N.NumLocals, nullptr); |
| 68 N.NumLocals = 0; | 67 N.NumLocals = 0; |
| 69 N.NumNonDeadPhis = 0; | 68 N.NumNonDeadPhis = 0; |
| 70 } | 69 } |
| 71 if (IsFullInit) | 70 if (IsFullInit) |
| 72 LiveToVarMap.assign(NumGlobals, nullptr); | 71 LiveToVarMap.assign(NumGlobals, nullptr); |
| 73 | 72 |
| 74 // Initialize the bitmask of which variables to track. | 73 // Initialize the bitmask of which variables to track. |
| 75 RangeMask.resize(NumVars); | 74 RangeMask.resize(NumVars); |
| 76 RangeMask.set(0, NumVars); // Track all variables by default. | 75 RangeMask.set(0, NumVars); // Track all variables by default. |
| 77 | 76 |
| 78 // Sort each variable into the appropriate LiveToVarMap. Set VarToLiveMap. | 77 // Sort each variable into the appropriate LiveToVarMap. Set VarToLiveMap. |
| 79 // Set RangeMask correctly for each variable. | 78 // Set RangeMask correctly for each variable. |
| 80 TmpNumGlobals = 0; | 79 TmpNumGlobals = 0; |
| 81 for (auto I = FirstVar, E = Func->getVariables().end(); I != E; ++I) { | 80 for (auto I = FirstVar, E = Func->getVariables().end(); I != E; ++I) { |
| 82 Variable *Var = *I; | 81 Variable *Var = *I; |
| 83 SizeT VarIndex = Var->getIndex(); | 82 SizeT VarIndex = Var->getIndex(); |
| 84 SizeT LiveIndex; | 83 SizeT LiveIndex; |
| 85 if (VMetadata->isMultiBlock(Var)) { | 84 if (VMetadata->isMultiBlock(Var)) { |
| 86 LiveIndex = TmpNumGlobals++; | 85 LiveIndex = TmpNumGlobals++; |
| 87 LiveToVarMap[LiveIndex] = Var; | 86 LiveToVarMap[LiveIndex] = Var; |
| 88 } else { | 87 } else { |
| (...skipping 16 matching lines...) Expand all Loading... |
| 105 (!IsFullInit && !Var->hasReg() && !Var->mustHaveReg())) | 104 (!IsFullInit && !Var->hasReg() && !Var->mustHaveReg())) |
| 106 RangeMask[VarIndex] = false; | 105 RangeMask[VarIndex] = false; |
| 107 } | 106 } |
| 108 | 107 |
| 109 // Process each node. | 108 // Process each node. |
| 110 for (auto I = FirstNode, E = Func->getNodes().end(); I != E; ++I) { | 109 for (auto I = FirstNode, E = Func->getNodes().end(); I != E; ++I) { |
| 111 LivenessNode &Node = Nodes[(*I)->getIndex()]; | 110 LivenessNode &Node = Nodes[(*I)->getIndex()]; |
| 112 // NumLocals, LiveToVarMap already initialized | 111 // NumLocals, LiveToVarMap already initialized |
| 113 Node.LiveIn.resize(NumGlobals); | 112 Node.LiveIn.resize(NumGlobals); |
| 114 Node.LiveOut.resize(NumGlobals); | 113 Node.LiveOut.resize(NumGlobals); |
| 115 // LiveBegin and LiveEnd are reinitialized before each pass over | 114 // LiveBegin and LiveEnd are reinitialized before each pass over the block. |
| 116 // the block. | |
| 117 } | 115 } |
| 118 } | 116 } |
| 119 | 117 |
| 120 void Liveness::init() { | 118 void Liveness::init() { |
| 121 constexpr bool IsFullInit = true; | 119 constexpr bool IsFullInit = true; |
| 122 NodeList::const_iterator FirstNode = Func->getNodes().begin(); | 120 NodeList::const_iterator FirstNode = Func->getNodes().begin(); |
| 123 VarList::const_iterator FirstVar = Func->getVariables().begin(); | 121 VarList::const_iterator FirstVar = Func->getVariables().begin(); |
| 124 initInternal(FirstNode, FirstVar, IsFullInit); | 122 initInternal(FirstNode, FirstVar, IsFullInit); |
| 125 } | 123 } |
| 126 | 124 |
| 127 void Liveness::initPhiEdgeSplits(NodeList::const_iterator FirstNode, | 125 void Liveness::initPhiEdgeSplits(NodeList::const_iterator FirstNode, |
| 128 VarList::const_iterator FirstVar) { | 126 VarList::const_iterator FirstVar) { |
| 129 constexpr bool IsFullInit = false; | 127 constexpr bool IsFullInit = false; |
| 130 initInternal(FirstNode, FirstVar, IsFullInit); | 128 initInternal(FirstNode, FirstVar, IsFullInit); |
| 131 } | 129 } |
| 132 | 130 |
| 133 Variable *Liveness::getVariable(SizeT LiveIndex, const CfgNode *Node) const { | 131 Variable *Liveness::getVariable(SizeT LiveIndex, const CfgNode *Node) const { |
| 134 if (LiveIndex < NumGlobals) | 132 if (LiveIndex < NumGlobals) |
| 135 return LiveToVarMap[LiveIndex]; | 133 return LiveToVarMap[LiveIndex]; |
| 136 SizeT NodeIndex = Node->getIndex(); | 134 SizeT NodeIndex = Node->getIndex(); |
| 137 return Nodes[NodeIndex].LiveToVarMap[LiveIndex - NumGlobals]; | 135 return Nodes[NodeIndex].LiveToVarMap[LiveIndex - NumGlobals]; |
| 138 } | 136 } |
| 139 | 137 |
| 140 } // end of namespace Ice | 138 } // end of namespace Ice |
| OLD | NEW |