[CVP] prevent propagating poison when substituting edge values into a phi (PR43802)

[spatel]

Summary

This phi simplification transform was added with:
D45448

However as shown in PR43802:
https://bugs.llvm.org/show_bug.cgi?id=43802

...we must be careful not to propagate poison when we do the substitution. There might be some more complicated analysis possible to retain the overflow flag, but it should always be safe and easy to drop flags (we have similar behavior in instcombine and other passes).

[nikic]

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

201

I don't think this is sufficient, as poison might come from an earlier instruction CommonValue depends on.

[nikic]

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

201

After looking at the getEdgeValueLocal() implementation, it looks like this should be sufficient after all. The reasoning along the lines of "What value does Y=f(X) given X==C" is only performed for direct users of X.

[nikic]

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

201

If any flags are dropped, processBinOp() should be called here to attempt to re-infer them.

[lebedev.ri]

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

201

I think it may be good to migrate to worklist-based solution.
I'm guessing rerunning CVP until done would come with double the time impact and little to no benefits.

[nlopes]

LGTM

[nikic]

I initially thought that there might be a cache invalidation problem here, because we recently started to take nowrap flags into account when computing ranges, and we might end up reasoning based on the no longer present nowrap flags. In particular I had something like this in mind:

efine i1 @test(i32 %arg) {
entry:
  %add = add nuw i32 %arg, 1
  %cmp = icmp eq i32 %arg, -1
  br i1 %cmp, label %bb2, label %bb3

bb2:
  br label %bb3

bb3:
  %r = phi i32 [ 0, %bb2 ], [ %add, %entry ]
  %c = icmp eq i32 %r, 0
  ret i1 %c
}

However, it seems like the same LVI analysis that determines the value of %add on the entry edge here also results in the range of %add in bb3 to be calculated as the full range (rather than the full range without zero), so it ends up working out in the end.

This all seems pretty fragile and there might be issues in the future if LVI gets more powerful, but I guess that for now this is fine.

[spatel]

In D69442#1722258, @nikic wrote:

This all seems pretty fragile and there might be issues in the future if LVI gets more powerful, but I guess that for now this is fine.

I agree, and thanks for looking further into this. I'll leave a TODO comment about this as well as trying to re-infer the flags.

[spatel]

(marking as accepted based on earlier LGTM)

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

static bool simplifyCommonValuePhi(PHINode *P, LazyValueInfo *LVI,
   for (auto &IncomingConstant : IncomingConstants) {
     Constant *C = IncomingConstant.first;
     BasicBlock *IncomingBB = P->getIncomingBlock(IncomingConstant.second);
     if (C != LVI->getConstantOnEdge(CommonValue, IncomingBB, ToBB, P))
       return false;
   }
 
   // All constant incoming values map to the same variable along the incoming
-  // edges of the phi. The phi is unnecessary.
+  // 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();
   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

else:
   store i32 %add, i32* %b
   br label %return
 
 return:
   %r = phi i8* [ %ptr, %else ], [ null, %entry ]
   ret i8* %r
 }
 
-; FIXME:
 ; 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 nsw i32 0, [[ARG:%.*]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub 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]]
 ;
 entry: