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.
> 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)
