<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 --- - [regalloc] A problem caused by the interaction between split and evict"
href="https://llvm.org/bugs/show_bug.cgi?id=31411">31411</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>[regalloc] A problem caused by the interaction between split and evict
</td>
</tr>
<tr>
<th>Product</th>
<td>libraries
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>Linux
</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>wmi@google.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org
</td>
</tr>
<tr>
<th>Classification</th>
<td>Unclassified
</td>
</tr></table>
<p>
<div>
<pre>For the testcase 1.cc:
~/workarea/llvm-r287002/dbuild/bin/clang -std=c++11 -fno-omit-frame-pointer
-fno-exceptions -O2 -S 1.cc -o 1.s
In BB#41 we found some fishy code. The movq instructions pairs below indicates
some problem in reg split.
# BB#41: # %if.then.i201
# in Loop: Header=BB0_35 Depth=2
xorl %eax, %eax
cmpl %r10d, %r12d
setl %al
movq -56(%rbp), %rcx # 8-byte Reload
=======>
movq %r13, %rdi
movq %r15, %r13
movq %r10, %r15
movq %r8, %r10
=======>
movq %rcx, %r8
addq %rax, %r8
movq -136(%rbp), %rax # 8-byte Reload
movslq 56(%rax), %rax
shlq $3, %rax
negq %rax
movq (%rdi,%rax), %rax
movq %r8, %rcx
movq %rcx, -56(%rbp) # 8-byte Spill
addq %r8, %rax
=======>
movq %r10, %r8
movq %r15, %r10
movq %r13, %r15
movq %rdi, %r13
=======>
movq %rax, (%r13)
We do some digging here and find the problem is about the interaction of split
and evict:
Suppose physical register %R1 is used in BB#41 but available elsewhere. virtual
registers: VR1,VR2,VR3,VR4 lives through BB#41. Register pressure is high in
the function so VR1 is split into VR1_a and VR1_b with %R1 available for VR1_a.
VR10 holds %R2.
BB#41
VR1_b = VR1_a;
...
def R1;
...
use R1;
...
VR1_a = VR1_b;
VR1_b is the remainder interval the stage of which is marked as SPILL after the
split, and it is local to BB#41. Because VR1_a is longer than VR1_b, VR1_a will
be allocated before VR1_b in the queue after split. VR1_a will easily get %R1.
VR1_b is marked as SPILL but it is shorter than VR1, so it can now evict VR10
for %R2, and VR1_b will get %R2. Note VR1_a and VR1_b get different physical
registers so the copies pair "VR1_b = VR1_a" and "VR1_a = VR1_b" cannot be
coalesced.
Since %R2 is only used in BB#41 but available elsewhere, it looks the same as
%R1 above. Then VR2 will be split in the same way as VR1 and generate another
pair of copies. So on for VR3, VR4...
I think a cause of the problem is:
VR1 cannot evict VR10 for %R2 before it is split, but after split, VR1_b can
evict VR10 because it is shorter now and has higher weight than VR1.
Since VR10 will be evicted anyway by VR1_b, why not do that before split, so
that VR1 can be allocated to %R2 without splitting, and no copies will be
inserted into BB#41.
However, it is not cheap to know that one of new vregs generated from splitting
VR1 can evict VR10 beforehand.
We can have an alternative solution here. Raising the priority of remainder
interval (VR1_b) after split so that VR1_b will be allocated before VR1_a.
VR1_b will still evict VR10 and get %R2. When allocating VR1_a, it can choose
between %R2 and %R1 and will more likely to choose %R2 because of hint, and the
copies will be coalesced.</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>