MachineBasicBlock.cpp revision 6dda9163585660a080c7fe0484a0dd75aceea00d
1aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos//===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===// 2aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos// 3aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos// The LLVM Compiler Infrastructure 4aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos// 8aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos//===----------------------------------------------------------------------===// 9aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos// 10aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos// Collect the sequence of machine instructions for a basic block. 11aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos// 12aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos//===----------------------------------------------------------------------===// 13aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos 14aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos#include "llvm/CodeGen/MachineBasicBlock.h" 15aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos#include "llvm/BasicBlock.h" 16853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman#include "llvm/CodeGen/LiveVariables.h" 17853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman#include "llvm/CodeGen/MachineDominators.h" 18aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos#include "llvm/CodeGen/MachineFunction.h" 19853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman#include "llvm/CodeGen/MachineLoopInfo.h" 20f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen#include "llvm/CodeGen/SlotIndexes.h" 21f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner#include "llvm/MC/MCAsmInfo.h" 22f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner#include "llvm/MC/MCContext.h" 2343cf6c3939176e8d87719516f0b2e4c6c346f340Bill Wendling#include "llvm/Target/TargetRegisterInfo.h" 2407000c6f01d8f57170f2d4c77a86d934bdc5c696Owen Anderson#include "llvm/Target/TargetData.h" 25f14cf85e334ff03bbdd23e473f14ffa4fb025e94Chris Lattner#include "llvm/Target/TargetInstrDesc.h" 267707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach#include "llvm/Target/TargetInstrInfo.h" 27743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 28f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner#include "llvm/Assembly/Writer.h" 29f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner#include "llvm/ADT/SmallString.h" 30e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling#include "llvm/ADT/SmallPtrSet.h" 31dbdbbd9a67af4ba3dd9bc808ac42a0a5ddf0f0c3David Greene#include "llvm/Support/Debug.h" 322c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman#include "llvm/Support/LeakDetector.h" 331cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar#include "llvm/Support/raw_ostream.h" 3452c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner#include <algorithm> 35aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenosusing namespace llvm; 36aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos 378e5f2c6f65841542e2a7092553fe42a00048e4c7Dan GohmanMachineBasicBlock::MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb) 388c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman : BB(bb), Number(-1), xParent(&mf), Alignment(0), IsLandingPad(false), 398c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman AddressTaken(false) { 40fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman Insts.Parent = this; 4117fb34bf8cd10a798c9206eeef3bff151b4d3688Tanya Lattner} 4217fb34bf8cd10a798c9206eeef3bff151b4d3688Tanya Lattner 432c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan GohmanMachineBasicBlock::~MachineBasicBlock() { 442c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman LeakDetector::removeGarbageObject(this); 452c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman} 462c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman 47f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner/// getSymbol - Return the MCSymbol for this basic block. 48f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner/// 491b2eb0e8a6aaf034675b17be6d853cb1c666200fChris LattnerMCSymbol *MachineBasicBlock::getSymbol() const { 50f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner const MachineFunction *MF = getParent(); 511b2eb0e8a6aaf034675b17be6d853cb1c666200fChris Lattner MCContext &Ctx = MF->getContext(); 521b2eb0e8a6aaf034675b17be6d853cb1c666200fChris Lattner const char *Prefix = Ctx.getAsmInfo().getPrivateGlobalPrefix(); 539b97a73dedf736e14b04a3d1a153f10d25b2507bChris Lattner return Ctx.GetOrCreateSymbol(Twine(Prefix) + "BB" + 549b97a73dedf736e14b04a3d1a153f10d25b2507bChris Lattner Twine(MF->getFunctionNumber()) + "_" + 559b97a73dedf736e14b04a3d1a153f10d25b2507bChris Lattner Twine(getNumber())); 56f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner} 57f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner 58f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner 596371ed5e2b29434796333e487e6d14cf16306b4cChris Lattnerraw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) { 601cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar MBB.print(OS); 611cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar return OS; 621cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar} 6317fb34bf8cd10a798c9206eeef3bff151b4d3688Tanya Lattner 6462ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// addNodeToList (MBB) - When an MBB is added to an MF, we need to update the 6562ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// parent pointer of the MBB, the MBB numbering, and any instructions in the 6662ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// MBB to be on the right operand list for registers. 6762ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// 6862ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// MBBs start out as #-1. When a MBB is added to a MachineFunction, it 6962ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// gets the next available unique MBB number. If it is removed from a 7062ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// MachineFunction, it goes back to being #-1. 716371ed5e2b29434796333e487e6d14cf16306b4cChris Lattnervoid ilist_traits<MachineBasicBlock>::addNodeToList(MachineBasicBlock *N) { 728e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineFunction &MF = *N->getParent(); 738e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman N->Number = MF.addToMBBNumbering(N); 7462ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner 7562ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner // Make sure the instructions have their operands in the reginfo lists. 768e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineRegisterInfo &RegInfo = MF.getRegInfo(); 7762ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner for (MachineBasicBlock::iterator I = N->begin(), E = N->end(); I != E; ++I) 7862ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner I->AddRegOperandsToUseLists(RegInfo); 792c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman 802c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman LeakDetector::removeGarbageObject(N); 810bcb1ad7be8515492ba02f64c0e43113ecdf8e32Brian Gaeke} 820bcb1ad7be8515492ba02f64c0e43113ecdf8e32Brian Gaeke 836371ed5e2b29434796333e487e6d14cf16306b4cChris Lattnervoid ilist_traits<MachineBasicBlock>::removeNodeFromList(MachineBasicBlock *N) { 84f20c1a497fe3922ac718429d65a5fe396890575eChris Lattner N->getParent()->removeFromMBBNumbering(N->Number); 850bcb1ad7be8515492ba02f64c0e43113ecdf8e32Brian Gaeke N->Number = -1; 862c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman LeakDetector::addGarbageObject(N); 870bcb1ad7be8515492ba02f64c0e43113ecdf8e32Brian Gaeke} 880bcb1ad7be8515492ba02f64c0e43113ecdf8e32Brian Gaeke 895e61fa95196b85281eec655787e9c73267532bd1Chris Lattner 9062ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// addNodeToList (MI) - When we add an instruction to a basic block 9162ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// list, we update its parent pointer and add its operands from reg use/def 9262ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// lists if appropriate. 936371ed5e2b29434796333e487e6d14cf16306b4cChris Lattnervoid ilist_traits<MachineInstr>::addNodeToList(MachineInstr *N) { 94f20c1a497fe3922ac718429d65a5fe396890575eChris Lattner assert(N->getParent() == 0 && "machine instruction already in a basic block"); 958e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman N->setParent(Parent); 9662ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner 978e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman // Add the instruction's register operands to their corresponding 988e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman // use/def lists. 998e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineFunction *MF = Parent->getParent(); 1008e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman N->AddRegOperandsToUseLists(MF->getRegInfo()); 1012c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman 1022c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman LeakDetector::removeGarbageObject(N); 103aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos} 104aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos 10562ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// removeNodeFromList (MI) - When we remove an instruction from a basic block 10662ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// list, we update its parent pointer and remove its operands from reg use/def 10762ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// lists if appropriate. 1086371ed5e2b29434796333e487e6d14cf16306b4cChris Lattnervoid ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr *N) { 109f20c1a497fe3922ac718429d65a5fe396890575eChris Lattner assert(N->getParent() != 0 && "machine instruction not in a basic block"); 1108e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 1118e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman // Remove from the use/def lists. 1128e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman N->RemoveRegOperandsFromUseLists(); 11362ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner 114f20c1a497fe3922ac718429d65a5fe396890575eChris Lattner N->setParent(0); 1152c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman 1162c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman LeakDetector::addGarbageObject(N); 117aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos} 118aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos 11962ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// transferNodesFromList (MI) - When moving a range of instructions from one 12062ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// MBB list to another, we need to update the parent pointers and the use/def 12162ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// lists. 1226371ed5e2b29434796333e487e6d14cf16306b4cChris Lattnervoid ilist_traits<MachineInstr>:: 1236371ed5e2b29434796333e487e6d14cf16306b4cChris LattnertransferNodesFromList(ilist_traits<MachineInstr> &fromList, 1246371ed5e2b29434796333e487e6d14cf16306b4cChris Lattner MachineBasicBlock::iterator first, 1256371ed5e2b29434796333e487e6d14cf16306b4cChris Lattner MachineBasicBlock::iterator last) { 126fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman assert(Parent->getParent() == fromList.Parent->getParent() && 127fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman "MachineInstr parent mismatch!"); 128fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman 129f20c1a497fe3922ac718429d65a5fe396890575eChris Lattner // Splice within the same MBB -> no change. 1308e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman if (Parent == fromList.Parent) return; 13162ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner 13262ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner // If splicing between two blocks within the same function, just update the 13362ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner // parent pointers. 134fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman for (; first != last; ++first) 1358e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman first->setParent(Parent); 136aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos} 137aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos 138fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohmanvoid ilist_traits<MachineInstr>::deleteNode(MachineInstr* MI) { 1398e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman assert(!MI->getParent() && "MI is still in a block!"); 1408e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman Parent->getParent()->DeleteMachineInstr(MI); 1418e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman} 1428e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 143d463a7446402f0771465fe66fe0a7d9f72534902Dan GohmanMachineBasicBlock::iterator MachineBasicBlock::getFirstNonPHI() { 144d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman iterator I = begin(); 145d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman while (I != end() && I->isPHI()) 146d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman ++I; 147d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman return I; 148d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman} 149d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman 15092095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund OlesenMachineBasicBlock::iterator 15192095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund OlesenMachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) { 15292095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen while (I != end() && (I->isPHI() || I->isLabel() || I->isDebugValue())) 15392095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen ++I; 15492095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen return I; 15592095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen} 15692095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen 15752c09d76564d6fb24444c4d56bc8978e042e72f9Chris LattnerMachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() { 158b6436e5be19937b622fabd87d1547b8fc7553c11Jakob Stoklund Olesen iterator I = end(); 15904223909b74fd0634ba26d434fa7fdf2f3c7444fJakob Stoklund Olesen while (I != begin() && ((--I)->getDesc().isTerminator() || I->isDebugValue())) 160b6436e5be19937b622fabd87d1547b8fc7553c11Jakob Stoklund Olesen ; /*noop */ 16104223909b74fd0634ba26d434fa7fdf2f3c7444fJakob Stoklund Olesen while (I != end() && !I->getDesc().isTerminator()) 16204223909b74fd0634ba26d434fa7fdf2f3c7444fJakob Stoklund Olesen ++I; 163b6436e5be19937b622fabd87d1547b8fc7553c11Jakob Stoklund Olesen return I; 164743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos} 165743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos 1664f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund OlesenMachineBasicBlock::iterator MachineBasicBlock::getLastNonDebugInstr() { 1674f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen iterator B = begin(), I = end(); 1684f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen while (I != B) { 1694f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen --I; 1704f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen if (I->isDebugValue()) 1714f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen continue; 1724f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen return I; 1734f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen } 1744f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen // The block is all debug values. 1754f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen return end(); 1764f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen} 1774f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen 178cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesenconst MachineBasicBlock *MachineBasicBlock::getLandingPadSuccessor() const { 179cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen // A block with a landing pad successor only has one other successor. 180cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen if (succ_size() > 2) 181cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen return 0; 182cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I) 183cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen if ((*I)->isLandingPad()) 184cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen return *I; 185cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen return 0; 186cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen} 187cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen 18852c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattnervoid MachineBasicBlock::dump() const { 189dbdbbd9a67af4ba3dd9bc808ac42a0a5ddf0f0c3David Greene print(dbgs()); 190aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos} 191aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos 192324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund OlesenStringRef MachineBasicBlock::getName() const { 193324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen if (const BasicBlock *LBB = getBasicBlock()) 194324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen return LBB->getName(); 195324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen else 196324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen return "(null)"; 197324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen} 198324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen 199f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesenvoid MachineBasicBlock::print(raw_ostream &OS, SlotIndexes *Indexes) const { 20013d828567812041c1ca1817f4b66fce840903a1fEvan Cheng const MachineFunction *MF = getParent(); 2016371ed5e2b29434796333e487e6d14cf16306b4cChris Lattner if (!MF) { 20252c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner OS << "Can't print out MachineBasicBlock because parent MachineFunction" 20352c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner << " is null\n"; 204792699c46ef9bfc47dd459bbfa7e71bcb2cee29aTanya Lattner return; 205792699c46ef9bfc47dd459bbfa7e71bcb2cee29aTanya Lattner } 206a63828619feaeee7a7468ab00c50c3d678afae55Alkis Evlogimenos 2070ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman if (Alignment) { OS << "Alignment " << Alignment << "\n"; } 2080ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman 209f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen if (Indexes) 210f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen OS << Indexes->getMBBStartIdx(this) << '\t'; 211f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen 2120ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman OS << "BB#" << getNumber() << ": "; 2130ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman 2140ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman const char *Comma = ""; 2150ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman if (const BasicBlock *LBB = getBasicBlock()) { 2160ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman OS << Comma << "derived from LLVM BB "; 2170ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman WriteAsOperand(OS, LBB, /*PrintType=*/false); 2180ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman Comma = ", "; 2190ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman } 2200ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman if (isLandingPad()) { OS << Comma << "EH LANDING PAD"; Comma = ", "; } 2210ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman if (hasAddressTaken()) { OS << Comma << "ADDRESS TAKEN"; Comma = ", "; } 2226371ed5e2b29434796333e487e6d14cf16306b4cChris Lattner OS << '\n'; 22313d828567812041c1ca1817f4b66fce840903a1fEvan Cheng 224f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen const TargetRegisterInfo *TRI = MF->getTarget().getRegisterInfo(); 225cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!livein_empty()) { 226f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen if (Indexes) OS << '\t'; 2270ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman OS << " Live Ins:"; 22881bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman for (livein_iterator I = livein_begin(),E = livein_end(); I != E; ++I) 229668c9e31df3e7c216c57559c69667273f7b0404dJakob Stoklund Olesen OS << ' ' << PrintReg(*I, TRI); 2306371ed5e2b29434796333e487e6d14cf16306b4cChris Lattner OS << '\n'; 23113d828567812041c1ca1817f4b66fce840903a1fEvan Cheng } 232681764b20c3418b4af783a84eb2a68145d69a9d7Chris Lattner // Print the preds of this block according to the CFG. 233681764b20c3418b4af783a84eb2a68145d69a9d7Chris Lattner if (!pred_empty()) { 234f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen if (Indexes) OS << '\t'; 235681764b20c3418b4af783a84eb2a68145d69a9d7Chris Lattner OS << " Predecessors according to CFG:"; 236681764b20c3418b4af783a84eb2a68145d69a9d7Chris Lattner for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI) 2370ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman OS << " BB#" << (*PI)->getNumber(); 2386371ed5e2b29434796333e487e6d14cf16306b4cChris Lattner OS << '\n'; 239681764b20c3418b4af783a84eb2a68145d69a9d7Chris Lattner } 240f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen 241a63828619feaeee7a7468ab00c50c3d678afae55Alkis Evlogimenos for (const_iterator I = begin(); I != end(); ++I) { 242f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen if (Indexes) { 243f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen if (Indexes->hasIndex(I)) 244f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen OS << Indexes->getInstructionIndex(I); 245f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen OS << '\t'; 246f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen } 2472d8e3d20be377112999670f210200b3658762571Chris Lattner OS << '\t'; 248a63828619feaeee7a7468ab00c50c3d678afae55Alkis Evlogimenos I->print(OS, &getParent()->getTarget()); 249a63828619feaeee7a7468ab00c50c3d678afae55Alkis Evlogimenos } 250380ae495996c84f348d12224ea9f4514f6471f59Chris Lattner 251380ae495996c84f348d12224ea9f4514f6471f59Chris Lattner // Print the successors of this block according to the CFG. 252380ae495996c84f348d12224ea9f4514f6471f59Chris Lattner if (!succ_empty()) { 253f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen if (Indexes) OS << '\t'; 254380ae495996c84f348d12224ea9f4514f6471f59Chris Lattner OS << " Successors according to CFG:"; 255380ae495996c84f348d12224ea9f4514f6471f59Chris Lattner for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) 2560ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman OS << " BB#" << (*SI)->getNumber(); 2576371ed5e2b29434796333e487e6d14cf16306b4cChris Lattner OS << '\n'; 258380ae495996c84f348d12224ea9f4514f6471f59Chris Lattner } 259aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos} 26052c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner 261b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid MachineBasicBlock::removeLiveIn(unsigned Reg) { 26281bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman std::vector<unsigned>::iterator I = 26381bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman std::find(LiveIns.begin(), LiveIns.end(), Reg); 26481bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman assert(I != LiveIns.end() && "Not a live in!"); 265b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng LiveIns.erase(I); 266b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 267b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 268a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Chengbool MachineBasicBlock::isLiveIn(unsigned Reg) const { 26981bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman livein_iterator I = std::find(livein_begin(), livein_end(), Reg); 270a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng return I != livein_end(); 271a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng} 272a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng 273c585a3f62adb2e491d792115af637ef75bdf489eChris Lattnervoid MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) { 2748e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman getParent()->splice(NewAfter, this); 275c585a3f62adb2e491d792115af637ef75bdf489eChris Lattner} 276c585a3f62adb2e491d792115af637ef75bdf489eChris Lattner 277c585a3f62adb2e491d792115af637ef75bdf489eChris Lattnervoid MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) { 278c585a3f62adb2e491d792115af637ef75bdf489eChris Lattner MachineFunction::iterator BBI = NewBefore; 2798e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman getParent()->splice(++BBI, this); 280c585a3f62adb2e491d792115af637ef75bdf489eChris Lattner} 281c585a3f62adb2e491d792115af637ef75bdf489eChris Lattner 2827707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbachvoid MachineBasicBlock::updateTerminator() { 2837707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach const TargetInstrInfo *TII = getParent()->getTarget().getInstrInfo(); 2847707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // A block with no successors has no concerns with fall-through edges. 2857707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (this->succ_empty()) return; 2867707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach 2877707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach MachineBasicBlock *TBB = 0, *FBB = 0; 2887707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach SmallVector<MachineOperand, 4> Cond; 2893bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings DebugLoc dl; // FIXME: this is nowhere 2907707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach bool B = TII->AnalyzeBranch(*this, TBB, FBB, Cond); 2917707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach (void) B; 2927707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach assert(!B && "UpdateTerminators requires analyzable predecessors!"); 2937707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (Cond.empty()) { 2947707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (TBB) { 2957707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // The block has an unconditional branch. If its successor is now 2967707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // its layout successor, delete the branch. 2977707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (isLayoutSuccessor(TBB)) 2987707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach TII->RemoveBranch(*this); 2997707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } else { 3007707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // The block has an unconditional fallthrough. If its successor is not 3017707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // its layout successor, insert a branch. 3027707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach TBB = *succ_begin(); 3037707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (!isLayoutSuccessor(TBB)) 3043bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(*this, TBB, 0, Cond, dl); 3057707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } 3067707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } else { 3077707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (FBB) { 3087707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // The block has a non-fallthrough conditional branch. If one of its 3097707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // successors is its layout successor, rewrite it to a fallthrough 3107707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // conditional branch. 3117707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (isLayoutSuccessor(TBB)) { 312e0239930ebd69336ca78843e55738a8bf2e4f2bbJakob Stoklund Olesen if (TII->ReverseBranchCondition(Cond)) 313e0239930ebd69336ca78843e55738a8bf2e4f2bbJakob Stoklund Olesen return; 3147707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach TII->RemoveBranch(*this); 3153bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(*this, FBB, 0, Cond, dl); 3167707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } else if (isLayoutSuccessor(FBB)) { 3177707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach TII->RemoveBranch(*this); 3183bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(*this, TBB, 0, Cond, dl); 3197707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } 3207707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } else { 3217707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // The block has a fallthrough conditional branch. 3227707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach MachineBasicBlock *MBBA = *succ_begin(); 3237896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MachineBasicBlock *MBBB = *llvm::next(succ_begin()); 3247707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (MBBA == TBB) std::swap(MBBB, MBBA); 3257707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (isLayoutSuccessor(TBB)) { 326e0239930ebd69336ca78843e55738a8bf2e4f2bbJakob Stoklund Olesen if (TII->ReverseBranchCondition(Cond)) { 327e0239930ebd69336ca78843e55738a8bf2e4f2bbJakob Stoklund Olesen // We can't reverse the condition, add an unconditional branch. 328e0239930ebd69336ca78843e55738a8bf2e4f2bbJakob Stoklund Olesen Cond.clear(); 3293bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(*this, MBBA, 0, Cond, dl); 330e0239930ebd69336ca78843e55738a8bf2e4f2bbJakob Stoklund Olesen return; 331e0239930ebd69336ca78843e55738a8bf2e4f2bbJakob Stoklund Olesen } 3327707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach TII->RemoveBranch(*this); 3333bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(*this, MBBA, 0, Cond, dl); 3347707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } else if (!isLayoutSuccessor(MBBA)) { 3357707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach TII->RemoveBranch(*this); 3363bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(*this, TBB, MBBA, Cond, dl); 3377707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } 3387707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } 3397707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } 3407707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach} 341c585a3f62adb2e491d792115af637ef75bdf489eChris Lattner 34252c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattnervoid MachineBasicBlock::addSuccessor(MachineBasicBlock *succ) { 34352c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner Successors.push_back(succ); 34452c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner succ->addPredecessor(this); 34552c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner} 34652c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner 34752c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattnervoid MachineBasicBlock::removeSuccessor(MachineBasicBlock *succ) { 34852c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner succ->removePredecessor(this); 34952c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner succ_iterator I = std::find(Successors.begin(), Successors.end(), succ); 35052c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner assert(I != Successors.end() && "Not a current successor!"); 35152c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner Successors.erase(I); 35252c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner} 35352c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner 354f20c1a497fe3922ac718429d65a5fe396890575eChris LattnerMachineBasicBlock::succ_iterator 355f20c1a497fe3922ac718429d65a5fe396890575eChris LattnerMachineBasicBlock::removeSuccessor(succ_iterator I) { 35652c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner assert(I != Successors.end() && "Not a current successor!"); 35752c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner (*I)->removePredecessor(this); 3585d5ee80ea8bf300d1ee8ccbd7174466d98a1e99eDan Gohman return Successors.erase(I); 35952c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner} 36052c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner 36152c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattnervoid MachineBasicBlock::addPredecessor(MachineBasicBlock *pred) { 36252c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner Predecessors.push_back(pred); 36352c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner} 36452c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner 36552c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattnervoid MachineBasicBlock::removePredecessor(MachineBasicBlock *pred) { 3666dda9163585660a080c7fe0484a0dd75aceea00dEli Friedman pred_iterator I = std::find(Predecessors.begin(), Predecessors.end(), pred); 36752c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner assert(I != Predecessors.end() && "Pred is not a predecessor of this block!"); 36852c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner Predecessors.erase(I); 36952c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner} 3704f098788d303bed05da6000f3ff24177aad56623Evan Cheng 3716371ed5e2b29434796333e487e6d14cf16306b4cChris Lattnervoid MachineBasicBlock::transferSuccessors(MachineBasicBlock *fromMBB) { 37263307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang if (this == fromMBB) 37363307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang return; 37463307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang 37514152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman while (!fromMBB->succ_empty()) { 37614152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman MachineBasicBlock *Succ = *fromMBB->succ_begin(); 37714152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman addSuccessor(Succ); 37814152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman fromMBB->removeSuccessor(Succ); 37914152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman } 38014152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman} 38114152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman 38214152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohmanvoid 38314152b480d09c7ca912af7c06d00b0ff3912e4f5Dan GohmanMachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB) { 38414152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman if (this == fromMBB) 38514152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman return; 3866371ed5e2b29434796333e487e6d14cf16306b4cChris Lattner 38714152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman while (!fromMBB->succ_empty()) { 38814152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman MachineBasicBlock *Succ = *fromMBB->succ_begin(); 38914152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman addSuccessor(Succ); 39014152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman fromMBB->removeSuccessor(Succ); 39114152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman 39214152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman // Fix up any PHI nodes in the successor. 39314152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman for (MachineBasicBlock::iterator MI = Succ->begin(), ME = Succ->end(); 39414152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman MI != ME && MI->isPHI(); ++MI) 39514152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman for (unsigned i = 2, e = MI->getNumOperands()+1; i != e; i += 2) { 39614152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman MachineOperand &MO = MI->getOperand(i); 39714152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman if (MO.getMBB() == fromMBB) 39814152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman MO.setMBB(this); 39914152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman } 40014152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman } 40163307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang} 40263307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang 4036d1b89e74f98470d05666ca9f59a8ec5d04b5eb4Dan Gohmanbool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const { 4046dda9163585660a080c7fe0484a0dd75aceea00dEli Friedman const_succ_iterator I = std::find(Successors.begin(), Successors.end(), MBB); 4054f098788d303bed05da6000f3ff24177aad56623Evan Cheng return I != Successors.end(); 4064f098788d303bed05da6000f3ff24177aad56623Evan Cheng} 4070370fad74b48388412c52d1325512f2c218487faEvan Cheng 4086d1b89e74f98470d05666ca9f59a8ec5d04b5eb4Dan Gohmanbool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const { 4096ade6f55a836129af634074e96f660ff23f59a30Dan Gohman MachineFunction::const_iterator I(this); 4107896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner return llvm::next(I) == MachineFunction::const_iterator(MBB); 4116ade6f55a836129af634074e96f660ff23f59a30Dan Gohman} 4126ade6f55a836129af634074e96f660ff23f59a30Dan Gohman 41315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonbool MachineBasicBlock::canFallThrough() { 41415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineFunction::iterator Fallthrough = this; 41515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson ++Fallthrough; 41615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If FallthroughBlock is off the end of the function, it can't fall through. 41715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (Fallthrough == getParent()->end()) 41815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return false; 41915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 42015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If FallthroughBlock isn't a successor, no fallthrough is possible. 42115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (!isSuccessor(Fallthrough)) 42215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return false; 42315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 424735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman // Analyze the branches, if any, at the end of the block. 425735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman MachineBasicBlock *TBB = 0, *FBB = 0; 426735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman SmallVector<MachineOperand, 4> Cond; 427735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman const TargetInstrInfo *TII = getParent()->getTarget().getInstrInfo(); 42833cc8d6b55ca5e1275d0984860f5d4f36f84f356Jakob Stoklund Olesen if (TII->AnalyzeBranch(*this, TBB, FBB, Cond)) { 429735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman // If we couldn't analyze the branch, examine the last instruction. 430735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman // If the block doesn't end in a known control barrier, assume fallthrough 431735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman // is possible. The isPredicable check is needed because this code can be 432735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman // called during IfConversion, where an instruction which is normally a 433735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman // Barrier is predicated and thus no longer an actual control barrier. This 434735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman // is over-conservative though, because if an instruction isn't actually 435735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman // predicated we could still treat it like a barrier. 43615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return empty() || !back().getDesc().isBarrier() || 43715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson back().getDesc().isPredicable(); 438735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman } 43915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 44015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If there is no branch, control always falls through. 44115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (TBB == 0) return true; 44215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 44315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If there is some explicit branch to the fallthrough block, it can obviously 44415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // reach, even though the branch should get folded to fall through implicitly. 44515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (MachineFunction::iterator(TBB) == Fallthrough || 44615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineFunction::iterator(FBB) == Fallthrough) 44715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return true; 44815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 44915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If it's an unconditional branch to some block not the fall through, it 45015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // doesn't fall through. 45115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (Cond.empty()) return false; 45215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 45315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Otherwise, if it is conditional and has no explicit false block, it falls 45415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // through. 45515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return FBB == 0; 45615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 45715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 458853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan GohmanMachineBasicBlock * 459853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan GohmanMachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { 460853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman MachineFunction *MF = getParent(); 461853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman DebugLoc dl; // FIXME: this is nowhere 462853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 463371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen // We may need to update this's terminator, but we can't do that if 464371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen // AnalyzeBranch fails. If this uses a jump table, we won't touch it. 465853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); 466853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman MachineBasicBlock *TBB = 0, *FBB = 0; 467853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman SmallVector<MachineOperand, 4> Cond; 468853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (TII->AnalyzeBranch(*this, TBB, FBB, Cond)) 469853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman return NULL; 470853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 471371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen // Avoid bugpoint weirdness: A block may end with a conditional branch but 472371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen // jumps to the same MBB is either case. We have duplicate CFG edges in that 473371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen // case that we can't handle. Since this never happens in properly optimized 474371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen // code, just skip those edges. 475371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen if (TBB && TBB == FBB) { 476371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen DEBUG(dbgs() << "Won't split critical edge after degenerate BB#" 477371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen << getNumber() << '\n'); 478371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen return NULL; 479371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen } 480371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen 481853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(); 482853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman MF->insert(llvm::next(MachineFunction::iterator(this)), NMBB); 483087fbeb7d14743d0904a94ef3c73cd5dcbc50c96Evan Cheng DEBUG(dbgs() << "Splitting critical edge:" 484853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman " BB#" << getNumber() 485853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman << " -- BB#" << NMBB->getNumber() 486853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman << " -- BB#" << Succ->getNumber() << '\n'); 487853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 488853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman ReplaceUsesOfBlockWith(Succ, NMBB); 489853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman updateTerminator(); 490853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 491853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // Insert unconditional "jump Succ" instruction in NMBB if necessary. 492853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman NMBB->addSuccessor(Succ); 493853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (!NMBB->isLayoutSuccessor(Succ)) { 494853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman Cond.clear(); 495853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman MF->getTarget().getInstrInfo()->InsertBranch(*NMBB, Succ, NULL, Cond, dl); 496853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } 497853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 498853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // Fix PHI nodes in Succ so they refer to NMBB instead of this 499853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman for (MachineBasicBlock::iterator i = Succ->begin(), e = Succ->end(); 500853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman i != e && i->isPHI(); ++i) 501853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2) 502853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (i->getOperand(ni+1).getMBB() == this) 503853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman i->getOperand(ni+1).setMBB(NMBB); 504853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 505853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (LiveVariables *LV = 506853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman P->getAnalysisIfAvailable<LiveVariables>()) 507853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman LV->addNewBlock(NMBB, this, Succ); 508853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 509853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (MachineDominatorTree *MDT = 51019708923bed9eccd534243bc76c40b9553365b59Evan Cheng P->getAnalysisIfAvailable<MachineDominatorTree>()) { 51119708923bed9eccd534243bc76c40b9553365b59Evan Cheng // Update dominator information. 51219708923bed9eccd534243bc76c40b9553365b59Evan Cheng MachineDomTreeNode *SucccDTNode = MDT->getNode(Succ); 51319708923bed9eccd534243bc76c40b9553365b59Evan Cheng 51419708923bed9eccd534243bc76c40b9553365b59Evan Cheng bool IsNewIDom = true; 51519708923bed9eccd534243bc76c40b9553365b59Evan Cheng for (const_pred_iterator PI = Succ->pred_begin(), E = Succ->pred_end(); 51619708923bed9eccd534243bc76c40b9553365b59Evan Cheng PI != E; ++PI) { 51719708923bed9eccd534243bc76c40b9553365b59Evan Cheng MachineBasicBlock *PredBB = *PI; 51819708923bed9eccd534243bc76c40b9553365b59Evan Cheng if (PredBB == NMBB) 51919708923bed9eccd534243bc76c40b9553365b59Evan Cheng continue; 52019708923bed9eccd534243bc76c40b9553365b59Evan Cheng if (!MDT->dominates(SucccDTNode, MDT->getNode(PredBB))) { 52119708923bed9eccd534243bc76c40b9553365b59Evan Cheng IsNewIDom = false; 52219708923bed9eccd534243bc76c40b9553365b59Evan Cheng break; 52319708923bed9eccd534243bc76c40b9553365b59Evan Cheng } 52419708923bed9eccd534243bc76c40b9553365b59Evan Cheng } 52519708923bed9eccd534243bc76c40b9553365b59Evan Cheng 52619708923bed9eccd534243bc76c40b9553365b59Evan Cheng // We know "this" dominates the newly created basic block. 52719708923bed9eccd534243bc76c40b9553365b59Evan Cheng MachineDomTreeNode *NewDTNode = MDT->addNewBlock(NMBB, this); 52819708923bed9eccd534243bc76c40b9553365b59Evan Cheng 52919708923bed9eccd534243bc76c40b9553365b59Evan Cheng // If all the other predecessors of "Succ" are dominated by "Succ" itself 53019708923bed9eccd534243bc76c40b9553365b59Evan Cheng // then the new block is the new immediate dominator of "Succ". Otherwise, 53119708923bed9eccd534243bc76c40b9553365b59Evan Cheng // the new block doesn't dominate anything. 53219708923bed9eccd534243bc76c40b9553365b59Evan Cheng if (IsNewIDom) 53319708923bed9eccd534243bc76c40b9553365b59Evan Cheng MDT->changeImmediateDominator(SucccDTNode, NewDTNode); 53419708923bed9eccd534243bc76c40b9553365b59Evan Cheng } 535853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 536e008384508342a2dec110eafaa87d93614976990Evan Cheng if (MachineLoopInfo *MLI = P->getAnalysisIfAvailable<MachineLoopInfo>()) 537853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (MachineLoop *TIL = MLI->getLoopFor(this)) { 538853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // If one or the other blocks were not in a loop, the new block is not 539853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // either, and thus LI doesn't need to be updated. 540853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) { 541853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (TIL == DestLoop) { 542853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // Both in the same loop, the NMBB joins loop. 543853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase()); 544853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } else if (TIL->contains(DestLoop)) { 545853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // Edge from an outer loop to an inner loop. Add to the outer loop. 546853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman TIL->addBasicBlockToLoop(NMBB, MLI->getBase()); 547853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } else if (DestLoop->contains(TIL)) { 548853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // Edge from an inner loop to an outer loop. Add to the outer loop. 549853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase()); 550853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } else { 551853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // Edge from two loops with no containment relation. Because these 552853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // are natural loops, we know that the destination block must be the 553853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // header of its loop (adding a branch into a loop elsewhere would 554853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // create an irreducible loop). 555853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman assert(DestLoop->getHeader() == Succ && 556853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman "Should not create irreducible loops!"); 557853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (MachineLoop *P = DestLoop->getParentLoop()) 558853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman P->addBasicBlockToLoop(NMBB, MLI->getBase()); 559853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } 560853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } 561853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } 562853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 563853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman return NMBB; 564853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman} 565853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 5668e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman/// removeFromParent - This method unlinks 'this' from the containing function, 5678e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman/// and returns it, but does not delete it. 5688e5f2c6f65841542e2a7092553fe42a00048e4c7Dan GohmanMachineBasicBlock *MachineBasicBlock::removeFromParent() { 5698e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman assert(getParent() && "Not embedded in a function!"); 5708e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman getParent()->remove(this); 5718e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman return this; 5728e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman} 5738e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 5748e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 5758e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman/// eraseFromParent - This method unlinks 'this' from the containing function, 5768e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman/// and deletes it. 5778e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohmanvoid MachineBasicBlock::eraseFromParent() { 5788e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman assert(getParent() && "Not embedded in a function!"); 5798e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman getParent()->erase(this); 5808e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman} 5818e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 5828e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 5830370fad74b48388412c52d1325512f2c218487faEvan Cheng/// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 5840370fad74b48388412c52d1325512f2c218487faEvan Cheng/// 'Old', change the code and CFG so that it branches to 'New' instead. 5850370fad74b48388412c52d1325512f2c218487faEvan Chengvoid MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old, 5860370fad74b48388412c52d1325512f2c218487faEvan Cheng MachineBasicBlock *New) { 5870370fad74b48388412c52d1325512f2c218487faEvan Cheng assert(Old != New && "Cannot replace self with self!"); 5880370fad74b48388412c52d1325512f2c218487faEvan Cheng 5890370fad74b48388412c52d1325512f2c218487faEvan Cheng MachineBasicBlock::iterator I = end(); 5900370fad74b48388412c52d1325512f2c218487faEvan Cheng while (I != begin()) { 5910370fad74b48388412c52d1325512f2c218487faEvan Cheng --I; 592749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (!I->getDesc().isTerminator()) break; 5930370fad74b48388412c52d1325512f2c218487faEvan Cheng 5940370fad74b48388412c52d1325512f2c218487faEvan Cheng // Scan the operands of this machine instruction, replacing any uses of Old 5950370fad74b48388412c52d1325512f2c218487faEvan Cheng // with New. 5960370fad74b48388412c52d1325512f2c218487faEvan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 597d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (I->getOperand(i).isMBB() && 598014278e6a11fa0767853b831e5bf51b95bf541c5Dan Gohman I->getOperand(i).getMBB() == Old) 5998aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner I->getOperand(i).setMBB(New); 6000370fad74b48388412c52d1325512f2c218487faEvan Cheng } 6010370fad74b48388412c52d1325512f2c218487faEvan Cheng 6025412d06e9c352c9795f4a71b91c4f869585866ebDan Gohman // Update the successor information. 6030370fad74b48388412c52d1325512f2c218487faEvan Cheng removeSuccessor(Old); 6045412d06e9c352c9795f4a71b91c4f869585866ebDan Gohman addSuccessor(New); 6050370fad74b48388412c52d1325512f2c218487faEvan Cheng} 6060370fad74b48388412c52d1325512f2c218487faEvan Cheng 6072bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng/// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the 6082bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng/// CFG to be inserted. If we have proven that MBB can only branch to DestA and 609c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling/// DestB, remove any other MBB successors from the CFG. DestA and DestB can be 610c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling/// null. 611c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling/// 612f20c1a497fe3922ac718429d65a5fe396890575eChris Lattner/// Besides DestA and DestB, retain other edges leading to LandingPads 613f20c1a497fe3922ac718429d65a5fe396890575eChris Lattner/// (currently there can be only one; we don't check or require that here). 6142bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng/// Note it is possible that DestA and/or DestB are LandingPads. 6152bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Chengbool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, 6162bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng MachineBasicBlock *DestB, 6172bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng bool isCond) { 618c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // The values of DestA and DestB frequently come from a call to the 619c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial 620c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // values from there. 621c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // 622c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // 1. If both DestA and DestB are null, then the block ends with no branches 623c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // (it falls through to its successor). 624c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // 2. If DestA is set, DestB is null, and isCond is false, then the block ends 625c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // with only an unconditional branch. 626c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // 3. If DestA is set, DestB is null, and isCond is true, then the block ends 627c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // with a conditional branch that falls through to a successor (DestB). 628c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // 4. If DestA and DestB is set and isCond is true, then the block ends with a 629c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // conditional branch followed by an unconditional branch. DestA is the 630c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // 'true' destination and DestB is the 'false' destination. 631c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling 632e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling bool Changed = false; 6332bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng 6347896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MachineFunction::iterator FallThru = 6357896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner llvm::next(MachineFunction::iterator(this)); 636e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling 637e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling if (DestA == 0 && DestB == 0) { 638e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling // Block falls through to successor. 639e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling DestA = FallThru; 640e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling DestB = FallThru; 641e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling } else if (DestA != 0 && DestB == 0) { 642e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling if (isCond) 643e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling // Block ends in conditional jump that falls through to successor. 6442bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng DestB = FallThru; 6452bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng } else { 646e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling assert(DestA && DestB && isCond && 647e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling "CFG in a bad state. Cannot correct CFG edges"); 6482bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng } 649e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling 650e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling // Remove superfluous edges. I.e., those which aren't destinations of this 651e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling // basic block, duplicate edges, or landing pads. 652e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling SmallPtrSet<const MachineBasicBlock*, 8> SeenMBBs; 6532bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng MachineBasicBlock::succ_iterator SI = succ_begin(); 6542bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng while (SI != succ_end()) { 655c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling const MachineBasicBlock *MBB = *SI; 656e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling if (!SeenMBBs.insert(MBB) || 657e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling (MBB != DestA && MBB != DestB && !MBB->isLandingPad())) { 658e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling // This is a superfluous edge, remove it. 6599e9cca424cf0374259706cbedec89507bf89bdcfBill Wendling SI = removeSuccessor(SI); 660e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling Changed = true; 661e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling } else { 662e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling ++SI; 6632bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng } 6642bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng } 665c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling 666e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling return Changed; 6672bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng} 6682a085c34933a6c76e5a86f2680d93c16b0438801Evan Cheng 669918f0f0beab7401172b0b17aeb04e8d757e97a10Dale Johannesen/// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping 67010fedd21d3d5e9527b13e38addd7002da2c1dc61Dale Johannesen/// any DBG_VALUE instructions. Return UnknownLoc if there is none. 671918f0f0beab7401172b0b17aeb04e8d757e97a10Dale JohannesenDebugLoc 67273e884bb3e971b1e794ba2501df15138f73b8b1aDale JohannesenMachineBasicBlock::findDebugLoc(MachineBasicBlock::iterator &MBBI) { 673918f0f0beab7401172b0b17aeb04e8d757e97a10Dale Johannesen DebugLoc DL; 67473e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen MachineBasicBlock::iterator E = end(); 67573e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen if (MBBI != E) { 676918f0f0beab7401172b0b17aeb04e8d757e97a10Dale Johannesen // Skip debug declarations, we don't want a DebugLoc from them. 677918f0f0beab7401172b0b17aeb04e8d757e97a10Dale Johannesen MachineBasicBlock::iterator MBBI2 = MBBI; 678518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner while (MBBI2 != E && MBBI2->isDebugValue()) 679918f0f0beab7401172b0b17aeb04e8d757e97a10Dale Johannesen MBBI2++; 68073e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen if (MBBI2 != E) 681918f0f0beab7401172b0b17aeb04e8d757e97a10Dale Johannesen DL = MBBI2->getDebugLoc(); 682918f0f0beab7401172b0b17aeb04e8d757e97a10Dale Johannesen } 683918f0f0beab7401172b0b17aeb04e8d757e97a10Dale Johannesen return DL; 684918f0f0beab7401172b0b17aeb04e8d757e97a10Dale Johannesen} 68573e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen 68673e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesenvoid llvm::WriteAsOperand(raw_ostream &OS, const MachineBasicBlock *MBB, 68773e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen bool t) { 68873e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen OS << "BB#" << MBB->getNumber(); 68973e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen} 69073e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen 691