Skip to content

Commit d640641

Browse files
rotaterightrotateright
committedDec 15, 2016
[InstCombine] add folds for icmp (smin X, Y), X
Min/max canonicalization (r287585) exposes the fact that we're missing combines for min/max patterns. This patch won't solve the example that was attached to that thread, so something else still needs fixing. The line between InstCombine and InstSimplify gets blurry here because sometimes the icmp instruction that we want to fold to already exists, but sometimes it's the swapped form of what we want. Corresponding changes for smax/umin/umax to follow. Differential Revision: https://reviews.llvm.org/D27531 llvm-svn: 289855
·
llvmorg-21-initllvmorg-4.0.0-rc1
1 parent e793966 commit d640641

File tree

3 files changed

+59
-36
lines changed

3 files changed

+59
-36
lines changed
 

‎llvm/include/llvm/IR/PatternMatch.h

+10
Original file line numberDiff line numberDiff line change
@@ -1349,6 +1349,16 @@ m_c_Xor(const LHS &L, const RHS &R) {
13491349
return m_CombineOr(m_Xor(L, R), m_Xor(R, L));
13501350
}
13511351

1352+
// TODO: Add the related SMax, UMax, UMin commuted matchers.
1353+
1354+
/// Matches an SMin with LHS and RHS in either order.
1355+
template<typename LHS, typename RHS>
1356+
inline match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>,
1357+
MaxMin_match<ICmpInst, RHS, LHS, smin_pred_ty>>
1358+
m_c_SMin(const LHS &L, const RHS &R) {
1359+
return m_CombineOr(m_SMin(L, R), m_SMin(R, L));
1360+
}
1361+
13521362
} // end namespace PatternMatch
13531363
} // end namespace llvm
13541364

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

+37
Original file line numberDiff line numberDiff line change
@@ -3030,6 +3030,40 @@ Instruction *InstCombiner::foldICmpBinOp(ICmpInst &I) {
30303030
return nullptr;
30313031
}
30323032

