This is an archive of the discontinued LLVM Phabricator instance.

Differential D20507

CodeGen: Refactor renameDisconnectedComponents() as a pass
ClosedPublic

Authored by MatzeB on May 20 2016, 8:08 PM.

Details

Reviewers
qcolombet
• tstellarAMD
Commits
rGf9acacaa928d: CodeGen: Refactor renameDisconnectedComponents() as a pass
rL271345: CodeGen: Refactor renameDisconnectedComponents() as a pass
Summary

Refactor LiveIntervals::renameDisconnectedComponents() to be a pass.
Also change the name to "RenameIndependentSubregs":

  • renameDisconnectedComponents() worked on a MachineFunction at a time so it is a natural candidate for an machine function pass.
  • The algorithm is testable with a .mir test now.
  • This also fixes a problem where the lazy renaming as part of the MachineScheduler introduced IMPLICIT_DEF instructions after the number of a nodes in a region were counted leading to a mismatch.

Diff Detail

Repository
rL LLVM

Event Timeline

MatzeB updated this revision to Diff 58029.May 20 2016, 8:08 PM
MatzeB retitled this revision from to CodeGen: Refactor renameDisconnectedComponents() as a pass.
MatzeB updated this object.
MatzeB added a reviewer: qcolombet.
MatzeB set the repository for this revision to rL LLVM.
MatzeB added a subscriber: llvm-commits.
Herald added subscribers: mcrosier, MatzeB. · View Herald TranscriptMay 20 2016, 8:08 PM
MatzeB updated this revision to Diff 58030.May 20 2016, 8:09 PM

Add a .mir test for the RenameIndependentSubregs pass.

Herald added a reviewer: • tstellarAMD. · View Herald TranscriptMay 20 2016, 8:09 PM
MatzeB updated this revision to Diff 58321.May 24 2016, 2:41 PM
MatzeB edited edge metadata.

Actually include newly created RenameIndependentSubregs.cpp file.

qcolombet edited edge metadata.May 26 2016, 5:46 PM

Hi Matthias,

I’ll try to look at this next week.

Thanks for your patience!

Cheers,
-Quentin

qcolombet accepted this revision.May 31 2016, 2:15 PM
qcolombet edited edge metadata.

Hi Matthias,

LGTM.

Nitpicks inlined.

Cheers,
-Quentin

