[InstCombine] optimize unsigned icmp of increment

[Deewiant]

Summary

Allows LLVM to optimize sequences like the following:

%add = add nuw i32 %x, 1
%cmp = icmp ugt i32 %add, %y

Into:

%cmp = icmp uge i32 %x, %y

Previously, only signed comparisons were being handled.

Decrements could also be handled, but 'sub nuw %x, 1' is currently canonicalized to 'add %x, -1' in InstCombineAddSub, losing the nuw flag. Removing that canonicalization seems like it might have far-reaching ramifications so I kept this simple for now.

[sanjoy]

I think we can be more aggressive here: the only non-poison value for (X +nuw -1) is -1, and we should be exploiting that.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2832

This looks wrong -- if X and Y are both 0 then uge (X +nuw -1) Y is uge -1 0 == true but ugt X Y is ugt 0 0 = false. Same for some of the cases below.

[Deewiant]

Regarding aggressiveness, simplifying X +nuw -1 to -1 appears worth doing but I figured it deserves a separate change.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2832

D'oh, you're right. I guess this relates to what I said initially about X +nuw -1 vs X -nuw 1: unless I screwed up even more, these properties do hold for subtractions, but we canonicalize them to nuwless additions so it wouldn't be very useful to match them. Would you rather have me remove these cases entirely or do the currently-useless subtraction matching in the hopes that the canonicalization is changed? I can also do that canonicalization change in InstCombineAddSub but I'm worried that it might have far-reaching effects.

[sanjoy]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2832

I'd suggest removing these for now, and adding a TODO about supporting subtractions later if the canonicalization changes.

[spatel]

Not sure if this is easier to read, but if the existing code was rewritten with something like this:

auto getNewPred = [](CmpInst::Predicate P, Value *AddConstant) {
  if (!match(AddConstant, m_AllOnes()) && !match(AddConstant, m_One()))
    return ICmpInst::BAD_ICMP_PREDICATE;

  switch (P) {
  case CmpInst::ICMP_SLT: return CmpInst::ICMP_SLE;
  case CmpInst::ICMP_SGE: return CmpInst::ICMP_SGT;
  case CmpInst::ICMP_SLE: return CmpInst::ICMP_SLT;
  case CmpInst::ICMP_SGT: return CmpInst::ICMP_SGE;
  default: return CmpInst::BAD_ICMP_PREDICATE;
  }
};

Then your patch would just be to add some cases to the switch?

[Deewiant]

In D24700#546763, @spatel wrote:

Not sure if this is easier to read, but if the existing code was rewritten with something like this:

auto getNewPred = [](CmpInst::Predicate P, Value *AddConstant) {
  if (!match(AddConstant, m_AllOnes()) && !match(AddConstant, m_One()))
    return ICmpInst::BAD_ICMP_PREDICATE;

  switch (P) {
  case CmpInst::ICMP_SLT: return CmpInst::ICMP_SLE;
  case CmpInst::ICMP_SGE: return CmpInst::ICMP_SGT;
  case CmpInst::ICMP_SLE: return CmpInst::ICMP_SLT;
  case CmpInst::ICMP_SGT: return CmpInst::ICMP_SGE;
  default: return CmpInst::BAD_ICMP_PREDICATE;
  }
};

Then your patch would just be to add some cases to the switch?

If I understood your meaning, I think using just a function like that would result in this matching too many cases. E.g. if the usage would be something like:

const auto NewPred = getNewPred(Pred);
if (A && NoOp0WrapProblem)
  return new ICmpInst(NewPred, A, Op1);

We'd be performing incorrect transformations like icmp sge (X + 1), Y -> icmp sgt X, Y. So we'd still have to combine specific predicates with specific match calls (and non-null A/C checks) somehow, and at that point I don't think that would really improve readability.

[Deewiant]

Removed the incorrect X +nuw -1 identities, replaced with a TODO about X - 1 identities.

[spatel]

In D24700#547730, @Deewiant wrote:

We'd be performing incorrect transformations like icmp sge (X + 1), Y -> icmp sgt X, Y. So we'd still have to combine specific predicates with specific match calls (and non-null A/C checks) somehow, and at that point I don't think that would really improve readability.

