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
44using namespace llvm;
45using namespace PatternMatch;
46
47enum TutorialVersion { V1, V2, V3 };
48static 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.
61static 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.
100static 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.
137static 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.
171static 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.
217static 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.
264static 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.
304static 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
354static bool doSimplify_v1(Function &F) {
355 return (int)eliminateCondBranches_v1(F) | mergeIntoSinglePredecessor_v1(F) |
356 removeDeadBlocks_v1(F);
357}
358
359static 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
364static 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
369namespace {
370struct 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 */
394llvm::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
410extern "C" LLVM_ATTRIBUTE_WEAK ::llvm::PassPluginLibraryInfo
411llvmGetPassPluginInfo() {
412 return getExampleIRTransformsPluginInfo();
413}
414#endif
415

source code of llvm/examples/IRTransforms/SimplifyCFG.cpp