Re: [PATCH PR97627]Avoid computing niters info for fake edges
On Fri, Jan 29, 2021 at 10:41 AM Bin.Cheng wrote: > > On Fri, Jan 29, 2021 at 3:55 PM Richard Biener > wrote: > > > > On Thu, Jan 28, 2021 at 11:31 AM Bin.Cheng wrote: > > > > > > On Thu, Jan 28, 2021 at 5:08 PM Richard Biener via Gcc-patches > > > wrote: > > > > > > > > On Thu, Jan 28, 2021 at 3:49 AM bin.cheng via Gcc-patches > > > > wrote: > > > > > > > > > > Hi, > > > > > As described in commit message, we need to avoid computing niters > > > > > info for fake > > > > > edges. This simple patch does this by two changes. > > > > > > > > > > Bootstrap and test on X86_64, is it ok? > > > > > > > > Hmm, so I think the patch is a bit complicated and avoiding niter > > > > compute > > > > for fake edges would be easier when just returning false for > > > > fake edges in number_of_iterations_exit_assumptions? > > > I just grepped calls to get_loop_exit_edges, and thought there might > > > be cases other than niters analysis that would also like to skip fake > > > edges. But I didn't check the calls one by one. > > > > My hunch is that the usual APIs always want to ignore them, but let's > > do a minimal fix that we can backport easily. > Yeah, please apply the trivial patch. OK, will do. Thanks, Richard. > Thanks, > bin > > > > > > > > > > Which pass was the problematical that had infinite loops connected to > > > > exit? > > > > > > > > I guess the cfgloop code should simply ignore fake exits - they mostly > > > > exist to make reverse CFG walks easy. Specifically single_exit > > > > and single_likely_exit but also exit edge recording should ignore them. > > > > > > > > That said, the testcase seems to be fixed with just > > > > > > > > diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c > > > > index 7d61ef080eb..7775bc7275c 100644 > > > > --- a/gcc/tree-ssa-loop-niter.c > > > > +++ b/gcc/tree-ssa-loop-niter.c > > > > @@ -2407,6 +2407,11 @@ number_of_iterations_exit_assumptions (class > > > > loop *loop, edge exit, > > > >affine_iv iv0, iv1; > > > >bool safe; > > > > > > > > + /* The condition at a fake exit (if it exists) does not control its > > > > + execution. */ > > > > + if (exit->flags & EDGE_FAKE) > > > > +return false; > > > > + > > > >/* Nothing to analyze if the loop is known to be infinite. */ > > > >if (loop_constraint_set_p (loop, LOOP_C_INFINITE)) > > > > return false; > > > > > > > > Your dfs_find_deadend change likely "breaks" post-dominance DFS order > > > > (this is a very fragile area). > > > > > > > > So any objection to just simplify the patch to the above hunk? > > > Considering we are in late stage3? No objection to this change. But I > > > do think dfs_find_deadend needs to be improved, if not as this patch > > > does. For a loop nest with the outermost loop as the infinite one, > > > the function adds fake (exit) edges for inner loops, which is > > > counter-intuitive. > > > > Sure, but then this is independent of the PR. As said, the fake exits > > only exist to make reverse CFG walkers easier - yes, for natural > > infinite loops we'd like to have "intuitive" post-dom behavior but for > > example for irreducible regions there's not much to do. > > > > Richard. > > > > > Thanks, > > > bin > > > > > > > > Thanks, > > > > Richard. > > > > > > > > > Thanks, > > > > > bin
Re: [PATCH PR97627]Avoid computing niters info for fake edges
On Fri, Jan 29, 2021 at 3:55 PM Richard Biener wrote: > > On Thu, Jan 28, 2021 at 11:31 AM Bin.Cheng wrote: > > > > On Thu, Jan 28, 2021 at 5:08 PM Richard Biener via Gcc-patches > > wrote: > > > > > > On Thu, Jan 28, 2021 at 3:49 AM bin.cheng via Gcc-patches > > > wrote: > > > > > > > > Hi, > > > > As described in commit message, we need to avoid computing niters info > > > > for fake > > > > edges. This simple patch does this by two changes. > > > > > > > > Bootstrap and test on X86_64, is it ok? > > > > > > Hmm, so I think the patch is a bit complicated and avoiding niter compute > > > for fake edges would be easier when just returning false for > > > fake edges in number_of_iterations_exit_assumptions? > > I just grepped calls to get_loop_exit_edges, and thought there might > > be cases other than niters analysis that would also like to skip fake > > edges. But I didn't check the calls one by one. > > My hunch is that the usual APIs always want to ignore them, but let's > do a minimal fix that we can backport easily. Yeah, please apply the trivial patch. Thanks, bin > > > > > > > Which pass was the problematical that had infinite loops connected to > > > exit? > > > > > > I guess the cfgloop code should simply ignore fake exits - they mostly > > > exist to make reverse CFG walks easy. Specifically single_exit > > > and single_likely_exit but also exit edge recording should ignore them. > > > > > > That said, the testcase seems to be fixed with just > > > > > > diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c > > > index 7d61ef080eb..7775bc7275c 100644 > > > --- a/gcc/tree-ssa-loop-niter.c > > > +++ b/gcc/tree-ssa-loop-niter.c > > > @@ -2407,6 +2407,11 @@ number_of_iterations_exit_assumptions (class > > > loop *loop, edge exit, > > >affine_iv iv0, iv1; > > >bool safe; > > > > > > + /* The condition at a fake exit (if it exists) does not control its > > > + execution. */ > > > + if (exit->flags & EDGE_FAKE) > > > +return false; > > > + > > >/* Nothing to analyze if the loop is known to be infinite. */ > > >if (loop_constraint_set_p (loop, LOOP_C_INFINITE)) > > > return false; > > > > > > Your dfs_find_deadend change likely "breaks" post-dominance DFS order > > > (this is a very fragile area). > > > > > > So any objection to just simplify the patch to the above hunk? > > Considering we are in late stage3? No objection to this change. But I > > do think dfs_find_deadend needs to be improved, if not as this patch > > does. For a loop nest with the outermost loop as the infinite one, > > the function adds fake (exit) edges for inner loops, which is > > counter-intuitive. > > Sure, but then this is independent of the PR. As said, the fake exits > only exist to make reverse CFG walkers easier - yes, for natural > infinite loops we'd like to have "intuitive" post-dom behavior but for > example for irreducible regions there's not much to do. > > Richard. > > > Thanks, > > bin > > > > > > Thanks, > > > Richard. > > > > > > > Thanks, > > > > bin
Re: [PATCH PR97627]Avoid computing niters info for fake edges
On Thu, Jan 28, 2021 at 11:31 AM Bin.Cheng wrote: > > On Thu, Jan 28, 2021 at 5:08 PM Richard Biener via Gcc-patches > wrote: > > > > On Thu, Jan 28, 2021 at 3:49 AM bin.cheng via Gcc-patches > > wrote: > > > > > > Hi, > > > As described in commit message, we need to avoid computing niters info > > > for fake > > > edges. This simple patch does this by two changes. > > > > > > Bootstrap and test on X86_64, is it ok? > > > > Hmm, so I think the patch is a bit complicated and avoiding niter compute > > for fake edges would be easier when just returning false for > > fake edges in number_of_iterations_exit_assumptions? > I just grepped calls to get_loop_exit_edges, and thought there might > be cases other than niters analysis that would also like to skip fake > edges. But I didn't check the calls one by one. My hunch is that the usual APIs always want to ignore them, but let's do a minimal fix that we can backport easily. > > > > Which pass was the problematical that had infinite loops connected to exit? > > > > I guess the cfgloop code should simply ignore fake exits - they mostly > > exist to make reverse CFG walks easy. Specifically single_exit > > and single_likely_exit but also exit edge recording should ignore them. > > > > That said, the testcase seems to be fixed with just > > > > diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c > > index 7d61ef080eb..7775bc7275c 100644 > > --- a/gcc/tree-ssa-loop-niter.c > > +++ b/gcc/tree-ssa-loop-niter.c > > @@ -2407,6 +2407,11 @@ number_of_iterations_exit_assumptions (class > > loop *loop, edge exit, > >affine_iv iv0, iv1; > >bool safe; > > > > + /* The condition at a fake exit (if it exists) does not control its > > + execution. */ > > + if (exit->flags & EDGE_FAKE) > > +return false; > > + > >/* Nothing to analyze if the loop is known to be infinite. */ > >if (loop_constraint_set_p (loop, LOOP_C_INFINITE)) > > return false; > > > > Your dfs_find_deadend change likely "breaks" post-dominance DFS order > > (this is a very fragile area). > > > > So any objection to just simplify the patch to the above hunk? > Considering we are in late stage3? No objection to this change. But I > do think dfs_find_deadend needs to be improved, if not as this patch > does. For a loop nest with the outermost loop as the infinite one, > the function adds fake (exit) edges for inner loops, which is > counter-intuitive. Sure, but then this is independent of the PR. As said, the fake exits only exist to make reverse CFG walkers easier - yes, for natural infinite loops we'd like to have "intuitive" post-dom behavior but for example for irreducible regions there's not much to do. Richard. > Thanks, > bin > > > > Thanks, > > Richard. > > > > > Thanks, > > > bin
Re: [PATCH PR97627]Avoid computing niters info for fake edges
On Thu, Jan 28, 2021 at 5:08 PM Richard Biener via Gcc-patches wrote: > > On Thu, Jan 28, 2021 at 3:49 AM bin.cheng via Gcc-patches > wrote: > > > > Hi, > > As described in commit message, we need to avoid computing niters info for > > fake > > edges. This simple patch does this by two changes. > > > > Bootstrap and test on X86_64, is it ok? > > Hmm, so I think the patch is a bit complicated and avoiding niter compute > for fake edges would be easier when just returning false for > fake edges in number_of_iterations_exit_assumptions? I just grepped calls to get_loop_exit_edges, and thought there might be cases other than niters analysis that would also like to skip fake edges. But I didn't check the calls one by one. > > Which pass was the problematical that had infinite loops connected to exit? > > I guess the cfgloop code should simply ignore fake exits - they mostly > exist to make reverse CFG walks easy. Specifically single_exit > and single_likely_exit but also exit edge recording should ignore them. > > That said, the testcase seems to be fixed with just > > diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c > index 7d61ef080eb..7775bc7275c 100644 > --- a/gcc/tree-ssa-loop-niter.c > +++ b/gcc/tree-ssa-loop-niter.c > @@ -2407,6 +2407,11 @@ number_of_iterations_exit_assumptions (class > loop *loop, edge exit, >affine_iv iv0, iv1; >bool safe; > > + /* The condition at a fake exit (if it exists) does not control its > + execution. */ > + if (exit->flags & EDGE_FAKE) > +return false; > + >/* Nothing to analyze if the loop is known to be infinite. */ >if (loop_constraint_set_p (loop, LOOP_C_INFINITE)) > return false; > > Your dfs_find_deadend change likely "breaks" post-dominance DFS order > (this is a very fragile area). > > So any objection to just simplify the patch to the above hunk? Considering we are in late stage3? No objection to this change. But I do think dfs_find_deadend needs to be improved, if not as this patch does. For a loop nest with the outermost loop as the infinite one, the function adds fake (exit) edges for inner loops, which is counter-intuitive. Thanks, bin > > Thanks, > Richard. > > > Thanks, > > bin
Re: [PATCH PR97627]Avoid computing niters info for fake edges
On Thu, Jan 28, 2021 at 3:49 AM bin.cheng via Gcc-patches wrote: > > Hi, > As described in commit message, we need to avoid computing niters info for > fake > edges. This simple patch does this by two changes. > > Bootstrap and test on X86_64, is it ok? Hmm, so I think the patch is a bit complicated and avoiding niter compute for fake edges would be easier when just returning false for fake edges in number_of_iterations_exit_assumptions? Which pass was the problematical that had infinite loops connected to exit? I guess the cfgloop code should simply ignore fake exits - they mostly exist to make reverse CFG walks easy. Specifically single_exit and single_likely_exit but also exit edge recording should ignore them. That said, the testcase seems to be fixed with just diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 7d61ef080eb..7775bc7275c 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -2407,6 +2407,11 @@ number_of_iterations_exit_assumptions (class loop *loop, edge exit, affine_iv iv0, iv1; bool safe; + /* The condition at a fake exit (if it exists) does not control its + execution. */ + if (exit->flags & EDGE_FAKE) +return false; + /* Nothing to analyze if the loop is known to be infinite. */ if (loop_constraint_set_p (loop, LOOP_C_INFINITE)) return false; Your dfs_find_deadend change likely "breaks" post-dominance DFS order (this is a very fragile area). So any objection to just simplify the patch to the above hunk? Thanks, Richard. > Thanks, > bin