Subzero: Initial O2 lowering

src/IceCfgNode.cpp

Index: src/IceCfgNode.cpp
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index c00b2c77538a49faf6b7fe37af067b0fccda7094..cfec72ec2e13f22814f769ef66687d10eac7079c 100644
--- a/src/IceCfgNode.cpp
+++ b/src/IceCfgNode.cpp
@@ -15,6 +15,7 @@
 #include "IceCfg.h"
 #include "IceCfgNode.h"
 #include "IceInst.h"
+#include "IceLiveness.h"
 #include "IceOperand.h"
 #include "IceTargetLowering.h"
 
@@ -49,6 +50,22 @@ void CfgNode::appendInst(Inst *Inst) {
   Inst->updateVars(this);
 }
 
+// Renumbers the non-deleted instructions in the node.  This needs to
+// be done in preparation for live range analysis.  The instruction
+// numbers in a block must be monotonically increasing.  The range of
+// instruction numbers in a block, from lowest to highest, must not
+// overlap with the range of any other block.
+void CfgNode::renumberInstructions() {
+  for (PhiList::const_iterator I = Phis.begin(), E = Phis.end(); I != E; ++I) {
+    (*I)->renumber(Func);
+  }
+  InstList::const_iterator I = Insts.begin(), E = Insts.end();
+  while (I != E) {
+    Inst *Inst = *I++;
+    Inst->renumber(Func);
+  }
+}
+
 // When a node is created, the OutEdges are immediately knows, but the
 // InEdges have to be built up incrementally.  After the CFG has been
 // constructed, the computePredecessors() pass finalizes it by