lib/CodeGen/LiveRangeUtils.h
10 ↗(On Diff #58321)

typo: functions

22 ↗(On Diff #58321)

typo: to to

lib/CodeGen/RenameIndependentSubregs.cpp
1 ↗(On Diff #58321)

Copy/paste :)

40 ↗(On Diff #58321)

Could you add a DEBUG_TYPE and a few DEBUG statements in the pass to follow what is going on?

107 ↗(On Diff #58321)

Period

122 ↗(On Diff #58321)

DEBUG comment.
Like we could print the register here.

127 ↗(On Diff #58321)

DEBUG comment.
And add a comment here to say we are going to check if that live-range has several component, etc.

137 ↗(On Diff #58321)

Although the current implementation is correct, I was wondering what are your thoughts regarding relaxing the constraints on the register class and constraining them back when we rewrite the operands?
I actually do not expect that we would get much more freedom for regalloc afterwards, but who knows.

Note: the current implementation is the right thing to do, I was thinking in terms of follow-up patch.

201 ↗(On Diff #58321)

DEBUG comment.
Print that number.

test/CodeGen/AMDGPU/rename-independent-subregs.mir
6 ↗(On Diff #58321)

Could you add a comment explaining what configuration does this test check?
Basically, I would expecting something stating that this test checks that we correctly split %0 as it has three disjoint sets.

This revision is now accepted and ready to land.May 31 2016, 2:15 PM
MatzeB marked 10 inline comments as done.May 31 2016, 3:38 PM
MatzeB added inline comments.
lib/CodeGen/RenameIndependentSubregs.cpp
40 ↗(On Diff #58321)

I added some DEBUG printing that tells you how many equivalence classes were found and into which newly created vregs they were distributed. I opted to not print anything for vregs where no independent classes could be found to keep the debug output small.

107 ↗(On Diff #58321)

I kept this as it is the officially recommended way in the llvm coding convention and what is done in most parts of llvm. I know it contradicts that other rule in the coding convention that states that you should write sentences ending in periods in your comments...

137 ↗(On Diff #58321)

Yes this indeed something we could do in a follow-up commit, I added a TODO comment.
And for the record: We have the same issue in the LiveIntervals::splitSeparateComponents() code.

Closed by commit rL271345: CodeGen: Refactor renameDisconnectedComponents() as a pass (authored by matze). · Explain WhyMay 31 2016, 3:44 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
llvm/
trunk/
include/
llvm/
CodeGen/
72 lines
5 lines
5 lines
1 line
lib/
CodeGen/
1 line
1 line
267 lines
16 lines
62 lines
12 lines
388 lines
5 lines
test/
CodeGen/
AMDGPU/
30 lines

Diff 59140

llvm/trunk/include/llvm/CodeGen/LiveInterval.h

Show First 20 Lines • Show All 858 Lines • ▼ Show 20 Lines public:
/// Distribute values in \p LI into a separate LiveIntervals /// Distribute values in \p LI into a separate LiveIntervals
/// for each connected component. LIV must have an empty LiveInterval for /// for each connected component. LIV must have an empty LiveInterval for
/// each additional connected component. The first connected component is /// each additional connected component. The first connected component is
/// left in \p LI. /// left in \p LI.
void Distribute(LiveInterval &LI, LiveInterval *LIV[], void Distribute(LiveInterval &LI, LiveInterval *LIV[],
MachineRegisterInfo &MRI); MachineRegisterInfo &MRI);
}; };
/// Helper class that can divide MachineOperands of a virtual register into
/// equivalence classes of connected components.
/// MachineOperands belong to the same equivalence class when they are part of
/// the same SubRange segment or adjacent segments (adjacent in control
/// flow); Different subranges affected by the same MachineOperand belong to
/// the same equivalence class.
///
/// Example:
/// vreg0:sub0 = ...
/// vreg0:sub1 = ...
/// vreg0:sub2 = ...
/// ...
/// xxx = op vreg0:sub1
/// vreg0:sub1 = ...
/// store vreg0:sub0_sub1
///
/// The example contains 3 different equivalence classes:
/// - One for the (dead) vreg0:sub2 definition
/// - One containing the first vreg0:sub1 definition and its use,
/// but not the second definition!
/// - The remaining class contains all other operands involving vreg0.
///
/// We provide a utility function here to rename disjunct classes to different
/// virtual registers.
class ConnectedSubRegClasses {
LiveIntervals &LIS;
MachineRegisterInfo &MRI;
const TargetInstrInfo &TII;
public:
ConnectedSubRegClasses(LiveIntervals &LIS, MachineRegisterInfo &MRI,
const TargetInstrInfo &TII)
: LIS(LIS), MRI(MRI), TII(TII) {}
/// Split unrelated subregister components and rename them to new vregs.
void renameComponents(LiveInterval &LI) const;
private:
struct SubRangeInfo {
ConnectedVNInfoEqClasses ConEQ;
LiveInterval::SubRange *SR;
unsigned Index;
SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR,
unsigned Index)
: ConEQ(LIS), SR(&SR), Index(Index) {}
};
/// \brief Build a vector of SubRange infos and a union find set of
/// equivalence classes.
/// Returns true if more than 1 equivalence class was found.
bool findComponents(IntEqClasses &Classes,
SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
LiveInterval &LI) const;
/// \brief Distribute the LiveInterval segments into the new LiveIntervals
/// belonging to their class.
void distribute(const IntEqClasses &Classes,
const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
const SmallVectorImpl<LiveInterval*> &Intervals) const;
/// \brief Constructs main liverange and add missing undef+dead flags.
void computeMainRangesFixFlags(const IntEqClasses &Classes,
const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
const SmallVectorImpl<LiveInterval*> &Intervals) const;
/// Rewrite Machine Operands to use the new vreg belonging to their class.
void rewriteOperands(const IntEqClasses &Classes,
const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
const SmallVectorImpl<LiveInterval*> &Intervals) const;
};
} }
#endif #endif

llvm/trunk/include/llvm/CodeGen/LiveIntervalAnalysis.h

Show First 20 Lines • Show All 399 Lines • ▼ Show 20 Lines public:
/// Remove value number and related live segments of @p LI and its subranges /// Remove value number and related live segments of @p LI and its subranges
/// that start at position @p Pos. /// that start at position @p Pos.
void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos); void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos);
/// Split separate components in LiveInterval \p LI into separate intervals. /// Split separate components in LiveInterval \p LI into separate intervals.
void splitSeparateComponents(LiveInterval &LI, void splitSeparateComponents(LiveInterval &LI,
SmallVectorImpl<LiveInterval*> &SplitLIs); SmallVectorImpl<LiveInterval*> &SplitLIs);
/// Assure dead subregister definitions have their own vreg assigned.
/// This calls ConnectedSubRegClasses::splitSeparateSubRegComponent()
/// on each virtual register.
void renameDisconnectedComponents();
/// For live interval \p LI with correct SubRanges construct matching /// For live interval \p LI with correct SubRanges construct matching
/// information for the main live range. Expects the main live range to not /// information for the main live range. Expects the main live range to not
/// have any segments or value numbers. /// have any segments or value numbers.
void constructMainRangeFromSubranges(LiveInterval &LI); void constructMainRangeFromSubranges(LiveInterval &LI);
private: private:
/// Compute live intervals for all virtual registers. /// Compute live intervals for all virtual registers.
void computeVirtRegs(); void computeVirtRegs();
Show All 38 Lines

llvm/trunk/include/llvm/CodeGen/Passes.h

Show First 20 Lines • Show All 350 Lines • ▼ Show 20 Lines/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
/// ///
Pass *createGlobalMergePass(const TargetMachine *TM, unsigned MaximalOffset, Pass *createGlobalMergePass(const TargetMachine *TM, unsigned MaximalOffset,
bool OnlyOptimizeForSize = false, bool OnlyOptimizeForSize = false,
bool MergeExternalByDefault = false); bool MergeExternalByDefault = false);
/// This pass splits the stack into a safe stack and an unsafe stack to /// This pass splits the stack into a safe stack and an unsafe stack to
/// protect against stack-based overflow vulnerabilities. /// protect against stack-based overflow vulnerabilities.
FunctionPass *createSafeStackPass(const TargetMachine *TM = nullptr); FunctionPass *createSafeStackPass(const TargetMachine *TM = nullptr);
/// This pass detects subregister lanes in a virtual register that are used
/// independently of other lanes and splits them into separate virtual
/// registers.
extern char &RenameIndependentSubregsID;
} // End llvm namespace } // End llvm namespace
/// Target machine pass initializer for passes with dependencies. Use with /// Target machine pass initializer for passes with dependencies. Use with
/// INITIALIZE_TM_PASS_END. /// INITIALIZE_TM_PASS_END.
#define INITIALIZE_TM_PASS_BEGIN INITIALIZE_PASS_BEGIN #define INITIALIZE_TM_PASS_BEGIN INITIALIZE_PASS_BEGIN
/// Target machine pass initializer for passes with dependencies. Use with /// Target machine pass initializer for passes with dependencies. Use with
/// INITIALIZE_TM_PASS_BEGIN. /// INITIALIZE_TM_PASS_BEGIN.
Show All 21 Lines

llvm/trunk/include/llvm/InitializePasses.h

Show First 20 Lines • Show All 260 Lines • ▼ Show 20 Lines
void initializeReassociateLegacyPassPass(PassRegistry&); void initializeReassociateLegacyPassPass(PassRegistry&);
void initializeRegBankSelectPass(PassRegistry &); void initializeRegBankSelectPass(PassRegistry &);
void initializeRegToMemPass(PassRegistry&); void initializeRegToMemPass(PassRegistry&);
void initializeRegionInfoPassPass(PassRegistry&); void initializeRegionInfoPassPass(PassRegistry&);
void initializeRegionOnlyPrinterPass(PassRegistry&); void initializeRegionOnlyPrinterPass(PassRegistry&);
void initializeRegionOnlyViewerPass(PassRegistry&); void initializeRegionOnlyViewerPass(PassRegistry&);
void initializeRegionPrinterPass(PassRegistry&); void initializeRegionPrinterPass(PassRegistry&);
void initializeRegionViewerPass(PassRegistry&); void initializeRegionViewerPass(PassRegistry&);
void initializeRenameIndependentSubregsPass(PassRegistry&);
void initializeReversePostOrderFunctionAttrsPass(PassRegistry&); void initializeReversePostOrderFunctionAttrsPass(PassRegistry&);
void initializeRewriteStatepointsForGCPass(PassRegistry&); void initializeRewriteStatepointsForGCPass(PassRegistry&);
void initializeSafeStackPass(PassRegistry&); void initializeSafeStackPass(PassRegistry&);
void initializeSCCPLegacyPassPass(PassRegistry &); void initializeSCCPLegacyPassPass(PassRegistry &);
void initializeSROALegacyPassPass(PassRegistry&); void initializeSROALegacyPassPass(PassRegistry&);
void initializeSROA_DTPass(PassRegistry&); void initializeSROA_DTPass(PassRegistry&);
void initializeSROA_SSAUpPass(PassRegistry&); void initializeSROA_SSAUpPass(PassRegistry&);
void initializeSCEVAAWrapperPassPass(PassRegistry&); void initializeSCEVAAWrapperPassPass(PassRegistry&);
▲ Show 20 Lines • Show All 67 Lines • Show Last 20 Lines

llvm/trunk/lib/CodeGen/CMakeLists.txt

Show First 20 Lines • Show All 94 Lines • ▼ Show 20 Linesadd_llvm_library(LLVMCodeGen
RegAllocBasic.cpp RegAllocBasic.cpp
RegAllocFast.cpp RegAllocFast.cpp
RegAllocGreedy.cpp RegAllocGreedy.cpp
RegAllocPBQP.cpp RegAllocPBQP.cpp
RegisterClassInfo.cpp RegisterClassInfo.cpp
RegisterCoalescer.cpp RegisterCoalescer.cpp
RegisterPressure.cpp RegisterPressure.cpp
RegisterScavenging.cpp RegisterScavenging.cpp
RenameIndependentSubregs.cpp
SafeStack.cpp SafeStack.cpp
ScheduleDAG.cpp ScheduleDAG.cpp
ScheduleDAGInstrs.cpp ScheduleDAGInstrs.cpp
ScheduleDAGPrinter.cpp ScheduleDAGPrinter.cpp
ScoreboardHazardRecognizer.cpp ScoreboardHazardRecognizer.cpp
ShadowStackGCLowering.cpp ShadowStackGCLowering.cpp
ShrinkWrap.cpp ShrinkWrap.cpp
SjLjEHPrepare.cpp SjLjEHPrepare.cpp
Show All 36 Lines

llvm/trunk/lib/CodeGen/CodeGen.cpp

Show First 20 Lines • Show All 62 Lines • ▼ Show 20 Linesvoid llvm::initializeCodeGen(PassRegistry &Registry) {
initializePHIEliminationPass(Registry); initializePHIEliminationPass(Registry);
initializePeepholeOptimizerPass(Registry); initializePeepholeOptimizerPass(Registry);
initializePostMachineSchedulerPass(Registry); initializePostMachineSchedulerPass(Registry);
initializePostRAHazardRecognizerPass(Registry); initializePostRAHazardRecognizerPass(Registry);
initializePostRASchedulerPass(Registry); initializePostRASchedulerPass(Registry);
initializePreISelIntrinsicLoweringPass(Registry); initializePreISelIntrinsicLoweringPass(Registry);
initializeProcessImplicitDefsPass(Registry); initializeProcessImplicitDefsPass(Registry);
initializeRegisterCoalescerPass(Registry); initializeRegisterCoalescerPass(Registry);
initializeRenameIndependentSubregsPass(Registry);
initializeShrinkWrapPass(Registry); initializeShrinkWrapPass(Registry);
initializeSlotIndexesPass(Registry); initializeSlotIndexesPass(Registry);
initializeStackColoringPass(Registry); initializeStackColoringPass(Registry);
initializeStackMapLivenessPass(Registry); initializeStackMapLivenessPass(Registry);
initializeLiveDebugValuesPass(Registry); initializeLiveDebugValuesPass(Registry);
initializeSafeStackPass(Registry); initializeSafeStackPass(Registry);
initializeStackProtectorPass(Registry); initializeStackProtectorPass(Registry);
initializeStackSlotColoringPass(Registry); initializeStackSlotColoringPass(Registry);
Show All 14 Lines

llvm/trunk/lib/CodeGen/LiveInterval.cpp

Show All 14 Lines
// i.e. a range might look like [1,20), [50,65), [1000,1001). Each // i.e. a range might look like [1,20), [50,65), [1000,1001). Each
// individual segment is represented as an instance of LiveRange::Segment, // individual segment is represented as an instance of LiveRange::Segment,
// and the whole range is represented as an instance of LiveRange. // and the whole range is represented as an instance of LiveRange.
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#include "llvm/CodeGen/LiveInterval.h" #include "llvm/CodeGen/LiveInterval.h"
#include "PHIEliminationUtils.h" #include "LiveRangeUtils.h"
#include "RegisterCoalescer.h" #include "RegisterCoalescer.h"
#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallSet.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Support/Debug.h" #include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h" #include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetRegisterInfo.h"
#include <algorithm> #include <algorithm>
using namespace llvm; using namespace llvm;
namespace { namespace {
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
// Implementation of various methods necessary for calculation of live ranges. // Implementation of various methods necessary for calculation of live ranges.
// The implementation of the methods abstracts from the concrete type of the // The implementation of the methods abstracts from the concrete type of the
▲ Show 20 Lines • Show All 1,130 Lines • ▼ Show 20 Linesunsigned ConnectedVNInfoEqClasses::Classify(const LiveRange &LR) {
// Lump all the unused values in with the last used value. // Lump all the unused values in with the last used value.
if (used && unused) if (used && unused)
EqClass.join(used->id, unused->id); EqClass.join(used->id, unused->id);
EqClass.compress(); EqClass.compress();
return EqClass.getNumClasses(); return EqClass.getNumClasses();
} }
template<typename LiveRangeT, typename EqClassesT>
static void DistributeRange(LiveRangeT &LR, LiveRangeT *SplitLRs[],
EqClassesT VNIClasses) {
// Move segments to new intervals.
LiveRange::iterator J = LR.begin(), E = LR.end();
while (J != E && VNIClasses[J->valno->id] == 0)
++J;
for (LiveRange::iterator I = J; I != E; ++I) {
if (unsigned eq = VNIClasses[I->valno->id]) {
assert((SplitLRs[eq-1]->empty() || SplitLRs[eq-1]->expiredAt(I->start)) &&
"New intervals should be empty");
SplitLRs[eq-1]->segments.push_back(*I);
} else
*J++ = *I;
}
LR.segments.erase(J, E);
// Transfer VNInfos to their new owners and renumber them.
unsigned j = 0, e = LR.getNumValNums();
while (j != e && VNIClasses[j] == 0)
++j;
for (unsigned i = j; i != e; ++i) {
VNInfo *VNI = LR.getValNumInfo(i);
if (unsigned eq = VNIClasses[i]) {
VNI->id = SplitLRs[eq-1]->getNumValNums();
SplitLRs[eq-1]->valnos.push_back(VNI);
} else {
VNI->id = j;
LR.valnos[j++] = VNI;
}
}
LR.valnos.resize(j);
}
void ConnectedVNInfoEqClasses::Distribute(LiveInterval &LI, LiveInterval *LIV[], void ConnectedVNInfoEqClasses::Distribute(LiveInterval &LI, LiveInterval *LIV[],
MachineRegisterInfo &MRI) { MachineRegisterInfo &MRI) {
// Rewrite instructions. // Rewrite instructions.
for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg), for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg),
RE = MRI.reg_end(); RI != RE;) { RE = MRI.reg_end(); RI != RE;) {
MachineOperand &MO = *RI; MachineOperand &MO = *RI;
MachineInstr *MI = RI->getParent(); MachineInstr *MI = RI->getParent();
++RI; ++RI;
▲ Show 20 Lines • Show All 50 Lines • ▼ Show 20 Lines for (LiveInterval::SubRange &SR : LI.subranges()) {
DistributeRange(SR, SubRanges.data(), VNIMapping); DistributeRange(SR, SubRanges.data(), VNIMapping);
} }
LI.removeEmptySubRanges(); LI.removeEmptySubRanges();
} }
// Distribute main liverange. // Distribute main liverange.
DistributeRange(LI, LIV, EqClass); DistributeRange(LI, LIV, EqClass);
} }
void ConnectedSubRegClasses::renameComponents(LiveInterval &LI) const {
// Shortcut: We cannot have split components with a single definition.
if (LI.valnos.size() < 2)
return;
SmallVector<SubRangeInfo, 4> SubRangeInfos;
IntEqClasses Classes;
if (!findComponents(Classes, SubRangeInfos, LI))
return;
// Create a new VReg for each class.
unsigned Reg = LI.reg;
const TargetRegisterClass *RegClass = MRI.getRegClass(Reg);
SmallVector<LiveInterval*, 4> Intervals;
Intervals.push_back(&LI);
for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses;
++I) {
unsigned NewVReg = MRI.createVirtualRegister(RegClass);
LiveInterval &NewLI = LIS.createEmptyInterval(NewVReg);
Intervals.push_back(&NewLI);
}
rewriteOperands(Classes, SubRangeInfos, Intervals);
distribute(Classes, SubRangeInfos, Intervals);
computeMainRangesFixFlags(Classes, SubRangeInfos, Intervals);
}
bool ConnectedSubRegClasses::findComponents(IntEqClasses &Classes,
SmallVectorImpl<ConnectedSubRegClasses::SubRangeInfo> &SubRangeInfos,
LiveInterval &LI) const {
// First step: Create connected components for the VNInfos inside the
// subranges and count the global number of such components.
unsigned NumComponents = 0;
for (LiveInterval::SubRange &SR : LI.subranges()) {
SubRangeInfos.push_back(SubRangeInfo(LIS, SR, NumComponents));
ConnectedVNInfoEqClasses &ConEQ = SubRangeInfos.back().ConEQ;
unsigned NumSubComponents = ConEQ.Classify(SR);
NumComponents += NumSubComponents;
}
// Shortcut: With only 1 subrange, the normal separate component tests are
// enough and we do not need to perform the union-find on the subregister
// segments.
if (SubRangeInfos.size() < 2)
return false;
// Next step: Build union-find structure over all subranges and merge classes
// across subranges when they are affected by the same MachineOperand.
const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
Classes.grow(NumComponents);
unsigned Reg = LI.reg;
for (const MachineOperand &MO : MRI.reg_nodbg_operands(Reg)) {
if (!MO.isDef() && !MO.readsReg())
continue;
unsigned SubRegIdx = MO.getSubReg();
LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
unsigned MergedID = ~0u;
for (ConnectedSubRegClasses::SubRangeInfo &SRInfo : SubRangeInfos) {
const LiveInterval::SubRange &SR = *SRInfo.SR;
if ((SR.LaneMask & LaneMask) == 0)
continue;
SlotIndex Pos = LIS.getInstructionIndex(*MO.getParent());
Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber())
: Pos.getBaseIndex();
const VNInfo *VNI = SR.getVNInfoAt(Pos);
if (VNI == nullptr)
continue;
// Map to local representant ID.
unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);
// Global ID
unsigned ID = LocalID + SRInfo.Index;
// Merge other sets
MergedID = MergedID == ~0u ? ID : Classes.join(MergedID, ID);
}
}
// Early exit if we ended up with a single equivalence class.
Classes.compress();
unsigned NumClasses = Classes.getNumClasses();
return NumClasses > 1;
}
void ConnectedSubRegClasses::rewriteOperands(const IntEqClasses &Classes,
const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
const SmallVectorImpl<LiveInterval*> &Intervals) const {
const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
unsigned Reg = Intervals[0]->reg;;
for (MachineRegisterInfo::reg_nodbg_iterator I = MRI.reg_nodbg_begin(Reg),
E = MRI.reg_nodbg_end(); I != E; ) {
MachineOperand &MO = *I++;
if (!MO.isDef() && !MO.readsReg())
continue;
MachineInstr &MI = *MO.getParent();
SlotIndex Pos = LIS.getInstructionIndex(MI);
unsigned SubRegIdx = MO.getSubReg();
LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
unsigned ID = ~0u;
for (const SubRangeInfo &SRInfo : SubRangeInfos) {
const LiveInterval::SubRange &SR = *SRInfo.SR;
if ((SR.LaneMask & LaneMask) == 0)
continue;
LiveRange::const_iterator I = SR.find(Pos);
if (I == SR.end())
continue;
const VNInfo &VNI = *I->valno;
// Map to local representant ID.
unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI);
// Global ID
ID = Classes[LocalID + SRInfo.Index];
break;
}
unsigned VReg = Intervals[ID]->reg;
MO.setReg(VReg);
}
}
void ConnectedSubRegClasses::distribute(const IntEqClasses &Classes,
const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
const SmallVectorImpl<LiveInterval*> &Intervals) const {
unsigned NumClasses = Classes.getNumClasses();
SmallVector<unsigned, 8> VNIMapping;
SmallVector<LiveInterval::SubRange*, 8> SubRanges;
BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
for (const SubRangeInfo &SRInfo : SubRangeInfos) {
LiveInterval::SubRange &SR = *SRInfo.SR;
unsigned NumValNos = SR.valnos.size();
VNIMapping.clear();
VNIMapping.reserve(NumValNos);
SubRanges.clear();
SubRanges.resize(NumClasses-1, nullptr);
for (unsigned I = 0; I < NumValNos; ++I) {
const VNInfo &VNI = *SR.valnos[I];
unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI);
unsigned ID = Classes[LocalID + SRInfo.Index];
VNIMapping.push_back(ID);
if (ID > 0 && SubRanges[ID-1] == nullptr)
SubRanges[ID-1] = Intervals[ID]->createSubRange(Allocator, SR.LaneMask);
}
DistributeRange(SR, SubRanges.data(), VNIMapping);
}
}
static bool subRangeLiveAt(const LiveInterval &LI, SlotIndex Pos) {
for (const LiveInterval::SubRange &SR : LI.subranges()) {
if (SR.liveAt(Pos))
return true;
}
return false;
}
void ConnectedSubRegClasses::computeMainRangesFixFlags(
const IntEqClasses &Classes,
const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
const SmallVectorImpl<LiveInterval*> &Intervals) const {
BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
const SlotIndexes &Indexes = *LIS.getSlotIndexes();
for (size_t I = 0, E = Intervals.size(); I < E; ++I) {
LiveInterval &LI = *Intervals[I];
unsigned Reg = LI.reg;
LI.removeEmptySubRanges();
// There must be a def (or live-in) before every use. Splitting vregs may
// violate this principle as the splitted vreg may not have a definition on
// every path. Fix this by creating IMPLICIT_DEF instruction as necessary.
for (const LiveInterval::SubRange &SR : LI.subranges()) {
// Search for "PHI" value numbers in the subranges. We must find a live
// value in each predecessor block, add an IMPLICIT_DEF where it is
// missing.
for (unsigned I = 0; I < SR.valnos.size(); ++I) {
const VNInfo &VNI = *SR.valnos[I];
if (VNI.isUnused() || !VNI.isPHIDef())
continue;
SlotIndex Def = VNI.def;
MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(Def);
for (MachineBasicBlock *PredMBB : MBB.predecessors()) {
SlotIndex PredEnd = Indexes.getMBBEndIdx(PredMBB);
if (subRangeLiveAt(LI, PredEnd.getPrevSlot()))
continue;
MachineBasicBlock::iterator InsertPos =
llvm::findPHICopyInsertPoint(PredMBB, &MBB, Reg);
const MCInstrDesc &MCDesc = TII.get(TargetOpcode::IMPLICIT_DEF);
MachineInstrBuilder ImpDef = BuildMI(*PredMBB, InsertPos,
DebugLoc(), MCDesc, Reg);
SlotIndex DefIdx = LIS.InsertMachineInstrInMaps(*ImpDef);
SlotIndex RegDefIdx = DefIdx.getRegSlot();
for (LiveInterval::SubRange &SR : LI.subranges()) {
VNInfo *SRVNI = SR.getNextValue(RegDefIdx, Allocator);
SR.addSegment(LiveRange::Segment(RegDefIdx, PredEnd, SRVNI));
}
}
}
}
for (MachineOperand &MO : MRI.reg_nodbg_operands(Reg)) {
if (!MO.isDef())
continue;
unsigned SubRegIdx = MO.getSubReg();
if (SubRegIdx == 0)
continue;
// After assigning the new vreg we may not have any other sublanes living
// in and out of the instruction anymore. We need to add new dead and
// undef flags in these cases.
if (!MO.isUndef()) {
SlotIndex Pos = LIS.getInstructionIndex(*MO.getParent());
if (!subRangeLiveAt(LI, Pos))
MO.setIsUndef();
}
if (!MO.isDead()) {
SlotIndex Pos = LIS.getInstructionIndex(*MO.getParent()).getDeadSlot();
if (!subRangeLiveAt(LI, Pos))
MO.setIsDead();
}
}
if (I == 0)
LI.clear();
LIS.constructMainRangeFromSubranges(LI);
}
}

