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..5b56530987cd98f99414fc0f14f75f31d3c8ddfb 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())
       continue;
     // A spill slot linked to a variable with a stack slot should reuse
     // that stack slot.
@@ -1695,8 +1707,10 @@ void TargetX8632::lowerAssign(const InstAssign *Inst) {
     _mov(T_Hi, Src0Hi);
     _mov(DestHi, T_Hi);
   } else {
-    // RI is either a physical register or an immediate.
-    Operand *RI = legalize(Src0, Legal_Reg | Legal_Imm);
+    // If Dest is in memory, then RI is either a physical register or
+    // an immediate, otherwise RI can be anything.
+    Operand *RI =
+        legalize(Src0, Dest->hasReg() ? Legal_All : Legal_Reg | Legal_Imm);
     if (isVectorType(Dest->getType()))
       _movp(Dest, RI);
     else
@@ -4098,6 +4112,165 @@ 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);

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

Would it help to also also assert that the Node is empty (no existing terminator
branch, since it's added by this)?

[Jim Stichnoth, 2014/10/30 00:25:25]

Done.

+  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

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

At the beginning of the successor block?

I guess because this node is empty, the two are the same, but if the Phis are
considered to be added to the end of this current block, then you're looking for
the LiveIn of the successor?

[Jim Stichnoth, 2014/10/30 00:25:25]

That's right, the beginning of the successor block.

One way to think about this is the following.  CfgNode::liveness() did a
backward pass over the successor's regular instructions, and then did a special
pass over its phi instructions where it marked the phi dest variables as not
live but ignored the phi src variables (see IsPhi in Inst::liveness()).  We're
trying to reconstruct the liveness state at the point between the regular
instructions and the phi instructions by starting with the final result
(successor's LiveIn) and undoing the killing of dest variables, meaning livening
them, meaning removing their registers from the available set.

While writing this, it occurred to me that this work is being identically
repeated on the successor node for every split edge, and could be done slightly
more efficiently at the time of splitting.  Added a TODO.

+  // 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 removing the live-in registers from the set.
+  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)) {

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

Probably rare, but might be good to add a test for this case --  It seems like
isMemoryOperand() is a bit conservative for ConstantUndef of integers (that's
not really mem=mem is it?). It wasn't obvious to me why Undef is made
deterministically 0 here, but not in the branches.

[Jim Stichnoth, 2014/10/30 00:25:25]

Because of the "(!isMemoryOperand(Dest) || !isMemoryOperand(Src))" test above,
Src must be memory and therefore not an integer constant (including undef).

Basically, this is copying some of the logic of legalize() which includes
lowering under to zeroes.  In the other situations, lowerAssign() will be called
which in turn calls legalize() which lowers them to zeroes.

[jvoung (off chromium), 2014/10/30 15:55:25]

How about legalize() in the later else-case? lowerAssign() is used for the first
if(), but not that later else (when mem=mem and no registers are free)?

[Jim Stichnoth, 2014/10/30 19:10:34]

I refactored the mem=mem case to be more uniform between the cases where there
is a register available and when one has to be spilled.

+          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 = Func->makeVariable(Dest->getType());
+        Tmp1->setNeedsStackSlot();
+        // TODO(stichnot): Don't force Tmp1 to be stack-allocated.  If
+        // there happens to be a free register, it could be used
+        // instead.
+        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);
+        }
+      }
+    }
+    // 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.