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,23 @@ continue; } + 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(Op, + m_IntToPtr(m_And(m_PtrToInt(m_Value(Ptr)), m_ConstantInt(CI))))) { + uint64_t AllOnes = ~((uint64_t)0); + uint64_t MeaningfulPtrBits = + (AllOnes >> (64 - DL.getMaxPointerSizeInBits())) & + (AllOnes << Log2_64(DL.getMinPointerABIAlignment())); + if ((CI->getValue().getZExtValue() & MeaningfulPtrBits) == + MeaningfulPtrBits) { + 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 @@ -3748,6 +3748,23 @@ continue; } } + 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))))) { + uint64_t AllOnes = ~((uint64_t)0); + uint64_t MeaningfulPtrBits = + (AllOnes >> (64 - DL.getMaxPointerSizeInBits())) & + (AllOnes << Log2_64(DL.getMinPointerABIAlignment())); + if ((CI->getValue().getZExtValue() & MeaningfulPtrBits) == + MeaningfulPtrBits) { + V = Ptr; + continue; + } + } // See if InstructionSimplify knows any relevant tricks. if (Instruction *I = dyn_cast(V)) 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,91 @@ +; 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). +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) + br label %loop.body + +loop.body: ; preds = %loop.body, %entry + %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.body ] + %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, !range !0 + %gep = getelementptr inbounds %struct.zot, %struct.zot* %addr.ptr, i64 0, i32 0, i64 %offset + store i64 1, i64* %gep, align 8 + %iv.next = add nuw nsw i64 %iv, 1 + %cond = icmp eq i64 %iv, 40000 + br i1 %cond, label %bb28, label %loop.body + +bb28: ; preds = %loop.body + 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. +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) + br label %loop.body + +loop.body: ; preds = %loop.body, %entry + %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.body ] + %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, !range !0 + %gep = getelementptr inbounds %struct.zot, %struct.zot* %addr.ptr, i64 0, i32 0, i64 %offset + store i64 1, i64* %gep, align 8 + %iv.next = add nuw nsw i64 %iv, 1 + %cond = icmp eq i64 %iv, 40000 + br i1 %cond, label %bb28, label %loop.body + +bb28: ; preds = %loop.body + 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. +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) + br label %loop.body + +loop.body: ; preds = %loop.body, %entry + %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.body ] + %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, !range !0 + %gep = getelementptr inbounds %struct.zot, %struct.zot* %addr.ptr, i64 0, i32 0, i64 %offset + store i64 1, i64* %gep, align 8 + %iv.next = add nuw nsw i64 %iv, 1 + %cond = icmp eq i64 %iv, 40000 + br i1 %cond, label %bb28, label %loop.body + +bb28: ; preds = %loop.body + ret void +} + +declare void @init(i64, %struct.zot** nocapture dereferenceable(8)) + +!0 = !{i64 0, i64 9223372036854775807}