This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[lno] Enable unrolling/peeling/unswitching of arbitrary loops


Hello,

this patch lifts the restriction tree level loop duplication passes had,
i.e. that the processed loops must have just a single exit block.  The
reason for this restriction was that if a variable was used outside of
the loop and the loop has multiple exits, then after unrolling we would
have to update ssa form in a nontrivial way (and using rewrite_into_ssa
was not an option, since we would have to do it once per loop, which
would lead to a quadratic behavior).

This patch removes this restriction by noting that we can remove the
source of the problems -- variables used outside of loops.  I call this
property (i.e. that no ssa name is used outside of the loop it is
defined in) "loop closed ssa form" -- does not someone know some "standard"
name for it, if any?

The other advantage is that all uses of a single induction variable
defining ssa name have now the same meaning; consider

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

Without the loop closed ssa form, the first use of k does not behave
like an induction variable from the point of view of the outer loop,
while the second is an induction variable with base 99 and step 1;
with loop closed ssa form, these are uses of different ssa names.

The slight drawback is that you of course need to preserve the form if
you want to use the advantages.  Most of the time it is trivial, if it
really becomes a problem (I guess during optimizations like loop
interchange etc. it could), you can always call
rewrite_into_loop_closed_ssa again after you are done with them.

Zdenek

Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.104
diff -c -3 -p -r1.1.2.104 ChangeLog.lno
*** ChangeLog.lno	25 Mar 2004 15:15:34 -0000	1.1.2.104
--- ChangeLog.lno	27 Mar 2004 18:26:22 -0000
***************
*** 1,3 ****
--- 1,56 ----
+ 2004-03-27  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>
+ 
+ 	* cfghooks.c (split_edge): Update IRREDUCIBLE_LOOP flags.
+ 	* tree-flow-inline.h (bsi_after_labels): New.
+ 	* tree-flow.h (struct ssa_name_ann_d): Add need_phi_state field.
+ 	(bsi_after_labels, rewrite_ssa_into_ssa, duplicate_ssa_name,
+ 	tree_ssa_dce_no_cfg_changes, rewrite_into_loop_closed_ssa,
+ 	verify_loop_closed_ssa, compute_phi_arg_on_exit): Declare.
+ 	(tree_loop_optimizer_init): Declaration changed.
+ 	* tree-into-ssa.c (struct mark_def_sites_global_data): Add
+ 	names_to_rename and ssa_names fields.
+ 	(insert_phi_nodes, get_value_for, set_value_for, set_def_block,
+ 	set_livein_block, insert_phi_nodes_1, insert_phi_nodes_for,
+ 	register_new_def, get_reaching_def, rewrite_into_ssa): Handle
+ 	rewriting of ssa names.
+ 	(get_phi_state, set_phi_state, ssa_mark_def_sites_initialize_block,
+ 	ssa_mark_phi_uses, ssa_mark_def_sites, duplicate_ssa_name,
+ 	ssa_rewrite_initialize_block, ssa_rewrite_phi_arguments,
+ 	ssa_rewrite_finalize_block, ssa_rewrite_stmt, rewrite_ssa_into_ssa):
+ 	New functions.
+ 	* tree-scalar-evolution.c (scev_initialize): Changed due to
+ 	tree_loop_optimizer_init change.
+ 	* tree-ssa-dce.c (perform_tree_ssa_dce, perform_tree_ssa_dce,
+ 	tree_ssa_cd_dce): Handle no cfg changes mode.
+ 	(tree_ssa_dce_no_cfg_changes): Resurrect.
+ 	* tree-ssa-loop-im.c (move_computations): Preserve loop closed ssa.
+ 	* tree-ssa-loop-ivopts.c (struct version_info): Field outermost_usage
+ 	removed.
+ 	(update_outermost_usage, find_outermost_usage): Removed.
+ 	(ip_normal_pos): Fix.
+ 	(tree_ssa_iv_optimize_init): Do not call find_outermost_usage.
+ 	(find_interesting_uses_stmt): Use loop closed ssa form.
+ 	(find_interesting_uses_outside): New.
+ 	(find_interesting_uses): Use it.
+ 	(determine_iv_cost): Prefer IP_NORMAL to IP_END.
+ 	(split_loop_exit_edge, protect_loop_closed_ssa_form_use,
+ 	protect_loop_closed_ssa_form, compute_phi_arg_on_exit): New functions.
+ 	(rewrite_use_outer): Preserve loop closed ssa form.
+ 	(tree_ssa_iv_optimize): Verify loop closed ssa form.
+ 	* tree-ssa-loop-manip.c (mfb_redirect_exit_edges): Removed.
+ 	(free_new_names): Free old ssa names.
+ 	(extend_exit_phi_nodes, add_exit_phis_edge,
+ 	add_exit_phis_use, add_exit_phis_stmt, add_exit_phis,
+ 	get_loops_exits, rewrite_into_loop_closed_ssa,
+ 	check_loop_closed_ssa_use, check_loop_closed_ssa_stmt,
+ 	verify_loop_closed_ssa): New functions.
+ 	(tree_duplicate_loop_to_header_edge): Use loop closed ssa form.
+ 	(tree_ssa_loop_version): Handle irreducible loops correctly.
+ 	* tree-ssa-loop.c (tree_loop_optimizer_init): Create loop closed ssa
+ 	form.
+ 	(tree_ssa_loop_opt, copy_loop_headers): Changed due to
+ 	tree_loop_optimizer_init change.
+ 
  2004-03-25  Sebastian Pop  <sebastian.pop@ensmp.fr>
  
  	* tree-data-ref.c (subscript_dependence_tester): Removed.
Index: cfghooks.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfghooks.c,v
retrieving revision 1.1.2.4.2.6
diff -c -3 -p -r1.1.2.4.2.6 cfghooks.c
*** cfghooks.c	21 Mar 2004 03:19:43 -0000	1.1.2.4.2.6
--- cfghooks.c	27 Mar 2004 18:26:29 -0000
*************** split_edge (edge e)
*** 398,403 ****
--- 398,404 ----
    gcov_type count = e->count;
    int freq = EDGE_FREQUENCY (e);
    edge f;
+   bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
  
    if (!cfg_hooks->split_edge)
      internal_error ("%s does not support split_edge.", cfg_hooks->name);
*************** split_edge (edge e)
*** 439,444 ****
--- 440,452 ----
  	    set_immediate_dominator (CDI_DOMINATORS, ret->succ->dest, ret);
  	}
      };
+ 
+   if (irr)
+     {
+       ret->flags |= BB_IRREDUCIBLE_LOOP;
+       ret->pred->flags |= EDGE_IRREDUCIBLE_LOOP;
+       ret->succ->flags |= EDGE_IRREDUCIBLE_LOOP;
+     }
  
    return ret;
  }
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow-inline.h,v
retrieving revision 1.1.2.64.2.6
diff -c -3 -p -r1.1.2.64.2.6 tree-flow-inline.h
*** tree-flow-inline.h	23 Mar 2004 08:32:21 -0000	1.1.2.64.2.6
--- tree-flow-inline.h	27 Mar 2004 18:26:30 -0000
*************** bsi_start (basic_block bb)
*** 530,535 ****
--- 530,579 ----
  }
  
  static inline block_stmt_iterator
