On Tue, 18 Jan 2022, Richard Biener wrote:
> On Mon, 17 Jan 2022, Jiufu Guo wrote:
>
> > Richard Biener <rguent...@suse.de> writes:
> >
> > > On Fri, 14 Jan 2022, Jiufu Guo wrote:
> > >
> > >> Richard Biener <rguent...@suse.de> writes:
> > >>
> > >> > On Thu, 13 Jan 2022, guojiufu wrote:
> > >> >
> > >> >> On 2022-01-03 22:30, Richard Biener wrote:
> > >> >> > On Wed, 22 Dec 2021, Jiufu Guo wrote:
> > >> >> >
> > >> >> >> Hi,
> > >> >> >> ...
> > >> >> >>
> > >> >> >> Bootstrap and regtest pass on ppc64* and x86_64. Is this ok for
> > >> >> >> trunk?
> > >> >> >
> > may means infer_loop_bounds_from_undefined may not useful
> > before IV's scev is ready.
>
> I think it's also SCEV does not get optimal results without
> niter estimates (or rather filled control IVs).
>
> > > override the global caching of analyze_scalar_evolution the per
> > > SSA name cache for SCEV analysis isn't overridden. That also means
> > > computing the estimates early will break your patch (I've
> > > tested calling estimate_numbers_of_iterations explicitely from
> > > loop distribution for example).
> > Calling simple_iv_with_niters/simple_iv early may break the patch,
> > because only inside number_of_iterations_exit_assumptions, the flag
> > is disabled.
> >
> > >
> > > What I'm trying to see is whether we can do some more concious
> > > setup of control IV computation and estimate computation. While
> > > your patch produces the desired result it is far from obvious
> > > why exactly it does this since it also does it in a "midlevel"
> > > place (of course my attempts to do it in a more obvious position
> > > failed).
> > >
> > > But first of all yes, we should disallow / early out on recursions
> > > via public APIs like estimate_numbers_of_iterations (already done)
> > > or number_of_latch_executions (missing) or
> > > number_of_iterations_exit[_assumptions] (very difficult there).
> >
> > I'm wondering if we can set loop->nb_iterations=chrec_dont_know
> > or chrec_known in number_of_iterations_exit_assumption at the
> > begining, and use it as a guard to avoid recursions on them.
>
> Yes, I tried that but in number_of_latch_executions which is the
> one eventually setting loop->nb_iterations. It's more difficult
> to avoid recursing in number_of_iterations_exit, but in theory
> we could add a niter specific edge flag like EDGE_NITER_IN_PROGRESS
> we could set.
>
> > >
> > > IMHO that we lazily compute estimate_numbers_of_iterations and that
> > > computes niter for each exit of a loop is a misdesign - the estimate
> > > should be computed from the toplevel, and maybe independently for
> > > each exit? I think that Honza changed it this way to make sure the
> > > estimates are always available when queried but I may mis-remember.
> > >
> > > With your patch, ontop of that limiting recursion of
> > > number_of_latch_executions doesn't break the positive effect
> > > at least.
> > >
> > > One unwanted side-effect of your patch might be that the
> > > computed estimate is now recorded w/o infer_loop_bounds_from_undefined
> > > which means it could be worse (and we won't re-compute it).
> > Yes, estimate was computed but infer_loop_bounds_from_undefined was
> > not called, and it will never be called before estimate is reset.
> >
> > >
> > > All in all it is somewhat of a mess and I'm not convinced your
> > > patch is an improvement in this regard :/ It looks like there's
> > > a chicken and egg problem with using and recording (at least one)
> > > control IV and SCEV caching whilst searching for one.
> >
> > Thanks for your comments, and welcome any sugguestions!
>
> To address the missed optimization in the testcase I think we need
> a way to roll back parts of SCEV caching so that
> estimate_numbers_of_iterations can wipe all caching it caused
> (and only that) after it is done. To then get the maximal positive
> effect we would also need to ensure that whenever we "visit" a loop
> with SCEV we "first" do estimate_numbers_of_iterations (that's the
> more difficult part I think, but maybe the less important one).
>
> The first part involves the 'scalar_evolution_info' cache where
> a solution would for example involve chaining the entries with
> a 'next' pointer and keeping track of the last added entry so
> estimate_numbers_of_iterations can remember the last added entry
> at start and remove those added. So maybe add scev_{push,pop}_htab
> functions (not sure if 'push' is a good name, the present entries
> will still be used just after 'pop' all entries added between the
> last push and the pop will be removed).
>
> Doing that in estimate_numbers_of_iterations will cause some
> extra work - maybe the function can pop() already after all
> control IVs are recorded, so the infer_loop_bounds_from_undefined
> work isn't wasted.
>
> All of this is IMHO stage1 stuff now but would be really useful
> to have. Which is why I'm adding a note to my very large
> RIRO (random-in-random-out ;)) TODO list - feel free to beat me
> on it!
Btw, in the least efficient way the effect can be simulated by
calling scev_reset_htab from estimate_numbers_of_iterations.
Richard.
