[killloop] Ivopts cleanups & improvements

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

a few cleanups and improvements to ivopts:
-- makes ivopts use profile to estimate number of iterations of loop
-- splits condition operands analysis to a separate function, thus
   cleaning up 3 places where similar lookups were done
-- allows offsets in memory references larger than 20 bits
-- does iv elimination only if it is cheaper than expressing the old
   iv

Zdenek

	* tree-ssa-loop-ivopts.c (AVG_LOOP_NITER): Use
	expected_loop_iterations.
	(BEFORE_LOOP_COST): New macro.
	(extract_cond_operands): New function.
	(find_interesting_uses_cond, rewrite_use_compare): Use
	extract_cond_operands.
	(get_address_cost): Do not limit offset to at most 20 bits.
	(determine_use_iv_cost_condition): Use extract_cond_operands.
	Choose better from keeping original iv and iv elimination.
	(determine_use_iv_cost_outer, determine_iv_cost): Use BEFORE_LOOP_COST.

Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.85
diff -c -3 -p -r2.85 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c	21 Jul 2005 07:24:10 -0000	2.85
--- tree-ssa-loop-ivopts.c	30 Aug 2005 13:32:46 -0000
*************** Software Foundation, 51 Franklin Street,
*** 93,102 ****
  /* The infinite cost.  */
  #define INFTY 10000000
  
! /* The expected number of loop iterations.  TODO -- use profiling instead of
!    this.  */
! #define AVG_LOOP_NITER(LOOP) 5
  
  
  /* Representation of the induction variable.  */
  struct iv
--- 93,107 ----
  /* The infinite cost.  */
  #define INFTY 10000000
  
! /* The expected number of loop iterations.  The plus one is because
!    expected_loop_iterations returns number of executions of latch
!    edge, not of loop body.  */
! #define AVG_LOOP_NITER(LOOP) (expected_loop_iterations (LOOP) + 1)
  
+ /* Cost accounted for computations that are performed before the loop.  */
+ 
+ #define BEFORE_LOOP_COST(LOOP, COST) \
+    (((COST) + AVG_LOOP_NITER (LOOP) - 1) / AVG_LOOP_NITER (LOOP))
  
  /* Representation of the induction variable.  */
  struct iv
*************** find_interesting_uses_outer (struct ivop
*** 1279,1343 ****
    return find_interesting_uses_outer_or_nonlin (data, op, USE_OUTER);
  }
  
  /* Checks whether the condition *COND_P in STMT is interesting
     and if so, records it.  */
  
  static void
  find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
  {
!   tree *op0_p;
!   tree *op1_p;
!   struct iv *iv0 = NULL, *iv1 = NULL, *civ;
!   struct iv const_iv;
!   tree zero = integer_zero_node;
  
!   const_iv.step = NULL_TREE;
! 
!   if (TREE_CODE (*cond_p) != SSA_NAME
!       && !COMPARISON_CLASS_P (*cond_p))
!     return;
! 
!   if (TREE_CODE (*cond_p) == SSA_NAME)
!     {
!       op0_p = cond_p;
!       op1_p = &zero;
!     }
!   else
      {
!       op0_p = &TREE_OPERAND (*cond_p, 0);
!       op1_p = &TREE_OPERAND (*cond_p, 1);
!     }
! 
!   if (TREE_CODE (*op0_p) == SSA_NAME)
!     iv0 = get_iv (data, *op0_p);
!   else
!     iv0 = &const_iv;
! 
!   if (TREE_CODE (*op1_p) == SSA_NAME)
!     iv1 = get_iv (data, *op1_p);
!   else
!     iv1 = &const_iv;
! 
!   if (/* When comparing with non-invariant value, we may not do any senseful
! 	 induction variable elimination.  */
!       (!iv0 || !iv1)
!       /* Eliminating condition based on two ivs would be nontrivial.
! 	 ??? TODO -- it is not really important to handle this case.  */
!       || (!zero_p (iv0->step) && !zero_p (iv1->step)))
!     {
!       find_interesting_uses_op (data, *op0_p);
!       find_interesting_uses_op (data, *op1_p);
!       return;
!     }
! 
!   if (zero_p (iv0->step) && zero_p (iv1->step))
!     {
!       /* If both are invariants, this is a work for unswitching.  */
        return;
      }
  
    civ = xmalloc (sizeof (struct iv));
!   *civ = zero_p (iv0->step) ? *iv1: *iv0;
    record_use (data, cond_p, civ, stmt, USE_COMPARE);
  }
  
