[AMDGPU] Add MachineDCE pass after RenameIndependentSubregs

[rampitec]

Summary

Detect dead lanes can create some dead defs. Then RenameIndependentSubregs
will break a REG_SEQUENCE which may use these dead defs. At this point
a dead instruction can be removed but we do not run a DCE anymore.

MachineDCE was only running before live variable analysis. The patch
adds a mean to preserve LiveIntervals and SlotIndexes in case it works
past this.

[arsenm]

I feel like we just keep spamming DCE runs to solve issues. Is there some reason it's difficult for RenameIndependentSubregs to clean up after itself?

[arsenm]

In D59626#1438255, @arsenm wrote:

I feel like we just keep spamming DCE runs to solve issues. Is there some reason it's difficult for RenameIndependentSubregs to clean up after itself?

Also, I think making more passes to have to care about LiveIntervals should generally be avoided

[rampitec]

In D59626#1438258, @arsenm wrote:

In D59626#1438255, @arsenm wrote:

I feel like we just keep spamming DCE runs to solve issues. Is there some reason it's difficult for RenameIndependentSubregs to clean up after itself?

Also, I think making more passes to have to care about LiveIntervals should generally be avoided

It is not only RenameIndependentSubregs, detect dead lanes also just mark them dead. I guess the assumption was it will be later deadcoded. And that never happened.
Even if both passes will cleanup after themselves both will need to handle LIS anyway.

[arsenm]

lib/CodeGen/DeadMachineInstructionElim.cpp

193–197 ↗

