LiveIntervalAnalysis.cpp revision 7c10b0d2c9b4d637edf27548c104b7199b0e3578
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 43ed41f1bb1981a98eea63f00c5988cf62bbdd7c59Andrew Lenharth static Statistic<> numIntervals 441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ("liveintervals", "Number of original intervals"); 45007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 46ed41f1bb1981a98eea63f00c5988cf62bbdd7c59Andrew Lenharth static Statistic<> numIntervalsAfter 471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ("liveintervals", "Number of intervals after coalescing"); 48007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 49ed41f1bb1981a98eea63f00c5988cf62bbdd7c59Andrew Lenharth static Statistic<> numJoins 501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ("liveintervals", "Number of interval joins performed"); 51007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 52ed41f1bb1981a98eea63f00c5988cf62bbdd7c59Andrew Lenharth static Statistic<> numPeep 531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ("liveintervals", "Number of identity moves eliminated after coalescing"); 54007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 55ed41f1bb1981a98eea63f00c5988cf62bbdd7c59Andrew Lenharth static Statistic<> numFolded 561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ("liveintervals", "Number of loads/stores folded into instructions"); 57007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 58ed41f1bb1981a98eea63f00c5988cf62bbdd7c59Andrew Lenharth static cl::opt<bool> 591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos EnableJoining("join-liveintervals", 601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos cl::desc("Join compatible live intervals"), 611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos cl::init(true)); 62d74ea2bbd8bb630331f35ead42d385249bd42af8Chris Lattner} 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 83993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Chengstatic bool isZeroLengthInterval(LiveInterval *li) { 84993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng for (LiveInterval::Ranges::const_iterator 85993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i) 86993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng if (i->end - i->start > LiveIntervals::InstrSlots::NUM) 87993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng return false; 88993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng return true; 89993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 90993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 91993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 92ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// runOnMachineFunction - Register allocate the whole function 93ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// 94ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mf_ = &fn; 961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos tm_ = &fn.getTarget(); 971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mri_ = tm_->getRegisterInfo(); 98f768bba43f5c036039851d2fcca8212edca18467Chris Lattner tii_ = tm_->getInstrInfo(); 991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos lv_ = &getAnalysis<LiveVariables>(); 1005327801fb87e3eda52a33f82e6211181030ecb93Alkis Evlogimenos allocatableRegs_ = mri_->getAllocatableSet(fn); 1012c4f7b5faaeedd97058ec4cfa44177124c42b9e1Alkis Evlogimenos r2rMap_.grow(mf_->getSSARegMap()->getLastVirtReg()); 1021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 103799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner // If this function has any live ins, insert a dummy instruction at the 104799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner // beginning of the function that we will pretend "defines" the values. This 105799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner // is to make the interval analysis simpler by providing a number. 106799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner if (fn.livein_begin() != fn.livein_end()) { 107712ad0c36dcfacb30620c793a6ffe4e80bd5d569Chris Lattner unsigned FirstLiveIn = fn.livein_begin()->first; 108799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner 109799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner // Find a reg class that contains this live in. 110799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner const TargetRegisterClass *RC = 0; 111799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner for (MRegisterInfo::regclass_iterator RCI = mri_->regclass_begin(), 112799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner E = mri_->regclass_end(); RCI != E; ++RCI) 113799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner if ((*RCI)->contains(FirstLiveIn)) { 114799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner RC = *RCI; 115799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner break; 116799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner } 117799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner 118799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner MachineInstr *OldFirstMI = fn.begin()->begin(); 119799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner mri_->copyRegToReg(*fn.begin(), fn.begin()->begin(), 120799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner FirstLiveIn, FirstLiveIn, RC); 121799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner assert(OldFirstMI != fn.begin()->begin() && 122799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner "copyRetToReg didn't insert anything!"); 123799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner } 124799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner 1251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // number MachineInstrs 1261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned miIndex = 0; 1271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 1281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mbb != mbbEnd; ++mbb) 1291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 1301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi != miEnd; ++mi) { 1311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos bool inserted = mi2iMap_.insert(std::make_pair(mi, miIndex)).second; 1321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 1331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_.push_back(mi); 1341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos miIndex += InstrSlots::NUM; 1351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 136ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 137799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner // Note intervals due to live-in values. 138799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner if (fn.livein_begin() != fn.livein_end()) { 139799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner MachineBasicBlock *Entry = fn.begin(); 140712ad0c36dcfacb30620c793a6ffe4e80bd5d569Chris Lattner for (MachineFunction::livein_iterator I = fn.livein_begin(), 141799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner E = fn.livein_end(); I != E; ++I) { 142799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner handlePhysicalRegisterDef(Entry, Entry->begin(), 1435ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner getOrCreateInterval(I->first), 0, 0, true); 144712ad0c36dcfacb30620c793a6ffe4e80bd5d569Chris Lattner for (const unsigned* AS = mri_->getAliasSet(I->first); *AS; ++AS) 145799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner handlePhysicalRegisterDef(Entry, Entry->begin(), 1465ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner getOrCreateInterval(*AS), 0, 0, true); 147799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner } 148799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner } 149799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner 1501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 151ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 153843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 15438135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner DEBUG(std::cerr << "********** INTERVALS **********\n"; 15538135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner for (iterator I = begin(), E = end(); I != E; ++I) { 15638135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner I->second.print(std::cerr, mri_); 15738135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner std::cerr << "\n"; 15838135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner }); 1597ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 1601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // join intervals if requested 1611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (EnableJoining) joinIntervals(); 1621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervalsAfter += getNumIntervals(); 1641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // perform a final pass over the instructions and compute spill 1661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // weights, coalesce virtual registers and remove identity moves 1671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos const LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 1681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 1701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mbbi != mbbe; ++mbbi) { 1711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineBasicBlock* mbb = mbbi; 1721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 1731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); 1751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mii != mie; ) { 1761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // if the move will be an identity move delete it 1771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned srcReg, dstReg, RegRep; 178f768bba43f5c036039851d2fcca8212edca18467Chris Lattner if (tii_->isMoveInstr(*mii, srcReg, dstReg) && 1791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos (RegRep = rep(srcReg)) == rep(dstReg)) { 1801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // remove from def list 1811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveInterval &interval = getOrCreateInterval(RegRep); 1821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // remove index -> MachineInstr and 1831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // MachineInstr -> index mappings 1841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos Mi2IndexMap::iterator mi2i = mi2iMap_.find(mii); 1851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (mi2i != mi2iMap_.end()) { 1861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_[mi2i->second/InstrSlots::NUM] = 0; 1871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_.erase(mi2i); 1881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mii = mbbi->erase(mii); 1901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ++numPeep; 1911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else { 1931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0; i < mii->getNumOperands(); ++i) { 1941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos const MachineOperand& mop = mii->getOperand(i); 1951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (mop.isRegister() && mop.getReg() && 1961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MRegisterInfo::isVirtualRegister(mop.getReg())) { 1971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // replace register with representative register 1981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned reg = rep(mop.getReg()); 199e53f4a055f74bded20d6129b4724ddd17fd199f6Chris Lattner mii->getOperand(i).setReg(reg); 2001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveInterval &RegInt = getInterval(reg); 2021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos RegInt.weight += 2037a36ae8b0103088328e3a4992ac08b3dce312248Chris Lattner (mop.isUse() + mop.isDef()) * pow(10.0F, (int)loopDepth); 2041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ++mii; 2071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2107a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 211993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng for (iterator I = begin(), E = end(); I != E; ++I) { 212993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng LiveInterval &li = I->second; 213993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng if (MRegisterInfo::isVirtualRegister(li.reg)) 214993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng // If the live interval legnth is essentially zero, i.e. in every live 215993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng // range the use follows def immediately, it doesn't make sense to spill 216993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng // it and hope it will be easier to allocate for this li. 217993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng if (isZeroLengthInterval(&li)) 218993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng li.weight = float(HUGE_VAL); 219993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng } 220993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 22170ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 2221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 223ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 224ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 22570ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 226ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencervoid LiveIntervals::print(std::ostream &O, const Module* ) const { 22770ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** INTERVALS **********\n"; 2288e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 2298e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner I->second.print(std::cerr, mri_); 2308e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner std::cerr << "\n"; 2318e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 23270ca358b7d540b6061236ddf757085042873c12cChris Lattner 23370ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** MACHINEINSTRS **********\n"; 23470ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 23570ca358b7d540b6061236ddf757085042873c12cChris Lattner mbbi != mbbe; ++mbbi) { 23670ca358b7d540b6061236ddf757085042873c12cChris Lattner O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 23770ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineBasicBlock::iterator mii = mbbi->begin(), 23870ca358b7d540b6061236ddf757085042873c12cChris Lattner mie = mbbi->end(); mii != mie; ++mii) { 239477e4555de341c5de780de3720d6f115ec133c4eChris Lattner O << getInstructionIndex(mii) << '\t' << *mii; 24070ca358b7d540b6061236ddf757085042873c12cChris Lattner } 24170ca358b7d540b6061236ddf757085042873c12cChris Lattner } 24270ca358b7d540b6061236ddf757085042873c12cChris Lattner} 24370ca358b7d540b6061236ddf757085042873c12cChris Lattner 24470ca358b7d540b6061236ddf757085042873c12cChris Lattnerstd::vector<LiveInterval*> LiveIntervals:: 24570ca358b7d540b6061236ddf757085042873c12cChris LattneraddIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { 246d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // since this is called after the analysis is done we don't know if 247d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // LiveVariables is available 248d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos lv_ = getAnalysisToUpdate<LiveVariables>(); 249d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos 2501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos std::vector<LiveInterval*> added; 2511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(li.weight != HUGE_VAL && 2531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "attempt to spill already spilled interval!"); 2541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tadding intervals for spills for interval: " 2561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos << li << '\n'); 2571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg); 2591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (LiveInterval::Ranges::const_iterator 2611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 2621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned index = getBaseIndex(i->start); 2631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = getBaseIndex(i->end-1) + InstrSlots::NUM; 2641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (; index != end; index += InstrSlots::NUM) { 2651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // skip deleted instructions 2661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos while (index != end && !getInstructionFromIndex(index)) 2671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos index += InstrSlots::NUM; 2681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (index == end) break; 2691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2703b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner MachineInstr *MI = getInstructionFromIndex(index); 2711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 272b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // NewRegLiveIn - This instruction might have multiple uses of the spilled 273b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // register. In this case, for the first use, keep track of the new vreg 274b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // that we reload it into. If we see a second use, reuse this vreg 275b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // instead of creating live ranges for two reloads. 276b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner unsigned NewRegLiveIn = 0; 277b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner 2781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for_operand: 2793b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 2803b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner MachineOperand& mop = MI->getOperand(i); 2811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (mop.isRegister() && mop.getReg() == li.reg) { 282b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner if (NewRegLiveIn && mop.isUse()) { 283b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // We already emitted a reload of this value, reuse it for 284b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // subsequent operands. 285e53f4a055f74bded20d6129b4724ddd17fd199f6Chris Lattner MI->getOperand(i).setReg(NewRegLiveIn); 286b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner DEBUG(std::cerr << "\t\t\t\treused reload into reg" << NewRegLiveIn 287b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner << " for operand #" << i << '\n'); 2883b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner } else if (MachineInstr* fmi = mri_->foldMemoryOperand(MI, i, slot)) { 289b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // Attempt to fold the memory reference into the instruction. If we 290b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // can do this, we don't need to insert spill code. 291d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos if (lv_) 2923b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner lv_->instructionChanged(MI, fmi); 293200370fb5617a1719f0054804b412469ce486ebdEvan Cheng MachineBasicBlock &MBB = *MI->getParent(); 29435f2705e3de4600c3621b883eed9b22e4607ddf4Chris Lattner vrm.virtFolded(li.reg, MI, i, fmi); 2953b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner mi2iMap_.erase(MI); 2961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_[index/InstrSlots::NUM] = fmi; 2971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_[fmi] = index; 2983b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner MI = MBB.insert(MBB.erase(MI), fmi); 2991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ++numFolded; 300477e4555de341c5de780de3720d6f115ec133c4eChris Lattner // Folding the load/store can completely change the instruction in 301477e4555de341c5de780de3720d6f115ec133c4eChris Lattner // unpredictable ways, rescan it from the beginning. 3021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos goto for_operand; 303477e4555de341c5de780de3720d6f115ec133c4eChris Lattner } else { 30470ca358b7d540b6061236ddf757085042873c12cChris Lattner // This is tricky. We need to add information in the interval about 30570ca358b7d540b6061236ddf757085042873c12cChris Lattner // the spill code so we have to use our extra load/store slots. 3061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // 30770ca358b7d540b6061236ddf757085042873c12cChris Lattner // If we have a use we are going to have a load so we start the 30870ca358b7d540b6061236ddf757085042873c12cChris Lattner // interval from the load slot onwards. Otherwise we start from the 30970ca358b7d540b6061236ddf757085042873c12cChris Lattner // def slot. 3101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned start = (mop.isUse() ? 3111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos getLoadIndex(index) : 3121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos getDefIndex(index)); 31370ca358b7d540b6061236ddf757085042873c12cChris Lattner // If we have a def we are going to have a store right after it so 31470ca358b7d540b6061236ddf757085042873c12cChris Lattner // we end the interval after the use of the next 31570ca358b7d540b6061236ddf757085042873c12cChris Lattner // instruction. Otherwise we end after the use of this instruction. 3161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = 1 + (mop.isDef() ? 3171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos getStoreIndex(index) : 3181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos getUseIndex(index)); 3191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // create a new register for this spill 321b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner NewRegLiveIn = mf_->getSSARegMap()->createVirtualRegister(rc); 322e53f4a055f74bded20d6129b4724ddd17fd199f6Chris Lattner MI->getOperand(i).setReg(NewRegLiveIn); 3231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos vrm.grow(); 324b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner vrm.assignVirt2StackSlot(NewRegLiveIn, slot); 325b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner LiveInterval& nI = getOrCreateInterval(NewRegLiveIn); 3261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(nI.empty()); 32770ca358b7d540b6061236ddf757085042873c12cChris Lattner 3281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the spill weight is now infinity as it 3291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // cannot be spilled again 33028696bee024805a6b191cfe12e1a24784dae8aa7Chris Lattner nI.weight = float(HUGE_VAL); 3311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(start, end, nI.getNextValue()); 3321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR); 3331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos nI.addRange(LR); 3341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos added.push_back(&nI); 33570ca358b7d540b6061236ddf757085042873c12cChris Lattner 336d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // update live variables if it is available 337d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos if (lv_) 3383b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner lv_->addVirtualRegisterKilled(NewRegLiveIn, MI); 339b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner 340b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // If this is a live in, reuse it for subsequent live-ins. If it's 341b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // a def, we can't do this. 342b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner if (!mop.isUse()) NewRegLiveIn = 0; 343b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner 344d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tadded new interval: " << nI << '\n'); 3451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 346843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 3471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 348843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 3491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 35026f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos 3511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return added; 352843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos} 353843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 354ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::printRegName(unsigned reg) const 355ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 3561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(reg)) 3571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos std::cerr << mri_->getName(reg); 3581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 3591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos std::cerr << "%reg" << reg; 360ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 361ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 362ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 363ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 364418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner LiveInterval& interval) 365ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 3661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); 3671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 3681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 369706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 370706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 371706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 3721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 3731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 3741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 3751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned defIndex = getDefIndex(getInstructionIndex(mi)); 3761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned ValNum = interval.getNextValue(); 3781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(ValNum == 0 && "First value in interval is not 0?"); 3791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ValNum = 0; // Clue in the optimizer. 3801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 3821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 3831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 3841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 3851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 3861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 3871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned killIdx; 3881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 3891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 3901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 3911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = defIndex+1; 3921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 3941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 3951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 396706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos assert(vi.AliveBlocks.empty() && 3971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 3981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(defIndex, killIdx, ValNum); 3991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR << "\n"); 4011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 4021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4046097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 4051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 4061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 4071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 4081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 409d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos LiveRange NewLR(defIndex, 410d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 411d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos ValNum); 4121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << NewLR); 4131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 4141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Iterate over all of the blocks that the variable is completely 4161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 4171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live interval. 4181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 4191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.AliveBlocks[i]) { 4201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineBasicBlock* mbb = mf_->getBlockNumbered(i); 4211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (!mbb->empty()) { 4221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(getInstructionIndex(&mbb->front()), 423d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 4241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ValNum); 4251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR); 4271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 4321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 4331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 4341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 4351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(getInstructionIndex(Kill->getParent()->begin()), 436d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos getUseIndex(getInstructionIndex(Kill))+1, 437d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos ValNum); 4381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR); 4401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 4431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 4441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 4451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the result of two address elimination, then the vreg is the first 4461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // operand, and is a def-and-use. 447706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos if (mi->getOperand(0).isRegister() && 4481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi->getOperand(0).getReg() == interval.reg && 4491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi->getOperand(0).isDef() && mi->getOperand(0).isUse()) { 4501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 4511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 4521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 4531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 4541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 4551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst)); 4561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned RedefIndex = getDefIndex(getInstructionIndex(mi)); 4571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Delete the initial value, which should be short and continuous, 4591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // becuase the 2-addr copy must be in the same MBB as the redef. 4601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 461706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 4621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(DefIndex, RedefIndex, interval.getNextValue()); 4631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " replace range with " << LR); 4641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 4671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 468ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->RegisterDefIsDead(mi, interval.reg)) 469ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0)); 4701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "RESULT: " << interval); 4721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 4741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Otherwise, this must be because of phi elimination. If this is the 4751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // first redefinition of the vreg that we have seen, go back and change 4761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range in the PHI block to be a different value number. 4771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.containsOneValue()) { 4781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(vi.Kills.size() == 1 && 4791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "PHI elimination vreg should have one kill, the PHI itself!"); 4801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Remove the old range that we now know has an incorrect number. 4821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Killer = vi.Kills[0]; 4831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned Start = getInstructionIndex(Killer->getParent()->begin()); 4841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 4851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "Removing [" << Start << "," << End << "] from: " 4861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos << interval << "\n"); 4871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(Start, End); 4881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "RESULT: " << interval); 4891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Replace the interval with one of a NEW value number. 4911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(Start, End, interval.getNextValue()); 4921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " replace range with " << LR); 4931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "RESULT: " << interval); 4951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 4981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 4991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 5001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned defIndex = getDefIndex(getInstructionIndex(mi)); 501706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos LiveRange LR(defIndex, 5021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 5031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.getNextValue()); 5041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 5051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR); 506dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 5071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 508ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 5091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << '\n'); 510ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 511ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 512f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 513ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 514f768bba43f5c036039851d2fcca8212edca18467Chris Lattner LiveInterval& interval, 5155ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner unsigned SrcReg, unsigned DestReg, 5165ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner bool isLiveIn) 517ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 5181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 5191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 5201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); 5211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos typedef LiveVariables::killed_iterator KillIter; 5221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned baseIndex = getInstructionIndex(mi); 5241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned start = getDefIndex(baseIndex); 5251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = start; 5261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 5281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 5291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 530ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->RegisterDefIsDead(mi, interval.reg)) { 531ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner DEBUG(std::cerr << " dead"); 532ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getDefIndex(start) + 1; 533ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 5341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 535ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 5361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 5371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 5381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 5395ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 5401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos baseIndex += InstrSlots::NUM; 541ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->KillsRegister(mi, interval.reg)) { 542ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner DEBUG(std::cerr << " killed"); 543ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getUseIndex(baseIndex) + 1; 544ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 545f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5475ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner 5485ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 5495ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 5505ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // and never used. 5515ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner assert(isLiveIn && "physreg was not killed in defining block!"); 5525ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner end = getDefIndex(start) + 1; // It's dead. 55302ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 554ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 5551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 556f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 557f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // Finally, if this is defining a new range for the physical register, and if 558f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // that physreg is just a copy from a vreg, and if THAT vreg was a copy from 559f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // the physreg, then the new fragment has the same value as the one copied 560f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // into the vreg. 561f768bba43f5c036039851d2fcca8212edca18467Chris Lattner if (interval.reg == DestReg && !interval.empty() && 562e97568c3c41e6de2b726d2cd99724659650e9614Chris Lattner MRegisterInfo::isVirtualRegister(SrcReg)) { 563f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 564f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // Get the live interval for the vreg, see if it is defined by a copy. 565f768bba43f5c036039851d2fcca8212edca18467Chris Lattner LiveInterval &SrcInterval = getOrCreateInterval(SrcReg); 566f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 567f768bba43f5c036039851d2fcca8212edca18467Chris Lattner if (SrcInterval.containsOneValue()) { 568f768bba43f5c036039851d2fcca8212edca18467Chris Lattner assert(!SrcInterval.empty() && "Can't contain a value and be empty!"); 569f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 570f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // Get the first index of the first range. Though the interval may have 571f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // multiple liveranges in it, we only check the first. 572f768bba43f5c036039851d2fcca8212edca18467Chris Lattner unsigned StartIdx = SrcInterval.begin()->start; 573f768bba43f5c036039851d2fcca8212edca18467Chris Lattner MachineInstr *SrcDefMI = getInstructionFromIndex(StartIdx); 574f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 575f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // Check to see if the vreg was defined by a copy instruction, and that 576f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // the source was this physreg. 577f768bba43f5c036039851d2fcca8212edca18467Chris Lattner unsigned VRegSrcSrc, VRegSrcDest; 578f768bba43f5c036039851d2fcca8212edca18467Chris Lattner if (tii_->isMoveInstr(*SrcDefMI, VRegSrcSrc, VRegSrcDest) && 579f768bba43f5c036039851d2fcca8212edca18467Chris Lattner SrcReg == VRegSrcDest && VRegSrcSrc == DestReg) { 580f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // Okay, now we know that the vreg was defined by a copy from this 581f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // physreg. Find the value number being copied and use it as the value 582f768bba43f5c036039851d2fcca8212edca18467Chris Lattner // for this range. 583f768bba43f5c036039851d2fcca8212edca18467Chris Lattner const LiveRange *DefRange = interval.getLiveRangeContaining(StartIdx-1); 584f768bba43f5c036039851d2fcca8212edca18467Chris Lattner if (DefRange) { 585f768bba43f5c036039851d2fcca8212edca18467Chris Lattner LiveRange LR(start, end, DefRange->ValId); 586f768bba43f5c036039851d2fcca8212edca18467Chris Lattner interval.addRange(LR); 587f768bba43f5c036039851d2fcca8212edca18467Chris Lattner DEBUG(std::cerr << " +" << LR << '\n'); 588f768bba43f5c036039851d2fcca8212edca18467Chris Lattner return; 589f768bba43f5c036039851d2fcca8212edca18467Chris Lattner } 590f768bba43f5c036039851d2fcca8212edca18467Chris Lattner } 591f768bba43f5c036039851d2fcca8212edca18467Chris Lattner } 592f768bba43f5c036039851d2fcca8212edca18467Chris Lattner } 593f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 594f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 5951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(start, end, interval.getNextValue()); 5961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 5971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR << '\n'); 598ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 599ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 600f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 601f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 602f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner unsigned reg) { 603f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner if (MRegisterInfo::isVirtualRegister(reg)) 604f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner handleVirtualRegisterDef(MBB, MI, getOrCreateInterval(reg)); 6055327801fb87e3eda52a33f82e6211181030ecb93Alkis Evlogimenos else if (allocatableRegs_[reg]) { 606f768bba43f5c036039851d2fcca8212edca18467Chris Lattner unsigned SrcReg = 0, DestReg = 0; 60760d97d4f55b6bd51179eba3388c95d5ec6942ec8Chris Lattner if (!tii_->isMoveInstr(*MI, SrcReg, DestReg)) 60860d97d4f55b6bd51179eba3388c95d5ec6942ec8Chris Lattner SrcReg = DestReg = 0; 609f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 610f768bba43f5c036039851d2fcca8212edca18467Chris Lattner handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(reg), 611f768bba43f5c036039851d2fcca8212edca18467Chris Lattner SrcReg, DestReg); 612f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner for (const unsigned* AS = mri_->getAliasSet(reg); *AS; ++AS) 613f768bba43f5c036039851d2fcca8212edca18467Chris Lattner handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(*AS), 614f768bba43f5c036039851d2fcca8212edca18467Chris Lattner SrcReg, DestReg); 615f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 6164d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 6174d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 618ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 6194d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 62008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 621ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 622ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::computeIntervals() 623ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 6241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "********** COMPUTING LIVE INTERVALS **********\n"); 6251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "********** Function: " 6261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos << ((Value*)mf_->getFunction())->getName() << '\n'); 627799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner bool IgnoreFirstInstr = mf_->livein_begin() != mf_->livein_end(); 6281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 629706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 6301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos I != E; ++I) { 6311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineBasicBlock* mbb = I; 6321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << ((Value*)mbb->getBasicBlock())->getName() << ":\n"); 6331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 634799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 635799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner if (IgnoreFirstInstr) { ++mi; IgnoreFirstInstr = false; } 636799a919dbc03d8451434a1f3afc6fe571212d19cChris Lattner for (; mi != miEnd; ++mi) { 6371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos const TargetInstrDescriptor& tid = 6381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos tm_->getInstrInfo()->get(mi->getOpcode()); 639477e4555de341c5de780de3720d6f115ec133c4eChris Lattner DEBUG(std::cerr << getInstructionIndex(mi) << "\t" << *mi); 6401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 6411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle implicit defs 642cd4317efcf334be10d9a98008a1445d6e12a7712Jim Laskey if (tid.ImplicitDefs) { 643cd4317efcf334be10d9a98008a1445d6e12a7712Jim Laskey for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 644cd4317efcf334be10d9a98008a1445d6e12a7712Jim Laskey handleRegisterDef(mbb, mi, *id); 645cd4317efcf334be10d9a98008a1445d6e12a7712Jim Laskey } 6461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 6471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle explicit defs 6481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (int i = mi->getNumOperands() - 1; i >= 0; --i) { 6491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineOperand& mop = mi->getOperand(i); 6501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 6511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (mop.isRegister() && mop.getReg() && mop.isDef()) 6521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos handleRegisterDef(mbb, mi, mop.getReg()); 6531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 654ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 6551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 656ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 657b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 658aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner/// IntA is defined as a copy from IntB and we know it only has one value 659aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner/// number. If all of the places that IntA and IntB overlap are defined by 660aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner/// copies from IntA to IntB, we know that these two ranges can really be 661aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner/// merged if we adjust the value numbers. If it is safe, adjust the value 662c60e6020c0dd1260b0d60835e2ab823f97a4b810Chris Lattner/// numbers and return true, allowing coalescing to occur. 663aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattnerbool LiveIntervals:: 664aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris LattnerAdjustIfAllOverlappingRangesAreCopiesFrom(LiveInterval &IntA, 665aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner LiveInterval &IntB, 666aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner unsigned CopyIdx) { 667aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner std::vector<LiveRange*> Ranges; 668aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner IntA.getOverlapingRanges(IntB, CopyIdx, Ranges); 669aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 670aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner assert(!Ranges.empty() && "Why didn't we do a simple join of this?"); 671aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 672aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner unsigned IntBRep = rep(IntB.reg); 673aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 674aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // Check to see if all of the overlaps (entries in Ranges) are defined by a 675aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // copy from IntA. If not, exit. 676aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner for (unsigned i = 0, e = Ranges.size(); i != e; ++i) { 677aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner unsigned Idx = Ranges[i]->start; 678aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner MachineInstr *MI = getInstructionFromIndex(Idx); 679aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner unsigned SrcReg, DestReg; 680aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (!tii_->isMoveInstr(*MI, SrcReg, DestReg)) return false; 681aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 682aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // If this copy isn't actually defining this range, it must be a live 683aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // range spanning basic blocks or something. 684aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (rep(DestReg) != rep(IntA.reg)) return false; 685aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 686aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // Check to see if this is coming from IntB. If not, bail out. 687aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (rep(SrcReg) != IntBRep) return false; 688aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner } 689aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 690aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // Okay, we can change this one. Get the IntB value number that IntA is 691aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // copied from. 692aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner unsigned ActualValNo = IntA.getLiveRangeContaining(CopyIdx-1)->ValId; 693aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 694aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // Change all of the value numbers to the same as what we IntA is copied from. 695aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner for (unsigned i = 0, e = Ranges.size(); i != e; ++i) 696aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner Ranges[i]->ValId = ActualValNo; 697aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 698aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner return true; 699aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner} 700aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 7011c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattnervoid LiveIntervals::joinIntervalsInMachineBB(MachineBasicBlock *MBB) { 7027ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner DEBUG(std::cerr << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); 7037ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 7047ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner for (MachineBasicBlock::iterator mi = MBB->begin(), mie = MBB->end(); 7057ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner mi != mie; ++mi) { 7067ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner DEBUG(std::cerr << getInstructionIndex(mi) << '\t' << *mi); 7077ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 7087ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // we only join virtual registers with allocatable 7097ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // physical registers since we do not have liveness information 7107ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // on not allocatable physical registers 711aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner unsigned SrcReg, DestReg; 712aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (tii_->isMoveInstr(*mi, SrcReg, DestReg) && 713aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner (MRegisterInfo::isVirtualRegister(SrcReg) || allocatableRegs_[SrcReg])&& 714aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner (MRegisterInfo::isVirtualRegister(DestReg)||allocatableRegs_[DestReg])){ 715706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 7167ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // Get representative registers. 717aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner SrcReg = rep(SrcReg); 718aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner DestReg = rep(DestReg); 719706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 7207ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // If they are already joined we continue. 721aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (SrcReg == DestReg) 7227ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner continue; 723706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 7247ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // If they are both physical registers, we cannot join them. 725aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (MRegisterInfo::isPhysicalRegister(SrcReg) && 726aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner MRegisterInfo::isPhysicalRegister(DestReg)) 7277ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner continue; 7287ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 729647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng // If they are not of the same register class, we cannot join them. 730647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng if (differingRegisterClasses(SrcReg, DestReg)) 7317ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner continue; 7327ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 733aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner LiveInterval &SrcInt = getInterval(SrcReg); 734aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner LiveInterval &DestInt = getInterval(DestReg); 735aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner assert(SrcInt.reg == SrcReg && DestInt.reg == DestReg && 7367ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner "Register mapping is horribly broken!"); 737060913cce42d8b746194c7ebd8b19c9789a03909Chris Lattner 738aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner DEBUG(std::cerr << "\t\tInspecting " << SrcInt << " and " << DestInt 739aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner << ": "); 740060913cce42d8b746194c7ebd8b19c9789a03909Chris Lattner 7414df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner // If two intervals contain a single value and are joined by a copy, it 7424df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner // does not matter if the intervals overlap, they can always be joined. 743aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner bool Joinable = SrcInt.containsOneValue() && DestInt.containsOneValue(); 7447ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 7457ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner unsigned MIDefIdx = getDefIndex(getInstructionIndex(mi)); 746aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 747aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // If the intervals think that this is joinable, do so now. 748aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (!Joinable && DestInt.joinable(SrcInt, MIDefIdx)) 749aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner Joinable = true; 750aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 751aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // If DestInt is actually a copy from SrcInt (which we know) that is used 752aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // to define another value of SrcInt, we can change the other range of 753aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner // SrcInt to be the value of the range that defines DestInt, allowing a 754c60e6020c0dd1260b0d60835e2ab823f97a4b810Chris Lattner // coalesce. 755aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (!Joinable && DestInt.containsOneValue() && 756aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner AdjustIfAllOverlappingRangesAreCopiesFrom(SrcInt, DestInt, MIDefIdx)) 757aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner Joinable = true; 758aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 759aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner if (!Joinable || overlapsAliases(&SrcInt, &DestInt)) { 760aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner DEBUG(std::cerr << "Interference!\n"); 761aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner } else { 762aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner DestInt.join(SrcInt, MIDefIdx); 763aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner DEBUG(std::cerr << "Joined. Result = " << DestInt << "\n"); 764aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 765647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng if (!MRegisterInfo::isPhysicalRegister(SrcReg)) { 766aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner r2iMap_.erase(SrcReg); 767aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner r2rMap_[SrcReg] = DestReg; 7687ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner } else { 7697ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // Otherwise merge the data structures the other way so we don't lose 7707ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // the physreg information. 771aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner r2rMap_[DestReg] = SrcReg; 772aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner DestInt.reg = SrcReg; 773aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner SrcInt.swap(DestInt); 774aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner r2iMap_.erase(DestReg); 775e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 7767ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner ++numJoins; 7777ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner } 778dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 7797ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner } 780dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 781dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 782cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattnernamespace { 783cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // DepthMBBCompare - Comparison predicate that sort first based on the loop 784cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // depth of the basic block (the unsigned), and then on the MBB number. 785cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner struct DepthMBBCompare { 786cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; 787cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { 788cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner if (LHS.first > RHS.first) return true; // Deeper loops first 789706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos return LHS.first == RHS.first && 7901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LHS.second->getNumber() < RHS.second->getNumber(); 791cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner } 792cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner }; 793cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner} 794cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner 795cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattnervoid LiveIntervals::joinIntervals() { 796cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner DEBUG(std::cerr << "********** JOINING INTERVALS ***********\n"); 7971c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner 798cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner const LoopInfo &LI = getAnalysis<LoopInfo>(); 799cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner if (LI.begin() == LI.end()) { 800cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // If there are no loops in the function, join intervals in function order. 8011c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 8021c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner I != E; ++I) 8031c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner joinIntervalsInMachineBB(I); 804cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner } else { 805cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // Otherwise, join intervals in inner loops before other intervals. 806cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // Unfortunately we can't just iterate over loop hierarchy here because 807cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // there may be more MBB's than BB's. Collect MBB's for sorting. 808cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; 809cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 810cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner I != E; ++I) 811cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner MBBs.push_back(std::make_pair(LI.getLoopDepth(I->getBasicBlock()), I)); 812cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner 813cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // Sort by loop depth. 814cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); 815cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner 816706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Finally, join intervals in loop nest order. 817cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 818cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner joinIntervalsInMachineBB(MBBs[i].second); 819cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner } 820c83e40d1b6582155286f1044623d544dea20202eChris Lattner 821c83e40d1b6582155286f1044623d544dea20202eChris Lattner DEBUG(std::cerr << "*** Register mapping ***\n"); 8225d0d1e350a30772fd70798b5733bb060febd7b0dAlkis Evlogimenos DEBUG(for (int i = 0, e = r2rMap_.size(); i != e; ++i) 8237c10b0d2c9b4d637edf27548c104b7199b0e3578Chris Lattner if (r2rMap_[i]) { 8247c10b0d2c9b4d637edf27548c104b7199b0e3578Chris Lattner std::cerr << " reg " << i << " -> "; 8257c10b0d2c9b4d637edf27548c104b7199b0e3578Chris Lattner printRegName(r2rMap_[i]); 8267c10b0d2c9b4d637edf27548c104b7199b0e3578Chris Lattner std::cerr << "\n"; 8277c10b0d2c9b4d637edf27548c104b7199b0e3578Chris Lattner }); 8281c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner} 8291c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner 830647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng/// Return true if the two specified registers belong to different register 831647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng/// classes. The registers may be either phys or virt regs. 832647c15e58ed4c3fda81041d401ca7547639958dcEvan Chengbool LiveIntervals::differingRegisterClasses(unsigned RegA, 833647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng unsigned RegB) const { 8347ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 8357ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // Get the register classes for the first reg. 836ad3c74fc9b52b652859807580c8e40b67394d689Chris Lattner if (MRegisterInfo::isPhysicalRegister(RegA)) { 837edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman assert(MRegisterInfo::isVirtualRegister(RegB) && 838ad3c74fc9b52b652859807580c8e40b67394d689Chris Lattner "Shouldn't consider two physregs!"); 839647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng return !mf_->getSSARegMap()->getRegClass(RegB)->contains(RegA); 840ad3c74fc9b52b652859807580c8e40b67394d689Chris Lattner } 8417ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 8427ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // Compare against the regclass for the second reg. 843647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng const TargetRegisterClass *RegClass = mf_->getSSARegMap()->getRegClass(RegA); 844647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng if (MRegisterInfo::isVirtualRegister(RegB)) 845647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng return RegClass != mf_->getSSARegMap()->getRegClass(RegB); 846647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng else 847647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng return !RegClass->contains(RegB); 8487ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner} 8497ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 8507ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattnerbool LiveIntervals::overlapsAliases(const LiveInterval *LHS, 8517ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner const LiveInterval *RHS) const { 8527ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner if (!MRegisterInfo::isPhysicalRegister(LHS->reg)) { 8537ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner if (!MRegisterInfo::isPhysicalRegister(RHS->reg)) 8547ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner return false; // vreg-vreg merge has no aliases! 8557ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner std::swap(LHS, RHS); 8567ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner } 8577ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 8587ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner assert(MRegisterInfo::isPhysicalRegister(LHS->reg) && 8597ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner MRegisterInfo::isVirtualRegister(RHS->reg) && 8607ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner "first interval must describe a physical register"); 86179b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 8624df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner for (const unsigned *AS = mri_->getAliasSet(LHS->reg); *AS; ++AS) 8634df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner if (RHS->overlaps(getInterval(*AS))) 8644df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner return true; 86579b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 8664df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner return false; 86779b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos} 86879b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 869a1613db62fec94845aa8306232fb665273615badAlkis EvlogimenosLiveInterval LiveIntervals::createInterval(unsigned reg) { 870edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman float Weight = MRegisterInfo::isPhysicalRegister(reg) ? 87128696bee024805a6b191cfe12e1a24784dae8aa7Chris Lattner (float)HUGE_VAL :0.0F; 872a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos return LiveInterval(reg, Weight); 8739a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 874