Improve handling of COPY instructions with identical value numbers

[kparzysz]

Summary

This is an alternative to D48032.

[tpr]

Yes, that works for me thanks on my larger test case.

lib/CodeGen/RegisterCoalescer.cpp

2486

Did you mean to leave this comment from my change in?

[kparzysz]

This testcase is exposing some preexisting problem in the coalescer. I have reverted this patch until I figure out what's wrong.

[kparzysz]

Properly extend liveness of a merged value when a redundant copy was erased.

[tpr]

With this, I'm getting a different assert "CopyMI input register not live" in one test case. I'll narrow it down and check I can reproduce it on upstream LLVM with your fix (as opposed to our local branch with your fix).

[tpr]

I can fix that assert on my testcase with this addition to your fix:

--- a/lib/CodeGen/RegisterCoalescer.cpp
+++ b/lib/CodeGen/RegisterCoalescer.cpp
@@ -1653,6 +1653,10 @@ bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) {
     deleteInstr(CopyMI);
     return false;  // Not coalescable.
   }
+  if (CopyMI->getOpcode() == TargetOpcode::IMPLICIT_DEF) {
+    // Not coalesceable; eliminateUndefCopy turned it into implicit_def.
+    return false;
+  }

   // Coalesced copies are normally removed immediately, but transformations
   // like removeCopyByCommutingDef() can inadvertently create identity copies.

I will go and test that more thoroughly.

[tpr]

I'm getting another failure somewhere else in our test suite with that. I need to analyze it further.

[tpr]

lib/CodeGen/RegisterCoalescer.cpp

2867

This is the cause of my second failure. In my test, because of some weird branching around in the control flow, there is another value in between Id and Q.endPoint(), and this code is illegally extending segment Id over the top of the other value.

I guess what it really needs is to add new segments as necessary so Id->valno is live on all paths from OtherDef to Def.

Is there some ready made code to do that somewhere?

[kparzysz]

Please post a testcase. We need to understand how these things happen.

[kparzysz]

Could you add "LIS->print(dbgs())" at the beginning of joinCopy and post the output with -debug-only=regalloc? You can remove the unnecessary parts from the output. For the copy that triggers the problem, I'd like to see all instructions using the registers from the copy and the debugging output from the coalescer.

[tpr]

Sorry about the lack of testcase. I need to get clearance to post it as it is derived from a third party app.

I'll gather together the useful bits of the debug log.

[tpr]

********** INTERVALS **********
%67 [3184r,3216r:0)  0@3184r weight:0.000000e+00
%72 [384B,544r:0)[2576r,2608B:2)[2864B,2912B:0)[3072r,3104B:1)[3104B,3264B:0)  0@2864B-phi 1@3072r 2@2576r L00000004 [384B,544r:0)[2576r,2608B:2)[2864B,2912B:0)[3072r,3104B:1)[3104B,3264B:0)  0@2864B-phi 1@3072r 2@2576r L00000002 [384B,528r:0)[2576r,2608B:2)[2864B,2912B:0)[3072r,3104B:1)[3104B,3264B:0)  0@2864B-phi 1@3072r 2@2576r L00000001 [384B,528r:0)[2576r,2608B:2)[2864B,2912B:0)[3072r,3104B:1)[3104B,3264B:0)  0@2864B-phi 1@3072r 2@2576r L00000008 [2576r,2608B:2)[2864B,2912B:0)[3072r,3104B:1)[3104B,3184r:0)  0@2864B-phi 1@3072r 2@2576r weight:0.000000e+00
%86 [224r,240B:1)[240B,384B:2)[640B,1808B:2)[1904r,1920B:3)[1920B,2576r:4)[2608B,2624r:4)[3216r,3264B:0)  0@3216r 1@224r 2@240B-phi 3@1904r 4@1920B-phi L00000004 [224r,240B:1)[240B,384B:2)[640B,1808B:2)[1904r,1920B:3)[1920B,2576r:4)[2608B,2624r:4)[3216r,3264B:0)  0@3216r 1@224r 2@240B-phi 3@1904r 4@1920B-phi L0000000B [224r,240B:1)[240B,384B:2)[640B,1808B:2)[1904r,1920B:3)[1920B,2576r:4)[3216r,3264B:0)  0@3216r 1@224r 2@240B-phi 3@1904r 4@1920B-phi weight:0.000000e+00

********** MACHINEINSTRS **********
# Machine code for function _amdgpu_cs_main: NoPHIs, TracksLiveness

2864B	bb.66.Flow:
	; predecessors: %bb.63, %bb.67
	  successors: %bb.68(0x80000000); %bb.68(100.00%)

2896B	  S_BRANCH %bb.68

2912B	bb.67 (%ir-block.152):
	; predecessors: %bb.64, %bb.65
	  successors: %bb.66(0x80000000); %bb.66(100.00%)

2928B	  $exec = S_OR_B64 $exec, %5:sreg_64, implicit-def $scc
2944B	  %8:vreg_1 = COPY %89:vreg_1
2960B	  %40:sreg_64_xexec = V_CMP_NE_U32_e64 0, %8:vreg_1, implicit $exec
2976B	  %39:vgpr_32 = V_CNDMASK_B32_e64 0, 1, %40:sreg_64_xexec, implicit $exec
2992B	  %82:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
3008B	  undef %81.sub0:vreg_128 = COPY %82:vgpr_32
3024B	  %81.sub1:vreg_128 = COPY %82:vgpr_32
3040B	  %81.sub2:vreg_128 = COPY %39:vgpr_32
3056B	  %73:vreg_128 = COPY %81:vreg_128
3072B	  %72:vreg_128 = COPY %73:vreg_128
3088B	  S_BRANCH %bb.66

3104B	bb.68 (%ir-block.156):
	; predecessors: %bb.66
	  successors: %bb.4(0x04000000), %bb.1(0x7c000000); %bb.4(3.12%), %bb.1(96.88%)

3120B	  %64:vgpr_32 = V_ADD_I32_e32 32, %85:vgpr_32, implicit-def dead $vcc, implicit $exec
3136B	  V_CMP_EQ_U32_e32 0, %64:vgpr_32, implicit-def $vcc, implicit $exec
3152B	  %63:vgpr_32 = COPY %64:vgpr_32
3168B	  $vcc = S_AND_B64 $exec, killed $vcc, implicit-def dead $scc
3184B	  %67:vreg_128 = COPY %72:vreg_128
3200B	  %85:vgpr_32 = COPY %63:vgpr_32
3216B	  %86:vreg_128 = COPY %67:vreg_128
3232B	  S_CBRANCH_VCCNZ %bb.4, implicit killed $vcc
3248B	  S_BRANCH %bb.1

# End machine code for function _amdgpu_cs_main.


