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]

[patch] for PR 18687


Hello,

part of the problems in this PR is caused by ivopts using # of
iterations anlaysis inefficiently.  During iv elimination, we

1) repeatedly ask for the number of iterations of the loop.
   This is solved by caching the results we get (this part of the
   patch was previously posted in
   http://gcc.gnu.org/ml/gcc-patches/2004-10/msg00136.html).

2) call number_of_iterations_cond just to verify that the period of the
   variable that we plan to use to control the loop is not smaller than
   the number of iterations of the loop (in this case we of course
   cannot perform the iv elimination using this iv).
   This is a terrible overkill, checking the condition directly is much
   more efficient.

Bootstrapped & regtested on i686 and amd64.

Zdenek

	PR tree-optimization/18687
	* tree-flow.h (find_loop_niter): Declare.
	* tree-ssa-loop-ivcanon.c (canonicalize_loop_induction_variables):
	Try using scev even for loops with more than one exit.
	* tree-ssa-loop-ivopts.c (struct loop_data): Removed niter field.
	(struct ivopts_data): Added niters field.
	(struct nfe_cache_elt): New.
	(nfe_hash, nfe_eq, niter_for_exit, niter_for_single_dom_exit): New
	functions.
	(tree_ssa_iv_optimize_init): Initialize niters cache.
	(determine_number_of_iterations): Removed.
	(find_induction_variables): Do not call determine_number_of_iterations.
	Access niters for single exit through niter_for_single_dom_exit.
	(add_iv_outer_candidates): Access niters for single exit through
	niter_for_single_dom_exit.
	(may_eliminate_iv): Take data argument.  Use niter_for_exit.  Do not use
	number_of_iterations_cond.
	(iv_period): New function.
	(determine_use_iv_cost_condition): Pass data to may_eliminate_iv.
	(may_replace_final_value): Take data argument.  Use
	niter_for_single_dom_exit.
	(determine_use_iv_cost_outer): Pass data to may_replace_final_value.
	(rewrite_use_compare): Pass data to may_eliminate_iv.
	(rewrite_use_outer): Pass data to may_replace_final_value.
	(free_loop_data): Clean up the niters cache.
	(tree_ssa_iv_optimize_finalize): Free the niters cache.
	(tree_ssa_iv_optimize_loop): Do not call loop_commit_inserts.
	* tree-ssa-loop-niter.c (find_loop_niter): New function.
	(find_loop_niter_by_eval): Use tree_int_cst_lt.
	(num_ending_zeros): Moved to tree.c.
	* tree.h (num_ending_zeros): Declare.
	* tree.c (num_ending_zeros): Moved from tree.c.

Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.80
diff -c -3 -p -r2.80 tree-flow.h
*** tree-flow.h	2 Feb 2005 20:56:16 -0000	2.80
--- tree-flow.h	8 Feb 2005 01:43:10 -0000
*************** void number_of_iterations_cond (tree, tr
*** 667,672 ****
--- 667,673 ----
  				struct tree_niter_desc *);
  bool number_of_iterations_exit (struct loop *, edge,
  				struct tree_niter_desc *niter);
+ tree find_loop_niter (struct loop *, edge *);
  tree loop_niter_by_eval (struct loop *, edge);
  tree find_loop_niter_by_eval (struct loop *, edge *);
  void estimate_numbers_of_iterations (struct loops *);
Index: tree-ssa-loop-ivcanon.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivcanon.c,v
retrieving revision 2.5
diff -c -3 -p -r2.5 tree-ssa-loop-ivcanon.c
*** tree-ssa-loop-ivcanon.c	1 Oct 2004 18:26:31 -0000	2.5
--- tree-ssa-loop-ivcanon.c	8 Feb 2005 01:43:10 -0000
*************** canonicalize_loop_induction_variables (s
*** 220,231 ****
        niter = fold (build2 (MINUS_EXPR, TREE_TYPE (niter), niter,
  			    build_int_cst (TREE_TYPE (niter), 1)));
      }
