Page MenuHomePhabricator

LIS: fix handleMove to properly extend main range
ClosedPublic

Authored by rampitec on Jun 30 2020, 3:00 PM.

Details

Summary

handleMoveDown or handleMoveUp cannot properly repair a main
range of a LiveInterval since they only get LiveRange. There
is a problem if certain use has moved few segments away and
there is a hole in the main range in between of these two
locations. We may get a SubRange with a very extended Segment
spanning several Segments of the main range and also spanning
that hole. If that happens then we end up with the main range
not covering its SubRange which is an error.

It might be possible to attempt fixing the main range in place
just between of the old and new index by extending all of its
Segments in between, but it is unclear this logic will be
faster than just straight constructMainRangeFromSubranges,
which itself is pretty cheap since it only contains interval
logic. That will also require shrinkToUses() call after which
is probably even more expensive.

In the test second move is from 64B to 92B for the sub1.
Subrange is correctly fixed:

L000000000000000C [16r,32B:0)[32B,92r:1) 0@16r 1@32B-phi

But the main range has a hole in between 80d and 88r after
updateRange():

%1 [16r,32B:0)[32B,80r:4)[80r,80d:3)[88r,96r:1)[96r,160B:2)

Since source position is 64B this segment is not even considered
by the updateRange().

Diff Detail

Event Timeline

rampitec created this revision.Jun 30 2020, 3:00 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 30 2020, 3:00 PM

If there are better ideas I would be happy to hear!

I also believe that will happen extremely rare, otherwise we would have already hit this problem. So the main overhead is really covers() checks.

arsenm added inline comments.Jul 6 2020, 12:42 PM
llvm/lib/CodeGen/LiveIntervals.cpp
1014

Needs a comment explaining this

rampitec updated this revision to Diff 275817.Jul 6 2020, 1:14 PM
rampitec marked an inline comment as done.

Added comment.

Can you please add a LiveInterval dump (possibly truncated) for the test before and after each move to this review? It's a bit hard to follow what happens there.

Can you please add a LiveInterval dump (possibly truncated) for the test before and after each move to this review? It's a bit hard to follow what happens there.

Sure! This is the LIS at each step w/o this patch:

Before 1st move:

%1 [16r,32B:0)[32B,80r:4)[80r,80d:3)[96r,112r:1)[112r,160B:2)  0@16r 1@96r 2@112r 3@80r 4@32B-phi
L000000000000000C [16r,32B:0)[32B,64r:1)  0@16r 1@32B-phi
L00000000000000C0 [16r,16d:0)  0@16r
L0000000000000003 [16r,16d:1)[96r,96d:0)  0@96r 1@16r
L0000000000000030 [16r,32B:2)[32B,48r:3)[80r,80d:1)[112r,160B:0)  0@112r 1@80r 2@16r 3@32B-phi
weight:0.000000e+00
%2 [48r,80r:0)  0@48r weight:0.000000e+00
%3 [64r,64d:0)  0@64r weight:0.000000e+00
RegMasks:
********** MACHINEINSTRS **********
# Machine code for function func: NoPHIs

0B      bb.0:
          successors: %bb.1(0x80000000); %bb.1(100.00%)

16B       %1:sgpr_128 = IMPLICIT_DEF

32B     bb.1:
        ; predecessors: %bb.0, %bb.1
          successors: %bb.1(0x40000000), %bb.2(0x40000000); %bb.1(50.00%), %bb.2(50.00%)

48B       %2:sgpr_32 = COPY %1.sub2:sgpr_128
64B       dead %3:sgpr_32 = COPY %1.sub1:sgpr_128
80B       dead %1.sub2:sgpr_128 = COPY %2:sgpr_32
96B       %1.sub0:sgpr_128 = IMPLICIT_DEF
112B      %1.sub2:sgpr_128 = IMPLICIT_DEF
128B      S_CBRANCH_SCC1 %bb.1, implicit undef $scc
144B      S_BRANCH %bb.2

160B    bb.2:
        ; predecessors: %bb.1

Before 2nd move (still correct):

%1 [16r,32B:0)[32B,80r:4)[80r,80d:3)[88r,96r:1)[96r,160B:2)  0@16r 1@88r 2@96r 3@80r 4@32B-phi
L000000000000000C [16r,32B:0)[32B,64r:1)  0@16r 1@32B-phi
L00000000000000C0 [16r,16d:0)  0@16r
L0000000000000003 [16r,16d:1)[96r,96d:0)  0@96r 1@16r
L0000000000000030 [16r,32B:2)[32B,48r:3)[80r,80d:1)[88r,160B:0)  0@88r 1@80r 2@16r 3@32B-phi
weight:0.000000e+00
%2 [48r,80r:0)  0@48r weight:0.000000e+00
%3 [64r,64d:0)  0@64r weight:0.000000e+00
RegMasks:
********** MACHINEINSTRS **********
# Machine code for function func: NoPHIs

