diff mbox

Slightly tune to make iv cand choosing algorithm more accurate

Message ID 002301cee123$cfde9960$6f9bcc20$@arm.com
State New
Headers show

Commit Message

Bin Cheng Nov. 14, 2013, 10:25 a.m. UTC 
Hi,
The algorithm choosing candidates in IVOPT has some defects that optimal iv
set can't be found in some cases.  This patch slightly tunes the algorithm
to make it more accurate.   The reasons are:
1) Changes in iv_ca_extend.  Dependences could be changed in the loop,
causing check condition " !iv_ca_has_deps (ivs, new_cp) " in future
iterations inaccurate.  This is a minor change and won't matter really much.
2) Changes in iv_ca_narrow.  Start narrowing from the candidate just picked
by iv_ca_prune.  Consider below example:

	cand	cost
	0	4	
	1	5
	2	5
use 0
	cand	cost	dep
	0	4
	1	0
	2	4
use 1
	cand	cost	dep
	0	4
	1	5
	2	4
The initial iv set is:
	use	cand
	0	0
	1	0
Which can be improved to: 
	use	cand
	0	1
	1	1

But IVOPT can't find this iv set because after it extending to <use 0, cand
1; use 1, cand 0>, iv_ca_narrow won't consider "cand 1" for "use 1", because
it has higher cost than "cand 0".  Consequently, IVOPT gives up and can't
find out that overall cost of "cand 1" is cheaper than "cand 0".  I think
the situation is worse on targets support auto-increment addressing mode.

I also changed iv_ca_narrow by checking the overall cost, rather than single
cost_pair.

Bootstrap and test on x86/x86_64.
Arm on going,  is it OK if tests pass?

Thanks,
bin

2013-11-14  Bin Cheng  <bin.cheng@arm.com>

	* tree-ssa-loop-ivopts.c (iv_ca_extend): Commit each candidate
	and use pair instantly.
	(iv_ca_narrow): New parameter.  Start narrowing with START.
	Apply candidate-use pair and check overall cost in narrowing.
	(iv_ca_prune): Pass new argument.
diff mbox

Patch

Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c	(revision 204697)
+++ gcc/tree-ssa-loop-ivopts.c	(working copy)
@@ -5653,12 +5653,12 @@  iv_ca_extend (struct ivopts_data *data, struct iv_
 	continue;
 
       if (!min_ncand && !cheaper_cost_pair (new_cp, old_cp))
-        continue;
+	continue;
 
+      iv_ca_set_cp (data, ivs, use, new_cp);
       *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
     }
 
-  iv_ca_delta_commit (data, ivs, *delta, true);
   cost = iv_ca_cost (ivs);
   if (n_ivs)
     *n_ivs = iv_ca_n_cands (ivs);
@@ -5668,18 +5668,20 @@  iv_ca_extend (struct ivopts_data *data, struct iv_
 }
 
 /* Try narrowing set IVS by removing CAND.  Return the cost of
-   the new set and store the differences in DELTA.  */
+   the new set and store the differences in DELTA.  START is
+   the candidate with which we start narrowing.  */
 
 static comp_cost
 iv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs,
-	      struct iv_cand *cand, struct iv_ca_delta **delta)
+	      struct iv_cand *cand, struct iv_cand *start,
+	      struct iv_ca_delta **delta)
 {
   unsigned i, ci;
   struct iv_use *use;
   struct cost_pair *old_cp, *new_cp, *cp;
   bitmap_iterator bi;
   struct iv_cand *cnd;
-  comp_cost cost;
+  comp_cost cost, best_cost, acost;
 
   *delta = NULL;
   for (i = 0; i < n_iv_uses (data); i++)
@@ -5690,7 +5692,9 @@  iv_ca_narrow (struct ivopts_data *data, struct iv_
       if (old_cp->cand != cand)
 	continue;
 
-      new_cp = NULL;
+      best_cost = iv_ca_cost (ivs);
+      /* Start narrowing with START.  */
+      new_cp = get_use_iv_cost (data, use, start);
 
       if (data->consider_all_candidates)
 	{
@@ -5705,13 +5709,15 @@  iv_ca_narrow (struct ivopts_data *data, struct iv_
 	      if (!cp)
 		continue;
 
-	      if (!iv_ca_has_deps (ivs, cp))
-                continue; 
+	      iv_ca_set_cp (data, ivs, use, cp);
+	      acost = iv_ca_cost (ivs);
+	      iv_ca_set_cp (data, ivs, use, old_cp);
 
-	      if (!cheaper_cost_pair (cp, new_cp))
-		continue;
-
-	      new_cp = cp;
+	      if (compare_costs (acost, best_cost) < 0)
+		{
+		  best_cost = acost;
+		  new_cp = cp;
+		}
 	    }
 	}
       else
@@ -5726,13 +5732,16 @@  iv_ca_narrow (struct ivopts_data *data, struct iv_
 	      cp = get_use_iv_cost (data, use, cnd);
 	      if (!cp)
 		continue;
-	      if (!iv_ca_has_deps (ivs, cp))
-		continue;
 
-	      if (!cheaper_cost_pair (cp, new_cp))
-		continue;
+	      iv_ca_set_cp (data, ivs, use, cp);
+	      acost = iv_ca_cost (ivs);
+	      iv_ca_set_cp (data, ivs, use, old_cp);
 
-	      new_cp = cp;
+	      if (compare_costs (acost, best_cost) < 0)
+		{
+		  best_cost = acost;
+		  new_cp = cp;
+		}
 	    }
 	}
 
@@ -5776,7 +5785,7 @@  iv_ca_prune (struct ivopts_data *data, struct iv_c
       if (cand == except_cand)
 	continue;
 
-      acost = iv_ca_narrow (data, ivs, cand, &act_delta);
+      acost = iv_ca_narrow (data, ivs, cand, except_cand, &act_delta);
 
       if (compare_costs (acost, best_cost) < 0)
 	{