]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===- UnifyFunctionExitNodes.cpp - Make all functions have a single exit -===// |
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 | // This pass is used to ensure that functions have at most one return | |
11 | // instruction in them. Additionally, it keeps track of which node is the new | |
12 | // exit node of the CFG. If there are no exit nodes in the CFG, the getExitNode | |
13 | // method will return a null pointer. | |
14 | // | |
15 | //===----------------------------------------------------------------------===// | |
16 | ||
17 | #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" | |
223e47cc | 18 | #include "llvm/ADT/StringExtras.h" |
970d7e83 LB |
19 | #include "llvm/IR/BasicBlock.h" |
20 | #include "llvm/IR/Function.h" | |
21 | #include "llvm/IR/Instructions.h" | |
22 | #include "llvm/IR/Type.h" | |
23 | #include "llvm/Transforms/Scalar.h" | |
223e47cc LB |
24 | using namespace llvm; |
25 | ||
26 | char UnifyFunctionExitNodes::ID = 0; | |
27 | INITIALIZE_PASS(UnifyFunctionExitNodes, "mergereturn", | |
28 | "Unify function exit nodes", false, false) | |
29 | ||
30 | Pass *llvm::createUnifyFunctionExitNodesPass() { | |
31 | return new UnifyFunctionExitNodes(); | |
32 | } | |
33 | ||
34 | void UnifyFunctionExitNodes::getAnalysisUsage(AnalysisUsage &AU) const{ | |
35 | // We preserve the non-critical-edgeness property | |
36 | AU.addPreservedID(BreakCriticalEdgesID); | |
37 | // This is a cluster of orthogonal Transforms | |
223e47cc LB |
38 | AU.addPreservedID(LowerSwitchID); |
39 | } | |
40 | ||
41 | // UnifyAllExitNodes - Unify all exit nodes of the CFG by creating a new | |
42 | // BasicBlock, and converting all returns to unconditional branches to this | |
43 | // new basic block. The singular exit node is returned. | |
44 | // | |
45 | // If there are no return stmts in the Function, a null pointer is returned. | |
46 | // | |
47 | bool UnifyFunctionExitNodes::runOnFunction(Function &F) { | |
48 | // Loop over all of the blocks in a function, tracking all of the blocks that | |
49 | // return. | |
50 | // | |
51 | std::vector<BasicBlock*> ReturningBlocks; | |
52 | std::vector<BasicBlock*> UnreachableBlocks; | |
53 | for(Function::iterator I = F.begin(), E = F.end(); I != E; ++I) | |
54 | if (isa<ReturnInst>(I->getTerminator())) | |
55 | ReturningBlocks.push_back(I); | |
56 | else if (isa<UnreachableInst>(I->getTerminator())) | |
57 | UnreachableBlocks.push_back(I); | |
58 | ||
59 | // Then unreachable blocks. | |
60 | if (UnreachableBlocks.empty()) { | |
1a4d82fc | 61 | UnreachableBlock = nullptr; |
223e47cc LB |
62 | } else if (UnreachableBlocks.size() == 1) { |
63 | UnreachableBlock = UnreachableBlocks.front(); | |
64 | } else { | |
65 | UnreachableBlock = BasicBlock::Create(F.getContext(), | |
66 | "UnifiedUnreachableBlock", &F); | |
67 | new UnreachableInst(F.getContext(), UnreachableBlock); | |
68 | ||
69 | for (std::vector<BasicBlock*>::iterator I = UnreachableBlocks.begin(), | |
70 | E = UnreachableBlocks.end(); I != E; ++I) { | |
71 | BasicBlock *BB = *I; | |
72 | BB->getInstList().pop_back(); // Remove the unreachable inst. | |
73 | BranchInst::Create(UnreachableBlock, BB); | |
74 | } | |
75 | } | |
76 | ||
77 | // Now handle return blocks. | |
78 | if (ReturningBlocks.empty()) { | |
1a4d82fc | 79 | ReturnBlock = nullptr; |
223e47cc LB |
80 | return false; // No blocks return |
81 | } else if (ReturningBlocks.size() == 1) { | |
82 | ReturnBlock = ReturningBlocks.front(); // Already has a single return block | |
83 | return false; | |
84 | } | |
85 | ||
86 | // Otherwise, we need to insert a new basic block into the function, add a PHI | |
87 | // nodes (if the function returns values), and convert all of the return | |
88 | // instructions into unconditional branches. | |
89 | // | |
90 | BasicBlock *NewRetBlock = BasicBlock::Create(F.getContext(), | |
91 | "UnifiedReturnBlock", &F); | |
92 | ||
1a4d82fc | 93 | PHINode *PN = nullptr; |
223e47cc | 94 | if (F.getReturnType()->isVoidTy()) { |
1a4d82fc | 95 | ReturnInst::Create(F.getContext(), nullptr, NewRetBlock); |
223e47cc LB |
96 | } else { |
97 | // If the function doesn't return void... add a PHI node to the block... | |
98 | PN = PHINode::Create(F.getReturnType(), ReturningBlocks.size(), | |
99 | "UnifiedRetVal"); | |
100 | NewRetBlock->getInstList().push_back(PN); | |
101 | ReturnInst::Create(F.getContext(), PN, NewRetBlock); | |
102 | } | |
103 | ||
104 | // Loop over all of the blocks, replacing the return instruction with an | |
105 | // unconditional branch. | |
106 | // | |
107 | for (std::vector<BasicBlock*>::iterator I = ReturningBlocks.begin(), | |
108 | E = ReturningBlocks.end(); I != E; ++I) { | |
109 | BasicBlock *BB = *I; | |
110 | ||
111 | // Add an incoming element to the PHI node for every return instruction that | |
112 | // is merging into this new block... | |
113 | if (PN) | |
114 | PN->addIncoming(BB->getTerminator()->getOperand(0), BB); | |
115 | ||
116 | BB->getInstList().pop_back(); // Remove the return insn | |
117 | BranchInst::Create(NewRetBlock, BB); | |
118 | } | |
119 | ReturnBlock = NewRetBlock; | |
120 | return true; | |
121 | } |