[InstCombine] Add simplifications for div/rem with `i1` operands; PR62607

[goldstein.w.n]

Summary

This is generally handled already in early CSE.

If a specialized pipeline is used, however, its possible for i1
operand with known-zero denominator to slip through. Generally the
known-zero denominator is caught and poison is returned, but if it is
indirect enough (known zero through a phi node) we can miss this case
in InstructionSimplify and then miss handling i1. This is because
i1 is current handled with the following check:

`if(Known.countMinLeadingZeros() == Known.getBitWidth() - 1)`

which only works on the assumption we don't know the denominator to be
zero. If we know the denominator to be zero, this check fails:
https://github.com/llvm/llvm-project/issues/62607

This patch simply adds an explicit if(Known.isZero) return poison;
which fixes the issue.

Alive2 Link for tests:

https://alive2.llvm.org/ce/z/VTw54n

[nikic]

Missing InstSimplify tests. The check for this was dropped as part of https://github.com/llvm/llvm-project/commit/946b32680311f43a349d0199f9e286f385cd9847, and apparently had no test coverage? Though I don't really get why the new KnownBits based code doesn't cover this: For i1 type I'd expect Known.countMinLeadingZeros() == Known.getBitWidth() - 1 to evaluate to true?

[goldstein.w.n]

In D150142#4327705, @nikic wrote:

Missing InstSim plify tests. The check for this was dropped as part of https://github.com/llvm/llvm-project/commit/946b32680311f43a349d0199f9e286f385cd9847, and apparently had no test coverage? Though I don't really get why the new KnownBits based code doesn't cover this: For i1 type I'd expect Known.countMinLeadingZeros() == Known.getBitWidth() - 1 to evaluate to true?

Its because the denominator is known-zero (at least in the case from the bugreport):

Known.Zero: 1
Known.One: 0 
Known.countMinLeadingZeros(): 1
Known.getBitWidth(): 1

So actually this patch should probably be returning poison?

Edit:
Hers a minimal reproduction:

define i1 @foo(i1 %c, i1 %x, i1 %y) {
  br i1 %c, label %true, label %false
true:
  %y_true = and i1 %y, 0
  br label %done
false:
  %y_false = and i1 %y, 0
  br label %done
done:
  %yy = phi i1 [ %y_false, %false ], [ %y_true, %true ]
  %r = sdiv i1 %x, %yy
  ret i1 %r
}

There needs to be some non-trivial zero pattern so it doesn't get constant folded.
Either returning poison or op0 is fine:
https://alive2.llvm.org/ce/z/9RuT_m
poison probably makes more sense though.

[goldstein.w.n]

Add explicit tests, better explain the issue

[nikic]

llvm/lib/Analysis/InstructionSimplify.cpp

1143–1147

Move this comment to the if below now?

llvm/test/Transforms/InstCombine/div-i1.ll

17

Is there a more robust way to test this that doesn't rely on worklist order bugs? Something like an assume to zero in an instsimplify test? Or does that also get simplified early?

llvm/test/Transforms/InstCombine/pr62607.ll

6 ↗

