@@ -33,6 +33,7 @@ along with GCC; see the file COPYING3. If not see
#include "dumpfile.h"
#include "tree-ssa.h"
#include "tree-pretty-print.h"
+#include "sreal.h"
static void flow_loops_cfg_dump (FILE *);
@@ -138,14 +139,11 @@ flow_loop_dump (const class loop *loop, FILE *file,
loop_depth (loop), (long) (loop_outer (loop)
? loop_outer (loop)->num : -1));
- if (loop->latch)
- {
- bool read_profile_p;
- gcov_type nit = expected_loop_iterations_unbounded (loop, &read_profile_p);
- if (read_profile_p && !loop->any_estimate)
- fprintf (file, ";; profile-based iteration count: %" PRIu64 "\n",
- (uint64_t) nit);
- }
+ bool reliable;
+ sreal iterations;
+ if (expected_loop_iterations_by_profile (loop, &iterations, &reliable))
+ fprintf (file, ";; profile-based iteration count: %f %s\n",
+ iterations.to_double (), reliable ? "(reliable)" : "(unreliable)");
fprintf (file, ";; nodes:");
bbs = get_loop_body (loop);
@@ -2014,10 +2012,12 @@ get_estimated_loop_iterations (class loop *loop, widest_int *nit)
profile. */
if (!loop->any_estimate)
{
- if (loop->header->count.reliable_p ())
+ sreal snit;
+ bool reliable;
+ if (expected_loop_iterations_by_profile (loop, &snit, &reliable)
+ && reliable)
{
- *nit = gcov_type_to_wide_int
- (expected_loop_iterations_unbounded (loop) + 1);
+ *nit = (snit + 0.5).to_int ();
return true;
}
return false;
@@ -403,7 +403,10 @@ extern void verify_loop_structure (void);
/* Loop analysis. */
extern bool just_once_each_iteration_p (const class loop *, const_basic_block);
gcov_type expected_loop_iterations_unbounded (const class loop *,
- bool *read_profile_p = NULL, bool by_profile_only = false);
+ bool *read_profile_p = NULL);
+extern bool expected_loop_iterations_by_profile (const class loop *loop,
+ sreal *ret,
+ bool *reliable = NULL);
extern unsigned expected_loop_iterations (class loop *);
extern rtx doloop_condition_get (rtx_insn *);
@@ -233,79 +233,101 @@ average_num_loop_insns (const class loop *loop)
return ret;
}
-/* Returns expected number of iterations of LOOP, according to
- measured or guessed profile.
+/* Return true if BB profile can be used to determine the expected number of
+ iterations (that is number of executions of latch edge(s) for each
+ entry of the loop. If this is the case initialize RET with the number
+ of iterations.
+
+ RELIABLE is set if profile indiates that the returned value should be
+ realistic estimate. (This is the case if we read profile and did not
+ messed it up yet and not the case of guessed profiles.)
- This functions attempts to return "sane" value even if profile
- information is not good enough to derive osmething.
- If BY_PROFILE_ONLY is set, this logic is bypassed and function
- return -1 in those scenarios. */
+ This function uses only CFG profile. We track more reliable info in
+ loop_info structure and for loop optimization heuristics more relevant
+ is get_estimated_loop_iterations API. */
-gcov_type
-expected_loop_iterations_unbounded (const class loop *loop,
- bool *read_profile_p,
- bool by_profile_only)
+bool
+expected_loop_iterations_by_profile (const class loop *loop, sreal *ret,
+ bool *reliable)
{
+ profile_count header_count = loop->header->count;
+ if (reliable)
+ *reliable = false;
+
+ /* TODO: For single exit loops we can use loop exit edge probability.
+ It also may be reliable while loop itself was adjusted. */
+ if (!header_count.initialized_p ()
+ || !header_count.nonzero_p ())
+ return false;
+
+ profile_count count_in = profile_count::zero ();
edge e;
edge_iterator ei;
- gcov_type expected = -1;
-
- if (read_profile_p)
- *read_profile_p = false;
- /* If we have no profile at all, use AVG_LOOP_NITER. */
- if (profile_status_for_fn (cfun) == PROFILE_ABSENT)
- {
- if (by_profile_only)
- return -1;
- expected = param_avg_loop_niter;
- }
- else if (loop->latch && (loop->latch->count.initialized_p ()
- || loop->header->count.initialized_p ()))
+ /* For single-latch loops avoid querying dominators. */
+ if (loop->latch)
{
- profile_count count_in = profile_count::zero (),
- count_latch = profile_count::zero ();
-
+ bool found = false;
FOR_EACH_EDGE (e, ei, loop->header->preds)
- if (e->src == loop->latch)
- count_latch = e->count ();
- else
+ if (e->src != loop->latch)
count_in += e->count ();
-
- if (!count_latch.initialized_p ())
- {
- if (by_profile_only)
- return -1;
- expected = param_avg_loop_niter;
- }
- else if (!count_in.nonzero_p ())
+ else
+ found = true;
+ /* If latch is not found, loop is inconsistent. */
+ gcc_checking_assert (found);
+ }
+ else
+ FOR_EACH_EDGE (e, ei, loop->header->preds)
+ if (!dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
+ count_in += e->count ();
+
+ bool known;
+ /* Number of iterations is number of executions of latch edge. */
+ *ret = (header_count - count_in).to_sreal_scale (count_in, &known);
+ if (!known)
+ return false;
+ if (reliable)
+ {
+ /* Header should have at least count_in many executions.
+ Give up on clearly inconsistent profile. */
+ if (header_count < count_in && header_count.differs_from_p (count_in))
{
- if (by_profile_only)
- return -1;
- expected = count_latch.to_gcov_type () * 2;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Inconsistent bb profile of loop %i\n",
+ loop->num);
+ *reliable = false;
}
else
- {
- expected = (count_latch.to_gcov_type () + count_in.to_gcov_type ()
- - 1) / count_in.to_gcov_type ();
- if (read_profile_p
- && count_latch.reliable_p () && count_in.reliable_p ())
- *read_profile_p = true;
- }
+ *reliable = count_in.reliable_p () && header_count.reliable_p ();
}
+ return true;
+}
+
+/* Returns expected number of iterations of LOOP, according to
+ measured or guessed profile.
+
+ This functions attempts to return "sane" value even if profile
+ information is not good enough to derive osmething. */
+
+gcov_type
+expected_loop_iterations_unbounded (const class loop *loop,
+ bool *read_profile_p)
+{
+ gcov_type expected = -1;
+
+ if (read_profile_p)
+ *read_profile_p = false;
+
+ sreal sreal_expected;
+ if (expected_loop_iterations_by_profile
+ (loop, &sreal_expected, read_profile_p))
+ expected = (sreal_expected + 0.5).to_int ();
else
- {
- if (by_profile_only)
- return -1;
- expected = param_avg_loop_niter;
- }
+ expected = param_avg_loop_niter;
- if (!by_profile_only)
- {
- HOST_WIDE_INT max = get_max_loop_iterations_int (loop);
- if (max != -1 && max < expected)
- return max;
- }
+ HOST_WIDE_INT max = get_max_loop_iterations_int (loop);
+ if (max != -1 && max < expected)
+ return max;
return expected;
}
@@ -31,6 +31,7 @@ along with GCC; see the file COPYING3. If not see
#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 *);
@@ -527,16 +528,16 @@ scale_loop_profile (class loop *loop, profile_probability p,
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:%f new upper bound %i:\n",
loop->num,
- (int)iterations,
+ iterations.to_double (),
(int)iteration_bound);
}
@@ -4142,11 +4142,11 @@ pass_profile::execute (function *fun)
profile_status_for_fn (fun) = PROFILE_GUESSED;
if (dump_file && (dump_flags & TDF_DETAILS))
{
+ sreal iterations;
for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
- if (loop->header->count.initialized_p ())
- fprintf (dump_file, "Loop got predicted %d to iterate %i times.\n",
- loop->num,
- (int)expected_loop_iterations_unbounded (loop));
+ if (expected_loop_iterations_by_profile (loop, &iterations))
+ fprintf (dump_file, "Loop got predicted %d to iterate %f times.\n",
+ loop->num, iterations.to_double ());
}
return 0;
}
@@ -1543,14 +1543,17 @@ branch_prob (bool thunk)
{
if (dump_file && (dump_flags & TDF_DETAILS))
report_predictor_hitrates ();
+ sreal nit;
+ bool reliable;
/* At this moment we have precise loop iteration count estimates.
Record them to loop structure before the profile gets out of date. */
for (auto loop : loops_list (cfun, 0))
- if (loop->header->count > 0 && loop->header->count.reliable_p ())
+ if (loop->header->count.ipa ().nonzero_p ()
+ && expected_loop_iterations_by_profile (loop, &nit, &reliable)
+ && reliable)
{
- gcov_type nit = expected_loop_iterations_unbounded (loop);
- widest_int bound = gcov_type_to_wide_int (nit);
+ widest_int bound = (nit + 0.5).to_int ();
loop->any_estimate = false;
record_niter_bound (loop, bound, true, false);
}
@@ -44,6 +44,7 @@ along with GCC; see the file COPYING3. If not see
#include "tree-dfa.h"
#include "internal-fn.h"
#include "gimple-range.h"
+#include "sreal.h"
/* The maximum number of dominator BBs we search for conditions
@@ -4775,6 +4776,9 @@ estimate_numbers_of_iterations (class loop *loop)
loop->estimate_state = EST_AVAILABLE;
+ sreal nit;
+ bool reliable;
+
/* If we have a measured profile, use it to estimate the number of
iterations. Normally this is recorded by branch_prob right after
reading the profile. In case we however found a new loop, record the
@@ -4787,10 +4791,10 @@ estimate_numbers_of_iterations (class loop *loop)
recomputing iteration bounds later in the compilation process will just
introduce random roundoff errors. */
if (!loop->any_estimate
- && loop->header->count.reliable_p ())
+ && expected_loop_iterations_by_profile (loop, &nit, &reliable)
+ && reliable)
{
- gcov_type nit = expected_loop_iterations_unbounded (loop);
- bound = gcov_type_to_wide_int (nit);
+ bound = (nit + 0.5).to_int ();
record_niter_bound (loop, bound, true, false);
}