[InstCombine] Support BitTests in ThreeWayComparison. Trivial case

[mkazantsev]

Summary

Three-way comparison matcher which is used in some of InstCombine's transforms
is intended to detect the following pattern:

%c1 = icmp eq %a, %b
%c2 = icmp slt %a, %b
%select1 = select %c2, %Less, %Greater
%select2 = select %c1, %Equal, %select2

It works fine if %a and %b are some values about which we know nothing. However
if %b is a constant zero, the situation is different. If we look closer at the example:

%c1 = icmp eq %a, 0
%c2 = icmp slt %a, 0
%select1 = select %c2, %Less, %Greater
%select2 = select %c1, %Equal, %select2

Then we can see that the pattern of %c2 and %select1 is actually a bit test of the
highest bit of %a. There are rules in InstCombine that detect this couple before we
go down to detection of the three-way comparison pattern which is only seen when we
process select2. These transforms may turn %c2, %select1 into something different,
and when we process %select2 we may not be able to recognize the three-way comparison
pattern.

This patch adds support of the following transform:

%c2 = icmp slt %a, 0
%select1 = select %c2, -1, %Greater

to

%shift = ashr %a, 31
%or = or %shift, %Greater

This is a part of fix for bug 37147.

[lebedev.ri]

Please upload all patches with the full context (-U99999).

test/Transforms/InstCombine/three-way-comparison.ll

2

