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]

[killloop] Improve handling of decreasing ivs


Hello,

on code like

for (i = 99; i >= 0; i--)
  something (a[i]);

ivopts tend to rewrite the loop to

for (i = 99; i != -1; i--)
  something (a[i]);

or

for (p = &a[99]; p != -sizeof(a[0]); p -= sizeof(a[0]))
  something (*p);

Which is OK, but on many architectures comparing with zero is more
profitable.  This patch makes ivopts to prefer the comparison with
zero.

Even more curiously, ivopts may sometimes decide to use

for (i = 0; i != -99; i--)
  something (a[99 + i]);

(this also is not bad on i686, but somewhat counterintuitive).  This is caused by:
1) Definition of address cost for i686, that considers more complex
   addressing modes to be cheaper (which is intended to cause CSE to
   use them).
2) add_old_iv_candidates by always proposing the candidate with initial
   value zero.  With this patch, it suggests a candidate with final
   value zero instead for decreasing ivs, which usually makes more
   sense.

The patch also implements a small improvement to the iv selection, that
fixes some cases where we select a slightly suboptimal iv and we are
unable to select a better one because we are stuck in local minimum.

Zdenek

Index: ChangeLog.killloop
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.killloop,v
retrieving revision 1.1.2.7
diff -c -3 -p -r1.1.2.7 ChangeLog.killloop
*** ChangeLog.killloop	31 Aug 2005 10:09:58 -0000	1.1.2.7
--- ChangeLog.killloop	2 Sep 2005 09:16:20 -0000
***************
*** 1,3 ****
--- 1,35 ----
+ 2005-09-02  Zdenek Dvorak  <dvorakz@suse.cz>
+ 
+ 	* Makefile.in (tree-ssa-loop-endcond.o): Add.
+ 	* tree-flow.h (select_condition_shape): Declare.
+ 	* tree-ssa-loop-endcond.c: New file.
+ 	* tree-ssa-loop-ivcanon.c: Extend comments.
+ 	* tree-ssa-loop-ivopts.c (struct cost_pair): Add cmp field.
+ 	(add_iv_value_candidates): Add all_important argument.  For decreasing
+ 	ivs, add iv with final value zero.
+ 	(add_old_iv_candidates): Use add_iv_value_candidates.
+ 	(add_derived_ivs_candidates): Add argument to add_iv_value_candidates.
+ 	(set_use_iv_cost): Add cmp argument.
+ 	(set_use_iv_cost_infinity, set_use_iv_cost_zero,
+ 	set_use_iv_cost_generic, set_use_iv_cost_outer,
+ 	set_use_iv_cost_compare): New functions.
+ 	(determine_use_iv_cost_generic, determine_use_iv_cost_address,
+ 	determine_use_iv_cost_outer): Use them.
+ 	(cand_value_at, iv_elimination_compare): Removed.
+ 	(iv_period): Moved to tree-ssa-loop-endcond.c.
+ 	(may_eliminate_iv): Use select_condition_shape.
+ 	(compare_cost): New function.
+ 	(determine_use_iv_cost_condition): Use set_use_iv_cost_compare and
+ 	compare_cost.
+ 	(determine_use_iv_costs): Dump value and cmp fields of cost pair.
+ 	(try_replacing_cands, minor_adjustments): New functions.
+ 	(find_optimal_iv_set): Call minor_adjustments.
+ 	(rewrite_use_compare): Use cmp field of cost pair.
+ 	* tree-ssa-loop-niter.c (zero_p, nonzero_p): Moved to ...
+ 	* tree.c (zero_p, nonzero_p): ... here.
+ 	(signed_type_for): Generate a signed integer type for pointers.
+ 	* tree.h (nonzero_p): Declare.
+ 
  2005-08-31  Zdenek Dvorak  <dvorakz@suse.cz>
  
  	* tree-ssa-loop-ivopts.c (AVG_LOOP_NITER): Use
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1530.2.2
diff -c -3 -p -r1.1530.2.2 Makefile.in
*** Makefile.in	30 Aug 2005 09:31:49 -0000	1.1530.2.2
--- Makefile.in	2 Sep 2005 09:16:21 -0000
*************** OBJS-common = \
*** 941,947 ****
   tree-ssa-loop-manip.o tree-ssa-threadupdate.o				   \
   tree-vectorizer.o tree-vect-analyze.o tree-vect-transform.o		   \
   tree-ssa-loop-ivcanon.o tree-ssa-propagate.o tree-ssa-address.o	   \
!  tree-ssa-math-opts.o							   \
   tree-ssa-loop-ivopts.o tree-if-conv.o tree-ssa-loop-unswitch.o		   \
   alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o	  	   \
   cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o		   \
--- 941,947 ----
   tree-ssa-loop-manip.o tree-ssa-threadupdate.o				   \
   tree-vectorizer.o tree-vect-analyze.o tree-vect-transform.o		   \
   tree-ssa-loop-ivcanon.o tree-ssa-propagate.o tree-ssa-address.o	   \
!  tree-ssa-math-opts.o tree-ssa-loop-endcond.o				   \
   tree-ssa-loop-ivopts.o tree-if-conv.o tree-ssa-loop-unswitch.o		   \
   alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o	  	   \
   cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o		   \
*************** tree-ssa-loop-ivopts.o : tree-ssa-loop-i
*** 1894,1899 ****
--- 1894,1905 ----
     tree-pass.h $(GGC_H) $(RECOG_H) insn-config.h $(HASHTAB_H) $(SCEV_H) \
     $(CFGLOOP_H) $(PARAMS_H) langhooks.h $(BASIC_BLOCK_H) hard-reg-set.h \
     tree-chrec.h $(VARRAY_H)
+ tree-ssa-loop-endcond.o : tree-ssa-loop-endcond.c $(TREE_FLOW_H) $(CONFIG_H) \
+    $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) $(EXPR_H) \
+    output.h $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
+    tree-pass.h $(GGC_H) $(RECOG_H) insn-config.h $(HASHTAB_H) $(SCEV_H) \
+    $(CFGLOOP_H) $(PARAMS_H) langhooks.h $(BASIC_BLOCK_H) hard-reg-set.h \
+    tree-chrec.h $(VARRAY_H)
  tree-ssa-loop-manip.o : tree-ssa-loop-manip.c $(TREE_FLOW_H) $(CONFIG_H) \
     $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) \
     output.h $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.130
