Fold certain additions through selects (and their compares) so as to eliminate subtractions. This code is often produced by the SMAX expansion in SCEV.

This implements test/Transforms/InstCombine/2007-12-18-AddSelCmpSub.ll


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

3 files changed, 99 insertions, 18 deletions

diff --git a/lib/Target/README.txt b/lib/Target/README.txt
index c942d94471..37c0a359a2 100644
--- a/lib/Target/README.txt
+++ b/lib/Target/README.txt
@@ -464,21 +464,3 @@ entry:
 }
 
 //===---------------------------------------------------------------------===//
-
-This code is often produced by the SMAX expansion in SCEV:
-
-define i32 @foo(i32 %a) {
-entry:
-        %tmp15 = sub i32 99, %a         ; <i32> [#uses=2]
-        %tmp16 = icmp slt i32 %tmp15, 0         ; <i1> [#uses=1]
-        %smax = select i1 %tmp16, i32 0, i32 %tmp15             ; <i32> [#uses=1]
-        %tmp12 = add i32 %smax, %a              ; <i32> [#uses=1]
-        %tmp13 = add i32 %tmp12, 1              ; <i32> [#uses=1]
-        ret i32 %tmp13
-}
-
-Note that the tmp12 add can be pushed through the select operands, turning
-it into a "select %tmp16, %a, 99".  We apparently already do this in dag 
-combine because it isn't present in X86 output.
-
-//===---------------------------------------------------------------------===//
diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp
index 7989ebf197..b059c49f0a 100644
--- a/lib/Transforms/Scalar/InstructionCombining.cpp
+++ b/lib/Transforms/Scalar/InstructionCombining.cpp
@@ -2130,6 +2130,67 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
       return new PtrToIntInst(I2, CI->getType());
     }
   }
+  
+  // add (select (icmp 0 (sub m A)) X Y) A ->
+  //   add (select (icmp A m) X Y) A
+  // 
+  // add (select X 0 (sub n A)) A ->
+  //  select X A n ->
+  {
+    SelectInst *SI = dyn_cast<SelectInst>(LHS);
+    Value *Other = RHS;
+    if (!SI) {
+      SI = dyn_cast<SelectInst>(RHS);
+      Other = LHS;
+    }
+    if (SI) {
+      Value *TV = SI->getTrueValue();
+      Value *FV = SI->getFalseValue();
+      Value *A;
+            
+      // Can we fold the add into the argument of the compare?
+      Value *Cond = SI->getCondition();
+      if (ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) {
+        Value *ICOp0 = IC->getOperand(0);
+        Value *ICOp1 = IC->getOperand(1);
+        ConstantInt *C3, *C4;
+        
+        // Check both arguments of the compare for a matching subtract.
+        if (match(ICOp0, m_ConstantInt(C3)) && C3->getValue() == 0 &&
+            match(ICOp1, m_Sub(m_ConstantInt(C4), m_Value(A))) &&
+            A == Other) {
+          // We managed to fold the add into the RHS of the select condition.
+          Cond = new ICmpInst(IC->getPredicate(), A, C4, "asis", SI);
+        } else if (match(ICOp1, m_ConstantInt(C3)) && C3->getValue() == 0 &&
+            match(ICOp0, m_Sub(m_ConstantInt(C4), m_Value(A))) &&
+            A == Other) {
+          // We managed to fold the add into the LHS of the select condition.
+          Cond = new ICmpInst(IC->getPredicate(), C4, A, "asis", SI);
+        }
+      }
+
+      // Can we fold the add into the argument of the select?
+      // We check both true and false select arguments for a matching subtract.
+      ConstantInt *C1, *C2;
+      if (match(FV, m_ConstantInt(C1)) && C1->getValue() == 0 &&
+          match(TV, m_Sub(m_ConstantInt(C2), m_Value(A))) &&
+          A == Other) {
+        // We managed to fold the add into the true select value,
+        // picking up a simplified condition, if available.
+        return new SelectInst(Cond, C2, A, "adselsub");
+      } else if (match(TV, m_ConstantInt(C1)) && C1->getValue() == 0 && 
+                 match(FV, m_Sub(m_ConstantInt(C2), m_Value(A))) &&
+                 A == Other) {
+        // We managed to fold the add into the false select value,
+        // picking up a simplified condition, if available.
+        return new SelectInst(Cond, A, C2, "adselsub");
+      } else if (Cond != SI->getCondition()) {
+        // We only managed to fold the add into the select condition.
+        SI->setOperand(0, Cond);
+        Changed = true;
+      }
+    }
+  }
 
   return Changed ? &I : 0;
 }
diff --git a/test/Transforms/InstCombine/2007-12-18-AddSelCmpSub.ll b/test/Transforms/InstCombine/2007-12-18-AddSelCmpSub.ll
new file mode 100644
index 0000000000..ef38eee30e
--- /dev/null
+++ b/test/Transforms/InstCombine/2007-12-18-AddSelCmpSub.ll
@@ -0,0 +1,38 @@
+; RUN: llvm-as < %s | opt -instcombine | llvm-dis | not grep {sub}
+
+define i32 @foo(i32 %a) {
+entry:
+        %tmp15 = sub i32 99, %a         ; <i32> [#uses=2]
+        %tmp16 = icmp slt i32 %tmp15, 0         ; <i1> [#uses=1]
+        %smax = select i1 %tmp16, i32 0, i32 %tmp15             ; <i32> [#uses=1]
+        %tmp12 = add i32 %smax, %a              ; <i32> [#uses=1]
+        %tmp13 = add i32 %tmp12, 1              ; <i32> [#uses=1]
+        ret i32 %tmp13
+}
+
+define i32 @bar(i32 %a) {
+entry:
+        %tmp15 = sub i32 99, %a         ; <i32> [#uses=2]
+        %tmp16 = icmp slt i32 %tmp15, 0         ; <i1> [#uses=1]
+        %smax = select i1 %tmp16, i32 0, i32 %tmp15             ; <i32> [#uses=1]
+        %tmp12 = add i32 %smax, %a              ; <i32> [#uses=1]
+        ret i32 %tmp12
+}
+
+define i32 @baz(i32 %a) {
+entry:
+        %tmp15 = sub i32 99, %a         ; <i32> [#uses=1]
+        %tmp16 = icmp slt i32 %tmp15, 0         ; <i1> [#uses=1]
+        %smax = select i1 %tmp16, i32 0, i32 42             ; <i32> [#uses=1]
+        %tmp12 = add i32 %smax, %a              ; <i32> [#uses=1]
+        ret i32 %tmp12
+}
+
+define i32 @fun(i32 %a) {
+entry:
+        %tmp15 = sub i32 99, %a         ; <i32> [#uses=1]
+        %tmp16 = icmp slt i32 %a, 0         ; <i1> [#uses=1]
+        %smax = select i1 %tmp16, i32 0, i32 %tmp15             ; <i32> [#uses=1]
+        %tmp12 = add i32 %smax, %a              ; <i32> [#uses=1]
+        ret i32 %tmp12
+}
\ No newline at end of file