Skip to content

Commit a2b9011

Browse files
committedFeb 27, 2018
Re-enable "[MachineCopyPropagation] Extend pass to do COPY source forwarding"
Re-enable commit r323991 now that r325931 has been committed to make MachineOperand::isRenamable() check more conservative w.r.t. code changes and opt-in on a per-target basis. llvm-svn: 326208
1 parent 3bfa8f0 commit a2b9011

File tree

123 files changed

+847
-576
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

123 files changed

+847
-576
lines changed
 

‎llvm/lib/CodeGen/MachineCopyPropagation.cpp

+206-1
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,35 @@
99
//
1010
// This is an extremely simple MachineInstr-level copy propagation pass.
1111
//
12+
// This pass forwards the source of COPYs to the users of their destinations
13+
// when doing so is legal. For example:
14+
//
15+
// %reg1 = COPY %reg0
16+
// ...
17+
// ... = OP %reg1
18+
//
19+
// If
20+
// - %reg0 has not been clobbered by the time of the use of %reg1
21+
// - the register class constraints are satisfied
22+
// - the COPY def is the only value that reaches OP
23+
// then this pass replaces the above with:
24+
//
25+
// %reg1 = COPY %reg0
26+
// ...
27+
// ... = OP %reg0
28+
//
29+
// This pass also removes some redundant COPYs. For example:
30+
//
31+
// %R1 = COPY %R0
32+
// ... // No clobber of %R1
33+
// %R0 = COPY %R1 <<< Removed
34+
//
35+
// or
36+
//
37+
// %R1 = COPY %R0
38+
// ... // No clobber of %R0
39+
// %R1 = COPY %R0 <<< Removed
40+
//
1241
//===----------------------------------------------------------------------===//
1342

1443
#include "llvm/ADT/DenseMap.h"
@@ -23,11 +52,13 @@
2352
#include "llvm/CodeGen/MachineInstr.h"
2453
#include "llvm/CodeGen/MachineOperand.h"
2554
#include "llvm/CodeGen/MachineRegisterInfo.h"
55+
#include "llvm/CodeGen/TargetInstrInfo.h"
2656
#include "llvm/CodeGen/TargetRegisterInfo.h"
2757
#include "llvm/CodeGen/TargetSubtargetInfo.h"
2858
#include "llvm/MC/MCRegisterInfo.h"
2959
#include "llvm/Pass.h"
3060
#include "llvm/Support/Debug.h"
61+
#include "llvm/Support/DebugCounter.h"
3162
#include "llvm/Support/raw_ostream.h"
3263
#include <cassert>
3364
#include <iterator>
@@ -37,6 +68,9 @@ using namespace llvm;
3768
#define DEBUG_TYPE "machine-cp"
3869

3970
STATISTIC(NumDeletes, "Number of dead copies deleted");
71+
STATISTIC(NumCopyForwards, "Number of copy uses forwarded");
72+
DEBUG_COUNTER(FwdCounter, "machine-cp-fwd",
73+
"Controls which register COPYs are forwarded");
4074

4175
namespace {
4276

@@ -73,6 +107,10 @@ using Reg2MIMap = DenseMap<unsigned, MachineInstr *>;
73107
void ReadRegister(unsigned Reg);
74108
void CopyPropagateBlock(MachineBasicBlock &MBB);
75109
bool eraseIfRedundant(MachineInstr &Copy, unsigned Src, unsigned Def);
110+
void forwardUses(MachineInstr &MI);
111+
bool isForwardableRegClassCopy(const MachineInstr &Copy,
112+
const MachineInstr &UseI, unsigned UseIdx);
113+
bool hasImplicitOverlap(const MachineInstr &MI, const MachineOperand &Use);
76114

77115
/// Candidates for deletion.
78116
SmallSetVector<MachineInstr*, 8> MaybeDeadCopies;
@@ -208,6 +246,152 @@ bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src,
208246
return true;
209247
}
210248

