1//===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// BreakCriticalEdges pass - Break all of the critical edges in the CFG by
10// inserting a dummy basic block. This pass may be "required" by passes that
11// cannot deal with critical edges. For this usage, the structure type is
12// forward declared. This pass obviously invalidates the CFG, but can update
13// dominator trees.
14//
15//===----------------------------------------------------------------------===//
16
17#include "llvm/Transforms/Utils/BreakCriticalEdges.h"
18#include "llvm/ADT/SetVector.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/Statistic.h"
21#include "llvm/Analysis/BlockFrequencyInfo.h"
22#include "llvm/Analysis/BranchProbabilityInfo.h"
23#include "llvm/Analysis/CFG.h"
24#include "llvm/Analysis/DomTreeUpdater.h"
25#include "llvm/Analysis/LoopInfo.h"
26#include "llvm/Analysis/MemorySSAUpdater.h"
27#include "llvm/Analysis/PostDominators.h"
28#include "llvm/IR/CFG.h"
29#include "llvm/IR/Dominators.h"
30#include "llvm/IR/Instructions.h"
31#include "llvm/InitializePasses.h"
32#include "llvm/Transforms/Utils.h"
33#include "llvm/Transforms/Utils/BasicBlockUtils.h"
34#include "llvm/Transforms/Utils/Cloning.h"
35#include "llvm/Transforms/Utils/ValueMapper.h"
36using namespace llvm;
37
38#define DEBUG_TYPE "break-crit-edges"
39
40STATISTIC(NumBroken, "Number of blocks inserted");
41
42namespace {
43struct BreakCriticalEdges : public FunctionPass {
44 static char ID; // Pass identification, replacement for typeid
45 BreakCriticalEdges() : FunctionPass(ID) {
46 initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry());
47 }
48
49 bool runOnFunction(Function &F) override {
50 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
51 auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
52
53 auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
54 auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
55
56 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
57 auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
58 unsigned N = SplitAllCriticalEdges(
59 F, Options: CriticalEdgeSplittingOptions(DT, LI, nullptr, PDT));
60 NumBroken += N;
61 return N > 0;
62 }
63
64 void getAnalysisUsage(AnalysisUsage &AU) const override {
65 AU.addPreserved<DominatorTreeWrapperPass>();
66 AU.addPreserved<LoopInfoWrapperPass>();
67
68 // No loop canonicalization guarantees are broken by this pass.
69 AU.addPreservedID(ID&: LoopSimplifyID);
70 }
71};
72} // namespace
73
74char BreakCriticalEdges::ID = 0;
75INITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges",
76 "Break critical edges in CFG", false, false)
77
78// Publicly exposed interface to pass...
79char &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID;
80
81FunctionPass *llvm::createBreakCriticalEdgesPass() {
82 return new BreakCriticalEdges();
83}
84
85PreservedAnalyses BreakCriticalEdgesPass::run(Function &F,
86 FunctionAnalysisManager &AM) {
87 auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(IR&: F);
88 auto *LI = AM.getCachedResult<LoopAnalysis>(IR&: F);
89 unsigned N = SplitAllCriticalEdges(F, Options: CriticalEdgeSplittingOptions(DT, LI));
90 NumBroken += N;
91 if (N == 0)
92 return PreservedAnalyses::all();
93 PreservedAnalyses PA;
94 PA.preserve<DominatorTreeAnalysis>();
95 PA.preserve<LoopAnalysis>();
96 return PA;
97}
98
99//===----------------------------------------------------------------------===//
100// Implementation of the external critical edge manipulation functions
101//===----------------------------------------------------------------------===//
102
103BasicBlock *llvm::SplitCriticalEdge(Instruction *TI, unsigned SuccNum,
104 const CriticalEdgeSplittingOptions &Options,
105 const Twine &BBName) {
106 if (!isCriticalEdge(TI, SuccNum, AllowIdenticalEdges: Options.MergeIdenticalEdges))
107 return nullptr;
108
109 return SplitKnownCriticalEdge(TI, SuccNum, Options, BBName);
110}
111
112BasicBlock *
113llvm::SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum,
114 const CriticalEdgeSplittingOptions &Options,
115 const Twine &BBName) {
116 BasicBlock *TIBB = TI->getParent();
117 BasicBlock *DestBB = TI->getSuccessor(Idx: SuccNum);
118
119 // Splitting the critical edge to a pad block is non-trivial.
120 // And we cannot split block with IndirectBr as a terminator.
121 // Don't do it in this generic function.
122 if (DestBB->isEHPad() || isa<IndirectBrInst>(Val: TI))
123 return nullptr;
124
125 if (Options.IgnoreUnreachableDests &&
126 isa<UnreachableInst>(Val: DestBB->getFirstNonPHIOrDbgOrLifetime()))
127 return nullptr;
128
129 auto *LI = Options.LI;
130 SmallVector<BasicBlock *, 4> LoopPreds;
131 // Check if extra modifications will be required to preserve loop-simplify
132 // form after splitting. If it would require splitting blocks with IndirectBr
133 // terminators, bail out if preserving loop-simplify form is requested.
134 if (LI) {
135 if (Loop *TIL = LI->getLoopFor(BB: TIBB)) {
136
137 // The only way that we can break LoopSimplify form by splitting a
138 // critical edge is if after the split there exists some edge from TIL to
139 // DestBB *and* the only edge into DestBB from outside of TIL is that of
140 // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB
141 // is the new exit block and it has no non-loop predecessors. If the
142 // second isn't true, then DestBB was not in LoopSimplify form prior to
143 // the split as it had a non-loop predecessor. In both of these cases,
144 // the predecessor must be directly in TIL, not in a subloop, or again
145 // LoopSimplify doesn't hold.
146 for (BasicBlock *P : predecessors(BB: DestBB)) {
147 if (P == TIBB)
148 continue; // The new block is known.
149 if (LI->getLoopFor(BB: P) != TIL) {
150 // No need to re-simplify, it wasn't to start with.
151 LoopPreds.clear();
152 break;
153 }
154 LoopPreds.push_back(Elt: P);
155 }
156 // Loop-simplify form can be preserved, if we can split all in-loop
157 // predecessors.
158 if (any_of(Range&: LoopPreds, P: [](BasicBlock *Pred) {
159 return isa<IndirectBrInst>(Val: Pred->getTerminator());
160 })) {
161 if (Options.PreserveLoopSimplify)
162 return nullptr;
163 LoopPreds.clear();
164 }
165 }
166 }
167
168 // Create a new basic block, linking it into the CFG.
169 BasicBlock *NewBB = nullptr;
170 if (BBName.str() != "")
171 NewBB = BasicBlock::Create(Context&: TI->getContext(), Name: BBName);
172 else
173 NewBB = BasicBlock::Create(Context&: TI->getContext(), Name: TIBB->getName() + "." +
174 DestBB->getName() +
175 "_crit_edge");
176 // Create our unconditional branch.
177 UncondBrInst *NewBI = UncondBrInst::Create(Target: DestBB, InsertBefore: NewBB);
178 NewBI->setDebugLoc(TI->getDebugLoc());
179 if (auto *LoopMD = TI->getMetadata(KindID: LLVMContext::MD_loop))
180 NewBI->setMetadata(KindID: LLVMContext::MD_loop, Node: LoopMD);
181
182 // Insert the block into the function... right after the block TI lives in.
183 Function &F = *TIBB->getParent();
184 Function::iterator FBBI = TIBB->getIterator();
185 F.insert(Position: ++FBBI, BB: NewBB);
186
187 // Branch to the new block, breaking the edge.
188 TI->setSuccessor(Idx: SuccNum, BB: NewBB);
189
190 // If there are any PHI nodes in DestBB, we need to update them so that they
191 // merge incoming values from NewBB instead of from TIBB.
192 {
193 unsigned BBIdx = 0;
194 for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(Val: I); ++I) {
195 // We no longer enter through TIBB, now we come in through NewBB.
196 // Revector exactly one entry in the PHI node that used to come from
197 // TIBB to come from NewBB.
198 PHINode *PN = cast<PHINode>(Val&: I);
199
200 // Reuse the previous value of BBIdx if it lines up. In cases where we
201 // have multiple phi nodes with *lots* of predecessors, this is a speed
202 // win because we don't have to scan the PHI looking for TIBB. This
203 // happens because the BB list of PHI nodes are usually in the same
204 // order.
205 if (PN->getIncomingBlock(i: BBIdx) != TIBB)
206 BBIdx = PN->getBasicBlockIndex(BB: TIBB);
207 PN->setIncomingBlock(i: BBIdx, BB: NewBB);
208 }
209 }
210
211 unsigned NumSplitIdenticalEdges = 1;
212
213 // If there are any other edges from TIBB to DestBB, update those to go
214 // through the split block, making those edges non-critical as well (and
215 // reducing the number of phi entries in the DestBB if relevant).
216 if (Options.MergeIdenticalEdges) {
217 for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
218 if (TI->getSuccessor(Idx: i) != DestBB) continue;
219
220 // Remove an entry for TIBB from DestBB phi nodes.
221 DestBB->removePredecessor(Pred: TIBB, KeepOneInputPHIs: Options.KeepOneInputPHIs);
222
223 // We found another edge to DestBB, go to NewBB instead.
224 TI->setSuccessor(Idx: i, BB: NewBB);
225
226 // Record the number of split identical edges to DestBB.
227 NumSplitIdenticalEdges++;
228 }
229 }
230
231 // If we have nothing to update, just return.
232 auto *DT = Options.DT;
233 auto *PDT = Options.PDT;
234 auto *MSSAU = Options.MSSAU;
235 if (MSSAU)
236 MSSAU->wireOldPredecessorsToNewImmediatePredecessor(
237 Old: DestBB, New: NewBB, Preds: {TIBB}, IdenticalEdgesWereMerged: Options.MergeIdenticalEdges);
238
239 if (!DT && !PDT && !LI)
240 return NewBB;
241
242 if (DT || PDT) {
243 // Update the DominatorTree.
244 // ---> NewBB -----\
245 // / V
246 // TIBB -------\\------> DestBB
247 //
248 // First, inform the DT about the new path from TIBB to DestBB via NewBB,
249 // then delete the old edge from TIBB to DestBB. By doing this in that order
250 // DestBB stays reachable in the DT the whole time and its subtree doesn't
251 // get disconnected.
252 SmallVector<DominatorTree::UpdateType, 3> Updates;
253 Updates.push_back(Elt: {DominatorTree::Insert, TIBB, NewBB});
254 Updates.push_back(Elt: {DominatorTree::Insert, NewBB, DestBB});
255 if (!llvm::is_contained(Range: successors(BB: TIBB), Element: DestBB))
256 Updates.push_back(Elt: {DominatorTree::Delete, TIBB, DestBB});
257
258 if (DT)
259 DT->applyUpdates(Updates);
260 if (PDT)
261 PDT->applyUpdates(Updates);
262 }
263
264 // Update LoopInfo if it is around.
265 if (LI) {
266 if (Loop *TIL = LI->getLoopFor(BB: TIBB)) {
267 // If one or the other blocks were not in a loop, the new block is not
268 // either, and thus LI doesn't need to be updated.
269 if (Loop *DestLoop = LI->getLoopFor(BB: DestBB)) {
270 if (TIL == DestLoop) {
271 // Both in the same loop, the NewBB joins loop.
272 DestLoop->addBasicBlockToLoop(NewBB, LI&: *LI);
273 } else if (TIL->contains(L: DestLoop)) {
274 // Edge from an outer loop to an inner loop. Add to the outer loop.
275 TIL->addBasicBlockToLoop(NewBB, LI&: *LI);
276 } else if (DestLoop->contains(L: TIL)) {
277 // Edge from an inner loop to an outer loop. Add to the outer loop.
278 DestLoop->addBasicBlockToLoop(NewBB, LI&: *LI);
279 } else {
280 // Edge from two loops with no containment relation. Because these
281 // are natural loops, we know that the destination block must be the
282 // header of its loop (adding a branch into a loop elsewhere would
283 // create an irreducible loop).
284 assert(DestLoop->getHeader() == DestBB &&
285 "Should not create irreducible loops!");
286 if (Loop *P = DestLoop->getParentLoop())
287 P->addBasicBlockToLoop(NewBB, LI&: *LI);
288 }
289 }
290
291 // If TIBB is in a loop and DestBB is outside of that loop, we may need
292 // to update LoopSimplify form and LCSSA form.
293 if (!TIL->contains(BB: DestBB)) {
294 assert(!TIL->contains(NewBB) &&
295 "Split point for loop exit is contained in loop!");
296
297 // Update LCSSA form in the newly created exit block.
298 if (Options.PreserveLCSSA) {
299 // If > 1 identical edges to be split, we need to introduce the same
300 // number of the incoming blocks for the new PHINode.
301 createPHIsForSplitLoopExit(
302 Preds: SmallVector<BasicBlock *, 4>(NumSplitIdenticalEdges, TIBB), SplitBB: NewBB,
303 DestBB);
304 }
305
306 if (!LoopPreds.empty()) {
307 assert(!DestBB->isEHPad() && "We don't split edges to EH pads!");
308 BasicBlock *NewExitBB = SplitBlockPredecessors(
309 BB: DestBB, Preds: LoopPreds, Suffix: "split", DT, LI, MSSAU, PreserveLCSSA: Options.PreserveLCSSA);
310 if (Options.PreserveLCSSA)
311 createPHIsForSplitLoopExit(Preds: LoopPreds, SplitBB: NewExitBB, DestBB);
312 }
313 }
314 }
315 }
316
317 return NewBB;
318}
319
320// Return the unique indirectbr predecessor of a block. This may return null
321// even if such a predecessor exists, if it's not useful for splitting.
322// If a predecessor is found, OtherPreds will contain all other (non-indirectbr)
323// predecessors of BB.
324static BasicBlock *
325findIBRPredecessor(BasicBlock *BB, SmallVectorImpl<BasicBlock *> &OtherPreds) {
326 // Verify we have exactly one IBR predecessor.
327 // Conservatively bail out if one of the other predecessors is not a "regular"
328 // terminator (that is, not a switch or a br).
329 BasicBlock *IBB = nullptr;
330 for (BasicBlock *PredBB : predecessors(BB)) {
331 Instruction *PredTerm = PredBB->getTerminator();
332 switch (PredTerm->getOpcode()) {
333 case Instruction::IndirectBr:
334 if (IBB)
335 return nullptr;
336 IBB = PredBB;
337 break;
338 case Instruction::UncondBr:
339 case Instruction::CondBr:
340 case Instruction::Switch:
341 OtherPreds.push_back(Elt: PredBB);
342 continue;
343 default:
344 return nullptr;
345 }
346 }
347
348 return IBB;
349}
350
351bool llvm::SplitIndirectBrCriticalEdges(Function &F,
352 bool IgnoreBlocksWithoutPHI,
353 BranchProbabilityInfo *BPI,
354 BlockFrequencyInfo *BFI,
355 DomTreeUpdater *DTU) {
356 // Check whether the function has any indirectbrs, and collect which blocks
357 // they may jump to. Since most functions don't have indirect branches,
358 // this lowers the common case's overhead to O(Blocks) instead of O(Edges).
359 SmallSetVector<BasicBlock *, 16> Targets;
360 for (auto &BB : F) {
361 if (isa<IndirectBrInst>(Val: BB.getTerminator()))
362 Targets.insert_range(R: successors(BB: &BB));
363 }
364
365 if (Targets.empty())
366 return false;
367
368 bool ShouldUpdateAnalysis = BPI && BFI;
369 bool Changed = false;
370 for (BasicBlock *Target : Targets) {
371 if (IgnoreBlocksWithoutPHI && Target->phis().empty())
372 continue;
373
374 SmallVector<BasicBlock *, 16> OtherPreds;
375 BasicBlock *IBRPred = findIBRPredecessor(BB: Target, OtherPreds);
376 // If we did not found an indirectbr, or the indirectbr is the only
377 // incoming edge, this isn't the kind of edge we're looking for.
378 if (!IBRPred || OtherPreds.empty())
379 continue;
380
381 // Don't even think about ehpads/landingpads.
382 auto FirstNonPHIIt = Target->getFirstNonPHIIt();
383 if (FirstNonPHIIt->isEHPad() || Target->isLandingPad())
384 continue;
385
386 // Remember edge probabilities if needed.
387 SmallVector<BranchProbability, 4> EdgeProbabilities;
388 if (ShouldUpdateAnalysis) {
389 EdgeProbabilities.reserve(N: Target->getTerminator()->getNumSuccessors());
390 for (unsigned I = 0, E = Target->getTerminator()->getNumSuccessors();
391 I < E; ++I)
392 EdgeProbabilities.emplace_back(Args: BPI->getEdgeProbability(Src: Target, IndexInSuccessors: I));
393 BPI->eraseBlock(BB: Target);
394 }
395
396 BasicBlock *BodyBlock =
397 SplitBlock(Old: Target, SplitPt: FirstNonPHIIt, DTU, LI: nullptr, MSSAU: nullptr, BBName: ".split");
398 if (ShouldUpdateAnalysis) {
399 // Copy the BFI/BPI from Target to BodyBlock.
400 BPI->setEdgeProbability(Src: BodyBlock, Probs: EdgeProbabilities);
401 BFI->setBlockFreq(BB: BodyBlock, Freq: BFI->getBlockFreq(BB: Target));
402 }
403 // It's possible Target was its own successor through an indirectbr.
404 // In this case, the indirectbr now comes from BodyBlock.
405 if (IBRPred == Target)
406 IBRPred = BodyBlock;
407
408 // At this point Target only has PHIs, and BodyBlock has the rest of the
409 // block's body. Create a copy of Target that will be used by the "direct"
410 // preds.
411 ValueToValueMapTy VMap;
412 BasicBlock *DirectSucc = CloneBasicBlock(BB: Target, VMap, NameSuffix: ".clone", F: &F);
413 if (!VMap.AtomMap.empty())
414 for (Instruction &I : *DirectSucc)
415 RemapSourceAtom(I: &I, VM&: VMap);
416
417 BlockFrequency BlockFreqForDirectSucc;
418 SmallVector<DominatorTree::UpdateType, 8> DTUpdates;
419 if (DTU)
420 DTUpdates.reserve(N: OtherPreds.size() * 2 + 1);
421 for (BasicBlock *Pred : OtherPreds) {
422 // If the target is a loop to itself, then the terminator of the split
423 // block (BodyBlock) needs to be updated.
424 BasicBlock *Src = Pred != Target ? Pred : BodyBlock;
425 Src->getTerminator()->replaceUsesOfWith(From: Target, To: DirectSucc);
426 if (ShouldUpdateAnalysis)
427 BlockFreqForDirectSucc += BFI->getBlockFreq(BB: Src) *
428 BPI->getEdgeProbability(Src, Dst: DirectSucc);
429 if (DTU) {
430 DTUpdates.push_back(Elt: {DominatorTree::Insert, Src, DirectSucc});
431 DTUpdates.push_back(Elt: {DominatorTree::Delete, Src, Target});
432 }
433 }
434 if (ShouldUpdateAnalysis) {
435 BFI->setBlockFreq(BB: DirectSucc, Freq: BlockFreqForDirectSucc);
436 BlockFrequency NewBlockFreqForTarget =
437 BFI->getBlockFreq(BB: Target) - BlockFreqForDirectSucc;
438 BFI->setBlockFreq(BB: Target, Freq: NewBlockFreqForTarget);
439 }
440 if (DTU) {
441 DTUpdates.push_back(Elt: {DominatorTree::Insert, DirectSucc, BodyBlock});
442 DTU->applyUpdates(Updates: DTUpdates);
443 }
444
445 // Ok, now fix up the PHIs. We know the two blocks only have PHIs, and that
446 // they are clones, so the number of PHIs are the same.
447 // (a) Remove the edge coming from IBRPred from the "Direct" PHI
448 // (b) Leave that as the only edge in the "Indirect" PHI.
449 // (c) Merge the two in the body block.
450 BasicBlock::iterator Indirect = Target->begin(),
451 End = Target->getFirstNonPHIIt();
452 BasicBlock::iterator Direct = DirectSucc->begin();
453 BasicBlock::iterator MergeInsert = BodyBlock->getFirstInsertionPt();
454
455 assert(&*End == Target->getTerminator() &&
456 "Block was expected to only contain PHIs");
457
458 while (Indirect != End) {
459 PHINode *DirPHI = cast<PHINode>(Val&: Direct);
460 PHINode *IndPHI = cast<PHINode>(Val&: Indirect);
461 BasicBlock::iterator InsertPt = Indirect;
462
463 // Now, clean up - the direct block shouldn't get the indirect value,
464 // and vice versa.
465 DirPHI->removeIncomingValue(BB: IBRPred);
466 Direct++;
467
468 // Advance the pointer here, to avoid invalidation issues when the old
469 // PHI is erased.
470 Indirect++;
471
472 PHINode *NewIndPHI = PHINode::Create(Ty: IndPHI->getType(), NumReservedValues: 1, NameStr: "ind", InsertBefore: InsertPt);
473 NewIndPHI->addIncoming(V: IndPHI->getIncomingValueForBlock(BB: IBRPred),
474 BB: IBRPred);
475 NewIndPHI->setDebugLoc(IndPHI->getDebugLoc());
476
477 // Create a PHI in the body block, to merge the direct and indirect
478 // predecessors.
479 PHINode *MergePHI = PHINode::Create(Ty: IndPHI->getType(), NumReservedValues: 2, NameStr: "merge");
480 MergePHI->insertBefore(InsertPos: MergeInsert);
481 MergePHI->addIncoming(V: NewIndPHI, BB: Target);
482 MergePHI->addIncoming(V: DirPHI, BB: DirectSucc);
483 MergePHI->applyMergedLocation(LocA: DirPHI->getDebugLoc(),
484 LocB: IndPHI->getDebugLoc());
485
486 IndPHI->replaceAllUsesWith(V: MergePHI);
487 IndPHI->eraseFromParent();
488 }
489
490 Changed = true;
491 }
492
493 return Changed;
494}
495