[PATCH] Fold more aggressively for trip counts

[jimbob at google dot com (Robert Kennedy)]

Attached is a patch to do a little bit of extra work in analyzing trip
counts for loops. As a side benefit, some other phases will perhaps
get slightly better folding results.

The motivation for this patch came from some experiments I did with
doing strength reduction and linear function test replacement rather
early in optimization, before, e.g., vectorization. At first, code
introduced by SR caused some failures by keeping loops from being
analyzed well, hence the genesis of this patch.

Bootstrapped and tested on i686-pc-linux-gnu.

	-- Robert Kennedy

		    ------------------------------

2007-01-02  Robert Kennedy <jimbob@google.com>

	* tree-ssa-loop-niter.c (tree_simplify_using_condition_1):
	Simplify using simply related variables, not just identical
	ones.
	* fold-const.c (fold_comparison): Fold comparisons like (x *
	1000 < 0) to (x < 0).
	
==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/fold-const.c#16 - /home/jimbob/clients/jimbob-perforce2-test/gcctools/google_vendor_src_branch/gcc/trunk/gcc/fold-const.c ====
# action=edit type=text
--- gcctools/google_vendor_src_branch/gcc/trunk/gcc/fold-const.c	2006-12-21 16:55:26.000000000 -0800
+++ gcctools/google_vendor_src_branch/gcc/trunk/gcc/fold-const.c	2007-01-02 11:06:35.000000000 -0800
@@ -42,7 +42,7 @@
    force_fit_type takes a constant, an overflowable flag and prior
    overflow indicators.  It forces the value to fit the type and sets
    TREE_OVERFLOW and TREE_CONSTANT_OVERFLOW as appropriate.
-   
+
    Note: Since the folders get called on non-gimple code as well as
    gimple code, we need to handle GIMPLE tuples as well as their
    corresponding tree equivalents.  */
@@ -8065,6 +8065,29 @@
 			    variable2);
     }
 
+  /* Transform comparisons of the form X * C1 CMP 0 to X CMP 0 in the
+     signed arithmetic case.  That form is created by the compiler
+     often enough for folding it to be of value. One example is in
+     computing loop trip counts after Operator Strength Reduction.  */
+  if (!(flag_wrapv || flag_trapv)
+      && !TYPE_UNSIGNED (TREE_TYPE (arg0))
+      && TREE_CODE (arg0) == MULT_EXPR
+      && (TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
+          && !TREE_OVERFLOW (TREE_OPERAND (arg0, 1)))
+      && integer_zerop (arg1))
+    {
+      tree const1 = TREE_OPERAND (arg0, 1);
+      tree const2 = arg1;                       /* zero */
+      tree variable1 = TREE_OPERAND (arg0, 0);
+      enum tree_code cmp_code = code;
+
+      /* If const1 is negative we swap the sense of the comparison.  */
+      if (tree_int_cst_sgn (const1) < 0)
+        cmp_code = swap_tree_comparison (cmp_code);
+
+      return fold_build2 (cmp_code, type, variable1, const2);
+    }
+
   tem = maybe_canonicalize_comparison (code, type, arg0, arg1);
   if (tem)
     return tem;
==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-loop-niter.c#10 - /home/jimbob/clients/jimbob-perforce2-test/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-loop-niter.c ====
# action=edit type=text
--- gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-loop-niter.c	2006-12-29 11:18:58.000000000 -0800
+++ gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-loop-niter.c	2007-01-02 11:11:41.000000000 -0800
@@ -837,6 +837,55 @@
   if (e && integer_zerop (e))
     return e;
 
+  /* Try something a little aggressive: If te is easily expressible in
+     terms of a variable in cond (resp. notcond), we can give a
+     stronger answer.  Get the definitions of te's variable(s) and try
+     checks based on equivalent (or weaker) conditions in terms of
+     them. The original motivation was to keep Operator Strength
+     Reduction from hurting subsequent loop optimizations by making
+     trip counts harder to compute.
+
+     TODO: Consider iterating here through copies instead of checking
+     just one level up.  */
+
+  if (COMPARISON_CLASS_P (te))
+    {
+      tree def0;
+      tree def1;
+
+      def0 = e0 = TREE_OPERAND (te, 0);
+      def1 = e1 = TREE_OPERAND (te, 1);
+
+      /* Did somebody make sure te is canonicalized somehow? What are the
+         rules for its canonicalization? */
+      if (TREE_CODE (e0) == SSA_NAME)
+        {
+          tree def = SSA_NAME_DEF_STMT (e0);
+          if (TREE_CODE (def) == GIMPLE_MODIFY_STMT)
+            def0 = GIMPLE_STMT_OPERAND (def, 1);
+        }
+      if (TREE_CODE (e1) == SSA_NAME)
+        {
+          tree def = SSA_NAME_DEF_STMT (e1);
+          if (TREE_CODE (def) == GIMPLE_MODIFY_STMT)
+            def1 = GIMPLE_STMT_OPERAND (def, 1);
+        }
+
+      if (def0 != e0
+          || def1 != e1)
+        te = fold_build2 (TREE_CODE (te), boolean_type_node, def0, def1);
+
+      /* Check whether COND ==> EXPR.  */
+      e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
+      if (e && integer_nonzerop (e))
+        return e;
+
+      /* Check whether COND ==> not EXPR.  */
+      e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
+      if (e && integer_zerop (e))
+        return e;
+    }
+
   return expr;
 }