+ bsi_after_labels (basic_block bb)
+ {
+   block_stmt_iterator bsi;
+   tree_stmt_iterator next;
+ 
+   bsi.bb = bb;
+ 
+   if (!bb->stmt_list)
+     {
+ #ifdef ENABLE_CHECKING
+       if (bb->index >= 0)
+ 	abort ();
+ #endif
+       bsi.tsi.ptr = NULL;
+       bsi.tsi.container = NULL;
+       return bsi;
+     }
+ 
+   bsi.tsi = tsi_start (bb->stmt_list);
+   if (tsi_end_p (bsi.tsi))
+     return bsi;
+ 
+   /* Ensure that there are some labels.  The rationale is that we want
+      to insert after the bsi that is returned, and these insertions should
+      be placed at the start of the basic block.  This would not work if the
+      first statement was not label; rather fail here than enable the user
+      proceed in wrong way.  */
+   if (TREE_CODE (tsi_stmt (bsi.tsi)) != LABEL_EXPR)
+     abort ();
+ 
+   next = bsi.tsi;
+   tsi_next (&next);
+ 
+   while (!tsi_end_p (next)
+ 	 && TREE_CODE (tsi_stmt (next)) == LABEL_EXPR)
+     {
+       bsi.tsi = next;
+       tsi_next (&next);
+     }
+ 
+   return bsi;
+ }
+ 
+ static inline block_stmt_iterator
  bsi_last (basic_block bb)
  {
    block_stmt_iterator bsi;
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.177.2.20
diff -c -3 -p -r1.1.4.177.2.20 tree-flow.h
*** tree-flow.h	23 Mar 2004 20:13:28 -0000	1.1.4.177.2.20
--- tree-flow.h	27 Mar 2004 18:26:31 -0000
*************** struct ssa_name_ann_d GTY(())
*** 271,276 ****
--- 271,281 ----
    /* Nonzero if the value of this pointer escapes the current function.  */
    unsigned int value_escapes_p : 1;
  
+   /* This field indicates whether or not the variable may need PHI nodes.
+      See the enum's definition for more detailed information about the
+      states.  */
+   ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
+ 
    /* Set of variables that this pointer may point to.  */
    bitmap pt_vars;
  
*************** typedef struct {
*** 411,416 ****
--- 416,422 ----
  
  static inline block_stmt_iterator bsi_start (basic_block);
  static inline block_stmt_iterator bsi_last (basic_block);
+ static inline block_stmt_iterator bsi_after_labels (basic_block);
  static inline bool bsi_end_p (block_stmt_iterator);
  static inline void bsi_next (block_stmt_iterator *);
  static inline void bsi_prev (block_stmt_iterator *);
*************** extern void kill_redundant_phi_nodes (vo
*** 571,576 ****
--- 577,585 ----
  
  /* In tree-into-ssa.c  */
  extern void rewrite_into_ssa (bool);
+ extern void rewrite_ssa_into_ssa (bitmap);
+ 
+ tree duplicate_ssa_name (tree, tree);
  
  extern unsigned int highest_ssa_version;
  
*************** extern void replace_exp (tree *, tree);
*** 591,598 ****
  extern bool cprop_into_stmt (tree, varray_type);
  extern void cprop_into_successor_phis (basic_block, varray_type);
  
  /* In tree-ssa-loop*.c  */
! struct loops *tree_loop_optimizer_init (FILE *);
  void tree_ssa_lim (struct loops *loops);
  void tree_ssa_iv_optimize (struct loops *);
  void canonicalize_induction_variables (struct loops *loops);
--- 600,610 ----
  extern bool cprop_into_stmt (tree, varray_type);
  extern void cprop_into_successor_phis (basic_block, varray_type);
  
+ /* In tree-ssa-dce.c.  */
+ void tree_ssa_dce_no_cfg_changes (void);
+ 
  /* In tree-ssa-loop*.c  */
! struct loops *tree_loop_optimizer_init (FILE *, bool);
  void tree_ssa_lim (struct loops *loops);
  void tree_ssa_iv_optimize (struct loops *);
  void canonicalize_induction_variables (struct loops *loops);
*************** void linear_transform_loops (struct loop
*** 610,615 ****
--- 622,630 ----
  void loop_commit_inserts (void);
  void tree_ssa_unswitch_loops (struct loops *loops);
  unsigned estimate_loop_size (struct loop *loop);
+ void rewrite_into_loop_closed_ssa (void);
+ void verify_loop_closed_ssa (void);
+ void compute_phi_arg_on_exit (edge, tree, tree);
  
  /* In tree-flow-inline.h  */
  static inline int phi_arg_from_edge (tree, edge);
Index: tree-into-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-into-ssa.c,v
retrieving revision 1.1.4.1
diff -c -3 -p -r1.1.4.1 tree-into-ssa.c
*** tree-into-ssa.c	21 Mar 2004 03:20:20 -0000	1.1.4.1
--- tree-into-ssa.c	27 Mar 2004 18:26:32 -0000
*************** struct mark_def_sites_global_data
*** 88,93 ****
--- 88,99 ----
       solely to avoid the overhead of allocating and deallocating
       the bitmap.  */
    sbitmap kills;
+ 
+   /* Bitmap of names to rename.  */
+   bitmap names_to_rename;
+ 
+   /* Array of ssa names.  */
+   tree *ssa_names;
  };
  
  /* Table to store the current reaching definition for every variable in
*************** static void compute_global_livein (bitma
*** 115,121 ****
  static void set_def_block (tree, basic_block);
  static void set_livein_block (tree, basic_block);
  static bool prepare_operand_for_rename (tree *op_p, size_t *uid_p);
! static void insert_phi_nodes (bitmap *);
  static void rewrite_stmt (struct dom_walk_data *, basic_block,
  			  block_stmt_iterator);
  static inline void rewrite_operand (tree *);
--- 121,127 ----
  static void set_def_block (tree, basic_block);
  static void set_livein_block (tree, basic_block);
  static bool prepare_operand_for_rename (tree *op_p, size_t *uid_p);
! static void insert_phi_nodes (bitmap *, bitmap, tree *);
  static void rewrite_stmt (struct dom_walk_data *, basic_block,
  			  block_stmt_iterator);
  static inline void rewrite_operand (tree *);
*************** static inline struct def_blocks_d *get_d
*** 131,142 ****
  static inline struct def_blocks_d *find_def_blocks_for (tree);
  static void htab_statistics (FILE *, htab_t);
  
  /* Return the value associated with variable VAR in TABLE.  */
  
  static inline tree
  get_value_for (tree var, varray_type table)
  {
!   return VARRAY_TREE (table, var_ann (var)->uid);
  }
  
  
--- 137,173 ----
  static inline struct def_blocks_d *find_def_blocks_for (tree);
  static void htab_statistics (FILE *, htab_t);
  
+ /* Gets phi_state field for VAR.  */
+ 
+ static inline enum need_phi_state
+ get_phi_state (tree var)
+ {
+   if (TREE_CODE (var) == SSA_NAME)
+     return get_ssa_name_ann (var)->need_phi_state;
+   else
+     return var_ann (var)->need_phi_state;
+ }
+ 
+ /* Sets phi_state field for VAR to STATE.  */
+ 
+ static inline void
+ set_phi_state (tree var, enum need_phi_state state)
+ {
+   if (TREE_CODE (var) == SSA_NAME)
+     get_ssa_name_ann (var)->need_phi_state = state;
+   else
+     var_ann (var)->need_phi_state = state;
+ }
+ 
  /* Return the value associated with variable VAR in TABLE.  */
  
  static inline tree
  get_value_for (tree var, varray_type table)
  {
!   if (TREE_CODE (var) == SSA_NAME)
!     return VARRAY_TREE (table, SSA_NAME_VERSION (var));
!   else
!     return VARRAY_TREE (table, var_ann (var)->uid);
  }
  
  
*************** get_value_for (tree var, varray_type tab
*** 145,151 ****
  static inline void
  set_value_for (tree var, tree value, varray_type table)
  {
!   VARRAY_TREE (table, var_ann (var)->uid) = value;
  }
  
  
--- 176,185 ----
  static inline void
  set_value_for (tree var, tree value, varray_type table)
  {
!   if (TREE_CODE (var) == SSA_NAME)
!     VARRAY_TREE (table, SSA_NAME_VERSION (var)) = value;
!   else
!     VARRAY_TREE (table, var_ann (var)->uid) = value;
  }
  
  
*************** mark_def_sites_initialize_block (struct 
*** 214,219 ****
--- 248,313 ----
    sbitmap_zero (kills);
  }
  
+ /* Block initialization routine for mark_def_sites.  Clear the 
+    KILLS bitmap at the start of each block.  */
+ 
+ static void
+ ssa_mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
+ 				     basic_block bb)
+ {
+   struct mark_def_sites_global_data *gd = walk_data->global_data;
+   sbitmap kills = gd->kills;
+   tree phi, def;
+   unsigned def_uid;
+ 
+   sbitmap_zero (kills);
+ 
+   for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+     {
+       def = PHI_RESULT (phi);
+       def_uid = SSA_NAME_VERSION (def);
+ 
+       if (!bitmap_bit_p (gd->names_to_rename, def_uid))
+ 	continue;
+ 
+       gd->ssa_names[def_uid] = def;
+ 
+       set_def_block (def, bb);
+       if (is_gimple_reg (def))
+ 	SET_BIT (kills, def_uid);
+     }
+ }
+ 
+ /* Marks ssa names used as arguments of phis at the end of BB.  */
+ 
+ static void
+ ssa_mark_phi_uses (struct dom_walk_data *walk_data, basic_block bb)
+ {
+   struct mark_def_sites_global_data *gd = walk_data->global_data;
+   sbitmap kills = gd->kills;
+   edge e;
+   tree phi, use;
+   unsigned uid;
+ 
+   for (e = bb->succ; e; e = e->succ_next)
+     {
+       if (e->dest == EXIT_BLOCK_PTR)
+ 	continue;
+ 
+       for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
+ 	{
+ 	  use = phi_element_for_edge (phi, e)->def;
+ 	  if (TREE_CODE (use) != SSA_NAME)
+ 	    continue;
+ 
+ 	  uid = SSA_NAME_VERSION (use);
+ 
+ 	  if (bitmap_bit_p (gd->names_to_rename, uid)
+ 	      && !TEST_BIT (kills, uid))
+ 	    set_livein_block (use, bb);
+ 	}
+     }
+ }
  
  /* Call back for walk_dominator_tree used to collect definition sites
     for every variable in the function.  For every statement S in block
*************** mark_def_sites (struct dom_walk_data *wa
*** 310,315 ****
--- 404,498 ----
      }
  }
  
+ /* Ditto, but works over ssa names.  */
+ 
+ static void
+ ssa_mark_def_sites (struct dom_walk_data *walk_data,
+ 		    basic_block bb,
+ 		    block_stmt_iterator bsi)
+ {
+   struct mark_def_sites_global_data *gd = walk_data->global_data;
+   sbitmap kills = gd->kills;
+   vdef_optype vdefs;
+   vuse_optype vuses;
+   def_optype defs;
+   use_optype uses;
+   size_t i, uid, def_uid;
+   tree stmt, use, def;
+   stmt_ann_t ann;
+ 
+   /* Mark all the blocks that have definitions for each variable in the
+      names_to_rename bitmap.  */
+   stmt = bsi_stmt (bsi);
+   get_stmt_operands (stmt);
+   ann = stmt_ann (stmt);
+ 
+   /* If a variable is used before being set, then the variable is live
+      across a block boundary, so mark it live-on-entry to BB.  */
+   uses = USE_OPS (ann);
+   for (i = 0; i < NUM_USES (uses); i++)
+     {
+       use = USE_OP (uses, i);
+       uid = SSA_NAME_VERSION (use);
+ 
+       if (bitmap_bit_p (gd->names_to_rename, uid)
+ 	  && !TEST_BIT (kills, uid))
+ 	set_livein_block (use, bb);
+     }
+ 	  
+   /* Similarly for virtual uses.  */
+   vuses = VUSE_OPS (ann);
+   for (i = 0; i < NUM_VUSES (vuses); i++)
+     {
+       use = VUSE_OP (vuses, i);
+       uid = SSA_NAME_VERSION (use);
+ 
+       if (bitmap_bit_p (gd->names_to_rename, uid)
+ 	  && !TEST_BIT (kills, uid))
+ 	set_livein_block (use, bb);
+     }
+ 
+   /* Note that virtual definitions are irrelevant for computing KILLS
+      because a VDEF does not constitute a killing definition of the
+      variable.  However, the operand of a virtual definitions is a use
+      of the variable, so it may cause the variable to be considered
+      live-on-entry.  */
+   vdefs = VDEF_OPS (ann);
+   for (i = 0; i < NUM_VDEFS (vdefs); i++)
+     {
+       def = VDEF_RESULT (vdefs, i);
+       def_uid = SSA_NAME_VERSION (def);
+ 
+       use = VDEF_OP (vdefs, i);
+       uid = SSA_NAME_VERSION (use);
+ 
+       if (bitmap_bit_p (gd->names_to_rename, uid)
+ 	  && !TEST_BIT (kills, uid))
+ 	set_livein_block (use, bb);
+ 
+       if (bitmap_bit_p (gd->names_to_rename, def_uid))
+ 	{
+ 	  gd->ssa_names[def_uid] = def;
+ 	  set_def_block (def, bb);
+ 	}
+     }
+ 
+   /* Now process the definition made by this statement.  Mark the
+      variables in KILLS.  */
+   defs = DEF_OPS (ann);
+   for (i = 0; i < NUM_DEFS (defs); i++)
+     {
+       def = DEF_OP (defs, i);
+       def_uid = SSA_NAME_VERSION (def);
+ 
+       if (bitmap_bit_p (gd->names_to_rename, def_uid))
+ 	{
+ 	  gd->ssa_names[def_uid] = def;
+ 	  set_def_block (def, bb);
+ 	  SET_BIT (kills, def_uid);
+ 	}
+     }
+ }
  
  /* Mark block BB as the definition site for variable VAR.  */
  
*************** static void
*** 317,323 ****
  set_def_block (tree var, basic_block bb)
  {
    struct def_blocks_d *db_p;
!   enum need_phi_state state = var_ann (var)->need_phi_state;
  
    db_p = get_def_blocks_for (var);
  
--- 500,506 ----
  set_def_block (tree var, basic_block bb)
  {
    struct def_blocks_d *db_p;
!   enum need_phi_state state = get_phi_state (var);
  
    db_p = get_def_blocks_for (var);
  
*************** set_def_block (tree var, basic_block bb)
*** 337,345 ****
       definition(s).  In this case we may need a PHI node, so enter
       state NEED_PHI_STATE_MAYBE.  */
    if (state == NEED_PHI_STATE_UNKNOWN)
!     var_ann (var)->need_phi_state = NEED_PHI_STATE_NO;
    else
!     var_ann (var)->need_phi_state = NEED_PHI_STATE_MAYBE;
  }
  
  
--- 520,528 ----
       definition(s).  In this case we may need a PHI node, so enter
       state NEED_PHI_STATE_MAYBE.  */
    if (state == NEED_PHI_STATE_UNKNOWN)
!     set_phi_state (var, NEED_PHI_STATE_NO);
    else
!     set_phi_state (var, NEED_PHI_STATE_MAYBE);
  }
  
  
*************** static void
*** 349,355 ****
  set_livein_block (tree var, basic_block bb)
  {
    struct def_blocks_d *db_p;
!   enum need_phi_state state = var_ann (var)->need_phi_state;
  
    db_p = get_def_blocks_for (var);
  
--- 532,538 ----
  set_livein_block (tree var, basic_block bb)
  {
    struct def_blocks_d *db_p;
!   enum need_phi_state state = get_phi_state (var);
  
    db_p = get_def_blocks_for (var);
  
*************** set_livein_block (tree var, basic_block 
*** 369,378 ****
        if (def_block_index == -1
  	  || ! dominated_by_p (CDI_DOMINATORS, bb,
  	                       BASIC_BLOCK (def_block_index)))
! 	var_ann (var)->need_phi_state = NEED_PHI_STATE_MAYBE;
      }
    else
!     var_ann (var)->need_phi_state = NEED_PHI_STATE_MAYBE;
  }
  
  
--- 552,561 ----
        if (def_block_index == -1
  	  || ! dominated_by_p (CDI_DOMINATORS, bb,
  	                       BASIC_BLOCK (def_block_index)))
! 	set_phi_state (var, NEED_PHI_STATE_MAYBE);
      }
    else
!     set_phi_state (var, NEED_PHI_STATE_MAYBE);
  }
  
  
*************** prepare_operand_for_rename (tree *op_p, 
*** 410,430 ****
  static inline
  void insert_phi_nodes_1 (tree var, bitmap *dfs)
  {
!   var_ann_t ann = var_ann (var);
!   if (ann->need_phi_state != NEED_PHI_STATE_NO)
      insert_phi_nodes_for (var, dfs);
  }
  
- 
  /* Insert PHI nodes at the dominance frontier of blocks with variable
     definitions.  DFS contains the dominance frontier information for
     the flowgraph.  PHI nodes will only be inserted at the dominance
     frontier of definition blocks for variables whose NEED_PHI_STATE
     annotation is marked as ``maybe'' or ``unknown'' (computed by
!    mark_def_sites).  */
  
  static void
! insert_phi_nodes (bitmap *dfs)
  {
    size_t i;
  
--- 593,612 ----
  static inline
  void insert_phi_nodes_1 (tree var, bitmap *dfs)
  {
!   if (get_phi_state (var) != NEED_PHI_STATE_NO)
      insert_phi_nodes_for (var, dfs);
  }
  
  /* Insert PHI nodes at the dominance frontier of blocks with variable
     definitions.  DFS contains the dominance frontier information for
     the flowgraph.  PHI nodes will only be inserted at the dominance
     frontier of definition blocks for variables whose NEED_PHI_STATE
     annotation is marked as ``maybe'' or ``unknown'' (computed by
!    mark_def_sites).  If NAMES_TO_RENAME is not NULL, do the same but
!    for ssa name rewriting.  SSA_NAMES then maps versions to ssa names.  */
  
  static void
! insert_phi_nodes (bitmap *dfs, bitmap names_to_rename, tree *ssa_names)
  {
    size_t i;
  
*************** insert_phi_nodes (bitmap *dfs)
*** 434,440 ****
       to the work list all the blocks that have a definition for the
       variable.  PHI nodes will be added to the dominance frontier blocks of
       each definition block.  */
!   if (vars_to_rename)
      EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i,
  	insert_phi_nodes_1 (referenced_var (i), dfs));
    else
--- 616,630 ----
       to the work list all the blocks that have a definition for the
       variable.  PHI nodes will be added to the dominance frontier blocks of
       each definition block.  */
!   if (names_to_rename)
!     {
!       EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i,
! 	{
! 	  if (ssa_names[i])
! 	    insert_phi_nodes_1 (ssa_names[i], dfs);
! 	});
!     }
!   else if (vars_to_rename)
      EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i,
  	insert_phi_nodes_1 (referenced_var (i), dfs));
    else
*************** rewrite_initialize_block (struct dom_wal
*** 519,524 ****
--- 709,764 ----
      }
  }
  
+ /* Creates a duplicate of a ssa name NAME defined in statement STMT.  */
+ 
+ tree
+ duplicate_ssa_name (tree name, tree stmt)
+ {
+   tree new_name = make_ssa_name (SSA_NAME_VAR (name), stmt);
+   ssa_name_ann_t old_ann = get_ssa_name_ann (name);
+   ssa_name_ann_t ann = get_ssa_name_ann (new_name);
+ 
+   *ann = *old_ann;
+   if (old_ann->pt_vars)
+     {
+       ann->pt_vars = BITMAP_GGC_ALLOC ();
+       bitmap_copy (ann->pt_vars, old_ann->pt_vars);
+     }
+ 
+   return new_name;
+ }
+ 
+ /* Ditto, for rewriting ssa names.  */
+ 
+ static void
+ ssa_rewrite_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
+ {
+   tree phi, new_name;
+   struct rewrite_block_data *bd
+     = (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
+   bitmap names_to_rename = walk_data->global_data;
+ 
+   if (dump_file && (dump_flags & TDF_DETAILS))
+     fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
+ 
+   /* Step 1.  Register new definitions for every PHI node in the block.
+      Conceptually, all the PHI nodes are executed in parallel and each PHI
+      node introduces a new version for the associated variable.  */
+   for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+     {
+       tree result = PHI_RESULT (phi);
+ 
+       if (bitmap_bit_p (names_to_rename, SSA_NAME_VERSION (result)))
+ 	{
+ 	  new_name = duplicate_ssa_name (result, phi);
+ 	  PHI_RESULT (phi) = new_name;
+ 	}
+       else
+ 	new_name = result;
+ 
+       register_new_def (result, new_name, &bd->block_defs, currdefs);
+     }
+ }
  
  /* SSA Rewriting Step 3.  Visit all the successor blocks of BB looking for
     PHI nodes.  For every PHI node found, add a new argument containing the
*************** rewrite_add_phi_arguments (struct dom_wa
*** 551,556 ****
--- 791,826 ----
      }
  }
  
+ /* Ditto, for ssa name rewriting.  */
+ 
+ static void
+ ssa_rewrite_phi_arguments (struct dom_walk_data *walk_data, basic_block bb)
+ {
+   edge e;
+   bitmap names_to_rename = walk_data->global_data;
+   tree *op;
+ 
+   for (e = bb->succ; e; e = e->succ_next)
+     {
+       tree phi;
+ 
+       if (e->dest == EXIT_BLOCK_PTR)
+ 	continue;
+ 
+       for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
+ 	{
+ 	  op = &phi_element_for_edge (phi, e)->def;
+ 	  if (TREE_CODE (*op) != SSA_NAME)
+ 	    continue;
+ 
+ 	  if (!bitmap_bit_p (names_to_rename, SSA_NAME_VERSION (*op)))
+ 	    continue;
+ 
+ 	  *op = get_reaching_def (*op);
+ 	}
+     }
+ }
+ 
  /* SSA Rewriting Step 5.  Restore the current reaching definition for each
     variable referenced in the block (in reverse order).  */
  
*************** rewrite_finalize_block (struct dom_walk_
*** 583,588 ****
--- 853,881 ----
      }
  }
  
+ /* Ditto, for rewriting ssa names.  */
+ 
+ static void
+ ssa_rewrite_finalize_block (struct dom_walk_data *walk_data,
+ 			    basic_block bb ATTRIBUTE_UNUSED)
+ {
+   struct rewrite_block_data *bd
+     = (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
+ 
+   /* Step 5.  Restore the current reaching definition for each variable
+      referenced in the block (in reverse order).  */
+   while (bd->block_defs && VARRAY_ACTIVE_SIZE (bd->block_defs) > 0)
+     {
+       tree var;
+       tree saved_def = VARRAY_TOP_TREE (bd->block_defs);
+       VARRAY_POP (bd->block_defs);
+       
+       var = VARRAY_TOP_TREE (bd->block_defs);
+       VARRAY_POP (bd->block_defs);
+ 
+       set_value_for (var, saved_def, currdefs);
+     }
+ }
  
  /* Dump SSA information to FILE.  */
  
*************** insert_phi_nodes_for (tree var, bitmap *
*** 659,664 ****
--- 952,960 ----
    bitmap phi_insertion_points;
    int bb_index;
    varray_type work_stack;
+   edge e;
+   tree phi;
+   basic_block bb;
  
    def_map = find_def_blocks_for (var);
    if (def_map == NULL)
*************** insert_phi_nodes_for (tree var, bitmap *
*** 689,698 ****
       We now always use fully pruned SSA form.  */
    while (VARRAY_ACTIVE_SIZE (work_stack) > 0)
      {
-       basic_block bb = VARRAY_TOP_BB (work_stack);
-       int bb_index = bb->index;
        int dfs_index;
  
        VARRAY_POP (work_stack);
        
        EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index],
--- 985,995 ----
       We now always use fully pruned SSA form.  */
    while (VARRAY_ACTIVE_SIZE (work_stack) > 0)
      {
        int dfs_index;
  
+       bb = VARRAY_TOP_BB (work_stack);
+       bb_index = bb->index;
+ 
        VARRAY_POP (work_stack);
        
        EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index],
*************** insert_phi_nodes_for (tree var, bitmap *
*** 713,721 ****
    /* And insert the PHI nodes.  */
    EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points, def_map->livein_blocks,
  			    0, bb_index,
!     {
!       create_phi_node (var, BASIC_BLOCK (bb_index));
!     });
  
    BITMAP_FREE (phi_insertion_points);
  }
--- 1010,1040 ----
    /* And insert the PHI nodes.  */
    EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points, def_map->livein_blocks,
  			    0, bb_index,
!     do
!       {
! 	bb = BASIC_BLOCK (bb_index);
! 
! 	/* If there already is a phi node for var, do nothing.  */
! 	if (TREE_CODE (var) == SSA_NAME)
! 	  {
! 	    for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
! 	      if (PHI_RESULT (phi) == var)
! 		break;
! 
! 	    if (phi)
! 	      break;
! 	  }
! 
! 	phi = create_phi_node (var, bb);
! 
! 	/* If we are rewriting ssa names, add also the phi arguments.  */
! 	if (TREE_CODE (var) == SSA_NAME)
! 	  {
! 	    for (e = bb->pred; e; e = e->pred_next)
! 	      add_phi_arg (&phi, var, e);
! 	  }
!       }
!     while (0));
  
    BITMAP_FREE (phi_insertion_points);
  }
*************** rewrite_stmt (struct dom_walk_data *walk
*** 800,805 ****
--- 1119,1211 ----
      }
  }
  
