• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- Transform/Utils/BasicBlockUtils.h - BasicBlock Utils -----*- C++ -*-===//
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 // This family of functions perform manipulations on basic blocks, and
10 // instructions contained within basic blocks.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
15 #define LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
16 
17 // FIXME: Move to this file: BasicBlock::removePredecessor, BB::splitBasicBlock
18 
19 #include "llvm/ADT/ArrayRef.h"
20 #include "llvm/Analysis/DomTreeUpdater.h"
21 #include "llvm/IR/BasicBlock.h"
22 #include "llvm/IR/CFG.h"
23 #include "llvm/IR/InstrTypes.h"
24 #include <cassert>
25 
26 namespace llvm {
27 
28 class BlockFrequencyInfo;
29 class BranchProbabilityInfo;
30 class DominatorTree;
31 class DomTreeUpdater;
32 class Function;
33 class Instruction;
34 class LoopInfo;
35 class MDNode;
36 class MemoryDependenceResults;
37 class MemorySSAUpdater;
38 class PostDominatorTree;
39 class ReturnInst;
40 class TargetLibraryInfo;
41 class Value;
42 
43 /// Replace contents of every block in \p BBs with single unreachable
44 /// instruction. If \p Updates is specified, collect all necessary DT updates
45 /// into this vector. If \p KeepOneInputPHIs is true, one-input Phis in
46 /// successors of blocks being deleted will be preserved.
47 void DetatchDeadBlocks(ArrayRef <BasicBlock *> BBs,
48                        SmallVectorImpl<DominatorTree::UpdateType> *Updates,
49                        bool KeepOneInputPHIs = false);
50 
51 /// Delete the specified block, which must have no predecessors.
52 void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU = nullptr,
53                      bool KeepOneInputPHIs = false);
54 
55 /// Delete the specified blocks from \p BB. The set of deleted blocks must have
56 /// no predecessors that are not being deleted themselves. \p BBs must have no
57 /// duplicating blocks. If there are loops among this set of blocks, all
58 /// relevant loop info updates should be done before this function is called.
59 /// If \p KeepOneInputPHIs is true, one-input Phis in successors of blocks
60 /// being deleted will be preserved.
61 void DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs,
62                       DomTreeUpdater *DTU = nullptr,
63                       bool KeepOneInputPHIs = false);
64 
65 /// Delete all basic blocks from \p F that are not reachable from its entry
66 /// node. If \p KeepOneInputPHIs is true, one-input Phis in successors of
67 /// blocks being deleted will be preserved.
68 bool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU = nullptr,
69                                 bool KeepOneInputPHIs = false);
70 
71 /// We know that BB has one predecessor. If there are any single-entry PHI nodes
72 /// in it, fold them away. This handles the case when all entries to the PHI
73 /// nodes in a block are guaranteed equal, such as when the block has exactly
74 /// one predecessor.
75 void FoldSingleEntryPHINodes(BasicBlock *BB,
76                              MemoryDependenceResults *MemDep = nullptr);
77 
78 /// Examine each PHI in the given block and delete it if it is dead. Also
79 /// recursively delete any operands that become dead as a result. This includes
80 /// tracing the def-use list from the PHI to see if it is ultimately unused or
81 /// if it reaches an unused cycle. Return true if any PHIs were deleted.
82 bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr);
83 
84 /// Attempts to merge a block into its predecessor, if possible. The return
85 /// value indicates success or failure.
86 /// By default do not merge blocks if BB's predecessor has multiple successors.
87 /// If PredecessorWithTwoSuccessors = true, the blocks can only be merged
88 /// if BB's Pred has a branch to BB and to AnotherBB, and BB has a single
89 /// successor Sing. In this case the branch will be updated with Sing instead of
90 /// BB, and BB will still be merged into its predecessor and removed.
91 bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU = nullptr,
92                                LoopInfo *LI = nullptr,
93                                MemorySSAUpdater *MSSAU = nullptr,
94                                MemoryDependenceResults *MemDep = nullptr,
95                                bool PredecessorWithTwoSuccessors = false);
96 
97 /// Try to remove redundant dbg.value instructions from given basic block.
98 /// Returns true if at least one instruction was removed.
99 bool RemoveRedundantDbgInstrs(BasicBlock *BB);
100 
101 /// Replace all uses of an instruction (specified by BI) with a value, then
102 /// remove and delete the original instruction.
103 void ReplaceInstWithValue(BasicBlock::InstListType &BIL,
104                           BasicBlock::iterator &BI, Value *V);
105 
106 /// Replace the instruction specified by BI with the instruction specified by I.
107 /// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The
108 /// original instruction is deleted and BI is updated to point to the new
109 /// instruction.
110 void ReplaceInstWithInst(BasicBlock::InstListType &BIL,
111                          BasicBlock::iterator &BI, Instruction *I);
112 
113 /// Replace the instruction specified by From with the instruction specified by
114 /// To. Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc.
115 void ReplaceInstWithInst(Instruction *From, Instruction *To);
116 
117 /// Option class for critical edge splitting.
118 ///
119 /// This provides a builder interface for overriding the default options used
120 /// during critical edge splitting.
121 struct CriticalEdgeSplittingOptions {
122   DominatorTree *DT;
123   PostDominatorTree *PDT;
124   LoopInfo *LI;
125   MemorySSAUpdater *MSSAU;
126   bool MergeIdenticalEdges = false;
127   bool KeepOneInputPHIs = false;
128   bool PreserveLCSSA = false;
129   bool IgnoreUnreachableDests = false;
130 
131   CriticalEdgeSplittingOptions(DominatorTree *DT = nullptr,
132                                LoopInfo *LI = nullptr,
133                                MemorySSAUpdater *MSSAU = nullptr,
134                                PostDominatorTree *PDT = nullptr)
DTCriticalEdgeSplittingOptions135       : DT(DT), PDT(PDT), LI(LI), MSSAU(MSSAU) {}
136 
setMergeIdenticalEdgesCriticalEdgeSplittingOptions137   CriticalEdgeSplittingOptions &setMergeIdenticalEdges() {
138     MergeIdenticalEdges = true;
139     return *this;
140   }
141 
setKeepOneInputPHIsCriticalEdgeSplittingOptions142   CriticalEdgeSplittingOptions &setKeepOneInputPHIs() {
143     KeepOneInputPHIs = true;
144     return *this;
145   }
146 
setPreserveLCSSACriticalEdgeSplittingOptions147   CriticalEdgeSplittingOptions &setPreserveLCSSA() {
148     PreserveLCSSA = true;
149     return *this;
150   }
151 
setIgnoreUnreachableDestsCriticalEdgeSplittingOptions152   CriticalEdgeSplittingOptions &setIgnoreUnreachableDests() {
153     IgnoreUnreachableDests = true;
154     return *this;
155   }
156 };
157 
158 /// If this edge is a critical edge, insert a new node to split the critical
159 /// edge. This will update the analyses passed in through the option struct.
160 /// This returns the new block if the edge was split, null otherwise.
161 ///
162 /// If MergeIdenticalEdges in the options struct is true (not the default),
163 /// *all* edges from TI to the specified successor will be merged into the same
164 /// critical edge block. This is most commonly interesting with switch
165 /// instructions, which may have many edges to any one destination.  This
166 /// ensures that all edges to that dest go to one block instead of each going
167 /// to a different block, but isn't the standard definition of a "critical
168 /// edge".
169 ///
170 /// It is invalid to call this function on a critical edge that starts at an
171 /// IndirectBrInst.  Splitting these edges will almost always create an invalid
172 /// program because the address of the new block won't be the one that is jumped
173 /// to.
174 BasicBlock *SplitCriticalEdge(Instruction *TI, unsigned SuccNum,
175                               const CriticalEdgeSplittingOptions &Options =
176                                   CriticalEdgeSplittingOptions());
177 
178 inline BasicBlock *
179 SplitCriticalEdge(BasicBlock *BB, succ_iterator SI,
180                   const CriticalEdgeSplittingOptions &Options =
181                       CriticalEdgeSplittingOptions()) {
182   return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(),
183                            Options);
184 }
185 
186 /// If the edge from *PI to BB is not critical, return false. Otherwise, split
187 /// all edges between the two blocks and return true. This updates all of the
188 /// same analyses as the other SplitCriticalEdge function. If P is specified, it
189 /// updates the analyses described above.
190 inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI,
191                               const CriticalEdgeSplittingOptions &Options =
192                                   CriticalEdgeSplittingOptions()) {
193   bool MadeChange = false;
194   Instruction *TI = (*PI)->getTerminator();
195   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
196     if (TI->getSuccessor(i) == Succ)
197       MadeChange |= !!SplitCriticalEdge(TI, i, Options);
198   return MadeChange;
199 }
200 
201 /// If an edge from Src to Dst is critical, split the edge and return true,
202 /// otherwise return false. This method requires that there be an edge between
203 /// the two blocks. It updates the analyses passed in the options struct
204 inline BasicBlock *
205 SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst,
206                   const CriticalEdgeSplittingOptions &Options =
207                       CriticalEdgeSplittingOptions()) {
208   Instruction *TI = Src->getTerminator();
209   unsigned i = 0;
210   while (true) {
211     assert(i != TI->getNumSuccessors() && "Edge doesn't exist!");
212     if (TI->getSuccessor(i) == Dst)
213       return SplitCriticalEdge(TI, i, Options);
214     ++i;
215   }
216 }
217 
218 /// Loop over all of the edges in the CFG, breaking critical edges as they are
219 /// found. Returns the number of broken edges.
220 unsigned SplitAllCriticalEdges(Function &F,
221                                const CriticalEdgeSplittingOptions &Options =
222                                    CriticalEdgeSplittingOptions());
223 
224 /// Split the edge connecting specified block.
225 BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To,
226                       DominatorTree *DT = nullptr, LoopInfo *LI = nullptr,
227                       MemorySSAUpdater *MSSAU = nullptr);
228 
229 /// Split the specified block at the specified instruction - everything before
230 /// SplitPt stays in Old and everything starting with SplitPt moves to a new
231 /// block. The two blocks are joined by an unconditional branch and the loop
232 /// info is updated.
233 BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt,
234                        DominatorTree *DT = nullptr, LoopInfo *LI = nullptr,
235                        MemorySSAUpdater *MSSAU = nullptr,
236                        const Twine &BBName = "");
237 
238 /// This method introduces at least one new basic block into the function and
239 /// moves some of the predecessors of BB to be predecessors of the new block.
240 /// The new predecessors are indicated by the Preds array. The new block is
241 /// given a suffix of 'Suffix'. Returns new basic block to which predecessors
242 /// from Preds are now pointing.
243 ///
244 /// If BB is a landingpad block then additional basicblock might be introduced.
245 /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more
246 /// details on this case.
247 ///
248 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
249 /// no other analyses. In particular, it does not preserve LoopSimplify
250 /// (because it's complicated to handle the case where one of the edges being
251 /// split is an exit of a loop with other exits).
252 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
253                                    const char *Suffix,
254                                    DominatorTree *DT = nullptr,
255                                    LoopInfo *LI = nullptr,
256                                    MemorySSAUpdater *MSSAU = nullptr,
257                                    bool PreserveLCSSA = false);
258 
259 /// This method transforms the landing pad, OrigBB, by introducing two new basic
260 /// blocks into the function. One of those new basic blocks gets the
261 /// predecessors listed in Preds. The other basic block gets the remaining
262 /// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both
263 /// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and
264 /// 'Suffix2', and are returned in the NewBBs vector.
265 ///
266 /// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
267 /// no other analyses. In particular, it does not preserve LoopSimplify
268 /// (because it's complicated to handle the case where one of the edges being
269 /// split is an exit of a loop with other exits).
270 void SplitLandingPadPredecessors(
271     BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix,
272     const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,
273     DominatorTree *DT = nullptr, LoopInfo *LI = nullptr,
274     MemorySSAUpdater *MSSAU = nullptr, bool PreserveLCSSA = false);
275 
276 /// This method duplicates the specified return instruction into a predecessor
277 /// which ends in an unconditional branch. If the return instruction returns a
278 /// value defined by a PHI, propagate the right value into the return. It
279 /// returns the new return instruction in the predecessor.
280 ReturnInst *FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,
281                                        BasicBlock *Pred,
282                                        DomTreeUpdater *DTU = nullptr);
283 
284 /// Split the containing block at the specified instruction - everything before
285 /// SplitBefore stays in the old basic block, and the rest of the instructions
286 /// in the BB are moved to a new block. The two blocks are connected by a
287 /// conditional branch (with value of Cmp being the condition).
288 /// Before:
289 ///   Head
290 ///   SplitBefore
291 ///   Tail
292 /// After:
293 ///   Head
294 ///   if (Cond)
295 ///     ThenBlock
296 ///   SplitBefore
297 ///   Tail
298 ///
299 /// If \p ThenBlock is not specified, a new block will be created for it.
300 /// If \p Unreachable is true, the newly created block will end with
301 /// UnreachableInst, otherwise it branches to Tail.
302 /// Returns the NewBasicBlock's terminator.
303 ///
304 /// Updates DT and LI if given.
305 Instruction *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore,
306                                        bool Unreachable,
307                                        MDNode *BranchWeights = nullptr,
308                                        DominatorTree *DT = nullptr,
309                                        LoopInfo *LI = nullptr,
310                                        BasicBlock *ThenBlock = nullptr);
311 
312 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen,
313 /// but also creates the ElseBlock.
314 /// Before:
315 ///   Head
316 ///   SplitBefore
317 ///   Tail
318 /// After:
319 ///   Head
320 ///   if (Cond)
321 ///     ThenBlock
322 ///   else
323 ///     ElseBlock
324 ///   SplitBefore
325 ///   Tail
326 void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
327                                    Instruction **ThenTerm,
328                                    Instruction **ElseTerm,
329                                    MDNode *BranchWeights = nullptr);
330 
331 /// Check whether BB is the merge point of a if-region.
332 /// If so, return the boolean condition that determines which entry into
333 /// BB will be taken.  Also, return by references the block that will be
334 /// entered from if the condition is true, and the block that will be
335 /// entered if the condition is false.
336 ///
337 /// This does no checking to see if the true/false blocks have large or unsavory
338 /// instructions in them.
339 Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue,
340                       BasicBlock *&IfFalse);
341 
342 // Split critical edges where the source of the edge is an indirectbr
343 // instruction. This isn't always possible, but we can handle some easy cases.
344 // This is useful because MI is unable to split such critical edges,
345 // which means it will not be able to sink instructions along those edges.
346 // This is especially painful for indirect branches with many successors, where
347 // we end up having to prepare all outgoing values in the origin block.
348 //
349 // Our normal algorithm for splitting critical edges requires us to update
350 // the outgoing edges of the edge origin block, but for an indirectbr this
351 // is hard, since it would require finding and updating the block addresses
352 // the indirect branch uses. But if a block only has a single indirectbr
353 // predecessor, with the others being regular branches, we can do it in a
354 // different way.
355 // Say we have A -> D, B -> D, I -> D where only I -> D is an indirectbr.
356 // We can split D into D0 and D1, where D0 contains only the PHIs from D,
357 // and D1 is the D block body. We can then duplicate D0 as D0A and D0B, and
358 // create the following structure:
359 // A -> D0A, B -> D0A, I -> D0B, D0A -> D1, D0B -> D1
360 // If BPI and BFI aren't non-null, BPI/BFI will be updated accordingly.
361 bool SplitIndirectBrCriticalEdges(Function &F,
362                                   BranchProbabilityInfo *BPI = nullptr,
363                                   BlockFrequencyInfo *BFI = nullptr);
364 
365 } // end namespace llvm
366 
367 #endif // LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
368