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