llvm/trunk/lib/CodeGen/LiveIntervalAnalysis.cpp

Show First 20 Lines • Show All 1,560 Lines • ▼ Show 20 Linesvoid LiveIntervals::splitSeparateComponents(LiveInterval &LI,
for (unsigned I = 1; I < NumComp; ++I) { for (unsigned I = 1; I < NumComp; ++I) {
unsigned NewVReg = MRI->createVirtualRegister(RegClass); unsigned NewVReg = MRI->createVirtualRegister(RegClass);
LiveInterval &NewLI = createEmptyInterval(NewVReg); LiveInterval &NewLI = createEmptyInterval(NewVReg);
SplitLIs.push_back(&NewLI); SplitLIs.push_back(&NewLI);
} }
ConEQ.Distribute(LI, SplitLIs.data(), *MRI); ConEQ.Distribute(LI, SplitLIs.data(), *MRI);
} }
void LiveIntervals::renameDisconnectedComponents() {
ConnectedSubRegClasses SubRegClasses(*this, *MRI, *TII);
// Iterate over all vregs. Note that we query getNumVirtRegs() the newly
// created vregs end up with higher numbers but do not need to be visited as
// there can't be any further splitting.
for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; ++I) {
unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
LiveInterval *LI = VirtRegIntervals[Reg];
if (LI == nullptr || !LI->hasSubRanges())
continue;
SubRegClasses.renameComponents(*LI);
}
}
void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) { void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) {
assert(LRCalc && "LRCalc not initialized."); assert(LRCalc && "LRCalc not initialized.");
LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
LRCalc->constructMainRangeFromSubranges(LI); LRCalc->constructMainRangeFromSubranges(LI);
} }

