* fold-const.c (fold): Fold difference of addresses.

	(ptr_difference_const): Moved from tree-ssa-loop-ivopts, based on
	get_inner_reference.
	* tree-ssa-loop-ivopts.c (peel_address): Removed.
	(ptr_difference_const): Moved to fold-const.c.
	(split_address_cost): Use get_inner_reference instead of peel_address.
	(ptr_difference_cost): Change type of diff to HOST_WIDE_INT.
	* tree.h (ptr_difference_const): Export.

	* tree-ssa-loop-ivopts.c (dump_iv, dump_use, dump_cand): Add induction
	variable type to the dump.  Fix indentation.
	(idx_find_step): Handle nonconstant array_ref_element_size and
	array_ref_low_bound.
	(idx_record_use): Handle array_ref_element_size and
	array_ref_low_bound.
	(find_interesting_uses_stmt): Handle memory = nontrivial_expression
	statements correctly.
	(get_computation_at, iv_value): Do not unshare expressions here.
	(rewrite_use_outer): Unshare the expression before it is emitted
	to code.
	* tree-ssa-loop-niter.c (unsigned_type_for, signed_type_for):
	Moved to tree.c.
	* tree.c (unsigned_type_for, signed_type_for): Moved from
	tree-ssa-loop-niter.c.  Use langhooks.
	* tree.h (signed_type_for): Export.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@87601 138bc75d-0d04-0410-961f-82ee72b054a4

6 files changed, 229 insertions, 170 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 859f6673f08..617b26a4434 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,31 @@
+2004-09-16  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>
+
+	* fold-const.c (fold): Fold difference of addresses.
+	(ptr_difference_const): Moved from tree-ssa-loop-ivopts, based on
+	get_inner_reference.
+	* tree-ssa-loop-ivopts.c (peel_address): Removed.
+	(ptr_difference_const): Moved to fold-const.c.
+	(split_address_cost): Use get_inner_reference instead of peel_address.
+	(ptr_difference_cost): Change type of diff to HOST_WIDE_INT.
+	* tree.h (ptr_difference_const): Export.
+
+	* tree-ssa-loop-ivopts.c (dump_iv, dump_use, dump_cand): Add induction
+	variable type to the dump.  Fix indentation.
+	(idx_find_step): Handle nonconstant array_ref_element_size and
+	array_ref_low_bound.
+	(idx_record_use): Handle array_ref_element_size and
+	array_ref_low_bound.
+	(find_interesting_uses_stmt): Handle memory = nontrivial_expression
+	statements correctly.
+	(get_computation_at, iv_value): Do not unshare expressions here.
+	(rewrite_use_outer): Unshare the expression before it is emitted
+	to code.
+	* tree-ssa-loop-niter.c (unsigned_type_for, signed_type_for):
+	Moved to tree.c.
+	* tree.c (unsigned_type_for, signed_type_for): Moved from
+	tree-ssa-loop-niter.c.  Use langhooks.
+	* tree.h (signed_type_for): Export.
+
 2004-09-16  David Edelsohn  <edelsohn@gnu.org>
 
 	* config/rs6000/rs6000.c (rs6000_xcoff_asm_named_section): Update
diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index 378578d000f..7d8fff9d9ee 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -6966,6 +6966,18 @@ fold (tree expr)
 	      || (INTEGRAL_TYPE_P (type) && flag_wrapv && !flag_trapv)))
 	return fold (build2 (PLUS_EXPR, type, arg0, negate_expr (arg1)));
 
+      /* Try folding difference of addresses.  */
+      {
+	HOST_WIDE_INT diff;
+
+	if (TREE_CODE (arg0) == ADDR_EXPR
+	    && TREE_CODE (arg1) == ADDR_EXPR
+	    && ptr_difference_const (TREE_OPERAND (arg0, 0),
+				     TREE_OPERAND (arg1, 0),
+				     &diff))
+	  return build_int_cst_type (type, diff);
+      }
+
       if (TREE_CODE (arg0) == MULT_EXPR
 	  && TREE_CODE (arg1) == MULT_EXPR
 	  && (INTEGRAL_TYPE_P (type) || flag_unsafe_math_optimizations))
@@ -10668,3 +10680,51 @@ round_down (tree value, int divisor)
 
   return value;
 }