diff -c -3 -p -r2.130 tree-flow.h
*** tree-flow.h	25 Jul 2005 12:04:49 -0000	2.130
--- tree-flow.h	2 Sep 2005 09:16:21 -0000
*************** struct loop *tree_ssa_loop_version (stru
*** 752,757 ****
--- 752,758 ----
  tree expand_simple_operations (tree);
  void substitute_in_loop_info (struct loop *, tree, tree);
  edge single_dom_exit (struct loop *);
+ bool select_condition_shape (tree, tree, tree, bool, enum tree_code *, tree *);
  
  /* In tree-ssa-loop-im.c  */
  /* The possibilities of statement movement.  */
Index: tree-ssa-loop-endcond.c
===================================================================
RCS file: tree-ssa-loop-endcond.c
diff -N tree-ssa-loop-endcond.c
*** /dev/null	1 Jan 1970 00:00:00 -0000
--- tree-ssa-loop-endcond.c	2 Sep 2005 09:16:21 -0000
***************
*** 0 ****
--- 1,267 ----
+ /* Loop exit test optimizations.
+    Copyright (C) 2005 Free Software Foundation, Inc.
+    
+ This file is part of GCC.
+    
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by the
+ Free Software Foundation; either version 2, or (at your option) any
+ later version.
+    
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+    
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING.  If not, write to the Free
+ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA.  */
+ 
+ /* This file implements optimizations with goal to transform the loop so that
+    testing of the ending condition is as cheap as possible.  Concretely:
+ 
+    -- loop reversal.  Loops are reversed if
+       1) they can be
+ 	   -- data dependences are OK
+ 	   -- number of iterations of the loop can be determined
+       2) it won't spoil the code
+ 	   -- on targets where traversing arrays in forward direction is more
+ 	      profitable, we do not make more arrays to be traversed backwards.
+ 	   -- initial values of ivs for the new loop are not too costly to
+ 	      compute.
+       3) it is usefull
+            -- there is an induction variable whose initial value is a constant,
+ 	      such that this iv may be used in the exit test.  And there is no
+ 	      iv whose final value would be a nicer constant such that this iv
+ 	      is used for anything else but the exit test.
+ 
+    -- condition shape selection.  We try to transform the condition so that it
+       performs compare with zero, which often is less expensive, or make the
+       value compared with simpler:
+       -- if we compare an induction variable X with value BASE - STEP * i
+          ((signed) STEP > 0), whose final value V satisfies
+ 	 -STEP <= V < 0 and whose initial value satisfies (signed) BASE >= 0,
+ 	 we use (signed) X >= 0 compare.
+       -- if X = BASE + STEP * i and final value V is of shape V' + C, where
+          0 < C <= STEP, and there is no overflow, then we use
+ 	 X <= V' compare.
+       -- otherwise we use X != V compare.
+       
+    TODO: implement loop reversal
+ 	 addition removal in condition shape selection
+ 	 use information about bounds on number of iterations in condition
+ 	   shape selection  */
+ 
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "tree.h"
+ #include "rtl.h"
+ #include "tm_p.h"
+ #include "hard-reg-set.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "diagnostic.h"
+ #include "tree-flow.h"
+ #include "tree-dump.h"
+ #include "timevar.h"
+ #include "cfgloop.h"
+ #include "varray.h"
+ #include "expr.h"
+ #include "tree-pass.h"
+ #include "ggc.h"
+ #include "insn-config.h"
+ #include "recog.h"
+ #include "hashtab.h"
+ #include "tree-chrec.h"
+ #include "tree-scalar-evolution.h"
+ #include "cfgloop.h"
+ #include "params.h"
+ #include "langhooks.h"
+ 
+ /* Returns period of induction variable with step STEP.  */
+ 
+ static tree
+ iv_period (tree step)
+ {
+   tree period, type, 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;
+ }
+ 
+ /* Given exit condition based on induction variable BASE + STEP * i,
+    whose final value is *BOUND, try altering comparison operator *CMP so
+    that the *BOUND can be replaced by zero.  Return true if this succeeds,
+    false otherwise.  */
+ 
+ static bool
+ modify_to_compare_with_zero (tree base, tree step,
+ 			     enum tree_code *cmp, tree *bound)
+ {
+   tree type = TREE_TYPE (step), signed_type = signed_type_for (type);
+   tree signed_bound = fold_convert (signed_type, *bound);
+   tree signed_step = fold_convert (signed_type, step);
+   tree signed_base = fold_convert (signed_type, base);
+   tree signed_zero = build_int_cst_type (signed_type, 0);
+ 
+   if (tree_int_cst_sign_bit (step))
+     {
+       step = fold_build1 (NEGATE_EXPR, type, step);
+       if (tree_int_cst_sign_bit (step))
+ 	{
+ 	  /* step = 0x7ffff... Rather avoid doing anything.  Nobody uses such
+ 	     an iv, anyway.  */
+ 	  return false;
+ 	}
+ 
+       /* Condition in shape base - step * i.  Check whether
+ 	 -step <= bound < 0.  */
+       if (!nonzero_p (fold_build2 (LE_EXPR, boolean_type_node,
+ 				   signed_step, signed_bound))
+ 	  || !nonzero_p (fold_build2 (LT_EXPR, boolean_type_node,
+ 				      signed_bound, signed_zero))
+ 	  /* We can apply the optimization, assuming that BASE >= 0.  */
+ 	  || !nonzero_p (fold_build2 (GE_EXPR, boolean_type_node,
+ 				      signed_base, signed_zero)))
+ 	return false;
+ 
+       *cmp = GE_EXPR;
+     }
+   else
+     {
+       /* Condition in shape base + step * i.  This case does not appear as
+ 	 often in practice, but let's try anyway.  Check whether
+ 	 0 < bound <= step.  */
+       if (!nonzero_p (fold_build2 (LT_EXPR, boolean_type_node,
+ 				   signed_zero, signed_bound))
+ 	  || !nonzero_p (fold_build2 (LE_EXPR, boolean_type_node,
+ 				      signed_bound, signed_step))
+ 	  /* We can apply the optimization, assuming that BASE <= 0.  */
+ 	  || !nonzero_p (fold_build2 (LE_EXPR, boolean_type_node,
+ 				      signed_base, signed_zero)))
+ 	return false;
+ 
+       *cmp = LE_EXPR;
+     }
+   
+   *bound = signed_zero;
+   return true;
+ }
+ 
+ /* Given exit condition based on induction variable BASE + STEP * i,
+    whose final value is *BOUND, try altering comparison operator *CMP and
+    *BOUND so that *BOUND does not contain unnecessary additions.  Return
+    true if this succeeds, false otherwise.  */
+ 
+ static bool
+ try_removing_addition_from_bound (tree base ATTRIBUTE_UNUSED,
+ 				  tree step ATTRIBUTE_UNUSED,
+ 				  enum tree_code *cmp ATTRIBUTE_UNUSED,
+ 				  tree *bound ATTRIBUTE_UNUSED)
+ {
+   /* NIY.  */
+   return false;
+ }
+ 
+ /* Check whether iv with step STEP wraps around the range of the type
+    after at most NITER iterations.  */
+ 
+ static bool
+ may_wrap_around_type_range_p (tree niter, tree step)
+ {
+   tree unsigned_type = unsigned_type_for (TREE_TYPE (step));
+   tree range = iv_period (build_int_cst_type (unsigned_type, 1));
+ 
+   step = fold_convert (unsigned_type, step);
+   if (tree_int_cst_sign_bit (step))
+     step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
+   if (tree_int_cst_sign_bit (step))
+     return true;
+   niter = fold_convert (unsigned_type, niter);
+  
+   /* We need to check whether niter * step <= range.  */
+   range = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, range, step);
+   return !nonzero_p (fold_build2 (LE_EXPR, boolean_type_node, niter, range));
+ }
+ 
+ /* Given an exit condition comparing an induction variable with value
+    BASE + STEP * i, such that the condition should be true
+    (false if EXIT_P is true) for exactly NITER iterations, choose a best shape
+    for the comparison.  Store the value to compare with to BOUND and the
+    comparison operator to CMP.  Signedness of BOUND and the variable may
+    differ; in that case, the induction variable must be cast to the type of
+    BOUND before comparing.
+    
+    Returns false if we are unable to find any suitable compare shape, true
+    if we succeed.  */
+ 
+ bool
+ select_condition_shape (tree niter, tree base, tree step,
+ 			bool exit_p, enum tree_code *cmp, tree *bound)
+ {
+   tree nit_type = TREE_TYPE (niter), per_type, wider_type;
+   tree iv_type = TREE_TYPE (step);
+   tree period, final;
+ 
+   /* To have chance to use this induction variable, its period must be at least
+      as large as the number of iterations.  */
+   period = iv_period (step);
+   per_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, niter))))
+     return false;
+ 
+   /* Determine the final value of the iv.  */
+   final = fold_build2 (PLUS_EXPR, iv_type, base,
+ 		       fold_build2 (MULT_EXPR, iv_type, step,
+ 				    fold_convert (iv_type, niter)));
+ 
+   /* At this point, we know that we can express the condition as
+      IV != FINAL.  */
+   *bound = final;
+   *cmp = NE_EXPR;
+ 
+   /* If final value is zero, this is the ideal shape.  */
+   if (zero_p (final))
+     goto end;
+ 
+   /* Check whether the variable wraps around the type range, i.e., whether
+      niter * step >= range.  If this is the case, we cannot do any of the
+      following optimizations.  */
+   if (may_wrap_around_type_range_p (niter, step))
+     goto end;
+ 
+   /* Else try transforming the condition to a compare with zero.  */
+   if (!modify_to_compare_with_zero (base, step, cmp, bound))
+     {
+       /* If everything else failed, try removing addition or subtraction
+ 	 from the bound.  */
+       try_removing_addition_from_bound (base, step, cmp, bound);
+     }
+ 
+ end:
+   if (exit_p)
+     *cmp = invert_tree_comparison (*cmp, false);
+ 
+   return true;
+ }
Index: tree-ssa-loop-ivcanon.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivcanon.c,v
retrieving revision 2.18
diff -c -3 -p -r2.18 tree-ssa-loop-ivcanon.c
*** tree-ssa-loop-ivcanon.c	21 Jul 2005 07:24:10 -0000	2.18
--- tree-ssa-loop-ivcanon.c	2 Sep 2005 09:16:21 -0000
*************** Software Foundation, 51 Franklin Street,
*** 21,33 ****
  /* This pass detects the loops that iterate a constant number of times,
     adds a canonical induction variable (step -1, tested against 0) 
     and replaces the exit test.  This enables the less powerful rtl
!    level analysis to use this information.
! 
!    This might spoil the code in some cases (by increasing register pressure).
!    Note that in the case the new variable is not needed, ivopts will get rid
!    of it, so it might only be a problem when there are no other linear induction
!    variables.  In that case the created optimization possibilities are likely
!    to pay up.
  
     Additionally in case we detect that it is beneficial to unroll the
     loop completely, we do it right here to expose the optimization
--- 21,37 ----
  /* This pass detects the loops that iterate a constant number of times,
     adds a canonical induction variable (step -1, tested against 0) 
     and replaces the exit test.  This enables the less powerful rtl
!    level analysis to use this information.  Also, this iv may happen
!    to be a good choice for the exit test, especially if comparison with
!    non-zero is expensive.
! 
!    This optimization might spoil the code in some cases (by increasing register
!    pressure, and introducing overheades for extra iv).  Note that in the case
!    the new variable is not needed, ivopts will get rid of it, so it might only
!    be a problem when there are no other linear induction variables.  In that
!    case the created optimization possibilities (possibility to unroll the loop
!    and to use decrease-and-branch instruction as loop exit) are likely to
!    pay up.
  
     Additionally in case we detect that it is beneficial to unroll the
     loop completely, we do it right here to expose the optimization
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.85.2.1
diff -c -3 -p -r2.85.2.1 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c	31 Aug 2005 10:09:58 -0000	2.85.2.1
--- tree-ssa-loop-ivopts.c	2 Sep 2005 09:16:21 -0000
*************** struct cost_pair
*** 148,153 ****
--- 148,154 ----
    unsigned cost;	/* The cost.  */
    bitmap depends_on;	/* The list of invariants that have to be
  			   preserved.  */
