Re: [PATCH] Allow loop header copying when first iteration condition is known.

[Aldy Hernandez <aldyh@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 3172 bytes --]

On Thu, Nov 11, 2021 at 8:30 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Wed, Nov 10, 2021 at 9:42 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
> >
> >
> >
> > On 11/10/2021 11:20 AM, Aldy Hernandez via Gcc-patches wrote:
> > > As discussed in the PR, the loop header copying pass avoids doing so
> > > when optimizing for size.  However, sometimes we can determine the
> > > loop entry conditional statically for the first iteration of the loop.
> > >
> > > This patch uses the path solver to determine the outgoing edge
> > > out of preheader->header->xx.  If so, it allows header copying.  Doing
> > > this in the loop optimizer saves us from doing gymnastics in the
> > > threader which doesn't have the context to determine if a loop
> > > transformation is profitable.
> > >
> > > I am only returning true in entry_loop_condition_is_static for
> > > a true conditional.  Technically a false conditional is also
> > > provably static, but allowing any boolean value causes a regression
> > > in gfortran.dg/vector_subscript_1.f90.
> > >
> > > I would have preferred not passing around the query object, but the
> > > layout of pass_ch and should_duplicate_loop_header_p make it a bit
> > > awkward to get it right without an outright refactor to the
> > > pass.
> > >
> > > Tested on x86-64 Linux.
> > >
> > > OK?
> > >
> > > gcc/ChangeLog:
> > >
> > >       PR tree-optimization/102906
> > >       * tree-ssa-loop-ch.c (entry_loop_condition_is_static): New.
> > >       (should_duplicate_loop_header_p): Call entry_loop_condition_is_static.
> > >       (class ch_base): Add m_ranger and m_query.
> > >       (ch_base::copy_headers): Pass m_query to
> > >       entry_loop_condition_is_static.
> > >       (pass_ch::execute): Allocate and deallocate m_ranger and
> > >       m_query.
> > >       (pass_ch_vect::execute): Same.
> > >
> > > gcc/testsuite/ChangeLog:
> > >
> > >       * gcc.dg/tree-ssa/pr102906.c: New test.
> > OK.  It also makes a nice little example of how to use a Ranger within
> > an existing pass.
>
> Note if you just test for the condition to be true it will only catch 50%
> of the desired cases since we have no idea whether the 'true' edge
> is the edge existing the loop or the edge remaining in the loop.
> For loop header copying we like to resolve statically to the edge
> remaining in the loop, so you want

Ahh, I figured there was some block shuffling needed.

I was cautious not to touch much because of the
gfortran.dg/vector_subscript_1.f90 regression, but now I see that the
test fails for all optimization levels except -Os.  With this fix we
properly fail for all levels.  I assume this is expected ;-).

>
> extract_true_false_edges_from_block (gimple_bb (last), &true_e, &false_e);
>
> /* If neither edge is the exit edge this is not a case we'd like to
>    special-case.  */
> if (!loop_exit_edge_p (l, true_e) && !loop_exit_edge_p (l, false_e))
>  return false;
>
> tree desired_static_value;
> if (loop_exit_edge_p (l, true_e))
>  desired_static_value = boolean_false_node;
> else
>   desired_static_value = boolean_true_node;
>
> and test for desired_static_value.

Thanks for the code!

OK pending tests?

[-- Attachment #2: 0001-Resolve-entry-loop-condition-for-the-edge-remaining-.patch --]
[-- Type: text/x-patch, Size: 1835 bytes --]

From 9609cff278d3ddea9f74b805b395d5c0293a126c Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Thu, 11 Nov 2021 11:27:07 +0100
Subject: [PATCH] Resolve entry loop condition for the edge remaining in the
 loop.

There is a known failure for gfortran.dg/vector_subscript_1.f90.  It
was previously failing for all optimization levels except -Os.
Getting the loop header copying right, now makes it fail for all
levels :-).

Co-authored-by: Richard Biener <rguenther@suse.de>

gcc/ChangeLog:

	* tree-ssa-loop-ch.c (entry_loop_condition_is_static): Resolve
	statically to the edge remaining in the loop.
---
 gcc/tree-ssa-loop-ch.c | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)

diff --git a/gcc/tree-ssa-loop-ch.c b/gcc/tree-ssa-loop-ch.c
index c7d86d751d4..af3401f112c 100644
--- a/gcc/tree-ssa-loop-ch.c
+++ b/gcc/tree-ssa-loop-ch.c
@@ -57,10 +57,24 @@ entry_loop_condition_is_static (class loop *l, path_range_query *query)
       || !irange::supports_type_p (TREE_TYPE (gimple_cond_lhs (last))))
     return false;
 
+  edge true_e, false_e;
+  extract_true_false_edges_from_block (e->dest, &true_e, &false_e);
+
+  /* If neither edge is the exit edge, this is not a case we'd like to
+     special-case.  */
+  if (!loop_exit_edge_p (l, true_e) && !loop_exit_edge_p (l, false_e))
+    return false;
+
+  tree desired_static_value;
+  if (loop_exit_edge_p (l, true_e))
+    desired_static_value = boolean_false_node;
+  else
+    desired_static_value = boolean_true_node;
+
   int_range<2> r;
   query->compute_ranges (e);
   query->range_of_stmt (r, last);
-  return r == int_range<2> (boolean_true_node, boolean_true_node);
+  return r == int_range<2> (desired_static_value, desired_static_value);
 }
 
 /* Check whether we should duplicate HEADER of LOOP.  At most *LIMIT
-- 
2.31.1