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]

[patch] for PR 18800


Hello,

the problem in this PR is that the algorithm for finding the new
set of induction variables gets struck in a local optimum.  Basically what
happens is that the costs are as follows:

  candidate  \ use            U          V
      C                       1          2
      D                       4          1

Obviously the best way is to have just C as an induction variable, with
cost of 3.  But the initial set happens to consist of D (cost 5).  However when
we try to insert the new induction variable C to the set, we get that
the best way is to express U by C and V by D, with cost of 7 (2 for uses +
4 for an extra induction variable), so we stick with the original chouce
of D.

This patch fixes the problem by also trying to remove the variables from
the newly formed set, provided that the set is small enough (to avoid
compile time problems).  Thus we find out that by removing D from the
set, we get the optimal choice.

Bootstrapped & regtested on i686, ppc and x86_64.

Zdenek

        PR tree-optimization/18800
        * params.def (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND): New parameter.
        * tree-ssa-loop-ivopts.c (struct iv_ca): Add n_cands field.
        (ALWAYS_PRUNE_CAND_SET_BOUND): New macro.
        (iv_ca_set_no_cp, iv_ca_set_cp, iv_ca_new): Update n_cands field.
        (iv_ca_delta_join, iv_ca_delta_reverse, iv_ca_n_cands, iv_ca_prune):
        New functions.
        (iv_ca_extend): Return number of candidates in the set.
        (try_add_cand_for): Add argument to iv_ca_extend calls.
        (try_improve_iv_set): Use iv_ca_prune.
        * doc/invoke.texi (iv-always-prune-cand-set-bound): Document.

Index: params.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/params.def,v
retrieving revision 1.50
diff -c -3 -p -r1.50 params.def
*** params.def	1 Dec 2004 16:46:24 -0000	1.50
--- params.def	13 Dec 2004 00:56:01 -0000
*************** DEFPARAM(PARAM_IV_MAX_CONSIDERED_USES,
*** 347,352 ****
--- 347,360 ----
  	 "Bound on number of iv uses in loop optimized in iv optimizations",
  	 250, 0, 0)
  
+ /* If there are at most this number of ivs in the set, try removing unnecessary
+    ivs from the set always.  */
+ 
+ DEFPARAM(PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND,
+ 	 "iv-always-prune-cand-set-bound",
+ 	 "If number of candidates in the set is smaller, we always try to remove unused ivs during its optimization",
+ 	 10, 0, 0)
+ 
  /* The product of the next two is used to decide whether or not to
     use .GLOBAL_VAR.  See tree-dfa.c.  */
  DEFPARAM(PARAM_GLOBAL_VAR_THRESHOLD,
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.35
diff -c -3 -p -r2.35 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c	7 Dec 2004 21:23:04 -0000	2.35
--- tree-ssa-loop-ivopts.c	13 Dec 2004 00:56:01 -0000
*************** struct iv_ca
*** 244,249 ****
--- 244,252 ----
    /* The candidates used.  */
    bitmap cands;
  
+   /* The number of candidates in the set.  */
+   unsigned n_cands;
+ 
    /* Total number of registers needed.  */
    unsigned n_regs;
  
*************** struct iv_ca_delta
*** 288,293 ****
--- 291,302 ----
  #define MAX_CONSIDERED_USES \
    ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES))
  
+ /* If there are at most this number of ivs in the set, try removing unnecessary
+    ivs from the set always.  */
+ 
+ #define ALWAYS_PRUNE_CAND_SET_BOUND \
+   ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND))
+ 
  /* The list of trees for that the decl_rtl field must be reset is stored
     here.  */
  
*************** iv_ca_set_no_cp (struct ivopts_data *dat
*** 3661,3666 ****
--- 3670,3676 ----
        /* Do not count the pseudocandidates.  */
        if (cp->cand->iv)
  	ivs->n_regs--;
+       ivs->n_cands--;
        ivs->cand_cost -= cp->cand->cost;
      }
  
*************** iv_ca_set_cp (struct ivopts_data *data, 
*** 3710,3715 ****
--- 3720,3726 ----
  	  /* Do not count the pseudocandidates.  */
  	  if (cp->cand->iv)
  	    ivs->n_regs++;
+ 	  ivs->n_cands++;
  	  ivs->cand_cost += cp->cand->cost;
  	}
  
