[InstCombine] convert 'isPositive' and 'isNegative' vector comparisons to shifts (PR26701, PR26819)

[spatel]

Summary

This is an update of:
http://reviews.llvm.org/rL262424

That was reverted because it caused failures in an end-to-end clang AArch64 test ( clang/test/CodeGen/aarch64-neon-misc.c ).
That failure no longer happens after:
http://reviews.llvm.org/rL262623
Ie, the AArch64 backend recognizes the pattern produced by this patch and generates the expected code.

There is an end-to-end improvement for AArch64 from this patch that is not currently tested anywhere AFAIK. That is noted in PR26819:
https://llvm.org/bugs/show_bug.cgi?id=26819

This source:

// Are elements of 'a' <= -1? Ie, is 'a' negative?
int32x2_t test_vcle_s32(int32x2_t a) {
  return vcle_s32(a, vceq_s32(a, a) );
}

Becomes:

test_vcle_s32:
  sshr	v0.2s, v0.2s, #31
  ret

Instead of the current:

test_vcle_s32:
  movi	d1, #0xffffffffffffffff
  cmge	v0.2s, v1.2s, v0.2s
  ret

Given the current controversy about end-to-end testing, I have not included a test for that in this patch. But it seems to me that we should have that kind of test *somewhere* to make sure that IR optimizations are correctly handled by a backend. In other words, if that current end-to-end AArch clang test didn't exist, I wouldn't have known that this patch pessimized AArch64. It's entirely possible that some other backend will still be pessimized by this change because it has no equivalent end-to-end test. The difference is sufficiently small that it is unlikely to show up as a perf regression anywhere, but it undoubtedly would be a regression.

[spatel]

Ping.
I hope my FUD-inducing summary didn't shoot this patch in the foot. :)

[spatel]

Ping * 2.

[spatel]

Ping * 3.

[mehdi_amini]

lib/Transforms/InstCombine/InstCombineCasts.cpp

985 ↗

