On Mon, Jul 17, 2023 at 5:18 PM Richard Biener via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> On Fri, 14 Jul 2023, Jan Hubicka wrote:
>
> > Hi,
> > loop-ch currently does analysis using ranger for all loops to identify
> > candidates and then follows by phase where headers are duplicated (which
> > breaks SSA and ranger). The second stage does more analysis (to see how
> > many BBs we want to duplicate) but can't use ranger and thus misses
> > information about static conditionals.
> >
> > This patch pushes all analysis into the first stage. We record how many
> > BBs to duplicate and the second stage just duplicats as it is told so.
> > This makes it possible to also extend range query done also to basic
> > blocks that are not headers. This is easy to do, since we already do
> > path specific query so we only need to extend the path by headers we
> > decided to dulicate earlier.
> >
> > This makes it possible to track situations where exit that is always
> > false in the first iteration for tests not in the original loop header.
> > Doing so lets us to update profile better and do better heuristics. In
> > particular I changed logic as follows
> > 1) should_duplicate_loop_header_p counts size of duplicated region. When
> > we
> > know that a given conditional will be constant true or constant false
> > either
> > in the duplicated region, by range query, or in the loop body after
> > duplication (since it is loop invariant), we do not account it to code
> > size
> > costs
> > 2) don't need account loop invariant compuations that will be duplicated
> > as they will become fully invariant
> > (maybe we want to have some cap for register pressure eventually?)
> > 3) optimize_size logic is now different. Originally we started
> > duplicating
> > iff the first conditional was known to be true by ranger query, but
> > then
> > we used same limits as for -O2.
> >
> > I now simply lower limits to 0. This means that every conditional
> > in duplicated sequence must be either loop invariant or constant when
> > duplicated and we only duplicate statements computing loop invariants
> > and those we account to 0 size anyway,
> >
> > This makes code IMO more streamlined (and hopefully will let us to merge
> > ibts with loop peeling logic), but makes little difference in practice.
> > The problem is that in loop:
> >
> > void test2();
> > void test(int n)
> > {
> > for (int i = 0; n && i < 10; i++)
> > test2();
> > }
> >
> > We produce:
> > <bb 4> [local count: 1073741824 freq: 9.090909]:
> > # i_4 = PHI <0(2), i_9(3)>
> > _1 = n_7(D) != 0;
> > _2 = i_4 <= 9;
> > _3 = _1 & _2;
> > if (_3 != 0)
> > goto <bb 3>; [89.00%]
> > else
> > goto <bb 5>; [11.00%]
> >
> > and do not understand that the final conditional is a combination of a
> > conditional
> > that is always true in first iteration and a conditional that is loop
> > invariant.
> >
> > This is also the case of
> > void test2();
> > void test(int n)
> > {
> > for (int i = 0; n; i++)
> > {
> > if (i > 10)
> > break;
> > test2();
> > }
> > }
> > Which we turn to the earlier case in ifcombine.
> >
> > With disabled ifcombine things however works as exepcted. This is something
> > I plan to handle incrementally. However extending loop-ch and peeling
> > passes
> > to understand such combined conditionals is still not good enough: at the
> > time ifcombine
> > merged the two conditionals we lost profile information on how often n is 0,
> > so we can't recover correct profile or know what is expected number of
> > iterations
> > after the transofrm.
This regressed
FAIL: gcc.target/i386/pr93089-2.c scan-assembler vmulps[^\n\r]*zmm
FAIL: gcc.target/i386/pr93089-3.c scan-assembler vmulps[^\n\r]*zmm
The testcase is quite simple, not sure why it's regressed.
1/* PR target/93089 */
2/* { dg-do compile } */
3/* { dg-options "-O2 -fopenmp-simd -mtune=znver1" } */
4/* { dg-final { scan-assembler "vmulps\[^\n\r]*zmm" } } */
5/* { dg-final { scan-assembler "vmulps\[^\n\r]*ymm" } } */
6
7#pragma omp declare simd notinbranch
8float
9foo (float x, float y)
10{
11 return x * y;
12}
> >
> > Bootstrapped/regtested x86_64-linux, OK?
>
> OK.
>
> Thanks,
> Richard.
>
> > Honza
> >
> >
> > gcc/ChangeLog:
> >
> > * tree-ssa-loop-ch.cc (edge_range_query): Take loop argument; be ready
> > for queries not in headers.
> > (static_loop_exit): Add basic blck parameter; update use of
> > edge_range_query
> > (should_duplicate_loop_header_p): Add ranger and static_exits
> > parameter. Do not account statements that will be optimized
> > out after duplicaiton in overall size. Add ranger query to
> > find static exits.
> > (update_profile_after_ch): Take static_exits has set instead of
> > single eliminated_edge.
> > (ch_base::copy_headers): Do all analysis in the first pass;
> > remember invariant_exits and static_exits.
> >
> > diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc
> > index 24e7fbc805a..e0139cb432c 100644
> > --- a/gcc/tree-ssa-loop-ch.cc
> > +++ b/gcc/tree-ssa-loop-ch.cc
> > @@ -49,11 +49,13 @@ along with GCC; see the file COPYING3. If not see
> > the range of the solved conditional in R. */
> >
> > static void
> > -edge_range_query (irange &r, edge e, gcond *cond, gimple_ranger &ranger)
> > +edge_range_query (irange &r, class loop *loop, gcond *cond, gimple_ranger
> > &ranger)
> > {
> > - auto_vec<basic_block> path (2);
> > - path.safe_push (e->dest);
> > - path.safe_push (e->src);
> > + auto_vec<basic_block, 8> path;
> > + for (basic_block bb = gimple_bb (cond); bb != loop->header; bb =
> > single_pred_edge (bb)->src)
> > + path.safe_push (bb);
> > + path.safe_push (loop->header);
> > + path.safe_push (loop_preheader_edge (loop)->src);
> > path_range_query query (ranger, path);
> > if (!query.range_of_stmt (r, cond))
> > r.set_varying (boolean_type_node);
> > @@ -63,17 +65,16 @@ edge_range_query (irange &r, edge e, gcond *cond,
> > gimple_ranger &ranger)
> > and NULL otherwise. */
> >
> > static edge
> > -static_loop_exit (class loop *l, gimple_ranger *ranger)
> > +static_loop_exit (class loop *l, basic_block bb, gimple_ranger *ranger)
> > {
> > - edge e = loop_preheader_edge (l);
> > - gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (e->dest));
> > + gcond *last = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
> > edge ret_e;
> >
> > if (!last)
> > return NULL;
> >
> > edge true_e, false_e;
> > - extract_true_false_edges_from_block (e->dest, &true_e, &false_e);
> > + extract_true_false_edges_from_block (bb, &true_e, &false_e);
> >
> > /* If neither edge is the exit edge, this is not a case we'd like to
> > special-case. */
> > @@ -93,7 +94,7 @@ static_loop_exit (class loop *l, gimple_ranger *ranger)
> > }
> >
> > int_range<2> r;
> > - edge_range_query (r, e, last, *ranger);
> > + edge_range_query (r, l, last, *ranger);
> > return r == desired_static_range ? ret_e : NULL;
> > }
> >
> > @@ -131,8 +132,10 @@ loop_iv_derived_p (class loop *loop,
> >
> > static bool
> > should_duplicate_loop_header_p (basic_block header, class loop *loop,
> > + gimple_ranger *ranger,
> > int *limit,
> > - hash_set <edge> *invariant_exits)
> > + hash_set <edge> *invariant_exits,
> > + hash_set <edge> *static_exits)
> > {
> > gimple_stmt_iterator bsi;
> >
> > @@ -209,6 +212,9 @@ should_duplicate_loop_header_p (basic_block header,
> > class loop *loop,
> > if (is_gimple_debug (last))
> > continue;
> >
> > + if (gimple_code (last) == GIMPLE_COND)
> > + break;
> > +
> > if (gimple_code (last) == GIMPLE_CALL
> > && (!gimple_inexpensive_call_p (as_a <gcall *> (last))
> > /* IFN_LOOP_DIST_ALIAS means that inner loop is distributed
> > @@ -222,16 +228,6 @@ should_duplicate_loop_header_p (basic_block header,
> > class loop *loop,
> > return false;
> > }
> >
> > - *limit -= estimate_num_insns (last, &eni_size_weights);
> > - if (*limit < 0)
> > - {
> > - if (dump_file && (dump_flags & TDF_DETAILS))
> > - fprintf (dump_file,
> > - " Not duplicating bb %i contains too many insns.\n",
> > - header->index);
> > - return false;
> > - }
> > -
> > /* Classify the stmt based on whether its computation is based
> > on a IV or whether it is invariant in the loop. */
> > gimple_set_uid (last, 0);
> > @@ -257,9 +253,36 @@ should_duplicate_loop_header_p (basic_block header,
> > class loop *loop,
> > inv = false;
> > }
> > gimple_set_uid (last, (iv ? 1 : 0) | (inv ? 2 : 0));
> > + /* Loop invariants will be optimized out in loop body after
> > + duplication; do not account invariant computation in code
> > + size costs. */
> > + if (inv)
> > + continue;
> > + }
> > +
> > + *limit -= estimate_num_insns (last, &eni_size_weights);
> > + if (*limit < 0)
> > + {
> > + if (dump_file && (dump_flags & TDF_DETAILS))
> > + fprintf (dump_file,
> > + " Not duplicating bb %i contains too many insns.\n",
> > + header->index);
> > + return false;
> > }
> > }
> >
> > + edge static_exit = static_loop_exit (loop, header, ranger);
> > +
> > + if (static_exit && static_exits)
> > + {
> > + static_exits->add (static_exit);
> > + if (dump_file && (dump_flags & TDF_DETAILS))
> > + fprintf (dump_file,
> > + " Will eliminate peeled conditional in bb %d.\n",
> > + static_exit->src->index);
> > + /* Still look for invariant exits; exit may be both. */
> > + }
> > +
> > /* If the condition tests a non-IV loop variant we do not want to rotate
> > the loop further. Unless this is the original loop header. */
> > tree lhs = gimple_cond_lhs (last);
> > @@ -284,12 +307,28 @@ should_duplicate_loop_header_p (basic_block header,
> > class loop *loop,
> > }
> > return true;
> > }
> > +
> > + if (static_exit)
> > + return true;
> > +
> > + /* We was not able to prove that conditional will be eliminated. */
> > + *limit -= estimate_num_insns (last, &eni_size_weights);
> > + if (*limit < 0)
> > + {
> > + if (dump_file && (dump_flags & TDF_DETAILS))
> > + fprintf (dump_file,
> > + " Not duplicating bb %i contains too many insns.\n",
> > + header->index);
> > + return false;
> > + }
> > +
> > /* TODO: This is heuristics that claims that IV based ocnditionals will
> > likely be optimized out in duplicated header. We could use ranger
> > query instead to tell this more precisely. */
> > - if (header != loop->header
> > - && ((!lhs_invariant && !loop_iv_derived_p (loop, lhs))
> > - || (!rhs_invariant && !loop_iv_derived_p (loop, rhs))))
> > + if ((lhs_invariant || loop_iv_derived_p (loop, lhs))
> > + && (rhs_invariant || loop_iv_derived_p (loop, rhs)))
> > + return true;
> > + if (header != loop->header)
> > {
> > if (dump_file && (dump_flags & TDF_DETAILS))
> > fprintf (dump_file,
> > @@ -386,8 +425,9 @@ do_while_loop_p (class loop *loop)
> > static void
> > update_profile_after_ch (class loop *loop,
> > basic_block *region, basic_block *region_copy,
> > - unsigned n_region, edge eliminated_edge,
> > + unsigned n_region,
> > hash_set <edge> *invariant_exits,
> > + hash_set <edge> *static_exits,
> > profile_count entry_count)
> > {
> > for (unsigned int i = 0; i < n_region; i++)
> > @@ -421,10 +461,13 @@ update_profile_after_ch (class loop *loop,
> > && e_copy->dest == region_copy[i + 1]));
> > region_copy[i]->count = entry_count;
> > profile_count exit_e_count = exit_e->count ();
> > - if (eliminated_edge == exit_e)
> > + bool was_static = false;
> > + if (static_exits->contains (exit_e))
> > {
> > /* Update profile and the conditional.
> > CFG update is done by caller. */
> > + static_exits->remove (exit_e);
> > + was_static = true;
> > e_copy->probability = profile_probability::always ();
> > exit_e_copy->probability = profile_probability::never ();
> > gcond *cond_stmt
> > @@ -437,7 +480,6 @@ update_profile_after_ch (class loop *loop,
> > /* Header copying is a special case of jump threading, so use
> > common code to update loop body exit condition. */
> > update_bb_profile_for_threading (region[i], entry_count, e);
> > - eliminated_edge = NULL;
> > }
> > else
> > region[i]->count -= region_copy[i]->count;
> > @@ -448,7 +490,7 @@ update_profile_after_ch (class loop *loop,
> > loop, so increase probability accordingly.
> > If the edge is eliminated_edge we already corrected
> > profile above. */
> > - if (entry_count.nonzero_p () && eliminated_edge != exit_e)
> > + if (entry_count.nonzero_p () && !was_static)
> > set_edge_probability_and_rescale_others
> > (exit_e_copy, exit_e_count.probability_in
> > (entry_count));
> > @@ -465,7 +507,7 @@ update_profile_after_ch (class loop *loop,
> > entry_count = e_copy->count ();
> > }
> > /* Be sure that we seen all edges we are supposed to update. */
> > - gcc_checking_assert (!eliminated_edge
> > + gcc_checking_assert (static_exits->is_empty ()
> > && invariant_exits->is_empty ());
> > }
> >
> > @@ -564,10 +606,7 @@ protected:
> > unsigned int
> > ch_base::copy_headers (function *fun)
> > {
> > - basic_block header;
> > - edge exit, nonexit, entry;
> > basic_block *bbs, *copied_bbs;
> > - unsigned n_bbs;
> > unsigned bbs_size;
> > bool changed = false;
> >
> > @@ -578,7 +617,12 @@ ch_base::copy_headers (function *fun)
> > copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
> > bbs_size = n_basic_blocks_for_fn (fun);
> >
> > - struct candidate {class loop *loop; edge static_exit;};
> > + struct candidate
> > + {
> > + class loop *loop;
> > + unsigned int nheaders;
> > + hash_set <edge> *invariant_exits, *static_exits;
> > + };
> > auto_vec<struct candidate> candidates;
> > auto_vec<std::pair<edge, loop_p> > copied;
> > auto_vec<class loop *> loops_to_unloop;
> > @@ -588,13 +632,14 @@ ch_base::copy_headers (function *fun)
> > gimple_ranger *ranger = new gimple_ranger;
> > for (auto loop : loops_list (cfun, 0))
> > {
> > - int initial_limit = param_max_loop_header_insns;
> > + int initial_limit = optimize_loop_for_speed_p (loop)
> > + ? param_max_loop_header_insns : 0;
> > int remaining_limit = initial_limit;
> > if (dump_file && (dump_flags & TDF_DETAILS))
> > fprintf (dump_file,
> > "Analyzing loop %i\n", loop->num);
> >
> > - header = loop->header;
> > + basic_block header = loop->header;
> > if (!get_max_loop_iterations_int (loop))
> > {
> > if (dump_file && (dump_flags & TDF_DETAILS))
> > @@ -613,24 +658,38 @@ ch_base::copy_headers (function *fun)
> > || !process_loop_p (loop))
> > continue;
> >
> > - edge static_exit = static_loop_exit (loop, ranger);
> > -
> > - /* Avoid loop header copying when optimizing for size unless we can
> > - determine that the loop condition is static in the first
> > - iteration. */
> > - if (optimize_loop_for_size_p (loop)
> > - && !loop->force_vectorize
> > - && !static_exit)
> > + /* Iterate the header copying up to limit; this takes care of the
> > cases
> > + like while (a && b) {...}, where we want to have both of the
> > conditions
> > + copied. TODO -- handle while (a || b) - like cases, by not requiring
> > + the header to have just a single successor and copying up to
> > + postdominator. */
> > + int nheaders = 0;
> > + hash_set <edge> *invariant_exits = new hash_set <edge>;
> > + hash_set <edge> *static_exits = new hash_set <edge>;
> > + while (should_duplicate_loop_header_p (header, loop, ranger,
> > + &remaining_limit,
> > + invariant_exits,
> > + static_exits))
> > {
> > + nheaders++;
> > if (dump_file && (dump_flags & TDF_DETAILS))
> > - fprintf (dump_file,
> > - " Not duplicating bb %i: optimizing for size.\n",
> > - header->index);
> > - continue;
> > + fprintf (dump_file, " Will duplicate bb %i\n", header->index);
> > +
> > + /* Find a successor of header that is inside a loop; i.e. the new
> > + header after the condition is copied. */
> > + if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
> > + header = EDGE_SUCC (header, 0)->dest;
> > + else
> > + header = EDGE_SUCC (header, 1)->dest;
> > }
> >
> > - if (should_duplicate_loop_header_p (header, loop, &remaining_limit,
> > NULL))
> > - candidates.safe_push ({loop, static_exit});
> > + if (nheaders)
> > + candidates.safe_push ({loop, nheaders, invariant_exits,
> > static_exits});
> > + else
> > + {
> > + delete invariant_exits;
> > + delete static_exits;
> > + }
> > }
> > /* Do not use ranger after we change the IL and not have updated SSA. */
> > delete ranger;
> > @@ -638,37 +697,25 @@ ch_base::copy_headers (function *fun)
> > for (auto candidate : candidates)
> > {
> > class loop *loop = candidate.loop;
> > - int initial_limit = param_max_loop_header_insns;
> > - int remaining_limit = initial_limit;
> > if (dump_file && (dump_flags & TDF_DETAILS))
> > fprintf (dump_file,
> > "Copying headers of loop %i\n", loop->num);
> >
> > - header = loop->header;
> > -
> > - /* Iterate the header copying up to limit; this takes care of the
> > cases
> > - like while (a && b) {...}, where we want to have both of the
> > conditions
> > - copied. TODO -- handle while (a || b) - like cases, by not requiring
> > - the header to have just a single successor and copying up to
> > - postdominator. */
> > -
> > - nonexit = NULL;
> > - n_bbs = 0;
> > + basic_block header = loop->header;
> > + edge nonexit = NULL;
> > + edge exit = NULL;
> > + unsigned int n_bbs = 0;
> > int nexits = 0;
> > profile_count exit_count = profile_count::zero ();
> > profile_count entry_count = profile_count::zero ();
> > edge e;
> > edge_iterator ei;
> > - hash_set <edge> invariant_exits;
> > +
> > FOR_EACH_EDGE (e, ei, loop->header->preds)
> > if (e->src != loop->latch)
> > entry_count += e->count ();
> > - while (should_duplicate_loop_header_p (header, loop,
> > &remaining_limit,
> > - &invariant_exits))
> > + while (n_bbs < candidate.nheaders)
> > {
> > - if (dump_file && (dump_flags & TDF_DETAILS))
> > - fprintf (dump_file, " Will duplicate bb %i\n", header->index);
> > -
> > /* Find a successor of header that is inside a loop; i.e. the new
> > header after the condition is copied. */
> > if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
> > @@ -688,21 +735,10 @@ ch_base::copy_headers (function *fun)
> > header = nonexit->dest;
> > }
> >
> > - if (!nonexit)
> > - continue;
> > -
> > if (dump_file && (dump_flags & TDF_DETAILS))
> > - {
> > - fprintf (dump_file,
> > - "Duplicating header of the loop %d up to edge %d->%d,"
> > - " %i insns.\n",
> > - loop->num, exit->src->index, exit->dest->index,
> > - initial_limit - remaining_limit);
> > - if (candidate.static_exit)
> > - fprintf (dump_file,
> > - " Will eliminate peeled conditional in bb %d.\n",
> > - candidate.static_exit->src->index);
> > - }
> > + fprintf (dump_file,
> > + "Duplicating header of the loop %d up to edge %d->%d\n",
> > + loop->num, exit->src->index, exit->dest->index);
> >
> > /* Ensure that the header will have just the latch as a predecessor
> > inside the loop. */
> > @@ -712,20 +748,25 @@ ch_base::copy_headers (function *fun)
> > exit = single_pred_edge (header);
> > }
> >
> > - entry = loop_preheader_edge (loop);
> > + edge entry = loop_preheader_edge (loop);
> >
> > propagate_threaded_block_debug_into (exit->dest, entry->dest);
> > if (!gimple_duplicate_seme_region (entry, exit, bbs, n_bbs,
> > copied_bbs,
> > true))
> > {
> > + delete candidate.static_exits;
> > + delete candidate.invariant_exits;
> > if (dump_file && (dump_flags & TDF_DETAILS))
> > fprintf (dump_file, "Duplication failed.\n");
> > continue;
> > }
> > if (loop->header->count.initialized_p ())
> > update_profile_after_ch (loop, bbs, copied_bbs, n_bbs,
> > - candidate.static_exit, &invariant_exits,
> > + candidate.invariant_exits,
> > + candidate.static_exits,
> > entry_count);
> > + delete candidate.static_exits;
> > + delete candidate.invariant_exits;
> > copied.safe_push (std::make_pair (entry, loop));
> >
> > /* If the loop has the form "for (i = j; i < j + 10; i++)" then
> >
>
> --
> Richard Biener <rguent...@suse.de>
> SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg,
> Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald, Boudien Moerman;
> HRB 36809 (AG Nuernberg)
--
BR,
Hongtao
