[CVP] Guard against poison in common phi value transform (PR50399)

[nikic]

Summary

The common phi value transform replaces constants with values that have the same value as the constant on a given edge. However, LVI generally only provides information that is correct up to poison, so this can end up replacing a well-defined value with poison. D69442 addressed an instance of this problem by clearing poison flags on the generating instruction, which was sufficient at the time. rGa917fb89dc28 made LVI's edge value analysis slightly more powerful, and clearing poison flags is no longer sufficient.

This patch changes the transform to instead explicitly guard against a poison value instead. This should be satisfied for most cases due to a branch on poison.

Fixes https://bugs.llvm.org/show_bug.cgi?id=50399.

[uabelho]

Hi!

I've verified that this indeed solves the problem I saw in
https://bugs.llvm.org/show_bug.cgi?id=50399 .
Thanks!

[spatel]

llvm/test/Transforms/CorrelatedValuePropagation/phi-common-val.ll

142

Check my understanding (add this test?): if the sub does not have nsw, then we still allow this transform because the plain sub can not create poison and arg is not poison?

[nikic]

llvm/test/Transforms/CorrelatedValuePropagation/phi-common-val.ll

142

Yes, that's right. I've added the additional test in https://github.com/llvm/llvm-project/commit/e42636d3c1a41a9b7c5d8095ae5ef6682e26d4a2 and it does still fold for the reason you described.

[spatel]

LGTM - need to fix the miscompile regardless of whether we could salvage the existing test.

llvm/test/Transforms/CorrelatedValuePropagation/phi-common-val.ll

142

Thanks. So it's one of those awkward cases where improving wrapping analysis could actually inhibit an optimization. I don't know if we have any plans for adjusting for that sort of thing, but might be worth a code or test comment?

[nikic]

llvm/test/Transforms/CorrelatedValuePropagation/phi-common-val.ll

142

Right. Unfortunately I don't have a good idea for how to retain this optimization. What the similar select optimization in InstCombine does is this monstrosity: https://github.com/llvm/llvm-project/blob/694068d0db4378d9956fe0d3234ee0c4d353d94c/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp#L1175-L1213 We unset the nowrap flags, rerun the analysis and then either do the fold or restore the flags. I don't think something like that is feasible (or advisable) here, because it will interact with the LVI caching in a dangerous way.

That said, I don't think this is a particularly important corner case either.

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LazyValueInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
static bool simplifyCommonValuePhi(PHINode *P, LazyValueInfo *LVI,
   // the same incoming variable value.
   for (auto &IncomingConstant : IncomingConstants) {
     Constant *C = IncomingConstant.first;
     BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second);
     if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P))
       return false;
   }
 
+  // LVI only guarantees that the value matches a certain constant if the value
+  // is not poison. Make sure we don't replace a well-defined value with poison.
+  // This is usually satisfied due to a prior branch on the value.
+  if (!isGuaranteedNotToBePoison(CommonValue, nullptr, P, DT))
+    return false;
+
   // All constant incoming values map to the same variable along the incoming
-  // edges of the phi. The phi is unnecessary. However, we must drop all
-  // poison-generating flags to ensure that no poison is propagated to the phi
-  // location by performing this substitution.
-  // Warning: If the underlying analysis changes, this may not be enough to
-  //          guarantee that poison is not propagated.
-  // TODO: We may be able to re-infer flags by re-analyzing the instruction.
-  if (auto *CommonInst = dyn_cast<Instruction>(CommonValue))
-    CommonInst->dropPoisonGeneratingFlags();
+  // edges of the phi. The phi is unnecessary.
   P->replaceAllUsesWith(CommonValue);
   P->eraseFromParent();
   ++NumPhiCommon;
   return true;
 }
 
 static bool processPHI(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT,
                        const SimplifyQuery &SQ) {

llvm/test/Transforms/CorrelatedValuePropagation/phi-common-val.ll

 }
 
 ; The sub has 'nsw', so it is not safe to propagate that value along
 ; the bb2 edge because that would propagate poison to the return.
 
 define i32 @PR43802(i32 %arg) {
 ; CHECK-LABEL: @PR43802(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SUB:%.*]] = sub i32 0, [[ARG:%.*]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 0, [[ARG:%.*]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[ARG]], -2147483648
 ; CHECK-NEXT:    br i1 [[CMP]], label [[BB2:%.*]], label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    ret i32 [[SUB]]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ -2147483648, [[BB2]] ], [ [[SUB]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   %sub = sub nsw i32 0, %arg
   %cmp = icmp eq i32 %arg, -2147483648
   br i1 %cmp, label %bb2, label %bb3
 
 bb2:
   br label %bb3
 
 bb3:
   %r = phi i32 [ -2147483648, %bb2 ], [ %sub, %entry ]
   ret i32 %r
 }
 
-; TODO: Miscompile.
+; Similar to the previous case, we know that %y is always poison on the
+; entry -> join1 edge, and thus always zero or poison on the join1 -> join2
+; edge. We need to make sure that we don't replace zero with "zero or poison".
+
 define i8 @pr50399(i8 %x) {
 ; CHECK-LABEL: @pr50399(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[X:%.*]], -100
-; CHECK-NEXT:    [[Y:%.*]] = add i8 [[X]], -100
+; CHECK-NEXT:    [[Y:%.*]] = add nsw i8 [[X]], -100
 ; CHECK-NEXT:    br i1 [[CMP]], label [[JOIN1:%.*]], label [[ELSE:%.*]]
 ; CHECK:       else:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i8 [[Y]], 0
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[JOIN1]], label [[ELSE2:%.*]]
 ; CHECK:       join1:
 ; CHECK-NEXT:    br label [[JOIN2:%.*]]
 ; CHECK:       else2:
 ; CHECK-NEXT:    br label [[JOIN2]]
 ; CHECK:       join2:
-; CHECK-NEXT:    ret i8 [[Y]]
+; CHECK-NEXT:    [[PHI:%.*]] = phi i8 [ 0, [[JOIN1]] ], [ [[Y]], [[ELSE2]] ]
+; CHECK-NEXT:    ret i8 [[PHI]]
 ;
   %cmp = icmp slt i8 %x, -100
   %y = add nsw i8 %x, -100
   br i1 %cmp, label %join1, label %else
 
 else:                                               ; preds = %cond.end9
   %cmp2 = icmp eq i8 %y, 0
   br i1 %cmp2, label %join1, label %else2