[InstCombine] Remove known bits constant folding

[nikic]

Summary

If ExpensiveCombines is enabled (which is the case with -O3 on the legacy PM and always on the new PM), InstCombine tries to compute the known bits of all instructions in the hope that all bits end up being known. This is the most expensive individual part of InstCombine.

How effective is it? If we add some statistics on how often the constant folding succeeds and how many KnownBits calculations are performed and run test-suite we get:

"instcombine.NumConstPropKnownBits": 642,
"instcombine.NumConstPropKnownBitsComputed": 18744965,

In other words, we get one fold for every 30000 KnownBits calculations. However, the truth is actually much worse: Currently, known bits are computed before performing other folds, so there is a high chance that cases that get folded by known bits would also have been handled by other folds.

What happens if we compute known bits after all other folds (hacky implementation: https://gist.github.com/nikic/751f25b3b9d9e0860db5dde934f70f46)?

"instcombine.NumConstPropKnownBits": 0,
"instcombine.NumConstPropKnownBitsComputed": 18105547,

So it turns out despite doing 18 million known bits calculations, the known bits fold does not do anything useful on test-suite. I was originally planning to move this into AggressiveInstCombine so it only runs once in the pipeline, but seeing this, I think we're better off removing it entirely.

As this is the only use of the "expensive combines" mechanism, it may be removed afterwards, but I'll leave that to a separate patch.

[nikic]

test/Transforms/InstCombine/all-bits-shift.ll

36

I believe this test case was the original motivation for having this fold.

However, I thinks this should be handled by InstCombineSimplifyDemanded, which we invoke in cases where we have a reasonable expectation of either demanded bits or known bits simplifications to occur (such as an "and" root, as is the case here). SimplifyDemanded currently doesn't handle this case due to what looks like an implementation bug to me: While normally SimplifyDemanded computes known bits for instructions it doesn't handle itself, it does not do so for some instructions it only partially handles (e.g. it handles a constant shift amount, but does not compute known bits if the shift amount is not constant).

test/Transforms/InstCombine/assume.ll

340

I'm not sure we really need to do anything about this, I think it's only important that we have an assume(false) here, and SimplifyCFG will deal with the rest.

If we do want to improve on this, we could convert assume(false) into store undef (the InstCombine UB pattern) and then remove all instructions after store undef.

test/Transforms/InstCombine/expensive-combines.ll

14

We're missing a fold to replace call with returned attribute to the returned argument. Known bits calculation handles the particular case where the operand is constant, but non-constant operands are not handled at all right now.

test/Transforms/InstCombine/out-of-bounds-indexes.ll

10

This is an improvement.

test/Transforms/InstCombine/phi-shifts.ll

13

This is an improvement.

[jdoerfert]

test/Transforms/InstCombine/assume.ll

340

Can't we replace the UB instruction with unreachable?

[nikic]

test/Transforms/InstCombine/assume.ll

340

InstCombine preserves CFG, so it's not possible to use unreachable directly. Instead we need to use UB patterns understood by SimplifyCFG (assume false is one of them), which will convert them to proper unreachable.

[lebedev.ri]

Rebase this after fixes (if any) have landed?

This is the most expensive individual part of InstCombine.

That is an interesting statement.
It would be good to have some perf numbers here.

Do we do this fold somewhere else in the pipeline?

[nikic]

Rebase over D75804 and D75815.

[nikic]

@lebedev.ri Finally got around to implementing some compile-time testing infrastructure today, here's some numbers (in terms of instructions retired) for this change:

Basically this is a 1-2% end-to-end improvement for -O3 compile-times.

[lebedev.ri]

In D75801#1922970, @nikic wrote:

@lebedev.ri Finally got around to implementing some compile-time testing infrastructure today, here's some numbers (in terms of instructions retired) for this change:

Basically this is a 1-2% end-to-end improvement for -O3 compile-times.

Thank you, so this does indeed have some measurable effect.
Sounds justified then.

In D75801#1912306, @lebedev.ri wrote:

Do we do this fold somewhere else in the pipeline?

?
Do we believe CVP/SCCP/??? will cover all the possible cases?

[spatel]

In D75801#1922970, @nikic wrote:

@lebedev.ri Finally got around to implementing some compile-time testing infrastructure today, here's some numbers (in terms of instructions retired) for this change:

Basically this is a 1-2% end-to-end improvement for -O3 compile-times.

http://llvm-compile-time-tracker.com/?config=O3&stat=wall-time
That looks great!
Is that end-to-end time for the entire compile or just 'opt -O3'?

[nikic]

In D75801#1923012, @lebedev.ri wrote:

In D75801#1912306, @lebedev.ri wrote:

Do we do this fold somewhere else in the pipeline?

?
Do we believe CVP/SCCP/??? will cover all the possible cases?

I believe this should be covered by two vectors: First, by known bits calculation as part of InstCombineSimplifyDemanded. We don't call this for literally everything, but it handles all the cases that are likely to be fully known via known bits (bitwise ops and shifts as root instructions). Second, we have the same known bits optimization as here also as part of SimplifyInstruction. That means we already perform this in all places that use that high-level interface (e.g. it happens during inlining). I do want to get rid of that known bits call as well, but I think it is the reason why the InstCombine fold triggers exactly zero times on test-suite.

In D75801#1926700, @spatel wrote:

http://llvm-compile-time-tracker.com/?config=O3&stat=wall-time
That looks great!
Is that end-to-end time for the entire compile or just 'opt -O3'?

Those are end-to-end times. Wall time is a bit too noisy to be really useful, so I tend to look at instructions, which is a reasonable proxy, and accurate to within 0.1% for most benchmarks.

test/Analysis/ValueTracking/known-signbit-shift.ll

46 ↗

(On Diff #249166)

I missed these Analysis test changes before. The shl here is poison because we know it wraps based on known bits. This optimization gets lost now.

I could add it back explicitly (and better, by returning undef rather than zero) like this: https://gist.github.com/nikic/29135f304f7cf9de6d18dff7ca12659a

I'm not sure whether that's worthwhile though, it seems that these tests are more about not crashing due to conflicting known bits than anything else.

[lebedev.ri]

SGTM, but i'll defer to @spatel.

test/Analysis/ValueTracking/known-signbit-shift.ll

46 ↗

(On Diff #249166)

This still seems like worthwhile fold.

[nikic]

test/Analysis/ValueTracking/known-signbit-shift.ll

46 ↗

(On Diff #249166)

I've opened D76489 to address the reason why this difference exists in the first place (SimplifyDemanded produces a less good known bits result). We could still do a better overflow detection on top of that, but at least this removes the gap to what we currently do.

[spatel]

Please update after D76489.
If we're going to defer the removal of ExpensiveCombines to a follow-on NFC patch, add a FIXME note in this patch near its definition to indicate that it is deprecated/useless (just in case the follow-on doesn't happen immediately).

[nikic]

Rebase and add FIXME.

[spatel]

LGTM

lib/Transforms/InstCombine/InstructionCombining.cpp

if (!I->use_empty() &&
         ++NumConstProp;
         if (isInstructionTriviallyDead(I, &TLI))
           eraseInstFromFunction(*I);
         MadeIRChange = true;
         continue;
       }
     }
 
-    // In general, it is possible for computeKnownBits to determine all bits in
-    // a value even when the operands are not all constants.
-    Type *Ty = I->getType();
-    if (ExpensiveCombines && !I->use_empty() && Ty->isIntOrIntVectorTy()) {
-      KnownBits Known = computeKnownBits(I, /*Depth*/0, I);
-      if (Known.isConstant()) {
-        Constant *C = ConstantInt::get(Ty, Known.getConstant());
-        LLVM_DEBUG(dbgs() << "IC: ConstFold (all bits known) to: " << *C
-                          << " from: " << *I << '\n');
-
-        // Add operands to the worklist.
-        replaceInstUsesWith(*I, C);
-        ++NumConstProp;
-        if (isInstructionTriviallyDead(I, &TLI))
-          eraseInstFromFunction(*I);
-        MadeIRChange = true;
-        continue;
-      }
-    }
-
     // See if we can trivially sink this instruction to a successor basic block.
     if (EnableCodeSinking && I->hasOneUse()) {
       BasicBlock *BB = I->getParent();
       Instruction *UserInst = cast<Instruction>(*I->user_begin());
       BasicBlock *UserParent;
 
       // Get the block the use occurs in.
       if (PHINode *PN = dyn_cast<PHINode>(UserInst))

test/Transforms/InstCombine/all-bits-shift.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine -expensive-combines=0 < %s | FileCheck %s --check-prefixes=CHECK,EXPENSIVE-OFF
 ; RUN: opt -S -instcombine -expensive-combines=1 < %s | FileCheck %s --check-prefixes=CHECK,EXPENSIVE-ON
 target datalayout = "E-m:e-i64:64-n32:64"
 target triple = "powerpc64-unknown-linux-gnu"
 
 @d = global i32 15, align 4
 @b = global i32* @d, align 8
 @a = common global i32 0, align 4
 
 ; Check that both InstCombine and InstSimplify can use computeKnownBits to
 ; realize that:
 ;   ((2072 >> (L == 0)) >> 7) & 1
 ; is always zero.
 define signext i32 @main() #1 {
-; EXPENSIVE-OFF-LABEL: @main(
-; EXPENSIVE-OFF-NEXT:  entry:
-; EXPENSIVE-OFF-NEXT:    [[TMP0:%.*]] = load i32*, i32** @b, align 8
-; EXPENSIVE-OFF-NEXT:    [[TMP1:%.*]] = load i32, i32* @a, align 4
-; EXPENSIVE-OFF-NEXT:    [[LNOT:%.*]] = icmp eq i32 [[TMP1]], 0
-; EXPENSIVE-OFF-NEXT:    [[LNOT_EXT:%.*]] = zext i1 [[LNOT]] to i32
-; EXPENSIVE-OFF-NEXT:    [[SHR_I:%.*]] = lshr i32 2072, [[LNOT_EXT]]
-; EXPENSIVE-OFF-NEXT:    [[CALL_LOBIT:%.*]] = lshr i32 [[SHR_I]], 7
-; EXPENSIVE-OFF-NEXT:    [[TMP2:%.*]] = and i32 [[CALL_LOBIT]], 1
-; EXPENSIVE-OFF-NEXT:    [[TMP3:%.*]] = load i32, i32* [[TMP0]], align 4
-; EXPENSIVE-OFF-NEXT:    [[OR:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; EXPENSIVE-OFF-NEXT:    store i32 [[OR]], i32* [[TMP0]], align 4
-; EXPENSIVE-OFF-NEXT:    [[TMP4:%.*]] = load i32, i32* @a, align 4
-; EXPENSIVE-OFF-NEXT:    [[LNOT_1:%.*]] = icmp eq i32 [[TMP4]], 0
-; EXPENSIVE-OFF-NEXT:    [[LNOT_EXT_1:%.*]] = zext i1 [[LNOT_1]] to i32
-; EXPENSIVE-OFF-NEXT:    [[SHR_I_1:%.*]] = lshr i32 2072, [[LNOT_EXT_1]]
-; EXPENSIVE-OFF-NEXT:    [[CALL_LOBIT_1:%.*]] = lshr i32 [[SHR_I_1]], 7
-; EXPENSIVE-OFF-NEXT:    [[TMP5:%.*]] = and i32 [[CALL_LOBIT_1]], 1
-; EXPENSIVE-OFF-NEXT:    [[OR_1:%.*]] = or i32 [[TMP5]], [[TMP3]]
-; EXPENSIVE-OFF-NEXT:    store i32 [[OR_1]], i32* [[TMP0]], align 4
-; EXPENSIVE-OFF-NEXT:    ret i32 [[OR_1]]
-;
-; EXPENSIVE-ON-LABEL: @main(
-; EXPENSIVE-ON-NEXT:  entry:
-; EXPENSIVE-ON-NEXT:    [[TMP0:%.*]] = load i32*, i32** @b, align 8
-; EXPENSIVE-ON-NEXT:    [[TMP1:%.*]] = load i32, i32* [[TMP0]], align 4
-; EXPENSIVE-ON-NEXT:    ret i32 [[TMP1]]
+; CHECK-LABEL: @main(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32*, i32** @b, align 8
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    [[LNOT:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    [[LNOT_EXT:%.*]] = zext i1 [[LNOT]] to i32
+; CHECK-NEXT:    [[SHR_I:%.*]] = lshr i32 2072, [[LNOT_EXT]]
+; CHECK-NEXT:    [[CALL_LOBIT:%.*]] = lshr i32 [[SHR_I]], 7
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[CALL_LOBIT]], 1
+; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[TMP0]], align 4
+; CHECK-NEXT:    [[OR:%.*]] = or i32 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    store i32 [[OR]], i32* [[TMP0]], align 4
+; CHECK-NEXT:    [[TMP4:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    [[LNOT_1:%.*]] = icmp eq i32 [[TMP4]], 0
+; CHECK-NEXT:    [[LNOT_EXT_1:%.*]] = zext i1 [[LNOT_1]] to i32
+; CHECK-NEXT:    [[SHR_I_1:%.*]] = lshr i32 2072, [[LNOT_EXT_1]]
+; CHECK-NEXT:    [[CALL_LOBIT_1:%.*]] = lshr i32 [[SHR_I_1]], 7
+; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[CALL_LOBIT_1]], 1
+; CHECK-NEXT:    [[OR_1:%.*]] = or i32 [[TMP5]], [[TMP3]]
+; CHECK-NEXT:    store i32 [[OR_1]], i32* [[TMP0]], align 4
+; CHECK-NEXT:    ret i32 [[OR_1]]
 ;
 entry:
   %0 = load i32*, i32** @b, align 8
   %1 = load i32, i32* @a, align 4
   %lnot = icmp eq i32 %1, 0
   %lnot.ext = zext i1 %lnot to i32
   %shr.i = lshr i32 2072, %lnot.ext
   %call.lobit = lshr i32 %shr.i, 7

test/Transforms/InstCombine/assume.ll

;
   tail call void @llvm.assume(i1 %cmp) ; %load has at least highest bit set
   %rval = icmp eq i32* %load, null
   ret i1 %rval
 }
 
 ; PR35846 - https://bugs.llvm.org/show_bug.cgi?id=35846
 
 define i32 @assumption_conflicts_with_known_bits(i32 %a, i32 %b) {
-; EXPENSIVE-ON-LABEL: @assumption_conflicts_with_known_bits(
-; EXPENSIVE-ON-NEXT:    tail call void @llvm.assume(i1 false)
-; EXPENSIVE-ON-NEXT:    ret i32 0
-;
-; EXPENSIVE-OFF-LABEL: @assumption_conflicts_with_known_bits(
-; EXPENSIVE-OFF-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], 3
-; EXPENSIVE-OFF-NEXT:    tail call void @llvm.assume(i1 false)
-; EXPENSIVE-OFF-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[AND1]], 0
-; EXPENSIVE-OFF-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
-; EXPENSIVE-OFF-NEXT:    ret i32 0
+; CHECK-LABEL: @assumption_conflicts_with_known_bits(
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], 3
+; CHECK-NEXT:    tail call void @llvm.assume(i1 false)
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[AND1]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
+; CHECK-NEXT:    ret i32 0
 ;
   %and1 = and i32 %b, 3
   %B1 = lshr i32 %and1, %and1
   %B3 = shl nuw nsw i32 %and1, %B1
   %cmp = icmp eq i32 %B3, 1
   tail call void @llvm.assume(i1 %cmp)
   %cmp2 = icmp eq i32 %B1, %B3
   tail call void @llvm.assume(i1 %cmp2)

test/Transforms/InstCombine/expensive-combines.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine < %s | FileCheck %s --check-prefix=DEFAULT
 ; RUN: opt -S -instcombine -expensive-combines=1 < %s | FileCheck %s --check-prefix=EXPENSIVE-ON
 ; RUN: opt -S -instcombine -expensive-combines=0 < %s | FileCheck %s --check-prefix=EXPENSIVE-OFF
 
 define void @test() {
 ; DEFAULT-LABEL: @test(
 ; DEFAULT-NEXT:    [[CALL:%.*]] = call i32 @passthru(i32 0)
-; DEFAULT-NEXT:    call void @sink(i32 0)
+; DEFAULT-NEXT:    call void @sink(i32 [[CALL]])
 ; DEFAULT-NEXT:    ret void
 ;
 ; EXPENSIVE-ON-LABEL: @test(
 ; EXPENSIVE-ON-NEXT:    [[CALL:%.*]] = call i32 @passthru(i32 0)
-; EXPENSIVE-ON-NEXT:    call void @sink(i32 0)
+; EXPENSIVE-ON-NEXT:    call void @sink(i32 [[CALL]])
 ; EXPENSIVE-ON-NEXT:    ret void
 ;
 ; EXPENSIVE-OFF-LABEL: @test(
 ; EXPENSIVE-OFF-NEXT:    [[CALL:%.*]] = call i32 @passthru(i32 0)
 ; EXPENSIVE-OFF-NEXT:    call void @sink(i32 [[CALL]])
 ; EXPENSIVE-OFF-NEXT:    ret void
 ;
   %call = call i32 @passthru(i32 0)
   call void @sink(i32 %call)
   ret void
 }
 
 declare i32 @passthru(i32 returned)
 declare void @sink(i32)

test/Transforms/InstCombine/out-of-bounds-indexes.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine -expensive-combines=0 < %s | FileCheck %s --check-prefixes=CHECK,EXPENSIVE-OFF
 ; RUN: opt -S -instcombine -expensive-combines=1 < %s | FileCheck %s --check-prefixes=CHECK,EXPENSIVE-ON
 ; Check that we don't crash on unreasonable constant indexes
 
 define i32 @test_out_of_bounds(i32 %a, i1 %x, i1 %y) {
-; EXPENSIVE-OFF-LABEL: @test_out_of_bounds(
-; EXPENSIVE-OFF-NEXT:  entry:
-; EXPENSIVE-OFF-NEXT:    [[AND1:%.*]] = and i32 [[A:%.*]], 3
-; EXPENSIVE-OFF-NEXT:    tail call void @llvm.assume(i1 undef)
-; EXPENSIVE-OFF-NEXT:    ret i32 [[AND1]]
-;
-; EXPENSIVE-ON-LABEL: @test_out_of_bounds(
-; EXPENSIVE-ON-NEXT:  entry:
-; EXPENSIVE-ON-NEXT:    [[AND1:%.*]] = and i32 [[A:%.*]], 3
-; EXPENSIVE-ON-NEXT:    tail call void @llvm.assume(i1 false)
-; EXPENSIVE-ON-NEXT:    ret i32 [[AND1]]
+; CHECK-LABEL: @test_out_of_bounds(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A:%.*]], 3
+; CHECK-NEXT:    tail call void @llvm.assume(i1 undef)
+; CHECK-NEXT:    ret i32 [[AND1]]
 ;
 entry:
   %and1 = and i32 %a, 3
   %B = lshr i32 %and1, -2147483648
   %cmp = icmp eq i32 %B, 1
   tail call void @llvm.assume(i1 %cmp)
   ret i32 %and1
 }
 
 define i128 @test_non64bit(i128 %a) {
-; EXPENSIVE-OFF-LABEL: @test_non64bit(
-; EXPENSIVE-OFF-NEXT:    [[AND1:%.*]] = and i128 [[A:%.*]], 3
-; EXPENSIVE-OFF-NEXT:    tail call void @llvm.assume(i1 undef)
-; EXPENSIVE-OFF-NEXT:    ret i128 [[AND1]]
-;
-; EXPENSIVE-ON-LABEL: @test_non64bit(
-; EXPENSIVE-ON-NEXT:    [[AND1:%.*]] = and i128 [[A:%.*]], 3
-; EXPENSIVE-ON-NEXT:    tail call void @llvm.assume(i1 false)
-; EXPENSIVE-ON-NEXT:    ret i128 [[AND1]]
+; CHECK-LABEL: @test_non64bit(
+; CHECK-NEXT:    [[AND1:%.*]] = and i128 [[A:%.*]], 3
+; CHECK-NEXT:    tail call void @llvm.assume(i1 undef)
+; CHECK-NEXT:    ret i128 [[AND1]]
 ;
   %and1 = and i128 %a, 3
   %B = lshr i128 %and1, -1
   %cmp = icmp eq i128 %B, 1
   tail call void @llvm.assume(i1 %cmp)
   ret i128 %and1
 }
 

test/Transforms/InstCombine/phi-shifts.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine -expensive-combines=0 < %s | FileCheck %s --check-prefixes=CHECK,EXPENSIVE-OFF
 ; RUN: opt -S -instcombine -expensive-combines=1 < %s | FileCheck %s --check-prefixes=CHECK,EXPENSIVE-ON
 
 ; OSS Fuzz: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=15217
 define i64 @fuzz15217(i1 %cond, i8* %Ptr, i64 %Val) {
-; EXPENSIVE-OFF-LABEL: @fuzz15217(
-; EXPENSIVE-OFF-NEXT:  entry:
-; EXPENSIVE-OFF-NEXT:    br i1 [[COND:%.*]], label [[END:%.*]], label [[TWO:%.*]]
-; EXPENSIVE-OFF:       two:
-; EXPENSIVE-OFF-NEXT:    br label [[END]]
-; EXPENSIVE-OFF:       end:
-; EXPENSIVE-OFF-NEXT:    ret i64 undef
-;
-; EXPENSIVE-ON-LABEL: @fuzz15217(
-; EXPENSIVE-ON-NEXT:  entry:
-; EXPENSIVE-ON-NEXT:    br i1 [[COND:%.*]], label [[END:%.*]], label [[TWO:%.*]]
-; EXPENSIVE-ON:       two:
-; EXPENSIVE-ON-NEXT:    br label [[END]]
-; EXPENSIVE-ON:       end:
-; EXPENSIVE-ON-NEXT:    ret i64 0
+; CHECK-LABEL: @fuzz15217(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[END:%.*]], label [[TWO:%.*]]
+; CHECK:       two:
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    ret i64 undef
 ;
 entry:
   br i1 %cond, label %end, label %two
 
 two:
   br label %end
 
 end:
   %tmp869.0 = phi i128 [ 0, %entry ], [ 18446744073709551616, %two ]
   %tmp29 = lshr i128 %tmp869.0, 64
   %B1 = lshr i128 %tmp29, 170141183460469231731687303715884105727
   %tmp30 = trunc i128 %B1 to i64
   ret i64 %tmp30
 }