This is an archive of the discontinued LLVM Phabricator instance.

[MachineCopyPropagation] Extend MCP to do trivial copy backward propagation
ClosedPublic

Authored by lkail on Sep 19 2019, 10:21 PM.

Details

Summary

This patch mainly do such transformation

$R0 = OP ...
... // No read/clobber of $R0 and $R1
$R1 = COPY $R0 // $R0 is killed

Replace $R0 with $R1 and remove the COPY, we have

$R1 = OP ...

This transformation can also expose more opportunities for existing copy elimination in MCP.

Diff Detail

Event Timeline

lkail created this revision.Sep 19 2019, 10:21 PM
lkail edited the summary of this revision. (Show Details)Sep 19 2019, 10:22 PM
lkail edited the summary of this revision. (Show Details)
lkail edited the summary of this revision. (Show Details)
lkail edited reviewers, added: efriedma; removed: eli.friedman.Sep 19 2019, 10:26 PM
lkail removed subscribers: nemanjai, jsji.
lkail added a comment.Sep 29 2019, 2:05 AM

Gentle ping

qcolombet requested changes to this revision.Oct 28 2019, 12:56 PM
qcolombet added inline comments.
llvm/lib/CodeGen/MachineCopyPropagation.cpp
328

Hard coding 0, seems artificial to me.
Could we find which operand defines Copy.getOperand(1).getReg() instead?

332

I find this condition hard to read.
Could you break it into smaller conditions?

E.g.,

if (!SrcOp.isRenamable())
  return false;
if (SrcOp.isImplicit())
  return false;

and so on.

365

Could you build this information as we iterate into the basic block?
I am afraid the compile time cost of this loop to be fairly large otherwise, since we are going to traverse all the instructions between two instructions again and again.

This revision now requires changes to proceed.Oct 28 2019, 12:56 PM
lkail added inline comments.Oct 30 2019, 12:54 AM
llvm/lib/CodeGen/MachineCopyPropagation.cpp
365

I find that it might be non-trivial to track information that help perform backward copy propagation in current forward iteration. Would it be a proper option that separating current main loop into two parts, one performs forward copy propagation, the other performs backward copy propagation? i.e.

for (MachineBasicBlock &MBB : MF) {
  ForwardCopyPropagateBlock(MBB); // Current CopyPropagateBlock
  BackwardCopyPropagateBlock(MBB);
}

In BackwardCopyPropagateBlock, iterate instructions reversely. Cons is increasing constant complexity.

qcolombet added inline comments.Oct 31 2019, 10:25 AM
llvm/lib/CodeGen/MachineCopyPropagation.cpp
365

That would work.
The nice thing about this approach is that we could easily stage the new optimization:

for (MachineBasicBlock &MBB : MF) {
  ForwardCopyPropagateBlock(MBB); // Current CopyPropagateBlock
  if (EnableBackwardCP)
    BackwardCopyPropagateBlock(MBB);
}
lkail planned changes to this revision.Oct 31 2019, 8:26 PM
lkail updated this revision to Diff 229460.Nov 15 2019, 12:52 AM
lkail added a reviewer: shiva0217.

Address @qcolombet's comment. @qcolombet I have no idea which is preferable to pass EnableBackwardCP option, target hook or cl::opt?

The RISC-V test changes look good. (I do not intend to review the optimisation implementation or other backend test changes).

lkail updated this revision to Diff 229494.Nov 15 2019, 3:29 AM

Introduce CopyTracker::invalidateRegister, original markRegUnavailable and clobberRegister are not appropriate for backward copy propagation.

lkail updated this revision to Diff 229498.Nov 15 2019, 3:41 AM
lkail updated this revision to Diff 229501.Nov 15 2019, 3:52 AM
lkail updated this revision to Diff 229504.Nov 15 2019, 4:14 AM
lkail updated this revision to Diff 229509.Nov 15 2019, 4:48 AM
lkail marked an inline comment as done.Nov 15 2019, 3:30 PM
lkail updated this revision to Diff 229975.Nov 18 2019, 10:46 PM

Add test case involving RegMask.

