Index: include/llvm/Analysis/MemorySSA.h =================================================================== --- include/llvm/Analysis/MemorySSA.h +++ include/llvm/Analysis/MemorySSA.h @@ -255,6 +255,10 @@ inline MemoryAccess *getOptimized() const; inline void setOptimized(MemoryAccess *); + bool definingAccessMayAlias() const { return !isMustAlias; } + + bool definingAccessMustAlias() const { return isMustAlias; } + /// \brief Reset the ID of what this MemoryUse was optimized to, causing it to /// be rewalked by the walker if necessary. /// This really should only be called by tests. @@ -270,16 +274,24 @@ setDefiningAccess(DMA); } - void setDefiningAccess(MemoryAccess *DMA, bool Optimized = false) { + void setDefiningToMayAlias() { isMustAlias = false; } + + void setDefiningToMustAlias() { isMustAlias = true; } + + void setDefiningAccess(MemoryAccess *DMA, bool Optimized = false, + bool IsMustAlias = false) { if (!Optimized) { + setDefiningToMayAlias(); setOperand(0, DMA); return; } + isMustAlias = IsMustAlias; setOptimized(DMA); } private: Instruction *MemoryInst; + bool isMustAlias; }; template <> Index: lib/Analysis/MemorySSA.cpp =================================================================== --- lib/Analysis/MemorySSA.cpp +++ lib/Analysis/MemorySSA.cpp @@ -234,10 +234,21 @@ return Result; } -static bool instructionClobbersQuery(MemoryDef *MD, - const MemoryLocation &UseLoc, - const Instruction *UseInst, - AliasAnalysis &AA) { +namespace { + +struct ClobberAlias { + bool IsClobber; + bool IsMustAlias; +}; + +} // end anonymous namespace + +// Return a pair of {IsClobber, IsMustAlias}. It relies on IsMustAlias being +// ignored if IsClobber = false. +static ClobberAlias instructionClobbersQuery(MemoryDef *MD, + const MemoryLocation &UseLoc, + const Instruction *UseInst, + AliasAnalysis &AA) { Instruction *DefInst = MD->getMemoryInst(); assert(DefInst && "Defining instruction not actually an instruction"); ImmutableCallSite UseCS(UseInst); @@ -245,16 +256,19 @@ if (const IntrinsicInst *II = dyn_cast(DefInst)) { // These intrinsics will show up as affecting memory, but they are just // markers. + bool checkIfMustAlias; switch (II->getIntrinsicID()) { case Intrinsic::lifetime_start: if (UseCS) - return false; - return AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), UseLoc); + return {false, false}; + checkIfMustAlias = + AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), UseLoc); + return {checkIfMustAlias, checkIfMustAlias}; case Intrinsic::lifetime_end: case Intrinsic::invariant_start: case Intrinsic::invariant_end: case Intrinsic::assume: - return false; + return {false, false}; default: break; } @@ -262,28 +276,38 @@ if (UseCS) { ModRefInfo I = AA.getModRefInfo(DefInst, UseCS); - return I != MRI_NoModRef; + return {I != MRI_NoModRef, false}; } if (auto *DefLoad = dyn_cast(DefInst)) { if (auto *UseLoad = dyn_cast(UseInst)) { switch (getLoadReorderability(UseLoad, DefLoad)) { case Reorderability::Always: - return false; + return {false, false}; case Reorderability::Never: - return true; + return {true, false}; case Reorderability::IfNoAlias: - return !AA.isNoAlias(UseLoc, MemoryLocation::get(DefLoad)); + AliasResult AResult = AA.alias(MemoryLocation::get(DefLoad), UseLoc); + return {AResult != NoAlias, AResult == MustAlias}; } } } - return AA.getModRefInfo(DefInst, UseLoc) & MRI_Mod; -} - -static bool instructionClobbersQuery(MemoryDef *MD, const MemoryUseOrDef *MU, - const MemoryLocOrCall &UseMLOC, - AliasAnalysis &AA) { + // FIXME: avoid calling AA twice here. + Optional DefLoc = MemoryLocation::getOrNone(DefInst); + if (DefLoc == None) + return {(bool)(AA.getModRefInfo(DefInst, UseLoc) & MRI_Mod), false}; + // IsClobber = if location is modified, not AResult != NoAlias; + bool IsClobber = AA.getModRefInfo(DefInst, UseLoc) & MRI_Mod; + if (!IsClobber) + return {false, false}; + return {true, AA.isMustAlias(DefLoc.getValue(), UseLoc)}; +} + +static ClobberAlias instructionClobbersQuery(MemoryDef *MD, + const MemoryUseOrDef *MU, + const MemoryLocOrCall &UseMLOC, + AliasAnalysis &AA) { // FIXME: This is a temporary hack to allow a single instructionClobbersQuery // to exist while MemoryLocOrCall is pushed through places. if (UseMLOC.IsCall) @@ -296,7 +320,7 @@ // Return true when MD may alias MU, return false otherwise. bool MemorySSAUtil::defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU, AliasAnalysis &AA) { - return instructionClobbersQuery(MD, MU, MemoryLocOrCall(MU), AA); + return instructionClobbersQuery(MD, MU, MemoryLocOrCall(MU), AA).IsClobber; } namespace { @@ -311,6 +335,7 @@ const Instruction *Inst = nullptr; // The MemoryAccess we actually got called with, used to test local domination const MemoryAccess *OriginalAccess = nullptr; + bool IsMustAlias = false; UpwardsMemoryQuery() = default; @@ -394,9 +419,15 @@ // // Also, note that this can't be hoisted out of the `Worklist` loop, // since MD may only act as a clobber for 1 of N MemoryLocations. - FoundClobber = - FoundClobber || MSSA.isLiveOnEntryDef(MD) || - instructionClobbersQuery(MD, MAP.second, Query.Inst, AA); + FoundClobber = FoundClobber || MSSA.isLiveOnEntryDef(MD); + if (!FoundClobber) { + ClobberAlias CA = + instructionClobbersQuery(MD, MAP.second, Query.Inst, AA); + if (CA.IsClobber) { + FoundClobber = true; + // Not used: CA.IsMustAlias; + } + } } break; } @@ -406,7 +437,8 @@ if (auto *MD = dyn_cast(MA)) { (void)MD; - assert(!instructionClobbersQuery(MD, MAP.second, Query.Inst, AA) && + assert(!instructionClobbersQuery(MD, MAP.second, Query.Inst, AA) + .IsClobber && "Found clobber before reaching ClobberAt!"); continue; } @@ -476,9 +508,10 @@ /// Result of calling walkToPhiOrClobber. struct UpwardsWalkResult { /// The "Result" of the walk. Either a clobber, the last thing we walked, or - /// both. + /// both. Include alias info when clobber found. MemoryAccess *Result; bool IsKnownClobber; + bool IsMustAlias; }; /// Walk to the next Phi or Clobber in the def chain starting at Desc.Last. @@ -494,17 +527,23 @@ for (MemoryAccess *Current : def_chain(Desc.Last)) { Desc.Last = Current; if (Current == StopAt) - return {Current, false}; - - if (auto *MD = dyn_cast(Current)) - if (MSSA.isLiveOnEntryDef(MD) || - instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA)) - return {MD, true}; + return {Current, false, false}; + + if (auto *MD = dyn_cast(Current)) { + if (MSSA.isLiveOnEntryDef(MD)) + return {MD, true, true}; + else { + ClobberAlias CA = + instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA); + if (CA.IsClobber) + return {MD, true, CA.IsMustAlias}; + } + } } assert(isa(Desc.Last) && "Ended at a non-clobber that's not a phi?"); - return {Desc.Last, false}; + return {Desc.Last, false, false}; } void addSearches(MemoryPhi *Phi, SmallVectorImpl &PausedSearches, @@ -847,6 +886,7 @@ MemoryAccess *Result; if (WalkResult.IsKnownClobber) { Result = WalkResult.Result; + Q.IsMustAlias = WalkResult.IsMustAlias; } else { OptznResult OptRes = tryOptimizePhi(cast(FirstDesc.Last), Current, Q.StartingLoc); @@ -1115,6 +1155,7 @@ // This is where the last walk for this memory location ended. unsigned long LastKill; bool LastKillValid; + bool IsMustAlias; }; void optimizeUsesInBlock(const BasicBlock *, unsigned long &, unsigned long &, @@ -1174,7 +1215,7 @@ } if (isUseTriviallyOptimizableToLiveOnEntry(*AA, MU->getMemoryInst())) { - MU->setDefiningAccess(MSSA->getLiveOnEntryDef(), true); + MU->setDefiningAccess(MSSA->getLiveOnEntryDef(), true, true); continue; } @@ -1216,6 +1257,7 @@ if (!LocInfo.LastKillValid) { LocInfo.LastKill = VersionStack.size() - 1; LocInfo.LastKillValid = true; + LocInfo.IsMustAlias = false; } // At this point, we should have corrected last kill and LowerBound to be @@ -1259,24 +1301,34 @@ // Reset UpperBound to liveOnEntryDef's place in the stack UpperBound = 0; FoundClobberResult = true; + LocInfo.IsMustAlias = true; break; } - if (instructionClobbersQuery(MD, MU, UseMLOC, *AA)) { + ClobberAlias CA = instructionClobbersQuery(MD, MU, UseMLOC, *AA); + if (CA.IsClobber) { FoundClobberResult = true; + LocInfo.IsMustAlias = CA.IsMustAlias; break; } --UpperBound; } + + // Note: Phis always have IsMustAlias set to false ATM. + // At the end of this loop, UpperBound is either a clobber, or lower bound // PHI walking may cause it to be < LowerBound, and in fact, < LastKill. if (FoundClobberResult || UpperBound < LocInfo.LastKill) { - MU->setDefiningAccess(VersionStack[UpperBound], true); // We were last killed now by where we got to + if (MSSA->isLiveOnEntryDef(VersionStack[UpperBound])) + LocInfo.IsMustAlias = true; + MU->setDefiningAccess(VersionStack[UpperBound], true, + LocInfo.IsMustAlias); LocInfo.LastKill = UpperBound; } else { // Otherwise, we checked all the new ones, and now we know we can get to // LastKill. - MU->setDefiningAccess(VersionStack[LocInfo.LastKill], true); + MU->setDefiningAccess(VersionStack[LocInfo.LastKill], true, + LocInfo.IsMustAlias); } LocInfo.LowerBound = VersionStack.size() - 1; LocInfo.LowerBoundBlock = BB; @@ -2047,8 +2099,8 @@ return MA; // If this is an already optimized use or def, return the optimized result. - // Note: Currently, we do not store the optimized def result because we'd need - // a separate field, since we can't use it as the defining access. + // Note: Currently, we store the optimized def result in + // a separate field, since we can't use the defining access. if (auto *MUD = dyn_cast(StartingAccess)) if (MUD->isOptimized()) return MUD->getOptimized(); @@ -2063,8 +2115,10 @@ if (isUseTriviallyOptimizableToLiveOnEntry(*MSSA->AA, I)) { MemoryAccess *LiveOnEntry = MSSA->getLiveOnEntryDef(); - if (auto *MUD = dyn_cast(StartingAccess)) + if (auto *MUD = dyn_cast(StartingAccess)) { MUD->setOptimized(LiveOnEntry); + MUD->setDefiningToMustAlias(); + } return LiveOnEntry; } @@ -2073,16 +2127,25 @@ // At this point, DefiningAccess may be the live on entry def. // If it is, we will not get a better result. - if (MSSA->isLiveOnEntryDef(DefiningAccess)) + if (MSSA->isLiveOnEntryDef(DefiningAccess)) { + if (auto *MUD = dyn_cast(StartingAccess)) { + MUD->setOptimized(DefiningAccess); + MUD->setDefiningToMustAlias(); + } return DefiningAccess; + } MemoryAccess *Result = getClobberingMemoryAccess(DefiningAccess, Q); DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is "); DEBUG(dbgs() << *DefiningAccess << "\n"); DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is "); DEBUG(dbgs() << *Result << "\n"); - if (auto *MUD = dyn_cast(StartingAccess)) + + if (auto *MUD = dyn_cast(StartingAccess)) { MUD->setOptimized(Result); + if (MSSA->isLiveOnEntryDef(Result) || Q.IsMustAlias) + MUD->setDefiningToMustAlias(); + } return Result; } Index: unittests/Analysis/MemorySSA.cpp =================================================================== --- unittests/Analysis/MemorySSA.cpp +++ unittests/Analysis/MemorySSA.cpp @@ -909,3 +909,187 @@ Updater.insertUse(LoadAccess); MSSA.verifyMemorySSA(); } + +// Test Must alias for optimized uses +TEST_F(MemorySSATest, TestLoadMustAlias) { + F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false), + GlobalValue::ExternalLinkage, "F", &M); + B.SetInsertPoint(BasicBlock::Create(C, "", F)); + Type *Int8 = Type::getInt8Ty(C); + Value *AllocaA = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A"); + Value *AllocaB = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B"); + + B.CreateStore(ConstantInt::get(Int8, 1), AllocaB); + // Check load from LOE + LoadInst *LA1 = B.CreateLoad(AllocaA, ""); + // Check load alias cached for second load + LoadInst *LA2 = B.CreateLoad(AllocaA, ""); + + B.CreateStore(ConstantInt::get(Int8, 1), AllocaA); + // Check load from store/def + LoadInst *LA3 = B.CreateLoad(AllocaA, ""); + // Check load alias cached for second load + LoadInst *LA4 = B.CreateLoad(AllocaA, ""); + + setupAnalyses(); + MemorySSA &MSSA = *Analyses->MSSA; + + unsigned I = 0; + for (LoadInst *V : {LA1, LA2, LA3, LA4}) { + MemoryUse *MemUse = dyn_cast_or_null(MSSA.getMemoryAccess(V)); + EXPECT_EQ(MemUse->definingAccessMustAlias(), true) + << "Load " << I << " doesn't have the correct alias information"; + // EXPECT_EQ expands such that if we increment I above, it won't get + // incremented except when we try to print the error message. + ++I; + } +} + +// Test Must alias for optimized defs. +TEST_F(MemorySSATest, TestStoreMustAlias) { + F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false), + GlobalValue::ExternalLinkage, "F", &M); + B.SetInsertPoint(BasicBlock::Create(C, "", F)); + Type *Int8 = Type::getInt8Ty(C); + Value *AllocaA = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A"); + Value *AllocaB = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B"); + StoreInst *SA1 = B.CreateStore(ConstantInt::get(Int8, 1), AllocaA); + StoreInst *SB1 = B.CreateStore(ConstantInt::get(Int8, 1), AllocaB); + StoreInst *SA2 = B.CreateStore(ConstantInt::get(Int8, 2), AllocaA); + StoreInst *SB2 = B.CreateStore(ConstantInt::get(Int8, 2), AllocaB); + StoreInst *SA3 = B.CreateStore(ConstantInt::get(Int8, 3), AllocaA); + StoreInst *SB3 = B.CreateStore(ConstantInt::get(Int8, 3), AllocaB); + + setupAnalyses(); + MemorySSA &MSSA = *Analyses->MSSA; + MemorySSAWalker *Walker = Analyses->Walker; + + unsigned I = 0; + for (StoreInst *V : {SA1, SB1, SA2, SB2, SA3, SB3}) { + MemoryDef *MemDef = dyn_cast_or_null(MSSA.getMemoryAccess(V)); + EXPECT_EQ(MemDef->isOptimized(), false) + << "Store " << I << " is optimized from the start?"; + EXPECT_EQ(MemDef->definingAccessMustAlias(), false) + << "Store " << I + << " has correct alias information before being optimized?"; + if (V == SA1) + Walker->getClobberingMemoryAccess(V); + else { + MemoryAccess *Def = MemDef->getDefiningAccess(); + MemoryAccess *Clob = Walker->getClobberingMemoryAccess(V); + EXPECT_NE(Def, Clob) << "Store " << I + << " has Defining Access equal to Clobbering Access"; + } + EXPECT_EQ(MemDef->isOptimized(), true) + << "Store " << I << " was not optimized"; + EXPECT_EQ(MemDef->definingAccessMustAlias(), true) + << "Store " << I << " doesn't have the correct alias information"; + // EXPECT_EQ expands such that if we increment I above, it won't get + // incremented except when we try to print the error message. + ++I; + } +} + +// Test May alias for optimized uses. +TEST_F(MemorySSATest, TestLoadMayAlias) { + F = Function::Create(FunctionType::get(B.getVoidTy(), + {B.getInt8PtrTy(), B.getInt8PtrTy()}, + false), + GlobalValue::ExternalLinkage, "F", &M); + B.SetInsertPoint(BasicBlock::Create(C, "", F)); + Type *Int8 = Type::getInt8Ty(C); + auto *ArgIt = F->arg_begin(); + Argument *PointerA = &*ArgIt; + Argument *PointerB = &*(++ArgIt); + B.CreateStore(ConstantInt::get(Int8, 1), PointerB); + LoadInst *LA1 = B.CreateLoad(PointerA, ""); + B.CreateStore(ConstantInt::get(Int8, 0), PointerA); + LoadInst *LB1 = B.CreateLoad(PointerB, ""); + B.CreateStore(ConstantInt::get(Int8, 0), PointerA); + LoadInst *LA2 = B.CreateLoad(PointerA, ""); + B.CreateStore(ConstantInt::get(Int8, 0), PointerB); + LoadInst *LB2 = B.CreateLoad(PointerB, ""); + + setupAnalyses(); + MemorySSA &MSSA = *Analyses->MSSA; + + unsigned I = 0; + for (LoadInst *V : {LA1, LB1}) { + MemoryUse *MemUse = dyn_cast_or_null(MSSA.getMemoryAccess(V)); + EXPECT_EQ(MemUse->definingAccessMayAlias(), true) + << "Load " << I << " doesn't have the correct alias information"; + // EXPECT_EQ expands such that if we increment I above, it won't get + // incremented except when we try to print the error message. + ++I; + } + for (LoadInst *V : {LA2, LB2}) { + MemoryUse *MemUse = dyn_cast_or_null(MSSA.getMemoryAccess(V)); + EXPECT_EQ(MemUse->definingAccessMayAlias(), false) + << "Load " << I << " doesn't have the correct alias information"; + // EXPECT_EQ expands such that if we increment I above, it won't get + // incremented except when we try to print the error message. + ++I; + } +} + +// Test May alias for optimized defs. +TEST_F(MemorySSATest, TestStoreMayAlias) { + F = Function::Create(FunctionType::get(B.getVoidTy(), + {B.getInt8PtrTy(), B.getInt8PtrTy()}, + false), + GlobalValue::ExternalLinkage, "F", &M); + B.SetInsertPoint(BasicBlock::Create(C, "", F)); + Type *Int8 = Type::getInt8Ty(C); + auto *ArgIt = F->arg_begin(); + Argument *PointerA = &*ArgIt; + Argument *PointerB = &*(++ArgIt); + Value *AllocaC = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "C"); + // Store into arg1, must alias because it's LOE => must + StoreInst *SA1 = B.CreateStore(ConstantInt::get(Int8, 0), PointerA); + // Store into arg2, may alias store to arg1 => may + StoreInst *SB1 = B.CreateStore(ConstantInt::get(Int8, 1), PointerB); + // Store into aloca, no alias with args, so must alias LOE => must + StoreInst *SC1 = B.CreateStore(ConstantInt::get(Int8, 2), AllocaC); + // Store into arg1, may alias store to arg2 => may + StoreInst *SA2 = B.CreateStore(ConstantInt::get(Int8, 3), PointerA); + // Store into arg2, may alias store to arg1 => may + StoreInst *SB2 = B.CreateStore(ConstantInt::get(Int8, 4), PointerB); + // Store into aloca, no alias with args, so must alias SC1 => must + StoreInst *SC2 = B.CreateStore(ConstantInt::get(Int8, 5), AllocaC); + // Store into arg2, must alias store to arg2 => must + StoreInst *SB3 = B.CreateStore(ConstantInt::get(Int8, 6), PointerB); + + setupAnalyses(); + MemorySSA &MSSA = *Analyses->MSSA; + MemorySSAWalker *Walker = Analyses->Walker; + + unsigned I = 0; + for (StoreInst *V : {SA1, SB1, SC1, SA2, SB2, SC2, SB3}) { + MemoryDef *MemDef = dyn_cast_or_null(MSSA.getMemoryAccess(V)); + EXPECT_EQ(MemDef->isOptimized(), false) + << "Store " << I << " is optimized from the start?"; + EXPECT_EQ(MemDef->definingAccessMustAlias(), false) + << "Store " << I + << " has correct alias information before being optimized?"; + ++I; + } + + for (StoreInst *V : {SA1, SB1, SC1, SA2, SB2, SC2, SB3}) + Walker->getClobberingMemoryAccess(V); + + I = 0; + for (StoreInst *V : {SA1, SB1, SC1, SA2, SB2, SC2, SB3}) { + MemoryDef *MemDef = dyn_cast_or_null(MSSA.getMemoryAccess(V)); + EXPECT_EQ(MemDef->isOptimized(), true) + << "Store " << I << " was not optimized"; + if (I == 1 || I == 3 || I == 4) + EXPECT_EQ(MemDef->definingAccessMayAlias(), true) + << "Store " << I << " doesn't have the correct alias information"; + else + EXPECT_EQ(MemDef->definingAccessMustAlias(), true) + << "Store " << I << " doesn't have the correct alias information"; + // EXPECT_EQ expands such that if we increment I above, it won't get + // incremented except when we try to print the error message. + ++I; + } +}