//===- BasicBlockUtils.cpp - BasicBlock Utilities --------------------------==// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This family of functions perform manipulations on basic blocks, and // instructions contained within basic blocks. // //===----------------------------------------------------------------------===// #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Twine.h" #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/DomTreeUpdater.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemoryDependenceAnalysis.h" #include "llvm/Analysis/MemorySSAUpdater.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DebugInfoMetadata.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/PseudoProbe.h" #include "llvm/IR/Type.h" #include "llvm/IR/User.h" #include "llvm/IR/Value.h" #include "llvm/IR/ValueHandle.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/Local.h" #include #include #include #include #include using namespace llvm; #define DEBUG_TYPE "basicblock-utils" static cl::opt MaxDeoptOrUnreachableSuccessorCheckDepth( "max-deopt-or-unreachable-succ-check-depth", cl::init(8), cl::Hidden, cl::desc("Set the maximum path length when checking whether a basic block " "is followed by a block that either has a terminating " "deoptimizing call or is terminated with an unreachable")); void llvm::detachDeadBlocks( ArrayRef BBs, SmallVectorImpl *Updates, bool KeepOneInputPHIs) { for (auto *BB : BBs) { // Loop through all of our successors and make sure they know that one // of their predecessors is going away. SmallPtrSet UniqueSuccessors; for (BasicBlock *Succ : successors(BB)) { Succ->removePredecessor(BB, KeepOneInputPHIs); if (Updates && UniqueSuccessors.insert(Succ).second) Updates->push_back({DominatorTree::Delete, BB, Succ}); } // Zap all the instructions in the block. while (!BB->empty()) { Instruction &I = BB->back(); // If this instruction is used, replace uses with an arbitrary value. // Because control flow can't get here, we don't care what we replace the // value with. Note that since this block is unreachable, and all values // contained within it must dominate their uses, that all uses will // eventually be removed (they are themselves dead). if (!I.use_empty()) I.replaceAllUsesWith(UndefValue::get(I.getType())); BB->getInstList().pop_back(); } new UnreachableInst(BB->getContext(), BB); assert(BB->getInstList().size() == 1 && isa(BB->getTerminator()) && "The successor list of BB isn't empty before " "applying corresponding DTU updates."); } } void llvm::DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU, bool KeepOneInputPHIs) { DeleteDeadBlocks({BB}, DTU, KeepOneInputPHIs); } void llvm::DeleteDeadBlocks(ArrayRef BBs, DomTreeUpdater *DTU, bool KeepOneInputPHIs) { #ifndef NDEBUG // Make sure that all predecessors of each dead block is also dead. SmallPtrSet Dead(BBs.begin(), BBs.end()); assert(Dead.size() == BBs.size() && "Duplicating blocks?"); for (auto *BB : Dead) for (BasicBlock *Pred : predecessors(BB)) assert(Dead.count(Pred) && "All predecessors must be dead!"); #endif SmallVector Updates; detachDeadBlocks(BBs, DTU ? &Updates : nullptr, KeepOneInputPHIs); if (DTU) DTU->applyUpdates(Updates); for (BasicBlock *BB : BBs) if (DTU) DTU->deleteBB(BB); else BB->eraseFromParent(); } bool llvm::EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU, bool KeepOneInputPHIs) { df_iterator_default_set Reachable; // Mark all reachable blocks. for (BasicBlock *BB : depth_first_ext(&F, Reachable)) (void)BB/* Mark all reachable blocks */; // Collect all dead blocks. std::vector DeadBlocks; for (BasicBlock &BB : F) if (!Reachable.count(&BB)) DeadBlocks.push_back(&BB); // Delete the dead blocks. DeleteDeadBlocks(DeadBlocks, DTU, KeepOneInputPHIs); return !DeadBlocks.empty(); } bool llvm::FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep) { if (!isa(BB->begin())) return false; while (PHINode *PN = dyn_cast(BB->begin())) { if (PN->getIncomingValue(0) != PN) PN->replaceAllUsesWith(PN->getIncomingValue(0)); else PN->replaceAllUsesWith(UndefValue::get(PN->getType())); if (MemDep) MemDep->removeInstruction(PN); // Memdep updates AA itself. PN->eraseFromParent(); } return true; } bool llvm::DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI, MemorySSAUpdater *MSSAU) { // Recursively deleting a PHI may cause multiple PHIs to be deleted // or RAUW'd undef, so use an array of WeakTrackingVH for the PHIs to delete. SmallVector PHIs; for (PHINode &PN : BB->phis()) PHIs.push_back(&PN); bool Changed = false; for (unsigned i = 0, e = PHIs.size(); i != e; ++i) if (PHINode *PN = dyn_cast_or_null(PHIs[i].operator Value*())) Changed |= RecursivelyDeleteDeadPHINode(PN, TLI, MSSAU); return Changed; } bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, LoopInfo *LI, MemorySSAUpdater *MSSAU, MemoryDependenceResults *MemDep, bool PredecessorWithTwoSuccessors) { if (BB->hasAddressTaken()) return false; // Can't merge if there are multiple predecessors, or no predecessors. BasicBlock *PredBB = BB->getUniquePredecessor(); if (!PredBB) return false; // Don't break self-loops. if (PredBB == BB) return false; // Don't break unwinding instructions. if (PredBB->getTerminator()->isExceptionalTerminator()) return false; // Can't merge if there are multiple distinct successors. if (!PredecessorWithTwoSuccessors && PredBB->getUniqueSuccessor() != BB) return false; // Currently only allow PredBB to have two predecessors, one being BB. // Update BI to branch to BB's only successor instead of BB. BranchInst *PredBB_BI; BasicBlock *NewSucc = nullptr; unsigned FallThruPath; if (PredecessorWithTwoSuccessors) { if (!(PredBB_BI = dyn_cast(PredBB->getTerminator()))) return false; BranchInst *BB_JmpI = dyn_cast(BB->getTerminator()); if (!BB_JmpI || !BB_JmpI->isUnconditional()) return false; NewSucc = BB_JmpI->getSuccessor(0); FallThruPath = PredBB_BI->getSuccessor(0) == BB ? 0 : 1; } // Can't merge if there is PHI loop. for (PHINode &PN : BB->phis()) if (llvm::is_contained(PN.incoming_values(), &PN)) return false; LLVM_DEBUG(dbgs() << "Merging: " << BB->getName() << " into " << PredBB->getName() << "\n"); // Begin by getting rid of unneeded PHIs. SmallVector, 4> IncomingValues; if (isa(BB->front())) { for (PHINode &PN : BB->phis()) if (!isa(PN.getIncomingValue(0)) || cast(PN.getIncomingValue(0))->getParent() != BB) IncomingValues.push_back(PN.getIncomingValue(0)); FoldSingleEntryPHINodes(BB, MemDep); } // DTU update: Collect all the edges that exit BB. // These dominator edges will be redirected from Pred. std::vector Updates; if (DTU) { // To avoid processing the same predecessor more than once. SmallPtrSet SeenSuccs; SmallPtrSet SuccsOfPredBB(succ_begin(PredBB), succ_end(PredBB)); Updates.reserve(Updates.size() + 2 * succ_size(BB) + 1); // Add insert edges first. Experimentally, for the particular case of two // blocks that can be merged, with a single successor and single predecessor // respectively, it is beneficial to have all insert updates first. Deleting // edges first may lead to unreachable blocks, followed by inserting edges // making the blocks reachable again. Such DT updates lead to high compile // times. We add inserts before deletes here to reduce compile time. for (BasicBlock *SuccOfBB : successors(BB)) // This successor of BB may already be a PredBB's successor. if (!SuccsOfPredBB.contains(SuccOfBB)) if (SeenSuccs.insert(SuccOfBB).second) Updates.push_back({DominatorTree::Insert, PredBB, SuccOfBB}); SeenSuccs.clear(); for (BasicBlock *SuccOfBB : successors(BB)) if (SeenSuccs.insert(SuccOfBB).second) Updates.push_back({DominatorTree::Delete, BB, SuccOfBB}); Updates.push_back({DominatorTree::Delete, PredBB, BB}); } Instruction *PTI = PredBB->getTerminator(); Instruction *STI = BB->getTerminator(); Instruction *Start = &*BB->begin(); // If there's nothing to move, mark the starting instruction as the last // instruction in the block. Terminator instruction is handled separately. if (Start == STI) Start = PTI; // Move all definitions in the successor to the predecessor... PredBB->getInstList().splice(PTI->getIterator(), BB->getInstList(), BB->begin(), STI->getIterator()); if (MSSAU) MSSAU->moveAllAfterMergeBlocks(BB, PredBB, Start); // Make all PHI nodes that referred to BB now refer to Pred as their // source... BB->replaceAllUsesWith(PredBB); if (PredecessorWithTwoSuccessors) { // Delete the unconditional branch from BB. BB->getInstList().pop_back(); // Update branch in the predecessor. PredBB_BI->setSuccessor(FallThruPath, NewSucc); } else { // Delete the unconditional branch from the predecessor. PredBB->getInstList().pop_back(); // Move terminator instruction. PredBB->getInstList().splice(PredBB->end(), BB->getInstList()); // Terminator may be a memory accessing instruction too. if (MSSAU) if (MemoryUseOrDef *MUD = cast_or_null( MSSAU->getMemorySSA()->getMemoryAccess(PredBB->getTerminator()))) MSSAU->moveToPlace(MUD, PredBB, MemorySSA::End); } // Add unreachable to now empty BB. new UnreachableInst(BB->getContext(), BB); // Inherit predecessors name if it exists. if (!PredBB->hasName()) PredBB->takeName(BB); if (LI) LI->removeBlock(BB); if (MemDep) MemDep->invalidateCachedPredecessors(); if (DTU) DTU->applyUpdates(Updates); // Finally, erase the old block and update dominator info. DeleteDeadBlock(BB, DTU); return true; } bool llvm::MergeBlockSuccessorsIntoGivenBlocks( SmallPtrSetImpl &MergeBlocks, Loop *L, DomTreeUpdater *DTU, LoopInfo *LI) { assert(!MergeBlocks.empty() && "MergeBlocks should not be empty"); bool BlocksHaveBeenMerged = false; while (!MergeBlocks.empty()) { BasicBlock *BB = *MergeBlocks.begin(); BasicBlock *Dest = BB->getSingleSuccessor(); if (Dest && (!L || L->contains(Dest))) { BasicBlock *Fold = Dest->getUniquePredecessor(); (void)Fold; if (MergeBlockIntoPredecessor(Dest, DTU, LI)) { assert(Fold == BB && "Expecting BB to be unique predecessor of the Dest block"); MergeBlocks.erase(Dest); BlocksHaveBeenMerged = true; } else MergeBlocks.erase(BB); } else MergeBlocks.erase(BB); } return BlocksHaveBeenMerged; } /// Remove redundant instructions within sequences of consecutive dbg.value /// instructions. This is done using a backward scan to keep the last dbg.value /// describing a specific variable/fragment. /// /// BackwardScan strategy: /// ---------------------- /// Given a sequence of consecutive DbgValueInst like this /// /// dbg.value ..., "x", FragmentX1 (*) /// dbg.value ..., "y", FragmentY1 /// dbg.value ..., "x", FragmentX2 /// dbg.value ..., "x", FragmentX1 (**) /// /// then the instruction marked with (*) can be removed (it is guaranteed to be /// obsoleted by the instruction marked with (**) as the latter instruction is /// describing the same variable using the same fragment info). /// /// Possible improvements: /// - Check fully overlapping fragments and not only identical fragments. /// - Support dbg.addr, dbg.declare. dbg.label, and possibly other meta /// instructions being part of the sequence of consecutive instructions. static bool removeRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB) { SmallVector ToBeRemoved; SmallDenseSet VariableSet; for (auto &I : reverse(*BB)) { if (DbgValueInst *DVI = dyn_cast(&I)) { DebugVariable Key(DVI->getVariable(), DVI->getExpression(), DVI->getDebugLoc()->getInlinedAt()); auto R = VariableSet.insert(Key); // If the same variable fragment is described more than once it is enough // to keep the last one (i.e. the first found since we for reverse // iteration). if (!R.second) ToBeRemoved.push_back(DVI); continue; } // Sequence with consecutive dbg.value instrs ended. Clear the map to // restart identifying redundant instructions if case we find another // dbg.value sequence. VariableSet.clear(); } for (auto &Instr : ToBeRemoved) Instr->eraseFromParent(); return !ToBeRemoved.empty(); } /// Remove redundant dbg.value instructions using a forward scan. This can /// remove a dbg.value instruction that is redundant due to indicating that a /// variable has the same value as already being indicated by an earlier /// dbg.value. /// /// ForwardScan strategy: /// --------------------- /// Given two identical dbg.value instructions, separated by a block of /// instructions that isn't describing the same variable, like this /// /// dbg.value X1, "x", FragmentX1 (**) /// /// dbg.value X1, "x", FragmentX1 (*) /// /// then the instruction marked with (*) can be removed. Variable "x" is already /// described as being mapped to the SSA value X1. /// /// Possible improvements: /// - Keep track of non-overlapping fragments. static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB) { SmallVector ToBeRemoved; DenseMap, DIExpression *>> VariableMap; for (auto &I : *BB) { if (DbgValueInst *DVI = dyn_cast(&I)) { DebugVariable Key(DVI->getVariable(), NoneType(), DVI->getDebugLoc()->getInlinedAt()); auto VMI = VariableMap.find(Key); // Update the map if we found a new value/expression describing the // variable, or if the variable wasn't mapped already. SmallVector Values(DVI->getValues()); if (VMI == VariableMap.end() || VMI->second.first != Values || VMI->second.second != DVI->getExpression()) { VariableMap[Key] = {Values, DVI->getExpression()}; continue; } // Found an identical mapping. Remember the instruction for later removal. ToBeRemoved.push_back(DVI); } } for (auto &Instr : ToBeRemoved) Instr->eraseFromParent(); return !ToBeRemoved.empty(); } bool llvm::RemoveRedundantDbgInstrs(BasicBlock *BB) { bool MadeChanges = false; // By using the "backward scan" strategy before the "forward scan" strategy we // can remove both dbg.value (2) and (3) in a situation like this: // // (1) dbg.value V1, "x", DIExpression() // ... // (2) dbg.value V2, "x", DIExpression() // (3) dbg.value V1, "x", DIExpression() // // The backward scan will remove (2), it is made obsolete by (3). After // getting (2) out of the way, the foward scan will remove (3) since "x" // already is described as having the value V1 at (1). MadeChanges |= removeRedundantDbgInstrsUsingBackwardScan(BB); MadeChanges |= removeRedundantDbgInstrsUsingForwardScan(BB); if (MadeChanges) LLVM_DEBUG(dbgs() << "Removed redundant dbg instrs from: " << BB->getName() << "\n"); return MadeChanges; } void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Value *V) { Instruction &I = *BI; // Replaces all of the uses of the instruction with uses of the value I.replaceAllUsesWith(V); // Make sure to propagate a name if there is one already. if (I.hasName() && !V->hasName()) V->takeName(&I); // Delete the unnecessary instruction now... BI = BIL.erase(BI); } void llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Instruction *I) { assert(I->getParent() == nullptr && "ReplaceInstWithInst: Instruction already inserted into basic block!"); // Copy debug location to newly added instruction, if it wasn't already set // by the caller. if (!I->getDebugLoc()) I->setDebugLoc(BI->getDebugLoc()); // Insert the new instruction into the basic block... BasicBlock::iterator New = BIL.insert(BI, I); // Replace all uses of the old instruction, and delete it. ReplaceInstWithValue(BIL, BI, I); // Move BI back to point to the newly inserted instruction BI = New; } bool llvm::IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB) { // Remember visited blocks to avoid infinite loop SmallPtrSet VisitedBlocks; unsigned Depth = 0; while (BB && Depth++ < MaxDeoptOrUnreachableSuccessorCheckDepth && VisitedBlocks.insert(BB).second) { if (BB->getTerminatingDeoptimizeCall() || isa(BB->getTerminator())) return true; BB = BB->getUniqueSuccessor(); } return false; } void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) { BasicBlock::iterator BI(From); ReplaceInstWithInst(From->getParent()->getInstList(), BI, To); } BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName) { unsigned SuccNum = GetSuccessorNumber(BB, Succ); Instruction *LatchTerm = BB->getTerminator(); CriticalEdgeSplittingOptions Options = CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA(); if ((isCriticalEdge(LatchTerm, SuccNum, Options.MergeIdenticalEdges))) { // If it is a critical edge, and the succesor is an exception block, handle // the split edge logic in this specific function if (Succ->isEHPad()) return ehAwareSplitEdge(BB, Succ, nullptr, nullptr, Options, BBName); // If this is a critical edge, let SplitKnownCriticalEdge do it. return SplitKnownCriticalEdge(LatchTerm, SuccNum, Options, BBName); } // If the edge isn't critical, then BB has a single successor or Succ has a // single pred. Split the block. if (BasicBlock *SP = Succ->getSinglePredecessor()) { // If the successor only has a single pred, split the top of the successor // block. assert(SP == BB && "CFG broken"); SP = nullptr; return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU, BBName, /*Before=*/true); } // Otherwise, if BB has a single successor, split it at the bottom of the // block. assert(BB->getTerminator()->getNumSuccessors() == 1 && "Should have a single succ!"); return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU, BBName); } void llvm::setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ) { if (auto *II = dyn_cast(TI)) II->setUnwindDest(Succ); else if (auto *CS = dyn_cast(TI)) CS->setUnwindDest(Succ); else if (auto *CR = dyn_cast(TI)) CR->setUnwindDest(Succ); else llvm_unreachable("unexpected terminator instruction"); } void llvm::updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, BasicBlock *NewPred, PHINode *Until) { int BBIdx = 0; for (PHINode &PN : DestBB->phis()) { // We manually update the LandingPadReplacement PHINode and it is the last // PHI Node. So, if we find it, we are done. if (Until == &PN) break; // Reuse the previous value of BBIdx if it lines up. In cases where we // have multiple phi nodes with *lots* of predecessors, this is a speed // win because we don't have to scan the PHI looking for TIBB. This // happens because the BB list of PHI nodes are usually in the same // order. if (PN.getIncomingBlock(BBIdx) != OldPred) BBIdx = PN.getBasicBlockIndex(OldPred); assert(BBIdx != -1 && "Invalid PHI Index!"); PN.setIncomingBlock(BBIdx, NewPred); } } BasicBlock *llvm::ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ, LandingPadInst *OriginalPad, PHINode *LandingPadReplacement, const CriticalEdgeSplittingOptions &Options, const Twine &BBName) { auto *PadInst = Succ->getFirstNonPHI(); if (!LandingPadReplacement && !PadInst->isEHPad()) return SplitEdge(BB, Succ, Options.DT, Options.LI, Options.MSSAU, BBName); auto *LI = Options.LI; SmallVector LoopPreds; // Check if extra modifications will be required to preserve loop-simplify // form after splitting. If it would require splitting blocks with IndirectBr // terminators, bail out if preserving loop-simplify form is requested. if (Options.PreserveLoopSimplify && LI) { if (Loop *BBLoop = LI->getLoopFor(BB)) { // The only way that we can break LoopSimplify form by splitting a // critical edge is when there exists some edge from BBLoop to Succ *and* // the only edge into Succ from outside of BBLoop is that of NewBB after // the split. If the first isn't true, then LoopSimplify still holds, // NewBB is the new exit block and it has no non-loop predecessors. If the // second isn't true, then Succ was not in LoopSimplify form prior to // the split as it had a non-loop predecessor. In both of these cases, // the predecessor must be directly in BBLoop, not in a subloop, or again // LoopSimplify doesn't hold. for (BasicBlock *P : predecessors(Succ)) { if (P == BB) continue; // The new block is known. if (LI->getLoopFor(P) != BBLoop) { // Loop is not in LoopSimplify form, no need to re simplify after // splitting edge. LoopPreds.clear(); break; } LoopPreds.push_back(P); } // Loop-simplify form can be preserved, if we can split all in-loop // predecessors. if (any_of(LoopPreds, [](BasicBlock *Pred) { return isa(Pred->getTerminator()); })) { return nullptr; } } } auto *NewBB = BasicBlock::Create(BB->getContext(), BBName, BB->getParent(), Succ); setUnwindEdgeTo(BB->getTerminator(), NewBB); updatePhiNodes(Succ, BB, NewBB, LandingPadReplacement); if (LandingPadReplacement) { auto *NewLP = OriginalPad->clone(); auto *Terminator = BranchInst::Create(Succ, NewBB); NewLP->insertBefore(Terminator); LandingPadReplacement->addIncoming(NewLP, NewBB); } else { Value *ParentPad = nullptr; if (auto *FuncletPad = dyn_cast(PadInst)) ParentPad = FuncletPad->getParentPad(); else if (auto *CatchSwitch = dyn_cast(PadInst)) ParentPad = CatchSwitch->getParentPad(); else if (auto *CleanupPad = dyn_cast(PadInst)) ParentPad = CleanupPad->getParentPad(); else if (auto *LandingPad = dyn_cast(PadInst)) ParentPad = LandingPad->getParent(); else llvm_unreachable("handling for other EHPads not implemented yet"); auto *NewCleanupPad = CleanupPadInst::Create(ParentPad, {}, BBName, NewBB); CleanupReturnInst::Create(NewCleanupPad, Succ, NewBB); } auto *DT = Options.DT; auto *MSSAU = Options.MSSAU; if (!DT && !LI) return NewBB; if (DT) { DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); SmallVector Updates; Updates.push_back({DominatorTree::Insert, BB, NewBB}); Updates.push_back({DominatorTree::Insert, NewBB, Succ}); Updates.push_back({DominatorTree::Delete, BB, Succ}); DTU.applyUpdates(Updates); DTU.flush(); if (MSSAU) { MSSAU->applyUpdates(Updates, *DT); if (VerifyMemorySSA) MSSAU->getMemorySSA()->verifyMemorySSA(); } } if (LI) { if (Loop *BBLoop = LI->getLoopFor(BB)) { // If one or the other blocks were not in a loop, the new block is not // either, and thus LI doesn't need to be updated. if (Loop *SuccLoop = LI->getLoopFor(Succ)) { if (BBLoop == SuccLoop) { // Both in the same loop, the NewBB joins loop. SuccLoop->addBasicBlockToLoop(NewBB, *LI); } else if (BBLoop->contains(SuccLoop)) { // Edge from an outer loop to an inner loop. Add to the outer loop. BBLoop->addBasicBlockToLoop(NewBB, *LI); } else if (SuccLoop->contains(BBLoop)) { // Edge from an inner loop to an outer loop. Add to the outer loop. SuccLoop->addBasicBlockToLoop(NewBB, *LI); } else { // Edge from two loops with no containment relation. Because these // are natural loops, we know that the destination block must be the // header of its loop (adding a branch into a loop elsewhere would // create an irreducible loop). assert(SuccLoop->getHeader() == Succ && "Should not create irreducible loops!"); if (Loop *P = SuccLoop->getParentLoop()) P->addBasicBlockToLoop(NewBB, *LI); } } // If BB is in a loop and Succ is outside of that loop, we may need to // update LoopSimplify form and LCSSA form. if (!BBLoop->contains(Succ)) { assert(!BBLoop->contains(NewBB) && "Split point for loop exit is contained in loop!"); // Update LCSSA form in the newly created exit block. if (Options.PreserveLCSSA) { createPHIsForSplitLoopExit(BB, NewBB, Succ); } if (!LoopPreds.empty()) { BasicBlock *NewExitBB = SplitBlockPredecessors( Succ, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA); if (Options.PreserveLCSSA) createPHIsForSplitLoopExit(LoopPreds, NewExitBB, Succ); } } } } return NewBB; } void llvm::createPHIsForSplitLoopExit(ArrayRef Preds, BasicBlock *SplitBB, BasicBlock *DestBB) { // SplitBB shouldn't have anything non-trivial in it yet. assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() || SplitBB->isLandingPad()) && "SplitBB has non-PHI nodes!"); // For each PHI in the destination block. for (PHINode &PN : DestBB->phis()) { int Idx = PN.getBasicBlockIndex(SplitBB); assert(Idx >= 0 && "Invalid Block Index"); Value *V = PN.getIncomingValue(Idx); // If the input is a PHI which already satisfies LCSSA, don't create // a new one. if (const PHINode *VP = dyn_cast(V)) if (VP->getParent() == SplitBB) continue; // Otherwise a new PHI is needed. Create one and populate it. PHINode *NewPN = PHINode::Create( PN.getType(), Preds.size(), "split", SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator()); for (BasicBlock *BB : Preds) NewPN->addIncoming(V, BB); // Update the original PHI. PN.setIncomingValue(Idx, NewPN); } } unsigned llvm::SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options) { unsigned NumBroken = 0; for (BasicBlock &BB : F) { Instruction *TI = BB.getTerminator(); if (TI->getNumSuccessors() > 1 && !isa(TI) && !isa(TI)) for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) if (SplitCriticalEdge(TI, i, Options)) ++NumBroken; } return NumBroken; } static BasicBlock *SplitBlockImpl(BasicBlock *Old, Instruction *SplitPt, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName, bool Before) { if (Before) { DomTreeUpdater LocalDTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); return splitBlockBefore(Old, SplitPt, DTU ? DTU : (DT ? &LocalDTU : nullptr), LI, MSSAU, BBName); } BasicBlock::iterator SplitIt = SplitPt->getIterator(); while (isa(SplitIt) || SplitIt->isEHPad()) { ++SplitIt; assert(SplitIt != SplitPt->getParent()->end()); } std::string Name = BBName.str(); BasicBlock *New = Old->splitBasicBlock( SplitIt, Name.empty() ? Old->getName() + ".split" : Name); // The new block lives in whichever loop the old one did. This preserves // LCSSA as well, because we force the split point to be after any PHI nodes. if (LI) if (Loop *L = LI->getLoopFor(Old)) L->addBasicBlockToLoop(New, *LI); if (DTU) { SmallVector Updates; // Old dominates New. New node dominates all other nodes dominated by Old. SmallPtrSet UniqueSuccessorsOfOld; Updates.push_back({DominatorTree::Insert, Old, New}); Updates.reserve(Updates.size() + 2 * succ_size(New)); for (BasicBlock *SuccessorOfOld : successors(New)) if (UniqueSuccessorsOfOld.insert(SuccessorOfOld).second) { Updates.push_back({DominatorTree::Insert, New, SuccessorOfOld}); Updates.push_back({DominatorTree::Delete, Old, SuccessorOfOld}); } DTU->applyUpdates(Updates); } else if (DT) // Old dominates New. New node dominates all other nodes dominated by Old. if (DomTreeNode *OldNode = DT->getNode(Old)) { std::vector Children(OldNode->begin(), OldNode->end()); DomTreeNode *NewNode = DT->addNewBlock(New, Old); for (DomTreeNode *I : Children) DT->changeImmediateDominator(I, NewNode); } // Move MemoryAccesses still tracked in Old, but part of New now. // Update accesses in successor blocks accordingly. if (MSSAU) MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin())); return New; } BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName, bool Before) { return SplitBlockImpl(Old, SplitPt, /*DTU=*/nullptr, DT, LI, MSSAU, BBName, Before); } BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, DomTreeUpdater *DTU, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName, bool Before) { return SplitBlockImpl(Old, SplitPt, DTU, /*DT=*/nullptr, LI, MSSAU, BBName, Before); } BasicBlock *llvm::splitBlockBefore(BasicBlock *Old, Instruction *SplitPt, DomTreeUpdater *DTU, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName) { BasicBlock::iterator SplitIt = SplitPt->getIterator(); while (isa(SplitIt) || SplitIt->isEHPad()) ++SplitIt; std::string Name = BBName.str(); BasicBlock *New = Old->splitBasicBlock( SplitIt, Name.empty() ? Old->getName() + ".split" : Name, /* Before=*/true); // The new block lives in whichever loop the old one did. This preserves // LCSSA as well, because we force the split point to be after any PHI nodes. if (LI) if (Loop *L = LI->getLoopFor(Old)) L->addBasicBlockToLoop(New, *LI); if (DTU) { SmallVector DTUpdates; // New dominates Old. The predecessor nodes of the Old node dominate // New node. SmallPtrSet UniquePredecessorsOfOld; DTUpdates.push_back({DominatorTree::Insert, New, Old}); DTUpdates.reserve(DTUpdates.size() + 2 * pred_size(New)); for (BasicBlock *PredecessorOfOld : predecessors(New)) if (UniquePredecessorsOfOld.insert(PredecessorOfOld).second) { DTUpdates.push_back({DominatorTree::Insert, PredecessorOfOld, New}); DTUpdates.push_back({DominatorTree::Delete, PredecessorOfOld, Old}); } DTU->applyUpdates(DTUpdates); // Move MemoryAccesses still tracked in Old, but part of New now. // Update accesses in successor blocks accordingly. if (MSSAU) { MSSAU->applyUpdates(DTUpdates, DTU->getDomTree()); if (VerifyMemorySSA) MSSAU->getMemorySSA()->verifyMemorySSA(); } } return New; } /// Update DominatorTree, LoopInfo, and LCCSA analysis information. static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, ArrayRef Preds, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA, bool &HasLoopExit) { // Update dominator tree if available. if (DTU) { // Recalculation of DomTree is needed when updating a forward DomTree and // the Entry BB is replaced. if (NewBB->isEntryBlock() && DTU->hasDomTree()) { // The entry block was removed and there is no external interface for // the dominator tree to be notified of this change. In this corner-case // we recalculate the entire tree. DTU->recalculate(*NewBB->getParent()); } else { // Split block expects NewBB to have a non-empty set of predecessors. SmallVector Updates; SmallPtrSet UniquePreds; Updates.push_back({DominatorTree::Insert, NewBB, OldBB}); Updates.reserve(Updates.size() + 2 * Preds.size()); for (auto *Pred : Preds) if (UniquePreds.insert(Pred).second) { Updates.push_back({DominatorTree::Insert, Pred, NewBB}); Updates.push_back({DominatorTree::Delete, Pred, OldBB}); } DTU->applyUpdates(Updates); } } else if (DT) { if (OldBB == DT->getRootNode()->getBlock()) { assert(NewBB->isEntryBlock()); DT->setNewRoot(NewBB); } else { // Split block expects NewBB to have a non-empty set of predecessors. DT->splitBlock(NewBB); } } // Update MemoryPhis after split if MemorySSA is available if (MSSAU) MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds); // The rest of the logic is only relevant for updating the loop structures. if (!LI) return; if (DTU && DTU->hasDomTree()) DT = &DTU->getDomTree(); assert(DT && "DT should be available to update LoopInfo!"); Loop *L = LI->getLoopFor(OldBB); // If we need to preserve loop analyses, collect some information about how // this split will affect loops. bool IsLoopEntry = !!L; bool SplitMakesNewLoopHeader = false; for (BasicBlock *Pred : Preds) { // Preds that are not reachable from entry should not be used to identify if // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader // as true and make the NewBB the header of some loop. This breaks LI. if (!DT->isReachableFromEntry(Pred)) continue; // If we need to preserve LCSSA, determine if any of the preds is a loop // exit. if (PreserveLCSSA) if (Loop *PL = LI->getLoopFor(Pred)) if (!PL->contains(OldBB)) HasLoopExit = true; // If we need to preserve LoopInfo, note whether any of the preds crosses // an interesting loop boundary. if (!L) continue; if (L->contains(Pred)) IsLoopEntry = false; else SplitMakesNewLoopHeader = true; } // Unless we have a loop for OldBB, nothing else to do here. if (!L) return; if (IsLoopEntry) { // Add the new block to the nearest enclosing loop (and not an adjacent // loop). To find this, examine each of the predecessors and determine which // loops enclose them, and select the most-nested loop which contains the // loop containing the block being split. Loop *InnermostPredLoop = nullptr; for (BasicBlock *Pred : Preds) { if (Loop *PredLoop = LI->getLoopFor(Pred)) { // Seek a loop which actually contains the block being split (to avoid // adjacent loops). while (PredLoop && !PredLoop->contains(OldBB)) PredLoop = PredLoop->getParentLoop(); // Select the most-nested of these loops which contains the block. if (PredLoop && PredLoop->contains(OldBB) && (!InnermostPredLoop || InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth())) InnermostPredLoop = PredLoop; } } if (InnermostPredLoop) InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI); } else { L->addBasicBlockToLoop(NewBB, *LI); if (SplitMakesNewLoopHeader) L->moveToHeader(NewBB); } } /// Update the PHI nodes in OrigBB to include the values coming from NewBB. /// This also updates AliasAnalysis, if available. static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB, ArrayRef Preds, BranchInst *BI, bool HasLoopExit) { // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB. SmallPtrSet PredSet(Preds.begin(), Preds.end()); for (BasicBlock::iterator I = OrigBB->begin(); isa(I); ) { PHINode *PN = cast(I++); // Check to see if all of the values coming in are the same. If so, we // don't need to create a new PHI node, unless it's needed for LCSSA. Value *InVal = nullptr; if (!HasLoopExit) { InVal = PN->getIncomingValueForBlock(Preds[0]); for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { if (!PredSet.count(PN->getIncomingBlock(i))) continue; if (!InVal) InVal = PN->getIncomingValue(i); else if (InVal != PN->getIncomingValue(i)) { InVal = nullptr; break; } } } if (InVal) { // If all incoming values for the new PHI would be the same, just don't // make a new PHI. Instead, just remove the incoming values from the old // PHI. // NOTE! This loop walks backwards for a reason! First off, this minimizes // the cost of removal if we end up removing a large number of values, and // second off, this ensures that the indices for the incoming values // aren't invalidated when we remove one. for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) if (PredSet.count(PN->getIncomingBlock(i))) PN->removeIncomingValue(i, false); // Add an incoming value to the PHI node in the loop for the preheader // edge. PN->addIncoming(InVal, NewBB); continue; } // If the values coming into the block are not the same, we need a new // PHI. // Create the new PHI node, insert it into NewBB at the end of the block PHINode *NewPHI = PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI); // NOTE! This loop walks backwards for a reason! First off, this minimizes // the cost of removal if we end up removing a large number of values, and // second off, this ensures that the indices for the incoming values aren't // invalidated when we remove one. for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) { BasicBlock *IncomingBB = PN->getIncomingBlock(i); if (PredSet.count(IncomingBB)) { Value *V = PN->removeIncomingValue(i, false); NewPHI->addIncoming(V, IncomingBB); } } PN->addIncoming(NewPHI, NewBB); } } static void SplitLandingPadPredecessorsImpl( BasicBlock *OrigBB, ArrayRef Preds, const char *Suffix1, const char *Suffix2, SmallVectorImpl &NewBBs, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA); static BasicBlock * SplitBlockPredecessorsImpl(BasicBlock *BB, ArrayRef Preds, const char *Suffix, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA) { // Do not attempt to split that which cannot be split. if (!BB->canSplitPredecessors()) return nullptr; // For the landingpads we need to act a bit differently. // Delegate this work to the SplitLandingPadPredecessors. if (BB->isLandingPad()) { SmallVector NewBBs; std::string NewName = std::string(Suffix) + ".split-lp"; SplitLandingPadPredecessorsImpl(BB, Preds, Suffix, NewName.c_str(), NewBBs, DTU, DT, LI, MSSAU, PreserveLCSSA); return NewBBs[0]; } // Create new basic block, insert right before the original block. BasicBlock *NewBB = BasicBlock::Create( BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB); // The new block unconditionally branches to the old block. BranchInst *BI = BranchInst::Create(BB, NewBB); Loop *L = nullptr; BasicBlock *OldLatch = nullptr; // Splitting the predecessors of a loop header creates a preheader block. if (LI && LI->isLoopHeader(BB)) { L = LI->getLoopFor(BB); // Using the loop start line number prevents debuggers stepping into the // loop body for this instruction. BI->setDebugLoc(L->getStartLoc()); // If BB is the header of the Loop, it is possible that the loop is // modified, such that the current latch does not remain the latch of the // loop. If that is the case, the loop metadata from the current latch needs // to be applied to the new latch. OldLatch = L->getLoopLatch(); } else BI->setDebugLoc(BB->getFirstNonPHIOrDbg()->getDebugLoc()); // Move the edges from Preds to point to NewBB instead of BB. for (unsigned i = 0, e = Preds.size(); i != e; ++i) { // This is slightly more strict than necessary; the minimum requirement // is that there be no more than one indirectbr branching to BB. And // all BlockAddress uses would need to be updated. assert(!isa(Preds[i]->getTerminator()) && "Cannot split an edge from an IndirectBrInst"); assert(!isa(Preds[i]->getTerminator()) && "Cannot split an edge from a CallBrInst"); Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB); } // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI // node becomes an incoming value for BB's phi node. However, if the Preds // list is empty, we need to insert dummy entries into the PHI nodes in BB to // account for the newly created predecessor. if (Preds.empty()) { // Insert dummy values as the incoming value. for (BasicBlock::iterator I = BB->begin(); isa(I); ++I) cast(I)->addIncoming(UndefValue::get(I->getType()), NewBB); } // Update DominatorTree, LoopInfo, and LCCSA analysis information. bool HasLoopExit = false; UpdateAnalysisInformation(BB, NewBB, Preds, DTU, DT, LI, MSSAU, PreserveLCSSA, HasLoopExit); if (!Preds.empty()) { // Update the PHI nodes in BB with the values coming from NewBB. UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit); } if (OldLatch) { BasicBlock *NewLatch = L->getLoopLatch(); if (NewLatch != OldLatch) { MDNode *MD = OldLatch->getTerminator()->getMetadata("llvm.loop"); NewLatch->getTerminator()->setMetadata("llvm.loop", MD); OldLatch->getTerminator()->setMetadata("llvm.loop", nullptr); } } return NewBB; } BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, ArrayRef Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA) { return SplitBlockPredecessorsImpl(BB, Preds, Suffix, /*DTU=*/nullptr, DT, LI, MSSAU, PreserveLCSSA); } BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, ArrayRef Preds, const char *Suffix, DomTreeUpdater *DTU, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA) { return SplitBlockPredecessorsImpl(BB, Preds, Suffix, DTU, /*DT=*/nullptr, LI, MSSAU, PreserveLCSSA); } static void SplitLandingPadPredecessorsImpl( BasicBlock *OrigBB, ArrayRef Preds, const char *Suffix1, const char *Suffix2, SmallVectorImpl &NewBBs, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA) { assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!"); // Create a new basic block for OrigBB's predecessors listed in Preds. Insert // it right before the original block. BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(), OrigBB->getName() + Suffix1, OrigBB->getParent(), OrigBB); NewBBs.push_back(NewBB1); // The new block unconditionally branches to the old block. BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1); BI1->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc()); // Move the edges from Preds to point to NewBB1 instead of OrigBB. for (unsigned i = 0, e = Preds.size(); i != e; ++i) { // This is slightly more strict than necessary; the minimum requirement // is that there be no more than one indirectbr branching to BB. And // all BlockAddress uses would need to be updated. assert(!isa(Preds[i]->getTerminator()) && "Cannot split an edge from an IndirectBrInst"); Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1); } bool HasLoopExit = false; UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DTU, DT, LI, MSSAU, PreserveLCSSA, HasLoopExit); // Update the PHI nodes in OrigBB with the values coming from NewBB1. UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit); // Move the remaining edges from OrigBB to point to NewBB2. SmallVector NewBB2Preds; for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB); i != e; ) { BasicBlock *Pred = *i++; if (Pred == NewBB1) continue; assert(!isa(Pred->getTerminator()) && "Cannot split an edge from an IndirectBrInst"); NewBB2Preds.push_back(Pred); e = pred_end(OrigBB); } BasicBlock *NewBB2 = nullptr; if (!NewBB2Preds.empty()) { // Create another basic block for the rest of OrigBB's predecessors. NewBB2 = BasicBlock::Create(OrigBB->getContext(), OrigBB->getName() + Suffix2, OrigBB->getParent(), OrigBB); NewBBs.push_back(NewBB2); // The new block unconditionally branches to the old block. BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2); BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc()); // Move the remaining edges from OrigBB to point to NewBB2. for (BasicBlock *NewBB2Pred : NewBB2Preds) NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2); // Update DominatorTree, LoopInfo, and LCCSA analysis information. HasLoopExit = false; UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DTU, DT, LI, MSSAU, PreserveLCSSA, HasLoopExit); // Update the PHI nodes in OrigBB with the values coming from NewBB2. UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit); } LandingPadInst *LPad = OrigBB->getLandingPadInst(); Instruction *Clone1 = LPad->clone(); Clone1->setName(Twine("lpad") + Suffix1); NewBB1->getInstList().insert(NewBB1->getFirstInsertionPt(), Clone1); if (NewBB2) { Instruction *Clone2 = LPad->clone(); Clone2->setName(Twine("lpad") + Suffix2); NewBB2->getInstList().insert(NewBB2->getFirstInsertionPt(), Clone2); // Create a PHI node for the two cloned landingpad instructions only // if the original landingpad instruction has some uses. if (!LPad->use_empty()) { assert(!LPad->getType()->isTokenTy() && "Split cannot be applied if LPad is token type. Otherwise an " "invalid PHINode of token type would be created."); PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad); PN->addIncoming(Clone1, NewBB1); PN->addIncoming(Clone2, NewBB2); LPad->replaceAllUsesWith(PN); } LPad->eraseFromParent(); } else { // There is no second clone. Just replace the landing pad with the first // clone. LPad->replaceAllUsesWith(Clone1); LPad->eraseFromParent(); } } void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef Preds, const char *Suffix1, const char *Suffix2, SmallVectorImpl &NewBBs, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA) { return SplitLandingPadPredecessorsImpl( OrigBB, Preds, Suffix1, Suffix2, NewBBs, /*DTU=*/nullptr, DT, LI, MSSAU, PreserveLCSSA); } void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef Preds, const char *Suffix1, const char *Suffix2, SmallVectorImpl &NewBBs, DomTreeUpdater *DTU, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA) { return SplitLandingPadPredecessorsImpl(OrigBB, Preds, Suffix1, Suffix2, NewBBs, DTU, /*DT=*/nullptr, LI, MSSAU, PreserveLCSSA); } ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, BasicBlock *Pred, DomTreeUpdater *DTU) { Instruction *UncondBranch = Pred->getTerminator(); // Clone the return and add it to the end of the predecessor. Instruction *NewRet = RI->clone(); Pred->getInstList().push_back(NewRet); // If the return instruction returns a value, and if the value was a // PHI node in "BB", propagate the right value into the return. for (Use &Op : NewRet->operands()) { Value *V = Op; Instruction *NewBC = nullptr; if (BitCastInst *BCI = dyn_cast(V)) { // Return value might be bitcasted. Clone and insert it before the // return instruction. V = BCI->getOperand(0); NewBC = BCI->clone(); Pred->getInstList().insert(NewRet->getIterator(), NewBC); Op = NewBC; } Instruction *NewEV = nullptr; if (ExtractValueInst *EVI = dyn_cast(V)) { V = EVI->getOperand(0); NewEV = EVI->clone(); if (NewBC) { NewBC->setOperand(0, NewEV); Pred->getInstList().insert(NewBC->getIterator(), NewEV); } else { Pred->getInstList().insert(NewRet->getIterator(), NewEV); Op = NewEV; } } if (PHINode *PN = dyn_cast(V)) { if (PN->getParent() == BB) { if (NewEV) { NewEV->setOperand(0, PN->getIncomingValueForBlock(Pred)); } else if (NewBC) NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred)); else Op = PN->getIncomingValueForBlock(Pred); } } } // Update any PHI nodes in the returning block to realize that we no // longer branch to them. BB->removePredecessor(Pred); UncondBranch->eraseFromParent(); if (DTU) DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}}); return cast(NewRet); } static Instruction * SplitBlockAndInsertIfThenImpl(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, BasicBlock *ThenBlock) { SmallVector Updates; BasicBlock *Head = SplitBefore->getParent(); BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator()); if (DTU) { SmallPtrSet UniqueSuccessorsOfHead; Updates.push_back({DominatorTree::Insert, Head, Tail}); Updates.reserve(Updates.size() + 2 * succ_size(Tail)); for (BasicBlock *SuccessorOfHead : successors(Tail)) if (UniqueSuccessorsOfHead.insert(SuccessorOfHead).second) { Updates.push_back({DominatorTree::Insert, Tail, SuccessorOfHead}); Updates.push_back({DominatorTree::Delete, Head, SuccessorOfHead}); } } Instruction *HeadOldTerm = Head->getTerminator(); LLVMContext &C = Head->getContext(); Instruction *CheckTerm; bool CreateThenBlock = (ThenBlock == nullptr); if (CreateThenBlock) { ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail); if (Unreachable) CheckTerm = new UnreachableInst(C, ThenBlock); else { CheckTerm = BranchInst::Create(Tail, ThenBlock); if (DTU) Updates.push_back({DominatorTree::Insert, ThenBlock, Tail}); } CheckTerm->setDebugLoc(SplitBefore->getDebugLoc()); } else CheckTerm = ThenBlock->getTerminator(); BranchInst *HeadNewTerm = BranchInst::Create(/*ifTrue*/ ThenBlock, /*ifFalse*/ Tail, Cond); if (DTU) Updates.push_back({DominatorTree::Insert, Head, ThenBlock}); HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights); ReplaceInstWithInst(HeadOldTerm, HeadNewTerm); if (DTU) DTU->applyUpdates(Updates); else if (DT) { if (DomTreeNode *OldNode = DT->getNode(Head)) { std::vector Children(OldNode->begin(), OldNode->end()); DomTreeNode *NewNode = DT->addNewBlock(Tail, Head); for (DomTreeNode *Child : Children) DT->changeImmediateDominator(Child, NewNode); // Head dominates ThenBlock. if (CreateThenBlock) DT->addNewBlock(ThenBlock, Head); else DT->changeImmediateDominator(ThenBlock, Head); } } if (LI) { if (Loop *L = LI->getLoopFor(Head)) { L->addBasicBlockToLoop(ThenBlock, *LI); L->addBasicBlockToLoop(Tail, *LI); } } return CheckTerm; } Instruction *llvm::SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights, DominatorTree *DT, LoopInfo *LI, BasicBlock *ThenBlock) { return SplitBlockAndInsertIfThenImpl(Cond, SplitBefore, Unreachable, BranchWeights, /*DTU=*/nullptr, DT, LI, ThenBlock); } Instruction *llvm::SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights, DomTreeUpdater *DTU, LoopInfo *LI, BasicBlock *ThenBlock) { return SplitBlockAndInsertIfThenImpl(Cond, SplitBefore, Unreachable, BranchWeights, DTU, /*DT=*/nullptr, LI, ThenBlock); } void llvm::SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, Instruction **ThenTerm, Instruction **ElseTerm, MDNode *BranchWeights) { BasicBlock *Head = SplitBefore->getParent(); BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator()); Instruction *HeadOldTerm = Head->getTerminator(); LLVMContext &C = Head->getContext(); BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail); BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail); *ThenTerm = BranchInst::Create(Tail, ThenBlock); (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc()); *ElseTerm = BranchInst::Create(Tail, ElseBlock); (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc()); BranchInst *HeadNewTerm = BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond); HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights); ReplaceInstWithInst(HeadOldTerm, HeadNewTerm); } BranchInst *llvm::GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse) { PHINode *SomePHI = dyn_cast(BB->begin()); BasicBlock *Pred1 = nullptr; BasicBlock *Pred2 = nullptr; if (SomePHI) { if (SomePHI->getNumIncomingValues() != 2) return nullptr; Pred1 = SomePHI->getIncomingBlock(0); Pred2 = SomePHI->getIncomingBlock(1); } else { pred_iterator PI = pred_begin(BB), PE = pred_end(BB); if (PI == PE) // No predecessor return nullptr; Pred1 = *PI++; if (PI == PE) // Only one predecessor return nullptr; Pred2 = *PI++; if (PI != PE) // More than two predecessors return nullptr; } // We can only handle branches. Other control flow will be lowered to // branches if possible anyway. BranchInst *Pred1Br = dyn_cast(Pred1->getTerminator()); BranchInst *Pred2Br = dyn_cast(Pred2->getTerminator()); if (!Pred1Br || !Pred2Br) return nullptr; // Eliminate code duplication by ensuring that Pred1Br is conditional if // either are. if (Pred2Br->isConditional()) { // If both branches are conditional, we don't have an "if statement". In // reality, we could transform this case, but since the condition will be // required anyway, we stand no chance of eliminating it, so the xform is // probably not profitable. if (Pred1Br->isConditional()) return nullptr; std::swap(Pred1, Pred2); std::swap(Pred1Br, Pred2Br); } if (Pred1Br->isConditional()) { // The only thing we have to watch out for here is to make sure that Pred2 // doesn't have incoming edges from other blocks. If it does, the condition // doesn't dominate BB. if (!Pred2->getSinglePredecessor()) return nullptr; // If we found a conditional branch predecessor, make sure that it branches // to BB and Pred2Br. If it doesn't, this isn't an "if statement". if (Pred1Br->getSuccessor(0) == BB && Pred1Br->getSuccessor(1) == Pred2) { IfTrue = Pred1; IfFalse = Pred2; } else if (Pred1Br->getSuccessor(0) == Pred2 && Pred1Br->getSuccessor(1) == BB) { IfTrue = Pred2; IfFalse = Pred1; } else { // We know that one arm of the conditional goes to BB, so the other must // go somewhere unrelated, and this must not be an "if statement". return nullptr; } return Pred1Br; } // Ok, if we got here, both predecessors end with an unconditional branch to // BB. Don't panic! If both blocks only have a single (identical) // predecessor, and THAT is a conditional branch, then we're all ok! BasicBlock *CommonPred = Pred1->getSinglePredecessor(); if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor()) return nullptr; // Otherwise, if this is a conditional branch, then we can use it! BranchInst *BI = dyn_cast(CommonPred->getTerminator()); if (!BI) return nullptr; assert(BI->isConditional() && "Two successors but not conditional?"); if (BI->getSuccessor(0) == Pred1) { IfTrue = Pred1; IfFalse = Pred2; } else { IfTrue = Pred2; IfFalse = Pred1; } return BI; } // After creating a control flow hub, the operands of PHINodes in an outgoing // block Out no longer match the predecessors of that block. Predecessors of Out // that are incoming blocks to the hub are now replaced by just one edge from // the hub. To match this new control flow, the corresponding values from each // PHINode must now be moved a new PHINode in the first guard block of the hub. // // This operation cannot be performed with SSAUpdater, because it involves one // new use: If the block Out is in the list of Incoming blocks, then the newly // created PHI in the Hub will use itself along that edge from Out to Hub. static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock, const SetVector &Incoming, BasicBlock *FirstGuardBlock) { auto I = Out->begin(); while (I != Out->end() && isa(I)) { auto Phi = cast(I); auto NewPhi = PHINode::Create(Phi->getType(), Incoming.size(), Phi->getName() + ".moved", &FirstGuardBlock->back()); for (auto In : Incoming) { Value *V = UndefValue::get(Phi->getType()); if (In == Out) { V = NewPhi; } else if (Phi->getBasicBlockIndex(In) != -1) { V = Phi->removeIncomingValue(In, false); } NewPhi->addIncoming(V, In); } assert(NewPhi->getNumIncomingValues() == Incoming.size()); if (Phi->getNumOperands() == 0) { Phi->replaceAllUsesWith(NewPhi); I = Phi->eraseFromParent(); continue; } Phi->addIncoming(NewPhi, GuardBlock); ++I; } } using BBPredicates = DenseMap; using BBSetVector = SetVector; // Redirects the terminator of the incoming block to the first guard // block in the hub. The condition of the original terminator (if it // was conditional) and its original successors are returned as a // tuple . The function additionally filters // out successors that are not in the set of outgoing blocks. // // - condition is non-null iff the branch is conditional. // - Succ1 is non-null iff the sole/taken target is an outgoing block. // - Succ2 is non-null iff condition is non-null and the fallthrough // target is an outgoing block. static std::tuple redirectToHub(BasicBlock *BB, BasicBlock *FirstGuardBlock, const BBSetVector &Outgoing) { auto Branch = cast(BB->getTerminator()); auto Condition = Branch->isConditional() ? Branch->getCondition() : nullptr; BasicBlock *Succ0 = Branch->getSuccessor(0); BasicBlock *Succ1 = nullptr; Succ0 = Outgoing.count(Succ0) ? Succ0 : nullptr; if (Branch->isUnconditional()) { Branch->setSuccessor(0, FirstGuardBlock); assert(Succ0); } else { Succ1 = Branch->getSuccessor(1); Succ1 = Outgoing.count(Succ1) ? Succ1 : nullptr; assert(Succ0 || Succ1); if (Succ0 && !Succ1) { Branch->setSuccessor(0, FirstGuardBlock); } else if (Succ1 && !Succ0) { Branch->setSuccessor(1, FirstGuardBlock); } else { Branch->eraseFromParent(); BranchInst::Create(FirstGuardBlock, BB); } } assert(Succ0 || Succ1); return std::make_tuple(Condition, Succ0, Succ1); } // Capture the existing control flow as guard predicates, and redirect // control flow from every incoming block to the first guard block in // the hub. // // There is one guard predicate for each outgoing block OutBB. The // predicate is a PHINode with one input for each InBB which // represents whether the hub should transfer control flow to OutBB if // it arrived from InBB. These predicates are NOT ORTHOGONAL. The Hub // evaluates them in the same order as the Outgoing set-vector, and // control branches to the first outgoing block whose predicate // evaluates to true. static void convertToGuardPredicates( BasicBlock *FirstGuardBlock, BBPredicates &GuardPredicates, SmallVectorImpl &DeletionCandidates, const BBSetVector &Incoming, const BBSetVector &Outgoing) { auto &Context = Incoming.front()->getContext(); auto BoolTrue = ConstantInt::getTrue(Context); auto BoolFalse = ConstantInt::getFalse(Context); // The predicate for the last outgoing is trivially true, and so we // process only the first N-1 successors. for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) { auto Out = Outgoing[i]; LLVM_DEBUG(dbgs() << "Creating guard for " << Out->getName() << "\n"); auto Phi = PHINode::Create(Type::getInt1Ty(Context), Incoming.size(), StringRef("Guard.") + Out->getName(), FirstGuardBlock); GuardPredicates[Out] = Phi; } for (auto In : Incoming) { Value *Condition; BasicBlock *Succ0; BasicBlock *Succ1; std::tie(Condition, Succ0, Succ1) = redirectToHub(In, FirstGuardBlock, Outgoing); // Optimization: Consider an incoming block A with both successors // Succ0 and Succ1 in the set of outgoing blocks. The predicates // for Succ0 and Succ1 complement each other. If Succ0 is visited // first in the loop below, control will branch to Succ0 using the // corresponding predicate. But if that branch is not taken, then // control must reach Succ1, which means that the predicate for // Succ1 is always true. bool OneSuccessorDone = false; for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) { auto Out = Outgoing[i]; auto Phi = GuardPredicates[Out]; if (Out != Succ0 && Out != Succ1) { Phi->addIncoming(BoolFalse, In); continue; } // Optimization: When only one successor is an outgoing block, // the predicate is always true. if (!Succ0 || !Succ1 || OneSuccessorDone) { Phi->addIncoming(BoolTrue, In); continue; } assert(Succ0 && Succ1); OneSuccessorDone = true; if (Out == Succ0) { Phi->addIncoming(Condition, In); continue; } auto Inverted = invertCondition(Condition); DeletionCandidates.push_back(Condition); Phi->addIncoming(Inverted, In); } } } // For each outgoing block OutBB, create a guard block in the Hub. The // first guard block was already created outside, and available as the // first element in the vector of guard blocks. // // Each guard block terminates in a conditional branch that transfers // control to the corresponding outgoing block or the next guard // block. The last guard block has two outgoing blocks as successors // since the condition for the final outgoing block is trivially // true. So we create one less block (including the first guard block) // than the number of outgoing blocks. static void createGuardBlocks(SmallVectorImpl &GuardBlocks, Function *F, const BBSetVector &Outgoing, BBPredicates &GuardPredicates, StringRef Prefix) { for (int i = 0, e = Outgoing.size() - 2; i != e; ++i) { GuardBlocks.push_back( BasicBlock::Create(F->getContext(), Prefix + ".guard", F)); } assert(GuardBlocks.size() == GuardPredicates.size()); // To help keep the loop simple, temporarily append the last // outgoing block to the list of guard blocks. GuardBlocks.push_back(Outgoing.back()); for (int i = 0, e = GuardBlocks.size() - 1; i != e; ++i) { auto Out = Outgoing[i]; assert(GuardPredicates.count(Out)); BranchInst::Create(Out, GuardBlocks[i + 1], GuardPredicates[Out], GuardBlocks[i]); } // Remove the last block from the guard list. GuardBlocks.pop_back(); } BasicBlock *llvm::CreateControlFlowHub( DomTreeUpdater *DTU, SmallVectorImpl &GuardBlocks, const BBSetVector &Incoming, const BBSetVector &Outgoing, const StringRef Prefix) { auto F = Incoming.front()->getParent(); auto FirstGuardBlock = BasicBlock::Create(F->getContext(), Prefix + ".guard", F); SmallVector Updates; if (DTU) { for (auto In : Incoming) { Updates.push_back({DominatorTree::Insert, In, FirstGuardBlock}); for (auto Succ : successors(In)) { if (Outgoing.count(Succ)) Updates.push_back({DominatorTree::Delete, In, Succ}); } } } BBPredicates GuardPredicates; SmallVector DeletionCandidates; convertToGuardPredicates(FirstGuardBlock, GuardPredicates, DeletionCandidates, Incoming, Outgoing); GuardBlocks.push_back(FirstGuardBlock); createGuardBlocks(GuardBlocks, F, Outgoing, GuardPredicates, Prefix); // Update the PHINodes in each outgoing block to match the new control flow. for (int i = 0, e = GuardBlocks.size(); i != e; ++i) { reconnectPhis(Outgoing[i], GuardBlocks[i], Incoming, FirstGuardBlock); } reconnectPhis(Outgoing.back(), GuardBlocks.back(), Incoming, FirstGuardBlock); if (DTU) { int NumGuards = GuardBlocks.size(); assert((int)Outgoing.size() == NumGuards + 1); for (int i = 0; i != NumGuards - 1; ++i) { Updates.push_back({DominatorTree::Insert, GuardBlocks[i], Outgoing[i]}); Updates.push_back( {DominatorTree::Insert, GuardBlocks[i], GuardBlocks[i + 1]}); } Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1], Outgoing[NumGuards - 1]}); Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1], Outgoing[NumGuards]}); DTU->applyUpdates(Updates); } for (auto I : DeletionCandidates) { if (I->use_empty()) if (auto Inst = dyn_cast_or_null(I)) Inst->eraseFromParent(); } return FirstGuardBlock; }