public inbox for gcc-cvs@sourceware.org help / color / mirror / Atom feed
From: Jan Hubicka <hubicka@gcc.gnu.org> To: gcc-cvs@gcc.gnu.org Subject: [gcc(refs/users/kubaneko/heads/histogram)] Merge final fix for copy header from master Date: Sat, 22 Apr 2023 09:29:05 +0000 (GMT) [thread overview] Message-ID: <20230422092905.BF9D43858C83@sourceware.org> (raw) https://gcc.gnu.org/g:3d73340a2969f72b754736f77d5285a86df2ed14 commit 3d73340a2969f72b754736f77d5285a86df2ed14 Author: Honza <jh@ryzen3.suse.cz> Date: Sat Apr 22 11:28:41 2023 +0200 Merge final fix for copy header from master Diff: --- gcc/cfgloopmanip.h | 1 + gcc/tree-ssa-loop-ch.cc | 114 +++++++++++++++++++++++++++++++++++-------- gcc/tree-ssa-loop-ivcanon.cc | 57 +++++++++++++++++++++- 3 files changed, 150 insertions(+), 22 deletions(-) diff --git a/gcc/cfgloopmanip.h b/gcc/cfgloopmanip.h index 93e417fcb7d..c40cfeae0e3 100644 --- a/gcc/cfgloopmanip.h +++ b/gcc/cfgloopmanip.h @@ -59,5 +59,6 @@ class loop * loop_version (class loop *, void *, basic_block *, profile_probability, profile_probability, profile_probability, profile_probability, bool); +void adjust_loop_info_after_peeling (class loop *loop, int npeel, bool precise); #endif /* GCC_CFGLOOPMANIP_H */ diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc index e621011fe44..2fad2a3d7b6 100644 --- a/gcc/tree-ssa-loop-ch.cc +++ b/gcc/tree-ssa-loop-ch.cc @@ -461,7 +461,8 @@ ch_base::copy_headers (function *fun) edge e; edge_iterator ei; FOR_EACH_EDGE (e, ei, loop->header->preds) - entry_count += e->count (); + if (e->src != loop->latch) + entry_count += e->count (); while (should_duplicate_loop_header_p (header, loop, &remaining_limit)) { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -498,8 +499,11 @@ ch_base::copy_headers (function *fun) /* Ensure that the header will have just the latch as a predecessor inside the loop. */ - if (!single_pred_p (exit->dest)) - exit = single_pred_edge (split_edge (exit)); + if (!single_pred_p (nonexit->dest)) + { + header = split_edge (nonexit); + exit = single_pred_edge (header); + } entry = loop_preheader_edge (loop); @@ -560,18 +564,17 @@ ch_base::copy_headers (function *fun) /* Update header of the loop. */ loop->header = header; /* Find correct latch. We only duplicate chain of conditionals so - there should be precisely two edges to the new header. One entry - edge and one to latch. */ + there should be precisely two edges to the new header. One entry + edge and one to latch. */ FOR_EACH_EDGE (e, ei, loop->header->preds) - if (header != e->src) - { - loop->latch = e->src; - break; - } - /* Ensure that the latch and the preheader is simple (we know that they - are not now, since there was the loop exit condition. */ - split_edge (loop_preheader_edge (loop)); - split_edge (loop_latch_edge (loop)); + if (header != e->src) + { + loop->latch = e->src; + break; + } + /* Ensure that the latch is simple. */ + if (!single_succ_p (loop_latch_edge (loop)->src)) + split_edge (loop_latch_edge (loop)); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -580,22 +583,91 @@ ch_base::copy_headers (function *fun) else fprintf (dump_file, "Loop %d is still not do-while loop.\n", loop->num); + fprintf (dump_file, "Exit count: "); + exit_count.dump (dump_file); + fprintf (dump_file, "\nEntry count: "); + entry_count.dump (dump_file); + fprintf (dump_file, "\n"); } - // if it is unlikely that after header copy the iterations enter the loop - // it behaves like peeling 1 time + + /* We possibly decreased number of itrations by 1. */ auto_vec<edge> exits = get_loop_exit_edges (loop); - if (nexits == (int) exits.length ()) - adjust_loop_estimates_minus (loop, 1, true); + bool precise = (nexits == (int) exits.length ()); + if (!get_max_loop_iterations_int (loop)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Loop %d no longer loops.\n", loop->num); + /* TODO: We can unloop like in tree-ssa-loop-ivcanon. */ + precise = false; + } + /* Check that loop may not terminate in other way than via + basic blocks we duplicated. */ + if (precise) + { + basic_block *bbs = get_loop_body (loop); + for (unsigned i = 0; i < loop->num_nodes && precise; ++i) + { + basic_block bb = bbs[i]; + bool found_exit = false; + FOR_EACH_EDGE (e, ei, bb->succs) + if (!flow_bb_inside_loop_p (loop, e->dest)) + { + found_exit = true; + break; + } + /* If BB has exit, it was duplicated. */ + if (found_exit) + continue; + /* Give up on irreducible loops. */ + if (bb->flags & BB_IRREDUCIBLE_LOOP) + { + precise = false; + break; + } + /* Check that inner loops are finite. */ + for (class loop *l = bb->loop_father; l != loop && precise; + l = loop_outer (l)) + if (!l->finite_p) + { + precise = false; + break; + } + /* Verify that there is no statement that may be terminate + execution in a way not visible to CFG. */ + for (gimple_stmt_iterator bsi = gsi_start_bb (bb); + !gsi_end_p (bsi); gsi_next (&bsi)) + if (stmt_can_terminate_bb_p (gsi_stmt (bsi))) + precise = false; + } + } + if (precise) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Peeled all exits:" + " decreased number of iterations of loop %d by 1.\n", + loop->num); + adjust_loop_info_after_peeling (loop, 1, true); + } else if (exit_count >= entry_count.apply_scale (9, 10)) - adjust_loop_estimates_minus (loop, 1, false); + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Peeled likely exits: likely decreased number " + "of iterations of loop %d by 1.\n", loop->num); + adjust_loop_info_after_peeling (loop, 1, false); + } + else if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Not decreased number" + " of iterations of loop %d; likely exits remains.\n", + loop->num); changed = true; } if (changed) { - if (flag_checking) - verify_loop_structure (); update_ssa (TODO_update_ssa); /* After updating SSA form perform CSE on the loop header copies. This is esp. required for the pass before diff --git a/gcc/tree-ssa-loop-ivcanon.cc b/gcc/tree-ssa-loop-ivcanon.cc index 9c8443fd8e6..6a9ed49bb25 100644 --- a/gcc/tree-ssa-loop-ivcanon.cc +++ b/gcc/tree-ssa-loop-ivcanon.cc @@ -980,6 +980,61 @@ estimated_peeled_sequence_size (struct loop_size *size, - size->eliminated_by_peeling), 1); } +/* Update loop estimates after peeling LOOP by NPEEL. + If PRECISE is false only likely exists were duplicated and thus + do not update any estimates that are supposed to be always reliable. */ +void +adjust_loop_info_after_peeling (class loop *loop, int npeel, bool precise) +{ + if (loop->any_estimate) + { + /* Since peeling is mostly about loops where first few + iterations are special, it is not quite correct to + assume that the remaining iterations will behave + the same way. However we do not have better info + so update the esitmate, since it is likely better + than keeping it as it is. + + Remove it if it looks wrong. + + TODO: We likely want to special case the situation where + peeling is optimizing out exit edges and only update + estimates here. */ + if (wi::leu_p (npeel, loop->nb_iterations_estimate)) + loop->nb_iterations_estimate -= npeel; + else + loop->any_estimate = false; + } + if (loop->any_upper_bound && precise) + { + if (wi::leu_p (npeel, loop->nb_iterations_upper_bound)) + loop->nb_iterations_upper_bound -= npeel; + else + { + /* Peeling maximal number of iterations or more + makes no sense and is a bug. + We should peel completely. */ + gcc_unreachable (); + } + } + if (loop->any_likely_upper_bound) + { + if (wi::leu_p (npeel, loop->nb_iterations_likely_upper_bound)) + loop->nb_iterations_likely_upper_bound -= npeel; + else + { + loop->any_estimate = true; + loop->nb_iterations_estimate = 0; + loop->nb_iterations_likely_upper_bound = 0; + } + } + if (loop->counters) + { + histogram_counters_minus_upper_bound (loop->counters, npeel); + /* TODO: Update loop estimate if possible. */ + } +} + /* If the loop is expected to iterate N times and is small enough, duplicate the loop body N+1 times before the loop itself. This way the hot path will never @@ -1184,7 +1239,7 @@ try_peel_loop (class loop *loop, "peeled loop %d, %i times.\n", loop->num, (int)npeel); } - adjust_loop_estimates_minus (loop, npeel, true); + adjust_loop_info_after_peeling (loop, npeel, true); profile_count entry_count = profile_count::zero ();
reply other threads:[~2023-04-22 9:29 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20230422092905.BF9D43858C83@sourceware.org \ --to=hubicka@gcc.gnu.org \ --cc=gcc-cvs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).