Re: [PATCH 2/3] Make early return predictor more precise.
On 23 June 2017 at 09:03, Martin Liška wrote: > On 06/22/2017 04:14 PM, Christophe Lyon wrote: >> Since this commit (r249450), I have noticed a regression: >> FAIL:gcc.dg/tree-ssa/ipa-split-5.c scan-tree-dump optimized "part" >> on aarch64/arm >> >> Christophe > > Hello. > > I'm aware of the failure and I fixed that (hopefully) in r249503. > Can you please test that? > Yes, I can confirm it's now OK. Thanks > Thanks, > Martin
Re: [PATCH 2/3] Make early return predictor more precise.
On 06/22/2017 04:14 PM, Christophe Lyon wrote: > Since this commit (r249450), I have noticed a regression: > FAIL:gcc.dg/tree-ssa/ipa-split-5.c scan-tree-dump optimized "part" > on aarch64/arm > > Christophe Hello. I'm aware of the failure and I fixed that (hopefully) in r249503. Can you please test that? Thanks, Martin
Re: [PATCH 2/3] Make early return predictor more precise.
Hi,
On 21 June 2017 at 14:50, Martin Liška wrote:
> On 06/21/2017 10:26 AM, Jan Hubicka wrote:
>>>
>>> Ok, so I fixed that in the described way. There's one remaining fallout of:
>>> gcc/testsuite/gcc.dg/tree-ssa/ipa-split-5.c
>>>
>>> Where a fnsplit is properly done, but then it's again inlined:
>>>
>>> Considering split_me.part.0/5 with 23 size
>>> to be inlined into test/2 in unknown:0
>>> Estimated badness is -0.01, frequency 0.33.
>>> Inlined split_me.part.0 into test which now has time 50.30 and size
>>> 44, net change of +17.
>>>
>>> Considering split_me.part.0/5 with 23 size
>>> to be inlined into test/2 in unknown:0
>>> Estimated badness is -0.01, frequency 0.33.
>>> Inlined split_me.part.0 into test which now has time 70.76 and size
>>> 61, net change of +17.
>>>
>>> Considering split_me.part.0/5 with 23 size
>>> to be inlined into test/2 in unknown:0
>>> Estimated badness is -0.01, frequency 0.33.
>>> Inlined split_me.part.0 into test which now has time 91.22 and size
>>> 78, net change of +17.
>>>
>>> Considering split_me.part.0/5 with 23 size
>>> to be inlined into test/2 in unknown:0
>>> Estimated badness is -0.01, frequency 0.33.
>>> Inlined split_me.part.0 into test which now has time 111.68 and size
>>> 95, net change of +17.
>>> Unit growth for small function inlining: 61->129 (111%)
>>>
>>> ...
>>>
>>> Any hint how to block the IPA inlining?
>>
>> I guess you only want to make cold part of split_me bigger or
>> just use --param to reduce growth for auto inlining.
>>
>> How the patch reduces split_me_part considerably?
>> Honza
>
> Well, I probably overlooked test results, test works fine.
>
> I'm going to install the patch.
>
Since this commit (r249450), I have noticed a regression:
FAIL:gcc.dg/tree-ssa/ipa-split-5.c scan-tree-dump optimized "part"
on aarch64/arm
Christophe
> Martin
>
>>>
>>> Sending new version of patch.
>>> Martin
>>>
I would just move pass_strip_predict_hints pre-IPA and not worry about
them chaining.
There is problem that after inlining the prediction may expand its scope
and predict branch that it outside of the original function body,
but I do not see very easy solution for that besides not re-doing
prediction (we could also copy probabilities from the inlined function
when they exists and honnor them in the outer function. I am not sure
that is going to improve prediction quality though - extra context
is probably useful)
Thanks,
Honza
>
> Thanks,
> Martin
>
>>
>> Where did you found this case?
>> Honza
>>>
>>>/* Create a new deep copy of the statement. */
>>>copy = gimple_copy (stmt);
>>> --
>>> 2.13.0
>>>
>>>
>>
>>> >From 84625a782add6ae2ed29630815b61b34a052770a Mon Sep 17 00:00:00 2001
>>> From: marxin
>>> Date: Tue, 6 Jun 2017 10:55:18 +0200
>>> Subject: [PATCH 1/2] Make early return predictor more precise.
>>>
>>> gcc/ChangeLog:
>>>
>>> 2017-05-26 Martin Liska
>>>
>>> PR tree-optimization/79489
>>> * gimplify.c (maybe_add_early_return_predict_stmt): New
>>> function.
>>> (gimplify_return_expr): Call the function.
>>> * predict.c (tree_estimate_probability_bb): Remove handling
>>> of early return.
>>> * predict.def: Update comment about early return predictor.
>>> * gimple-predict.h (is_gimple_predict): New function.
>>> * predict.def: Change default value of early return to 66.
>>> * tree-tailcall.c (find_tail_calls): Skip GIMPLE_PREDICT
>>> statements.
>>> * passes.def: Put pass_strip_predict_hints to the beginning of
>>> IPA passes.
>>> ---
>>> gcc/gimple-low.c | 2 ++
>>> gcc/gimple-predict.h | 8
>>> gcc/gimplify.c | 16
>>> gcc/passes.def | 1 +
>>> gcc/predict.c| 41 -
>>> gcc/predict.def | 15 +++
>>> gcc/tree-tailcall.c | 2 ++
>>> 7 files changed, 32 insertions(+), 53 deletions(-)
>>>
>>> diff --git a/gcc/gimple-low.c b/gcc/gimple-low.c
>>> index 619b9d7bfb1..4ea6c3532f3 100644
>>> --- a/gcc/gimple-low.c
>>> +++ b/gcc/gimple-low.c
>>> @@ -30,6 +30,8 @@ along with GCC; see the file COPYING3. If not see
>>> #include "calls.h"
>>> #include "gimple-iterator.h"
>>> #include "gimple-low.h"
>>> +#include "predict.h"
>>> +#include "gimple-predict.h"
>>>
>>> /* The differences between High GIMPLE and Low GIMPLE are the
>>> following:
>>> diff --git a/gcc/gimple-predict.h b/gcc/gimple-predict.h
>>> index ba58e12e9e9..0e6c2e1ea01 100644
>>> --- a/gcc/gimple-predict.h
>>> +++ b/gcc/gimple-predict.h
>>> @@ -80,4 +80,12 @@ gimple_build_predict (enum br_predictor predictor, enum
>>> prediction outcome)
>>>return p;
>>> }
>>>
>>> +/* Return true if GS is a GIMPLE_PREDICT statement. */
>>> +
>>> +static inline bool
>>> +is_gimple_predict (const gimple *gs)
>>> +{
>>> + return g
Re: [PATCH 2/3] Make early return predictor more precise.
On 06/21/2017 10:26 AM, Jan Hubicka wrote:
>>
>> Ok, so I fixed that in the described way. There's one remaining fallout of:
>> gcc/testsuite/gcc.dg/tree-ssa/ipa-split-5.c
>>
>> Where a fnsplit is properly done, but then it's again inlined:
>>
>> Considering split_me.part.0/5 with 23 size
>> to be inlined into test/2 in unknown:0
>> Estimated badness is -0.01, frequency 0.33.
>> Inlined split_me.part.0 into test which now has time 50.30 and size 44,
>> net change of +17.
>>
>> Considering split_me.part.0/5 with 23 size
>> to be inlined into test/2 in unknown:0
>> Estimated badness is -0.01, frequency 0.33.
>> Inlined split_me.part.0 into test which now has time 70.76 and size 61,
>> net change of +17.
>>
>> Considering split_me.part.0/5 with 23 size
>> to be inlined into test/2 in unknown:0
>> Estimated badness is -0.01, frequency 0.33.
>> Inlined split_me.part.0 into test which now has time 91.22 and size 78,
>> net change of +17.
>>
>> Considering split_me.part.0/5 with 23 size
>> to be inlined into test/2 in unknown:0
>> Estimated badness is -0.01, frequency 0.33.
>> Inlined split_me.part.0 into test which now has time 111.68 and size
>> 95, net change of +17.
>> Unit growth for small function inlining: 61->129 (111%)
>>
>> ...
>>
>> Any hint how to block the IPA inlining?
>
> I guess you only want to make cold part of split_me bigger or
> just use --param to reduce growth for auto inlining.
>
> How the patch reduces split_me_part considerably?
> Honza
Well, I probably overlooked test results, test works fine.
I'm going to install the patch.
Martin
>>
>> Sending new version of patch.
>> Martin
>>
>>>
>>> I would just move pass_strip_predict_hints pre-IPA and not worry about
>>> them chaining.
>>>
>>> There is problem that after inlining the prediction may expand its scope
>>> and predict branch that it outside of the original function body,
>>> but I do not see very easy solution for that besides not re-doing
>>> prediction (we could also copy probabilities from the inlined function
>>> when they exists and honnor them in the outer function. I am not sure
>>> that is going to improve prediction quality though - extra context
>>> is probably useful)
>>>
>>> Thanks,
>>> Honza
Thanks,
Martin
>
> Where did you found this case?
> Honza
>>
>>/* Create a new deep copy of the statement. */
>>copy = gimple_copy (stmt);
>> --
>> 2.13.0
>>
>>
>
>> >From 84625a782add6ae2ed29630815b61b34a052770a Mon Sep 17 00:00:00 2001
>> From: marxin
>> Date: Tue, 6 Jun 2017 10:55:18 +0200
>> Subject: [PATCH 1/2] Make early return predictor more precise.
>>
>> gcc/ChangeLog:
>>
>> 2017-05-26 Martin Liska
>>
>> PR tree-optimization/79489
>> * gimplify.c (maybe_add_early_return_predict_stmt): New
>> function.
>> (gimplify_return_expr): Call the function.
>> * predict.c (tree_estimate_probability_bb): Remove handling
>> of early return.
>> * predict.def: Update comment about early return predictor.
>> * gimple-predict.h (is_gimple_predict): New function.
>> * predict.def: Change default value of early return to 66.
>> * tree-tailcall.c (find_tail_calls): Skip GIMPLE_PREDICT
>> statements.
>> * passes.def: Put pass_strip_predict_hints to the beginning of
>> IPA passes.
>> ---
>> gcc/gimple-low.c | 2 ++
>> gcc/gimple-predict.h | 8
>> gcc/gimplify.c | 16
>> gcc/passes.def | 1 +
>> gcc/predict.c| 41 -
>> gcc/predict.def | 15 +++
>> gcc/tree-tailcall.c | 2 ++
>> 7 files changed, 32 insertions(+), 53 deletions(-)
>>
>> diff --git a/gcc/gimple-low.c b/gcc/gimple-low.c
>> index 619b9d7bfb1..4ea6c3532f3 100644
>> --- a/gcc/gimple-low.c
>> +++ b/gcc/gimple-low.c
>> @@ -30,6 +30,8 @@ along with GCC; see the file COPYING3. If not see
>> #include "calls.h"
>> #include "gimple-iterator.h"
>> #include "gimple-low.h"
>> +#include "predict.h"
>> +#include "gimple-predict.h"
>>
>> /* The differences between High GIMPLE and Low GIMPLE are the
>> following:
>> diff --git a/gcc/gimple-predict.h b/gcc/gimple-predict.h
>> index ba58e12e9e9..0e6c2e1ea01 100644
>> --- a/gcc/gimple-predict.h
>> +++ b/gcc/gimple-predict.h
>> @@ -80,4 +80,12 @@ gimple_build_predict (enum br_predictor predictor, enum
>> prediction outcome)
>>return p;
>> }
>>
>> +/* Return true if GS is a GIMPLE_PREDICT statement. */
>> +
>> +static inline bool
>> +is_gimple_predict (const gimple *gs)
>> +{
>> + return gimple_code (gs) == GIMPLE_PREDICT;
>> +}
>> +
>> #endif /* GCC_GIMPLE_PREDICT_H */
>> diff --git a/gcc/gimplify.c b/gcc/gimplify.c
>> index 9af95a28704..1c6e1591953 100644
>> --- a/gcc/gimplify.c
>> +++ b/gcc/gimplify.c
>> @@ -1428,6 +1428,20 @@ gimplify_bind_expr (tree *expr_p, gimple_seq *pre_p)
>>return GS_ALL_DONE;
>> }
>>
>> +/* Ma
Re: [PATCH 2/3] Make early return predictor more precise.
>
> Ok, so I fixed that in the described way. There's one remaining fallout of:
> gcc/testsuite/gcc.dg/tree-ssa/ipa-split-5.c
>
> Where a fnsplit is properly done, but then it's again inlined:
>
> Considering split_me.part.0/5 with 23 size
> to be inlined into test/2 in unknown:0
> Estimated badness is -0.01, frequency 0.33.
> Inlined split_me.part.0 into test which now has time 50.30 and size 44,
> net change of +17.
>
> Considering split_me.part.0/5 with 23 size
> to be inlined into test/2 in unknown:0
> Estimated badness is -0.01, frequency 0.33.
> Inlined split_me.part.0 into test which now has time 70.76 and size 61,
> net change of +17.
>
> Considering split_me.part.0/5 with 23 size
> to be inlined into test/2 in unknown:0
> Estimated badness is -0.01, frequency 0.33.
> Inlined split_me.part.0 into test which now has time 91.22 and size 78,
> net change of +17.
>
> Considering split_me.part.0/5 with 23 size
> to be inlined into test/2 in unknown:0
> Estimated badness is -0.01, frequency 0.33.
> Inlined split_me.part.0 into test which now has time 111.68 and size 95,
> net change of +17.
> Unit growth for small function inlining: 61->129 (111%)
>
> ...
>
> Any hint how to block the IPA inlining?
I guess you only want to make cold part of split_me bigger or
just use --param to reduce growth for auto inlining.
How the patch reduces split_me_part considerably?
Honza
>
> Sending new version of patch.
> Martin
>
> >
> > I would just move pass_strip_predict_hints pre-IPA and not worry about
> > them chaining.
> >
> > There is problem that after inlining the prediction may expand its scope
> > and predict branch that it outside of the original function body,
> > but I do not see very easy solution for that besides not re-doing
> > prediction (we could also copy probabilities from the inlined function
> > when they exists and honnor them in the outer function. I am not sure
> > that is going to improve prediction quality though - extra context
> > is probably useful)
> >
> > Thanks,
> > Honza
> >>
> >> Thanks,
> >> Martin
> >>
> >>>
> >>> Where did you found this case?
> >>> Honza
>
> /* Create a new deep copy of the statement. */
> copy = gimple_copy (stmt);
> --
> 2.13.0
>
>
> >From 84625a782add6ae2ed29630815b61b34a052770a Mon Sep 17 00:00:00 2001
> From: marxin
> Date: Tue, 6 Jun 2017 10:55:18 +0200
> Subject: [PATCH 1/2] Make early return predictor more precise.
>
> gcc/ChangeLog:
>
> 2017-05-26 Martin Liska
>
> PR tree-optimization/79489
> * gimplify.c (maybe_add_early_return_predict_stmt): New
> function.
> (gimplify_return_expr): Call the function.
> * predict.c (tree_estimate_probability_bb): Remove handling
> of early return.
> * predict.def: Update comment about early return predictor.
> * gimple-predict.h (is_gimple_predict): New function.
> * predict.def: Change default value of early return to 66.
> * tree-tailcall.c (find_tail_calls): Skip GIMPLE_PREDICT
> statements.
> * passes.def: Put pass_strip_predict_hints to the beginning of
> IPA passes.
> ---
> gcc/gimple-low.c | 2 ++
> gcc/gimple-predict.h | 8
> gcc/gimplify.c | 16
> gcc/passes.def | 1 +
> gcc/predict.c| 41 -
> gcc/predict.def | 15 +++
> gcc/tree-tailcall.c | 2 ++
> 7 files changed, 32 insertions(+), 53 deletions(-)
>
> diff --git a/gcc/gimple-low.c b/gcc/gimple-low.c
> index 619b9d7bfb1..4ea6c3532f3 100644
> --- a/gcc/gimple-low.c
> +++ b/gcc/gimple-low.c
> @@ -30,6 +30,8 @@ along with GCC; see the file COPYING3. If not see
> #include "calls.h"
> #include "gimple-iterator.h"
> #include "gimple-low.h"
> +#include "predict.h"
> +#include "gimple-predict.h"
>
> /* The differences between High GIMPLE and Low GIMPLE are the
> following:
> diff --git a/gcc/gimple-predict.h b/gcc/gimple-predict.h
> index ba58e12e9e9..0e6c2e1ea01 100644
> --- a/gcc/gimple-predict.h
> +++ b/gcc/gimple-predict.h
> @@ -80,4 +80,12 @@ gimple_build_predict (enum br_predictor predictor, enum
> prediction outcome)
>return p;
> }
>
> +/* Return true if GS is a GIMPLE_PREDICT statement. */
> +
> +static inline bool
> +is_gimple_predict (const gimple *gs)
> +{
> + return gimple_code (gs) == GIMPLE_PREDICT;
> +}
> +
> #endif /* GCC_GIMPLE_PREDICT_H */
> diff --git a/gcc/gimplify.c b/gcc/gimplify.c
> index 9af95a28704..1c6e1591953 100644
> --- a/gcc/gimplify.c
> +++ b/gcc/gimplify.c
> @@ -1428,6 +1428,20 @@ gimplify_bind_expr (tree *expr_p, gimple_seq *pre_p)
>return GS_ALL_DONE;
> }
>
> +/* Maybe add early return predict statement to PRE_P sequence. */
> +
> +static void
> +maybe_add_early_return_predict_stmt (gimple_seq *pre_p)
> +{
> + /* If we are not in a conditional context, add PREDICT statement. */
> + if (gimple_con
Re: [PATCH 2/3] Make early return predictor more precise.
On 06/19/2017 01:11 PM, Jan Hubicka wrote:
>> Ok, you're right that we can preserve the predictor. However, let's consider
>> following test-case:
>>
>> static
>> int baz(int a)
>> {
>> if (a == 1)
>> return 1;
>>
>> return 0;
>> }
>>
>>
>> static
>> int bar(int a)
>> {
>> if (a == 1)
>> return baz(a);
>>
>> return 0;
>> }
>>
>> static
>> int foo(int a)
>> {
>> if (a == 1)
>> return bar(a);
>>
>> return 12;
>> }
>>
>> int main(int argc, char **argv)
>> {
>> return foo(argc);
>> }
>>
>> There after einline we have:
>>
>> main (int argc, char * * argv)
>> {
>> int D.1832;
>> int _3;
>> int _4;
>>
>>[100.00%]:
>> if (argc_2(D) == 1)
>> goto ; [37.13%]
>> else
>> goto ; [62.87%]
>>
>>[37.13%]:
>> // predicted unlikely by early return (on trees) predictor.
>> // predicted unlikely by early return (on trees) predictor.
>> // predicted unlikely by early return (on trees) predictor.
>>
>>[100.00%]:
>> # _3 = PHI <12(2), 1(3)>
>> _5 = _3;
>> _4 = _5;
>> return _4;
>>
>> }
>>
>> I'm thinking what's the best place to merge all the predictor
>> statements?
>
> I wonder if we need to - predictors are relatively short lived.
> In fact they do not need to hit IPA passes but they do as at a time
> I was implementing them I was worrying about introducing yet another
> global IPA pass to remove them (we can't do during early inlining
> because we want to reuse them after inlining).
Ok, so I fixed that in the described way. There's one remaining fallout of:
gcc/testsuite/gcc.dg/tree-ssa/ipa-split-5.c
Where a fnsplit is properly done, but then it's again inlined:
Considering split_me.part.0/5 with 23 size
to be inlined into test/2 in unknown:0
Estimated badness is -0.01, frequency 0.33.
Inlined split_me.part.0 into test which now has time 50.30 and size 44,
net change of +17.
Considering split_me.part.0/5 with 23 size
to be inlined into test/2 in unknown:0
Estimated badness is -0.01, frequency 0.33.
Inlined split_me.part.0 into test which now has time 70.76 and size 61,
net change of +17.
Considering split_me.part.0/5 with 23 size
to be inlined into test/2 in unknown:0
Estimated badness is -0.01, frequency 0.33.
Inlined split_me.part.0 into test which now has time 91.22 and size 78,
net change of +17.
Considering split_me.part.0/5 with 23 size
to be inlined into test/2 in unknown:0
Estimated badness is -0.01, frequency 0.33.
Inlined split_me.part.0 into test which now has time 111.68 and size 95,
net change of +17.
Unit growth for small function inlining: 61->129 (111%)
...
Any hint how to block the IPA inlining?
Sending new version of patch.
Martin
>
> I would just move pass_strip_predict_hints pre-IPA and not worry about
> them chaining.
>
> There is problem that after inlining the prediction may expand its scope
> and predict branch that it outside of the original function body,
> but I do not see very easy solution for that besides not re-doing
> prediction (we could also copy probabilities from the inlined function
> when they exists and honnor them in the outer function. I am not sure
> that is going to improve prediction quality though - extra context
> is probably useful)
>
> Thanks,
> Honza
>>
>> Thanks,
>> Martin
>>
>>>
>>> Where did you found this case?
>>> Honza
/* Create a new deep copy of the statement. */
copy = gimple_copy (stmt);
--
2.13.0
>From 84625a782add6ae2ed29630815b61b34a052770a Mon Sep 17 00:00:00 2001
From: marxin
Date: Tue, 6 Jun 2017 10:55:18 +0200
Subject: [PATCH 1/2] Make early return predictor more precise.
gcc/ChangeLog:
2017-05-26 Martin Liska
PR tree-optimization/79489
* gimplify.c (maybe_add_early_return_predict_stmt): New
function.
(gimplify_return_expr): Call the function.
* predict.c (tree_estimate_probability_bb): Remove handling
of early return.
* predict.def: Update comment about early return predictor.
* gimple-predict.h (is_gimple_predict): New function.
* predict.def: Change default value of early return to 66.
* tree-tailcall.c (find_tail_calls): Skip GIMPLE_PREDICT
statements.
* passes.def: Put pass_strip_predict_hints to the beginning of
IPA passes.
---
gcc/gimple-low.c | 2 ++
gcc/gimple-predict.h | 8
gcc/gimplify.c | 16
gcc/passes.def | 1 +
gcc/predict.c| 41 -
gcc/predict.def | 15 +++
gcc/tree-tailcall.c | 2 ++
7 files changed, 32 insertions(+), 53 deletions(-)
diff --git a/gcc/gimple-low.c b/gcc/gimple-low.c
index 619b9d7bfb1..4ea6c3532f3 100644
--- a/gcc/gimple-low.c
+++ b/gcc/gimple-low.c
@@ -30,6 +30,8 @@ along with GCC; see the file COPYING3. If not see
#include "calls.h"
#include "gimple-iterator.h"
#include "gimple-low.h"
+#include "predict.h"
+#include "gimple-predict.h"
/* The differences between High GIMPLE and Low GIMPLE are the
follo
Re: [PATCH 2/3] Make early return predictor more precise.
> Ok, you're right that we can preserve the predictor. However, let's consider
> following test-case:
>
> static
> int baz(int a)
> {
> if (a == 1)
> return 1;
>
> return 0;
> }
>
>
> static
> int bar(int a)
> {
> if (a == 1)
> return baz(a);
>
> return 0;
> }
>
> static
> int foo(int a)
> {
> if (a == 1)
> return bar(a);
>
> return 12;
> }
>
> int main(int argc, char **argv)
> {
> return foo(argc);
> }
>
> There after einline we have:
>
> main (int argc, char * * argv)
> {
> int D.1832;
> int _3;
> int _4;
>
>[100.00%]:
> if (argc_2(D) == 1)
> goto ; [37.13%]
> else
> goto ; [62.87%]
>
>[37.13%]:
> // predicted unlikely by early return (on trees) predictor.
> // predicted unlikely by early return (on trees) predictor.
> // predicted unlikely by early return (on trees) predictor.
>
>[100.00%]:
> # _3 = PHI <12(2), 1(3)>
> _5 = _3;
> _4 = _5;
> return _4;
>
> }
>
> I'm thinking what's the best place to merge all the predictor
> statements?
I wonder if we need to - predictors are relatively short lived.
In fact they do not need to hit IPA passes but they do as at a time
I was implementing them I was worrying about introducing yet another
global IPA pass to remove them (we can't do during early inlining
because we want to reuse them after inlining).
I would just move pass_strip_predict_hints pre-IPA and not worry about
them chaining.
There is problem that after inlining the prediction may expand its scope
and predict branch that it outside of the original function body,
but I do not see very easy solution for that besides not re-doing
prediction (we could also copy probabilities from the inlined function
when they exists and honnor them in the outer function. I am not sure
that is going to improve prediction quality though - extra context
is probably useful)
Thanks,
Honza
>
> Thanks,
> Martin
>
> >
> > Where did you found this case?
> > Honza
> >>
> >>/* Create a new deep copy of the statement. */
> >>copy = gimple_copy (stmt);
> >> --
> >> 2.13.0
> >>
Re: [PATCH 2/3] Make early return predictor more precise.
On 06/09/2017 04:08 PM, Jan Hubicka wrote:
>> gcc/ChangeLog:
>>
>> 2017-05-26 Martin Liska
>>
>> PR tree-optimization/79489
>> * gimplify.c (maybe_add_early_return_predict_stmt): New
>> function.
>> (gimplify_return_expr): Call the function.
>> * predict.c (tree_estimate_probability_bb): Remove handling
>> of early return.
>> * predict.def: Update comment about early return predictor.
>> * gimple-predict.h (is_gimple_predict): New function.
>> * tree-inline.c (remap_gimple_stmt): Do not copy early return
>> predictors during inlining.
>> * predict.def: Change default value of early return to 66.
>
> Thanks for working on this.
> Doing tail recursion early is quite useful. Can't we make the pass to
> skip predict statements in analysis similar was as debug statements are
> skipped?
Hi.
Yes, this was easy to fix, skipping here helps.
>> diff --git a/gcc/tree-inline.c b/gcc/tree-inline.c
>> index f3ec404ef09..3f3813cb062 100644
>> --- a/gcc/tree-inline.c
>> +++ b/gcc/tree-inline.c
>> @@ -1629,6 +1629,13 @@ remap_gimple_stmt (gimple *stmt, copy_body_data *id)
>>gimple_seq_add_stmt (&stmts, copy);
>>return stmts;
>> }
>> + if (is_gimple_predict (stmt))
>> +{
>> + /* Do not copy early return predictor that does not make sense
>> + after inlining. */
>> + if (gimple_predict_predictor (stmt) == PRED_TREE_EARLY_RETURN)
>> +return stmts;
>> +}
>
> I am also not quite sure about this one. The code was still structured in a
> way
> there was early return in the inlined function, so we may still assume that
> the heuristic works for it?
Ok, you're right that we can preserve the predictor. However, let's consider
following test-case:
static
int baz(int a)
{
if (a == 1)
return 1;
return 0;
}
static
int bar(int a)
{
if (a == 1)
return baz(a);
return 0;
}
static
int foo(int a)
{
if (a == 1)
return bar(a);
return 12;
}
int main(int argc, char **argv)
{
return foo(argc);
}
There after einline we have:
main (int argc, char * * argv)
{
int D.1832;
int _3;
int _4;
[100.00%]:
if (argc_2(D) == 1)
goto ; [37.13%]
else
goto ; [62.87%]
[37.13%]:
// predicted unlikely by early return (on trees) predictor.
// predicted unlikely by early return (on trees) predictor.
// predicted unlikely by early return (on trees) predictor.
[100.00%]:
# _3 = PHI <12(2), 1(3)>
_5 = _3;
_4 = _5;
return _4;
}
I'm thinking what's the best place to merge all the predictor
statements?
Thanks,
Martin
>
> Where did you found this case?
> Honza
>>
>>/* Create a new deep copy of the statement. */
>>copy = gimple_copy (stmt);
>> --
>> 2.13.0
>>
Re: [PATCH 2/3] Make early return predictor more precise.
> gcc/ChangeLog:
>
> 2017-05-26 Martin Liska
>
> PR tree-optimization/79489
> * gimplify.c (maybe_add_early_return_predict_stmt): New
> function.
> (gimplify_return_expr): Call the function.
> * predict.c (tree_estimate_probability_bb): Remove handling
> of early return.
> * predict.def: Update comment about early return predictor.
> * gimple-predict.h (is_gimple_predict): New function.
> * tree-inline.c (remap_gimple_stmt): Do not copy early return
> predictors during inlining.
> * predict.def: Change default value of early return to 66.
Thanks for working on this.
Doing tail recursion early is quite useful. Can't we make the pass to
skip predict statements in analysis similar was as debug statements are
skipped?
> diff --git a/gcc/tree-inline.c b/gcc/tree-inline.c
> index f3ec404ef09..3f3813cb062 100644
> --- a/gcc/tree-inline.c
> +++ b/gcc/tree-inline.c
> @@ -1629,6 +1629,13 @@ remap_gimple_stmt (gimple *stmt, copy_body_data *id)
> gimple_seq_add_stmt (&stmts, copy);
> return stmts;
> }
> + if (is_gimple_predict (stmt))
> + {
> + /* Do not copy early return predictor that does not make sense
> + after inlining. */
> + if (gimple_predict_predictor (stmt) == PRED_TREE_EARLY_RETURN)
> + return stmts;
> + }
I am also not quite sure about this one. The code was still structured in a way
there was early return in the inlined function, so we may still assume that
the heuristic works for it?
Where did you found this case?
Honza
>
>/* Create a new deep copy of the statement. */
>copy = gimple_copy (stmt);
> --
> 2.13.0
>
[PATCH 2/3] Make early return predictor more precise.
gcc/ChangeLog:
2017-05-26 Martin Liska
PR tree-optimization/79489
* gimplify.c (maybe_add_early_return_predict_stmt): New
function.
(gimplify_return_expr): Call the function.
* predict.c (tree_estimate_probability_bb): Remove handling
of early return.
* predict.def: Update comment about early return predictor.
* gimple-predict.h (is_gimple_predict): New function.
* tree-inline.c (remap_gimple_stmt): Do not copy early return
predictors during inlining.
* predict.def: Change default value of early return to 66.
gcc/testsuite/ChangeLog:
2017-05-31 Martin Liska
PR tree-optimization/79489
* gcc.dg/tree-ssa/tailrecursion-1.c: Change tail1 to tailr2.
* gcc.dg/tree-ssa/tailrecursion-2.c: Likewise.
* gcc.dg/tree-ssa/tailrecursion-6.c: Likewise.
---
gcc/gimple-low.c| 3 ++
gcc/gimple-predict.h| 8 +
gcc/gimplify.c | 16 ++
gcc/predict.c | 41 -
gcc/predict.def | 15 ++---
gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-1.c | 4 +--
gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-2.c | 4 +--
gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-6.c | 4 +--
gcc/tree-inline.c | 7 +
9 files changed, 43 insertions(+), 59 deletions(-)
diff --git a/gcc/gimple-low.c b/gcc/gimple-low.c
index 619b9d7bfb1..a56a7b87b88 100644
--- a/gcc/gimple-low.c
+++ b/gcc/gimple-low.c
@@ -30,6 +30,8 @@ along with GCC; see the file COPYING3. If not see
#include "calls.h"
#include "gimple-iterator.h"
#include "gimple-low.h"
+#include "predict.h"
+#include "gimple-predict.h"
/* The differences between High GIMPLE and Low GIMPLE are the
following:
@@ -684,6 +686,7 @@ lower_gimple_return (gimple_stmt_iterator *gsi, struct
lower_data *data)
/* When not optimizing, make sure user returns are preserved. */
if (!optimize && gimple_has_location (stmt))
DECL_ARTIFICIAL (tmp_rs.label) = 0;
+
t = gimple_build_goto (tmp_rs.label);
gimple_set_location (t, gimple_location (stmt));
gimple_set_block (t, gimple_block (stmt));
diff --git a/gcc/gimple-predict.h b/gcc/gimple-predict.h
index ba58e12e9e9..0e6c2e1ea01 100644
--- a/gcc/gimple-predict.h
+++ b/gcc/gimple-predict.h
@@ -80,4 +80,12 @@ gimple_build_predict (enum br_predictor predictor, enum
prediction outcome)
return p;
}
+/* Return true if GS is a GIMPLE_PREDICT statement. */
+
+static inline bool
+is_gimple_predict (const gimple *gs)
+{
+ return gimple_code (gs) == GIMPLE_PREDICT;
+}
+
#endif /* GCC_GIMPLE_PREDICT_H */
diff --git a/gcc/gimplify.c b/gcc/gimplify.c
index 2c7fc9fabd1..f192a891a8c 100644
--- a/gcc/gimplify.c
+++ b/gcc/gimplify.c
@@ -1428,6 +1428,20 @@ gimplify_bind_expr (tree *expr_p, gimple_seq *pre_p)
return GS_ALL_DONE;
}
+/* Maybe add early return predict statement to PRE_P sequence. */
+
+static void
+maybe_add_early_return_predict_stmt (gimple_seq *pre_p)
+{
+ /* If we are not in a conditional context, add PREDICT statement. */
+ if (gimple_conditional_context ())
+{
+ gimple *predict = gimple_build_predict (PRED_TREE_EARLY_RETURN,
+ NOT_TAKEN);
+ gimplify_seq_add_stmt (pre_p, predict);
+}
+}
+
/* Gimplify a RETURN_EXPR. If the expression to be returned is not a
GIMPLE value, it is assigned to a new temporary and the statement is
re-written to return the temporary.
@@ -1458,6 +1472,7 @@ gimplify_return_expr (tree stmt, gimple_seq *pre_p)
|| TREE_CODE (ret_expr) == RESULT_DECL
|| ret_expr == error_mark_node)
{
+ maybe_add_early_return_predict_stmt (pre_p);
greturn *ret = gimple_build_return (ret_expr);
gimple_set_no_warning (ret, TREE_NO_WARNING (stmt));
gimplify_seq_add_stmt (pre_p, ret);
@@ -1525,6 +1540,7 @@ gimplify_return_expr (tree stmt, gimple_seq *pre_p)
gimplify_and_add (TREE_OPERAND (stmt, 0), pre_p);
+ maybe_add_early_return_predict_stmt (pre_p);
ret = gimple_build_return (result);
gimple_set_no_warning (ret, TREE_NO_WARNING (stmt));
gimplify_seq_add_stmt (pre_p, ret);
diff --git a/gcc/predict.c b/gcc/predict.c
index ea445e94e46..d561f27342d 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -2695,7 +2695,6 @@ tree_estimate_probability_bb (basic_block bb)
{
edge e;
edge_iterator ei;
- gimple *last;
FOR_EACH_EDGE (e, ei, bb->succs)
{
@@ -2722,46 +2721,6 @@ tree_estimate_probability_bb (basic_block bb)
}
}
- /* Predict early returns to be probable, as we've already taken
-care for error returns and other cases are often used for
-fast paths through function.
-
-Since we've already removed the return statements, we are
-looking for CFG like:
-
-if (conditional)
