Subzero: Improve performance of liveness analysis and live range construction.

src/IceLiveness.h

 //===- 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.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file declares the Liveness and LivenessNode classes,
@@ skipping 19 matching lines @@
   LivenessNode() : NumLocals(0) {}
   // NumLocals is the number of Variables local to this block.
   SizeT NumLocals;
   // 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.
   std::vector<Variable *> LiveToVarMap;
   // LiveIn and LiveOut track the in- and out-liveness of the global
   // variables.  The size of each vector is
   // LivenessNode::NumGlobals.
-  llvm::BitVector LiveIn, LiveOut;
+  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
-  // size of each vector is NumLocals + Liveness::NumGlobals.
-  std::vector<InstNumberT> LiveBegin, LiveEnd;
+  // index/key of each element is less than NumLocals +
+  // Liveness::NumGlobals.
+  BeginEndMap LiveBegin, LiveEnd;
 
 private:
   // TODO: Disable these constructors when Liveness::Nodes is no
   // longer an STL container.
   // LivenessNode(const LivenessNode &) = delete;
   // LivenessNode &operator=(const LivenessNode &) = delete;
 };
 
 class Liveness {
 public:
   Liveness(Cfg *Func, LivenessMode Mode)
       : Func(Func), Mode(Mode), NumGlobals(0) {}
   void init();
+  Cfg *getFunc() const { return Func; }
+  LivenessMode getMode() const { return Mode; }
   Variable *getVariable(SizeT LiveIndex, const CfgNode *Node) const;
   SizeT getLiveIndex(const Variable *Var) const;

[jvoung (off chromium), 2014/10/13 20:50:50]

Can this variant of getLiveIndex() be removed now?

[Jim Stichnoth, 2014/10/13 23:15:22]

Done.

+  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;
   }
-  llvm::BitVector &getLiveIn(const CfgNode *Node) {
+  LivenessBV &getLiveIn(const CfgNode *Node) {
     return Nodes[Node->getIndex()].LiveIn;
   }
-  llvm::BitVector &getLiveOut(const CfgNode *Node) {
+  LivenessBV &getLiveOut(const CfgNode *Node) {
     return Nodes[Node->getIndex()].LiveOut;
   }
-  std::vector<InstNumberT> &getLiveBegin(const CfgNode *Node) {
-    return Nodes[Node->getIndex()].LiveBegin;
+  BeginEndMap *getLiveBegin(const CfgNode *Node) {
+    return &Nodes[Node->getIndex()].LiveBegin;
   }
-  std::vector<InstNumberT> &getLiveEnd(const CfgNode *Node) {
-    return Nodes[Node->getIndex()].LiveEnd;
+  BeginEndMap *getLiveEnd(const CfgNode *Node) {
+    return &Nodes[Node->getIndex()].LiveEnd;
   }
   LiveRange &getLiveRange(Variable *Var);
   void addLiveRange(Variable *Var, InstNumberT Start, InstNumberT End,
                     uint32_t WeightDelta);
 
 private:
   Cfg *Func;
   LivenessMode Mode;
   SizeT NumGlobals;
   // Size of Nodes is Cfg::Nodes.size().
   std::vector<LivenessNode> Nodes;
   // VarToLiveMap maps a Variable's Variable::Number to its live index
   // within its basic block.
   std::vector<SizeT> VarToLiveMap;
   // LiveToVarMap is analogous to LivenessNode::LiveToVarMap, but for
   // non-local variables.
   std::vector<Variable *> LiveToVarMap;
   // LiveRanges maps a Variable::Number to its live range.
   std::vector<LiveRange> LiveRanges;
   Liveness(const Liveness &) = delete;
   Liveness &operator=(const Liveness &) = delete;
 };
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICELIVENESS_H