1d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner//===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===// 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//===----------------------------------------------------------------------===// 9009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 10b7653df0853f06112b741be09f1b7ae5a6aa6fdeChris Lattner// This file implements the BasicBlock class for the VMCore library. 11009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 12009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner//===----------------------------------------------------------------------===// 13009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 140a4fd1ab7e7c83b3ecf03cbd6b35d2b164995267Gabor Greif#include "llvm/BasicBlock.h" 153464547968b58dda0acbf6e0e192f03f66652848Chris Lattner#include "llvm/Constants.h" 1644336292fcd9f3f99cbfc2c3366bea0cf95bb675Misha Brukman#include "llvm/Instructions.h" 177249ef04557cc6f9af7b6df93728683be3b65048Dale Johannesen#include "llvm/IntrinsicInst.h" 18f81b57694b3c34a79b1464ffd21e6768c8d22662Owen Anderson#include "llvm/LLVMContext.h" 19009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#include "llvm/Type.h" 20fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman#include "llvm/ADT/STLExtras.h" 21455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner#include "llvm/Support/CFG.h" 22551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/LeakDetector.h" 237e70829632f82de15db187845666aaca6e04b792Chris Lattner#include "SymbolTableListTraitsImpl.h" 247e70829632f82de15db187845666aaca6e04b792Chris Lattner#include <algorithm> 25108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattnerusing namespace llvm; 26108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner 270dd2a6a89f49438b239638ab147ac5746d6c32c3Gabor GreifValueSymbolTable *BasicBlock::getValueSymbolTable() { 280dd2a6a89f49438b239638ab147ac5746d6c32c3Gabor Greif if (Function *F = getParent()) 290dd2a6a89f49438b239638ab147ac5746d6c32c3Gabor Greif return &F->getValueSymbolTable(); 3017fcdd5e1b78b829068ca657c97357a39d6e768bChris Lattner return 0; 3117fcdd5e1b78b829068ca657c97357a39d6e768bChris Lattner} 3217fcdd5e1b78b829068ca657c97357a39d6e768bChris Lattner 33e922c0201916e0b980ab3cfe91e1413e68d55647Owen AndersonLLVMContext &BasicBlock::getContext() const { 34e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson return getType()->getContext(); 350a205a459884ec745df1c529396dd921f029dafdOwen Anderson} 360a205a459884ec745df1c529396dd921f029dafdOwen Anderson 377e70829632f82de15db187845666aaca6e04b792Chris Lattner// Explicit instantiation of SymbolTableListTraits since some of the methods 387e70829632f82de15db187845666aaca6e04b792Chris Lattner// are not in the public header file... 39c63ca0a71b299ee0b8fc7dc8405d7f3c856ecfa3John McCalltemplate class llvm::SymbolTableListTraits<Instruction, BasicBlock>; 407e70829632f82de15db187845666aaca6e04b792Chris Lattner 415d7a5a4f53304869ae5b76771ab67213447b65a5Bill Wendling 421d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen AndersonBasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent, 43280a6e607d8eb7401749a92db624a82de47da777Nick Lewycky BasicBlock *InsertBefore) 445d7a5a4f53304869ae5b76771ab67213447b65a5Bill Wendling : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(0) { 450a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner 460a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner // Make sure that we get added to a function 470a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner LeakDetector::addGarbageObject(this); 480a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner 490a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner if (InsertBefore) { 5017fcdd5e1b78b829068ca657c97357a39d6e768bChris Lattner assert(NewParent && 514f05611ed948ed1fb3e861d178aae18bd025ce1cChris Lattner "Cannot insert block before another block with no function!"); 5217fcdd5e1b78b829068ca657c97357a39d6e768bChris Lattner NewParent->getBasicBlockList().insert(InsertBefore, this); 5317fcdd5e1b78b829068ca657c97357a39d6e768bChris Lattner } else if (NewParent) { 5417fcdd5e1b78b829068ca657c97357a39d6e768bChris Lattner NewParent->getBasicBlockList().push_back(this); 550a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner } 568fc9b3db536f1523263e8b380899fb4d7df23ce1NAKAMURA Takumi 57dec628eead87b20773c98a00830580df211acc98Chris Lattner setName(Name); 580a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner} 590a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner 605d7a5a4f53304869ae5b76771ab67213447b65a5Bill Wendling 61afba8fe662d65b25b4baf46bb26cc18e1f9cc0a5Gordon HenriksenBasicBlock::~BasicBlock() { 62dac8bde235b92b28202fe64ada3695aedbb8bf6dChris Lattner // If the address of the block is taken and it is being deleted (e.g. because 63dac8bde235b92b28202fe64ada3695aedbb8bf6dChris Lattner // it is dead), this means that there is either a dangling constant expr 64dac8bde235b92b28202fe64ada3695aedbb8bf6dChris Lattner // hanging off the block, or an undefined use of the block (source code 65dac8bde235b92b28202fe64ada3695aedbb8bf6dChris Lattner // expecting the address of a label to keep the block alive even though there 66dac8bde235b92b28202fe64ada3695aedbb8bf6dChris Lattner // is no indirect branch). Handle these cases by zapping the BlockAddress 67cdfc940912d56a63b6f12eaa7f3faf79cf74c693Chris Lattner // nodes. There are no other possible uses at this point. 68dac8bde235b92b28202fe64ada3695aedbb8bf6dChris Lattner if (hasAddressTaken()) { 69dac8bde235b92b28202fe64ada3695aedbb8bf6dChris Lattner assert(!use_empty() && "There should be at least one blockaddress!"); 70cdfc940912d56a63b6f12eaa7f3faf79cf74c693Chris Lattner Constant *Replacement = 71cdfc940912d56a63b6f12eaa7f3faf79cf74c693Chris Lattner ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1); 72dac8bde235b92b28202fe64ada3695aedbb8bf6dChris Lattner while (!use_empty()) { 73dac8bde235b92b28202fe64ada3695aedbb8bf6dChris Lattner BlockAddress *BA = cast<BlockAddress>(use_back()); 74cdfc940912d56a63b6f12eaa7f3faf79cf74c693Chris Lattner BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement, 75cdfc940912d56a63b6f12eaa7f3faf79cf74c693Chris Lattner BA->getType())); 76dac8bde235b92b28202fe64ada3695aedbb8bf6dChris Lattner BA->destroyConstant(); 77dac8bde235b92b28202fe64ada3695aedbb8bf6dChris Lattner } 78dac8bde235b92b28202fe64ada3695aedbb8bf6dChris Lattner } 798fc9b3db536f1523263e8b380899fb4d7df23ce1NAKAMURA Takumi 80afba8fe662d65b25b4baf46bb26cc18e1f9cc0a5Gordon Henriksen assert(getParent() == 0 && "BasicBlock still linked into the program!"); 81afba8fe662d65b25b4baf46bb26cc18e1f9cc0a5Gordon Henriksen dropAllReferences(); 82afba8fe662d65b25b4baf46bb26cc18e1f9cc0a5Gordon Henriksen InstList.clear(); 83009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 84009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 85bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattnervoid BasicBlock::setParent(Function *parent) { 86d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner if (getParent()) 87d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner LeakDetector::addGarbageObject(this); 88d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner 8917fcdd5e1b78b829068ca657c97357a39d6e768bChris Lattner // Set Parent=parent, updating instruction symtab entries as appropriate. 9017fcdd5e1b78b829068ca657c97357a39d6e768bChris Lattner InstList.setSymTabObject(&Parent, parent); 91d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner 92d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner if (getParent()) 93d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner LeakDetector::removeGarbageObject(this); 94bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattner} 95bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattner 964b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattnervoid BasicBlock::removeFromParent() { 974b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattner getParent()->getBasicBlockList().remove(this); 984b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattner} 994b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattner 1004b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattnervoid BasicBlock::eraseFromParent() { 1014b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattner getParent()->getBasicBlockList().erase(this); 1024b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattner} 1034b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattner 104a71965b1adf6bfeddfd3b38fdf7df9b4412bc6c2Chris Lattner/// moveBefore - Unlink this basic block from its current function and 105a71965b1adf6bfeddfd3b38fdf7df9b4412bc6c2Chris Lattner/// insert it into the function that MovePos lives in, right before MovePos. 1066a13aed525f586fc8f475ce17ce7f6cf77ddd2f4Chris Lattnervoid BasicBlock::moveBefore(BasicBlock *MovePos) { 1076a13aed525f586fc8f475ce17ce7f6cf77ddd2f4Chris Lattner MovePos->getParent()->getBasicBlockList().splice(MovePos, 1086a13aed525f586fc8f475ce17ce7f6cf77ddd2f4Chris Lattner getParent()->getBasicBlockList(), this); 1096a13aed525f586fc8f475ce17ce7f6cf77ddd2f4Chris Lattner} 1106a13aed525f586fc8f475ce17ce7f6cf77ddd2f4Chris Lattner 111a71965b1adf6bfeddfd3b38fdf7df9b4412bc6c2Chris Lattner/// moveAfter - Unlink this basic block from its current function and 112a71965b1adf6bfeddfd3b38fdf7df9b4412bc6c2Chris Lattner/// insert it into the function that MovePos lives in, right after MovePos. 113a71965b1adf6bfeddfd3b38fdf7df9b4412bc6c2Chris Lattnervoid BasicBlock::moveAfter(BasicBlock *MovePos) { 114a71965b1adf6bfeddfd3b38fdf7df9b4412bc6c2Chris Lattner Function::iterator I = MovePos; 115a71965b1adf6bfeddfd3b38fdf7df9b4412bc6c2Chris Lattner MovePos->getParent()->getBasicBlockList().splice(++I, 116a71965b1adf6bfeddfd3b38fdf7df9b4412bc6c2Chris Lattner getParent()->getBasicBlockList(), this); 117a71965b1adf6bfeddfd3b38fdf7df9b4412bc6c2Chris Lattner} 118a71965b1adf6bfeddfd3b38fdf7df9b4412bc6c2Chris Lattner 1194b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattner 120009505452b713ed2e3a8e99c5545a6e721c65495Chris LattnerTerminatorInst *BasicBlock::getTerminator() { 121009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (InstList.empty()) return 0; 1227e70829632f82de15db187845666aaca6e04b792Chris Lattner return dyn_cast<TerminatorInst>(&InstList.back()); 123009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 124009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 12550cdabcfd52e88381ade61450d98a1c757195befDan Gohmanconst TerminatorInst *BasicBlock::getTerminator() const { 126009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (InstList.empty()) return 0; 1277e70829632f82de15db187845666aaca6e04b792Chris Lattner return dyn_cast<TerminatorInst>(&InstList.back()); 128009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 129009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 13002dea8b39f3acad5de1df36273444d149145e7fcDan GohmanInstruction* BasicBlock::getFirstNonPHI() { 13102dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator i = begin(); 13202dea8b39f3acad5de1df36273444d149145e7fcDan Gohman // All valid basic blocks should have a terminator, 13302dea8b39f3acad5de1df36273444d149145e7fcDan Gohman // which is not a PHINode. If we have an invalid basic 13402dea8b39f3acad5de1df36273444d149145e7fcDan Gohman // block we'll get an assertion failure when dereferencing 13502dea8b39f3acad5de1df36273444d149145e7fcDan Gohman // a past-the-end iterator. 13602dea8b39f3acad5de1df36273444d149145e7fcDan Gohman while (isa<PHINode>(i)) ++i; 13702dea8b39f3acad5de1df36273444d149145e7fcDan Gohman return &*i; 138dd49dbfe44098eb53b1ac29f017e422147572bbbVladimir Prus} 139dd49dbfe44098eb53b1ac29f017e422147572bbbVladimir Prus 1407249ef04557cc6f9af7b6df93728683be3b65048Dale JohannesenInstruction* BasicBlock::getFirstNonPHIOrDbg() { 1417249ef04557cc6f9af7b6df93728683be3b65048Dale Johannesen BasicBlock::iterator i = begin(); 1427249ef04557cc6f9af7b6df93728683be3b65048Dale Johannesen // All valid basic blocks should have a terminator, 1437249ef04557cc6f9af7b6df93728683be3b65048Dale Johannesen // which is not a PHINode. If we have an invalid basic 1447249ef04557cc6f9af7b6df93728683be3b65048Dale Johannesen // block we'll get an assertion failure when dereferencing 1457249ef04557cc6f9af7b6df93728683be3b65048Dale Johannesen // a past-the-end iterator. 1467249ef04557cc6f9af7b6df93728683be3b65048Dale Johannesen while (isa<PHINode>(i) || isa<DbgInfoIntrinsic>(i)) ++i; 1477249ef04557cc6f9af7b6df93728683be3b65048Dale Johannesen return &*i; 1487249ef04557cc6f9af7b6df93728683be3b65048Dale Johannesen} 1497249ef04557cc6f9af7b6df93728683be3b65048Dale Johannesen 15077a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael EspindolaInstruction* BasicBlock::getFirstNonPHIOrDbgOrLifetime() { 15177a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola // All valid basic blocks should have a terminator, 15277a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola // which is not a PHINode. If we have an invalid basic 15377a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola // block we'll get an assertion failure when dereferencing 15477a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola // a past-the-end iterator. 15577a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola BasicBlock::iterator i = begin(); 15677a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola for (;; ++i) { 15777a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola if (isa<PHINode>(i) || isa<DbgInfoIntrinsic>(i)) 15877a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola continue; 15977a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola 16077a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola const IntrinsicInst *II = dyn_cast<IntrinsicInst>(i); 16177a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola if (!II) 16277a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola break; 16377a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola if (II->getIntrinsicID() != Intrinsic::lifetime_start && 16477a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola II->getIntrinsicID() != Intrinsic::lifetime_end) 16577a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola break; 16677a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola } 16777a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola return &*i; 16877a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola} 16977a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola 170d2e103daf8a093e0e25ddbaa7549c083887196e8Bill WendlingBasicBlock::iterator BasicBlock::getFirstInsertionPt() { 171d2e103daf8a093e0e25ddbaa7549c083887196e8Bill Wendling iterator InsertPt = getFirstNonPHI(); 172d2e103daf8a093e0e25ddbaa7549c083887196e8Bill Wendling if (isa<LandingPadInst>(InsertPt)) ++InsertPt; 173d2e103daf8a093e0e25ddbaa7549c083887196e8Bill Wendling return InsertPt; 174d2e103daf8a093e0e25ddbaa7549c083887196e8Bill Wendling} 175d2e103daf8a093e0e25ddbaa7549c083887196e8Bill Wendling 176009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattnervoid BasicBlock::dropAllReferences() { 1777e70829632f82de15db187845666aaca6e04b792Chris Lattner for(iterator I = begin(), E = end(); I != E; ++I) 1787e70829632f82de15db187845666aaca6e04b792Chris Lattner I->dropAllReferences(); 179009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 180009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 181ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner/// getSinglePredecessor - If this basic block has a single predecessor block, 182ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner/// return the block, otherwise return a null pointer. 183ad993cbb77b26b36cee938686b3377c0d92abd5eChris LattnerBasicBlock *BasicBlock::getSinglePredecessor() { 184ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner pred_iterator PI = pred_begin(this), E = pred_end(this); 185ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner if (PI == E) return 0; // No preds. 186ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner BasicBlock *ThePred = *PI; 187ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner ++PI; 188ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner return (PI == E) ? ThePred : 0 /*multiple preds*/; 189ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner} 190ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner 19187f1e7796d02ea991bdbf084f312879988732a26Torok Edwin/// getUniquePredecessor - If this basic block has a unique predecessor block, 19287f1e7796d02ea991bdbf084f312879988732a26Torok Edwin/// return the block, otherwise return a null pointer. 1938fc9b3db536f1523263e8b380899fb4d7df23ce1NAKAMURA Takumi/// Note that unique predecessor doesn't mean single edge, there can be 1948fc9b3db536f1523263e8b380899fb4d7df23ce1NAKAMURA Takumi/// multiple edges from the unique predecessor to this block (for example 1959053a739e50cb6f6b68268cc7c6b95146e66d396Torok Edwin/// a switch statement with multiple cases having the same destination). 19687f1e7796d02ea991bdbf084f312879988732a26Torok EdwinBasicBlock *BasicBlock::getUniquePredecessor() { 19787f1e7796d02ea991bdbf084f312879988732a26Torok Edwin pred_iterator PI = pred_begin(this), E = pred_end(this); 19887f1e7796d02ea991bdbf084f312879988732a26Torok Edwin if (PI == E) return 0; // No preds. 19987f1e7796d02ea991bdbf084f312879988732a26Torok Edwin BasicBlock *PredBB = *PI; 20087f1e7796d02ea991bdbf084f312879988732a26Torok Edwin ++PI; 20187f1e7796d02ea991bdbf084f312879988732a26Torok Edwin for (;PI != E; ++PI) { 20287f1e7796d02ea991bdbf084f312879988732a26Torok Edwin if (*PI != PredBB) 20387f1e7796d02ea991bdbf084f312879988732a26Torok Edwin return 0; 2049053a739e50cb6f6b68268cc7c6b95146e66d396Torok Edwin // The same predecessor appears multiple times in the predecessor list. 2059053a739e50cb6f6b68268cc7c6b95146e66d396Torok Edwin // This is OK. 20687f1e7796d02ea991bdbf084f312879988732a26Torok Edwin } 20787f1e7796d02ea991bdbf084f312879988732a26Torok Edwin return PredBB; 20887f1e7796d02ea991bdbf084f312879988732a26Torok Edwin} 20987f1e7796d02ea991bdbf084f312879988732a26Torok Edwin 210566f600779d8c28a81bb08951ec1962fe34322abChris Lattner/// removePredecessor - This method is used to notify a BasicBlock that the 211566f600779d8c28a81bb08951ec1962fe34322abChris Lattner/// specified Predecessor of the block is no longer able to reach it. This is 212fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// actually not used to update the Predecessor list, but is actually used to 213566f600779d8c28a81bb08951ec1962fe34322abChris Lattner/// update the PHI nodes that reside in the block. Note that this should be 214566f600779d8c28a81bb08951ec1962fe34322abChris Lattner/// called while the predecessor still refers to this block. 215566f600779d8c28a81bb08951ec1962fe34322abChris Lattner/// 2163464547968b58dda0acbf6e0e192f03f66652848Chris Lattnervoid BasicBlock::removePredecessor(BasicBlock *Pred, 217280a6e607d8eb7401749a92db624a82de47da777Nick Lewycky bool DontDeleteUselessPHIs) { 2181f21ef1511ce003fc177121b980e783b83992f82Chris Lattner assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs. 21935f0aecdb012ba150953f6f3a98862be9c72d265Chris Lattner find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) && 2209d80930e950214d026afd3a3d18cda32629efdb9Jeff Cohen "removePredecessor: BB is not a predecessor!"); 22135f0aecdb012ba150953f6f3a98862be9c72d265Chris Lattner 222f23586c7efe615d061c00c24cf62f03f7962776fChris Lattner if (InstList.empty()) return; 223a9e7781b3b8e457946491529816feab73c66d774Chris Lattner PHINode *APN = dyn_cast<PHINode>(&front()); 224a9e7781b3b8e457946491529816feab73c66d774Chris Lattner if (!APN) return; // Quick exit. 225b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 226b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // If there are exactly two predecessors, then we want to nuke the PHI nodes 227a9e7781b3b8e457946491529816feab73c66d774Chris Lattner // altogether. However, we cannot do this, if this in this case: 22887a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // 22987a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // Loop: 23087a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // %x = phi [X, Loop] 23187a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // %x2 = add %x, 1 ;; This would become %x2 = add %x2, 1 23287a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // br Loop ;; %x2 does not dominate all uses 23387a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // 23487a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // This is because the PHI node input is actually taken from the predecessor 235fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // basic block. The only case this can happen is with a self loop, so we 23687a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // check for this case explicitly now. 237fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // 238a9e7781b3b8e457946491529816feab73c66d774Chris Lattner unsigned max_idx = APN->getNumIncomingValues(); 239b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!"); 24087a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner if (max_idx == 2) { 241a9e7781b3b8e457946491529816feab73c66d774Chris Lattner BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred); 24287a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner 24387a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // Disable PHI elimination! 24487a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner if (this == Other) max_idx = 3; 24587a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner } 24687a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner 2473464547968b58dda0acbf6e0e192f03f66652848Chris Lattner // <= Two predecessors BEFORE I remove one? 2483464547968b58dda0acbf6e0e192f03f66652848Chris Lattner if (max_idx <= 2 && !DontDeleteUselessPHIs) { 249b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner // Yup, loop through and nuke the PHI nodes 2507e70829632f82de15db187845666aaca6e04b792Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(&front())) { 2513464547968b58dda0acbf6e0e192f03f66652848Chris Lattner // Remove the predecessor first. 252280a6e607d8eb7401749a92db624a82de47da777Nick Lewycky PN->removeIncomingValue(Pred, !DontDeleteUselessPHIs); 253b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 254b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // If the PHI _HAD_ two uses, replace PHI node with its now *single* value 255dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner if (max_idx == 2) { 256c137120bb047a7017cbab21f5f9c9e6f65e2b84fJay Foad if (PN->getIncomingValue(0) != PN) 257c137120bb047a7017cbab21f5f9c9e6f65e2b84fJay Foad PN->replaceAllUsesWith(PN->getIncomingValue(0)); 25802a78cf7eacf97f2c9584e29d02f77612aead35fChris Lattner else 25902a78cf7eacf97f2c9584e29d02f77612aead35fChris Lattner // We are left with an infinite loop with no entries: kill the PHI. 2609e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 261dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner getInstList().pop_front(); // Remove the PHI node 262dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner } 263dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner 264dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner // If the PHI node already only had one entry, it got deleted by 265dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner // removeIncomingValue. 266b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } 267b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } else { 268b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // Okay, now we know that we need to remove predecessor #pred_idx from all 269b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // PHI nodes. Iterate over each PHI node fixing them up 270f878218c972dc570eb50e739c2ee2b9dd75ee5ddChris Lattner PHINode *PN; 27180f4d88a97e1b925c2ea67f932dd9c3ce1df1f8dChris Lattner for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) { 27280f4d88a97e1b925c2ea67f932dd9c3ce1df1f8dChris Lattner ++II; 273280a6e607d8eb7401749a92db624a82de47da777Nick Lewycky PN->removeIncomingValue(Pred, false); 274a83ba0f5c934e2cdbb5724cab365ecc0b5aae6c6Nate Begeman // If all incoming values to the Phi are the same, we can replace the Phi 275a83ba0f5c934e2cdbb5724cab365ecc0b5aae6c6Nate Begeman // with that value. 27690245d4cbb7816ef21f038ec5ef7e01971283436Owen Anderson Value* PNV = 0; 27723a19572b2839ee3a6a3520d60d62a465cec7d53Duncan Sands if (!DontDeleteUselessPHIs && (PNV = PN->hasConstantValue())) 27823a19572b2839ee3a6a3520d60d62a465cec7d53Duncan Sands if (PNV != PN) { 27923a19572b2839ee3a6a3520d60d62a465cec7d53Duncan Sands PN->replaceAllUsesWith(PNV); 28023a19572b2839ee3a6a3520d60d62a465cec7d53Duncan Sands PN->eraseFromParent(); 28123a19572b2839ee3a6a3520d60d62a465cec7d53Duncan Sands } 282a83ba0f5c934e2cdbb5724cab365ecc0b5aae6c6Nate Begeman } 283b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } 284b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner} 285b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 286009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 2870f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// splitBasicBlock - This splits a basic block into two at the specified 2880f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// instruction. Note that all instructions BEFORE the specified iterator stay 289fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// as part of the original basic block, an unconditional branch is added to 2900f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// the new BB, and the rest of the instructions in the BB are moved to the new 2910f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// BB, including the old terminator. This invalidates the iterator. 2920f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// 293fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// Note that this only works on well formed basic blocks (must have a 2940f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// terminator), and 'I' must not be the end of instruction list (which would 2950f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// cause a degenerate basic block to be formed, having a terminator inside of 296fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// the basic block). 2970f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// 2986e0d1cb30957a636c53158d3089e6fb88348a57aDaniel DunbarBasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) { 299009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!"); 300fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman assert(I != InstList.end() && 3019d80930e950214d026afd3a3d18cda32629efdb9Jeff Cohen "Trying to get me to create degenerate basic block!"); 302009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 3037896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner BasicBlock *InsertBefore = llvm::next(Function::iterator(this)) 304fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman .getNodePtrUnchecked(); 3051d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *New = BasicBlock::Create(getContext(), BBName, 3061d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson getParent(), InsertBefore); 307009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 308f2c3106866137b0c06e99f453a83d9558c0c6934Chris Lattner // Move all of the specified instructions from the original basic block into 309f2c3106866137b0c06e99f453a83d9558c0c6934Chris Lattner // the new basic block. 310f2c3106866137b0c06e99f453a83d9558c0c6934Chris Lattner New->getInstList().splice(New->end(), this->getInstList(), I, end()); 311009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 312009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner // Add a branch instruction to the newly formed basic block. 313051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(New, this); 314e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner 315e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // Now we must loop through all of the successors of the New block (which 316e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // _were_ the successors of the 'this' block), and update any PHI nodes in 317e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // successors. If there were PHI nodes in the successors, then they need to 318e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // know that incoming branches will be from New, not from Old. 319e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // 3201c9ab515de41707c8e04a51694a50479068e891dChris Lattner for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) { 321e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // Loop over any phi nodes in the basic block, updating the BB field of 322e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // incoming values... 323e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner BasicBlock *Successor = *I; 324f878218c972dc570eb50e739c2ee2b9dd75ee5ddChris Lattner PHINode *PN; 325e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner for (BasicBlock::iterator II = Successor->begin(); 3269bf2a926cbdf05c5b412ec35e72908a08a4cf34bChris Lattner (PN = dyn_cast<PHINode>(II)); ++II) { 327e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner int IDX = PN->getBasicBlockIndex(this); 328e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner while (IDX != -1) { 329e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner PN->setIncomingBlock((unsigned)IDX, New); 330e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner IDX = PN->getBasicBlockIndex(this); 331e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner } 332e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner } 333e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner } 334009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return New; 335009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 336eeb8ef1f37a8d106a9fb77b9dd6a7ab6866904e5Dan Gohman 33795c3e48f9557adb6064d580684bb14cacec2f826Jay Foadvoid BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) { 33895c3e48f9557adb6064d580684bb14cacec2f826Jay Foad TerminatorInst *TI = getTerminator(); 33995c3e48f9557adb6064d580684bb14cacec2f826Jay Foad if (!TI) 34095c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // Cope with being called on a BasicBlock that doesn't have a terminator 34195c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this. 34295c3e48f9557adb6064d580684bb14cacec2f826Jay Foad return; 34395c3e48f9557adb6064d580684bb14cacec2f826Jay Foad for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 34495c3e48f9557adb6064d580684bb14cacec2f826Jay Foad BasicBlock *Succ = TI->getSuccessor(i); 34577c714027ce4188be0af75b05cbbd493221fc22fNAKAMURA Takumi // N.B. Succ might not be a complete BasicBlock, so don't assume 34677c714027ce4188be0af75b05cbbd493221fc22fNAKAMURA Takumi // that it ends with a non-phi instruction. 34777c714027ce4188be0af75b05cbbd493221fc22fNAKAMURA Takumi for (iterator II = Succ->begin(), IE = Succ->end(); II != IE; ++II) { 34877c714027ce4188be0af75b05cbbd493221fc22fNAKAMURA Takumi PHINode *PN = dyn_cast<PHINode>(II); 34977c714027ce4188be0af75b05cbbd493221fc22fNAKAMURA Takumi if (!PN) 35077c714027ce4188be0af75b05cbbd493221fc22fNAKAMURA Takumi break; 35195c3e48f9557adb6064d580684bb14cacec2f826Jay Foad int i; 35295c3e48f9557adb6064d580684bb14cacec2f826Jay Foad while ((i = PN->getBasicBlockIndex(this)) >= 0) 35395c3e48f9557adb6064d580684bb14cacec2f826Jay Foad PN->setIncomingBlock(i, New); 35495c3e48f9557adb6064d580684bb14cacec2f826Jay Foad } 35595c3e48f9557adb6064d580684bb14cacec2f826Jay Foad } 35695c3e48f9557adb6064d580684bb14cacec2f826Jay Foad} 357e6e8826870bee3facb04f950f0bd725f8a88623dBill Wendling 358e6e8826870bee3facb04f950f0bd725f8a88623dBill Wendling/// isLandingPad - Return true if this basic block is a landing pad. I.e., it's 359e6e8826870bee3facb04f950f0bd725f8a88623dBill Wendling/// the destination of the 'unwind' edge of an invoke instruction. 360e6e8826870bee3facb04f950f0bd725f8a88623dBill Wendlingbool BasicBlock::isLandingPad() const { 361e6e8826870bee3facb04f950f0bd725f8a88623dBill Wendling return isa<LandingPadInst>(getFirstNonPHI()); 362e6e8826870bee3facb04f950f0bd725f8a88623dBill Wendling} 363e6e8826870bee3facb04f950f0bd725f8a88623dBill Wendling 364e6e8826870bee3facb04f950f0bd725f8a88623dBill Wendling/// getLandingPadInst() - Return the landingpad instruction associated with 365e6e8826870bee3facb04f950f0bd725f8a88623dBill Wendling/// the landing pad. 366e6e8826870bee3facb04f950f0bd725f8a88623dBill WendlingLandingPadInst *BasicBlock::getLandingPadInst() { 367e6e8826870bee3facb04f950f0bd725f8a88623dBill Wendling return dyn_cast<LandingPadInst>(getFirstNonPHI()); 368e6e8826870bee3facb04f950f0bd725f8a88623dBill Wendling} 3697750c3fc9f1dc47fce14c5dbb6c17bf5b52f3ba1Bill Wendlingconst LandingPadInst *BasicBlock::getLandingPadInst() const { 3707750c3fc9f1dc47fce14c5dbb6c17bf5b52f3ba1Bill Wendling return dyn_cast<LandingPadInst>(getFirstNonPHI()); 3717750c3fc9f1dc47fce14c5dbb6c17bf5b52f3ba1Bill Wendling} 372