LiveIntervalAnalysis.cpp revision 3749943648772743c9c0e852553e50e6700a0c1b
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 265afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Chengstatic 2663749943648772743c9c0e852553e50e6700a0c1bEvan Chengbool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) { 267afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng unsigned Reg = MI.getOperand(MOIdx).getReg(); 268afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) { 269afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng const MachineOperand &MO = MI.getOperand(i); 270afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng if (!MO.isReg()) 271afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng continue; 272afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng if (MO.getReg() == Reg && MO.isDef()) { 273afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() && 274afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng MI.getOperand(MOIdx).getSubReg() && 275afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng MO.getSubReg()); 276afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return true; 277afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng } 278afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng } 279afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return false; 280afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng} 281afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng 2823749943648772743c9c0e852553e50e6700a0c1bEvan Cheng/// isPartialRedef - Return true if the specified def at the specific index is 2833749943648772743c9c0e852553e50e6700a0c1bEvan Cheng/// partially re-defining the specified live interval. A common case of this is 2843749943648772743c9c0e852553e50e6700a0c1bEvan Cheng/// a definition of the sub-register. 2853749943648772743c9c0e852553e50e6700a0c1bEvan Chengbool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO, 2863749943648772743c9c0e852553e50e6700a0c1bEvan Cheng LiveInterval &interval) { 2873749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (!MO.getSubReg() || MO.isEarlyClobber()) 2883749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return false; 2893749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 2903749943648772743c9c0e852553e50e6700a0c1bEvan Cheng SlotIndex RedefIndex = MIIdx.getDefIndex(); 2913749943648772743c9c0e852553e50e6700a0c1bEvan Cheng const LiveRange *OldLR = 2923749943648772743c9c0e852553e50e6700a0c1bEvan Cheng interval.getLiveRangeContaining(RedefIndex.getUseIndex()); 2933749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (OldLR->valno->isDefAccurate()) { 2943749943648772743c9c0e852553e50e6700a0c1bEvan Cheng MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def); 2953749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return DefMI->findRegisterDefOperandIdx(interval.reg) != -1; 2963749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } 2973749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return false; 2983749943648772743c9c0e852553e50e6700a0c1bEvan Cheng} 2993749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 300be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 301ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 302233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 3038651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineOperand& MO, 304ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx, 305be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 3068e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 3078a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\tregister: "; 308752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printRegName(interval.reg, tri_); 3098e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 310419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 311706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 312706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 313706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 3141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 315d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 3161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 3171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 318233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex defIndex = MIIdx.getDefIndex(); 31939faac2531268b8555475796c6071556670dc290Dale Johannesen // Earlyclobbers move back one, so that they overlap the live range 32039faac2531268b8555475796c6071556670dc290Dale Johannesen // of inputs. 32186b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen if (MO.isEarlyClobber()) 322233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames defIndex = MIIdx.getUseIndex(); 323c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 32404ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 325518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (mi->isExtractSubreg() || mi->isInsertSubreg() || mi->isSubregToReg() || 32604ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 327c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 3287ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 3293749943648772743c9c0e852553e50e6700a0c1bEvan Cheng VNInfo *ValNo = interval.getNextValue(defIndex, CopyMI, true, 3303749943648772743c9c0e852553e50e6700a0c1bEvan Cheng VNInfoAllocator); 3317ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(ValNo->id == 0 && "First value in interval is not 0?"); 3321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 3341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 3351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 3361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 3371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 3381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 339233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex killIdx; 3401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 341233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex(); 3421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 343233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames killIdx = defIndex.getStoreIndex(); 3441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 3461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 3471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 348493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin assert(vi.AliveBlocks.empty() && 3491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 3507ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIdx, ValNo); 3511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3528a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << "\n"); 3538651125d2885f74546b6e2a556082111d5b75da3Lang Hames ValNo->addKill(killIdx); 3541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 3551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3576097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 3581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 3591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 3601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 3611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 36274ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo); 3638a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << NewLR); 3641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 3651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 366dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen bool PHIJoin = lv_->isPHIJoin(interval.reg); 367dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 368dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen if (PHIJoin) { 369dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // A phi join register is killed at the end of the MBB and revived as a new 370dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // valno in the killing blocks. 371dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks"); 372dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " phi-join"); 373dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->addKill(indexes_->getTerminatorGap(mbb)); 374dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->setHasPHIKill(true); 375dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } else { 376dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // Iterate over all of the blocks that the variable is completely 377dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 378dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // live interval. 379dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 380dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen E = vi.AliveBlocks.end(); I != E; ++I) { 381dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I); 382dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo); 383dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen interval.addRange(LR); 384dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " +" << LR); 385dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } 3861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 3891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 3901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 3911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 392dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen SlotIndex Start = getMBBStartIdx(Kill->getParent()); 393dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen SlotIndex killIdx = getInstructionIndex(Kill).getDefIndex(); 394dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 395dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // Create interval with one of a NEW value number. Note that this value 396dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // number isn't actually defined by an instruction, weird huh? :) 397dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen if (PHIJoin) { 398dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo = interval.getNextValue(SlotIndex(Start, true), 0, false, 399dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen VNInfoAllocator); 400dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->setIsPHIDef(true); 401dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } 402dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LiveRange LR(Start, killIdx, ValNo); 4031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4048651125d2885f74546b6e2a556082111d5b75da3Lang Hames ValNo->addKill(killIdx); 4058a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 4061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 4093749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (MultipleDefsBySameMI(*mi, MOIdx)) 410afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng // Mutple defs of the same virtual register by the same instruction. e.g. 411afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng // %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ... 412afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng // This is likely due to elimination of REG_SEQUENCE instructions. Return 413afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng // here since there is nothing to do. 414afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return; 415afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng 4161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 4171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 418bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 419bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 4203749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 4213749943648772743c9c0e852553e50e6700a0c1bEvan Cheng // It may also be partial redef like this: 4223749943648772743c9c0e852553e50e6700a0c1bEvan Cheng // 80 %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0 4233749943648772743c9c0e852553e50e6700a0c1bEvan Cheng // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0 4243749943648772743c9c0e852553e50e6700a0c1bEvan Cheng bool PartReDef = isPartialRedef(MIIdx, MO, interval); 4253749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) { 4261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 4271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 4281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 4291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 4301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 4313749943648772743c9c0e852553e50e6700a0c1bEvan Cheng // Two-address vregs should always only be redefined once. This means 4323749943648772743c9c0e852553e50e6700a0c1bEvan Cheng // that at this point, there should be exactly one value number in it. 4333749943648772743c9c0e852553e50e6700a0c1bEvan Cheng assert((PartReDef || interval.containsOneValue()) && 4343749943648772743c9c0e852553e50e6700a0c1bEvan Cheng "Unexpected 2-addr liveint!"); 4353749943648772743c9c0e852553e50e6700a0c1bEvan Cheng unsigned NumVals = interval.getNumValNums(); 4363749943648772743c9c0e852553e50e6700a0c1bEvan Cheng SlotIndex DefIndex = interval.getValNumInfo(NumVals-1)->def.getDefIndex(); 437233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex RedefIndex = MIIdx.getDefIndex(); 438fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 439233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames RedefIndex = MIIdx.getUseIndex(); 4401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 44135f291d2c5f80e8e713704190230064311bbbbbeLang Hames const LiveRange *OldLR = 442233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames interval.getLiveRangeContaining(RedefIndex.getUseIndex()); 4437ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *OldValNo = OldLR->valno; 4444f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 4451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Delete the initial value, which should be short and continuous, 446be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 4471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 448706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 44991725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 45091725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 45152c1afcaea61440950a11a4ccadac4354420d727Lang Hames VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->getCopy(), 452857c4e01f85601cf2084adb860616256ee47c177Lang Hames false, // update at * 453c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng VNInfoAllocator); 454857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setFlags(OldValNo->getFlags()); // * <- updating here 455857c4e01f85601cf2084adb860616256ee47c177Lang Hames 45691725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 457c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->def = RedefIndex; 45852c1afcaea61440950a11a4ccadac4354420d727Lang Hames OldValNo->setCopy(0); 459be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 460be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 461be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 4628a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " replace range with " << LR); 4631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4648651125d2885f74546b6e2a556082111d5b75da3Lang Hames ValNo->addKill(RedefIndex); 4651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 4671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 4686b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) 469233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(), 470233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames OldValNo)); 4711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4728e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 4738a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << " RESULT: "; 4748a34229dcf484739119857988772572ef0cad9f2David Greene interval.print(dbgs(), tri_); 4758e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 4763749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } else if (lv_->isPHIJoin(interval.reg)) { 4771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 4781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 4791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 480dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 481233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex defIndex = MIIdx.getDefIndex(); 482fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 483233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames defIndex = MIIdx.getUseIndex(); 484752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 4857ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 486c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 48704ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 488518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (mi->isExtractSubreg() || mi->isInsertSubreg() || mi->isSubregToReg()|| 48904ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 490c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 491857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); 49291725b75852443923b419fd23215194cfc65dd88Chris Lattner 49374ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames SlotIndex killIndex = getMBBEndIdx(mbb); 4947ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 4951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 496233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames ValNo->addKill(indexes_->getTerminatorGap(mbb)); 497857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasPHIKill(true); 498dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " phi-join +" << LR); 4993749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } else { 5003749943648772743c9c0e852553e50e6700a0c1bEvan Cheng llvm_unreachable("Multiply defined register"); 501dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 5021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 503ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 5048a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << '\n'); 505ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 506ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 507f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 508ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 509233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 5106b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson MachineOperand& MO, 51191725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveInterval &interval, 512c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI) { 5131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 5141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 5158e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 5168a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\tregister: "; 517752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printRegName(interval.reg, tri_); 5188e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 5191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 520233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 521233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = baseIndex.getDefIndex(); 52286b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen // Earlyclobbers move back one. 52386b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen if (MO.isEarlyClobber()) 524233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames start = MIIdx.getUseIndex(); 525233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = start; 5261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 5281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 5291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 53039faac2531268b8555475796c6071556670dc290Dale Johannesen // For earlyclobbers, the defSlot was pushed back one; the extra 53139faac2531268b8555475796c6071556670dc290Dale Johannesen // advance below compensates. 5326b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) { 5338a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 534233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = start.getStoreIndex(); 535ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 5361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 537ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 5381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 5391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 5401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 541233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 5425ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 543233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 544bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen if (mi->isDebugValue()) 545bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen continue; 546233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 547233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 548233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 5496130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 5508a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " killed"); 551233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = baseIndex.getDefIndex(); 552ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 553c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 554c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_); 555c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (DefIdx != -1) { 556c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (mi->isRegTiedToUseOperand(DefIdx)) { 557c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Two-address instruction. 558233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = baseIndex.getDefIndex(); 559c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 560c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Another instruction redefines the register before it is ever read. 561bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // Then the register is essentially dead at the instruction that 562bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // defines it. Hence its interval is: 563c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // [defSlot(def), defSlot(def)+1) 5648a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 565233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = start.getStoreIndex(); 566c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 567c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng goto exit; 568c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 569f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5707fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 571233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 5721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5735ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner 5745ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 5755ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 576d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // and never used. Another possible case is the implicit use of the 577d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // physical register has been deleted by two-address pass. 578233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = start.getStoreIndex(); 57902ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 580ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 5811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 582f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 58324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 58424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 5855379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng bool Extend = OldLR != interval.end(); 5865379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng VNInfo *ValNo = Extend 587857c4e01f85601cf2084adb860616256ee47c177Lang Hames ? OldLR->valno : interval.getNextValue(start, CopyMI, true, VNInfoAllocator); 5885379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng if (MO.isEarlyClobber() && Extend) 589857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasRedefByEC(true); 5907ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 5911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 5928651125d2885f74546b6e2a556082111d5b75da3Lang Hames LR.valno->addKill(end); 5938a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << '\n'); 594ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 595ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 596f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 597f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 598233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 599ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng MachineOperand& MO, 600ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx) { 6016b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 602ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 6036b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg())); 6046b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson else if (allocatableRegs_[MO.getReg()]) { 605c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 60604ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 607518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg() || 60804ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 609c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = MI; 610c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 6116b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg()), CopyMI); 61224a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Def of a register also defines its sub-registers. 6136b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS) 6146130f66eaae89f8878590796977678afa8448926Evan Cheng // If MI also modifies the sub-register explicitly, avoid processing it 6156130f66eaae89f8878590796977678afa8448926Evan Cheng // more than once. Do not pass in TRI here so it checks for exact match. 6166130f66eaae89f8878590796977678afa8448926Evan Cheng if (!MI->modifiesRegister(*AS)) 617c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 6186b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(*AS), 0); 619f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 6204d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 6214d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 622b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 623233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 62424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 6258e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 6268a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\tlivein register: "; 627752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printRegName(interval.reg, tri_); 6288e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 629b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 630b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 631b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 632b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 6334507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng MachineBasicBlock::iterator E = MBB->end(); 6344507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // Skip over DBG_VALUE at the start of the MBB. 6354507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi != E && mi->isDebugValue()) { 6364507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng while (++mi != E && mi->isDebugValue()) 6374507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng ; 6384507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi == E) 6394507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // MBB is empty except for DBG_VALUE's. 6404507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng return; 6414507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng } 6424507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng 643233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 644233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = baseIndex; 645233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 646233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 647233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 648233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = baseIndex; 6490076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng bool SeenDefUse = false; 650b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 651bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen while (mi != E) { 6521d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen if (mi->killsRegister(interval.reg, tri_)) { 6531d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen DEBUG(dbgs() << " killed"); 6541d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen end = baseIndex.getDefIndex(); 6551d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen SeenDefUse = true; 6561d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen break; 6571d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen } else if (mi->modifiesRegister(interval.reg, tri_)) { 6581d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // Another instruction redefines the register before it is ever read. 6591d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // Then the register is essentially dead at the instruction that defines 6601d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // it. Hence its interval is: 6611d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // [defSlot(def), defSlot(def)+1) 6621d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen DEBUG(dbgs() << " dead"); 6631d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen end = start.getStoreIndex(); 6641d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen SeenDefUse = true; 6651d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen break; 666bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen } 6671d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen 6684507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng while (++mi != E && mi->isDebugValue()) 6694507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // Skip over DBG_VALUE. 6704507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng ; 6714507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi != E) 672233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 673b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 674b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 67575611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 6760076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng if (!SeenDefUse) { 677292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng if (isAlias) { 6788a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 679233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = MIIdx.getStoreIndex(); 680292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } else { 6818a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " live through"); 682292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng end = baseIndex; 683292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } 68424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 68524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 68610382fb71d8306f320ecbeb7049d25354c0e5457Lang Hames VNInfo *vni = 687233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames interval.getNextValue(SlotIndex(getMBBStartIdx(MBB), true), 6888651125d2885f74546b6e2a556082111d5b75da3Lang Hames 0, false, VNInfoAllocator); 689d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames vni->setIsPHIDef(true); 690d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames LiveRange LR(start, end, vni); 6913de23e6f6cf337451a0934159da494d645b93133Jakob Stoklund Olesen 6929b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 6938651125d2885f74546b6e2a556082111d5b75da3Lang Hames LR.valno->addKill(end); 6948a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << '\n'); 695b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 696b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 697ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 6984d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 69908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 700ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 70191aac1015e6714d959801dd8d60f55a72827dc4dDale Johannesenvoid LiveIntervals::computeIntervals() { 7028a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n" 7038e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << "********** Function: " 7048e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'); 705d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 706d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng SmallVector<unsigned, 8> UndefUses; 707428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 708428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 709428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 71000a99a35840451a291eb61a192a750908a4073aeEvan Cheng if (MBB->empty()) 71100a99a35840451a291eb61a192a750908a4073aeEvan Cheng continue; 71200a99a35840451a291eb61a192a750908a4073aeEvan Cheng 713134eb73fc35e6ead3cfd3ed5024d0d7efa507441Owen Anderson // Track the index of the current machine instr. 714233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIndex = getMBBStartIdx(MBB); 715ad98f795d0dba3db721139a8a74a98acdce0ff60Bob Wilson DEBUG(dbgs() << "BB#" << MBB->getNumber() 716ad98f795d0dba3db721139a8a74a98acdce0ff60Bob Wilson << ":\t\t# derived from " << MBB->getName() << "\n"); 7171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 718cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 71981bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), 720cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 721cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 722cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Multiple live-ins can alias the same register. 7236f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 724cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!hasInterval(*AS)) 725cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 726cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman true); 727dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 728dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner 72999500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson // Skip over empty initial indices. 730233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(MIIndex) == 0) 731233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 73299500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson 7331caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 7341caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen MI != miEnd; ++MI) { 7358a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << MIIndex << "\t" << *MI); 736518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isDebugValue()) 7371caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen continue; 7381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 739438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 740428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 741428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 742d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (!MO.isReg() || !MO.getReg()) 743d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng continue; 744d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 7451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 746d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (MO.isDef()) 747ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleRegisterDef(MBB, MI, MIIndex, MO, i); 748d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng else if (MO.isUndef()) 749d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng UndefUses.push_back(MO.getReg()); 7501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 7517fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 752233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Move to the next instr slot. 753233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 754ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 7551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 756d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 757d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // Create empty intervals for registers defined by implicit_def's (except 758d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // for those implicit_def that define values which are liveout of their 759d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // blocks. 760d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { 761d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng unsigned UndefReg = UndefUses[i]; 762d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng (void)getOrCreateInterval(UndefReg); 763d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng } 764ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 765b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 76603857b29d8271a23943254579e6cf7b7df4b1bd3Owen AndersonLiveInterval* LiveIntervals::createInterval(unsigned reg) { 7670a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 76803857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson return new LiveInterval(reg, Weight); 7699a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 770f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 7710a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// dupInterval - Duplicate a live interval. The caller is responsible for 7720a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// managing the allocated memory. 7730a1fcce09230e9b4bd30a8f07447aa075dce7470Evan ChengLiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 7740a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng LiveInterval *NewLI = createInterval(li->reg); 77590f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng NewLI->Copy(*li, mri_, getVNInfoAllocator()); 7760a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng return NewLI; 7770a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng} 7780a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng 779c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// getVNInfoSourceReg - Helper function that parses the specified VNInfo 780c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// copy field and returns the source register that defines it. 781c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Chengunsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 78252c1afcaea61440950a11a4ccadac4354420d727Lang Hames if (!VNI->getCopy()) 783c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 784c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 785518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (VNI->getCopy()->isExtractSubreg()) { 7868f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng // If it's extracting out of a physical register, return the sub-register. 78752c1afcaea61440950a11a4ccadac4354420d727Lang Hames unsigned Reg = VNI->getCopy()->getOperand(1).getReg(); 788ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 789ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng unsigned SrcSubReg = VNI->getCopy()->getOperand(2).getImm(); 790ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng unsigned DstSubReg = VNI->getCopy()->getOperand(0).getSubReg(); 791ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng if (SrcSubReg == DstSubReg) 792ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng // %reg1034:3<def> = EXTRACT_SUBREG %EDX, 3 793ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng // reg1034 can still be coalesced to EDX. 794ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng return Reg; 795ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng assert(DstSubReg == 0); 79652c1afcaea61440950a11a4ccadac4354420d727Lang Hames Reg = tri_->getSubReg(Reg, VNI->getCopy()->getOperand(2).getImm()); 797ac94863a1c090f2221ff2e21b7ee5480bd1db594Evan Cheng } 7988f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng return Reg; 799518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner } else if (VNI->getCopy()->isInsertSubreg() || 800518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner VNI->getCopy()->isSubregToReg()) 80152c1afcaea61440950a11a4ccadac4354420d727Lang Hames return VNI->getCopy()->getOperand(2).getReg(); 8028f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 80304ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 80452c1afcaea61440950a11a4ccadac4354420d727Lang Hames if (tii_->isMoveInstr(*VNI->getCopy(), SrcReg, DstReg, SrcSubReg, DstSubReg)) 805c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return SrcReg; 806c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("Unrecognized copy instruction!"); 807c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 808c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng} 809f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 810f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 811f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 812f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 813f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 814d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 815d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 816d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 817d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 818d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 819d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 820d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 821d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 822d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || !MO.isUse()) 823d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 824d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 825d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 826d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 8271873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner 8281873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner if (TargetRegisterInfo::isPhysicalRegister(Reg) && 8291873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner !allocatableRegs_[Reg]) 8301873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner continue; 831d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // FIXME: For now, only remat MI with at most one register operand. 832d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng assert(!RegOp && 833d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng "Can't rematerialize instruction with multiple register operand!"); 834d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 8356d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#ifndef NDEBUG 836d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng break; 8376d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#endif 838d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 839d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 840d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 841d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 842d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 843d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 844d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 845233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx) const { 846233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index = getInstructionIndex(MI); 847d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 848d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 849d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return UI != li.end() && UI->valno == ValNo; 850d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 851d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 852f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 853f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 854f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 8555ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *ValNo, MachineInstr *MI, 856dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng SmallVectorImpl<LiveInterval*> &SpillIs, 8575ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool &isLoad) { 858f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 859f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 860f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 861a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman if (!tii_->isTriviallyReMaterializable(MI, aa_)) 862a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman return false; 863f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 864a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // Target-specific code can mark an instruction as being rematerializable 865a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // if it has one virtual reg use, though it had better be something like 866a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // a PIC base register which is likely to be live everywhere. 8676d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = getReMatImplicitUse(li, MI); 8686d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse) { 8696d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const LiveInterval &ImpLi = getInterval(ImpUse); 87028a1e486907104b85c5787345914917d74f0cf77Evan Cheng for (MachineRegisterInfo::use_nodbg_iterator 87128a1e486907104b85c5787345914917d74f0cf77Evan Cheng ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end(); 87228a1e486907104b85c5787345914917d74f0cf77Evan Cheng ri != re; ++ri) { 8736d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineInstr *UseMI = &*ri; 874233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx = getInstructionIndex(UseMI); 8756d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 8766d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman continue; 8776d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 8786d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8796d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 880dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng 881dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // If a register operand of the re-materialized instruction is going to 882dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // be spilled next, then it's not legal to re-materialize this instruction. 883dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng for (unsigned i = 0, e = SpillIs.size(); i != e; ++i) 884dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng if (ImpUse == SpillIs[i]->reg) 885dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng return false; 8866d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 8876d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return true; 8885ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 8895ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 89006587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 89106587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng/// val# of the specified interval is re-materializable. 89206587497dc1c39516f24784a2ac1d9323faae0a5Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 89306587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng const VNInfo *ValNo, MachineInstr *MI) { 89406587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng SmallVector<LiveInterval*, 4> Dummy1; 89506587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng bool Dummy2; 89606587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng return isReMaterializable(li, ValNo, MI, Dummy1, Dummy2); 89706587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng} 89806587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng 8995ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 9005ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 901dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 902dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng SmallVectorImpl<LiveInterval*> &SpillIs, 903dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng bool &isLoad) { 9045ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 9055ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 9065ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 9075ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 908857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->isUnused()) 9095ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 9105ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 911857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (!VNI->isDefAccurate()) 9125ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng return false; 913857c4e01f85601cf2084adb860616256ee47c177Lang Hames MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 9145ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 915d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 916dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 917f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 9185ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 919f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 920f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 921f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 922f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 92379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// FilterFoldedOps - Filter out two-address use operands. Return 92479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// true if it finds any issue with the operands that ought to prevent 92579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// folding. 92679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengstatic bool FilterFoldedOps(MachineInstr *MI, 92779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 92879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned &MRInfo, 92979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &FoldOps) { 93079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MRInfo = 0; 931aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 932aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned OpIdx = Ops[i]; 933d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(OpIdx); 934aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // FIXME: fold subreg use. 935d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.getSubReg()) 93679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 937d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.isDef()) 938aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isMod; 939aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 940aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Filter out two-address use operand(s). 941a24752ff43dc1ad8c18c5d9e78549c45f62b980eEvan Cheng if (MI->isRegTiedToDefOperand(OpIdx)) { 942aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo = VirtRegMap::isModRef; 943aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng continue; 944aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 945aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isRef; 946aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 947aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoldOps.push_back(OpIdx); 948e62f97c094dba44e4c259d20135167fa91912eeaEvan Cheng } 94979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 95079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng} 95179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 95279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 95379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 95479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// slot / to reg or any rematerialized load into ith operand of specified 95579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// MI. If it is successul, MI is updated with the newly created MI and 95679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// returns true. 95779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengbool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 95879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng VirtRegMap &vrm, MachineInstr *DefMI, 959233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex InstrIdx, 96079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 96179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng bool isSS, int Slot, unsigned Reg) { 96279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // If it is an implicit def instruction, just delete it. 963518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isImplicitDef()) { 96479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng RemoveMachineInstrFromMaps(MI); 96579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 96679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MI->eraseFromParent(); 96779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng ++numFolds; 96879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 96979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng } 97079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 97179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 97279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 97379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 97479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> FoldOps; 97579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 97679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 977cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 978427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // The only time it's safe to fold into a two address instruction is when 979427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // it's folding reload and spill from / into a spill stack slot. 980427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng if (DefMI && (MRInfo & VirtRegMap::isMod)) 981249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng return false; 982249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng 983f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 984f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 985f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (fmi) { 986d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng // Remember this instruction uses the spill slot. 987d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng if (isSS) vrm.addSpillSlotUse(Slot, fmi); 988d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng 989f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Attempt to fold the memory reference into the instruction. If 990f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // we can do this, we don't need to insert spill code. 991f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineBasicBlock &MBB = *MI->getParent(); 9928480293f41c11c22762164449e41cd3adb0dd7d8Evan Cheng if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 993aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 99481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.transferSpillPts(MI, fmi); 9950cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.transferRestorePts(MI, fmi); 996c1f53c742620dd4f2460685477303002bba8a8d8Evan Cheng vrm.transferEmergencySpills(MI, fmi); 997233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames ReplaceMachineInstrInMaps(MI, fmi); 998f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI = MBB.insert(MBB.erase(MI), fmi); 9990cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numFolds; 1000f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 1001f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1002f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 1003f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1004f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1005018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// canFoldMemoryOperand - Returns true if the specified load / store 1006018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// folding is possible. 1007018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 100879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 10093c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng bool ReMat) const { 101079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 101179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 101279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 1013018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng SmallVector<unsigned, 2> FoldOps; 101479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 101579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 1016018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 10173c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng // It's only legal to remat for a use, not a def. 10183c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng if (ReMat && (MRInfo & VirtRegMap::isMod)) 101979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 1020018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1021d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return tii_->canFoldMemoryOperand(MI, FoldOps); 1022d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1023d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 102481a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 1025233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveInterval::Ranges::const_iterator itr = li.ranges.begin(); 1026233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 1027233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end); 1028233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 1029233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (mbb == 0) 1030233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return false; 1031233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 1032233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames for (++itr; itr != li.ranges.end(); ++itr) { 1033233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineBasicBlock *mbb2 = 1034233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames indexes_->getMBBCoveringRange(itr->start, itr->end); 1035233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 1036233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (mbb2 != mbb) 103781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 103881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1039233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 104081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return true; 104181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 104281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1043d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 1044d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// interval on to-be re-materialized operands of MI) with new register. 1045d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengvoid LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 1046d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI, unsigned NewVReg, 1047d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm) { 1048d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // There is an implicit use. That means one of the other operand is 1049d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // being remat'ed and the remat'ed instruction has li.reg as an 1050d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // use operand. Make sure we rewrite that as well. 1051d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1052d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 1053d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg()) 1054d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1055d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 1056d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1057d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1058d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!vrm.isReMaterialized(Reg)) 1059d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1060d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 10616130f66eaae89f8878590796977678afa8448926Evan Cheng MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 10626130f66eaae89f8878590796977678afa8448926Evan Cheng if (UseMO) 10636130f66eaae89f8878590796977678afa8448926Evan Cheng UseMO->setReg(NewVReg); 1064d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1065d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1066d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 1067f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 1068f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 1069018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals:: 1070d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan ChengrewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 1071233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool TrySplit, SlotIndex index, SlotIndex end, 10728651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineInstr *MI, 107381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1074f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1075f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1076d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1077f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1078f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 107922f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 1080313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 1081289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> &MBBVRegsMap, 1082c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1083018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool CanFold = false; 1084f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RestartInstruction: 1085f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1086f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineOperand& mop = MI->getOperand(i); 1087d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!mop.isReg()) 1088f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1089f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Reg = mop.getReg(); 1090f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned RegI = Reg; 10916f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1092f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1093f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (Reg != li.reg) 1094f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1095f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1096f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool TryFold = !DefIsReMat; 1097cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng bool FoldSS = true; // Default behavior unless it's a remat. 1098f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int FoldSlot = Slot; 1099f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIsReMat) { 1100f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If this is the rematerializable definition MI itself and 1101f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // all of its uses are rematerialized, simply delete it. 110281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MI == ReMatOrigDefMI && CanDelete) { 1103bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen DEBUG(dbgs() << "\t\t\t\tErasing re-materializable def: " 110428a1e486907104b85c5787345914917d74f0cf77Evan Cheng << *MI << '\n'); 1105f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RemoveMachineInstrFromMaps(MI); 1106cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng vrm.RemoveMachineInstrFromMaps(MI); 1107f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI->eraseFromParent(); 1108f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng break; 1109f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1110f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1111f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If def for this use can't be rematerialized, then try folding. 11120cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If def is rematerializable and it's a load, also try folding. 1113cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 1114f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (isLoad) { 1115f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Try fold loads (from stack slot, constant pool, etc.) into uses. 1116f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSS = isLoadSS; 1117f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSlot = LdSlot; 1118f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1119f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1120f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1121f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Scan all of the operands of this instruction rewriting operands 1122f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // to use NewVReg instead of li.reg as appropriate. We do this for 1123f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // two reasons: 1124f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1125f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1. If the instr reads the same spilled vreg multiple times, we 1126f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // want to reuse the NewVReg. 1127f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 2. If the instr is a two-addr instruction, we are required to 1128f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // keep the src/dst regs pinned. 1129f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1130f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Keep track of whether we replace a use and/or def so that we can 1131f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create the spill interval with the appropriate range. 1132cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 113381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasUse = mop.isUse(); 113481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasDef = mop.isDef(); 1135aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 1136aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(i); 1137f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 1138aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng const MachineOperand &MOj = MI->getOperand(j); 1139d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MOj.isReg()) 1140f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1141aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned RegJ = MOj.getReg(); 11426f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 1143f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1144f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (RegJ == RegI) { 1145aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1146d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (!MOj.isUndef()) { 1147d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng HasUse |= MOj.isUse(); 1148d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng HasDef |= MOj.isDef(); 1149d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng } 1150f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1151f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1152f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 115326b86a0b5676253040dc206b437536a24306fb76David Greene // Create a new virtual register for the spill interval. 115426b86a0b5676253040dc206b437536a24306fb76David Greene // Create the new register now so we can map the fold instruction 115526b86a0b5676253040dc206b437536a24306fb76David Greene // to the new register so when it is unfolded we get the correct 115626b86a0b5676253040dc206b437536a24306fb76David Greene // answer. 115726b86a0b5676253040dc206b437536a24306fb76David Greene bool CreatedNewVReg = false; 115826b86a0b5676253040dc206b437536a24306fb76David Greene if (NewVReg == 0) { 115926b86a0b5676253040dc206b437536a24306fb76David Greene NewVReg = mri_->createVirtualRegister(rc); 116026b86a0b5676253040dc206b437536a24306fb76David Greene vrm.grow(); 116126b86a0b5676253040dc206b437536a24306fb76David Greene CreatedNewVReg = true; 1162ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen 1163ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen // The new virtual register should get the same allocation hints as the 1164ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen // old one. 1165ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(Reg); 1166ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen if (Hint.first || Hint.second) 1167ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen mri_->setRegAllocationHint(NewVReg, Hint.first, Hint.second); 116826b86a0b5676253040dc206b437536a24306fb76David Greene } 116926b86a0b5676253040dc206b437536a24306fb76David Greene 11709c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!TryFold) 11719c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanFold = false; 11729c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng else { 1173018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Do not fold load / store here if we are splitting. We'll find an 1174018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // optimal point to insert a load / store later. 1175018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (!TrySplit) { 1176018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 117726b86a0b5676253040dc206b437536a24306fb76David Greene Ops, FoldSS, FoldSlot, NewVReg)) { 1178018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Folding the load/store can completely change the instruction in 1179018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // unpredictable ways, rescan it from the beginning. 118026b86a0b5676253040dc206b437536a24306fb76David Greene 118126b86a0b5676253040dc206b437536a24306fb76David Greene if (FoldSS) { 118226b86a0b5676253040dc206b437536a24306fb76David Greene // We need to give the new vreg the same stack slot as the 118326b86a0b5676253040dc206b437536a24306fb76David Greene // spilled interval. 118426b86a0b5676253040dc206b437536a24306fb76David Greene vrm.assignVirt2StackSlot(NewVReg, FoldSlot); 118526b86a0b5676253040dc206b437536a24306fb76David Greene } 118626b86a0b5676253040dc206b437536a24306fb76David Greene 1187018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasUse = false; 1188018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasDef = false; 1189018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng CanFold = false; 1190c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng if (isNotInMIMap(MI)) 11917e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng break; 1192018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng goto RestartInstruction; 1193018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1194018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } else { 11959c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // We'll try to fold it later if it's profitable. 11963c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 1197018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 11989c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng } 1199cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1200cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mop.setReg(NewVReg); 1201d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mop.isImplicit()) 1202d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1203cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1204cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Reuse NewVReg for other reads. 1205d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 1206d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &mopj = MI->getOperand(Ops[j]); 1207d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng mopj.setReg(NewVReg); 1208d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mopj.isImplicit()) 1209d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1210d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1211cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 121281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 121381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (DefIsReMat) { 1214378445303b10b092a898a75131141a8259cff50bEvan Cheng vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI); 1215d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 121681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each valnum may have its own remat id. 1217d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 121881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 1219d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 122081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 122181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!CanDelete || (HasUse && HasDef)) { 122281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a two-addr instruction then its use operands are 122381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // rematerializable but its def is not. It should be assigned a 122481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // stack slot. 122581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 122681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1227f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1228f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1229f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1230cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng } else if (HasUse && HasDef && 1231cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1232cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // If this interval hasn't been assigned a stack slot (because earlier 1233cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // def is a deleted remat def), do it now. 1234cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng assert(Slot != VirtRegMap::NO_STACK_SLOT); 1235cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1236f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1237f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1238313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Add the 1239313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // register as an implicit use on the use MI. 1240313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (DefIsReMat && ImpUse) 1241313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1242313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 12435b69ebac857104770b1a751bf7a463fda4330a62Evan Cheng // Create a new register interval for this spill / remat. 1244f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 124581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 124681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng NewLIs.push_back(&nI); 12471953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 124881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (TrySplit) 124981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(NewVReg, li.reg); 125081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1251f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1252f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasUse) { 125381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 1254233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange LR(index.getLoadIndex(), index.getDefIndex(), 1255233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator)); 12568a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 125781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 125881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 125981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Extend the split live interval to this def / use. 1260233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex End = index.getDefIndex(); 126181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 126281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getValNumInfo(nI.getNumValNums()-1)); 12638a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 126481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 126581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1266f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1267f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasDef) { 1268233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange LR(index.getDefIndex(), index.getStoreIndex(), 1269233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator)); 12708a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 1271f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.addRange(LR); 1272f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 127381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 12748e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 12758a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\t\t\tAdded new interval: "; 12768a34229dcf484739119857988772572ef0cad9f2David Greene nI.print(dbgs(), tri_); 12778a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << '\n'; 12788e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 1279f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1280018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng return CanFold; 1281f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 128281a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 12830cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng const VNInfo *VNI, 12848651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineBasicBlock *MBB, 1285233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Idx) const { 1286233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex End = getMBBEndIdx(MBB); 12870cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 1288233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (VNI->kills[j].isPHI()) 1289ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames continue; 1290ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 1291233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex KillIdx = VNI->kills[j]; 129274ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames if (KillIdx > Idx && KillIdx <= End) 12930cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng return true; 129481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 129581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 129681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 129781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1298063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// RewriteInfo - Keep track of machine instrs that will be rewritten 1299063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// during spilling. 1300844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 1301844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfo { 1302233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index; 1303844731a7f1909f55935e3514c9e713a62d67662eDan Gohman MachineInstr *MI; 1304844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasUse; 1305844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasDef; 1306233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames RewriteInfo(SlotIndex i, MachineInstr *mi, bool u, bool d) 1307844731a7f1909f55935e3514c9e713a62d67662eDan Gohman : Index(i), MI(mi), HasUse(u), HasDef(d) {} 1308844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1309844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1310844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfoCompare { 1311844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1312844731a7f1909f55935e3514c9e713a62d67662eDan Gohman return LHS.Index < RHS.Index; 1313844731a7f1909f55935e3514c9e713a62d67662eDan Gohman } 1314844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1315844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} 1316063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1317f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengvoid LiveIntervals:: 131881a038218171860ee4c382849c647d3dc841fe8bEvan ChengrewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1319f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval::Ranges::const_iterator &I, 132081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1321f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1322f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1323d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1324f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1325f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 132622f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 132781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &SpillMBBs, 1328289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes, 13290cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector &RestoreMBBs, 1330289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes, 1331289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> &MBBVRegsMap, 1332c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1333018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool AllCanFold = true; 133481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned NewVReg = 0; 1335233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = I->start.getBaseIndex(); 1336233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); 1337f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1338063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // First collect all the def / use in this live range that will be rewritten. 13397e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Make sure they are sorted according to instruction index. 1340063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::vector<RewriteInfo> RewriteMIs; 1341d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1342d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->reg_end(); ri != re; ) { 1343419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1344063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineOperand &O = ri.getOperand(); 1345063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++ri; 1346bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen if (MI->isDebugValue()) { 1347962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng // Modify DBG_VALUE now that the value is in a spill slot. 13486691a8935c9f2e049ff5eed45ba2894f60108909Evan Cheng if (Slot != VirtRegMap::MAX_STACK_SLOT || isLoadSS) { 13496fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng uint64_t Offset = MI->getOperand(1).getImm(); 13506fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng const MDNode *MDPtr = MI->getOperand(2).getMetadata(); 13516fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng DebugLoc DL = MI->getDebugLoc(); 13526691a8935c9f2e049ff5eed45ba2894f60108909Evan Cheng int FI = isLoadSS ? LdSlot : (int)Slot; 13536691a8935c9f2e049ff5eed45ba2894f60108909Evan Cheng if (MachineInstr *NewDV = tii_->emitFrameIndexDebugValue(*mf_, FI, 13546fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng Offset, MDPtr, DL)) { 13556fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI); 13566fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng ReplaceMachineInstrInMaps(MI, NewDV); 13576fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 13586fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng MBB->insert(MBB->erase(MI), NewDV); 13596fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng continue; 13606fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng } 1361962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng } 13626fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng 13636fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); 13646fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng RemoveMachineInstrFromMaps(MI); 13656fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 13666fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng MI->eraseFromParent(); 1367bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen continue; 1368bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen } 136924d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); 1370233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = getInstructionIndex(MI); 1371063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng if (index < start || index >= end) 1372063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng continue; 1373d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 1374d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (O.isUndef()) 137579a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // Must be defined by an implicit def. It should not be spilled. Note, 137679a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // this is for correctness reason. e.g. 137779a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 8 %reg1024<def> = IMPLICIT_DEF 137879a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 137979a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // The live range [12, 14) are not part of the r1024 live interval since 138079a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // it's defined by an implicit def. It will not conflicts with live 138179a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // interval of r1025. Now suppose both registers are spilled, you can 1382b9890ae3c35ad7d8e49261650d5b98f49f97a705Evan Cheng // easily see a situation where both registers are reloaded before 138379a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // the INSERT_SUBREG and both target registers that would overlap. 138479a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng continue; 1385063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 1386063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 1387063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1388063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1389313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 1390063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // Now rewrite the defs and uses. 1391063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 1392063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteInfo &rwi = RewriteMIs[i]; 1393063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1394233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = rwi.Index; 1395063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasUse = rwi.HasUse; 1396063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasDef = rwi.HasDef; 1397063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineInstr *MI = rwi.MI; 1398063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // If MI def and/or use the same register multiple times, then there 1399063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // are multiple entries. 1400313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned NumUses = MIHasUse; 1401063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng while (i != e && RewriteMIs[i].MI == MI) { 1402063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng assert(RewriteMIs[i].Index == index); 1403313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng bool isUse = RewriteMIs[i].HasUse; 1404313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (isUse) ++NumUses; 1405313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MIHasUse |= isUse; 1406063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MIHasDef |= RewriteMIs[i].HasDef; 1407063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1408063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 140981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1410313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 14110a891ed7d5875a9ccdb93b4472b0f43947d8289bEvan Cheng if (ImpUse && MI != ReMatDefMI) { 1412e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // Re-matting an instruction with virtual register use. Prevent interval 1413e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // from being spilled. 1414e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen getInterval(ImpUse).markNotSpillable(); 1415313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng } 1416313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1417063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned MBBId = MBB->getNumber(); 1418018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng unsigned ThisVReg = 0; 141970306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (TrySplit) { 1420289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId); 14211953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NVI != MBBVRegsMap.end()) { 1422018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = NVI->second; 14231953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // One common case: 14241953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // x = use 14251953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 14261953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 14271953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // def = ... 14281953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // = use 14291953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // It's better to start a new interval to avoid artifically 14301953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // extend the new interval. 14311953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (MIHasDef && !MIHasUse) { 14321953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.erase(MBB->getNumber()); 1433018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = 0; 14341953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 14351953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 1436cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng } 1437018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1438018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool IsNew = ThisVReg == 0; 1439018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (IsNew) { 1440018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // This ends the previous live interval. If all of its def / use 1441018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // can be folded, give it a low spill weight. 1442018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1443018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1444018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1445018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1446018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold = true; 1447018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1448018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng NewVReg = ThisVReg; 1449018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 145081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasDef = false; 145181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasUse = false; 1452d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 14539c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng index, end, MI, ReMatOrigDefMI, ReMatDefMI, 14549c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 14559c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 1456c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); 145781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!HasDef && !HasUse) 145881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 145981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1460018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold &= CanFold; 1461018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 146281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Update weight of spill interval. 146381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 146470306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (!TrySplit) { 146581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // The spill weight is now infinity as it cannot be spilled again. 1466e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen nI.markNotSpillable(); 14670cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 14680cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 14690cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 14700cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Keep track of the last def and first use in each MBB. 14710cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasDef) { 14720cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MI != ReMatOrigDefMI || !CanDelete) { 14730cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool HasKill = false; 14740cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasUse) 1475233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, index.getDefIndex()); 14760cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else { 14771953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // If this is a two-address code, then this index starts a new VNInfo. 1478233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const VNInfo *VNI = li.findDefinedVNInfoForRegInt(index.getDefIndex()); 14790cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VNI) 1480233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, index.getDefIndex()); 148181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1482289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 1483e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.find(MBBId); 14840cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasKill) { 14851953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII == SpillIdxes.end()) { 14861953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> S; 14871953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng S.push_back(SRInfo(index, NewVReg, true)); 14881953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SpillIdxes.insert(std::make_pair(MBBId, S)); 14891953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if (SII->second.back().vreg != NewVReg) { 14901953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.push_back(SRInfo(index, NewVReg, true)); 14918651125d2885f74546b6e2a556082111d5b75da3Lang Hames } else if (index > SII->second.back().index) { 14920cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If there is an earlier def and this is a two-address 14930cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // instruction, then it's not possible to fold the store (which 14940cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // would also fold the load). 14951953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SRInfo &Info = SII->second.back(); 14961953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.index = index; 14971953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.canFold = !HasUse; 149881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 14990cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs.set(MBBId); 1500e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } else if (SII != SpillIdxes.end() && 1501e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.back().vreg == NewVReg && 15028651125d2885f74546b6e2a556082111d5b75da3Lang Hames index > SII->second.back().index) { 1503e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // There is an earlier def that's not killed (must be two-address). 1504e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // The spill is no longer needed. 1505e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.pop_back(); 1506e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng if (SII->second.empty()) { 1507e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.erase(MBBId); 1508e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillMBBs.reset(MBBId); 1509e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } 151081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 151181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 15120cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 151381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 15140cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasUse) { 1515289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 15160cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillIdxes.find(MBBId); 15171953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII != SpillIdxes.end() && 15181953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().vreg == NewVReg && 15198651125d2885f74546b6e2a556082111d5b75da3Lang Hames index > SII->second.back().index) 15200cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Use(s) following the last def, it's not safe to fold the spill. 15211953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().canFold = false; 1522289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator RII = 15230cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreIdxes.find(MBBId); 15241953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 15250cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If we are splitting live intervals, only fold if it's the first 15260cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // use and there isn't another use later in the MBB. 15271953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.back().canFold = false; 15280cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else if (IsNew) { 15290cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Only need a reload if there isn't an earlier def / use. 15301953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII == RestoreIdxes.end()) { 15311953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> Infos; 15321953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Infos.push_back(SRInfo(index, NewVReg, true)); 15331953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 15341953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else { 15351953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.push_back(SRInfo(index, NewVReg, true)); 15361953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 15370cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreMBBs.set(MBBId); 15380cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 153981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 15400cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 15410cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Update spill weight. 154222f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 1543c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1544f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1545018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1546018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1547018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // If all of its def / use can be folded, give it a low spill weight. 1548018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1549018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1550018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1551f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1552f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1553233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesbool LiveIntervals::alsoFoldARestore(int Id, SlotIndex index, 15548651125d2885f74546b6e2a556082111d5b75da3Lang Hames unsigned vr, BitVector &RestoreMBBs, 1555289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 15561953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 15571953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 15581953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 15591953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 15601953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && 15611953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].vreg == vr && 15621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].canFold) 15631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return true; 15641953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 15651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 15661953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1567233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveIntervals::eraseRestoreInfo(int Id, SlotIndex index, 15688651125d2885f74546b6e2a556082111d5b75da3Lang Hames unsigned vr, BitVector &RestoreMBBs, 1569289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 15701953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 15711953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return; 15721953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 15731953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 15741953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && Restores[i].vreg) 1575233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames Restores[i].index = SlotIndex(); 15761953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 157781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 15784cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 15794cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// spilled and create empty intervals for their uses. 15804cce6b4c7882ef0cc993d931b90bf33985c96110Evan Chengvoid 15814cce6b4c7882ef0cc993d931b90bf33985c96110Evan ChengLiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 15824cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng const TargetRegisterClass* rc, 15834cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1584419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1585419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng re = mri_->reg_end(); ri != re; ) { 15864cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &O = ri.getOperand(); 1587419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1588419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng ++ri; 158928a1e486907104b85c5787345914917d74f0cf77Evan Cheng if (MI->isDebugValue()) { 159028a1e486907104b85c5787345914917d74f0cf77Evan Cheng // Remove debug info for now. 159128a1e486907104b85c5787345914917d74f0cf77Evan Cheng O.setReg(0U); 159228a1e486907104b85c5787345914917d74f0cf77Evan Cheng DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); 159328a1e486907104b85c5787345914917d74f0cf77Evan Cheng continue; 159428a1e486907104b85c5787345914917d74f0cf77Evan Cheng } 15954cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng if (O.isDef()) { 1596518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner assert(MI->isImplicitDef() && 15974cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng "Register def was not rewritten?"); 15984cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng RemoveMachineInstrFromMaps(MI); 15994cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 16004cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MI->eraseFromParent(); 16014cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } else { 16024cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // This must be an use of an implicit_def so it's not part of the live 16034cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // interval. Create a new empty live interval for it. 16044cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // FIXME: Can we simply erase some of the instructions? e.g. Stores? 16054cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng unsigned NewVReg = mri_->createVirtualRegister(rc); 16064cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.grow(); 16074cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.setIsImplicitlyDefined(NewVReg); 16084cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng NewLIs.push_back(&getOrCreateInterval(NewVReg)); 16094cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 16104cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &MO = MI->getOperand(i); 16114784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng if (MO.isReg() && MO.getReg() == li.reg) { 16124cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MO.setReg(NewVReg); 16134784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng MO.setIsUndef(); 16144784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng } 16154cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 16164cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 1617419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 1618419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng} 1619419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 1620e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesenfloat 1621e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund OlesenLiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { 1622e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // Limit the loop depth ridiculousness. 1623e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen if (loopDepth > 200) 1624e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen loopDepth = 200; 1625e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 1626e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // The loop depth is used to roughly estimate the number of times the 1627e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // instruction is executed. Something like 10^d is simple, but will quickly 1628e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // overflow a float. This expression behaves like 10^d for small d, but is 1629e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of 1630e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // headroom before overflow. 1631e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen float lc = powf(1 + (100.0f / (loopDepth+10)), (float)loopDepth); 1632e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 1633e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen return (isDef + isUse) * lc; 1634e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen} 1635e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 1636352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesenvoid 1637352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund OlesenLiveIntervals::normalizeSpillWeights(std::vector<LiveInterval*> &NewLIs) { 1638352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) 1639352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen normalizeSpillWeight(*NewLIs[i]); 1640352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen} 1641352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen 1642f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengstd::vector<LiveInterval*> LiveIntervals:: 1643d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen AndersonaddIntervalsForSpillsFast(const LiveInterval &li, 1644d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson const MachineLoopInfo *loopInfo, 1645c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng VirtRegMap &vrm) { 16461719731d3d8ab6a986d67912f35daaad4f6910dbOwen Anderson unsigned slot = vrm.assignVirt2StackSlot(li.reg); 1647d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1648d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson std::vector<LiveInterval*> added; 1649d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1650e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen assert(li.isSpillable() && "attempt to spill already spilled interval!"); 1651d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 16528e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 16538a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\t\t\tadding intervals for spills for interval: "; 16548e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling li.dump(); 16558a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << '\n'; 16568e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 1657d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1658d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1659d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1660a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg); 1661a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson while (RI != mri_->reg_end()) { 1662a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MachineInstr* MI = &*RI; 16638dc2cbe793ff577f69c17426d6dfaef94ad69191Owen Anderson 1664a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson SmallVector<unsigned, 2> Indices; 1665a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson bool HasUse = false; 1666a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson bool HasDef = false; 16678dc2cbe793ff577f69c17426d6dfaef94ad69191Owen Anderson 1668a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1669a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MachineOperand& mop = MI->getOperand(i); 1670d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!mop.isReg() || mop.getReg() != li.reg) continue; 1671a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1672a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson HasUse |= MI->getOperand(i).isUse(); 1673a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson HasDef |= MI->getOperand(i).isDef(); 1674a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1675a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson Indices.push_back(i); 1676d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 16771719731d3d8ab6a986d67912f35daaad4f6910dbOwen Anderson 1678a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI), 1679a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson Indices, true, slot, li.reg)) { 1680a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson unsigned NewVReg = mri_->createVirtualRegister(rc); 1681a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.grow(); 1682a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.assignVirt2StackSlot(NewVReg, slot); 1683a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1684a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // create a new register for this spill 1685a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson LiveInterval &nI = getOrCreateInterval(NewVReg); 1686e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen nI.markNotSpillable(); 1687a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1688a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // Rewrite register operands to use the new vreg. 1689a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson for (SmallVectorImpl<unsigned>::iterator I = Indices.begin(), 1690a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson E = Indices.end(); I != E; ++I) { 1691a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MI->getOperand(*I).setReg(NewVReg); 1692a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1693a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (MI->getOperand(*I).isUse()) 1694a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MI->getOperand(*I).setIsKill(true); 1695a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 1696a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1697a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // Fill in the new live interval. 1698233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = getInstructionIndex(MI); 1699a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (HasUse) { 1700233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange LR(index.getLoadIndex(), index.getUseIndex(), 1701233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.getNextValue(SlotIndex(), 0, false, 17028651125d2885f74546b6e2a556082111d5b75da3Lang Hames getVNInfoAllocator())); 17038a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 1704a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson nI.addRange(LR); 1705a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.addRestorePoint(NewVReg, MI); 1706a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 1707a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (HasDef) { 1708233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange LR(index.getDefIndex(), index.getStoreIndex(), 1709233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.getNextValue(SlotIndex(), 0, false, 17108651125d2885f74546b6e2a556082111d5b75da3Lang Hames getVNInfoAllocator())); 17118a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 1712a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson nI.addRange(LR); 1713a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.addSpillPoint(NewVReg, true, MI); 1714a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 1715a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 17161719731d3d8ab6a986d67912f35daaad4f6910dbOwen Anderson added.push_back(&nI); 17178dc2cbe793ff577f69c17426d6dfaef94ad69191Owen Anderson 17188e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 17198a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\t\t\tadded new interval: "; 17208e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling nI.dump(); 17218a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << '\n'; 17228e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 1723a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 17249a032931453209505f6765a35be108ae5ea39b3bOwen Anderson 17259a032931453209505f6765a35be108ae5ea39b3bOwen Anderson 1726a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson RI = mri_->reg_begin(li.reg); 1727d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 1728d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1729d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson return added; 1730d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson} 1731d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1732d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Andersonstd::vector<LiveInterval*> LiveIntervals:: 173381a038218171860ee4c382849c647d3dc841fe8bEvan ChengaddIntervalsForSpills(const LiveInterval &li, 1734dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng SmallVectorImpl<LiveInterval*> &SpillIs, 1735c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { 1736ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson 1737ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson if (EnableFastSpilling) 1738c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng return addIntervalsForSpillsFast(li, loopInfo, vrm); 1739ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson 1740e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen assert(li.isSpillable() && "attempt to spill already spilled interval!"); 1741f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 17428e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 17438a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\t\t\tadding intervals for spills for interval: "; 17448a34229dcf484739119857988772572ef0cad9f2David Greene li.print(dbgs(), tri_); 17458a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << '\n'; 17468e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 1747f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 174872eeb94fe1d69cd05bdbbe86b2bc9fa25c963c22Evan Cheng // Each bit specify whether a spill is required in the MBB. 174981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector SpillMBBs(mf_->getNumBlockIDs()); 1750289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes; 17510cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector RestoreMBBs(mf_->getNumBlockIDs()); 1752289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes; 1753289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> MBBVRegsMap; 1754f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> NewLIs; 1755d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1756f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1757f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned NumValNums = li.getNumValNums(); 1758f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatDefs; 1759f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDefs.resize(NumValNums, NULL); 1760f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1761f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatOrigDefs.resize(NumValNums, NULL); 1762f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> ReMatIds; 1763f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1764f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng BitVector ReMatDelete(NumValNums); 1765f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1766f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 176781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Spilling a split live interval. It cannot be split any further. Also, 176881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // it's also guaranteed to be a single val# / range interval. 176981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (vrm.getPreSplitReg(li.reg)) { 177081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(li.reg, 0); 1771d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng // Unset the split kill marker on the last use. 1772233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex KillIdx = vrm.getKillPoint(li.reg); 1773233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (KillIdx != SlotIndex()) { 1774d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1775d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillMI && "Last use disappeared?"); 1776d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1777d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillOp != -1 && "Last use disappeared?"); 1778f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner KillMI->getOperand(KillOp).setIsKill(false); 1779d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng } 1780adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng vrm.removeKillPoint(li.reg); 178181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = vrm.isReMaterialized(li.reg); 178281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot = vrm.getStackSlot(li.reg); 178381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng assert(Slot != VirtRegMap::MAX_STACK_SLOT); 178481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = DefIsReMat ? 178581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.getReMaterializedMI(li.reg) : NULL; 178681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int LdSlot = 0; 178781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 178881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoad = isLoadSS || 178915511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad())); 179081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool IsFirstRange = true; 179181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 179281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 179381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a split live interval with multiple ranges, it means there 179481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // are two-address instructions that re-defined the value. Only the 179581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // first def can be rematerialized! 179681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (IsFirstRange) { 1797cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // Note ReMatOrigDefMI has already been deleted. 179881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 179981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1800d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 18010cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1802c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 180381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 180481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, 0, 180581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, 0, false, false, false, 1806d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 18070cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1808c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 180981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 181081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng IsFirstRange = false; 181181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1812419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 18134cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 1814352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen normalizeSpillWeights(NewLIs); 181581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return NewLIs; 181681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 181781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1818752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng bool TrySplit = !intervalIsInOneMBB(li); 18190cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (TrySplit) 18200cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numSplits; 1821f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool NeedStackSlot = false; 1822f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1823f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng i != e; ++i) { 1824f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const VNInfo *VNI = *i; 1825f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned VN = VNI->id; 1826857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->isUnused()) 1827f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; // Dead val#. 1828f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Is the def for the val# rematerializable? 1829857c4e01f85601cf2084adb860616256ee47c177Lang Hames MachineInstr *ReMatDefMI = VNI->isDefAccurate() 1830857c4e01f85601cf2084adb860616256ee47c177Lang Hames ? getInstructionFromIndex(VNI->def) : 0; 18315ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool dummy; 1832dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) { 1833f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Remember how to remat the def of this val#. 183481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReMatOrigDefs[VN] = ReMatDefMI; 18352c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman // Original def may be modified so we have to make a copy here. 18361ed9922794cda9dbe295e74674b909287e544632Evan Cheng MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI); 1837752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng CloneMIs.push_back(Clone); 18381ed9922794cda9dbe295e74674b909287e544632Evan Cheng ReMatDefs[VN] = Clone; 1839f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1840f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = true; 1841857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->hasPHIKill()) { 1842c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // A kill is a phi node, not all of its uses can be rematerialized. 1843f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // It must not be deleted. 1844c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng CanDelete = false; 1845c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // Need a stack slot if there is any live range where uses cannot be 1846c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // rematerialized. 1847c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng NeedStackSlot = true; 1848f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1849f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (CanDelete) 1850f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDelete.set(VN); 1851f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1852f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Need a stack slot if there is any live range where uses cannot be 1853f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // rematerialized. 1854f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng NeedStackSlot = true; 1855f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1856f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1857f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1858f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // One stack slot per live interval. 1859b98bbb7597495fb401b020679a94389298175506Owen Anderson if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) { 1860b98bbb7597495fb401b020679a94389298175506Owen Anderson if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT) 1861b98bbb7597495fb401b020679a94389298175506Owen Anderson Slot = vrm.assignVirt2StackSlot(li.reg); 1862b98bbb7597495fb401b020679a94389298175506Owen Anderson 1863b98bbb7597495fb401b020679a94389298175506Owen Anderson // This case only occurs when the prealloc splitter has already assigned 1864b98bbb7597495fb401b020679a94389298175506Owen Anderson // a stack slot to this vreg. 1865b98bbb7597495fb401b020679a94389298175506Owen Anderson else 1866b98bbb7597495fb401b020679a94389298175506Owen Anderson Slot = vrm.getStackSlot(li.reg); 1867b98bbb7597495fb401b020679a94389298175506Owen Anderson } 1868f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1869f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Create new intervals and rewrite defs and uses. 1870f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::Ranges::const_iterator 1871f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 187281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 187381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 187481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = ReMatDefMI != NULL; 1875f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = ReMatDelete[I->valno->id]; 1876f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int LdSlot = 0; 187781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1878f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad = isLoadSS || 187915511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad()); 188081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 18810cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1882d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, 18830cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1884c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 1885f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1886f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 18870cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Insert spills / restores if we are splitting. 1888419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng if (!TrySplit) { 18894cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 1890352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen normalizeSpillWeights(NewLIs); 18911953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return NewLIs; 1892419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 18931953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1894b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng SmallPtrSet<LiveInterval*, 4> AddedKill; 1895aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 18961953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NeedStackSlot) { 18971953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = SpillMBBs.find_first(); 18981953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 18991953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &spills = SpillIdxes[Id]; 19001953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = spills.size(); i != e; ++i) { 1901233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = spills[i].index; 19021953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = spills[i].vreg; 1903597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 19040cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 19050cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1906aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1907aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool FoundUse = false; 1908aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1909cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (spills[i].canFold) { 1910aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 19110cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 19120cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineOperand &MO = MI->getOperand(j); 1913d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || MO.getReg() != VReg) 19140cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 1915aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 1916aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1917aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (MO.isDef()) 1918cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng continue; 1919aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (isReMat || 1920aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng (!FoundUse && !alsoFoldARestore(Id, index, VReg, 1921aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng RestoreMBBs, RestoreIdxes))) { 1922aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // MI has two-address uses of the same register. If the use 1923aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // isn't the first and only use in the BB, then we can't fold 1924aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // it. FIXME: Move this to rewriteInstructionsForSpills. 1925aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 1926cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng break; 1927cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 1928aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoundUse = true; 19290cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 19300cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 19310cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the store into the def if possible. 1932cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1933aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 1934aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 1935cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng Folded = true; 193648fe63526e35ddaee7e98879596a569911f41319Sebastian Redl if (FoundUse) { 1937aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Also folded uses, do not issue a load. 1938aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 1939233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.removeRange(index.getLoadIndex(), index.getDefIndex()); 1940f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng } 1941233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.removeRange(index.getDefIndex(), index.getStoreIndex()); 1942cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 19430cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 19440cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 19457e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Otherwise tell the spiller to issue a spill. 1946b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!Folded) { 1947b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 1948233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool isKill = LR->end == index.getStoreIndex(); 1949b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng if (!MI->registerDefIsDead(nI.reg)) 1950b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng // No need to spill a dead def. 1951b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng vrm.addSpillPoint(VReg, isKill, MI); 1952b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (isKill) 1953b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng AddedKill.insert(&nI); 1954b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 19550cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 19561953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = SpillMBBs.find_next(Id); 19570cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 19581953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 19590cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 19601953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = RestoreMBBs.find_first(); 19611953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 19621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &restores = RestoreIdxes[Id]; 19631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = restores.size(); i != e; ++i) { 1964233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = restores[i].index; 1965233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (index == SlotIndex()) 19661953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng continue; 19671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = restores[i].vreg; 1968597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 19699c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 197081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1971aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1972aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1973cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (restores[i].canFold) { 1974aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 197581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 197681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineOperand &MO = MI->getOperand(j); 1977d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || MO.getReg() != VReg) 197881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 1979aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 19800cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MO.isDef()) { 1981aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // If this restore were to be folded, it would have been folded 1982aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // already. 1983aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 198481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng break; 198581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1986aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 198781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 198881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 19890cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 19900cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the load into the use if possible. 1991cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1992aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 19939c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!isReMat) 1994aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 1995aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 19960cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 19970cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng int LdSlot = 0; 19980cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 19990cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If the rematerializable def is a load, also try to fold it. 200015511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad()) 2001aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 2002aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops, isLoadSS, LdSlot, VReg); 2003650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng if (!Folded) { 2004650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 2005650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng if (ImpUse) { 2006650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng // Re-matting an instruction with virtual register use. Add the 2007e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // register as an implicit use on the use MI and mark the register 2008e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // interval as unspillable. 2009650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 2010e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen ImpLi.markNotSpillable(); 2011650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 2012650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng } 2013d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 2014aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 20150cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 20160cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If folding is not possible / failed, then tell the spiller to issue a 20170cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // load / rematerialization for us. 2018597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (Folded) 2019233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.removeRange(index.getLoadIndex(), index.getDefIndex()); 2020b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng else 20210cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.addRestorePoint(VReg, MI); 202281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 20231953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = RestoreMBBs.find_next(Id); 202481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 202581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 2026b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // Finalize intervals: add kills, finalize spill weights, and filter out 2027b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // dead intervals. 2028597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng std::vector<LiveInterval*> RetNewLIs; 2029597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 2030597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval *LI = NewLIs[i]; 2031597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (!LI->empty()) { 2032233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LI->weight /= SlotIndex::NUM * getApproximateInstructionCount(*LI); 2033b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!AddedKill.count(LI)) { 2034b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 2035233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex LastUseIdx = LR->end.getBaseIndex(); 2036d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 20376130f66eaae89f8878590796977678afa8448926Evan Cheng int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 2038b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng assert(UseIdx != -1); 2039a24752ff43dc1ad8c18c5d9e78549c45f62b980eEvan Cheng if (!LastUse->isRegTiedToDefOperand(UseIdx)) { 2040b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LastUse->getOperand(UseIdx).setIsKill(); 2041d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng vrm.addKillPoint(LI->reg, LastUseIdx); 2042adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng } 2043b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 2044597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng RetNewLIs.push_back(LI); 2045597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 2046597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 204781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 20484cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 2049352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen normalizeSpillWeights(RetNewLIs); 2050597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng return RetNewLIs; 2051f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 2052676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2053676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// hasAllocatableSuperReg - Return true if the specified physical register has 2054676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// any super register that's allocatable. 2055676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengbool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 2056676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 2057676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (allocatableRegs_[*AS] && hasInterval(*AS)) 2058676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return true; 2059676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return false; 2060676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2061676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2062676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getRepresentativeReg - Find the largest super register of the specified 2063676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// physical register. 2064676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 2065676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // Find the largest super-register that is allocatable. 2066676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned BestReg = Reg; 2067676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 2068676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SuperReg = *AS; 2069676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 2070676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng BestReg = SuperReg; 2071676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng break; 2072676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2073676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2074676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return BestReg; 2075676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2076676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2077676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getNumConflictsWithPhysReg - Return the number of uses and defs of the 2078676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// specified interval that conflicts with the specified physical register. 2079676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 2080676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg) const { 2081676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned NumConflicts = 0; 2082676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 2083676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2084676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 2085676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 2086676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 208728a1e486907104b85c5787345914917d74f0cf77Evan Cheng if (MI->isDebugValue()) 208828a1e486907104b85c5787345914917d74f0cf77Evan Cheng continue; 2089233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index = getInstructionIndex(MI); 2090676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) 2091676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng ++NumConflicts; 2092676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2093676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return NumConflicts; 2094676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2095676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2096676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// spillPhysRegAroundRegDefsUses - Spill the specified physical register 20972824a655509577127d221eecd1425de196f80320Evan Cheng/// around all defs and uses of the specified interval. Return true if it 20982824a655509577127d221eecd1425de196f80320Evan Cheng/// was able to cut its interval. 20992824a655509577127d221eecd1425de196f80320Evan Chengbool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 2100676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg, VirtRegMap &vrm) { 2101676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SpillReg = getRepresentativeReg(PhysReg); 2102676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2103676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 2104676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // If there are registers which alias PhysReg, but which are not a 2105676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // sub-register of the chosen representative super register. Assert 2106676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // since we can't handle it yet. 210770f2f65aacdbc96fe158b2860b5f0bad075ee548Dan Gohman assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) || 2108676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng tri_->isSuperRegister(*AS, SpillReg)); 2109676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 21102824a655509577127d221eecd1425de196f80320Evan Cheng bool Cut = false; 21110222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng SmallVector<unsigned, 4> PRegs; 21120222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng if (hasInterval(SpillReg)) 21130222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng PRegs.push_back(SpillReg); 21140222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng else { 21150222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng SmallSet<unsigned, 4> Added; 21160222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) 21170222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng if (Added.insert(*AS) && hasInterval(*AS)) { 21180222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng PRegs.push_back(*AS); 21190222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng for (const unsigned* ASS = tri_->getSubRegisters(*AS); *ASS; ++ASS) 21200222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng Added.insert(*ASS); 21210222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng } 21220222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng } 21230222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng 2124676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SmallPtrSet<MachineInstr*, 8> SeenMIs; 2125676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2126676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 2127676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 2128676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 212928a1e486907104b85c5787345914917d74f0cf77Evan Cheng if (MI->isDebugValue() || SeenMIs.count(MI)) 2130676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 2131676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SeenMIs.insert(MI); 2132233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index = getInstructionIndex(MI); 21330222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng for (unsigned i = 0, e = PRegs.size(); i != e; ++i) { 21340222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng unsigned PReg = PRegs[i]; 21350222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng LiveInterval &pli = getInterval(PReg); 21360222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng if (!pli.liveAt(Index)) 21370222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng continue; 21380222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng vrm.addEmergencySpill(PReg, MI); 2139233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex StartIdx = Index.getLoadIndex(); 2140233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex EndIdx = Index.getNextIndex().getBaseIndex(); 21412824a655509577127d221eecd1425de196f80320Evan Cheng if (pli.isInOneLiveRange(StartIdx, EndIdx)) { 21425a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng pli.removeRange(StartIdx, EndIdx); 21432824a655509577127d221eecd1425de196f80320Evan Cheng Cut = true; 21442824a655509577127d221eecd1425de196f80320Evan Cheng } else { 21457d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin std::string msg; 21467d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin raw_string_ostream Msg(msg); 21477d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin Msg << "Ran out of registers during register allocation!"; 2148518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isInlineAsm()) { 21497d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin Msg << "\nPlease check your inline asm statement for invalid " 21500222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng << "constraints:\n"; 21517d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin MI->print(Msg, tm_); 21525a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng } 215375361b69f3f327842b9dad69fa7f28ae3b688412Chris Lattner report_fatal_error(Msg.str()); 21545a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng } 21550222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng for (const unsigned* AS = tri_->getSubRegisters(PReg); *AS; ++AS) { 2156676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasInterval(*AS)) 2157676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 2158676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng LiveInterval &spli = getInterval(*AS); 2159676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (spli.liveAt(Index)) 2160233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames spli.removeRange(Index.getLoadIndex(), 2161233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames Index.getNextIndex().getBaseIndex()); 2162676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2163676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2164676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 21652824a655509577127d221eecd1425de196f80320Evan Cheng return Cut; 2166676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2167c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 2168c4dc132c8a787fc41b6a162121251234aa618965Owen AndersonLiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 2169ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames MachineInstr* startInst) { 2170c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveInterval& Interval = getOrCreateInterval(reg); 2171c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VNInfo* VN = Interval.getNextValue( 2172233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex(getInstructionIndex(startInst).getDefIndex()), 21738651125d2885f74546b6e2a556082111d5b75da3Lang Hames startInst, true, getVNInfoAllocator()); 2174857c4e01f85601cf2084adb860616256ee47c177Lang Hames VN->setHasPHIKill(true); 2175233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames VN->kills.push_back(indexes_->getTerminatorGap(startInst->getParent())); 21768651125d2885f74546b6e2a556082111d5b75da3Lang Hames LiveRange LR( 2177233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex(getInstructionIndex(startInst).getDefIndex()), 217874ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames getMBBEndIdx(startInst->getParent()), VN); 2179c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson Interval.addRange(LR); 2180c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 2181c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson return LR; 2182c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson} 2183b5257664795d49ada0d4669fe8ed1cd49c04fbf3David Greene 2184