[PATCH][RFC] Virtual operands in loop-closed SSA form

[PATCH][RFC] Virtual operands in loop-closed SSA form

[Richard Guenther]

While we should already be in loop-closed SSA form for virtual
operands most of the time (because we have a virtual use at
the return statement) and loop-closed SSA form for virtuals
is cheap (we only have a single virtual operand now) the following
makes sure that a loop-closed PHI node for virtuals does exist.

Nobody makes use of the fact but ISTR code that has code explicitely
dealing with the situation that virtuals are _not_ in loop-closed
SSA form.

Testing pending.

Richard.

2012-08-22  Richard Guenther  <rguenther@suse.de>

	* tree-ssa-loop-manip.c (add_exit_phis_var): Allow virtual operands.
	(find_uses_to_rename_use): Likewise.
	(find_uses_to_rename_bb): Likewise.
	(find_uses_to_rename_stmt): Walk over all operands.

Index: gcc/tree-ssa-loop-manip.c
===================================================================
--- gcc/tree-ssa-loop-manip.c	(revision 190590)
+++ gcc/tree-ssa-loop-manip.c	(working copy)
@@ -303,8 +303,7 @@ add_exit_phis_var (tree var, bitmap use_
   basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
   bitmap live_exits = BITMAP_ALLOC (&loop_renamer_obstack);
 
-  gcc_checking_assert (! virtual_operand_p (var));
-  gcc_assert (! bitmap_bit_p (use_blocks, def_bb->index));
+  gcc_checking_assert (! bitmap_bit_p (use_blocks, def_bb->index));
 
   compute_live_loop_exits (live_exits, use_blocks, loop_exits, def_bb);
 
@@ -367,10 +366,6 @@ find_uses_to_rename_use (basic_block bb,
   if (TREE_CODE (use) != SSA_NAME)
     return;
 
-  /* We don't need to keep virtual operands in loop-closed form.  */
-  if (virtual_operand_p (use))
-    return;
-
   ver = SSA_NAME_VERSION (use);
   def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
   if (!def_bb)
@@ -408,7 +403,7 @@ find_uses_to_rename_stmt (gimple stmt, b
   if (is_gimple_debug (stmt))
     return;
 
-  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
+  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
     find_uses_to_rename_use (bb, var, use_blocks, need_phis);
 }
 
@@ -428,9 +423,8 @@ find_uses_to_rename_bb (basic_block bb,
     for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
       {
         gimple phi = gsi_stmt (bsi);
-	if (! virtual_operand_p (gimple_phi_result (phi)))
-	  find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
-				   use_blocks, need_phis);
+	find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
+				 use_blocks, need_phis);
       }
 
   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))

Re: [PATCH][RFC] Virtual operands in loop-closed SSA form

[Steven Bosscher]

On Wed, Aug 22, 2012 at 3:01 PM, Richard Guenther <rguenther@suse.de> wrote:
>
> While we should already be in loop-closed SSA form for virtual
> operands most of the time (because we have a virtual use at
> the return statement) and loop-closed SSA form for virtuals
> is cheap (we only have a single virtual operand now) the following
> makes sure that a loop-closed PHI node for virtuals does exist.

Make sense. I think it would be good to add an explanation of what
this means in the comment before rewrite_into_loop_closed_ssa, because
"liveness" of a memory reference isn't as obvious as that of an ssa
register.

Did you try this with the header-copying change from PR46590 to make
it do only TODO_update_ssa_no_phi?

Ciao!
Steven

Re: [PATCH][RFC] Virtual operands in loop-closed SSA form

[Richard Guenther]

On Wed, 22 Aug 2012, Steven Bosscher wrote:

> On Wed, Aug 22, 2012 at 3:01 PM, Richard Guenther <rguenther@suse.de> wrote:
> >
> > While we should already be in loop-closed SSA form for virtual
> > operands most of the time (because we have a virtual use at
> > the return statement) and loop-closed SSA form for virtuals
> > is cheap (we only have a single virtual operand now) the following
> > makes sure that a loop-closed PHI node for virtuals does exist.
> 
> Make sense. I think it would be good to add an explanation of what
> this means in the comment before rewrite_into_loop_closed_ssa, because
> "liveness" of a memory reference isn't as obvious as that of an ssa
> register.
> 
> Did you try this with the header-copying change from PR46590 to make
> it do only TODO_update_ssa_no_phi?

