give instcombine some helper functions for matching MIN and MAX, and

implement some optimizations for MIN(MIN()) and MAX(MAX()) and
MIN(MAX()) etc.  This substantially improves the code in PR5822 but
doesn't kick in much elsewhere.  2 max's were optimized in
pairlocalalign and one in smg2000.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91814 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp
index 9033877b454cfc4e9e4903f7ee8d30b8504b14e9..ca60219b9090491f643678051bcdcfca8121871b 100644 (file)
--- a/lib/Transforms/Scalar/InstructionCombining.cpp
+++ b/lib/Transforms/Scalar/InstructionCombining.cpp
@@ -75,6 +75,15 @@ STATISTIC(NumDeadInst , "Number of dead inst eliminated");
 STATISTIC(NumDeadStore, "Number of dead stores eliminated");
 STATISTIC(NumSunkInst , "Number of instructions sunk");
 
+/// SelectPatternFlavor - We can match a variety of different patterns for
+/// select operations.
+enum SelectPatternFlavor {
+  SPF_UNKNOWN = 0,
+  SPF_SMIN, SPF_UMIN,
+  SPF_SMAX, SPF_UMAX
+  //SPF_ABS - TODO.
+};
+
 namespace {
   /// InstCombineWorklist - This is the worklist management logic for
   /// InstCombine.
@@ -281,6 +290,9 @@ namespace {
     Instruction *FoldSelectOpOp(SelectInst &SI, Instruction *TI,
                                 Instruction *FI);
     Instruction *FoldSelectIntoOp(SelectInst &SI, Value*, Value*);
+    Instruction *FoldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
+                              Value *A, Value *B, Instruction &Outer,
+                              SelectPatternFlavor SPF2, Value *C);
     Instruction *visitSelectInst(SelectInst &SI);
     Instruction *visitSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
     Instruction *visitCallInst(CallInst &CI);
@@ -649,6 +661,57 @@ static inline Value *dyn_castFNegVal(Value *V) {
   return 0;
 }
 
+/// MatchSelectPattern - Pattern match integer [SU]MIN, [SU]MAX, and ABS idioms,
+/// returning the kind and providing the out parameter results if we
+/// successfully match.
+static SelectPatternFlavor
+MatchSelectPattern(Value *V, Value *&LHS, Value *&RHS) {
+  SelectInst *SI = dyn_cast<SelectInst>(V);
+  if (SI == 0) return SPF_UNKNOWN;
+  
+  ICmpInst *ICI = dyn_cast<ICmpInst>(SI->getCondition());
+  if (ICI == 0) return SPF_UNKNOWN;
+  
+  LHS = ICI->getOperand(0);
+  RHS = ICI->getOperand(1);
+  
+  // (icmp X, Y) ? X : Y 
+  if (SI->getTrueValue() == ICI->getOperand(0) &&
+      SI->getFalseValue() == ICI->getOperand(1)) {
+    switch (ICI->getPredicate()) {
+    default: return SPF_UNKNOWN; // Equality.
+    case ICmpInst::ICMP_UGT:
+    case ICmpInst::ICMP_UGE: return SPF_UMAX;
+    case ICmpInst::ICMP_SGT:
+    case ICmpInst::ICMP_SGE: return SPF_SMAX;
+    case ICmpInst::ICMP_ULT:
+    case ICmpInst::ICMP_ULE: return SPF_UMIN;
+    case ICmpInst::ICMP_SLT:
+    case ICmpInst::ICMP_SLE: return SPF_SMIN;
+    }
+  }
+  
+  // (icmp X, Y) ? Y : X 
+  if (SI->getTrueValue() == ICI->getOperand(1) &&
+      SI->getFalseValue() == ICI->getOperand(0)) {
+    switch (ICI->getPredicate()) {
+      default: return SPF_UNKNOWN; // Equality.
+      case ICmpInst::ICMP_UGT:
+      case ICmpInst::ICMP_UGE: return SPF_UMIN;
+      case ICmpInst::ICMP_SGT:
+      case ICmpInst::ICMP_SGE: return SPF_SMIN;
+      case ICmpInst::ICMP_ULT:
+      case ICmpInst::ICMP_ULE: return SPF_UMAX;
+      case ICmpInst::ICMP_SLT:
+      case ICmpInst::ICMP_SLE: return SPF_SMAX;
+    }
+  }
+  
+  // TODO: (X > 4) ? X : 5   -->  (X >= 5) ? X : 5  -->  MAX(X, 5)
+  
+  return SPF_UNKNOWN;
+}
+
 /// isFreeToInvert - Return true if the specified value is free to invert (apply
 /// ~ to).  This happens in cases where the ~ can be eliminated.
 static inline bool isFreeToInvert(Value *V) {
@@ -733,12 +796,12 @@ static bool MultiplyOverflows(ConstantInt *C1, ConstantInt *C2, bool sign) {
 
   APInt MulExt = LHSExt * RHSExt;
 
-  if (sign) {
-    APInt Min = APInt::getSignedMinValue(W).sext(W * 2);
-    APInt Max = APInt::getSignedMaxValue(W).sext(W * 2);
-    return MulExt.slt(Min) || MulExt.sgt(Max);
-  } else 
+  if (!sign)
     return MulExt.ugt(APInt::getLowBitsSet(W * 2, W));
+  
+  APInt Min = APInt::getSignedMinValue(W).sext(W * 2);
+  APInt Max = APInt::getSignedMaxValue(W).sext(W * 2);
+  return MulExt.slt(Min) || MulExt.sgt(Max);
 }
 
 
@@ -9479,9 +9542,6 @@ Instruction *InstCombiner::visitSelectInstWithICmp(SelectInst &SI,
       return ReplaceInstUsesWith(SI, TrueVal);
     /// NOTE: if we wanted to, this is where to detect integer MIN/MAX
   }
-
-  /// NOTE: if we wanted to, this is where to detect integer ABS
-
   return Changed ? &SI : 0;
 }
 
@@ -9523,6 +9583,35 @@ static bool CanSelectOperandBeMappingIntoPredBlock(const Value *V,
   return false;
 }
 
+/// FoldSPFofSPF - We have an SPF (e.g. a min or max) of an SPF of the form:
+///   SPF2(SPF1(A, B), C) 
+Instruction *InstCombiner::FoldSPFofSPF(Instruction *Inner,
+                                        SelectPatternFlavor SPF1,
+                                        Value *A, Value *B,
+                                        Instruction &Outer,
+                                        SelectPatternFlavor SPF2, Value *C) {
+  if (C == A || C == B) {
+    // MAX(MAX(A, B), B) -> MAX(A, B)
+    // MIN(MIN(a, b), a) -> MIN(a, b)
+    if (SPF1 == SPF2)
+      return ReplaceInstUsesWith(Outer, Inner);
+    
+    // MAX(MIN(a, b), a) -> a
+    // MIN(MAX(a, b), a) -> a
+    if (SPF1 == SPF_SMIN && SPF2 == SPF_SMAX ||
+        SPF1 == SPF_SMAX && SPF2 == SPF_SMIN ||
+        SPF1 == SPF_UMIN && SPF2 == SPF_UMAX ||
+        SPF1 == SPF_UMAX && SPF2 == SPF_UMIN)
+      return ReplaceInstUsesWith(Outer, C);
+  }
+  
+  // TODO: MIN(MIN(A, 23), 97)
+  return 0;
+}
+
+
+
+
 Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
   Value *CondVal = SI.getCondition();
   Value *TrueVal = SI.getTrueValue();
@@ -9729,9 +9818,28 @@ Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
 
   // See if we can fold the select into one of our operands.
   if (SI.getType()->isInteger()) {
-    Instruction *FoldI = FoldSelectIntoOp(SI, TrueVal, FalseVal);
-    if (FoldI)
+    if (Instruction *FoldI = FoldSelectIntoOp(SI, TrueVal, FalseVal))
       return FoldI;
+    
+    // MAX(MAX(a, b), a) -> MAX(a, b)
+    // MIN(MIN(a, b), a) -> MIN(a, b)
+    // MAX(MIN(a, b), a) -> a
+    // MIN(MAX(a, b), a) -> a
+    Value *LHS, *RHS, *LHS2, *RHS2;
+    if (SelectPatternFlavor SPF = MatchSelectPattern(&SI, LHS, RHS)) {
+      if (SelectPatternFlavor SPF2 = MatchSelectPattern(LHS, LHS2, RHS2))
+        if (Instruction *R = FoldSPFofSPF(cast<Instruction>(LHS),SPF2,LHS2,RHS2, 
+                                          SI, SPF, RHS))
+          return R;
+      if (SelectPatternFlavor SPF2 = MatchSelectPattern(RHS, LHS2, RHS2))
+        if (Instruction *R = FoldSPFofSPF(cast<Instruction>(RHS),SPF2,LHS2,RHS2,
+                                          SI, SPF, LHS))
+          return R;
+    }
+
+    // TODO.
+    // ABS(-X) -> ABS(X)
+    // ABS(ABS(X)) -> ABS(X)
   }
 
   // See if we can fold the select into a phi node if the condition is a select.

diff --git a/test/Transforms/InstCombine/select.ll b/test/Transforms/InstCombine/select.ll
index 565cfa57ff820d5fc6b1f7ed0ab9b9ff818c7414..7c597007c318cb23ef9852684db851571b39a632 100644 (file)
--- a/test/Transforms/InstCombine/select.ll
+++ b/test/Transforms/InstCombine/select.ll
@@ -382,3 +382,43 @@ next:
 ; CHECK-NEXT: ret i32 %a
 }
 