249+
/// Decide whether we should forward the source of \param Copy to its use in
250+
/// \param UseI based on the physical register class constraints of the opcode
251+
/// and avoiding introducing more cross-class COPYs.
252+
bool MachineCopyPropagation::isForwardableRegClassCopy(const MachineInstr &Copy,
253+
const MachineInstr &UseI,
254+
unsigned UseIdx) {
255+
256+
unsigned CopySrcReg = Copy.getOperand(1).getReg();
257+
258+
// If the new register meets the opcode register constraints, then allow
259+
// forwarding.
260+
if (const TargetRegisterClass *URC =
261+
UseI.getRegClassConstraint(UseIdx, TII, TRI))
262+
return URC->contains(CopySrcReg);
263+
264+
if (!UseI.isCopy())
265+
return false;
266+
267+
/// COPYs don't have register class constraints, so if the user instruction
268+
/// is a COPY, we just try to avoid introducing additional cross-class
269+
/// COPYs. For example:
270+
///
271+
/// RegClassA = COPY RegClassB // Copy parameter
272+
/// ...
273+
/// RegClassB = COPY RegClassA // UseI parameter
274+
///
275+
/// which after forwarding becomes
276+
///
277+
/// RegClassA = COPY RegClassB
278+
/// ...
279+
/// RegClassB = COPY RegClassB
280+
///
281+
/// so we have reduced the number of cross-class COPYs and potentially
282+
/// introduced a nop COPY that can be removed.
283+
const TargetRegisterClass *UseDstRC =
284+
TRI->getMinimalPhysRegClass(UseI.getOperand(0).getReg());
285+
286+
const TargetRegisterClass *SuperRC = UseDstRC;
287+
for (TargetRegisterClass::sc_iterator SuperRCI = UseDstRC->getSuperClasses();
288+
SuperRC; SuperRC = *SuperRCI++)
289+
if (SuperRC->contains(CopySrcReg))
290+
return true;
291+
292+
return false;
293+
}
294+
295+
/// Check that \p MI does not have implicit uses that overlap with it's \p Use
296+
/// operand (the register being replaced), since these can sometimes be
297+
/// implicitly tied to other operands. For example, on AMDGPU:
298+
///
299+
/// V_MOVRELS_B32_e32 %VGPR2, %M0<imp-use>, %EXEC<imp-use>, %VGPR2_VGPR3_VGPR4_VGPR5<imp-use>
300+
///
301+
/// the %VGPR2 is implicitly tied to the larger reg operand, but we have no
302+
/// way of knowing we need to update the latter when updating the former.
303+
bool MachineCopyPropagation::hasImplicitOverlap(const MachineInstr &MI,
304+
const MachineOperand &Use) {
305+
for (const MachineOperand &MIUse : MI.uses())
306+
if (&MIUse != &Use && MIUse.isReg() && MIUse.isImplicit() &&
307+
MIUse.isUse() && TRI->regsOverlap(Use.getReg(), MIUse.getReg()))
308+
return true;
309+
310+
return false;
311+
}
312+
313+
/// Look for available copies whose destination register is used by \p MI and
314+
/// replace the use in \p MI with the copy's source register.
315+
void MachineCopyPropagation::forwardUses(MachineInstr &MI) {
316+
if (AvailCopyMap.empty())
317+
return;
318+
319+
// Look for non-tied explicit vreg uses that have an active COPY
320+
// instruction that defines the physical register allocated to them.
321+
// Replace the vreg with the source of the active COPY.
322+
for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx < OpEnd;
323+
++OpIdx) {
324+
MachineOperand &MOUse = MI.getOperand(OpIdx);
325+
// Don't forward into undef use operands since doing so can cause problems
326+
// with the machine verifier, since it doesn't treat undef reads as reads,
327+
// so we can end up with a live range that ends on an undef read, leading to
328+
// an error that the live range doesn't end on a read of the live range
329+
// register.
330+
if (!MOUse.isReg() || MOUse.isTied() || MOUse.isUndef() || MOUse.isDef() ||
331+
MOUse.isImplicit())
332+
continue;
333+
334+
if (!MOUse.getReg())
335+
continue;
336+
337+
// Check that the register is marked 'renamable' so we know it is safe to
338+
// rename it without violating any constraints that aren't expressed in the
339+
// IR (e.g. ABI or opcode requirements).
340+
if (!MOUse.isRenamable())
341+
continue;
342+
343+
auto CI = AvailCopyMap.find(MOUse.getReg());
344+
if (CI == AvailCopyMap.end())
345+
continue;
346+
347+
MachineInstr &Copy = *CI->second;
348+
unsigned CopyDstReg = Copy.getOperand(0).getReg();
349+
const MachineOperand &CopySrc = Copy.getOperand(1);
350+
unsigned CopySrcReg = CopySrc.getReg();
351+
352+
// FIXME: Don't handle partial uses of wider COPYs yet.
353+
if (MOUse.getReg() != CopyDstReg) {
354+
DEBUG(dbgs() << "MCP: FIXME! Not forwarding COPY to sub-register use:\n "
355+
<< MI);
356+
continue;
357+
}
358+
359+
// Don't forward COPYs of reserved regs unless they are constant.
360+
if (MRI->isReserved(CopySrcReg) && !MRI->isConstantPhysReg(CopySrcReg))
361+
continue;
362+
363+
if (!isForwardableRegClassCopy(Copy, MI, OpIdx))
364+
continue;
365+
366+
if (hasImplicitOverlap(MI, MOUse))
367+
continue;
368+
369+
if (!DebugCounter::shouldExecute(FwdCounter)) {
370+
DEBUG(dbgs() << "MCP: Skipping forwarding due to debug counter:\n "
371+
<< MI);
372+
continue;
373+
}
374+
375+
DEBUG(dbgs() << "MCP: Replacing " << printReg(MOUse.getReg(), TRI)
376+
<< "\n with " << printReg(CopySrcReg, TRI) << "\n in "
377+
<< MI << " from " << Copy);
378+
379+
MOUse.setReg(CopySrcReg);
380+
if (!CopySrc.isRenamable())
381+
MOUse.setIsRenamable(false);
382+
383+
DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n");
384+
385+
// Clear kill markers that may have been invalidated.
386+
for (MachineInstr &KMI :
387+
make_range(Copy.getIterator(), std::next(MI.getIterator())))
388+
KMI.clearRegisterKills(CopySrcReg, TRI);
389+
390+
++NumCopyForwards;
391+
Changed = true;
392+
}
393+
}
394+
211395
void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
212396
DEBUG(dbgs() << "MCP: CopyPropagateBlock " << MBB.getName() << "\n");
213397

