Fwd: [PATCH 1/3]Improve induction variable elimination

["Bin.Cheng" <amker.cheng@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1525 bytes --]

Hi, forward to Zdenek for the review.

Thanks,
bin


---------- Forwarded message ----------
From: Bin Cheng <bin.cheng@arm.com>
Date: Thu, Jul 17, 2014 at 10:07 AM
Subject: [PATCH 1/3]Improve induction variable elimination
To: gcc-patches@gcc.gnu.org


Hi,
This is a series of three patches improving induction variable elimination.
Currently GCC only eliminates iv for very specific case when the loop's
latch could run zero times, i.e., when may_be_zero field of loop niter
information evaluates to true.  In fact, it's so specific that
iv_elimination_compare_lt rarely succeeds during either GCC bootstrap or
spec2000/spec2006 compilation.  Though intrusive data shows these patches
don't help iv elimination that much for GCC bootstrap, they do capture
5%~15% more eliminations for compiling spec2000/2006.  Detailed numbers are
like:
                  2k/int       2k/fp       2k6/int       2k6/fp
improve ~9.6%      ~4.8%      ~5.5%        ~14.4%

All patches pass bootstrap and regression test on x86_64/x86.  I will
bootstrap and test them on aarch64/arm platforms too.

The first patch turns to tree operand_equal_p to check the number of
iterations in iv_elimination_lt.  Though I think this change isn't necessary
for current code, it's needed if we further relax iv elimination for cases
in which sign/unsigned conversion is involved.

Thanks,
bin

2014-07-17  Bin Cheng  <bin.cheng@arm.com>

        * tree-ssa-loop-ivopts.c (iv_elimination_compare_lt): Check number
        of iteration using tree comparison.

[-- Attachment #2: iv_elimination-improve-a-20140716.txt --]
[-- Type: text/plain, Size: 1757 bytes --]

Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c	(revision 212387)
+++ gcc/tree-ssa-loop-ivopts.c	(working copy)
@@ -4605,7 +4605,7 @@ iv_elimination_compare_lt (struct ivopts_data *dat
 			   struct tree_niter_desc *niter)
 {
   tree cand_type, a, b, mbz, nit_type = TREE_TYPE (niter->niter), offset;
-  struct aff_tree nit, tmpa, tmpb;
+  struct aff_tree nit, tmp1, tmpa, tmpb;
   enum tree_code comp;
   HOST_WIDE_INT step;
 
@@ -4661,15 +4661,19 @@ iv_elimination_compare_lt (struct ivopts_data *dat
     return false;
 
   /* Expected number of iterations is B - A - 1.  Check that it matches
-     the actual number, i.e., that B - A - NITER = 1.  */
+     the actual number, i.e., that B - A = NITER + 1.  */
   tree_to_aff_combination (niter->niter, nit_type, &nit);
-  tree_to_aff_combination (fold_convert (nit_type, a), nit_type, &tmpa);
-  tree_to_aff_combination (fold_convert (nit_type, b), nit_type, &tmpb);
-  aff_combination_scale (&nit, -1);
-  aff_combination_scale (&tmpa, -1);
-  aff_combination_add (&tmpb, &tmpa);
-  aff_combination_add (&tmpb, &nit);
-  if (tmpb.n != 0 || tmpb.offset != 1)
+  aff_combination_const (&tmp1, nit_type, 1);
+  tree_to_aff_combination (b, TREE_TYPE (b), &tmpb);
+  aff_combination_add (&nit, &tmp1);
+  if (a != integer_zero_node)
+    {
+      tree_to_aff_combination (a, TREE_TYPE (b), &tmpa);
+      aff_combination_scale (&tmpa, -1);
+      aff_combination_add (&tmpb, &tmpa);
+    }
+  if (!operand_equal_p (aff_combination_to_tree (&nit),
+			aff_combination_to_tree (&tmpb), 0))
     return false;
 
   /* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not