Skip to content

Commit 91f95f0

Browse files
MatzeBMatzeB
committedAug 18, 2016
CodeGen: Add/Factor out LiveRegUnits class; NFCI
This is a set of register units intended to track register liveness, it is similar in spirit to LivePhysRegs. You can also think of this as the liveness tracking parts of the RegisterScavenger factored out into an own class. This was proposed in http://llvm.org/PR27609 Differential Revision: http://reviews.llvm.org/D21916 llvm-svn: 279171
1 parent a1c7653 commit 91f95f0

File tree

5 files changed

+229
-68
lines changed

5 files changed

+229
-68
lines changed
 

‎llvm/include/llvm/CodeGen/LiveRegUnits.h

+116
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,116 @@
1+
//===- llvm/CodeGen/LiveRegUnits.h - Register Unit Set ----------*- C++ -*-===//
2+
//
3+
// The LLVM Compiler Infrastructure
4+
//
5+
// This file is distributed under the University of Illinois Open Source
6+
// License. See LICENSE.TXT for details.
7+
//
8+
//===----------------------------------------------------------------------===//
9+
//
10+
/// \file
11+
/// A set of register units. It is intended for register liveness tracking.
12+
//
13+
//===----------------------------------------------------------------------===//
14+
15+
#ifndef LLVM_CODEGEN_LIVEREGUNITS_H
16+
#define LLVM_CODEGEN_LIVEREGUNITS_H
17+
18+
#include "llvm/ADT/BitVector.h"
19+
#include "llvm/Target/TargetRegisterInfo.h"
20+
21+
namespace llvm {
22+
23+
class MachineInstr;
24+
class MachineBasicBlock;
25+
26+
/// A set of register units used to track register liveness.
27+
class LiveRegUnits {
28+
const TargetRegisterInfo *TRI;
29+
BitVector Units;
30+
31+
public:
32+
/// Constructs a new empty LiveRegUnits set.
33+
LiveRegUnits() : TRI(nullptr) {}
34+
35+
/// Constructs and initialize an empty LiveRegUnits set.
36+
LiveRegUnits(const TargetRegisterInfo &TRI) {
37+
init(TRI);
38+
}
39+
40+
/// Initialize and clear the set.
41+
void init(const TargetRegisterInfo &TRI) {
42+
this->TRI = &TRI;
43+
Units.reset();
44+
Units.resize(TRI.getNumRegUnits());
45+
}
46+
47+
/// Clears the set.
48+
void clear() { Units.reset(); }
49+
50+
/// Returns true if the set is empty.
51+
bool empty() const { return Units.empty(); }
52+
53+
/// Adds register units covered by physical register \p Reg.
54+
void addReg(unsigned Reg) {
55+
for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit)
56+
Units.set(*Unit);
57+
}
58+
59+
/// \brief Adds register units covered by physical register \p Reg that are
60+
/// part of the lanemask \p Mask.
61+
void addRegMasked(unsigned Reg, LaneBitmask Mask) {
62+
for (MCRegUnitMaskIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) {
63+
LaneBitmask UnitMask = (*Unit).second;
64+
if (UnitMask == 0 || (UnitMask & Mask) != 0)
65+
Units.set((*Unit).first);
66+
}
67+
}
68+
69+
/// Removes all register units covered by physical register \p Reg.
70+
void removeReg(unsigned Reg) {
71+
for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit)
72+
Units.reset(*Unit);
73+
}
74+
75+
/// Removes register units not preserved by the regmask \p RegMask.
76+
/// The regmask has the same format as the one in the RegMask machine operand.
77+
void removeRegsNotPreserved(const uint32_t *RegMask);
78+
79+
/// Returns true if no part of physical register \p Reg is live.
80+
bool available(unsigned Reg) const {
81+
for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) {
82+
if (Units.test(*Unit))
83+
return false;
84+
}
85+
return true;
86+
}
87+
88+
/// Updates liveness when stepping backwards over the instruction \p MI.
89+
void stepBackward(const MachineInstr &MI);
90+
91+
/// Adds registers living out of block \p MBB.
92+
/// Live out registers are the union of the live-in registers of the successor
93+
/// blocks and pristine registers. Live out registers of the end block are the
94+
/// callee saved registers.
95+
void addLiveOuts(const MachineBasicBlock &MBB);
96+
97+
/// Adds registers living into block \p MBB.
98+
void addLiveIns(const MachineBasicBlock &MBB);
99+
100+
/// Adds all register units marked in the bitvector \p RegUnits.
101+
void addUnits(const BitVector &RegUnits) {
102+
Units |= RegUnits;
103+
}
104+
/// Removes all register units marked in the bitvector \p RegUnits.
105+
void removeUnits(const BitVector &RegUnits) {
106+
Units.reset(RegUnits);
107+
}
108+
/// Return the internal bitvector representation of the set.
109+
const BitVector &getBitVector() const {
110+
return Units;
111+
}
112+
};
113+
114+
} // namespace llvm
115+
116+
#endif

