[BDCE] Remove instructions without demanded bits

[nikic]

Summary

Followup to D55563.

If an instruction has no demanded bits, remove it directly during BDCE, instead of leaving it for something else to clean up.

[lebedev.ri]

test/Transforms/BDCE/invalidate-assumptions.ll

88

Can you please do a NFC regen commit first?

[nikic]

test/Transforms/BDCE/invalidate-assumptions.ll

88

I'm wondering if I should maybe just manually edit those changes away? Using a pattern for an argument name doesn't make a lot of sense to me. Is there a reason why update_test_checks.py generates it this way? Is this so the result looks for uniform?

[lebedev.ri]

test/Transforms/BDCE/invalidate-assumptions.ll

88

[[A:%.*]] means "match %.* regex, and store it to A".
So when [[A]] is encountered next, it will be expanded to what was previously matched, which is %a.
And no, consistently using these update tools is the only sane way.

[nikic]

Rebase over regenerated test checks.

[spatel]

test/Transforms/BDCE/invalidate-assumptions.ll

88

I agree that using a pattern for an argument is not ideal. The history for this is that the script used to *not* regex-ify arguments (that was my quick/dirty initial implementation which was just copied from existing scripts), but the script also didn't work with tests that had loops or function calls. This was fixed with D28384 and follow-up commits.

I don't know what it takes to improve the script to do both things, but it would be a welcome change if someone wants to take that on. Independent of that, I agree with Roman - just use the script as-is to update regression tests. It's less error-prone to run the script than hand-edit small improvements on top of the results.

[hfinkel]

LGTM

lib/Transforms/Scalar/BDCE.cpp

