LLVM  14.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"
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 
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 
46 namespace {
47 
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 
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.
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 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::initializeUnifyFunctionExitNodesLegacyPassPass
void initializeUnifyFunctionExitNodesLegacyPassPass(PassRegistry &)
llvm::Function
Definition: Function.h:62
llvm::UnifyFunctionExitNodesLegacyPass::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: UnifyFunctionExitNodes.cpp:116
UnifyFunctionExitNodes.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
INITIALIZE_PASS
INITIALIZE_PASS(UnifyFunctionExitNodesLegacyPass, "mergereturn", "Unify function exit nodes", false, false) Pass *llvm
Definition: UnifyFunctionExitNodes.cpp:31
llvm::UnifyFunctionExitNodesLegacyPass::UnifyFunctionExitNodesLegacyPass
UnifyFunctionExitNodesLegacyPass()
Definition: UnifyFunctionExitNodes.cpp:25
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
Utils.h
llvm::UnifyFunctionExitNodesLegacyPass
Definition: UnifyFunctionExitNodes.h:24
Type.h
BasicBlock.h
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2783
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3124
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::AnalysisUsage::addPreservedID
AnalysisUsage & addPreservedID(const void *ID)
Definition: PassAnalysisSupport.h:88
llvm::UnifyFunctionExitNodesPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: UnifyFunctionExitNodes.cpp:123
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
llvm::LowerSwitchID
char & LowerSwitchID
Definition: LowerSwitch.cpp:570
llvm::createUnifyFunctionExitNodesPass
Pass * createUnifyFunctionExitNodesPass()
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::PHINode::Create
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...
Definition: Instructions.h:2675
Function.h
llvm::ReturnInst::Create
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3013
llvm::BreakCriticalEdgesID
char & BreakCriticalEdgesID
llvm::BasicBlock::getInstList
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:363
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
Instructions.h
llvm::UnifyFunctionExitNodesLegacyPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: UnifyFunctionExitNodes.cpp:38
llvm::PHINode
Definition: Instructions.h:2633
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::UnreachableInst
This function has undefined behavior.
Definition: Instructions.h:4713
InitializePasses.h
llvm::UnifyFunctionExitNodesLegacyPass::ID
static char ID
Definition: UnifyFunctionExitNodes.h:26
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37