[llvm-dev] List of alias analyses available in LLVM, and how to use them from llc

Tue Jul 4 03:18:13 PDT 2017

Hi Ethan,

I'm not aware of a complete, up-to-date document of the available AA
analyses. It might make sense to look at the source, though.

You can find a list of available alias analyses in the PassRegistry[1].
Just grep for ALIAS. If you're building on top of the legacy pass manager,
there's a similar file for it, but the actual analyses should be the same.
I guess how these analyses work is in most cases obvious by their name.
Otherewise, another look at their implementation might help. For instance,
the implementation of TBAA[2] is comparatively well documented.

Hope that helps a bit!

Philip

[1] https://github.com/llvm-mirror/llvm/blob/master/lib/
Passes/PassRegistry.def
[2] http://llvm.org/doxygen/TypeBasedAliasAnalysis_8cpp_source.html

2017-07-04 0:51 GMT+02:00 Ethan J. Johnson via llvm-dev <
llvm-dev at lists.llvm.org>:

> Hi all,
>
> I have two questions about alias analysis; see below for the background on
> why I am asking these questions. First, the questions:
>
>    1. Is there an up-to-date list somewhere of all the alias analyses in
>    LLVM, and what their capabilities are? I've been told that the
>    AliasAnalysis page in the official documentation (http://llvm.org/docs/
>    AliasAnalysis.html) is severely out of date. I see in particular that
>    it makes no mention of e.g. TBAA, which shows up in "opt -help".
>    2. Is it possible to override the default alias analysis
>    implementation when running the "llc" tool (or from clang)? I am working
>    from within a MachineFunctionPass, so (unfortunately) I cannot use "opt",
>    which would provide easy command-line options to do this. If there is no
>    command-line ability to specify a different alias analysis, how could I do
>    so in code? Presently, I am simply using getAnalysis<AliasAnalysis>() to
>    get the default alias analysis, which is BasicAA.
>
> Now for the background:
>
> I am writing an analysis pass at the machine-IR level
> (MachineFunctionPass) for security research. (Before anyone asks, yes,
> we've considered doing this in regular IR, and it isn't sufficient for our
> needs. :-) We are studying code-reuse attacks and need to examine the
> actual machine instructions available to an attacker in the final compiled
> binary.)
>
> I'm currently exploring the use of IR-level alias analysis information in
> my MachineFunctionPass. Specifically, I'm using AliasSetTracker on the
> Value* pointers returned by MachineMemOperand::getValue() (similar to what
> MachineInstr::mayAlias() does, though we're not using that interface
> because we're interested in alias sets).
>
> So far, I've been using BasicAliasAnalysis's results, since they're the
> default that I get when simply using getAnalysis<AliasAnalysis>(). However,
> I'd like to try some more advanced alias analyses. Specifically, I'm
> looking for something that provides better field-sensitivity within structs
> on the stack. BasicAA is field-sensitive in general but I've observed that
> this has trouble distinguishing between (for instance) scalar and array
> fields within the same struct when the array is accessed through a variable
> index. A simple motivating example of this is:
>
> struct mystruct {
>     short s;
>     int i;
>     int arr[5];
> };
>
> struct mystruct str;
> str.s = (short) rand();
> str.i = rand();
> for (int idx = 0; idx < 5; ++idx) {
>     str.arr[idx] = rand();
> }
>
> printf("%hd %d %d %d %d %d %d", str.s, str.i, str.arr[0], str.arr[1],
> str.arr[2], str.arr[3], str.arr[4]);
>
> For the above code, BasicAA knows that str.s, str.i, and str.arr[0-4] are
> all pairwise NoAlias, but it says that they are all PartialAlias with
> str.arr[idx]. Clearly, this is because idx is a variable with unknown
> value, and it doesn't fall into one the "special cases" that BasicAA can
> recognize as NoAlias. (For instance, if I write str.arr[(unsigned)idx]
> instead, it can figure out that it is NoAlias with str.s, since the
> explicit zero-extension lets BasicAA know that the index **must** be
> positive, and they are far enough apart that they can't alias. Oddly, it
> still thinks str.i is PartialAlias...I haven't figured this one out but
> would guess it somehow slips through the cracks of BasicAA's special cases.)
>
> Having an array alongside scalars in a struct is fairly common, and I'd
> like to not have to sacrifice field sensitivity when it occurs. My
> thinking, therefore, is that I need a smarter AA that knows things about
> types, e.g., that it's undefined behavior to access a scalar struct field
> through an out-of-bounds pointer to an array field in the same struct. This
> sounds like the sort of thing TBAA ("Type-Based Alias Analysis") might be
> able to do - hence my questions above.
>
> Thanks in advance for your time and assistance!
>
> Sincerely,
> Ethan Johnson
>
> --
> Ethan J. Johnson
> Computer Science PhD student, Systems group, University of Rochesterejohns48 at cs.rochester.eduethanjohnson@acm.org
> PGP public key available from public directory or on request
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170704/d545f95f/attachment-0001.html>