+   enum tree_code cmp;	/* The comparison operator used in iv elimination.  */
    tree value;		/* For final value elimination, the expression for
  			   the final value of the iv.  For iv elimination,
  			   the new bound to compare with.  */
*************** add_standard_iv_candidates (struct ivopt
*** 2174,2179 ****
--- 2175,2218 ----
      add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE * 2);
  }
  
+ /* Adds candidates based on the value of the induction variable IV and USE.
+    If ALL_IMPORTANT is true, mark all the candidates as important.  */
+ 
+ static void
+ add_iv_value_candidates (struct ivopts_data *data,
+ 			 struct iv *iv, struct iv_use *use,
+ 			 bool all_important)
+ {
+   unsigned HOST_WIDE_INT offset;
+   tree base;
+   struct tree_niter_desc *niter = niter_for_single_dom_exit (data);
+   tree type = TREE_TYPE (iv->base);
+ 
+   add_candidate (data, iv->base, iv->step, all_important, use);
+ 
+   /* The same, but with initial value zero.  If the iv is decreasing,
+      try using a variable with final value zero instead.  Always make
+      such variable important, since it is generic enough so that possibly
+      many uses may be based on it.  */
+   if (TREE_CODE (iv->step) == INTEGER_CST
+       && tree_int_cst_sign_bit (iv->step)
+       && niter)
+     {
+       base = fold_build2 (MULT_EXPR, type,
+ 			  fold_convert (type, niter->niter),
+ 			  fold_build1 (NEGATE_EXPR, type, iv->step));
+       add_candidate (data, base, iv->step, true, use);
+     }
+   else
+     add_candidate (data, build_int_cst (type, 0),
+ 		   iv->step, true, use);
+ 
+   /* Third, try removing the constant offset.  */
+   base = strip_offset (iv->base, &offset);
+   if (offset)
+     add_candidate (data, base, iv->step, all_important, use);
+ }
+ 
  
  /* Adds candidates bases on the old induction variable IV.  */
  
