[patch] Lno branch merge part 6 -- loop closed ssa form

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

this patch implements creation of loop closed ssa form, i.e.
strenghtening of the ssa form requirements by the property that no
ssa name is used outside of the loop it is defined in, using the
standard convention that uses in phi nodes are assumed to be in the
starting basic block of the edge.  The property is achieved by inserting
phi nodes (possibly with just one argument) to the loop exits as
necessary.

This strengthening of the basic ssa form has several advantages:

1) Updating it during unrolling/peeling/versioning is trivial, since
   we do not need to care about the uses outside of the loop.
2) The behavior of all uses of an induction variable is the same
   wrto induction variable analysis.
   Without loop closed ssa form, you need to distinguish the case when
   the variable is used outside of the loop it is defined in, for example

   for (i = 0; i < 100; i++)
     {
       for (j = 0; j < 100; j++)
	 {
	   k = i + j;
	   use1 (k);
	 }
       use2 (k);
     }

   Looking from the outer loop with the normal SSA form, the first use of k
   is not well-behaved, while the second one is an induction variable with
   base 99 and step 1.

The patch causes this strenghtening to be created just before the loop
optimizer (and it is removed by first copy propagation pass).  The other
approach (proposed by Kenneth) would be to create the loop closed ssa
form in the beginning and preserve it all the time.  I did not choose
this way for the following reasons:

1) Memory: We need to create quite many new phi nodes and ssa names
   (mostly due to presence of virtual names, that tend to be used on
   many places throughout the program).  Preserving them all the time
   would unnecessarily slow down unrelated optimization passes.
2) Problems with updating: all passes would have to be updated to
   a) not kill phi nodes on loop exits; which may sometimes be a bit
      problematic if we do not want to decrease the power of the
      optimization.
   b) update/preserve loop closed ssa form, in cases 
        -- when something is inserted to the exit of the loop (easy)
	-- when some expression or its part is hoisted outside of loop
	   through exit(s).  Harder, but we probably do not do anything
	   of this type at the moment.
	-- when new loop is created.  This is easy if the optimization knows
	   about loops.  The problematic would be the case when an
	   irreducible region is turned into regular loop say by
	   constant propagation or jump threading; we would basically
	   need to create the loop closed ssa form for the variables
	   inside the loop using the generic algorithm anyway.
3) Limited usefullness outside of the loop optimizer. The exit phi nodes for real
   (not virtual) names could be probably useful for value range
   analysis, but that's about it.

Basically the only advantage of creating the loop closed ssa form early
is that it avoids one ssa creation pass; given that the possible
compilation time gains would be decreased/negated by 1), this did not
seem to be important enough to me.

Bootstrapped & regtested on ia64.

Zdenek

	* tree-ssa-loop-manip.c: New file.
	* Makefile.in (tree-ssa-loop-manip.o): Add.
	* tree-flow.h (rewrite_into_loop_closed_ssa, verify_loop_closed_ssa):
	Declare.
	* tree-ssa-loop.c (tree_loop_optimizer_init): Create loop closed ssa
	form.

Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1315
diff -c -3 -p -r1.1315 Makefile.in
*** Makefile.in	30 Jun 2004 21:11:25 -0000	1.1315
--- Makefile.in	30 Jun 2004 21:40:03 -0000
*************** OBJS-common = \
*** 898,904 ****
   cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o		   \
   cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o	   \
   cfgrtl.o combine.o conflict.o convert.o coverage.o cse.o cselib.o 	   \
!  dbxout.o ddg.o tree-ssa-loop-ch.o loop-invariant.o			   \
   debug.o df.o diagnostic.o dojump.o dominance.o loop-doloop.o		   \
   dwarf2asm.o dwarf2out.o emit-rtl.o except.o explow.o loop-iv.o		   \
   expmed.o expr.o final.o flow.o fold-const.o function.o gcse.o		   \
--- 898,904 ----
   cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o		   \
   cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o	   \
   cfgrtl.o combine.o conflict.o convert.o coverage.o cse.o cselib.o 	   \
!  dbxout.o ddg.o tree-ssa-loop-ch.o tree-ssa-loop-manip.o loop-invariant.o  \
   debug.o df.o diagnostic.o dojump.o dominance.o loop-doloop.o		   \
   dwarf2asm.o dwarf2out.o emit-rtl.o except.o explow.o loop-iv.o		   \
   expmed.o expr.o final.o flow.o fold-const.o function.o gcse.o		   \
