#include "gimplify-me.h"
#include "tree-ssa-loop-manip.h"
#include "dumpfile.h"
+#include "sreal.h"
static void copy_loops_to (class loop **, int,
class loop *);
free (bbs);
}
+/* Scales the frequencies of all basic blocks in LOOP that are strictly
+ dominated by BB by NUM/DEN. */
+
+void
+scale_dominated_blocks_in_loop (class loop *loop, basic_block bb,
+ profile_count num, profile_count den)
+{
+ basic_block son;
+
+ if (!den.nonzero_p () && !(num == profile_count::zero ()))
+ return;
+ auto_vec <basic_block, 8> worklist;
+ worklist.safe_push (bb);
+
+ while (!worklist.is_empty ())
+ for (son = first_dom_son (CDI_DOMINATORS, worklist.pop ());
+ son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ {
+ if (!flow_bb_inside_loop_p (loop, son))
+ continue;
+ son->count = son->count.apply_scale (num, den);
+ worklist.safe_push (son);
+ }
+}
+
+/* Return exit that suitable for update when loop iterations
+ changed. */
+
+static edge
+loop_exit_for_scaling (class loop *loop)
+{
+ edge exit_edge = single_exit (loop);
+ if (!exit_edge)
+ {
+ auto_vec<edge> exits = get_loop_exit_edges (loop);
+ exit_edge = single_likely_exit (loop, exits);
+ }
+ return exit_edge;
+}
+
+/* Assume that loop's entry count and profile up to a given EXIT_EDGE is
+ consistent. Update exit probability so loop exists with PROFILE_COUNT
+ and rescale profile of basic blocks inside loop dominated by EXIT_EDGE->src.
+
+ This is useful after number of iteraitons of loop has changed.
+ If EXIT_EDGE is NULL, the function will try to identify suitable exit.
+ If DESIRED_COUNT is NULL, loop entry count will be used.
+ In consistent profile usually loop exists as many times as it is entred.
+
+ Return updated exit if successfull and NULL otherwise. */
+
+edge
+update_loop_exit_probability_scale_dom_bbs (class loop *loop,
+ edge exit_edge,
+ profile_count desired_count)
+{
+ if (!exit_edge)
+ exit_edge = loop_exit_for_scaling (loop);
+ if (!exit_edge)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, ";; Not updating exit probability of loop %i;"
+ " it has no single exit\n",
+ loop->num);
+ }
+ return NULL;
+ }
+ /* If exit is inside another loop, adjusting its probability will also
+ adjust number of the inner loop iterations. Just do noting for now. */
+ if (!just_once_each_iteration_p (loop, exit_edge->src))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, ";; Not updating exit probability of loop %i;"
+ " exit is inside inner loop\n",
+ loop->num);
+ }
+ return NULL;
+ }
+ /* Normal loops exit as many times as they are entered. */
+ if (!desired_count.initialized_p ())
+ desired_count = loop_count_in (loop);
+ /* See if everything is already perfect. */
+ if (desired_count == exit_edge->count ())
+ return exit_edge;
+ profile_count old_exit_count = exit_edge->count ();
+ /* See if update is possible.
+ Avoid turning probability to 0 or 1 just trying to reach impossible
+ value.
+
+ Natural profile update after some loop will happily scale header count to
+ be less than count of entering the loop. This is bad idea and they should
+ special case maybe_flat_loop_profile.
+
+ It may also happen that the source basic block of the exit edge is
+ inside in-loop condition:
+
+ +-> header
+ | |
+ | B1
+ | / \
+ | | B2--exit_edge-->
+ | \ /
+ | B3
+ +__/
+
+ If B2 count is smaller than desired exit edge count
+ the profile was inconsistent with the newly discovered upper bound.
+ Probablity of edge B1->B2 is too low. We do not attempt to fix
+ that (as it is hard in general). */
+ if (desired_count > exit_edge->src->count
+ && exit_edge->src->count.differs_from_p (desired_count))
+ {
+ if (dump_file)
+ {
+ fprintf (dump_file, ";; Source bb of loop %i has count ",
+ loop->num);
+ exit_edge->src->count.dump (dump_file, cfun);
+ fprintf (dump_file,
+ " which is smaller then desired count of exitting loop ");
+ desired_count.dump (dump_file, cfun);
+ fprintf (dump_file, ". Profile update is impossible.\n");
+ }
+ /* Drop quality of probability since we know it likely
+ bad. */
+ exit_edge->probability = exit_edge->probability.guessed ();
+ return NULL;
+ }
+ if (!exit_edge->src->count.nonzero_p ())
+ {
+ if (dump_file)
+ {
+ fprintf (dump_file, ";; Not updating exit edge probability"
+ " in loop %i since profile is zero ",
+ loop->num);
+ }
+ return NULL;
+ }
+ set_edge_probability_and_rescale_others
+ (exit_edge, desired_count.probability_in (exit_edge->src->count));
+ /* Rescale the remaining edge probabilities and see if there is only
+ one. */
+ edge other_edge = NULL;
+ bool found = false;
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, exit_edge->src->succs)
+ if (!(e->flags & EDGE_FAKE)
+ && !loop_exit_edge_p (loop, e))
+ {
+ if (found)
+ {
+ other_edge = NULL;
+ break;
+ }
+ other_edge = e;
+ found = true;
+ }
+ /* If there is only loop latch after other edge,
+ update its profile. This is tiny bit more precise
+ than scaling. */
+ if (other_edge && other_edge->dest == loop->latch)
+ {
+ if (single_pred_p (loop->latch))
+ loop->latch->count = loop->latch->count
+ + old_exit_count - exit_edge->count ();
+ }
+ else
+ /* If there are multple blocks, just scale. */
+ scale_dominated_blocks_in_loop (loop, exit_edge->src,
+ exit_edge->src->count - exit_edge->count (),
+ exit_edge->src->count - old_exit_count);
+ return exit_edge;
+}
+
/* Scale profile in LOOP by P.
If ITERATION_BOUND is not -1, scale even further if loop is predicted
to iterate too many times.
if (iteration_bound == -1)
return;
- gcov_type iterations = expected_loop_iterations_unbounded (loop, NULL, true);
- if (iterations == -1)
+ sreal iterations;
+ if (!expected_loop_iterations_by_profile (loop, &iterations))
return;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file,
- ";; guessed iterations of loop %i:%i new upper bound %i:\n",
+ ";; Guessed iterations of loop %i is %f. New upper bound %i.\n",
loop->num,
- (int)iterations,
+ iterations.to_double (),
(int)iteration_bound);
}
/* See if loop is predicted to iterate too many times. */
- if (iterations <= iteration_bound)
+ if (iterations <= (sreal)iteration_bound)
return;
- /* Compute number of invocations of the loop. */
- profile_count count_in = profile_count::zero ();
- edge e;
- edge_iterator ei;
- bool found_latch = false;
- FOR_EACH_EDGE (e, ei, loop->header->preds)
- if (e->src != loop->latch)
- count_in += e->count ();
- else
- found_latch = true;
- gcc_checking_assert (found_latch);
+ profile_count count_in = loop_count_in (loop);
/* Now scale the loop body so header count is
count_in * (iteration_bound + 1) */
(int)iteration_bound);
}
/* Finally attempt to fix exit edge probability. */
- auto_vec<edge> exits = get_loop_exit_edges (loop);
- edge exit_edge = single_likely_exit (loop, exits);
+ edge exit_edge = loop_exit_for_scaling (loop);
/* In a consistent profile unadjusted_exit_count should be same as count_in,
however to preserve as much of the original info, avoid recomputing
it. */
- profile_count unadjusted_exit_count;
+ profile_count unadjusted_exit_count = profile_count::uninitialized ();
if (exit_edge)
unadjusted_exit_count = exit_edge->count ();
scale_loop_frequencies (loop, scale_prob);
-
- if (exit_edge && exit_edge->src->loop_father != loop)
- {
- fprintf (dump_file,
- ";; Loop exit is in inner loop;"
- " will leave exit probabilities inconsistent\n");
- }
- else if (exit_edge)
- {
- profile_count old_exit_count = exit_edge->count ();
- profile_probability new_probability;
- if (iteration_bound > 0)
- {
- /* It may happen that the source basic block of the exit edge is
- inside in-loop condition:
-
- +-> header
- | |
- | B1
- | / \
- | | B2--exit_edge-->
- | \ /
- | B3
- +__/
-
- If B2 count is smaller than desired exit edge count
- the profile was inconsistent with the newly discovered upper bound.
- Probablity of edge B1->B2 is too low. We do not attempt to fix
- that (as it is hard in general) but we want to avoid dropping
- count of edge B2->B3 to zero may confuse later optimizations. */
- if (unadjusted_exit_count.apply_scale (7, 8) > exit_edge->src->count)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file,
- ";; Source basic block of loop exit count is too small;"
- " will leave exit probabilities inconsistent\n");
- exit_edge->probability = exit_edge->probability.guessed ();
- return;
- }
- new_probability
- = unadjusted_exit_count.probability_in (exit_edge->src->count);
- }
- else
- new_probability = profile_probability::always ();
- set_edge_probability_and_rescale_others (exit_edge, new_probability);
- profile_count new_exit_count = exit_edge->count ();
-
- /* Rescale the remaining edge probabilities and see if there is only
- one. */
- edge other_edge = NULL;
- bool found = false;
- FOR_EACH_EDGE (e, ei, exit_edge->src->succs)
- if (!(e->flags & EDGE_FAKE)
- && !loop_exit_edge_p (loop, e))
- {
- if (found)
- {
- other_edge = NULL;
- break;
- }
- other_edge = e;
- found = true;
- }
- /* If there is only loop latch after other edge,
- update its profile. */
- if (other_edge && other_edge->dest == loop->latch)
- loop->latch->count -= new_exit_count - old_exit_count;
- else
- {
- basic_block *body = get_loop_body (loop);
- profile_count new_count = exit_edge->src->count - new_exit_count;
- profile_count old_count = exit_edge->src->count - old_exit_count;
-
- for (unsigned int i = 0; i < loop->num_nodes; i++)
- if (body[i] != exit_edge->src
- && dominated_by_p (CDI_DOMINATORS, body[i], exit_edge->src))
- body[i]->count = body[i]->count.apply_scale (new_count,
- old_count);
-
- free (body);
- }
- }
- else if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file,
- ";; Loop has mulitple exits;"
- " will leave exit probabilities inconsistent\n");
- }
+ update_loop_exit_probability_scale_dom_bbs (loop, exit_edge,
+ unadjusted_exit_count);
}
/* Recompute dominance information for basic blocks outside LOOP. */
have no successor, which caller is expected to fix somehow.
If this may cause the information about irreducible regions to become
- invalid, IRRED_INVALIDATED is set to true.
+ invalid, IRRED_INVALIDATED is set to true.
LOOP_CLOSED_SSA_INVALIDATED, if non-NULL, is a bitmap where we store
basic blocks that had non-trivial update on their loop_father.*/
should've managed the flags so all except for original loop
has won't exist set. */
scale_act = wanted_count.probability_in (count_in);
+
/* Now simulate the duplication adjustments and compute header
frequency of the last copy. */
for (i = 0; i < ndupl; i++)
profile_probability prob_pass_main = bitmap_bit_p (wont_exit, 0)
? prob_pass_wont_exit
: prob_pass_thru;
- profile_probability p = prob_pass_main;
- profile_count scale_main_den = count_in;
- for (i = 0; i < ndupl; i++)
+ if (!(flags & DLTHE_FLAG_FLAT_PROFILE))
{
- scale_main_den += count_in.apply_probability (p);
- p = p * scale_step[i];
+ profile_probability p = prob_pass_main;
+ profile_count scale_main_den = count_in;
+ for (i = 0; i < ndupl; i++)
+ {
+ scale_main_den += count_in.apply_probability (p);
+ p = p * scale_step[i];
+ }
+ /* If original loop is executed COUNT_IN times, the unrolled
+ loop will account SCALE_MAIN_DEN times. */
+ scale_main = count_in.probability_in (scale_main_den);
}
- /* If original loop is executed COUNT_IN times, the unrolled
- loop will account SCALE_MAIN_DEN times. */
- scale_main = count_in.probability_in (scale_main_den);
+ else
+ scale_main = profile_probability::always ();
scale_act = scale_main * prob_pass_main;
}
else
projects / thirdparty / gcc.git / blobdiff