[NewGVN] Split OpPHI detection and creation.

[fhahn]

Summary

It also adds a check making sure PHIs for operands are all in the same
block.

Patch by Daniel Berlin <[e-mail]>

[• dberlin]

I don't understand how this can happen, since the value phi should be equivalent to an op phi in the same block.
I need to look at this more.

[• dberlin]

So, we are definitely "doing it wrong".

This code is definitely broken in the case that multiple operands are defined by phi of ops, and they are not in the same block.
In fact, i think it's now broken with all multiple phis, unless the phis are in the same block. It is just getting lucky because it is getting blocked from using them.

It also badly needs refactoring because of how long it took to notice this.

Here is what is happening:

Let me start with context. The reason it differentiates the phi block from the instruction block is to catch the case the instruction operand is dependent on a dominating phi

ie
bb0
a = phi
goto bb1

bb1:
b = add a, 1

These are to transform valid phi of ops.
Here it will evaluate add a, 1 for each predecessor block of *a*

The limitation on the code the way it is currently written, however, is that it assumes *all* phis for the instruction are in the same block.
Thus, it only evaluates the phiblock once, and generates the operation in the phi block and sees what happens.
You can see this in the code if you look hard enough. the loop over the original instruction operands will return an expression or nullptr the second it hits an operand that is a phi.
The only reason it translates each phi in the expression when they are in the same block is because it does `Op = Op->DoPHITranslation(PHIBlock, PredBB);` for each pred.
Which will handle it regardless of whether it's the original phi or not.

If you give it something like:
bb:

br label %bb1

bb1:

%tmp = phi i32 [ 0, %bb ], [ %tmp10, %bb6 ]

bb6:

%tmp7 = phi i32 [ 0, %bb1 ], [ 1, %bb4 ], [ 1, %bb5 ]
%tmp9 = or i32 %tmp, %tmp7

It will try to evaluate tmp9 in the tmp1 block as or i32 <phi pred>, %tmp7, and either

1. fail to find anything
2. fail safety checks
3. get unlucky, find something, and crash

At least as far as i've been able to reproduce, the only case #3 occurs is when we've made phi of ops for the operands, as you see in this case.
There, it gets past the safety checking/etc, and all the way to the valuephi creation, but now the value phi is in the wrong block.

The correct way to handle all of this is unfortunately recursive.
We'd have to translate through each phi and phi block that occurs as an operand, and evaluate the operation in every possible predecessor of those, and merge those results.

This is unlikely to be worth it ATM, it seems incredibly uncommon.
It would be easy, however, if we refactored this code sanely.

For now, safety wise, we should verify all phis for an op are in the same block and give up if not.
I'll send along a patch to fhahn that works but is otherwise untested.

[• dberlin]

There is also a case 4 here i forgot, which is get unlucky, find something (where all blocks have the same number of preds) and probably generate wrong code :)

[fhahn]

In D43865#1026006, @dberlin wrote:

There, it gets past the safety checking/etc, and all the way to the valuephi creation, but now the value phi is in the wrong block.

The correct way to handle all of this is unfortunately recursive.
We'd have to translate through each phi and phi block that occurs as an operand, and evaluate the operation in every possible predecessor of those, and merge those results.

This is unlikely to be worth it ATM, it seems incredibly uncommon.
It would be easy, however, if we refactored this code sanely.

For now, safety wise, we should verify all phis for an op are in the same block and give up if not.
I'll send along a patch to fhahn that works but is otherwise untested.

Thanks for tracking that down and for sending along a patch. As far as I can see, it splits up analysis and the phi creation, which makes it much easier to see what going on :) It also fixes the issue by checking if all phis for on op are in the same block

Given that, I was wondering if there is anything left you want me to do or I should look into? :)

[• dberlin]

At a minimum, the patch needs bootstrap and testing, i didn't test it except on this case and test/Transforms/NewGVN.
:)

[fhahn]

In D43865#1028755, @dberlin wrote:

At a minimum, the patch needs bootstrap and testing, i didn't test it except on this case and test/Transforms/NewGVN.
:)

Done!

