[LLVMbugs] [Bug 86] New: [basicaa] Basic AA misses a large number of simple testcases

[bugzilla-daemon at zion.cs.uiuc.edu]

http://llvm.cs.uiuc.edu/bugs/show_bug.cgi?id=86

           Summary: [basicaa] Basic AA misses a large number of simple
                    testcases
           Product: libraries
           Version: 1.0
          Platform: PC
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Global Analyses
        AssignedTo: sabre at nondot.org
        ReportedBy: sabre at nondot.org


While working on the pool allocator, I notice that a large number of obvious (to
a human) code motion opportunities were being missed by the LLVM optimizer.

Given that basicaa is a purely local algorithm it is limited in what it can do,
but it could do a much better job than it does now.  In particular, in the
following testcase:

---
%T = type { uint, [10 x ubyte] }
void %test(%T* %P) {
  %A = getelementptr %T* %P, long 0
  %B = getelementptr %T* %P, long 0, ubyte 0
  %C = getelementptr %T* %P, long 0, ubyte 1
  %D = getelementptr %T* %P, long 0, ubyte 1, long 0
  %E = getelementptr %T* %P, long 0, ubyte 1, long 5
  ret void
}
---

Basic-aa should be able to determine that _every_ alias pair is either must or
no alias, there should be no may aliases.  In this case, basicaa currently gets
5/15 of the pairs:

$ llvm-as < 2003-11-04-SimpleCases.ll | opt -aa-eval -print-may-aliases
-disable-output -print-must-aliases -print-no-aliases
Function: test
  May:  %T* %A, %T* %P
  May:  uint* %B, %T* %P
  May:  uint* %B, %T* %A
  No:   [10 x ubyte]* %C, %T* %P
  May:  [10 x ubyte]* %C, %T* %A
  No:   [10 x ubyte]* %C, uint* %B
  No:   ubyte* %D, %T* %P
  May:  ubyte* %D, %T* %A
  May:  ubyte* %D, uint* %B
  May:  ubyte* %D, [10 x ubyte]* %C
  No:   ubyte* %E, %T* %P
  May:  ubyte* %E, %T* %A
  May:  ubyte* %E, uint* %B
  May:  ubyte* %E, [10 x ubyte]* %C
  No:   ubyte* %E, ubyte* %D
===== Alias Analysis Evaluator Report =====
  15 Total Alias Queries Performed
  5 no alias responses (33%)
  10 may alias responses (66%)
  0 must alias responses (0%)
  Alias Analysis Evaluator Summary: 33%/66%/0%

This sucks.  The testcase is:
test/Regression/Transforms/BasicAA/2003-11-04-SimpleCases.ll

This bug is just a tracker so that I remember to come back to this issue when I
have time in the future.

-Chris



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.