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] Fix the check elimination


Hello,

I finished by putting enough constraints on the loop nb_iter detection
and check-elim such that the compiler bootstrap with -ftree-elim-check

I have also unified the nb_iter and check-elim analyzers since they
both rely on the detection of the first iteration that does not
satisfy an if condition.  

Bootstrapped with the following flags:
-O2 -ftree-elim-checks -fdump-tree-elck-details -fscalar-evolutions 
-fdump-tree-scev -fall-data-deps -fdump-tree-ddall

	* tree-chrec.c (chrec_contains_symbols): Factorize conditions,
	chrec_not_analyzed_yet is a NULL_TREE.
	* tree-chrec.h (prove_truth_value_{lt, le, ge, ne, gt, eq}.c):
	Removed.
	(evolution_function_is_multivariate, 
	evolution_function_is_peeled_affine_p): New.
	* tree-data-ref.c (analyze_all_data_dependences): Dump some 
	statistics on the data dependences.
	* tree-elim-check.c (not_code, prove_truth_value): New.
	(try_eliminate_check): Use prove_truth_value.
	* tree-fold-const.h (tree_is_ne): New.
	* tree-scalar-evolution.c (types_forbid_solutions_p, 
	first_iteration_non_satisfying_noev_noev, 
	first_iteration_non_satisfying_noev_ev, 
	first_iteration_non_satisfying_ev_noev, 
	first_iteration_non_satisfying_ev_ev, 
	first_iteration_non_satisfying_1, 
	first_iteration_non_satisfying, 
	gather_stats_on_scev_database): New functions.
	(nb_iterations_less, nb_iterations_eq, nb_iterations_ne): Removed.
	(set_nb_iterations_in_loop): Be more careful on overflow.
	(number_of_iterations_in_loop): Use first_iteration_non_satisfying.
	* tree-scalar-evolution.h (first_iteration_non_satisfying, 
	gather_stats_on_scev_database): Declared.

Index: tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-chrec.c,v
retrieving revision 1.1.2.10
diff -c -3 -p -r1.1.2.10 tree-chrec.c
*** tree-chrec.c	23 Mar 2004 20:13:27 -0000	1.1.2.10
--- tree-chrec.c	30 Mar 2004 14:44:05 -0000
*************** chrec_contains_symbols (tree chrec)
*** 1922,1932 ****
  bool 
  chrec_contains_undetermined (tree chrec)
  {
-   if (chrec == NULL_TREE)
-     return false;
-   
    if (chrec == chrec_top
!       || chrec == chrec_not_analyzed_yet)
      return true;
    
    switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
--- 1922,1930 ----
  bool 
  chrec_contains_undetermined (tree chrec)
  {
    if (chrec == chrec_top
!       || chrec == chrec_not_analyzed_yet
!       || chrec == NULL_TREE)
      return true;
    
    switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
Index: tree-chrec.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-chrec.h,v
retrieving revision 1.1.2.7
diff -c -3 -p -r1.1.2.7 tree-chrec.h
*** tree-chrec.h	23 Mar 2004 20:13:28 -0000	1.1.2.7
--- tree-chrec.h	30 Mar 2004 14:44:05 -0000
*************** static inline bool chrec_should_remain_s
*** 116,128 ****
  /* Analyzers.  */
  extern void analyze_overlapping_iterations (tree, tree, tree *, tree *);
  
- static inline bool prove_truth_value_lt (tree, tree, tree, bool *);
- static inline bool prove_truth_value_le (tree, tree, tree, bool *);
- static inline bool prove_truth_value_ge (tree, tree, tree, bool *);
- static inline bool prove_truth_value_ne (tree, tree, tree, bool *);
- static inline bool prove_truth_value_gt (tree, tree, tree, bool *);
- static inline bool prove_truth_value_eq (tree, tree, tree, bool *);
- 
  
  
  /* Constructors.  */
--- 116,121 ----
*************** evolution_function_is_affine_or_constant
*** 294,434 ****
      || evolution_function_is_constant_p (chrec);
  }
  
! /* Determines which expressions are simpler to be {handled | kept} in a 
!    symbolic form.  */
! 
! static inline bool
! chrec_should_remain_symbolic (tree evfun)
! {
!   if (evfun == NULL_TREE
!       || evfun == chrec_top)
!     return true;
!   
!   return false;
! }
! 
! /* Determines whether EXPR does not contains chrec expressions.  */
! 
! static inline bool
! tree_does_not_contain_chrecs (tree expr)
! {
!   return !tree_contains_chrecs (expr);
! }
! 
! /* Determines whether "CHREC0 (x) > CHREC1 (x)" for all the integers x
!    such that "0 <= x < nb_iter".  When this property is statically
!    computable, set VALUE and return true.  */
! 
! static inline bool
! prove_truth_value_gt (tree chrec0, 
! 		      tree chrec1, 
! 		      tree nb_iters ATTRIBUTE_UNUSED,
! 		      bool *value)
! {
!   tree diff = chrec_fold_minus (integer_type_node, chrec0, chrec1);
!   return chrec_is_positive (diff, value);
! }
! 
! /* Determines whether "CHREC0 (x) < CHREC1 (x)" for all the integers x
!    such that "0 <= x <= nb_iters".  When this property is statically
!    computable, set VALUE and return true.  */
  
  static inline bool
! prove_truth_value_lt (tree chrec0, 
! 		      tree chrec1, 
! 		      tree nb_iters,
! 		      bool *value)
  {
!   return prove_truth_value_gt (chrec1, chrec0, nb_iters, value);
  }
  
! /* Determines whether "CHREC0 (x) <= CHREC1 (x)" for all the integers
!    x such that "0 <= x <= nb_iters".  When this property is statically
!    computable, set VALUE and return true.  */
  
! static inline bool
! prove_truth_value_le (tree chrec0, 
! 		      tree chrec1, 
! 		      tree nb_iters, 
! 		      bool *value)
  {
!   if (prove_truth_value_gt (chrec0, chrec1, nb_iters, value))
!     {
!       *value = !*value;
!       return true;
!     }
    
!   return false;
! }
! 
! /* Determines whether "CHREC0 (x) >= CHREC1 (x)" for all the integers
!    x such that "0 <= x <= nb_iters".  When this property is statically
!    computable, set VALUE and return true.  */
  
- static inline bool
- prove_truth_value_ge (tree chrec0, 
- 		      tree chrec1, 
- 		      tree nb_iters,
- 		      bool *value)
- {
-   if (prove_truth_value_gt (chrec1, chrec0, nb_iters, value))
-     {
-       *value = !*value;
-       return true;
-     }
-   
    return false;
  }
  
! /* Determines whether "CHREC0 (x) == CHREC1 (x)" for all the integers
!    x such that "0 <= x <= nb_iters".  When this property is statically
!    computable, set VALUE and return true.  */
  
  static inline bool
! prove_truth_value_eq (tree chrec0, 
! 		      tree chrec1, 
! 		      tree nb_iters ATTRIBUTE_UNUSED,
! 		      bool *value)
  {
!   tree diff;
!   
!   if (TREE_TYPE (initial_condition (chrec0)) 
!       != TREE_TYPE (initial_condition (chrec1)))
!     return false;
!   
!   diff = chrec_fold_minus (integer_type_node, chrec0, chrec1);
!   if (TREE_CODE (diff) == INTEGER_CST)
!     {
!       if (integer_zerop (diff))
! 	*value = true;
!       
!       else
! 	*value = false;
!       
!       return true;
!     }
    
!   else
!     return false;  
  }
  
! /* Determines whether "CHREC0 (x) != CHREC1 (x)" for all the integers
!    x such that "0 <= x <= nb_iters".  When this property is statically
!    computable, set VALUE and return true.  */
  
  static inline bool
! prove_truth_value_ne (tree chrec0, 
! 		      tree chrec1, 
! 		      tree nb_iters,
! 		      bool *value)
  {
!   if (prove_truth_value_eq (chrec0, chrec1, nb_iters, value))
!     {
!       *value = !*value;
!       return true;
!     }
!   
!   return false;
  }
  
  #endif  /* GCC_TREE_CHREC_H  */
--- 287,334 ----
      || evolution_function_is_constant_p (chrec);
  }
  
! /* Determine whether the given tree is a multivariate evolution.  */
  
  static inline bool
! evolution_function_is_multivariate (tree chrec)
  {
!   return !evolution_function_is_univariate_p (chrec);
  }
  
! /* Determine whether the given tree is an affine peeled chrec.  */
  
! static inline bool 
! evolution_function_is_peeled_affine_p (tree chrec)
  {
!   if (chrec == NULL_TREE)
!     return false;
    
!   if (TREE_CODE (chrec) == PEELED_CHREC)
!     return (evolution_function_is_affine_or_constant_p (CHREC_LEFT (chrec)) 
! 	    && evolution_function_is_affine_p (CHREC_RIGHT (chrec)));
  
    return false;
  }
  
! /* Determines which expressions are simpler to be {handled | kept} in a 
!    symbolic form.  */
  
  static inline bool
! chrec_should_remain_symbolic (tree evfun)
  {
!   if (evfun == NULL_TREE
!       || evfun == chrec_top)
!     return true;
    
!   return false;
  }
  
