[llvm-bugs] [Bug 31411] New: [regalloc] A problem caused by the interaction between split and evict

[via llvm-bugs]

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

            Bug ID: 31411
           Summary: [regalloc] A problem caused by the interaction between
                    split and evict
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: Register Allocator
          Assignee: unassignedbugs at nondot.org
          Reporter: wmi at google.com
                CC: llvm-bugs at lists.llvm.org
    Classification: Unclassified

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.

-- 
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/20161216/ad2e6242/attachment.html>