Yes, but it didn't help :(

The following is the patch I am applying, bootstrapped and tested on
x86_64-unknown-linux-gnu.

Richard.

2012-08-23  Richard Guenther  <rguenther@suse.de>

	* tree-ssa-loop-manip.c (add_exit_phis_var): Allow virtual operands.
	(find_uses_to_rename_use): Likewise.
	(find_uses_to_rename_bb): Likewise.
	(find_uses_to_rename_stmt): Walk over all operands.

Index: gcc/tree-ssa-loop-manip.c
===================================================================
*** gcc/tree-ssa-loop-manip.c.orig	2012-08-22 15:02:02.000000000 +0200
--- gcc/tree-ssa-loop-manip.c	2012-08-23 09:14:02.141575345 +0200
*************** add_exit_phis_var (tree var, bitmap use_
*** 303,310 ****
    basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
    bitmap live_exits = BITMAP_ALLOC (&loop_renamer_obstack);
  
!   gcc_checking_assert (! virtual_operand_p (var));
!   gcc_assert (! bitmap_bit_p (use_blocks, def_bb->index));
  
    compute_live_loop_exits (live_exits, use_blocks, loop_exits, def_bb);
  
--- 303,309 ----
    basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
    bitmap live_exits = BITMAP_ALLOC (&loop_renamer_obstack);
  
!   gcc_checking_assert (! bitmap_bit_p (use_blocks, def_bb->index));
  
    compute_live_loop_exits (live_exits, use_blocks, loop_exits, def_bb);
  
*************** find_uses_to_rename_use (basic_block bb,
*** 367,376 ****
    if (TREE_CODE (use) != SSA_NAME)
      return;
  
-   /* We don't need to keep virtual operands in loop-closed form.  */
-   if (virtual_operand_p (use))
-     return;
- 
    ver = SSA_NAME_VERSION (use);
    def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
    if (!def_bb)
--- 366,371 ----
*************** find_uses_to_rename_stmt (gimple stmt, b
*** 408,414 ****
    if (is_gimple_debug (stmt))
      return;
  
!   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
      find_uses_to_rename_use (bb, var, use_blocks, need_phis);
  }
  
--- 403,409 ----
    if (is_gimple_debug (stmt))
      return;
  
!   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
      find_uses_to_rename_use (bb, var, use_blocks, need_phis);
  }
  
*************** find_uses_to_rename_bb (basic_block bb,
*** 428,436 ****
      for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
        {
          gimple phi = gsi_stmt (bsi);
! 	if (! virtual_operand_p (gimple_phi_result (phi)))
! 	  find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
! 				   use_blocks, need_phis);
        }
  
    for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
--- 423,430 ----
      for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
        {
          gimple phi = gsi_stmt (bsi);
! 	find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
! 				 use_blocks, need_phis);
        }
  
    for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
*************** find_uses_to_rename (bitmap changed_bbs,
*** 474,479 ****
--- 468,476 ----
  
     1) Updating it during unrolling/peeling/versioning is trivial, since
        we do not need to care about the uses outside of the loop.
+       The same applies to virtual operands which are also rewritten into
+       loop closed SSA form.  Note that virtual operands are always live
+       until function exit.
     2) The behavior of all uses of an induction variable is the same.
        Without this, you need to distinguish the case when the variable
        is used outside of the loop it is defined in, for example

Re: [PATCH][RFC] Virtual operands in loop-closed SSA form

[Steven Bosscher]

On Thu, Aug 23, 2012 at 9:35 AM, Richard Guenther <rguenther@suse.de> wrote:
> +       The same applies to virtual operands which are also rewritten into
> +       loop closed SSA form.  Note that virtual operands are always live
> +       until function exit.

Ouch!
What does this do to the memory foot print and compile time for PR54146?

Ciao!
Steven