LiveIntervalAnalysis.cpp revision 75611fb4e6ab253be30ac29a2b15e9bf8c1d146e
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" 3320b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng#include "llvm/ADT/SmallSet.h" 34551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 35551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 3620aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 3797af751deb9b26fd42fbcee082da9ccc4ded5b45Jeff Cohen#include <cmath> 38ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 39ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 40cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numIntervals, "Number of original intervals"); 41cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numIntervalsAfter, "Number of intervals after coalescing"); 42cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numFolded , "Number of loads/stores folded into instructions"); 43cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 441997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar LiveIntervals::ID = 0; 45ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosnamespace { 465d8925c7c506a54ebdfb0bc93437ec9f602eaaa0Chris Lattner RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 47d74ea2bbd8bb630331f35ead42d385249bd42af8Chris Lattner} 48ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 49f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 502513330de8f8020d15d5bc96640a0957b7c733b9David Greene AU.addPreserved<LiveVariables>(); 511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LiveVariables>(); 521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addPreservedID(PHIEliminationID); 531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(PHIEliminationID); 541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LoopInfo>(); 561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 57ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 58ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 59f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::releaseMemory() { 601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_.clear(); 611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_.clear(); 621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 63993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 64993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 65ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// runOnMachineFunction - Register allocate the whole function 66ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// 67ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mf_ = &fn; 691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos tm_ = &fn.getTarget(); 701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mri_ = tm_->getRegisterInfo(); 71f768bba43f5c036039851d2fcca8212edca18467Chris Lattner tii_ = tm_->getInstrInfo(); 721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos lv_ = &getAnalysis<LiveVariables>(); 7320b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng allocatableRegs_ = mri_->getAllocatableSet(fn); 741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 75428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Number MachineInstrs and MachineBasicBlocks. 76428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Initialize MBB indexes to a sentinal. 77428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBB2IdxMap.resize(mf_->getNumBlockIDs(), ~0U); 78428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner 79428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned MIIndex = 0; 80428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); 81428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBB != E; ++MBB) { 82428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Set the MBB2IdxMap entry for this MBB. 83428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBB2IdxMap[MBB->getNumber()] = MIIndex; 840c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 85428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 86428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner I != E; ++I) { 87428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; 881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 89428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner i2miMap_.push_back(I); 90428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MIIndex += InstrSlots::NUM; 911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 92428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner } 93ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 95ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 97843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 98bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** INTERVALS **********\n"; 99bdc679d564e67a81792e463f6614b0088f975025Bill Wendling for (iterator I = begin(), E = end(); I != E; ++I) { 100bdc679d564e67a81792e463f6614b0088f975025Bill Wendling I->second.print(DOUT, mri_); 101bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\n"; 102bdc679d564e67a81792e463f6614b0088f975025Bill Wendling } 1037ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 1041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervalsAfter += getNumIntervals(); 10570ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 1061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 107ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 108ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 10970ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 110ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencervoid LiveIntervals::print(std::ostream &O, const Module* ) const { 11170ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** INTERVALS **********\n"; 1128e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 113bdc679d564e67a81792e463f6614b0088f975025Bill Wendling I->second.print(DOUT, mri_); 114bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\n"; 1158e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 11670ca358b7d540b6061236ddf757085042873c12cChris Lattner 11770ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** MACHINEINSTRS **********\n"; 11870ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 11970ca358b7d540b6061236ddf757085042873c12cChris Lattner mbbi != mbbe; ++mbbi) { 12070ca358b7d540b6061236ddf757085042873c12cChris Lattner O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 12170ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineBasicBlock::iterator mii = mbbi->begin(), 12270ca358b7d540b6061236ddf757085042873c12cChris Lattner mie = mbbi->end(); mii != mie; ++mii) { 123477e4555de341c5de780de3720d6f115ec133c4eChris Lattner O << getInstructionIndex(mii) << '\t' << *mii; 12470ca358b7d540b6061236ddf757085042873c12cChris Lattner } 12570ca358b7d540b6061236ddf757085042873c12cChris Lattner } 12670ca358b7d540b6061236ddf757085042873c12cChris Lattner} 12770ca358b7d540b6061236ddf757085042873c12cChris Lattner 1282513330de8f8020d15d5bc96640a0957b7c733b9David Greene// Not called? 12901352aa1875ee08ae847cce398322042830d92edBill Wendling/// CreateNewLiveInterval - Create a new live interval with the given live 13001352aa1875ee08ae847cce398322042830d92edBill Wendling/// ranges. The new live interval will have an infinite spill weight. 13101352aa1875ee08ae847cce398322042830d92edBill WendlingLiveInterval& 13201352aa1875ee08ae847cce398322042830d92edBill WendlingLiveIntervals::CreateNewLiveInterval(const LiveInterval *LI, 13301352aa1875ee08ae847cce398322042830d92edBill Wendling const std::vector<LiveRange> &LRs) { 13401352aa1875ee08ae847cce398322042830d92edBill Wendling const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(LI->reg); 13501352aa1875ee08ae847cce398322042830d92edBill Wendling 13601352aa1875ee08ae847cce398322042830d92edBill Wendling // Create a new virtual register for the spill interval. 13701352aa1875ee08ae847cce398322042830d92edBill Wendling unsigned NewVReg = mf_->getSSARegMap()->createVirtualRegister(RC); 13801352aa1875ee08ae847cce398322042830d92edBill Wendling 13901352aa1875ee08ae847cce398322042830d92edBill Wendling // Replace the old virtual registers in the machine operands with the shiny 14001352aa1875ee08ae847cce398322042830d92edBill Wendling // new one. 14101352aa1875ee08ae847cce398322042830d92edBill Wendling for (std::vector<LiveRange>::const_iterator 14201352aa1875ee08ae847cce398322042830d92edBill Wendling I = LRs.begin(), E = LRs.end(); I != E; ++I) { 14301352aa1875ee08ae847cce398322042830d92edBill Wendling unsigned Index = getBaseIndex(I->start); 14401352aa1875ee08ae847cce398322042830d92edBill Wendling unsigned End = getBaseIndex(I->end - 1) + InstrSlots::NUM; 14501352aa1875ee08ae847cce398322042830d92edBill Wendling 14601352aa1875ee08ae847cce398322042830d92edBill Wendling for (; Index != End; Index += InstrSlots::NUM) { 14701352aa1875ee08ae847cce398322042830d92edBill Wendling // Skip deleted instructions 14801352aa1875ee08ae847cce398322042830d92edBill Wendling while (Index != End && !getInstructionFromIndex(Index)) 14901352aa1875ee08ae847cce398322042830d92edBill Wendling Index += InstrSlots::NUM; 15001352aa1875ee08ae847cce398322042830d92edBill Wendling 15101352aa1875ee08ae847cce398322042830d92edBill Wendling if (Index == End) break; 15201352aa1875ee08ae847cce398322042830d92edBill Wendling 15301352aa1875ee08ae847cce398322042830d92edBill Wendling MachineInstr *MI = getInstructionFromIndex(Index); 15401352aa1875ee08ae847cce398322042830d92edBill Wendling 155beeb77f3ae9e784f45ede2e38f51b9b25eb65913Bill Wendling for (unsigned J = 0, e = MI->getNumOperands(); J != e; ++J) { 15601352aa1875ee08ae847cce398322042830d92edBill Wendling MachineOperand &MOp = MI->getOperand(J); 1572513330de8f8020d15d5bc96640a0957b7c733b9David Greene if (MOp.isRegister() && MOp.getReg() == LI->reg) 15801352aa1875ee08ae847cce398322042830d92edBill Wendling MOp.setReg(NewVReg); 15901352aa1875ee08ae847cce398322042830d92edBill Wendling } 16001352aa1875ee08ae847cce398322042830d92edBill Wendling } 16101352aa1875ee08ae847cce398322042830d92edBill Wendling } 16201352aa1875ee08ae847cce398322042830d92edBill Wendling 16301352aa1875ee08ae847cce398322042830d92edBill Wendling LiveInterval &NewLI = getOrCreateInterval(NewVReg); 16401352aa1875ee08ae847cce398322042830d92edBill Wendling 16501352aa1875ee08ae847cce398322042830d92edBill Wendling // The spill weight is now infinity as it cannot be spilled again 16601352aa1875ee08ae847cce398322042830d92edBill Wendling NewLI.weight = float(HUGE_VAL); 16701352aa1875ee08ae847cce398322042830d92edBill Wendling 16801352aa1875ee08ae847cce398322042830d92edBill Wendling for (std::vector<LiveRange>::const_iterator 16901352aa1875ee08ae847cce398322042830d92edBill Wendling I = LRs.begin(), E = LRs.end(); I != E; ++I) { 170bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " Adding live range " << *I << " to new interval\n"; 17101352aa1875ee08ae847cce398322042830d92edBill Wendling NewLI.addRange(*I); 17201352aa1875ee08ae847cce398322042830d92edBill Wendling } 17301352aa1875ee08ae847cce398322042830d92edBill Wendling 174bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "Created new live interval " << NewLI << "\n"; 17501352aa1875ee08ae847cce398322042830d92edBill Wendling return NewLI; 17601352aa1875ee08ae847cce398322042830d92edBill Wendling} 17701352aa1875ee08ae847cce398322042830d92edBill Wendling 17870ca358b7d540b6061236ddf757085042873c12cChris Lattnerstd::vector<LiveInterval*> LiveIntervals:: 17970ca358b7d540b6061236ddf757085042873c12cChris LattneraddIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { 180d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // since this is called after the analysis is done we don't know if 181d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // LiveVariables is available 182d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos lv_ = getAnalysisToUpdate<LiveVariables>(); 183d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos 1841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos std::vector<LiveInterval*> added; 1851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1867902c75331fa8f38fc8380f5573d935c0d149ef5Jim Laskey assert(li.weight != HUGE_VALF && 1871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "attempt to spill already spilled interval!"); 1881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 189bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\t\t\tadding intervals for spills for interval: "; 190bdc679d564e67a81792e463f6614b0088f975025Bill Wendling li.print(DOUT, mri_); 191bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << '\n'; 1921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg); 1941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (LiveInterval::Ranges::const_iterator 1961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 1971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned index = getBaseIndex(i->start); 1981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = getBaseIndex(i->end-1) + InstrSlots::NUM; 1991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (; index != end; index += InstrSlots::NUM) { 2001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // skip deleted instructions 2011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos while (index != end && !getInstructionFromIndex(index)) 2021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos index += InstrSlots::NUM; 2031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (index == end) break; 2041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2053b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner MachineInstr *MI = getInstructionFromIndex(index); 2061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2072926869b4a083fc951484de03a9867eabf81e880Chris Lattner RestartInstruction: 2083b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 2093b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner MachineOperand& mop = MI->getOperand(i); 2101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (mop.isRegister() && mop.getReg() == li.reg) { 2112638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng MachineInstr *fmi = li.remat ? NULL 2122638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng : mri_->foldMemoryOperand(MI, i, slot); 2132638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng if (fmi) { 214b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // Attempt to fold the memory reference into the instruction. If we 215b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // can do this, we don't need to insert spill code. 216d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos if (lv_) 2173b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner lv_->instructionChanged(MI, fmi); 218200370fb5617a1719f0054804b412469ce486ebdEvan Cheng MachineBasicBlock &MBB = *MI->getParent(); 21935f2705e3de4600c3621b883eed9b22e4607ddf4Chris Lattner vrm.virtFolded(li.reg, MI, i, fmi); 2203b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner mi2iMap_.erase(MI); 2211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_[index/InstrSlots::NUM] = fmi; 2221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_[fmi] = index; 2233b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner MI = MBB.insert(MBB.erase(MI), fmi); 2241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ++numFolded; 225477e4555de341c5de780de3720d6f115ec133c4eChris Lattner // Folding the load/store can completely change the instruction in 226477e4555de341c5de780de3720d6f115ec133c4eChris Lattner // unpredictable ways, rescan it from the beginning. 2272926869b4a083fc951484de03a9867eabf81e880Chris Lattner goto RestartInstruction; 228477e4555de341c5de780de3720d6f115ec133c4eChris Lattner } else { 2292926869b4a083fc951484de03a9867eabf81e880Chris Lattner // Create a new virtual register for the spill interval. 2302926869b4a083fc951484de03a9867eabf81e880Chris Lattner unsigned NewVReg = mf_->getSSARegMap()->createVirtualRegister(rc); 2312926869b4a083fc951484de03a9867eabf81e880Chris Lattner 2322926869b4a083fc951484de03a9867eabf81e880Chris Lattner // Scan all of the operands of this instruction rewriting operands 2332926869b4a083fc951484de03a9867eabf81e880Chris Lattner // to use NewVReg instead of li.reg as appropriate. We do this for 2342926869b4a083fc951484de03a9867eabf81e880Chris Lattner // two reasons: 2351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // 2362926869b4a083fc951484de03a9867eabf81e880Chris Lattner // 1. If the instr reads the same spilled vreg multiple times, we 2372926869b4a083fc951484de03a9867eabf81e880Chris Lattner // want to reuse the NewVReg. 2382926869b4a083fc951484de03a9867eabf81e880Chris Lattner // 2. If the instr is a two-addr instruction, we are required to 2392926869b4a083fc951484de03a9867eabf81e880Chris Lattner // keep the src/dst regs pinned. 2402926869b4a083fc951484de03a9867eabf81e880Chris Lattner // 2412926869b4a083fc951484de03a9867eabf81e880Chris Lattner // Keep track of whether we replace a use and/or def so that we can 2422926869b4a083fc951484de03a9867eabf81e880Chris Lattner // create the spill interval with the appropriate range. 2432926869b4a083fc951484de03a9867eabf81e880Chris Lattner mop.setReg(NewVReg); 2442926869b4a083fc951484de03a9867eabf81e880Chris Lattner 2452926869b4a083fc951484de03a9867eabf81e880Chris Lattner bool HasUse = mop.isUse(); 2462926869b4a083fc951484de03a9867eabf81e880Chris Lattner bool HasDef = mop.isDef(); 2472926869b4a083fc951484de03a9867eabf81e880Chris Lattner for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 2482926869b4a083fc951484de03a9867eabf81e880Chris Lattner if (MI->getOperand(j).isReg() && 2492926869b4a083fc951484de03a9867eabf81e880Chris Lattner MI->getOperand(j).getReg() == li.reg) { 2502926869b4a083fc951484de03a9867eabf81e880Chris Lattner MI->getOperand(j).setReg(NewVReg); 2512926869b4a083fc951484de03a9867eabf81e880Chris Lattner HasUse |= MI->getOperand(j).isUse(); 2522926869b4a083fc951484de03a9867eabf81e880Chris Lattner HasDef |= MI->getOperand(j).isDef(); 2532926869b4a083fc951484de03a9867eabf81e880Chris Lattner } 2542926869b4a083fc951484de03a9867eabf81e880Chris Lattner } 2551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // create a new register for this spill 2571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos vrm.grow(); 2582638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng if (li.remat) 2592638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng vrm.setVirtIsReMaterialized(NewVReg, li.remat); 2602926869b4a083fc951484de03a9867eabf81e880Chris Lattner vrm.assignVirt2StackSlot(NewVReg, slot); 2612926869b4a083fc951484de03a9867eabf81e880Chris Lattner LiveInterval &nI = getOrCreateInterval(NewVReg); 2622638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng nI.remat = li.remat; 2631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(nI.empty()); 26470ca358b7d540b6061236ddf757085042873c12cChris Lattner 2651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the spill weight is now infinity as it 2661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // cannot be spilled again 2677902c75331fa8f38fc8380f5573d935c0d149ef5Jim Laskey nI.weight = HUGE_VALF; 2682926869b4a083fc951484de03a9867eabf81e880Chris Lattner 2692926869b4a083fc951484de03a9867eabf81e880Chris Lattner if (HasUse) { 2702926869b4a083fc951484de03a9867eabf81e880Chris Lattner LiveRange LR(getLoadIndex(index), getUseIndex(index), 2712926869b4a083fc951484de03a9867eabf81e880Chris Lattner nI.getNextValue(~0U, 0)); 272bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 2732926869b4a083fc951484de03a9867eabf81e880Chris Lattner nI.addRange(LR); 2742926869b4a083fc951484de03a9867eabf81e880Chris Lattner } 2752926869b4a083fc951484de03a9867eabf81e880Chris Lattner if (HasDef) { 2762926869b4a083fc951484de03a9867eabf81e880Chris Lattner LiveRange LR(getDefIndex(index), getStoreIndex(index), 2772926869b4a083fc951484de03a9867eabf81e880Chris Lattner nI.getNextValue(~0U, 0)); 278bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 2792926869b4a083fc951484de03a9867eabf81e880Chris Lattner nI.addRange(LR); 2802926869b4a083fc951484de03a9867eabf81e880Chris Lattner } 2812926869b4a083fc951484de03a9867eabf81e880Chris Lattner 2821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos added.push_back(&nI); 28370ca358b7d540b6061236ddf757085042873c12cChris Lattner 284d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // update live variables if it is available 285d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos if (lv_) 2862926869b4a083fc951484de03a9867eabf81e880Chris Lattner lv_->addVirtualRegisterKilled(NewVReg, MI); 287b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner 288bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\t\t\tadded new interval: "; 289bdc679d564e67a81792e463f6614b0088f975025Bill Wendling nI.print(DOUT, mri_); 290bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << '\n'; 2911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 292843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 2931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 294843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 2951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 29626f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos 2971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return added; 298843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos} 299843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 300be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::printRegName(unsigned reg) const { 3011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(reg)) 302e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling cerr << mri_->getName(reg); 3031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 304e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling cerr << "%reg" << reg; 305ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 306ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 307bf105c842450d3308d024be203ddd533f37051ecEvan Cheng/// isReDefinedByTwoAddr - Returns true if the Reg re-definition is due to 308bf105c842450d3308d024be203ddd533f37051ecEvan Cheng/// two addr elimination. 309bf105c842450d3308d024be203ddd533f37051ecEvan Chengstatic bool isReDefinedByTwoAddr(MachineInstr *MI, unsigned Reg, 310bf105c842450d3308d024be203ddd533f37051ecEvan Cheng const TargetInstrInfo *TII) { 311bf105c842450d3308d024be203ddd533f37051ecEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 312bf105c842450d3308d024be203ddd533f37051ecEvan Cheng MachineOperand &MO1 = MI->getOperand(i); 313bf105c842450d3308d024be203ddd533f37051ecEvan Cheng if (MO1.isRegister() && MO1.isDef() && MO1.getReg() == Reg) { 314bf105c842450d3308d024be203ddd533f37051ecEvan Cheng for (unsigned j = i+1; j < e; ++j) { 315bf105c842450d3308d024be203ddd533f37051ecEvan Cheng MachineOperand &MO2 = MI->getOperand(j); 316bf105c842450d3308d024be203ddd533f37051ecEvan Cheng if (MO2.isRegister() && MO2.isUse() && MO2.getReg() == Reg && 31751cdcd197268a7abf19b2698fc824e0da3d98049Evan Cheng MI->getInstrDescriptor()-> 31851cdcd197268a7abf19b2698fc824e0da3d98049Evan Cheng getOperandConstraint(j, TOI::TIED_TO) == (int)i) 319bf105c842450d3308d024be203ddd533f37051ecEvan Cheng return true; 320bf105c842450d3308d024be203ddd533f37051ecEvan Cheng } 321bf105c842450d3308d024be203ddd533f37051ecEvan Cheng } 322bf105c842450d3308d024be203ddd533f37051ecEvan Cheng } 323bf105c842450d3308d024be203ddd533f37051ecEvan Cheng return false; 324bf105c842450d3308d024be203ddd533f37051ecEvan Cheng} 325bf105c842450d3308d024be203ddd533f37051ecEvan Cheng 326be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 327ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 3286b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 329be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 330bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 3311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 3321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 333706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 334706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 335706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 3361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 3371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 3389193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng // Remember if the definition can be rematerialized. All load's from fixed 33982a87a01723c095176c6940bcc63d3a7c8007b4bDan Gohman // stack slots are re-materializable. The target may permit other 34082a87a01723c095176c6940bcc63d3a7c8007b4bDan Gohman // instructions to be re-materialized as well. 3419193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng int FrameIdx = 0; 3429193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng if (vi.DefInst && 34382a87a01723c095176c6940bcc63d3a7c8007b4bDan Gohman (tii_->isTriviallyReMaterializable(vi.DefInst) || 3449193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng (tii_->isLoadFromStackSlot(vi.DefInst, FrameIdx) && 34582a87a01723c095176c6940bcc63d3a7c8007b4bDan Gohman mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx)))) 3462638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng interval.remat = vi.DefInst; 3472638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng 3481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 3496b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 3501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 35191725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned ValNum; 35291725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 35391725b75852443923b419fd23215194cfc65dd88Chris Lattner if (!tii_->isMoveInstr(*mi, SrcReg, DstReg)) 35491725b75852443923b419fd23215194cfc65dd88Chris Lattner ValNum = interval.getNextValue(~0U, 0); 35591725b75852443923b419fd23215194cfc65dd88Chris Lattner else 35691725b75852443923b419fd23215194cfc65dd88Chris Lattner ValNum = interval.getNextValue(defIndex, SrcReg); 35791725b75852443923b419fd23215194cfc65dd88Chris Lattner 3581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(ValNum == 0 && "First value in interval is not 0?"); 3591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ValNum = 0; // Clue in the optimizer. 3601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 3621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 3631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 3641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 3651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 3661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 3671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned killIdx; 3681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 3691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 3701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 3711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = defIndex+1; 3721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 3741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 3751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 37661de82d8853a02fe39c47302432abb70a586704fEvan Cheng assert(vi.AliveBlocks.none() && 3771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 3781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(defIndex, killIdx, ValNum); 3791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 380bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << "\n"; 3811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 3821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3846097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 3851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 3861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 3871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 3881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 389d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos LiveRange NewLR(defIndex, 390d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 391d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos ValNum); 392bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << NewLR; 3931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 3941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Iterate over all of the blocks that the variable is completely 3961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 3971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live interval. 3981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 3991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.AliveBlocks[i]) { 400428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = mf_->getBlockNumbered(i); 401428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner if (!MBB->empty()) { 402428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner LiveRange LR(getMBBStartIdx(i), 403428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner getInstructionIndex(&MBB->back()) + InstrSlots::NUM, 4041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ValNum); 4051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 406bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 4071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 4121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 4131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 4141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 415428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner LiveRange LR(getMBBStartIdx(Kill->getParent()), 416d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos getUseIndex(getInstructionIndex(Kill))+1, 417d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos ValNum); 4181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 419bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 4201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 4239193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng // Can no longer safely assume definition is rematerializable. 4242638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng interval.remat = NULL; 4252638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng 4261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 4271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 428bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 429bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 430bf105c842450d3308d024be203ddd533f37051ecEvan Cheng if (isReDefinedByTwoAddr(mi, interval.reg, tii_)) { 4311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 4321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 4331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 4341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 4351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 4361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst)); 4376b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned RedefIndex = getDefIndex(MIIdx); 4381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Delete the initial value, which should be short and continuous, 440be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 4411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 442706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 443be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Two-address vregs should always only be redefined once. This means 444be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // that at this point, there should be exactly one value number in it. 445be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 446be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 44791725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 44891725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 44991725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned ValNo = interval.getNextValue(0, 0); 45091725b75852443923b419fd23215194cfc65dd88Chris Lattner interval.setValueNumberInfo(1, interval.getValNumInfo(0)); 451be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 45291725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 45391725b75852443923b419fd23215194cfc65dd88Chris Lattner interval.setValueNumberInfo(0, std::make_pair(~0U, 0U)); 454be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 455be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 456be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 457bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 4581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 4611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 462ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->RegisterDefIsDead(mi, interval.reg)) 463ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0)); 4641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 46556fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " RESULT: "; 466bdc679d564e67a81792e463f6614b0088f975025Bill Wendling interval.print(DOUT, mri_); 4671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 4691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Otherwise, this must be because of phi elimination. If this is the 4701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // first redefinition of the vreg that we have seen, go back and change 4711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range in the PHI block to be a different value number. 4721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.containsOneValue()) { 4731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(vi.Kills.size() == 1 && 4741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "PHI elimination vreg should have one kill, the PHI itself!"); 4751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Remove the old range that we now know has an incorrect number. 4771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Killer = vi.Kills[0]; 478428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned Start = getMBBStartIdx(Killer->getParent()); 4791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 48056fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " Removing [" << Start << "," << End << "] from: "; 481bdc679d564e67a81792e463f6614b0088f975025Bill Wendling interval.print(DOUT, mri_); DOUT << "\n"; 4821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(Start, End); 48356fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " RESULT: "; interval.print(DOUT, mri_); 4841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 485be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Replace the interval with one of a NEW value number. Note that this 486be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // value number isn't actually defined by an instruction, weird huh? :) 48791725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveRange LR(Start, End, interval.getNextValue(~0U, 0)); 488bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 4891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 49056fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " RESULT: "; interval.print(DOUT, mri_); 4911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 4941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 4951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 4966b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 49791725b75852443923b419fd23215194cfc65dd88Chris Lattner 49891725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned ValNum; 49991725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 50091725b75852443923b419fd23215194cfc65dd88Chris Lattner if (!tii_->isMoveInstr(*mi, SrcReg, DstReg)) 50191725b75852443923b419fd23215194cfc65dd88Chris Lattner ValNum = interval.getNextValue(~0U, 0); 50291725b75852443923b419fd23215194cfc65dd88Chris Lattner else 50391725b75852443923b419fd23215194cfc65dd88Chris Lattner ValNum = interval.getNextValue(defIndex, SrcReg); 50491725b75852443923b419fd23215194cfc65dd88Chris Lattner 505706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos LiveRange LR(defIndex, 50691725b75852443923b419fd23215194cfc65dd88Chris Lattner getInstructionIndex(&mbb->back()) + InstrSlots::NUM, ValNum); 5071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 508bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 509dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 5101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 511ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 512bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << '\n'; 513ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 514ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 515f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 516ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 5176b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 51891725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveInterval &interval, 51991725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg) { 5201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 5211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 522bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 5231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5246b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned baseIndex = MIIdx; 5251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned start = getDefIndex(baseIndex); 5261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = start; 5271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 5291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 5301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 531ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->RegisterDefIsDead(mi, interval.reg)) { 532bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 533ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getDefIndex(start) + 1; 534ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 5351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 536ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 5371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 5381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 5391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 5405ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 5411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos baseIndex += InstrSlots::NUM; 542ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->KillsRegister(mi, interval.reg)) { 543bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " killed"; 544ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getUseIndex(baseIndex) + 1; 545ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 5469a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng } else if (lv_->ModifiesRegister(mi, interval.reg)) { 5479a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // Another instruction redefines the register before it is ever read. 5489a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // Then the register is essentially dead at the instruction that defines 5499a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // it. Hence its interval is: 5509a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // [defSlot(def), defSlot(def)+1) 551bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 5529a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng end = getDefIndex(start) + 1; 5539a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng goto exit; 554f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5565ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner 5575ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 5585ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 5595ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // and never used. 56091725b75852443923b419fd23215194cfc65dd88Chris Lattner assert(!SrcReg && "physreg was not killed in defining block!"); 5615ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner end = getDefIndex(start) + 1; // It's dead. 56202ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 563ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 5641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 565f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 56624a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 56724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 56824a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng unsigned Id = (OldLR != interval.end()) 56924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng ? OldLR->ValId 57024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng : interval.getNextValue(SrcReg != 0 ? start : ~0U, SrcReg); 57124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveRange LR(start, end, Id); 5721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 573bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << '\n'; 574ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 575ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 576f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 577f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 5786b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 579f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner unsigned reg) { 580f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner if (MRegisterInfo::isVirtualRegister(reg)) 5816b128bdc58a496e9f08e4d09416330320761baffChris Lattner handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg)); 5825327801fb87e3eda52a33f82e6211181030ecb93Alkis Evlogimenos else if (allocatableRegs_[reg]) { 58391725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 58491725b75852443923b419fd23215194cfc65dd88Chris Lattner if (!tii_->isMoveInstr(*MI, SrcReg, DstReg)) 58591725b75852443923b419fd23215194cfc65dd88Chris Lattner SrcReg = 0; 5866b128bdc58a496e9f08e4d09416330320761baffChris Lattner handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg); 58724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Def of a register also defines its sub-registers. 58824a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng for (const unsigned* AS = mri_->getSubRegisters(reg); *AS; ++AS) 58924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Avoid processing some defs more than once. 59024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng if (!MI->findRegisterDefOperand(*AS)) 59124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0); 592f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5934d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 5944d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 595b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 5969b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned MIIdx, 59724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 598b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 599b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 600b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 601b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 602b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 6039b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned baseIndex = MIIdx; 6049b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned start = baseIndex; 605b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng unsigned end = start; 606b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng while (mi != MBB->end()) { 607b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng if (lv_->KillsRegister(mi, interval.reg)) { 608b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " killed"; 609b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getUseIndex(baseIndex) + 1; 610b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 611b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } else if (lv_->ModifiesRegister(mi, interval.reg)) { 612b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Another instruction redefines the register before it is ever read. 613b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Then the register is essentially dead at the instruction that defines 614b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // it. Hence its interval is: 615b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // [defSlot(def), defSlot(def)+1) 616b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " dead"; 617b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getDefIndex(start) + 1; 618b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 619b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 620b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 621b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng baseIndex += InstrSlots::NUM; 622b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng ++mi; 623b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 624b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 625b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengexit: 62675611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 62775611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng if (end == MIIdx) { 62824a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng DOUT << " dead"; 62975611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng if (isAlias) 63075611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng end = getDefIndex(MIIdx) + 1; 63124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 63224a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 633b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng assert(start < end && "did not find end of interval?"); 634b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 635b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng LiveRange LR(start, end, interval.getNextValue(~0U, 0)); 636b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " +" << LR << '\n'; 6379b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 638b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 639b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 640ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 6414d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 64208cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 643ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 644f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::computeIntervals() { 645bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 646bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << "********** Function: " 647bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'; 6486b128bdc58a496e9f08e4d09416330320761baffChris Lattner // Track the index of the current machine instr. 6496b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIndex = 0; 650428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 651428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 652428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 653bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 6541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 655428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 6560c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 6570c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng if (MBB->livein_begin() != MBB->livein_end()) { 658b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Create intervals for live-ins to this BB first. 659b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 6600c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng LE = MBB->livein_end(); LI != LE; ++LI) { 6619b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 66224a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Multiple live-ins can alias the same register. 66324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS) 66424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng if (!hasInterval(*AS)) 66524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), true); 6660c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng } 667dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 668dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner 669428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (; MI != miEnd; ++MI) { 670bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << MIIndex << "\t" << *MI; 6711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 672438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 673428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 674428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 6751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 676428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner if (MO.isRegister() && MO.getReg() && MO.isDef()) 677428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner handleRegisterDef(MBB, MI, MIIndex, MO.getReg()); 6781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 6796b128bdc58a496e9f08e4d09416330320761baffChris Lattner 6806b128bdc58a496e9f08e4d09416330320761baffChris Lattner MIIndex += InstrSlots::NUM; 681ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 6821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 683ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 684b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 685a1613db62fec94845aa8306232fb665273615badAlkis EvlogimenosLiveInterval LiveIntervals::createInterval(unsigned reg) { 686edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman float Weight = MRegisterInfo::isPhysicalRegister(reg) ? 6877902c75331fa8f38fc8380f5573d935c0d149ef5Jim Laskey HUGE_VALF : 0.0F; 688a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos return LiveInterval(reg, Weight); 6899a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 690