[Subreg liveness] Assertion `INext != E && "Must have following segment"' failed

[Quuxplusone]

Bugzilla Link	PR41372
Status	RESOLVED FIXED
Importance	P enhancement
Reported by	Jonas Paulsson (paulsson@linux.vnet.ibm.com)
Reported on	2019-04-04 06:29:31 -0700
Last modified on	2019-12-07 16:05:47 -0800
Version	trunk
Hardware	PC Linux
CC	kparzysz@quicinc.com, llvm-bugs@lists.llvm.org, paulsson@linux.vnet.ibm.com, quentin.colombet@gmail.com, uweigand@de.ibm.com
Fixed by commit(s)
Attachments	tc_musthavefollseg.ll (2285 bytes, text/plain) tc_musthavefollseg_unreduced.bc (637352 bytes, application/octet-stream) regcoal.patch (1182 bytes, text/plain)
Blocks
Blocked by
See also

Created attachment 21726
reduced testcase

llc -mcpu=z13 -O3 -o out.s -misched=ilpmin -systemz-subreg-liveness
tc_musthavefollseg.ll

llc: llvm/llvm-dev/lib/CodeGen/LiveIntervals.cpp:1142: void
llvm::LiveIntervals::HMEditor::handleMoveDown(llvm::LiveRange&)
: Assertion `INext != E && "Must have following segment"' failed.

Stack dump:
0.      Program arguments: llc -mcpu=z13 -O3 -o out.s -misched=ilpmin -systemz-
subreg-liveness tc_musthavefollseg.ll
2.      Running pass 'Machine Instruction Scheduler' on function '@main'

...
 #9 0x000002aa3522b370 llvm::LiveIntervals::HMEditor::updateRange(llvm::LiveRange&, unsigned int, llvm::LaneBitmask)
#10 0x000002aa3522bae4
llvm::LiveIntervals::HMEditor::updateAllRanges(llvm::MachineInstr*)
#11 0x000002aa3522eb50 llvm::LiveIntervals::handleMove(llvm::MachineInstr&,
bool)
#12 0x000002aa353563d4
llvm::ScheduleDAGMI::moveInstruction(llvm::MachineInstr*,
llvm::MachineInstrBundleIterator<llvm::MachineInstr, false>)
...

[Quuxplusone]

Attached tc_musthavefollseg.ll (2285 bytes, text/plain): reduced testcase

[Quuxplusone]

Attached tc_musthavefollseg_unreduced.bc (637352 bytes, application/octet-stream): unreduced test case, llc input

[Quuxplusone]

Ping! Saw this again this week in testing. Original test case still failing.

[Quuxplusone]

Ping! Saw this again this week in testing. Original test case still failing.

[Quuxplusone]

Ping! Saw this again this week in testing. Original test case still failing.

[Quuxplusone]

Ping! Saw this again this week in testing. Original test case still failing.

[Quuxplusone]

(In reply to Jonas Paulsson from comment #5)
> Ping! Saw this again this week in testing. Original test case still failing.

Thanks Jonas for the reminder. I’ll try to look at it this week.

[Quuxplusone]

I can reproduce the problem, looking.

[Quuxplusone]

At first glance, I'd say the problem is that we have a subrange that is dead,
but we fail to see that and thus try to extend the live-range to the next
segment, which, since it is dead, does not exist.

The problematic sequence is this one:
  %5:gr64bit = LGHI 25
  %5.subreg_l32:gr64bit = MSFI %5.subreg_l32:gr64bit(tied-def 0), -117440512

Here subreg_h32 is never used, yet the (sub)live-range is not mark as dead:
 %5 L00000001:  [160r,176r:0)  0@160r

Thus, when we try to update 176r to the new index, we fail to see that 176r was
the last use and look for the next segment.

[Quuxplusone]

For the record the full live-interval for %5 at the time of the assert looks
like this:
main range: [160r,240r:0)[240r,264B:1)[288B,432r:1)[432r,448r:2)[576B,640B:1)
0@160r 1@240r 2@432r
L00000008: [232r,240r:0)[240r,264B:1)[288B,432r:1)[432r,448r:2)[576B,640B:1)
0@232r 1@240r 2@432r
L00000001: [160r,176r:0)  0@160r weight:0.000000e+00

Notice how L00000001 goes from 160r to 176r, whereas at this point, there is no
instruction at 176r. This happens because L00000001 is actually not used by
what was at 176r and thus doesn't get updated when we move it around.

Anyway, that's a side problem in the sense that if that lane was marked as dead
to beginning with, the use index wouldn't be here, so no update would be
required.

Given those live-ranges are created during register coalescing, I am going to
look at why we don't mark that lane as dead.

[Quuxplusone]

Attached regcoal.patch (1182 bytes, text/plain): Tentative fix

[Quuxplusone]

Note to myself: would be better if I can mark the dead lanes in refineSubRanges.

[Quuxplusone]

I'll go with the tentative fix I've already attached.
Doing the right thing in LiveInterval::refineSubRanges is problematic for two
reasons:
1. It may incur in increase in compile time that most users of this function
don't need.
2. The IR needs to reflect what the live intervals are supposed to represent,
but the register coalescer calls that function before it updates the IR.

We could reuse LiveIntervals::shrinkToUses as well after the IR has been
updated, but right now, the rematerialization doesn't call that function so,
same problem: potential increase in compile time. Given we know specifically
what needs to happen for the remat case, that compile time increase is not
really worth it.

[Quuxplusone]

Should be fixed with:
To https://github.com/llvm/llvm-project.git
   1f822f212cd..2ec71ea7c74  2ec71ea7c74df20983031c6e1be07b14da0e9109 -> master

[Quuxplusone]

@qcolombet:

Thank you for fixing this :-)

I see that https://bugs.llvm.org/show_bug.cgi?id=35574 now also seems fixed ("Live segment doesn't end at a valid instruction"). Do you believe your fix also handles this assertion? I saw a new test this week which also went away with your latest patch included...

[Quuxplusone]

(In reply to Jonas Paulsson from comment #14)
> @qcolombet:
>
> Thank you for fixing this :-)
>
> I see that https://bugs.llvm.org/show_bug.cgi?id=35574 now also seems fixed
> ("Live segment doesn't end at a valid instruction"). Do you believe your fix
> also handles this assertion? I saw a new test this week which also went away
> with your latest patch included...

Yeah, that would make sense that this patch fixes a “doesn’t end at a valid
instruction“ assert.

Happy to help!

Thanks for your patience.