Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 1 | //===- UnifyFunctionExitNodes.cpp - Make all functions have a single exit -===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame^] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | 63a0b2a | 2001-07-06 16:58:36 +0000 | [diff] [blame] | 9 | // |
Chris Lattner | b444a1f | 2002-05-07 18:51:25 +0000 | [diff] [blame] | 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. |
Chris Lattner | 63a0b2a | 2001-07-06 16:58:36 +0000 | [diff] [blame] | 14 | // |
| 15 | //===----------------------------------------------------------------------===// |
| 16 | |
Chris Lattner | fc514f4 | 2002-05-07 19:18:48 +0000 | [diff] [blame] | 17 | #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" |
Chris Lattner | 6c0e049 | 2003-03-31 17:30:25 +0000 | [diff] [blame] | 18 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 63a0b2a | 2001-07-06 16:58:36 +0000 | [diff] [blame] | 19 | #include "llvm/BasicBlock.h" |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 20 | #include "llvm/Function.h" |
Alkis Evlogimenos | eb62bc7 | 2004-07-29 12:17:34 +0000 | [diff] [blame] | 21 | #include "llvm/Instructions.h" |
Chris Lattner | 63a0b2a | 2001-07-06 16:58:36 +0000 | [diff] [blame] | 22 | #include "llvm/Type.h" |
Chris Lattner | 108e4ab | 2003-11-21 16:52:05 +0000 | [diff] [blame] | 23 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 24 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 25 | char UnifyFunctionExitNodes::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 26 | static RegisterPass<UnifyFunctionExitNodes> |
Chris Lattner | f629309 | 2002-07-23 18:06:35 +0000 | [diff] [blame] | 27 | X("mergereturn", "Unify function exit nodes"); |
Chris Lattner | 93193f8 | 2002-01-31 00:42:27 +0000 | [diff] [blame] | 28 | |
Chris Lattner | 191b0ba | 2006-06-02 18:40:06 +0000 | [diff] [blame] | 29 | int UnifyFunctionExitNodes::stub; |
| 30 | |
Chris Lattner | 108e4ab | 2003-11-21 16:52:05 +0000 | [diff] [blame] | 31 | Pass *llvm::createUnifyFunctionExitNodesPass() { |
Chris Lattner | f46057be | 2003-09-10 20:34:51 +0000 | [diff] [blame] | 32 | return new UnifyFunctionExitNodes(); |
| 33 | } |
| 34 | |
Chris Lattner | 6c0e049 | 2003-03-31 17:30:25 +0000 | [diff] [blame] | 35 | void UnifyFunctionExitNodes::getAnalysisUsage(AnalysisUsage &AU) const{ |
| 36 | // We preserve the non-critical-edgeness property |
| 37 | AU.addPreservedID(BreakCriticalEdgesID); |
Chris Lattner | 8d89e7b | 2006-05-09 04:13:41 +0000 | [diff] [blame] | 38 | // This is a cluster of orthogonal Transforms |
| 39 | AU.addPreservedID(PromoteMemoryToRegisterID); |
| 40 | AU.addPreservedID(LowerSelectID); |
| 41 | AU.addPreservedID(LowerSwitchID); |
Chris Lattner | 6c0e049 | 2003-03-31 17:30:25 +0000 | [diff] [blame] | 42 | } |
| 43 | |
Chris Lattner | 63a0b2a | 2001-07-06 16:58:36 +0000 | [diff] [blame] | 44 | // UnifyAllExitNodes - Unify all exit nodes of the CFG by creating a new |
| 45 | // BasicBlock, and converting all returns to unconditional branches to this |
| 46 | // new basic block. The singular exit node is returned. |
| 47 | // |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 48 | // If there are no return stmts in the Function, a null pointer is returned. |
Chris Lattner | 63a0b2a | 2001-07-06 16:58:36 +0000 | [diff] [blame] | 49 | // |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 50 | bool UnifyFunctionExitNodes::runOnFunction(Function &F) { |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 51 | // Loop over all of the blocks in a function, tracking all of the blocks that |
Chris Lattner | 63a0b2a | 2001-07-06 16:58:36 +0000 | [diff] [blame] | 52 | // return. |
| 53 | // |
Chris Lattner | de579f1 | 2003-05-22 22:00:07 +0000 | [diff] [blame] | 54 | std::vector<BasicBlock*> ReturningBlocks; |
Chris Lattner | f46057be | 2003-09-10 20:34:51 +0000 | [diff] [blame] | 55 | std::vector<BasicBlock*> UnwindingBlocks; |
Chris Lattner | ec7c1ab | 2004-10-16 18:21:33 +0000 | [diff] [blame] | 56 | std::vector<BasicBlock*> UnreachableBlocks; |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 57 | for(Function::iterator I = F.begin(), E = F.end(); I != E; ++I) |
| 58 | if (isa<ReturnInst>(I->getTerminator())) |
| 59 | ReturningBlocks.push_back(I); |
Chris Lattner | f46057be | 2003-09-10 20:34:51 +0000 | [diff] [blame] | 60 | else if (isa<UnwindInst>(I->getTerminator())) |
| 61 | UnwindingBlocks.push_back(I); |
Chris Lattner | ec7c1ab | 2004-10-16 18:21:33 +0000 | [diff] [blame] | 62 | else if (isa<UnreachableInst>(I->getTerminator())) |
| 63 | UnreachableBlocks.push_back(I); |
Chris Lattner | 63a0b2a | 2001-07-06 16:58:36 +0000 | [diff] [blame] | 64 | |
Chris Lattner | ec7c1ab | 2004-10-16 18:21:33 +0000 | [diff] [blame] | 65 | // Handle unwinding blocks first. |
Chris Lattner | f46057be | 2003-09-10 20:34:51 +0000 | [diff] [blame] | 66 | if (UnwindingBlocks.empty()) { |
| 67 | UnwindBlock = 0; |
| 68 | } else if (UnwindingBlocks.size() == 1) { |
| 69 | UnwindBlock = UnwindingBlocks.front(); |
| 70 | } else { |
| 71 | UnwindBlock = new BasicBlock("UnifiedUnwindBlock", &F); |
Chris Lattner | f8485c6 | 2003-11-20 18:25:24 +0000 | [diff] [blame] | 72 | new UnwindInst(UnwindBlock); |
Chris Lattner | f46057be | 2003-09-10 20:34:51 +0000 | [diff] [blame] | 73 | |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 74 | for (std::vector<BasicBlock*>::iterator I = UnwindingBlocks.begin(), |
Chris Lattner | f46057be | 2003-09-10 20:34:51 +0000 | [diff] [blame] | 75 | E = UnwindingBlocks.end(); I != E; ++I) { |
| 76 | BasicBlock *BB = *I; |
Chris Lattner | ec7c1ab | 2004-10-16 18:21:33 +0000 | [diff] [blame] | 77 | BB->getInstList().pop_back(); // Remove the unwind insn |
Alkis Evlogimenos | 99c58f4 | 2004-05-26 21:38:14 +0000 | [diff] [blame] | 78 | new BranchInst(UnwindBlock, BB); |
Chris Lattner | f46057be | 2003-09-10 20:34:51 +0000 | [diff] [blame] | 79 | } |
| 80 | } |
| 81 | |
Chris Lattner | ec7c1ab | 2004-10-16 18:21:33 +0000 | [diff] [blame] | 82 | // Then unreachable blocks. |
| 83 | if (UnreachableBlocks.empty()) { |
| 84 | UnreachableBlock = 0; |
| 85 | } else if (UnreachableBlocks.size() == 1) { |
| 86 | UnreachableBlock = UnreachableBlocks.front(); |
| 87 | } else { |
| 88 | UnreachableBlock = new BasicBlock("UnifiedUnreachableBlock", &F); |
| 89 | new UnreachableInst(UnreachableBlock); |
| 90 | |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 91 | for (std::vector<BasicBlock*>::iterator I = UnreachableBlocks.begin(), |
Chris Lattner | ec7c1ab | 2004-10-16 18:21:33 +0000 | [diff] [blame] | 92 | E = UnreachableBlocks.end(); I != E; ++I) { |
| 93 | BasicBlock *BB = *I; |
| 94 | BB->getInstList().pop_back(); // Remove the unreachable inst. |
| 95 | new BranchInst(UnreachableBlock, BB); |
| 96 | } |
| 97 | } |
| 98 | |
| 99 | // Now handle return blocks. |
Chris Lattner | 417cf7e | 2002-02-01 04:53:48 +0000 | [diff] [blame] | 100 | if (ReturningBlocks.empty()) { |
Chris Lattner | f46057be | 2003-09-10 20:34:51 +0000 | [diff] [blame] | 101 | ReturnBlock = 0; |
Chris Lattner | b444a1f | 2002-05-07 18:51:25 +0000 | [diff] [blame] | 102 | return false; // No blocks return |
Chris Lattner | 2180153 | 2002-01-31 01:12:06 +0000 | [diff] [blame] | 103 | } else if (ReturningBlocks.size() == 1) { |
Chris Lattner | f46057be | 2003-09-10 20:34:51 +0000 | [diff] [blame] | 104 | ReturnBlock = ReturningBlocks.front(); // Already has a single return block |
Chris Lattner | 2180153 | 2002-01-31 01:12:06 +0000 | [diff] [blame] | 105 | return false; |
| 106 | } |
Chris Lattner | 63a0b2a | 2001-07-06 16:58:36 +0000 | [diff] [blame] | 107 | |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 108 | // Otherwise, we need to insert a new basic block into the function, add a PHI |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 109 | // node (if the function returns a value), and convert all of the return |
Chris Lattner | 63a0b2a | 2001-07-06 16:58:36 +0000 | [diff] [blame] | 110 | // instructions into unconditional branches. |
| 111 | // |
Chris Lattner | f46057be | 2003-09-10 20:34:51 +0000 | [diff] [blame] | 112 | BasicBlock *NewRetBlock = new BasicBlock("UnifiedReturnBlock", &F); |
Chris Lattner | 63a0b2a | 2001-07-06 16:58:36 +0000 | [diff] [blame] | 113 | |
Chris Lattner | 6c0e049 | 2003-03-31 17:30:25 +0000 | [diff] [blame] | 114 | PHINode *PN = 0; |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 115 | if (F.getReturnType() != Type::VoidTy) { |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 116 | // If the function doesn't return void... add a PHI node to the block... |
Chris Lattner | 6c0e049 | 2003-03-31 17:30:25 +0000 | [diff] [blame] | 117 | PN = new PHINode(F.getReturnType(), "UnifiedRetVal"); |
Chris Lattner | 8606d99 | 2002-09-10 23:31:28 +0000 | [diff] [blame] | 118 | NewRetBlock->getInstList().push_back(PN); |
Chris Lattner | 63a0b2a | 2001-07-06 16:58:36 +0000 | [diff] [blame] | 119 | } |
Chris Lattner | 108e4ab | 2003-11-21 16:52:05 +0000 | [diff] [blame] | 120 | new ReturnInst(PN, NewRetBlock); |
Chris Lattner | 63a0b2a | 2001-07-06 16:58:36 +0000 | [diff] [blame] | 121 | |
| 122 | // Loop over all of the blocks, replacing the return instruction with an |
| 123 | // unconditional branch. |
| 124 | // |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 125 | for (std::vector<BasicBlock*>::iterator I = ReturningBlocks.begin(), |
Chris Lattner | de579f1 | 2003-05-22 22:00:07 +0000 | [diff] [blame] | 126 | E = ReturningBlocks.end(); I != E; ++I) { |
Chris Lattner | 6c0e049 | 2003-03-31 17:30:25 +0000 | [diff] [blame] | 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) PN->addIncoming(BB->getTerminator()->getOperand(0), BB); |
| 132 | |
| 133 | BB->getInstList().pop_back(); // Remove the return insn |
Chris Lattner | 108e4ab | 2003-11-21 16:52:05 +0000 | [diff] [blame] | 134 | new BranchInst(NewRetBlock, BB); |
Chris Lattner | 63a0b2a | 2001-07-06 16:58:36 +0000 | [diff] [blame] | 135 | } |
Chris Lattner | f46057be | 2003-09-10 20:34:51 +0000 | [diff] [blame] | 136 | ReturnBlock = NewRetBlock; |
Chris Lattner | 2180153 | 2002-01-31 01:12:06 +0000 | [diff] [blame] | 137 | return true; |
Chris Lattner | 63a0b2a | 2001-07-06 16:58:36 +0000 | [diff] [blame] | 138 | } |