@@ -241,6 +425,11 @@ void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
241425
if (eraseIfRedundant(*MI, Def, Src) || eraseIfRedundant(*MI, Src, Def))
242426
continue;
243427

428+
forwardUses(*MI);
429+
430+
// Src may have been changed by forwardUses()
431+
Src = MI->getOperand(1).getReg();
432+
244433
// If Src is defined by a previous copy, the previous copy cannot be
245434
// eliminated.
246435
ReadRegister(Src);
@@ -292,6 +481,20 @@ void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
292481
continue;
293482
}
294483

484+
// Clobber any earlyclobber regs first.
485+
for (const MachineOperand &MO : MI->operands())
486+
if (MO.isReg() && MO.isEarlyClobber()) {
487+
unsigned Reg = MO.getReg();
488+
// If we have a tied earlyclobber, that means it is also read by this
489+
// instruction, so we need to make sure we don't remove it as dead
490+
// later.
491+
if (MO.isTied())
492+
ReadRegister(Reg);
493+
ClobberRegister(Reg);
494+
}
495+
496+
forwardUses(*MI);
497+
295498
// Not a copy.
296499
SmallVector<unsigned, 2> Defs;
297500
const MachineOperand *RegMask = nullptr;
@@ -307,7 +510,7 @@ void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
307510
assert(!TargetRegisterInfo::isVirtualRegister(Reg) &&
308511
"MachineCopyPropagation should be run after register allocation!");
309512

310-
if (MO.isDef()) {
513+
if (MO.isDef() && !MO.isEarlyClobber()) {
311514
Defs.push_back(Reg);
312515
continue;
313516
} else if (MO.readsReg())
@@ -364,6 +567,8 @@ void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
364567
// since we don't want to trust live-in lists.
365568
if (MBB.succ_empty()) {
366569
for (MachineInstr *MaybeDead : MaybeDeadCopies) {
570+
DEBUG(dbgs() << "MCP: Removing copy due to no live-out succ: ";
571+
MaybeDead->dump());
367572
assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg()));
368573
MaybeDead->eraseFromParent();
369574
Changed = true;

‎llvm/lib/CodeGen/TargetPassConfig.cpp

+4
Original file line numberDiff line numberDiff line change
@@ -1083,6 +1083,10 @@ void TargetPassConfig::addOptimizedRegAlloc(FunctionPass *RegAllocPass) {
10831083
// kill markers.
10841084
addPass(&StackSlotColoringID);
10851085

1086+
// Copy propagate to forward register uses and try to eliminate COPYs that
1087+
// were not coalesced.
1088+
addPass(&MachineCopyPropagationID);
1089+
10861090
// Run post-ra machine LICM to hoist reloads / remats.
10871091
//
10881092
// FIXME: can this move into MachineLateOptimization?

0 commit comments

Comments
 (0)
Please sign in to comment.