Added instcombine for 'ABS(ABS(X)) -> ABS(X)'

[dinesh.d]

Summary

Tried implementing SPF_ABS and instcombine for ABS(ABS(X))

I left ABS(-X) -> ABS(X) from TODO comment because it was not
reducing instructions count. For calculating ABS(X), it generate
instruction to negate X for select instruction.

[dinesh.d]

Replace isa<> and cast with dyn_cast.

[dinesh.d]

Gentle ping

[bkramer]

lib/Transforms/InstCombine/InstCombineSelect.cpp

73

What about X < 0 ? -X : X;?

[dinesh.d]

updated code to handle following patterns [Thanks for pointing out]

// (X > 0) ? X : -X
// (X < 0) ? -X : X
// (X > 1) ? -X : X

[dinesh.d]

corrected one typo in comments.
I have written

(x > 1)? -x : x

whereas I meant

(x < 1)? -x : x

[dinesh.d]

Gentle Ping

[dinesh.d]

gentle ping

[reames]

One potential bug, and a couple of small comments, but otherwise looks fine.

(Note: I don't have commit rights so this is not an approval to commit.)

lib/Transforms/InstCombine/InstCombineSelect.cpp

34

Personally, I find the code with these extracted much harder to read. I would prefer you not extract these, but don't have a strong preference. i.e. feel free to ignore

83

An unsigned comparison against -1 doesn't seem right here. -1 is going to be the all ones pattern; nothing will be greater than that.

I think what you want is:
case ICmpInst::ICMP_SGT:

if minus one: return SPF_ABS
fallthrough

case ICmpInst::ICMP_UGT:

if zero: return SFP_ABS
break

93

You could add cases for "<=" or ">=" here as well right?

You might also add a comment why you can't recognize Neg(Abs(X)) patterns. (i.e. the most negative int problem) Glancing at your code it seems like an obvious extension and isn't immediate obvious why you can't.

[dinesh.d]

Thanks Philip. I appreciate your effort.

I do have one request though. As you are also new to llvm, it will be great if you can avoid
using strong words until you have some familiarity with the module in context.

lib/Transforms/InstCombine/InstCombineSelect.cpp

34

I think now they are more readable. I have seen similar code in many places in inst combine and llvm in general. But I too do not have any strong preference and will change it if others agree with you.

83

I agree that it is written in the way you have suggested. But I don't think this is bug in current code. It will simply never reach to MINUS_ONE check in UGT case.

I will be happy to change it and ULT (X, 0) case too. Thanks for pointing it out.

93

Due to other transform, we will never get <= or >= case here. These cases will always transform to < or > so we don't need to check them here. My understanding may be wrong. Let's other comment on that.

I have never mentioned I can't. For NEG(ABS(X)), before reaching to this instruction, ABS(X) will be analyzed and my patch is able to recognize it as ABS. I don't think NEG(ABS(X)) is valid pattern here in current context.

This patch even transform ABS(-ABS(X)) to ABS(X). I hope this makes it clear to you.

[dinesh.d]

Updated patch to handle both ABS(X) and NEG(ABS(X)) and tests for all possible combinations or ABS(ABS) and NABS(NABS)
I have removed check for unsigned predicates as ABS of unsigned values are value them selves and must already handled before.
Thanks to Philip and sorry as I did not get your comment right previously.

[dinesh.d]

gentle ping

[reames]

With the last round of changes, this looks fine to me. I'm unclear whether this is covering all useful patterns (i.e. why don't we need GTE, or LTE pattens?), but what's here seems correct and useful.

Reminder: You will need to find another reviewer. I do not have commit rights and can not approve your change.

[dinesh.d]

Thanks for review, Philip.

InstCombine code changes >= and <= to corrosponding > and < before this code get hit.
You can try with this code with clang build in debug mode or Release+Assert

> cat test.cpp
int test(int x) {
    int y = (x >= 0) ? x : -x;
    int z = (y >= 0) ? y : -y;
    return z;
}

> clang -O0 -S -emit-llvm test.cpp
> opt -mem2reg -instcombine -debug test.ll

Let me know if you have any doubts.

[bkramer]

The updated patch LGTM. Thanks!

We don't have to match patterns for sle and uge as instcombine canonicalizes them into slt and ugt. That makes code like this simpler.

[dinesh.d]

Closed by commit rL210312 (authored by dinesh).

lib/Transforms/InstCombine/InstCombine.h

 
 /// 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.
