[InstCombine] Don't combine CmpInst that used for verify the legality of the lshr

[TiehuZhang]

Summary

When the value of lshr's shift operand is unknown (e.g., the operand is passed through a function parameter), the cmp instruction used to determine the validity of the shift operand cannot be eliminated. Otherwise, undefined behavior may occur.

[lebedev.ri]

Sorry, but i can not parse the description,

The current transformation is *not* a miscompile:
https://godbolt.org/z/WeTeasK53
https://alive2.llvm.org/ce/z/LVDqSX

[mdchen]

@lebedev.ri I think the problem is when %0 is negative, the original code gives a definite result while the transformed IR is UB.

[TiehuZhang]

In D111804#3064140, @lebedev.ri wrote:

Sorry, but i can not parse the description,

The current transformation is *not* a miscompile:
https://godbolt.org/z/WeTeasK53
https://alive2.llvm.org/ce/z/LVDqSX

I'm sorry I didn't make my point clear. The purpose of my current modification is to circumvent a false optimization. In, the case, %0 may be negative. If we eliminate %cmp = icmp slt i32 %0, 0, undefined behavior may occur, as lshr performed a negative shift. @lebedev.ri

original version

%cmp = icmp slt i32 %0, 0
%shr = lshr i32 7, %0
%cmp1 = icmp sgt i32 %0, %shr
%or.cond = or i1 %cmp, %cmp1
br i1 %or.cond, label %cond.end, label %cond.false

miscompile

%shr = lshr i32 7, %0
%1 = icmp ult i32 %shr, %0
br i1 %1, label %cond.end, label %cond.false

[craig.topper]

If an input to an or instruction is poison, the output of the or is poison regardless of whether the other operand is true when the poison result occurs.

If an incorrect optimization is occurring it must be where the or is created.

[TiehuZhang]

In D111804#3065906, @craig.topper wrote:

If an input to an or instruction is poison, the output of the or is poison regardless of whether the other operand is true when the poison result occurs.

If an incorrect optimization is occurring it must be where the or is created.

Thanks for your review! @craig.topper. Do you mean that we should prevent this pattern from being generated, rather than remedying it after the pattern is generated? Actually, the issue I met started from D95959. That optimization does not seem to apply to all scenarios, such as those where the shift operand is negative. In the case I present, this optimization results in a miscalculation of the KnownBit, which in turn results in a false transformation.

[craig.topper]

In D111804#3065924, @TiehuZhang wrote:

In D111804#3065906, @craig.topper wrote:

If an input to an or instruction is poison, the output of the or is poison regardless of whether the other operand is true when the poison result occurs.

If an incorrect optimization is occurring it must be where the or is created.

Thanks for your review! @craig.topper. Do you mean that we should prevent this pattern from being generated, rather than remedying it after the pattern is generated? Actually, the issue I met started from D95959. That optimization does not seem to apply to all scenarios, such as those where the shift operand is negative. In the case I present, this optimization results in a miscalculation of the KnownBit, which in turn results in a false transformation.

The transform is correct based on the semantics of llvm's or instruction. The or instruction in llvm does not have short circuit evaluation. It can't block the spread of poison. The IR that has the semantics you want is

define i32 @cmp_lshr_cmp(i32 %0) {
entry:
  %cmp = icmp slt i32 %0, 0
  %shr = lshr i32 7, %0
  %cmp1 = icmp sgt i32 %0, %shr
  %or.cond = select i1 %cmp, i1 true, i1 %cmp1
  br i1 %or.cond, label %cond.end, label %cond.false

cond.false:                                       ; preds = %entry
  ret i32 1

cond.end:                                         ; preds = %entry, %cond.false
  ret i32 0
}

Using a select instruction instead of an or prevents the %cmp1 value from being used if %cmp is true. There was previously an incorrect transform that would turn such a select into an or, but it was disabled in https://reviews.llvm.org/D101191

[TiehuZhang]

In D111804#3065956, @craig.topper wrote:

In D111804#3065924, @TiehuZhang wrote:

In D111804#3065906, @craig.topper wrote:

If an input to an or instruction is poison, the output of the or is poison regardless of whether the other operand is true when the poison result occurs.

If an incorrect optimization is occurring it must be where the or is created.

Thanks for your review! @craig.topper. Do you mean that we should prevent this pattern from being generated, rather than remedying it after the pattern is generated? Actually, the issue I met started from D95959. That optimization does not seem to apply to all scenarios, such as those where the shift operand is negative. In the case I present, this optimization results in a miscalculation of the KnownBit, which in turn results in a false transformation.

The transform is correct based on the semantics of llvm's or instruction. The or instruction in llvm does not have short circuit evaluation. It can't block the spread of poison. The IR that has the semantics you want is

define i32 @cmp_lshr_cmp(i32 %0) {
entry:
  %cmp = icmp slt i32 %0, 0
  %shr = lshr i32 7, %0
  %cmp1 = icmp sgt i32 %0, %shr
  %or.cond = select i1 %cmp, i1 true, i1 %cmp1
  br i1 %or.cond, label %cond.end, label %cond.false

cond.false:                                       ; preds = %entry
  ret i32 1

cond.end:                                         ; preds = %entry, %cond.false
  ret i32 0
}

Using a select instruction instead of an or prevents the %cmp1 value from being used if %cmp is true. There was previously an incorrect transform that would turn such a select into an or, but it was disabled in https://reviews.llvm.org/D101191

OK, I get it. I'll try to find out why the or is still generated. Thanks very much @craig.topper

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Value *InstCombinerImpl::simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1,
   // Check the upper range comparison, e.g. x < n
   ICmpInst::Predicate NewPred;
   switch (Pred1) {
     case ICmpInst::ICMP_SLT: NewPred = ICmpInst::ICMP_ULT; break;
     case ICmpInst::ICMP_SLE: NewPred = ICmpInst::ICMP_ULE; break;
     default: return nullptr;
   }
 
+  // If x > -1 or x >= 0 is used to verify the legality of lshr,
+  // it shouldn't be combined.
+  if (auto *I = dyn_cast<Operator>(RangeEnd))
+    if (I->getOpcode() == Instruction::LShr)
+      return nullptr;
+
   // This simplification is only valid if the upper range is not negative.
   KnownBits Known = computeKnownBits(RangeEnd, /*Depth=*/0, Cmp1);
   if (!Known.isNonNegative())
     return nullptr;
 
   if (Inverted)
     NewPred = ICmpInst::getInversePredicate(NewPred);
 

llvm/test/Transforms/InstCombine/shift.ll

 ; CHECK-NEXT:    [[S:%.*]] = shl i8 12, [[X:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[S]], 4
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %s = shl i8 12, %x ; 0b00001100
   %r = and i8 %s, 7  ; 0b00000111
   ret i8 %r
 }
+
+define i32 @cmp_lshr_cmp(i32 %0) {
+; CHECK-LABEL: @cmp_lshr_cmp(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[TMP0:%.*]], 0
+; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 7, [[TMP0]]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[SHR]], [[TMP0]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[CMP]], [[CMP1]]
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
+; CHECK:       cond.false:
+; CHECK-NEXT:    ret i32 1
+; CHECK:       cond.end:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %cmp = icmp slt i32 %0, 0
+  %shr = lshr i32 7, %0
+  %cmp1 = icmp sgt i32 %0, %shr
+  %or.cond = or i1 %cmp, %cmp1
+  br i1 %or.cond, label %cond.end, label %cond.false
+
+cond.false:                                       ; preds = %entry
+  ret i32 1
+
+cond.end:                                         ; preds = %entry, %cond.false
+  ret i32 0
+}
+