lkail marked an inline comment as done.Nov 19 2019, 1:20 AM
lkail marked 3 inline comments as done.Nov 22 2019, 8:38 PM
lkail planned changes to this revision.Nov 28 2019, 6:13 AM

Rebased and get broken tests, I'll investigate it and change this patch.

lkail updated this revision to Diff 231488.Nov 29 2019, 1:03 AM

Rebased and fixed broken tests. Ready to be reviewed.

lkail marked an inline comment as not done.Nov 29 2019, 1:04 AM

The RISC-V test changes look good. (I do not intend to review the optimisation implementation or other backend test changes).

Thanks @lenary .

lkail updated this revision to Diff 231490.Nov 29 2019, 1:10 AM
qcolombet added inline comments.Dec 2 2019, 4:47 PM
llvm/lib/CodeGen/MachineCopyPropagation.cpp
196

It seems to me that we could just reuse directly findAvailCopy and thus eliminate findCopyDefViaUnit.
The only difference would be the that we use a different iterator for the. forward and the backward case.

qcolombet added inline comments.Dec 2 2019, 5:24 PM
llvm/lib/CodeGen/MachineCopyPropagation.cpp
196

Spoke too soon. I see the difference in findCopyDefViaUnit:
We check that the source of the copy is used only once, then that the reg unit defined by this copy is available.

I still need to go through the rest of that patch, but I would expect that we could do more code reuse if we were to drop from the list of available copies anything that is read or clobbered between the use and the definition. I.e., the case were more than one copy use the same source (which is basically what DefRegs.size() != 1 represents) wouldn't be kept in the Copies variable to begin with.

Anyway, not something that must be fixed here. We can refactor later.
Let me go through the whole patch first.

lkail marked an inline comment as done.Dec 2 2019, 6:37 PM
lkail added inline comments.
llvm/lib/CodeGen/MachineCopyPropagation.cpp
196

I agree with that there are still some redundancies in current code. I think findAvailBackwardCopy can be combined into findAvailCopy with an additional flag to indicate if its forward or backward and reverseIterator in findAvailBackwardCopy can be replaced with Iterator.

lkail marked an inline comment as not done.Dec 2 2019, 6:38 PM
lkail updated this revision to Diff 231811.Dec 2 2019, 6:57 PM

Rebased and add comment for invalidateRegister.

qcolombet accepted this revision.Dec 3 2019, 8:56 AM

LGTM.
One nit below.

llvm/lib/CodeGen/MachineCopyPropagation.cpp
752

Should this be an assert?

Put differently, when can we find a backward copy for MODef.getReg() when the source is not MODef.getReg()?

This revision is now accepted and ready to land.Dec 3 2019, 8:56 AM
lkail marked an inline comment as done.Dec 3 2019, 6:35 PM
lkail added inline comments.
llvm/lib/CodeGen/MachineCopyPropagation.cpp
752

Yes, you are right. I supposed following code might not be handled correctly(to illustrate, might not be perfect)

name: foo
alignment:       2
tracksRegLiveness: true
frameInfo:
  maxAlignment:    16
  maxCallFrameSize: 0
stack:
  - { id: 0, type: spill-slot, size: 16, alignment: 16 }
body: |
  bb.0.entry:
    liveins: $r0, $r1
    renamable $q0 = MVE_VLDRWU32 renamable $r0, 80, 0, $noreg :: (load 16 from %stack.0, align 4)
    renamable $s4 = COPY renamable killed $s0
    MVE_VSTRWU32 killed renamable $q1, killed renamable $r1, 0, 0, $noreg :: (store 16 into %stack.0, align 128)
    tBX_RET 14, $noreg

I thought $s0 might be propagated(thought it won't pass isBackwardPropagatableRegClassCopy later). However, in findAvailBackwardCopy we have already checked !TRI.isSubRegisterEq(AvailCopy->getOperand(1).getReg(), Reg)), thus $s0 won't be propagated.

lkail added a comment.Dec 3 2019, 6:36 PM
This comment was removed by lkail.
This revision was automatically updated to reflect the committed changes.