diff --git a/llvm/include/llvm/CodeGen/LiveIntervalCalc.h b/llvm/include/llvm/CodeGen/LiveIntervalCalc.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/CodeGen/LiveIntervalCalc.h @@ -0,0 +1,84 @@ +//===- LiveIntervalCalc.h - Calculate live intervals -----------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// The LiveIntervalCalc class is an extension of LiveRangeCalc targeted to the +// computation and modification of the LiveInterval variants of LiveRanges. +// LiveIntervals are meant to track liveness of registers and stack slots and +// LiveIntervalCalc adds to LiveRangeCalc all the machinery requied to +// construct the liveness of virtual registers tracked by a LiveInterval. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIB_CODEGEN_LIVEINTERVALCALC_H +#define LLVM_LIB_CODEGEN_LIVEINTERVALCALC_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/IndexedMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/LiveRangeCalc.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/SlotIndexes.h" +#include "llvm/MC/LaneBitmask.h" +#include + +namespace llvm { + +template class DomTreeNodeBase; +class MachineDominatorTree; +class MachineFunction; +class MachineRegisterInfo; + +using MachineDomTreeNode = DomTreeNodeBase; + +class LiveIntervalCalc : public LiveRangeCalc { + /// Extend the live range of @p LR to reach all uses of Reg. + /// + /// If @p LR is a main range, or if @p LI is null, then all uses must be + /// jointly dominated by the definitions from @p LR. If @p LR is a subrange + /// of the live interval @p LI, corresponding to lane mask @p LaneMask, + /// all uses must be jointly dominated by the definitions from @p LR + /// together with definitions of other lanes where @p LR becomes undefined + /// (via operands). + /// If @p LR is a main range, the @p LaneMask should be set to ~0, i.e. + /// LaneBitmask::getAll(). + void extendToUses(LiveRange &LR, Register Reg, LaneBitmask LaneMask, + LiveInterval *LI = nullptr); + +public: + LiveIntervalCalc() = default; + + /// createDeadDefs - Create a dead def in LI for every def operand of Reg. + /// Each instruction defining Reg gets a new VNInfo with a corresponding + /// minimal live range. + void createDeadDefs(LiveRange &LR, Register Reg); + + /// Extend the live range of @p LR to reach all uses of Reg. + /// + /// All uses must be jointly dominated by existing liveness. PHI-defs are + /// inserted as needed to preserve SSA form. + void extendToUses(LiveRange &LR, MCRegister PhysReg) { + extendToUses(LR, PhysReg, LaneBitmask::getAll()); + } + + /// Calculates liveness for the register specified in live interval @p LI. + /// Creates subregister live ranges as needed if subreg liveness tracking is + /// enabled. + void calculate(LiveInterval &LI, bool TrackSubRegs); + + /// For live interval \p LI with correct SubRanges construct matching + /// information for the main live range. Expects the main live range to not + /// have any segments or value numbers. + void constructMainRangeFromSubranges(LiveInterval &LI); +}; + +} // end namespace llvm + +#endif // LLVM_LIB_CODEGEN_LIVEINTERVALCALC_H diff --git a/llvm/include/llvm/CodeGen/LiveIntervals.h b/llvm/include/llvm/CodeGen/LiveIntervals.h --- a/llvm/include/llvm/CodeGen/LiveIntervals.h +++ b/llvm/include/llvm/CodeGen/LiveIntervals.h @@ -41,7 +41,7 @@ extern cl::opt UseSegmentSetForPhysRegs; class BitVector; -class LiveRangeCalc; +class LiveIntervalCalc; class MachineBlockFrequencyInfo; class MachineDominatorTree; class MachineFunction; @@ -59,7 +59,7 @@ AliasAnalysis *AA; SlotIndexes* Indexes; MachineDominatorTree *DomTree = nullptr; - LiveRangeCalc *LRCalc = nullptr; + LiveIntervalCalc *LICalc = nullptr; /// Special pool allocator for VNInfo's (LiveInterval val#). VNInfo::Allocator VNInfoAllocator; diff --git a/llvm/include/llvm/CodeGen/LiveRangeCalc.h b/llvm/include/llvm/CodeGen/LiveRangeCalc.h --- a/llvm/include/llvm/CodeGen/LiveRangeCalc.h +++ b/llvm/include/llvm/CodeGen/LiveRangeCalc.h @@ -1,4 +1,4 @@ -//===- LiveRangeCalc.h - Calculate live ranges ------------------*- C++ -*-===// +//===- LiveRangeCalc.h - Calculate live ranges -----------------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -6,15 +6,17 @@ // //===----------------------------------------------------------------------===// // -// The LiveRangeCalc class can be used to compute live ranges from scratch. It -// caches information about values in the CFG to speed up repeated operations -// on the same live range. The cache can be shared by non-overlapping live -// ranges. SplitKit uses that when computing the live range of split products. +// The LiveRangeCalc class can be used to implement the computation of +// live ranges from scratch. +// It caches information about values in the CFG to speed up repeated +// operations on the same live range. The cache can be shared by +// non-overlapping live ranges. SplitKit uses that when computing the live +// range of split products. // // A low-level interface is available to clients that know where a variable is // live, but don't know which value it has as every point. LiveRangeCalc will // propagate values down the dominator tree, and even insert PHI-defs where -// needed. SplitKit uses this faster interface when possible. +// needed. SplitKit uses this faster interface when possible. // //===----------------------------------------------------------------------===// @@ -159,18 +161,14 @@ /// the given @p LiveOuts. void updateFromLiveIns(); - /// Extend the live range of @p LR to reach all uses of Reg. - /// - /// If @p LR is a main range, or if @p LI is null, then all uses must be - /// jointly dominated by the definitions from @p LR. If @p LR is a subrange - /// of the live interval @p LI, corresponding to lane mask @p LaneMask, - /// all uses must be jointly dominated by the definitions from @p LR - /// together with definitions of other lanes where @p LR becomes undefined - /// (via operands). - /// If @p LR is a main range, the @p LaneMask should be set to ~0, i.e. - /// LaneBitmask::getAll(). - void extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask, - LiveInterval *LI = nullptr); +protected: + /// Some getters to expose in a read-only way some private fields to + /// subclasses. + const MachineFunction *getMachineFunction() { return MF; } + const MachineRegisterInfo *getRegInfo() const { return MRI; } + SlotIndexes *getIndexes() { return Indexes; } + MachineDominatorTree *getDomTree() { return DomTree; } + VNInfo::Allocator *getVNAlloc() { return Alloc; } /// Reset Map and Seen fields. void resetLiveOutMap(); @@ -210,29 +208,6 @@ void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, ArrayRef Undefs); - /// createDeadDefs - Create a dead def in LI for every def operand of Reg. - /// Each instruction defining Reg gets a new VNInfo with a corresponding - /// minimal live range. - void createDeadDefs(LiveRange &LR, unsigned Reg); - - /// Extend the live range of @p LR to reach all uses of Reg. - /// - /// All uses must be jointly dominated by existing liveness. PHI-defs are - /// inserted as needed to preserve SSA form. - void extendToUses(LiveRange &LR, unsigned PhysReg) { - extendToUses(LR, PhysReg, LaneBitmask::getAll()); - } - - /// Calculates liveness for the register specified in live interval @p LI. - /// Creates subregister live ranges as needed if subreg liveness tracking is - /// enabled. - void calculate(LiveInterval &LI, bool TrackSubRegs); - - /// For live interval \p LI with correct SubRanges construct matching - /// information for the main live range. Expects the main live range to not - /// have any segments or value numbers. - void constructMainRangeFromSubranges(LiveInterval &LI); - //===--------------------------------------------------------------------===// // Low-level interface. //===--------------------------------------------------------------------===// diff --git a/llvm/lib/CodeGen/CMakeLists.txt b/llvm/lib/CodeGen/CMakeLists.txt --- a/llvm/lib/CodeGen/CMakeLists.txt +++ b/llvm/lib/CodeGen/CMakeLists.txt @@ -56,6 +56,7 @@ LiveIntervalUnion.cpp LivePhysRegs.cpp LiveRangeCalc.cpp + LiveIntervalCalc.cpp LiveRangeEdit.cpp LiveRangeShrink.cpp LiveRegMatrix.cpp diff --git a/llvm/lib/CodeGen/InlineSpiller.cpp b/llvm/lib/CodeGen/InlineSpiller.cpp --- a/llvm/lib/CodeGen/InlineSpiller.cpp +++ b/llvm/lib/CodeGen/InlineSpiller.cpp @@ -23,8 +23,8 @@ #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/LiveIntervalCalc.h" #include "llvm/CodeGen/LiveIntervals.h" -#include "llvm/CodeGen/LiveRangeCalc.h" #include "llvm/CodeGen/LiveRangeEdit.h" #include "llvm/CodeGen/LiveStacks.h" #include "llvm/CodeGen/MachineBasicBlock.h" diff --git a/llvm/lib/CodeGen/LiveIntervalCalc.cpp b/llvm/lib/CodeGen/LiveIntervalCalc.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/CodeGen/LiveIntervalCalc.cpp @@ -0,0 +1,206 @@ +//===- LiveIntervalCalc.cpp - Calculate live interval --------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Implementation of the LiveIntervalCalc class. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/LiveIntervalCalc.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineOperand.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/SlotIndexes.h" +#include "llvm/CodeGen/TargetRegisterInfo.h" +#include "llvm/MC/LaneBitmask.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include +#include +#include +#include +#include + +using namespace llvm; + +#define DEBUG_TYPE "regalloc" + +// Reserve an address that indicates a value that is known to be "undef". +static VNInfo UndefVNI(0xbad, SlotIndex()); + +static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc, + LiveRange &LR, const MachineOperand &MO) { + const MachineInstr &MI = *MO.getParent(); + SlotIndex DefIdx = + Indexes.getInstructionIndex(MI).getRegSlot(MO.isEarlyClobber()); + + // Create the def in LR. This may find an existing def. + LR.createDeadDef(DefIdx, Alloc); +} + +void LiveIntervalCalc::calculate(LiveInterval &LI, bool TrackSubRegs) { + const MachineRegisterInfo *MRI = getRegInfo(); + SlotIndexes *Indexes = getIndexes(); + VNInfo::Allocator *Alloc = getVNAlloc(); + + assert(MRI && Indexes && "call reset() first"); + + // Step 1: Create minimal live segments for every definition of Reg. + // Visit all def operands. If the same instruction has multiple defs of Reg, + // createDeadDef() will deduplicate. + const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo(); + unsigned Reg = LI.reg; + for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) { + if (!MO.isDef() && !MO.readsReg()) + continue; + + unsigned SubReg = MO.getSubReg(); + if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) { + LaneBitmask SubMask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg) + : MRI->getMaxLaneMaskForVReg(Reg); + // If this is the first time we see a subregister def, initialize + // subranges by creating a copy of the main range. + if (!LI.hasSubRanges() && !LI.empty()) { + LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg); + LI.createSubRangeFrom(*Alloc, ClassMask, LI); + } + + LI.refineSubRanges( + *Alloc, SubMask, + [&MO, Indexes, Alloc](LiveInterval::SubRange &SR) { + if (MO.isDef()) + createDeadDef(*Indexes, *Alloc, SR, MO); + }, + *Indexes, TRI); + } + + // Create the def in the main liverange. We do not have to do this if + // subranges are tracked as we recreate the main range later in this case. + if (MO.isDef() && !LI.hasSubRanges()) + createDeadDef(*Indexes, *Alloc, LI, MO); + } + + // We may have created empty live ranges for partially undefined uses, we + // can't keep them because we won't find defs in them later. + LI.removeEmptySubRanges(); + + const MachineFunction *MF = getMachineFunction(); + MachineDominatorTree *DomTree = getDomTree(); + // Step 2: Extend live segments to all uses, constructing SSA form as + // necessary. + if (LI.hasSubRanges()) { + for (LiveInterval::SubRange &S : LI.subranges()) { + LiveIntervalCalc SubLIC; + SubLIC.reset(MF, Indexes, DomTree, Alloc); + SubLIC.extendToUses(S, Reg, S.LaneMask, &LI); + } + LI.clear(); + constructMainRangeFromSubranges(LI); + } else { + resetLiveOutMap(); + extendToUses(LI, Reg, LaneBitmask::getAll()); + } +} + +void LiveIntervalCalc::constructMainRangeFromSubranges(LiveInterval &LI) { + // First create dead defs at all defs found in subranges. + LiveRange &MainRange = LI; + assert(MainRange.segments.empty() && MainRange.valnos.empty() && + "Expect empty main liverange"); + + VNInfo::Allocator *Alloc = getVNAlloc(); + for (const LiveInterval::SubRange &SR : LI.subranges()) { + for (const VNInfo *VNI : SR.valnos) { + if (!VNI->isUnused() && !VNI->isPHIDef()) + MainRange.createDeadDef(VNI->def, *Alloc); + } + } + resetLiveOutMap(); + extendToUses(MainRange, LI.reg, LaneBitmask::getAll(), &LI); +} + +void LiveIntervalCalc::createDeadDefs(LiveRange &LR, Register Reg) { + const MachineRegisterInfo *MRI = getRegInfo(); + SlotIndexes *Indexes = getIndexes(); + VNInfo::Allocator *Alloc = getVNAlloc(); + assert(MRI && Indexes && "call reset() first"); + + // Visit all def operands. If the same instruction has multiple defs of Reg, + // LR.createDeadDef() will deduplicate. + for (MachineOperand &MO : MRI->def_operands(Reg)) + createDeadDef(*Indexes, *Alloc, LR, MO); +} + +void LiveIntervalCalc::extendToUses(LiveRange &LR, Register Reg, + LaneBitmask Mask, LiveInterval *LI) { + const MachineRegisterInfo *MRI = getRegInfo(); + SlotIndexes *Indexes = getIndexes(); + SmallVector Undefs; + if (LI != nullptr) + LI->computeSubRangeUndefs(Undefs, Mask, *MRI, *Indexes); + + // Visit all operands that read Reg. This may include partial defs. + bool IsSubRange = !Mask.all(); + const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo(); + for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) { + // Clear all kill flags. They will be reinserted after register allocation + // by LiveIntervals::addKillFlags(). + if (MO.isUse()) + MO.setIsKill(false); + // MO::readsReg returns "true" for subregister defs. This is for keeping + // liveness of the entire register (i.e. for the main range of the live + // interval). For subranges, definitions of non-overlapping subregisters + // do not count as uses. + if (!MO.readsReg() || (IsSubRange && MO.isDef())) + continue; + + unsigned SubReg = MO.getSubReg(); + if (SubReg != 0) { + LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg); + if (MO.isDef()) + SLM = ~SLM; + // Ignore uses not reading the current (sub)range. + if ((SLM & Mask).none()) + continue; + } + + // Determine the actual place of the use. + const MachineInstr *MI = MO.getParent(); + unsigned OpNo = (&MO - &MI->getOperand(0)); + SlotIndex UseIdx; + if (MI->isPHI()) { + assert(!MO.isDef() && "Cannot handle PHI def of partial register."); + // The actual place where a phi operand is used is the end of the pred + // MBB. PHI operands are paired: (Reg, PredMBB). + UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo + 1).getMBB()); + } else { + // Check for early-clobber redefs. + bool isEarlyClobber = false; + unsigned DefIdx; + if (MO.isDef()) + isEarlyClobber = MO.isEarlyClobber(); + else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) { + // FIXME: This would be a lot easier if tied early-clobber uses also + // had an early-clobber flag. + isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber(); + } + UseIdx = Indexes->getInstructionIndex(*MI).getRegSlot(isEarlyClobber); + } + + // MI is reading Reg. We may have visited MI before if it happens to be + // reading Reg multiple times. That is OK, extend() is idempotent. + extend(LR, UseIdx, Reg, Undefs); + } +} \ No newline at end of file diff --git a/llvm/lib/CodeGen/LiveIntervals.cpp b/llvm/lib/CodeGen/LiveIntervals.cpp --- a/llvm/lib/CodeGen/LiveIntervals.cpp +++ b/llvm/lib/CodeGen/LiveIntervals.cpp @@ -21,7 +21,7 @@ #include "llvm/ADT/iterator_range.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/LiveInterval.h" -#include "llvm/CodeGen/LiveRangeCalc.h" +#include "llvm/CodeGen/LiveIntervalCalc.h" #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" @@ -101,9 +101,7 @@ initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); } -LiveIntervals::~LiveIntervals() { - delete LRCalc; -} +LiveIntervals::~LiveIntervals() { delete LICalc; } void LiveIntervals::releaseMemory() { // Free the live intervals themselves. @@ -131,8 +129,8 @@ Indexes = &getAnalysis(); DomTree = &getAnalysis(); - if (!LRCalc) - LRCalc = new LiveRangeCalc(); + if (!LICalc) + LICalc = new LiveIntervalCalc(); // Allocate space for all virtual registers. VirtRegIntervals.resize(MRI->getNumVirtRegs()); @@ -192,10 +190,10 @@ /// Compute the live interval of a virtual register, based on defs and uses. bool LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { - assert(LRCalc && "LRCalc not initialized."); + assert(LICalc && "LICalc not initialized."); assert(LI.empty() && "Should only compute empty intervals."); - LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); - LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg)); + LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); + LICalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg)); return computeDeadValues(LI, nullptr); } @@ -266,8 +264,8 @@ /// 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()); + assert(LICalc && "LICalc not initialized."); + LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); // The physregs aliasing Unit are the roots and their super-registers. // Create all values as dead defs before extending to uses. Note that roots @@ -281,7 +279,7 @@ Super.isValid(); ++Super) { unsigned Reg = *Super; if (!MRI->reg_empty(Reg)) - LRCalc->createDeadDefs(LR, Reg); + LICalc->createDeadDefs(LR, Reg); // A register unit is considered reserved if all its roots and all their // super registers are reserved. if (!MRI->isReserved(Reg)) @@ -300,7 +298,7 @@ Super.isValid(); ++Super) { unsigned Reg = *Super; if (!MRI->reg_empty(Reg)) - LRCalc->extendToUses(LR, Reg); + LICalc->extendToUses(LR, Reg); } } } @@ -623,10 +621,10 @@ void LiveIntervals::extendToIndices(LiveRange &LR, ArrayRef Indices, ArrayRef Undefs) { - assert(LRCalc && "LRCalc not initialized."); - LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); + assert(LICalc && "LICalc not initialized."); + LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); for (SlotIndex Idx : Indices) - LRCalc->extend(LR, Idx, /*PhysReg=*/0, Undefs); + LICalc->extend(LR, Idx, /*PhysReg=*/0, Undefs); } void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill, @@ -1678,7 +1676,7 @@ } void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) { - assert(LRCalc && "LRCalc not initialized."); - LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); - LRCalc->constructMainRangeFromSubranges(LI); + assert(LICalc && "LICalc not initialized."); + LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); + LICalc->constructMainRangeFromSubranges(LI); } diff --git a/llvm/lib/CodeGen/LiveRangeCalc.cpp b/llvm/lib/CodeGen/LiveRangeCalc.cpp --- a/llvm/lib/CodeGen/LiveRangeCalc.cpp +++ b/llvm/lib/CodeGen/LiveRangeCalc.cpp @@ -1,4 +1,4 @@ -//===- LiveRangeCalc.cpp - Calculate live ranges --------------------------===// +//===- LiveRangeCalc.cpp - Calculate live ranges -------------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -61,158 +61,6 @@ LiveIn.clear(); } -static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc, - LiveRange &LR, const MachineOperand &MO) { - const MachineInstr &MI = *MO.getParent(); - SlotIndex DefIdx = - Indexes.getInstructionIndex(MI).getRegSlot(MO.isEarlyClobber()); - - // Create the def in LR. This may find an existing def. - LR.createDeadDef(DefIdx, Alloc); -} - -void LiveRangeCalc::calculate(LiveInterval &LI, bool TrackSubRegs) { - assert(MRI && Indexes && "call reset() first"); - - // Step 1: Create minimal live segments for every definition of Reg. - // Visit all def operands. If the same instruction has multiple defs of Reg, - // createDeadDef() will deduplicate. - const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo(); - unsigned Reg = LI.reg; - for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) { - if (!MO.isDef() && !MO.readsReg()) - continue; - - unsigned SubReg = MO.getSubReg(); - if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) { - LaneBitmask SubMask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg) - : MRI->getMaxLaneMaskForVReg(Reg); - // If this is the first time we see a subregister def, initialize - // subranges by creating a copy of the main range. - if (!LI.hasSubRanges() && !LI.empty()) { - LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg); - LI.createSubRangeFrom(*Alloc, ClassMask, LI); - } - - LI.refineSubRanges(*Alloc, SubMask, - [&MO, this](LiveInterval::SubRange &SR) { - if (MO.isDef()) - createDeadDef(*Indexes, *Alloc, SR, MO); - }, - *Indexes, TRI); - } - - // Create the def in the main liverange. We do not have to do this if - // subranges are tracked as we recreate the main range later in this case. - if (MO.isDef() && !LI.hasSubRanges()) - createDeadDef(*Indexes, *Alloc, LI, MO); - } - - // We may have created empty live ranges for partially undefined uses, we - // can't keep them because we won't find defs in them later. - LI.removeEmptySubRanges(); - - // Step 2: Extend live segments to all uses, constructing SSA form as - // necessary. - if (LI.hasSubRanges()) { - for (LiveInterval::SubRange &S : LI.subranges()) { - LiveRangeCalc SubLRC; - SubLRC.reset(MF, Indexes, DomTree, Alloc); - SubLRC.extendToUses(S, Reg, S.LaneMask, &LI); - } - LI.clear(); - constructMainRangeFromSubranges(LI); - } else { - resetLiveOutMap(); - extendToUses(LI, Reg, LaneBitmask::getAll()); - } -} - -void LiveRangeCalc::constructMainRangeFromSubranges(LiveInterval &LI) { - // First create dead defs at all defs found in subranges. - LiveRange &MainRange = LI; - assert(MainRange.segments.empty() && MainRange.valnos.empty() && - "Expect empty main liverange"); - - for (const LiveInterval::SubRange &SR : LI.subranges()) { - for (const VNInfo *VNI : SR.valnos) { - if (!VNI->isUnused() && !VNI->isPHIDef()) - MainRange.createDeadDef(VNI->def, *Alloc); - } - } - resetLiveOutMap(); - extendToUses(MainRange, LI.reg, LaneBitmask::getAll(), &LI); -} - -void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) { - assert(MRI && Indexes && "call reset() first"); - - // Visit all def operands. If the same instruction has multiple defs of Reg, - // LR.createDeadDef() will deduplicate. - for (MachineOperand &MO : MRI->def_operands(Reg)) - createDeadDef(*Indexes, *Alloc, LR, MO); -} - -void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask Mask, - LiveInterval *LI) { - SmallVector Undefs; - if (LI != nullptr) - LI->computeSubRangeUndefs(Undefs, Mask, *MRI, *Indexes); - - // Visit all operands that read Reg. This may include partial defs. - bool IsSubRange = !Mask.all(); - const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo(); - for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) { - // Clear all kill flags. They will be reinserted after register allocation - // by LiveIntervals::addKillFlags(). - if (MO.isUse()) - MO.setIsKill(false); - // MO::readsReg returns "true" for subregister defs. This is for keeping - // liveness of the entire register (i.e. for the main range of the live - // interval). For subranges, definitions of non-overlapping subregisters - // do not count as uses. - if (!MO.readsReg() || (IsSubRange && MO.isDef())) - continue; - - unsigned SubReg = MO.getSubReg(); - if (SubReg != 0) { - LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg); - if (MO.isDef()) - SLM = ~SLM; - // Ignore uses not reading the current (sub)range. - if ((SLM & Mask).none()) - continue; - } - - // Determine the actual place of the use. - const MachineInstr *MI = MO.getParent(); - unsigned OpNo = (&MO - &MI->getOperand(0)); - SlotIndex UseIdx; - if (MI->isPHI()) { - assert(!MO.isDef() && "Cannot handle PHI def of partial register."); - // The actual place where a phi operand is used is the end of the pred - // MBB. PHI operands are paired: (Reg, PredMBB). - UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo+1).getMBB()); - } else { - // Check for early-clobber redefs. - bool isEarlyClobber = false; - unsigned DefIdx; - if (MO.isDef()) - isEarlyClobber = MO.isEarlyClobber(); - else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) { - // FIXME: This would be a lot easier if tied early-clobber uses also - // had an early-clobber flag. - isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber(); - } - UseIdx = Indexes->getInstructionIndex(*MI).getRegSlot(isEarlyClobber); - } - - // MI is reading Reg. We may have visited MI before if it happens to be - // reading Reg multiple times. That is OK, extend() is idempotent. - extend(LR, UseIdx, Reg, Undefs); - } -} - void LiveRangeCalc::updateFromLiveIns() { LiveRangeUpdater Updater; for (const LiveInBlock &I : LiveIn) { diff --git a/llvm/lib/CodeGen/MachineVerifier.cpp b/llvm/lib/CodeGen/MachineVerifier.cpp --- a/llvm/lib/CodeGen/MachineVerifier.cpp +++ b/llvm/lib/CodeGen/MachineVerifier.cpp @@ -34,8 +34,8 @@ #include "llvm/Analysis/EHPersonalities.h" #include "llvm/CodeGen/GlobalISel/RegisterBank.h" #include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/LiveIntervalCalc.h" #include "llvm/CodeGen/LiveIntervals.h" -#include "llvm/CodeGen/LiveRangeCalc.h" #include "llvm/CodeGen/LiveStacks.h" #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/MachineBasicBlock.h" diff --git a/llvm/lib/CodeGen/SplitKit.h b/llvm/lib/CodeGen/SplitKit.h --- a/llvm/lib/CodeGen/SplitKit.h +++ b/llvm/lib/CodeGen/SplitKit.h @@ -23,8 +23,8 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/LiveIntervalCalc.h" #include "llvm/CodeGen/LiveIntervals.h" -#include "llvm/CodeGen/LiveRangeCalc.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/SlotIndexes.h" @@ -327,21 +327,21 @@ /// its def. The full live range can be inferred exactly from the range /// of RegIdx in RegAssign. /// 3. (Null, true). As above, but the ranges in RegAssign are too large, and - /// the live range must be recomputed using LiveRangeCalc::extend(). + /// the live range must be recomputed using ::extend(). /// 4. (VNI, false) The value is mapped to a single new value. /// The new value has no live ranges anywhere. ValueMap Values; - /// LRCalc - Cache for computing live ranges and SSA update. Each instance + /// LICalc - Cache for computing live ranges and SSA update. Each instance /// can only handle non-overlapping live ranges, so use a separate - /// LiveRangeCalc instance for the complement interval when in spill mode. - LiveRangeCalc LRCalc[2]; + /// LiveIntervalCalc instance for the complement interval when in spill mode. + LiveIntervalCalc LICalc[2]; - /// getLRCalc - Return the LRCalc to use for RegIdx. In spill mode, the + /// getLICalc - Return the LICalc to use for RegIdx. In spill mode, the /// complement interval can overlap the other intervals, so it gets its own - /// LRCalc instance. When not in spill mode, all intervals can share one. - LiveRangeCalc &getLRCalc(unsigned RegIdx) { - return LRCalc[SpillMode != SM_Partition && RegIdx != 0]; + /// LICalc instance. When not in spill mode, all intervals can share one. + LiveIntervalCalc &getLICalc(unsigned RegIdx) { + return LICalc[SpillMode != SM_Partition && RegIdx != 0]; } /// Find a subrange corresponding to the lane mask @p LM in the live @@ -414,7 +414,7 @@ /// all predecessor values that reach this def. If @p LR is a subrange, /// the array @p Undefs is the set of all locations where it is undefined /// via in other subranges for the same register. - void extendPHIRange(MachineBasicBlock &B, LiveRangeCalc &LRC, + void extendPHIRange(MachineBasicBlock &B, LiveIntervalCalc &LIC, LiveRange &LR, LaneBitmask LM, ArrayRef Undefs); diff --git a/llvm/lib/CodeGen/SplitKit.cpp b/llvm/lib/CodeGen/SplitKit.cpp --- a/llvm/lib/CodeGen/SplitKit.cpp +++ b/llvm/lib/CodeGen/SplitKit.cpp @@ -20,8 +20,8 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/LiveIntervalCalc.h" #include "llvm/CodeGen/LiveIntervals.h" -#include "llvm/CodeGen/LiveRangeCalc.h" #include "llvm/CodeGen/LiveRangeEdit.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" @@ -379,11 +379,11 @@ RegAssign.clear(); Values.clear(); - // Reset the LiveRangeCalc instances needed for this spill mode. - LRCalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, + // Reset the LiveIntervalCalc instances needed for this spill mode. + LICalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator()); if (SpillMode) - LRCalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, + LICalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator()); // We don't need an AliasAnalysis since we will only be performing @@ -832,7 +832,7 @@ assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && "Range cannot span basic blocks"); - // The complement interval will be extended as needed by LRCalc.extend(). + // The complement interval will be extended as needed by LICalc.extend(). if (ParentVNI) forceRecompute(0, *ParentVNI); LLVM_DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); @@ -1118,7 +1118,7 @@ } /// transferValues - Transfer all possible values to the new live ranges. -/// Values that were rematerialized are left alone, they need LRCalc.extend(). +/// Values that were rematerialized are left alone, they need LICalc.extend(). bool SplitEditor::transferValues() { bool Skipped = false; RegAssignMap::const_iterator AssignI = RegAssign.begin(); @@ -1166,7 +1166,7 @@ continue; } - LiveRangeCalc &LRC = getLRCalc(RegIdx); + LiveIntervalCalc &LIC = getLICalc(RegIdx); // This value has multiple defs in RegIdx, but it wasn't rematerialized, // so the live range is accurate. Add live-in blocks in [Start;End) to the @@ -1182,7 +1182,7 @@ LLVM_DEBUG(dbgs() << ':' << VNI->id << "*" << printMBBReference(*MBB)); // MBB has its own def. Is it also live-out? if (BlockEnd <= End) - LRC.setLiveOutValue(&*MBB, VNI); + LIC.setLiveOutValue(&*MBB, VNI); // Skip to the next block for live-in. ++MBB; @@ -1200,16 +1200,16 @@ VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End)); assert(VNI && "Missing def for complex mapped parent PHI"); if (End >= BlockEnd) - LRC.setLiveOutValue(&*MBB, VNI); // Live-out as well. + LIC.setLiveOutValue(&*MBB, VNI); // Live-out as well. } else { // This block needs a live-in value. The last block covered may not // be live-out. if (End < BlockEnd) - LRC.addLiveInBlock(LI, MDT[&*MBB], End); + LIC.addLiveInBlock(LI, MDT[&*MBB], End); else { // Live-through, and we don't know the value. - LRC.addLiveInBlock(LI, MDT[&*MBB]); - LRC.setLiveOutValue(&*MBB, nullptr); + LIC.addLiveInBlock(LI, MDT[&*MBB]); + LIC.setLiveOutValue(&*MBB, nullptr); } } BlockStart = BlockEnd; @@ -1220,9 +1220,9 @@ LLVM_DEBUG(dbgs() << '\n'); } - LRCalc[0].calculateValues(); + LICalc[0].calculateValues(); if (SpillMode) - LRCalc[1].calculateValues(); + LICalc[1].calculateValues(); return Skipped; } @@ -1238,7 +1238,7 @@ return true; } -void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveRangeCalc &LRC, +void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveIntervalCalc &LIC, LiveRange &LR, LaneBitmask LM, ArrayRef Undefs) { for (MachineBasicBlock *P : B.predecessors()) { @@ -1252,7 +1252,7 @@ LiveRange &PSR = !LM.all() ? getSubRangeForMask(LM, PLI) : static_cast(PLI); if (PSR.liveAt(LastUse)) - LRC.extend(LR, End, /*PhysReg=*/0, Undefs); + LIC.extend(LR, End, /*PhysReg=*/0, Undefs); } } @@ -1270,14 +1270,14 @@ unsigned RegIdx = RegAssign.lookup(V->def); LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); - LiveRangeCalc &LRC = getLRCalc(RegIdx); + LiveIntervalCalc &LIC = getLICalc(RegIdx); MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def); if (!removeDeadSegment(V->def, LI)) - extendPHIRange(B, LRC, LI, LaneBitmask::getAll(), /*Undefs=*/{}); + extendPHIRange(B, LIC, LI, LaneBitmask::getAll(), /*Undefs=*/{}); } SmallVector Undefs; - LiveRangeCalc SubLRC; + LiveIntervalCalc SubLIC; for (LiveInterval::SubRange &PS : ParentLI.subranges()) { for (const VNInfo *V : PS.valnos) { @@ -1290,11 +1290,11 @@ continue; MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def); - SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, + SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator()); Undefs.clear(); LI.computeSubRangeUndefs(Undefs, PS.LaneMask, MRI, *LIS.getSlotIndexes()); - extendPHIRange(B, SubLRC, S, PS.LaneMask, Undefs); + extendPHIRange(B, SubLIC, S, PS.LaneMask, Undefs); } } } @@ -1363,8 +1363,8 @@ if (MO.isUse()) ExtPoints.push_back(ExtPoint(MO, RegIdx, Next)); } else { - LiveRangeCalc &LRC = getLRCalc(RegIdx); - LRC.extend(LI, Next, 0, ArrayRef()); + LiveIntervalCalc &LIC = getLICalc(RegIdx); + LIC.extend(LI, Next, 0, ArrayRef()); } } @@ -1372,7 +1372,7 @@ LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx)); assert(LI.hasSubRanges()); - LiveRangeCalc SubLRC; + LiveIntervalCalc SubLIC; Register Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg(); LaneBitmask LM = Sub != 0 ? TRI.getSubRegIndexLaneMask(Sub) : MRI.getMaxLaneMaskForVReg(Reg); @@ -1386,11 +1386,11 @@ // %1 = COPY %0 if (S.empty()) continue; - SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, + SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator()); SmallVector Undefs; LI.computeSubRangeUndefs(Undefs, S.LaneMask, MRI, *LIS.getSlotIndexes()); - SubLRC.extend(S, EP.Next, 0, Undefs); + SubLIC.extend(S, EP.Next, 0, Undefs); } }