+
+/* Returns true if addresses of E1 and E2 differ by a constant, false
+   otherwise.  If they do, &E1 - &E2 is stored in *DIFF.  */
+
+bool
+ptr_difference_const (tree e1, tree e2, HOST_WIDE_INT *diff)
+{
+  tree core1, core2;
+  HOST_WIDE_INT bitsize1, bitsize2;
+  HOST_WIDE_INT bitpos1, bitpos2;
+  tree toffset1, toffset2, tdiff, type;
+  enum machine_mode mode1, mode2;
+  int unsignedp1, unsignedp2, volatilep1, volatilep2;
+  
+  core1 = get_inner_reference (e1, &bitsize1, &bitpos1, &toffset1, &mode1,
+			       &unsignedp1, &volatilep1);
+  core2 = get_inner_reference (e2, &bitsize2, &bitpos2, &toffset2, &mode2,
+			       &unsignedp2, &volatilep2);
+
+  if (bitpos1 % BITS_PER_UNIT != 0
+      || bitpos2 % BITS_PER_UNIT != 0
+      || !operand_equal_p (core1, core2, 0))
+    return false;
+
+  if (toffset1 && toffset2)
+    {
+      type = TREE_TYPE (toffset1);
+      if (type != TREE_TYPE (toffset2))
+	toffset2 = fold_convert (type, toffset2);
+
+      tdiff = fold (build2 (MINUS_EXPR, type, toffset1, toffset2));
+      if (!host_integerp (tdiff, 0))
+	return false;
+
+      *diff = tree_low_cst (tdiff, 0);
+    }
+  else if (toffset1 || toffset2)
+    {
+      /* If only one of the offsets is non-constant, the difference cannot
+	 be a constant.  */
+      return false;
+    }
+  else
+    *diff = 0;
+
+  *diff += (bitpos1 - bitpos2) / BITS_PER_UNIT;
+  return true;
+}
diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index c8e3762a5e9..e831b511088 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -305,6 +305,10 @@ dump_iv (FILE *file, struct iv *iv)
   print_generic_expr (file, iv->ssa_name, TDF_SLIM);
   fprintf (file, "\n");
 
+  fprintf (file, "  type ");
+  print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
+  fprintf (file, "\n");
+
   if (iv->step)
     {
       fprintf (file, "  base ");
@@ -358,34 +362,38 @@ dump_use (FILE *file, struct iv_use *use)
       gcc_unreachable ();
     }
 
-   fprintf (file, "  in statement ");
-   print_generic_expr (file, use->stmt, TDF_SLIM);
-   fprintf (file, "\n");
-
-   fprintf (file, "  at position ");
-   if (use->op_p)
-     print_generic_expr (file, *use->op_p, TDF_SLIM);
-   fprintf (file, "\n");
-
-   if (iv->step)
-     {
-       fprintf (file, "  base ");
-       print_generic_expr (file, iv->base, TDF_SLIM);
-       fprintf (file, "\n");
-
-       fprintf (file, "  step ");
-       print_generic_expr (file, iv->step, TDF_SLIM);
-       fprintf (file, "\n");
-     }
-   else
-     {
-       fprintf (file, "  invariant ");
-       print_generic_expr (file, iv->base, TDF_SLIM);
-       fprintf (file, "\n");
-     }
-
-   fprintf (file, "  related candidates ");
-   dump_bitmap (file, use->related_cands);
+  fprintf (file, "  in statement ");
+  print_generic_expr (file, use->stmt, TDF_SLIM);
+  fprintf (file, "\n");
+
+  fprintf (file, "  at position ");
+  if (use->op_p)
+    print_generic_expr (file, *use->op_p, TDF_SLIM);
+  fprintf (file, "\n");
+
+  fprintf (file, "  type ");
+  print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
+  fprintf (file, "\n");
+
+  if (iv->step)
+    {
+      fprintf (file, "  base ");
+      print_generic_expr (file, iv->base, TDF_SLIM);
+      fprintf (file, "\n");
+
+      fprintf (file, "  step ");
+      print_generic_expr (file, iv->step, TDF_SLIM);
+      fprintf (file, "\n");
+    }
+  else
+    {
+      fprintf (file, "  invariant ");
+      print_generic_expr (file, iv->base, TDF_SLIM);
+      fprintf (file, "\n");
+    }
+
+  fprintf (file, "  related candidates ");
+  dump_bitmap (file, use->related_cands);
 }
 
 /* Dumps information about the uses to FILE.  */
