Re: IPA merge 4: SSA inliner

[Diego Novillo <dnovillo at redhat dot com>]

Jan Hubicka wrote on 12/03/06 14:34:
> Hi,
> this patch updates inliner to deal with SSA (so it now can handle both SSA and
> non-SSA gimple.  This is quite natural to do, since SSA is more an extension of
> IL than different one and also needed for -O0 inlining).  The SSA code is
> unused now, since we are not quite ready to reorder the pass queue (with my
> passmanager patch, one can do it and get crashes on testcases with static
> variables, I have patch for static variables in queue), however I am sending
> it, so we can parallelize the efforts and as example how SSA updating on IPA
> level looks like now.
>
> Some interesting stuff:
>
>  1) Inserting SSA body into SSA body is basically easy, since dominator
>     tree change little.  SSA names for automatic variables in outer function
>     don't need to change, most of SSA in internal function doesn't either.
>     
>     So the basic idea is to have remap_ssa_name producing new SSA names for
>     copied ones and new copy_phis_for_bb re-creating PHI nodes in the copied
>     body according to the original PHIs.
>  2) For virtual operands I simply trigger rebuild of SSA of everything
>     mentioned.  The scheme outlined above doesn't work for static variables
>     touched by both inlined and callee functions since we need to merge
>     SSA form built on those.
>  3) SSA names for return decls are stripped away and SSA form is rebuilt.
>     This should be fine since there ought to be only one name as we have
>     single return_stmt.  We however might break SSA from otherwise in the case
>     function returned partially uninitialized return value
>  4) SSA operands are copy/constant propagated by inliner.  Inliner always
>     constant propagated in order to get "const" declared arguments right.
>     We can easilly do more, but it also tend to uncover latent bugs.
>     I did little measurements on tramp3d and not doing the constant/copy
>     prop increases number of SSA names built by 30%, so I think it is worthwhile
>     (and it also makes it easier to inline callbacks)
I'd like to know what bugs this uncovered.  In the optimizer or the
inliner?

>  5) EH edges comming from inlined function body to landing paths within outer
>     function cause troubles since PHI nodes can be associated with the landing
>     pads.  I discussed this with Rth on the summit and we concluded it is safe
>     to to rebuild SSA on those symbols: since they have PHIs on abnormal edges
>     we don't have overlapping liveranges.
Yes.

>  6) Problematic are also return values returned via slot.  These variables
>     do have address taken (technically to pass to inlined function) but we
>     don't model it properly in the outer function, so they might be in SSA form
>     and we might have issues with partly initialized return values.
We don't detect that the symbol's address has been taken?  That's not
good.  Got a test case?

> Honza
>
> 	* tree-inline.c (remap_ssa_name): New function.
> 	(remap_decl): Update SSA datastructures for DECLs.
> 	(copy_body_r): Deal with SSA_NAMEs; add referenced global vars.
> 	(copy_bb): Set SSA_NAME def stmts.
> 	(update_ssa_acorss_eh_edges): New function.
> 	(copy_edge_for_bb): Call it; mark new vars for renaming.
> 	(copy_phis_for_bb): New function.
> 	(initialize_cfun): Break out from ...
> 	(copy_cfg_body): ... here; maintain AUX map for both directions;
> 	call SSA updating workers.
> 	(setup_one_parameter): Do propagation across SSA form.
> 	(declare_return_variable): Work on SSA.
> 	(expand_call_inline): Update SSA from on return values.
> 	(optimize_inline_calls): Do sanity checking, dead blocks removal,
> 	update SSA form.
> 	(tree_function_verioning): Update initialize_cfun.
> Index: tree-inline.c
> ===================================================================
> *** tree-inline.c	(revision 119454)
> --- tree-inline.c	(working copy)
> *************** Boston, MA 02110-1301, USA.  */
> *** 49,54 ****
> --- 49,55 ----
>   #include "debug.h"
>   #include "pointer-set.h"
>   #include "ipa-prop.h"
> + #include "tree-pass.h"
>   
>   /* I'm not real happy about this, but we need to handle gimple and
>      non-gimple trees.  */
> *************** insert_decl_map (copy_body_data *id, tre
> *** 140,145 ****
> --- 141,190 ----
>   		       (splay_tree_value) value);
>   }
>   
> + /* Construct new SSA name for old one.  */
> + 
Document the arguments.