*************** add_old_iv_candidates (struct ivopts_dat
*** 2183,2194 ****
    tree phi, def;
    struct iv_cand *cand;
  
!   add_candidate (data, iv->base, iv->step, true, NULL);
! 
!   /* The same, but with initial value zero.  */
!   add_candidate (data,
! 		 build_int_cst (TREE_TYPE (iv->base), 0),
! 		 iv->step, true, NULL);
  
    phi = SSA_NAME_DEF_STMT (iv->ssa_name);
    if (TREE_CODE (phi) == PHI_NODE)
--- 2222,2228 ----
    tree phi, def;
    struct iv_cand *cand;
  
!   add_iv_value_candidates (data, iv, NULL, true);
  
    phi = SSA_NAME_DEF_STMT (iv->ssa_name);
    if (TREE_CODE (phi) == PHI_NODE)
*************** add_old_ivs_candidates (struct ivopts_da
*** 2221,2249 ****
      }
  }
  
- /* Adds candidates based on the value of the induction variable IV and USE.  */
- 
- static void
- add_iv_value_candidates (struct ivopts_data *data,
- 			 struct iv *iv, struct iv_use *use)
- {
-   unsigned HOST_WIDE_INT offset;
-   tree base;
- 
-   add_candidate (data, iv->base, iv->step, false, use);
- 
-   /* The same, but with initial value zero.  Make such variable important,
-      since it is generic enough so that possibly many uses may be based
-      on it.  */
-   add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
- 		 iv->step, true, use);
- 
-   /* Third, try removing the constant offset.  */
-   base = strip_offset (iv->base, &offset);
-   if (offset)
-     add_candidate (data, base, iv->step, false, use);
- }
- 
  /* Possibly adds pseudocandidate for replacing the final value of USE by
     a direct computation.  */
  