2576B	%72:vreg_128 = COPY %86:vreg_128
	Considering merging to VReg_128 with %72 in %86
		RHS = %72 [384B,544r:0)[2576r,2608B:2)[2864B,2912B:0)[3072r,3104B:1)[3104B,3264B:0)  0@2864B-phi 1@3072r 2@2576r L00000004 [384B,544r:0)[2576r,2608B:2)[2864B,2912B:0)[3072r,3104B:1)[3104B,3264B:0)  0@2864B-phi 1@3072r 2@2576r L00000002 [384B,528r:0)[2576r,2608B:2)[2864B,2912B:0)[3072r,3104B:1)[3104B,3264B:0)  0@2864B-phi 1@3072r 2@2576r L00000001 [384B,528r:0)[2576r,2608B:2)[2864B,2912B:0)[3072r,3104B:1)[3104B,3264B:0)  0@2864B-phi 1@3072r 2@2576r L00000008 [2576r,2608B:2)[2864B,2912B:0)[3072r,3104B:1)[3104B,3184r:0)  0@2864B-phi 1@3072r 2@2576r weight:0.000000e+00
		LHS = %86 [224r,240B:1)[240B,384B:2)[640B,1808B:2)[1904r,1920B:3)[1920B,2576r:4)[2608B,2624r:4)[3216r,3264B:0)  0@3216r 1@224r 2@240B-phi 3@1904r 4@1920B-phi L00000004 [224r,240B:1)[240B,384B:2)[640B,1808B:2)[1904r,1920B:3)[1920B,2576r:4)[2608B,2624r:4)[3216r,3264B:0)  0@3216r 1@224r 2@240B-phi 3@1904r 4@1920B-phi L0000000B [224r,240B:1)[240B,384B:2)[640B,1808B:2)[1904r,1920B:3)[1920B,2576r:4)[3216r,3264B:0)  0@3216r 1@224r 2@240B-phi 3@1904r 4@1920B-phi weight:0.000000e+00
		merge %86:0@3216r into %72:0@2864B --> @2864B
		merge %72:2@2576r into %86:4@1920B --> @1920B
		LHST = %86 %86 [224r,240B:1)[240B,384B:2)[640B,1808B:2)[1904r,1920B:3)[1920B,2576r:4)[2608B,2624r:4)[3216r,3264B:0)  0@3216r 1@224r 2@240B-phi 3@1904r 4@1920B-phi L00000004 [224r,240B:1)[240B,384B:2)[640B,1808B:2)[1904r,1920B:3)[1920B,2576r:4)[2608B,2624r:4)[3216r,3264B:0)  0@3216r 1@224r 2@240B-phi 3@1904r 4@1920B-phi L0000000B [224r,240B:1)[240B,384B:2)[640B,1808B:2)[1904r,1920B:3)[1920B,2576r:4)[3216r,3264B:0)  0@3216r 1@224r 2@240B-phi 3@1904r 4@1920B-phi weight:0.000000e+00
		merge %86:0@3216r into %72:0@2864B --> @2864B
		merge %72:2@2576r into %86:4@1920B --> @1920B
		joined lanes: [224r,240B:1)[240B,384B:2)[384B,544r:0)[640B,1808B:2)[1904r,1920B:3)[1920B,2624r:4)[2864B,2912B:0)[3072r,3104B:5)[3104B,3264B:0)  0@2864B-phi 1@224r 2@240B-phi 3@1904r 4@1920B-phi 5@3072r
		merge %86:0@3216r into %72:0@2864B --> @2864B
		merge %72:2@2576r into %86:4@1920B --> @1920B
		joined lanes: [224r,240B:1)[240B,384B:2)[384B,528r:0)[640B,1808B:2)[1904r,1920B:3)[1920B,2608B:4)[2864B,2912B:0)[3072r,3104B:5)[3104B,3264B:0)  0@2864B-phi 1@224r 2@240B-phi 3@1904r 4@1920B-phi 5@3072r
		merge %86:0@3216r into %72:0@2864B --> @2864B
		merge %72:2@2576r into %86:4@1920B --> @1920B
		joined lanes: [224r,240B:1)[240B,384B:2)[384B,528r:0)[640B,1808B:2)[1904r,1920B:3)[1920B,2608B:4)[2864B,2912B:0)[3072r,3104B:5)[3104B,3264B:0)  0@2864B-phi 1@224r 2@240B-phi 3@1904r 4@1920B-phi 5@3072r
		merge %72:2@2576r into %86:4@1920B --> @1920B
		joined lanes: [224r,240B:1)[240B,384B:2)[640B,1808B:2)[1904r,1920B:3)[1920B,2608B:4)[2864B,2912B:5)[3072r,3104B:6)[3104B,3184r:5)[3216r,3264B:0)  0@3216r 1@224r 2@240B-phi 3@1904r 4@1920B-phi 5@2864B-phi 6@3072r
	Joined SubRanges %86 [224r,240B:1)[240B,384B:2)[640B,1808B:2)[1904r,1920B:3)[1920B,2576r:4)[2608B,2624r:4)[3216r,3264B:0)  0@3216r 1@224r 2@240B-phi 3@1904r 4@1920B-phi L00000001 [224r,240B:1)[240B,384B:2)[384B,528r:0)[640B,1808B:2)[1904r,1920B:3)[1920B,2608B:4)[2864B,2912B:0)[3072r,3104B:5)[3104B,3264B:0)  0@2864B-phi 1@224r 2@240B-phi 3@1904r 4@1920B-phi 5@3072r L00000002 [224r,240B:1)[240B,384B:2)[384B,528r:0)[640B,1808B:2)[1904r,1920B:3)[1920B,2608B:4)[2864B,2912B:0)[3072r,3104B:5)[3104B,3264B:0)  0@2864B-phi 1@224r 2@240B-phi 3@1904r 4@1920B-phi 5@3072r L00000004 [224r,240B:1)[240B,384B:2)[384B,544r:0)[640B,1808B:2)[1904r,1920B:3)[1920B,2624r:4)[2864B,2912B:0)[3072r,3104B:5)[3104B,3264B:0)  0@2864B-phi 1@224r 2@240B-phi 3@1904r 4@1920B-phi 5@3072r L00000008 [224r,240B:1)[240B,384B:2)[640B,1808B:2)[1904r,1920B:3)[1920B,2608B:4)[2864B,2912B:5)[3072r,3104B:6)[3104B,3184r:5)[3216r,3264B:0)  0@3216r 1@224r 2@240B-phi 3@1904r 4@1920B-phi 5@2864B-phi 6@3072r weight:0.000000e+00
		Expecting instruction removal at 3216r
		 checking:  L00000001 [224r,240B:1)[240B,384B:2)[384B,528r:0)[640B,1808B:2)[1904r,1920B:3)[1920B,2608B:4)[2864B,2912B:0)[3072r,3104B:5)[3104B,3264B:0)  0@2864B-phi 1@224r 2@240B-phi 3@1904r 4@1920B-phi 5@3072r
		 checking:  L00000002 [224r,240B:1)[240B,384B:2)[384B,528r:0)[640B,1808B:2)[1904r,1920B:3)[1920B,2608B:4)[2864B,2912B:0)[3072r,3104B:5)[3104B,3264B:0)  0@2864B-phi 1@224r 2@240B-phi 3@1904r 4@1920B-phi 5@3072r
		 checking:  L00000004 [224r,240B:1)[240B,384B:2)[384B,544r:0)[640B,1808B:2)[1904r,1920B:3)[1920B,2624r:4)[2864B,2912B:0)[3072r,3104B:5)[3104B,3264B:0)  0@2864B-phi 1@224r 2@240B-phi 3@1904r 4@1920B-phi 5@3072r
		 checking:  L00000008 [224r,240B:1)[240B,384B:2)[640B,1808B:2)[1904r,1920B:3)[1920B,2608B:4)[2864B,2912B:5)[3072r,3104B:6)[3104B,3184r:5)[3216r,3264B:0)  0@3216r 1@224r 2@240B-phi 3@1904r 4@1920B-phi 5@2864B-phi 6@3072r
		Prune sublane 00000008 at 3216r
