[SimplifyCFG] avoid creating unnecessary assume calls

[spatel]

Summary

We are looking at improving analysis for undef in D97244, but there is concern that extra assumptions created can counteract the benefits.

While looking at the most basic examples, it seems clear that simplifycfg is creating assumes that have no possible benefit because no uses of the incoming values remain after we reduce the control-flow. The usual dead code elimination utils don't try hard to kill assumes, so this can lead to bloat that remains through the optimizer.

This patch tries to avoid creating assumes during branch elimination if there is likely no need for them. This reverses several of the test diffs that were added with D61409, but I added some test comments to show that we do still create assumes where it would be helpful.

[lebedev.ri]

I think the fact that we are *not* creating such assumes in most of the places is a bug.
I can't really comment on the strain such assumes incur on the optimization pipeline,
but i don't expect it to be too high, and i do think that should be fixed (by assume operand bundles?)
rather than the use case be shunned into a corner and avoided.

Concretely, i would expect that this will pessimize e.g. the case where
we are operating on a function argument, we happen to not have other uses,
so we don't emit an assumption, but then we inline the function
and suddenly there are uses that would have benefitted from that knowledge,
but it has been lost by then..

[xbolva00]

Yeah, I think that assume bundles should be the thing we want here.

[spatel]

Ok - I'll abandon this. I think it's ok to try D97244. If we do hit problems, we have a link to this patch for potential solutions.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