(On Diff #520511)

Remove triple.

86 ↗

(On Diff #520511)

Is this already a minimal reduction per llvm-reduce?

[floatshadow]

In D150142#4327941, @goldstein.w.n wrote:

Edit:
Hers a minimal reproduction:

define i1 @foo(i1 %c, i1 %x, i1 %y) {
  br i1 %c, label %true, label %false
true:
  %y_true = and i1 %y, 0
  br label %done
false:
  %y_false = and i1 %y, 0
  br label %done
done:
  %yy = phi i1 [ %y_false, %false ], [ %y_true, %true ]
  %r = sdiv i1 %x, %yy
  ret i1 %r
}

There needs to be some non-trivial zero pattern so it doesn't get constant folded.
Either returning poison or op0 is fine:
https://alive2.llvm.org/ce/z/9RuT_m
poison probably makes more sense though.

I guess this reproduction need some refinement. KnownBits indeed neglects zero cases, but the threadBinOpOverPHI would do recursive check which later got folded in a pattern match if (match(Op1, m_Zero())) in simplifyDivRem

[floatshadow]

llvm/lib/Analysis/InstructionSimplify.cpp

1097

Can we remove this? I think this might also be covered by KnownBits::isZero() check now.

[goldstein.w.n]

llvm/lib/Analysis/InstructionSimplify.cpp

1097

We can, although my feeling is it makes sense to have a fastpath for the common case (knownbits can be expensive).

llvm/test/Transforms/InstCombine/div-i1.ll

17

Is there a more robust way to test this that doesn't rely on worklist order bugs? Something like an assume to zero in an instsimplify test? Or does that also get simplified early?

It gets simplified early (and is handled correctly now/before). This was the simplest reproduction I could create.

llvm/test/Transforms/InstCombine/pr62607.ll

86 ↗

(On Diff #520511)

Is this already a minimal reduction per llvm-reduce?

No, but updated (so yes in v3). Neat tool :)

[goldstein.w.n]

Reduce test, cleanup comments

[goldstein.w.n]

ping. This is still an outstanding bug.

[nikic]

LGTM

llvm/test/Transforms/InstCombine/pr62607.ll

17 ↗

(On Diff #520775)

Most of these declarations are dead?

19 ↗

(On Diff #520775)

Merge this into the other file with @pr62607 name.

50 ↗

(On Diff #520775)

Attributes shouldn't be needed either.

[goldstein.w.n]

Cleanup tests

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *simplifyDivRem(Instruction::BinaryOps Opcode, Value *Op0,
   // X / undef -> poison
   // X % undef -> poison
   if (Q.isUndefValue(Op1) || isa<PoisonValue>(Op1))
     return PoisonValue::get(Ty);
 
   // X / 0 -> poison
   // X % 0 -> poison
   // We don't need to preserve faults!
   if (match(Op1, m_Zero()))
     return PoisonValue::get(Ty);
 
   // If any element of a constant divisor fixed width vector is zero or undef
   // the behavior is undefined and we can fold the whole op to poison.
   auto *Op1C = dyn_cast<Constant>(Op1);
   auto *VTy = dyn_cast<FixedVectorType>(Ty);
   if (Op1C && VTy) {
     unsigned NumElts = VTy->getNumElements();
static Value *simplifyDivRem(Instruction::BinaryOps Opcode, Value *Op0,
   if (match(Op0, m_Zero()))
     return Constant::getNullValue(Op0->getType());
 
   // X / X -> 1
   // X % X -> 0
   if (Op0 == Op1)
     return IsDiv ? ConstantInt::get(Ty, 1) : Constant::getNullValue(Ty);
 
+
+  KnownBits Known = computeKnownBits(Op1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
+  // X / 0 -> poison
+  // X % 0 -> poison
+  // If the divisor is known to be zero, just return poison. This can happen in
+  // some cases where its provable indirectly the denominator is zero but it's
+  // not trivially simplifiable (i.e known zero through a phi node).
+  if (Known.isZero())
+    return PoisonValue::get(Ty);
+
   // X / 1 -> X
   // X % 1 -> 0
   // If the divisor can only be zero or one, we can't have division-by-zero
   // or remainder-by-zero, so assume the divisor is 1.
   //   e.g. 1, zext (i8 X), sdiv X (Y and 1)
-  KnownBits Known = computeKnownBits(Op1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
   if (Known.countMinLeadingZeros() == Known.getBitWidth() - 1)
     return IsDiv ? Op0 : Constant::getNullValue(Ty);
 
   // If X * Y does not overflow, then:
   //   X * Y / Y -> X
   //   X * Y % Y -> 0
   Value *X;
   if (match(Op0, m_c_Mul(m_Value(X), m_Specific(Op1)))) {

llvm/test/Transforms/InstCombine/div-i1.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -passes=instcombine < %s | FileCheck %s
+
+define i1 @sdiv_by_zero_indirect_is_poison(i1 %c, i1 %x, i1 %y) {
+; CHECK-LABEL: @sdiv_by_zero_indirect_is_poison(
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[TRUE:%.*]], label [[FALSE:%.*]]
+; CHECK:       true:
+; CHECK-NEXT:    br label [[DONE:%.*]]
+; CHECK:       false:
+; CHECK-NEXT:    br label [[DONE]]
+; CHECK:       done:
+; CHECK-NEXT:    ret i1 poison
+;
+  br i1 %c, label %true, label %false
+true:
+  %y_true = and i1 %y, 0
+  br label %done
+false:
+  %y_false = and i1 %y, 0
+  br label %done
+done:
+  %yy = phi i1 [ %y_false, %false ], [ %y_true, %true ]
+  %r = sdiv i1 %x, %yy
+  ret i1 %r
+}
+
+define i1 @udiv_by_zero_indirect_is_poison(i1 %c, i1 %x, i1 %y) {
+; CHECK-LABEL: @udiv_by_zero_indirect_is_poison(
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[TRUE:%.*]], label [[FALSE:%.*]]
+; CHECK:       true:
+; CHECK-NEXT:    br label [[DONE:%.*]]
+; CHECK:       false:
+; CHECK-NEXT:    br label [[DONE]]
+; CHECK:       done:
+; CHECK-NEXT:    ret i1 poison
+;
+  br i1 %c, label %true, label %false
+true:
+  %y_true = and i1 %y, 0
+  br label %done
+false:
+  %y_false = and i1 %y, 0
+  br label %done
+done:
+  %yy = phi i1 [ %y_false, %false ], [ %y_true, %true ]
+  %r = udiv i1 %x, %yy
+  ret i1 %r
+}
+
+define i1 @srem_by_zero_indirect_is_poison(i1 %c, i1 %x, i1 %y) {
+; CHECK-LABEL: @srem_by_zero_indirect_is_poison(
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[TRUE:%.*]], label [[FALSE:%.*]]
+; CHECK:       true:
+; CHECK-NEXT:    br label [[DONE:%.*]]
+; CHECK:       false:
+; CHECK-NEXT:    br label [[DONE]]
+; CHECK:       done:
+; CHECK-NEXT:    ret i1 poison
+;
+  br i1 %c, label %true, label %false
+true:
+  %y_true = and i1 %y, 0
+  br label %done
+false:
+  %y_false = and i1 %y, 0
+  br label %done
+done:
+  %yy = phi i1 [ %y_false, %false ], [ %y_true, %true ]
+  %r = srem i1 %x, %yy
+  ret i1 %r
+}
+
+define i1 @urem_by_zero_indirect_is_poison(i1 %c, i1 %x, i1 %y) {
+; CHECK-LABEL: @urem_by_zero_indirect_is_poison(
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[TRUE:%.*]], label [[FALSE:%.*]]
+; CHECK:       true:
+; CHECK-NEXT:    br label [[DONE:%.*]]
+; CHECK:       false:
+; CHECK-NEXT:    br label [[DONE]]
+; CHECK:       done:
+; CHECK-NEXT:    ret i1 poison
+;
+  br i1 %c, label %true, label %false
+true:
+  %y_true = and i1 %y, 0
+  br label %done
+false:
+  %y_false = and i1 %y, 0
+  br label %done
+done:
+  %yy = phi i1 [ %y_false, %false ], [ %y_true, %true ]
+  %r = urem i1 %x, %yy
+  ret i1 %r
+}
+
+define i1 @sdiv_i1_is_op0(i1 %x, i1 %y) {
+; CHECK-LABEL: @sdiv_i1_is_op0(
+; CHECK-NEXT:    ret i1 [[X:%.*]]
+;
+  %r = sdiv i1 %x, %y
+  ret i1 %r
+}
+
+define i1 @udiv_i1_is_op0(i1 %x, i1 %y) {
+; CHECK-LABEL: @udiv_i1_is_op0(
+; CHECK-NEXT:    ret i1 [[X:%.*]]
+;
+  %r = udiv i1 %x, %y
+  ret i1 %r
+}
+
+define i1 @srem_i1_is_zero(i1 %x, i1 %y) {
+; CHECK-LABEL: @srem_i1_is_zero(
+; CHECK-NEXT:    ret i1 false
+;
+  %r = srem i1 %x, %y
+  ret i1 %r
+}
+
+define i1 @urem_i1_is_zero(i1 %x, i1 %y) {
+; CHECK-LABEL: @urem_i1_is_zero(
+; CHECK-NEXT:    ret i1 false
+;
+  %r = urem i1 %x, %y
+  ret i1 %r
+}
+
+declare void @llvm.assume(i1 noundef)
+
+define i1 @pt62607() {
+; CHECK-LABEL: @pt62607(
+; CHECK-NEXT:  entry_1:
+; CHECK-NEXT:    br label [[LOOP_5:%.*]]
+; CHECK:       loop_5:
+; CHECK-NEXT:    [[LOOP_CNT_I1_26_0:%.*]] = phi i1 [ false, [[ENTRY_1:%.*]] ], [ [[VAL_I1_55:%.*]], [[LOOP_5]] ]
+; CHECK-NEXT:    [[VAL_I1_55]] = xor i1 [[LOOP_CNT_I1_26_0]], true
+; CHECK-NEXT:    call void @llvm.assume(i1 [[VAL_I1_55]])
+; CHECK-NEXT:    br i1 poison, label [[LOOP_5]], label [[LOOP_EXIT_8:%.*]]
+; CHECK:       loop_exit_8:
+; CHECK-NEXT:    ret i1 false
+;
+entry_1:
+  %val_i1_38 = trunc i8 109 to i1
+  br label %loop_5
+loop_5:  ; preds = %loop_5, %entry_1
+  %loop_cnt_i1_26.0 = phi i1 [ false, %entry_1 ], [ %val_i1_55, %loop_5 ]
+  %val_i1_55 = add i1 %loop_cnt_i1_26.0, true
+  call void @llvm.assume(i1 %val_i1_55)
+  %val_i1_67 = udiv i1 %val_i1_38, %loop_cnt_i1_26.0
+  br i1 %val_i1_67, label %loop_5, label %loop_exit_8
+loop_exit_8:  ; preds = %loop_5
+  ret i1 false
+}