+ /* Ditto, for rewriting ssa names.  */
+ 
+ static void
+ ssa_rewrite_stmt (struct dom_walk_data *walk_data,
+ 		  basic_block bb ATTRIBUTE_UNUSED,
+ 		  block_stmt_iterator si)
+ {
+   size_t i;
+   stmt_ann_t ann;
+   tree stmt, var, *use_p;
+   vuse_optype vuses;
+   vdef_optype vdefs;
+   def_optype defs;
+   use_optype uses;
+   struct rewrite_block_data *bd;
+   bitmap names_to_rename = walk_data->global_data;
+ 
+   bd = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
+ 
+   stmt = bsi_stmt (si);
+   ann = stmt_ann (stmt);
+ 
+   if (dump_file && (dump_flags & TDF_DETAILS))
+     {
+       fprintf (dump_file, "Renaming statement ");
+       print_generic_stmt (dump_file, stmt, TDF_SLIM);
+       fprintf (dump_file, "\n");
+     }
+ 
+ #if defined ENABLE_CHECKING
+   /* We have just scanned the code for operands.  No statement should
+      be modified.  */
+   if (ann->modified)
+     abort ();
+ #endif
+ 
+   defs = DEF_OPS (ann);
+   uses = USE_OPS (ann);
+   vuses = VUSE_OPS (ann);
+   vdefs = VDEF_OPS (ann);
+ 
+   /* Step 1.  Rewrite USES and VUSES in the statement.  */
+   for (i = 0; i < NUM_USES (uses); i++)
+     {
+       use_p = USE_OP_PTR (uses, i);
+       if (bitmap_bit_p (names_to_rename, SSA_NAME_VERSION (*use_p)))
+ 	*use_p = get_reaching_def (*use_p);
+     }
+ 
+   /* Rewrite virtual uses in the statement.  */
+   for (i = 0; i < NUM_VUSES (vuses); i++)
+     {
+       use_p = VUSE_OP_PTR (vuses, i);
+       if (bitmap_bit_p (names_to_rename, SSA_NAME_VERSION (*use_p)))
+ 	*use_p = get_reaching_def (*use_p);
+     }
+ 
+   /* Step 2.  Register the statement's DEF and VDEF operands.  */
+   for (i = 0; i < NUM_DEFS (defs); i++)
+     {
+       tree *def_p = DEF_OP_PTR (defs, i);
+       var = *def_p;
+ 
+       if (!bitmap_bit_p (names_to_rename, SSA_NAME_VERSION (*def_p)))
+ 	continue;
+ 
+       *def_p = duplicate_ssa_name (var, stmt);
+       register_new_def (var, *def_p, &bd->block_defs, currdefs);
+     }
+ 
+   /* Register new virtual definitions made by the statement.  */
+   for (i = 0; i < NUM_VDEFS (vdefs); i++)
+     {
+       tree *def_p = VDEF_RESULT_PTR (vdefs, i);
+       var = *def_p;
+ 
+       use_p = VDEF_OP_PTR (vdefs, i);
+       if (bitmap_bit_p (names_to_rename, SSA_NAME_VERSION (*use_p)))
+ 	*use_p = get_reaching_def (*use_p);
+ 
+       if (!bitmap_bit_p (names_to_rename, SSA_NAME_VERSION (*def_p)))
+ 	continue;
+ 
+       *def_p = duplicate_ssa_name (var, stmt);
+       register_new_def (var, *def_p, &bd->block_defs, currdefs);
+     }
+ }
  
  /* Replace the operand pointed by OP_P with its immediate reaching
     definition.  */
