1 //===- UnifyFunctionExitNodes.cpp - Make all functions have a single exit -===//
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 pass is used to ensure that functions have at most one return and one
10 // unreachable instruction in them.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
15 #include "llvm/IR/BasicBlock.h"
16 #include "llvm/IR/Function.h"
17 #include "llvm/IR/Instructions.h"
18 #include "llvm/IR/Type.h"
19 #include "llvm/InitializePasses.h"
20 #include "llvm/Transforms/Utils.h"
21 using namespace llvm;
22
23 char UnifyFunctionExitNodesLegacyPass::ID = 0;
24
UnifyFunctionExitNodesLegacyPass()25 UnifyFunctionExitNodesLegacyPass::UnifyFunctionExitNodesLegacyPass()
26 : FunctionPass(ID) {
27 initializeUnifyFunctionExitNodesLegacyPassPass(
28 *PassRegistry::getPassRegistry());
29 }
30
31 INITIALIZE_PASS(UnifyFunctionExitNodesLegacyPass, "mergereturn",
32 "Unify function exit nodes", false, false)
33
createUnifyFunctionExitNodesPass()34 Pass *llvm::createUnifyFunctionExitNodesPass() {
35 return new UnifyFunctionExitNodesLegacyPass();
36 }
37
getAnalysisUsage(AnalysisUsage & AU) const38 void UnifyFunctionExitNodesLegacyPass::getAnalysisUsage(
39 AnalysisUsage &AU) const {
40 // We preserve the non-critical-edgeness property
41 AU.addPreservedID(BreakCriticalEdgesID);
42 // This is a cluster of orthogonal Transforms
43 AU.addPreservedID(LowerSwitchID);
44 }
45
46 namespace {
47
unifyUnreachableBlocks(Function & F)48 bool unifyUnreachableBlocks(Function &F) {
49 std::vector<BasicBlock *> UnreachableBlocks;
50
51 for (BasicBlock &I : F)
52 if (isa<UnreachableInst>(I.getTerminator()))
53 UnreachableBlocks.push_back(&I);
54
55 if (UnreachableBlocks.size() <= 1)
56 return false;
57
58 BasicBlock *UnreachableBlock =
59 BasicBlock::Create(F.getContext(), "UnifiedUnreachableBlock", &F);
60 new UnreachableInst(F.getContext(), UnreachableBlock);
61
62 for (BasicBlock *BB : UnreachableBlocks) {
63 BB->getInstList().pop_back(); // Remove the unreachable inst.
64 BranchInst::Create(UnreachableBlock, BB);
65 }
66
67 return true;
68 }
69
unifyReturnBlocks(Function & F)70 bool unifyReturnBlocks(Function &F) {
71 std::vector<BasicBlock *> ReturningBlocks;
72
73 for (BasicBlock &I : F)
74 if (isa<ReturnInst>(I.getTerminator()))
75 ReturningBlocks.push_back(&I);
76
77 if (ReturningBlocks.size() <= 1)
78 return false;
79
80 // Insert a new basic block into the function, add PHI nodes (if the function
81 // returns values), and convert all of the return instructions into
82 // unconditional branches.
83 BasicBlock *NewRetBlock = BasicBlock::Create(F.getContext(),
84 "UnifiedReturnBlock", &F);
85
86 PHINode *PN = nullptr;
87 if (F.getReturnType()->isVoidTy()) {
88 ReturnInst::Create(F.getContext(), nullptr, NewRetBlock);
89 } else {
90 // If the function doesn't return void... add a PHI node to the block...
91 PN = PHINode::Create(F.getReturnType(), ReturningBlocks.size(),
92 "UnifiedRetVal");
93 NewRetBlock->getInstList().push_back(PN);
94 ReturnInst::Create(F.getContext(), PN, NewRetBlock);
95 }
96
97 // Loop over all of the blocks, replacing the return instruction with an
98 // unconditional branch.
99 for (BasicBlock *BB : ReturningBlocks) {
100 // Add an incoming element to the PHI node for every return instruction that
101 // is merging into this new block...
102 if (PN)
103 PN->addIncoming(BB->getTerminator()->getOperand(0), BB);
104
105 BB->getInstList().pop_back(); // Remove the return insn
106 BranchInst::Create(NewRetBlock, BB);
107 }
108
109 return true;
110 }
111 } // namespace
112
113 // Unify all exit nodes of the CFG by creating a new BasicBlock, and converting
114 // all returns to unconditional branches to this new basic block. Also, unify
115 // all unreachable blocks.
runOnFunction(Function & F)116 bool UnifyFunctionExitNodesLegacyPass::runOnFunction(Function &F) {
117 bool Changed = false;
118 Changed |= unifyUnreachableBlocks(F);
119 Changed |= unifyReturnBlocks(F);
120 return Changed;
121 }
122
run(Function & F,FunctionAnalysisManager & AM)123 PreservedAnalyses UnifyFunctionExitNodesPass::run(Function &F,
124 FunctionAnalysisManager &AM) {
125 bool Changed = false;
126 Changed |= unifyUnreachableBlocks(F);
127 Changed |= unifyReturnBlocks(F);
128 return Changed ? PreservedAnalyses() : PreservedAnalyses::all();
129 }
130