[llvm-bugs] [Bug 26447] New: Possible (probable?) bug in computing LiveRange overlap

[via llvm-bugs]

https://llvm.org/bugs/show_bug.cgi?id=26447

            Bug ID: 26447
           Summary: Possible (probable?) bug in computing LiveRange
                    overlap
           Product: libraries
           Version: trunk
          Hardware: All
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: Register Allocator
          Assignee: unassignedbugs at nondot.org
          Reporter: stephen.montgomery333 at gmail.com
                CC: llvm-bugs at lists.llvm.org, qcolombet at apple.com
    Classification: Unclassified

Created attachment 15807
  --> https://llvm.org/bugs/attachment.cgi?id=15807&action=edit
Possible fix for LiveRange::overlaps bug with CoalescerPair

I submitted this recently to the llvmdev mailing list but didn't get any
feedback so I'm taking the plunge and reporting it as a bug.

My backend for the Freescale S12X micro controller family failed with a "ran
out of registers during register allocation" message recently. I traced the
issue down to the code that checks whether two LiveRanges have overlapping
segments that are not coalescable.

I’ve got two ranges [608r,656r:0)[656r,672r:1) and [0B,32r)[672r,688r). I don’t
believe that these overlap though maybe I've misunderstood how LiveRanges work.
In any event, if I iterate over one LiveRange's segments and use
LiveRange::overlaps(SlotIndex Start, SlotIndex End) I don't get any overlap.

However, the version of LiveRange::overlaps that takes a CoalescerPair and
checks for coalescable segments thinks that these ranges _do_ overlap.

I think the problem is in the loop that advances the iterator that ends
earliest. I think it should advance until J->end > I->start, not >=. That way,
I think it would have the same effect as LiveRange::find() which is what I
believe the code is aiming to do, just more efficiently than find().

I've checked against the trunk (my work is based off version 3.7) and there
haven't been any changes in this area so I believe the bug is still present.

I’ve attached a patch which seems to fix things for me. I don't see any
regressions for the supported backends when using 'check-all' having applied
this fix. It may be I'm just hitting the bug because the S12X has very few
registers and many restrictions on which registers can be used in certain
instructions.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20160203/8ae53616/attachment.html>