@@ -438,22 +446,26 @@ dump_cand (FILE *file, struct iv_cand *cand)
       break;
     }
 
-   if (iv->step)
-     {
-       fprintf (file, "  base ");
-       print_generic_expr (file, iv->base, TDF_SLIM);
-       fprintf (file, "\n");
-
-       fprintf (file, "  step ");
-       print_generic_expr (file, iv->step, TDF_SLIM);
-       fprintf (file, "\n");
-     }
-   else
-     {
-       fprintf (file, "  invariant ");
-       print_generic_expr (file, iv->base, TDF_SLIM);
-       fprintf (file, "\n");
-     }
+  fprintf (file, "  type ");
+  print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
+  fprintf (file, "\n");
+
+  if (iv->step)
+    {
+      fprintf (file, "  base ");
+      print_generic_expr (file, iv->base, TDF_SLIM);
+      fprintf (file, "\n");
+
+      fprintf (file, "  step ");
+      print_generic_expr (file, iv->step, TDF_SLIM);
+      fprintf (file, "\n");
+    }
+  else
+    {
+      fprintf (file, "  invariant ");
+      print_generic_expr (file, iv->base, TDF_SLIM);
+      fprintf (file, "\n");
+    }
 }
 
 /* Returns the info for ssa version VER.  */
@@ -1150,7 +1162,9 @@ idx_find_step (tree base, tree *idx, void *data)
 {
   struct ifs_ivopts_data *dta = data;
   struct iv *iv;
-  tree step, type, iv_type, iv_step;
+  tree step, type, iv_type, iv_step, lbound;
+  basic_block def_bb;
+  struct loop *loop = dta->ivopts_data->current_loop;
   
   if (TREE_CODE (*idx) != SSA_NAME)
     return true;
@@ -1167,7 +1181,30 @@ idx_find_step (tree base, tree *idx, void *data)
   iv_type = TREE_TYPE (iv->base);
   type = build_pointer_type (TREE_TYPE (base));
   if (TREE_CODE (base) == ARRAY_REF)
-    step = array_ref_element_size (base);
+    {
+      step = array_ref_element_size (base);
+      lbound = array_ref_low_bound (base);
+
+      /* We only handle addresses whose step is an integer constant.  */
+      if (TREE_CODE (step) != INTEGER_CST)
+	return false;
+
+      /* We need the lower bound to be invariant in loop, since otherwise
+	 we are unable to initialize a new induction variable created
+	 in strength reduction -- we need to take the address of the
+	 reference in front of the loop.  */
+      if (is_gimple_min_invariant (lbound))
+	; /* Nothing to do.  */
+      else if (TREE_CODE (lbound) != SSA_NAME)
+	return false;
+      else
+	{
+	  def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (lbound));
+	  if (def_bb
+	      && flow_bb_inside_loop_p (loop, def_bb))
+	    return false;
+	}
+    }
   else
     /* The step for pointer arithmetics already is 1 byte.  */
     step = build_int_cst (type, 1);
@@ -1198,10 +1235,15 @@ idx_find_step (tree base, tree *idx, void *data)
    object is passed to it in DATA.  */
 
 static bool
-idx_record_use (tree base ATTRIBUTE_UNUSED, tree *idx,
+idx_record_use (tree base, tree *idx,
 		void *data)
 {
   find_interesting_uses_op (data, *idx);
+  if (TREE_CODE (base) == ARRAY_REF)
+    {
+      find_interesting_uses_op (data, array_ref_element_size (base));
+      find_interesting_uses_op (data, array_ref_low_bound (base));
+    }
   return true;
 }
 
@@ -1318,12 +1360,22 @@ find_interesting_uses_stmt (struct ivopts_data *data, tree stmt)
 	default: ;
 	}
 
-      if (TREE_CODE_CLASS (TREE_CODE (lhs)) == 'r')
+      /* Handle memory = gimple_val.  */
+      if (TREE_CODE_CLASS (TREE_CODE (lhs)) == 'r'
+	  && is_gimple_val (rhs))
 	{
 	  find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0));
 	  find_interesting_uses_op (data, rhs);
 	  return;
 	}
