[basicaa] Basic AA misses a large number of simple testcases

[Quuxplusone]

Bugzilla Link	PR86
Status	RESOLVED FIXED
Importance	P enhancement
Reported by	Chris Lattner (clattner@nondot.org)
Reported on	2003-11-04 10:47:03 -0800
Last modified on	2010-02-22 12:52:38 -0800
Version	1.0
Hardware	All All
CC	llvm-bugs@lists.llvm.org
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also

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

[Quuxplusone]

This would be nice to fix for 1.1, but it does not block it.

-Chris

[Quuxplusone]

erk .. reassigned wrong bug .. undoing ..

[Quuxplusone]

Another note, basicaa could be extended for a very simple form of mod/ref
information.  If a pointer is locally allocated (either malloc or alloca) and
never passed  into a call or stored to memory, then we know that calls will not
mod/ref the memory.  This can be important for tail call elimination.

[Quuxplusone]

Here's a testcase that should get significantly better with better
disambiguation:

$ extract -func MakeMove 186.crafty.llvm.bc | opt -aa-eval -disable-output
===== Alias Analysis Evaluator Report =====
  30135 Total Alias Queries Performed
  23879 no alias responses (79%)
  6041 may alias responses (20%)
  215 must alias responses (0%)
  Alias Analysis Evaluator Summary: 79%/20%/0%

Almost all of the pointer references are directly to globals: we should be able
to disambiguate almost everything in this function of crafty.

-Chris

[Quuxplusone]

Here's a partial patch:
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20031208/010083.html

This resolves 3 aliases, bringing us up to:

$ llvm-as < 2003-11-04-SimpleCases.ll | opt -aa-eval -print-may-aliases \
               -disable-output -print-must-aliases -print-no-aliases
Function: test
  Must: %T* %A, %T* %P
  Must: uint* %B, %T* %P
  Must: 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%)
  7 may alias responses (46%)
  3 must alias responses (20%)
  Alias Analysis Evaluator Summary: 33%/46%/20%

[Quuxplusone]

Here's a new testcase that basicaa should be able to handle (this is now
2003-12-11-ConstExprGEP.ll):

%T = type { uint, [10 x ubyte] }
%G = external global %T
void %test() {
  %D = getelementptr %T* %G, long 0, ubyte 0
  %E = getelementptr %T* %G, long 0, ubyte 1, long 5
  %F = getelementptr uint* getelementptr (%T* %G, long 0, ubyte 0), long 0
  %G = getelementptr [10 x ubyte]* getelementptr (%T* %G, long 0, ubyte 1), long
0, long 5
  ret void
}

On this, we currently get:

$ llvm-as < 2003-12-11-ConstExprGEP.ll | opt -aa-eval -print-may-aliases
-print-no-aliases -print-must-aliases -disable-output
Function: test
  May:  uint* getelementptr (%T* %G, long 0, ubyte 0), %T* %G
  May:  [10 x ubyte]* getelementptr (%T* %G, long 0, ubyte 1), %T* %G
  May:  [10 x ubyte]* getelementptr (%T* %G, long 0, ubyte 1), uint*
getelementptr (%T* %G, long 0, ubyte 0)
  Must: uint* %D, %T* %G
  May:  uint* %D, uint* getelementptr (%T* %G, long 0, ubyte 0)
  May:  uint* %D, [10 x ubyte]* getelementptr (%T* %G, long 0, ubyte 1)
  No:   ubyte* %E, %T* %G
  May:  ubyte* %E, uint* getelementptr (%T* %G, long 0, ubyte 0)
  May:  ubyte* %E, [10 x ubyte]* getelementptr (%T* %G, long 0, ubyte 1)
  No:   ubyte* %E, uint* %D
  May:  uint* %F, %T* %G
  Must: uint* %F, uint* getelementptr (%T* %G, long 0, ubyte 0)
  May:  uint* %F, [10 x ubyte]* getelementptr (%T* %G, long 0, ubyte 1)
  May:  uint* %F, uint* %D
  May:  uint* %F, ubyte* %E
  May:  ubyte* %G, %T* %G
  May:  ubyte* %G, uint* getelementptr (%T* %G, long 0, ubyte 0)
  No:   ubyte* %G, [10 x ubyte]* getelementptr (%T* %G, long 0, ubyte 1)
  May:  ubyte* %G, uint* %D
  May:  ubyte* %G, ubyte* %E
  May:  ubyte* %G, uint* %F
===== Alias Analysis Evaluator Report =====
  21 Total Alias Queries Performed
  3 no alias responses (14%)
  16 may alias responses (76%)
  2 must alias responses (9%)
  Alias Analysis Evaluator Summary: 14%/76%/9%

[Quuxplusone]

These two patches implement this PR:
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20031208/010094.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20031208/010097.html

With these patches, we correctly/perfectly resolve all aliases from
BasicAA/2003-11-04-SimpleCases.ll as well as 2003-12-11-ConstExprGEP.ll.

An example from crafty that improves a lot is the MakeMove function (there may
be others, this is just one I was debugging other bugs in recently.  It mainly
references globals and arrays):

Before:

$ extract -func MakeMove 186.crafty.llvm.bc | opt -aa-eval -disable-output
===== Alias Analysis Evaluator Report =====
  30135 Total Alias Queries Performed
  23879 no alias responses (79%)
  6041 may alias responses (20%)
  215 must alias responses (0%)
  Alias Analysis Evaluator Summary: 79%/20%/0%

Now:

$ extract -func MakeMove 186.crafty.llvm.bc | opt -aa-eval -disable-output
===== Alias Analysis Evaluator Report =====
  30135 Total Alias Queries Performed
  28471 no alias responses (94%)
  1448 may alias responses (4%)
  216 must alias responses (0%)
  Alias Analysis Evaluator Summary: 94%/4%/0%

Not bad for a purely local algorithm :)

-Chris