LiveIntervalAnalysis.cpp revision 70ca358b7d540b6061236ddf757085042873c12c
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" 19a3b8b5c0e0a1d0942288568b2012592184ca67c5Chris Lattner#include "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> 37ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 38ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 39ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosnamespace { 401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos RegisterAnalysis<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 41ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos Statistic<> numIntervals 431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ("liveintervals", "Number of original intervals"); 44007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos Statistic<> numIntervalsAfter 461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ("liveintervals", "Number of intervals after coalescing"); 47007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos Statistic<> numJoins 491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ("liveintervals", "Number of interval joins performed"); 50007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos Statistic<> numPeep 521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ("liveintervals", "Number of identity moves eliminated after coalescing"); 53007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos Statistic<> numFolded 551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ("liveintervals", "Number of loads/stores folded into instructions"); 56007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos cl::opt<bool> 581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos EnableJoining("join-liveintervals", 591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos cl::desc("Join compatible live intervals"), 601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos cl::init(true)); 61ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos}; 62ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 63ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const 64ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addPreserved<LiveVariables>(); 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(); 891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos lv_ = &getAnalysis<LiveVariables>(); 905327801fb87e3eda52a33f82e6211181030ecb93Alkis Evlogimenos allocatableRegs_ = mri_->getAllocatableSet(fn); 912c4f7b5faaeedd97058ec4cfa44177124c42b9e1Alkis Evlogimenos r2rMap_.grow(mf_->getSSARegMap()->getLastVirtReg()); 921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // number MachineInstrs 941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned miIndex = 0; 951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mbb != mbbEnd; ++mbb) 971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi != miEnd; ++mi) { 991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos bool inserted = mi2iMap_.insert(std::make_pair(mi, miIndex)).second; 1001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 1011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_.push_back(mi); 1021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos miIndex += InstrSlots::NUM; 1031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 104ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 106ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 108843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 1097ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner#if 1 1101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "********** INTERVALS **********\n"); 1111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(for (iterator I = begin(), E = end(); I != E; ++I) 1121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos std::cerr << I->second << "\n"); 1137ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner#endif 1147ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 1151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // join intervals if requested 1161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (EnableJoining) joinIntervals(); 1171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervalsAfter += getNumIntervals(); 1191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // perform a final pass over the instructions and compute spill 1211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // weights, coalesce virtual registers and remove identity moves 1221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos const LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 1231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos const TargetInstrInfo& tii = *tm_->getInstrInfo(); 1241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 1261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mbbi != mbbe; ++mbbi) { 1271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineBasicBlock* mbb = mbbi; 1281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 1291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); 1311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mii != mie; ) { 1321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // if the move will be an identity move delete it 1331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned srcReg, dstReg, RegRep; 1341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (tii.isMoveInstr(*mii, srcReg, dstReg) && 1351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos (RegRep = rep(srcReg)) == rep(dstReg)) { 1361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // remove from def list 1371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveInterval &interval = getOrCreateInterval(RegRep); 1381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // remove index -> MachineInstr and 1391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // MachineInstr -> index mappings 1401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos Mi2IndexMap::iterator mi2i = mi2iMap_.find(mii); 1411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (mi2i != mi2iMap_.end()) { 1421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_[mi2i->second/InstrSlots::NUM] = 0; 1431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_.erase(mi2i); 1441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mii = mbbi->erase(mii); 1461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ++numPeep; 1471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else { 1491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0; i < mii->getNumOperands(); ++i) { 1501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos const MachineOperand& mop = mii->getOperand(i); 1511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (mop.isRegister() && mop.getReg() && 1521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MRegisterInfo::isVirtualRegister(mop.getReg())) { 1531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // replace register with representative register 1541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned reg = rep(mop.getReg()); 1551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mii->SetMachineOperandReg(i, reg); 1561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveInterval &RegInt = getInterval(reg); 1581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos RegInt.weight += 1591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos (mop.isUse() + mop.isDef()) * pow(10.0F, loopDepth); 1601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ++mii; 1631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1667a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 16770ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 1681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 169ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 170ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 17170ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 17270ca358b7d540b6061236ddf757085042873c12cChris Lattnervoid LiveIntervals::print(std::ostream &O) const { 17370ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** INTERVALS **********\n"; 17470ca358b7d540b6061236ddf757085042873c12cChris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) 17570ca358b7d540b6061236ddf757085042873c12cChris Lattner O << I->second << "\n"; 17670ca358b7d540b6061236ddf757085042873c12cChris Lattner 17770ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** MACHINEINSTRS **********\n"; 17870ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 17970ca358b7d540b6061236ddf757085042873c12cChris Lattner mbbi != mbbe; ++mbbi) { 18070ca358b7d540b6061236ddf757085042873c12cChris Lattner O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 18170ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineBasicBlock::iterator mii = mbbi->begin(), 18270ca358b7d540b6061236ddf757085042873c12cChris Lattner mie = mbbi->end(); mii != mie; ++mii) { 18370ca358b7d540b6061236ddf757085042873c12cChris Lattner O << getInstructionIndex(mii) << '\t'; 18470ca358b7d540b6061236ddf757085042873c12cChris Lattner mii->print(O, tm_); 18570ca358b7d540b6061236ddf757085042873c12cChris Lattner } 18670ca358b7d540b6061236ddf757085042873c12cChris Lattner } 18770ca358b7d540b6061236ddf757085042873c12cChris Lattner} 18870ca358b7d540b6061236ddf757085042873c12cChris Lattner 18970ca358b7d540b6061236ddf757085042873c12cChris Lattner 19070ca358b7d540b6061236ddf757085042873c12cChris Lattnerstd::vector<LiveInterval*> LiveIntervals:: 19170ca358b7d540b6061236ddf757085042873c12cChris LattneraddIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { 192d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // since this is called after the analysis is done we don't know if 193d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // LiveVariables is available 194d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos lv_ = getAnalysisToUpdate<LiveVariables>(); 195d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos 1961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos std::vector<LiveInterval*> added; 1971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(li.weight != HUGE_VAL && 1991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "attempt to spill already spilled interval!"); 2001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tadding intervals for spills for interval: " 2021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos << li << '\n'); 2031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg); 2051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (LiveInterval::Ranges::const_iterator 2071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 2081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned index = getBaseIndex(i->start); 2091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = getBaseIndex(i->end-1) + InstrSlots::NUM; 2101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (; index != end; index += InstrSlots::NUM) { 2111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // skip deleted instructions 2121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos while (index != end && !getInstructionFromIndex(index)) 2131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos index += InstrSlots::NUM; 2141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (index == end) break; 2151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineBasicBlock::iterator mi = getInstructionFromIndex(index); 2171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for_operand: 2191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0; i != mi->getNumOperands(); ++i) { 2201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineOperand& mop = mi->getOperand(i); 2211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (mop.isRegister() && mop.getReg() == li.reg) { 222d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos if (MachineInstr* fmi = mri_->foldMemoryOperand(mi, i, slot)) { 223d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos if (lv_) 224d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos lv_->instructionChanged(mi, fmi); 2251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos vrm.virtFolded(li.reg, mi, fmi); 2261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_.erase(mi); 2271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_[index/InstrSlots::NUM] = fmi; 2281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_[fmi] = index; 2291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineBasicBlock& mbb = *mi->getParent(); 2301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi = mbb.insert(mbb.erase(mi), fmi); 2311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ++numFolded; 2321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos goto for_operand; 2331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else { 23570ca358b7d540b6061236ddf757085042873c12cChris Lattner // This is tricky. We need to add information in the interval about 23670ca358b7d540b6061236ddf757085042873c12cChris Lattner // the spill code so we have to use our extra load/store slots. 2371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // 23870ca358b7d540b6061236ddf757085042873c12cChris Lattner // If we have a use we are going to have a load so we start the 23970ca358b7d540b6061236ddf757085042873c12cChris Lattner // interval from the load slot onwards. Otherwise we start from the 24070ca358b7d540b6061236ddf757085042873c12cChris Lattner // def slot. 2411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned start = (mop.isUse() ? 2421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos getLoadIndex(index) : 2431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos getDefIndex(index)); 24470ca358b7d540b6061236ddf757085042873c12cChris Lattner // If we have a def we are going to have a store right after it so 24570ca358b7d540b6061236ddf757085042873c12cChris Lattner // we end the interval after the use of the next 24670ca358b7d540b6061236ddf757085042873c12cChris Lattner // instruction. Otherwise we end after the use of this instruction. 2471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = 1 + (mop.isDef() ? 2481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos getStoreIndex(index) : 2491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos getUseIndex(index)); 2501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // create a new register for this spill 252d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos unsigned nReg = mf_->getSSARegMap()->createVirtualRegister(rc); 2531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi->SetMachineOperandReg(i, nReg); 2541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos vrm.grow(); 2551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos vrm.assignVirt2StackSlot(nReg, slot); 2561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveInterval& nI = getOrCreateInterval(nReg); 2571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(nI.empty()); 25870ca358b7d540b6061236ddf757085042873c12cChris Lattner 2591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the spill weight is now infinity as it 2601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // cannot be spilled again 2611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos nI.weight = HUGE_VAL; 2621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(start, end, nI.getNextValue()); 2631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR); 2641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos nI.addRange(LR); 2651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos added.push_back(&nI); 26670ca358b7d540b6061236ddf757085042873c12cChris Lattner 267d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // update live variables if it is available 268d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos if (lv_) 269d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos lv_->addVirtualRegisterKilled(nReg, mi); 270d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tadded new interval: " << nI << '\n'); 2711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 272843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 2731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 274843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 2751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 27626f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos 2771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return added; 278843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos} 279843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 280ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::printRegName(unsigned reg) const 281ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 2821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(reg)) 2831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos std::cerr << mri_->getName(reg); 2841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 2851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos std::cerr << "%reg" << reg; 286ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 287ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 288ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 289ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 290418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner LiveInterval& interval) 291ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 2921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); 2931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 2941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 295706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 296706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 297706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 2981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 2991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 3001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 3011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned defIndex = getDefIndex(getInstructionIndex(mi)); 3021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned ValNum = interval.getNextValue(); 3041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(ValNum == 0 && "First value in interval is not 0?"); 3051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ValNum = 0; // Clue in the optimizer. 3061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 3081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 3091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 3101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 3111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 3121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 3131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned killIdx; 3141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 3151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 3161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 3171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = defIndex+1; 3181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 3201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 3211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 322706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos assert(vi.AliveBlocks.empty() && 3231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 3241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(defIndex, killIdx, ValNum); 3251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR << "\n"); 3271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 3281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3306097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 3311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 3321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 3331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 3341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 335d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos LiveRange NewLR(defIndex, 336d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 337d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos ValNum); 3381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << NewLR); 3391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 3401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Iterate over all of the blocks that the variable is completely 3421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 3431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live interval. 3441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 3451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.AliveBlocks[i]) { 3461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineBasicBlock* mbb = mf_->getBlockNumbered(i); 3471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (!mbb->empty()) { 3481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(getInstructionIndex(&mbb->front()), 349d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 3501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ValNum); 3511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR); 3531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 3581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 3591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 3601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 3611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(getInstructionIndex(Kill->getParent()->begin()), 362d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos getUseIndex(getInstructionIndex(Kill))+1, 363d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos ValNum); 3641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR); 3661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 3691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 3701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 3711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the result of two address elimination, then the vreg is the first 3721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // operand, and is a def-and-use. 373706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos if (mi->getOperand(0).isRegister() && 3741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi->getOperand(0).getReg() == interval.reg && 3751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi->getOperand(0).isDef() && mi->getOperand(0).isUse()) { 3761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 3771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 3781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 3791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 3801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 3811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst)); 3821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned RedefIndex = getDefIndex(getInstructionIndex(mi)); 3831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Delete the initial value, which should be short and continuous, 3851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // becuase the 2-addr copy must be in the same MBB as the redef. 3861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 387706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 3881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(DefIndex, RedefIndex, interval.getNextValue()); 3891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " replace range with " << LR); 3901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 3931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 3941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (LiveVariables::killed_iterator KI = lv_->dead_begin(mi), 3951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos E = lv_->dead_end(mi); KI != E; ++KI) 3961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (KI->second == interval.reg) { 3971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0)); 3981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos break; 3991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "RESULT: " << interval); 4021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 4041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Otherwise, this must be because of phi elimination. If this is the 4051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // first redefinition of the vreg that we have seen, go back and change 4061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range in the PHI block to be a different value number. 4071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.containsOneValue()) { 4081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(vi.Kills.size() == 1 && 4091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "PHI elimination vreg should have one kill, the PHI itself!"); 4101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Remove the old range that we now know has an incorrect number. 4121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Killer = vi.Kills[0]; 4131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned Start = getInstructionIndex(Killer->getParent()->begin()); 4141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 4151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "Removing [" << Start << "," << End << "] from: " 4161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos << interval << "\n"); 4171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(Start, End); 4181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "RESULT: " << interval); 4191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Replace the interval with one of a NEW value number. 4211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(Start, End, interval.getNextValue()); 4221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " replace range with " << LR); 4231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "RESULT: " << interval); 4251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 4281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 4291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 4301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned defIndex = getDefIndex(getInstructionIndex(mi)); 431706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos LiveRange LR(defIndex, 4321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 4331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.getNextValue()); 4341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR); 436dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 4371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 438ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 4391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << '\n'); 440ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 441ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 442f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 443ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 444418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner LiveInterval& interval) 445ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 4461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 4471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 4481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); 4491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos typedef LiveVariables::killed_iterator KillIter; 4501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned baseIndex = getInstructionIndex(mi); 4521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned start = getDefIndex(baseIndex); 4531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = start; 4541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 4561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 4571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 4581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (KillIter ki = lv_->dead_begin(mi), ke = lv_->dead_end(mi); 4591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ki != ke; ++ki) { 4601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.reg == ki->second) { 4611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " dead"); 4621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos end = getDefIndex(start) + 1; 4631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos goto exit; 464af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos } 4651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 466ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 4671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 4681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 4691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 4701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos while (true) { 4711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ++mi; 4721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(mi != MBB->end() && "physreg was not killed in defining block!"); 4731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos baseIndex += InstrSlots::NUM; 4741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (KillIter ki = lv_->killed_begin(mi), ke = lv_->killed_end(mi); 4751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ki != ke; ++ki) { 4761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.reg == ki->second) { 4771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " killed"); 4781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos end = getUseIndex(baseIndex) + 1; 4791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos goto exit; 4801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 481f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 4821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 48302ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 484ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 4851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 4861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(start, end, interval.getNextValue()); 4871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << " +" << LR << '\n'); 489ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 490ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 491f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 492f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 493f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner unsigned reg) { 494f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner if (MRegisterInfo::isVirtualRegister(reg)) 495f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner handleVirtualRegisterDef(MBB, MI, getOrCreateInterval(reg)); 4965327801fb87e3eda52a33f82e6211181030ecb93Alkis Evlogimenos else if (allocatableRegs_[reg]) { 497f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(reg)); 498f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner for (const unsigned* AS = mri_->getAliasSet(reg); *AS; ++AS) 499f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(*AS)); 500f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5014d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 5024d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 503ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 5044d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 50508cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 506ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 507ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::computeIntervals() 508ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 5091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "********** COMPUTING LIVE INTERVALS **********\n"); 5101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << "********** Function: " 5111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos << ((Value*)mf_->getFunction())->getName() << '\n'); 5121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 513706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 5141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos I != E; ++I) { 5151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineBasicBlock* mbb = I; 5161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << ((Value*)mbb->getBasicBlock())->getName() << ":\n"); 5171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 5191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi != miEnd; ++mi) { 5201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos const TargetInstrDescriptor& tid = 5211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos tm_->getInstrInfo()->get(mi->getOpcode()); 5221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos DEBUG(std::cerr << getInstructionIndex(mi) << "\t"; 5231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi->print(std::cerr, tm_)); 5241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle implicit defs 5261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 5271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos handleRegisterDef(mbb, mi, *id); 5281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle explicit defs 5301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (int i = mi->getNumOperands() - 1; i >= 0; --i) { 5311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineOperand& mop = mi->getOperand(i); 5321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 5331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (mop.isRegister() && mop.getReg() && mop.isDef()) 5341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos handleRegisterDef(mbb, mi, mop.getReg()); 5351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 536ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 5371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 538ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 539b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 5401c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattnervoid LiveIntervals::joinIntervalsInMachineBB(MachineBasicBlock *MBB) { 5417ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner DEBUG(std::cerr << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); 5427ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner const TargetInstrInfo &TII = *tm_->getInstrInfo(); 5437ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 5447ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner for (MachineBasicBlock::iterator mi = MBB->begin(), mie = MBB->end(); 5457ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner mi != mie; ++mi) { 5467ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner DEBUG(std::cerr << getInstructionIndex(mi) << '\t' << *mi); 5477ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 5487ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // we only join virtual registers with allocatable 5497ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // physical registers since we do not have liveness information 5507ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // on not allocatable physical registers 5517ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner unsigned regA, regB; 5527ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner if (TII.isMoveInstr(*mi, regA, regB) && 5535327801fb87e3eda52a33f82e6211181030ecb93Alkis Evlogimenos (MRegisterInfo::isVirtualRegister(regA) || allocatableRegs_[regA]) && 5545327801fb87e3eda52a33f82e6211181030ecb93Alkis Evlogimenos (MRegisterInfo::isVirtualRegister(regB) || allocatableRegs_[regB])) { 555706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 5567ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // Get representative registers. 5577ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner regA = rep(regA); 5587ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner regB = rep(regB); 559706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 5607ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // If they are already joined we continue. 5617ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner if (regA == regB) 5627ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner continue; 563706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 5647ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // If they are both physical registers, we cannot join them. 565706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(regA) && 5667ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner MRegisterInfo::isPhysicalRegister(regB)) 5677ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner continue; 5687ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 5697ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // If they are not of the same register class, we cannot join them. 5707ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner if (differingRegisterClasses(regA, regB)) 5717ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner continue; 5727ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 5737ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner LiveInterval &IntA = getInterval(regA); 5747ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner LiveInterval &IntB = getInterval(regB); 5757ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner assert(IntA.reg == regA && IntB.reg == regB && 5767ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner "Register mapping is horribly broken!"); 577060913cce42d8b746194c7ebd8b19c9789a03909Chris Lattner 578060913cce42d8b746194c7ebd8b19c9789a03909Chris Lattner DEBUG(std::cerr << "\t\tInspecting " << IntA << " and " << IntB << ": "); 579060913cce42d8b746194c7ebd8b19c9789a03909Chris Lattner 5804df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner // If two intervals contain a single value and are joined by a copy, it 5814df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner // does not matter if the intervals overlap, they can always be joined. 5827ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner bool TriviallyJoinable = 5837ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner IntA.containsOneValue() && IntB.containsOneValue(); 5847ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 5857ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner unsigned MIDefIdx = getDefIndex(getInstructionIndex(mi)); 586c25b55a5b237772bbd7cc55988d3ca0ec569aedeChris Lattner if ((TriviallyJoinable || IntB.joinable(IntA, MIDefIdx)) && 5877ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner !overlapsAliases(&IntA, &IntB)) { 5887ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner IntB.join(IntA, MIDefIdx); 5897ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 5907ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner if (!MRegisterInfo::isPhysicalRegister(regA)) { 5914df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner r2iMap_.erase(regA); 5927ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner r2rMap_[regA] = regB; 5937ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner } else { 5947ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // Otherwise merge the data structures the other way so we don't lose 5957ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // the physreg information. 5967ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner r2rMap_[regB] = regA; 5977ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner IntB.reg = regA; 598a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos IntA.swap(IntB); 5994df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner r2iMap_.erase(regB); 600e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 6017ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner DEBUG(std::cerr << "Joined. Result = " << IntB << "\n"); 6027ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner ++numJoins; 6037ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner } else { 6047ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner DEBUG(std::cerr << "Interference!\n"); 6057ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner } 606dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 6077ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner } 608dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 609dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 610cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattnernamespace { 611cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // DepthMBBCompare - Comparison predicate that sort first based on the loop 612cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // depth of the basic block (the unsigned), and then on the MBB number. 613cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner struct DepthMBBCompare { 614cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; 615cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { 616cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner if (LHS.first > RHS.first) return true; // Deeper loops first 617706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos return LHS.first == RHS.first && 6181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LHS.second->getNumber() < RHS.second->getNumber(); 619cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner } 620cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner }; 621cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner} 622cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner 623cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattnervoid LiveIntervals::joinIntervals() { 624cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner DEBUG(std::cerr << "********** JOINING INTERVALS ***********\n"); 6251c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner 626cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner const LoopInfo &LI = getAnalysis<LoopInfo>(); 627cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner if (LI.begin() == LI.end()) { 628cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // If there are no loops in the function, join intervals in function order. 6291c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 6301c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner I != E; ++I) 6311c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner joinIntervalsInMachineBB(I); 632cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner } else { 633cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // Otherwise, join intervals in inner loops before other intervals. 634cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // Unfortunately we can't just iterate over loop hierarchy here because 635cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // there may be more MBB's than BB's. Collect MBB's for sorting. 636cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; 637cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 638cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner I != E; ++I) 639cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner MBBs.push_back(std::make_pair(LI.getLoopDepth(I->getBasicBlock()), I)); 640cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner 641cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // Sort by loop depth. 642cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); 643cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner 644706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Finally, join intervals in loop nest order. 645cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 646cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner joinIntervalsInMachineBB(MBBs[i].second); 647cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner } 648c83e40d1b6582155286f1044623d544dea20202eChris Lattner 649c83e40d1b6582155286f1044623d544dea20202eChris Lattner DEBUG(std::cerr << "*** Register mapping ***\n"); 6505d0d1e350a30772fd70798b5733bb060febd7b0dAlkis Evlogimenos DEBUG(for (int i = 0, e = r2rMap_.size(); i != e; ++i) 6515d0d1e350a30772fd70798b5733bb060febd7b0dAlkis Evlogimenos if (r2rMap_[i]) 6525d0d1e350a30772fd70798b5733bb060febd7b0dAlkis Evlogimenos std::cerr << " reg " << i << " -> reg " << r2rMap_[i] << "\n"); 6531c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner} 6541c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner 6557ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner/// Return true if the two specified registers belong to different register 6567ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner/// classes. The registers may be either phys or virt regs. 6577ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattnerbool LiveIntervals::differingRegisterClasses(unsigned RegA, 6587ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner unsigned RegB) const { 6597ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner const TargetRegisterClass *RegClass; 6607ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 6617ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // Get the register classes for the first reg. 6627ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner if (MRegisterInfo::isVirtualRegister(RegA)) 6637ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner RegClass = mf_->getSSARegMap()->getRegClass(RegA); 6647ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner else 6657ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner RegClass = mri_->getRegClass(RegA); 6667ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 6677ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // Compare against the regclass for the second reg. 6687ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner if (MRegisterInfo::isVirtualRegister(RegB)) 6697ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner return RegClass != mf_->getSSARegMap()->getRegClass(RegB); 6707ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner else 671d0d0a1a08f9e27f4c950e846e0a21c3c3f11e40cChris Lattner return !RegClass->contains(RegB); 6727ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner} 6737ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 6747ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattnerbool LiveIntervals::overlapsAliases(const LiveInterval *LHS, 6757ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner const LiveInterval *RHS) const { 6767ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner if (!MRegisterInfo::isPhysicalRegister(LHS->reg)) { 6777ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner if (!MRegisterInfo::isPhysicalRegister(RHS->reg)) 6787ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner return false; // vreg-vreg merge has no aliases! 6797ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner std::swap(LHS, RHS); 6807ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner } 6817ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 6827ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner assert(MRegisterInfo::isPhysicalRegister(LHS->reg) && 6837ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner MRegisterInfo::isVirtualRegister(RHS->reg) && 6847ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner "first interval must describe a physical register"); 68579b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 6864df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner for (const unsigned *AS = mri_->getAliasSet(LHS->reg); *AS; ++AS) 6874df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner if (RHS->overlaps(getInterval(*AS))) 6884df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner return true; 68979b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 6904df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner return false; 69179b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos} 69279b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 693a1613db62fec94845aa8306232fb665273615badAlkis EvlogimenosLiveInterval LiveIntervals::createInterval(unsigned reg) { 6944df98e546dd0cca214df661ae1072e1a3f6eff98Chris Lattner float Weight = MRegisterInfo::isPhysicalRegister(reg) ? HUGE_VAL :0.0F; 695a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos return LiveInterval(reg, Weight); 6969a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 697