! /* Determines whether EXPR does not contains chrec expressions.  */
  
  static inline bool
! tree_does_not_contain_chrecs (tree expr)
  {
!   return !tree_contains_chrecs (expr);
  }
  
  #endif  /* GCC_TREE_CHREC_H  */
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-data-ref.c,v
retrieving revision 1.1.2.12
diff -c -3 -p -r1.1.2.12 tree-data-ref.c
*** tree-data-ref.c	25 Mar 2004 15:15:34 -0000	1.1.2.12
--- tree-data-ref.c	30 Mar 2004 14:44:05 -0000
*************** analyze_all_data_dependences (struct loo
*** 883,897 ****
        ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
        build_classic_dist_vector (ddr, &classic_dist);
      }
! 
!   if (dump_file)
      {
        dump_data_dependence_relations (dump_file, dependence_relations);
        fprintf (dump_file, "\n\n");
      }
- 
    
!   /* Don't dump distances for avoiding to update the testsuite.  */
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
        for (i = 0; i < VARRAY_ACTIVE_SIZE (classic_dist); i++)
--- 883,897 ----
        ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
        build_classic_dist_vector (ddr, &classic_dist);
      }
!   
!   if (dump_file && (dump_flags & TDF_DETAILS))
      {
        dump_data_dependence_relations (dump_file, dependence_relations);
        fprintf (dump_file, "\n\n");
      }
    
!   /* Don't dump distances in order to avoid to update the
!      testsuite.  */
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
        for (i = 0; i < VARRAY_ACTIVE_SIZE (classic_dist); i++)
*************** analyze_all_data_dependences (struct loo
*** 903,908 ****
--- 903,966 ----
  	  fprintf (dump_file, ")\n");
  	}
        fprintf (dump_file, "\n\n");
+     }
+ 
+   if (dump_file && (dump_flags & TDF_STATS))
+     {
+       unsigned nb_top_relations = 0;
+       unsigned nb_bot_relations = 0;
+       unsigned nb_basename_differ = 0;
+       unsigned nb_non_distance_relations = 0;
+       unsigned nb_chrec_relations = 0;
+ 
+       for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
+ 	{
+ 	  struct data_dependence_relation *ddr;
+ 	  ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
+ 	  
+ 	  if (DDR_ARE_DEPENDENT (ddr) == chrec_top)
+ 	    nb_top_relations++;
+ 	  
+ 	  else if (DDR_ARE_DEPENDENT (ddr) == chrec_bot)
+ 	    {
+ 	      struct data_reference *a = DDR_A (ddr);
+ 	      struct data_reference *b = DDR_B (ddr);
+ 	      
+ 	      if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
+ 		  || array_base_name_differ_p (a, b))
+ 		nb_basename_differ++;
+ 	      else
+ 		nb_bot_relations++;
+ 	    }
+ 	  	  
+ 	  else 
+ 	    {
+ 	      unsigned j;
+ 	      
+ 	      nb_chrec_relations++;
+ 	      
+ 	      for (j = 0; j < DDR_NUM_SUBSCRIPTS (ddr); j++)
+ 		{
+ 		  struct subscript *subscript = DDR_SUBSCRIPT (ddr, j);
+ 		  
+ 		  if (SUB_DISTANCE (subscript) == chrec_top)
+ 		    {
+ 		      nb_non_distance_relations++;
+ 		      break;
+ 		    }
+ 		}
+ 	    }
+ 	}
+       
+       fprintf (dump_file, "\n(\n");
+       fprintf (dump_file, "%d\tnb_top_relations\n", nb_top_relations);
+       fprintf (dump_file, "%d\tnb_bot_relations\n", nb_bot_relations);
+       fprintf (dump_file, "%d\tnb_basename_differ\n", nb_basename_differ);
+       fprintf (dump_file, "%d\tnb_non_distance_relations\n", nb_non_distance_relations);
+       fprintf (dump_file, "%d\tnb_chrec_relations\n", nb_chrec_relations);
+       fprintf (dump_file, "\n)\n");
+       
+       gather_stats_on_scev_database ();
      }
    
    varray_clear (dependence_relations);
Index: tree-elim-check.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-elim-check.c,v
retrieving revision 1.1.2.3
diff -c -3 -p -r1.1.2.3 tree-elim-check.c
*** tree-elim-check.c	23 Mar 2004 20:54:46 -0000	1.1.2.3
--- tree-elim-check.c	30 Mar 2004 14:44:05 -0000
*************** Software Foundation, 59 Temple Place - S
*** 69,88 ****
  #include "tree-pass.h"
  #include "flags.h"
  
! static void remove_redundant_check (tree, bool);
! static void try_eliminate_check (tree);
! static void scan_all_loops_r (struct loop *);
  
  /* Remove the check by setting the condition COND to VALUE.  */
  