(On Diff #49754)

I usually see canonicalization as something that is target independent, and then after optimization the lowering can adjust toward something that the target will "like" (ultimately the SDAG legalizer is doing this). Any comment?

[spatel]

lib/Transforms/InstCombine/InstCombineCasts.cpp

985 ↗

(On Diff #49754)

That sounds right to me in general. But are you suggesting that we should do the comparison canonicalizations for vector types too? Ie, (x <=s -1) --> (x <s 0).

My code comment here is my assumption about why we *don't* do that - vector ISAs may have limited functionality, so some backends (x86 at least) would have to then undo that canonicalization.

I see 2 reasons to justify this patch as written:

1. The shift transform is an actual IR optimization, not just a canonicalization - it reduces the instruction count and/or complexity of the IR.
2. We're already doing this (shift) transform for some comparisons, so we might as well include the other, related comparison operators where it can apply.

[spatel]

Ping * 4.

[spatel]

Ping * 5.

[mehdi_amini]

Someone should provide some feedback on the vector canonicalization question (Chandler? David?)

[spatel]

In D17859#395086, @joker.eph wrote:

Someone should provide some feedback on the vector canonicalization question (Chandler? David?)

Adding Chandler to reviewers.

[spatel]

Ping * 6.

For reference, some other questions about where we draw the 'canonical IR' line:
http://lists.llvm.org/pipermail/llvm-dev/2016-April/098154.html
https://llvm.org/bugs/show_bug.cgi?id=27343
https://llvm.org/bugs/show_bug.cgi?id=24766#c2

We try to maintain our target-independent idealism in IR, particularly in InstCombine, but we do make concessions for practical target constraints.

For this (really minor!) case, I think the potentially limited range of vector functionality is reason not to try hard to canonicalize vector comparisons in the same way as integer comparisons.

[hfinkel]

lib/Transforms/InstCombine/InstCombineCasts.cpp

985 ↗

(On Diff #49754)

That sounds right to me in general. But are you suggesting that we should do the comparison canonicalizations for vector types too? Ie, (x <=s -1) --> (x <s 0).

Yes. Having different canonicalization rules for vectors and scalars is confusing, and leads to problems like this. Keeping track of what we do, in general, is hard. Keeping track of different rules for scalars and vectors should be avoided if possible.

My code comment here is my assumption about why we *don't* do that - vector ISAs may have limited functionality, so some backends (x86 at least) would have to then undo that canonicalization.

Often times these things are just oversights, or were done a long time ago when the backend infrastructure was not as mature. I don't know how we ended up in this state on this particular issue, but given that matching this in the backend seems fairly easy (in either form), we should do that.

[chandlerc]

lib/Transforms/InstCombine/InstCombineCasts.cpp

985 ↗

(On Diff #49754)

+1 to what Hal said.

We should canonicalize vectors and scalars aggressively and solve problems that arise in the backend.

We shouldn't add more code to match non-canonical patterns in instcombine, we should fix the canonicalization.

[spatel]

lib/Transforms/InstCombine/InstCombineCasts.cpp

985 ↗

(On Diff #49754)

Some day I'll get canonicalization right. :)

I've drafted a patch to do as suggested here, but now I'm wondering if there's another reason not to treat vectors and scalars the same for the purposes of icmp with constant: there's a fundamental difference between vector and scalar icmp ops.

Example:
icmp uge i32 %x, 0 --> true
icmp uge <2 x i32> %x, <i32 0, i32 42> --> ?

We want to subtract 1 from the constant operand and canonicalize to 'ugt' here. We don't have to worry about the first case in InstCombiner::visitICmpInst() because InstSimplify takes care of those kinds of edge cases. That doesn't exist for vectors (although it probably should for a splatted constant vector).

Is it still worth doing this canonicalization if it doesn't work in general?

[spatel]

Patch updated:
I didn't see a reply to my latest question: is it really a canonicalization if it only works some of the time?
But here's a semi-canonicalization patch for comparison to the earlier draft.

[chandlerc]

lib/Transforms/InstCombine/InstCombineCasts.cpp

985 ↗

(On Diff #49754)

This is a great question.

I'm not sure. I can see at least three options:

1. Canonicalize to ugt when we can, but not always, much as your code does here. Teach passes that assume we canonicalized on ugt to consider the uge case for vectors.

2. Drop all canonicalizing to ugt, and audit the code that matches on ugt to also match on uge.

3. Canonicalize the vector case to ugt as well by replacing the boundary elements with undef, and then inserting a 'true' over the resulting i1 lane coming out of the icmp.

While #1 is clearly the simplest and safest approach, I'm not sure what the right long term solution is here. #3 seems really appealing if it works, but I'm worried that it the insertion of the true will end up causing problems downstream. Might be worth some experimentation though.

[spatel]

lib/Transforms/InstCombine/InstCombineCasts.cpp

985 ↗

(On Diff #49754)

For #3, we would have to add insertelements and/or shufflevectors to the IR, right? Here we reach a strange place where bigger IR is "more canonical" than smaller IR?

I'm still holding out hope for option #2 (the earlier draft of this patch) because:

1. It's just ~2 lines of code to catch a very specific optimization (turning a compare into a shift).
2. The odds that the canonicalization is actually helpful for vector integer targets seem slim.

In this draft, I've added a lot of code, and it's really only that one tiny shift transform that I can see as a benefit. It's just not worth the effort IMO.

[chandlerc]

lib/Transforms/InstCombine/InstCombineCasts.cpp

985 ↗

(On Diff #49754)

For #3, yes, we'd add an instruction which clobbers a lane with a constant. The challenging part of vectors is modeling partial constants. For almost all cases I wouldn't expect it to be worth it but for i1 vectors I think it might be OK. But I'm not sure yet.

Regarding #2, I don't really understand why this is only for turning a compare into a shift. There are a *lot* of places in the code that match on ICMP_UGT only and not on ICMP_UGE... I'm also surprised actually that these are that related because the new patch only seems to touch UGE and UGT not SGE and SGT...

[spatel]

lib/Transforms/InstCombine/InstCombineCasts.cpp

985 ↗

(On Diff #49754)

I agree that there's lots of potential ICMP transforms, but I just don't see that in actual vector code. Maybe I'm just not imagining the possibilities well enough.

Another potential problem is that we just don't have enough of the IR plumbing done so that it can trigger follow-on transforms (eg, https://llvm.org/bugs/show_bug.cgi?id=24942 ).

The new patch (doing the canonicalization when possible but ignoring the edge cases) is enabled for all of UGE/ULE/SGE/SLE. Did I miss something? I am experiencing some weirdness in Phab from replying inline to a spot that only exists in the old version of the patch. :)

[chandlerc]

LGTM -- I think this is the best option we have for now.

I think we should add support for the ge/le icmp variants to any transforms that we end up with test cases for where we have a constant at a boundary here. This is no worse than completely removing the canonicalization, but lets us be lazy and allows the easy cases to still collapse to the same predictable structure.

lib/Transforms/InstCombine/InstCombineCompares.cpp

3145–3146 ↗

(On Diff #57102)

I'd not have the comment talk about a missing instsimplify pass as we'll likely fail to remove it when adding that...

[spatel]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3145–3146 ↗

(On Diff #57102)

Good point. I'll replace this with a blurb about the trade-offs that we discussed here. Thanks!

llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp

case ICmpInst::ICMP_SLE:
       return new ICmpInst(ICmpInst::ICMP_SLT, Op0, Builder.getInt(Op1Val + 1));
     case ICmpInst::ICMP_UGE:
       assert(!Op1C->isMinValue(false)); // A >=u MIN -> TRUE
       return new ICmpInst(ICmpInst::ICMP_UGT, Op0, Builder.getInt(Op1Val - 1));
     case ICmpInst::ICMP_SGE:
       assert(!Op1C->isMinValue(true));  // A >=s MIN -> TRUE
       return new ICmpInst(ICmpInst::ICMP_SGT, Op0, Builder.getInt(Op1Val - 1));
     default:
-      break;
-    }
+      return nullptr;
+    }
+
+  // The usual vector types are ConstantDataVector. Exotic vector types are
+  // ConstantVector. They both derive from Constant.
+  if (isa<ConstantDataVector>(Op1) || isa<ConstantVector>(Op1)) {
+    Constant *Op1C = cast<Constant>(Op1);
+    Type *Op1Type = Op1->getType();
+    unsigned NumElts = Op1Type->getVectorNumElements();
+
+    // Set the new comparison predicate and splat a vector of 1 or -1 to
+    // increment or decrement the vector constants. But first, check that no
+    // elements of the constant vector would overflow/underflow when we
+    // increment/decrement the constants.
+    //
+    // TODO? If the edge cases for vectors were guaranteed to be handled as they
+    // are for scalar, we could remove the min/max checks here. However, to do
+    // that, we would have to use insertelement/shufflevector to replace edge
+    // values.
+    
+    CmpInst::Predicate NewPred;
+    Constant *OneOrNegOne = nullptr;
+    switch (I.getPredicate()) {
+    case ICmpInst::ICMP_ULE:
+      for (unsigned i = 0; i != NumElts; ++i)
+        if (cast<ConstantInt>(Op1C->getAggregateElement(i))->isMaxValue(false))
+          return nullptr;
+      NewPred = ICmpInst::ICMP_ULT;
+      OneOrNegOne = ConstantInt::get(Op1Type, 1);
+      break;
+    case ICmpInst::ICMP_SLE:
+      for (unsigned i = 0; i != NumElts; ++i)
+        if (cast<ConstantInt>(Op1C->getAggregateElement(i))->isMaxValue(true))
+          return nullptr;
+      NewPred = ICmpInst::ICMP_SLT;
+      OneOrNegOne = ConstantInt::get(Op1Type, 1);
+      break;
+    case ICmpInst::ICMP_UGE:
+      for (unsigned i = 0; i != NumElts; ++i)
+        if (cast<ConstantInt>(Op1C->getAggregateElement(i))->isMinValue(false))
+          return nullptr;
+      NewPred = ICmpInst::ICMP_UGT;
+      OneOrNegOne = ConstantInt::get(Op1Type, -1);
+      break;
+    case ICmpInst::ICMP_SGE:
+      for (unsigned i = 0; i != NumElts; ++i)
+        if (cast<ConstantInt>(Op1C->getAggregateElement(i))->isMinValue(true))
+          return nullptr;
+      NewPred = ICmpInst::ICMP_SGT;
+      OneOrNegOne = ConstantInt::get(Op1Type, -1);
+      break;
+    default:
+      return nullptr;
     }
 
-  // TODO: Handle vectors.
+    return new ICmpInst(NewPred, Op0, ConstantExpr::getAdd(Op1C, OneOrNegOne));
+  }
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
   bool Changed = false;
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   unsigned Op0Cplxity = getComplexity(Op0);

llvm/trunk/test/Transforms/InstCombine/icmp-vec.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+; Canonicalize vector ge/le comparisons with constants to gt/lt.
+
+; Normal types are ConstantDataVectors. Test the constant values adjacent to the
+; min/max values that we're not allowed to transform.
+
+define <2 x i1> @sge(<2 x i8> %x) {
+; CHECK-LABEL: @sge(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <2 x i8> %x, <i8 -128, i8 126>
+; CHECK-NEXT:    ret <2 x i1> [[CMP]]
+;
+  %cmp = icmp sge <2 x i8> %x, <i8 -127, i8 -129>
+  ret <2 x i1> %cmp
+}
+
+define <2 x i1> @uge(<2 x i8> %x) {
+; CHECK-LABEL: @uge(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt <2 x i8> %x, <i8 -2, i8 0>
+; CHECK-NEXT:    ret <2 x i1> [[CMP]]
+;
+  %cmp = icmp uge <2 x i8> %x, <i8 -1, i8 1>
+  ret <2 x i1> %cmp
+}
+
+define <2 x i1> @sle(<2 x i8> %x) {
+; CHECK-LABEL: @sle(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <2 x i8> %x, <i8 127, i8 -127>
+; CHECK-NEXT:    ret <2 x i1> [[CMP]]
+;
+  %cmp = icmp sle <2 x i8> %x, <i8 126, i8 128>
+  ret <2 x i1> %cmp
+}
+
+define <2 x i1> @ule(<2 x i8> %x) {
+; CHECK-LABEL: @ule(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult <2 x i8> %x, <i8 -1, i8 1>
+; CHECK-NEXT:    ret <2 x i1> [[CMP]]
+;
+  %cmp = icmp ule <2 x i8> %x, <i8 254, i8 0>
+  ret <2 x i1> %cmp
+}
+
+; Weird types are ConstantVectors, not ConstantDataVectors. For an i3 type:
+; Signed min = -4
+; Unsigned min = 0
+; Signed max = 3
+; Unsigned max = 7
+
+define <3 x i1> @sge_weird(<3 x i3> %x) {
+; CHECK-LABEL: @sge_weird(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <3 x i3> %x, <i3 -4, i3 2, i3 -1>
+; CHECK-NEXT:    ret <3 x i1> [[CMP]]
+;
+  %cmp = icmp sge <3 x i3> %x, <i3 -3, i3 -5, i3 0>
+  ret <3 x i1> %cmp
+}
+
+define <3 x i1> @uge_weird(<3 x i3> %x) {
+; CHECK-LABEL: @uge_weird(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt <3 x i3> %x, <i3 -2, i3 0, i3 1>
+; CHECK-NEXT:    ret <3 x i1> [[CMP]]
+;
+  %cmp = icmp uge <3 x i3> %x, <i3 -1, i3 1, i3 2>
+  ret <3 x i1> %cmp
+}
+
+define <3 x i1> @sle_weird(<3 x i3> %x) {
+; CHECK-LABEL: @sle_weird(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <3 x i3> %x, <i3 3, i3 -3, i3 1>
+; CHECK-NEXT:    ret <3 x i1> [[CMP]]
+;
+  %cmp = icmp sle <3 x i3> %x, <i3 2, i3 4, i3 0>
+  ret <3 x i1> %cmp
+}
+
+define <3 x i1> @ule_weird(<3 x i3> %x) {
+; CHECK-LABEL: @ule_weird(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult <3 x i3> %x, <i3 -1, i3 1, i3 2>
+; CHECK-NEXT:    ret <3 x i1> [[CMP]]
+;
+  %cmp = icmp ule <3 x i3> %x, <i3 6, i3 0, i3 1>
+  ret <3 x i1> %cmp
+}
+
+; We can't do the transform if any constants are already at the limits.
+
+define <2 x i1> @sge_min(<2 x i3> %x) {
+; CHECK-LABEL: @sge_min(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sge <2 x i3> %x, <i3 -4, i3 1>
+; CHECK-NEXT:    ret <2 x i1> [[CMP]]
+;
+  %cmp = icmp sge <2 x i3> %x, <i3 -4, i3 1>
+  ret <2 x i1> %cmp
+}
+
+define <2 x i1> @uge_min(<2 x i3> %x) {
+; CHECK-LABEL: @uge_min(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp uge <2 x i3> %x, <i3 1, i3 0>
+; CHECK-NEXT:    ret <2 x i1> [[CMP]]
+;
+  %cmp = icmp uge <2 x i3> %x, <i3 1, i3 0>
+  ret <2 x i1> %cmp
+}
+
+define <2 x i1> @sle_max(<2 x i3> %x) {
+; CHECK-LABEL: @sle_max(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sle <2 x i3> %x, <i3 1, i3 3>
+; CHECK-NEXT:    ret <2 x i1> [[CMP]]
+;
+  %cmp = icmp sle <2 x i3> %x, <i3 1, i3 3>
+  ret <2 x i1> %cmp
+}
+
+define <2 x i1> @ule_max(<2 x i3> %x) {
+; CHECK-LABEL: @ule_max(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule <2 x i3> %x, <i3 -1, i3 1>
+; CHECK-NEXT:    ret <2 x i1> [[CMP]]
+;
+  %cmp = icmp ule <2 x i3> %x, <i3 7, i3 1>
+  ret <2 x i1> %cmp
+}
+

llvm/trunk/test/Transforms/LoopVectorize/if-conversion.ll

 ;       sum += A[i] + 2;
 ;
 ;   return sum;
 ; }
 
 ;CHECK-LABEL: @reduction_func(
 ;CHECK: load <4 x i32>
 ;CHECK: add <4 x i32>
-;CHECK: icmp sle <4 x i32>
+;CHECK: icmp slt <4 x i32>
 ;CHECK: select <4 x i1>
 ;CHECK: ret i32
 define i32 @reduction_func(i32* nocapture %A, i32 %n) nounwind uwtable readonly ssp {
 entry:
   %cmp10 = icmp sgt i32 %n, 0
   br i1 %cmp10, label %for.body, label %for.end
 
 for.body:                                         ; preds = %entry, %for.inc