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

The key performance problem was that the per-block LiveBegin and LiveEnd vectors were dense with respect to the multi-block "global" variables, even though very few of the global variables are ever live within the block.  This led to large vectors needlessly initialized and iterated over.

The new approach is to accumulate two small vectors of <variable,instruction_number> tuples (LiveBegin and LiveEnd) as each block is processed, then sort the vectors and iterate over them in parallel to construct the live ranges.

Some of the anomalies in the original liveness analysis code have been straightened out:

1. Variables have an IgnoreLiveness attribute to suppress analysis.  This is currently used only on the esp register.

2. Instructions have a DestNonKillable attribute which causes the Dest variable not to be marked as starting a new live range at that instruction.  This is used when a variable is non-SSA and has more than one assignment within a block, but we want to treat it as a single live range.  This lets the variable have zero or one live range begins or ends within a block.  DestNonKillable is derived automatically for two-address instructions, and annotated manually in a few other cases.

This is tested by comparing the O2 asm output in each Spec2K component.  In theory, the output should be the same except for some differences in pseudo-instructions output as comments.  However, some actual differences showed up, related to the i64 shl instruction followed by trunc to i32.  This turned out to be a liveness bug that was accidentally fixed.

BUG= none
R=jvoung@chromium.org

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

src/IceLiveness.h

diff --git a/src/IceLiveness.h b/src/IceLiveness.h
index 031f4e9..2949d56 100644
--- a/src/IceLiveness.h
+++ b/src/IceLiveness.h
@@ -37,11 +37,12 @@
   // 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.
+  LiveBeginEndMap LiveBegin, LiveEnd;
 
 private:
   // TODO: Disable these constructors when Liveness::Nodes is no
@@ -55,23 +56,25 @@
   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;
+  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;
+  LiveBeginEndMap *getLiveBegin(const CfgNode *Node) {
+    return &Nodes[Node->getIndex()].LiveBegin;
   }
-  std::vector<InstNumberT> &getLiveEnd(const CfgNode *Node) {
-    return Nodes[Node->getIndex()].LiveEnd;
+  LiveBeginEndMap *getLiveEnd(const CfgNode *Node) {
+    return &Nodes[Node->getIndex()].LiveEnd;
   }
   LiveRange &getLiveRange(Variable *Var);
   void addLiveRange(Variable *Var, InstNumberT Start, InstNumberT End,