3033+
/// Fold icmp Pred smin(X, Y), X.
3034+
static Instruction *foldICmpWithSMin(ICmpInst &Cmp) {
3035+
ICmpInst::Predicate Pred = Cmp.getPredicate();
3036+
Value *Op0 = Cmp.getOperand(0);
3037+
Value *X = Cmp.getOperand(1);
3038+
3039+
// TODO: This should be expanded to handle smax/umax/umin.
3040+
3041+
// Canonicalize minimum operand to LHS of the icmp.
3042+
if (match(X, m_c_SMin(m_Specific(Op0), m_Value()))) {
3043+
std::swap(Op0, X);
3044+
Pred = Cmp.getSwappedPredicate();
3045+
}
3046+
3047+
Value *Y;
3048+
if (!match(Op0, m_c_SMin(m_Specific(X), m_Value(Y))))
3049+
return nullptr;
3050+
3051+
// smin(X, Y) == X --> X <= Y
3052+
// smin(X, Y) >= X --> X <= Y
3053+
if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_SGE)
3054+
return new ICmpInst(ICmpInst::ICMP_SLE, X, Y);
3055+
3056+
// smin(X, Y) != X --> X > Y
3057+
// smin(X, Y) < X --> X > Y
3058+
if (Pred == CmpInst::ICMP_NE || Pred == CmpInst::ICMP_SLT)
3059+
return new ICmpInst(ICmpInst::ICMP_SGT, X, Y);
3060+
3061+
// These cases should be handled in InstSimplify:
3062+
// smin(X, Y) <= X --> true
3063+
// smin(X, Y) > X --> false
3064+
return nullptr;
3065+
}
3066+
30333067
Instruction *InstCombiner::foldICmpEquality(ICmpInst &I) {
30343068
if (!I.isEquality())
30353069
return nullptr;
@@ -4277,6 +4311,9 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
42774311
if (Instruction *Res = foldICmpBinOp(I))
42784312
return Res;
42794313

4314+
if (Instruction *Res = foldICmpWithSMin(I))
4315+
return Res;
4316+
42804317
{
42814318
Value *A, *B;
42824319
// Transform (A & ~B) == 0 --> (A & B) != 0

‎llvm/test/Transforms/InstCombine/smin-icmp.ll

+12-36
Original file line numberDiff line numberDiff line change
@@ -11,9 +11,7 @@
1111

1212
define i1 @eq_smin1(i32 %x, i32 %y) {
1313
; CHECK-LABEL: @eq_smin1(
14-
; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 %x, %y
15-
; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP1]], i32 %x, i32 %y
16-
; CHECK-NEXT: [[CMP2:%.*]] = icmp eq i32 [[SEL]], %x
14+
; CHECK-NEXT: [[CMP2:%.*]] = icmp sle i32 %x, %y
1715
; CHECK-NEXT: ret i1 [[CMP2]]
1816
;
1917
%cmp1 = icmp slt i32 %x, %y
@@ -26,9 +24,7 @@ define i1 @eq_smin1(i32 %x, i32 %y) {
2624

2725
define i1 @eq_smin2(i32 %x, i32 %y) {
2826
; CHECK-LABEL: @eq_smin2(
29-
; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 %y, %x
30-
; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP1]], i32 %y, i32 %x
31-
; CHECK-NEXT: [[CMP2:%.*]] = icmp eq i32 [[SEL]], %x
27+
; CHECK-NEXT: [[CMP2:%.*]] = icmp sle i32 %x, %y
3228
; CHECK-NEXT: ret i1 [[CMP2]]
3329
;
3430
%cmp1 = icmp slt i32 %y, %x
@@ -42,9 +38,7 @@ define i1 @eq_smin2(i32 %x, i32 %y) {
4238
define i1 @eq_smin3(i32 %a, i32 %y) {
4339
; CHECK-LABEL: @eq_smin3(
4440
; CHECK-NEXT: [[X:%.*]] = add i32 %a, 3
45-
; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 [[X]], %y
46-
; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP1]], i32 [[X]], i32 %y
47-
; CHECK-NEXT: [[CMP2:%.*]] = icmp eq i32 [[X]], [[SEL]]
41+
; CHECK-NEXT: [[CMP2:%.*]] = icmp sle i32 [[X]], %y
4842
; CHECK-NEXT: ret i1 [[CMP2]]
4943
;
5044
%x = add i32 %a, 3 ; thwart complexity-based canonicalization
@@ -59,9 +53,7 @@ define i1 @eq_smin3(i32 %a, i32 %y) {
5953
define i1 @eq_smin4(i32 %a, i32 %y) {
6054
; CHECK-LABEL: @eq_smin4(
6155
; CHECK-NEXT: [[X:%.*]] = add i32 %a, 3
62-
; CHECK-NEXT: [[CMP1:%.*]] = icmp sgt i32 [[X]], %y
63-
; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP1]], i32 %y, i32 [[X]]
64-
; CHECK-NEXT: [[CMP2:%.*]] = icmp eq i32 [[X]], [[SEL]]
56+
; CHECK-NEXT: [[CMP2:%.*]] = icmp sle i32 [[X]], %y
6557
; CHECK-NEXT: ret i1 [[CMP2]]
6658
;
6759
%x = add i32 %a, 3 ; thwart complexity-based canonicalization
@@ -75,9 +67,7 @@ define i1 @eq_smin4(i32 %a, i32 %y) {
7567

7668
define i1 @sge_smin1(i32 %x, i32 %y) {
7769
; CHECK-LABEL: @sge_smin1(
78-
; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 %x, %y
79-
; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP1]], i32 %x, i32 %y
80-
; CHECK-NEXT: [[CMP2:%.*]] = icmp sge i32 [[SEL]], %x
70+
; CHECK-NEXT: [[CMP2:%.*]] = icmp sle i32 %x, %y
8171
; CHECK-NEXT: ret i1 [[CMP2]]
8272
;
8373
%cmp1 = icmp slt i32 %x, %y
@@ -90,9 +80,7 @@ define i1 @sge_smin1(i32 %x, i32 %y) {
9080

9181
define i1 @sge_smin2(i32 %x, i32 %y) {
9282
; CHECK-LABEL: @sge_smin2(
93-
; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 %y, %x
94-
; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP1]], i32 %y, i32 %x
95-
; CHECK-NEXT: [[CMP2:%.*]] = icmp sge i32 [[SEL]], %x
83+
; CHECK-NEXT: [[CMP2:%.*]] = icmp sle i32 %x, %y
9684
; CHECK-NEXT: ret i1 [[CMP2]]
9785
;
9886
%cmp1 = icmp slt i32 %y, %x
@@ -106,9 +94,7 @@ define i1 @sge_smin2(i32 %x, i32 %y) {
10694
define i1 @sge_smin3(i32 %a, i32 %y) {
10795
; CHECK-LABEL: @sge_smin3(
10896
; CHECK-NEXT: [[X:%.*]] = add i32 %a, 3
109-
; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 [[X]], %y
110-
; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP1]], i32 [[X]], i32 %y
111-
; CHECK-NEXT: [[CMP2:%.*]] = icmp sle i32 [[X]], [[SEL]]
97+
; CHECK-NEXT: [[CMP2:%.*]] = icmp sle i32 [[X]], %y
11298
; CHECK-NEXT: ret i1 [[CMP2]]
11399
;
114100
%x = add i32 %a, 3 ; thwart complexity-based canonicalization
@@ -123,9 +109,7 @@ define i1 @sge_smin3(i32 %a, i32 %y) {
123109
define i1 @sge_smin4(i32 %a, i32 %y) {
124110
; CHECK-LABEL: @sge_smin4(
125111
; CHECK-NEXT: [[X:%.*]] = add i32 %a, 3
126-
; CHECK-NEXT: [[CMP1:%.*]] = icmp sgt i32 [[X]], %y
127-
; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP1]], i32 %y, i32 [[X]]
128-
; CHECK-NEXT: [[CMP2:%.*]] = icmp sle i32 [[X]], [[SEL]]
112+
; CHECK-NEXT: [[CMP2:%.*]] = icmp sle i32 [[X]], %y
129113
; CHECK-NEXT: ret i1 [[CMP2]]
130114
;
131115
%x = add i32 %a, 3 ; thwart complexity-based canonicalization
@@ -139,9 +123,7 @@ define i1 @sge_smin4(i32 %a, i32 %y) {
139123

140124
define i1 @ne_smin1(i32 %x, i32 %y) {
141125
; CHECK-LABEL: @ne_smin1(
142-
; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 %x, %y
143-
; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP1]], i32 %x, i32 %y
144-
; CHECK-NEXT: [[CMP2:%.*]] = icmp ne i32 [[SEL]], %x
126+
; CHECK-NEXT: [[CMP2:%.*]] = icmp sgt i32 %x, %y
145127
; CHECK-NEXT: ret i1 [[CMP2]]
146128
;
147129
%cmp1 = icmp slt i32 %x, %y
@@ -168,9 +150,7 @@ define i1 @ne_smin2(i32 %x, i32 %y) {
168150
define i1 @ne_smin3(i32 %a, i32 %y) {
169151
; CHECK-LABEL: @ne_smin3(
170152
; CHECK-NEXT: [[X:%.*]] = add i32 %a, 3
171-
; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 [[X]], %y
172-
; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP1]], i32 [[X]], i32 %y
173-
; CHECK-NEXT: [[CMP2:%.*]] = icmp ne i32 [[X]], [[SEL]]
153+
; CHECK-NEXT: [[CMP2:%.*]] = icmp sgt i32 [[X]], %y
174154
; CHECK-NEXT: ret i1 [[CMP2]]
175155
;
176156
%x = add i32 %a, 3 ; thwart complexity-based canonicalization
@@ -199,9 +179,7 @@ define i1 @ne_smin4(i32 %a, i32 %y) {
199179

200180
define i1 @slt_smin1(i32 %x, i32 %y) {
201181
; CHECK-LABEL: @slt_smin1(
202-
; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 %x, %y
203-
; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP1]], i32 %x, i32 %y
204-
; CHECK-NEXT: [[CMP2:%.*]] = icmp slt i32 [[SEL]], %x
182+
; CHECK-NEXT: [[CMP2:%.*]] = icmp sgt i32 %x, %y
205183
; CHECK-NEXT: ret i1 [[CMP2]]
206184
;
207185
%cmp1 = icmp slt i32 %x, %y
@@ -228,9 +206,7 @@ define i1 @slt_smin2(i32 %x, i32 %y) {
228206
define i1 @slt_smin3(i32 %a, i32 %y) {
229207
; CHECK-LABEL: @slt_smin3(
230208
; CHECK-NEXT: [[X:%.*]] = add i32 %a, 3
231-
; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 [[X]], %y
232-
; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP1]], i32 [[X]], i32 %y
233-
; CHECK-NEXT: [[CMP2:%.*]] = icmp sgt i32 [[X]], [[SEL]]
209+
; CHECK-NEXT: [[CMP2:%.*]] = icmp sgt i32 [[X]], %y
234210
; CHECK-NEXT: ret i1 [[CMP2]]
235211
;
236212
%x = add i32 %a, 3 ; thwart complexity-based canonicalization

0 commit comments

Comments
 (0)
Please sign in to comment.