*************** iv_ca_delta_add (struct iv_use *use, str
*** 3806,3811 ****
--- 3817,3843 ----
    return change;
  }
  
+ /* Joins two lists of changes L1 and L2.  Destructive -- old lists
+    are rewritten.   */
+ 
+ static struct iv_ca_delta *
+ iv_ca_delta_join (struct iv_ca_delta *l1, struct iv_ca_delta *l2)
+ {
+   struct iv_ca_delta *last;
+ 
+   if (!l2)
+     return l1;
+ 
+   if (!l1)
+     return l2;
+ 
+   for (last = l1; last->next_change; last = last->next_change)
+     continue;
+   last->next_change = l2;
+ 
+   return l1;
+ }
+ 
  /* Returns candidate by that USE is expressed in IVS.  */
  
  static struct cost_pair *
*************** iv_ca_cand_for_use (struct iv_ca *ivs, s
*** 3814,3819 ****
--- 3846,3873 ----
    return ivs->cand_for_use[use->id];
  }
  
+ /* Reverse the list of changes DELTA, forming the inverse to it.  */
+ 
+ static struct iv_ca_delta *
+ iv_ca_delta_reverse (struct iv_ca_delta *delta)
+ {
+   struct iv_ca_delta *act, *next, *prev = NULL;
+   struct cost_pair *tmp;
+ 
+   for (act = delta; act; act = next)
+     {
+       next = act->next_change;
+       act->next_change = prev;
+       prev = act;
+ 
+       tmp = act->old_cp;
+       act->old_cp = act->new_cp;
+       act->new_cp = tmp;
+     }
+ 
+   return prev;
+ }
+ 
  /* Commit changes in DELTA to IVS.  If FORWARD is false, the changes are
     reverted instead.  */
  
*************** iv_ca_delta_commit (struct ivopts_data *
*** 3822,3844 ****
  		    struct iv_ca_delta *delta, bool forward)
  {
    struct cost_pair *from, *to;
  
!   for (; delta; delta = delta->next_change)
!     {
!       if (forward)
! 	{
! 	  from = delta->old_cp;
! 	  to = delta->new_cp;
! 	}
!       else
! 	{
! 	  from = delta->new_cp;
! 	  to = delta->old_cp;
! 	}
  
!       gcc_assert (iv_ca_cand_for_use (ivs, delta->use) == from);
!       iv_ca_set_cp (data, ivs, delta->use, to);
      }
  }
  
  /* Returns true if CAND is used in IVS.  */
--- 3876,3896 ----
  		    struct iv_ca_delta *delta, bool forward)
  {
    struct cost_pair *from, *to;
+   struct iv_ca_delta *act;
  
!   if (!forward)
!     delta = iv_ca_delta_reverse (delta);
  
!   for (act = delta; act; act = act->next_change)
!     {
!       from = act->old_cp;
!       to = act->new_cp;
!       gcc_assert (iv_ca_cand_for_use (ivs, act->use) == from);
!       iv_ca_set_cp (data, ivs, act->use, to);
      }
+ 
+   if (!forward)
+     iv_ca_delta_reverse (delta);
  }
  
  /* Returns true if CAND is used in IVS.  */
*************** iv_ca_cand_used_p (struct iv_ca *ivs, st
*** 3849,3854 ****
--- 3901,3914 ----
    return ivs->n_cand_uses[cand->id] > 0;
  }
  
+ /* Returns number of induction variable candidates in the set IVS.  */
+ 
+ static unsigned
+ iv_ca_n_cands (struct iv_ca *ivs)
+ {
+   return ivs->n_cands;
+ }
+ 
  /* Free the list of changes DELTA.  */
  
  static void
*************** iv_ca_new (struct ivopts_data *data)
*** 3877,3882 ****
--- 3937,3943 ----
    nw->cand_for_use = xcalloc (n_iv_uses (data), sizeof (struct cost_pair *));
    nw->n_cand_uses = xcalloc (n_iv_cands (data), sizeof (unsigned));
    nw->cands = BITMAP_XMALLOC ();
