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" 257707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach#include "llvm/Target/TargetInstrInfo.h" 26743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 27f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner#include "llvm/Assembly/Writer.h" 28f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner#include "llvm/ADT/SmallString.h" 29e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling#include "llvm/ADT/SmallPtrSet.h" 30dbdbbd9a67af4ba3dd9bc808ac42a0a5ddf0f0c3David Greene#include "llvm/Support/Debug.h" 312c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman#include "llvm/Support/LeakDetector.h" 321cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar#include "llvm/Support/raw_ostream.h" 3352c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner#include <algorithm> 34aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenosusing namespace llvm; 35aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos 368e5f2c6f65841542e2a7092553fe42a00048e4c7Dan GohmanMachineBasicBlock::MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb) 378c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman : BB(bb), Number(-1), xParent(&mf), Alignment(0), IsLandingPad(false), 388c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman AddressTaken(false) { 39fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman Insts.Parent = this; 4017fb34bf8cd10a798c9206eeef3bff151b4d3688Tanya Lattner} 4117fb34bf8cd10a798c9206eeef3bff151b4d3688Tanya Lattner 422c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan GohmanMachineBasicBlock::~MachineBasicBlock() { 432c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman LeakDetector::removeGarbageObject(this); 442c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman} 452c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman 46f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner/// getSymbol - Return the MCSymbol for this basic block. 47f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner/// 481b2eb0e8a6aaf034675b17be6d853cb1c666200fChris LattnerMCSymbol *MachineBasicBlock::getSymbol() const { 49f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner const MachineFunction *MF = getParent(); 501b2eb0e8a6aaf034675b17be6d853cb1c666200fChris Lattner MCContext &Ctx = MF->getContext(); 511b2eb0e8a6aaf034675b17be6d853cb1c666200fChris Lattner const char *Prefix = Ctx.getAsmInfo().getPrivateGlobalPrefix(); 529b97a73dedf736e14b04a3d1a153f10d25b2507bChris Lattner return Ctx.GetOrCreateSymbol(Twine(Prefix) + "BB" + 539b97a73dedf736e14b04a3d1a153f10d25b2507bChris Lattner Twine(MF->getFunctionNumber()) + "_" + 549b97a73dedf736e14b04a3d1a153f10d25b2507bChris Lattner Twine(getNumber())); 55f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner} 56f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner 57f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner 586371ed5e2b29434796333e487e6d14cf16306b4cChris Lattnerraw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) { 591cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar MBB.print(OS); 601cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar return OS; 611cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar} 6217fb34bf8cd10a798c9206eeef3bff151b4d3688Tanya Lattner 6312af5ff7205630a802fe4b4ca355fa143c1449f1Jakub Staszak/// addNodeToList (MBB) - When an MBB is added to an MF, we need to update the 6462ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// parent pointer of the MBB, the MBB numbering, and any instructions in the 6562ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// MBB to be on the right operand list for registers. 6662ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// 6762ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// MBBs start out as #-1. When a MBB is added to a MachineFunction, it 6862ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// gets the next available unique MBB number. If it is removed from a 6962ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner/// MachineFunction, it goes back to being #-1. 706371ed5e2b29434796333e487e6d14cf16306b4cChris Lattnervoid ilist_traits<MachineBasicBlock>::addNodeToList(MachineBasicBlock *N) { 718e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineFunction &MF = *N->getParent(); 728e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman N->Number = MF.addToMBBNumbering(N); 7362ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner 7462ed6b9ade63bf01717ce5274fa11e93e873d245Chris Lattner // Make sure the instructions have their operands in the reginfo lists. 758e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineRegisterInfo &RegInfo = MF.getRegInfo(); 76ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng for (MachineBasicBlock::instr_iterator 77ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng I = N->instr_begin(), E = N->instr_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); 9612af5ff7205630a802fe4b4ca355fa143c1449f1Jakub Staszak 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(); 11312af5ff7205630a802fe4b4ca355fa143c1449f1Jakub Staszak 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, 1247c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng ilist_iterator<MachineInstr> first, 1257c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng ilist_iterator<MachineInstr> 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() { 144f378f5fae3b7c35fc0f8996accf121ffe59093e2Benjamin Kramer instr_iterator I = instr_begin(), E = instr_end(); 145f378f5fae3b7c35fc0f8996accf121ffe59093e2Benjamin Kramer while (I != E && I->isPHI()) 146d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman ++I; 1477c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng assert(!I->isInsideBundle() && "First non-phi MI cannot be inside a bundle!"); 148d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman return I; 149d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman} 150d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman 15192095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund OlesenMachineBasicBlock::iterator 15292095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund OlesenMachineBasicBlock::SkipPHIsAndLabels(MachineBasicBlock::iterator I) { 153f378f5fae3b7c35fc0f8996accf121ffe59093e2Benjamin Kramer iterator E = end(); 154f378f5fae3b7c35fc0f8996accf121ffe59093e2Benjamin Kramer while (I != E && (I->isPHI() || I->isLabel() || I->isDebugValue())) 15592095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen ++I; 1567c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng // FIXME: This needs to change if we wish to bundle labels / dbg_values 1577c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng // inside the bundle. 1587c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng assert(!I->isInsideBundle() && 1597c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng "First non-phi / non-label instruction is inside a bundle!"); 16092095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen return I; 16192095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen} 16292095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen 16352c09d76564d6fb24444c4d56bc8978e042e72f9Chris LattnerMachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() { 164f378f5fae3b7c35fc0f8996accf121ffe59093e2Benjamin Kramer iterator B = begin(), E = end(), I = E; 165f378f5fae3b7c35fc0f8996accf121ffe59093e2Benjamin Kramer while (I != B && ((--I)->isTerminator() || I->isDebugValue())) 166b6436e5be19937b622fabd87d1547b8fc7553c11Jakob Stoklund Olesen ; /*noop */ 167f378f5fae3b7c35fc0f8996accf121ffe59093e2Benjamin Kramer while (I != E && !I->isTerminator()) 1687c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng ++I; 1697c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng return I; 1707c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng} 1717c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 1727c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan ChengMachineBasicBlock::const_iterator 1737c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan ChengMachineBasicBlock::getFirstTerminator() const { 174f378f5fae3b7c35fc0f8996accf121ffe59093e2Benjamin Kramer const_iterator B = begin(), E = end(), I = E; 175f378f5fae3b7c35fc0f8996accf121ffe59093e2Benjamin Kramer while (I != B && ((--I)->isTerminator() || I->isDebugValue())) 1767c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng ; /*noop */ 177f378f5fae3b7c35fc0f8996accf121ffe59093e2Benjamin Kramer while (I != E && !I->isTerminator()) 1787c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng ++I; 1797c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng return I; 1807c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng} 1817c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 182ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan ChengMachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() { 183f378f5fae3b7c35fc0f8996accf121ffe59093e2Benjamin Kramer instr_iterator B = instr_begin(), E = instr_end(), I = E; 184f378f5fae3b7c35fc0f8996accf121ffe59093e2Benjamin Kramer while (I != B && ((--I)->isTerminator() || I->isDebugValue())) 1857c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng ; /*noop */ 186f378f5fae3b7c35fc0f8996accf121ffe59093e2Benjamin Kramer while (I != E && !I->isTerminator()) 18704223909b74fd0634ba26d434fa7fdf2f3c7444fJakob Stoklund Olesen ++I; 188b6436e5be19937b622fabd87d1547b8fc7553c11Jakob Stoklund Olesen return I; 189743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos} 190743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos 1914f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund OlesenMachineBasicBlock::iterator MachineBasicBlock::getLastNonDebugInstr() { 1927c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng // Skip over end-of-block dbg_value instructions. 193ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng instr_iterator B = instr_begin(), I = instr_end(); 1944f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen while (I != B) { 1954f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen --I; 1967c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng // Return instruction that starts a bundle. 1977c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng if (I->isDebugValue() || I->isInsideBundle()) 1987c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng continue; 1997c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng return I; 2007c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng } 2017c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng // The block is all debug values. 2027c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng return end(); 2037c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng} 2047c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 2057c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan ChengMachineBasicBlock::const_iterator 2067c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan ChengMachineBasicBlock::getLastNonDebugInstr() const { 2077c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng // Skip over end-of-block dbg_value instructions. 208ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng const_instr_iterator B = instr_begin(), I = instr_end(); 2097c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng while (I != B) { 2107c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng --I; 2117c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng // Return instruction that starts a bundle. 2127c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng if (I->isDebugValue() || I->isInsideBundle()) 2134f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen continue; 2144f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen return I; 2154f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen } 2164f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen // The block is all debug values. 2174f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen return end(); 2184f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen} 2194f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen 220cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesenconst MachineBasicBlock *MachineBasicBlock::getLandingPadSuccessor() const { 221cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen // A block with a landing pad successor only has one other successor. 222cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen if (succ_size() > 2) 223cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen return 0; 224cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I) 225cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen if ((*I)->isLandingPad()) 226cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen return *I; 227cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen return 0; 228cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen} 229cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen 23052c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattnervoid MachineBasicBlock::dump() const { 231dbdbbd9a67af4ba3dd9bc808ac42a0a5ddf0f0c3David Greene print(dbgs()); 232aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos} 233aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos 234324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund OlesenStringRef MachineBasicBlock::getName() const { 235324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen if (const BasicBlock *LBB = getBasicBlock()) 236324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen return LBB->getName(); 237324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen else 238324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen return "(null)"; 239324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen} 240324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen 2418ceaa660bfec72249976c1f411db7f40cbc438bbAndrew Trick/// Return a hopefully unique identifier for this block. 2428ceaa660bfec72249976c1f411db7f40cbc438bbAndrew Trickstd::string MachineBasicBlock::getFullName() const { 2438ceaa660bfec72249976c1f411db7f40cbc438bbAndrew Trick std::string Name; 2448ceaa660bfec72249976c1f411db7f40cbc438bbAndrew Trick if (getParent()) 2458ceaa660bfec72249976c1f411db7f40cbc438bbAndrew Trick Name = (getParent()->getFunction()->getName() + ":").str(); 2468ceaa660bfec72249976c1f411db7f40cbc438bbAndrew Trick if (getBasicBlock()) 2478ceaa660bfec72249976c1f411db7f40cbc438bbAndrew Trick Name += getBasicBlock()->getName(); 2488ceaa660bfec72249976c1f411db7f40cbc438bbAndrew Trick else 2498ceaa660bfec72249976c1f411db7f40cbc438bbAndrew Trick Name += (Twine("BB") + Twine(getNumber())).str(); 2508ceaa660bfec72249976c1f411db7f40cbc438bbAndrew Trick return Name; 2518ceaa660bfec72249976c1f411db7f40cbc438bbAndrew Trick} 2528ceaa660bfec72249976c1f411db7f40cbc438bbAndrew Trick 253f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesenvoid MachineBasicBlock::print(raw_ostream &OS, SlotIndexes *Indexes) const { 25413d828567812041c1ca1817f4b66fce840903a1fEvan Cheng const MachineFunction *MF = getParent(); 2556371ed5e2b29434796333e487e6d14cf16306b4cChris Lattner if (!MF) { 25652c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner OS << "Can't print out MachineBasicBlock because parent MachineFunction" 25752c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner << " is null\n"; 258792699c46ef9bfc47dd459bbfa7e71bcb2cee29aTanya Lattner return; 259792699c46ef9bfc47dd459bbfa7e71bcb2cee29aTanya Lattner } 260a63828619feaeee7a7468ab00c50c3d678afae55Alkis Evlogimenos 261f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen if (Indexes) 262f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen OS << Indexes->getMBBStartIdx(this) << '\t'; 263f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen 2640ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman OS << "BB#" << getNumber() << ": "; 2650ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman 2660ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman const char *Comma = ""; 2670ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman if (const BasicBlock *LBB = getBasicBlock()) { 2680ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman OS << Comma << "derived from LLVM BB "; 2690ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman WriteAsOperand(OS, LBB, /*PrintType=*/false); 2700ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman Comma = ", "; 2710ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman } 2720ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman if (isLandingPad()) { OS << Comma << "EH LANDING PAD"; Comma = ", "; } 2730ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman if (hasAddressTaken()) { OS << Comma << "ADDRESS TAKEN"; Comma = ", "; } 274f2e944523c18c20192f675901d64c69d9602ff47Jakob Stoklund Olesen if (Alignment) { 275f2e944523c18c20192f675901d64c69d9602ff47Jakob Stoklund Olesen OS << Comma << "Align " << Alignment << " (" << (1u << Alignment) 276f2e944523c18c20192f675901d64c69d9602ff47Jakob Stoklund Olesen << " bytes)"; 277f2e944523c18c20192f675901d64c69d9602ff47Jakob Stoklund Olesen Comma = ", "; 278f2e944523c18c20192f675901d64c69d9602ff47Jakob Stoklund Olesen } 279f2e944523c18c20192f675901d64c69d9602ff47Jakob Stoklund Olesen 2806371ed5e2b29434796333e487e6d14cf16306b4cChris Lattner OS << '\n'; 28113d828567812041c1ca1817f4b66fce840903a1fEvan Cheng 282f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen const TargetRegisterInfo *TRI = MF->getTarget().getRegisterInfo(); 283cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!livein_empty()) { 284f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen if (Indexes) OS << '\t'; 2850ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman OS << " Live Ins:"; 28681bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman for (livein_iterator I = livein_begin(),E = livein_end(); I != E; ++I) 287668c9e31df3e7c216c57559c69667273f7b0404dJakob Stoklund Olesen OS << ' ' << PrintReg(*I, TRI); 2886371ed5e2b29434796333e487e6d14cf16306b4cChris Lattner OS << '\n'; 28913d828567812041c1ca1817f4b66fce840903a1fEvan Cheng } 290681764b20c3418b4af783a84eb2a68145d69a9d7Chris Lattner // Print the preds of this block according to the CFG. 291681764b20c3418b4af783a84eb2a68145d69a9d7Chris Lattner if (!pred_empty()) { 292f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen if (Indexes) OS << '\t'; 293681764b20c3418b4af783a84eb2a68145d69a9d7Chris Lattner OS << " Predecessors according to CFG:"; 294681764b20c3418b4af783a84eb2a68145d69a9d7Chris Lattner for (const_pred_iterator PI = pred_begin(), E = pred_end(); PI != E; ++PI) 2950ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman OS << " BB#" << (*PI)->getNumber(); 2966371ed5e2b29434796333e487e6d14cf16306b4cChris Lattner OS << '\n'; 297681764b20c3418b4af783a84eb2a68145d69a9d7Chris Lattner } 298f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen 299ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng for (const_instr_iterator I = instr_begin(); I != instr_end(); ++I) { 300f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen if (Indexes) { 301f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen if (Indexes->hasIndex(I)) 302f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen OS << Indexes->getInstructionIndex(I); 303f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen OS << '\t'; 304f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen } 3052d8e3d20be377112999670f210200b3658762571Chris Lattner OS << '\t'; 306ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng if (I->isInsideBundle()) 307ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng OS << " * "; 308a63828619feaeee7a7468ab00c50c3d678afae55Alkis Evlogimenos I->print(OS, &getParent()->getTarget()); 309a63828619feaeee7a7468ab00c50c3d678afae55Alkis Evlogimenos } 310380ae495996c84f348d12224ea9f4514f6471f59Chris Lattner 311380ae495996c84f348d12224ea9f4514f6471f59Chris Lattner // Print the successors of this block according to the CFG. 312380ae495996c84f348d12224ea9f4514f6471f59Chris Lattner if (!succ_empty()) { 313f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen if (Indexes) OS << '\t'; 314380ae495996c84f348d12224ea9f4514f6471f59Chris Lattner OS << " Successors according to CFG:"; 315380ae495996c84f348d12224ea9f4514f6471f59Chris Lattner for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) 3160ba90f3e34b826b039bdfece1415ef032c4ad3f5Dan Gohman OS << " BB#" << (*SI)->getNumber(); 3176371ed5e2b29434796333e487e6d14cf16306b4cChris Lattner OS << '\n'; 318380ae495996c84f348d12224ea9f4514f6471f59Chris Lattner } 319aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos} 32052c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner 321b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid MachineBasicBlock::removeLiveIn(unsigned Reg) { 32281bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman std::vector<unsigned>::iterator I = 32381bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman std::find(LiveIns.begin(), LiveIns.end(), Reg); 32478836f0bb2bf5958c1b9f904b0ad0057c77ab75fJakob Stoklund Olesen if (I != LiveIns.end()) 32578836f0bb2bf5958c1b9f904b0ad0057c77ab75fJakob Stoklund Olesen LiveIns.erase(I); 326b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 327b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 328a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Chengbool MachineBasicBlock::isLiveIn(unsigned Reg) const { 32981bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman livein_iterator I = std::find(livein_begin(), livein_end(), Reg); 330a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng return I != livein_end(); 331a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng} 332a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng 333c585a3f62adb2e491d792115af637ef75bdf489eChris Lattnervoid MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) { 3348e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman getParent()->splice(NewAfter, this); 335c585a3f62adb2e491d792115af637ef75bdf489eChris Lattner} 336c585a3f62adb2e491d792115af637ef75bdf489eChris Lattner 337c585a3f62adb2e491d792115af637ef75bdf489eChris Lattnervoid MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) { 338c585a3f62adb2e491d792115af637ef75bdf489eChris Lattner MachineFunction::iterator BBI = NewBefore; 3398e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman getParent()->splice(++BBI, this); 340c585a3f62adb2e491d792115af637ef75bdf489eChris Lattner} 341c585a3f62adb2e491d792115af637ef75bdf489eChris Lattner 3427707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbachvoid MachineBasicBlock::updateTerminator() { 3437707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach const TargetInstrInfo *TII = getParent()->getTarget().getInstrInfo(); 3447707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // A block with no successors has no concerns with fall-through edges. 3457707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (this->succ_empty()) return; 3467707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach 3477707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach MachineBasicBlock *TBB = 0, *FBB = 0; 3487707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach SmallVector<MachineOperand, 4> Cond; 3493bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings DebugLoc dl; // FIXME: this is nowhere 3507707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach bool B = TII->AnalyzeBranch(*this, TBB, FBB, Cond); 3517707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach (void) B; 3527707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach assert(!B && "UpdateTerminators requires analyzable predecessors!"); 3537707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (Cond.empty()) { 3547707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (TBB) { 3557707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // The block has an unconditional branch. If its successor is now 3567707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // its layout successor, delete the branch. 3577707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (isLayoutSuccessor(TBB)) 3587707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach TII->RemoveBranch(*this); 3597707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } else { 3607707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // The block has an unconditional fallthrough. If its successor is not 3613b7b209bf86d3e81d61cc195020bd4891467291bChandler Carruth // its layout successor, insert a branch. First we have to locate the 3623b7b209bf86d3e81d61cc195020bd4891467291bChandler Carruth // only non-landing-pad successor, as that is the fallthrough block. 3633b7b209bf86d3e81d61cc195020bd4891467291bChandler Carruth for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) { 3643b7b209bf86d3e81d61cc195020bd4891467291bChandler Carruth if ((*SI)->isLandingPad()) 3653b7b209bf86d3e81d61cc195020bd4891467291bChandler Carruth continue; 3663b7b209bf86d3e81d61cc195020bd4891467291bChandler Carruth assert(!TBB && "Found more than one non-landing-pad successor!"); 3673b7b209bf86d3e81d61cc195020bd4891467291bChandler Carruth TBB = *SI; 3683b7b209bf86d3e81d61cc195020bd4891467291bChandler Carruth } 369521fc5bcd73489f604a0b3251247c5ef21b5a0a5Chandler Carruth 370521fc5bcd73489f604a0b3251247c5ef21b5a0a5Chandler Carruth // If there is no non-landing-pad successor, the block has no 371521fc5bcd73489f604a0b3251247c5ef21b5a0a5Chandler Carruth // fall-through edges to be concerned with. 372521fc5bcd73489f604a0b3251247c5ef21b5a0a5Chandler Carruth if (!TBB) 373521fc5bcd73489f604a0b3251247c5ef21b5a0a5Chandler Carruth return; 374521fc5bcd73489f604a0b3251247c5ef21b5a0a5Chandler Carruth 375521fc5bcd73489f604a0b3251247c5ef21b5a0a5Chandler Carruth // Finally update the unconditional successor to be reached via a branch 376521fc5bcd73489f604a0b3251247c5ef21b5a0a5Chandler Carruth // if it would not be reached by fallthrough. 3777707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (!isLayoutSuccessor(TBB)) 3783bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(*this, TBB, 0, Cond, dl); 3797707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } 3807707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } else { 3817707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (FBB) { 3827707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // The block has a non-fallthrough conditional branch. If one of its 3837707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // successors is its layout successor, rewrite it to a fallthrough 3847707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // conditional branch. 3857707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (isLayoutSuccessor(TBB)) { 386e0239930ebd69336ca78843e55738a8bf2e4f2bbJakob Stoklund Olesen if (TII->ReverseBranchCondition(Cond)) 387e0239930ebd69336ca78843e55738a8bf2e4f2bbJakob Stoklund Olesen return; 3887707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach TII->RemoveBranch(*this); 3893bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(*this, FBB, 0, Cond, dl); 3907707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } else if (isLayoutSuccessor(FBB)) { 3917707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach TII->RemoveBranch(*this); 3923bf912593301152b65accb9d9c37a95172f1df5aStuart Hastings TII->InsertBranch(*this, TBB, 0, Cond, dl); 3937707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } 3947707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } else { 395f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth // Walk through the successors and find the successor which is not 396f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth // a landing pad and is not the conditional branch destination (in TBB) 397f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth // as the fallthrough successor. 398f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth MachineBasicBlock *FallthroughBB = 0; 399f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) { 400f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth if ((*SI)->isLandingPad() || *SI == TBB) 401f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth continue; 402f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth assert(!FallthroughBB && "Found more than one fallthrough successor."); 403f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth FallthroughBB = *SI; 404f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth } 405f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth if (!FallthroughBB && canFallThrough()) { 406f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth // We fallthrough to the same basic block as the conditional jump 407f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth // targets. Remove the conditional jump, leaving unconditional 408f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth // fallthrough. 409f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth // FIXME: This does not seem like a reasonable pattern to support, but it 410f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth // has been seen in the wild coming out of degenerate ARM test cases. 411f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth TII->RemoveBranch(*this); 412f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth 413f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth // Finally update the unconditional successor to be reached via a branch 414f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth // if it would not be reached by fallthrough. 415f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth if (!isLayoutSuccessor(TBB)) 416f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth TII->InsertBranch(*this, TBB, 0, Cond, dl); 417f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth return; 418f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth } 419f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth 4207707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach // The block has a fallthrough conditional branch. 4217707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach if (isLayoutSuccessor(TBB)) { 422e0239930ebd69336ca78843e55738a8bf2e4f2bbJakob Stoklund Olesen if (TII->ReverseBranchCondition(Cond)) { 423e0239930ebd69336ca78843e55738a8bf2e4f2bbJakob Stoklund Olesen // We can't reverse the condition, add an unconditional branch. 424e0239930ebd69336ca78843e55738a8bf2e4f2bbJakob Stoklund Olesen Cond.clear(); 425f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth TII->InsertBranch(*this, FallthroughBB, 0, Cond, dl); 426e0239930ebd69336ca78843e55738a8bf2e4f2bbJakob Stoklund Olesen return; 427e0239930ebd69336ca78843e55738a8bf2e4f2bbJakob Stoklund Olesen } 4287707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach TII->RemoveBranch(*this); 429f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth TII->InsertBranch(*this, FallthroughBB, 0, Cond, dl); 430f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth } else if (!isLayoutSuccessor(FallthroughBB)) { 4317707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach TII->RemoveBranch(*this); 432f1a60c734c2edb97ab75e67328935538fae5bae6Chandler Carruth TII->InsertBranch(*this, TBB, FallthroughBB, Cond, dl); 4337707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } 4347707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } 4357707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach } 4367707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach} 437c585a3f62adb2e491d792115af637ef75bdf489eChris Lattner 4387cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszakvoid MachineBasicBlock::addSuccessor(MachineBasicBlock *succ, uint32_t weight) { 4397cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 4407cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak // If we see non-zero value for the first time it means we actually use Weight 4417cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak // list, so we fill all Weights with 0's. 4427cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak if (weight != 0 && Weights.empty()) 4437cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak Weights.resize(Successors.size()); 4447cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 4457cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak if (weight != 0 || !Weights.empty()) 4467cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak Weights.push_back(weight); 4477cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 4487cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak Successors.push_back(succ); 4497cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak succ->addPredecessor(this); 4507cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak } 45152c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner 45252c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattnervoid MachineBasicBlock::removeSuccessor(MachineBasicBlock *succ) { 45352c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner succ->removePredecessor(this); 45452c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner succ_iterator I = std::find(Successors.begin(), Successors.end(), succ); 45552c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner assert(I != Successors.end() && "Not a current successor!"); 4567cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 4577cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak // If Weight list is empty it means we don't use it (disabled optimization). 4587cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak if (!Weights.empty()) { 4597cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak weight_iterator WI = getWeightIterator(I); 4607cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak Weights.erase(WI); 4617cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak } 4627cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 46352c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner Successors.erase(I); 46452c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner} 46552c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner 46612af5ff7205630a802fe4b4ca355fa143c1449f1Jakub StaszakMachineBasicBlock::succ_iterator 467f20c1a497fe3922ac718429d65a5fe396890575eChris LattnerMachineBasicBlock::removeSuccessor(succ_iterator I) { 46852c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner assert(I != Successors.end() && "Not a current successor!"); 4697cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 4707cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak // If Weight list is empty it means we don't use it (disabled optimization). 4717cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak if (!Weights.empty()) { 4727cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak weight_iterator WI = getWeightIterator(I); 4737cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak Weights.erase(WI); 4747cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak } 4757cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 47652c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner (*I)->removePredecessor(this); 4775d5ee80ea8bf300d1ee8ccbd7174466d98a1e99eDan Gohman return Successors.erase(I); 47852c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner} 47952c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner 4807cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszakvoid MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old, 4817cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak MachineBasicBlock *New) { 4827cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak uint32_t weight = 0; 4837cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak succ_iterator SI = std::find(Successors.begin(), Successors.end(), Old); 4847cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 4857cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak // If Weight list is empty it means we don't use it (disabled optimization). 4867cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak if (!Weights.empty()) { 4877cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak weight_iterator WI = getWeightIterator(SI); 4887cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak weight = *WI; 4897cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak } 4907cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 4917cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak // Update the successor information. 4927cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak removeSuccessor(SI); 4937cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak addSuccessor(New, weight); 4947cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak} 4957cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 49652c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattnervoid MachineBasicBlock::addPredecessor(MachineBasicBlock *pred) { 49752c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner Predecessors.push_back(pred); 49852c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner} 49952c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner 50052c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattnervoid MachineBasicBlock::removePredecessor(MachineBasicBlock *pred) { 5016dda9163585660a080c7fe0484a0dd75aceea00dEli Friedman pred_iterator I = std::find(Predecessors.begin(), Predecessors.end(), pred); 50252c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner assert(I != Predecessors.end() && "Pred is not a predecessor of this block!"); 50352c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner Predecessors.erase(I); 50452c09d76564d6fb24444c4d56bc8978e042e72f9Chris Lattner} 5054f098788d303bed05da6000f3ff24177aad56623Evan Cheng 5066371ed5e2b29434796333e487e6d14cf16306b4cChris Lattnervoid MachineBasicBlock::transferSuccessors(MachineBasicBlock *fromMBB) { 50763307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang if (this == fromMBB) 50863307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang return; 50912af5ff7205630a802fe4b4ca355fa143c1449f1Jakub Staszak 51014152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman while (!fromMBB->succ_empty()) { 51114152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman MachineBasicBlock *Succ = *fromMBB->succ_begin(); 5127cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak uint32_t weight = 0; 5137cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 5147cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 5157cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak // If Weight list is empty it means we don't use it (disabled optimization). 5167cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak if (!fromMBB->Weights.empty()) 5177cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak weight = *fromMBB->Weights.begin(); 5187cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 5197cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak addSuccessor(Succ, weight); 52014152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman fromMBB->removeSuccessor(Succ); 52114152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman } 52214152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman} 52314152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman 52414152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohmanvoid 52514152b480d09c7ca912af7c06d00b0ff3912e4f5Dan GohmanMachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB) { 52614152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman if (this == fromMBB) 52714152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman return; 52812af5ff7205630a802fe4b4ca355fa143c1449f1Jakub Staszak 52914152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman while (!fromMBB->succ_empty()) { 53014152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman MachineBasicBlock *Succ = *fromMBB->succ_begin(); 53114152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman addSuccessor(Succ); 53214152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman fromMBB->removeSuccessor(Succ); 53314152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman 53414152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman // Fix up any PHI nodes in the successor. 535ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng for (MachineBasicBlock::instr_iterator MI = Succ->instr_begin(), 536ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng ME = Succ->instr_end(); MI != ME && MI->isPHI(); ++MI) 53714152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman for (unsigned i = 2, e = MI->getNumOperands()+1; i != e; i += 2) { 53814152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman MachineOperand &MO = MI->getOperand(i); 53914152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman if (MO.getMBB() == fromMBB) 54014152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman MO.setMBB(this); 54114152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman } 54214152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman } 54363307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang} 54463307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang 5456d1b89e74f98470d05666ca9f59a8ec5d04b5eb4Dan Gohmanbool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const { 5466dda9163585660a080c7fe0484a0dd75aceea00dEli Friedman const_succ_iterator I = std::find(Successors.begin(), Successors.end(), MBB); 5474f098788d303bed05da6000f3ff24177aad56623Evan Cheng return I != Successors.end(); 5484f098788d303bed05da6000f3ff24177aad56623Evan Cheng} 5490370fad74b48388412c52d1325512f2c218487faEvan Cheng 5506d1b89e74f98470d05666ca9f59a8ec5d04b5eb4Dan Gohmanbool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const { 5516ade6f55a836129af634074e96f660ff23f59a30Dan Gohman MachineFunction::const_iterator I(this); 5527896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner return llvm::next(I) == MachineFunction::const_iterator(MBB); 5536ade6f55a836129af634074e96f660ff23f59a30Dan Gohman} 5546ade6f55a836129af634074e96f660ff23f59a30Dan Gohman 55515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilsonbool MachineBasicBlock::canFallThrough() { 55615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineFunction::iterator Fallthrough = this; 55715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson ++Fallthrough; 55815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If FallthroughBlock is off the end of the function, it can't fall through. 55915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (Fallthrough == getParent()->end()) 56015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return false; 56115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 56215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If FallthroughBlock isn't a successor, no fallthrough is possible. 56315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (!isSuccessor(Fallthrough)) 56415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return false; 56515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 566735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman // Analyze the branches, if any, at the end of the block. 567735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman MachineBasicBlock *TBB = 0, *FBB = 0; 568735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman SmallVector<MachineOperand, 4> Cond; 569735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman const TargetInstrInfo *TII = getParent()->getTarget().getInstrInfo(); 57033cc8d6b55ca5e1275d0984860f5d4f36f84f356Jakob Stoklund Olesen if (TII->AnalyzeBranch(*this, TBB, FBB, Cond)) { 571735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman // If we couldn't analyze the branch, examine the last instruction. 572735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman // If the block doesn't end in a known control barrier, assume fallthrough 5730162ff421deb2e7bee16aff5ed6a0a8029bcbfbeChad Rosier // is possible. The isPredicated check is needed because this code can be 574735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman // called during IfConversion, where an instruction which is normally a 5756a5d0e2a98003f5235ed8c3b9a439ad85d3d91d9Chad Rosier // Barrier is predicated and thus no longer an actual control barrier. 5760162ff421deb2e7bee16aff5ed6a0a8029bcbfbeChad Rosier return empty() || !back().isBarrier() || TII->isPredicated(&back()); 577735985fbbe3a1752b02163af0ec3ab6e6a7f0948Dan Gohman } 57815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 57915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If there is no branch, control always falls through. 58015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (TBB == 0) return true; 58115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 58215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If there is some explicit branch to the fallthrough block, it can obviously 58315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // reach, even though the branch should get folded to fall through implicitly. 58415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (MachineFunction::iterator(TBB) == Fallthrough || 58515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson MachineFunction::iterator(FBB) == Fallthrough) 58615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return true; 58715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 58815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // If it's an unconditional branch to some block not the fall through, it 58915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // doesn't fall through. 59015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson if (Cond.empty()) return false; 59115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 59215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // Otherwise, if it is conditional and has no explicit false block, it falls 59315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson // through. 59415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson return FBB == 0; 59515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson} 59615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 597853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan GohmanMachineBasicBlock * 598853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan GohmanMachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { 599853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman MachineFunction *MF = getParent(); 600853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman DebugLoc dl; // FIXME: this is nowhere 601853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 602371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen // We may need to update this's terminator, but we can't do that if 603371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen // AnalyzeBranch fails. If this uses a jump table, we won't touch it. 604853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); 605853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman MachineBasicBlock *TBB = 0, *FBB = 0; 606853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman SmallVector<MachineOperand, 4> Cond; 607853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (TII->AnalyzeBranch(*this, TBB, FBB, Cond)) 608853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman return NULL; 609853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 610371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen // Avoid bugpoint weirdness: A block may end with a conditional branch but 611371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen // jumps to the same MBB is either case. We have duplicate CFG edges in that 612371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen // case that we can't handle. Since this never happens in properly optimized 613371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen // code, just skip those edges. 614371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen if (TBB && TBB == FBB) { 615371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen DEBUG(dbgs() << "Won't split critical edge after degenerate BB#" 616371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen << getNumber() << '\n'); 617371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen return NULL; 618371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen } 619371e82bf513778bf2bde4c3eebe9407af2cef21fJakob Stoklund Olesen 620853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(); 621853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman MF->insert(llvm::next(MachineFunction::iterator(this)), NMBB); 622087fbeb7d14743d0904a94ef3c73cd5dcbc50c96Evan Cheng DEBUG(dbgs() << "Splitting critical edge:" 623853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman " BB#" << getNumber() 624853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman << " -- BB#" << NMBB->getNumber() 625853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman << " -- BB#" << Succ->getNumber() << '\n'); 626853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 62757903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen // On some targets like Mips, branches may kill virtual registers. Make sure 62857903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen // that LiveVariables is properly updated after updateTerminator replaces the 62957903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen // terminators. 63057903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen LiveVariables *LV = P->getAnalysisIfAvailable<LiveVariables>(); 63157903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen 63257903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen // Collect a list of virtual registers killed by the terminators. 63357903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen SmallVector<unsigned, 4> KilledRegs; 63457903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen if (LV) 635ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); 6367c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng I != E; ++I) { 63757903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen MachineInstr *MI = I; 63857903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen for (MachineInstr::mop_iterator OI = MI->operands_begin(), 63957903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen OE = MI->operands_end(); OI != OE; ++OI) { 64072a043f9d61aac53305102687a024a08d1fd8dadLang Hames if (!OI->isReg() || OI->getReg() == 0 || 64172a043f9d61aac53305102687a024a08d1fd8dadLang Hames !OI->isUse() || !OI->isKill() || OI->isUndef()) 64257903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen continue; 64357903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen unsigned Reg = OI->getReg(); 64472a043f9d61aac53305102687a024a08d1fd8dadLang Hames if (TargetRegisterInfo::isPhysicalRegister(Reg) || 64557903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen LV->getVarInfo(Reg).removeKill(MI)) { 64657903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen KilledRegs.push_back(Reg); 64757903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen DEBUG(dbgs() << "Removing terminator kill: " << *MI); 64857903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen OI->setIsKill(false); 64957903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen } 65057903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen } 65157903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen } 65257903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen 653853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman ReplaceUsesOfBlockWith(Succ, NMBB); 654853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman updateTerminator(); 655853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 656853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // Insert unconditional "jump Succ" instruction in NMBB if necessary. 657853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman NMBB->addSuccessor(Succ); 658853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (!NMBB->isLayoutSuccessor(Succ)) { 659853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman Cond.clear(); 660853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman MF->getTarget().getInstrInfo()->InsertBranch(*NMBB, Succ, NULL, Cond, dl); 661853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } 662853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 663853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // Fix PHI nodes in Succ so they refer to NMBB instead of this 664ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng for (MachineBasicBlock::instr_iterator 665ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng i = Succ->instr_begin(),e = Succ->instr_end(); 666ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng i != e && i->isPHI(); ++i) 667853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2) 668853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (i->getOperand(ni+1).getMBB() == this) 669853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman i->getOperand(ni+1).setMBB(NMBB); 670853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 671ac7caa0d436fa9fe96234c4e009cdacd7cd6b124Jakob Stoklund Olesen // Inherit live-ins from the successor 672ac7caa0d436fa9fe96234c4e009cdacd7cd6b124Jakob Stoklund Olesen for (MachineBasicBlock::livein_iterator I = Succ->livein_begin(), 673ac7caa0d436fa9fe96234c4e009cdacd7cd6b124Jakob Stoklund Olesen E = Succ->livein_end(); I != E; ++I) 674ac7caa0d436fa9fe96234c4e009cdacd7cd6b124Jakob Stoklund Olesen NMBB->addLiveIn(*I); 675ac7caa0d436fa9fe96234c4e009cdacd7cd6b124Jakob Stoklund Olesen 67657903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen // Update LiveVariables. 67772a043f9d61aac53305102687a024a08d1fd8dadLang Hames const TargetRegisterInfo *TRI = MF->getTarget().getRegisterInfo(); 67857903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen if (LV) { 67957903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen // Restore kills of virtual registers that were killed by the terminators. 68057903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen while (!KilledRegs.empty()) { 68157903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen unsigned Reg = KilledRegs.pop_back_val(); 682ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) { 68372a043f9d61aac53305102687a024a08d1fd8dadLang Hames if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false)) 68457903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen continue; 68572a043f9d61aac53305102687a024a08d1fd8dadLang Hames if (TargetRegisterInfo::isVirtualRegister(Reg)) 68672a043f9d61aac53305102687a024a08d1fd8dadLang Hames LV->getVarInfo(Reg).Kills.push_back(I); 68757903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen DEBUG(dbgs() << "Restored terminator kill: " << *I); 68857903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen break; 68957903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen } 69057903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen } 69157903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen // Update relevant live-through information. 692853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman LV->addNewBlock(NMBB, this, Succ); 69357903357ee4f9fed47dcad6f3739414301136b0fJakob Stoklund Olesen } 694853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 695853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (MachineDominatorTree *MDT = 69619708923bed9eccd534243bc76c40b9553365b59Evan Cheng P->getAnalysisIfAvailable<MachineDominatorTree>()) { 69719708923bed9eccd534243bc76c40b9553365b59Evan Cheng // Update dominator information. 69819708923bed9eccd534243bc76c40b9553365b59Evan Cheng MachineDomTreeNode *SucccDTNode = MDT->getNode(Succ); 69919708923bed9eccd534243bc76c40b9553365b59Evan Cheng 70019708923bed9eccd534243bc76c40b9553365b59Evan Cheng bool IsNewIDom = true; 70119708923bed9eccd534243bc76c40b9553365b59Evan Cheng for (const_pred_iterator PI = Succ->pred_begin(), E = Succ->pred_end(); 70219708923bed9eccd534243bc76c40b9553365b59Evan Cheng PI != E; ++PI) { 70319708923bed9eccd534243bc76c40b9553365b59Evan Cheng MachineBasicBlock *PredBB = *PI; 70419708923bed9eccd534243bc76c40b9553365b59Evan Cheng if (PredBB == NMBB) 70519708923bed9eccd534243bc76c40b9553365b59Evan Cheng continue; 70619708923bed9eccd534243bc76c40b9553365b59Evan Cheng if (!MDT->dominates(SucccDTNode, MDT->getNode(PredBB))) { 70719708923bed9eccd534243bc76c40b9553365b59Evan Cheng IsNewIDom = false; 70819708923bed9eccd534243bc76c40b9553365b59Evan Cheng break; 70919708923bed9eccd534243bc76c40b9553365b59Evan Cheng } 71019708923bed9eccd534243bc76c40b9553365b59Evan Cheng } 71119708923bed9eccd534243bc76c40b9553365b59Evan Cheng 71219708923bed9eccd534243bc76c40b9553365b59Evan Cheng // We know "this" dominates the newly created basic block. 71319708923bed9eccd534243bc76c40b9553365b59Evan Cheng MachineDomTreeNode *NewDTNode = MDT->addNewBlock(NMBB, this); 71419708923bed9eccd534243bc76c40b9553365b59Evan Cheng 71519708923bed9eccd534243bc76c40b9553365b59Evan Cheng // If all the other predecessors of "Succ" are dominated by "Succ" itself 71619708923bed9eccd534243bc76c40b9553365b59Evan Cheng // then the new block is the new immediate dominator of "Succ". Otherwise, 71719708923bed9eccd534243bc76c40b9553365b59Evan Cheng // the new block doesn't dominate anything. 71819708923bed9eccd534243bc76c40b9553365b59Evan Cheng if (IsNewIDom) 71919708923bed9eccd534243bc76c40b9553365b59Evan Cheng MDT->changeImmediateDominator(SucccDTNode, NewDTNode); 72019708923bed9eccd534243bc76c40b9553365b59Evan Cheng } 721853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 722e008384508342a2dec110eafaa87d93614976990Evan Cheng if (MachineLoopInfo *MLI = P->getAnalysisIfAvailable<MachineLoopInfo>()) 723853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (MachineLoop *TIL = MLI->getLoopFor(this)) { 724853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // If one or the other blocks were not in a loop, the new block is not 725853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // either, and thus LI doesn't need to be updated. 726853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) { 727853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (TIL == DestLoop) { 728853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // Both in the same loop, the NMBB joins loop. 729853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase()); 730853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } else if (TIL->contains(DestLoop)) { 731853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // Edge from an outer loop to an inner loop. Add to the outer loop. 732853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman TIL->addBasicBlockToLoop(NMBB, MLI->getBase()); 733853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } else if (DestLoop->contains(TIL)) { 734853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // Edge from an inner loop to an outer loop. Add to the outer loop. 735853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase()); 736853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } else { 737853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // Edge from two loops with no containment relation. Because these 738853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // are natural loops, we know that the destination block must be the 739853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // header of its loop (adding a branch into a loop elsewhere would 740853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman // create an irreducible loop). 741853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman assert(DestLoop->getHeader() == Succ && 742853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman "Should not create irreducible loops!"); 743853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman if (MachineLoop *P = DestLoop->getParentLoop()) 744853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman P->addBasicBlockToLoop(NMBB, MLI->getBase()); 745853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } 746853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } 747853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman } 748853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 749853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman return NMBB; 750853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman} 751853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 752ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan ChengMachineBasicBlock::iterator 753ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan ChengMachineBasicBlock::erase(MachineBasicBlock::iterator I) { 754ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng if (I->isBundle()) { 755ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng MachineBasicBlock::iterator E = llvm::next(I); 756ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng return Insts.erase(I.getInstrIterator(), E.getInstrIterator()); 757ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng } 758ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng 759ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng return Insts.erase(I.getInstrIterator()); 760ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng} 761ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng 762ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan ChengMachineInstr *MachineBasicBlock::remove(MachineInstr *I) { 763ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng if (I->isBundle()) { 764f378f5fae3b7c35fc0f8996accf121ffe59093e2Benjamin Kramer instr_iterator MII = llvm::next(I); 765f378f5fae3b7c35fc0f8996accf121ffe59093e2Benjamin Kramer iterator E = end(); 766f378f5fae3b7c35fc0f8996accf121ffe59093e2Benjamin Kramer while (MII != E && MII->isInsideBundle()) { 767ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng MachineInstr *MI = &*MII++; 768ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng Insts.remove(MI); 769ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng } 770ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng } 771ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng 772ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng return Insts.remove(I); 773ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng} 774ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng 775ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Chengvoid MachineBasicBlock::splice(MachineBasicBlock::iterator where, 776ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng MachineBasicBlock *Other, 777ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng MachineBasicBlock::iterator From) { 778ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng if (From->isBundle()) { 779ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng MachineBasicBlock::iterator To = llvm::next(From); 780ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng Insts.splice(where.getInstrIterator(), Other->Insts, 781ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng From.getInstrIterator(), To.getInstrIterator()); 782ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng return; 783ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng } 784ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng 785ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng Insts.splice(where.getInstrIterator(), Other->Insts, From.getInstrIterator()); 786ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng} 787ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng 7888e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman/// removeFromParent - This method unlinks 'this' from the containing function, 7898e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman/// and returns it, but does not delete it. 7908e5f2c6f65841542e2a7092553fe42a00048e4c7Dan GohmanMachineBasicBlock *MachineBasicBlock::removeFromParent() { 7918e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman assert(getParent() && "Not embedded in a function!"); 7928e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman getParent()->remove(this); 7938e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman return this; 7948e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman} 7958e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 7968e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 7978e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman/// eraseFromParent - This method unlinks 'this' from the containing function, 7988e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman/// and deletes it. 7998e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohmanvoid MachineBasicBlock::eraseFromParent() { 8008e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman assert(getParent() && "Not embedded in a function!"); 8018e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman getParent()->erase(this); 8028e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman} 8038e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 8048e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 8050370fad74b48388412c52d1325512f2c218487faEvan Cheng/// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 8060370fad74b48388412c52d1325512f2c218487faEvan Cheng/// 'Old', change the code and CFG so that it branches to 'New' instead. 8070370fad74b48388412c52d1325512f2c218487faEvan Chengvoid MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old, 8080370fad74b48388412c52d1325512f2c218487faEvan Cheng MachineBasicBlock *New) { 8090370fad74b48388412c52d1325512f2c218487faEvan Cheng assert(Old != New && "Cannot replace self with self!"); 8100370fad74b48388412c52d1325512f2c218487faEvan Cheng 811ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng MachineBasicBlock::instr_iterator I = instr_end(); 812ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng while (I != instr_begin()) { 8130370fad74b48388412c52d1325512f2c218487faEvan Cheng --I; 8145a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (!I->isTerminator()) break; 8150370fad74b48388412c52d1325512f2c218487faEvan Cheng 8160370fad74b48388412c52d1325512f2c218487faEvan Cheng // Scan the operands of this machine instruction, replacing any uses of Old 8170370fad74b48388412c52d1325512f2c218487faEvan Cheng // with New. 8180370fad74b48388412c52d1325512f2c218487faEvan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 819d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (I->getOperand(i).isMBB() && 820014278e6a11fa0767853b831e5bf51b95bf541c5Dan Gohman I->getOperand(i).getMBB() == Old) 8218aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner I->getOperand(i).setMBB(New); 8220370fad74b48388412c52d1325512f2c218487faEvan Cheng } 8230370fad74b48388412c52d1325512f2c218487faEvan Cheng 8245412d06e9c352c9795f4a71b91c4f869585866ebDan Gohman // Update the successor information. 8257cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak replaceSuccessor(Old, New); 8260370fad74b48388412c52d1325512f2c218487faEvan Cheng} 8270370fad74b48388412c52d1325512f2c218487faEvan Cheng 8282bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng/// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the 8292bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng/// CFG to be inserted. If we have proven that MBB can only branch to DestA and 830c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling/// DestB, remove any other MBB successors from the CFG. DestA and DestB can be 831c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling/// null. 83212af5ff7205630a802fe4b4ca355fa143c1449f1Jakub Staszak/// 833f20c1a497fe3922ac718429d65a5fe396890575eChris Lattner/// Besides DestA and DestB, retain other edges leading to LandingPads 834f20c1a497fe3922ac718429d65a5fe396890575eChris Lattner/// (currently there can be only one; we don't check or require that here). 8352bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng/// Note it is possible that DestA and/or DestB are LandingPads. 8362bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Chengbool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, 8372bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng MachineBasicBlock *DestB, 8382bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng bool isCond) { 839c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // The values of DestA and DestB frequently come from a call to the 840c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial 841c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // values from there. 842c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // 843c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // 1. If both DestA and DestB are null, then the block ends with no branches 844c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // (it falls through to its successor). 845c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // 2. If DestA is set, DestB is null, and isCond is false, then the block ends 846c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // with only an unconditional branch. 847c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // 3. If DestA is set, DestB is null, and isCond is true, then the block ends 848c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // with a conditional branch that falls through to a successor (DestB). 849c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // 4. If DestA and DestB is set and isCond is true, then the block ends with a 850c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // conditional branch followed by an unconditional branch. DestA is the 851c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling // 'true' destination and DestB is the 'false' destination. 852c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling 853e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling bool Changed = false; 8542bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng 8557896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MachineFunction::iterator FallThru = 8567896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner llvm::next(MachineFunction::iterator(this)); 857e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling 858e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling if (DestA == 0 && DestB == 0) { 859e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling // Block falls through to successor. 860e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling DestA = FallThru; 861e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling DestB = FallThru; 862e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling } else if (DestA != 0 && DestB == 0) { 863e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling if (isCond) 864e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling // Block ends in conditional jump that falls through to successor. 8652bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng DestB = FallThru; 8662bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng } else { 867e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling assert(DestA && DestB && isCond && 868e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling "CFG in a bad state. Cannot correct CFG edges"); 8692bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng } 870e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling 871e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling // Remove superfluous edges. I.e., those which aren't destinations of this 872e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling // basic block, duplicate edges, or landing pads. 873e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling SmallPtrSet<const MachineBasicBlock*, 8> SeenMBBs; 8742bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng MachineBasicBlock::succ_iterator SI = succ_begin(); 8752bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng while (SI != succ_end()) { 876c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling const MachineBasicBlock *MBB = *SI; 877e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling if (!SeenMBBs.insert(MBB) || 878e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling (MBB != DestA && MBB != DestB && !MBB->isLandingPad())) { 879e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling // This is a superfluous edge, remove it. 8809e9cca424cf0374259706cbedec89507bf89bdcfBill Wendling SI = removeSuccessor(SI); 881e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling Changed = true; 882e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling } else { 883e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling ++SI; 8842bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng } 8852bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng } 886c70d3311513802e01d634d69e550f96a7a96d04aBill Wendling 887e543d161a0959a912efd20027ca98d3d0bf576ecBill Wendling return Changed; 8882bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng} 8892a085c34933a6c76e5a86f2680d93c16b0438801Evan Cheng 890918f0f0beab7401172b0b17aeb04e8d757e97a10Dale Johannesen/// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping 89110fedd21d3d5e9527b13e38addd7002da2c1dc61Dale Johannesen/// any DBG_VALUE instructions. Return UnknownLoc if there is none. 892918f0f0beab7401172b0b17aeb04e8d757e97a10Dale JohannesenDebugLoc 893ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan ChengMachineBasicBlock::findDebugLoc(instr_iterator MBBI) { 894918f0f0beab7401172b0b17aeb04e8d757e97a10Dale Johannesen DebugLoc DL; 895ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng instr_iterator E = instr_end(); 8967c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng if (MBBI == E) 8977c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng return DL; 8987c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 8997c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng // Skip debug declarations, we don't want a DebugLoc from them. 9007c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng while (MBBI != E && MBBI->isDebugValue()) 9017c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng MBBI++; 9027c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng if (MBBI != E) 9037c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng DL = MBBI->getDebugLoc(); 904918f0f0beab7401172b0b17aeb04e8d757e97a10Dale Johannesen return DL; 905918f0f0beab7401172b0b17aeb04e8d757e97a10Dale Johannesen} 90673e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen 9077cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak/// getSuccWeight - Return weight of the edge from this block to MBB. 9087cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak/// 90925101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub Staszakuint32_t MachineBasicBlock::getSuccWeight(const MachineBasicBlock *succ) const { 910981d82674c59b0e6415d3a30b2f9da625e438852Jakub Staszak if (Weights.empty()) 911981d82674c59b0e6415d3a30b2f9da625e438852Jakub Staszak return 0; 912981d82674c59b0e6415d3a30b2f9da625e438852Jakub Staszak 91325101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub Staszak const_succ_iterator I = std::find(Successors.begin(), Successors.end(), succ); 9147cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak return *getWeightIterator(I); 9157cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak} 9167cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 9177cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak/// getWeightIterator - Return wight iterator corresonding to the I successor 9187cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak/// iterator 9197cc2b07437a1243c33324549a1904fefc5f1845eJakub StaszakMachineBasicBlock::weight_iterator MachineBasicBlock:: 9207cc2b07437a1243c33324549a1904fefc5f1845eJakub StaszakgetWeightIterator(MachineBasicBlock::succ_iterator I) { 921981d82674c59b0e6415d3a30b2f9da625e438852Jakub Staszak assert(Weights.size() == Successors.size() && "Async weight list!"); 9227cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak size_t index = std::distance(Successors.begin(), I); 9237cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak assert(index < Weights.size() && "Not a current successor!"); 9247cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak return Weights.begin() + index; 9257cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak} 9267cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 92725101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub Staszak/// getWeightIterator - Return wight iterator corresonding to the I successor 92825101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub Staszak/// iterator 92925101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub StaszakMachineBasicBlock::const_weight_iterator MachineBasicBlock:: 93025101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub StaszakgetWeightIterator(MachineBasicBlock::const_succ_iterator I) const { 93125101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub Staszak assert(Weights.size() == Successors.size() && "Async weight list!"); 93225101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub Staszak const size_t index = std::distance(Successors.begin(), I); 93325101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub Staszak assert(index < Weights.size() && "Not a current successor!"); 93425101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub Staszak return Weights.begin() + index; 93525101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub Staszak} 93625101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub Staszak 93773e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesenvoid llvm::WriteAsOperand(raw_ostream &OS, const MachineBasicBlock *MBB, 93873e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen bool t) { 93973e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen OS << "BB#" << MBB->getNumber(); 94073e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen} 94173e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen 942