+  SPF_UMAX,
+  SPF_ABS
 };
 
 /// getComplexity:  Assign a complexity or rank value to LLVM Values...
 ///   0 -> undef, 1 -> Const, 2 -> Other, 3 -> Arg, 3 -> Unary, 4 -> OtherInst
 static inline unsigned getComplexity(Value *V) {
   if (isa<Instruction>(V)) {
     if (BinaryOperator::isNeg(V) || BinaryOperator::isFNeg(V) ||
         BinaryOperator::isNot(V))

lib/Transforms/InstCombine/InstCombineSelect.cpp

 static SelectPatternFlavor
 MatchSelectPattern(Value *V, Value *&LHS, Value *&RHS) {
   SelectInst *SI = dyn_cast<SelectInst>(V);
   if (!SI) return SPF_UNKNOWN;
 
   ICmpInst *ICI = dyn_cast<ICmpInst>(SI->getCondition());
   if (!ICI) return SPF_UNKNOWN;
 
-  LHS = ICI->getOperand(0);
-  RHS = ICI->getOperand(1);
+  ICmpInst::Predicate Pred = ICI->getPredicate();
+  Value *CmpLHS = ICI->getOperand(0);
+  Value *CmpRHS = ICI->getOperand(1);
+  Value *TrueVal = SI->getTrueValue();
+  Value *FalseVal = SI->getFalseValue();
+
+  LHS = CmpLHS;
+  RHS = CmpRHS;
 
   // (icmp X, Y) ? X : Y
-  if (SI->getTrueValue() == ICI->getOperand(0) &&
-      SI->getFalseValue() == ICI->getOperand(1)) {
-    switch (ICI->getPredicate()) {
+  if (TrueVal == CmpLHS && FalseVal == CmpRHS) {
+    switch (Pred) {
     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;
+  if (TrueVal == CmpRHS && FalseVal == CmpLHS) {
+    switch (Pred) {
     }
   }
 
+  // (X > -1) ? X : -X
+  // (X > 0) ? X : -X
+  // (X < 0) ? -X : X
+  // (X < 1) ? -X : X
+  if (ConstantInt *C1 = dyn_cast<ConstantInt>(CmpRHS)) {
+    if (match(TrueVal, m_Neg(m_Specific(FalseVal))) ||
+        match(FalseVal, m_Neg(m_Specific(TrueVal)))) {
+      switch (Pred) {
+      default:
+        return SPF_UNKNOWN;
+      case ICmpInst::ICMP_UGT:
+      case ICmpInst::ICMP_SGT:
+        if (CmpLHS == TrueVal && (C1->isZero() || C1->isMinusOne()))
+          return SPF_ABS;
+        break;
+      case ICmpInst::ICMP_ULT:
+      case ICmpInst::ICMP_SLT:
+        if (CmpLHS == FalseVal && (C1->isZero() || C1->isOne()))
+          return SPF_ABS;
+        break;
+      }
+    }
+  }
+
   // TODO: (X > 4) ? X : 5   -->  (X >= 5) ? X : 5  -->  MAX(X, 5)
 
   return SPF_UNKNOWN;
 }
 
-
 /// GetSelectFoldableOperands - We want to turn code that looks like this:
 ///   %C = or %A, %B
 ///   %D = select %cond, %C, %A
 /// into:
 ///   %C = select %cond, %B, 0
 ///   %D = or %A, %C
 ///
 /// Assuming that the specified instruction is an operand to the select, return
if (ConstantInt *CB = dyn_cast<ConstantInt>(B)) {
             (SPF1 == SPF_SMAX && ACB.sge(ACC)))
           return ReplaceInstUsesWith(Outer, Inner);
       }
     }
   }
 
   // TODO: MIN(MIN(A, 97), 23) -> MIN(A, 23)
   // TODO: MAX(MAX(A, 23), 97) -> MAX(A, 97)
+
+  // ABS(ABS(X)) -> ABS(X)
+  if (SPF1 == SPF_ABS && SPF2 == SPF_ABS)
+    return ReplaceInstUsesWith(Outer, Inner);
   return nullptr;
 }
 
 /// foldSelectICmpAnd - If one of the constants is zero (we know they can't
 /// both be) and we have an icmp instruction with zero, and we have an 'and'
 /// with the non-constant value and a power of two we can turn the select
 /// into a shift on the result of the 'and'.
 static Value *foldSelectICmpAnd(const SelectInst &SI, ConstantInt *TrueVal,
if (SelectPatternFlavor SPF = MatchSelectPattern(&SI, LHS, RHS)) {
       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.
   if (isa<PHINode>(SI.getCondition()))
     // The true/false values have to be live in the PHI predecessor's blocks.
     if (CanSelectOperandBeMappingIntoPredBlock(TrueVal, SI) &&
         CanSelectOperandBeMappingIntoPredBlock(FalseVal, SI))
       if (Instruction *NV = FoldOpIntoPhi(SI))

test/Transforms/InstCombine/select.ll

 entry:
   %cmp = icmp ult i32 %x, 68
   %cond = select i1 %cmp, i32 68, i32 %x
   %cmp3 = icmp ult i32 %cond, 47
   %retval = select i1 %cmp3, i32 47, i32 %cond
   ret i32 %retval
 ; CHECK-LABEL: @test71(
 ; CHECK: ret i32 %cond
+}
+
+define i32 @abs_abs_x1(i32 %x) {
+  %ispos = icmp sgt i32 %x, -1
+  %neg = sub i32 0, %x
+  %cond = select i1 %ispos, i32 %x, i32 %neg
+  %sub = sub nsw i32 0, %cond
+  %ispos2 = icmp sgt i32 %sub, -1
+  %1 = select i1 %ispos2, i32 %sub, i32 %cond
+  ret i32 %1
+; CHECK-LABEL: @abs_abs_x1(
+; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp sgt i32 %x, -1
+; CHECK-NEXT: [[NEG:%[a-z0-9]+]] = sub i32 0, %x
+; CHECK-NEXT: [[SEL:%[a-z0-9]+]] = select i1 [[CMP]], i32 %x, i32 [[NEG]]
+; CHECK-NEXT: ret i32 [[SEL]]
+}
+
+define i32 @abs_abs_x2(i32 %x) {
+  %cmp = icmp sgt i32 %x, -1
+  %sub = sub nsw i32 0, %x
+  %cond = select i1 %cmp, i32 %x, i32 %sub
+  %cmp1 = icmp sgt i32 %cond, -1
+  %sub4 = sub nsw i32 0, %cond
+  %cond6 = select i1 %cmp1, i32 %cond, i32 %sub4
+  ret i32 %cond6
+; CHECK-LABEL: @abs_abs_x2(
+; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp sgt i32 %x, -1
+; CHECK-NEXT: [[NEG:%[a-z0-9]+]] = sub nsw i32 0, %x
+; CHECK-NEXT: [[SEL:%[a-z0-9]+]] = select i1 [[CMP]], i32 %x, i32 [[NEG]]
+; CHECK-NEXT: ret i32 [[SEL]]
+}
+
+define i32 @abs_abs_x3(i32 %x) {
+  %cmp = icmp sgt i32 %x, -1
+  %sub = sub nsw i32 0, %x
+  %cond = select i1 %cmp, i32 %x, i32 %sub
+  %sub1 = sub nsw i32 0, %cond
+  %cmp2 = icmp sgt i32 %cond, 0
+  %cond7 = select i1 %cmp2, i32 %cond, i32 %sub1
+  ret i32 %cond7
+; CHECK-LABEL: @abs_abs_x3(
+; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp sgt i32 %x, -1
+; CHECK-NEXT: [[NEG:%[a-z0-9]+]] = sub nsw i32 0, %x
+; CHECK-NEXT: [[SEL:%[a-z0-9]+]] = select i1 [[CMP]], i32 %x, i32 [[NEG]]
+; CHECK-NEXT: ret i32 [[SEL]]
+}
+
+define i32 @abs_abs_x4(i32 %x) {
+  %cmp = icmp sgt i32 %x, -1
+  %sub = sub nsw i32 0, %x
+  %cond = select i1 %cmp, i32 %x, i32 %sub
+  %cmp1 = icmp slt i32 %cond, 0
+  %sub3 = sub nsw i32 0, %cond
+  %cond6 = select i1 %cmp1, i32 %sub3, i32 %cond
+  ret i32 %cond6
+; CHECK-LABEL: @abs_abs_x4(
+; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp sgt i32 %x, -1
+; CHECK-NEXT: [[NEG:%[a-z0-9]+]] = sub nsw i32 0, %x
+; CHECK-NEXT: [[SEL:%[a-z0-9]+]] = select i1 [[CMP]], i32 %x, i32 [[NEG]]
+; CHECK-NEXT: ret i32 [[SEL]]
+}
+
+define i32 @abs_abs_x5(i32 %x) {
+  %cmp = icmp slt i32 %x, 0
+  %sub = sub nsw i32 0, %x
+  %cond = select i1 %cmp, i32 %sub, i32 %x
+  %cmp1 = icmp sgt i32 %cond, -1
+  %sub4 = sub nsw i32 0, %cond
+  %cond6 = select i1 %cmp1, i32 %cond, i32 %sub4
+  ret i32 %cond6
+; CHECK-LABEL: @abs_abs_x5(
+; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp slt i32 %x, 0
+; CHECK-NEXT: [[NEG:%[a-z0-9]+]] = sub nsw i32 0, %x
+; CHECK-NEXT: [[SEL:%[a-z0-9]+]] = select i1 [[CMP]], i32 [[NEG]], i32 %x
+; CHECK-NEXT: ret i32 [[SEL]]
+}
+
+define i32 @abs_abs_x6(i32 %x) {
+  %cmp = icmp slt i32 %x, 0
+  %sub = sub nsw i32 0, %x
+  %cond = select i1 %cmp, i32 %sub, i32 %x
+  %cmp1 = icmp slt i32 %cond, 0
+  %sub3 = sub nsw i32 0, %cond
+  %cond6 = select i1 %cmp1, i32 %sub3, i32 %cond
+  ret i32 %cond6
+; CHECK-LABEL: @abs_abs_x6(
+; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp slt i32 %x, 0
+; CHECK-NEXT: [[NEG:%[a-z0-9]+]] = sub nsw i32 0, %x
+; CHECK-NEXT: [[SEL:%[a-z0-9]+]] = select i1 [[CMP]], i32 [[NEG]], i32 %x
+; CHECK-NEXT: ret i32 [[SEL]]
 }
 No newline at end of file