Re: stack variable liveness analysis

[Michael Matz <matz at suse dot de>]

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.

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.