[SimplifyCFG] Look for control flow changes instead of side effects.

[tejohnson]

Summary

When passingValueIsAlwaysUndefined scans for an instruction between an
inst with a null or undef argument and its first use, it was checking
for instructions that may have side effects, which is a superset of the
instructions it intended to find (as per the comments, control flow
changing instructions that would prevent reaching the uses). Switch
to using isGuaranteedToTransferExecutionToSuccessor() instead.

Without this change, when enabling -fwhole-program-vtables, which causes
assumes to be inserted by clang, we can get different simplification
decisions. In particular, when building with instrumentation FDO it can
affect the optimizations decisions before FDO matching, leading to some
mismatches.

I had to modify d83507-knowledge-retention-bug.ll since this fix enables
more aggressive optimization of that code such that it no longer tested
the original bug it was meant to test. I removed the undef which still
provokes the original failure (confirmed by temporarily reverting the
fix) and also changed it to just invoke the passes of interest to narrow
the testing.

Similarly I needed to adjust code for UnreachableEliminate.ll to avoid
an undef which was causing the function body to get optimized away with
this fix.

[xbolva00]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6630–6631

Split?

if (i == I->getParent()->end())

return false;

[xbolva00]

Makes sense. I added more potentional reviewers.

[nikic]

I believe you're looking for isGuaranteedToTransferExecutionToSuccessor() here. We don't actually care whether there are side-effects, it only matters whether we are guaranteed to reach the UB.

[tejohnson]

In D101507#2726052, @nikic wrote:

I believe you're looking for isGuaranteedToTransferExecutionToSuccessor() here. We don't actually care whether there are side-effects, it only matters whether we are guaranteed to reach the UB.

Ah great, switched to using that. This necessitating adjusting one test that otherwise got optimized away with the change.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6630–6631

Good idea, done.

[tejohnson]

Address comments.

[nikic]

LGTM, summary needs an update though.

llvm/test/Transforms/PhaseOrdering/d83507-knowledge-retention-bug.ll

3

Would it be possible to instead adjust the test to have a non-undef IV?

[tejohnson]

In D101507#2728127, @nikic wrote:

LGTM, summary needs an update though.

Ack. fixing momentarily.

llvm/test/Transforms/PhaseOrdering/d83507-knowledge-retention-bug.ll

3

Indeed, I removed the undef and the test still works (confirmed by temporarily reverting its fix again). I went ahead and left my change to only invoke the 2 passes of interest though - it seems like this is probably better to avoid the test being affected by future changes to various unrelated optimization passes.

[tejohnson]

Update test

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

if (C->isNullValue() || isa<UndefValue>(C)) {
     // Only look at the first use, avoid hurting compile time with long uselists
     User *Use = *I->user_begin();
 
     // Now make sure that there are no instructions in between that can alter
     // control flow (eg. calls)
     for (BasicBlock::iterator
              i = ++BasicBlock::iterator(I),
              UI = BasicBlock::iterator(dyn_cast<Instruction>(Use));
-         i != UI; ++i)
-      if (i == I->getParent()->end() || i->mayHaveSideEffects())
+         i != UI; ++i) {
+      if (i == I->getParent()->end())
         return false;
+      if (!isGuaranteedToTransferExecutionToSuccessor(&*i))
+        return false;
+    }
 
     // Look through GEPs. A load from a GEP derived from NULL is still undefined
     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Use))
       if (GEP->getPointerOperand() == I) {
         if (!GEP->isInBounds() || !GEP->hasAllZeroIndices())
           PtrValueMayBeModified = true;
         return passingValueIsAlwaysUndefined(V, GEP, PtrValueMayBeModified);
       }

llvm/test/CodeGen/Thumb2/LowOverheadLoops/while-loops.ll