! static void 
  remove_redundant_check (tree cond, bool value)
  {
    /* A dead COND_EXPR means the condition is dead. We don't change any
       flow, just replace the expression with a constant.  */
!   if (dump_file && (dump_flags & TDF_STATS))
      fprintf (dump_file, "Replacing one of the conditions.\n");
! 
    if (value == true)
      COND_EXPR_COND (cond) = integer_one_node;
    
--- 69,194 ----
  #include "tree-pass.h"
  #include "flags.h"
  
! /* Return the negation of the comparison code.  */
! 
! static inline enum tree_code
! not_code (enum tree_code code)
! {
!   switch (code)
!     {
!     case EQ_EXPR:
!       return NE_EXPR;
!     case NE_EXPR:
!       return EQ_EXPR;
!     case LT_EXPR:
!       return GE_EXPR;
!     case LE_EXPR:
!       return GT_EXPR;
!     case GT_EXPR:
!       return LE_EXPR;
!     case GE_EXPR:
!       return LT_EXPR;
!       
!     default:
!       return code;
!     }
! }
! 
! /* Determine whether "CHREC0 (x) CODE CHREC1 (x)", for all the
!    integers x such that "0 <= x <= NB_ITERS_IN_LOOP".  When this
!    property is statically computable, set VALUE and return true.  */
! 
! static bool
! prove_truth_value (enum tree_code code, 
! 		   unsigned loop_nb, 
! 		   tree chrec0, 
! 		   tree chrec1, 
! 		   tree nb_iters_in_loop, 
! 		   bool *value)
! {
!   tree nb_iters_in_then, nb_iters_in_else;
!   
!   if (dump_file && (dump_flags & TDF_DETAILS))
!     {
!       fprintf (dump_file, "  (nb_iters_in_loop = ");
!       print_generic_expr (dump_file, nb_iters_in_loop, 0);
!       fprintf (dump_file, ")\n  (chrec0 = ");
!       print_generic_expr (dump_file, chrec0, 0);
!       fprintf (dump_file, ")\n  (chrec1 = ");
!       print_generic_expr (dump_file, chrec1, 0);
!       fprintf (dump_file, ")\n");
!     }
!   
!   if (automatically_generated_chrec_p (nb_iters_in_loop))
!     return false;
!   
!   /* Compute the number of iterations that fall in the THEN clause,
!      and the number of iterations that fall in the ELSE clause.  */
!   nb_iters_in_then = first_iteration_non_satisfying 
!     (code, loop_nb, chrec0, chrec1);
!   nb_iters_in_else = first_iteration_non_satisfying 
!     (not_code (code), loop_nb, chrec0, chrec1);
!   
!   if (dump_file && (dump_flags & TDF_DETAILS))
!     {
!       fprintf (dump_file, "  (nb_iters_in_then = ");
!       print_generic_expr (dump_file, nb_iters_in_then, 0);
!       fprintf (dump_file, ")\n  (nb_iters_in_else = ");
!       print_generic_expr (dump_file, nb_iters_in_else, 0);
!       fprintf (dump_file, ")\n");
!     }
!   
!   if (nb_iters_in_then == chrec_top
!       || nb_iters_in_else == chrec_top)
!     return false;
!   
!   if (nb_iters_in_then == chrec_bot
!       && integer_zerop (nb_iters_in_else))
!     {
!       *value = true;
!       return true;
!     }
!   
!   if (nb_iters_in_else == chrec_bot
!       && integer_zerop (nb_iters_in_then))
!     {
!       *value = false;
!       return true;
!     }
!   
!   if (TREE_CODE (nb_iters_in_then) == INTEGER_CST
!       && TREE_CODE (nb_iters_in_else) == INTEGER_CST)
!     {
!       if (integer_zerop (nb_iters_in_then)
! 	  && tree_is_gt (nb_iters_in_else, nb_iters_in_loop))
! 	{
! 	  *value = false;
! 	  return true;
! 	}
!       
!       if (integer_zerop (nb_iters_in_else)
! 	  && tree_is_gt (nb_iters_in_then, nb_iters_in_loop))
! 	{
! 	  *value = true;
! 	  return true;
! 	}
!       
!       return false;
!     }
!   
!   return false;
! }
  
  /* Remove the check by setting the condition COND to VALUE.  */
  
! static inline void 
  remove_redundant_check (tree cond, bool value)
  {
    /* A dead COND_EXPR means the condition is dead. We don't change any
       flow, just replace the expression with a constant.  */
!   if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file, "Replacing one of the conditions.\n");
!   
    if (value == true)
      COND_EXPR_COND (cond) = integer_one_node;
    
*************** try_eliminate_check (tree cond)
*** 103,110 ****
    tree chrec0, chrec1;
    unsigned loop_nb = loop_num (loop_of_stmt (cond));
    tree nb_iters = number_of_iterations_in_loop (loop_of_stmt (cond));
! 
!   if (dump_file && (dump_flags & TDF_STATS))
      {
        fprintf (dump_file, "(try_eliminate_check \n");
        fprintf (dump_file, "  (cond = ");
--- 209,219 ----
    tree chrec0, chrec1;
    unsigned loop_nb = loop_num (loop_of_stmt (cond));
    tree nb_iters = number_of_iterations_in_loop (loop_of_stmt (cond));
!   
!   if (automatically_generated_chrec_p (nb_iters))
!     return;
!   
!   if (dump_file && (dump_flags & TDF_DETAILS))
      {
        fprintf (dump_file, "(try_eliminate_check \n");
        fprintf (dump_file, "  (cond = ");
*************** try_eliminate_check (tree cond)
*** 123,129 ****
  	break;
        chrec0 = instantiate_parameters (loop_nb, chrec0);
        
!       if (dump_file && (dump_flags & TDF_STATS))
  	{
  	  fprintf (dump_file, "  (test = ");
  	  print_generic_expr (dump_file, test, 0);
--- 232,238 ----
  	break;
        chrec0 = instantiate_parameters (loop_nb, chrec0);
        
!       if (dump_file && (dump_flags & TDF_DETAILS))
  	{
  	  fprintf (dump_file, "  (test = ");
  	  print_generic_expr (dump_file, test, 0);
*************** try_eliminate_check (tree cond)
*** 135,141 ****
  	  fprintf (dump_file, ")\n");
  	}
        
!       if (prove_truth_value_ne (chrec0, integer_zero_node, nb_iters, &value))
  	remove_redundant_check (cond, value);
        break;
  
--- 244,251 ----
  	  fprintf (dump_file, ")\n");
  	}
        
!       if (prove_truth_value (NE_EXPR, loop_nb, chrec0, integer_zero_node, 
! 			     nb_iters, &value))
  	remove_redundant_check (cond, value);
        break;
  
*************** try_eliminate_check (tree cond)
*** 158,164 ****
        chrec0 = instantiate_parameters (loop_nb, chrec0);
        chrec1 = instantiate_parameters (loop_nb, chrec1);
        
!       if (dump_file && (dump_flags & TDF_STATS))
  	{
  	  fprintf (dump_file, "  (test = ");
  	  print_generic_expr (dump_file, test, 0);
--- 268,274 ----
        chrec0 = instantiate_parameters (loop_nb, chrec0);
        chrec1 = instantiate_parameters (loop_nb, chrec1);
        
!       if (dump_file && (dump_flags & TDF_DETAILS))
  	{
  	  fprintf (dump_file, "  (test = ");
  	  print_generic_expr (dump_file, test, 0);
*************** try_eliminate_check (tree cond)
*** 172,219 ****
  	  fprintf (dump_file, ")\n");
  	}
        
!       switch (TREE_CODE (test))
! 	{
! 	case LT_EXPR:
! 	  if (prove_truth_value_lt (chrec0, chrec1, nb_iters, &value))
! 	    remove_redundant_check (cond, value);
! 	  break;
! 	  
! 	case LE_EXPR:
! 	  if (prove_truth_value_le (chrec0, chrec1, nb_iters, &value))
! 	    remove_redundant_check (cond, value);
! 	  break;
! 	  
! 	case GT_EXPR:
! 	  if (prove_truth_value_gt (chrec0, chrec1, nb_iters, &value))
! 	    remove_redundant_check (cond, value);
! 	  break;
! 	  
! 	case GE_EXPR:
! 	  if (prove_truth_value_ge (chrec0, chrec1, nb_iters, &value))
! 	    remove_redundant_check (cond, value);
! 	  break;
! 	    
! 	case EQ_EXPR:
! 	  if (prove_truth_value_eq (chrec0, chrec1, nb_iters, &value))
! 	    remove_redundant_check (cond, value);
! 	  break;
! 	  
! 	case NE_EXPR:
! 	  if (prove_truth_value_ne (chrec0, chrec1, nb_iters, &value))
! 	    remove_redundant_check (cond, value);
! 	  break;
! 	  
! 	default:
! 	  break;
! 	}
        break;
        
      default:
        break;
      }
    
!   if (dump_file && (dump_flags & TDF_STATS))
      fprintf (dump_file, ")\n");
  }
  
--- 282,297 ----
  	  fprintf (dump_file, ")\n");
  	}
        
!       if (prove_truth_value (TREE_CODE (test), loop_nb, chrec0, chrec1, 
! 			     nb_iters, &value))
! 	remove_redundant_check (cond, value);
        break;
        
      default:
        break;
      }
    
!   if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file, ")\n");
  }
  
Index: tree-fold-const.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-fold-const.h,v
retrieving revision 1.1.2.5
diff -c -3 -p -r1.1.2.5 tree-fold-const.h
*** tree-fold-const.h	23 Mar 2004 20:13:28 -0000	1.1.2.5
--- tree-fold-const.h	30 Mar 2004 14:44:06 -0000
*************** tree_is_eq (tree a, tree b)
*** 257,261 ****
--- 257,269 ----
    return (tree_int_cst_sgn (cmp) != 0);
  }
  
+ /* Given two integer constants A and B, determine whether "A != B".  */
+ 
+ static inline bool
+ tree_is_ne (tree a, tree b)
+ {
+   tree cmp = fold (build (NE_EXPR, boolean_type_node, a, b));
+   return (tree_int_cst_sgn (cmp) != 0);
+ }
  
  #endif  /* GCC_TREE_FOLD_H  */
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.c,v
retrieving revision 1.1.2.25
diff -c -3 -p -r1.1.2.25 tree-scalar-evolution.c
*** tree-scalar-evolution.c	27 Mar 2004 18:29:36 -0000	1.1.2.25
--- tree-scalar-evolution.c	30 Mar 2004 14:44:06 -0000
*************** Software Foundation, 59 Temple Place - S
*** 266,272 ****
  
  
  static bool loop_phi_node_p (tree);
! static tree compute_overall_effect_of_inner_loop (tree);
  
  static void set_scalar_evolution (tree, tree);
  static void set_scalar_evolution_outer_value (tree, tree);
--- 266,272 ----
  
  
  static bool loop_phi_node_p (tree);
! 
  
  static void set_scalar_evolution (tree, tree);
  static void set_scalar_evolution_outer_value (tree, tree);
*************** static varray_type already_instantiated_
*** 305,311 ****
  
  /* Statistics counters.  */
  static unsigned stats_nb_chrecs = 0;
! static unsigned stats_nb_peeled = 0;
  static unsigned stats_nb_affine = 0;
  static unsigned stats_nb_affine_multivar = 0;
  static unsigned stats_nb_higher_poly = 0;
--- 305,311 ----
  
  /* Statistics counters.  */
  static unsigned stats_nb_chrecs = 0;
! static unsigned stats_nb_peeled_affine = 0;
  static unsigned stats_nb_affine = 0;
  static unsigned stats_nb_affine_multivar = 0;
  static unsigned stats_nb_higher_poly = 0;