*************** tree-ssa-loop-ch.o : tree-ssa-loop-ch.c 
*** 1679,1684 ****
--- 1679,1688 ----
     $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) tree-inline.h \
     output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
     tree-pass.h flags.h
+ tree-ssa-loop-manip.o : tree-ssa-loop-manip.c $(TREE_FLOW_H) $(CONFIG_H) \
+    $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) \
+    output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
+    tree-pass.h cfglayout.h
  tree-ssa-alias.o : tree-ssa-alias.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
     $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) tree-inline.h $(FLAGS_H) \
     function.h $(TIMEVAR_H) tree-alias-common.h convert.h $(TM_H) coretypes.h \
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.17
diff -c -3 -p -r2.17 tree-flow.h
*** tree-flow.h	30 Jun 2004 21:28:59 -0000	2.17
--- tree-flow.h	30 Jun 2004 21:40:03 -0000
*************** extern void propagate_value (use_operand
*** 595,600 ****
--- 595,604 ----
  extern void propagate_tree_value (tree *, tree);
  extern void replace_exp (use_operand_p, tree);
  
+ /* In tree-ssa-loop*.c  */
+ void rewrite_into_loop_closed_ssa (void);
+ void verify_loop_closed_ssa (void);
+ 
  /* In tree-flow-inline.h  */
  static inline int phi_arg_from_edge (tree, edge);
  static inline bool may_propagate_copy (tree, tree);
Index: tree-ssa-loop-manip.c
===================================================================
RCS file: tree-ssa-loop-manip.c
diff -N tree-ssa-loop-manip.c
*** /dev/null	1 Jan 1970 00:00:00 -0000
--- tree-ssa-loop-manip.c	30 Jun 2004 21:40:03 -0000
***************
*** 0 ****
--- 1,341 ----
+ /* High-level loop manipulation functions.
+    Copyright (C) 2004 Free Software Foundation, Inc.
+    
+ This file is part of GCC.
+    
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by the
+ Free Software Foundation; either version 2, or (at your option) any
+ later version.
+    
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+    
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING.  If not, write to the Free
+ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA.  */
+ 
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "tree.h"
+ #include "rtl.h"
+ #include "tm_p.h"
+ #include "hard-reg-set.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "diagnostic.h"
+ #include "tree-flow.h"
+ #include "tree-dump.h"
+ #include "timevar.h"
+ #include "cfgloop.h"
+ #include "tree-pass.h"
+ #include "cfglayout.h"
+ 
+ /* Add exit phis for the USE on EXIT.  */
+ 
+ static void
+ add_exit_phis_edge (basic_block exit, tree use)
+ {
+   tree phi, def_stmt = SSA_NAME_DEF_STMT (use);
+   basic_block def_bb = bb_for_stmt (def_stmt);
+   struct loop *def_loop;
+   edge e;
+ 
+   /* Check that some of the edges entering the EXIT block exits a loop in
+      that USE is defined.  */
+   for (e = exit->pred; e; e = e->pred_next)
+     {
+       def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
+       if (!flow_bb_inside_loop_p (def_loop, e->dest))
+ 	break;
+     }
+ 
+   if (!e)
+     return;
+ 
+   phi = create_phi_node (use, exit);
+ 
+   for (e = exit->pred; e; e = e->pred_next)
+     add_phi_arg (&phi, use, e);
+ 
+   SSA_NAME_DEF_STMT (use) = def_stmt;
+ }
+ 
+ /* Add exit phis for VAR that is used in LIVEIN.
+    Exits of the loops are stored in EXITS.  */
+ 
+ static void
+ add_exit_phis_var (tree var, bitmap livein, bitmap exits)
+ {
+   bitmap def;
+   int index;
+   basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
+ 
+   bitmap_clear_bit (livein, def_bb->index);
+ 
+   def = BITMAP_XMALLOC ();
+   bitmap_set_bit (def, def_bb->index);
+   compute_global_livein (livein, def);
+   BITMAP_XFREE (def);
+ 
+   EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index,
+ 			    add_exit_phis_edge (BASIC_BLOCK (index), var));
+ }
+ 
+ /* Add exit phis for the names marked in NAMES_TO_RENAME.
+    Exits of the loops are stored in EXITS.  Sets of blocks where the ssa
+    names are used are stored in USE_BLOCKS.  */
+ 
+ static void
+ add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
+ {
+   unsigned i;
+ 
+   EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i,
+     {
+       add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
+     });
+ }
+ 
+ /* Returns a bitmap of all loop exit edge targets.  */
+ 
+ static bitmap
+ get_loops_exits (void)
+ {
+   bitmap exits = BITMAP_XMALLOC ();
+   basic_block bb;
+   edge e;
+ 
+   FOR_EACH_BB (bb)
+     {
+       for (e = bb->pred; e; e = e->pred_next)
+ 	if (e->src != ENTRY_BLOCK_PTR
+ 	    && !flow_bb_inside_loop_p (e->src->loop_father, bb))
+ 	  {
+ 	    bitmap_set_bit (exits, bb->index);
+ 	    break;
+ 	  }
+     }
+ 
+   return exits;
+ }
+ 
+ /* For USE in BB, if it is used outside of the loop it is defined in,
+    mark it in NAMES_TO_RENAME.  Record basic block BB where it is used
+    to USE_BLOCKS.  */
+ 
+ static void
+ find_uses_to_rename_use (basic_block bb, tree use, bitmap names_to_rename,
+ 			 bitmap *use_blocks)
+ {
+   unsigned ver;
+   basic_block def_bb;
+   struct loop *def_loop;
+ 
+   if (TREE_CODE (use) != SSA_NAME)
+     return;
+ 
+   ver = SSA_NAME_VERSION (use);
+   def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
+   if (!def_bb)
+     return;
+   def_loop = def_bb->loop_father;
+ 
+   /* If the definition is not inside loop, it is not interesting.  */
+   if (!def_loop->outer)
+     return;
+ 
+   if (!use_blocks[ver])
+     use_blocks[ver] = BITMAP_XMALLOC ();
+   bitmap_set_bit (use_blocks[ver], bb->index);
+ 
+   if (!flow_bb_inside_loop_p (def_loop, bb))
+     bitmap_set_bit (names_to_rename, ver);
+ }
+ 
+ /* For uses in STMT, mark names that are used outside of the loop they are
+    defined in in NAMES_TO_RENAME.  Record the set of blocks in that the ssa
+    names are defined to USE_BLOCKS.  */
+ 
+ static void
+ find_uses_to_rename_stmt (tree stmt, bitmap names_to_rename,
+ 			  bitmap *use_blocks)
+ {
+   use_optype uses;
+   vuse_optype vuses;
+   v_may_def_optype v_may_defs;
+   stmt_ann_t ann;
+   unsigned i;
+   basic_block bb = bb_for_stmt (stmt);
+ 
+   get_stmt_operands (stmt);
+   ann = stmt_ann (stmt);
+ 
+   uses = USE_OPS (ann);
+   for (i = 0; i < NUM_USES (uses); i++)
+     find_uses_to_rename_use (bb, USE_OP (uses, i),
+ 			     names_to_rename, use_blocks);
+ 
+   vuses = VUSE_OPS (ann);
+   for (i = 0; i < NUM_VUSES (vuses); i++)
+     find_uses_to_rename_use (bb, VUSE_OP (vuses, i),
+ 			     names_to_rename, use_blocks);
+ 
+   v_may_defs = V_MAY_DEF_OPS (ann);
+   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
+     find_uses_to_rename_use (bb, V_MAY_DEF_OP (v_may_defs, i),
+ 			     names_to_rename, use_blocks);
+ }
+ 
+ /* Marks names that are used outside of the loop they are defined in
+    in NAMES_TO_RENAME.  Records the set of blocks in that the ssa
+    names are defined to USE_BLOCKS.  */
+ 
+ static void
+ find_uses_to_rename (bitmap names_to_rename, bitmap *use_blocks)
+ {
+   basic_block bb;
+   block_stmt_iterator bsi;
+   tree phi;
+   unsigned i;
+ 
+   FOR_EACH_BB (bb)
+     {
+       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ 	for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
+ 	  find_uses_to_rename_use (PHI_ARG_EDGE (phi, i)->src,
+ 				   PHI_ARG_DEF (phi, i), names_to_rename,
+ 				   use_blocks);
+ 
+       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ 	find_uses_to_rename_stmt (bsi_stmt (bsi),
+ 				  names_to_rename, use_blocks);
+     }
+ }
+ 
+ /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
+    phi nodes to ensure that no variable is used outside the loop it is
+    defined in.
+ 
+    This strengthening of the basic ssa form has several advantages:
+ 
+    1) Updating it during unrolling/peeling/versioning is trivial, since
+       we do not need to care about the uses outside of the loop.
+    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
+ 
+       for (i = 0; i < 100; i++)
+ 	{
+ 	  for (j = 0; j < 100; j++)
+ 	    {
+ 	      k = i + j;
+ 	      use1 (k);
+ 	    }
+ 	  use2 (k);
+ 	}
+ 
+       Looking from the outer loop with the normal SSA form, the first use of k
+       is not well-behaved, while the second one is an induction variable with
+       base 99 and step 1.  */
+ 
+ void
+ rewrite_into_loop_closed_ssa (void)
+ {
+   bitmap names_to_rename = BITMAP_XMALLOC ();
+   bitmap loop_exits = get_loops_exits ();
+   bitmap *use_blocks;
+   unsigned i;
+ 
+   use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
+ 
+   /* Find the uses outside loops.  */
+   find_uses_to_rename (names_to_rename, use_blocks);
+ 
+   /* Add the phi nodes on exits of the loops for the names we need to
+      rewrite.  */
+   add_exit_phis (names_to_rename, use_blocks, loop_exits);
+ 
+   for (i = 0; i < num_ssa_names; i++)
+     BITMAP_XFREE (use_blocks[i]);
+   free (use_blocks);
+   BITMAP_XFREE (loop_exits);
+ 
+   /* Do the rewriting.  */
+   rewrite_ssa_into_ssa (names_to_rename);
+   BITMAP_XFREE (names_to_rename);
+ }
+ 
+ /* Check invariants of the loop closed ssa form for the USE in BB.  */
+ 
+ static void
+ check_loop_closed_ssa_use (basic_block bb, tree use)
+ {
+   tree def;
+   basic_block def_bb;
+   
+   if (TREE_CODE (use) != SSA_NAME)
+     return;
+ 
+   def = SSA_NAME_DEF_STMT (use);
+   def_bb = bb_for_stmt (def);
+   if (def_bb
+       && !flow_bb_inside_loop_p (def_bb->loop_father, bb))
+     abort ();
+ }
+ 
+ /* Checks invariants of loop closed ssa form in statement STMT in BB.  */
+ 
+ static void
+ check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
+ {
+   use_optype uses;
+   vuse_optype vuses;
+   v_may_def_optype v_may_defs;
+   stmt_ann_t ann;
+   unsigned i;
+ 
+   get_stmt_operands (stmt);
+   ann = stmt_ann (stmt);
+ 
+   uses = USE_OPS (ann);
+   for (i = 0; i < NUM_USES (uses); i++)
+     check_loop_closed_ssa_use (bb, USE_OP (uses, i));
+ 
+   vuses = VUSE_OPS (ann);
+   for (i = 0; i < NUM_VUSES (vuses); i++)
+     check_loop_closed_ssa_use (bb, VUSE_OP (vuses, i));
+ 
+   v_may_defs = V_MAY_DEF_OPS (ann);
+   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
+     check_loop_closed_ssa_use (bb, V_MAY_DEF_OP (v_may_defs, i));
+ }
+ 
+ /* Checks that invariants of the loop closed ssa form are preserved.  */
+ 
+ void
+ verify_loop_closed_ssa (void)
+ {
+   basic_block bb;
+   block_stmt_iterator bsi;
+   tree phi;
+   unsigned i;
+ 
+   verify_ssa ();
+ 
+   FOR_EACH_BB (bb)
+     {
+       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ 	for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
+ 	  check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
+ 				     PHI_ARG_DEF (phi, i));
+ 
+       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ 	check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
+     }
+ }
Index: tree-ssa-loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop.c,v
retrieving revision 2.7
diff -c -3 -p -r2.7 tree-ssa-loop.c
*** tree-ssa-loop.c	30 Jun 2004 21:28:59 -0000	2.7
--- tree-ssa-loop.c	30 Jun 2004 21:40:03 -0000
*************** tree_loop_optimizer_init (FILE *dump)
*** 60,65 ****
--- 60,70 ----
    rewrite_into_ssa (false);
    bitmap_clear (vars_to_rename);
  
+   rewrite_into_loop_closed_ssa ();
+ #ifdef ENABLE_CHECKING
+   verify_loop_closed_ssa ();
+ #endif
+ 
    return loops;
  }
  
*************** struct tree_opt_pass pass_loop_done = 
*** 140,143 ****
    0,					/* todo_flags_start */
    0					/* todo_flags_finish */
  };
- 
--- 145,147 ----