[LLVMbugs] [Bug 4749] New: StrongPhiElimination losts a copy

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.org/bugs/show_bug.cgi?id=4749

           Summary: StrongPhiElimination losts a copy
           Product: libraries
           Version: trunk
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Common Code Generator Code
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: yuanlin2004 at gmail.com
                CC: llvmbugs at cs.uiuc.edu, yuanlin2004 at gmail.com


Take the following test case tt.c,

--------------------------------------
void foo( int *pa,  int *pb)
{
    int x;
    int y;

    x = *pa;
    y = *pb;

    while(*pa) {
        y = x;
        x = 0;
        pa ++;
    }

    *pb = y;
}

--------------------------------------

>~/llvm/trunk/llvm/Debug/bin/clang-cc tt.c --emit-llvm-bc -o tt.bc
>~/llvm/trunk/llvm/Debug/bin/opt -O3 tt.bc -o tt.opt.bc
>~/llvm/trunk/llvm/Debug/bin/llc -march=x86 tt.opt.bc -o - -strong-phi-elim
        .file   "tt.opt.bc"

        .text
        .align  16
        .globl  foo
        .type   foo, at function
foo:                                                        # @foo
.LBB1_0:                                                    # %entry
        pushl   %esi
        movl    8(%esp), %eax
        movl    (%eax), %ecx
        testl   %ecx, %ecx
        movl    12(%esp), %edx
        je      .LBB1_3
        .align  16
.LBB1_1:                                                    # %while.body
                                                            # Loop Depth 1
                                                            # Loop Header
                                                            # Inner Loop
        movl    %ecx, %esi
        cmpl    $0, 4(%eax)
        leal    4(%eax), %eax
        movl    $0, %ecx               <--------------- clears ecx
        jne     .LBB1_1
.LBB1_2:                                                    # %while.end
        movl    %ecx, (%edx)
        popl    %esi
        ret
.LBB1_3:                                                    #
%entry.while.end_crit_edge
        movl    (%edx), %ecx
        jmp     .LBB1_2
        .size   foo, .-foo

        .section        .note.GNU-stack,"", at progbits


Notice that the value of %ecx (which corresponds to 'y' after the loop) always
becomes 0 if the while loop body is ever entered. This is incorrect.


The following is my initial assess of the problem:

Hello, I've encountered a problem similar to 'lost-copy' when using
the StrongPhiElimination and wonder whether it is a incompatibility
issue between the two different algorithms used in
StrongPhiElimination.cpp. The StrongPhiElimination is mostly based on
the algorithm in Zoran Budimilic et al's "Fast Copy Coalescing and
Live-Range Identification" ([1]), while the 'Copy Insertion' part is
from Preston Briggs et al's "Practical Improvements to the
Construction and Destruction of Static Single Assignment Form" ([2]).

The test case I have is as follows,

Block 1
 r1 = ...
 if (...) goto Block 2
 else goto Block 3

Block 2
 r2 = ...
 goto Block 4

Block 3
 r3 = phi(r1, r4)
 r4 = ...
 if (...) goto Block 3
 else goto Block 4

Block 4
 r5 = phi(r2, r3)
 ... = r5


Since the live range of r2, r3, and r5 do not interference,
StrongPhiElimination decides, before InsertCopies(), to rename both r2
and r3 to r5 based onthe algorithm in [1]

During InsertCopies(), because 'r3' is live after Block 3 and this is
the typical case where 'lost-copy' could happen, StrongPhiEilimination
inserts a copy from r3 to a temp register r99 based on the algorithm
in [2]. Block 3 then becomes

Block 3
  r3 = phi(r1, r4)
  r99 = r3
  r4 = ...
  r3 = r4
  if (...) goto Block 3
  else (...) goto Block 4

The Insert-copy algorithm in [2] would normally rename r3 in Block 4
to r99. But StrongPhiEliminination decides unify 'r5', 'r2' and 'r3'
instead of inserting copies for 'r5=phi(r2, r3)' in Block 4, therefore
the 'waiting' set for Block 4 is empty. 'r3' is not renamed to 'r99'
in StrongPhiElimination.

Then StrongPhiElimination proceeds to the renaming phase and rename
both r2 and r3 to r5. The final code becomes

Block 1
 r1 = ...
 r5 = r1
 if (...) goto Block 2
 else goto Block 3

Block 2
 r5 = ...
 goto Block 4

Block 3
  r99 = r5
  r4 = ...
  r5 = r4
  if (...) goto Block 3
  else (...) goto Block 4

Block 4
 ... = r5

The value of r5 in Block 4 is wrong when the path Block 1->Block
3->Block 4 is taken.


-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.