LLVM API Documentation
00001 //===- UnifyFunctionExitNodes.cpp - Make all functions have a single exit -===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source 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 using namespace llvm; 00024 00025 static RegisterOpt<UnifyFunctionExitNodes> 00026 X("mergereturn", "Unify function exit nodes"); 00027 00028 int UnifyFunctionExitNodes::stub; 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(LowerSelectID); 00040 AU.addPreservedID(LowerSwitchID); 00041 } 00042 00043 // UnifyAllExitNodes - Unify all exit nodes of the CFG by creating a new 00044 // BasicBlock, and converting all returns to unconditional branches to this 00045 // new basic block. The singular exit node is returned. 00046 // 00047 // If there are no return stmts in the Function, a null pointer is returned. 00048 // 00049 bool UnifyFunctionExitNodes::runOnFunction(Function &F) { 00050 // Loop over all of the blocks in a function, tracking all of the blocks that 00051 // return. 00052 // 00053 std::vector<BasicBlock*> ReturningBlocks; 00054 std::vector<BasicBlock*> UnwindingBlocks; 00055 std::vector<BasicBlock*> UnreachableBlocks; 00056 for(Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 00057 if (isa<ReturnInst>(I->getTerminator())) 00058 ReturningBlocks.push_back(I); 00059 else if (isa<UnwindInst>(I->getTerminator())) 00060 UnwindingBlocks.push_back(I); 00061 else if (isa<UnreachableInst>(I->getTerminator())) 00062 UnreachableBlocks.push_back(I); 00063 00064 // Handle unwinding blocks first. 00065 if (UnwindingBlocks.empty()) { 00066 UnwindBlock = 0; 00067 } else if (UnwindingBlocks.size() == 1) { 00068 UnwindBlock = UnwindingBlocks.front(); 00069 } else { 00070 UnwindBlock = new BasicBlock("UnifiedUnwindBlock", &F); 00071 new UnwindInst(UnwindBlock); 00072 00073 for (std::vector<BasicBlock*>::iterator I = UnwindingBlocks.begin(), 00074 E = UnwindingBlocks.end(); I != E; ++I) { 00075 BasicBlock *BB = *I; 00076 BB->getInstList().pop_back(); // Remove the unwind insn 00077 new BranchInst(UnwindBlock, BB); 00078 } 00079 } 00080 00081 // Then unreachable blocks. 00082 if (UnreachableBlocks.empty()) { 00083 UnreachableBlock = 0; 00084 } else if (UnreachableBlocks.size() == 1) { 00085 UnreachableBlock = UnreachableBlocks.front(); 00086 } else { 00087 UnreachableBlock = new BasicBlock("UnifiedUnreachableBlock", &F); 00088 new UnreachableInst(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 new BranchInst(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 // node (if the function returns a value), and convert all of the return 00109 // instructions into unconditional branches. 00110 // 00111 BasicBlock *NewRetBlock = new BasicBlock("UnifiedReturnBlock", &F); 00112 00113 PHINode *PN = 0; 00114 if (F.getReturnType() != Type::VoidTy) { 00115 // If the function doesn't return void... add a PHI node to the block... 00116 PN = new PHINode(F.getReturnType(), "UnifiedRetVal"); 00117 NewRetBlock->getInstList().push_back(PN); 00118 } 00119 new ReturnInst(PN, NewRetBlock); 00120 00121 // Loop over all of the blocks, replacing the return instruction with an 00122 // unconditional branch. 00123 // 00124 for (std::vector<BasicBlock*>::iterator I = ReturningBlocks.begin(), 00125 E = ReturningBlocks.end(); I != E; ++I) { 00126 BasicBlock *BB = *I; 00127 00128 // Add an incoming element to the PHI node for every return instruction that 00129 // is merging into this new block... 00130 if (PN) PN->addIncoming(BB->getTerminator()->getOperand(0), BB); 00131 00132 BB->getInstList().pop_back(); // Remove the return insn 00133 new BranchInst(NewRetBlock, BB); 00134 } 00135 ReturnBlock = NewRetBlock; 00136 return true; 00137 }