--- 2255,2260 ----
*************** add_derived_ivs_candidates (struct ivopt
*** 2281,2291 ****
  	case USE_COMPARE:
  	case USE_ADDRESS:
  	  /* Just add the ivs based on the value of the iv used here.  */
! 	  add_iv_value_candidates (data, use->iv, use);
  	  break;
  
  	case USE_OUTER:
! 	  add_iv_value_candidates (data, use->iv, use);
  
  	  /* Additionally, add the pseudocandidate for the possibility to
  	     replace the final value by a direct computation.  */
--- 2292,2302 ----
  	case USE_COMPARE:
  	case USE_ADDRESS:
  	  /* Just add the ivs based on the value of the iv used here.  */
! 	  add_iv_value_candidates (data, use->iv, use, false);
  	  break;
  
  	case USE_OUTER:
! 	  add_iv_value_candidates (data, use->iv, use, false);
  
  	  /* Additionally, add the pseudocandidate for the possibility to
  	     replace the final value by a direct computation.  */
*************** alloc_use_cost_map (struct ivopts_data *
*** 2390,2402 ****
  }
  
  /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
!    on invariants DEPENDS_ON and that the value used in expressing it
!    is VALUE.*/
  
  static void
  set_use_iv_cost (struct ivopts_data *data,
  		 struct iv_use *use, struct iv_cand *cand, unsigned cost,
! 		 bitmap depends_on, tree value)
  {
    unsigned i, s;
  
--- 2401,2413 ----
  }
  
  /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
!    on invariants DEPENDS_ON, that the value used in expressing it
!    is VALUE, and that the comparison used is CMP.  */
  
  static void
  set_use_iv_cost (struct ivopts_data *data,
  		 struct iv_use *use, struct iv_cand *cand, unsigned cost,
! 		 bitmap depends_on, enum tree_code cmp, tree value)
  {
    unsigned i, s;
  
*************** set_use_iv_cost (struct ivopts_data *dat
*** 2408,2418 ****
  
    if (data->consider_all_candidates)
      {
!       use->cost_map[cand->id].cand = cand;
!       use->cost_map[cand->id].cost = cost;
!       use->cost_map[cand->id].depends_on = depends_on;
!       use->cost_map[cand->id].value = value;
!       return;
      }
  
    /* n_map_members is a power of two, so this computes modulo.  */
--- 2419,2426 ----
  
    if (data->consider_all_candidates)
      {
!       i = cand->id;
!       goto found;
      }
  
    /* n_map_members is a power of two, so this computes modulo.  */
*************** found:
*** 2431,2436 ****
--- 2439,2503 ----
    use->cost_map[i].cost = cost;
    use->cost_map[i].depends_on = depends_on;
    use->cost_map[i].value = value;
+   use->cost_map[i].cmp = cmp;
+ }
+ 
+ /* Sets cost of using candidate CAND for USE to infinity.  Empty,
+    just to make code more readable and also for the case that
+    sometimes in future we wanted to do something in this case.  */
+ 
+ static void
+ set_use_iv_cost_infinity (struct ivopts_data *data ATTRIBUTE_UNUSED,
+ 			  struct iv_use *use ATTRIBUTE_UNUSED,
+ 			  struct iv_cand *cand ATTRIBUTE_UNUSED)
+ {
+ }
+ 
+ /* Sets cost of using candidate CAND for USE to zero.  */
+ 
+ static void
+ set_use_iv_cost_zero (struct ivopts_data *data, struct iv_use *use,
+ 		      struct iv_cand *cand)
+ {
+   set_use_iv_cost (data, use, cand, 0, NULL, ERROR_MARK, NULL_TREE);
+ }
+ 
+ /* Sets cost of using candidate CAND for USE to COST and record
+    that it depends on invariants in DEPENDS_ON bitmap.  */
+ 
+ static void
+ set_use_iv_cost_generic (struct ivopts_data *data,
+ 			 struct iv_use *use, struct iv_cand *cand,
+ 			 unsigned cost, bitmap depends_on)
+ {
+   set_use_iv_cost (data, use, cand, cost, depends_on, ERROR_MARK, NULL_TREE);
+ }
+ 
+ /* Sets cost of using candidate CAND for USE (that is of type USE_OUTER) to
+    COST and record that it depends on invariants in DEPENDS_ON bitmap.  Record
+    that the final value is VALUE.  */
+ 
+ static void
+ set_use_iv_cost_outer (struct ivopts_data *data,
+ 			 struct iv_use *use, struct iv_cand *cand,
+ 			 unsigned cost, bitmap depends_on, tree value)
+ {
+   gcc_assert (use->type == USE_OUTER);
+   set_use_iv_cost (data, use, cand, cost, depends_on, ERROR_MARK, value);
+ }
+ 
+ /* Sets cost of using candidate CAND for USE (that is of type USE_COMPARE)
+    to COST and record that it depends on invariants in DEPENDS_ON bitmap.
+    Record that the replacement is to compare using CMP with BOUND.  */
+ 
+ static void
+ set_use_iv_cost_compare (struct ivopts_data *data,
+ 			 struct iv_use *use, struct iv_cand *cand,
+ 			 unsigned cost, bitmap depends_on, enum tree_code cmp,
+ 			 tree bound)
+ {
+   gcc_assert (use->type == USE_COMPARE);
+   set_use_iv_cost (data, use, cand, cost, depends_on, cmp, bound);
  }
  
  /* Gets cost of (USE, CANDIDATE) pair.  */
*************** determine_use_iv_cost_generic (struct iv
*** 3929,3940 ****
    if (cand->pos == IP_ORIGINAL
        && cand->incremented_at == use->stmt)
      {
!       set_use_iv_cost (data, use, cand, 0, NULL, NULL_TREE);
        return true;
      }
  
    cost = get_computation_cost (data, use, cand, false, &depends_on);
!   set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
  
    return cost != INFTY;
  }
--- 3996,4007 ----
    if (cand->pos == IP_ORIGINAL
        && cand->incremented_at == use->stmt)
      {
!       set_use_iv_cost_zero (data, use, cand);
        return true;
      }
  
    cost = get_computation_cost (data, use, cand, false, &depends_on);
!   set_use_iv_cost_generic (data, use, cand, cost, depends_on);
  
    return cost != INFTY;
  }
*************** determine_use_iv_cost_address (struct iv
*** 3948,3954 ****
    bitmap depends_on;
    unsigned cost = get_computation_cost (data, use, cand, true, &depends_on);
  
!   set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
  
    return cost != INFTY;
  }
--- 4015,4021 ----
    bitmap depends_on;
    unsigned cost = get_computation_cost (data, use, cand, true, &depends_on);
  
!   set_use_iv_cost_generic (data, use, cand, cost, depends_on);
  
    return cost != INFTY;
  }
*************** iv_value (struct iv *iv, tree niter)
*** 3967,4041 ****
    return fold_build2 (PLUS_EXPR, type, iv->base, val);
  }
  
- /* Computes value of candidate CAND at position AT in iteration NITER.  */
- 
- static tree
- cand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter)
- {
-   tree val = iv_value (cand->iv, niter);
-   tree type = TREE_TYPE (cand->iv->base);
- 
-   if (stmt_after_increment (loop, cand, at))
-     val = fold_build2 (PLUS_EXPR, type, val, cand->iv->step);
- 
-   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;
- }
- 
- /* Returns the comparison operator used when eliminating the iv USE.  */
- 
- static enum tree_code
- iv_elimination_compare (struct ivopts_data *data, struct iv_use *use)
- {
-   struct loop *loop = data->current_loop;
-   basic_block ex_bb;
-   edge exit;
- 
-   ex_bb = bb_for_stmt (use->stmt);
-   exit = EDGE_SUCC (ex_bb, 0);
-   if (flow_bb_inside_loop_p (loop, exit->dest))
-     exit = EDGE_SUCC (ex_bb, 1);
- 
-   return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
- }
- 
  /* Check whether it is possible to express the condition in USE by comparison
!    of candidate CAND.  If so, store the value compared with to BOUND.  */
  
  static bool
  may_eliminate_iv (struct ivopts_data *data,
! 		  struct iv_use *use, struct iv_cand *cand, 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;
    
!   if (TREE_CODE (cand->iv->step) != INTEGER_CST)
      return false;
  
    /* For now works only for exits that dominate the loop latch.  TODO -- extend
--- 4034,4055 ----
    return fold_build2 (PLUS_EXPR, type, iv->base, val);
  }
  
  /* Check whether it is possible to express the condition in USE by comparison
!    of candidate CAND.  If so, store the value compared with to BOUND and
!    the comparison operator to *CMP.  */
  
  static bool
  may_eliminate_iv (struct ivopts_data *data,
! 		  struct iv_use *use, struct iv_cand *cand,
! 		  enum tree_code *cmp, tree *bound)
  {
    basic_block ex_bb;
    edge exit;
    struct tree_niter_desc *niter;
    struct loop *loop = data->current_loop;
+   tree base = cand->iv->base, step = cand->iv->step, type = TREE_TYPE (step);
    
!   if (TREE_CODE (step) != INTEGER_CST)
      return false;
  
    /* For now works only for exits that dominate the loop latch.  TODO -- extend
*************** may_eliminate_iv (struct ivopts_data *da
*** 4058,4087 ****
        || !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;
! 
!   *bound = cand_value_at (loop, cand, use->stmt, nit);
!   return true;
  }
  
  /* Determines cost of basing replacement of USE on CAND in a condition.  */
--- 4072,4096 ----
        || !zero_p (niter->may_be_zero))
      return false;
  
!   if (stmt_after_increment (loop, cand, use->stmt))
!     base = fold_build2 (PLUS_EXPR, type, base, step);
!   return select_condition_shape (niter->niter, base, step,
! 				 (exit->flags & EDGE_TRUE_VALUE) != 0,
! 				 cmp, bound);
! }
  