llvm/trunk/lib/CodeGen/LiveRangeUtils.h

//===-- LiveRangeUtils.h - Live Range modification utilities ----*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
/// This file contains helper functions to modify live ranges.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_LIB_CODEGEN_LIVERANGEUTILS_H
#define LLVM_LIB_CODEGEN_LIVERANGEUTILS_H
#include "llvm/CodeGen/LiveInterval.h"
namespace llvm {
/// Helper function that distributes live range value numbers and the
/// corresponding segments of a master live range \p LR to a list of newly
/// created live ranges \p SplitLRs. \p VNIClasses maps each value number in \p
/// LR to 0 meaning it should stay or to 1..N meaning it should go to a specific
/// live range in the \p SplitLRs array.
template<typename LiveRangeT, typename EqClassesT>
static void DistributeRange(LiveRangeT &LR, LiveRangeT *SplitLRs[],
EqClassesT VNIClasses) {
// Move segments to new intervals.
typename LiveRangeT::iterator J = LR.begin(), E = LR.end();
while (J != E && VNIClasses[J->valno->id] == 0)
++J;
for (typename LiveRangeT::iterator I = J; I != E; ++I) {
if (unsigned eq = VNIClasses[I->valno->id]) {
assert((SplitLRs[eq-1]->empty() || SplitLRs[eq-1]->expiredAt(I->start)) &&
"New intervals should be empty");
SplitLRs[eq-1]->segments.push_back(*I);
} else
*J++ = *I;
}
LR.segments.erase(J, E);
// Transfer VNInfos to their new owners and renumber them.
unsigned j = 0, e = LR.getNumValNums();
while (j != e && VNIClasses[j] == 0)
++j;
for (unsigned i = j; i != e; ++i) {
VNInfo *VNI = LR.getValNumInfo(i);
if (unsigned eq = VNIClasses[i]) {
VNI->id = SplitLRs[eq-1]->getNumValNums();
SplitLRs[eq-1]->valnos.push_back(VNI);
} else {
VNI->id = j;
LR.valnos[j++] = VNI;
}
}
LR.valnos.resize(j);
}
} // End llvm namespace
#endif

llvm/trunk/lib/CodeGen/MachineScheduler.cpp

Show First 20 Lines • Show All 876 Lines • ▼ Show 20 Linesvoid ScheduleDAGMILive::enterRegion(MachineBasicBlock *bb,
// For convenience remember the end of the liveness region. // For convenience remember the end of the liveness region.
LiveRegionEnd = (RegionEnd == bb->end()) ? RegionEnd : std::next(RegionEnd); LiveRegionEnd = (RegionEnd == bb->end()) ? RegionEnd : std::next(RegionEnd);
SUPressureDiffs.clear(); SUPressureDiffs.clear();
ShouldTrackPressure = SchedImpl->shouldTrackPressure(); ShouldTrackPressure = SchedImpl->shouldTrackPressure();
ShouldTrackLaneMasks = SchedImpl->shouldTrackLaneMasks(); ShouldTrackLaneMasks = SchedImpl->shouldTrackLaneMasks();
if (ShouldTrackLaneMasks) { assert((!ShouldTrackLaneMasks || ShouldTrackPressure) &&
if (!ShouldTrackPressure) "ShouldTrackLaneMasks requires ShouldTrackPressure");
report_fatal_error("ShouldTrackLaneMasks requires ShouldTrackPressure");
// Dead subregister defs have no users and therefore no dependencies,
// moving them around may cause liveintervals to degrade into multiple
// components. Change independent components to have their own vreg to avoid
// this.
if (!DisconnectedComponentsRenamed)
LIS->renameDisconnectedComponents();
}
} }
// Setup the register pressure trackers for the top scheduled top and bottom // Setup the register pressure trackers for the top scheduled top and bottom
// scheduled regions. // scheduled regions.
void ScheduleDAGMILive::initRegPressure() { void ScheduleDAGMILive::initRegPressure() {
TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin, TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin,
ShouldTrackLaneMasks, false); ShouldTrackLaneMasks, false);
BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd, BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd,
▲ Show 20 Lines • Show All 2,615 Lines • Show Last 20 Lines

