Bug? Coalescing & Updating Subreg Intervals

I have a question about what is going on at line 754 of
SimpleRegisterCoalescing.cpp. The comment says we are
updating the live intervals for subregisters. This happens when
we coalesce to a physical register.

Now, I read that as, "merge in the range information from the
eliminated live interval to the subregister live interval," but that
appears to not be what happens.

In my case, I have the following two intervals which are being
coalesced:

%reg1026,0 = [458,5168:0 [0])[5180,15248:0 [0]) 0@458

%reg15,inf = [0,10:0 [0])[10,458:87 [0])[938,942:1 [0])[942,943:2 [0])
[962,966:3 [0])[966,967:4 [0])[1242,1246:5 [0])[1246,1247:6 [0])[1266,1270:7
[0])[1270,1271:8 [0])[1578,1582:9 [0])[1582,1583:10 [0])[1602,1606:11 [0])
[1606,1607:12 [0])[2314,2318:13 [0])[2318,2319:14 [0])[2338,2342:15 [0])
[2342,2343:16 [0])[3366,3370:17 [0])[3370,3371:18 [0])[3390,3394:19 [0])
[3394,3395:20 [0])[3642,3646:21 [0])[3646,3647:22 [0])[3666,3670:23 [0])
[3670,3671:24 [0])[3942,3946:25 [0])[3946,3947:26 [0])[3966,3970:27 [0])
[3970,3971:28 [0])[6098,6102:29 [0])[6102,6103:30 [0])[6126,6130:31 [0])
[6130,6131:32 [0])[6390,6394:33 [0])[6394,6395:34 [0])[6418,6422:35 [0])
[6422,6423:36 [0])[6714,6718:37 [0])[6718,6719:38 [0])[6742,6746:39 [0])
[6746,6747:40 [0])[7434,7438:41 [0])[7438,7439:42 [0])[7462,7466:43 [0])
[7466,7467:44 [0])[8446,8450:45 [0])[8450,8451:46 [0])[8474,8478:47 [0])
[8478,8479:48 [0])[8710,8714:49 [0])[8714,8715:50 [0])[8738,8742:51 [0])
[8742,8743:52 [0])[8998,9002:53 [0])[9002,9003:54 [0])[9022,9026:55 [0])
[9026,9027:56 [0])[10490,10494:57 [0])[10494,10495:58 [0])[10518,10522:59
[0])[10522,10523:60 [0])[10782,10786:61 [0])[10786,10787:62 [0])
[10810,10814:63 [0])[10814,10815:64 [0])[11106,11110:65 [0])[11110,11111:66
[0])[11134,11138:67 [0])[11138,11139:68 [0])[11826,11830:69 [0])
[11830,11831:70 [0])[11854,11858:71 [0])[11858,11859:72 [0])[12838,12842:73
[0])[12842,12843:74 [0])[12866,12870:75 [0])[12870,12871:76 [0])
[13102,13106:77 [0])[13106,13107:78 [0])[13130,13134:79 [0])[13134,13135:80
[0])[13390,13394:81 [0])[13394,13395:82 [0])[13414,13418:83 [0])
[13418,13419:84 [0])[15350,15374:88 [0])[15374,15382:85 [0])[15382,15383:86
[0]) 0@0-(10) 1@938-(942) 2@942-(943) 3@962-(966) 4@966-(967) 5@1242-(1246)
6@1246-(1247) 7@1266-(1270) 8@1270-(1271) 9@1578-(1582) 10@1582-(1583)
11@1602-(1606) 12@1606-(1607) 13@2314-(2318) 14@2318-(2319) 15@2338-(2342)
16@2342-(2343) 17@3366-(3370) 18@3370-(3371) 19@3390-(3394) 20@3394-(3395)
21@3642-(3646) 22@3646-(3647) 23@3666-(3670) 24@3670-(3671) 25@3942-(3946)
26@3946-(3947) 27@3966-(3970) 28@3970-(3971) 29@6098-(6102) 30@6102-(6103)
31@6126-(6130) 32@6130-(6131) 33@6390-(6394) 34@6394-(6395) 35@6418-(6422)
36@6422-(6423) 37@6714-(6718) 38@6718-(6719) 39@6742-(6746) 40@6746-(6747)
41@7434-(7438) 42@7438-(7439) 43@7462-(7466) 44@7466-(7467) 45@8446-(8450)
46@8450-(8451) 47@8474-(8478) 48@8478-(8479) 49@8710-(8714) 50@8714-(8715)
51@8738-(8742) 52@8742-(8743) 53@8998-(9002) 54@9002-(9003) 55@9022-(9026)
56@9026-(9027) 57@10490-(10494) 58@10494-(10495) 59@10518-(10522)
60@10522-(10523) 61@10782-(10786) 62@10786-(10787) 63@10810-(10814)
64@10814-(10815) 65@11106-(11110) 66@11110-(11111) 67@11134-(11138)
68@11138-(11139) 69@11826-(11830) 70@11830-(11831) 71@11854-(11858)
72@11858-(11859) 73@12838-(12842) 74@12842-(12843) 75@12866-(12870)
76@12870-(12871) 77@13102-(13106) 78@13106-(13107) 79@13130-(13134)
80@13134-(13135) 81@13390-(13394) 82@13394-(13395) 83@13414-(13418)
84@13418-(13419) 85@15374-(15382) 86@15382-(15383) 87@? 88@?

