[lno] Fix PR 16656

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

Hello,

the problem with this testcase was that it contains a loop with some
2500 occurences of a memory reference whose address can be expressed
as an iv.  Since the algorithm used to find a good set of ivs is
worst-case cubic in the number of ivs, this lead to effectively
infinite loop.

This patch

1) Bounds the maximum number of iv uses that a considered loop may
   contain.
2) Makes the decision procedure more efficient -- even if
   MAX_CONSIDERED_USES is set to infinity, we manage to compile the
   testcase with "only" 70% of compile time spent by ivopts now.

Zdenek

Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.232
diff -c -3 -p -r1.1.2.232 ChangeLog.lno
*** ChangeLog.lno	22 Jul 2004 12:00:45 -0000	1.1.2.232
--- ChangeLog.lno	23 Jul 2004 14:02:50 -0000
***************
*** 1,3 ****
--- 1,15 ----
+ 2004-07-23  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>
+ 
+ 	PR tree-optimization/16656
+ 	* tree-ssa-loop-ivopts.c (CONSIDER_ALL_CANDIDATES_BOUND): Increase
+ 	to 30.
+ 	(MAX_CONSIDERED_USES): New.
+ 	(set_cost_up_to, try_add_cand_for): New functions.
+ 	(set_cost): Use set_cost_up_to.
+ 	(find_best_candidate, get_initial_solution): Improve efficiency.
+ 	(tree_ssa_iv_optimize_loop): Fail if there are more than
+ 	MAX_CONSIDERED_USES iv uses in the loop.
+ 
  2004-07-22  Dorit Naishlos <dorit@il.ibm.com>
  
          * tree-data-ref.c (array_base_name_differ_p): Add comments, and consider
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-ivopts.c,v
retrieving revision 1.1.2.47
diff -c -3 -p -r1.1.2.47 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c	22 Jul 2004 01:01:36 -0000	1.1.2.47
--- tree-ssa-loop-ivopts.c	23 Jul 2004 14:02:50 -0000
*************** struct ivopts_data
*** 224,230 ****
  
  /* Bound on number of candidates below that all candidates are considered.  */
  
! #define CONSIDER_ALL_CANDIDATES_BOUND 15
  
  /* The properties of the target.  */
  
--- 224,234 ----
  
  /* Bound on number of candidates below that all candidates are considered.  */
  
! #define CONSIDER_ALL_CANDIDATES_BOUND 30
! 
! /* If there are more iv occurences, we just give up (it is quite unlikely that
!    optimizing such a loop would help, and it would take ages).  */
! #define MAX_CONSIDERED_USES 250
  
  /* The properties of the target.  */
  
