llvm dev - Jan 2008 - [LLVMdev] Possible LiveInterval Bug

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

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
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

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