LiveRangeEdit.cpp revision e9bd4ea5fda4957c373a3bbc14803d9670041dcc
1a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen//===--- LiveRangeEdit.cpp - Basic tools for editing a register live range --===// 2a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen// 3a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 4a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen// 5a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 6a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 7a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen// 8a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 9a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen// 10a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen// The LiveRangeEdit class represents changes done to a virtual register when it 11a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen// is spilled or split. 12a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 13a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen 14cf610d07de3ba4929bb5d00e084877dd974b44a1Jakob Stoklund Olesen#define DEBUG_TYPE "regalloc" 15a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen#include "LiveRangeEdit.h" 16a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen#include "VirtRegMap.h" 175881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen#include "llvm/ADT/SetVector.h" 18e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 196094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen#include "llvm/CodeGen/CalcSpillWeights.h" 20a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 21a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 22080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 235881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen#include "llvm/Support/Debug.h" 245881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 25a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen 26a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesenusing namespace llvm; 27a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen 28e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund OlesenSTATISTIC(NumDCEDeleted, "Number of instructions deleted by DCE"); 29e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund OlesenSTATISTIC(NumDCEFoldedLoads, "Number of single use loads folded after DCE"); 30e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund OlesenSTATISTIC(NumFracRanges, "Number of live ranges fractured by DCE"); 31e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen 326a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund OlesenLiveInterval &LiveRangeEdit::createFrom(unsigned OldReg, 336a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen LiveIntervals &LIS, 346a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen VirtRegMap &VRM) { 356a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen MachineRegisterInfo &MRI = VRM.getRegInfo(); 366a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen unsigned VReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg)); 376a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen VRM.grow(); 386a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen VRM.setIsSplitFromReg(VReg, VRM.getOriginal(OldReg)); 396a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen LiveInterval &LI = LIS.getOrCreateInterval(VReg); 406a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen newRegs_.push_back(&LI); 416a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen return LI; 42a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen} 43a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen 443b7d917dec53a742fcb14802557ee75d35185968Jakob Stoklund Olesenbool LiveRangeEdit::checkRematerializable(VNInfo *VNI, 452ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen const MachineInstr *DefMI, 462ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen const TargetInstrInfo &tii, 472ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen AliasAnalysis *aa) { 482ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen assert(DefMI && "Missing instruction"); 492ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen scannedRemattable_ = true; 503b7d917dec53a742fcb14802557ee75d35185968Jakob Stoklund Olesen if (!tii.isTriviallyReMaterializable(DefMI, aa)) 513b7d917dec53a742fcb14802557ee75d35185968Jakob Stoklund Olesen return false; 523b7d917dec53a742fcb14802557ee75d35185968Jakob Stoklund Olesen remattable_.insert(VNI); 533b7d917dec53a742fcb14802557ee75d35185968Jakob Stoklund Olesen return true; 542ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen} 552ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen 56080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesenvoid LiveRangeEdit::scanRemattable(LiveIntervals &lis, 57080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen const TargetInstrInfo &tii, 58080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen AliasAnalysis *aa) { 59080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen for (LiveInterval::vni_iterator I = parent_.vni_begin(), 60080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen E = parent_.vni_end(); I != E; ++I) { 61080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen VNInfo *VNI = *I; 62080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen if (VNI->isUnused()) 63080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen continue; 64080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen MachineInstr *DefMI = lis.getInstructionFromIndex(VNI->def); 65080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen if (!DefMI) 66080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen continue; 672ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen checkRematerializable(VNI, DefMI, tii, aa); 68080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen } 69806562cc59ad35e6c742abe9109e9b8090b3f820Jakob Stoklund Olesen scannedRemattable_ = true; 70080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen} 71080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen 72080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesenbool LiveRangeEdit::anyRematerializable(LiveIntervals &lis, 73080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen const TargetInstrInfo &tii, 74080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen AliasAnalysis *aa) { 75080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen if (!scannedRemattable_) 76080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen scanRemattable(lis, tii, aa); 77080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen return !remattable_.empty(); 78080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen} 79080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen 80a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen/// allUsesAvailableAt - Return true if all registers used by OrigMI at 81a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen/// OrigIdx are also available with the same value at UseIdx. 82a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesenbool LiveRangeEdit::allUsesAvailableAt(const MachineInstr *OrigMI, 83a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen SlotIndex OrigIdx, 84a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen SlotIndex UseIdx, 85a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen LiveIntervals &lis) { 86a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen OrigIdx = OrigIdx.getUseIndex(); 87a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen UseIdx = UseIdx.getUseIndex(); 88a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen for (unsigned i = 0, e = OrigMI->getNumOperands(); i != e; ++i) { 89a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen const MachineOperand &MO = OrigMI->getOperand(i); 902ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen if (!MO.isReg() || !MO.getReg() || MO.isDef()) 91a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen continue; 92a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen // Reserved registers are OK. 93a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen if (MO.isUndef() || !lis.hasInterval(MO.getReg())) 94a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen continue; 95a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen // We cannot depend on virtual registers in uselessRegs_. 961973b3e2541f95c87e4acb7e134362ff306ec9edJakob Stoklund Olesen if (uselessRegs_) 971973b3e2541f95c87e4acb7e134362ff306ec9edJakob Stoklund Olesen for (unsigned ui = 0, ue = uselessRegs_->size(); ui != ue; ++ui) 981973b3e2541f95c87e4acb7e134362ff306ec9edJakob Stoklund Olesen if ((*uselessRegs_)[ui]->reg == MO.getReg()) 991973b3e2541f95c87e4acb7e134362ff306ec9edJakob Stoklund Olesen return false; 100a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen 101a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen LiveInterval &li = lis.getInterval(MO.getReg()); 102a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen const VNInfo *OVNI = li.getVNInfoAt(OrigIdx); 103a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen if (!OVNI) 104a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen continue; 105a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen if (OVNI != li.getVNInfoAt(UseIdx)) 106a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen return false; 107a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen } 108a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen return true; 109a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen} 110a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen 111b80e973c95034e5754d888140497a9658a7c1dedJakob Stoklund Olesenbool LiveRangeEdit::canRematerializeAt(Remat &RM, 112b80e973c95034e5754d888140497a9658a7c1dedJakob Stoklund Olesen SlotIndex UseIdx, 113b80e973c95034e5754d888140497a9658a7c1dedJakob Stoklund Olesen bool cheapAsAMove, 114b80e973c95034e5754d888140497a9658a7c1dedJakob Stoklund Olesen LiveIntervals &lis) { 115080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen assert(scannedRemattable_ && "Call anyRematerializable first"); 116080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen 117080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen // Use scanRemattable info. 118080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen if (!remattable_.count(RM.ParentVNI)) 119b80e973c95034e5754d888140497a9658a7c1dedJakob Stoklund Olesen return false; 120080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen 1212ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen // No defining instruction provided. 1222ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen SlotIndex DefIdx; 1232ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen if (RM.OrigMI) 1242ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen DefIdx = lis.getInstructionIndex(RM.OrigMI); 1252ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen else { 1262ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen DefIdx = RM.ParentVNI->def; 1272ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen RM.OrigMI = lis.getInstructionFromIndex(DefIdx); 1282ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen assert(RM.OrigMI && "No defining instruction for remattable value"); 1292ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen } 130080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen 131080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen // If only cheap remats were requested, bail out early. 132b80e973c95034e5754d888140497a9658a7c1dedJakob Stoklund Olesen if (cheapAsAMove && !RM.OrigMI->getDesc().isAsCheapAsAMove()) 133b80e973c95034e5754d888140497a9658a7c1dedJakob Stoklund Olesen return false; 134080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen 135080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen // Verify that all used registers are available with the same values. 1362ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen if (!allUsesAvailableAt(RM.OrigMI, DefIdx, UseIdx, lis)) 137b80e973c95034e5754d888140497a9658a7c1dedJakob Stoklund Olesen return false; 138080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen 139b80e973c95034e5754d888140497a9658a7c1dedJakob Stoklund Olesen return true; 140080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen} 141080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen 142080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund OlesenSlotIndex LiveRangeEdit::rematerializeAt(MachineBasicBlock &MBB, 143080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen MachineBasicBlock::iterator MI, 144080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen unsigned DestReg, 145080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen const Remat &RM, 146080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen LiveIntervals &lis, 147080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen const TargetInstrInfo &tii, 148bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen const TargetRegisterInfo &tri, 149bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen bool Late) { 150080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen assert(RM.OrigMI && "Invalid remat"); 151080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen tii.reMaterialize(MBB, MI, DestReg, 0, RM.OrigMI, tri); 152f1583ae84a8eeb0f6c0f81bd5bf189bdc9eaecb2Jakob Stoklund Olesen rematted_.insert(RM.ParentVNI); 153bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen return lis.getSlotIndexes()->insertMachineInstrInMaps(--MI, Late) 154bb30dd40ed0873e39fec4dfa321091a0c8d1abfcJakob Stoklund Olesen .getDefIndex(); 155080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen} 156080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen 1577792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesenvoid LiveRangeEdit::eraseVirtReg(unsigned Reg, LiveIntervals &LIS) { 1587792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen if (delegate_ && delegate_->LRE_CanEraseVirtReg(Reg)) 1597792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen LIS.removeInterval(Reg); 1607792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen} 1617792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen 1623520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesenbool LiveRangeEdit::foldAsLoad(LiveInterval *LI, 1633520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen SmallVectorImpl<MachineInstr*> &Dead, 1643520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen MachineRegisterInfo &MRI, 1653520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen LiveIntervals &LIS, 1663520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen const TargetInstrInfo &TII) { 1673520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen MachineInstr *DefMI = 0, *UseMI = 0; 1683520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen 1693520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen // Check that there is a single def and a single use. 1703520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen for (MachineRegisterInfo::reg_nodbg_iterator I = MRI.reg_nodbg_begin(LI->reg), 1713520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen E = MRI.reg_nodbg_end(); I != E; ++I) { 1723520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen MachineOperand &MO = I.getOperand(); 1733520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 1743520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen if (MO.isDef()) { 1753520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen if (DefMI && DefMI != MI) 1763520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen return false; 1773520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen if (!MI->getDesc().canFoldAsLoad()) 1783520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen return false; 1793520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen DefMI = MI; 1803520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen } else if (!MO.isUndef()) { 1813520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen if (UseMI && UseMI != MI) 1823520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen return false; 1833520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen // FIXME: Targets don't know how to fold subreg uses. 1843520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen if (MO.getSubReg()) 1853520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen return false; 1863520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen UseMI = MI; 1873520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen } 1883520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen } 1893520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen if (!DefMI || !UseMI) 1903520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen return false; 1913520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen 1923520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen DEBUG(dbgs() << "Try to fold single def: " << *DefMI 1933520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen << " into single use: " << *UseMI); 1943520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen 1953520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen SmallVector<unsigned, 8> Ops; 1963520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen if (UseMI->readsWritesVirtualRegister(LI->reg, &Ops).second) 1973520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen return false; 1983520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen 1993520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen MachineInstr *FoldMI = TII.foldMemoryOperand(UseMI, Ops, DefMI); 2003520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen if (!FoldMI) 2013520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen return false; 2023520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen DEBUG(dbgs() << " folded: " << *FoldMI); 2033520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen LIS.ReplaceMachineInstrInMaps(UseMI, FoldMI); 2043520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen UseMI->eraseFromParent(); 2053520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen DefMI->addRegisterDead(LI->reg, 0); 2063520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen Dead.push_back(DefMI); 207e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumDCEFoldedLoads; 2083520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen return true; 2093520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen} 2103520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen 2115881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesenvoid LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr*> &Dead, 2126a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen LiveIntervals &LIS, VirtRegMap &VRM, 2135881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen const TargetInstrInfo &TII) { 2145881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen SetVector<LiveInterval*, 2155881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen SmallVector<LiveInterval*, 8>, 2165881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen SmallPtrSet<LiveInterval*, 8> > ToShrink; 2171edc3cf65d54130542fc91bac67ecf616ef88d48Jakob Stoklund Olesen MachineRegisterInfo &MRI = VRM.getRegInfo(); 2185881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 2195881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen for (;;) { 2205881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen // Erase all dead defs. 2215881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen while (!Dead.empty()) { 2225881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen MachineInstr *MI = Dead.pop_back_val(); 2235881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen assert(MI->allDefsAreDead() && "Def isn't really dead"); 224c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen SlotIndex Idx = LIS.getInstructionIndex(MI).getDefIndex(); 2255881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 2265881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen // Never delete inline asm. 227c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen if (MI->isInlineAsm()) { 228c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen DEBUG(dbgs() << "Won't delete: " << Idx << '\t' << *MI); 2295881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen continue; 230c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen } 2315881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 2325881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen // Use the same criteria as DeadMachineInstructionElim. 2335881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen bool SawStore = false; 234c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen if (!MI->isSafeToMove(&TII, 0, SawStore)) { 235c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen DEBUG(dbgs() << "Can't delete: " << Idx << '\t' << *MI); 2365881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen continue; 237c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen } 2385881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 2395881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen DEBUG(dbgs() << "Deleting dead def " << Idx << '\t' << *MI); 2405881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 2415881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen // Check for live intervals that may shrink 2425881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen for (MachineInstr::mop_iterator MOI = MI->operands_begin(), 2435881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen MOE = MI->operands_end(); MOI != MOE; ++MOI) { 2445881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen if (!MOI->isReg()) 2455881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen continue; 2465881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen unsigned Reg = MOI->getReg(); 2475881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 2485881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen continue; 2495881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen LiveInterval &LI = LIS.getInterval(Reg); 250cc5c4296fda7270e8394626d7254596f5f9c8d82Jakob Stoklund Olesen 2511edc3cf65d54130542fc91bac67ecf616ef88d48Jakob Stoklund Olesen // Shrink read registers, unless it is likely to be expensive and 2521edc3cf65d54130542fc91bac67ecf616ef88d48Jakob Stoklund Olesen // unlikely to change anything. We typically don't want to shrink the 2531edc3cf65d54130542fc91bac67ecf616ef88d48Jakob Stoklund Olesen // PIC base register that has lots of uses everywhere. 2541edc3cf65d54130542fc91bac67ecf616ef88d48Jakob Stoklund Olesen // Always shrink COPY uses that probably come from live range splitting. 2551edc3cf65d54130542fc91bac67ecf616ef88d48Jakob Stoklund Olesen if (MI->readsVirtualRegister(Reg) && 2561edc3cf65d54130542fc91bac67ecf616ef88d48Jakob Stoklund Olesen (MI->isCopy() || MOI->isDef() || MRI.hasOneNonDBGUse(Reg) || 2571edc3cf65d54130542fc91bac67ecf616ef88d48Jakob Stoklund Olesen LI.killedAt(Idx))) 2585881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen ToShrink.insert(&LI); 259cc5c4296fda7270e8394626d7254596f5f9c8d82Jakob Stoklund Olesen 260cc5c4296fda7270e8394626d7254596f5f9c8d82Jakob Stoklund Olesen // Remove defined value. 261cc5c4296fda7270e8394626d7254596f5f9c8d82Jakob Stoklund Olesen if (MOI->isDef()) { 262cc5c4296fda7270e8394626d7254596f5f9c8d82Jakob Stoklund Olesen if (VNInfo *VNI = LI.getVNInfoAt(Idx)) { 2631e6c65dba706de80f5a4ceb8a1fc86bc3d0a61c6Jakob Stoklund Olesen if (delegate_) 2641e6c65dba706de80f5a4ceb8a1fc86bc3d0a61c6Jakob Stoklund Olesen delegate_->LRE_WillShrinkVirtReg(LI.reg); 265cc5c4296fda7270e8394626d7254596f5f9c8d82Jakob Stoklund Olesen LI.removeValNo(VNI); 266cc5c4296fda7270e8394626d7254596f5f9c8d82Jakob Stoklund Olesen if (LI.empty()) { 267cc5c4296fda7270e8394626d7254596f5f9c8d82Jakob Stoklund Olesen ToShrink.remove(&LI); 268cc5c4296fda7270e8394626d7254596f5f9c8d82Jakob Stoklund Olesen eraseVirtReg(Reg, LIS); 269cc5c4296fda7270e8394626d7254596f5f9c8d82Jakob Stoklund Olesen } 270cc5c4296fda7270e8394626d7254596f5f9c8d82Jakob Stoklund Olesen } 271cc5c4296fda7270e8394626d7254596f5f9c8d82Jakob Stoklund Olesen } 2725881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen } 2735881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 27492a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen if (delegate_) 27592a55f4bdd120cdd3bb5a004c792d4d24a940311Jakob Stoklund Olesen delegate_->LRE_WillEraseInstruction(MI); 2765881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen LIS.RemoveMachineInstrFromMaps(MI); 2775881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen MI->eraseFromParent(); 278e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumDCEDeleted; 2795881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen } 2805881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 2815881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen if (ToShrink.empty()) 2825881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen break; 2835881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 2845881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen // Shrink just one live interval. Then delete new dead defs. 2851d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen LiveInterval *LI = ToShrink.back(); 2865881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen ToShrink.pop_back(); 2871edc3cf65d54130542fc91bac67ecf616ef88d48Jakob Stoklund Olesen if (foldAsLoad(LI, Dead, MRI, LIS, TII)) 2883520019931c2bad615c35edcb943cd1e8582ebacJakob Stoklund Olesen continue; 2891d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen if (delegate_) 2901d5b84508173b93faf513032b3847152e6060791Jakob Stoklund Olesen delegate_->LRE_WillShrinkVirtReg(LI->reg); 2916a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen if (!LIS.shrinkToUses(LI, &Dead)) 2926a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen continue; 2936a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen 2946a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen // LI may have been separated, create new intervals. 2956a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen LI->RenumberValues(LIS); 2966a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen ConnectedVNInfoEqClasses ConEQ(LIS); 2976a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen unsigned NumComp = ConEQ.Classify(LI); 2986a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen if (NumComp <= 1) 2996a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen continue; 300e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumFracRanges; 3016a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen DEBUG(dbgs() << NumComp << " components: " << *LI << '\n'); 3026a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen SmallVector<LiveInterval*, 8> Dups(1, LI); 303f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen for (unsigned i = 1; i != NumComp; ++i) { 3046a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen Dups.push_back(&createFrom(LI->reg, LIS, VRM)); 305f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen if (delegate_) 306f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen delegate_->LRE_DidCloneVirtReg(Dups.back()->reg, LI->reg); 307f22ca3fe5f0cfbb832cf41270f97cf5c0134fd7bJakob Stoklund Olesen } 3081edc3cf65d54130542fc91bac67ecf616ef88d48Jakob Stoklund Olesen ConEQ.Distribute(&Dups[0], MRI); 3095881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen } 3105881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen} 3115881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 3126094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesenvoid LiveRangeEdit::calculateRegClassAndHint(MachineFunction &MF, 3136094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen LiveIntervals &LIS, 3146094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen const MachineLoopInfo &Loops) { 3156094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen VirtRegAuxInfo VRAI(MF, LIS, Loops); 3166094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen for (iterator I = begin(), E = end(); I != E; ++I) { 3176094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen LiveInterval &LI = **I; 3186094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen VRAI.CalculateRegClass(LI.reg); 3196094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen VRAI.CalculateWeightAndHint(LI); 3206094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen } 3216094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen} 322