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. 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