llvm/trunk/lib/CodeGen/RenameIndependentSubregs.cpp

//===-- RenameIndependentSubregs.cpp - Live Interval Analysis -------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
/// Rename independent subregisters looks for virtual registers with
/// independently used subregisters and renames them to new virtual registers.
/// Example: In the following:
/// %vreg0:sub0<read-undef> = ...
/// %vreg0:sub1 = ...
/// use %vreg0:sub0
/// %vreg0:sub0 = ...
/// use %vreg0:sub0
/// use %vreg0:sub1
/// sub0 and sub1 are never used together, and we have two independent sub0
/// definitions. This pass will rename to:
/// %vreg0:sub0<read-undef> = ...
/// %vreg1:sub1<read-undef> = ...
/// use %vreg1:sub1
/// %vreg2:sub1<read-undef> = ...
/// use %vreg2:sub1
/// use %vreg0:sub0
//
//===----------------------------------------------------------------------===//
#include "LiveRangeUtils.h"
#include "PHIEliminationUtils.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
using namespace llvm;
#define DEBUG_TYPE "rename-independent-subregs"
namespace {
class RenameIndependentSubregs : public MachineFunctionPass {
public:
static char ID;
RenameIndependentSubregs() : MachineFunctionPass(ID) {}
const char *getPassName() const override {
return "Rename Disconnected Subregister Components";
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
AU.addRequired<LiveIntervals>();
AU.addPreserved<LiveIntervals>();
AU.addRequired<SlotIndexes>();
AU.addPreserved<SlotIndexes>();
MachineFunctionPass::getAnalysisUsage(AU);
}
bool runOnMachineFunction(MachineFunction &MF) override;
private:
struct SubRangeInfo {
ConnectedVNInfoEqClasses ConEQ;
LiveInterval::SubRange *SR;
unsigned Index;
SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR,
unsigned Index)
: ConEQ(LIS), SR(&SR), Index(Index) {}
};
/// Split unrelated subregister components and rename them to new vregs.
bool renameComponents(LiveInterval &LI) const;
/// \brief Build a vector of SubRange infos and a union find set of
/// equivalence classes.
/// Returns true if more than 1 equivalence class was found.
bool findComponents(IntEqClasses &Classes,
SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
LiveInterval &LI) const;
/// \brief Distribute the LiveInterval segments into the new LiveIntervals
/// belonging to their class.
void distribute(const IntEqClasses &Classes,
const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
const SmallVectorImpl<LiveInterval*> &Intervals) const;
/// \brief Constructs main liverange and add missing undef+dead flags.
void computeMainRangesFixFlags(const IntEqClasses &Classes,
const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
const SmallVectorImpl<LiveInterval*> &Intervals) const;
/// Rewrite Machine Operands to use the new vreg belonging to their class.
void rewriteOperands(const IntEqClasses &Classes,
const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
const SmallVectorImpl<LiveInterval*> &Intervals) const;
LiveIntervals *LIS;
MachineRegisterInfo *MRI;
const TargetInstrInfo *TII;
};
} // end anonymous namespace
char RenameIndependentSubregs::ID;
char &llvm::RenameIndependentSubregsID = RenameIndependentSubregs::ID;
INITIALIZE_PASS_BEGIN(RenameIndependentSubregs, "rename-independent-subregs",
"Rename Independent Subregisters", false, false)
INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
INITIALIZE_PASS_END(RenameIndependentSubregs, "rename-independent-subregs",
"Rename Independent Subregisters", false, false)
bool RenameIndependentSubregs::renameComponents(LiveInterval &LI) const {
// Shortcut: We cannot have split components with a single definition.
if (LI.valnos.size() < 2)
return false;
SmallVector<SubRangeInfo, 4> SubRangeInfos;
IntEqClasses Classes;
if (!findComponents(Classes, SubRangeInfos, LI))
return false;
// Create a new VReg for each class.
unsigned Reg = LI.reg;
const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
SmallVector<LiveInterval*, 4> Intervals;
Intervals.push_back(&LI);
DEBUG(dbgs() << PrintReg(Reg) << ": Found " << Classes.getNumClasses()
<< " equivalence classes.\n");
DEBUG(dbgs() << PrintReg(Reg) << ": Splitting into newly created:");
for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses;
++I) {
unsigned NewVReg = MRI->createVirtualRegister(RegClass);
LiveInterval &NewLI = LIS->createEmptyInterval(NewVReg);
Intervals.push_back(&NewLI);
DEBUG(dbgs() << ' ' << PrintReg(NewVReg));
}
DEBUG(dbgs() << '\n');
rewriteOperands(Classes, SubRangeInfos, Intervals);
distribute(Classes, SubRangeInfos, Intervals);
computeMainRangesFixFlags(Classes, SubRangeInfos, Intervals);
return true;
}
bool RenameIndependentSubregs::findComponents(IntEqClasses &Classes,
SmallVectorImpl<RenameIndependentSubregs::SubRangeInfo> &SubRangeInfos,
LiveInterval &LI) const {
// First step: Create connected components for the VNInfos inside the
// subranges and count the global number of such components.
unsigned NumComponents = 0;
for (LiveInterval::SubRange &SR : LI.subranges()) {
SubRangeInfos.push_back(SubRangeInfo(*LIS, SR, NumComponents));
ConnectedVNInfoEqClasses &ConEQ = SubRangeInfos.back().ConEQ;
unsigned NumSubComponents = ConEQ.Classify(SR);
NumComponents += NumSubComponents;
}
// Shortcut: With only 1 subrange, the normal separate component tests are
// enough and we do not need to perform the union-find on the subregister
// segments.
if (SubRangeInfos.size() < 2)
return false;
// Next step: Build union-find structure over all subranges and merge classes
// across subranges when they are affected by the same MachineOperand.
const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
Classes.grow(NumComponents);
unsigned Reg = LI.reg;
for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
if (!MO.isDef() && !MO.readsReg())
continue;
unsigned SubRegIdx = MO.getSubReg();
LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
unsigned MergedID = ~0u;
for (RenameIndependentSubregs::SubRangeInfo &SRInfo : SubRangeInfos) {
const LiveInterval::SubRange &SR = *SRInfo.SR;
if ((SR.LaneMask & LaneMask) == 0)
continue;
SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber())
: Pos.getBaseIndex();
const VNInfo *VNI = SR.getVNInfoAt(Pos);
if (VNI == nullptr)
continue;
// Map to local representant ID.
unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);
// Global ID
unsigned ID = LocalID + SRInfo.Index;
// Merge other sets
MergedID = MergedID == ~0u ? ID : Classes.join(MergedID, ID);
}
}
// Early exit if we ended up with a single equivalence class.
Classes.compress();
unsigned NumClasses = Classes.getNumClasses();
return NumClasses > 1;
}
void RenameIndependentSubregs::rewriteOperands(const IntEqClasses &Classes,
const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
const SmallVectorImpl<LiveInterval*> &Intervals) const {
const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
unsigned Reg = Intervals[0]->reg;;
for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg),
E = MRI->reg_nodbg_end(); I != E; ) {
MachineOperand &MO = *I++;
if (!MO.isDef() && !MO.readsReg())
continue;
MachineInstr &MI = *MO.getParent();
SlotIndex Pos = LIS->getInstructionIndex(MI);
unsigned SubRegIdx = MO.getSubReg();
LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
unsigned ID = ~0u;
for (const SubRangeInfo &SRInfo : SubRangeInfos) {
const LiveInterval::SubRange &SR = *SRInfo.SR;
if ((SR.LaneMask & LaneMask) == 0)
continue;
LiveRange::const_iterator I = SR.find(Pos);
if (I == SR.end())
continue;
const VNInfo &VNI = *I->valno;
// Map to local representant ID.
unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI);
// Global ID
ID = Classes[LocalID + SRInfo.Index];
break;
}
unsigned VReg = Intervals[ID]->reg;
MO.setReg(VReg);
}
// TODO: We could attempt to recompute new register classes while visiting
// the operands: Some of the split register may be fine with less constraint
// classes than the original vreg.
}
void RenameIndependentSubregs::distribute(const IntEqClasses &Classes,
const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
const SmallVectorImpl<LiveInterval*> &Intervals) const {
unsigned NumClasses = Classes.getNumClasses();
SmallVector<unsigned, 8> VNIMapping;
SmallVector<LiveInterval::SubRange*, 8> SubRanges;
BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
for (const SubRangeInfo &SRInfo : SubRangeInfos) {
LiveInterval::SubRange &SR = *SRInfo.SR;
unsigned NumValNos = SR.valnos.size();
VNIMapping.clear();
VNIMapping.reserve(NumValNos);
SubRanges.clear();
SubRanges.resize(NumClasses-1, nullptr);
for (unsigned I = 0; I < NumValNos; ++I) {
const VNInfo &VNI = *SR.valnos[I];
unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI);
unsigned ID = Classes[LocalID + SRInfo.Index];
VNIMapping.push_back(ID);
if (ID > 0 && SubRanges[ID-1] == nullptr)
SubRanges[ID-1] = Intervals[ID]->createSubRange(Allocator, SR.LaneMask);
}
DistributeRange(SR, SubRanges.data(), VNIMapping);
}
}
static bool subRangeLiveAt(const LiveInterval &LI, SlotIndex Pos) {
for (const LiveInterval::SubRange &SR : LI.subranges()) {
if (SR.liveAt(Pos))
return true;
}
return false;
}
void RenameIndependentSubregs::computeMainRangesFixFlags(
const IntEqClasses &Classes,
const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
const SmallVectorImpl<LiveInterval*> &Intervals) const {
BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
const SlotIndexes &Indexes = *LIS->getSlotIndexes();
for (size_t I = 0, E = Intervals.size(); I < E; ++I) {
LiveInterval &LI = *Intervals[I];
unsigned Reg = LI.reg;
LI.removeEmptySubRanges();
// There must be a def (or live-in) before every use. Splitting vregs may
// violate this principle as the splitted vreg may not have a definition on
// every path. Fix this by creating IMPLICIT_DEF instruction as necessary.
for (const LiveInterval::SubRange &SR : LI.subranges()) {
// Search for "PHI" value numbers in the subranges. We must find a live
// value in each predecessor block, add an IMPLICIT_DEF where it is
// missing.
for (unsigned I = 0; I < SR.valnos.size(); ++I) {
const VNInfo &VNI = *SR.valnos[I];
if (VNI.isUnused() || !VNI.isPHIDef())
continue;
SlotIndex Def = VNI.def;
MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(Def);
for (MachineBasicBlock *PredMBB : MBB.predecessors()) {
SlotIndex PredEnd = Indexes.getMBBEndIdx(PredMBB);
if (subRangeLiveAt(LI, PredEnd.getPrevSlot()))
continue;
MachineBasicBlock::iterator InsertPos =
llvm::findPHICopyInsertPoint(PredMBB, &MBB, Reg);
const MCInstrDesc &MCDesc = TII->get(TargetOpcode::IMPLICIT_DEF);
MachineInstrBuilder ImpDef = BuildMI(*PredMBB, InsertPos,
DebugLoc(), MCDesc, Reg);
SlotIndex DefIdx = LIS->InsertMachineInstrInMaps(*ImpDef);
SlotIndex RegDefIdx = DefIdx.getRegSlot();
for (LiveInterval::SubRange &SR : LI.subranges()) {
VNInfo *SRVNI = SR.getNextValue(RegDefIdx, Allocator);
SR.addSegment(LiveRange::Segment(RegDefIdx, PredEnd, SRVNI));
}
}
}
}
for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
if (!MO.isDef())
continue;
unsigned SubRegIdx = MO.getSubReg();
if (SubRegIdx == 0)
continue;
// After assigning the new vreg we may not have any other sublanes living
// in and out of the instruction anymore. We need to add new dead and
// undef flags in these cases.
if (!MO.isUndef()) {
SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
if (!subRangeLiveAt(LI, Pos))
MO.setIsUndef();
}
if (!MO.isDead()) {
SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent()).getDeadSlot();
if (!subRangeLiveAt(LI, Pos))
MO.setIsDead();
}
}
if (I == 0)
LI.clear();
LIS->constructMainRangeFromSubranges(LI);
}
}
bool RenameIndependentSubregs::runOnMachineFunction(MachineFunction &MF) {
// Skip renaming if liveness of subregister is not tracked.
if (!MF.getSubtarget().enableSubRegLiveness())
return false;
DEBUG(dbgs() << "Renaming independent subregister live ranges in "
<< MF.getName() << '\n');
LIS = &getAnalysis<LiveIntervals>();
MRI = &MF.getRegInfo();
TII = MF.getSubtarget().getInstrInfo();
// Iterate over all vregs. Note that we query getNumVirtRegs() the newly
// created vregs end up with higher numbers but do not need to be visited as
// there can't be any further splitting.
bool Changed = false;
for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; ++I) {
unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
if (!LIS->hasInterval(Reg))
continue;
LiveInterval &LI = LIS->getInterval(Reg);
if (!LI.hasSubRanges())
continue;
Changed |= renameComponents(LI);
}
return Changed;
}

