X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=44ea4da31776f10e9b161a8c678ca86ccf5da75b;hb=264a325a90f7b397b8c9ff954080ffc73c9e2483;hp=7a3b30511620665c3b8f80fc13af9bb55eb7e92a;hpb=03d9609c6154ed91daefb4e4f89b7298c11961f3;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 7a3b3051162..44ea4da3177 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -15,13 +15,13 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "regalloc" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "LiveRangeCalc.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/LiveVariables.h" +#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineRegisterInfo.h" @@ -36,11 +36,14 @@ #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" #include #include #include using namespace llvm; +#define DEBUG_TYPE "regalloc" + char LiveIntervals::ID = 0; char &llvm::LiveIntervalsID = LiveIntervals::ID; INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", @@ -78,7 +81,7 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { } LiveIntervals::LiveIntervals() : MachineFunctionPass(ID), - DomTree(0), LRCalc(0) { + DomTree(nullptr), LRCalc(nullptr) { initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); } @@ -109,8 +112,8 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { MF = &fn; MRI = &MF->getRegInfo(); TM = &fn.getTarget(); - TRI = TM->getRegisterInfo(); - TII = TM->getInstrInfo(); + TRI = TM->getSubtargetImpl()->getRegisterInfo(); + TII = TM->getSubtargetImpl()->getInstrInfo(); AA = &getAnalysis(); Indexes = &getAnalysis(); DomTree = &getAnalysis(); @@ -170,7 +173,8 @@ void LiveIntervals::dumpInstrs() const { #endif LiveInterval* LiveIntervals::createInterval(unsigned reg) { - float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; + float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? + llvm::huge_valf : 0.0F; return new LiveInterval(reg, Weight); } @@ -183,6 +187,7 @@ void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); LRCalc->createDeadDefs(LI); LRCalc->extendToUses(LI); + computeDeadValues(&LI, LI, nullptr, nullptr); } void LiveIntervals::computeVirtRegs() { @@ -324,8 +329,10 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, SmallPtrSet LiveOut; // Visit all instructions reading li->reg. - for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(li->reg); - MachineInstr *UseMI = I.skipInstruction();) { + for (MachineRegisterInfo::reg_instr_iterator + I = MRI->reg_instr_begin(li->reg), E = MRI->reg_instr_end(); + I != E; ) { + MachineInstr *UseMI = &*(I++); if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg)) continue; SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); @@ -407,21 +414,34 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, // Handle dead values. bool CanSeparate = false; + computeDeadValues(li, NewLR, &CanSeparate, dead); + + // Move the trimmed segments back. + li->segments.swap(NewLR.segments); + DEBUG(dbgs() << "Shrunk: " << *li << '\n'); + return CanSeparate; +} + +void LiveIntervals::computeDeadValues(LiveInterval *li, + LiveRange &LR, + bool *CanSeparate, + SmallVectorImpl *dead) { for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); I != E; ++I) { VNInfo *VNI = *I; if (VNI->isUnused()) continue; - LiveRange::iterator LRI = NewLR.FindSegmentContaining(VNI->def); - assert(LRI != NewLR.end() && "Missing segment for PHI"); + LiveRange::iterator LRI = LR.FindSegmentContaining(VNI->def); + assert(LRI != LR.end() && "Missing segment for PHI"); if (LRI->end != VNI->def.getDeadSlot()) continue; if (VNI->isPHIDef()) { // This is a dead PHI. Remove it. VNI->markUnused(); - NewLR.removeSegment(LRI->start, LRI->end); + LR.removeSegment(LRI->start, LRI->end); DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); - CanSeparate = true; + if (CanSeparate) + *CanSeparate = true; } else { // This is a dead def. Make sure the instruction knows. MachineInstr *MI = getInstructionFromIndex(VNI->def); @@ -433,11 +453,6 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, } } } - - // Move the trimmed segments back. - li->segments.swap(NewLR.segments); - DEBUG(dbgs() << "Shrunk: " << *li << '\n'); - return CanSeparate; } void LiveIntervals::extendToIndices(LiveRange &LR, @@ -457,7 +472,7 @@ void LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill, MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill); SlotIndex MBBStart, MBBEnd; - tie(MBBStart, MBBEnd) = Indexes->getMBBRange(KillMBB); + std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(KillMBB); // If VNI isn't live out from KillMBB, the value is trivially pruned. if (LRQ.endPoint() < MBBEnd) { @@ -484,7 +499,7 @@ void LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill, MachineBasicBlock *MBB = *I; // Check if VNI is live in to MBB. - tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB); + std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB); LiveQueryResult LRQ = LI->Query(MBBStart); if (LRQ.valueIn() != VNI) { // This block isn't part of the VNI segment. Prune the search. @@ -568,9 +583,9 @@ void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { break; } if (CancelKill) - MI->clearRegisterKills(Reg, NULL); + MI->clearRegisterKills(Reg, nullptr); else - MI->addRegisterKilled(Reg, NULL); + MI->addRegisterKilled(Reg, nullptr); } } } @@ -586,17 +601,17 @@ LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { SlotIndex Start = LI.beginIndex(); if (Start.isBlock()) - return NULL; + return nullptr; SlotIndex Stop = LI.endIndex(); if (Stop.isBlock()) - return NULL; + return nullptr; // getMBBFromIndex doesn't need to search the MBB table when both indexes // belong to proper instructions. MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start); MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop); - return MBB1 == MBB2 ? MBB1 : NULL; + return MBB1 == MBB2 ? MBB1 : nullptr; } bool @@ -619,9 +634,12 @@ LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const { } float -LiveIntervals::getSpillWeight(bool isDef, bool isUse, BlockFrequency freq) { - const float Scale = 1.0f / BlockFrequency::getEntryFrequency(); - return (isDef + isUse) * (freq.getFrequency() * Scale); +LiveIntervals::getSpillWeight(bool isDef, bool isUse, + const MachineBlockFrequencyInfo *MBFI, + const MachineInstr *MI) { + BlockFrequency Freq = MBFI->getBlockFreq(MI->getParent()); + const float Scale = 1.0f / MBFI->getEntryFreq(); + return (isDef + isUse) * (Freq.getFrequency() * Scale); } LiveRange::Segment @@ -869,8 +887,8 @@ private: // values. The new range should be placed immediately before NewI, move any // intermediate ranges up. assert(NewI != I && "Inconsistent iterators"); - std::copy(llvm::next(I), NewI, I); - *llvm::prior(NewI) + std::copy(std::next(I), NewI, I); + *std::prev(NewI) = LiveRange::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI); } @@ -915,7 +933,7 @@ private: if (I == E || !SlotIndex::isSameInstr(I->start, OldIdx)) { // No def, search for the new kill. // This can never be an early clobber kill since there is no def. - llvm::prior(I)->end = findLastUseBefore(Reg).getRegSlot(); + std::prev(I)->end = findLastUseBefore(Reg).getRegSlot(); return; } } @@ -951,7 +969,7 @@ private: // DefVNI is a dead def. It may have been moved across other values in LR, // so move I up to NewI. Slide [NewI;I) down one position. - std::copy_backward(NewI, I, llvm::next(I)); + std::copy_backward(NewI, I, std::next(I)); *NewI = LiveRange::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI); } @@ -963,11 +981,11 @@ private: "No RegMask at OldIdx."); *RI = NewIdx.getRegSlot(); assert((RI == LIS.RegMaskSlots.begin() || - SlotIndex::isEarlierInstr(*llvm::prior(RI), *RI)) && - "Cannot move regmask instruction above another call"); - assert((llvm::next(RI) == LIS.RegMaskSlots.end() || - SlotIndex::isEarlierInstr(*RI, *llvm::next(RI))) && - "Cannot move regmask instruction below another call"); + SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) && + "Cannot move regmask instruction above another call"); + assert((std::next(RI) == LIS.RegMaskSlots.end() || + SlotIndex::isEarlierInstr(*RI, *std::next(RI))) && + "Cannot move regmask instruction below another call"); } // Return the last use of reg between NewIdx and OldIdx. @@ -975,10 +993,10 @@ private: if (TargetRegisterInfo::isVirtualRegister(Reg)) { SlotIndex LastUse = NewIdx; - for (MachineRegisterInfo::use_nodbg_iterator - UI = MRI.use_nodbg_begin(Reg), - UE = MRI.use_nodbg_end(); - UI != UE; UI.skipInstruction()) { + for (MachineRegisterInfo::use_instr_nodbg_iterator + UI = MRI.use_instr_nodbg_begin(Reg), + UE = MRI.use_instr_nodbg_end(); + UI != UE; ++UI) { const MachineInstr* MI = &*UI; SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI); if (InstSlot > LastUse && InstSlot < OldIdx) @@ -1120,7 +1138,7 @@ LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, if (LII->end.isDead()) { SlotIndex prevStart; if (LII != LI.begin()) - prevStart = llvm::prior(LII)->start; + prevStart = std::prev(LII)->start; // FIXME: This could be more efficient if there was a // removeSegment method that returned an iterator.