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