Lines Matching +full:batch +full:- +full:reduce
1 //===- MemorySSA.cpp - Memory SSA Builder ---------------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
11 //===----------------------------------------------------------------------===//
30 #include "llvm/Config/llvm-config.h"
64 DotCFGMSSA("dot-cfg-mssa",
76 "memssa-check-limit", cl::Hidden, cl::init(100),
88 VerifyMemorySSAX("verify-memoryssa", cl::location(VerifyMemorySSA),
105 if (MemoryAccess *MA = MSSA->getMemoryAccess(BB))
111 if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
125 : MSSA(M), Walker(M->getWalker()), BAA(M->getAA()) {}
129 if (MemoryAccess *MA = MSSA->getMemoryAccess(BB))
135 if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) {
136 MemoryAccess *Clobber = Walker->getClobberingMemoryAccess(MA, BAA);
139 OS << " - clobbered by ";
140 if (MSSA->isLiveOnEntryDef(Clobber))
155 /// non-calls, and functions called on one usually assert on the other.
164 : MemoryLocOrCall(MUD->getMemoryInst()) {}
166 : MemoryLocOrCall(MUD->getMemoryInst()) {}
200 if (Call->getCalledOperand() != Other.Call->getCalledOperand())
203 return Call->arg_size() == Other.Call->arg_size() &&
204 std::equal(Call->arg_begin(), Call->arg_end(),
205 Other.Call->arg_begin());
236 MLOC.getCall()->getCalledOperand()));
238 for (const Value *Arg : MLOC.getCall()->args())
250 /// This does one-way checks to see if Use could theoretically be hoisted above
258 bool VolatileUse = Use->isVolatile();
259 bool VolatileClobber = MayClobber->isVolatile();
265 // non-volatile operations.'"
274 bool SeqCstUse = Use->getOrdering() == AtomicOrdering::SequentiallyConsistent;
275 bool MayClobberIsAcquire = isAtLeastOrStrongerThan(MayClobber->getOrdering(),
284 Instruction *DefInst = MD->getMemoryInst();
295 switch (II->getIntrinsicID()) {
333 return instructionClobbersQuery(MD, MemoryLocation(), MU->getMemoryInst(),
335 return instructionClobbersQuery(MD, UseMLOC.getLoc(), MU->getMemoryInst(),
376 return I->hasMetadata(LLVMContext::MD_invariant_load) ||
385 /// This is meant to be as simple and self-contained as possible. Because it
426 // since it won't let us short-circuit.
528 assert(From->getNumOperands() && "Phi with no operands?");
530 BasicBlock *BB = From->getBlock();
533 while ((Node = Node->getIDom())) {
534 auto *Defs = MSSA.getBlockDefs(Node->getBlock());
536 return &*Defs->rbegin();
578 if (!--*UpwardWalkLimit)
581 if (instructionClobbersQuery(MD, Desc.Loc, Query->Inst, *AA))
590 "Ended at a non-clobber that's not a phi?");
646 // - We generally query things in a top-down order, so if we got below D
649 // - We still cache things for A, so C only needs to walk up a bit.
656 if (Query->SkipSelfAccess && Node.Loc == Query->StartingLoc) {
657 assert(isa<MemoryDef>(Query->OriginalAccess));
658 SkipStopWhere = Query->OriginalAccess;
716 T &curNode() const { return W->Paths[*N]; }
748 return NP - &Paths.front();
755 /// - Find the earliest def/phi, A, we can optimize to
756 /// - Find if all paths from the starting memory access ultimately reach A
757 /// - If not, optimization isn't possible.
758 /// - Otherwise, walk from A to another clobber or phi, A'.
759 /// - If A' is a def, we're done.
760 /// - If A' is a phi, try to optimize it.
786 if (!MSSA.dominates(I->Clobber, Dom->Clobber))
788 auto Last = Paths.end() - 1;
811 // Find the node we started at. We can't search based on N->Last, since
813 auto Iter = find_if(def_path(Blocker->LastNode), [&](const DefPath &N) {
866 // Micro-opt: If we hit the end of the chain, save it.
880 const BasicBlock *ChainBB = DefChainEnd->getBlock();
884 if (DT.dominates(ChainBB, TP.Clobber->getBlock()))
941 // its def. (This has the nice side-effect of ensuring we never cache uses)
943 Current = MU->getDefiningAccess();
946 // Fast path for the overly-common case (no crazy phi optimization
999 // original queried access. If true, there will be a follow-up query searching
1024 return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL, false);
1029 return Walker->getClobberingMemoryAccessBase(MA, Loc, BAA, UWL);
1034 return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL, false, false);
1051 MUD->resetOptimized();
1067 return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL, true);
1072 return Walker->getClobberingMemoryAccessBase(MA, Loc, BAA, UWL);
1089 MUD->resetOptimized();
1101 if (It == PerBlockAccesses.end() || !isa<MemoryPhi>(It->second->front()))
1103 AccessList *Accesses = It->second.get();
1104 auto *Phi = cast<MemoryPhi>(&Accesses->front());
1107 for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I)
1108 if (Phi->getIncomingBlock(I) == BB) {
1109 Phi->setIncomingValue(I, IncomingVal);
1115 Phi->addIncoming(IncomingVal, BB);
1127 AccessList *Accesses = It->second.get();
1130 if (MUD->getDefiningAccess() == nullptr || RenameAllUses)
1131 MUD->setDefiningAccess(IncomingVal);
1155 bool AlreadyVisited = !Visited.insert(Root->getBlock()).second;
1159 IncomingVal = renameBlock(Root->getBlock(), IncomingVal, RenameAllUses);
1160 renameSuccessorPhis(Root->getBlock(), IncomingVal, RenameAllUses);
1161 WorkStack.push_back({Root, Root->begin(), IncomingVal});
1168 if (ChildIt == Node->end()) {
1173 BasicBlock *BB = Child->getBlock();
1184 IncomingVal = &*BlockDefs->rbegin();
1188 WorkStack.push_back({Child, Child->begin(), IncomingVal});
1197 assert(!DT->isReachableFromEntry(BB) &&
1205 if (!DT->isReachableFromEntry(S))
1209 if (It == PerBlockAccesses.end() || !isa<MemoryPhi>(It->second->front()))
1211 AccessList *Accesses = It->second.get();
1212 auto *Phi = cast<MemoryPhi>(&Accesses->front());
1213 Phi->addIncoming(LiveOnEntryDef.get(), BB);
1220 auto &Accesses = It->second;
1221 for (auto AI = Accesses->begin(), AE = Accesses->end(); AI != AE;) {
1226 UseOrDef->setDefiningAccess(LiveOnEntryDef.get());
1228 Accesses->erase(AI);
1236 // Build MemorySSA using a batch alias analysis. This reuses the internal
1239 // significantly reduce the time spent by the compiler in AA, because we will
1243 buildMemorySSA(BatchAA, iterator_range(F->begin(), F->end()));
1245 // use non-batch AliasAnalysis.
1246 this->AA = AA;
1254 // Build MemorySSA using a batch alias analysis. This reuses the internal
1257 // significantly reduce the time spent by the compiler in AA, because we will
1262 BatchAA, map_range(L.blocks(), [](const BasicBlock *BB) -> BasicBlock & {
1266 // use non-batch AliasAnalysis.
1267 this->AA = AA;
1283 Res.first->second = std::make_unique<AccessList>();
1284 return Res.first->second.get();
1291 Res.first->second = std::make_unique<DefsList>();
1292 return Res.first->second.get();
1297 /// This class is a batch walker of all MemoryUse's in the program, and points
1299 /// is a batch walker that touches everything, it does not operate like the
1300 /// other walkers. This walker is basically performing a top-down SSA renaming
1303 /// which is walking bottom-up.
1360 MemorySSA::AccessList *Accesses = MSSA->getWritableBlockAccesses(BB);
1370 BasicBlock *BackBlock = VersionStack.back()->getBlock();
1371 if (DT->dominates(BackBlock, BB))
1373 while (VersionStack.back()->getBlock() == BackBlock)
1386 if (MU->isOptimized())
1401 // XXX: This is non-optimal, but only is slower cases with heavily
1403 // be to make lowerbound and lastkill a per-loc stack, and pop it until
1409 !DT->dominates(LocInfo.LowerBoundBlock, BB)) {
1414 LocInfo.LowerBoundBlock = VersionStack[0]->getBlock();
1425 LocInfo.LastKill = VersionStack.size() - 1;
1436 unsigned long UpperBound = VersionStack.size() - 1;
1438 if (UpperBound - LocInfo.LowerBound > MaxCheckLimit) {
1440 << *(MU->getMemoryInst()) << ")"
1442 << UpperBound - LocInfo.LowerBound
1454 // The invariant.group handling in MemorySSA is ad-hoc and doesn't
1457 Walker->getClobberingMemoryAccessWithoutInvariantGroup(
1462 --UpperBound;
1473 --UpperBound;
1479 MU->setDefiningAccess(VersionStack[UpperBound], true);
1484 MU->setDefiningAccess(VersionStack[LocInfo.LastKill], true);
1486 LocInfo.LowerBound = VersionStack.size() - 1;
1495 VersionStack.push_back(MSSA->getLiveOnEntryDef());
1499 // We perform a non-recursive top-down dominator tree walk.
1500 for (const auto *DomNode : depth_first(DT->getRootNode()))
1501 optimizeUsesInBlock(DomNode->getBlock(), StackEpoch, PopEpoch, VersionStack,
1530 // We maintain lists of memory accesses per-block, trading memory for time. We
1547 Accesses->push_back(MUD);
1552 Defs->push_back(*MUD);
1567 if (auto *P = getMemoryAccess(L->getLoopPreheader())) {
1568 for (Use &U : make_early_inc_range(P->uses()))
1575 L->getExitBlocks(ExitBlocks);
1577 renamePass(DT->getNode(L->getLoopPreheader()), LiveOnEntryDef.get(),
1580 renamePass(DT->getRootNode(), LiveOnEntryDef.get(), Visited);
1626 Accesses->push_front(NewAccess);
1628 Defs->push_front(*NewAccess);
1632 Accesses->insert(AI, NewAccess);
1637 Defs->insert(DI, *NewAccess);
1641 Accesses->push_back(NewAccess);
1644 Defs->push_back(*NewAccess);
1653 bool WasEnd = InsertPt == Accesses->end();
1654 Accesses->insert(AccessList::iterator(InsertPt), What);
1662 Defs->push_back(*What);
1664 Defs->insert(InsertPt->getDefsIterator(), *What);
1666 while (InsertPt != Accesses->end() && !isa<MemoryDef>(InsertPt))
1669 if (InsertPt == Accesses->end())
1670 Defs->push_back(*What);
1672 Defs->insert(InsertPt->getDefsIterator(), *What);
1686 MD->resetOptimized();
1687 What->setBlock(BB);
1706 ValueToMemoryAccess.erase(What->getBlock());
1718 MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++);
1733 "non-memory touching instruction");
1737 NewAccess->setDefiningAccess(Definition);
1747 if (!SI->isUnordered())
1750 if (!LI->isUnordered())
1768 switch (II->getIntrinsicID()) {
1783 if (!I->mayReadFromMemory() && !I->mayWriteToMemory())
1791 ModRefInfo ModRef = AAP->getModRefInfo(I, std::nullopt);
1806 ModRefInfo ModRef = AAP->getModRefInfo(I, std::nullopt);
1826 MUD = new MemoryDef(I->getContext(), nullptr, I, I->getParent(), NextID++);
1828 MUD = new MemoryUse(I->getContext(), nullptr, I, I->getParent());
1831 MUD->setOptimized(LiveOnEntry);
1840 assert(MA->use_empty() &&
1844 MUD->setDefiningAccess(nullptr);
1847 getWalker()->invalidateInfo(MA);
1851 MemoryInst = MUD->getMemoryInst();
1853 MemoryInst = MA->getBlock();
1856 if (VMA->second == MA)
1867 BasicBlock *BB = MA->getBlock();
1868 // The access list owns the reference, so we erase it from the non-owning list
1872 std::unique_ptr<DefsList> &Defs = DefsIt->second;
1873 Defs->remove(*MA);
1874 if (Defs->empty())
1881 std::unique_ptr<AccessList> &Accesses = AccessIt->second;
1883 Accesses->erase(MA);
1885 Accesses->remove(MA);
1887 if (Accesses->empty()) {
1895 Function *F = this->F;
1897 F = L->getHeader()->getParent();
1898 F->print(OS, &Writer);
1912 auto Blocks = iterator_range(F->begin(), F->end());
1920 map_range(L->blocks(), [](const BasicBlock *BB) -> BasicBlock & {
1945 for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I) {
1946 auto *Pred = Phi->getIncomingBlock(I);
1947 auto *IncAcc = Phi->getIncomingValue(I);
1951 if (auto *DTNode = DT->getNode(Pred)) {
1953 if (auto *DefList = getBlockDefs(DTNode->getBlock())) {
1954 auto *LastAcc = &*(--DefList->end());
1961 DTNode = DTNode->getIDom();
2002 unsigned long ThisNumber = ThisNumberIter->second;
2011 "All valid BasicBlocks should exist in F -- dangling pointers?");
2017 /// Verify def-uses: the immediate use information - walk all the memory
2037 for (const Use &U : Phi->uses()) {
2041 // Verify def-uses for full verify.
2043 assert(Phi->getNumOperands() == pred_size(&B) &&
2045 for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I) {
2046 verifyUseInDefs(Phi->getIncomingValue(I), Phi);
2047 assert(is_contained(predecessors(&B), Phi->getIncomingBlock(I)) &&
2066 for (const Use &U : MD->uses()) {
2072 // Verify def-uses for full verify.
2074 verifyUseInDefs(MA->getDefiningAccess(), MA);
2082 assert(AL->size() == ActualAccesses.size() &&
2087 assert((!DL || DL->size() == ActualDefs.size()) &&
2090 auto ALI = AL->begin();
2092 while (ALI != AL->end() && AAI != ActualAccesses.end()) {
2099 auto DLI = DL->begin();
2101 while (DLI != DL->end() && ADI != ActualDefs.end()) {
2111 /// Verify the def-use lists in MemorySSA, by verifying that \p Use
2119 assert(is_contained(Def->users(), Use) &&
2126 /// allow at least N-1 sequences of insertBefore or insertAfter (and at least
2130 // The pre-increment ensures the numbers really start at 1.
2144 const BasicBlock *DominatorBlock = Dominator->getBlock();
2146 assert((DominatorBlock == Dominatee->getBlock()) &&
2181 if (Dominator->getBlock() != Dominatee->getBlock())
2182 return DT->dominates(Dominator->getBlock(), Dominatee->getBlock());
2189 BasicBlock *UseBB = MP->getIncomingBlock(Dominatee);
2191 if (UseBB != Dominator->getBlock())
2192 return DT->dominates(Dominator->getBlock(), UseBB);
2213 case MemoryPhiVal: return static_cast<const MemoryPhi *>(this)->print(OS);
2214 case MemoryDefVal: return static_cast<const MemoryDef *>(this)->print(OS);
2215 case MemoryUseVal: return static_cast<const MemoryUse *>(this)->print(OS);
2224 if (A && A->getID())
2225 OS << A->getID();
2235 OS << "->";
2248 if (BB->hasName())
2249 OS << BB->getName();
2251 BB->printAsOperand(OS, false);
2253 if (unsigned ID = MA->getID())
2265 if (UO && UO->getID())
2266 OS << UO->getID();
2298 return &(CFGInfo->getFunction()->getEntryBlock());
2301 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
2305 return nodes_iterator(CFGInfo->getFunction()->begin());
2309 return nodes_iterator(CFGInfo->getFunction()->end());
2313 return CFGInfo->getFunction()->size();
2323 return "MSSA CFG for '" + CFGInfo->getFunction()->getName().str() +
2330 [CFGInfo](raw_string_ostream &OS, const BasicBlock &BB) -> void {
2331 BB.print(OS, &CFGInfo->getWriter(), true, true);
2333 [](std::string &S, unsigned &I, unsigned Idx) -> void {
2334 std::string Str = S.substr(I, Idx - I);
2438 MSSA->verifyMemorySSA();
2442 MSSA->print(OS);
2447 /// Walk the use-def chains starting at \p StartingAccess and find
2462 if (MSSA->isLiveOnEntryDef(StartingUseOrDef))
2465 I = StartingUseOrDef->getMemoryInst();
2469 if (!isa<CallBase>(I) && I->isFenceLike())
2501 Value *PointerOperand = getLoadStorePointerOperand(&I)->stripPointerCasts();
2512 for (const User *Us : PointerOperand->users()) {
2520 if (U->hasMetadata(LLVMContext::MD_invariant_group) &&
2521 getLoadStorePointerOperand(U) == PointerOperand && !U->isVolatile()) {
2539 *StartingAccess->getMemoryInst(), MSSA->getDomTree())) {
2542 auto *ClobberMA = MSSA->getMemoryAccess(I);
2545 return ClobberMA->getDefiningAccess();
2555 if (StartingAccess->isOptimized()) {
2557 return StartingAccess->getOptimized();
2561 const Instruction *I = StartingAccess->getMemoryInst();
2565 if (!isa<CallBase>(I) && I->isFenceLike())
2571 MemoryAccess *LiveOnEntry = MSSA->getLiveOnEntryDef();
2572 StartingAccess->setOptimized(LiveOnEntry);
2579 MemoryAccess *DefiningAccess = StartingAccess->getDefiningAccess();
2583 if (MSSA->isLiveOnEntryDef(DefiningAccess)) {
2584 StartingAccess->setOptimized(DefiningAccess);
2590 StartingAccess->setOptimized(OptimizedAccess);
2592 OptimizedAccess = StartingAccess->getOptimized();
2618 return Use->getDefiningAccess();
2625 return Use->getDefiningAccess();
2643 Ptr = Ptr->stripPointerCasts();
2649 Ptr = Ptr->stripPointerCasts();
2651 if (I->getParent()->isEntryBlock())
2655 return IsGuaranteedLoopInvariantBase(GEP->getPointerOperand()) &&
2656 GEP->hasAllConstantIndices();