--- 1284,1377 ----
    return find_interesting_uses_outer_or_nonlin (data, op, USE_OUTER);
  }
  
+ /* Given a condition *COND_P, checks whether it is a compare of an induction
+    variable and an invariant.  If this is the case, CONTROL_VAR is set
+    to location of the iv, BOUND to the location of the invariant,
+    IV_VAR and IV_BOUND are set to the corresponding induction variable
+    descriptions, and true is returned.  If this is not the case,
+    CONTROL_VAR and BOUND are set to the arguments of the condition and
+    false is returned.  */
+ 
+ static bool
+ extract_cond_operands (struct ivopts_data *data, tree *cond_p,
+ 		       tree **control_var, tree **bound,
+ 		       struct iv **iv_var, struct iv **iv_bound)
+ {
+   /* The nodes returned when COND has just one operand.  Note that you should
+      not modify anything in BOUND or IV_BOUND because of this.  */
+   static struct iv const_iv;
+   static tree zero;
+   tree cond = *cond_p;
+   tree *op0 = &zero, *op1 = &zero, *tmp_op;
+   struct iv *iv0 = &const_iv, *iv1 = &const_iv, *tmp_iv;
+   bool ret = false;
+ 
+   zero = integer_zero_node;
+   if (TREE_CODE (cond) == SSA_NAME)
+     {
+       op0 = cond_p;
+       iv0 = get_iv (data, cond);
+       ret = (iv0 && !zero_p (iv0->step));
+       goto end;
+     }
+ 
+   if (!COMPARISON_CLASS_P (cond))
+     {
+       op0 = cond_p;
+       goto end;
+     }
+ 
+   op0 = &TREE_OPERAND (cond, 0);
+   op1 = &TREE_OPERAND (cond, 1);
+   if (TREE_CODE (*op0) == SSA_NAME)
+     iv0 = get_iv (data, *op0);
+   if (TREE_CODE (*op1) == SSA_NAME)
+     iv1 = get_iv (data, *op1);
+ 
+   /* Exactly one of the compared values must be an iv, and the other one must
+      be an invariant.  */
+   if (!iv0 || !iv1)
+     goto end;
+ 
+   if (zero_p (iv0->step))
+     {
+       /* Control variable may be on the other side.  */
+       tmp_op = op0; op0 = op1; op1 = tmp_op;
+       tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
+     }
+   ret = !zero_p (iv0->step) && zero_p (iv1->step);
+ 
+ end:
+   if (control_var)
+     *control_var = op0;;
+   if (iv_var)
+     *iv_var = iv0;;
+   if (bound)
+     *bound = op1;
+   if (iv_bound)
+     *iv_bound = iv1;
+ 
+   return ret;
+ }
+ 
  /* Checks whether the condition *COND_P in STMT is interesting
     and if so, records it.  */
  
  static void
  find_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p)
  {
!   tree *var_p, *bound_p;
!   struct iv *var_iv, *civ;
  
!   if (!extract_cond_operands (data, cond_p, &var_p, &bound_p, &var_iv, NULL))
      {
!       find_interesting_uses_op (data, *var_p);
!       find_interesting_uses_op (data, *bound_p);
        return;
      }
  
    civ = xmalloc (sizeof (struct iv));
!   *civ = *var_iv;
    record_use (data, cond_p, civ, stmt, USE_COMPARE);
  }
  
