LiveIntervalAnalysis.cpp revision 81bf03eb5cd68243eabb52505105aa5f4a831bf3
1a3b8b5c0e0a1d0942288568b2012592184ca67c5Chris Lattner//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 2ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 3ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// The LLVM Compiler Infrastructure 4ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 8ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos//===----------------------------------------------------------------------===// 9ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 10ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// This file implements the LiveInterval analysis pass which is used 11ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// by the Linear Scan Register allocator. This pass linearizes the 12ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// basic blocks of the function in DFS order and uses the 13ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// LiveVariables pass to conservatively compute live intervals for 14ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// each virtual and physical register. 15ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 16ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos//===----------------------------------------------------------------------===// 17ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 18ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#define DEBUG_TYPE "liveintervals" 193c3fe462f7978b429ecdd71750c26be25c3d1335Chris Lattner#include "llvm/CodeGen/LiveIntervalAnalysis.h" 2008a6c7614be9793754b17930ba619e875aef9585Misha Brukman#include "VirtRegMap.h" 21015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner#include "llvm/Value.h" 226d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#include "llvm/Analysis/AliasAnalysis.h" 23ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/LiveVariables.h" 24ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 25ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineInstr.h" 262578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng#include "llvm/CodeGen/MachineInstrBuilder.h" 2722f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 28c76909abfec876c6b751d693ebd3df07df686aa0Dan Gohman#include "llvm/CodeGen/MachineMemOperand.h" 2984bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 30ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/Passes.h" 31233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/ProcessImplicitDefs.h" 326f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 33ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 34ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 3595dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson#include "llvm/Target/TargetOptions.h" 36551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 37551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 387d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 397d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/raw_ostream.h" 402578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng#include "llvm/ADT/DepthFirstIterator.h" 412578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng#include "llvm/ADT/SmallSet.h" 42551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 43551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 4420aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 45f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames#include <limits> 4697af751deb9b26fd42fbcee082da9ccc4ded5b45Jeff Cohen#include <cmath> 47ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 48ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 49844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Hidden options for help debugging. 50844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> DisableReMat("disable-rematerialization", 51844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(false), cl::Hidden); 52844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 53ae339babb2a2445e7bb009912a39994718f10d54Owen Andersonstatic cl::opt<bool> EnableFastSpilling("fast-spill", 54ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson cl::init(false), cl::Hidden); 55ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson 56752195e3c662c6b5db042cf897c984624720f3b8Evan ChengSTATISTIC(numIntervals , "Number of original intervals"); 57752195e3c662c6b5db042cf897c984624720f3b8Evan ChengSTATISTIC(numFolds , "Number of loads/stores folded into instructions"); 58752195e3c662c6b5db042cf897c984624720f3b8Evan ChengSTATISTIC(numSplits , "Number of intervals split"); 59cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 601997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar LiveIntervals::ID = 0; 61844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 62ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 63f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 64845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman AU.setPreservesCFG(); 656d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addRequired<AliasAnalysis>(); 666d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addPreserved<AliasAnalysis>(); 672513330de8f8020d15d5bc96640a0957b7c733b9David Greene AU.addPreserved<LiveVariables>(); 681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LiveVariables>(); 6967d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineLoopInfoID); 7067d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineDominatorsID); 7195dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson 7295dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson if (!StrongPHIElim) { 7395dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson AU.addPreservedID(PHIEliminationID); 7495dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson AU.addRequiredID(PHIEliminationID); 7595dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson } 7695dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson 771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 78233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addPreserved<ProcessImplicitDefs>(); 79233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addRequired<ProcessImplicitDefs>(); 80233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addPreserved<SlotIndexes>(); 81233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addRequiredTransitive<SlotIndexes>(); 821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 83ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 84ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 85f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::releaseMemory() { 8603857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson // Free the live intervals themselves. 8720e2839cb975a2d4ee931e1ea4c4660a36ef0177Owen Anderson for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(), 88d6a6b3b7563a3f54ba48d465fc03ee10bbccb7a8Bob Wilson E = r2iMap_.end(); I != E; ++I) 8903857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson delete I->second; 9003857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson 911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 92ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 93dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 94991de14dd62dcbab4b31357ae22dc5b053ba50a0Benjamin Kramer VNInfoAllocator.DestroyAll(); 95752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng while (!CloneMIs.empty()) { 96752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng MachineInstr *MI = CloneMIs.back(); 97752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng CloneMIs.pop_back(); 981ed9922794cda9dbe295e74674b909287e544632Evan Cheng mf_->DeleteMachineInstr(MI); 991ed9922794cda9dbe295e74674b909287e544632Evan Cheng } 100993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 101993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 10280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// runOnMachineFunction - Register allocate the whole function 10380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// 10480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Andersonbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 10580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mf_ = &fn; 10680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mri_ = &mf_->getRegInfo(); 10780b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tm_ = &fn.getTarget(); 10880b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tri_ = tm_->getRegisterInfo(); 10980b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tii_ = tm_->getInstrInfo(); 1106d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman aa_ = &getAnalysis<AliasAnalysis>(); 11180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson lv_ = &getAnalysis<LiveVariables>(); 112233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames indexes_ = &getAnalysis<SlotIndexes>(); 11380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson allocatableRegs_ = tri_->getAllocatableSet(fn); 114ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 116ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 118843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 11970ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 1201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 121ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 122ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 12370ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 12445cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattnervoid LiveIntervals::print(raw_ostream &OS, const Module* ) const { 125705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "********** INTERVALS **********\n"; 1268e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 127705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner I->second->print(OS, tri_); 128705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "\n"; 1298e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 13070ca358b7d540b6061236ddf757085042873c12cChris Lattner 131752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printInstrs(OS); 132752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng} 133752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 134752195e3c662c6b5db042cf897c984624720f3b8Evan Chengvoid LiveIntervals::printInstrs(raw_ostream &OS) const { 135705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "********** MACHINEINSTRS **********\n"; 136705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner 1373380d5c4aaafc3d78d32f583d685d64a67ae5224Chris Lattner for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 1383380d5c4aaafc3d78d32f583d685d64a67ae5224Chris Lattner mbbi != mbbe; ++mbbi) { 1396cd8103bea5c0bc92f30b8021e9469131a2a408fJakob Stoklund Olesen OS << "BB#" << mbbi->getNumber() 1406cd8103bea5c0bc92f30b8021e9469131a2a408fJakob Stoklund Olesen << ":\t\t# derived from " << mbbi->getName() << "\n"; 1413380d5c4aaafc3d78d32f583d685d64a67ae5224Chris Lattner for (MachineBasicBlock::iterator mii = mbbi->begin(), 1423380d5c4aaafc3d78d32f583d685d64a67ae5224Chris Lattner mie = mbbi->end(); mii != mie; ++mii) { 143518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (mii->isDebugValue()) 1444507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng OS << " \t" << *mii; 1451caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen else 1461caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen OS << getInstructionIndex(mii) << '\t' << *mii; 1473380d5c4aaafc3d78d32f583d685d64a67ae5224Chris Lattner } 1483380d5c4aaafc3d78d32f583d685d64a67ae5224Chris Lattner } 14970ca358b7d540b6061236ddf757085042873c12cChris Lattner} 15070ca358b7d540b6061236ddf757085042873c12cChris Lattner 151752195e3c662c6b5db042cf897c984624720f3b8Evan Chengvoid LiveIntervals::dumpInstrs() const { 1528a34229dcf484739119857988772572ef0cad9f2David Greene printInstrs(dbgs()); 153752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng} 154752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 155cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesenbool LiveIntervals::conflictsWithPhysReg(const LiveInterval &li, 156cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen VirtRegMap &vrm, unsigned reg) { 157cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // We don't handle fancy stuff crossing basic block boundaries 158cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (li.ranges.size() != 1) 159cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen return true; 160cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen const LiveRange &range = li.ranges.front(); 161cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen SlotIndex idx = range.start.getBaseIndex(); 162cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen SlotIndex end = range.end.getPrevSlot().getBaseIndex().getNextIndex(); 163cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 164cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // Skip deleted instructions 165cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen MachineInstr *firstMI = getInstructionFromIndex(idx); 166cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen while (!firstMI && idx != end) { 167cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen idx = idx.getNextIndex(); 168cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen firstMI = getInstructionFromIndex(idx); 169cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen } 170cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (!firstMI) 171cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen return false; 172cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 173cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // Find last instruction in range 174cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen SlotIndex lastIdx = end.getPrevIndex(); 175cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen MachineInstr *lastMI = getInstructionFromIndex(lastIdx); 176cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen while (!lastMI && lastIdx != idx) { 177cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen lastIdx = lastIdx.getPrevIndex(); 178cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen lastMI = getInstructionFromIndex(lastIdx); 179cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen } 180cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (!lastMI) 181cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen return false; 182cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 183cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // Range cannot cross basic block boundaries or terminators 184cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen MachineBasicBlock *MBB = firstMI->getParent(); 185cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (MBB != lastMI->getParent() || lastMI->getDesc().isTerminator()) 186cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen return true; 187cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 188cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen MachineBasicBlock::const_iterator E = lastMI; 189cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen ++E; 190cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen for (MachineBasicBlock::const_iterator I = firstMI; I != E; ++I) { 191cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen const MachineInstr &MI = *I; 192cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 193cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // Allow copies to and from li.reg 194cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 195cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (tii_->isMoveInstr(MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 196cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (SrcReg == li.reg || DstReg == li.reg) 197cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen continue; 198cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 199cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // Check for operands using reg 200cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 201cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen const MachineOperand& mop = MI.getOperand(i); 202cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (!mop.isReg()) 203cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen continue; 204cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen unsigned PhysReg = mop.getReg(); 205cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (PhysReg == 0 || PhysReg == li.reg) 206cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen continue; 207cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { 208cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (!vrm.hasPhys(PhysReg)) 209c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 210cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen PhysReg = vrm.getPhys(PhysReg); 211c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 212cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (PhysReg && tri_->regsOverlap(PhysReg, reg)) 213cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen return true; 214c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 215c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 216c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 217cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // No conflicts found. 218c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return false; 219c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng} 220c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 221826cbac2a0cef418fd8949813761c2ed975f3df1Evan Cheng/// conflictsWithSubPhysRegRef - Similar to conflictsWithPhysRegRef except 222826cbac2a0cef418fd8949813761c2ed975f3df1Evan Cheng/// it checks for sub-register reference and it can check use as well. 223826cbac2a0cef418fd8949813761c2ed975f3df1Evan Chengbool LiveIntervals::conflictsWithSubPhysRegRef(LiveInterval &li, 2248f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng unsigned Reg, bool CheckUse, 2258f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng SmallPtrSet<MachineInstr*,32> &JoinedCopies) { 2268f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng for (LiveInterval::Ranges::const_iterator 2278f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 228233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames for (SlotIndex index = I->start.getBaseIndex(), 229233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); 230233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames index != end; 231233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames index = index.getNextIndex()) { 232f4811a96941433fc3828869d76dfeba5ec5decd3Jakob Stoklund Olesen MachineInstr *MI = getInstructionFromIndex(index); 233f4811a96941433fc3828869d76dfeba5ec5decd3Jakob Stoklund Olesen if (!MI) 234f4811a96941433fc3828869d76dfeba5ec5decd3Jakob Stoklund Olesen continue; // skip deleted instructions 2358f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 2368f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (JoinedCopies.count(MI)) 2378f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 2388f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 2398f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng MachineOperand& MO = MI->getOperand(i); 2408f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (!MO.isReg()) 2418f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 2428f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (MO.isUse() && !CheckUse) 2438f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 2448f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng unsigned PhysReg = MO.getReg(); 2458f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (PhysReg == 0 || TargetRegisterInfo::isVirtualRegister(PhysReg)) 2468f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 2478f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (tri_->isSubRegister(Reg, PhysReg)) 2488f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng return true; 2498f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 2508f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 2518f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 2528f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 2538f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng return false; 2548f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng} 2558f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 256504f9a61e61ee274fe50d8300825bdc2e5adb9b0Daniel Dunbar#ifndef NDEBUG 257752195e3c662c6b5db042cf897c984624720f3b8Evan Chengstatic void printRegName(unsigned reg, const TargetRegisterInfo* tri_) { 2586f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isPhysicalRegister(reg)) 2598a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << tri_->getName(reg); 2601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 2618a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "%reg" << reg; 262ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 263504f9a61e61ee274fe50d8300825bdc2e5adb9b0Daniel Dunbar#endif 264ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 265be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 266ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 267233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 2688651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineOperand& MO, 269ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx, 270be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 2718e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 2728a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\tregister: "; 273752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printRegName(interval.reg, tri_); 2748e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 275419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 276706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 277706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 278706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 2791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 280d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 2811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 2821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 283233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex defIndex = MIIdx.getDefIndex(); 28439faac2531268b8555475796c6071556670dc290Dale Johannesen // Earlyclobbers move back one, so that they overlap the live range 28539faac2531268b8555475796c6071556670dc290Dale Johannesen // of inputs. 28686b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen if (MO.isEarlyClobber()) 287233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames defIndex = MIIdx.getUseIndex(); 2887ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 289c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 29004ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 291518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (mi->isExtractSubreg() || mi->isInsertSubreg() || mi->isSubregToReg() || 29204ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 293c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 2945379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng // Earlyclobbers move back one. 295857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); 2967ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 2977ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(ValNo->id == 0 && "First value in interval is not 0?"); 2981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 3001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 3011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 3021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 3031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 3041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 305233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex killIdx; 3061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 307233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex(); 3081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 309233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames killIdx = defIndex.getStoreIndex(); 3101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 3121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 3131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 314493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin assert(vi.AliveBlocks.empty() && 3151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 3167ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIdx, ValNo); 3171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3188a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << "\n"); 3198651125d2885f74546b6e2a556082111d5b75da3Lang Hames ValNo->addKill(killIdx); 3201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 3211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3236097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 3241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 3251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 3261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 3271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 32874ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo); 3298a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << NewLR); 3301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 3311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 332dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen bool PHIJoin = lv_->isPHIJoin(interval.reg); 333dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 334dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen if (PHIJoin) { 335dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // A phi join register is killed at the end of the MBB and revived as a new 336dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // valno in the killing blocks. 337dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks"); 338dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " phi-join"); 339dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->addKill(indexes_->getTerminatorGap(mbb)); 340dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->setHasPHIKill(true); 341dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } else { 342dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // Iterate over all of the blocks that the variable is completely 343dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 344dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // live interval. 345dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 346dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen E = vi.AliveBlocks.end(); I != E; ++I) { 347dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I); 348dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo); 349dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen interval.addRange(LR); 350dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " +" << LR); 351dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } 3521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 3551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 3561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 3571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 358dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen SlotIndex Start = getMBBStartIdx(Kill->getParent()); 359dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen SlotIndex killIdx = getInstructionIndex(Kill).getDefIndex(); 360dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 361dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // Create interval with one of a NEW value number. Note that this value 362dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // number isn't actually defined by an instruction, weird huh? :) 363dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen if (PHIJoin) { 364dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo = interval.getNextValue(SlotIndex(Start, true), 0, false, 365dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen VNInfoAllocator); 366dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->setIsPHIDef(true); 367dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } 368dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LiveRange LR(Start, killIdx, ValNo); 3691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3708651125d2885f74546b6e2a556082111d5b75da3Lang Hames ValNo->addKill(killIdx); 3718a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 3721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 3751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 3761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 377bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 378bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 379d9df5017040489303acb57bdd8697ef0f8bafc08Bob Wilson if (mi->isRegTiedToUseOperand(MOIdx)) { 3801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 3811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 3821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 3831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 3841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 385a07cec9e24a286157541d2337cd66b24cd116586Evan Cheng assert(interval.containsOneValue()); 386233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex DefIndex = interval.getValNumInfo(0)->def.getDefIndex(); 387233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex RedefIndex = MIIdx.getDefIndex(); 388fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 389233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames RedefIndex = MIIdx.getUseIndex(); 3901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 39135f291d2c5f80e8e713704190230064311bbbbbeLang Hames const LiveRange *OldLR = 392233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames interval.getLiveRangeContaining(RedefIndex.getUseIndex()); 3937ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *OldValNo = OldLR->valno; 3944f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 3951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Delete the initial value, which should be short and continuous, 396be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 3971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 398706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 399be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Two-address vregs should always only be redefined once. This means 400be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // that at this point, there should be exactly one value number in it. 401be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 402be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 40391725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 40491725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 40552c1afcaea61440950a11a4ccadac4354420d727Lang Hames VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->getCopy(), 406857c4e01f85601cf2084adb860616256ee47c177Lang Hames false, // update at * 407c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng VNInfoAllocator); 408857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setFlags(OldValNo->getFlags()); // * <- updating here 409857c4e01f85601cf2084adb860616256ee47c177Lang Hames 41091725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 411c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->def = RedefIndex; 41252c1afcaea61440950a11a4ccadac4354420d727Lang Hames OldValNo->setCopy(0); 413be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 414be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 415be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 4168a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " replace range with " << LR); 4171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4188651125d2885f74546b6e2a556082111d5b75da3Lang Hames ValNo->addKill(RedefIndex); 4191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 4211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 4226b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) 423233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(), 424233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames OldValNo)); 4251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4268e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 4278a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << " RESULT: "; 4288a34229dcf484739119857988772572ef0cad9f2David Greene interval.print(dbgs(), tri_); 4298e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 4301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 431dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen assert(lv_->isPHIJoin(interval.reg) && "Multiply defined register"); 4321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 4331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 4341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 435dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 436233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex defIndex = MIIdx.getDefIndex(); 437fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 438233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames defIndex = MIIdx.getUseIndex(); 439752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 4407ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 441c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 44204ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 443518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (mi->isExtractSubreg() || mi->isInsertSubreg() || mi->isSubregToReg()|| 44404ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 445c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 446857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); 44791725b75852443923b419fd23215194cfc65dd88Chris Lattner 44874ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames SlotIndex killIndex = getMBBEndIdx(mbb); 4497ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 4501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 451233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames ValNo->addKill(indexes_->getTerminatorGap(mbb)); 452857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasPHIKill(true); 453dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " phi-join +" << LR); 454dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 4551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 456ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 4578a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << '\n'); 458ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 459ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 460f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 461ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 462233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 4636b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson MachineOperand& MO, 46491725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveInterval &interval, 465c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI) { 4661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 4671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 4688e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 4698a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\tregister: "; 470752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printRegName(interval.reg, tri_); 4718e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 4721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 473233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 474233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = baseIndex.getDefIndex(); 47586b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen // Earlyclobbers move back one. 47686b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen if (MO.isEarlyClobber()) 477233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames start = MIIdx.getUseIndex(); 478233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = start; 4791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 4811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 4821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 48339faac2531268b8555475796c6071556670dc290Dale Johannesen // For earlyclobbers, the defSlot was pushed back one; the extra 48439faac2531268b8555475796c6071556670dc290Dale Johannesen // advance below compensates. 4856b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) { 4868a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 487233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = start.getStoreIndex(); 488ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 4891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 490ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 4911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 4921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 4931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 494233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 4955ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 496233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 497bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen if (mi->isDebugValue()) 498bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen continue; 499233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 500233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 501233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 5026130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 5038a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " killed"); 504233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = baseIndex.getDefIndex(); 505ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 506c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 507c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_); 508c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (DefIdx != -1) { 509c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (mi->isRegTiedToUseOperand(DefIdx)) { 510c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Two-address instruction. 511233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = baseIndex.getDefIndex(); 512c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 513c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Another instruction redefines the register before it is ever read. 514bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // Then the register is essentially dead at the instruction that 515bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // defines it. Hence its interval is: 516c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // [defSlot(def), defSlot(def)+1) 5178a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 518233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = start.getStoreIndex(); 519c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 520c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng goto exit; 521c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 522f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5237fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 524233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 5251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5265ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner 5275ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 5285ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 529d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // and never used. Another possible case is the implicit use of the 530d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // physical register has been deleted by two-address pass. 531233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = start.getStoreIndex(); 53202ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 533ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 5341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 535f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 53624a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 53724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 5385379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng bool Extend = OldLR != interval.end(); 5395379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng VNInfo *ValNo = Extend 540857c4e01f85601cf2084adb860616256ee47c177Lang Hames ? OldLR->valno : interval.getNextValue(start, CopyMI, true, VNInfoAllocator); 5415379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng if (MO.isEarlyClobber() && Extend) 542857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasRedefByEC(true); 5437ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 5441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 5458651125d2885f74546b6e2a556082111d5b75da3Lang Hames LR.valno->addKill(end); 5468a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << '\n'); 547ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 548ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 549f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 550f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 551233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 552ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng MachineOperand& MO, 553ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx) { 5546b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 555ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 5566b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg())); 5576b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson else if (allocatableRegs_[MO.getReg()]) { 558c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 55904ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 560518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg() || 56104ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 562c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = MI; 563c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 5646b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg()), CopyMI); 56524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Def of a register also defines its sub-registers. 5666b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS) 5676130f66eaae89f8878590796977678afa8448926Evan Cheng // If MI also modifies the sub-register explicitly, avoid processing it 5686130f66eaae89f8878590796977678afa8448926Evan Cheng // more than once. Do not pass in TRI here so it checks for exact match. 5696130f66eaae89f8878590796977678afa8448926Evan Cheng if (!MI->modifiesRegister(*AS)) 570c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 5716b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(*AS), 0); 572f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5734d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 5744d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 575b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 576233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 57724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 5788e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 5798a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\tlivein register: "; 580752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printRegName(interval.reg, tri_); 5818e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 582b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 583b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 584b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 585b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 5864507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng MachineBasicBlock::iterator E = MBB->end(); 5874507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // Skip over DBG_VALUE at the start of the MBB. 5884507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi != E && mi->isDebugValue()) { 5894507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng while (++mi != E && mi->isDebugValue()) 5904507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng ; 5914507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi == E) 5924507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // MBB is empty except for DBG_VALUE's. 5934507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng return; 5944507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng } 5954507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng 596233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 597233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = baseIndex; 598233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 599233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 600233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 601233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = baseIndex; 6020076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng bool SeenDefUse = false; 603b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 604bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen while (mi != E) { 6051d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen if (mi->killsRegister(interval.reg, tri_)) { 6061d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen DEBUG(dbgs() << " killed"); 6071d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen end = baseIndex.getDefIndex(); 6081d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen SeenDefUse = true; 6091d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen break; 6101d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen } else if (mi->modifiesRegister(interval.reg, tri_)) { 6111d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // Another instruction redefines the register before it is ever read. 6121d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // Then the register is essentially dead at the instruction that defines 6131d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // it. Hence its interval is: 6141d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // [defSlot(def), defSlot(def)+1) 6151d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen DEBUG(dbgs() << " dead"); 6161d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen end = start.getStoreIndex(); 6171d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen SeenDefUse = true; 6181d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen break; 619bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen } 6201d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen 6214507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng while (++mi != E && mi->isDebugValue()) 6224507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // Skip over DBG_VALUE. 6234507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng ; 6244507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi != E) 625233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 626b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 627b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 62875611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 6290076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng if (!SeenDefUse) { 630292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng if (isAlias) { 6318a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 632233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = MIIdx.getStoreIndex(); 633292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } else { 6348a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " live through"); 635292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng end = baseIndex; 636292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } 63724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 63824a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 63910382fb71d8306f320ecbeb7049d25354c0e5457Lang Hames VNInfo *vni = 640233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames interval.getNextValue(SlotIndex(getMBBStartIdx(MBB), true), 6418651125d2885f74546b6e2a556082111d5b75da3Lang Hames 0, false, VNInfoAllocator); 642d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames vni->setIsPHIDef(true); 643d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames LiveRange LR(start, end, vni); 6443de23e6f6cf337451a0934159da494d645b93133Jakob Stoklund Olesen 6459b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 6468651125d2885f74546b6e2a556082111d5b75da3Lang Hames LR.valno->addKill(end); 6478a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << '\n'); 648b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 649b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 650ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 6514d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 65208cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 653ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 65491aac1015e6714d959801dd8d60f55a72827dc4dDale Johannesenvoid LiveIntervals::computeIntervals() { 6558a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n" 6568e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << "********** Function: " 6578e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'); 658d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 659d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng SmallVector<unsigned, 8> UndefUses; 660428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 661428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 662428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 66300a99a35840451a291eb61a192a750908a4073aeEvan Cheng if (MBB->empty()) 66400a99a35840451a291eb61a192a750908a4073aeEvan Cheng continue; 66500a99a35840451a291eb61a192a750908a4073aeEvan Cheng 666134eb73fc35e6ead3cfd3ed5024d0d7efa507441Owen Anderson // Track the index of the current machine instr. 667233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIndex = getMBBStartIdx(MBB); 6688a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << MBB->getName() << ":\n"); 6691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 670cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 67181bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), 672cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 673cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 674cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Multiple live-ins can alias the same register. 6756f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 676cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!hasInterval(*AS)) 677cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 678cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman true); 679dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 680dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner 68199500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson // Skip over empty initial indices. 682233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(MIIndex) == 0) 683233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 68499500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson 6851caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 6861caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen MI != miEnd; ++MI) { 6878a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << MIIndex << "\t" << *MI); 688518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isDebugValue()) 6891caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen continue; 6901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 691438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 692428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 693428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 694d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (!MO.isReg() || !MO.getReg()) 695d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng continue; 696d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 6971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 698d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (MO.isDef()) 699ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleRegisterDef(MBB, MI, MIIndex, MO, i); 700d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng else if (MO.isUndef()) 701d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng UndefUses.push_back(MO.getReg()); 7021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 7037fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 704233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Move to the next instr slot. 705233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 706ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 7071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 708d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 709d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // Create empty intervals for registers defined by implicit_def's (except 710d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // for those implicit_def that define values which are liveout of their 711d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // blocks. 712d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { 713d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng unsigned UndefReg = UndefUses[i]; 714d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng (void)getOrCreateInterval(UndefReg); 715d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng } 716ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 717b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 71803857b29d8271a23943254579e6cf7b7df4b1bd3Owen AndersonLiveInterval* LiveIntervals::createInterval(unsigned reg) { 7190a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 72003857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson return new LiveInterval(reg, Weight); 7219a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 722f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 7230a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// dupInterval - Duplicate a live interval. The caller is responsible for 7240a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// managing the allocated memory. 7250a1fcce09230e9b4bd30a8f07447aa075dce7470Evan ChengLiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 7260a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng LiveInterval *NewLI = createInterval(li->reg); 72790f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng NewLI->Copy(*li, mri_, getVNInfoAllocator()); 7280a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng return NewLI; 7290a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng} 7300a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng 731c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// getVNInfoSourceReg - Helper function that parses the specified VNInfo 732c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// copy field and returns the source register that defines it. 733c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Chengunsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 73452c1afcaea61440950a11a4ccadac4354420d727Lang Hames if (!VNI->getCopy()) 735c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 736c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 737518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (VNI->getCopy()->isExtractSubreg()) { 7388f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng // If it's extracting out of a physical register, return the sub-register. 73952c1afcaea61440950a11a4ccadac4354420d727Lang Hames unsigned Reg = VNI->getCopy()->getOperand(1).getReg(); 740ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 741ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng unsigned SrcSubReg = VNI->getCopy()->getOperand(2).getImm(); 742ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng unsigned DstSubReg = VNI->getCopy()->getOperand(0).getSubReg(); 743ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng if (SrcSubReg == DstSubReg) 744ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng // %reg1034:3<def> = EXTRACT_SUBREG %EDX, 3 745ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng // reg1034 can still be coalesced to EDX. 746ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng return Reg; 747ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng assert(DstSubReg == 0); 74852c1afcaea61440950a11a4ccadac4354420d727Lang Hames Reg = tri_->getSubReg(Reg, VNI->getCopy()->getOperand(2).getImm()); 749ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng } 7508f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng return Reg; 751518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner } else if (VNI->getCopy()->isInsertSubreg() || 752518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner VNI->getCopy()->isSubregToReg()) 75352c1afcaea61440950a11a4ccadac4354420d727Lang Hames return VNI->getCopy()->getOperand(2).getReg(); 7548f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 75504ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 75652c1afcaea61440950a11a4ccadac4354420d727Lang Hames if (tii_->isMoveInstr(*VNI->getCopy(), SrcReg, DstReg, SrcSubReg, DstSubReg)) 757c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return SrcReg; 758c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("Unrecognized copy instruction!"); 759c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 760c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng} 761f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 762f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 763f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 764f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 765f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 766d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 767d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 768d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 769d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 770d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 771d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 772d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 773d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 774d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || !MO.isUse()) 775d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 776d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 777d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 778d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 7791873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner 7801873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner if (TargetRegisterInfo::isPhysicalRegister(Reg) && 7811873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner !allocatableRegs_[Reg]) 7821873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner continue; 783d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // FIXME: For now, only remat MI with at most one register operand. 784d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng assert(!RegOp && 785d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng "Can't rematerialize instruction with multiple register operand!"); 786d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 7876d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#ifndef NDEBUG 788d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng break; 7896d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#endif 790d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 791d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 792d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 793d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 794d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 795d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 796d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 797233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx) const { 798233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index = getInstructionIndex(MI); 799d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 800d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 801d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return UI != li.end() && UI->valno == ValNo; 802d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 803d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 804f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 805f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 806f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 8075ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *ValNo, MachineInstr *MI, 808dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng SmallVectorImpl<LiveInterval*> &SpillIs, 8095ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool &isLoad) { 810f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 811f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 812f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 813a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman if (!tii_->isTriviallyReMaterializable(MI, aa_)) 814a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman return false; 815f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 816a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // Target-specific code can mark an instruction as being rematerializable 817a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // if it has one virtual reg use, though it had better be something like 818a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // a PIC base register which is likely to be live everywhere. 8196d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = getReMatImplicitUse(li, MI); 8206d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse) { 8216d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const LiveInterval &ImpLi = getInterval(ImpUse); 82228a1e486907104b85c5787345914917d74f0cf77Evan Cheng for (MachineRegisterInfo::use_nodbg_iterator 82328a1e486907104b85c5787345914917d74f0cf77Evan Cheng ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end(); 82428a1e486907104b85c5787345914917d74f0cf77Evan Cheng ri != re; ++ri) { 8256d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineInstr *UseMI = &*ri; 826233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx = getInstructionIndex(UseMI); 8276d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 8286d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman continue; 8296d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 8306d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8316d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 832dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng 833dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // If a register operand of the re-materialized instruction is going to 834dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // be spilled next, then it's not legal to re-materialize this instruction. 835dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng for (unsigned i = 0, e = SpillIs.size(); i != e; ++i) 836dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng if (ImpUse == SpillIs[i]->reg) 837dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng return false; 8386d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 8396d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return true; 8405ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 8415ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 84206587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 84306587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng/// val# of the specified interval is re-materializable. 84406587497dc1c39516f24784a2ac1d9323faae0a5Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 84506587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng const VNInfo *ValNo, MachineInstr *MI) { 84606587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng SmallVector<LiveInterval*, 4> Dummy1; 84706587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng bool Dummy2; 84806587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng return isReMaterializable(li, ValNo, MI, Dummy1, Dummy2); 84906587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng} 85006587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng 8515ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 8525ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 853dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 854dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng SmallVectorImpl<LiveInterval*> &SpillIs, 855dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng bool &isLoad) { 8565ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 8575ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 8585ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 8595ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 860857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->isUnused()) 8615ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 8625ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 863857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (!VNI->isDefAccurate()) 8645ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng return false; 865857c4e01f85601cf2084adb860616256ee47c177Lang Hames MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 8665ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 867d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 868dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 869f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 8705ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 871f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 872f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 873f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 874f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 87579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// FilterFoldedOps - Filter out two-address use operands. Return 87679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// true if it finds any issue with the operands that ought to prevent 87779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// folding. 87879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengstatic bool FilterFoldedOps(MachineInstr *MI, 87979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 88079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned &MRInfo, 88179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &FoldOps) { 88279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MRInfo = 0; 883aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 884aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned OpIdx = Ops[i]; 885d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(OpIdx); 886aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // FIXME: fold subreg use. 887d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.getSubReg()) 88879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 889d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.isDef()) 890aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isMod; 891aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 892aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Filter out two-address use operand(s). 893a24752ff43dc1ad8c18c5d9e78549c45f62b980eEvan Cheng if (MI->isRegTiedToDefOperand(OpIdx)) { 894aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo = VirtRegMap::isModRef; 895aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng continue; 896aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 897aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isRef; 898aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 899aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoldOps.push_back(OpIdx); 900e62f97c094dba44e4c259d20135167fa91912eeaEvan Cheng } 90179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 90279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng} 90379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 90479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 90579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 90679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// slot / to reg or any rematerialized load into ith operand of specified 90779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// MI. If it is successul, MI is updated with the newly created MI and 90879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// returns true. 90979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengbool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 91079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng VirtRegMap &vrm, MachineInstr *DefMI, 911233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex InstrIdx, 91279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 91379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng bool isSS, int Slot, unsigned Reg) { 91479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // If it is an implicit def instruction, just delete it. 915518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isImplicitDef()) { 91679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng RemoveMachineInstrFromMaps(MI); 91779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 91879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MI->eraseFromParent(); 91979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng ++numFolds; 92079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 92179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng } 92279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 92379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 92479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 92579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 92679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> FoldOps; 92779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 92879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 929cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 930427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // The only time it's safe to fold into a two address instruction is when 931427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // it's folding reload and spill from / into a spill stack slot. 932427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng if (DefMI && (MRInfo & VirtRegMap::isMod)) 933249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng return false; 934249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng 935f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 936f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 937f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (fmi) { 938d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng // Remember this instruction uses the spill slot. 939d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng if (isSS) vrm.addSpillSlotUse(Slot, fmi); 940d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng 941f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Attempt to fold the memory reference into the instruction. If 942f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // we can do this, we don't need to insert spill code. 943f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineBasicBlock &MBB = *MI->getParent(); 9448480293f41c11c22762164449e41cd3adb0dd7d8Evan Cheng if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 945aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 94681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.transferSpillPts(MI, fmi); 9470cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.transferRestorePts(MI, fmi); 948c1f53c742620dd4f2460685477303002bba8a8d8Evan Cheng vrm.transferEmergencySpills(MI, fmi); 949233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames ReplaceMachineInstrInMaps(MI, fmi); 950f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI = MBB.insert(MBB.erase(MI), fmi); 9510cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numFolds; 952f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 953f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 954f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 955f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 956f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 957018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// canFoldMemoryOperand - Returns true if the specified load / store 958018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// folding is possible. 959018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 96079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 9613c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng bool ReMat) const { 96279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 96379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 96479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 965018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng SmallVector<unsigned, 2> FoldOps; 96679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 96779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 968018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 9693c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng // It's only legal to remat for a use, not a def. 9703c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng if (ReMat && (MRInfo & VirtRegMap::isMod)) 97179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 972018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 973d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return tii_->canFoldMemoryOperand(MI, FoldOps); 974d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 975d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 97681a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 977233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveInterval::Ranges::const_iterator itr = li.ranges.begin(); 978233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 979233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end); 980233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 981233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (mbb == 0) 982233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return false; 983233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 984233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames for (++itr; itr != li.ranges.end(); ++itr) { 985233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineBasicBlock *mbb2 = 986233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames indexes_->getMBBCoveringRange(itr->start, itr->end); 987233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 988233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (mbb2 != mbb) 98981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 99081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 991233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 99281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return true; 99381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 99481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 995d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 996d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// interval on to-be re-materialized operands of MI) with new register. 997d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengvoid LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 998d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI, unsigned NewVReg, 999d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm) { 1000d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // There is an implicit use. That means one of the other operand is 1001d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // being remat'ed and the remat'ed instruction has li.reg as an 1002d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // use operand. Make sure we rewrite that as well. 1003d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1004d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 1005d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg()) 1006d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1007d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 1008d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1009d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1010d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!vrm.isReMaterialized(Reg)) 1011d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1012d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 10136130f66eaae89f8878590796977678afa8448926Evan Cheng MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 10146130f66eaae89f8878590796977678afa8448926Evan Cheng if (UseMO) 10156130f66eaae89f8878590796977678afa8448926Evan Cheng UseMO->setReg(NewVReg); 1016d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1017d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1018d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 1019f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 1020f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 1021018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals:: 1022d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan ChengrewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 1023233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool TrySplit, SlotIndex index, SlotIndex end, 10248651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineInstr *MI, 102581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1026f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1027f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1028d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1029f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1030f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 103122f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 1032313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 1033289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> &MBBVRegsMap, 1034c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1035018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool CanFold = false; 1036f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RestartInstruction: 1037f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1038f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineOperand& mop = MI->getOperand(i); 1039d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!mop.isReg()) 1040f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1041f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Reg = mop.getReg(); 1042f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned RegI = Reg; 10436f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1044f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1045f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (Reg != li.reg) 1046f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1047f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1048f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool TryFold = !DefIsReMat; 1049cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng bool FoldSS = true; // Default behavior unless it's a remat. 1050f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int FoldSlot = Slot; 1051f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIsReMat) { 1052f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If this is the rematerializable definition MI itself and 1053f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // all of its uses are rematerialized, simply delete it. 105481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MI == ReMatOrigDefMI && CanDelete) { 1055bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen DEBUG(dbgs() << "\t\t\t\tErasing re-materializable def: " 105628a1e486907104b85c5787345914917d74f0cf77Evan Cheng << *MI << '\n'); 1057f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RemoveMachineInstrFromMaps(MI); 1058cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng vrm.RemoveMachineInstrFromMaps(MI); 1059f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI->eraseFromParent(); 1060f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng break; 1061f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1062f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1063f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If def for this use can't be rematerialized, then try folding. 10640cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If def is rematerializable and it's a load, also try folding. 1065cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 1066f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (isLoad) { 1067f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Try fold loads (from stack slot, constant pool, etc.) into uses. 1068f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSS = isLoadSS; 1069f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSlot = LdSlot; 1070f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1071f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1072f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1073f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Scan all of the operands of this instruction rewriting operands 1074f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // to use NewVReg instead of li.reg as appropriate. We do this for 1075f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // two reasons: 1076f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1077f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1. If the instr reads the same spilled vreg multiple times, we 1078f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // want to reuse the NewVReg. 1079f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 2. If the instr is a two-addr instruction, we are required to 1080f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // keep the src/dst regs pinned. 1081f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1082f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Keep track of whether we replace a use and/or def so that we can 1083f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create the spill interval with the appropriate range. 1084cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 108581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasUse = mop.isUse(); 108681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasDef = mop.isDef(); 1087aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 1088aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(i); 1089f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 1090aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng const MachineOperand &MOj = MI->getOperand(j); 1091d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MOj.isReg()) 1092f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1093aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned RegJ = MOj.getReg(); 10946f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 1095f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1096f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (RegJ == RegI) { 1097aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1098d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (!MOj.isUndef()) { 1099d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng HasUse |= MOj.isUse(); 1100d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng HasDef |= MOj.isDef(); 1101d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng } 1102f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1103f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1104f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 110526b86a0b5676253040dc206b437536a24306fb76David Greene // Create a new virtual register for the spill interval. 110626b86a0b5676253040dc206b437536a24306fb76David Greene // Create the new register now so we can map the fold instruction 110726b86a0b5676253040dc206b437536a24306fb76David Greene // to the new register so when it is unfolded we get the correct 110826b86a0b5676253040dc206b437536a24306fb76David Greene // answer. 110926b86a0b5676253040dc206b437536a24306fb76David Greene bool CreatedNewVReg = false; 111026b86a0b5676253040dc206b437536a24306fb76David Greene if (NewVReg == 0) { 111126b86a0b5676253040dc206b437536a24306fb76David Greene NewVReg = mri_->createVirtualRegister(rc); 111226b86a0b5676253040dc206b437536a24306fb76David Greene vrm.grow(); 111326b86a0b5676253040dc206b437536a24306fb76David Greene CreatedNewVReg = true; 1114ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen 1115ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen // The new virtual register should get the same allocation hints as the 1116ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen // old one. 1117ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(Reg); 1118ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen if (Hint.first || Hint.second) 1119ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen mri_->setRegAllocationHint(NewVReg, Hint.first, Hint.second); 112026b86a0b5676253040dc206b437536a24306fb76David Greene } 112126b86a0b5676253040dc206b437536a24306fb76David Greene 11229c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!TryFold) 11239c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanFold = false; 11249c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng else { 1125018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Do not fold load / store here if we are splitting. We'll find an 1126018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // optimal point to insert a load / store later. 1127018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (!TrySplit) { 1128018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 112926b86a0b5676253040dc206b437536a24306fb76David Greene Ops, FoldSS, FoldSlot, NewVReg)) { 1130018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Folding the load/store can completely change the instruction in 1131018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // unpredictable ways, rescan it from the beginning. 113226b86a0b5676253040dc206b437536a24306fb76David Greene 113326b86a0b5676253040dc206b437536a24306fb76David Greene if (FoldSS) { 113426b86a0b5676253040dc206b437536a24306fb76David Greene // We need to give the new vreg the same stack slot as the 113526b86a0b5676253040dc206b437536a24306fb76David Greene // spilled interval. 113626b86a0b5676253040dc206b437536a24306fb76David Greene vrm.assignVirt2StackSlot(NewVReg, FoldSlot); 113726b86a0b5676253040dc206b437536a24306fb76David Greene } 113826b86a0b5676253040dc206b437536a24306fb76David Greene 1139018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasUse = false; 1140018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasDef = false; 1141018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng CanFold = false; 1142c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng if (isNotInMIMap(MI)) 11437e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng break; 1144018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng goto RestartInstruction; 1145018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1146018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } else { 11479c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // We'll try to fold it later if it's profitable. 11483c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 1149018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 11509c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng } 1151cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1152cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mop.setReg(NewVReg); 1153d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mop.isImplicit()) 1154d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1155cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1156cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Reuse NewVReg for other reads. 1157d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 1158d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &mopj = MI->getOperand(Ops[j]); 1159d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng mopj.setReg(NewVReg); 1160d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mopj.isImplicit()) 1161d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1162d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1163cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 116481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 116581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (DefIsReMat) { 1166378445303b10b092a898a75131141a8259cff50bEvan Cheng vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI); 1167d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 116881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each valnum may have its own remat id. 1169d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 117081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 1171d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 117281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 117381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!CanDelete || (HasUse && HasDef)) { 117481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a two-addr instruction then its use operands are 117581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // rematerializable but its def is not. It should be assigned a 117681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // stack slot. 117781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 117881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1179f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1180f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1181f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1182cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng } else if (HasUse && HasDef && 1183cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1184cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // If this interval hasn't been assigned a stack slot (because earlier 1185cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // def is a deleted remat def), do it now. 1186cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng assert(Slot != VirtRegMap::NO_STACK_SLOT); 1187cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1188f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1189f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1190313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Add the 1191313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // register as an implicit use on the use MI. 1192313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (DefIsReMat && ImpUse) 1193313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1194313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 11955b69ebac857104770b1a751bf7a463fda4330a62Evan Cheng // Create a new register interval for this spill / remat. 1196f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 119781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 119881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng NewLIs.push_back(&nI); 11991953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 120081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (TrySplit) 120181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(NewVReg, li.reg); 120281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1203f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1204f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasUse) { 120581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 1206233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange LR(index.getLoadIndex(), index.getDefIndex(), 1207233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator)); 12088a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 120981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 121081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 121181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Extend the split live interval to this def / use. 1212233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex End = index.getDefIndex(); 121381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 121481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getValNumInfo(nI.getNumValNums()-1)); 12158a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 121681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 121781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1218f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1219f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasDef) { 1220233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange LR(index.getDefIndex(), index.getStoreIndex(), 1221233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator)); 12228a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 1223f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.addRange(LR); 1224f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 122581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 12268e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 12278a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\t\t\tAdded new interval: "; 12288a34229dcf484739119857988772572ef0cad9f2David Greene nI.print(dbgs(), tri_); 12298a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << '\n'; 12308e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 1231f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1232018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng return CanFold; 1233f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 123481a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 12350cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng const VNInfo *VNI, 12368651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineBasicBlock *MBB, 1237233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Idx) const { 1238233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex End = getMBBEndIdx(MBB); 12390cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 1240233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (VNI->kills[j].isPHI()) 1241ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames continue; 1242ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 1243233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex KillIdx = VNI->kills[j]; 124474ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames if (KillIdx > Idx && KillIdx <= End) 12450cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng return true; 124681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 124781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 124881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 124981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1250063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// RewriteInfo - Keep track of machine instrs that will be rewritten 1251063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// during spilling. 1252844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 1253844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfo { 1254233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index; 1255844731a7f1909f55935e3514c9e713a62d67662eDan Gohman MachineInstr *MI; 1256844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasUse; 1257844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasDef; 1258233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames RewriteInfo(SlotIndex i, MachineInstr *mi, bool u, bool d) 1259844731a7f1909f55935e3514c9e713a62d67662eDan Gohman : Index(i), MI(mi), HasUse(u), HasDef(d) {} 1260844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1261844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1262844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfoCompare { 1263844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1264844731a7f1909f55935e3514c9e713a62d67662eDan Gohman return LHS.Index < RHS.Index; 1265844731a7f1909f55935e3514c9e713a62d67662eDan Gohman } 1266844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1267844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} 1268063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1269f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengvoid LiveIntervals:: 127081a038218171860ee4c382849c647d3dc841fe8bEvan ChengrewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1271f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval::Ranges::const_iterator &I, 127281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1273f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1274f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1275d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1276f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1277f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 127822f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 127981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &SpillMBBs, 1280289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes, 12810cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector &RestoreMBBs, 1282289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes, 1283289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> &MBBVRegsMap, 1284c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1285018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool AllCanFold = true; 128681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned NewVReg = 0; 1287233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = I->start.getBaseIndex(); 1288233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); 1289f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1290063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // First collect all the def / use in this live range that will be rewritten. 12917e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Make sure they are sorted according to instruction index. 1292063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::vector<RewriteInfo> RewriteMIs; 1293d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1294d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->reg_end(); ri != re; ) { 1295419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1296063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineOperand &O = ri.getOperand(); 1297063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++ri; 1298bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen if (MI->isDebugValue()) { 1299bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // Remove debug info for now. 1300bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen O.setReg(0U); 1301bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); 1302bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen continue; 1303bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen } 130424d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); 1305233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = getInstructionIndex(MI); 1306063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng if (index < start || index >= end) 1307063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng continue; 1308d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 1309d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (O.isUndef()) 131079a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // Must be defined by an implicit def. It should not be spilled. Note, 131179a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // this is for correctness reason. e.g. 131279a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 8 %reg1024<def> = IMPLICIT_DEF 131379a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 131479a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // The live range [12, 14) are not part of the r1024 live interval since 131579a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // it's defined by an implicit def. It will not conflicts with live 131679a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // interval of r1025. Now suppose both registers are spilled, you can 1317b9890ae3c35ad7d8e49261650d5b98f49f97a705Evan Cheng // easily see a situation where both registers are reloaded before 131879a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // the INSERT_SUBREG and both target registers that would overlap. 131979a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng continue; 1320063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 1321063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 1322063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1323063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1324313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 1325063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // Now rewrite the defs and uses. 1326063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 1327063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteInfo &rwi = RewriteMIs[i]; 1328063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1329233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = rwi.Index; 1330063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasUse = rwi.HasUse; 1331063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasDef = rwi.HasDef; 1332063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineInstr *MI = rwi.MI; 1333063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // If MI def and/or use the same register multiple times, then there 1334063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // are multiple entries. 1335313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned NumUses = MIHasUse; 1336063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng while (i != e && RewriteMIs[i].MI == MI) { 1337063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng assert(RewriteMIs[i].Index == index); 1338313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng bool isUse = RewriteMIs[i].HasUse; 1339313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (isUse) ++NumUses; 1340313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MIHasUse |= isUse; 1341063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MIHasDef |= RewriteMIs[i].HasDef; 1342063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1343063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 134481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1345313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 13460a891ed7d5875a9ccdb93b4472b0f43947d8289bEvan Cheng if (ImpUse && MI != ReMatDefMI) { 1347e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // Re-matting an instruction with virtual register use. Prevent interval 1348e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // from being spilled. 1349e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen getInterval(ImpUse).markNotSpillable(); 1350313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng } 1351313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1352063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned MBBId = MBB->getNumber(); 1353018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng unsigned ThisVReg = 0; 135470306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (TrySplit) { 1355289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId); 13561953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NVI != MBBVRegsMap.end()) { 1357018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = NVI->second; 13581953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // One common case: 13591953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // x = use 13601953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 13611953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 13621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // def = ... 13631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // = use 13641953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // It's better to start a new interval to avoid artifically 13651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // extend the new interval. 13661953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (MIHasDef && !MIHasUse) { 13671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.erase(MBB->getNumber()); 1368018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = 0; 13691953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 13701953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 1371cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng } 1372018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1373018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool IsNew = ThisVReg == 0; 1374018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (IsNew) { 1375018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // This ends the previous live interval. If all of its def / use 1376018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // can be folded, give it a low spill weight. 1377018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1378018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1379018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1380018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1381018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold = true; 1382018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1383018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng NewVReg = ThisVReg; 1384018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 138581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasDef = false; 138681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasUse = false; 1387d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 13889c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng index, end, MI, ReMatOrigDefMI, ReMatDefMI, 13899c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 13909c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 1391c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); 139281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!HasDef && !HasUse) 139381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 139481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1395018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold &= CanFold; 1396018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 139781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Update weight of spill interval. 139881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 139970306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (!TrySplit) { 140081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // The spill weight is now infinity as it cannot be spilled again. 1401e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen nI.markNotSpillable(); 14020cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 14030cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 14040cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 14050cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Keep track of the last def and first use in each MBB. 14060cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasDef) { 14070cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MI != ReMatOrigDefMI || !CanDelete) { 14080cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool HasKill = false; 14090cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasUse) 1410233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, index.getDefIndex()); 14110cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else { 14121953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // If this is a two-address code, then this index starts a new VNInfo. 1413233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const VNInfo *VNI = li.findDefinedVNInfoForRegInt(index.getDefIndex()); 14140cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VNI) 1415233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, index.getDefIndex()); 141681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1417289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 1418e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.find(MBBId); 14190cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasKill) { 14201953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII == SpillIdxes.end()) { 14211953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> S; 14221953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng S.push_back(SRInfo(index, NewVReg, true)); 14231953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SpillIdxes.insert(std::make_pair(MBBId, S)); 14241953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if (SII->second.back().vreg != NewVReg) { 14251953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.push_back(SRInfo(index, NewVReg, true)); 14268651125d2885f74546b6e2a556082111d5b75da3Lang Hames } else if (index > SII->second.back().index) { 14270cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If there is an earlier def and this is a two-address 14280cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // instruction, then it's not possible to fold the store (which 14290cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // would also fold the load). 14301953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SRInfo &Info = SII->second.back(); 14311953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.index = index; 14321953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.canFold = !HasUse; 143381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 14340cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs.set(MBBId); 1435e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } else if (SII != SpillIdxes.end() && 1436e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.back().vreg == NewVReg && 14378651125d2885f74546b6e2a556082111d5b75da3Lang Hames index > SII->second.back().index) { 1438e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // There is an earlier def that's not killed (must be two-address). 1439e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // The spill is no longer needed. 1440e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.pop_back(); 1441e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng if (SII->second.empty()) { 1442e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.erase(MBBId); 1443e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillMBBs.reset(MBBId); 1444e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } 144581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 144681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 14470cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 144881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 14490cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasUse) { 1450289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 14510cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillIdxes.find(MBBId); 14521953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII != SpillIdxes.end() && 14531953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().vreg == NewVReg && 14548651125d2885f74546b6e2a556082111d5b75da3Lang Hames index > SII->second.back().index) 14550cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Use(s) following the last def, it's not safe to fold the spill. 14561953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().canFold = false; 1457289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator RII = 14580cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreIdxes.find(MBBId); 14591953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 14600cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If we are splitting live intervals, only fold if it's the first 14610cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // use and there isn't another use later in the MBB. 14621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.back().canFold = false; 14630cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else if (IsNew) { 14640cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Only need a reload if there isn't an earlier def / use. 14651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII == RestoreIdxes.end()) { 14661953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> Infos; 14671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Infos.push_back(SRInfo(index, NewVReg, true)); 14681953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 14691953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else { 14701953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.push_back(SRInfo(index, NewVReg, true)); 14711953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 14720cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreMBBs.set(MBBId); 14730cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 147481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 14750cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 14760cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Update spill weight. 147722f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 1478c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1479f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1480018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1481018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1482018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // If all of its def / use can be folded, give it a low spill weight. 1483018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1484018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1485018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1486f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1487f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1488233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesbool LiveIntervals::alsoFoldARestore(int Id, SlotIndex index, 14898651125d2885f74546b6e2a556082111d5b75da3Lang Hames unsigned vr, BitVector &RestoreMBBs, 1490289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 14911953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 14921953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 14931953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 14941953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 14951953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && 14961953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].vreg == vr && 14971953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].canFold) 14981953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return true; 14991953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 15001953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 15011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1502233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveIntervals::eraseRestoreInfo(int Id, SlotIndex index, 15038651125d2885f74546b6e2a556082111d5b75da3Lang Hames unsigned vr, BitVector &RestoreMBBs, 1504289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 15051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 15061953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return; 15071953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 15081953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 15091953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && Restores[i].vreg) 1510233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames Restores[i].index = SlotIndex(); 15111953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 151281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 15134cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 15144cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// spilled and create empty intervals for their uses. 15154cce6b4c7882ef0cc993d931b90bf33985c96110Evan Chengvoid 15164cce6b4c7882ef0cc993d931b90bf33985c96110Evan ChengLiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 15174cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng const TargetRegisterClass* rc, 15184cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1519419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1520419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng re = mri_->reg_end(); ri != re; ) { 15214cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &O = ri.getOperand(); 1522419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1523419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng ++ri; 152428a1e486907104b85c5787345914917d74f0cf77Evan Cheng if (MI->isDebugValue()) { 152528a1e486907104b85c5787345914917d74f0cf77Evan Cheng // Remove debug info for now. 152628a1e486907104b85c5787345914917d74f0cf77Evan Cheng O.setReg(0U); 152728a1e486907104b85c5787345914917d74f0cf77Evan Cheng DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); 152828a1e486907104b85c5787345914917d74f0cf77Evan Cheng continue; 152928a1e486907104b85c5787345914917d74f0cf77Evan Cheng } 15304cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng if (O.isDef()) { 1531518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner assert(MI->isImplicitDef() && 15324cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng "Register def was not rewritten?"); 15334cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng RemoveMachineInstrFromMaps(MI); 15344cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 15354cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MI->eraseFromParent(); 15364cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } else { 15374cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // This must be an use of an implicit_def so it's not part of the live 15384cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // interval. Create a new empty live interval for it. 15394cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // FIXME: Can we simply erase some of the instructions? e.g. Stores? 15404cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng unsigned NewVReg = mri_->createVirtualRegister(rc); 15414cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.grow(); 15424cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.setIsImplicitlyDefined(NewVReg); 15434cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng NewLIs.push_back(&getOrCreateInterval(NewVReg)); 15444cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 15454cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &MO = MI->getOperand(i); 15464784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng if (MO.isReg() && MO.getReg() == li.reg) { 15474cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MO.setReg(NewVReg); 15484784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng MO.setIsUndef(); 15494784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng } 15504cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 15514cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 1552419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 1553419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng} 1554419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 1555e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesenfloat 1556e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund OlesenLiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { 1557e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // Limit the loop depth ridiculousness. 1558e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen if (loopDepth > 200) 1559e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen loopDepth = 200; 1560e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 1561e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // The loop depth is used to roughly estimate the number of times the 1562e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // instruction is executed. Something like 10^d is simple, but will quickly 1563e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // overflow a float. This expression behaves like 10^d for small d, but is 1564e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of 1565e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // headroom before overflow. 1566e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen float lc = powf(1 + (100.0f / (loopDepth+10)), (float)loopDepth); 1567e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 1568e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen return (isDef + isUse) * lc; 1569e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen} 1570e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 1571352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesenvoid 1572352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund OlesenLiveIntervals::normalizeSpillWeights(std::vector<LiveInterval*> &NewLIs) { 1573352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) 1574352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen normalizeSpillWeight(*NewLIs[i]); 1575352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen} 1576352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen 1577f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengstd::vector<LiveInterval*> LiveIntervals:: 1578d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen AndersonaddIntervalsForSpillsFast(const LiveInterval &li, 1579d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson const MachineLoopInfo *loopInfo, 1580c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng VirtRegMap &vrm) { 15811719731d3d8ab6a986d67912f35daaad4f6910dbOwen Anderson unsigned slot = vrm.assignVirt2StackSlot(li.reg); 1582d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1583d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson std::vector<LiveInterval*> added; 1584d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1585e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen assert(li.isSpillable() && "attempt to spill already spilled interval!"); 1586d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 15878e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 15888a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\t\t\tadding intervals for spills for interval: "; 15898e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling li.dump(); 15908a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << '\n'; 15918e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 1592d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1593d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1594d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1595a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg); 1596a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson while (RI != mri_->reg_end()) { 1597a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MachineInstr* MI = &*RI; 15988dc2cbe793ff577f69c17426d6dfaef94ad69191Owen Anderson 1599a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson SmallVector<unsigned, 2> Indices; 1600a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson bool HasUse = false; 1601a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson bool HasDef = false; 16028dc2cbe793ff577f69c17426d6dfaef94ad69191Owen Anderson 1603a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1604a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MachineOperand& mop = MI->getOperand(i); 1605d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!mop.isReg() || mop.getReg() != li.reg) continue; 1606a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1607a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson HasUse |= MI->getOperand(i).isUse(); 1608a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson HasDef |= MI->getOperand(i).isDef(); 1609a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1610a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson Indices.push_back(i); 1611d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 16121719731d3d8ab6a986d67912f35daaad4f6910dbOwen Anderson 1613a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI), 1614a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson Indices, true, slot, li.reg)) { 1615a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson unsigned NewVReg = mri_->createVirtualRegister(rc); 1616a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.grow(); 1617a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.assignVirt2StackSlot(NewVReg, slot); 1618a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1619a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // create a new register for this spill 1620a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson LiveInterval &nI = getOrCreateInterval(NewVReg); 1621e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen nI.markNotSpillable(); 1622a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1623a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // Rewrite register operands to use the new vreg. 1624a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson for (SmallVectorImpl<unsigned>::iterator I = Indices.begin(), 1625a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson E = Indices.end(); I != E; ++I) { 1626a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MI->getOperand(*I).setReg(NewVReg); 1627a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1628a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (MI->getOperand(*I).isUse()) 1629a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MI->getOperand(*I).setIsKill(true); 1630a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 1631a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1632a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // Fill in the new live interval. 1633233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = getInstructionIndex(MI); 1634a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (HasUse) { 1635233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange LR(index.getLoadIndex(), index.getUseIndex(), 1636233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.getNextValue(SlotIndex(), 0, false, 16378651125d2885f74546b6e2a556082111d5b75da3Lang Hames getVNInfoAllocator())); 16388a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 1639a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson nI.addRange(LR); 1640a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.addRestorePoint(NewVReg, MI); 1641a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 1642a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (HasDef) { 1643233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange LR(index.getDefIndex(), index.getStoreIndex(), 1644233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.getNextValue(SlotIndex(), 0, false, 16458651125d2885f74546b6e2a556082111d5b75da3Lang Hames getVNInfoAllocator())); 16468a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 1647a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson nI.addRange(LR); 1648a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.addSpillPoint(NewVReg, true, MI); 1649a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 1650a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 16511719731d3d8ab6a986d67912f35daaad4f6910dbOwen Anderson added.push_back(&nI); 16528dc2cbe793ff577f69c17426d6dfaef94ad69191Owen Anderson 16538e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 16548a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\t\t\tadded new interval: "; 16558e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling nI.dump(); 16568a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << '\n'; 16578e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 1658a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 16599a032931453209505f6765a35be108ae5ea39b3bOwen Anderson 16609a032931453209505f6765a35be108ae5ea39b3bOwen Anderson 1661a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson RI = mri_->reg_begin(li.reg); 1662d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 1663d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1664d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson return added; 1665d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson} 1666d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1667d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Andersonstd::vector<LiveInterval*> LiveIntervals:: 166881a038218171860ee4c382849c647d3dc841fe8bEvan ChengaddIntervalsForSpills(const LiveInterval &li, 1669dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng SmallVectorImpl<LiveInterval*> &SpillIs, 1670c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { 1671ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson 1672ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson if (EnableFastSpilling) 1673c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng return addIntervalsForSpillsFast(li, loopInfo, vrm); 1674ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson 1675e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen assert(li.isSpillable() && "attempt to spill already spilled interval!"); 1676f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 16778e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 16788a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\t\t\tadding intervals for spills for interval: "; 16798a34229dcf484739119857988772572ef0cad9f2David Greene li.print(dbgs(), tri_); 16808a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << '\n'; 16818e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 1682f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 168372eeb94fe1d69cd05bdbbe86b2bc9fa25c963c22Evan Cheng // Each bit specify whether a spill is required in the MBB. 168481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector SpillMBBs(mf_->getNumBlockIDs()); 1685289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes; 16860cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector RestoreMBBs(mf_->getNumBlockIDs()); 1687289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes; 1688289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> MBBVRegsMap; 1689f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> NewLIs; 1690d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1691f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1692f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned NumValNums = li.getNumValNums(); 1693f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatDefs; 1694f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDefs.resize(NumValNums, NULL); 1695f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1696f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatOrigDefs.resize(NumValNums, NULL); 1697f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> ReMatIds; 1698f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1699f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng BitVector ReMatDelete(NumValNums); 1700f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1701f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 170281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Spilling a split live interval. It cannot be split any further. Also, 170381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // it's also guaranteed to be a single val# / range interval. 170481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (vrm.getPreSplitReg(li.reg)) { 170581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(li.reg, 0); 1706d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng // Unset the split kill marker on the last use. 1707233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex KillIdx = vrm.getKillPoint(li.reg); 1708233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (KillIdx != SlotIndex()) { 1709d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1710d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillMI && "Last use disappeared?"); 1711d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1712d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillOp != -1 && "Last use disappeared?"); 1713f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner KillMI->getOperand(KillOp).setIsKill(false); 1714d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng } 1715adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng vrm.removeKillPoint(li.reg); 171681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = vrm.isReMaterialized(li.reg); 171781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot = vrm.getStackSlot(li.reg); 171881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng assert(Slot != VirtRegMap::MAX_STACK_SLOT); 171981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = DefIsReMat ? 172081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.getReMaterializedMI(li.reg) : NULL; 172181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int LdSlot = 0; 172281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 172381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoad = isLoadSS || 172415511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad())); 172581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool IsFirstRange = true; 172681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 172781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 172881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a split live interval with multiple ranges, it means there 172981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // are two-address instructions that re-defined the value. Only the 173081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // first def can be rematerialized! 173181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (IsFirstRange) { 1732cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // Note ReMatOrigDefMI has already been deleted. 173381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 173481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1735d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 17360cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1737c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 173881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 173981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, 0, 174081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, 0, false, false, false, 1741d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 17420cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1743c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 174481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 174581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng IsFirstRange = false; 174681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1747419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 17484cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 1749352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen normalizeSpillWeights(NewLIs); 175081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return NewLIs; 175181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 175281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1753752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng bool TrySplit = !intervalIsInOneMBB(li); 17540cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (TrySplit) 17550cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numSplits; 1756f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool NeedStackSlot = false; 1757f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1758f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng i != e; ++i) { 1759f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const VNInfo *VNI = *i; 1760f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned VN = VNI->id; 1761857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->isUnused()) 1762f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; // Dead val#. 1763f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Is the def for the val# rematerializable? 1764857c4e01f85601cf2084adb860616256ee47c177Lang Hames MachineInstr *ReMatDefMI = VNI->isDefAccurate() 1765857c4e01f85601cf2084adb860616256ee47c177Lang Hames ? getInstructionFromIndex(VNI->def) : 0; 17665ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool dummy; 1767dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) { 1768f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Remember how to remat the def of this val#. 176981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReMatOrigDefs[VN] = ReMatDefMI; 17702c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman // Original def may be modified so we have to make a copy here. 17711ed9922794cda9dbe295e74674b909287e544632Evan Cheng MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI); 1772752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng CloneMIs.push_back(Clone); 17731ed9922794cda9dbe295e74674b909287e544632Evan Cheng ReMatDefs[VN] = Clone; 1774f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1775f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = true; 1776857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->hasPHIKill()) { 1777c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // A kill is a phi node, not all of its uses can be rematerialized. 1778f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // It must not be deleted. 1779c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng CanDelete = false; 1780c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // Need a stack slot if there is any live range where uses cannot be 1781c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // rematerialized. 1782c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng NeedStackSlot = true; 1783f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1784f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (CanDelete) 1785f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDelete.set(VN); 1786f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1787f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Need a stack slot if there is any live range where uses cannot be 1788f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // rematerialized. 1789f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng NeedStackSlot = true; 1790f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1791f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1792f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1793f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // One stack slot per live interval. 1794b98bbb7597495fb401b020679a94389298175506Owen Anderson if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) { 1795b98bbb7597495fb401b020679a94389298175506Owen Anderson if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT) 1796b98bbb7597495fb401b020679a94389298175506Owen Anderson Slot = vrm.assignVirt2StackSlot(li.reg); 1797b98bbb7597495fb401b020679a94389298175506Owen Anderson 1798b98bbb7597495fb401b020679a94389298175506Owen Anderson // This case only occurs when the prealloc splitter has already assigned 1799b98bbb7597495fb401b020679a94389298175506Owen Anderson // a stack slot to this vreg. 1800b98bbb7597495fb401b020679a94389298175506Owen Anderson else 1801b98bbb7597495fb401b020679a94389298175506Owen Anderson Slot = vrm.getStackSlot(li.reg); 1802b98bbb7597495fb401b020679a94389298175506Owen Anderson } 1803f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1804f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Create new intervals and rewrite defs and uses. 1805f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::Ranges::const_iterator 1806f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 180781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 180881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 180981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = ReMatDefMI != NULL; 1810f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = ReMatDelete[I->valno->id]; 1811f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int LdSlot = 0; 181281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1813f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad = isLoadSS || 181415511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad()); 181581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 18160cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1817d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, 18180cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1819c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 1820f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1821f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 18220cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Insert spills / restores if we are splitting. 1823419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng if (!TrySplit) { 18244cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 1825352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen normalizeSpillWeights(NewLIs); 18261953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return NewLIs; 1827419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 18281953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1829b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng SmallPtrSet<LiveInterval*, 4> AddedKill; 1830aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 18311953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NeedStackSlot) { 18321953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = SpillMBBs.find_first(); 18331953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 18341953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &spills = SpillIdxes[Id]; 18351953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = spills.size(); i != e; ++i) { 1836233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = spills[i].index; 18371953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = spills[i].vreg; 1838597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 18390cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 18400cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1841aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1842aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool FoundUse = false; 1843aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1844cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (spills[i].canFold) { 1845aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 18460cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 18470cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineOperand &MO = MI->getOperand(j); 1848d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || MO.getReg() != VReg) 18490cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 1850aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 1851aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1852aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (MO.isDef()) 1853cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng continue; 1854aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (isReMat || 1855aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng (!FoundUse && !alsoFoldARestore(Id, index, VReg, 1856aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng RestoreMBBs, RestoreIdxes))) { 1857aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // MI has two-address uses of the same register. If the use 1858aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // isn't the first and only use in the BB, then we can't fold 1859aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // it. FIXME: Move this to rewriteInstructionsForSpills. 1860aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 1861cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng break; 1862cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 1863aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoundUse = true; 18640cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 18650cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 18660cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the store into the def if possible. 1867cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1868aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 1869aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 1870cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng Folded = true; 187148fe63526e35ddaee7e98879596a569911f41319Sebastian Redl if (FoundUse) { 1872aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Also folded uses, do not issue a load. 1873aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 1874233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.removeRange(index.getLoadIndex(), index.getDefIndex()); 1875f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng } 1876233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.removeRange(index.getDefIndex(), index.getStoreIndex()); 1877cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 18780cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 18790cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 18807e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Otherwise tell the spiller to issue a spill. 1881b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!Folded) { 1882b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 1883233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool isKill = LR->end == index.getStoreIndex(); 1884b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng if (!MI->registerDefIsDead(nI.reg)) 1885b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng // No need to spill a dead def. 1886b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng vrm.addSpillPoint(VReg, isKill, MI); 1887b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (isKill) 1888b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng AddedKill.insert(&nI); 1889b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 18900cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 18911953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = SpillMBBs.find_next(Id); 18920cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 18931953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 18940cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 18951953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = RestoreMBBs.find_first(); 18961953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 18971953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &restores = RestoreIdxes[Id]; 18981953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = restores.size(); i != e; ++i) { 1899233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = restores[i].index; 1900233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (index == SlotIndex()) 19011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng continue; 19021953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = restores[i].vreg; 1903597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 19049c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 190581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1906aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1907aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1908cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (restores[i].canFold) { 1909aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 191081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 191181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineOperand &MO = MI->getOperand(j); 1912d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || MO.getReg() != VReg) 191381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 1914aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 19150cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MO.isDef()) { 1916aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // If this restore were to be folded, it would have been folded 1917aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // already. 1918aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 191981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng break; 192081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1921aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 192281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 192381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 19240cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 19250cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the load into the use if possible. 1926cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1927aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 19289c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!isReMat) 1929aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 1930aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 19310cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 19320cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng int LdSlot = 0; 19330cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 19340cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If the rematerializable def is a load, also try to fold it. 193515511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad()) 1936aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1937aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops, isLoadSS, LdSlot, VReg); 1938650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng if (!Folded) { 1939650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 1940650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng if (ImpUse) { 1941650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng // Re-matting an instruction with virtual register use. Add the 1942e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // register as an implicit use on the use MI and mark the register 1943e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // interval as unspillable. 1944650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 1945e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen ImpLi.markNotSpillable(); 1946650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1947650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng } 1948d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1949aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 19500cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 19510cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If folding is not possible / failed, then tell the spiller to issue a 19520cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // load / rematerialization for us. 1953597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (Folded) 1954233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.removeRange(index.getLoadIndex(), index.getDefIndex()); 1955b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng else 19560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.addRestorePoint(VReg, MI); 195781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 19581953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = RestoreMBBs.find_next(Id); 195981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 196081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1961b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // Finalize intervals: add kills, finalize spill weights, and filter out 1962b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // dead intervals. 1963597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng std::vector<LiveInterval*> RetNewLIs; 1964597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 1965597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval *LI = NewLIs[i]; 1966597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (!LI->empty()) { 1967233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LI->weight /= SlotIndex::NUM * getApproximateInstructionCount(*LI); 1968b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!AddedKill.count(LI)) { 1969b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 1970233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex LastUseIdx = LR->end.getBaseIndex(); 1971d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 19726130f66eaae89f8878590796977678afa8448926Evan Cheng int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 1973b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng assert(UseIdx != -1); 1974a24752ff43dc1ad8c18c5d9e78549c45f62b980eEvan Cheng if (!LastUse->isRegTiedToDefOperand(UseIdx)) { 1975b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LastUse->getOperand(UseIdx).setIsKill(); 1976d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng vrm.addKillPoint(LI->reg, LastUseIdx); 1977adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng } 1978b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 1979597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng RetNewLIs.push_back(LI); 1980597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 1981597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 198281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 19834cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 1984352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen normalizeSpillWeights(RetNewLIs); 1985597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng return RetNewLIs; 1986f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1987676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1988676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// hasAllocatableSuperReg - Return true if the specified physical register has 1989676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// any super register that's allocatable. 1990676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengbool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 1991676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 1992676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (allocatableRegs_[*AS] && hasInterval(*AS)) 1993676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return true; 1994676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return false; 1995676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1996676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1997676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getRepresentativeReg - Find the largest super register of the specified 1998676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// physical register. 1999676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 2000676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // Find the largest super-register that is allocatable. 2001676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned BestReg = Reg; 2002676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 2003676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SuperReg = *AS; 2004676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 2005676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng BestReg = SuperReg; 2006676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng break; 2007676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2008676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2009676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return BestReg; 2010676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2011676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2012676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getNumConflictsWithPhysReg - Return the number of uses and defs of the 2013676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// specified interval that conflicts with the specified physical register. 2014676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 2015676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg) const { 2016676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned NumConflicts = 0; 2017676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 2018676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2019676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 2020676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 2021676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 202228a1e486907104b85c5787345914917d74f0cf77Evan Cheng if (MI->isDebugValue()) 202328a1e486907104b85c5787345914917d74f0cf77Evan Cheng continue; 2024233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index = getInstructionIndex(MI); 2025676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) 2026676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng ++NumConflicts; 2027676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2028676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return NumConflicts; 2029676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2030676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2031676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// spillPhysRegAroundRegDefsUses - Spill the specified physical register 20322824a655509577127d221eecd1425de196f80320Evan Cheng/// around all defs and uses of the specified interval. Return true if it 20332824a655509577127d221eecd1425de196f80320Evan Cheng/// was able to cut its interval. 20342824a655509577127d221eecd1425de196f80320Evan Chengbool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 2035676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg, VirtRegMap &vrm) { 2036676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SpillReg = getRepresentativeReg(PhysReg); 2037676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2038676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 2039676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // If there are registers which alias PhysReg, but which are not a 2040676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // sub-register of the chosen representative super register. Assert 2041676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // since we can't handle it yet. 204270f2f65aacdbc96fe158b2860b5f0bad075ee548Dan Gohman assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) || 2043676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng tri_->isSuperRegister(*AS, SpillReg)); 2044676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 20452824a655509577127d221eecd1425de196f80320Evan Cheng bool Cut = false; 20460222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng SmallVector<unsigned, 4> PRegs; 20470222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng if (hasInterval(SpillReg)) 20480222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng PRegs.push_back(SpillReg); 20490222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng else { 20500222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng SmallSet<unsigned, 4> Added; 20510222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) 20520222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng if (Added.insert(*AS) && hasInterval(*AS)) { 20530222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng PRegs.push_back(*AS); 20540222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng for (const unsigned* ASS = tri_->getSubRegisters(*AS); *ASS; ++ASS) 20550222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng Added.insert(*ASS); 20560222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng } 20570222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng } 20580222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng 2059676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SmallPtrSet<MachineInstr*, 8> SeenMIs; 2060676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2061676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 2062676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 2063676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 206428a1e486907104b85c5787345914917d74f0cf77Evan Cheng if (MI->isDebugValue() || SeenMIs.count(MI)) 2065676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 2066676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SeenMIs.insert(MI); 2067233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index = getInstructionIndex(MI); 20680222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng for (unsigned i = 0, e = PRegs.size(); i != e; ++i) { 20690222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng unsigned PReg = PRegs[i]; 20700222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng LiveInterval &pli = getInterval(PReg); 20710222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng if (!pli.liveAt(Index)) 20720222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng continue; 20730222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng vrm.addEmergencySpill(PReg, MI); 2074233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex StartIdx = Index.getLoadIndex(); 2075233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex EndIdx = Index.getNextIndex().getBaseIndex(); 20762824a655509577127d221eecd1425de196f80320Evan Cheng if (pli.isInOneLiveRange(StartIdx, EndIdx)) { 20775a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng pli.removeRange(StartIdx, EndIdx); 20782824a655509577127d221eecd1425de196f80320Evan Cheng Cut = true; 20792824a655509577127d221eecd1425de196f80320Evan Cheng } else { 20807d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin std::string msg; 20817d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin raw_string_ostream Msg(msg); 20827d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin Msg << "Ran out of registers during register allocation!"; 2083518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isInlineAsm()) { 20847d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin Msg << "\nPlease check your inline asm statement for invalid " 20850222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng << "constraints:\n"; 20867d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin MI->print(Msg, tm_); 20875a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng } 208875361b69f3f327842b9dad69fa7f28ae3b688412Chris Lattner report_fatal_error(Msg.str()); 20895a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng } 20900222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng for (const unsigned* AS = tri_->getSubRegisters(PReg); *AS; ++AS) { 2091676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasInterval(*AS)) 2092676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 2093676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng LiveInterval &spli = getInterval(*AS); 2094676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (spli.liveAt(Index)) 2095233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames spli.removeRange(Index.getLoadIndex(), 2096233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames Index.getNextIndex().getBaseIndex()); 2097676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2098676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2099676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 21002824a655509577127d221eecd1425de196f80320Evan Cheng return Cut; 2101676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2102c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 2103c4dc132c8a787fc41b6a162121251234aa618965Owen AndersonLiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 2104ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames MachineInstr* startInst) { 2105c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveInterval& Interval = getOrCreateInterval(reg); 2106c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VNInfo* VN = Interval.getNextValue( 2107233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex(getInstructionIndex(startInst).getDefIndex()), 21088651125d2885f74546b6e2a556082111d5b75da3Lang Hames startInst, true, getVNInfoAllocator()); 2109857c4e01f85601cf2084adb860616256ee47c177Lang Hames VN->setHasPHIKill(true); 2110233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames VN->kills.push_back(indexes_->getTerminatorGap(startInst->getParent())); 21118651125d2885f74546b6e2a556082111d5b75da3Lang Hames LiveRange LR( 2112233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex(getInstructionIndex(startInst).getDefIndex()), 211374ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames getMBBEndIdx(startInst->getParent()), VN); 2114c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson Interval.addRange(LR); 2115c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 2116c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson return LR; 2117c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson} 2118b5257664795d49ada0d4669fe8ed1cd49c04fbf3David Greene 2119