From f197cf2126be3b224cadfe8b1cde9c05f638a0ea Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Sun, 14 Feb 2021 18:51:45 +0100 Subject: [PATCH] [BasicAA] Merge aliasGEP code paths At this point, we can treat the case of GEP/GEP aliasing and GEP/non-GEP aliasing in essentially the same way. The only differences are that we need to do an additional negative GEP base check, and that we perform a bailout on unknown sizes for the GEP/non-GEP case (the latter exists only to limit compile-time). This change is not quite NFC due to the peculiar effect that the DecomposedGEP for V2 can actually be non-trivial even if V2 is not a GEP. The reason for this is that getUnderlyingObject() can look through LCSSA phi nodes, while stripPointerCasts() doesn't. This can lead to slightly better results if single-entry phi nodes occur inside a loop, where looking through the phi node via aliasPhi() would subject it to phi cycle equivalence restrictions. It would probably make sense to adjust pointer cast stripping (for AA) to handle this case, and ensure consistent results. --- llvm/lib/Analysis/BasicAliasAnalysis.cpp | 77 +++++++++++--------------------- llvm/test/Analysis/BasicAA/phi-aa.ll | 4 +- 2 files changed, 27 insertions(+), 54 deletions(-) diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp index b7af511..ac3a327 100644 --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -1102,69 +1102,42 @@ AliasResult BasicAAResult::aliasGEP( // cannot alias. if (isGEPBaseAtNegativeOffset(GEP1, DecompGEP1, DecompGEP2, V2Size)) return NoAlias; - // If we have two gep instructions with must-alias or not-alias'ing base - // pointers, figure out if the indexes to the GEP tell us anything about the - // derived pointer. + if (const GEPOperator *GEP2 = dyn_cast(V2)) { // Check for the GEP base being at a negative offset, this time in the other // direction. if (isGEPBaseAtNegativeOffset(GEP2, DecompGEP2, DecompGEP1, V1Size)) return NoAlias; - - // Subtract the GEP2 pointer from the GEP1 pointer to find out their - // symbolic difference. - DecompGEP1.Offset -= DecompGEP2.Offset; - GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices); - - // For GEPs with identical offsets, we can preserve the size and AAInfo - // when performing the alias check on the underlying objects. - if (DecompGEP1.Offset == 0 && DecompGEP1.VarIndices.empty()) - return getBestAAResults().alias( - MemoryLocation(UnderlyingV1, V1Size, V1AAInfo), - MemoryLocation(UnderlyingV2, V2Size, V2AAInfo), AAQI); - - // Do the base pointers alias? - AliasResult BaseAlias = getBestAAResults().alias( - MemoryLocation::getBeforeOrAfter(UnderlyingV1), - MemoryLocation::getBeforeOrAfter(UnderlyingV2), AAQI); - - // If we get a No or May, then return it immediately, no amount of analysis - // will improve this situation. - if (BaseAlias != MustAlias) { - assert(BaseAlias == NoAlias || BaseAlias == MayAlias); - return BaseAlias; - } } else { - // Check to see if these two pointers are related by the getelementptr - // instruction. If one pointer is a GEP with a non-zero index of the other - // pointer, we know they cannot alias. - - // If both accesses are unknown size, we can't do anything useful here. + // TODO: This limitation exists for compile-time reasons. Relax it if we + // can avoid exponential pathological cases. if (!V1Size.hasValue() && !V2Size.hasValue()) return MayAlias; - - AliasResult R = getBestAAResults().alias( - MemoryLocation::getBeforeOrAfter(UnderlyingV1), - MemoryLocation(V2, V2Size, V2AAInfo), AAQI); - if (R != MustAlias) { - // If V2 may alias GEP base pointer, conservatively returns MayAlias. - // If V2 is known not to alias GEP base pointer, then the two values - // cannot alias per GEP semantics: "Any memory access must be done through - // a pointer value associated with an address range of the memory access, - // otherwise the behavior is undefined.". - assert(R == NoAlias || R == MayAlias); - return R; - } } - // In the two GEP Case, if there is no difference in the offsets of the - // computed pointers, the resultant pointers are a must alias. This - // happens when we have two lexically identical GEP's (for example). - // - // In the other case, if we have getelementptr , 0, 0, 0, 0, ... and V2 - // must aliases the GEP, the end result is a must alias also. + // Subtract the GEP2 pointer from the GEP1 pointer to find out their + // symbolic difference. + DecompGEP1.Offset -= DecompGEP2.Offset; + GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices); + + // For GEPs with identical offsets, we can preserve the size and AAInfo + // when performing the alias check on the underlying objects. if (DecompGEP1.Offset == 0 && DecompGEP1.VarIndices.empty()) - return MustAlias; + return getBestAAResults().alias( + MemoryLocation(UnderlyingV1, V1Size, V1AAInfo), + MemoryLocation(UnderlyingV2, V2Size, V2AAInfo), AAQI); + + // Do the base pointers alias? + AliasResult BaseAlias = getBestAAResults().alias( + MemoryLocation::getBeforeOrAfter(UnderlyingV1), + MemoryLocation::getBeforeOrAfter(UnderlyingV2), AAQI); + + // If we get a No or May, then return it immediately, no amount of analysis + // will improve this situation. + if (BaseAlias != MustAlias) { + assert(BaseAlias == NoAlias || BaseAlias == MayAlias); + return BaseAlias; + } // If there is a constant difference between the pointers, but the difference // is less than the size of the associated memory object, then we know diff --git a/llvm/test/Analysis/BasicAA/phi-aa.ll b/llvm/test/Analysis/BasicAA/phi-aa.ll index 5ec8503..39a3180 100644 --- a/llvm/test/Analysis/BasicAA/phi-aa.ll +++ b/llvm/test/Analysis/BasicAA/phi-aa.ll @@ -200,8 +200,8 @@ for.body: ; preds = %for.body, %entry ; CHECK-LABEL: single_arg_phi ; CHECK: MayAlias: i32* %ptr, i32* %ptr.next -; CHECK: MayAlias: i32* %ptr.next, i32* %ptr.next.phi -; TODO: Both of these could be MustAlias. +; CHECK: MustAlias: i32* %ptr.next, i32* %ptr.next.phi +; TODO: The first one could be MustAlias as well. define void @single_arg_phi(i32* %ptr.base) { entry: br label %loop -- 2.7.4