14d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner//===-- BasicBlockUtils.cpp - BasicBlock Utilities -------------------------==// 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//===----------------------------------------------------------------------===// 94d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// 104d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// This family of functions perform manipulations on basic blocks, and 114d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// instructions contained within basic blocks. 124d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// 134d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner//===----------------------------------------------------------------------===// 144d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 154d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 1654b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner#include "llvm/Analysis/AliasAnalysis.h" 1781e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#include "llvm/Analysis/CFG.h" 18b5b7997fd0765f73b711ea4c72e4433ce3637794Chris Lattner#include "llvm/Analysis/LoopInfo.h" 19b5b7997fd0765f73b711ea4c72e4433ce3637794Chris Lattner#include "llvm/Analysis/MemoryDependenceAnalysis.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constant.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 2236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 240b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 250b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 260b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Type.h" 2736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/ValueHandle.h" 287d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 29d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Scalar.h" 30d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/Local.h" 314d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner#include <algorithm> 32f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 33d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 3471af9b07a58a264064813545889cf6473ce23de6Chris Lattner/// DeleteDeadBlock - Delete the specified block, which must have no 3571af9b07a58a264064813545889cf6473ce23de6Chris Lattner/// predecessors. 3671af9b07a58a264064813545889cf6473ce23de6Chris Lattnervoid llvm::DeleteDeadBlock(BasicBlock *BB) { 372973a25dbc0ee1081e34421e53b8f4308b624854Chris Lattner assert((pred_begin(BB) == pred_end(BB) || 382973a25dbc0ee1081e34421e53b8f4308b624854Chris Lattner // Can delete self loop. 392973a25dbc0ee1081e34421e53b8f4308b624854Chris Lattner BB->getSinglePredecessor() == BB) && "Block is not dead!"); 402b1ba24fb75e633560846e551acadade92783bb3Chris Lattner TerminatorInst *BBTerm = BB->getTerminator(); 41e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 422b1ba24fb75e633560846e551acadade92783bb3Chris Lattner // Loop through all of our successors and make sure they know that one 432b1ba24fb75e633560846e551acadade92783bb3Chris Lattner // of their predecessors is going away. 442b1ba24fb75e633560846e551acadade92783bb3Chris Lattner for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) 452b1ba24fb75e633560846e551acadade92783bb3Chris Lattner BBTerm->getSuccessor(i)->removePredecessor(BB); 46e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 472b1ba24fb75e633560846e551acadade92783bb3Chris Lattner // Zap all the instructions in the block. 482b1ba24fb75e633560846e551acadade92783bb3Chris Lattner while (!BB->empty()) { 492b1ba24fb75e633560846e551acadade92783bb3Chris Lattner Instruction &I = BB->back(); 502b1ba24fb75e633560846e551acadade92783bb3Chris Lattner // If this instruction is used, replace uses with an arbitrary value. 512b1ba24fb75e633560846e551acadade92783bb3Chris Lattner // Because control flow can't get here, we don't care what we replace the 522b1ba24fb75e633560846e551acadade92783bb3Chris Lattner // value with. Note that since this block is unreachable, and all values 532b1ba24fb75e633560846e551acadade92783bb3Chris Lattner // contained within it must dominate their uses, that all uses will 542b1ba24fb75e633560846e551acadade92783bb3Chris Lattner // eventually be removed (they are themselves dead). 552b1ba24fb75e633560846e551acadade92783bb3Chris Lattner if (!I.use_empty()) 569e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson I.replaceAllUsesWith(UndefValue::get(I.getType())); 572b1ba24fb75e633560846e551acadade92783bb3Chris Lattner BB->getInstList().pop_back(); 582b1ba24fb75e633560846e551acadade92783bb3Chris Lattner } 59e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 602b1ba24fb75e633560846e551acadade92783bb3Chris Lattner // Zap the block! 612b1ba24fb75e633560846e551acadade92783bb3Chris Lattner BB->eraseFromParent(); 622b1ba24fb75e633560846e551acadade92783bb3Chris Lattner} 632b1ba24fb75e633560846e551acadade92783bb3Chris Lattner 6429874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner/// FoldSingleEntryPHINodes - We know that BB has one predecessor. If there are 6529874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner/// any single-entry PHI nodes in it, fold them away. This handles the case 6629874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner/// when all entries to the PHI nodes in a block are guaranteed equal, such as 6729874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner/// when the block has exactly one predecessor. 68b5b7997fd0765f73b711ea4c72e4433ce3637794Chris Lattnervoid llvm::FoldSingleEntryPHINodes(BasicBlock *BB, Pass *P) { 69b5b7997fd0765f73b711ea4c72e4433ce3637794Chris Lattner if (!isa<PHINode>(BB->begin())) return; 70e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 71dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AliasAnalysis *AA = nullptr; 72dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MemoryDependenceAnalysis *MemDep = nullptr; 73b5b7997fd0765f73b711ea4c72e4433ce3637794Chris Lattner if (P) { 74b5b7997fd0765f73b711ea4c72e4433ce3637794Chris Lattner AA = P->getAnalysisIfAvailable<AliasAnalysis>(); 75b5b7997fd0765f73b711ea4c72e4433ce3637794Chris Lattner MemDep = P->getAnalysisIfAvailable<MemoryDependenceAnalysis>(); 76b5b7997fd0765f73b711ea4c72e4433ce3637794Chris Lattner } 77e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 7829874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 7929874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner if (PN->getIncomingValue(0) != PN) 8029874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 8129874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner else 829e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 83e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 84b5b7997fd0765f73b711ea4c72e4433ce3637794Chris Lattner if (MemDep) 85b5b7997fd0765f73b711ea4c72e4433ce3637794Chris Lattner MemDep->removeInstruction(PN); // Memdep updates AA itself. 86b5b7997fd0765f73b711ea4c72e4433ce3637794Chris Lattner else if (AA && isa<PointerType>(PN->getType())) 87b5b7997fd0765f73b711ea4c72e4433ce3637794Chris Lattner AA->deleteValue(PN); 88e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 8929874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner PN->eraseFromParent(); 9029874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner } 9129874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner} 9229874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner 9329874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner 94afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it 95afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// is dead. Also recursively delete any operands that become dead as 96afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// a result. This includes tracing the def-use list from the PHI to see if 9735738ac150afafe2359268d4b2169498c6c98c5fDan Gohman/// it is ultimately unused or if it reaches an unused cycle. 988e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool llvm::DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI) { 99afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman // Recursively deleting a PHI may cause multiple PHIs to be deleted 100afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman // or RAUW'd undef, so use an array of WeakVH for the PHIs to delete. 101afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman SmallVector<WeakVH, 8> PHIs; 102afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman for (BasicBlock::iterator I = BB->begin(); 103afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman PHINode *PN = dyn_cast<PHINode>(I); ++I) 104afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman PHIs.push_back(PN); 105afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman 10690fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman bool Changed = false; 107afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 108afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*())) 1098e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer Changed |= RecursivelyDeleteDeadPHINode(PN, TLI); 11090fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman 11190fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman return Changed; 112afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman} 113afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman 114438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman/// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, 115438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman/// if possible. The return value indicates success or failure. 116882029269e0cf4b497993b8e9a754429ef035facChris Lattnerbool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, Pass *P) { 1171c034dcbbc86674cc146340a877495f71d9a2569Dan Gohman // Don't merge away blocks who have their address taken. 1181c034dcbbc86674cc146340a877495f71d9a2569Dan Gohman if (BB->hasAddressTaken()) return false; 119e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 1201c034dcbbc86674cc146340a877495f71d9a2569Dan Gohman // Can't merge if there are multiple predecessors, or no predecessors. 1211c034dcbbc86674cc146340a877495f71d9a2569Dan Gohman BasicBlock *PredBB = BB->getUniquePredecessor(); 122438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman if (!PredBB) return false; 1231c034dcbbc86674cc146340a877495f71d9a2569Dan Gohman 1243ecaf1b33940470d5bf554135778ba5a8bce9a79Owen Anderson // Don't break self-loops. 125438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman if (PredBB == BB) return false; 1263ecaf1b33940470d5bf554135778ba5a8bce9a79Owen Anderson // Don't break invokes. 127438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman if (isa<InvokeInst>(PredBB->getTerminator())) return false; 128e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 129438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman succ_iterator SI(succ_begin(PredBB)), SE(succ_end(PredBB)); 130dc85f8ab808aec2f673262f5145eda58538cfb26Chris Lattner BasicBlock *OnlySucc = BB; 131438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman for (; SI != SE; ++SI) 132438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman if (*SI != OnlySucc) { 133dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines OnlySucc = nullptr; // There are multiple distinct successors! 134438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman break; 135438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman } 136e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 137438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman // Can't merge if there are multiple successors. 138438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman if (!OnlySucc) return false; 139e435a5d9374b61049b16ef69e6314542815fadb4Devang Patel 140438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman // Can't merge if there is PHI loop. 141438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; ++BI) { 142438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman if (PHINode *PN = dyn_cast<PHINode>(BI)) { 143438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 144438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman if (PN->getIncomingValue(i) == PN) 145438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman return false; 146438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman } else 147438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman break; 148438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman } 149438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman 150438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman // Begin by getting rid of unneeded PHIs. 151dc85f8ab808aec2f673262f5145eda58538cfb26Chris Lattner if (isa<PHINode>(BB->front())) 152b5b7997fd0765f73b711ea4c72e4433ce3637794Chris Lattner FoldSingleEntryPHINodes(BB, P); 153e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 154b31b06d04b81c5383e2fba0cd44d4ba3f324a794Owen Anderson // Delete the unconditional branch from the predecessor... 155b31b06d04b81c5383e2fba0cd44d4ba3f324a794Owen Anderson PredBB->getInstList().pop_back(); 156e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 157b31b06d04b81c5383e2fba0cd44d4ba3f324a794Owen Anderson // Make all PHI nodes that referred to BB now refer to Pred as their 158b31b06d04b81c5383e2fba0cd44d4ba3f324a794Owen Anderson // source... 159b31b06d04b81c5383e2fba0cd44d4ba3f324a794Owen Anderson BB->replaceAllUsesWith(PredBB); 160e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 16195c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // Move all definitions in the successor to the predecessor... 16295c3e48f9557adb6064d580684bb14cacec2f826Jay Foad PredBB->getInstList().splice(PredBB->end(), BB->getInstList()); 163e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 164438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman // Inherit predecessors name if it exists. 16511f2ec8eb534502a0d5b7e3c13c1a38e877876b2Owen Anderson if (!PredBB->hasName()) 16611f2ec8eb534502a0d5b7e3c13c1a38e877876b2Owen Anderson PredBB->takeName(BB); 167e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 168b31b06d04b81c5383e2fba0cd44d4ba3f324a794Owen Anderson // Finally, erase the old block and update dominator info. 169b31b06d04b81c5383e2fba0cd44d4ba3f324a794Owen Anderson if (P) { 17036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DominatorTreeWrapperPass *DTWP = 17136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines P->getAnalysisIfAvailable<DominatorTreeWrapperPass>()) { 17236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree &DT = DTWP->getDomTree(); 17336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DomTreeNode *DTN = DT.getNode(BB)) { 17436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DomTreeNode *PredDTN = DT.getNode(PredBB); 175fbbd4abfe5a89e432240d2c05201b44a5e2f2f78Jakob Stoklund Olesen SmallVector<DomTreeNode*, 8> Children(DTN->begin(), DTN->end()); 1766227d5c690504c7ada5780c00a635b282c46e275Craig Topper for (SmallVectorImpl<DomTreeNode *>::iterator DI = Children.begin(), 177b31b06d04b81c5383e2fba0cd44d4ba3f324a794Owen Anderson DE = Children.end(); DI != DE; ++DI) 17836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DT.changeImmediateDominator(*DI, PredDTN); 179b31b06d04b81c5383e2fba0cd44d4ba3f324a794Owen Anderson 18036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DT.eraseNode(BB); 181b31b06d04b81c5383e2fba0cd44d4ba3f324a794Owen Anderson } 182e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 183dc85f8ab808aec2f673262f5145eda58538cfb26Chris Lattner if (LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>()) 184dc85f8ab808aec2f673262f5145eda58538cfb26Chris Lattner LI->removeBlock(BB); 185e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 186b6810991a9648a40fe05162d744f42c3c178dba7Chris Lattner if (MemoryDependenceAnalysis *MD = 187b6810991a9648a40fe05162d744f42c3c178dba7Chris Lattner P->getAnalysisIfAvailable<MemoryDependenceAnalysis>()) 188b6810991a9648a40fe05162d744f42c3c178dba7Chris Lattner MD->invalidateCachedPredecessors(); 189b31b06d04b81c5383e2fba0cd44d4ba3f324a794Owen Anderson } 190b31b06d04b81c5383e2fba0cd44d4ba3f324a794Owen Anderson } 191e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 192b31b06d04b81c5383e2fba0cd44d4ba3f324a794Owen Anderson BB->eraseFromParent(); 193438b583dbd20f63b70d0b5abb7780a50bf03dd83Dan Gohman return true; 194b31b06d04b81c5383e2fba0cd44d4ba3f324a794Owen Anderson} 195b31b06d04b81c5383e2fba0cd44d4ba3f324a794Owen Anderson 1960f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) 1970f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// with a value, then remove and delete the original instruction. 1980f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// 199f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnervoid llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL, 200f7703df4968084c18c248c1feea9961c19a32e6aChris Lattner BasicBlock::iterator &BI, Value *V) { 20118961504fc2b299578dba817900a0696cf3ccc4dChris Lattner Instruction &I = *BI; 2024d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Replaces all of the uses of the instruction with uses of the value 20318961504fc2b299578dba817900a0696cf3ccc4dChris Lattner I.replaceAllUsesWith(V); 2044d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 20586cc42355593dd1689f7d58d56695c451215b02bChris Lattner // Make sure to propagate a name if there is one already. 20686cc42355593dd1689f7d58d56695c451215b02bChris Lattner if (I.hasName() && !V->hasName()) 20786cc42355593dd1689f7d58d56695c451215b02bChris Lattner V->takeName(&I); 208fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 2095560c9d49ccae132cabf1155f18aa0480dce3edaMisha Brukman // Delete the unnecessary instruction now... 21018961504fc2b299578dba817900a0696cf3ccc4dChris Lattner BI = BIL.erase(BI); 2114d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner} 2124d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 2134d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 2140f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// ReplaceInstWithInst - Replace the instruction specified by BI with the 2150f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// instruction specified by I. The original instruction is deleted and BI is 2160f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// updated to point to the new instruction. 2170f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// 218f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnervoid llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL, 219f7703df4968084c18c248c1feea9961c19a32e6aChris Lattner BasicBlock::iterator &BI, Instruction *I) { 220dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(I->getParent() == nullptr && 2214d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner "ReplaceInstWithInst: Instruction already inserted into basic block!"); 2224d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 2234d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Insert the new instruction into the basic block... 22418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner BasicBlock::iterator New = BIL.insert(BI, I); 2254d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 2264d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Replace all uses of the old instruction, and delete it. 2274d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner ReplaceInstWithValue(BIL, BI, I); 2284d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 2294d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Move BI back to point to the newly inserted instruction 23018961504fc2b299578dba817900a0696cf3ccc4dChris Lattner BI = New; 2314d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner} 2324d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 2330f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// ReplaceInstWithInst - Replace the instruction specified by From with the 2340f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// instruction specified by To. 2350f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// 236f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnervoid llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) { 23718961504fc2b299578dba817900a0696cf3ccc4dChris Lattner BasicBlock::iterator BI(From); 23818961504fc2b299578dba817900a0696cf3ccc4dChris Lattner ReplaceInstWithInst(From->getParent()->getInstList(), BI, To); 2394d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner} 240b0f0ef8f26eb8911ec1bb31380b5fe2d62e1c0ecChris Lattner 241e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak/// SplitEdge - Split the edge connecting specified block. Pass P must 242e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak/// not be NULL. 243adb6f226714dcfae363f51b453c4590b0f42da5eBob WilsonBasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, Pass *P) { 244ae23daf63afccd68be965ff4f7acafa818d76aaaBob Wilson unsigned SuccNum = GetSuccessorNumber(BB, Succ); 245e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 2468019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel // If this is a critical edge, let SplitCriticalEdge do it. 247adb6f226714dcfae363f51b453c4590b0f42da5eBob Wilson TerminatorInst *LatchTerm = BB->getTerminator(); 248adb6f226714dcfae363f51b453c4590b0f42da5eBob Wilson if (SplitCriticalEdge(LatchTerm, SuccNum, P)) 2498019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel return LatchTerm->getSuccessor(SuccNum); 2508019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel 2518019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel // If the edge isn't critical, then BB has a single successor or Succ has a 2528019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel // single pred. Split the block. 2538019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel if (BasicBlock *SP = Succ->getSinglePredecessor()) { 2548019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel // If the successor only has a single pred, split the top of the successor 2558019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel // block. 2568019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel assert(SP == BB && "CFG broken"); 257dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SP = nullptr; 2588019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel return SplitBlock(Succ, Succ->begin(), P); 2598019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel } 260e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 261b0433d4b2fb66922fa3625871840ccb72c8a9decChris Lattner // Otherwise, if BB has a single successor, split it at the bottom of the 262b0433d4b2fb66922fa3625871840ccb72c8a9decChris Lattner // block. 263b0433d4b2fb66922fa3625871840ccb72c8a9decChris Lattner assert(BB->getTerminator()->getNumSuccessors() == 1 && 264e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak "Should have a single succ!"); 265b0433d4b2fb66922fa3625871840ccb72c8a9decChris Lattner return SplitBlock(BB, BB->getTerminator(), P); 2668019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel} 2678019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel 2688019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel/// SplitBlock - Split the specified block at the specified instruction - every 2698019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel/// thing before SplitPt stays in Old and everything starting with SplitPt moves 2708019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel/// to a new block. The two blocks are joined by an unconditional branch and 2718019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel/// the loop info is updated. 2728019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel/// 2738019893c3f55a4bfe770888fe285d6dae57cf216Devang PatelBasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) { 2748019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel BasicBlock::iterator SplitIt = SplitPt; 275ab82fd9ff6874118594bc64bdafcadaa5b7fcb60Bill Wendling while (isa<PHINode>(SplitIt) || isa<LandingPadInst>(SplitIt)) 2768019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel ++SplitIt; 2778019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split"); 2788019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel 2795c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // The new block lives in whichever loop the old one did. This preserves 2805c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman // LCSSA as well, because we force the split point to be after any PHI nodes. 281dc85f8ab808aec2f673262f5145eda58538cfb26Chris Lattner if (LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>()) 282a90793b431458c1bac4c7267946738968c4cdf58Owen Anderson if (Loop *L = LI->getLoopFor(Old)) 283a90793b431458c1bac4c7267946738968c4cdf58Owen Anderson L->addBasicBlockToLoop(New, LI->getBase()); 2848019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel 28536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DominatorTreeWrapperPass *DTWP = 28636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines P->getAnalysisIfAvailable<DominatorTreeWrapperPass>()) { 28736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree &DT = DTWP->getDomTree(); 288e2d50046fd29cb3eb2483e080cb7c39b460fbb19Gabor Greif // Old dominates New. New node dominates all other nodes dominated by Old. 28936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DomTreeNode *OldNode = DT.getNode(Old)) { 290605e2b518445d86491e1a0c812f7c85193d3517aRafael Espindola std::vector<DomTreeNode *> Children; 291605e2b518445d86491e1a0c812f7c85193d3517aRafael Espindola for (DomTreeNode::iterator I = OldNode->begin(), E = OldNode->end(); 292e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak I != E; ++I) 293605e2b518445d86491e1a0c812f7c85193d3517aRafael Espindola Children.push_back(*I); 2940f1666b480f7ac55af09fdd5ff09c3df7c20e2e4Evan Cheng 29536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DomTreeNode *NewNode = DT.addNewBlock(New, Old); 296a8a8a366299863fe3711880add4c041c437b63cfDevang Patel for (std::vector<DomTreeNode *>::iterator I = Children.begin(), 297e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak E = Children.end(); I != E; ++I) 29836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DT.changeImmediateDominator(*I, NewNode); 299605e2b518445d86491e1a0c812f7c85193d3517aRafael Espindola } 3000f1666b480f7ac55af09fdd5ff09c3df7c20e2e4Evan Cheng } 3018019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel 3028019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel return New; 3038019893c3f55a4bfe770888fe285d6dae57cf216Devang Patel} 30454b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner 305a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling/// UpdateAnalysisInformation - Update DominatorTree, LoopInfo, and LCCSA 306a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling/// analysis information. 307d4770144d46992be0321d3cd4dc9315da1aa4d5dBill Wendlingstatic void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, 3089210e840ddd2358204281504e9d43a67c5b43219Bill Wendling ArrayRef<BasicBlock *> Preds, 3099210e840ddd2358204281504e9d43a67c5b43219Bill Wendling Pass *P, bool &HasLoopExit) { 310a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling if (!P) return; 311a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling 312a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>(); 313dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Loop *L = LI ? LI->getLoopFor(OldBB) : nullptr; 314a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling 315a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling // If we need to preserve loop analyses, collect some information about how 316a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling // this split will affect loops. 317a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling bool IsLoopEntry = !!L; 318a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling bool SplitMakesNewLoopHeader = false; 319a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling if (LI) { 3207e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling bool PreserveLCSSA = P->mustPreserveAnalysisID(LCSSAID); 3219210e840ddd2358204281504e9d43a67c5b43219Bill Wendling for (ArrayRef<BasicBlock*>::iterator 3229210e840ddd2358204281504e9d43a67c5b43219Bill Wendling i = Preds.begin(), e = Preds.end(); i != e; ++i) { 3239210e840ddd2358204281504e9d43a67c5b43219Bill Wendling BasicBlock *Pred = *i; 3247e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling 325a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling // If we need to preserve LCSSA, determine if any of the preds is a loop 326a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling // exit. 327a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling if (PreserveLCSSA) 3289210e840ddd2358204281504e9d43a67c5b43219Bill Wendling if (Loop *PL = LI->getLoopFor(Pred)) 329a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling if (!PL->contains(OldBB)) 330a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling HasLoopExit = true; 331a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling 332a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling // If we need to preserve LoopInfo, note whether any of the preds crosses 333a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling // an interesting loop boundary. 334a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling if (!L) continue; 3359210e840ddd2358204281504e9d43a67c5b43219Bill Wendling if (L->contains(Pred)) 336a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling IsLoopEntry = false; 337a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling else 338a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling SplitMakesNewLoopHeader = true; 339a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling } 340a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling } 341a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling 342a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling // Update dominator tree if available. 34336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DominatorTreeWrapperPass *DTWP = 34436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines P->getAnalysisIfAvailable<DominatorTreeWrapperPass>()) 34536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DTWP->getDomTree().splitBlock(NewBB); 346a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling 347a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling if (!L) return; 348a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling 349a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling if (IsLoopEntry) { 350a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling // Add the new block to the nearest enclosing loop (and not an adjacent 351a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling // loop). To find this, examine each of the predecessors and determine which 352a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling // loops enclose them, and select the most-nested loop which contains the 353a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling // loop containing the block being split. 354dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Loop *InnermostPredLoop = nullptr; 3559210e840ddd2358204281504e9d43a67c5b43219Bill Wendling for (ArrayRef<BasicBlock*>::iterator 3569210e840ddd2358204281504e9d43a67c5b43219Bill Wendling i = Preds.begin(), e = Preds.end(); i != e; ++i) { 3579210e840ddd2358204281504e9d43a67c5b43219Bill Wendling BasicBlock *Pred = *i; 3589210e840ddd2358204281504e9d43a67c5b43219Bill Wendling if (Loop *PredLoop = LI->getLoopFor(Pred)) { 359a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling // Seek a loop which actually contains the block being split (to avoid 360a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling // adjacent loops). 361a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling while (PredLoop && !PredLoop->contains(OldBB)) 362a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling PredLoop = PredLoop->getParentLoop(); 363a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling 364a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling // Select the most-nested of these loops which contains the block. 365a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling if (PredLoop && PredLoop->contains(OldBB) && 366a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling (!InnermostPredLoop || 367a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth())) 368a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling InnermostPredLoop = PredLoop; 369a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling } 3709210e840ddd2358204281504e9d43a67c5b43219Bill Wendling } 371a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling 372a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling if (InnermostPredLoop) 373a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling InnermostPredLoop->addBasicBlockToLoop(NewBB, LI->getBase()); 374a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling } else { 375a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling L->addBasicBlockToLoop(NewBB, LI->getBase()); 376a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling if (SplitMakesNewLoopHeader) 377a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling L->moveToHeader(NewBB); 378a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling } 379a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling} 380a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling 3811c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling/// UpdatePHINodes - Update the PHI nodes in OrigBB to include the values coming 3821c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling/// from NewBB. This also updates AliasAnalysis, if available. 3831c44d869cd920f3c2d7fdc9196677db202440089Bill Wendlingstatic void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB, 3841c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling ArrayRef<BasicBlock*> Preds, BranchInst *BI, 3851c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling Pass *P, bool HasLoopExit) { 3861c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB. 387dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AliasAnalysis *AA = P ? P->getAnalysisIfAvailable<AliasAnalysis>() : nullptr; 388dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end()); 3891c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) { 3901c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling PHINode *PN = cast<PHINode>(I++); 3911c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling 3921c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling // Check to see if all of the values coming in are the same. If so, we 3931c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling // don't need to create a new PHI node, unless it's needed for LCSSA. 394dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *InVal = nullptr; 3951c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling if (!HasLoopExit) { 3961c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling InVal = PN->getIncomingValueForBlock(Preds[0]); 397dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 398dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!PredSet.count(PN->getIncomingBlock(i))) 399dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 400dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!InVal) 401dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines InVal = PN->getIncomingValue(i); 402dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines else if (InVal != PN->getIncomingValue(i)) { 403dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines InVal = nullptr; 4041c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling break; 4051c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling } 406dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 4071c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling } 4081c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling 4091c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling if (InVal) { 4101c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling // If all incoming values for the new PHI would be the same, just don't 4111c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling // make a new PHI. Instead, just remove the incoming values from the old 4121c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling // PHI. 413e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 414dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // NOTE! This loop walks backwards for a reason! First off, this minimizes 415dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // the cost of removal if we end up removing a large number of values, and 416dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // second off, this ensures that the indices for the incoming values 417dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // aren't invalidated when we remove one. 418dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) 419dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (PredSet.count(PN->getIncomingBlock(i))) 420dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PN->removeIncomingValue(i, false); 421dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 422dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Add an incoming value to the PHI node in the loop for the preheader 423dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // edge. 424dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PN->addIncoming(InVal, NewBB); 425dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 426dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 4271c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling 428dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If the values coming into the block are not the same, we need a new 429dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // PHI. 430dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Create the new PHI node, insert it into NewBB at the end of the block 431dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PHINode *NewPHI = 432dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI); 433dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (AA) 434dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AA->copyValue(PN, NewPHI); 435dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 436dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // NOTE! This loop walks backwards for a reason! First off, this minimizes 437dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // the cost of removal if we end up removing a large number of values, and 438dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // second off, this ensures that the indices for the incoming values aren't 439dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // invalidated when we remove one. 440dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) { 441dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BasicBlock *IncomingBB = PN->getIncomingBlock(i); 442dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (PredSet.count(IncomingBB)) { 443dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *V = PN->removeIncomingValue(i, false); 444dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NewPHI->addIncoming(V, IncomingBB); 445dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 4461c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling } 4471c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling 448dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PN->addIncoming(NewPHI, NewBB); 4491c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling } 4501c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling} 4511c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling 45254b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner/// SplitBlockPredecessors - This method transforms BB by introducing a new 45354b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner/// basic block into the function, and moving some of the predecessors of BB to 45454b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner/// be predecessors of the new block. The new predecessors are indicated by the 45554b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner/// Preds array, which has NumPreds elements in it. The new block is given a 45654b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner/// suffix of 'Suffix'. 45754b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner/// 4585c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree, 459301278719b67dcdd1159d9f91b4db5ef57f025c6Cameron Zwarich/// LoopInfo, and LCCSA but no other analyses. In particular, it does not 460301278719b67dcdd1159d9f91b4db5ef57f025c6Cameron Zwarich/// preserve LoopSimplify (because it's complicated to handle the case where one 461301278719b67dcdd1159d9f91b4db5ef57f025c6Cameron Zwarich/// of the edges being split is an exit of a loop with other exits). 4625c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman/// 463e673b54bdde4b538cbd67eadac80a15d238c926fJakub StaszakBasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, 4642fac1d5d61a83c45dcf44119c41dce15ef10e9dcJakub Staszak ArrayRef<BasicBlock*> Preds, 4652fac1d5d61a83c45dcf44119c41dce15ef10e9dcJakub Staszak const char *Suffix, Pass *P) { 46654b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner // Create new basic block, insert right before the original block. 4671d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), BB->getName()+Suffix, 4681d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BB->getParent(), BB); 469e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 47054b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner // The new block unconditionally branches to the old block. 47154b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner BranchInst *BI = BranchInst::Create(BB, NewBB); 472e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 47354b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner // Move the edges from Preds to point to NewBB instead of BB. 4742fac1d5d61a83c45dcf44119c41dce15ef10e9dcJakub Staszak for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 475b8eb17c80793c33368e3c3af6de4bd8c1b09ba5bDan Gohman // This is slightly more strict than necessary; the minimum requirement 476b8eb17c80793c33368e3c3af6de4bd8c1b09ba5bDan Gohman // is that there be no more than one indirectbr branching to BB. And 477b8eb17c80793c33368e3c3af6de4bd8c1b09ba5bDan Gohman // all BlockAddress uses would need to be updated. 478b8eb17c80793c33368e3c3af6de4bd8c1b09ba5bDan Gohman assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) && 479b8eb17c80793c33368e3c3af6de4bd8c1b09ba5bDan Gohman "Cannot split an edge from an IndirectBrInst"); 48054b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB); 4815c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman } 4825c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman 48354b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI 48454b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner // node becomes an incoming value for BB's phi node. However, if the Preds 48554b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner // list is empty, we need to insert dummy entries into the PHI nodes in BB to 48654b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner // account for the newly created predecessor. 4872fac1d5d61a83c45dcf44119c41dce15ef10e9dcJakub Staszak if (Preds.size() == 0) { 48854b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner // Insert dummy values as the incoming value. 48954b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) 4909e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB); 49154b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner return NewBB; 49254b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner } 4935c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman 494a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling // Update DominatorTree, LoopInfo, and LCCSA analysis information. 495a644b33e8b9a45044dc531cfc1aac95fe7930605Bill Wendling bool HasLoopExit = false; 4962fac1d5d61a83c45dcf44119c41dce15ef10e9dcJakub Staszak UpdateAnalysisInformation(BB, NewBB, Preds, P, HasLoopExit); 4975c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman 4981c44d869cd920f3c2d7fdc9196677db202440089Bill Wendling // Update the PHI nodes in BB with the values coming from NewBB. 4992fac1d5d61a83c45dcf44119c41dce15ef10e9dcJakub Staszak UpdatePHINodes(BB, NewBB, Preds, BI, P, HasLoopExit); 50054b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner return NewBB; 50154b9c3ba2a5b0aa8fda817bcc72c370040cfb3f8Chris Lattner} 50252c95856b4a40ccae6c4b0e13b2a04101e1f79c9Chris Lattner 5037e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling/// SplitLandingPadPredecessors - This method transforms the landing pad, 5047e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling/// OrigBB, by introducing two new basic blocks into the function. One of those 5057e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling/// new basic blocks gets the predecessors listed in Preds. The other basic 5067e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling/// block gets the remaining predecessors of OrigBB. The landingpad instruction 5077e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling/// OrigBB is clone into both of the new basic blocks. The new blocks are given 5087e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling/// the suffixes 'Suffix1' and 'Suffix2', and are returned in the NewBBs vector. 509e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak/// 5107e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree, 5117e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling/// DominanceFrontier, LoopInfo, and LCCSA but no other analyses. In particular, 5127e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling/// it does not preserve LoopSimplify (because it's complicated to handle the 5137e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling/// case where one of the edges being split is an exit of a loop with other 5147e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling/// exits). 515e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak/// 5167e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendlingvoid llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, 5177e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling ArrayRef<BasicBlock*> Preds, 5187e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling const char *Suffix1, const char *Suffix2, 5197e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling Pass *P, 5207e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling SmallVectorImpl<BasicBlock*> &NewBBs) { 5217e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!"); 5227e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling 5237e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling // Create a new basic block for OrigBB's predecessors listed in Preds. Insert 5247e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling // it right before the original block. 5257e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(), 5267e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling OrigBB->getName() + Suffix1, 5277e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling OrigBB->getParent(), OrigBB); 5287e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling NewBBs.push_back(NewBB1); 5297e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling 5307e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling // The new block unconditionally branches to the old block. 5317e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1); 5327e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling 5337e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling // Move the edges from Preds to point to NewBB1 instead of OrigBB. 5347e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 5357e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling // This is slightly more strict than necessary; the minimum requirement 5367e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling // is that there be no more than one indirectbr branching to BB. And 5377e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling // all BlockAddress uses would need to be updated. 5387e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) && 5397e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling "Cannot split an edge from an IndirectBrInst"); 5407e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1); 5417e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling } 5427e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling 5437e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling // Update DominatorTree, LoopInfo, and LCCSA analysis information. 5447e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling bool HasLoopExit = false; 5457e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling UpdateAnalysisInformation(OrigBB, NewBB1, Preds, P, HasLoopExit); 5467e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling 5477e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling // Update the PHI nodes in OrigBB with the values coming from NewBB1. 5487e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, P, HasLoopExit); 5497e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling 5507e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling // Move the remaining edges from OrigBB to point to NewBB2. 5517e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling SmallVector<BasicBlock*, 8> NewBB2Preds; 5527e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB); 5537e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling i != e; ) { 5547e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling BasicBlock *Pred = *i++; 55594657b964f90107989c61a63a214451c03922649Bill Wendling if (Pred == NewBB1) continue; 5567e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling assert(!isa<IndirectBrInst>(Pred->getTerminator()) && 5577e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling "Cannot split an edge from an IndirectBrInst"); 5587e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling NewBB2Preds.push_back(Pred); 5597e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling e = pred_end(OrigBB); 5607e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling } 5617e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling 562dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BasicBlock *NewBB2 = nullptr; 56394657b964f90107989c61a63a214451c03922649Bill Wendling if (!NewBB2Preds.empty()) { 56494657b964f90107989c61a63a214451c03922649Bill Wendling // Create another basic block for the rest of OrigBB's predecessors. 56594657b964f90107989c61a63a214451c03922649Bill Wendling NewBB2 = BasicBlock::Create(OrigBB->getContext(), 56694657b964f90107989c61a63a214451c03922649Bill Wendling OrigBB->getName() + Suffix2, 56794657b964f90107989c61a63a214451c03922649Bill Wendling OrigBB->getParent(), OrigBB); 56894657b964f90107989c61a63a214451c03922649Bill Wendling NewBBs.push_back(NewBB2); 56994657b964f90107989c61a63a214451c03922649Bill Wendling 57094657b964f90107989c61a63a214451c03922649Bill Wendling // The new block unconditionally branches to the old block. 57194657b964f90107989c61a63a214451c03922649Bill Wendling BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2); 5727e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling 57394657b964f90107989c61a63a214451c03922649Bill Wendling // Move the remaining edges from OrigBB to point to NewBB2. 57494657b964f90107989c61a63a214451c03922649Bill Wendling for (SmallVectorImpl<BasicBlock*>::iterator 57594657b964f90107989c61a63a214451c03922649Bill Wendling i = NewBB2Preds.begin(), e = NewBB2Preds.end(); i != e; ++i) 57694657b964f90107989c61a63a214451c03922649Bill Wendling (*i)->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2); 57794657b964f90107989c61a63a214451c03922649Bill Wendling 57894657b964f90107989c61a63a214451c03922649Bill Wendling // Update DominatorTree, LoopInfo, and LCCSA analysis information. 57994657b964f90107989c61a63a214451c03922649Bill Wendling HasLoopExit = false; 58094657b964f90107989c61a63a214451c03922649Bill Wendling UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, P, HasLoopExit); 58194657b964f90107989c61a63a214451c03922649Bill Wendling 58294657b964f90107989c61a63a214451c03922649Bill Wendling // Update the PHI nodes in OrigBB with the values coming from NewBB2. 58394657b964f90107989c61a63a214451c03922649Bill Wendling UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, P, HasLoopExit); 58494657b964f90107989c61a63a214451c03922649Bill Wendling } 5857e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling 5867e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling LandingPadInst *LPad = OrigBB->getLandingPadInst(); 5877e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling Instruction *Clone1 = LPad->clone(); 5887e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling Clone1->setName(Twine("lpad") + Suffix1); 5897e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling NewBB1->getInstList().insert(NewBB1->getFirstInsertionPt(), Clone1); 5907e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling 59194657b964f90107989c61a63a214451c03922649Bill Wendling if (NewBB2) { 59294657b964f90107989c61a63a214451c03922649Bill Wendling Instruction *Clone2 = LPad->clone(); 59394657b964f90107989c61a63a214451c03922649Bill Wendling Clone2->setName(Twine("lpad") + Suffix2); 59494657b964f90107989c61a63a214451c03922649Bill Wendling NewBB2->getInstList().insert(NewBB2->getFirstInsertionPt(), Clone2); 59594657b964f90107989c61a63a214451c03922649Bill Wendling 59694657b964f90107989c61a63a214451c03922649Bill Wendling // Create a PHI node for the two cloned landingpad instructions. 59794657b964f90107989c61a63a214451c03922649Bill Wendling PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad); 59894657b964f90107989c61a63a214451c03922649Bill Wendling PN->addIncoming(Clone1, NewBB1); 59994657b964f90107989c61a63a214451c03922649Bill Wendling PN->addIncoming(Clone2, NewBB2); 60094657b964f90107989c61a63a214451c03922649Bill Wendling LPad->replaceAllUsesWith(PN); 60194657b964f90107989c61a63a214451c03922649Bill Wendling LPad->eraseFromParent(); 60294657b964f90107989c61a63a214451c03922649Bill Wendling } else { 60394657b964f90107989c61a63a214451c03922649Bill Wendling // There is no second clone. Just replace the landing pad with the first 60494657b964f90107989c61a63a214451c03922649Bill Wendling // clone. 60594657b964f90107989c61a63a214451c03922649Bill Wendling LPad->replaceAllUsesWith(Clone1); 60694657b964f90107989c61a63a214451c03922649Bill Wendling LPad->eraseFromParent(); 60794657b964f90107989c61a63a214451c03922649Bill Wendling } 6087e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling} 6097e8840c4d9ac7cc259fd967d9fe7540740d1ce92Bill Wendling 610c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng/// FoldReturnIntoUncondBranch - This method duplicates the specified return 611c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng/// instruction into a predecessor which ends in an unconditional branch. If 612c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng/// the return instruction returns a value defined by a PHI, propagate the 613c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng/// right value into the return. It returns the new return instruction in the 614c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng/// predecessor. 615c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan ChengReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, 616c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng BasicBlock *Pred) { 617c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng Instruction *UncondBranch = Pred->getTerminator(); 618c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng // Clone the return and add it to the end of the predecessor. 619c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng Instruction *NewRet = RI->clone(); 620c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng Pred->getInstList().push_back(NewRet); 621e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 622c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng // If the return instruction returns a value, and if the value was a 623c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng // PHI node in "BB", propagate the right value into the return. 624c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end(); 6259c777a484415198b3fb0dbeb57a594573b245152Evan Cheng i != e; ++i) { 6269c777a484415198b3fb0dbeb57a594573b245152Evan Cheng Value *V = *i; 627dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Instruction *NewBC = nullptr; 6289c777a484415198b3fb0dbeb57a594573b245152Evan Cheng if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) { 6299c777a484415198b3fb0dbeb57a594573b245152Evan Cheng // Return value might be bitcasted. Clone and insert it before the 6309c777a484415198b3fb0dbeb57a594573b245152Evan Cheng // return instruction. 6319c777a484415198b3fb0dbeb57a594573b245152Evan Cheng V = BCI->getOperand(0); 6329c777a484415198b3fb0dbeb57a594573b245152Evan Cheng NewBC = BCI->clone(); 6339c777a484415198b3fb0dbeb57a594573b245152Evan Cheng Pred->getInstList().insert(NewRet, NewBC); 6349c777a484415198b3fb0dbeb57a594573b245152Evan Cheng *i = NewBC; 6359c777a484415198b3fb0dbeb57a594573b245152Evan Cheng } 6369c777a484415198b3fb0dbeb57a594573b245152Evan Cheng if (PHINode *PN = dyn_cast<PHINode>(V)) { 6379c777a484415198b3fb0dbeb57a594573b245152Evan Cheng if (PN->getParent() == BB) { 6389c777a484415198b3fb0dbeb57a594573b245152Evan Cheng if (NewBC) 6399c777a484415198b3fb0dbeb57a594573b245152Evan Cheng NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred)); 6409c777a484415198b3fb0dbeb57a594573b245152Evan Cheng else 6419c777a484415198b3fb0dbeb57a594573b245152Evan Cheng *i = PN->getIncomingValueForBlock(Pred); 6429c777a484415198b3fb0dbeb57a594573b245152Evan Cheng } 6439c777a484415198b3fb0dbeb57a594573b245152Evan Cheng } 6449c777a484415198b3fb0dbeb57a594573b245152Evan Cheng } 645e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 646c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng // Update any PHI nodes in the returning block to realize that we no 647c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng // longer branch to them. 648c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng BB->removePredecessor(Pred); 649c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng UncondBranch->eraseFromParent(); 650c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng return cast<ReturnInst>(NewRet); 651fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump} 65240348e8d1ff564a23101d4fd37fe4dd03d9018abDevang Patel 6534a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov/// SplitBlockAndInsertIfThen - Split the containing block at the 65436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// specified instruction - everything before and including SplitBefore stays 65536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// in the old basic block, and everything after SplitBefore is moved to a 6564a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov/// new block. The two blocks are connected by a conditional branch 6574a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov/// (with value of Cmp being the condition). 6584a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov/// Before: 6594a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov/// Head 66036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// SplitBefore 6614a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov/// Tail 6624a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov/// After: 6634a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov/// Head 66436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// if (Cond) 6654a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov/// ThenBlock 66636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// SplitBefore 6674a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov/// Tail 6684a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov/// 6694a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov/// If Unreachable is true, then ThenBlock ends with 6704a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov/// UnreachableInst, otherwise it branches to Tail. 6714a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov/// Returns the NewBasicBlock's terminator. 6724a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov 67336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesTerminatorInst *llvm::SplitBlockAndInsertIfThen(Value *Cond, 67436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *SplitBefore, 67536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool Unreachable, 67636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MDNode *BranchWeights) { 6774a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov BasicBlock *Head = SplitBefore->getParent(); 6784a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov BasicBlock *Tail = Head->splitBasicBlock(SplitBefore); 6794a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov TerminatorInst *HeadOldTerm = Head->getTerminator(); 6804a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov LLVMContext &C = Head->getContext(); 6814a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail); 6824a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov TerminatorInst *CheckTerm; 6834a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov if (Unreachable) 6844a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov CheckTerm = new UnreachableInst(C, ThenBlock); 6854a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov else 6864a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov CheckTerm = BranchInst::Create(Tail, ThenBlock); 68736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CheckTerm->setDebugLoc(SplitBefore->getDebugLoc()); 6884a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov BranchInst *HeadNewTerm = 68936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/Tail, Cond); 69036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines HeadNewTerm->setDebugLoc(SplitBefore->getDebugLoc()); 6914a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights); 6924a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov ReplaceInstWithInst(HeadOldTerm, HeadNewTerm); 6934a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov return CheckTerm; 6944a2dec05cef5882b745dd248d79e42a42cdbc87bEvgeniy Stepanov} 69501d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 69636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, 69736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// but also creates the ElseBlock. 69836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Before: 69936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Head 70036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// SplitBefore 70136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Tail 70236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// After: 70336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Head 70436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// if (Cond) 70536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// ThenBlock 70636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// else 70736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// ElseBlock 70836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// SplitBefore 70936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Tail 71036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid llvm::SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, 71136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines TerminatorInst **ThenTerm, 71236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines TerminatorInst **ElseTerm, 71336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MDNode *BranchWeights) { 71436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *Head = SplitBefore->getParent(); 71536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *Tail = Head->splitBasicBlock(SplitBefore); 71636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines TerminatorInst *HeadOldTerm = Head->getTerminator(); 71736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LLVMContext &C = Head->getContext(); 71836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail); 71936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail); 72036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines *ThenTerm = BranchInst::Create(Tail, ThenBlock); 72136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc()); 72236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines *ElseTerm = BranchInst::Create(Tail, ElseBlock); 72336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc()); 72436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BranchInst *HeadNewTerm = 72536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond); 72636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines HeadNewTerm->setDebugLoc(SplitBefore->getDebugLoc()); 72736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights); 72836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ReplaceInstWithInst(HeadOldTerm, HeadNewTerm); 72936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 73036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 73136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 73201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard/// GetIfCondition - Given a basic block (BB) with two predecessors, 73301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard/// check to see if the merge at this block is due 73401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard/// to an "if condition". If so, return the boolean condition that determines 73501d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard/// which entry into BB will be taken. Also, return by references the block 73601d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard/// that will be entered from if the condition is true, and the block that will 73701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard/// be entered if the condition is false. 73801d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard/// 73901d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard/// This does no checking to see if the true/false blocks have large or unsavory 74001d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard/// instructions in them. 74101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom StellardValue *llvm::GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, 74201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard BasicBlock *&IfFalse) { 74301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard PHINode *SomePHI = dyn_cast<PHINode>(BB->begin()); 744dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BasicBlock *Pred1 = nullptr; 745dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BasicBlock *Pred2 = nullptr; 74601d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 74701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard if (SomePHI) { 74801d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard if (SomePHI->getNumIncomingValues() != 2) 749dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 75001d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard Pred1 = SomePHI->getIncomingBlock(0); 75101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard Pred2 = SomePHI->getIncomingBlock(1); 75201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard } else { 75301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 75401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard if (PI == PE) // No predecessor 755dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 75601d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard Pred1 = *PI++; 75701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard if (PI == PE) // Only one predecessor 758dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 75901d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard Pred2 = *PI++; 76001d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard if (PI != PE) // More than two predecessors 761dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 76201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard } 76301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 76401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // We can only handle branches. Other control flow will be lowered to 76501d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // branches if possible anyway. 76601d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator()); 76701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator()); 768dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Pred1Br || !Pred2Br) 769dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 77001d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 77101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // Eliminate code duplication by ensuring that Pred1Br is conditional if 77201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // either are. 77301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard if (Pred2Br->isConditional()) { 77401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // If both branches are conditional, we don't have an "if statement". In 77501d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // reality, we could transform this case, but since the condition will be 77601d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // required anyway, we stand no chance of eliminating it, so the xform is 77701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // probably not profitable. 77801d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard if (Pred1Br->isConditional()) 779dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 78001d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 78101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard std::swap(Pred1, Pred2); 78201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard std::swap(Pred1Br, Pred2Br); 78301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard } 78401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 78501d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard if (Pred1Br->isConditional()) { 78601d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // The only thing we have to watch out for here is to make sure that Pred2 78701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // doesn't have incoming edges from other blocks. If it does, the condition 78801d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // doesn't dominate BB. 789dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Pred2->getSinglePredecessor()) 790dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 79101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 79201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // If we found a conditional branch predecessor, make sure that it branches 79301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 79401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard if (Pred1Br->getSuccessor(0) == BB && 79501d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard Pred1Br->getSuccessor(1) == Pred2) { 79601d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard IfTrue = Pred1; 79701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard IfFalse = Pred2; 79801d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard } else if (Pred1Br->getSuccessor(0) == Pred2 && 79901d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard Pred1Br->getSuccessor(1) == BB) { 80001d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard IfTrue = Pred2; 80101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard IfFalse = Pred1; 80201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard } else { 80301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // We know that one arm of the conditional goes to BB, so the other must 80401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // go somewhere unrelated, and this must not be an "if statement". 805dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 80601d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard } 80701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 80801d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard return Pred1Br->getCondition(); 80901d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard } 81001d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 81101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // Ok, if we got here, both predecessors end with an unconditional branch to 81201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // BB. Don't panic! If both blocks only have a single (identical) 81301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // predecessor, and THAT is a conditional branch, then we're all ok! 81401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard BasicBlock *CommonPred = Pred1->getSinglePredecessor(); 815dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor()) 816dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 81701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 81801d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // Otherwise, if this is a conditional branch, then we can use it! 81901d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator()); 820dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!BI) return nullptr; 82101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 82201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard assert(BI->isConditional() && "Two successors but not conditional?"); 82301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard if (BI->getSuccessor(0) == Pred1) { 82401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard IfTrue = Pred1; 82501d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard IfFalse = Pred2; 82601d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard } else { 82701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard IfTrue = Pred2; 82801d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard IfFalse = Pred1; 82901d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard } 83001d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard return BI->getCondition(); 83101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard} 832