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/IR/BasicBlock.h" 19 #include "llvm/IR/Function.h" 20 #include "llvm/IR/Instructions.h" 21 #include "llvm/IR/Type.h" 22 #include "llvm/Transforms/Utils.h" 23 using namespace llvm; 24 25 char UnifyFunctionExitNodes::ID = 0; 26 INITIALIZE_PASS(UnifyFunctionExitNodes, "mergereturn", 27 "Unify function exit nodes", false, false) 28 29 Pass *llvm::createUnifyFunctionExitNodesPass() { 30 return new UnifyFunctionExitNodes(); 31 } 32 33 void UnifyFunctionExitNodes::getAnalysisUsage(AnalysisUsage &AU) const{ 34 // We preserve the non-critical-edgeness property 35 AU.addPreservedID(BreakCriticalEdgesID); 36 // This is a cluster of orthogonal Transforms 37 AU.addPreservedID(LowerSwitchID); 38 } 39 40 // UnifyAllExitNodes - Unify all exit nodes of the CFG by creating a new 41 // BasicBlock, and converting all returns to unconditional branches to this 42 // new basic block. The singular exit node is returned. 43 // 44 // If there are no return stmts in the Function, a null pointer is returned. 45 // 46 bool UnifyFunctionExitNodes::runOnFunction(Function &F) { 47 // Loop over all of the blocks in a function, tracking all of the blocks that 48 // return. 49 // 50 std::vector<BasicBlock*> ReturningBlocks; 51 std::vector<BasicBlock*> UnreachableBlocks; 52 for (BasicBlock &I : F) 53 if (isa<ReturnInst>(I.getTerminator())) 54 ReturningBlocks.push_back(&I); 55 else if (isa<UnreachableInst>(I.getTerminator())) 56 UnreachableBlocks.push_back(&I); 57 58 // Then unreachable blocks. 59 if (UnreachableBlocks.empty()) { 60 UnreachableBlock = nullptr; 61 } else if (UnreachableBlocks.size() == 1) { 62 UnreachableBlock = UnreachableBlocks.front(); 63 } else { 64 UnreachableBlock = BasicBlock::Create(F.getContext(), 65 "UnifiedUnreachableBlock", &F); 66 new UnreachableInst(F.getContext(), UnreachableBlock); 67 68 for (BasicBlock *BB : UnreachableBlocks) { 69 BB->getInstList().pop_back(); // Remove the unreachable inst. 70 BranchInst::Create(UnreachableBlock, BB); 71 } 72 } 73 74 // Now handle return blocks. 75 if (ReturningBlocks.empty()) { 76 ReturnBlock = nullptr; 77 return false; // No blocks return 78 } else if (ReturningBlocks.size() == 1) { 79 ReturnBlock = ReturningBlocks.front(); // Already has a single return block 80 return false; 81 } 82 83 // Otherwise, we need to insert a new basic block into the function, add a PHI 84 // nodes (if the function returns values), and convert all of the return 85 // instructions into unconditional branches. 86 // 87 BasicBlock *NewRetBlock = BasicBlock::Create(F.getContext(), 88 "UnifiedReturnBlock", &F); 89 90 PHINode *PN = nullptr; 91 if (F.getReturnType()->isVoidTy()) { 92 ReturnInst::Create(F.getContext(), nullptr, NewRetBlock); 93 } else { 94 // If the function doesn't return void... add a PHI node to the block... 95 PN = PHINode::Create(F.getReturnType(), ReturningBlocks.size(), 96 "UnifiedRetVal"); 97 NewRetBlock->getInstList().push_back(PN); 98 ReturnInst::Create(F.getContext(), PN, NewRetBlock); 99 } 100 101 // Loop over all of the blocks, replacing the return instruction with an 102 // unconditional branch. 103 // 104 for (BasicBlock *BB : ReturningBlocks) { 105 // Add an incoming element to the PHI node for every return instruction that 106 // is merging into this new block... 107 if (PN) 108 PN->addIncoming(BB->getTerminator()->getOperand(0), BB); 109 110 BB->getInstList().pop_back(); // Remove the return insn 111 BranchInst::Create(NewRetBlock, BB); 112 } 113 ReturnBlock = NewRetBlock; 114 return true; 115 } 116