With and without this patch, bootstrapping clang/llvm fails with "value number changed after ..." assertions. I finally took the time and re-visited D42180. One case we seem to miss is when changes to the translated operands of the ValueOp cause us to find a leader for the ValueOp, for which we previously did not find a leader and returned early. In this case no additional users are added to trigger re-evaluation of the phi node.

Together with D42180, bootstrapping passed. And also running the test-suite.

[• dberlin]

So, just to put this on the review: the current code on this review definitely not the right fix compared to the patch i sent :)
I think we should commit that split/cleanup (not sure if you did it as part of the last patch.
It sounds like you had time to bootstrap/test it. If so, please feel free to commit it

[fhahn]

In D43865#1072149, @dberlin wrote:

So, just to put this on the review: the current code on this review definitely not the right fix compared to the patch i sent :)
I think we should commit that split/cleanup (not sure if you did it as part of the last patch.
It sounds like you had time to bootstrap/test it. If so, please feel free to commit it

Yep, the diff in Phab is out-dated. I'll commit D42180 first, and then rebase your patch and do another bootstrap round and update the diff here.

[fhahn]

This is mostly @dberlin 's patch rebased and with the test case.

lib/Transforms/Scalar/NewGVN.cpp

NewGVN::makePossiblePHIOfOps(Instruction *I,
   auto *MemAccess = getMemoryAccess(I);
   // If the memory operation is defined by a memory operation this block that
   // isn't a MemoryPhi, transforming the pointer backwards through a scalar phi
   // can't help, as it would still be killed by that memory operation.
   if (MemAccess && !isa<MemoryPhi>(MemAccess->getDefiningAccess()) &&
       MemAccess->getDefiningAccess()->getBlock() == I->getParent())
     return nullptr;
 
-  SmallPtrSet<const Value *, 10> VisitedOps;
   // Convert op of phis to phi of ops
-  for (auto *Op : I->operand_values()) {
+  SmallPtrSet<const Value *, 10> VisitedOps;
+  SmallVector<Value *, 4> Ops(I->operand_values());
+  BasicBlock *SamePHIBlock = nullptr;
+  PHINode *OpPHI = nullptr;
+  if (!DebugCounter::shouldExecute(PHIOfOpsCounter))
+    return nullptr;
+  for (auto *Op : Ops) {
     if (!isa<PHINode>(Op)) {
       auto *ValuePHI = RealToTemp.lookup(Op);
       if (!ValuePHI)
         continue;
       DEBUG(dbgs() << "Found possible dependent phi of ops\n");
       Op = ValuePHI;
     }
-    auto *OpPHI = cast<PHINode>(Op);
+    OpPHI = cast<PHINode>(Op);
+    if (!SamePHIBlock) {
+      SamePHIBlock = getBlockForValue(OpPHI);
+    } else if (SamePHIBlock != getBlockForValue(OpPHI)) {
+      DEBUG(dbgs()
+            << "PHIs for operands are not all in the same block, aborting\n");
+      return nullptr;
+    }
     // No point in doing this for one-operand phis.
-    if (OpPHI->getNumOperands() == 1)
+    if (OpPHI->getNumOperands() == 1) {
+      OpPHI = nullptr;
       continue;
-    if (!DebugCounter::shouldExecute(PHIOfOpsCounter))
-      return nullptr;
-    SmallVector<ValPair, 4> Ops;
-    SmallPtrSet<Value *, 4> Deps;
-    auto *PHIBlock = getBlockForValue(OpPHI);
-    RevisitOnReachabilityChange[PHIBlock].reset(InstrToDFSNum(I));
-    for (unsigned PredNum = 0; PredNum < OpPHI->getNumOperands(); ++PredNum) {
-      auto *PredBB = OpPHI->getIncomingBlock(PredNum);
-      Value *FoundVal = nullptr;
-      // We could just skip unreachable edges entirely but it's tricky to do
-      // with rewriting existing phi nodes.
-      if (ReachableEdges.count({PredBB, PHIBlock})) {
-        // Clone the instruction, create an expression from it that is
-        // translated back into the predecessor, and see if we have a leader.
-        Instruction *ValueOp = I->clone();
-        SmallPtrSet<Value *, 4> CurrentDeps;
-        if (MemAccess)
-          TempToMemory.insert({ValueOp, MemAccess});
-        bool SafeForPHIOfOps = true;
-        VisitedOps.clear();
-        for (auto &Op : ValueOp->operands()) {
-          auto *OrigOp = &*Op;
-          // When these operand changes, it could change whether there is a
-          // leader for us or not, so we have to add additional users.
-          if (isa<PHINode>(Op)) {
-            Op = Op->DoPHITranslation(PHIBlock, PredBB);
-            if (Op != OrigOp && Op != I)
-              CurrentDeps.insert(Op);
-          } else if (auto *ValuePHI = RealToTemp.lookup(Op)) {
-            if (getBlockForValue(ValuePHI) == PHIBlock)
-              Op = ValuePHI->getIncomingValueForBlock(PredBB);
-          }
-          // If we phi-translated the op, it must be safe.
-          SafeForPHIOfOps =
-              SafeForPHIOfOps &&
-              (Op != OrigOp || OpIsSafeForPHIOfOps(Op, PHIBlock, VisitedOps));
-        }
-        // FIXME: For those things that are not safe we could generate
-        // expressions all the way down, and see if this comes out to a
-        // constant.  For anything where that is true, and unsafe, we should
-        // have made a phi-of-ops (or value numbered it equivalent to something)
-        // for the pieces already.
-        FoundVal = !SafeForPHIOfOps ? nullptr
-                                    : findLeaderForInst(ValueOp, Visited,
-                                                        MemAccess, I, PredBB);
-        ValueOp->deleteValue();
-        if (!FoundVal) {
-          // We failed to find a leader for the current ValueOp, but this might
-          // change in case of the translated operands change.
-          if (SafeForPHIOfOps)
-            for (auto Dep : CurrentDeps)
-              addAdditionalUsers(Dep, I);
+    }
+  }
+
+  if (!OpPHI)
+
+  SmallVector<ValPair, 4> PHIOps;
+    SmallPtrSet<Value *, 4> CurrentDeps;
 
-          return nullptr;
-        }
-        Deps.insert(CurrentDeps.begin(), CurrentDeps.end());
-      } else {
-        DEBUG(dbgs() << "Skipping phi of ops operand for incoming block "
-                     << getBlockName(PredBB)
-                     << " because the block is unreachable\n");
-        FoundVal = UndefValue::get(I->getType());
-        RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I));
-      }
 
-      Ops.push_back({FoundVal, PredBB});
-      DEBUG(dbgs() << "Found phi of ops operand " << *FoundVal << " in "
-                   << getBlockName(PredBB) << "\n");
-    }
-    for (auto Dep : Deps)
-      addAdditionalUsers(Dep, I);
-    sortPHIOps(Ops);
-    auto *E = performSymbolicPHIEvaluation(Ops, I, PHIBlock);
-    if (isa<ConstantExpression>(E) || isa<VariableExpression>(E)) {
-      DEBUG(dbgs()
-            << "Not creating real PHI of ops because it simplified to existing "
-               "value or constant\n");
-      return E;
-    }
-    auto *ValuePHI = RealToTemp.lookup(I);
-    bool NewPHI = false;
-    if (!ValuePHI) {
-      ValuePHI =
-          PHINode::Create(I->getType(), OpPHI->getNumOperands(), "phiofops");
-      addPhiOfOps(ValuePHI, PHIBlock, I);
-      NewPHI = true;
-      NumGVNPHIOfOpsCreated++;
-    }
-    if (NewPHI) {
-      for (auto PHIOp : Ops)
-        ValuePHI->addIncoming(PHIOp.first, PHIOp.second);
-    } else {
-      TempToBlock[ValuePHI] = PHIBlock;
-      unsigned int i = 0;
-      for (auto PHIOp : Ops) {
-        ValuePHI->setIncomingValue(i, PHIOp.first);
-        ValuePHI->setIncomingBlock(i, PHIOp.second);
-        ++i;
-      }
-    }
-    RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I));
-    DEBUG(dbgs() << "Created phi of ops " << *ValuePHI << " for " << *I
-                 << "\n");
+    PHIOps.push_back({FoundVal, PredBB});
+  sortPHIOps(PHIOps);
+  auto *E = performSymbolicPHIEvaluation(PHIOps, I, PHIBlock);
+    for (auto PHIOp : PHIOps)
+    for (auto PHIOp : PHIOps) {
+  DEBUG(dbgs() << "Created phi of ops " << *ValuePHI << " for " << *I << "\n");
 
-    return E;
-  }
-  return nullptr;
-}
 
 // The algorithm initially places the values of the routine in the TOP
 // congruence class. The leader of TOP is the undetermined value `undef`.
 // When the algorithm has finished, values still in TOP are unreachable.
 void NewGVN::initializeCongruenceClasses(Function &F) {
   NextCongruenceNum = 0;
 
   // Note that even though we use the live on entry def as a representative

test/Transforms/NewGVN/phi-of-ops-move-block.ll

critedge:                                        ; preds = %lr.ph, %bb1
   %cmp2 = icmp ne i32 %.05.lcssa, 0
   %brmerge = or i1 %cmp0, %cmp2
   %add1 = add nsw i32 %storemerge, -1
   br i1 %brmerge, label %bb1, label %end
 
 end:
   ret void
 }
