diff options
Diffstat (limited to 'contrib/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp')
-rw-r--r-- | contrib/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp | 209 |
1 files changed, 108 insertions, 101 deletions
diff --git a/contrib/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp b/contrib/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp index 70d3483..471dcea 100644 --- a/contrib/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/contrib/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -1,4 +1,4 @@ -//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// +//===- LiveIntervalAnalysis.cpp - Live Interval Analysis ------------------===// // // The LLVM Compiler Infrastructure // @@ -7,35 +7,52 @@ // //===----------------------------------------------------------------------===// // -// This file implements the LiveInterval analysis pass which is used -// by the Linear Scan Register allocator. This pass linearizes the -// basic blocks of the function in DFS order and computes live intervals for -// each virtual and physical register. +/// \file This file implements the LiveInterval analysis pass which is used +/// by the Linear Scan Register allocator. This pass linearizes the +/// basic blocks of the function in DFS order and computes live intervals for +/// each virtual and physical register. // //===----------------------------------------------------------------------===// #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "LiveRangeCalc.h" -#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/CodeGen/LiveInterval.h" #include "llvm/CodeGen/LiveVariables.h" +#include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" #include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineInstrBundle.h" +#include "llvm/CodeGen/MachineOperand.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/SlotIndexes.h" #include "llvm/CodeGen/VirtRegMap.h" -#include "llvm/IR/Value.h" +#include "llvm/MC/LaneBitmask.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/Pass.h" #include "llvm/Support/BlockFrequency.h" #include "llvm/Support/CommandLine.h" +#include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" -#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetSubtargetInfo.h" #include <algorithm> -#include <cmath> +#include <cassert> +#include <cstdint> +#include <iterator> +#include <tuple> +#include <utility> + using namespace llvm; #define DEBUG_TYPE "regalloc" @@ -59,11 +76,13 @@ static bool EnablePrecomputePhysRegs = false; #endif // NDEBUG namespace llvm { + cl::opt<bool> UseSegmentSetForPhysRegs( "use-segment-set-for-physregs", cl::Hidden, cl::init(true), cl::desc( "Use segment set for the computation of the live ranges of physregs.")); -} + +} // end namespace llvm void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); @@ -78,8 +97,7 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { MachineFunctionPass::getAnalysisUsage(AU); } -LiveIntervals::LiveIntervals() : MachineFunctionPass(ID), - DomTree(nullptr), LRCalc(nullptr) { +LiveIntervals::LiveIntervals() : MachineFunctionPass(ID) { initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); } @@ -96,16 +114,14 @@ void LiveIntervals::releaseMemory() { RegMaskBits.clear(); RegMaskBlocks.clear(); - for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i) - delete RegUnitRanges[i]; + for (LiveRange *LR : RegUnitRanges) + delete LR; RegUnitRanges.clear(); // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. VNInfoAllocator.Reset(); } -/// runOnMachineFunction - calculates LiveIntervals -/// bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { MF = &fn; MRI = &MF->getRegInfo(); @@ -135,14 +151,13 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { return true; } -/// print - Implement the dump method. void LiveIntervals::print(raw_ostream &OS, const Module* ) const { OS << "********** INTERVALS **********\n"; // Dump the regunits. - for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i) - if (LiveRange *LR = RegUnitRanges[i]) - OS << PrintRegUnit(i, TRI) << ' ' << *LR << '\n'; + for (unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; ++Unit) + if (LiveRange *LR = RegUnitRanges[Unit]) + OS << PrintRegUnit(Unit, TRI) << ' ' << *LR << '\n'; // Dump the virtregs. for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { @@ -152,8 +167,8 @@ void LiveIntervals::print(raw_ostream &OS, const Module* ) const { } OS << "RegMasks:"; - for (unsigned i = 0, e = RegMaskSlots.size(); i != e; ++i) - OS << ' ' << RegMaskSlots[i]; + for (SlotIndex Idx : RegMaskSlots) + OS << ' ' << Idx; OS << '\n'; printInstrs(OS); @@ -165,20 +180,17 @@ void LiveIntervals::printInstrs(raw_ostream &OS) const { } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) -void LiveIntervals::dumpInstrs() const { +LLVM_DUMP_METHOD void LiveIntervals::dumpInstrs() const { printInstrs(dbgs()); } #endif LiveInterval* LiveIntervals::createInterval(unsigned reg) { - float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? - llvm::huge_valf : 0.0F; + float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? huge_valf : 0.0F; return new LiveInterval(reg, Weight); } - -/// computeVirtRegInterval - Compute the live interval of a virtual register, -/// based on defs and uses. +/// Compute the live interval of a virtual register, based on defs and uses. void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { assert(LRCalc && "LRCalc not initialized."); assert(LI.empty() && "Should only compute empty intervals."); @@ -200,7 +212,7 @@ void LiveIntervals::computeRegMasks() { RegMaskBlocks.resize(MF->getNumBlockIDs()); // Find all instructions with regmask operands. - for (MachineBasicBlock &MBB : *MF) { + for (const MachineBasicBlock &MBB : *MF) { std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()]; RMB.first = RegMaskSlots.size(); @@ -210,7 +222,7 @@ void LiveIntervals::computeRegMasks() { RegMaskBits.push_back(Mask); } - for (MachineInstr &MI : MBB) { + for (const MachineInstr &MI : MBB) { for (const MachineOperand &MO : MI.operands()) { if (!MO.isRegMask()) continue; @@ -245,9 +257,9 @@ void LiveIntervals::computeRegMasks() { // interference. // -/// computeRegUnitInterval - Compute the live range of a register unit, based -/// on the uses and defs of aliasing registers. The range should be empty, -/// or contain only dead phi-defs from ABI blocks. +/// Compute the live range of a register unit, based on the uses and defs of +/// aliasing registers. The range should be empty, or contain only dead +/// phi-defs from ABI blocks. void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) { assert(LRCalc && "LRCalc not initialized."); LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); @@ -257,22 +269,30 @@ void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) { // may share super-registers. That's OK because createDeadDefs() is // idempotent. It is very rare for a register unit to have multiple roots, so // uniquing super-registers is probably not worthwhile. - for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) { - for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true); - Supers.isValid(); ++Supers) { - if (!MRI->reg_empty(*Supers)) - LRCalc->createDeadDefs(LR, *Supers); + bool IsReserved = true; + for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) { + for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true); + Super.isValid(); ++Super) { + unsigned Reg = *Super; + if (!MRI->reg_empty(Reg)) + LRCalc->createDeadDefs(LR, Reg); + // A register unit is considered reserved if all its roots and all their + // super registers are reserved. + if (!MRI->isReserved(Reg)) + IsReserved = false; } } // Now extend LR to reach all uses. // Ignore uses of reserved registers. We only track defs of those. - for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) { - for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true); - Supers.isValid(); ++Supers) { - unsigned Reg = *Supers; - if (!MRI->isReserved(Reg) && !MRI->reg_empty(Reg)) - LRCalc->extendToUses(LR, Reg); + if (!IsReserved) { + for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) { + for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true); + Super.isValid(); ++Super) { + unsigned Reg = *Super; + if (!MRI->reg_empty(Reg)) + LRCalc->extendToUses(LR, Reg); + } } } @@ -281,11 +301,9 @@ void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) { LR.flushSegmentSet(); } - -/// computeLiveInRegUnits - Precompute the live ranges of any register units -/// that are live-in to an ABI block somewhere. Register values can appear -/// without a corresponding def when entering the entry block or a landing pad. -/// +/// Precompute the live ranges of any register units that are live-in to an ABI +/// block somewhere. Register values can appear without a corresponding def when +/// entering the entry block or a landing pad. void LiveIntervals::computeLiveInRegUnits() { RegUnitRanges.resize(TRI->getNumRegUnits()); DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n"); @@ -294,18 +312,15 @@ void LiveIntervals::computeLiveInRegUnits() { SmallVector<unsigned, 8> NewRanges; // Check all basic blocks for live-ins. - for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); - MFI != MFE; ++MFI) { - const MachineBasicBlock *MBB = &*MFI; - + for (const MachineBasicBlock &MBB : *MF) { // We only care about ABI blocks: Entry + landing pads. - if ((MFI != MF->begin() && !MBB->isEHPad()) || MBB->livein_empty()) + if ((&MBB != &MF->front() && !MBB.isEHPad()) || MBB.livein_empty()) continue; // Create phi-defs at Begin for all live-in registers. - SlotIndex Begin = Indexes->getMBBStartIdx(MBB); - DEBUG(dbgs() << Begin << "\tBB#" << MBB->getNumber()); - for (const auto &LI : MBB->liveins()) { + SlotIndex Begin = Indexes->getMBBStartIdx(&MBB); + DEBUG(dbgs() << Begin << "\tBB#" << MBB.getNumber()); + for (const auto &LI : MBB.liveins()) { for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); ++Units) { unsigned Unit = *Units; LiveRange *LR = RegUnitRanges[Unit]; @@ -324,16 +339,13 @@ void LiveIntervals::computeLiveInRegUnits() { DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n"); // Compute the 'normal' part of the ranges. - for (unsigned i = 0, e = NewRanges.size(); i != e; ++i) { - unsigned Unit = NewRanges[i]; + for (unsigned Unit : NewRanges) computeRegUnitRange(*RegUnitRanges[Unit], Unit); - } } - static void createSegmentsForValues(LiveRange &LR, - iterator_range<LiveInterval::vni_iterator> VNIs) { - for (auto VNI : VNIs) { + iterator_range<LiveInterval::vni_iterator> VNIs) { + for (VNInfo *VNI : VNIs) { if (VNI->isUnused()) continue; SlotIndex Def = VNI->def; @@ -341,7 +353,7 @@ static void createSegmentsForValues(LiveRange &LR, } } -typedef SmallVector<std::pair<SlotIndex, VNInfo*>, 16> ShrinkToUsesWorkList; +using ShrinkToUsesWorkList = SmallVector<std::pair<SlotIndex, VNInfo*>, 16>; static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes, ShrinkToUsesWorkList &WorkList, @@ -349,7 +361,7 @@ static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes, // Keep track of the PHIs that are in use. SmallPtrSet<VNInfo*, 8> UsedPHIs; // Blocks that have already been added to WorkList as live-out. - SmallPtrSet<MachineBasicBlock*, 16> LiveOut; + SmallPtrSet<const MachineBasicBlock*, 16> LiveOut; // Extend intervals to reach all uses in WorkList. while (!WorkList.empty()) { @@ -368,7 +380,7 @@ static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes, !UsedPHIs.insert(VNI).second) continue; // The PHI is live, make sure the predecessors are live-out. - for (auto &Pred : MBB->predecessors()) { + for (const MachineBasicBlock *Pred : MBB->predecessors()) { if (!LiveOut.insert(Pred).second) continue; SlotIndex Stop = Indexes.getMBBEndIdx(Pred); @@ -384,7 +396,7 @@ static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes, LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI)); // Make sure VNI is live-out from the predecessors. - for (auto &Pred : MBB->predecessors()) { + for (const MachineBasicBlock *Pred : MBB->predecessors()) { if (!LiveOut.insert(Pred).second) continue; SlotIndex Stop = Indexes.getMBBEndIdx(Pred); @@ -415,22 +427,20 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, ShrinkToUsesWorkList WorkList; // Visit all instructions reading li->reg. - 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)) + unsigned Reg = li->reg; + for (MachineInstr &UseMI : MRI->reg_instructions(Reg)) { + if (UseMI.isDebugValue() || !UseMI.readsVirtualRegister(Reg)) continue; - SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot(); + SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); LiveQueryResult LRQ = li->Query(Idx); VNInfo *VNI = LRQ.valueIn(); if (!VNI) { // This shouldn't happen: readsVirtualRegister returns true, but there is // no live value. It is likely caused by a target getting <undef> flags // wrong. - DEBUG(dbgs() << Idx << '\t' << *UseMI + DEBUG(dbgs() << Idx << '\t' << UseMI << "Warning: Instr claims to read non-existent value in " - << *li << '\n'); + << *li << '\n'); continue; } // Special case: An early-clobber tied operand reads and writes the @@ -458,7 +468,7 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, bool LiveIntervals::computeDeadValues(LiveInterval &LI, SmallVectorImpl<MachineInstr*> *dead) { bool MayHaveSplitComponents = false; - for (auto VNI : LI.valnos) { + for (VNInfo *VNI : LI.valnos) { if (VNI->isUnused()) continue; SlotIndex Def = VNI->def; @@ -548,7 +558,7 @@ void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) { SR.segments.swap(NewLR.segments); // Remove dead PHI value numbers - for (auto VNI : SR.valnos) { + for (VNInfo *VNI : SR.valnos) { if (VNI->isUnused()) continue; const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def); @@ -571,8 +581,8 @@ void LiveIntervals::extendToIndices(LiveRange &LR, ArrayRef<SlotIndex> Undefs) { assert(LRCalc && "LRCalc not initialized."); LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); - for (unsigned i = 0, e = Indices.size(); i != e; ++i) - LRCalc->extend(LR, Indices[i], /*PhysReg=*/0, Undefs); + for (SlotIndex Idx : Indices) + LRCalc->extend(LR, Idx, /*PhysReg=*/0, Undefs); } void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill, @@ -599,13 +609,11 @@ void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill, // Find all blocks that are reachable from KillMBB without leaving VNI's live // range. It is possible that KillMBB itself is reachable, so start a DFS // from each successor. - typedef df_iterator_default_set<MachineBasicBlock*,9> VisitedTy; + using VisitedTy = df_iterator_default_set<MachineBasicBlock*,9>; VisitedTy Visited; - for (MachineBasicBlock::succ_iterator - SuccI = KillMBB->succ_begin(), SuccE = KillMBB->succ_end(); - SuccI != SuccE; ++SuccI) { + for (MachineBasicBlock *Succ : KillMBB->successors()) { for (df_ext_iterator<MachineBasicBlock*, VisitedTy> - I = df_ext_begin(*SuccI, Visited), E = df_ext_end(*SuccI, Visited); + I = df_ext_begin(Succ, Visited), E = df_ext_end(Succ, Visited); I != E;) { MachineBasicBlock *MBB = *I; @@ -657,9 +665,9 @@ void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { // Find the regunit intervals for the assigned register. They may overlap // the virtual register live range, cancelling any kills. RU.clear(); - for (MCRegUnitIterator Units(VRM->getPhys(Reg), TRI); Units.isValid(); - ++Units) { - const LiveRange &RURange = getRegUnit(*Units); + for (MCRegUnitIterator Unit(VRM->getPhys(Reg), TRI); Unit.isValid(); + ++Unit) { + const LiveRange &RURange = getRegUnit(*Unit); if (RURange.empty()) continue; RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end))); @@ -802,9 +810,8 @@ LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const { // Conservatively return true instead of scanning huge predecessor lists. if (PHIMBB->pred_size() > 100) return true; - for (MachineBasicBlock::const_pred_iterator - PI = PHIMBB->pred_begin(), PE = PHIMBB->pred_end(); PI != PE; ++PI) - if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(*PI))) + for (const MachineBasicBlock *Pred : PHIMBB->predecessors()) + if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(Pred))) return true; } return false; @@ -831,7 +838,6 @@ LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr &startInst) { return S; } - //===----------------------------------------------------------------------===// // Register mask functions //===----------------------------------------------------------------------===// @@ -864,7 +870,7 @@ bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, return false; bool Found = false; - for (;;) { + while (true) { assert(*SlotI >= LiveI->start); // Loop over all slots overlapping this segment. while (*SlotI < LiveI->end) { @@ -895,7 +901,7 @@ bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, // IntervalUpdate class. //===----------------------------------------------------------------------===// -// HMEditor is a toolkit used by handleMove to trim or extend live intervals. +/// Toolkit used by handleMove to trim or extend live intervals. class LiveIntervals::HMEditor { private: LiveIntervals& LIS; @@ -1241,10 +1247,12 @@ private: LiveRange::iterator NewIdxIn = NewIdxOut; assert(NewIdxIn == LR.find(NewIdx.getBaseIndex())); const SlotIndex SplitPos = NewIdxDef; + OldIdxVNI = OldIdxIn->valno; // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut. + OldIdxOut->valno->def = OldIdxIn->start; *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end, - OldIdxIn->valno); + OldIdxOut->valno); // OldIdxIn and OldIdxVNI are now undef and can be overridden. // We Slide [NewIdxIn, OldIdxIn) down one position. // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -| @@ -1514,8 +1522,7 @@ LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, } } - for (unsigned i = 0, e = OrigRegs.size(); i != e; ++i) { - unsigned Reg = OrigRegs[i]; + for (unsigned Reg : OrigRegs) { if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; @@ -1524,16 +1531,16 @@ LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, if (!LI.hasAtLeastOneValue()) continue; - for (LiveInterval::SubRange &S : LI.subranges()) { + for (LiveInterval::SubRange &S : LI.subranges()) repairOldRegInRange(Begin, End, endIdx, S, Reg, S.LaneMask); - } + repairOldRegInRange(Begin, End, endIdx, LI, Reg); } } void LiveIntervals::removePhysRegDefAt(unsigned Reg, SlotIndex Pos) { - for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { - if (LiveRange *LR = getCachedRegUnit(*Units)) + for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) { + if (LiveRange *LR = getCachedRegUnit(*Unit)) if (VNInfo *VNI = LR->getVNInfoAt(Pos)) LR->removeValNo(VNI); } |