*************** rewrite_operand (tree *op_p)
*** 811,817 ****
      *op_p = get_reaching_def (*op_p);
  }
  
- 
  /* Register DEF to be a new definition for variable VAR and push VAR's
     current reaching definition into the stack pointed by BLOCK_DEFS_P.
     IS_REAL_OPERAND is true when DEF is a real definition.  */
--- 1217,1222 ----
*************** register_new_def (tree var, tree def,
*** 828,834 ****
    /* If the current reaching definition is NULL, push the variable itself
       so that the dominator tree callbacks know what variable is associated
       with this NULL reaching def when unwinding the *BLOCK_DEFS_P stack.  */
!   if (currdef == NULL_TREE)
      VARRAY_PUSH_TREE (*block_defs_p, var);
  
    /* Push the current reaching definition into *BLOCK_DEFS_P.  This stack is
--- 1233,1240 ----
    /* If the current reaching definition is NULL, push the variable itself
       so that the dominator tree callbacks know what variable is associated
       with this NULL reaching def when unwinding the *BLOCK_DEFS_P stack.  */
!   if (currdef == NULL_TREE
!       || TREE_CODE (var) == SSA_NAME)
      VARRAY_PUSH_TREE (*block_defs_p, var);
  
    /* Push the current reaching definition into *BLOCK_DEFS_P.  This stack is
*************** register_new_def (tree var, tree def,
*** 851,857 ****
  static tree
  get_reaching_def (tree var)
  {
!   tree default_d, currdef_var;
    
    /* Lookup the current reaching definition for VAR.  */
    default_d = NULL_TREE;
--- 1257,1263 ----
  static tree
  get_reaching_def (tree var)
  {
!   tree default_d, currdef_var, avar;
    
    /* Lookup the current reaching definition for VAR.  */
    default_d = NULL_TREE;
*************** get_reaching_def (tree var)
*** 861,871 ****
       default definition for it (if needed).  */
    if (currdef_var == NULL_TREE)
      {
!       default_d = default_def (var);
        if (default_d == NULL_TREE)
  	{
! 	  default_d = make_ssa_name (var, build_empty_stmt ());
! 	  set_default_def (var, default_d);
  	}
        set_value_for (var, default_d, currdefs);
      }
--- 1267,1282 ----
       default definition for it (if needed).  */
    if (currdef_var == NULL_TREE)
      {
!       if (TREE_CODE (var) == SSA_NAME)
! 	avar = SSA_NAME_VAR (var);
!       else
! 	avar = var;
! 
!       default_d = default_def (avar);
        if (default_d == NULL_TREE)
  	{
! 	  default_d = make_ssa_name (avar, build_empty_stmt ());
! 	  set_default_def (avar, default_d);
  	}
        set_value_for (var, default_d, currdefs);
      }
*************** rewrite_into_ssa (bool all)
*** 1118,1124 ****
    sbitmap_free (mark_def_sites_global_data.kills);
  
    /* Insert PHI nodes at dominance frontiers of definition blocks.  */
!   insert_phi_nodes (dfs);
  
    /* Rewrite all the basic blocks in the program.  */
    timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
--- 1529,1535 ----
    sbitmap_free (mark_def_sites_global_data.kills);
  
    /* Insert PHI nodes at dominance frontiers of definition blocks.  */
!   insert_phi_nodes (dfs, NULL, NULL);
  
    /* Rewrite all the basic blocks in the program.  */
    timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
*************** rewrite_into_ssa (bool all)
*** 1164,1169 ****
--- 1575,1712 ----
    VARRAY_CLEAR (currdefs);
  
    vars_to_rename = old_vars_to_rename;
+   timevar_pop (TV_TREE_SSA_OTHER);
+ }
+ 
+ /* The ssa names in NAMES_TO_RENAME may have more than one definition;
+    add phi nodes and rewrite them to fix this.  */
+ 
+ void
+ rewrite_ssa_into_ssa (bitmap names_to_rename)
+ {
+   bitmap *dfs;
+   basic_block bb;
+   struct dom_walk_data walk_data;
+   struct mark_def_sites_global_data mark_def_sites_global_data;
+   tree *ssa_names;
+   
+   if (bitmap_first_set_bit (names_to_rename) < 0)
+     return;
+ 
+   timevar_push (TV_TREE_SSA_OTHER);
+ 
+   /* Allocate memory for the DEF_BLOCKS hash table.  */
+   def_blocks = htab_create (highest_ssa_version,
+ 			    def_blocks_hash, def_blocks_eq, def_blocks_free);
+ 
+   VARRAY_TREE_INIT (currdefs, highest_ssa_version, "currdefs");
+ 
+   ssa_names = xcalloc (highest_ssa_version, sizeof (tree));
+ 
+   /* Initialize dominance frontier and immediate dominator bitmaps. 
+      Also count the number of predecessors for each block.  Doing so
+      can save significant time during PHI insertion for large graphs.  */
+   dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
+   FOR_EACH_BB (bb)
+     {
+       edge e;
+       int count = 0;
+ 
+       for (e = bb->pred; e; e = e->pred_next)
+ 	count++;
+ 
+       bb_ann (bb)->num_preds = count;
+       dfs[bb->index] = BITMAP_XMALLOC ();
+     }
+ 
+   /* Ensure that the dominance information is OK.  */
+   calculate_dominance_info (CDI_DOMINATORS);
+ 
+   /* Compute dominance frontiers.  */
+   compute_dominance_frontiers (dfs);
+ 
+   /* Setup callbacks for the generic dominator tree walker to find and
+      mark definition sites.  */
+   walk_data.walk_stmts_backward = false;
+   walk_data.dom_direction = CDI_DOMINATORS;
+   walk_data.initialize_block_local_data = NULL;
+   walk_data.before_dom_children_before_stmts
+ 	  = ssa_mark_def_sites_initialize_block;
+   walk_data.before_dom_children_walk_stmts = ssa_mark_def_sites;
+   walk_data.before_dom_children_after_stmts = ssa_mark_phi_uses; 
+   walk_data.after_dom_children_before_stmts =  NULL;
+   walk_data.after_dom_children_walk_stmts =  NULL;
+   walk_data.after_dom_children_after_stmts =  NULL;
+ 
+   mark_def_sites_global_data.kills = sbitmap_alloc (highest_ssa_version);
+   mark_def_sites_global_data.names_to_rename = names_to_rename;
+   mark_def_sites_global_data.ssa_names = ssa_names;
+   walk_data.global_data = &mark_def_sites_global_data;
+ 
+   /* We do not have any local data.  */
+   walk_data.block_local_data_size = 0;
+ 
+   /* Initialize the dominator walker.  */
+   init_walk_dominator_tree (&walk_data);
+ 
+   /* Recursively walk the dominator tree.  */
+   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
+ 
+   /* Finalize the dominator walker.  */
+   fini_walk_dominator_tree (&walk_data);
+ 
+   /* We no longer need this bitmap, clear and free it.  */
+   sbitmap_free (mark_def_sites_global_data.kills);
+ 
+   /* Insert PHI nodes at dominance frontiers of definition blocks.  */
+   insert_phi_nodes (dfs, names_to_rename, ssa_names);
+ 
+   /* Rewrite all the basic blocks in the program.  */
+   timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
+ 
+   /* Setup callbacks for the generic dominator tree walker.  */
+   walk_data.walk_stmts_backward = false;
+   walk_data.dom_direction = CDI_DOMINATORS;
+   walk_data.initialize_block_local_data
+ 	  = rewrite_initialize_block_local_data;
+   walk_data.before_dom_children_before_stmts = ssa_rewrite_initialize_block;
+   walk_data.before_dom_children_walk_stmts = ssa_rewrite_stmt;
+   walk_data.before_dom_children_after_stmts = ssa_rewrite_phi_arguments;
+   walk_data.after_dom_children_before_stmts = NULL;
+   walk_data.after_dom_children_walk_stmts =  NULL;
+   walk_data.after_dom_children_after_stmts =  ssa_rewrite_finalize_block;
+   walk_data.global_data = names_to_rename;
+   walk_data.block_local_data_size = sizeof (struct rewrite_block_data);
+ 
+   /* Initialize the dominator walker.  */
+   init_walk_dominator_tree (&walk_data);
+ 
+   /* Recursively walk the dominator tree rewriting each statement in
+      each basic block.  */
+   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
+ 
+   /* Finalize the dominator walker.  */
+   fini_walk_dominator_tree (&walk_data);
+ 
+   timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
+ 
+   /* Debugging dumps.  */
+   if (dump_file && (dump_flags & TDF_STATS))
+     {
+       dump_dfa_stats (dump_file);
+       dump_tree_ssa_stats (dump_file);
+     }
+ 
+   /* Free allocated memory.  */
+   FOR_EACH_BB (bb)
+     BITMAP_XFREE (dfs[bb->index]);
+   free (dfs);
+ 
+   htab_delete (def_blocks);
+   VARRAY_CLEAR (currdefs);
+ 
+   free (ssa_names);
+ 
    timevar_pop (TV_TREE_SSA_OTHER);
  }
  
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.c,v
retrieving revision 1.1.2.24
diff -c -3 -p -r1.1.2.24 tree-scalar-evolution.c
*** tree-scalar-evolution.c	23 Mar 2004 20:13:28 -0000	1.1.2.24
--- tree-scalar-evolution.c	27 Mar 2004 18:26:35 -0000
*************** scev_initialize (struct loops *loops)
*** 3152,3158 ****
  static void
  scev_init (void)
  {
!   current_loops = tree_loop_optimizer_init (NULL);
    if (!current_loops)
      return;
    scev_initialize (current_loops);
--- 3152,3158 ----
  static void
  scev_init (void)
  {
!   current_loops = tree_loop_optimizer_init (NULL, true);
    if (!current_loops)
      return;
    scev_initialize (current_loops);
Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dce.c,v
retrieving revision 1.1.2.72.2.5
diff -c -3 -p -r1.1.2.72.2.5 tree-ssa-dce.c
*** tree-ssa-dce.c	23 Mar 2004 11:28:20 -0000	1.1.2.72.2.5
--- tree-ssa-dce.c	27 Mar 2004 18:26:36 -0000
*************** tree_dce_done (bool aggressive)
*** 801,806 ****
--- 801,808 ----
     In aggressive mode, control dependences are taken into account, which
     results in more dead code elimination, but at the cost of some time.
  
+    If NO_CFG_CHANGES is true, avoid changing cfg.
+ 
     FIXME: Aggressive mode before PRE doesn't work currently because
  	  the dominance info is not invalidated after DCE1.  This is
  	  not an issue right now because we only run aggressive DCE
*************** tree_dce_done (bool aggressive)
*** 808,817 ****
  	  start experimenting with pass ordering.  */
  
  static void
! perform_tree_ssa_dce (bool aggressive)
  {
    struct edge_list *el = NULL;
  
    tree_dce_init (aggressive);
  
    if (aggressive)
--- 810,822 ----
  	  start experimenting with pass ordering.  */
  
  static void
! perform_tree_ssa_dce (bool aggressive, bool no_cfg_changes)
  {
    struct edge_list *el = NULL;
  
+   if (no_cfg_changes && aggressive)
+     abort ();
+ 
    tree_dce_init (aggressive);
  
    if (aggressive)
*************** perform_tree_ssa_dce (bool aggressive)
*** 833,839 ****
    if (aggressive)
      free_dominance_info (CDI_POST_DOMINATORS);
  
!   cleanup_tree_cfg ();
  
    /* Debugging dumps.  */
    if (dump_file)
--- 838,845 ----
    if (aggressive)
      free_dominance_info (CDI_POST_DOMINATORS);
  
!   if (!no_cfg_changes)
!     cleanup_tree_cfg ();
  
    /* Debugging dumps.  */
    if (dump_file)
*************** perform_tree_ssa_dce (bool aggressive)
*** 845,861 ****
    tree_dce_done (aggressive);
  }
  
  /* Pass entry points.  */
  static void
  tree_ssa_dce (void)
  {
!   perform_tree_ssa_dce (/*aggressive=*/false);
  }
  
  static void
  tree_ssa_cd_dce (void)
  {
!   perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
  }
  
  static bool
--- 851,875 ----
    tree_dce_done (aggressive);
  }
  
+ /* Cleanup the dead code, but avoid cfg changes.  */
+ 
+ void
+ tree_ssa_dce_no_cfg_changes (void)
+ {
+   perform_tree_ssa_dce (false, true);
+ }
+ 
  /* Pass entry points.  */
  static void
  tree_ssa_dce (void)
  {
!   perform_tree_ssa_dce (/*aggressive=*/false, false);
  }
  
  static void
  tree_ssa_cd_dce (void)
  {
!   perform_tree_ssa_dce (/*aggressive=*/optimize >= 2, false);
  }
  
  static bool
Index: tree-ssa-loop-im.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-im.c,v
retrieving revision 1.1.2.10
diff -c -3 -p -r1.1.2.10 tree-ssa-loop-im.c
*** tree-ssa-loop-im.c	21 Mar 2004 13:34:20 -0000	1.1.2.10
--- tree-ssa-loop-im.c	27 Mar 2004 18:26:37 -0000
*************** move_computations (void)
*** 576,581 ****
--- 576,588 ----
  
    loop_commit_inserts ();
    rewrite_into_ssa (false);
+   if (bitmap_first_set_bit (vars_to_rename) >= 0)
+     {
+       /* The rewrite of ssa names may cause violation of loop closed ssa
+ 	 form invariants.  TODO -- avoid these rewrites completely.
+ 	 Information in virtual phi nodes is sufficient for it.  */
+       rewrite_into_loop_closed_ssa ();
+     }
    bitmap_clear (vars_to_rename);
  }
  
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-ivopts.c,v
retrieving revision 1.1.2.19
diff -c -3 -p -r1.1.2.19 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c	23 Mar 2004 11:28:20 -0000	1.1.2.19
--- tree-ssa-loop-ivopts.c	27 Mar 2004 18:26:41 -0000
*************** struct version_info
*** 116,123 ****
  			   an expression that is not an induction variable.  */
    unsigned inv_id;	/* Id of an invariant.  */
    bool preserve_biv;	/* For the original biv, whether to preserve it.  */
-   struct loop *outermost_usage;
- 			/* The outermost loop in that the variable is used.  */
  };
  
  /* Description of number of iterations of a loop.  */
--- 116,121 ----
*************** find_exit_edges (void)
*** 845,914 ****
      }
  }
  