MergeInClobberRanges comes along and sees that [458,5168:0 [0])
from %reg1026 overlaps [938,942:1 [0]) from %reg15. It then proceeds
to add [458,938:89 [0]) to %reg15.

It then moves on to the next LiveRange of %reg1026.

Huh? What happened to the rest of [458,5168:0 [0])? Doesn't the subreg live
interval need to contain this whole LiveRange?

Or am I not understanding what this part of the coalescing code does?

I discovered this through an assert I put into some of my own code. I want to
know if that assert is bogus or if there's a bug here.

Thanks!

                                            -Dave

A little more information: the assert checks that after coalescing two nodes,
all subregister live intervals for the register coaelsced to now interfere
with whatever the eliminated live interval interfered with, since the
superregister live interval now contains information from the eliminated live
interval and thus it interferes with whatever the eliminated live interval
interfered with (and thuis so should the subregister live interval, correct?).
In my case, this test _fails_, which I found to be unexpected.

In other words, after coalescing, should it be the case that subregister
intervals contain at least all of the range information that was contained
in any eliminated intervals when those eliminated intervals were coalesced
to the subregister's superregister?

If not, which is this code supposed to be doing?

                                                 -Dave

Oops, I was inaccruate. We're actually coalescing to %reg80. %reg15
is a subreg of %reg80.

                                               -Dave

I discovered this through an assert I put into some of my own code. I want
to know if that assert is bogus or if there's a bug here.

A little more information: the assert checks that after coalescing two nodes,
all subregister live intervals for the register coaelsced to now interfere
with whatever the eliminated live interval interfered with, since the
superregister live interval now contains information from the eliminated live
interval and thus it interferes with whatever the eliminated live interval
interfered with (and thuis so should the subregister live interval, correct?).
In my case, this test _fails_, which I found to be unexpected.

In other words, after coalescing, should it be the case that subregister
intervals contain at least all of the range information that was contained
in any eliminated intervals when those eliminated intervals were coalesced
to the subregister's superregister?

Right. The code is being conservative. It's saying all of the entirety of the superregister's live interval must also be in the subregister's live interval. i.e. When the superregister is live, the subregister must be live.

Evan

Ok, but that is NOT what's happening in this case.

Also, LiveIntervalAnalysis doesn't do any subregister checks as
far as I can tell. It's certainly not the case that subregister
intervals contain all of the information their supperregister's
interval contains.

So is this just supposed to be a conservative update for the
purposes of coalescing?

In any event, it seems not to be working right if what you
describe is supposed to be happening.

Given the two intervals in my example, which should happen
with the two overlappring ranges

%reg1026: [458,5168:0 [0])
%reg15: [938,942:1 [0])

My assumption was that after MergeInClobberRanges that %reg15
would contain [458,5168:0 [0]). But it doesn't.

                                                  -Dave

In other words, after coalescing, should it be the case that
subregister
intervals contain at least all of the range information that was
contained
in any eliminated intervals when those eliminated intervals were
coalesced
to the subregister's superregister?

Right. The code is being conservative. It's saying all of the entirety
of the superregister's live interval must also be in the subregister's
live interval. i.e. When the superregister is live, the subregister
must be live.

Ok, but that is NOT what's happening in this case.

Also, LiveIntervalAnalysis doesn't do any subregister checks as
far as I can tell. It's certainly not the case that subregister
intervals contain all of the information their supperregister's
interval contains.

SimpleRegisterCoalescing::JoinIntervals(). When coalescing a physical register with a virtual one the first thing it check is sub-registers.

So is this just supposed to be a conservative update for the
purposes of coalescing?

In any event, it seems not to be working right if what you
describe is supposed to be happening.

Given the two intervals in my example, which should happen
with the two overlappring ranges

%reg1026: [458,5168:0 [0])
%reg15: [938,942:1 [0])

My assumption was that after MergeInClobberRanges that %reg15
would contain [458,5168:0 [0]). But it doesn't.

So this is the call site?

     // Update the liveintervals of sub-registers.
     for (const unsigned *AS = tri_->getSubRegisters(DstReg); *AS; ++AS)
       li_->getOrCreateInterval(*AS).MergeInClobberRanges(*ResSrcInt,
                                                  li_- >getVNInfoAllocator());

Can you take a look at MergeInClobberRanges() to see what is going on? Otherwise, please file a bug with a test case.

Evan

> Also, LiveIntervalAnalysis doesn't do any subregister checks as
> far as I can tell. It's certainly not the case that subregister
> intervals contain all of the information their supperregister's
> interval contains.

SimpleRegisterCoalescing::JoinIntervals(). When coalescing a physical
register with a virtual one the first thing it check is sub-registers.

