stack variable liveness analysis

[Xinliang David Li]

On Mon, Aug 24, 2009 at 4:53 AM, Michael Matz<matz@suse.de> wrote:
> Hi,
>
> On Sun, 23 Aug 2009, Xinliang David Li wrote:
>
>> 1) It is not the intension of this patch to replace existing scope
>> based stack layout scheme with a liveness analysis based one. The
>> intension of the patch is to only catch  DEFINITE conflicts (which are
>> most common), so the implementation ignores may-aliases to reduce
>> false positives. IMHO, a complete liveness based solution won't be
>> practical as the may-aliases and arrays are hard to deal with -- you
>> may end up with a stack layout way too conservative than necessary. A
>> feasible solution is to perform 'overlay' in early phases of compiler
>> when language required live times are still valid. The layout pass
>> will need to be done after each inline phase as well.
>> 2) the implementation tracks liveness at byte level for record typed
>> variables to avoid false negatives.
>>
>> Please evaluate if this is a good thing to have for trunk.  The patch is
>> regression tested with the bootstrapped compiler (x86_64/linux), and
>> also tested with SPEC2k/06 (C/C++) with FDO.
>
> All top-level vars conflict with everything else, no need to handle
> them or look at them.  --param stack-var-anal-top-level seems only to
> exist for the testcases.  Rewrite the testcases to contain everything in a
> subblock, then you don't need it anymore.
>
> +  top_level_vars = pointer_set_create ();
> +
> +  for (t = BLOCK_VARS (outer_block); t ; t = TREE_CHAIN (t))
> +    pointer_set_insert (top_level_vars, t);
>
> You don't need a pointer set for detecting top-level vars.  Use
>  TREE_BLOCK (var) == DECL_INITIAL (current_function_decl)
> for that.


Hmm, got assertion on this one -- tree_block expects expression code
class not declarations.


David


>
> You should check for references being trivially not stack-vars in the
> walk_tree thingy.  E.g. SSA_NAMEs don't have to be handled (you don't add
> them to the sets in the end anyway, but you do useless hashtable checking
> on them).  You don't need to handle some of the *_REF tree codes as they
> can only contain SSA_NAMEs or constants (e.g. the INDIRECT_REFs,
> theoretically they might contain also ADDR_REFs of stack decls, but that's
> considered invalid and would probably lead to breakages elsewhere).
>
> The byte-wise tracking doesn't look appealing IMHO, not the least because
> it fails to address the problem for arrays.  Unfortunately I don't have a
> real alternative.  Maybe it would be good to persue the idea of somehow
> marking the conservatively "first" occurences of each stack decl and only
> regard those as kill points, but not the intermediate ones.  The
> intermediates would be those for which at least one path from ENTRY exists
> that doesn't contain another definition of the same decl.  That would be
> another data-flow problem though, and it's already slow enough :-/
>
>
> Ciao,
> Michael.
>