LLVM 17.0.0git
UnifyFunctionExitNodes.cpp
Go to the documentation of this file.
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
15#include "llvm/IR/BasicBlock.h"
16#include "llvm/IR/Function.h"
18#include "llvm/IR/Type.h"
21using namespace llvm;
22
24
26 : FunctionPass(ID) {
29}
30
32 "Unify function exit nodes", false, false)
33
36}
37
39 AnalysisUsage &AU) const {
40 // We preserve the non-critical-edgeness property
42 // This is a cluster of orthogonal Transforms
44}
45
46namespace {
47
48bool 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->back().eraseFromParent(); // Remove the unreachable inst.
64 BranchInst::Create(UnreachableBlock, BB);
65 }
66
67 return true;
68}
69
70bool 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 PN->insertInto(NewRetBlock, NewRetBlock->end());
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->back().eraseFromParent(); // 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.
117 bool Changed = false;
118 Changed |= unifyUnreachableBlocks(F);
119 Changed |= unifyReturnBlocks(F);
120 return Changed;
121}
122
125 bool Changed = false;
126 Changed |= unifyUnreachableBlocks(F);
127 Changed |= unifyReturnBlocks(F);
128 return Changed ? PreservedAnalyses() : PreservedAnalyses::all();
129}
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
Represent the analysis usage information of a pass.
AnalysisUsage & addPreservedID(const void *ID)
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator end()
Definition: BasicBlock.h:316
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:105
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
SymbolTableList< Instruction >::iterator insertInto(BasicBlock *ParentBB, SymbolTableList< Instruction >::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Definition: Instruction.cpp:98
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, Instruction *InsertBefore=nullptr)
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
This function has undefined behavior.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Pass * createUnifyFunctionExitNodesPass()
void initializeUnifyFunctionExitNodesLegacyPassPass(PassRegistry &)
char & LowerSwitchID
char & BreakCriticalEdgesID