0B      bb.0:
          successors: %bb.1(0x80000000); %bb.1(100.00%)

16B       %1:sgpr_128 = IMPLICIT_DEF

32B     bb.1:
        ; predecessors: %bb.0, %bb.1
          successors: %bb.1(0x40000000), %bb.2(0x40000000); %bb.1(50.00%), %bb.2(50.00%)

48B       %2:sgpr_32 = COPY %1.sub2:sgpr_128
64B       dead %3:sgpr_32 = COPY %1.sub1:sgpr_128
80B       dead %1.sub2:sgpr_128 = COPY %2:sgpr_32
88B       %1.sub2:sgpr_128 = IMPLICIT_DEF
96B       %1.sub0:sgpr_128 = IMPLICIT_DEF
128B      S_CBRANCH_SCC1 %bb.1, implicit undef $scc
144B      S_BRANCH %bb.2

160B    bb.2:
        ; predecessors: %bb.1

After 2nd move from 64B to 92B, LIS is broken:

%1 [16r,32B:0)[32B,80r:4)[80r,80d:3)[88r,96r:1)[96r,160B:2)  0@16r 1@88r 2@96r 3@80r 4@32B-phi
L000000000000000C [16r,32B:0)[32B,92r:1)  0@16r 1@32B-phi
L00000000000000C0 [16r,16d:0)  0@16r
L0000000000000003 [16r,16d:1)[96r,96d:0)  0@96r 1@16r
L0000000000000030 [16r,32B:2)[32B,48r:3)[80r,80d:1)[88r,160B:0)  0@88r 1@80r 2@16r 3@32B-phi
weight:0.000000e+00
%2 [48r,80r:0)  0@48r weight:0.000000e+00
%3 [92r,92d:0)  0@92r weight:0.000000e+00
RegMasks:
********** MACHINEINSTRS **********
# Machine code for function func: NoPHIs

0B      bb.0:
          successors: %bb.1(0x80000000); %bb.1(100.00%)

16B       %1:sgpr_128 = IMPLICIT_DEF

32B     bb.1:
        ; predecessors: %bb.0, %bb.1
          successors: %bb.1(0x40000000), %bb.2(0x40000000); %bb.1(50.00%), %bb.2(50.00%)

48B       %2:sgpr_32 = COPY %1.sub2:sgpr_128
80B       dead %1.sub2:sgpr_128 = COPY %2:sgpr_32
88B       %1.sub2:sgpr_128 = IMPLICIT_DEF
92B       dead %3:sgpr_32 = COPY %1.sub1:sgpr_128
96B       %1.sub0:sgpr_128 = IMPLICIT_DEF
128B      S_CBRANCH_SCC1 %bb.1, implicit undef $scc
144B      S_BRANCH %bb.2

160B    bb.2:
        ; predecessors: %bb.1
*** Bad machine code: A Subrange is not covered by the main range ***
- function:    func
- interval:    %1 [16r,32B:0)[32B,80r:4)[80r,80d:3)[88r,96r:1)[96r,160B:2)  0@16r 1@88r 2@96r 3@80r 4@32B-phi L000000000000000C [16r,32B:0)[32B,92r:1)  0@16r 1@32B-phi L00000000000000C0 [16r,16d:0)  0@16r L0000000000000003 [16r,16d:1)[96r,96d:0)  0@96r 1@16r L0000000000000030 [16r,32B:2)[32B,48r:3)[80r,80d:1)[88r,160B:0)  0@88r 1@80r 2@16r 3@32B-phi weight:0.000000e+00
LLVM ERROR: Found 1 machine code errors.

The difference after the patch which occurs after the 2nd move:

%1 [16r,32B:0)[32B,80r:4)[80r,88r:3)[88r,96r:2)[96r,160B:1)  0@16r 1@96r 2@88r 3@80r 4@32B-phi

I understood your patch. Generally I think patching LIS with cleared undef flags ins't right at first place because the semantic of register lifetime is ruined. After the first move there should be an undef flag set at the %1.sub2 = IMPLICIT_DEF instruction which would break lives of all subregs live at this point. Can we drop updating LIS during scheduling and recreate it from scratch? Or may be fully recreate only the intervals for the registers involved in moves when the undef flag is patched after scheduling?

vpykhtin accepted this revision.Jul 7 2020, 9:36 AM

Given than the condition here is rare, I'm ok with the patch, reworking undef handling in scheduler is a massive work.

This revision is now accepted and ready to land.Jul 7 2020, 9:36 AM

Given than the condition here is rare, I'm ok with the patch, reworking undef handling in scheduler is a massive work.

Right. Scheduler deliberately drops undef flags before the scheduling. To recreate them in the middle of the scheduling would be against the concept. I assume there is nothing after the scheduler which needs them. Moreover it looks like complete recompute of an LI in the middle of the scheduling is expensive and recompute of just some will simply result in an incosistent LIS.

This revision was automatically updated to reflect the committed changes.