[InstCombine] Add oneuse checks to shr + cmp constant folds.

[aemerson]

Summary

This change has virtually no code size regressions on the llvm test suite (+ SPECs)
while having these improvements (measured with -Os on Darwin arm64):

External/S.../CFP2006/450.soplex/450.soplex    214024.00      213920.00     -0.0%
External/S...7speed/641.leela_s/641.leela_s     93412.00       93348.00     -0.1%
External/S...17rate/541.leela_r/541.leela_r     93412.00       93348.00     -0.1%
MultiSourc.../Applications/JM/lencod/lencod    426044.00      425748.00     -0.1%
MultiSourc...rks/mediabench/gsm/toast/toast     20436.00       20416.00     -0.1%
MultiSourc...ench/telecomm-gsm/telecomm-gsm     20436.00       20416.00     -0.1%
MultiSourc...Prolangs-C/assembler/assembler     16172.00       16156.00     -0.1%
MultiSourc...nch/mpeg2/mpeg2dec/mpeg2decode     35332.00       35256.00     -0.2%
SingleSour...Adobe-C++/stepanov_abstraction      6904.00        6888.00     -0.2%
External/SPEC/CINT2000/254.gap/254.gap         366060.00      365132.00     -0.3%
MultiSourc...-ProxyApps-C++/PENNANT/PENNANT     79688.00       79484.00     -0.3%
External/S...NT2006/464.h264ref/464.h264ref    352044.00      351132.00     -0.3%
SingleSour...arks/Adobe-C++/functionobjects     15524.00       15480.00     -0.3%
SingleSour...arks/Adobe-C++/stepanov_vector     10728.00       10696.00     -0.3%
SingleSour...ks/Misc-C++/stepanov_container     16900.00       16848.00     -0.3%
MultiSource/Applications/oggenc/oggenc         124184.00      123780.00     -0.3%
SingleSour...tout-C++/Shootout-C++-wordfreq      7060.00        7036.00     -0.3%
MultiSourc...ity-rijndael/security-rijndael      8976.00        8936.00     -0.4%
MultiSource/Benchmarks/McCat/18-imp/imp          9816.00        9772.00     -0.4%
SingleSour...chmarks/Misc-C++/stepanov_v1p2      1772.00        1764.00     -0.5%
MultiSourc...iabench/g721/g721encode/encode      5492.00        5464.00     -0.5%
MultiSourc...rks/McCat/03-testtrie/testtrie      1364.00        1344.00     -1.5%
SingleSour.../execute/GCC-C-execute-pr42833       400.00         364.00     -9.0%

Doing so also prevents a regression described in https://reviews.llvm.org/D143624

[goldstein.w.n]

llvm/test/Transforms/InstCombine/icmp-shr-lt-gt.ll

900

Can you split the tests to a seperate patch so we can see the dif?

[aemerson]

llvm/test/Transforms/InstCombine/icmp-shr-lt-gt.ll

900

You can just look at the test immediately before this one to see what the original codegen is. The difference is just that the code is this case isn’t combined.

[goldstein.w.n]

Where are the codegen improvements coming from?
Better imm values or something? Personally this feels a bit of a hack at the expense of potential ILP.

[aemerson]

In D149918#4320934, @goldstein.w.n wrote:

Where are the codegen improvements coming from?
Better imm values or something? Personally this feels a bit of a hack at the expense of potential ILP.

I'll look into exactly what changed in the codegen tomorrow. Why does this feel like a hack as opposed to all the other hasOneUse() checks in the optimizers?

[goldstein.w.n]

In D149918#4321150, @aemerson wrote:

In D149918#4320934, @goldstein.w.n wrote:

Where are the codegen improvements coming from?
Better imm values or something? Personally this feels a bit of a hack at the expense of potential ILP.

I'll look into exactly what changed in the codegen tomorrow. Why does this feel like a hack as opposed to all the other hasOneUse() checks in the optimizers?

The hasOneUse checks are there to prevent creating more instructions. Even with multi-use on ashr this combine
doesn't create more instructions and does shrink the critical path so it passes muster for an InstCombine.

If it is only darwin arm64 that cares about this change, why not handle it in the backend?

[aemerson]

In D149918#4322154, @goldstein.w.n wrote:

In D149918#4321150, @aemerson wrote:

In D149918#4320934, @goldstein.w.n wrote:

Where are the codegen improvements coming from?
Better imm values or something? Personally this feels a bit of a hack at the expense of potential ILP.

I'll look into exactly what changed in the codegen tomorrow. Why does this feel like a hack as opposed to all the other hasOneUse() checks in the optimizers?

