9
9
//
10
10
// This is an extremely simple MachineInstr-level copy propagation pass.
11
11
//
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
+ //
12
41
// ===----------------------------------------------------------------------===//
13
42
14
43
#include " llvm/ADT/DenseMap.h"
23
52
#include " llvm/CodeGen/MachineInstr.h"
24
53
#include " llvm/CodeGen/MachineOperand.h"
25
54
#include " llvm/CodeGen/MachineRegisterInfo.h"
55
+ #include " llvm/CodeGen/TargetInstrInfo.h"
26
56
#include " llvm/CodeGen/TargetRegisterInfo.h"
27
57
#include " llvm/CodeGen/TargetSubtargetInfo.h"
28
58
#include " llvm/MC/MCRegisterInfo.h"
29
59
#include " llvm/Pass.h"
30
60
#include " llvm/Support/Debug.h"
61
+ #include " llvm/Support/DebugCounter.h"
31
62
#include " llvm/Support/raw_ostream.h"
32
63
#include < cassert>
33
64
#include < iterator>
@@ -37,6 +68,9 @@ using namespace llvm;
37
68
#define DEBUG_TYPE " machine-cp"
38
69
39
70
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" );
40
74
41
75
namespace {
42
76
@@ -73,6 +107,10 @@ using Reg2MIMap = DenseMap<unsigned, MachineInstr *>;
73
107
void ReadRegister (unsigned Reg);
74
108
void CopyPropagateBlock (MachineBasicBlock &MBB);
75
109
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);
76
114
77
115
// / Candidates for deletion.
78
116
SmallSetVector<MachineInstr*, 8 > MaybeDeadCopies;
@@ -208,6 +246,152 @@ bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src,
208
246
return true ;
209
247
}
210
248
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
+
211
395
void MachineCopyPropagation::CopyPropagateBlock (MachineBasicBlock &MBB) {
212
396
DEBUG (dbgs () << " MCP: CopyPropagateBlock " << MBB.getName () << " \n " );
213
397
@@ -241,6 +425,11 @@ void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
241
425
if (eraseIfRedundant (*MI, Def, Src) || eraseIfRedundant (*MI, Src, Def))
242
426
continue ;
243
427
428
+ forwardUses (*MI);
429
+
430
+ // Src may have been changed by forwardUses()
431
+ Src = MI->getOperand (1 ).getReg ();
432
+
244
433
// If Src is defined by a previous copy, the previous copy cannot be
245
434
// eliminated.
246
435
ReadRegister (Src);
@@ -292,6 +481,20 @@ void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
292
481
continue ;
293
482
}
294
483
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
+
295
498
// Not a copy.
296
499
SmallVector<unsigned , 2 > Defs;
297
500
const MachineOperand *RegMask = nullptr ;
@@ -307,7 +510,7 @@ void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
307
510
assert (!TargetRegisterInfo::isVirtualRegister (Reg) &&
308
511
" MachineCopyPropagation should be run after register allocation!" );
309
512
310
- if (MO.isDef ()) {
513
+ if (MO.isDef () && !MO. isEarlyClobber () ) {
311
514
Defs.push_back (Reg);
312
515
continue ;
313
516
} else if (MO.readsReg ())
@@ -364,6 +567,8 @@ void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
364
567
// since we don't want to trust live-in lists.
365
568
if (MBB.succ_empty ()) {
366
569
for (MachineInstr *MaybeDead : MaybeDeadCopies) {
570
+ DEBUG (dbgs () << " MCP: Removing copy due to no live-out succ: " ;
571
+ MaybeDead->dump ());
367
572
assert (!MRI->isReserved (MaybeDead->getOperand (0 ).getReg ()));
368
573
MaybeDead->eraseFromParent ();
369
574
Changed = true ;
0 commit comments