Ah, yes. We should probably have some negative regression tests for those cases. :)
There's code in canonicalizeCmpWithConstant() that does similar matching, so maybe there's still some way to shrink the logic, but it can wait.

[sanjoy]

Please upload with full context. One easy way to do that is to use the arcanist tool.

[Deewiant]

Sorry, I wasn't careful when I did the update. Trying arcanist now.

[sanjoy]

lgtm with nits

test/Transforms/InstCombine/icmp.ll

2769

Add one or two negative checks.

2803

I'd drop the fptosi unless you need it for some reason -- it is distracting.

[Deewiant]

[InstCombine] add negative tests for icmp of inc/dec

test/Transforms/InstCombine/icmp.ll

2769

Added one for each combination of signed/unsigned, LHS/RHS, increment/decrement, for a total of eight.

2803

I copied the idea from the tests for the nsw case further above (e.g. cmp_sgt_rhs_dec). I haven't actually looked into what exactly is happening here: without fptosi the comparisons get flipped so that the increment is on the LHS, which would make these tests equivalent to the earlier ones.

[spatel]

test/Transforms/InstCombine/icmp.ll

2803

The commuting happens because of operand complexity canonicalization. It would be nice to add a comment above here to make that clear.

Please see:
https://llvm.org/bugs/show_bug.cgi?id=28296
https://reviews.llvm.org/D24419
...for more info.

[sanjoy]

lgtm, as stated earlier.

If you don't have commit access yet, let me know and I will commit this for you.

test/Transforms/InstCombine/icmp.ll

2803

Ok.

[spatel]

test/Transforms/InstCombine/icmp.ll

2803

Also note that fptosi is a unary operator, so if we fix PR28296, these tests will silently stop testing the cases that they were hoping to test (sigh).

It might be better if they used a non-nuw 'add' to match the complexity of 'add nuw'.

[Deewiant]

test/Transforms/InstCombine/icmp.ll

2803

If the canonicalization starts working differently the tests would rather start failing, since the icmp CHECKs would no longer match due to the reversed comparison.

Should I duplicate the comment next to every fptosi-using test here? There are 10 of them altogether.

[spatel]

test/Transforms/InstCombine/icmp.ll

2803

If the commuted operand cases don't fold, that's a logic hole (see D24419).
But I don't think that will happen in this case - we have duplicated all of the patterns using NoOp0WrapProblem / NoOp1WrapProblem?

I see now that the tests are scattered all over the place. One comment line is enough for now. Sooner or later, I'll get back to this chunk of code to make it vector-capable, so I would move all of the nsw/nuw tests to their own test file.

If you want to make that change ahead of this patch, feel free, but I wouldn't hold up this patch since it is already approved.

[spatel]

This patch hasn't been committed to trunk yet although it is accepted. Any more changes wanted/needed?

[Deewiant]

D'oh, sorry about leaving this hanging for so long. Apparently I never received an e-mail for your last message about adding a comment for the tests and then never checked back on the web page either. I should be able to add the comment tomorrow and then this is hopefully good to go.

[Deewiant]

• [InstCombine] explain fptosi usage in tests

[spatel]

LGTM - do you have commit access?

[Deewiant]

Nope, I do not have commit access.

lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombiner::foldICmpBinOp(ICmpInst &I) {
   // icmp sge X, (Y + 1) -> icmp sgt X, Y
   if (C && NoOp1WrapProblem && Pred == CmpInst::ICMP_SGE && match(D, m_One()))
     return new ICmpInst(CmpInst::ICMP_SGT, Op0, C);
 
   // icmp slt X, (Y + 1) -> icmp sle X, Y
   if (C && NoOp1WrapProblem && Pred == CmpInst::ICMP_SLT && match(D, m_One()))
     return new ICmpInst(CmpInst::ICMP_SLE, Op0, C);
 
+  // TODO: The subtraction-related identities shown below also hold, but
+  // canonicalization from (X -nuw 1) to (X + -1) means that the combinations
+  // wouldn't happen even if they were implemented.
+  //
+  // icmp ult (X - 1), Y -> icmp ule X, Y
+  // icmp uge (X - 1), Y -> icmp ugt X, Y
+  // icmp ugt X, (Y - 1) -> icmp uge X, Y
+  // icmp ule X, (Y - 1) -> icmp ult X, Y
+
+  // icmp ule (X + 1), Y -> icmp ult X, Y
+  if (A && NoOp0WrapProblem && Pred == CmpInst::ICMP_ULE && match(B, m_One()))
+    return new ICmpInst(CmpInst::ICMP_ULT, A, Op1);
+
+  // icmp ugt (X + 1), Y -> icmp uge X, Y
+  if (A && NoOp0WrapProblem && Pred == CmpInst::ICMP_UGT && match(B, m_One()))
+    return new ICmpInst(CmpInst::ICMP_UGE, A, Op1);
+
+  // icmp uge X, (Y + 1) -> icmp ugt X, Y
+  if (C && NoOp1WrapProblem && Pred == CmpInst::ICMP_UGE && match(D, m_One()))
+    return new ICmpInst(CmpInst::ICMP_UGT, Op0, C);
+
+  // icmp ult X, (Y + 1) -> icmp ule X, Y
+  if (C && NoOp1WrapProblem && Pred == CmpInst::ICMP_ULT && match(D, m_One()))
+    return new ICmpInst(CmpInst::ICMP_ULE, Op0, C);
+
   // if C1 has greater magnitude than C2:
   //  icmp (X + C1), (Y + C2) -> icmp (X + C3), Y
   //  s.t. C3 = C1 - C2
   //
   // if C2 has greater magnitude than C1:
   //  icmp (X + C1), (Y + C2) -> icmp X, (Y + C3)
   //  s.t. C3 = C2 - C1
   if (A && C && NoOp0WrapProblem && NoOp1WrapProblem &&

test/Transforms/InstCombine/icmp.ll

 ; CHECK-LABEL: @f10(
 ; CHECK-NEXT:    [[CMP580:%.*]] = icmp uge i16 %p, mul (i16 zext (i8 ptrtoint (i1 (i16)* @f10 to i8) to i16), i16 zext (i8 ptrtoint (i1 (i16)* @f10 to i8) to i16))
 ; CHECK-NEXT:    ret i1 [[CMP580]]
 ;
   %cmp580 = icmp ule i16 mul (i16 zext (i8 ptrtoint (i1 (i16)* @f10 to i8) to i16), i16 zext (i8 ptrtoint (i1 (i16)* @f10 to i8) to i16)), %p
   ret i1 %cmp580
 }
 
+; Note: fptosi is used in various tests below to ensure that operand complexity
+; canonicalization does not kick in, which would make some of the tests
+; equivalent to one another.
+
 define i1 @cmp_sgt_rhs_dec(float %x, i32 %i) {
 ; CHECK-LABEL: @cmp_sgt_rhs_dec(
 ; CHECK-NEXT:    [[CONV:%.*]] = fptosi float %x to i32
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i32 [[CONV]], %i
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %conv = fptosi float %x to i32
   %dec = sub nsw i32 %i, 1

 ; CHECK: ret i1 [[b]]
 
   %pp = ptrtoint i8* %p to i64
   %qq = ptrtoint i32* %q to i64
   %o = or i64 %pp, %qq
   %b = icmp eq i64 %o, 0
   ret i1 %b
 }
+
+define i1 @icmp_add1_ugt(i32 %x, i32 %y) {
+; CHECK-LABEL: @icmp_add1_ugt(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i32 %x, %y
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %add = add nuw i32 %x, 1
+  %cmp = icmp ugt i32 %add, %y
+  ret i1 %cmp
+}
+
+define i1 @icmp_add1_ule(i32 %x, i32 %y) {
+; CHECK-LABEL: @icmp_add1_ule(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 %x, %y
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %add = add nuw i32 %x, 1
+  %cmp = icmp ule i32 %add, %y
+  ret i1 %cmp
+}
+
+define i1 @cmp_uge_rhs_inc(float %x, i32 %i) {
+; CHECK-LABEL: @cmp_uge_rhs_inc(
+; CHECK-NEXT:    [[CONV:%.*]] = fptosi float %x to i32
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[CONV]], %i
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %conv = fptosi float %x to i32
+  %inc = add nuw i32 %i, 1
+  %cmp = icmp uge i32 %conv, %inc
+  ret i1 %cmp
+}
+
+define i1 @cmp_ult_rhs_inc(float %x, i32 %i) {
+; CHECK-LABEL: @cmp_ult_rhs_inc(
+; CHECK-NEXT:    [[CONV:%.*]] = fptosi float %x to i32
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[CONV]], %i
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %conv = fptosi float %x to i32
+  %inc = add nuw i32 %i, 1
+  %cmp = icmp ult i32 %conv, %inc
+  ret i1 %cmp
+}
+
+define i1 @cmp_sge_lhs_inc(i32 %x, i32 %y) {
+; CHECK-LABEL: @cmp_sge_lhs_inc(
+; CHECK-NEXT:    [[INC:%.*]] = add
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i32 [[INC]], %y
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %inc = add nsw i32 %x, 1
+  %cmp = icmp sge i32 %inc, %y
+  ret i1 %cmp
+}
+
+define i1 @cmp_uge_lhs_inc(i32 %x, i32 %y) {
+; CHECK-LABEL: @cmp_uge_lhs_inc(
+; CHECK-NEXT:    [[INC:%.*]] = add
+; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i32 [[INC]], %y
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %inc = add nuw i32 %x, 1
+  %cmp = icmp uge i32 %inc, %y
+  ret i1 %cmp
+}
+
+define i1 @cmp_sgt_lhs_dec(i32 %x, i32 %y) {
+; CHECK-LABEL: @cmp_sgt_lhs_dec(
+; CHECK-NEXT:    [[DEC:%.*]] = {{add|sub}}
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[DEC]], %y
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %dec = sub nsw i32 %x, 1
+  %cmp = icmp sgt i32 %dec, %y
+  ret i1 %cmp
+}
+
+define i1 @cmp_ugt_lhs_dec(i32 %x, i32 %y) {
+; CHECK-LABEL: @cmp_ugt_lhs_dec(
+; CHECK-NEXT:    [[DEC:%.*]] = {{add|sub}}
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[DEC]], %y
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %dec = sub nuw i32 %x, 1
+  %cmp = icmp ugt i32 %dec, %y
+  ret i1 %cmp
+}
+
+define i1 @cmp_sle_rhs_inc(float %x, i32 %y) {
+; CHECK-LABEL: @cmp_sle_rhs_inc(
+; CHECK-NEXT:    [[CONV:%.*]] = fptosi float %x to i32
+; CHECK-NEXT:    [[INC:%.*]] = add
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i32 [[CONV]], [[INC]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %conv = fptosi float %x to i32
+  %inc = add nsw i32 %y, 1
+  %cmp = icmp sle i32 %conv, %inc
+  ret i1 %cmp
+}
+
+define i1 @cmp_ule_rhs_inc(float %x, i32 %y) {
+; CHECK-LABEL: @cmp_ule_rhs_inc(
+; CHECK-NEXT:    [[CONV:%.*]] = fptosi float %x to i32
+; CHECK-NEXT:    [[INC:%.*]] = add
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[CONV]], [[INC]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %conv = fptosi float %x to i32
+  %inc = add nuw i32 %y, 1
+  %cmp = icmp ule i32 %conv, %inc
+  ret i1 %cmp
+}
+
+define i1 @cmp_slt_rhs_dec(float %x, i32 %y) {
+; CHECK-LABEL: @cmp_slt_rhs_dec(
+; CHECK-NEXT:    [[CONV:%.*]] = fptosi float %x to i32
+; CHECK-NEXT:    [[DEC:%.*]] = {{add|sub}}
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[CONV]], [[DEC]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %conv = fptosi float %x to i32
+  %dec = sub nsw i32 %y, 1
+  %cmp = icmp slt i32 %conv, %dec
+  ret i1 %cmp
+}
+
+define i1 @cmp_ult_rhs_dec(float %x, i32 %y) {
+; CHECK-LABEL: @cmp_ult_rhs_dec(
+; CHECK-NEXT:    [[CONV:%.*]] = fptosi float %x to i32
+; CHECK-NEXT:    [[DEC:%.*]] = {{add|sub}}
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[CONV]], [[DEC]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %conv = fptosi float %x to i32
+  %dec = sub nuw i32 %y, 1
+  %cmp = icmp ult i32 %conv, %dec
+  ret i1 %cmp
+}