LiveIntervalAnalysis.cpp revision dc5198bac7e3f9b61617c8c46a1c28a84daa9325
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" 23eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen#include "llvm/CodeGen/CalcSpillWeights.h" 24ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/LiveVariables.h" 25ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 26ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineInstr.h" 272578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng#include "llvm/CodeGen/MachineInstrBuilder.h" 2822f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 29c76909abfec876c6b751d693ebd3df07df686aa0Dan Gohman#include "llvm/CodeGen/MachineMemOperand.h" 3084bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 31ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/Passes.h" 32233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/ProcessImplicitDefs.h" 336f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 34ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 35ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 3695dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson#include "llvm/Target/TargetOptions.h" 37551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 38551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 397d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 407d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/raw_ostream.h" 412578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng#include "llvm/ADT/DepthFirstIterator.h" 422578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng#include "llvm/ADT/SmallSet.h" 43551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 44551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 4520aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 46f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames#include <limits> 4797af751deb9b26fd42fbcee082da9ccc4ded5b45Jeff Cohen#include <cmath> 48ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 49ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 50844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Hidden options for help debugging. 511b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesenstatic cl::opt<bool> DisableReMat("disable-rematerialization", 52844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(false), cl::Hidden); 53844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 54752195e3c662c6b5db042cf897c984624720f3b8Evan ChengSTATISTIC(numIntervals , "Number of original intervals"); 55752195e3c662c6b5db042cf897c984624720f3b8Evan ChengSTATISTIC(numFolds , "Number of loads/stores folded into instructions"); 56752195e3c662c6b5db042cf897c984624720f3b8Evan ChengSTATISTIC(numSplits , "Number of intervals split"); 57cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 581997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar LiveIntervals::ID = 0; 592ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", 602ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Live Interval Analysis", false, false) 612ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LiveVariables) 622ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 632ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(PHIElimination) 642ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(TwoAddressInstructionPass) 652ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(ProcessImplicitDefs) 662ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 672ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 682ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(LiveIntervals, "liveintervals", 69ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Live Interval Analysis", false, false) 70ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 71f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 72845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman AU.setPreservesCFG(); 736d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addRequired<AliasAnalysis>(); 746d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addPreserved<AliasAnalysis>(); 751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LiveVariables>(); 76148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng AU.addPreserved<LiveVariables>(); 77148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng AU.addRequired<MachineLoopInfo>(); 78148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng AU.addPreserved<MachineLoopInfo>(); 7967d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineDominatorsID); 801b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 8195dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson if (!StrongPHIElim) { 8295dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson AU.addPreservedID(PHIEliminationID); 8395dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson AU.addRequiredID(PHIEliminationID); 8495dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson } 851b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 87233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addPreserved<ProcessImplicitDefs>(); 88233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addRequired<ProcessImplicitDefs>(); 89233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addPreserved<SlotIndexes>(); 90233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addRequiredTransitive<SlotIndexes>(); 911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 92ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 93ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 94f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::releaseMemory() { 9503857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson // Free the live intervals themselves. 9620e2839cb975a2d4ee931e1ea4c4660a36ef0177Owen Anderson for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(), 97d6a6b3b7563a3f54ba48d465fc03ee10bbccb7a8Bob Wilson E = r2iMap_.end(); I != E; ++I) 9803857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson delete I->second; 991b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 1001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 101ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 102ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. 103ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer VNInfoAllocator.Reset(); 104752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng while (!CloneMIs.empty()) { 105752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng MachineInstr *MI = CloneMIs.back(); 106752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng CloneMIs.pop_back(); 1071ed9922794cda9dbe295e74674b909287e544632Evan Cheng mf_->DeleteMachineInstr(MI); 1081ed9922794cda9dbe295e74674b909287e544632Evan Cheng } 109993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 110993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 11180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// runOnMachineFunction - Register allocate the whole function 11280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// 11380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Andersonbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 11480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mf_ = &fn; 11580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mri_ = &mf_->getRegInfo(); 11680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tm_ = &fn.getTarget(); 11780b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tri_ = tm_->getRegisterInfo(); 11880b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tii_ = tm_->getInstrInfo(); 1196d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman aa_ = &getAnalysis<AliasAnalysis>(); 12080b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson lv_ = &getAnalysis<LiveVariables>(); 121233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames indexes_ = &getAnalysis<SlotIndexes>(); 12280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson allocatableRegs_ = tri_->getAllocatableSet(fn); 123ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 125ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 127843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 12870ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 1291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 130ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 131ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 13270ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 13345cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattnervoid LiveIntervals::print(raw_ostream &OS, const Module* ) const { 134705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "********** INTERVALS **********\n"; 1358e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 136705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner I->second->print(OS, tri_); 137705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "\n"; 1388e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 13970ca358b7d540b6061236ddf757085042873c12cChris Lattner 140752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printInstrs(OS); 141752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng} 142752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 143752195e3c662c6b5db042cf897c984624720f3b8Evan Chengvoid LiveIntervals::printInstrs(raw_ostream &OS) const { 144705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "********** MACHINEINSTRS **********\n"; 145f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen mf_->print(OS, indexes_); 14670ca358b7d540b6061236ddf757085042873c12cChris Lattner} 14770ca358b7d540b6061236ddf757085042873c12cChris Lattner 148752195e3c662c6b5db042cf897c984624720f3b8Evan Chengvoid LiveIntervals::dumpInstrs() const { 1498a34229dcf484739119857988772572ef0cad9f2David Greene printInstrs(dbgs()); 150752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng} 151752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 152cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesenbool LiveIntervals::conflictsWithPhysReg(const LiveInterval &li, 153cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen VirtRegMap &vrm, unsigned reg) { 154cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // We don't handle fancy stuff crossing basic block boundaries 155cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (li.ranges.size() != 1) 156cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen return true; 157cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen const LiveRange &range = li.ranges.front(); 158cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen SlotIndex idx = range.start.getBaseIndex(); 159cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen SlotIndex end = range.end.getPrevSlot().getBaseIndex().getNextIndex(); 160cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 161cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // Skip deleted instructions 162cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen MachineInstr *firstMI = getInstructionFromIndex(idx); 163cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen while (!firstMI && idx != end) { 164cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen idx = idx.getNextIndex(); 165cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen firstMI = getInstructionFromIndex(idx); 166cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen } 167cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (!firstMI) 168cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen return false; 169cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 170cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // Find last instruction in range 171cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen SlotIndex lastIdx = end.getPrevIndex(); 172cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen MachineInstr *lastMI = getInstructionFromIndex(lastIdx); 173cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen while (!lastMI && lastIdx != idx) { 174cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen lastIdx = lastIdx.getPrevIndex(); 175cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen lastMI = getInstructionFromIndex(lastIdx); 176cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen } 177cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (!lastMI) 178cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen return false; 179cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 180cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // Range cannot cross basic block boundaries or terminators 181cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen MachineBasicBlock *MBB = firstMI->getParent(); 182cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (MBB != lastMI->getParent() || lastMI->getDesc().isTerminator()) 183cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen return true; 184cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 185cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen MachineBasicBlock::const_iterator E = lastMI; 186cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen ++E; 187cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen for (MachineBasicBlock::const_iterator I = firstMI; I != E; ++I) { 188cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen const MachineInstr &MI = *I; 189cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 190cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // Allow copies to and from li.reg 1918ea324093cd512acc37f7b5a60e511e64103699eJakob Stoklund Olesen if (MI.isCopy()) 1928ea324093cd512acc37f7b5a60e511e64103699eJakob Stoklund Olesen if (MI.getOperand(0).getReg() == li.reg || 1938ea324093cd512acc37f7b5a60e511e64103699eJakob Stoklund Olesen MI.getOperand(1).getReg() == li.reg) 1948ea324093cd512acc37f7b5a60e511e64103699eJakob Stoklund Olesen continue; 195cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen 196cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // Check for operands using reg 197cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 198cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen const MachineOperand& mop = MI.getOperand(i); 199cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (!mop.isReg()) 200cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen continue; 201cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen unsigned PhysReg = mop.getReg(); 202cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (PhysReg == 0 || PhysReg == li.reg) 203cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen continue; 204cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { 205cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (!vrm.hasPhys(PhysReg)) 206c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 207cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen PhysReg = vrm.getPhys(PhysReg); 208c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 209cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen if (PhysReg && tri_->regsOverlap(PhysReg, reg)) 210cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen return true; 211c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 212c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 213c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 214cf97036675340bc889cfe04295cda63afe9496e2Jakob Stoklund Olesen // No conflicts found. 215c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return false; 216c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng} 217c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 218a24986d8bfd941252f7d080943e02bbe6a0c2944Jakob Stoklund Olesenbool LiveIntervals::conflictsWithAliasRef(LiveInterval &li, unsigned Reg, 2198f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng SmallPtrSet<MachineInstr*,32> &JoinedCopies) { 2208f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng for (LiveInterval::Ranges::const_iterator 2218f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 222233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames for (SlotIndex index = I->start.getBaseIndex(), 223233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); 224233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames index != end; 225233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames index = index.getNextIndex()) { 226f4811a96941433fc3828869d76dfeba5ec5decd3Jakob Stoklund Olesen MachineInstr *MI = getInstructionFromIndex(index); 227f4811a96941433fc3828869d76dfeba5ec5decd3Jakob Stoklund Olesen if (!MI) 228f4811a96941433fc3828869d76dfeba5ec5decd3Jakob Stoklund Olesen continue; // skip deleted instructions 2298f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 2308f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (JoinedCopies.count(MI)) 2318f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 2328f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 2338f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng MachineOperand& MO = MI->getOperand(i); 2348f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (!MO.isReg()) 2358f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 2368f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng unsigned PhysReg = MO.getReg(); 237a24986d8bfd941252f7d080943e02bbe6a0c2944Jakob Stoklund Olesen if (PhysReg == 0 || PhysReg == Reg || 238a24986d8bfd941252f7d080943e02bbe6a0c2944Jakob Stoklund Olesen TargetRegisterInfo::isVirtualRegister(PhysReg)) 2398f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 240a24986d8bfd941252f7d080943e02bbe6a0c2944Jakob Stoklund Olesen if (tri_->regsOverlap(Reg, PhysReg)) 2418f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng return true; 2428f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 2438f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 2448f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 2458f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 2468f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng return false; 2478f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng} 2488f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 249afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Chengstatic 2503749943648772743c9c0e852553e50e6700a0c1bEvan Chengbool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) { 251afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng unsigned Reg = MI.getOperand(MOIdx).getReg(); 252afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) { 253afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng const MachineOperand &MO = MI.getOperand(i); 254afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng if (!MO.isReg()) 255afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng continue; 256afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng if (MO.getReg() == Reg && MO.isDef()) { 257afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() && 258afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng MI.getOperand(MOIdx).getSubReg() && 259ed2185e171a86b8c0e166803fd4066383a6cff08Jakob Stoklund Olesen (MO.getSubReg() || MO.isImplicit())); 260afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return true; 261afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng } 262afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng } 263afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return false; 264afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng} 265afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng 2663749943648772743c9c0e852553e50e6700a0c1bEvan Cheng/// isPartialRedef - Return true if the specified def at the specific index is 2673749943648772743c9c0e852553e50e6700a0c1bEvan Cheng/// partially re-defining the specified live interval. A common case of this is 2681b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen/// a definition of the sub-register. 2693749943648772743c9c0e852553e50e6700a0c1bEvan Chengbool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO, 2703749943648772743c9c0e852553e50e6700a0c1bEvan Cheng LiveInterval &interval) { 2713749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (!MO.getSubReg() || MO.isEarlyClobber()) 2723749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return false; 2733749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 2743749943648772743c9c0e852553e50e6700a0c1bEvan Cheng SlotIndex RedefIndex = MIIdx.getDefIndex(); 2753749943648772743c9c0e852553e50e6700a0c1bEvan Cheng const LiveRange *OldLR = 2763749943648772743c9c0e852553e50e6700a0c1bEvan Cheng interval.getLiveRangeContaining(RedefIndex.getUseIndex()); 2776e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def); 2786e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames if (DefMI != 0) { 2793749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return DefMI->findRegisterDefOperandIdx(interval.reg) != -1; 2803749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } 2813749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return false; 2823749943648772743c9c0e852553e50e6700a0c1bEvan Cheng} 2833749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 284be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 285ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 286233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 2878651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineOperand& MO, 288ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx, 289be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 2904314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_)); 291419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 292706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 293706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 294706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 2951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 296d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 2971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 2981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 299233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex defIndex = MIIdx.getDefIndex(); 30039faac2531268b8555475796c6071556670dc290Dale Johannesen // Earlyclobbers move back one, so that they overlap the live range 30139faac2531268b8555475796c6071556670dc290Dale Johannesen // of inputs. 30286b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen if (MO.isEarlyClobber()) 303233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames defIndex = MIIdx.getUseIndex(); 30463e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen 30563e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen // Make sure the first definition is not a partial redefinition. Add an 30663e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen // <imp-def> of the full register. 30763e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen if (MO.getSubReg()) 30863e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen mi->addRegisterDefined(interval.reg); 30963e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen 310c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 31104c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (mi->isCopyLike()) { 312c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 3130465bcffbbffb5ff5f420787b4350cb8abb196f7Jakob Stoklund Olesen } 3140465bcffbbffb5ff5f420787b4350cb8abb196f7Jakob Stoklund Olesen 3156e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames VNInfo *ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 3167ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(ValNo->id == 0 && "First value in interval is not 0?"); 3171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 3191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 3201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 3211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 3221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 3231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 324233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex killIdx; 3251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 326233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex(); 3271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 328233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames killIdx = defIndex.getStoreIndex(); 3291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 3311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 3321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 333493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin assert(vi.AliveBlocks.empty() && 3341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 3357ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIdx, ValNo); 3361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3378a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << "\n"); 3381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 3391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3416097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 3421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 3431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 3441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 3451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 34674ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo); 3478a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << NewLR); 3481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 3491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 350dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen bool PHIJoin = lv_->isPHIJoin(interval.reg); 351dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 352dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen if (PHIJoin) { 353dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // A phi join register is killed at the end of the MBB and revived as a new 354dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // valno in the killing blocks. 355dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks"); 356dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " phi-join"); 357dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->setHasPHIKill(true); 358dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } else { 359dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // Iterate over all of the blocks that the variable is completely 360dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 361dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // live interval. 362dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 363dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen E = vi.AliveBlocks.end(); I != E; ++I) { 364dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I); 365dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo); 366dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen interval.addRange(LR); 367dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " +" << LR); 368dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } 3691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 3721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 3731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 3741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 375dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen SlotIndex Start = getMBBStartIdx(Kill->getParent()); 376dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen SlotIndex killIdx = getInstructionIndex(Kill).getDefIndex(); 377dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 378dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // Create interval with one of a NEW value number. Note that this value 379dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // number isn't actually defined by an instruction, weird huh? :) 380dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen if (PHIJoin) { 3816e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames assert(getInstructionFromIndex(Start) == 0 && 3826e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames "PHI def index points at actual instruction."); 3836e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames ValNo = interval.getNextValue(Start, 0, VNInfoAllocator); 384dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->setIsPHIDef(true); 385dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } 386dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LiveRange LR(Start, killIdx, ValNo); 3871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3888a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 3891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 3923749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (MultipleDefsBySameMI(*mi, MOIdx)) 393761fd4c1d97977c16de9f0cf921056a37b906304Nick Lewycky // Multiple defs of the same virtual register by the same instruction. 394761fd4c1d97977c16de9f0cf921056a37b906304Nick Lewycky // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ... 395afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng // This is likely due to elimination of REG_SEQUENCE instructions. Return 396afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng // here since there is nothing to do. 397afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return; 398afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng 3991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 4001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 401bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 402bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 4033749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 4043749943648772743c9c0e852553e50e6700a0c1bEvan Cheng // It may also be partial redef like this: 4051b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // 80 %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0 4061b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0 4073749943648772743c9c0e852553e50e6700a0c1bEvan Cheng bool PartReDef = isPartialRedef(MIIdx, MO, interval); 4083749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) { 4091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 4101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 4111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 4121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 4131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 414233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex RedefIndex = MIIdx.getDefIndex(); 415fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 416233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames RedefIndex = MIIdx.getUseIndex(); 4171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 41835f291d2c5f80e8e713704190230064311bbbbbeLang Hames const LiveRange *OldLR = 419233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames interval.getLiveRangeContaining(RedefIndex.getUseIndex()); 4207ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *OldValNo = OldLR->valno; 421c66d0f2a9386cc7cb3237b8e3cace2b62a9c7dc8Jakob Stoklund Olesen SlotIndex DefIndex = OldValNo->def.getDefIndex(); 4224f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 423c66d0f2a9386cc7cb3237b8e3cace2b62a9c7dc8Jakob Stoklund Olesen // Delete the previous value, which should be short and continuous, 424be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 4251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 426706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 42791725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 42891725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 4296e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator); 430857c4e01f85601cf2084adb860616256ee47c177Lang Hames 43191725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 432c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->def = RedefIndex; 433ad6c5a20ba87e7aba91ef7e8b270715a25379770Evan Cheng OldValNo->setCopy(0); 434ad6c5a20ba87e7aba91ef7e8b270715a25379770Evan Cheng 435ad6c5a20ba87e7aba91ef7e8b270715a25379770Evan Cheng // A re-def may be a copy. e.g. %reg1030:6<def> = VMOVD %reg1026, ... 43604c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (PartReDef && mi->isCopyLike()) 437ad6c5a20ba87e7aba91ef7e8b270715a25379770Evan Cheng OldValNo->setCopy(&*mi); 4381b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 439be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 440be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 4418a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " replace range with " << LR); 4421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 4451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 4466b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) 447233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(), 448233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames OldValNo)); 4491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4508e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 4518a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << " RESULT: "; 4528a34229dcf484739119857988772572ef0cad9f2David Greene interval.print(dbgs(), tri_); 4538e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 4543749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } else if (lv_->isPHIJoin(interval.reg)) { 4551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 4561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 4571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 458dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 459233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex defIndex = MIIdx.getDefIndex(); 460fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 461233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames defIndex = MIIdx.getUseIndex(); 462752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 4637ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 464c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 46504c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (mi->isCopyLike()) 466c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 4676e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 4681b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 46974ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames SlotIndex killIndex = getMBBEndIdx(mbb); 4707ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 4711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 472857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasPHIKill(true); 473dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " phi-join +" << LR); 4743749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } else { 4753749943648772743c9c0e852553e50e6700a0c1bEvan Cheng llvm_unreachable("Multiply defined register"); 476dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 4771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 478ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 4798a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << '\n'); 480ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 481ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 482f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 483ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 484233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 4856b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson MachineOperand& MO, 48691725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveInterval &interval, 487c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI) { 4881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 4891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 4904314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_)); 4911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 492233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 493233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = baseIndex.getDefIndex(); 49486b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen // Earlyclobbers move back one. 49586b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen if (MO.isEarlyClobber()) 496233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames start = MIIdx.getUseIndex(); 497233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = start; 4981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 5001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 5011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 50239faac2531268b8555475796c6071556670dc290Dale Johannesen // For earlyclobbers, the defSlot was pushed back one; the extra 50339faac2531268b8555475796c6071556670dc290Dale Johannesen // advance below compensates. 5046b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) { 5058a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 506233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = start.getStoreIndex(); 507ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 5081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 509ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 5101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 5111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 5121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 513233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 5145ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 515233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 516bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen if (mi->isDebugValue()) 517bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen continue; 518233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 519233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 520233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 5216130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 5228a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " killed"); 523233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = baseIndex.getDefIndex(); 524ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 525c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 5261015ba7018c87f48cc7bb45a564eb4a27241e76aEvan Cheng int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_); 527c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (DefIdx != -1) { 528c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (mi->isRegTiedToUseOperand(DefIdx)) { 529c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Two-address instruction. 530233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = baseIndex.getDefIndex(); 531c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 532c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Another instruction redefines the register before it is ever read. 533bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // Then the register is essentially dead at the instruction that 534bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // defines it. Hence its interval is: 535c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // [defSlot(def), defSlot(def)+1) 5368a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 537233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = start.getStoreIndex(); 538c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 539c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng goto exit; 540c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 541f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5421b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 543233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 5441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5451b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 5465ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 5475ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 548d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // and never used. Another possible case is the implicit use of the 549d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // physical register has been deleted by two-address pass. 550233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = start.getStoreIndex(); 55102ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 552ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 5531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 554f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 55524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 55631cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen VNInfo *ValNo = interval.getVNInfoAt(start); 55731cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen bool Extend = ValNo != 0; 55831cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen if (!Extend) 55931cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen ValNo = interval.getNextValue(start, CopyMI, VNInfoAllocator); 56031cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen if (Extend && MO.isEarlyClobber()) 561857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasRedefByEC(true); 5627ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 5631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 5648a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << '\n'); 565ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 566ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 567f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 568f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 569233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 570ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng MachineOperand& MO, 571ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx) { 5726b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 573ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 5746b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg())); 5756b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson else if (allocatableRegs_[MO.getReg()]) { 576c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 57704c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (MI->isCopyLike()) 578c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = MI; 579c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 5806b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg()), CopyMI); 58124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Def of a register also defines its sub-registers. 5826b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS) 5836130f66eaae89f8878590796977678afa8448926Evan Cheng // If MI also modifies the sub-register explicitly, avoid processing it 5846130f66eaae89f8878590796977678afa8448926Evan Cheng // more than once. Do not pass in TRI here so it checks for exact match. 5851015ba7018c87f48cc7bb45a564eb4a27241e76aEvan Cheng if (!MI->definesRegister(*AS)) 586c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 5876b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(*AS), 0); 588f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5894d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 5904d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 591b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 592233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 59324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 5944314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tlivein register: " << PrintReg(interval.reg, tri_)); 595b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 596b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 597b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 598b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 5994507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng MachineBasicBlock::iterator E = MBB->end(); 6004507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // Skip over DBG_VALUE at the start of the MBB. 6014507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi != E && mi->isDebugValue()) { 6024507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng while (++mi != E && mi->isDebugValue()) 6034507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng ; 6044507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi == E) 6054507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // MBB is empty except for DBG_VALUE's. 6064507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng return; 6074507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng } 6084507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng 609233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 610233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = baseIndex; 611233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 612233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 613233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 614233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = baseIndex; 6150076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng bool SeenDefUse = false; 616b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 617bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen while (mi != E) { 6181d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen if (mi->killsRegister(interval.reg, tri_)) { 6191d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen DEBUG(dbgs() << " killed"); 6201d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen end = baseIndex.getDefIndex(); 6211d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen SeenDefUse = true; 6221d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen break; 6231015ba7018c87f48cc7bb45a564eb4a27241e76aEvan Cheng } else if (mi->definesRegister(interval.reg, tri_)) { 6241d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // Another instruction redefines the register before it is ever read. 6251d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // Then the register is essentially dead at the instruction that defines 6261d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // it. Hence its interval is: 6271d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // [defSlot(def), defSlot(def)+1) 6281d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen DEBUG(dbgs() << " dead"); 6291d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen end = start.getStoreIndex(); 6301d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen SeenDefUse = true; 6311d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen break; 632bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen } 6331d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen 6344507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng while (++mi != E && mi->isDebugValue()) 6354507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // Skip over DBG_VALUE. 6364507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng ; 6374507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi != E) 638233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 639b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 640b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 64175611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 6420076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng if (!SeenDefUse) { 643292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng if (isAlias) { 6448a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 645233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = MIIdx.getStoreIndex(); 646292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } else { 6478a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " live through"); 648292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng end = baseIndex; 649292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } 65024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 65124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 6526e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames SlotIndex defIdx = getMBBStartIdx(MBB); 6536e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames assert(getInstructionFromIndex(defIdx) == 0 && 6546e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames "PHI def index points at actual instruction."); 65510382fb71d8306f320ecbeb7049d25354c0e5457Lang Hames VNInfo *vni = 6566e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames interval.getNextValue(defIdx, 0, VNInfoAllocator); 657d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames vni->setIsPHIDef(true); 658d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames LiveRange LR(start, end, vni); 6593de23e6f6cf337451a0934159da494d645b93133Jakob Stoklund Olesen 6609b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 6618a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << '\n'); 662b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 663b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 664ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 6654d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 66608cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 667ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 6681b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesenvoid LiveIntervals::computeIntervals() { 6698a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n" 6708e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << "********** Function: " 6718e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'); 672d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 673d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng SmallVector<unsigned, 8> UndefUses; 674428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 675428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 676428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 67700a99a35840451a291eb61a192a750908a4073aeEvan Cheng if (MBB->empty()) 67800a99a35840451a291eb61a192a750908a4073aeEvan Cheng continue; 67900a99a35840451a291eb61a192a750908a4073aeEvan Cheng 680134eb73fc35e6ead3cfd3ed5024d0d7efa507441Owen Anderson // Track the index of the current machine instr. 681233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIndex = getMBBStartIdx(MBB); 682ad98f795d0dba3db721139a8a74a98acdce0ff60Bob Wilson DEBUG(dbgs() << "BB#" << MBB->getNumber() 683ad98f795d0dba3db721139a8a74a98acdce0ff60Bob Wilson << ":\t\t# derived from " << MBB->getName() << "\n"); 6841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 685cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 68681bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), 687cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 688cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 689cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Multiple live-ins can alias the same register. 6906f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 691cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!hasInterval(*AS)) 692cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 693cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman true); 694dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 6951b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 69699500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson // Skip over empty initial indices. 697233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(MIIndex) == 0) 698233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 6991b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 7001caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 7011caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen MI != miEnd; ++MI) { 7028a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << MIIndex << "\t" << *MI); 703518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isDebugValue()) 7041caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen continue; 7051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 706438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 707428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 708428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 709d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (!MO.isReg() || !MO.getReg()) 710d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng continue; 711d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 7121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 713d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (MO.isDef()) 714ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleRegisterDef(MBB, MI, MIIndex, MO, i); 715d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng else if (MO.isUndef()) 716d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng UndefUses.push_back(MO.getReg()); 7171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 7181b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 719233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Move to the next instr slot. 720233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 721ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 7221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 723d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 724d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // Create empty intervals for registers defined by implicit_def's (except 725d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // for those implicit_def that define values which are liveout of their 726d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // blocks. 727d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { 728d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng unsigned UndefReg = UndefUses[i]; 729d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng (void)getOrCreateInterval(UndefReg); 730d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng } 731ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 732b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 73303857b29d8271a23943254579e6cf7b7df4b1bd3Owen AndersonLiveInterval* LiveIntervals::createInterval(unsigned reg) { 7340a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 73503857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson return new LiveInterval(reg, Weight); 7369a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 737f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 7380a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// dupInterval - Duplicate a live interval. The caller is responsible for 7390a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// managing the allocated memory. 7400a1fcce09230e9b4bd30a8f07447aa075dce7470Evan ChengLiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 7410a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng LiveInterval *NewLI = createInterval(li->reg); 74290f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng NewLI->Copy(*li, mri_, getVNInfoAllocator()); 7430a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng return NewLI; 7440a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng} 7450a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng 74611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen/// shrinkToUses - After removing some uses of a register, shrink its live 74711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen/// range to just the remaining uses. This method does not compute reaching 74811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen/// defs for new uses, and it doesn't remove dead defs. 7496a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesenbool LiveIntervals::shrinkToUses(LiveInterval *li, 7500d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen SmallVectorImpl<MachineInstr*> *dead) { 75111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen DEBUG(dbgs() << "Shrink: " << *li << '\n'); 75211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(li->reg) 75311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen && "Can't only shrink physical registers"); 75411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Find all the values used, including PHI kills. 75511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList; 75611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 75711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Visit all instructions reading li->reg. 75811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li->reg); 75911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen MachineInstr *UseMI = I.skipInstruction();) { 76011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg)) 76111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 76211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SlotIndex Idx = getInstructionIndex(UseMI).getUseIndex(); 76311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNInfo *VNI = li->getVNInfoAt(Idx); 7649ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen if (!VNI) { 7659ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen // This shouldn't happen: readsVirtualRegister returns true, but there is 7669ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen // no live value. It is likely caused by a target getting <undef> flags 7679ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen // wrong. 7689ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen DEBUG(dbgs() << Idx << '\t' << *UseMI 7699ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen << "Warning: Instr claims to read non-existent value in " 7709ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen << *li << '\n'); 7719ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen continue; 7729ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen } 77311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (VNI->def == Idx) { 77411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Special case: An early-clobber tied operand reads and writes the 77511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // register one slot early. 77611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen Idx = Idx.getPrevSlot(); 77711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNI = li->getVNInfoAt(Idx); 77811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(VNI && "Early-clobber tied value not available"); 77911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 78011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen WorkList.push_back(std::make_pair(Idx, VNI)); 78111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 78211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 78311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Create a new live interval with only minimal live segments per def. 78411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen LiveInterval NewLI(li->reg, 0); 78511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 78611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen I != E; ++I) { 78711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNInfo *VNI = *I; 78811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (VNI->isUnused()) 78911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 79011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen NewLI.addRange(LiveRange(VNI->def, VNI->def.getNextSlot(), VNI)); 791a9d5c2715b5e8e0be613d8d31e76c35a5bfff07dJakob Stoklund Olesen 792a9d5c2715b5e8e0be613d8d31e76c35a5bfff07dJakob Stoklund Olesen // A use tied to an early-clobber def ends at the load slot and isn't caught 793a9d5c2715b5e8e0be613d8d31e76c35a5bfff07dJakob Stoklund Olesen // above. Catch it here instead. This probably only ever happens for inline 794a9d5c2715b5e8e0be613d8d31e76c35a5bfff07dJakob Stoklund Olesen // assembly. 795a9d5c2715b5e8e0be613d8d31e76c35a5bfff07dJakob Stoklund Olesen if (VNI->def.isUse()) 796a9d5c2715b5e8e0be613d8d31e76c35a5bfff07dJakob Stoklund Olesen if (VNInfo *UVNI = li->getVNInfoAt(VNI->def.getLoadIndex())) 797a9d5c2715b5e8e0be613d8d31e76c35a5bfff07dJakob Stoklund Olesen WorkList.push_back(std::make_pair(VNI->def.getLoadIndex(), UVNI)); 79811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 79911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 800e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // Keep track of the PHIs that are in use. 801e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen SmallPtrSet<VNInfo*, 8> UsedPHIs; 802e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen 80311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Extend intervals to reach all uses in WorkList. 80411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen while (!WorkList.empty()) { 80511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SlotIndex Idx = WorkList.back().first; 80611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNInfo *VNI = WorkList.back().second; 80711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen WorkList.pop_back(); 80811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen const MachineBasicBlock *MBB = getMBBFromIndex(Idx); 80911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SlotIndex BlockStart = getMBBStartIdx(MBB); 810e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen 811e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // Extend the live range for VNI to be live at Idx. 812e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) { 8134b11a70f7a63dc4c051a96a90ed6687eb0595cdaNick Lewycky (void)ExtVNI; 814e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen assert(ExtVNI == VNI && "Unexpected existing value number"); 815e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // Is this a PHIDef we haven't seen before? 816c29d9b3495a2d87af524ad5c4b62f46c4265d828Jakob Stoklund Olesen if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI)) 817e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen continue; 818e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // The PHI is live, make sure the predecessors are live-out. 819e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 820e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 821e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot(); 822e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen VNInfo *PVNI = li->getVNInfoAt(Stop); 823e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // A predecessor is not required to have a live-out value for a PHI. 824e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen if (PVNI) { 825e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen assert(PVNI->hasPHIKill() && "Missing hasPHIKill flag"); 826e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen WorkList.push_back(std::make_pair(Stop, PVNI)); 82711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 82811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 82911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 83011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 83111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 83211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // VNI is live-in to MBB. 83311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); 83411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen NewLI.addRange(LiveRange(BlockStart, Idx.getNextSlot(), VNI)); 83511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 83611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Make sure VNI is live-out from the predecessors. 83711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 83811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 83911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot(); 84011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(li->getVNInfoAt(Stop) == VNI && "Wrong value out of predecessor"); 84111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen WorkList.push_back(std::make_pair(Stop, VNI)); 84211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 84311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 84411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 84511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Handle dead values. 8466a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen bool CanSeparate = false; 84711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 84811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen I != E; ++I) { 84911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNInfo *VNI = *I; 85011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (VNI->isUnused()) 85111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 85211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def); 85311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(LII != NewLI.end() && "Missing live range for PHI"); 85411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (LII->end != VNI->def.getNextSlot()) 85511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 856a4d347357ce04d9101130dca0df33cb62ea35a2fJakob Stoklund Olesen if (VNI->isPHIDef()) { 85711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // This is a dead PHI. Remove it. 85811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNI->setIsUnused(true); 85911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen NewLI.removeRange(*LII); 8606a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); 8616a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen CanSeparate = true; 86211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } else { 86311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // This is a dead def. Make sure the instruction knows. 86411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen MachineInstr *MI = getInstructionFromIndex(VNI->def); 86511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(MI && "No instruction defining live value"); 86611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen MI->addRegisterDead(li->reg, tri_); 8670d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen if (dead && MI->allDefsAreDead()) { 868c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI); 8690d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen dead->push_back(MI); 8700d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen } 87111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 87211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 87311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 87411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Move the trimmed ranges back. 87511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen li->ranges.swap(NewLI.ranges); 876c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen DEBUG(dbgs() << "Shrunk: " << *li << '\n'); 8776a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen return CanSeparate; 87811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen} 87911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 88011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 881f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 882f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 883f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 884f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 885cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund OlesenMachineBasicBlock::iterator 886cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund OlesenLiveIntervals::getLastSplitPoint(const LiveInterval &li, 887f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineBasicBlock *mbb) const { 888cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen const MachineBasicBlock *lpad = mbb->getLandingPadSuccessor(); 889cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen 890cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen // If li is not live into a landing pad, we can insert spill code before the 891cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen // first terminator. 892cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen if (!lpad || !isLiveInToMBB(li, lpad)) 893cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen return mbb->getFirstTerminator(); 894cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen 895cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen // When there is a landing pad, spill code must go before the call instruction 896cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen // that can throw. 897cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen MachineBasicBlock::iterator I = mbb->end(), B = mbb->begin(); 898cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen while (I != B) { 899cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen --I; 900cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen if (I->getDesc().isCall()) 901cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen return I; 902cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen } 90345e53975f81164d6e5e6322e83dd19030b7d3c88Jakob Stoklund Olesen // The block contains no calls that can throw, so use the first terminator. 904cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen return mbb->getFirstTerminator(); 905cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen} 906cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen 9078a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesenvoid LiveIntervals::addKillFlags() { 9088a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen for (iterator I = begin(), E = end(); I != E; ++I) { 9098a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen unsigned Reg = I->first; 9108a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) 9118a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 9128a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen if (mri_->reg_nodbg_empty(Reg)) 9138a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 9148a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen LiveInterval *LI = I->second; 9158a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen 9168a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen // Every instruction that kills Reg corresponds to a live range end point. 9178a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE; 9188a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen ++RI) { 9198a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen // A LOAD index indicates an MBB edge. 9208a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen if (RI->end.isLoad()) 9218a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 9228a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen MachineInstr *MI = getInstructionFromIndex(RI->end); 9238a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen if (!MI) 9248a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 9258a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen MI->addRegisterKilled(Reg, NULL); 9268a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen } 9278a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen } 9288a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen} 9298a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen 930d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 931d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 932d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 933d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 934d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 935d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 936d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 937d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 938d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || !MO.isUse()) 939d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 940d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 941d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 942d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 9431b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 9441873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner if (TargetRegisterInfo::isPhysicalRegister(Reg) && 9451873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner !allocatableRegs_[Reg]) 9461873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner continue; 947d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // FIXME: For now, only remat MI with at most one register operand. 948d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng assert(!RegOp && 949d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng "Can't rematerialize instruction with multiple register operand!"); 950d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 9516d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#ifndef NDEBUG 952d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng break; 9536d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#endif 954d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 955d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 956d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 957d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 958d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 959d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 960d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 961233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx) const { 96231cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen VNInfo *UValNo = li.getVNInfoAt(UseIdx); 96331cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI)); 964d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 965d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 966f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 967f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 968f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trickbool 969f4baeaf8485f01beda46d29fd55753199dc68070Andrew TrickLiveIntervals::isReMaterializable(const LiveInterval &li, 970f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick const VNInfo *ValNo, MachineInstr *MI, 97138f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen const SmallVectorImpl<LiveInterval*> *SpillIs, 972f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick bool &isLoad) { 973f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 974f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 975f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 976a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman if (!tii_->isTriviallyReMaterializable(MI, aa_)) 977a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman return false; 978f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 979a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // Target-specific code can mark an instruction as being rematerializable 980a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // if it has one virtual reg use, though it had better be something like 981a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // a PIC base register which is likely to be live everywhere. 9826d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = getReMatImplicitUse(li, MI); 9836d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse) { 9846d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const LiveInterval &ImpLi = getInterval(ImpUse); 98528a1e486907104b85c5787345914917d74f0cf77Evan Cheng for (MachineRegisterInfo::use_nodbg_iterator 98628a1e486907104b85c5787345914917d74f0cf77Evan Cheng ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end(); 98728a1e486907104b85c5787345914917d74f0cf77Evan Cheng ri != re; ++ri) { 9886d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineInstr *UseMI = &*ri; 989233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx = getInstructionIndex(UseMI); 99031cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen if (li.getVNInfoAt(UseIdx) != ValNo) 9916d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman continue; 9926d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 9936d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 9946d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 995dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng 996dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // If a register operand of the re-materialized instruction is going to 997dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // be spilled next, then it's not legal to re-materialize this instruction. 99838f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen if (SpillIs) 99938f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen for (unsigned i = 0, e = SpillIs->size(); i != e; ++i) 100038f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen if (ImpUse == (*SpillIs)[i]->reg) 100138f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen return false; 10026d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 10036d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return true; 10045ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 10055ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 100606587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 100706587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng/// val# of the specified interval is re-materializable. 100806587497dc1c39516f24784a2ac1d9323faae0a5Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 100906587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng const VNInfo *ValNo, MachineInstr *MI) { 101006587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng bool Dummy2; 101138f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen return isReMaterializable(li, ValNo, MI, 0, Dummy2); 101206587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng} 101306587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng 10145ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 10155ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 1016f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trickbool 1017f4baeaf8485f01beda46d29fd55753199dc68070Andrew TrickLiveIntervals::isReMaterializable(const LiveInterval &li, 101838f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen const SmallVectorImpl<LiveInterval*> *SpillIs, 1019f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick bool &isLoad) { 10205ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 10215ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 10225ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 10235ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 1024857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->isUnused()) 10255ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 10265ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 1027857c4e01f85601cf2084adb860616256ee47c177Lang Hames MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 10286e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames if (!ReMatDefMI) 10296e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames return false; 10305ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 1031d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 1032dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 1033f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 10345ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 1035f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1036f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 1037f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1038f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 103979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// FilterFoldedOps - Filter out two-address use operands. Return 104079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// true if it finds any issue with the operands that ought to prevent 104179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// folding. 104279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengstatic bool FilterFoldedOps(MachineInstr *MI, 104379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 104479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned &MRInfo, 104579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &FoldOps) { 104679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MRInfo = 0; 1047aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 1048aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned OpIdx = Ops[i]; 1049d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(OpIdx); 1050aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // FIXME: fold subreg use. 1051d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.getSubReg()) 105279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 1053d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.isDef()) 1054aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isMod; 1055aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 1056aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Filter out two-address use operand(s). 1057a24752ff43dc1ad8c18c5d9e78549c45f62b980eEvan Cheng if (MI->isRegTiedToDefOperand(OpIdx)) { 1058aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo = VirtRegMap::isModRef; 1059aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng continue; 1060aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 1061aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isRef; 1062aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 1063aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoldOps.push_back(OpIdx); 1064e62f97c094dba44e4c259d20135167fa91912eeaEvan Cheng } 106579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 106679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng} 10671b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 106879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 106979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 107079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// slot / to reg or any rematerialized load into ith operand of specified 107179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// MI. If it is successul, MI is updated with the newly created MI and 107279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// returns true. 107379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengbool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 107479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng VirtRegMap &vrm, MachineInstr *DefMI, 1075233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex InstrIdx, 107679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 107779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng bool isSS, int Slot, unsigned Reg) { 107879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // If it is an implicit def instruction, just delete it. 1079518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isImplicitDef()) { 108079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng RemoveMachineInstrFromMaps(MI); 108179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 108279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MI->eraseFromParent(); 108379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng ++numFolds; 108479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 108579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng } 108679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 108779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 108879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 108979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 109079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> FoldOps; 109179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 109279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 1093cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1094427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // The only time it's safe to fold into a two address instruction is when 1095427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // it's folding reload and spill from / into a spill stack slot. 1096427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng if (DefMI && (MRInfo & VirtRegMap::isMod)) 1097249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng return false; 1098249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng 1099e05442d50806e2850eae1571958816028093df85Jakob Stoklund Olesen MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(MI, FoldOps, Slot) 1100e05442d50806e2850eae1571958816028093df85Jakob Stoklund Olesen : tii_->foldMemoryOperand(MI, FoldOps, DefMI); 1101f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (fmi) { 1102d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng // Remember this instruction uses the spill slot. 1103d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng if (isSS) vrm.addSpillSlotUse(Slot, fmi); 1104d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng 1105f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Attempt to fold the memory reference into the instruction. If 1106f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // we can do this, we don't need to insert spill code. 11078480293f41c11c22762164449e41cd3adb0dd7d8Evan Cheng if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 1108aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 110981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.transferSpillPts(MI, fmi); 11100cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.transferRestorePts(MI, fmi); 1111c1f53c742620dd4f2460685477303002bba8a8d8Evan Cheng vrm.transferEmergencySpills(MI, fmi); 1112233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames ReplaceMachineInstrInMaps(MI, fmi); 1113e05442d50806e2850eae1571958816028093df85Jakob Stoklund Olesen MI->eraseFromParent(); 1114e05442d50806e2850eae1571958816028093df85Jakob Stoklund Olesen MI = fmi; 11150cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numFolds; 1116f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 1117f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1118f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 1119f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1120f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1121018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// canFoldMemoryOperand - Returns true if the specified load / store 1122018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// folding is possible. 1123018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 112479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 11253c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng bool ReMat) const { 112679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 112779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 112879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 1129018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng SmallVector<unsigned, 2> FoldOps; 113079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 113179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 1132018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 11333c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng // It's only legal to remat for a use, not a def. 11343c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng if (ReMat && (MRInfo & VirtRegMap::isMod)) 113579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 1136018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1137d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return tii_->canFoldMemoryOperand(MI, FoldOps); 1138d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1139d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 114081a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 1141233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveInterval::Ranges::const_iterator itr = li.ranges.begin(); 1142233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 1143233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end); 1144233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 1145233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (mbb == 0) 1146233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return false; 1147233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 1148233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames for (++itr; itr != li.ranges.end(); ++itr) { 1149233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineBasicBlock *mbb2 = 1150233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames indexes_->getMBBCoveringRange(itr->start, itr->end); 1151233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 1152233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (mbb2 != mbb) 115381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 115481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1155233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 115681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return true; 115781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 115881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1159d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 1160d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// interval on to-be re-materialized operands of MI) with new register. 1161d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengvoid LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 1162d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI, unsigned NewVReg, 1163d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm) { 1164d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // There is an implicit use. That means one of the other operand is 1165d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // being remat'ed and the remat'ed instruction has li.reg as an 1166d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // use operand. Make sure we rewrite that as well. 1167d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1168d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 1169d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg()) 1170d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1171d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 1172c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1173d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1174d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!vrm.isReMaterialized(Reg)) 1175d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1176d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 11776130f66eaae89f8878590796977678afa8448926Evan Cheng MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 11786130f66eaae89f8878590796977678afa8448926Evan Cheng if (UseMO) 11796130f66eaae89f8878590796977678afa8448926Evan Cheng UseMO->setReg(NewVReg); 1180d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1181d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1182d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 1183f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 1184f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 1185018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals:: 1186d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan ChengrewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 11871b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen bool TrySplit, SlotIndex index, SlotIndex end, 11888651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineInstr *MI, 118981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1190f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1191f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1192d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1193f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1194f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 119522f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 1196313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 1197289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> &MBBVRegsMap, 1198c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1199018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool CanFold = false; 1200f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RestartInstruction: 1201f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1202f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineOperand& mop = MI->getOperand(i); 1203d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!mop.isReg()) 1204f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1205f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Reg = mop.getReg(); 1206c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1207f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1208f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (Reg != li.reg) 1209f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1210f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1211f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool TryFold = !DefIsReMat; 1212cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng bool FoldSS = true; // Default behavior unless it's a remat. 1213f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int FoldSlot = Slot; 1214f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIsReMat) { 1215f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If this is the rematerializable definition MI itself and 1216f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // all of its uses are rematerialized, simply delete it. 121781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MI == ReMatOrigDefMI && CanDelete) { 1218bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen DEBUG(dbgs() << "\t\t\t\tErasing re-materializable def: " 121928a1e486907104b85c5787345914917d74f0cf77Evan Cheng << *MI << '\n'); 1220f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RemoveMachineInstrFromMaps(MI); 1221cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng vrm.RemoveMachineInstrFromMaps(MI); 1222f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI->eraseFromParent(); 1223f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng break; 1224f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1225f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1226f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If def for this use can't be rematerialized, then try folding. 12270cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If def is rematerializable and it's a load, also try folding. 1228cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 1229f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (isLoad) { 1230f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Try fold loads (from stack slot, constant pool, etc.) into uses. 1231f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSS = isLoadSS; 1232f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSlot = LdSlot; 1233f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1234f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1235f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1236f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Scan all of the operands of this instruction rewriting operands 1237f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // to use NewVReg instead of li.reg as appropriate. We do this for 1238f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // two reasons: 1239f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1240f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1. If the instr reads the same spilled vreg multiple times, we 1241f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // want to reuse the NewVReg. 1242f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 2. If the instr is a two-addr instruction, we are required to 1243f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // keep the src/dst regs pinned. 1244f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1245f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Keep track of whether we replace a use and/or def so that we can 12461b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // create the spill interval with the appropriate range. 1247aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 1248ead06be02fe6b9a2bf6fbe04237c1276ed0cdb5cJakob Stoklund Olesen tie(HasUse, HasDef) = MI->readsWritesVirtualRegister(Reg, &Ops); 1249f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 125026b86a0b5676253040dc206b437536a24306fb76David Greene // Create a new virtual register for the spill interval. 125126b86a0b5676253040dc206b437536a24306fb76David Greene // Create the new register now so we can map the fold instruction 125226b86a0b5676253040dc206b437536a24306fb76David Greene // to the new register so when it is unfolded we get the correct 125326b86a0b5676253040dc206b437536a24306fb76David Greene // answer. 125426b86a0b5676253040dc206b437536a24306fb76David Greene bool CreatedNewVReg = false; 125526b86a0b5676253040dc206b437536a24306fb76David Greene if (NewVReg == 0) { 125626b86a0b5676253040dc206b437536a24306fb76David Greene NewVReg = mri_->createVirtualRegister(rc); 125726b86a0b5676253040dc206b437536a24306fb76David Greene vrm.grow(); 125826b86a0b5676253040dc206b437536a24306fb76David Greene CreatedNewVReg = true; 1259ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen 1260ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen // The new virtual register should get the same allocation hints as the 1261ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen // old one. 1262ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(Reg); 1263ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen if (Hint.first || Hint.second) 1264ce7a663140e6e67cf5ef7091e076e8541300c15aJakob Stoklund Olesen mri_->setRegAllocationHint(NewVReg, Hint.first, Hint.second); 126526b86a0b5676253040dc206b437536a24306fb76David Greene } 126626b86a0b5676253040dc206b437536a24306fb76David Greene 12679c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!TryFold) 12689c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanFold = false; 12699c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng else { 1270018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Do not fold load / store here if we are splitting. We'll find an 1271018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // optimal point to insert a load / store later. 1272018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (!TrySplit) { 1273018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 127426b86a0b5676253040dc206b437536a24306fb76David Greene Ops, FoldSS, FoldSlot, NewVReg)) { 1275018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Folding the load/store can completely change the instruction in 1276018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // unpredictable ways, rescan it from the beginning. 127726b86a0b5676253040dc206b437536a24306fb76David Greene 127826b86a0b5676253040dc206b437536a24306fb76David Greene if (FoldSS) { 127926b86a0b5676253040dc206b437536a24306fb76David Greene // We need to give the new vreg the same stack slot as the 128026b86a0b5676253040dc206b437536a24306fb76David Greene // spilled interval. 128126b86a0b5676253040dc206b437536a24306fb76David Greene vrm.assignVirt2StackSlot(NewVReg, FoldSlot); 128226b86a0b5676253040dc206b437536a24306fb76David Greene } 128326b86a0b5676253040dc206b437536a24306fb76David Greene 1284018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasUse = false; 1285018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasDef = false; 1286018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng CanFold = false; 1287c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng if (isNotInMIMap(MI)) 12887e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng break; 1289018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng goto RestartInstruction; 1290018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1291018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } else { 12929c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // We'll try to fold it later if it's profitable. 12933c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 1294018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 12959c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng } 1296cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1297cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mop.setReg(NewVReg); 1298d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mop.isImplicit()) 1299d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1300cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1301cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Reuse NewVReg for other reads. 13027c2e4a8715836a44e82ac6c7370826519ccdfddbJakob Stoklund Olesen bool HasEarlyClobber = false; 1303d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 1304d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &mopj = MI->getOperand(Ops[j]); 1305d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng mopj.setReg(NewVReg); 1306d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mopj.isImplicit()) 1307d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 13087c2e4a8715836a44e82ac6c7370826519ccdfddbJakob Stoklund Olesen if (mopj.isEarlyClobber()) 13097c2e4a8715836a44e82ac6c7370826519ccdfddbJakob Stoklund Olesen HasEarlyClobber = true; 1310d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 13111b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 131281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 131381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (DefIsReMat) { 1314378445303b10b092a898a75131141a8259cff50bEvan Cheng vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI); 1315d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 131681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each valnum may have its own remat id. 1317d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 131881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 1319d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 132081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 132181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!CanDelete || (HasUse && HasDef)) { 132281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a two-addr instruction then its use operands are 132381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // rematerializable but its def is not. It should be assigned a 132481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // stack slot. 132581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 132681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1327f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1328f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1329f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1330cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng } else if (HasUse && HasDef && 1331cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1332cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // If this interval hasn't been assigned a stack slot (because earlier 1333cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // def is a deleted remat def), do it now. 1334cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng assert(Slot != VirtRegMap::NO_STACK_SLOT); 1335cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1336f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1337f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1338313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Add the 1339313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // register as an implicit use on the use MI. 1340313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (DefIsReMat && ImpUse) 1341313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1342313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 13435b69ebac857104770b1a751bf7a463fda4330a62Evan Cheng // Create a new register interval for this spill / remat. 1344f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 134581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 134681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng NewLIs.push_back(&nI); 13471953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 134881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (TrySplit) 134981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(NewVReg, li.reg); 135081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1351f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1352f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasUse) { 135381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 1354233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange LR(index.getLoadIndex(), index.getDefIndex(), 13556e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames nI.getNextValue(SlotIndex(), 0, VNInfoAllocator)); 13568a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 135781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 135881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 135981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Extend the split live interval to this def / use. 1360233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex End = index.getDefIndex(); 136181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 136281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getValNumInfo(nI.getNumValNums()-1)); 13638a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 136481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 136581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1366f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1367f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasDef) { 13687c2e4a8715836a44e82ac6c7370826519ccdfddbJakob Stoklund Olesen // An early clobber starts at the use slot, except for an early clobber 13697c2e4a8715836a44e82ac6c7370826519ccdfddbJakob Stoklund Olesen // tied to a use operand (yes, that is a thing). 13707c2e4a8715836a44e82ac6c7370826519ccdfddbJakob Stoklund Olesen LiveRange LR(HasEarlyClobber && !HasUse ? 13717c2e4a8715836a44e82ac6c7370826519ccdfddbJakob Stoklund Olesen index.getUseIndex() : index.getDefIndex(), 13727c2e4a8715836a44e82ac6c7370826519ccdfddbJakob Stoklund Olesen index.getStoreIndex(), 13736e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames nI.getNextValue(SlotIndex(), 0, VNInfoAllocator)); 13748a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 1375f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.addRange(LR); 1376f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 137781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 13788e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 13798a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\t\t\tAdded new interval: "; 13808a34229dcf484739119857988772572ef0cad9f2David Greene nI.print(dbgs(), tri_); 13818a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << '\n'; 13828e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 1383f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1384018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng return CanFold; 1385f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 138681a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 13870cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng const VNInfo *VNI, 13888651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineBasicBlock *MBB, 1389233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Idx) const { 139015a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen return li.killedInRange(Idx.getNextSlot(), getMBBEndIdx(MBB)); 139181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 139281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1393063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// RewriteInfo - Keep track of machine instrs that will be rewritten 1394063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// during spilling. 1395844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 1396844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfo { 1397233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index; 1398844731a7f1909f55935e3514c9e713a62d67662eDan Gohman MachineInstr *MI; 1399ead06be02fe6b9a2bf6fbe04237c1276ed0cdb5cJakob Stoklund Olesen RewriteInfo(SlotIndex i, MachineInstr *mi) : Index(i), MI(mi) {} 1400844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1401844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1402844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfoCompare { 1403844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1404844731a7f1909f55935e3514c9e713a62d67662eDan Gohman return LHS.Index < RHS.Index; 1405844731a7f1909f55935e3514c9e713a62d67662eDan Gohman } 1406844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1407844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} 1408063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1409f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengvoid LiveIntervals:: 141081a038218171860ee4c382849c647d3dc841fe8bEvan ChengrewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1411f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval::Ranges::const_iterator &I, 141281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1413f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1414f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1415d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1416f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1417f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 141822f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 141981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &SpillMBBs, 1420289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes, 14210cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector &RestoreMBBs, 1422289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes, 1423289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> &MBBVRegsMap, 1424c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1425018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool AllCanFold = true; 142681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned NewVReg = 0; 1427233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = I->start.getBaseIndex(); 1428233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); 1429f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1430063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // First collect all the def / use in this live range that will be rewritten. 14317e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Make sure they are sorted according to instruction index. 1432063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::vector<RewriteInfo> RewriteMIs; 1433d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1434d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->reg_end(); ri != re; ) { 1435419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1436063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineOperand &O = ri.getOperand(); 1437063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++ri; 1438bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen if (MI->isDebugValue()) { 1439962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng // Modify DBG_VALUE now that the value is in a spill slot. 14406691a8935c9f2e049ff5eed45ba2894f60108909Evan Cheng if (Slot != VirtRegMap::MAX_STACK_SLOT || isLoadSS) { 14416fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng uint64_t Offset = MI->getOperand(1).getImm(); 14426fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng const MDNode *MDPtr = MI->getOperand(2).getMetadata(); 14436fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng DebugLoc DL = MI->getDebugLoc(); 14446691a8935c9f2e049ff5eed45ba2894f60108909Evan Cheng int FI = isLoadSS ? LdSlot : (int)Slot; 14456691a8935c9f2e049ff5eed45ba2894f60108909Evan Cheng if (MachineInstr *NewDV = tii_->emitFrameIndexDebugValue(*mf_, FI, 14466fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng Offset, MDPtr, DL)) { 14476fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI); 14486fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng ReplaceMachineInstrInMaps(MI, NewDV); 14496fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 14506fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng MBB->insert(MBB->erase(MI), NewDV); 14516fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng continue; 14526fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng } 1453962021bc7f6721c20c7dfe8ca809e2d98b1c554aEvan Cheng } 14546fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng 14556fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); 14566fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng RemoveMachineInstrFromMaps(MI); 14576fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 14586fa7636e614cbf0a19d374e169791a774281e8d3Evan Cheng MI->eraseFromParent(); 1459bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen continue; 1460bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen } 146163e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen assert(!(O.isImplicit() && O.isUse()) && 146263e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen "Spilling register that's used as implicit use?"); 1463233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = getInstructionIndex(MI); 1464063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng if (index < start || index >= end) 1465063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng continue; 1466d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 1467d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (O.isUndef()) 146879a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // Must be defined by an implicit def. It should not be spilled. Note, 146979a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // this is for correctness reason. e.g. 147079a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 8 %reg1024<def> = IMPLICIT_DEF 147179a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 147279a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // The live range [12, 14) are not part of the r1024 live interval since 147379a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // it's defined by an implicit def. It will not conflicts with live 147479a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // interval of r1025. Now suppose both registers are spilled, you can 1475b9890ae3c35ad7d8e49261650d5b98f49f97a705Evan Cheng // easily see a situation where both registers are reloaded before 147679a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // the INSERT_SUBREG and both target registers that would overlap. 147779a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng continue; 1478ead06be02fe6b9a2bf6fbe04237c1276ed0cdb5cJakob Stoklund Olesen RewriteMIs.push_back(RewriteInfo(index, MI)); 1479063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 1480063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1481063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1482313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 1483063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // Now rewrite the defs and uses. 1484063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 1485063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteInfo &rwi = RewriteMIs[i]; 1486063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1487233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = rwi.Index; 1488063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineInstr *MI = rwi.MI; 1489063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // If MI def and/or use the same register multiple times, then there 1490063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // are multiple entries. 1491063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng while (i != e && RewriteMIs[i].MI == MI) { 1492063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng assert(RewriteMIs[i].Index == index); 1493063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1494063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 149581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1496313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 14970a891ed7d5875a9ccdb93b4472b0f43947d8289bEvan Cheng if (ImpUse && MI != ReMatDefMI) { 1498e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // Re-matting an instruction with virtual register use. Prevent interval 1499e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // from being spilled. 1500e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen getInterval(ImpUse).markNotSpillable(); 1501313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng } 1502313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1503063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned MBBId = MBB->getNumber(); 1504018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng unsigned ThisVReg = 0; 150570306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (TrySplit) { 1506289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId); 15071953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NVI != MBBVRegsMap.end()) { 1508018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = NVI->second; 15091953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // One common case: 15101953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // x = use 15111953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 15121953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 15131953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // def = ... 15141953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // = use 15151953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // It's better to start a new interval to avoid artifically 15161953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // extend the new interval. 1517ead06be02fe6b9a2bf6fbe04237c1276ed0cdb5cJakob Stoklund Olesen if (MI->readsWritesVirtualRegister(li.reg) == 1518ead06be02fe6b9a2bf6fbe04237c1276ed0cdb5cJakob Stoklund Olesen std::make_pair(false,true)) { 15191953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.erase(MBB->getNumber()); 1520018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = 0; 15211953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 15221953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 1523cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng } 1524018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1525018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool IsNew = ThisVReg == 0; 1526018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (IsNew) { 1527018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // This ends the previous live interval. If all of its def / use 1528018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // can be folded, give it a low spill weight. 1529018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1530018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1531018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1532018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1533018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold = true; 1534018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1535018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng NewVReg = ThisVReg; 1536018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 153781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasDef = false; 153881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasUse = false; 1539d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 15409c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng index, end, MI, ReMatOrigDefMI, ReMatDefMI, 15419c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 15429c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 1543c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); 154481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!HasDef && !HasUse) 154581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 154681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1547018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold &= CanFold; 1548018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 154981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Update weight of spill interval. 155081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 155170306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (!TrySplit) { 155281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // The spill weight is now infinity as it cannot be spilled again. 1553e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen nI.markNotSpillable(); 15540cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 15550cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 15560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 15570cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Keep track of the last def and first use in each MBB. 15580cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasDef) { 15590cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MI != ReMatOrigDefMI || !CanDelete) { 15600cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool HasKill = false; 15610cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasUse) 1562233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, index.getDefIndex()); 15630cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else { 15641953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // If this is a two-address code, then this index starts a new VNInfo. 1565233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const VNInfo *VNI = li.findDefinedVNInfoForRegInt(index.getDefIndex()); 15660cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VNI) 1567233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, index.getDefIndex()); 156881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1569289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 1570e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.find(MBBId); 15710cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasKill) { 15721953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII == SpillIdxes.end()) { 15731953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> S; 15741953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng S.push_back(SRInfo(index, NewVReg, true)); 15751953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SpillIdxes.insert(std::make_pair(MBBId, S)); 15761953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if (SII->second.back().vreg != NewVReg) { 15771953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.push_back(SRInfo(index, NewVReg, true)); 15788651125d2885f74546b6e2a556082111d5b75da3Lang Hames } else if (index > SII->second.back().index) { 15790cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If there is an earlier def and this is a two-address 15800cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // instruction, then it's not possible to fold the store (which 15810cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // would also fold the load). 15821953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SRInfo &Info = SII->second.back(); 15831953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.index = index; 15841953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.canFold = !HasUse; 158581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 15860cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs.set(MBBId); 1587e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } else if (SII != SpillIdxes.end() && 1588e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.back().vreg == NewVReg && 15898651125d2885f74546b6e2a556082111d5b75da3Lang Hames index > SII->second.back().index) { 1590e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // There is an earlier def that's not killed (must be two-address). 1591e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // The spill is no longer needed. 1592e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.pop_back(); 1593e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng if (SII->second.empty()) { 1594e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.erase(MBBId); 1595e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillMBBs.reset(MBBId); 1596e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } 159781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 159881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 15990cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 160081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 16010cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasUse) { 1602289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 16030cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillIdxes.find(MBBId); 16041953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII != SpillIdxes.end() && 16051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().vreg == NewVReg && 16068651125d2885f74546b6e2a556082111d5b75da3Lang Hames index > SII->second.back().index) 16070cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Use(s) following the last def, it's not safe to fold the spill. 16081953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().canFold = false; 1609289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator RII = 16100cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreIdxes.find(MBBId); 16111953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 16120cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If we are splitting live intervals, only fold if it's the first 16130cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // use and there isn't another use later in the MBB. 16141953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.back().canFold = false; 16150cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else if (IsNew) { 16160cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Only need a reload if there isn't an earlier def / use. 16171953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII == RestoreIdxes.end()) { 16181953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> Infos; 16191953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Infos.push_back(SRInfo(index, NewVReg, true)); 16201953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 16211953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else { 16221953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.push_back(SRInfo(index, NewVReg, true)); 16231953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 16240cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreMBBs.set(MBBId); 16250cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 162681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 16270cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 16280cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Update spill weight. 162922f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 1630c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1631f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1632018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1633018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1634018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // If all of its def / use can be folded, give it a low spill weight. 1635018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1636018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1637018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1638f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1639f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1640233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesbool LiveIntervals::alsoFoldARestore(int Id, SlotIndex index, 16418651125d2885f74546b6e2a556082111d5b75da3Lang Hames unsigned vr, BitVector &RestoreMBBs, 1642289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 16431953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 16441953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 16451953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 16461953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 16471953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && 16481953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].vreg == vr && 16491953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].canFold) 16501953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return true; 16511953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 16521953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 16531953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1654233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveIntervals::eraseRestoreInfo(int Id, SlotIndex index, 16558651125d2885f74546b6e2a556082111d5b75da3Lang Hames unsigned vr, BitVector &RestoreMBBs, 1656289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 16571953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 16581953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return; 16591953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 16601953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 16611953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && Restores[i].vreg) 1662233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames Restores[i].index = SlotIndex(); 16631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 166481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 16654cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 16664cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// spilled and create empty intervals for their uses. 16674cce6b4c7882ef0cc993d931b90bf33985c96110Evan Chengvoid 16684cce6b4c7882ef0cc993d931b90bf33985c96110Evan ChengLiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 16694cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng const TargetRegisterClass* rc, 16704cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1671419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1672419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng re = mri_->reg_end(); ri != re; ) { 16734cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &O = ri.getOperand(); 1674419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1675419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng ++ri; 167628a1e486907104b85c5787345914917d74f0cf77Evan Cheng if (MI->isDebugValue()) { 167728a1e486907104b85c5787345914917d74f0cf77Evan Cheng // Remove debug info for now. 167828a1e486907104b85c5787345914917d74f0cf77Evan Cheng O.setReg(0U); 167928a1e486907104b85c5787345914917d74f0cf77Evan Cheng DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); 168028a1e486907104b85c5787345914917d74f0cf77Evan Cheng continue; 168128a1e486907104b85c5787345914917d74f0cf77Evan Cheng } 16824cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng if (O.isDef()) { 1683518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner assert(MI->isImplicitDef() && 16844cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng "Register def was not rewritten?"); 16854cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng RemoveMachineInstrFromMaps(MI); 16864cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 16874cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MI->eraseFromParent(); 16884cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } else { 16894cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // This must be an use of an implicit_def so it's not part of the live 16904cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // interval. Create a new empty live interval for it. 16914cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // FIXME: Can we simply erase some of the instructions? e.g. Stores? 16924cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng unsigned NewVReg = mri_->createVirtualRegister(rc); 16934cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.grow(); 16944cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.setIsImplicitlyDefined(NewVReg); 16954cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng NewLIs.push_back(&getOrCreateInterval(NewVReg)); 16964cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 16974cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &MO = MI->getOperand(i); 16984784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng if (MO.isReg() && MO.getReg() == li.reg) { 16994cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MO.setReg(NewVReg); 17004784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng MO.setIsUndef(); 17014784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng } 17024cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 17034cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 1704419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 1705419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng} 1706419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 1707e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesenfloat 1708e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund OlesenLiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { 1709e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // Limit the loop depth ridiculousness. 1710e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen if (loopDepth > 200) 1711e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen loopDepth = 200; 1712e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 1713e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // The loop depth is used to roughly estimate the number of times the 1714e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // instruction is executed. Something like 10^d is simple, but will quickly 1715e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // overflow a float. This expression behaves like 10^d for small d, but is 1716e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of 1717e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // headroom before overflow. 1718dc5198bac7e3f9b61617c8c46a1c28a84daa9325NAKAMURA Takumi // By the way, powf() might be unavailable here. For consistency, 1719dc5198bac7e3f9b61617c8c46a1c28a84daa9325NAKAMURA Takumi // We may take pow(double,double). 1720dc5198bac7e3f9b61617c8c46a1c28a84daa9325NAKAMURA Takumi float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth); 1721e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 1722e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen return (isDef + isUse) * lc; 1723e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen} 1724e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 1725eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesenstatic void normalizeSpillWeights(std::vector<LiveInterval*> &NewLIs) { 1726352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) 1727eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen NewLIs[i]->weight = 1728eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen normalizeSpillWeight(NewLIs[i]->weight, NewLIs[i]->getSize()); 1729352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen} 1730352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen 1731f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengstd::vector<LiveInterval*> LiveIntervals:: 173281a038218171860ee4c382849c647d3dc841fe8bEvan ChengaddIntervalsForSpills(const LiveInterval &li, 173338f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen const SmallVectorImpl<LiveInterval*> *SpillIs, 1734c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { 1735e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen assert(li.isSpillable() && "attempt to spill already spilled interval!"); 1736f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 17378e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 17388a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << "\t\t\t\tadding intervals for spills for interval: "; 17398a34229dcf484739119857988772572ef0cad9f2David Greene li.print(dbgs(), tri_); 17408a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << '\n'; 17418e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 1742f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 174372eeb94fe1d69cd05bdbbe86b2bc9fa25c963c22Evan Cheng // Each bit specify whether a spill is required in the MBB. 174481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector SpillMBBs(mf_->getNumBlockIDs()); 1745289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes; 17460cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector RestoreMBBs(mf_->getNumBlockIDs()); 1747289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes; 1748289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> MBBVRegsMap; 1749f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> NewLIs; 1750d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1751f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1752f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned NumValNums = li.getNumValNums(); 1753f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatDefs; 1754f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDefs.resize(NumValNums, NULL); 1755f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1756f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatOrigDefs.resize(NumValNums, NULL); 1757f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> ReMatIds; 1758f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1759f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng BitVector ReMatDelete(NumValNums); 1760f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1761f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 176281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Spilling a split live interval. It cannot be split any further. Also, 176381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // it's also guaranteed to be a single val# / range interval. 176481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (vrm.getPreSplitReg(li.reg)) { 176581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(li.reg, 0); 1766d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng // Unset the split kill marker on the last use. 1767233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex KillIdx = vrm.getKillPoint(li.reg); 1768233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (KillIdx != SlotIndex()) { 1769d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1770d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillMI && "Last use disappeared?"); 1771d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1772d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillOp != -1 && "Last use disappeared?"); 1773f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner KillMI->getOperand(KillOp).setIsKill(false); 1774d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng } 1775adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng vrm.removeKillPoint(li.reg); 177681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = vrm.isReMaterialized(li.reg); 177781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot = vrm.getStackSlot(li.reg); 177881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng assert(Slot != VirtRegMap::MAX_STACK_SLOT); 177981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = DefIsReMat ? 178081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.getReMaterializedMI(li.reg) : NULL; 178181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int LdSlot = 0; 178281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 178381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoad = isLoadSS || 178415511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad())); 178581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool IsFirstRange = true; 178681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 178781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 178881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a split live interval with multiple ranges, it means there 178981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // are two-address instructions that re-defined the value. Only the 179081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // first def can be rematerialized! 179181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (IsFirstRange) { 1792cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // Note ReMatOrigDefMI has already been deleted. 179381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 179481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1795d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 17960cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1797c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 179881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 179981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, 0, 180081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, 0, false, false, false, 1801d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 18020cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1803c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 180481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 180581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng IsFirstRange = false; 180681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1807419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 18084cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 1809352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen normalizeSpillWeights(NewLIs); 181081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return NewLIs; 181181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 181281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1813752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng bool TrySplit = !intervalIsInOneMBB(li); 18140cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (TrySplit) 18150cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numSplits; 1816f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool NeedStackSlot = false; 1817f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1818f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng i != e; ++i) { 1819f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const VNInfo *VNI = *i; 1820f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned VN = VNI->id; 1821857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->isUnused()) 1822f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; // Dead val#. 1823f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Is the def for the val# rematerializable? 18246e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 18255ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool dummy; 1826dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) { 1827f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Remember how to remat the def of this val#. 182881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReMatOrigDefs[VN] = ReMatDefMI; 18292c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman // Original def may be modified so we have to make a copy here. 18301ed9922794cda9dbe295e74674b909287e544632Evan Cheng MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI); 1831752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng CloneMIs.push_back(Clone); 18321ed9922794cda9dbe295e74674b909287e544632Evan Cheng ReMatDefs[VN] = Clone; 1833f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1834f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = true; 1835857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->hasPHIKill()) { 1836c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // A kill is a phi node, not all of its uses can be rematerialized. 1837f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // It must not be deleted. 1838c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng CanDelete = false; 1839c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // Need a stack slot if there is any live range where uses cannot be 1840c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // rematerialized. 1841c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng NeedStackSlot = true; 1842f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1843f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (CanDelete) 1844f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDelete.set(VN); 1845f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1846f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Need a stack slot if there is any live range where uses cannot be 1847f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // rematerialized. 1848f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng NeedStackSlot = true; 1849f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1850f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1851f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1852f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // One stack slot per live interval. 1853b98bbb7597495fb401b020679a94389298175506Owen Anderson if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) { 1854b98bbb7597495fb401b020679a94389298175506Owen Anderson if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT) 1855b98bbb7597495fb401b020679a94389298175506Owen Anderson Slot = vrm.assignVirt2StackSlot(li.reg); 18561b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 1857b98bbb7597495fb401b020679a94389298175506Owen Anderson // This case only occurs when the prealloc splitter has already assigned 1858b98bbb7597495fb401b020679a94389298175506Owen Anderson // a stack slot to this vreg. 1859b98bbb7597495fb401b020679a94389298175506Owen Anderson else 1860b98bbb7597495fb401b020679a94389298175506Owen Anderson Slot = vrm.getStackSlot(li.reg); 1861b98bbb7597495fb401b020679a94389298175506Owen Anderson } 1862f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1863f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Create new intervals and rewrite defs and uses. 1864f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::Ranges::const_iterator 1865f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 186681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 186781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 186881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = ReMatDefMI != NULL; 1869f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = ReMatDelete[I->valno->id]; 1870f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int LdSlot = 0; 187181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1872f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad = isLoadSS || 187315511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad()); 187481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 18750cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1876d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, 18770cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1878c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 1879f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1880f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 18810cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Insert spills / restores if we are splitting. 1882419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng if (!TrySplit) { 18834cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 1884352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen normalizeSpillWeights(NewLIs); 18851953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return NewLIs; 1886419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 18871953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1888b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng SmallPtrSet<LiveInterval*, 4> AddedKill; 1889aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 18901953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NeedStackSlot) { 18911953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = SpillMBBs.find_first(); 18921953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 18931953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &spills = SpillIdxes[Id]; 18941953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = spills.size(); i != e; ++i) { 1895233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = spills[i].index; 18961953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = spills[i].vreg; 1897597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 18980cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 18990cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1900aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1901aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool FoundUse = false; 1902aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1903cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (spills[i].canFold) { 1904aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 19050cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 19060cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineOperand &MO = MI->getOperand(j); 1907d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || MO.getReg() != VReg) 19080cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 1909aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 1910aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1911aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (MO.isDef()) 1912cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng continue; 19131b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen if (isReMat || 1914aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng (!FoundUse && !alsoFoldARestore(Id, index, VReg, 1915aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng RestoreMBBs, RestoreIdxes))) { 1916aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // MI has two-address uses of the same register. If the use 1917aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // isn't the first and only use in the BB, then we can't fold 1918aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // it. FIXME: Move this to rewriteInstructionsForSpills. 1919aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 1920cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng break; 1921cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 1922aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoundUse = true; 19230cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 19240cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 19250cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the store into the def if possible. 1926cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1927aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 1928aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 1929cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng Folded = true; 193048fe63526e35ddaee7e98879596a569911f41319Sebastian Redl if (FoundUse) { 1931aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Also folded uses, do not issue a load. 1932aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 1933233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.removeRange(index.getLoadIndex(), index.getDefIndex()); 1934f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng } 1935233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.removeRange(index.getDefIndex(), index.getStoreIndex()); 1936cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 19370cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 19380cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 19397e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Otherwise tell the spiller to issue a spill. 1940b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!Folded) { 1941b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 1942233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool isKill = LR->end == index.getStoreIndex(); 1943b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng if (!MI->registerDefIsDead(nI.reg)) 1944b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng // No need to spill a dead def. 1945b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng vrm.addSpillPoint(VReg, isKill, MI); 1946b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (isKill) 1947b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng AddedKill.insert(&nI); 1948b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 19490cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 19501953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = SpillMBBs.find_next(Id); 19510cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 19521953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 19530cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 19541953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = RestoreMBBs.find_first(); 19551953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 19561953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &restores = RestoreIdxes[Id]; 19571953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = restores.size(); i != e; ++i) { 1958233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = restores[i].index; 1959233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (index == SlotIndex()) 19601953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng continue; 19611953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = restores[i].vreg; 1962597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 19639c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 196481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1965aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1966aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1967cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (restores[i].canFold) { 1968aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 196981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 197081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineOperand &MO = MI->getOperand(j); 1971d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || MO.getReg() != VReg) 197281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 1973aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 19740cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MO.isDef()) { 1975aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // If this restore were to be folded, it would have been folded 1976aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // already. 1977aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 197881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng break; 197981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1980aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 198181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 198281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 19830cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 19840cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the load into the use if possible. 1985cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1986aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 19879c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!isReMat) 1988aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 1989aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 19900cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 19910cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng int LdSlot = 0; 19920cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 19930cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If the rematerializable def is a load, also try to fold it. 199415511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad()) 1995aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1996aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops, isLoadSS, LdSlot, VReg); 1997650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng if (!Folded) { 1998650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 1999650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng if (ImpUse) { 2000650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng // Re-matting an instruction with virtual register use. Add the 2001e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // register as an implicit use on the use MI and mark the register 2002e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // interval as unspillable. 2003650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 2004e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen ImpLi.markNotSpillable(); 2005650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 2006650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng } 2007d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 2008aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 20090cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 20100cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If folding is not possible / failed, then tell the spiller to issue a 20110cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // load / rematerialization for us. 2012597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (Folded) 2013233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.removeRange(index.getLoadIndex(), index.getDefIndex()); 2014b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng else 20150cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.addRestorePoint(VReg, MI); 201681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 20171953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = RestoreMBBs.find_next(Id); 201881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 201981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 2020b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // Finalize intervals: add kills, finalize spill weights, and filter out 2021b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // dead intervals. 2022597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng std::vector<LiveInterval*> RetNewLIs; 2023597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 2024597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval *LI = NewLIs[i]; 2025597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (!LI->empty()) { 2026b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!AddedKill.count(LI)) { 2027b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 2028233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex LastUseIdx = LR->end.getBaseIndex(); 2029d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 20306130f66eaae89f8878590796977678afa8448926Evan Cheng int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 2031b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng assert(UseIdx != -1); 2032a24752ff43dc1ad8c18c5d9e78549c45f62b980eEvan Cheng if (!LastUse->isRegTiedToDefOperand(UseIdx)) { 2033b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LastUse->getOperand(UseIdx).setIsKill(); 2034d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng vrm.addKillPoint(LI->reg, LastUseIdx); 2035adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng } 2036b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 2037597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng RetNewLIs.push_back(LI); 2038597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 2039597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 204081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 20414cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 2042352d352c023ed411d9e4357ea01f3ec468ff87dcJakob Stoklund Olesen normalizeSpillWeights(RetNewLIs); 2043597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng return RetNewLIs; 2044f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 2045676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2046676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// hasAllocatableSuperReg - Return true if the specified physical register has 2047676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// any super register that's allocatable. 2048676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengbool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 2049676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 2050676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (allocatableRegs_[*AS] && hasInterval(*AS)) 2051676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return true; 2052676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return false; 2053676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2054676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2055676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getRepresentativeReg - Find the largest super register of the specified 2056676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// physical register. 2057676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 20581b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // Find the largest super-register that is allocatable. 2059676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned BestReg = Reg; 2060676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 2061676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SuperReg = *AS; 2062676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 2063676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng BestReg = SuperReg; 2064676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng break; 2065676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2066676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2067676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return BestReg; 2068676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2069676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2070676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getNumConflictsWithPhysReg - Return the number of uses and defs of the 2071676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// specified interval that conflicts with the specified physical register. 2072676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 2073676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg) const { 2074676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned NumConflicts = 0; 2075676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 2076676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2077676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 2078676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 2079676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 208028a1e486907104b85c5787345914917d74f0cf77Evan Cheng if (MI->isDebugValue()) 208128a1e486907104b85c5787345914917d74f0cf77Evan Cheng continue; 2082233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index = getInstructionIndex(MI); 2083676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) 2084676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng ++NumConflicts; 2085676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2086676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return NumConflicts; 2087676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2088676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2089676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// spillPhysRegAroundRegDefsUses - Spill the specified physical register 20902824a655509577127d221eecd1425de196f80320Evan Cheng/// around all defs and uses of the specified interval. Return true if it 20912824a655509577127d221eecd1425de196f80320Evan Cheng/// was able to cut its interval. 20922824a655509577127d221eecd1425de196f80320Evan Chengbool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 2093676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg, VirtRegMap &vrm) { 2094676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SpillReg = getRepresentativeReg(PhysReg); 2095676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2096f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen DEBUG(dbgs() << "spillPhysRegAroundRegDefsUses " << tri_->getName(PhysReg) 2097f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen << " represented by " << tri_->getName(SpillReg) << '\n'); 2098f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen 2099676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 2100676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // If there are registers which alias PhysReg, but which are not a 2101676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // sub-register of the chosen representative super register. Assert 2102676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // since we can't handle it yet. 210370f2f65aacdbc96fe158b2860b5f0bad075ee548Dan Gohman assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) || 2104676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng tri_->isSuperRegister(*AS, SpillReg)); 2105676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 21062824a655509577127d221eecd1425de196f80320Evan Cheng bool Cut = false; 21070222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng SmallVector<unsigned, 4> PRegs; 21080222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng if (hasInterval(SpillReg)) 21090222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng PRegs.push_back(SpillReg); 2110f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen for (const unsigned *SR = tri_->getSubRegisters(SpillReg); *SR; ++SR) 2111f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen if (hasInterval(*SR)) 2112f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen PRegs.push_back(*SR); 2113f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen 2114f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen DEBUG({ 2115f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen dbgs() << "Trying to spill:"; 2116f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen for (unsigned i = 0, e = PRegs.size(); i != e; ++i) 2117f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen dbgs() << ' ' << tri_->getName(PRegs[i]); 2118f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen dbgs() << '\n'; 2119f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen }); 21200222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng 2121676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SmallPtrSet<MachineInstr*, 8> SeenMIs; 2122676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2123676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 2124676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 2125676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 212628a1e486907104b85c5787345914917d74f0cf77Evan Cheng if (MI->isDebugValue() || SeenMIs.count(MI)) 2127676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 2128676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SeenMIs.insert(MI); 2129233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index = getInstructionIndex(MI); 2130f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen bool LiveReg = false; 21310222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng for (unsigned i = 0, e = PRegs.size(); i != e; ++i) { 21320222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng unsigned PReg = PRegs[i]; 21330222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng LiveInterval &pli = getInterval(PReg); 21340222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng if (!pli.liveAt(Index)) 21350222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng continue; 2136f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen LiveReg = true; 2137233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex StartIdx = Index.getLoadIndex(); 2138233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex EndIdx = Index.getNextIndex().getBaseIndex(); 2139f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen if (!pli.isInOneLiveRange(StartIdx, EndIdx)) { 21407d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin std::string msg; 21417d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin raw_string_ostream Msg(msg); 21427d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin Msg << "Ran out of registers during register allocation!"; 2143518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isInlineAsm()) { 21447d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin Msg << "\nPlease check your inline asm statement for invalid " 21450222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng << "constraints:\n"; 21467d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin MI->print(Msg, tm_); 21475a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng } 214875361b69f3f327842b9dad69fa7f28ae3b688412Chris Lattner report_fatal_error(Msg.str()); 21495a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng } 2150f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen pli.removeRange(StartIdx, EndIdx); 2151f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen LiveReg = true; 2152676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2153f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen if (!LiveReg) 2154f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen continue; 2155f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen DEBUG(dbgs() << "Emergency spill around " << Index << '\t' << *MI); 2156f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen vrm.addEmergencySpill(SpillReg, MI); 2157f4840c07f84d018c4de5dbdad4166b9e162f8f89Jakob Stoklund Olesen Cut = true; 2158676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 21592824a655509577127d221eecd1425de196f80320Evan Cheng return Cut; 2160676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2161c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 2162c4dc132c8a787fc41b6a162121251234aa618965Owen AndersonLiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 2163ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames MachineInstr* startInst) { 2164c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveInterval& Interval = getOrCreateInterval(reg); 2165c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VNInfo* VN = Interval.getNextValue( 2166233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex(getInstructionIndex(startInst).getDefIndex()), 21676e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames startInst, getVNInfoAllocator()); 2168857c4e01f85601cf2084adb860616256ee47c177Lang Hames VN->setHasPHIKill(true); 21698651125d2885f74546b6e2a556082111d5b75da3Lang Hames LiveRange LR( 2170233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex(getInstructionIndex(startInst).getDefIndex()), 217174ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames getMBBEndIdx(startInst->getParent()), VN); 2172c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson Interval.addRange(LR); 21731b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 2174c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson return LR; 2175c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson} 2176b5257664795d49ada0d4669fe8ed1cd49c04fbf3David Greene 2177