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] Final value replacement


Hello,

this patch adds possibility to replace the final value of the induction
variable that is unused otherwise, e.g.

for (i = 0; i < 10; i++)
  j = 2 * i;

to

for (i = 0; i < 10; i++);
j = 18;

Zdenek

Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.90
diff -c -3 -p -r1.1.2.90 ChangeLog.lno
*** ChangeLog.lno	18 Mar 2004 20:21:50 -0000	1.1.2.90
--- ChangeLog.lno	18 Mar 2004 21:26:23 -0000
***************
*** 1,3 ****
--- 1,36 ----
+ 2003-03-18  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>
+ 
+ 	* tree-flow.h (loop_commit_inserts): Declare.
+ 	* tree-ssa-loop-im.c (commit_inserts): Rename to...
+ 	(loop_commit_inserts): ... this.
+ 	* move_computations (move_computations, determine_lsm): Use
+ 	loop_commit_inserts.
+ 	* tree-ssa-loop-ivopts.c (AVG_LOOP_NITER): New macro.
+ 	(struct iv): New field use_id.
+ 	(struct version_info): New field preserve_biv.
+ 	(alloc_iv, record_use, free_loop_data): Initialize new fields.
+ 	(enum use_type): Add USE_OUTER.
+ 	(dump_use, find_interesting_uses_op, add_derived_ivs_candidates,
+ 	determine_use_iv_cost, rewrite_use): Handle USE_OUTER.
+ 	(dump_cand, find_interesting_uses_stmt, add_candidate_1,
+ 	determine_use_iv_cost_condition, determine_iv_cost, set_cost,
+ 	create_new_iv, rewrite_use_nonlinear_expr): Handle final value
+ 	replacement.
+ 	(find_interesting_uses_outer, add_iv_outer_candidates,
+ 	may_replace_final_value, determine_use_iv_cost_outer,
+ 	remove_statement, rewrite_use_outer): New functions.
+ 	(var_at_use): Replaced by ...
+ 	(var_at_stmt): ... this.
+ 	(get_computation_at): Split from ...
+ 	(get_computation): ... here.
+ 	(get_computation_cost_at): Split from ...
+ 	(get_computation_cost): ... here.
+ 	(iv_value): Split from ...
+ 	(cand_value_at): ... here.
+ 	(may_eliminate_iv, rewrite_use_compare): Reflect these changes.
+ 	(tree_ssa_iv_optimize_loop): Call loop_commit_inserts.
+ 	* tree-ssanames.c (make_ssa_name): Handle NULL argument.
+ 
  2003-03-18  Devang Patel  <dpatel@apple.com>
  
  	* tree-ssa-live.c (new_tree_live_info): Set num_blocks to 
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.177.2.15
diff -c -3 -p -r1.1.4.177.2.15 tree-flow.h
*** tree-flow.h	17 Mar 2004 18:39:42 -0000	1.1.4.177.2.15
--- tree-flow.h	18 Mar 2004 21:26:24 -0000
*************** void test_loop_versioning (struct loops 
*** 612,617 ****
--- 612,618 ----
  bool tree_ssa_loop_version (struct loops *, struct loop *, tree);
  bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *);
  void linear_transform_loops (struct loops *, varray_type);
+ void loop_commit_inserts (void);
  
  /* In tree-flow-inline.h  */
  static inline int phi_arg_from_edge (tree, edge);
Index: tree-ssa-loop-im.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-im.c,v
retrieving revision 1.1.2.7
diff -c -3 -p -r1.1.2.7 tree-ssa-loop-im.c
*** tree-ssa-loop-im.c	17 Mar 2004 18:39:43 -0000	1.1.2.7
--- tree-ssa-loop-im.c	18 Mar 2004 21:26:24 -0000
*************** determine_invariantness (void)
*** 475,482 ****
  
  /* Commits edge inserts and updates loop info.  */
  
! static void
! commit_inserts (void)
  {
    unsigned old_last_basic_block, i;
    basic_block bb;
--- 475,482 ----
  
  /* Commits edge inserts and updates loop info.  */
  
! void
! loop_commit_inserts (void)
  {
    unsigned old_last_basic_block, i;
    basic_block bb;
*************** move_computations (void)
*** 554,560 ****
    walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
    fini_walk_dominator_tree (&walk_data);
  
!   commit_inserts ();
    rewrite_into_ssa (false);
    bitmap_clear (vars_to_rename);
  }
--- 554,560 ----
    walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
    fini_walk_dominator_tree (&walk_data);
  
!   loop_commit_inserts ();
    rewrite_into_ssa (false);
    bitmap_clear (vars_to_rename);
  }
*************** determine_lsm (struct loops *loops)
*** 922,928 ****
  	  if (loop == loops->tree_root)
  	    {
  	      free_df ();
! 	      commit_inserts ();
  	      return;
  	    }
  	}
--- 922,928 ----
  	  if (loop == loops->tree_root)
  	    {
  	      free_df ();
! 	      loop_commit_inserts ();
  	      return;
  	    }
  	}
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-ivopts.c,v
retrieving revision 1.1.2.14
diff -c -3 -p -r1.1.2.14 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c	3 Mar 2004 21:33:09 -0000	1.1.2.14
--- tree-ssa-loop-ivopts.c	18 Mar 2004 21:26:24 -0000
*************** Software Foundation, 59 Temple Place - S
*** 88,93 ****
--- 88,97 ----
  /* The infinite cost.  */
  #define INFTY 10000000
  
