| //===- 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 |
| /// This file 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 "IceCfgNode.h" |
| #include "IceDefs.h" |
| #include "IceTypes.h" |
| |
| 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. |
| CfgVector<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: |
| Liveness(Cfg *Func, LivenessMode Mode) : Func(Func), Mode(Mode) {} |
| 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 { return VarToLiveMap[VarIndex]; } |
| 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; |
| } |
| 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]; } |
| |
| private: |
| 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()) |
| Nodes.resize(Index + 1); |
| } |
| Cfg *Func; |
| LivenessMode Mode; |
| SizeT NumGlobals = 0; |
| /// Size of Nodes is Cfg::Nodes.size(). |
| CfgVector<LivenessNode> Nodes; |
| /// VarToLiveMap maps a Variable's Variable::Number to its live index within |
| /// its basic block. |
| CfgVector<SizeT> VarToLiveMap; |
| /// LiveToVarMap is analogous to LivenessNode::LiveToVarMap, but for non-local |
| /// variables. |
| CfgVector<Variable *> LiveToVarMap; |
| /// RangeMask[Variable::Number] indicates whether we want to track that |
| /// Variable's live range. |
| llvm::BitVector RangeMask; |
| }; |
| |
| } // end of namespace Ice |
| |
| #endif // SUBZERO_SRC_ICELIVENESS_H |