diff mbox

PR78153

Message ID CAAgBjMn-nb5j+M-32EERZwsjqhVw-S2V_fvyg1k_ryGoPU--PA@mail.gmail.com
State New
Headers show

Commit Message

Prathamesh Kulkarni Nov. 23, 2016, 6:10 p.m. UTC 
On 23 November 2016 at 17:51, Richard Biener <rguenther@suse.de> wrote:
> On Wed, 23 Nov 2016, Prathamesh Kulkarni wrote:

>

>> On 23 November 2016 at 17:21, Richard Biener <rguenther@suse.de> wrote:

>> > On Wed, 23 Nov 2016, Prathamesh Kulkarni wrote:

>> >

>> >> On 23 November 2016 at 15:16, Richard Biener <rguenther@suse.de> wrote:

>> >> > On Tue, 22 Nov 2016, Prathamesh Kulkarni wrote:

>> >> >

>> >> >> On 22 November 2016 at 20:53, Richard Biener <rguenther@suse.de> wrote:

>> >> >> > On Tue, 22 Nov 2016, Prathamesh Kulkarni wrote:

>> >> >> >

>> >> >> >> On 22 November 2016 at 20:18, Richard Biener <rguenther@suse.de> wrote:

>> >> >> >> > On Tue, 22 Nov 2016, Prathamesh Kulkarni wrote:

>> >> >> >> >

>> >> >> >> >> On 21 November 2016 at 15:10, Richard Biener <rguenther@suse.de> wrote:

>> >> >> >> >> > On Sun, 20 Nov 2016, Prathamesh Kulkarni wrote:

>> >> >> >> >> >

>> >> >> >> >> >> Hi,

>> >> >> >> >> >> As suggested by Martin in PR78153 strlen's return value cannot exceed

>> >> >> >> >> >> PTRDIFF_MAX.

>> >> >> >> >> >> So I set it's range to [0, PTRDIFF_MAX - 1] in extract_range_basic()

>> >> >> >> >> >> in the attached patch.

>> >> >> >> >> >>

>> >> >> >> >> >> However it regressed strlenopt-3.c:

>> >> >> >> >> >>

>> >> >> >> >> >> Consider fn1() from strlenopt-3.c:

>> >> >> >> >> >>

>> >> >> >> >> >> __attribute__((noinline, noclone)) size_t

>> >> >> >> >> >> fn1 (char *p, char *q)

>> >> >> >> >> >> {

>> >> >> >> >> >>   size_t s = strlen (q);

>> >> >> >> >> >>   strcpy (p, q);

>> >> >> >> >> >>   return s - strlen (p);

>> >> >> >> >> >> }

>> >> >> >> >> >>

>> >> >> >> >> >> The optimized dump shows the following:

>> >> >> >> >> >>

>> >> >> >> >> >> __attribute__((noclone, noinline))

>> >> >> >> >> >> fn1 (char * p, char * q)

>> >> >> >> >> >> {

>> >> >> >> >> >>   size_t s;

>> >> >> >> >> >>   size_t _7;

>> >> >> >> >> >>   long unsigned int _9;

>> >> >> >> >> >>

>> >> >> >> >> >>   <bb 2>:

>> >> >> >> >> >>   s_4 = strlen (q_3(D));

>> >> >> >> >> >>   _9 = s_4 + 1;

>> >> >> >> >> >>   __builtin_memcpy (p_5(D), q_3(D), _9);

>> >> >> >> >> >>   _7 = 0;

>> >> >> >> >> >>   return _7;

>> >> >> >> >> >>

>> >> >> >> >> >> }

>> >> >> >> >> >>

>> >> >> >> >> >> which introduces the regression, because the test expects "return 0;" in fn1().

>> >> >> >> >> >>

>> >> >> >> >> >> The issue seems to be in vrp2:

>> >> >> >> >> >>

>> >> >> >> >> >> Before the patch:

>> >> >> >> >> >> Visiting statement:

>> >> >> >> >> >> s_4 = strlen (q_3(D));

>> >> >> >> >> >> Found new range for s_4: VARYING

>> >> >> >> >> >>

>> >> >> >> >> >> Visiting statement:

>> >> >> >> >> >> _1 = s_4;

>> >> >> >> >> >> Found new range for _1: [s_4, s_4]

>> >> >> >> >> >> marking stmt to be not simulated again

>> >> >> >> >> >>

>> >> >> >> >> >> Visiting statement:

>> >> >> >> >> >> _7 = s_4 - _1;

>> >> >> >> >> >> Applying pattern match.pd:111, gimple-match.c:27997

>> >> >> >> >> >> Match-and-simplified s_4 - _1 to 0

>> >> >> >> >> >> Intersecting

>> >> >> >> >> >>   [0, 0]

>> >> >> >> >> >> and

>> >> >> >> >> >>   [0, +INF]

>> >> >> >> >> >> to

>> >> >> >> >> >>   [0, 0]

>> >> >> >> >> >> Found new range for _7: [0, 0]

>> >> >> >> >> >>

>> >> >> >> >> >> __attribute__((noclone, noinline))

>> >> >> >> >> >> fn1 (char * p, char * q)

>> >> >> >> >> >> {

>> >> >> >> >> >>   size_t s;

>> >> >> >> >> >>   long unsigned int _1;

>> >> >> >> >> >>   long unsigned int _9;

>> >> >> >> >> >>

>> >> >> >> >> >>   <bb 2>:

>> >> >> >> >> >>   s_4 = strlen (q_3(D));

>> >> >> >> >> >>   _9 = s_4 + 1;

>> >> >> >> >> >>   __builtin_memcpy (p_5(D), q_3(D), _9);

>> >> >> >> >> >>   _1 = s_4;

>> >> >> >> >> >>   return 0;

>> >> >> >> >> >>

>> >> >> >> >> >> }

>> >> >> >> >> >>

>> >> >> >> >> >>

>> >> >> >> >> >> After the patch:

>> >> >> >> >> >> Visiting statement:

>> >> >> >> >> >> s_4 = strlen (q_3(D));

>> >> >> >> >> >> Intersecting

>> >> >> >> >> >>   [0, 9223372036854775806]

>> >> >> >> >> >> and

>> >> >> >> >> >>   [0, 9223372036854775806]

>> >> >> >> >> >> to

>> >> >> >> >> >>   [0, 9223372036854775806]

>> >> >> >> >> >> Found new range for s_4: [0, 9223372036854775806]

>> >> >> >> >> >> marking stmt to be not simulated again

>> >> >> >> >> >>

>> >> >> >> >> >> Visiting statement:

>> >> >> >> >> >> _1 = s_4;

>> >> >> >> >> >> Intersecting

>> >> >> >> >> >>   [0, 9223372036854775806]  EQUIVALENCES: { s_4 } (1 elements)

>> >> >> >> >> >> and

>> >> >> >> >> >>   [0, 9223372036854775806]

>> >> >> >> >> >> to

>> >> >> >> >> >>   [0, 9223372036854775806]  EQUIVALENCES: { s_4 } (1 elements)

>> >> >> >> >> >> Found new range for _1: [0, 9223372036854775806]

>> >> >> >> >> >> marking stmt to be not simulated again

>> >> >> >> >> >>

>> >> >> >> >> >> Visiting statement:

>> >> >> >> >> >> _7 = s_4 - _1;

>> >> >> >> >> >> Intersecting

>> >> >> >> >> >>   ~[9223372036854775807, 9223372036854775809]

>> >> >> >> >> >> and

>> >> >> >> >> >>   ~[9223372036854775807, 9223372036854775809]

>> >> >> >> >> >> to

>> >> >> >> >> >>   ~[9223372036854775807, 9223372036854775809]

>> >> >> >> >> >> Found new range for _7: ~[9223372036854775807, 9223372036854775809]

>> >> >> >> >> >> marking stmt to be not simulated again

>> >> >> >> >> >>

>> >> >> >> >> >> __attribute__((noclone, noinline))

>> >> >> >> >> >> fn1 (char * p, char * q)

>> >> >> >> >> >> {

>> >> >> >> >> >>   size_t s;

>> >> >> >> >> >>   long unsigned int _1;

>> >> >> >> >> >>   size_t _7;

>> >> >> >> >> >>   long unsigned int _9;

>> >> >> >> >> >>

>> >> >> >> >> >>   <bb 2>:

>> >> >> >> >> >>   s_4 = strlen (q_3(D));

>> >> >> >> >> >>   _9 = s_4 + 1;

>> >> >> >> >> >>   __builtin_memcpy (p_5(D), q_3(D), _9);

>> >> >> >> >> >>   _1 = s_4;

>> >> >> >> >> >>   _7 = s_4 - _1;

>> >> >> >> >> >>   return _7;

>> >> >> >> >> >>

>> >> >> >> >> >> }

>> >> >> >> >> >>

>> >> >> >> >> >> Then forwprop4 turns

>> >> >> >> >> >> _1 = s_4

>> >> >> >> >> >> _7 = s_4 - _1

>> >> >> >> >> >> into

>> >> >> >> >> >> _7 = 0

>> >> >> >> >> >>

>> >> >> >> >> >> and we end up with:

>> >> >> >> >> >> _7 = 0

>> >> >> >> >> >> return _7

>> >> >> >> >> >> in optimized dump.

>> >> >> >> >> >>

>> >> >> >> >> >> Running ccp again after forwprop4 trivially solves the issue, however

>> >> >> >> >> >> I am not sure if we want to run ccp again ?

>> >> >> >> >> >>

>> >> >> >> >> >> The issue is probably with extract_range_from_ssa_name():

>> >> >> >> >> >> For _1 = s_4

>> >> >> >> >> >>

>> >> >> >> >> >> Before patch:

>> >> >> >> >> >> VR for s_4 is set to varying.

>> >> >> >> >> >> So VR for _1 is set to [s_4, s_4] by extract_range_from_ssa_name.

>> >> >> >> >> >> Since VR for _1 is [s_4, s_4] it implicitly implies that _1 is equal to s_4,

>> >> >> >> >> >> and vrp is able to transform _7 = s_4 - _1 to _7 = 0 (by using

>> >> >> >> >> >> match.pd pattern x - x -> 0).

>> >> >> >> >> >>

>> >> >> >> >> >> After patch:

>> >> >> >> >> >> VR for s_4 is set to [0, PTRDIFF_MAX - 1]

>> >> >> >> >> >> And correspondingly VR for _1 is set to [0, PTRDIFF_MAX - 1]

>> >> >> >> >> >> so IIUC, we then lose the information that _1 is equal to s_4,

>> >> >> >> >> >

>> >> >> >> >> > We don't lose it, it's in its set of equivalencies.

>> >> >> >> >> Ah, I missed that, thanks. For some reason I had mis-conception that

>> >> >> >> >> equivalences stores

>> >> >> >> >> variables which have same value-ranges but are not necessarily equal.

>> >> >> >> >> >

>> >> >> >> >> >> and vrp doesn't transform _7 = s_4 - _1 to _7 = 0.

>> >> >> >> >> >> forwprop4 does that because it sees that s_4 and _1 are equivalent.

>> >> >> >> >> >> Does this sound correct ?

>> >> >> >> >> >

>> >> >> >> >> > Yes.  So the issue is really that vrp_visit_assignment_or_call calls

>> >> >> >> >> > gimple_fold_stmt_to_constant_1 with vrp_valueize[_1] which when

>> >> >> >> >> > we do not have a singleton VR_RANGE does not fall back to looking

>> >> >> >> >> > at equivalences (there's not a good cheap way to do that currently because

>> >> >> >> >> > VRP doesn't keep a proper copy lattice but simply IORs equivalences

>> >> >> >> >> > from all equivalences).  In theory simply using the first set bit

>> >> >> >> >> > might work.  Thus sth like

>> >> >> >> >> >

>> >> >> >> >> > @@ -7057,6 +7030,12 @@ vrp_valueize (tree name)

>> >> >> >> >> >               || is_gimple_min_invariant (vr->min))

>> >> >> >> >> >           && vrp_operand_equal_p (vr->min, vr->max))

>> >> >> >> >> >         return vr->min;

>> >> >> >> >> > +      else if (vr->equiv && ! bitmap_empty_p (vr->equiv))

>> >> >> >> >> > +       {

>> >> >> >> >> > +         unsigned num = bitmap_first_set_bit (vr->equiv);

>> >> >> >> >> > +         if (num < SSA_NAME_VERSION (name))

>> >> >> >> >> > +           return ssa_name (num);

>> >> >> >> >> > +       }

>> >> >> >> >> >      }

>> >> >> >> >> >    return name;

>> >> >> >> >> >  }

>> >> >> >> >> >

>> >> >> >> >> > might work with the idea of simply doing canonicalization to one of

>> >> >> >> >> > the equivalences.  But as we don't allow copies in the SSA def stmt