(On Diff #191622)

Can you just use shrinkToUses?

[rampitec]

lib/CodeGen/DeadMachineInstructionElim.cpp

193–197 ↗

(On Diff #191622)

I am afraid not. It does far less than needed. In particular it does not handle defs, and this cannot be solved by just removing a dead interval.

[rampitec]

Rebased.

[rampitec]

Ping.

Since the primary goal of the DCE here is to clean dead subregs I can bail this pass invocation if subreg liveness if not supported by target. What do you think?

[rampitec]

In D59626#1449373, @rampitec wrote:

Ping.

Since the primary goal of the DCE here is to clean dead subregs I can bail this pass invocation if subreg liveness if not supported by target. What do you think?

In fact the BE affected most if x86. Adding @craig.topper as a reviewer. At the same time x86 does not override subRegLivenessEnabled, so it should not be limited to targets with subreg liveness enabled only.

[craig.topper]

test/CodeGen/X86/combine-bitselect.ll

657 ↗

(On Diff #192198)

This test should be fixed to not be an infinite loop. The middle end wouldn't have given this code to the backend.

test/CodeGen/X86/speculative-load-hardening-gather.ll

10 ↗

(On Diff #192198)

This looks like speculative load hardening is creating an instruction it doesn't end up using. The speculative loading hardening pass runs after the previous times the MachineDCE was ran. Maybe we should fix the pass to not insert dead instructions.

test/CodeGen/X86/speculative-load-hardening-indirect.ll

134 ↗

(On Diff #192198)

This looks like new regular expressioning the script wasn't doing previously. Can you drop this from this from your diff or rerun the script on an unmodified trunk and commit it.

test/CodeGen/X86/tail-dup-merge-loop-headers.ll

262 ↗

(On Diff #192198)

This basic block isn't reachable and is keeping other code alive. That would normally have been removed by IR passes.

[rampitec]

test/CodeGen/X86/combine-bitselect.ll

657 ↗

(On Diff #192198)

Does it change anything? The test has no side effects anyway.
I am not really sure what does it test, so I am a little afraid to touch it. I can add an option not run extra DCE pass here if needed.

test/CodeGen/X86/speculative-load-hardening-indirect.ll

134 ↗

(On Diff #192198)

Will do.

test/CodeGen/X86/tail-dup-merge-loop-headers.ll

262 ↗

(On Diff #192198)

Do I conclude x86 does not really need this pass, since most of the stuff can be handled separatetly, like speculative load hardening?
If that is the case I can only enable it if subreg liveness is enabled, like proposed earlier.

[rampitec]

Rebased.

test/CodeGen/X86/speculative-load-hardening-indirect.ll

134 ↗

(On Diff #192198)

Done.

[craig.topper]

I don't think X86 needs this pass. Everything here looks like bad test construction or the issue in speculative load hardening.

test/CodeGen/X86/combine-bitselect.ll

657 ↗

(On Diff #192198)

I updated this test in trunk so that it no longer has an infinite loop that would allow things to be deleted.

[rampitec]

In D59626#1453765, @craig.topper wrote:

I don't think X86 needs this pass. Everything here looks like bad test construction or the issue in speculative load hardening.

OK, thanks! Than I will skip it for targets which do not track subreg liveness.

[rampitec]

Skip this invocation for targets which do not have subregister liveness.

[qcolombet]

Hi @rampitec,

Are the dead instructions marked during the detect dead lanes pass or during the rename independent SubReg pass?

I would expect the former and in that case, it may be easier to just do the code deletion there.

Cheers,
-Quentin

[rampitec]

In D59626#1454322, @qcolombet wrote:

Hi @rampitec,

Are the dead instructions marked during the detect dead lanes pass or during the rename independent SubReg pass?

I would expect the former and in that case, it may be easier to just do the code deletion there.

Cheers,
-Quentin

The detect dead lanes pass cannot really delete dead lanes, just mark them. So a subreg definition becomes dead, but in most cases retain a use by REG_SEQUENCE.
Rename independent subregs deletes REQ_SEQENCEs and the subreg looses that use, so finally can be deleted.

I.e. both passes can free up new dead instructions independently, but in most cases they need to work together.

[qcolombet]

lib/CodeGen/DeadMachineInstructionElim.cpp

120 ↗

(On Diff #193617)

I feel that the pass shouldn't be making that decision.
If someone put that in their pipeline, the pass should just run.

[rampitec]

lib/CodeGen/DeadMachineInstructionElim.cpp

120 ↗

(On Diff #193617)

TargetPassConfig does not have subtarget access when it adds a pass to the pipeline.
So the choice is: 1) always run even if it will not find anything 2) perform this check 3) insert it from the target and not from common TargetPassConfig.
In all cases code to handle LIS is needed though.

I can make it only running from AMDGPU target since we always track subreg liveness. Would that be better?

[rampitec]

Moving pass insertion from common TargetPassConfig into AMDGPU, since most targets do not need it.
Changes to maintain liveness if available remain in the MachineDCE pass, but are a no-op for any other target until they decide to use it late in the RA.

[rampitec]

lib/CodeGen/DeadMachineInstructionElim.cpp

120 ↗

(On Diff #193617)

I have reverted the check and only add it from AMDGPU. If any other target feels it may need it there is an option to do the same.
If this is committed it will be possible since pass will not destroy liveness anymore.

[qcolombet]

Looks reasonable to me.

I leave the final approval to @arsenm for the AMDGPU changes.

[arsenm]

lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

168–170 ↗

(On Diff #193766)

I prefer avoiding double negative flags, so -amdgpu-dce-in-ra and default to true

test/CodeGen/AMDGPU/dead-lane.mir

10–15 ↗

(On Diff #193766)

You can drop the registers section (although %0 will need a class marker)

[rampitec]

Addressed review comments.

[arsenm]

LGTM except for the option description string

lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

170 ↗

(On Diff #193922)

Description needs to be updated

[rampitec]

Changed option description.

[arsenm]

LGTM

[bjope]

I see a couple of problems with the changes to DeadMachineInstructionElim.cpp in this patch:

• I get MachineVerifier problems because the LIS update does not take into consideration that the removal of a dead use can introduce disjoint live ranges (resulting in verifier complaining about "Multiple connected components in live interval".
• I get MachineVerifier problems because the LIS update does not update live ranges for physical registers. Consider an instruction like this dead %42:regs = COPY $a1, if that is removed and it is the last use of the physical register $a1 then we need to shrink the live range for $a1 , otherwise the MachineVerifier will complain about "Live segment doesn't end at a valid instruction".
• I do not think the !MRI->reg_empty(Reg) check takes debug info into consideration. Possibly introducing a debug invariance problem.
• It does not seem like this pass is using the LIS itself. So why do we even bother keeping it update? It is destroyed, and then it is up to the pass manager to detect if it needs to be recalculated by a later pass, right? Or do we know that it will be used by a later pass, and thereby we want to bother about preserving it (even if it isn't for the greater good of the pass itself). If it is like that, then we probably need to add some code comments to highlight that we only do it because some other pass needs it (for example in case that pass is removed in the future).
• Is it really true that we now preserve all possible analyses (both existing and future, both upstream and downstream), motivating the change from setPreservesCFG() to setPreservesAll(). I mean, the pass is pretty "destructive" as it removes instructions. You have only added (afaict incomplete) support to preserve the LIS. Notice that I'm not sure exactly what the difference between "PreservesAll" and "PreservesCFG" is, but I suppose it includes more analysis results besides LIS (and SlotIndices).

Maybe we can back out the change in DeadMachineInstructionElim.cpp until the above problems have been sorted out?

[rampitec]

Bjorn,

did you enable MachineDCE in RA in some other target? So far it is only enabled in the AMDGPU, so I am curious where do you see these problems?

In D59626#1458186, @bjope wrote:

I see a couple of problems with the changes to DeadMachineInstructionElim.cpp in this patch:

• I get MachineVerifier problems because the LIS update does not take into consideration that the removal of a dead use can introduce disjoint live ranges (resulting in verifier complaining about "Multiple connected components in live interval".

I am recomputing liveness for all affected uses, how could that be?

• I get MachineVerifier problems because the LIS update does not update live ranges for physical registers. Consider an instruction like this dead %42:regs = COPY $a1, if that is removed and it is the last use of the physical register $a1 then we need to shrink the live range for $a1 , otherwise the MachineVerifier will complain about "Live segment doesn't end at a valid instruction".

That is probably right. I avoid deleting dead phys, but not their uses. I think shrinkToUses() will be appropriate here.

• I do not think the !MRI->reg_empty(Reg) check takes debug info into consideration. Possibly introducing a debug invariance problem.

I thought about this, so I did not use reg_nodbg_empty() in this instance. I.e. this LI gets recreated.

• It does not seem like this pass is using the LIS itself. So why do we even bother keeping it update? It is destroyed, and then it is up to the pass manager to detect if it needs to be recalculated by a later pass, right? Or do we know that it will be used by a later pass, and thereby we want to bother about preserving it (even if it isn't for the greater good of the pass itself). If it is like that, then we probably need to add some code comments to highlight that we only do it because some other pass needs it (for example in case that pass is removed in the future).

The pass does not use it, but should update if it exists. That is true, if I do not claim it is preserved then it will be recalculated, but that is very slow.
So far only AMDGPU should be using it with liveness available. Am I missing some other invocation?

• Is it really true that we now preserve all possible analyses (both existing and future, both upstream and downstream), motivating the change from setPreservesCFG() to setPreservesAll(). I mean, the pass is pretty "destructive" as it removes instructions. You have only added (afaict incomplete) support to preserve the LIS. Notice that I'm not sure exactly what the difference between "PreservesAll" and "PreservesCFG" is, but I suppose it includes more analysis results besides LIS (and SlotIndices).

It does preserve LIS and SlotIndexes. The rest of the analysis passes (like PDT) are just unaffected by the pass itself. I believe that is more or less the same assumption for all passes which use PreservesAll() that we are considering exiting analysis passes. Otherwise this method is not future proof in general.

Maybe we can back out the change in DeadMachineInstructionElim.cpp until the above problems have been sorted out?

If there is no better way. If you see the problems do you mind to share an IR?

[rampitec]

In D59626#1458594, @rampitec wrote:

• I get MachineVerifier problems because the LIS update does not update live ranges for physical registers. Consider an instruction like this dead %42:regs = COPY $a1, if that is removed and it is the last use of the physical register $a1 then we need to shrink the live range for $a1 , otherwise the MachineVerifier will complain about "Live segment doesn't end at a valid instruction".

Actually I cannot reproduce it:

# RUN: llc -march=amdgcn -mcpu=tonga %s -run-pass liveintervals,dead-mi-elimination -verify-machineinstrs -o - | FileCheck -check-prefix=GCN %s
  
---
name:            dead_phys_use
tracksRegLiveness: true
liveins:
  - { reg: '$vgpr0', virtual-reg: '%2' }
body:             |
  bb.0:
    liveins: $vgpr0

    %2:vgpr_32 = COPY $vgpr0
    $vgpr1 = COPY %2:vgpr_32
    %1:vgpr_32 = COPY $vgpr0, implicit $exec
    SI_RETURN_TO_EPILOG $vgpr1
...

The last COPY is dead and $vgpr0 will be affected, but verifier did not find any errors:

bb.0:
  liveins: $vgpr0

  %0:vgpr_32 = COPY $vgpr0
  $vgpr1 = COPY %0
  SI_RETURN_TO_EPILOG $vgpr1

[bjope]

In D59626#1458594, @rampitec wrote:

Bjorn,

did you enable MachineDCE in RA in some other target? So far it is only enabled in the AMDGPU, so I am curious where do you see these problems?

Well, our OOT target is using the DeadMachineInstructionElim pass in (maybe non-standard according to in-tree target) positions in the backend pipeline.

In D59626#1458186, @bjope wrote:

I see a couple of problems with the changes to DeadMachineInstructionElim.cpp in this patch:

• I get MachineVerifier problems because the LIS update does not take into consideration that the removal of a dead use can introduce disjoint live ranges (resulting in verifier complaining about "Multiple connected components in live interval".

I am recomputing liveness for all affected uses, how could that be?

Ok, so the test case is from the OOT target. Here is an excerpt of the MIR:

0B	bb.0:

16B	  %0:rn = ...
32B	  %10:an32pairs = ...
80B	  %4:an32_0_7 = ... %10.hiAcc:an32pairs, ...
96B	  brr_cond %bb.3, ...
112B	  brr_uncond %bb.1

128B	bb.1:

144B	  brr_cond %bb.2, ...
160B	  brr_uncond %bb.3

176B	bb.2:

192B	  %8:anh_rn = COPY %4.lo16:an32_0_7
224B	  %7:anh_rn = COPY %10.hiAcc_then_lo16:an32pairs
256B	  brr_uncond %bb.4

272B	bb.3:

288B	  %9:rn = ...
304B	  %10:an32pairs = ... %9:rn, ...
352B	  %7:anh_rn = COPY %10.hiAcc_then_lo16:an32pairs
368B	  %8:anh_rn = COPY %10.hiAcc_then_hi16:an32pairs

384B	bb.4::

400B	  nop 0, $noreg, 0, implicit %10.loAcc:an32pairs
416B	  $a0h = COPY %8:anh_rn
432B	  $a1h = COPY %7:anh_rn
448B	  rets implicit $a0h, implicit $a1h

The nop is removed by by DMIE, resulting in

*** Bad machine code: Multiple connected components in live interval ***
- function:    f3
- interval:    %10 [32r,224r:0)[304r,368r:1)  0@32r 1@304r weight:0.000000e+00

• I get MachineVerifier problems because the LIS update does not update live ranges for physical registers. Consider an instruction like this dead %42:regs = COPY $a1, if that is removed and it is the last use of the physical register $a1 then we need to shrink the live range for $a1 , otherwise the MachineVerifier will complain about "Live segment doesn't end at a valid instruction".

That is probably right. I avoid deleting dead phys, but not their uses. I think shrinkToUses() will be appropriate here.

• I do not think the !MRI->reg_empty(Reg) check takes debug info into consideration. Possibly introducing a debug invariance problem.

I thought about this, so I did not use reg_nodbg_empty() in this instance. I.e. this LI gets recreated.

So it might be that that the call to createAndComputeVirtRegInterval only happens when having debug info. And afaict that might give a different codegen compared to the situation when not having any debug info. I think we usually try to avoid that. Codegen should not be impacted by existence of debug info.

• It does not seem like this pass is using the LIS itself. So why do we even bother keeping it update? It is destroyed, and then it is up to the pass manager to detect if it needs to be recalculated by a later pass, right? Or do we know that it will be used by a later pass, and thereby we want to bother about preserving it (even if it isn't for the greater good of the pass itself). If it is like that, then we probably need to add some code comments to highlight that we only do it because some other pass needs it (for example in case that pass is removed in the future).

The pass does not use it, but should update if it exists. That is true, if I do not claim it is preserved then it will be recalculated, but that is very slow.
So far only AMDGPU should be using it with liveness available. Am I missing some other invocation?

Well, in my case it is an OOT target. So I'm can't blame you for missing that.

• Is it really true that we now preserve all possible analyses (both existing and future, both upstream and downstream), motivating the change from setPreservesCFG() to setPreservesAll(). I mean, the pass is pretty "destructive" as it removes instructions. You have only added (afaict incomplete) support to preserve the LIS. Notice that I'm not sure exactly what the difference between "PreservesAll" and "PreservesCFG" is, but I suppose it includes more analysis results besides LIS (and SlotIndices).

It does preserve LIS and SlotIndexes. The rest of the analysis passes (like PDT) are just unaffected by the pass itself. I believe that is more or less the same assumption for all passes which use PreservesAll() that we are considering exiting analysis passes. Otherwise this method is not future proof in general.

Ok. A little bit scary. But if that is how PreservesAll() works in general I guess it is ok.

Maybe we can back out the change in DeadMachineInstructionElim.cpp until the above problems have been sorted out?

If there is no better way. If you see the problems do you mind to share an IR?

A little bit hard due to that I've only triggered it for the OOT target so far. For now I hacked around it in our downstream clone (although using setPreservesCFG instead gives some churn in some AMDGPU test cases, so it seems like we get different results if LIS is recalculated instead of just being preserved by DeadMachineInstructionElim, I would have expected to get the same result, at least if the preserve worked correctly).

Anyway. I can try to make in-tree reproducers tomorrow.

[rampitec]

In D59626#1458686, @bjope wrote:

Actually shrinkToUses does not work with phys. That should be possible to avoid removing dead phys uses if that phys is allocatable (otherwise liveness is not calculated for it).
I also do not see how to reproduce disjoint intervals.
And yes, changing it back to PreservesCFG() should effectively switch this off.

[rampitec]

@bjope could you please check if D60419 solves your problem with physreg use removal?

[rampitec]

In D59626#1458773, @rampitec wrote:

@bjope could you please check if D60419 solves your problem with physreg use removal?

WRT disjoint liveranges. I only see such possibility with a physreg, because virtual should be recomputed. So maybe the same patch would help.

[bjope]

Here is a MIR-reproducer triggering "Multiple connected components in live interval".

For some reason I needed to add "simple-register-coalescing" at the end of the list of passes to run. Otherwise the pass manager decides to discard LIS before dead-mi-elimination.

# RUN: llc -mtriple=amdgcn-- -run-pass=liveintervals,machineverifier,dead-mi-elimination,machineverifier,simple-register-coalescing -o /dev/null %s

---
name:            foo
tracksRegLiveness: true
body:             |
  bb.0:
    liveins: $sgpr0_sgpr1

    %10:sreg_128 = S_LOAD_DWORDX4_IMM killed $noreg, 9, 0
    S_NOP 0, implicit-def %4:sreg_128, implicit %10.sub1:sreg_128
    S_CBRANCH_SCC0 %bb.3, implicit undef $scc
    S_BRANCH %bb.1

  bb.1:
    S_CBRANCH_SCC0 %bb.2, implicit undef $scc
    S_BRANCH %bb.3

  bb.2:
    %8:sreg_32_xm0 = COPY %4.sub1:sreg_128
    %7:sreg_32_xm0 = COPY %10.sub1:sreg_128
    S_BRANCH %bb.4

  bb.3:
    %10:sreg_128 = S_LOAD_DWORDX4_IMM killed $noreg, 10, 0
    %7:sreg_32_xm0 = COPY %10.sub1:sreg_128
    %8:sreg_32_xm0 = COPY %10.sub2:sreg_128

  bb.4:
    S_NOP 0, implicit %10
    $sgpr0 = COPY %8:sreg_32_xm0
    $sgpr1 = COPY %7:sreg_32_xm0
    S_ENDPGM 0, implicit $sgpr0, implicit $sgpr1
...

[bjope]

In D59626#1458773, @rampitec wrote:

@bjope could you please check if D60419 solves your problem with physreg use removal?

Isn't it weird that this pass now is doing less optimizations when an analysis pass is provided? It might be OK for your use case, but it seems weird from a more general perspective.

FWIW, I'm not sure exactly why we are running this pass in a lot of places in our OOT target (after ISel, before coalescing, post-coalescing, etc). But we have done it for years (since before I started working with this target), and now some of those runs won't do as much cleanup as they used to do (when a LIS is found). Not sure, but maybe it is exactly these physreg removals we aim for, so I'm not sure that solving the LIS preservation problem by not eliminating certain dead instructions is good enough for us. It will take some time to analyse that, so at the moment it is easier for me to just make a work around patch downstream.

[rampitec]

In D59626#1459918, @bjope wrote:

In D59626#1458773, @rampitec wrote:

@bjope could you please check if D60419 solves your problem with physreg use removal?

Isn't it weird that this pass now is doing less optimizations when an analysis pass is provided? It might be OK for your use case, but it seems weird from a more general perspective.

FWIW, I'm not sure exactly why we are running this pass in a lot of places in our OOT target (after ISel, before coalescing, post-coalescing, etc). But we have done it for years (since before I started working with this target), and now some of those runs won't do as much cleanup as they used to do (when a LIS is found). Not sure, but maybe it is exactly these physreg removals we aim for, so I'm not sure that solving the LIS preservation problem by not eliminating certain dead instructions is good enough for us. It will take some time to analyse that, so at the moment it is easier for me to just make a work around patch downstream.

Bjorn, thank you for the testcase. It doesn't seem to be easy to quick fix, while I am going for vacation tomorrow. I will create a revert patch for now and try to sort it out later.

I understood someone might be aiming for dead phys regs, but handling phys without recompute can be much more challenging, so probably a full recompute is not unreasonable under such scenario too.

[rampitec]

In D59626#1459926, @rampitec wrote:

In D59626#1459918, @bjope wrote:

In D59626#1458773, @rampitec wrote:

@bjope could you please check if D60419 solves your problem with physreg use removal?

Isn't it weird that this pass now is doing less optimizations when an analysis pass is provided? It might be OK for your use case, but it seems weird from a more general perspective.

FWIW, I'm not sure exactly why we are running this pass in a lot of places in our OOT target (after ISel, before coalescing, post-coalescing, etc). But we have done it for years (since before I started working with this target), and now some of those runs won't do as much cleanup as they used to do (when a LIS is found). Not sure, but maybe it is exactly these physreg removals we aim for, so I'm not sure that solving the LIS preservation problem by not eliminating certain dead instructions is good enough for us. It will take some time to analyse that, so at the moment it is easier for me to just make a work around patch downstream.

Bjorn, thank you for the testcase. It doesn't seem to be easy to quick fix, while I am going for vacation tomorrow. I will create a revert patch for now and try to sort it out later.

I understood someone might be aiming for dead phys regs, but handling phys without recompute can be much more challenging, so probably a full recompute is not unreasonable under such scenario too.

Revert patch: D60466

[bjope]

For the record, I think the "multiple connected components" problem could have been solved by something like this after the call to "createAndComputeVirtRegInterval"

LiveInterval &LI = LIS->getInterval(Reg);
assert(Reg == LI.reg && "Invalid reg to interval mapping");
if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
  // Check whether or not LI is composed by multiple connected
  // components and if that is the case, fix that.
  SmallVector<LiveInterval*, 8> SplitLIs;
  LIS->splitSeparateComponents(LI, SplitLIs);
}

However, that still leaves the questions about if the pass should do less optimizations related to physregs when LIS is available, or how to preserve LIS if optimizing on physregs.
And I'm not sure about the cost of using splitSeparateComponents compared to a full recompute.

[rampitec]

In D59626#1460006, @bjope wrote:

For the record, I think the "multiple connected components" problem could have been solved by something like this after the call to "createAndComputeVirtRegInterval"

LiveInterval &LI = LIS->getInterval(Reg);
assert(Reg == LI.reg && "Invalid reg to interval mapping");
if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
  // Check whether or not LI is composed by multiple connected
  // components and if that is the case, fix that.
  SmallVector<LiveInterval*, 8> SplitLIs;
  LIS->splitSeparateComponents(LI, SplitLIs);
}

However, that still leaves the questions about if the pass should do less optimizations related to physregs when LIS is available, or how to preserve LIS if optimizing on physregs.
And I'm not sure about the cost of using splitSeparateComponents compared to a full recompute.

Thank you for the hint and test case. For the phys I could remove all regunits, but for some reason I cannot always get them reconstructed. It will need some more debugging.

[rampitec]

In D59626#1460006, @bjope wrote:

For the record, I think the "multiple connected components" problem could have been solved by something like this after the call to "createAndComputeVirtRegInterval"

LiveInterval &LI = LIS->getInterval(Reg);
assert(Reg == LI.reg && "Invalid reg to interval mapping");
if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
  // Check whether or not LI is composed by multiple connected
  // components and if that is the case, fix that.
  SmallVector<LiveInterval*, 8> SplitLIs;
  LIS->splitSeparateComponents(LI, SplitLIs);
}

However, that still leaves the questions about if the pass should do less optimizations related to physregs when LIS is available, or how to preserve LIS if optimizing on physregs.
And I'm not sure about the cost of using splitSeparateComponents compared to a full recompute.

For the record, this code works if applied after createAndComputeVirtRegInterval() call.

[rampitec]

In D59626#1460173, @rampitec wrote:

In D59626#1460006, @bjope wrote:

For the record, I think the "multiple connected components" problem could have been solved by something like this after the call to "createAndComputeVirtRegInterval"

LiveInterval &LI = LIS->getInterval(Reg);
assert(Reg == LI.reg && "Invalid reg to interval mapping");
if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
  // Check whether or not LI is composed by multiple connected
  // components and if that is the case, fix that.
  SmallVector<LiveInterval*, 8> SplitLIs;
  LIS->splitSeparateComponents(LI, SplitLIs);
}

However, that still leaves the questions about if the pass should do less optimizations related to physregs when LIS is available, or how to preserve LIS if optimizing on physregs.
And I'm not sure about the cost of using splitSeparateComponents compared to a full recompute.

For the record, this code works if applied after createAndComputeVirtRegInterval() call.

The problem with phys regs is that I see no way to recompute liveins. If I remove reg units for affected register they are reconstructed on the next query. However if it was a livein I will drop it as well, and it is only recomputed in private LiveIntervals::computeLiveInRegUnits(), which is only called from LiveIntervals::runOnMachineFunction()...

llvm/trunk/lib/CodeGen/DeadMachineInstructionElim.cpp

 //===- DeadMachineInstructionElim.cpp - Remove dead machine instructions --===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This is an extremely simple MachineInstr-level dead-code-elimination pass.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/LiveIntervals.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "dead-mi-elimination"
 
 STATISTIC(NumDeletes,          "Number of dead instructions deleted");
 
 namespace {
   class DeadMachineInstructionElim : public MachineFunctionPass {
     bool runOnMachineFunction(MachineFunction &MF) override;
 
     const TargetRegisterInfo *TRI;
     const MachineRegisterInfo *MRI;
     const TargetInstrInfo *TII;
+    LiveIntervals *LIS;
     BitVector LivePhysRegs;
 
   public:
     static char ID; // Pass identification, replacement for typeid
     DeadMachineInstructionElim() : MachineFunctionPass(ID) {
      initializeDeadMachineInstructionElimPass(*PassRegistry::getPassRegistry());
     }
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
-      AU.setPreservesCFG();
+      AU.setPreservesAll();
       MachineFunctionPass::getAnalysisUsage(AU);
     }
 
   private:
     bool isDead(const MachineInstr *MI) const;
   };
 }
 char DeadMachineInstructionElim::ID = 0;
bool DeadMachineInstructionElim::isDead(const MachineInstr *MI) const {
 
   // Examine each operand.
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = MI->getOperand(i);
     if (MO.isReg() && MO.isDef()) {
       unsigned Reg = MO.getReg();
       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
         // Don't delete live physreg defs, or any reserved register defs.
-        if (LivePhysRegs.test(Reg) || MRI->isReserved(Reg))
+        // Do not remove physreg defs if we have LIS as we may be unable
+        // to accurately recompute its liveness.
+        if (LivePhysRegs.test(Reg) || MRI->isReserved(Reg) || LIS)
           return false;
       } else {
+        // An instruction can also use its def in case if it is a tied operand.
+        // TODO: Technically we can also remove it if def dominates the use.
+        //       This can happen when two instructions define different subregs
+        //       of the same register.
         for (const MachineInstr &Use : MRI->use_nodbg_instructions(Reg)) {
           if (&Use != MI)
             // This def has a non-debug use. Don't delete the instruction!
             return false;
         }
       }
     }
   }
 
   // If there are no defs with uses, the instruction is dead.
   return true;
 }
 
 bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) {
   if (skipFunction(MF.getFunction()))
     return false;
 
   bool AnyChanges = false;
   MRI = &MF.getRegInfo();
   TRI = MF.getSubtarget().getRegisterInfo();
   TII = MF.getSubtarget().getInstrInfo();
+  LIS = getAnalysisIfAvailable<LiveIntervals>();
+  DenseSet<unsigned> RecalcRegs;
 
   // Loop over all instructions in all blocks, from bottom to top, so that it's
   // more likely that chains of dependent but ultimately dead instructions will
   // be cleaned up.
   for (MachineBasicBlock &MBB : make_range(MF.rbegin(), MF.rend())) {
     // Start out assuming that reserved registers are live out of this block.
     LivePhysRegs = MRI->getReservedRegs();
 
for (MachineBasicBlock &MBB : make_range(MF.rbegin(), MF.rend())) {
     // liveness as we go.
     for (MachineBasicBlock::reverse_iterator MII = MBB.rbegin(),
          MIE = MBB.rend(); MII != MIE; ) {
       MachineInstr *MI = &*MII++;
 
       // If the instruction is dead, delete it!
       if (isDead(MI)) {
         LLVM_DEBUG(dbgs() << "DeadMachineInstructionElim: DELETING: " << *MI);
+        if (LIS) {
+          for (const MachineOperand &MO : MI->operands()) {
+            if (MO.isReg() && TRI->isVirtualRegister(MO.getReg()))
+              RecalcRegs.insert(MO.getReg());
+          }
+          LIS->RemoveMachineInstrFromMaps(*MI);
+        }
+
         // It is possible that some DBG_VALUE instructions refer to this
         // instruction.  They get marked as undef and will be deleted
         // in the live debug variable analysis.
         MI->eraseFromParentAndMarkDBGValuesForRemoval();
         AnyChanges = true;
         ++NumDeletes;
         continue;
       }
for (MachineBasicBlock::reverse_iterator MII = MBB.rbegin(),
               LivePhysRegs.set(*AI);
           }
         }
       }
     }
   }
 
   LivePhysRegs.clear();
+
+  for (auto Reg : RecalcRegs) {
+    LIS->removeInterval(Reg);
+    if (!MRI->reg_empty(Reg))
+      LIS->createAndComputeVirtRegInterval(Reg);
+  }
+
   return AnyChanges;
 }

llvm/trunk/lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

 
 // Enable Mode register optimization
 static cl::opt<bool> EnableSIModeRegisterPass(
   "amdgpu-mode-register",
   cl::desc("Enable mode register pass"),
   cl::init(true),
   cl::Hidden);
 
+// Option is used in lit tests to prevent deadcoding of patterns inspected.
+static cl::opt<bool>
+EnableDCEInRA("amdgpu-dce-in-ra",
+    cl::init(true), cl::Hidden,
+    cl::desc("Enable machine DCE inside regalloc"));
+
 extern "C" void LLVMInitializeAMDGPUTarget() {
   // Register the target
   RegisterTargetMachine<R600TargetMachine> X(getTheAMDGPUTarget());
   RegisterTargetMachine<GCNTargetMachine> Y(getTheGCNTarget());
 
   PassRegistry *PR = PassRegistry::getPassRegistry();
   initializeR600ClauseMergePassPass(*PR);
   initializeR600ControlFlowFinalizerPass(*PR);
void GCNPassConfig::addOptimizedRegAlloc() {
   // This must be run immediately after phi elimination and before
   // TwoAddressInstructions, otherwise the processing of the tied operand of
   // SI_ELSE will introduce a copy of the tied operand source after the else.
   insertPass(&PHIEliminationID, &SILowerControlFlowID, false);
 
   // This must be run just after RegisterCoalescing.
   insertPass(&RegisterCoalescerID, &SIPreAllocateWWMRegsID, false);
 
+  if (EnableDCEInRA)
+    insertPass(&RenameIndependentSubregsID, &DeadMachineInstructionElimID);
+
   TargetPassConfig::addOptimizedRegAlloc();
 }
 
 void GCNPassConfig::addPostRegAlloc() {
   addPass(&SIFixVGPRCopiesID);
   if (getOptLevel() > CodeGenOpt::None)
     addPass(&SIOptimizeExecMaskingID);
   TargetPassConfig::addPostRegAlloc();

llvm/trunk/test/CodeGen/AMDGPU/dead-lane.mir

+# RUN: llc -march=amdgcn -mcpu=tonga %s -start-before detect-dead-lanes -stop-before machine-scheduler -verify-machineinstrs -o - | FileCheck -check-prefix=GCN %s
+
+# GCN-LABEL: name: dead_lane
+# GCN:      bb.0:
+# GCN-NEXT: undef %3.sub0:vreg_64 = V_MAC_F32_e32 undef %1:vgpr_32, undef %1:vgpr_32, undef %3.sub0, implicit $exec
+# GCN-NEXT: FLAT_STORE_DWORD undef %4:vreg_64, %3.sub0,
+---
+name:            dead_lane
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    %1:vgpr_32 = V_MAC_F32_e32 undef %0:vgpr_32, undef %0:vgpr_32, undef %0:vgpr_32, implicit $exec
+    %2:vgpr_32 = V_MAC_F32_e32 undef %0:vgpr_32, undef %0:vgpr_32, undef %0:vgpr_32, implicit $exec
+    %3:vreg_64 = REG_SEQUENCE %1:vgpr_32, %subreg.sub0, %2:vgpr_32, %subreg.sub1
+    FLAT_STORE_DWORD undef %4:vreg_64, %3.sub0, 0, 0, 0, implicit $exec, implicit $flat_scr
+    S_ENDPGM 0
+
+...

llvm/trunk/test/CodeGen/AMDGPU/salu-to-valu.ll

bb1:
   br i1 %cnd, label %bb4, label %bb2
 
 bb2:
   %tmp3 = add nsw i32 %tmp, 1
   br label %bb4
 
 bb4:
   %tmp5 = phi i32 [ %tmp3, %bb2 ], [ %tmp, %bb1 ]
+  store volatile i32 %tmp5, i32 addrspace(1)* undef
   br label %bb1
 }
 
 ; GCN-LABEL: {{^}}phi_imm_in_sgprs
 ; GCN: s_movk_i32 [[A:s[0-9]+]], 0x400
 ; GCN: s_movk_i32 [[B:s[0-9]+]], 0x400
 ; GCN: [[LOOP_LABEL:[0-9a-zA-Z_]+]]:
 ; GCN: s_xor_b32 [[B]], [[B]], [[A]]

llvm/trunk/test/CodeGen/AMDGPU/sdwa-peephole.ll

 bb2:                                              ; preds = %bb1
   %tmp3 = call i32 asm "v_and_b32_e32 $0, $1, $2", "=v,s,v"(i32 65535, i32 undef) #1
   %tmp5 = or i32 %tmp3, 65536
   %tmp6 = insertelement <2 x i32> %tmp, i32 %tmp5, i64 0
   br label %bb11
 
 bb11:                                             ; preds = %bb10, %bb2
   %tmp12 = phi <2 x i32> [ %tmp6, %bb2 ], [ %tmp, %bb1 ]
+  store volatile <2 x i32> %tmp12, <2 x i32> addrspace(1)* undef
   br label %bb1
 }

llvm/trunk/test/CodeGen/AMDGPU/shrink-carry.mir

 body:             |
   bb.0:
 
     %0 = IMPLICIT_DEF
     %1 = IMPLICIT_DEF
     %2 = IMPLICIT_DEF
     %3 = V_CMP_GT_U32_e64 %0, %1, implicit $exec
     %4, %5 = V_SUBBREV_U32_e64 0, %0, %3, 0, implicit $exec
+    GLOBAL_STORE_DWORD undef $vgpr0_vgpr1, %4, 0, 0, 0, implicit $exec
 
 ...
 
 # GCN-LABEL: name: subb{{$}}
 # GCN:       V_SUBBREV_U32_e32 0, undef $vgpr0, implicit-def $vcc, implicit killed $vcc, implicit $exec
 
 ---
 name:            subb
 tracksRegLiveness: true
 registers:
   - { id: 0, class: vgpr_32 }
   - { id: 1, class: vgpr_32 }
   - { id: 2, class: vgpr_32 }
   - { id: 3, class: sreg_64_xexec }
   - { id: 4, class: vgpr_32 }
   - { id: 5, class: sreg_64_xexec }
 body:             |
   bb.0:
 
     %0 = IMPLICIT_DEF
     %1 = IMPLICIT_DEF
     %2 = IMPLICIT_DEF
     %3 = V_CMP_GT_U32_e64 %0, %1, implicit $exec
     %4, %5 = V_SUBB_U32_e64 %0, 0, %3, 0, implicit $exec
+    GLOBAL_STORE_DWORD undef $vgpr0_vgpr1, %4, 0, 0, 0, implicit $exec
 
 ...
 
 # GCN-LABEL: name: addc{{$}}
 # GCN:       V_ADDC_U32_e32 0, undef $vgpr0, implicit-def $vcc, implicit killed $vcc, implicit $exec
 
 ---
 name:            addc
 tracksRegLiveness: true
 registers:
   - { id: 0, class: vgpr_32 }
   - { id: 1, class: vgpr_32 }
   - { id: 2, class: vgpr_32 }
   - { id: 3, class: sreg_64_xexec }
   - { id: 4, class: vgpr_32 }
   - { id: 5, class: sreg_64_xexec }
 body:             |
   bb.0:
 
     %0 = IMPLICIT_DEF
     %1 = IMPLICIT_DEF
     %2 = IMPLICIT_DEF
     %3 = V_CMP_GT_U32_e64 %0, %1, implicit $exec
     %4, %5 = V_ADDC_U32_e64 0, %0, %3, 0, implicit $exec
+    GLOBAL_STORE_DWORD undef $vgpr0_vgpr1, %4, 0, 0, 0, implicit $exec
 
 ...
 
 # GCN-LABEL: name: addc2{{$}}
 # GCN:       V_ADDC_U32_e32 0, undef $vgpr0, implicit-def $vcc, implicit killed $vcc, implicit $exec
 
 ---
 name:            addc2
 tracksRegLiveness: true
 registers:
   - { id: 0, class: vgpr_32 }
   - { id: 1, class: vgpr_32 }
   - { id: 2, class: vgpr_32 }
   - { id: 3, class: sreg_64_xexec }
   - { id: 4, class: vgpr_32 }
   - { id: 5, class: sreg_64_xexec }
 body:             |
   bb.0:
 
     %0 = IMPLICIT_DEF
     %1 = IMPLICIT_DEF
     %2 = IMPLICIT_DEF
     %3 = V_CMP_GT_U32_e64 %0, %1, implicit $exec
     %4, %5 = V_ADDC_U32_e64 %0, 0, %3, 0, implicit $exec
+    GLOBAL_STORE_DWORD undef $vgpr0_vgpr1, %4, 0, 0, 0, implicit $exec
 
 ...

llvm/trunk/test/CodeGen/AMDGPU/spill-empty-live-interval.mir

-# RUN: llc -mtriple=amdgcn-amd-amdhsa -verify-machineinstrs -stress-regalloc=1 -start-before=simple-register-coalescing -stop-after=greedy -o - %s | FileCheck %s
+# RUN: llc -mtriple=amdgcn-amd-amdhsa -amdgpu-dce-in-ra=0 -verify-machineinstrs -stress-regalloc=1 -start-before=simple-register-coalescing -stop-after=greedy -o - %s | FileCheck %s
 # https://bugs.llvm.org/show_bug.cgi?id=33620
 
 ---
 # This would assert due to the empty live interval created for %9
 # on the last S_NOP with an undef subreg use.
 
 # CHECK-LABEL: name: expecting_non_empty_interval
 

llvm/trunk/test/CodeGen/AMDGPU/subreg-coalescer-undef-use.ll

-; RUN: llc -march=amdgcn -mcpu=tahiti -o - %s | FileCheck %s
+; RUN: llc -march=amdgcn -mcpu=tahiti -amdgpu-dce-in-ra=0 -o - %s | FileCheck %s
 ; Don't crash when the use of an undefined value is only detected by the
 ; register coalescer because it is hidden with subregister insert/extract.
 target triple="amdgcn--"
 
 ; CHECK-LABEL: foobar:
 ; CHECK: s_load_dwordx2 s[4:5], s[0:1], 0x9
 ; CHECK-NEXT: s_load_dwordx2 s[0:1], s[0:1], 0xb
 ; CHECK-NEXT: v_mbcnt_lo_u32_b32_e64