12fbfdcffd3e0cf41422aaa6c526c37cb02b81341Chris Lattner//===- UnifyFunctionExitNodes.cpp - Make all functions have a single exit -===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 963a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner// 10b444a1fff47162591933e00197375bbbd255f595Chris Lattner// This pass is used to ensure that functions have at most one return 11b444a1fff47162591933e00197375bbbd255f595Chris Lattner// instruction in them. Additionally, it keeps track of which node is the new 12b444a1fff47162591933e00197375bbbd255f595Chris Lattner// exit node of the CFG. If there are no exit nodes in the CFG, the getExitNode 13b444a1fff47162591933e00197375bbbd255f595Chris Lattner// method will return a null pointer. 1463a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner// 1563a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner//===----------------------------------------------------------------------===// 1663a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner 17fc514f40a63126bbda9404c717890f8dd6cbbcadChris Lattner#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/StringExtras.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/BasicBlock.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Type.h" 23d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Scalar.h" 24108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattnerusing namespace llvm; 25d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 261997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar UnifyFunctionExitNodes::ID = 0; 27d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(UnifyFunctionExitNodes, "mergereturn", 28ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Unify function exit nodes", false, false) 2993193f806378e06092820c099e437886c7309b94Chris Lattner 30108e4ab159b59a616b0868e396dc7ddc1fb48616Chris LattnerPass *llvm::createUnifyFunctionExitNodesPass() { 31f46057be77c39d972a2aacb9743ce265efa60b70Chris Lattner return new UnifyFunctionExitNodes(); 32f46057be77c39d972a2aacb9743ce265efa60b70Chris Lattner} 33f46057be77c39d972a2aacb9743ce265efa60b70Chris Lattner 346c0e0496dc8f901a282ae1f591b8af2ecf095b97Chris Lattnervoid UnifyFunctionExitNodes::getAnalysisUsage(AnalysisUsage &AU) const{ 356c0e0496dc8f901a282ae1f591b8af2ecf095b97Chris Lattner // We preserve the non-critical-edgeness property 366c0e0496dc8f901a282ae1f591b8af2ecf095b97Chris Lattner AU.addPreservedID(BreakCriticalEdgesID); 378d89e7bdbcea38fe2ab3c85d91359712cd45714bChris Lattner // This is a cluster of orthogonal Transforms 388d89e7bdbcea38fe2ab3c85d91359712cd45714bChris Lattner AU.addPreservedID(LowerSwitchID); 396c0e0496dc8f901a282ae1f591b8af2ecf095b97Chris Lattner} 406c0e0496dc8f901a282ae1f591b8af2ecf095b97Chris Lattner 4163a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner// UnifyAllExitNodes - Unify all exit nodes of the CFG by creating a new 4263a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner// BasicBlock, and converting all returns to unconditional branches to this 4363a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner// new basic block. The singular exit node is returned. 4463a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner// 452fbfdcffd3e0cf41422aaa6c526c37cb02b81341Chris Lattner// If there are no return stmts in the Function, a null pointer is returned. 4663a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner// 4718961504fc2b299578dba817900a0696cf3ccc4dChris Lattnerbool UnifyFunctionExitNodes::runOnFunction(Function &F) { 482fbfdcffd3e0cf41422aaa6c526c37cb02b81341Chris Lattner // Loop over all of the blocks in a function, tracking all of the blocks that 4963a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner // return. 5063a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner // 51de579f11ff018aeac07ca28e7c94dd477f342b9cChris Lattner std::vector<BasicBlock*> ReturningBlocks; 52ec7c1ab1dafa0fdb383d0e6df4726cecb4c88c70Chris Lattner std::vector<BasicBlock*> UnreachableBlocks; 53cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar for (BasicBlock &I : F) 54cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (isa<ReturnInst>(I.getTerminator())) 55cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar ReturningBlocks.push_back(&I); 56cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar else if (isa<UnreachableInst>(I.getTerminator())) 57cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar UnreachableBlocks.push_back(&I); 58f46057be77c39d972a2aacb9743ce265efa60b70Chris Lattner 59ec7c1ab1dafa0fdb383d0e6df4726cecb4c88c70Chris Lattner // Then unreachable blocks. 60ec7c1ab1dafa0fdb383d0e6df4726cecb4c88c70Chris Lattner if (UnreachableBlocks.empty()) { 61dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines UnreachableBlock = nullptr; 62ec7c1ab1dafa0fdb383d0e6df4726cecb4c88c70Chris Lattner } else if (UnreachableBlocks.size() == 1) { 63ec7c1ab1dafa0fdb383d0e6df4726cecb4c88c70Chris Lattner UnreachableBlock = UnreachableBlocks.front(); 64ec7c1ab1dafa0fdb383d0e6df4726cecb4c88c70Chris Lattner } else { 651d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson UnreachableBlock = BasicBlock::Create(F.getContext(), 661d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson "UnifiedUnreachableBlock", &F); 671d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson new UnreachableInst(F.getContext(), UnreachableBlock); 68ec7c1ab1dafa0fdb383d0e6df4726cecb4c88c70Chris Lattner 69fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman for (std::vector<BasicBlock*>::iterator I = UnreachableBlocks.begin(), 70ec7c1ab1dafa0fdb383d0e6df4726cecb4c88c70Chris Lattner E = UnreachableBlocks.end(); I != E; ++I) { 71ec7c1ab1dafa0fdb383d0e6df4726cecb4c88c70Chris Lattner BasicBlock *BB = *I; 72ec7c1ab1dafa0fdb383d0e6df4726cecb4c88c70Chris Lattner BB->getInstList().pop_back(); // Remove the unreachable inst. 73051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(UnreachableBlock, BB); 74ec7c1ab1dafa0fdb383d0e6df4726cecb4c88c70Chris Lattner } 75ec7c1ab1dafa0fdb383d0e6df4726cecb4c88c70Chris Lattner } 76ec7c1ab1dafa0fdb383d0e6df4726cecb4c88c70Chris Lattner 77ec7c1ab1dafa0fdb383d0e6df4726cecb4c88c70Chris Lattner // Now handle return blocks. 78417cf7ef96ffcf81f5ca6c48639c804c2aa68bceChris Lattner if (ReturningBlocks.empty()) { 79dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ReturnBlock = nullptr; 80b444a1fff47162591933e00197375bbbd255f595Chris Lattner return false; // No blocks return 8121801532fdd6019734e990603405a0d983266804Chris Lattner } else if (ReturningBlocks.size() == 1) { 82f46057be77c39d972a2aacb9743ce265efa60b70Chris Lattner ReturnBlock = ReturningBlocks.front(); // Already has a single return block 8321801532fdd6019734e990603405a0d983266804Chris Lattner return false; 8421801532fdd6019734e990603405a0d983266804Chris Lattner } 8563a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner 862fbfdcffd3e0cf41422aaa6c526c37cb02b81341Chris Lattner // Otherwise, we need to insert a new basic block into the function, add a PHI 87c5eb380b60689c0993e07025872a9038be967b40Devang Patel // nodes (if the function returns values), and convert all of the return 8863a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner // instructions into unconditional branches. 8963a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner // 901d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *NewRetBlock = BasicBlock::Create(F.getContext(), 911d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson "UnifiedReturnBlock", &F); 9263a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner 93dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PHINode *PN = nullptr; 94f012705c7e4ca8cf90b6b734ce1d5355daca5ba5Benjamin Kramer if (F.getReturnType()->isVoidTy()) { 95dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ReturnInst::Create(F.getContext(), nullptr, NewRetBlock); 96fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman } else { 972fbfdcffd3e0cf41422aaa6c526c37cb02b81341Chris Lattner // If the function doesn't return void... add a PHI node to the block... 983ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PN = PHINode::Create(F.getReturnType(), ReturningBlocks.size(), 993ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad "UnifiedRetVal"); 1008606d9924b2c1581e45748430be749f1e2934025Chris Lattner NewRetBlock->getInstList().push_back(PN); 1011d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ReturnInst::Create(F.getContext(), PN, NewRetBlock); 10263a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner } 10363a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner 10463a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner // Loop over all of the blocks, replacing the return instruction with an 10563a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner // unconditional branch. 10663a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner // 107fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman for (std::vector<BasicBlock*>::iterator I = ReturningBlocks.begin(), 108de579f11ff018aeac07ca28e7c94dd477f342b9cChris Lattner E = ReturningBlocks.end(); I != E; ++I) { 1096c0e0496dc8f901a282ae1f591b8af2ecf095b97Chris Lattner BasicBlock *BB = *I; 1106c0e0496dc8f901a282ae1f591b8af2ecf095b97Chris Lattner 1116c0e0496dc8f901a282ae1f591b8af2ecf095b97Chris Lattner // Add an incoming element to the PHI node for every return instruction that 1126c0e0496dc8f901a282ae1f591b8af2ecf095b97Chris Lattner // is merging into this new block... 113fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman if (PN) 114fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman PN->addIncoming(BB->getTerminator()->getOperand(0), BB); 1156c0e0496dc8f901a282ae1f591b8af2ecf095b97Chris Lattner 1166c0e0496dc8f901a282ae1f591b8af2ecf095b97Chris Lattner BB->getInstList().pop_back(); // Remove the return insn 117051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(NewRetBlock, BB); 11863a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner } 119f46057be77c39d972a2aacb9743ce265efa60b70Chris Lattner ReturnBlock = NewRetBlock; 12021801532fdd6019734e990603405a0d983266804Chris Lattner return true; 12163a0b2a9b4242913fc2763b217dc7ad71180711aChris Lattner} 122