1193323Sed//===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// BreakCriticalEdges pass - Break all of the critical edges in the CFG by 10193323Sed// inserting a dummy basic block. This pass may be "required" by passes that 11193323Sed// cannot deal with critical edges. For this usage, the structure type is 12193323Sed// forward declared. This pass obviously invalidates the CFG, but can update 13218893Sdim// dominator trees. 14193323Sed// 15193323Sed//===----------------------------------------------------------------------===// 16193323Sed 17314564Sdim#include "llvm/Transforms/Utils/BreakCriticalEdges.h" 18327952Sdim#include "llvm/ADT/SetVector.h" 19249423Sdim#include "llvm/ADT/SmallVector.h" 20249423Sdim#include "llvm/ADT/Statistic.h" 21327952Sdim#include "llvm/Analysis/BlockFrequencyInfo.h" 22327952Sdim#include "llvm/Analysis/BranchProbabilityInfo.h" 23261991Sdim#include "llvm/Analysis/CFG.h" 24193323Sed#include "llvm/Analysis/LoopInfo.h" 25344779Sdim#include "llvm/Analysis/MemorySSAUpdater.h" 26353358Sdim#include "llvm/Analysis/PostDominators.h" 27276479Sdim#include "llvm/IR/CFG.h" 28276479Sdim#include "llvm/IR/Dominators.h" 29249423Sdim#include "llvm/IR/Instructions.h" 30249423Sdim#include "llvm/IR/Type.h" 31360784Sdim#include "llvm/InitializePasses.h" 32198090Srdivacky#include "llvm/Support/ErrorHandling.h" 33341825Sdim#include "llvm/Transforms/Utils.h" 34249423Sdim#include "llvm/Transforms/Utils/BasicBlockUtils.h" 35327952Sdim#include "llvm/Transforms/Utils/Cloning.h" 36327952Sdim#include "llvm/Transforms/Utils/ValueMapper.h" 37193323Sedusing namespace llvm; 38193323Sed 39276479Sdim#define DEBUG_TYPE "break-crit-edges" 40276479Sdim 41193323SedSTATISTIC(NumBroken, "Number of blocks inserted"); 42193323Sed 43193323Sednamespace { 44198892Srdivacky struct BreakCriticalEdges : public FunctionPass { 45193323Sed static char ID; // Pass identification, replacement for typeid 46218893Sdim BreakCriticalEdges() : FunctionPass(ID) { 47218893Sdim initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry()); 48218893Sdim } 49193323Sed 50280031Sdim bool runOnFunction(Function &F) override { 51288943Sdim auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 52288943Sdim auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; 53353358Sdim 54353358Sdim auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>(); 55353358Sdim auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr; 56353358Sdim 57288943Sdim auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>(); 58288943Sdim auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; 59288943Sdim unsigned N = 60353358Sdim SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions(DT, LI, nullptr, PDT)); 61280031Sdim NumBroken += N; 62280031Sdim return N > 0; 63280031Sdim } 64193323Sed 65276479Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 66276479Sdim AU.addPreserved<DominatorTreeWrapperPass>(); 67288943Sdim AU.addPreserved<LoopInfoWrapperPass>(); 68193323Sed 69193323Sed // No loop canonicalization guarantees are broken by this pass. 70193323Sed AU.addPreservedID(LoopSimplifyID); 71193323Sed } 72193323Sed }; 73193323Sed} 74193323Sed 75193323Sedchar BreakCriticalEdges::ID = 0; 76212904SdimINITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges", 77218893Sdim "Break critical edges in CFG", false, false) 78193323Sed 79221345Sdim// Publicly exposed interface to pass... 80212904Sdimchar &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID; 81193323SedFunctionPass *llvm::createBreakCriticalEdgesPass() { 82193323Sed return new BreakCriticalEdges(); 83193323Sed} 84193323Sed 85314564SdimPreservedAnalyses BreakCriticalEdgesPass::run(Function &F, 86314564Sdim FunctionAnalysisManager &AM) { 87314564Sdim auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F); 88314564Sdim auto *LI = AM.getCachedResult<LoopAnalysis>(F); 89314564Sdim unsigned N = SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions(DT, LI)); 90314564Sdim NumBroken += N; 91314564Sdim if (N == 0) 92314564Sdim return PreservedAnalyses::all(); 93314564Sdim PreservedAnalyses PA; 94314564Sdim PA.preserve<DominatorTreeAnalysis>(); 95314564Sdim PA.preserve<LoopAnalysis>(); 96314564Sdim return PA; 97314564Sdim} 98314564Sdim 99193323Sed//===----------------------------------------------------------------------===// 100193323Sed// Implementation of the external critical edge manipulation functions 101193323Sed//===----------------------------------------------------------------------===// 102193323Sed 103309124Sdim/// When a loop exit edge is split, LCSSA form may require new PHIs in the new 104309124Sdim/// exit block. This function inserts the new PHIs, as needed. Preds is a list 105309124Sdim/// of preds inside the loop, SplitBB is the new loop exit block, and DestBB is 106309124Sdim/// the old loop exit, now the successor of SplitBB. 107239462Sdimstatic void createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds, 108198090Srdivacky BasicBlock *SplitBB, 109198090Srdivacky BasicBlock *DestBB) { 110198090Srdivacky // SplitBB shouldn't have anything non-trivial in it yet. 111234982Sdim assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() || 112234982Sdim SplitBB->isLandingPad()) && "SplitBB has non-PHI nodes!"); 113198090Srdivacky 114234982Sdim // For each PHI in the destination block. 115327952Sdim for (PHINode &PN : DestBB->phis()) { 116327952Sdim unsigned Idx = PN.getBasicBlockIndex(SplitBB); 117327952Sdim Value *V = PN.getIncomingValue(Idx); 118234982Sdim 119198090Srdivacky // If the input is a PHI which already satisfies LCSSA, don't create 120198090Srdivacky // a new one. 121198090Srdivacky if (const PHINode *VP = dyn_cast<PHINode>(V)) 122198090Srdivacky if (VP->getParent() == SplitBB) 123198090Srdivacky continue; 124234982Sdim 125198090Srdivacky // Otherwise a new PHI is needed. Create one and populate it. 126296417Sdim PHINode *NewPN = PHINode::Create( 127327952Sdim PN.getType(), Preds.size(), "split", 128296417Sdim SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator()); 129198090Srdivacky for (unsigned i = 0, e = Preds.size(); i != e; ++i) 130198090Srdivacky NewPN->addIncoming(V, Preds[i]); 131234982Sdim 132198090Srdivacky // Update the original PHI. 133327952Sdim PN.setIncomingValue(Idx, NewPN); 134198090Srdivacky } 135198090Srdivacky} 136198090Srdivacky 137309124SdimBasicBlock * 138344779Sdimllvm::SplitCriticalEdge(Instruction *TI, unsigned SuccNum, 139309124Sdim const CriticalEdgeSplittingOptions &Options) { 140288943Sdim if (!isCriticalEdge(TI, SuccNum, Options.MergeIdenticalEdges)) 141288943Sdim return nullptr; 142226633Sdim 143198892Srdivacky assert(!isa<IndirectBrInst>(TI) && 144198892Srdivacky "Cannot split critical edge from IndirectBrInst"); 145226633Sdim 146193323Sed BasicBlock *TIBB = TI->getParent(); 147193323Sed BasicBlock *DestBB = TI->getSuccessor(SuccNum); 148193323Sed 149296417Sdim // Splitting the critical edge to a pad block is non-trivial. Don't do 150226633Sdim // it in this generic function. 151296417Sdim if (DestBB->isEHPad()) return nullptr; 152226633Sdim 153353358Sdim // Don't split the non-fallthrough edge from a callbr. 154353358Sdim if (isa<CallBrInst>(TI) && SuccNum > 0) 155353358Sdim return nullptr; 156353358Sdim 157353358Sdim if (Options.IgnoreUnreachableDests && 158353358Sdim isa<UnreachableInst>(DestBB->getFirstNonPHIOrDbgOrLifetime())) 159353358Sdim return nullptr; 160353358Sdim 161193323Sed // Create a new basic block, linking it into the CFG. 162198090Srdivacky BasicBlock *NewBB = BasicBlock::Create(TI->getContext(), 163198090Srdivacky TIBB->getName() + "." + DestBB->getName() + "_crit_edge"); 164203954Srdivacky // Create our unconditional branch. 165223017Sdim BranchInst *NewBI = BranchInst::Create(DestBB, NewBB); 166223017Sdim NewBI->setDebugLoc(TI->getDebugLoc()); 167193323Sed 168193323Sed // Branch to the new block, breaking the edge. 169193323Sed TI->setSuccessor(SuccNum, NewBB); 170193323Sed 171193323Sed // Insert the block into the function... right after the block TI lives in. 172193323Sed Function &F = *TIBB->getParent(); 173296417Sdim Function::iterator FBBI = TIBB->getIterator(); 174193323Sed F.getBasicBlockList().insert(++FBBI, NewBB); 175226633Sdim 176193323Sed // If there are any PHI nodes in DestBB, we need to update them so that they 177193323Sed // merge incoming values from NewBB instead of from TIBB. 178224145Sdim { 179224145Sdim unsigned BBIdx = 0; 180224145Sdim for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) { 181224145Sdim // We no longer enter through TIBB, now we come in through NewBB. 182224145Sdim // Revector exactly one entry in the PHI node that used to come from 183224145Sdim // TIBB to come from NewBB. 184224145Sdim PHINode *PN = cast<PHINode>(I); 185224145Sdim 186224145Sdim // Reuse the previous value of BBIdx if it lines up. In cases where we 187224145Sdim // have multiple phi nodes with *lots* of predecessors, this is a speed 188224145Sdim // win because we don't have to scan the PHI looking for TIBB. This 189224145Sdim // happens because the BB list of PHI nodes are usually in the same 190224145Sdim // order. 191224145Sdim if (PN->getIncomingBlock(BBIdx) != TIBB) 192226633Sdim BBIdx = PN->getBasicBlockIndex(TIBB); 193224145Sdim PN->setIncomingBlock(BBIdx, NewBB); 194203954Srdivacky } 195193323Sed } 196226633Sdim 197193323Sed // If there are any other edges from TIBB to DestBB, update those to go 198193323Sed // through the split block, making those edges non-critical as well (and 199193323Sed // reducing the number of phi entries in the DestBB if relevant). 200288943Sdim if (Options.MergeIdenticalEdges) { 201193323Sed for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) { 202193323Sed if (TI->getSuccessor(i) != DestBB) continue; 203226633Sdim 204193323Sed // Remove an entry for TIBB from DestBB phi nodes. 205353358Sdim DestBB->removePredecessor(TIBB, Options.KeepOneInputPHIs); 206226633Sdim 207193323Sed // We found another edge to DestBB, go to NewBB instead. 208193323Sed TI->setSuccessor(i, NewBB); 209193323Sed } 210193323Sed } 211193323Sed 212203954Srdivacky // If we have nothing to update, just return. 213288943Sdim auto *DT = Options.DT; 214353358Sdim auto *PDT = Options.PDT; 215288943Sdim auto *LI = Options.LI; 216344779Sdim auto *MSSAU = Options.MSSAU; 217344779Sdim if (MSSAU) 218344779Sdim MSSAU->wireOldPredecessorsToNewImmediatePredecessor( 219344779Sdim DestBB, NewBB, {TIBB}, Options.MergeIdenticalEdges); 220344779Sdim 221353358Sdim if (!DT && !PDT && !LI) 222203954Srdivacky return NewBB; 223193323Sed 224353358Sdim if (DT || PDT) { 225327952Sdim // Update the DominatorTree. 226327952Sdim // ---> NewBB -----\ 227327952Sdim // / V 228327952Sdim // TIBB -------\\------> DestBB 229193323Sed // 230327952Sdim // First, inform the DT about the new path from TIBB to DestBB via NewBB, 231327952Sdim // then delete the old edge from TIBB to DestBB. By doing this in that order 232327952Sdim // DestBB stays reachable in the DT the whole time and its subtree doesn't 233327952Sdim // get disconnected. 234327952Sdim SmallVector<DominatorTree::UpdateType, 3> Updates; 235327952Sdim Updates.push_back({DominatorTree::Insert, TIBB, NewBB}); 236327952Sdim Updates.push_back({DominatorTree::Insert, NewBB, DestBB}); 237327952Sdim if (llvm::find(successors(TIBB), DestBB) == succ_end(TIBB)) 238327952Sdim Updates.push_back({DominatorTree::Delete, TIBB, DestBB}); 239226633Sdim 240353358Sdim if (DT) 241353358Sdim DT->applyUpdates(Updates); 242353358Sdim if (PDT) 243353358Sdim PDT->applyUpdates(Updates); 244193323Sed } 245193323Sed 246193323Sed // Update LoopInfo if it is around. 247203954Srdivacky if (LI) { 248198090Srdivacky if (Loop *TIL = LI->getLoopFor(TIBB)) { 249198090Srdivacky // If one or the other blocks were not in a loop, the new block is not 250198090Srdivacky // either, and thus LI doesn't need to be updated. 251193323Sed if (Loop *DestLoop = LI->getLoopFor(DestBB)) { 252193323Sed if (TIL == DestLoop) { 253193323Sed // Both in the same loop, the NewBB joins loop. 254288943Sdim DestLoop->addBasicBlockToLoop(NewBB, *LI); 255201360Srdivacky } else if (TIL->contains(DestLoop)) { 256193323Sed // Edge from an outer loop to an inner loop. Add to the outer loop. 257288943Sdim TIL->addBasicBlockToLoop(NewBB, *LI); 258201360Srdivacky } else if (DestLoop->contains(TIL)) { 259193323Sed // Edge from an inner loop to an outer loop. Add to the outer loop. 260288943Sdim DestLoop->addBasicBlockToLoop(NewBB, *LI); 261193323Sed } else { 262193323Sed // Edge from two loops with no containment relation. Because these 263193323Sed // are natural loops, we know that the destination block must be the 264193323Sed // header of its loop (adding a branch into a loop elsewhere would 265193323Sed // create an irreducible loop). 266193323Sed assert(DestLoop->getHeader() == DestBB && 267193323Sed "Should not create irreducible loops!"); 268193323Sed if (Loop *P = DestLoop->getParentLoop()) 269288943Sdim P->addBasicBlockToLoop(NewBB, *LI); 270193323Sed } 271193323Sed } 272288943Sdim 273276479Sdim // If TIBB is in a loop and DestBB is outside of that loop, we may need 274276479Sdim // to update LoopSimplify form and LCSSA form. 275288943Sdim if (!TIL->contains(DestBB)) { 276198090Srdivacky assert(!TIL->contains(NewBB) && 277198090Srdivacky "Split point for loop exit is contained in loop!"); 278198090Srdivacky 279198090Srdivacky // Update LCSSA form in the newly created exit block. 280288943Sdim if (Options.PreserveLCSSA) { 281239462Sdim createPHIsForSplitLoopExit(TIBB, NewBB, DestBB); 282288943Sdim } 283198090Srdivacky 284276479Sdim // The only that we can break LoopSimplify form by splitting a critical 285276479Sdim // edge is if after the split there exists some edge from TIL to DestBB 286276479Sdim // *and* the only edge into DestBB from outside of TIL is that of 287276479Sdim // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB 288276479Sdim // is the new exit block and it has no non-loop predecessors. If the 289276479Sdim // second isn't true, then DestBB was not in LoopSimplify form prior to 290276479Sdim // the split as it had a non-loop predecessor. In both of these cases, 291276479Sdim // the predecessor must be directly in TIL, not in a subloop, or again 292276479Sdim // LoopSimplify doesn't hold. 293276479Sdim SmallVector<BasicBlock *, 4> LoopPreds; 294276479Sdim for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); I != E; 295276479Sdim ++I) { 296276479Sdim BasicBlock *P = *I; 297276479Sdim if (P == NewBB) 298276479Sdim continue; // The new block is known. 299276479Sdim if (LI->getLoopFor(P) != TIL) { 300276479Sdim // No need to re-simplify, it wasn't to start with. 301276479Sdim LoopPreds.clear(); 302276479Sdim break; 303210299Sed } 304276479Sdim LoopPreds.push_back(P); 305198090Srdivacky } 306276479Sdim if (!LoopPreds.empty()) { 307296417Sdim assert(!DestBB->isEHPad() && "We don't split edges to EH pads!"); 308288943Sdim BasicBlock *NewExitBB = SplitBlockPredecessors( 309344779Sdim DestBB, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA); 310288943Sdim if (Options.PreserveLCSSA) 311276479Sdim createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB); 312276479Sdim } 313198090Srdivacky } 314198090Srdivacky } 315193323Sed } 316198090Srdivacky 317198090Srdivacky return NewBB; 318193323Sed} 319327952Sdim 320327952Sdim// Return the unique indirectbr predecessor of a block. This may return null 321327952Sdim// even if such a predecessor exists, if it's not useful for splitting. 322327952Sdim// If a predecessor is found, OtherPreds will contain all other (non-indirectbr) 323327952Sdim// predecessors of BB. 324327952Sdimstatic BasicBlock * 325327952SdimfindIBRPredecessor(BasicBlock *BB, SmallVectorImpl<BasicBlock *> &OtherPreds) { 326327952Sdim // If the block doesn't have any PHIs, we don't care about it, since there's 327327952Sdim // no point in splitting it. 328327952Sdim PHINode *PN = dyn_cast<PHINode>(BB->begin()); 329327952Sdim if (!PN) 330327952Sdim return nullptr; 331327952Sdim 332327952Sdim // Verify we have exactly one IBR predecessor. 333327952Sdim // Conservatively bail out if one of the other predecessors is not a "regular" 334327952Sdim // terminator (that is, not a switch or a br). 335327952Sdim BasicBlock *IBB = nullptr; 336327952Sdim for (unsigned Pred = 0, E = PN->getNumIncomingValues(); Pred != E; ++Pred) { 337327952Sdim BasicBlock *PredBB = PN->getIncomingBlock(Pred); 338344779Sdim Instruction *PredTerm = PredBB->getTerminator(); 339327952Sdim switch (PredTerm->getOpcode()) { 340327952Sdim case Instruction::IndirectBr: 341327952Sdim if (IBB) 342327952Sdim return nullptr; 343327952Sdim IBB = PredBB; 344327952Sdim break; 345327952Sdim case Instruction::Br: 346327952Sdim case Instruction::Switch: 347327952Sdim OtherPreds.push_back(PredBB); 348327952Sdim continue; 349327952Sdim default: 350327952Sdim return nullptr; 351327952Sdim } 352327952Sdim } 353327952Sdim 354327952Sdim return IBB; 355327952Sdim} 356327952Sdim 357327952Sdimbool llvm::SplitIndirectBrCriticalEdges(Function &F, 358327952Sdim BranchProbabilityInfo *BPI, 359327952Sdim BlockFrequencyInfo *BFI) { 360327952Sdim // Check whether the function has any indirectbrs, and collect which blocks 361327952Sdim // they may jump to. Since most functions don't have indirect branches, 362327952Sdim // this lowers the common case's overhead to O(Blocks) instead of O(Edges). 363327952Sdim SmallSetVector<BasicBlock *, 16> Targets; 364327952Sdim for (auto &BB : F) { 365327952Sdim auto *IBI = dyn_cast<IndirectBrInst>(BB.getTerminator()); 366327952Sdim if (!IBI) 367327952Sdim continue; 368327952Sdim 369327952Sdim for (unsigned Succ = 0, E = IBI->getNumSuccessors(); Succ != E; ++Succ) 370327952Sdim Targets.insert(IBI->getSuccessor(Succ)); 371327952Sdim } 372327952Sdim 373327952Sdim if (Targets.empty()) 374327952Sdim return false; 375327952Sdim 376327952Sdim bool ShouldUpdateAnalysis = BPI && BFI; 377327952Sdim bool Changed = false; 378327952Sdim for (BasicBlock *Target : Targets) { 379327952Sdim SmallVector<BasicBlock *, 16> OtherPreds; 380327952Sdim BasicBlock *IBRPred = findIBRPredecessor(Target, OtherPreds); 381327952Sdim // If we did not found an indirectbr, or the indirectbr is the only 382327952Sdim // incoming edge, this isn't the kind of edge we're looking for. 383327952Sdim if (!IBRPred || OtherPreds.empty()) 384327952Sdim continue; 385327952Sdim 386327952Sdim // Don't even think about ehpads/landingpads. 387327952Sdim Instruction *FirstNonPHI = Target->getFirstNonPHI(); 388327952Sdim if (FirstNonPHI->isEHPad() || Target->isLandingPad()) 389327952Sdim continue; 390327952Sdim 391327952Sdim BasicBlock *BodyBlock = Target->splitBasicBlock(FirstNonPHI, ".split"); 392327952Sdim if (ShouldUpdateAnalysis) { 393327952Sdim // Copy the BFI/BPI from Target to BodyBlock. 394327952Sdim for (unsigned I = 0, E = BodyBlock->getTerminator()->getNumSuccessors(); 395327952Sdim I < E; ++I) 396327952Sdim BPI->setEdgeProbability(BodyBlock, I, 397327952Sdim BPI->getEdgeProbability(Target, I)); 398327952Sdim BFI->setBlockFreq(BodyBlock, BFI->getBlockFreq(Target).getFrequency()); 399327952Sdim } 400327952Sdim // It's possible Target was its own successor through an indirectbr. 401327952Sdim // In this case, the indirectbr now comes from BodyBlock. 402327952Sdim if (IBRPred == Target) 403327952Sdim IBRPred = BodyBlock; 404327952Sdim 405327952Sdim // At this point Target only has PHIs, and BodyBlock has the rest of the 406327952Sdim // block's body. Create a copy of Target that will be used by the "direct" 407327952Sdim // preds. 408327952Sdim ValueToValueMapTy VMap; 409327952Sdim BasicBlock *DirectSucc = CloneBasicBlock(Target, VMap, ".clone", &F); 410327952Sdim 411327952Sdim BlockFrequency BlockFreqForDirectSucc; 412327952Sdim for (BasicBlock *Pred : OtherPreds) { 413327952Sdim // If the target is a loop to itself, then the terminator of the split 414327952Sdim // block (BodyBlock) needs to be updated. 415327952Sdim BasicBlock *Src = Pred != Target ? Pred : BodyBlock; 416327952Sdim Src->getTerminator()->replaceUsesOfWith(Target, DirectSucc); 417327952Sdim if (ShouldUpdateAnalysis) 418327952Sdim BlockFreqForDirectSucc += BFI->getBlockFreq(Src) * 419327952Sdim BPI->getEdgeProbability(Src, DirectSucc); 420327952Sdim } 421327952Sdim if (ShouldUpdateAnalysis) { 422327952Sdim BFI->setBlockFreq(DirectSucc, BlockFreqForDirectSucc.getFrequency()); 423327952Sdim BlockFrequency NewBlockFreqForTarget = 424327952Sdim BFI->getBlockFreq(Target) - BlockFreqForDirectSucc; 425327952Sdim BFI->setBlockFreq(Target, NewBlockFreqForTarget.getFrequency()); 426327952Sdim BPI->eraseBlock(Target); 427327952Sdim } 428327952Sdim 429327952Sdim // Ok, now fix up the PHIs. We know the two blocks only have PHIs, and that 430327952Sdim // they are clones, so the number of PHIs are the same. 431327952Sdim // (a) Remove the edge coming from IBRPred from the "Direct" PHI 432327952Sdim // (b) Leave that as the only edge in the "Indirect" PHI. 433327952Sdim // (c) Merge the two in the body block. 434327952Sdim BasicBlock::iterator Indirect = Target->begin(), 435327952Sdim End = Target->getFirstNonPHI()->getIterator(); 436327952Sdim BasicBlock::iterator Direct = DirectSucc->begin(); 437327952Sdim BasicBlock::iterator MergeInsert = BodyBlock->getFirstInsertionPt(); 438327952Sdim 439327952Sdim assert(&*End == Target->getTerminator() && 440327952Sdim "Block was expected to only contain PHIs"); 441327952Sdim 442327952Sdim while (Indirect != End) { 443327952Sdim PHINode *DirPHI = cast<PHINode>(Direct); 444327952Sdim PHINode *IndPHI = cast<PHINode>(Indirect); 445327952Sdim 446327952Sdim // Now, clean up - the direct block shouldn't get the indirect value, 447327952Sdim // and vice versa. 448327952Sdim DirPHI->removeIncomingValue(IBRPred); 449327952Sdim Direct++; 450327952Sdim 451327952Sdim // Advance the pointer here, to avoid invalidation issues when the old 452327952Sdim // PHI is erased. 453327952Sdim Indirect++; 454327952Sdim 455327952Sdim PHINode *NewIndPHI = PHINode::Create(IndPHI->getType(), 1, "ind", IndPHI); 456327952Sdim NewIndPHI->addIncoming(IndPHI->getIncomingValueForBlock(IBRPred), 457327952Sdim IBRPred); 458327952Sdim 459327952Sdim // Create a PHI in the body block, to merge the direct and indirect 460327952Sdim // predecessors. 461327952Sdim PHINode *MergePHI = 462327952Sdim PHINode::Create(IndPHI->getType(), 2, "merge", &*MergeInsert); 463327952Sdim MergePHI->addIncoming(NewIndPHI, Target); 464327952Sdim MergePHI->addIncoming(DirPHI, DirectSucc); 465327952Sdim 466327952Sdim IndPHI->replaceAllUsesWith(MergePHI); 467327952Sdim IndPHI->eraseFromParent(); 468327952Sdim } 469327952Sdim 470327952Sdim Changed = true; 471327952Sdim } 472327952Sdim 473327952Sdim return Changed; 474327952Sdim} 475