LiveIntervalAnalysis.cpp revision dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8
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{ 48f6f91bf6680668990ff3804b14cf05beedc56ec4Alkis Evlogimenos AU.addPreserved<LiveVariables>(); 49ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos AU.addRequired<LiveVariables>(); 50f6f91bf6680668990ff3804b14cf05beedc56ec4Alkis Evlogimenos AU.addPreservedID(PHIEliminationID); 51ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos AU.addRequiredID(PHIEliminationID); 52ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 53ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 54ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 55ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// runOnMachineFunction - Register allocate the whole function 56ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// 57ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 58ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "Machine Function\n"); 59ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mf_ = &fn; 60ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos tm_ = &fn.getTarget(); 61ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mri_ = tm_->getRegisterInfo(); 62ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos lv_ = &getAnalysis<LiveVariables>(); 63ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos allocatableRegisters_.clear(); 64ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mbbi2mbbMap_.clear(); 65ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mi2iMap_.clear(); 66ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos r2iMap_.clear(); 67ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos r2iMap_.clear(); 68ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos intervals_.clear(); 69ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 70ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // mark allocatable registers 71ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos allocatableRegisters_.resize(MRegisterInfo::FirstVirtualRegister); 72ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // Loop over all of the register classes... 73ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MRegisterInfo::regclass_iterator 74ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos rci = mri_->regclass_begin(), rce = mri_->regclass_end(); 75ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos rci != rce; ++rci) { 76ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // Loop over all of the allocatable registers in the function... 77ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (TargetRegisterClass::iterator 78ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos i = (*rci)->allocation_order_begin(*mf_), 79ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos e = (*rci)->allocation_order_end(*mf_); i != e; ++i) { 80ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos allocatableRegisters_[*i] = true; // The reg is allocatable! 81ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 82ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 83ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 84ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // number MachineInstrs 85ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned miIndex = 0; 86ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 87ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mbb != mbbEnd; ++mbb) { 88ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos const std::pair<MachineBasicBlock*, unsigned>& entry = 89ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos lv_->getMachineBasicBlockInfo(&*mbb); 90ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos bool inserted = mbbi2mbbMap_.insert(std::make_pair(entry.second, 91ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos entry.first)).second; 92ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(inserted && "multiple index -> MachineBasicBlock"); 93ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 94ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 95ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mi != miEnd; ++mi) { 96ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos inserted = mi2iMap_.insert(std::make_pair(*mi, miIndex)).second; 97ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 98ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ++miIndex; 99ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 100ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 101ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 102ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos computeIntervals(); 103ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 104ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos return true; 105ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 106ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 107ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::printRegName(unsigned reg) const 108ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 109ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (reg < MRegisterInfo::FirstVirtualRegister) 110ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos std::cerr << mri_->getName(reg); 111ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else 112ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos std::cerr << '%' << reg; 113ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 114ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 115ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 116ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 117ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 118ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 119ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\t\tregister: ";printRegName(reg); std::cerr << '\n'); 120ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 121ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned instrIndex = getInstructionIndex(*mi); 122ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 123ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(reg); 124ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 125dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos Interval* interval = 0; 126ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 127dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos if (r2iit == r2iMap_.end()) { 128ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // add new interval 129ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos intervals_.push_back(Interval(reg)); 130ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // update interval index for this register 131ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos r2iMap_[reg] = intervals_.size() - 1; 132dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos interval = &intervals_.back(); 133dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 134dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos else { 135dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos interval = &intervals_[r2iit->second]; 136dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 137ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 138dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos for (MbbIndex2MbbMap::iterator 139dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 140dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos it != itEnd; ++it) { 141dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned liveBlockIndex = it->first; 142dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos MachineBasicBlock* liveBlock = it->second; 143dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos if (liveBlockIndex < vi.AliveBlocks.size() && 144dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos vi.AliveBlocks[liveBlockIndex]) { 145dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned start = getInstructionIndex(liveBlock->front()); 146dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned end = getInstructionIndex(liveBlock->back()) + 1; 147dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos interval->addRange(start, end); 148ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 149dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 150ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 151dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos bool killedInDefiningBasicBlock = false; 152dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos for (int i = 0, e = vi.Kills.size(); i != e; ++i) { 153dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos MachineBasicBlock* killerBlock = vi.Kills[i].first; 154dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos MachineInstr* killerInstr = vi.Kills[i].second; 155dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos killedInDefiningBasicBlock |= mbb == killerBlock; 156dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned start = (mbb == killerBlock ? 157dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos instrIndex : 158dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos getInstructionIndex(killerBlock->front())); 159dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned end = getInstructionIndex(killerInstr) + 1; 160dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 161ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 162dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos if (!killedInDefiningBasicBlock) { 163dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned end = getInstructionIndex(mbb->back()) + 1; 164dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos interval->addRange(instrIndex, end); 165ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 166ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 167ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 168ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, 169ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 170ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 171ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 172ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\t\tregister: ";printRegName(reg); std::cerr << '\n'); 1734c214d2bf0da92a7973bb7902c0d6d055b1fa991Alkis Evlogimenos if (!lv_->getAllocatablePhysicalRegisters()[reg]) { 1744c214d2bf0da92a7973bb7902c0d6d055b1fa991Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tnon allocatable register: ignoring\n"); 1754c214d2bf0da92a7973bb7902c0d6d055b1fa991Alkis Evlogimenos return; 1764c214d2bf0da92a7973bb7902c0d6d055b1fa991Alkis Evlogimenos } 177ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 178ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned start = getInstructionIndex(*mi); 179ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned end = start; 180ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 181ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineBasicBlock::iterator e = mbb->end(); mi != e; ++mi) { 182ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (LiveVariables::killed_iterator 183ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ki = lv_->dead_begin(*mi), 184ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ke = lv_->dead_end(*mi); 185ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ki != ke; ++ki) { 186ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (reg == ki->second) { 187ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos end = getInstructionIndex(ki->first) + 1; 188ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos goto exit; 189ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 190ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 191ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 192ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (LiveVariables::killed_iterator 193ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ki = lv_->killed_begin(*mi), 194ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ke = lv_->killed_end(*mi); 195ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ki != ke; ++ki) { 196ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (reg == ki->second) { 197ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos end = getInstructionIndex(ki->first) + 1; 198ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos goto exit; 199ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 200ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 201ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 202ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 203ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(start < end && "did not find end of interval?"); 204ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 205ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 206ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (r2iit != r2iMap_.end()) { 207ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned ii = r2iit->second; 208ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Interval& interval = intervals_[ii]; 209ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos interval.addRange(start, end); 210ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 211ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else { 212ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos intervals_.push_back(Interval(reg)); 213ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Interval& interval = intervals_.back(); 214ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // update interval index for this register 215ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos r2iMap_[reg] = intervals_.size() - 1; 216ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos interval.addRange(start, end); 217ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 218ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 219ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 220ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb, 221ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 222ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 223ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 224ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (reg < MRegisterInfo::FirstVirtualRegister) { 225ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (allocatableRegisters_[reg]) { 226ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos handlePhysicalRegisterDef(mbb, mi, reg); 227ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 228ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 229ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else { 230ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos handleVirtualRegisterDef(mbb, mi, reg); 231ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 232ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 233ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 234ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosunsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const 235ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 236ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(mi2iMap_.find(instr) != mi2iMap_.end() && 237ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos "instruction not assigned a number"); 238ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos return mi2iMap_.find(instr)->second; 239ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 240ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 241ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 242ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 243ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// live interval is an interval [i, j] where 1 <= i <= j <= N for 244ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 245ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::computeIntervals() 246ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 247ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "computing live intervals:\n"); 248ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 249ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MbbIndex2MbbMap::iterator 250ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 251ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos it != itEnd; ++it) { 252ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock* mbb = it->second; 253ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "machine basic block: " 254ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos << mbb->getBasicBlock()->getName() << "\n"); 255ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 256ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mi != miEnd; ++mi) { 257ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineInstr* instr = *mi; 258ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos const TargetInstrDescriptor& tid = 259ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos tm_->getInstrInfo().get(instr->getOpcode()); 260ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\tinstruction[" 261ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos << getInstructionIndex(instr) << "]: "; 262ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos instr->print(std::cerr, *tm_);); 263ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 264ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // handle implicit defs 265ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (const unsigned* id = tid.ImplicitDefs; *id; ++id) { 266ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned physReg = *id; 267ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos handlePhysicalRegisterDef(mbb, mi, physReg); 268ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 269ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 270ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // handle explicit defs 271ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (int i = instr->getNumOperands() - 1; i >= 0; --i) { 272ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineOperand& mop = instr->getOperand(i); 273ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 2749435eda6993944e74419d2f586fdd25635293760Alkis Evlogimenos if (!mop.isRegister()) 275ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos continue; 276ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 2774d7af65903cbc858464362e70a6adf499982ec8aAlkis Evlogimenos if (mop.isDef()) { 278ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg = mop.getAllocatedRegNum(); 2799435eda6993944e74419d2f586fdd25635293760Alkis Evlogimenos if (reg < MRegisterInfo::FirstVirtualRegister) 2809435eda6993944e74419d2f586fdd25635293760Alkis Evlogimenos handlePhysicalRegisterDef(mbb, mi, reg); 2819435eda6993944e74419d2f586fdd25635293760Alkis Evlogimenos else 2829435eda6993944e74419d2f586fdd25635293760Alkis Evlogimenos handleVirtualRegisterDef(mbb, mi, reg); 283ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 284ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 285ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 286ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 287ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 28891ceae6d2060367a5212b15b26faa804ea0448a5Alkis Evlogimenos std::sort(intervals_.begin(), intervals_.end(), StartPointComp()); 289ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::copy(intervals_.begin(), intervals_.end(), 290ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos std::ostream_iterator<Interval>(std::cerr, "\n"))); 291ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 292b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 293dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenosvoid LiveIntervals::Interval::addRange(unsigned start, unsigned end) 294dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos{ 295dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tadding range: [" << start <<','<< end << "]\n"); 296dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos //assert(start < end && "invalid range?"); 297dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos Range range = std::make_pair(start, end); 298dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos Ranges::iterator it = 299dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range), 300dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos range); 301dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 302dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tbefore merge forward: " << *this << '\n'); 303dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos mergeRangesForward(it); 304dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tbefore merge backward: " << *this << '\n'); 305dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos mergeRangesBackward(it); 306dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); 307dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 308dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 309dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenosvoid LiveIntervals::Interval::mergeRangesForward(Ranges::iterator it) 310dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos{ 311dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos for (Ranges::iterator next = it + 1; 312dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos next != ranges.end() && it->second >= next->first; ) { 313dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos it->second = std::max(it->second, next->second); 314dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos next = ranges.erase(next); 315dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 316dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 317dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 318dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenosvoid LiveIntervals::Interval::mergeRangesBackward(Ranges::iterator it) 319dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos{ 320dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos for (Ranges::iterator prev = it - 1; 321dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos it != ranges.begin() && it->first <= prev->second; ) { 322dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos it->first = std::min(it->first, prev->first); 323dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos it->second = std::max(it->second, prev->second); 324dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos it = ranges.erase(prev); 325dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos prev = it - 1; 326dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 327dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 328dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 329b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenosstd::ostream& llvm::operator<<(std::ostream& os, 330b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos const LiveIntervals::Interval& li) 331b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos{ 332b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos os << "%reg" << li.reg << " = "; 333b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos for (LiveIntervals::Interval::Ranges::const_iterator 334b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 335b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos os << "[" << i->first << "," << i->second << "]"; 336b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos } 337b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos return os; 338b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos} 339