[LLVMbugs] [Bug 13564] New: Extend BasicAliasAnalysis to recognize cyclic NoAlias phis in loops

[bugzilla-daemon at llvm.org]

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

             Bug #: 13564
           Summary: Extend BasicAliasAnalysis to recognize cyclic NoAlias
                    phis in loops
           Product: tools
           Version: trunk
          Platform: PC
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: opt
        AssignedTo: arnolds at codeaurora.org
        ReportedBy: arnolds at codeaurora.org
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified


Created attachment 9022
  --> http://llvm.org/bugs/attachment.cgi?id=9022
Patch

BasicAliasAnalysis should recognize phis that have incoming
values from outside the loop that are known to not alias and whose other
incoming values do not change this fact because they perform congruent
operations.

Example: We want to prove that ptr_phi and ptr_phi2 do not alias each other.

bb:
 ptr = ptr2 + 1

loop:
  ptr_phi = phi [bb, ptr], [loop, ptr_plus_one]
  ptr2_phi = phi [bb, ptr2], [loop, ptr2_plus_one]
  ...
  ptr_plus_one = gep ptr_phi, 1
  ptr2_plus_one = gep ptr2_phi, 1

This would enable the elimination of one load in code like the following:

extern int foo;

int test_noalias(int *ptr, int num, int* coeff) {
  int *ptr2 = ptr;
  int result = (*ptr++) * (*coeff--);
  while (num--) {
    *ptr2++ = *ptr;
    result +=  (*coeff--) * (*ptr++);
  }
  *ptr = foo;
  return result;
}

Currently, without the improvement to basic alias analysis we generate the
following code for the loop:

The loads from %r9 are the accesses to "ptr".

.LBB0_2:                                # %while.body
                                        # =>This Inner Loop Header: Depth=1
        movl    (%r9), %ecx
        movl    %ecx, -4(%r9)
        movl    (%r9), %ecx
        imull   (%rdx), %ecx
        addl    %ecx, %eax
        addq    $-4, %rdx
        addq    $4, %r9
        decl    %esi
        jne     .LBB0_2

With the improvement we would generate:

.LBB0_2:                                # %while.body
                                        # =>This Inner Loop Header: Depth=1
        movl    (%r9), %ecx
        movl    %ecx, -4(%r9)
        imull   (%rdx), %ecx
        addl    %ecx, %eax
        addq    $4, %r9
        addq    $-4, %rdx
        decl    %esi
        jne     .LBB0_2

The attached patch implements this enhancement.

-- 
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.