- /* Update usage information about OP using the fact that it is used in
-    the LOOP.  */
- 
- static void
- update_outermost_usage (struct ivopts_data *data, tree op, struct loop *loop)
- {
-   struct version_info *info;
- 
-   if (TREE_CODE (op) != SSA_NAME)
-     return;
-   info = name_info (data, op);
- 
-   if (!info->outermost_usage)
-     info->outermost_usage = loop;
-   else
-     info->outermost_usage = find_common_loop (loop, info->outermost_usage);
- }
- 
- /* Finds the outermost loop in that each ssa name is used.  */
- 
- static void
- find_outermost_usage (struct ivopts_data *data)
- {
-   basic_block bb;
-   block_stmt_iterator bsi;
-   unsigned i;
-   use_optype uses;
-   tree use, stmt, phi;
-   struct loop *loop, *aloop;
- 
-   FOR_EACH_BB (bb)
-     {
-       loop = bb->loop_father;
- 
-       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
- 	for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
- 	  {
- 	    use = PHI_ARG_DEF (phi, i);
- 
- 	    /* Use on the entry edge of a loop counts as use in the
- 	       superloop.  */
- 	    if (loop->header == bb
- 		&& PHI_ARG_EDGE (phi, i) == loop_preheader_edge (loop))
- 	      aloop = loop->outer;
- 	    else
- 	      aloop = loop;
- 	    update_outermost_usage (data, use, aloop);
- 	  }
- 
-       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- 	{
- 	  stmt = bsi_stmt (bsi);
- 	  get_stmt_operands (stmt);
- 
- 	  uses = STMT_USE_OPS (stmt);
- 	  for (i = 0; i < NUM_USES (uses); i++)
- 	    {
- 	      use = USE_OP (uses, i);
- 	      update_outermost_usage (data, use, loop);
- 	    }
- 	}
-     }
- }
- 
  /* Returns the basic block in that statements should be emitted for IP_END
     position in LOOP.  */
  
--- 843,848 ----
*************** ip_normal_pos (struct loop *loop)
*** 926,931 ****
--- 860,866 ----
  {
    tree last;
    basic_block bb;
+   edge exit;
  
    if (loop->latch->pred->pred_next)
      return NULL;
*************** ip_normal_pos (struct loop *loop)
*** 935,940 ****
--- 870,882 ----
    if (TREE_CODE (last) != COND_EXPR)
      return NULL;
  
+   exit = bb->succ;
+   if (exit->dest == loop->latch)
+     exit = exit->succ_next;
+ 
+   if (flow_bb_inside_loop_p (loop, exit->dest))
+     return NULL;
+ 
    return bb;
  }
  
