Subzero: Cleanly implement register allocation after phi lowering.

src/IceCfgNode.cpp

 //===- subzero/src/IceCfgNode.cpp - Basic block (node) implementation -----===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 252 matching lines @@
     return true;
   if (const auto Var2 = llvm::dyn_cast<Variable>(Opnd)) {
     if (Var->hasReg() && Var->getRegNum() == Var2->getRegNum())
       return true;
   }
   return false;
 }
 
 } // end of anonymous namespace
 
-// This the "advanced" version of Phi lowering for a basic block, in
-// contrast to the simple version that lowers through assignments
-// involving temporaries.
+// This the "advanced" version of Phi lowering for a basic block, in contrast to
+// the simple version that lowers through assignments involving temporaries.
 //
-// All Phi instructions in a basic block are conceptually executed in
-// parallel.  However, if we lower Phis early and commit to a
-// sequential ordering, we may end up creating unnecessary
-// interferences which lead to worse register allocation.  Delaying
-// Phi scheduling until after register allocation can help unless
-// there are no free registers for shuffling registers or stack slots
-// and spilling becomes necessary.
+// All Phi instructions in a basic block are conceptually executed in parallel.
+// However, if we lower Phis early and commit to a sequential ordering, we may
+// end up creating unnecessary interferences which lead to worse register
+// allocation.  Delaying Phi scheduling until after register allocation can help
+// unless there are no free registers for shuffling registers or stack slots and
+// spilling becomes necessary.
 //
-// The advanced Phi lowering starts by finding a topological sort of
-// the Phi instructions, where "A=B" comes before "B=C" due to the
-// anti-dependence on B.  If a topological sort is not possible due to
-// a cycle, the cycle is broken by introducing a non-parallel
-// temporary.  For example, a cycle arising from a permutation like
-// "A=B;B=C;C=A" can become "T=A;A=B;B=C;C=T".  All else being equal,
-// prefer to schedule assignments with register-allocated Src operands
-// earlier, in case that register becomes free afterwards, and prefer
-// to schedule assignments with register-allocated Dest variables
-// later, to keep that register free for longer.
+// The advanced Phi lowering starts by finding a topological sort of the Phi
+// instructions, where "A=B" comes before "B=C" due to the anti-dependence on B.
+// Preexisting register assignments are considered in the topological sort.  If
+// a topological sort is not possible due to a cycle, the cycle is broken by
+// introducing a non-parallel temporary.  For example, a cycle arising from a
+// permutation like "A=B;B=C;C=A" can become "T=A;A=B;B=C;C=T".  All else being
+// equal, prefer to schedule assignments with register-allocated Src operands
+// earlier, in case that register becomes free afterwards, and prefer to
+// schedule assignments with register-allocated Dest variables later, to keep
+// that register free for longer.
 //
