1 | //===- SimplifyCFG.cpp ----------------------------------------------------===// |
2 | // |
3 | // |
4 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
5 | // See https://llvm.org/LICENSE.txt for license information. |
6 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
7 | // |
8 | //===----------------------------------------------------------------------===// |
9 | // |
10 | // This file implements the control flow graph (CFG) simplifications |
11 | // presented as part of the 'Getting Started With LLVM: Basics' tutorial at the |
12 | // US LLVM Developers Meeting 2019. It also contains additional material. |
13 | // |
14 | // The current file contains three different CFG simplifications. There are |
15 | // multiple versions of each implementation (e.g. _v1 and _v2), which implement |
16 | // additional functionality (e.g. preserving analysis like the DominatorTree) or |
17 | // use additional utilities to simplify the code (e.g. LLVM's PatternMatch.h). |
18 | // The available simplifications are: |
19 | // 1. Trivially Dead block Removal (removeDeadBlocks_v[1,2]). |
20 | // This simplifications removes all blocks without predecessors in the CFG |
21 | // from a function. |
22 | // 2. Conditional Branch Elimination (eliminateCondBranches_v[1,2,3]) |
23 | // This simplification replaces conditional branches with constant integer |
24 | // conditions with unconditional branches. |
25 | // 3. Single Predecessor Block Merging (mergeIntoSinglePredecessor_v[1,2]) |
26 | // This simplification merges blocks with a single predecessor into the |
27 | // predecessor, if that block has a single successor. |
28 | // |
29 | // TODOs |
30 | // * Preserve LoopInfo. |
31 | // * Add fixed point iteration to delete all dead blocks |
32 | // * Add implementation using reachability to discover dead blocks. |
33 | //===----------------------------------------------------------------------===// |
34 | |
35 | #include "llvm/Analysis/DomTreeUpdater.h" |
36 | #include "llvm/IR/Dominators.h" |
37 | #include "llvm/IR/Function.h" |
38 | #include "llvm/IR/PassManager.h" |
39 | #include "llvm/IR/PatternMatch.h" |
40 | #include "llvm/Passes/PassBuilder.h" |
41 | #include "llvm/Passes/PassPlugin.h" |
42 | #include "llvm/Support/CommandLine.h" |
43 | |
44 | using namespace llvm; |
45 | using namespace PatternMatch; |
46 | |
47 | enum TutorialVersion { V1, V2, V3 }; |
48 | static cl::opt<TutorialVersion> |
49 | Version("tut-simplifycfg-version" , cl::desc("Select tutorial version" ), |
50 | cl::Hidden, cl::ValueOptional, cl::init(Val: V1), |
51 | cl::values(clEnumValN(V1, "v1" , "version 1" ), |
52 | clEnumValN(V2, "v2" , "version 2" ), |
53 | clEnumValN(V3, "v3" , "version 3" ), |
54 | // Sentinel value for unspecified option. |
55 | clEnumValN(V3, "" , "" ))); |
56 | |
57 | #define DEBUG_TYPE "tut-simplifycfg" |
58 | |
59 | // Remove trivially dead blocks. First version, not preserving the |
60 | // DominatorTree. |
61 | static bool removeDeadBlocks_v1(Function &F) { |
62 | bool Changed = false; |
63 | |
64 | // Remove trivially dead blocks. |
65 | for (BasicBlock &BB : make_early_inc_range(Range&: F)) { |
66 | // Skip blocks we know to not be trivially dead. We know a block is |
67 | // guaranteed to be dead, iff it is neither the entry block nor |
68 | // has any predecessors. |
69 | if (&F.getEntryBlock() == &BB || !pred_empty(BB: &BB)) |
70 | continue; |
71 | |
72 | // Notify successors of BB that BB is going to be removed. This removes |
73 | // incoming values from BB from PHIs in the successors. Note that this will |
74 | // not actually remove BB from the predecessor lists of its successors. |
75 | for (BasicBlock *Succ : successors(BB: &BB)) |
76 | Succ->removePredecessor(Pred: &BB); |
77 | // TODO: Find a better place to put such small variations. |
78 | // Alternatively, we can update the PHI nodes manually: |
79 | // for (PHINode &PN : make_early_inc_range(Succ->phis())) |
80 | // PN.removeIncomingValue(&BB); |
81 | |
82 | // Replace all instructions in BB with a poison constant. The block is |
83 | // unreachable, so the results of the instructions should never get used. |
84 | while (!BB.empty()) { |
85 | Instruction &I = BB.back(); |
86 | I.replaceAllUsesWith(V: PoisonValue::get(T: I.getType())); |
87 | I.eraseFromParent(); |
88 | } |
89 | |
90 | // Finally remove the basic block. |
91 | BB.eraseFromParent(); |
92 | Changed = true; |
93 | } |
94 | |
95 | return Changed; |
96 | } |
97 | |
98 | // Remove trivially dead blocks. This is the second version and preserves the |
99 | // dominator tree. |
100 | static bool removeDeadBlocks_v2(Function &F, DominatorTree &DT) { |
101 | bool Changed = false; |
102 | DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); |
103 | SmallVector<DominatorTree::UpdateType, 8> DTUpdates; |
104 | |
105 | // Remove trivially dead blocks. |
106 | for (BasicBlock &BB : make_early_inc_range(Range&: F)) { |
107 | // Skip blocks we know to not be trivially dead. We know a block is |
108 | // guaranteed to be dead, iff it is neither the entry block nor |
109 | // has any predecessors. |
110 | if (&F.getEntryBlock() == &BB || !pred_empty(BB: &BB)) |
111 | continue; |
112 | |
113 | // Notify successors of BB that BB is going to be removed. This removes |
114 | // incoming values from BB from PHIs in the successors. Note that this will |
115 | // not actually remove BB from the predecessor lists of its successors. |
116 | for (BasicBlock *Succ : successors(BB: &BB)) { |
117 | Succ->removePredecessor(Pred: &BB); |
118 | |
119 | // Collect updates that need to be applied to the dominator tree. |
120 | DTUpdates.push_back(Elt: {DominatorTree::Delete, &BB, Succ}); |
121 | } |
122 | |
123 | // Remove BB via the DomTreeUpdater. DomTreeUpdater::deleteBB conveniently |
124 | // removes the instructions in BB as well. |
125 | DTU.deleteBB(DelBB: &BB); |
126 | Changed = true; |
127 | } |
128 | |
129 | // Apply updates permissively, to remove duplicates. |
130 | DTU.applyUpdatesPermissive(Updates: DTUpdates); |
131 | |
132 | return Changed; |
133 | } |
134 | |
135 | // Eliminate branches with constant conditionals. This is the first version, |
136 | // which *does not* preserve the dominator tree. |
137 | static bool eliminateCondBranches_v1(Function &F) { |
138 | bool Changed = false; |
139 | |
140 | // Eliminate branches with constant conditionals. |
141 | for (BasicBlock &BB : F) { |
142 | // Skip blocks without conditional branches as terminators. |
143 | BranchInst *BI = dyn_cast<BranchInst>(Val: BB.getTerminator()); |
144 | if (!BI || !BI->isConditional()) |
145 | continue; |
146 | |
147 | // Skip blocks with conditional branches without ConstantInt conditions. |
148 | ConstantInt *CI = dyn_cast<ConstantInt>(Val: BI->getCondition()); |
149 | if (!CI) |
150 | continue; |
151 | |
152 | // We use the branch condition (CI), to select the successor we remove: |
153 | // if CI == 1 (true), we remove the second successor, otherwise the first. |
154 | BasicBlock *RemovedSucc = BI->getSuccessor(i: CI->isOne()); |
155 | // Tell RemovedSucc we will remove BB from its predecessors. |
156 | RemovedSucc->removePredecessor(Pred: &BB); |
157 | |
158 | // Replace the conditional branch with an unconditional one, by creating |
159 | // a new unconditional branch to the selected successor and removing the |
160 | // conditional one. |
161 | BranchInst::Create(IfTrue: BI->getSuccessor(i: CI->isZero()), InsertBefore: BI); |
162 | BI->eraseFromParent(); |
163 | Changed = true; |
164 | } |
165 | |
166 | return Changed; |
167 | } |
168 | |
169 | // Eliminate branches with constant conditionals. This is the second |
170 | // version, which *does* preserve the dominator tree. |
171 | static bool eliminateCondBranches_v2(Function &F, DominatorTree &DT) { |
172 | bool Changed = false; |
173 | |
174 | DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); |
175 | SmallVector<DominatorTree::UpdateType, 8> DTUpdates; |
176 | // Eliminate branches with constant conditionals. |
177 | for (BasicBlock &BB : F) { |
178 | // Skip blocks without conditional branches as terminators. |
179 | BranchInst *BI = dyn_cast<BranchInst>(Val: BB.getTerminator()); |
180 | if (!BI || !BI->isConditional()) |
181 | continue; |
182 | |
183 | // Skip blocks with conditional branches without ConstantInt conditions. |
184 | ConstantInt *CI = dyn_cast<ConstantInt>(Val: BI->getCondition()); |
185 | if (!CI) |
186 | continue; |
187 | |
188 | // We use the branch condition (CI), to select the successor we remove: |
189 | // if CI == 1 (true), we remove the second successor, otherwise the first. |
190 | BasicBlock *RemovedSucc = BI->getSuccessor(i: CI->isOne()); |
191 | // Tell RemovedSucc we will remove BB from its predecessors. |
192 | RemovedSucc->removePredecessor(Pred: &BB); |
193 | |
194 | // Replace the conditional branch with an unconditional one, by creating |
195 | // a new unconditional branch to the selected successor and removing the |
196 | // conditional one. |
197 | BranchInst *NewBranch = |
198 | BranchInst::Create(IfTrue: BI->getSuccessor(i: CI->isZero()), InsertBefore: BI); |
199 | BI->eraseFromParent(); |
200 | |
201 | // Delete the edge between BB and RemovedSucc in the DominatorTree, iff |
202 | // the conditional branch did not use RemovedSucc as both the true and false |
203 | // branches. |
204 | if (NewBranch->getSuccessor(i: 0) != RemovedSucc) |
205 | DTUpdates.push_back(Elt: {DominatorTree::Delete, &BB, RemovedSucc}); |
206 | Changed = true; |
207 | } |
208 | |
209 | // Apply updates permissively, to remove duplicates. |
210 | DTU.applyUpdatesPermissive(Updates: DTUpdates); |
211 | |
212 | return Changed; |
213 | } |
214 | |
215 | // Eliminate branches with constant conditionals. This is the third |
216 | // version, which uses PatternMatch.h. |
217 | static bool eliminateCondBranches_v3(Function &F, DominatorTree &DT) { |
218 | bool Changed = false; |
219 | DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); |
220 | SmallVector<DominatorTree::UpdateType, 8> DTUpdates; |
221 | |
222 | // Eliminate branches with constant conditionals. |
223 | for (BasicBlock &BB : F) { |
224 | ConstantInt *CI = nullptr; |
225 | BasicBlock *TakenSucc, *RemovedSucc; |
226 | // Check if the terminator is a conditional branch, with constant integer |
227 | // condition and also capture the successor blocks as TakenSucc and |
228 | // RemovedSucc. |
229 | if (!match(V: BB.getTerminator(), |
230 | P: m_Br(C: m_ConstantInt(CI), T: m_BasicBlock(V&: TakenSucc), |
231 | F: m_BasicBlock(V&: RemovedSucc)))) |
232 | continue; |
233 | |
234 | // If the condition is false, swap TakenSucc and RemovedSucc. |
235 | if (CI->isZero()) |
236 | std::swap(a&: TakenSucc, b&: RemovedSucc); |
237 | |
238 | // Tell RemovedSucc we will remove BB from its predecessors. |
239 | RemovedSucc->removePredecessor(Pred: &BB); |
240 | |
241 | // Replace the conditional branch with an unconditional one, by creating |
242 | // a new unconditional branch to the selected successor and removing the |
243 | // conditional one. |
244 | |
245 | BranchInst *NewBranch = BranchInst::Create(IfTrue: TakenSucc, InsertBefore: BB.getTerminator()); |
246 | BB.getTerminator()->eraseFromParent(); |
247 | |
248 | // Delete the edge between BB and RemovedSucc in the DominatorTree, iff |
249 | // the conditional branch did not use RemovedSucc as both the true and false |
250 | // branches. |
251 | if (NewBranch->getSuccessor(i: 0) != RemovedSucc) |
252 | DTUpdates.push_back(Elt: {DominatorTree::Delete, &BB, RemovedSucc}); |
253 | Changed = true; |
254 | } |
255 | |
256 | // Apply updates permissively, to remove duplicates. |
257 | DTU.applyUpdatesPermissive(Updates: DTUpdates); |
258 | return Changed; |
259 | } |
260 | |
261 | // Merge basic blocks into their single predecessor, if their predecessor has a |
262 | // single successor. This is the first version and does not preserve the |
263 | // DominatorTree. |
264 | static bool mergeIntoSinglePredecessor_v1(Function &F) { |
265 | bool Changed = false; |
266 | |
267 | // Merge blocks with single predecessors. |
268 | for (BasicBlock &BB : make_early_inc_range(Range&: F)) { |
269 | BasicBlock *Pred = BB.getSinglePredecessor(); |
270 | // Make sure BB has a single predecessor Pred and BB is the single |
271 | // successor of Pred. |
272 | if (!Pred || Pred->getSingleSuccessor() != &BB) |
273 | continue; |
274 | |
275 | // Do not try to merge self loops. That can happen in dead blocks. |
276 | if (Pred == &BB) |
277 | continue; |
278 | |
279 | // Need to replace it before nuking the branch. |
280 | BB.replaceAllUsesWith(V: Pred); |
281 | // PHI nodes in BB can only have a single incoming value. Remove them. |
282 | for (PHINode &PN : make_early_inc_range(Range: BB.phis())) { |
283 | PN.replaceAllUsesWith(V: PN.getIncomingValue(i: 0)); |
284 | PN.eraseFromParent(); |
285 | } |
286 | // Move all instructions from BB to Pred. |
287 | for (Instruction &I : make_early_inc_range(Range&: BB)) |
288 | I.moveBefore(MovePos: Pred->getTerminator()); |
289 | |
290 | // Remove the Pred's terminator (which jumped to BB). BB's terminator |
291 | // will become Pred's terminator. |
292 | Pred->getTerminator()->eraseFromParent(); |
293 | BB.eraseFromParent(); |
294 | |
295 | Changed = true; |
296 | } |
297 | |
298 | return Changed; |
299 | } |
300 | |
301 | // Merge basic blocks into their single predecessor, if their predecessor has a |
302 | // single successor. This is the second version and does preserve the |
303 | // DominatorTree. |
304 | static bool mergeIntoSinglePredecessor_v2(Function &F, DominatorTree &DT) { |
305 | bool Changed = false; |
306 | DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); |
307 | SmallVector<DominatorTree::UpdateType, 8> DTUpdates; |
308 | |
309 | // Merge blocks with single predecessors. |
310 | for (BasicBlock &BB : make_early_inc_range(Range&: F)) { |
311 | BasicBlock *Pred = BB.getSinglePredecessor(); |
312 | // Make sure BB has a single predecessor Pred and BB is the single |
313 | // successor of Pred. |
314 | if (!Pred || Pred->getSingleSuccessor() != &BB) |
315 | continue; |
316 | |
317 | // Do not try to merge self loops. That can happen in dead blocks. |
318 | if (Pred == &BB) |
319 | continue; |
320 | |
321 | // Tell DTU about the changes to the CFG: All edges from BB to its |
322 | // successors get removed and we add edges between Pred and BB's successors. |
323 | for (BasicBlock *Succ : successors(BB: &BB)) { |
324 | DTUpdates.push_back(Elt: {DominatorTree::Delete, &BB, Succ}); |
325 | DTUpdates.push_back(Elt: {DominatorTree::Insert, Pred, Succ}); |
326 | } |
327 | // Also remove the edge between Pred and BB. |
328 | DTUpdates.push_back(Elt: {DominatorTree::Delete, Pred, &BB}); |
329 | |
330 | // Need to replace it before nuking the branch. |
331 | BB.replaceAllUsesWith(V: Pred); |
332 | // PHI nodes in BB can only have a single incoming value. Remove them. |
333 | for (PHINode &PN : make_early_inc_range(Range: BB.phis())) { |
334 | PN.replaceAllUsesWith(V: PN.getIncomingValue(i: 0)); |
335 | PN.eraseFromParent(); |
336 | } |
337 | // Move all instructions from BB to Pred. |
338 | for (Instruction &I : make_early_inc_range(Range&: BB)) |
339 | I.moveBefore(MovePos: Pred->getTerminator()); |
340 | |
341 | // Remove the Pred's terminator (which jumped to BB). BB's terminator |
342 | // will become Pred's terminator. |
343 | Pred->getTerminator()->eraseFromParent(); |
344 | DTU.deleteBB(DelBB: &BB); |
345 | |
346 | Changed = true; |
347 | } |
348 | |
349 | // Apply updates permissively, to remove duplicates. |
350 | DTU.applyUpdatesPermissive(Updates: DTUpdates); |
351 | return Changed; |
352 | } |
353 | |
354 | static bool doSimplify_v1(Function &F) { |
355 | return (int)eliminateCondBranches_v1(F) | mergeIntoSinglePredecessor_v1(F) | |
356 | removeDeadBlocks_v1(F); |
357 | } |
358 | |
359 | static bool doSimplify_v2(Function &F, DominatorTree &DT) { |
360 | return (int)eliminateCondBranches_v2(F, DT) | |
361 | mergeIntoSinglePredecessor_v2(F, DT) | removeDeadBlocks_v2(F, DT); |
362 | } |
363 | |
364 | static bool doSimplify_v3(Function &F, DominatorTree &DT) { |
365 | return (int)eliminateCondBranches_v3(F, DT) | |
366 | mergeIntoSinglePredecessor_v2(F, DT) | removeDeadBlocks_v2(F, DT); |
367 | } |
368 | |
369 | namespace { |
370 | struct SimplifyCFGPass : public PassInfoMixin<SimplifyCFGPass> { |
371 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM) { |
372 | switch (Version) { |
373 | case V1: |
374 | doSimplify_v1(F); |
375 | break; |
376 | case V2: { |
377 | DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(IR&: F); |
378 | doSimplify_v2(F, DT); |
379 | break; |
380 | } |
381 | case V3: { |
382 | DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(IR&: F); |
383 | doSimplify_v3(F, DT); |
384 | break; |
385 | } |
386 | } |
387 | |
388 | return PreservedAnalyses::none(); |
389 | } |
390 | }; |
391 | } // namespace |
392 | |
393 | /* New PM Registration */ |
394 | llvm::PassPluginLibraryInfo getExampleIRTransformsPluginInfo() { |
395 | return {LLVM_PLUGIN_API_VERSION, .PluginName: "SimplifyCFG" , LLVM_VERSION_STRING, |
396 | .RegisterPassBuilderCallbacks: [](PassBuilder &PB) { |
397 | PB.registerPipelineParsingCallback( |
398 | C: [](StringRef Name, llvm::FunctionPassManager &PM, |
399 | ArrayRef<llvm::PassBuilder::PipelineElement>) { |
400 | if (Name == "tut-simplifycfg" ) { |
401 | PM.addPass(Pass: SimplifyCFGPass()); |
402 | return true; |
403 | } |
404 | return false; |
405 | }); |
406 | }}; |
407 | } |
408 | |
409 | #ifndef LLVM_SIMPLIFYCFG_LINK_INTO_TOOLS |
410 | extern "C" LLVM_ATTRIBUTE_WEAK ::llvm::PassPluginLibraryInfo |
411 | llvmGetPassPluginInfo() { |
412 | return getExampleIRTransformsPluginInfo(); |
413 | } |
414 | #endif |
415 | |