BasicBlockUtils.cpp revision 5560c9d49ccae132cabf1155f18aa0480dce3eda
14d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner//===-- BasicBlockUtils.cpp - BasicBlock Utilities -------------------------==// 24d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// 34d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// This family of functions perform manipulations on basic blocks, and 44d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// instructions contained within basic blocks. 54d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// 64d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner//===----------------------------------------------------------------------===// 74d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 84d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 94d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner#include "llvm/Function.h" 10b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner#include "llvm/iTerminators.h" 11b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner#include "llvm/Constant.h" 12b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner#include "llvm/Type.h" 134d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner#include <algorithm> 144d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 154d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) 164d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// with a value, then remove and delete the original instruction. 174d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// 184d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattnervoid ReplaceInstWithValue(BasicBlock::InstListType &BIL, 194d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner BasicBlock::iterator &BI, Value *V) { 2018961504fc2b299578dba817900a0696cf3ccc4dChris Lattner Instruction &I = *BI; 214d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Replaces all of the uses of the instruction with uses of the value 2218961504fc2b299578dba817900a0696cf3ccc4dChris Lattner I.replaceAllUsesWith(V); 234d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 2418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner std::string OldName = I.getName(); 2518961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 265560c9d49ccae132cabf1155f18aa0480dce3edaMisha Brukman // Delete the unnecessary instruction now... 2718961504fc2b299578dba817900a0696cf3ccc4dChris Lattner BI = BIL.erase(BI); 284d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 29a3bbcb5b664c1c851b87392119608901b2e1837cMisha Brukman // Make sure to propagate a name if there is one already... 3018961504fc2b299578dba817900a0696cf3ccc4dChris Lattner if (OldName.size() && !V->hasName()) 316e6026b46569b01f8f6d4dcdb6c899c3a9c76b3eChris Lattner V->setName(OldName, &BIL.getParent()->getSymbolTable()); 324d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner} 334d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 344d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 354d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// ReplaceInstWithInst - Replace the instruction specified by BI with the 364d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// instruction specified by I. The original instruction is deleted and BI is 374d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// updated to point to the new instruction. 384d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// 394d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattnervoid ReplaceInstWithInst(BasicBlock::InstListType &BIL, 404d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner BasicBlock::iterator &BI, Instruction *I) { 414d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner assert(I->getParent() == 0 && 424d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner "ReplaceInstWithInst: Instruction already inserted into basic block!"); 434d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 444d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Insert the new instruction into the basic block... 4518961504fc2b299578dba817900a0696cf3ccc4dChris Lattner BasicBlock::iterator New = BIL.insert(BI, I); 464d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 474d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Replace all uses of the old instruction, and delete it. 484d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner ReplaceInstWithValue(BIL, BI, I); 494d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 504d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Move BI back to point to the newly inserted instruction 5118961504fc2b299578dba817900a0696cf3ccc4dChris Lattner BI = New; 524d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner} 534d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 544d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// ReplaceInstWithInst - Replace the instruction specified by From with the 55b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner// instruction specified by To. 564d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// 574d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattnervoid ReplaceInstWithInst(Instruction *From, Instruction *To) { 5818961504fc2b299578dba817900a0696cf3ccc4dChris Lattner BasicBlock::iterator BI(From); 5918961504fc2b299578dba817900a0696cf3ccc4dChris Lattner ReplaceInstWithInst(From->getParent()->getInstList(), BI, To); 604d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner} 61b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner 62b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner// RemoveSuccessor - Change the specified terminator instruction such that its 63b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner// successor #SuccNum no longer exists. Because this reduces the outgoing 64b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner// degree of the current basic block, the actual terminator instruction itself 65b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner// may have to be changed. In the case where the last successor of the block is 66b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner// deleted, a return instruction is inserted in its place which can cause a 67b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner// suprising change in program behavior if it is not expected. 68b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner// 69b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattnervoid RemoveSuccessor(TerminatorInst *TI, unsigned SuccNum) { 70b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner assert(SuccNum < TI->getNumSuccessors() && 71b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner "Trying to remove a nonexistant successor!"); 72b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner 73b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner // If our old successor block contains any PHI nodes, remove the entry in the 74b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner // PHI nodes that comes from this branch... 75b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner // 76b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner BasicBlock *BB = TI->getParent(); 77b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner TI->getSuccessor(SuccNum)->removePredecessor(BB); 78b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner 79b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner TerminatorInst *NewTI = 0; 80b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner switch (TI->getOpcode()) { 81b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner case Instruction::Br: 82b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner // If this is a conditional branch... convert to unconditional branch. 83b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner if (TI->getNumSuccessors() == 2) { 84b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner cast<BranchInst>(TI)->setUnconditionalDest(TI->getSuccessor(1-SuccNum)); 85b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner } else { // Otherwise convert to a return instruction... 86b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner Value *RetVal = 0; 87b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner 88b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner // Create a value to return... if the function doesn't return null... 89b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner if (BB->getParent()->getReturnType() != Type::VoidTy) 90b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner RetVal = Constant::getNullValue(BB->getParent()->getReturnType()); 91b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner 92b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner // Create the return... 93b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner NewTI = new ReturnInst(RetVal); 94b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner } 95b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner break; 96b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner 97b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner case Instruction::Invoke: // Should convert to call 98b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner case Instruction::Switch: // Should remove entry 99b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner default: 100b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner case Instruction::Ret: // Cannot happen, has no successors! 101b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner assert(0 && "Unhandled terminator instruction type in RemoveSuccessor!"); 102b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner abort(); 103b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner } 104b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner 105b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner if (NewTI) // If it's a different instruction, replace. 106b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner ReplaceInstWithInst(TI, NewTI); 107b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner} 108