Subzero: Initial O2 lowering

Includes the following:
1. Liveness analysis.
2. Linear-scan register allocation.
3. Address mode optimization.
4. Compare-branch fusing.

All of these depend on liveness analysis.  There are three versions of liveness analysis (in order of increasing cost):
1. Lightweight.  This computes last-uses for variables local to a single basic block.
2. Full.  This computes last-uses for all variables based on global dataflow analysis.
3. Full live ranges.  This computes all last-uses, plus calculates the live range intervals in terms of instruction numbers.  (The live ranges are needed for register allocation.)

For testing the full live range computation, Cfg::validateLiveness() checks every Variable of every Inst and verifies that the current Inst is contained within the Variable's live range.

The cross tests are run with O2 in addition to Om1.

Some of the lit tests (for what good they do) are updated with O2 code sequences.

BUG= none
R=jvoung@chromium.org

Review URL: https://codereview.chromium.org/300563003

src/IceInst.h

diff --git a/src/IceInst.h b/src/IceInst.h
index fd0eeea..a465eda 100644
--- a/src/IceInst.h
+++ b/src/IceInst.h
@@ -56,10 +56,14 @@
   };
   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 @@
     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 @@
   // 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 @@
     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 @@
   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 @@
   }
   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 @@
 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: