LiveIntervalAnalysis.cpp revision 6cd8103bea5c0bc92f30b8021e9469131a2a408f
1a3b8b5c0e0a1d0942288568b2012592184ca67c5Chris Lattner//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 2ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 3ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// The LLVM Compiler Infrastructure 4ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 8ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos//===----------------------------------------------------------------------===// 9ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 10ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// This file implements the LiveInterval analysis pass which is used 11ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// by the Linear Scan Register allocator. This pass linearizes the 12ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// basic blocks of the function in DFS order and uses the 13ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// LiveVariables pass to conservatively compute live intervals for 14ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// each virtual and physical register. 15ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 16ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos//===----------------------------------------------------------------------===// 17ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 18ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#define DEBUG_TYPE "liveintervals" 193c3fe462f7978b429ecdd71750c26be25c3d1335Chris Lattner#include "llvm/CodeGen/LiveIntervalAnalysis.h" 2008a6c7614be9793754b17930ba619e875aef9585Misha Brukman#include "VirtRegMap.h" 21015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner#include "llvm/Value.h" 226d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#include "llvm/Analysis/AliasAnalysis.h" 23ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/LiveVariables.h" 24ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 25ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineInstr.h" 262578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng#include "llvm/CodeGen/MachineInstrBuilder.h" 2722f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 28c76909abfec876c6b751d693ebd3df07df686aa0Dan Gohman#include "llvm/CodeGen/MachineMemOperand.h" 2984bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 30ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/Passes.h" 31233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/ProcessImplicitDefs.h" 326f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 33ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 34ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 3595dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson#include "llvm/Target/TargetOptions.h" 36551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 37551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 387d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 397d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/raw_ostream.h" 402578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng#include "llvm/ADT/DepthFirstIterator.h" 412578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng#include "llvm/ADT/SmallSet.h" 42551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 43551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 4420aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 45f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames#include <limits> 4697af751deb9b26fd42fbcee082da9ccc4ded5b45Jeff Cohen#include <cmath> 47ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 48ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 49844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Hidden options for help debugging. 50844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> DisableReMat("disable-rematerialization", 51844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(false), cl::Hidden); 52844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 53ae339babb2a2445e7bb009912a39994718f10d54Owen Andersonstatic cl::opt<bool> EnableFastSpilling("fast-spill", 54ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson cl::init(false), cl::Hidden); 55ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson 56752195e3c662c6b5db042cf897c984624720f3b8Evan ChengSTATISTIC(numIntervals , "Number of original intervals"); 57752195e3c662c6b5db042cf897c984624720f3b8Evan ChengSTATISTIC(numFolds , "Number of loads/stores folded into instructions"); 58752195e3c662c6b5db042cf897c984624720f3b8Evan ChengSTATISTIC(numSplits , "Number of intervals split"); 59cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 601997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar LiveIntervals::ID = 0; 61844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 62ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 63f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 64845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman AU.setPreservesCFG(); 656d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addRequired<AliasAnalysis>(); 666d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addPreserved<AliasAnalysis>(); 672513330de8f8020d15d5bc96640a0957b7c733b9David Greene AU.addPreserved<LiveVariables>(); 681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LiveVariables>(); 6967d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineLoopInfoID); 7067d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineDominatorsID); 7195dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson 7295dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson if (!StrongPHIElim) { 7395dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson AU.addPreservedID(PHIEliminationID); 7495dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson AU.addRequiredID(PHIEliminationID); 7595dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson } 7695dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson 771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 78233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addPreserved<ProcessImplicitDefs>(); 79233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addRequired<ProcessImplicitDefs>(); 80233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addPreserved<SlotIndexes>(); 81233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addRequiredTransitive<SlotIndexes>(); 821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 83ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 84ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 85f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::releaseMemory() { 8603857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson // Free the live intervals themselves. 8720e2839cb975a2d4ee931e1ea4c4660a36ef0177Owen Anderson for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(), 8803857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson E = r2iMap_.end(); I != E; ++I) 8903857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson delete I->second; 9003857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson 911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 92ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 93dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 94dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng VNInfoAllocator.Reset(); 95752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng while (!CloneMIs.empty()) { 96752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng MachineInstr *MI = CloneMIs.back(); 97752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng CloneMIs.pop_back(); 981ed9922794cda9dbe295e74674b909287e544632Evan Cheng mf_->DeleteMachineInstr(MI); 991ed9922794cda9dbe295e74674b909287e544632Evan Cheng } 100993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 101993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 10280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// runOnMachineFunction - Register allocate the whole function 10380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// 10480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Andersonbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 10580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mf_ = &fn; 10680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mri_ = &mf_->getRegInfo(); 10780b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tm_ = &fn.getTarget(); 10880b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tri_ = tm_->getRegisterInfo(); 10980b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tii_ = tm_->getInstrInfo(); 1106d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman aa_ = &getAnalysis<AliasAnalysis>(); 11180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson lv_ = &getAnalysis<LiveVariables>(); 112233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames indexes_ = &getAnalysis<SlotIndexes>(); 11380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson allocatableRegs_ = tri_->getAllocatableSet(fn); 114ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 116ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 118843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 11970ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 1201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 121ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 122ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 12370ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 12445cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattnervoid LiveIntervals::print(raw_ostream &OS, const Module* ) const { 125705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "********** INTERVALS **********\n"; 1268e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 127705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner I->second->print(OS, tri_); 128705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "\n"; 1298e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 13070ca358b7d540b6061236ddf757085042873c12cChris Lattner 131752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printInstrs(OS); 132752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng} 133752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 134752195e3c662c6b5db042cf897c984624720f3b8Evan Chengvoid LiveIntervals::printInstrs(raw_ostream &OS) const { 135705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "********** MACHINEINSTRS **********\n"; 136705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner 1373380d5c4aaafc3d78d32f583d685d64a67ae5224Chris Lattner for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 1383380d5c4aaafc3d78d32f583d685d64a67ae5224Chris Lattner mbbi != mbbe; ++mbbi) { 1396cd8103bea5c0bc92f30b8021e9469131a2a408fJakob Stoklund Olesen OS << "BB#" << mbbi->getNumber() 1406cd8103bea5c0bc92f30b8021e9469131a2a408fJakob Stoklund Olesen << ":\t\t# derived from " << mbbi->getName() << "\n"; 1413380d5c4aaafc3d78d32f583d685d64a67ae5224Chris Lattner for (MachineBasicBlock::iterator mii = mbbi->begin(), 1423380d5c4aaafc3d78d32f583d685d64a67ae5224Chris Lattner mie = mbbi->end(); mii != mie; ++mii) { 143705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << getInstructionIndex(mii) << '\t' << *mii; 1443380d5c4aaafc3d78d32f583d685d64a67ae5224Chris Lattner } 1453380d5c4aaafc3d78d32f583d685d64a67ae5224Chris Lattner } 14670ca358b7d540b6061236ddf757085042873c12cChris Lattner} 14770ca358b7d540b6061236ddf757085042873c12cChris Lattner 148752195e3c662c6b5db042cf897c984624720f3b8Evan Chengvoid LiveIntervals::dumpInstrs() const { 149752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printInstrs(errs()); 150752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng} 151752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 152c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng/// conflictsWithPhysRegDef - Returns true if the specified register 153c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng/// is defined during the duration of the specified interval. 154c92da3882ee4e18153bb36fcdf33af393aba8259Evan Chengbool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, 155c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng VirtRegMap &vrm, unsigned reg) { 156c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (LiveInterval::Ranges::const_iterator 157c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 158233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames for (SlotIndex index = I->start.getBaseIndex(), 159233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); 160233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames index != end; 161233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames index = index.getNextIndex()) { 162c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng // skip deleted instructions 163c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng while (index != end && !getInstructionFromIndex(index)) 164233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames index = index.getNextIndex(); 165c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng if (index == end) break; 166c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 167c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 16804ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 16904ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 1705d446265c740c17ed12e693423f0363296670d60Evan Cheng if (SrcReg == li.reg || DstReg == li.reg) 1715d446265c740c17ed12e693423f0363296670d60Evan Cheng continue; 172c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 173c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng MachineOperand& mop = MI->getOperand(i); 174d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!mop.isReg()) 175c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 176c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng unsigned PhysReg = mop.getReg(); 1775d446265c740c17ed12e693423f0363296670d60Evan Cheng if (PhysReg == 0 || PhysReg == li.reg) 178c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 1796f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { 1805d446265c740c17ed12e693423f0363296670d60Evan Cheng if (!vrm.hasPhys(PhysReg)) 1815d446265c740c17ed12e693423f0363296670d60Evan Cheng continue; 182c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng PhysReg = vrm.getPhys(PhysReg); 1835d446265c740c17ed12e693423f0363296670d60Evan Cheng } 1846f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (PhysReg && tri_->regsOverlap(PhysReg, reg)) 185c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return true; 186c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 187c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 188c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 189c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 190c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return false; 191c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng} 192c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 1938f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng/// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except 1948f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng/// it can check use as well. 1958f90b6eb2fd0125f5b779de80954944f9071fb87Evan Chengbool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li, 1968f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng unsigned Reg, bool CheckUse, 1978f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng SmallPtrSet<MachineInstr*,32> &JoinedCopies) { 1988f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng for (LiveInterval::Ranges::const_iterator 1998f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 200233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames for (SlotIndex index = I->start.getBaseIndex(), 201233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); 202233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames index != end; 203233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames index = index.getNextIndex()) { 2048f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng // Skip deleted instructions. 2058f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng MachineInstr *MI = 0; 2068f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng while (index != end) { 2078f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng MI = getInstructionFromIndex(index); 2088f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (MI) 2098f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng break; 210233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames index = index.getNextIndex(); 2118f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 2128f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (index == end) break; 2138f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 2148f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (JoinedCopies.count(MI)) 2158f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 2168f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 2178f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng MachineOperand& MO = MI->getOperand(i); 2188f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (!MO.isReg()) 2198f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 2208f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (MO.isUse() && !CheckUse) 2218f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 2228f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng unsigned PhysReg = MO.getReg(); 2238f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (PhysReg == 0 || TargetRegisterInfo::isVirtualRegister(PhysReg)) 2248f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 2258f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (tri_->isSubRegister(Reg, PhysReg)) 2268f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng return true; 2278f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 2288f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 2298f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 2308f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 2318f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng return false; 2328f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng} 2338f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 234504f9a61e61ee274fe50d8300825bdc2e5adb9b0Daniel Dunbar#ifndef NDEBUG 235752195e3c662c6b5db042cf897c984624720f3b8Evan Chengstatic void printRegName(unsigned reg, const TargetRegisterInfo* tri_) { 2366f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isPhysicalRegister(reg)) 2373f0e83067d7938f742d21e14fc87c006d2fc3161Daniel Dunbar errs() << tri_->getName(reg); 2381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 2393f0e83067d7938f742d21e14fc87c006d2fc3161Daniel Dunbar errs() << "%reg" << reg; 240ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 241504f9a61e61ee274fe50d8300825bdc2e5adb9b0Daniel Dunbar#endif 242ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 243be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 244ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 245233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 2468651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineOperand& MO, 247ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx, 248be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 2498e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 2508e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling errs() << "\t\tregister: "; 251752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printRegName(interval.reg, tri_); 2528e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 253419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 254706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 255706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 256706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 2571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 258d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 2591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 2601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 261233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex defIndex = MIIdx.getDefIndex(); 26239faac2531268b8555475796c6071556670dc290Dale Johannesen // Earlyclobbers move back one, so that they overlap the live range 26339faac2531268b8555475796c6071556670dc290Dale Johannesen // of inputs. 26486b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen if (MO.isEarlyClobber()) 265233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames defIndex = MIIdx.getUseIndex(); 2667ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 267c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 26804ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 269c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 2707e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 27197121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 27204ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 273c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 2745379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng // Earlyclobbers move back one. 275857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); 2767ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 2777ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(ValNo->id == 0 && "First value in interval is not 0?"); 2781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 2801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 2811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 2821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 2831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 2841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 285233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex killIdx; 2861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 287233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex(); 2881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 289233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames killIdx = defIndex.getStoreIndex(); 2901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 2921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 2931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 294493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin assert(vi.AliveBlocks.empty() && 2951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 2967ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIdx, ValNo); 2971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 2988e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " +" << LR << "\n"); 2998651125d2885f74546b6e2a556082111d5b75da3Lang Hames ValNo->addKill(killIdx); 3001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 3011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3036097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 3041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 3051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 3061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 3071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 308233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange NewLR(defIndex, getMBBEndIdx(mbb).getNextIndex().getLoadIndex(), 309233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames ValNo); 3108e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " +" << NewLR); 3111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 3121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Iterate over all of the blocks that the variable is completely 3141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 3151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live interval. 316493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 317493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin E = vi.AliveBlocks.end(); I != E; ++I) { 318233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange LR( 319233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames getMBBStartIdx(mf_->getBlockNumbered(*I)), 320233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames getMBBEndIdx(mf_->getBlockNumbered(*I)).getNextIndex().getLoadIndex(), 321233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames ValNo); 3224a829ecc54cdcb0192550639556a18728af5119cDan Gohman interval.addRange(LR); 3238e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " +" << LR); 3241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 3271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 3281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 3291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 330233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex killIdx = 331233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames getInstructionIndex(Kill).getDefIndex(); 332b0f5973bee566269f41d1cc21b7a1d3bede1d837Evan Cheng LiveRange LR(getMBBStartIdx(Kill->getParent()), killIdx, ValNo); 3331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3348651125d2885f74546b6e2a556082111d5b75da3Lang Hames ValNo->addKill(killIdx); 3358e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " +" << LR); 3361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 3391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 3401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 341bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 342bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 343d9df5017040489303acb57bdd8697ef0f8bafc08Bob Wilson if (mi->isRegTiedToUseOperand(MOIdx)) { 3441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 3451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 3461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 3471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 3481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 349a07cec9e24a286157541d2337cd66b24cd116586Evan Cheng assert(interval.containsOneValue()); 350233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex DefIndex = interval.getValNumInfo(0)->def.getDefIndex(); 351233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex RedefIndex = MIIdx.getDefIndex(); 352fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 353233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames RedefIndex = MIIdx.getUseIndex(); 3541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 35535f291d2c5f80e8e713704190230064311bbbbbeLang Hames const LiveRange *OldLR = 356233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames interval.getLiveRangeContaining(RedefIndex.getUseIndex()); 3577ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *OldValNo = OldLR->valno; 3584f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 3591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Delete the initial value, which should be short and continuous, 360be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 3611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 362706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 363be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Two-address vregs should always only be redefined once. This means 364be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // that at this point, there should be exactly one value number in it. 365be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 366be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 36791725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 36891725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 36952c1afcaea61440950a11a4ccadac4354420d727Lang Hames VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->getCopy(), 370857c4e01f85601cf2084adb860616256ee47c177Lang Hames false, // update at * 371c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng VNInfoAllocator); 372857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setFlags(OldValNo->getFlags()); // * <- updating here 373857c4e01f85601cf2084adb860616256ee47c177Lang Hames 37491725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 375c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->def = RedefIndex; 37652c1afcaea61440950a11a4ccadac4354420d727Lang Hames OldValNo->setCopy(0); 377fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 378857c4e01f85601cf2084adb860616256ee47c177Lang Hames OldValNo->setHasRedefByEC(true); 379be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 380be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 381be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 3828e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " replace range with " << LR); 3831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3848651125d2885f74546b6e2a556082111d5b75da3Lang Hames ValNo->addKill(RedefIndex); 3851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 3871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 3886b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) 389233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(), 390233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames OldValNo)); 3911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3928e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 3938e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling errs() << " RESULT: "; 3948e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling interval.print(errs(), tri_); 3958e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 3961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 3971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Otherwise, this must be because of phi elimination. If this is the 3981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // first redefinition of the vreg that we have seen, go back and change 3991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range in the PHI block to be a different value number. 4001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.containsOneValue()) { 4011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Remove the old range that we now know has an incorrect number. 402f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng VNInfo *VNI = interval.getValNumInfo(0); 4031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Killer = vi.Kills[0]; 404233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Start = getMBBStartIdx(Killer->getParent()); 405233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex End = getInstructionIndex(Killer).getDefIndex(); 4068e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 4078e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling errs() << " Removing [" << Start << "," << End << "] from: "; 4088e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling interval.print(errs(), tri_); 4098e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling errs() << "\n"; 4108e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 411ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames interval.removeRange(Start, End); 412ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames assert(interval.ranges.size() == 1 && 413752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng "Newly discovered PHI interval has >1 ranges."); 4148651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineBasicBlock *killMBB = getMBBFromIndex(interval.endIndex()); 415233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames VNI->addKill(indexes_->getTerminatorGap(killMBB)); 416857c4e01f85601cf2084adb860616256ee47c177Lang Hames VNI->setHasPHIKill(true); 4178e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 4188e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling errs() << " RESULT: "; 4198e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling interval.print(errs(), tri_); 4208e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 4211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 422be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Replace the interval with one of a NEW value number. Note that this 423be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // value number isn't actually defined by an instruction, weird huh? :) 42410382fb71d8306f320ecbeb7049d25354c0e5457Lang Hames LiveRange LR(Start, End, 425233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames interval.getNextValue(SlotIndex(getMBBStartIdx(mbb), true), 426233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 0, false, VNInfoAllocator)); 427857c4e01f85601cf2084adb860616256ee47c177Lang Hames LR.valno->setIsPHIDef(true); 4288e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " replace range with " << LR); 4291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4308651125d2885f74546b6e2a556082111d5b75da3Lang Hames LR.valno->addKill(End); 4318e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 4328e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling errs() << " RESULT: "; 4338e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling interval.print(errs(), tri_); 4348e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 4351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 4381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 4391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 440233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex defIndex = MIIdx.getDefIndex(); 441fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 442233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames defIndex = MIIdx.getUseIndex(); 443752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 4447ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 445c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 44604ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 447c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 4487e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 44997121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 45004ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 451c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 452857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); 45391725b75852443923b419fd23215194cfc65dd88Chris Lattner 454233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex killIndex = getMBBEndIdx(mbb).getNextIndex().getLoadIndex(); 4557ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 4561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 457233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames ValNo->addKill(indexes_->getTerminatorGap(mbb)); 458857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasPHIKill(true); 4598e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " +" << LR); 460dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 4611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 462ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 4638e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << '\n'); 464ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 465ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 466f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 467ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 468233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 4696b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson MachineOperand& MO, 47091725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveInterval &interval, 471c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI) { 4721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 4731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 4748e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 4758e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling errs() << "\t\tregister: "; 476752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printRegName(interval.reg, tri_); 4778e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 4781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 479233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 480233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = baseIndex.getDefIndex(); 48186b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen // Earlyclobbers move back one. 48286b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen if (MO.isEarlyClobber()) 483233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames start = MIIdx.getUseIndex(); 484233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = start; 4851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 4871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 4881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 48939faac2531268b8555475796c6071556670dc290Dale Johannesen // For earlyclobbers, the defSlot was pushed back one; the extra 49039faac2531268b8555475796c6071556670dc290Dale Johannesen // advance below compensates. 4916b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) { 4928e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " dead"); 493233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = start.getStoreIndex(); 494ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 4951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 496ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 4971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 4981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 4991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 500233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 5015ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 502233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 503233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 504233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 505233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 5066130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 5078e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " killed"); 508233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = baseIndex.getDefIndex(); 509ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 510c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 511c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_); 512c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (DefIdx != -1) { 513c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (mi->isRegTiedToUseOperand(DefIdx)) { 514c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Two-address instruction. 515233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = baseIndex.getDefIndex(); 516233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames assert(!mi->getOperand(DefIdx).isEarlyClobber() && 517233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames "Two address instruction is an early clobber?"); 518c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 519c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Another instruction redefines the register before it is ever read. 520c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Then the register is essentially dead at the instruction that defines 521c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // it. Hence its interval is: 522c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // [defSlot(def), defSlot(def)+1) 5238e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " dead"); 524233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = start.getStoreIndex(); 525c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 526c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng goto exit; 527c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 528f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5297fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 530233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 5311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5325ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner 5335ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 5345ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 535d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // and never used. Another possible case is the implicit use of the 536d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // physical register has been deleted by two-address pass. 537233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = start.getStoreIndex(); 53802ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 539ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 5401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 541f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 54224a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 54324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 5445379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng bool Extend = OldLR != interval.end(); 5455379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng VNInfo *ValNo = Extend 546857c4e01f85601cf2084adb860616256ee47c177Lang Hames ? OldLR->valno : interval.getNextValue(start, CopyMI, true, VNInfoAllocator); 5475379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng if (MO.isEarlyClobber() && Extend) 548857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasRedefByEC(true); 5497ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 5501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 5518651125d2885f74546b6e2a556082111d5b75da3Lang Hames LR.valno->addKill(end); 5528e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " +" << LR << '\n'); 553ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 554ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 555f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 556f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 557233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 558ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng MachineOperand& MO, 559ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx) { 5606b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 561ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 5626b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg())); 5636b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson else if (allocatableRegs_[MO.getReg()]) { 564c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 56504ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 566c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 5677e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 56897121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 56904ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 570c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = MI; 571c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 5726b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg()), CopyMI); 57324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Def of a register also defines its sub-registers. 5746b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS) 5756130f66eaae89f8878590796977678afa8448926Evan Cheng // If MI also modifies the sub-register explicitly, avoid processing it 5766130f66eaae89f8878590796977678afa8448926Evan Cheng // more than once. Do not pass in TRI here so it checks for exact match. 5776130f66eaae89f8878590796977678afa8448926Evan Cheng if (!MI->modifiesRegister(*AS)) 578c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 5796b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(*AS), 0); 580f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5814d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 5824d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 583b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 584233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 58524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 5868e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 5878e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling errs() << "\t\tlivein register: "; 588752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printRegName(interval.reg, tri_); 5898e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 590b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 591b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 592b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 593b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 594233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 595233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = baseIndex; 596233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 597233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 598233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 599233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = baseIndex; 6000076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng bool SeenDefUse = false; 60199500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson 602b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng while (mi != MBB->end()) { 6036130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 6048e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " killed"); 605233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = baseIndex.getDefIndex(); 6060076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng SeenDefUse = true; 607d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames break; 6086130f66eaae89f8878590796977678afa8448926Evan Cheng } else if (mi->modifiesRegister(interval.reg, tri_)) { 609b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Another instruction redefines the register before it is ever read. 610b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Then the register is essentially dead at the instruction that defines 611b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // it. Hence its interval is: 612b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // [defSlot(def), defSlot(def)+1) 6138e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " dead"); 614233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = start.getStoreIndex(); 6150076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng SeenDefUse = true; 616d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames break; 617b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 618b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 619b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng ++mi; 6200076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng if (mi != MBB->end()) { 621233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 6220076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng } 623b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 624b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 62575611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 6260076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng if (!SeenDefUse) { 627292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng if (isAlias) { 6288e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " dead"); 629233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames end = MIIdx.getStoreIndex(); 630292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } else { 6318e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " live through"); 632292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng end = baseIndex; 633292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } 63424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 63524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 63610382fb71d8306f320ecbeb7049d25354c0e5457Lang Hames VNInfo *vni = 637233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames interval.getNextValue(SlotIndex(getMBBStartIdx(MBB), true), 6388651125d2885f74546b6e2a556082111d5b75da3Lang Hames 0, false, VNInfoAllocator); 639d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames vni->setIsPHIDef(true); 640d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames LiveRange LR(start, end, vni); 6413de23e6f6cf337451a0934159da494d645b93133Jakob Stoklund Olesen 6429b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 6438651125d2885f74546b6e2a556082111d5b75da3Lang Hames LR.valno->addKill(end); 6448e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " +" << LR << '\n'); 645b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 646b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 647ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 6484d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 64908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 650ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 65191aac1015e6714d959801dd8d60f55a72827dc4dDale Johannesenvoid LiveIntervals::computeIntervals() { 652ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar DEBUG(errs() << "********** COMPUTING LIVE INTERVALS **********\n" 6538e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << "********** Function: " 6548e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'); 655d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 656d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng SmallVector<unsigned, 8> UndefUses; 657428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 658428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 659428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 660134eb73fc35e6ead3cfd3ed5024d0d7efa507441Owen Anderson // Track the index of the current machine instr. 661233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIndex = getMBBStartIdx(MBB); 662324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen DEBUG(errs() << MBB->getName() << ":\n"); 6631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 664428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 6650c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 666cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 667cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 668cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 669cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 670cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Multiple live-ins can alias the same register. 6716f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 672cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!hasInterval(*AS)) 673cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 674cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman true); 675dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 676dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner 67799500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson // Skip over empty initial indices. 678233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(MIIndex) == 0) 679233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 68099500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson 681428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (; MI != miEnd; ++MI) { 6828e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << MIIndex << "\t" << *MI); 6831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 684438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 685428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 686428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 687d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (!MO.isReg() || !MO.getReg()) 688d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng continue; 689d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 6901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 691d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (MO.isDef()) 692ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleRegisterDef(MBB, MI, MIIndex, MO, i); 693d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng else if (MO.isUndef()) 694d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng UndefUses.push_back(MO.getReg()); 6951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 6967fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 697233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Move to the next instr slot. 698233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 699ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 7001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 701d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 702d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // Create empty intervals for registers defined by implicit_def's (except 703d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // for those implicit_def that define values which are liveout of their 704d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // blocks. 705d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { 706d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng unsigned UndefReg = UndefUses[i]; 707d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng (void)getOrCreateInterval(UndefReg); 708d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng } 709ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 710b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 71103857b29d8271a23943254579e6cf7b7df4b1bd3Owen AndersonLiveInterval* LiveIntervals::createInterval(unsigned reg) { 7120a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 71303857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson return new LiveInterval(reg, Weight); 7149a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 715f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 7160a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// dupInterval - Duplicate a live interval. The caller is responsible for 7170a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// managing the allocated memory. 7180a1fcce09230e9b4bd30a8f07447aa075dce7470Evan ChengLiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 7190a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng LiveInterval *NewLI = createInterval(li->reg); 72090f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng NewLI->Copy(*li, mri_, getVNInfoAllocator()); 7210a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng return NewLI; 7220a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng} 7230a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng 724c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// getVNInfoSourceReg - Helper function that parses the specified VNInfo 725c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// copy field and returns the source register that defines it. 726c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Chengunsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 72752c1afcaea61440950a11a4ccadac4354420d727Lang Hames if (!VNI->getCopy()) 728c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 729c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 73052c1afcaea61440950a11a4ccadac4354420d727Lang Hames if (VNI->getCopy()->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { 7318f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng // If it's extracting out of a physical register, return the sub-register. 73252c1afcaea61440950a11a4ccadac4354420d727Lang Hames unsigned Reg = VNI->getCopy()->getOperand(1).getReg(); 7338f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (TargetRegisterInfo::isPhysicalRegister(Reg)) 73452c1afcaea61440950a11a4ccadac4354420d727Lang Hames Reg = tri_->getSubReg(Reg, VNI->getCopy()->getOperand(2).getImm()); 7358f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng return Reg; 73652c1afcaea61440950a11a4ccadac4354420d727Lang Hames } else if (VNI->getCopy()->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 73752c1afcaea61440950a11a4ccadac4354420d727Lang Hames VNI->getCopy()->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) 73852c1afcaea61440950a11a4ccadac4354420d727Lang Hames return VNI->getCopy()->getOperand(2).getReg(); 7398f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 74004ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 74152c1afcaea61440950a11a4ccadac4354420d727Lang Hames if (tii_->isMoveInstr(*VNI->getCopy(), SrcReg, DstReg, SrcSubReg, DstSubReg)) 742c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return SrcReg; 743c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("Unrecognized copy instruction!"); 744c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 745c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng} 746f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 747f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 748f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 749f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 750f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 751d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 752d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 753d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 754d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 755d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 756d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 757d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 758d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 759d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || !MO.isUse()) 760d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 761d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 762d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 763d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 7641873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner 7651873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner if (TargetRegisterInfo::isPhysicalRegister(Reg) && 7661873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner !allocatableRegs_[Reg]) 7671873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner continue; 768d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // FIXME: For now, only remat MI with at most one register operand. 769d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng assert(!RegOp && 770d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng "Can't rematerialize instruction with multiple register operand!"); 771d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 7726d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#ifndef NDEBUG 773d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng break; 7746d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#endif 775d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 776d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 777d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 778d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 779d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 780d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 781d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 782233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx) const { 783233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index = getInstructionIndex(MI); 784d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 785d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 786d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return UI != li.end() && UI->valno == ValNo; 787d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 788d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 789f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 790f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 791f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 7925ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *ValNo, MachineInstr *MI, 793dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng SmallVectorImpl<LiveInterval*> &SpillIs, 7945ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool &isLoad) { 795f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 796f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 797f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 798a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman if (!tii_->isTriviallyReMaterializable(MI, aa_)) 799a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman return false; 800f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 801a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // Target-specific code can mark an instruction as being rematerializable 802a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // if it has one virtual reg use, though it had better be something like 803a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // a PIC base register which is likely to be live everywhere. 8046d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = getReMatImplicitUse(li, MI); 8056d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse) { 8066d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const LiveInterval &ImpLi = getInterval(ImpUse); 8076d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), 8086d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman re = mri_->use_end(); ri != re; ++ri) { 8096d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineInstr *UseMI = &*ri; 810233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx = getInstructionIndex(UseMI); 8116d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 8126d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman continue; 8136d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 8146d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8156d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 816dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng 817dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // If a register operand of the re-materialized instruction is going to 818dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // be spilled next, then it's not legal to re-materialize this instruction. 819dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng for (unsigned i = 0, e = SpillIs.size(); i != e; ++i) 820dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng if (ImpUse == SpillIs[i]->reg) 821dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng return false; 8226d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 8236d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return true; 8245ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 8255ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 82606587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 82706587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng/// val# of the specified interval is re-materializable. 82806587497dc1c39516f24784a2ac1d9323faae0a5Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 82906587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng const VNInfo *ValNo, MachineInstr *MI) { 83006587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng SmallVector<LiveInterval*, 4> Dummy1; 83106587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng bool Dummy2; 83206587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng return isReMaterializable(li, ValNo, MI, Dummy1, Dummy2); 83306587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng} 83406587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng 8355ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 8365ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 837dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 838dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng SmallVectorImpl<LiveInterval*> &SpillIs, 839dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng bool &isLoad) { 8405ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 8415ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 8425ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 8435ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 844857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->isUnused()) 8455ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 8465ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 847857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (!VNI->isDefAccurate()) 8485ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng return false; 849857c4e01f85601cf2084adb860616256ee47c177Lang Hames MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 8505ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 851d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 852dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 853f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 8545ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 855f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 856f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 857f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 858f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 85979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// FilterFoldedOps - Filter out two-address use operands. Return 86079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// true if it finds any issue with the operands that ought to prevent 86179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// folding. 86279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengstatic bool FilterFoldedOps(MachineInstr *MI, 86379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 86479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned &MRInfo, 86579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &FoldOps) { 86679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MRInfo = 0; 867aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 868aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned OpIdx = Ops[i]; 869d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(OpIdx); 870aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // FIXME: fold subreg use. 871d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.getSubReg()) 87279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 873d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.isDef()) 874aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isMod; 875aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 876aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Filter out two-address use operand(s). 877a24752ff43dc1ad8c18c5d9e78549c45f62b980eEvan Cheng if (MI->isRegTiedToDefOperand(OpIdx)) { 878aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo = VirtRegMap::isModRef; 879aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng continue; 880aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 881aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isRef; 882aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 883aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoldOps.push_back(OpIdx); 884e62f97c094dba44e4c259d20135167fa91912eeaEvan Cheng } 88579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 88679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng} 88779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 88879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 88979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 89079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// slot / to reg or any rematerialized load into ith operand of specified 89179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// MI. If it is successul, MI is updated with the newly created MI and 89279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// returns true. 89379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengbool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 89479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng VirtRegMap &vrm, MachineInstr *DefMI, 895233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex InstrIdx, 89679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 89779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng bool isSS, int Slot, unsigned Reg) { 89879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // If it is an implicit def instruction, just delete it. 89920ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 90079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng RemoveMachineInstrFromMaps(MI); 90179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 90279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MI->eraseFromParent(); 90379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng ++numFolds; 90479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 90579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng } 90679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 90779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 90879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 90979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 91079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> FoldOps; 91179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 91279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 913cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 914427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // The only time it's safe to fold into a two address instruction is when 915427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // it's folding reload and spill from / into a spill stack slot. 916427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng if (DefMI && (MRInfo & VirtRegMap::isMod)) 917249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng return false; 918249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng 919f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 920f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 921f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (fmi) { 922d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng // Remember this instruction uses the spill slot. 923d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng if (isSS) vrm.addSpillSlotUse(Slot, fmi); 924d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng 925f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Attempt to fold the memory reference into the instruction. If 926f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // we can do this, we don't need to insert spill code. 927f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineBasicBlock &MBB = *MI->getParent(); 9288480293f41c11c22762164449e41cd3adb0dd7d8Evan Cheng if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 929aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 93081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.transferSpillPts(MI, fmi); 9310cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.transferRestorePts(MI, fmi); 932c1f53c742620dd4f2460685477303002bba8a8d8Evan Cheng vrm.transferEmergencySpills(MI, fmi); 933233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames ReplaceMachineInstrInMaps(MI, fmi); 934f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI = MBB.insert(MBB.erase(MI), fmi); 9350cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numFolds; 936f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 937f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 938f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 939f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 940f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 941018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// canFoldMemoryOperand - Returns true if the specified load / store 942018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// folding is possible. 943018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 94479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 9453c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng bool ReMat) const { 94679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 94779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 94879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 949018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng SmallVector<unsigned, 2> FoldOps; 95079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 95179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 952018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 9533c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng // It's only legal to remat for a use, not a def. 9543c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng if (ReMat && (MRInfo & VirtRegMap::isMod)) 95579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 956018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 957d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return tii_->canFoldMemoryOperand(MI, FoldOps); 958d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 959d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 96081a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 961233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveInterval::Ranges::const_iterator itr = li.ranges.begin(); 962233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 963233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end); 964233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 965233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (mbb == 0) 966233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return false; 967233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 968233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames for (++itr; itr != li.ranges.end(); ++itr) { 969233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineBasicBlock *mbb2 = 970233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames indexes_->getMBBCoveringRange(itr->start, itr->end); 971233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 972233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (mbb2 != mbb) 97381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 97481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 975233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 97681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return true; 97781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 97881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 979d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 980d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// interval on to-be re-materialized operands of MI) with new register. 981d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengvoid LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 982d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI, unsigned NewVReg, 983d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm) { 984d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // There is an implicit use. That means one of the other operand is 985d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // being remat'ed and the remat'ed instruction has li.reg as an 986d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // use operand. Make sure we rewrite that as well. 987d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 988d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 989d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg()) 990d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 991d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 992d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 993d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 994d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!vrm.isReMaterialized(Reg)) 995d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 996d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 9976130f66eaae89f8878590796977678afa8448926Evan Cheng MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 9986130f66eaae89f8878590796977678afa8448926Evan Cheng if (UseMO) 9996130f66eaae89f8878590796977678afa8448926Evan Cheng UseMO->setReg(NewVReg); 1000d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1001d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1002d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 1003f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 1004f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 1005018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals:: 1006d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan ChengrewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 1007233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool TrySplit, SlotIndex index, SlotIndex end, 10088651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineInstr *MI, 100981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1010f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1011f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1012d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1013f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1014f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 101522f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 1016313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 1017289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> &MBBVRegsMap, 1018c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1019018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool CanFold = false; 1020f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RestartInstruction: 1021f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1022f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineOperand& mop = MI->getOperand(i); 1023d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!mop.isReg()) 1024f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1025f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Reg = mop.getReg(); 1026f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned RegI = Reg; 10276f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1028f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1029f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (Reg != li.reg) 1030f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1031f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1032f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool TryFold = !DefIsReMat; 1033cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng bool FoldSS = true; // Default behavior unless it's a remat. 1034f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int FoldSlot = Slot; 1035f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIsReMat) { 1036f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If this is the rematerializable definition MI itself and 1037f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // all of its uses are rematerialized, simply delete it. 103881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MI == ReMatOrigDefMI && CanDelete) { 10398e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << "\t\t\t\tErasing re-materlizable def: " 10408e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << MI << '\n'); 1041f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RemoveMachineInstrFromMaps(MI); 1042cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng vrm.RemoveMachineInstrFromMaps(MI); 1043f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI->eraseFromParent(); 1044f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng break; 1045f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1046f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1047f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If def for this use can't be rematerialized, then try folding. 10480cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If def is rematerializable and it's a load, also try folding. 1049cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 1050f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (isLoad) { 1051f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Try fold loads (from stack slot, constant pool, etc.) into uses. 1052f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSS = isLoadSS; 1053f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSlot = LdSlot; 1054f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1055f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1056f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1057f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Scan all of the operands of this instruction rewriting operands 1058f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // to use NewVReg instead of li.reg as appropriate. We do this for 1059f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // two reasons: 1060f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1061f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1. If the instr reads the same spilled vreg multiple times, we 1062f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // want to reuse the NewVReg. 1063f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 2. If the instr is a two-addr instruction, we are required to 1064f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // keep the src/dst regs pinned. 1065f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1066f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Keep track of whether we replace a use and/or def so that we can 1067f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create the spill interval with the appropriate range. 1068cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 106981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasUse = mop.isUse(); 107081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasDef = mop.isDef(); 1071aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 1072aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(i); 1073f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 1074aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng const MachineOperand &MOj = MI->getOperand(j); 1075d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MOj.isReg()) 1076f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1077aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned RegJ = MOj.getReg(); 10786f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 1079f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1080f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (RegJ == RegI) { 1081aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1082d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (!MOj.isUndef()) { 1083d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng HasUse |= MOj.isUse(); 1084d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng HasDef |= MOj.isDef(); 1085d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng } 1086f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1087f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1088f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 108926b86a0b5676253040dc206b437536a24306fb76David Greene // Create a new virtual register for the spill interval. 109026b86a0b5676253040dc206b437536a24306fb76David Greene // Create the new register now so we can map the fold instruction 109126b86a0b5676253040dc206b437536a24306fb76David Greene // to the new register so when it is unfolded we get the correct 109226b86a0b5676253040dc206b437536a24306fb76David Greene // answer. 109326b86a0b5676253040dc206b437536a24306fb76David Greene bool CreatedNewVReg = false; 109426b86a0b5676253040dc206b437536a24306fb76David Greene if (NewVReg == 0) { 109526b86a0b5676253040dc206b437536a24306fb76David Greene NewVReg = mri_->createVirtualRegister(rc); 109626b86a0b5676253040dc206b437536a24306fb76David Greene vrm.grow(); 109726b86a0b5676253040dc206b437536a24306fb76David Greene CreatedNewVReg = true; 109826b86a0b5676253040dc206b437536a24306fb76David Greene } 109926b86a0b5676253040dc206b437536a24306fb76David Greene 11009c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!TryFold) 11019c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanFold = false; 11029c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng else { 1103018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Do not fold load / store here if we are splitting. We'll find an 1104018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // optimal point to insert a load / store later. 1105018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (!TrySplit) { 1106018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 110726b86a0b5676253040dc206b437536a24306fb76David Greene Ops, FoldSS, FoldSlot, NewVReg)) { 1108018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Folding the load/store can completely change the instruction in 1109018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // unpredictable ways, rescan it from the beginning. 111026b86a0b5676253040dc206b437536a24306fb76David Greene 111126b86a0b5676253040dc206b437536a24306fb76David Greene if (FoldSS) { 111226b86a0b5676253040dc206b437536a24306fb76David Greene // We need to give the new vreg the same stack slot as the 111326b86a0b5676253040dc206b437536a24306fb76David Greene // spilled interval. 111426b86a0b5676253040dc206b437536a24306fb76David Greene vrm.assignVirt2StackSlot(NewVReg, FoldSlot); 111526b86a0b5676253040dc206b437536a24306fb76David Greene } 111626b86a0b5676253040dc206b437536a24306fb76David Greene 1117018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasUse = false; 1118018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasDef = false; 1119018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng CanFold = false; 1120c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng if (isNotInMIMap(MI)) 11217e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng break; 1122018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng goto RestartInstruction; 1123018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1124018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } else { 11259c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // We'll try to fold it later if it's profitable. 11263c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 1127018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 11289c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng } 1129cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1130cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mop.setReg(NewVReg); 1131d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mop.isImplicit()) 1132d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1133cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1134cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Reuse NewVReg for other reads. 1135d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 1136d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &mopj = MI->getOperand(Ops[j]); 1137d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng mopj.setReg(NewVReg); 1138d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mopj.isImplicit()) 1139d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1140d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1141cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 114281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 114381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (DefIsReMat) { 1144378445303b10b092a898a75131141a8259cff50bEvan Cheng vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI); 1145d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 114681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each valnum may have its own remat id. 1147d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 114881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 1149d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 115081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 115181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!CanDelete || (HasUse && HasDef)) { 115281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a two-addr instruction then its use operands are 115381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // rematerializable but its def is not. It should be assigned a 115481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // stack slot. 115581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 115681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1157f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1158f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1159f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1160cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng } else if (HasUse && HasDef && 1161cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1162cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // If this interval hasn't been assigned a stack slot (because earlier 1163cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // def is a deleted remat def), do it now. 1164cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng assert(Slot != VirtRegMap::NO_STACK_SLOT); 1165cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1166f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1167f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1168313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Add the 1169313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // register as an implicit use on the use MI. 1170313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (DefIsReMat && ImpUse) 1171313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1172313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 11735b69ebac857104770b1a751bf7a463fda4330a62Evan Cheng // Create a new register interval for this spill / remat. 1174f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 117581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 117681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng NewLIs.push_back(&nI); 11771953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 117881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (TrySplit) 117981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(NewVReg, li.reg); 118081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1181f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1182f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasUse) { 118381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 1184233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange LR(index.getLoadIndex(), index.getDefIndex(), 1185233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator)); 11868e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " +" << LR); 118781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 118881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 118981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Extend the split live interval to this def / use. 1190233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex End = index.getDefIndex(); 119181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 119281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getValNumInfo(nI.getNumValNums()-1)); 11938e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " +" << LR); 119481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 119581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1196f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1197f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasDef) { 1198233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange LR(index.getDefIndex(), index.getStoreIndex(), 1199233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator)); 12008e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " +" << LR); 1201f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.addRange(LR); 1202f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 120381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 12048e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 12058e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling errs() << "\t\t\t\tAdded new interval: "; 12068e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling nI.print(errs(), tri_); 12078e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling errs() << '\n'; 12088e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 1209f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1210018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng return CanFold; 1211f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 121281a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 12130cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng const VNInfo *VNI, 12148651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineBasicBlock *MBB, 1215233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Idx) const { 1216233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex End = getMBBEndIdx(MBB); 12170cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 1218233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (VNI->kills[j].isPHI()) 1219ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames continue; 1220ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 1221233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex KillIdx = VNI->kills[j]; 12220cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (KillIdx > Idx && KillIdx < End) 12230cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng return true; 122481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 122581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 122681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 122781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1228063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// RewriteInfo - Keep track of machine instrs that will be rewritten 1229063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// during spilling. 1230844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 1231844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfo { 1232233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index; 1233844731a7f1909f55935e3514c9e713a62d67662eDan Gohman MachineInstr *MI; 1234844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasUse; 1235844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasDef; 1236233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames RewriteInfo(SlotIndex i, MachineInstr *mi, bool u, bool d) 1237844731a7f1909f55935e3514c9e713a62d67662eDan Gohman : Index(i), MI(mi), HasUse(u), HasDef(d) {} 1238844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1239844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1240844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfoCompare { 1241844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1242844731a7f1909f55935e3514c9e713a62d67662eDan Gohman return LHS.Index < RHS.Index; 1243844731a7f1909f55935e3514c9e713a62d67662eDan Gohman } 1244844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1245844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} 1246063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1247f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengvoid LiveIntervals:: 124881a038218171860ee4c382849c647d3dc841fe8bEvan ChengrewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1249f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval::Ranges::const_iterator &I, 125081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1251f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1252f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1253d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1254f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1255f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 125622f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 125781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &SpillMBBs, 1258289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes, 12590cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector &RestoreMBBs, 1260289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes, 1261289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> &MBBVRegsMap, 1262c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1263018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool AllCanFold = true; 126481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned NewVReg = 0; 1265233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = I->start.getBaseIndex(); 1266233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); 1267f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1268063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // First collect all the def / use in this live range that will be rewritten. 12697e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Make sure they are sorted according to instruction index. 1270063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::vector<RewriteInfo> RewriteMIs; 1271d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1272d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->reg_end(); ri != re; ) { 1273419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1274063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineOperand &O = ri.getOperand(); 1275063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++ri; 127624d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); 1277233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = getInstructionIndex(MI); 1278063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng if (index < start || index >= end) 1279063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng continue; 1280d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 1281d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (O.isUndef()) 128279a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // Must be defined by an implicit def. It should not be spilled. Note, 128379a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // this is for correctness reason. e.g. 128479a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 8 %reg1024<def> = IMPLICIT_DEF 128579a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 128679a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // The live range [12, 14) are not part of the r1024 live interval since 128779a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // it's defined by an implicit def. It will not conflicts with live 128879a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // interval of r1025. Now suppose both registers are spilled, you can 1289b9890ae3c35ad7d8e49261650d5b98f49f97a705Evan Cheng // easily see a situation where both registers are reloaded before 129079a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // the INSERT_SUBREG and both target registers that would overlap. 129179a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng continue; 1292063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 1293063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 1294063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1295063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1296313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 1297063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // Now rewrite the defs and uses. 1298063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 1299063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteInfo &rwi = RewriteMIs[i]; 1300063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1301233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = rwi.Index; 1302063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasUse = rwi.HasUse; 1303063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasDef = rwi.HasDef; 1304063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineInstr *MI = rwi.MI; 1305063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // If MI def and/or use the same register multiple times, then there 1306063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // are multiple entries. 1307313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned NumUses = MIHasUse; 1308063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng while (i != e && RewriteMIs[i].MI == MI) { 1309063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng assert(RewriteMIs[i].Index == index); 1310313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng bool isUse = RewriteMIs[i].HasUse; 1311313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (isUse) ++NumUses; 1312313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MIHasUse |= isUse; 1313063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MIHasDef |= RewriteMIs[i].HasDef; 1314063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1315063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 131681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1317313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 13180a891ed7d5875a9ccdb93b4472b0f43947d8289bEvan Cheng if (ImpUse && MI != ReMatDefMI) { 1319313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Update the 132024d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // register interval's spill weight to HUGE_VALF to prevent it from 132124d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // being spilled. 1322313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 132324d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng ImpLi.weight = HUGE_VALF; 1324313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng } 1325313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1326063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned MBBId = MBB->getNumber(); 1327018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng unsigned ThisVReg = 0; 132870306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (TrySplit) { 1329289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId); 13301953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NVI != MBBVRegsMap.end()) { 1331018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = NVI->second; 13321953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // One common case: 13331953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // x = use 13341953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 13351953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 13361953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // def = ... 13371953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // = use 13381953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // It's better to start a new interval to avoid artifically 13391953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // extend the new interval. 13401953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (MIHasDef && !MIHasUse) { 13411953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.erase(MBB->getNumber()); 1342018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = 0; 13431953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 13441953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 1345cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng } 1346018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1347018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool IsNew = ThisVReg == 0; 1348018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (IsNew) { 1349018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // This ends the previous live interval. If all of its def / use 1350018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // can be folded, give it a low spill weight. 1351018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1352018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1353018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1354018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1355018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold = true; 1356018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1357018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng NewVReg = ThisVReg; 1358018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 135981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasDef = false; 136081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasUse = false; 1361d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 13629c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng index, end, MI, ReMatOrigDefMI, ReMatDefMI, 13639c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 13649c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 1365c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); 136681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!HasDef && !HasUse) 136781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 136881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1369018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold &= CanFold; 1370018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 137181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Update weight of spill interval. 137281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 137370306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (!TrySplit) { 137481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // The spill weight is now infinity as it cannot be spilled again. 137581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.weight = HUGE_VALF; 13760cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 13770cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 13780cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 13790cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Keep track of the last def and first use in each MBB. 13800cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasDef) { 13810cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MI != ReMatOrigDefMI || !CanDelete) { 13820cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool HasKill = false; 13830cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasUse) 1384233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, index.getDefIndex()); 13850cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else { 13861953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // If this is a two-address code, then this index starts a new VNInfo. 1387233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const VNInfo *VNI = li.findDefinedVNInfoForRegInt(index.getDefIndex()); 13880cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VNI) 1389233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, index.getDefIndex()); 139081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1391289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 1392e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.find(MBBId); 13930cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasKill) { 13941953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII == SpillIdxes.end()) { 13951953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> S; 13961953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng S.push_back(SRInfo(index, NewVReg, true)); 13971953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SpillIdxes.insert(std::make_pair(MBBId, S)); 13981953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if (SII->second.back().vreg != NewVReg) { 13991953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.push_back(SRInfo(index, NewVReg, true)); 14008651125d2885f74546b6e2a556082111d5b75da3Lang Hames } else if (index > SII->second.back().index) { 14010cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If there is an earlier def and this is a two-address 14020cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // instruction, then it's not possible to fold the store (which 14030cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // would also fold the load). 14041953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SRInfo &Info = SII->second.back(); 14051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.index = index; 14061953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.canFold = !HasUse; 140781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 14080cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs.set(MBBId); 1409e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } else if (SII != SpillIdxes.end() && 1410e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.back().vreg == NewVReg && 14118651125d2885f74546b6e2a556082111d5b75da3Lang Hames index > SII->second.back().index) { 1412e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // There is an earlier def that's not killed (must be two-address). 1413e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // The spill is no longer needed. 1414e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.pop_back(); 1415e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng if (SII->second.empty()) { 1416e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.erase(MBBId); 1417e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillMBBs.reset(MBBId); 1418e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } 141981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 142081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 14210cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 142281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 14230cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasUse) { 1424289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 14250cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillIdxes.find(MBBId); 14261953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII != SpillIdxes.end() && 14271953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().vreg == NewVReg && 14288651125d2885f74546b6e2a556082111d5b75da3Lang Hames index > SII->second.back().index) 14290cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Use(s) following the last def, it's not safe to fold the spill. 14301953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().canFold = false; 1431289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator RII = 14320cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreIdxes.find(MBBId); 14331953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 14340cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If we are splitting live intervals, only fold if it's the first 14350cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // use and there isn't another use later in the MBB. 14361953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.back().canFold = false; 14370cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else if (IsNew) { 14380cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Only need a reload if there isn't an earlier def / use. 14391953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII == RestoreIdxes.end()) { 14401953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> Infos; 14411953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Infos.push_back(SRInfo(index, NewVReg, true)); 14421953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 14431953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else { 14441953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.push_back(SRInfo(index, NewVReg, true)); 14451953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 14460cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreMBBs.set(MBBId); 14470cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 144881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 14490cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 14500cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Update spill weight. 145122f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 1452c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1453f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1454018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1455018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1456018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // If all of its def / use can be folded, give it a low spill weight. 1457018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1458018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1459018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1460f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1461f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1462233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesbool LiveIntervals::alsoFoldARestore(int Id, SlotIndex index, 14638651125d2885f74546b6e2a556082111d5b75da3Lang Hames unsigned vr, BitVector &RestoreMBBs, 1464289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 14651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 14661953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 14671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 14681953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 14691953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && 14701953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].vreg == vr && 14711953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].canFold) 14721953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return true; 14731953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 14741953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 14751953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1476233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveIntervals::eraseRestoreInfo(int Id, SlotIndex index, 14778651125d2885f74546b6e2a556082111d5b75da3Lang Hames unsigned vr, BitVector &RestoreMBBs, 1478289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 14791953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 14801953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return; 14811953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 14821953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 14831953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && Restores[i].vreg) 1484233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames Restores[i].index = SlotIndex(); 14851953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 148681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 14874cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 14884cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// spilled and create empty intervals for their uses. 14894cce6b4c7882ef0cc993d931b90bf33985c96110Evan Chengvoid 14904cce6b4c7882ef0cc993d931b90bf33985c96110Evan ChengLiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 14914cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng const TargetRegisterClass* rc, 14924cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1493419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1494419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng re = mri_->reg_end(); ri != re; ) { 14954cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &O = ri.getOperand(); 1496419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1497419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng ++ri; 14984cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng if (O.isDef()) { 14994cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF && 15004cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng "Register def was not rewritten?"); 15014cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng RemoveMachineInstrFromMaps(MI); 15024cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 15034cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MI->eraseFromParent(); 15044cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } else { 15054cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // This must be an use of an implicit_def so it's not part of the live 15064cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // interval. Create a new empty live interval for it. 15074cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // FIXME: Can we simply erase some of the instructions? e.g. Stores? 15084cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng unsigned NewVReg = mri_->createVirtualRegister(rc); 15094cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.grow(); 15104cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.setIsImplicitlyDefined(NewVReg); 15114cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng NewLIs.push_back(&getOrCreateInterval(NewVReg)); 15124cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 15134cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &MO = MI->getOperand(i); 15144784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng if (MO.isReg() && MO.getReg() == li.reg) { 15154cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MO.setReg(NewVReg); 15164784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng MO.setIsUndef(); 15174784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng } 15184cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 15194cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 1520419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 1521419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng} 1522419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 1523f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengstd::vector<LiveInterval*> LiveIntervals:: 1524d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen AndersonaddIntervalsForSpillsFast(const LiveInterval &li, 1525d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson const MachineLoopInfo *loopInfo, 1526c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng VirtRegMap &vrm) { 15271719731d3d8ab6a986d67912f35daaad4f6910dbOwen Anderson unsigned slot = vrm.assignVirt2StackSlot(li.reg); 1528d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1529d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson std::vector<LiveInterval*> added; 1530d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1531d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson assert(li.weight != HUGE_VALF && 1532d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson "attempt to spill already spilled interval!"); 1533d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 15348e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 15358e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling errs() << "\t\t\t\tadding intervals for spills for interval: "; 15368e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling li.dump(); 15378e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling errs() << '\n'; 15388e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 1539d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1540d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1541d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1542a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg); 1543a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson while (RI != mri_->reg_end()) { 1544a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MachineInstr* MI = &*RI; 15458dc2cbe793ff577f69c17426d6dfaef94ad69191Owen Anderson 1546a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson SmallVector<unsigned, 2> Indices; 1547a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson bool HasUse = false; 1548a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson bool HasDef = false; 15498dc2cbe793ff577f69c17426d6dfaef94ad69191Owen Anderson 1550a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1551a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MachineOperand& mop = MI->getOperand(i); 1552d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!mop.isReg() || mop.getReg() != li.reg) continue; 1553a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1554a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson HasUse |= MI->getOperand(i).isUse(); 1555a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson HasDef |= MI->getOperand(i).isDef(); 1556a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1557a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson Indices.push_back(i); 1558d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 15591719731d3d8ab6a986d67912f35daaad4f6910dbOwen Anderson 1560a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI), 1561a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson Indices, true, slot, li.reg)) { 1562a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson unsigned NewVReg = mri_->createVirtualRegister(rc); 1563a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.grow(); 1564a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.assignVirt2StackSlot(NewVReg, slot); 1565a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1566a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // create a new register for this spill 1567a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson LiveInterval &nI = getOrCreateInterval(NewVReg); 1568a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1569a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // the spill weight is now infinity as it 1570a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // cannot be spilled again 1571a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson nI.weight = HUGE_VALF; 1572a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1573a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // Rewrite register operands to use the new vreg. 1574a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson for (SmallVectorImpl<unsigned>::iterator I = Indices.begin(), 1575a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson E = Indices.end(); I != E; ++I) { 1576a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MI->getOperand(*I).setReg(NewVReg); 1577a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1578a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (MI->getOperand(*I).isUse()) 1579a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MI->getOperand(*I).setIsKill(true); 1580a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 1581a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1582a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // Fill in the new live interval. 1583233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = getInstructionIndex(MI); 1584a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (HasUse) { 1585233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange LR(index.getLoadIndex(), index.getUseIndex(), 1586233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.getNextValue(SlotIndex(), 0, false, 15878651125d2885f74546b6e2a556082111d5b75da3Lang Hames getVNInfoAllocator())); 15888e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " +" << LR); 1589a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson nI.addRange(LR); 1590a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.addRestorePoint(NewVReg, MI); 1591a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 1592a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (HasDef) { 1593233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange LR(index.getDefIndex(), index.getStoreIndex(), 1594233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.getNextValue(SlotIndex(), 0, false, 15958651125d2885f74546b6e2a556082111d5b75da3Lang Hames getVNInfoAllocator())); 15968e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG(errs() << " +" << LR); 1597a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson nI.addRange(LR); 1598a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.addSpillPoint(NewVReg, true, MI); 1599a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 1600a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 16011719731d3d8ab6a986d67912f35daaad4f6910dbOwen Anderson added.push_back(&nI); 16028dc2cbe793ff577f69c17426d6dfaef94ad69191Owen Anderson 16038e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 16048e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling errs() << "\t\t\t\tadded new interval: "; 16058e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling nI.dump(); 16068e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling errs() << '\n'; 16078e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 1608a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 16099a032931453209505f6765a35be108ae5ea39b3bOwen Anderson 16109a032931453209505f6765a35be108ae5ea39b3bOwen Anderson 1611a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson RI = mri_->reg_begin(li.reg); 1612d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 1613d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1614d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson return added; 1615d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson} 1616d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1617d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Andersonstd::vector<LiveInterval*> LiveIntervals:: 161881a038218171860ee4c382849c647d3dc841fe8bEvan ChengaddIntervalsForSpills(const LiveInterval &li, 1619dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng SmallVectorImpl<LiveInterval*> &SpillIs, 1620c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { 1621ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson 1622ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson if (EnableFastSpilling) 1623c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng return addIntervalsForSpillsFast(li, loopInfo, vrm); 1624ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson 1625f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng assert(li.weight != HUGE_VALF && 1626f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng "attempt to spill already spilled interval!"); 1627f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 16288e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 16298e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling errs() << "\t\t\t\tadding intervals for spills for interval: "; 16308e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling li.print(errs(), tri_); 16318e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling errs() << '\n'; 16328e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 1633f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 163472eeb94fe1d69cd05bdbbe86b2bc9fa25c963c22Evan Cheng // Each bit specify whether a spill is required in the MBB. 163581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector SpillMBBs(mf_->getNumBlockIDs()); 1636289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes; 16370cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector RestoreMBBs(mf_->getNumBlockIDs()); 1638289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes; 1639289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> MBBVRegsMap; 1640f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> NewLIs; 1641d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1642f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1643f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned NumValNums = li.getNumValNums(); 1644f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatDefs; 1645f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDefs.resize(NumValNums, NULL); 1646f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1647f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatOrigDefs.resize(NumValNums, NULL); 1648f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> ReMatIds; 1649f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1650f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng BitVector ReMatDelete(NumValNums); 1651f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1652f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 165381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Spilling a split live interval. It cannot be split any further. Also, 165481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // it's also guaranteed to be a single val# / range interval. 165581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (vrm.getPreSplitReg(li.reg)) { 165681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(li.reg, 0); 1657d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng // Unset the split kill marker on the last use. 1658233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex KillIdx = vrm.getKillPoint(li.reg); 1659233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (KillIdx != SlotIndex()) { 1660d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1661d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillMI && "Last use disappeared?"); 1662d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1663d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillOp != -1 && "Last use disappeared?"); 1664f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner KillMI->getOperand(KillOp).setIsKill(false); 1665d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng } 1666adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng vrm.removeKillPoint(li.reg); 166781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = vrm.isReMaterialized(li.reg); 166881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot = vrm.getStackSlot(li.reg); 166981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng assert(Slot != VirtRegMap::MAX_STACK_SLOT); 167081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = DefIsReMat ? 167181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.getReMaterializedMI(li.reg) : NULL; 167281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int LdSlot = 0; 167381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 167481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoad = isLoadSS || 167515511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad())); 167681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool IsFirstRange = true; 167781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 167881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 167981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a split live interval with multiple ranges, it means there 168081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // are two-address instructions that re-defined the value. Only the 168181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // first def can be rematerialized! 168281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (IsFirstRange) { 1683cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // Note ReMatOrigDefMI has already been deleted. 168481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 168581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1686d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 16870cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1688c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 168981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 169081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, 0, 169181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, 0, false, false, false, 1692d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 16930cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1694c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 169581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 169681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng IsFirstRange = false; 169781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1698419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 16994cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 170081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return NewLIs; 170181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 170281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1703752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng bool TrySplit = !intervalIsInOneMBB(li); 17040cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (TrySplit) 17050cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numSplits; 1706f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool NeedStackSlot = false; 1707f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1708f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng i != e; ++i) { 1709f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const VNInfo *VNI = *i; 1710f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned VN = VNI->id; 1711857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->isUnused()) 1712f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; // Dead val#. 1713f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Is the def for the val# rematerializable? 1714857c4e01f85601cf2084adb860616256ee47c177Lang Hames MachineInstr *ReMatDefMI = VNI->isDefAccurate() 1715857c4e01f85601cf2084adb860616256ee47c177Lang Hames ? getInstructionFromIndex(VNI->def) : 0; 17165ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool dummy; 1717dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) { 1718f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Remember how to remat the def of this val#. 171981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReMatOrigDefs[VN] = ReMatDefMI; 17202c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman // Original def may be modified so we have to make a copy here. 17211ed9922794cda9dbe295e74674b909287e544632Evan Cheng MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI); 1722752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng CloneMIs.push_back(Clone); 17231ed9922794cda9dbe295e74674b909287e544632Evan Cheng ReMatDefs[VN] = Clone; 1724f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1725f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = true; 1726857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->hasPHIKill()) { 1727c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // A kill is a phi node, not all of its uses can be rematerialized. 1728f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // It must not be deleted. 1729c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng CanDelete = false; 1730c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // Need a stack slot if there is any live range where uses cannot be 1731c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // rematerialized. 1732c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng NeedStackSlot = true; 1733f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1734f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (CanDelete) 1735f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDelete.set(VN); 1736f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1737f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Need a stack slot if there is any live range where uses cannot be 1738f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // rematerialized. 1739f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng NeedStackSlot = true; 1740f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1741f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1742f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1743f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // One stack slot per live interval. 1744b98bbb7597495fb401b020679a94389298175506Owen Anderson if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) { 1745b98bbb7597495fb401b020679a94389298175506Owen Anderson if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT) 1746b98bbb7597495fb401b020679a94389298175506Owen Anderson Slot = vrm.assignVirt2StackSlot(li.reg); 1747b98bbb7597495fb401b020679a94389298175506Owen Anderson 1748b98bbb7597495fb401b020679a94389298175506Owen Anderson // This case only occurs when the prealloc splitter has already assigned 1749b98bbb7597495fb401b020679a94389298175506Owen Anderson // a stack slot to this vreg. 1750b98bbb7597495fb401b020679a94389298175506Owen Anderson else 1751b98bbb7597495fb401b020679a94389298175506Owen Anderson Slot = vrm.getStackSlot(li.reg); 1752b98bbb7597495fb401b020679a94389298175506Owen Anderson } 1753f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1754f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Create new intervals and rewrite defs and uses. 1755f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::Ranges::const_iterator 1756f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 175781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 175881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 175981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = ReMatDefMI != NULL; 1760f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = ReMatDelete[I->valno->id]; 1761f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int LdSlot = 0; 176281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1763f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad = isLoadSS || 176415511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad()); 176581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 17660cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1767d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, 17680cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1769c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 1770f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1771f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 17720cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Insert spills / restores if we are splitting. 1773419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng if (!TrySplit) { 17744cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 17751953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return NewLIs; 1776419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 17771953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1778b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng SmallPtrSet<LiveInterval*, 4> AddedKill; 1779aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 17801953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NeedStackSlot) { 17811953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = SpillMBBs.find_first(); 17821953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 17831953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &spills = SpillIdxes[Id]; 17841953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = spills.size(); i != e; ++i) { 1785233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = spills[i].index; 17861953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = spills[i].vreg; 1787597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 17880cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 17890cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1790aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1791aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool FoundUse = false; 1792aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1793cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (spills[i].canFold) { 1794aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 17950cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 17960cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineOperand &MO = MI->getOperand(j); 1797d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || MO.getReg() != VReg) 17980cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 1799aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 1800aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1801aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (MO.isDef()) 1802cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng continue; 1803aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (isReMat || 1804aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng (!FoundUse && !alsoFoldARestore(Id, index, VReg, 1805aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng RestoreMBBs, RestoreIdxes))) { 1806aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // MI has two-address uses of the same register. If the use 1807aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // isn't the first and only use in the BB, then we can't fold 1808aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // it. FIXME: Move this to rewriteInstructionsForSpills. 1809aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 1810cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng break; 1811cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 1812aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoundUse = true; 18130cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 18140cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 18150cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the store into the def if possible. 1816cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1817aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 1818aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 1819cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng Folded = true; 182048fe63526e35ddaee7e98879596a569911f41319Sebastian Redl if (FoundUse) { 1821aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Also folded uses, do not issue a load. 1822aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 1823233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.removeRange(index.getLoadIndex(), index.getDefIndex()); 1824f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng } 1825233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.removeRange(index.getDefIndex(), index.getStoreIndex()); 1826cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 18270cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 18280cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 18297e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Otherwise tell the spiller to issue a spill. 1830b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!Folded) { 1831b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 1832233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool isKill = LR->end == index.getStoreIndex(); 1833b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng if (!MI->registerDefIsDead(nI.reg)) 1834b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng // No need to spill a dead def. 1835b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng vrm.addSpillPoint(VReg, isKill, MI); 1836b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (isKill) 1837b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng AddedKill.insert(&nI); 1838b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 18390cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 18401953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = SpillMBBs.find_next(Id); 18410cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 18421953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 18430cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 18441953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = RestoreMBBs.find_first(); 18451953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 18461953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &restores = RestoreIdxes[Id]; 18471953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = restores.size(); i != e; ++i) { 1848233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex index = restores[i].index; 1849233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (index == SlotIndex()) 18501953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng continue; 18511953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = restores[i].vreg; 1852597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 18539c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 185481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1855aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1856aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1857cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (restores[i].canFold) { 1858aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 185981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 186081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineOperand &MO = MI->getOperand(j); 1861d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || MO.getReg() != VReg) 186281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 1863aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 18640cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MO.isDef()) { 1865aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // If this restore were to be folded, it would have been folded 1866aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // already. 1867aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 186881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng break; 186981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1870aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 187181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 187281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 18730cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 18740cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the load into the use if possible. 1875cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1876aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 18779c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!isReMat) 1878aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 1879aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 18800cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 18810cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng int LdSlot = 0; 18820cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 18830cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If the rematerializable def is a load, also try to fold it. 188415511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad()) 1885aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1886aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops, isLoadSS, LdSlot, VReg); 1887650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng if (!Folded) { 1888650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 1889650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng if (ImpUse) { 1890650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng // Re-matting an instruction with virtual register use. Add the 1891650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng // register as an implicit use on the use MI and update the register 1892650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng // interval's spill weight to HUGE_VALF to prevent it from being 1893650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng // spilled. 1894650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 1895650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng ImpLi.weight = HUGE_VALF; 1896650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1897650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng } 1898d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1899aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 19000cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 19010cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If folding is not possible / failed, then tell the spiller to issue a 19020cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // load / rematerialization for us. 1903597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (Folded) 1904233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames nI.removeRange(index.getLoadIndex(), index.getDefIndex()); 1905b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng else 19060cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.addRestorePoint(VReg, MI); 190781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 19081953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = RestoreMBBs.find_next(Id); 190981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 191081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1911b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // Finalize intervals: add kills, finalize spill weights, and filter out 1912b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // dead intervals. 1913597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng std::vector<LiveInterval*> RetNewLIs; 1914597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 1915597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval *LI = NewLIs[i]; 1916597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (!LI->empty()) { 1917233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LI->weight /= SlotIndex::NUM * getApproximateInstructionCount(*LI); 1918b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!AddedKill.count(LI)) { 1919b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 1920233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex LastUseIdx = LR->end.getBaseIndex(); 1921d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 19226130f66eaae89f8878590796977678afa8448926Evan Cheng int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 1923b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng assert(UseIdx != -1); 1924a24752ff43dc1ad8c18c5d9e78549c45f62b980eEvan Cheng if (!LastUse->isRegTiedToDefOperand(UseIdx)) { 1925b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LastUse->getOperand(UseIdx).setIsKill(); 1926d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng vrm.addKillPoint(LI->reg, LastUseIdx); 1927adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng } 1928b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 1929597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng RetNewLIs.push_back(LI); 1930597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 1931597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 193281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 19334cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 1934597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng return RetNewLIs; 1935f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1936676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1937676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// hasAllocatableSuperReg - Return true if the specified physical register has 1938676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// any super register that's allocatable. 1939676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengbool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 1940676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 1941676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (allocatableRegs_[*AS] && hasInterval(*AS)) 1942676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return true; 1943676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return false; 1944676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1945676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1946676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getRepresentativeReg - Find the largest super register of the specified 1947676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// physical register. 1948676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 1949676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // Find the largest super-register that is allocatable. 1950676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned BestReg = Reg; 1951676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 1952676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SuperReg = *AS; 1953676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 1954676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng BestReg = SuperReg; 1955676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng break; 1956676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1957676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1958676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return BestReg; 1959676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1960676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1961676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getNumConflictsWithPhysReg - Return the number of uses and defs of the 1962676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// specified interval that conflicts with the specified physical register. 1963676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 1964676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg) const { 1965676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned NumConflicts = 0; 1966676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 1967676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 1968676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 1969676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 1970676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 1971233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index = getInstructionIndex(MI); 1972676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) 1973676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng ++NumConflicts; 1974676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1975676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return NumConflicts; 1976676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1977676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1978676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// spillPhysRegAroundRegDefsUses - Spill the specified physical register 19792824a655509577127d221eecd1425de196f80320Evan Cheng/// around all defs and uses of the specified interval. Return true if it 19802824a655509577127d221eecd1425de196f80320Evan Cheng/// was able to cut its interval. 19812824a655509577127d221eecd1425de196f80320Evan Chengbool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 1982676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg, VirtRegMap &vrm) { 1983676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SpillReg = getRepresentativeReg(PhysReg); 1984676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1985676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 1986676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // If there are registers which alias PhysReg, but which are not a 1987676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // sub-register of the chosen representative super register. Assert 1988676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // since we can't handle it yet. 198970f2f65aacdbc96fe158b2860b5f0bad075ee548Dan Gohman assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) || 1990676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng tri_->isSuperRegister(*AS, SpillReg)); 1991676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 19922824a655509577127d221eecd1425de196f80320Evan Cheng bool Cut = false; 19930222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng SmallVector<unsigned, 4> PRegs; 19940222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng if (hasInterval(SpillReg)) 19950222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng PRegs.push_back(SpillReg); 19960222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng else { 19970222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng SmallSet<unsigned, 4> Added; 19980222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) 19990222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng if (Added.insert(*AS) && hasInterval(*AS)) { 20000222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng PRegs.push_back(*AS); 20010222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng for (const unsigned* ASS = tri_->getSubRegisters(*AS); *ASS; ++ASS) 20020222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng Added.insert(*ASS); 20030222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng } 20040222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng } 20050222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng 2006676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SmallPtrSet<MachineInstr*, 8> SeenMIs; 2007676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2008676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 2009676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 2010676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 2011676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (SeenMIs.count(MI)) 2012676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 2013676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SeenMIs.insert(MI); 2014233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Index = getInstructionIndex(MI); 20150222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng for (unsigned i = 0, e = PRegs.size(); i != e; ++i) { 20160222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng unsigned PReg = PRegs[i]; 20170222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng LiveInterval &pli = getInterval(PReg); 20180222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng if (!pli.liveAt(Index)) 20190222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng continue; 20200222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng vrm.addEmergencySpill(PReg, MI); 2021233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex StartIdx = Index.getLoadIndex(); 2022233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex EndIdx = Index.getNextIndex().getBaseIndex(); 20232824a655509577127d221eecd1425de196f80320Evan Cheng if (pli.isInOneLiveRange(StartIdx, EndIdx)) { 20245a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng pli.removeRange(StartIdx, EndIdx); 20252824a655509577127d221eecd1425de196f80320Evan Cheng Cut = true; 20262824a655509577127d221eecd1425de196f80320Evan Cheng } else { 20277d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin std::string msg; 20287d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin raw_string_ostream Msg(msg); 20297d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin Msg << "Ran out of registers during register allocation!"; 20305a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng if (MI->getOpcode() == TargetInstrInfo::INLINEASM) { 20317d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin Msg << "\nPlease check your inline asm statement for invalid " 20320222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng << "constraints:\n"; 20337d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin MI->print(Msg, tm_); 20345a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng } 20357d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin llvm_report_error(Msg.str()); 20365a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng } 20370222a8cfb8f8f3f67e4a07164eb1ecf9c44e6f64Evan Cheng for (const unsigned* AS = tri_->getSubRegisters(PReg); *AS; ++AS) { 2038676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasInterval(*AS)) 2039676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 2040676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng LiveInterval &spli = getInterval(*AS); 2041676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (spli.liveAt(Index)) 2042233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames spli.removeRange(Index.getLoadIndex(), 2043233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames Index.getNextIndex().getBaseIndex()); 2044676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2045676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2046676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 20472824a655509577127d221eecd1425de196f80320Evan Cheng return Cut; 2048676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2049c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 2050c4dc132c8a787fc41b6a162121251234aa618965Owen AndersonLiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 2051ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames MachineInstr* startInst) { 2052c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveInterval& Interval = getOrCreateInterval(reg); 2053c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VNInfo* VN = Interval.getNextValue( 2054233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex(getInstructionIndex(startInst).getDefIndex()), 20558651125d2885f74546b6e2a556082111d5b75da3Lang Hames startInst, true, getVNInfoAllocator()); 2056857c4e01f85601cf2084adb860616256ee47c177Lang Hames VN->setHasPHIKill(true); 2057233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames VN->kills.push_back(indexes_->getTerminatorGap(startInst->getParent())); 20588651125d2885f74546b6e2a556082111d5b75da3Lang Hames LiveRange LR( 2059233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex(getInstructionIndex(startInst).getDefIndex()), 2060233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames getMBBEndIdx(startInst->getParent()).getNextIndex().getBaseIndex(), VN); 2061c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson Interval.addRange(LR); 2062c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 2063c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson return LR; 2064c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson} 2065b5257664795d49ada0d4669fe8ed1cd49c04fbf3David Greene 2066