[PATCH, PR 40866] decrease the cost of an IV candidate by 1 when the IV is used in a test against zero

[Changpeng Fang <changpeng dot fang at amd dot com>]

Hi,

The patch below fixes PR 40866 : [4.3/4.4/4.5 Regression] No counter 
reversal for simple loops anymore.

Problem:
The loop optimizer canonicalizes the loop to a downward counting loop 
which may save one instruction if
the bound test is against zero. However, ivopts do not know that 
comparing with zero is more efficient
than comparing with any other expressions and thus eliminate the 
reversed IV based on the current cost
model.

Solution:
In this patch, we changed the ivopts cost model to decrease the cost of 
an IV candidate by 1 when the IV is
a test against zero. This idea was initially proposed by Zdenek Dvorak 
as shown in the comment #3 of the bug
report.

Bootstrapped and tested on x86-64-linux. OK for trunk?

Thanks,

Changpeng
>From 8efd640211b2c45bd11a0ad65c6497d6a06556d4 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Tue, 9 Feb 2010 00:20:40 -0600
Subject: [PATCH] Fix PR40886.

2010-02-10  Sebastian Pop  <sebastian.pop@amd.com>
	    Changpeng Fang  <changpeng.fang@amd.com>

	PR middle-end/40886
	* tree-ssa-loop-ivopts.c (determine_use_iv_cost_condition): Decrement
	the cost of an IV candidate when the IV is used in a test against zero.

	* gcc.dg/tree-ssa/ivopts-3.c: New.


---
 gcc/testsuite/gcc.dg/tree-ssa/ivopts-3.c |   12 ++++++++++++
 gcc/tree-ssa-loop-ivopts.c               |   15 ++++++++++++++-
 2 files changed, 26 insertions(+), 1 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ivopts-3.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ivopts-3.c b/gcc/testsuite/gcc.dg/tree-ssa/ivopts-3.c
new file mode 100644
index 0000000..7c4236b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ivopts-3.c
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ivopts-details" } */
+
+void main (void)
+{
+  int i;
+  for (i = 0; i < 10; i++)
+    f2 ();
+}
+
+/* { dg-final { scan-tree-dump-times "!= 0" 4 "ivopts" } }  */
+/* { dg-final { cleanup-tree-dump "ivopts" } }  */
diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index 436e6ce..74dadf7 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -4089,6 +4089,7 @@ determine_use_iv_cost_condition (struct ivopts_data *data,
   bitmap depends_on_elim = NULL, depends_on_express = NULL, depends_on;
   comp_cost elim_cost, express_cost, cost;
   bool ok;
+  tree *control_var, *bound_cst;
 
   /* Only consider real candidates.  */
   if (!cand->iv)
@@ -4110,9 +4111,21 @@ determine_use_iv_cost_condition (struct ivopts_data *data,
 
   /* 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->stmt, NULL, NULL, NULL, &cmp_iv);
+  ok = extract_cond_operands (data, use->stmt, &control_var, &bound_cst,
+			      NULL, &cmp_iv);
   gcc_assert (ok);
 
+  /* When the condition is a comparison of the candidate IV against
+     zero, prefer this IV.
+
+     TODO: The constant that we're substracting from the cost should
+     be target-dependent.  This information should be added to the
+     target costs for each backend.  */
+  if (integer_zerop (*bound_cst)
+      && (operand_equal_p (*control_var, cand->var_after, 0)
+	  || operand_equal_p (*control_var, cand->var_before, 0)))
+    elim_cost.cost -= 1;
+
   express_cost = get_computation_cost (data, use, cand, false,
 				       &depends_on_express, NULL);
   fd_ivopts_data = data;
-- 
1.6.3.3