!   else if (try_eval)
!     niter = find_loop_niter_by_eval (loop, &exit);
! 
!   if (chrec_contains_undetermined (niter)
!       || TREE_CODE (niter) != INTEGER_CST)
!     return false;
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
--- 220,242 ----
        niter = fold (build2 (MINUS_EXPR, TREE_TYPE (niter), niter,
  			    build_int_cst (TREE_TYPE (niter), 1)));
      }
!   else
!     {
!       /* If the loop has more than one exit, try checking all of them
! 	 for # of iterations determinable through scev.  */
!       if (!loop->single_exit)
! 	niter = find_loop_niter (loop, &exit);
! 
!       /* Finally if everything else fails, try brute force evaluation.  */
!       if (try_eval
! 	  && (chrec_contains_undetermined (niter)
! 	      || TREE_CODE (niter) != INTEGER_CST))
! 	niter = find_loop_niter_by_eval (loop, &exit);
! 
!       if (chrec_contains_undetermined (niter)
! 	  || TREE_CODE (niter) != INTEGER_CST)
! 	return false;
!     }
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.44
diff -c -3 -p -r2.44 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c	6 Feb 2005 18:48:58 -0000	2.44
--- tree-ssa-loop-ivopts.c	8 Feb 2005 01:43:10 -0000
*************** struct version_info
*** 123,131 ****
  /* Information attached to loop.  */
  struct loop_data
  {
-   struct tree_niter_desc niter;
- 			/* Number of iterations.  */
- 
    unsigned regs_used;	/* Number of registers used.  */
  };
  
--- 123,128 ----
*************** struct ivopts_data
*** 199,204 ****
--- 196,204 ----
    /* The currently optimized loop.  */
    struct loop *current_loop;
  
+   /* Numbers of iterations for all exits of the current loop.  */
+   htab_t niters;
+ 
    /* The size of version_info array allocated.  */
    unsigned version_info_size;
  
*************** stmt_after_increment (struct loop *loop,
*** 639,644 ****
--- 639,724 ----
      }
  }
  
+ /* Element of the table in that we cache the numbers of iterations obtained
+    from exits of the loop.  */
+ 
+ struct nfe_cache_elt
+ {
+   /* The edge for that the number of iterations is cached.  */
+   edge exit;
+ 
+   /* True if the # of iterations was succesfully determined.  */
+   bool valid_p;
+ 
+   /* Description of # of iterations.  */
+   struct tree_niter_desc niter;
+ };
+ 
+ /* Hash function for nfe_cache_elt E.  */
+ 
+ static hashval_t
+ nfe_hash (const void *e)
+ {
+   const struct nfe_cache_elt *elt = e;
+ 
+   return htab_hash_pointer (elt->exit);
+ }
+ 
+ /* Equality function for nfe_cache_elt E1 and edge E2.  */
+ 
+ static int
+ nfe_eq (const void *e1, const void *e2)
+ {
+   const struct nfe_cache_elt *elt1 = e1;
+ 
+   return elt1->exit == e2;
+ }
+ 
+ /*  Returns structure describing number of iterations determined from
+     EXIT of DATA->current_loop, or NULL if something goes wrong.  */
+ 
+ static struct tree_niter_desc *
+ niter_for_exit (struct ivopts_data *data, edge exit)
+ {
+   struct nfe_cache_elt *nfe_desc;
+   PTR *slot;
+ 
+   slot = htab_find_slot_with_hash (data->niters, exit,
+ 				   htab_hash_pointer (exit),
+ 				   INSERT);
+ 
+   if (!*slot)
+     {
+       nfe_desc = xmalloc (sizeof (struct nfe_cache_elt));
+       nfe_desc->exit = exit;
+       nfe_desc->valid_p = number_of_iterations_exit (data->current_loop,
+ 						     exit, &nfe_desc->niter);
+       *slot = nfe_desc;
+     }
+   else
+     nfe_desc = *slot;
+ 
+   if (!nfe_desc->valid_p)
+     return NULL;
+ 
+   return &nfe_desc->niter;
+ }
+ 
+ /* Returns structure describing number of iterations determined from
+    single dominating exit of DATA->current_loop, or NULL if something
+    goes wrong.  */
+ 
+ static struct tree_niter_desc *
+ niter_for_single_dom_exit (struct ivopts_data *data)
+ {
+   edge exit = single_dom_exit (data->current_loop);
+ 
+   if (!exit)
+     return NULL;
+ 
+   return niter_for_exit (data, exit);
+ }
+ 
  /* Initializes data structures used by the iv optimization pass, stored
     in DATA.  LOOPS is the loop tree.  */
  
*************** tree_ssa_iv_optimize_init (struct loops 
*** 653,658 ****
--- 733,739 ----
    data->relevant = BITMAP_XMALLOC ();
    data->important_candidates = BITMAP_XMALLOC ();
    data->max_inv_id = 0;
+   data->niters = htab_create (10, nfe_hash, nfe_eq, free);
  
    for (i = 1; i < loops->num; i++)
      if (loops->parray[i])
*************** find_givs (struct ivopts_data *data)
*** 1009,1028 ****
    free (body);
  }
  
- /* Determine the number of iterations of the current loop.  */
- 
- static void
- determine_number_of_iterations (struct ivopts_data *data)
- {
-   struct loop *loop = data->current_loop;
-   edge exit = single_dom_exit (loop);
- 
-   if (!exit)
-     return;
- 
-   number_of_iterations_exit (loop, exit, &loop_data (loop)->niter);
- }
- 
  /* For each ssa name defined in LOOP determines whether it is an induction
     variable and if so, its initial value and step.  */
  
--- 1090,1095 ----
*************** static bool
*** 1030,1036 ****
  find_induction_variables (struct ivopts_data *data)
  {
    unsigned i;
-   struct loop *loop = data->current_loop;
    bitmap_iterator bi;
  
    if (!find_bivs (data))
--- 1097,1102 ----
*************** find_induction_variables (struct ivopts_
*** 1038,1062 ****
  
    find_givs (data);
    mark_bivs (data);
-   determine_number_of_iterations (data);
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
!       if (loop_data (loop)->niter.niter)
  	{
  	  fprintf (dump_file, "  number of iterations ");
! 	  print_generic_expr (dump_file, loop_data (loop)->niter.niter,
! 			      TDF_SLIM);
  	  fprintf (dump_file, "\n");
  
      	  fprintf (dump_file, "  may be zero if ");
!     	  print_generic_expr (dump_file, loop_data (loop)->niter.may_be_zero,
!     			      TDF_SLIM);
!     	  fprintf (dump_file, "\n");
! 
!     	  fprintf (dump_file, "  bogus unless ");
!     	  print_generic_expr (dump_file, loop_data (loop)->niter.assumptions,
!     			      TDF_SLIM);
      	  fprintf (dump_file, "\n");
      	  fprintf (dump_file, "\n");
      	};
--- 1104,1124 ----
  
    find_givs (data);
    mark_bivs (data);
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
!       struct tree_niter_desc *niter;
! 
!       niter = niter_for_single_dom_exit (data);
! 
!       if (niter)
  	{
  	  fprintf (dump_file, "  number of iterations ");
! 	  print_generic_expr (dump_file, niter->niter, TDF_SLIM);
  	  fprintf (dump_file, "\n");
  
      	  fprintf (dump_file, "  may be zero if ");
!     	  print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
      	  fprintf (dump_file, "\n");
      	  fprintf (dump_file, "\n");
      	};
*************** static void
*** 1958,1973 ****
  add_iv_outer_candidates (struct ivopts_data *data, struct iv_use *use)
  {
    struct tree_niter_desc *niter;
-   struct loop *loop = data->current_loop;
  
    /* We must know where we exit the loop and how many times does it roll.  */
!   if (!single_dom_exit (loop))
!     return;
! 
!   niter = &loop_data (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 (data, NULL, NULL, false, IP_NORMAL, use, NULL_TREE);
--- 2020,2030 ----
  add_iv_outer_candidates (struct ivopts_data *data, struct iv_use *use)
  {
    struct tree_niter_desc *niter;
  
    /* We must know where we exit the loop and how many times does it roll.  */
!   niter = niter_for_single_dom_exit (data);
!   if (!niter
!       || !zero_p (niter->may_be_zero))
      return;
  
    add_candidate_1 (data, NULL, NULL, false, IP_NORMAL, use, NULL_TREE);
*************** cand_value_at (struct loop *loop, struct
*** 3233,3251 ****
    return val;
  }
  
  /* Check whether it is possible to express the condition in USE by comparison
     of candidate CAND.  If so, store the comparison code to COMPARE and the
     value compared with to BOUND.  */
  
  static bool
! may_eliminate_iv (struct loop *loop,
  		  struct iv_use *use, struct iv_cand *cand,
  		  enum tree_code *compare, tree *bound)
  {
    basic_block ex_bb;
    edge exit;
!   struct tree_niter_desc niter, new_niter;
!   tree wider_type, type, base;
    
    /* For now works only for exits that dominate the loop latch.  TODO -- extend
       for other conditions inside loop body.  */
--- 3290,3333 ----
    return val;
  }
  
+ /* Returns period of induction variable iv.  */
+ 
+ static tree
+ iv_period (struct iv *iv)
+ {
+   tree step = iv->step, period, type;
+   tree pow2div;
+ 
+   gcc_assert (step && TREE_CODE (step) == INTEGER_CST);
+ 
+   /* Period of the iv is gcd (step, type range).  Since type range is power
+      of two, it suffices to determine the maximum power of two that divides
+      step.  */
+   pow2div = num_ending_zeros (step);
+   type = unsigned_type_for (TREE_TYPE (step));
+ 
+   period = build_low_bits_mask (type,
+ 				(TYPE_PRECISION (type)
+ 				 - tree_low_cst (pow2div, 1)));
+ 
+   return period;
+ }
+ 
  /* Check whether it is possible to express the condition in USE by comparison
     of candidate CAND.  If so, store the comparison code to COMPARE and the
     value compared with to BOUND.  */
  
  static bool
! may_eliminate_iv (struct ivopts_data *data,
  		  struct iv_use *use, struct iv_cand *cand,
  		  enum tree_code *compare, tree *bound)
  {
    basic_block ex_bb;
    edge exit;
!   struct tree_niter_desc *niter;
!   tree nit, nit_type;
!   tree wider_type, period, per_type;
!   struct loop *loop = data->current_loop;
    
    /* For now works only for exits that dominate the loop latch.  TODO -- extend
       for other conditions inside loop body.  */
*************** may_eliminate_iv (struct loop *loop,
*** 3262,3304 ****
    if (flow_bb_inside_loop_p (loop, exit->dest))
      return false;
  
!   niter.niter = NULL_TREE;
!   number_of_iterations_exit (loop, exit, &niter);
!   if (!niter.niter
!       || !integer_nonzerop (niter.assumptions)
!       || !integer_zerop (niter.may_be_zero))
      return false;
  
!   if (exit->flags & EDGE_TRUE_VALUE)
!     *compare = EQ_EXPR;
!   else
!     *compare = NE_EXPR;
! 
!   *bound = cand_value_at (loop, cand, use->stmt, niter.niter);
  
!   /* Let us check there is not some problem with overflows, by checking that
!      the number of iterations is unchanged.  */
!   base = cand->iv->base;
!   type = TREE_TYPE (base);
!   if (stmt_after_increment (loop, cand, use->stmt))
!     base = fold (build2 (PLUS_EXPR, type, base, cand->iv->step));
! 
!   new_niter.niter = NULL_TREE;
!   number_of_iterations_cond (TREE_TYPE (cand->iv->base), base,
! 			     cand->iv->step, NE_EXPR, *bound, NULL_TREE,
! 			     &new_niter);
!   if (!new_niter.niter
!       || !integer_nonzerop (new_niter.assumptions)
!       || !integer_zerop (new_niter.may_be_zero))
      return false;
  
!   wider_type = TREE_TYPE (new_niter.niter);
!   if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (TREE_TYPE (niter.niter)))
!     wider_type = TREE_TYPE (niter.niter);
!   if (!operand_equal_p (fold_convert (wider_type, niter.niter),
! 			fold_convert (wider_type, new_niter.niter), 0))
      return false;
  
    return true;
  }
  
--- 3344,3382 ----
    if (flow_bb_inside_loop_p (loop, exit->dest))
      return false;
  
!   niter = niter_for_exit (data, exit);
!   if (!niter
!       || !zero_p (niter->may_be_zero))
      return false;
  
!   nit = niter->niter;
!   nit_type = TREE_TYPE (nit);
  
!   /* Determine whether we may use the variable to test whether niter iterations
!      elapsed.  This is the case iff the period of the induction variable is
!      greater than the number of iterations.  */
!   period = iv_period (cand->iv);
!   if (!period)
      return false;
+   per_type = TREE_TYPE (period);
+ 
+   wider_type = TREE_TYPE (period);
+   if (TYPE_PRECISION (nit_type) < TYPE_PRECISION (per_type))
+     wider_type = per_type;
+   else
+     wider_type = nit_type;
  
!   if (!integer_nonzerop (fold (build2 (GE_EXPR, boolean_type_node,
! 				       fold_convert (wider_type, period),
! 				       fold_convert (wider_type, nit)))))
      return false;
  
+   if (exit->flags & EDGE_TRUE_VALUE)
+     *compare = EQ_EXPR;
+   else
+     *compare = NE_EXPR;
+ 
+   *bound = cand_value_at (loop, cand, use->stmt, nit);
    return true;
  }
  
*************** determine_use_iv_cost_condition (struct 
*** 3318,3324 ****
        return false;
      }
  
!   if (may_eliminate_iv (data->current_loop, use, cand, &compare, &bound))
      {
        bitmap depends_on = NULL;
        unsigned cost = force_var_cost (data, bound, &depends_on);
--- 3396,3402 ----
        return false;
      }
  
!   if (may_eliminate_iv (data, use, cand, &compare, &bound))
      {
        bitmap depends_on = NULL;
        unsigned cost = force_var_cost (data, bound, &depends_on);
*************** determine_use_iv_cost_condition (struct 
*** 3345,3352 ****
     a direct computation.  If so, the formula is stored to *VALUE.  */
  
  static bool
! may_replace_final_value (struct loop *loop, struct iv_use *use, tree *value)
  {
    edge exit;
    struct tree_niter_desc *niter;
  
--- 3423,3432 ----
     a direct computation.  If so, the formula is stored to *VALUE.  */
  
  static bool
! may_replace_final_value (struct ivopts_data *data, struct iv_use *use,
! 			 tree *value)
  {
+   struct loop *loop = data->current_loop;
    edge exit;
    struct tree_niter_desc *niter;
  
*************** may_replace_final_value (struct loop *lo
*** 3357,3366 ****
    gcc_assert (dominated_by_p (CDI_DOMINATORS, exit->src,
  			      bb_for_stmt (use->stmt)));
  
!   niter = &loop_data (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);
--- 3437,3445 ----
    gcc_assert (dominated_by_p (CDI_DOMINATORS, exit->src,
  			      bb_for_stmt (use->stmt)));
  
!   niter = niter_for_single_dom_exit (data);
!   if (!niter
!       || !zero_p (niter->may_be_zero))
      return false;
  
    *value = iv_value (use->iv, niter->niter);
*************** determine_use_iv_cost_outer (struct ivop
*** 3393,3399 ****
  
    if (!cand->iv)
      {
!       if (!may_replace_final_value (loop, use, &value))
  	{
  	  set_use_iv_cost (data, use, cand, INFTY, NULL);
  	  return false;
--- 3472,3478 ----
  
    if (!cand->iv)
      {
!       if (!may_replace_final_value (data, use, &value))
  	{
  	  set_use_iv_cost (data, use, cand, INFTY, NULL);
  	  return false;
*************** rewrite_use_compare (struct ivopts_data 
*** 4749,4756 ****
    block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
    enum tree_code compare;
    
!   if (may_eliminate_iv (data->current_loop,
! 			use, cand, &compare, &bound))
      {
        op = force_gimple_operand (unshare_expr (bound), &stmts,
  				 true, NULL_TREE);
--- 4828,4834 ----
    block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
    enum tree_code compare;
    
!   if (may_eliminate_iv (data, use, cand, &compare, &bound))
      {
        op = force_gimple_operand (unshare_expr (bound), &stmts,
  				 true, NULL_TREE);
*************** rewrite_use_outer (struct ivopts_data *d
*** 4924,4930 ****
      {
        if (!cand->iv)
  	{
! 	  bool ok = may_replace_final_value (data->current_loop, use, &value);
  	  gcc_assert (ok);
  	}
        else
--- 5002,5008 ----
      {
        if (!cand->iv)
  	{
! 	  bool ok = may_replace_final_value (data, use, &value);
  	  gcc_assert (ok);
  	}
        else
*************** free_loop_data (struct ivopts_data *data
*** 5045,5050 ****
--- 5123,5130 ----
    unsigned i, j;
    bitmap_iterator bi;
  
+   htab_empty (data->niters);
+ 
    EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
      {
        struct version_info *info;
*************** tree_ssa_iv_optimize_finalize (struct lo
*** 5122,5127 ****
--- 5202,5208 ----
    free (data->version_info);
    BITMAP_XFREE (data->relevant);
    BITMAP_XFREE (data->important_candidates);
+   htab_delete (data->niters);
  
    VARRAY_FREE (decl_rtl_to_reset);
    VARRAY_FREE (data->iv_uses);
*************** tree_ssa_iv_optimize_loop (struct ivopts
*** 5189,5196 ****
    /* Remove the ivs that are unused after rewriting.  */
    remove_unused_ivs (data);
  
-   loop_commit_inserts ();
- 
    /* We have changed the structure of induction variables; it might happen
       that definitions in the scev database refer to some of them that were
       eliminated.  */
--- 5270,5275 ----
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.18
diff -c -3 -p -r2.18 tree-ssa-loop-niter.c
*** tree-ssa-loop-niter.c	23 Nov 2004 01:27:42 -0000	2.18
--- tree-ssa-loop-niter.c	8 Feb 2005 01:43:10 -0000
*************** nonzero_p (tree arg)
*** 80,123 ****
    return (TREE_INT_CST_LOW (arg) != 0 || TREE_INT_CST_HIGH (arg) != 0);
  }
  
- /* Returns number of zeros at the end of binary representation of X.
-    
-    ??? Use ffs if available?  */
- 
- static tree
- num_ending_zeros (tree x)
- {
-   unsigned HOST_WIDE_INT fr, nfr;
-   unsigned num, abits;
-   tree type = TREE_TYPE (x);
- 
-   if (TREE_INT_CST_LOW (x) == 0)
-     {
-       num = HOST_BITS_PER_WIDE_INT;
-       fr = TREE_INT_CST_HIGH (x);
-     }
-   else
-     {
-       num = 0;
-       fr = TREE_INT_CST_LOW (x);
-     }
- 
-   for (abits = HOST_BITS_PER_WIDE_INT / 2; abits; abits /= 2)
-     {
-       nfr = fr >> abits;
-       if (nfr << abits == fr)
- 	{
- 	  num += abits;
- 	  fr = nfr;
- 	}
-     }
- 
-   if (num > TYPE_PRECISION (type))
-     num = TYPE_PRECISION (type);
- 
-   return build_int_cst_type (type, num);
- }
- 
  /* Returns inverse of X modulo 2^s, where MASK = 2^s-1.  */
  
  static tree
--- 80,85 ----
*************** number_of_iterations_exit (struct loop *
*** 823,828 ****
--- 785,859 ----
    return integer_onep (niter->assumptions);
  }
  
+ /* Try to determine the number of iterations of LOOP.  If we succeed,
+    expression giving number of iterations is returned and *EXIT is
+    set to the edge from that the information is obtained.  Otherwise
+    chrec_dont_know is returned.  */
+ 
+ tree
+ find_loop_niter (struct loop *loop, edge *exit)
+ {
+   unsigned n_exits, i;
+   edge *exits = get_loop_exit_edges (loop, &n_exits);
+   edge ex;
+   tree niter = NULL_TREE, aniter;
+   struct tree_niter_desc desc;
+ 
+   *exit = NULL;
+   for (i = 0; i < n_exits; i++)
+     {
+       ex = exits[i];
+       if (!just_once_each_iteration_p (loop, ex->src))
+ 	continue;
+ 
+       if (!number_of_iterations_exit (loop, ex, &desc))
+ 	continue;
+ 
+       if (nonzero_p (desc.may_be_zero))
+ 	{
+ 	  /* We exit in the first iteration through this exit.
+ 	     We won't find anything better.  */
+ 	  niter = build_int_cst_type (unsigned_type_node, 0);
+ 	  *exit = ex;
+ 	  break;
+ 	}
+ 
+       if (!zero_p (desc.may_be_zero))
+ 	continue;
+ 
+       aniter = desc.niter;
+ 
+       if (!niter)
+ 	{
+ 	  /* Nothing recorded yet.  */
+ 	  niter = aniter;
+ 	  *exit = ex;
+ 	  continue;
+ 	}
+ 
+       /* Prefer constants, the lower the better.  */
+       if (TREE_CODE (aniter) != INTEGER_CST)
+ 	continue;
+ 
+       if (TREE_CODE (niter) != INTEGER_CST)
+ 	{
+ 	  niter = aniter;
+ 	  *exit = ex;
+ 	  continue;
+ 	}
+ 
+       if (tree_int_cst_lt (aniter, niter))
+ 	{
+ 	  niter = aniter;
+ 	  *exit = ex;
+ 	  continue;
+ 	}
+     }
+   free (exits);
+ 
+   return niter ? niter : chrec_dont_know;
+ }
+ 
  /*
  
     Analysis of a number of iterations of a loop by a brute-force evaluation.
*************** find_loop_niter_by_eval (struct loop *lo
*** 1055,1067 ****
  	continue;
  
        aniter = loop_niter_by_eval (loop, ex);
!       if (chrec_contains_undetermined (aniter)
! 	  || TREE_CODE (aniter) != INTEGER_CST)
  	continue;
  
        if (niter
! 	  && !nonzero_p (fold (build2 (LT_EXPR, boolean_type_node,
! 					     aniter, niter))))
  	continue;
  
        niter = aniter;
--- 1086,1096 ----
  	continue;
  
        aniter = loop_niter_by_eval (loop, ex);
!       if (chrec_contains_undetermined (aniter))
  	continue;
  
        if (niter
! 	  && !tree_int_cst_lt (aniter, niter))
  	continue;
  
        niter = aniter;
Index: tree.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.c,v
retrieving revision 1.462
diff -c -3 -p -r1.462 tree.c
*** tree.c	2 Feb 2005 23:13:53 -0000	1.462
--- tree.c	8 Feb 2005 01:43:10 -0000
*************** operand_equal_for_phi_arg_p (tree arg0, 
*** 6193,6196 ****
--- 6193,6234 ----
    return operand_equal_p (arg0, arg1, 0);
  }
  
+ /* Returns number of zeros at the end of binary representation of X.
+    
+    ??? Use ffs if available?  */
+ 
+ tree
+ num_ending_zeros (tree x)
+ {
+   unsigned HOST_WIDE_INT fr, nfr;
+   unsigned num, abits;
+   tree type = TREE_TYPE (x);
+ 
+   if (TREE_INT_CST_LOW (x) == 0)
+     {
+       num = HOST_BITS_PER_WIDE_INT;
+       fr = TREE_INT_CST_HIGH (x);
+     }
+   else
+     {
+       num = 0;
+       fr = TREE_INT_CST_LOW (x);
+     }
+ 
+   for (abits = HOST_BITS_PER_WIDE_INT / 2; abits; abits /= 2)
+     {
+       nfr = fr >> abits;
+       if (nfr << abits == fr)
+ 	{
+ 	  num += abits;
+ 	  fr = nfr;
+ 	}
+     }
+ 
+   if (num > TYPE_PRECISION (type))
+     num = TYPE_PRECISION (type);
+ 
+   return build_int_cst_type (type, num);
+ }
+ 
  #include "gt-tree.h"
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.685
diff -c -3 -p -r1.685 tree.h
*** tree.h	7 Feb 2005 10:06:53 -0000	1.685
--- tree.h	8 Feb 2005 01:43:10 -0000
*************** extern int integer_nonzerop (tree);
*** 3275,3280 ****
--- 3275,3281 ----
  
  extern bool zero_p (tree);
  extern bool cst_and_fits_in_hwi (tree);
+ extern tree num_ending_zeros (tree);
  
  /* staticp (tree x) is nonzero if X is a reference to data allocated
     at a fixed address in memory.  Returns the outermost data.  */


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