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 /// This file declares the Liveness and LivenessNode classes, | 11 /// This file declares the Liveness and LivenessNode classes, which are used for |
12 /// which are used for liveness analysis. The node-specific | 12 /// liveness analysis. The node-specific information tracked for each Variable |
13 /// information tracked for each Variable includes whether it is | 13 /// includes whether it is live on entry, whether it is live on exit, the |
14 /// live on entry, whether it is live on exit, the instruction number | 14 /// instruction number that starts its live range, and the instruction number |
15 /// that starts its live range, and the instruction number that ends | 15 /// that ends its live range. At the Cfg level, the actual live intervals are |
16 /// its live range. At the Cfg level, the actual live intervals are | |
17 /// recorded. | 16 /// recorded. |
18 /// | 17 /// |
19 //===----------------------------------------------------------------------===// | 18 //===----------------------------------------------------------------------===// |
20 | 19 |
21 #ifndef SUBZERO_SRC_ICELIVENESS_H | 20 #ifndef SUBZERO_SRC_ICELIVENESS_H |
22 #define SUBZERO_SRC_ICELIVENESS_H | 21 #define SUBZERO_SRC_ICELIVENESS_H |
23 | 22 |
24 #include "IceCfgNode.h" | 23 #include "IceCfgNode.h" |
25 #include "IceDefs.h" | 24 #include "IceDefs.h" |
26 #include "IceTypes.h" | 25 #include "IceTypes.h" |
27 | 26 |
28 namespace Ice { | 27 namespace Ice { |
29 | 28 |
30 class Liveness { | 29 class Liveness { |
31 Liveness() = delete; | 30 Liveness() = delete; |
32 Liveness(const Liveness &) = delete; | 31 Liveness(const Liveness &) = delete; |
33 Liveness &operator=(const Liveness &) = delete; | 32 Liveness &operator=(const Liveness &) = delete; |
34 | 33 |
35 class LivenessNode { | 34 class LivenessNode { |
36 LivenessNode &operator=(const LivenessNode &) = delete; | 35 LivenessNode &operator=(const LivenessNode &) = delete; |
37 | 36 |
38 public: | 37 public: |
39 LivenessNode() = default; | 38 LivenessNode() = default; |
40 LivenessNode(const LivenessNode &) = default; | 39 LivenessNode(const LivenessNode &) = default; |
41 /// NumLocals is the number of Variables local to this block. | 40 /// NumLocals is the number of Variables local to this block. |
42 SizeT NumLocals = 0; | 41 SizeT NumLocals = 0; |
43 /// NumNonDeadPhis tracks the number of Phi instructions that | 42 /// NumNonDeadPhis tracks the number of Phi instructions that |
44 /// Inst::liveness() identified as tentatively live. If | 43 /// Inst::liveness() identified as tentatively live. If NumNonDeadPhis |
45 /// NumNonDeadPhis changes from the last liveness pass, then liveness | 44 /// changes from the last liveness pass, then liveness has not yet |
46 /// has not yet converged. | 45 /// converged. |
47 SizeT NumNonDeadPhis = 0; | 46 SizeT NumNonDeadPhis = 0; |
48 // LiveToVarMap maps a liveness bitvector index to a Variable. This | 47 // LiveToVarMap maps a liveness bitvector index to a Variable. This is |
49 // is generally just for printing/dumping. The index should be less | 48 // generally just for printing/dumping. The index should be less than |
50 // than NumLocals + Liveness::NumGlobals. | 49 // NumLocals + Liveness::NumGlobals. |
51 std::vector<Variable *> LiveToVarMap; | 50 std::vector<Variable *> LiveToVarMap; |
52 // LiveIn and LiveOut track the in- and out-liveness of the global | 51 // LiveIn and LiveOut track the in- and out-liveness of the global |
53 // variables. The size of each vector is | 52 // variables. The size of each vector is LivenessNode::NumGlobals. |
54 // LivenessNode::NumGlobals. | |
55 LivenessBV LiveIn, LiveOut; | 53 LivenessBV LiveIn, LiveOut; |
56 // LiveBegin and LiveEnd track the instruction numbers of the start | 54 // LiveBegin and LiveEnd track the instruction numbers of the start and end |
57 // and end of each variable's live range within this block. The | 55 // of each variable's live range within this block. The index/key of each |
58 // index/key of each element is less than NumLocals + | 56 // element is less than NumLocals + Liveness::NumGlobals. |
59 // Liveness::NumGlobals. | |
60 LiveBeginEndMap LiveBegin, LiveEnd; | 57 LiveBeginEndMap LiveBegin, LiveEnd; |
61 }; | 58 }; |
62 | 59 |
63 public: | 60 public: |
64 Liveness(Cfg *Func, LivenessMode Mode) : Func(Func), Mode(Mode) {} | 61 Liveness(Cfg *Func, LivenessMode Mode) : Func(Func), Mode(Mode) {} |
65 void init(); | 62 void init(); |
66 void initPhiEdgeSplits(NodeList::const_iterator FirstNode, | 63 void initPhiEdgeSplits(NodeList::const_iterator FirstNode, |
67 VarList::const_iterator FirstVar); | 64 VarList::const_iterator FirstVar); |
68 Cfg *getFunc() const { return Func; } | 65 Cfg *getFunc() const { return Func; } |
69 LivenessMode getMode() const { return Mode; } | 66 LivenessMode getMode() const { return Mode; } |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
104 /// Resize Nodes so that Nodes[Index] is valid. | 101 /// Resize Nodes so that Nodes[Index] is valid. |
105 void resize(SizeT Index) { | 102 void resize(SizeT Index) { |
106 if (Index >= Nodes.size()) | 103 if (Index >= Nodes.size()) |
107 Nodes.resize(Index + 1); | 104 Nodes.resize(Index + 1); |
108 } | 105 } |
109 Cfg *Func; | 106 Cfg *Func; |
110 LivenessMode Mode; | 107 LivenessMode Mode; |
111 SizeT NumGlobals = 0; | 108 SizeT NumGlobals = 0; |
112 /// Size of Nodes is Cfg::Nodes.size(). | 109 /// Size of Nodes is Cfg::Nodes.size(). |
113 std::vector<LivenessNode> Nodes; | 110 std::vector<LivenessNode> Nodes; |
114 /// VarToLiveMap maps a Variable's Variable::Number to its live index | 111 /// VarToLiveMap maps a Variable's Variable::Number to its live index within |
115 /// within its basic block. | 112 /// its basic block. |
116 std::vector<SizeT> VarToLiveMap; | 113 std::vector<SizeT> VarToLiveMap; |
117 /// LiveToVarMap is analogous to LivenessNode::LiveToVarMap, but for | 114 /// LiveToVarMap is analogous to LivenessNode::LiveToVarMap, but for non-local |
118 /// non-local variables. | 115 /// variables. |
119 std::vector<Variable *> LiveToVarMap; | 116 std::vector<Variable *> LiveToVarMap; |
120 /// RangeMask[Variable::Number] indicates whether we want to track that | 117 /// RangeMask[Variable::Number] indicates whether we want to track that |
121 /// Variable's live range. | 118 /// Variable's live range. |
122 llvm::BitVector RangeMask; | 119 llvm::BitVector RangeMask; |
123 }; | 120 }; |
124 | 121 |
125 } // end of namespace Ice | 122 } // end of namespace Ice |
126 | 123 |
127 #endif // SUBZERO_SRC_ICELIVENESS_H | 124 #endif // SUBZERO_SRC_ICELIVENESS_H |
OLD | NEW |