Subzero: Initial O2 lowering

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 39 matching lines @@
     Switch,
     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; }
 
   int32_t getNumber() const { return Number; }
+  void renumber(Cfg *Func);
 
   bool isDeleted() const { return Deleted; }
   void setDeleted() { Deleted = true; }
+  void deleteIfDead();
 
   bool hasSideEffects() const { return HasSideEffects; }
 
   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();
   }
 
   // Updates the status of the Variables contained within the
   // instruction.  In particular, it marks where the Dest variable is
   // first assigned, and it tracks whether variables are live across
   // basic blocks, i.e. used in a different block from their definition.
   void updateVars(CfgNode *Node);
 
+  void liveness(LivenessMode Mode, int32_t 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;
   void dumpDest(const Cfg *Func) const;
   virtual bool isRedundantAssign() const { return false; }
 
   virtual ~Inst() {}
 
 protected:
   Inst(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest);
   void addSource(Operand *Src) {
     assert(Src);
     assert(NumSrcs < MaxSrcs);
     Srcs[NumSrcs++] = Src;
   }
+  void setLastUse(SizeT VarIndex) {
+    if (VarIndex < 8 * sizeof(LiveRangesEnded))

[JF, 2014/05/25 22:50:50]

s/8/CHAR_BIT/

[Jim Stichnoth, 2014/05/29 01:39:46]

Done.

+      LiveRangesEnded |= (1u << VarIndex);

[JF, 2014/05/25 22:50:50]

Use a typedef for LiveRangesEnded, and cast 1u to that type.

[Jim Stichnoth, 2014/05/29 01:39:46]

Done.

+  }
+  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;
   // 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;
 
   Variable *Dest;
   const SizeT MaxSrcs; // only used for assert
   SizeT NumSrcs;
   Operand **Srcs;
 
+  uint32_t LiveRangesEnded; // only first 32 src operands tracked, sorry
+
 private:
   Inst(const Inst &) LLVM_DELETED_FUNCTION;
   Inst &operator=(const Inst &) LLVM_DELETED_FUNCTION;
 };
 
 // Alloca instruction.  This captures the size in bytes as getSrc(0),
 // and the required alignment in bytes.  The alignment must be either
 // 0 (no alignment required) or a power of 2.
 class InstAlloca : public Inst {
 public:
@@ skipping 249 matching lines @@
 
 // Phi instruction.  For incoming edge I, the node is Labels[I] and
 // the Phi source operand is getSrc(I).
 class InstPhi : public Inst {
 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,
+                          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; }
 
 private:
   InstPhi(Cfg *Func, SizeT MaxSrcs, Variable *Dest);
   InstPhi(const InstPhi &) LLVM_DELETED_FUNCTION;
   InstPhi &operator=(const InstPhi &) LLVM_DELETED_FUNCTION;
   virtual void destroy(Cfg *Func) {
     Func->deallocateArrayOf<CfgNode *>(Labels);
@@ skipping 213 matching lines @@
   // This instruction is ignored if Linked->isDeleted() is true.
   const Inst *Linked;
 };
 
 // The Target instruction is the base class for all target-specific
 // instructions.
 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:
   InstTarget(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest)
       : Inst(Func, Kind, MaxSrcs, Dest) {
     assert(Kind >= Target);
   }
   InstTarget(const InstTarget &) LLVM_DELETED_FUNCTION;
   InstTarget &operator=(const InstTarget &) LLVM_DELETED_FUNCTION;
   virtual ~InstTarget() {}
 };
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICEINST_H