+
+; In this test case a temporary PhiOfOps node gets moved to BB with more
+; predecessors, so a new one needs to be created.
+define void @test2() {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[STOREMERGE:%.*]] = phi i32 [ 0, [[TMP0:%.*]] ], [ [[ADD:%.*]], [[CRITEDGE:%.*]] ]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[STOREMERGE]], 0
+; CHECK-NEXT:    br i1 [[CMP1]], label [[LR_PH:%.*]], label [[CRITEDGE]]
+; CHECK:       lr.ph:
+; CHECK-NEXT:    br i1 undef, label [[SPLIT1:%.*]], label [[SPLIT2:%.*]]
+; CHECK:       split1:
+; CHECK-NEXT:    br label [[CRITEDGE]]
+; CHECK:       split2:
+; CHECK-NEXT:    br label [[CRITEDGE]]
+; CHECK:       critedge:
+; CHECK-NEXT:    [[PHIOFOPS1:%.*]] = phi i1 [ false, [[BB1]] ], [ true, [[SPLIT2]] ], [ true, [[SPLIT1]] ]
+; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ undef, [[BB1]] ], [ undef, [[SPLIT2]] ], [ undef, [[SPLIT1]] ]
+; CHECK-NEXT:    [[LCSSA:%.*]] = phi i32 [ 0, [[BB1]] ], [ -1, [[SPLIT1]] ], [ -1, [[SPLIT2]] ]
+; CHECK-NEXT:    [[ADD]] = add nsw i32 [[STOREMERGE]], -1
+; CHECK-NEXT:    br i1 [[PHIOFOPS]], label [[BB1]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+  br label %bb1
+
+bb1:                                      ; preds = %critedge, %0
+  %storemerge = phi i32 [ 0, %0 ], [ %add, %critedge ]
+  %cmp1 = icmp eq i32 %storemerge, 0
+  br i1 %cmp1, label %lr.ph, label %critedge
+
+lr.ph:                                           ; preds = %bb1
+  br i1 undef, label %split1, label %split2
+
+split1:                                     ; preds = %lr.ph
+  br label %critedge
+
+split2:                                     ; preds = %lr.ph
+  br label %critedge
+
+critedge:                                        ; preds = %split1, %split2, %bb1
+  %lcssa = phi i32 [ 0, %bb1 ], [ -1, %split1 ], [ -1, %split2 ]
+  %cmp2 = icmp ne i32 %lcssa, 0
+  %brmerge = or i1 %cmp1, %cmp2
+  %add = add nsw i32 %storemerge, -1
+  br i1 %brmerge, label %bb1, label %exit
+
+exit:                                      ; preds = %critedge
+  ret void
+}