Assertion failed: (I->end <= std::next(I)->start), function verify, file ../lib/CodeGen/LiveInterval.cpp, line 1022.

(lldb) up 5
frame #5: 0x00000001012cf283 llc`(anonymous namespace)::JoinVals::pruneSubRegValues(this=0x00007fff5fbfa9e8, LI=0x0000000106b0a9e0, ShrinkMask=0x0000000106d00be0) + 1619 at RegisterCoalescer.cpp:2872
   2869	        }
   2870	        // Mark value number as unused.
   2871	        ValueOut->markUnused();
-> 2872	        S.verify();
   2873	        continue;
   2874	      }
   2875	      // If a subrange ends at the copy, then a value was copied but only
(lldb) p S.dump()
 L00000008 [224r,240B:1)[240B,384B:2)[640B,1808B:2)[1904r,1920B:3)[1920B,2608B:4)[2864B,3264B:5)[3072r,3104B:6)[3104B,3184r:5)  0@x 1@224r 2@240B-phi 3@1904r 4@1920B-phi 5@2864B-phi 6@3072r

It was trying to coalesce %72 and %86, and it did that thing where it notices that a value of %86 is copied (at 3216) from %67, which is itself copied (at 3184) from %72. %72's value at that point is 5@2864B-phi, which reaches 3184 by branching over [2912B,3104B), in which another value 6@3072r is defined.

In lane L00000008, it wants to remove the segment [3216r,3264B:0) and extend [2864B,2912B:5) to 3264B, but it ends up with [2864B,3264B:5), whereas it should have [2864B,2912B:5)[3104B,3264B:5).

[tpr]

I've just realized I am allowed to post the whole cutdown test case because it comes from a conformance test, not from someone else's app.

What's the best way to post it?

[kparzysz]

Is it an .ll file? You can email it to me, I'll try to see if I can reduce it.

[tpr]

Thanks, but how do I get your email address from phabricator? It's a .mir file that I got from -stop-before=simple-register-coalescer on a .ll test that I had cut down with bugpoint.

[kparzysz]

My username at codeaurora.org.

[tpr]

I'm trying out fixing up the LR like this:

// If a subrange starts at the copy then an undefined value has been
// copied and we must remove that subrange value as well.
VNInfo *ValueOut = Q.valueOutOrDead();
if (ValueOut != nullptr && Q.valueIn() == nullptr) {
  DEBUG(dbgs() << "\t\tPrune sublane " << PrintLaneMask(S.LaneMask)
               << " at " << Def << "\n");
  SmallVector<SlotIndex, 4> EndPoints;
  LIS->pruneValue(S, Def, &EndPoints);
  DidPrune = true;

  // Mark value number as unused.
  ValueOut->markUnused();

  if (V.Identical) {
    // Ensure that liveness reaches the end points of the value that we
    // have just pruned.
    LIS->extendToIndices(S, EndPoints, ArrayRef<SlotIndex>());
  }
  S.verify();
  continue;
}

[kparzysz]

That simply undoes the pruning. It has to extend the specific value (OtherVNI).

[tpr]

It has pruned value 0 away completely, and it extends value 5 to reach the end point(s) of value 0. Isn't that what we want?

[tpr]

I guess there is the possibility that OtherVNI is not the closest dominating def, but surely it would not be coalescing in the first place if that was true.

[kparzysz]

You're right, extendToIndices should be ok. I wanted to be explicit about what gets extended (since it could catch other errors), while extendToIndices would just extend whatever is the reaching value.

[kparzysz]

Use extendToIndices.

[kparzysz]

I can reproduce the problem using your testcase (which now works), let me try to reduce it and add to the patch.

[tpr]

lib/CodeGen/RegisterCoalescer.cpp

2867

Why don't we need to extend to all the uses of the value we've just pruned?

[kparzysz]

Updated the extension, added second testcase.

[kparzysz]

Remove unnecessary stuff from the other testcase.

[tpr]

I now have another test case where the extendToIndices falls over with "Use not dominated by all defs". I will investigate.

[tpr]

lib/CodeGen/RegisterCoalescer.cpp

2866

My new failure is because it gets here with V.Identical true, but in this particular lane there is no def or liveness at OtherDef. So I added a check for that:

