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