Christian Convey
2015-Jun-15 11:15 UTC
[LLVMdev] Expressing ambiguous points-to info in AliasAnalysis::alias(...) results?
On Mon, Jun 15, 2015 at 1:43 AM, Daniel Berlin <dberlin at dberlin.org> wrote:> > The AA algorithm uses dataflow analysis to monitor the possible > propagation > > of those values through the program code, and it represents those flows > by > > updates to the may-point-to graph. If at some code point CP, a > may-point-to > > graph vertex "B" has no outbound edges, that's equivalent to saying that > the > > AA has concluded the runtime memory modeled by "B" does not contain any > > pointer that a correct program has any business trying to dereference. > > FWIW: When i first did GCC's current points-to analysis, I did the > same thing. It eliminated "non-pointer" values along the same lines. > This broke roughly "the entire world". >Whoa, thanks for the warning.> I tried to find some subset i felt was worthwhile and where it was > okay, but gave up after a while. >I'm not quite sure which things you're referring to in that statement. Would you mind clarifying? -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150615/dde54bcd/attachment.html>
Daniel Berlin
2015-Jun-15 13:31 UTC
[LLVMdev] Expressing ambiguous points-to info in AliasAnalysis::alias(...) results?
On Mon, Jun 15, 2015 at 4:15 AM, Christian Convey <christian.convey at gmail.com> wrote:> On Mon, Jun 15, 2015 at 1:43 AM, Daniel Berlin <dberlin at dberlin.org> wrote: >> >> > The AA algorithm uses dataflow analysis to monitor the possible >> > propagation >> > of those values through the program code, and it represents those flows >> > by >> > updates to the may-point-to graph. If at some code point CP, a >> > may-point-to >> > graph vertex "B" has no outbound edges, that's equivalent to saying that >> > the >> > AA has concluded the runtime memory modeled by "B" does not contain any >> > pointer that a correct program has any business trying to dereference. >> >> FWIW: When i first did GCC's current points-to analysis, I did the >> same thing. It eliminated "non-pointer" values along the same lines. >> This broke roughly "the entire world". > > > Whoa, thanks for the warning. > >> >> I tried to find some subset i felt was worthwhile and where it was >> okay, but gave up after a while. > > > I'm not quite sure which things you're referring to in that statement. > Would you mind clarifying?You can try to ameliorate it by doing things like say "well, we believe code patterns that look like this generate valid pointers, but patterns that look like this can be ignored". It is very hard to find a set of patterns you allow that gives you anything meaningfully better, but doesn't still break the world. As for your statement on authors putting a lot of thought into published algorithms - they do, but honestly, published algorithms should generally be treated like a starting point. They are often vastly simplified for publication, or otherwise in need of significant *engineering* work.
Christian Convey
2015-Jun-15 14:25 UTC
[LLVMdev] Expressing ambiguous points-to info in AliasAnalysis::alias(...) results?
On Mon, Jun 15, 2015 at 9:31 AM, Daniel Berlin <dberlin at dberlin.org> wrote:> >> I tried to find some subset i felt was worthwhile and where it was > >> okay, but gave up after a while. > > > > > > I'm not quite sure which things you're referring to in that statement. > > Would you mind clarifying? > > You can try to ameliorate it by doing things like say "well, we > believe code patterns that look like this generate valid pointers, > but patterns that look like this can be ignored". It is very hard to > find a set of patterns you allow that gives you anything meaningfully >Interesting. So do you know of a decent alternative? Or do you think that may-point-to analysis in something as general as LLVM IR is basically a dead end? Also, can you share a few examples of code constructs which produce pointers used in correct programs, but which are hard to recognize statically? It's probably my inexperience talking, but the only examples I can think of involve interfacing with hardware. I did look at the LLVM IR for calling a virtual function in C++, since you mentioned that as an example earlier. From manual inspection, I thought I could spot the value flow of the virtual function pointer from where the function was defined, into the vtable constant for that class, and then into the class instance's vtable pointer.> As for your statement on authors putting a lot of thought into > published algorithms - they do, but honestly, published algorithms > should generally be treated like a starting point. They are often > vastly simplified for publication, or otherwise in need of significant > *engineering* work. >Thanks for the warning. Yes, I'm feeling that pain in spades :) -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150615/019f20a6/attachment.html>
Seemingly Similar Threads
- [LLVMdev] Expressing ambiguous points-to info in AliasAnalysis::alias(...) results?
- [LLVMdev] Expressing ambiguous points-to info in AliasAnalysis::alias(...) results?
- [LLVMdev] Expressing ambiguous points-to info in AliasAnalysis::alias(...) results?
- [LLVMdev] Expressing ambiguous points-to info in AliasAnalysis::alias(...) results?
- [LLVMdev] Expressing ambiguous points-to info in AliasAnalysis::alias(...) results?