From 864d2f9cf82ccc06deebd8458c019aa65b2b4012 Mon Sep 17 00:00:00 2001 From: Roman Lebedev Date: Wed, 25 Sep 2019 19:06:40 +0000 Subject: [PATCH] [InstCombine] Fold (A - B) u>=/u< A --> B u>/u<= A iff B != 0 https://rise4fun.com/Alive/KtL This also shows that the fold added in D67412 / r372257 was too specific, and the new fold allows those test cases to be handled more generically, therefore i delete now-dead code. This is yet again motivated by D67122 "[UBSan][clang][compiler-rt] Applying non-zero offset to nullptr is undefined behaviour" git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@372912 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../InstCombine/InstCombineAndOrXor.cpp | 15 --------------- .../InstCombine/InstCombineCompares.cpp | 17 +++++++++++++---- .../InstCombine/InstCombineInternal.h | 2 +- ...esult-of-usub-is-non-zero-and-no-overflow.ll | 8 ++++---- ...rflow-check-to-comparison-of-sub-operands.ll | 8 ++++---- 5 files changed, 22 insertions(+), 28 deletions(-) diff --git a/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp index 3eeb2272613..6252e5d15a1 100644 --- a/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ b/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -1107,21 +1107,6 @@ static Value *foldUnsignedUnderflowCheck(ICmpInst *ZeroICmp, if (!match(ZeroCmpOp, m_Sub(m_Value(Base), m_Value(Offset)))) return nullptr; - // ZeroCmpOp < Base && ZeroCmpOp != 0 --> Base > Offset iff Offset != 0 - // ZeroCmpOp >= Base || ZeroCmpOp == 0 --> Base <= Base iff Offset != 0 - if (match(UnsignedICmp, - m_c_ICmp(UnsignedPred, m_Specific(ZeroCmpOp), m_Specific(Base)))) { - if (UnsignedICmp->getOperand(0) != ZeroCmpOp) - UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred); - - if (UnsignedPred == ICmpInst::ICMP_ULT && IsAnd && - EqPred == ICmpInst::ICMP_NE && IsKnownNonZero(Offset)) - return Builder.CreateICmpUGT(Base, Offset); - if (UnsignedPred == ICmpInst::ICMP_UGE && !IsAnd && - EqPred == ICmpInst::ICMP_EQ && IsKnownNonZero(Offset)) - return Builder.CreateICmpULE(Base, Offset); - } - if (!match(UnsignedICmp, m_c_ICmp(UnsignedPred, m_Specific(Base), m_Specific(Offset))) || !ICmpInst::isUnsigned(UnsignedPred)) diff --git a/lib/Transforms/InstCombine/InstCombineCompares.cpp b/lib/Transforms/InstCombine/InstCombineCompares.cpp index 5bafab49032..b68266705e5 100644 --- a/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ b/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -3638,7 +3638,8 @@ Value *InstCombiner::foldUnsignedMultiplicationOverflowCheck(ICmpInst &I) { /// TODO: A large part of this logic is duplicated in InstSimplify's /// simplifyICmpWithBinOp(). We should be able to share that and avoid the code /// duplication. -Instruction *InstCombiner::foldICmpBinOp(ICmpInst &I) { +Instruction *InstCombiner::foldICmpBinOp(ICmpInst &I, const SimplifyQuery &SQ) { + const SimplifyQuery Q = SQ.getWithInstruction(&I); Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); // Special logic for binary operators. @@ -3840,6 +3841,14 @@ Instruction *InstCombiner::foldICmpBinOp(ICmpInst &I) { // C u= (C - D) --> C u= D if (C == Op0 && (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_UGE)) return new ICmpInst(Pred, C, D); + // (A - B) u>=/u< A --> B u>/u<= A iff B != 0 + if (A == Op1 && (Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_ULT) && + isKnownNonZero(B, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT)) + return new ICmpInst(CmpInst::getFlippedStrictnessPredicate(Pred), B, A); + // C u<=/u> (C - D) --> C u= D iff B != 0 + if (C == Op0 && (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_UGT) && + isKnownNonZero(D, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT)) + return new ICmpInst(CmpInst::getFlippedStrictnessPredicate(Pred), C, D); // icmp (A-B), (C-B) -> icmp A, C for equalities or if there is no overflow. if (B && D && B == D && NoOp0WrapProblem && NoOp1WrapProblem) @@ -5346,6 +5355,7 @@ static Instruction *foldVectorCmp(CmpInst &Cmp, Instruction *InstCombiner::visitICmpInst(ICmpInst &I) { bool Changed = false; + const SimplifyQuery Q = SQ.getWithInstruction(&I); Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); unsigned Op0Cplxity = getComplexity(Op0); unsigned Op1Cplxity = getComplexity(Op1); @@ -5360,8 +5370,7 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) { Changed = true; } - if (Value *V = SimplifyICmpInst(I.getPredicate(), Op0, Op1, - SQ.getWithInstruction(&I))) + if (Value *V = SimplifyICmpInst(I.getPredicate(), Op0, Op1, Q)) return replaceInstUsesWith(I, V); // Comparing -val or val with non-zero is the same as just comparing val @@ -5394,7 +5403,7 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) { if (Instruction *Res = foldICmpWithDominatingICmp(I)) return Res; - if (Instruction *Res = foldICmpBinOp(I)) + if (Instruction *Res = foldICmpBinOp(I, Q)) return Res; if (Instruction *Res = foldICmpUsingKnownBits(I)) diff --git a/lib/Transforms/InstCombine/InstCombineInternal.h b/lib/Transforms/InstCombine/InstCombineInternal.h index 5e4a56ba257..673099436b7 100644 --- a/lib/Transforms/InstCombine/InstCombineInternal.h +++ b/lib/Transforms/InstCombine/InstCombineInternal.h @@ -868,7 +868,7 @@ private: Instruction *foldICmpWithConstant(ICmpInst &Cmp); Instruction *foldICmpInstWithConstant(ICmpInst &Cmp); Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp); - Instruction *foldICmpBinOp(ICmpInst &Cmp); + Instruction *foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ); Instruction *foldICmpEquality(ICmpInst &Cmp); Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I); Instruction *foldICmpWithZero(ICmpInst &Cmp); diff --git a/test/Transforms/InstCombine/result-of-usub-is-non-zero-and-no-overflow.ll b/test/Transforms/InstCombine/result-of-usub-is-non-zero-and-no-overflow.ll index 8a5b444d3ed..26bbc445296 100644 --- a/test/Transforms/InstCombine/result-of-usub-is-non-zero-and-no-overflow.ll +++ b/test/Transforms/InstCombine/result-of-usub-is-non-zero-and-no-overflow.ll @@ -292,7 +292,7 @@ define i1 @t10(i64 %base, i64* nonnull %offsetptr) { ; CHECK-NEXT: [[OFFSET:%.*]] = ptrtoint i64* [[OFFSETPTR:%.*]] to i64 ; CHECK-NEXT: [[ADJUSTED:%.*]] = sub i64 [[BASE:%.*]], [[OFFSET]] ; CHECK-NEXT: call void @use64(i64 [[ADJUSTED]]) -; CHECK-NEXT: [[NO_UNDERFLOW:%.*]] = icmp ult i64 [[ADJUSTED]], [[BASE]] +; CHECK-NEXT: [[NO_UNDERFLOW:%.*]] = icmp ule i64 [[OFFSET]], [[BASE]] ; CHECK-NEXT: call void @use1(i1 [[NO_UNDERFLOW]]) ; CHECK-NEXT: [[NOT_NULL:%.*]] = icmp ne i64 [[ADJUSTED]], 0 ; CHECK-NEXT: call void @use1(i1 [[NOT_NULL]]) @@ -315,7 +315,7 @@ define i1 @t11_commutative(i64 %base, i64* nonnull %offsetptr) { ; CHECK-NEXT: [[OFFSET:%.*]] = ptrtoint i64* [[OFFSETPTR:%.*]] to i64 ; CHECK-NEXT: [[ADJUSTED:%.*]] = sub i64 [[BASE:%.*]], [[OFFSET]] ; CHECK-NEXT: call void @use64(i64 [[ADJUSTED]]) -; CHECK-NEXT: [[NO_UNDERFLOW:%.*]] = icmp ult i64 [[ADJUSTED]], [[BASE]] +; CHECK-NEXT: [[NO_UNDERFLOW:%.*]] = icmp ule i64 [[OFFSET]], [[BASE]] ; CHECK-NEXT: call void @use1(i1 [[NO_UNDERFLOW]]) ; CHECK-NEXT: [[NOT_NULL:%.*]] = icmp ne i64 [[ADJUSTED]], 0 ; CHECK-NEXT: call void @use1(i1 [[NOT_NULL]]) @@ -339,7 +339,7 @@ define i1 @t12(i64 %base, i64* nonnull %offsetptr) { ; CHECK-NEXT: [[OFFSET:%.*]] = ptrtoint i64* [[OFFSETPTR:%.*]] to i64 ; CHECK-NEXT: [[ADJUSTED:%.*]] = sub i64 [[BASE:%.*]], [[OFFSET]] ; CHECK-NEXT: call void @use64(i64 [[ADJUSTED]]) -; CHECK-NEXT: [[NO_UNDERFLOW:%.*]] = icmp uge i64 [[ADJUSTED]], [[BASE]] +; CHECK-NEXT: [[NO_UNDERFLOW:%.*]] = icmp ugt i64 [[OFFSET]], [[BASE]] ; CHECK-NEXT: call void @use1(i1 [[NO_UNDERFLOW]]) ; CHECK-NEXT: [[NOT_NULL:%.*]] = icmp eq i64 [[ADJUSTED]], 0 ; CHECK-NEXT: call void @use1(i1 [[NOT_NULL]]) @@ -362,7 +362,7 @@ define i1 @t13(i64 %base, i64* nonnull %offsetptr) { ; CHECK-NEXT: [[OFFSET:%.*]] = ptrtoint i64* [[OFFSETPTR:%.*]] to i64 ; CHECK-NEXT: [[ADJUSTED:%.*]] = sub i64 [[BASE:%.*]], [[OFFSET]] ; CHECK-NEXT: call void @use64(i64 [[ADJUSTED]]) -; CHECK-NEXT: [[NO_UNDERFLOW:%.*]] = icmp uge i64 [[ADJUSTED]], [[BASE]] +; CHECK-NEXT: [[NO_UNDERFLOW:%.*]] = icmp ugt i64 [[OFFSET]], [[BASE]] ; CHECK-NEXT: call void @use1(i1 [[NO_UNDERFLOW]]) ; CHECK-NEXT: [[NOT_NULL:%.*]] = icmp eq i64 [[ADJUSTED]], 0 ; CHECK-NEXT: call void @use1(i1 [[NOT_NULL]]) diff --git a/test/Transforms/InstCombine/strict-sub-underflow-check-to-comparison-of-sub-operands.ll b/test/Transforms/InstCombine/strict-sub-underflow-check-to-comparison-of-sub-operands.ll index ceef17a3737..9abb588a4ee 100644 --- a/test/Transforms/InstCombine/strict-sub-underflow-check-to-comparison-of-sub-operands.ll +++ b/test/Transforms/InstCombine/strict-sub-underflow-check-to-comparison-of-sub-operands.ll @@ -11,7 +11,7 @@ define i1 @t0(i8 %base, i8 %offset) { ; CHECK-NEXT: call void @llvm.assume(i1 [[CMP]]) ; CHECK-NEXT: [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET]] ; CHECK-NEXT: call void @use8(i8 [[ADJUSTED]]) -; CHECK-NEXT: [[RES:%.*]] = icmp ult i8 [[ADJUSTED]], [[BASE]] +; CHECK-NEXT: [[RES:%.*]] = icmp uge i8 [[BASE]], [[OFFSET]] ; CHECK-NEXT: ret i1 [[RES]] ; %cmp = icmp slt i8 %offset, 0 @@ -28,7 +28,7 @@ define i1 @t1(i8 %base, i8 %offset) { ; CHECK-NEXT: call void @llvm.assume(i1 [[CMP]]) ; CHECK-NEXT: [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET]] ; CHECK-NEXT: call void @use8(i8 [[ADJUSTED]]) -; CHECK-NEXT: [[RES:%.*]] = icmp uge i8 [[ADJUSTED]], [[BASE]] +; CHECK-NEXT: [[RES:%.*]] = icmp ult i8 [[BASE]], [[OFFSET]] ; CHECK-NEXT: ret i1 [[RES]] ; %cmp = icmp slt i8 %offset, 0 @@ -46,7 +46,7 @@ define i1 @t2(i8 %offset) { ; CHECK-NEXT: [[BASE:%.*]] = call i8 @gen8() ; CHECK-NEXT: [[ADJUSTED:%.*]] = sub i8 [[BASE]], [[OFFSET]] ; CHECK-NEXT: call void @use8(i8 [[ADJUSTED]]) -; CHECK-NEXT: [[RES:%.*]] = icmp ugt i8 [[BASE]], [[ADJUSTED]] +; CHECK-NEXT: [[RES:%.*]] = icmp uge i8 [[BASE]], [[OFFSET]] ; CHECK-NEXT: ret i1 [[RES]] ; %cmp = icmp slt i8 %offset, 0 @@ -65,7 +65,7 @@ define i1 @t3(i8 %offset) { ; CHECK-NEXT: [[BASE:%.*]] = call i8 @gen8() ; CHECK-NEXT: [[ADJUSTED:%.*]] = sub i8 [[BASE]], [[OFFSET]] ; CHECK-NEXT: call void @use8(i8 [[ADJUSTED]]) -; CHECK-NEXT: [[RES:%.*]] = icmp ule i8 [[BASE]], [[ADJUSTED]] +; CHECK-NEXT: [[RES:%.*]] = icmp ult i8 [[BASE]], [[OFFSET]] ; CHECK-NEXT: ret i1 [[RES]] ; %cmp = icmp slt i8 %offset, 0 -- 2.40.0