*************** tree_ssa_iv_optimize_init (struct loops 
*** 1026,1032 ****
        loops->parray[i]->aux = xcalloc (1, sizeof (struct loop_data));
  
    find_exit_edges ();
-   find_outermost_usage (data);
  
    VARRAY_GENERIC_PTR_NOGC_INIT (data->iv_uses, 20, "iv_uses");
    VARRAY_GENERIC_PTR_NOGC_INIT (data->iv_candidates, 20, "iv_candidates");
--- 968,973 ----
*************** find_interesting_uses_stmt (struct ivopt
*** 2164,2170 ****
    tree *op_p, lhs, rhs;
    use_optype uses = NULL;
    unsigned i, n;
-   struct loop *loop;
  
    find_invariants_stmt (data, stmt);
  
--- 2105,2110 ----
*************** find_interesting_uses_stmt (struct ivopt
*** 2181,2203 ****
  
        if (TREE_CODE (lhs) == SSA_NAME)
  	{
! 	  /* If the statement defines an induction variable, uses of the induction
! 	     variables of the loop are not interesting.  */
  
  	  iv = get_iv (data, lhs);
  
  	  if (iv && !zero_p (iv->step))
! 	    {
! 	      /* If the variable is used outside of the loop, we must either
! 		 preserve it or express the final value in other way.  */
! 	      loop = name_info (data, lhs)->outermost_usage;
! 	      if (loop
! 		  && loop != data->current_loop
! 		  && !flow_loop_nested_p (data->current_loop, loop))
! 		find_interesting_uses_outer (data, lhs);
! 
! 	      return;
! 	    }
  	}
  
        switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
--- 2121,2133 ----
  
        if (TREE_CODE (lhs) == SSA_NAME)
  	{
! 	  /* If the statement defines an induction variable, the uses are not
! 	     interesting by themselves.  */
  
  	  iv = get_iv (data, lhs);
  
  	  if (iv && !zero_p (iv->step))
! 	    return;
  	}
  
        switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
*************** find_interesting_uses_stmt (struct ivopt
*** 2230,2247 ****
        iv = get_iv (data, lhs);
  
        if (iv && !zero_p (iv->step))
! 	{
! 	  /* If the variable is used outside of the loop, we must preserve it
! 	     or express the final value in other way.  */
! 	      
! 	  loop = name_info (data, lhs)->outermost_usage;
! 	  if (loop
! 	      && loop != data->current_loop
! 	      && !flow_loop_nested_p (data->current_loop, loop))
! 	    find_interesting_uses_outer (data, lhs);
! 
! 	  return;
! 	}
      }
  
    if (TREE_CODE (stmt) == PHI_NODE)
--- 2160,2166 ----
        iv = get_iv (data, lhs);
  
        if (iv && !zero_p (iv->step))
! 	return;
      }
  
    if (TREE_CODE (stmt) == PHI_NODE)
*************** find_interesting_uses_stmt (struct ivopt
*** 2270,2275 ****
--- 2189,2209 ----
      }
  }
  
+ /* Finds interesting uses of induction variables outside of loops
+    on loop exit edge EXIT.  */
+ 
+ static void
+ find_interesting_uses_outside (struct ivopts_data *data, edge exit)
+ {
+   tree phi, def;
+ 
+   for (phi = phi_nodes (exit->dest); phi; phi = TREE_CHAIN (phi))
+     {
+       def = phi_element_for_edge (phi, exit)->def;
+       find_interesting_uses_outer (data, def);
+     }
+ }
+ 
  /* Finds uses of the induction variables that are interesting.  */
  
  static void
*************** find_interesting_uses (struct ivopts_dat
*** 2281,2286 ****
--- 2215,2221 ----
    basic_block *body = get_loop_body (data->current_loop);
    unsigned i;
    struct version_info *info;
+   edge e;
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file, "Uses:\n\n");
*************** find_interesting_uses (struct ivopts_dat
*** 2289,2299 ****
--- 2224,2240 ----
      {
        bb = body[i];
  
+       for (e = bb->succ; e; e = e->succ_next)
+ 	if (e->dest != EXIT_BLOCK_PTR
+ 	    && !flow_bb_inside_loop_p (data->current_loop, e->dest))
+ 	  find_interesting_uses_outside (data, e);
+ 
        for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
  	find_interesting_uses_stmt (data, phi);
        for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
  	find_interesting_uses_stmt (data, bsi_stmt (bsi));
      }
+ 
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
        fprintf (dump_file, "\n");
*************** static void
*** 3950,3956 ****
  determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
  {
    unsigned cost_base, cost_step;
!   tree base;
  
    if (!cand->iv)
      {
--- 3891,3898 ----
  determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
  {
    unsigned cost_base, cost_step;
!   tree base, last;
!   basic_block bb;
  
    if (!cand->iv)
      {
*************** determine_iv_cost (struct ivopts_data *d
*** 3971,3976 ****
--- 3913,3930 ----
    /* Prefer the original iv unless we may gain something by replacing it.  */
    if (cand->pos == IP_ORIGINAL)
      cand->cost--;
+   
+   /* Prefer not to insert statements into latch unless there are some
+      already (so that we do not create unnecesary jumps).  */
+   if (cand->pos == IP_END)
+     {
+       bb = ip_end_pos (data->current_loop);
+       last = last_stmt (bb);
+ 
+       if (!last
+ 	  || TREE_CODE (last) == LABEL_EXPR)
+ 	cand->cost++;
+     }
  }
  
  /* Determines costs of computation of the candidates.  */
*************** rewrite_use_compare (struct ivopts_data 
*** 4690,4695 ****
--- 4644,4783 ----
    *op_p = op;
  }
  
+ /* Split loop exit edge EXIT.  The things are a bit complicated by a need to
+    preserve the loop closed ssa form.  */
+ 
+ static void
+ split_loop_exit_edge (edge exit)
+ {
+   basic_block dest = exit->dest;
+   basic_block bb = loop_split_edge_with (exit, NULL);
+   tree phi, *def_p, new_phi, new_name;
+ 
+   for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
+     {
+       def_p = &phi_element_for_edge (phi, bb->succ)->def;
+ 
+       new_name = duplicate_ssa_name (*def_p, NULL);
+       new_phi = create_phi_node (new_name, bb);
+       SSA_NAME_DEF_STMT (new_name) = new_phi;
+       add_phi_arg (&new_phi, *def_p, exit);
+       *def_p = new_name;
+     }
+ }
+ 
+ /* Ensure that operand *OP_P may be used at the end of EXIT without
+    violating loop closed ssa form.  */
+ 
+ static void
+ protect_loop_closed_ssa_form_use (edge exit, tree *op_p)
+ {
+   basic_block def_bb;
+   struct loop *def_loop;
+   tree phi;
+ 
+   if (TREE_CODE (*op_p) != SSA_NAME)
+     return;
+ 
+   def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (*op_p));
+   if (!def_bb)
+     return;
+ 
+   def_loop = def_bb->loop_father;
+   if (flow_bb_inside_loop_p (def_loop, exit->dest))
+     return;
+ 
+   /* Try finding a phi node that copies the value out of the loop.  */
+   for (phi = phi_nodes (exit->dest); phi; phi = TREE_CHAIN (phi))
+     if (phi_element_for_edge (phi, exit)->def == *op_p)
+       break;
+ 
+   if (!phi)
+     {
+       /* Create such a phi node.  */
+       tree new_name = duplicate_ssa_name (*op_p, NULL);
+ 
+       phi = create_phi_node (new_name, exit->dest);
+       SSA_NAME_DEF_STMT (new_name) = phi;
+       add_phi_arg (&phi, *op_p, exit);
+     }
+ 
+   *op_p = PHI_RESULT (phi);
+ }
+ 
+ /* Ensure that operands of STMT may be used at the end of EXIT without
+    violating loop closed ssa form.  */
+ 
+ static void
+ protect_loop_closed_ssa_form (edge exit, tree stmt)
+ {
+   use_optype uses;
+   vuse_optype vuses;
+   vdef_optype vdefs;
+   unsigned i;
+ 
+   get_stmt_operands (stmt);
+ 
+   uses = STMT_USE_OPS (stmt);
+   for (i = 0; i < NUM_USES (uses); i++)
+     protect_loop_closed_ssa_form_use (exit, USE_OP_PTR (uses, i));
+ 
+   vuses = STMT_VUSE_OPS (stmt);
+   for (i = 0; i < NUM_VUSES (vuses); i++)
+     protect_loop_closed_ssa_form_use (exit, VUSE_OP_PTR (vuses, i));
+ 
+   vdefs = STMT_VDEF_OPS (stmt);
+   for (i = 0; i < NUM_VDEFS (vdefs); i++)
+     protect_loop_closed_ssa_form_use (exit, VDEF_OP_PTR (vdefs, i));
+ }
+ 
+ /* STMTS compute a value of a phi argument OP on EXIT of a loop.  Arrange things
+    so that they are emitted on the correct place, and so that the loop closed
+    ssa form is preserved.  */
+ 
+ void
+ compute_phi_arg_on_exit (edge exit, tree stmts, tree op)
+ {
+   tree_stmt_iterator tsi;
+   block_stmt_iterator bsi;
+   tree phi, stmt, def, next;
+ 
+   if (exit->dest->pred->pred_next)
+     split_loop_exit_edge (exit);
+ 
+   if (TREE_CODE (stmts) == STATEMENT_LIST)
+     {
+       for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi))
+ 	protect_loop_closed_ssa_form (exit, tsi_stmt (tsi));
+     }
+   else
+     protect_loop_closed_ssa_form (exit, stmts);
+ 
+   /* Ensure there is label in exit->dest, so that we can
+      insert after it.  */
+   tree_block_label (exit->dest);
+   bsi = bsi_after_labels (exit->dest);
+   bsi_insert_after (&bsi, stmts, BSI_CONTINUE_LINKING);
+ 
+   if (!op)
+     return;
+ 
+   for (phi = phi_nodes (exit->dest); phi; phi = next)
+     {
+       next = TREE_CHAIN (phi);
+ 
+       if (phi_element_for_edge (phi, exit)->def == op)
+ 	{
+ 	  def = PHI_RESULT (phi);
+ 	  remove_statement (phi, false);
+ 	  stmt = build (MODIFY_EXPR, TREE_TYPE (op),
+ 			def, op);
+ 	  SSA_NAME_DEF_STMT (def) = stmt;
+ 	  bsi_insert_after (&bsi, stmt, BSI_CONTINUE_LINKING);
+ 	}
+     }
+ }
+ 
  /* Rewrites the final value of USE (that is only needed outside of the loop)
     using candidate CAND.  */
  
*************** rewrite_use_outer (struct ivopts_data *d
*** 4698,4713 ****
  		   struct iv_use *use, struct iv_cand *cand)
  {
    edge exit;
!   tree value, op, stmts, tgt = *use->op_p, type = TREE_TYPE (tgt), ass;
  
    exit = loop_data (data->current_loop)->single_exit;
  
-   /* If the variable is going to be preserved anyway, there is nothing to
-      do.  TODO except if the final value is a constant or something similarly
-      simple to compute.  */
-   if (name_info (data, tgt)->preserve_biv)
-     return;
- 
    if (exit)
      {
        if (!cand->iv)
--- 4786,4796 ----
  		   struct iv_use *use, struct iv_cand *cand)
  {
    edge exit;
!   tree value, op, stmts, tgt = *use->op_p;
!   tree phi;
  
    exit = loop_data (data->current_loop)->single_exit;
  
    if (exit)
      {
        if (!cand->iv)
*************** rewrite_use_outer (struct ivopts_data *d
*** 4719,4735 ****
  	value = get_computation_at (data->current_loop,
  				    use, cand, last_stmt (exit->src));
  
!       op = force_gimple_operand (value, &stmts, SSA_NAME_VAR (tgt), false);
  
        if (stmts)
! 	bsi_insert_on_edge (exit, stmts);
!       ass = build (MODIFY_EXPR, type, tgt, op);
!       bsi_insert_on_edge (exit, ass);
!       remove_statement (use->stmt, false);
!       SSA_NAME_DEF_STMT (tgt) = ass;
        return;
      }
  
    /* Otherwise we just need to compute the iv.  */
    rewrite_use_nonlinear_expr (data, use, cand);
  }
--- 4802,4834 ----
  	value = get_computation_at (data->current_loop,
  				    use, cand, last_stmt (exit->src));
  
!       op = force_gimple_operand (value, &stmts, SSA_NAME_VAR (tgt), true);
! 	  
!       /* If we will preserve the iv anyway and we would need to perform
! 	 some computation to replace the final value, do nothing.  */
!       if (stmts && name_info (data, tgt)->preserve_biv)
! 	return;
! 
!       for (phi = phi_nodes (exit->dest); phi; phi = TREE_CHAIN (phi))
! 	{
! 	  tree *def_p = &phi_element_for_edge (phi, exit)->def;
! 
! 	  if (*def_p == tgt)
! 	    *def_p = op;
! 	}
  
        if (stmts)
! 	compute_phi_arg_on_exit (exit, stmts, op);
! 
!       remove_statement (use->stmt, true);
        return;
      }
  
+   /* If the variable is going to be preserved anyway, there is nothing to
+      do.  */
+   if (name_info (data, tgt)->preserve_biv)
+     return;
+ 
    /* Otherwise we just need to compute the iv.  */
    rewrite_use_nonlinear_expr (data, use, cand);
  }
*************** tree_ssa_iv_optimize (struct loops *loop
*** 4975,4987 ****
    while (loop->inner)
      loop = loop->inner;
  
    /* Scan the loops, inner ones first.  */
    while (loop != loops->tree_root)
      {
        if (tree_ssa_iv_optimize_loop (&data, loop))
  	{
  #ifdef ENABLE_CHECKING
! 	  verify_ssa ();
  #endif
  	}
  
--- 5074,5090 ----
    while (loop->inner)
      loop = loop->inner;
  
+ #ifdef ENABLE_CHECKING
+   verify_loop_closed_ssa ();
+ #endif
+ 
    /* Scan the loops, inner ones first.  */
    while (loop != loops->tree_root)
      {
        if (tree_ssa_iv_optimize_loop (&data, loop))
  	{
  #ifdef ENABLE_CHECKING
! 	  verify_loop_closed_ssa ();
  #endif
  	}
  
Index: tree-ssa-loop-manip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-manip.c,v
retrieving revision 1.1.2.6
diff -c -3 -p -r1.1.2.6 tree-ssa-loop-manip.c
*** tree-ssa-loop-manip.c	21 Mar 2004 13:34:21 -0000	1.1.2.6
--- tree-ssa-loop-manip.c	27 Mar 2004 18:26:42 -0000
*************** static void lv_update_pending_stmts (edg
*** 41,56 ****
  static void lv_adjust_loop_header_phi (basic_block, basic_block, basic_block, 
  				       edge);
  
- /* Checks whether E is an exit edge of the MFB_REE_LOOP.  Callback for
-    make_forwarder_block.  */
- 
- static struct loop *mfb_ree_loop;
- static bool
- mfb_redirect_exit_edges (edge e)
- {
-   return flow_bb_inside_loop_p (mfb_ree_loop, e->src);
- }
- 
  /* Copies phi nodes in newly created copies of the LOOP.  The new blocks start
     since FIRST_NEW_BLOCK index.  PEELING is true if we were peeling
     the loop.  */
--- 41,46 ----
*************** copy_phi_nodes (struct loop *loop, unsig
*** 79,87 ****
  		abort ();
  
  	      new_e = bb->pred;
! 	      e = (peeling && bb->rbi->copy_number == 1
! 		   ? entry
! 		   : latch);
  	      def = phi_element_for_edge (phi, e)->def;
  	      add_phi_arg (&new_phi, def, new_e);
  	      continue;
--- 69,75 ----
  		abort ();
  
  	      new_e = bb->pred;
! 	      e = (peeling && bb->rbi->copy_number == 1 ? entry : latch);
  	      def = phi_element_for_edge (phi, e)->def;
  	      add_phi_arg (&new_phi, def, new_e);
  	      continue;
*************** rename_variables (unsigned first_new_blo
*** 273,283 ****
      }
  }
  
! /* Releases the structures holding the new ssa names.  If FREE_VARS is true,
!    also the original ssa names are released.  */
  
  static void
! free_new_names (tree definitions, bool free_vars)
  {
    tree def;
    ssa_name_ann_t ann;
--- 261,271 ----
      }
  }
  
! /* Releases the structures holding the new ssa names. The original ssa names
!    are released.  */
  
  static void
! free_new_names (tree definitions)
  {
    tree def;
    ssa_name_ann_t ann;
*************** free_new_names (tree definitions, bool f
*** 290,297 ****
        free (ann->common.aux);
        ann->common.aux = NULL;
  
!       if (free_vars)
! 	release_ssa_name (def);
      }
  }
  
--- 278,284 ----
        free (ann->common.aux);
        ann->common.aux = NULL;
  
!       release_ssa_name (def);
      }
  }
  
*************** set_phi_def_stmts (basic_block bb)
*** 306,311 ****
--- 293,324 ----
      SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi;
  }
  
+ /* Extends phi nodes on EXIT to the newly created edges.  */
+ 
+ static void
+ extend_exit_phi_nodes (unsigned first_new_block, edge exit)
+ {
+   basic_block exit_block = exit->dest;
+   edge ae;
+   tree phi, def;
+ 
+   for (phi = phi_nodes (exit_block); phi; phi = TREE_CHAIN (phi))
+     {
+       def = phi_element_for_edge (phi, exit)->def;
+ 
+       for (ae = exit_block->pred; ae; ae = ae->pred_next)
+ 	{
+ 	  if (ae->src->index < (int) first_new_block)
+ 	    continue;
+ 
+ 	  if (ae->src->rbi->original != exit->src)
+ 	    continue;
+ 
+ 	  add_phi_arg (&phi, def, ae);
+ 	}
+     }
+ }
+ 
  /* The same ad cfgloopmanip.c:duplicate_loop_to_header_edge, but also updates
     ssa.  In order to achieve this, only loops whose exits all lead to the same
     location are handled.
*************** tree_duplicate_loop_to_header_edge (stru
*** 322,391 ****
  				    unsigned int *n_to_remove, int flags)
  {
    unsigned first_new_block;
!   basic_block exit_block = NULL, bb;
!   unsigned n_exits, i;
!   edge *exits;
    bool peeling = (e != loop_latch_edge (loop));
!   edge latch, latch_copy, ae, oe;
    tree phi, arg, map, def;
!   tree definitions, usable_outside;
  
    if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
      return false;
    if (!(loops->state & LOOPS_HAVE_PREHEADERS))
      return false;
  
!   exits = get_loop_exit_edges (loop, &n_exits);
!   for (i = 0; i < n_exits; i++)
!     {
!       /* Edges to exit can be safely ignored, since no uses may be reached
! 	 through them.  */
!       if(exits[i]->dest == EXIT_BLOCK_PTR)
! 	continue;
! 
!       if (!exit_block)
! 	exit_block = exits[i]->dest;
!       else if (exits[i]->dest != exit_block)
! 	{
! 	  free (exits);
! 	  return false;
! 	}
!     }
!   free (exits);
! 
!   /* Ensure that only exits of the loop enter the exit_block.  */
!   if (exit_block)
!     {
!       for (ae = exit_block->pred; ae; ae = ae->pred_next)
! 	if (!flow_bb_inside_loop_p (loop, ae->src))
! 	  break;
! 
!       if (ae)
! 	{
! 	  mfb_ree_loop = loop;
! 	  make_forwarder_block (exit_block, mfb_redirect_exit_edges, NULL);
! 	  bb = exit_block->succ->dest;
! 	  add_bb_to_loop (bb, exit_block->loop_father);
! 
! 	  if (exit_block->loop_father->latch == exit_block)
! 	    exit_block->loop_father->latch = bb;
! 	}
!     }
  
    definitions = collect_defs (loop);
-   usable_outside = NULL_TREE;
-   if (exit_block)
-     {
-       for (arg = definitions; arg; arg = TREE_CHAIN (arg))
- 	{
- 	  def = TREE_VALUE (arg);
- 	  if (!dominated_by_p (CDI_DOMINATORS, exit_block,
- 		    	       bb_for_stmt (SSA_NAME_DEF_STMT (def))))
- 	    continue;
- 
- 	  usable_outside = tree_cons (NULL, def, usable_outside);
- 	}
-     }
  
    first_new_block = last_basic_block;
    if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
--- 335,360 ----
  				    unsigned int *n_to_remove, int flags)
  {
    unsigned first_new_block;
!   basic_block bb;
!   unsigned i;
    bool peeling = (e != loop_latch_edge (loop));
!   edge latch, latch_copy;
    tree phi, arg, map, def;
!   tree definitions;
!   edge *exits;
!   unsigned n_exits;
  
    if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
      return false;
    if (!(loops->state & LOOPS_HAVE_PREHEADERS))
      return false;
  
! #ifdef ENABLE_CHECKING
!   verify_loop_closed_ssa ();
! #endif
  
+   exits = get_loop_exit_edges (loop, &n_exits);
    definitions = collect_defs (loop);
  
    first_new_block = last_basic_block;
    if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
*************** tree_duplicate_loop_to_header_edge (stru
*** 410,453 ****
    if (arg)
      abort ();
  
!   if (exit_block)
!     {
!       /* Extend the phi nodes in exit_block.  */
!       for (phi = phi_nodes (exit_block); phi; phi = TREE_CHAIN (phi))
! 	{
! 	  for (ae = exit_block->pred; ae; ae = ae->pred_next)
! 	    {
! 	      if (ae->src->rbi->copy_number == 0)
! 		continue;
! 
! 	      oe = find_edge (ae->src->rbi->original, exit_block);
! 	      if (!oe)
! 		abort ();
! 
! 	      def = phi_element_for_edge (phi, oe)->def;
! 	      add_phi_arg (&phi, def, ae);
! 	    }
! 	}
  
-       /* Add phi nodes for definitions to exit_block (we could find out
- 	 which of them are really used outside of the loop and don't emit the
- 	 phi nodes for the remaining ones; for this we would however need
- 	 to know immediate uses).  */
-       for (arg = usable_outside; arg; arg = TREE_CHAIN (arg))
- 	{
- 	  def = TREE_VALUE (arg);
- 	  phi = create_phi_node (def, exit_block);
- 	  for (ae = exit_block->pred; ae; ae = ae->pred_next)
- 	    add_phi_arg (&phi, def, ae);
- 	}
-     }
-   
    /* Copy the phi nodes.  */
    copy_phi_nodes (loop, first_new_block, peeling);
  
    /* Rename the variables.  */
    rename_variables (first_new_block);
!   free_new_names (definitions, exit_block == NULL);
  
    /* For some time we have the identical ssa names as results in multiple phi
       nodes.  When phi node is resized, it sets SSA_NAME_DEF_STMT of its result
--- 379,395 ----
    if (arg)
      abort ();
  
!   /* Extend exit phi nodes.  */
!   for (i = 0; i < n_exits; i++)
!     extend_exit_phi_nodes (first_new_block, exits[i]);
!   free (exits);
  
    /* Copy the phi nodes.  */
    copy_phi_nodes (loop, first_new_block, peeling);
  
    /* Rename the variables.  */
    rename_variables (first_new_block);
!   free_new_names (definitions);
  
    /* For some time we have the identical ssa names as results in multiple phi
       nodes.  When phi node is resized, it sets SSA_NAME_DEF_STMT of its result
*************** tree_duplicate_loop_to_header_edge (stru
*** 462,469 ****
        if (bb->rbi->copy_number == 1)
    	set_phi_def_stmts (bb->rbi->original);
      }
!   if (exit_block)
!     set_phi_def_stmts (exit_block);
  
    return true;
  }
--- 404,413 ----
        if (bb->rbi->copy_number == 1)
    	set_phi_def_stmts (bb->rbi->original);
      }
! 
! #ifdef ENABLE_CHECKING
!   verify_loop_closed_ssa ();
! #endif
  
    return true;
  }
*************** tree_ssa_loop_version (struct loops *loo
*** 680,688 ****
        entry->flags |= irred_flag;
        return NULL;
      }
-   entry->flags |= irred_flag;
  
!   /* After duplication entry edge now points to new loop head blcok.
       Note down new head as second_head.  */
    second_head = entry->dest;
  
--- 624,631 ----
        entry->flags |= irred_flag;
        return NULL;
      }
  
!   /* After duplication entry edge now points to new loop head block.
       Note down new head as second_head.  */
    second_head = entry->dest;
  
*************** tree_ssa_loop_version (struct loops *loo
*** 706,713 ****
    /* At this point condition_bb is loop predheader with two successors, 
       first_head and second_head.   Make sure that loop predheader has only 
       one successor. */
!   loop_split_edge_with (find_edge (condition_bb, first_head), NULL);
!   loop_split_edge_with (find_edge (condition_bb, second_head), NULL);
  
    /* Ensure that the latch has just a single successor.  */
    loop_split_edge_with (loop_latch_edge (loop), NULL);
--- 649,664 ----
    /* At this point condition_bb is loop predheader with two successors, 
       first_head and second_head.   Make sure that loop predheader has only 
       one successor. */
!   if (irred_flag)
!     {
!       condition_bb->flags |= BB_IRREDUCIBLE_LOOP;
!       loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
!       loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
!       condition_bb->pred->flags |= EDGE_IRREDUCIBLE_LOOP;
!     }
! 
!   loop_split_edge_with (loop_preheader_edge (loop), NULL);
!   loop_split_edge_with (loop_preheader_edge (nloop), NULL);
  
    /* Ensure that the latch has just a single successor.  */
    loop_split_edge_with (loop_latch_edge (loop), NULL);
*************** tree_ssa_loop_version (struct loops *loo
*** 716,722 ****
    return nloop;
  }
  
- 
  void
  test_loop_versioning (struct loops *loops)
  {
--- 667,672 ----
*************** test_loop_versioning (struct loops *loop
*** 741,744 ****
--- 691,966 ----
        verify_ssa ();
      }
  
+ }
+ 
+ /* 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);
+   edge e;
+ 
+   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 the USE in BB.  Mark the ssa names in NAMES_TO_RENAME.
+    Exits of the loops are stored in EXITS array of length N_EXITS.  */
+ 
+ static void
+ add_exit_phis_use (basic_block bb, tree use, bitmap names_to_rename,
+ 		   unsigned n_exits, basic_block *exits)
+ {
+   tree def;
+   basic_block def_bb;
+   unsigned i;
+   
+   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))
+     return;
+ 
+   if (bitmap_bit_p (names_to_rename, SSA_NAME_VERSION (use)))
+     return;
+   bitmap_set_bit (names_to_rename, SSA_NAME_VERSION (use));
+ 
+   /* We must add phi nodes for all loop exits (not just those involved),
+      since ssa rewriting creates new phi nodes in loop headers.  ??? Perhaps
+      it would be sufficient to do this for superloops of the
+      def_bb->loop_father?  */
+ 
+   /* Do not insert a new phi if there already is one defining the use.  */
+   if (TREE_CODE (def) != PHI_NODE)
+     def_bb = NULL;
+ 
+   for (i = 0; i < n_exits; i++)
+     if (exits[i] != def_bb)
+       add_exit_phis_edge (exits[i], use);
+ }
+ 
+ /* Add exit phis for the names used in STMT in BB.  Mark the ssa names in
+    NAMES_TO_RENAME.  Exits of the loops are stored in EXITS array of length
+    N_EXITS.  */
+ 
+ static void
+ add_exit_phis_stmt (basic_block bb, tree stmt, bitmap names_to_rename,
+ 		    unsigned n_exits, basic_block *exits)
+ {
+   use_optype uses;
+   vuse_optype vuses;
+   vdef_optype vdefs;
+   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++)
+     add_exit_phis_use (bb, USE_OP (uses, i), names_to_rename,
+ 		       n_exits, exits);
+ 
+   vuses = VUSE_OPS (ann);
+   for (i = 0; i < NUM_VUSES (vuses); i++)
+     add_exit_phis_use (bb, VUSE_OP (vuses, i), names_to_rename,
+ 		       n_exits, exits);
+ 
+   vdefs = VDEF_OPS (ann);
+   for (i = 0; i < NUM_VDEFS (vdefs); i++)
+     add_exit_phis_use (bb, VDEF_OP (vdefs, i), names_to_rename,
+ 		       n_exits, exits);
+ }
+ 
+ /* Add exit phis for the names used outside of the loop they are
+    defined in.  Mark the ssa names in NAMES_TO_RENAME.  Exits of
+    the loops are stored in EXITS array of length N_EXITS.  */
+ 
+ static void
+ add_exit_phis (bitmap names_to_rename, unsigned n_exits, basic_block *exits)
+ {
+   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++)
+ 	  add_exit_phis_use (PHI_ARG_EDGE (phi, i)->src,
+ 			     PHI_ARG_DEF (phi, i),
+ 			     names_to_rename,
+ 			     n_exits, exits);
+ 
+       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ 	add_exit_phis_stmt (bb, bsi_stmt (bsi), names_to_rename,
+ 			    n_exits, exits);
+     }
+ }
+ 
+ /* Stores all loop exit edge targets to EXITS and their number to N_EXITS.  */
+ 
+ static void
+ get_loops_exits (unsigned *n_exits, basic_block **exits)
+ {
+   basic_block bb;
+   edge e;
+ 
+   *n_exits = 0;
+   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))
+ 	  {
+ 	    (*n_exits)++;
+ 	    break;
+ 	  }
+     }
+ 
+   if (!*n_exits)
+     {
+       *exits = NULL;
+       return;
+     }
+ 
+   *exits = xmalloc ((*n_exits) * sizeof (basic_block));
+   *n_exits = 0;
+   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))
+ 	  {
+ 	    (*exits)[(*n_exits)++] = bb;
+ 	    break;
+ 	  }
+     }
+ }
+ 
+ /* 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 strenghtening 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 100 and step 1.  */
+ 
+ void
+ rewrite_into_loop_closed_ssa (void)
+ {
+   bitmap names_to_rename = BITMAP_XMALLOC ();
+   unsigned n_loop_exits;
+   basic_block *loop_exits;
+ 
+   get_loops_exits (&n_loop_exits, &loop_exits);
+ 
+   /* Add the phi nodes on exits of the loops for the names we need to
+      rewrite.  Also mark the new names to rewrite.  */
+   add_exit_phis (names_to_rename, n_loop_exits, loop_exits);
+ 
+   /* Do the rewriting.  */
+   rewrite_ssa_into_ssa (names_to_rename);
+   BITMAP_XFREE (names_to_rename);
+ 
+   free (loop_exits);
+ 
+   /* Prune the useless phi nodes.  */
+   tree_ssa_dce_no_cfg_changes ();
+ }
+ 
+ /* 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;
+   vdef_optype vdefs;
+   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));
+ 
+   vdefs = VDEF_OPS (ann);
+   for (i = 0; i < NUM_VDEFS (vdefs); i++)
+     check_loop_closed_ssa_use (bb, VDEF_OP (vdefs, 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/Attic/tree-ssa-loop.c,v
retrieving revision 1.1.2.3.2.16
diff -c -3 -p -r1.1.2.3.2.16 tree-ssa-loop.c
*** tree-ssa-loop.c	21 Mar 2004 13:34:21 -0000	1.1.2.3.2.16
--- tree-ssa-loop.c	27 Mar 2004 18:26:42 -0000
*************** Software Foundation, 59 Temple Place - S
*** 39,54 ****
  #include "tree-inline.h"
  
  /* Initializes the loop structures.  DUMP is the file to that the details
!    about the analysis should be dumped.  */
  
  struct loops *
