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

On Wednesday 20 February 2008 14:14, David Greene wrote:
> 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?

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

                                                 -Dave

On Wednesday 20 February 2008 14:14, David Greene wrote:
> In my case, I have the following two intervals which are being
> coalesced:
>
> %reg1026,0 = [458,5168:0 [0])[5180,15248:0 [0])  0 at 458
>
> %reg15,inf = [0,10:0 [0])[10,458:87 [0])[938,942:1 [0])[942,943:2 [0])
Oops, I was inaccruate.  We're actually coalescing to %reg80.  %reg15
is a subreg of %reg80.

                                               -Dave

On Feb 20, 2008, at 12:25 PM, David Greene wrote:
> On Wednesday 20 February 2008 14:14, David Greene wrote:
>
>> 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
>
>
> If not, which is this code supposed to be doing?
>
>                                                 -Dave
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev