malloc cannot alias preexisting pointers

[Richard Biener]

On Sat, May 18, 2019 at 2:56 PM Marc Glisse <marc.glisse@inria.fr> wrote:
>
> On Wed, 15 May 2019, Richard Biener wrote:
>
> > As you write the heuristic you could as well remove the malloc result
> > points-to set from the others after points-to analysis is finished?
>
> Looking at the vector testcase:
>
> #include <vector>
> #include <memory>
> #include <new>
> inline void* operator new(std::size_t n){return malloc(n);}
> inline void operator delete(void*p){free(p);}
> typedef std::unique_ptr<int> T;
> typedef std::vector<T> V;
> void f(V&v){v.reserve(1024);}
>
> I get in the alias pass for malloc
>
> _24, points-to NULL, points-to vars: { D.48250 } (escaped, escaped heap)
>
> and for the pointer I want to say cannot alias _24
>
> _4, points-to non-local, points-to escaped, points-to NULL, points-to vars: { }
>
> I don't see what I can remove from where, all the important info is in
> "escaped" (well in this case I guess "points-to escaped" could be dropped
> because this is the very first statement and nothing has escaped yet, but
> that's too specialized). Actually, I don't even understand how I could
> encode the fact that they cannot alias in the current points-to
> structures. It seems that it would require at least changing from one
> "escaped" to several "escaped_XX" (or more radically several PT info per
> SSA_NAME).

Note that while 'escaped' is a special variable during points-to solving
once we transition to points-to sets as attached to SSA names it is
just a placeholder for a set of DECLs (which does indeed save bits
in the points-to bitmaps).  To prune sth from escaped on a specific
SSA name (as you need to do here) you could simply remove
the 'points-to-escaped' bit, expand 'escaped' "inline" into the points-to
bitmap of the SSA name and prune from the result.

Note I have never done statistics on how much having that separate
ESCAPED set helps memory-wise, it definitely makes points-to
queries more expensive since we eventually have to look into the
ESCAPED solution as well.  A better data structure for points-to
set representation might be nice to have.

> > One could even devise something like a "negative" live set
> > (all-locals & ~live-locals), pruning the points-to sets of SSA names
> > on the whole CFG considering that
> >
> > int *p;
> > int y;
> > void foo()
> > {
> >   int x;
> >   *p = &y;
> >   if (p != &y) abort ();
> >   *p = &x;
> > }
> >
> > computes p to point to both y and x at the point of the comparison.
> >
> > That is, this isn't special to malloc but to all variables that come into
> > scope only after function entry.
>
> Indeed, flow sensitivity can help for more than malloc.
>
> > This is something I would like much more than these kinds of local
> > tricks in the oracle itself.
>
> That's interesting, but I don't see how it would solve the "escaped"
> issue.
>
>
>
> One detail I noticed: in the alias dump, I see
> _10 = { ESCAPED NONLOCAL }
> for a POINTER_DIFF_EXPR that cannot encode a pointer. If I change that to
> get _10 = { } and _6 = { }, for
>    _19 = (long unsigned int) _10;
> I have _19 = { } as expected, but for
>    _7 = _6 /[ex] 8;
> I get _7 = { NONLOCAL } same as v
> where I was expecting _7 = { }. I guess that's because it involves a
> constant, and constants can be addresses.
> It feels like the pass is creating a bit of useless work for itself,
> though that probably doesn't matter...

Yeah, here it's missing special-casing of some operators, neither
POINTER_MINUS_EXPR is handled (always creates a non-pointer,
aka points-to nothing?), nor *_DIV_EXPR are handled (same
points-to set as the LHS I guess, similar for *_MOD_EXPR).
Tracking pointers through integers is both good and bad here
I guess...

I'll test a patch for the above.

Richard.


>
> --
> Marc Glisse