llvm/trunk/lib/CodeGen/TargetPassConfig.cpp

Show First 20 Lines • Show All 769 Lines • ▼ Show 20 Linesvoid TargetPassConfig::addOptimizedRegAlloc(FunctionPass *RegAllocPass) {
// Eventually, we want to run LiveIntervals before PHI elimination. // Eventually, we want to run LiveIntervals before PHI elimination.
if (EarlyLiveIntervals) if (EarlyLiveIntervals)
addPass(&LiveIntervalsID, false); addPass(&LiveIntervalsID, false);
addPass(&TwoAddressInstructionPassID, false); addPass(&TwoAddressInstructionPassID, false);
addPass(&RegisterCoalescerID); addPass(&RegisterCoalescerID);
// The machine scheduler may accidentally create disconnected components
// when moving subregister definitions around, avoid this by splitting them to
// separate vregs before. Splitting can also improve reg. allocation quality.
addPass(&RenameIndependentSubregsID);
// PreRA instruction scheduling. // PreRA instruction scheduling.
addPass(&MachineSchedulerID); addPass(&MachineSchedulerID);
if (RegAllocPass) { if (RegAllocPass) {
// Add the selected register allocation pass. // Add the selected register allocation pass.
addPass(RegAllocPass); addPass(RegAllocPass);
// Allow targets to change the register assignments before rewriting. // Allow targets to change the register assignments before rewriting.
▲ Show 20 Lines • Show All 52 Lines • Show Last 20 Lines

llvm/trunk/test/CodeGen/AMDGPU/rename-independent-subregs.mir

# RUN: llc -march=amdgcn -run-pass rename-independent-subregs -o /dev/null %s 2>&1 | FileCheck %s
--- |
define void @test0() { ret void }
...
---
# In the test below we have two independent def+use pairs of subregister1 which
# can be moved to a new virtual register. The third def of sub1 however is used
# in combination with sub0 and needs to stay with the original vreg.
# CHECK-LABEL: name: test0
# CHECK: S_NOP 0, implicit-def undef %0:sub0
# CHECK: S_NOP 0, implicit-def undef %2:sub1
# CHECK: S_NOP 0, implicit %2:sub1
# CHECK: S_NOP 0, implicit-def undef %1:sub1
# CHECK: S_NOP 0, implicit %1:sub1
# CHECK: S_NOP 0, implicit-def %0:sub1
# CHECK: S_NOP 0, implicit %0
name: test0
isSSA: true
registers:
- { id: 0, class: sreg_128 }
body: |
bb.0:
S_NOP 0, implicit-def undef %0:sub0
S_NOP 0, implicit-def %0:sub1
S_NOP 0, implicit %0:sub1
S_NOP 0, implicit-def %0:sub1
S_NOP 0, implicit %0:sub1
S_NOP 0, implicit-def %0:sub1
S_NOP 0, implicit %0
...