> + static tree
> + remap_ssa_name (tree name, copy_body_data *id)
> + {
> +   tree new;
> +   splay_tree_node n;
> + 
> +   gcc_assert (TREE_CODE (name) == SSA_NAME);
> + 
> +   n = splay_tree_lookup (id->decl_map, (splay_tree_key) name);
> +   if (n)
> +     return (tree) n->value;
> + 
> +   /* Do not set DEF_STMT yet as statement might not get copied.  */
> +   new = remap_decl (SSA_NAME_VAR (name), id);
What?  If you are copying the SSA name, why wouldn't you copy the
statement that defined it?  Is this name going to become a default
definition?

> +   /* We might've substituted constant or another SSA_NAME for
> +      the variable.  */
> +   if ((TREE_CODE (new) == VAR_DECL || TREE_CODE (new) == PARM_DECL)
> +       /* Replace the SSA name representing RESULT_DECL by variable during
> + 	 inlining:  this saves us from need to introduce PHI node in a case
> + 	 return value is just partly initialized.  */
Move this comment before the if().  It's better to have a longer
description before the whole if() than break appart the flow of the
predicates with extraneous commentary.  Additionally, I have no idea
what you were trying to say in that comment.

> +       && (TREE_CODE (SSA_NAME_VAR (name)) != RESULT_DECL
> + 	  || !id->transform_return_to_modify))
> +     {
> +       new = make_ssa_name (new, NULL);
> +       insert_decl_map (id, name, new);
> +       if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (name))
> + 	  /* When inlining, parameters are replaced by initialized vars.  */
> + 	  && (TREE_CODE (new) == PARM_DECL || TREE_CODE (name) != PARM_DECL))
How could 'name' be anything other than an SSA_NAME?  '|| TREE_CODE
(name) != PARM_DECL' is trivially true.

> + 	{
> + 	  SSA_NAME_DEF_STMT (new) = build_empty_stmt ();
> + 	  if (gimple_default_def (id->src_cfun, SSA_NAME_VAR (name)) == name)
> + 	    set_default_def (SSA_NAME_VAR (new), new);
> + 	}
> +       SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new)
> + 	= SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name);
> +     }
> +   else
> +     insert_decl_map (id, name, new);
> +   TREE_TYPE (new) = remap_type (TREE_TYPE (name), id);
> +   return new;
> + }
> + 
>   /* Remap DECL during the copying of the BLOCK tree for the function.  */
>   
>   tree
> *************** remap_decl (tree decl, copy_body_data *i
> *** 187,192 ****
> --- 232,255 ----
>   	    walk_tree (&DECL_QUALIFIER (t), copy_body_r, id, NULL);
>   	}
>   
> +       if (cfun && gimple_in_ssa_p (cfun)
> + 	  && (TREE_CODE (t) == VAR_DECL
> + 	      || TREE_CODE (t) == RESULT_DECL || TREE_CODE (t) == PARM_DECL))
> + 	{
> + 	  tree def;
> + 
> + 	  get_var_ann (t);
> + 	  if (TREE_CODE (decl) != PARM_DECL
> + 	      && (def = gimple_default_def (id->src_cfun, decl)))
>                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
SSA_NAME_IS_DEFAULT_DEF (def)

> + 
> +       /* Global variables we didn't seen yet needs to go into referenced
> + 	 vars.  */
s/didn't seen yet needs to/have not seen yet/

> + 	  if (gimple_in_ssa_p (cfun))
> + 	    {
> + 	       ssa_op_iter i;
> + 	       tree def;
> + 
> + 	       FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
> + 		if (TREE_CODE (def) == SSA_NAME)
> + 		  SSA_NAME_DEF_STMT (def) = stmt;
> + 	    }
So, you set DEF statement for all the remapped names here?  If so,
then I'm not so concerned about setting DEF_STMT to NULL in
remap_ssa_name.

>   	}
>       }
>     return copy_basic_block;
>   }
>   
> + /* Inserting Single Entry Multiple Exit region in SSA form into code in SSA
> +    form is quite easy, since dominator relationship for old basic blocks does
> +    not change.
> + 
> +    There is however exception where inlining might change dominatorships across
> +    EH edges from basic block within inlined functions destinating to landging
> +    pads in function we inline into.
> + 
Rephrase.  It's unclear what you are trying to say here.

> +    It is safe to mark PHI_RESULT of such PHI nodes for renaming; the EH edges
> +    are abnormal and SSA_NAME_OCCURS_IN_ABNORMAL_PHI must be set.
Add something like 'this means, that there will be no overlapping live
ranges for the underlying symbol."

> +    This might change in future if we allow redirecting of EH edges and
> +    we might want to change way build CFG pre-inlining to include
> +    all the possible edges then.  */
You don't seem to be documenting what the function *does*.
Documentation for BB is also missing.