*************** find_best_candidate (struct ivopts_data 
*** 3708,3716 ****
    unsigned c, d;
    unsigned best_cost = INFTY, cost;
    struct iv_cand *cnd = NULL, *acnd;
!   bitmap depends_on = NULL;
  
!   EXECUTE_IF_SET_IN_BITMAP (sol, 0, c,
      {
        acnd = iv_cand (data, c);
        cost = get_use_iv_cost (data, use, acnd, &depends_on);
--- 3712,3728 ----
    unsigned c, d;
    unsigned best_cost = INFTY, cost;
    struct iv_cand *cnd = NULL, *acnd;
!   bitmap depends_on = NULL, asol;
! 
!   if (data->consider_all_candidates)
!     asol = sol;
!   else
!     {
!       asol = BITMAP_XMALLOC ();
!       bitmap_a_and_b (asol, sol, use->related_cands);
!     }
  
!   EXECUTE_IF_SET_IN_BITMAP (asol, 0, c,
      {
        acnd = iv_cand (data, c);
        cost = get_use_iv_cost (data, use, acnd, &depends_on);
*************** next_cand: ;
*** 3745,3758 ****
    if (cand)
      *cand = cnd;
  
    return best_cost;
  }
  
! /* Computes cost of set of ivs SOL + invariants INV.  Removes unnecessary
!    induction variable candidates and invariants from the sets.  */
  
  static unsigned
! set_cost (struct ivopts_data *data, bitmap sol, bitmap inv)
  {
    unsigned i;
    unsigned cost = 0, size = 0, acost;
--- 3757,3775 ----
    if (cand)
      *cand = cnd;
  
+   if (!data->consider_all_candidates)
+     BITMAP_XFREE (asol);
+ 
    return best_cost;
  }
  
! /* Returns cost of set of ivs SOL + invariants INV.  Removes unnecessary
!    induction variable candidates and invariants from the sets.  Only
!    uses 0 .. MAX_USE - 1 are taken into account.  */
  
  static unsigned
! set_cost_up_to (struct ivopts_data *data, bitmap sol, bitmap inv,
! 		unsigned max_use)
  {
    unsigned i;
    unsigned cost = 0, size = 0, acost;
*************** set_cost (struct ivopts_data *data, bitm
*** 3760,3766 ****
    struct iv_cand *cand;
    bitmap used_ivs = BITMAP_XMALLOC (), used_inv = BITMAP_XMALLOC ();
  
!   for (i = 0; i < n_iv_uses (data); i++)
      {
        use = iv_use (data, i);
        acost = find_best_candidate (data, use, sol, inv,
--- 3777,3783 ----
    struct iv_cand *cand;
    bitmap used_ivs = BITMAP_XMALLOC (), used_inv = BITMAP_XMALLOC ();
  
!   for (i = 0; i < max_use; i++)
      {
        use = iv_use (data, i);
        acost = find_best_candidate (data, use, sol, inv,
*************** set_cost (struct ivopts_data *data, bitm
*** 3796,3801 ****
--- 3813,3878 ----
    return cost;
  }
  
+ /* Computes cost of set of ivs SOL + invariants INV.  Removes unnecessary
+    induction variable candidates and invariants from the sets.  */
+ 
+ static unsigned
+ set_cost (struct ivopts_data *data, bitmap sol, bitmap inv)
+ {
+   return set_cost_up_to (data, sol, inv, n_iv_uses (data));
+ }
+ 
+ /* Tries to extend the sets IVS and INV in the best possible way in order
+    to express the USE.  */
+ 
+ static bool
+ try_add_cand_for (struct ivopts_data *data, bitmap ivs, bitmap inv,
+ 		  struct iv_use *use)
+ {
+   unsigned best_cost = set_cost_up_to (data, ivs, inv, use->id + 1), act_cost;
+   bitmap best_ivs = BITMAP_XMALLOC ();
+   bitmap best_inv = BITMAP_XMALLOC ();
+   bitmap act_ivs = BITMAP_XMALLOC ();
+   bitmap act_inv = BITMAP_XMALLOC ();
+   unsigned i;
+   struct cost_pair *cp;
+ 
+   bitmap_copy (best_ivs, ivs);
+   bitmap_copy (best_inv, inv);
+ 
+   for (i = 0; i < use->n_map_members; i++)
+     {
+       cp = use->cost_map + i;
+       if (cp->cost == INFTY)
+ 	continue;
+ 
+       bitmap_copy (act_ivs, ivs);
+       bitmap_set_bit (act_ivs, cp->cand->id);
+       if (cp->depends_on)
+ 	bitmap_a_or_b (act_inv, inv, cp->depends_on);
+       else
+ 	bitmap_copy (act_inv, inv);
+       act_cost = set_cost_up_to (data, act_ivs, act_inv, use->id + 1);
+ 
+       if (act_cost < best_cost)
+ 	{
+ 	  best_cost = act_cost;
+ 	  bitmap_copy (best_ivs, act_ivs);
+ 	  bitmap_copy (best_inv, act_inv);
+ 	}
+     }
+ 
+   bitmap_copy (ivs, best_ivs);
+   bitmap_copy (inv, best_inv);
+ 
+   BITMAP_XFREE (best_ivs);
+   BITMAP_XFREE (best_inv);
+   BITMAP_XFREE (act_ivs);
+   BITMAP_XFREE (act_inv);
+ 
+   return (best_cost != INFTY);
+ }
+ 
  /* Finds an initial set of IVS and invariants INV.  We do this by simply
     choosing the best candidate for each use.  */
  
*************** get_initial_solution (struct ivopts_data
*** 3804,3814 ****
  {
    unsigned i;
  
!   for (i = 0; i < n_iv_cands (data); i++)
!     bitmap_set_bit (ivs, i);
!   for (i = 1; i <= data->max_inv_id; i++)
!     if (!ver_info (data, i)->has_nonlin_use)
!       bitmap_set_bit (inv, i);
  
    return set_cost (data, ivs, inv);
  }
--- 3881,3889 ----
  {
    unsigned i;
  
!   for (i = 0; i < n_iv_uses (data); i++)
!     if (!try_add_cand_for (data, ivs, inv, iv_use (data, i)))
!       return INFTY;
  
    return set_cost (data, ivs, inv);
  }
*************** tree_ssa_iv_optimize_loop (struct ivopts
*** 4679,4684 ****
--- 4754,4761 ----
  
    /* Finds interesting uses (item 1).  */
    find_interesting_uses (data);
+   if (n_iv_uses (data) > MAX_CONSIDERED_USES)
+     goto finish;
  
    /* Finds candidates for the induction variables (item 2).  */
    find_iv_candidates (data);