[NewGVN] Add ops as dependency if we cannot find a leader for ValueOp.

[fhahn]

Summary

If those operands change, we might find a leader for ValueOp, which
could enable new phi-of-op creation.

This fixes a case where we missed creating a phi-of-ops node. With
this patch, bootstrapping clang/llvm works with -enable-newgvn, whereas
without it, the "value changed after iteration" assertion is triggered.

[• dberlin]

This is definitely not right, unfortunately.

This is already taken care of by code below:

// 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)
    Deps.insert(Op);
} else if (auto *ValuePHI = RealToTemp.lookup(Op)) {
  if (getBlockForValue(ValuePHI) == PHIBlock)
    Op = ValuePHI->getIncomingValueForBlock(PredBB);
}

By the end of this loop, Deps should contain the set of operands we depend on.

Note that the only values that need to be added are phis, because everything else should be the same as the original IR, and *already* a user. You do not have to represent dependencies that are already represented in the IR

IE
given

1 foo = something
2 b = use foo

2 will already be re-evaluated if foo changes, it's already a user of 1's result.

If foo is a phi we translate, *then* we have to add it to someone's users because it is different than the original IR.

I would suggest starting by checking for the invariants you expect at the end of makePossiblePhiOfOps and understanding where they are not being met.

[fhahn]

Will do, thanks!

[fhahn]

Updated to add additional users for the translated operands of the current ValueOp, if we cannot find a leader for the ValueOp.

If those operands change, we might find a leader for ValueOp, which
could enable new phi-of-op creation.

This fixes a case where we missed creating a phi-of-ops node. With
this patch, bootstrapping clang/llvm works with -enable-newgvn, whereas
without it, the "value changed after iteration" assertion is triggered.

This is based on @dberlin's patch shared for D43865, because it is
slightly clearer what's going on, but it does not really depend on it.

[fhahn]

ping. Does this make sense?

[fhahn]

ping

[llvm-commits]

Sorry, i'll stare at this again.

• msg-18854-420.txt162 BDownload

[• dberlin]

Sorry for the delay. I've mostly convinced myself this isn't wrong, so let's go with it for now.

[fhahn]

Thanks! Rebased on ToT without D43865.

[fhahn]

Thank you very much for all the feedback & patience :)

lib/Transforms/Scalar/NewGVN.cpp

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)
-              Deps.insert(Op);
+              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)
+        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);
+
           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));
       }
 

test/Transforms/NewGVN/pr35074.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -newgvn -S | FileCheck %s
+
+define void @sort(i64 %.16) {
+; CHECK-LABEL: @sort(
+; CHECK-NEXT:  Entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = extractvalue { i64, i1 } undef, 0
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i64 [[TMP0]], 2
+; CHECK-NEXT:    br i1 undef, label [[DIVZEROFAIL2_I:%.*]], label [[WHILEBODY_LR_PH:%.*]]
+; CHECK:       DivZeroFail2.i:
+; CHECK-NEXT:    unreachable
+; CHECK:       WhileBody.lr.ph:
+; CHECK-NEXT:    [[TMP2:%.*]] = udiv i64 [[DOT16:%.*]], [[TMP1]]
+; CHECK-NEXT:    br label [[WHILEBODY:%.*]]
+; CHECK:       WhileBody:
+; CHECK-NEXT:    [[ITERATOR:%.*]] = phi i64 [ 0, [[WHILEBODY_LR_PH]] ], [ [[TMP6:%.*]], [[BOUNDSCHECKOK276:%.*]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 [[ITERATOR]], i64 [[TMP2]])
+; CHECK-NEXT:    [[TMP4:%.*]] = extractvalue { i64, i1 } [[TMP3]], 0
+; CHECK-NEXT:    [[TMP5:%.*]] = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 [[TMP4]], i64 1)
+; CHECK-NEXT:    [[TMP6]] = extractvalue { i64, i1 } [[TMP5]], 0
+; CHECK-NEXT:    br i1 false, label [[BOUNDSCHECKFAIL275:%.*]], label [[BOUNDSCHECKOK276]]
+; CHECK:       WhileEnd:
+; CHECK-NEXT:    ret void
+; CHECK:       BoundsCheckFail275:
+; CHECK-NEXT:    unreachable
+; CHECK:       BoundsCheckOk276:
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp ult i64 [[TMP6]], [[DOT16]]
+; CHECK-NEXT:    br i1 [[TMP7]], label [[WHILEBODY]], label [[WHILEEND:%.*]]
+;
+Entry:
+  %0 = extractvalue { i64, i1 } undef, 0
+  %1 = lshr i64 %0, 2
+  br i1 undef, label %DivZeroFail2.i, label %WhileBody.lr.ph
+
+DivZeroFail2.i:                                   ; preds = %Entry
+  unreachable
+
+WhileBody.lr.ph:                                  ; preds = %Entry
+  %2 = udiv i64 %.16, %1
+  br label %WhileBody
+
+WhileBody:                                        ; preds = %BoundsCheckOk276, %WhileBody.lr.ph
+  %iterator = phi i64 [ 0, %WhileBody.lr.ph ], [ %6, %BoundsCheckOk276 ]
+  %3 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %iterator, i64 %2)
+  %4 = extractvalue { i64, i1 } %3, 0
+  %5 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %4, i64 1)
+  %6 = extractvalue { i64, i1 } %5, 0
+  %7 = icmp ugt i64 %iterator, %.16
+  br i1 %7, label %BoundsCheckFail275, label %BoundsCheckOk276
+
+WhileEnd:                                         ; preds = %BoundsCheckOk276
+  ret void
+
+BoundsCheckFail275:                               ; preds = %WhileBody
+  unreachable
+
+BoundsCheckOk276:                                 ; preds = %WhileBody
+  %8 = icmp ult i64 %6, %.16
+  br i1 %8, label %WhileBody, label %WhileEnd
+}
+
+declare { i64, i1 } @llvm.uadd.with.overflow.i64(i64, i64)