[LLVMdev] Writing a new AA pass

[Dimitri Tcaciuc]

Hello everyone,

Proceeding with an effort to optimize
pointer-arg-to-struct-with-data-pointer arrangement, I'm taking a shot at
writing a specific AA pass. I've got a scaffold up modelling after BasicAA
and bumped into a few issues. Here's a snippet of IR I'm dealing with.
Slice is the wrapper structure and "data" pointer is element 0 and we're
looking at two of them.

---- IR ----

  define void foo(%Slice* noalias %a, %Slice* noalias %b)

  store %Slice* %a, %Slice** %v
  store %Slice* %b, %Slice** %v1
  ; ...

  %v6 = load %Slice** %v
  %v14 = load %Slice** %v1
  ; ...

  %gep9 = getelementptr inbounds %Slice* %v6, i32 0, i32 0
  %v10 = load double** %gep9
  ; v13 = <index calculation>
  ; ...
  %addr = getelementptr double* %v10, i64 %v13
  %getitem = load double* %addr
  ;...

  %gep18 = getelementptr inbounds %Slice* %v14, i32 0, i32 0
  %v19 = load double** %gep18
  ; v22 = <index calculation>
  ; ...
  %addr23 = getelementptr double* %v19, i64 %v22
  %getitem24 = load double* %addr23

---- /IR ----


Right now I'm forwarding alias() calls to base class and just observing the
current alias analysis result. Here's a portion of the output

---- Debug ----

 LocA  %gep9 = getelementptr inbounds %Slice* %a, i64 0, i32 0
 LocB  %gep18 = getelementptr inbounds %Slice* %b, i64 0, i32 0
  Aliases? 0

 LocA  %addr = getelementptr double* %v10, i64 %v11
 LocB  %gep18 = getelementptr inbounds %Slice* %b, i64 0, i32 0
  Aliases? 0

 LocA  %gep9 = getelementptr inbounds %Slice* %a, i64 0, i32 0
 LocB  %addr23 = getelementptr double* %v19, i64 %v11
  Aliases? 0

 LocA  %addr = getelementptr double* %v10, i64 %v11
 LocB  %addr23 = getelementptr double* %v19, i64 %v11
  Aliases? 1

 LocA  %gep18 = getelementptr inbounds %Slice* %b, i64 0, i32 0
 LocB  %addr23 = getelementptr double* %v19, i64 %v11
  Aliases? 0

 LocA  %addr = getelementptr double* %v10, i64 %v11
 LocB  %addr23 = getelementptr double* %v19, i64 %v11
  Aliases? 1

---- /Debug ----

The results raise a few questions:

1. For whatever reason, the only type of instruction making it to alias()
is GEP. Looking at BasicAA code, it seems I should also expect load()s and
some of those are definitely present in IR. How come I'm not seeing them?

2. It seems that current AA has no problem disambiguating Slice pointer
from data pointer, but has issues distinguishing two data pointers, even
tho two Slice pointers are marked as noalias. This is the spot I want to
augment. My planned logic is to

  a) Mark data pointer loads (pointer itself, not elements) with special
metadata (say, !sliceaa.data)
  b) Find parent Slice structure
  c) If Slices don't alias, data pointers don't alias as well. This is very
simplistic and wrong in many situations, but it should be good for starters.

What would be the proper way to look for those "parent" slice structs?
Closest thing I found so far is in memory dependency analysis where I
retrieve the parent block (or parent function) and iterate all instructions
until I, say, find result value which is the same as the source value in a
load and so on. Is there a better way?


Thanks,


Dimitri.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130122/55ba33bf/attachment.html>