On Mon, Jun 3, 2019 at 1:27 PM Richard Biener
<richard.guent...@gmail.com> wrote:
>
> On Mon, Jun 3, 2019 at 11:37 AM Richard Biener
> <richard.guent...@gmail.com> wrote:
> >
> > On Fri, May 31, 2019 at 5:35 PM Jeff Law <l...@redhat.com> wrote:>
> > > On 5/30/19 4:56 PM, Martin Sebor wrote:
> > > > On 5/30/19 10:15 AM, Jeff Law wrote:
> > > >> On 5/30/19 9:34 AM, Martin Sebor wrote:
> > > >>
> > > >>>>> If the alias oracle can be used to give the same results without
> > > >>>>> excessive false positives then I think it would be fine to make
> > > >>>>> use of it. Is that something you consider a prerequisite for
> > > >>>>> this change or should I look into it as a followup?
> > > >>>> I think we should explore it a bit before making a final decision.
> > > >>>> It
> > > >>>> may guide us for other work in this space (like detecting escaping
> > > >>>> locals). I think a dirty prototype to see if it's even in the right
> > > >>>> ballpark would make sense.
> > > >>>
> > > >>> Okay, let me look into it.
> > > >> Sounds good. Again, go with a quick prototype to see if it's likely
> > > >> feasible. The tests you've added should dramatically help evaluating
> > > >> if
> > > >> the oracle is up to the task.
> > > >
> > > > So to expand on what I said on the phone when we spoke: the problem
> > > > I quickly ran into with the prototype is that I wasn't able to find
> > > > a way to identify pointers to alloca/VLA storage.
> > > Your analysis matches my very quick read of the aliasing code. It may
> > > be the case that the Steensgaard patent got in the way here.
> > >
> > > >
> > > > In the the points-to solution for the pointer being returned they
> > > > both have the vars_contains_escaped_heap flag set. That seems like
> > > > an omission that shouldn't be hard to fix, but on its own, I don't
> > > > think it would be sufficient.
> > > RIght. In theory the result of an alloca call shouldn't alias anything
> > > in the heap -- but there were some implementations of alloca that were
> > > built on top of malloc (ugh). That flag may be catering to that case.
> > >
> > > But in the case of a __builtin_alloca that shouldn't apply. Hmm. That
> > > ultimately might be a bug.
> > >
> > > >
> > > > In the IL a VLA is represented as a pointer to an array, but when
> > > > returning a pointer into a VLA (at some offset so it's an SSA_NAME),
> > > > the pointer's point-to solution doesn't include the VLA pointer or
> > > > (AFAICS) make it possible to tell even that it is a VLA. For example
> > > > here:
> > > >
> > > > f (int n)
> > > > {
> > > > int * p;
> > > > int[0:D.1912] * a.1;
> > > > sizetype _1;
> > > > void * saved_stack.3_3;
> > > > sizetype _6;
> > > >
> > > > <bb 2> [local count: 1073741824]:
> > > > saved_stack.3_3 = __builtin_stack_save ();
> > > > _1 = (sizetype) n_2(D);
> > > > _6 = _1 * 4;
> > > > a.1_8 = __builtin_alloca_with_align (_6, 32);
> > > > p_9 = a.1_8 + _6;
> > > > __builtin_stack_restore (saved_stack.3_3);
> > > > return p_9;
> > > > }
> > > >
> > > > p_9's solution's is:
> > > >
> > > > p_9, points-to vars: { D.1925 } (escaped, escaped heap)
> > > >
> > > > I couldn't find out how to determine that D.1925 is a VLA (or even
> > > > what it is). It's not among the function's local variables that
> > > > FOR_EACH_LOCAL_DECL iterates over.
> > > It's possible that decl was created internally as part of the alias
> > > oracle's analysis.
> >
> > Yes. Note that only the UID was reserved the fake decl doesn't
> > live on.
> >
> > Note that for the testcase above the "local" alloca storage escapes
> > which means you run into a catch-22 here given points-to computes
> > a conservative correct solution and you want to detect escaping
> > locals. Usually detecting a pointer to local storage can be done
> > by using ptr_deref_may_alias_global_p but of course in this
> > case the storage was marked global by PTA itself (and our PTA
> > is not flow-sensitive and it doesn't distinguish an escape through
> > a return stmt from an escape through a call which is relevant
> > even for local storage).
> >
> > Feature-wise the PTA solver is missing sth like a "filter"
> > we could put in front of return stmts that doesn't let
> > addresses of locals leak. The simplest way of implementing
> > this might be to not include 'returns' in the constraints at all
> > (in non-IPA mode) and handle them by post-processing the
> > solver result. That gets us some additional flow-sensitivity
> > and a way to filter locals. Let me see if I can cook up this.
> >
> > That may ultimatively also help the warning code where you
> > then can use ptr_deref_may_alias_global_p.
> >
> > Sth like the attached - completely untested (the
> > is_global_var check is likely too simplistic...). It does
> > the job on alloca for me.
> >
> > p_5, points-to NULL, points-to vars: { D.1913 }
> > _6, points-to NULL, points-to vars: { D.1913 }
> >
> > foo (int n)
> > {
> > void * p;
> > long unsigned int _1;
> > void * _6;
> >
> > <bb 2> :
> > _1 = (long unsigned int) n_2(D);
> > p_5 = __builtin_alloca (_1);
> > _6 = p_5;
> > return p_5;
>
> I am testing the following fixed and more complete patch (still
> the actual return values we process optimally is restricted).
> I'm not sure whether it will really help real-world testcases
> since the lack of flow-sensitivity in general and the lack of
> distinguishing between escapes via calls vs. escapes via
> return pessimizes things (escapes to global memory complicates
> things there). Also in IPA mode we cannot post-process
> returns like in the hack^Wpatch, a "filter" op would need to be
> added, complicating the solver.
>
> Bootstrap / regtest running on x86_64-unknown-linux-gnu.
Needs another iteration since it miscompiles gengtype and
struct S { int *mem; };
struct S * __attribute__((noinline,noipa))
foo ()
{
struct S *s = __builtin_malloc (sizeof (struct S));
s->mem = __builtin_malloc (sizeof (int));
s->mem[0] = 1;
return s;
}
int
main()
{
struct S *s = foo();
if (s->mem[0] != 1)
__builtin_abort ();
return 0;
}
Richard.
> Richard.
>
> 2019-06-03 Richard Biener <rguent...@suse.de>
>
> * tree-ssa-structalias.c: Include tree-cfg.h.
> (make_heapvar): Do not make heap vars artificial.
> (find_func_aliases_for_builtin_call): Handle stack allocation
> functions.
> (find_func_aliases): Delay processing of simple enough returns
> in non-IPA mode.
> (set_uids_in_ptset): Adjust.
> (find_what_var_points_to): Likewise.
> (compute_points_to_sets): Post-process return statements,
> amending the escaped solution.
>
> * gcc.dg/tree-ssa/alias-37.c: New testcase.
>
> >
> > Richard.
> >
> > > See make_heapvar in tree-ssa-structalias.c
> > > >
> > > > By replacing the VLA in the test case with a call to malloc I get
> > > > this for the returned p_7:
> > > >
> > > > p_7, points-to NULL, points-to vars: { D.1916 } (escaped, escaped
> > > > heap)
> > > >
> > > > Again, I see no way to quickly tell that this pointer points into
> > > > the block returned from malloc.
> > > If there's a way to make that determination it'd have to be on the
> > > variable since the pt_solution flag bits don't carry a storage class
> > > directly.
> > >
> > > You might try to get a handle on those decls and dump them to see if
> > > there's anything easily identifiable. But it may be easier to dig into
> > > the code that creates them. A real quick scan of the aliasing code also
> > > shows the "variable_info" structure. It's private to the aliasing code,
> > > but might guide you at things to look at.
> > >
> > > Regardless, I don't see an immediate path forward using the oracle to
> > > identify objects in the stack for your patch. WHich is unfortunate.
> > >
> > >
> > >
> > >
> > > Jeff
