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] Preserve user ivs if possible


Hello,

this patch makes the induction variable optimization to use the original
ivs unless it can gain something by replacing them.

Zdenek

Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.68
diff -c -3 -p -r1.1.2.68 ChangeLog.lno
*** ChangeLog.lno	2 Mar 2004 11:46:06 -0000	1.1.2.68
--- ChangeLog.lno	3 Mar 2004 07:27:59 -0000
***************
*** 1,3 ****
--- 1,15 ----
+ 2004-03-03  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>
+ 
+ 	* tree-ssa-loop-ivopts.c (enum iv_position): Add IP_ORIGINAL.
+ 	(struct iv_cand): Add incremented_at.
+ 	(dump_cand, add_candidate_1, add_candidate, add_old_iv_candidates,
+ 	var_at_use, get_computation, get_computation_cost,
+ 	cand_value_at, determine_iv_cost, find_best_candidate,
+ 	create_new_iv): Handle IP_ORIGINAL.
+ 	(stmt_after_ip_original_pos, stmt_after_increment): New functions.
+ 	(find_givs_in_stmt): Cast the values to the result type.
+ 	(record_invariant): Do not record virtual operands.
+ 
  2004-03-02  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>
  
  	* tree-ssa-loop-ivopts.c (number_of_iterations_cond, cand_value_at):
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-ivopts.c,v
retrieving revision 1.1.2.13
diff -c -3 -p -r1.1.2.13 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c	2 Mar 2004 11:46:05 -0000	1.1.2.13
--- tree-ssa-loop-ivopts.c	3 Mar 2004 07:27:59 -0000
*************** enum iv_position
*** 203,209 ****
    IP_START,		/* At the very beginning of the loop body.  */
  #endif
    IP_NORMAL,		/* At the end, just before the exit condition.  */
!   IP_END		/* At the end of the latch block.  */
  };
  
  /* The induction variable candidate.  */
--- 203,210 ----
    IP_START,		/* At the very beginning of the loop body.  */
  #endif
    IP_NORMAL,		/* At the end, just before the exit condition.  */
!   IP_END,		/* At the end of the latch block.  */
!   IP_ORIGINAL		/* The original biv.  */
  };
  
  /* The induction variable candidate.  */
*************** struct iv_cand
*** 213,218 ****
--- 214,221 ----
    bool important;	/* Whether this is an "important" candidate, i.e. such
  			   that it should be considered by all uses.  */
    enum iv_position pos;	/* Where it is computed.  */
+   tree incremented_at;	/* For original biv, the statement where it is
+ 			   incremented.  */
    tree var_before;	/* The variable used for it before incrementation.  */
    tree var_after;	/* The variable used for it after incrementation.  */
    struct iv *iv;	/* The value of the candidate.  */
*************** dump_cand (FILE *file, struct iv_cand *c
*** 377,382 ****
--- 380,389 ----
      case IP_END:
        fprintf (file, "  incremented at end\n");
        break;
+ 
+     case IP_ORIGINAL:
+       fprintf (file, "  original biv\n");
+       break;
      }
  
     if (iv->step)
*************** stmt_after_ip_normal_pos (tree stmt)
*** 896,901 ****
--- 903,962 ----
    return stmt == last_stmt (bb);
  }
  
+ /* Returns true if STMT if after the place where the original induction
+    variable CAND is incremented.  */
+ 
+ static bool
+ stmt_after_ip_original_pos (struct iv_cand *cand, tree stmt)
+ {
+   basic_block cand_bb = bb_for_stmt (cand->incremented_at);
+   basic_block stmt_bb = bb_for_stmt (stmt);
+   block_stmt_iterator bsi;
+ 
+   if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
+     return false;
+ 
+   if (stmt_bb != cand_bb)
+     return true;
+ 
+   /* Scan the block from the end, since the original ivs are usually
+      incremented at the end of the loop body.  */
+   for (bsi = bsi_last (stmt_bb); ; bsi_prev (&bsi))
+     {
+       if (bsi_stmt (bsi) == cand->incremented_at)
+ 	return false;
+       if (bsi_stmt (bsi) == stmt)
+ 	return true;
+     }
+ }
+ 
+ /* Returns true if STMT if after the place where the induction variable
+    CAND is incremented.  */
+ 
+ static bool
+ stmt_after_increment (struct iv_cand *cand, tree stmt)
+ {
+   switch (cand->pos)
+     {
+ #if DISABLE_IP_START
+     case IP_START:
+       return true;
+ #endif
+ 
+     case IP_END:
+       return false;
+ 
+     case IP_NORMAL:
+       return stmt_after_ip_normal_pos (stmt);
+ 
+     case IP_ORIGINAL:
+       return stmt_after_ip_original_pos (cand, stmt);
+ 
+     default:
+       abort ();
+     }
+ }
+ 
  /* Initializes data structures used by the iv optimization pass.  LOOPS is the
     loop tree.  */
  
