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 "IceDefs.h" 25 #include "IceBitVector.h" 26 #include "IceCfgNode.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 "NumGlobals(" + 119 std::to_string(NumGlobals) + ")"; 120 } 121 122 private: Liveness(Cfg * Func,LivenessMode Mode)123 Liveness(Cfg *Func, LivenessMode Mode) 124 : Alloc(new ArenaAllocator()), AllocScope(this), Func(Func), Mode(Mode) {} 125 126 void initInternal(NodeList::const_iterator FirstNode, 127 VarList::const_iterator FirstVar, bool IsFullInit); 128 /// Resize Nodes so that Nodes[Index] is valid. resize(SizeT Index)129 void resize(SizeT Index) { 130 if (Index >= Nodes.size()) { 131 assert(false && "The Nodes array is not expected to be resized."); 132 Nodes.resize(Index + 1); 133 } 134 } 135 std::unique_ptr<ArenaAllocator> Alloc; 136 LivenessAllocatorScope AllocScope; // Must be declared after Alloc. 137 static constexpr SizeT InvalidLiveIndex = -1; 138 Cfg *Func; 139 LivenessMode Mode; 140 /// Size of Nodes is Cfg::Nodes.size(). 141 LivenessVector<LivenessNode> Nodes; 142 /// VarToLiveMap maps a Variable's Variable::Number to its live index within 143 /// its basic block. 144 LivenessVector<SizeT> VarToLiveMap; 145 /// LiveToVarMap is analogous to LivenessNode::LiveToVarMap, but for non-local 146 /// variables. 147 LivenessVector<Variable *> LiveToVarMap; 148 /// RangeMask[Variable::Number] indicates whether we want to track that 149 /// Variable's live range. 150 LivenessBV RangeMask; 151 /// ScratchBV is a bitvector that can be reused across CfgNode passes, to 152 /// avoid having to allocate/deallocate memory so frequently. 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; 160 }; 161 162 } // end of namespace Ice 163 164 #endif // SUBZERO_SRC_ICELIVENESS_H 165