+ /* The expected number of loop iterations.  TODO -- use profiling instead of
+    this.  */
+ #define AVG_LOOP_NITER(LOOP) 5
+ 
  /* Just to shorten the ugly names.  */
  #define EXEC_BINARY nondestructive_fold_binary_to_constant
  #define EXEC_UNARY nondestructive_fold_unary_to_constant
*************** struct iv
*** 100,105 ****
--- 104,110 ----
    tree ssa_name;	/* The ssa name with the value.  */
    bool biv_p;		/* Is it a biv?  */
    bool have_use_for;	/* Do we already have a use for it?  */
+   unsigned use_id;	/* The identificator in the use if it is the case.  */
  };
  
  /* The currently optimized loop.  ??? Perhaps it would be better to pass it
*************** struct version_info
*** 118,123 ****
--- 123,129 ----
    bool has_nonlin_use;	/* For a loop-level invariant, whether it is used in
  			   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.  */
  };
*************** struct loop_data
*** 158,163 ****
--- 164,170 ----
  enum use_type
  {
    USE_NONLINEAR_EXPR,	/* Use in a nonlinear expression.  */
+   USE_OUTER,		/* The induction variable is used outside the loop.  */
    USE_ADDRESS,		/* Use in an address.  */
    USE_COMPARE		/* Use is a compare.  */
  };
*************** struct iv_cand
*** 218,224 ****
  			   incremented.  */
    tree var_before;	/* The variable used for it before incrementation.  */
    tree var_after;	/* The variable used for it after incrementation.  */
!   struct iv *iv;	/* The value of the candidate.  */
    unsigned cost;	/* Cost of the candidate.  */
  };
  
--- 225,234 ----
  			   incremented.  */
    tree var_before;	/* The variable used for it before incrementation.  */
    tree var_after;	/* The variable used for it after incrementation.  */
!   struct iv *iv;	/* The value of the candidate.  NULL for
! 			   "pseudocandidate" used to indicate the possibility
! 			   to replace the final value of an iv by direct
! 			   computation of the value.  */
    unsigned cost;	/* Cost of the candidate.  */
  };
  
