Index: include/llvm/Analysis/AliasSetTracker.h =================================================================== --- include/llvm/Analysis/AliasSetTracker.h +++ include/llvm/Analysis/AliasSetTracker.h @@ -115,8 +115,10 @@ } }; - PointerRec *PtrList, **PtrListEnd; // Doubly linked list of nodes. - AliasSet *Forward; // Forwarding pointer. + // Doubly linked list of nodes. + PointerRec *PtrList, **PtrListEnd; + // Forwarding pointer. + AliasSet *Forward; /// All instructions without a specific address in this alias set. std::vector > UnknownInsts; @@ -189,6 +191,12 @@ iterator end() const { return iterator(); } bool empty() const { return PtrList == nullptr; } + // TODO: This should not be RefCount - RefCount is an upper bound on the + // size, not the actual size, since it includes other references, + // like forwarding sets. Unfortunately, ilist::size() is linear, so we'd have + // to add code to keep track of the exact size. + unsigned size() { return RefCount; } + void print(raw_ostream &OS) const; void dump() const; @@ -317,7 +325,8 @@ public: /// Create an empty collection of AliasSets, and use the specified alias /// analysis object to disambiguate load and store addresses. - explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {} + explicit AliasSetTracker(AliasAnalysis &aa) + : AA(aa), TotalMayAliasSetSize(0), Saturated(false) {} ~AliasSetTracker() { clear(); } /// These methods are used to add different types of instructions to the alias @@ -395,6 +404,16 @@ private: friend class AliasSet; + + // An upper bound for the total number of pointers contained in all + // "may" alias sets. + // TODO: Make this precise, see AliasSet::size() for details. + unsigned TotalMayAliasSetSize; + + // Signifies this AST is saturated. A saturated AST lumps all pointers into + // a single "May" set. + bool Saturated; + void removeAliasSet(AliasSet *AS); /// Just like operator[] on the map, except that it creates an entry for the @@ -407,16 +426,12 @@ } AliasSet &addPointer(Value *P, uint64_t Size, const AAMDNodes &AAInfo, - AliasSet::AccessLattice E, - bool &NewSet) { - NewSet = false; - AliasSet &AS = getAliasSetForPointer(P, Size, AAInfo, &NewSet); - AS.Access |= E; - return AS; - } + AliasSet::AccessLattice E, bool &NewSet); AliasSet *mergeAliasSetsForPointer(const Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo); + AliasSet &mergeAllAliasSets(); + AliasSet *findAliasSetForUnknownInst(Instruction *Inst); }; Index: lib/Analysis/AliasSetTracker.cpp =================================================================== --- lib/Analysis/AliasSetTracker.cpp +++ lib/Analysis/AliasSetTracker.cpp @@ -26,12 +26,16 @@ #include "llvm/Support/raw_ostream.h" using namespace llvm; +static cl::opt SaturationBound("alias-set-saturation-size", + cl::Hidden, cl::init(250)); + /// mergeSetIn - Merge the specified alias set into this alias set. /// void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) { assert(!AS.Forward && "Alias set is already forwarding!"); assert(!Forward && "This set is a forwarding set!!"); + bool WasMustAlias = (Alias == SetMustAlias); // Update the alias and access types of this set... Access |= AS.Access; Alias |= AS.Alias; @@ -52,6 +56,13 @@ Alias = SetMayAlias; } + if (Alias == SetMayAlias) { + if (WasMustAlias) + AST.TotalMayAliasSetSize += size(); + if (AS.Alias == SetMustAlias) + AST.TotalMayAliasSetSize += AS.size(); + } + bool ASHadUnknownInsts = !AS.UnknownInsts.empty(); if (UnknownInsts.empty()) { // Merge call sites... if (ASHadUnknownInsts) { @@ -86,6 +97,9 @@ AS->Forward = nullptr; } AliasSets.erase(AS); + + if (AS->Alias == AliasSet::SetMayAlias) + TotalMayAliasSetSize -= AS->size(); } void AliasSet::removeFromTracker(AliasSetTracker &AST) { @@ -105,10 +119,13 @@ AliasResult Result = AA.alias(MemoryLocation(P->getValue(), P->getSize(), P->getAAInfo()), MemoryLocation(Entry.getValue(), Size, AAInfo)); - if (Result != MustAlias) + if (Result != MustAlias) { Alias = SetMayAlias; - else // First entry of must alias must have maximum size! + AST.TotalMayAliasSetSize += size(); + } else { + // First entry of must alias must have maximum size! P->updateSizeAndAAInfo(Size, AAInfo); + } assert(Result != NoAlias && "Cannot be part of must set!"); } @@ -121,6 +138,9 @@ PtrListEnd = Entry.setPrevInList(PtrListEnd); assert(*PtrListEnd == nullptr && "End of list is not null?"); addRef(); // Entry points to alias set. + + if (Alias == SetMayAlias) + AST.TotalMayAliasSetSize++; } void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) { @@ -145,6 +165,9 @@ bool AliasSet::aliasesPointer(const Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo, AliasAnalysis &AA) const { + // TODO: If the AST is saturated, the answer for the special set should be + // yes. + if (Alias == SetMustAlias) { assert(UnknownInsts.empty() && "Illegal must alias set!"); @@ -177,6 +200,10 @@ bool AliasSet::aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const { + + // TODO: If the AST is saturated, the answer for the special set should be + // yes. + if (!Inst->mayReadOrWriteMemory()) return false; @@ -250,9 +277,6 @@ return FoundSet; } - - - /// getAliasSetForPointer - Return the alias set that the specified pointer /// lives in. AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, uint64_t Size, @@ -260,6 +284,17 @@ bool *New) { AliasSet::PointerRec &Entry = getEntryFor(Pointer); + if (Saturated) { + // Update the data structure, for the sake of consistency. + // Note that we will never need a merge here, since there's only one + // active alias set. + if (Entry.hasAliasSet()) + Entry.updateSizeAndAAInfo(Size, AAInfo); + else + AliasSets.back().addPointer(*this, Entry, Size, AAInfo); + return AliasSets.back(); + } + // Check to see if the pointer is already known. if (Entry.hasAliasSet()) { // If the size changed, we may need to merge several alias sets. @@ -446,6 +481,9 @@ // Unlink and delete from the list of values. PtrValEnt->eraseFromList(); + + if (AS->Alias == AliasSet::SetMayAlias) + TotalMayAliasSetSize--; // Stop using the alias set. AS->dropRef(*this); @@ -476,7 +514,76 @@ true); } +AliasSet &AliasSetTracker::mergeAllAliasSets() { + Saturated = true; + + // Collect all alias sets, so that we can drop references with impunity + // without worrying about iterator invalidation. + std::vector ASVector; + ASVector.reserve(SaturationBound); + for (iterator I = begin(), E = end(); I != E; I++) + ASVector.push_back(&*I); + + // Copy all instructions and pointers into a new set, and forward all other + // sets to it. + AliasSets.push_back(new AliasSet()); + AliasSet &DummyAS = AliasSets.back(); + DummyAS.Alias = AliasSet::SetMayAlias; + DummyAS.Access = AliasSet::ModRefAccess; + + for (auto Cur : ASVector) { + // Redirect the existing set here. + AliasSet *FwdTo = Cur->Forward; + Cur->Forward = &DummyAS; + DummyAS.addRef(); + + // If Cur was already forwarding, that is enough. + if (FwdTo) { + FwdTo->dropRef(*this); + continue; + } + + // Otherwise, we need to do the actual work of copying. + if (!Cur->UnknownInsts.empty()) { + if (DummyAS.UnknownInsts.empty()) + DummyAS.addRef(); + DummyAS.UnknownInsts.insert(DummyAS.UnknownInsts.end(), + Cur->UnknownInsts.begin(), + Cur->UnknownInsts.end()); + Cur->UnknownInsts.clear(); + Cur->dropRef(*this); + } + + // Merge the list pointers... + if (Cur->PtrList) { + *DummyAS.PtrListEnd = Cur->PtrList; + Cur->PtrList->setPrevInList(DummyAS.PtrListEnd); + DummyAS.PtrListEnd = Cur->PtrListEnd; + + Cur->PtrList = nullptr; + Cur->PtrListEnd = &Cur->PtrList; + } + } + + return AliasSets.back(); +} + +AliasSet &AliasSetTracker::addPointer(Value *P, uint64_t Size, + const AAMDNodes &AAInfo, + AliasSet::AccessLattice E, bool &NewSet) { + NewSet = false; + AliasSet &AS = getAliasSetForPointer(P, Size, AAInfo, &NewSet); + AS.Access |= E; + + if (!Saturated && (TotalMayAliasSetSize > SaturationBound)) { + // The AS is now saturated. From here on, we conservatively consider all + // pointers to alias each-other. + return mergeAllAliasSets(); + } + + return AS; +} //===----------------------------------------------------------------------===// // AliasSet/AliasSetTracker Printing Support Index: test/Analysis/AliasSet/saturation.ll =================================================================== --- test/Analysis/AliasSet/saturation.ll +++ test/Analysis/AliasSet/saturation.ll @@ -0,0 +1,21 @@ +; RUN: opt -basicaa -print-alias-sets -alias-set-saturation-size=2 -S -o - < %s 2>&1 | FileCheck %s --check-prefix=NOSAT +; RUN: opt -basicaa -print-alias-sets -alias-set-saturation-size=1 -S -o - < %s 2>&1 | FileCheck %s --check-prefix=SAT + +; NOSAT: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %a, 4) +; NOSAT: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %b, 4) +; NOSAT: AliasSet[{{.*}}, 2] may alias, Mod Pointers: (i32* %c, 4), (i32* %d, 4) + +; SAT: AliasSet[{{.*}}, 1] must alias, Mod forwarding to 0x[[FWD:[0-9a-f]*]] +; SAT: AliasSet[{{.*}}, 1] must alias, Mod forwarding to 0x[[FWD]] +; SAT: AliasSet[{{.*}}, 2] may alias, Mod forwarding to 0x[[FWD]] +; SAT: AliasSet[0x[[FWD]], 3] may alias, Mod/Ref Pointers: (i32* %a, 4), (i32* %b, 4), (i32* %c, 4), (i32* %d, 4) + +define void @foo(i32* %c, i32* %d) { + %a = alloca i32 + %b = alloca i32 + store i32 1, i32* %a + store i32 2, i32* %b + store i32 3, i32* %c + store i32 4, i32* %d + ret void +}