Subzero: Initial O2 lowering

src/IceInst.h

Index: src/IceInst.h
diff --git a/src/IceInst.h b/src/IceInst.h
index fd0eeea9d76b6908bf8791c9f019ab25424b81ce..a465edae4773d95e138947ebc1e9f83586c6deec 100644
--- a/src/IceInst.h
+++ b/src/IceInst.h
@@ -56,10 +56,14 @@ public:
   };
   InstKind getKind() const { return Kind; }
 
-  int32_t getNumber() const { return Number; }
+  InstNumberT getNumber() const { return Number; }
+  void renumber(Cfg *Func);
+  static const InstNumberT NumberDeleted = -1;
+  static const InstNumberT NumberSentinel = 0;
 
   bool isDeleted() const { return Deleted; }
   void setDeleted() { Deleted = true; }
+  void deleteIfDead();
 
   bool hasSideEffects() const { return HasSideEffects; }
 
@@ -71,6 +75,8 @@ public:
     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 {
@@ -88,8 +94,12 @@ public:
   // basic blocks, i.e. used in a different block from their definition.
   void updateVars(CfgNode *Node);
 
+  void livenessLightweight(llvm::BitVector &Live);
+  void liveness(InstNumberT InstNumber, llvm::BitVector &Live,
+                Liveness *Liveness, const CfgNode *Node);
   virtual void emit(const Cfg *Func) const;
   virtual void dump(const Cfg *Func) const;
+  virtual void dumpExtras(const Cfg *Func) const;
   void dumpDecorated(const Cfg *Func) const;
   void emitSources(const Cfg *Func) const;
   void dumpSources(const Cfg *Func) const;
@@ -105,15 +115,22 @@ protected:
     assert(NumSrcs < MaxSrcs);
     Srcs[NumSrcs++] = Src;
   }
+  void setLastUse(SizeT VarIndex) {
+    if (VarIndex < CHAR_BIT * sizeof(LiveRangesEnded))
+      LiveRangesEnded |= (((LREndedBits)1u) << VarIndex);
+  }
+  void resetLastUses() { LiveRangesEnded = 0; }
   // The destroy() method lets the instruction cleanly release any
   // memory that was allocated via the Cfg's allocator.
   virtual void destroy(Cfg *Func) { Func->deallocateArrayOf<Operand *>(Srcs); }
 
   const InstKind Kind;
   // Number is the instruction number for describing live ranges.
-  int32_t Number;
+  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.
@@ -124,6 +141,18 @@ protected:
   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
+  // could contain more than 1 Variable).  All the variables in an
+  // instruction are conceptually flattened and each variable is
+  // mapped to one bit position of the LiveRangesEnded bit vector.
+  // Only the first CHAR_BIT * sizeof(LREndedBits) variables are
+  // tracked this way.
+  typedef uint32_t LREndedBits; // only first 32 src operands tracked, sorry
+  LREndedBits LiveRangesEnded;
+
 private:
   Inst(const Inst &) LLVM_DELETED_FUNCTION;
   Inst &operator=(const Inst &) LLVM_DELETED_FUNCTION;
@@ -393,6 +422,8 @@ public:
   }
   void addArgument(Operand *Source, CfgNode *Label);
   Operand *getOperandForTarget(CfgNode *Target) const;
+  void livenessPhiOperand(llvm::BitVector &Live, CfgNode *Target,
+                          Liveness *Liveness);
   Inst *lower(Cfg *Func, CfgNode *Node);
   virtual void dump(const Cfg *Func) const;
   static bool classof(const Inst *Inst) { return Inst->getKind() == Phi; }
@@ -626,6 +657,7 @@ class InstTarget : public Inst {
 public:
   virtual void emit(const Cfg *Func) const = 0;
   virtual void dump(const Cfg *Func) const;
+  virtual void dumpExtras(const Cfg *Func) const;
   static bool classof(const Inst *Inst) { return Inst->getKind() >= Target; }
 
 protected: