[InstCombine] Support BitTests in ThreeWayComparison. General case, part 1

[mkazantsev]

Summary

In this patch we continue supporting BitTests of the highest bit in the ThreeWayComparison
matcher in the InstCombine (see problem's description in the message of D45854).

This patch adds support for the transform of

%c2 = icmp slt %a, 0
%select1 = select %c2, %Less, %Greater

to

(%a s>> 31) - (%Less - %Greater) + %Greater

This is a part of fix of the bug 37147.

[lebedev.ri]

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

[mkazantsev]

Added context

[mkazantsev]

Formatted tests.

[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

if (match(RHS, m_Zero())) {
       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;
       }
+
+      // Try to recognize:
+      //   select i1 (a < 0), i32 Less, i32 Greater
+      // simplified in form:
+      //   (a s>> 31) & (Less - Greater) + Greater
+      ConstantInt *LessMinusGreater;
+      if (match(SI->getFalseValue(),
+                m_Add(m_And(m_AShr(m_Specific(LHS), m_Specific(ShiftValue)),
+                            m_ConstantInt(LessMinusGreater)),
+                      m_ConstantInt(Greater)))) {
+        APInt LessI = LessMinusGreater->getValue() + Greater->getValue();
+        Less = ConstantInt::get(Greater->getContext(), LessI);
+        return true;
+      }
     }
   }
   return false;
 }
 
 Instruction *InstCombiner::foldICmpSelectConstant(ICmpInst &Cmp,
                                                   SelectInst *Select,
                                                   ConstantInt *C) {

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

 
 callfoo:
   call void @foo(i32 %select2)
   br label %exit
 
 exit:
   ret i32 42
 }
+
+
+; Same as @compare_against_arbitrary_value, but now the three-way comparison
+; returns not idiomatic comparator's result (-1, 0, 1) but some other constants.
+define i32 @compare_against_arbitrary_value_non_idiomatic_1(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 425.
+; CHECK-LABEL: @compare_against_arbitrary_value_non_idiomatic_1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], [[C:%.*]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK:       callfoo:
+; CHECK-NEXT:    call void @foo(i32 425)
+; 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 -6, i32 425
+  %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_non_idiomatic_add(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 425.
+; CHECK-LABEL: @compare_against_zero_non_idiomatic_add(
+; 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:%.*]] = and i32 [[TMP1]], -431
+; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i32 [[TMP2]], 425
+; CHECK-NEXT:    call void @foo(i32 [[TMP3]])
+; 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 -6, i32 425
+  %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
+}