Lines Matching +full:dt +full:- +full:node
1 //===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
13 // Loop pre-header insertion guarantees that there is a single, non-critical
17 // Loop exit-block insertion guarantees that all exit blocks from the loop
20 // by the loop header). This simplifies transformations such as store-sinking
31 // asm-goto where blockaddress expressions are used.
40 //===----------------------------------------------------------------------===//
74 #define DEBUG_TYPE "loop-simplify"
85 Function::iterator BBI = --NewBB->getIterator();
93 // fall-through.
99 Function::iterator BBI = Pred->getIterator();
100 if (++BBI != NewBB->getParent()->end() && L->contains(&*BBI)) {
111 NewBB->moveAfter(FoundBB);
114 /// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
118 BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, DominatorTree *DT,
121 BasicBlock *Header = L->getHeader();
126 if (!L->contains(P)) { // Coming in from outside the loop?
130 if (isa<IndirectBrInst>(P->getTerminator()))
138 // Split out the loop pre-header.
140 PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", DT,
145 LLVM_DEBUG(dbgs() << "LoopSimplify: Creating pre-header "
146 << PreheaderBB->getName() << "\n");
171 /// The first part of loop-nestification is to find a PHI node that tells
173 static PHINode *findPHIToPartitionLoops(Loop *L, DominatorTree *DT,
175 const DataLayout &DL = L->getHeader()->getDataLayout();
176 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) {
179 if (Value *V = simplifyInstruction(PN, {DL, nullptr, DT, AC})) {
181 PN->replaceAllUsesWith(V);
182 PN->eraseFromParent();
186 // Scan this PHI node looking for a use of the PHI node by itself.
187 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
188 if (PN->getIncomingValue(i) == PN &&
189 L->contains(PN->getIncomingBlock(i)))
216 DominatorTree *DT, LoopInfo *LI,
234 for (auto *BB : L->blocks()) {
237 if (CI->isConvergent()) {
245 BasicBlock *Header = L->getHeader();
246 assert(!Header->isEHPad() && "Can't insert backedge to EH pad");
248 PHINode *PN = findPHIToPartitionLoops(L, DT, AC);
252 // handles the case when a PHI node has multiple instances of itself as
255 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
256 if (PN->getIncomingValue(i) != PN ||
257 !L->contains(PN->getIncomingBlock(i))) {
259 if (isa<IndirectBrInst>(PN->getIncomingBlock(i)->getTerminator()))
261 OuterLoopPreds.push_back(PN->getIncomingBlock(i));
270 SE->forgetLoop(L);
273 DT, LI, MSSAU, PreserveLCSSA);
280 Loop *NewOuter = LI->AllocateLoop();
283 if (Loop *Parent = L->getParentLoop())
284 Parent->replaceChildLoopWith(L, NewOuter);
286 LI->changeTopLevelLoop(L, NewOuter);
289 NewOuter->addChildLoop(L);
291 for (BasicBlock *BB : L->blocks())
292 NewOuter->addBlockEntry(BB);
296 L->moveToHeader(Header);
302 if (DT->dominates(Header, P))
308 const std::vector<Loop*> &SubLoops = L->getSubLoops();
310 if (BlocksInL.count(SubLoops[I]->getHeader()))
313 NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I));
319 for (unsigned i = 0; i != L->getBlocks().size(); ++i) {
320 BasicBlock *BB = L->getBlocks()[i];
323 L->removeBlockFromLoop(BB);
325 LI->changeLoopFor(BB, NewOuter);
328 --i;
334 formDedicatedExitBlocks(L, DT, LI, MSSAU, PreserveLCSSA);
338 // L, can now be used in NewOuter loop. We need to insert phi-nodes for them
342 // already be a use of an LCSSA phi node.
343 formLCSSA(*L, *DT, LI, SE);
345 assert(NewOuter->isRecursivelyLCSSAForm(*DT, *LI) &&
359 DominatorTree *DT, LoopInfo *LI,
361 assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!");
364 BasicBlock *Header = L->getHeader();
365 Function *F = Header->getParent();
372 assert(!Header->isEHPad() && "Can't insert backedge to EH pad");
374 // Figure out which basic blocks contain back-edges to the loop header.
378 if (isa<IndirectBrInst>(P->getTerminator()))
385 BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(),
386 Header->getName() + ".backedge", F);
388 BETerminator->setDebugLoc(Header->getFirstNonPHI()->getDebugLoc());
391 << BEBlock->getName() << "\n");
394 Function::iterator InsertPos = ++BackedgeBlocks.back()->getIterator();
395 F->splice(InsertPos, F, BEBlock->getIterator());
399 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
401 PHINode *NewPN = PHINode::Create(PN->getType(), BackedgeBlocks.size(),
402 PN->getName()+".be", BETerminator->getIterator());
404 // Loop over the PHI node, moving all entries except the one for the
405 // preheader over to the new PHI node.
409 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
410 BasicBlock *IBB = PN->getIncomingBlock(i);
411 Value *IV = PN->getIncomingValue(i);
415 NewPN->addIncoming(IV, IBB);
428 PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx));
429 PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx));
432 PN->removeIncomingValueIf([](unsigned Idx) { return Idx != 0; },
435 // Finally, add the newly constructed PHI node as the entry for the BEBlock.
436 PN->addIncoming(NewPN, BEBlock);
439 // subset of the incoming values of the old PHI node) have the same value,
440 // eliminate the PHI Node.
442 NewPN->replaceAllUsesWith(UniqueValue);
443 NewPN->eraseFromParent();
453 Instruction *TI = BB->getTerminator();
455 LoopMD = TI->getMetadata(LLVMContext::MD_loop);
456 TI->setMetadata(LLVMContext::MD_loop, nullptr);
457 TI->replaceSuccessorWith(Header, BEBlock);
459 BEBlock->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopMD);
461 //===--- Update all analyses which we must preserve now -----------------===//
463 // Update Loop Information - we know that this block is now in the current
465 L->addBasicBlockToLoop(BEBlock, *LI);
468 DT->splitBlock(BEBlock);
471 MSSAU->updatePhisWhenInsertingUniqueBackedgeBlock(Header, Preheader,
479 DominatorTree *DT, LoopInfo *LI,
484 MSSAU->getMemorySSA()->verifyMemorySSA();
492 for (BasicBlock *BB : L->blocks()) {
493 if (BB == L->getHeader())
498 if (!L->contains(P))
501 // Delete each unique out-of-loop (and thus dead) predecessor.
505 << P->getName() << "\n");
508 Instruction *TI = P->getTerminator();
516 MSSAU->getMemorySSA()->verifyMemorySSA();
522 L->getExitingBlocks(ExitingBlocks);
524 if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
525 if (BI->isConditional()) {
526 if (UndefValue *Cond = dyn_cast<UndefValue>(BI->getCondition())) {
530 << ExitingBlock->getName() << "\n");
532 BI->setCondition(ConstantInt::get(Cond->getType(),
533 !L->contains(BI->getSuccessor(0))));
540 BasicBlock *Preheader = L->getLoopPreheader();
542 Preheader = InsertPreheaderForLoop(L, DT, LI, MSSAU, PreserveLCSSA);
551 if (formDedicatedExitBlocks(L, DT, LI, MSSAU, PreserveLCSSA))
555 MSSAU->getMemorySSA()->verifyMemorySSA();
559 BasicBlock *LoopLatch = L->getLoopLatch();
564 if (L->getNumBackEdges() < 8) {
565 if (Loop *OuterL = separateNestedLoop(L, Preheader, DT, LI, SE,
569 // depth-first nest walk.
583 LoopLatch = insertUniqueBackedgeBlock(L, Preheader, DT, LI, MSSAU);
589 MSSAU->getMemorySSA()->verifyMemorySSA();
591 const DataLayout &DL = L->getHeader()->getDataLayout();
597 for (BasicBlock::iterator I = L->getHeader()->begin();
599 if (Value *V = simplifyInstruction(PN, {DL, nullptr, DT, AC})) {
600 if (SE) SE->forgetValue(PN);
601 if (!PreserveLCSSA || LI->replacementPreservesLCSSAForm(PN, V)) {
602 PN->replaceAllUsesWith(V);
603 PN->eraseFromParent();
612 // function), however this code is loop-aware, where SimplifyCFG is
614 // loop-invariant instructions out of the way to open up more
621 if (L->contains(SuccBB))
634 if (!ExitingBlock->getSinglePredecessor()) continue;
635 BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
636 if (!BI || !BI->isConditional()) continue;
637 CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
638 if (!CI || CI->getParent() != ExitingBlock) continue;
644 for (auto I = ExitingBlock->instructionsWithoutDebug().begin(); &*I != BI; ) {
648 if (!L->makeLoopInvariant(
650 Preheader ? Preheader->getTerminator() : nullptr, MSSAU, SE)) {
668 << ExitingBlock->getName() << "\n");
672 LI->removeBlock(ExitingBlock);
674 DomTreeNode *Node = DT->getNode(ExitingBlock);
675 while (!Node->isLeaf()) {
676 DomTreeNode *Child = Node->back();
677 DT->changeImmediateDominator(Child, Node->getIDom());
679 DT->eraseNode(ExitingBlock);
683 MSSAU->removeBlocks(ExitBlockSet);
686 BI->getSuccessor(0)->removePredecessor(
688 BI->getSuccessor(1)->removePredecessor(
690 ExitingBlock->eraseFromParent();
695 MSSAU->getMemorySSA()->verifyMemorySSA();
700 bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
709 assert(DT && "DT not available.");
711 assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
716 // Worklist maintains our depth-first queue of loops in this nest to process.
721 // the back. This will let us process loops from back to front in depth-first
725 Worklist.append(L2->begin(), L2->end());
729 Changed |= simplifyOneLoop(Worklist.pop_back_val(), Worklist, DT, LI, SE,
734 // any changes. Do this here rather than in simplifyOneLoop() as the top-most
737 SE->forgetTopmostLoop(L);
773 /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees.
779 INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify",
784 INITIALIZE_PASS_END(LoopSimplify, "loop-simplify",
791 /// runOnFunction - Run down all loops in the CFG (recursively, but we could do
797 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
799 ScalarEvolution *SE = SEWP ? &SEWP->getSE() : nullptr;
806 MSSA = &MSSAAnalysis->getMSSA();
814 Changed |= simplifyLoop(L, DT, LI, SE, AC, MSSAU.get(), PreserveLCSSA);
819 *LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, *LI); });
820 assert(InLCSSA && "LCSSA is broken after loop-simplify.");
830 DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F);
836 auto *MSSA = &MSSAAnalysis->getMSSA();
845 simplifyLoop(L, DT, LI, SE, AC, MSSAU.get(), /*PreserveLCSSA*/ false);
866 // FIXME: Restore this code when we re-enable verification in verifyAnalysis
871 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
874 // It used to be possible to just assert L->isLoopSimplifyForm(), however
880 if (!L->getLoopPreheader() || !L->getLoopLatch()) {
882 for (BasicBlock *Pred : predecessors(L->getHeader()))
883 if (isa<IndirectBrInst>(Pred->getTerminator())) {
893 if (!L->hasDedicatedExits()) {
896 L->getExitingBlocks(ExitingBlocks);
898 if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) {
912 // FIXME: This routine is being called mid-way through the loop pass manager
917 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)