From ad20681cdeaf72383891b153b925624aa585be4d Mon Sep 17 00:00:00 2001 From: Duncan Sands Date: Tue, 3 May 2011 19:53:10 +0000 Subject: [PATCH] Implement some basic simplifications involving min/max, for example max(a,b) >= a -> true. According to my super-optimizer, these are by far the most common simplifications (of the -instsimplify kind) that occur in the testsuite and aren't caught by -std-compile-opts. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130780 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/PatternMatch.h | 93 ++++++++++++++++ lib/Analysis/InstructionSimplify.cpp | 118 ++++++++++++++++++++ test/Transforms/InstSimplify/maxmin.ll | 145 +++++++++++++++++++++++++ 3 files changed, 356 insertions(+) create mode 100644 test/Transforms/InstSimplify/maxmin.ll diff --git a/include/llvm/Support/PatternMatch.h b/include/llvm/Support/PatternMatch.h index 172480e7ae6..f0fb516d5f7 100644 --- a/include/llvm/Support/PatternMatch.h +++ b/include/llvm/Support/PatternMatch.h @@ -694,6 +694,99 @@ inline brc_match m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) { return brc_match(C, T, F); } + +//===----------------------------------------------------------------------===// +// Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y). +// + +template +struct MaxMin_match { + LHS_t L; + RHS_t R; + + MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) + : L(LHS), R(RHS) {} + + template + bool match(OpTy *V) { + // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x". + SelectInst *SI = dyn_cast(V); + if (!SI) + return false; + ICmpInst *Cmp = dyn_cast(SI->getCondition()); + if (!Cmp) + return false; + // At this point we have a select conditioned on a comparison. Check that + // it is the values returned by the select that are being compared. + Value *TrueVal = SI->getTrueValue(); + Value *FalseVal = SI->getFalseValue(); + Value *LHS = Cmp->getOperand(0); + Value *RHS = Cmp->getOperand(1); + if ((TrueVal != LHS || FalseVal != RHS) && + (TrueVal != RHS || FalseVal != LHS)) + return false; + ICmpInst::Predicate Pred = LHS == TrueVal ? + Cmp->getPredicate() : Cmp->getSwappedPredicate(); + // Does "(x pred y) ? x : y" represent the desired max/min operation? + if (!Pred_t::match(Pred)) + return false; + // It does! Bind the operands. + return L.match(LHS) && R.match(RHS); + } +}; + +/// smax_pred_ty - Helper class for identifying signed max predicates. +struct smax_pred_ty { + static bool match(ICmpInst::Predicate Pred) { + return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE; + } +}; + +/// smin_pred_ty - Helper class for identifying signed min predicates. +struct smin_pred_ty { + static bool match(ICmpInst::Predicate Pred) { + return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE; + } +}; + +/// umax_pred_ty - Helper class for identifying unsigned max predicates. +struct umax_pred_ty { + static bool match(ICmpInst::Predicate Pred) { + return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE; + } +}; + +/// umin_pred_ty - Helper class for identifying unsigned min predicates. +struct umin_pred_ty { + static bool match(ICmpInst::Predicate Pred) { + return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE; + } +}; + +template +inline MaxMin_match +m_SMax(const LHS &L, const RHS &R) { + return MaxMin_match(L, R); +} + +template +inline MaxMin_match +m_SMin(const LHS &L, const RHS &R) { + return MaxMin_match(L, R); +} + +template +inline MaxMin_match +m_UMax(const LHS &L, const RHS &R) { + return MaxMin_match(L, R); +} + +template +inline MaxMin_match +m_UMin(const LHS &L, const RHS &R) { + return MaxMin_match(L, R); +} + } // end namespace PatternMatch } // end namespace llvm diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp index 7c43a9d5c3d..3028f17a526 100644 --- a/lib/Analysis/InstructionSimplify.cpp +++ b/lib/Analysis/InstructionSimplify.cpp @@ -1868,6 +1868,124 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, } } + // Simplify comparisons involving max/min. + Value *A, *B; + CmpInst::Predicate P = CmpInst::BAD_ICMP_PREDICATE; + CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B". + + // Signed max/min. + if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { + if (A != RHS) std::swap(A, B); // smax(A, B) pred A. + EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B". + // We analyze this as smax(A, B) pred A. + P = Pred; + } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) && + (A == LHS || B == LHS)) { + if (A != LHS) std::swap(A, B); // A pred smax(A, B). + EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B". + // We analyze this as smax(A, B) swapped-pred A. + P = CmpInst::getSwappedPredicate(Pred); + } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) && + (A == RHS || B == RHS)) { + if (A != RHS) std::swap(A, B); // smin(A, B) pred A. + EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B". + // We analyze this as smax(-A, -B) swapped-pred -A. + // Note that we do not need to actually form -A or -B thanks to EqP. + P = CmpInst::getSwappedPredicate(Pred); + } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) && + (A == LHS || B == LHS)) { + if (A != LHS) std::swap(A, B); // A pred smin(A, B). + EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B". + // We analyze this as smax(-A, -B) pred -A. + // Note that we do not need to actually form -A or -B thanks to EqP. + P = Pred; + } + if (P != CmpInst::BAD_ICMP_PREDICATE) { + // Cases correspond to "max(A, B) p A". + switch (P) { + default: + break; + case CmpInst::ICMP_EQ: + case CmpInst::ICMP_SLE: + // Equivalent to "A EqP B". + if (MaxRecurse) + if (Value *V = SimplifyICmpInst(EqP, A, B, TD, DT, MaxRecurse-1)) + return V; + break; + case CmpInst::ICMP_NE: + case CmpInst::ICMP_SGT: + // Equivalent to "A inverse-EqP B". + if (MaxRecurse) + if (Value *V = SimplifyICmpInst(CmpInst::getInversePredicate(EqP), A, B, + TD, DT, MaxRecurse-1)) + return V; + break; + case CmpInst::ICMP_SGE: + // Always true. + return Constant::getAllOnesValue(ITy); + case CmpInst::ICMP_SLT: + // Always false. + return Constant::getNullValue(ITy); + } + } + + // Unsigned max/min. + P = CmpInst::BAD_ICMP_PREDICATE; + if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { + if (A != RHS) std::swap(A, B); // umax(A, B) pred A. + EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B". + // We analyze this as umax(A, B) pred A. + P = Pred; + } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) && + (A == LHS || B == LHS)) { + if (A != LHS) std::swap(A, B); // A pred umax(A, B). + EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B". + // We analyze this as umax(A, B) swapped-pred A. + P = CmpInst::getSwappedPredicate(Pred); + } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) && + (A == RHS || B == RHS)) { + if (A != RHS) std::swap(A, B); // umin(A, B) pred A. + EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B". + // We analyze this as umax(-A, -B) swapped-pred -A. + // Note that we do not need to actually form -A or -B thanks to EqP. + P = CmpInst::getSwappedPredicate(Pred); + } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) && + (A == LHS || B == LHS)) { + if (A != LHS) std::swap(A, B); // A pred umin(A, B). + EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B". + // We analyze this as umax(-A, -B) pred -A. + // Note that we do not need to actually form -A or -B thanks to EqP. + P = Pred; + } + if (P != CmpInst::BAD_ICMP_PREDICATE) { + // Cases correspond to "max(A, B) p A". + switch (P) { + default: + break; + case CmpInst::ICMP_EQ: + case CmpInst::ICMP_ULE: + // Equivalent to "A EqP B". + if (MaxRecurse) + if (Value *V = SimplifyICmpInst(EqP, A, B, TD, DT, MaxRecurse-1)) + return V; + break; + case CmpInst::ICMP_NE: + case CmpInst::ICMP_UGT: + // Equivalent to "A inverse-EqP B". + if (MaxRecurse) + if (Value *V = SimplifyICmpInst(CmpInst::getInversePredicate(EqP), A, B, + TD, DT, MaxRecurse-1)) + return V; + break; + case CmpInst::ICMP_UGE: + // Always true. + return Constant::getAllOnesValue(ITy); + case CmpInst::ICMP_ULT: + // Always false. + return Constant::getNullValue(ITy); + } + } + // If the comparison is with the result of a select instruction, check whether // comparing with either branch of the select always yields the same value. if (isa(LHS) || isa(RHS)) diff --git a/test/Transforms/InstSimplify/maxmin.ll b/test/Transforms/InstSimplify/maxmin.ll new file mode 100644 index 00000000000..6d9225921c2 --- /dev/null +++ b/test/Transforms/InstSimplify/maxmin.ll @@ -0,0 +1,145 @@ +; RUN: opt < %s -instsimplify -S | FileCheck %s + +define i1 @max1(i32 %x, i32 %y) { +; CHECK: @max1 + %c = icmp sgt i32 %x, %y + %m = select i1 %c, i32 %x, i32 %y + %r = icmp slt i32 %m, %x + ret i1 %r +; CHECK: ret i1 false +} + +define i1 @max2(i32 %x, i32 %y) { +; CHECK: @max2 + %c = icmp sge i32 %x, %y + %m = select i1 %c, i32 %x, i32 %y + %r = icmp sge i32 %m, %x + ret i1 %r +; CHECK: ret i1 true +} + +define i1 @max3(i32 %x, i32 %y) { +; CHECK: @max3 + %c = icmp ugt i32 %x, %y + %m = select i1 %c, i32 %x, i32 %y + %r = icmp ult i32 %m, %x + ret i1 %r +; CHECK: ret i1 false +} + +define i1 @max4(i32 %x, i32 %y) { +; CHECK: @max4 + %c = icmp uge i32 %x, %y + %m = select i1 %c, i32 %x, i32 %y + %r = icmp uge i32 %m, %x + ret i1 %r +; CHECK: ret i1 true +} + +define i1 @max5(i32 %x, i32 %y) { +; CHECK: @max5 + %c = icmp sgt i32 %x, %y + %m = select i1 %c, i32 %x, i32 %y + %r = icmp sgt i32 %x, %m + ret i1 %r +; CHECK: ret i1 false +} + +define i1 @max6(i32 %x, i32 %y) { +; CHECK: @max6 + %c = icmp sge i32 %x, %y + %m = select i1 %c, i32 %x, i32 %y + %r = icmp sle i32 %x, %m + ret i1 %r +; CHECK: ret i1 true +} + +define i1 @max7(i32 %x, i32 %y) { +; CHECK: @max7 + %c = icmp ugt i32 %x, %y + %m = select i1 %c, i32 %x, i32 %y + %r = icmp ugt i32 %x, %m + ret i1 %r +; CHECK: ret i1 false +} + +define i1 @max8(i32 %x, i32 %y) { +; CHECK: @max8 + %c = icmp uge i32 %x, %y + %m = select i1 %c, i32 %x, i32 %y + %r = icmp ule i32 %x, %m + ret i1 %r +; CHECK: ret i1 true +} + +define i1 @min1(i32 %x, i32 %y) { +; CHECK: @min1 + %c = icmp sgt i32 %x, %y + %m = select i1 %c, i32 %y, i32 %x + %r = icmp sgt i32 %m, %x + ret i1 %r +; CHECK: ret i1 false +} + +define i1 @min2(i32 %x, i32 %y) { +; CHECK: @min2 + %c = icmp sge i32 %x, %y + %m = select i1 %c, i32 %y, i32 %x + %r = icmp sle i32 %m, %x + ret i1 %r +; CHECK: ret i1 true +} + +define i1 @min3(i32 %x, i32 %y) { +; CHECK: @min3 + %c = icmp ugt i32 %x, %y + %m = select i1 %c, i32 %y, i32 %x + %r = icmp ugt i32 %m, %x + ret i1 %r +; CHECK: ret i1 false +} + +define i1 @min4(i32 %x, i32 %y) { +; CHECK: @min4 + %c = icmp uge i32 %x, %y + %m = select i1 %c, i32 %y, i32 %x + %r = icmp ule i32 %m, %x + ret i1 %r +; CHECK: ret i1 true +} + +define i1 @min5(i32 %x, i32 %y) { +; CHECK: @min5 + %c = icmp sgt i32 %x, %y + %m = select i1 %c, i32 %y, i32 %x + %r = icmp slt i32 %x, %m + ret i1 %r +; CHECK: ret i1 false +} + +define i1 @min6(i32 %x, i32 %y) { +; CHECK: @min6 + %c = icmp sge i32 %x, %y + %m = select i1 %c, i32 %y, i32 %x + %r = icmp sge i32 %x, %m + ret i1 %r +; CHECK: ret i1 true +} + +define i1 @min7(i32 %x, i32 %y) { +; CHECK: @min7 + %c = icmp ugt i32 %x, %y + %m = select i1 %c, i32 %y, i32 %x + %r = icmp ult i32 %x, %m + ret i1 %r +; CHECK: ret i1 false +} + +define i1 @min8(i32 %x, i32 %y) { +; CHECK: @min8 + %c = icmp uge i32 %x, %y + %m = select i1 %c, i32 %y, i32 %x + %r = icmp uge i32 %x, %m + ret i1 %r +; CHECK: ret i1 true +} -- 2.34.1