Index: llvm/include/llvm/Transforms/Scalar/GVN.h =================================================================== --- llvm/include/llvm/Transforms/Scalar/GVN.h +++ llvm/include/llvm/Transforms/Scalar/GVN.h @@ -35,6 +35,7 @@ class AssumeInst; class AssumptionCache; class BasicBlock; +class BatchAAResults; class BranchInst; class CallInst; class ExtractValueInst; @@ -45,7 +46,9 @@ class LoadInst; class LoopInfo; class MemDepResult; +class MemoryAccess; class MemoryDependenceResults; +class MemoryLocation; class MemorySSA; class MemorySSAUpdater; class NonLocalDepResult; @@ -210,6 +213,7 @@ ~ValueTable(); ValueTable &operator=(const ValueTable &Arg); + uint32_t lookupOrAdd(MemoryAccess *); uint32_t lookupOrAdd(Value *V); uint32_t lookup(Value *V, bool Verify = true) const; uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, @@ -242,6 +246,7 @@ OptimizationRemarkEmitter *ORE = nullptr; ImplicitControlFlowTracking *ICF = nullptr; LoopInfo *LI = nullptr; + AAResults *AA = nullptr; MemorySSAUpdater *MSSAU = nullptr; ValueTable VN; @@ -328,21 +333,59 @@ // List of critical edges to be split between iterations. SmallVector, 4> toSplit; + enum class DepKind { + Other = 0, // Unknown value + Def, // Exaclty overlapping locations. + Clobber, // Reaching value superset of needed bits. + }; + + struct ReachingMemVal { + DepKind Kind; + BasicBlock *Block; + const Value *Addr; + Instruction *Inst; + int32_t Offset; + + static ReachingMemVal getUnknown(BasicBlock *BB, const Value *Addr, + Instruction *Inst = nullptr) { + return {DepKind::Other, BB, Addr, Inst, -1}; + } + + static ReachingMemVal getDef(const Value *Addr, Instruction *Inst) { + return {DepKind::Def, Inst->getParent(), Addr, Inst, -1}; + } + + static ReachingMemVal getClobber(const Value *Addr, Instruction *Inst, + int32_t Offset = -1) { + return {DepKind::Clobber, Inst->getParent(), Addr, Inst, Offset}; + } + }; + + Optional findReachingValueForLoadInBlock( + const MemoryLocation &Loc, bool IsInvariantload, BasicBlock *BB, + Instruction *DomLower, Instruction *DomUpper, MemoryAccess *ClobberMA, + MemorySSA &MSSA, BatchAAResults &AA); + + bool findReachingValuesForLoad(LoadInst *Inst, MemorySSA &MSSA, AAResults &AA, + SmallVectorImpl &Values); + // Helper functions of redundant load elimination bool processLoad(LoadInst *L); bool processNonLocalLoad(LoadInst *L); + bool processNonLocalLoad(LoadInst *L, SmallVectorImpl &Deps); bool processAssumeIntrinsic(AssumeInst *II); /// Given a local dependency (Def or Clobber) determine if a value is /// available for the load. Returns true if an value is known to be /// available and populates Res. Returns false otherwise. - bool AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo, + bool AnalyzeLoadAvailability(LoadInst *Load, const ReachingMemVal &Dep, Value *Address, gvn::AvailableValue &Res); /// Given a list of non-local dependencies, determine if a value is /// available for the load in each specified block. If it is, add it to /// ValuesPerBlock. If not, add it to UnavailableBlocks. - void AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps, + void AnalyzeLoadAvailability(LoadInst *Load, + SmallVectorImpl &Deps, AvailValInBlkVect &ValuesPerBlock, UnavailBlkVect &UnavailableBlocks); Index: llvm/lib/Transforms/Scalar/GVN.cpp =================================================================== --- llvm/lib/Transforms/Scalar/GVN.cpp +++ llvm/lib/Transforms/Scalar/GVN.cpp @@ -111,6 +111,11 @@ static cl::opt GVNEnableMemDep("enable-gvn-memdep", cl::init(true)); static cl::opt GVNEnableMemorySSA("enable-gvn-memoryssa", cl::init(false)); +static cl::opt BlockScanLimit( + "gvn-block-scan-limit", cl::Hidden, cl::init(100), + cl::desc("The number of memory accesses to scan in a block in reaching " + "memory values analysis (default = 100)")); + static cl::opt MaxNumDeps( "gvn-max-num-deps", cl::Hidden, cl::init(100), cl::desc("Max number of dependences to attempt Load PRE (default = 100)")); @@ -481,15 +486,7 @@ assert(MSSA && "Function should not be called without MemorySSA"); assert(MSSA->getMemoryAccess(I) && "Instruction does not access memory"); MemoryAccess *MA = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(I); - - uint32_t N = 0; - if (isa(MA)) - N = lookupOrAdd(MA->getBlock()); - else if (MSSA->isLiveOnEntryDef(MA)) - N = lookupOrAdd(&I->getFunction()->getEntryBlock()); - else - N = lookupOrAdd(cast(MA)->getMemoryInst()); - E.varargs.push_back(N); + E.varargs.push_back(lookupOrAdd(MA)); } uint32_t GVNPass::ValueTable::lookupOrAddCall(CallInst *C) { @@ -632,6 +629,12 @@ return valueNumbering.count(V) != 0; } +uint32_t GVNPass::ValueTable::lookupOrAdd(MemoryAccess *MA) { + return MSSA->isLiveOnEntryDef(MA) || isa(MA) + ? lookupOrAdd(MA->getBlock()) + : lookupOrAdd(cast(MA)->getMemoryInst()); +} + /// lookup_or_add - Returns the value number for the specified value, assigning /// it a new number if it did not have one before. uint32_t GVNPass::ValueTable::lookupOrAdd(Value *V) { @@ -1081,7 +1084,8 @@ // tracks. It is potentially possible to remove the load from the table, // but then there all of the operations based on it would need to be // rehashed. Just leave the dead load around. - gvn.getMemDep().removeInstruction(CoercedLoad); + if (gvn.isMemDepEnabled()) + gvn.getMemDep().removeInstruction(CoercedLoad); LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: " << Offset << " " << *getCoercedLoadValue() << '\n' << *Res << '\n' @@ -1131,7 +1135,7 @@ /// Try to locate the three instruction involved in a missed /// load-elimination case that is due to an intervening store. -static void reportMayClobberedLoad(LoadInst *Load, MemDepResult DepInfo, +static void reportMayClobberedLoad(LoadInst *Load, Instruction *DepInst, DominatorTree *DT, OptimizationRemarkEmitter *ORE) { using namespace ore; @@ -1186,7 +1190,7 @@ if (OtherAccess) R << " in favor of " << NV("OtherAccess", OtherAccess); - R << " because it is clobbered by " << NV("ClobberedBy", DepInfo.getInst()); + R << " because it is clobbered by " << NV("ClobberedBy", DepInst); ORE->emit(R); } @@ -1226,9 +1230,9 @@ return AvailableValue::getSelect(Sel); } -bool GVNPass::AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo, +bool GVNPass::AnalyzeLoadAvailability(LoadInst *Load, const ReachingMemVal &Dep, Value *Address, AvailableValue &Res) { - if (!DepInfo.isDef() && !DepInfo.isClobber()) { + if (Dep.Kind == DepKind::Other) { assert(isa(Address)); if (auto R = tryToConvertLoadOfPtrSelect( Load->getParent(), Load->getIterator(), Address, Load->getType(), @@ -1239,14 +1243,14 @@ return false; } - assert((DepInfo.isDef() || DepInfo.isClobber()) && + assert((Dep.Kind == DepKind::Def || Dep.Kind == DepKind::Clobber) && "expected a local dependence"); assert(Load->isUnordered() && "rules below are incorrect for ordered access"); const DataLayout &DL = Load->getModule()->getDataLayout(); - Instruction *DepInst = DepInfo.getInst(); - if (DepInfo.isClobber()) { + Instruction *DepInst = Dep.Inst; + if (Dep.Kind == DepKind::Clobber) { // If the dependence is to a store that writes to a superset of the bits // read by the load, we can extract the bits we need for the load from the // stored value. @@ -1273,14 +1277,18 @@ if (DepLoad != Load && Address && Load->isAtomic() <= DepLoad->isAtomic()) { Type *LoadType = Load->getType(); - int Offset = -1; - - // If MD reported clobber, check it was nested. - if (DepInfo.isClobber() && - canCoerceMustAliasedValueToLoad(DepLoad, LoadType, DL)) { - const auto ClobberOff = MD->getClobberOffset(DepLoad); - // GVN has no deal with a negative offset. - Offset = (ClobberOff == None || *ClobberOff < 0) ? -1 : *ClobberOff; + int Offset = Dep.Offset; + if (MD && !MSSAU) { + // If MD reported clobber, check it was nested. + if (canCoerceMustAliasedValueToLoad(DepLoad, LoadType, DL)) { + const auto ClobberOff = MD->getClobberOffset(DepLoad); + // GVN has no deal with a negative offset. + Offset = (ClobberOff == None || *ClobberOff < 0) ? -1 : *ClobberOff; + } + } else { + if (!canCoerceMustAliasedValueToLoad(DepLoad, LoadType, DL) || + Offset < 0) + Offset = -1; } if (Offset == -1) Offset = @@ -1311,11 +1319,11 @@ dbgs() << "GVN: load "; Load->printAsOperand(dbgs()); dbgs() << " is clobbered by " << *DepInst << '\n';); if (ORE->allowExtraAnalysis(DEBUG_TYPE)) - reportMayClobberedLoad(Load, DepInfo, DT, ORE); + reportMayClobberedLoad(Load, DepInst, DT, ORE); return false; } - assert(DepInfo.isDef() && "follows from above"); + assert(Dep.Kind == DepKind::Def && "follows from above"); // Loading the alloca -> undef. // Loading immediately after lifetime begin -> undef. @@ -1369,7 +1377,8 @@ return false; } -void GVNPass::AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps, +void GVNPass::AnalyzeLoadAvailability(LoadInst *Load, + SmallVectorImpl &Deps, AvailValInBlkVect &ValuesPerBlock, UnavailBlkVect &UnavailableBlocks) { // Filter out useless results (non-locals, etc). Keep track of the blocks @@ -1378,22 +1387,20 @@ // that could potentially clobber the load). unsigned NumDeps = Deps.size(); for (unsigned i = 0, e = NumDeps; i != e; ++i) { - BasicBlock *DepBB = Deps[i].getBB(); - MemDepResult DepInfo = Deps[i].getResult(); - + const auto &Dep = Deps[i]; + BasicBlock *DepBB = Dep.Block; if (DeadBlocks.count(DepBB)) { // Dead dependent mem-op disguise as a load evaluating the same value // as the load in question. - ValuesPerBlock.push_back(AvailableValueInBlock::getUndef(DepBB)); + ValuesPerBlock.push_back(AvailableValueInBlock::getUndef(Dep.Block)); continue; } // The address being loaded in this non-local block may not be the same as // the pointer operand of the load if PHI translation occurs. Make sure // to consider the right address. - Value *Address = Deps[i].getAddress(); - - if (!DepInfo.isDef() && !DepInfo.isClobber()) { + Value *Address = const_cast(Deps[i].Addr); + if (Dep.Kind == DepKind::Other) { if (auto R = tryToConvertLoadOfPtrSelect( DepBB, DepBB->end(), Address, Load->getType(), getDominatorTree(), getAliasAnalysis())) { @@ -1406,7 +1413,7 @@ } AvailableValue AV; - if (AnalyzeLoadAvailability(Load, DepInfo, Address, AV)) { + if (AnalyzeLoadAvailability(Load, Dep, Address, AV)) { // subtlety: because we know this was a non-local dependency, we know // it's safe to materialize anywhere between the instruction within // DepInfo and the end of it's block. @@ -1475,7 +1482,8 @@ // Add the newly created load. ValuesPerBlock.push_back( AvailableValueInBlock::get(UnavailableBlock, NewLoad)); - MD->invalidateCachedPointerInfo(LoadPtr); + if (MD) + MD->invalidateCachedPointerInfo(LoadPtr); LLVM_DEBUG(dbgs() << "GVN INSERTED " << *NewLoad << '\n'); } @@ -1486,7 +1494,7 @@ V->takeName(Load); if (Instruction *I = dyn_cast(V)) I->setDebugLoc(Load->getDebugLoc()); - if (V->getType()->isPtrOrPtrVectorTy()) + if (MD && V->getType()->isPtrOrPtrVectorTy()) MD->invalidateCachedPointerInfo(V); markInstructionForDeletion(Load); ORE->emit([&]() { @@ -1837,7 +1845,7 @@ Attribute::SanitizeHWAddress)) return false; - // Step 1: Find the non-local dependencies of the load. + // Find the non-local dependencies of the load. LoadDepVect Deps; MD->getNonLocalPointerDependency(Load, Deps); @@ -1848,10 +1856,26 @@ if (NumDeps > MaxNumDeps) return false; + SmallVector MemVals; + for (const NonLocalDepResult &Dep : Deps) { + Value *Address = Dep.getAddress(); + BasicBlock *BB = Dep.getBB(); + Instruction *Inst = Dep.getResult().getInst(); + if (Dep.getResult().isClobber()) + MemVals.emplace_back(ReachingMemVal::getClobber(Address, Inst)); + else if (Dep.getResult().isDef()) + MemVals.emplace_back(ReachingMemVal::getDef(Address, Inst)); + else + MemVals.emplace_back(ReachingMemVal::getUnknown(BB, Address, Inst)); + } + return processNonLocalLoad(Load, MemVals); +} + +bool GVNPass ::processNonLocalLoad(LoadInst *Load, + SmallVectorImpl &Deps) { // If we had a phi translation failure, we'll have a single entry which is a // clobber in the current block. Reject this early. - if (NumDeps == 1 && - !Deps[0].getResult().isDef() && !Deps[0].getResult().isClobber()) { + if (Deps.size() == 1 && Deps[0].Kind == DepKind::Other) { LLVM_DEBUG(dbgs() << "GVN: non-local load "; Load->printAsOperand(dbgs()); dbgs() << " has unknown dependencies\n";); return false; @@ -1896,7 +1920,7 @@ // to propagate Load's DebugLoc because Load may not post-dominate I. if (Load->getDebugLoc() && Load->getParent() == I->getParent()) I->setDebugLoc(Load->getDebugLoc()); - if (V->getType()->isPtrOrPtrVectorTy()) + if (MD && V->getType()->isPtrOrPtrVectorTy()) MD->invalidateCachedPointerInfo(V); markInstructionForDeletion(Load); ++NumGVNLoad; @@ -2120,10 +2144,452 @@ I->replaceAllUsesWith(Repl); } +Optional GVNPass::findReachingValueForLoadInBlock( + const MemoryLocation &Loc, bool IsInvariantLoad, BasicBlock *BB, + Instruction *DomLower, Instruction *DomUpper, MemoryAccess *ClobberMA, + MemorySSA &MSSA, BatchAAResults &AA) { + + auto updateChoice = [&](ReachingMemVal &Choice, AliasResult &AR, + Instruction *Candidate) { + // TODO: Worth choosing between exact or partial overlap ? + if (Choice.Kind == DepKind::Other) + Choice.Inst = Candidate; + else if (MSSA.locallyDominates(MSSA.getMemoryAccess(Choice.Inst), + MSSA.getMemoryAccess(Candidate))) + Choice.Inst = Candidate; + else + return; + + if (AR == AliasResult::PartialAlias) { + Choice.Kind = DepKind::Clobber; + Choice.Offset = AR.getOffset(); + } else { + Choice.Kind = DepKind::Def; + Choice.Offset = -1; + } + Choice.Block = Candidate->getParent(); + }; + + // Lower bound is inclusive, upper bound is exclusive. + auto isBetweenBounds = [&](const MemoryUseOrDef *U) { + if (DomLower == nullptr && DomUpper == nullptr) + return true; + MemoryAccess *Lower = + DomLower == nullptr ? nullptr : MSSA.getMemoryAccess(DomLower); + if (Lower != nullptr && !MSSA.locallyDominates(Lower, U)) + return false; + MemoryAccess *Upper = + DomUpper == nullptr ? nullptr : MSSA.getMemoryAccess(DomUpper); + return Upper == nullptr || (U != Upper && MSSA.locallyDominates(U, Upper)); + }; + + // Return the memory location, accessed by the [masked]load/store instruction + // `I`, if the instruction could potentially provide a useful value for + // elimiating the load. + auto getLoadStoreLocationIfInteresting = + [&](Instruction *I, + bool StoresAreInteresting) -> Optional { + if (auto *L = dyn_cast(I)) + return MemoryLocation::get(L); + + if (auto *II = dyn_cast(I)) { + if (II->getIntrinsicID() == Intrinsic::masked_load) + return MemoryLocation::getForArgument(II, 0, TLI); + } + + if (!StoresAreInteresting) + return None; + + if (auto *S = dyn_cast(I)) + return MemoryLocation::get(S); + + if (auto *II = dyn_cast(I)) { + if (II->getIntrinsicID() == Intrinsic::masked_store) + return MemoryLocation::getForArgument(II, 1, TLI); + } + + return None; + }; + + // For all the memory accesses in the block. + const auto *MemAccessList = MSSA.getBlockAccesses(BB); + if (MemAccessList == nullptr) + return None; + auto ReachingVal = ReachingMemVal::getUnknown(BB, Loc.Ptr); + unsigned NumAccessesScanned = 0; + for (const MemoryAccess &MA : *MemAccessList) { + // We we spent too much time scanning the block, just give up and return + // an unknown value. + if (++NumAccessesScanned >= BlockScanLimit) + return ReachingMemVal::getUnknown(BB, Loc.Ptr); + + auto *UseOrDef = dyn_cast(&MA); + if (UseOrDef == nullptr) + continue; + + // We are interested only in loads here, and, in the case of invariant load, + // in the stores. + Instruction *I = UseOrDef->getMemoryInst(); + Optional M = + getLoadStoreLocationIfInteresting(I, IsInvariantLoad); + if (!M) + continue; + + // Skip if the use is not within the bounds. Additionally, the uses needs to + // be dominated by the clobbering memory access. + if (!isBetweenBounds(UseOrDef) || + (ClobberMA->getBlock() == BB && !MSSA.locallyDominates(ClobberMA, &MA))) + continue; + + AliasResult AR = AA.alias(*M, Loc); + // If the locations do not certainly alias, we cannot possibly infer the + // following load loads the same value. + if (AR == AliasResult::NoAlias || AR == AliasResult::MayAlias) + continue; + + // Locations partially overlap, but neither is a subset of the other, or the + // second location is before the first. + if (AR == AliasResult::PartialAlias && + (!AR.hasOffset() || AR.getOffset() < 0)) + continue; + + // Locations precisely overlap or the second accesses subset of the bits of + // the first. + updateChoice(ReachingVal, AR, I); + } + + // Found something. + if (ReachingVal.Kind != DepKind::Other) + return ReachingVal; + + // If the clobbering access is the entry memory state, continue the search + // into predecessors, unless the load is from a local object in which case + // return the allocation instruction. + if (MSSA.isLiveOnEntryDef(ClobberMA)) { + auto *Alloc = dyn_cast(getUnderlyingObject(Loc.Ptr)); + if (Alloc != nullptr && Alloc->getParent() == BB) + return ReachingMemVal::getDef(Loc.Ptr, const_cast(Alloc)); + + return None; + } + + // If the clobberring access is a MemoryPhi or in another block, go to + // predecessors. + if (ClobberMA->getBlock() != BB || isa(ClobberMA)) + return None; + + // Loads from "constant" memory can't be clobbered. + if (IsInvariantLoad || AA.pointsToConstantMemory(Loc)) + return None; + + Instruction *ClobberInst = cast(ClobberMA)->getMemoryInst(); + auto getOrdering = [](const Instruction *I) { + assert(isa(I) || isa(I)); + if (const auto *L = dyn_cast(I)) + return L->getOrdering(); + return cast(I)->getOrdering(); + }; + + // Check if the clobbering access is a load or a store that we can reuse. + if (Optional M = + getLoadStoreLocationIfInteresting(ClobberInst, true)) { + AliasResult AR = AA.alias(*M, Loc); + if (AR == AliasResult::MustAlias) + return ReachingMemVal::getDef(Loc.Ptr, ClobberInst); + + if (AR == AliasResult::NoAlias) { + // If the locations do not alias we may still be able to skip over the + // cloberrring instuction, even if it is atomic. + + // The original load is either non-atomic or unordered. We can reorder + // these across non-atomic, unordered or monotonic loads or across any + // store. + if (!ClobberInst->isAtomic() || + !isStrongerThan(getOrdering(ClobberInst), + AtomicOrdering::Monotonic) || + isa(ClobberInst)) + return None; + return ReachingMemVal::getClobber(Loc.Ptr, ClobberInst); + } + + // Skip over volatile loads (the orignal load is non-volatile, non-atomic). + if (!ClobberInst->isAtomic() && isa(ClobberInst)) + return None; + + if (AR == AliasResult::MayAlias || + (AR == AliasResult::PartialAlias && + (!AR.hasOffset() || AR.getOffset() < 0))) + return ReachingMemVal::getClobber(Loc.Ptr, ClobberInst); + + // The only option left is a store of the superset of the required bits. + assert(AR == AliasResult::PartialAlias && AR.hasOffset() && + AR.getOffset() > 0 && "Follows from the conditions above"); + return ReachingMemVal::getClobber(Loc.Ptr, ClobberInst, AR.getOffset()); + } + + if (const IntrinsicInst *II = dyn_cast(ClobberInst)) { + if (isa(II)) + return None; + if (II->getIntrinsicID() == Intrinsic::lifetime_start) { + MemoryLocation M = MemoryLocation::getForArgument(II, 1, TLI); + if (AA.isMustAlias(M, Loc)) + return ReachingMemVal::getDef(Loc.Ptr, ClobberInst); + return None; + } + } + + // If we are at a malloc-like function call, we can turn the load into `undef` + // or zero. + if (isNoAliasCall(ClobberInst)) { + const Value *Obj = getUnderlyingObject(Loc.Ptr); + if (Obj == ClobberInst || AA.isMustAlias(ClobberInst, Loc.Ptr)) + return ReachingMemVal::getDef(Loc.Ptr, ClobberInst); + } + + // Can reorder loads across a release fence. + if (auto *Fence = dyn_cast(ClobberInst)) { + if (Fence->getOrdering() == AtomicOrdering::Release) + return None; + } + + // See if the clobber instruction (e.g. a call) may modify the location. + ModRefInfo MR = AA.getModRefInfo(ClobberInst, Loc); + // If modification is possible, analyse deeper, to exclude accesses to + // non-escaping local allocations. + if (isModAndRefSet(MR)) + MR = AA.callCapturesBefore(ClobberInst, Loc, DT); + MR = clearMust(MR); + if (MR == ModRefInfo::NoModRef || MR == ModRefInfo::Ref) + return None; + + // Conservatively return unknown value for the load. + return ReachingMemVal::getClobber(Loc.Ptr, ClobberInst); +} + +static Instruction *findInvariantGroupValue(LoadInst *L, DominatorTree &DT) { + // We consider bitcasts and zero GEPs to be the same pointer value. Start by + // stripping bitcasts and zero GEPs, then we will recursively look at loads + // and stores through bitcasts and zero GEPs. + Value *PointerOperand = L->getPointerOperand()->stripPointerCasts(); + + // It's not safe to walk the use list of a global value because function + // passes aren't allowed to look outside their functions. + // FIXME: this could be fixed by filtering instructions from outside of + // current function. + if (isa(PointerOperand)) + return nullptr; + + // Queue to process all pointers that are equivalent to load operand. + SmallVector PointerUsesQueue; + PointerUsesQueue.push_back(PointerOperand); + + Instruction *MostDominatingInstruction = L; + + // FIXME: This loop is O(n^2) because dominates can be O(n) and in worst case + // we will see all the instructions. + while (!PointerUsesQueue.empty()) { + Value *Ptr = PointerUsesQueue.pop_back_val(); + assert(Ptr && !isa(Ptr) && + "Null or GlobalValue should not be inserted"); + + for (User *Us : Ptr->users()) { + auto *U = dyn_cast(Us); + if (!U || U == L || !DT.dominates(U, MostDominatingInstruction)) + continue; + + // Add bitcasts and zero GEPs to queue. + if (isa(U)) { + PointerUsesQueue.push_back(U); + continue; + } + if (auto *GEP = dyn_cast(U)) { + if (GEP->hasAllZeroIndices()) + PointerUsesQueue.push_back(U); + continue; + } + + // If we hit a load/store with an invariant.group metadata and the same + // pointer operand, we can assume that value pointed to by the pointer + // operand didn't change. + if (U->hasMetadata(LLVMContext::MD_invariant_group) && + getLoadStorePointerOperand(U) == Ptr && !U->isVolatile()) { + MostDominatingInstruction = U; + } + } + } + return MostDominatingInstruction == L ? nullptr : MostDominatingInstruction; +} + +bool GVNPass::findReachingValuesForLoad( + LoadInst *L, MemorySSA &MSSA, AAResults &AA, + SmallVectorImpl &Values) { + + struct WorkItem { + WorkItem(BasicBlock *BB, MemoryAccess *ClobberMA, const PHITransAddr &Addr, + Instruction *DomLower, Instruction *DomUpper) + : BB(BB), ClobberMA(ClobberMA), Addr(Addr), DomLower(DomLower), + DomUpper(DomUpper) {} + BasicBlock *BB; + MemoryAccess *ClobberMA; + PHITransAddr Addr; + Instruction *DomLower; + Instruction *DomUpper; + }; + SmallVector Worklist; + + // Keep the set of visited blocks, together with the pointer they were visited + // with. Due to phi-translation, it is possible that we come to a block with a + // different pointer in which case we set the block we're coming from (a + // successor of the visited block) as cloberring the memory location in an + // unknown way. + DenseMap Visited; + + auto collectPredecessors = [&](BasicBlock *BB, const PHITransAddr &Addr, + MemoryAccess *ClobberMA, + SmallVectorImpl &Worklist) -> bool { + if (Addr.NeedsPHITranslationFromBlock(BB) && + !Addr.IsPotentiallyPHITranslatable()) + return false; + auto *MPhi = + ClobberMA->getBlock() == BB ? dyn_cast(ClobberMA) : nullptr; + for (BasicBlock *Pred : predecessors(BB)) { + if (!DT->isReachableFromEntry(Pred)) + continue; + PHITransAddr TransAddr = Addr; + if (TransAddr.NeedsPHITranslationFromBlock(BB)) + TransAddr.PHITranslateValue(BB, Pred, DT, false); + auto It = Visited.find(Pred); + if (It != Visited.end()) { + // If we reach a visited block with a different address, set the + // current block as clobberring the memory location in an unknown way + // (by returning false). + if (It->second != TransAddr.getAddr()) { + for (const auto &T : Worklist) + Visited.erase(T.BB); + return false; + } + // Otherwise just stop the traversal. + continue; + } + Visited.insert({Pred, TransAddr.getAddr()}); + Worklist.emplace_back( + Pred, + MPhi == nullptr ? ClobberMA : MPhi->getIncomingValueForBlock(Pred), + TransAddr, Pred == L->getParent() ? L : nullptr, nullptr); + } + return true; + }; + + const DataLayout &DL = L->getModule()->getDataLayout(); + auto Loc = MemoryLocation::get(L); + BasicBlock *StartBlock = L->getParent(); + bool IsInvariantLoad = L->hasMetadata(LLVMContext::MD_invariant_load); + bool HasSanitizer = + StartBlock->getParent()->hasFnAttribute(Attribute::SanitizeAddress) || + StartBlock->getParent()->hasFnAttribute(Attribute::SanitizeHWAddress); + BatchAAResults BatchAA(AA); + + // Traverse the CFG backwards from the block containing the load instruction, + // looking for instructions, from which we can deduce what value the load + // would, well, load. Do a depth-first search with a worklist. Blocks are + // marked as visited at the time of adding them to the worklist. That allows + // as to record a block as cloberring the memory location whenever we try to + // continue the search into a predecessor block for which the phi-translation + // fails or yields a different pointer. Once exception is the initial block, + // which is marked visited not when we start the search (next statement + // below), but when we come to it for a second time via a backedge. + Worklist.emplace_back(StartBlock, + MSSA.getMemoryAccess(L)->getDefiningAccess(), + PHITransAddr(L->getPointerOperand(), DL, AC), nullptr, + L); + while (!Worklist.empty()) { + // If we have found too many blocks so far this load isn't worth worrying + // about. Optimizing it will be too expensive. + if (Values.size() > MaxNumDeps) + return false; + + WorkItem Item = Worklist.back(); + Worklist.pop_back(); + + assert((Item.BB == StartBlock && Item.DomLower == nullptr) || + Visited.count(Item.BB) && + "All block in the worklist must be marked as visited (except " + "the very first block)"); + assert( + Item.Addr.getAddr() != nullptr && + "Blocks with failed phi-translation must not appear on the worklist"); + + // If we have found a definite answer (a reusable value or unknown), + // continue with the next block in the worklist. + if (Optional R = findReachingValueForLoadInBlock( + Loc.getWithNewPtr(Item.Addr.getAddr()), IsInvariantLoad, Item.BB, + Item.DomLower, Item.DomUpper, Item.ClobberMA, MSSA, BatchAA)) { + if (R->Kind != DepKind::Def && + L->hasMetadata(LLVMContext::MD_invariant_group)) { + if (Instruction *G = findInvariantGroupValue(L, *DT)) + R = ReachingMemVal::getDef(getLoadStorePointerOperand(G), G); + } + Values.emplace_back(std::move(*R)); + continue; + } + + // Non-local speculations are not allowed under asan. Note the we can exit + // from here only on the first iteration of the loop. + assert((Item.BB == StartBlock || !HasSanitizer) && + "Should have exited on the first iteration"); + if (HasSanitizer) { + Values.emplace_back(ReachingMemVal::getUnknown(Item.BB, Loc.Ptr)); + break; + } + + // If the clobbering access is in another block, look in the predecessors, + // keeping the same clobbering access. This also handles the case when the + // clobbering access is liveOnEntry and we aren't at the entry block. + // If the clobbering access is a MemoryPhi, look in the predecessors, + // using the corresponding incoming value for this MemoryPhi as the + // clobbering access. + if (Item.ClobberMA->getBlock() != Item.BB || + isa(Item.ClobberMA)) { + SmallVector TmpWorklist; + if (!collectPredecessors(Item.BB, Item.Addr, Item.ClobberMA, + TmpWorklist)) { + Values.push_back( + ReachingMemVal::getUnknown(Item.BB, Item.Addr.getAddr())); + continue; + } + for (auto &T : TmpWorklist) { + if (T.Addr.getAddr() == nullptr) { + // If the phi-translation to a predecessor failed, record the + // predecessor as a clobber. + Values.push_back(ReachingMemVal::getUnknown(T.BB, nullptr)); + continue; + } + Worklist.push_back(std::move(T)); + } + continue; + } + + if (!MSSA.isLiveOnEntryDef(Item.ClobberMA)) { + // The clobbering access is a normal instruction, that we can + // nevertheless skip over (e.g. a release fence). + auto *Def = cast(Item.ClobberMA); + auto &Last = Worklist.emplace_back(Item); + Last.ClobberMA = Def->getDefiningAccess(); + continue; + } + + // If we have liveOnEntry and we are at the entry block, then this block + // does not provide any useful value for the load. + Values.emplace_back(ReachingMemVal::getUnknown(Item.BB, Loc.Ptr)); + } + + return true; +} + /// Attempt to eliminate a load, first by eliminating it /// locally, and then attempting non-local elimination if that fails. bool GVNPass::processLoad(LoadInst *L) { - if (!MD) + if (!MD && !MSSAU) return false; // This code hasn't been audited for ordered or volatile memory access @@ -2135,17 +2601,35 @@ return true; } - // ... to a pointer that has been loaded from before... - MemDepResult Dep = MD->getDependency(L); + ReachingMemVal MemVal = ReachingMemVal::getUnknown(nullptr, nullptr); + if (MD && !MSSAU) { + // ... to a pointer that has been loaded from before... + MemDepResult Dep = MD->getDependency(L); - // If it is defined in another block, try harder. - if (Dep.isNonLocal()) - return processNonLocalLoad(L); + // If it is defined in another block, try harder. + if (Dep.isNonLocal()) + return processNonLocalLoad(L); + + // Only handle the local case below + if (Dep.isDef()) + MemVal = ReachingMemVal::getDef(L->getPointerOperand(), Dep.getInst()); + else if (Dep.isClobber()) + MemVal = + ReachingMemVal::getClobber(L->getPointerOperand(), Dep.getInst()); + } else { + SmallVector MemVals; + if (!findReachingValuesForLoad(L, *MSSAU->getMemorySSA(), *AA, MemVals)) + return false; // Too many dependencies. + assert(MemVals.size() && "Expected at least an unknown value"); + if (MemVals.size() > 1 || MemVals[0].Block != L->getParent()) + return processNonLocalLoad(L, MemVals); + + // Only handle the local case below + MemVal = MemVals[0]; + } Value *Address = L->getPointerOperand(); - // Only handle the local case below - if (!Dep.isDef() && !Dep.isClobber() && !isa(Address)) { - // This might be a NonFuncLocal or an Unknown + if (MemVal.Kind == DepKind::Other && !isa(Address)) { LLVM_DEBUG( // fast print dep, using operator<< on instruction is too slow. dbgs() << "GVN: load "; L->printAsOperand(dbgs()); @@ -2154,7 +2638,7 @@ } AvailableValue AV; - if (AnalyzeLoadAvailability(L, Dep, Address, AV)) { + if (AnalyzeLoadAvailability(L, MemVal, Address, AV)) { Value *AvailableValue = AV.MaterializeAdjustedValue(L, L, *this); // Replace the load! @@ -2707,6 +3191,7 @@ DT = &RunDT; VN.setDomTree(DT); TLI = &RunTLI; + AA = &RunAA; VN.setAliasAnalysis(&RunAA); MD = RunMD; ImplicitControlFlowTracking ImplicitCFT; @@ -3316,8 +3801,6 @@ return false; auto *LIWP = getAnalysisIfAvailable(); - - auto *MSSAWP = getAnalysisIfAvailable(); return Impl.runImpl( F, getAnalysis().getAssumptionCache(F), getAnalysis().getDomTree(), @@ -3328,7 +3811,9 @@ : nullptr, LIWP ? &LIWP->getLoopInfo() : nullptr, &getAnalysis().getORE(), - MSSAWP ? &MSSAWP->getMSSA() : nullptr); + Impl.isMemorySSAEnabled() + ? &getAnalysis().getMSSA() + : nullptr); } void getAnalysisUsage(AnalysisUsage &AU) const override { Index: llvm/test/Analysis/TypeBasedAliasAnalysis/gvn-nonlocal-type-mismatch.ll =================================================================== --- llvm/test/Analysis/TypeBasedAliasAnalysis/gvn-nonlocal-type-mismatch.ll +++ llvm/test/Analysis/TypeBasedAliasAnalysis/gvn-nonlocal-type-mismatch.ll @@ -1,4 +1,5 @@ -; RUN: opt -tbaa -basic-aa -gvn -S < %s | FileCheck %s +; RUN: opt -tbaa -basic-aa -gvn -S -enable-gvn-memoryssa=false < %s | FileCheck %s --check-prefixes=CHECK,CHECK-MEMDEP +; RUN: opt -tbaa -basic-aa -gvn -S -enable-gvn-memoryssa=true < %s | FileCheck %s --check-prefixes=CHECK,CHECK-MEMSSA target datalayout = "e-p:64:64:64" @@ -30,14 +31,19 @@ ; the other type could be unified with the first type, however for now, GVN ; should just be conservative. +; However, with the MemorySSA changes this no longer happens and GVN optimises +; it just like in the next function. + ; CHECK: @watch_out_for_type_change ; CHECK: if.then: ; CHECK: %t = load i32, i32* %p ; CHECK: store i32 %t, i32* %q ; CHECK: ret void ; CHECK: if.else: -; CHECK: %u = load i32, i32* %p -; CHECK: store i32 %u, i32* %q +; CHECK-MEMDEP-NEXT: %u = load i32, i32* %p +; CHECK-MEMDEP-NEXT: store i32 %u, i32* %q +; CHECK-MEMSSA-NEXT: store i32 0, i32* %q +; CHECK-MEMSSA-NEXT: ret void define void @watch_out_for_type_change(i1 %c, i32* %p, i32* %p1, i32* %q) nounwind { entry: Index: llvm/test/Transforms/GVN/PRE/rle.ll =================================================================== --- llvm/test/Transforms/GVN/PRE/rle.ll +++ llvm/test/Transforms/GVN/PRE/rle.ll @@ -1,6 +1,7 @@ -; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt < %s -data-layout="e-p:32:32:32-p1:16:16:16-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-n8:16:32" -basic-aa -gvn -enable-split-backedge-in-load-pre -S -dce | FileCheck %s --check-prefixes=CHECK,LE -; RUN: opt < %s -data-layout="E-p:32:32:32-p1:16:16:16-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:64:64-n32" -basic-aa -gvn -enable-split-backedge-in-load-pre -S -dce | FileCheck %s --check-prefixes=CHECK,BE +; RUN: opt < %s -data-layout="e-p:32:32:32-p1:16:16:16-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-n8:16:32" -basic-aa -gvn -enable-split-backedge-in-load-pre -enable-gvn-memoryssa=false -S -dce | FileCheck %s --check-prefixes=CHECK,LE,LE-MEMDEP +; RUN: opt < %s -data-layout="e-p:32:32:32-p1:16:16:16-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-n8:16:32" -basic-aa -gvn -enable-split-backedge-in-load-pre -enable-gvn-memoryssa=true -S -dce | FileCheck %s --check-prefixes=CHECK,LE,LE-MEMSSA +; RUN: opt < %s -data-layout="E-p:32:32:32-p1:16:16:16-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:64:64-n32" -basic-aa -gvn -enable-split-backedge-in-load-pre -enable-gvn-memoryssa=false -S -dce | FileCheck %s --check-prefixes=CHECK,BE,BE-MEMDEP +; RUN: opt < %s -data-layout="E-p:32:32:32-p1:16:16:16-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:64:64-n32" -basic-aa -gvn -enable-split-backedge-in-load-pre -enable-gvn-memoryssa=true -S -dce | FileCheck %s --check-prefixes=CHECK,BE,BE-MEMSSA ;; Trivial RLE test. define i32 @test0(i32 %V, i32* %P) { @@ -1014,11 +1015,15 @@ ; CHECK-NEXT: [[XX:%.*]] = bitcast i8* [[P:%.*]] to i32* ; CHECK-NEXT: [[X1:%.*]] = load i32, i32* [[XX]], align 4 ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[X1]], 127 -; LE-NEXT: [[TMP0:%.*]] = lshr i32 [[X1]], 16 -; BE-NEXT: [[TMP0:%.*]] = lshr i32 [[X1]], 8 +; LE-MEMDEP-NEXT: [[TMP0:%.*]] = lshr i32 [[X1]], 16 +; BE-MEMDEP-NEXT: [[TMP0:%.*]] = lshr i32 [[X1]], 8 +; LE-MEMSSA-NEXT: [[TMP0:%.*]] = lshr i32 [[X1]], 8 +; BE-MEMSSA-NEXT: [[TMP0:%.*]] = lshr i32 [[X1]], 16 ; CHECK-NEXT: [[TMP1:%.*]] = trunc i32 [[TMP0]] to i8 -; LE-NEXT: [[TMP2:%.*]] = lshr i32 [[X1]], 8 -; BE-NEXT: [[TMP2:%.*]] = lshr i32 [[X1]], 16 +; LE-MEMDEP-NEXT: [[TMP2:%.*]] = lshr i32 [[X1]], 8 +; BE-MEMDEP-NEXT: [[TMP2:%.*]] = lshr i32 [[X1]], 16 +; LE-MEMSSA-NEXT: [[TMP2:%.*]] = lshr i32 [[X1]], 16 +; BE-MEMSSA-NEXT: [[TMP2:%.*]] = lshr i32 [[X1]], 8 ; CHECK-NEXT: [[TMP3:%.*]] = trunc i32 [[TMP2]] to i8 ; CHECK-NEXT: br i1 [[CMP]], label [[IF:%.*]], label [[ELSE:%.*]] ; CHECK: if: @@ -1026,7 +1031,10 @@ ; CHECK: else: ; CHECK-NEXT: br label [[JOIN]] ; CHECK: join: -; CHECK-NEXT: [[TTMP5:%.*]] = phi i8 [ [[TMP3]], [[IF]] ], [ [[TMP1]], [[ELSE]] ] +; LE-MEMDEP-NEXT: [[TTMP5:%.*]] = phi i8 [ [[TMP3]], [[IF]] ], [ [[TMP1]], [[ELSE]] ] +; BE-MEMDEP-NEXT: [[TTMP5:%.*]] = phi i8 [ [[TMP3]], [[IF]] ], [ [[TMP1]], [[ELSE]] ] +; LE-MEMSSA-NEXT: [[TTMP5:%.*]] = phi i8 [ [[TMP1]], [[IF]] ], [ [[TMP3]], [[ELSE]] ] +; BE-MEMSSA-NEXT: [[TTMP5:%.*]] = phi i8 [ [[TMP1]], [[IF]] ], [ [[TMP3]], [[ELSE]] ] ; CHECK-NEXT: [[CONV6:%.*]] = zext i8 [[TTMP5]] to i32 ; CHECK-NEXT: ret i32 [[CONV6]] ; CHECK: if.end: @@ -1281,3 +1289,40 @@ call void @use3(i8*** %x, i8** %DEAD) nounwind ret void } + + +define i32 @test_nonaliasing_clobber_ma(i1 %c0, i1 %c1, i1 %c2, i1 %c3, i32* noalias %p, i32* %q) { +; CHECK-LABEL: @test_nonaliasing_clobber_ma( +; CHECK-LABEL: H: +; CHECK-NEXT: %v = phi i32 [ %u, %F ], [ 1, %G ] +A: + br i1 %c0, label %B, label %C + +B: + store i32 0, i32* %p + br label %C + +C: + br i1 %c1, label %D, label %E + +D: + store i32 0, i32* %q + br label %E + +E: + br i1 %c2, label %F, label %G + +F: + %u = load i32, i32* %p + br i1 %c3, label %G, label %H + +G: + store i32 1, i32* %p + br label %H + +H: + %w = phi i32 [%u, %F], [0, %G] + %v = load i32, i32* %p + %r = add i32 %w, %v + ret i32 %r +} Index: llvm/test/Transforms/LoopVectorize/X86/metadata-enable.ll =================================================================== --- llvm/test/Transforms/LoopVectorize/X86/metadata-enable.ll +++ llvm/test/Transforms/LoopVectorize/X86/metadata-enable.ll @@ -1,13 +1,13 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt < %s -mcpu=corei7 -passes='default' -S -unroll-allow-partial=0 | FileCheck %s --check-prefix=O1 -; RUN: opt < %s -mcpu=corei7 -passes='default' -S -unroll-allow-partial=0 | FileCheck %s --check-prefix=O2 -; RUN: opt < %s -mcpu=corei7 -passes='default' -S -unroll-threshold=150 -unroll-allow-partial=0 | FileCheck %s --check-prefix=O3 -; RUN: opt < %s -mcpu=corei7 -passes='default' -S -unroll-allow-partial=0 | FileCheck %s --check-prefix=O3DEFAULT -; RUN: opt < %s -mcpu=corei7 -passes='default' -S -unroll-allow-partial=0 | FileCheck %s --check-prefix=Os -; RUN: opt < %s -mcpu=corei7 -passes='default' -S -unroll-allow-partial=0 | FileCheck %s --check-prefix=Oz -; RUN: opt < %s -mcpu=corei7 -passes='default,loop-vectorize' -S -unroll-allow-partial=0 | FileCheck %s --check-prefix=O1VEC2 -; RUN: opt < %s -mcpu=corei7 -passes='default,loop-vectorize' -S -unroll-allow-partial=0 | FileCheck %s --check-prefix=OzVEC2 -; RUN: opt < %s -mcpu=corei7 -passes='default' -unroll-threshold=150 -vectorize-loops=false -S -unroll-allow-partial=0 | FileCheck %s --check-prefix=O3DIS +; RUN: opt < %s -mcpu=corei7 -passes='default' -S -unroll-allow-partial=0 -enable-gvn-memoryssa=false | FileCheck %s --check-prefix=O1 +; RUN: opt < %s -mcpu=corei7 -passes='default' -S -unroll-allow-partial=0 -enable-gvn-memoryssa=false | FileCheck %s --check-prefix=O2 +; RUN: opt < %s -mcpu=corei7 -passes='default' -S -unroll-threshold=150 -unroll-allow-partial=0 -enable-gvn-memoryssa=false | FileCheck %s --check-prefix=O3 +; RUN: opt < %s -mcpu=corei7 -passes='default' -S -unroll-allow-partial=0 -enable-gvn-memoryssa=false| FileCheck %s --check-prefix=O3DEFAULT +; RUN: opt < %s -mcpu=corei7 -passes='default' -S -unroll-allow-partial=0 -enable-gvn-memoryssa=false| FileCheck %s --check-prefix=Os +; RUN: opt < %s -mcpu=corei7 -passes='default' -S -unroll-allow-partial=0 -enable-gvn-memoryssa=false| FileCheck %s --check-prefix=Oz +; RUN: opt < %s -mcpu=corei7 -passes='default,loop-vectorize' -S -unroll-allow-partial=0 -enable-gvn-memoryssa=false | FileCheck %s --check-prefix=O1VEC2 +; RUN: opt < %s -mcpu=corei7 -passes='default,loop-vectorize' -S -unroll-allow-partial=0 -enable-gvn-memoryssa=false | FileCheck %s --check-prefix=OzVEC2 +; RUN: opt < %s -mcpu=corei7 -passes='default' -unroll-threshold=150 -vectorize-loops=false -S -unroll-allow-partial=0 -enable-gvn-memoryssa=false | FileCheck %s --check-prefix=O3DIS ; This file tests the llvm.loop.vectorize.enable metadata forcing ; vectorization even when optimization levels are too low, or when