SimplifyCFGPass.cpp revision 263508
1//===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===// 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 file implements dead code elimination and basic block merging, along 11// with a collection of other peephole control flow optimizations. For example: 12// 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)". 20// * etc.. 21// 22//===----------------------------------------------------------------------===// 23 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/Constants.h" 32#include "llvm/IR/DataLayout.h" 33#include "llvm/IR/Instructions.h" 34#include "llvm/IR/IntrinsicInst.h" 35#include "llvm/IR/Module.h" 36#include "llvm/Pass.h" 37#include "llvm/Support/CFG.h" 38#include "llvm/Transforms/Utils/Local.h" 39using namespace llvm; 40 41STATISTIC(NumSimpl, "Number of blocks simplified"); 42 43namespace { 44struct CFGSimplifyPass : public FunctionPass { 45 static char ID; // Pass identification, replacement for typeid 46 CFGSimplifyPass() : FunctionPass(ID) { 47 initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry()); 48 } 49 virtual bool runOnFunction(Function &F); 50 51 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 52 AU.addRequired<TargetTransformInfo>(); 53 } 54}; 55} 56 57char CFGSimplifyPass::ID = 0; 58INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, 59 false) 60INITIALIZE_AG_DEPENDENCY(TargetTransformInfo) 61INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, 62 false) 63 64// Public interface to the CFGSimplification pass 65FunctionPass *llvm::createCFGSimplificationPass() { 66 return new CFGSimplifyPass(); 67} 68 69/// mergeEmptyReturnBlocks - If we have more than one empty (other than phi 70/// node) return blocks, merge them together to promote recursive block merging. 71static bool mergeEmptyReturnBlocks(Function &F) { 72 bool Changed = false; 73 74 BasicBlock *RetBlock = 0; 75 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++; 79 80 // Only look at return blocks. 81 ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator()); 82 if (Ret == 0) continue; 83 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; 89 --I; 90 // Skip over debug info. 91 while (isa<DbgInfoIntrinsic>(I) && I != BB.begin()) 92 --I; 93 if (!isa<DbgInfoIntrinsic>(I) && 94 (!isa<PHINode>(I) || I != BB.begin() || 95 Ret->getNumOperands() == 0 || 96 Ret->getOperand(0) != I)) 97 continue; 98 } 99 100 // If this is the first returning block, remember it and keep going. 101 if (RetBlock == 0) { 102 RetBlock = &BB; 103 continue; 104 } 105 106 // Otherwise, we found a duplicate return block. Merge the two. 107 Changed = true; 108 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 111 // blocks. 112 if (Ret->getNumOperands() == 0 || 113 Ret->getOperand(0) == 114 cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) { 115 BB.replaceAllUsesWith(RetBlock); 116 BB.eraseFromParent(); 117 continue; 118 } 119 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", 127 &RetBlock->front()); 128 129 for (pred_iterator PI = PB; PI != PE; ++PI) 130 RetBlockPHI->addIncoming(InVal, *PI); 131 RetBlock->getTerminator()->setOperand(0, RetBlockPHI); 132 } 133 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); 140 } 141 142 return Changed; 143} 144 145/// iterativelySimplifyCFG - Call SimplifyCFG on all the blocks in the function, 146/// iterating until no more changes are made. 147static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI, 148 const DataLayout *TD) { 149 bool Changed = false; 150 bool LocalChange = true; 151 while (LocalChange) { 152 LocalChange = false; 153 154 // Loop over all of the basic blocks and remove them if they are unneeded... 155 // 156 for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) { 157 if (SimplifyCFG(BBIt++, TTI, TD)) { 158 LocalChange = true; 159 ++NumSimpl; 160 } 161 } 162 Changed |= LocalChange; 163 } 164 return Changed; 165} 166 167// It is possible that we may require multiple passes over the code to fully 168// simplify the CFG. 169// 170bool CFGSimplifyPass::runOnFunction(Function &F) { 171 const TargetTransformInfo &TTI = getAnalysis<TargetTransformInfo>(); 172 const DataLayout *TD = getAnalysisIfAvailable<DataLayout>(); 173 bool EverChanged = removeUnreachableBlocks(F); 174 EverChanged |= mergeEmptyReturnBlocks(F); 175 EverChanged |= iterativelySimplifyCFG(F, TTI, TD); 176 177 // If neither pass changed anything, we're done. 178 if (!EverChanged) return false; 179 180 // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens, 181 // removeUnreachableBlocks is needed to nuke them, which means we should 182 // iterate between the two optimizations. We structure the code like this to 183 // avoid reruning iterativelySimplifyCFG if the second pass of 184 // removeUnreachableBlocks doesn't do anything. 185 if (!removeUnreachableBlocks(F)) 186 return true; 187 188 do { 189 EverChanged = iterativelySimplifyCFG(F, TTI, TD); 190 EverChanged |= removeUnreachableBlocks(F); 191 } while (EverChanged); 192 193 return true; 194} 195