Index: include/llvm/Analysis/AliasSetTracker.h =================================================================== --- include/llvm/Analysis/AliasSetTracker.h +++ include/llvm/Analysis/AliasSetTracker.h @@ -22,11 +22,11 @@ #include "llvm/ADT/ilist_node.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/ValueHandle.h" +#include "llvm/Analysis/AliasAnalysis.h" #include namespace llvm { -class AliasAnalysis; class LoadInst; class StoreInst; class VAArgInst; @@ -123,12 +123,7 @@ /// memory (and not any particular access), whether it modifies or references /// the memory, or whether it does both. The lattice goes from "NoAccess" to /// either RefAccess or ModAccess, then to ModRefAccess as necessary. - enum AccessLattice { - NoAccess = 0, - RefAccess = 1, - ModAccess = 2, - ModRefAccess = RefAccess | ModAccess - }; + typedef ModRefInfo AccessLattice; unsigned Access : 2; /// The kind of alias relationship between pointers of the set. @@ -159,8 +154,8 @@ public: /// Accessors... - bool isRef() const { return Access & RefAccess; } - bool isMod() const { return Access & ModAccess; } + bool isRef() const { return Access & MRI_Ref; } + bool isMod() const { return Access & MRI_Mod; } bool isMustAlias() const { return Alias == SetMustAlias; } bool isMayAlias() const { return Alias == SetMayAlias; } @@ -224,7 +219,7 @@ friend struct ilist_sentinel_traits; AliasSet() : PtrList(nullptr), PtrListEnd(&PtrList), Forward(nullptr), RefCount(0), - Access(NoAccess), Alias(SetMustAlias), Volatile(false) { + Access(MRI_NoModRef), Alias(SetMustAlias), Volatile(false) { } AliasSet(const AliasSet &AS) = delete; @@ -252,9 +247,9 @@ void removeFromTracker(AliasSetTracker &AST); void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size, - const AAMDNodes &AAInfo, + const AAMDNodes &AAInfo, ModRefInfo MR, bool KnownMustAlias = false); - void addUnknownInst(Instruction *I, AliasAnalysis &AA); + void addUnknownInst(Instruction *I, AliasAnalysis &AA, ModRefInfo MR); void removeUnknownInst(AliasSetTracker &AST, Instruction *I) { bool WasEmpty = UnknownInsts.empty(); for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i) @@ -271,10 +266,18 @@ public: /// aliasesPointer - Return true if the specified pointer "may" (or must) /// alias one of the members in the set. - /// + /// MRcommon - if Ptr is aliased by existing UnknownInsts, + /// then not-null MRcommon will be set to the worst ModRefInfo met + /// bool aliasesPointer(const Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo, - AliasAnalysis &AA) const; - bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const; + AliasAnalysis &AA, ModRefInfo* MRcommon = nullptr) const; + /// aliasesUnknownInst - Return true if the specified UnknownInst + /// has not-null ModRefInfo (not MRI_NoModRef) with some + /// pointer or UnknownInst already existing in AliasSet + /// MRcommon - not-null MRcommon will be set to the worst ModRefInfo met + /// + bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA, + ModRefInfo* MRcommon = nullptr) const; }; inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) { @@ -433,9 +436,11 @@ return AS; } AliasSet *findAliasSetForPointer(const Value *Ptr, uint64_t Size, - const AAMDNodes &AAInfo); + const AAMDNodes &AAInfo, + ModRefInfo* MRcommonPtr = nullptr); - AliasSet *findAliasSetForUnknownInst(Instruction *Inst); + AliasSet *findAliasSetForUnknownInst(Instruction *Inst, + ModRefInfo* MRcommonPtr = nullptr); }; inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) { Index: lib/Analysis/AliasSetTracker.cpp =================================================================== --- lib/Analysis/AliasSetTracker.cpp +++ lib/Analysis/AliasSetTracker.cpp @@ -95,7 +95,7 @@ void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size, const AAMDNodes &AAInfo, - bool KnownMustAlias) { + ModRefInfo MR, bool KnownMustAlias) { assert(!Entry.hasAliasSet() && "Entry already in set!"); // Check to see if we have to downgrade to _may_ alias. @@ -112,6 +112,9 @@ assert(Result != NoAlias && "Cannot be part of must set!"); } + // upgrading access if existing UnknownInst has ModRef with new pointer + Access |= MR; + Entry.setAliasSet(this); Entry.updateSizeAndAAInfo(Size, AAInfo); @@ -123,20 +126,34 @@ addRef(); // Entry points to alias set. } -void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) { +void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA, + ModRefInfo MR) { if (UnknownInsts.empty()) addRef(); UnknownInsts.emplace_back(I); if (!I->mayWriteToMemory()) { Alias = SetMayAlias; - Access |= RefAccess; + Access |= MRI_Ref; return; } - // FIXME: This should use mod/ref information to make this not suck so bad Alias = SetMayAlias; - Access = ModRefAccess; + Access |= MR; +} + +namespace { + /// returns true if there is no request of worst ModRefInfo + /// (MRcommonPtr is null) + /// or when achieved maximum ModRefInfo (MRI_ModRef). + bool processMR(ModRefInfo MR, ModRefInfo* MRcommonPtr, ModRefInfo& MRcommon) { + MRcommon = ModRefInfo(MRcommon | MR); + return !MRcommonPtr || (MRcommon == MRI_ModRef); + } + bool fillExitMR(ModRefInfo* MRcommonPtr, ModRefInfo& MRcommon) { + if (MRcommonPtr) *MRcommonPtr = MRcommon; + return MRcommon != MRI_NoModRef; + } } /// aliasesPointer - Return true if the specified pointer "may" (or must) @@ -144,7 +161,8 @@ /// bool AliasSet::aliasesPointer(const Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo, - AliasAnalysis &AA) const { + AliasAnalysis &AA, + ModRefInfo* MRcommonPtr) const { if (Alias == SetMustAlias) { assert(UnknownInsts.empty() && "Illegal must alias set!"); @@ -164,35 +182,44 @@ MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo()))) return true; + // to gather worst ModRefInfo + ModRefInfo MRcommon = MRI_NoModRef; + // Check the unknown instructions... if (!UnknownInsts.empty()) { for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) - if (AA.getModRefInfo(UnknownInsts[i], - MemoryLocation(Ptr, Size, AAInfo)) != MRI_NoModRef) - return true; + if (processMR(AA.getModRefInfo(UnknownInsts[i], + MemoryLocation(Ptr, Size, AAInfo)), MRcommonPtr, MRcommon)) + return fillExitMR(MRcommonPtr, MRcommon); } - return false; + return fillExitMR(MRcommonPtr, MRcommon); } bool AliasSet::aliasesUnknownInst(const Instruction *Inst, - AliasAnalysis &AA) const { + AliasAnalysis &AA, + ModRefInfo* MRcommonPtr) const { if (!Inst->mayReadOrWriteMemory()) return false; + // to gather worst ModRefInfo + ModRefInfo MRcommon = MRI_NoModRef; + for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) { ImmutableCallSite C1(getUnknownInst(i)), C2(Inst); - if (!C1 || !C2 || AA.getModRefInfo(C1, C2) != MRI_NoModRef || - AA.getModRefInfo(C2, C1) != MRI_NoModRef) - return true; + if (!C1 || !C2 || + processMR(AA.getModRefInfo(C1, C2), MRcommonPtr, MRcommon) || + processMR(AA.getModRefInfo(C2, C1), MRcommonPtr, MRcommon)) + return fillExitMR(MRcommonPtr, MRcommon); } - for (iterator I = begin(), E = end(); I != E; ++I) - if (AA.getModRefInfo(Inst, MemoryLocation(I.getPointer(), I.getSize(), - I.getAAInfo())) != MRI_NoModRef) - return true; - - return false; + for (iterator I = begin(), E = end(); I != E; ++I) { + ModRefInfo MR = AA.getModRefInfo( + Inst, MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo())); + if (processMR(MR, MRcommonPtr, MRcommon)) + return fillExitMR(MRcommonPtr, MRcommon); + } + return fillExitMR(MRcommonPtr, MRcommon); } void AliasSetTracker::clear() { @@ -214,11 +241,15 @@ /// AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr, uint64_t Size, - const AAMDNodes &AAInfo) { + const AAMDNodes &AAInfo, + ModRefInfo* MRcommonPtr) { AliasSet *FoundSet = nullptr; for (iterator I = begin(), E = end(); I != E;) { iterator Cur = I++; - if (Cur->Forward || !Cur->aliasesPointer(Ptr, Size, AAInfo, AA)) continue; + ModRefInfo MR = MRI_NoModRef; + if (Cur->Forward || !Cur->aliasesPointer(Ptr, Size, AAInfo, AA, &MR)) + continue; + *MRcommonPtr = ModRefInfo(*MRcommonPtr | MR); if (!FoundSet) { // If this is the first alias set ptr can go into. FoundSet = Cur; // Remember it. @@ -248,12 +279,15 @@ return false; } -AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) { +AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst, + ModRefInfo* MRcommonPtr) { AliasSet *FoundSet = nullptr; for (iterator I = begin(), E = end(); I != E;) { iterator Cur = I++; - if (Cur->Forward || !Cur->aliasesUnknownInst(Inst, AA)) + ModRefInfo MR = MRI_NoModRef; + if (Cur->Forward || !Cur->aliasesUnknownInst(Inst, AA, &MR)) continue; + *MRcommonPtr = ModRefInfo(*MRcommonPtr | MR); if (!FoundSet) // If this is the first alias set ptr can go into. FoundSet = Cur; // Remember it. else if (!Cur->Forward) // Otherwise, we must merge the sets. @@ -279,22 +313,23 @@ return *Entry.getAliasSet(*this)->getForwardedTarget(*this); } - if (AliasSet *AS = findAliasSetForPointer(Pointer, Size, AAInfo)) { + ModRefInfo MR = MRI_NoModRef; + if (AliasSet *AS = findAliasSetForPointer(Pointer, Size, AAInfo, &MR)) { // Add it to the alias set it aliases. - AS->addPointer(*this, Entry, Size, AAInfo); + AS->addPointer(*this, Entry, Size, AAInfo, MR); 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, AAInfo); + AliasSets.back().addPointer(*this, Entry, Size, AAInfo, MRI_NoModRef); return AliasSets.back(); } bool AliasSetTracker::add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo) { bool NewPtr; - addPointer(Ptr, Size, AAInfo, AliasSet::NoAccess, NewPtr); + addPointer(Ptr, Size, AAInfo, MRI_NoModRef, NewPtr); return NewPtr; } @@ -305,7 +340,7 @@ AAMDNodes AAInfo; LI->getAAMetadata(AAInfo); - AliasSet::AccessLattice Access = AliasSet::RefAccess; + AliasSet::AccessLattice Access = MRI_Ref; bool NewPtr; const DataLayout &DL = LI->getModule()->getDataLayout(); AliasSet &AS = addPointer(LI->getOperand(0), @@ -321,7 +356,7 @@ AAMDNodes AAInfo; SI->getAAMetadata(AAInfo); - AliasSet::AccessLattice Access = AliasSet::ModAccess; + AliasSet::AccessLattice Access = MRI_Mod; bool NewPtr; const DataLayout &DL = SI->getModule()->getDataLayout(); Value *Val = SI->getOperand(0); @@ -338,7 +373,7 @@ bool NewPtr; addPointer(VAAI->getOperand(0), MemoryLocation::UnknownSize, AAInfo, - AliasSet::ModRefAccess, NewPtr); + MRI_ModRef, NewPtr); return NewPtr; } @@ -349,14 +384,15 @@ if (!Inst->mayReadOrWriteMemory()) return true; // doesn't alias anything - AliasSet *AS = findAliasSetForUnknownInst(Inst); + ModRefInfo MR = MRI_NoModRef; + AliasSet *AS = findAliasSetForUnknownInst(Inst, &MR); if (AS) { - AS->addUnknownInst(Inst, AA); + AS->addUnknownInst(Inst, AA, MR); return false; } AliasSets.push_back(new AliasSet()); AS = &AliasSets.back(); - AS->addUnknownInst(Inst, AA); + AS->addUnknownInst(Inst, AA, MR); return true; } @@ -556,7 +592,7 @@ I = PointerMap.find_as(From); AliasSet *AS = I->second->getAliasSet(*this); AS->addPointer(*this, Entry, I->second->getSize(), - I->second->getAAInfo(), + I->second->getAAInfo(), MRI_NoModRef, true); } @@ -570,10 +606,10 @@ OS << " AliasSet[" << (const void*)this << ", " << RefCount << "] "; OS << (Alias == SetMustAlias ? "must" : "may") << " alias, "; switch (Access) { - case NoAccess: OS << "No access "; break; - case RefAccess: OS << "Ref "; break; - case ModAccess: OS << "Mod "; break; - case ModRefAccess: OS << "Mod/Ref "; break; + case MRI_NoModRef: OS << "No access "; break; + case MRI_Ref: OS << "Ref "; break; + case MRI_Mod: OS << "Mod "; break; + case MRI_ModRef: OS << "Mod/Ref "; break; default: llvm_unreachable("Bad value for Access!"); } if (isVolatile()) OS << "[volatile] "; Index: test/Transforms/LICM/licm_call_referenced_ptr.ll =================================================================== --- test/Transforms/LICM/licm_call_referenced_ptr.ll +++ test/Transforms/LICM/licm_call_referenced_ptr.ll @@ -0,0 +1,40 @@ +; RUN: opt < %s -basicaa -licm -S | FileCheck %s + +declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i32, i1) nounwind + +define i8 @"main"() { +entry: + %A = alloca [64 x i8] + %B = alloca [4 x i8] + %A0 = getelementptr [64 x i8], [64 x i8]* %A, i32 0, i32 0 + %B0 = getelementptr [4 x i8], [4 x i8]* %B, i32 0, i32 0 + %B1 = getelementptr [4 x i8], [4 x i8]* %B, i32 0, i32 1 + %B2 = getelementptr [4 x i8], [4 x i8]* %B, i32 0, i32 2 + %B3 = getelementptr [4 x i8], [4 x i8]* %B, i32 0, i32 3 + store i8 0, i8* %A0 + store i8 32, i8* %B0 + store i8 73, i8* %B1 + store i8 74, i8* %B2 + store i8 75, i8* %B3 + br label %loop_begin + +loop_begin: +; CHECK: loop_begin: +; CHECK-NEXT: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %A0, i8* %B0, i64 4, i32 4, i1 false) + + %b_val = load i8, i8* %B0 + + ; *B is invariant in loop and limit_val must be hoisted + %limit_val_1 = mul i8 %b_val, 3 + %limit_val = add i8 %limit_val_1, 67 + + call void @llvm.memcpy.p0i8.p0i8.i64(i8* %A0, i8* %B0, i64 4, i32 4, i1 false) + + %exitcond = icmp ugt i8 164, %limit_val + br i1 %exitcond, label %after_loop, label %loop_begin + +after_loop: + %b_val_result = load i8, i8* %B0 + ret i8 %b_val_result +} +