From a8702eaf78e70e1eef8a63882ce97ae6d60edf5b Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Mon, 18 Oct 2010 20:44:50 +0000 Subject: [PATCH] Make AliasSetTracker TBAA-aware, enabling TBAA-enabled LICM. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@116743 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/AliasSetTracker.h | 41 ++++++++++---- include/llvm/LinkAllPasses.h | 2 +- lib/Analysis/AliasSetTracker.cpp | 73 +++++++++++++++++-------- lib/Transforms/Scalar/LICM.cpp | 9 ++- 4 files changed, 85 insertions(+), 40 deletions(-) diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h index 8e2f7fd29a3..d3e8c727ed3 100644 --- a/include/llvm/Analysis/AliasSetTracker.h +++ b/include/llvm/Analysis/AliasSetTracker.h @@ -41,9 +41,10 @@ class AliasSet : public ilist_node { PointerRec **PrevInList, *NextInList; AliasSet *AS; unsigned Size; + const MDNode *TBAAInfo; public: PointerRec(Value *V) - : Val(V), PrevInList(0), NextInList(0), AS(0), Size(0) {} + : Val(V), PrevInList(0), NextInList(0), AS(0), Size(0), TBAAInfo(0) {} Value *getValue() const { return Val; } @@ -55,12 +56,19 @@ class AliasSet : public ilist_node { return &NextInList; } - void updateSize(unsigned NewSize) { + void updateSizeAndTBAAInfo(unsigned NewSize, const MDNode *NewTBAAInfo) { if (NewSize > Size) Size = NewSize; + + if (!TBAAInfo) + TBAAInfo = NewTBAAInfo; + else if (TBAAInfo != NewTBAAInfo) + TBAAInfo = reinterpret_cast(-1); } unsigned getSize() const { return Size; } + const MDNode *getTBAAInfo() const { return TBAAInfo; } + AliasSet *getAliasSet(AliasSetTracker &AST) { assert(AS && "No AliasSet yet!"); if (AS->Forward) { @@ -187,6 +195,7 @@ public: Value *getPointer() const { return CurNode->getValue(); } unsigned getSize() const { return CurNode->getSize(); } + const MDNode *getTBAAInfo() const { return CurNode->getTBAAInfo(); } iterator& operator++() { // Preincrement assert(CurNode && "Advancing past AliasSet.end()!"); @@ -231,6 +240,7 @@ private: void removeFromTracker(AliasSetTracker &AST); void addPointer(AliasSetTracker &AST, PointerRec &Entry, unsigned Size, + const MDNode *TBAAInfo, bool KnownMustAlias = false); void addCallSite(CallSite CS, AliasAnalysis &AA); void removeCallSite(CallSite CS) { @@ -245,7 +255,8 @@ private: /// aliasesPointer - Return true if the specified pointer "may" (or must) /// alias one of the members in the set. /// - bool aliasesPointer(const Value *Ptr, unsigned Size, AliasAnalysis &AA) const; + bool aliasesPointer(const Value *Ptr, unsigned Size, const MDNode *TBAAInfo, + AliasAnalysis &AA) const; bool aliasesCallSite(CallSite CS, AliasAnalysis &AA) const; }; @@ -298,7 +309,7 @@ public: /// These methods return true if inserting the instruction resulted in the /// addition of a new alias set (i.e., the pointer did not alias anything). /// - bool add(Value *Ptr, unsigned Size); // Add a location + bool add(Value *Ptr, unsigned Size, const MDNode *TBAAInfo); // Add a location bool add(LoadInst *LI); bool add(StoreInst *SI); bool add(VAArgInst *VAAI); @@ -312,7 +323,8 @@ public: /// remove methods - These methods are used to remove all entries that might /// be aliased by the specified instruction. These methods return true if any /// alias sets were eliminated. - bool remove(Value *Ptr, unsigned Size); // Remove a location + // Remove a location + bool remove(Value *Ptr, unsigned Size, const MDNode *TBAAInfo); bool remove(LoadInst *LI); bool remove(StoreInst *SI); bool remove(VAArgInst *VAAI); @@ -332,18 +344,21 @@ public: /// lives in. If the New argument is non-null, this method sets the value to /// true if a new alias set is created to contain the pointer (because the /// pointer didn't alias anything). - AliasSet &getAliasSetForPointer(Value *P, unsigned Size, bool *New = 0); + AliasSet &getAliasSetForPointer(Value *P, unsigned Size, + const MDNode *TBAAInfo, + bool *New = 0); /// getAliasSetForPointerIfExists - Return the alias set containing the /// location specified if one exists, otherwise return null. - AliasSet *getAliasSetForPointerIfExists(Value *P, unsigned Size) { - return findAliasSetForPointer(P, Size); + AliasSet *getAliasSetForPointerIfExists(Value *P, unsigned Size, + const MDNode *TBAAInfo) { + return findAliasSetForPointer(P, Size, TBAAInfo); } /// containsPointer - Return true if the specified location is represented by /// this alias set, false otherwise. This does not modify the AST object or /// alias sets. - bool containsPointer(Value *P, unsigned Size) const; + bool containsPointer(Value *P, unsigned Size, const MDNode *TBAAInfo) const; /// getAliasAnalysis - Return the underlying alias analysis object used by /// this tracker. @@ -390,14 +405,16 @@ private: return *Entry; } - AliasSet &addPointer(Value *P, unsigned Size, AliasSet::AccessType E, + AliasSet &addPointer(Value *P, unsigned Size, const MDNode *TBAAInfo, + AliasSet::AccessType E, bool &NewSet) { NewSet = false; - AliasSet &AS = getAliasSetForPointer(P, Size, &NewSet); + AliasSet &AS = getAliasSetForPointer(P, Size, TBAAInfo, &NewSet); AS.AccessTy |= E; return AS; } - AliasSet *findAliasSetForPointer(const Value *Ptr, unsigned Size); + AliasSet *findAliasSetForPointer(const Value *Ptr, unsigned Size, + const MDNode *TBAAInfo); AliasSet *findAliasSetForCallSite(CallSite CS); }; diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h index 7af4465b401..7bd365183fa 100644 --- a/include/llvm/LinkAllPasses.h +++ b/include/llvm/LinkAllPasses.h @@ -152,7 +152,7 @@ namespace { (void)new llvm::ScalarEvolution(); ((llvm::Function*)0)->viewCFGOnly(); llvm::AliasSetTracker X(*(llvm::AliasAnalysis*)0); - X.add((llvm::Value*)0, 0); // for -print-alias-sets + X.add((llvm::Value*)0, 0, 0); // for -print-alias-sets } } ForcePassLinking; // Force link by creating a global definition. } diff --git a/lib/Analysis/AliasSetTracker.cpp b/lib/Analysis/AliasSetTracker.cpp index 68525f256e5..0f13af6ab06 100644 --- a/lib/Analysis/AliasSetTracker.cpp +++ b/lib/Analysis/AliasSetTracker.cpp @@ -15,6 +15,7 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Instructions.h" #include "llvm/IntrinsicInst.h" +#include "llvm/LLVMContext.h" #include "llvm/Pass.h" #include "llvm/Type.h" #include "llvm/Target/TargetData.h" @@ -87,7 +88,8 @@ void AliasSet::removeFromTracker(AliasSetTracker &AST) { } void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry, - unsigned Size, bool KnownMustAlias) { + unsigned Size, const MDNode *TBAAInfo, + bool KnownMustAlias) { assert(!Entry.hasAliasSet() && "Entry already in set!"); // Check to see if we have to downgrade to _may_ alias. @@ -95,16 +97,18 @@ void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry, if (PointerRec *P = getSomePointer()) { AliasAnalysis &AA = AST.getAliasAnalysis(); AliasAnalysis::AliasResult Result = - AA.alias(P->getValue(), P->getSize(), Entry.getValue(), Size); + AA.alias(AliasAnalysis::Location(P->getValue(), P->getSize(), + P->getTBAAInfo()), + AliasAnalysis::Location(Entry.getValue(), Size, TBAAInfo)); if (Result == AliasAnalysis::MayAlias) AliasTy = MayAlias; else // First entry of must alias must have maximum size! - P->updateSize(Size); + P->updateSizeAndTBAAInfo(Size, TBAAInfo); assert(Result != AliasAnalysis::NoAlias && "Cannot be part of must set!"); } Entry.setAliasSet(this); - Entry.updateSize(Size); + Entry.updateSizeAndTBAAInfo(Size, TBAAInfo); // Add it to the end of the list... assert(*PtrListEnd == 0 && "End of list is not null?"); @@ -135,6 +139,7 @@ void AliasSet::addCallSite(CallSite CS, AliasAnalysis &AA) { /// alias one of the members in the set. /// bool AliasSet::aliasesPointer(const Value *Ptr, unsigned Size, + const MDNode *TBAAInfo, AliasAnalysis &AA) const { if (AliasTy == MustAlias) { assert(CallSites.empty() && "Illegal must alias set!"); @@ -143,19 +148,25 @@ bool AliasSet::aliasesPointer(const Value *Ptr, unsigned Size, // SOME value in the set. PointerRec *SomePtr = getSomePointer(); assert(SomePtr && "Empty must-alias set??"); - return AA.alias(SomePtr->getValue(), SomePtr->getSize(), Ptr, Size); + return AA.alias(AliasAnalysis::Location(SomePtr->getValue(), + SomePtr->getSize(), + SomePtr->getTBAAInfo()), + AliasAnalysis::Location(Ptr, Size, TBAAInfo)); } // If this is a may-alias set, we have to check all of the pointers in the set // to be sure it doesn't alias the set... for (iterator I = begin(), E = end(); I != E; ++I) - if (AA.alias(Ptr, Size, I.getPointer(), I.getSize())) + if (AA.alias(AliasAnalysis::Location(Ptr, Size, TBAAInfo), + AliasAnalysis::Location(I.getPointer(), I.getSize(), I.getTBAAInfo()))) return true; // Check the call sites list and invoke list... if (!CallSites.empty()) { for (unsigned i = 0, e = CallSites.size(); i != e; ++i) - if (AA.getModRefInfo(CallSites[i], Ptr, Size) != AliasAnalysis::NoModRef) + if (AA.getModRefInfo(CallSites[i], + AliasAnalysis::Location(Ptr, Size, TBAAInfo)) != + AliasAnalysis::NoModRef) return true; } @@ -198,10 +209,11 @@ void AliasSetTracker::clear() { /// that may alias the pointer, merge them together and return the unified set. /// AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr, - unsigned Size) { + unsigned Size, + const MDNode *TBAAInfo) { AliasSet *FoundSet = 0; for (iterator I = begin(), E = end(); I != E; ++I) { - if (I->Forward || !I->aliasesPointer(Ptr, Size, AA)) continue; + if (I->Forward || !I->aliasesPointer(Ptr, Size, TBAAInfo, AA)) continue; if (FoundSet == 0) { // If this is the first alias set ptr can go into. FoundSet = I; // Remember it. @@ -216,9 +228,10 @@ AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr, /// containsPointer - Return true if the specified location is represented by /// this alias set, false otherwise. This does not modify the AST object or /// alias sets. -bool AliasSetTracker::containsPointer(Value *Ptr, unsigned Size) const { +bool AliasSetTracker::containsPointer(Value *Ptr, unsigned Size, + const MDNode *TBAAInfo) const { for (const_iterator I = begin(), E = end(); I != E; ++I) - if (!I->Forward && I->aliasesPointer(Ptr, Size, AA)) + if (!I->Forward && I->aliasesPointer(Ptr, Size, TBAAInfo, AA)) return true; return false; } @@ -245,32 +258,33 @@ AliasSet *AliasSetTracker::findAliasSetForCallSite(CallSite CS) { /// getAliasSetForPointer - Return the alias set that the specified pointer /// lives in. AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, unsigned Size, + const MDNode *TBAAInfo, bool *New) { AliasSet::PointerRec &Entry = getEntryFor(Pointer); // Check to see if the pointer is already known. if (Entry.hasAliasSet()) { - Entry.updateSize(Size); + Entry.updateSizeAndTBAAInfo(Size, TBAAInfo); // Return the set! return *Entry.getAliasSet(*this)->getForwardedTarget(*this); } - if (AliasSet *AS = findAliasSetForPointer(Pointer, Size)) { + if (AliasSet *AS = findAliasSetForPointer(Pointer, Size, TBAAInfo)) { // Add it to the alias set it aliases. - AS->addPointer(*this, Entry, Size); + AS->addPointer(*this, Entry, Size, TBAAInfo); return *AS; } if (New) *New = true; // Otherwise create a new alias set to hold the loaded pointer. AliasSets.push_back(new AliasSet()); - AliasSets.back().addPointer(*this, Entry, Size); + AliasSets.back().addPointer(*this, Entry, Size, TBAAInfo); return AliasSets.back(); } -bool AliasSetTracker::add(Value *Ptr, unsigned Size) { +bool AliasSetTracker::add(Value *Ptr, unsigned Size, const MDNode *TBAAInfo) { bool NewPtr; - addPointer(Ptr, Size, AliasSet::NoModRef, NewPtr); + addPointer(Ptr, Size, TBAAInfo, AliasSet::NoModRef, NewPtr); return NewPtr; } @@ -279,6 +293,7 @@ bool AliasSetTracker::add(LoadInst *LI) { bool NewPtr; AliasSet &AS = addPointer(LI->getOperand(0), AA.getTypeStoreSize(LI->getType()), + LI->getMetadata(LLVMContext::MD_tbaa), AliasSet::Refs, NewPtr); if (LI->isVolatile()) AS.setVolatile(); return NewPtr; @@ -289,6 +304,7 @@ bool AliasSetTracker::add(StoreInst *SI) { Value *Val = SI->getOperand(0); AliasSet &AS = addPointer(SI->getOperand(1), AA.getTypeStoreSize(Val->getType()), + SI->getMetadata(LLVMContext::MD_tbaa), AliasSet::Mods, NewPtr); if (SI->isVolatile()) AS.setVolatile(); return NewPtr; @@ -296,7 +312,9 @@ bool AliasSetTracker::add(StoreInst *SI) { bool AliasSetTracker::add(VAArgInst *VAAI) { bool NewPtr; - addPointer(VAAI->getOperand(0), ~0, AliasSet::ModRef, NewPtr); + addPointer(VAAI->getOperand(0), AliasAnalysis::UnknownSize, + VAAI->getMetadata(LLVMContext::MD_tbaa), + AliasSet::ModRef, NewPtr); return NewPtr; } @@ -358,6 +376,7 @@ void AliasSetTracker::add(const AliasSetTracker &AST) { bool X; for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) { AliasSet &NewAS = addPointer(ASI.getPointer(), ASI.getSize(), + ASI.getTBAAInfo(), (AliasSet::AccessType)AS.AccessTy, X); if (AS.isVolatile()) NewAS.setVolatile(); } @@ -393,8 +412,9 @@ void AliasSetTracker::remove(AliasSet &AS) { AS.removeFromTracker(*this); } -bool AliasSetTracker::remove(Value *Ptr, unsigned Size) { - AliasSet *AS = findAliasSetForPointer(Ptr, Size); +bool +AliasSetTracker::remove(Value *Ptr, unsigned Size, const MDNode *TBAAInfo) { + AliasSet *AS = findAliasSetForPointer(Ptr, Size, TBAAInfo); if (!AS) return false; remove(*AS); return true; @@ -402,7 +422,8 @@ bool AliasSetTracker::remove(Value *Ptr, unsigned Size) { bool AliasSetTracker::remove(LoadInst *LI) { unsigned Size = AA.getTypeStoreSize(LI->getType()); - AliasSet *AS = findAliasSetForPointer(LI->getOperand(0), Size); + const MDNode *TBAAInfo = LI->getMetadata(LLVMContext::MD_tbaa); + AliasSet *AS = findAliasSetForPointer(LI->getOperand(0), Size, TBAAInfo); if (!AS) return false; remove(*AS); return true; @@ -410,14 +431,17 @@ bool AliasSetTracker::remove(LoadInst *LI) { bool AliasSetTracker::remove(StoreInst *SI) { unsigned Size = AA.getTypeStoreSize(SI->getOperand(0)->getType()); - AliasSet *AS = findAliasSetForPointer(SI->getOperand(1), Size); + const MDNode *TBAAInfo = SI->getMetadata(LLVMContext::MD_tbaa); + AliasSet *AS = findAliasSetForPointer(SI->getOperand(1), Size, TBAAInfo); if (!AS) return false; remove(*AS); return true; } bool AliasSetTracker::remove(VAArgInst *VAAI) { - AliasSet *AS = findAliasSetForPointer(VAAI->getOperand(0), ~0); + AliasSet *AS = findAliasSetForPointer(VAAI->getOperand(0), + AliasAnalysis::UnknownSize, + VAAI->getMetadata(LLVMContext::MD_tbaa)); if (!AS) return false; remove(*AS); return true; @@ -507,7 +531,8 @@ void AliasSetTracker::copyValue(Value *From, Value *To) { // Add it to the alias set it aliases... I = PointerMap.find(From); AliasSet *AS = I->second->getAliasSet(*this); - AS->addPointer(*this, Entry, I->second->getSize(), true); + AS->addPointer(*this, Entry, I->second->getSize(), I->second->getTBAAInfo(), + true); } diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp index d9afaa21cb7..12fcd028f50 100644 --- a/lib/Transforms/Scalar/LICM.cpp +++ b/lib/Transforms/Scalar/LICM.cpp @@ -36,6 +36,7 @@ #include "llvm/DerivedTypes.h" #include "llvm/IntrinsicInst.h" #include "llvm/Instructions.h" +#include "llvm/LLVMContext.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AliasSetTracker.h" #include "llvm/Analysis/ConstantFolding.h" @@ -187,9 +188,10 @@ namespace { /// pointerInvalidatedByLoop - Return true if the body of this loop may /// store into the memory location pointed to by V. /// - bool pointerInvalidatedByLoop(Value *V, unsigned Size) { + bool pointerInvalidatedByLoop(Value *V, unsigned Size, + const MDNode *TBAAInfo) { // Check to see if any of the basic blocks in CurLoop invalidate *V. - return CurAST->getAliasSetForPointer(V, Size).isMod(); + return CurAST->getAliasSetForPointer(V, Size, TBAAInfo).isMod(); } bool canSinkOrHoistInst(Instruction &I); @@ -402,7 +404,8 @@ bool LICM::canSinkOrHoistInst(Instruction &I) { unsigned Size = 0; if (LI->getType()->isSized()) Size = AA->getTypeStoreSize(LI->getType()); - return !pointerInvalidatedByLoop(LI->getOperand(0), Size); + return !pointerInvalidatedByLoop(LI->getOperand(0), Size, + LI->getMetadata(LLVMContext::MD_tbaa)); } else if (CallInst *CI = dyn_cast(&I)) { // Handle obvious cases efficiently. AliasAnalysis::ModRefBehavior Behavior = AA->getModRefBehavior(CI); -- 2.34.1