The hasOneUse checks are there to prevent creating more instructions. Even with multi-use on ashr this combine
doesn't create more instructions and does shrink the critical path so it passes muster for an InstCombine.

Ok, that's fair.

If it is only darwin arm64 that cares about this change, why not handle it in the backend?

First of all, I didn't say that only Darwin arm64 cares about this, it's just the system that I happened to run the test suite build on. Secondly, these combines aren't easy to undo (at least one of them involves combing two constants into one). If anything, I think these combines make more sense to do at the codegen level than here but I could be wrong.

So looking at two cases, in oggenc there are quite a few occurrences of select patterns being broken by this combine (because the compare immediate is being munged into something not useful). These result in fewer simplifications which will be both larger and slower.

In MiBench/security-rijndael, we have as you say unfriendly immediate to compares being generated which causes us to have to materialize to registers. This is both a performance and code size hit.

[dmgreen]

I can verify that this fixes the issues, including the other one from https://reviews.llvm.org/D143624#4315468 that looks more difficult to reverse. It may be worth adding some tests like https://godbolt.org/z/cxKrfM4TK. But otherwise it LGTM. Getting more ILP sounds like something the backend should handle, if it is profitable given the constants.

[goldstein.w.n]

In D149918#4325473, @dmgreen wrote:

I can verify that this fixes the issues, including the other one from https://reviews.llvm.org/D143624#4315468 that looks more difficult to reverse. It may be worth adding some tests like https://godbolt.org/z/cxKrfM4TK. But otherwise it LGTM. Getting more ILP sounds like something the backend should handle, if it is profitable given the constants.

I think the generic statement "more ILP is better than less ILP" is fair for instcombine to make. Choosing which constants are profitable (what this patch is trying to approximate), however, still doesn't make sense to me.

[aemerson]

In D149918#4325535, @goldstein.w.n wrote:

In D149918#4325473, @dmgreen wrote:

I can verify that this fixes the issues, including the other one from https://reviews.llvm.org/D143624#4315468 that looks more difficult to reverse. It may be worth adding some tests like https://godbolt.org/z/cxKrfM4TK. But otherwise it LGTM. Getting more ILP sounds like something the backend should handle, if it is profitable given the constants.

I think the generic statement "more ILP is better than less ILP" is fair for instcombine to make.

Do you have an alternative suggestion given that we can’t really undo some of these transforms? ILP is not the only consideration that instcombine has, code size (which we can demonstrate is improved by this change) is an equally important goal.

Choosing which constants are profitable (what this patch is trying to approximate), however, still doesn't make sense to me.

We’re not trying to approximate choosing constants. We’re just adding a one use check.

[nikic]

