LiveIntervalAnalysis.cpp revision 089efffd7d1ca0d10522ace38d36e0a67f4fac2d
11176bdada62cabc6ec4b0308a930e83b679d5d36John Reck//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 21176bdada62cabc6ec4b0308a930e83b679d5d36John Reck// 31176bdada62cabc6ec4b0308a930e83b679d5d36John Reck// The LLVM Compiler Infrastructure 41176bdada62cabc6ec4b0308a930e83b679d5d36John Reck// 51176bdada62cabc6ec4b0308a930e83b679d5d36John Reck// This file is distributed under the University of Illinois Open Source 61176bdada62cabc6ec4b0308a930e83b679d5d36John Reck// License. See LICENSE.TXT for details. 71176bdada62cabc6ec4b0308a930e83b679d5d36John Reck// 81176bdada62cabc6ec4b0308a930e83b679d5d36John Reck//===----------------------------------------------------------------------===// 91176bdada62cabc6ec4b0308a930e83b679d5d36John Reck// 101176bdada62cabc6ec4b0308a930e83b679d5d36John Reck// This file implements the LiveInterval analysis pass which is used 111176bdada62cabc6ec4b0308a930e83b679d5d36John Reck// by the Linear Scan Register allocator. This pass linearizes the 121176bdada62cabc6ec4b0308a930e83b679d5d36John Reck// basic blocks of the function in DFS order and uses the 131176bdada62cabc6ec4b0308a930e83b679d5d36John Reck// LiveVariables pass to conservatively compute live intervals for 141176bdada62cabc6ec4b0308a930e83b679d5d36John Reck// each virtual and physical register. 151176bdada62cabc6ec4b0308a930e83b679d5d36John Reck// 161176bdada62cabc6ec4b0308a930e83b679d5d36John Reck//===----------------------------------------------------------------------===// 171176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 181176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#define DEBUG_TYPE "liveintervals" 191176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "llvm/CodeGen/LiveIntervalAnalysis.h" 201176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "VirtRegMap.h" 211176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "llvm/Value.h" 221176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "llvm/CodeGen/LiveVariables.h" 231176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "llvm/CodeGen/MachineFrameInfo.h" 241176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "llvm/CodeGen/MachineInstr.h" 251176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "llvm/CodeGen/MachineLoopInfo.h" 261176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "llvm/CodeGen/MachineRegisterInfo.h" 271176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "llvm/CodeGen/Passes.h" 281176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "llvm/Target/TargetRegisterInfo.h" 291176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "llvm/Target/TargetInstrInfo.h" 301176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "llvm/Target/TargetMachine.h" 311176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "llvm/Support/CommandLine.h" 321176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "llvm/Support/Debug.h" 331176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "llvm/ADT/Statistic.h" 341176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "llvm/ADT/STLExtras.h" 351176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include <algorithm> 361176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include <cmath> 371176bdada62cabc6ec4b0308a930e83b679d5d36John Reckusing namespace llvm; 381176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 391176bdada62cabc6ec4b0308a930e83b679d5d36John Reck// Hidden options for help debugging. 401176bdada62cabc6ec4b0308a930e83b679d5d36John Reckstatic cl::opt<bool> DisableReMat("disable-rematerialization", 411176bdada62cabc6ec4b0308a930e83b679d5d36John Reck cl::init(false), cl::Hidden); 421176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 431176bdada62cabc6ec4b0308a930e83b679d5d36John Reckstatic cl::opt<bool> SplitAtBB("split-intervals-at-bb", 441176bdada62cabc6ec4b0308a930e83b679d5d36John Reck cl::init(true), cl::Hidden); 451176bdada62cabc6ec4b0308a930e83b679d5d36John Reckstatic cl::opt<int> SplitLimit("split-limit", 461176bdada62cabc6ec4b0308a930e83b679d5d36John Reck cl::init(-1), cl::Hidden); 471176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 481176bdada62cabc6ec4b0308a930e83b679d5d36John ReckSTATISTIC(numIntervals, "Number of original intervals"); 491176bdada62cabc6ec4b0308a930e83b679d5d36John ReckSTATISTIC(numIntervalsAfter, "Number of intervals after coalescing"); 501176bdada62cabc6ec4b0308a930e83b679d5d36John ReckSTATISTIC(numFolds , "Number of loads/stores folded into instructions"); 511176bdada62cabc6ec4b0308a930e83b679d5d36John ReckSTATISTIC(numSplits , "Number of intervals split"); 521176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 531176bdada62cabc6ec4b0308a930e83b679d5d36John Reckchar LiveIntervals::ID = 0; 541176bdada62cabc6ec4b0308a930e83b679d5d36John Reckstatic RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 551176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 561176bdada62cabc6ec4b0308a930e83b679d5d36John Reckvoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 571176bdada62cabc6ec4b0308a930e83b679d5d36John Reck AU.addPreserved<LiveVariables>(); 581176bdada62cabc6ec4b0308a930e83b679d5d36John Reck AU.addRequired<LiveVariables>(); 591176bdada62cabc6ec4b0308a930e83b679d5d36John Reck AU.addPreservedID(MachineLoopInfoID); 601176bdada62cabc6ec4b0308a930e83b679d5d36John Reck AU.addPreservedID(MachineDominatorsID); 611176bdada62cabc6ec4b0308a930e83b679d5d36John Reck AU.addPreservedID(PHIEliminationID); 621176bdada62cabc6ec4b0308a930e83b679d5d36John Reck AU.addRequiredID(PHIEliminationID); 631176bdada62cabc6ec4b0308a930e83b679d5d36John Reck AU.addRequiredID(TwoAddressInstructionPassID); 641176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineFunctionPass::getAnalysisUsage(AU); 651176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 661176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 671176bdada62cabc6ec4b0308a930e83b679d5d36John Reckvoid LiveIntervals::releaseMemory() { 681176bdada62cabc6ec4b0308a930e83b679d5d36John Reck Idx2MBBMap.clear(); 691176bdada62cabc6ec4b0308a930e83b679d5d36John Reck mi2iMap_.clear(); 701176bdada62cabc6ec4b0308a930e83b679d5d36John Reck i2miMap_.clear(); 711176bdada62cabc6ec4b0308a930e83b679d5d36John Reck r2iMap_.clear(); 721176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 731176bdada62cabc6ec4b0308a930e83b679d5d36John Reck VNInfoAllocator.Reset(); 741176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i) 751176bdada62cabc6ec4b0308a930e83b679d5d36John Reck delete ClonedMIs[i]; 761176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 771176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 781176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// runOnMachineFunction - Register allocate the whole function 791176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// 801176bdada62cabc6ec4b0308a930e83b679d5d36John Reckbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 811176bdada62cabc6ec4b0308a930e83b679d5d36John Reck mf_ = &fn; 821176bdada62cabc6ec4b0308a930e83b679d5d36John Reck mri_ = &mf_->getRegInfo(); 831176bdada62cabc6ec4b0308a930e83b679d5d36John Reck tm_ = &fn.getTarget(); 841176bdada62cabc6ec4b0308a930e83b679d5d36John Reck tri_ = tm_->getRegisterInfo(); 851176bdada62cabc6ec4b0308a930e83b679d5d36John Reck tii_ = tm_->getInstrInfo(); 861176bdada62cabc6ec4b0308a930e83b679d5d36John Reck lv_ = &getAnalysis<LiveVariables>(); 871176bdada62cabc6ec4b0308a930e83b679d5d36John Reck allocatableRegs_ = tri_->getAllocatableSet(fn); 881176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 891176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Number MachineInstrs and MachineBasicBlocks. 901176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Initialize MBB indexes to a sentinal. 911176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U)); 921176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 931176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned MIIndex = 0; 941176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); 951176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MBB != E; ++MBB) { 961176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned StartIdx = MIIndex; 971176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 981176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 991176bdada62cabc6ec4b0308a930e83b679d5d36John Reck I != E; ++I) { 1001176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; 1011176bdada62cabc6ec4b0308a930e83b679d5d36John Reck assert(inserted && "multiple MachineInstr -> index mappings"); 1021176bdada62cabc6ec4b0308a930e83b679d5d36John Reck i2miMap_.push_back(I); 1031176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MIIndex += InstrSlots::NUM; 1041176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 1051176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1061176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Set the MBB2IdxMap entry for this MBB. 1071176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MBB2IdxMap[MBB->getNumber()] = (StartIdx == MIIndex) 1081176bdada62cabc6ec4b0308a930e83b679d5d36John Reck ? std::make_pair(StartIdx, StartIdx) // Empty MBB 1091176bdada62cabc6ec4b0308a930e83b679d5d36John Reck : std::make_pair(StartIdx, MIIndex - 1); 1101176bdada62cabc6ec4b0308a930e83b679d5d36John Reck Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); 1111176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 1121176bdada62cabc6ec4b0308a930e83b679d5d36John Reck std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); 1131176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1141176bdada62cabc6ec4b0308a930e83b679d5d36John Reck computeIntervals(); 1151176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1161176bdada62cabc6ec4b0308a930e83b679d5d36John Reck numIntervals += getNumIntervals(); 1171176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1181176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << "********** INTERVALS **********\n"; 1191176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (iterator I = begin(), E = end(); I != E; ++I) { 1201176bdada62cabc6ec4b0308a930e83b679d5d36John Reck I->second.print(DOUT, tri_); 1211176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << "\n"; 1221176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 1231176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1241176bdada62cabc6ec4b0308a930e83b679d5d36John Reck numIntervalsAfter += getNumIntervals(); 1251176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DEBUG(dump()); 1261176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return true; 1271176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 1281176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1291176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// print - Implement the dump method. 1301176bdada62cabc6ec4b0308a930e83b679d5d36John Reckvoid LiveIntervals::print(std::ostream &O, const Module* ) const { 1311176bdada62cabc6ec4b0308a930e83b679d5d36John Reck O << "********** INTERVALS **********\n"; 1321176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (const_iterator I = begin(), E = end(); I != E; ++I) { 1331176bdada62cabc6ec4b0308a930e83b679d5d36John Reck I->second.print(DOUT, tri_); 1341176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << "\n"; 1351176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 1361176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1371176bdada62cabc6ec4b0308a930e83b679d5d36John Reck O << "********** MACHINEINSTRS **********\n"; 1381176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 1391176bdada62cabc6ec4b0308a930e83b679d5d36John Reck mbbi != mbbe; ++mbbi) { 1401176bdada62cabc6ec4b0308a930e83b679d5d36John Reck O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 1411176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (MachineBasicBlock::iterator mii = mbbi->begin(), 1421176bdada62cabc6ec4b0308a930e83b679d5d36John Reck mie = mbbi->end(); mii != mie; ++mii) { 1431176bdada62cabc6ec4b0308a930e83b679d5d36John Reck O << getInstructionIndex(mii) << '\t' << *mii; 1441176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 1451176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 1461176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 1471176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1481176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// conflictsWithPhysRegDef - Returns true if the specified register 1491176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// is defined during the duration of the specified interval. 1501176bdada62cabc6ec4b0308a930e83b679d5d36John Reckbool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, 1511176bdada62cabc6ec4b0308a930e83b679d5d36John Reck VirtRegMap &vrm, unsigned reg) { 1521176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (LiveInterval::Ranges::const_iterator 1531176bdada62cabc6ec4b0308a930e83b679d5d36John Reck I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 1541176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (unsigned index = getBaseIndex(I->start), 1551176bdada62cabc6ec4b0308a930e83b679d5d36John Reck end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end; 1561176bdada62cabc6ec4b0308a930e83b679d5d36John Reck index += InstrSlots::NUM) { 1571176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // skip deleted instructions 1581176bdada62cabc6ec4b0308a930e83b679d5d36John Reck while (index != end && !getInstructionFromIndex(index)) 1591176bdada62cabc6ec4b0308a930e83b679d5d36John Reck index += InstrSlots::NUM; 1601176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (index == end) break; 1611176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1621176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *MI = getInstructionFromIndex(index); 1631176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned SrcReg, DstReg; 1641176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (tii_->isMoveInstr(*MI, SrcReg, DstReg)) 1651176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (SrcReg == li.reg || DstReg == li.reg) 1661176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 1671176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1681176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineOperand& mop = MI->getOperand(i); 1691176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (!mop.isRegister()) 1701176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 1711176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned PhysReg = mop.getReg(); 1721176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (PhysReg == 0 || PhysReg == li.reg) 1731176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 1741176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { 1751176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (!vrm.hasPhys(PhysReg)) 1761176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 1771176bdada62cabc6ec4b0308a930e83b679d5d36John Reck PhysReg = vrm.getPhys(PhysReg); 1781176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 1791176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (PhysReg && tri_->regsOverlap(PhysReg, reg)) 1801176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return true; 1811176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 1821176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 1831176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 1841176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1851176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return false; 1861176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 1871176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1881176bdada62cabc6ec4b0308a930e83b679d5d36John Reckvoid LiveIntervals::printRegName(unsigned reg) const { 1891176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (TargetRegisterInfo::isPhysicalRegister(reg)) 1901176bdada62cabc6ec4b0308a930e83b679d5d36John Reck cerr << tri_->getName(reg); 1911176bdada62cabc6ec4b0308a930e83b679d5d36John Reck else 1921176bdada62cabc6ec4b0308a930e83b679d5d36John Reck cerr << "%reg" << reg; 1931176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 1941176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1951176bdada62cabc6ec4b0308a930e83b679d5d36John Reckvoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 1961176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineBasicBlock::iterator mi, 1971176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned MIIdx, 1981176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveInterval &interval) { 1991176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 2001176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 2011176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 2021176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (mi->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 2031176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << "is a implicit_def\n"; 2041176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return; 2051176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 2061176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 2071176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Virtual registers may be defined multiple times (due to phi 2081176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // elimination and 2-addr elimination). Much of what we do only has to be 2091176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // done once for the vreg. We use an empty interval to detect the first 2101176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // time we see a vreg. 2111176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (interval.empty()) { 2121176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Get the Idx of the defining instructions. 2131176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned defIndex = getDefIndex(MIIdx); 2141176bdada62cabc6ec4b0308a930e83b679d5d36John Reck VNInfo *ValNo; 2151176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *CopyMI = NULL; 2161176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned SrcReg, DstReg; 2171176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 2181176bdada62cabc6ec4b0308a930e83b679d5d36John Reck mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 2191176bdada62cabc6ec4b0308a930e83b679d5d36John Reck tii_->isMoveInstr(*mi, SrcReg, DstReg)) 2201176bdada62cabc6ec4b0308a930e83b679d5d36John Reck CopyMI = mi; 2211176bdada62cabc6ec4b0308a930e83b679d5d36John Reck ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 2221176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 2231176bdada62cabc6ec4b0308a930e83b679d5d36John Reck assert(ValNo->id == 0 && "First value in interval is not 0?"); 2241176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 2251176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Loop over all of the blocks that the vreg is defined in. There are 2261176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // two cases we have to handle here. The most common case is a vreg 2271176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // whose lifetime is contained within a basic block. In this case there 2281176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // will be a single kill, in MBB, which comes after the definition. 2291176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 2301176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // FIXME: what about dead vars? 2311176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned killIdx; 2321176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (vi.Kills[0] != mi) 2331176bdada62cabc6ec4b0308a930e83b679d5d36John Reck killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 2341176bdada62cabc6ec4b0308a930e83b679d5d36John Reck else 2351176bdada62cabc6ec4b0308a930e83b679d5d36John Reck killIdx = defIndex+1; 2361176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 2371176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // If the kill happens after the definition, we have an intra-block 2381176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // live range. 2391176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (killIdx > defIndex) { 2401176bdada62cabc6ec4b0308a930e83b679d5d36John Reck assert(vi.AliveBlocks.none() && 2411176bdada62cabc6ec4b0308a930e83b679d5d36John Reck "Shouldn't be alive across any blocks!"); 2421176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveRange LR(defIndex, killIdx, ValNo); 2431176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addRange(LR); 2441176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " +" << LR << "\n"; 2451176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addKill(ValNo, killIdx); 2461176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return; 2471176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 2481176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 2491176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 2501176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // The other case we handle is when a virtual register lives to the end 2511176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // of the defining block, potentially live across some blocks, then is 2521176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // live into some number of blocks, but gets killed. Start by adding a 2531176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // range that goes from this definition to the end of the defining block. 2541176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveRange NewLR(defIndex, 2551176bdada62cabc6ec4b0308a930e83b679d5d36John Reck getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 2561176bdada62cabc6ec4b0308a930e83b679d5d36John Reck ValNo); 2571176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " +" << NewLR; 2581176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addRange(NewLR); 2591176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 2601176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Iterate over all of the blocks that the variable is completely 2611176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 2621176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // live interval. 2631176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 2641176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (vi.AliveBlocks[i]) { 2651176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineBasicBlock *MBB = mf_->getBlockNumbered(i); 2661176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (!MBB->empty()) { 2671176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveRange LR(getMBBStartIdx(i), 2681176bdada62cabc6ec4b0308a930e83b679d5d36John Reck getInstructionIndex(&MBB->back()) + InstrSlots::NUM, 2691176bdada62cabc6ec4b0308a930e83b679d5d36John Reck ValNo); 2701176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addRange(LR); 2711176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " +" << LR; 2721176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 2731176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 2741176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 2751176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 2761176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Finally, this virtual register is live from the start of any killing 2771176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // block to the 'use' slot of the killing instruction. 2781176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 2791176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *Kill = vi.Kills[i]; 2801176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1; 2811176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveRange LR(getMBBStartIdx(Kill->getParent()), 2821176bdada62cabc6ec4b0308a930e83b679d5d36John Reck killIdx, ValNo); 2831176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addRange(LR); 2841176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addKill(ValNo, killIdx); 2851176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " +" << LR; 2861176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 2871176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 2881176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } else { 2891176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // If this is the second time we see a virtual register definition, it 2901176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // must be due to phi elimination or two addr elimination. If this is 2911176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // the result of two address elimination, then the vreg is one of the 2921176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // def-and-use register operand. 2931176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (mi->isRegReDefinedByTwoAddr(interval.reg)) { 2941176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // If this is a two-address definition, then we have already processed 2951176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // the live range. The only problem is that we didn't realize there 2961176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // are actually two values in the live interval. Because of this we 2971176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // need to take the LiveRegion that defines this register and split it 2981176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // into two values. 2991176bdada62cabc6ec4b0308a930e83b679d5d36John Reck assert(interval.containsOneValue()); 3001176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def); 3011176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned RedefIndex = getDefIndex(MIIdx); 3021176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 3031176bdada62cabc6ec4b0308a930e83b679d5d36John Reck const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); 3041176bdada62cabc6ec4b0308a930e83b679d5d36John Reck VNInfo *OldValNo = OldLR->valno; 3051176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 3061176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Delete the initial value, which should be short and continuous, 3071176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // because the 2-addr copy must be in the same MBB as the redef. 3081176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.removeRange(DefIndex, RedefIndex); 3091176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 3101176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Two-address vregs should always only be redefined once. This means 3111176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // that at this point, there should be exactly one value number in it. 3121176bdada62cabc6ec4b0308a930e83b679d5d36John Reck assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 3131176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 3141176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // The new value number (#1) is defined by the instruction we claimed 3151176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // defined value #0. 3161176bdada62cabc6ec4b0308a930e83b679d5d36John Reck VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->copy, 3171176bdada62cabc6ec4b0308a930e83b679d5d36John Reck VNInfoAllocator); 3181176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 3191176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Value#0 is now defined by the 2-addr instruction. 3201176bdada62cabc6ec4b0308a930e83b679d5d36John Reck OldValNo->def = RedefIndex; 3211176bdada62cabc6ec4b0308a930e83b679d5d36John Reck OldValNo->copy = 0; 3221176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 3231176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Add the new live interval which replaces the range for the input copy. 3241176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveRange LR(DefIndex, RedefIndex, ValNo); 3251176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " replace range with " << LR; 3261176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addRange(LR); 3271176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addKill(ValNo, RedefIndex); 3281176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 3291176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // If this redefinition is dead, we need to add a dummy unit live 3301176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // range covering the def slot. 3311176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (mi->registerDefIsDead(interval.reg, tri_)) 3321176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); 3331176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 3341176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " RESULT: "; 3351176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.print(DOUT, tri_); 3361176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 3371176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } else { 3381176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Otherwise, this must be because of phi elimination. If this is the 3391176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // first redefinition of the vreg that we have seen, go back and change 3401176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // the live range in the PHI block to be a different value number. 3411176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (interval.containsOneValue()) { 3421176bdada62cabc6ec4b0308a930e83b679d5d36John Reck assert(vi.Kills.size() == 1 && 3431176bdada62cabc6ec4b0308a930e83b679d5d36John Reck "PHI elimination vreg should have one kill, the PHI itself!"); 3441176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 3451176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Remove the old range that we now know has an incorrect number. 3461176bdada62cabc6ec4b0308a930e83b679d5d36John Reck VNInfo *VNI = interval.getValNumInfo(0); 3471176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *Killer = vi.Kills[0]; 3481176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned Start = getMBBStartIdx(Killer->getParent()); 3491176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 3501176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " Removing [" << Start << "," << End << "] from: "; 3511176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.print(DOUT, tri_); DOUT << "\n"; 3521176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.removeRange(Start, End); 3531176bdada62cabc6ec4b0308a930e83b679d5d36John Reck VNI->hasPHIKill = true; 3541176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " RESULT: "; interval.print(DOUT, tri_); 3551176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 3561176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Replace the interval with one of a NEW value number. Note that this 3571176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // value number isn't actually defined by an instruction, weird huh? :) 3581176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator)); 3591176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " replace range with " << LR; 3601176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addRange(LR); 3611176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addKill(LR.valno, End); 3621176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " RESULT: "; interval.print(DOUT, tri_); 3631176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 3641176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 3651176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // In the case of PHI elimination, each variable definition is only 3661176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // live until the end of the block. We've already taken care of the 3671176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // rest of the live range. 3681176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned defIndex = getDefIndex(MIIdx); 3691176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 3701176bdada62cabc6ec4b0308a930e83b679d5d36John Reck VNInfo *ValNo; 3711176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *CopyMI = NULL; 3721176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned SrcReg, DstReg; 3731176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 3741176bdada62cabc6ec4b0308a930e83b679d5d36John Reck mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 3751176bdada62cabc6ec4b0308a930e83b679d5d36John Reck tii_->isMoveInstr(*mi, SrcReg, DstReg)) 3761176bdada62cabc6ec4b0308a930e83b679d5d36John Reck CopyMI = mi; 3771176bdada62cabc6ec4b0308a930e83b679d5d36John Reck ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 3781176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 3791176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM; 3801176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveRange LR(defIndex, killIndex, ValNo); 3811176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addRange(LR); 3821176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addKill(ValNo, killIndex); 3831176bdada62cabc6ec4b0308a930e83b679d5d36John Reck ValNo->hasPHIKill = true; 3841176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " +" << LR; 3851176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 3861176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 3871176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 3881176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << '\n'; 3891176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 3901176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 3911176bdada62cabc6ec4b0308a930e83b679d5d36John Reckvoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 3921176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineBasicBlock::iterator mi, 3931176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned MIIdx, 3941176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveInterval &interval, 3951176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *CopyMI) { 3961176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // A physical register cannot be live across basic block, so its 3971176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // lifetime must end somewhere in its defining basic block. 3981176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 3991176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 4001176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned baseIndex = MIIdx; 4011176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned start = getDefIndex(baseIndex); 4021176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned end = start; 4031176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 4041176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // If it is not used after definition, it is considered dead at 4051176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // the instruction defining it. Hence its interval is: 4061176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // [defSlot(def), defSlot(def)+1) 4071176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (mi->registerDefIsDead(interval.reg, tri_)) { 4081176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " dead"; 4091176bdada62cabc6ec4b0308a930e83b679d5d36John Reck end = getDefIndex(start) + 1; 4101176bdada62cabc6ec4b0308a930e83b679d5d36John Reck goto exit; 4111176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 4121176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 4131176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // If it is not dead on definition, it must be killed by a 4141176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // subsequent instruction. Hence its interval is: 4151176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // [defSlot(def), useSlot(kill)+1) 4161176bdada62cabc6ec4b0308a930e83b679d5d36John Reck while (++mi != MBB->end()) { 4171176bdada62cabc6ec4b0308a930e83b679d5d36John Reck baseIndex += InstrSlots::NUM; 4181176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (mi->killsRegister(interval.reg, tri_)) { 4191176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " killed"; 4201176bdada62cabc6ec4b0308a930e83b679d5d36John Reck end = getUseIndex(baseIndex) + 1; 4211176bdada62cabc6ec4b0308a930e83b679d5d36John Reck goto exit; 4221176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } else if (mi->modifiesRegister(interval.reg, tri_)) { 4231176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Another instruction redefines the register before it is ever read. 4241176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Then the register is essentially dead at the instruction that defines 4251176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // it. Hence its interval is: 4261176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // [defSlot(def), defSlot(def)+1) 4271176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " dead"; 4281176bdada62cabc6ec4b0308a930e83b679d5d36John Reck end = getDefIndex(start) + 1; 4291176bdada62cabc6ec4b0308a930e83b679d5d36John Reck goto exit; 4301176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 4311176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 4321176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 4331176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // The only case we should have a dead physreg here without a killing or 4341176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // instruction where we know it's dead is if it is live-in to the function 4351176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // and never used. 4361176bdada62cabc6ec4b0308a930e83b679d5d36John Reck assert(!CopyMI && "physreg was not killed in defining block!"); 4371176bdada62cabc6ec4b0308a930e83b679d5d36John Reck end = getDefIndex(start) + 1; // It's dead. 4381176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 4391176bdada62cabc6ec4b0308a930e83b679d5d36John Reckexit: 4401176bdada62cabc6ec4b0308a930e83b679d5d36John Reck assert(start < end && "did not find end of interval?"); 4411176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 4421176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Already exists? Extend old live interval. 4431176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 4441176bdada62cabc6ec4b0308a930e83b679d5d36John Reck VNInfo *ValNo = (OldLR != interval.end()) 4451176bdada62cabc6ec4b0308a930e83b679d5d36John Reck ? OldLR->valno : interval.getNextValue(start, CopyMI, VNInfoAllocator); 4461176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveRange LR(start, end, ValNo); 4471176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addRange(LR); 4481176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addKill(LR.valno, end); 4491176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " +" << LR << '\n'; 4501176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 4511176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 4521176bdada62cabc6ec4b0308a930e83b679d5d36John Reckvoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 4531176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineBasicBlock::iterator MI, 4541176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned MIIdx, 4551176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned reg) { 4561176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (TargetRegisterInfo::isVirtualRegister(reg)) 4571176bdada62cabc6ec4b0308a930e83b679d5d36John Reck handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg)); 4581176bdada62cabc6ec4b0308a930e83b679d5d36John Reck else if (allocatableRegs_[reg]) { 4591176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *CopyMI = NULL; 4601176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned SrcReg, DstReg; 4611176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 4621176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 4631176bdada62cabc6ec4b0308a930e83b679d5d36John Reck tii_->isMoveInstr(*MI, SrcReg, DstReg)) 4641176bdada62cabc6ec4b0308a930e83b679d5d36John Reck CopyMI = MI; 4651176bdada62cabc6ec4b0308a930e83b679d5d36John Reck handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), CopyMI); 4661176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Def of a register also defines its sub-registers. 4671176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (const unsigned* AS = tri_->getSubRegisters(reg); *AS; ++AS) 4681176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // If MI also modifies the sub-register explicitly, avoid processing it 4691176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // more than once. Do not pass in TRI here so it checks for exact match. 4701176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (!MI->modifiesRegister(*AS)) 4711176bdada62cabc6ec4b0308a930e83b679d5d36John Reck handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0); 4721176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 4731176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 4741176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 4751176bdada62cabc6ec4b0308a930e83b679d5d36John Reckvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 4761176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned MIIdx, 4771176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveInterval &interval, bool isAlias) { 4781176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 4791176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 4801176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Look for kills, if it reaches a def before it's killed, then it shouldn't 4811176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // be considered a livein. 4821176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineBasicBlock::iterator mi = MBB->begin(); 4831176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned baseIndex = MIIdx; 4841176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned start = baseIndex; 4851176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned end = start; 4861176bdada62cabc6ec4b0308a930e83b679d5d36John Reck while (mi != MBB->end()) { 4871176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (mi->killsRegister(interval.reg, tri_)) { 4881176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " killed"; 4891176bdada62cabc6ec4b0308a930e83b679d5d36John Reck end = getUseIndex(baseIndex) + 1; 4901176bdada62cabc6ec4b0308a930e83b679d5d36John Reck goto exit; 4911176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } else if (mi->modifiesRegister(interval.reg, tri_)) { 4921176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Another instruction redefines the register before it is ever read. 4931176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Then the register is essentially dead at the instruction that defines 4941176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // it. Hence its interval is: 4951176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // [defSlot(def), defSlot(def)+1) 4961176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " dead"; 4971176bdada62cabc6ec4b0308a930e83b679d5d36John Reck end = getDefIndex(start) + 1; 4981176bdada62cabc6ec4b0308a930e83b679d5d36John Reck goto exit; 4991176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 5001176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 5011176bdada62cabc6ec4b0308a930e83b679d5d36John Reck baseIndex += InstrSlots::NUM; 5021176bdada62cabc6ec4b0308a930e83b679d5d36John Reck ++mi; 5031176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 5041176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 5051176bdada62cabc6ec4b0308a930e83b679d5d36John Reckexit: 5061176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Live-in register might not be used at all. 5071176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (end == MIIdx) { 5081176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (isAlias) { 5091176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " dead"; 5101176bdada62cabc6ec4b0308a930e83b679d5d36John Reck end = getDefIndex(MIIdx) + 1; 5111176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } else { 5121176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " live through"; 5131176bdada62cabc6ec4b0308a930e83b679d5d36John Reck end = baseIndex; 5141176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 5151176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 5161176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 5171176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator)); 5181176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addRange(LR); 5191176bdada62cabc6ec4b0308a930e83b679d5d36John Reck interval.addKill(LR.valno, end); 5201176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " +" << LR << '\n'; 5211176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 5221176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 5231176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// computeIntervals - computes the live intervals for virtual 5241176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// registers. for some ordering of the machine instructions [1,N] a 5251176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// live interval is an interval [i, j) where 1 <= i <= j < N for 5261176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// which a variable is live 5271176bdada62cabc6ec4b0308a930e83b679d5d36John Reckvoid LiveIntervals::computeIntervals() { 5281176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 5291176bdada62cabc6ec4b0308a930e83b679d5d36John Reck << "********** Function: " 5301176bdada62cabc6ec4b0308a930e83b679d5d36John Reck << ((Value*)mf_->getFunction())->getName() << '\n'; 5311176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Track the index of the current machine instr. 5321176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned MIIndex = 0; 5331176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 5341176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MBBI != E; ++MBBI) { 5351176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineBasicBlock *MBB = MBBI; 5361176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 5371176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 5381176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 5391176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 5401176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Create intervals for live-ins to this BB first. 5411176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 5421176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LE = MBB->livein_end(); LI != LE; ++LI) { 5431176bdada62cabc6ec4b0308a930e83b679d5d36John Reck handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 5441176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Multiple live-ins can alias the same register. 5451176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 5461176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (!hasInterval(*AS)) 5471176bdada62cabc6ec4b0308a930e83b679d5d36John Reck handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 5481176bdada62cabc6ec4b0308a930e83b679d5d36John Reck true); 5491176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 5501176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 5511176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (; MI != miEnd; ++MI) { 5521176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << MIIndex << "\t" << *MI; 5531176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 5541176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Handle defs. 5551176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 5561176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineOperand &MO = MI->getOperand(i); 5571176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // handle register defs - build intervals 5581176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (MO.isRegister() && MO.getReg() && MO.isDef()) 5591176bdada62cabc6ec4b0308a930e83b679d5d36John Reck handleRegisterDef(MBB, MI, MIIndex, MO.getReg()); 5601176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 5611176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 5621176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MIIndex += InstrSlots::NUM; 5631176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 5641176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 5651176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 5661176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 5671176bdada62cabc6ec4b0308a930e83b679d5d36John Reckbool LiveIntervals::findLiveInMBBs(const LiveRange &LR, 5681176bdada62cabc6ec4b0308a930e83b679d5d36John Reck SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 5691176bdada62cabc6ec4b0308a930e83b679d5d36John Reck std::vector<IdxMBBPair>::const_iterator I = 5701176bdada62cabc6ec4b0308a930e83b679d5d36John Reck std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start); 5711176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 5721176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool ResVal = false; 5731176bdada62cabc6ec4b0308a930e83b679d5d36John Reck while (I != Idx2MBBMap.end()) { 5741176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (LR.end <= I->first) 5751176bdada62cabc6ec4b0308a930e83b679d5d36John Reck break; 5761176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MBBs.push_back(I->second); 5771176bdada62cabc6ec4b0308a930e83b679d5d36John Reck ResVal = true; 5781176bdada62cabc6ec4b0308a930e83b679d5d36John Reck ++I; 5791176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 5801176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return ResVal; 5811176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 5821176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 5831176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 5841176bdada62cabc6ec4b0308a930e83b679d5d36John ReckLiveInterval LiveIntervals::createInterval(unsigned reg) { 5851176bdada62cabc6ec4b0308a930e83b679d5d36John Reck float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? 5861176bdada62cabc6ec4b0308a930e83b679d5d36John Reck HUGE_VALF : 0.0F; 5871176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return LiveInterval(reg, Weight); 5881176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 5891176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 5901176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// getVNInfoSourceReg - Helper function that parses the specified VNInfo 5911176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// copy field and returns the source register that defines it. 5921176bdada62cabc6ec4b0308a930e83b679d5d36John Reckunsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 5931176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (!VNI->copy) 5941176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return 0; 5951176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 5961176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 5971176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return VNI->copy->getOperand(1).getReg(); 5981176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG) 5991176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return VNI->copy->getOperand(2).getReg(); 6001176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned SrcReg, DstReg; 6011176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg)) 6021176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return SrcReg; 6031176bdada62cabc6ec4b0308a930e83b679d5d36John Reck assert(0 && "Unrecognized copy instruction!"); 6041176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return 0; 6051176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 6061176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 6071176bdada62cabc6ec4b0308a930e83b679d5d36John Reck//===----------------------------------------------------------------------===// 6081176bdada62cabc6ec4b0308a930e83b679d5d36John Reck// Register allocator hooks. 6091176bdada62cabc6ec4b0308a930e83b679d5d36John Reck// 6101176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 6111176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 6121176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// allow one) virtual register operand, then its uses are implicitly using 6131176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// the register. Returns the virtual register. 6141176bdada62cabc6ec4b0308a930e83b679d5d36John Reckunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 6151176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *MI) const { 6161176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned RegOp = 0; 6171176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 6181176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineOperand &MO = MI->getOperand(i); 6191176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (!MO.isRegister() || !MO.isUse()) 6201176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 6211176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned Reg = MO.getReg(); 6221176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (Reg == 0 || Reg == li.reg) 6231176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 6241176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // FIXME: For now, only remat MI with at most one register operand. 6251176bdada62cabc6ec4b0308a930e83b679d5d36John Reck assert(!RegOp && 6261176bdada62cabc6ec4b0308a930e83b679d5d36John Reck "Can't rematerialize instruction with multiple register operand!"); 6271176bdada62cabc6ec4b0308a930e83b679d5d36John Reck RegOp = MO.getReg(); 6281176bdada62cabc6ec4b0308a930e83b679d5d36John Reck break; 6291176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 6301176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return RegOp; 6311176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 6321176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 6331176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// isValNoAvailableAt - Return true if the val# of the specified interval 6341176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// which reaches the given instruction also reaches the specified use index. 6351176bdada62cabc6ec4b0308a930e83b679d5d36John Reckbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 6361176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned UseIdx) const { 6371176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned Index = getInstructionIndex(MI); 6381176bdada62cabc6ec4b0308a930e83b679d5d36John Reck VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 6391176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 6401176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return UI != li.end() && UI->valno == ValNo; 6411176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 6421176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 6431176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// isReMaterializable - Returns true if the definition MI of the specified 6441176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// val# of the specified interval is re-materializable. 6451176bdada62cabc6ec4b0308a930e83b679d5d36John Reckbool LiveIntervals::isReMaterializable(const LiveInterval &li, 6461176bdada62cabc6ec4b0308a930e83b679d5d36John Reck const VNInfo *ValNo, MachineInstr *MI, 6471176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool &isLoad) { 6481176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (DisableReMat) 6491176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return false; 6501176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 6511176bdada62cabc6ec4b0308a930e83b679d5d36John Reck isLoad = false; 6521176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) 6531176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return true; 6541176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 6551176bdada62cabc6ec4b0308a930e83b679d5d36John Reck int FrameIdx = 0; 6561176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (tii_->isLoadFromStackSlot(MI, FrameIdx) && 6571176bdada62cabc6ec4b0308a930e83b679d5d36John Reck mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx)) 6581176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // FIXME: Let target specific isReallyTriviallyReMaterializable determines 6591176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // this but remember this is not safe to fold into a two-address 6601176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // instruction. 6611176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // This is a load from fixed stack slot. It can be rematerialized. 6621176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return true; 6631176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 6641176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (tii_->isTriviallyReMaterializable(MI)) { 6651176bdada62cabc6ec4b0308a930e83b679d5d36John Reck const TargetInstrDesc &TID = MI->getDesc(); 6661176bdada62cabc6ec4b0308a930e83b679d5d36John Reck isLoad = TID.isSimpleLoad(); 6671176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 6681176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned ImpUse = getReMatImplicitUse(li, MI); 6691176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (ImpUse) { 6701176bdada62cabc6ec4b0308a930e83b679d5d36John Reck const LiveInterval &ImpLi = getInterval(ImpUse); 6711176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), 6721176bdada62cabc6ec4b0308a930e83b679d5d36John Reck re = mri_->use_end(); ri != re; ++ri) { 6731176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *UseMI = &*ri; 6741176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned UseIdx = getInstructionIndex(UseMI); 6751176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 6761176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 6771176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 6781176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return false; 6791176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 6801176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 6811176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return true; 6821176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 6831176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 6841176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return false; 6851176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 6861176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 6871176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// isReMaterializable - Returns true if every definition of MI of every 6881176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// val# of the specified interval is re-materializable. 6891176bdada62cabc6ec4b0308a930e83b679d5d36John Reckbool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) { 6901176bdada62cabc6ec4b0308a930e83b679d5d36John Reck isLoad = false; 6911176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 6921176bdada62cabc6ec4b0308a930e83b679d5d36John Reck i != e; ++i) { 6931176bdada62cabc6ec4b0308a930e83b679d5d36John Reck const VNInfo *VNI = *i; 6941176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned DefIdx = VNI->def; 6951176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (DefIdx == ~1U) 6961176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; // Dead val#. 6971176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Is the def for the val# rematerializable? 6981176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (DefIdx == ~0u) 6991176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return false; 7001176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx); 7011176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool DefIsLoad = false; 7021176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (!ReMatDefMI || 7031176bdada62cabc6ec4b0308a930e83b679d5d36John Reck !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad)) 7041176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return false; 7051176bdada62cabc6ec4b0308a930e83b679d5d36John Reck isLoad |= DefIsLoad; 7061176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 7071176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return true; 7081176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 7091176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 7101176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// FilterFoldedOps - Filter out two-address use operands. Return 7111176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// true if it finds any issue with the operands that ought to prevent 7121176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// folding. 7131176bdada62cabc6ec4b0308a930e83b679d5d36John Reckstatic bool FilterFoldedOps(MachineInstr *MI, 7141176bdada62cabc6ec4b0308a930e83b679d5d36John Reck SmallVector<unsigned, 2> &Ops, 7151176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned &MRInfo, 7161176bdada62cabc6ec4b0308a930e83b679d5d36John Reck SmallVector<unsigned, 2> &FoldOps) { 7171176bdada62cabc6ec4b0308a930e83b679d5d36John Reck const TargetInstrDesc &TID = MI->getDesc(); 7181176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 7191176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MRInfo = 0; 7201176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 7211176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned OpIdx = Ops[i]; 7221176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineOperand &MO = MI->getOperand(OpIdx); 7231176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // FIXME: fold subreg use. 7241176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (MO.getSubReg()) 7251176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return true; 7261176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (MO.isDef()) 7271176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MRInfo |= (unsigned)VirtRegMap::isMod; 7281176bdada62cabc6ec4b0308a930e83b679d5d36John Reck else { 7291176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Filter out two-address use operand(s). 7301176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (!MO.isImplicit() && 7311176bdada62cabc6ec4b0308a930e83b679d5d36John Reck TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) { 7321176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MRInfo = VirtRegMap::isModRef; 7331176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 7341176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 7351176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MRInfo |= (unsigned)VirtRegMap::isRef; 7361176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 7371176bdada62cabc6ec4b0308a930e83b679d5d36John Reck FoldOps.push_back(OpIdx); 7381176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 7391176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return false; 7401176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 7411176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 7421176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 7431176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 7441176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// slot / to reg or any rematerialized load into ith operand of specified 7451176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// MI. If it is successul, MI is updated with the newly created MI and 7461176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// returns true. 7471176bdada62cabc6ec4b0308a930e83b679d5d36John Reckbool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 7481176bdada62cabc6ec4b0308a930e83b679d5d36John Reck VirtRegMap &vrm, MachineInstr *DefMI, 7491176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned InstrIdx, 7501176bdada62cabc6ec4b0308a930e83b679d5d36John Reck SmallVector<unsigned, 2> &Ops, 7511176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool isSS, int Slot, unsigned Reg) { 7521176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // If it is an implicit def instruction, just delete it. 7531176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 7541176bdada62cabc6ec4b0308a930e83b679d5d36John Reck RemoveMachineInstrFromMaps(MI); 7551176bdada62cabc6ec4b0308a930e83b679d5d36John Reck vrm.RemoveMachineInstrFromMaps(MI); 7561176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MI->eraseFromParent(); 7571176bdada62cabc6ec4b0308a930e83b679d5d36John Reck ++numFolds; 7581176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return true; 7591176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 7601176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 7611176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Filter the list of operand indexes that are to be folded. Abort if 7621176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // any operand will prevent folding. 7631176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned MRInfo = 0; 7641176bdada62cabc6ec4b0308a930e83b679d5d36John Reck SmallVector<unsigned, 2> FoldOps; 7651176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 7661176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return false; 7671176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 7681176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // The only time it's safe to fold into a two address instruction is when 7691176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // it's folding reload and spill from / into a spill stack slot. 7701176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (DefMI && (MRInfo & VirtRegMap::isMod)) 7711176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return false; 7721176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 7731176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 7741176bdada62cabc6ec4b0308a930e83b679d5d36John Reck : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 7751176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (fmi) { 7761176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Remember this instruction uses the spill slot. 7771176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (isSS) vrm.addSpillSlotUse(Slot, fmi); 7781176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 7791176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Attempt to fold the memory reference into the instruction. If 7801176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // we can do this, we don't need to insert spill code. 7811176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (lv_) 7821176bdada62cabc6ec4b0308a930e83b679d5d36John Reck lv_->instructionChanged(MI, fmi); 7831176bdada62cabc6ec4b0308a930e83b679d5d36John Reck else 7841176bdada62cabc6ec4b0308a930e83b679d5d36John Reck fmi->copyKillDeadInfo(MI, tri_); 7851176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineBasicBlock &MBB = *MI->getParent(); 7861176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 7871176bdada62cabc6ec4b0308a930e83b679d5d36John Reck vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 7881176bdada62cabc6ec4b0308a930e83b679d5d36John Reck vrm.transferSpillPts(MI, fmi); 7891176bdada62cabc6ec4b0308a930e83b679d5d36John Reck vrm.transferRestorePts(MI, fmi); 7901176bdada62cabc6ec4b0308a930e83b679d5d36John Reck vrm.transferEmergencySpills(MI, fmi); 7911176bdada62cabc6ec4b0308a930e83b679d5d36John Reck mi2iMap_.erase(MI); 7921176bdada62cabc6ec4b0308a930e83b679d5d36John Reck i2miMap_[InstrIdx /InstrSlots::NUM] = fmi; 7931176bdada62cabc6ec4b0308a930e83b679d5d36John Reck mi2iMap_[fmi] = InstrIdx; 7941176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MI = MBB.insert(MBB.erase(MI), fmi); 7951176bdada62cabc6ec4b0308a930e83b679d5d36John Reck ++numFolds; 7961176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return true; 7971176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 7981176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return false; 7991176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 8001176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 8011176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// canFoldMemoryOperand - Returns true if the specified load / store 8021176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// folding is possible. 8031176bdada62cabc6ec4b0308a930e83b679d5d36John Reckbool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 8041176bdada62cabc6ec4b0308a930e83b679d5d36John Reck SmallVector<unsigned, 2> &Ops, 8051176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool ReMat) const { 8061176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Filter the list of operand indexes that are to be folded. Abort if 8071176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // any operand will prevent folding. 8081176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned MRInfo = 0; 8091176bdada62cabc6ec4b0308a930e83b679d5d36John Reck SmallVector<unsigned, 2> FoldOps; 8101176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 8111176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return false; 8121176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 8131176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // It's only legal to remat for a use, not a def. 8141176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (ReMat && (MRInfo & VirtRegMap::isMod)) 8151176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return false; 8161176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 8171176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return tii_->canFoldMemoryOperand(MI, FoldOps); 8181176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 8191176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 8201176bdada62cabc6ec4b0308a930e83b679d5d36John Reckbool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 8211176bdada62cabc6ec4b0308a930e83b679d5d36John Reck SmallPtrSet<MachineBasicBlock*, 4> MBBs; 8221176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (LiveInterval::Ranges::const_iterator 8231176bdada62cabc6ec4b0308a930e83b679d5d36John Reck I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 8241176bdada62cabc6ec4b0308a930e83b679d5d36John Reck std::vector<IdxMBBPair>::const_iterator II = 8251176bdada62cabc6ec4b0308a930e83b679d5d36John Reck std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start); 8261176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (II == Idx2MBBMap.end()) 8271176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 8281176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (I->end > II->first) // crossing a MBB. 8291176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return false; 8301176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MBBs.insert(II->second); 8311176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (MBBs.size() > 1) 8321176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return false; 8331176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 8341176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return true; 8351176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 8361176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 8371176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 8381176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// interval on to-be re-materialized operands of MI) with new register. 8391176bdada62cabc6ec4b0308a930e83b679d5d36John Reckvoid LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 8401176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *MI, unsigned NewVReg, 8411176bdada62cabc6ec4b0308a930e83b679d5d36John Reck VirtRegMap &vrm) { 8421176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // There is an implicit use. That means one of the other operand is 8431176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // being remat'ed and the remat'ed instruction has li.reg as an 8441176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // use operand. Make sure we rewrite that as well. 8451176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 8461176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineOperand &MO = MI->getOperand(i); 8471176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (!MO.isRegister()) 8481176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 8491176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned Reg = MO.getReg(); 8501176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 8511176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 8521176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (!vrm.isReMaterialized(Reg)) 8531176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 8541176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 8551176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 8561176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (UseMO) 8571176bdada62cabc6ec4b0308a930e83b679d5d36John Reck UseMO->setReg(NewVReg); 8581176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 8591176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 8601176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 8611176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 8621176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 8631176bdada62cabc6ec4b0308a930e83b679d5d36John Reckbool LiveIntervals:: 8641176bdada62cabc6ec4b0308a930e83b679d5d36John ReckrewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 8651176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool TrySplit, unsigned index, unsigned end, MachineInstr *MI, 8661176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 8671176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned Slot, int LdSlot, 8681176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 8691176bdada62cabc6ec4b0308a930e83b679d5d36John Reck VirtRegMap &vrm, 8701176bdada62cabc6ec4b0308a930e83b679d5d36John Reck const TargetRegisterClass* rc, 8711176bdada62cabc6ec4b0308a930e83b679d5d36John Reck SmallVector<int, 4> &ReMatIds, 8721176bdada62cabc6ec4b0308a930e83b679d5d36John Reck const MachineLoopInfo *loopInfo, 8731176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 8741176bdada62cabc6ec4b0308a930e83b679d5d36John Reck std::map<unsigned,unsigned> &MBBVRegsMap, 8751176bdada62cabc6ec4b0308a930e83b679d5d36John Reck std::vector<LiveInterval*> &NewLIs) { 8761176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool CanFold = false; 8771176bdada62cabc6ec4b0308a930e83b679d5d36John Reck RestartInstruction: 8781176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 8791176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineOperand& mop = MI->getOperand(i); 8801176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (!mop.isRegister()) 8811176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 8821176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned Reg = mop.getReg(); 8831176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned RegI = Reg; 8841176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 8851176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 8861176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (Reg != li.reg) 8871176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 8881176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 8891176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool TryFold = !DefIsReMat; 8901176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool FoldSS = true; // Default behavior unless it's a remat. 8911176bdada62cabc6ec4b0308a930e83b679d5d36John Reck int FoldSlot = Slot; 8921176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (DefIsReMat) { 8931176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // If this is the rematerializable definition MI itself and 8941176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // all of its uses are rematerialized, simply delete it. 8951176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (MI == ReMatOrigDefMI && CanDelete) { 8961176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << "\t\t\t\tErasing re-materlizable def: "; 8971176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << MI << '\n'; 8981176bdada62cabc6ec4b0308a930e83b679d5d36John Reck RemoveMachineInstrFromMaps(MI); 8991176bdada62cabc6ec4b0308a930e83b679d5d36John Reck vrm.RemoveMachineInstrFromMaps(MI); 9001176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MI->eraseFromParent(); 9011176bdada62cabc6ec4b0308a930e83b679d5d36John Reck break; 9021176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 9031176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 9041176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // If def for this use can't be rematerialized, then try folding. 9051176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // If def is rematerializable and it's a load, also try folding. 9061176bdada62cabc6ec4b0308a930e83b679d5d36John Reck TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 9071176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (isLoad) { 9081176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Try fold loads (from stack slot, constant pool, etc.) into uses. 9091176bdada62cabc6ec4b0308a930e83b679d5d36John Reck FoldSS = isLoadSS; 9101176bdada62cabc6ec4b0308a930e83b679d5d36John Reck FoldSlot = LdSlot; 9111176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 9121176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 9131176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 9141176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Scan all of the operands of this instruction rewriting operands 9151176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // to use NewVReg instead of li.reg as appropriate. We do this for 9161176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // two reasons: 9171176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // 9181176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // 1. If the instr reads the same spilled vreg multiple times, we 9191176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // want to reuse the NewVReg. 9201176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // 2. If the instr is a two-addr instruction, we are required to 9211176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // keep the src/dst regs pinned. 9221176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // 9231176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Keep track of whether we replace a use and/or def so that we can 9241176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // create the spill interval with the appropriate range. 9251176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 9261176bdada62cabc6ec4b0308a930e83b679d5d36John Reck HasUse = mop.isUse(); 9271176bdada62cabc6ec4b0308a930e83b679d5d36John Reck HasDef = mop.isDef(); 9281176bdada62cabc6ec4b0308a930e83b679d5d36John Reck SmallVector<unsigned, 2> Ops; 9291176bdada62cabc6ec4b0308a930e83b679d5d36John Reck Ops.push_back(i); 9301176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 9311176bdada62cabc6ec4b0308a930e83b679d5d36John Reck const MachineOperand &MOj = MI->getOperand(j); 9321176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (!MOj.isRegister()) 9331176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 9341176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned RegJ = MOj.getReg(); 9351176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 9361176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 9371176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (RegJ == RegI) { 9381176bdada62cabc6ec4b0308a930e83b679d5d36John Reck Ops.push_back(j); 9391176bdada62cabc6ec4b0308a930e83b679d5d36John Reck HasUse |= MOj.isUse(); 9401176bdada62cabc6ec4b0308a930e83b679d5d36John Reck HasDef |= MOj.isDef(); 9411176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 9421176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 9431176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 9441176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (TryFold) { 9451176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Do not fold load / store here if we are splitting. We'll find an 9461176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // optimal point to insert a load / store later. 9471176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (!TrySplit) { 9481176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 9491176bdada62cabc6ec4b0308a930e83b679d5d36John Reck Ops, FoldSS, FoldSlot, Reg)) { 9501176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Folding the load/store can completely change the instruction in 9511176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // unpredictable ways, rescan it from the beginning. 9521176bdada62cabc6ec4b0308a930e83b679d5d36John Reck HasUse = false; 9531176bdada62cabc6ec4b0308a930e83b679d5d36John Reck HasDef = false; 9541176bdada62cabc6ec4b0308a930e83b679d5d36John Reck CanFold = false; 9551176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (isRemoved(MI)) 9561176bdada62cabc6ec4b0308a930e83b679d5d36John Reck break; 9571176bdada62cabc6ec4b0308a930e83b679d5d36John Reck goto RestartInstruction; 9581176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 9591176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } else { 9601176bdada62cabc6ec4b0308a930e83b679d5d36John Reck CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 9611176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 9621176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } else 9631176bdada62cabc6ec4b0308a930e83b679d5d36John Reck CanFold = false; 9641176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 9651176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Create a new virtual register for the spill interval. 9661176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool CreatedNewVReg = false; 9671176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (NewVReg == 0) { 9681176bdada62cabc6ec4b0308a930e83b679d5d36John Reck NewVReg = mri_->createVirtualRegister(rc); 9691176bdada62cabc6ec4b0308a930e83b679d5d36John Reck vrm.grow(); 9701176bdada62cabc6ec4b0308a930e83b679d5d36John Reck CreatedNewVReg = true; 9711176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 9721176bdada62cabc6ec4b0308a930e83b679d5d36John Reck mop.setReg(NewVReg); 9731176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (mop.isImplicit()) 9741176bdada62cabc6ec4b0308a930e83b679d5d36John Reck rewriteImplicitOps(li, MI, NewVReg, vrm); 9751176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 9761176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Reuse NewVReg for other reads. 9771176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 9781176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineOperand &mopj = MI->getOperand(Ops[j]); 9791176bdada62cabc6ec4b0308a930e83b679d5d36John Reck mopj.setReg(NewVReg); 9801176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (mopj.isImplicit()) 9811176bdada62cabc6ec4b0308a930e83b679d5d36John Reck rewriteImplicitOps(li, MI, NewVReg, vrm); 9821176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 9831176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 9841176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (CreatedNewVReg) { 9851176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (DefIsReMat) { 9861176bdada62cabc6ec4b0308a930e83b679d5d36John Reck vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/); 9871176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 9881176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Each valnum may have its own remat id. 9891176bdada62cabc6ec4b0308a930e83b679d5d36John Reck ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 9901176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } else { 9911176bdada62cabc6ec4b0308a930e83b679d5d36John Reck vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 9921176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 9931176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (!CanDelete || (HasUse && HasDef)) { 9941176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // If this is a two-addr instruction then its use operands are 9951176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // rematerializable but its def is not. It should be assigned a 9961176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // stack slot. 9971176bdada62cabc6ec4b0308a930e83b679d5d36John Reck vrm.assignVirt2StackSlot(NewVReg, Slot); 9981176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 9991176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } else { 10001176bdada62cabc6ec4b0308a930e83b679d5d36John Reck vrm.assignVirt2StackSlot(NewVReg, Slot); 10011176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 10021176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } else if (HasUse && HasDef && 10031176bdada62cabc6ec4b0308a930e83b679d5d36John Reck vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 10041176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // If this interval hasn't been assigned a stack slot (because earlier 10051176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // def is a deleted remat def), do it now. 10061176bdada62cabc6ec4b0308a930e83b679d5d36John Reck assert(Slot != VirtRegMap::NO_STACK_SLOT); 10071176bdada62cabc6ec4b0308a930e83b679d5d36John Reck vrm.assignVirt2StackSlot(NewVReg, Slot); 10081176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 10091176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 10101176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Re-matting an instruction with virtual register use. Add the 10111176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // register as an implicit use on the use MI. 10121176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (DefIsReMat && ImpUse) 10131176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 10141176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 10151176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // create a new register interval for this spill / remat. 10161176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveInterval &nI = getOrCreateInterval(NewVReg); 10171176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (CreatedNewVReg) { 10181176bdada62cabc6ec4b0308a930e83b679d5d36John Reck NewLIs.push_back(&nI); 10191176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 10201176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (TrySplit) 10211176bdada62cabc6ec4b0308a930e83b679d5d36John Reck vrm.setIsSplitFromReg(NewVReg, li.reg); 10221176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 10231176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 10241176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (HasUse) { 10251176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (CreatedNewVReg) { 10261176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, 10271176bdada62cabc6ec4b0308a930e83b679d5d36John Reck nI.getNextValue(~0U, 0, VNInfoAllocator)); 10281176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " +" << LR; 10291176bdada62cabc6ec4b0308a930e83b679d5d36John Reck nI.addRange(LR); 10301176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } else { 10311176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Extend the split live interval to this def / use. 10321176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned End = getUseIndex(index)+1; 10331176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 10341176bdada62cabc6ec4b0308a930e83b679d5d36John Reck nI.getValNumInfo(nI.getNumValNums()-1)); 10351176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " +" << LR; 10361176bdada62cabc6ec4b0308a930e83b679d5d36John Reck nI.addRange(LR); 10371176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 10381176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 10391176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (HasDef) { 10401176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveRange LR(getDefIndex(index), getStoreIndex(index), 10411176bdada62cabc6ec4b0308a930e83b679d5d36John Reck nI.getNextValue(~0U, 0, VNInfoAllocator)); 10421176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << " +" << LR; 10431176bdada62cabc6ec4b0308a930e83b679d5d36John Reck nI.addRange(LR); 10441176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 10451176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 10461176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << "\t\t\t\tAdded new interval: "; 10471176bdada62cabc6ec4b0308a930e83b679d5d36John Reck nI.print(DOUT, tri_); 10481176bdada62cabc6ec4b0308a930e83b679d5d36John Reck DOUT << '\n'; 10491176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 10501176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return CanFold; 10511176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 10521176bdada62cabc6ec4b0308a930e83b679d5d36John Reckbool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 10531176bdada62cabc6ec4b0308a930e83b679d5d36John Reck const VNInfo *VNI, 10541176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineBasicBlock *MBB, unsigned Idx) const { 10551176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned End = getMBBEndIdx(MBB); 10561176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 10571176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned KillIdx = VNI->kills[j]; 10581176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (KillIdx > Idx && KillIdx < End) 10591176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return true; 10601176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 10611176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return false; 10621176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 10631176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 10641176bdada62cabc6ec4b0308a930e83b679d5d36John Reckstatic const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) { 10651176bdada62cabc6ec4b0308a930e83b679d5d36John Reck const VNInfo *VNI = NULL; 10661176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (LiveInterval::const_vni_iterator i = li.vni_begin(), 10671176bdada62cabc6ec4b0308a930e83b679d5d36John Reck e = li.vni_end(); i != e; ++i) 10681176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if ((*i)->def == DefIdx) { 10691176bdada62cabc6ec4b0308a930e83b679d5d36John Reck VNI = *i; 10701176bdada62cabc6ec4b0308a930e83b679d5d36John Reck break; 10711176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 10721176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return VNI; 10731176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 10741176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 10751176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// RewriteInfo - Keep track of machine instrs that will be rewritten 10761176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/// during spilling. 10771176bdada62cabc6ec4b0308a930e83b679d5d36John Recknamespace { 10781176bdada62cabc6ec4b0308a930e83b679d5d36John Reck struct RewriteInfo { 10791176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned Index; 10801176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *MI; 10811176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool HasUse; 10821176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool HasDef; 10831176bdada62cabc6ec4b0308a930e83b679d5d36John Reck RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d) 10841176bdada62cabc6ec4b0308a930e83b679d5d36John Reck : Index(i), MI(mi), HasUse(u), HasDef(d) {} 10851176bdada62cabc6ec4b0308a930e83b679d5d36John Reck }; 10861176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 10871176bdada62cabc6ec4b0308a930e83b679d5d36John Reck struct RewriteInfoCompare { 10881176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 10891176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return LHS.Index < RHS.Index; 10901176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 10911176bdada62cabc6ec4b0308a930e83b679d5d36John Reck }; 10921176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 10931176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 10941176bdada62cabc6ec4b0308a930e83b679d5d36John Reckvoid LiveIntervals:: 10951176bdada62cabc6ec4b0308a930e83b679d5d36John ReckrewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 10961176bdada62cabc6ec4b0308a930e83b679d5d36John Reck LiveInterval::Ranges::const_iterator &I, 10971176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 10981176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned Slot, int LdSlot, 10991176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 11001176bdada62cabc6ec4b0308a930e83b679d5d36John Reck VirtRegMap &vrm, 11011176bdada62cabc6ec4b0308a930e83b679d5d36John Reck const TargetRegisterClass* rc, 11021176bdada62cabc6ec4b0308a930e83b679d5d36John Reck SmallVector<int, 4> &ReMatIds, 11031176bdada62cabc6ec4b0308a930e83b679d5d36John Reck const MachineLoopInfo *loopInfo, 11041176bdada62cabc6ec4b0308a930e83b679d5d36John Reck BitVector &SpillMBBs, 11051176bdada62cabc6ec4b0308a930e83b679d5d36John Reck std::map<unsigned, std::vector<SRInfo> > &SpillIdxes, 11061176bdada62cabc6ec4b0308a930e83b679d5d36John Reck BitVector &RestoreMBBs, 11071176bdada62cabc6ec4b0308a930e83b679d5d36John Reck std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes, 11081176bdada62cabc6ec4b0308a930e83b679d5d36John Reck std::map<unsigned,unsigned> &MBBVRegsMap, 11091176bdada62cabc6ec4b0308a930e83b679d5d36John Reck std::vector<LiveInterval*> &NewLIs) { 11101176bdada62cabc6ec4b0308a930e83b679d5d36John Reck bool AllCanFold = true; 11111176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned NewVReg = 0; 11121176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned start = getBaseIndex(I->start); 11131176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; 11141176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 11151176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // First collect all the def / use in this live range that will be rewritten. 11161176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Make sure they are sorted according to instruction index. 11171176bdada62cabc6ec4b0308a930e83b679d5d36John Reck std::vector<RewriteInfo> RewriteMIs; 11181176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 11191176bdada62cabc6ec4b0308a930e83b679d5d36John Reck re = mri_->reg_end(); ri != re; ) { 11201176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineInstr *MI = &*ri; 11211176bdada62cabc6ec4b0308a930e83b679d5d36John Reck MachineOperand &O = ri.getOperand(); 11221176bdada62cabc6ec4b0308a930e83b679d5d36John Reck ++ri; 11231176bdada62cabc6ec4b0308a930e83b679d5d36John Reck assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); 11241176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned index = getInstructionIndex(MI); 11251176bdada62cabc6ec4b0308a930e83b679d5d36John Reck if (index < start || index >= end) 11261176bdada62cabc6ec4b0308a930e83b679d5d36John Reck continue; 11271176bdada62cabc6ec4b0308a930e83b679d5d36John Reck RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 11281176bdada62cabc6ec4b0308a930e83b679d5d36John Reck } 11291176bdada62cabc6ec4b0308a930e83b679d5d36John Reck std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 11301176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 11311176bdada62cabc6ec4b0308a930e83b679d5d36John Reck unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 11321176bdada62cabc6ec4b0308a930e83b679d5d36John Reck // Now rewrite the defs and uses. 11331176bdada62cabc6ec4b0308a930e83b679d5d36John Reck for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 11341176bdada62cabc6ec4b0308a930e83b679d5d36John Reck RewriteInfo &rwi = RewriteMIs[i]; 11351176bdada62cabc6ec4b0308a930e83b679d5d36John Reck ++i; 1136 unsigned index = rwi.Index; 1137 bool MIHasUse = rwi.HasUse; 1138 bool MIHasDef = rwi.HasDef; 1139 MachineInstr *MI = rwi.MI; 1140 // If MI def and/or use the same register multiple times, then there 1141 // are multiple entries. 1142 unsigned NumUses = MIHasUse; 1143 while (i != e && RewriteMIs[i].MI == MI) { 1144 assert(RewriteMIs[i].Index == index); 1145 bool isUse = RewriteMIs[i].HasUse; 1146 if (isUse) ++NumUses; 1147 MIHasUse |= isUse; 1148 MIHasDef |= RewriteMIs[i].HasDef; 1149 ++i; 1150 } 1151 MachineBasicBlock *MBB = MI->getParent(); 1152 1153 if (ImpUse && MI != ReMatDefMI) { 1154 // Re-matting an instruction with virtual register use. Update the 1155 // register interval's spill weight to HUGE_VALF to prevent it from 1156 // being spilled. 1157 LiveInterval &ImpLi = getInterval(ImpUse); 1158 ImpLi.weight = HUGE_VALF; 1159 } 1160 1161 unsigned MBBId = MBB->getNumber(); 1162 unsigned ThisVReg = 0; 1163 if (TrySplit) { 1164 std::map<unsigned,unsigned>::const_iterator NVI = MBBVRegsMap.find(MBBId); 1165 if (NVI != MBBVRegsMap.end()) { 1166 ThisVReg = NVI->second; 1167 // One common case: 1168 // x = use 1169 // ... 1170 // ... 1171 // def = ... 1172 // = use 1173 // It's better to start a new interval to avoid artifically 1174 // extend the new interval. 1175 if (MIHasDef && !MIHasUse) { 1176 MBBVRegsMap.erase(MBB->getNumber()); 1177 ThisVReg = 0; 1178 } 1179 } 1180 } 1181 1182 bool IsNew = ThisVReg == 0; 1183 if (IsNew) { 1184 // This ends the previous live interval. If all of its def / use 1185 // can be folded, give it a low spill weight. 1186 if (NewVReg && TrySplit && AllCanFold) { 1187 LiveInterval &nI = getOrCreateInterval(NewVReg); 1188 nI.weight /= 10.0F; 1189 } 1190 AllCanFold = true; 1191 } 1192 NewVReg = ThisVReg; 1193 1194 bool HasDef = false; 1195 bool HasUse = false; 1196 bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 1197 index, end, MI, ReMatOrigDefMI, ReMatDefMI, 1198 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1199 CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 1200 ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); 1201 if (!HasDef && !HasUse) 1202 continue; 1203 1204 AllCanFold &= CanFold; 1205 1206 // Update weight of spill interval. 1207 LiveInterval &nI = getOrCreateInterval(NewVReg); 1208 if (!TrySplit) { 1209 // The spill weight is now infinity as it cannot be spilled again. 1210 nI.weight = HUGE_VALF; 1211 continue; 1212 } 1213 1214 // Keep track of the last def and first use in each MBB. 1215 if (HasDef) { 1216 if (MI != ReMatOrigDefMI || !CanDelete) { 1217 bool HasKill = false; 1218 if (!HasUse) 1219 HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index)); 1220 else { 1221 // If this is a two-address code, then this index starts a new VNInfo. 1222 const VNInfo *VNI = findDefinedVNInfo(li, getDefIndex(index)); 1223 if (VNI) 1224 HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); 1225 } 1226 std::map<unsigned, std::vector<SRInfo> >::iterator SII = 1227 SpillIdxes.find(MBBId); 1228 if (!HasKill) { 1229 if (SII == SpillIdxes.end()) { 1230 std::vector<SRInfo> S; 1231 S.push_back(SRInfo(index, NewVReg, true)); 1232 SpillIdxes.insert(std::make_pair(MBBId, S)); 1233 } else if (SII->second.back().vreg != NewVReg) { 1234 SII->second.push_back(SRInfo(index, NewVReg, true)); 1235 } else if ((int)index > SII->second.back().index) { 1236 // If there is an earlier def and this is a two-address 1237 // instruction, then it's not possible to fold the store (which 1238 // would also fold the load). 1239 SRInfo &Info = SII->second.back(); 1240 Info.index = index; 1241 Info.canFold = !HasUse; 1242 } 1243 SpillMBBs.set(MBBId); 1244 } else if (SII != SpillIdxes.end() && 1245 SII->second.back().vreg == NewVReg && 1246 (int)index > SII->second.back().index) { 1247 // There is an earlier def that's not killed (must be two-address). 1248 // The spill is no longer needed. 1249 SII->second.pop_back(); 1250 if (SII->second.empty()) { 1251 SpillIdxes.erase(MBBId); 1252 SpillMBBs.reset(MBBId); 1253 } 1254 } 1255 } 1256 } 1257 1258 if (HasUse) { 1259 std::map<unsigned, std::vector<SRInfo> >::iterator SII = 1260 SpillIdxes.find(MBBId); 1261 if (SII != SpillIdxes.end() && 1262 SII->second.back().vreg == NewVReg && 1263 (int)index > SII->second.back().index) 1264 // Use(s) following the last def, it's not safe to fold the spill. 1265 SII->second.back().canFold = false; 1266 std::map<unsigned, std::vector<SRInfo> >::iterator RII = 1267 RestoreIdxes.find(MBBId); 1268 if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 1269 // If we are splitting live intervals, only fold if it's the first 1270 // use and there isn't another use later in the MBB. 1271 RII->second.back().canFold = false; 1272 else if (IsNew) { 1273 // Only need a reload if there isn't an earlier def / use. 1274 if (RII == RestoreIdxes.end()) { 1275 std::vector<SRInfo> Infos; 1276 Infos.push_back(SRInfo(index, NewVReg, true)); 1277 RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 1278 } else { 1279 RII->second.push_back(SRInfo(index, NewVReg, true)); 1280 } 1281 RestoreMBBs.set(MBBId); 1282 } 1283 } 1284 1285 // Update spill weight. 1286 unsigned loopDepth = loopInfo->getLoopDepth(MBB); 1287 nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1288 } 1289 1290 if (NewVReg && TrySplit && AllCanFold) { 1291 // If all of its def / use can be folded, give it a low spill weight. 1292 LiveInterval &nI = getOrCreateInterval(NewVReg); 1293 nI.weight /= 10.0F; 1294 } 1295} 1296 1297bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr, 1298 BitVector &RestoreMBBs, 1299 std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 1300 if (!RestoreMBBs[Id]) 1301 return false; 1302 std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 1303 for (unsigned i = 0, e = Restores.size(); i != e; ++i) 1304 if (Restores[i].index == index && 1305 Restores[i].vreg == vr && 1306 Restores[i].canFold) 1307 return true; 1308 return false; 1309} 1310 1311void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr, 1312 BitVector &RestoreMBBs, 1313 std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 1314 if (!RestoreMBBs[Id]) 1315 return; 1316 std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 1317 for (unsigned i = 0, e = Restores.size(); i != e; ++i) 1318 if (Restores[i].index == index && Restores[i].vreg) 1319 Restores[i].index = -1; 1320} 1321 1322/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 1323/// spilled and create empty intervals for their uses. 1324void 1325LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 1326 const TargetRegisterClass* rc, 1327 std::vector<LiveInterval*> &NewLIs) { 1328 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1329 re = mri_->reg_end(); ri != re; ) { 1330 MachineOperand &O = ri.getOperand(); 1331 MachineInstr *MI = &*ri; 1332 ++ri; 1333 if (O.isDef()) { 1334 assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF && 1335 "Register def was not rewritten?"); 1336 RemoveMachineInstrFromMaps(MI); 1337 vrm.RemoveMachineInstrFromMaps(MI); 1338 MI->eraseFromParent(); 1339 } else { 1340 // This must be an use of an implicit_def so it's not part of the live 1341 // interval. Create a new empty live interval for it. 1342 // FIXME: Can we simply erase some of the instructions? e.g. Stores? 1343 unsigned NewVReg = mri_->createVirtualRegister(rc); 1344 vrm.grow(); 1345 vrm.setIsImplicitlyDefined(NewVReg); 1346 NewLIs.push_back(&getOrCreateInterval(NewVReg)); 1347 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1348 MachineOperand &MO = MI->getOperand(i); 1349 if (MO.isReg() && MO.getReg() == li.reg) 1350 MO.setReg(NewVReg); 1351 } 1352 } 1353 } 1354} 1355 1356 1357std::vector<LiveInterval*> LiveIntervals:: 1358addIntervalsForSpills(const LiveInterval &li, 1359 const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { 1360 // Since this is called after the analysis is done we don't know if 1361 // LiveVariables is available 1362 lv_ = getAnalysisToUpdate<LiveVariables>(); 1363 1364 assert(li.weight != HUGE_VALF && 1365 "attempt to spill already spilled interval!"); 1366 1367 DOUT << "\t\t\t\tadding intervals for spills for interval: "; 1368 li.print(DOUT, tri_); 1369 DOUT << '\n'; 1370 1371 // Each bit specify whether it a spill is required in the MBB. 1372 BitVector SpillMBBs(mf_->getNumBlockIDs()); 1373 std::map<unsigned, std::vector<SRInfo> > SpillIdxes; 1374 BitVector RestoreMBBs(mf_->getNumBlockIDs()); 1375 std::map<unsigned, std::vector<SRInfo> > RestoreIdxes; 1376 std::map<unsigned,unsigned> MBBVRegsMap; 1377 std::vector<LiveInterval*> NewLIs; 1378 const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1379 1380 unsigned NumValNums = li.getNumValNums(); 1381 SmallVector<MachineInstr*, 4> ReMatDefs; 1382 ReMatDefs.resize(NumValNums, NULL); 1383 SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1384 ReMatOrigDefs.resize(NumValNums, NULL); 1385 SmallVector<int, 4> ReMatIds; 1386 ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1387 BitVector ReMatDelete(NumValNums); 1388 unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1389 1390 // Spilling a split live interval. It cannot be split any further. Also, 1391 // it's also guaranteed to be a single val# / range interval. 1392 if (vrm.getPreSplitReg(li.reg)) { 1393 vrm.setIsSplitFromReg(li.reg, 0); 1394 // Unset the split kill marker on the last use. 1395 unsigned KillIdx = vrm.getKillPoint(li.reg); 1396 if (KillIdx) { 1397 MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1398 assert(KillMI && "Last use disappeared?"); 1399 int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1400 assert(KillOp != -1 && "Last use disappeared?"); 1401 KillMI->getOperand(KillOp).setIsKill(false); 1402 } 1403 vrm.removeKillPoint(li.reg); 1404 bool DefIsReMat = vrm.isReMaterialized(li.reg); 1405 Slot = vrm.getStackSlot(li.reg); 1406 assert(Slot != VirtRegMap::MAX_STACK_SLOT); 1407 MachineInstr *ReMatDefMI = DefIsReMat ? 1408 vrm.getReMaterializedMI(li.reg) : NULL; 1409 int LdSlot = 0; 1410 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1411 bool isLoad = isLoadSS || 1412 (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad())); 1413 bool IsFirstRange = true; 1414 for (LiveInterval::Ranges::const_iterator 1415 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 1416 // If this is a split live interval with multiple ranges, it means there 1417 // are two-address instructions that re-defined the value. Only the 1418 // first def can be rematerialized! 1419 if (IsFirstRange) { 1420 // Note ReMatOrigDefMI has already been deleted. 1421 rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 1422 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1423 false, vrm, rc, ReMatIds, loopInfo, 1424 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1425 MBBVRegsMap, NewLIs); 1426 } else { 1427 rewriteInstructionsForSpills(li, false, I, NULL, 0, 1428 Slot, 0, false, false, false, 1429 false, vrm, rc, ReMatIds, loopInfo, 1430 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1431 MBBVRegsMap, NewLIs); 1432 } 1433 IsFirstRange = false; 1434 } 1435 1436 handleSpilledImpDefs(li, vrm, rc, NewLIs); 1437 return NewLIs; 1438 } 1439 1440 bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li); 1441 if (SplitLimit != -1 && (int)numSplits >= SplitLimit) 1442 TrySplit = false; 1443 if (TrySplit) 1444 ++numSplits; 1445 bool NeedStackSlot = false; 1446 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1447 i != e; ++i) { 1448 const VNInfo *VNI = *i; 1449 unsigned VN = VNI->id; 1450 unsigned DefIdx = VNI->def; 1451 if (DefIdx == ~1U) 1452 continue; // Dead val#. 1453 // Is the def for the val# rematerializable? 1454 MachineInstr *ReMatDefMI = (DefIdx == ~0u) 1455 ? 0 : getInstructionFromIndex(DefIdx); 1456 bool dummy; 1457 if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) { 1458 // Remember how to remat the def of this val#. 1459 ReMatOrigDefs[VN] = ReMatDefMI; 1460 // Original def may be modified so we have to make a copy here. vrm must 1461 // delete these! 1462 ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone(); 1463 1464 bool CanDelete = true; 1465 if (VNI->hasPHIKill) { 1466 // A kill is a phi node, not all of its uses can be rematerialized. 1467 // It must not be deleted. 1468 CanDelete = false; 1469 // Need a stack slot if there is any live range where uses cannot be 1470 // rematerialized. 1471 NeedStackSlot = true; 1472 } 1473 if (CanDelete) 1474 ReMatDelete.set(VN); 1475 } else { 1476 // Need a stack slot if there is any live range where uses cannot be 1477 // rematerialized. 1478 NeedStackSlot = true; 1479 } 1480 } 1481 1482 // One stack slot per live interval. 1483 if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) 1484 Slot = vrm.assignVirt2StackSlot(li.reg); 1485 1486 // Create new intervals and rewrite defs and uses. 1487 for (LiveInterval::Ranges::const_iterator 1488 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 1489 MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 1490 MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 1491 bool DefIsReMat = ReMatDefMI != NULL; 1492 bool CanDelete = ReMatDelete[I->valno->id]; 1493 int LdSlot = 0; 1494 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1495 bool isLoad = isLoadSS || 1496 (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad()); 1497 rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 1498 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1499 CanDelete, vrm, rc, ReMatIds, loopInfo, 1500 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1501 MBBVRegsMap, NewLIs); 1502 } 1503 1504 // Insert spills / restores if we are splitting. 1505 if (!TrySplit) { 1506 handleSpilledImpDefs(li, vrm, rc, NewLIs); 1507 return NewLIs; 1508 } 1509 1510 SmallPtrSet<LiveInterval*, 4> AddedKill; 1511 SmallVector<unsigned, 2> Ops; 1512 if (NeedStackSlot) { 1513 int Id = SpillMBBs.find_first(); 1514 while (Id != -1) { 1515 std::vector<SRInfo> &spills = SpillIdxes[Id]; 1516 for (unsigned i = 0, e = spills.size(); i != e; ++i) { 1517 int index = spills[i].index; 1518 unsigned VReg = spills[i].vreg; 1519 LiveInterval &nI = getOrCreateInterval(VReg); 1520 bool isReMat = vrm.isReMaterialized(VReg); 1521 MachineInstr *MI = getInstructionFromIndex(index); 1522 bool CanFold = false; 1523 bool FoundUse = false; 1524 Ops.clear(); 1525 if (spills[i].canFold) { 1526 CanFold = true; 1527 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 1528 MachineOperand &MO = MI->getOperand(j); 1529 if (!MO.isRegister() || MO.getReg() != VReg) 1530 continue; 1531 1532 Ops.push_back(j); 1533 if (MO.isDef()) 1534 continue; 1535 if (isReMat || 1536 (!FoundUse && !alsoFoldARestore(Id, index, VReg, 1537 RestoreMBBs, RestoreIdxes))) { 1538 // MI has two-address uses of the same register. If the use 1539 // isn't the first and only use in the BB, then we can't fold 1540 // it. FIXME: Move this to rewriteInstructionsForSpills. 1541 CanFold = false; 1542 break; 1543 } 1544 FoundUse = true; 1545 } 1546 } 1547 // Fold the store into the def if possible. 1548 bool Folded = false; 1549 if (CanFold && !Ops.empty()) { 1550 if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 1551 Folded = true; 1552 if (FoundUse > 0) { 1553 // Also folded uses, do not issue a load. 1554 eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 1555 nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 1556 } 1557 nI.removeRange(getDefIndex(index), getStoreIndex(index)); 1558 } 1559 } 1560 1561 // Otherwise tell the spiller to issue a spill. 1562 if (!Folded) { 1563 LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 1564 bool isKill = LR->end == getStoreIndex(index); 1565 vrm.addSpillPoint(VReg, isKill, MI); 1566 if (isKill) 1567 AddedKill.insert(&nI); 1568 } 1569 } 1570 Id = SpillMBBs.find_next(Id); 1571 } 1572 } 1573 1574 int Id = RestoreMBBs.find_first(); 1575 while (Id != -1) { 1576 std::vector<SRInfo> &restores = RestoreIdxes[Id]; 1577 for (unsigned i = 0, e = restores.size(); i != e; ++i) { 1578 int index = restores[i].index; 1579 if (index == -1) 1580 continue; 1581 unsigned VReg = restores[i].vreg; 1582 LiveInterval &nI = getOrCreateInterval(VReg); 1583 MachineInstr *MI = getInstructionFromIndex(index); 1584 bool CanFold = false; 1585 Ops.clear(); 1586 if (restores[i].canFold) { 1587 CanFold = true; 1588 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 1589 MachineOperand &MO = MI->getOperand(j); 1590 if (!MO.isRegister() || MO.getReg() != VReg) 1591 continue; 1592 1593 if (MO.isDef()) { 1594 // If this restore were to be folded, it would have been folded 1595 // already. 1596 CanFold = false; 1597 break; 1598 } 1599 Ops.push_back(j); 1600 } 1601 } 1602 1603 // Fold the load into the use if possible. 1604 bool Folded = false; 1605 if (CanFold && !Ops.empty()) { 1606 if (!vrm.isReMaterialized(VReg)) 1607 Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 1608 else { 1609 MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 1610 int LdSlot = 0; 1611 bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1612 // If the rematerializable def is a load, also try to fold it. 1613 if (isLoadSS || ReMatDefMI->getDesc().isSimpleLoad()) 1614 Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1615 Ops, isLoadSS, LdSlot, VReg); 1616 unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 1617 if (ImpUse) { 1618 // Re-matting an instruction with virtual register use. Add the 1619 // register as an implicit use on the use MI and update the register 1620 // interval's spill weight to HUGE_VALF to prevent it from being 1621 // spilled. 1622 LiveInterval &ImpLi = getInterval(ImpUse); 1623 ImpLi.weight = HUGE_VALF; 1624 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1625 } 1626 } 1627 } 1628 // If folding is not possible / failed, then tell the spiller to issue a 1629 // load / rematerialization for us. 1630 if (Folded) 1631 nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 1632 else 1633 vrm.addRestorePoint(VReg, MI); 1634 } 1635 Id = RestoreMBBs.find_next(Id); 1636 } 1637 1638 // Finalize intervals: add kills, finalize spill weights, and filter out 1639 // dead intervals. 1640 std::vector<LiveInterval*> RetNewLIs; 1641 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 1642 LiveInterval *LI = NewLIs[i]; 1643 if (!LI->empty()) { 1644 LI->weight /= LI->getSize(); 1645 if (!AddedKill.count(LI)) { 1646 LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 1647 unsigned LastUseIdx = getBaseIndex(LR->end); 1648 MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 1649 int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 1650 assert(UseIdx != -1); 1651 if (LastUse->getOperand(UseIdx).isImplicit() || 1652 LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){ 1653 LastUse->getOperand(UseIdx).setIsKill(); 1654 vrm.addKillPoint(LI->reg, LastUseIdx); 1655 } 1656 } 1657 RetNewLIs.push_back(LI); 1658 } 1659 } 1660 1661 handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 1662 return RetNewLIs; 1663} 1664 1665/// hasAllocatableSuperReg - Return true if the specified physical register has 1666/// any super register that's allocatable. 1667bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 1668 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 1669 if (allocatableRegs_[*AS] && hasInterval(*AS)) 1670 return true; 1671 return false; 1672} 1673 1674/// getRepresentativeReg - Find the largest super register of the specified 1675/// physical register. 1676unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 1677 // Find the largest super-register that is allocatable. 1678 unsigned BestReg = Reg; 1679 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 1680 unsigned SuperReg = *AS; 1681 if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 1682 BestReg = SuperReg; 1683 break; 1684 } 1685 } 1686 return BestReg; 1687} 1688 1689/// getNumConflictsWithPhysReg - Return the number of uses and defs of the 1690/// specified interval that conflicts with the specified physical register. 1691unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 1692 unsigned PhysReg) const { 1693 unsigned NumConflicts = 0; 1694 const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 1695 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 1696 E = mri_->reg_end(); I != E; ++I) { 1697 MachineOperand &O = I.getOperand(); 1698 MachineInstr *MI = O.getParent(); 1699 unsigned Index = getInstructionIndex(MI); 1700 if (pli.liveAt(Index)) 1701 ++NumConflicts; 1702 } 1703 return NumConflicts; 1704} 1705 1706/// spillPhysRegAroundRegDefsUses - Spill the specified physical register 1707/// around all defs and uses of the specified interval. 1708void LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 1709 unsigned PhysReg, VirtRegMap &vrm) { 1710 unsigned SpillReg = getRepresentativeReg(PhysReg); 1711 1712 for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 1713 // If there are registers which alias PhysReg, but which are not a 1714 // sub-register of the chosen representative super register. Assert 1715 // since we can't handle it yet. 1716 assert(*AS == SpillReg || !allocatableRegs_[*AS] || 1717 tri_->isSuperRegister(*AS, SpillReg)); 1718 1719 LiveInterval &pli = getInterval(SpillReg); 1720 SmallPtrSet<MachineInstr*, 8> SeenMIs; 1721 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 1722 E = mri_->reg_end(); I != E; ++I) { 1723 MachineOperand &O = I.getOperand(); 1724 MachineInstr *MI = O.getParent(); 1725 if (SeenMIs.count(MI)) 1726 continue; 1727 SeenMIs.insert(MI); 1728 unsigned Index = getInstructionIndex(MI); 1729 if (pli.liveAt(Index)) { 1730 vrm.addEmergencySpill(SpillReg, MI); 1731 pli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); 1732 for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) { 1733 if (!hasInterval(*AS)) 1734 continue; 1735 LiveInterval &spli = getInterval(*AS); 1736 if (spli.liveAt(Index)) 1737 spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); 1738 } 1739 } 1740 } 1741} 1742