Re: [tree-ssa]: Loop LICM, take 2

[Diego Novillo <dnovillo at redhat dot com>]

On Tue, 2003-08-26 at 09:31, Daniel Berlin wrote:

> Diego, give this one a try.
> It bootstraps, i'm running regression tests now.
>
It looks mostly OK.  But it needs a ton of comments and blank lines to
separate the different functions.  I would've thought that we want to
proceed in loop nesting order so that we could avoid visiting nested
loops.  

> Index: cfgloop.c
> ===================================================================
> RCS file: /cvs/gcc/gcc/gcc/cfgloop.c,v
> --- cfgloop.c	23 Jul 2003 16:59:32 -0000	1.14.2.11
> +++ cfgloop.c	24 Aug 2003 20:02:03 -0000
> @@ -696,6 +696,7 @@
>    rc_order = NULL;
> 
>    /* Join loops with shared headers.  */
> +  if (0)
>    canonicalize_loop_headers ();
> 
>    /* Compute the dominators.  */
> @@ -735,9 +736,11 @@
>  	     from a latch node.  */
>  	  if (latch != ENTRY_BLOCK_PTR && dominated_by_p (dom, latch, header))
>  	    {
> +#if 0
>  	      /* Shared headers should be eliminated by now.  */
>  	      if (more_latches)
>  		abort ();
> +#endif
>  	      more_latches = 1;
>  	      SET_BIT (headers, header->index);
>  	      num_loops++;
>
We need to address these two hacks before adding LICM.  Why are they
necessary?  What would it take to actually fix the problem?


> Index: tree-cfg.c
> ===================================================================
> RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
> --- tree-cfg.c	24 Aug 2003 03:04:40 -0000	1.1.4.155
> +++ tree-cfg.c	24 Aug 2003 20:02:06 -0000
> @@ -2147,6 +2147,11 @@
>  {
>    tree stmt = bsi_stmt (from);
>    remove_bsi_from_block (&from, false);
> +  if (!bsi_end_p (to))
> +    {
> +      stmt_ann (stmt)->scope = stmt_ann (bsi_stmt (to))->scope;
> +      stmt_ann (stmt)->scope_level = stmt_ann (bsi_stmt (to))->scope_level;
> +    }
>    bsi_insert_after (&to, stmt, BSI_SAME_STMT);
>  }
> 
> @@ -2157,6 +2162,11 @@
>  {
>    tree stmt = bsi_stmt (from);
>    remove_bsi_from_block (&from, false);
> +  if (!bsi_end_p (to))
> +    {
> +      stmt_ann (stmt)->scope = stmt_ann (bsi_stmt (to))->scope;
> +      stmt_ann (stmt)->scope_level = stmt_ann (bsi_stmt (to))->scope_level;
> +    }
>    bsi_insert_before (&to, stmt, BSI_SAME_STMT);
>  }
> 
So, if we are moving into an empty block, we lose the scope for the
statement?

> +static void
> +hoist_invariants_in (struct loop *loop)
> +{
> +  size_t i;
> +  basic_block *bbs;
> +
> +  bitmap loop_body = BITMAP_GGC_ALLOC ();
> +  bitmap_clear (loop_body);
> +
> +  bbs = get_loop_body (loop);
> +  for (i = 0; i < loop->num_nodes; i++)
> +    if (bbs[i]->index >= 0)
> +      bitmap_set_bit (loop_body, bbs[i]->index);
> +
> +  for (i = 0; i < loop->num_nodes; i++)
> +    {
> +      block_stmt_iterator bsi;
> +      if (bsi_end_p (bsi_start (bbs[i])))
> +	continue;
> +
This doesn't seem necessary.

> +      for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
> +	{
> +	  tree stmt = bsi_stmt (bsi);
> +	  varray_type uses;
> +	  varray_type vuses;
> +	  size_t j;
> +	  bool can_hoist = true;
> +
> +	  if (IS_EMPTY_STMT (stmt)
> +	      || contains_unrenamed_variables (stmt)
> +	      || TREE_CODE (stmt) != MODIFY_EXPR
> +	      || TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
> +
> +	    continue;
>
Why are you making all these checks?  What I had in mind is something
like: if all the uses and vuses of the statement come from outside the
loop and the statement has no volatile operands, lift it (which is
roughly what you do below).  Why are you checking for unrenamed
variables?  Why do you care whether the LHS of the assignment is an SSA
name?  Perhaps we need to add some information to the SSA web?

> +static void
> +hoist_invariants (tree fndecl, struct loops *loops)
> +{
> +  int i;
> +  licm_dump_file = dump_begin (TDI_loop_licm, &licm_dump_flags);
> +  flow_loops_dump (loops, licm_dump_file, NULL, 0);
> +
> +  for (i = loops->num - 1; i >= 0; i--)
>
Any particular reason why we proceed in this order?  I would've thought
that we want to traverse the loop tree from the top down, so that we
don't have visit all the loops in a nest.


Diego.