+
+      /* TODO -- we should also handle address uses of type
+
+	 memory = call (whatever);
+
+	 and
+
+	 call (memory).  */
     }
 
   if (TREE_CODE (stmt) == PHI_NODE
@@ -1995,10 +2047,10 @@ static tree
 get_computation_at (struct loop *loop,
 		    struct iv_use *use, struct iv_cand *cand, tree at)
 {
-  tree ubase = unsave_expr_now (use->iv->base);
-  tree ustep = unsave_expr_now (use->iv->step);
-  tree cbase = unsave_expr_now (cand->iv->base);
-  tree cstep = unsave_expr_now (cand->iv->step);
+  tree ubase = use->iv->base;
+  tree ustep = use->iv->step;
+  tree cbase = cand->iv->base;
+  tree cstep = cand->iv->step;
   tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase);
   tree uutype;
   tree expr, delta;
@@ -2500,98 +2552,6 @@ force_var_cost (struct ivopts_data *data,
   return target_spill_cost;
 }
 
-/* Peels a single layer of ADDR.  If DIFF is not NULL, do it only if the
-   offset is constant and add the offset to DIFF.  */
-
-static tree
-peel_address (tree addr, unsigned HOST_WIDE_INT *diff)
-{
-  tree off, size;
-  HOST_WIDE_INT bit_offset;
-
-  switch (TREE_CODE (addr))
-    {
-    case SSA_NAME:
-    case INDIRECT_REF:
-    case BIT_FIELD_REF:
-    case VAR_DECL:
-    case PARM_DECL:
-    case RESULT_DECL:
-    case STRING_CST:
-    case REALPART_EXPR:
-    case IMAGPART_EXPR:
-      return NULL_TREE;
-
-    case COMPONENT_REF:
-      off = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (addr, 1));
-      bit_offset = TREE_INT_CST_LOW (off);
-
-      gcc_assert ((bit_offset % BITS_PER_UNIT) == 0);
-      
-      if (diff)
-	*diff += bit_offset / BITS_PER_UNIT;
-
-      return TREE_OPERAND (addr, 0);
-
-    case VIEW_CONVERT_EXPR:
-      return TREE_OPERAND (addr, 0);
-
-    case ARRAY_REF:
-      off = TREE_OPERAND (addr, 1);
-
-      if (diff)
-	{
-	  if (!cst_and_fits_in_hwi (off))
-	    return NULL_TREE;
-
-	  size = TYPE_SIZE_UNIT (TREE_TYPE (addr));
-	  if (!cst_and_fits_in_hwi (size))
-	    return NULL_TREE;
-
-	  *diff += TREE_INT_CST_LOW (off) * TREE_INT_CST_LOW (size);
-	}
-
-      return TREE_OPERAND (addr, 0);
-
-    default:
-      gcc_unreachable ();
-    }
-}
-
-/* Checks whether E1 and E2 have constant difference, and if they do,
-   store it in *DIFF.  */
-
-static bool
-ptr_difference_const (tree e1, tree e2, unsigned HOST_WIDE_INT *diff)
-{
-  int d1 = 0, d2 = 0;
-  tree x;
-  unsigned HOST_WIDE_INT delta1 = 0, delta2 = 0;
-
-  /* Find depths of E1 and E2.  */
-  for (x = e1; x; x = peel_address (x, NULL))
-    d1++;
-  for (x = e2; x; x = peel_address (x, NULL))
-    d2++;
-
-  for (; e1 && d1 > d2; e1 = peel_address (e1, &delta1))
-    d1--;
-  for (; e2 && d2 > d1; e2 = peel_address (e2, &delta2))
-    d2--;
-
-  while (e1 && e2 && !operand_equal_p (e1, e2, 0))
-    {
-      e1 = peel_address (e1, &delta1);
-      e2 = peel_address (e2, &delta1);
-    }
-
-  if (!e1 || !e2)
-    return false;
-
-  *diff = delta1 - delta2;
-  return true;
-}
-
 /* Estimates cost of expressing address ADDR  as var + symbol + offset.  The
    value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
    to false if the corresponding part is missing.  DEPENDS_ON is a set of the
@@ -2602,21 +2562,28 @@ split_address_cost (struct ivopts_data *data,
 		    tree addr, bool *symbol_present, bool *var_present,
 		    unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
 {
-  tree core = addr;
-
-  while (core
-	 && TREE_CODE (core) != VAR_DECL)
-    core = peel_address (core, offset);
+  tree core;
+  HOST_WIDE_INT bitsize;
+  HOST_WIDE_INT bitpos;
+  tree toffset;
+  enum machine_mode mode;
+  int unsignedp, volatilep;
+  
+  core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
+			      &unsignedp, &volatilep);
 
-  if (!core)
+  if (toffset != 0
+      || bitpos % BITS_PER_UNIT != 0
+      || TREE_CODE (core) != VAR_DECL)
     {
       *symbol_present = false;
       *var_present = true;
       fd_ivopts_data = data;
       walk_tree (&addr, find_depends, depends_on, NULL);
       return target_spill_cost;
-    }  
-	  
+    }
+
+  *offset += bitpos / BITS_PER_UNIT;
   if (TREE_STATIC (core)
       || DECL_EXTERNAL (core))
     {
@@ -2641,7 +2608,7 @@ ptr_difference_cost (struct ivopts_data *data,
 		     tree e1, tree e2, bool *symbol_present, bool *var_present,
 		     unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
 {
-  unsigned HOST_WIDE_INT diff = 0;
+  HOST_WIDE_INT diff = 0;
   unsigned cost;
 
   gcc_assert (TREE_CODE (e1) == ADDR_EXPR);
@@ -2905,7 +2872,7 @@ iv_value (struct iv *iv, tree niter)
   tree type = TREE_TYPE (iv->base);
 
   niter = fold_convert (type, niter);
-  val = fold (build2 (MULT_EXPR, type, iv->step, unsave_expr_now (niter)));
+  val = fold (build2 (MULT_EXPR, type, iv->step, niter));
 
   return fold (build2 (PLUS_EXPR, type, iv->base, val));
 }
@@ -4125,6 +4092,7 @@ rewrite_use_outer (struct ivopts_data *data,
 	value = get_computation_at (data->current_loop,
 				    use, cand, last_stmt (exit->src));
 
+      value = unshare_expr (value);
       op = force_gimple_operand (value, &stmts, true, SSA_NAME_VAR (tgt));
 	  
       /* If we will preserve the iv anyway and we would need to perform
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index dd5fad9adb5..686545bf26f 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -84,22 +84,6 @@ inverse (tree x, tree mask)
   return rslt;
 }
 
-/* Returns unsigned variant of TYPE.  */
-
-tree
-unsigned_type_for (tree type)
-{
-  return make_unsigned_type (TYPE_PRECISION (type));
-}
-
-/* Returns signed variant of TYPE.  */
-
-static tree
-signed_type_for (tree type)
-{
-  return make_signed_type (TYPE_PRECISION (type));
-}
-
 /* Determine the number of iterations according to condition (for staying
    inside loop) which compares two induction variables using comparison
    operator CODE.  The induction variable on left side of the comparison
diff --git a/gcc/tree.c b/gcc/tree.c
index 392d997535c..05bbc1eaa92 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -5866,4 +5866,20 @@ tree_fold_gcd (tree a, tree b)
     }
 }
 
+/* Returns unsigned variant of TYPE.  */
+
+tree
+unsigned_type_for (tree type)
+{
+  return lang_hooks.types.unsigned_type (type);
+}
+
+/* Returns signed variant of TYPE.  */
+
+tree
+signed_type_for (tree type)
+{
+  return lang_hooks.types.signed_type (type);
+}
+
 #include "gt-tree.h"
diff --git a/gcc/tree.h b/gcc/tree.h
index 015f8d3fabc..19ba2201b84 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -2792,6 +2792,7 @@ extern tree build_empty_stmt (void);
 
 extern tree make_signed_type (int);
 extern tree make_unsigned_type (int);
+extern tree signed_type_for (tree);
 extern tree unsigned_type_for (tree);
 extern void initialize_sizetypes (bool);
 extern void set_sizetype (tree);
@@ -3464,6 +3465,8 @@ extern tree constant_boolean_node (int, tree);
 extern bool tree_swap_operands_p (tree, tree, bool);
 extern enum tree_code swap_tree_comparison (enum tree_code);
 
+extern bool ptr_difference_const (tree, tree, HOST_WIDE_INT *);
+
 /* In builtins.c */
 extern tree fold_builtin (tree, bool);
 extern tree fold_builtin_fputs (tree, bool, bool, tree);