From ab29f091eb64c8608ba943df604b218bcff41a26 Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Mon, 23 Nov 2020 16:46:41 -0500 Subject: [PATCH] [InstCombine] propagate 'nsw' on pointer difference of 'inbounds' geps This is a retry of 324a53205. I cautiously reverted that at 6aa3fc4 because the rules about gep math were not clear. Since then, we have added this line to LangRef for gep inbounds: "The successive addition of offsets (without adding the base address) does not wrap the pointer index type in a signed sense (nsw)." See D90708 and post-commit comments on the revert patch for more details. --- llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp | 7 ++++--- llvm/test/Transforms/InstCombine/sub-gep.ll | 16 +++++++++++----- llvm/test/Transforms/InstCombine/sub.ll | 2 +- 3 files changed, 16 insertions(+), 9 deletions(-) diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp index b8431a5..9a6a790 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp @@ -1678,11 +1678,12 @@ Value *InstCombinerImpl::OptimizePointerDifference(Value *LHS, Value *RHS, I->getOpcode() == Instruction::Mul) I->setHasNoUnsignedWrap(); - // If we had a constant expression GEP on the other side offsetting the - // pointer, subtract it from the offset we have. + // If we have a 2nd GEP of the same base pointer, subtract the offsets. + // If both GEPs are inbounds, then the subtract does not have signed overflow. if (GEP2) { Value *Offset = EmitGEPOffset(GEP2); - Result = Builder.CreateSub(Result, Offset, "gepdiff"); + Result = Builder.CreateSub(Result, Offset, "gepdiff", /* NUW */ false, + GEP1->isInBounds() && GEP2->isInBounds()); } // If we have p - gep(p, ...) then we have to negate the result. diff --git a/llvm/test/Transforms/InstCombine/sub-gep.ll b/llvm/test/Transforms/InstCombine/sub-gep.ll index 9868ed1..2389b70 100644 --- a/llvm/test/Transforms/InstCombine/sub-gep.ll +++ b/llvm/test/Transforms/InstCombine/sub-gep.ll @@ -245,7 +245,7 @@ define i64 @test24b(i8* %P, i64 %A){ define i64 @test25(i8* %P, i64 %A){ ; CHECK-LABEL: @test25( ; CHECK-NEXT: [[B_IDX:%.*]] = shl nsw i64 [[A:%.*]], 1 -; CHECK-NEXT: [[GEPDIFF:%.*]] = add i64 [[B_IDX]], -84 +; CHECK-NEXT: [[GEPDIFF:%.*]] = add nsw i64 [[B_IDX]], -84 ; CHECK-NEXT: ret i64 [[GEPDIFF]] ; %B = getelementptr inbounds [42 x i16], [42 x i16]* @Arr, i64 0, i64 %A @@ -260,7 +260,7 @@ define i16 @test25_as1(i8 addrspace(1)* %P, i64 %A) { ; CHECK-LABEL: @test25_as1( ; CHECK-NEXT: [[TMP1:%.*]] = trunc i64 [[A:%.*]] to i16 ; CHECK-NEXT: [[B_IDX:%.*]] = shl nsw i16 [[TMP1]], 1 -; CHECK-NEXT: [[GEPDIFF:%.*]] = add i16 [[B_IDX]], -84 +; CHECK-NEXT: [[GEPDIFF:%.*]] = add nsw i16 [[B_IDX]], -84 ; CHECK-NEXT: ret i16 [[GEPDIFF]] ; %B = getelementptr inbounds [42 x i16], [42 x i16] addrspace(1)* @Arr_as1, i64 0, i64 %A @@ -272,7 +272,7 @@ define i16 @test25_as1(i8 addrspace(1)* %P, i64 %A) { define i64 @test30(i8* %foo, i64 %i, i64 %j) { ; CHECK-LABEL: @test30( ; CHECK-NEXT: [[GEP1_IDX:%.*]] = shl nsw i64 [[I:%.*]], 2 -; CHECK-NEXT: [[GEPDIFF:%.*]] = sub i64 [[GEP1_IDX]], [[J:%.*]] +; CHECK-NEXT: [[GEPDIFF:%.*]] = sub nsw i64 [[GEP1_IDX]], [[J:%.*]] ; CHECK-NEXT: ret i64 [[GEPDIFF]] ; %bit = bitcast i8* %foo to i32* @@ -287,7 +287,7 @@ define i64 @test30(i8* %foo, i64 %i, i64 %j) { define i16 @test30_as1(i8 addrspace(1)* %foo, i16 %i, i16 %j) { ; CHECK-LABEL: @test30_as1( ; CHECK-NEXT: [[GEP1_IDX:%.*]] = shl nsw i16 [[I:%.*]], 2 -; CHECK-NEXT: [[GEPDIFF:%.*]] = sub i16 [[GEP1_IDX]], [[J:%.*]] +; CHECK-NEXT: [[GEPDIFF:%.*]] = sub nsw i16 [[GEP1_IDX]], [[J:%.*]] ; CHECK-NEXT: ret i16 [[GEPDIFF]] ; %bit = bitcast i8 addrspace(1)* %foo to i32 addrspace(1)* @@ -299,9 +299,11 @@ define i16 @test30_as1(i8 addrspace(1)* %foo, i16 %i, i16 %j) { ret i16 %sub } +; Inbounds translates to 'nsw' on sub + define i64 @gep_diff_both_inbounds(i8* %foo, i64 %i, i64 %j) { ; CHECK-LABEL: @gep_diff_both_inbounds( -; CHECK-NEXT: [[GEPDIFF:%.*]] = sub i64 [[I:%.*]], [[J:%.*]] +; CHECK-NEXT: [[GEPDIFF:%.*]] = sub nsw i64 [[I:%.*]], [[J:%.*]] ; CHECK-NEXT: ret i64 [[GEPDIFF]] ; %gep1 = getelementptr inbounds i8, i8* %foo, i64 %i @@ -312,6 +314,8 @@ define i64 @gep_diff_both_inbounds(i8* %foo, i64 %i, i64 %j) { ret i64 %sub } +; Negative test for 'nsw' - both geps must be inbounds + define i64 @gep_diff_first_inbounds(i8* %foo, i64 %i, i64 %j) { ; CHECK-LABEL: @gep_diff_first_inbounds( ; CHECK-NEXT: [[GEPDIFF:%.*]] = sub i64 [[I:%.*]], [[J:%.*]] @@ -325,6 +329,8 @@ define i64 @gep_diff_first_inbounds(i8* %foo, i64 %i, i64 %j) { ret i64 %sub } +; Negative test for 'nsw' - both geps must be inbounds + define i64 @gep_diff_second_inbounds(i8* %foo, i64 %i, i64 %j) { ; CHECK-LABEL: @gep_diff_second_inbounds( ; CHECK-NEXT: [[GEPDIFF:%.*]] = sub i64 [[I:%.*]], [[J:%.*]] diff --git a/llvm/test/Transforms/InstCombine/sub.ll b/llvm/test/Transforms/InstCombine/sub.ll index d9c67d0..7809a93 100644 --- a/llvm/test/Transforms/InstCombine/sub.ll +++ b/llvm/test/Transforms/InstCombine/sub.ll @@ -1077,7 +1077,7 @@ define i64 @test58([100 x [100 x i8]]* %foo, i64 %i, i64 %j) { ; CHECK-LABEL: @test58( ; CHECK-NEXT: [[GEP1_OFFS:%.*]] = add nsw i64 [[I:%.*]], 4200 ; CHECK-NEXT: [[GEP2_OFFS:%.*]] = add nsw i64 [[J:%.*]], 4200 -; CHECK-NEXT: [[GEPDIFF:%.*]] = sub i64 [[GEP1_OFFS]], [[GEP2_OFFS]] +; CHECK-NEXT: [[GEPDIFF:%.*]] = sub nsw i64 [[GEP1_OFFS]], [[GEP2_OFFS]] ; CHECK-NEXT: ret i64 [[GEPDIFF]] ; %gep1 = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 42, i64 %i -- 2.7.4