Index: llvm/trunk/include/llvm/Analysis/AliasSetTracker.h =================================================================== --- llvm/trunk/include/llvm/Analysis/AliasSetTracker.h +++ llvm/trunk/include/llvm/Analysis/AliasSetTracker.h @@ -52,9 +52,13 @@ PointerRec **PrevInList = nullptr; PointerRec *NextInList = nullptr; AliasSet *AS = nullptr; - LocationSize Size = 0; + LocationSize Size = LocationSize::mapEmpty(); AAMDNodes AAInfo; + // Whether the size for this record has been set at all. This makes no + // guarantees about the size being known. + bool isSizeSet() const { return Size != LocationSize::mapEmpty(); } + public: PointerRec(Value *V) : Val(V), AAInfo(DenseMapInfo::getEmptyKey()) {} @@ -71,9 +75,10 @@ bool updateSizeAndAAInfo(LocationSize NewSize, const AAMDNodes &NewAAInfo) { bool SizeChanged = false; - if (NewSize > Size) { - Size = NewSize; - SizeChanged = true; + if (NewSize != Size) { + LocationSize OldSize = Size; + Size = isSizeSet() ? Size.unionWith(NewSize) : NewSize; + SizeChanged = OldSize != Size; } if (AAInfo == DenseMapInfo::getEmptyKey()) @@ -91,7 +96,10 @@ return SizeChanged; } - LocationSize getSize() const { return Size; } + LocationSize getSize() const { + assert(isSizeSet() && "Getting an unset size!"); + return Size; + } /// Return the AAInfo, or null if there is no information or conflicting /// information. Index: llvm/trunk/include/llvm/Analysis/MemoryLocation.h =================================================================== --- llvm/trunk/include/llvm/Analysis/MemoryLocation.h +++ llvm/trunk/include/llvm/Analysis/MemoryLocation.h @@ -34,18 +34,39 @@ class TargetLibraryInfo; // Represents the size of a MemoryLocation. Logically, it's an -// Optional. +// Optional that also carries a bit to represent whether the integer +// it contains, N, is 'precise'. Precise, in this context, means that we know +// that the area of storage referenced by the given MemoryLocation must be +// precisely N bytes. An imprecise value is formed as the union of two or more +// precise values, and can conservatively represent all of the values unioned +// into it. Importantly, imprecise values are an *upper-bound* on the size of a +// MemoryLocation. // -// We plan to use it for more soon, but we're trying to transition to this brave -// new world in small, easily-reviewable pieces; please see D44748. +// Concretely, a precise MemoryLocation is (%p, 4) in +// store i32 0, i32* %p +// +// Since we know that %p must be at least 4 bytes large at this point. +// Otherwise, we have UB. An example of an imprecise MemoryLocation is (%p, 4) +// at the memcpy in +// +// %n = select i1 %foo, i64 1, i64 4 +// call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %baz, i64 %n, i32 1, +// i1 false) +// +// ...Since we'll copy *up to* 4 bytes into %p, but we can't guarantee that +// we'll ever actually do so. +// +// If asked to represent a pathologically large value, this will degrade to +// None. class LocationSize { enum : uint64_t { Unknown = ~uint64_t(0), + ImpreciseBit = uint64_t(1) << 63, MapEmpty = Unknown - 1, MapTombstone = Unknown - 2, // The maximum value we can represent without falling back to 'unknown'. - MaxValue = MapTombstone - 1, + MaxValue = (MapTombstone - 1) & ~ImpreciseBit, }; uint64_t Value; @@ -56,11 +77,28 @@ constexpr LocationSize(uint64_t Raw, DirectConstruction): Value(Raw) {} + static_assert(Unknown & ImpreciseBit, "Unknown is imprecise by definition."); public: + // FIXME: Migrate all users to construct via either `precise` or `upperBound`, + // to make it more obvious at the callsite the kind of size that they're + // providing. + // + // Since the overwhelming majority of users of this provide precise values, + // this assumes the provided value is precise. constexpr LocationSize(uint64_t Raw) : Value(Raw > MaxValue ? Unknown : Raw) {} static LocationSize precise(uint64_t Value) { return LocationSize(Value); } + + static LocationSize upperBound(uint64_t Value) { + // You can't go lower than 0, so give a precise result. + if (LLVM_UNLIKELY(Value == 0)) + return precise(0); + if (LLVM_UNLIKELY(Value > MaxValue)) + return unknown(); + return LocationSize(Value | ImpreciseBit, Direct); + } + constexpr static LocationSize unknown() { return LocationSize(Unknown, Direct); } @@ -73,10 +111,28 @@ return LocationSize(MapEmpty, Direct); } + // Returns a LocationSize that can correctly represent either `*this` or + // `Other`. + LocationSize unionWith(LocationSize Other) const { + if (Other == *this) + return *this; + + if (!hasValue() || !Other.hasValue()) + return unknown(); + + return upperBound(std::max(getValue(), Other.getValue())); + } + bool hasValue() const { return Value != Unknown; } uint64_t getValue() const { assert(hasValue() && "Getting value from an unknown LocationSize!"); - return Value; + return Value & ~ImpreciseBit; + } + + // Returns whether or not this value is precise. Note that if a value is + // precise, it's guaranteed to not be `unknown()`. + bool isPrecise() const { + return (Value & ImpreciseBit) == 0; } bool operator==(const LocationSize &Other) const { @@ -87,21 +143,16 @@ return !(*this == Other); } + // Ordering operators are not provided, since it's unclear if there's only one + // reasonable way to compare: + // - values that don't exist against values that do, and + // - precise values to imprecise values + void print(raw_ostream &OS) const; // Returns an opaque value that represents this LocationSize. Cannot be // reliably converted back into a LocationSize. uint64_t toRaw() const { return Value; } - - // NOTE: These comparison operators will go away with D44748. Please don't - // rely on them. - bool operator<(const LocationSize &Other) const { - return Value < Other.Value; - } - - bool operator>(const LocationSize &Other) const { - return Other < *this; - } }; inline raw_ostream &operator<<(raw_ostream &OS, LocationSize Size) { Index: llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp +++ llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp @@ -1715,12 +1715,10 @@ // If the size of one access is larger than the entire object on the other // side, then we know such behavior is undefined and can assume no alias. bool NullIsValidLocation = NullPointerIsDefined(&F); - if ((V1Size != MemoryLocation::UnknownSize && - isObjectSmallerThan(O2, V1Size.getValue(), DL, TLI, - NullIsValidLocation)) || - (V2Size != MemoryLocation::UnknownSize && - isObjectSmallerThan(O1, V2Size.getValue(), DL, TLI, - NullIsValidLocation))) + if ((V1Size.isPrecise() && isObjectSmallerThan(O2, V1Size.getValue(), DL, TLI, + NullIsValidLocation)) || + (V2Size.isPrecise() && isObjectSmallerThan(O1, V2Size.getValue(), DL, TLI, + NullIsValidLocation))) return NoAlias; // Check the cache before climbing up use-def chains. This also terminates @@ -1778,8 +1776,7 @@ // If both pointers are pointing into the same object and one of them // accesses the entire object, then the accesses must overlap in some way. if (O1 == O2) - if (V1Size != MemoryLocation::UnknownSize && - V2Size != MemoryLocation::UnknownSize && + if (V1Size.isPrecise() && V2Size.isPrecise() && (isObjectSize(O1, V1Size.getValue(), DL, TLI, NullIsValidLocation) || isObjectSize(O2, V2Size.getValue(), DL, TLI, NullIsValidLocation))) return AliasCache[Locs] = PartialAlias; Index: llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp +++ llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -1113,21 +1113,36 @@ // If we already have a cache entry for this CacheKey, we may need to do some // work to reconcile the cache entry and the current query. if (!Pair.second) { - if (CacheInfo->Size < Loc.Size) { - // The query's Size is greater than the cached one. Throw out the - // cached data and proceed with the query at the greater size. - CacheInfo->Pair = BBSkipFirstBlockPair(); - CacheInfo->Size = Loc.Size; - for (auto &Entry : CacheInfo->NonLocalDeps) - if (Instruction *Inst = Entry.getResult().getInst()) - RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey); - CacheInfo->NonLocalDeps.clear(); - } else if (CacheInfo->Size > Loc.Size) { - // This query's Size is less than the cached one. Conservatively restart - // the query using the greater size. - return getNonLocalPointerDepFromBB( - QueryInst, Pointer, Loc.getWithNewSize(CacheInfo->Size), isLoad, - StartBB, Result, Visited, SkipFirstBlock); + if (CacheInfo->Size != Loc.Size) { + bool ThrowOutEverything; + if (CacheInfo->Size.hasValue() && Loc.Size.hasValue()) { + // FIXME: We may be able to do better in the face of results with mixed + // precision. We don't appear to get them in practice, though, so just + // be conservative. + ThrowOutEverything = + CacheInfo->Size.isPrecise() != Loc.Size.isPrecise() || + CacheInfo->Size.getValue() < Loc.Size.getValue(); + } else { + // For our purposes, unknown size > all others. + ThrowOutEverything = !Loc.Size.hasValue(); + } + + if (ThrowOutEverything) { + // The query's Size is greater than the cached one. Throw out the + // cached data and proceed with the query at the greater size. + CacheInfo->Pair = BBSkipFirstBlockPair(); + CacheInfo->Size = Loc.Size; + for (auto &Entry : CacheInfo->NonLocalDeps) + if (Instruction *Inst = Entry.getResult().getInst()) + RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey); + CacheInfo->NonLocalDeps.clear(); + } else { + // This query's Size is less than the cached one. Conservatively restart + // the query using the greater size. + return getNonLocalPointerDepFromBB( + QueryInst, Pointer, Loc.getWithNewSize(CacheInfo->Size), isLoad, + StartBB, Result, Visited, SkipFirstBlock); + } } // If the query's AATags are inconsistent with the cached one, Index: llvm/trunk/lib/Analysis/MemoryLocation.cpp =================================================================== --- llvm/trunk/lib/Analysis/MemoryLocation.cpp +++ llvm/trunk/lib/Analysis/MemoryLocation.cpp @@ -26,8 +26,10 @@ OS << "mapEmpty"; else if (*this == mapTombstone()) OS << "mapTombstone"; - else + else if (isPrecise()) OS << "precise(" << getValue() << ')'; + else + OS << "upperBound(" << getValue() << ')'; } MemoryLocation MemoryLocation::get(const LoadInst *LI) { Index: llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -349,9 +349,9 @@ InstOverlapIntervalsTy &IOL, AliasAnalysis &AA, const Function *F) { - // If we don't know the sizes of either access, then we can't do a comparison. - if (Later.Size == MemoryLocation::UnknownSize || - Earlier.Size == MemoryLocation::UnknownSize) + // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll + // get imprecise values here, though (except for unknown sizes). + if (!Later.Size.isPrecise() || !Earlier.Size.isPrecise()) return OW_Unknown; const uint64_t LaterSize = Later.Size.getValue(); Index: llvm/trunk/test/Transforms/LICM/pr36228.ll =================================================================== --- llvm/trunk/test/Transforms/LICM/pr36228.ll +++ llvm/trunk/test/Transforms/LICM/pr36228.ll @@ -0,0 +1,40 @@ +; RUN: opt -S -licm -o - %s | FileCheck %s +; +; Be sure that we don't hoist loads incorrectly if a loop has conditional UB. +; See PR36228. + +declare void @check(i8) +declare void @llvm.memcpy.p0i8.p0i8.i64(i8*, i8*, i64, i32, i1) + +; CHECK-LABEL: define void @buggy +define void @buggy(i8* %src, i1* %kOne) { +entry: + %dst = alloca [1 x i8], align 1 + %0 = getelementptr inbounds [1 x i8], [1 x i8]* %dst, i64 0, i64 0 + store i8 42, i8* %0, align 1 + %src16 = bitcast i8* %src to i16* + %srcval = load i16, i16* %src16 + br label %while.cond + +while.cond: ; preds = %if.end, %entry + %dp.0 = phi i8* [ %0, %entry ], [ %dp.1, %if.end ] + %1 = load volatile i1, i1* %kOne, align 4 + br i1 %1, label %if.else, label %if.then + +if.then: ; preds = %while.cond + store i8 9, i8* %dp.0, align 1 + br label %if.end + +if.else: ; preds = %while.cond + call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dp.0, i8* %src, i64 2, i32 1, i1 false) + %dp.new = getelementptr inbounds i8, i8* %dp.0, i64 1 + br label %if.end + +if.end: ; preds = %if.else, %if.then + %dp.1 = phi i8* [ %dp.0, %if.then ], [ %dp.new, %if.else ] + ; CHECK: %2 = load i8, i8* %0 + %2 = load i8, i8* %0, align 1 + ; CHECK-NEXT: call void @check(i8 %2) + call void @check(i8 %2) + br label %while.cond +} Index: llvm/trunk/unittests/Analysis/BasicAliasAnalysisTest.cpp =================================================================== --- llvm/trunk/unittests/Analysis/BasicAliasAnalysisTest.cpp +++ llvm/trunk/unittests/Analysis/BasicAliasAnalysisTest.cpp @@ -0,0 +1,124 @@ +//===- BasicAliasAnalysisTest.cpp - Unit tests for BasicAA ----------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Targeted tests that are hard/convoluted to make happen with just `opt`. +// + +#include "llvm/Analysis/BasicAliasAnalysis.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/AsmParser/Parser.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Module.h" +#include "llvm/Support/SourceMgr.h" +#include "gtest/gtest.h" + +using namespace llvm; + +// FIXME: This is duplicated between this file and MemorySSATest. Refactor. +const static char DLString[] = "e-i64:64-f80:128-n8:16:32:64-S128"; + +/// There's a lot of common setup between these tests. This fixture helps reduce +/// that. Tests should mock up a function, store it in F, and then call +/// setupAnalyses(). +class BasicAATest : public testing::Test { +protected: + // N.B. Many of these members depend on each other (e.g. the Module depends on + // the Context, etc.). So, order matters here (and in TestAnalyses). + LLVMContext C; + Module M; + IRBuilder<> B; + DataLayout DL; + TargetLibraryInfoImpl TLII; + TargetLibraryInfo TLI; + Function *F; + + // Things that we need to build after the function is created. + struct TestAnalyses { + DominatorTree DT; + AssumptionCache AC; + BasicAAResult BAA; + + TestAnalyses(BasicAATest &Test) + : DT(*Test.F), AC(*Test.F), BAA(Test.DL, *Test.F, Test.TLI, AC, &DT) {} + }; + + llvm::Optional Analyses; + + BasicAAResult &setupAnalyses() { + assert(F); + Analyses.emplace(*this); + return Analyses->BAA; + } + +public: + BasicAATest() + : M("BasicAATest", C), B(C), DL(DLString), TLI(TLII), F(nullptr) {} +}; + +// Check that a function arg can't trivially alias a global when we're accessing +// >sizeof(global) bytes through that arg, unless the access size is just an +// upper-bound. +TEST_F(BasicAATest, AliasInstWithObjectOfImpreciseSize) { + F = Function::Create( + FunctionType::get(B.getVoidTy(), {B.getInt32Ty()->getPointerTo()}, false), + GlobalValue::ExternalLinkage, "F", &M); + + BasicBlock *Entry(BasicBlock::Create(C, "", F)); + B.SetInsertPoint(Entry); + + Value *IncomingI32Ptr = F->arg_begin(); + + auto *GlobalPtr = + cast(M.getOrInsertGlobal("some_global", B.getInt8Ty())); + + // Without sufficiently restricted linkage/an init, some of the object size + // checking bits get more conservative. + GlobalPtr->setLinkage(GlobalValue::LinkageTypes::InternalLinkage); + GlobalPtr->setInitializer(B.getInt8(0)); + + BasicAAResult &BasicAA = setupAnalyses(); + ASSERT_EQ( + BasicAA.alias(MemoryLocation(IncomingI32Ptr, LocationSize::precise(4)), + MemoryLocation(GlobalPtr, LocationSize::precise(1))), + AliasResult::NoAlias); + + ASSERT_EQ( + BasicAA.alias(MemoryLocation(IncomingI32Ptr, LocationSize::upperBound(4)), + MemoryLocation(GlobalPtr, LocationSize::precise(1))), + AliasResult::MayAlias); +} + +// Check that we fall back to MayAlias if we see an access of an entire object +// that's just an upper-bound. +TEST_F(BasicAATest, AliasInstWithFullObjectOfImpreciseSize) { + F = Function::Create( + FunctionType::get(B.getVoidTy(), {B.getInt64Ty()}, false), + GlobalValue::ExternalLinkage, "F", &M); + + BasicBlock *Entry(BasicBlock::Create(C, "", F)); + B.SetInsertPoint(Entry); + + Value *ArbitraryI32 = F->arg_begin(); + AllocaInst *I8 = B.CreateAlloca(B.getInt8Ty(), B.getInt32(2)); + auto *I8AtUncertainOffset = + cast(B.CreateGEP(I8, ArbitraryI32)); + + BasicAAResult &BasicAA = setupAnalyses(); + ASSERT_EQ(BasicAA.alias( + MemoryLocation(I8, LocationSize::precise(2)), + MemoryLocation(I8AtUncertainOffset, LocationSize::precise(1))), + AliasResult::PartialAlias); + + ASSERT_EQ(BasicAA.alias( + MemoryLocation(I8, LocationSize::upperBound(2)), + MemoryLocation(I8AtUncertainOffset, LocationSize::precise(1))), + AliasResult::MayAlias); +} Index: llvm/trunk/unittests/Analysis/CMakeLists.txt =================================================================== --- llvm/trunk/unittests/Analysis/CMakeLists.txt +++ llvm/trunk/unittests/Analysis/CMakeLists.txt @@ -8,6 +8,7 @@ add_llvm_unittest(AnalysisTests AliasAnalysisTest.cpp AliasSetTrackerTest.cpp + BasicAliasAnalysisTest.cpp BlockFrequencyInfoTest.cpp BranchProbabilityInfoTest.cpp CallGraphTest.cpp