[InstCombine] Fix worklist management when simplifying demanded bits (PR44541)

[nikic]

Summary

When simplifying demanded bits, we currently only report the instruction on which SimplifyDemandedBits was called as changed. However, this is a recursive call, and the actually modified instruction will usually be further up the chain. Additionally, all the intermediate instructions should also be revisited, as additional combines may be possible after the demanded bits simplification. We fix this by explicitly adding them to the worklist.

I originally wrote this patch to address the excessive number of instcombine iterations in an existing test (drops from 5 to 3, which is still not optimal), but found that this also addresses https://bugs.llvm.org/show_bug.cgi?id=44541, though I'm not sure whether this is really a "fix". What happens there is that demanded bits simplifies

%zero = call i16 @passthru(i16 0)
%sub = sub nuw nsw i16 %arg, %zero
%cmp = icmp slt i16 %sub, 0
%ret = select i1 %cmp, i16 0, i16 %sub

to

%zero = call i16 @passthru(i16 0)
%sub = sub nuw nsw i16 %arg, 0
%cmp = icmp slt i16 %sub, 0
%ret = select i1 %cmp, i16 0, i16 %sub

without adding the sub to the worklist (which this patch fixes). Then %cmp = icmp slt i16 %sub, 0 sensibly becomes %cmp = icmp slt i16 %arg, 0. The select is then recognized as a minmax SPF and canonicalized to

%zero = call i16 @passthru(i16 0)
%sub = sub nuw nsw i16 %arg, 0
%cmp = icmp sgt i16 0, %sub
%ret = select i1 %cmp, i16 0, i16 %sub

At which point we enter an infinite combine loop. Adding the %sub to the worklist is sufficient to get it simplified and avoid the issue. I don't know if that's considered enough, or whether there is also a bug in SPF matching or canonicalization here, in the sense that it needs to special-case this type of pattern, on the off-chance that it could appear through another pathway.

[nikic]

llvm/test/Transforms/InstCombine/logical-select.ll

553 ↗

(On Diff #238842)

These changes are caused by https://bugs.llvm.org/show_bug.cgi?id=44521. It's one of two common spurious differences that arise when worklist order changes are made.

[spatel]

This change LGTM.

To fix the infinite loop bug without this change, we could add a clause in canonicalizeMinMaxWithConstant() to avoid creating this:
%cmp = icmp sgt i16 0, %sub

Ie, if the LHS returned by matchSelectPattern() is a constant, swap LHS and RHS because we know we can't create a canonical compare that way. An alternative would be to do that swap within matchSelectPattern() itself. We already have a different LHS/RHS constraint for ABS/NABS on that analysis.

I'm not sure how we can expose that bug with this fix in place though, so might want to make that fix first to be safer?

[nikic]

In D72944#1829322, @spatel wrote:

To fix the infinite loop bug without this change, we could add a clause in canonicalizeMinMaxWithConstant() to avoid creating this:
%cmp = icmp sgt i16 0, %sub

Ie, if the LHS returned by matchSelectPattern() is a constant, swap LHS and RHS because we know we can't create a canonical compare that way. An alternative would be to do that swap within matchSelectPattern() itself. We already have a different LHS/RHS constraint for ABS/NABS on that analysis.

I'm not sure how we can expose that bug with this fix in place though, so might want to make that fix first to be safer?

I don't think this would help. The problem here is not that the icmp operand order is non-canonical (though it would of course be better if we directly created it in canonical order), but that the (SPF) canonical form is based on %sub rather than %arg. This is because SPF has special support for sub-based min/max in https://github.com/llvm-mirror/llvm/blob/2c4ca6832fa6b306ee6a7010bfb80a3f2596f824/lib/Analysis/ValueTracking.cpp#L4687-L4699. I think to avoid this issue interdependently of this patch, we'd have to special case that code to not match the degenerate case where the sub has a zero on the RHS.

[nikic]

This should be using AddDeferred now. But if we do that, we run into https://bugs.llvm.org/show_bug.cgi?id=44754. Additionally, we don't get the desired number of iterations anymore until D73803 and followup work will shake out (a dangling "not" is not getting DCEd and blocks transforms)...

[nikic]

Rebase over D74294.

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

bool InstCombiner::SimplifyDemandedBits(Instruction *I, unsigned OpNo,
                                         const APInt &DemandedMask,
                                         KnownBits &Known,
                                         unsigned Depth) {
   Use &U = I->getOperandUse(OpNo);
   Value *NewVal = SimplifyDemandedUseBits(U.get(), DemandedMask, Known,
                                           Depth, I);
   if (!NewVal) return false;
   U = NewVal;
+  // Add the simplified instruction back to the worklist.
+  Worklist.addValue(U.get());
   return true;
 }
 
 
 /// This function attempts to replace V with a simpler value based on the
 /// demanded bits. When this function is called, it is known that only the bits
 /// set in DemandedMask of the result of V are ever used downstream.
 /// Consequently, depending on the mask and V, it may be possible to replace V

llvm/test/Transforms/InstCombine/pr44541.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S -instcombine -expensive-combines=0 -instcombine-infinite-loop-threshold=3 < %s | FileCheck %s
+; RUN: opt -S -instcombine -expensive-combines=0 -instcombine-infinite-loop-threshold=2 < %s | FileCheck %s
 
 ; This test used to cause an infinite combine loop.
 
 define i16 @passthru(i16 returned %x) {
 ; CHECK-LABEL: @passthru(
 ; CHECK-NEXT:    ret i16 [[X:%.*]]
 ;
   ret i16 %x

llvm/test/Transforms/InstCombine/select-imm-canon.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -instcombine -S | FileCheck %s
+; RUN: opt < %s -instcombine -instcombine-infinite-loop-threshold=3 -S | FileCheck %s
 
 define i8 @single(i32 %A) {
 ; CHECK-LABEL: @single(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[A:%.*]], -128
 ; CHECK-NEXT:    [[L2:%.*]] = select i1 [[TMP0]], i32 [[A]], i32 -128
 ; CHECK-NEXT:    [[CONV7:%.*]] = trunc i32 [[L2]] to i8
 ; CHECK-NEXT:    ret i8 [[CONV7]]