Please use utils/update_test_checks.py (the file's header should say it was used), and don't adjust the ; CHECK lines afterwards manually.

[mkazantsev]

Added context.

[mkazantsev]

Updated tests using script.

[mkazantsev]

We will try another approach to deal with the problem, see discussion in review of D45862.

[mkazantsev]

Abandoning in favour of D46086

lib/Transforms/InstCombine/InstCombineCompares.cpp

bool InstCombiner::matchThreeWayIntCompare(SelectInst *SI, Value *&LHS,
   // they get canonicalized into this form.
 
   // select i1 (a == b), i32 Equal, i32 (select i1 (a < b), i32 Less, i32
   // Greater), where Equal, Less and Greater are placeholders for any three
   // constants.
   ICmpInst::Predicate PredA, PredB;
   if (match(SI->getTrueValue(), m_ConstantInt(Equal)) &&
       match(SI->getCondition(), m_ICmp(PredA, m_Value(LHS), m_Value(RHS))) &&
-      PredA == ICmpInst::ICMP_EQ &&
-      match(SI->getFalseValue(),
+      PredA == ICmpInst::ICMP_EQ) {
+    if (match(SI->getFalseValue(),
               m_Select(m_ICmp(PredB, m_Specific(LHS), m_Specific(RHS)),
                        m_ConstantInt(Less), m_ConstantInt(Greater))) &&
-      PredB == ICmpInst::ICMP_SLT) {
+        PredB == ICmpInst::ICMP_SLT)
       return true;
+
+    if (match(RHS, m_Zero())) {
+      // RHS = 0 is a special case. Here we expected to see something like:
+      //   select i1 (a < 0), i32 Less, i32 Greater
+      // however such select could have been recognized as a bit test of the
+      // highest big by other combine transforms. Here we try to recognize this
+      // select in some particular cases.
+      // Try to recognize:
+      //   select i1 (a < 0), i32 -1, i32 Greater
+      // simplified in form:
+      //   (a s>> 31) | Greater
+      // If %a was negative, then the result of "ashr" is -1 and the result of
+      // "or" is also -1. If %a was non-negative, then the result of "ashr" is 0
+      // and the result of "or" is "Greater".
+      Value *ShiftValue = ConstantInt::get(
+          LHS->getType(), LHS->getType()->getIntegerBitWidth() - 1);
+      if (match(SI->getFalseValue(),
+                m_Or(m_AShr(m_Specific(LHS), m_Specific(ShiftValue)),
+                     m_ConstantInt(Greater)))) {
+        Less = ConstantInt::get(Greater->getType(), -1, true);
+        return true;
+      }
+    }
   }
   return false;
 }
 
 Instruction *InstCombiner::foldICmpSelectConstant(ICmpInst &Cmp,
                                                   SelectInst *Select,
                                                   ConstantInt *C) {
 

test/Transforms/InstCombine/three-way-comparison.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; Test that various patterns of three-ways comparison are recognized.
+
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
+
+declare void @foo(i32 %x)
+
+define i32 @compare_against_arbitrary_value(i32 %x, i32 %c) {
+; TODO: We can prove that if %x s> %c then %x != c, so there should be no actual
+;       calculations in callfoo block. @foo can be invoked with 1. We only do it
+;       for constants that are not 0 currently while it could be generalized.
+; CHECK-LABEL: @compare_against_arbitrary_value(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], [[C:%.*]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[X]], [[C]]
+; CHECK-NEXT:    [[SELECT2:%.*]] = zext i1 [[CMP1]] to i32
+; CHECK-NEXT:    call void @foo(i32 [[SELECT2]])
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 42
+;
+
+entry:
+  %cmp1 = icmp eq i32 %x, %c
+  %cmp2 = icmp slt i32 %x, %c
+  %select1 = select i1 %cmp2, i32 -1, i32 1
+  %select2 = select i1 %cmp1, i32 0, i32 %select1
+  %cond = icmp sgt i32 %select2, 0
+  br i1 %cond, label %callfoo, label %exit
+
+callfoo:
+  call void @foo(i32 %select2)
+  br label %exit
+
+exit:
+  ret i32 42
+}
+
+define i32 @compare_against_zero(i32 %x) {
+; TODO: We can prove that if %x s> %c then %x != c, so there should be no actual
+;       calculations in callfoo block. @foo can be invoked with 1. For some
+;       reasons it does not happen for constant zero while it does happen for
+;       other constants.
+; CHECK-LABEL: @compare_against_zero(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 0
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X]], 31
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], 1
+; CHECK-NEXT:    call void @foo(i32 [[TMP2]])
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 42
+;
+
+entry:
+  %cmp1 = icmp eq i32 %x, 0
+  %cmp2 = icmp slt i32 %x, 0
+  %select1 = select i1 %cmp2, i32 -1, i32 1
+  %select2 = select i1 %cmp1, i32 0, i32 %select1
+  %cond = icmp sgt i32 %select2, 0
+  br i1 %cond, label %callfoo, label %exit
+
+callfoo:
+  call void @foo(i32 %select2)
+  br label %exit
+
+exit:
+  ret i32 42
+}
+
+define i32 @compare_against_one(i32 %x) {
+; CHECK-LABEL: @compare_against_one(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 1
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    call void @foo(i32 1)
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 42
+;
+
+entry:
+  %cmp1 = icmp eq i32 %x, 1
+  %cmp2 = icmp slt i32 %x, 1
+  %select1 = select i1 %cmp2, i32 -1, i32 1
+  %select2 = select i1 %cmp1, i32 0, i32 %select1
+  %cond = icmp sgt i32 %select2, 0
+  br i1 %cond, label %callfoo, label %exit
+
+callfoo:
+  call void @foo(i32 %select2)
+  br label %exit
+
+exit:
+  ret i32 42
+}
+
+define i32 @compare_against_two(i32 %x) {
+; CHECK-LABEL: @compare_against_two(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 2
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    call void @foo(i32 1)
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 42
+;
+
+entry:
+  %cmp1 = icmp eq i32 %x, 2
+  %cmp2 = icmp slt i32 %x, 2
+  %select1 = select i1 %cmp2, i32 -1, i32 1
+  %select2 = select i1 %cmp1, i32 0, i32 %select1
+  %cond = icmp sgt i32 %select2, 0
+  br i1 %cond, label %callfoo, label %exit
+
+callfoo:
+  call void @foo(i32 %select2)
+  br label %exit
+
+exit:
+  ret i32 42
+}
+
+define i32 @compare_against_three(i32 %x) {
+; CHECK-LABEL: @compare_against_three(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 3
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    call void @foo(i32 1)
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 42
+;
+
+entry:
+  %cmp1 = icmp eq i32 %x, 3
+  %cmp2 = icmp slt i32 %x, 3
+  %select1 = select i1 %cmp2, i32 -1, i32 1
+  %select2 = select i1 %cmp1, i32 0, i32 %select1
+  %cond = icmp sgt i32 %select2, 0
+  br i1 %cond, label %callfoo, label %exit
+
+callfoo:
+  call void @foo(i32 %select2)
+  br label %exit
+
+exit:
+  ret i32 42
+}
+
+define i32 @compare_against_four(i32 %x) {
+; CHECK-LABEL: @compare_against_four(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 4
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    call void @foo(i32 1)
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 42
+;
+
+entry:
+  %cmp1 = icmp eq i32 %x, 4
+  %cmp2 = icmp slt i32 %x, 4
+  %select1 = select i1 %cmp2, i32 -1, i32 1
+  %select2 = select i1 %cmp1, i32 0, i32 %select1
+  %cond = icmp sgt i32 %select2, 0
+  br i1 %cond, label %callfoo, label %exit
+
+callfoo:
+  call void @foo(i32 %select2)
+  br label %exit
+
+exit:
+  ret i32 42
+}
+
+define i32 @compare_against_five(i32 %x) {
+; CHECK-LABEL: @compare_against_five(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 5
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    call void @foo(i32 1)
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 42
+;
+
+entry:
+  %cmp1 = icmp eq i32 %x, 5
+  %cmp2 = icmp slt i32 %x, 5
+  %select1 = select i1 %cmp2, i32 -1, i32 1
+  %select2 = select i1 %cmp1, i32 0, i32 %select1
+  %cond = icmp sgt i32 %select2, 0
+  br i1 %cond, label %callfoo, label %exit
+
+callfoo:
+  call void @foo(i32 %select2)
+  br label %exit
+
+exit:
+  ret i32 42
+}
+
+define i32 @compare_against_six(i32 %x) {
+; CHECK-LABEL: @compare_against_six(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 6
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    call void @foo(i32 1)
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 42
+;
+
+entry:
+  %cmp1 = icmp eq i32 %x, 6
+  %cmp2 = icmp slt i32 %x, 6
+  %select1 = select i1 %cmp2, i32 -1, i32 1
+  %select2 = select i1 %cmp1, i32 0, i32 %select1
+  %cond = icmp sgt i32 %select2, 0
+  br i1 %cond, label %callfoo, label %exit
+
+callfoo:
+  call void @foo(i32 %select2)
+  br label %exit
+
+exit:
+  ret i32 42
+}