Subzero: Allow delaying Phi lowering until after register allocation.

src/IceTargetLoweringX8632.cpp

 //===- subzero/src/IceTargetLoweringX8632.cpp - x86-32 lowering -----------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the TargetLoweringX8632 class, which
 // consists almost entirely of the lowering sequence for each
 // high-level instruction.  It also implements
 // TargetX8632Fast::postLower() which does the simplest possible
 // register allocation for the "fast" target.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/MathExtras.h"
 
 #include "IceCfg.h"
 #include "IceCfgNode.h"
 #include "IceClFlags.h"
 #include "IceDefs.h"
 #include "IceGlobalInits.h"
 #include "IceInstX8632.h"
+#include "IceLiveness.h"
 #include "IceOperand.h"
 #include "IceRegistersX8632.h"
 #include "IceTargetLoweringX8632.def"
 #include "IceTargetLoweringX8632.h"
 #include "IceUtils.h"
 
 namespace Ice {
 
 namespace {
 
@@ skipping 231 matching lines @@
                 "Inconsistency between ICETYPEX8632_TABLE and ICETYPE_TABLE");
 ICETYPE_TABLE;
 #undef X
 } // end of namespace dummy3
 
 } // end of anonymous namespace
 
 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.
   llvm::SmallBitVector IntegerRegisters(RegX8632::Reg_NUM);
   llvm::SmallBitVector IntegerRegistersI8(RegX8632::Reg_NUM);
   llvm::SmallBitVector FloatRegisters(RegX8632::Reg_NUM);
   llvm::SmallBitVector VectorRegisters(RegX8632::Reg_NUM);
   llvm::SmallBitVector InvalidRegisters(RegX8632::Reg_NUM);
   ScratchRegs.resize(RegX8632::Reg_NUM);
 #define X(val, encode, name, name16, name8, scratch, preserved, stackptr,      \
@@ skipping 18 matching lines @@
   TypeToRegisterSet[IceType_v16i1] = VectorRegisters;
   TypeToRegisterSet[IceType_v16i8] = VectorRegisters;
   TypeToRegisterSet[IceType_v8i16] = VectorRegisters;
   TypeToRegisterSet[IceType_v4i32] = VectorRegisters;
   TypeToRegisterSet[IceType_v4f32] = VectorRegisters;
 }
 
 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);
   Func->doAddressOpt();
 
   // Argument lowering
   Func->doArgLowering();
 
   // Target lowering.  This requires liveness analysis for some parts
   // of the lowering decisions, such as compare/branch fusing.  If
   // non-lightweight liveness analysis is used, the instructions need
   // to be renumbered first.  TODO: This renumbering should only be
   // necessary if we're actually calculating live intervals, which we
   // only do for register allocation.
   Func->renumberInstructions();
   if (Func->hasError())
     return;
 
   // TODO: It should be sufficient to use the fastest liveness
   // calculation, i.e. livenessLightweight().  However, for some
   // reason that slows down the rest of the translation.  Investigate.
   Func->liveness(Liveness_Basic);
   if (Func->hasError())
     return;
   Func->dump("After x86 address mode opt");
 
   Func->genCode();
   if (Func->hasError())
     return;
+  Func->dump("After x86 codegen");
 
   // Register allocation.  This requires instruction renumbering and
   // full liveness analysis.
   Func->renumberInstructions();
   if (Func->hasError())
     return;
   Func->liveness(Liveness_Intervals);
   if (Func->hasError())
     return;
   // Validate the live range computations.  The expensive validation
   // call is deliberately only made when assertions are enabled.
   assert(Func->validateLiveness());
   ComputedLiveRanges = true;
   // The post-codegen dump is done here, after liveness analysis and
   // associated cleanup, to make the dump cleaner and more useful.
   Func->dump("After initial x8632 codegen");
   Func->getVMetadata()->init(VMK_All);
   regAlloc();
   if (Func->hasError())
     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())
     return;
   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
   // reorder CfgNodes should be done after branch optimization.  We go
   // ahead and do it before nop insertion to reduce the amount of work
   // needed for searching for opportunities.
   Func->doBranchOpt();
   Func->dump("After branch optimization");
 
   // Nop insertion
@@ skipping 46 matching lines @@
 #define X(val, encode, name, name16, name8, scratch, preserved, stackptr,      \
           frameptr, isI8, isInt, isFP)                                         \
   name,
   REGX8632_TABLE
 #undef X
 };
 
 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) {
       Func->addImplicitArg(Reg);
       Reg->setIgnoreLiveness();
     }
   }
   return Reg;
 }
 
@@ skipping 234 matching lines @@
   for (Variable *Var : Variables) {
     if (Var->hasReg()) {
       RegsUsed[Var->getRegNum()] = true;
       continue;
     }
     // An argument either does not need a stack slot (if passed in a
     // register) or already has one (if passed on the stack).
     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.
     if (SpillVariable *SpillVar = llvm::dyn_cast<SpillVariable>(Var)) {
       assert(Var->getWeight() == RegWeight::Zero);
       if (!SpillVar->getLinkedTo()->hasReg()) {
         VariablesLinkedToSpillSlots.push_back(Var);
         continue;
       }
     }
@@ skipping 963 matching lines @@
     Operand *Src0Lo = loOperand(Src0);
     Operand *Src0Hi = hiOperand(Src0);
     Variable *DestLo = llvm::cast<Variable>(loOperand(Dest));
     Variable *DestHi = llvm::cast<Variable>(hiOperand(Dest));
     Variable *T_Lo = NULL, *T_Hi = NULL;
     _mov(T_Lo, Src0Lo);
     _mov(DestLo, T_Lo);
     _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
       _mov(Dest, RI);
   }
 }
 
 void TargetX8632::lowerBr(const InstBr *Inst) {
   if (Inst->isUnconditional()) {
     _br(Inst->getTargetUnconditional());
@@ skipping 2381 matching lines @@
   }
 }
 
 void TargetX8632::lowerUnreachable(const InstUnreachable * /*Inst*/) {
   const SizeT MaxSrcs = 0;
   Variable *Dest = NULL;
   InstCall *Call = makeHelperCall("ice_unreachable", Dest, MaxSrcs);
   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.
 //
 // TODO(wala): Add limited support for vector constants so that
 // complex initialization in registers is unnecessary.
 
 Variable *TargetX8632::makeVectorOfZeros(Type Ty, int32_t RegNum) {
   Variable *Reg = makeReg(Ty, RegNum);
   // Insert a FakeDef, since otherwise the live range of Reg might
@@ skipping 424 matching lines @@
   } else if (IsConstant || IsExternal)
     Str << "\t.zero\t" << Size << "\n";
   // Size is part of .comm.
 
   if (IsConstant || HasNonzeroInitializer || IsExternal)
     Str << "\t.size\t" << MangledName << ", " << Size << "\n";
   // Size is part of .comm.
 }
 
 } // end of namespace Ice