Right. I'm just wondering why LiveIntervalAnalysis doesn't do this as well.
It's not a big deal, because I think LiveIntervalAnalysis is ok as-is. Just
curious.

> My assumption was that after MergeInClobberRanges that %reg15
> would contain [458,5168:0 [0]). But it doesn't.

So this is the call site?

     // Update the liveintervals of sub-registers.
     for (const unsigned *AS = tri_->getSubRegisters(DstReg); *AS; ++AS)
       li_->getOrCreateInterval(*AS).MergeInClobberRanges(*ResSrcInt,
                                                  li_-

Yep.

>getVNInfoAllocator());

Can you take a look at MergeInClobberRanges() to see what is going on?
Otherwise, please file a bug with a test case.

Yes. I think I know what's going on. This happens in SPEC 2006 bwaves on the
block_solver.f source file. This is of course using our frontend and
optimizer, so it may not be reproducable for anyone else. I'll see if I can
generate a .ll testcase. The llvm tools probably won't fail because they
don't contain the assert that I have in my code.

Here are the steps of what happens in MergeInClobberRanges:

1. IP = [0,10:0 [0]) (begin() for %reg15)

2. I = [458,5168:0 [0]) (begin() for %reg1026)

3. Start = 458, End = 5168

4. IP = [938,942:1 [0]) (std::upper_bound(IP, end(), Start)

5. IP != begin() && IP[-1].end > Start is FALSE

6. IP != end() && End > IP->start is TRUE

7. End = 938 (IP->start)

8. Start == End is FALSE

9. IP = [458,938:89 [0])
    (addRangeFrom(LiveRange(Start, End, ClobberValNo), IP))

10. We are now done processing [458,5168:0 [0]) from %reg1026
    but we didn't process the part of the interval AFTER 938, where
    the overlap with %reg15 ends!

This comment seems strange to me:

// If the end of this range overlaps with an existing liverange, trim it.

There's a similar comment about trimming the start of the Clobbers live range.

Why do we do this trimming? The comment seems to say we don't care about
the rest of the live range from Clobbers (%reg1026 in this case) but that
doesn't match with our expectation that %reg15 will contain all of the live
range information from %reg1026.

So what's the right answer?

                                                  -Dave

I'll add that merging this correctly could get tricky. %reg15 contains the
following live ranges, all of which overlap [458,5168:0 [0]) from %reg1026:

[938,942:1 [0])[942,943:2 [0])[962,966:3 [0])[966,967:4 [0])[1242,1246:5 [0])
[1246,1247:6 [0])[1266,1270:7 [0])[1270,1271:8 [0])[1578,1582:9 [0])
[1582,1583:10 [0])[1602,1606:11 [0])[1606,1607:12 [0])[2314,2318:13 [0])
[2318,2319:14 [0])[2338,2342:15 [0])[2342,2343:16 [0])[3366,3370:17 [0])
[3370,3371:18 [0])[3390,3394:19 [0])[3394,3395:20 [0])[3642,3646:21 [0])
[3646,3647:22 [0])[3666,3670:23 [0])[3670,3671:24 [0])[3942,3946:25 [0])
[3946,3947:26 [0])[3966,3970:27 [0])[3970,3971:28 [0])

They all have different value numbers. How should this get merged in this
case? Do we process each of these live ranges against [458,5168:0 [0])
using the existing code?

What do we do with the holes between them? Fill them with new ranges
that have an unknown definition value?

                                                     -Dave

Why do we do this trimming? The comment seems to say we don't care about
the rest of the live range from Clobbers (%reg1026 in this case) but that
doesn't match with our expectation that %reg15 will contain all of the live
range information from %reg1026.

I'll add that merging this correctly could get tricky. %reg15 contains the
following live ranges, all of which overlap [458,5168:0 [0]) from %reg1026:

[938,942:1 [0])[942,943:2 [0])[962,966:3 [0])[966,967:4 [0])[1242,1246:5 [0])
[1246,1247:6 [0])[1266,1270:7 [0])[1270,1271:8 [0])[1578,1582:9 [0])
[1582,1583:10 [0])[1602,1606:11 [0])[1606,1607:12 [0])[2314,2318:13 [0])
[2318,2319:14 [0])[2338,2342:15 [0])[2342,2343:16 [0])[3366,3370:17 [0])
[3370,3371:18 [0])[3390,3394:19 [0])[3394,3395:20 [0])[3642,3646:21 [0])
[3646,3647:22 [0])[3666,3670:23 [0])[3670,3671:24 [0])[3942,3946:25 [0])
[3946,3947:26 [0])[3966,3970:27 [0])[3970,3971:28 [0])

They all have different value numbers. How should this get merged in this
case? Do we process each of these live ranges against [458,5168:0 [0])
using the existing code?

What do we do with the holes between them? Fill them with new ranges
that have an unknown definition value?

All of the new ranges, including values, should be from the new val# defined by an unknown instruction. This does prevent further coalescing but should be correct.

Evan

Ok. I'm working on a fix for this. I think I'm close.

                                           -Dave