LiveIntervalAnalysis.cpp revision 1997473cf72957d0e70322e2fe6fe2ab141c58a6
1a3b8b5c0e0a1d0942288568b2012592184ca67c5Chris Lattner//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 2ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 3ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// The LLVM Compiler Infrastructure 4ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 5ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// This file was developed by the LLVM research group and is distributed under 6ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// the University of Illinois Open Source License. See LICENSE.TXT for details. 7ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 8ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos//===----------------------------------------------------------------------===// 9ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 10ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// This file implements the LiveInterval analysis pass which is used 11ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// by the Linear Scan Register allocator. This pass linearizes the 12ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// basic blocks of the function in DFS order and uses the 13ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// LiveVariables pass to conservatively compute live intervals for 14ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// each virtual and physical register. 15ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 16ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos//===----------------------------------------------------------------------===// 17ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 18ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#define DEBUG_TYPE "liveintervals" 193c3fe462f7978b429ecdd71750c26be25c3d1335Chris Lattner#include "llvm/CodeGen/LiveIntervalAnalysis.h" 2008a6c7614be9793754b17930ba619e875aef9585Misha Brukman#include "VirtRegMap.h" 21015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner#include "llvm/Value.h" 226b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos#include "llvm/Analysis/LoopInfo.h" 23ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/LiveVariables.h" 24ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 25ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineInstr.h" 26ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/Passes.h" 27ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/SSARegMap.h" 28ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/MRegisterInfo.h" 29ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 30ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 31551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 32551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 3320b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng#include "llvm/ADT/SmallSet.h" 34551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 35551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 3620aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 3797af751deb9b26fd42fbcee082da9ccc4ded5b45Jeff Cohen#include <cmath> 38ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 39ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 40cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numIntervals, "Number of original intervals"); 41cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numIntervalsAfter, "Number of intervals after coalescing"); 42cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numJoins , "Number of interval joins performed"); 43cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numPeep , "Number of identity moves eliminated after coalescing"); 44cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numFolded , "Number of loads/stores folded into instructions"); 45ba1a3df608a14ca37ca944f4c942c202e919ea80Evan ChengSTATISTIC(numAborts , "Number of times interval joining aborted"); 46cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 471997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar LiveIntervals::ID = 0; 48ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosnamespace { 495d8925c7c506a54ebdfb0bc93437ec9f602eaaa0Chris Lattner RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 50ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 51ed41f1bb1981a98eea63f00c5988cf62bbdd7c59Andrew Lenharth static cl::opt<bool> 521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos EnableJoining("join-liveintervals", 53428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner cl::desc("Coallesce copies (default=true)"), 541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos cl::init(true)); 55d74ea2bbd8bb630331f35ead42d385249bd42af8Chris Lattner} 56ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 57f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LiveVariables>(); 591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addPreservedID(PHIEliminationID); 601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(PHIEliminationID); 611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LoopInfo>(); 631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 64ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 65ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 66f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::releaseMemory() { 671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_.clear(); 681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_.clear(); 691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2rMap_.clear(); 7188d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng JoinedLIs.clear(); 7208cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos} 7308cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos 7408cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos 75993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Chengstatic bool isZeroLengthInterval(LiveInterval *li) { 76993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng for (LiveInterval::Ranges::const_iterator 77993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i) 78993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng if (i->end - i->start > LiveIntervals::InstrSlots::NUM) 79993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng return false; 80993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng return true; 81993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 82993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 83993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 84ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// runOnMachineFunction - Register allocate the whole function 85ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// 86ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mf_ = &fn; 881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos tm_ = &fn.getTarget(); 891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mri_ = tm_->getRegisterInfo(); 90f768bba43f5c036039851d2fcca8212edca18467Chris Lattner tii_ = tm_->getInstrInfo(); 911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos lv_ = &getAnalysis<LiveVariables>(); 922c4f7b5faaeedd97058ec4cfa44177124c42b9e1Alkis Evlogimenos r2rMap_.grow(mf_->getSSARegMap()->getLastVirtReg()); 9320b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng allocatableRegs_ = mri_->getAllocatableSet(fn); 9420b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng for (MRegisterInfo::regclass_iterator I = mri_->regclass_begin(), 9520b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng E = mri_->regclass_end(); I != E; ++I) 9620b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng allocatableRCRegs_.insert(std::make_pair(*I,mri_->getAllocatableSet(fn, *I))); 971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 98428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Number MachineInstrs and MachineBasicBlocks. 99428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Initialize MBB indexes to a sentinal. 100428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBB2IdxMap.resize(mf_->getNumBlockIDs(), ~0U); 101428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner 102428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned MIIndex = 0; 103428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); 104428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBB != E; ++MBB) { 105428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Set the MBB2IdxMap entry for this MBB. 106428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBB2IdxMap[MBB->getNumber()] = MIIndex; 1070c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 108428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 109428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner I != E; ++I) { 110428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; 1111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 112428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner i2miMap_.push_back(I); 113428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MIIndex += InstrSlots::NUM; 1141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 115428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner } 116ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 118ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 120843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 121bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** INTERVALS **********\n"; 122bdc679d564e67a81792e463f6614b0088f975025Bill Wendling for (iterator I = begin(), E = end(); I != E; ++I) { 123bdc679d564e67a81792e463f6614b0088f975025Bill Wendling I->second.print(DOUT, mri_); 124bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\n"; 125bdc679d564e67a81792e463f6614b0088f975025Bill Wendling } 1267ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 127428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Join (coallesce) intervals if requested. 12820b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng if (EnableJoining) { 12920b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng joinIntervals(); 13020b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng DOUT << "********** INTERVALS POST JOINING **********\n"; 13120b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng for (iterator I = begin(), E = end(); I != E; ++I) { 13220b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng I->second.print(DOUT, mri_); 13320b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng DOUT << "\n"; 13420b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng } 13520b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng } 1361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervalsAfter += getNumIntervals(); 1381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // perform a final pass over the instructions and compute spill 140fbecc5a593da0a5b4d9ff6be63c5558060e31e43Chris Lattner // weights, coalesce virtual registers and remove identity moves. 141428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner const LoopInfo &loopInfo = getAnalysis<LoopInfo>(); 1421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 1441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mbbi != mbbe; ++mbbi) { 1451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineBasicBlock* mbb = mbbi; 1461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 1471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); 1491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mii != mie; ) { 1501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // if the move will be an identity move delete it 1511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned srcReg, dstReg, RegRep; 152f768bba43f5c036039851d2fcca8212edca18467Chris Lattner if (tii_->isMoveInstr(*mii, srcReg, dstReg) && 1531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos (RegRep = rep(srcReg)) == rep(dstReg)) { 1541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // remove from def list 155b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng LiveInterval &RegInt = getOrCreateInterval(RegRep); 156b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineOperand *MO = mii->findRegisterDefOperand(dstReg); 157b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // If def of this move instruction is dead, remove its live range from 158b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // the dstination register's live interval. 159b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng if (MO->isDead()) { 160b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng unsigned MoveIdx = getDefIndex(getInstructionIndex(mii)); 161b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng LiveInterval::iterator MLR = RegInt.FindLiveRangeContaining(MoveIdx); 162b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng RegInt.removeRange(MLR->start, MoveIdx+1); 163b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng if (RegInt.empty()) 164b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng removeInterval(RegRep); 165b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 166f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner RemoveMachineInstrFromMaps(mii); 1671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mii = mbbi->erase(mii); 1681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ++numPeep; 1692638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng } else { 17020b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng SmallSet<unsigned, 4> UniqueUses; 171fbecc5a593da0a5b4d9ff6be63c5558060e31e43Chris Lattner for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { 172fbecc5a593da0a5b4d9ff6be63c5558060e31e43Chris Lattner const MachineOperand &mop = mii->getOperand(i); 1731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (mop.isRegister() && mop.getReg() && 1741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MRegisterInfo::isVirtualRegister(mop.getReg())) { 1751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // replace register with representative register 1761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned reg = rep(mop.getReg()); 177e53f4a055f74bded20d6129b4724ddd17fd199f6Chris Lattner mii->getOperand(i).setReg(reg); 1781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 17920b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng // Multiple uses of reg by the same instruction. It should not 18020b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng // contribute to spill weight again. 18120b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng if (UniqueUses.count(reg) != 0) 18220b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng continue; 1831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveInterval &RegInt = getInterval(reg); 184710216275b93b332bc69f41a1d4553197b64edf8Evan Cheng float w = (mop.isUse()+mop.isDef()) * powf(10.0F, (float)loopDepth); 185710216275b93b332bc69f41a1d4553197b64edf8Evan Cheng // If the definition instruction is re-materializable, its spill 1869193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng // weight is half of what it would have been normally unless it's 1879193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng // a load from fixed stack slot. 1889193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng int Dummy; 1899193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng if (RegInt.remat && !tii_->isLoadFromStackSlot(RegInt.remat, Dummy)) 190710216275b93b332bc69f41a1d4553197b64edf8Evan Cheng w /= 2; 191710216275b93b332bc69f41a1d4553197b64edf8Evan Cheng RegInt.weight += w; 19220b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng UniqueUses.insert(reg); 1931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ++mii; 1961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 1997a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 200993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng for (iterator I = begin(), E = end(); I != E; ++I) { 201b75a663707e40a6b72bf404e7fbf08f7d9e1eb90Chris Lattner LiveInterval &LI = I->second; 202b75a663707e40a6b72bf404e7fbf08f7d9e1eb90Chris Lattner if (MRegisterInfo::isVirtualRegister(LI.reg)) { 203c9d94d12900bd0d2bd482ef31f8f1deb3ffafa23Chris Lattner // If the live interval length is essentially zero, i.e. in every live 204993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng // range the use follows def immediately, it doesn't make sense to spill 205993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng // it and hope it will be easier to allocate for this li. 206b75a663707e40a6b72bf404e7fbf08f7d9e1eb90Chris Lattner if (isZeroLengthInterval(&LI)) 2077902c75331fa8f38fc8380f5573d935c0d149ef5Jim Laskey LI.weight = HUGE_VALF; 20820b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng 20920b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng // Slightly prefer live interval that has been assigned a preferred reg. 21020b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng if (LI.preference) 21120b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng LI.weight *= 1.01F; 21220b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng 213393ebae0ef7fa72d133bf901a02fcce3b5554ab7Chris Lattner // Divide the weight of the interval by its size. This encourages 214393ebae0ef7fa72d133bf901a02fcce3b5554ab7Chris Lattner // spilling of intervals that are large and have few uses, and 215393ebae0ef7fa72d133bf901a02fcce3b5554ab7Chris Lattner // discourages spilling of small intervals with many uses. 21620b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng LI.weight /= LI.getSize(); 217c9d94d12900bd0d2bd482ef31f8f1deb3ffafa23Chris Lattner } 218993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng } 219993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 22070ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 2211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 222ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 223ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 22470ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 225ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencervoid LiveIntervals::print(std::ostream &O, const Module* ) const { 22670ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** INTERVALS **********\n"; 2278e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 228bdc679d564e67a81792e463f6614b0088f975025Bill Wendling I->second.print(DOUT, mri_); 229bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\n"; 2308e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 23170ca358b7d540b6061236ddf757085042873c12cChris Lattner 23270ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** MACHINEINSTRS **********\n"; 23370ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 23470ca358b7d540b6061236ddf757085042873c12cChris Lattner mbbi != mbbe; ++mbbi) { 23570ca358b7d540b6061236ddf757085042873c12cChris Lattner O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 23670ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineBasicBlock::iterator mii = mbbi->begin(), 23770ca358b7d540b6061236ddf757085042873c12cChris Lattner mie = mbbi->end(); mii != mie; ++mii) { 238477e4555de341c5de780de3720d6f115ec133c4eChris Lattner O << getInstructionIndex(mii) << '\t' << *mii; 23970ca358b7d540b6061236ddf757085042873c12cChris Lattner } 24070ca358b7d540b6061236ddf757085042873c12cChris Lattner } 24170ca358b7d540b6061236ddf757085042873c12cChris Lattner} 24270ca358b7d540b6061236ddf757085042873c12cChris Lattner 24301352aa1875ee08ae847cce398322042830d92edBill Wendling/// CreateNewLiveInterval - Create a new live interval with the given live 24401352aa1875ee08ae847cce398322042830d92edBill Wendling/// ranges. The new live interval will have an infinite spill weight. 24501352aa1875ee08ae847cce398322042830d92edBill WendlingLiveInterval& 24601352aa1875ee08ae847cce398322042830d92edBill WendlingLiveIntervals::CreateNewLiveInterval(const LiveInterval *LI, 24701352aa1875ee08ae847cce398322042830d92edBill Wendling const std::vector<LiveRange> &LRs) { 24801352aa1875ee08ae847cce398322042830d92edBill Wendling const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(LI->reg); 24901352aa1875ee08ae847cce398322042830d92edBill Wendling 25001352aa1875ee08ae847cce398322042830d92edBill Wendling // Create a new virtual register for the spill interval. 25101352aa1875ee08ae847cce398322042830d92edBill Wendling unsigned NewVReg = mf_->getSSARegMap()->createVirtualRegister(RC); 25201352aa1875ee08ae847cce398322042830d92edBill Wendling 25301352aa1875ee08ae847cce398322042830d92edBill Wendling // Replace the old virtual registers in the machine operands with the shiny 25401352aa1875ee08ae847cce398322042830d92edBill Wendling // new one. 25501352aa1875ee08ae847cce398322042830d92edBill Wendling for (std::vector<LiveRange>::const_iterator 25601352aa1875ee08ae847cce398322042830d92edBill Wendling I = LRs.begin(), E = LRs.end(); I != E; ++I) { 25701352aa1875ee08ae847cce398322042830d92edBill Wendling unsigned Index = getBaseIndex(I->start); 25801352aa1875ee08ae847cce398322042830d92edBill Wendling unsigned End = getBaseIndex(I->end - 1) + InstrSlots::NUM; 25901352aa1875ee08ae847cce398322042830d92edBill Wendling 26001352aa1875ee08ae847cce398322042830d92edBill Wendling for (; Index != End; Index += InstrSlots::NUM) { 26101352aa1875ee08ae847cce398322042830d92edBill Wendling // Skip deleted instructions 26201352aa1875ee08ae847cce398322042830d92edBill Wendling while (Index != End && !getInstructionFromIndex(Index)) 26301352aa1875ee08ae847cce398322042830d92edBill Wendling Index += InstrSlots::NUM; 26401352aa1875ee08ae847cce398322042830d92edBill Wendling 26501352aa1875ee08ae847cce398322042830d92edBill Wendling if (Index == End) break; 26601352aa1875ee08ae847cce398322042830d92edBill Wendling 26701352aa1875ee08ae847cce398322042830d92edBill Wendling MachineInstr *MI = getInstructionFromIndex(Index); 26801352aa1875ee08ae847cce398322042830d92edBill Wendling 269beeb77f3ae9e784f45ede2e38f51b9b25eb65913Bill Wendling for (unsigned J = 0, e = MI->getNumOperands(); J != e; ++J) { 27001352aa1875ee08ae847cce398322042830d92edBill Wendling MachineOperand &MOp = MI->getOperand(J); 27101352aa1875ee08ae847cce398322042830d92edBill Wendling if (MOp.isRegister() && rep(MOp.getReg()) == LI->reg) 27201352aa1875ee08ae847cce398322042830d92edBill Wendling MOp.setReg(NewVReg); 27301352aa1875ee08ae847cce398322042830d92edBill Wendling } 27401352aa1875ee08ae847cce398322042830d92edBill Wendling } 27501352aa1875ee08ae847cce398322042830d92edBill Wendling } 27601352aa1875ee08ae847cce398322042830d92edBill Wendling 27701352aa1875ee08ae847cce398322042830d92edBill Wendling LiveInterval &NewLI = getOrCreateInterval(NewVReg); 27801352aa1875ee08ae847cce398322042830d92edBill Wendling 27901352aa1875ee08ae847cce398322042830d92edBill Wendling // The spill weight is now infinity as it cannot be spilled again 28001352aa1875ee08ae847cce398322042830d92edBill Wendling NewLI.weight = float(HUGE_VAL); 28101352aa1875ee08ae847cce398322042830d92edBill Wendling 28201352aa1875ee08ae847cce398322042830d92edBill Wendling for (std::vector<LiveRange>::const_iterator 28301352aa1875ee08ae847cce398322042830d92edBill Wendling I = LRs.begin(), E = LRs.end(); I != E; ++I) { 284bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " Adding live range " << *I << " to new interval\n"; 28501352aa1875ee08ae847cce398322042830d92edBill Wendling NewLI.addRange(*I); 28601352aa1875ee08ae847cce398322042830d92edBill Wendling } 28701352aa1875ee08ae847cce398322042830d92edBill Wendling 288bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "Created new live interval " << NewLI << "\n"; 28901352aa1875ee08ae847cce398322042830d92edBill Wendling return NewLI; 29001352aa1875ee08ae847cce398322042830d92edBill Wendling} 29101352aa1875ee08ae847cce398322042830d92edBill Wendling 29270ca358b7d540b6061236ddf757085042873c12cChris Lattnerstd::vector<LiveInterval*> LiveIntervals:: 29370ca358b7d540b6061236ddf757085042873c12cChris LattneraddIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { 294d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // since this is called after the analysis is done we don't know if 295d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // LiveVariables is available 296d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos lv_ = getAnalysisToUpdate<LiveVariables>(); 297d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos 2981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos std::vector<LiveInterval*> added; 2991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3007902c75331fa8f38fc8380f5573d935c0d149ef5Jim Laskey assert(li.weight != HUGE_VALF && 3011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "attempt to spill already spilled interval!"); 3021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 303bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\t\t\tadding intervals for spills for interval: "; 304bdc679d564e67a81792e463f6614b0088f975025Bill Wendling li.print(DOUT, mri_); 305bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << '\n'; 3061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg); 3081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (LiveInterval::Ranges::const_iterator 3101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 3111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned index = getBaseIndex(i->start); 3121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = getBaseIndex(i->end-1) + InstrSlots::NUM; 3131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (; index != end; index += InstrSlots::NUM) { 3141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // skip deleted instructions 3151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos while (index != end && !getInstructionFromIndex(index)) 3161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos index += InstrSlots::NUM; 3171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (index == end) break; 3181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3193b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner MachineInstr *MI = getInstructionFromIndex(index); 3201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3212926869b4a083fc951484de03a9867eabf81e880Chris Lattner RestartInstruction: 3223b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 3233b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner MachineOperand& mop = MI->getOperand(i); 3241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (mop.isRegister() && mop.getReg() == li.reg) { 3252638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng MachineInstr *fmi = li.remat ? NULL 3262638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng : mri_->foldMemoryOperand(MI, i, slot); 3272638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng if (fmi) { 328b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // Attempt to fold the memory reference into the instruction. If we 329b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner // can do this, we don't need to insert spill code. 330d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos if (lv_) 3313b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner lv_->instructionChanged(MI, fmi); 332200370fb5617a1719f0054804b412469ce486ebdEvan Cheng MachineBasicBlock &MBB = *MI->getParent(); 33335f2705e3de4600c3621b883eed9b22e4607ddf4Chris Lattner vrm.virtFolded(li.reg, MI, i, fmi); 3343b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner mi2iMap_.erase(MI); 3351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_[index/InstrSlots::NUM] = fmi; 3361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_[fmi] = index; 3373b9db830f7f0ed33af13459be3fd60ebe01a13caChris Lattner MI = MBB.insert(MBB.erase(MI), fmi); 3381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ++numFolded; 339477e4555de341c5de780de3720d6f115ec133c4eChris Lattner // Folding the load/store can completely change the instruction in 340477e4555de341c5de780de3720d6f115ec133c4eChris Lattner // unpredictable ways, rescan it from the beginning. 3412926869b4a083fc951484de03a9867eabf81e880Chris Lattner goto RestartInstruction; 342477e4555de341c5de780de3720d6f115ec133c4eChris Lattner } else { 3432926869b4a083fc951484de03a9867eabf81e880Chris Lattner // Create a new virtual register for the spill interval. 3442926869b4a083fc951484de03a9867eabf81e880Chris Lattner unsigned NewVReg = mf_->getSSARegMap()->createVirtualRegister(rc); 3452926869b4a083fc951484de03a9867eabf81e880Chris Lattner 3462926869b4a083fc951484de03a9867eabf81e880Chris Lattner // Scan all of the operands of this instruction rewriting operands 3472926869b4a083fc951484de03a9867eabf81e880Chris Lattner // to use NewVReg instead of li.reg as appropriate. We do this for 3482926869b4a083fc951484de03a9867eabf81e880Chris Lattner // two reasons: 3491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // 3502926869b4a083fc951484de03a9867eabf81e880Chris Lattner // 1. If the instr reads the same spilled vreg multiple times, we 3512926869b4a083fc951484de03a9867eabf81e880Chris Lattner // want to reuse the NewVReg. 3522926869b4a083fc951484de03a9867eabf81e880Chris Lattner // 2. If the instr is a two-addr instruction, we are required to 3532926869b4a083fc951484de03a9867eabf81e880Chris Lattner // keep the src/dst regs pinned. 3542926869b4a083fc951484de03a9867eabf81e880Chris Lattner // 3552926869b4a083fc951484de03a9867eabf81e880Chris Lattner // Keep track of whether we replace a use and/or def so that we can 3562926869b4a083fc951484de03a9867eabf81e880Chris Lattner // create the spill interval with the appropriate range. 3572926869b4a083fc951484de03a9867eabf81e880Chris Lattner mop.setReg(NewVReg); 3582926869b4a083fc951484de03a9867eabf81e880Chris Lattner 3592926869b4a083fc951484de03a9867eabf81e880Chris Lattner bool HasUse = mop.isUse(); 3602926869b4a083fc951484de03a9867eabf81e880Chris Lattner bool HasDef = mop.isDef(); 3612926869b4a083fc951484de03a9867eabf81e880Chris Lattner for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 3622926869b4a083fc951484de03a9867eabf81e880Chris Lattner if (MI->getOperand(j).isReg() && 3632926869b4a083fc951484de03a9867eabf81e880Chris Lattner MI->getOperand(j).getReg() == li.reg) { 3642926869b4a083fc951484de03a9867eabf81e880Chris Lattner MI->getOperand(j).setReg(NewVReg); 3652926869b4a083fc951484de03a9867eabf81e880Chris Lattner HasUse |= MI->getOperand(j).isUse(); 3662926869b4a083fc951484de03a9867eabf81e880Chris Lattner HasDef |= MI->getOperand(j).isDef(); 3672926869b4a083fc951484de03a9867eabf81e880Chris Lattner } 3682926869b4a083fc951484de03a9867eabf81e880Chris Lattner } 3691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // create a new register for this spill 3711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos vrm.grow(); 3722638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng if (li.remat) 3732638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng vrm.setVirtIsReMaterialized(NewVReg, li.remat); 3742926869b4a083fc951484de03a9867eabf81e880Chris Lattner vrm.assignVirt2StackSlot(NewVReg, slot); 3752926869b4a083fc951484de03a9867eabf81e880Chris Lattner LiveInterval &nI = getOrCreateInterval(NewVReg); 3762638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng nI.remat = li.remat; 3771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(nI.empty()); 37870ca358b7d540b6061236ddf757085042873c12cChris Lattner 3791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the spill weight is now infinity as it 3801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // cannot be spilled again 3817902c75331fa8f38fc8380f5573d935c0d149ef5Jim Laskey nI.weight = HUGE_VALF; 3822926869b4a083fc951484de03a9867eabf81e880Chris Lattner 3832926869b4a083fc951484de03a9867eabf81e880Chris Lattner if (HasUse) { 3842926869b4a083fc951484de03a9867eabf81e880Chris Lattner LiveRange LR(getLoadIndex(index), getUseIndex(index), 3852926869b4a083fc951484de03a9867eabf81e880Chris Lattner nI.getNextValue(~0U, 0)); 386bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 3872926869b4a083fc951484de03a9867eabf81e880Chris Lattner nI.addRange(LR); 3882926869b4a083fc951484de03a9867eabf81e880Chris Lattner } 3892926869b4a083fc951484de03a9867eabf81e880Chris Lattner if (HasDef) { 3902926869b4a083fc951484de03a9867eabf81e880Chris Lattner LiveRange LR(getDefIndex(index), getStoreIndex(index), 3912926869b4a083fc951484de03a9867eabf81e880Chris Lattner nI.getNextValue(~0U, 0)); 392bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 3932926869b4a083fc951484de03a9867eabf81e880Chris Lattner nI.addRange(LR); 3942926869b4a083fc951484de03a9867eabf81e880Chris Lattner } 3952926869b4a083fc951484de03a9867eabf81e880Chris Lattner 3961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos added.push_back(&nI); 39770ca358b7d540b6061236ddf757085042873c12cChris Lattner 398d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos // update live variables if it is available 399d8d26b3268acf7f157028f0cb60a545b185e8905Alkis Evlogimenos if (lv_) 4002926869b4a083fc951484de03a9867eabf81e880Chris Lattner lv_->addVirtualRegisterKilled(NewVReg, MI); 401b11443dc8458b0ba72d484dacf99dffa2e8d3b51Chris Lattner 402bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\t\t\tadded new interval: "; 403bdc679d564e67a81792e463f6614b0088f975025Bill Wendling nI.print(DOUT, mri_); 404bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << '\n'; 4051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 406843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 4071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 408843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 4091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 41026f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos 4111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return added; 412843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos} 413843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 414be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::printRegName(unsigned reg) const { 4151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(reg)) 416e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling cerr << mri_->getName(reg); 4171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 418e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling cerr << "%reg" << reg; 419ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 420ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 421bf105c842450d3308d024be203ddd533f37051ecEvan Cheng/// isReDefinedByTwoAddr - Returns true if the Reg re-definition is due to 422bf105c842450d3308d024be203ddd533f37051ecEvan Cheng/// two addr elimination. 423bf105c842450d3308d024be203ddd533f37051ecEvan Chengstatic bool isReDefinedByTwoAddr(MachineInstr *MI, unsigned Reg, 424bf105c842450d3308d024be203ddd533f37051ecEvan Cheng const TargetInstrInfo *TII) { 425bf105c842450d3308d024be203ddd533f37051ecEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 426bf105c842450d3308d024be203ddd533f37051ecEvan Cheng MachineOperand &MO1 = MI->getOperand(i); 427bf105c842450d3308d024be203ddd533f37051ecEvan Cheng if (MO1.isRegister() && MO1.isDef() && MO1.getReg() == Reg) { 428bf105c842450d3308d024be203ddd533f37051ecEvan Cheng for (unsigned j = i+1; j < e; ++j) { 429bf105c842450d3308d024be203ddd533f37051ecEvan Cheng MachineOperand &MO2 = MI->getOperand(j); 430bf105c842450d3308d024be203ddd533f37051ecEvan Cheng if (MO2.isRegister() && MO2.isUse() && MO2.getReg() == Reg && 43151cdcd197268a7abf19b2698fc824e0da3d98049Evan Cheng MI->getInstrDescriptor()-> 43251cdcd197268a7abf19b2698fc824e0da3d98049Evan Cheng getOperandConstraint(j, TOI::TIED_TO) == (int)i) 433bf105c842450d3308d024be203ddd533f37051ecEvan Cheng return true; 434bf105c842450d3308d024be203ddd533f37051ecEvan Cheng } 435bf105c842450d3308d024be203ddd533f37051ecEvan Cheng } 436bf105c842450d3308d024be203ddd533f37051ecEvan Cheng } 437bf105c842450d3308d024be203ddd533f37051ecEvan Cheng return false; 438bf105c842450d3308d024be203ddd533f37051ecEvan Cheng} 439bf105c842450d3308d024be203ddd533f37051ecEvan Cheng 440be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 441ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 4426b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 443be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 444bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 4451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 4461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 447706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 448706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 449706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 4501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 4511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 4529193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng // Remember if the definition can be rematerialized. All load's from fixed 4539193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng // stack slots are re-materializable. 4549193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng int FrameIdx = 0; 4559193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng if (vi.DefInst && 4569193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng (tii_->isReMaterializable(vi.DefInst->getOpcode()) || 4579193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng (tii_->isLoadFromStackSlot(vi.DefInst, FrameIdx) && 4589193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx)))) 4592638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng interval.remat = vi.DefInst; 4602638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng 4611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 4626b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 4631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 46491725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned ValNum; 46591725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 46691725b75852443923b419fd23215194cfc65dd88Chris Lattner if (!tii_->isMoveInstr(*mi, SrcReg, DstReg)) 46791725b75852443923b419fd23215194cfc65dd88Chris Lattner ValNum = interval.getNextValue(~0U, 0); 46891725b75852443923b419fd23215194cfc65dd88Chris Lattner else 46991725b75852443923b419fd23215194cfc65dd88Chris Lattner ValNum = interval.getNextValue(defIndex, SrcReg); 47091725b75852443923b419fd23215194cfc65dd88Chris Lattner 4711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(ValNum == 0 && "First value in interval is not 0?"); 4721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ValNum = 0; // Clue in the optimizer. 4731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 4751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 4761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 4771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 4781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 4791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 4801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned killIdx; 4811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 4821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 4831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 4841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = defIndex+1; 4851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 4871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 4881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 48961de82d8853a02fe39c47302432abb70a586704fEvan Cheng assert(vi.AliveBlocks.none() && 4901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 4911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveRange LR(defIndex, killIdx, ValNum); 4921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 493bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << "\n"; 4941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 4951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4976097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 4981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 4991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 5001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 5011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 502d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos LiveRange NewLR(defIndex, 503d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 504d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos ValNum); 505bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << NewLR; 5061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 5071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Iterate over all of the blocks that the variable is completely 5091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 5101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live interval. 5111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 5121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.AliveBlocks[i]) { 513428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = mf_->getBlockNumbered(i); 514428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner if (!MBB->empty()) { 515428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner LiveRange LR(getMBBStartIdx(i), 516428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner getInstructionIndex(&MBB->back()) + InstrSlots::NUM, 5171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos ValNum); 5181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 519bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 5201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 5251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 5261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 5271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 528428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner LiveRange LR(getMBBStartIdx(Kill->getParent()), 529d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos getUseIndex(getInstructionIndex(Kill))+1, 530d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos ValNum); 5311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 532bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 5331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 5369193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng // Can no longer safely assume definition is rematerializable. 5372638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng interval.remat = NULL; 5382638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng 5391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 5401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 541bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 542bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 543bf105c842450d3308d024be203ddd533f37051ecEvan Cheng if (isReDefinedByTwoAddr(mi, interval.reg, tii_)) { 5441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 5451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 5461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 5471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 5481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 5491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst)); 5506b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned RedefIndex = getDefIndex(MIIdx); 5511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Delete the initial value, which should be short and continuous, 553be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 5541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 555706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 556be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Two-address vregs should always only be redefined once. This means 557be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // that at this point, there should be exactly one value number in it. 558be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 559be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 56091725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 56191725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 56291725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned ValNo = interval.getNextValue(0, 0); 56391725b75852443923b419fd23215194cfc65dd88Chris Lattner interval.setValueNumberInfo(1, interval.getValNumInfo(0)); 564be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 56591725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 56691725b75852443923b419fd23215194cfc65dd88Chris Lattner interval.setValueNumberInfo(0, std::make_pair(~0U, 0U)); 567be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 568be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 569be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 570bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 5711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 5721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 5741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 575ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->RegisterDefIsDead(mi, interval.reg)) 576ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0)); 5771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 57856fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " RESULT: "; 579bdc679d564e67a81792e463f6614b0088f975025Bill Wendling interval.print(DOUT, mri_); 5801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 5821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Otherwise, this must be because of phi elimination. If this is the 5831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // first redefinition of the vreg that we have seen, go back and change 5841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range in the PHI block to be a different value number. 5851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.containsOneValue()) { 5861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(vi.Kills.size() == 1 && 5871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "PHI elimination vreg should have one kill, the PHI itself!"); 5881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Remove the old range that we now know has an incorrect number. 5901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Killer = vi.Kills[0]; 591428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned Start = getMBBStartIdx(Killer->getParent()); 5921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 59356fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " Removing [" << Start << "," << End << "] from: "; 594bdc679d564e67a81792e463f6614b0088f975025Bill Wendling interval.print(DOUT, mri_); DOUT << "\n"; 5951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(Start, End); 59656fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " RESULT: "; interval.print(DOUT, mri_); 5971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 598be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Replace the interval with one of a NEW value number. Note that this 599be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // value number isn't actually defined by an instruction, weird huh? :) 60091725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveRange LR(Start, End, interval.getNextValue(~0U, 0)); 601bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 6021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 60356fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " RESULT: "; interval.print(DOUT, mri_); 6041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 6051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 6061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 6071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 6081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 6096b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 61091725b75852443923b419fd23215194cfc65dd88Chris Lattner 61191725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned ValNum; 61291725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 61391725b75852443923b419fd23215194cfc65dd88Chris Lattner if (!tii_->isMoveInstr(*mi, SrcReg, DstReg)) 61491725b75852443923b419fd23215194cfc65dd88Chris Lattner ValNum = interval.getNextValue(~0U, 0); 61591725b75852443923b419fd23215194cfc65dd88Chris Lattner else 61691725b75852443923b419fd23215194cfc65dd88Chris Lattner ValNum = interval.getNextValue(defIndex, SrcReg); 61791725b75852443923b419fd23215194cfc65dd88Chris Lattner 618706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos LiveRange LR(defIndex, 61991725b75852443923b419fd23215194cfc65dd88Chris Lattner getInstructionIndex(&mbb->back()) + InstrSlots::NUM, ValNum); 6201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 621bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 622dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 6231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 624ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 625bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << '\n'; 626ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 627ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 628f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 629ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 6306b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 63191725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveInterval &interval, 63291725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg) { 6331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 6341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 635bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 6361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 6376b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned baseIndex = MIIdx; 6381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned start = getDefIndex(baseIndex); 6391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = start; 6401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 6411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 6421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 6431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 644ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->RegisterDefIsDead(mi, interval.reg)) { 645bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 646ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getDefIndex(start) + 1; 647ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 6481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 649ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 6501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 6511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 6521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 6535ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 6541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos baseIndex += InstrSlots::NUM; 655ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->KillsRegister(mi, interval.reg)) { 656bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " killed"; 657ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getUseIndex(baseIndex) + 1; 658ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 6599a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng } else if (lv_->ModifiesRegister(mi, interval.reg)) { 6609a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // Another instruction redefines the register before it is ever read. 6619a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // Then the register is essentially dead at the instruction that defines 6629a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // it. Hence its interval is: 6639a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // [defSlot(def), defSlot(def)+1) 664bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 6659a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng end = getDefIndex(start) + 1; 6669a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng goto exit; 667f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 6681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 6695ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner 6705ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 6715ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 6725ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // and never used. 67391725b75852443923b419fd23215194cfc65dd88Chris Lattner assert(!SrcReg && "physreg was not killed in defining block!"); 6745ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner end = getDefIndex(start) + 1; // It's dead. 67502ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 676ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 6771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 678f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 67924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 68024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 68124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng unsigned Id = (OldLR != interval.end()) 68224a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng ? OldLR->ValId 68324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng : interval.getNextValue(SrcReg != 0 ? start : ~0U, SrcReg); 68424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveRange LR(start, end, Id); 6851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 686bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << '\n'; 687ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 688ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 689f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 690f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 6916b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 692f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner unsigned reg) { 693f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner if (MRegisterInfo::isVirtualRegister(reg)) 6946b128bdc58a496e9f08e4d09416330320761baffChris Lattner handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg)); 6955327801fb87e3eda52a33f82e6211181030ecb93Alkis Evlogimenos else if (allocatableRegs_[reg]) { 69691725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 69791725b75852443923b419fd23215194cfc65dd88Chris Lattner if (!tii_->isMoveInstr(*MI, SrcReg, DstReg)) 69891725b75852443923b419fd23215194cfc65dd88Chris Lattner SrcReg = 0; 6996b128bdc58a496e9f08e4d09416330320761baffChris Lattner handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg); 70024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Def of a register also defines its sub-registers. 70124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng for (const unsigned* AS = mri_->getSubRegisters(reg); *AS; ++AS) 70224a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Avoid processing some defs more than once. 70324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng if (!MI->findRegisterDefOperand(*AS)) 70424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0); 705f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 7064d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 7074d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 708b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 7099b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned MIIdx, 71024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 711b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 712b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 713b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 714b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 715b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 7169b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned baseIndex = MIIdx; 7179b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned start = baseIndex; 718b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng unsigned end = start; 719b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng while (mi != MBB->end()) { 720b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng if (lv_->KillsRegister(mi, interval.reg)) { 721b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " killed"; 722b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getUseIndex(baseIndex) + 1; 723b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 724b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } else if (lv_->ModifiesRegister(mi, interval.reg)) { 725b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Another instruction redefines the register before it is ever read. 726b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Then the register is essentially dead at the instruction that defines 727b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // it. Hence its interval is: 728b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // [defSlot(def), defSlot(def)+1) 729b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " dead"; 730b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getDefIndex(start) + 1; 731b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 732b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 733b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 734b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng baseIndex += InstrSlots::NUM; 735b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng ++mi; 736b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 737b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 738b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengexit: 73924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Alias of a live-in register might not be used at all. 74024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng if (isAlias && end == 0) { 74124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng DOUT << " dead"; 74224a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng end = getDefIndex(start) + 1; 74324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 74424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 745b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng assert(start < end && "did not find end of interval?"); 746b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 747b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng LiveRange LR(start, end, interval.getNextValue(~0U, 0)); 748b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " +" << LR << '\n'; 7499b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 750b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 751b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 752ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 7534d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 75408cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 755ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 756f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::computeIntervals() { 757bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 758bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << "********** Function: " 759bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'; 7606b128bdc58a496e9f08e4d09416330320761baffChris Lattner // Track the index of the current machine instr. 7616b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIndex = 0; 762428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 763428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 764428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 765bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 7661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 767428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 7680c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 7690c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng if (MBB->livein_begin() != MBB->livein_end()) { 770b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Create intervals for live-ins to this BB first. 771b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 7720c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng LE = MBB->livein_end(); LI != LE; ++LI) { 7739b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 77424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Multiple live-ins can alias the same register. 77524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS) 77624a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng if (!hasInterval(*AS)) 77724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), true); 7780c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng } 779dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 780dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner 781428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (; MI != miEnd; ++MI) { 782bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << MIIndex << "\t" << *MI; 7831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 784438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 785428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 786428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 7871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 788428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner if (MO.isRegister() && MO.getReg() && MO.isDef()) 789428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner handleRegisterDef(MBB, MI, MIIndex, MO.getReg()); 7901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 7916b128bdc58a496e9f08e4d09416330320761baffChris Lattner 7926b128bdc58a496e9f08e4d09416330320761baffChris Lattner MIIndex += InstrSlots::NUM; 793ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 7941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 795ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 796b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 797f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// AdjustCopiesBackFrom - We found a non-trivially-coallescable copy with IntA 798f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// being the source and IntB being the dest, thus this defines a value number 799f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// in IntB. If the source value number (in IntA) is defined by a copy from B, 800f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// see if we can merge these two pieces of B into a single value number, 801f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// eliminating a copy. For example: 802f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// 803f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// A3 = B0 804f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// ... 805f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// B1 = A3 <- this copy 806f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// 807f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// In this case, B0 can be extended to where the B1 copy lives, allowing the B1 808f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// value number to be replaced with B0 (which simplifies the B liveinterval). 809f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// 810f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// This returns true if an interval was modified. 811f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// 812f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnerbool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, 8136d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner MachineInstr *CopyMI) { 8146d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner unsigned CopyIdx = getDefIndex(getInstructionIndex(CopyMI)); 8156d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 816f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // BValNo is a value number in B that is defined by a copy from A. 'B3' in 817f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // the example above. 818f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); 819f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner unsigned BValNo = BLR->ValId; 820f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 821f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Get the location that B is defined at. Two options: either this value has 822f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // an unknown definition point or it is defined at CopyIdx. If unknown, we 823f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // can't process it. 824f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner unsigned BValNoDefIdx = IntB.getInstForValNum(BValNo); 825f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (BValNoDefIdx == ~0U) return false; 826f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner assert(BValNoDefIdx == CopyIdx && 827f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner "Copy doesn't define the value?"); 828f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 829f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // AValNo is the value number in A that defines the copy, A0 in the example. 830f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LiveInterval::iterator AValLR = IntA.FindLiveRangeContaining(CopyIdx-1); 831f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner unsigned AValNo = AValLR->ValId; 832aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 833f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // If AValNo is defined as a copy from IntB, we can potentially process this. 834aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 835f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Get the instruction that defines this value number. 83691725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg = IntA.getSrcRegForValNum(AValNo); 83791725b75852443923b419fd23215194cfc65dd88Chris Lattner if (!SrcReg) return false; // Not defined by a copy. 838aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 839f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // If the value number is not defined by a copy instruction, ignore it. 840aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 841f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // If the source register comes from an interval other than IntB, we can't 842f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // handle this. 843f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (rep(SrcReg) != IntB.reg) return false; 84491725b75852443923b419fd23215194cfc65dd88Chris Lattner 845f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Get the LiveRange in IntB that this value number starts with. 84691725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned AValNoInstIdx = IntA.getInstForValNum(AValNo); 847f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNoInstIdx-1); 848aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 849f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Make sure that the end of the live range is inside the same block as 850f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // CopyMI. 851f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner MachineInstr *ValLREndInst = getInstructionFromIndex(ValLR->end-1); 852c114b2cad7293d98686d380273085f5c32966b52Chris Lattner if (!ValLREndInst || 853c114b2cad7293d98686d380273085f5c32966b52Chris Lattner ValLREndInst->getParent() != CopyMI->getParent()) return false; 854f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 855f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, we now know that ValLR ends in the same block that the CopyMI 856f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // live-range starts. If there are no intervening live ranges between them in 857f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // IntB, we can merge them. 858f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (ValLR+1 != BLR) return false; 859aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 860bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\nExtending: "; IntB.print(DOUT, mri_); 861ba256037ced5606d5cea8a1676b21eaf91d924deChris Lattner 862ba256037ced5606d5cea8a1676b21eaf91d924deChris Lattner // We are about to delete CopyMI, so need to remove it as the 'instruction 863ba256037ced5606d5cea8a1676b21eaf91d924deChris Lattner // that defines this value #'. 86491725b75852443923b419fd23215194cfc65dd88Chris Lattner IntB.setValueNumberInfo(BValNo, std::make_pair(~0U, 0)); 865ba256037ced5606d5cea8a1676b21eaf91d924deChris Lattner 866f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, we can merge them. We need to insert a new liverange: 867f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // [ValLR.end, BLR.begin) of either value number, then we merge the 868f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // two value numbers. 869c114b2cad7293d98686d380273085f5c32966b52Chris Lattner unsigned FillerStart = ValLR->end, FillerEnd = BLR->start; 870c114b2cad7293d98686d380273085f5c32966b52Chris Lattner IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo)); 871c114b2cad7293d98686d380273085f5c32966b52Chris Lattner 872c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // If the IntB live range is assigned to a physical register, and if that 873c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // physreg has aliases, 874c114b2cad7293d98686d380273085f5c32966b52Chris Lattner if (MRegisterInfo::isPhysicalRegister(IntB.reg)) { 87524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Update the liveintervals of sub-registers. 87624a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng for (const unsigned *AS = mri_->getSubRegisters(IntB.reg); *AS; ++AS) { 877c114b2cad7293d98686d380273085f5c32966b52Chris Lattner LiveInterval &AliasLI = getInterval(*AS); 878c114b2cad7293d98686d380273085f5c32966b52Chris Lattner AliasLI.addRange(LiveRange(FillerStart, FillerEnd, 87991725b75852443923b419fd23215194cfc65dd88Chris Lattner AliasLI.getNextValue(~0U, 0))); 880c114b2cad7293d98686d380273085f5c32966b52Chris Lattner } 881c114b2cad7293d98686d380273085f5c32966b52Chris Lattner } 882f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 883f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, merge "B1" into the same value number as "B0". 884f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (BValNo != ValLR->ValId) 885f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner IntB.MergeValueNumberInto(BValNo, ValLR->ValId); 886bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " result = "; IntB.print(DOUT, mri_); 887bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\n"; 88816191f03337645dc1638b7489d71d685e6c07cddEvan Cheng 88916191f03337645dc1638b7489d71d685e6c07cddEvan Cheng // If the source instruction was killing the source register before the 89016191f03337645dc1638b7489d71d685e6c07cddEvan Cheng // merge, unset the isKill marker given the live range has been extended. 891faa510726f4b40aa4495e60e4d341c6467e3fb01Evan Cheng int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true); 892ad7ccf34b5de14bd2b9ddc8072d14582a2ce29d9Evan Cheng if (UIdx != -1) 893ad7ccf34b5de14bd2b9ddc8072d14582a2ce29d9Evan Cheng ValLREndInst->getOperand(UIdx).unsetIsKill(); 894f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 895f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Finally, delete the copy instruction. 896f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner RemoveMachineInstrFromMaps(CopyMI); 897f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner CopyMI->eraseFromParent(); 898f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner ++numPeep; 899aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner return true; 900aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner} 901aa51a484e188ecb8d3e4b6ac852c553a4aacc89aChris Lattner 90220b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng 903f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 904f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// which are the src/dst of the copy instruction CopyMI. This returns true 905f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// if the copy was successfully coallesced away, or if it is never possible 90620b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng/// to coallesce this copy, due to register constraints. It returns 907f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// false if it is not currently possible to coallesce this interval, but 908f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// it may be possible if other things get coallesced. 909f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnerbool LiveIntervals::JoinCopy(MachineInstr *CopyMI, 91020b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng unsigned SrcReg, unsigned DstReg, bool PhysOnly) { 911bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << getInstructionIndex(CopyMI) << '\t' << *CopyMI; 912b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 913f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Get representative registers. 914b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng unsigned repSrcReg = rep(SrcReg); 915b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng unsigned repDstReg = rep(DstReg); 916f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 917f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // If they are already joined we continue. 918b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng if (repSrcReg == repDstReg) { 919bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\tCopy already coallesced.\n"; 920f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return true; // Not coallescable. 921f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 922f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 92320b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng bool SrcIsPhys = MRegisterInfo::isPhysicalRegister(repSrcReg); 92420b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng bool DstIsPhys = MRegisterInfo::isPhysicalRegister(repDstReg); 92520b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng if (PhysOnly && !SrcIsPhys && !DstIsPhys) 92620b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng // Only joining physical registers with virtual registers in this round. 92720b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng return true; 92820b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng 929f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // If they are both physical registers, we cannot join them. 93020b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng if (SrcIsPhys && DstIsPhys) { 931bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\tCan not coallesce physregs.\n"; 932f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return true; // Not coallescable. 9337ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner } 934f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 935f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // We only join virtual registers with allocatable physical registers. 93620b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng if (SrcIsPhys && !allocatableRegs_[repSrcReg]) { 937bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\tSrc reg is unallocatable physreg.\n"; 938f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return true; // Not coallescable. 939f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 94020b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng if (DstIsPhys && !allocatableRegs_[repDstReg]) { 941bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\tDst reg is unallocatable physreg.\n"; 942f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return true; // Not coallescable. 943f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 944f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 945f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // If they are not of the same register class, we cannot join them. 946b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng if (differingRegisterClasses(repSrcReg, repDstReg)) { 947bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\tSrc/Dest are different register classes.\n"; 948f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return true; // Not coallescable. 949f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 950f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 951b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng LiveInterval &SrcInt = getInterval(repSrcReg); 95220b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng LiveInterval &DstInt = getInterval(repDstReg); 95320b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng assert(SrcInt.reg == repSrcReg && DstInt.reg == repDstReg && 954f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner "Register mapping is horribly broken!"); 95520b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng 956bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tInspecting "; SrcInt.print(DOUT, mri_); 95720b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng DOUT << " and "; DstInt.print(DOUT, mri_); 958bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << ": "; 959b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 960b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Check if it is necessary to propagate "isDead" property before intervals 961b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // are joined. 962b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg); 963b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng bool isDead = mopd->isDead(); 964edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng bool isShorten = false; 9652c3535d2a6738d154914a59f272fac45e50b706bEvan Cheng unsigned SrcStart = 0, RemoveStart = 0; 9662c3535d2a6738d154914a59f272fac45e50b706bEvan Cheng unsigned SrcEnd = 0, RemoveEnd = 0; 967b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng if (isDead) { 96848ef398ebd2f2b992c81bebd5159de119ce62c80Evan Cheng unsigned CopyIdx = getInstructionIndex(CopyMI); 96948ef398ebd2f2b992c81bebd5159de119ce62c80Evan Cheng LiveInterval::iterator SrcLR = 97048ef398ebd2f2b992c81bebd5159de119ce62c80Evan Cheng SrcInt.FindLiveRangeContaining(getUseIndex(CopyIdx)); 9712c3535d2a6738d154914a59f272fac45e50b706bEvan Cheng RemoveStart = SrcStart = SrcLR->start; 9722c3535d2a6738d154914a59f272fac45e50b706bEvan Cheng RemoveEnd = SrcEnd = SrcLR->end; 97348ef398ebd2f2b992c81bebd5159de119ce62c80Evan Cheng // The instruction which defines the src is only truly dead if there are 97448ef398ebd2f2b992c81bebd5159de119ce62c80Evan Cheng // no intermediate uses and there isn't a use beyond the copy. 97548ef398ebd2f2b992c81bebd5159de119ce62c80Evan Cheng // FIXME: find the last use, mark is kill and shorten the live range. 976d592a28ca1506f2ccd6384679d87cce4b4fd874aEvan Cheng if (SrcEnd > getDefIndex(CopyIdx)) { 977b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng isDead = false; 978d592a28ca1506f2ccd6384679d87cce4b4fd874aEvan Cheng } else { 979edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng MachineOperand *MOU; 9802c3535d2a6738d154914a59f272fac45e50b706bEvan Cheng MachineInstr *LastUse= lastRegisterUse(repSrcReg, SrcStart, CopyIdx, MOU); 981edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng if (LastUse) { 982edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng // Shorten the liveinterval to the end of last use. 983edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng MOU->setIsKill(); 984edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng isDead = false; 985edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng isShorten = true; 9862c3535d2a6738d154914a59f272fac45e50b706bEvan Cheng RemoveStart = getDefIndex(getInstructionIndex(LastUse)); 9872c3535d2a6738d154914a59f272fac45e50b706bEvan Cheng RemoveEnd = SrcEnd; 9882f524575396b740b8bdae076b5711e602e82f834Evan Cheng } else { 9892f524575396b740b8bdae076b5711e602e82f834Evan Cheng MachineInstr *SrcMI = getInstructionFromIndex(SrcStart); 9902f524575396b740b8bdae076b5711e602e82f834Evan Cheng if (SrcMI) { 991bcfd4665b5597ed1ba679584a69080396d68bcf9Evan Cheng MachineOperand *mops = findDefOperand(SrcMI, repSrcReg); 9922f524575396b740b8bdae076b5711e602e82f834Evan Cheng if (mops) 9932f524575396b740b8bdae076b5711e602e82f834Evan Cheng // A dead def should have a single cycle interval. 9942f524575396b740b8bdae076b5711e602e82f834Evan Cheng ++RemoveStart; 9952f524575396b740b8bdae076b5711e602e82f834Evan Cheng } 9962f524575396b740b8bdae076b5711e602e82f834Evan Cheng } 997edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng } 998b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 999b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 1000ba1a3df608a14ca37ca944f4c942c202e919ea80Evan Cheng // We need to be careful about coalescing a source physical register with a 1001ba1a3df608a14ca37ca944f4c942c202e919ea80Evan Cheng // virtual register. Once the coalescing is done, it cannot be broken and 1002ba1a3df608a14ca37ca944f4c942c202e919ea80Evan Cheng // these are not spillable! If the destination interval uses are far away, 1003ba1a3df608a14ca37ca944f4c942c202e919ea80Evan Cheng // think twice about coalescing them! 100420b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng if (!mopd->isDead() && (SrcIsPhys || DstIsPhys)) { 100520b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng LiveInterval &JoinVInt = SrcIsPhys ? DstInt : SrcInt; 100620b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng unsigned JoinVReg = SrcIsPhys ? repDstReg : repSrcReg; 100720b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng unsigned JoinPReg = SrcIsPhys ? repSrcReg : repDstReg; 100820b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(JoinVReg); 100920b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng unsigned Threshold = allocatableRCRegs_[RC].count(); 101020b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng 101120b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng // If the virtual register live interval is long has it has low use desity, 101220b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng // do not join them, instead mark the physical register as its allocation 101320b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng // preference. 101420b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng unsigned Length = JoinVInt.getSize() / InstrSlots::NUM; 101520b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng LiveVariables::VarInfo &vi = lv_->getVarInfo(JoinVReg); 101620b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng if (Length > Threshold && 101720b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng (((float)vi.NumUses / Length) < (1.0 / Threshold))) { 101820b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng JoinVInt.preference = JoinPReg; 1019cf596c54d4089ef23ce00be04bbb674d3ae2e0a6Evan Cheng ++numAborts; 102020b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng DOUT << "\tMay tie down a physical register, abort!\n"; 1021cf596c54d4089ef23ce00be04bbb674d3ae2e0a6Evan Cheng return false; 1022cf596c54d4089ef23ce00be04bbb674d3ae2e0a6Evan Cheng } 1023ba1a3df608a14ca37ca944f4c942c202e919ea80Evan Cheng } 1024ba1a3df608a14ca37ca944f4c942c202e919ea80Evan Cheng 10256d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Okay, attempt to join these two intervals. On failure, this returns false. 10266d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Otherwise, if one of the intervals being joined is a physreg, this method 102720b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng // always canonicalizes DstInt to be it. The output "SrcInt" will not have 10286d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // been modified, so we can use this information below to update aliases. 102920b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng if (JoinIntervals(DstInt, SrcInt)) { 1030b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng if (isDead) { 1031b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Result of the copy is dead. Propagate this property. 1032a16d4429e49b5406c0af905953b5eae13b9cf47cEvan Cheng if (SrcStart == 0) { 1033a16d4429e49b5406c0af905953b5eae13b9cf47cEvan Cheng assert(MRegisterInfo::isPhysicalRegister(repSrcReg) && 1034a16d4429e49b5406c0af905953b5eae13b9cf47cEvan Cheng "Live-in must be a physical register!"); 1035a16d4429e49b5406c0af905953b5eae13b9cf47cEvan Cheng // Live-in to the function but dead. Remove it from entry live-in set. 1036b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // JoinIntervals may end up swapping the two intervals. 1037a16d4429e49b5406c0af905953b5eae13b9cf47cEvan Cheng mf_->begin()->removeLiveIn(repSrcReg); 1038b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } else { 1039b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineInstr *SrcMI = getInstructionFromIndex(SrcStart); 1040b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng if (SrcMI) { 1041bcfd4665b5597ed1ba679584a69080396d68bcf9Evan Cheng MachineOperand *mops = findDefOperand(SrcMI, repSrcReg); 1042b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng if (mops) 1043b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng mops->setIsDead(); 1044b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 1045b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 1046b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 1047edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng 10482c3535d2a6738d154914a59f272fac45e50b706bEvan Cheng if (isShorten || isDead) { 1049edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng // Shorten the live interval. 105020b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng LiveInterval &LiveInInt = (repSrcReg == DstInt.reg) ? DstInt : SrcInt; 10512c3535d2a6738d154914a59f272fac45e50b706bEvan Cheng LiveInInt.removeRange(RemoveStart, RemoveEnd); 1052edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng } 1053b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } else { 10546d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Coallescing failed. 10556d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 10566d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If we can eliminate the copy without merging the live ranges, do so now. 105720b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng if (AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI)) 10586d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner return true; 1059f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 10606d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Otherwise, we are unable to join the intervals. 1061bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "Interference!\n"; 1062f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return false; 1063f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 1064f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 106520b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng bool Swapped = repSrcReg == DstInt.reg; 1066e7f729b42b54fa751ba3524e1c597aad6d3ec3d7Chris Lattner if (Swapped) 1067b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng std::swap(repSrcReg, repDstReg); 1068b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng assert(MRegisterInfo::isVirtualRegister(repSrcReg) && 1069e7f729b42b54fa751ba3524e1c597aad6d3ec3d7Chris Lattner "LiveInterval::join didn't work right!"); 1070e7f729b42b54fa751ba3524e1c597aad6d3ec3d7Chris Lattner 1071c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // If we're about to merge live ranges into a physical register live range, 1072c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // we have to update any aliased register's live ranges to indicate that they 1073c114b2cad7293d98686d380273085f5c32966b52Chris Lattner // have clobbered values for this range. 1074b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng if (MRegisterInfo::isPhysicalRegister(repDstReg)) { 107524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Update the liveintervals of sub-registers. 107624a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng for (const unsigned *AS = mri_->getSubRegisters(repDstReg); *AS; ++AS) 107724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng getInterval(*AS).MergeInClobberRanges(SrcInt); 1078cf596c54d4089ef23ce00be04bbb674d3ae2e0a6Evan Cheng } else { 1079f44c72817e3a7f517ad796705effb8d59e6a6dfaEvan Cheng // Merge use info if the destination is a virtual register. 1080cf596c54d4089ef23ce00be04bbb674d3ae2e0a6Evan Cheng LiveVariables::VarInfo& dVI = lv_->getVarInfo(repDstReg); 1081cf596c54d4089ef23ce00be04bbb674d3ae2e0a6Evan Cheng LiveVariables::VarInfo& sVI = lv_->getVarInfo(repSrcReg); 108220b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng dVI.NumUses += sVI.NumUses; 1083c114b2cad7293d98686d380273085f5c32966b52Chris Lattner } 1084c114b2cad7293d98686d380273085f5c32966b52Chris Lattner 108520b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng DOUT << "\n\t\tJoined. Result = "; DstInt.print(DOUT, mri_); 1086bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\n"; 108730cac02a925c9d56613711b0e77099cb7252bc9bEvan Cheng 108888d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng // Remember these liveintervals have been joined. 108988d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng JoinedLIs.set(repSrcReg - MRegisterInfo::FirstVirtualRegister); 109088d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng if (MRegisterInfo::isVirtualRegister(repDstReg)) 109188d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng JoinedLIs.set(repDstReg - MRegisterInfo::FirstVirtualRegister); 109230cac02a925c9d56613711b0e77099cb7252bc9bEvan Cheng 1093da2295e631ae07788f7db53efa3bea6367e7656cEvan Cheng // If the intervals were swapped by Join, swap them back so that the register 1094da2295e631ae07788f7db53efa3bea6367e7656cEvan Cheng // mapping (in the r2i map) is correct. 109520b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng if (Swapped) SrcInt.swap(DstInt); 1096b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng removeInterval(repSrcReg); 1097b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng r2rMap_[repSrcReg] = repDstReg; 1098e7f729b42b54fa751ba3524e1c597aad6d3ec3d7Chris Lattner 1099bfe180af9eef1cf767f61f501ca325fcce2ae7ceChris Lattner // Finally, delete the copy instruction. 1100bfe180af9eef1cf767f61f501ca325fcce2ae7ceChris Lattner RemoveMachineInstrFromMaps(CopyMI); 1101bfe180af9eef1cf767f61f501ca325fcce2ae7ceChris Lattner CopyMI->eraseFromParent(); 1102bfe180af9eef1cf767f61f501ca325fcce2ae7ceChris Lattner ++numPeep; 1103f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner ++numJoins; 1104f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return true; 1105dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 1106dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 11076d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// ComputeUltimateVN - Assuming we are going to join two live intervals, 11086d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// compute what the resultant value numbers for each value in the input two 11096d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// ranges will be. This is complicated by copies between the two which can 11106d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// and will commonly cause multiple value numbers to be merged into one. 11116d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// 11126d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// VN is the value number that we're trying to resolve. InstDefiningValue 11136d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// keeps track of the new InstDefiningValue assignment for the result 11146d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of 11156d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// whether a value in this or other is a copy from the opposite set. 11166d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have 11176d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// already been assigned. 11186d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// 11196d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// ThisFromOther[x] - If x is defined as a copy from the other interval, this 11206d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// contains the value number the copy is from. 11216d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// 11226d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattnerstatic unsigned ComputeUltimateVN(unsigned VN, 112391725b75852443923b419fd23215194cfc65dd88Chris Lattner SmallVector<std::pair<unsigned, 112491725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned>, 16> &ValueNumberInfo, 11256d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner SmallVector<int, 16> &ThisFromOther, 11266d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner SmallVector<int, 16> &OtherFromThis, 11276d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner SmallVector<int, 16> &ThisValNoAssignments, 11286d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner SmallVector<int, 16> &OtherValNoAssignments, 11296d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner LiveInterval &ThisLI, LiveInterval &OtherLI) { 11306d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If the VN has already been computed, just return it. 11316d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (ThisValNoAssignments[VN] >= 0) 11326d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner return ThisValNoAssignments[VN]; 11338a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner// assert(ThisValNoAssignments[VN] != -2 && "Cyclic case?"); 11346d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 11356d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If this val is not a copy from the other val, then it must be a new value 11366d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // number in the destination. 11376d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner int OtherValNo = ThisFromOther[VN]; 11386d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (OtherValNo == -1) { 113991725b75852443923b419fd23215194cfc65dd88Chris Lattner ValueNumberInfo.push_back(ThisLI.getValNumInfo(VN)); 114091725b75852443923b419fd23215194cfc65dd88Chris Lattner return ThisValNoAssignments[VN] = ValueNumberInfo.size()-1; 11416d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 11426d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 11438a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner // Otherwise, this *is* a copy from the RHS. If the other side has already 11448a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner // been computed, return it. 11458a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner if (OtherValNoAssignments[OtherValNo] >= 0) 11468a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo]; 11478a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner 11488a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner // Mark this value number as currently being computed, then ask what the 11498a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner // ultimate value # of the other value is. 11506d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner ThisValNoAssignments[VN] = -2; 11516d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner unsigned UltimateVN = 115291725b75852443923b419fd23215194cfc65dd88Chris Lattner ComputeUltimateVN(OtherValNo, ValueNumberInfo, 11536d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OtherFromThis, ThisFromOther, 11546d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OtherValNoAssignments, ThisValNoAssignments, 11556d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OtherLI, ThisLI); 11566d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner return ThisValNoAssignments[VN] = UltimateVN; 11576d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner} 11586d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 1159f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattnerstatic bool InVector(unsigned Val, const SmallVector<unsigned, 8> &V) { 1160f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner return std::find(V.begin(), V.end(), Val) != V.end(); 1161f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner} 1162f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 1163f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// SimpleJoin - Attempt to joint the specified interval into this one. The 1164f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// caller of this method must guarantee that the RHS only contains a single 1165f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// value number and that the RHS is not defined by a copy from this 1166f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// interval. This returns false if the intervals are not joinable, or it 1167f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// joins them and returns true. 1168f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattnerbool LiveIntervals::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) { 1169f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner assert(RHS.containsOneValue()); 1170f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 1171f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // Some number (potentially more than one) value numbers in the current 1172f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // interval may be defined as copies from the RHS. Scan the overlapping 1173f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // portions of the LHS and RHS, keeping track of this and looking for 1174f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // overlapping live ranges that are NOT defined as copies. If these exist, we 1175f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // cannot coallesce. 1176f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 1177f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner LiveInterval::iterator LHSIt = LHS.begin(), LHSEnd = LHS.end(); 1178f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner LiveInterval::iterator RHSIt = RHS.begin(), RHSEnd = RHS.end(); 1179f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 1180f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (LHSIt->start < RHSIt->start) { 1181f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner LHSIt = std::upper_bound(LHSIt, LHSEnd, RHSIt->start); 1182f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (LHSIt != LHS.begin()) --LHSIt; 1183f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } else if (RHSIt->start < LHSIt->start) { 1184f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner RHSIt = std::upper_bound(RHSIt, RHSEnd, LHSIt->start); 1185f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (RHSIt != RHS.begin()) --RHSIt; 1186f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } 1187f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 1188f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner SmallVector<unsigned, 8> EliminatedLHSVals; 1189f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 1190f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner while (1) { 1191f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // Determine if these live intervals overlap. 1192f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner bool Overlaps = false; 1193f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (LHSIt->start <= RHSIt->start) 1194f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner Overlaps = LHSIt->end > RHSIt->start; 1195f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner else 1196f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner Overlaps = RHSIt->end > LHSIt->start; 1197f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 1198f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // If the live intervals overlap, there are two interesting cases: if the 1199f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // LHS interval is defined by a copy from the RHS, it's ok and we record 1200f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // that the LHS value # is the same as the RHS. If it's not, then we cannot 1201f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // coallesce these live ranges and we bail out. 1202f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (Overlaps) { 1203f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // If we haven't already recorded that this value # is safe, check it. 1204f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (!InVector(LHSIt->ValId, EliminatedLHSVals)) { 1205f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // Copy from the RHS? 1206f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner unsigned SrcReg = LHS.getSrcRegForValNum(LHSIt->ValId); 1207f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (rep(SrcReg) != RHS.reg) 1208f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner return false; // Nope, bail out. 1209f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 1210f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner EliminatedLHSVals.push_back(LHSIt->ValId); 1211f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } 1212f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 1213f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // We know this entire LHS live range is okay, so skip it now. 1214f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (++LHSIt == LHSEnd) break; 1215f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner continue; 1216f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } 1217f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 1218f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (LHSIt->end < RHSIt->end) { 1219f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (++LHSIt == LHSEnd) break; 1220f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } else { 1221f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // One interesting case to check here. It's possible that we have 1222f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // something like "X3 = Y" which defines a new value number in the LHS, 1223f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // and is the last use of this liverange of the RHS. In this case, we 1224f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // want to notice this copy (so that it gets coallesced away) even though 1225f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // the live ranges don't actually overlap. 1226f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (LHSIt->start == RHSIt->end) { 1227f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (InVector(LHSIt->ValId, EliminatedLHSVals)) { 1228f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // We already know that this value number is going to be merged in 1229f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // if coallescing succeeds. Just skip the liverange. 1230f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (++LHSIt == LHSEnd) break; 1231f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } else { 1232f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // Otherwise, if this is a copy from the RHS, mark it as being merged 1233f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // in. 1234f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (rep(LHS.getSrcRegForValNum(LHSIt->ValId)) == RHS.reg) { 1235f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner EliminatedLHSVals.push_back(LHSIt->ValId); 1236f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 1237f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // We know this entire LHS live range is okay, so skip it now. 1238f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (++LHSIt == LHSEnd) break; 1239f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } 1240f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } 1241f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } 1242f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 1243f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (++RHSIt == RHSEnd) break; 1244f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } 1245f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } 1246f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 1247f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // If we got here, we know that the coallescing will be successful and that 1248f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // the value numbers in EliminatedLHSVals will all be merged together. Since 1249f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // the most common case is that EliminatedLHSVals has a single number, we 1250f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // optimize for it: if there is more than one value, we merge them all into 1251f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // the lowest numbered one, then handle the interval as if we were merging 1252f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // with one value number. 1253f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner unsigned LHSValNo; 1254f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (EliminatedLHSVals.size() > 1) { 1255f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // Loop through all the equal value numbers merging them into the smallest 1256f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // one. 1257f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner unsigned Smallest = EliminatedLHSVals[0]; 1258f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner for (unsigned i = 1, e = EliminatedLHSVals.size(); i != e; ++i) { 1259f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (EliminatedLHSVals[i] < Smallest) { 1260f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // Merge the current notion of the smallest into the smaller one. 1261f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner LHS.MergeValueNumberInto(Smallest, EliminatedLHSVals[i]); 1262f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner Smallest = EliminatedLHSVals[i]; 1263f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } else { 1264f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // Merge into the smallest. 1265f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner LHS.MergeValueNumberInto(EliminatedLHSVals[i], Smallest); 1266f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } 1267f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } 1268f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner LHSValNo = Smallest; 1269f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } else { 1270f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner assert(!EliminatedLHSVals.empty() && "No copies from the RHS?"); 1271f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner LHSValNo = EliminatedLHSVals[0]; 1272f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } 1273f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 1274f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // Okay, now that there is a single LHS value number that we're merging the 1275f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // RHS into, update the value number info for the LHS to indicate that the 1276f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // value number is defined where the RHS value number was. 1277f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner LHS.setValueNumberInfo(LHSValNo, RHS.getValNumInfo(0)); 1278f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 1279f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // Okay, the final step is to loop over the RHS live intervals, adding them to 1280f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // the LHS. 1281f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner LHS.MergeRangesInAsValue(RHS, LHSValNo); 1282f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner LHS.weight += RHS.weight; 128320b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng if (RHS.preference && !LHS.preference) 128420b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng LHS.preference = RHS.preference; 1285f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 1286f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner return true; 1287f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner} 1288f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 12896d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// JoinIntervals - Attempt to join these two intervals. On failure, this 12906d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// returns false. Otherwise, if one of the intervals being joined is a 12916d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// physreg, this method always canonicalizes LHS to be it. The output 12926d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// "RHS" will not have been modified, so we can use this information 12936d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// below to update aliases. 12946d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattnerbool LiveIntervals::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) { 12952ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner // Compute the final value assignment, assuming that the live ranges can be 12962ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner // coallesced. 12976d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner SmallVector<int, 16> LHSValNoAssignments; 12986d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner SmallVector<int, 16> RHSValNoAssignments; 129991725b75852443923b419fd23215194cfc65dd88Chris Lattner SmallVector<std::pair<unsigned,unsigned>, 16> ValueNumberInfo; 130024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 130124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // If a live interval is a physical register, conservatively check if any 130224a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // of its sub-registers is overlapping the live interval of the virtual 130324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // register. If so, do not coalesce. 130424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng if (MRegisterInfo::isPhysicalRegister(LHS.reg) && 130524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng *mri_->getSubRegisters(LHS.reg)) { 130624a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng for (const unsigned* SR = mri_->getSubRegisters(LHS.reg); *SR; ++SR) 130724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng if (hasInterval(*SR) && RHS.overlaps(getInterval(*SR))) { 130824a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng DOUT << "Interfere with sub-register "; 130924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng DEBUG(getInterval(*SR).print(DOUT, mri_)); 131024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng return false; 131124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 131224a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } else if (MRegisterInfo::isPhysicalRegister(RHS.reg) && 131324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng *mri_->getSubRegisters(RHS.reg)) { 131424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng for (const unsigned* SR = mri_->getSubRegisters(RHS.reg); *SR; ++SR) 131524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng if (hasInterval(*SR) && LHS.overlaps(getInterval(*SR))) { 131624a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng DOUT << "Interfere with sub-register "; 131724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng DEBUG(getInterval(*SR).print(DOUT, mri_)); 131824a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng return false; 131924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 132024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 1321238416c99b2a2baea06ac05a5964bbbbf660f3ddChris Lattner 13226d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Compute ultimate value numbers for the LHS and RHS values. 13232ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner if (RHS.containsOneValue()) { 13242ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner // Copies from a liveinterval with a single value are simple to handle and 13252ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner // very common, handle the special case here. This is important, because 13262ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner // often RHS is small and LHS is large (e.g. a physreg). 13272ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner 13282ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner // Find out if the RHS is defined as a copy from some value in the LHS. 13292ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner int RHSValID = -1; 13302ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner std::pair<unsigned,unsigned> RHSValNoInfo; 1331f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner unsigned RHSSrcReg = RHS.getSrcRegForValNum(0); 1332f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if ((RHSSrcReg == 0 || rep(RHSSrcReg) != LHS.reg)) { 1333f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // If RHS is not defined as a copy from the LHS, we can use simpler and 1334f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // faster checks to see if the live ranges are coallescable. This joiner 1335f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // can't swap the LHS/RHS intervals though. 1336f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner if (!MRegisterInfo::isPhysicalRegister(RHS.reg)) { 1337f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner return SimpleJoin(LHS, RHS); 13382ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner } else { 1339f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner RHSValNoInfo = RHS.getValNumInfo(0); 13402ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner } 13412ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner } else { 1342f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // It was defined as a copy from the LHS, find out what value # it is. 1343f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner unsigned ValInst = RHS.getInstForValNum(0); 1344f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner RHSValID = LHS.getLiveRangeContaining(ValInst-1)->ValId; 1345f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner RHSValNoInfo = LHS.getValNumInfo(RHSValID); 13462ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner } 13472ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner 1348f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner LHSValNoAssignments.resize(LHS.getNumValNums(), -1); 1349f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner RHSValNoAssignments.resize(RHS.getNumValNums(), -1); 13502ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner ValueNumberInfo.resize(LHS.getNumValNums()); 13512ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner 13522ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner // Okay, *all* of the values in LHS that are defined as a copy from RHS 13532ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner // should now get updated. 13542ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { 13552ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner if (unsigned LHSSrcReg = LHS.getSrcRegForValNum(VN)) { 13562ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner if (rep(LHSSrcReg) != RHS.reg) { 13572ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner // If this is not a copy from the RHS, its value number will be 13582ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner // unmodified by the coallescing. 13592ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner ValueNumberInfo[VN] = LHS.getValNumInfo(VN); 13602ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner LHSValNoAssignments[VN] = VN; 13612ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner } else if (RHSValID == -1) { 13622ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner // Otherwise, it is a copy from the RHS, and we don't already have a 13632ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner // value# for it. Keep the current value number, but remember it. 13642ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner LHSValNoAssignments[VN] = RHSValID = VN; 13652ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner ValueNumberInfo[VN] = RHSValNoInfo; 13662ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner } else { 13672ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner // Otherwise, use the specified value #. 13682ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner LHSValNoAssignments[VN] = RHSValID; 13692ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner if (VN != (unsigned)RHSValID) 13702ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner ValueNumberInfo[VN].first = ~1U; 13712ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner else 13722ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner ValueNumberInfo[VN] = RHSValNoInfo; 13732ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner } 13742ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner } else { 13752ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner ValueNumberInfo[VN] = LHS.getValNumInfo(VN); 13762ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner LHSValNoAssignments[VN] = VN; 13772ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner } 13782ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner } 13792ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner 13802ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner assert(RHSValID != -1 && "Didn't find value #?"); 13812ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner RHSValNoAssignments[0] = RHSValID; 13822ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner 13832ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner } else { 1384238416c99b2a2baea06ac05a5964bbbbf660f3ddChris Lattner // Loop over the value numbers of the LHS, seeing if any are defined from 1385238416c99b2a2baea06ac05a5964bbbbf660f3ddChris Lattner // the RHS. 13862ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner SmallVector<int, 16> LHSValsDefinedFromRHS; 13872ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner LHSValsDefinedFromRHS.resize(LHS.getNumValNums(), -1); 13882ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { 13892ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner unsigned ValSrcReg = LHS.getSrcRegForValNum(VN); 13902ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner if (ValSrcReg == 0) // Src not defined by a copy? 13912ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner continue; 13922ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner 1393238416c99b2a2baea06ac05a5964bbbbf660f3ddChris Lattner // DstReg is known to be a register in the LHS interval. If the src is 1394238416c99b2a2baea06ac05a5964bbbbf660f3ddChris Lattner // from the RHS interval, we can use its value #. 13952ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner if (rep(ValSrcReg) != RHS.reg) 13962ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner continue; 13972ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner 13982ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner // Figure out the value # from the RHS. 13992ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner unsigned ValInst = LHS.getInstForValNum(VN); 14002ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner LHSValsDefinedFromRHS[VN] = RHS.getLiveRangeContaining(ValInst-1)->ValId; 14012ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner } 14022ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner 1403238416c99b2a2baea06ac05a5964bbbbf660f3ddChris Lattner // Loop over the value numbers of the RHS, seeing if any are defined from 1404238416c99b2a2baea06ac05a5964bbbbf660f3ddChris Lattner // the LHS. 14052ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner SmallVector<int, 16> RHSValsDefinedFromLHS; 14062ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner RHSValsDefinedFromLHS.resize(RHS.getNumValNums(), -1); 14072ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) { 14082ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner unsigned ValSrcReg = RHS.getSrcRegForValNum(VN); 14092ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner if (ValSrcReg == 0) // Src not defined by a copy? 14102ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner continue; 14112ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner 1412238416c99b2a2baea06ac05a5964bbbbf660f3ddChris Lattner // DstReg is known to be a register in the RHS interval. If the src is 1413238416c99b2a2baea06ac05a5964bbbbf660f3ddChris Lattner // from the LHS interval, we can use its value #. 14142ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner if (rep(ValSrcReg) != LHS.reg) 14152ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner continue; 14162ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner 14172ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner // Figure out the value # from the LHS. 14182ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner unsigned ValInst = RHS.getInstForValNum(VN); 14192ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner RHSValsDefinedFromLHS[VN] = LHS.getLiveRangeContaining(ValInst-1)->ValId; 14202ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner } 14212ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner 1422f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner LHSValNoAssignments.resize(LHS.getNumValNums(), -1); 1423f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner RHSValNoAssignments.resize(RHS.getNumValNums(), -1); 1424f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner ValueNumberInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); 1425f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 14262ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { 14278a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner if (LHSValNoAssignments[VN] >= 0 || LHS.getInstForValNum(VN) == ~2U) 14288a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner continue; 14292ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner ComputeUltimateVN(VN, ValueNumberInfo, 14302ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, 14312ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner LHSValNoAssignments, RHSValNoAssignments, LHS, RHS); 14322ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner } 14332ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) { 14348a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner if (RHSValNoAssignments[VN] >= 0 || RHS.getInstForValNum(VN) == ~2U) 14358a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner continue; 14368a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner // If this value number isn't a copy from the LHS, it's a new number. 14378a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner if (RHSValsDefinedFromLHS[VN] == -1) { 14388a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner ValueNumberInfo.push_back(RHS.getValNumInfo(VN)); 14398a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner RHSValNoAssignments[VN] = ValueNumberInfo.size()-1; 14408a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner continue; 14418a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner } 14428a67f6e848244b00dd706a7e01079d1b39c07731Chris Lattner 14432ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner ComputeUltimateVN(VN, ValueNumberInfo, 14442ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, 14452ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner RHSValNoAssignments, LHSValNoAssignments, RHS, LHS); 14462ebfa0c61823c5d7528b1b3235106c30cb8d53f1Chris Lattner } 14476d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 14486d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 14496d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Armed with the mappings of LHS/RHS values to ultimate values, walk the 14506d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // interval lists to see if these intervals are coallescable. 14516d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner LiveInterval::const_iterator I = LHS.begin(); 14526d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner LiveInterval::const_iterator IE = LHS.end(); 14536d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner LiveInterval::const_iterator J = RHS.begin(); 14546d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner LiveInterval::const_iterator JE = RHS.end(); 14556d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 14566d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Skip ahead until the first place of potential sharing. 14576d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (I->start < J->start) { 14586d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner I = std::upper_bound(I, IE, J->start); 14596d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (I != LHS.begin()) --I; 14606d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } else if (J->start < I->start) { 14616d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner J = std::upper_bound(J, JE, I->start); 14626d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (J != RHS.begin()) --J; 14636d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 14646d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 14656d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner while (1) { 14666d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Determine if these two live ranges overlap. 14676d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner bool Overlaps; 14686d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (I->start < J->start) { 14696d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner Overlaps = I->end > J->start; 14706d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } else { 14716d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner Overlaps = J->end > I->start; 14726d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 14736d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 14746d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If so, check value # info to determine if they are really different. 14756d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (Overlaps) { 14766d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If the live range overlap will map to the same value number in the 14776d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // result liverange, we can still coallesce them. If not, we can't. 14786d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (LHSValNoAssignments[I->ValId] != RHSValNoAssignments[J->ValId]) 14796d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner return false; 14806d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 14816d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 14826d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (I->end < J->end) { 14836d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner ++I; 14846d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (I == IE) break; 14856d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } else { 14866d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner ++J; 14876d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (J == JE) break; 14886d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 14896d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 14906d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 14916d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If we get here, we know that we can coallesce the live ranges. Ask the 14926d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // intervals to coallesce themselves now. 14936d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], 149491725b75852443923b419fd23215194cfc65dd88Chris Lattner ValueNumberInfo); 14956d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner return true; 14966d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner} 1497f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 1498f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 1499cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattnernamespace { 1500cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // DepthMBBCompare - Comparison predicate that sort first based on the loop 1501cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // depth of the basic block (the unsigned), and then on the MBB number. 1502cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner struct DepthMBBCompare { 1503cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; 1504cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { 1505cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner if (LHS.first > RHS.first) return true; // Deeper loops first 1506706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos return LHS.first == RHS.first && 15071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LHS.second->getNumber() < RHS.second->getNumber(); 1508cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner } 1509cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner }; 1510cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner} 1511cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner 1512f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 15131acb17cb8392dce33079fe45f383944ec6616757Chris Lattnervoid LiveIntervals::CopyCoallesceInMBB(MachineBasicBlock *MBB, 1514faf05bbaea5893488dac4eee58700912ddfe28ccEvan Cheng std::vector<CopyRec> *TryAgain, bool PhysOnly) { 1515bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 1516f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 1517f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 1518f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner MII != E;) { 1519f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner MachineInstr *Inst = MII++; 1520f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 1521f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // If this isn't a copy, we can't join intervals. 1522f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner unsigned SrcReg, DstReg; 1523f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg)) continue; 1524f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 1525faf05bbaea5893488dac4eee58700912ddfe28ccEvan Cheng if (TryAgain && !JoinCopy(Inst, SrcReg, DstReg, PhysOnly)) 1526faf05bbaea5893488dac4eee58700912ddfe28ccEvan Cheng TryAgain->push_back(getCopyRec(Inst, SrcReg, DstReg)); 1527f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 1528f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner} 1529f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 1530f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 1531cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattnervoid LiveIntervals::joinIntervals() { 1532bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** JOINING INTERVALS ***********\n"; 15331c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner 153488d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng JoinedLIs.resize(getNumIntervals()); 153588d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng JoinedLIs.reset(); 153688d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng 15371acb17cb8392dce33079fe45f383944ec6616757Chris Lattner std::vector<CopyRec> TryAgainList; 1538cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner const LoopInfo &LI = getAnalysis<LoopInfo>(); 1539cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner if (LI.begin() == LI.end()) { 1540cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // If there are no loops in the function, join intervals in function order. 15411c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 15421c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner I != E; ++I) 1543faf05bbaea5893488dac4eee58700912ddfe28ccEvan Cheng CopyCoallesceInMBB(I, &TryAgainList); 1544cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner } else { 1545cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // Otherwise, join intervals in inner loops before other intervals. 1546cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // Unfortunately we can't just iterate over loop hierarchy here because 1547cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // there may be more MBB's than BB's. Collect MBB's for sorting. 154820b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng 154920b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng // Join intervals in the function prolog first. We want to join physical 155020b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng // registers with virtual registers before the intervals got too long. 1551cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; 155220b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); I != E;++I) 1553cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner MBBs.push_back(std::make_pair(LI.getLoopDepth(I->getBasicBlock()), I)); 1554cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner 1555cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner // Sort by loop depth. 1556cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); 1557cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner 1558706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Finally, join intervals in loop nest order. 1559cc0d156f7bca0811aade0a95b0e7419176383c90Chris Lattner for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 1560faf05bbaea5893488dac4eee58700912ddfe28ccEvan Cheng CopyCoallesceInMBB(MBBs[i].second, NULL, true); 156120b0abc24fb3fa15098b7cb12c7762fb0770e133Evan Cheng for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 1562faf05bbaea5893488dac4eee58700912ddfe28ccEvan Cheng CopyCoallesceInMBB(MBBs[i].second, &TryAgainList, false); 15631acb17cb8392dce33079fe45f383944ec6616757Chris Lattner } 15641acb17cb8392dce33079fe45f383944ec6616757Chris Lattner 15651acb17cb8392dce33079fe45f383944ec6616757Chris Lattner // Joining intervals can allow other intervals to be joined. Iteratively join 15661acb17cb8392dce33079fe45f383944ec6616757Chris Lattner // until we make no progress. 15671acb17cb8392dce33079fe45f383944ec6616757Chris Lattner bool ProgressMade = true; 15681acb17cb8392dce33079fe45f383944ec6616757Chris Lattner while (ProgressMade) { 15691acb17cb8392dce33079fe45f383944ec6616757Chris Lattner ProgressMade = false; 15701acb17cb8392dce33079fe45f383944ec6616757Chris Lattner 15711acb17cb8392dce33079fe45f383944ec6616757Chris Lattner for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) { 15721acb17cb8392dce33079fe45f383944ec6616757Chris Lattner CopyRec &TheCopy = TryAgainList[i]; 15731acb17cb8392dce33079fe45f383944ec6616757Chris Lattner if (TheCopy.MI && 15741acb17cb8392dce33079fe45f383944ec6616757Chris Lattner JoinCopy(TheCopy.MI, TheCopy.SrcReg, TheCopy.DstReg)) { 15751acb17cb8392dce33079fe45f383944ec6616757Chris Lattner TheCopy.MI = 0; // Mark this one as done. 15761acb17cb8392dce33079fe45f383944ec6616757Chris Lattner ProgressMade = true; 15771acb17cb8392dce33079fe45f383944ec6616757Chris Lattner } 15781acb17cb8392dce33079fe45f383944ec6616757Chris Lattner } 1579f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 158088d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng 158188d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng // Some live range has been lengthened due to colaescing, eliminate the 158288d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng // unnecessary kills. 158388d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng int RegNum = JoinedLIs.find_first(); 158488d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng while (RegNum != -1) { 158588d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng unsigned Reg = RegNum + MRegisterInfo::FirstVirtualRegister; 158688d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng unsigned repReg = rep(Reg); 158788d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng LiveInterval &LI = getInterval(repReg); 158888d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng LiveVariables::VarInfo& svi = lv_->getVarInfo(Reg); 158988d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng for (unsigned i = 0, e = svi.Kills.size(); i != e; ++i) { 159088d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng MachineInstr *Kill = svi.Kills[i]; 159188d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng // Suppose vr1 = op vr2, x 159288d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng // and vr1 and vr2 are coalesced. vr2 should still be marked kill 159388d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng // unless it is a two-address operand. 159488d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng if (isRemoved(Kill) || hasRegisterDef(Kill, repReg)) 159588d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng continue; 159688d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng if (LI.liveAt(getInstructionIndex(Kill) + InstrSlots::NUM)) 159788d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng unsetRegisterKill(Kill, repReg); 159888d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng } 159988d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng RegNum = JoinedLIs.find_next(RegNum); 160088d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng } 1601f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 1602bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "*** Register mapping ***\n"; 1603bdc679d564e67a81792e463f6614b0088f975025Bill Wendling for (int i = 0, e = r2rMap_.size(); i != e; ++i) 1604bdc679d564e67a81792e463f6614b0088f975025Bill Wendling if (r2rMap_[i]) { 1605bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " reg " << i << " -> "; 1606bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DEBUG(printRegName(r2rMap_[i])); 1607bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\n"; 1608bdc679d564e67a81792e463f6614b0088f975025Bill Wendling } 16091c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner} 16101c5c0444f1326b58cf05015651f36f2b04ca322dChris Lattner 1611647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng/// Return true if the two specified registers belong to different register 1612647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng/// classes. The registers may be either phys or virt regs. 1613647c15e58ed4c3fda81041d401ca7547639958dcEvan Chengbool LiveIntervals::differingRegisterClasses(unsigned RegA, 1614647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng unsigned RegB) const { 16157ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 16167ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // Get the register classes for the first reg. 1617ad3c74fc9b52b652859807580c8e40b67394d689Chris Lattner if (MRegisterInfo::isPhysicalRegister(RegA)) { 1618edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman assert(MRegisterInfo::isVirtualRegister(RegB) && 1619ad3c74fc9b52b652859807580c8e40b67394d689Chris Lattner "Shouldn't consider two physregs!"); 1620647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng return !mf_->getSSARegMap()->getRegClass(RegB)->contains(RegA); 1621ad3c74fc9b52b652859807580c8e40b67394d689Chris Lattner } 16227ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 16237ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner // Compare against the regclass for the second reg. 1624647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng const TargetRegisterClass *RegClass = mf_->getSSARegMap()->getRegClass(RegA); 1625647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng if (MRegisterInfo::isVirtualRegister(RegB)) 1626647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng return RegClass != mf_->getSSARegMap()->getRegClass(RegB); 1627647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng else 1628647c15e58ed4c3fda81041d401ca7547639958dcEvan Cheng return !RegClass->contains(RegB); 16297ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner} 16307ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 1631edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng/// lastRegisterUse - Returns the last use of the specific register between 1632edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng/// cycles Start and End. It also returns the use operand by reference. It 1633edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng/// returns NULL if there are no uses. 1634edeffb37dc41591b3d3943a5c02c04e55d348524Evan ChengMachineInstr * 1635edeffb37dc41591b3d3943a5c02c04e55d348524Evan ChengLiveIntervals::lastRegisterUse(unsigned Reg, unsigned Start, unsigned End, 1636edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng MachineOperand *&MOU) { 1637edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng int e = (End-1) / InstrSlots::NUM * InstrSlots::NUM; 1638edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng int s = Start; 1639edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng while (e >= s) { 1640b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Skip deleted instructions 1641edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng MachineInstr *MI = getInstructionFromIndex(e); 1642edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng while ((e - InstrSlots::NUM) >= s && !MI) { 1643edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng e -= InstrSlots::NUM; 1644edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng MI = getInstructionFromIndex(e); 1645edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng } 1646edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng if (e < s || MI == NULL) 1647edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng return NULL; 1648b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 1649edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) { 1650b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineOperand &MO = MI->getOperand(i); 1651b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng if (MO.isReg() && MO.isUse() && MO.getReg() && 1652edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng mri_->regsOverlap(rep(MO.getReg()), Reg)) { 1653edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng MOU = &MO; 1654edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng return MI; 1655edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng } 1656b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 1657edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng 1658edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng e -= InstrSlots::NUM; 1659b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 1660b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 1661edeffb37dc41591b3d3943a5c02c04e55d348524Evan Cheng return NULL; 1662bcfd4665b5597ed1ba679584a69080396d68bcf9Evan Cheng} 1663bcfd4665b5597ed1ba679584a69080396d68bcf9Evan Cheng 1664bcfd4665b5597ed1ba679584a69080396d68bcf9Evan Cheng 1665bcfd4665b5597ed1ba679584a69080396d68bcf9Evan Cheng/// findDefOperand - Returns the MachineOperand that is a def of the specific 1666bcfd4665b5597ed1ba679584a69080396d68bcf9Evan Cheng/// register. It returns NULL if the def is not found. 1667bcfd4665b5597ed1ba679584a69080396d68bcf9Evan ChengMachineOperand *LiveIntervals::findDefOperand(MachineInstr *MI, unsigned Reg) { 1668bcfd4665b5597ed1ba679584a69080396d68bcf9Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1669bcfd4665b5597ed1ba679584a69080396d68bcf9Evan Cheng MachineOperand &MO = MI->getOperand(i); 1670bcfd4665b5597ed1ba679584a69080396d68bcf9Evan Cheng if (MO.isReg() && MO.isDef() && 1671bcfd4665b5597ed1ba679584a69080396d68bcf9Evan Cheng mri_->regsOverlap(rep(MO.getReg()), Reg)) 1672bcfd4665b5597ed1ba679584a69080396d68bcf9Evan Cheng return &MO; 1673bcfd4665b5597ed1ba679584a69080396d68bcf9Evan Cheng } 1674bcfd4665b5597ed1ba679584a69080396d68bcf9Evan Cheng return NULL; 1675b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 1676b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 167730cac02a925c9d56613711b0e77099cb7252bc9bEvan Cheng/// unsetRegisterKill - Unset IsKill property of all uses of specific register 167830cac02a925c9d56613711b0e77099cb7252bc9bEvan Cheng/// of the specific instruction. 167930cac02a925c9d56613711b0e77099cb7252bc9bEvan Chengvoid LiveIntervals::unsetRegisterKill(MachineInstr *MI, unsigned Reg) { 168030cac02a925c9d56613711b0e77099cb7252bc9bEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 168130cac02a925c9d56613711b0e77099cb7252bc9bEvan Cheng MachineOperand &MO = MI->getOperand(i); 168230cac02a925c9d56613711b0e77099cb7252bc9bEvan Cheng if (MO.isReg() && MO.isUse() && MO.isKill() && MO.getReg() && 168330cac02a925c9d56613711b0e77099cb7252bc9bEvan Cheng mri_->regsOverlap(rep(MO.getReg()), Reg)) 168430cac02a925c9d56613711b0e77099cb7252bc9bEvan Cheng MO.unsetIsKill(); 168530cac02a925c9d56613711b0e77099cb7252bc9bEvan Cheng } 168630cac02a925c9d56613711b0e77099cb7252bc9bEvan Cheng} 168730cac02a925c9d56613711b0e77099cb7252bc9bEvan Cheng 168888d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng/// hasRegisterDef - True if the instruction defines the specific register. 168988d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng/// 169088d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Chengbool LiveIntervals::hasRegisterDef(MachineInstr *MI, unsigned Reg) { 169188d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 169288d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng MachineOperand &MO = MI->getOperand(i); 169388d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng if (MO.isReg() && MO.isDef() && 169488d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng mri_->regsOverlap(rep(MO.getReg()), Reg)) 169588d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng return true; 169688d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng } 169788d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng return false; 169888d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng} 169988d1f587d2205b4275dc4c0319a5f2d4d1e6fd42Evan Cheng 1700a1613db62fec94845aa8306232fb665273615badAlkis EvlogimenosLiveInterval LiveIntervals::createInterval(unsigned reg) { 1701edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman float Weight = MRegisterInfo::isPhysicalRegister(reg) ? 17027902c75331fa8f38fc8380f5573d935c0d149ef5Jim Laskey HUGE_VALF : 0.0F; 1703a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos return LiveInterval(reg, Weight); 17049a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 1705