From: "Bin.Cheng" <amker.cheng@gmail.com>
To: Jan Hubicka <hubicka@ucw.cz>
Cc: Richard Biener <richard.guenther@gmail.com>,
"gcc-patches@gcc.gnu.org" <gcc-patches@gcc.gnu.org>,
"pthaugen@linux.vnet.ibm.com" <pthaugen@linux.vnet.ibm.com>
Subject: Re: [PATCH PR77536]Generate correct profiling information for vectorized loop
Date: Tue, 21 Feb 2017 14:48:00 -0000 [thread overview]
Message-ID: <CAHFci2_Kc2YaMLPQwzsobHYVrY-LjvNwEo49ZkzpjGdgtm=5wg@mail.gmail.com> (raw)
In-Reply-To: <20170220160509.GA2669@kam.mff.cuni.cz>
[-- Attachment #1: Type: text/plain, Size: 5590 bytes --]
On Mon, Feb 20, 2017 at 4:05 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> BTW, if we use gcov_type in calculation from expected_loop_iterations_unbounded,
>> how should we adjust the number for calling scale_loop_frequencies
>> which has int type? In extreme case, gcov_type could be out of int's
>> range, we have to cap the value anyway. But yes, 10000 in
>> expect_loop_iterations is too small.
>
> What I usually do is to use fixed point math in this case (based on REG_BR_PROB_BASE).
> Just pass REG_BR_PROB_BASE as den and calculate the adjustment in gcov_type converting
> to int. Because you should be just decreasing the counts, it won't overflow and because
> the decarese will be in range, say 2...256 times, it should also be sufficiently
> precise.
>
> Be careful to avoid overflow of gcov type - it is not safe to multiply two
> counts in 64bit math because each count can be more than 2^32. (next stage1 I
> plan to switch most of this to sreals that will make this easier)
>
>> >> > But I guess here it is sort of safe because vectorized loops are simple.
>> >> > You can't just scale down the existing counts/frequencies by vf, because the
>> >> > entry edge frequency was adjusted.
>> >> I am not 100% follow here, it looks the code avoids changing frequency
>> >> counter for preheader/exit edge, otherwise we would need to change all
>> >> counters dominated by them?
>> >
>> > I was just wondering what is wrong with taking the existing frequencies/counts
>> > the loop body has and dividing them all by the unroll factor. This is correct
>> > if you ignore the versioning. With versioning I guess you want to scale by
>> > the unroll factor and also subtract frequencies/counts that was acocunted to
>> > the other versions of the loop, right?
>> IIUC, for (vectorized) loop header, it's frequency is calculated by:
>> freq_header = freq_preheader + freq_latch
>> and freq_latch = (niter * freq_preheader). Simply scaling it by VF gives:
>> freq_header = (freq_preheader + freq_latch) / VF
>> which is wrong. Especially if the loop is vectorized by large VF
>> (=16) and we normally assume niter (=10) without profiling
>> information, it results not only mismatch, but also
>> (loop->header->frequency < loop->preheader->frequency). In fact, if
>> we have accurate niter information, the counter should be:
>> freq_header = freq_preheader + niter * freq_preheader
>
> You are right. We need to compensate for the change of probability of the loop
> exit edge.
>>
>> >> >
>> >> > Also niter_for_unrolled_loop depends on sanity of the profile, so perhaps you
>> >> > need to compute it before you start chanigng the CFG by peeling proplogue?
>> >> Peeling for prologue doesn't change profiling information of
>> >> vect_loop, it is the skip edge from before loop to preferred epilogue
>> >> loop that will change profile counters. I guess here exists a dilemma
>> >> that niter_for_unrolled_loop is for loop after peeling for prologue?
>> >
>> > expected_loop_iterations_unbounded calculates number of iteations by computing
>> > sum of frequencies of edges entering the loop and comparing it to the frequency
>> > of loop header. While peeling the prologue, you split the preheader edge and
>> > adjust frequency of the new preheader BB of the loop to be vectorized. I think
>> > that will adjust the #of iterations estimate.
>> It's not the case now I think. one motivation of new vect_do_peeling
>> is to avoid niter checks between prologue and vector loop. Once
>> prologue loop is entered or checked, the vector loop must be executed
>> unconditionally. So the preheaderof vector loop has consistent
>> frequency counters now. The niter check on whether vector loop should
>> be executed is now merged with cost check before prologue, and in the
>> future I think this can be further merged if loop versioning is
>> needed.
>
> Originally you have
>
> loop_preheader
> |
> v
> loop_header
>
> and the ratio of the two BB frequencies is the loop iteration count. Then you
> do something like:
>
> orig_loop_preheader
> |
> v
> loop_prologue -----> scalar_version_of_loop
> |
> v
> new_loop_preheader
> |
> v
> loop_header
>
> At some point, you need to update new_loop_preheader frequency/count
> to reflect the fact that with some probability the loop_prologue avoids
> the vectorized loop. Once you do it and if you don't scale frequency of
> loop_header you will make expect_loop_iterations to return higher value
> than previously.
>
> So at the time you are calling it, you need to be sure that the loop_header
> and its preheader frequences was both adjusted by same factor. Or you need
> to call it early before you start hacking on the CFG and its profile.
>
> Pehaps currently it is safe, because your peeling code is also scaling
> the loop profiles.
Hi Honza,
Attachment is the updated patch. Bootstrap and test ongoing, any comments?
Thanks,
bin
2017-02-21 Bin Cheng <bin.cheng@arm.com>
PR tree-optimization/77536
* tree-ssa-loop-manip.c (niter_for_unrolled_loop): New function.
(tree_transform_and_unroll_loop): Use above function to compute the
estimated niter of unrolled loop and use it when scaling profile.
* tree-ssa-loop-manip.h niter_for_unrolled_loop(): New declaration.
* tree-vect-loop.c (scale_profile_for_vect_loop): New function.
(vect_transform_loop): Call above function.
gcc/testsuite/ChangeLog
2017-02-21 Bin Cheng <bin.cheng@arm.com>
PR tree-optimization/77536
* gcc.dg/vect/pr79347.c: Revise testing string.
[-- Attachment #2: pr77536-20170217.txt --]
[-- Type: text/plain, Size: 7646 bytes --]
diff --git a/gcc/testsuite/gcc.dg/vect/pr79347.c b/gcc/testsuite/gcc.dg/vect/pr79347.c
index 586c638..6825420 100644
--- a/gcc/testsuite/gcc.dg/vect/pr79347.c
+++ b/gcc/testsuite/gcc.dg/vect/pr79347.c
@@ -10,4 +10,4 @@ void n(void)
a[i]++;
}
-/* { dg-final { scan-tree-dump-times "Invalid sum of " 2 "vect" } } */
+/* { dg-final { scan-tree-dump-not "Invalid sum of " "vect" } } */
diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
index 43df29c..cf2cd48 100644
--- a/gcc/tree-ssa-loop-manip.c
+++ b/gcc/tree-ssa-loop-manip.c
@@ -1093,6 +1093,33 @@ scale_dominated_blocks_in_loop (struct loop *loop, basic_block bb,
}
}
+/* Return estimated niter for LOOP after unrolling by FACTOR times. */
+
+gcov_type
+niter_for_unrolled_loop (struct loop *loop, unsigned factor)
+{
+ gcc_assert (factor != 0);
+ bool profile_p = false;
+ gcov_type est_niter = expected_loop_iterations_unbounded (loop, &profile_p);
+ gcov_type new_est_niter = est_niter / factor;
+
+ /* Without profile feedback, loops for which we do not know a better estimate
+ are assumed to roll 10 times. When we unroll such loop, it appears to
+ roll too little, and it may even seem to be cold. To avoid this, we
+ ensure that the created loop appears to roll at least 5 times (but at
+ most as many times as before unrolling). Don't do adjustment if profile
+ feedback is present. */
+ if (new_est_niter < 5 && !profile_p)
+ {
+ if (est_niter < 5)
+ new_est_niter = est_niter;
+ else
+ new_est_niter = 5;
+ }
+
+ return new_est_niter;
+}
+
/* Unroll LOOP FACTOR times. DESC describes number of iterations of LOOP.
EXIT is the exit of the loop to that DESC corresponds.
@@ -1170,12 +1197,11 @@ tree_transform_and_unroll_loop (struct loop *loop, unsigned factor,
gimple_stmt_iterator bsi;
use_operand_p op;
bool ok;
- unsigned est_niter, prob_entry, scale_unrolled, scale_rest, freq_e, freq_h;
- unsigned new_est_niter, i, prob;
+ unsigned i, prob, prob_entry, scale_unrolled, scale_rest, freq_e, freq_h;
+ gcov_type new_est_niter = niter_for_unrolled_loop (loop, factor);
unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
auto_vec<edge> to_remove;
- est_niter = expected_loop_iterations (loop);
determine_exit_conditions (loop, desc, factor,
&enter_main_cond, &exit_base, &exit_step,
&exit_cmp, &exit_bound);
@@ -1207,22 +1233,6 @@ tree_transform_and_unroll_loop (struct loop *loop, unsigned factor,
gcc_assert (new_loop != NULL);
update_ssa (TODO_update_ssa);
- /* Determine the probability of the exit edge of the unrolled loop. */
- new_est_niter = est_niter / factor;
-
- /* Without profile feedback, loops for that we do not know a better estimate
- are assumed to roll 10 times. When we unroll such loop, it appears to
- roll too little, and it may even seem to be cold. To avoid this, we
- ensure that the created loop appears to roll at least 5 times (but at
- most as many times as before unrolling). */
- if (new_est_niter < 5)
- {
- if (est_niter < 5)
- new_est_niter = est_niter;
- else
- new_est_niter = 5;
- }
-
/* Prepare the cfg and update the phi nodes. Move the loop exit to the
loop latch (and make its condition dummy, for the moment). */
rest = loop_preheader_edge (new_loop)->src;
@@ -1329,7 +1339,12 @@ tree_transform_and_unroll_loop (struct loop *loop, unsigned factor,
freq_h = loop->header->frequency;
freq_e = EDGE_FREQUENCY (loop_preheader_edge (loop));
if (freq_h != 0)
- scale_loop_frequencies (loop, freq_e * (new_est_niter + 1), freq_h);
+ {
+ gcov_type scale;
+ /* This should not overflow. */
+ scale = GCOV_COMPUTE_SCALE (freq_e * (new_est_niter + 1), freq_h);
+ scale_loop_frequencies (loop, scale, REG_BR_PROB_BASE);
+ }
exit_bb = single_pred (loop->latch);
new_exit = find_edge (exit_bb, rest);
diff --git a/gcc/tree-ssa-loop-manip.h b/gcc/tree-ssa-loop-manip.h
index 1e7531f..a139050 100644
--- a/gcc/tree-ssa-loop-manip.h
+++ b/gcc/tree-ssa-loop-manip.h
@@ -48,6 +48,7 @@ extern bool gimple_duplicate_loop_to_header_edge (struct loop *, edge,
int);
extern bool can_unroll_loop_p (struct loop *loop, unsigned factor,
struct tree_niter_desc *niter);
+extern gcov_type niter_for_unrolled_loop (struct loop *, unsigned);
extern void tree_transform_and_unroll_loop (struct loop *, unsigned,
edge, struct tree_niter_desc *,
transform_callback, void *);
diff --git a/gcc/tree-vect-loop.c b/gcc/tree-vect-loop.c
index c5a1627..2ca03c5 100644
--- a/gcc/tree-vect-loop.c
+++ b/gcc/tree-vect-loop.c
@@ -6718,6 +6718,48 @@ loop_niters_no_overflow (loop_vec_info loop_vinfo)
return false;
}
+/* Scale profiling counters by estimation for LOOP which is vectorized
+ by factor VF. */
+
+static void
+scale_profile_for_vect_loop (struct loop *loop, unsigned vf)
+{
+ edge preheader = loop_preheader_edge (loop);
+ unsigned freq_h = loop->header->frequency;
+ unsigned freq_e = EDGE_FREQUENCY (preheader);
+ /* Reduce loop iterations by the vectorization factor. */
+ gcov_type new_est_niter = niter_for_unrolled_loop (loop, vf);
+
+ /* Use profiling count information if frequencies are zero. */
+ if (freq_h == 0 || freq_e == 0)
+ {
+ freq_e = preheader->count;
+ freq_h = loop->header->count;
+ }
+
+ if (freq_h != 0)
+ {
+ gcov_type scale;
+ /* This should not overflow. */
+ scale = GCOV_COMPUTE_SCALE (freq_e * (new_est_niter + 1), freq_h);
+ scale_loop_frequencies (loop, scale, REG_BR_PROB_BASE);
+ }
+
+ basic_block exit_bb = single_pred (loop->latch);
+ edge exit_e = single_exit (loop);
+ exit_e->count = loop_preheader_edge (loop)->count;
+ exit_e->probability = REG_BR_PROB_BASE / (new_est_niter + 1);
+
+ edge exit_l = single_pred_edge (loop->latch);
+ int prob = exit_l->probability;
+ exit_l->probability = REG_BR_PROB_BASE - exit_e->probability;
+ exit_l->count = exit_bb->count - exit_e->count;
+ if (exit_l->count < 0)
+ exit_l->count = 0;
+ if (prob > 0)
+ scale_bbs_frequencies_int (&loop->latch, 1, exit_l->probability, prob);
+}
+
/* Function vect_transform_loop.
The analysis phase has determined that the loop is vectorizable.
@@ -6743,16 +6785,10 @@ vect_transform_loop (loop_vec_info loop_vinfo)
bool transform_pattern_stmt = false;
bool check_profitability = false;
int th;
- /* Record number of iterations before we started tampering with the profile. */
- gcov_type expected_iterations = expected_loop_iterations_unbounded (loop);
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location, "=== vec_transform_loop ===\n");
- /* If profile is inprecise, we have chance to fix it up. */
- if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
- expected_iterations = LOOP_VINFO_INT_NITERS (loop_vinfo);
-
/* Use the more conservative vectorization threshold. If the number
of iterations is constant assume the cost check has been performed
by our caller. If the threshold makes all loops profitable that
@@ -7068,9 +7104,8 @@ vect_transform_loop (loop_vec_info loop_vinfo)
slpeel_make_loop_iterate_ntimes (loop, niters_vector);
- /* Reduce loop iterations by the vectorization factor. */
- scale_loop_profile (loop, GCOV_COMPUTE_SCALE (1, vf),
- expected_iterations / vf);
+ scale_profile_for_vect_loop (loop, vf);
+
/* The minimum number of iterations performed by the epilogue. This
is 1 when peeling for gaps because we always need a final scalar
iteration. */
next prev parent reply other threads:[~2017-02-21 14:47 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-02-16 18:38 Bin Cheng
2017-02-17 1:39 ` Pat Haugen
2017-02-20 12:54 ` Richard Biener
2017-02-20 14:21 ` Jan Hubicka
2017-02-20 15:16 ` Bin.Cheng
2017-02-20 15:44 ` Jan Hubicka
2017-02-20 16:05 ` Bin.Cheng
2017-02-20 17:02 ` Jan Hubicka
2017-02-20 17:53 ` Bin.Cheng
2017-02-21 14:48 ` Bin.Cheng [this message]
2017-02-21 15:52 ` Jan Hubicka
2017-02-22 12:23 ` Bin.Cheng
2017-02-22 14:59 ` Jan Hubicka
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='CAHFci2_Kc2YaMLPQwzsobHYVrY-LjvNwEo49ZkzpjGdgtm=5wg@mail.gmail.com' \
--to=amker.cheng@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=hubicka@ucw.cz \
--cc=pthaugen@linux.vnet.ibm.com \
--cc=richard.guenther@gmail.com \
/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: link
Be 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).