Subzero: Allow delaying Phi lowering until after register allocation.

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.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the CfgNode class, including the complexities
 // of instruction insertion and in-edge calculation.
 //
 //===----------------------------------------------------------------------===//
 
 #include "assembler.h"
 #include "IceCfg.h"
 #include "IceCfgNode.h"
 #include "IceInst.h"
 #include "IceLiveness.h"
 #include "IceOperand.h"
 #include "IceTargetLowering.h"
 
 namespace Ice {
 
 CfgNode::CfgNode(Cfg *Func, SizeT LabelNumber, IceString Name)
     : Func(Func), Number(LabelNumber), Name(Name), HasReturn(false),
-      InstCountEstimate(0) {}
+      NeedsPlacement(false), InstCountEstimate(0) {}
 
 // Returns the name the node was created with.  If no name was given,
 // it synthesizes a (hopefully) unique name.
 IceString CfgNode::getName() const {
   if (!Name.empty())
     return Name;
   return "__" + std::to_string(getIndex());
 }
 
 // Adds an instruction to either the Phi list or the regular
@@ skipping 159 matching lines @@
     }
   }
 }
 
 // Deletes the phi instructions after the loads and stores are placed.
 void CfgNode::deletePhis() {
   for (InstPhi *I : Phis)
     I->setDeleted();
 }
 
