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/ADT/StringExtras.h" 19 #include "llvm/IR/BasicBlock.h" 20 #include "llvm/IR/Function.h" 21 #include "llvm/IR/Instructions.h" 22 #include "llvm/IR/Type.h" 23 #include "llvm/Transforms/Scalar.h" 24 using namespace llvm; 25 26 char UnifyFunctionExitNodes::ID = 0; 27 INITIALIZE_PASS(UnifyFunctionExitNodes, "mergereturn", 28 "Unify function exit nodes", false, false) 29 30 Pass *llvm::createUnifyFunctionExitNodesPass() { 31 return new UnifyFunctionExitNodes(); 32 } 33 34 void 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.addPreserved("mem2reg"); 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 // 48 bool 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*> UnreachableBlocks; 54 for(Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 55 if (isa<ReturnInst>(I->getTerminator())) 56 ReturningBlocks.push_back(I); 57 else if (isa<UnreachableInst>(I->getTerminator())) 58 UnreachableBlocks.push_back(I); 59 60 // Then unreachable blocks. 61 if (UnreachableBlocks.empty()) { 62 UnreachableBlock = 0; 63 } else if (UnreachableBlocks.size() == 1) { 64 UnreachableBlock = UnreachableBlocks.front(); 65 } else { 66 UnreachableBlock = BasicBlock::Create(F.getContext(), 67 "UnifiedUnreachableBlock", &F); 68 new UnreachableInst(F.getContext(), UnreachableBlock); 69 70 for (std::vector<BasicBlock*>::iterator I = UnreachableBlocks.begin(), 71 E = UnreachableBlocks.end(); I != E; ++I) { 72 BasicBlock *BB = *I; 73 BB->getInstList().pop_back(); // Remove the unreachable inst. 74 BranchInst::Create(UnreachableBlock, BB); 75 } 76 } 77 78 // Now handle return blocks. 79 if (ReturningBlocks.empty()) { 80 ReturnBlock = 0; 81 return false; // No blocks return 82 } else if (ReturningBlocks.size() == 1) { 83 ReturnBlock = ReturningBlocks.front(); // Already has a single return block 84 return false; 85 } 86 87 // Otherwise, we need to insert a new basic block into the function, add a PHI 88 // nodes (if the function returns values), and convert all of the return 89 // instructions into unconditional branches. 90 // 91 BasicBlock *NewRetBlock = BasicBlock::Create(F.getContext(), 92 "UnifiedReturnBlock", &F); 93 94 PHINode *PN = 0; 95 if (F.getReturnType()->isVoidTy()) { 96 ReturnInst::Create(F.getContext(), NULL, NewRetBlock); 97 } else { 98 // If the function doesn't return void... add a PHI node to the block... 99 PN = PHINode::Create(F.getReturnType(), ReturningBlocks.size(), 100 "UnifiedRetVal"); 101 NewRetBlock->getInstList().push_back(PN); 102 ReturnInst::Create(F.getContext(), PN, NewRetBlock); 103 } 104 105 // Loop over all of the blocks, replacing the return instruction with an 106 // unconditional branch. 107 // 108 for (std::vector<BasicBlock*>::iterator I = ReturningBlocks.begin(), 109 E = ReturningBlocks.end(); I != E; ++I) { 110 BasicBlock *BB = *I; 111 112 // Add an incoming element to the PHI node for every return instruction that 113 // is merging into this new block... 114 if (PN) 115 PN->addIncoming(BB->getTerminator()->getOperand(0), BB); 116 117 BB->getInstList().pop_back(); // Remove the return insn 118 BranchInst::Create(NewRetBlock, BB); 119 } 120 ReturnBlock = NewRetBlock; 121 return true; 122 } 123