@@ -111,6 +128,15 @@ void CfgNode::placePhiStores() {
   // instruction.  Calling getTerminatorEdges() on a non-terminator
   // instruction will cause an llvm_unreachable().
   assert(((*InsertionPoint)->getTerminatorEdges(), true));
+  if (llvm::isa<InstBr>(*InsertionPoint)) {
+    if (InsertionPoint != Insts.begin()) {
+      --InsertionPoint;
+      if (!llvm::isa<InstIcmp>(*InsertionPoint) &&
+          !llvm::isa<InstFcmp>(*InsertionPoint)) {
+        ++InsertionPoint;
+      }
+    }
+  }

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

Can you explain this?

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

Done.  Also modified the logic to look only for *conditional* branches followed
by cmp instructions.

 
   // Consider every out-edge.
   for (NodeList::const_iterator I1 = OutEdges.begin(), E1 = OutEdges.end();
@@ -145,6 +171,19 @@ void CfgNode::deletePhis() {
   }
 }
 
+// Does address mode optimization.  Pass each instruction to the
+// TargetLowering object.  If it returns a new instruction
+// (representing the optimized address mode), then insert the new
+// instruction and delete the old.
+void CfgNode::doAddressOpt() {
+  TargetLowering *Target = Func->getTarget();
+  LoweringContext &Context = Target->getContext();
+  Context.init(this);
+  while (!Context.atEnd()) {
+    Target->doAddressOpt();
+  }
+}
+
 // Drives the target lowering.  Passes the current instruction and the
 // next non-deleted instruction for target lowering.
 void CfgNode::genCode() {
@@ -162,6 +201,179 @@ void CfgNode::genCode() {
   }
 }
 
+// Performs liveness analysis on the block.  Returns true if the
+// incoming liveness changed from before, false if it stayed the same.
+// (If it changes, the node's predecessors need to be processed
+// again.)
+bool CfgNode::liveness(LivenessMode Mode, Liveness *Liveness) {
+  SizeT NumVars;
+  if (Mode == Liveness_LREndLightweight)
+    NumVars = Func->getNumVariables();
+  else
+    NumVars = Liveness->getLocalSize(this);
+  llvm::BitVector Live(NumVars);
+  if (Mode != Liveness_LREndLightweight) {
+    // Mark the beginning and ending of each variable's live range
+    // with the sentinel instruction number 0.
+    std::vector<int> &LiveBegin = Liveness->getLiveBegin(this);
+    std::vector<int> &LiveEnd = Liveness->getLiveEnd(this);
+    LiveBegin.assign(NumVars, 0);
+    LiveEnd.assign(NumVars, 0);
+    // Initialize Live to be the union of all successors' LiveIn.
+    for (NodeList::const_iterator I = OutEdges.begin(), E = OutEdges.end();
+         I != E; ++I) {
+      CfgNode *Succ = *I;
+      Live |= Liveness->getLiveIn(Succ);
+      // Mark corresponding argument of phis in successor as live.
+      for (PhiList::const_iterator I1 = Succ->Phis.begin(),
+                                   E1 = Succ->Phis.end();
+           I1 != E1; ++I1) {
+        (*I1)->livenessPhiOperand(Live, this, Liveness);
+      }
+    }
+    Liveness->getLiveOut(this) = Live;
+  }
+
+  // Process regular instructions in reverse order.
+  for (InstList::const_reverse_iterator I = Insts.rbegin(), E = Insts.rend();
+       I != E; ++I) {
+    (*I)->liveness(Mode, (*I)->getNumber(), Live, Liveness, this);
+  }
+  // Process phis in forward order so that we can override the
+  // instruction number to be that of the earliest phi instruction in
+  // the block.
+  int32_t FirstPhiNumber = 0; // sentinel value
+  for (PhiList::const_iterator I = Phis.begin(), E = Phis.end(); I != E; ++I) {
+    if (FirstPhiNumber <= 0)
+      FirstPhiNumber = (*I)->getNumber();
+    (*I)->liveness(Mode, FirstPhiNumber, Live, Liveness, this);
+  }
+
+  // When using the sparse representation, after traversing the
+  // instructions in the block, the Live bitvector should only contain
+  // set bits for global variables upon block entry.  We validate this
+  // by shrinking the Live vector and then testing it against the
+  // pre-shrunk version.  (The shrinking is required, but the
+  // validation is not.)
+  if (Mode != Liveness_LREndLightweight) {
+    llvm::BitVector LiveOrig = Live;
+    Live.resize(Liveness->getGlobalSize());
+    // Non-global arguments in the entry node are allowed to be live on
+    // entry.
+    bool IsEntry = (Func->getEntryNode() == this);
+    assert(IsEntry || Live == LiveOrig);
+    // The following block helps debug why the previous assertion
+    // failed.

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

Shouldn't the block be before the assertion?

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

Good point.  Fixed this, including replacing the assert() with an
llvm_unreachable() at the end of the block.

+    if (!(IsEntry || Live == LiveOrig)) {
+      Ostream &Str = Func->getContext()->getStrDump();
+      Func->setCurrentNode(NULL);
+      Str << "LiveOrig-Live =";
+      for (SizeT i = Live.size(); i < LiveOrig.size(); ++i) {
+        if (LiveOrig.test(i)) {
+          Str << " ";
+          Liveness->getVariable(i, this)->dump(Func);
+        }
+      }
+      Str << "\n";
+    }
+  }
+
+  bool Changed = false;
+  if (Mode != Liveness_LREndLightweight) {
+    llvm::BitVector &LiveIn = Liveness->getLiveIn(this);
+    // Add in current LiveIn
+    Live |= LiveIn;
+    // Check result, set LiveIn=Live
+    Changed = (Live != LiveIn);
+    if (Changed)
+      LiveIn = Live;
+  }
+  return Changed;
+}
+
+// Now that basic liveness is complete, remove dead instructions that
+// were tentatively marked as dead, and compute actual live ranges.
+// It is assumed that within a single basic block, a live range begins
+// at most once and ends at most once.  This is certainly true for
+// pure SSA form.  It is also true once phis are lowered, since each
+// assignment to the phi-based temporary is in a different basic
+// block, and there is a single read that ends the live in the basic
+// block that contained the actual phi instruction.
+void CfgNode::livenessPostprocess(LivenessMode Mode, Liveness *Liveness) {
+  int32_t FirstInstNum = 0;
+  int32_t LastInstNum = 0;
+  // Process phis in any order.  Process only Dest operands.
+  for (PhiList::const_iterator I = Phis.begin(), E = Phis.end(); I != E; ++I) {
+    InstPhi *Inst = *I;
+    Inst->deleteIfDead();
+    if (Inst->isDeleted())
+      continue;
+    if (FirstInstNum <= 0)
+      FirstInstNum = Inst->getNumber();
+    assert(Inst->getNumber() > LastInstNum);
+    LastInstNum = Inst->getNumber();
+  }
+  // Process instructions
+  for (InstList::const_iterator I = Insts.begin(), E = Insts.end(); I != E;
+       ++I) {
+    Inst *Inst = *I;
+    Inst->deleteIfDead();
+    if (Inst->isDeleted())
+      continue;
+    if (FirstInstNum <= 0)
+      FirstInstNum = Inst->getNumber();
+    assert(Inst->getNumber() > LastInstNum);
+    LastInstNum = Inst->getNumber();
+    // Create fake live ranges for a Kill instruction, but only if the
+    // linked instruction is still alive.
+    if (Mode == Liveness_RangesFull) {
+      if (InstFakeKill *Kill = llvm::dyn_cast<InstFakeKill>(Inst)) {
+        if (!Kill->getLinked()->isDeleted()) {
+          SizeT NumSrcs = Inst->getSrcSize();
+          for (SizeT i = 0; i < NumSrcs; ++i) {
+            Variable *Var = llvm::cast<Variable>(Inst->getSrc(i));
+            int32_t InstNumber = Inst->getNumber();
+            Liveness->addLiveRange(Var, InstNumber, InstNumber, 1);
+          }
+        }
+      }
+    }
+  }
+  if (Mode != Liveness_RangesFull)
+    return;
+
+  SizeT NumVars = Liveness->getLocalSize(this);
+  SizeT NumGlobals = Liveness->getGlobalSize();
+  llvm::BitVector &LiveIn = Liveness->getLiveIn(this);
+  llvm::BitVector &LiveOut = Liveness->getLiveOut(this);
+  std::vector<int> &LiveBegin = Liveness->getLiveBegin(this);
+  std::vector<int> &LiveEnd = Liveness->getLiveEnd(this);
+  for (SizeT i = 0; i < NumVars; ++i) {
+    // Deal with the case where the variable is both live-in and
+    // live-out, but LiveEnd comes before LiveBegin.  In this case, we
+    // need to add two segments to the live range because there is a
+    // hole in the middle.  This would typically happen as a result of
+    // phi lowering in the presence of loopback edges.
+    bool IsGlobal = (i < NumGlobals);
+    if (IsGlobal && LiveIn[i] && LiveOut[i] && LiveBegin[i] > LiveEnd[i]) {
+      Variable *Var = Liveness->getVariable(i, this);
+      Liveness->addLiveRange(Var, FirstInstNum, LiveEnd[i], 1);
+      Liveness->addLiveRange(Var, LiveBegin[i], LastInstNum + 1, 1);
+      continue;
+    }
+    int32_t Begin = (IsGlobal && LiveIn[i]) ? FirstInstNum : LiveBegin[i];
+    int32_t End = (IsGlobal && LiveOut[i]) ? LastInstNum + 1 : LiveEnd[i];
+    if (Begin <= 0 && End <= 0)
+      continue;
+    if (Begin <= FirstInstNum)
+      Begin = FirstInstNum;
+    if (End <= 0)
+      End = LastInstNum + 1;
+    Variable *Var = Liveness->getVariable(i, this);
+    Liveness->addLiveRange(Var, Begin, End, 1);
+  }
+}
+
 // ======================== Dump routines ======================== //
 
 void CfgNode::emit(Cfg *Func) const {
@@ -194,6 +406,7 @@ void CfgNode::emit(Cfg *Func) const {
 void CfgNode::dump(Cfg *Func) const {
   Func->setCurrentNode(this);
   Ostream &Str = Func->getContext()->getStrDump();
+  Liveness *Liveness = Func->getLiveness();
   if (Func->getContext()->isVerbose(IceV_Instructions)) {
     Str << getName() << ":\n";
   }
@@ -208,6 +421,19 @@ void CfgNode::dump(Cfg *Func) const {
     }
     Str << "\n";
   }
+  // Dump the live-in variables.
+  llvm::BitVector LiveIn;
+  if (Liveness)
+    LiveIn = Liveness->getLiveIn(this);
+  if (Func->getContext()->isVerbose(IceV_Liveness) && !LiveIn.empty()) {
+    Str << "    // LiveIn:";
+    for (SizeT i = 0; i < LiveIn.size(); ++i) {
+      if (LiveIn[i]) {
+        Str << " %" << Liveness->getVariable(i, this)->getName();
+      }
+    }
+    Str << "\n";
+  }
   // Dump each instruction.
   if (Func->getContext()->isVerbose(IceV_Instructions)) {
     for (PhiList::const_iterator I = Phis.begin(), E = Phis.end(); I != E;
@@ -221,6 +447,19 @@ void CfgNode::dump(Cfg *Func) const {
       Inst->dumpDecorated(Func);
     }
   }
+  // Dump the live-out variables.
+  llvm::BitVector LiveOut;
+  if (Liveness)
+    LiveOut = Liveness->getLiveOut(this);
+  if (Func->getContext()->isVerbose(IceV_Liveness) && !LiveOut.empty()) {
+    Str << "    // LiveOut:";
+    for (SizeT i = 0; i < LiveOut.size(); ++i) {
+      if (LiveOut[i]) {
+        Str << " %" << Liveness->getVariable(i, this)->getName();
+      }
+    }
+    Str << "\n";
+  }
   // Dump list of successor nodes.
   if (Func->getContext()->isVerbose(IceV_Succs)) {
     Str << "    // succs = ";