if (auto *BI = dyn_cast<BranchInst>(TI)) {
       // or a degenerate conditional branch with matching destinations.
       if (all_of(BI->successors(),
                  [BB](auto *Successor) { return Successor == BB; })) {
         new UnreachableInst(TI->getContext(), TI);
         TI->eraseFromParent();
         Changed = true;
       } else {
         assert(BI->isConditional() && "Can't get here with an uncond branch.");
-        Value* Cond = BI->getCondition();
+        Value *Cond = BI->getCondition();
         assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
                "The destinations are guaranteed to be different here.");
+
+        // We are eliminating at least one use of the condition by erasing the
+        // conditional branch. If there are other uses of the condition or its
+        // operands, preserve information for those uses by creating an assume.
+        auto shouldCreateAssume = [](Value *Cond) {
+          if (!Cond->hasOneUse())
+            return true;
+
+          CmpInst::Predicate Pred;
+          Value *X, *Y;
+          if (match(Cond, m_Cmp(Pred, m_Value(X), m_Value(Y)))) {
+            if (!isa<Constant>(X) && !X->hasOneUse())
+              return true;
+            if (!isa<Constant>(Y) && !Y->hasOneUse())
+              return true;
+          }
+          return false;
+        };
+
         if (BI->getSuccessor(0) == BB) {
+          if (shouldCreateAssume(Cond))
             Builder.CreateAssumption(Builder.CreateNot(Cond));
           Builder.CreateBr(BI->getSuccessor(1));
         } else {
           assert(BI->getSuccessor(1) == BB && "Incorrect CFG");
+          if (shouldCreateAssume(Cond))
             Builder.CreateAssumption(Cond);
           Builder.CreateBr(BI->getSuccessor(0));
         }
         EraseTerminatorAndDCECond(BI);
         Changed = true;
       }
       Updates.push_back({DominatorTree::Delete, Predecessor, BB});
     } else if (auto *SI = dyn_cast<SwitchInst>(TI)) {
       SwitchInstProfUpdateWrapper SU(*SI);

llvm/test/Transforms/LoopVectorize/if-pred-stores.ll

 ; Track basic blocks when unrolling conditional blocks. This code used to assert
 ; because we did not update the phi nodes with the proper predecessor in the
 ; vectorized loop body.
 ; PR18724
 
 define void @bug18724(i1 %cond) {
 ; UNROLL-LABEL: @bug18724(
 ; UNROLL-NEXT:  entry:
-; UNROLL-NEXT:    [[TMP0:%.*]] = xor i1 [[COND:%.*]], true
-; UNROLL-NEXT:    call void @llvm.assume(i1 [[TMP0]])
 ; UNROLL-NEXT:    br label [[FOR_BODY14:%.*]]
 ; UNROLL:       for.body14:
 ; UNROLL-NEXT:    [[INDVARS_IV3:%.*]] = phi i64 [ [[INDVARS_IV_NEXT4:%.*]], [[FOR_INC23:%.*]] ], [ undef, [[ENTRY:%.*]] ]
 ; UNROLL-NEXT:    [[INEWCHUNKS_120:%.*]] = phi i32 [ [[INEWCHUNKS_2:%.*]], [[FOR_INC23]] ], [ undef, [[ENTRY]] ]
 ; UNROLL-NEXT:    [[ARRAYIDX16:%.*]] = getelementptr inbounds [768 x i32], [768 x i32]* undef, i64 0, i64 [[INDVARS_IV3]]
 ; UNROLL-NEXT:    [[TMP:%.*]] = load i32, i32* [[ARRAYIDX16]], align 4
 ; UNROLL-NEXT:    br i1 undef, label [[IF_THEN18:%.*]], label [[FOR_INC23]]
 ; UNROLL:       if.then18:
 ; UNROLL-NEXT:    store i32 2, i32* [[ARRAYIDX16]], align 4
 ; UNROLL-NEXT:    [[INC21:%.*]] = add nsw i32 [[INEWCHUNKS_120]], 1
 ; UNROLL-NEXT:    br label [[FOR_INC23]]
 ; UNROLL:       for.inc23:
 ; UNROLL-NEXT:    [[INEWCHUNKS_2]] = phi i32 [ [[INC21]], [[IF_THEN18]] ], [ [[INEWCHUNKS_120]], [[FOR_BODY14]] ]
 ; UNROLL-NEXT:    [[INDVARS_IV_NEXT4]] = add nsw i64 [[INDVARS_IV3]], 1
-; UNROLL-NEXT:    [[TMP1:%.*]] = trunc i64 [[INDVARS_IV3]] to i32
-; UNROLL-NEXT:    [[CMP13:%.*]] = icmp slt i32 [[TMP1]], 0
-; UNROLL-NEXT:    call void @llvm.assume(i1 [[CMP13]])
 ; UNROLL-NEXT:    br label [[FOR_BODY14]]
 ;
 ; UNROLL-NOSIMPLIFY-LABEL: @bug18724(
 ; UNROLL-NOSIMPLIFY-NEXT:  entry:
 ; UNROLL-NOSIMPLIFY-NEXT:    br label [[FOR_BODY9:%.*]]
 ; UNROLL-NOSIMPLIFY:       for.body9:
 ; UNROLL-NOSIMPLIFY-NEXT:    br i1 [[COND:%.*]], label [[FOR_INC26:%.*]], label [[FOR_BODY14_PREHEADER:%.*]]
 ; UNROLL-NOSIMPLIFY:       for.body14.preheader:

 ; UNROLL-NOSIMPLIFY-NEXT:    [[INEWCHUNKS_2_LCSSA:%.*]] = phi i32 [ [[INEWCHUNKS_2]], [[FOR_INC23]] ], [ [[BIN_RDX]], [[MIDDLE_BLOCK]] ]
 ; UNROLL-NOSIMPLIFY-NEXT:    br label [[FOR_INC26]]
 ; UNROLL-NOSIMPLIFY:       for.inc26:
 ; UNROLL-NOSIMPLIFY-NEXT:    [[INEWCHUNKS_1_LCSSA:%.*]] = phi i32 [ undef, [[FOR_BODY9]] ], [ [[INEWCHUNKS_2_LCSSA]], [[FOR_INC26_LOOPEXIT]] ]
 ; UNROLL-NOSIMPLIFY-NEXT:    unreachable
 ;
 ; VEC-LABEL: @bug18724(
 ; VEC-NEXT:  entry:
-; VEC-NEXT:    [[TMP0:%.*]] = xor i1 [[COND:%.*]], true
-; VEC-NEXT:    call void @llvm.assume(i1 [[TMP0]])
 ; VEC-NEXT:    br label [[FOR_BODY14:%.*]]
 ; VEC:       for.body14:
 ; VEC-NEXT:    [[INDVARS_IV3:%.*]] = phi i64 [ [[INDVARS_IV_NEXT4:%.*]], [[FOR_INC23:%.*]] ], [ undef, [[ENTRY:%.*]] ]
 ; VEC-NEXT:    [[INEWCHUNKS_120:%.*]] = phi i32 [ [[INEWCHUNKS_2:%.*]], [[FOR_INC23]] ], [ undef, [[ENTRY]] ]
 ; VEC-NEXT:    [[ARRAYIDX16:%.*]] = getelementptr inbounds [768 x i32], [768 x i32]* undef, i64 0, i64 [[INDVARS_IV3]]
 ; VEC-NEXT:    [[TMP:%.*]] = load i32, i32* [[ARRAYIDX16]], align 4
 ; VEC-NEXT:    br i1 undef, label [[IF_THEN18:%.*]], label [[FOR_INC23]]
 ; VEC:       if.then18:
 ; VEC-NEXT:    store i32 2, i32* [[ARRAYIDX16]], align 4
 ; VEC-NEXT:    [[INC21:%.*]] = add nsw i32 [[INEWCHUNKS_120]], 1
 ; VEC-NEXT:    br label [[FOR_INC23]]
 ; VEC:       for.inc23:
 ; VEC-NEXT:    [[INEWCHUNKS_2]] = phi i32 [ [[INC21]], [[IF_THEN18]] ], [ [[INEWCHUNKS_120]], [[FOR_BODY14]] ]
 ; VEC-NEXT:    [[INDVARS_IV_NEXT4]] = add nsw i64 [[INDVARS_IV3]], 1
-; VEC-NEXT:    [[TMP1:%.*]] = trunc i64 [[INDVARS_IV3]] to i32
-; VEC-NEXT:    [[CMP13:%.*]] = icmp slt i32 [[TMP1]], 0
-; VEC-NEXT:    call void @llvm.assume(i1 [[CMP13]])
 ; VEC-NEXT:    br label [[FOR_BODY14]]
 ;
 entry:
   br label %for.body9
 
 for.body9:
   br i1 %cond, label %for.inc26, label %for.body14
 

llvm/test/Transforms/SimplifyCFG/UnreachableEliminate.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1  -S | FileCheck %s
 
 define void @test1(i1 %C, i1* %BP) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[C:%.*]], true
-; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %C, label %T, label %F
 T:
   store i1 %C, i1* %BP
   unreachable
 F:

 
 ;; We can either convert the following control-flow to a select or remove the
 ;; unreachable control flow because of the undef store of null. Make sure we do
 ;; the latter.
 
 define void @test5(i1 %cond, i8* %ptr) {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[COND:%.*]], true
-; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
 ; CHECK-NEXT:    store i8 2, i8* [[PTR:%.*]], align 8
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %cond, label %bb1, label %bb3
 
 bb3:
   br label %bb2
bb2:
   %ptr.2 = phi i8* [ %ptr, %bb3 ], [ null, %bb1 ]
   store i8 2, i8* %ptr.2, align 8
   ret void
 }
 
 define void @test6(i1 %cond, i8* %ptr) {
 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[COND:%.*]], true
-; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
 ; CHECK-NEXT:    store i8 2, i8* [[PTR:%.*]], align 8
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %cond, label %bb1, label %bb2
 
 bb1:
   br label %bb2
bb2:
   store i8 2, i8* %ptr.2, align 8
   ret void
 }
 
 
 define i32 @test7(i1 %X) {
 ; CHECK-LABEL: @test7(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[X:%.*]], true
-; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   br i1 %X, label %if, label %else
 
 if:
   call void undef()
   br label %else
 
 else:
   %phi = phi i32 [ 0, %entry ], [ 1, %if ]
   ret i32 %phi
 }
 
 define void @test8(i1 %X, void ()* %Y) {
 ; CHECK-LABEL: @test8(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[X:%.*]], true
-; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
 ; CHECK-NEXT:    call void [[Y:%.*]]()
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %X, label %if, label %else
 
 if:
   br label %else

 
 declare i8* @fn_nonnull_noundef_arg(i8* nonnull noundef %p)
 declare i8* @fn_nonnull_arg(i8* nonnull %p)
 declare i8* @fn_noundef_arg(i8* noundef %p)
 
 define void @test9(i1 %X, i8* %Y) {
 ; CHECK-LABEL: @test9(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[X:%.*]], true
-; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
-; CHECK-NEXT:    [[TMP1:%.*]] = call i8* @fn_nonnull_noundef_arg(i8* [[Y:%.*]])
+; CHECK-NEXT:    [[TMP0:%.*]] = call i8* @fn_nonnull_noundef_arg(i8* [[Y:%.*]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %X, label %if, label %else
 
 if:
   br label %else
 
else:
   %phi = phi i8* [ %Y, %entry ], [ undef, %if ]
   call i8* @fn_noundef_arg(i8* %phi)
   ret void
 }
 
 define void @test9_null_callsite(i1 %X, i8* %Y) {
 ; CHECK-LABEL: @test9_null_callsite(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[X:%.*]], true
-; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
-; CHECK-NEXT:    [[TMP1:%.*]] = call i8* @fn_nonnull_arg(i8* noundef nonnull [[Y:%.*]])
+; CHECK-NEXT:    [[TMP0:%.*]] = call i8* @fn_nonnull_arg(i8* noundef nonnull [[Y:%.*]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %X, label %if, label %else
 
 if:
   br label %else
 
else:
   %gep = getelementptr inbounds i8, i8* %P, i64 0
   call i8* @fn_nonnull_noundef_arg(i8* %gep)
   ret void
 }
 
 define void @test9_gep_zero(i1 %X, i8* %Y) {
 ; CHECK-LABEL: @test9_gep_zero(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[X:%.*]], true
-; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8* [[Y:%.*]], i64 0
-; CHECK-NEXT:    [[TMP1:%.*]] = call i8* @fn_nonnull_noundef_arg(i8* [[GEP]])
+; CHECK-NEXT:    [[TMP0:%.*]] = call i8* @fn_nonnull_noundef_arg(i8* [[GEP]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %X, label %if, label %else
 
 if:
   br label %else
 
 else:
   %phi = phi i8* [ %Y, %entry ], [ null, %if ]
   %gep = getelementptr inbounds i8, i8* %phi, i64 0
   call i8* @fn_nonnull_noundef_arg(i8* %gep)
   ret void
 }
 
 define void @test9_gep_bitcast(i1 %X, i32* %Y) {
 ; CHECK-LABEL: @test9_gep_bitcast(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[X:%.*]], true
-; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, i32* [[Y:%.*]], i64 0
 ; CHECK-NEXT:    [[BC:%.*]] = bitcast i32* [[GEP]] to i8*
-; CHECK-NEXT:    [[TMP1:%.*]] = call i8* @fn_nonnull_noundef_arg(i8* [[BC]])
+; CHECK-NEXT:    [[TMP0:%.*]] = call i8* @fn_nonnull_noundef_arg(i8* [[BC]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %X, label %if, label %else
 
 if:
   br label %else
 

llvm/test/Transforms/SimplifyCFG/fold-branch-to-common-dest.ll

 }
 
 @f.b = external global i8, align 1
 define void @pr48450_3() {
 ; CHECK-LABEL: @pr48450_3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_COND1:%.*]]
 ; CHECK:       for.cond1:
-; CHECK-NEXT:    [[V:%.*]] = load i8, i8* @f.b, align 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[V]], 1
-; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
 ; CHECK-NEXT:    br label [[FOR_COND1]]
 ;
 entry:
   br label %for.cond1
 
 for.cond1:
   %v = load i8, i8* @f.b, align 1
   %cmp = icmp slt i8 %v, 1

llvm/test/Transforms/SimplifyCFG/simplifyUnreachable-degenerate-conditional-branch-with-matching-destinations.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -simplifycfg -simplifycfg-require-and-preserve-domtree=1 < %s | FileCheck %s
 
 @global = external global i16, align 1
 @global.1 = external global i16, align 1
 @global.2 = external global i16, align 1
 
 define void @widget() {
 ; CHECK-LABEL: @widget(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    [[I:%.*]] = load i16, i16* @global, align 1
-; CHECK-NEXT:    [[I13:%.*]] = icmp ne i16 [[I]], 0
-; CHECK-NEXT:    call void @llvm.assume(i1 [[I13]])
 ; CHECK-NEXT:    unreachable
 ;
 bb:
   %i = load i16, i16* @global, align 1
   %i13 = icmp ne i16 %i, 0
   br i1 %i13, label %bb16, label %bb14
 
 bb14:                                             ; preds = %bb

llvm/test/Transforms/SimplifyCFG/switch-range-to-icmp.ll

 }
 
 ; This would crash because we did not clean up the
 ; default block of the switch before removing the switch.
 
 define void @PR42737(i32* %a, i1 %c) {
 ; CHECK-LABEL: @PR42737(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[C:%.*]], true
-; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   br i1 %c, label %switch, label %else
 
 else:
   store i32 2, i32* %a
   br label %switch

llvm/test/Transforms/SimplifyCFG/unreachable_assume.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s
 
+; We add an assume to preserve information about %p.
+
 define i32 @assume1(i32 %p) {
 ; CHECK-LABEL: @assume1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i32 [[P:%.*]], 0
 ; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[CMP]], true
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
 ; CHECK-NEXT:    [[CALL:%.*]] = call i32 @abs(i32 [[P]])
 ; CHECK-NEXT:    ret i32 [[CALL]]
 ;
 entry:
   %cmp = icmp sle i32 %p, 0
   br i1 %cmp, label %if.then, label %if.end
 
 if.then:
   unreachable
 
 if.end:
   %call = call i32 @abs(i32 %p)
   ret i32 %call
 }
 
+; We add an assume to preserve information about %p.
 
 define i32 @assume2(i32 %p) {
 ; CHECK-LABEL: @assume2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[P:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
 ; CHECK-NEXT:    [[CALL:%.*]] = call i32 @abs(i32 [[P]])
 ; CHECK-NEXT:    ret i32 [[CALL]]