*************** dump_use (FILE *file, struct iv_use *use
*** 298,303 ****
--- 308,317 ----
        fprintf (file, "  generic\n");
        break;
  
+     case USE_OUTER:
+       fprintf (file, "  outside\n");
+       break;
+ 
      case USE_ADDRESS:
        fprintf (file, "  address\n");
        break;
*************** dump_use (FILE *file, struct iv_use *use
*** 305,310 ****
--- 319,327 ----
      case USE_COMPARE:
        fprintf (file, "  compare\n");
        break;
+ 
+     default:
+       abort ();
      }
  
     fprintf (file, "  in statement ");
*************** dump_cand (FILE *file, struct iv_cand *c
*** 365,370 ****
--- 382,393 ----
    fprintf (file, "candidate %d%s\n",
  	   cand->id, cand->important ? " (important)" : "");
  
+   if (!iv)
+     {
+       fprintf (file, "  final value replacement\n");
+       return;
+     }
+ 
    switch (cand->pos)
      {
  #if DISABLE_IP_START
*************** alloc_iv (tree base, tree step)
*** 996,1001 ****
--- 1019,1025 ----
    iv->step = step;
    iv->biv_p = false;
    iv->have_use_for = false;
+   iv->use_id = 0;
    iv->ssa_name = NULL_TREE;
  
    return iv;
*************** find_induction_variables (void)
*** 1791,1797 ****
  
  /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV.  */
  
! static void
  record_use (tree *use_p, struct iv *iv, tree stmt, enum use_type use_type)
  {
    struct iv_use *use = xcalloc (1, sizeof (struct iv_use));
--- 1815,1821 ----
  
  /* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV.  */
  
! static struct iv_use *
  record_use (tree *use_p, struct iv *iv, tree stmt, enum use_type use_type)
  {
    struct iv_use *use = xcalloc (1, sizeof (struct iv_use));
*************** record_use (tree *use_p, struct iv *iv, 
*** 1807,1812 ****
--- 1831,1838 ----
      dump_use (tree_dump_file, use);
  
    VARRAY_PUSH_GENERIC_PTR_NOGC (iv_uses, use);
+ 
+   return use;
  }
  
  /* Checks whether OP is a loop-level invariant and if so, records it.
*************** find_interesting_uses_op (tree *op_p)
*** 1848,1855 ****
      return;
  
    iv = get_iv (*op_p);
!   if (!iv || iv->have_use_for)
      return;
    if (zero_p (iv->step))
      {
        record_invariant (*op_p, true);
--- 1874,1894 ----
      return;
  
    iv = get_iv (*op_p);
!   if (!iv)
      return;
+   
+   if (iv->have_use_for)
+     {
+       struct iv_use *use = VARRAY_GENERIC_PTR_NOGC (iv_uses, iv->use_id);
+ 
+       if (use->type != USE_NONLINEAR_EXPR
+ 	  && use->type != USE_OUTER)
+ 	abort ();
+ 
+       use->type = USE_NONLINEAR_EXPR;
+       return;
+     }
+ 
    if (zero_p (iv->step))
      {
        record_invariant (*op_p, true);
*************** find_interesting_uses_op (tree *op_p)
*** 1860,1866 ****
    civ = xmalloc (sizeof (struct iv));
    *civ = *iv;
  
!   record_use (op_p, civ, SSA_NAME_DEF_STMT (*op_p), USE_NONLINEAR_EXPR);
  }
  
  /* Checks whether the condition *COND_P in STMT is interesting
--- 1899,1948 ----
    civ = xmalloc (sizeof (struct iv));
    *civ = *iv;
  
!   iv->use_id = record_use (op_p, civ, SSA_NAME_DEF_STMT (*op_p),
! 			   USE_NONLINEAR_EXPR)->id;
! }
! 
! /* Records a definition of induction variable *OP_P that is used outside of the
!    loop.  */
! 
! static void
! find_interesting_uses_outer (tree *op_p)
! {
!   struct iv *iv;
!   struct iv *civ;
!   tree stmt;
! 
!   if (TREE_CODE (*op_p) != SSA_NAME)
!     abort ();
! 
!   iv = get_iv (*op_p);
!   if (!iv)
!     abort ();
!   
!   if (iv->have_use_for)
!     {
!       struct iv_use *use = VARRAY_GENERIC_PTR_NOGC (iv_uses, iv->use_id);
! 
!       if (use->type != USE_NONLINEAR_EXPR
! 	  && use->type != USE_OUTER)
! 	abort ();
! 
!       return;
!     }
! 
!   if (zero_p (iv->step))
!     {
!       record_invariant (*op_p, true);
!       return;
!     }
!   iv->have_use_for = true;
! 
!   civ = xmalloc (sizeof (struct iv));
!   *civ = *iv;
! 
!   stmt = SSA_NAME_DEF_STMT (*op_p);
!   iv->use_id = record_use (op_p, civ, stmt, USE_OUTER)->id;
  }
  
  /* Checks whether the condition *COND_P in STMT is interesting
*************** find_interesting_uses_stmt (tree stmt)
*** 2071,2085 ****
  
  	  if (iv)
  	    {
! 	      /* If the variable is used outside of the loop, we must preserve it.
! 
! 		 TODO -- add posibility to replace it by the known final value,
! 		 or to express the final value using the other ivs.  */
  	      loop = name_info (lhs)->outermost_usage;
  	      if (loop
  		  && loop != current_loop
  		  && !flow_loop_nested_p (current_loop, loop))
! 		find_interesting_uses_op (&lhs);
  
  	      return;
  	    }
--- 2153,2165 ----
  
  	  if (iv)
  	    {
! 	      /* 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 (lhs)->outermost_usage;
  	      if (loop
  		  && loop != current_loop
  		  && !flow_loop_nested_p (current_loop, loop))
! 		find_interesting_uses_outer (&TREE_OPERAND (stmt, 0));
  
  	      return;
  	    }
*************** find_interesting_uses_stmt (tree stmt)
*** 2114,2128 ****
  
        if (iv)
  	{
! 	  /* If the variable is used outside of the loop, we must preserve it.
! 	     FIXME -- we do not handle this case correctly, since we just try
! 	     to replace the rhs of the phi.  */
  	      
  	  loop = name_info (lhs)->outermost_usage;
  	  if (loop
  	      && loop != current_loop
  	      && !flow_loop_nested_p (current_loop, loop))
! 	    find_interesting_uses_op (&lhs);
  
  	  return;
  	}
--- 2194,2207 ----
  
        if (iv)
  	{
! 	  /* If the variable is used outside of the loop, we must preserve it
! 	     or express the final value in other way.  */
  	      
  	  loop = name_info (lhs)->outermost_usage;
  	  if (loop
  	      && loop != current_loop
  	      && !flow_loop_nested_p (current_loop, loop))
! 	    find_interesting_uses_outer (&PHI_RESULT (stmt));
  
  	  return;
  	}
*************** find_interesting_uses (void)
*** 2202,2208 ****
  
  /* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
     position to POS.  If USE is not NULL, the candidate is set as related to
!    it.  */
  
  static struct iv_cand *
  add_candidate_1 (tree base, tree step, bool important, enum iv_position pos,
--- 2281,2288 ----
  
  /* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
     position to POS.  If USE is not NULL, the candidate is set as related to
!    it.  If both BASE and STEP are NULL, we add a pseudocandidate for the
!    replacement of the final value of the iv by a direct computation.  */
  
  static struct iv_cand *
  add_candidate_1 (tree base, tree step, bool important, enum iv_position pos,
*************** add_candidate_1 (tree base, tree step, b
*** 2221,2226 ****
--- 2301,2317 ----
        if (cand->incremented_at != incremented_at)
  	continue;
  
+       if (!cand->iv)
+ 	{
+ 	  if (!base && !step)
+ 	    break;
+ 
+ 	  continue;
+ 	}
+ 
+       if (!base && !step)
+ 	continue;
+ 
        if (!operand_equal_p (base, cand->iv->base, 0))
  	continue;
  
*************** add_candidate_1 (tree base, tree step, b
*** 2240,2248 ****
      {
        cand = xcalloc (1, sizeof (struct iv_cand));
        cand->id = i;
!       cand->iv = alloc_iv (base, step);
        cand->pos = pos;
!       if (pos != IP_ORIGINAL)
  	{
  	  cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
  	  cand->var_after = cand->var_before;
--- 2331,2344 ----
      {
        cand = xcalloc (1, sizeof (struct iv_cand));
        cand->id = i;
! 
!       if (!base && !step)
! 	cand->iv = NULL;
!       else
! 	cand->iv = alloc_iv (base, step);
! 
        cand->pos = pos;
!       if (pos != IP_ORIGINAL && cand->iv)
  	{
  	  cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
  	  cand->var_after = cand->var_before;
*************** add_address_candidates (struct iv *iv, s
*** 2394,2399 ****
--- 2490,2516 ----
      }
  }
  
+ /* Possibly adds pseudocandidate for replacing the final value of USE by
+    a direct computation.  */
+ 
+ static void
+ add_iv_outer_candidates (struct iv_use *use)
+ {
+   struct tree_niter_desc *niter;
+ 
+   /* We must know where we exit the loop and how many times does it roll.  */
+   if (!LOOP_DATA (current_loop)->single_exit)
+     return;
+ 
+   niter = &LOOP_DATA (current_loop)->niter;
+   if (!niter->niter
+       || !operand_equal_p (niter->assumptions, boolean_true_node, 0)
+       || !operand_equal_p (niter->may_be_zero, boolean_false_node, 0))
+     return;
+ 
+   add_candidate_1 (NULL, NULL, false, IP_NORMAL, use, NULL_TREE);
+ }
+ 
  /* Adds candidates based on the uses.  */
  
  static void
*************** add_derived_ivs_candidates (void)
*** 2416,2424 ****
--- 2533,2552 ----
  	  add_iv_value_candidates (use->iv, use);
  	  break;
  
+ 	case USE_OUTER:
+ 	  add_iv_value_candidates (use->iv, use);
+ 
+ 	  /* Additionally, add the pseudocandidate for the possibility to
+ 	     replace the final value by a direct computation.  */
+ 	  add_iv_outer_candidates (use);
+ 	  break;
+ 
  	case USE_ADDRESS:
  	  add_address_candidates (use->iv, use);
  	  break;
+ 
+ 	default:
+ 	  abort ();
  	}
      }
  }
*************** computation_cost (tree expr)
*** 2638,2660 ****
    return cost;
  }
  
! /* Returns variable containing the value of candidate CAND at position
!    of USE.  */
  
  static tree
! var_at_use (struct iv_use *use, struct iv_cand *cand)
  {
!   if (stmt_after_increment (cand, use->stmt))
      return cand->var_after;
    else
      return cand->var_before;
  }
  
  /* Determines the expression by that USE is expressed from induction variable
!    CAND.  */
  
  static tree
! get_computation (struct iv_use *use, struct iv_cand *cand)
  {
    tree ubase = use->iv->base, ustep = use->iv->step;
    tree cbase = cand->iv->base, cstep = cand->iv->step;
--- 2766,2787 ----
    return cost;
  }
  
! /* Returns variable containing the value of candidate CAND at statement AT.  */
  
  static tree
! var_at_stmt (struct iv_cand *cand, tree stmt)
  {
!   if (stmt_after_increment (cand, stmt))
      return cand->var_after;
    else
      return cand->var_before;
  }
  
  /* Determines the expression by that USE is expressed from induction variable
!    CAND at statement AT.  */
  
  static tree
! get_computation_at (struct iv_use *use, struct iv_cand *cand, tree at)
  {
    tree ubase = use->iv->base, ustep = use->iv->step;
    tree cbase = cand->iv->base, cstep = cand->iv->step;
*************** get_computation (struct iv_use *use, str
*** 2664,2670 ****
    unsigned HOST_WIDE_INT ustepi, cstepi;
    HOST_WIDE_INT ratioi;
  
!   expr = var_at_use (use, cand);
  
    if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
      {
--- 2791,2797 ----
    unsigned HOST_WIDE_INT ustepi, cstepi;
    HOST_WIDE_INT ratioi;
  
!   expr = var_at_stmt (cand, at);
  
    if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
      {
*************** get_computation (struct iv_use *use, str
*** 2695,2701 ****
      }
  
    /* We may need to shift the value if we are after the increment.  */
!   if (stmt_after_increment (cand, use->stmt))
      cbase = fold (build (PLUS_EXPR, utype, cbase, cstep));
  
    /* use = ubase + ratio * (var - cbase).  If either cbase is a constant
--- 2822,2828 ----
      }
  
    /* We may need to shift the value if we are after the increment.  */
!   if (stmt_after_increment (cand, at))
      cbase = fold (build (PLUS_EXPR, utype, cbase, cstep));
  
    /* use = ubase + ratio * (var - cbase).  If either cbase is a constant
*************** get_computation (struct iv_use *use, str
*** 2732,2737 ****
--- 2859,2873 ----
    return expr;
  }
  
+ /* Determines the expression by that USE is expressed from induction variable
+    CAND.  */
+ 
+ static tree
+ get_computation (struct iv_use *use, struct iv_cand *cand)
+ {
+   return get_computation_at (use, cand, use->stmt);
+ }
+ 
  /* Strips constant offsets from EXPR and adds them to OFFSET.  */
  
  static void
*************** difference_cost (tree e1, tree e2, bool 
*** 3288,3302 ****
     from induction variable CAND.  If ADDRESS_P is true, we just need
     to create an address from it, otherwise we want to get it into
     register.  A set of invariants we depend on is stored in
!    DEPENDS_ON.  */
  
  static unsigned
! get_computation_cost (struct iv_use *use, struct iv_cand *cand,
! 		      bool address_p, bitmap *depends_on)
  {
    tree ubase = use->iv->base, ustep = use->iv->step;
!   tree cbase = cand->iv->base, cstep = cand->iv->step;
!   tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
    unsigned HOST_WIDE_INT ustepi, cstepi, offset = 0;
    HOST_WIDE_INT ratio, aratio;
    bool var_present, symbol_present;
--- 3424,3438 ----
     from induction variable CAND.  If ADDRESS_P is true, we just need
     to create an address from it, otherwise we want to get it into
     register.  A set of invariants we depend on is stored in
!    DEPENDS_ON.  AT is the statement at that the value is computed.  */
  
  static unsigned
! get_computation_cost_at (struct iv_use *use, struct iv_cand *cand,
! 			 bool address_p, bitmap *depends_on, tree at)
  {
    tree ubase = use->iv->base, ustep = use->iv->step;
!   tree cbase, cstep;
!   tree utype = TREE_TYPE (ubase), ctype;
    unsigned HOST_WIDE_INT ustepi, cstepi, offset = 0;
    HOST_WIDE_INT ratio, aratio;
    bool var_present, symbol_present;
*************** get_computation_cost (struct iv_use *use
*** 3304,3309 ****
--- 3440,3453 ----
  
    *depends_on = NULL;
  
+   /* Only consider real candidates.  */
+   if (!cand->iv)
+     return INFTY;
+ 
+   cbase = cand->iv->base;
+   cstep = cand->iv->step;
+   ctype = TREE_TYPE (cbase);
+ 
    if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
      {
        /* We do not have a precision to express the values of use.  */
*************** get_computation_cost (struct iv_use *use
*** 3365,3371 ****
  
    /* If we are after the increment, the value of the candidate is higher by
       one iteration.  */
!   if (stmt_after_increment (cand, use->stmt))
      offset -= ratio * cstepi;
  
    /* Now the computation is in shape symbol + var1 + const + ratio * var2.
--- 3509,3515 ----
  
    /* If we are after the increment, the value of the candidate is higher by
       one iteration.  */
!   if (stmt_after_increment (cand, at))
      offset -= ratio * cstepi;
  
    /* Now the computation is in shape symbol + var1 + const + ratio * var2.
*************** get_computation_cost (struct iv_use *use
*** 3398,3404 ****
  fallback:
    {
      /* Just get the expression, expand it and measure the cost.  */
!     tree comp = get_computation (use, cand);
  
      if (!comp)
        return INFTY;
--- 3542,3548 ----
  fallback:
    {
      /* Just get the expression, expand it and measure the cost.  */
!     tree comp = get_computation_at (use, cand, at);
  
      if (!comp)
        return INFTY;
*************** fallback:
*** 3410,3415 ****
--- 3554,3572 ----
    }
  }
  
+ /* Determines the cost of the computation by that USE is expressed
+    from induction variable CAND.  If ADDRESS_P is true, we just need
+    to create an address from it, otherwise we want to get it into
+    register.  A set of invariants we depend on is stored in
+    DEPENDS_ON.  */
+ 
+ static unsigned
+ get_computation_cost (struct iv_use *use, struct iv_cand *cand,
+ 		      bool address_p, bitmap *depends_on)
+ {
+   return get_computation_cost_at (use, cand, address_p, depends_on, use->stmt);
+ }
+ 
  /* Determines cost of basing replacement of USE on CAND in a generic
     expression.  */
  
*************** determine_use_iv_cost_address (struct iv
*** 3433,3453 ****
    set_use_iv_cost (use, cand, cost, depends_on);
  }
  
! /* Computes value of candidate CAND at position USE in iteration NITER.  */
  
  static tree
! cand_value_at (struct iv_cand *cand, struct iv_use *use, tree niter)
  {
    tree val;
    tree type = TREE_TYPE (niter);
  
!   if (stmt_after_increment (cand, use->stmt))
      niter = fold (build (PLUS_EXPR, type, niter,
  			 convert (type, integer_one_node)));
  
!   val = fold (build (MULT_EXPR, type, cand->iv->step, niter));
! 
!   return fold (build (PLUS_EXPR, type, cand->iv->base, val));
  }
  
  /* Check whether it is possible to express the condition in USE by comparison
--- 3590,3620 ----
    set_use_iv_cost (use, cand, cost, depends_on);
  }
  
! /* Computes value of induction variable IV in iteration NITER.  */
  
  static tree
! iv_value (struct iv *iv, tree niter)
  {
    tree val;
    tree type = TREE_TYPE (niter);
  
!   val = fold (build (MULT_EXPR, type, iv->step, niter));
! 
!   return fold (build (PLUS_EXPR, type, iv->base, val));
! }
! 
! /* Computes value of candidate CAND at position AT in iteration NITER.  */
! 
! static tree
! cand_value_at (struct iv_cand *cand, tree at, tree niter)
! {
!   tree type = TREE_TYPE (niter);
! 
!   if (stmt_after_increment (cand, at))
      niter = fold (build (PLUS_EXPR, type, niter,
  			 convert (type, integer_one_node)));
  
!   return iv_value (cand->iv, niter);
  }
  
  /* Check whether it is possible to express the condition in USE by comparison
*************** may_eliminate_iv (struct iv_use *use, st
*** 3481,3487 ****
    else
      *compare = NE_EXPR;
  
!   *bound = cand_value_at (cand, use, niter->niter);
  
    return true;
  }
--- 3648,3654 ----
    else
      *compare = NE_EXPR;
  
!   *bound = cand_value_at (cand, use->stmt, niter->niter);
  
    return true;
  }
*************** determine_use_iv_cost_condition (struct 
*** 3494,3502 ****
    tree bound;
    enum tree_code compare;
  
    if (may_eliminate_iv (use, cand, &compare, &bound))
      {
!       bitmap depends_on = BITMAP_XMALLOC ();
        unsigned cost = force_var_cost (bound, &depends_on);
  
        set_use_iv_cost (use, cand, cost, depends_on);
--- 3661,3676 ----
    tree bound;
    enum tree_code compare;
  
+   /* Only consider real candidates.  */
+   if (!cand->iv)
+     {
+       set_use_iv_cost (use, cand, INFTY, NULL);
+       return;
+     }
+ 
    if (may_eliminate_iv (use, cand, &compare, &bound))
      {
!       bitmap depends_on = NULL;
        unsigned cost = force_var_cost (bound, &depends_on);
  
        set_use_iv_cost (use, cand, cost, depends_on);
*************** determine_use_iv_cost_condition (struct 
*** 3517,3522 ****
--- 3691,3769 ----
    determine_use_iv_cost_generic (use, cand);
  }
  
+ /* Checks whether it is possible to replace the final value of USE by
+    a direct computation.  If so, the formula is stored to *VALUE.  */
+ 
+ static bool
+ may_replace_final_value (struct iv_use *use, tree *value)
+ {
+   edge exit;
+   struct tree_niter_desc *niter;
+ 
+   exit = LOOP_DATA (current_loop)->single_exit;
+   if (!exit)
+     return false;
+ 
+   if (!dominated_by_p (CDI_DOMINATORS, exit->src,
+ 		       bb_for_stmt (use->stmt)))
+     abort ();
+ 
+   niter = &LOOP_DATA (current_loop)->niter;
+   if (!niter->niter
+       || !operand_equal_p (niter->assumptions, boolean_true_node, 0)
+       || !operand_equal_p (niter->may_be_zero, boolean_false_node, 0))
+     return false;
+ 
+   *value = iv_value (use->iv, niter->niter);
+ 
+   return true;
+ }
+ 
+ /* Determines cost of replacing final value of USE using CAND.  */
+ 
+ static void
+ determine_use_iv_cost_outer (struct iv_use *use, struct iv_cand *cand)
+ {
+   bitmap depends_on;
+   unsigned cost;
+   edge exit;
+   tree value;
+ 	  
+   if (!cand->iv)
+     {
+       if (!may_replace_final_value (use, &value))
+ 	{
+ 	  set_use_iv_cost (use, cand, INFTY, NULL);
+ 	  return;
+ 	}
+ 
+       depends_on = NULL;
+       cost = force_var_cost (value, &depends_on);
+ 
+       cost /= AVG_LOOP_NITER (current_loop);
+ 
+       set_use_iv_cost (use, cand, cost, depends_on);
+       return;
+     }
+ 
+   exit = LOOP_DATA (current_loop)->single_exit;
+   if (exit)
+     {
+       /* If there is just a single exit, we may use value of the candidate
+ 	 after we take it to determine the value of use.  */
+       cost = get_computation_cost_at (use, cand, false, &depends_on,
+ 				      last_stmt (exit->src));
+       cost /= AVG_LOOP_NITER (current_loop);
+     }
+   else
+     {
+       /* Otherwise we just need to compute the iv.  */
+       cost = get_computation_cost (use, cand, false, &depends_on);
+     }
+ 				   
+   set_use_iv_cost (use, cand, cost, depends_on);
+ }
+ 
  /* Determines cost of basing replacement of USE on CAND.  */
  
  static void
*************** determine_use_iv_cost (struct iv_use *us
*** 3528,3533 ****
--- 3775,3784 ----
        determine_use_iv_cost_generic (use, cand);
        break;
  
+     case USE_OUTER:
+       determine_use_iv_cost_outer (use, cand);
+       break;
+ 
      case USE_ADDRESS:
        determine_use_iv_cost_address (use, cand);
        break;
*************** static void
*** 3628,3644 ****
  determine_iv_cost (struct iv_cand *cand)
  {
    unsigned cost_base, cost_step;
!   tree base = cand->iv->base;
  
    /* There are two costs associated with the candidate -- its incrementation
       and its initialization.  The second is almost negligible for any loop
       that rolls enough, so we take it just very little into account.  */
  
    cost_base = force_var_cost (base, NULL);
    cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
  
!   /* TODO use profile to determine the ratio here.  */
!   cand->cost = cost_step + cost_base / 5;
  
    /* Prefer the original iv unless we may gain something by replacing it.  */
    if (cand->pos == IP_ORIGINAL)
--- 3879,3901 ----
  determine_iv_cost (struct iv_cand *cand)
  {
    unsigned cost_base, cost_step;
!   tree base;
! 
!   if (!cand->iv)
!     {
!       cand->cost = 0;
!       return;
!     }
  
    /* There are two costs associated with the candidate -- its incrementation
       and its initialization.  The second is almost negligible for any loop
       that rolls enough, so we take it just very little into account.  */
  
+   base = cand->iv->base;
    cost_base = force_var_cost (base, NULL);
    cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
  
!   cand->cost = cost_step + cost_base / AVG_LOOP_NITER (current_loop);
  
    /* Prefer the original iv unless we may gain something by replacing it.  */
    if (cand->pos == IP_ORIGINAL)
*************** set_cost (bitmap sol, bitmap inv)
*** 3893,3900 ****
  
    EXECUTE_IF_SET_IN_BITMAP (used_ivs, 0, i,
      {
-       size++;
        cand = VARRAY_GENERIC_PTR_NOGC (iv_candidates, i);
        cost += cand->cost;
      });
    EXECUTE_IF_SET_IN_BITMAP (used_inv, 0, i, size++);
--- 4150,4161 ----
  
    EXECUTE_IF_SET_IN_BITMAP (used_ivs, 0, i,
      {
        cand = VARRAY_GENERIC_PTR_NOGC (iv_candidates, i);
+ 
+       /* Do not count the pseudocandidates.  */
+       if (cand->iv)
+ 	size++;
+ 
        cost += cand->cost;
      });
    EXECUTE_IF_SET_IN_BITMAP (used_inv, 0, i, size++);
*************** create_new_iv (struct iv_cand *cand)
*** 4127,4132 ****
--- 4388,4396 ----
    tree base;
    bool after = false;
  
+   if (!cand->iv)
+     return;
+ 
    switch (cand->pos)
      {
  #if DISABLE_IP_START
*************** create_new_iv (struct iv_cand *cand)
*** 4153,4159 ****
        break;
  
      case IP_ORIGINAL:
!       /* Nothing to do here.  */
        return;
      }
   
--- 4417,4425 ----
        break;
  
      case IP_ORIGINAL:
!       /* Mark that the iv is preserved.  */
!       name_info (cand->var_before)->preserve_biv = true;
!       name_info (cand->var_after)->preserve_biv = true;
        return;
      }
   
*************** create_new_ivs (bitmap set)
*** 4181,4186 ****
--- 4447,4471 ----
      });
  }
  
+ /* Removes statement STMT (real or a phi node).  */
+ 
+ static void
+ remove_statement (tree stmt)
+ {
+   if (TREE_CODE (stmt) == PHI_NODE)
+     {
+       /* Prevent the ssa name defined by the statement from being removed.  */
+       PHI_RESULT (stmt) = NULL;
+       remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
+     }
+   else
+     {
+       block_stmt_iterator bsi = stmt_bsi (stmt);
+ 
+       bsi_remove (&bsi);
+     }
+ }
+ 
  /* Rewrites USE (definition of iv used in a nonlinear expression)
     using candidate CAND.  */
  
*************** static void
*** 4188,4210 ****
  rewrite_use_nonlinear_expr (struct iv_use *use, struct iv_cand *cand)
  {
    tree comp = unshare_expr (get_computation (use, cand));
!   tree op, stmts;
!   block_stmt_iterator bsi;
   
    if (TREE_CODE (use->stmt) == PHI_NODE)
      {
!       /* TODO -- handle rewriting of the phi node.  This may only occur when
! 	 the result of the phi node is used outside of the loop.  */
!       return;
      }
  
!   bsi = stmt_bsi (use->stmt);
!   op = force_gimple_operand (comp, &stmts,
! 			     SSA_NAME_VAR (TREE_OPERAND (use->stmt, 0)),
! 			     false);
!   if (stmts)
!     bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
!   TREE_OPERAND (use->stmt, 1) = op;
  }
  
  /* Rewrites USE (address that is an iv) using candidate CAND.  */
--- 4473,4520 ----
  rewrite_use_nonlinear_expr (struct iv_use *use, struct iv_cand *cand)
  {
    tree comp = unshare_expr (get_computation (use, cand));
!   tree op, stmts, tgt, ass;
!   block_stmt_iterator bsi, pbsi;
   
    if (TREE_CODE (use->stmt) == PHI_NODE)
      {
!       tgt = PHI_RESULT (use->stmt);
! 
!       /* If we should keep the biv, do not replace it.  */
!       if (name_info (tgt)->preserve_biv)
! 	return;
! 
!       pbsi = bsi = bsi_start (bb_for_stmt (use->stmt));
!       while (!bsi_end_p (pbsi)
! 	     && TREE_CODE (bsi_stmt (pbsi)) == LABEL_EXPR)
! 	{
! 	  bsi = pbsi;
! 	  bsi_next (&pbsi);
! 	}
!     }
!   else
!     {
!       tgt = TREE_OPERAND (use->stmt, 0);
!       bsi = stmt_bsi (use->stmt);
      }
  
!   op = force_gimple_operand (comp, &stmts, SSA_NAME_VAR (tgt), false);
! 
!   if (TREE_CODE (use->stmt) == PHI_NODE)
!     {
!       if (stmts)
! 	bsi_insert_after (&bsi, stmts, BSI_CONTINUE_LINKING);
!       ass = build (MODIFY_EXPR, TREE_TYPE (tgt), tgt, op);
!       bsi_insert_after (&bsi, ass, BSI_NEW_STMT);
!       remove_statement (use->stmt);
!       SSA_NAME_DEF_STMT (tgt) = ass;
!     }
!   else
!     {
!       if (stmts)
! 	bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
!       TREE_OPERAND (use->stmt, 1) = op;
!     }
  }
  
  /* Rewrites USE (address that is an iv) using candidate CAND.  */
*************** rewrite_use_compare (struct iv_use *use,
*** 4273,4279 ****
  	bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
  
        *use->op_p = build (compare, boolean_type_node,
! 			  var_at_use (use, cand), op);
        modify_stmt (use->stmt);
        return;
      }
--- 4583,4589 ----
  	bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
  
        *use->op_p = build (compare, boolean_type_node,
! 			  var_at_stmt (cand, use->stmt), op);
        modify_stmt (use->stmt);
        return;
      }
*************** rewrite_use_compare (struct iv_use *use,
*** 4295,4300 ****
--- 4605,4652 ----
    *op_p = op;
  }
  
+ /* Rewrites the final value of USE (that is only needed outside of the loop)
+    using candidate CAND.  */
+ 
+ static void
+ rewrite_use_outer (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 (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 (tgt)->preserve_biv)
+     return;
+ 
+   if (exit)
+     {
+       if (!cand->iv)
+ 	{
+ 	  if (!may_replace_final_value (use, &value))
+ 	    abort ();
+ 	}
+       else
+ 	value = get_computation_at (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);
+       SSA_NAME_DEF_STMT (tgt) = ass;
+       return;
+     }
+ 
+   /* Otherwise we just need to compute the iv.  */
+   rewrite_use_nonlinear_expr (use, cand);
+ }
+ 
  /* Rewrites USE using candidate CAND.  */
  
  static void
*************** rewrite_use (struct iv_use *use, struct 
*** 4306,4311 ****
--- 4658,4667 ----
  	rewrite_use_nonlinear_expr (use, cand);
  	break;
  
+       case USE_OUTER:
+ 	rewrite_use_outer (use, cand);
+ 	break;
+ 
        case USE_ADDRESS:
  	rewrite_use_address (use, cand);
  	break;
*************** rewrite_use (struct iv_use *use, struct 
*** 4313,4318 ****
--- 4669,4677 ----
        case USE_COMPARE:
  	rewrite_use_compare (use, cand);
  	break;
+ 
+       default:
+ 	abort ();
      }
    modify_stmt (use->stmt);
  }
*************** free_loop_data (void)
*** 4353,4358 ****
--- 4712,4718 ----
  	free (info->iv);
        info->iv = NULL;
        info->has_nonlin_use = false;
+       info->preserve_biv = false;
        info->inv_id = 0;
      });
    bitmap_clear (relevant);
*************** free_loop_data (void)
*** 4375,4381 ****
      {
        struct iv_cand *cand = VARRAY_GENERIC_PTR_NOGC (iv_candidates, i);
  
!       free (cand->iv);
        free (cand);
      }
    VARRAY_POP_ALL (iv_candidates);
--- 4735,4742 ----
      {
        struct iv_cand *cand = VARRAY_GENERIC_PTR_NOGC (iv_candidates, i);
  
!       if (cand->iv)
! 	free (cand->iv);
        free (cand);
      }
    VARRAY_POP_ALL (iv_candidates);
*************** tree_ssa_iv_optimize_loop (struct loop *
*** 4475,4480 ****
--- 4836,4842 ----
    
    /* Rewrite the uses (item 4, part 2).  */
    rewrite_uses ();
+   loop_commit_inserts ();
  
    BITMAP_XFREE (iv_set);
  finish:
Index: tree-ssanames.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssanames.c,v
retrieving revision 1.1.2.6.2.1
diff -c -3 -p -r1.1.2.6.2.1 tree-ssanames.c
*** tree-ssanames.c	25 Jan 2004 20:20:16 -0000	1.1.2.6.2.1
--- tree-ssanames.c	18 Mar 2004 21:26:24 -0000
*************** make_ssa_name (tree var, tree stmt)
*** 167,172 ****
--- 167,175 ----
  void
  release_ssa_name (tree var)
  {
+   if (!var)
+     return;
+ 
    /* release_ssa_name can be called multiple times on a single SSA_NAME.
       However, it should only end up on our free list one time.   We
       keep a status bit in the SSA_NAME node itself to indicate it has


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