LLVM  6.0.0svn
BreakCriticalEdges.cpp
Go to the documentation of this file.
1 //===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // BreakCriticalEdges pass - Break all of the critical edges in the CFG by
11 // inserting a dummy basic block. This pass may be "required" by passes that
12 // cannot deal with critical edges. For this usage, the structure type is
13 // forward declared. This pass obviously invalidates the CFG, but can update
14 // dominator trees.
15 //
16 //===----------------------------------------------------------------------===//
17 
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/Statistic.h"
22 #include "llvm/Analysis/CFG.h"
23 #include "llvm/Analysis/LoopInfo.h"
24 #include "llvm/IR/CFG.h"
25 #include "llvm/IR/Dominators.h"
26 #include "llvm/IR/Instructions.h"
27 #include "llvm/IR/Type.h"
29 #include "llvm/Transforms/Scalar.h"
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "break-crit-edges"
34 
35 STATISTIC(NumBroken, "Number of blocks inserted");
36 
37 namespace {
38  struct BreakCriticalEdges : public FunctionPass {
39  static char ID; // Pass identification, replacement for typeid
40  BreakCriticalEdges() : FunctionPass(ID) {
42  }
43 
44  bool runOnFunction(Function &F) override {
45  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
46  auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
47  auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
48  auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
49  unsigned N =
51  NumBroken += N;
52  return N > 0;
53  }
54 
55  void getAnalysisUsage(AnalysisUsage &AU) const override {
58 
59  // No loop canonicalization guarantees are broken by this pass.
61  }
62  };
63 }
64 
65 char BreakCriticalEdges::ID = 0;
66 INITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges",
67  "Break critical edges in CFG", false, false)
68 
69 // Publicly exposed interface to pass...
70 char &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID;
72  return new BreakCriticalEdges();
73 }
74 
77  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
78  auto *LI = AM.getCachedResult<LoopAnalysis>(F);
80  NumBroken += N;
81  if (N == 0)
82  return PreservedAnalyses::all();
85  PA.preserve<LoopAnalysis>();
86  return PA;
87 }
88 
89 //===----------------------------------------------------------------------===//
90 // Implementation of the external critical edge manipulation functions
91 //===----------------------------------------------------------------------===//
92 
93 /// When a loop exit edge is split, LCSSA form may require new PHIs in the new
94 /// exit block. This function inserts the new PHIs, as needed. Preds is a list
95 /// of preds inside the loop, SplitBB is the new loop exit block, and DestBB is
96 /// the old loop exit, now the successor of SplitBB.
98  BasicBlock *SplitBB,
99  BasicBlock *DestBB) {
100  // SplitBB shouldn't have anything non-trivial in it yet.
101  assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() ||
102  SplitBB->isLandingPad()) && "SplitBB has non-PHI nodes!");
103 
104  // For each PHI in the destination block.
105  for (BasicBlock::iterator I = DestBB->begin();
106  PHINode *PN = dyn_cast<PHINode>(I); ++I) {
107  unsigned Idx = PN->getBasicBlockIndex(SplitBB);
108  Value *V = PN->getIncomingValue(Idx);
109 
110  // If the input is a PHI which already satisfies LCSSA, don't create
111  // a new one.
112  if (const PHINode *VP = dyn_cast<PHINode>(V))
113  if (VP->getParent() == SplitBB)
114  continue;
115 
116  // Otherwise a new PHI is needed. Create one and populate it.
117  PHINode *NewPN = PHINode::Create(
118  PN->getType(), Preds.size(), "split",
119  SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator());
120  for (unsigned i = 0, e = Preds.size(); i != e; ++i)
121  NewPN->addIncoming(V, Preds[i]);
122 
123  // Update the original PHI.
124  PN->setIncomingValue(Idx, NewPN);
125  }
126 }
127 
128 BasicBlock *
130  const CriticalEdgeSplittingOptions &Options) {
131  if (!isCriticalEdge(TI, SuccNum, Options.MergeIdenticalEdges))
132  return nullptr;
133 
134  assert(!isa<IndirectBrInst>(TI) &&
135  "Cannot split critical edge from IndirectBrInst");
136 
137  BasicBlock *TIBB = TI->getParent();
138  BasicBlock *DestBB = TI->getSuccessor(SuccNum);
139 
140  // Splitting the critical edge to a pad block is non-trivial. Don't do
141  // it in this generic function.
142  if (DestBB->isEHPad()) return nullptr;
143 
144  // Create a new basic block, linking it into the CFG.
146  TIBB->getName() + "." + DestBB->getName() + "_crit_edge");
147  // Create our unconditional branch.
148  BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);
149  NewBI->setDebugLoc(TI->getDebugLoc());
150 
151  // Branch to the new block, breaking the edge.
152  TI->setSuccessor(SuccNum, NewBB);
153 
154  // Insert the block into the function... right after the block TI lives in.
155  Function &F = *TIBB->getParent();
156  Function::iterator FBBI = TIBB->getIterator();
157  F.getBasicBlockList().insert(++FBBI, NewBB);
158 
159  // If there are any PHI nodes in DestBB, we need to update them so that they
160  // merge incoming values from NewBB instead of from TIBB.
161  {
162  unsigned BBIdx = 0;
163  for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
164  // We no longer enter through TIBB, now we come in through NewBB.
165  // Revector exactly one entry in the PHI node that used to come from
166  // TIBB to come from NewBB.
167  PHINode *PN = cast<PHINode>(I);
168 
169  // Reuse the previous value of BBIdx if it lines up. In cases where we
170  // have multiple phi nodes with *lots* of predecessors, this is a speed
171  // win because we don't have to scan the PHI looking for TIBB. This
172  // happens because the BB list of PHI nodes are usually in the same
173  // order.
174  if (PN->getIncomingBlock(BBIdx) != TIBB)
175  BBIdx = PN->getBasicBlockIndex(TIBB);
176  PN->setIncomingBlock(BBIdx, NewBB);
177  }
178  }
179 
180  // If there are any other edges from TIBB to DestBB, update those to go
181  // through the split block, making those edges non-critical as well (and
182  // reducing the number of phi entries in the DestBB if relevant).
183  if (Options.MergeIdenticalEdges) {
184  for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
185  if (TI->getSuccessor(i) != DestBB) continue;
186 
187  // Remove an entry for TIBB from DestBB phi nodes.
188  DestBB->removePredecessor(TIBB, Options.DontDeleteUselessPHIs);
189 
190  // We found another edge to DestBB, go to NewBB instead.
191  TI->setSuccessor(i, NewBB);
192  }
193  }
194 
195  // If we have nothing to update, just return.
196  auto *DT = Options.DT;
197  auto *LI = Options.LI;
198  if (!DT && !LI)
199  return NewBB;
200 
201  if (DT) {
202  // Update the DominatorTree.
203  // ---> NewBB -----\
204  // / V
205  // TIBB -------\\------> DestBB
206  //
207  // First, inform the DT about the new path from TIBB to DestBB via NewBB,
208  // then delete the old edge from TIBB to DestBB. By doing this in that order
209  // DestBB stays reachable in the DT the whole time and its subtree doesn't
210  // get disconnected.
212  Updates.push_back({DominatorTree::Insert, TIBB, NewBB});
213  Updates.push_back({DominatorTree::Insert, NewBB, DestBB});
214  if (llvm::find(successors(TIBB), DestBB) == succ_end(TIBB))
215  Updates.push_back({DominatorTree::Delete, TIBB, DestBB});
216 
217  DT->applyUpdates(Updates);
218  }
219 
220  // Update LoopInfo if it is around.
221  if (LI) {
222  if (Loop *TIL = LI->getLoopFor(TIBB)) {
223  // If one or the other blocks were not in a loop, the new block is not
224  // either, and thus LI doesn't need to be updated.
225  if (Loop *DestLoop = LI->getLoopFor(DestBB)) {
226  if (TIL == DestLoop) {
227  // Both in the same loop, the NewBB joins loop.
228  DestLoop->addBasicBlockToLoop(NewBB, *LI);
229  } else if (TIL->contains(DestLoop)) {
230  // Edge from an outer loop to an inner loop. Add to the outer loop.
231  TIL->addBasicBlockToLoop(NewBB, *LI);
232  } else if (DestLoop->contains(TIL)) {
233  // Edge from an inner loop to an outer loop. Add to the outer loop.
234  DestLoop->addBasicBlockToLoop(NewBB, *LI);
235  } else {
236  // Edge from two loops with no containment relation. Because these
237  // are natural loops, we know that the destination block must be the
238  // header of its loop (adding a branch into a loop elsewhere would
239  // create an irreducible loop).
240  assert(DestLoop->getHeader() == DestBB &&
241  "Should not create irreducible loops!");
242  if (Loop *P = DestLoop->getParentLoop())
243  P->addBasicBlockToLoop(NewBB, *LI);
244  }
245  }
246 
247  // If TIBB is in a loop and DestBB is outside of that loop, we may need
248  // to update LoopSimplify form and LCSSA form.
249  if (!TIL->contains(DestBB)) {
250  assert(!TIL->contains(NewBB) &&
251  "Split point for loop exit is contained in loop!");
252 
253  // Update LCSSA form in the newly created exit block.
254  if (Options.PreserveLCSSA) {
255  createPHIsForSplitLoopExit(TIBB, NewBB, DestBB);
256  }
257 
258  // The only that we can break LoopSimplify form by splitting a critical
259  // edge is if after the split there exists some edge from TIL to DestBB
260  // *and* the only edge into DestBB from outside of TIL is that of
261  // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB
262  // is the new exit block and it has no non-loop predecessors. If the
263  // second isn't true, then DestBB was not in LoopSimplify form prior to
264  // the split as it had a non-loop predecessor. In both of these cases,
265  // the predecessor must be directly in TIL, not in a subloop, or again
266  // LoopSimplify doesn't hold.
268  for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); I != E;
269  ++I) {
270  BasicBlock *P = *I;
271  if (P == NewBB)
272  continue; // The new block is known.
273  if (LI->getLoopFor(P) != TIL) {
274  // No need to re-simplify, it wasn't to start with.
275  LoopPreds.clear();
276  break;
277  }
278  LoopPreds.push_back(P);
279  }
280  if (!LoopPreds.empty()) {
281  assert(!DestBB->isEHPad() && "We don't split edges to EH pads!");
282  BasicBlock *NewExitBB = SplitBlockPredecessors(
283  DestBB, LoopPreds, "split", DT, LI, Options.PreserveLCSSA);
284  if (Options.PreserveLCSSA)
285  createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);
286  }
287  }
288  }
289  }
290 
291  return NewBB;
292 }
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void removePredecessor(BasicBlock *Pred, bool DontDeleteUselessPHIs=false)
Notify the BasicBlock that the predecessor Pred is no longer able to reach it.
Definition: BasicBlock.cpp:276
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BasicBlock * getSuccessor(unsigned idx) const
Return the specified successor.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:728
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:238
F(f)
unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
Loop over all of the edges in the CFG, breaking critical edges as they are found. ...
void initializeBreakCriticalEdgesPass(PassRegistry &)
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Option class for critical edge splitting.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:933
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
AnalysisUsage & addPreservedID(const void *ID)
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
BasicBlock * SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
If this edge is a critical edge, insert a new node to split the critical edge.
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:171
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:54
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
void setSuccessor(unsigned idx, BasicBlock *B)
Update the specified successor to point at the provided block.
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
Conditional or Unconditional Branch instruction.
char & BreakCriticalEdgesID
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const Instruction & front() const
Definition: BasicBlock.h:264
FunctionPass * createBreakCriticalEdgesPass()
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:101
self_iterator getIterator()
Definition: ilist_node.h:82
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:834
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:34
char & LoopSimplifyID
bool isLandingPad() const
Return true if this basic block is a landing pad.
Definition: BasicBlock.cpp:442
Iterator for intrusive lists based on ilist_node.
void setIncomingBlock(unsigned i, BasicBlock *BB)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
iterator insert(iterator where, pointer New)
Definition: ilist.h:241
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:284
static void createPHIsForSplitLoopExit(ArrayRef< BasicBlock *> Preds, BasicBlock *SplitBB, BasicBlock *DestBB)
When a loop exit edge is split, LCSSA form may require new PHIs in the new exit block.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:439
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:220
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:706
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:565
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getNumSuccessors() const
Return the number of successors that this terminator has.
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:383
LLVM Value Representation.
Definition: Value.h:73
succ_range successors(BasicBlock *BB)
Definition: CFG.h:143
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:958
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:120
void setIncomingValue(unsigned i, Value *V)
const BasicBlock * getParent() const
Definition: Instruction.h:66
bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:88