https://github.com/bjope updated https://github.com/llvm/llvm-project/pull/135155
From 0abeb7b7eea0e15e15c98a8e4f8501fde81d4811 Mon Sep 17 00:00:00 2001 From: Bjorn Pettersson <bjorn.a.petters...@ericsson.com> Date: Tue, 11 Mar 2025 16:27:43 +0100 Subject: [PATCH 1/2] [InstCombine] Improve inbounds preservation for ADD+GEP -> GEP+GEP Given that we have a "add nuw" and a "getelementptr inbounds nuw" like this: %idx = add nuw i64 %idx1, %idx2 %gep = getelementptr inbounds nuw i32, ptr %ptr, i64 %idx Then we can preserve the "inbounds nuw" flag when transforming that into two getelementptr instructions: %gep1 = getelementptr inbounds nuw i32, ptr %ptr, i64 %idx1 %gep = getelementptr inbounds nuw i32, ptr %ptr, i64 %idx2 Similarly for just having "nuw" instead of "inbounds nuw" on the getelementptr. Proof: https://alive2.llvm.org/ce/z/4uhfDq --- .../InstCombine/InstructionCombining.cpp | 43 +++++++++++-------- llvm/test/Transforms/InstCombine/array.ll | 10 ++--- 2 files changed, 30 insertions(+), 23 deletions(-) diff --git a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp index 856e02c9f1ddb..19a818f4baa30 100644 --- a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -3087,12 +3087,22 @@ Instruction *InstCombinerImpl::visitGetElementPtrInst(GetElementPtrInst &GEP) { return nullptr; if (GEP.getNumIndices() == 1) { - // We can only preserve inbounds if the original gep is inbounds, the add - // is nsw, and the add operands are non-negative. - auto CanPreserveInBounds = [&](bool AddIsNSW, Value *Idx1, Value *Idx2) { + auto CanPreserveNoWrapFlags = [&](bool AddIsNSW, bool AddIsNUW, Value *Idx1, + Value *Idx2) { + // Preserve "inbounds nuw" if the original gep is "inbounds nuw", + // and the add is "nuw". + if (GEP.isInBounds() && GEP.hasNoUnsignedWrap() && AddIsNUW) + return GEPNoWrapFlags::inBounds() | GEPNoWrapFlags::noUnsignedWrap(); + // Preserve "inbounds" if the original gep is "inbounds", the add + // is "nsw", and the add operands are non-negative. SimplifyQuery Q = SQ.getWithInstruction(&GEP); - return GEP.isInBounds() && AddIsNSW && isKnownNonNegative(Idx1, Q) && - isKnownNonNegative(Idx2, Q); + if (GEP.isInBounds() && AddIsNSW && isKnownNonNegative(Idx1, Q) && + isKnownNonNegative(Idx2, Q)) + return GEPNoWrapFlags::inBounds(); + // Preserve "nuw" if the original gep is "nuw", and the add is "nuw". + if (GEP.hasNoUnsignedWrap() && AddIsNUW) + return GEPNoWrapFlags::noUnsignedWrap(); + return GEPNoWrapFlags::none(); }; // Try to replace ADD + GEP with GEP + GEP. @@ -3104,15 +3114,15 @@ Instruction *InstCombinerImpl::visitGetElementPtrInst(GetElementPtrInst &GEP) { // as: // %newptr = getelementptr i32, ptr %ptr, i64 %idx1 // %newgep = getelementptr i32, ptr %newptr, i64 %idx2 - bool IsInBounds = CanPreserveInBounds( - cast<OverflowingBinaryOperator>(GEP.getOperand(1))->hasNoSignedWrap(), - Idx1, Idx2); + bool NSW = match(GEP.getOperand(1), m_NSWAddLike(m_Value(), m_Value())); + bool NUW = match(GEP.getOperand(1), m_NUWAddLike(m_Value(), m_Value())); + GEPNoWrapFlags NWFlags = CanPreserveNoWrapFlags(NSW, NUW, Idx1, Idx2); auto *NewPtr = Builder.CreateGEP(GEP.getSourceElementType(), GEP.getPointerOperand(), - Idx1, "", IsInBounds); - return replaceInstUsesWith( - GEP, Builder.CreateGEP(GEP.getSourceElementType(), NewPtr, Idx2, "", - IsInBounds)); + Idx1, "", NWFlags); + return replaceInstUsesWith(GEP, + Builder.CreateGEP(GEP.getSourceElementType(), + NewPtr, Idx2, "", NWFlags)); } ConstantInt *C; if (match(GEP.getOperand(1), m_OneUse(m_SExtLike(m_OneUse(m_NSWAdd( @@ -3123,17 +3133,16 @@ Instruction *InstCombinerImpl::visitGetElementPtrInst(GetElementPtrInst &GEP) { // as: // %newptr = getelementptr i32, ptr %ptr, i32 %idx1 // %newgep = getelementptr i32, ptr %newptr, i32 idx2 - bool IsInBounds = CanPreserveInBounds( - /*IsNSW=*/true, Idx1, C); + GEPNoWrapFlags NWFlags = CanPreserveNoWrapFlags( + /*IsNSW=*/true, /*IsNUW=*/false, Idx1, C); auto *NewPtr = Builder.CreateGEP( GEP.getSourceElementType(), GEP.getPointerOperand(), - Builder.CreateSExt(Idx1, GEP.getOperand(1)->getType()), "", - IsInBounds); + Builder.CreateSExt(Idx1, GEP.getOperand(1)->getType()), "", NWFlags); return replaceInstUsesWith( GEP, Builder.CreateGEP(GEP.getSourceElementType(), NewPtr, Builder.CreateSExt(C, GEP.getOperand(1)->getType()), - "", IsInBounds)); + "", NWFlags)); } } diff --git a/llvm/test/Transforms/InstCombine/array.ll b/llvm/test/Transforms/InstCombine/array.ll index 763c6e77f89ee..5d389958173a5 100644 --- a/llvm/test/Transforms/InstCombine/array.ll +++ b/llvm/test/Transforms/InstCombine/array.ll @@ -122,12 +122,11 @@ define ptr @gep_inbounds_nuwaddlike(ptr %ptr, i64 %a, i64 %b) { ret ptr %gep } -; FIXME: Preserve "inbounds nuw". define ptr @gep_inbounds_add_nuw(ptr %ptr, i64 %a, i64 %b) { ; CHECK-LABEL: define ptr @gep_inbounds_add_nuw( ; CHECK-SAME: ptr [[PTR:%.*]], i64 [[A:%.*]], i64 [[B:%.*]]) { -; CHECK-NEXT: [[TMP1:%.*]] = getelementptr i32, ptr [[PTR]], i64 [[A]] -; CHECK-NEXT: [[GEP:%.*]] = getelementptr i32, ptr [[TMP1]], i64 [[B]] +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds nuw i32, ptr [[PTR]], i64 [[A]] +; CHECK-NEXT: [[GEP:%.*]] = getelementptr inbounds nuw i32, ptr [[TMP1]], i64 [[B]] ; CHECK-NEXT: ret ptr [[GEP]] ; %add = add nuw i64 %a, %b @@ -135,12 +134,11 @@ define ptr @gep_inbounds_add_nuw(ptr %ptr, i64 %a, i64 %b) { ret ptr %gep } -; FIXME: Preserve "nuw". define ptr @gep_add_nuw(ptr %ptr, i64 %a, i64 %b) { ; CHECK-LABEL: define ptr @gep_add_nuw( ; CHECK-SAME: ptr [[PTR:%.*]], i64 [[A:%.*]], i64 [[B:%.*]]) { -; CHECK-NEXT: [[TMP1:%.*]] = getelementptr i32, ptr [[PTR]], i64 [[A]] -; CHECK-NEXT: [[GEP:%.*]] = getelementptr i32, ptr [[TMP1]], i64 [[B]] +; CHECK-NEXT: [[TMP1:%.*]] = getelementptr nuw i32, ptr [[PTR]], i64 [[A]] +; CHECK-NEXT: [[GEP:%.*]] = getelementptr nuw i32, ptr [[TMP1]], i64 [[B]] ; CHECK-NEXT: ret ptr [[GEP]] ; %add = add nuw i64 %a, %b From 3ed5acf4ce65100bfa28ea50a7689b82ad3ce3ff Mon Sep 17 00:00:00 2001 From: Bjorn Pettersson <bjorn.a.petters...@ericsson.com> Date: Thu, 10 Apr 2025 15:00:34 +0200 Subject: [PATCH 2/2] Fixups after review feedback: - Make sure we try to derive inbound + nuw before doing the ADD+GEP->GEP+GEP rewrites. This to make it possible to rely on "nuw" being present when trying to preserve flags. - Make sure the special ADDNSW+SEXTLIKE+GEP->GEP+GEP case is checking for ADDNUW+ZEXTNNEG+GEP->GEP+GEP when preserving flags. This way we do not need to check for non-negative operands. --- .../InstCombine/InstructionCombining.cpp | 99 +++++++++---------- 1 file changed, 48 insertions(+), 51 deletions(-) diff --git a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp index 19a818f4baa30..b5e085be9b084 100644 --- a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -3086,23 +3086,51 @@ Instruction *InstCombinerImpl::visitGetElementPtrInst(GetElementPtrInst &GEP) { if (GEPType->isVectorTy()) return nullptr; + if (!GEP.isInBounds()) { + unsigned IdxWidth = + DL.getIndexSizeInBits(PtrOp->getType()->getPointerAddressSpace()); + APInt BasePtrOffset(IdxWidth, 0); + Value *UnderlyingPtrOp = + PtrOp->stripAndAccumulateInBoundsConstantOffsets(DL, + BasePtrOffset); + bool CanBeNull, CanBeFreed; + uint64_t DerefBytes = UnderlyingPtrOp->getPointerDereferenceableBytes( + DL, CanBeNull, CanBeFreed); + if (!CanBeNull && !CanBeFreed && DerefBytes != 0) { + if (GEP.accumulateConstantOffset(DL, BasePtrOffset) && + BasePtrOffset.isNonNegative()) { + APInt AllocSize(IdxWidth, DerefBytes); + if (BasePtrOffset.ule(AllocSize)) { + return GetElementPtrInst::CreateInBounds( + GEP.getSourceElementType(), PtrOp, Indices, GEP.getName()); + } + } + } + } + + // nusw + nneg -> nuw + if (GEP.hasNoUnsignedSignedWrap() && !GEP.hasNoUnsignedWrap() && + all_of(GEP.indices(), [&](Value *Idx) { + return isKnownNonNegative(Idx, SQ.getWithInstruction(&GEP)); + })) { + GEP.setNoWrapFlags(GEP.getNoWrapFlags() | GEPNoWrapFlags::noUnsignedWrap()); + return &GEP; + } + + // These rewrites is trying to preserve inbounds/nuw attributes. So we want to + // do this after having tried to derive "nuw" above. if (GEP.getNumIndices() == 1) { - auto CanPreserveNoWrapFlags = [&](bool AddIsNSW, bool AddIsNUW, Value *Idx1, - Value *Idx2) { - // Preserve "inbounds nuw" if the original gep is "inbounds nuw", - // and the add is "nuw". - if (GEP.isInBounds() && GEP.hasNoUnsignedWrap() && AddIsNUW) - return GEPNoWrapFlags::inBounds() | GEPNoWrapFlags::noUnsignedWrap(); - // Preserve "inbounds" if the original gep is "inbounds", the add - // is "nsw", and the add operands are non-negative. - SimplifyQuery Q = SQ.getWithInstruction(&GEP); - if (GEP.isInBounds() && AddIsNSW && isKnownNonNegative(Idx1, Q) && - isKnownNonNegative(Idx2, Q)) - return GEPNoWrapFlags::inBounds(); - // Preserve "nuw" if the original gep is "nuw", and the add is "nuw". - if (GEP.hasNoUnsignedWrap() && AddIsNUW) - return GEPNoWrapFlags::noUnsignedWrap(); - return GEPNoWrapFlags::none(); + auto GetPreservedNoWrapFlags = [&](bool AddIsNUW, Value *Idx1, Value *Idx2) { + // Preserve "inbounds nuw" if the original gep is "inbounds nuw", and the + // add is "nuw". Preserve "nuw" if the original gep is "nuw", and the add + // is "nuw". + GEPNoWrapFlags Flags = GEPNoWrapFlags::none(); + if (GEP.hasNoUnsignedWrap() && AddIsNUW) { + Flags |= GEPNoWrapFlags::noUnsignedWrap(); + if (GEP.isInBounds()) + Flags |= GEPNoWrapFlags::inBounds(); + } + return Flags; }; // Try to replace ADD + GEP with GEP + GEP. @@ -3114,9 +3142,8 @@ Instruction *InstCombinerImpl::visitGetElementPtrInst(GetElementPtrInst &GEP) { // as: // %newptr = getelementptr i32, ptr %ptr, i64 %idx1 // %newgep = getelementptr i32, ptr %newptr, i64 %idx2 - bool NSW = match(GEP.getOperand(1), m_NSWAddLike(m_Value(), m_Value())); bool NUW = match(GEP.getOperand(1), m_NUWAddLike(m_Value(), m_Value())); - GEPNoWrapFlags NWFlags = CanPreserveNoWrapFlags(NSW, NUW, Idx1, Idx2); + GEPNoWrapFlags NWFlags = GetPreservedNoWrapFlags(NUW, Idx1, Idx2); auto *NewPtr = Builder.CreateGEP(GEP.getSourceElementType(), GEP.getPointerOperand(), Idx1, "", NWFlags); @@ -3133,8 +3160,9 @@ Instruction *InstCombinerImpl::visitGetElementPtrInst(GetElementPtrInst &GEP) { // as: // %newptr = getelementptr i32, ptr %ptr, i32 %idx1 // %newgep = getelementptr i32, ptr %newptr, i32 idx2 - GEPNoWrapFlags NWFlags = CanPreserveNoWrapFlags( - /*IsNSW=*/true, /*IsNUW=*/false, Idx1, C); + bool NUW = match(GEP.getOperand(1), m_NNegZExt(m_NUWAddLike(m_Value(), + m_Value()))); + GEPNoWrapFlags NWFlags = GetPreservedNoWrapFlags(NUW, Idx1, C); auto *NewPtr = Builder.CreateGEP( GEP.getSourceElementType(), GEP.getPointerOperand(), Builder.CreateSExt(Idx1, GEP.getOperand(1)->getType()), "", NWFlags); @@ -3146,37 +3174,6 @@ Instruction *InstCombinerImpl::visitGetElementPtrInst(GetElementPtrInst &GEP) { } } - if (!GEP.isInBounds()) { - unsigned IdxWidth = - DL.getIndexSizeInBits(PtrOp->getType()->getPointerAddressSpace()); - APInt BasePtrOffset(IdxWidth, 0); - Value *UnderlyingPtrOp = - PtrOp->stripAndAccumulateInBoundsConstantOffsets(DL, - BasePtrOffset); - bool CanBeNull, CanBeFreed; - uint64_t DerefBytes = UnderlyingPtrOp->getPointerDereferenceableBytes( - DL, CanBeNull, CanBeFreed); - if (!CanBeNull && !CanBeFreed && DerefBytes != 0) { - if (GEP.accumulateConstantOffset(DL, BasePtrOffset) && - BasePtrOffset.isNonNegative()) { - APInt AllocSize(IdxWidth, DerefBytes); - if (BasePtrOffset.ule(AllocSize)) { - return GetElementPtrInst::CreateInBounds( - GEP.getSourceElementType(), PtrOp, Indices, GEP.getName()); - } - } - } - } - - // nusw + nneg -> nuw - if (GEP.hasNoUnsignedSignedWrap() && !GEP.hasNoUnsignedWrap() && - all_of(GEP.indices(), [&](Value *Idx) { - return isKnownNonNegative(Idx, SQ.getWithInstruction(&GEP)); - })) { - GEP.setNoWrapFlags(GEP.getNoWrapFlags() | GEPNoWrapFlags::noUnsignedWrap()); - return &GEP; - } - if (Instruction *R = foldSelectGEP(GEP, Builder)) return R; _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