if (V.Identical && S.Query(OtherDef).valueOut()) {
  // If V is identical to V.OtherVNI and is live out of OtherDef in
  // this lane, then we can't simply prune V from S. V needs to be
  // replaced with V.OtherVNI.

But I am now getting a "Couldn't join subrange" in the code that originally prompted this whole fix (but in not the cutdown that is the first test in this change). So I need to investigate that.

[kparzysz]

lib/CodeGen/RegisterCoalescer.cpp

2295–2296

This should obvoiusly be &&...

[kparzysz]

Fixed a typo and added a check for subrange liveness at OtherDef.

[tpr]

Good spot on the typo, but unfortunately it does not fix my latest problem. I have been told that I am not allowed to send the test case outside of AMD, so I'll have to try and get by with just showing you part of a debug dump of what is going on.

It is trying to coalesce %17 and %25, and the main range and L00000008 say that 832r is a CR_Erase with Identical set. But then L00000001 says that 832r is CR_Unresolved.

Any ideas? I'll have to stop working on this in a minute until tomorrow.

********** INTERVALS **********
%1 [912r,928r:0)  0@912r weight:0.000000e+00
%16 [816r,832r:0)  0@816r weight:0.000000e+00
%17 [800r,848r:0)  0@800r weight:0.000000e+00
%18 [720r,720d:0)  0@720r weight:0.000000e+00
%25 [528r,592r:0)[592r,608r:3)[608r,640r:4)[640r,704B:5)[704B,752r:0)[752r,768r:1)[768r,816r:2)[832r,864B:6)[864B,912r:7)  0@528r 1@752r 2@768r 3@592r 4@608r 5@640r 6@832r 7@864B-phi L00000008 [640r,672r:0)[832r,832d:1)  0@640r 1@832r 2@x L00000001 [592r,672r:1)[752r,800r:0)[832r,832d:2)  0@752r 1@592r 2@832r 3@x L00000002 [608r,672r:1)[768r,800r:0)[832r,832d:2)  0@768r 1@608r 2@832r 3@x L00000004 [528r,816r:0)[832r,864B:1)[864B,912r:2)  0@528r 1@832r 2@864B-phi weight:0.000000e+00
%36 [976r,992r:0)  0@976r weight:0.000000e+00
%41 [672r,704B:1)[848r,864B:0)[864B,976r:2)  0@848r 1@672r 2@864B-phi weight:0.000000e+00
%42 [112r,144B:2)[992r,1008B:1)[1008B,1040r:3)[1184r,1216B:0)  0@1184r 1@992r 2@112r 3@1008B-phi L00000008 [112r,144B:2)[992r,1008B:1)[1008B,1040r:3)[1184r,1216B:0)  0@1184r 1@992r 2@112r 3@1008B-phi L00000007 [112r,112d:2)[992r,992d:1)[1184r,1184d:0)  0@1184r 1@992r 2@112r 3@x weight:0.000000e+00
RegMasks:
********** MACHINEINSTRS **********
...
752B	  %25.sub0:sreg_128 = COPY %25.sub2:sreg_128
768B	  %25.sub1:sreg_128 = COPY %25.sub2:sreg_128
800B	  %17:sreg_128 = COPY %25:sreg_128
816B	  %16:sreg_128 = COPY %25:sreg_128
832B	  %25:sreg_128 = COPY %16:sreg_128
848B	  %41:sreg_128 = COPY %17:sreg_128

864B	bb.17.bb22:
	; predecessors: %bb.15, %bb.16
...

# End machine code for function _amdgpu_cs_main.

800B	%17:sreg_128 = COPY %25:sreg_128
	Considering merging to SReg_128 with %17 in %25
		RHS = %17 [800r,848r:0)  0@800r weight:0.000000e+00
		LHS = %25 [528r,592r:0)[592r,608r:3)[608r,640r:4)[640r,704B:5)[704B,752r:0)[752r,768r:1)[768r,816r:2)[832r,864B:6)[864B,912r:7)  0@528r 1@752r 2@768r 3@592r 4@608r 5@640r 6@832r 7@864B-phi L00000008 [640r,672r:0)[832r,832d:1)  0@640r 1@832r 2@x L00000001 [592r,672r:1)[752r,800r:0)[832r,832d:2)  0@752r 1@592r 2@832r 3@x L00000002 [608r,672r:1)[768r,800r:0)[832r,832d:2)  0@768r 1@608r 2@832r 3@x L00000004 [528r,816r:0)[832r,864B:1)[864B,912r:2)  0@528r 1@832r 2@864B-phi weight:0.000000e+00
		analyzeValue(528r) gives CR_Keep
		analyzeValue(752r) gives CR_Keep
		analyzeValue(768r) gives CR_Keep
		analyzeValue(592r) gives CR_Keep
		analyzeValue(608r) gives CR_Keep
		analyzeValue(640r) gives CR_Keep
		analyzeValue(800r) gives CR_Erase
		merge %17:0@800r into %25:2@768r --> @768r
		Identical CR_Erase
		analyzeValue(832r) gives CR_Erase
		merge %25:6@832r into %17:0@800r --> @768r
		analyzeValue(864B) gives CR_Keep
		LHST = %25 %25 [528r,592r:0)[592r,608r:3)[608r,640r:4)[640r,704B:5)[704B,752r:0)[752r,768r:1)[768r,816r:2)[832r,864B:6)[864B,912r:7)  0@528r 1@752r 2@768r 3@592r 4@608r 5@640r 6@832r 7@864B-phi L00000008 [640r,672r:0)[832r,832d:1)  0@640r 1@832r 2@x L00000001 [592r,672r:1)[752r,800r:0)[832r,832d:2)  0@752r 1@592r 2@832r 3@x L00000002 [608r,672r:1)[768r,800r:0)[832r,832d:2)  0@768r 1@608r 2@832r 3@x L00000004 [528r,816r:0)[832r,864B:1)[864B,912r:2)  0@528r 1@832r 2@864B-phi weight:0.000000e+00
	joinSubRegRanges  L00000008 EMPTY
		LRange [640r,672r:0)[832r,832d:1)  0@640r 1@832r 2@x
		RRange [800r,848r:0)  0@800r
		analyzeValue(640r) gives CR_Keep
		analyzeValue(800r) gives CR_Keep
		Identical CR_Erase
		analyzeValue(832r) gives CR_Erase
		merge %25:1@832r into %17:0@800r --> @800r
		analyzeValue(invalid) gives CR_Keep
		joined lanes: [640r,672r:0)[800r,848r:1)  0@640r 1@800r 2@x
	joinSubRegRanges  L00000001 EMPTY
		LRange [592r,672r:1)[752r,800r:0)[832r,832d:2)  0@752r 1@592r 2@832r 3@x
		RRange [800r,848r:0)  0@800r
		analyzeValue(752r) gives CR_Keep
		analyzeValue(592r) gives CR_Keep
		analyzeValue(800r) gives CR_Erase
		merge %17:0@800r into %25:0@752r --> @752r
		analyzeValue(832r) gives CR_Unresolved
		analyzeValue(invalid) gives CR_Keep
		conflict at %25:2@832r
*** Couldn't join subrange!

UNREACHABLE executed at ../lib/CodeGen/RegisterCoalescer.cpp:3060!

[tpr]

Actually, with this change on top of upstream llvm, L00000008 fails with CR_Unresolved too. But I also had D35073, which fixed the problem for L00000008 but not L00000001, in the dump I added above.

[kparzysz]

Fix the "cannot join subranges" issue caused by redefining an undef value (more details in comments), roughly something like this:

%0 <- undef
%1 = COPY %0
%0 = COPY %1  <- now %0 is "def", even though it's identical to what it was before (i.e. "undef").

[tpr]

D'oh! I now think that last problem is because I made a mistake resolving conflicts when cherry-picking this change on top of D35073.

So I think this change is good, and I'm going to set off some more testing overnight to make sure.

[tpr]

Ah, I see you've done a fix for it anyway. It might fix the same as D35073. I'll check.

[tpr]

Your 'Fix the "cannot join subranges" issue caused by redefining an undef value' does not seem to fix all the cases covered by D35073, so I suggest removing that part of the fix again and moving the discussion on how to fix that problem onto D35073. (I realize you had to try and fix it blind as I was unable to give you my test case.)

lib/CodeGen/RegisterCoalescer.cpp

2873

I now have a test case that hits this assert. I will investigate further.

[kparzysz]

lib/CodeGen/RegisterCoalescer.cpp

2873

It could be because of a basic block boundary between Def and OtherDef. You can probably delete this code under #ifndef NDEBUG.

[tpr]

lib/CodeGen/RegisterCoalescer.cpp

2873

We don't want to test this in the case that there were no end points to extend to. So I put this round the block of code inside the #ifndef:

if (!EndPoints.empty()) {

[kparzysz]

My fix for the redef/undef issue was trying to avoid cases where we treat "undef" values from different registers as identical. I guess this could be relaxed (i.e. we can treat all undef values as identical), but we'd have to make sure that this equality is only used to allow removing an undef value (i.e. to allow pruning it without following it with extendToIndices).

[tpr]

Oh dear, testing has shown up another "CopyMI input register not live".

[tpr]

That's because this change isn't in yet:

--- a/lib/CodeGen/RegisterCoalescer.cpp
+++ b/lib/CodeGen/RegisterCoalescer.cpp
@@ -1653,6 +1653,10 @@ bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) {
     deleteInstr(CopyMI);
     return false;  // Not coalescable.
   }
+  if (CopyMI->getOpcode() == TargetOpcode::IMPLICIT_DEF) {
+    // Not coalesceable; eliminateUndefCopy turned it into implicit_def.
+    return false;
+  }

   // Coalesced copies are normally removed immediately, but transformations
   // like removeCopyByCommutingDef() can inadvertently create identity copies.

[kparzysz]

This shouldn't be necessary. Try returning "true" from eliminateUndefCopy after generating an IMPLICIT_DEF.

[tpr]

But then it would erase CopyMI, which used to be the copy but is now the IMPLICIT_DEF.

[kparzysz]

We shouldn't really be calling joinCopy with something that is not a COPY, but I guess it's a minor issue. Please replace the getOpcode() == ... with isImplicitDef(), and it should be fine.

[tpr]

It was a copy at the point that joinCopy was called, but eliminateUndefCopy changed it to implicit_def.

Good idea re isImplicitDef().

[tpr]

lib/CodeGen/RegisterCoalescer.cpp

2873

Even with that change, I've now got a different test case that hits this assert. I'll investigate and see what is going on.

[tpr]

Here's what I've found so far.

Here is some of the code (two separate blocks, but the first one is the only predecessor of the second one):

656B	  %217.sub0:vreg_128 = COPY %46:sgpr_32
720B	  %188:vreg_128 = COPY %217:vreg_128
816B	  %172:vreg_128 = IMPLICIT_DEF

1568B	  %185:vreg_128 = COPY %188:vreg_128
1600B	  %172:vreg_128 = COPY %185:vreg_128

We're trying to coalesce this:

1200B	%217:vreg_128 = COPY %172:vreg_128

At 1600, we have that situation where it sets CR_Erase and Identical. %172 is a copy of %185 is a copy of %188 is a copy of %217 defined at 656r, and it's the same value of %217 that is live and reaches 1600.

My current theory is that that condition is not strong enough: we have a different value of %172 at 816, and it is "in the way", in the sense that, once we have merged, the value defined at 656r no longer reaches 1600. Then the extendToIndices for L00000004 goes wrong because it attaches the use at 1648B to the implicit_def at 816r.

But I'm not sure what the stronger condition should be.

I can give you this test case, so I'll email it over.

[tpr]

This "in the way" def at 816r is an implicit_def that is also being erased. I think this has to be the case, otherwise the main range would not have set our def as CR_Erase Identical, and/or the main range would not have allowed coalescing at all.

Therefore I now think the fix for this problem is to do all the prunes first, remembering the end points, and then do the extend afterwards.

I have a local fix for that which I will now start testing.

[tpr]

Hi Krzysztof

With my latest fix for the "in the way value" problem, it all passes my local testing.

That latest fix is quite a big diff in pruneSubRegValues because it puts the loops the other way round (outer loop is subranges, inner loop is values). So I figured it would be easier to start a new review D48478 to supersede and subsume this one. Could you head over and review that one please?

Thanks for all your help on this issue.

[kparzysz]

Fixed handling of newly created implicit defs, relaxed handling of undef values in followCopyChain.

[kparzysz]

This includes all testcases from related reviews.

[tpr]

Thanks Krzysztof. This all works for me now.

lib/CodeGen/RegisterCoalescer.cpp

for (const LiveInterval::SubRange &SR : SrcLI.subranges()) {
       if ((SR.LaneMask & SrcMask).none())
         continue;
       if (SR.liveAt(Idx))
         return false;
     }
   } else if (SrcLI.liveAt(Idx))
     return false;
 