‎llvm/include/llvm/CodeGen/RegisterScavenging.h

+6-8
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@
1919
#define LLVM_CODEGEN_REGISTERSCAVENGING_H
2020

2121
#include "llvm/ADT/BitVector.h"
22+
#include "llvm/CodeGen/LiveRegUnits.h"
2223
#include "llvm/CodeGen/MachineBasicBlock.h"
2324
#include "llvm/CodeGen/MachineRegisterInfo.h"
2425

@@ -58,10 +59,7 @@ class RegScavenger {
5859
/// A vector of information on scavenged registers.
5960
SmallVector<ScavengedInfo, 2> Scavenged;
6061

61-
/// The current state of each reg unit immediately before MBBI.
62-
/// One bit per register unit. If bit is not set it means any
63-
/// register containing that register unit is currently being used.
64-
BitVector RegUnitsAvailable;
62+
LiveRegUnits LiveUnits;
6563

6664
// These BitVectors are only used internally to forward(). They are members
6765
// to avoid frequent reallocations.
@@ -183,11 +181,11 @@ class RegScavenger {
183181

184182
/// setUsed / setUnused - Mark the state of one or a number of register units.
185183
///
186-
void setUsed(BitVector &RegUnits) {
187-
RegUnitsAvailable.reset(RegUnits);
184+
void setUsed(const BitVector &RegUnits) {
185+
LiveUnits.addUnits(RegUnits);
188186
}
189-
void setUnused(BitVector &RegUnits) {
190-
RegUnitsAvailable |= RegUnits;
187+
void setUnused(const BitVector &RegUnits) {
188+
LiveUnits.removeUnits(RegUnits);
191189
}
192190

193191
/// Processes the current instruction and fill the KillRegUnits and

‎llvm/lib/CodeGen/CMakeLists.txt

+1
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,7 @@ add_llvm_library(LLVMCodeGen
4444
LiveRangeCalc.cpp
4545
LiveRangeEdit.cpp
4646
LiveRegMatrix.cpp
47+
LiveRegUnits.cpp
4748
LiveStackAnalysis.cpp
4849
LiveVariables.cpp
4950
LLVMTargetMachine.cpp

‎llvm/lib/CodeGen/LiveRegUnits.cpp

+97
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
//===--- LiveRegUnits.cpp - Register Unit Set -----------------------------===//
2+
//
3+
// The LLVM Compiler Infrastructure
4+
//
5+
// This file is distributed under the University of Illinois Open Source
6+
// License. See LICENSE.TXT for details.
7+
//
8+
//===----------------------------------------------------------------------===//
9+
//
10+
/// \file This file imlements the LiveRegUnits set.
11+
//
12+
//===----------------------------------------------------------------------===//
13+
14+
#include "llvm/CodeGen/LiveRegUnits.h"
15+
#include "llvm/CodeGen/MachineFrameInfo.h"
16+
#include "llvm/CodeGen/MachineFunction.h"
17+
#include "llvm/CodeGen/MachineInstrBundle.h"
18+
using namespace llvm;
19+
20+
void LiveRegUnits::removeRegsNotPreserved(const uint32_t *RegMask) {
21+
for (unsigned U = 0, E = TRI->getNumRegUnits(); U != E; ++U) {
22+
for (MCRegUnitRootIterator RootReg(U, TRI); RootReg.isValid(); ++RootReg) {
23+
if (MachineOperand::clobbersPhysReg(RegMask, *RootReg))
24+
Units.reset(U);
25+
}
26+
}
27+
}
28+
29+
void LiveRegUnits::stepBackward(const MachineInstr &MI) {
30+
// Remove defined registers and regmask kills from the set.
31+
for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
32+
if (O->isReg()) {
33+
if (!O->isDef())
34+
continue;
35+
unsigned Reg = O->getReg();
36+
if (!TargetRegisterInfo::isPhysicalRegister(Reg))
37+
continue;
38+
removeReg(Reg);
39+
} else if (O->isRegMask())
40+
removeRegsNotPreserved(O->getRegMask());
41+
}
42+
43+
// Add uses to the set.
44+
for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
45+
if (!O->isReg() || !O->readsReg())
46+
continue;
47+
unsigned Reg = O->getReg();
48+
if (!TargetRegisterInfo::isPhysicalRegister(Reg))
49+
continue;
50+
addReg(Reg);
51+
}
52+
}
53+
54+
/// Add live-in registers of basic block \p MBB to \p LiveUnits.
55+
static void addLiveIns(LiveRegUnits &LiveUnits, const MachineBasicBlock &MBB) {
56+
for (const auto &LI : MBB.liveins())
57+
LiveUnits.addRegMasked(LI.PhysReg, LI.LaneMask);
58+
}
59+
60+
static void addLiveOuts(LiveRegUnits &LiveUnits, const MachineBasicBlock &MBB) {
61+
// To get the live-outs we simply merge the live-ins of all successors.
62+
for (const MachineBasicBlock *Succ : MBB.successors())
63+
addLiveIns(LiveUnits, *Succ);
64+
}
65+
66+
/// Add pristine registers to the given \p LiveUnits. This function removes
67+
/// actually saved callee save registers when \p InPrologueEpilogue is false.
68+
static void removeSavedRegs(LiveRegUnits &LiveUnits, const MachineFunction &MF,
69+
const MachineFrameInfo &MFI,
70+
const TargetRegisterInfo &TRI) {
71+
for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
72+
LiveUnits.removeReg(Info.getReg());
73+
}
74+
75+
void LiveRegUnits::addLiveOuts(const MachineBasicBlock &MBB) {
76+
const MachineFunction &MF = *MBB.getParent();
77+
const MachineFrameInfo &MFI = MF.getFrameInfo();
78+
if (MFI.isCalleeSavedInfoValid()) {
79+
for (const MCPhysReg *I = TRI->getCalleeSavedRegs(&MF); *I; ++I)
80+
addReg(*I);
81+
if (!MBB.isReturnBlock())
82+
removeSavedRegs(*this, MF, MFI, *TRI);
83+
}
84+
::addLiveOuts(*this, MBB);
85+
}
86+
87+
void LiveRegUnits::addLiveIns(const MachineBasicBlock &MBB) {
88+
const MachineFunction &MF = *MBB.getParent();
89+
const MachineFrameInfo &MFI = MF.getFrameInfo();
90+
if (MFI.isCalleeSavedInfoValid()) {
91+
for (const MCPhysReg *I = TRI->getCalleeSavedRegs(&MF); *I; ++I)
92+
addReg(*I);
93+
if (&MBB != &MF.front())
94+
removeSavedRegs(*this, MF, MFI, *TRI);
95+
}
96+
::addLiveIns(*this, MBB);
97+
}

‎llvm/lib/CodeGen/RegisterScavenging.cpp

+9-60
Original file line numberDiff line numberDiff line change
@@ -32,18 +32,15 @@ using namespace llvm;
3232
#define DEBUG_TYPE "reg-scavenging"
3333

3434
void RegScavenger::setRegUsed(unsigned Reg, LaneBitmask LaneMask) {
35-
for (MCRegUnitMaskIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) {
36-
LaneBitmask UnitMask = (*RUI).second;
37-
if (UnitMask == 0 || (LaneMask & UnitMask) != 0)
38-
RegUnitsAvailable.reset((*RUI).first);
39-
}
35+
LiveUnits.addRegMasked(Reg, LaneMask);
4036
}
4137

4238
void RegScavenger::init(MachineBasicBlock &MBB) {
4339
MachineFunction &MF = *MBB.getParent();
4440
TII = MF.getSubtarget().getInstrInfo();
4541
TRI = MF.getSubtarget().getRegisterInfo();
4642
MRI = &MF.getRegInfo();
43+
LiveUnits.init(*TRI);
4744

4845
assert((NumRegUnits == 0 || NumRegUnits == TRI->getNumRegUnits()) &&
4946
"Target changed?");
@@ -56,7 +53,6 @@ void RegScavenger::init(MachineBasicBlock &MBB) {
5653
// Self-initialize.
5754
if (!this->MBB) {
5855
NumRegUnits = TRI->getNumRegUnits();
59-
RegUnitsAvailable.resize(NumRegUnits);
6056
KillRegUnits.resize(NumRegUnits);
6157
DefRegUnits.resize(NumRegUnits);
6258
TmpRegUnits.resize(NumRegUnits);
@@ -69,32 +65,17 @@ void RegScavenger::init(MachineBasicBlock &MBB) {
6965
I->Restore = nullptr;
7066
}
7167

72-
// All register units start out unused.
73-
RegUnitsAvailable.set();
74-
75-
// Pristine CSRs are not available.
76-
BitVector PR = MF.getFrameInfo().getPristineRegs(MF);
77-
for (int I = PR.find_first(); I>0; I = PR.find_next(I))
78-
setRegUsed(I);
79-
8068
Tracking = false;
8169
}
8270

83-
void RegScavenger::setLiveInsUsed(const MachineBasicBlock &MBB) {
84-
for (const auto &LI : MBB.liveins())
85-
setRegUsed(LI.PhysReg, LI.LaneMask);
86-
}
87-
8871
void RegScavenger::enterBasicBlock(MachineBasicBlock &MBB) {
8972
init(MBB);
90-
setLiveInsUsed(MBB);
73+
LiveUnits.addLiveIns(MBB);
9174
}
9275

9376
void RegScavenger::enterBasicBlockEnd(MachineBasicBlock &MBB) {
9477
init(MBB);
95-
// Merge live-ins of successors to get live-outs.
96-
for (const MachineBasicBlock *Succ : MBB.successors())
97-
setLiveInsUsed(*Succ);
78+
LiveUnits.addLiveOuts(MBB);
9879

9980
// Move internal iterator at the last instruction of the block.
10081
if (MBB.begin() != MBB.end()) {
@@ -268,36 +249,7 @@ void RegScavenger::backward() {
268249
assert(Tracking && "Must be tracking to determine kills and defs");
269250

270251
const MachineInstr &MI = *MBBI;
271-
// Defined or clobbered registers are available now.
272-
for (const MachineOperand &MO : MI.operands()) {
273-
if (MO.isRegMask()) {
274-
for (unsigned RU = 0, RUEnd = TRI->getNumRegUnits(); RU != RUEnd;
275-
++RU) {
276-
for (MCRegUnitRootIterator RURI(RU, TRI); RURI.isValid(); ++RURI) {
277-
if (MO.clobbersPhysReg(*RURI)) {
278-
RegUnitsAvailable.set(RU);
279-
break;
280-
}
281-
}
282-
}
283-
} else if (MO.isReg() && MO.isDef()) {
284-
unsigned Reg = MO.getReg();
285-
if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) ||
286-
isReserved(Reg))
287-
continue;
288-
addRegUnits(RegUnitsAvailable, Reg);
289-
}
290-
}
291-
// Mark read registers as unavailable.
292-
for (const MachineOperand &MO : MI.uses()) {
293-
if (MO.isReg() && MO.readsReg()) {
294-
unsigned Reg = MO.getReg();
295-
if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) ||
296-
isReserved(Reg))
297-
continue;
298-
removeRegUnits(RegUnitsAvailable, Reg);
299-
}
300-
}
252+
LiveUnits.stepBackward(MI);
301253

302254
// Expire scavenge spill frameindex uses.
303255
for (ScavengedInfo &I : Scavenged) {
@@ -315,12 +267,9 @@ void RegScavenger::backward() {
315267
}
316268

317269
bool RegScavenger::isRegUsed(unsigned Reg, bool includeReserved) const {
318-
if (includeReserved && isReserved(Reg))
319-
return true;
320-
for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
321-
if (!RegUnitsAvailable.test(*RUI))
322-
return true;
323-
return false;
270+
if (isReserved(Reg))
271+
return includeReserved;
272+
return !LiveUnits.available(Reg);
324273
}
325274

326275
unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const {
@@ -621,7 +570,7 @@ unsigned RegScavenger::scavengeRegisterBackwards(const TargetRegisterClass &RC,
621570
MachineBasicBlock::iterator SpillBefore = P.second;
622571
ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillBefore, ReloadBefore);
623572
Scavenged.Restore = &*std::prev(SpillBefore);
624-
addRegUnits(RegUnitsAvailable, Reg);
573+
LiveUnits.removeReg(Reg);
625574
DEBUG(dbgs() << "Scavenged register with spill: " << PrintReg(Reg, TRI)
626575
<< " until " << *SpillBefore);
627576
} else {

0 commit comments

Comments
 (0)
Please sign in to comment.