LiveIntervalAnalysis.cpp revision e53f4a055f74bded20d6129b4724ddd17fd199f6
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> 3608a6c7614be9793754b17930ba619e875aef9585Misha Brukman#include <cmath> 372c2c6c61f100bc7c3df873b11203fcea1b5e18feChris Lattner#include <iostream> 38ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 39ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 40ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosnamespace { 411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos RegisterAnalysis<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 42ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos Statistic<> numIntervals 441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ("liveintervals", "Number of original intervals"); 45007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos Statistic<> numIntervalsAfter 471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ("liveintervals", "Number of intervals after coalescing"); 48007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos Statistic<> numJoins 501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ("liveintervals", "Number of interval joins performed"); 51007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos Statistic<> numPeep 531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ("liveintervals", "Number of identity moves eliminated after coalescing"); 54007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos Statistic<> numFolded 561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ("liveintervals", "Number of loads/stores folded into instructions"); 57007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos cl::opt<bool> 591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos EnableJoining("join-liveintervals", 601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos cl::desc("Join compatible live intervals"), 611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos cl::init(true)); 62ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos}; 63ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 64ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const 65ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LiveVariables>(); 671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addPreservedID(PHIEliminationID); 681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(PHIEliminationID); 691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LoopInfo>(); 711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 72ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 73ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 7408cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenosvoid LiveIntervals::releaseMemory() 7508cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos{ 761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_.clear(); 771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_.clear(); 781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2rMap_.clear(); 8008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos} 8108cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos 8208cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos 83ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// runOnMachineFunction - Register allocate the whole function 84ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// 85ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mf_ = &fn; 871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos tm_ = &fn.getTarget(); 881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mri_ = tm_->getRegisterInfo(); 89f768bba43f5c036039851d2fcca8212edca18467Chris Lattner tii_ = tm_->getInstrInfo(); 901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos lv_ = &getAnalysis<LiveVariables>(); 915327801fb87e3eda52a33f82e6211181030ecb93Alkis Evlogimenos allocatableRegs_ = mri_->getAllocatableSet(fn); 922c4f7b5faaeedd97058ec4cfa44177124c42b9e1Alkis Evlogimenos r2rMap_.grow(mf_->getSSARegMap()->getLastVirtReg()); 931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 94799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner // If this function has any live ins, insert a dummy instruction at the 95799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner // beginning of the function that we will pretend "defines" the values. This 96799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner // is to make the interval analysis simpler by providing a number. 97799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner if (fn.livein_begin() != fn.livein_end()) { 98712ad0c36dcfacb30620c793a6ffe4e80bd5d569Chris Lattner unsigned FirstLiveIn = fn.livein_begin()->first; 99799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner 100799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner // Find a reg class that contains this live in. 101799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner const TargetRegisterClass *RC = 0; 102799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner for (MRegisterInfo::regclass_iterator RCI = mri_->regclass_begin(), 103799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner E = mri_->regclass_end(); RCI != E; ++RCI) 104799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner if ((*RCI)->contains(FirstLiveIn)) { 105799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner RC = *RCI; 106799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner break; 107799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner } 108799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner 109799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner MachineInstr *OldFirstMI = fn.begin()->begin(); 110799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner mri_->copyRegToReg(*fn.begin(), fn.begin()->begin(), 111799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner FirstLiveIn, FirstLiveIn, RC); 112799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner assert(OldFirstMI != fn.begin()->begin() && 113799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner "copyRetToReg didn't insert anything!"); 114799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner } 115799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner 1161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // number MachineInstrs 1171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned miIndex = 0; 1181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 1191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mbb != mbbEnd; ++mbb) 1201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 1211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi != miEnd; ++mi) { 1221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos bool inserted = mi2iMap_.insert(std::make_pair(mi, miIndex)).second; 1231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 1241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_.push_back(mi); 1251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos miIndex += InstrSlots::NUM; 1261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 127ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 128799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner // Note intervals due to live-in values. 129799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner if (fn.livein_begin() != fn.livein_end()) { 130799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner MachineBasicBlock *Entry = fn.begin(); 131712ad0c36dcfacb30620c793a6ffe4e80bd5d569Chris Lattner for (MachineFunction::livein_iterator I = fn.livein_begin(), 132799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner E = fn.livein_end(); I != E; ++I) { 133799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner handlePhysicalRegisterDef(Entry, Entry->begin(), 1345ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner getOrCreateInterval(I->first), 0, 0, true); 135712ad0c36dcfacb30620c793a6ffe4e80bd5d569Chris Lattner for (const unsigned* AS = mri_->getAliasSet(I->first); *AS; ++AS) 136799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner handlePhysicalRegisterDef(Entry, Entry->begin(), 1375ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner getOrCreateInterval(*AS), 0, 0, true); 138799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner } 139799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner } 140799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner 1411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 142ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 144843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 14538135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner DEBUG(std::cerr << "********** INTERVALS **********\n"; 14638135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner for (iterator I = begin(), E = end(); I != E; ++I) { 14738135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner I->second.print(std::cerr, mri_); 14838135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner std::cerr << "\n"; 14938135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner }); 1507ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 1511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // join intervals if requested 1521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (EnableJoining) joinIntervals(); 1531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervalsAfter += getNumIntervals(); 1551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // perform a final pass over the instructions and compute spill 1571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // weights, coalesce virtual registers and remove identity moves 1581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos const LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 1591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 1611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mbbi != mbbe; ++mbbi) { 1621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineBasicBlock* mbb = mbbi; 1631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 1641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); 1661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mii != mie; ) { 1671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // if the move will be an identity move delete it 1681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned srcReg, dstReg, RegRep; 169f768bba43f5c036039851d2fcca8212edca18467Chris Lattner if (tii_->isMoveInstr(*mii, srcReg, dstReg) && 1701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos (RegRep = rep(srcReg)) == rep(dstReg)) { 1711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // remove from def list 1721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveInterval &interval = getOrCreateInterval(RegRep); 1731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // remove index -> MachineInstr and 1741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // MachineInstr -> index mappings 1751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos Mi2IndexMap::iterator mi2i = mi2iMap_.find(mii); 1761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (mi2i != mi2iMap_.end()) { 1771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_[mi2i->second/InstrSlots::NUM] = 0; 1781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_.erase(mi2i); 1791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mii = mbbi->erase(mii); 1811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ++numPeep; 1821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else { 1841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0; i < mii->getNumOperands(); ++i) { 1851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos const MachineOperand& mop = mii->getOperand(i); 1861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (mop.isRegister() && mop.getReg() && 1871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MRegisterInfo::isVirtualRegister(mop.getReg())) { 1881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // replace register with representative register 1891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned reg = rep(mop.getReg()); 190e53f4a055f74bded20d6129b4724ddd17fd199f6Chris Lattner mii->getOperand(i).setReg(reg); 1911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveInterval &RegInt = getInterval(reg); 1931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos RegInt.weight += 1947a36ae8b0103088328e3a4992ac08b3dce312248Chris Lattner (mop.isUse() + mop.isDef()) * pow(10.0F, (int)loopDepth); 1951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ++mii; 1981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2017a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 20270ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 2031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 204ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 205ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 20670ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 207ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencervoid LiveIntervals::print(std::ostream &O, const Module* ) const { 20870ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** INTERVALS **********\n"; 2098e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 2108e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner I->second.print(std::cerr, mri_); 2118e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner std::cerr << "\n"; 2128e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 21370ca358b7d540b6061236ddf757085042873c12cChris Lattner 21470ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** MACHINEINSTRS **********\n"; 21570ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 21670ca358b7d540b6061236ddf757085042873c12cChris Lattner mbbi != mbbe; ++mbbi) { 21770ca358b7d540b6061236ddf757085042873c12cChris Lattner O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 21870ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineBasicBlock::iterator mii = mbbi->begin(), 21970ca358b7d540b6061236ddf757085042873c12cChris Lattner mie = mbbi->end(); mii != mie; ++mii) { 220477e4555de341c5de780de3720d6f115ec133c4eChris Lattner O << getInstructionIndex(mii) << '\t' << *mii; 22170ca358b7d540b6061236ddf757085042873c12cChris Lattner } 22270ca358b7d540b6061236ddf757085042873c12cChris Lattner } 22370ca358b7d540b6061236ddf757085042873c12cChris Lattner} 22470ca358b7d540b6061236ddf757085042873c12cChris Lattner 22570ca358b7d540b6061236ddf757085042873c12cChris Lattnerstd::vector<LiveInterval*> LiveIntervals:: 22670ca358b7d540b6061236ddf757085042873c12cChris LattneraddIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { 227d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // since this is called after the analysis is done we don't know if 228d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // LiveVariables is available 229d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos lv_ = getAnalysisToUpdate<LiveVariables>(); 230d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos 2311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos std::vector<LiveInterval*> added; 2321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(li.weight != HUGE_VAL && 2341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "attempt to spill already spilled interval!"); 2351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tadding intervals for spills for interval: " 2371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos << li << '\n'); 2381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg); 2401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (LiveInterval::Ranges::const_iterator 2421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 2431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned index = getBaseIndex(i->start); 2441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = getBaseIndex(i->end-1) + InstrSlots::NUM; 2451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (; index != end; index += InstrSlots::NUM) { 2461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // skip deleted instructions 2471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos while (index != end && !getInstructionFromIndex(index)) 2481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos index += InstrSlots::NUM; 2491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (index == end) break; 2501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2513b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner MachineInstr *MI = getInstructionFromIndex(index); 2521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 253b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // NewRegLiveIn - This instruction might have multiple uses of the spilled 254b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // register. In this case, for the first use, keep track of the new vreg 255b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // that we reload it into. If we see a second use, reuse this vreg 256b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // instead of creating live ranges for two reloads. 257b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner unsigned NewRegLiveIn = 0; 258b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner 2591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for_operand: 2603b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 2613b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner MachineOperand& mop = MI->getOperand(i); 2621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (mop.isRegister() && mop.getReg() == li.reg) { 263b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner if (NewRegLiveIn && mop.isUse()) { 264b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // We already emitted a reload of this value, reuse it for 265b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // subsequent operands. 266e53f4a055f74bded20d6129b4724ddd17fd199f6Chris Lattner MI->getOperand(i).setReg(NewRegLiveIn); 267b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner DEBUG(std::cerr << "\t\t\t\treused reload into reg" << NewRegLiveIn 268b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner << " for operand #" << i << '\n'); 2693b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner } else if (MachineInstr* fmi = mri_->foldMemoryOperand(MI, i, slot)) { 270b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // Attempt to fold the memory reference into the instruction. If we 271b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // can do this, we don't need to insert spill code. 272d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos if (lv_) 2733b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner lv_->instructionChanged(MI, fmi); 274200370fb5617a1719f0054804b412469ce486ebdEvan Cheng MachineBasicBlock &MBB = *MI->getParent(); 27535f2705e3de4600c3621b883eed9b22e4607ddf4Chris Lattner vrm.virtFolded(li.reg, MI, i, fmi); 2763b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner mi2iMap_.erase(MI); 2771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_[index/InstrSlots::NUM] = fmi; 2781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_[fmi] = index; 2793b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner MI = MBB.insert(MBB.erase(MI), fmi); 2801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ++numFolded; 281477e4555de341c5de780de3720d6f115ec133c4eChris Lattner // Folding the load/store can completely change the instruction in 282477e4555de341c5de780de3720d6f115ec133c4eChris Lattner // unpredictable ways, rescan it from the beginning. 2831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos goto for_operand; 284477e4555de341c5de780de3720d6f115ec133c4eChris Lattner } else { 28570ca358b7d540b6061236ddf757085042873c12cChris Lattner // This is tricky. We need to add information in the interval about 28670ca358b7d540b6061236ddf757085042873c12cChris Lattner // the spill code so we have to use our extra load/store slots. 2871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // 28870ca358b7d540b6061236ddf757085042873c12cChris Lattner // If we have a use we are going to have a load so we start the 28970ca358b7d540b6061236ddf757085042873c12cChris Lattner // interval from the load slot onwards. Otherwise we start from the 29070ca358b7d540b6061236ddf757085042873c12cChris Lattner // def slot. 2911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned start = (mop.isUse() ? 2921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos getLoadIndex(index) : 2931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos getDefIndex(index)); 29470ca358b7d540b6061236ddf757085042873c12cChris Lattner // If we have a def we are going to have a store right after it so 29570ca358b7d540b6061236ddf757085042873c12cChris Lattner // we end the interval after the use of the next 29670ca358b7d540b6061236ddf757085042873c12cChris Lattner // instruction. Otherwise we end after the use of this instruction. 2971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = 1 + (mop.isDef() ? 2981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos getStoreIndex(index) : 2991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos getUseIndex(index)); 3001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // create a new register for this spill 302b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner NewRegLiveIn = mf_->getSSARegMap()->createVirtualRegister(rc); 303e53f4a055f74bded20d6129b4724ddd17fd199f6Chris Lattner MI->getOperand(i).setReg(NewRegLiveIn); 3041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos vrm.grow(); 305b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner vrm.assignVirt2StackSlot(NewRegLiveIn, slot); 306b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner LiveInterval& nI = getOrCreateInterval(NewRegLiveIn); 3071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(nI.empty()); 30870ca358b7d540b6061236ddf757085042873c12cChris Lattner 3091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the spill weight is now infinity as it 3101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // cannot be spilled again 31128696bee024805a6b191cfe12e1a24784dae8aa7Chris Lattner nI.weight = float(HUGE_VAL); 3121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(start, end, nI.getNextValue()); 3131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR); 3141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos nI.addRange(LR); 3151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos added.push_back(&nI); 31670ca358b7d540b6061236ddf757085042873c12cChris Lattner 317d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // update live variables if it is available 318d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos if (lv_) 3193b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner lv_->addVirtualRegisterKilled(NewRegLiveIn, MI); 320b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner 321b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // If this is a live in, reuse it for subsequent live-ins. If it's 322b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // a def, we can't do this. 323b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner if (!mop.isUse()) NewRegLiveIn = 0; 324b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner 325d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tadded new interval: " << nI << '\n'); 3261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 327843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 3281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 329843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 3301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 33126f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos 3321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return added; 333843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos} 334843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 335ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::printRegName(unsigned reg) const 336ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 3371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(reg)) 3381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos std::cerr << mri_->getName(reg); 3391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 3401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos std::cerr << "%reg" << reg; 341ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 342ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 343ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 344ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 345418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner LiveInterval& interval) 346ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 3471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); 3481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 3491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 350706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 351706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 352706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 3531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 3541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 3551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 3561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned defIndex = getDefIndex(getInstructionIndex(mi)); 3571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned ValNum = interval.getNextValue(); 3591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(ValNum == 0 && "First value in interval is not 0?"); 3601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ValNum = 0; // Clue in the optimizer. 3611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 3631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 3641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 3651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 3661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 3671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 3681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned killIdx; 3691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 3701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 3711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 3721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = defIndex+1; 3731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 3751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 3761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 377706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos assert(vi.AliveBlocks.empty() && 3781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 3791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(defIndex, killIdx, ValNum); 3801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR << "\n"); 3821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 3831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3856097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 3861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 3871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 3881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 3891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 390d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos LiveRange NewLR(defIndex, 391d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 392d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos ValNum); 3931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << NewLR); 3941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 3951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Iterate over all of the blocks that the variable is completely 3971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 3981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live interval. 3991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 4001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.AliveBlocks[i]) { 4011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineBasicBlock* mbb = mf_->getBlockNumbered(i); 4021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (!mbb->empty()) { 4031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(getInstructionIndex(&mbb->front()), 404d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 4051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ValNum); 4061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR); 4081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 4131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 4141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 4151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 4161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(getInstructionIndex(Kill->getParent()->begin()), 417d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos getUseIndex(getInstructionIndex(Kill))+1, 418d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos ValNum); 4191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR); 4211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 4241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 4251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 4261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the result of two address elimination, then the vreg is the first 4271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // operand, and is a def-and-use. 428706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos if (mi->getOperand(0).isRegister() && 4291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi->getOperand(0).getReg() == interval.reg && 4301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi->getOperand(0).isDef() && mi->getOperand(0).isUse()) { 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)); 4371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned RedefIndex = getDefIndex(getInstructionIndex(mi)); 4381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Delete the initial value, which should be short and continuous, 4401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // becuase the 2-addr copy must be in the same MBB as the redef. 4411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 442706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 4431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(DefIndex, RedefIndex, interval.getNextValue()); 4441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " replace range with " << LR); 4451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 4481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 449ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->RegisterDefIsDead(mi, interval.reg)) 450ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0)); 4511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "RESULT: " << interval); 4531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 4551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Otherwise, this must be because of phi elimination. If this is the 4561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // first redefinition of the vreg that we have seen, go back and change 4571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range in the PHI block to be a different value number. 4581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.containsOneValue()) { 4591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(vi.Kills.size() == 1 && 4601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "PHI elimination vreg should have one kill, the PHI itself!"); 4611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Remove the old range that we now know has an incorrect number. 4631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Killer = vi.Kills[0]; 4641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned Start = getInstructionIndex(Killer->getParent()->begin()); 4651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 4661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "Removing [" << Start << "," << End << "] from: " 4671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos << interval << "\n"); 4681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(Start, End); 4691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "RESULT: " << interval); 4701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Replace the interval with one of a NEW value number. 4721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(Start, End, interval.getNextValue()); 4731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " replace range with " << LR); 4741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "RESULT: " << interval); 4761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 4791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 4801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 4811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned defIndex = getDefIndex(getInstructionIndex(mi)); 482706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos LiveRange LR(defIndex, 4831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 4841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.getNextValue()); 4851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR); 487dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 4881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 489ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 4901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << '\n'); 491ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 492ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 493f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 494ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 495f768bba43f5c036039851d2fcca8212edca18467Chris Lattner LiveInterval& interval, 4965ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner unsigned SrcReg, unsigned DestReg, 4975ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner bool isLiveIn) 498ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 4991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 5001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 5011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); 5021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos typedef LiveVariables::killed_iterator KillIter; 5031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned baseIndex = getInstructionIndex(mi); 5051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned start = getDefIndex(baseIndex); 5061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = start; 5071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 5091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 5101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 511ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->RegisterDefIsDead(mi, interval.reg)) { 512ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner DEBUG(std::cerr << " dead"); 513ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getDefIndex(start) + 1; 514ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 5151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 516ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 5171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 5181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 5191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 5205ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 5211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos baseIndex += InstrSlots::NUM; 522ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->KillsRegister(mi, interval.reg)) { 523ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner DEBUG(std::cerr << " killed"); 524ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getUseIndex(baseIndex) + 1; 525ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 526f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5285ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner 5295ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 5305ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 5315ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // and never used. 5325ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner assert(isLiveIn && "physreg was not killed in defining block!"); 5335ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner end = getDefIndex(start) + 1; // It's dead. 53402ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 535ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 5361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 537f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 538f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // Finally, if this is defining a new range for the physical register, and if 539f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // that physreg is just a copy from a vreg, and if THAT vreg was a copy from 540f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // the physreg, then the new fragment has the same value as the one copied 541f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // into the vreg. 542f768bba43f5c036039851d2fcca8212edca18467Chris Lattner if (interval.reg == DestReg && !interval.empty() && 543e97568c3c41e6de2b726d2cd99724659650e9614Chris Lattner MRegisterInfo::isVirtualRegister(SrcReg)) { 544f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 545f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // Get the live interval for the vreg, see if it is defined by a copy. 546f768bba43f5c036039851d2fcca8212edca18467Chris Lattner LiveInterval &SrcInterval = getOrCreateInterval(SrcReg); 547f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 548f768bba43f5c036039851d2fcca8212edca18467Chris Lattner if (SrcInterval.containsOneValue()) { 549f768bba43f5c036039851d2fcca8212edca18467Chris Lattner assert(!SrcInterval.empty() && "Can't contain a value and be empty!"); 550f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 551f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // Get the first index of the first range. Though the interval may have 552f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // multiple liveranges in it, we only check the first. 553f768bba43f5c036039851d2fcca8212edca18467Chris Lattner unsigned StartIdx = SrcInterval.begin()->start; 554f768bba43f5c036039851d2fcca8212edca18467Chris Lattner MachineInstr *SrcDefMI = getInstructionFromIndex(StartIdx); 555f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 556f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // Check to see if the vreg was defined by a copy instruction, and that 557f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // the source was this physreg. 558f768bba43f5c036039851d2fcca8212edca18467Chris Lattner unsigned VRegSrcSrc, VRegSrcDest; 559f768bba43f5c036039851d2fcca8212edca18467Chris Lattner if (tii_->isMoveInstr(*SrcDefMI, VRegSrcSrc, VRegSrcDest) && 560f768bba43f5c036039851d2fcca8212edca18467Chris Lattner SrcReg == VRegSrcDest && VRegSrcSrc == DestReg) { 561f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // Okay, now we know that the vreg was defined by a copy from this 562f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // physreg. Find the value number being copied and use it as the value 563f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // for this range. 564f768bba43f5c036039851d2fcca8212edca18467Chris Lattner const LiveRange *DefRange = interval.getLiveRangeContaining(StartIdx-1); 565f768bba43f5c036039851d2fcca8212edca18467Chris Lattner if (DefRange) { 566f768bba43f5c036039851d2fcca8212edca18467Chris Lattner LiveRange LR(start, end, DefRange->ValId); 567f768bba43f5c036039851d2fcca8212edca18467Chris Lattner interval.addRange(LR); 568f768bba43f5c036039851d2fcca8212edca18467Chris Lattner DEBUG(std::cerr << " +" << LR << '\n'); 569f768bba43f5c036039851d2fcca8212edca18467Chris Lattner return; 570f768bba43f5c036039851d2fcca8212edca18467Chris Lattner } 571f768bba43f5c036039851d2fcca8212edca18467Chris Lattner } 572f768bba43f5c036039851d2fcca8212edca18467Chris Lattner } 573f768bba43f5c036039851d2fcca8212edca18467Chris Lattner } 574f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 575f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 5761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(start, end, interval.getNextValue()); 5771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 5781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR << '\n'); 579ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 580ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 581f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 582f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 583f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner unsigned reg) { 584f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner if (MRegisterInfo::isVirtualRegister(reg)) 585f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner handleVirtualRegisterDef(MBB, MI, getOrCreateInterval(reg)); 5865327801fb87e3eda52a33f82e6211181030ecb93Alkis Evlogimenos else if (allocatableRegs_[reg]) { 587f768bba43f5c036039851d2fcca8212edca18467Chris Lattner unsigned SrcReg = 0, DestReg = 0; 58860d97d4f55b6bd51179eba3388c95d5ec6942ec8Chris Lattner if (!tii_->isMoveInstr(*MI, SrcReg, DestReg)) 58960d97d4f55b6bd51179eba3388c95d5ec6942ec8Chris Lattner SrcReg = DestReg = 0; 590f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 591f768bba43f5c036039851d2fcca8212edca18467Chris Lattner handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(reg), 592f768bba43f5c036039851d2fcca8212edca18467Chris Lattner SrcReg, DestReg); 593f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner for (const unsigned* AS = mri_->getAliasSet(reg); *AS; ++AS) 594f768bba43f5c036039851d2fcca8212edca18467Chris Lattner handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(*AS), 595f768bba43f5c036039851d2fcca8212edca18467Chris Lattner SrcReg, DestReg); 596f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5974d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 5984d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 599ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 6004d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 60108cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 602ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 603ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::computeIntervals() 604ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 6051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "********** COMPUTING LIVE INTERVALS **********\n"); 6061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "********** Function: " 6071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos << ((Value*)mf_->getFunction())->getName() << '\n'); 608799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner bool IgnoreFirstInstr = mf_->livein_begin() != mf_->livein_end(); 6091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 610706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 6111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos I != E; ++I) { 6121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineBasicBlock* mbb = I; 6131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << ((Value*)mbb->getBasicBlock())->getName() << ":\n"); 6141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 615799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 616799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner if (IgnoreFirstInstr) { ++mi; IgnoreFirstInstr = false; } 617799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner for (; mi != miEnd; ++mi) { 6181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos const TargetInstrDescriptor& tid = 6191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos tm_->getInstrInfo()->get(mi->getOpcode()); 620477e4555de341c5de780de3720d6f115ec133c4eChris Lattner DEBUG(std::cerr << getInstructionIndex(mi) << "\t" << *mi); 6211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 6221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle implicit defs 6231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 6241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos handleRegisterDef(mbb, mi, *id); 6251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 6261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle explicit defs 6271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (int i = mi->getNumOperands() - 1; i >= 0; --i) { 6281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineOperand& mop = mi->getOperand(i); 6291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 6301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (mop.isRegister() && mop.getReg() && mop.isDef()) 6311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos handleRegisterDef(mbb, mi, mop.getReg()); 6321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 633ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 6341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 635ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 636b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 637aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner/// IntA is defined as a copy from IntB and we know it only has one value 638aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner/// number. If all of the places that IntA and IntB overlap are defined by 639aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner/// copies from IntA to IntB, we know that these two ranges can really be 640aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner/// merged if we adjust the value numbers. If it is safe, adjust the value 641c60e6020c0dd1260b0d60835e2ab823f97a4b810Chris Lattner/// numbers and return true, allowing coalescing to occur. 642aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattnerbool LiveIntervals:: 643aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris LattnerAdjustIfAllOverlappingRangesAreCopiesFrom(LiveInterval &IntA, 644aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner LiveInterval &IntB, 645aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner unsigned CopyIdx) { 646aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner std::vector<LiveRange*> Ranges; 647aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner IntA.getOverlapingRanges(IntB, CopyIdx, Ranges); 648aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 649aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner assert(!Ranges.empty() && "Why didn't we do a simple join of this?"); 650aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 651aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner unsigned IntBRep = rep(IntB.reg); 652aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 653aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // Check to see if all of the overlaps (entries in Ranges) are defined by a 654aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // copy from IntA. If not, exit. 655aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner for (unsigned i = 0, e = Ranges.size(); i != e; ++i) { 656aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner unsigned Idx = Ranges[i]->start; 657aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner MachineInstr *MI = getInstructionFromIndex(Idx); 658aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner unsigned SrcReg, DestReg; 659aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (!tii_->isMoveInstr(*MI, SrcReg, DestReg)) return false; 660aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 661aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // If this copy isn't actually defining this range, it must be a live 662aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // range spanning basic blocks or something. 663aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (rep(DestReg) != rep(IntA.reg)) return false; 664aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 665aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // Check to see if this is coming from IntB. If not, bail out. 666aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (rep(SrcReg) != IntBRep) return false; 667aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner } 668aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 669aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // Okay, we can change this one. Get the IntB value number that IntA is 670aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // copied from. 671aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner unsigned ActualValNo = IntA.getLiveRangeContaining(CopyIdx-1)->ValId; 672aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 673aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // Change all of the value numbers to the same as what we IntA is copied from. 674aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner for (unsigned i = 0, e = Ranges.size(); i != e; ++i) 675aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner Ranges[i]->ValId = ActualValNo; 676aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 677aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner return true; 678aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner} 679aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 6801c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattnervoid LiveIntervals::joinIntervalsInMachineBB(MachineBasicBlock *MBB) { 6817ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner DEBUG(std::cerr << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); 6827ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 6837ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner for (MachineBasicBlock::iterator mi = MBB->begin(), mie = MBB->end(); 6847ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner mi != mie; ++mi) { 6857ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner DEBUG(std::cerr << getInstructionIndex(mi) << '\t' << *mi); 6867ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 6877ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // we only join virtual registers with allocatable 6887ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // physical registers since we do not have liveness information 6897ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // on not allocatable physical registers 690aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner unsigned SrcReg, DestReg; 691aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (tii_->isMoveInstr(*mi, SrcReg, DestReg) && 692aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner (MRegisterInfo::isVirtualRegister(SrcReg) || allocatableRegs_[SrcReg])&& 693aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner (MRegisterInfo::isVirtualRegister(DestReg)||allocatableRegs_[DestReg])){ 694706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 6957ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // Get representative registers. 696aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner SrcReg = rep(SrcReg); 697aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner DestReg = rep(DestReg); 698706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 6997ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // If they are already joined we continue. 700aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (SrcReg == DestReg) 7017ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner continue; 702706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 7037ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // If they are both physical registers, we cannot join them. 704aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (MRegisterInfo::isPhysicalRegister(SrcReg) && 705aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner MRegisterInfo::isPhysicalRegister(DestReg)) 7067ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner continue; 7077ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 7087ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // If they are not of the same register class, we cannot join them. 709aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (differingRegisterClasses(SrcReg, DestReg)) 7107ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner continue; 7117ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 712aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner LiveInterval &SrcInt = getInterval(SrcReg); 713aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner LiveInterval &DestInt = getInterval(DestReg); 714aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner assert(SrcInt.reg == SrcReg && DestInt.reg == DestReg && 7157ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner "Register mapping is horribly broken!"); 716060913cce42d8b746194c7ebd8b19c9789a03909Chris Lattner 717aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner DEBUG(std::cerr << "\t\tInspecting " << SrcInt << " and " << DestInt 718aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner << ": "); 719060913cce42d8b746194c7ebd8b19c9789a03909Chris Lattner 7204df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner // If two intervals contain a single value and are joined by a copy, it 7214df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner // does not matter if the intervals overlap, they can always be joined. 722aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner bool Joinable = SrcInt.containsOneValue() && DestInt.containsOneValue(); 7237ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 7247ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner unsigned MIDefIdx = getDefIndex(getInstructionIndex(mi)); 725aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 726aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // If the intervals think that this is joinable, do so now. 727aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (!Joinable && DestInt.joinable(SrcInt, MIDefIdx)) 728aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner Joinable = true; 729aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 730aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // If DestInt is actually a copy from SrcInt (which we know) that is used 731aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // to define another value of SrcInt, we can change the other range of 732aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // SrcInt to be the value of the range that defines DestInt, allowing a 733c60e6020c0dd1260b0d60835e2ab823f97a4b810Chris Lattner // coalesce. 734aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (!Joinable && DestInt.containsOneValue() && 735aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner AdjustIfAllOverlappingRangesAreCopiesFrom(SrcInt, DestInt, MIDefIdx)) 736aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner Joinable = true; 737aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 738aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (!Joinable || overlapsAliases(&SrcInt, &DestInt)) { 739aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner DEBUG(std::cerr << "Interference!\n"); 740aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner } else { 741aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner DestInt.join(SrcInt, MIDefIdx); 742aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner DEBUG(std::cerr << "Joined. Result = " << DestInt << "\n"); 743aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 744aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (!MRegisterInfo::isPhysicalRegister(SrcReg)) { 745aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner r2iMap_.erase(SrcReg); 746aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner r2rMap_[SrcReg] = DestReg; 7477ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner } else { 7487ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // Otherwise merge the data structures the other way so we don't lose 7497ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // the physreg information. 750aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner r2rMap_[DestReg] = SrcReg; 751aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner DestInt.reg = SrcReg; 752aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner SrcInt.swap(DestInt); 753aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner r2iMap_.erase(DestReg); 754e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 7557ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner ++numJoins; 7567ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner } 757dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 7587ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner } 759dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 760dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 761cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattnernamespace { 762cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // DepthMBBCompare - Comparison predicate that sort first based on the loop 763cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // depth of the basic block (the unsigned), and then on the MBB number. 764cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner struct DepthMBBCompare { 765cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; 766cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { 767cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner if (LHS.first > RHS.first) return true; // Deeper loops first 768706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos return LHS.first == RHS.first && 7691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LHS.second->getNumber() < RHS.second->getNumber(); 770cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner } 771cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner }; 772cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner} 773cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner 774cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattnervoid LiveIntervals::joinIntervals() { 775cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner DEBUG(std::cerr << "********** JOINING INTERVALS ***********\n"); 7761c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner 777cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner const LoopInfo &LI = getAnalysis<LoopInfo>(); 778cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner if (LI.begin() == LI.end()) { 779cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // If there are no loops in the function, join intervals in function order. 7801c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 7811c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner I != E; ++I) 7821c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner joinIntervalsInMachineBB(I); 783cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner } else { 784cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // Otherwise, join intervals in inner loops before other intervals. 785cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // Unfortunately we can't just iterate over loop hierarchy here because 786cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // there may be more MBB's than BB's. Collect MBB's for sorting. 787cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; 788cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 789cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner I != E; ++I) 790cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner MBBs.push_back(std::make_pair(LI.getLoopDepth(I->getBasicBlock()), I)); 791cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner 792cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // Sort by loop depth. 793cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); 794cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner 795706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Finally, join intervals in loop nest order. 796cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 797cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner joinIntervalsInMachineBB(MBBs[i].second); 798cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner } 799c83e40d1b6582155286f1044623d544dea20202eChris Lattner 800c83e40d1b6582155286f1044623d544dea20202eChris Lattner DEBUG(std::cerr << "*** Register mapping ***\n"); 8015d0d1e350a30772fd70798b5733bb060febd7b0dAlkis Evlogimenos DEBUG(for (int i = 0, e = r2rMap_.size(); i != e; ++i) 8025d0d1e350a30772fd70798b5733bb060febd7b0dAlkis Evlogimenos if (r2rMap_[i]) 8035d0d1e350a30772fd70798b5733bb060febd7b0dAlkis Evlogimenos std::cerr << " reg " << i << " -> reg " << r2rMap_[i] << "\n"); 8041c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner} 8051c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner 8067ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner/// Return true if the two specified registers belong to different register 8077ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner/// classes. The registers may be either phys or virt regs. 8087ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattnerbool LiveIntervals::differingRegisterClasses(unsigned RegA, 8097ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner unsigned RegB) const { 8107ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 8117ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // Get the register classes for the first reg. 812ad3c74fc9b52b652859807580c8e40b67394d689Chris Lattner if (MRegisterInfo::isPhysicalRegister(RegA)) { 813edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman assert(MRegisterInfo::isVirtualRegister(RegB) && 814ad3c74fc9b52b652859807580c8e40b67394d689Chris Lattner "Shouldn't consider two physregs!"); 815ad3c74fc9b52b652859807580c8e40b67394d689Chris Lattner return !mf_->getSSARegMap()->getRegClass(RegB)->contains(RegA); 816ad3c74fc9b52b652859807580c8e40b67394d689Chris Lattner } 8177ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 8187ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // Compare against the regclass for the second reg. 819ad3c74fc9b52b652859807580c8e40b67394d689Chris Lattner const TargetRegisterClass *RegClass = mf_->getSSARegMap()->getRegClass(RegA); 8207ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner if (MRegisterInfo::isVirtualRegister(RegB)) 8217ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner return RegClass != mf_->getSSARegMap()->getRegClass(RegB); 8227ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner else 823d0d0a1a08f9e27f4c950e846e0a21c3c3f11e40cChris Lattner return !RegClass->contains(RegB); 8247ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner} 8257ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 8267ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattnerbool LiveIntervals::overlapsAliases(const LiveInterval *LHS, 8277ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner const LiveInterval *RHS) const { 8287ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner if (!MRegisterInfo::isPhysicalRegister(LHS->reg)) { 8297ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner if (!MRegisterInfo::isPhysicalRegister(RHS->reg)) 8307ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner return false; // vreg-vreg merge has no aliases! 8317ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner std::swap(LHS, RHS); 8327ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner } 8337ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 8347ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner assert(MRegisterInfo::isPhysicalRegister(LHS->reg) && 8357ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner MRegisterInfo::isVirtualRegister(RHS->reg) && 8367ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner "first interval must describe a physical register"); 83779b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 8384df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner for (const unsigned *AS = mri_->getAliasSet(LHS->reg); *AS; ++AS) 8394df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner if (RHS->overlaps(getInterval(*AS))) 8404df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner return true; 84179b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 8424df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner return false; 84379b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos} 84479b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 845a1613db62fec94845aa8306232fb665273615badAlkis EvlogimenosLiveInterval LiveIntervals::createInterval(unsigned reg) { 846edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman float Weight = MRegisterInfo::isPhysicalRegister(reg) ? 84728696bee024805a6b191cfe12e1a24784dae8aa7Chris Lattner (float)HUGE_VAL :0.0F; 848a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos return LiveInterval(reg, Weight); 8499a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 850