[InstSimplify] fold icmp based on range of abs/nabs (2nd try)
This is retrying the fold from rL345717
(reverted at rL347780)
...with a fix for the miscompile
demonstrated by PR39510:
https://bugs.llvm.org/show_bug.cgi?id=39510
Original commit message:
This is a fix for PR39475:
https://bugs.llvm.org/show_bug.cgi?id=39475
We managed to get some of these patterns using computeKnownBits in https://reviews.llvm.org/D47041, but that
can't be used for nabs(). Instead, put in some range-based logic, so we can fold
both abs/nabs with icmp with a constant value.
Alive proofs:
https://rise4fun.com/Alive/21r
Name: abs_nsw_is_positive
%cmp = icmp slt i32 %x, 0
%negx = sub nsw i32 0, %x
%abs = select i1 %cmp, i32 %negx, i32 %x
%r = icmp sgt i32 %abs, -1
=>
%r = i1 true
Name: abs_nsw_is_not_negative
%cmp = icmp slt i32 %x, 0
%negx = sub nsw i32 0, %x
%abs = select i1 %cmp, i32 %negx, i32 %x
%r = icmp slt i32 %abs, 0
=>
%r = i1 false
Name: nabs_is_negative_or_0
%cmp = icmp slt i32 %x, 0
%negx = sub i32 0, %x
%nabs = select i1 %cmp, i32 %x, i32 %negx
%r = icmp slt i32 %nabs, 1
=>
%r = i1 true
Name: nabs_is_not_over_0
%cmp = icmp slt i32 %x, 0
%negx = sub i32 0, %x
%nabs = select i1 %cmp, i32 %x, i32 %negx
%r = icmp sgt i32 %nabs, 0
=>
%r = i1 false
Differential Revision: https://reviews.llvm.org/D53844
llvm-svn: 345832
diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp
index c4b0763..db929aa 100644
--- a/llvm/lib/Analysis/InstructionSimplify.cpp
+++ b/llvm/lib/Analysis/InstructionSimplify.cpp
@@ -2996,6 +2996,44 @@
return nullptr;
}
+static Value *simplifyICmpWithAbsNabs(CmpInst::Predicate Pred, Value *Op0,
+ Value *Op1) {
+ // We need a comparison with a constant.
+ const APInt *C;
+ if (!match(Op1, m_APInt(C)))
+ return nullptr;
+
+ // matchSelectPattern returns the negation part of an abs pattern in SP1.
+ // If the negate has an NSW flag, abs(INT_MIN) is undefined. Without that
+ // constraint, we can't make a contiguous range for the result of abs.
+ ICmpInst::Predicate AbsPred = ICmpInst::BAD_ICMP_PREDICATE;
+ Value *SP0, *SP1;
+ SelectPatternFlavor SPF = matchSelectPattern(Op0, SP0, SP1).Flavor;
+ if (SPF == SelectPatternFlavor::SPF_ABS &&
+ cast<Instruction>(SP1)->hasNoSignedWrap())
+ // The result of abs(X) is >= 0 (with nsw).
+ AbsPred = ICmpInst::ICMP_SGE;
+ if (SPF == SelectPatternFlavor::SPF_NABS)
+ // The result of -abs(X) is <= 0.
+ AbsPred = ICmpInst::ICMP_SLE;
+
+ if (AbsPred == ICmpInst::BAD_ICMP_PREDICATE)
+ return nullptr;
+
+ // If there is no intersection between abs/nabs and the range of this icmp,
+ // the icmp must be false. If the abs/nabs range is a subset of the icmp
+ // range, the icmp must be true.
+ APInt Zero = APInt::getNullValue(C->getBitWidth());
+ ConstantRange AbsRange = ConstantRange::makeExactICmpRegion(AbsPred, Zero);
+ ConstantRange CmpRange = ConstantRange::makeExactICmpRegion(Pred, *C);
+ if (AbsRange.intersectWith(CmpRange).isEmptySet())
+ return getFalse(GetCompareTy(Op0));
+ if (CmpRange.contains(AbsRange))
+ return getTrue(GetCompareTy(Op0));
+
+ return nullptr;
+}
+
/// Simplify integer comparisons where at least one operand of the compare
/// matches an integer min/max idiom.
static Value *simplifyICmpWithMinMax(CmpInst::Predicate Pred, Value *LHS,
@@ -3427,6 +3465,9 @@
if (Value *V = simplifyICmpWithMinMax(Pred, LHS, RHS, Q, MaxRecurse))
return V;
+ if (Value *V = simplifyICmpWithAbsNabs(Pred, LHS, RHS))
+ return V;
+
// Simplify comparisons of related pointers using a powerful, recursive
// GEP-walk when we have target data available..
if (LHS->getType()->isPointerTy())