• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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