Ethan J. Johnson via llvm-dev
2017-Jul-03 22:51 UTC
[llvm-dev] List of alias analyses available in LLVM, and how to use them from llc
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 Rochester ejohns48 at cs.rochester.edu ethanjohnson at acm.org PGP public key available from public directory or on request -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170703/5f10c983/attachment.html>
Philip Pfaffe via llvm-dev
2017-Jul-04 10:18 UTC
[llvm-dev] List of alias analyses available in LLVM, and how to use them from llc
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>