! /* Estimate cost of comparing with BOUND.  */
  
! static unsigned
! compare_cost (tree bound)
! {
!   /* Prefer costants, and prefer zero even more.  */
!   if (zero_p (bound))
!     return 0;
!   else if (TREE_CODE (bound) == INTEGER_CST)
!     return 1;
    else
!     return 2;
  }
  
  /* Determines cost of basing replacement of USE on CAND in a condition.  */
*************** static bool
*** 4090,4121 ****
  determine_use_iv_cost_condition (struct ivopts_data *data,
  				 struct iv_use *use, struct iv_cand *cand)
  {
!   tree bound = NULL_TREE;
    struct iv *cmp_iv;
    bitmap depends_on_elim = NULL, depends_on_express = NULL, depends_on;
    unsigned elim_cost, express_cost, cost;
    bool ok;
  
    /* Only consider real candidates.  */
    if (!cand->iv)
      {
!       set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
        return false;
      }
  
    /* Try iv elimination.  */
!   if (may_eliminate_iv (data, use, cand, &bound))
!     elim_cost = force_var_cost (data, bound, &depends_on_elim);
    else
      elim_cost = INFTY;
  
    /* Try expressing the original giv.  If it is compared with an invariant,
       note that we cannot get rid of it.  */
!   ok = extract_cond_operands (data, use->op_p, NULL, NULL, NULL, &cmp_iv);
    gcc_assert (ok);
  
!   express_cost = get_computation_cost (data, use, cand, false,
! 				       &depends_on_express);
    fd_ivopts_data = data;
    walk_tree (&cmp_iv->base, find_depends, &depends_on_express, NULL);
  
--- 4099,4133 ----
  determine_use_iv_cost_condition (struct ivopts_data *data,
  				 struct iv_use *use, struct iv_cand *cand)
  {
!   tree bound = NULL_TREE, *cmp_inv;
    struct iv *cmp_iv;
    bitmap depends_on_elim = NULL, depends_on_express = NULL, depends_on;
    unsigned elim_cost, express_cost, cost;
+   enum tree_code cmp = ERROR_MARK;
    bool ok;
  
    /* Only consider real candidates.  */
    if (!cand->iv)
      {
!       set_use_iv_cost_infinity (data, use, cand);
        return false;
      }
  
    /* Try iv elimination.  */
!   if (may_eliminate_iv (data, use, cand, &cmp, &bound))
!     elim_cost = (force_var_cost (data, bound, &depends_on_elim)
! 		 + compare_cost (bound));
    else
      elim_cost = INFTY;
  
    /* Try expressing the original giv.  If it is compared with an invariant,
       note that we cannot get rid of it.  */
!   ok = extract_cond_operands (data, use->op_p, NULL, &cmp_inv, NULL, &cmp_iv);
    gcc_assert (ok);
  
!   express_cost = (get_computation_cost (data, use, cand, false,
! 					&depends_on_express)
! 		  + compare_cost (*cmp_inv));
    fd_ivopts_data = data;
    walk_tree (&cmp_iv->base, find_depends, &depends_on_express, NULL);
  
*************** determine_use_iv_cost_condition (struct 
*** 4134,4140 ****
        bound = NULL_TREE;
      }
  
!   set_use_iv_cost (data, use, cand, cost, depends_on, bound);
  
    if (depends_on_elim)
      BITMAP_FREE (depends_on_elim);
--- 4146,4152 ----
        bound = NULL_TREE;
      }
  
!   set_use_iv_cost_compare (data, use, cand, cost, depends_on, cmp, bound);
  
    if (depends_on_elim)
      BITMAP_FREE (depends_on_elim);
*************** determine_use_iv_cost_outer (struct ivop
*** 4191,4197 ****
    if (cand->pos == IP_ORIGINAL
        && cand->incremented_at == use->stmt)
      {
!       set_use_iv_cost (data, use, cand, 0, NULL, NULL_TREE);
        return true;
      }
  
--- 4203,4209 ----
    if (cand->pos == IP_ORIGINAL
        && cand->incremented_at == use->stmt)
      {
!       set_use_iv_cost_zero (data, use, cand);
        return true;
      }
  
*************** determine_use_iv_cost_outer (struct ivop
*** 4199,4205 ****
      {
        if (!may_replace_final_value (data, use, &value))
  	{
! 	  set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
  	  return false;
  	}
  
--- 4211,4218 ----
      {
        if (!may_replace_final_value (data, use, &value))
  	{
! 	  set_use_iv_cost (data, use, cand, INFTY, NULL,
! 			   ERROR_MARK, NULL_TREE);
  	  return false;
  	}
  
*************** determine_use_iv_cost_outer (struct ivop
*** 4207,4213 ****
        cost = force_var_cost (data, value, &depends_on);
        cost = BEFORE_LOOP_COST (loop, cost);
  
!       set_use_iv_cost (data, use, cand, cost, depends_on, value);
        return cost != INFTY;
      }
  
--- 4220,4226 ----
        cost = force_var_cost (data, value, &depends_on);
        cost = BEFORE_LOOP_COST (loop, cost);
  
!       set_use_iv_cost_outer (data, use, cand, cost, depends_on, value);
        return cost != INFTY;
      }
  
*************** determine_use_iv_cost_outer (struct ivop
*** 4227,4233 ****
        cost = get_computation_cost (data, use, cand, false, &depends_on);
      }
  				   
!   set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
  
    return cost != INFTY;
  }
--- 4240,4246 ----
        cost = get_computation_cost (data, use, cand, false, &depends_on);
      }
  				   
!   set_use_iv_cost_generic (data, use, cand, cost, depends_on);
  
    return cost != INFTY;
  }
*************** determine_use_iv_costs (struct ivopts_da
*** 4266,4271 ****
--- 4279,4285 ----
    unsigned i, j;
    struct iv_use *use;
    struct iv_cand *cand;
+   struct cost_pair *cp;
    bitmap to_clear = BITMAP_ALLOC (NULL);
  
    alloc_use_cost_map (data);
*************** determine_use_iv_costs (struct ivopts_da
*** 4314,4330 ****
  	  fprintf (dump_file, "  cand\tcost\tdepends on\n");
  	  for (j = 0; j < use->n_map_members; j++)
  	    {
! 	      if (!use->cost_map[j].cand
! 		  || use->cost_map[j].cost == INFTY)
  		continue;
  
! 	      fprintf (dump_file, "  %d\t%d\t",
! 		       use->cost_map[j].cand->id,
! 		       use->cost_map[j].cost);
! 	      if (use->cost_map[j].depends_on)
! 		bitmap_print (dump_file,
! 			      use->cost_map[j].depends_on, "","");
  	      fprintf (dump_file, "\n");
  	    }
  
  	  fprintf (dump_file, "\n");
--- 4328,4373 ----
  	  fprintf (dump_file, "  cand\tcost\tdepends on\n");
  	  for (j = 0; j < use->n_map_members; j++)
  	    {
! 	      cp = &use->cost_map[j];
! 	      if (!cp->cand || cp->cost == INFTY)
  		continue;
  
! 	      fprintf (dump_file, "  %d\t%d\t", cp->cand->id, cp->cost);
! 	      if (cp->depends_on)
! 		bitmap_print (dump_file, cp->depends_on, "","");
  	      fprintf (dump_file, "\n");
+ 
+ 	      if (cp->value)
+ 		{
+ 		  fprintf (dump_file, "\t\t");
+ 		  switch (cp->cmp)
+ 		    {
+ 		    case EQ_EXPR:
+ 		      fprintf (dump_file, "== ");
+ 		      break;
+ 		    case NE_EXPR:
+ 		      fprintf (dump_file, "!= ");
+ 		      break;
+ 		    case LT_EXPR:
+ 		      fprintf (dump_file, " < ");
+ 		      break;
+ 		    case GT_EXPR:
+ 		      fprintf (dump_file, " > ");
+ 		      break;
+ 		    case LE_EXPR:
+ 		      fprintf (dump_file, "<= ");
+ 		      break;
+ 		    case GE_EXPR:
+ 		      fprintf (dump_file, ">= ");
+ 		      break;
+ 
+ 		    default:
+ 		      gcc_assert (cp->cmp == ERROR_MARK);
+ 		      fprintf (dump_file, "   ");
+ 		    }
+ 		  print_generic_expr (dump_file, cp->value, TDF_SLIM);
+ 		  fprintf (dump_file, "\n");
+ 		}
  	    }
  
  	  fprintf (dump_file, "\n");
*************** try_improve_iv_set (struct ivopts_data *
*** 5227,5232 ****
--- 5270,5360 ----
    return true;
  }
  
+ /* Try replacing OLD candidate by NEW one in the set of IVS.  Returns
+    true if the set of ivs is improved.  */
+ 
+ static bool
+ try_replacing_cands (struct ivopts_data *data, struct iv_ca *ivs,
+ 		     struct iv_cand *old, struct iv_cand *new)
+ {
+   struct iv_ca_delta *delta_add, *delta_remove;
+   unsigned old_cost = iv_ca_cost (ivs), new_cost;
+ 
+   /* Only consider minor change, i.e., replacing with an iv with the same
+      step.  */
+   if (!old->iv || !new->iv
+       || !operand_equal_p (old->iv->step, new->iv->step, 0))
+     return false;
+ 
+   /* Try replacing the iv.  */
+   iv_ca_extend (data, ivs, new, &delta_add, NULL);
+   if (!delta_add)
+     return false;
+   iv_ca_delta_commit (data, ivs, delta_add, true);
+   new_cost = iv_ca_narrow (data, ivs, old, &delta_remove);
+ 
+   if (new_cost >= old_cost)
+     {
+       iv_ca_delta_commit (data, ivs, delta_add, false);
+       iv_ca_delta_free (&delta_add);
+       iv_ca_delta_free (&delta_remove);
+       gcc_assert (old_cost == iv_ca_cost (ivs));
+       return false;
+     }
+ 
+   iv_ca_delta_commit (data, ivs, delta_remove, true);
+   iv_ca_delta_free (&delta_add);
+   iv_ca_delta_free (&delta_remove);
+   gcc_assert (new_cost == iv_ca_cost (ivs));
+   return true;
+ }
+ 
+ /* Try improve the set of IVS by "minor adjustments" -- i.e., try replacing
+    an iv in the set by other ivs with the same step.  Occasionally, this may
+    help us get from a local minimum: if we have two similar ivs C1 and C2 such
+    that C1 is cheaper than C2 for use U1, and more expensive for use U2,
+    and C1 is already in the set, adding C2 does not have to succeed (if the
+    difference in costs is small enough, so that having both C1 and C2 in the
+    set is a loss).  If we replace C1 by C2, we may get slightly better choice
+    of ivs.  Returns true if the function improves the set of IVS.  */
+ 
+ static bool
+ minor_adjustments (struct ivopts_data *data, struct iv_ca *ivs)
+ {
+   unsigned i, j;
+   struct iv_cand *cand;
+   bitmap_iterator bi;
+   bool changed = false;
+   struct iv_ca_delta *delta;
+ 
+   /* Try extending the set of induction variables by one.  */
+   for (i = 0; i < n_iv_cands (data); i++)
+     {
+       cand = iv_cand (data, i);
+       
+       if (iv_ca_cand_used_p (ivs, cand))
+ 	continue;
+ 
+       EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, j, bi)
+ 	{
+ 	  if (try_replacing_cands (data, ivs, iv_cand (data, i), cand))
+ 	    {
+ 	      changed = true;
+ 	      break;
+ 	    }
+ 	}
+     }
+ 
+   if (changed)
+     {
+       iv_ca_prune (data, ivs, NULL, &delta);
+       iv_ca_delta_commit (data, ivs, delta, true);
+       iv_ca_delta_free (&delta);
+     }
+ 
+   return changed;
+ }
+ 
  /* Attempts to find the optimal set of induction variables.  We do simple
     greedy heuristic -- we try to replace at most one candidate in the selected
     solution and remove the unused ivs while this improves the cost.  */
*************** find_optimal_iv_set (struct ivopts_data 
*** 5262,5267 ****
--- 5390,5404 ----
  	}
      }
  
+   if (minor_adjustments (data, set))
+     {
+       if (dump_file && (dump_flags & TDF_DETAILS))
+ 	{
+ 	  fprintf (dump_file, "After minor adjustments:\n");
+ 	  iv_ca_dump (data, dump_file, set);
+ 	}
+     }
+     
    if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file, "Final cost %d\n\n", iv_ca_cost (set));
  
