LiveIntervalAnalysis.cpp revision ff0cbe175df40e0d2b36e59c6fb72f211f1cba4c
1ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos//===-- LiveIntervals.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" 19ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/LiveIntervals.h" 20ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Function.h" 21ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/LiveVariables.h" 22ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 23ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineFunctionPass.h" 24ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineInstr.h" 25ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/Passes.h" 26ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/SSARegMap.h" 27ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/MRegisterInfo.h" 28ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 29ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 30ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetRegInfo.h" 31ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Support/CFG.h" 32ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "Support/Debug.h" 33ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "Support/DepthFirstIterator.h" 34ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "Support/Statistic.h" 35ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include <iostream> 36ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 37ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 38ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 39ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosnamespace { 40ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos RegisterAnalysis<LiveIntervals> X("liveintervals", 41ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos "Live Interval Analysis"); 42ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 43ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Statistic<> numIntervals("liveintervals", "Number of intervals"); 44ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos}; 45ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 46ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const 47ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 48ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos AU.setPreservesAll(); 49ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos AU.addRequired<LiveVariables>(); 50ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos AU.addRequiredID(PHIEliminationID); 51ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 52ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 53ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 54ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// runOnMachineFunction - Register allocate the whole function 55ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// 56ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 57ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "Machine Function\n"); 58ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mf_ = &fn; 59ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos tm_ = &fn.getTarget(); 60ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mri_ = tm_->getRegisterInfo(); 61ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos lv_ = &getAnalysis<LiveVariables>(); 62ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos allocatableRegisters_.clear(); 63ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mbbi2mbbMap_.clear(); 64ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mi2iMap_.clear(); 65ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos r2iMap_.clear(); 66ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos r2iMap_.clear(); 67ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos intervals_.clear(); 68ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 69ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // mark allocatable registers 70ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos allocatableRegisters_.resize(MRegisterInfo::FirstVirtualRegister); 71ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // Loop over all of the register classes... 72ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MRegisterInfo::regclass_iterator 73ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos rci = mri_->regclass_begin(), rce = mri_->regclass_end(); 74ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos rci != rce; ++rci) { 75ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // Loop over all of the allocatable registers in the function... 76ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (TargetRegisterClass::iterator 77ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos i = (*rci)->allocation_order_begin(*mf_), 78ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos e = (*rci)->allocation_order_end(*mf_); i != e; ++i) { 79ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos allocatableRegisters_[*i] = true; // The reg is allocatable! 80ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 81ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 82ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 83ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // number MachineInstrs 84ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned miIndex = 0; 85ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 86ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mbb != mbbEnd; ++mbb) { 87ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos const std::pair<MachineBasicBlock*, unsigned>& entry = 88ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos lv_->getMachineBasicBlockInfo(&*mbb); 89ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos bool inserted = mbbi2mbbMap_.insert(std::make_pair(entry.second, 90ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos entry.first)).second; 91ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(inserted && "multiple index -> MachineBasicBlock"); 92ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 93ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 94ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mi != miEnd; ++mi) { 95ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos inserted = mi2iMap_.insert(std::make_pair(*mi, miIndex)).second; 96ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 97ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ++miIndex; 98ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 99ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 100ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 101ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos computeIntervals(); 102ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 103ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos return true; 104ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 105ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 106ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::printRegName(unsigned reg) const 107ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 108ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (reg < MRegisterInfo::FirstVirtualRegister) 109ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos std::cerr << mri_->getName(reg); 110ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else 111ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos std::cerr << '%' << reg; 112ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 113ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 114ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 115ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 116ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 117ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 118ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\t\tregister: ";printRegName(reg); std::cerr << '\n'); 119ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 120ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned instrIndex = getInstructionIndex(*mi); 121ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 122ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(reg); 123ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 124ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 125ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // handle multiple definition case (machine instructions violating 126ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // ssa after phi-elimination 127ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (r2iit != r2iMap_.end()) { 128ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned ii = r2iit->second; 129ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Interval& interval = intervals_[ii]; 130ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned end = getInstructionIndex(mbb->back()) + 1; 131ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tadding range: [" 132ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos << instrIndex << ',' << end << "]\n"); 133ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos interval.addRange(instrIndex, end); 134ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\t\t\t" << interval << '\n'); 135ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 136ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else { 137ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // add new interval 138ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos intervals_.push_back(Interval(reg)); 139ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Interval& interval = intervals_.back(); 140ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // update interval index for this register 141ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos r2iMap_[reg] = intervals_.size() - 1; 142ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 143ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MbbIndex2MbbMap::iterator 144ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 145ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos it != itEnd; ++it) { 146ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned liveBlockIndex = it->first; 147ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock* liveBlock = it->second; 148ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (liveBlockIndex < vi.AliveBlocks.size() && 149ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos vi.AliveBlocks[liveBlockIndex]) { 150ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned start = getInstructionIndex(liveBlock->front()); 151ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned end = getInstructionIndex(liveBlock->back()) + 1; 152ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tadding range: [" 153ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos << start << ',' << end << "]\n"); 154ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos interval.addRange(start, end); 155ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 156ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 157ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 158ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos bool killedInDefiningBasicBlock = false; 159ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (int i = 0, e = vi.Kills.size(); i != e; ++i) { 160ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock* killerBlock = vi.Kills[i].first; 161ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineInstr* killerInstr = vi.Kills[i].second; 162ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos killedInDefiningBasicBlock |= mbb == killerBlock; 163ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned start = (mbb == killerBlock ? 164ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos instrIndex : 165ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos getInstructionIndex(killerBlock->front())); 166ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned end = getInstructionIndex(killerInstr) + 1; 167ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tadding range: [" 168ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos << start << ',' << end << "]\n"); 169ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos interval.addRange(start, end); 170ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 171ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 172ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (!killedInDefiningBasicBlock) { 173ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned end = getInstructionIndex(mbb->back()) + 1; 174ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos interval.addRange(instrIndex, end); 175ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 176ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 177ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\t\t\t" << interval << '\n'); 178ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 179ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 180ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 181ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, 182ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 183ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 184ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 185ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\t\tregister: ";printRegName(reg); std::cerr << '\n'); 186ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 187ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned start = getInstructionIndex(*mi); 188ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned end = start; 189ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 190ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineBasicBlock::iterator e = mbb->end(); mi != e; ++mi) { 191ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (LiveVariables::killed_iterator 192ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ki = lv_->dead_begin(*mi), 193ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ke = lv_->dead_end(*mi); 194ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ki != ke; ++ki) { 195ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (reg == ki->second) { 196ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos end = getInstructionIndex(ki->first) + 1; 197ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos goto exit; 198ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 199ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 200ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 201ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (LiveVariables::killed_iterator 202ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ki = lv_->killed_begin(*mi), 203ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ke = lv_->killed_end(*mi); 204ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ki != ke; ++ki) { 205ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (reg == ki->second) { 206ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos end = getInstructionIndex(ki->first) + 1; 207ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos goto exit; 208ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 209ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 210ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 211ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 212ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(start < end && "did not find end of interval?"); 213ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 214ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 215ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (r2iit != r2iMap_.end()) { 216ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned ii = r2iit->second; 217ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Interval& interval = intervals_[ii]; 218ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tadding range: [" 219ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos << start << ',' << end << "]\n"); 220ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos interval.addRange(start, end); 221ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\t\t\t" << interval << '\n'); 222ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 223ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else { 224ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos intervals_.push_back(Interval(reg)); 225ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Interval& interval = intervals_.back(); 226ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // update interval index for this register 227ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos r2iMap_[reg] = intervals_.size() - 1; 228ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tadding range: [" 229ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos << start << ',' << end << "]\n"); 230ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos interval.addRange(start, end); 231ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\t\t\t" << interval << '\n'); 232ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 233ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 234ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 235ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb, 236ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 237ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 238ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 239ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (reg < MRegisterInfo::FirstVirtualRegister) { 240ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (allocatableRegisters_[reg]) { 241ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos handlePhysicalRegisterDef(mbb, mi, reg); 242ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 243ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 244ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else { 245ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos handleVirtualRegisterDef(mbb, mi, reg); 246ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 247ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 248ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 249ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosunsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const 250ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 251ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(mi2iMap_.find(instr) != mi2iMap_.end() && 252ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos "instruction not assigned a number"); 253ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos return mi2iMap_.find(instr)->second; 254ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 255ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 256ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 257ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 258ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// live interval is an interval [i, j] where 1 <= i <= j <= N for 259ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 260ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::computeIntervals() 261ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 262ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "computing live intervals:\n"); 263ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 264ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MbbIndex2MbbMap::iterator 265ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 266ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos it != itEnd; ++it) { 267ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock* mbb = it->second; 268ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "machine basic block: " 269ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos << mbb->getBasicBlock()->getName() << "\n"); 270ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 271ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mi != miEnd; ++mi) { 272ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineInstr* instr = *mi; 273ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos const TargetInstrDescriptor& tid = 274ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos tm_->getInstrInfo().get(instr->getOpcode()); 275ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\tinstruction[" 276ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos << getInstructionIndex(instr) << "]: "; 277ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos instr->print(std::cerr, *tm_);); 278ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 279ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // handle implicit defs 280ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (const unsigned* id = tid.ImplicitDefs; *id; ++id) { 281ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned physReg = *id; 282ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos handlePhysicalRegisterDef(mbb, mi, physReg); 283ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 284ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 285ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // handle explicit defs 286ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (int i = instr->getNumOperands() - 1; i >= 0; --i) { 287ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineOperand& mop = instr->getOperand(i); 288ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 289ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (!mop.isVirtualRegister()) 290ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos continue; 291ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 292ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (mop.opIsDefOnly() || mop.opIsDefAndUse()) { 293ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg = mop.getAllocatedRegNum(); 294ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos handleVirtualRegisterDef(mbb, mi, reg); 295ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 296ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 297ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 298ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 299ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 300ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::copy(intervals_.begin(), intervals_.end(), 301ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos std::ostream_iterator<Interval>(std::cerr, "\n"))); 302ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 303