static bool bitTrackingDCE(Function &F, DemandedBits &DB) {
   bool Changed = false;
   for (Instruction &I : instructions(F)) {
     // If the instruction has side effects and no non-dbg uses,
     // skip it. This way we avoid computing known bits on an instruction
     // that will not help us.
     if (I.mayHaveSideEffects() && I.use_empty())
       continue;
 
-    // Remove instructions not reached during analysis.
-    if (DB.isInstructionDead(&I)) {
+    // Remove instructions that are dead, either because they were not reached
+    // during analysis or have no demanded bits.
+    if (DB.isInstructionDead(&I) ||
+        (I.getType()->isIntOrIntVectorTy() &&
+         DB.getDemandedBits(&I).isNullValue() &&
+         wouldInstructionBeTriviallyDead(&I))) {
       salvageDebugInfo(I);
       Worklist.push_back(&I);
       I.dropAllReferences();
       Changed = true;
       continue;
     }
 
     for (Use &U : I.operands()) {

test/Transforms/BDCE/invalidate-assumptions.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -bdce %s -S | FileCheck %s
 
 ; The 'nuw' on the subtract allows us to deduce that %setbit is not demanded.
 ; But if we change that value to '0', then the 'nuw' is no longer valid. If we don't
 ; remove the 'nuw', another pass (-instcombine) may make a transform based on an
 ; that incorrect assumption and we can miscompile:
 ; https://bugs.llvm.org/show_bug.cgi?id=33695
 
 define i1 @PR33695(i1 %b, i8 %x) {
 ; CHECK-LABEL: @PR33695(
-; CHECK-NEXT:    [[SETBIT:%.*]] = or i8 [[X:%.*]], 64
 ; CHECK-NEXT:    [[LITTLE_NUMBER:%.*]] = zext i1 [[B:%.*]] to i8
 ; CHECK-NEXT:    [[BIG_NUMBER:%.*]] = shl i8 0, 1
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i8 [[BIG_NUMBER]], [[LITTLE_NUMBER]]
 ; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i8 [[SUB]] to i1
 ; CHECK-NEXT:    ret i1 [[TRUNC]]
 ;
   %setbit = or i8 %x, 64
   %little_number = zext i1 %b to i8
   %big_number = shl i8 %setbit, 1
   %sub = sub nuw i8 %big_number, %little_number
   %trunc = trunc i8 %sub to i1
   ret i1 %trunc
 }
 
 ; Similar to above, but now with more no-wrap.
 ; https://bugs.llvm.org/show_bug.cgi?id=34037
 
 define i64 @PR34037(i64 %m, i32 %r, i64 %j, i1 %b, i32 %k, i64 %p) {
 ; CHECK-LABEL: @PR34037(
-; CHECK-NEXT:    [[CONV:%.*]] = zext i32 [[R:%.*]] to i64
-; CHECK-NEXT:    [[AND:%.*]] = and i64 [[M:%.*]], 0
-; CHECK-NEXT:    [[NEG:%.*]] = xor i64 0, 34359738367
-; CHECK-NEXT:    [[OR:%.*]] = or i64 [[J:%.*]], 0
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i64 0, 29
 ; CHECK-NEXT:    [[CONV1:%.*]] = select i1 [[B:%.*]], i64 7, i64 0
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i64 [[SHL]], [[CONV1]]
 ; CHECK-NEXT:    [[CONV2:%.*]] = zext i32 [[K:%.*]] to i64
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i64 [[SUB]], [[CONV2]]
 ; CHECK-NEXT:    [[CONV4:%.*]] = and i64 [[P:%.*]], 65535
 ; CHECK-NEXT:    [[AND5:%.*]] = and i64 [[MUL]], [[CONV4]]
 ; CHECK-NEXT:    ret i64 [[AND5]]

 ; This is a manufactured example based on the 1st test to prove that the
 ; assumption-killing algorithm stops at the call. Ie, it does not remove
 ; nsw/nuw from the 'add' because a call demands all bits of its argument.
 
 declare i1 @foo(i1)
 
 define i1 @poison_on_call_user_is_ok(i1 %b, i8 %x) {
 ; CHECK-LABEL: @poison_on_call_user_is_ok(
-; CHECK-NEXT:    [[SETBIT:%.*]] = or i8 [[X:%.*]], 64
 ; CHECK-NEXT:    [[LITTLE_NUMBER:%.*]] = zext i1 [[B:%.*]] to i8
 ; CHECK-NEXT:    [[BIG_NUMBER:%.*]] = shl i8 0, 1
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i8 [[BIG_NUMBER]], [[LITTLE_NUMBER]]
 ; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i8 [[SUB]] to i1
 ; CHECK-NEXT:    [[CALL_RESULT:%.*]] = call i1 @foo(i1 [[TRUNC]])
 ; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i1 [[CALL_RESULT]], true
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i1 [[TRUNC]], [[ADD]]
 ; CHECK-NEXT:    ret i1 [[MUL]]

 }
 
 
 ; We were asserting that all users of a trivialized integer-type instruction were
 ; also integer-typed, but that's too strong. The alloca has a pointer-type result.
 
 define void @PR34179(i32* %a) {
 ; CHECK-LABEL: @PR34179(
 ; CHECK-NEXT:    [[T0:%.*]] = load volatile i32, i32* [[A:%.*]]
 ; CHECK-NEXT:    ret void
 ;
   %t0 = load volatile i32, i32* %a
   %vla = alloca i32, i32 %t0
   ret void
 }
 

test/Transforms/BDCE/vectors.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -bdce < %s | FileCheck %s
 
 ; BDCE applied to integer vectors.
 
 define <2 x i32> @test_basic(<2 x i32> %a, <2 x i32> %b) {
 ; CHECK-LABEL: @test_basic(
-; CHECK-NEXT:    [[A2:%.*]] = add <2 x i32> [[A:%.*]], <i32 1, i32 1>
 ; CHECK-NEXT:    [[A3:%.*]] = and <2 x i32> zeroinitializer, <i32 4, i32 4>
 ; CHECK-NEXT:    [[B2:%.*]] = add <2 x i32> [[B:%.*]], <i32 1, i32 1>
 ; CHECK-NEXT:    [[B3:%.*]] = and <2 x i32> [[B2]], <i32 8, i32 8>
 ; CHECK-NEXT:    [[C:%.*]] = or <2 x i32> [[A3]], [[B3]]
 ; CHECK-NEXT:    [[D:%.*]] = ashr <2 x i32> [[C]], <i32 3, i32 3>
 ; CHECK-NEXT:    ret <2 x i32> [[D]]
 ;
   %a2 = add <2 x i32> %a, <i32 1, i32 1>
   %a3 = and <2 x i32> %a2, <i32 4, i32 4>
   %b2 = add <2 x i32> %b, <i32 1, i32 1>
   %b3 = and <2 x i32> %b2, <i32 8, i32 8>
   %c = or <2 x i32> %a3, %b3
   %d = ashr <2 x i32> %c, <i32 3, i32 3>
   ret <2 x i32> %d
 }
 
 ; Going vector -> scalar
 define i32 @test_extractelement(<2 x i32> %a, <2 x i32> %b) {
 ; CHECK-LABEL: @test_extractelement(
-; CHECK-NEXT:    [[A2:%.*]] = add <2 x i32> [[A:%.*]], <i32 1, i32 1>
 ; CHECK-NEXT:    [[A3:%.*]] = and <2 x i32> zeroinitializer, <i32 4, i32 4>
 ; CHECK-NEXT:    [[B2:%.*]] = add <2 x i32> [[B:%.*]], <i32 1, i32 1>
 ; CHECK-NEXT:    [[B3:%.*]] = and <2 x i32> [[B2]], <i32 8, i32 8>
 ; CHECK-NEXT:    [[C:%.*]] = or <2 x i32> [[A3]], [[B3]]
 ; CHECK-NEXT:    [[D:%.*]] = extractelement <2 x i32> [[C]], i32 0
 ; CHECK-NEXT:    [[E:%.*]] = ashr i32 [[D]], 3
 ; CHECK-NEXT:    ret i32 [[E]]
 ;
   %a2 = add <2 x i32> %a, <i32 1, i32 1>
   %a3 = and <2 x i32> %a2, <i32 4, i32 4>
   %b2 = add <2 x i32> %b, <i32 1, i32 1>
   %b3 = and <2 x i32> %b2, <i32 8, i32 8>
   %c = or <2 x i32> %a3, %b3
   %d = extractelement <2 x i32> %c, i32 0
   %e = ashr i32 %d, 3
   ret i32 %e
 }
 
 ; Going scalar -> vector
 define <2 x i32> @test_insertelement(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test_insertelement(
-; CHECK-NEXT:    [[X:%.*]] = insertelement <2 x i32> undef, i32 [[A:%.*]], i32 0
-; CHECK-NEXT:    [[X2:%.*]] = insertelement <2 x i32> zeroinitializer, i32 [[B:%.*]], i32 1
 ; CHECK-NEXT:    [[X3:%.*]] = and <2 x i32> zeroinitializer, <i32 4, i32 4>
-; CHECK-NEXT:    [[Y:%.*]] = insertelement <2 x i32> undef, i32 [[B]], i32 0
-; CHECK-NEXT:    [[Y2:%.*]] = insertelement <2 x i32> [[Y]], i32 [[A]], i32 1
+; CHECK-NEXT:    [[Y:%.*]] = insertelement <2 x i32> undef, i32 [[B:%.*]], i32 0
+; CHECK-NEXT:    [[Y2:%.*]] = insertelement <2 x i32> [[Y]], i32 [[A:%.*]], i32 1
 ; CHECK-NEXT:    [[Y3:%.*]] = and <2 x i32> [[Y2]], <i32 8, i32 8>
 ; CHECK-NEXT:    [[Z:%.*]] = or <2 x i32> [[X3]], [[Y3]]
 ; CHECK-NEXT:    [[U:%.*]] = ashr <2 x i32> [[Z]], <i32 3, i32 3>
 ; CHECK-NEXT:    ret <2 x i32> [[U]]
 ;
   %x = insertelement <2 x i32> undef, i32 %a, i32 0
   %x2 = insertelement <2 x i32> %x, i32 %b, i32 1
   %x3 = and <2 x i32> %x2, <i32 4, i32 4>
;
   %z = fptoui <2 x double> %y to <2 x i32>
   %u = ashr <2 x i32> %z, <i32 3, i32 3>
   ret <2 x i32> %u
 }
 
 ; Assumption invalidation (adapted from invalidate-assumptions.ll)
 define <2 x i1> @test_assumption_invalidation(<2 x i1> %b, <2 x i8> %x) {
 ; CHECK-LABEL: @test_assumption_invalidation(
-; CHECK-NEXT:    [[SETBIT:%.*]] = or <2 x i8> [[X:%.*]], <i8 64, i8 64>
 ; CHECK-NEXT:    [[LITTLE_NUMBER:%.*]] = zext <2 x i1> [[B:%.*]] to <2 x i8>
 ; CHECK-NEXT:    [[BIG_NUMBER:%.*]] = shl <2 x i8> zeroinitializer, <i8 1, i8 1>
 ; CHECK-NEXT:    [[SUB:%.*]] = sub <2 x i8> [[BIG_NUMBER]], [[LITTLE_NUMBER]]
 ; CHECK-NEXT:    [[TRUNC:%.*]] = trunc <2 x i8> [[SUB]] to <2 x i1>
 ; CHECK-NEXT:    ret <2 x i1> [[TRUNC]]
 ;
   %setbit = or <2 x i8> %x, <i8 64, i8 64>
   %little_number = zext <2 x i1> %b to <2 x i8>
   %big_number = shl <2 x i8> %setbit, <i8 1, i8 1>
   %sub = sub nuw <2 x i8> %big_number, %little_number
   %trunc = trunc <2 x i8> %sub to <2 x i1>
   ret <2 x i1> %trunc
 }