On Fri, May 31, 2019 at 5:35 PM Jeff Law 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; > > > > [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; : _1 = (long unsigned int) n_2(D); p_5 = __builtin_alloca (_1); _6 = p_5; return p_5; 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