if.end:                                           ; preds = %if.end.loopexit, %for.body
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 }
 
 declare <4 x i1> @llvm.arm.mve.vctp32(i32)
 declare i32 @llvm.arm.mve.addv.predicated.v4i32.v4i1(<4 x i32>, i32, <4 x i1>)
 
 
 ; Long test that was spilling lr between t2LoopDec and End
-define dso_local i32 @b(i32* %c, i32 %d, i32 %e) "frame-pointer"="all" {
+define dso_local i32 @b(i32* %c, i32 %d, i32 %e, i32* %n) "frame-pointer"="all" {
 ; CHECK-LABEL: b:
 ; CHECK:       @ %bb.0: @ %entry
 ; CHECK-NEXT:    .save {r4, r5, r6, r7, lr}
 ; CHECK-NEXT:    push {r4, r5, r6, r7, lr}
 ; CHECK-NEXT:    .setfp r7, sp, #12
 ; CHECK-NEXT:    add r7, sp, #12
 ; CHECK-NEXT:    .save {r8, r9, r10, r11}
 ; CHECK-NEXT:    push.w {r8, r9, r10, r11}
-; CHECK-NEXT:    .pad #8
-; CHECK-NEXT:    sub sp, #8
+; CHECK-NEXT:    .pad #12
+; CHECK-NEXT:    sub sp, #12
 ; CHECK-NEXT:    wls lr, r1, .LBB2_3
 ; CHECK-NEXT:  @ %bb.1: @ %while.body.preheader
-; CHECK-NEXT:    adds r1, r0, #4
-; CHECK-NEXT:    mvn r3, #1
-; CHECK-NEXT:    @ implicit-def: $r9
-; CHECK-NEXT:    @ implicit-def: $r10
+; CHECK-NEXT:    mov r4, r2
+; CHECK-NEXT:    adds r2, r3, #4
+; CHECK-NEXT:    add.w r9, r0, #4
+; CHECK-NEXT:    mvn r11, #1
 ; CHECK-NEXT:    @ implicit-def: $r6
-; CHECK-NEXT:    @ implicit-def: $r4
-; CHECK-NEXT:    str r2, [sp] @ 4-byte Spill
+; CHECK-NEXT:    @ implicit-def: $r12
+; CHECK-NEXT:    str r4, [sp] @ 4-byte Spill
 ; CHECK-NEXT:  .LBB2_2: @ %while.body
 ; CHECK-NEXT:    @ =>This Inner Loop Header: Depth=1
-; CHECK-NEXT:    str r1, [sp, #4] @ 4-byte Spill
-; CHECK-NEXT:    ldr r1, [sp, #4] @ 4-byte Reload
-; CHECK-NEXT:    ldr.w r8, [r10]
-; CHECK-NEXT:    ldr r1, [r1, #-4]
-; CHECK-NEXT:    mul r11, r8, r0
-; CHECK-NEXT:    adds r0, #4
-; CHECK-NEXT:    mul r1, r1, r9
-; CHECK-NEXT:    adds.w r12, r1, #-2147483648
+; CHECK-NEXT:    ldr r1, [r9, #-4]
+; CHECK-NEXT:    ldr.w r10, [r2]
+; CHECK-NEXT:    str r0, [sp, #4] @ 4-byte Spill
+; CHECK-NEXT:    muls r1, r3, r1
+; CHECK-NEXT:    adds.w r8, r1, #-2147483648
 ; CHECK-NEXT:    asr.w r5, r1, #31
-; CHECK-NEXT:    add.w r1, r11, #-2147483648
-; CHECK-NEXT:    adc r5, r5, #0
-; CHECK-NEXT:    asrl r12, r5, r1
-; CHECK-NEXT:    smull r2, r1, r8, r12
-; CHECK-NEXT:    lsll r2, r1, #30
-; CHECK-NEXT:    asrs r5, r1, #31
-; CHECK-NEXT:    mov r2, r1
-; CHECK-NEXT:    lsll r2, r5, r8
-; CHECK-NEXT:    lsll r2, r5, #30
-; CHECK-NEXT:    ldrd r2, r11, [r3]
+; CHECK-NEXT:    adc r1, r5, #0
+; CHECK-NEXT:    mul r5, r10, r0
+; CHECK-NEXT:    mov r0, r2
+; CHECK-NEXT:    ldr.w r2, [r11, #4]
+; CHECK-NEXT:    str r2, [sp, #8] @ 4-byte Spill
+; CHECK-NEXT:    ldr r2, [sp, #8] @ 4-byte Reload
+; CHECK-NEXT:    add.w r5, r5, #-2147483648
+; CHECK-NEXT:    asrl r8, r1, r5
+; CHECK-NEXT:    smull r4, r5, r10, r8
+; CHECK-NEXT:    lsll r4, r5, #30
 ; CHECK-NEXT:    asrs r1, r5, #31
-; CHECK-NEXT:    mov r12, r5
-; CHECK-NEXT:    asrs r5, r4, #31
-; CHECK-NEXT:    muls r2, r6, r2
-; CHECK-NEXT:    adds r2, #2
-; CHECK-NEXT:    lsll r12, r1, r2
-; CHECK-NEXT:    ldr r2, [sp, #4] @ 4-byte Reload
-; CHECK-NEXT:    add.w r1, r12, #-2147483648
-; CHECK-NEXT:    ldr r2, [r2]
-; CHECK-NEXT:    mul r2, r2, r9
-; CHECK-NEXT:    add.w r9, r9, #4
-; CHECK-NEXT:    adds r4, r4, r2
-; CHECK-NEXT:    adc.w r2, r5, r2, asr #31
-; CHECK-NEXT:    adds.w r5, r4, #-2147483648
-; CHECK-NEXT:    smull r6, r4, r11, r6
-; CHECK-NEXT:    adc r2, r2, #0
-; CHECK-NEXT:    asrs r5, r2, #31
-; CHECK-NEXT:    subs r6, r2, r6
+; CHECK-NEXT:    mov r4, r5
+; CHECK-NEXT:    lsll r4, r1, r10
+; CHECK-NEXT:    lsll r4, r1, #30
+; CHECK-NEXT:    ldr.w r4, [r11]
+; CHECK-NEXT:    asrs r5, r1, #31
+; CHECK-NEXT:    mov r8, r1
+; CHECK-NEXT:    muls r4, r6, r4
+; CHECK-NEXT:    adds r4, #2
+; CHECK-NEXT:    lsll r8, r5, r4
+; CHECK-NEXT:    ldr r4, [r9], #4
+; CHECK-NEXT:    asr.w r5, r12, #31
+; CHECK-NEXT:    add.w r8, r8, #-2147483648
+; CHECK-NEXT:    muls r4, r3, r4
+; CHECK-NEXT:    adds r3, #4
+; CHECK-NEXT:    adds.w r1, r12, r4
+; CHECK-NEXT:    adc.w r5, r5, r4, asr #31
+; CHECK-NEXT:    smull r6, r4, r2, r6
+; CHECK-NEXT:    adds.w r1, r1, #-2147483648
+; CHECK-NEXT:    adc r1, r5, #0
+; CHECK-NEXT:    mov r2, r0
+; CHECK-NEXT:    asrs r5, r1, #31
+; CHECK-NEXT:    subs r6, r1, r6
 ; CHECK-NEXT:    sbcs r5, r4
 ; CHECK-NEXT:    adds.w r6, r6, #-2147483648
 ; CHECK-NEXT:    adc r5, r5, #0
-; CHECK-NEXT:    asrl r6, r5, r1
-; CHECK-NEXT:    movs r1, #2
+; CHECK-NEXT:    asrl r6, r5, r8
 ; CHECK-NEXT:    lsrl r6, r5, #2
-; CHECK-NEXT:    str r6, [r1]
-; CHECK-NEXT:    ldr r1, [r3], #-4
-; CHECK-NEXT:    mls r1, r1, r8, r2
-; CHECK-NEXT:    adds.w r4, r1, #-2147483648
-; CHECK-NEXT:    asr.w r2, r1, #31
-; CHECK-NEXT:    adc r1, r2, #0
-; CHECK-NEXT:    ldr r2, [sp] @ 4-byte Reload
-; CHECK-NEXT:    lsrl r4, r1, #2
-; CHECK-NEXT:    rsbs r1, r4, #0
-; CHECK-NEXT:    str r1, [r10, #-4]
-; CHECK-NEXT:    add.w r10, r10, #4
-; CHECK-NEXT:    str r1, [r2]
-; CHECK-NEXT:    ldr r1, [sp, #4] @ 4-byte Reload
-; CHECK-NEXT:    adds r1, #4
+; CHECK-NEXT:    movs r5, #2
+; CHECK-NEXT:    str r6, [r5]
+; CHECK-NEXT:    ldr r5, [r11], #-4
+; CHECK-NEXT:    mls r1, r5, r10, r1
+; CHECK-NEXT:    adds.w r12, r1, #-2147483648
+; CHECK-NEXT:    asr.w r4, r1, #31
+; CHECK-NEXT:    adc r1, r4, #0
+; CHECK-NEXT:    ldrd r4, r0, [sp] @ 8-byte Folded Reload
+; CHECK-NEXT:    lsrl r12, r1, #2
+; CHECK-NEXT:    rsb.w r1, r12, #0
+; CHECK-NEXT:    adds r0, #4
+; CHECK-NEXT:    str r1, [r4]
+; CHECK-NEXT:    str r1, [r2, #-4]
+; CHECK-NEXT:    adds r2, #4
 ; CHECK-NEXT:    le lr, .LBB2_2
 ; CHECK-NEXT:  .LBB2_3: @ %while.end
-; CHECK-NEXT:    add sp, #8
+; CHECK-NEXT:    add sp, #12
 ; CHECK-NEXT:    pop.w {r8, r9, r10, r11}
 ; CHECK-NEXT:    pop {r4, r5, r6, r7, pc}
 entry:
   %0 = inttoptr i32 %e to i32*
   %tobool.not70 = icmp eq i32 %d, 0
   br i1 %tobool.not70, label %while.end, label %while.body
 
 while.body:                                       ; preds = %entry, %while.body
   %p.077 = phi i32* [ %incdec.ptr22, %while.body ], [ inttoptr (i32 2 to i32*), %entry ]
   %c.addr.076 = phi i32* [ %incdec.ptr1, %while.body ], [ %c, %entry ]
-  %n.075 = phi i32* [ %incdec.ptr43, %while.body ], [ undef, %entry ]
+  %n.075 = phi i32* [ %incdec.ptr43, %while.body ], [ %n, %entry ]
   %m.074 = phi i32 [ %conv35, %while.body ], [ undef, %entry ]
   %d.addr.073 = phi i32 [ %dec, %while.body ], [ %d, %entry ]
   %h.072 = phi i32 [ %conv41, %while.body ], [ undef, %entry ]
   %incdec.ptr43 = getelementptr inbounds i32, i32* %n.075, i32 1
   %1 = ptrtoint i32* %n.075 to i32
   %2 = load i32, i32* %incdec.ptr43, align 4
   %3 = load i32, i32* %c.addr.076, align 4
   %mul = mul nsw i32 %3, %1

llvm/test/Transforms/PhaseOrdering/d83507-knowledge-retention-bug.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -O1                   -enable-knowledge-retention -S < %s  | FileCheck %s
-; RUN: opt -passes='default<O1>' -enable-knowledge-retention -S < %s  | FileCheck %s
+; RUN: opt -loop-rotate -instcombine -enable-knowledge-retention -S < %s  | FileCheck %s
+; RUN: opt -passes='loop(loop-rotate),instcombine' -enable-knowledge-retention -S < %s  | FileCheck %s
 
 %0 = type { %0* }
 
-define %0* @f1() local_unnamed_addr {
+define %0* @f1(%0* %i0) local_unnamed_addr {
 ; CHECK-LABEL: @f1(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:         br label [[BB3:%.*]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    [[I1:%.*]] = phi %0* [ [[I5:%.*]], [[BB3]] ], [ undef, [[BB:%.*]] ]
+; CHECK-NEXT:    [[I1:%.*]] = phi %0* [ %i0, [[BB:%.*]] ], [ [[I5:%.*]], [[BB3]] ]
 ; CHECK-NEXT:    call void @llvm.assume(i1 true) [ "nonnull"(%0* [[I1]]) ]
 ; CHECK-NEXT:    [[I4:%.*]] = getelementptr inbounds [[TMP0:%.*]], %0* [[I1]], i64 0, i32 0
 ; CHECK-NEXT:    [[I5]] = load %0*, %0** [[I4]], align 8
 ; CHECK-NEXT:    [[I2:%.*]] = icmp eq %0* [[I5]], null
 ; CHECK-NEXT:    br i1 [[I2]], label [[BB6:%.*]], label [[BB3]]
 ; CHECK:       bb6:
 ; CHECK-NEXT:    ret %0* undef
 ;
 bb:
   br label %bb1
 
 bb1:
-  %i = phi %0* [ undef, %bb ], [ %i5, %bb3 ]
+  %i = phi %0* [ %i0, %bb ], [ %i5, %bb3 ]
   %i2 = icmp eq %0* %i, null
   br i1 %i2, label %bb6, label %bb3
 
 bb3:
   call void @llvm.assume(i1 true) [ "nonnull"(%0* %i) ]
   %i4 = getelementptr inbounds %0, %0* %i, i64 0, i32 0
   %i5 = load %0*, %0** %i4, align 8
   br label %bb1
 
 bb6:
   ret %0* undef
 }
 
 declare void @llvm.assume(i1)

llvm/test/Transforms/SimplifyCFG/UnreachableEliminate.ll

bb1:
   br label %bb2
 
 bb2:
   %ptr.2 = phi i8* [ %ptr, %bb3 ], [ null, %bb1 ]
   store i8 2, i8* %ptr.2, align 8
   ret void
 }
 
+declare void @llvm.assume(i1)
+declare i1 @llvm.type.test(i8*, metadata) nounwind readnone
+
+;; Same as the above test but make sure the unreachable control flow is still
+;; removed in the presence of a type test / assume sequence.
+
+define void @test5_type_test_assume(i1 %cond, i8* %ptr, [3 x i8*]* %vtable) {
+; CHECK-LABEL: @test5_type_test_assume(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[COND:%.*]], true
+; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
+; CHECK-NEXT:    [[VTABLE:%.*]] = bitcast [3 x i8*]* %vtable to i8*
+; CHECK-NEXT:    [[P:%.*]] = call i1 @llvm.type.test(i8* [[VTABLE]], metadata !"foo")
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[P]])
+; 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
+
+bb1:
+  br label %bb2
+
+bb2:
+  %ptr.2 = phi i8* [ %ptr, %bb3 ], [ null, %bb1 ]
+  %vtablei8 = bitcast [3 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"foo")
+  tail call void @llvm.assume(i1 %p)
+  store i8 2, i8* %ptr.2, align 8
+  ret void
+}
+
 define void @test5_no_null_opt(i1 %cond, i8* %ptr) #0 {
 ; CHECK-LABEL: @test5_no_null_opt(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[PTR_2:%.*]] = select i1 [[COND:%.*]], i8* null, i8* [[PTR:%.*]]
 ; CHECK-NEXT:    store i8 2, i8* [[PTR_2]], align 8
 ; CHECK-NEXT:    ret void
 ;
 entry: