On Wed, Nov 06, 2013 at 03:21:04PM -0700, Jeff Law wrote:
> >2013-11-06 Jakub Jelinek <ja...@redhat.com>
> >
> > * tree-ssa-loop-niter.c: Include tree-ssanames.h.
> > (determine_value_range): Add loop argument. Use get_range_info to
> > improve range.
> > (bound_difference): Adjust caller.
> Clever, using the range from the PHI in the loop header. While it
> may be too wide, it's likely going to be a lot better than nothing.
>
> Add a testcase and this is OK.
Ok, thanks, here is what I've committed after another bootstrap/regtest.
2013-11-07 Jakub Jelinek <ja...@redhat.com>
* tree-ssa-loop-niter.c: Include tree-ssanames.h.
(determine_value_range): Add loop argument. Use get_range_info to
improve range.
(bound_difference): Adjust caller.
* gcc.dg/tree-ssa/loop-39.c: New test.
--- gcc/tree-ssa-loop-niter.c.jj 2013-10-24 10:19:21.000000000 +0200
+++ gcc/tree-ssa-loop-niter.c 2013-11-07 11:49:37.568083138 +0100
@@ -45,6 +45,7 @@ along with GCC; see the file COPYING3.
#include "diagnostic-core.h"
#include "tree-inline.h"
#include "tree-pass.h"
+#include "tree-ssanames.h"
#define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
@@ -119,9 +120,12 @@ split_to_var_and_offset (tree expr, tree
in TYPE to MIN and MAX. */
static void
-determine_value_range (tree type, tree var, mpz_t off,
+determine_value_range (struct loop *loop, tree type, tree var, mpz_t off,
mpz_t min, mpz_t max)
{
+ double_int minv, maxv;
+ enum value_range_type rtype = VR_VARYING;
+
/* If the expression is a constant, we know its value exactly. */
if (integer_zerop (var))
{
@@ -130,9 +134,73 @@ determine_value_range (tree type, tree v
return;
}
+ get_type_static_bounds (type, min, max);
+
+ /* See if we have some range info from VRP. */
+ if (TREE_CODE (var) == SSA_NAME && INTEGRAL_TYPE_P (type))
+ {
+ edge e = loop_preheader_edge (loop);
+ gimple_stmt_iterator gsi;
+
+ /* Either for VAR itself... */
+ rtype = get_range_info (var, &minv, &maxv);
+ /* Or for PHI results in loop->header where VAR is used as
+ PHI argument from the loop preheader edge. */
+ for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next
(&gsi))
+ {
+ gimple phi = gsi_stmt (gsi);
+ double_int minc, maxc;
+ if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var
+ && (get_range_info (gimple_phi_result (phi), &minc, &maxc)
+ == VR_RANGE))
+ {
+ if (rtype != VR_RANGE)
+ {
+ rtype = VR_RANGE;
+ minv = minc;
+ maxv = maxc;
+ }
+ else
+ {
+ minv = minv.max (minc, TYPE_UNSIGNED (type));
+ maxv = maxv.min (maxc, TYPE_UNSIGNED (type));
+ gcc_assert (minv.cmp (maxv, TYPE_UNSIGNED (type)) <= 0);
+ }
+ }
+ }
+ if (rtype == VR_RANGE)
+ {
+ mpz_t minm, maxm;
+ gcc_assert (minv.cmp (maxv, TYPE_UNSIGNED (type)) <= 0);
+ mpz_init (minm);
+ mpz_init (maxm);
+ mpz_set_double_int (minm, minv, TYPE_UNSIGNED (type));
+ mpz_set_double_int (maxm, maxv, TYPE_UNSIGNED (type));
+ mpz_add (minm, minm, off);
+ mpz_add (maxm, maxm, off);
+ /* If the computation may not wrap or off is zero, then this
+ is always fine. If off is negative and minv + off isn't
+ smaller than type's minimum, or off is positive and
+ maxv + off isn't bigger than type's maximum, use the more
+ precise range too. */
+ if (nowrap_type_p (type)
+ || mpz_sgn (off) == 0
+ || (mpz_sgn (off) < 0 && mpz_cmp (minm, min) >= 0)
+ || (mpz_sgn (off) > 0 && mpz_cmp (maxm, max) <= 0))
+ {
+ mpz_set (min, minm);
+ mpz_set (max, maxm);
+ mpz_clear (minm);
+ mpz_clear (maxm);
+ return;
+ }
+ mpz_clear (minm);
+ mpz_clear (maxm);
+ }
+ }
+
/* If the computation may wrap, we know nothing about the value, except for
the range of the type. */
- get_type_static_bounds (type, min, max);
if (!nowrap_type_p (type))
return;
@@ -405,8 +473,8 @@ bound_difference (struct loop *loop, tre
mpz_init (maxx);
mpz_init (miny);
mpz_init (maxy);
- determine_value_range (type, varx, offx, minx, maxx);
- determine_value_range (type, vary, offy, miny, maxy);
+ determine_value_range (loop, type, varx, offx, minx, maxx);
+ determine_value_range (loop, type, vary, offy, miny, maxy);
mpz_sub (bnds->below, minx, maxy);
mpz_sub (bnds->up, maxx, miny);
--- gcc/testsuite/gcc.dg/tree-ssa/loop-39.c.jj 2013-11-07 11:52:01.871309995
+0100
+++ gcc/testsuite/gcc.dg/tree-ssa/loop-39.c 2013-11-07 11:54:30.549496152
+0100
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sccp-details" } */
+
+int
+foo (unsigned int n)
+{
+ int i, r = 1;
+ if (n > 0)
+ {
+ asm ("");
+ if (n < 10)
+ {
+ asm ("");
+ do
+ {
+ --n;
+ r *= 2;
+ }
+ while (n > 0);
+ }
+ }
+ return r + n;
+}
+
+/* { dg-final { scan-tree-dump "# of iterations \[^\n\r]*, bounded by 8"
"sccp" } } */
+/* { dg-final { cleanup-tree-dump "sccp" } } */
Jakub