>> >> >> >> >> > (via vrp_valueize_1) I'm not sure that's good enough canonicalization.

>> >> >> >> >> IIUC, we record the equivalent variables in vr->equiv

>> >> >> >> >> but do not canonicalize to one of the equivalence like "copy-of value"

>> >> >> >> >> in copyprop ?

>> >> >> >> >> Using first set bit unfortunately doesn't help for the above case.

>> >> >> >> >>

>> >> >> >> >> Sorry if this sounds silly, should we just run copyprop/ccp once again

>> >> >> >> >> after vrp2 to ensure that there are no copies left ?

>> >> >> >> >

>> >> >> >> > why?  forwprop also does copy and constant propagation.  For the

>> >> >> >> > regression simply adjust the pass dump you scan.

>> >> >> >> Well, with the patch the redundant store to and load from _7 still remains

>> >> >> >> in optimized dump for fn1() in strlenopt-3.c:

>> >> >> >>

>> >> >> >> __attribute__((noclone, noinline))

>> >> >> >> fn1 (char * p, char * q)

>> >> >> >> {

>> >> >> >>   size_t s;

>> >> >> >>   size_t _7;

>> >> >> >>   long unsigned int _9;

>> >> >> >>

>> >> >> >>   <bb 2>:

>> >> >> >>   s_4 = strlen (q_3(D));

>> >> >> >>   _9 = s_4 + 1;

>> >> >> >>   __builtin_memcpy (p_5(D), q_3(D), _9);

>> >> >> >>   _7 = 0;

>> >> >> >>   return _7;

>> >> >> >>

>> >> >> >> }

>> >> >> >>

>> >> >> >> Running ccp again after forwprop4 would get rid of _7.

>> >> >> >> Without the patch we have return _0; in optimized dump.

>> >> >> >

>> >> >> > Ah, but then that's a missing "folding" of the return.  It's not

>> >> >> > a load/store anyway.

>> >> >> Hi Richard,

>> >> >> Thanks for the suggestion. In the attached untested patch, I tried to

>> >> >> modify forwprop to fold return-value to constant.

>> >> >> The optimized dump shows return 0; for the above test-case with this patch.

>> >> >> Does it look OK ?

>> >> >

>> >> > No, the fix is to make fold_stmt_1 handle GIMPLE_RETURN and simply

>> >> > valueize the return value (note 'valueize' might return NULL or be NULL).

>> >> >

>> >> Hi Richard,

>> >> Does the attached patch look OK ? I verified it prevents the

>> >> regression for above case.

>> >> Bootstrap+test on x86_64-unknown-linux-gnu in progress.

>> >

>> > +           tree val = valueize (ret);

>> > +           if (val && TREE_CONSTANT (val))

>> > +             {

>> >

>> > ok apart from the TREE_CONSTANT check which should be necessary

>> > (it misses applying copy propagation).

>> Well without TREE_CONSTANT check, it goes into infinite loop for above  test,

>> which would happen if valueize (ret) returns ret

>> Instead of TREE_CONSTANT is the following check OK ?

>> tree val = valueize (ret);

>> if (val && val != ret)

>>   {

>>     gimple_return_set_retval (ret_stmt, val);

>>     changed = true;

>>   }

>

> Yeah, you indeed shall not return true if you changed nothing.

Thanks, I committed the attached patch as r242786 after
bootstrap+test on x86_64-unknown-linux-gnu and
cross-test on arm*-*-*, aarch64*-*-*.

Thanks,
Prathamesh
>

> Richard.

>

>> Thanks,

>> Prathamesh

>> >

>> > Thanks,

>> > Richard.

>> >

>> >> Thanks,

>> >> Prathamesh

>> >> > Richard.

>> >> >

>> >> >>

>> >> >> Thanks,

>> >> >> Prathamesh

>> >> >> >

>> >> >> > Richard.

>> >> >> >

>> >> >> >> Thanks,

>> >> >> >> Prathamesh

>> >> >> >> >

>> >> >> >> >> However that might be quite expensive ?

>> >> >> >> >> Or make vrp track copies like copyprop using a separate copy-of lattice ?

>> >> >> >> >

>> >> >> >> > Ideally we'd unify the three SSA propagation passes into one.  We'd

>> >> >> >> > have to have separate lattices for copy&constant and range&known-bits.

>> >> >> >> >

>> >> >> >> > Richard.

>> >> >> >> >

>> >> >> >> >> Thanks,

>> >> >> >> >> Prathamesh

>> >> >> >> >> >

>> >> >> >> >> > Richard.

>> >> >> >> >>

>> >> >> >> >>

>> >> >> >> >

>> >> >> >> > --

>> >> >> >> > Richard Biener <rguenther@suse.de>

>> >> >> >> > SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

>> >> >> >>

>> >> >> >>

>> >> >> >

>> >> >> > --

>> >> >> > Richard Biener <rguenther@suse.de>

>> >> >> > SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

>> >> >>

>> >> >

>> >> > --

>> >> > Richard Biener <rguenther@suse.de>

>> >> > SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

>> >>

>> >

>> > --

>> > Richard Biener <rguenther@suse.de>

>> > SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

>>

>>

>

> --

> Richard Biener <rguenther@suse.de>

> SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)
2016-11-23  Prathamesh Kulkarni  <prathamesh.kulkarni@linaro.org>

	PR middle-end/78153
	* gimple-fold.c (fold_stmt_1): Handle case for GIMPLE_RETURN.
	* tree-vrp.c (extract_range_basic): Handle case for
	CFN_BUILT_IN_STRLEN.

