Chris Lattner | b03832d | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 1 | //===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===// |
Misha Brukman | b1c9317 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
Chandler Carruth | 2946cd7 | 2019-01-19 08:50:56 +0000 | [diff] [blame] | 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 |
Misha Brukman | b1c9317 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 6 | // |
John Criswell | 482202a | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 7 | //===----------------------------------------------------------------------===// |
Chris Lattner | b03832d | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 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 |
Cameron Zwarich | b703654 | 2011-01-18 04:11:31 +0000 | [diff] [blame] | 13 | // dominator trees. |
Chris Lattner | b03832d | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 14 | // |
| 15 | //===----------------------------------------------------------------------===// |
| 16 | |
Wei Mi | e04d0ef | 2016-07-22 18:04:25 +0000 | [diff] [blame] | 17 | #include "llvm/Transforms/Utils/BreakCriticalEdges.h" |
Hiroshi Yamauchi | 9364fa3 | 2017-12-04 20:36:01 +0000 | [diff] [blame] | 18 | #include "llvm/ADT/SetVector.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 19 | #include "llvm/ADT/SmallVector.h" |
| 20 | #include "llvm/ADT/Statistic.h" |
Hiroshi Yamauchi | f3bda1d | 2017-12-12 19:07:43 +0000 | [diff] [blame] | 21 | #include "llvm/Analysis/BlockFrequencyInfo.h" |
| 22 | #include "llvm/Analysis/BranchProbabilityInfo.h" |
Nick Lewycky | 0b68245 | 2013-07-27 01:24:00 +0000 | [diff] [blame] | 23 | #include "llvm/Analysis/CFG.h" |
Chris Lattner | 89c1dfc | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 24 | #include "llvm/Analysis/LoopInfo.h" |
Alina Sbirlea | ab6f84f7 | 2018-08-21 23:32:03 +0000 | [diff] [blame] | 25 | #include "llvm/Analysis/MemorySSAUpdater.h" |
Matt Arsenault | 65b4ab9 | 2019-02-22 15:01:41 +0000 | [diff] [blame] | 26 | #include "llvm/Analysis/PostDominators.h" |
Chandler Carruth | 1305dc3 | 2014-03-04 11:45:46 +0000 | [diff] [blame] | 27 | #include "llvm/IR/CFG.h" |
Chandler Carruth | 5ad5f15 | 2014-01-13 09:26:24 +0000 | [diff] [blame] | 28 | #include "llvm/IR/Dominators.h" |
Chandler Carruth | 9fb823b | 2013-01-02 11:36:10 +0000 | [diff] [blame] | 29 | #include "llvm/IR/Instructions.h" |
| 30 | #include "llvm/IR/Type.h" |
Reid Kleckner | 05da2fe | 2019-11-13 13:15:01 -0800 | [diff] [blame] | 31 | #include "llvm/InitializePasses.h" |
Torok Edwin | 56d0659 | 2009-07-11 20:10:48 +0000 | [diff] [blame] | 32 | #include "llvm/Support/ErrorHandling.h" |
David Blaikie | a373d18 | 2018-03-28 17:44:36 +0000 | [diff] [blame] | 33 | #include "llvm/Transforms/Utils.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 34 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
Hiroshi Yamauchi | 9364fa3 | 2017-12-04 20:36:01 +0000 | [diff] [blame] | 35 | #include "llvm/Transforms/Utils/Cloning.h" |
| 36 | #include "llvm/Transforms/Utils/ValueMapper.h" |
Chris Lattner | df3c342 | 2004-01-09 06:12:26 +0000 | [diff] [blame] | 37 | using namespace llvm; |
Brian Gaeke | 960707c | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 38 | |
Chandler Carruth | 964daaa | 2014-04-22 02:55:47 +0000 | [diff] [blame] | 39 | #define DEBUG_TYPE "break-crit-edges" |
| 40 | |
Chris Lattner | 45f966d | 2006-12-19 22:17:40 +0000 | [diff] [blame] | 41 | STATISTIC(NumBroken, "Number of blocks inserted"); |
Chris Lattner | b03832d | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 42 | |
Chris Lattner | 45f966d | 2006-12-19 22:17:40 +0000 | [diff] [blame] | 43 | namespace { |
Nick Lewycky | 02d5f77 | 2009-10-25 06:33:48 +0000 | [diff] [blame] | 44 | struct BreakCriticalEdges : public FunctionPass { |
Nick Lewycky | e7da2d6 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 45 | static char ID; // Pass identification, replacement for typeid |
Owen Anderson | 6c18d1a | 2010-10-19 17:21:58 +0000 | [diff] [blame] | 46 | BreakCriticalEdges() : FunctionPass(ID) { |
| 47 | initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry()); |
| 48 | } |
Devang Patel | 09f162c | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 49 | |
Kostya Serebryany | e5ea424 | 2014-11-19 00:17:31 +0000 | [diff] [blame] | 50 | bool runOnFunction(Function &F) override { |
Chandler Carruth | 37df2cf | 2015-01-19 12:09:11 +0000 | [diff] [blame] | 51 | auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); |
| 52 | auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; |
Matt Arsenault | 65b4ab9 | 2019-02-22 15:01:41 +0000 | [diff] [blame] | 53 | |
| 54 | auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>(); |
| 55 | auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr; |
| 56 | |
Chandler Carruth | 37df2cf | 2015-01-19 12:09:11 +0000 | [diff] [blame] | 57 | auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>(); |
| 58 | auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; |
| 59 | unsigned N = |
Matt Arsenault | 65b4ab9 | 2019-02-22 15:01:41 +0000 | [diff] [blame] | 60 | SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions(DT, LI, nullptr, PDT)); |
Kostya Serebryany | e5ea424 | 2014-11-19 00:17:31 +0000 | [diff] [blame] | 61 | NumBroken += N; |
| 62 | return N > 0; |
| 63 | } |
Misha Brukman | b1c9317 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 64 | |
Craig Topper | 3e4c697 | 2014-03-05 09:10:37 +0000 | [diff] [blame] | 65 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
Chandler Carruth | 7352302 | 2014-01-13 13:07:17 +0000 | [diff] [blame] | 66 | AU.addPreserved<DominatorTreeWrapperPass>(); |
Chandler Carruth | 4f8f307 | 2015-01-17 14:16:18 +0000 | [diff] [blame] | 67 | AU.addPreserved<LoopInfoWrapperPass>(); |
Chris Lattner | 72272a7 | 2003-10-12 21:52:28 +0000 | [diff] [blame] | 68 | |
| 69 | // No loop canonicalization guarantees are broken by this pass. |
| 70 | AU.addPreservedID(LoopSimplifyID); |
Chris Lattner | 4bec665 | 2002-09-24 15:43:12 +0000 | [diff] [blame] | 71 | } |
| 72 | }; |
Alexander Kornienko | f00654e | 2015-06-23 09:49:53 +0000 | [diff] [blame] | 73 | } |
Chris Lattner | b03832d | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 74 | |
Dan Gohman | d78c400 | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 75 | char BreakCriticalEdges::ID = 0; |
Owen Anderson | d31d82d | 2010-08-23 17:52:01 +0000 | [diff] [blame] | 76 | INITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges", |
Owen Anderson | df7a4f2 | 2010-10-07 22:25:06 +0000 | [diff] [blame] | 77 | "Break critical edges in CFG", false, false) |
Dan Gohman | d78c400 | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 78 | |
Chris Lattner | 0ab5e2c | 2011-04-15 05:18:47 +0000 | [diff] [blame] | 79 | // Publicly exposed interface to pass... |
Owen Anderson | a7aed18 | 2010-08-06 18:33:48 +0000 | [diff] [blame] | 80 | char &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID; |
Chris Lattner | 7471b96 | 2004-07-31 10:01:58 +0000 | [diff] [blame] | 81 | FunctionPass *llvm::createBreakCriticalEdgesPass() { |
| 82 | return new BreakCriticalEdges(); |
| 83 | } |
Chris Lattner | b03832d | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 84 | |
Wei Mi | e04d0ef | 2016-07-22 18:04:25 +0000 | [diff] [blame] | 85 | PreservedAnalyses BreakCriticalEdgesPass::run(Function &F, |
| 86 | FunctionAnalysisManager &AM) { |
| 87 | auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F); |
| 88 | auto *LI = AM.getCachedResult<LoopAnalysis>(F); |
| 89 | unsigned N = SplitAllCriticalEdges(F, 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 | |
Chris Lattner | 1e6d305 | 2003-11-10 04:42:42 +0000 | [diff] [blame] | 99 | //===----------------------------------------------------------------------===// |
| 100 | // Implementation of the external critical edge manipulation functions |
| 101 | //===----------------------------------------------------------------------===// |
Chris Lattner | 75f80bd | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 102 | |
Sanjay Patel | 85ce0f1 | 2016-04-23 16:31:48 +0000 | [diff] [blame] | 103 | /// When a loop exit edge is split, LCSSA form may require new PHIs in the new |
| 104 | /// exit block. This function inserts the new PHIs, as needed. Preds is a list |
| 105 | /// of preds inside the loop, SplitBB is the new loop exit block, and DestBB is |
| 106 | /// the old loop exit, now the successor of SplitBB. |
Bill Wendling | 325e6cd | 2012-04-30 10:25:51 +0000 | [diff] [blame] | 107 | static void createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds, |
Dan Gohman | ec4557f | 2009-09-09 18:18:18 +0000 | [diff] [blame] | 108 | BasicBlock *SplitBB, |
| 109 | BasicBlock *DestBB) { |
| 110 | // SplitBB shouldn't have anything non-trivial in it yet. |
Bill Wendling | bf4b9af | 2012-04-30 10:44:54 +0000 | [diff] [blame] | 111 | assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() || |
| 112 | SplitBB->isLandingPad()) && "SplitBB has non-PHI nodes!"); |
Dan Gohman | ec4557f | 2009-09-09 18:18:18 +0000 | [diff] [blame] | 113 | |
Bill Wendling | bf4b9af | 2012-04-30 10:44:54 +0000 | [diff] [blame] | 114 | // For each PHI in the destination block. |
Benjamin Kramer | c7fc81e | 2017-12-30 15:27:33 +0000 | [diff] [blame] | 115 | for (PHINode &PN : DestBB->phis()) { |
| 116 | unsigned Idx = PN.getBasicBlockIndex(SplitBB); |
| 117 | Value *V = PN.getIncomingValue(Idx); |
Bill Wendling | bf4b9af | 2012-04-30 10:44:54 +0000 | [diff] [blame] | 118 | |
Dan Gohman | ec4557f | 2009-09-09 18:18:18 +0000 | [diff] [blame] | 119 | // If the input is a PHI which already satisfies LCSSA, don't create |
| 120 | // a new one. |
| 121 | if (const PHINode *VP = dyn_cast<PHINode>(V)) |
| 122 | if (VP->getParent() == SplitBB) |
| 123 | continue; |
Bill Wendling | bf4b9af | 2012-04-30 10:44:54 +0000 | [diff] [blame] | 124 | |
Dan Gohman | ec4557f | 2009-09-09 18:18:18 +0000 | [diff] [blame] | 125 | // Otherwise a new PHI is needed. Create one and populate it. |
Duncan P. N. Exon Smith | 5b4c837 | 2015-10-13 02:39:05 +0000 | [diff] [blame] | 126 | PHINode *NewPN = PHINode::Create( |
Benjamin Kramer | c7fc81e | 2017-12-30 15:27:33 +0000 | [diff] [blame] | 127 | PN.getType(), Preds.size(), "split", |
Duncan P. N. Exon Smith | 5b4c837 | 2015-10-13 02:39:05 +0000 | [diff] [blame] | 128 | SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator()); |
Dan Gohman | ec4557f | 2009-09-09 18:18:18 +0000 | [diff] [blame] | 129 | for (unsigned i = 0, e = Preds.size(); i != e; ++i) |
| 130 | NewPN->addIncoming(V, Preds[i]); |
Bill Wendling | bf4b9af | 2012-04-30 10:44:54 +0000 | [diff] [blame] | 131 | |
Dan Gohman | ec4557f | 2009-09-09 18:18:18 +0000 | [diff] [blame] | 132 | // Update the original PHI. |
Benjamin Kramer | c7fc81e | 2017-12-30 15:27:33 +0000 | [diff] [blame] | 133 | PN.setIncomingValue(Idx, NewPN); |
Dan Gohman | ec4557f | 2009-09-09 18:18:18 +0000 | [diff] [blame] | 134 | } |
| 135 | } |
| 136 | |
Sanjay Patel | 85ce0f1 | 2016-04-23 16:31:48 +0000 | [diff] [blame] | 137 | BasicBlock * |
Chandler Carruth | b99a2468 | 2018-10-15 09:17:09 +0000 | [diff] [blame] | 138 | llvm::SplitCriticalEdge(Instruction *TI, unsigned SuccNum, |
Sanjay Patel | 85ce0f1 | 2016-04-23 16:31:48 +0000 | [diff] [blame] | 139 | const CriticalEdgeSplittingOptions &Options) { |
Chandler Carruth | 37df2cf | 2015-01-19 12:09:11 +0000 | [diff] [blame] | 140 | if (!isCriticalEdge(TI, SuccNum, Options.MergeIdenticalEdges)) |
| 141 | return nullptr; |
Andrew Trick | 411842f | 2011-10-04 03:34:49 +0000 | [diff] [blame] | 142 | |
Chris Lattner | ba364b0 | 2009-10-31 21:51:10 +0000 | [diff] [blame] | 143 | assert(!isa<IndirectBrInst>(TI) && |
| 144 | "Cannot split critical edge from IndirectBrInst"); |
Andrew Trick | 411842f | 2011-10-04 03:34:49 +0000 | [diff] [blame] | 145 | |
Chris Lattner | 75f80bd | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 146 | BasicBlock *TIBB = TI->getParent(); |
Chris Lattner | 12764c8 | 2002-10-31 02:44:36 +0000 | [diff] [blame] | 147 | BasicBlock *DestBB = TI->getSuccessor(SuccNum); |
Chris Lattner | 75f80bd | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 148 | |
David Majnemer | eb518bd | 2015-08-04 08:21:40 +0000 | [diff] [blame] | 149 | // Splitting the critical edge to a pad block is non-trivial. Don't do |
Bill Wendling | 2dfbcc4 | 2011-08-17 21:04:05 +0000 | [diff] [blame] | 150 | // it in this generic function. |
David Majnemer | eb518bd | 2015-08-04 08:21:40 +0000 | [diff] [blame] | 151 | if (DestBB->isEHPad()) return nullptr; |
Bill Wendling | 2dfbcc4 | 2011-08-17 21:04:05 +0000 | [diff] [blame] | 152 | |
Craig Topper | 784929d | 2019-02-08 20:48:56 +0000 | [diff] [blame] | 153 | // Don't split the non-fallthrough edge from a callbr. |
| 154 | if (isa<CallBrInst>(TI) && SuccNum > 0) |
| 155 | return nullptr; |
| 156 | |
Craig Topper | 03e93f5 | 2019-03-12 18:20:25 +0000 | [diff] [blame] | 157 | if (Options.IgnoreUnreachableDests && |
| 158 | isa<UnreachableInst>(DestBB->getFirstNonPHIOrDbgOrLifetime())) |
| 159 | return nullptr; |
| 160 | |
Chris Lattner | 75f80bd | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 161 | // Create a new basic block, linking it into the CFG. |
Owen Anderson | 55f1c09 | 2009-08-13 21:58:54 +0000 | [diff] [blame] | 162 | BasicBlock *NewBB = BasicBlock::Create(TI->getContext(), |
| 163 | TIBB->getName() + "." + DestBB->getName() + "_crit_edge"); |
Chris Lattner | 72c4dce | 2010-02-13 04:24:19 +0000 | [diff] [blame] | 164 | // Create our unconditional branch. |
Devang Patel | c23bcbc | 2011-05-17 19:43:06 +0000 | [diff] [blame] | 165 | BranchInst *NewBI = BranchInst::Create(DestBB, NewBB); |
| 166 | NewBI->setDebugLoc(TI->getDebugLoc()); |
Misha Brukman | b1c9317 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 167 | |
Chris Lattner | 80ea207 | 2006-10-28 06:44:56 +0000 | [diff] [blame] | 168 | // Branch to the new block, breaking the edge. |
Chris Lattner | 75f80bd | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 169 | TI->setSuccessor(SuccNum, NewBB); |
| 170 | |
| 171 | // Insert the block into the function... right after the block TI lives in. |
| 172 | Function &F = *TIBB->getParent(); |
Duncan P. N. Exon Smith | 5b4c837 | 2015-10-13 02:39:05 +0000 | [diff] [blame] | 173 | Function::iterator FBBI = TIBB->getIterator(); |
Chris Lattner | 233f97a | 2007-04-17 18:09:47 +0000 | [diff] [blame] | 174 | F.getBasicBlockList().insert(++FBBI, NewBB); |
Andrew Trick | 411842f | 2011-10-04 03:34:49 +0000 | [diff] [blame] | 175 | |
Chris Lattner | 75f80bd | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 176 | // If there are any PHI nodes in DestBB, we need to update them so that they |
| 177 | // merge incoming values from NewBB instead of from TIBB. |
Jay Foad | 61ea0e4 | 2011-06-23 09:09:15 +0000 | [diff] [blame] | 178 | { |
| 179 | unsigned BBIdx = 0; |
| 180 | for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) { |
| 181 | // We no longer enter through TIBB, now we come in through NewBB. |
| 182 | // Revector exactly one entry in the PHI node that used to come from |
| 183 | // TIBB to come from NewBB. |
| 184 | PHINode *PN = cast<PHINode>(I); |
| 185 | |
| 186 | // Reuse the previous value of BBIdx if it lines up. In cases where we |
| 187 | // have multiple phi nodes with *lots* of predecessors, this is a speed |
| 188 | // win because we don't have to scan the PHI looking for TIBB. This |
| 189 | // happens because the BB list of PHI nodes are usually in the same |
| 190 | // order. |
| 191 | if (PN->getIncomingBlock(BBIdx) != TIBB) |
Andrew Trick | 411842f | 2011-10-04 03:34:49 +0000 | [diff] [blame] | 192 | BBIdx = PN->getBasicBlockIndex(TIBB); |
Jay Foad | 61ea0e4 | 2011-06-23 09:09:15 +0000 | [diff] [blame] | 193 | PN->setIncomingBlock(BBIdx, NewBB); |
Chris Lattner | 5e7f705 | 2010-02-13 05:01:14 +0000 | [diff] [blame] | 194 | } |
Chris Lattner | 75f80bd | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 195 | } |
Andrew Trick | 411842f | 2011-10-04 03:34:49 +0000 | [diff] [blame] | 196 | |
Chris Lattner | 80ea207 | 2006-10-28 06:44:56 +0000 | [diff] [blame] | 197 | // If there are any other edges from TIBB to DestBB, update those to go |
| 198 | // through the split block, making those edges non-critical as well (and |
| 199 | // reducing the number of phi entries in the DestBB if relevant). |
Chandler Carruth | 37df2cf | 2015-01-19 12:09:11 +0000 | [diff] [blame] | 200 | if (Options.MergeIdenticalEdges) { |
Chris Lattner | 80ea207 | 2006-10-28 06:44:56 +0000 | [diff] [blame] | 201 | for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) { |
| 202 | if (TI->getSuccessor(i) != DestBB) continue; |
Andrew Trick | 411842f | 2011-10-04 03:34:49 +0000 | [diff] [blame] | 203 | |
Chris Lattner | 80ea207 | 2006-10-28 06:44:56 +0000 | [diff] [blame] | 204 | // Remove an entry for TIBB from DestBB phi nodes. |
Max Kazantsev | 20b9189 | 2019-02-12 07:09:29 +0000 | [diff] [blame] | 205 | DestBB->removePredecessor(TIBB, Options.KeepOneInputPHIs); |
Andrew Trick | 411842f | 2011-10-04 03:34:49 +0000 | [diff] [blame] | 206 | |
Chris Lattner | 80ea207 | 2006-10-28 06:44:56 +0000 | [diff] [blame] | 207 | // We found another edge to DestBB, go to NewBB instead. |
| 208 | TI->setSuccessor(i, NewBB); |
| 209 | } |
| 210 | } |
Andrew Trick | 411842f | 2011-10-04 03:34:49 +0000 | [diff] [blame] | 211 | |
Chris Lattner | 5e7f705 | 2010-02-13 05:01:14 +0000 | [diff] [blame] | 212 | // If we have nothing to update, just return. |
Chandler Carruth | 37df2cf | 2015-01-19 12:09:11 +0000 | [diff] [blame] | 213 | auto *DT = Options.DT; |
Matt Arsenault | 65b4ab9 | 2019-02-22 15:01:41 +0000 | [diff] [blame] | 214 | auto *PDT = Options.PDT; |
Chandler Carruth | 37df2cf | 2015-01-19 12:09:11 +0000 | [diff] [blame] | 215 | auto *LI = Options.LI; |
Alina Sbirlea | ab6f84f7 | 2018-08-21 23:32:03 +0000 | [diff] [blame] | 216 | auto *MSSAU = Options.MSSAU; |
| 217 | if (MSSAU) |
Alina Sbirlea | f98c2c5 | 2018-09-07 21:14:48 +0000 | [diff] [blame] | 218 | MSSAU->wireOldPredecessorsToNewImmediatePredecessor( |
| 219 | DestBB, NewBB, {TIBB}, Options.MergeIdenticalEdges); |
Alina Sbirlea | ab6f84f7 | 2018-08-21 23:32:03 +0000 | [diff] [blame] | 220 | |
Matt Arsenault | 65b4ab9 | 2019-02-22 15:01:41 +0000 | [diff] [blame] | 221 | if (!DT && !PDT && !LI) |
Chris Lattner | 5e7f705 | 2010-02-13 05:01:14 +0000 | [diff] [blame] | 222 | return NewBB; |
Chris Lattner | 5ac72de | 2002-10-08 21:06:27 +0000 | [diff] [blame] | 223 | |
Matt Arsenault | 65b4ab9 | 2019-02-22 15:01:41 +0000 | [diff] [blame] | 224 | if (DT || PDT) { |
Jakub Kuderski | e35a449 | 2017-08-17 16:45:35 +0000 | [diff] [blame] | 225 | // Update the DominatorTree. |
| 226 | // ---> NewBB -----\ |
| 227 | // / V |
| 228 | // TIBB -------\\------> DestBB |
Chris Lattner | bedbd6b | 2002-09-26 16:18:51 +0000 | [diff] [blame] | 229 | // |
Jakub Kuderski | e35a449 | 2017-08-17 16:45:35 +0000 | [diff] [blame] | 230 | // First, inform the DT about the new path from TIBB to DestBB via NewBB, |
| 231 | // then delete the old edge from TIBB to DestBB. By doing this in that order |
| 232 | // DestBB stays reachable in the DT the whole time and its subtree doesn't |
| 233 | // get disconnected. |
| 234 | SmallVector<DominatorTree::UpdateType, 3> Updates; |
| 235 | Updates.push_back({DominatorTree::Insert, TIBB, NewBB}); |
| 236 | Updates.push_back({DominatorTree::Insert, NewBB, DestBB}); |
| 237 | if (llvm::find(successors(TIBB), DestBB) == succ_end(TIBB)) |
| 238 | Updates.push_back({DominatorTree::Delete, TIBB, DestBB}); |
Andrew Trick | 411842f | 2011-10-04 03:34:49 +0000 | [diff] [blame] | 239 | |
Matt Arsenault | 65b4ab9 | 2019-02-22 15:01:41 +0000 | [diff] [blame] | 240 | if (DT) |
| 241 | DT->applyUpdates(Updates); |
| 242 | if (PDT) |
| 243 | PDT->applyUpdates(Updates); |
Chris Lattner | 75f80bd | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 244 | } |
Chris Lattner | 12764c8 | 2002-10-31 02:44:36 +0000 | [diff] [blame] | 245 | |
Chris Lattner | 89c1dfc | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 246 | // Update LoopInfo if it is around. |
Chris Lattner | 5e7f705 | 2010-02-13 05:01:14 +0000 | [diff] [blame] | 247 | if (LI) { |
Dan Gohman | 3ddbc24 | 2009-09-08 15:45:00 +0000 | [diff] [blame] | 248 | if (Loop *TIL = LI->getLoopFor(TIBB)) { |
| 249 | // If one or the other blocks were not in a loop, the new block is not |
| 250 | // either, and thus LI doesn't need to be updated. |
Chris Lattner | 89c1dfc | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 251 | if (Loop *DestLoop = LI->getLoopFor(DestBB)) { |
| 252 | if (TIL == DestLoop) { |
| 253 | // Both in the same loop, the NewBB joins loop. |
Chandler Carruth | 691addc | 2015-01-18 01:25:51 +0000 | [diff] [blame] | 254 | DestLoop->addBasicBlockToLoop(NewBB, *LI); |
Dan Gohman | 18fa568 | 2009-12-18 01:24:09 +0000 | [diff] [blame] | 255 | } else if (TIL->contains(DestLoop)) { |
Chris Lattner | 8aca0ee | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 256 | // Edge from an outer loop to an inner loop. Add to the outer loop. |
Chandler Carruth | 691addc | 2015-01-18 01:25:51 +0000 | [diff] [blame] | 257 | TIL->addBasicBlockToLoop(NewBB, *LI); |
Dan Gohman | 18fa568 | 2009-12-18 01:24:09 +0000 | [diff] [blame] | 258 | } else if (DestLoop->contains(TIL)) { |
Chris Lattner | 8aca0ee | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 259 | // Edge from an inner loop to an outer loop. Add to the outer loop. |
Chandler Carruth | 691addc | 2015-01-18 01:25:51 +0000 | [diff] [blame] | 260 | DestLoop->addBasicBlockToLoop(NewBB, *LI); |
Chris Lattner | 89c1dfc | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 261 | } else { |
| 262 | // Edge from two loops with no containment relation. Because these |
| 263 | // are natural loops, we know that the destination block must be the |
| 264 | // header of its loop (adding a branch into a loop elsewhere would |
| 265 | // create an irreducible loop). |
| 266 | assert(DestLoop->getHeader() == DestBB && |
| 267 | "Should not create irreducible loops!"); |
| 268 | if (Loop *P = DestLoop->getParentLoop()) |
Chandler Carruth | 691addc | 2015-01-18 01:25:51 +0000 | [diff] [blame] | 269 | P->addBasicBlockToLoop(NewBB, *LI); |
Chris Lattner | 89c1dfc | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 270 | } |
| 271 | } |
Chandler Carruth | ad34d91 | 2015-01-19 10:23:00 +0000 | [diff] [blame] | 272 | |
Chandler Carruth | d4be9dc | 2014-01-29 13:16:53 +0000 | [diff] [blame] | 273 | // If TIBB is in a loop and DestBB is outside of that loop, we may need |
| 274 | // to update LoopSimplify form and LCSSA form. |
Chandler Carruth | ad34d91 | 2015-01-19 10:23:00 +0000 | [diff] [blame] | 275 | if (!TIL->contains(DestBB)) { |
Dan Gohman | ec4557f | 2009-09-09 18:18:18 +0000 | [diff] [blame] | 276 | assert(!TIL->contains(NewBB) && |
| 277 | "Split point for loop exit is contained in loop!"); |
| 278 | |
| 279 | // Update LCSSA form in the newly created exit block. |
Chandler Carruth | 37df2cf | 2015-01-19 12:09:11 +0000 | [diff] [blame] | 280 | if (Options.PreserveLCSSA) { |
Bill Wendling | 325e6cd | 2012-04-30 10:25:51 +0000 | [diff] [blame] | 281 | createPHIsForSplitLoopExit(TIBB, NewBB, DestBB); |
Chandler Carruth | ad34d91 | 2015-01-19 10:23:00 +0000 | [diff] [blame] | 282 | } |
Dan Gohman | ec4557f | 2009-09-09 18:18:18 +0000 | [diff] [blame] | 283 | |
Chandler Carruth | d4be9dc | 2014-01-29 13:16:53 +0000 | [diff] [blame] | 284 | // The only that we can break LoopSimplify form by splitting a critical |
| 285 | // edge is if after the split there exists some edge from TIL to DestBB |
| 286 | // *and* the only edge into DestBB from outside of TIL is that of |
| 287 | // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB |
| 288 | // is the new exit block and it has no non-loop predecessors. If the |
| 289 | // second isn't true, then DestBB was not in LoopSimplify form prior to |
| 290 | // the split as it had a non-loop predecessor. In both of these cases, |
| 291 | // the predecessor must be directly in TIL, not in a subloop, or again |
| 292 | // LoopSimplify doesn't hold. |
| 293 | SmallVector<BasicBlock *, 4> LoopPreds; |
Duncan P. N. Exon Smith | 6c99015 | 2014-07-21 17:06:51 +0000 | [diff] [blame] | 294 | for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); I != E; |
| 295 | ++I) { |
| 296 | BasicBlock *P = *I; |
Chandler Carruth | d4be9dc | 2014-01-29 13:16:53 +0000 | [diff] [blame] | 297 | if (P == NewBB) |
| 298 | continue; // The new block is known. |
| 299 | if (LI->getLoopFor(P) != TIL) { |
| 300 | // No need to re-simplify, it wasn't to start with. |
| 301 | LoopPreds.clear(); |
| 302 | break; |
Gabor Greif | fd8e7d4 | 2010-07-09 16:31:08 +0000 | [diff] [blame] | 303 | } |
Chandler Carruth | d4be9dc | 2014-01-29 13:16:53 +0000 | [diff] [blame] | 304 | LoopPreds.push_back(P); |
| 305 | } |
| 306 | if (!LoopPreds.empty()) { |
David Majnemer | eb518bd | 2015-08-04 08:21:40 +0000 | [diff] [blame] | 307 | assert(!DestBB->isEHPad() && "We don't split edges to EH pads!"); |
Chandler Carruth | b5797b6 | 2015-01-18 09:21:15 +0000 | [diff] [blame] | 308 | BasicBlock *NewExitBB = SplitBlockPredecessors( |
Alina Sbirlea | ab6f84f7 | 2018-08-21 23:32:03 +0000 | [diff] [blame] | 309 | DestBB, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA); |
Chandler Carruth | 37df2cf | 2015-01-19 12:09:11 +0000 | [diff] [blame] | 310 | if (Options.PreserveLCSSA) |
Chandler Carruth | d4be9dc | 2014-01-29 13:16:53 +0000 | [diff] [blame] | 311 | createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB); |
Dan Gohman | 3ddbc24 | 2009-09-08 15:45:00 +0000 | [diff] [blame] | 312 | } |
| 313 | } |
Dan Gohman | 3ddbc24 | 2009-09-08 15:45:00 +0000 | [diff] [blame] | 314 | } |
Chris Lattner | 89c1dfc | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 315 | } |
Dan Gohman | 3ddbc24 | 2009-09-08 15:45:00 +0000 | [diff] [blame] | 316 | |
| 317 | return NewBB; |
Chris Lattner | 75f80bd | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 318 | } |
Hiroshi Yamauchi | 9364fa3 | 2017-12-04 20:36:01 +0000 | [diff] [blame] | 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. |
| 324 | static BasicBlock * |
| 325 | findIBRPredecessor(BasicBlock *BB, SmallVectorImpl<BasicBlock *> &OtherPreds) { |
| 326 | // If the block doesn't have any PHIs, we don't care about it, since there's |
| 327 | // no point in splitting it. |
| 328 | PHINode *PN = dyn_cast<PHINode>(BB->begin()); |
| 329 | if (!PN) |
| 330 | return nullptr; |
| 331 | |
| 332 | // Verify we have exactly one IBR predecessor. |
| 333 | // Conservatively bail out if one of the other predecessors is not a "regular" |
| 334 | // terminator (that is, not a switch or a br). |
| 335 | BasicBlock *IBB = nullptr; |
| 336 | for (unsigned Pred = 0, E = PN->getNumIncomingValues(); Pred != E; ++Pred) { |
| 337 | BasicBlock *PredBB = PN->getIncomingBlock(Pred); |
Chandler Carruth | edb12a8 | 2018-10-15 10:04:59 +0000 | [diff] [blame] | 338 | Instruction *PredTerm = PredBB->getTerminator(); |
Hiroshi Yamauchi | 9364fa3 | 2017-12-04 20:36:01 +0000 | [diff] [blame] | 339 | switch (PredTerm->getOpcode()) { |
| 340 | case Instruction::IndirectBr: |
| 341 | if (IBB) |
| 342 | return nullptr; |
| 343 | IBB = PredBB; |
| 344 | break; |
| 345 | case Instruction::Br: |
| 346 | case Instruction::Switch: |
| 347 | OtherPreds.push_back(PredBB); |
| 348 | continue; |
| 349 | default: |
| 350 | return nullptr; |
| 351 | } |
| 352 | } |
| 353 | |
| 354 | return IBB; |
| 355 | } |
| 356 | |
Hiroshi Yamauchi | f3bda1d | 2017-12-12 19:07:43 +0000 | [diff] [blame] | 357 | bool llvm::SplitIndirectBrCriticalEdges(Function &F, |
| 358 | BranchProbabilityInfo *BPI, |
| 359 | BlockFrequencyInfo *BFI) { |
Hiroshi Yamauchi | 9364fa3 | 2017-12-04 20:36:01 +0000 | [diff] [blame] | 360 | // Check whether the function has any indirectbrs, and collect which blocks |
| 361 | // they may jump to. Since most functions don't have indirect branches, |
| 362 | // this lowers the common case's overhead to O(Blocks) instead of O(Edges). |
| 363 | SmallSetVector<BasicBlock *, 16> Targets; |
| 364 | for (auto &BB : F) { |
| 365 | auto *IBI = dyn_cast<IndirectBrInst>(BB.getTerminator()); |
| 366 | if (!IBI) |
| 367 | continue; |
| 368 | |
| 369 | for (unsigned Succ = 0, E = IBI->getNumSuccessors(); Succ != E; ++Succ) |
| 370 | Targets.insert(IBI->getSuccessor(Succ)); |
| 371 | } |
| 372 | |
| 373 | if (Targets.empty()) |
| 374 | return false; |
| 375 | |
Hiroshi Yamauchi | f3bda1d | 2017-12-12 19:07:43 +0000 | [diff] [blame] | 376 | bool ShouldUpdateAnalysis = BPI && BFI; |
Hiroshi Yamauchi | 9364fa3 | 2017-12-04 20:36:01 +0000 | [diff] [blame] | 377 | bool Changed = false; |
| 378 | for (BasicBlock *Target : Targets) { |
| 379 | SmallVector<BasicBlock *, 16> OtherPreds; |
| 380 | BasicBlock *IBRPred = findIBRPredecessor(Target, OtherPreds); |
| 381 | // If we did not found an indirectbr, or the indirectbr is the only |
| 382 | // incoming edge, this isn't the kind of edge we're looking for. |
| 383 | if (!IBRPred || OtherPreds.empty()) |
| 384 | continue; |
| 385 | |
| 386 | // Don't even think about ehpads/landingpads. |
| 387 | Instruction *FirstNonPHI = Target->getFirstNonPHI(); |
| 388 | if (FirstNonPHI->isEHPad() || Target->isLandingPad()) |
| 389 | continue; |
| 390 | |
| 391 | BasicBlock *BodyBlock = Target->splitBasicBlock(FirstNonPHI, ".split"); |
Hiroshi Yamauchi | f3bda1d | 2017-12-12 19:07:43 +0000 | [diff] [blame] | 392 | if (ShouldUpdateAnalysis) { |
| 393 | // Copy the BFI/BPI from Target to BodyBlock. |
| 394 | for (unsigned I = 0, E = BodyBlock->getTerminator()->getNumSuccessors(); |
| 395 | I < E; ++I) |
| 396 | BPI->setEdgeProbability(BodyBlock, I, |
| 397 | BPI->getEdgeProbability(Target, I)); |
| 398 | BFI->setBlockFreq(BodyBlock, BFI->getBlockFreq(Target).getFrequency()); |
| 399 | } |
Hiroshi Yamauchi | 9364fa3 | 2017-12-04 20:36:01 +0000 | [diff] [blame] | 400 | // It's possible Target was its own successor through an indirectbr. |
| 401 | // In this case, the indirectbr now comes from BodyBlock. |
| 402 | if (IBRPred == Target) |
| 403 | IBRPred = BodyBlock; |
| 404 | |
| 405 | // At this point Target only has PHIs, and BodyBlock has the rest of the |
| 406 | // block's body. Create a copy of Target that will be used by the "direct" |
| 407 | // preds. |
| 408 | ValueToValueMapTy VMap; |
| 409 | BasicBlock *DirectSucc = CloneBasicBlock(Target, VMap, ".clone", &F); |
| 410 | |
Hiroshi Yamauchi | f3bda1d | 2017-12-12 19:07:43 +0000 | [diff] [blame] | 411 | BlockFrequency BlockFreqForDirectSucc; |
Hiroshi Yamauchi | 9364fa3 | 2017-12-04 20:36:01 +0000 | [diff] [blame] | 412 | for (BasicBlock *Pred : OtherPreds) { |
| 413 | // If the target is a loop to itself, then the terminator of the split |
Hiroshi Yamauchi | f3bda1d | 2017-12-12 19:07:43 +0000 | [diff] [blame] | 414 | // block (BodyBlock) needs to be updated. |
| 415 | BasicBlock *Src = Pred != Target ? Pred : BodyBlock; |
| 416 | Src->getTerminator()->replaceUsesOfWith(Target, DirectSucc); |
| 417 | if (ShouldUpdateAnalysis) |
| 418 | BlockFreqForDirectSucc += BFI->getBlockFreq(Src) * |
| 419 | BPI->getEdgeProbability(Src, DirectSucc); |
| 420 | } |
| 421 | if (ShouldUpdateAnalysis) { |
| 422 | BFI->setBlockFreq(DirectSucc, BlockFreqForDirectSucc.getFrequency()); |
| 423 | BlockFrequency NewBlockFreqForTarget = |
| 424 | BFI->getBlockFreq(Target) - BlockFreqForDirectSucc; |
| 425 | BFI->setBlockFreq(Target, NewBlockFreqForTarget.getFrequency()); |
| 426 | BPI->eraseBlock(Target); |
Hiroshi Yamauchi | 9364fa3 | 2017-12-04 20:36:01 +0000 | [diff] [blame] | 427 | } |
| 428 | |
| 429 | // Ok, now fix up the PHIs. We know the two blocks only have PHIs, and that |
| 430 | // they are clones, so the number of PHIs are the same. |
| 431 | // (a) Remove the edge coming from IBRPred from the "Direct" PHI |
| 432 | // (b) Leave that as the only edge in the "Indirect" PHI. |
| 433 | // (c) Merge the two in the body block. |
| 434 | BasicBlock::iterator Indirect = Target->begin(), |
| 435 | End = Target->getFirstNonPHI()->getIterator(); |
| 436 | BasicBlock::iterator Direct = DirectSucc->begin(); |
| 437 | BasicBlock::iterator MergeInsert = BodyBlock->getFirstInsertionPt(); |
| 438 | |
| 439 | assert(&*End == Target->getTerminator() && |
| 440 | "Block was expected to only contain PHIs"); |
| 441 | |
| 442 | while (Indirect != End) { |
| 443 | PHINode *DirPHI = cast<PHINode>(Direct); |
| 444 | PHINode *IndPHI = cast<PHINode>(Indirect); |
| 445 | |
| 446 | // Now, clean up - the direct block shouldn't get the indirect value, |
| 447 | // and vice versa. |
| 448 | DirPHI->removeIncomingValue(IBRPred); |
| 449 | Direct++; |
| 450 | |
| 451 | // Advance the pointer here, to avoid invalidation issues when the old |
| 452 | // PHI is erased. |
| 453 | Indirect++; |
| 454 | |
| 455 | PHINode *NewIndPHI = PHINode::Create(IndPHI->getType(), 1, "ind", IndPHI); |
| 456 | NewIndPHI->addIncoming(IndPHI->getIncomingValueForBlock(IBRPred), |
| 457 | IBRPred); |
| 458 | |
| 459 | // Create a PHI in the body block, to merge the direct and indirect |
| 460 | // predecessors. |
| 461 | PHINode *MergePHI = |
| 462 | PHINode::Create(IndPHI->getType(), 2, "merge", &*MergeInsert); |
| 463 | MergePHI->addIncoming(NewIndPHI, Target); |
| 464 | MergePHI->addIncoming(DirPHI, DirectSucc); |
| 465 | |
| 466 | IndPHI->replaceAllUsesWith(MergePHI); |
| 467 | IndPHI->eraseFromParent(); |
| 468 | } |
| 469 | |
| 470 | Changed = true; |
| 471 | } |
| 472 | |
| 473 | return Changed; |
| 474 | } |