-// Once the ordering is determined, the Cfg edge is split and the
-// assignment list is lowered by the target lowering layer.  The
-// specific placement of the new node within the Cfg node list is
-// deferred until later, including after empty node contraction.
+// Once the ordering is determined, the Cfg edge is split and the assignment
+// list is lowered by the target lowering layer.  Since the assignment lowering
+// may create new infinite-weight temporaries, a follow-on register allocation
+// pass will be needed.  To prepare for this, liveness (including live range
+// calculation) of the split nodes needs to be calculated, and liveness of the
+// original node need to be updated to "undo" the effects of the phi
+// assignments.
+
+// The specific placement of the new node within the Cfg node list is deferred
+// until later, including after empty node contraction.
+//
+// After phi assignments are lowered across all blocks, another register
+// allocation pass is run, focusing only on pre-colored and infinite-weight
+// variables, similar to Om1 register allocation (except without the need to
+// specially compute these variables' live ranges, since they have already been
+// precisely calculated).  The register allocator in this mode needs the ability
+// to forcibly spill and reload registers in case none are naturally available.
 void CfgNode::advancedPhiLowering() {
   if (getPhis().empty())
     return;
 
   // Count the number of non-deleted Phi instructions.
   struct PhiDesc {
     InstPhi *Phi;
     Variable *Dest;
     Operand *Src;
     bool Processed;
     size_t NumPred; // number of entries whose Src is this Dest
     int32_t Weight; // preference for topological order
   };
   llvm::SmallVector<PhiDesc, 32> Desc(getPhis().size());
 
   size_t NumPhis = 0;
   for (Inst &I : Phis) {
-    auto Inst = llvm::dyn_cast<InstPhi>(&I);
+    auto *Inst = llvm::dyn_cast<InstPhi>(&I);
     if (!Inst->isDeleted()) {
+      Variable *Dest = Inst->getDest();
       Desc[NumPhis].Phi = Inst;
-      Desc[NumPhis].Dest = Inst->getDest();
+      Desc[NumPhis].Dest = Dest;
       ++NumPhis;
+      // Undo the effect of the phi instruction on this node's live-in set by
+      // marking the phi dest variable as live on entry.
+      SizeT VarNum = Func->getLiveness()->getLiveIndex(Dest->getIndex());
+      assert(!Func->getLiveness()->getLiveIn(this)[VarNum]);
+      Func->getLiveness()->getLiveIn(this)[VarNum] = true;
+      Inst->setDeleted();
     }
   }
   if (NumPhis == 0)
     return;
 
   SizeT InEdgeIndex = 0;
   for (CfgNode *Pred : InEdges) {
     CfgNode *Split = splitIncomingEdge(Pred, InEdgeIndex++);
-    AssignList Assignments;
     SizeT Remaining = NumPhis;
 
     // First pass computes Src and initializes NumPred.
     for (size_t I = 0; I < NumPhis; ++I) {
       Variable *Dest = Desc[I].Dest;
       Operand *Src = Desc[I].Phi->getOperandForTarget(Pred);
       Desc[I].Src = Src;
       Desc[I].Processed = false;
       Desc[I].NumPred = 0;
       // Cherry-pick any trivial assignments, so that they don't
       // contribute to the running complexity of the topological sort.
       if (sameVarOrReg(Dest, Src)) {
         Desc[I].Processed = true;
         --Remaining;
         if (Dest != Src)
           // If Dest and Src are syntactically the same, don't bother
           // adding the assignment, because in all respects it would
           // be redundant, and if Dest/Src are on the stack, the
           // target lowering may naively decide to lower it using a
           // temporary register.
-          Assignments.push_back(InstAssign::create(Func, Dest, Src));
+          Split->appendInst(InstAssign::create(Func, Dest, Src));
       }
     }
     // Second pass computes NumPred by comparing every pair of Phi
     // instructions.
     for (size_t I = 0; I < NumPhis; ++I) {
       if (Desc[I].Processed)
         continue;
       const Variable *Dest = Desc[I].Dest;
       for (size_t J = 0; J < NumPhis; ++J) {
         if (Desc[J].Processed)
           continue;
         if (I != J) {
           // There shouldn't be two Phis with the same Dest variable
           // or register.
           assert(!sameVarOrReg(Dest, Desc[J].Dest));
         }
         const Operand *Src = Desc[J].Src;
         if (sameVarOrReg(Dest, Src))
           ++Desc[I].NumPred;
       }
     }
 
     // Another pass to compute initial Weight values.
 
     // Always pick NumPred=0 over NumPred>0.
-    const int32_t WeightNoPreds = 4;
+    constexpr int32_t WeightNoPreds = 4;
     // Prefer Src as a register because the register might free up.
-    const int32_t WeightSrcIsReg = 2;
+    constexpr int32_t WeightSrcIsReg = 2;
     // Prefer Dest not as a register because the register stays free
     // longer.
-    const int32_t WeightDestNotReg = 1;
+    constexpr int32_t WeightDestNotReg = 1;
 
     for (size_t I = 0; I < NumPhis; ++I) {
       if (Desc[I].Processed)
         continue;
       int32_t Weight = 0;
       if (Desc[I].NumPred == 0)
         Weight += WeightNoPreds;
       if (auto Var = llvm::dyn_cast<Variable>(Desc[I].Src))
         if (Var->hasReg())
           Weight += WeightSrcIsReg;
@@ skipping 34 matching lines @@
         // be rewritten as "X=tmp".
         for (size_t J = 0; !Found && J < NumPhis; ++J) {
           if (Desc[J].Processed)
             continue;
           Operand *OtherSrc = Desc[J].Src;
           if (Desc[J].NumPred && sameVarOrReg(Dest, OtherSrc)) {
             SizeT VarNum = Func->getNumVariables();
             Variable *Tmp = Func->makeVariable(OtherSrc->getType());
             if (BuildDefs::dump())
               Tmp->setName(Func, "__split_" + std::to_string(VarNum));
-            Assignments.push_back(InstAssign::create(Func, Tmp, OtherSrc));
+            Split->appendInst(InstAssign::create(Func, Tmp, OtherSrc));
             Desc[J].Src = Tmp;
             Found = true;
           }
         }
         assert(Found);
       }
       // Now that a cycle (if any) has been broken, create the actual
       // assignment.
-      Assignments.push_back(InstAssign::create(Func, Dest, Src));
+      Split->appendInst(InstAssign::create(Func, Dest, Src));
       // Update NumPred for all Phi assignments using this Phi's Src
       // as their Dest variable.  Also update Weight if NumPred
       // dropped from 1 to 0.
       if (auto Var = llvm::dyn_cast<Variable>(Src)) {
         for (size_t I = 0; I < NumPhis; ++I) {
           if (Desc[I].Processed)
             continue;
           if (sameVarOrReg(Var, Desc[I].Dest)) {
             if (--Desc[I].NumPred == 0)
               Desc[I].Weight += WeightNoPreds;
           }
         }
       }
       Desc[BestIndex].Processed = true;
     }
+    Split->appendInst(InstBr::create(Func, this));
 
-    Func->getTarget()->lowerPhiAssignments(Split, Assignments);
-
-    // Renumber the instructions to be monotonically increasing so
-    // that addNode() doesn't assert when multi-definitions are added
-    // out of order.
-    Split->renumberInstructions();
+    Split->genCode();
     Func->getVMetadata()->addNode(Split);
   }
