[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

Value *NewGVN::findLeaderForInst(Instruction *TransInst,
   TempToBlock.erase(TransInst);
   if (MemAccess)
     TempToMemory.erase(TransInst);
   if (!E)
     return nullptr;
   auto *FoundVal = findPHIOfOpsLeader(E, OrigInst, PredBB);
   if (!FoundVal) {
     ExpressionToPhiOfOps[E].insert(OrigInst);
+    // Also force re-evaluation if any of the expressions operands change,
+    // as that could lead to a different result for the symbolic evaluation.
+    if (auto *BE = dyn_cast<BasicExpression>(E))
+      for (auto &Op : BE->operands())
+        ExpressionToPhiOfOps[createVariableOrConstant(Op)].insert(OrigInst);
     DEBUG(dbgs() << "Cannot find phi of ops operand for " << *TransInst
                  << " in block " << getBlockName(PredBB) << "\n");
     return nullptr;
   }
   if (auto *SI = dyn_cast<StoreInst>(FoundVal))
     FoundVal = SI->getValueOperand();
   return FoundVal;
 }

test/Transforms/NewGVN/pr35074-phi-of-ops-expr-operand-change-cases-change.ll

+; RUN: opt < %s -newgvn -S | FileCheck %s
+
+; CHECK-LABEL: WhileBody:
+; br i1 false, label %BoundsCheckFail275, label %BoundsCheckOk276
+; CHECK-LABEL: WhileEnd:
+
+define void @sort(i64 %.16) {
+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)