X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FUnifyFunctionExitNodes.cpp;h=0c2fc0a972b53c931706a5f9fd82bb13563a9e67;hb=7ed0364cee76de015ada95cfe08073e3b8cba825;hp=da7b1f609aea8f8ab610cff4237b219f4ad2cf7c;hpb=417cf7ef96ffcf81f5ca6c48639c804c2aa68bce;p=oota-llvm.git diff --git a/lib/Transforms/Utils/UnifyFunctionExitNodes.cpp b/lib/Transforms/Utils/UnifyFunctionExitNodes.cpp index da7b1f609ae..0c2fc0a972b 100644 --- a/lib/Transforms/Utils/UnifyFunctionExitNodes.cpp +++ b/lib/Transforms/Utils/UnifyFunctionExitNodes.cpp @@ -1,76 +1,122 @@ -//===- SimplifyCFG.cpp - CFG Simplification Routines -------------*- C++ -*--=// +//===- UnifyFunctionExitNodes.cpp - Make all functions have a single exit -===// // -// This file provides several routines that are useful for simplifying CFGs in -// various ways... +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass is used to ensure that functions have at most one return +// instruction in them. Additionally, it keeps track of which node is the new +// exit node of the CFG. If there are no exit nodes in the CFG, the getExitNode +// method will return a null pointer. // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/UnifyMethodExitNodes.h" -#include "llvm/BasicBlock.h" -#include "llvm/Method.h" -#include "llvm/iTerminators.h" -#include "llvm/iPHINode.h" -#include "llvm/Type.h" -using std::vector; +#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Type.h" +#include "llvm/Transforms/Scalar.h" +using namespace llvm; -AnalysisID UnifyMethodExitNodes::ID(AnalysisID::create()); +char UnifyFunctionExitNodes::ID = 0; +INITIALIZE_PASS(UnifyFunctionExitNodes, "mergereturn", + "Unify function exit nodes", false, false) +Pass *llvm::createUnifyFunctionExitNodesPass() { + return new UnifyFunctionExitNodes(); +} + +void UnifyFunctionExitNodes::getAnalysisUsage(AnalysisUsage &AU) const{ + // We preserve the non-critical-edgeness property + AU.addPreservedID(BreakCriticalEdgesID); + // This is a cluster of orthogonal Transforms + AU.addPreserved("mem2reg"); + AU.addPreservedID(LowerSwitchID); +} // UnifyAllExitNodes - Unify all exit nodes of the CFG by creating a new // BasicBlock, and converting all returns to unconditional branches to this // new basic block. The singular exit node is returned. // -// If there are no return stmts in the Method, a null pointer is returned. +// If there are no return stmts in the Function, a null pointer is returned. // -bool UnifyMethodExitNodes::doit(Method *M, BasicBlock *&ExitNode) { - // Loop over all of the blocks in a method, tracking all of the blocks that +bool UnifyFunctionExitNodes::runOnFunction(Function &F) { + // Loop over all of the blocks in a function, tracking all of the blocks that // return. // - vector ReturningBlocks; - for(Method::iterator I = M->begin(), E = M->end(); I != E; ++I) - if (isa((*I)->getTerminator())) - ReturningBlocks.push_back(*I); + std::vector ReturningBlocks; + std::vector UnreachableBlocks; + for(Function::iterator I = F.begin(), E = F.end(); I != E; ++I) + if (isa(I->getTerminator())) + ReturningBlocks.push_back(I); + else if (isa(I->getTerminator())) + UnreachableBlocks.push_back(I); + + // Then unreachable blocks. + if (UnreachableBlocks.empty()) { + UnreachableBlock = nullptr; + } else if (UnreachableBlocks.size() == 1) { + UnreachableBlock = UnreachableBlocks.front(); + } else { + UnreachableBlock = BasicBlock::Create(F.getContext(), + "UnifiedUnreachableBlock", &F); + new UnreachableInst(F.getContext(), UnreachableBlock); + + for (std::vector::iterator I = UnreachableBlocks.begin(), + E = UnreachableBlocks.end(); I != E; ++I) { + BasicBlock *BB = *I; + BB->getInstList().pop_back(); // Remove the unreachable inst. + BranchInst::Create(UnreachableBlock, BB); + } + } + // Now handle return blocks. if (ReturningBlocks.empty()) { - ExitNode = 0; - return false; // No blocks return + ReturnBlock = nullptr; + return false; // No blocks return } else if (ReturningBlocks.size() == 1) { - ExitNode = ReturningBlocks.front(); // Already has a single return block + ReturnBlock = ReturningBlocks.front(); // Already has a single return block return false; } - // Otherwise, we need to insert a new basic block into the method, add a PHI - // node (if the function returns a value), and convert all of the return + // Otherwise, we need to insert a new basic block into the function, add a PHI + // nodes (if the function returns values), and convert all of the return // instructions into unconditional branches. // - BasicBlock *NewRetBlock = new BasicBlock("UnifiedExitNode", M); + BasicBlock *NewRetBlock = BasicBlock::Create(F.getContext(), + "UnifiedReturnBlock", &F); - if (M->getReturnType() != Type::VoidTy) { - // If the method doesn't return void... add a PHI node to the block... - PHINode *PN = new PHINode(M->getReturnType()); - NewRetBlock->getInstList().push_back(PN); - - // Add an incoming element to the PHI node for every return instruction that - // is merging into this new block... - for (vector::iterator I = ReturningBlocks.begin(), - E = ReturningBlocks.end(); I != E; ++I) - PN->addIncoming((*I)->getTerminator()->getOperand(0), *I); - - // Add a return instruction to return the result of the PHI node... - NewRetBlock->getInstList().push_back(new ReturnInst(PN)); + PHINode *PN = nullptr; + if (F.getReturnType()->isVoidTy()) { + ReturnInst::Create(F.getContext(), nullptr, NewRetBlock); } else { - // If it returns void, just add a return void instruction to the block - NewRetBlock->getInstList().push_back(new ReturnInst()); + // If the function doesn't return void... add a PHI node to the block... + PN = PHINode::Create(F.getReturnType(), ReturningBlocks.size(), + "UnifiedRetVal"); + NewRetBlock->getInstList().push_back(PN); + ReturnInst::Create(F.getContext(), PN, NewRetBlock); } // Loop over all of the blocks, replacing the return instruction with an // unconditional branch. // - for (vector::iterator I = ReturningBlocks.begin(), - E = ReturningBlocks.end(); I != E; ++I) { - delete (*I)->getInstList().pop_back(); // Remove the return insn - (*I)->getInstList().push_back(new BranchInst(NewRetBlock)); + for (std::vector::iterator I = ReturningBlocks.begin(), + E = ReturningBlocks.end(); I != E; ++I) { + BasicBlock *BB = *I; + + // Add an incoming element to the PHI node for every return instruction that + // is merging into this new block... + if (PN) + PN->addIncoming(BB->getTerminator()->getOperand(0), BB); + + BB->getInstList().pop_back(); // Remove the return insn + BranchInst::Create(NewRetBlock, BB); } - ExitNode = NewRetBlock; + ReturnBlock = NewRetBlock; return true; }