+
+define i32 @test30(i32 %x, i32 %y) {
+  %cmp = icmp sgt i32 %x, %y
+  %cond = select i1 %cmp, i32 %x, i32 %y
+  %cmp5 = icmp sgt i32 %cond, %x
+  %retval = select i1 %cmp5, i32 %cond, i32 %x
+  ret i32 %retval
+}
+
+define i32 @test31(i32 %x, i32 %y) {
+  %cmp = icmp ugt i32 %x, %y 
+  %cond = select i1 %cmp, i32 %x, i32 %y
+  %cmp5 = icmp ugt i32 %cond, %x
+  %retval = select i1 %cmp5, i32 %cond, i32 %x
+  ret i32 %retval
+}
+
+define i32 @test32(i32 %x, i32 %y) {
+  %cmp = icmp sgt i32 %x, %y
+  %cond = select i1 %cmp, i32 %y, i32 %x
+  %cmp5 = icmp sgt i32 %cond, %x
+  %retval = select i1 %cmp5, i32 %x, i32 %cond
+  ret i32 %retval
+}
+
+define i32 @test33(i32 %x, i32 %y) {
+  %cmp = icmp sgt i32 %x, %y
+  %cond = select i1 %cmp, i32 %y, i32 %x
+  %cmp5 = icmp sgt i32 %cond, %x
+  %retval = select i1 %cmp5, i32 %cond, i32 %x
+  ret i32 %retval
+}
+
+define i32 @test34(i32 %x, i32 %y) {
+  %cmp = icmp sgt i32 %x, %y
+  %cond = select i1 %cmp, i32 %x, i32 %y
+  %cmp5 = icmp sgt i32 %cond, %x
+  %retval = select i1 %cmp5, i32 %x, i32 %cond
+  ret i32 %retval
+}