[LLVMdev] Bug? Coalescing & Updating Subreg Intervals

[David Greene]

On Thursday 21 February 2008 01:23, Evan Cheng wrote:

> > 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