*************** get_address_cost (bool symbol_present, b
*** 3309,3336 ****
  
    if (!initialized)
      {
!       HOST_WIDE_INT i;
        initialized = true;
- 
        reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
- 
        addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
!       for (i = 1; i <= 1 << 20; i <<= 1)
  	{
  	  XEXP (addr, 1) = gen_int_mode (i, Pmode);
  	  if (!memory_address_p (Pmode, addr))
  	    break;
  	}
-       max_offset = i >> 1;
        off = max_offset;
  
!       for (i = 1; i <= 1 << 20; i <<= 1)
  	{
! 	  XEXP (addr, 1) = gen_int_mode (-i, Pmode);
  	  if (!memory_address_p (Pmode, addr))
  	    break;
  	}
-       min_offset = -(i >> 1);
  
        if (dump_file && (dump_flags & TDF_DETAILS))
  	{
--- 3343,3378 ----
  
    if (!initialized)
      {
!       HOST_WIDE_INT i, j;
!       HOST_WIDE_INT bits = HOST_BITS_PER_WIDE_INT;
!       if (GET_MODE_BITSIZE (Pmode) < bits)
! 	bits = GET_MODE_BITSIZE (Pmode);
        initialized = true;
        reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
        addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
! 
!       max_offset = 0;
!       i = 0;
!       for (j = 0; j < bits - 1; j++)
  	{
+ 	  i = (i << 1) + 1;
  	  XEXP (addr, 1) = gen_int_mode (i, Pmode);
  	  if (!memory_address_p (Pmode, addr))
  	    break;
+ 	  max_offset = i;
  	}
        off = max_offset;
  
!       min_offset = 0;
!       i = -1;
!       for (j = 0; j < bits; j++)
  	{
! 	  XEXP (addr, 1) = gen_int_mode (i, Pmode);
  	  if (!memory_address_p (Pmode, addr))
  	    break;
+ 	  min_offset = i;
+ 	  i <<= 1;
  	}
  
        if (dump_file && (dump_flags & TDF_DETAILS))
  	{
*************** static bool
*** 4048,4056 ****
  determine_use_iv_cost_condition (struct ivopts_data *data,
  				 struct iv_use *use, struct iv_cand *cand)
  {
!   tree bound = NULL_TREE, op, cond;
!   bitmap depends_on = NULL;
!   unsigned cost;
  
    /* Only consider real candidates.  */
    if (!cand->iv)
--- 4090,4100 ----
  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)
*************** determine_use_iv_cost_condition (struct 
*** 4059,4092 ****
        return false;
      }
  
    if (may_eliminate_iv (data, use, cand, &bound))
!     {
!       cost = force_var_cost (data, bound, &depends_on);
  
!       set_use_iv_cost (data, use, cand, cost, depends_on, bound);
!       return cost != INFTY;
      }
! 
!   /* The induction variable elimination failed; just express the original
!      giv.  If it is compared with an invariant, note that we cannot get
!      rid of it.  */
!   cost = get_computation_cost (data, use, cand, false, &depends_on);
! 
!   cond = *use->op_p;
!   if (TREE_CODE (cond) != SSA_NAME)
      {
!       op = TREE_OPERAND (cond, 0);
!       if (TREE_CODE (op) == SSA_NAME && !zero_p (get_iv (data, op)->step))
! 	op = TREE_OPERAND (cond, 1);
!       if (TREE_CODE (op) == SSA_NAME)
! 	{
! 	  op = get_iv (data, op)->base;
! 	  fd_ivopts_data = data;
! 	  walk_tree (&op, find_depends, &depends_on, NULL);
! 	}
      }
  
!   set_use_iv_cost (data, use, cand, cost, depends_on, NULL);
    return cost != INFTY;
  }
  
--- 4103,4146 ----
        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);
! 
!   /* Choose the better approach.  */
!   if (elim_cost < express_cost)
!     {
!       cost = elim_cost;
!       depends_on = depends_on_elim;
!       depends_on_elim = NULL;
      }
!   else
      {
!       cost = express_cost;
!       depends_on = depends_on_express;
!       depends_on_express = NULL;
!       bound = NULL_TREE;
      }
  
!   set_use_iv_cost (data, use, cand, cost, depends_on, bound);
! 
!   if (depends_on_elim)
!     BITMAP_FREE (depends_on_elim);
!   if (depends_on_express)
!     BITMAP_FREE (depends_on_express);
! 
    return cost != INFTY;
  }
  
*************** determine_use_iv_cost_outer (struct ivop
*** 4151,4158 ****
  
        depends_on = NULL;
        cost = force_var_cost (data, value, &depends_on);
! 
!       cost /= AVG_LOOP_NITER (loop);
  
        set_use_iv_cost (data, use, cand, cost, depends_on, value);
        return cost != INFTY;
--- 4205,4211 ----
  
        depends_on = NULL;
        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;
*************** determine_use_iv_cost_outer (struct ivop
*** 4166,4172 ****
        cost = get_computation_cost_at (data, use, cand, false, &depends_on,
  				      last_stmt (exit->src));
        if (cost != INFTY)
! 	cost /= AVG_LOOP_NITER (loop);
      }
    else
      {
--- 4219,4225 ----
        cost = get_computation_cost_at (data, use, cand, false, &depends_on,
  				      last_stmt (exit->src));
        if (cost != INFTY)
! 	cost = BEFORE_LOOP_COST (loop, cost);
      }
    else
      {
*************** determine_iv_cost (struct ivopts_data *d
*** 4302,4308 ****
    cost_base = force_var_cost (data, base, NULL);
    cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
  
!   cand->cost = cost_step + cost_base / AVG_LOOP_NITER (current_loop);
  
    /* Prefer the original iv unless we may gain something by replacing it;
       this is not really relevant for artificial ivs created by other
--- 4355,4361 ----
    cost_base = force_var_cost (data, base, NULL);
    cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
  
!   cand->cost = cost_step + BEFORE_LOOP_COST (data->current_loop, cost_base);
  
    /* Prefer the original iv unless we may gain something by replacing it;
       this is not really relevant for artificial ivs created by other
*************** static void
*** 5501,5512 ****
  rewrite_use_compare (struct ivopts_data *data,
  		     struct iv_use *use, struct iv_cand *cand)
  {
!   tree comp;
!   tree *op_p, cond, op, stmts, 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);
!   
    bound = cp->value;
    if (bound)
      {
--- 5554,5565 ----
  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;
! 
    bound = cp->value;
    if (bound)
      {
*************** rewrite_use_compare (struct ivopts_data 
*** 5514,5528 ****
        tree var_type = TREE_TYPE (var);
  
        compare = iv_elimination_compare (data, use);
!       bound = fold_convert (var_type, bound);
!       op = force_gimple_operand (unshare_expr (bound), &stmts,
! 				 true, NULL_TREE);
! 
!       if (stmts)
! 	bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
  
        *use->op_p = build2 (compare, boolean_type_node, var, op);
-       update_stmt (use->stmt);
        return;
      }
  
--- 5567,5576 ----
        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;
      }
  
*************** rewrite_use_compare (struct ivopts_data 
*** 5530,5546 ****
       giv.  */
    comp = get_computation (data->current_loop, use, cand);
  
!   cond = *use->op_p;
!   op_p = &TREE_OPERAND (cond, 0);
!   if (TREE_CODE (*op_p) != SSA_NAME
!       || zero_p (get_iv (data, *op_p)->step))
!     op_p = &TREE_OPERAND (cond, 1);
! 
!   op = force_gimple_operand (comp, &stmts, true, SSA_NAME_VAR (*op_p));
!   if (stmts)
!     bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
  
!   *op_p = op;
  }
  
  /* Ensure that operand *OP_P may be used at the end of EXIT without
--- 5578,5587 ----
       giv.  */
    comp = get_computation (data->current_loop, use, cand);
  
!   ok = extract_cond_operands (data, use->op_p, &var_p, NULL, NULL, NULL);
!   gcc_assert (ok);
  
!   *var_p = force_gimple_operand_bsi (&bsi, comp, true, SSA_NAME_VAR (*var_p));
  }
  
  /* Ensure that operand *OP_P may be used at the end of EXIT without