1 //===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements dead code elimination and basic block merging, along
11 // with a collection of other peephole control flow optimizations. For example:
13 // * Removes basic blocks with no predecessors.
14 // * Merges a basic block into its predecessor if there is only one and the
15 // predecessor only has one successor.
16 // * Eliminates PHI nodes for basic blocks with a single predecessor.
17 // * Eliminates a basic block that only contains an unconditional branch.
18 // * Changes invoke instructions to nounwind functions to be calls.
19 // * Change things like "if (x) if (y)" into "if (x&y)".
22 //===----------------------------------------------------------------------===//
24 #define DEBUG_TYPE "simplifycfg"
25 #include "llvm/Transforms/Scalar.h"
26 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/ADT/SmallVector.h"
28 #include "llvm/ADT/Statistic.h"
29 #include "llvm/Analysis/TargetTransformInfo.h"
30 #include "llvm/IR/Attributes.h"
31 #include "llvm/IR/CFG.h"
32 #include "llvm/IR/Constants.h"
33 #include "llvm/IR/DataLayout.h"
34 #include "llvm/IR/Instructions.h"
35 #include "llvm/IR/IntrinsicInst.h"
36 #include "llvm/IR/Module.h"
37 #include "llvm/Pass.h"
38 #include "llvm/Transforms/Utils/Local.h"
41 STATISTIC(NumSimpl, "Number of blocks simplified");
44 struct CFGSimplifyPass : public FunctionPass {
45 static char ID; // Pass identification, replacement for typeid
46 CFGSimplifyPass() : FunctionPass(ID) {
47 initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
49 bool runOnFunction(Function &F) override;
51 void getAnalysisUsage(AnalysisUsage &AU) const override {
52 AU.addRequired<TargetTransformInfo>();
57 char CFGSimplifyPass::ID = 0;
58 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
60 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
61 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
64 // Public interface to the CFGSimplification pass
65 FunctionPass *llvm::createCFGSimplificationPass() {
66 return new CFGSimplifyPass();
69 /// mergeEmptyReturnBlocks - If we have more than one empty (other than phi
70 /// node) return blocks, merge them together to promote recursive block merging.
71 static bool mergeEmptyReturnBlocks(Function &F) {
74 BasicBlock *RetBlock = 0;
76 // Scan all the blocks in the function, looking for empty return blocks.
77 for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
78 BasicBlock &BB = *BBI++;
80 // Only look at return blocks.
81 ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator());
82 if (Ret == 0) continue;
84 // Only look at the block if it is empty or the only other thing in it is a
85 // single PHI node that is the operand to the return.
86 if (Ret != &BB.front()) {
87 // Check for something else in the block.
88 BasicBlock::iterator I = Ret;
90 // Skip over debug info.
91 while (isa<DbgInfoIntrinsic>(I) && I != BB.begin())
93 if (!isa<DbgInfoIntrinsic>(I) &&
94 (!isa<PHINode>(I) || I != BB.begin() ||
95 Ret->getNumOperands() == 0 ||
96 Ret->getOperand(0) != I))
100 // If this is the first returning block, remember it and keep going.
106 // Otherwise, we found a duplicate return block. Merge the two.
109 // Case when there is no input to the return or when the returned values
110 // agree is trivial. Note that they can't agree if there are phis in the
112 if (Ret->getNumOperands() == 0 ||
113 Ret->getOperand(0) ==
114 cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
115 BB.replaceAllUsesWith(RetBlock);
116 BB.eraseFromParent();
120 // If the canonical return block has no PHI node, create one now.
121 PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
122 if (RetBlockPHI == 0) {
123 Value *InVal = cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0);
124 pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock);
125 RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(),
126 std::distance(PB, PE), "merge",
129 for (pred_iterator PI = PB; PI != PE; ++PI)
130 RetBlockPHI->addIncoming(InVal, *PI);
131 RetBlock->getTerminator()->setOperand(0, RetBlockPHI);
134 // Turn BB into a block that just unconditionally branches to the return
135 // block. This handles the case when the two return blocks have a common
136 // predecessor but that return different things.
137 RetBlockPHI->addIncoming(Ret->getOperand(0), &BB);
138 BB.getTerminator()->eraseFromParent();
139 BranchInst::Create(RetBlock, &BB);
145 /// iterativelySimplifyCFG - Call SimplifyCFG on all the blocks in the function,
146 /// iterating until no more changes are made.
147 static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
148 const DataLayout *DL) {
149 bool Changed = false;
150 bool LocalChange = true;
151 while (LocalChange) {
154 // Loop over all of the basic blocks and remove them if they are unneeded...
156 for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
157 if (SimplifyCFG(BBIt++, TTI, DL)) {
162 Changed |= LocalChange;
167 // It is possible that we may require multiple passes over the code to fully
170 bool CFGSimplifyPass::runOnFunction(Function &F) {
171 if (skipOptnoneFunction(F))
174 const TargetTransformInfo &TTI = getAnalysis<TargetTransformInfo>();
175 DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
176 const DataLayout *DL = DLP ? &DLP->getDataLayout() : 0;
177 bool EverChanged = removeUnreachableBlocks(F);
178 EverChanged |= mergeEmptyReturnBlocks(F);
179 EverChanged |= iterativelySimplifyCFG(F, TTI, DL);
181 // If neither pass changed anything, we're done.
182 if (!EverChanged) return false;
184 // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens,
185 // removeUnreachableBlocks is needed to nuke them, which means we should
186 // iterate between the two optimizations. We structure the code like this to
187 // avoid reruning iterativelySimplifyCFG if the second pass of
188 // removeUnreachableBlocks doesn't do anything.
189 if (!removeUnreachableBlocks(F))
193 EverChanged = iterativelySimplifyCFG(F, TTI, DL);
194 EverChanged |= removeUnreachableBlocks(F);
195 } while (EverChanged);