-  LLVM_DEBUG(dbgs() << "\tEliminating copy of <undef> value\n");
-
-  // Remove any DstReg segments starting at the instruction.
+  // If the undef copy defines a live-out value (i.e. an input to a PHI def),
+  // then replace it with an IMPLICIT_DEF.
   LiveInterval &DstLI = LIS->getInterval(DstReg);
   SlotIndex RegIndex = Idx.getRegSlot();
+  LiveRange::Segment *Seg = DstLI.getSegmentContaining(RegIndex);
+  assert(Seg != nullptr && "No segment for defining instruction");
+  if (VNInfo *V = DstLI.getVNInfoAt(Seg->end)) {
+    if (V->isPHIDef()) {
+      CopyMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
+      for (unsigned i = CopyMI->getNumOperands(); i != 0; --i) {
+        MachineOperand &MO = CopyMI->getOperand(i-1);
+        if (MO.isReg() && MO.isUse())
+          CopyMI->RemoveOperand(i-1);
+      }
+      LLVM_DEBUG(dbgs() << "\tReplaced copy of <undef> value with an "
+                           "implicit def\n");
+      return false;
+    }
+  }
+
+  // Remove any DstReg segments starting at the instruction.
+  LLVM_DEBUG(dbgs() << "\tEliminating copy of <undef> value\n");
+
   // Remove value or merge with previous one in case of a subregister def.
   if (VNInfo *PrevVNI = DstLI.getVNInfoAt(Idx)) {
     VNInfo *VNI = DstLI.getVNInfoAt(RegIndex);
     DstLI.MergeValueNumberInto(VNI, PrevVNI);
 
     // The affected subregister segments can be removed.
     LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(DstSubIdx);
     for (LiveInterval::SubRange &SR : DstLI.subranges()) {
struct Val {
 
     /// True when the live range of this value will be pruned because of an
     /// overlapping CR_Replace value in the other live range.
     bool Pruned = false;
 
     /// True once Pruned above has been computed.
     bool PrunedComputed = false;
 
+    /// True if this value is determined to be identical to OtherVNI
+    /// (in valuesIdentical). This is used with CR_Erase where the erased
+    /// copy is redundant, i.e. the source value is already the same as
+    /// the destination. In such cases the subranges need to be updated
+    /// properly. See comment at pruneSubRegValues for more info.
+    bool Identical = false;
+
     Val() = default;
 
     bool isAnalyzed() const { return WriteLanes.any(); }
   };
 
   /// One entry per value number in LI.
   SmallVector<Val, 8> Vals;
 
   /// Compute the bitmask of lanes actually written by DefMI.
   /// Set Redef if there are any partial register definitions that depend on the
   /// previous value of the register.
   LaneBitmask computeWriteLanes(const MachineInstr *DefMI, bool &Redef) const;
 
   /// Find the ultimate value that VNI was copied from.
-  std::pair<const VNInfo*,unsigned> followCopyChain(const VNInfo *VNI) const;
+  std::pair<const VNInfo*,unsigned> followCopyChain(const VNInfo *VNI,
+                                                    unsigned OtherReg) const;
 
   bool valuesIdentical(VNInfo *Val0, VNInfo *Val1, const JoinVals &Other) const;
 
   /// Analyze ValNo in this live range, and set all fields of Vals[ValNo].
   /// Return a conflict resolution when possible, but leave the hard cases as
   /// CR_Unresolved.
   /// Recursively calls computeAssignment() on this and Other, guaranteeing that
   /// both OtherVNI and RedefVNI have been analyzed and mapped before returning.
L |= TRI->getSubRegIndexLaneMask(
            TRI->composeSubRegIndices(SubIdx, MO.getSubReg()));
     if (MO.readsReg())
       Redef = true;
   }
   return L;
 }
 
 std::pair<const VNInfo*, unsigned> JoinVals::followCopyChain(
-    const VNInfo *VNI) const {
-  unsigned Reg = this->Reg;
+    const VNInfo *VNI, unsigned OtherReg) const {
+  unsigned TrackReg = Reg;
 
   while (!VNI->isPHIDef()) {
     SlotIndex Def = VNI->def;
     MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
     assert(MI && "No defining instruction");
     if (!MI->isFullCopy())
-      return std::make_pair(VNI, Reg);
+      return std::make_pair(VNI, TrackReg);
     unsigned SrcReg = MI->getOperand(1).getReg();
     if (!TargetRegisterInfo::isVirtualRegister(SrcReg))
-      return std::make_pair(VNI, Reg);
+      return std::make_pair(VNI, TrackReg);
 
     const LiveInterval &LI = LIS->getInterval(SrcReg);
     const VNInfo *ValueIn;
     // No subrange involved.
     if (!SubRangeJoin || !LI.hasSubRanges()) {
       LiveQueryResult LRQ = LI.Query(Def);
       ValueIn = LRQ.valueIn();
     } else {
       // Query subranges. Pick the first matching one.
       ValueIn = nullptr;
       for (const LiveInterval::SubRange &S : LI.subranges()) {
         // Transform lanemask to a mask in the joined live interval.
         LaneBitmask SMask = TRI->composeSubRegIndexLaneMask(SubIdx, S.LaneMask);
         if ((SMask & LaneMask).none())
           continue;
         LiveQueryResult LRQ = S.Query(Def);
         ValueIn = LRQ.valueIn();
         break;
       }
     }
-    if (ValueIn == nullptr)
+    if (ValueIn == nullptr) {
+      // Reaching undefined value is legitimate in cases where it comes from
+      // one of the considered registers (Reg or OtherReg).
+      //
+      // 1   undef %0.sub1 = ...  ;; %0.sub0 == undef
+      // 2   %1 = COPY %0         ;; %1 is defined here.
+      // 3   %0 = COPY %1         ;; Now %0.sub0 has a definition!
+      // 4   ...                  ;; Here we should indicate that %0 at 3 is
+      //                          ;; the same as %0 at 2 (%0 at 3 == %1 at 2).
+      if (SrcReg == Reg || SrcReg == OtherReg)
+        return std::make_pair(nullptr, SrcReg);
       break;
+    }
     VNI = ValueIn;
-    Reg = SrcReg;
+    TrackReg = SrcReg;
   }
-  return std::make_pair(VNI, Reg);
+  return std::make_pair(VNI, TrackReg);
 }
 
 bool JoinVals::valuesIdentical(VNInfo *Value0, VNInfo *Value1,
                                const JoinVals &Other) const {
   const VNInfo *Orig0;
   unsigned Reg0;
-  std::tie(Orig0, Reg0) = followCopyChain(Value0);
-  if (Orig0 == Value1)
+  std::tie(Orig0, Reg0) = followCopyChain(Value0, Other.Reg);
+  if (Orig0 == Value1 && Reg0 == Other.Reg)
     return true;
 
   const VNInfo *Orig1;
   unsigned Reg1;
-  std::tie(Orig1, Reg1) = Other.followCopyChain(Value1);
+  std::tie(Orig1, Reg1) = Other.followCopyChain(Value1, Reg);
+  // If both values are undefined, and the source registers are the same
+  // register, the values are identical. Filter out cases where only one
+  // value is defined.
+  if (Orig0 == nullptr || Orig1 == nullptr)
+    return Orig0 == Orig1 && Reg0 == Reg1;
 
   // The values are equal if they are defined at the same place and use the
   // same register. Note that we cannot compare VNInfos directly as some of
   // them might be from a copy created in mergeSubRangeInto()  while the other
   // is from the original LiveInterval.
   return Orig0->def == Orig1->def && Reg0 == Reg1;
 }
 