Please add tests as @dmgreen suggested (and also for whatever pattern you saw in oggenc, if it's a different one) and precommit them. See https://llvm.org/docs/TestingGuide.html#precommit-workflow-for-tests if you are unfamiliar with the precommit workflow.

I'm open to considering this, as ultimately what we care about in InstCombine is what form is most beneficial for further transforms. Blocking this in the multi-use case will lose us some folds that could have made use of the simplified condition, but your data seems to suggest that in practice we lose more by failing to match select patterns. The alternative is to try harder when matching those select patterns.

However, if we want to do this change, you will first have to implement LVI support to effectively undo this when reasoning about condition ranges. That is, LVI needs to know how to determine the range of X given a condition of the form (ashr X, C) pred C2. This works automatically if such comparisons get folded, but requires special support if they don't.

[aemerson]

In D149918#4327542, @nikic wrote:

Please add tests as @dmgreen suggested (and also for whatever pattern you saw in oggenc, if it's a different one) and precommit them. See https://llvm.org/docs/TestingGuide.html#precommit-workflow-for-tests if you are unfamiliar with the precommit workflow.

I'm open to considering this, as ultimately what we care about in InstCombine is what form is most beneficial for further transforms. Blocking this in the multi-use case will lose us some folds that could have made use of the simplified condition, but your data seems to suggest that in practice we lose more by failing to match select patterns. The alternative is to try harder when matching those select patterns.

However, if we want to do this change, you will first have to implement LVI support to effectively undo this when reasoning about condition ranges. That is, LVI needs to know how to determine the range of X given a condition of the form (ashr X, C) pred C2. This works automatically if such comparisons get folded, but requires special support if they don't.

I'm not familiar with LVI, but I plugged in:

define i1 @ashrsgt_01_00(i4 %x, ptr %p) {
  %s = ashr i4 %x, 1
  %c = icmp sgt i4 %s, 0
  ret i1 %c
}

into opt and even after instcombine folds that to a single icmp, LVI doesn't seem to know anything about %x, just that it's overdefined. I assume you mean something else?

[nikic]

@aemerson You need to use the comparison as a branch condition, something like this:

define i1 @test(i4 %x) {
  %s = ashr i4 %x, 1
  %c = icmp sgt i4 %s, 0
  br i1 %c, label %if, label %else
if:
  %c2 = icmp sgt i4 %x, 1
  ret i1 %c2
else:
  ret i1 false
}

CVP will not be able to fold this anymore if the comparison isn't moved to %x in a multi-use scenario (for that matter, InstCombine won't either, which is something it does handle right now).

[aemerson]

Rebase on top of pre-committed tests.

[aemerson]

@nikic Now that the LVI patch has went in, is this ok?

[nikic]

LGTM

llvm/test/Transforms/InstCombine/ashr-icmp-minmax-idiom-break.ll

4 ↗

(On Diff #557818)

Adjust comment.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (ShAmtVal >= TypeBits || ShAmtVal == 0)
     return nullptr;
 
   bool IsExact = Shr->isExact();
   Type *ShrTy = Shr->getType();
   // TODO: If we could guarantee that InstSimplify would handle all of the
   // constant-value-based preconditions in the folds below, then we could assert
   // those conditions rather than checking them. This is difficult because of
   // undef/poison (PR34838).
-  if (IsAShr) {
+  if (IsAShr && Shr->hasOneUse()) {
     if (IsExact || Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_ULT) {
       // When ShAmtC can be shifted losslessly:
       // icmp PRED (ashr exact X, ShAmtC), C --> icmp PRED X, (C << ShAmtC)
       // icmp slt/ult (ashr X, ShAmtC), C --> icmp slt/ult X, (C << ShAmtC)
       APInt ShiftedC = C.shl(ShAmtVal);
       if (ShiftedC.ashr(ShAmtVal) == C)
         return new ICmpInst(Pred, X, ConstantInt::get(ShrTy, ShiftedC));
     }

llvm/test/Transforms/InstCombine/icmp-shr-lt-gt.ll

 ; CHECK-NEXT:    [[C:%.*]] = icmp sgt i4 [[X:%.*]], 1
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %s = ashr i4 %x, 1
   %c = icmp sgt i4 %s, 0
   ret i1 %c
 }
 
+define i1 @ashrsgt_01_00_multiuse(i4 %x, ptr %p) {
+; CHECK-LABEL: @ashrsgt_01_00_multiuse(
+; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
+; CHECK-NEXT:    [[C:%.*]] = icmp sgt i4 [[S]], 0
+; CHECK-NEXT:    store i4 [[S]], ptr [[P:%.*]], align 1
+; CHECK-NEXT:    ret i1 [[C]]
+;
+  %s = ashr i4 %x, 1
+  %c = icmp sgt i4 %s, 0
+  store i4 %s, ptr %p
+  ret i1 %c
+}
+
 define i1 @ashrsgt_01_01(i4 %x) {
 ; CHECK-LABEL: @ashrsgt_01_01(
 ; CHECK-NEXT:    [[C:%.*]] = icmp sgt i4 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %s = ashr i4 %x, 1
   %c = icmp sgt i4 %s, 1
   ret i1 %c

llvm/test/Transforms/InstCombine/icmp-shr.ll

 ; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[X:%.*]], 1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 0 ; 0b0000
   ret i1 %r
 }
 
+define i1 @ashr_ugt_0_multiuse(i4 %x, ptr %p) {
+; CHECK-LABEL: @ashr_ugt_0_multiuse(
+; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[X]], 1
+; CHECK-NEXT:    store i4 [[S]], ptr [[P:%.*]], align 1
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %s = ashr i4 %x, 1
+  %r = icmp ugt i4 %s, 0 ; 0b0000
+  store i4 %s, ptr %p
+  ret i1 %r
+}
+
 define i1 @ashr_ugt_1(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_1(
 ; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 1 ; 0b0001
   ret i1 %r

 ; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[X:%.*]], 4
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 2 ; 0b0010
   ret i1 %r
 }
 
+define i1 @ashr_ult_2_multiuse(i4 %x, ptr %p) {
+; CHECK-LABEL: @ashr_ult_2_multiuse(
+; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[X]], 4
+; CHECK-NEXT:    store i4 [[S]], ptr [[P:%.*]], align 1
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %s = ashr i4 %x, 1
+  %r = icmp ult i4 %s, 2 ; 0b0010
+  store i4 %s, ptr %p
+  ret i1 %r
+}
+
 ; negative test
 
 define i1 @ashr_ult_3(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_3(
 ; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[X:%.*]], 6
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1