LLVM API Documentation
00001 //===- UnifyFunctionExitNodes.cpp - Make all functions have a single exit -===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass is used to ensure that functions have at most one return 00011 // instruction in them. Additionally, it keeps track of which node is the new 00012 // exit node of the CFG. If there are no exit nodes in the CFG, the getExitNode 00013 // method will return a null pointer. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" 00018 #include "llvm/Transforms/Scalar.h" 00019 #include "llvm/BasicBlock.h" 00020 #include "llvm/Function.h" 00021 #include "llvm/Instructions.h" 00022 #include "llvm/Type.h" 00023 #include "llvm/ADT/StringExtras.h" 00024 using namespace llvm; 00025 00026 char UnifyFunctionExitNodes::ID = 0; 00027 static RegisterPass<UnifyFunctionExitNodes> 00028 X("mergereturn", "Unify function exit nodes"); 00029 00030 Pass *llvm::createUnifyFunctionExitNodesPass() { 00031 return new UnifyFunctionExitNodes(); 00032 } 00033 00034 void UnifyFunctionExitNodes::getAnalysisUsage(AnalysisUsage &AU) const{ 00035 // We preserve the non-critical-edgeness property 00036 AU.addPreservedID(BreakCriticalEdgesID); 00037 // This is a cluster of orthogonal Transforms 00038 AU.addPreservedID(PromoteMemoryToRegisterID); 00039 AU.addPreservedID(LowerSwitchID); 00040 } 00041 00042 // UnifyAllExitNodes - Unify all exit nodes of the CFG by creating a new 00043 // BasicBlock, and converting all returns to unconditional branches to this 00044 // new basic block. The singular exit node is returned. 00045 // 00046 // If there are no return stmts in the Function, a null pointer is returned. 00047 // 00048 bool UnifyFunctionExitNodes::runOnFunction(Function &F) { 00049 // Loop over all of the blocks in a function, tracking all of the blocks that 00050 // return. 00051 // 00052 std::vector<BasicBlock*> ReturningBlocks; 00053 std::vector<BasicBlock*> UnwindingBlocks; 00054 std::vector<BasicBlock*> UnreachableBlocks; 00055 for(Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 00056 if (isa<ReturnInst>(I->getTerminator())) 00057 ReturningBlocks.push_back(I); 00058 else if (isa<UnwindInst>(I->getTerminator())) 00059 UnwindingBlocks.push_back(I); 00060 else if (isa<UnreachableInst>(I->getTerminator())) 00061 UnreachableBlocks.push_back(I); 00062 00063 // Handle unwinding blocks first. 00064 if (UnwindingBlocks.empty()) { 00065 UnwindBlock = 0; 00066 } else if (UnwindingBlocks.size() == 1) { 00067 UnwindBlock = UnwindingBlocks.front(); 00068 } else { 00069 UnwindBlock = BasicBlock::Create(F.getContext(), "UnifiedUnwindBlock", &F); 00070 new UnwindInst(F.getContext(), UnwindBlock); 00071 00072 for (std::vector<BasicBlock*>::iterator I = UnwindingBlocks.begin(), 00073 E = UnwindingBlocks.end(); I != E; ++I) { 00074 BasicBlock *BB = *I; 00075 BB->getInstList().pop_back(); // Remove the unwind insn 00076 BranchInst::Create(UnwindBlock, BB); 00077 } 00078 } 00079 00080 // Then unreachable blocks. 00081 if (UnreachableBlocks.empty()) { 00082 UnreachableBlock = 0; 00083 } else if (UnreachableBlocks.size() == 1) { 00084 UnreachableBlock = UnreachableBlocks.front(); 00085 } else { 00086 UnreachableBlock = BasicBlock::Create(F.getContext(), 00087 "UnifiedUnreachableBlock", &F); 00088 new UnreachableInst(F.getContext(), UnreachableBlock); 00089 00090 for (std::vector<BasicBlock*>::iterator I = UnreachableBlocks.begin(), 00091 E = UnreachableBlocks.end(); I != E; ++I) { 00092 BasicBlock *BB = *I; 00093 BB->getInstList().pop_back(); // Remove the unreachable inst. 00094 BranchInst::Create(UnreachableBlock, BB); 00095 } 00096 } 00097 00098 // Now handle return blocks. 00099 if (ReturningBlocks.empty()) { 00100 ReturnBlock = 0; 00101 return false; // No blocks return 00102 } else if (ReturningBlocks.size() == 1) { 00103 ReturnBlock = ReturningBlocks.front(); // Already has a single return block 00104 return false; 00105 } 00106 00107 // Otherwise, we need to insert a new basic block into the function, add a PHI 00108 // nodes (if the function returns values), and convert all of the return 00109 // instructions into unconditional branches. 00110 // 00111 BasicBlock *NewRetBlock = BasicBlock::Create(F.getContext(), 00112 "UnifiedReturnBlock", &F); 00113 00114 PHINode *PN = 0; 00115 if (F.getReturnType() == Type::getVoidTy(F.getContext())) { 00116 ReturnInst::Create(F.getContext(), NULL, NewRetBlock); 00117 } else { 00118 // If the function doesn't return void... add a PHI node to the block... 00119 PN = PHINode::Create(F.getReturnType(), "UnifiedRetVal"); 00120 NewRetBlock->getInstList().push_back(PN); 00121 ReturnInst::Create(F.getContext(), PN, NewRetBlock); 00122 } 00123 00124 // Loop over all of the blocks, replacing the return instruction with an 00125 // unconditional branch. 00126 // 00127 for (std::vector<BasicBlock*>::iterator I = ReturningBlocks.begin(), 00128 E = ReturningBlocks.end(); I != E; ++I) { 00129 BasicBlock *BB = *I; 00130 00131 // Add an incoming element to the PHI node for every return instruction that 00132 // is merging into this new block... 00133 if (PN) 00134 PN->addIncoming(BB->getTerminator()->getOperand(0), BB); 00135 00136 BB->getInstList().pop_back(); // Remove the return insn 00137 BranchInst::Create(NewRetBlock, BB); 00138 } 00139 ReturnBlock = NewRetBlock; 00140 return true; 00141 }