-
-  for (Inst &I : Phis)
-    I.setDeleted();
 }
 
 // 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);
@@ skipping 405 matching lines @@
   Liveness *Liveness = Func->getLiveness();
   bool DecorateAsm =
       Liveness && Func->getContext()->getFlags().getDecorateAsm();
   Str << getAsmName() << ":\n";
   // LiveRegCount keeps track of the number of currently live
   // variables that each register is assigned to.  Normally that would
   // be only 0 or 1, but the register allocator's AllowOverlap
   // inference allows it to be greater than 1 for short periods.
   std::vector<SizeT> LiveRegCount(Func->getTarget()->getNumRegisters());
   if (DecorateAsm) {
-    const bool IsLiveIn = true;
+    constexpr bool IsLiveIn = true;
     emitRegisterUsage(Str, Func, this, IsLiveIn, LiveRegCount);
   }
 
   for (const Inst &I : Phis) {
     if (I.isDeleted())
       continue;
     // Emitting a Phi instruction should cause an error.
     I.emit(Func);
   }
   for (const Inst &I : Insts) {
@@ skipping 14 matching lines @@
         ++LiveRegCount[Dest->getRegNum()];
       continue;
     }
     I.emit(Func);
     if (DecorateAsm)
       emitLiveRangesEnded(Str, Func, &I, LiveRegCount);
     Str << "\n";
     updateStats(Func, &I);
   }
   if (DecorateAsm) {
-    const bool IsLiveIn = false;
+    constexpr bool IsLiveIn = false;
     emitRegisterUsage(Str, Func, this, IsLiveIn, LiveRegCount);
   }
 }
 
 // Helper class for emitIAS().
 namespace {
 class BundleEmitHelper {
   BundleEmitHelper() = delete;
   BundleEmitHelper(const BundleEmitHelper &) = delete;
   BundleEmitHelper &operator=(const BundleEmitHelper &) = delete;
@@ skipping 321 matching lines @@
   InstIntrinsicCall *Inst = InstIntrinsicCall::create(
       Func, 5, Func->makeVariable(IceType_i64), RMWI64Name, Info->Info);
   Inst->addArg(AtomicRMWOp);
   Inst->addArg(Counter);
   Inst->addArg(One);
   Inst->addArg(OrderAcquireRelease);
   Insts.push_front(Inst);
 }
 
 } // end of namespace Ice