testsuite/
	* gcc.dg/tree-ssa/pr78153-1.c: New test.
	* gcc.dg/tree-ssa/pr78153-2.c: Likewise.

Comments

Rainer Orth Nov. 23, 2016, 10:14 p.m. UTC | #1 
Hi Prathamesh,

> Thanks, I committed the attached patch as r242786 after

> bootstrap+test on x86_64-unknown-linux-gnu and

> cross-test on arm*-*-*, aarch64*-*-*.


this patch broke Ada bootstrap on Solaris.  I've filed PR middle-end/78501.

	Rainer

-- 
-----------------------------------------------------------------------------
Rainer Orth, Center for Biotechnology, Bielefeld University
diff mbox

Patch

diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
index aabc8ff..6842301 100644
--- a/gcc/gimple-fold.c
+++ b/gcc/gimple-fold.c
@@ -4406,6 +4406,23 @@  fold_stmt_1 (gimple_stmt_iterator *gsi, bool inplace, tree (*valueize) (tree))
 	}
       break;
 
+    case GIMPLE_RETURN:
+      {
+	greturn *ret_stmt = as_a<greturn *> (stmt);
+	tree ret = gimple_return_retval(ret_stmt);
+
+	if (ret && TREE_CODE (ret) == SSA_NAME && valueize)
+	  {
+	    tree val = valueize (ret);
+	    if (val && val != ret)
+	      {
+		gimple_return_set_retval (ret_stmt, val);
+		changed = true;
+	      }
+	  }
+      }
+      break;
+
     default:;
     }
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr78153-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr78153-1.c
new file mode 100644
index 0000000..2530ba0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr78153-1.c
@@ -0,0 +1,10 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp-slim" } */
+
+void f(const char *s)
+{
+  if (__PTRDIFF_MAX__ <= __builtin_strlen (s))
+    __builtin_abort ();
+}
+
+/* { dg-final { scan-tree-dump-not "__builtin_abort" "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr78153-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr78153-2.c
new file mode 100644
index 0000000..de70450
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr78153-2.c
@@ -0,0 +1,11 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp-slim" } */
+
+void f(const char *s)
+{
+  __PTRDIFF_TYPE__ n = __builtin_strlen (s);
+  if (n < 0)
+    __builtin_abort ();
+}
+
+/* { dg-final { scan-tree-dump-not "__builtin_abort" "evrp" } } */
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index c2a4133..373582a 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -4013,6 +4013,16 @@  extract_range_basic (value_range *vr, gimple *stmt)
 			          : vrp_val_max (type), NULL);
 	  }
 	  return;
+	case CFN_BUILT_IN_STRLEN:
+	  {
+	    tree type = TREE_TYPE (gimple_call_lhs (stmt));
+	    tree max = vrp_val_max (ptrdiff_type_node);
+	    wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
+	    tree range_min = build_zero_cst (type); 
+	    tree range_max = wide_int_to_tree (type, wmax - 1);
+	    set_value_range (vr, VR_RANGE, range_min, range_max, NULL);
+	  }
+	  return;
 	default:
 	  break;
 	}