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

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

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

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