*************** chrec_is_positive (tree chrec, bool *val
*** 695,705 ****
     symbolic. */
  
  static tree 
! set_scev_keep_symbolic (tree var,
  			tree chrec)
  {
    if (chrec == chrec_not_analyzed_yet)
      return chrec;
    
    switch (TREE_CODE (chrec))
      {
--- 695,709 ----
     symbolic. */
  
  static tree 
! set_scev_keep_symbolic (tree def,
  			tree chrec)
  {
    if (chrec == chrec_not_analyzed_yet)
      return chrec;
+ 
+   if (chrec == chrec_top)
+     /*    return def; */
+     return chrec;
    
    switch (TREE_CODE (chrec))
      {
*************** set_scev_keep_symbolic (tree var,
*** 708,721 ****
      case INDIRECT_REF:
      case COMPONENT_REF:
        /* KEEP_IT_SYMBOLIC.  */
!       chrec = var;
!       break;
        
      default:
!       break;
      }
-   
-   return chrec;
  }
  
  /* Associate CHREC to SCALAR.  */
--- 712,722 ----
      case INDIRECT_REF:
      case COMPONENT_REF:
        /* KEEP_IT_SYMBOLIC.  */
!       return def;
        
      default:
!       return chrec;
      }
  }
  
  /* Associate CHREC to SCALAR.  */
*************** multiply_evolution (unsigned loop_nb, 
*** 1327,1612 ****
  /* This section deals with the approximation of the number of
     iterations a loop will run.  */
  
! /* Try to compute the number of iterations in LOOP_NB such that:
!    - when (CODE is LE_EXPR) the loop exits when CHREC0 > CHREC1,
!    - when (CODE is LT_EXPR) the loop exits when CHREC0 >= CHREC1.
! */
  
  static tree 
! nb_iterations_less (enum tree_code code, 
! 		    unsigned loop_nb, 
! 		    tree chrec0, 
! 		    tree chrec1)
  {
!   tree other_ev0, other_ev1, other_evolutions;
!   tree res = chrec_top;
    
!   if (automatically_generated_chrec_p (chrec0)
!       || automatically_generated_chrec_p (chrec1))
      return chrec_top;
    
!   other_ev0 = chrec0;
!   other_ev1 = chrec1;
!   
!   chrec0 = evolution_function_in_loop_num (chrec0, loop_nb);
!   chrec1 = evolution_function_in_loop_num (chrec1, loop_nb);
    
!   /* Compute the evolutions on other dimensions.  */
!   other_ev0 = chrec_fold_minus (integer_type_node, chrec0, other_ev0);
!   other_ev1 = chrec_fold_minus (integer_type_node, chrec1, other_ev1);
!   other_evolutions = chrec_fold_plus (integer_type_node, other_ev0, other_ev1);
    
!   if (evolution_function_is_affine_or_constant_p (chrec0)
!       && evolution_function_is_affine_or_constant_p (chrec1))
      {
!       tree type0, type1;
!       tree left0, left1, right0, right1;
        
!       type0 = chrec_type (chrec0);
!       type1 = chrec_type (chrec1);
        
!       switch (TREE_CODE (chrec0))
! 	{
! 	case POLYNOMIAL_CHREC:
! 	  left0 = CHREC_LEFT (chrec0);
! 	  right0 = CHREC_RIGHT (chrec0);
! 	  break;
! 	  
! 	case INTEGER_CST:
! 	  left0 = chrec0;
! 	  right0 = integer_zero_node;
! 	  break;
! 	  
! 	default:
  	  return chrec_top;
! 	}
        
!       switch (TREE_CODE (chrec1))
! 	{
! 	case POLYNOMIAL_CHREC:
! 	  left1 = CHREC_LEFT (chrec1);
! 	  right1 = CHREC_RIGHT (chrec1);
! 	  break;
! 	  
! 	case INTEGER_CST:
! 	  left1 = chrec1;
! 	  right1 = integer_zero_node;
! 	  break;
! 	  
! 	default:
  	  return chrec_top;
! 	}
        
!       if (TREE_CODE (left0) != INTEGER_CST
! 	  || TREE_CODE (left1) != INTEGER_CST
! 	  || TREE_CODE (right0) != INTEGER_CST
! 	  || TREE_CODE (right1) != INTEGER_CST)
! 	return chrec_top;
        
!       if (code == LE_EXPR)
! 	{
! 	  if (tree_is_gt (left0, left1))
! 	    return other_evolutions;
! 	  
! 	  if (tree_is_gt (TYPE_MIN_VALUE (type1), 
! 			  TYPE_MAX_VALUE (type0)))
! 	    return chrec_bot;
! 	}
!       else
! 	{
! 	  if (tree_is_ge (left0, left1))
! 	    return other_evolutions;
! 	  
! 	  if (tree_is_ge (TYPE_MIN_VALUE (type1), 
! 			  TYPE_MAX_VALUE (type0)))
! 	    return chrec_bot;
! 	}
        
!       /* No evolution.  */
!       if (integer_zerop (right0) 
! 	  && integer_zerop (right1))
! 	return chrec_bot;
  
!       /* No evolution on chrec0.  */
!       if (integer_zerop (right0))
! 	{
! 	  tree nb_iters;
! 	  tree tmin, tmax;
! 	  
! 	  tmin = TYPE_MIN_VALUE (type1);
! 	  tmax = TYPE_MAX_VALUE (type1);
! 	  
! 	  if (code == LE_EXPR)
! 	    {
! 	      if (tree_is_gt (tmin, left0))
! 		return chrec_bot;
! 	      
! 	      if (tree_int_cst_sgn (right1) > 0)
! 		nb_iters = tree_fold_plus 
! 		  (integer_type_node, 
! 		   tree_fold_floor_div
! 		   (integer_type_node, 
! 		    tree_fold_minus (integer_type_node, tmax, left1), 
! 		    right1), integer_one_node);
! 	      
! 	      else 
! 		nb_iters = tree_fold_plus 
! 		  (integer_type_node, 
! 		   tree_fold_floor_div
! 		   (integer_type_node, 
! 		    tree_fold_minus (type1, left1, left0), 
! 		    tree_fold_abs (type1, right1)), 
! 		   integer_one_node);
! 	      
! 	      /* Verify the result.  */
! 	      if (tree_is_gt 
! 		  (left0, 
! 		   tree_fold_plus (type1, left1, 
! 				   tree_fold_multiply 
! 				   (integer_type_node, nb_iters, right1))))
! 		return chrec_fold_plus 
! 		  (chrec_type (res), nb_iters, other_evolutions);
! 	      
! 	      else 
! 		/* Difficult cases fall down there.  */
! 		return chrec_top;
! 	    }
! 	  else
! 	    {
! 	      if (tree_is_ge (tmin, left0))
! 		return chrec_bot;
! 	      
! 	      if (tree_int_cst_sgn (right1) > 0)
! 		nb_iters = tree_fold_ceil_div
! 		  (integer_type_node, 
! 		   tree_fold_minus (integer_type_node, tmax, left1), 
! 		   right1);
! 	      
! 	      else 
! 		nb_iters = tree_fold_ceil_div
! 		  (integer_type_node, 
! 		   tree_fold_minus (type1, left1, left0), 
! 		   tree_fold_abs (type1, right1));
! 	      
! 	      /* Verify the result.  */
! 	      if (tree_is_ge 
! 		  (left0, 
! 		   tree_fold_plus (type1, left1, 
! 				   tree_fold_multiply 
! 				   (integer_type_node, nb_iters, right1))))
! 		return chrec_fold_plus 
! 		  (chrec_type (res), nb_iters, other_evolutions);
! 	      
! 	      else 
! 		/* Difficult cases fall down there.  */
! 		return chrec_top;
! 	    }
! 	}
!       
!       /* No evolution on chrec1.  */
!       if (integer_zerop (right1))
! 	{
! 	  tree nb_iters;
! 	  tree tmin, tmax;
! 	  
! 	  tmin = TYPE_MIN_VALUE (type0);
! 	  tmax = TYPE_MAX_VALUE (type0);
! 	  
! 	  if (code == LE_EXPR)
! 	    {
! 	      if (tree_is_gt (left1, tmax))
! 		return chrec_bot;
! 	      
! 	      if (tree_int_cst_sgn (right0) < 0)
! 		nb_iters = tree_fold_plus 
! 		  (integer_type_node, 
! 		   tree_fold_floor_div
! 		   (integer_type_node, 
! 		    tree_fold_minus (integer_type_node, left0, tmin), 
! 		    tree_fold_abs (type0, right0)), integer_one_node);
! 	      
! 	      else 
! 		nb_iters = tree_fold_plus 
! 		  (integer_type_node, 
! 		   tree_fold_floor_div
! 		   (integer_type_node, 
! 		    tree_fold_minus (type1, left1, left0), 
! 		    right0), integer_one_node);
! 	      
! 	      /* Verify the result.  */
! 	      if (tree_is_le
! 		  (left1, 
! 		   tree_fold_plus (type0, left0, 
! 				   tree_fold_multiply 
! 				   (integer_type_node, nb_iters, right0))))
! 		return chrec_fold_plus 
! 		  (chrec_type (res), nb_iters, other_evolutions);
! 	      
! 	      else 
! 		/* Difficult cases fall down there.  */
! 		return chrec_top;
! 	    }
! 	  else
! 	    {
! 	      if (tree_is_ge (left1, tmax))
! 		return chrec_bot;
! 	      
! 	      if (tree_int_cst_sgn (right0) < 0)
! 		nb_iters = tree_fold_ceil_div 
! 		  (integer_type_node, 
! 		   tree_fold_minus (integer_type_node, left0, tmin), 
! 		   tree_fold_abs (type0, right0));
! 	      
! 	      else 
! 		nb_iters = tree_fold_ceil_div
! 		  (integer_type_node, 
! 		   tree_fold_minus (type1, left1, left0), 
! 		   right0);
! 	      
! 	      /* Verify the result.  */
! 	      if (tree_is_lt
! 		  (left1, 
! 		   tree_fold_plus (type0, left0, 
! 				   tree_fold_multiply 
! 				   (integer_type_node, nb_iters, right0))))
! 		return chrec_fold_plus 
! 		  (chrec_type (res), nb_iters, other_evolutions);
! 	      
! 	      else 
! 		/* Difficult cases fall down there.  */
! 		return chrec_top;
! 	    }
! 	}
        
!       /* Evolution on chrec0 and chrec1.  */
!       else
! 	return chrec_top;
      }
    
!   else
!     return chrec_top;
  }
  
! /* Try to compute the number of iterations in LOOP_NB such that the
!    loop exits when CHREC0 != CHREC1.  */
  
  static tree 
! nb_iterations_eq (unsigned loop_nb ATTRIBUTE_UNUSED, 
! 		  tree chrec0 ATTRIBUTE_UNUSED, 
! 		  tree chrec1 ATTRIBUTE_UNUSED)
  {
    return chrec_top;
  }
  
! /* Try to compute the number of iterations in LOOP_NB such that the
!    loop exits when CHREC0 == CHREC1.  */
  
  static tree 
! nb_iterations_ne (unsigned loop_nb ATTRIBUTE_UNUSED, 
! 		  tree chrec0 ATTRIBUTE_UNUSED, 
! 		  tree chrec1 ATTRIBUTE_UNUSED)
  {
!   return chrec_top;
  }
  
  /* Helper function.  */
--- 1328,2037 ----
  /* This section deals with the approximation of the number of
     iterations a loop will run.  */
  
! /* Helper function that determines whether the considered types are
!    compatible for finding a solution.  */
! #if 0
! static bool
! types_forbid_solutions_p (enum tree_code code, 
! 			  tree type0, 
! 			  tree type1)
! {
!   switch (code)
!     {
!     case LE_EXPR:
!       return tree_is_le (TYPE_MAX_VALUE (type0), 
! 			 TYPE_MIN_VALUE (type1));
!       
!     case LT_EXPR:
!       return tree_is_lt (TYPE_MAX_VALUE (type0), 
! 			 TYPE_MIN_VALUE (type1));
!       
!     case EQ_EXPR:
!       return false;
!       
!     case NE_EXPR:
!       return (tree_is_lt (TYPE_MAX_VALUE (type0), 
! 			  TYPE_MIN_VALUE (type1))
! 	      || tree_is_lt (TYPE_MAX_VALUE (type1), 
! 			     TYPE_MIN_VALUE (type0)));
!       
!     default:
!       abort ();
!       return false;
!     }
! }
! #endif
! 
! /* Helper function for the case when both evolution functions don't
!    have an evolution in the considered loop.  */
  
  static tree 
! first_iteration_non_satisfying_noev_noev (enum tree_code code, 
! 					  unsigned loop_nb ATTRIBUTE_UNUSED, 
! 					  tree chrec0, 
! 					  tree chrec1)
  {
!   tree init0 = initial_condition (chrec0);
!   tree init1 = initial_condition (chrec1);
    
!   if (TREE_CODE (init0) != INTEGER_CST
!       || TREE_CODE (init1) != INTEGER_CST)
!     return chrec_top;
! 
!   if (!evolution_function_is_constant_p (chrec0)
!       || !evolution_function_is_constant_p (chrec1))
      return chrec_top;
    
!   switch (code)
!     {
!     case LE_EXPR:
!       if (tree_is_gt (init0, init1))
! 	return integer_zero_node;
!       else
! 	return chrec_bot;
!       
!     case LT_EXPR:
!       if (tree_is_ge (init0, init1))
! 	return integer_zero_node;
!       else
! 	return chrec_bot;
!       
!     case EQ_EXPR:
!       if (tree_is_eq (init0, init1))
! 	return integer_zero_node;
!       else
! 	return chrec_bot;
!       
!     case NE_EXPR:
!       if (tree_is_ne (init0, init1))
! 	return integer_zero_node;
!       else
! 	return chrec_bot;
!       
!     default:
!       return chrec_top;
!     }
! }
! 
! /* Helper function for the case when CHREC0 has no evolution and
!    CHREC1 has an evolution in the considered loop.  */
! 
! static tree 
! first_iteration_non_satisfying_noev_ev (enum tree_code code, 
! 					unsigned loop_nb, 
! 					tree chrec0, 
! 					tree chrec1)
! {
!   tree type1 = chrec_type (chrec1);
!   /*  tree tmax = TYPE_MAX_VALUE (type1); */
!   tree ev_in_this_loop;
!   tree init0, init1, step1;
!   tree nb_iters;
!   
!   ev_in_this_loop = evolution_function_in_loop_num (chrec1, loop_nb);
!   if (!evolution_function_is_affine_p (ev_in_this_loop))
!     /* For the moment handle only polynomials of degree 1.  */
!     return chrec_top;
    
!   init1 = CHREC_LEFT (ev_in_this_loop);
!   step1 = CHREC_RIGHT (ev_in_this_loop);
!   init0 = initial_condition (chrec0);
!   if (TREE_CODE (init0) != INTEGER_CST
!       || TREE_CODE (init1) != INTEGER_CST
!       || TREE_CODE (step1) != INTEGER_CST)
!     /* For the moment we deal only with INTEGER_CSTs.  */
!     return chrec_top;
    
!   switch (code)
      {
!     case LE_EXPR:
!       {
! 	if (tree_is_gt (init0, init1))
! 	  {
! 	    if (evolution_function_is_constant_p (chrec0))
! 	      /* Example: "while (2 <= {0, +, 1}_2)".  */
! 	      return integer_zero_node;
! 	    else
! 	      /* Example: "while ({2, +, -1}_1 <= {0, +, 1}_2)".  The
! 		 number of iterations in loop_2 during the first two
! 		 iterations of loop_1 is equal to 0.  */
! 	      return chrec_top;
! 	  }
! 	
! 	if (tree_int_cst_sgn (step1) > 0)
! 	  {
! 	    if (evolution_function_is_constant_p (chrec0))
! 	      /* Example: "while (2 <= {3, +, 1}_2)".  */
! 	      return chrec_top;
! 	    /* nb_iters = tree_fold_plus 
! 	       (integer_type_node, 
! 	       tree_fold_floor_div (integer_type_node, 
! 	       tree_fold_minus (integer_type_node, 
! 	       tmax, init1), 
! 	       step1), 
! 	       integer_one_node);
! 	    */
! 	    else
! 	      /* Example: "while ({2, +, 1}_1 <= {3, +, 1}_2)".  */
! 	      return chrec_top;
! 	  }
! 	
! 	else
! 	  {
! 	    if (evolution_function_is_constant_p (chrec0))
! 	      /* Example: "while (2 <= {3, +, -1}_2)".  */
! 	      nb_iters = tree_fold_plus 
! 		(integer_type_node, 
! 		 tree_fold_floor_div (integer_type_node, 
! 				      tree_fold_minus (integer_type_node, 
! 						       init1, init0), 
! 				      tree_fold_abs (integer_type_node, 
! 						     step1)), 
! 		 integer_one_node);
! 	    else
! 	      /* Example: "while ({2, +, 1}_1 <= {3, +, -1}_2)".  */
! 	      return chrec_top;
! 	  }
! 	
! 	/* Verify the result.  */
! 	if (evolution_function_is_constant_p (chrec0)
! 	    && tree_is_gt (init0, 
! 			   tree_fold_plus (type1, init1, 
! 					   tree_fold_multiply 
! 					   (integer_type_node, 
! 					    nb_iters, step1))))
! 	  return nb_iters;
! 	
! 	else 
! 	  /* Difficult cases fall down there.  Example: When the
! 	     evolution step is big enough the wrapped value can be
! 	     bigger than init0.  In these cases the loop may end after
! 	     several wraps, or never end.  */
! 	  return chrec_top;
!       }
        
!     case LT_EXPR:
!       {
! 	if (tree_is_ge (init0, init1))
! 	  {
! 	    if (evolution_function_is_constant_p (chrec0))
! 	      /* Example: "while (2 < {0, +, 1}_2)".  */
! 	      return integer_zero_node;
! 	    else
! 	      /* Example: "while ({2, +, 1}_1 < {0, +, 1}_2)".  */
! 	      return chrec_top;
! 	  }
! 	
! 	if (tree_int_cst_sgn (step1) > 0)
! 	  {
! 	    if (evolution_function_is_constant_p (chrec0))
! 	      /* Example: "while (2 < {3, +, 1}_2)".  */
! 	      return chrec_top;
! 	    /* nb_iters = tree_fold_ceil_div
! 	       (integer_type_node, 
! 	       tree_fold_minus (integer_type_node, tmax, init1), 
! 	       step1);
! 	    */
! 	    else
! 	      /* Example: "while ({2, +, 1}_1 < {3, +, 1}_2)".  */
! 	      return chrec_top;
! 	  }
! 	else 
! 	  {
! 	    if (evolution_function_is_constant_p (chrec0))
! 	      /* Example: "while (2 < {3, +, -1}_2)".  */
! 	      nb_iters = tree_fold_ceil_div
! 		(integer_type_node, 
! 		 tree_fold_minus (type1, init1, init0), 
! 		 tree_fold_abs (type1, step1));
! 	    else
! 	      /* Example: "while ({2, +, 1}_1 < {3, +, -1}_2)".  */
! 	      return chrec_top;
! 	  }
! 	
! 	/* Verify the result.  */
! 	if (evolution_function_is_constant_p (chrec0)
! 	    && tree_is_ge (init0, 
! 			   tree_fold_plus (type1, init1, 
! 					   tree_fold_multiply 
! 					   (integer_type_node, 
! 					    nb_iters, step1))))
! 	  return nb_iters;
! 	
! 	else 
! 	  /* Difficult cases fall down there.  */
! 	  return chrec_top;
!       }
        
!     case EQ_EXPR:
!       {
! 	if (tree_is_ne (init0, init1))
! 	  {
! 	    if (evolution_function_is_constant_p (chrec0))
! 	      /* Example: "while (2 == {0, +, 1}_2)".  */
! 	      return integer_zero_node;
! 	    else
! 	      /* Example: "while ({2, +, -1}_1 == {0, +, 1}_2)".  */
! 	      return chrec_top;
! 	  }
! 	
! 	if (evolution_function_is_constant_p (chrec0))
! 	  {
! 	    if (integer_zerop (step1))
! 	      /* Example: "while (2 == {2, +, 0}_2)".  */
! 	      return chrec_bot;
! 	    else
! 	      return integer_one_node;
! 	  }
! 	else
  	  return chrec_top;
!       }
        
!     case NE_EXPR:
!       {
! 	if (tree_is_eq (init0, init1))
! 	  {
! 	    if (evolution_function_is_constant_p (chrec0))
! 	      /* Example: "while (0 != {0, +, 1}_2)".  */
! 	      return integer_zero_node;
! 	    else
! 	      /* Example: "while ({0, +, -1}_1 != {0, +, 1}_2)".  */
! 	      return chrec_top;
! 	  }
! 	
! 	if (tree_int_cst_sgn (step1) > 0)
! 	  {
! 	    if (evolution_function_is_constant_p (chrec0))
! 	      {
! 		if (tree_is_gt (init0, init1))
! 		  {
! 		    tree diff = tree_fold_minus (integer_type_node, 
! 						 init0, init1);
! 		    if (tree_fold_divides_p (integer_type_node, step1, diff))
! 		      /* Example: "while (3 != {2, +, 1}_2)".  */
! 		      nb_iters = tree_fold_exact_div 
! 			(integer_type_node, diff, step1);
! 		    else
! 		      /* Example: "while (3 != {2, +, 2}_2)".  */
! 		      return chrec_top;
! 		  }
! 		else
! 		  /* Example: "while (2 != {3, +, 1}_2)".  */
! 		  return chrec_top;
! 	      }
! 	    else
! 	      /* Example: "while ({2, +, 1}_1 != {3, +, 1}_2)".  */
! 	      return chrec_top;
! 	  }
! 	
! 	else
! 	  {
! 	    if (evolution_function_is_constant_p (chrec0))
! 	      {
! 		if (tree_is_lt (init0, init1))
! 		  {
! 		    tree diff = tree_fold_minus (integer_type_node, 
! 						 init1, init0);
! 		    if (tree_fold_divides_p (integer_type_node, step1, diff))
! 		      /* Example: "while (2 != {3, +, -1}_2)".  */
! 		      nb_iters = tree_fold_exact_div 
! 			(integer_type_node, diff, 
! 			 tree_fold_abs (integer_type_node, step1));
! 		    else
! 		      /* Example: "while (2 != {3, +, -2}_2)".  */
! 		      return chrec_top;
! 		  }
! 		else
! 		  /* Example: "while (3 != {2, +, -1}_2)".  */
! 		  return chrec_top;
! 	      }
! 	    else
! 	      /* Example: "while ({2, +, 1}_1 != {3, +, -1}_2)".  */
! 	      return chrec_top;
! 	  }
! 
! 	/* Verify the result.  */
! 	if (evolution_function_is_constant_p (chrec0)
! 	    && tree_is_eq (init0, 
! 			   tree_fold_plus (type1, init1, 
! 					   tree_fold_multiply 
! 					   (integer_type_node, 
! 					    nb_iters, step1))))
! 	  return nb_iters;
! 	
! 	else 
! 	  /* Difficult cases fall down there.  */
  	  return chrec_top;
!       }
! 
!     default:
!       return chrec_top;
!     }
!   return chrec_top;
! }
! 
! /* Helper function for the case when CHREC1 has no evolution and
!    CHREC0 has an evolution in the considered loop.  */
! 
! static tree 
! first_iteration_non_satisfying_ev_noev (enum tree_code code, 
! 					unsigned loop_nb, 
! 					tree chrec0, 
! 					tree chrec1)
! {
!   tree type0 = chrec_type (chrec0);
!   /*  tree tmin = TYPE_MIN_VALUE (type0); */
!   tree ev_in_this_loop;
!   tree init0, init1, step0;
!   tree nb_iters;
!   
!   ev_in_this_loop = evolution_function_in_loop_num (chrec0, loop_nb);
!   if (!evolution_function_is_affine_p (ev_in_this_loop))
!     /* For the moment handle only polynomials of degree 1.  */
!     return chrec_top;
!   
!   init0 = CHREC_LEFT (ev_in_this_loop);
!   step0 = CHREC_RIGHT (ev_in_this_loop);
!   init1 = initial_condition (chrec1);
!   if (TREE_CODE (init1) != INTEGER_CST
!       || TREE_CODE (init0) != INTEGER_CST
!       || TREE_CODE (step0) != INTEGER_CST)
!     /* For the moment we deal only with INTEGER_CSTs.  */
!     return chrec_top;
!   
!   switch (code)
!     {
!     case LE_EXPR:
!       {
! 	if (tree_is_gt (init0, init1))
! 	  {
! 	    if (evolution_function_is_constant_p (chrec1))
! 	      /* Example: "while ({2, +, 1}_2 <= 0)".  */
! 	      return integer_zero_node;
! 	    
! 	    else
! 	      /* Example: "while ({2, +, 1}_2 <= {0, +, 1}_1)".  */
! 	      return chrec_top;
! 	  }
! 	
! 	if (tree_int_cst_sgn (step0) < 0)
! 	  {
! 	    if (evolution_function_is_constant_p (chrec1))
! 	      /* Example: "while ({2, +, -1}_2 <= 3)".  */
! 	      return chrec_top;
! 	    /* nb_iters = tree_fold_plus 
! 	       (integer_type_node, 
! 	       tree_fold_floor_div (integer_type_node, 
! 	       tree_fold_minus (integer_type_node, 
! 	       init0, tmin), 
! 	       tree_fold_abs (integer_type_node, 
! 	       step0)), 
! 	       integer_one_node);
! 	    */
! 	    else
! 	      /* Example: "while ({2, +, -1}_2 <= {3, +, 1}_1)".  */
! 	      return chrec_top;
! 	  }
! 	else 
! 	  {
! 	    if (evolution_function_is_constant_p (chrec1))
! 	      /* Example: "while ({2, +, 1}_2 <= 3)".  */
! 	      nb_iters = tree_fold_plus 
! 		(integer_type_node, 
! 		 tree_fold_floor_div (integer_type_node, 
! 				      tree_fold_minus (integer_type_node, 
! 						       init1, init0), 
! 				      step0), 
! 		 integer_one_node);
! 	    else
! 	      /* Example: "while ({2, +, 1}_2 <= {3, +, 1}_1)".  */
! 	      return chrec_top;
! 	  }
! 	
! 	/* Verify the result.  */
! 	if (evolution_function_is_constant_p (chrec1)
! 	    && tree_is_gt (tree_fold_plus (type0, init0, 
! 					   tree_fold_multiply 
! 					   (integer_type_node, 
! 					    nb_iters, step0)), 
! 			   init1))
! 	  return nb_iters;
! 	
! 	else 
! 	  /* Difficult cases fall down there.  */
! 	  return chrec_top;
!       }
        
!     case LT_EXPR:
!       {
! 	if (tree_is_ge (init0, init1))
! 	  {
! 	    if (evolution_function_is_constant_p (chrec1))
! 	      /* Example: "while ({2, +, 1}_2 < 0)".  */
! 	      return integer_zero_node;
! 	    
! 	    else
! 	      /* Example: "while ({2, +, 1}_2 < {0, +, 1}_1)".  */
! 	      return chrec_top;
! 	  }
! 	
! 	if (tree_int_cst_sgn (step0) < 0)
! 	  {
! 	    if (evolution_function_is_constant_p (chrec1))
! 	      /* Example: "while ({2, +, -1}_2 < 3)".  */
! 	      return chrec_top;
! 	    /* nb_iters = tree_fold_ceil_div 
! 	       (integer_type_node, 
! 	       tree_fold_minus (integer_type_node, init0, tmin), 
! 	       tree_fold_abs (integer_type_node, step0));
! 	    */
! 	    else
! 	      /* Example: "while ({2, +, -1}_2 < {3, +, 1}_1)".  */
! 	      return chrec_top;
! 	  }
! 	else 
! 	  {
! 	    if (evolution_function_is_constant_p (chrec1))
! 	      /* Example: "while ({2, +, 1}_2 < 3)".  */
! 	      nb_iters = tree_fold_ceil_div
! 		(integer_type_node, 
! 		 tree_fold_minus (integer_type_node, init1, init0), 
! 		 step0);
! 	    else
! 	      /* Example: "while ({2, +, 1}_2 < {3, +, 1}_1)".  */
! 	      return chrec_top;
! 	  }
! 	
! 	/* Verify the result.  */
! 	if (evolution_function_is_constant_p (chrec1)
! 	    && tree_is_ge (tree_fold_plus (type0, init0, 
! 					   tree_fold_multiply 
! 					   (integer_type_node, 
! 					    nb_iters, step0)),
! 			   init1))
! 	  return nb_iters;
! 	
! 	else 
! 	  /* Difficult cases fall down there.  */
! 	  return chrec_top;
!       }
        
!     case EQ_EXPR:
!       {
! 	if (tree_is_ne (init0, init1))
! 	  {
! 	    if (evolution_function_is_constant_p (chrec1))
! 	      /* Example: "while ({2, +, 1}_2 == 0)".  */
! 	      return integer_zero_node;
! 	    else
! 	      /* Example: "while ({2, +, -1}_2 == {0, +, 1}_1)".  */
! 	      return chrec_top;
! 	  }
! 	
! 	if (evolution_function_is_constant_p (chrec1))
! 	  {
! 	    if (integer_zerop (step0))
! 	      /* Example: "while ({2, +, 0}_2 == 2)".  */
! 	      return chrec_bot;
! 	    else
! 	      return integer_one_node;
! 	  }
! 	else
! 	  return chrec_top;
!       }	
        
!     case NE_EXPR:
!       {
! 	if (tree_is_eq (init0, init1))
! 	  {
! 	    if (evolution_function_is_constant_p (chrec1))
! 	      /* Example: "while ({0, +, 1}_2 != 0)".  */
! 	      return integer_zero_node;
! 	    else
! 	      /* Example: "while ({0, +, -1}_2 != {0, +, 1}_1)".  */
! 	      return chrec_top;
! 	  }
! 	
! 	if (tree_int_cst_sgn (step0) > 0)
! 	  {
! 	    if (evolution_function_is_constant_p (chrec1))
! 	      {
! 		if (tree_is_lt (init0, init1))
! 		  {
! 		    tree diff = tree_fold_minus (integer_type_node, 
! 						 init1, init0);
! 		    if (tree_fold_divides_p (integer_type_node, step0, diff))
! 		      /* Example: "while ({2, +, 1}_2 != 3)".  */
! 		      nb_iters = tree_fold_exact_div 
! 			(integer_type_node, diff, step0);
! 		    else
! 		      /* Example: "while ({2, +, 2}_2 != 3)".  */
! 		      return chrec_top;
! 		  }
! 		else
! 		  /* Example: "while ({3, +, 1}_2 != 2)".  */
! 		  return chrec_top;
! 	      }
! 	    else
! 	      /* Example: "while ({2, +, 1}_2 != {3, +, 1}_1)".  */
! 	      return chrec_top;
! 	  }
! 	
! 	else
! 	  {
! 	    if (evolution_function_is_constant_p (chrec1))
! 	      {
! 		if (tree_is_gt (init0, init1))
! 		  {
! 		    tree diff = tree_fold_minus (integer_type_node, 
! 						 init0, init1);
! 		    if (tree_fold_divides_p (integer_type_node, step0, diff))
! 		      /* Example: "while ({3, +, -1}_2 != 2)".  */
! 		      nb_iters = tree_fold_exact_div 
! 			(integer_type_node, diff, 
! 			 tree_fold_abs (integer_type_node, step0));
! 		    else
! 		      /* Example: "while ({3, +, -2}_2 != 2)".  */
! 		      return chrec_top;
! 		  }
! 		else
! 		  /* Example: "while ({2, +, -1}_2 != 3)".  */
! 		  return chrec_top;
! 	      }
! 	    else
! 	      /* Example: "while ({2, +, -1}_2 != {3, +, -1}_1)".  */
! 	      return chrec_top;
! 	  }
  
! 	/* Verify the result.  */
! 	if (evolution_function_is_constant_p (chrec1)
! 	    && tree_is_eq (tree_fold_plus (type0, init0, 
! 					   tree_fold_multiply 
! 					   (integer_type_node, 
! 					    nb_iters, step0)),
! 			   init1))
! 	  return nb_iters;
! 	else 
! 	  /* Difficult cases fall down there.  */
! 	  return chrec_top;
!       }
        
!     default:
!       return chrec_top;
      }
    
!   return chrec_top;
  }
  
! /* Helper function for the case when both CHREC0 and CHREC1 has an
!    evolution in the considered loop.  */
  
  static tree 
! first_iteration_non_satisfying_ev_ev (enum tree_code code, 
! 				      unsigned loop_nb ATTRIBUTE_UNUSED, 
! 				      tree chrec0 ATTRIBUTE_UNUSED, 
! 				      tree chrec1 ATTRIBUTE_UNUSED)
  {
+   switch (code)
+     {
+     case LE_EXPR:
+       
+     case LT_EXPR:
+       
+     case EQ_EXPR:
+       
+     case NE_EXPR:
+       
+     default:
+       return chrec_top;
+     }
+   
    return chrec_top;
  }
  
! /* Helper function.  */
  
  static tree 
! first_iteration_non_satisfying_1 (enum tree_code code, 
! 				  unsigned loop_nb, 
! 				  tree chrec0, 
! 				  tree chrec1)
  {
!   if (automatically_generated_chrec_p (chrec0)
!       || automatically_generated_chrec_p (chrec1))
!     return chrec_top;
!   
!   if (no_evolution_in_loop_p (chrec0, loop_nb))
!     {
!       if (no_evolution_in_loop_p (chrec1, loop_nb))
! 	return first_iteration_non_satisfying_noev_noev (code, loop_nb, 
! 							 chrec0, chrec1);
!       else
! 	return first_iteration_non_satisfying_noev_ev (code, loop_nb, 
! 						       chrec0, chrec1);
!     }
!   
!   else
!     {
!       if (no_evolution_in_loop_p (chrec1, loop_nb))
! 	return first_iteration_non_satisfying_ev_noev (code, loop_nb, 
! 						       chrec0, chrec1);
!       else
! 	return first_iteration_non_satisfying_ev_ev (code, loop_nb, 
! 						     chrec0, chrec1);
!     }
! }
! 
! /* Try to compute the first iteration I of LOOP_NB that does not satisfy
!    CODE: in the context of the computation of the number of iterations:
!    - if (CODE is LE_EXPR) the loop exits when CHREC0 (I) > CHREC1 (I),
!    - if (CODE is LT_EXPR) the loop exits when CHREC0 (I) >= CHREC1 (I),
!    - if (CODE is EQ_EXPR) the loop exits when CHREC0 (I) != CHREC1 (I), 
!    ...
!    
!    The result is one of the following: 
!    - CHREC_TOP when the analyzer cannot determine the property, 
!    - CHREC_BOT when the property is always true, 
!    - an INTEGER_CST tree node, 
!    - a CHREC, 
!    - an expression containing SSA_NAMEs.
! */
! 
! tree 
! first_iteration_non_satisfying (enum tree_code code, 
! 				unsigned loop_nb, 
! 				tree chrec0, 
! 				tree chrec1)
! {
!   switch (code)
!     {
!     case LT_EXPR:
!       return first_iteration_non_satisfying_1 (LT_EXPR, loop_nb, 
! 					       chrec0, chrec1);
!       
!     case LE_EXPR:
!       return first_iteration_non_satisfying_1 (LE_EXPR, loop_nb, 
! 					       chrec0, chrec1);
!       
!     case GT_EXPR:
!       return first_iteration_non_satisfying_1 (LT_EXPR, loop_nb, 
! 					       chrec1, chrec0);
!       
!     case GE_EXPR:
!       return first_iteration_non_satisfying_1 (LE_EXPR, loop_nb, 
! 					       chrec1, chrec0);
!       
!     case EQ_EXPR:
!       return first_iteration_non_satisfying_1 (EQ_EXPR, loop_nb, 
! 					       chrec0, chrec1);
!       
!     case NE_EXPR:
!       return first_iteration_non_satisfying_1 (NE_EXPR, loop_nb, 
! 					       chrec0, chrec1);
!       
!     default:
!       return chrec_top;
!     }
  }
  
  /* Helper function.  */
*************** set_nb_iterations_in_loop (struct loop *
*** 1630,1635 ****
--- 2055,2067 ----
    /* After the loop copy headers has transformed the code, each loop
       runs at least once.  */
    res = chrec_fold_plus (chrec_type (res), res, integer_one_node);
+   /* FIXME HWI: However we want to store one iteration less than the
+      count of the loop in order to be compatible with the other
+      nb_iter computations in loop-iv.  This also allows the
+      representation of nb_iters that are equal to MAX_INT.  */
+   if (TREE_CODE (res) == INTEGER_CST
+       && TREE_INT_CST_LOW (res) == 0)
+     res = chrec_top;
    
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
*************** follow_ssa_edge_in_condition_phi (unsign
*** 2103,2108 ****
--- 2535,2543 ----
    tree evolution_of_branch;
    tree init_cond = initial_condition (*evolution_of_loop);
    
+   /* Disabled for the moment.  */
+   return false;
+   
    res = follow_ssa_edge_in_condition_phi_branch 
      (0, loop_nb, condition_phi, halting_phi, &evolution_of_branch, init_cond);
    
*************** number_of_iterations_in_loop (struct loo
*** 2852,2858 ****
        
        else
  	return set_nb_iterations_in_loop 
! 	  (loop, nb_iterations_ne (loop_nb, chrec0, chrec1));
        
      case LT_EXPR:
      case LE_EXPR:
--- 3287,3294 ----
        
        else
  	return set_nb_iterations_in_loop 
! 	  (loop, first_iteration_non_satisfying (NE_EXPR, loop_nb, 
! 						 chrec0, chrec1));
        
      case LT_EXPR:
      case LE_EXPR:
*************** number_of_iterations_in_loop (struct loo
*** 2891,2926 ****
        if (chrec_contains_undetermined (chrec0)
  	  || chrec_contains_undetermined (chrec1))
  	return cannot_analyze_loop_nb_iterations_yet ();
! 	
!       switch (TREE_CODE (test))
! 	{
! 	case LT_EXPR:
! 	  return set_nb_iterations_in_loop 
! 	    (loop, nb_iterations_less (LT_EXPR, loop_nb, chrec0, chrec1));
! 	  
! 	case LE_EXPR:
! 	  return set_nb_iterations_in_loop 
! 	    (loop, nb_iterations_less (LE_EXPR, loop_nb, chrec0, chrec1));
! 	  
! 	case GT_EXPR:
! 	  return set_nb_iterations_in_loop 
! 	    (loop, nb_iterations_less (LT_EXPR, loop_nb, chrec1, chrec0));
! 	  
! 	case GE_EXPR:
! 	  return set_nb_iterations_in_loop 
! 	    (loop, nb_iterations_less (LE_EXPR, loop_nb, chrec1, chrec0));
! 	  
! 	case EQ_EXPR:
! 	  return set_nb_iterations_in_loop 
! 	    (loop, nb_iterations_eq (loop_nb, chrec0, chrec1));
! 	  
! 	case NE_EXPR:
! 	  return set_nb_iterations_in_loop 
! 	    (loop, nb_iterations_ne (loop_nb, chrec0, chrec1));
! 	  
! 	default:
! 	  return set_nb_iterations_in_loop (loop, chrec_top);
! 	}
        
      default:
        return set_nb_iterations_in_loop (loop, chrec_top);
--- 3327,3336 ----
        if (chrec_contains_undetermined (chrec0)
  	  || chrec_contains_undetermined (chrec1))
  	return cannot_analyze_loop_nb_iterations_yet ();
!       
!       return set_nb_iterations_in_loop 
! 	(loop, first_iteration_non_satisfying (TREE_CODE (test), loop_nb, 
! 					       chrec0, chrec1));
        
      default:
        return set_nb_iterations_in_loop (loop, chrec_top);
*************** static inline void
*** 2952,2958 ****
  reset_chrecs_counters (void)
  {
    stats_nb_chrecs = 0;
!   stats_nb_peeled = 0;
    stats_nb_affine = 0;
    stats_nb_affine_multivar = 0;
    stats_nb_higher_poly = 0;
--- 3362,3368 ----
  reset_chrecs_counters (void)
  {
    stats_nb_chrecs = 0;
!   stats_nb_peeled_affine = 0;
    stats_nb_affine = 0;
    stats_nb_affine_multivar = 0;
    stats_nb_higher_poly = 0;
*************** gather_chrec_stats (FILE *file, tree chr
*** 2972,2977 ****
--- 3382,3390 ----
    print_generic_expr (file, chrec, 0);
    fprintf (file, "\n");
  
+   if (chrec == NULL_TREE)
+     return;
+   
    switch (TREE_CODE (chrec))
      {
      case POLYNOMIAL_CHREC:
*************** gather_chrec_stats (FILE *file, tree chr
*** 2987,2992 ****
--- 3400,3411 ----
  	  stats_nb_affine_multivar++;
  	}
        
+       else if (evolution_function_is_peeled_affine_p (chrec))
+ 	{
+ 	  fprintf (file, "  peeled_affine\n");
+ 	  stats_nb_peeled_affine++;
+ 	}
+       
        else
  	{
  	  fprintf (file, "  higher_degree_polynomial\n");
*************** gather_chrec_stats (FILE *file, tree chr
*** 2995,3005 ****
        
        break;
        
-     case PEELED_CHREC:
-       stats_nb_peeled++;
-       fprintf (file, "  peeled\n");
-       break;
-       
      case EXPONENTIAL_CHREC:
        stats_nb_expo++;
        fprintf (file, "  exponential\n");
--- 3414,3419 ----
*************** gather_chrec_stats (FILE *file, tree chr
*** 3015,3021 ****
  	{
  	  stats_nb_interval_chrec++;
  	  fprintf (file, "  interval chrec\n");
! 	}	  
        break;
        
      default:
--- 3429,3435 ----
  	{
  	  stats_nb_interval_chrec++;
  	  fprintf (file, "  interval chrec\n");
! 	}
        break;
        
      default:
*************** gather_chrec_stats (FILE *file, tree chr
*** 3029,3035 ****
      }
    
    fprintf (file, ")\n");
- 	      
  }
  
  /* Dump the stats about the chrecs.  */
--- 3443,3448 ----
*************** dump_chrecs_stats (FILE *file)
*** 3040,3055 ****
    fprintf (file, "\n(\n");
    fprintf (file, "-----------------------------------------\n");
    fprintf (file, "%d\taffine univariate chrecs\n", stats_nb_affine);
!   fprintf (file, "%d\taffine multivariate chrecs\n", stats_nb_affine_multivar);
!   fprintf (file, "%d\tdegree greater than 2 polynomials\n", stats_nb_higher_poly);
!   fprintf (file, "%d\tpeeled chrecs\n", stats_nb_peeled);
    fprintf (file, "%d\texponential chrecs\n", stats_nb_expo);
    fprintf (file, "%d\tchrec_top chrecs\n", stats_nb_chrec_top);
    fprintf (file, "%d\tinterval chrecs\n", stats_nb_chrec_top);
    fprintf (file, "-----------------------------------------\n");
    fprintf (file, "%d\ttotal chrecs\n", stats_nb_chrecs);
    fprintf (file, "-----------------------------------------\n");
!   fprintf (file, "%d\twith undetermined coefficients\n", stats_nb_undetermined);
    fprintf (file, "-----------------------------------------\n");
    fprintf (file, ")\n\n");
  }
--- 3453,3473 ----
    fprintf (file, "\n(\n");
    fprintf (file, "-----------------------------------------\n");
    fprintf (file, "%d\taffine univariate chrecs\n", stats_nb_affine);
!   fprintf (file, "%d\taffine multivariate chrecs\n", 
! 	   stats_nb_affine_multivar);
!   fprintf (file, "%d\tdegree greater than 2 polynomials\n", 
! 	   stats_nb_higher_poly);
!   fprintf (file, "%d\taffine peeled chrecs\n", stats_nb_peeled_affine);
    fprintf (file, "%d\texponential chrecs\n", stats_nb_expo);
    fprintf (file, "%d\tchrec_top chrecs\n", stats_nb_chrec_top);
    fprintf (file, "%d\tinterval chrecs\n", stats_nb_chrec_top);
    fprintf (file, "-----------------------------------------\n");
    fprintf (file, "%d\ttotal chrecs\n", stats_nb_chrecs);
+   fprintf (file, "%d\twith undetermined coefficients\n", 
+ 	   stats_nb_undetermined);
    fprintf (file, "-----------------------------------------\n");
!   fprintf (file, "%d\tchrecs in the scev database\n", 
! 	   VARRAY_ACTIVE_SIZE (*scalar_evolution_info));
    fprintf (file, "-----------------------------------------\n");
    fprintf (file, ")\n\n");
  }
*************** analyze_scalar_evolution_for_all_loop_ph
*** 3097,3102 ****
--- 3515,3542 ----
    
    if (dump_file && (dump_flags & TDF_STATS))
      dump_chrecs_stats (dump_file);
+ }
+ 
+ /* Classify the chrecs of the whole database.  */
+ 
+ void 
+ gather_stats_on_scev_database (void)
+ {
+   unsigned i;
+   
+   if (!dump_file)
+     return;
+   
+   reset_chrecs_counters ();  
+   
+   for (i = 0; i < VARRAY_ACTIVE_SIZE (*scalar_evolution_info); i++)
+     {
+       struct scev_info_str *elt = 
+ 	VARRAY_GENERIC_PTR (*scalar_evolution_info, i);
+       gather_chrec_stats (dump_file, MI_INNER_LOOPS_CHREC (elt));
+     }
+   
+   dump_chrecs_stats (dump_file);
  }
  
  
Index: tree-scalar-evolution.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.h,v
retrieving revision 1.1.2.7
diff -c -3 -p -r1.1.2.7 tree-scalar-evolution.h
*** tree-scalar-evolution.h	23 Mar 2004 20:13:28 -0000	1.1.2.7
--- tree-scalar-evolution.h	30 Mar 2004 14:44:06 -0000
*************** Software Foundation, 59 Temple Place - S
*** 22,27 ****
--- 22,29 ----
  #ifndef GCC_TREE_SCALAR_EVOLUTION_H
  #define GCC_TREE_SCALAR_EVOLUTION_H
  
+ extern tree first_iteration_non_satisfying (enum tree_code, unsigned, 
+ 					    tree, tree);
  extern tree number_of_iterations_in_loop (struct loop *);
  extern tree get_loop_exit_condition (struct loop *);
  
*************** extern void scev_finalize (void);
*** 30,35 ****
--- 32,38 ----
  extern tree analyze_scalar_evolution (unsigned, tree);
  extern tree instantiate_parameters (unsigned, tree);
  extern void eliminate_redundant_checks (void);
+ extern void gather_stats_on_scev_database (void);
  
  
  struct scev_info_str {


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