+// Splits the edge from Pred to this node by creating a new node and
+// hooking up the in and out edges appropriately.  (The EdgeIndex
+// parameter is only used to make the new node's name unique when
+// there are multiple edges between the same pair of nodes.)  The new
+// node's instruction list is initialized to the empty list, with no
+// terminator instruction.  If there are multiple edges from Pred to
+// this node, only one edge is split, and the particular choice of
+// edge is undefined.  This could happen with a switch instruction, or
+// a conditional branch that weirdly has both branches to the same
+// place.  TODO(stichnot,kschimpf): Figure out whether this is legal
+// in the LLVM IR or the PNaCl bitcode, and if so, we need to
+// establish a strong relationship among the ordering of Pred's
+// out-edge list, this node's in-edge list, and the Phi instruction's
+// operand list.
+CfgNode *CfgNode::splitIncomingEdge(CfgNode *Pred, SizeT EdgeIndex) {
+  CfgNode *NewNode =
+      Func->makeNode("split_" + Pred->getName() + "_" + getName() + "_" +
+                     std::to_string(EdgeIndex));
+  // The new node is added to the end of the node list, and will later
+  // need to be sorted into a reasonable topological order.
+  NewNode->setNeedsPlacement(true);
+  // Repoint Pred's out-edge.
+  bool Found = false;
+  for (auto I = Pred->OutEdges.begin(), E = Pred->OutEdges.end();
+       !Found && I != E; ++I) {
+    if (*I == this) {
+      *I = NewNode;
+      NewNode->InEdges.push_back(Pred);
+      Found = true;
+    }
+  }
+  assert(Found);
+  // Repoint this node's in-edge.
+  Found = false;
+  for (auto I = InEdges.begin(), E = InEdges.end(); !Found && I != E; ++I) {
+    if (*I == Pred) {
+      *I = NewNode;
+      NewNode->OutEdges.push_back(this);
+      Found = true;
+    }
+  }
+  assert(Found);
+  // Repoint a suitable branch instruction's target.
+  Found = false;
+  for (auto I = Pred->getInsts().rbegin(), E = Pred->getInsts().rend();
+       !Found && I != E; ++I) {
+    if (!(*I)->isDeleted()) {
+      Found = (*I)->repointEdge(this, NewNode);
+    }
+  }
+  assert(Found);
+  return NewNode;
+}
+
+namespace {
+
+// Helper function used by advancedPhiLowering().
+bool sameVarOrReg(const Variable *Var, const Operand *Opnd) {
+  if (Var == Opnd)
+    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.
+//
+// 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.
+//
+// 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.
+void CfgNode::advancedPhiLowering() {
+  if (getPhis().empty())
+    return;
+
+  // Count the number of non-deleted Phi instructions.
+  struct {
+    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
+  } Desc[getPhis().size()];
+
+  size_t NumPhis = 0;
+  for (InstPhi *Inst : getPhis()) {
+    if (!Inst->isDeleted()) {
+      Desc[NumPhis].Phi = Inst;
+      Desc[NumPhis].Dest = Inst->getDest();
+      ++NumPhis;
+    }
+  }
+  if (NumPhis == 0)
+    return;
+
+  SizeT InEdgeIndex = 0;
+  for (CfgNode *Pred : InEdges) {
+    CfgNode *Split = splitIncomingEdge(Pred, InEdgeIndex++);
+    AssignList Assignments;
+
+    // First pass computes Src and initializes NumPred.
+    for (size_t I = 0; I < NumPhis; ++I) {
+      Desc[I].Src = Desc[I].Phi->getOperandForTarget(Pred);
+      Desc[I].Processed = false;
+      Desc[I].NumPred = 0;
+    }
+    // Second pass computes NumPred by comparing every pair of Phi
+    // instructions.
+    for (size_t I = 0; I < NumPhis; ++I) {
+      const Variable *Dest = Desc[I].Dest;
+      for (size_t J = 0; J < NumPhis; ++J) {
+        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;
+    // Prefer Src as a register because the register might free up.
+    const int32_t WeightSrcIsReg = 2;
+    // Prefer Dest not as a register because the register stays free
+    // longer.
+    const int32_t WeightDestNotReg = 1;
+
+    for (size_t I = 0; I < NumPhis; ++I) {
+      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;
+      if (!Desc[I].Dest->hasReg())
+        Weight += WeightDestNotReg;
+      Desc[I].Weight = Weight;
+    }
+
+    // Repeatedly choose and process the best candidate in the
+    // topological sort, until no candidates remain.  This
+    // implementation is O(N^2) where N is the number of Phi

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

Any idea the "usual" # of Phis? (Would the N^2 be a problem? Anyway, this can be
tuned later too, but does look like dealing with cycles will be more work the
O(N) way).

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

OK, I ran some numbers across spec2k (is that representative? I don't know). 
Here is the distribution of number of Phi instructions in a basic block, across
all basic blocks in spec2k.  99% of blocks have 4 or fewer Phi instructions. 
(If we consider blocks with only 2 or more Phis, the 99% point is 9 Phis.)

Phis  Total   Fract.  Cumulative
0     154892  77.62%  77.62%
1     27688   13.88%  91.50%
2     9400    4.71%   96.21%
3     4750    2.38%   98.59%
4     1345    0.67%   99.27%
5     597     0.30%   99.57%
6     340     0.17%   99.74%
7     131     0.07%   99.80%
8     153     0.08%   99.88%
9     86      0.04%   99.92%
10    35      0.02%   99.94%
11    36      0.02%   99.96%
12    21      0.01%   99.97%
13    2       0.00%   99.97%
14    21      0.01%   99.98%
15    20      0.01%   99.99%
16    3       0.00%   99.99%
17    3       0.00%   99.99%
18    2       0.00%   99.99%
19    3       0.00%   99.99%
20    2       0.00%   100.00%
21    0       0.00%   100.00%
22    0       0.00%   100.00%
23    0       0.00%   100.00%
24    0       0.00%   100.00%
25    0       0.00%   100.00%
26    1       0.00%   100.00%
27    1       0.00%   100.00%
28    4       0.00%   100.00%
29    0       0.00%   100.00%
30    2       0.00%   100.00%
31    1       0.00%   100.00%

Actually, this N^2 loop is done for every edge, not every node, so those
statistics look like the following.  99% are 6 or fewer Phis, or 14 or fewer
when considering only 2 or more Phis.


Phis  Total   Fract.  Cumulative
0     200284  60.65%  60.65%
1     81668   24.73%  85.38%
2     25454   7.71%   93.09%
3     12362   3.74%   96.83%
4     4196    1.27%   98.10%
5     1848    0.56%   98.66%
6     1494    0.45%   99.11%
7     474     0.14%   99.26%
8     801     0.24%   99.50%
9     684     0.21%   99.71%
10    113     0.03%   99.74%
11    164     0.05%   99.79%
12    87      0.03%   99.82%
13    4       0.00%   99.82%
14    293     0.09%   99.91%
15    208     0.06%   99.97%
16    15      0.00%   99.97%
17    19      0.01%   99.98%
18    5       0.00%   99.98%
19    6       0.00%   99.98%
20    5       0.00%   99.99%
21    0       0.00%   99.99%
22    0       0.00%   99.99%
23    0       0.00%   99.99%
24    0       0.00%   99.99%
25    0       0.00%   99.99%
26    2       0.00%   99.99%
27    2       0.00%   99.99%
28    10      0.00%   99.99%
29    0       0.00%   99.99%
30    32      0.01%   100.00%
31    2       0.00%   100.00%

One more thing.  Summing up Total*Phis as an approximation of an O(N) algorithm
cost, compared to summing up Total*Phis*Phis as an O(N^2) cost, gives the O(N^2)
cost as 3.4x the O(N) cost, to give an idea of the opportunity.  (My conclusion:
something to consider later, but I'm not holding my breath.)

+    // instructions, but with a small constant factor compared to a
+    // likely implementation of O(N) topological sort.
+    for (size_t Remaining = NumPhis; Remaining; --Remaining) {
+      size_t BestIndex = 0;
+      int32_t BestWeight = -1;
+      // Find the best candidate.
+      for (size_t I = 0; I < NumPhis; ++I) {
+        if (Desc[I].Processed)
+          continue;
+        int32_t Weight = 0;
+        Weight = Desc[I].Weight;
+        if (Weight > BestWeight) {
+          BestIndex = I;
+          BestWeight = Weight;
+        }
+      }
+      assert(BestWeight >= 0);
+      assert(Desc[BestIndex].NumPred <= 1);
+      Variable *Dest = Desc[BestIndex].Dest;
+      Operand *Src = Desc[BestIndex].Src;
+      // Break a cycle by introducing a temporary.  Except don't
+      // bother for a self-assignment, which looks like a self-cycle
+      // with NumPred=1, since it can be left alone and will
+      // eventually be removed as a redundant assignment.
+      bool IsSelfAssignment = sameVarOrReg(Dest, Src);
+      if (!IsSelfAssignment && Desc[BestIndex].NumPred) {
+        bool Found = false;
+        // If the target instruction "A=B" is part of a cycle, find
+        // the "X=A" assignment in the cycle because it will have to
+        // 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(), "__split_" + std::to_string(VarNum));
+            Tmp->setNeedsStackSlot();
+            Assignments.push_back(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.  Except 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.
+      if (Dest != Src)

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

Could it be broadened beyond syntactically the same (to include all of
IsSelfAssignment)?

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

This was actually deliberate because if the test is broadened, you would lose
assignments like "A:eax=B:eax", and if another liveness pass gets run later, you
could have the assignment of B incorrectly eliminated, and the liveness of A
could incorrectly propagate all the way back to the entry node.  But this is
never a problem with "A=A" style assignments.

That said, these redundant assignments do contribute to the O(N^2) time, so I
moved them to be handled during initialization.

+        Assignments.push_back(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;
+    }
+
+    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();
+    Func->getVMetadata()->addNode(Split);
+  }
+
+  for (InstPhi *Inst : getPhis())
+    Inst->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);
   while (!Context.atEnd()) {
     Target->doAddressOpt();
@@ skipping 16 matching lines @@
   Context.advanceNext();
   Context.advanceCur();
   Target->doNopInsertion();
 }
 
 // Drives the target lowering.  Passes the current instruction and the
 // next non-deleted instruction for target lowering.
 void CfgNode::genCode() {
   TargetLowering *Target = Func->getTarget();
   LoweringContext &Context = Target->getContext();
-  // Lower only the regular instructions.  Defer the Phi instructions.
+  // Lower the regular instructions.
   Context.init(this);
   while (!Context.atEnd()) {
     InstList::iterator Orig = Context.getCur();
     if (llvm::isa<InstRet>(*Orig))
       setHasReturn();
     Target->lower();
     // Ensure target lowering actually moved the cursor.
     assert(Context.getCur() != Orig);
   }
+  // Do preliminary lowering of the Phi instructions.
+  Target->prelowerPhis();
 }
 
 void CfgNode::livenessLightweight() {
   SizeT NumVars = Func->getNumVariables();
   LivenessBV Live(NumVars);
   // Process regular instructions in reverse order.
   // TODO(stichnot): Use llvm::make_range with LLVM 3.5.
   for (auto I = Insts.rbegin(), E = Insts.rend(); I != E; ++I) {
     if ((*I)->isDeleted())
       continue;
@@ skipping 30 matching lines @@
   // Initialize Live to be the union of all successors' LiveIn.
   for (CfgNode *Succ : OutEdges) {
     Live |= Liveness->getLiveIn(Succ);
     // Mark corresponding argument of phis in successor as live.
     for (InstPhi *I : Succ->Phis)
       I->livenessPhiOperand(Live, this, Liveness);
   }
   Liveness->getLiveOut(this) = Live;
 
   // Process regular instructions in reverse order.
-  // TODO(stichnot): Use llvm::make_range with LLVM 3.5.
   for (auto I = Insts.rbegin(), E = Insts.rend(); I != E; ++I) {
     if ((*I)->isDeleted())
       continue;
     (*I)->liveness((*I)->getNumber(), Live, Liveness, LiveBegin, LiveEnd);
   }
   // Process phis in forward order so that we can override the
   // instruction number to be that of the earliest phi instruction in
   // the block.
+  SizeT NumNonDeadPhis = 0;
   InstNumberT FirstPhiNumber = Inst::NumberSentinel;
   for (InstPhi *I : Phis) {
     if (I->isDeleted())
       continue;
     if (FirstPhiNumber == Inst::NumberSentinel)
       FirstPhiNumber = I->getNumber();
-    I->liveness(FirstPhiNumber, Live, Liveness, LiveBegin, LiveEnd);
+    if (I->liveness(FirstPhiNumber, Live, Liveness, LiveBegin, LiveEnd))
+      ++NumNonDeadPhis;
   }
 
   // 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.)
   LivenessBV LiveOrig = Live;
   Live.resize(Liveness->getNumGlobalVars());
@@ skipping 14 matching lines @@
     }
     Str << "\n";
     llvm_unreachable("Fatal inconsistency in liveness analysis");
   }
 
   bool Changed = false;
   LivenessBV &LiveIn = Liveness->getLiveIn(this);
   // Add in current LiveIn
   Live |= LiveIn;
   // Check result, set LiveIn=Live
-  Changed = (Live != LiveIn);
-  if (Changed)
+  SizeT &PrevNumNonDeadPhis = Liveness->getNumNonDeadPhis(this);
+  bool LiveInChanged = (Live != LiveIn);
+  Changed = (NumNonDeadPhis != PrevNumNonDeadPhis || LiveInChanged);
+  if (LiveInChanged)
     LiveIn = Live;
+  PrevNumNonDeadPhis = NumNonDeadPhis;
   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
@@ skipping 99 matching lines @@
       ++IEB;
   }
   // Process the variables that are live across the entire block.
   for (int i = LiveInAndOut.find_first(); i != -1;
        i = LiveInAndOut.find_next(i)) {
     Variable *Var = Liveness->getVariable(i, this);
     Var->addLiveRange(FirstInstNum, LastInstNum + 1, 1);
   }
 }
 
+// If this node contains only deleted instructions, and ends in an
+// unconditional branch, contract the node by repointing all its
+// in-edges to its successor.
+void CfgNode::contractIfEmpty() {
+  if (InEdges.size() == 0)
+    return;
+  Inst *Branch = NULL;
+  for (Inst *I : Insts) {
+    if (!I->isDeleted() && !I->isUnconditionalBranch())
+      return;
+    Branch = I;
+  }
+  Branch->setDeleted();
+  assert(OutEdges.size() == 1);
+  // Repoint all this node's in-edges to this node's successor.
+  for (CfgNode *Pred : InEdges) {
+    for (auto I = Pred->OutEdges.begin(), E = Pred->OutEdges.end(); I != E;
+         ++I) {
+      if (*I == this) {
+        *I = OutEdges[0];
+        OutEdges[0]->InEdges.push_back(Pred);
+      }
+    }
+    for (Inst *I : Pred->getInsts()) {
+      if (!I->isDeleted())
+        I->repointEdge(this, OutEdges[0]);
+    }
+  }
+  InEdges.clear();
+  // Don't bother removing the single out-edge, which would also
+  // require finding the corresponding in-edge in the successor and
+  // removing it.
+}
+
 void CfgNode::doBranchOpt(const CfgNode *NextNode) {
   TargetLowering *Target = Func->getTarget();
   // Check every instruction for a branch optimization opportunity.
   // It may be more efficient to iterate in reverse and stop after the
   // first opportunity, unless there is some target lowering where we
   // have the possibility of multiple such optimizations per block
   // (currently not the case for x86 lowering).
-  for (Inst *I : Insts)
-    Target->doBranchOpt(I, NextNode);
+  for (Inst *I : Insts) {
+    if (!I->isDeleted()) {
+      Target->doBranchOpt(I, NextNode);
+    }
+  }
 }
 
 // ======================== Dump routines ======================== //
 
 void CfgNode::emit(Cfg *Func) const {
   Func->setCurrentNode(this);
   Ostream &Str = Func->getContext()->getStrEmit();
   if (Func->getEntryNode() == this) {
     Str << Func->getContext()->mangleName(Func->getFunctionName()) << ":\n";
   }
@@ skipping 106 matching lines @@
       if (!First)
         Str << ", ";
       First = false;
       Str << "%" << I->getName();
     }
     Str << "\n";
   }
 }
 
 } // end of namespace Ice