if (OtherLRQ.isKill() && OtherLRQ.endPoint() <= VNI->def)
     return CR_Keep;
 
   // Handle the case where VNI and OtherVNI can be proven to be identical:
   //
   //   %other = COPY %ext
   //   %this  = COPY %ext <-- Erase this copy
   //
   if (DefMI->isFullCopy() && !CP.isPartial()
-      && valuesIdentical(VNI, V.OtherVNI, Other))
+      && valuesIdentical(VNI, V.OtherVNI, Other)) {
+    V.Identical = true;
     return CR_Erase;
+  }
 
   // If the lanes written by this instruction were all undef in OtherVNI, it is
   // still safe to join the live ranges. This can't be done with a simple value
   // mapping, though - OtherVNI will map to multiple values:
   //
   //   1 %dst:ssub0 = FOO                <-- OtherVNI
   //   2 %src = BAR                      <-- VNI
   //   3 %dst:ssub1 = COPY killed %src    <-- Eliminate this copy.
case CR_Merge:
       break;
     case CR_Unresolved:
     case CR_Impossible:
       llvm_unreachable("Unresolved conflicts");
     }
   }
 }
 
+/// Consider the following situation when coalescing the copy between
+/// %31 and %45 at 800. (The vertical lines represent live range segments.)
+///
+///                              Main range         Subrange 0004 (sub2)
+///                              %31    %45           %31    %45
+///  544    %45 = COPY %28               +                    +
+///                                      | v1                 | v1
+///  560B bb.1:                          +                    +
+///  624        = %45.sub2               | v2                 | v2
+///  800    %31 = COPY %45        +      +             +      +
+///                               | v0                 | v0
+///  816    %31.sub1 = ...        +                    |
+///  880    %30 = COPY %31        | v1                 +
+///  928    %45 = COPY %30        |      +                    +
+///                               |      | v0                 | v0  <--+
+///  992B   ; backedge -> bb.1    |      +                    +        |
+/// 1040        = %31.sub0        +                                    |
+///                                                 This value must remain
+///                                                 live-out!
+///
+/// Assuming that %31 is coalesced into %45, the copy at 928 becomes
+/// redundant, since it copies the value from %45 back into it. The
+/// conflict resolution for the main range determines that %45.v0 is
+/// to be erased, which is ok since %31.v1 is identical to it.
+/// The problem happens with the subrange for sub2: it has to be live
+/// on exit from the block, but since 928 was actually a point of
+/// definition of %45.sub2, %45.sub2 was not live immediately prior
+/// to that definition. As a result, when 928 was erased, the value v0
+/// for %45.sub2 was pruned in pruneSubRegValues. Consequently, an
+/// IMPLICIT_DEF was inserted as a "backedge" definition for %45.sub2,
+/// providing an incorrect value to the use at 624.
+///
+/// Since the main-range values %31.v1 and %45.v0 were proved to be
+/// identical, the corresponding values in subranges must also be the
+/// same. A redundant copy is removed because it's not needed, and not
+/// because it copied an undefined value, so any liveness that originated
+/// from that copy cannot disappear. When pruning a value that started
+/// at the removed copy, the corresponding identical value must be
+/// extended to replace it.
 void JoinVals::pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask) {
   // Look for values being erased.
   bool DidPrune = false;
   for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
+    Val &V = Vals[i];
     // We should trigger in all cases in which eraseInstrs() does something.
     // match what eraseInstrs() is doing, print a message so
-    if (Vals[i].Resolution != CR_Erase &&
-        (Vals[i].Resolution != CR_Keep || !Vals[i].ErasableImplicitDef ||
-         !Vals[i].Pruned))
+    if (V.Resolution != CR_Erase &&
+        (V.Resolution != CR_Keep || !V.ErasableImplicitDef || !V.Pruned))
       continue;
 
     // Check subranges at the point where the copy will be removed.
     SlotIndex Def = LR.getValNumInfo(i)->def;
+    SlotIndex OtherDef;
+    if (V.Identical)
+      OtherDef = V.OtherVNI->def;
+
     // Print message so mismatches with eraseInstrs() can be diagnosed.
     LLVM_DEBUG(dbgs() << "\t\tExpecting instruction removal at " << Def
                       << '\n');
     for (LiveInterval::SubRange &S : LI.subranges()) {
       LiveQueryResult Q = S.Query(Def);
 
       // If a subrange starts at the copy then an undefined value has been
       // copied and we must remove that subrange value as well.
       VNInfo *ValueOut = Q.valueOutOrDead();
       if (ValueOut != nullptr && Q.valueIn() == nullptr) {
         LLVM_DEBUG(dbgs() << "\t\tPrune sublane " << PrintLaneMask(S.LaneMask)
                           << " at " << Def << "\n");
-        LIS->pruneValue(S, Def, nullptr);
+        SmallVector<SlotIndex,8> EndPoints;
+        LIS->pruneValue(S, Def, &EndPoints);
         DidPrune = true;
         // Mark value number as unused.
         ValueOut->markUnused();
+
+        if (V.Identical && S.Query(OtherDef).valueOut()) {
+          // If V is identical to V.OtherVNI (and S was live at OtherDef),
+          // then we can't simply prune V from S. V needs to be replaced
+          // with V.OtherVNI.
+          LIS->extendToIndices(S, EndPoints);
+#ifndef NDEBUG
+          // Make sure that the value at Def is really V.OtherVNI.
+          LiveRange::iterator Id = S.find(OtherDef);
+          LiveRange::iterator T = S.find(Def);
+          assert(Id != S.end() && T != S.end() && T->valno == Id->valno);
+#endif
+        }
         continue;
       }
       // If a subrange ends at the copy, then a value was copied but only
       // partially used later. Shrink the subregister range appropriately.
       if (Q.valueIn() != nullptr && Q.valueOut() == nullptr) {
         LLVM_DEBUG(dbgs() << "\t\tDead uses at sublane "
                           << PrintLaneMask(S.LaneMask) << " at " << Def
                           << "\n");

test/CodeGen/AMDGPU/coalescer-extend-pruned-subrange.mir

+# RUN: llc -mtriple=amdgcn--amdpal -mcpu=gfx803 -run-pass=simple-register-coalescing -o - %s | FileCheck -check-prefix=GCN %s
+
+# GCN: {{^body}}
+
+---
+name: foo
+tracksRegLiveness: true
+body: |
+  bb.0:
+    successors: %bb.2
+
+    %0:sreg_32_xm0 = S_MOV_B32 1
+    %1:vgpr_32 = COPY %0
+    INLINEASM &"; %1", 1, 327690, def %1, 2147483657, %1(tied-def 3)
+    %2:sreg_64 = V_CMP_NE_U32_e64 0, %1, implicit $exec
+    undef %3.sub0:sreg_128 = COPY %0
+    %3.sub1:sreg_128 = COPY %0
+    %3.sub2:sreg_128 = COPY %0
+    %4:sreg_128 = COPY %3
+    %5:vgpr_32 = V_MOV_B32_e32 -64, implicit $exec
+    %6:vreg_128 = COPY %4
+    %7:sreg_32_xm0 = S_AND_B32 target-flags(amdgpu-gotprel) 1, %2.sub0, implicit-def dead $scc
+    %8:sreg_32_xm0 = S_MOV_B32 0
+    %9:vgpr_32 = COPY %5
+    %10:vreg_128 = COPY %6
+    S_BRANCH %bb.2
+
+  bb.1:
+    %11:vgpr_32 = V_OR_B32_e32 %12.sub0, %12.sub1, implicit $exec
+    %13:vgpr_32 = V_OR_B32_e32 %11, %12.sub2, implicit $exec
+    %14:vgpr_32 = V_AND_B32_e32 1, %13, implicit $exec
+    %15:sreg_64_xexec = V_CMP_EQ_U32_e64 0, %14, implicit $exec
+    %16:vgpr_32 = V_CNDMASK_B32_e64 0, 1, %15, implicit $exec
+    BUFFER_STORE_DWORD_OFFEN_exact %16, undef %17:vgpr_32, undef %18:sreg_128, 0, 0, 0, 0, 0, implicit $exec :: (dereferenceable store 4 into constant-pool, align 1, addrspace 4)
+    S_ENDPGM
+
+  bb.2:
+    successors: %bb.3, %bb.4
+
+    %19:sreg_64 = V_CMP_EQ_U32_e64 1, %7, implicit $exec
+    %20:sreg_64 = COPY $exec, implicit-def $exec
+    %21:sreg_64 = S_AND_B64 %20, %19, implicit-def dead $scc
+    $exec = S_MOV_B64_term %21
+    SI_MASK_BRANCH %bb.4, implicit $exec
+    S_BRANCH %bb.3
+
+  bb.3:
+    successors: %bb.4
+
+    undef %22.sub0:sreg_128 = COPY %8
+    %22.sub1:sreg_128 = COPY %8
+    %22.sub2:sreg_128 = COPY %8
+    %23:sreg_128 = COPY %22
+    %24:vreg_128 = COPY %23
+    %10:vreg_128 = COPY %24
+
+  bb.4:
+    successors: %bb.5
+
+    $exec = S_OR_B64 $exec, %20, implicit-def $scc
+
+  bb.5:
+    successors: %bb.7, %bb.6
+
+    S_CBRANCH_SCC0 %bb.7, implicit undef $scc
+
+  bb.6:
+    successors: %bb.9
+
+    %12:vreg_128 = COPY %10
+    S_BRANCH %bb.9
+
+  bb.7:
+    successors: %bb.8, %bb.10
+
+    %25:vgpr_32 = V_AND_B32_e32 target-flags(amdgpu-gotprel32-hi) 1, %10.sub2, implicit $exec
+    %26:sreg_64 = V_CMP_EQ_U32_e64 1, %25, implicit $exec
+    %27:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+    %28:vreg_1 = COPY %27
+    %29:sreg_64 = COPY $exec, implicit-def $exec
+    %30:sreg_64 = S_AND_B64 %29, %26, implicit-def dead $scc
+    $exec = S_MOV_B64_term %30
+    SI_MASK_BRANCH %bb.10, implicit $exec
+    S_BRANCH %bb.8
+
+  bb.8:
+    successors: %bb.10
+
+    %31:vgpr_32 = BUFFER_LOAD_DWORD_OFFEN undef %32:vgpr_32, undef %33:sreg_128, 0, 0, 0, 0, 0, implicit $exec :: (dereferenceable load 4 from constant-pool, align 1, addrspace 4)
+    %34:sreg_64_xexec = V_CMP_NE_U32_e64 0, %31, implicit $exec
+    %35:vgpr_32 = V_CNDMASK_B32_e64 0, -1, %34, implicit $exec
+    %28:vreg_1 = COPY %35
+    S_BRANCH %bb.10
+
+  bb.9:
+    successors: %bb.11
+
+    S_BRANCH %bb.11
+
+  bb.10:
+    successors: %bb.9
+
+    $exec = S_OR_B64 $exec, %29, implicit-def $scc
+    %36:vreg_1 = COPY %28
+    %37:sreg_64_xexec = V_CMP_NE_U32_e64 0, %36, implicit $exec
+    %38:vgpr_32 = V_CNDMASK_B32_e64 0, 1, %37, implicit $exec
+    %39:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+    undef %40.sub0:vreg_128 = COPY %39
+    %40.sub1:vreg_128 = COPY %39
+    %40.sub2:vreg_128 = COPY %38
+    %41:vreg_128 = COPY %40
+    %12:vreg_128 = COPY %41
+    S_BRANCH %bb.9
+
+  bb.11:
+    successors: %bb.2, %bb.1
+
+    %42:vgpr_32 = V_ADD_I32_e32 32, %9, implicit-def dead $vcc, implicit $exec
+    V_CMP_EQ_U32_e32 0, %42, implicit-def $vcc, implicit $exec
+    %43:vgpr_32 = COPY %42
+    $vcc = S_AND_B64 $exec, killed $vcc, implicit-def dead $scc
+    %44:vreg_128 = COPY %12
+    %9:vgpr_32 = COPY %43
+    %10:vreg_128 = COPY %44
+    S_CBRANCH_VCCNZ %bb.1, implicit killed $vcc
+    S_BRANCH %bb.2
+
+...

test/CodeGen/AMDGPU/coalescer-identical-values-undef.mir

+# RUN: llc -mtriple=amdgcn--amdpal -run-pass=simple-register-coalescing -o - %s | FileCheck %s
+
+# Check that this doesn't crash. Check for some legitimate output.
+# CHECK: S_CBRANCH_SCC1
+
+---
+name: fred
+tracksRegLiveness: true
+body: |
+  bb.0:
+    successors: %bb.1, %bb.2
+    liveins: $sgpr4
+    undef %0.sub2:sreg_128 = COPY $sgpr4
+    %3 = IMPLICIT_DEF
+    S_CBRANCH_SCC1 %bb.2, implicit undef $scc
+
+  bb.1:
+    successors: %bb.2
+    %0.sub0:sreg_128 = COPY %0.sub2
+    %0.sub1:sreg_128 = COPY %0.sub2
+    %1:sreg_128 = COPY %0
+    %2:sreg_128 = COPY %0
+    %0:sreg_128 = COPY %2
+    %3:sreg_128 = COPY %1
+
+  bb.2:
+    $sgpr1 = COPY %3
+    $sgpr2 = COPY %0.sub2
+...

test/CodeGen/AMDGPU/coalescing-with-subregs-in-loop-bug.mir

+# RUN: llc -mtriple=amdgcn--amdpal -mcpu=gfx803 -run-pass=simple-register-coalescing,rename-independent-subregs %s -o - | FileCheck -check-prefix=GCN %s
+
+# This test is for a bug where the following happens:
+#
+# Inside the loop, %29.sub2 is used in a V_LSHLREV whose result is then used
+# in an LDS read. %29 is a 128 bit value that is linked by copies to
+# %45 (from phi elimination), %28 (the value in the loop pre-header),
+# %31 (defined and subreg-modified in the loop, and used after the loop)
+# and %30:
+#
+#     %45:vreg_128 = COPY killed %28
+# bb.1:
+#     %29:vreg_128 = COPY killed %45
+#     %39:vgpr_32 = V_LSHLREV_B32_e32 2, %29.sub2, implicit $exec
+#     %31:vreg_128 = COPY killed %29
+#     %31.sub1:vreg_128 = COPY %34
+#     %30:vreg_128 = COPY %31
+#     %45:vreg_128 = COPY killed %30
+#     S_CBRANCH_EXECNZ %bb.39, implicit $exec
+#     S_BRANCH %bb.40
+# bb.2:
+#     undef %32.sub0:vreg_128 = COPY killed %31.sub0
+#
+# So this coalesces together into a single 128 bit value whose sub1 is modified
+# in the loop, but the sub2 used in the V_LSHLREV is not modified in the loop.
+#
+# The bug is that the coalesced value has a L00000004 subrange (for sub2) that
+# says that it is not live up to the end of the loop block. The symptom is that
+# Rename Independent Subregs separates sub2 into its own register, and it is
+# not live round the loop, so that pass adds an IMPLICIT_DEF for it just before
+# the loop backedge.
+
+# GCN: bb.1:
+# GCN: V_LSHLREV_B32_e32 2, [[val:%[0-9][0-9]*]].sub2
+# GCN-NOT: [[val]]:vreg_128 = IMPLICIT_DEF
+
+---
+name: _amdgpu_cs_main
+tracksRegLiveness: true
+body: |
+  bb.0:
+    successors: %bb.1
+
+    %3:sgpr_32 = S_MOV_B32 0
+    undef %19.sub1:vreg_128 = COPY undef %3
+    %4:sgpr_32 = S_MOV_B32 1
+    %5:sgpr_32 = S_MOV_B32 2
+    %11:sreg_32_xm0 = S_MOV_B32 255
+    undef %28.sub0:vreg_128 = COPY killed %3
+    %28.sub1:vreg_128 = COPY killed %4
+    %28.sub2:vreg_128 = COPY killed %11
+    %28.sub3:vreg_128 = COPY killed %5
+    %2:sreg_64 = S_MOV_B64 0
+    %34:sreg_32 = S_MOV_B32 7
+    %37:vreg_128 = COPY undef %42:vreg_128
+    %43:sreg_64 = COPY killed %2
+    %44:vreg_128 = COPY killed %37
+    %45:vreg_128 = COPY killed %28
+
+  bb.1:
+    successors: %bb.1, %bb.2
+
+    %29:vreg_128 = COPY killed %45
+    %36:vreg_128 = COPY killed %44
+    %0:sreg_64 = COPY killed %43
+    %39:vgpr_32 = V_LSHLREV_B32_e32 2, %29.sub2, implicit $exec
+    %41:vgpr_32 = V_ADD_I32_e32 1152, %39, implicit-def dead $vcc, implicit $exec
+    $m0 = S_MOV_B32 -1
+    %12:vreg_64 = DS_READ2_B32 killed %41, 0, 1, 0, implicit $m0, implicit $exec
+    %13:vreg_64 = DS_READ2_B32 %39, -112, -111, 0, implicit $m0, implicit $exec
+    %14:vreg_64 = DS_READ2_B32 %39, 0, 1, 0, implicit $m0, implicit $exec
+    %40:vgpr_32 = V_ADD_I32_e32 1160, %39, implicit-def dead $vcc, implicit $exec
+    %15:vreg_64 = DS_READ2_B32 killed %40, 0, 1, 0, implicit $m0, implicit $exec
+    %16:vreg_64 = DS_READ2_B32 %39, -110, -109, 0, implicit $m0, implicit $exec
+    %17:vreg_64 = DS_READ2_B32 %39, 2, 3, 0, implicit $m0, implicit $exec
+    undef %35.sub1:vreg_128 = COPY undef %34
+    %31:vreg_128 = COPY killed %29
+    %31.sub1:vreg_128 = COPY %34
+    %38:vgpr_32 = V_ADD_I32_e32 1, %36.sub0, implicit-def dead $vcc, implicit $exec
+    %18:sreg_64 = V_CMP_LT_I32_e64 5, %38, implicit $exec
+    %1:sreg_64 = S_OR_B64 killed %18, killed %0, implicit-def $scc
+    %30:vreg_128 = COPY %31
+    %43:sreg_64 = COPY %1
+    %44:vreg_128 = COPY %35
+    %45:vreg_128 = COPY killed %30
+    $exec = S_ANDN2_B64_term $exec, %1
+    S_CBRANCH_EXECNZ %bb.1, implicit $exec
+    S_BRANCH %bb.2
+
+  bb.2:
+    $exec = S_OR_B64 $exec, killed %1, implicit-def $scc
+    %33:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+    undef %32.sub0:vreg_128 = COPY killed %31.sub0
+    %32.sub2:vreg_128 = COPY %33
+    $vgpr0_vgpr1_vgpr2_vgpr3 = COPY %32:vreg_128
+    S_ENDPGM
+
+...