On Tue, 22 Nov 2016, Prathamesh Kulkarni wrote:
> On 22 November 2016 at 20:18, Richard Biener <rguent...@suse.de> wrote:
> > On Tue, 22 Nov 2016, Prathamesh Kulkarni wrote:
> >
> >> On 21 November 2016 at 15:10, Richard Biener <rguent...@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.
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 <rguent...@suse.de>
> > SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB
> > 21284 (AG Nuernberg)
>
>
--
Richard Biener <rguent...@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB
21284 (AG Nuernberg)