*************** find_givs_in_stmt (tree stmt)
*** 1170,1175 ****
--- 1231,1243 ----
        op0 = TREE_OPERAND (rhs, 0);
        if (!get_var_def (op0, &base0, &step0))
  	return;
+ 
+       if (TREE_TYPE (op0) != type)
+ 	{
+ 	  base0 = convert (type, base0);
+ 	  if (step0)
+ 	    step0 = convert (type, step0);
+ 	}
      }
  
    if (class == '2')
*************** find_givs_in_stmt (tree stmt)
*** 1177,1182 ****
--- 1245,1257 ----
        op1 = TREE_OPERAND (rhs, 1);
        if (!get_var_def (op1, &base, &step))
  	return;
+ 
+       if (TREE_TYPE (op1) != type)
+ 	{
+ 	  base = convert (type, base);
+ 	  if (step)
+ 	    step = convert (type, step);
+ 	}
      }
  
    switch (code)
*************** record_invariant (tree op, bool nonlinea
*** 1744,1750 ****
    basic_block bb;
    struct version_info *info;
  
!   if (TREE_CODE (op) != SSA_NAME)
      return;
  
    bb = bb_for_stmt (SSA_NAME_DEF_STMT (op));
--- 1819,1826 ----
    basic_block bb;
    struct version_info *info;
  
!   if (TREE_CODE (op) != SSA_NAME
!       || !is_gimple_reg (op))
      return;
  
    bb = bb_for_stmt (SSA_NAME_DEF_STMT (op));
*************** find_interesting_uses (void)
*** 2128,2136 ****
     position to POS.  If USE is not NULL, the candidate is set as related to
     it.  */
  
! static void
  add_candidate_1 (tree base, tree step, bool important, enum iv_position pos,
! 		 struct iv_use *use)
  {
    unsigned i;
    struct iv_cand *cand = NULL;
--- 2204,2212 ----
     position to POS.  If USE is not NULL, the candidate is set as related to
     it.  */
  
! static struct iv_cand *
  add_candidate_1 (tree base, tree step, bool important, enum iv_position pos,
! 		 struct iv_use *use, tree incremented_at)
  {
    unsigned i;
    struct iv_cand *cand = NULL;
*************** add_candidate_1 (tree base, tree step, b
*** 2142,2147 ****
--- 2218,2226 ----
        if (cand->pos != pos)
  	continue;
  
+       if (cand->incremented_at != incremented_at)
+ 	continue;
+ 
        if (!operand_equal_p (base, cand->iv->base, 0))
  	continue;
  
*************** add_candidate_1 (tree base, tree step, b
*** 2163,2171 ****
        cand->id = i;
        cand->iv = alloc_iv (base, step);
        cand->pos = pos;
!       cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
!       cand->var_after = cand->var_before;
        cand->important = important;
        VARRAY_PUSH_GENERIC_PTR_NOGC (iv_candidates, cand);
  
        if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
--- 2242,2254 ----
        cand->id = i;
        cand->iv = alloc_iv (base, step);
        cand->pos = pos;
!       if (pos != IP_ORIGINAL)
! 	{
! 	  cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
! 	  cand->var_after = cand->var_before;
! 	}
        cand->important = important;
+       cand->incremented_at = incremented_at;
        VARRAY_PUSH_GENERIC_PTR_NOGC (iv_candidates, cand);
  
        if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
*************** add_candidate_1 (tree base, tree step, b
*** 2186,2191 ****
--- 2269,2276 ----
  	fprintf (tree_dump_file, "Candidate %d is related to use %d\n",
  		 cand->id, use->id);
      }
+ 
+   return cand;
  }
  
  /* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
*************** static void
*** 2196,2207 ****
  add_candidate (tree base, tree step, bool important, struct iv_use *use)
  {
  #if DISABLE_IP_START
!   add_candidate_1 (base, step, important, IP_START, use);
  #endif
    if (ip_normal_pos ())
!     add_candidate_1 (base, step, important, IP_NORMAL, use);
    if (ip_end_pos ())
!     add_candidate_1 (base, step, important, IP_END, use);
  }
  
  /* Adds standard iv candidates.  */
--- 2281,2294 ----
  add_candidate (tree base, tree step, bool important, struct iv_use *use)
  {
  #if DISABLE_IP_START
!   /* Shift the initial value so that the value in the body matches.  */
!   add_candidate_1 (fold (MINUS_EXPR, TREE_TYPE (base), base, step),
! 		   step, important, IP_START, use, NULL_TREE);
  #endif
    if (ip_normal_pos ())
!     add_candidate_1 (base, step, important, IP_NORMAL, use, NULL_TREE);
    if (ip_end_pos ())
!     add_candidate_1 (base, step, important, IP_END, use, NULL_TREE);
  }
  
  /* Adds standard iv candidates.  */
*************** add_standard_iv_candidates (void)
*** 2225,2236 ****
  
  static void
  add_old_iv_candidates (struct iv *iv)
! { 
    add_candidate (iv->base, iv->step, true, NULL);
  
    /* The same, but with initial value zero.  */
    add_candidate (convert (TREE_TYPE (iv->base), integer_zero_node),
  		 iv->step, true, NULL);
  }
  
  /* Adds candidates based on the old induction variables.  */
--- 2312,2338 ----
  
  static void
  add_old_iv_candidates (struct iv *iv)
! {
!   tree phi, def;
!   struct iv_cand *cand;
! 
    add_candidate (iv->base, iv->step, true, NULL);
  
    /* The same, but with initial value zero.  */
    add_candidate (convert (TREE_TYPE (iv->base), integer_zero_node),
  		 iv->step, true, NULL);
+ 
+   phi = SSA_NAME_DEF_STMT (iv->ssa_name);
+   if (TREE_CODE (phi) == PHI_NODE)
+     {
+       /* Additionally record the possibility of leaving the original iv
+ 	 untouched.  */
+       def = phi_element_for_edge (phi, loop_latch_edge (current_loop))->def;
+       cand = add_candidate_1 (iv->base, iv->step, true, IP_ORIGINAL, NULL,
+ 			      SSA_NAME_DEF_STMT (def));
+       cand->var_before = iv->ssa_name;
+       cand->var_after = def;
+     }
  }
  
  /* Adds candidates based on the old induction variables.  */
*************** computation_cost (tree expr)
*** 2542,2566 ****
  static tree
  var_at_use (struct iv_use *use, struct iv_cand *cand)
  {
!   switch (cand->pos)
!     {
! #if DISABLE_IP_START
!     case IP_START:
!       return cand->var_after;
! #endif
! 
!     case IP_NORMAL:
!       if (stmt_after_ip_normal_pos (use->stmt))
! 	return cand->var_after;
!       else
! 	return cand->var_before;
! 
!     case IP_END:
!       return cand->var_before;
! 
!     default:
!       abort ();
!     }
  }
  
  /* Determines the expression by that USE is expressed from induction variable
--- 2644,2653 ----
  static tree
  var_at_use (struct iv_use *use, struct iv_cand *cand)
  {
!   if (stmt_after_increment (cand, use->stmt))
!     return cand->var_after;
!   else
!     return cand->var_before;
  }
  
  /* Determines the expression by that USE is expressed from induction variable
*************** get_computation (struct iv_use *use, str
*** 2607,2616 ****
        return NULL_TREE;
      }
  
!   /* If we are after the "normal" position, the value of the candidate is
!      higher by one iteration.  */
!   if (cand->pos == IP_NORMAL
!       && stmt_after_ip_normal_pos (use->stmt))
      cbase = fold (build (PLUS_EXPR, utype, cbase, cstep));
  
    /* use = ubase + ratio * (var - cbase).  If either cbase is a constant
--- 2694,2701 ----
        return NULL_TREE;
      }
  
!   /* We may need to shift the value if we are after the increment.  */
!   if (stmt_after_increment (cand, use->stmt))
      cbase = fold (build (PLUS_EXPR, utype, cbase, cstep));
  
    /* use = ubase + ratio * (var - cbase).  If either cbase is a constant
*************** get_computation_cost (struct iv_use *use
*** 3278,3287 ****
  			       depends_on);
      }
  
!   /* If we are after the "normal" position, the value of the candidate is
!      higher by one iteration.  */
!   if (cand->pos == IP_NORMAL
!       && stmt_after_ip_normal_pos (use->stmt))
      offset -= ratio * cstepi;
  
    /* Now the computation is in shape symbol + var1 + const + ratio * var2.
--- 3363,3371 ----
  			       depends_on);
      }
  
!   /* If we are after the increment, the value of the candidate is higher by
!      one iteration.  */
!   if (stmt_after_increment (cand, use->stmt))
      offset -= ratio * cstepi;
  
    /* Now the computation is in shape symbol + var1 + const + ratio * var2.
*************** cand_value_at (struct iv_cand *cand, str
*** 3357,3364 ****
    tree val;
    tree type = TREE_TYPE (niter);
  
!   if (cand->pos == IP_NORMAL
!       && stmt_after_ip_normal_pos (use->stmt))
      niter = fold (build (PLUS_EXPR, type, niter,
  			 convert (type, integer_one_node)));
  
--- 3441,3447 ----
    tree val;
    tree type = TREE_TYPE (niter);
  
!   if (stmt_after_increment (cand, use->stmt))
      niter = fold (build (PLUS_EXPR, type, niter,
  			 convert (type, integer_one_node)));
  
*************** determine_iv_cost (struct iv_cand *cand)
*** 3551,3572 ****
       and its initialization.  The second is almost negligible for any loop
       that rolls enough, so we take it just very little into account.  */
  
- #if DISABLE_IP_START
-   tree type = TREE_TYPE (base);
- 
-   if (cand->pos == IP_START)
-     {
-       /* We must decrease the base, because it will get increased just at the
- 	 start of the loop body.  */
-       base = fold (build (MINUS_EXPR, type, base, cand->iv->step));
-     }
- #endif
- 
    cost_base = force_var_cost (base, NULL);
    cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
  
    /* TODO use profile to determine the ratio here.  */
    cand->cost = cost_step + cost_base / 5;
  }
  
  /* Determines costs of computation of the candidates.  */
--- 3634,3648 ----
       and its initialization.  The second is almost negligible for any loop
       that rolls enough, so we take it just very little into account.  */
  
    cost_base = force_var_cost (base, NULL);
    cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
  
    /* TODO use profile to determine the ratio here.  */
    cand->cost = cost_step + cost_base / 5;
+ 
+   /* Prefer the original iv unless we may gain something by replacing it.  */
+   if (cand->pos == IP_ORIGINAL)
+     cand->cost--;
  }
  
  /* Determines costs of computation of the candidates.  */
*************** find_best_candidate (struct iv_use *use,
*** 3757,3764 ****
        acnd = VARRAY_GENERIC_PTR_NOGC (iv_candidates, c);
        cost = get_use_iv_cost (use, acnd, &depends_on);
  
!       if (cost >= best_cost)
  	goto next_cand;
  
        if (depends_on)
  	{
--- 3833,3848 ----
        acnd = VARRAY_GENERIC_PTR_NOGC (iv_candidates, c);
        cost = get_use_iv_cost (use, acnd, &depends_on);
  
!       if (cost == INFTY)
! 	goto next_cand;
!       if (cost > best_cost)
  	goto next_cand;
+       if (cost == best_cost)
+ 	{
+ 	  /* Prefer the cheaper iv.  */
+ 	  if (acnd->cost >= cnd->cost)
+ 	    goto next_cand;
+ 	}
  
        if (depends_on)
  	{
*************** create_new_iv (struct iv_cand *cand)
*** 4067,4086 ****
        incr_pos = bsi_last (ip_end_pos ());
        after = true;
        break;
      }
   
    gimple_add_tmp_var (cand->var_before);
    add_referenced_tmp_var (cand->var_before);
  
    base = unshare_expr (cand->iv->base);
- #if DISABLE_IP_START
-   if (cand->pos == IP_START)
-     {
-       /* We must decrease the base, because it will get increased just at the
- 	 start of the loop body.  */
-       base = fold (build (MINUS_EXPR, TREE_TYPE (base), base, cand->iv->step));
-     }
- #endif
  
    create_iv (base, cand->iv->step, cand->var_before, current_loop,
  	     &incr_pos, after, &cand->var_before, &cand->var_after);
--- 4151,4166 ----
        incr_pos = bsi_last (ip_end_pos ());
        after = true;
        break;
+ 
+     case IP_ORIGINAL:
+       /* Nothing to do here.  */
+       return;
      }
   
    gimple_add_tmp_var (cand->var_before);
    add_referenced_tmp_var (cand->var_before);
  
    base = unshare_expr (cand->iv->base);
  
    create_iv (base, cand->iv->step, cand->var_before, current_loop,
  	     &incr_pos, after, &cand->var_before, &cand->var_after);


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