Subzero: Allow delaying Phi lowering until after register allocation.

src/IceTargetLoweringX8632.cpp

Index: src/IceTargetLoweringX8632.cpp
diff --git a/src/IceTargetLoweringX8632.cpp b/src/IceTargetLoweringX8632.cpp
index 8082c5223d41e58e14f8ed9caecb9d51602511a1..96cff36cc111b0e69b1ad28aa1323649fb3cd6d8 100644
--- a/src/IceTargetLoweringX8632.cpp
+++ b/src/IceTargetLoweringX8632.cpp
@@ -25,6 +25,7 @@
 #include "IceDefs.h"
 #include "IceGlobalInits.h"
 #include "IceInstX8632.h"
+#include "IceLiveness.h"
 #include "IceOperand.h"
 #include "IceRegistersX8632.h"
 #include "IceTargetLoweringX8632.def"
@@ -276,8 +277,7 @@ ICETYPE_TABLE;
 TargetX8632::TargetX8632(Cfg *Func)
     : TargetLowering(Func), InstructionSet(CLInstructionSet),
       IsEbpBasedFrame(false), NeedsStackAlignment(false), FrameSizeLocals(0),
-      SpillAreaSizeBytes(0), NextLabelNumber(0), ComputedLiveRanges(false),
-      PhysicalRegisters(VarList(RegX8632::Reg_NUM)) {
+      SpillAreaSizeBytes(0), NextLabelNumber(0), ComputedLiveRanges(false) {
   // TODO: Don't initialize IntegerRegisters and friends every time.
   // Instead, initialize in some sort of static initializer for the
   // class.
@@ -316,17 +316,19 @@ TargetX8632::TargetX8632(Cfg *Func)
 void TargetX8632::translateO2() {
   TimerMarker T(TimerStack::TT_O2, Func);
 
-  // Lower Phi instructions.
-  Func->placePhiLoads();
-  if (Func->hasError())
-    return;
-  Func->placePhiStores();
-  if (Func->hasError())
-    return;
-  Func->deletePhis();
-  if (Func->hasError())
-    return;
-  Func->dump("After Phi lowering");
+  if (!Ctx->getFlags().PhiEdgeSplit) {
+    // Lower Phi instructions.
+    Func->placePhiLoads();
+    if (Func->hasError())
+      return;
+    Func->placePhiStores();
+    if (Func->hasError())
+      return;
+    Func->deletePhis();
+    if (Func->hasError())
+      return;
+    Func->dump("After Phi lowering");
+  }
 
   // Address mode optimization.
   Func->getVMetadata()->init(VMK_SingleDefs);
@@ -356,6 +358,7 @@ void TargetX8632::translateO2() {
   Func->genCode();
   if (Func->hasError())
     return;
+  Func->dump("After x86 codegen");
 
   // Register allocation.  This requires instruction renumbering and
   // full liveness analysis.
@@ -378,6 +381,11 @@ void TargetX8632::translateO2() {
     return;
   Func->dump("After linear scan regalloc");
 
+  if (Ctx->getFlags().PhiEdgeSplit) {
+    Func->advancedPhiLowering();
+    Func->dump("After advanced Phi lowering");
+  }
+
   // Stack frame mapping.
   Func->genFrame();
   if (Func->hasError())
@@ -385,6 +393,8 @@ void TargetX8632::translateO2() {
   Func->dump("After stack frame mapping");
 
   Func->deleteRedundantAssignments();
+  Func->contractEmptyNodes();
+  Func->reorderNodes();
 
   // Branch optimization.  This needs to be done just before code
   // emission.  In particular, no transformations that insert or
@@ -451,12 +461,14 @@ IceString TargetX8632::RegNames[] = {
 Variable *TargetX8632::getPhysicalRegister(SizeT RegNum, Type Ty) {
   if (Ty == IceType_void)
     Ty = IceType_i32;
-  assert(RegNum < PhysicalRegisters.size());
-  Variable *Reg = PhysicalRegisters[RegNum];
+  if (PhysicalRegisters[Ty].empty())
+    PhysicalRegisters[Ty].resize(RegX8632::Reg_NUM);
+  assert(RegNum < PhysicalRegisters[Ty].size());
+  Variable *Reg = PhysicalRegisters[Ty][RegNum];
   if (Reg == NULL) {
     Reg = Func->makeVariable(Ty);
     Reg->setRegNum(RegNum);
-    PhysicalRegisters[RegNum] = Reg;
+    PhysicalRegisters[Ty][RegNum] = Reg;
     // Specially mark esp as an "argument" so that it is considered
     // live upon function entry.
     if (RegNum == RegX8632::Reg_esp) {
@@ -711,7 +723,7 @@ void TargetX8632::addProlog(CfgNode *Node) {
     if (Var->getIsArg())
       continue;
     // An unreferenced variable doesn't need a stack slot.
-    if (ComputedLiveRanges && Var->getLiveRange().isEmpty())
+    if (ComputedLiveRanges && !Var->needsStackSlot())

[jvoung (off chromium), 2014/10/27 22:12:21]

Just for reference, I remember you mentioned there was bug related to the
original getLiveRange().isEmpty() check, but I don't know if there was a simple
reproducer =)

[Jim Stichnoth, 2014/10/28 01:20:14]

I think the problem was that the temporary generated for breaking dependence
cycles didn't have a live range associated with it, and at the same time
ComputedLiveRanges was true, so the temporary wasn't getting a stack slot
assigned but was ultimately using a stack offset of 0.  So maybe a reproducer
would be to not set NeedsStackSlot for the temporary...

[jvoung (off chromium), 2014/10/29 13:46:50]

Okay, nevermind =)

       continue;
     // A spill slot linked to a variable with a stack slot should reuse
     // that stack slot.
@@ -1696,7 +1708,8 @@ void TargetX8632::lowerAssign(const InstAssign *Inst) {
     _mov(DestHi, T_Hi);
   } else {
     // RI is either a physical register or an immediate.

[jvoung (off chromium), 2014/10/27 22:12:21]

Seems like the comment on "RI is either..." is no longer true if Dest->hasReg()?

[Jim Stichnoth, 2014/10/28 01:20:14]

Oops, comment changed.

-    Operand *RI = legalize(Src0, Legal_Reg | Legal_Imm);
+    Operand *RI =
+        legalize(Src0, Dest->hasReg() ? Legal_All : Legal_Reg | Legal_Imm);
     if (isVectorType(Dest->getType()))
       _movp(Dest, RI);
     else
@@ -4098,6 +4111,162 @@ void TargetX8632::lowerUnreachable(const InstUnreachable * /*Inst*/) {
   lowerCall(Call);
 }
 
+// Turn an i64 Phi instruction into a pair of i32 Phi instructions, to
+// preserve integrity of liveness analysis.  Undef values are also
+// turned into zeroes, since loOperand() and hiOperand() don't expect
+// Undef input.
+void TargetX8632::prelowerPhis() {
+  CfgNode *Node = Context.getNode();
+  for (InstPhi *Phi : Node->getPhis()) {
+    if (Phi->isDeleted())
+      continue;
+    Variable *Dest = Phi->getDest();
+    if (Dest->getType() == IceType_i64) {
+      Variable *DestLo = llvm::cast<Variable>(loOperand(Dest));
+      Variable *DestHi = llvm::cast<Variable>(hiOperand(Dest));
+      InstPhi *PhiLo = InstPhi::create(Func, Phi->getSrcSize(), DestLo);
+      InstPhi *PhiHi = InstPhi::create(Func, Phi->getSrcSize(), DestHi);
+      for (SizeT I = 0; I < Phi->getSrcSize(); ++I) {
+        Operand *Src = Phi->getSrc(I);
+        CfgNode *Label = Phi->getLabel(I);
+        if (llvm::isa<ConstantUndef>(Src))
+          Src = Ctx->getConstantZero(Dest->getType());
+        PhiLo->addArgument(loOperand(Src), Label);
+        PhiHi->addArgument(hiOperand(Src), Label);
+      }
+      Node->getPhis().push_back(PhiLo);
+      Node->getPhis().push_back(PhiHi);
+      Phi->setDeleted();
+    }
+  }
+}
+
+namespace {
+
+bool isMemoryOperand(const Operand *Opnd) {
+  if (const auto Var = llvm::dyn_cast<Variable>(Opnd))
+    return !Var->hasReg();
+  if (llvm::isa<Constant>(Opnd))
+    return isScalarFloatingType(Opnd->getType());
+  return true;
+}
+
+} // end of anonymous namespace
+
+// Lower the pre-ordered list of assignments into mov instructions.
+// Also has to do some ad-hoc register allocation as necessary.
+void TargetX8632::lowerPhiAssignments(CfgNode *Node,
+                                      const AssignList &Assignments) {
+  assert(Node->getOutEdges().size() == 1);
+  CfgNode *Succ = Node->getOutEdges()[0];
+  getContext().init(Node);
+  // Register set setup similar to regAlloc() and postLower().
+  RegSetMask RegInclude = RegSet_All;
+  RegSetMask RegExclude = RegSet_StackPointer;
+  if (hasFramePointer())
+    RegExclude |= RegSet_FramePointer;
+  llvm::SmallBitVector Available = getRegisterSet(RegInclude, RegExclude);
+  bool NeedsRegs = false;
+  // Initialize the set of available registers to the set of what is
+  // available (not live) at the beginning of the block, minus all
+  // registers used as Dest operands in the Assignments.  To do this,
+  // we start off assuming all registers are available, then iterate
+  // through the Assignments and remove Dest registers.  During this
+  // iteration, we also determine whether we will actually need any
+  // extra registers for memory-to-memory copies.  If so, we do the
+  // actual work of remove the live-in registers from the set.

[jvoung (off chromium), 2014/10/27 22:12:21]

"of remove the" -> "of removing the"

[Jim Stichnoth, 2014/10/28 01:20:14]

Done.

+  for (InstAssign *Assign : Assignments) {
+    Variable *Dest = Assign->getDest();
+    if (Dest->hasReg()) {
+      Available[Dest->getRegNum()] = false;
+    } else if (isMemoryOperand(Assign->getSrc(0))) {
+      NeedsRegs = true; // Src and Dest are both in memory
+    }
+  }
+  if (NeedsRegs) {
+    LivenessBV &LiveIn = Func->getLiveness()->getLiveIn(Succ);
+    for (int i = LiveIn.find_first(); i != -1; i = LiveIn.find_next(i)) {
+      Variable *Var = Func->getLiveness()->getVariable(i, Succ);
+      if (Var->hasReg())
+        Available[Var->getRegNum()] = false;
+    }
+  }
+  // Iterate backwards through the Assignments.  After lowering each
+  // assignment, add Dest to the set of available registers, and
+  // remove Src from the set of available registers.  Iteration is
+  // done backwards to enable incremental updates of the available
+  // register set, and the lowered instruction numbers may be out of
+  // order, but that can be worked around by renumbering the block
+  // afterwards if necessary.
+  for (auto I = Assignments.rbegin(), E = Assignments.rend(); I != E; ++I) {
+    Context.rewind();
+    InstAssign *Assign = *I;
+    Variable *Dest = Assign->getDest();
+    Operand *Src = Assign->getSrc(0);
+    Variable *SrcVar = llvm::dyn_cast<Variable>(Src);
+    // Use normal assignments lowering, except lower mem=mem specially
+    // so we can register-allocate at the same time.
+    if (!isMemoryOperand(Dest) || !isMemoryOperand(Src)) {
+      lowerAssign(Assign);
+    } else {
+      assert(Dest->getType() == Src->getType());
+      const llvm::SmallBitVector &RegsForType =
+          getRegisterSetForType(Dest->getType());
+      llvm::SmallBitVector AvailRegsForType = RegsForType & Available;
+      if (AvailRegsForType.any()) {
+        // TODO(stichnot): Opportunity for register randomization.
+        int32_t RegNum = AvailRegsForType.find_first();
+        Variable *Temp = NULL;
+        Operand *NewSrc = Src;
+        if (llvm::isa<ConstantUndef>(Src)) {
+          if (isVectorType(Src->getType()))
+            NewSrc = makeVectorOfZeros(Src->getType());
+          else
+            NewSrc = Ctx->getConstantZero(Src->getType());
+        }
+        if (isVectorType(Dest->getType())) {
+          Temp = makeReg(Dest->getType(), RegNum);
+          _movp(Temp, NewSrc);
+          _movp(Dest, Temp);
+        } else {
+          _mov(Temp, NewSrc, RegNum);
+          _mov(Dest, Temp);
+        }
+      } else {
+        // TODO(stichnot): Opportunity for register randomization.
+        int32_t RegNum = RegsForType.find_first();
+        assert(RegNum >= 0);
+        Variable *Preg = getPhysicalRegister(RegNum, Dest->getType());
+        Variable *Tmp1 = makeReg(Dest->getType());
+        Variable *Tmp2 = NULL;
+        if (isVectorType(Dest->getType())) {
+          Tmp2 = makeReg(Dest->getType(), RegNum);
+          _movp(Tmp1, Preg);
+          _movp(Tmp2, Src);
+          _movp(Dest, Tmp2);
+          _movp(Preg, Tmp1);
+        } else {
+          _mov(Tmp1, Preg);
+          _mov(Tmp2, Src, RegNum);
+          _mov(Dest, Tmp2);
+          _mov(Preg, Tmp1);
+        }
+        Tmp1->setNeedsStackSlot();

[jvoung (off chromium), 2014/10/27 22:12:21]

Woh interesting -- Tmp1 is a "makeReg()" so has infinite weight, but it also
NeedsStackSlot. Could makeVariable() be used instead or no?

[Jim Stichnoth, 2014/10/28 01:20:14]

Good point, done.

+      }
+    }
+    // Update register availability before moving to the previous
+    // instruction on the Assignments list.
+    if (Dest->hasReg())
+      Available[Dest->getRegNum()] = true;
+    if (SrcVar && SrcVar->hasReg())
+      Available[SrcVar->getRegNum()] = false;
+  }
+
+  // Add the terminator branch instruction to the end.
+  Context.setInsertPoint(Context.end());
+  _br(Succ);
+}
+
 // There is no support for loading or emitting vector constants, so the
 // vector values returned from makeVectorOfZeros, makeVectorOfOnes,
 // etc. are initialized with register operations.