> + static void
> + update_ssa_across_eh_edges (basic_block bb)
> + {
> +   edge e;
> +   edge_iterator ei;
> + 
> +   FOR_EACH_EDGE (e, ei, bb->succs)
> +     if (!e->dest->aux
> + 	|| ((basic_block)e->dest->aux)->index == ENTRY_BLOCK)
> +       {
> + 	tree phi;
> + 
> + 	gcc_assert (e->flags & EDGE_EH);
> + 	for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
> + 	  {
> + 	    gcc_assert (SSA_NAME_OCCURS_IN_ABNORMAL_PHI
> + 			(PHI_RESULT (phi)));
> + 	    mark_sym_for_renaming
> + 	      (SSA_NAME_VAR (PHI_RESULT (phi)));
> + 	  }
> +       }
> + }
> + 
>   /* Copy edges from BB into its copy constructed earlier, scale profile
>      accordingly.  Edges will be taken care of later.  Assume aux
>      pointers to point to the copies of each BB.  */
> *************** copy_edges_for_bb (basic_block bb, int c
> *** 821,826 ****
> --- 940,947 ----
>   
>         copy_stmt = bsi_stmt (bsi);
>         update_stmt (copy_stmt);
> +       if (gimple_in_ssa_p (cfun))
> +         mark_new_vars_to_rename (copy_stmt);
Careful here.  This has disappeared.  You *could* use
mark_symbols_for_renaming, but that only works if the symbols you want
to rename are not wrapped in SSA names in the operands.  What symbols
are you trying to mark for renaming here?

> + /* Copy the PHIs.  All blocks and edges was copied, some blocks
> +    was possibly splited and new outgoing EH edges inserted.
s/was/are/
s/splited/split/

> +    BB points to the block of original function and AUX pointers links
> +    the original and newly copied blocks.  */
Spacing.

> + /* Build struct function and associated datastructures for the new clone
> +    to be build.  */
s/build/built/
Spacing.
You need to document the arguments.

> +      We might want to introduce a notion that single SSA_NAME might
> +      represent multiple variables for purposes of debugging. */
No.  Lord, no.

> +   if (gimple_in_ssa_p (cfun) && rhs && def && is_gimple_reg (p)
> +       && (TREE_CODE (rhs) == SSA_NAME
> + 	  /* Replacing &""[0] has interesting side effects.  Exclude ADDR_EXPRs
> + 	     now.  */
What are those side effects?  Again, I'd rather have this comment
before the if().  Though, I guess I can't win this argument as I see
lots of instances like this one sprinkled all over the place.

> ! 	  def = remap_ssa_name (def, id);
> !           init_stmt = build2 (MODIFY_EXPR, TREE_TYPE (var), def, rhs);
You mean GIMPLE_MODIFY_STMT here.

> ! 	      /* FIXME: rewriting random variables in SSA form is going
> ! 		 to cause missoptimizations once we start optimizing. 
> ! 
I don't understand this.  Why would we have mis-optimizations?  Show
me sample code?

> !     {
> !       /* Handle case of inlining function that miss return statement so return value becomes
> !          undefined.  */
Line wrapping.

> !       if (TREE_CODE (stmt) == MODIFY_EXPR
GIMPLE_MODIFY_STMT.