+   nw->n_cands = 0;
    nw->n_regs = 0;
    nw->cand_use_cost = 0;
    nw->cand_cost = 0;
*************** iv_ca_dump (struct ivopts_data *data, FI
*** 3920,3930 ****
  }
  
  /* Try changing candidate in IVS to CAND for each use.  Return cost of the
!    new set, and store differences in DELTA.  */
  
  static unsigned
  iv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs,
! 	      struct iv_cand *cand, struct iv_ca_delta **delta)
  {
    unsigned i, cost;
    struct iv_use *use;
--- 3981,3993 ----
  }
  
  /* Try changing candidate in IVS to CAND for each use.  Return cost of the
!    new set, and store differences in DELTA.  Number of induction variables
!    in the new set is stored to N_IVS.  */
  
  static unsigned
  iv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs,
! 	      struct iv_cand *cand, struct iv_ca_delta **delta,
! 	      unsigned *n_ivs)
  {
    unsigned i, cost;
    struct iv_use *use;
*************** iv_ca_extend (struct ivopts_data *data, 
*** 3955,3960 ****
--- 4018,4025 ----
  
    iv_ca_delta_commit (data, ivs, *delta, true);
    cost = iv_ca_cost (ivs);
+   if (n_ivs)
+     *n_ivs = iv_ca_n_cands (ivs);
    iv_ca_delta_commit (data, ivs, *delta, false);
  
    return cost;
*************** iv_ca_narrow (struct ivopts_data *data, 
*** 4044,4049 ****
--- 4109,4163 ----
    return cost;
  }
  
+ /* Try optimizing the set of candidates IVS by removing candidates different
+    from to EXCEPT_CAND from it.  Return cost of the new set, and store
+    differences in DELTA.  */
+ 
+ static unsigned
+ iv_ca_prune (struct ivopts_data *data, struct iv_ca *ivs,
+ 	     struct iv_cand *except_cand, struct iv_ca_delta **delta)
+ {
+   bitmap_iterator bi;
+   struct iv_ca_delta *act_delta, *best_delta;
+   unsigned i, best_cost, acost;
+   struct iv_cand *cand;
+ 
+   best_delta = NULL;
+   best_cost = iv_ca_cost (ivs);
+ 
+   EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi)
+     {
+       cand = iv_cand (data, i);
+ 
+       if (cand == except_cand)
+ 	continue;
+ 
+       acost = iv_ca_narrow (data, ivs, cand, &act_delta);
+ 
+       if (acost < best_cost)
+ 	{
+ 	  best_cost = acost;
+ 	  iv_ca_delta_free (&best_delta);
+ 	  best_delta = act_delta;
+ 	}
+       else
+ 	iv_ca_delta_free (&act_delta);
+     }
+ 
+   if (!best_delta)
+     {
+       *delta = NULL;
+       return best_cost;
+     }
+ 
+   /* Recurse to possibly remove other unnecessary ivs.  */
+   iv_ca_delta_commit (data, ivs, best_delta, true);
+   best_cost = iv_ca_prune (data, ivs, except_cand, delta);
+   iv_ca_delta_commit (data, ivs, best_delta, false);
+   *delta = iv_ca_delta_join (best_delta, *delta);
+   return best_cost;
+ }
+ 
  /* Tries to extend the sets IVS in the best possible way in order
     to express the USE.  */
  
*************** try_add_cand_for (struct ivopts_data *da
*** 4088,4094 ****
  	continue;
  
        iv_ca_set_cp (data, ivs, use, cp);
!       act_cost = iv_ca_extend (data, ivs, cand, &act_delta);
        iv_ca_set_no_cp (data, ivs, use);
        act_delta = iv_ca_delta_add (use, NULL, cp, act_delta);
  
--- 4202,4208 ----
  	continue;
  
        iv_ca_set_cp (data, ivs, use, cp);
!       act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
        iv_ca_set_no_cp (data, ivs, use);
        act_delta = iv_ca_delta_add (use, NULL, cp, act_delta);
  
*************** try_add_cand_for (struct ivopts_data *da
*** 4121,4127 ****
  
  	  act_delta = NULL;
  	  iv_ca_set_cp (data, ivs, use, cp);
! 	  act_cost = iv_ca_extend (data, ivs, cand, &act_delta);
  	  iv_ca_set_no_cp (data, ivs, use);
  	  act_delta = iv_ca_delta_add (use, iv_ca_cand_for_use (ivs, use),
  				       cp, act_delta);
--- 4235,4241 ----
  
  	  act_delta = NULL;
  	  iv_ca_set_cp (data, ivs, use, cp);
! 	  act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL);
  	  iv_ca_set_no_cp (data, ivs, use);
  	  act_delta = iv_ca_delta_add (use, iv_ca_cand_for_use (ivs, use),
  				       cp, act_delta);
*************** get_initial_solution (struct ivopts_data
*** 4168,4192 ****
  static bool
  try_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs)
  {
!   unsigned i, acost, best_cost = iv_ca_cost (ivs);
!   struct iv_ca_delta *best_delta = NULL, *act_delta;
    struct iv_cand *cand;
  
!   /* Try altering 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))
! 	acost = iv_ca_narrow (data, ivs, cand, &act_delta);
!       else
! 	acost = iv_ca_extend (data, ivs, cand, &act_delta);
  
        if (acost < best_cost)
  	{
  	  best_cost = acost;
! 	  if (best_delta)
! 	    iv_ca_delta_free (&best_delta);
  	  best_delta = act_delta;
  	}
        else
--- 4282,4317 ----
  static bool
  try_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs)
  {
!   unsigned i, acost, best_cost = iv_ca_cost (ivs), n_ivs;
!   struct iv_ca_delta *best_delta = NULL, *act_delta, *tmp_delta;
    struct iv_cand *cand;
  
!   /* 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;
! 
!       acost = iv_ca_extend (data, ivs, cand, &act_delta, &n_ivs);
!       if (!act_delta)
! 	continue;
! 
!       /* If we successfully added the candidate and the set is small enough,
! 	 try optimizing it by removing other candidates.  */
!       if (n_ivs <= ALWAYS_PRUNE_CAND_SET_BOUND)
!       	{
! 	  iv_ca_delta_commit (data, ivs, act_delta, true);
! 	  acost = iv_ca_prune (data, ivs, cand, &tmp_delta);
! 	  iv_ca_delta_commit (data, ivs, act_delta, false);
! 	  act_delta = iv_ca_delta_join (act_delta, tmp_delta);
! 	}
  
        if (acost < best_cost)
  	{
  	  best_cost = acost;
! 	  iv_ca_delta_free (&best_delta);
  	  best_delta = act_delta;
  	}
        else
*************** try_improve_iv_set (struct ivopts_data *
*** 4194,4202 ****
      }
  
    if (!best_delta)
!     return false;
  
    iv_ca_delta_commit (data, ivs, best_delta, true);
    iv_ca_delta_free (&best_delta);
    return true;
  }
--- 4319,4335 ----
      }
  
    if (!best_delta)
!     {
!       /* Try removing the candidates from the set instead.  */
!       best_cost = iv_ca_prune (data, ivs, NULL, &best_delta);
! 
!       /* Nothing more we can do.  */
!       if (!best_delta)
! 	return false;
!     }
  
    iv_ca_delta_commit (data, ivs, best_delta, true);
+   gcc_assert (best_cost == iv_ca_cost (ivs));
    iv_ca_delta_free (&best_delta);
    return true;
  }
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.560
diff -c -3 -p -r1.560 invoke.texi
*** doc/invoke.texi	8 Dec 2004 01:20:34 -0000	1.560
--- doc/invoke.texi	13 Dec 2004 00:56:01 -0000
*************** if there are more candidates, to avoid q
*** 5475,5480 ****
--- 5475,5485 ----
  The induction variable optimizations give up on loops that contain more
  induction variable uses.
  
+ @item iv-always-prune-cand-set-bound
+ If number of candidates in the set is smaller than this value,
+ we always try to remove unnecessary ivs from the set during its
+ optimization when a new iv is added to the set.
+ 
  @item max-iterations-to-track
  
  The maximum number of iterations of a loop the brute force algorithm


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