<html>
    <head>
      <base href="https://llvm.org/bugs/" />
    </head>
    <body><table border="1" cellspacing="0" cellpadding="8">
        <tr>
          <th>Bug ID</th>
          <td><a class="bz_bug_link 
          bz_status_NEW "
   title="NEW --- - Possible (probable?) bug in computing LiveRange overlap"
   href="https://llvm.org/bugs/show_bug.cgi?id=26447">26447</a>
          </td>
        </tr>

        <tr>
          <th>Summary</th>
          <td>Possible (probable?) bug in computing LiveRange overlap
          </td>
        </tr>

        <tr>
          <th>Product</th>
          <td>libraries
          </td>
        </tr>

        <tr>
          <th>Version</th>
          <td>trunk
          </td>
        </tr>

        <tr>
          <th>Hardware</th>
          <td>All
          </td>
        </tr>

        <tr>
          <th>OS</th>
          <td>All
          </td>
        </tr>

        <tr>
          <th>Status</th>
          <td>NEW
          </td>
        </tr>

        <tr>
          <th>Severity</th>
          <td>normal
          </td>
        </tr>

        <tr>
          <th>Priority</th>
          <td>P
          </td>
        </tr>

        <tr>
          <th>Component</th>
          <td>Register Allocator
          </td>
        </tr>

        <tr>
          <th>Assignee</th>
          <td>unassignedbugs@nondot.org
          </td>
        </tr>

        <tr>
          <th>Reporter</th>
          <td>stephen.montgomery333@gmail.com
          </td>
        </tr>

        <tr>
          <th>CC</th>
          <td>llvm-bugs@lists.llvm.org, qcolombet@apple.com
          </td>
        </tr>

        <tr>
          <th>Classification</th>
          <td>Unclassified
          </td>
        </tr></table>
      <p>
        <div>
        <pre>Created <span class=""><a href="attachment.cgi?id=15807" name="attach_15807" title="Possible fix for LiveRange::overlaps bug with CoalescerPair">attachment 15807</a> <a href="attachment.cgi?id=15807&action=edit" title="Possible fix for LiveRange::overlaps bug with CoalescerPair">[details]</a></span>
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.</pre>
        </div>
      </p>
      <hr>
      <span>You are receiving this mail because:</span>
      
      <ul>
          <li>You are on the CC list for the bug.</li>
      </ul>
    </body>
</html>