| 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 | 
|---|