Subzero: Fix a bug in advanced 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 307 matching lines @@
   InstPhi *Phi = nullptr;
   Variable *Dest = nullptr;
   Operand *Src = nullptr;
   bool Processed = false;
   size_t NumPred = 0; // number of entries whose Src is this Dest
   int32_t Weight = 0; // preference for topological order
 };
 using PhiDescList = llvm::SmallVector<PhiDesc, 32>;
 
 // Always pick NumPred=0 over NumPred>0.
-constexpr int32_t WeightNoPreds = 4;
+constexpr int32_t WeightNoPreds = 8;
 // Prefer Src as a register because the register might free up.
-constexpr int32_t WeightSrcIsReg = 2;
+constexpr int32_t WeightSrcIsReg = 4;
 // Prefer Dest not as a register because the register stays free longer.
-constexpr int32_t WeightDestNotReg = 1;
+constexpr int32_t WeightDestNotReg = 2;
+// Prefer NumPred=1 over NumPred>1.  This is used as a tiebreaker when a
+// dependency cycle must be broken so that hopefully only one temporary
+// assignment has to be added to break the cycle.
+constexpr int32_t WeightOnePred = 1;
 
 bool sameVarOrReg(TargetLowering *Target, const Variable *Var1,
                   const Operand *Opnd) {
   if (Var1 == Opnd)
     return true;
   const auto *Var2 = llvm::dyn_cast<Variable>(Opnd);
   if (Var2 == nullptr)
     return false;
 
   // If either operand lacks a register, they cannot be the same.
   if (!Var1->hasReg())
     return false;
   if (!Var2->hasReg())
     return false;
 
   const auto RegNum1 = Var1->getRegNum();
   const auto RegNum2 = Var2->getRegNum();
   // Quick common-case check.
   if (RegNum1 == RegNum2)
     return true;
 
   assert(Target->getAliasesForRegister(RegNum1)[RegNum2] ==
          Target->getAliasesForRegister(RegNum2)[RegNum1]);
   return Target->getAliasesForRegister(RegNum1)[RegNum2];
 }
 
 // Update NumPred for all Phi assignments using Var as their Dest variable.
-// Also update Weight if NumPred dropped from 1 to 0.
+// Also update Weight if NumPred dropped from 2 to 1, or 1 to 0.
 void updatePreds(PhiDescList &Desc, TargetLowering *Target, Variable *Var) {
   for (PhiDesc &Item : Desc) {
     if (!Item.Processed && sameVarOrReg(Target, Var, Item.Dest)) {
-      if (--Item.NumPred == 0) {
-        Item.Weight += WeightNoPreds;
+      --Item.NumPred;
+      if (Item.NumPred == 1) {
+        // If NumPred changed from 2 to 1, add in WeightOnePred.
+        Item.Weight += WeightOnePred;
+      } else if (Item.NumPred == 0) {
+        // If NumPred changed from 1 to 0, subtract WeightOnePred and add in
+        // WeightNoPreds.
+        Item.Weight += (WeightNoPreds - WeightOnePred);
       }
     }
   }
 }
 
 } // 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.
 //
@@ skipping 96 matching lines @@
       }
     }
 
     // Another pass to compute initial Weight values.
     for (PhiDesc &Item : Desc) {
       if (Item.Processed)
         continue;
       int32_t Weight = 0;
       if (Item.NumPred == 0)
         Weight += WeightNoPreds;
+      if (Item.NumPred == 1)
+        Weight += WeightOnePred;
       if (auto *Var = llvm::dyn_cast<Variable>(Item.Src))
         if (Var->hasReg())
           Weight += WeightSrcIsReg;
       if (!Item.Dest->hasReg())
         Weight += WeightDestNotReg;
       Item.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 instructions, but with a small constant factor compared to
     // a likely implementation of O(N) topological sort.
     for (; Remaining; --Remaining) {
       int32_t BestWeight = -1;
       PhiDesc *BestItem = nullptr;
       // Find the best candidate.
       for (PhiDesc &Item : Desc) {
         if (Item.Processed)
           continue;
-        int32_t Weight = 0;
-        Weight = Item.Weight;
+        const int32_t Weight = Item.Weight;
         if (Weight > BestWeight) {
           BestItem = &Item;
           BestWeight = Weight;
         }
       }
       assert(BestWeight >= 0);
-      assert(BestItem->NumPred <= 1);
       Variable *Dest = BestItem->Dest;
       Operand *Src = BestItem->Src;
       assert(!sameVarOrReg(Target, Dest, Src));
       // Break a cycle by introducing a temporary.
-      if (BestItem->NumPred) {
+      while (BestItem->NumPred > 0) {
         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 (PhiDesc &Item : Desc) {
           if (Item.Processed)
             continue;
           Operand *OtherSrc = Item.Src;
           if (Item.NumPred && sameVarOrReg(Target, Dest, OtherSrc)) {
             SizeT VarNum = Func->getNumVariables();
@@ skipping 921 matching lines @@
   auto *Instr = InstIntrinsicCall::create(
       Func, 5, Func->makeVariable(IceType_i64), RMWI64Name, Info->Info);
   Instr->addArg(AtomicRMWOp);
   Instr->addArg(Counter);
   Instr->addArg(One);
   Instr->addArg(OrderAcquireRelease);
   Insts.push_front(Instr);
 }
 
 } // end of namespace Ice