Possible LiveInterval Bug

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Possible LiveInterval Bug

dag-7
I just ran into a problem here.  I'm in SimpleRegisterCoalescing at the point
where EXTRACT_SUBREG coalescing updates live ranges of aliased
registers (around line 473 of SimpleRegisterCoalescing.cpp).

There's a call to MergeValueInAsValue at line 50.  MergeValueInAsValue has
this code:

void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS,
                                     const VNInfo *RHSValNo, VNInfo *LHSValNo)
{
  SmallVector<VNInfo*, 4> ReplacedValNos;
  iterator IP = begin();
  for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
    if (I->valno != RHSValNo)
      continue;
    unsigned Start = I->start, End = I->end;
    IP = std::upper_bound(IP, end(), Start);
    // If the start of this range overlaps with an existing liverange, trim
it.
    if (IP != begin() && IP[-1].end > Start) {
      if (IP->valno != LHSValNo) {
        ReplacedValNos.push_back(IP->valno);

What happens if IP == end()?  We're pushing bogus information onto
ReplacedvalNos (IP->valno is not valid).

Is this a bug or should IP never be end() at this point?  If the latter is
true then I've got a bug somewhere else I need to hunt down.

                                                   -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Possible LiveInterval Bug

Evan Cheng-2
AFAIK std::upper_bound() would not return end(), right?

Evan

On Jan 29, 2008, at 3:08 PM, David Greene wrote:

> I just ran into a problem here.  I'm in SimpleRegisterCoalescing at  
> the point
> where EXTRACT_SUBREG coalescing updates live ranges of aliased
> registers (around line 473 of SimpleRegisterCoalescing.cpp).
>
> There's a call to MergeValueInAsValue at line 50.  
> MergeValueInAsValue has
> this code:
>
> void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS,
>                                     const VNInfo *RHSValNo, VNInfo  
> *LHSValNo)
> {
>  SmallVector<VNInfo*, 4> ReplacedValNos;
>  iterator IP = begin();
>  for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
>    if (I->valno != RHSValNo)
>      continue;
>    unsigned Start = I->start, End = I->end;
>    IP = std::upper_bound(IP, end(), Start);
>    // If the start of this range overlaps with an existing  
> liverange, trim
> it.
>    if (IP != begin() && IP[-1].end > Start) {
>      if (IP->valno != LHSValNo) {
>        ReplacedValNos.push_back(IP->valno);
>
> What happens if IP == end()?  We're pushing bogus information onto
> ReplacedvalNos (IP->valno is not valid).
>
> Is this a bug or should IP never be end() at this point?  If the  
> latter is
> true then I've got a bug somewhere else I need to hunt down.
>
>                                                   -Dave
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Possible LiveInterval Bug

dag-7
On Wednesday 30 January 2008 02:02, Evan Cheng wrote:
> AFAIK std::upper_bound() would not return end(), right?

Yes, it can return end().  In fact that's exactly what I'm seeing.
std::upper_bound is just binary search and returns where
the element should be inserted to retain ordering.  So for
example, if my iterator range is over:

1 2 3 4 5

and I call std::upper_bound(begin(), end(), 6), it's going to
return end() because that's the position before which 6
should be inserted to maintain ordering.

I did find a bug in other parts of my code that made this
paritcular problem go away, but if end() is not expected here
we should document that with an assert.  Otherwise we
should check for it and act appropriately (I don't know what
that would be in this case).

                                       -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Possible LiveInterval Bug

Evan Cheng-2
Hrm, I see a bug here. Let's say the liverange in question is [13,20)  
and the interval it's being merged to is something like this: [1, 4),  
[10, 15)

     IP = std::upper_bound(IP, end(), Start);
     if (IP != begin() && IP[-1].end > Start) {
        if (IP->valno != LHSValNo) {
          ReplacedValNos.push_back(IP->valno);
          IP->valno = LHSValNo; // Update val#.
        }

IP is end() and we would be pushing junk into ReplacedValNos. Is this  
what you saw?

I wonder if the fix should be changing the inner if to:
if (IP[-1].valno != LHSValNo) {
   ReplacedValNos.push_back(IP[-1].valno);
   IP[-1].valno = LHSValNo;
}

I'll do some testing.

Thanks,

Evan

On Jan 30, 2008, at 10:05 AM, David Greene wrote:

> On Wednesday 30 January 2008 02:02, Evan Cheng wrote:
>> AFAIK std::upper_bound() would not return end(), right?
>
> Yes, it can return end().  In fact that's exactly what I'm seeing.
> std::upper_bound is just binary search and returns where
> the element should be inserted to retain ordering.  So for
> example, if my iterator range is over:
>
> 1 2 3 4 5
>
> and I call std::upper_bound(begin(), end(), 6), it's going to
> return end() because that's the position before which 6
> should be inserted to maintain ordering.
>
> I did find a bug in other parts of my code that made this
> paritcular problem go away, but if end() is not expected here
> we should document that with an assert.  Otherwise we
> should check for it and act appropriately (I don't know what
> that would be in this case).
>
>                                       -Dave
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Possible LiveInterval Bug

dag-7
On Wednesday 30 January 2008 15:06, Evan Cheng wrote:

> Hrm, I see a bug here. Let's say the liverange in question is [13,20)
> and the interval it's being merged to is something like this: [1, 4),
> [10, 15)
>
>      IP = std::upper_bound(IP, end(), Start);
>      if (IP != begin() && IP[-1].end > Start) {
>         if (IP->valno != LHSValNo) {
>           ReplacedValNos.push_back(IP->valno);
>           IP->valno = LHSValNo; // Update val#.
>         }
>
> IP is end() and we would be pushing junk into ReplacedValNos. Is this
> what you saw?

Yep, exactly.

> I wonder if the fix should be changing the inner if to:
> if (IP[-1].valno != LHSValNo) {
>    ReplacedValNos.push_back(IP[-1].valno);
>    IP[-1].valno = LHSValNo;
> }

I was thinking along the same lines.  But does this work for the cases where
IP is _not_ end()?  Is it true that we always want to look one back from IP?

                                             -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Possible LiveInterval Bug

Evan Cheng-2

On Jan 30, 2008, at 1:21 PM, David Greene wrote:

> On Wednesday 30 January 2008 15:06, Evan Cheng wrote:
>> Hrm, I see a bug here. Let's say the liverange in question is [13,20)
>> and the interval it's being merged to is something like this: [1, 4),
>> [10, 15)
>>
>>     IP = std::upper_bound(IP, end(), Start);
>>     if (IP != begin() && IP[-1].end > Start) {
>>        if (IP->valno != LHSValNo) {
>>          ReplacedValNos.push_back(IP->valno);
>>          IP->valno = LHSValNo; // Update val#.
>>        }
>>
>> IP is end() and we would be pushing junk into ReplacedValNos. Is this
>> what you saw?
>
> Yep, exactly.
>
>> I wonder if the fix should be changing the inner if to:
>> if (IP[-1].valno != LHSValNo) {
>>   ReplacedValNos.push_back(IP[-1].valno);
>>   IP[-1].valno = LHSValNo;
>> }
>
> I was thinking along the same lines.  But does this work for the  
> cases where
> IP is _not_ end()?  Is it true that we always want to look one back  
> from IP?

I think so. That's the intention and it's safe because IP != begin().

Evan

>
>
>                                             -Dave
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Possible LiveInterval Bug

dag-7
On Wednesday 30 January 2008 16:22, Evan Cheng wrote:

> > I was thinking along the same lines.  But does this work for the
> > cases where
> > IP is _not_ end()?  Is it true that we always want to look one back
> > from IP?
>
> I think so. That's the intention and it's safe because IP != begin().

Right.  But doesn't that imply we've had some messed up intervals being
created for quite some time, even onces where IP was _not_ end()?  How the
heck did this ever work?  :-/

                                   -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Possible LiveInterval Bug

Evan Cheng-2

On Jan 30, 2008, at 3:53 PM, David Greene wrote:

> On Wednesday 30 January 2008 16:22, Evan Cheng wrote:
>
>>> I was thinking along the same lines.  But does this work for the
>>> cases where
>>> IP is _not_ end()?  Is it true that we always want to look one back
>>> from IP?
>>
>> I think so. That's the intention and it's safe because IP != begin().
>
> Right.  But doesn't that imply we've had some messed up intervals  
> being
> created for quite some time, even onces where IP was _not_ end()?  
> How the
> heck did this ever work?  :-/

This routine is rarely called. I am surprised the bug hasn't surfaced  
before. But that's how it is...

Thanks,

Evan

>
>
>                                   -Dave
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev