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

src/IceInst.h

 //===- subzero/src/IceInst.h - High-level instructions ----------*- 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 Inst class and its target-independent
@@ skipping 48 matching lines @@
     FakeDef,  // not part of LLVM/PNaCl bitcode
     FakeUse,  // not part of LLVM/PNaCl bitcode
     FakeKill, // not part of LLVM/PNaCl bitcode
     Target    // target-specific low-level ICE
               // Anything >= Target is an InstTarget subclass.
   };
   InstKind getKind() const { return Kind; }
 
   InstNumberT getNumber() const { return Number; }
   void renumber(Cfg *Func);
-  static const InstNumberT NumberDeleted = -1;
-  static const InstNumberT NumberSentinel = 0;
+  enum {
+    NumberDeleted = -1,
+    NumberSentinel = 0
+  };
 
   bool isDeleted() const { return Deleted; }
   void setDeleted() { Deleted = true; }
   void deleteIfDead();
 
   bool hasSideEffects() const { return HasSideEffects; }
 
+  bool isDestNonKillable() const { return IsDestNonKillable; }
+  void setDestNonKillable() { IsDestNonKillable = true; }
+
   Variable *getDest() const { return Dest; }
 
   SizeT getSrcSize() const { return NumSrcs; }
   Operand *getSrc(SizeT I) const {
     assert(I < getSrcSize());
     return Srcs[I];
   }
 
   bool isLastUse(const Operand *Src) const;
 
   // Returns a list of out-edges corresponding to a terminator
   // instruction, which is the last instruction of the block.
   virtual NodeList getTerminatorEdges() const {
     // All valid terminator instructions override this method.  For
     // the default implementation, we assert in case some CfgNode
     // is constructed without a terminator instruction at the end.
     llvm_unreachable(
         "getTerminatorEdges() called on a non-terminator instruction");
     return NodeList();
   }
 
   virtual bool isSimpleAssign() const { return false; }
 
-  void livenessLightweight(Cfg *Func, llvm::BitVector &Live);
-  void liveness(InstNumberT InstNumber, llvm::BitVector &Live,
-                Liveness *Liveness, const CfgNode *Node);
+  void livenessLightweight(Cfg *Func, LivenessBV &Live);
+  void liveness(InstNumberT InstNumber, LivenessBV &Live, Liveness *Liveness,
+                BeginEndMap *LiveBegin, BeginEndMap *LiveEnd);
 
   // Get the number of native instructions that this instruction
   // ultimately emits.  By default, high-level instructions don't
   // result in any native instructions, and a target-specific
   // instruction results in a single native instruction.
   virtual uint32_t getEmitInstCount() const { return 0; }
   virtual void emit(const Cfg *Func) const = 0;
   virtual void emitIAS(const Cfg *Func) const = 0;
   virtual void dump(const Cfg *Func) const;
   virtual void dumpExtras(const Cfg *Func) const;
@@ skipping 25 matching lines @@
   // Number is the instruction number for describing live ranges.
   InstNumberT Number;
   // Deleted means irrevocably deleted.
   bool Deleted;
   // Dead means pending deletion after liveness analysis converges.
   bool Dead;
   // HasSideEffects means the instruction is something like a function
   // call or a volatile load that can't be removed even if its Dest
   // variable is not live.
   bool HasSideEffects;
+  // IsDestNonKillable means that liveness analysis shouldn't consider
+  // this instruction to kill the Dest variable.  This is used when
+  // lowering produces two assignments to the same variable.
+  bool IsDestNonKillable;
 
   Variable *Dest;
   const SizeT MaxSrcs; // only used for assert
   SizeT NumSrcs;
   Operand **Srcs;
 
   // LiveRangesEnded marks which Variables' live ranges end in this
   // instruction.  An instruction can have an arbitrary number of
   // source operands (e.g. a call instruction), and each source
   // operand can contain 0 or 1 Variable (and target-specific operands
@@ skipping 368 matching lines @@
 
 // Phi instruction.  For incoming edge I, the node is Labels[I] and
 // the Phi source operand is getSrc(I).
 class InstPhi : public InstHighLevel {
 public:
   static InstPhi *create(Cfg *Func, SizeT MaxSrcs, Variable *Dest) {
     return new (Func->allocateInst<InstPhi>()) InstPhi(Func, MaxSrcs, Dest);
   }
   void addArgument(Operand *Source, CfgNode *Label);
   Operand *getOperandForTarget(CfgNode *Target) const;
-  void livenessPhiOperand(llvm::BitVector &Live, CfgNode *Target,
+  void livenessPhiOperand(LivenessBV &Live, CfgNode *Target,
                           Liveness *Liveness);
   Inst *lower(Cfg *Func);
   void dump(const Cfg *Func) const override;
   static bool classof(const Inst *Inst) { return Inst->getKind() == Phi; }
 
 private:
   InstPhi(Cfg *Func, SizeT MaxSrcs, Variable *Dest);
   InstPhi(const InstPhi &) = delete;
   InstPhi &operator=(const InstPhi &) = delete;
   void destroy(Cfg *Func) override {
@@ skipping 237 matching lines @@
       : Inst(Func, Kind, MaxSrcs, Dest) {
     assert(Kind >= Target);
   }
   void emitIAS(const Cfg *Func) const override { emit(Func); }
   ~InstTarget() override {}
 };
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEINST_H