UnifyFunctionExitNodes.cpp revision d68a07650cdb2e18f18f362ba533459aa10e01b6
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" 18#include "llvm/Transforms/Scalar.h" 19#include "llvm/BasicBlock.h" 20#include "llvm/Function.h" 21#include "llvm/Instructions.h" 22#include "llvm/Type.h" 23#include "llvm/ADT/StringExtras.h" 24using namespace llvm; 25 26char UnifyFunctionExitNodes::ID = 0; 27static RegisterPass<UnifyFunctionExitNodes> 28X("mergereturn", "Unify function exit nodes"); 29 30Pass *llvm::createUnifyFunctionExitNodesPass() { 31 return new UnifyFunctionExitNodes(); 32} 33 34void 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 38 AU.addPreservedID(PromoteMemoryToRegisterID); 39 AU.addPreservedID(LowerSwitchID); 40} 41 42// UnifyAllExitNodes - Unify all exit nodes of the CFG by creating a new 43// BasicBlock, and converting all returns to unconditional branches to this 44// new basic block. The singular exit node is returned. 45// 46// If there are no return stmts in the Function, a null pointer is returned. 47// 48bool UnifyFunctionExitNodes::runOnFunction(Function &F) { 49 // Loop over all of the blocks in a function, tracking all of the blocks that 50 // return. 51 // 52 std::vector<BasicBlock*> ReturningBlocks; 53 std::vector<BasicBlock*> UnwindingBlocks; 54 std::vector<BasicBlock*> UnreachableBlocks; 55 for(Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 56 if (isa<ReturnInst>(I->getTerminator())) 57 ReturningBlocks.push_back(I); 58 else if (isa<UnwindInst>(I->getTerminator())) 59 UnwindingBlocks.push_back(I); 60 else if (isa<UnreachableInst>(I->getTerminator())) 61 UnreachableBlocks.push_back(I); 62 63 // Handle unwinding blocks first. 64 if (UnwindingBlocks.empty()) { 65 UnwindBlock = 0; 66 } else if (UnwindingBlocks.size() == 1) { 67 UnwindBlock = UnwindingBlocks.front(); 68 } else { 69 UnwindBlock = BasicBlock::Create("UnifiedUnwindBlock", &F); 70 new UnwindInst(UnwindBlock); 71 72 for (std::vector<BasicBlock*>::iterator I = UnwindingBlocks.begin(), 73 E = UnwindingBlocks.end(); I != E; ++I) { 74 BasicBlock *BB = *I; 75 BB->getInstList().pop_back(); // Remove the unwind insn 76 BranchInst::Create(UnwindBlock, BB); 77 } 78 } 79 80 // Then unreachable blocks. 81 if (UnreachableBlocks.empty()) { 82 UnreachableBlock = 0; 83 } else if (UnreachableBlocks.size() == 1) { 84 UnreachableBlock = UnreachableBlocks.front(); 85 } else { 86 UnreachableBlock = BasicBlock::Create("UnifiedUnreachableBlock", &F); 87 new UnreachableInst(UnreachableBlock); 88 89 for (std::vector<BasicBlock*>::iterator I = UnreachableBlocks.begin(), 90 E = UnreachableBlocks.end(); I != E; ++I) { 91 BasicBlock *BB = *I; 92 BB->getInstList().pop_back(); // Remove the unreachable inst. 93 BranchInst::Create(UnreachableBlock, BB); 94 } 95 } 96 97 // Now handle return blocks. 98 if (ReturningBlocks.empty()) { 99 ReturnBlock = 0; 100 return false; // No blocks return 101 } else if (ReturningBlocks.size() == 1) { 102 ReturnBlock = ReturningBlocks.front(); // Already has a single return block 103 return false; 104 } 105 106 // Otherwise, we need to insert a new basic block into the function, add a PHI 107 // nodes (if the function returns values), and convert all of the return 108 // instructions into unconditional branches. 109 // 110 BasicBlock *NewRetBlock = BasicBlock::Create("UnifiedReturnBlock", &F); 111 112 PHINode *PN = 0; 113 if (F.getReturnType() == Type::VoidTy) { 114 ReturnInst::Create(NULL, NewRetBlock); 115 } else { 116 // If the function doesn't return void... add a PHI node to the block... 117 PN = PHINode::Create(F.getReturnType(), "UnifiedRetVal"); 118 NewRetBlock->getInstList().push_back(PN); 119 ReturnInst::Create(PN, NewRetBlock); 120 } 121 122 // Loop over all of the blocks, replacing the return instruction with an 123 // unconditional branch. 124 // 125 for (std::vector<BasicBlock*>::iterator I = ReturningBlocks.begin(), 126 E = ReturningBlocks.end(); I != E; ++I) { 127 BasicBlock *BB = *I; 128 129 // Add an incoming element to the PHI node for every return instruction that 130 // is merging into this new block... 131 if (PN) 132 PN->addIncoming(BB->getTerminator()->getOperand(0), BB); 133 134 BB->getInstList().pop_back(); // Remove the return insn 135 BranchInst::Create(NewRetBlock, BB); 136 } 137 ReturnBlock = NewRetBlock; 138 return true; 139} 140