Index: llvm/trunk/include/llvm/Analysis/AliasSetTracker.h =================================================================== --- llvm/trunk/include/llvm/Analysis/AliasSetTracker.h +++ llvm/trunk/include/llvm/Analysis/AliasSetTracker.h @@ -115,15 +115,21 @@ } }; - 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; /// Number of nodes pointing to this AliasSet plus the number of AliasSets /// forwarding to it. - unsigned RefCount : 28; + unsigned RefCount : 27; + + // Signifies that this set should be considered to alias any pointer. + // Use when the tracker holding this set is saturated. + unsigned AliasAny : 1; /// The kinds of access this alias set models. /// @@ -153,7 +159,10 @@ /// True if this alias set contains volatile loads or stores. unsigned Volatile : 1; + unsigned SetSize; + void addRef() { ++RefCount; } + void dropRef(AliasSetTracker &AST) { assert(RefCount >= 1 && "Invalid reference count detected!"); if (--RefCount == 0) @@ -189,6 +198,10 @@ iterator end() const { return iterator(); } bool empty() const { return PtrList == nullptr; } + // Unfortunately, ilist::size() is linear, so we have to add code to keep + // track of the list's exact size. + unsigned size() { return SetSize; } + void print(raw_ostream &OS) const; void dump() const; @@ -230,9 +243,9 @@ // to serve as a sentinel. friend struct ilist_sentinel_traits; AliasSet() - : PtrList(nullptr), PtrListEnd(&PtrList), Forward(nullptr), RefCount(0), - Access(NoAccess), Alias(SetMustAlias), Volatile(false) { - } + : PtrList(nullptr), PtrListEnd(&PtrList), Forward(nullptr), RefCount(0), + AliasAny(false), Access(NoAccess), Alias(SetMustAlias), + Volatile(false), SetSize(0) {} AliasSet(const AliasSet &AS) = delete; void operator=(const AliasSet &AS) = delete; @@ -317,7 +330,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), AliasAnyAS(nullptr) {} ~AliasSetTracker() { clear(); } /// These methods are used to add different types of instructions to the alias @@ -395,6 +409,14 @@ private: friend class AliasSet; + + // The total number of pointers contained in all "may" alias sets. + unsigned TotalMayAliasSetSize; + + // A non-null value signifies this AST is saturated. A saturated AST lumps + // all pointers into a single "May" set. + AliasSet *AliasAnyAS; + void removeAliasSet(AliasSet *AS); /// Just like operator[] on the map, except that it creates an entry for the @@ -407,16 +429,14 @@ } 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); + /// Merge all alias sets into a single set that is considered to alias any + /// pointer. + AliasSet &mergeAllAliasSets(); + AliasSet *findAliasSetForUnknownInst(Instruction *Inst); }; Index: llvm/trunk/lib/Analysis/AliasSetTracker.cpp =================================================================== --- llvm/trunk/lib/Analysis/AliasSetTracker.cpp +++ llvm/trunk/lib/Analysis/AliasSetTracker.cpp @@ -26,12 +26,19 @@ #include "llvm/Support/raw_ostream.h" using namespace llvm; +static cl::opt + SaturationThreshold("alias-set-saturation-threshold", cl::Hidden, + cl::init(250), + cl::desc("The maximum number of pointers may-alias " + "sets may contain before degradation")); + /// 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 +59,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) { @@ -63,11 +77,13 @@ AS.UnknownInsts.clear(); } - AS.Forward = this; // Forward across AS now... - addRef(); // AS is now pointing to us... + AS.Forward = this; // Forward across AS now... + addRef(); // AS is now pointing to us... // Merge the list of constituent pointers... if (AS.PtrList) { + SetSize += AS.size(); + AS.SetSize = 0; *PtrListEnd = AS.PtrList; AS.PtrList->setPrevInList(PtrListEnd); PtrListEnd = AS.PtrListEnd; @@ -85,7 +101,12 @@ Fwd->dropRef(*this); AS->Forward = nullptr; } + + if (AS->Alias == AliasSet::SetMayAlias) + TotalMayAliasSetSize -= AS->size(); + AliasSets.erase(AS); + } void AliasSet::removeFromTracker(AliasSetTracker &AST) { @@ -105,10 +126,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!"); } @@ -116,11 +140,16 @@ Entry.updateSizeAndAAInfo(Size, AAInfo); // Add it to the end of the list... + ++SetSize; assert(*PtrListEnd == nullptr && "End of list is not null?"); *PtrListEnd = &Entry; PtrListEnd = Entry.setPrevInList(PtrListEnd); assert(*PtrListEnd == nullptr && "End of list is not null?"); - addRef(); // Entry points to alias set. + // Entry points to alias set. + addRef(); + + if (Alias == SetMayAlias) + AST.TotalMayAliasSetSize++; } void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) { @@ -145,6 +174,9 @@ bool AliasSet::aliasesPointer(const Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo, AliasAnalysis &AA) const { + if (AliasAny) + return true; + if (Alias == SetMustAlias) { assert(UnknownInsts.empty() && "Illegal must alias set!"); @@ -177,6 +209,10 @@ bool AliasSet::aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const { + + if (AliasAny) + return true; + if (!Inst->mayReadOrWriteMemory()) return false; @@ -250,9 +286,6 @@ return FoundSet; } - - - /// getAliasSetForPointer - Return the alias set that the specified pointer /// lives in. AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, uint64_t Size, @@ -260,6 +293,22 @@ bool *New) { AliasSet::PointerRec &Entry = getEntryFor(Pointer); + if (AliasAnyAS) { + // At this point, the AST is saturated, so we only have one active alias + // set. That means we already know which alias set we want to return, and + // just need to add the pointer to that set to keep the data structure + // consistent. + // This, of course, means that we will never need a merge here. + if (Entry.hasAliasSet()) { + Entry.updateSizeAndAAInfo(Size, AAInfo); + assert(Entry.getAliasSet(*this) == AliasAnyAS && + "Entry in saturated AST must belong to only alias set"); + } else { + AliasAnyAS->addPointer(*this, Entry, Size, AAInfo); + } + return *AliasAnyAS; + } + // 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 +495,11 @@ // Unlink and delete from the list of values. PtrValEnt->eraseFromList(); + + if (AS->Alias == AliasSet::SetMayAlias) { + AS->SetSize--; + TotalMayAliasSetSize--; + } // Stop using the alias set. AS->dropRef(*this); @@ -477,7 +531,60 @@ true); } +AliasSet &AliasSetTracker::mergeAllAliasSets() { + assert(!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold) && + "Full merge should happen once, when the saturation threshold is " + "reached"); + + // Collect all alias sets, so that we can drop references with impunity + // without worrying about iterator invalidation. + std::vector ASVector; + ASVector.reserve(SaturationThreshold); + 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()); + AliasAnyAS = &AliasSets.back(); + AliasAnyAS->Alias = AliasSet::SetMayAlias; + AliasAnyAS->Access = AliasSet::ModRefAccess; + AliasAnyAS->AliasAny = true; + + for (auto Cur : ASVector) { + + // If Cur was already forwarding, just forward to the new AS instead. + AliasSet *FwdTo = Cur->Forward; + if (FwdTo) { + Cur->Forward = AliasAnyAS; + AliasAnyAS->addRef(); + FwdTo->dropRef(*this); + continue; + } + + // Otherwise, perform the actual merge. + AliasAnyAS->mergeSetIn(*Cur, *this); + } + + return *AliasAnyAS; +} + +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 (!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold)) { + // The AST is now saturated. From here on, we conservatively consider all + // pointers to alias each-other. + return mergeAllAliasSets(); + } + + return AS; +} //===----------------------------------------------------------------------===// // AliasSet/AliasSetTracker Printing Support @@ -572,7 +679,7 @@ bool runOnFunction(Function &F) override { auto &AAWP = getAnalysis(); Tracker = new AliasSetTracker(AAWP.getAAResults()); - + errs() << "Alias sets for function '" << F.getName() << "':\n"; for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) Tracker->add(&*I); Tracker->print(errs()); Index: llvm/trunk/test/Analysis/AliasSet/saturation.ll =================================================================== --- llvm/trunk/test/Analysis/AliasSet/saturation.ll +++ llvm/trunk/test/Analysis/AliasSet/saturation.ll @@ -0,0 +1,53 @@ +; RUN: opt -basicaa -print-alias-sets -alias-set-saturation-threshold=2 -S -o - < %s 2>&1 | FileCheck %s --check-prefix=CHECK --check-prefix=NOSAT +; RUN: opt -basicaa -print-alias-sets -alias-set-saturation-threshold=1 -S -o - < %s 2>&1 | FileCheck %s --check-prefix=CHECK --check-prefix=SAT + +; CHECK-LABEL: 'allmust' +; CHECK: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %a, 4) +; CHECK: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %b, 4) +; CHECK: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %c, 4) +; CHECK: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %d, 4) +define void @allmust() { + %a = alloca i32 + %b = alloca i32 + %c = alloca i32 + %d = alloca i32 + store i32 1, i32* %a + store i32 2, i32* %b + store i32 3, i32* %c + store i32 4, i32* %d + ret void +} + +; CHECK-LABEL :'mergemay' +; NOSAT: AliasSet[{{.*}}, 2] may alias, Mod Pointers: (i32* %a, 4), (i32* %a1, 4) +; NOSAT: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %b, 4) +; SAT: AliasSet[{{.*}}, 2] may alias, Mod forwarding to 0x[[FWD:[0-9a-f]*]] +; SAT: AliasSet[{{.*}}, 1] must alias, Mod forwarding to 0x[[FWD]] +; SAT: AliasSet[0x[[FWD]], 2] may alias, Mod/Ref Pointers: (i32* %a, 4), (i32* %a1, 4), (i32* %b, 4) +define void @mergemay(i32 %k) { + %a = alloca i32 + %b = alloca i32 + store i32 1, i32* %a + store i32 2, i32* %b + %a1 = getelementptr i32, i32 *%a, i32 %k + store i32 2, i32* %a1 + ret void +} + +; CHECK-LABEL: 'mergemust' +; 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 @mergemust(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 +}