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,26 @@ 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) { + // FIXME: is this redundant? + resetOptimized(); + 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 @@ -237,7 +237,7 @@ static bool instructionClobbersQuery(MemoryDef *MD, const MemoryLocation &UseLoc, const Instruction *UseInst, - AliasAnalysis &AA) { + AliasAnalysis &AA, bool &FoundMustAlias) { Instruction *DefInst = MD->getMemoryInst(); assert(DefInst && "Defining instruction not actually an instruction"); ImmutableCallSite UseCS(UseInst); @@ -245,11 +245,16 @@ if (const IntrinsicInst *II = dyn_cast(DefInst)) { // These intrinsics will show up as affecting memory, but they are just // markers. + bool isMustAlias; switch (II->getIntrinsicID()) { case Intrinsic::lifetime_start: if (UseCS) return false; - return AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), UseLoc); + isMustAlias = + AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), UseLoc); + if (isMustAlias) + FoundMustAlias = true; + return isMustAlias; case Intrinsic::lifetime_end: case Intrinsic::invariant_start: case Intrinsic::invariant_end: @@ -273,30 +278,44 @@ case Reorderability::Never: return true; case Reorderability::IfNoAlias: - return !AA.isNoAlias(UseLoc, MemoryLocation::get(DefLoad)); + AliasResult AResult = AA.alias(MemoryLocation::get(DefLoad), UseLoc); + if (AResult == MustAlias) + FoundMustAlias = true; + return AResult != NoAlias; } } } - return AA.getModRefInfo(DefInst, UseLoc) & MRI_Mod; + Optional DefLoc = MemoryLocation::getOrNone(DefInst); + if (DefLoc == None) + return AA.getModRefInfo(DefInst, UseLoc) & MRI_Mod; + else { + AliasResult AResult = AA.alias(DefLoc.getValue(), UseLoc); + if (AResult == MustAlias) + FoundMustAlias = true; + // Must return if location is modified, not AResult != NoAlias; + return AA.getModRefInfo(DefInst, UseLoc) & MRI_Mod; + } } static bool instructionClobbersQuery(MemoryDef *MD, const MemoryUseOrDef *MU, const MemoryLocOrCall &UseMLOC, - AliasAnalysis &AA) { + AliasAnalysis &AA, bool &FoundMustAlias) { // FIXME: This is a temporary hack to allow a single instructionClobbersQuery // to exist while MemoryLocOrCall is pushed through places. if (UseMLOC.IsCall) return instructionClobbersQuery(MD, MemoryLocation(), MU->getMemoryInst(), - AA); - return instructionClobbersQuery(MD, UseMLOC.getLoc(), MU->getMemoryInst(), - AA); + AA, FoundMustAlias); + return instructionClobbersQuery(MD, UseMLOC.getLoc(), MU->getMemoryInst(), AA, + FoundMustAlias); } // 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); + bool FoundMustAlias; + return instructionClobbersQuery(MD, MU, MemoryLocOrCall(MU), AA, + FoundMustAlias); } namespace { @@ -311,6 +330,7 @@ const Instruction *Inst = nullptr; // The MemoryAccess we actually got called with, used to test local domination const MemoryAccess *OriginalAccess = nullptr; + bool FoundMustAlias = false; UpwardsMemoryQuery() = default; @@ -374,6 +394,7 @@ } bool FoundClobber = false; + bool FoundMustAlias; DenseSet VisitedPhis; SmallVector Worklist; Worklist.emplace_back(Start, StartLoc); @@ -394,9 +415,9 @@ // // 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) || + instructionClobbersQuery(MD, MAP.second, Query.Inst, + AA, FoundMustAlias); } break; } @@ -406,7 +427,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, + FoundMustAlias) && "Found clobber before reaching ClobberAt!"); continue; } @@ -476,9 +498,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 FoundMustAlias; }; /// Walk to the next Phi or Clobber in the def chain starting at Desc.Last. @@ -491,20 +514,22 @@ const MemoryAccess *StopAt = nullptr) const { assert(!isa(Desc.Last) && "Uses don't exist in my world"); + bool FoundMustAlias = false; for (MemoryAccess *Current : def_chain(Desc.Last)) { Desc.Last = Current; if (Current == StopAt) - return {Current, false}; + return {Current, false, FoundMustAlias}; if (auto *MD = dyn_cast(Current)) if (MSSA.isLiveOnEntryDef(MD) || - instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA)) - return {MD, true}; + instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA, + FoundMustAlias)) + return {MD, true, FoundMustAlias}; } 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 +872,7 @@ MemoryAccess *Result; if (WalkResult.IsKnownClobber) { Result = WalkResult.Result; + Q.FoundMustAlias = WalkResult.FoundMustAlias; } else { OptznResult OptRes = tryOptimizePhi(cast(FirstDesc.Last), Current, Q.StartingLoc); @@ -1115,6 +1141,7 @@ // This is where the last walk for this memory location ended. unsigned long LastKill; bool LastKillValid; + bool MustAlias; }; void optimizeUsesInBlock(const BasicBlock *, unsigned long &, unsigned long &, @@ -1174,7 +1201,7 @@ } if (isUseTriviallyOptimizableToLiveOnEntry(*AA, MU->getMemoryInst())) { - MU->setDefiningAccess(MSSA->getLiveOnEntryDef(), true); + MU->setDefiningAccess(MSSA->getLiveOnEntryDef(), true, true); continue; } @@ -1216,6 +1243,7 @@ if (!LocInfo.LastKillValid) { LocInfo.LastKill = VersionStack.size() - 1; LocInfo.LastKillValid = true; + LocInfo.MustAlias = false; } // At this point, we should have corrected last kill and LowerBound to be @@ -1259,24 +1287,31 @@ // Reset UpperBound to liveOnEntryDef's place in the stack UpperBound = 0; FoundClobberResult = true; + LocInfo.MustAlias = true; break; } - if (instructionClobbersQuery(MD, MU, UseMLOC, *AA)) { + if (instructionClobbersQuery(MD, MU, UseMLOC, *AA, LocInfo.MustAlias)) { FoundClobberResult = true; break; } --UpperBound; } + + // Note: Phis always have MustAlias 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.MustAlias = true; + MU->setDefiningAccess(VersionStack[UpperBound], true, LocInfo.MustAlias); 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.MustAlias); } LocInfo.LowerBound = VersionStack.size() - 1; LocInfo.LowerBoundBlock = BB; @@ -2047,8 +2082,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 +2098,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 +2110,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.FoundMustAlias) + 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; + } +}