From: "Bin.Cheng" <amker.cheng@gmail.com>
To: Jan Hubicka <hubicka@ucw.cz>
Cc: gcc-patches List <gcc-patches@gcc.gnu.org>,
Richard Biener <rguenther@suse.de>
Subject: Re: Do not give realistic estimates for loop with array accesses
Date: Wed, 30 Mar 2016 13:50:00 -0000 [thread overview]
Message-ID: <CAHFci29MmtXa2DN29aPyfGo2aa8AKTsUk+Y3fRa1j9pwdvaFFg@mail.gmail.com> (raw)
In-Reply-To: <20160330100018.GA54780@kam.mff.cuni.cz>
On Wed, Mar 30, 2016 at 11:00 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
> Hi,
> while looking into sudoku solving benchark, I noticed that we incorrectly
> estimate loop to iterate 10 times just because the array it traverses is of
> dimension 10. This of course is just upper bound and not realistic bound.
> Realistically those loops iterates once most of time.
>
> It turns out this bug was introduced by me in
> https://gcc.gnu.org/ml/gcc-patches/2013-01/msg00444.html
> While I do not recall doing that patch, it seems like a thinko about reliable
> (name of the variable) and realistic (name of the parameter it is passed to).
>
> Fixing this caused one testsuite fallout in predictive commoning testcase
> because loop unswitching previously disabled itself having an estimated number
> of iterations 1 (I am not sure if that is not supposed to be 0, with 1
> iteration unswithcing may pay back, little bit, I suppose it wants to test
> number of stmt executions of the condtional to be at least 2 which depends on
> whether the conditional is before or after the loop exits). This made me notice
> that some loop passes that want to give up on low trip count uses combination
> of estimated number of iterations and max number of iterations while other
> don't which is fixed here. The code combining both realistic and max counts
> is same as i.e. in unroller and other passes already.
>
> I also wonder if predictive comming is a win for loops with very low
> trip count, but that is for separate patch, too, anyway.
>
> Bootstrapped/regtested x86_64-linux, OK?
>
> Honza
>
> * tree-ssa-loop-niter.c (idx_infer_loop_bounds): We can't get realistic
> estimates here.
> * tree-ssa-loop-unswitch.c (tree_unswitch_single_loop): Use also
> max_loop_iterations_int.
> * tree-ssa-loop-ivopts.c (avg_loop_niter): Likewise.
> * tree-vect-loop.c (vect_analyze_loop_2): Likewise.
> Index: tree-ssa-loop-niter.c
> ===================================================================
> --- tree-ssa-loop-niter.c (revision 234516)
> +++ tree-ssa-loop-niter.c (working copy)
> @@ -3115,7 +3115,6 @@ idx_infer_loop_bounds (tree base, tree *
> tree low, high, type, next;
> bool sign, upper = true, at_end = false;
> struct loop *loop = data->loop;
> - bool reliable = true;
>
> if (TREE_CODE (base) != ARRAY_REF)
> return true;
> @@ -3187,14 +3186,14 @@ idx_infer_loop_bounds (tree base, tree *
> && tree_int_cst_compare (next, high) <= 0)
> return true;
>
> - /* If access is not executed on every iteration, we must ensure that overlow may
> - not make the access valid later. */
> + /* If access is not executed on every iteration, we must ensure that overlow
> + may not make the access valid later. */
> if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt))
> && scev_probably_wraps_p (initial_condition_in_loop_num (ev, loop->num),
> step, data->stmt, loop, true))
> - reliable = false;
> + upper = false;
>
> - record_nonwrapping_iv (loop, init, step, data->stmt, low, high, reliable, upper);
> + record_nonwrapping_iv (loop, init, step, data->stmt, low, high, false, upper);
> return true;
> }
Hi,
I have a concern that GCC records bound information from basic blocks
even that don't dominate loop latch. Given below example:
extern int b[];
void bar (int *);
int foo (int x, int n)
{
int i;
int arr[128] = {0};
for (i = 0; i < n; i++)
{
if (x > i)
{
a[i] = i;
b[i] = i;
}
}
bar (arr);
return 0;
}
The upper bound inferred from a[i] is 127. This information is
recorded along with the stmt itself in loop->bounds. Afterwards, this
information is also used in a flow-sensitive way. In this example, we
are sure that &b[i] won't overflow (thus a SCEV) because it's in the
same basic block as a[i]. GCC currently relies on such information in
overflow detection for scev, i.e., loop_exits_before_overflow.
But with this change, we won't record upper bound information in
record_estimate because the parameter is set to false?
Thanks,
bin
next prev parent reply other threads:[~2016-03-30 13:25 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-03-30 11:02 Jan Hubicka
2016-03-30 12:09 ` Richard Biener
2016-03-30 12:36 ` Jan Hubicka
2016-03-30 12:49 ` Richard Biener
2016-03-30 18:52 ` Bernhard Reutner-Fischer
2016-04-07 14:52 ` Tom de Vries
2016-03-30 13:50 ` Bin.Cheng [this message]
2016-03-30 14:41 ` Jan Hubicka
2016-03-30 15:30 ` Bin.Cheng
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=CAHFci29MmtXa2DN29aPyfGo2aa8AKTsUk+Y3fRa1j9pwdvaFFg@mail.gmail.com \
--to=amker.cheng@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=hubicka@ucw.cz \
--cc=rguenther@suse.de \
/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).