| //===- subzero/src/IceLiveness.h - Liveness analysis ------------*- C++ -*-===// |
| // |
| // The Subzero Code Generator |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| /// |
| /// \file |
| /// \brief Declares the Liveness and LivenessNode classes, which are used for |
| /// liveness analysis. |
| /// |
| /// The node-specific information tracked for each Variable includes whether it |
| /// is live on entry, whether it is live on exit, the instruction number that |
| /// starts its live range, and the instruction number that ends its live range. |
| /// At the Cfg level, the actual live intervals are recorded. |
| /// |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef SUBZERO_SRC_ICELIVENESS_H |
| #define SUBZERO_SRC_ICELIVENESS_H |
| |
| #include "IceDefs.h" |
| #include "IceBitVector.h" |
| #include "IceCfgNode.h" |
| #include "IceTLS.h" |
| #include "IceTypes.h" |
| |
| #include <memory> |
| #include <utility> |
| |
| namespace Ice { |
| |
| class Liveness { |
| Liveness() = delete; |
| Liveness(const Liveness &) = delete; |
| Liveness &operator=(const Liveness &) = delete; |
| |
| class LivenessNode { |
| LivenessNode &operator=(const LivenessNode &) = delete; |
| |
| public: |
| LivenessNode() = default; |
| LivenessNode(const LivenessNode &) = default; |
| /// NumLocals is the number of Variables local to this block. |
| SizeT NumLocals = 0; |
| /// NumNonDeadPhis tracks the number of Phi instructions that |
| /// Inst::liveness() identified as tentatively live. If NumNonDeadPhis |
| /// changes from the last liveness pass, then liveness has not yet |
| /// converged. |
| SizeT NumNonDeadPhis = 0; |
| // LiveToVarMap maps a liveness bitvector index to a Variable. This is |
| // generally just for printing/dumping. The index should be less than |
| // NumLocals + Liveness::NumGlobals. |
| LivenessVector<Variable *> LiveToVarMap; |
| // LiveIn and LiveOut track the in- and out-liveness of the global |
| // variables. The size of each vector is LivenessNode::NumGlobals. |
| LivenessBV LiveIn, LiveOut; |
| // LiveBegin and LiveEnd track the instruction numbers of the start and end |
| // of each variable's live range within this block. The index/key of each |
| // element is less than NumLocals + Liveness::NumGlobals. |
| LiveBeginEndMap LiveBegin, LiveEnd; |
| }; |
| |
| public: |
| void init(); |
| void initPhiEdgeSplits(NodeList::const_iterator FirstNode, |
| VarList::const_iterator FirstVar); |
| Cfg *getFunc() const { return Func; } |
| LivenessMode getMode() const { return Mode; } |
| Variable *getVariable(SizeT LiveIndex, const CfgNode *Node) const; |
| SizeT getLiveIndex(SizeT VarIndex) const { |
| const SizeT LiveIndex = VarToLiveMap[VarIndex]; |
| assert(LiveIndex != InvalidLiveIndex); |
| return LiveIndex; |
| } |
| SizeT getNumGlobalVars() const { return NumGlobals; } |
| SizeT getNumVarsInNode(const CfgNode *Node) const { |
| return NumGlobals + Nodes[Node->getIndex()].NumLocals; |
| } |
| SizeT &getNumNonDeadPhis(const CfgNode *Node) { |
| return Nodes[Node->getIndex()].NumNonDeadPhis; |
| } |
| LivenessBV &getLiveIn(const CfgNode *Node) { |
| SizeT Index = Node->getIndex(); |
| resize(Index); |
| return Nodes[Index].LiveIn; |
| } |
| LivenessBV &getLiveOut(const CfgNode *Node) { |
| SizeT Index = Node->getIndex(); |
| resize(Index); |
| return Nodes[Index].LiveOut; |
| } |
| LivenessBV &getScratchBV() { return ScratchBV; } |
| LiveBeginEndMap *getLiveBegin(const CfgNode *Node) { |
| SizeT Index = Node->getIndex(); |
| resize(Index); |
| return &Nodes[Index].LiveBegin; |
| } |
| LiveBeginEndMap *getLiveEnd(const CfgNode *Node) { |
| SizeT Index = Node->getIndex(); |
| resize(Index); |
| return &Nodes[Index].LiveEnd; |
| } |
| bool getRangeMask(SizeT Index) const { return RangeMask[Index]; } |
| |
| ArenaAllocator *getAllocator() const { return Alloc.get(); } |
| |
| static std::unique_ptr<Liveness> create(Cfg *Func, LivenessMode Mode) { |
| return std::unique_ptr<Liveness>(new Liveness(Func, Mode)); |
| } |
| |
| static void TlsInit() { LivenessAllocatorTraits::init(); } |
| |
| std::string dumpStr() const { |
| return "MaxLocals(" + std::to_string(MaxLocals) + "), " |
| "NumGlobals(" + |
| std::to_string(NumGlobals) + ")"; |
| } |
| |
| private: |
| Liveness(Cfg *Func, LivenessMode Mode) |
| : Alloc(new ArenaAllocator()), AllocScope(this), Func(Func), Mode(Mode) {} |
| |
| void initInternal(NodeList::const_iterator FirstNode, |
| VarList::const_iterator FirstVar, bool IsFullInit); |
| /// Resize Nodes so that Nodes[Index] is valid. |
| void resize(SizeT Index) { |
| if (Index >= Nodes.size()) { |
| assert(false && "The Nodes array is not expected to be resized."); |
| Nodes.resize(Index + 1); |
| } |
| } |
| std::unique_ptr<ArenaAllocator> Alloc; |
| LivenessAllocatorScope AllocScope; // Must be declared after Alloc. |
| static constexpr SizeT InvalidLiveIndex = -1; |
| Cfg *Func; |
| LivenessMode Mode; |
| /// Size of Nodes is Cfg::Nodes.size(). |
| LivenessVector<LivenessNode> Nodes; |
| /// VarToLiveMap maps a Variable's Variable::Number to its live index within |
| /// its basic block. |
| LivenessVector<SizeT> VarToLiveMap; |
| /// LiveToVarMap is analogous to LivenessNode::LiveToVarMap, but for non-local |
| /// variables. |
| LivenessVector<Variable *> LiveToVarMap; |
| /// RangeMask[Variable::Number] indicates whether we want to track that |
| /// Variable's live range. |
| LivenessBV RangeMask; |
| /// ScratchBV is a bitvector that can be reused across CfgNode passes, to |
| /// avoid having to allocate/deallocate memory so frequently. |
| LivenessBV ScratchBV; |
| /// MaxLocals indicates what is the maximum number of local variables in a |
| /// single basic block, across all blocks in a function. |
| SizeT MaxLocals = 0; |
| /// NumGlobals indicates how many global variables (i.e., Multi Block) exist |
| /// for a function. |
| SizeT NumGlobals = 0; |
| }; |
| |
| } // end of namespace Ice |
| |
| #endif // SUBZERO_SRC_ICELIVENESS_H |