*************** static void
*** 5554,5562 ****
  rewrite_use_compare (struct ivopts_data *data,
  		     struct iv_use *use, struct iv_cand *cand)
  {
!   tree comp, *var_p, op, bound;
    block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
-   enum tree_code compare;
    struct cost_pair *cp = get_use_iv_cost (data, use, cand);
    bool ok;
  
--- 5691,5698 ----
  rewrite_use_compare (struct ivopts_data *data,
  		     struct iv_use *use, struct iv_cand *cand)
  {
!   tree comp, *var_p, bound;
    block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
    struct cost_pair *cp = get_use_iv_cost (data, use, cand);
    bool ok;
  
*************** rewrite_use_compare (struct ivopts_data 
*** 5564,5576 ****
    if (bound)
      {
        tree var = var_at_stmt (data->current_loop, cand, use->stmt);
!       tree var_type = TREE_TYPE (var);
  
!       compare = iv_elimination_compare (data, use);
!       bound = unshare_expr (fold_convert (var_type, bound));
!       op = force_gimple_operand_bsi (&bsi, bound, true, NULL_TREE);
  
!       *use->op_p = build2 (compare, boolean_type_node, var, op);
        return;
      }
  
--- 5700,5721 ----
    if (bound)
      {
        tree var = var_at_stmt (data->current_loop, cand, use->stmt);
!       tree bound_type = TREE_TYPE (bound), var_type = TREE_TYPE (var), type;
! 
!       /* If we compare for equality or nonequality, it is better to use type
! 	 of variable (since cast of bound can be often eliminated completely).
! 	 Otherwise, we must use type of bound.  */
!       if (cp->cmp == EQ_EXPR || cp->cmp == NE_EXPR)
! 	type = var_type;
!       else
! 	type = bound_type;
  
!       bound = fold_convert (type, unshare_expr (bound));
!       var = fold_convert (type, var);
!       bound = force_gimple_operand_bsi (&bsi, bound, true, NULL_TREE);
!       var = force_gimple_operand_bsi (&bsi, var, true, NULL_TREE);
  
!       *use->op_p = build2 (cp->cmp, boolean_type_node, var, bound);
        return;
      }
  
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.33
diff -c -3 -p -r2.33 tree-ssa-loop-niter.c
*** tree-ssa-loop-niter.c	21 Jul 2005 07:24:12 -0000	2.33
--- tree-ssa-loop-niter.c	2 Sep 2005 09:16:21 -0000
*************** Software Foundation, 51 Franklin Street,
*** 52,87 ****
  
  */
  
- /* Returns true if ARG is either NULL_TREE or constant zero.  Unlike
-    integer_zerop, it does not care about overflow flags.  */
- 
- bool
- zero_p (tree arg)
- {
-   if (!arg)
-     return true;
- 
-   if (TREE_CODE (arg) != INTEGER_CST)
-     return false;
- 
-   return (TREE_INT_CST_LOW (arg) == 0 && TREE_INT_CST_HIGH (arg) == 0);
- }
- 
- /* Returns true if ARG a nonzero constant.  Unlike integer_nonzerop, it does
-    not care about overflow flags.  */
- 
- static bool
- nonzero_p (tree arg)
- {
-   if (!arg)
-     return false;
- 
-   if (TREE_CODE (arg) != INTEGER_CST)
-     return false;
- 
-   return (TREE_INT_CST_LOW (arg) != 0 || TREE_INT_CST_HIGH (arg) != 0);
- }
- 
  /* Returns inverse of X modulo 2^s, where MASK = 2^s-1.  */
  
  static tree
--- 52,57 ----
Index: tree.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.c,v
retrieving revision 1.497
diff -c -3 -p -r1.497 tree.c
*** tree.c	20 Jul 2005 01:18:29 -0000	1.497
--- tree.c	2 Sep 2005 09:16:21 -0000
*************** integer_zerop (tree expr)
*** 1145,1150 ****
--- 1145,1180 ----
  	      && integer_zerop (TREE_IMAGPART (expr))));
  }
  
