OLD | NEW |
1 //===- subzero/src/IceLiveness.h - Liveness analysis ------------*- C++ -*-===// | 1 //===- subzero/src/IceLiveness.h - Liveness analysis ------------*- C++ -*-===// |
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 /// \brief Declares the Liveness and LivenessNode classes, which are used for | 11 /// \brief Declares the Liveness and LivenessNode classes, which are used for |
12 /// liveness analysis. | 12 /// liveness analysis. |
13 /// | 13 /// |
14 /// The node-specific information tracked for each Variable includes whether it | 14 /// The node-specific information tracked for each Variable includes whether it |
15 /// is live on entry, whether it is live on exit, the instruction number that | 15 /// is live on entry, whether it is live on exit, the instruction number that |
16 /// starts its live range, and the instruction number that ends its live range. | 16 /// starts its live range, and the instruction number that ends its live range. |
17 /// At the Cfg level, the actual live intervals are recorded. | 17 /// At the Cfg level, the actual live intervals are recorded. |
18 /// | 18 /// |
19 //===----------------------------------------------------------------------===// | 19 //===----------------------------------------------------------------------===// |
20 | 20 |
21 #ifndef SUBZERO_SRC_ICELIVENESS_H | 21 #ifndef SUBZERO_SRC_ICELIVENESS_H |
22 #define SUBZERO_SRC_ICELIVENESS_H | 22 #define SUBZERO_SRC_ICELIVENESS_H |
23 | 23 |
24 #include "IceDefs.h" | 24 #include "IceDefs.h" |
25 #include "IceBitVector.h" | 25 #include "IceBitVector.h" |
26 #include "IceCfgNode.h" | 26 #include "IceCfgNode.h" |
| 27 #include "IceTLS.h" |
27 #include "IceTypes.h" | 28 #include "IceTypes.h" |
28 | 29 |
| 30 #include <memory> |
| 31 #include <utility> |
| 32 |
29 namespace Ice { | 33 namespace Ice { |
30 | 34 |
31 class Liveness { | 35 class Liveness { |
32 Liveness() = delete; | 36 Liveness() = delete; |
33 Liveness(const Liveness &) = delete; | 37 Liveness(const Liveness &) = delete; |
34 Liveness &operator=(const Liveness &) = delete; | 38 Liveness &operator=(const Liveness &) = delete; |
35 | 39 |
36 class LivenessNode { | 40 class LivenessNode { |
37 LivenessNode &operator=(const LivenessNode &) = delete; | 41 LivenessNode &operator=(const LivenessNode &) = delete; |
38 | 42 |
39 public: | 43 public: |
40 LivenessNode() = default; | 44 LivenessNode() = default; |
41 LivenessNode(const LivenessNode &) = default; | 45 LivenessNode(const LivenessNode &) = default; |
42 /// NumLocals is the number of Variables local to this block. | 46 /// NumLocals is the number of Variables local to this block. |
43 SizeT NumLocals = 0; | 47 SizeT NumLocals = 0; |
44 /// NumNonDeadPhis tracks the number of Phi instructions that | 48 /// NumNonDeadPhis tracks the number of Phi instructions that |
45 /// Inst::liveness() identified as tentatively live. If NumNonDeadPhis | 49 /// Inst::liveness() identified as tentatively live. If NumNonDeadPhis |
46 /// changes from the last liveness pass, then liveness has not yet | 50 /// changes from the last liveness pass, then liveness has not yet |
47 /// converged. | 51 /// converged. |
48 SizeT NumNonDeadPhis = 0; | 52 SizeT NumNonDeadPhis = 0; |
49 // LiveToVarMap maps a liveness bitvector index to a Variable. This is | 53 // LiveToVarMap maps a liveness bitvector index to a Variable. This is |
50 // generally just for printing/dumping. The index should be less than | 54 // generally just for printing/dumping. The index should be less than |
51 // NumLocals + Liveness::NumGlobals. | 55 // NumLocals + Liveness::NumGlobals. |
52 CfgVector<Variable *> LiveToVarMap; | 56 LivenessVector<Variable *> LiveToVarMap; |
53 // LiveIn and LiveOut track the in- and out-liveness of the global | 57 // LiveIn and LiveOut track the in- and out-liveness of the global |
54 // variables. The size of each vector is LivenessNode::NumGlobals. | 58 // variables. The size of each vector is LivenessNode::NumGlobals. |
55 LivenessBV LiveIn, LiveOut; | 59 LivenessBV LiveIn, LiveOut; |
56 // LiveBegin and LiveEnd track the instruction numbers of the start and end | 60 // LiveBegin and LiveEnd track the instruction numbers of the start and end |
57 // of each variable's live range within this block. The index/key of each | 61 // of each variable's live range within this block. The index/key of each |
58 // element is less than NumLocals + Liveness::NumGlobals. | 62 // element is less than NumLocals + Liveness::NumGlobals. |
59 LiveBeginEndMap LiveBegin, LiveEnd; | 63 LiveBeginEndMap LiveBegin, LiveEnd; |
60 }; | 64 }; |
61 | 65 |
62 public: | 66 public: |
63 Liveness(Cfg *Func, LivenessMode Mode) : Func(Func), Mode(Mode) {} | |
64 void init(); | 67 void init(); |
65 void initPhiEdgeSplits(NodeList::const_iterator FirstNode, | 68 void initPhiEdgeSplits(NodeList::const_iterator FirstNode, |
66 VarList::const_iterator FirstVar); | 69 VarList::const_iterator FirstVar); |
67 Cfg *getFunc() const { return Func; } | 70 Cfg *getFunc() const { return Func; } |
68 LivenessMode getMode() const { return Mode; } | 71 LivenessMode getMode() const { return Mode; } |
69 Variable *getVariable(SizeT LiveIndex, const CfgNode *Node) const; | 72 Variable *getVariable(SizeT LiveIndex, const CfgNode *Node) const; |
70 SizeT getLiveIndex(SizeT VarIndex) const { | 73 SizeT getLiveIndex(SizeT VarIndex) const { |
71 const SizeT LiveIndex = VarToLiveMap[VarIndex]; | 74 const SizeT LiveIndex = VarToLiveMap[VarIndex]; |
72 assert(LiveIndex != InvalidLiveIndex); | 75 assert(LiveIndex != InvalidLiveIndex); |
73 return LiveIndex; | 76 return LiveIndex; |
(...skipping 21 matching lines...) Expand all Loading... |
95 resize(Index); | 98 resize(Index); |
96 return &Nodes[Index].LiveBegin; | 99 return &Nodes[Index].LiveBegin; |
97 } | 100 } |
98 LiveBeginEndMap *getLiveEnd(const CfgNode *Node) { | 101 LiveBeginEndMap *getLiveEnd(const CfgNode *Node) { |
99 SizeT Index = Node->getIndex(); | 102 SizeT Index = Node->getIndex(); |
100 resize(Index); | 103 resize(Index); |
101 return &Nodes[Index].LiveEnd; | 104 return &Nodes[Index].LiveEnd; |
102 } | 105 } |
103 bool getRangeMask(SizeT Index) const { return RangeMask[Index]; } | 106 bool getRangeMask(SizeT Index) const { return RangeMask[Index]; } |
104 | 107 |
| 108 ArenaAllocator *getAllocator() const { return Alloc.get(); } |
| 109 |
| 110 static std::unique_ptr<Liveness> create(Cfg *Func, LivenessMode Mode) { |
| 111 return std::unique_ptr<Liveness>(new Liveness(Func, Mode)); |
| 112 } |
| 113 |
| 114 static void TlsInit() { LivenessAllocatorTraits::init(); } |
| 115 |
| 116 std::string dumpStr() const { |
| 117 return "MaxLocals(" + std::to_string(MaxLocals) + "), " |
| 118 "NumGlobals(" + |
| 119 std::to_string(NumGlobals) + ")"; |
| 120 } |
| 121 |
105 private: | 122 private: |
| 123 Liveness(Cfg *Func, LivenessMode Mode) |
| 124 : Alloc(new ArenaAllocator()), AllocScope(this), Func(Func), Mode(Mode) {} |
| 125 |
106 void initInternal(NodeList::const_iterator FirstNode, | 126 void initInternal(NodeList::const_iterator FirstNode, |
107 VarList::const_iterator FirstVar, bool IsFullInit); | 127 VarList::const_iterator FirstVar, bool IsFullInit); |
108 /// Resize Nodes so that Nodes[Index] is valid. | 128 /// Resize Nodes so that Nodes[Index] is valid. |
109 void resize(SizeT Index) { | 129 void resize(SizeT Index) { |
110 if (Index >= Nodes.size()) | 130 if (Index >= Nodes.size()) { |
| 131 assert(false && "The Nodes array is not expected to be resized."); |
111 Nodes.resize(Index + 1); | 132 Nodes.resize(Index + 1); |
| 133 } |
112 } | 134 } |
| 135 std::unique_ptr<ArenaAllocator> Alloc; |
| 136 LivenessAllocatorScope AllocScope; // Must be declared after Alloc. |
113 static constexpr SizeT InvalidLiveIndex = -1; | 137 static constexpr SizeT InvalidLiveIndex = -1; |
114 Cfg *Func; | 138 Cfg *Func; |
115 LivenessMode Mode; | 139 LivenessMode Mode; |
116 SizeT NumGlobals = 0; | |
117 /// Size of Nodes is Cfg::Nodes.size(). | 140 /// Size of Nodes is Cfg::Nodes.size(). |
118 CfgVector<LivenessNode> Nodes; | 141 LivenessVector<LivenessNode> Nodes; |
119 /// VarToLiveMap maps a Variable's Variable::Number to its live index within | 142 /// VarToLiveMap maps a Variable's Variable::Number to its live index within |
120 /// its basic block. | 143 /// its basic block. |
121 CfgVector<SizeT> VarToLiveMap; | 144 LivenessVector<SizeT> VarToLiveMap; |
122 /// LiveToVarMap is analogous to LivenessNode::LiveToVarMap, but for non-local | 145 /// LiveToVarMap is analogous to LivenessNode::LiveToVarMap, but for non-local |
123 /// variables. | 146 /// variables. |
124 CfgVector<Variable *> LiveToVarMap; | 147 LivenessVector<Variable *> LiveToVarMap; |
125 /// RangeMask[Variable::Number] indicates whether we want to track that | 148 /// RangeMask[Variable::Number] indicates whether we want to track that |
126 /// Variable's live range. | 149 /// Variable's live range. |
127 LivenessBV RangeMask; | 150 LivenessBV RangeMask; |
128 /// ScratchBV is a bitvector that can be reused across CfgNode passes, to | 151 /// ScratchBV is a bitvector that can be reused across CfgNode passes, to |
129 /// avoid having to allocate/deallocate memory so frequently. | 152 /// avoid having to allocate/deallocate memory so frequently. |
130 LivenessBV ScratchBV; | 153 LivenessBV ScratchBV; |
| 154 /// MaxLocals indicates what is the maximum number of local variables in a |
| 155 /// single basic block, across all blocks in a function. |
| 156 SizeT MaxLocals = 0; |
| 157 /// NumGlobals indicates how many global variables (i.e., Multi Block) exist |
| 158 /// for a function. |
| 159 SizeT NumGlobals = 0; |
131 }; | 160 }; |
132 | 161 |
133 } // end of namespace Ice | 162 } // end of namespace Ice |
134 | 163 |
135 #endif // SUBZERO_SRC_ICELIVENESS_H | 164 #endif // SUBZERO_SRC_ICELIVENESS_H |
OLD | NEW |