LiveIntervalAnalysis.cpp revision 45e53975f81164d6e5e6322e83dd19030b7d3c88
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. 501b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesenstatic cl::opt<bool> DisableReMat("disable-rematerialization", 51844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(false), cl::Hidden); 52844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 53752195e3c662c6b5db042cf897c984624720f3b8Evan ChengSTATISTIC(numIntervals , "Number of original intervals"); 54752195e3c662c6b5db042cf897c984624720f3b8Evan ChengSTATISTIC(numFolds , "Number of loads/stores folded into instructions"); 55752195e3c662c6b5db042cf897c984624720f3b8Evan ChengSTATISTIC(numSplits , "Number of intervals split"); 56cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 571997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar LiveIntervals::ID = 0; 582ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", 592ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Live Interval Analysis", false, false) 602ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LiveVariables) 612ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 622ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(PHIElimination) 632ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(TwoAddressInstructionPass) 642ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(ProcessImplicitDefs) 652ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 662ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 672ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(LiveIntervals, "liveintervals", 68ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Live Interval Analysis", false, false) 69ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 70f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 71845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman AU.setPreservesCFG(); 726d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addRequired<AliasAnalysis>(); 736d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addPreserved<AliasAnalysis>(); 741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LiveVariables>(); 75148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng AU.addPreserved<LiveVariables>(); 76148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng AU.addRequired<MachineLoopInfo>(); 77148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng AU.addPreserved<MachineLoopInfo>(); 7867d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineDominatorsID); 791b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 8095dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson if (!StrongPHIElim) { 8195dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson AU.addPreservedID(PHIEliminationID); 8295dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson AU.addRequiredID(PHIEliminationID); 8395dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson } 841b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 86233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addPreserved<ProcessImplicitDefs>(); 87233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addRequired<ProcessImplicitDefs>(); 88233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addPreserved<SlotIndexes>(); 89233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addRequiredTransitive<SlotIndexes>(); 901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 91ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 92ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 93f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::releaseMemory() { 9403857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson // Free the live intervals themselves. 9520e2839cb975a2d4ee931e1ea4c4660a36ef0177Owen Anderson for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(), 96d6a6b3b7563a3f54ba48d465fc03ee10bbccb7a8Bob Wilson E = r2iMap_.end(); I != E; ++I) 9703857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson delete I->second; 981b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 100ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 101ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. 102ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer VNInfoAllocator.Reset(); 103752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng while (!CloneMIs.empty()) { 104752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng MachineInstr *MI = CloneMIs.back(); 105752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng CloneMIs.pop_back(); 1061ed9922794cda9dbe295e74674b909287e544632Evan Cheng mf_->DeleteMachineInstr(MI); 1071ed9922794cda9dbe295e74674b909287e544632Evan Cheng } 108993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 109993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 11080b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// runOnMachineFunction - Register allocate the whole function 11180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// 11280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Andersonbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 11380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mf_ = &fn; 11480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mri_ = &mf_->getRegInfo(); 11580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tm_ = &fn.getTarget(); 11680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tri_ = tm_->getRegisterInfo(); 11780b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tii_ = tm_->getInstrInfo(); 1186d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman aa_ = &getAnalysis<AliasAnalysis>(); 11980b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson lv_ = &getAnalysis<LiveVariables>(); 120233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames indexes_ = &getAnalysis<SlotIndexes>(); 12180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson allocatableRegs_ = tri_->getAllocatableSet(fn); 122ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 124ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 126843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 12770ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 1281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 129ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 130ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 13170ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 13245cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattnervoid LiveIntervals::print(raw_ostream &OS, const Module* ) const { 133705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "********** INTERVALS **********\n"; 1348e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 135705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner I->second->print(OS, tri_); 136705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "\n"; 1378e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 13870ca358b7d540b6061236ddf757085042873c12cChris Lattner 139752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printInstrs(OS); 140752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng} 141752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 142752195e3c662c6b5db042cf897c984624720f3b8Evan Chengvoid LiveIntervals::printInstrs(raw_ostream &OS) const { 143705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "********** MACHINEINSTRS **********\n"; 144f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen mf_->print(OS, indexes_); 14570ca358b7d540b6061236ddf757085042873c12cChris Lattner} 14670ca358b7d540b6061236ddf757085042873c12cChris Lattner 147752195e3c662c6b5db042cf897c984624720f3b8Evan Chengvoid LiveIntervals::dumpInstrs() const { 1488a34229dcf484739119857988772572ef0cad9f2David Greene printInstrs(dbgs()); 149752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng} 150752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 151cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesenbool LiveIntervals::conflictsWithPhysReg(const LiveInterval &li, 152cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen VirtRegMap &vrm, unsigned reg) { 153cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // We don't handle fancy stuff crossing basic block boundaries 154cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (li.ranges.size() != 1) 155cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen return true; 156cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen const LiveRange &range = li.ranges.front(); 157cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen SlotIndex idx = range.start.getBaseIndex(); 158cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen SlotIndex end = range.end.getPrevSlot().getBaseIndex().getNextIndex(); 159cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 160cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // Skip deleted instructions 161cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen MachineInstr *firstMI = getInstructionFromIndex(idx); 162cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen while (!firstMI && idx != end) { 163cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen idx = idx.getNextIndex(); 164cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen firstMI = getInstructionFromIndex(idx); 165cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen } 166cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (!firstMI) 167cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen return false; 168cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 169cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // Find last instruction in range 170cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen SlotIndex lastIdx = end.getPrevIndex(); 171cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen MachineInstr *lastMI = getInstructionFromIndex(lastIdx); 172cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen while (!lastMI && lastIdx != idx) { 173cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen lastIdx = lastIdx.getPrevIndex(); 174cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen lastMI = getInstructionFromIndex(lastIdx); 175cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen } 176cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (!lastMI) 177cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen return false; 178cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 179cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // Range cannot cross basic block boundaries or terminators 180cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen MachineBasicBlock *MBB = firstMI->getParent(); 181cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (MBB != lastMI->getParent() || lastMI->getDesc().isTerminator()) 182cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen return true; 183cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 184cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen MachineBasicBlock::const_iterator E = lastMI; 185cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen ++E; 186cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen for (MachineBasicBlock::const_iterator I = firstMI; I != E; ++I) { 187cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen const MachineInstr &MI = *I; 188cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 189cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // Allow copies to and from li.reg 1908ea324093cd512acc37f7b5a60e511e64103699eJakob Stoklund Olesen if (MI.isCopy()) 1918ea324093cd512acc37f7b5a60e511e64103699eJakob Stoklund Olesen if (MI.getOperand(0).getReg() == li.reg || 1928ea324093cd512acc37f7b5a60e511e64103699eJakob Stoklund Olesen MI.getOperand(1).getReg() == li.reg) 1938ea324093cd512acc37f7b5a60e511e64103699eJakob Stoklund Olesen continue; 194cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 195cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // Check for operands using reg 196cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 197cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen const MachineOperand& mop = MI.getOperand(i); 198cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (!mop.isReg()) 199cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen continue; 200cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen unsigned PhysReg = mop.getReg(); 201cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (PhysReg == 0 || PhysReg == li.reg) 202cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen continue; 203cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { 204cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (!vrm.hasPhys(PhysReg)) 205c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 206cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen PhysReg = vrm.getPhys(PhysReg); 207c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 208cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (PhysReg && tri_->regsOverlap(PhysReg, reg)) 209cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen return true; 210c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 211c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 212c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 213cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // No conflicts found. 214c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return false; 215c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng} 216c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 217a24986d8bfd941252f7d080943e02bbe6a0c2944Jakob Stoklund Olesenbool LiveIntervals::conflictsWithAliasRef(LiveInterval &li, unsigned Reg, 2188f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng SmallPtrSet<MachineInstr*,32> &JoinedCopies) { 2198f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng for (LiveInterval::Ranges::const_iterator 2208f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 221233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames for (SlotIndex index = I->start.getBaseIndex(), 222233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); 223233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames index != end; 224233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames index = index.getNextIndex()) { 225f4811a96941433fc3828869d76dfeba5ec5decd3Jakob Stoklund Olesen MachineInstr *MI = getInstructionFromIndex(index); 226f4811a96941433fc3828869d76dfeba5ec5decd3Jakob Stoklund Olesen if (!MI) 227f4811a96941433fc3828869d76dfeba5ec5decd3Jakob Stoklund Olesen continue; // skip deleted instructions 2288f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 2298f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (JoinedCopies.count(MI)) 2308f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 2318f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 2328f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng MachineOperand& MO = MI->getOperand(i); 2338f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (!MO.isReg()) 2348f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 2358f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng unsigned PhysReg = MO.getReg(); 236a24986d8bfd941252f7d080943e02bbe6a0c2944Jakob Stoklund Olesen if (PhysReg == 0 || PhysReg == Reg || 237a24986d8bfd941252f7d080943e02bbe6a0c2944Jakob Stoklund Olesen TargetRegisterInfo::isVirtualRegister(PhysReg)) 2388f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 239a24986d8bfd941252f7d080943e02bbe6a0c2944Jakob Stoklund Olesen if (tri_->regsOverlap(Reg, PhysReg)) 2408f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng return true; 2418f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 2428f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 2438f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 2448f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 2458f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng return false; 2468f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng} 2478f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 248afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Chengstatic 2493749943648772743c9c0e852553e50e6700a0c1bEvan Chengbool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) { 250afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng unsigned Reg = MI.getOperand(MOIdx).getReg(); 251afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) { 252afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng const MachineOperand &MO = MI.getOperand(i); 253afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng if (!MO.isReg()) 254afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng continue; 255afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng if (MO.getReg() == Reg && MO.isDef()) { 256afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() && 257afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng MI.getOperand(MOIdx).getSubReg() && 258ed2185e171a86b8c0e166803fd4066383a6cff08Jakob Stoklund Olesen (MO.getSubReg() || MO.isImplicit())); 259afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return true; 260afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng } 261afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng } 262afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return false; 263afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng} 264afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng 2653749943648772743c9c0e852553e50e6700a0c1bEvan Cheng/// isPartialRedef - Return true if the specified def at the specific index is 2663749943648772743c9c0e852553e50e6700a0c1bEvan Cheng/// partially re-defining the specified live interval. A common case of this is 2671b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen/// a definition of the sub-register. 2683749943648772743c9c0e852553e50e6700a0c1bEvan Chengbool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO, 2693749943648772743c9c0e852553e50e6700a0c1bEvan Cheng LiveInterval &interval) { 2703749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (!MO.getSubReg() || MO.isEarlyClobber()) 2713749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return false; 2723749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 2733749943648772743c9c0e852553e50e6700a0c1bEvan Cheng SlotIndex RedefIndex = MIIdx.getDefIndex(); 2743749943648772743c9c0e852553e50e6700a0c1bEvan Cheng const LiveRange *OldLR = 2753749943648772743c9c0e852553e50e6700a0c1bEvan Cheng interval.getLiveRangeContaining(RedefIndex.getUseIndex()); 2766e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def); 2776e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames if (DefMI != 0) { 2783749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return DefMI->findRegisterDefOperandIdx(interval.reg) != -1; 2793749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } 2803749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return false; 2813749943648772743c9c0e852553e50e6700a0c1bEvan Cheng} 2823749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 283be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 284ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 285233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 2868651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineOperand& MO, 287ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx, 288be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 2894314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_)); 290419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 291706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 292706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 293706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 2941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 295d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 2961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 2971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 298233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex defIndex = MIIdx.getDefIndex(); 29939faac2531268b8555475796c6071556670dc290Dale Johannesen // Earlyclobbers move back one, so that they overlap the live range 30039faac2531268b8555475796c6071556670dc290Dale Johannesen // of inputs. 30186b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen if (MO.isEarlyClobber()) 302233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames defIndex = MIIdx.getUseIndex(); 30363e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen 30463e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen // Make sure the first definition is not a partial redefinition. Add an 30563e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen // <imp-def> of the full register. 30663e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen if (MO.getSubReg()) 30763e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen mi->addRegisterDefined(interval.reg); 30863e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen 309c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 31004c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (mi->isCopyLike()) { 311c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 3120465bcffbbffb5ff5f420787b4350cb8abb196f7Jakob Stoklund Olesen } 3130465bcffbbffb5ff5f420787b4350cb8abb196f7Jakob Stoklund Olesen 3146e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames VNInfo *ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 3157ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(ValNo->id == 0 && "First value in interval is not 0?"); 3161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 3181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 3191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 3201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 3211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 3221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 323233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex killIdx; 3241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 325233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex(); 3261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 327233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames killIdx = defIndex.getStoreIndex(); 3281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 3301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 3311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 332493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin assert(vi.AliveBlocks.empty() && 3331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 3347ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIdx, ValNo); 3351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3368a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << "\n"); 3371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 3381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3406097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 3411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 3421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 3431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 3441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 34574ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo); 3468a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << NewLR); 3471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 3481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 349dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen bool PHIJoin = lv_->isPHIJoin(interval.reg); 350dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 351dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen if (PHIJoin) { 352dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // A phi join register is killed at the end of the MBB and revived as a new 353dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // valno in the killing blocks. 354dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks"); 355dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " phi-join"); 356dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->setHasPHIKill(true); 357dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } else { 358dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // Iterate over all of the blocks that the variable is completely 359dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 360dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // live interval. 361dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 362dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen E = vi.AliveBlocks.end(); I != E; ++I) { 363dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I); 364dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo); 365dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen interval.addRange(LR); 366dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " +" << LR); 367dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } 3681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 3711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 3721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 3731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 374dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen SlotIndex Start = getMBBStartIdx(Kill->getParent()); 375dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen SlotIndex killIdx = getInstructionIndex(Kill).getDefIndex(); 376dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 377dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // Create interval with one of a NEW value number. Note that this value 378dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // number isn't actually defined by an instruction, weird huh? :) 379dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen if (PHIJoin) { 3806e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames assert(getInstructionFromIndex(Start) == 0 && 3816e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames "PHI def index points at actual instruction."); 3826e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames ValNo = interval.getNextValue(Start, 0, VNInfoAllocator); 383dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->setIsPHIDef(true); 384dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } 385dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LiveRange LR(Start, killIdx, ValNo); 3861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3878a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 3881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 3913749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (MultipleDefsBySameMI(*mi, MOIdx)) 392761fd4c1d97977c16de9f0cf921056a37b906304Nick Lewycky // Multiple defs of the same virtual register by the same instruction. 393761fd4c1d97977c16de9f0cf921056a37b906304Nick Lewycky // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ... 394afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng // This is likely due to elimination of REG_SEQUENCE instructions. Return 395afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng // here since there is nothing to do. 396afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return; 397afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng 3981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 3991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 400bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 401bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 4023749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 4033749943648772743c9c0e852553e50e6700a0c1bEvan Cheng // It may also be partial redef like this: 4041b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // 80 %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0 4051b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0 4063749943648772743c9c0e852553e50e6700a0c1bEvan Cheng bool PartReDef = isPartialRedef(MIIdx, MO, interval); 4073749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) { 4081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 4091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 4101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 4111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 4121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 413233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex RedefIndex = MIIdx.getDefIndex(); 414fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 415233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames RedefIndex = MIIdx.getUseIndex(); 4161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 41735f291d2c5f80e8e713704190230064311bbbbbeLang Hames const LiveRange *OldLR = 418233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames interval.getLiveRangeContaining(RedefIndex.getUseIndex()); 4197ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *OldValNo = OldLR->valno; 420c66d0f2a9386cc7cb3237b8e3cace2b62a9c7dc8Jakob Stoklund Olesen SlotIndex DefIndex = OldValNo->def.getDefIndex(); 4214f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 422c66d0f2a9386cc7cb3237b8e3cace2b62a9c7dc8Jakob Stoklund Olesen // Delete the previous value, which should be short and continuous, 423be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 4241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 425706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 42691725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 42791725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 4286e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator); 429857c4e01f85601cf2084adb860616256ee47c177Lang Hames 43091725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 431c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->def = RedefIndex; 432ad6c5a20ba87e7aba91ef7e8b270715a25379770Evan Cheng OldValNo->setCopy(0); 433ad6c5a20ba87e7aba91ef7e8b270715a25379770Evan Cheng 434ad6c5a20ba87e7aba91ef7e8b270715a25379770Evan Cheng // A re-def may be a copy. e.g. %reg1030:6<def> = VMOVD %reg1026, ... 43504c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (PartReDef && mi->isCopyLike()) 436ad6c5a20ba87e7aba91ef7e8b270715a25379770Evan Cheng OldValNo->setCopy(&*mi); 4371b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 438be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 439be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 4408a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " replace range with " << LR); 4411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 4441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 4456b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) 446233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(), 447233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames OldValNo)); 4481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4498e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 4508a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << " RESULT: "; 4518a34229dcf484739119857988772572ef0cad9f2David Greene interval.print(dbgs(), tri_); 4528e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 4533749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } else if (lv_->isPHIJoin(interval.reg)) { 4541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 4551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 4561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 457dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 458233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex defIndex = MIIdx.getDefIndex(); 459fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 460233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames defIndex = MIIdx.getUseIndex(); 461752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 4627ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 463c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 46404c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (mi->isCopyLike()) 465c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 4666e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 4671b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 46874ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames SlotIndex killIndex = getMBBEndIdx(mbb); 4697ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 4701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 471857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasPHIKill(true); 472dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " phi-join +" << LR); 4733749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } else { 4743749943648772743c9c0e852553e50e6700a0c1bEvan Cheng llvm_unreachable("Multiply defined register"); 475dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 4761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 477ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 4788a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << '\n'); 479ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 480ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 481f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 482ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 483233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 4846b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson MachineOperand& MO, 48591725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveInterval &interval, 486c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI) { 4871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 4881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 4894314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_)); 4901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 491233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 492233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = baseIndex.getDefIndex(); 49386b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen // Earlyclobbers move back one. 49486b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen if (MO.isEarlyClobber()) 495233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames start = MIIdx.getUseIndex(); 496233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = start; 4971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 4991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 5001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 50139faac2531268b8555475796c6071556670dc290Dale Johannesen // For earlyclobbers, the defSlot was pushed back one; the extra 50239faac2531268b8555475796c6071556670dc290Dale Johannesen // advance below compensates. 5036b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) { 5048a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 505233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = start.getStoreIndex(); 506ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 5071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 508ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 5091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 5101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 5111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 512233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 5135ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 514233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 515bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen if (mi->isDebugValue()) 516bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen continue; 517233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 518233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 519233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 5206130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 5218a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " killed"); 522233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = baseIndex.getDefIndex(); 523ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 524c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 5251015ba7018c87f48cc7bb45a564eb4a27241e76aEvan Cheng int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_); 526c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (DefIdx != -1) { 527c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (mi->isRegTiedToUseOperand(DefIdx)) { 528c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Two-address instruction. 529233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = baseIndex.getDefIndex(); 530c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 531c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Another instruction redefines the register before it is ever read. 532bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // Then the register is essentially dead at the instruction that 533bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // defines it. Hence its interval is: 534c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // [defSlot(def), defSlot(def)+1) 5358a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 536233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = start.getStoreIndex(); 537c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 538c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng goto exit; 539c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 540f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5411b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 542233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 5431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5441b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 5455ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 5465ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 547d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // and never used. Another possible case is the implicit use of the 548d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // physical register has been deleted by two-address pass. 549233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = start.getStoreIndex(); 55002ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 551ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 5521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 553f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 55424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 55531cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen VNInfo *ValNo = interval.getVNInfoAt(start); 55631cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen bool Extend = ValNo != 0; 55731cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen if (!Extend) 55831cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen ValNo = interval.getNextValue(start, CopyMI, VNInfoAllocator); 55931cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen if (Extend && MO.isEarlyClobber()) 560857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasRedefByEC(true); 5617ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 5621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 5638a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << '\n'); 564ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 565ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 566f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 567f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 568233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 569ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng MachineOperand& MO, 570ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx) { 5716b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 572ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 5736b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg())); 5746b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson else if (allocatableRegs_[MO.getReg()]) { 575c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 57604c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (MI->isCopyLike()) 577c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = MI; 578c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 5796b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg()), CopyMI); 58024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Def of a register also defines its sub-registers. 5816b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS) 5826130f66eaae89f8878590796977678afa8448926Evan Cheng // If MI also modifies the sub-register explicitly, avoid processing it 5836130f66eaae89f8878590796977678afa8448926Evan Cheng // more than once. Do not pass in TRI here so it checks for exact match. 5841015ba7018c87f48cc7bb45a564eb4a27241e76aEvan Cheng if (!MI->definesRegister(*AS)) 585c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 5866b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(*AS), 0); 587f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5884d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 5894d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 590b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 591233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 59224a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 5934314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tlivein register: " << PrintReg(interval.reg, tri_)); 594b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 595b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 596b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 597b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 5984507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng MachineBasicBlock::iterator E = MBB->end(); 5994507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // Skip over DBG_VALUE at the start of the MBB. 6004507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi != E && mi->isDebugValue()) { 6014507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng while (++mi != E && mi->isDebugValue()) 6024507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng ; 6034507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi == E) 6044507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // MBB is empty except for DBG_VALUE's. 6054507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng return; 6064507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng } 6074507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng 608233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 609233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = baseIndex; 610233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 611233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 612233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 613233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = baseIndex; 6140076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng bool SeenDefUse = false; 615b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 616bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen while (mi != E) { 6171d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen if (mi->killsRegister(interval.reg, tri_)) { 6181d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen DEBUG(dbgs() << " killed"); 6191d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen end = baseIndex.getDefIndex(); 6201d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen SeenDefUse = true; 6211d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen break; 6221015ba7018c87f48cc7bb45a564eb4a27241e76aEvan Cheng } else if (mi->definesRegister(interval.reg, tri_)) { 6231d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // Another instruction redefines the register before it is ever read. 6241d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // Then the register is essentially dead at the instruction that defines 6251d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // it. Hence its interval is: 6261d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // [defSlot(def), defSlot(def)+1) 6271d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen DEBUG(dbgs() << " dead"); 6281d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen end = start.getStoreIndex(); 6291d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen SeenDefUse = true; 6301d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen break; 631bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen } 6321d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen 6334507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng while (++mi != E && mi->isDebugValue()) 6344507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // Skip over DBG_VALUE. 6354507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng ; 6364507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi != E) 637233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 638b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 639b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 64075611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 6410076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng if (!SeenDefUse) { 642292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng if (isAlias) { 6438a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 644233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = MIIdx.getStoreIndex(); 645292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } else { 6468a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " live through"); 647292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng end = baseIndex; 648292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } 64924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 65024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 6516e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames SlotIndex defIdx = getMBBStartIdx(MBB); 6526e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames assert(getInstructionFromIndex(defIdx) == 0 && 6536e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames "PHI def index points at actual instruction."); 65410382fb71d8306f320ecbeb7049d25354c0e5457Lang Hames VNInfo *vni = 6556e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames interval.getNextValue(defIdx, 0, VNInfoAllocator); 656d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames vni->setIsPHIDef(true); 657d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames LiveRange LR(start, end, vni); 6583de23e6f6cf337451a0934159da494d645b93133Jakob Stoklund Olesen 6599b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 6608a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << '\n'); 661b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 662b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 663ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 6644d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 66508cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 666ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 6671b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesenvoid LiveIntervals::computeIntervals() { 6688a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n" 6698e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << "********** Function: " 6708e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'); 671d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 672d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng SmallVector<unsigned, 8> UndefUses; 673428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 674428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 675428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 67600a99a35840451a291eb61a192a750908a4073aeEvan Cheng if (MBB->empty()) 67700a99a35840451a291eb61a192a750908a4073aeEvan Cheng continue; 67800a99a35840451a291eb61a192a750908a4073aeEvan Cheng 679134eb73fc35e6ead3cfd3ed5024d0d7efa507441Owen Anderson // Track the index of the current machine instr. 680233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIndex = getMBBStartIdx(MBB); 681ad98f795d0dba3db721139a8a74a98acdce0ff60Bob Wilson DEBUG(dbgs() << "BB#" << MBB->getNumber() 682ad98f795d0dba3db721139a8a74a98acdce0ff60Bob Wilson << ":\t\t# derived from " << MBB->getName() << "\n"); 6831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 684cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 68581bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), 686cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 687cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 688cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Multiple live-ins can alias the same register. 6896f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 690cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!hasInterval(*AS)) 691cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 692cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman true); 693dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 6941b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 69599500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson // Skip over empty initial indices. 696233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(MIIndex) == 0) 697233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 6981b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 6991caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 7001caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen MI != miEnd; ++MI) { 7018a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << MIIndex << "\t" << *MI); 702518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isDebugValue()) 7031caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen continue; 7041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 705438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 706428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 707428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 708d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (!MO.isReg() || !MO.getReg()) 709d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng continue; 710d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 7111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 712d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (MO.isDef()) 713ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleRegisterDef(MBB, MI, MIIndex, MO, i); 714d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng else if (MO.isUndef()) 715d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng UndefUses.push_back(MO.getReg()); 7161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 7171b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 718233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Move to the next instr slot. 719233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 720ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 7211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 722d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 723d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // Create empty intervals for registers defined by implicit_def's (except 724d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // for those implicit_def that define values which are liveout of their 725d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // blocks. 726d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { 727d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng unsigned UndefReg = UndefUses[i]; 728d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng (void)getOrCreateInterval(UndefReg); 729d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng } 730ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 731b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 73203857b29d8271a23943254579e6cf7b7df4b1bd3Owen AndersonLiveInterval* LiveIntervals::createInterval(unsigned reg) { 7330a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 73403857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson return new LiveInterval(reg, Weight); 7359a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 736f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 7370a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// dupInterval - Duplicate a live interval. The caller is responsible for 7380a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// managing the allocated memory. 7390a1fcce09230e9b4bd30a8f07447aa075dce7470Evan ChengLiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 7400a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng LiveInterval *NewLI = createInterval(li->reg); 74190f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng NewLI->Copy(*li, mri_, getVNInfoAllocator()); 7420a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng return NewLI; 7430a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng} 7440a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng 745f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 746f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 747f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 748f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 749cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund OlesenMachineBasicBlock::iterator 750cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund OlesenLiveIntervals::getLastSplitPoint(const LiveInterval &li, 751cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen MachineBasicBlock *mbb) { 752cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen const MachineBasicBlock *lpad = mbb->getLandingPadSuccessor(); 753cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen 754cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen // If li is not live into a landing pad, we can insert spill code before the 755cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen // first terminator. 756cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen if (!lpad || !isLiveInToMBB(li, lpad)) 757cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen return mbb->getFirstTerminator(); 758cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen 759cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen // When there is a landing pad, spill code must go before the call instruction 760cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen // that can throw. 761cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen MachineBasicBlock::iterator I = mbb->end(), B = mbb->begin(); 762cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen while (I != B) { 763cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen --I; 764cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen if (I->getDesc().isCall()) 765cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen return I; 766cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen } 76745e53975f81164d6e5e6322e83dd19030b7d3c88Jakob Stoklund Olesen // The block contains no calls that can throw, so use the first terminator. 768cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen return mbb->getFirstTerminator(); 769cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen} 770cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen 771d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 772d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 773d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 774d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 775d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 776d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 777d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 778d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 779d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || !MO.isUse()) 780d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 781d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 782d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 783d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 7841b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 7851873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner if (TargetRegisterInfo::isPhysicalRegister(Reg) && 7861873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner !allocatableRegs_[Reg]) 7871873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner continue; 788d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // FIXME: For now, only remat MI with at most one register operand. 789d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng assert(!RegOp && 790d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng "Can't rematerialize instruction with multiple register operand!"); 791d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 7926d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#ifndef NDEBUG 793d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng break; 7946d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#endif 795d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 796d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 797d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 798d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 799d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 800d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 801d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 802233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx) const { 80331cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen VNInfo *UValNo = li.getVNInfoAt(UseIdx); 80431cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI)); 805d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 806d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 807f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 808f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 809f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trickbool 810f4baeaf8485f01beda46d29fd55753199dc68070Andrew TrickLiveIntervals::isReMaterializable(const LiveInterval &li, 811f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick const VNInfo *ValNo, MachineInstr *MI, 812f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick const SmallVectorImpl<LiveInterval*> &SpillIs, 813f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick bool &isLoad) { 814f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 815f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 816f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 817a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman if (!tii_->isTriviallyReMaterializable(MI, aa_)) 818a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman return false; 819f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 820a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // Target-specific code can mark an instruction as being rematerializable 821a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // if it has one virtual reg use, though it had better be something like 822a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // a PIC base register which is likely to be live everywhere. 8236d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = getReMatImplicitUse(li, MI); 8246d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse) { 8256d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const LiveInterval &ImpLi = getInterval(ImpUse); 82628a1e486907104b85c5787345914917d74f0cf77Evan Cheng for (MachineRegisterInfo::use_nodbg_iterator 82728a1e486907104b85c5787345914917d74f0cf77Evan Cheng ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end(); 82828a1e486907104b85c5787345914917d74f0cf77Evan Cheng ri != re; ++ri) { 8296d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineInstr *UseMI = &*ri; 830233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx = getInstructionIndex(UseMI); 83131cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen if (li.getVNInfoAt(UseIdx) != ValNo) 8326d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman continue; 8336d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 8346d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8356d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 836dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng 837dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // If a register operand of the re-materialized instruction is going to 838dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // be spilled next, then it's not legal to re-materialize this instruction. 839dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng for (unsigned i = 0, e = SpillIs.size(); i != e; ++i) 840dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng if (ImpUse == SpillIs[i]->reg) 841dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng return false; 8426d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 8436d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return true; 8445ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 8455ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 84606587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 84706587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng/// val# of the specified interval is re-materializable. 84806587497dc1c39516f24784a2ac1d9323faae0a5Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 84906587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng const VNInfo *ValNo, MachineInstr *MI) { 85006587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng SmallVector<LiveInterval*, 4> Dummy1; 85106587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng bool Dummy2; 85206587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng return isReMaterializable(li, ValNo, MI, Dummy1, Dummy2); 85306587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng} 85406587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng 8555ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 8565ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 857f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trickbool 858f4baeaf8485f01beda46d29fd55753199dc68070Andrew TrickLiveIntervals::isReMaterializable(const LiveInterval &li, 859f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick const SmallVectorImpl<LiveInterval*> &SpillIs, 860f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick bool &isLoad) { 8615ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 8625ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 8635ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 8645ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 865857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->isUnused()) 8665ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 8675ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 868857c4e01f85601cf2084adb860616256ee47c177Lang Hames MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 8696e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames if (!ReMatDefMI) 8706e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames return false; 8715ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 872d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 873dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 874f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 8755ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 876f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 877f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 878f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 879f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 88079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// FilterFoldedOps - Filter out two-address use operands. Return 88179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// true if it finds any issue with the operands that ought to prevent 88279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// folding. 88379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengstatic bool FilterFoldedOps(MachineInstr *MI, 88479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 88579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned &MRInfo, 88679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &FoldOps) { 88779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MRInfo = 0; 888aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 889aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned OpIdx = Ops[i]; 890d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(OpIdx); 891aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // FIXME: fold subreg use. 892d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.getSubReg()) 89379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 894d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.isDef()) 895aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isMod; 896aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 897aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Filter out two-address use operand(s). 898a24752ff43dc1ad8c18c5d9e78549c45f62b980eEvan Cheng if (MI->isRegTiedToDefOperand(OpIdx)) { 899aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo = VirtRegMap::isModRef; 900aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng continue; 901aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 902aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isRef; 903aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 904aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoldOps.push_back(OpIdx); 905e62f97c094dba44e4c259d20135167fa91912eeaEvan Cheng } 90679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 90779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng} 9081b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 90979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 91079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 91179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// slot / to reg or any rematerialized load into ith operand of specified 91279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// MI. If it is successul, MI is updated with the newly created MI and 91379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// returns true. 91479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengbool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 91579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng VirtRegMap &vrm, MachineInstr *DefMI, 916233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex InstrIdx, 91779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 91879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng bool isSS, int Slot, unsigned Reg) { 91979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // If it is an implicit def instruction, just delete it. 920518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isImplicitDef()) { 92179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng RemoveMachineInstrFromMaps(MI); 92279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 92379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MI->eraseFromParent(); 92479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng ++numFolds; 92579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 92679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng } 92779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 92879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 92979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 93079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 93179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> FoldOps; 93279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 93379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 934cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 935427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // The only time it's safe to fold into a two address instruction is when 936427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // it's folding reload and spill from / into a spill stack slot. 937427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng if (DefMI && (MRInfo & VirtRegMap::isMod)) 938249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng return false; 939249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng 940e05442d50806e2850eae1571958816028093df85Jakob Stoklund Olesen MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(MI, FoldOps, Slot) 941e05442d50806e2850eae1571958816028093df85Jakob Stoklund Olesen : tii_->foldMemoryOperand(MI, FoldOps, DefMI); 942f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (fmi) { 943d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng // Remember this instruction uses the spill slot. 944d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng if (isSS) vrm.addSpillSlotUse(Slot, fmi); 945d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng 946f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Attempt to fold the memory reference into the instruction. If 947f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // we can do this, we don't need to insert spill code. 9488480293f41c11c22762164449e41cd3adb0dd7d8Evan Cheng if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 949aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 95081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.transferSpillPts(MI, fmi); 9510cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.transferRestorePts(MI, fmi); 952c1f53c742620dd4f2460685477303002bba8a8d8Evan Cheng vrm.transferEmergencySpills(MI, fmi); 953233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames ReplaceMachineInstrInMaps(MI, fmi); 954e05442d50806e2850eae1571958816028093df85Jakob Stoklund Olesen MI->eraseFromParent(); 955e05442d50806e2850eae1571958816028093df85Jakob Stoklund Olesen MI = fmi; 9560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numFolds; 957f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 958f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 959f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 960f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 961f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 962018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// canFoldMemoryOperand - Returns true if the specified load / store 963018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// folding is possible. 964018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 96579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 9663c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng bool ReMat) const { 96779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 96879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 96979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 970018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng SmallVector<unsigned, 2> FoldOps; 97179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 97279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 973018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 9743c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng // It's only legal to remat for a use, not a def. 9753c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng if (ReMat && (MRInfo & VirtRegMap::isMod)) 97679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 977018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 978d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return tii_->canFoldMemoryOperand(MI, FoldOps); 979d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 980d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 98181a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 982233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveInterval::Ranges::const_iterator itr = li.ranges.begin(); 983233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 984233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end); 985233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 986233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (mbb == 0) 987233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return false; 988233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 989233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames for (++itr; itr != li.ranges.end(); ++itr) { 990233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineBasicBlock *mbb2 = 991233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames indexes_->getMBBCoveringRange(itr->start, itr->end); 992233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 993233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (mbb2 != mbb) 99481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 99581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 996233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 99781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return true; 99881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 99981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1000d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 1001d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// interval on to-be re-materialized operands of MI) with new register. 1002d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengvoid LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 1003d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI, unsigned NewVReg, 1004d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm) { 1005d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // There is an implicit use. That means one of the other operand is 1006d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // being remat'ed and the remat'ed instruction has li.reg as an 1007d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // use operand. Make sure we rewrite that as well. 1008d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1009d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 1010d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg()) 1011d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1012d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 1013c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1014d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1015d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!vrm.isReMaterialized(Reg)) 1016d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1017d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 10186130f66eaae89f8878590796977678afa8448926Evan Cheng MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 10196130f66eaae89f8878590796977678afa8448926Evan Cheng if (UseMO) 10206130f66eaae89f8878590796977678afa8448926Evan Cheng UseMO->setReg(NewVReg); 1021d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1022d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1023d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 1024f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 1025f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 1026018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals:: 1027d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan ChengrewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 10281b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen bool TrySplit, SlotIndex index, SlotIndex end, 10298651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineInstr *MI, 103081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1031f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1032f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1033d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1034f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1035f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 103622f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 1037313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 1038289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> &MBBVRegsMap, 1039c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1040018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool CanFold = false; 1041f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RestartInstruction: 1042f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1043f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineOperand& mop = MI->getOperand(i); 1044d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!mop.isReg()) 1045f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1046f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Reg = mop.getReg(); 1047c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1048f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1049f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (Reg != li.reg) 1050f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1051f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1052f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool TryFold = !DefIsReMat; 1053cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng bool FoldSS = true; // Default behavior unless it's a remat. 1054f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int FoldSlot = Slot; 1055f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIsReMat) { 1056f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If this is the rematerializable definition MI itself and 1057f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // all of its uses are rematerialized, simply delete it. 105881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MI == ReMatOrigDefMI && CanDelete) { 1059bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen DEBUG(dbgs() << "\t\t\t\tErasing re-materializable def: " 106028a1e486907104b85c5787345914917d74f0cf77Evan Cheng << *MI << '\n'); 1061f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RemoveMachineInstrFromMaps(MI); 1062cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng vrm.RemoveMachineInstrFromMaps(MI); 1063f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI->eraseFromParent(); 1064f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng break; 1065f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1066f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1067f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If def for this use can't be rematerialized, then try folding. 10680cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If def is rematerializable and it's a load, also try folding. 1069cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 1070f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (isLoad) { 1071f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Try fold loads (from stack slot, constant pool, etc.) into uses. 1072f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSS = isLoadSS; 1073f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSlot = LdSlot; 1074f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1075f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1076f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1077f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Scan all of the operands of this instruction rewriting operands 1078f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // to use NewVReg instead of li.reg as appropriate. We do this for 1079f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // two reasons: 1080f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1081f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1. If the instr reads the same spilled vreg multiple times, we 1082f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // want to reuse the NewVReg. 1083f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 2. If the instr is a two-addr instruction, we are required to 1084f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // keep the src/dst regs pinned. 1085f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1086f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Keep track of whether we replace a use and/or def so that we can 10871b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // create the spill interval with the appropriate range. 1088aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 1089ead06be02fe6b9a2bf6fbe04237c1276ed0cdb5cJakob Stoklund Olesen tie(HasUse, HasDef) = MI->readsWritesVirtualRegister(Reg, &Ops); 1090f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 109126b86a0b5676253040dc206b437536a24306fb76David Greene // Create a new virtual register for the spill interval. 109226b86a0b5676253040dc206b437536a24306fb76David Greene // Create the new register now so we can map the fold instruction 109326b86a0b5676253040dc206b437536a24306fb76David Greene // to the new register so when it is unfolded we get the correct 109426b86a0b5676253040dc206b437536a24306fb76David Greene // answer. 109526b86a0b5676253040dc206b437536a24306fb76David Greene bool CreatedNewVReg = false; 109626b86a0b5676253040dc206b437536a24306fb76David Greene if (NewVReg == 0) { 109726b86a0b5676253040dc206b437536a24306fb76David Greene NewVReg = mri_->createVirtualRegister(rc); 109826b86a0b5676253040dc206b437536a24306fb76David Greene vrm.grow(); 109926b86a0b5676253040dc206b437536a24306fb76David Greene CreatedNewVReg = true; 1100ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen 1101ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen // The new virtual register should get the same allocation hints as the 1102ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen // old one. 1103ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(Reg); 1104ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen if (Hint.first || Hint.second) 1105ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen mri_->setRegAllocationHint(NewVReg, Hint.first, Hint.second); 110626b86a0b5676253040dc206b437536a24306fb76David Greene } 110726b86a0b5676253040dc206b437536a24306fb76David Greene 11089c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!TryFold) 11099c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanFold = false; 11109c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng else { 1111018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Do not fold load / store here if we are splitting. We'll find an 1112018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // optimal point to insert a load / store later. 1113018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (!TrySplit) { 1114018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 111526b86a0b5676253040dc206b437536a24306fb76David Greene Ops, FoldSS, FoldSlot, NewVReg)) { 1116018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Folding the load/store can completely change the instruction in 1117018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // unpredictable ways, rescan it from the beginning. 111826b86a0b5676253040dc206b437536a24306fb76David Greene 111926b86a0b5676253040dc206b437536a24306fb76David Greene if (FoldSS) { 112026b86a0b5676253040dc206b437536a24306fb76David Greene // We need to give the new vreg the same stack slot as the 112126b86a0b5676253040dc206b437536a24306fb76David Greene // spilled interval. 112226b86a0b5676253040dc206b437536a24306fb76David Greene vrm.assignVirt2StackSlot(NewVReg, FoldSlot); 112326b86a0b5676253040dc206b437536a24306fb76David Greene } 112426b86a0b5676253040dc206b437536a24306fb76David Greene 1125018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasUse = false; 1126018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasDef = false; 1127018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng CanFold = false; 1128c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng if (isNotInMIMap(MI)) 11297e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng break; 1130018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng goto RestartInstruction; 1131018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1132018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } else { 11339c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // We'll try to fold it later if it's profitable. 11343c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 1135018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 11369c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng } 1137cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1138cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mop.setReg(NewVReg); 1139d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mop.isImplicit()) 1140d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1141cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1142cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Reuse NewVReg for other reads. 11437c2e4a8715836a44e82ac6c7370826519ccdfddbJakob Stoklund Olesen bool HasEarlyClobber = false; 1144d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 1145d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &mopj = MI->getOperand(Ops[j]); 1146d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng mopj.setReg(NewVReg); 1147d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mopj.isImplicit()) 1148d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 11497c2e4a8715836a44e82ac6c7370826519ccdfddbJakob Stoklund Olesen if (mopj.isEarlyClobber()) 11507c2e4a8715836a44e82ac6c7370826519ccdfddbJakob Stoklund Olesen HasEarlyClobber = true; 1151d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 11521b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 115381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 115481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (DefIsReMat) { 1155378445303b10b092a898a75131141a8259cff50bEvan Cheng vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI); 1156d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 115781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each valnum may have its own remat id. 1158d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 115981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 1160d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 116181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 116281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!CanDelete || (HasUse && HasDef)) { 116381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a two-addr instruction then its use operands are 116481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // rematerializable but its def is not. It should be assigned a 116581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // stack slot. 116681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 116781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1168f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1169f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1170f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1171cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng } else if (HasUse && HasDef && 1172cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1173cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // If this interval hasn't been assigned a stack slot (because earlier 1174cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // def is a deleted remat def), do it now. 1175cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng assert(Slot != VirtRegMap::NO_STACK_SLOT); 1176cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1177f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1178f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1179313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Add the 1180313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // register as an implicit use on the use MI. 1181313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (DefIsReMat && ImpUse) 1182313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1183313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 11845b69ebac857104770b1a751bf7a463fda4330a62Evan Cheng // Create a new register interval for this spill / remat. 1185f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 118681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 118781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng NewLIs.push_back(&nI); 11881953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 118981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (TrySplit) 119081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(NewVReg, li.reg); 119181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1192f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1193f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasUse) { 119481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 1195233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange LR(index.getLoadIndex(), index.getDefIndex(), 11966e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames nI.getNextValue(SlotIndex(), 0, VNInfoAllocator)); 11978a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 119881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 119981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 120081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Extend the split live interval to this def / use. 1201233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex End = index.getDefIndex(); 120281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 120381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getValNumInfo(nI.getNumValNums()-1)); 12048a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 120581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 120681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1207f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1208f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasDef) { 12097c2e4a8715836a44e82ac6c7370826519ccdfddbJakob Stoklund Olesen // An early clobber starts at the use slot, except for an early clobber 12107c2e4a8715836a44e82ac6c7370826519ccdfddbJakob Stoklund Olesen // tied to a use operand (yes, that is a thing). 12117c2e4a8715836a44e82ac6c7370826519ccdfddbJakob Stoklund Olesen LiveRange LR(HasEarlyClobber && !HasUse ? 12127c2e4a8715836a44e82ac6c7370826519ccdfddbJakob Stoklund Olesen index.getUseIndex() : index.getDefIndex(), 12137c2e4a8715836a44e82ac6c7370826519ccdfddbJakob Stoklund Olesen index.getStoreIndex(), 12146e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames nI.getNextValue(SlotIndex(), 0, VNInfoAllocator)); 12158a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 1216f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.addRange(LR); 1217f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 121881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 12198e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 12208a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\t\t\tAdded new interval: "; 12218a34229dcf484739119857988772572ef0cad9f2David Greene nI.print(dbgs(), tri_); 12228a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << '\n'; 12238e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 1224f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1225018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng return CanFold; 1226f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 122781a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 12280cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng const VNInfo *VNI, 12298651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineBasicBlock *MBB, 1230233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Idx) const { 123115a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen return li.killedInRange(Idx.getNextSlot(), getMBBEndIdx(MBB)); 123281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 123381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1234063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// RewriteInfo - Keep track of machine instrs that will be rewritten 1235063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// during spilling. 1236844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 1237844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfo { 1238233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index; 1239844731a7f1909f55935e3514c9e713a62d67662eDan Gohman MachineInstr *MI; 1240ead06be02fe6b9a2bf6fbe04237c1276ed0cdb5cJakob Stoklund Olesen RewriteInfo(SlotIndex i, MachineInstr *mi) : Index(i), MI(mi) {} 1241844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1242844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1243844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfoCompare { 1244844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1245844731a7f1909f55935e3514c9e713a62d67662eDan Gohman return LHS.Index < RHS.Index; 1246844731a7f1909f55935e3514c9e713a62d67662eDan Gohman } 1247844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1248844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} 1249063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1250f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengvoid LiveIntervals:: 125181a038218171860ee4c382849c647d3dc841fe8bEvan ChengrewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1252f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval::Ranges::const_iterator &I, 125381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1254f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1255f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1256d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1257f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1258f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 125922f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 126081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &SpillMBBs, 1261289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes, 12620cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector &RestoreMBBs, 1263289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes, 1264289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> &MBBVRegsMap, 1265c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1266018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool AllCanFold = true; 126781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned NewVReg = 0; 1268233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = I->start.getBaseIndex(); 1269233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); 1270f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1271063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // First collect all the def / use in this live range that will be rewritten. 12727e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Make sure they are sorted according to instruction index. 1273063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::vector<RewriteInfo> RewriteMIs; 1274d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1275d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->reg_end(); ri != re; ) { 1276419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1277063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineOperand &O = ri.getOperand(); 1278063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++ri; 1279bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen if (MI->isDebugValue()) { 1280962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng // Modify DBG_VALUE now that the value is in a spill slot. 12816691a8935c9f2e049ff5eed45ba2894f60108909Evan Cheng if (Slot != VirtRegMap::MAX_STACK_SLOT || isLoadSS) { 12826fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng uint64_t Offset = MI->getOperand(1).getImm(); 12836fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng const MDNode *MDPtr = MI->getOperand(2).getMetadata(); 12846fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng DebugLoc DL = MI->getDebugLoc(); 12856691a8935c9f2e049ff5eed45ba2894f60108909Evan Cheng int FI = isLoadSS ? LdSlot : (int)Slot; 12866691a8935c9f2e049ff5eed45ba2894f60108909Evan Cheng if (MachineInstr *NewDV = tii_->emitFrameIndexDebugValue(*mf_, FI, 12876fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng Offset, MDPtr, DL)) { 12886fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI); 12896fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng ReplaceMachineInstrInMaps(MI, NewDV); 12906fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 12916fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng MBB->insert(MBB->erase(MI), NewDV); 12926fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng continue; 12936fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng } 1294962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng } 12956fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng 12966fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); 12976fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng RemoveMachineInstrFromMaps(MI); 12986fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 12996fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng MI->eraseFromParent(); 1300bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen continue; 1301bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen } 130263e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen assert(!(O.isImplicit() && O.isUse()) && 130363e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen "Spilling register that's used as implicit use?"); 1304233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = getInstructionIndex(MI); 1305063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng if (index < start || index >= end) 1306063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng continue; 1307d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 1308d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (O.isUndef()) 130979a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // Must be defined by an implicit def. It should not be spilled. Note, 131079a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // this is for correctness reason. e.g. 131179a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 8 %reg1024<def> = IMPLICIT_DEF 131279a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 131379a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // The live range [12, 14) are not part of the r1024 live interval since 131479a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // it's defined by an implicit def. It will not conflicts with live 131579a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // interval of r1025. Now suppose both registers are spilled, you can 1316b9890ae3c35ad7d8e49261650d5b98f49f97a705Evan Cheng // easily see a situation where both registers are reloaded before 131779a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // the INSERT_SUBREG and both target registers that would overlap. 131879a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng continue; 1319ead06be02fe6b9a2bf6fbe04237c1276ed0cdb5cJakob Stoklund Olesen RewriteMIs.push_back(RewriteInfo(index, MI)); 1320063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 1321063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1322063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1323313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 1324063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // Now rewrite the defs and uses. 1325063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 1326063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteInfo &rwi = RewriteMIs[i]; 1327063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1328233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = rwi.Index; 1329063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineInstr *MI = rwi.MI; 1330063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // If MI def and/or use the same register multiple times, then there 1331063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // are multiple entries. 1332063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng while (i != e && RewriteMIs[i].MI == MI) { 1333063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng assert(RewriteMIs[i].Index == index); 1334063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1335063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 133681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1337313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 13380a891ed7d5875a9ccdb93b4472b0f43947d8289bEvan Cheng if (ImpUse && MI != ReMatDefMI) { 1339e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // Re-matting an instruction with virtual register use. Prevent interval 1340e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // from being spilled. 1341e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen getInterval(ImpUse).markNotSpillable(); 1342313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng } 1343313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1344063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned MBBId = MBB->getNumber(); 1345018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng unsigned ThisVReg = 0; 134670306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (TrySplit) { 1347289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId); 13481953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NVI != MBBVRegsMap.end()) { 1349018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = NVI->second; 13501953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // One common case: 13511953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // x = use 13521953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 13531953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 13541953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // def = ... 13551953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // = use 13561953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // It's better to start a new interval to avoid artifically 13571953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // extend the new interval. 1358ead06be02fe6b9a2bf6fbe04237c1276ed0cdb5cJakob Stoklund Olesen if (MI->readsWritesVirtualRegister(li.reg) == 1359ead06be02fe6b9a2bf6fbe04237c1276ed0cdb5cJakob Stoklund Olesen std::make_pair(false,true)) { 13601953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.erase(MBB->getNumber()); 1361018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = 0; 13621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 13631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 1364cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng } 1365018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1366018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool IsNew = ThisVReg == 0; 1367018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (IsNew) { 1368018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // This ends the previous live interval. If all of its def / use 1369018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // can be folded, give it a low spill weight. 1370018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1371018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1372018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1373018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1374018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold = true; 1375018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1376018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng NewVReg = ThisVReg; 1377018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 137881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasDef = false; 137981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasUse = false; 1380d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 13819c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng index, end, MI, ReMatOrigDefMI, ReMatDefMI, 13829c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 13839c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 1384c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); 138581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!HasDef && !HasUse) 138681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 138781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1388018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold &= CanFold; 1389018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 139081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Update weight of spill interval. 139181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 139270306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (!TrySplit) { 139381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // The spill weight is now infinity as it cannot be spilled again. 1394e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen nI.markNotSpillable(); 13950cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 13960cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 13970cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 13980cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Keep track of the last def and first use in each MBB. 13990cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasDef) { 14000cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MI != ReMatOrigDefMI || !CanDelete) { 14010cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool HasKill = false; 14020cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasUse) 1403233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, index.getDefIndex()); 14040cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else { 14051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // If this is a two-address code, then this index starts a new VNInfo. 1406233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const VNInfo *VNI = li.findDefinedVNInfoForRegInt(index.getDefIndex()); 14070cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VNI) 1408233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, index.getDefIndex()); 140981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1410289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 1411e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.find(MBBId); 14120cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasKill) { 14131953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII == SpillIdxes.end()) { 14141953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> S; 14151953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng S.push_back(SRInfo(index, NewVReg, true)); 14161953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SpillIdxes.insert(std::make_pair(MBBId, S)); 14171953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if (SII->second.back().vreg != NewVReg) { 14181953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.push_back(SRInfo(index, NewVReg, true)); 14198651125d2885f74546b6e2a556082111d5b75da3Lang Hames } else if (index > SII->second.back().index) { 14200cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If there is an earlier def and this is a two-address 14210cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // instruction, then it's not possible to fold the store (which 14220cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // would also fold the load). 14231953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SRInfo &Info = SII->second.back(); 14241953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.index = index; 14251953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.canFold = !HasUse; 142681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 14270cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs.set(MBBId); 1428e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } else if (SII != SpillIdxes.end() && 1429e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.back().vreg == NewVReg && 14308651125d2885f74546b6e2a556082111d5b75da3Lang Hames index > SII->second.back().index) { 1431e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // There is an earlier def that's not killed (must be two-address). 1432e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // The spill is no longer needed. 1433e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.pop_back(); 1434e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng if (SII->second.empty()) { 1435e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.erase(MBBId); 1436e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillMBBs.reset(MBBId); 1437e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } 143881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 143981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 14400cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 144181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 14420cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasUse) { 1443289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 14440cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillIdxes.find(MBBId); 14451953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII != SpillIdxes.end() && 14461953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().vreg == NewVReg && 14478651125d2885f74546b6e2a556082111d5b75da3Lang Hames index > SII->second.back().index) 14480cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Use(s) following the last def, it's not safe to fold the spill. 14491953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().canFold = false; 1450289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator RII = 14510cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreIdxes.find(MBBId); 14521953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 14530cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If we are splitting live intervals, only fold if it's the first 14540cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // use and there isn't another use later in the MBB. 14551953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.back().canFold = false; 14560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else if (IsNew) { 14570cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Only need a reload if there isn't an earlier def / use. 14581953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII == RestoreIdxes.end()) { 14591953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> Infos; 14601953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Infos.push_back(SRInfo(index, NewVReg, true)); 14611953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 14621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else { 14631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.push_back(SRInfo(index, NewVReg, true)); 14641953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 14650cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreMBBs.set(MBBId); 14660cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 146781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 14680cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 14690cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Update spill weight. 147022f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 1471c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1472f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1473018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1474018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1475018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // If all of its def / use can be folded, give it a low spill weight. 1476018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1477018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1478018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1479f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1480f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1481233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesbool LiveIntervals::alsoFoldARestore(int Id, SlotIndex index, 14828651125d2885f74546b6e2a556082111d5b75da3Lang Hames unsigned vr, BitVector &RestoreMBBs, 1483289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 14841953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 14851953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 14861953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 14871953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 14881953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && 14891953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].vreg == vr && 14901953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].canFold) 14911953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return true; 14921953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 14931953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 14941953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1495233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveIntervals::eraseRestoreInfo(int Id, SlotIndex index, 14968651125d2885f74546b6e2a556082111d5b75da3Lang Hames unsigned vr, BitVector &RestoreMBBs, 1497289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 14981953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 14991953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return; 15001953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 15011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 15021953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && Restores[i].vreg) 1503233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames Restores[i].index = SlotIndex(); 15041953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 150581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 15064cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 15074cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// spilled and create empty intervals for their uses. 15084cce6b4c7882ef0cc993d931b90bf33985c96110Evan Chengvoid 15094cce6b4c7882ef0cc993d931b90bf33985c96110Evan ChengLiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 15104cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng const TargetRegisterClass* rc, 15114cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1512419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1513419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng re = mri_->reg_end(); ri != re; ) { 15144cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &O = ri.getOperand(); 1515419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1516419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng ++ri; 151728a1e486907104b85c5787345914917d74f0cf77Evan Cheng if (MI->isDebugValue()) { 151828a1e486907104b85c5787345914917d74f0cf77Evan Cheng // Remove debug info for now. 151928a1e486907104b85c5787345914917d74f0cf77Evan Cheng O.setReg(0U); 152028a1e486907104b85c5787345914917d74f0cf77Evan Cheng DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); 152128a1e486907104b85c5787345914917d74f0cf77Evan Cheng continue; 152228a1e486907104b85c5787345914917d74f0cf77Evan Cheng } 15234cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng if (O.isDef()) { 1524518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner assert(MI->isImplicitDef() && 15254cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng "Register def was not rewritten?"); 15264cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng RemoveMachineInstrFromMaps(MI); 15274cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 15284cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MI->eraseFromParent(); 15294cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } else { 15304cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // This must be an use of an implicit_def so it's not part of the live 15314cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // interval. Create a new empty live interval for it. 15324cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // FIXME: Can we simply erase some of the instructions? e.g. Stores? 15334cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng unsigned NewVReg = mri_->createVirtualRegister(rc); 15344cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.grow(); 15354cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.setIsImplicitlyDefined(NewVReg); 15364cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng NewLIs.push_back(&getOrCreateInterval(NewVReg)); 15374cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 15384cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &MO = MI->getOperand(i); 15394784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng if (MO.isReg() && MO.getReg() == li.reg) { 15404cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MO.setReg(NewVReg); 15414784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng MO.setIsUndef(); 15424784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng } 15434cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 15444cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 1545419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 1546419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng} 1547419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 1548e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesenfloat 1549e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund OlesenLiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { 1550e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // Limit the loop depth ridiculousness. 1551e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen if (loopDepth > 200) 1552e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen loopDepth = 200; 1553e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 1554e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // The loop depth is used to roughly estimate the number of times the 1555e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // instruction is executed. Something like 10^d is simple, but will quickly 1556e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // overflow a float. This expression behaves like 10^d for small d, but is 1557e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of 1558e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // headroom before overflow. 155987565c1d779a1903d10ddd11d886c0f79ee430b5Chris Lattner float lc = std::pow(1 + (100.0f / (loopDepth+10)), (float)loopDepth); 1560e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 1561e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen return (isDef + isUse) * lc; 1562e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen} 1563e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 1564352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesenvoid 1565352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund OlesenLiveIntervals::normalizeSpillWeights(std::vector<LiveInterval*> &NewLIs) { 1566352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) 1567352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen normalizeSpillWeight(*NewLIs[i]); 1568352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen} 1569352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen 1570f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengstd::vector<LiveInterval*> LiveIntervals:: 157181a038218171860ee4c382849c647d3dc841fe8bEvan ChengaddIntervalsForSpills(const LiveInterval &li, 1572f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick const SmallVectorImpl<LiveInterval*> &SpillIs, 1573c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { 1574e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen assert(li.isSpillable() && "attempt to spill already spilled interval!"); 1575f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 15768e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 15778a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\t\t\tadding intervals for spills for interval: "; 15788a34229dcf484739119857988772572ef0cad9f2David Greene li.print(dbgs(), tri_); 15798a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << '\n'; 15808e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 1581f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 158272eeb94fe1d69cd05bdbbe86b2bc9fa25c963c22Evan Cheng // Each bit specify whether a spill is required in the MBB. 158381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector SpillMBBs(mf_->getNumBlockIDs()); 1584289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes; 15850cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector RestoreMBBs(mf_->getNumBlockIDs()); 1586289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes; 1587289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> MBBVRegsMap; 1588f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> NewLIs; 1589d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1590f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1591f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned NumValNums = li.getNumValNums(); 1592f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatDefs; 1593f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDefs.resize(NumValNums, NULL); 1594f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1595f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatOrigDefs.resize(NumValNums, NULL); 1596f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> ReMatIds; 1597f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1598f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng BitVector ReMatDelete(NumValNums); 1599f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1600f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 160181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Spilling a split live interval. It cannot be split any further. Also, 160281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // it's also guaranteed to be a single val# / range interval. 160381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (vrm.getPreSplitReg(li.reg)) { 160481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(li.reg, 0); 1605d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng // Unset the split kill marker on the last use. 1606233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex KillIdx = vrm.getKillPoint(li.reg); 1607233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (KillIdx != SlotIndex()) { 1608d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1609d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillMI && "Last use disappeared?"); 1610d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1611d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillOp != -1 && "Last use disappeared?"); 1612f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner KillMI->getOperand(KillOp).setIsKill(false); 1613d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng } 1614adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng vrm.removeKillPoint(li.reg); 161581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = vrm.isReMaterialized(li.reg); 161681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot = vrm.getStackSlot(li.reg); 161781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng assert(Slot != VirtRegMap::MAX_STACK_SLOT); 161881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = DefIsReMat ? 161981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.getReMaterializedMI(li.reg) : NULL; 162081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int LdSlot = 0; 162181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 162281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoad = isLoadSS || 162315511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad())); 162481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool IsFirstRange = true; 162581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 162681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 162781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a split live interval with multiple ranges, it means there 162881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // are two-address instructions that re-defined the value. Only the 162981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // first def can be rematerialized! 163081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (IsFirstRange) { 1631cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // Note ReMatOrigDefMI has already been deleted. 163281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 163381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1634d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 16350cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1636c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 163781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 163881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, 0, 163981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, 0, false, false, false, 1640d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 16410cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1642c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 164381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 164481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng IsFirstRange = false; 164581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1646419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 16474cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 1648352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen normalizeSpillWeights(NewLIs); 164981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return NewLIs; 165081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 165181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1652752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng bool TrySplit = !intervalIsInOneMBB(li); 16530cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (TrySplit) 16540cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numSplits; 1655f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool NeedStackSlot = false; 1656f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1657f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng i != e; ++i) { 1658f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const VNInfo *VNI = *i; 1659f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned VN = VNI->id; 1660857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->isUnused()) 1661f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; // Dead val#. 1662f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Is the def for the val# rematerializable? 16636e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 16645ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool dummy; 1665dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) { 1666f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Remember how to remat the def of this val#. 166781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReMatOrigDefs[VN] = ReMatDefMI; 16682c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman // Original def may be modified so we have to make a copy here. 16691ed9922794cda9dbe295e74674b909287e544632Evan Cheng MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI); 1670752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng CloneMIs.push_back(Clone); 16711ed9922794cda9dbe295e74674b909287e544632Evan Cheng ReMatDefs[VN] = Clone; 1672f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1673f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = true; 1674857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->hasPHIKill()) { 1675c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // A kill is a phi node, not all of its uses can be rematerialized. 1676f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // It must not be deleted. 1677c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng CanDelete = false; 1678c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // Need a stack slot if there is any live range where uses cannot be 1679c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // rematerialized. 1680c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng NeedStackSlot = true; 1681f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1682f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (CanDelete) 1683f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDelete.set(VN); 1684f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1685f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Need a stack slot if there is any live range where uses cannot be 1686f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // rematerialized. 1687f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng NeedStackSlot = true; 1688f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1689f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1690f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1691f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // One stack slot per live interval. 1692b98bbb7597495fb401b020679a94389298175506Owen Anderson if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) { 1693b98bbb7597495fb401b020679a94389298175506Owen Anderson if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT) 1694b98bbb7597495fb401b020679a94389298175506Owen Anderson Slot = vrm.assignVirt2StackSlot(li.reg); 16951b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 1696b98bbb7597495fb401b020679a94389298175506Owen Anderson // This case only occurs when the prealloc splitter has already assigned 1697b98bbb7597495fb401b020679a94389298175506Owen Anderson // a stack slot to this vreg. 1698b98bbb7597495fb401b020679a94389298175506Owen Anderson else 1699b98bbb7597495fb401b020679a94389298175506Owen Anderson Slot = vrm.getStackSlot(li.reg); 1700b98bbb7597495fb401b020679a94389298175506Owen Anderson } 1701f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1702f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Create new intervals and rewrite defs and uses. 1703f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::Ranges::const_iterator 1704f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 170581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 170681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 170781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = ReMatDefMI != NULL; 1708f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = ReMatDelete[I->valno->id]; 1709f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int LdSlot = 0; 171081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1711f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad = isLoadSS || 171215511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad()); 171381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 17140cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1715d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, 17160cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1717c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 1718f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1719f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 17200cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Insert spills / restores if we are splitting. 1721419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng if (!TrySplit) { 17224cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 1723352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen normalizeSpillWeights(NewLIs); 17241953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return NewLIs; 1725419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 17261953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1727b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng SmallPtrSet<LiveInterval*, 4> AddedKill; 1728aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 17291953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NeedStackSlot) { 17301953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = SpillMBBs.find_first(); 17311953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 17321953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &spills = SpillIdxes[Id]; 17331953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = spills.size(); i != e; ++i) { 1734233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = spills[i].index; 17351953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = spills[i].vreg; 1736597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 17370cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 17380cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1739aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1740aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool FoundUse = false; 1741aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1742cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (spills[i].canFold) { 1743aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 17440cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 17450cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineOperand &MO = MI->getOperand(j); 1746d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || MO.getReg() != VReg) 17470cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 1748aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 1749aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1750aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (MO.isDef()) 1751cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng continue; 17521b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen if (isReMat || 1753aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng (!FoundUse && !alsoFoldARestore(Id, index, VReg, 1754aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng RestoreMBBs, RestoreIdxes))) { 1755aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // MI has two-address uses of the same register. If the use 1756aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // isn't the first and only use in the BB, then we can't fold 1757aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // it. FIXME: Move this to rewriteInstructionsForSpills. 1758aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 1759cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng break; 1760cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 1761aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoundUse = true; 17620cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 17630cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 17640cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the store into the def if possible. 1765cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1766aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 1767aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 1768cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng Folded = true; 176948fe63526e35ddaee7e98879596a569911f41319Sebastian Redl if (FoundUse) { 1770aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Also folded uses, do not issue a load. 1771aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 1772233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.removeRange(index.getLoadIndex(), index.getDefIndex()); 1773f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng } 1774233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.removeRange(index.getDefIndex(), index.getStoreIndex()); 1775cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 17760cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 17770cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 17787e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Otherwise tell the spiller to issue a spill. 1779b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!Folded) { 1780b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 1781233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool isKill = LR->end == index.getStoreIndex(); 1782b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng if (!MI->registerDefIsDead(nI.reg)) 1783b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng // No need to spill a dead def. 1784b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng vrm.addSpillPoint(VReg, isKill, MI); 1785b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (isKill) 1786b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng AddedKill.insert(&nI); 1787b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 17880cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 17891953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = SpillMBBs.find_next(Id); 17900cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 17911953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 17920cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 17931953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = RestoreMBBs.find_first(); 17941953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 17951953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &restores = RestoreIdxes[Id]; 17961953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = restores.size(); i != e; ++i) { 1797233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = restores[i].index; 1798233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (index == SlotIndex()) 17991953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng continue; 18001953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = restores[i].vreg; 1801597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 18029c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 180381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1804aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1805aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1806cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (restores[i].canFold) { 1807aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 180881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 180981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineOperand &MO = MI->getOperand(j); 1810d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || MO.getReg() != VReg) 181181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 1812aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 18130cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MO.isDef()) { 1814aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // If this restore were to be folded, it would have been folded 1815aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // already. 1816aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 181781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng break; 181881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1819aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 182081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 182181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 18220cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 18230cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the load into the use if possible. 1824cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1825aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 18269c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!isReMat) 1827aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 1828aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 18290cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 18300cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng int LdSlot = 0; 18310cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 18320cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If the rematerializable def is a load, also try to fold it. 183315511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad()) 1834aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1835aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops, isLoadSS, LdSlot, VReg); 1836650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng if (!Folded) { 1837650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 1838650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng if (ImpUse) { 1839650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng // Re-matting an instruction with virtual register use. Add the 1840e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // register as an implicit use on the use MI and mark the register 1841e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // interval as unspillable. 1842650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 1843e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen ImpLi.markNotSpillable(); 1844650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1845650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng } 1846d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1847aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 18480cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 18490cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If folding is not possible / failed, then tell the spiller to issue a 18500cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // load / rematerialization for us. 1851597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (Folded) 1852233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.removeRange(index.getLoadIndex(), index.getDefIndex()); 1853b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng else 18540cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.addRestorePoint(VReg, MI); 185581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 18561953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = RestoreMBBs.find_next(Id); 185781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 185881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1859b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // Finalize intervals: add kills, finalize spill weights, and filter out 1860b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // dead intervals. 1861597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng std::vector<LiveInterval*> RetNewLIs; 1862597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 1863597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval *LI = NewLIs[i]; 1864597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (!LI->empty()) { 1865b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!AddedKill.count(LI)) { 1866b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 1867233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex LastUseIdx = LR->end.getBaseIndex(); 1868d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 18696130f66eaae89f8878590796977678afa8448926Evan Cheng int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 1870b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng assert(UseIdx != -1); 1871a24752ff43dc1ad8c18c5d9e78549c45f62b980eEvan Cheng if (!LastUse->isRegTiedToDefOperand(UseIdx)) { 1872b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LastUse->getOperand(UseIdx).setIsKill(); 1873d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng vrm.addKillPoint(LI->reg, LastUseIdx); 1874adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng } 1875b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 1876597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng RetNewLIs.push_back(LI); 1877597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 1878597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 187981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 18804cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 1881352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen normalizeSpillWeights(RetNewLIs); 1882597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng return RetNewLIs; 1883f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1884676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1885676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// hasAllocatableSuperReg - Return true if the specified physical register has 1886676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// any super register that's allocatable. 1887676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengbool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 1888676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 1889676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (allocatableRegs_[*AS] && hasInterval(*AS)) 1890676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return true; 1891676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return false; 1892676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1893676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1894676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getRepresentativeReg - Find the largest super register of the specified 1895676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// physical register. 1896676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 18971b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // Find the largest super-register that is allocatable. 1898676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned BestReg = Reg; 1899676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 1900676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SuperReg = *AS; 1901676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 1902676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng BestReg = SuperReg; 1903676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng break; 1904676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1905676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1906676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return BestReg; 1907676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1908676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1909676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getNumConflictsWithPhysReg - Return the number of uses and defs of the 1910676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// specified interval that conflicts with the specified physical register. 1911676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 1912676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg) const { 1913676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned NumConflicts = 0; 1914676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 1915676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 1916676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 1917676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 1918676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 191928a1e486907104b85c5787345914917d74f0cf77Evan Cheng if (MI->isDebugValue()) 192028a1e486907104b85c5787345914917d74f0cf77Evan Cheng continue; 1921233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index = getInstructionIndex(MI); 1922676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) 1923676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng ++NumConflicts; 1924676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1925676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return NumConflicts; 1926676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1927676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1928676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// spillPhysRegAroundRegDefsUses - Spill the specified physical register 19292824a655509577127d221eecd1425de196f80320Evan Cheng/// around all defs and uses of the specified interval. Return true if it 19302824a655509577127d221eecd1425de196f80320Evan Cheng/// was able to cut its interval. 19312824a655509577127d221eecd1425de196f80320Evan Chengbool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 1932676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg, VirtRegMap &vrm) { 1933676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SpillReg = getRepresentativeReg(PhysReg); 1934676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1935f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen DEBUG(dbgs() << "spillPhysRegAroundRegDefsUses " << tri_->getName(PhysReg) 1936f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen << " represented by " << tri_->getName(SpillReg) << '\n'); 1937f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen 1938676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 1939676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // If there are registers which alias PhysReg, but which are not a 1940676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // sub-register of the chosen representative super register. Assert 1941676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // since we can't handle it yet. 194270f2f65aacdbc96fe158b2860b5f0bad075ee548Dan Gohman assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) || 1943676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng tri_->isSuperRegister(*AS, SpillReg)); 1944676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 19452824a655509577127d221eecd1425de196f80320Evan Cheng bool Cut = false; 19460222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng SmallVector<unsigned, 4> PRegs; 19470222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng if (hasInterval(SpillReg)) 19480222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng PRegs.push_back(SpillReg); 1949f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen for (const unsigned *SR = tri_->getSubRegisters(SpillReg); *SR; ++SR) 1950f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen if (hasInterval(*SR)) 1951f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen PRegs.push_back(*SR); 1952f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen 1953f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen DEBUG({ 1954f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen dbgs() << "Trying to spill:"; 1955f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen for (unsigned i = 0, e = PRegs.size(); i != e; ++i) 1956f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen dbgs() << ' ' << tri_->getName(PRegs[i]); 1957f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen dbgs() << '\n'; 1958f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen }); 19590222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng 1960676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SmallPtrSet<MachineInstr*, 8> SeenMIs; 1961676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 1962676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 1963676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 1964676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 196528a1e486907104b85c5787345914917d74f0cf77Evan Cheng if (MI->isDebugValue() || SeenMIs.count(MI)) 1966676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 1967676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SeenMIs.insert(MI); 1968233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index = getInstructionIndex(MI); 1969f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen bool LiveReg = false; 19700222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng for (unsigned i = 0, e = PRegs.size(); i != e; ++i) { 19710222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng unsigned PReg = PRegs[i]; 19720222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng LiveInterval &pli = getInterval(PReg); 19730222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng if (!pli.liveAt(Index)) 19740222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng continue; 1975f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen LiveReg = true; 1976233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex StartIdx = Index.getLoadIndex(); 1977233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex EndIdx = Index.getNextIndex().getBaseIndex(); 1978f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen if (!pli.isInOneLiveRange(StartIdx, EndIdx)) { 19797d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin std::string msg; 19807d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin raw_string_ostream Msg(msg); 19817d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin Msg << "Ran out of registers during register allocation!"; 1982518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isInlineAsm()) { 19837d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin Msg << "\nPlease check your inline asm statement for invalid " 19840222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng << "constraints:\n"; 19857d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin MI->print(Msg, tm_); 19865a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng } 198775361b69f3f327842b9dad69fa7f28ae3b688412Chris Lattner report_fatal_error(Msg.str()); 19885a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng } 1989f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen pli.removeRange(StartIdx, EndIdx); 1990f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen LiveReg = true; 1991676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1992f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen if (!LiveReg) 1993f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen continue; 1994f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen DEBUG(dbgs() << "Emergency spill around " << Index << '\t' << *MI); 1995f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen vrm.addEmergencySpill(SpillReg, MI); 1996f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen Cut = true; 1997676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 19982824a655509577127d221eecd1425de196f80320Evan Cheng return Cut; 1999676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2000c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 2001c4dc132c8a787fc41b6a162121251234aa618965Owen AndersonLiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 2002ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames MachineInstr* startInst) { 2003c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveInterval& Interval = getOrCreateInterval(reg); 2004c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VNInfo* VN = Interval.getNextValue( 2005233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex(getInstructionIndex(startInst).getDefIndex()), 20066e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames startInst, getVNInfoAllocator()); 2007857c4e01f85601cf2084adb860616256ee47c177Lang Hames VN->setHasPHIKill(true); 20088651125d2885f74546b6e2a556082111d5b75da3Lang Hames LiveRange LR( 2009233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex(getInstructionIndex(startInst).getDefIndex()), 201074ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames getMBBEndIdx(startInst->getParent()), VN); 2011c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson Interval.addRange(LR); 20121b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 2013c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson return LR; 2014c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson} 2015b5257664795d49ada0d4669fe8ed1cd49c04fbf3David Greene 2016