diff --git a/llvm/include/llvm/Analysis/ValueTracking.h b/llvm/include/llvm/Analysis/ValueTracking.h --- a/llvm/include/llvm/Analysis/ValueTracking.h +++ b/llvm/include/llvm/Analysis/ValueTracking.h @@ -245,6 +245,12 @@ DL); } + /// Try to peak through a IntToPtr instruction to find a corresponding + /// PtrToInt instruction which can be used as underlying object, allowing + /// arithmetic instructions that do not change the underlying object in + /// between. + Value *GetUnderlyingObjectFromInt2Ptr(const Value *V, const DataLayout &DL); + /// Returns true if the GEP is based on a pointer to a string (array of // \p CharSize integers) and is indexing into this string. bool isGEPBasedOnPointerToString(const GEPOperator *GEP, diff --git a/llvm/include/llvm/IR/DataLayout.h b/llvm/include/llvm/IR/DataLayout.h --- a/llvm/include/llvm/IR/DataLayout.h +++ b/llvm/include/llvm/IR/DataLayout.h @@ -323,6 +323,8 @@ /// Layout pointer alignment unsigned getPointerABIAlignment(unsigned AS) const; + unsigned getMinPointerABIAlignment() const; + /// Return target's alignment for stack-based pointers /// FIXME: The defaults need to be removed once all of /// the backends/clients are updated. diff --git a/llvm/include/llvm/IR/PatternMatch.h b/llvm/include/llvm/IR/PatternMatch.h --- a/llvm/include/llvm/IR/PatternMatch.h +++ b/llvm/include/llvm/IR/PatternMatch.h @@ -1156,6 +1156,12 @@ return CastClass_match(Op); } +/// Matches IntToPtr +template +inline CastClass_match m_IntToPtr(const OpTy &Op) { + return CastClass_match(Op); +} + /// Matches Trunc. template inline CastClass_match m_Trunc(const OpTy &Op) { diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -25,9 +25,9 @@ #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/MemoryLocation.h" +#include "llvm/Analysis/PhiValues.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueTracking.h" -#include "llvm/Analysis/PhiValues.h" #include "llvm/IR/Argument.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/Constant.h" @@ -46,6 +46,7 @@ #include "llvm/IR/Intrinsics.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/Operator.h" +#include "llvm/IR/PatternMatch.h" #include "llvm/IR/Type.h" #include "llvm/IR/User.h" #include "llvm/IR/Value.h" @@ -62,6 +63,7 @@ #define DEBUG_TYPE "basicaa" using namespace llvm; +using namespace PatternMatch; /// Enable analysis of recursive PHI nodes. static cl::opt EnableRecPhiAnalysis("basicaa-recphi", cl::Hidden, @@ -469,6 +471,10 @@ continue; } + if (auto *Ptr = GetUnderlyingObjectFromInt2Ptr(Op, DL)) { + V = Ptr; + continue; + } const GEPOperator *GEPOp = dyn_cast(Op); if (!GEPOp) { if (const auto *Call = dyn_cast(V)) { diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -3461,6 +3461,44 @@ return Ptr; } +Value *llvm::GetUnderlyingObjectFromInt2Ptr(const Value *V, + const DataLayout &DL) { + Value *Ptr; + ConstantInt *CI; + // Check if the inttoptr and ptrtoint are used to strip away insignificant + // bits of the pointer. If that's the case, the target of the starting + // pointer remains unchanged. + if (match(V, + m_IntToPtr(m_And(m_PtrToInt(m_Value(Ptr)), m_ConstantInt(CI))))) { + // Check that + const Instruction *Int2Ptr = cast(V); + const Instruction *And = cast(Int2Ptr->getOperand(0)); + const Instruction *Ptr2Int = cast(And->getOperand(0)); + // 1) there are no interfering instructions between the ptrtoint,and, + // inttoptr + // chain. This is overly conservative and we can relax it to allow + // any non-throwing,etc instructions in between. + if (std::next(Ptr2Int->getIterator()) != And->getIterator() || + std::next(And->getIterator()) != Int2Ptr->getIterator()) + return nullptr; + // 2) the ptrtoint and the and have a single user, to ensure the original + // ptrtoint does not contribute to multiple accesses. + if (!Ptr2Int->hasOneUse() || !And->hasOneUse()) + return nullptr; + + uint64_t AllOnes = ~((uint64_t)0); + uint64_t MeaningfulPtrBits = + (AllOnes >> (64 - DL.getMaxPointerSizeInBits())) & + (AllOnes << Log2_64(DL.getMinPointerABIAlignment())); + if ((CI->getValue().getZExtValue() & MeaningfulPtrBits) == + MeaningfulPtrBits) { + return Ptr; + } + } + + return nullptr; +} + bool llvm::isGEPBasedOnPointerToString(const GEPOperator *GEP, unsigned CharSize) { // Make sure the GEP has exactly three arguments. @@ -3748,7 +3786,7 @@ continue; } } - + // // See if InstructionSimplify knows any relevant tricks. if (Instruction *I = dyn_cast(V)) // TODO: Acquire a DominatorTree and AssumptionCache and use them. @@ -3757,6 +3795,10 @@ continue; } + if (auto *Ptr = GetUnderlyingObjectFromInt2Ptr(V, DL)) { + V = Ptr; + continue; + } return V; } assert(V->getType()->isPointerTy() && "Unexpected operand type!"); diff --git a/llvm/lib/IR/DataLayout.cpp b/llvm/lib/IR/DataLayout.cpp --- a/llvm/lib/IR/DataLayout.cpp +++ b/llvm/lib/IR/DataLayout.cpp @@ -616,6 +616,14 @@ return I->ABIAlign; } +unsigned DataLayout::getMinPointerABIAlignment() const { + unsigned MaxABIAlign = std::numeric_limits::max(); + for (auto &P : Pointers) + MaxABIAlign = std::min(MaxABIAlign, P.ABIAlign); + + return MaxABIAlign; +} + unsigned DataLayout::getPointerPrefAlignment(unsigned AS) const { PointersTy::const_iterator I = findPointerLowerBound(AS); if (I == Pointers.end() || I->AddressSpace != AS) { diff --git a/llvm/test/Analysis/BasicAA/strip-nonsignificant-ptr-bits.ll b/llvm/test/Analysis/BasicAA/strip-nonsignificant-ptr-bits.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/BasicAA/strip-nonsignificant-ptr-bits.ll @@ -0,0 +1,159 @@ +; RUN: opt -basicaa -aa-eval -print-no-aliases -disable-output %s 2>&1 | FileCheck %s + +; We have 2 pointer address spaces with different pointer sizes and ABI alignments, +; to make sure we pick the maximum pointer size and minimum ABI alignment for +; multiple address spaces. +target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128-p0:48:64:128-p1:56:64:64" + +%struct.zot = type <{ [20 x i64] }> + +; inttoptr(and(ptrtoint(X), 72057594037927928) roundtrip strips away the most +; significant 8 bits and the least significant 3 bits of X. Those bits are +; not used, the pointer value remains unchanged and we can use %addr as +; underlying object ( according to target pointer size (56bit) and ABI alignment +; requirement (3bit). +; CHECK-LABEL: Function: test1: 5 pointers, 1 call sites +; CHECK-NEXT: NoAlias: %struct.zot** %loc, i64* %offset.addr +; CHECK-NEXT: NoAlias: %struct.zot* %addr, %struct.zot** %loc +; CHECK-NEXT: NoAlias: %struct.zot* %addr.ptr, %struct.zot** %loc +; CHECK-NEXT: NoAlias: %struct.zot** %loc, i64* %gep +define void @test1(i64* %offset.addr) { +entry: + %loc = alloca %struct.zot*, align 8 + call void @init(i64 0, %struct.zot** nocapture nonnull dereferenceable(8) %loc) + %addr = load %struct.zot*, %struct.zot** %loc, align 8 + %addr.int = ptrtoint %struct.zot* %addr to i64 + %addr.strip = and i64 %addr.int, 72057594037927928 + %addr.ptr = inttoptr i64 %addr.strip to %struct.zot* + %offset = load i64, i64* %offset.addr, align 8 + %gep = getelementptr inbounds %struct.zot, %struct.zot* %addr.ptr, i64 0, i32 0, i64 %offset + store i64 1, i64* %gep, align 8 + ret void +} + + +; inttoptr(and(ptrtoint(X), 72057594037927920) roundtrip strips away the 4 least +; significant bits and changes the pointer value. We cannot use %addr as underlying object. +; CHECK-NEXT: Function: test2: 5 pointers, 1 call sites +; CHECK-NEXT: NoAlias: %struct.zot** %loc, i64* %offset.addr +; CHECK-NEXT: NoAlias: %struct.zot* %addr, %struct.zot** %loc +; CHECK-NEXT: NoAlias: %struct.zot* %addr.ptr, %struct.zot** %loc +define void @test2(i64* %offset.addr) { +entry: + %loc = alloca %struct.zot*, align 8 + call void @init(i64 0, %struct.zot** nocapture nonnull dereferenceable(8) %loc) + %addr = load %struct.zot*, %struct.zot** %loc, align 8 + %addr.int = ptrtoint %struct.zot* %addr to i64 + %addr.strip = and i64 %addr.int, 72057594037927920 + %addr.ptr = inttoptr i64 %addr.strip to %struct.zot* + %offset = load i64, i64* %offset.addr, align 8 + %gep = getelementptr inbounds %struct.zot, %struct.zot* %addr.ptr, i64 0, i32 0, i64 %offset + store i64 1, i64* %gep, align 8 + ret void +} + +; inttoptr(and(ptrtoint(X), 36028797018963960) roundtrip strips away the 9 most +; significant bits and changes the pointer value. We cannot use %addr as underlying object. +; CHECK-NEXT: Function: test3: 5 pointers, 1 call sites +; CHECK-NEXT: NoAlias: %struct.zot** %loc, i64* %offset.addr +; CHECK-NEXT: NoAlias: %struct.zot* %addr, %struct.zot** %loc +; CHECK-NEXT: NoAlias: %struct.zot* %addr.ptr, %struct.zot** %loc +define void @test3(i64* %offset.addr) { +entry: + %loc = alloca %struct.zot*, align 8 + call void @init(i64 0, %struct.zot** nocapture nonnull dereferenceable(8) %loc) + %addr = load %struct.zot*, %struct.zot** %loc, align 8 + %addr.int = ptrtoint %struct.zot* %addr to i64 + %addr.strip = and i64 %addr.int, 36028797018963960 + %addr.ptr = inttoptr i64 %addr.strip to %struct.zot* + %offset = load i64, i64* %offset.addr, align 8 + %gep = getelementptr inbounds %struct.zot, %struct.zot* %addr.ptr, i64 0, i32 0, i64 %offset + store i64 1, i64* %gep, align 8 + ret void +} + +declare void @use(i64) + +; ptrtoint has multiple users, do not use %addr as underlying object +; CHECK-NEXT: Function: test_multiuse1: 5 pointers, 2 call sites +; CHECK-NEXT: NoAlias: %struct.zot** %loc, i64* %offset.addr +; CHECK-NEXT: NoAlias: %struct.zot* %addr, %struct.zot** %loc +; CHECK-NEXT: NoAlias: %struct.zot* %addr.ptr, %struct.zot** %loc +define void @test_multiuse1(i64* %offset.addr) { +entry: + %loc = alloca %struct.zot*, align 8 + call void @init(i64 0, %struct.zot** nocapture nonnull dereferenceable(8) %loc) + %addr = load %struct.zot*, %struct.zot** %loc, align 8 + %addr.int = ptrtoint %struct.zot* %addr to i64 + %addr.strip = and i64 %addr.int, 72057594037927928 + %addr.ptr = inttoptr i64 %addr.strip to %struct.zot* + %offset = load i64, i64* %offset.addr, align 8 + %gep = getelementptr inbounds %struct.zot, %struct.zot* %addr.ptr, i64 0, i32 0, i64 %offset + call void @use(i64 %addr.int) + store i64 1, i64* %gep, align 8 + ret void +} + +; and has multiple users, do not use %addr as underlying object +; CHECK-NEXT: Function: test_multiuse2: 5 pointers, 2 call sites +; CHECK-NEXT: NoAlias: %struct.zot** %loc, i64* %offset.addr +; CHECK-NEXT: NoAlias: %struct.zot* %addr, %struct.zot** %loc +; CHECK-NEXT: NoAlias: %struct.zot* %addr.ptr, %struct.zot** %loc +define void @test_multiuse2(i64* %offset.addr) { +entry: + %loc = alloca %struct.zot*, align 8 + call void @init(i64 0, %struct.zot** nocapture nonnull dereferenceable(8) %loc) + %addr = load %struct.zot*, %struct.zot** %loc, align 8 + %addr.int = ptrtoint %struct.zot* %addr to i64 + %addr.strip = and i64 %addr.int, 72057594037927928 + %addr.ptr = inttoptr i64 %addr.strip to %struct.zot* + %offset = load i64, i64* %offset.addr, align 8 + %gep = getelementptr inbounds %struct.zot, %struct.zot* %addr.ptr, i64 0, i32 0, i64 %offset + call void @use(i64 %addr.strip) + store i64 1, i64* %gep, align 8 + ret void +} + +declare void @foo() + +; Instruction between ptrtoint and AND. +; CHECK-NEXT: Function: test_inst_between1: 5 pointers, 2 call sites +; CHECK-NEXT: NoAlias: %struct.zot** %loc, i64* %offset.addr +; CHECK-NEXT: NoAlias: %struct.zot* %addr, %struct.zot** %loc +; CHECK-NEXT: NoAlias: %struct.zot* %addr.ptr, %struct.zot** %loc +define void @test_inst_between1(i64* %offset.addr) { +entry: + %loc = alloca %struct.zot*, align 8 + call void @init(i64 0, %struct.zot** nocapture nonnull dereferenceable(8) %loc) + %addr = load %struct.zot*, %struct.zot** %loc, align 8 + %addr.int = ptrtoint %struct.zot* %addr to i64 + call void @foo() + %addr.strip = and i64 %addr.int, 72057594037927928 + %addr.ptr = inttoptr i64 %addr.strip to %struct.zot* + %offset = load i64, i64* %offset.addr, align 8 + %gep = getelementptr inbounds %struct.zot, %struct.zot* %addr.ptr, i64 0, i32 0, i64 %offset + store i64 1, i64* %gep, align 8 + ret void +} + +; Instruction between AND and inttoptr. +; CHECK-NEXT: Function: test_inst_between2: 5 pointers, 2 call sites +; CHECK-NEXT: NoAlias: %struct.zot** %loc, i64* %offset.addr +; CHECK-NEXT: NoAlias: %struct.zot* %addr, %struct.zot** %loc +; CHECK-NEXT: NoAlias: %struct.zot* %addr.ptr, %struct.zot** %loc +define void @test_inst_between2(i64* %offset.addr) { +entry: + %loc = alloca %struct.zot*, align 8 + call void @init(i64 0, %struct.zot** nocapture nonnull dereferenceable(8) %loc) + %addr = load %struct.zot*, %struct.zot** %loc, align 8 + %addr.int = ptrtoint %struct.zot* %addr to i64 + %addr.strip = and i64 %addr.int, 72057594037927928 + call void @foo() + %addr.ptr = inttoptr i64 %addr.strip to %struct.zot* + %offset = load i64, i64* %offset.addr, align 8 + %gep = getelementptr inbounds %struct.zot, %struct.zot* %addr.ptr, i64 0, i32 0, i64 %offset + store i64 1, i64* %gep, align 8 + ret void +} + +declare void @init(i64, %struct.zot** nocapture dereferenceable(8))