On Tue, 14 May 2019, Richard Biener wrote:
In princple PTA should know the aliasing cannot happen but possibly
the info is either lost or the IL is too obfuscated at the point it gets
computed. (hello C++...)
We don't need much obfuscation for this, a simple C program
int g;
int*f(int**p){
int*q=*p;
int*r=__builtin_malloc(4);
*q=1;
*r=2;
g=*q;
return r;
}
gives
q_4 = *p_3(D);
r_6 = __builtin_malloc (4);
*q_4 = 1;
*r_6 = 2;
_1 = *q_4;
g = _1;
return r_6;
where we clearly don't manage to prove that q and r don't alias.
We can probably improve this one in general from inside PTA
by treating escapes through return specially. I wasn't looking
too closely at the C++ testcase but I simply assumed the
addition to ESCAPED happens through storing the malloc
result to memory that PTA cannot prove local.
Yes, that is indeed the case. I only wrote the version with return to
simplify, but the vector testcase does store the malloc result in
non-local memory, so handling return as a special case wouldn't help it.
So at ldist time I see
# PT = null { D.47989 } (escaped, escaped heap)
# ALIGN = 8, MISALIGN = 0
# USE = nonlocal null { D.47989 } (escaped, escaped heap)
# CLB = nonlocal null { D.47989 } (escaped, escaped heap)
_27 = malloc (8192);
good. The interesting loop is the following where the allocation PTA
is good and _4 intersect because they include ESCAPED. This is
because _27 itself escapes and PTA not being flow-sensitive. I don't
see an easy way to improve things here but dislike the stmt walking
very much. That is, the proper solution is to re-write PTA in some way.
I am trying to imagine what that might look like. I imagine that instead
of having a single "escaped" set, we would have multiple escaped sets at
different points in the function (at most one per VDEF?). Then _4 would
only contain escaped3 while heap5 (*_27) only appears in escaped9 and
later? It may be tricky to keep a linear-ish complexity with anything more
powerful than the current PTA. I don't know what LLVM is doing, but they
seem to manage.
IIRC LLVM uses Steensgard analysis which is flow-sensitive but generally
less powerful. We are using Andersen constraint-based analysis because
Steensgard was patented back in time (that patent has now expired).
In https://llvm.org/docs/AliasAnalysis.html they say that Steensgaard’s
algorithm is flow-insensitive and context-insensitive, so it might not be
it. They run about 5 different alias analysis engines and combine their
results to disambiguate as much as they can.
One approach to make PTA "more" flow-sensitive is to partition the function
into regions (basically represent the function as a series of function calls
to its parts).
For the issue above there's the long-standing issue of splitting escapes
from function return from escapes to functions called to properly represent
local variable lifetime.
That said, your simpler patch still relies on up-to-date dominators, sth
not guaranteed or required previously.
Ah, dom_info_available_p does not mean that the available information is
up-to-date? :-(
We might consider implementing a separate (region-based) analysis
adjusting/pruning points-to information with flow-sensitive knowlege.
This might even work when done from inside PTA as post-processing.
--
Marc Glisse