+ /* Returns true if ARG is either NULL_TREE or constant zero.  Unlike
+    integer_zerop, it does not care about overflow flags.  */
+ 
+ bool
+ zero_p (tree arg)
+ {
+   if (!arg)
+     return true;
+ 
+   if (TREE_CODE (arg) != INTEGER_CST)
+     return false;
+ 
+   return (TREE_INT_CST_LOW (arg) == 0 && TREE_INT_CST_HIGH (arg) == 0);
+ }
+ 
+ /* Returns true if ARG a nonzero constant.  Unlike integer_nonzerop, it does
+    not care about overflow flags.  */
+ 
+ bool
+ nonzero_p (tree arg)
+ {
+   if (!arg)
+     return false;
+ 
+   if (TREE_CODE (arg) != INTEGER_CST)
+     return false;
+ 
+   return (TREE_INT_CST_LOW (arg) != 0 || TREE_INT_CST_HIGH (arg) != 0);
+ }
+ 
  /* Return 1 if EXPR is the integer constant one or the corresponding
     complex constant.  */
  
*************** unsigned_type_for (tree type)
*** 6674,6679 ****
--- 6704,6712 ----
  tree
  signed_type_for (tree type)
  {
+   if (POINTER_TYPE_P (type))
+     return lang_hooks.types.type_for_size (TYPE_PRECISION (type), 0);
+ 
    return lang_hooks.types.signed_type (type);
  }
  
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.750
diff -c -3 -p -r1.750 tree.h
*** tree.h	26 Jul 2005 02:56:44 -0000	1.750
--- tree.h	2 Sep 2005 09:16:21 -0000
*************** extern int integer_pow2p (tree);
*** 3585,3590 ****
--- 3585,3591 ----
  extern int integer_nonzerop (tree);
  
  extern bool zero_p (tree);
+ extern bool nonzero_p (tree);
  extern bool cst_and_fits_in_hwi (tree);
  extern tree num_ending_zeros (tree);
  


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