LiveIntervalAnalysis.cpp revision 32dfbeada7292167bb488f36a71a5a6a519ddaff
1a3b8b5c0e0a1d0942288568b2012592184ca67c5Chris Lattner//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 2ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 3ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// The LLVM Compiler Infrastructure 4ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 5ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// This file was developed by the LLVM research group and is distributed under 6ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// the University of Illinois Open Source License. See LICENSE.TXT for details. 7ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 8ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos//===----------------------------------------------------------------------===// 9ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 10ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// This file implements the LiveInterval analysis pass which is used 11ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// by the Linear Scan Register allocator. This pass linearizes the 12ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// basic blocks of the function in DFS order and uses the 13ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// LiveVariables pass to conservatively compute live intervals for 14ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// each virtual and physical register. 15ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 16ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos//===----------------------------------------------------------------------===// 17ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 18ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#define DEBUG_TYPE "liveintervals" 193c3fe462f7978b429ecdd71750c26be25c3d1335Chris Lattner#include "llvm/CodeGen/LiveIntervalAnalysis.h" 2008a6c7614be9793754b17930ba619e875aef9585Misha Brukman#include "VirtRegMap.h" 21015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner#include "llvm/Value.h" 226b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos#include "llvm/Analysis/LoopInfo.h" 23ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/LiveVariables.h" 24ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 25ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineInstr.h" 26ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/Passes.h" 27ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/SSARegMap.h" 28ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/MRegisterInfo.h" 29ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 30ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 31551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 32551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 33551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 34551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 3520aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 3697af751deb9b26fd42fbcee082da9ccc4ded5b45Jeff Cohen#include <cmath> 37ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 38ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 39bc165e436beb02443abea9736c1b77e2dd7828b6Evan Chengnamespace { 40bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng // Hidden options for help debugging. 41bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng cl::opt<bool> DisableReMat("disable-rematerialization", 42bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng cl::init(false), cl::Hidden); 43bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng} 44bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng 45cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numIntervals, "Number of original intervals"); 46cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numIntervalsAfter, "Number of intervals after coalescing"); 47cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numFolded , "Number of loads/stores folded into instructions"); 48cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 491997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar LiveIntervals::ID = 0; 50ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosnamespace { 515d8925c7c506a54ebdfb0bc93437ec9f602eaaa0Chris Lattner RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 52d74ea2bbd8bb630331f35ead42d385249bd42af8Chris Lattner} 53ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 54f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 552513330de8f8020d15d5bc96640a0957b7c733b9David Greene AU.addPreserved<LiveVariables>(); 561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LiveVariables>(); 571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addPreservedID(PHIEliminationID); 581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(PHIEliminationID); 591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LoopInfo>(); 611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 62ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 63ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 64f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::releaseMemory() { 651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_.clear(); 661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_.clear(); 671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 68dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 69dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng VNInfoAllocator.Reset(); 70549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i) 71549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng delete ClonedMIs[i]; 72993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 73993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 74ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// runOnMachineFunction - Register allocate the whole function 75ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// 76ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mf_ = &fn; 781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos tm_ = &fn.getTarget(); 791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mri_ = tm_->getRegisterInfo(); 80f768bba43f5c036039851d2fcca8212edca18467Chris Lattner tii_ = tm_->getInstrInfo(); 811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos lv_ = &getAnalysis<LiveVariables>(); 8220b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng allocatableRegs_ = mri_->getAllocatableSet(fn); 831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 84428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Number MachineInstrs and MachineBasicBlocks. 85428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Initialize MBB indexes to a sentinal. 86549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U)); 87428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner 88428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned MIIndex = 0; 89428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); 90428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBB != E; ++MBB) { 91549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned StartIdx = MIIndex; 920c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 93428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 94428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner I != E; ++I) { 95428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; 961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 97428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner i2miMap_.push_back(I); 98428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MIIndex += InstrSlots::NUM; 991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 100549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 101549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // Set the MBB2IdxMap entry for this MBB. 102549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1); 103428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner } 104ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 106ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 108843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 109bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** INTERVALS **********\n"; 110bdc679d564e67a81792e463f6614b0088f975025Bill Wendling for (iterator I = begin(), E = end(); I != E; ++I) { 111bdc679d564e67a81792e463f6614b0088f975025Bill Wendling I->second.print(DOUT, mri_); 112bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\n"; 113bdc679d564e67a81792e463f6614b0088f975025Bill Wendling } 1147ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 1151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervalsAfter += getNumIntervals(); 11670ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 1171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 118ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 119ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 12070ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 121ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencervoid LiveIntervals::print(std::ostream &O, const Module* ) const { 12270ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** INTERVALS **********\n"; 1238e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 124bdc679d564e67a81792e463f6614b0088f975025Bill Wendling I->second.print(DOUT, mri_); 125bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\n"; 1268e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 12770ca358b7d540b6061236ddf757085042873c12cChris Lattner 12870ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** MACHINEINSTRS **********\n"; 12970ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 13070ca358b7d540b6061236ddf757085042873c12cChris Lattner mbbi != mbbe; ++mbbi) { 13170ca358b7d540b6061236ddf757085042873c12cChris Lattner O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 13270ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineBasicBlock::iterator mii = mbbi->begin(), 13370ca358b7d540b6061236ddf757085042873c12cChris Lattner mie = mbbi->end(); mii != mie; ++mii) { 134477e4555de341c5de780de3720d6f115ec133c4eChris Lattner O << getInstructionIndex(mii) << '\t' << *mii; 13570ca358b7d540b6061236ddf757085042873c12cChris Lattner } 13670ca358b7d540b6061236ddf757085042873c12cChris Lattner } 13770ca358b7d540b6061236ddf757085042873c12cChris Lattner} 13870ca358b7d540b6061236ddf757085042873c12cChris Lattner 139549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 140549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng/// val# of the specified interval is re-materializable. 1417ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 1427ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng const VNInfo *ValNo, MachineInstr *MI) { 143bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng if (DisableReMat) 144bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng return false; 145bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng 146549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (tii_->isTriviallyReMaterializable(MI)) 147549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng return true; 148549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 149549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng int FrameIdx = 0; 150549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (!tii_->isLoadFromStackSlot(MI, FrameIdx) || 151549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng !mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx)) 152549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng return false; 153549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 154549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // This is a load from fixed stack slot. It can be rematerialized unless it's 155549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // re-defined by a two-address instruction. 1567ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1577ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng i != e; ++i) { 1587ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng const VNInfo *VNI = *i; 1597ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (VNI == ValNo) 160549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng continue; 1617ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng unsigned DefIdx = VNI->def; 162549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (DefIdx == ~1U) 163549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng continue; // Dead val#. 164549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MachineInstr *DefMI = (DefIdx == ~0u) 165549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng ? NULL : getInstructionFromIndex(DefIdx); 16632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (DefMI && DefMI->isRegReDefinedByTwoAddr(li.reg)) 167549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng return false; 168549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng } 169549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng return true; 170549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng} 171549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 17234c2a9f57ccf57f341ad27cef59e4c5eb2253e1dEvan Cheng/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 17334c2a9f57ccf57f341ad27cef59e4c5eb2253e1dEvan Cheng/// slot / to reg or any rematerialized load into ith operand of specified 17434c2a9f57ccf57f341ad27cef59e4c5eb2253e1dEvan Cheng/// MI. If it is successul, MI is updated with the newly created MI and 17534c2a9f57ccf57f341ad27cef59e4c5eb2253e1dEvan Cheng/// returns true. 176549f27d3070195d6647b796841a5291b4549e8e0Evan Chengbool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm, 17732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MachineInstr *DefMI, 178549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned index, unsigned i, 17932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng bool isSS, int slot, unsigned reg) { 18034c2a9f57ccf57f341ad27cef59e4c5eb2253e1dEvan Cheng MachineInstr *fmi = isSS 18134c2a9f57ccf57f341ad27cef59e4c5eb2253e1dEvan Cheng ? mri_->foldMemoryOperand(MI, i, slot) 18234c2a9f57ccf57f341ad27cef59e4c5eb2253e1dEvan Cheng : mri_->foldMemoryOperand(MI, i, DefMI); 183549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (fmi) { 184549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // Attempt to fold the memory reference into the instruction. If 185549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // we can do this, we don't need to insert spill code. 186549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (lv_) 187549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng lv_->instructionChanged(MI, fmi); 188549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MachineBasicBlock &MBB = *MI->getParent(); 189549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng vrm.virtFolded(reg, MI, i, fmi); 190549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng mi2iMap_.erase(MI); 191549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng i2miMap_[index/InstrSlots::NUM] = fmi; 192549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng mi2iMap_[fmi] = index; 193549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MI = MBB.insert(MBB.erase(MI), fmi); 194549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng ++numFolded; 195549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng return true; 196549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng } 197549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng return false; 198549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng} 199549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 20070ca358b7d540b6061236ddf757085042873c12cChris Lattnerstd::vector<LiveInterval*> LiveIntervals:: 201549f27d3070195d6647b796841a5291b4549e8e0Evan ChengaddIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, unsigned reg) { 202d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // since this is called after the analysis is done we don't know if 203d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // LiveVariables is available 204d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos lv_ = getAnalysisToUpdate<LiveVariables>(); 205d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos 2061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos std::vector<LiveInterval*> added; 2071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2087902c75331fa8f38fc8380f5573d935c0d149ef5Jim Laskey assert(li.weight != HUGE_VALF && 2091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "attempt to spill already spilled interval!"); 2101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 211bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\t\t\tadding intervals for spills for interval: "; 212bdc679d564e67a81792e463f6614b0088f975025Bill Wendling li.print(DOUT, mri_); 213bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << '\n'; 2141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 21532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng SSARegMap *RegMap = mf_->getSSARegMap(); 21632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng const TargetRegisterClass* rc = RegMap->getRegClass(li.reg); 2171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 218549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned NumValNums = li.getNumValNums(); 219549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng SmallVector<MachineInstr*, 4> ReMatDefs; 220549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng ReMatDefs.resize(NumValNums, NULL); 221549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng SmallVector<MachineInstr*, 4> ReMatOrigDefs; 222549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng ReMatOrigDefs.resize(NumValNums, NULL); 223549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng SmallVector<int, 4> ReMatIds; 224549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 225549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng BitVector ReMatDelete(NumValNums); 226549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned slot = VirtRegMap::MAX_STACK_SLOT; 227549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 228549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng bool NeedStackSlot = false; 2297ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 2307ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng i != e; ++i) { 2317ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng const VNInfo *VNI = *i; 2327ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng unsigned VN = VNI->id; 2337ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng unsigned DefIdx = VNI->def; 234549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (DefIdx == ~1U) 235549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng continue; // Dead val#. 236549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // Is the def for the val# rematerializable? 237549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MachineInstr *DefMI = (DefIdx == ~0u) 238549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng ? NULL : getInstructionFromIndex(DefIdx); 2397ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (DefMI && isReMaterializable(li, VNI, DefMI)) { 240549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // Remember how to remat the def of this val#. 2417ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng ReMatOrigDefs[VN] = DefMI; 242549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // Original def may be modified so we have to make a copy here. vrm must 243549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // delete these! 2447ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng ReMatDefs[VN] = DefMI = DefMI->clone(); 245549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng vrm.setVirtIsReMaterialized(reg, DefMI); 246549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 247549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng bool CanDelete = true; 2487ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 2497ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng unsigned KillIdx = VNI->kills[j]; 250549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MachineInstr *KillMI = (KillIdx & 1) 251549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng ? NULL : getInstructionFromIndex(KillIdx); 252549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // Kill is a phi node, not all of its uses can be rematerialized. 253549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // It must not be deleted. 254549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (!KillMI) { 255549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng CanDelete = false; 256549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // Need a stack slot if there is any live range where uses cannot be 257549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // rematerialized. 258549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng NeedStackSlot = true; 259549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng break; 260549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng } 261549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng } 262549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 263549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (CanDelete) 2647ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng ReMatDelete.set(VN); 265549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng } else { 266549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // Need a stack slot if there is any live range where uses cannot be 267549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // rematerialized. 268549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng NeedStackSlot = true; 269549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng } 270549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng } 271549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 272549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // One stack slot per live interval. 273549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (NeedStackSlot) 274549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng slot = vrm.assignVirt2StackSlot(reg); 275549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 2761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (LiveInterval::Ranges::const_iterator 277549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 2787ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng MachineInstr *DefMI = ReMatDefs[I->valno->id]; 2797ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng MachineInstr *OrigDefMI = ReMatOrigDefs[I->valno->id]; 280549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng bool DefIsReMat = DefMI != NULL; 2817ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng bool CanDelete = ReMatDelete[I->valno->id]; 282549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng int LdSlot = 0; 283549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(DefMI, LdSlot); 28434c2a9f57ccf57f341ad27cef59e4c5eb2253e1dEvan Cheng bool isLoad = isLoadSS || 28534c2a9f57ccf57f341ad27cef59e4c5eb2253e1dEvan Cheng (DefIsReMat && (DefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG)); 286549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned index = getBaseIndex(I->start); 287549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; 2881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (; index != end; index += InstrSlots::NUM) { 2891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // skip deleted instructions 2901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos while (index != end && !getInstructionFromIndex(index)) 2911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos index += InstrSlots::NUM; 2921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (index == end) break; 2931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2943b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner MachineInstr *MI = getInstructionFromIndex(index); 2951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2962926869b4a083fc951484de03a9867eabf81e880Chris Lattner RestartInstruction: 2973b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 2983b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner MachineOperand& mop = MI->getOperand(i); 29932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (!mop.isRegister()) 30032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng continue; 30132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng unsigned Reg = mop.getReg(); 30232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (Reg == 0 || MRegisterInfo::isPhysicalRegister(Reg)) 30332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng continue; 30432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng bool isSubReg = RegMap->isSubRegister(Reg); 30532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng unsigned SubIdx = 0; 30632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (isSubReg) { 30732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng SubIdx = RegMap->getSubRegisterIndex(Reg); 30832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng Reg = RegMap->getSuperRegister(Reg); 30932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 31032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (Reg != li.reg) 31132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng continue; 31232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 31332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng bool TryFold = !DefIsReMat; 31432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng bool FoldSS = true; 31532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng int FoldSlot = slot; 31632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (DefIsReMat) { 31732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // If this is the rematerializable definition MI itself and 31832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // all of its uses are rematerialized, simply delete it. 31932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (MI == OrigDefMI && CanDelete) { 32032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng RemoveMachineInstrFromMaps(MI); 32132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MI->eraseFromParent(); 32232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng break; 323549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng } 324549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 32532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // If def for this use can't be rematerialized, then try folding. 32632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng TryFold = !OrigDefMI || (OrigDefMI && (MI == OrigDefMI || isLoad)); 32732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (isLoad) { 32832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // Try fold loads (from stack slot, constant pool, etc.) into uses. 32932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng FoldSS = isLoadSS; 33032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng FoldSlot = LdSlot; 33132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 33232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 33332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 33432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // FIXME: fold subreg use 33532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (!isSubReg && TryFold && 33632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng tryFoldMemoryOperand(MI, vrm, DefMI, index, i, FoldSS, FoldSlot, Reg)) 33732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // Folding the load/store can completely change the instruction in 33832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // unpredictable ways, rescan it from the beginning. 33932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng goto RestartInstruction; 34032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 34132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // Create a new virtual register for the spill interval. 34232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng unsigned NewVReg = RegMap->createVirtualRegister(rc); 34332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (isSubReg) 34432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng RegMap->setIsSubRegister(NewVReg, NewVReg, SubIdx); 3452926869b4a083fc951484de03a9867eabf81e880Chris Lattner 34632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // Scan all of the operands of this instruction rewriting operands 34732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // to use NewVReg instead of li.reg as appropriate. We do this for 34832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // two reasons: 34932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // 35032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // 1. If the instr reads the same spilled vreg multiple times, we 35132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // want to reuse the NewVReg. 35232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // 2. If the instr is a two-addr instruction, we are required to 35332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // keep the src/dst regs pinned. 35432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // 35532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // Keep track of whether we replace a use and/or def so that we can 35632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // create the spill interval with the appropriate range. 35732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng mop.setReg(NewVReg); 3582926869b4a083fc951484de03a9867eabf81e880Chris Lattner 35932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng bool HasUse = mop.isUse(); 36032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng bool HasDef = mop.isDef(); 36132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 36232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (MI->getOperand(j).isRegister() && 36332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MI->getOperand(j).getReg() == li.reg) { 36432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MI->getOperand(j).setReg(NewVReg); 36532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng HasUse |= MI->getOperand(j).isUse(); 36632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng HasDef |= MI->getOperand(j).isDef(); 367549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng } 36832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 3691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 37032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng vrm.grow(); 37132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (DefIsReMat) { 37232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng vrm.setVirtIsReMaterialized(NewVReg, DefMI/*, CanDelete*/); 37332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (ReMatIds[I->valno->id] == VirtRegMap::MAX_STACK_SLOT) { 37432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // Each valnum may have its own remat id. 37532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng ReMatIds[I->valno->id] = vrm.assignVirtReMatId(NewVReg); 376549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng } else { 37732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng vrm.assignVirtReMatId(NewVReg, ReMatIds[I->valno->id]); 37832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 37932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (!CanDelete || (HasUse && HasDef)) { 38032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // If this is a two-addr instruction then its use operands are 38132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // rematerializable but its def is not. It should be assigned a 38232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // stack slot. 383549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng vrm.assignVirt2StackSlot(NewVReg, slot); 384549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng } 38532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } else { 38632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng vrm.assignVirt2StackSlot(NewVReg, slot); 38732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 388549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 38932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // create a new register interval for this spill / remat. 39032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 39132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng assert(nI.empty()); 392549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 39332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // the spill weight is now infinity as it 39432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // cannot be spilled again 39532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng nI.weight = HUGE_VALF; 396549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 39732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (HasUse) { 39832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, 39932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng nI.getNextValue(~0U, 0, VNInfoAllocator)); 40032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng DOUT << " +" << LR; 40132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng nI.addRange(LR); 40232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 40332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (HasDef) { 40432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng LiveRange LR(getDefIndex(index), getStoreIndex(index), 40532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng nI.getNextValue(~0U, 0, VNInfoAllocator)); 40632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng DOUT << " +" << LR; 40732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng nI.addRange(LR); 40832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 4092926869b4a083fc951484de03a9867eabf81e880Chris Lattner 41032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng added.push_back(&nI); 41170ca358b7d540b6061236ddf757085042873c12cChris Lattner 41232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // update live variables if it is available 41332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (lv_) 41432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng lv_->addVirtualRegisterKilled(NewVReg, MI); 415b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner 41632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng DOUT << "\t\t\t\tadded new interval: "; 41732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng nI.print(DOUT, mri_); 41832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng DOUT << '\n'; 4191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 420843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 4211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 42226f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos 4231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return added; 424843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos} 425843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 426be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::printRegName(unsigned reg) const { 4271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(reg)) 428e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling cerr << mri_->getName(reg); 4291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 430e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling cerr << "%reg" << reg; 431ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 432ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 433be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 434ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 4356b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 436be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 437bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 4381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 4391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 440706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 441706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 442706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 4431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 4441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 4451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 4466b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 4477ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 44891725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 44932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (tii_->isMoveInstr(*mi, SrcReg, DstReg)) 450f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator); 45132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 45232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG) 45332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(), 45432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng VNInfoAllocator); 45532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng else 45632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator); 4577ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 4587ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(ValNo->id == 0 && "First value in interval is not 0?"); 4591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 4611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 4621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 4631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 4641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 4651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 4661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned killIdx; 4671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 4681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 4691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 4701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = defIndex+1; 4711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 4731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 4741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 47561de82d8853a02fe39c47302432abb70a586704fEvan Cheng assert(vi.AliveBlocks.none() && 4761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 4777ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIdx, ValNo); 4781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 479bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << "\n"; 480f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, killIdx); 4811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 4821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4846097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 4851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 4861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 4871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 4881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 489d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos LiveRange NewLR(defIndex, 490d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 4917ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng ValNo); 492bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << NewLR; 4931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 4941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Iterate over all of the blocks that the variable is completely 4961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 4971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live interval. 4981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 4991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.AliveBlocks[i]) { 500428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = mf_->getBlockNumbered(i); 501428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner if (!MBB->empty()) { 502428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner LiveRange LR(getMBBStartIdx(i), 503428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner getInstructionIndex(&MBB->back()) + InstrSlots::NUM, 5047ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng ValNo); 5051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 506bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 5071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 5121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 5131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 5141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 5158df786012dc6b875f31ba4152e09c6e0098082eeEvan Cheng unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1; 516428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner LiveRange LR(getMBBStartIdx(Kill->getParent()), 5177ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng killIdx, ValNo); 5181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 519f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, killIdx); 520bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 5211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 5241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 5251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 526bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 527bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 52832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (mi->isRegReDefinedByTwoAddr(interval.reg)) { 5291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 5301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 5311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 5321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 5331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 5341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst)); 5356b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned RedefIndex = getDefIndex(MIIdx); 5361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5374f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); 5387ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *OldValNo = OldLR->valno; 5394f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng unsigned OldEnd = OldLR->end; 5404f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 5411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Delete the initial value, which should be short and continuous, 542be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 5431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 544706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 545be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Two-address vregs should always only be redefined once. This means 546be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // that at this point, there should be exactly one value number in it. 547be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 548be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 54991725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 55091725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 551f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng VNInfo *ValNo = interval.getNextValue(0, 0, VNInfoAllocator); 552f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.copyValNumInfo(ValNo, OldValNo); 553be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 55491725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 5557ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng OldValNo->def = RedefIndex; 5567ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng OldValNo->reg = 0; 557be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 558be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 559be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 560bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 5611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 562f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, RedefIndex); 563f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.removeKills(ValNo, RedefIndex, OldEnd); 5641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 5661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 567ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->RegisterDefIsDead(mi, interval.reg)) 5687ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); 5691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 57056fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " RESULT: "; 571bdc679d564e67a81792e463f6614b0088f975025Bill Wendling interval.print(DOUT, mri_); 5721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 5741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Otherwise, this must be because of phi elimination. If this is the 5751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // first redefinition of the vreg that we have seen, go back and change 5761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range in the PHI block to be a different value number. 5771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.containsOneValue()) { 5781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(vi.Kills.size() == 1 && 5791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "PHI elimination vreg should have one kill, the PHI itself!"); 5801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Remove the old range that we now know has an incorrect number. 582f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng VNInfo *VNI = interval.getValNumInfo(0); 5831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Killer = vi.Kills[0]; 584428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned Start = getMBBStartIdx(Killer->getParent()); 5851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 58656fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " Removing [" << Start << "," << End << "] from: "; 587bdc679d564e67a81792e463f6614b0088f975025Bill Wendling interval.print(DOUT, mri_); DOUT << "\n"; 5881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(Start, End); 589f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(VNI, Start+1); // odd # means phi node 59056fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " RESULT: "; interval.print(DOUT, mri_); 5911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 592be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Replace the interval with one of a NEW value number. Note that this 593be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // value number isn't actually defined by an instruction, weird huh? :) 594f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator)); 595bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 5961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 597f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, End); 59856fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " RESULT: "; interval.print(DOUT, mri_); 5991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 6001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 6011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 6021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 6031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 6046b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 60591725b75852443923b419fd23215194cfc65dd88Chris Lattner 6067ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 60791725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 60832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (tii_->isMoveInstr(*mi, SrcReg, DstReg)) 609f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator); 61032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 61132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(), 61232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng VNInfoAllocator); 61332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng else 61432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator); 61591725b75852443923b419fd23215194cfc65dd88Chris Lattner 61624c2e5cf7e926452ea5875d027ec0d24d9c19e39Evan Cheng unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM; 6177ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 6181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 619f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, killIndex-1); // odd # means phi node 620bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 621dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 6221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 623ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 624bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << '\n'; 625ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 626ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 627f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 628ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 6296b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 63091725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveInterval &interval, 63191725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg) { 6321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 6331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 634bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 6351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 6366b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned baseIndex = MIIdx; 6371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned start = getDefIndex(baseIndex); 6381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = start; 6391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 6401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 6411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 6421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 643ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->RegisterDefIsDead(mi, interval.reg)) { 644bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 645ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getDefIndex(start) + 1; 646ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 6471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 648ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 6491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 6501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 6511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 6525ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 6531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos baseIndex += InstrSlots::NUM; 654ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->KillsRegister(mi, interval.reg)) { 655bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " killed"; 656ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getUseIndex(baseIndex) + 1; 657ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 6589a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng } else if (lv_->ModifiesRegister(mi, interval.reg)) { 6599a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // Another instruction redefines the register before it is ever read. 6609a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // Then the register is essentially dead at the instruction that defines 6619a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // it. Hence its interval is: 6629a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // [defSlot(def), defSlot(def)+1) 663bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 6649a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng end = getDefIndex(start) + 1; 6659a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng goto exit; 666f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 6671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 6685ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner 6695ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 6705ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 6715ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // and never used. 67291725b75852443923b419fd23215194cfc65dd88Chris Lattner assert(!SrcReg && "physreg was not killed in defining block!"); 6735ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner end = getDefIndex(start) + 1; // It's dead. 67402ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 675ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 6761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 677f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 67824a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 67924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 6807ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo = (OldLR != interval.end()) 681f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng ? OldLR->valno : interval.getNextValue(start, SrcReg, VNInfoAllocator); 6827ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 6831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 684f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 685bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << '\n'; 686ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 687ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 688f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 689f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 6906b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 691f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner unsigned reg) { 692f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner if (MRegisterInfo::isVirtualRegister(reg)) 6936b128bdc58a496e9f08e4d09416330320761baffChris Lattner handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg)); 6945327801fb87e3eda52a33f82e6211181030ecb93Alkis Evlogimenos else if (allocatableRegs_[reg]) { 69591725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 69632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 69732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng SrcReg = MI->getOperand(1).getReg(); 69832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng else if (!tii_->isMoveInstr(*MI, SrcReg, DstReg)) 69991725b75852443923b419fd23215194cfc65dd88Chris Lattner SrcReg = 0; 7006b128bdc58a496e9f08e4d09416330320761baffChris Lattner handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg); 70124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Def of a register also defines its sub-registers. 70224a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng for (const unsigned* AS = mri_->getSubRegisters(reg); *AS; ++AS) 70324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Avoid processing some defs more than once. 70424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng if (!MI->findRegisterDefOperand(*AS)) 70524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0); 706f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 7074d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 7084d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 709b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 7109b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned MIIdx, 71124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 712b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 713b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 714b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 715b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 716b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 7179b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned baseIndex = MIIdx; 7189b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned start = baseIndex; 719b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng unsigned end = start; 720b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng while (mi != MBB->end()) { 721b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng if (lv_->KillsRegister(mi, interval.reg)) { 722b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " killed"; 723b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getUseIndex(baseIndex) + 1; 724b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 725b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } else if (lv_->ModifiesRegister(mi, interval.reg)) { 726b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Another instruction redefines the register before it is ever read. 727b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Then the register is essentially dead at the instruction that defines 728b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // it. Hence its interval is: 729b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // [defSlot(def), defSlot(def)+1) 730b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " dead"; 731b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getDefIndex(start) + 1; 732b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 733b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 734b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 735b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng baseIndex += InstrSlots::NUM; 736b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng ++mi; 737b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 738b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 739b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengexit: 74075611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 74175611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng if (end == MIIdx) { 742292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng if (isAlias) { 743292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " dead"; 74475611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng end = getDefIndex(MIIdx) + 1; 745292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } else { 746292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " live through"; 747292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng end = baseIndex; 748292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } 74924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 75024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 751f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator)); 7529b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 753f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 75424c2e5cf7e926452ea5875d027ec0d24d9c19e39Evan Cheng DOUT << " +" << LR << '\n'; 755b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 756b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 757ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 7584d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 75908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 760ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 761f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::computeIntervals() { 762bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 763bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << "********** Function: " 764bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'; 7656b128bdc58a496e9f08e4d09416330320761baffChris Lattner // Track the index of the current machine instr. 7666b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIndex = 0; 767428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 768428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 769428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 770bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 7711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 772428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 7730c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 774cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 775cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 776cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 777cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 778cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Multiple live-ins can alias the same register. 779cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS) 780cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!hasInterval(*AS)) 781cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 782cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman true); 783dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 784dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner 785428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (; MI != miEnd; ++MI) { 786bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << MIIndex << "\t" << *MI; 7871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 788438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 789428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 790428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 7911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 792428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner if (MO.isRegister() && MO.getReg() && MO.isDef()) 793428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner handleRegisterDef(MBB, MI, MIIndex, MO.getReg()); 7941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 7956b128bdc58a496e9f08e4d09416330320761baffChris Lattner 7966b128bdc58a496e9f08e4d09416330320761baffChris Lattner MIIndex += InstrSlots::NUM; 797ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 7981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 799ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 800b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 801a1613db62fec94845aa8306232fb665273615badAlkis EvlogimenosLiveInterval LiveIntervals::createInterval(unsigned reg) { 802edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman float Weight = MRegisterInfo::isPhysicalRegister(reg) ? 8037902c75331fa8f38fc8380f5573d935c0d149ef5Jim Laskey HUGE_VALF : 0.0F; 804a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos return LiveInterval(reg, Weight); 8059a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 806