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