! tree_loop_optimizer_init (FILE *dump)
  {
    struct loops *loops = loop_optimizer_init (dump);
  
    if (!loops)
      return NULL;
  
    /* Creation of preheaders may create redundant phi nodes (if the loop is
       entered by more than one edge, but the initial value of the induction
       variable is the same on all of them).  */
--- 39,59 ----
  #include "tree-inline.h"
  
  /* Initializes the loop structures.  DUMP is the file to that the details
!    about the analysis should be dumped.  If CANONICALIZE_SSA is true, loop
!    closed ssa form is enforced and redundant phi nodes created by creating
!    preheaders are cleaned up.  */
  
  struct loops *
! tree_loop_optimizer_init (FILE *dump, bool canonicalize_ssa)
  {
    struct loops *loops = loop_optimizer_init (dump);
  
    if (!loops)
      return NULL;
  
+   if (!canonicalize_ssa)
+     return loops;
+ 
    /* Creation of preheaders may create redundant phi nodes (if the loop is
       entered by more than one edge, but the initial value of the induction
       variable is the same on all of them).  */
*************** tree_loop_optimizer_init (FILE *dump)
*** 56,61 ****
--- 61,72 ----
    rewrite_into_ssa (false);
    bitmap_clear (vars_to_rename);
  
+   rewrite_into_loop_closed_ssa ();
+ 
+ #ifdef ENABLE_CHECKING
+   verify_loop_closed_ssa ();
+ #endif
+ 
    return loops;
  }
  
*************** tree_ssa_loop_opt (void)
*** 68,74 ****
  {
    struct loops *loops;
  
!   loops = tree_loop_optimizer_init (dump_file);
  
    if (loops)
      {
--- 79,85 ----
  {
    struct loops *loops;
  
!   loops = tree_loop_optimizer_init (dump_file, true);
  
    if (loops)
      {
*************** copy_loop_headers (void)
*** 343,349 ****
    edge preheader_edge;
    varray_type bbs_to_duplicate = NULL;
  
!   loops = tree_loop_optimizer_init (dump_file);
    if (!loops)
      return;
    
--- 354,360 ----
    edge preheader_edge;
    varray_type bbs_to_duplicate = NULL;
  
!   loops = tree_loop_optimizer_init (dump_file, false);
    if (!loops)
      return;
    


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]