Re: [PATCH] Add malloc predictor (PR middle-end/83023).
On 08/07/2018 01:51 PM, Jan Hubicka wrote:
>>
>> 2018-07-26 Martin Liska
>>
>> PR middle-end/83023
>> * predict.c (expr_expected_value_1): Handle DECL_IS_MALLOC,
>> BUILT_IN_REALLOC and DECL_IS_OPERATOR_NEW.
>> * predict.def (PRED_MALLOC_NONNULL): New predictor.
>
> Patch is OK. I am still somewhat worried that we will run into functions that
> do return NULL in most times and otherwise they return newly mallocated block.
Thanks.
>
> For this reason please simply document the behaviour in extend.texi.
> For auto-detected malloc attribute I guess we may invent extra flag about
> probability of NULL return value later if we run into interesting testcases.
I documented that and installed patch as r263355.
Martin
>
> I think it is a mistake that we don't detect malloc attribute early. It has
> good chance of making the simplifications in early opts to cascade. I will
> look into this.
>
> Honza
>>
>> gcc/testsuite/ChangeLog:
>>
>> 2018-07-26 Martin Liska
>>
>> PR middle-end/83023
>> * gcc.dg/predict-16.c: New test.
>> * g++.dg/predict-1.C: New test.
>> ---
>> gcc/predict.c | 12 +++
>> gcc/predict.def | 5 -
>> gcc/testsuite/g++.dg/predict-1.C | 15 +
>> gcc/testsuite/gcc.dg/predict-16.c | 36 +++
>> 4 files changed, 67 insertions(+), 1 deletion(-)
>> create mode 100644 gcc/testsuite/g++.dg/predict-1.C
>> create mode 100644 gcc/testsuite/gcc.dg/predict-16.c
>>
>> diff --git a/gcc/predict.c b/gcc/predict.c
>> index 2ee8274fe61..ef6794edda5 100644
>> --- a/gcc/predict.c
>> +++ b/gcc/predict.c
>> @@ -2380,6 +2380,14 @@ expr_expected_value_1 (tree type, tree op0, enum
>> tree_code code,
>> }
>>return NULL;
>> }
>> +
>> + if (DECL_IS_MALLOC (decl) || DECL_IS_OPERATOR_NEW (decl))
>> +{
>> + if (predictor)
>> +*predictor = PRED_MALLOC_NONNULL;
>> + return boolean_true_node;
>> +}
>> +
>>if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
>> switch (DECL_FUNCTION_CODE (decl))
>>{
>> @@ -2420,6 +2428,10 @@ expr_expected_value_1 (tree type, tree op0, enum
>> tree_code code,
>> if (predictor)
>>*predictor = PRED_COMPARE_AND_SWAP;
>> return boolean_true_node;
>> + case BUILT_IN_REALLOC:
>> +if (predictor)
>> + *predictor = PRED_MALLOC_NONNULL;
>> +return boolean_true_node;
>>default:
>> break;
>> }
>> diff --git a/gcc/predict.def b/gcc/predict.def
>> index 03900bf89b3..bf659704bfc 100644
>> --- a/gcc/predict.def
>> +++ b/gcc/predict.def
>> @@ -55,6 +55,10 @@ DEF_PREDICTOR (PRED_UNCONDITIONAL, "unconditional jump",
>> PROB_ALWAYS,
>> DEF_PREDICTOR (PRED_BUILTIN_UNPREDICTABLE, "__builtin_unpredictable",
>> PROB_EVEN,
>>PRED_FLAG_FIRST_MATCH)
>>
>> +/* Return value of malloc function is almost always non-null. */
>> +DEF_PREDICTOR (PRED_MALLOC_NONNULL, "malloc returned non-NULL", \
>> + PROB_VERY_LIKELY, PRED_FLAG_FIRST_MATCH)
>> +
>> /* Use number of loop iterations determined by # of iterations
>> analysis to set probability. We don't want to use Dempster-Shaffer
>> theory here, as the predictions is exact. */
>> @@ -173,7 +177,6 @@ DEF_PREDICTOR (PRED_HOT_LABEL, "hot label", HITRATE
>> (85), 0)
>> DEF_PREDICTOR (PRED_COLD_LABEL, "cold label", PROB_VERY_LIKELY,
>> PRED_FLAG_FIRST_MATCH)
>>
>> -
>> /* The following predictors are used in Fortran. */
>>
>> /* Branch leading to an integer overflow are extremely unlikely. */
>> diff --git a/gcc/testsuite/g++.dg/predict-1.C
>> b/gcc/testsuite/g++.dg/predict-1.C
>> new file mode 100644
>> index 000..8e2032f33a4
>> --- /dev/null
>> +++ b/gcc/testsuite/g++.dg/predict-1.C
>> @@ -0,0 +1,15 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
>> +
>> +#include
>> +
>> +int *r;
>> +
>> +void test()
>> +{
>> + r = new(std::nothrow) int;
>> + if (r)
>> +__builtin_memset (r, 0, sizeof(int));
>> +}
>> +
>> +/* { dg-final { scan-tree-dump "malloc returned non-NULL heuristics of
>> edge\[^:\]*: 99.96%" "profile_estimate"} } */
>> diff --git a/gcc/testsuite/gcc.dg/predict-16.c
>> b/gcc/testsuite/gcc.dg/predict-16.c
>> new file mode 100644
>> index 000..e1f331b909a
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/predict-16.c
>> @@ -0,0 +1,36 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
>> +
>> +#include
>> +#include
>> +
>> +void *r;
>> +void *r2;
>> +void *r3;
>> +void *r4;
>> +void *r5;
>> +
>> +void *m (size_t s, int c)
>> +{
>> + r = malloc (s);
>> + if (r)
>> +memset (r, 0, s);
>> +
>> + r2 = calloc (s, 0);
>> + if (r2)
>> +memset (r2, 0, s);
>> +
>> + r3 = __builtin_malloc (s);
>> + if (r3)
>> +memset (r3, 0,
Re: [PATCH] Add malloc predictor (PR middle-end/83023).
>
> 2018-07-26 Martin Liska
>
> PR middle-end/83023
> * predict.c (expr_expected_value_1): Handle DECL_IS_MALLOC,
> BUILT_IN_REALLOC and DECL_IS_OPERATOR_NEW.
> * predict.def (PRED_MALLOC_NONNULL): New predictor.
Patch is OK. I am still somewhat worried that we will run into functions that
do return NULL in most times and otherwise they return newly mallocated block.
For this reason please simply document the behaviour in extend.texi.
For auto-detected malloc attribute I guess we may invent extra flag about
probability of NULL return value later if we run into interesting testcases.
I think it is a mistake that we don't detect malloc attribute early. It has
good chance of making the simplifications in early opts to cascade. I will
look into this.
Honza
>
> gcc/testsuite/ChangeLog:
>
> 2018-07-26 Martin Liska
>
> PR middle-end/83023
> * gcc.dg/predict-16.c: New test.
> * g++.dg/predict-1.C: New test.
> ---
> gcc/predict.c | 12 +++
> gcc/predict.def | 5 -
> gcc/testsuite/g++.dg/predict-1.C | 15 +
> gcc/testsuite/gcc.dg/predict-16.c | 36 +++
> 4 files changed, 67 insertions(+), 1 deletion(-)
> create mode 100644 gcc/testsuite/g++.dg/predict-1.C
> create mode 100644 gcc/testsuite/gcc.dg/predict-16.c
>
> diff --git a/gcc/predict.c b/gcc/predict.c
> index 2ee8274fe61..ef6794edda5 100644
> --- a/gcc/predict.c
> +++ b/gcc/predict.c
> @@ -2380,6 +2380,14 @@ expr_expected_value_1 (tree type, tree op0, enum
> tree_code code,
> }
> return NULL;
> }
> +
> + if (DECL_IS_MALLOC (decl) || DECL_IS_OPERATOR_NEW (decl))
> + {
> + if (predictor)
> + *predictor = PRED_MALLOC_NONNULL;
> + return boolean_true_node;
> + }
> +
> if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
> switch (DECL_FUNCTION_CODE (decl))
> {
> @@ -2420,6 +2428,10 @@ expr_expected_value_1 (tree type, tree op0, enum
> tree_code code,
> if (predictor)
> *predictor = PRED_COMPARE_AND_SWAP;
> return boolean_true_node;
> + case BUILT_IN_REALLOC:
> + if (predictor)
> + *predictor = PRED_MALLOC_NONNULL;
> + return boolean_true_node;
> default:
> break;
> }
> diff --git a/gcc/predict.def b/gcc/predict.def
> index 03900bf89b3..bf659704bfc 100644
> --- a/gcc/predict.def
> +++ b/gcc/predict.def
> @@ -55,6 +55,10 @@ DEF_PREDICTOR (PRED_UNCONDITIONAL, "unconditional jump",
> PROB_ALWAYS,
> DEF_PREDICTOR (PRED_BUILTIN_UNPREDICTABLE, "__builtin_unpredictable",
> PROB_EVEN,
>PRED_FLAG_FIRST_MATCH)
>
> +/* Return value of malloc function is almost always non-null. */
> +DEF_PREDICTOR (PRED_MALLOC_NONNULL, "malloc returned non-NULL", \
> +PROB_VERY_LIKELY, PRED_FLAG_FIRST_MATCH)
> +
> /* Use number of loop iterations determined by # of iterations
> analysis to set probability. We don't want to use Dempster-Shaffer
> theory here, as the predictions is exact. */
> @@ -173,7 +177,6 @@ DEF_PREDICTOR (PRED_HOT_LABEL, "hot label", HITRATE (85),
> 0)
> DEF_PREDICTOR (PRED_COLD_LABEL, "cold label", PROB_VERY_LIKELY,
> PRED_FLAG_FIRST_MATCH)
>
> -
> /* The following predictors are used in Fortran. */
>
> /* Branch leading to an integer overflow are extremely unlikely. */
> diff --git a/gcc/testsuite/g++.dg/predict-1.C
> b/gcc/testsuite/g++.dg/predict-1.C
> new file mode 100644
> index 000..8e2032f33a4
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/predict-1.C
> @@ -0,0 +1,15 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
> +
> +#include
> +
> +int *r;
> +
> +void test()
> +{
> + r = new(std::nothrow) int;
> + if (r)
> +__builtin_memset (r, 0, sizeof(int));
> +}
> +
> +/* { dg-final { scan-tree-dump "malloc returned non-NULL heuristics of
> edge\[^:\]*: 99.96%" "profile_estimate"} } */
> diff --git a/gcc/testsuite/gcc.dg/predict-16.c
> b/gcc/testsuite/gcc.dg/predict-16.c
> new file mode 100644
> index 000..e1f331b909a
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/predict-16.c
> @@ -0,0 +1,36 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
> +
> +#include
> +#include
> +
> +void *r;
> +void *r2;
> +void *r3;
> +void *r4;
> +void *r5;
> +
> +void *m (size_t s, int c)
> +{
> + r = malloc (s);
> + if (r)
> +memset (r, 0, s);
> +
> + r2 = calloc (s, 0);
> + if (r2)
> +memset (r2, 0, s);
> +
> + r3 = __builtin_malloc (s);
> + if (r3)
> +memset (r3, 0, s);
> +
> + r4 = __builtin_calloc (s, 0);
> + if (r4)
> +memset (r4, 0, s);
> +
> + r5 = __builtin_realloc (r4, s);
> + if (r5)
> +memset (r4, 0, s);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "malloc returned non-NULL
Re: [PATCH] Add malloc predictor (PR middle-end/83023).
On 08/01/2018 05:04 PM, Marc Glisse wrote:
> On Wed, 1 Aug 2018, Martin Liška wrote:
>
>> On 08/01/2018 02:25 PM, Marc Glisse wrote:
>>> On Wed, 1 Aug 2018, Martin Liška wrote:
>>>
On 07/27/2018 02:38 PM, Marc Glisse wrote:
> On Fri, 27 Jul 2018, Martin Liška wrote:
>
>> So answer is yes, the builtin can be then removed.
>
> Good, thanks. While looking at how widely it is going to apply, I noticed
> that the default, throwing operator new has attribute malloc and
> everything, but the non-throwing variant declared in doesn't, so it
> won't benefit from the new predictor. I don't know if there is a good
> reason for this disparity...
>
Well in case somebody uses operator new:
int* p1 = new int;
if (p1)
delete p1;
we optimize out that to if (true), even when one has used defined
operator new. Thus it's probably OK.
>>>
>>> Throwing new is returns_nonnull (errors are reported with exceptions) so
>>> that's fine, but non-throwing new is not:
>>>
>>> int* p1 = new(std::nothrow) int;
>>>
>>> Here errors are reported by returning 0, so it is common to test if p1 is 0
>>> and this is precisely the case that could benefit from a predictor but does
>>> not have the attribute to do so (there are also consequences on aliasing).
>>
>> Then it can be handled with DECL_IS_OPERATOR_NEW, for those we can also set
>> the newly introduced predictor.
>
> Independently of whether you extend the predictor to DECL_IS_OPERATOR_NEW, it
> would be good for this nothrow operator new to get the aliasing benefits of
> attribute malloc. I'll open a PR.
>
>>> (Jan's remark about functions with an inferred malloc attribute reminds me
>>> that at some point, the code was adding attribute malloc for functions that
>>> always return 0...)
>>
>> By inferred do you mean function that are marked as malloc in IPA pure-const
>> (propagate_malloc)?
>
> Yes.
>
>> Example would be appreciated.
>
> I used the past tense, I am not claiming this still happens.
>
Ok, so I'm sending updated version of the patch including DECL_IS_OPERATOR_NEW
operator.
In SPEC2006 it's seen 1021 times. There are some statistics about frequency of
individual
benchmarks:
400.perlbench: 4
401.bzip2: 4
403.gcc: 13
410.bwaves: 0
416.gamess: 0
429.mcf: 4
433.milc: 23
434.zeusmp: 0
435.gromacs: 13
436.cactusADM: 221
437.leslie3d: 84
444.namd: 1
445.gobmk: 15
447.dealII: 52
450.soplex: 87
453.povray: 20
454.calculix: 102
456.hmmer: 40
458.sjeng: 4
459.GemsFDTD: 0
462.libquantum: 19
464.h264ref: 166
465.tonto: 55
470.lbm: 1
471.omnetpp: 3
473.astar: 0
481.wrf: 47
482.sphinx3: 21
483.xalancbmk: 22
Ready for trunk?
Martin
>From 8689ac0907c27709d81f72782eaa5a3a752a2991 Mon Sep 17 00:00:00 2001
From: marxin
Date: Thu, 26 Jul 2018 15:25:00 +0200
Subject: [PATCH] Add malloc predictor (PR middle-end/83023).
gcc/ChangeLog:
2018-07-26 Martin Liska
PR middle-end/83023
* predict.c (expr_expected_value_1): Handle DECL_IS_MALLOC,
BUILT_IN_REALLOC and DECL_IS_OPERATOR_NEW.
* predict.def (PRED_MALLOC_NONNULL): New predictor.
gcc/testsuite/ChangeLog:
2018-07-26 Martin Liska
PR middle-end/83023
* gcc.dg/predict-16.c: New test.
* g++.dg/predict-1.C: New test.
---
gcc/predict.c | 12 +++
gcc/predict.def | 5 -
gcc/testsuite/g++.dg/predict-1.C | 15 +
gcc/testsuite/gcc.dg/predict-16.c | 36 +++
4 files changed, 67 insertions(+), 1 deletion(-)
create mode 100644 gcc/testsuite/g++.dg/predict-1.C
create mode 100644 gcc/testsuite/gcc.dg/predict-16.c
diff --git a/gcc/predict.c b/gcc/predict.c
index 2ee8274fe61..ef6794edda5 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -2380,6 +2380,14 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
}
return NULL;
}
+
+ if (DECL_IS_MALLOC (decl) || DECL_IS_OPERATOR_NEW (decl))
+ {
+ if (predictor)
+ *predictor = PRED_MALLOC_NONNULL;
+ return boolean_true_node;
+ }
+
if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
switch (DECL_FUNCTION_CODE (decl))
{
@@ -2420,6 +2428,10 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
if (predictor)
*predictor = PRED_COMPARE_AND_SWAP;
return boolean_true_node;
+ case BUILT_IN_REALLOC:
+ if (predictor)
+ *predictor = PRED_MALLOC_NONNULL;
+ return boolean_true_node;
default:
break;
}
diff --git a/gcc/predict.def b/gcc/predict.def
index 03900bf89b3..bf659704bfc 100644
--- a/gcc/predict.def
+++ b/gcc/predict.def
@@ -55,6 +55,10 @@ DEF_PREDICTOR (PRED_UNCONDITIONAL, "unconditional jump", PROB_ALWAYS,
DEF_PREDICTOR (PRED_BUILTIN_UNPREDICTABLE, "__builtin_unpredictable", PROB_EVEN,
PRED_FLAG_FIRST_MATCH)
+/* Return value of malloc function is almost always non-null. */
+DEF_PREDICTOR (PRED_MALLOC_NONNULL, "malloc returned
Re: [PATCH] Add malloc predictor (PR middle-end/83023).
On 08/01/2018 05:25 AM, Marc Glisse wrote: Throwing new is returns_nonnull (errors are reported with exceptions) so that's fine, but non-throwing new is not: int* p1 = new(std::nothrow) int; Here errors are reported by returning 0, so it is common to test if p1 is 0 and this is precisely the case that could benefit from a predictor but does not have the attribute to do so (there are also consequences on aliasing). Agreed. both throwing and non-throwing operator new are malloc-like. Placement new doesn't throw, it is explicitly defined to return the passed in pointer (and it's not replaceable by the user). So may return null, but I don't think any code (outside of a conformance testsuite) would actually do that. I can't find words that specify the return value of any allocation function is unaliased to any existing object. The closest it gets is that the non-placement forms might be implemented via malloc and friends. nathan -- Nathan Sidwell
Re: [PATCH] Add malloc predictor (PR middle-end/83023).
On Wed, 1 Aug 2018, Martin Liška wrote: On 08/01/2018 02:25 PM, Marc Glisse wrote: On Wed, 1 Aug 2018, Martin Liška wrote: On 07/27/2018 02:38 PM, Marc Glisse wrote: On Fri, 27 Jul 2018, Martin Liška wrote: So answer is yes, the builtin can be then removed. Good, thanks. While looking at how widely it is going to apply, I noticed that the default, throwing operator new has attribute malloc and everything, but the non-throwing variant declared in doesn't, so it won't benefit from the new predictor. I don't know if there is a good reason for this disparity... Well in case somebody uses operator new: int* p1 = new int; if (p1) delete p1; we optimize out that to if (true), even when one has used defined operator new. Thus it's probably OK. Throwing new is returns_nonnull (errors are reported with exceptions) so that's fine, but non-throwing new is not: int* p1 = new(std::nothrow) int; Here errors are reported by returning 0, so it is common to test if p1 is 0 and this is precisely the case that could benefit from a predictor but does not have the attribute to do so (there are also consequences on aliasing). Then it can be handled with DECL_IS_OPERATOR_NEW, for those we can also set the newly introduced predictor. Independently of whether you extend the predictor to DECL_IS_OPERATOR_NEW, it would be good for this nothrow operator new to get the aliasing benefits of attribute malloc. I'll open a PR. (Jan's remark about functions with an inferred malloc attribute reminds me that at some point, the code was adding attribute malloc for functions that always return 0...) By inferred do you mean function that are marked as malloc in IPA pure-const (propagate_malloc)? Yes. Example would be appreciated. I used the past tense, I am not claiming this still happens. -- Marc Glisse
Re: [PATCH] Add malloc predictor (PR middle-end/83023).
On 08/01/2018 02:25 PM, Marc Glisse wrote: > On Wed, 1 Aug 2018, Martin Liška wrote: > >> On 07/27/2018 02:38 PM, Marc Glisse wrote: >>> On Fri, 27 Jul 2018, Martin Liška wrote: >>> So answer is yes, the builtin can be then removed. >>> >>> Good, thanks. While looking at how widely it is going to apply, I noticed >>> that the default, throwing operator new has attribute malloc and >>> everything, but the non-throwing variant declared in doesn't, so it >>> won't benefit from the new predictor. I don't know if there is a good >>> reason for this disparity... >>> >> >> Well in case somebody uses operator new: >> >> int* p1 = new int; >> if (p1) >> delete p1; >> >> we optimize out that to if (true), even when one has used defined >> operator new. Thus it's probably OK. > > Throwing new is returns_nonnull (errors are reported with exceptions) so > that's fine, but non-throwing new is not: > > int* p1 = new(std::nothrow) int; > > Here errors are reported by returning 0, so it is common to test if p1 is 0 > and this is precisely the case that could benefit from a predictor but does > not have the attribute to do so (there are also consequences on aliasing). Then it can be handled with DECL_IS_OPERATOR_NEW, for those we can also set the newly introduced predictor. > > (Jan's remark about functions with an inferred malloc attribute reminds me > that at some point, the code was adding attribute malloc for functions that > always return 0...) > By inferred do you mean function that are marked as malloc in IPA pure-const (propagate_malloc)? Example would be appreciated. Martin
Re: [PATCH] Add malloc predictor (PR middle-end/83023).
On Wed, 1 Aug 2018, Martin Liška wrote: On 07/27/2018 02:38 PM, Marc Glisse wrote: On Fri, 27 Jul 2018, Martin Liška wrote: So answer is yes, the builtin can be then removed. Good, thanks. While looking at how widely it is going to apply, I noticed that the default, throwing operator new has attribute malloc and everything, but the non-throwing variant declared in doesn't, so it won't benefit from the new predictor. I don't know if there is a good reason for this disparity... Well in case somebody uses operator new: int* p1 = new int; if (p1) delete p1; we optimize out that to if (true), even when one has used defined operator new. Thus it's probably OK. Throwing new is returns_nonnull (errors are reported with exceptions) so that's fine, but non-throwing new is not: int* p1 = new(std::nothrow) int; Here errors are reported by returning 0, so it is common to test if p1 is 0 and this is precisely the case that could benefit from a predictor but does not have the attribute to do so (there are also consequences on aliasing). (Jan's remark about functions with an inferred malloc attribute reminds me that at some point, the code was adding attribute malloc for functions that always return 0...) -- Marc Glisse
Re: [PATCH] Add malloc predictor (PR middle-end/83023).
On 07/31/2018 11:25 AM, Jan Hubicka wrote:
>> Hi.
>>
>> Following patch implements new predictors that annotates malloc-like
>> functions.
>> These almost every time return a non-null value.
>>
>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>>
>> Ready to be installed?
>> Martin
>>
>> gcc/ChangeLog:
>>
>> 2018-07-26 Martin Liska
>>
>> PR middle-end/83023
>> * predict.c (expr_expected_value_1): Handle DECL_IS_MALLOC
>> declarations.
>> * predict.def (PRED_MALLOC_NONNULL): New predictor.
>>
>> gcc/testsuite/ChangeLog:
>>
>> 2018-07-26 Martin Liska
>>
>> PR middle-end/83023
>> * gcc.dg/predict-16.c: New test.
>
> These are two conceptually different things - wether you return new memory
> and whether the return value is commonly non-null. While it goes together
> for majority of malloc function I wonder if this is safe WRT the auto-detected
> malloc attributes. I do not know how common is code that returns new memory
> only under some conditions?
You are right that malloc attribute does not guarantee that non-null is returned
in most cases. But I would say in most cases it's the case.
I'm sending updated version of the patch where I added BUILT_IN_REALLOC, which
doesn't have malloc attribute, but return non-null in most cases.
May I install that?
Martin
>
> Honza
>
>From 8ead58710e5676032183627bffc139382b34c609 Mon Sep 17 00:00:00 2001
From: marxin
Date: Thu, 26 Jul 2018 15:25:00 +0200
Subject: [PATCH] Add malloc predictor (PR middle-end/83023).
gcc/ChangeLog:
2018-07-26 Martin Liska
PR middle-end/83023
* predict.c (expr_expected_value_1): Handle DECL_IS_MALLOC
declarations.
* predict.def (PRED_MALLOC_NONNULL): New predictor.
gcc/testsuite/ChangeLog:
2018-07-26 Martin Liska
PR middle-end/83023
* gcc.dg/predict-16.c: New test.
---
gcc/predict.c | 12 +++
gcc/predict.def | 5 -
gcc/testsuite/gcc.dg/predict-16.c | 36 +++
3 files changed, 52 insertions(+), 1 deletion(-)
create mode 100644 gcc/testsuite/gcc.dg/predict-16.c
diff --git a/gcc/predict.c b/gcc/predict.c
index a6769eda1c7..69909d2dee1 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -2380,6 +2380,14 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
}
return NULL;
}
+
+ if (DECL_IS_MALLOC (decl))
+ {
+ if (predictor)
+ *predictor = PRED_MALLOC_NONNULL;
+ return boolean_true_node;
+ }
+
if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
switch (DECL_FUNCTION_CODE (decl))
{
@@ -2414,6 +2422,10 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
if (predictor)
*predictor = PRED_COMPARE_AND_SWAP;
return boolean_true_node;
+ case BUILT_IN_REALLOC:
+ if (predictor)
+ *predictor = PRED_MALLOC_NONNULL;
+ return boolean_true_node;
default:
break;
}
diff --git a/gcc/predict.def b/gcc/predict.def
index 4ed97ed165c..76e6590cc96 100644
--- a/gcc/predict.def
+++ b/gcc/predict.def
@@ -51,6 +51,10 @@ DEF_PREDICTOR (PRED_NO_PREDICTION, "no prediction", PROB_ALWAYS, 0)
DEF_PREDICTOR (PRED_UNCONDITIONAL, "unconditional jump", PROB_ALWAYS,
PRED_FLAG_FIRST_MATCH)
+/* Return value of malloc function is almost always non-null. */
+DEF_PREDICTOR (PRED_MALLOC_NONNULL, "malloc returned non-NULL", \
+ PROB_VERY_LIKELY, PRED_FLAG_FIRST_MATCH)
+
/* Use number of loop iterations determined by # of iterations
analysis to set probability. We don't want to use Dempster-Shaffer
theory here, as the predictions is exact. */
@@ -169,7 +173,6 @@ DEF_PREDICTOR (PRED_HOT_LABEL, "hot label", HITRATE (85), 0)
DEF_PREDICTOR (PRED_COLD_LABEL, "cold label", PROB_VERY_LIKELY,
PRED_FLAG_FIRST_MATCH)
-
/* The following predictors are used in Fortran. */
/* Branch leading to an integer overflow are extremely unlikely. */
diff --git a/gcc/testsuite/gcc.dg/predict-16.c b/gcc/testsuite/gcc.dg/predict-16.c
new file mode 100644
index 000..b71ad6c706d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-16.c
@@ -0,0 +1,36 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+#include
+#include
+
+void *r;
+void *r2;
+void *r3;
+void *r4;
+void *r5;
+
+void *m (size_t s, int c)
+{
+ r = malloc (s);
+ if (r)
+memset (r, 0, s);
+
+ r2 = calloc (s, 0);
+ if (r2)
+memset (r2, 0, s);
+
+ r3 = __builtin_malloc (s);
+ if (r3)
+memset (r3, 0, s);
+
+ r4 = __builtin_calloc (s, 0);
+ if (r4)
+memset (r4, 0, s);
+
+ r5 = __builtin_realloc (r4, s);
+ if (r5)
+memset (r4, 0, s);
+}
+
+/* { dg-final { scan-tree-dump-times "malloc returned non-NULL heuristics of edge\[^:\]*: 99.96%" 4 "profile_estimate"} } */
--
2.18.0
Re: [PATCH] Add malloc predictor (PR middle-end/83023).
On 07/27/2018 02:38 PM, Marc Glisse wrote: > On Fri, 27 Jul 2018, Martin Liška wrote: > >> So answer is yes, the builtin can be then removed. > > Good, thanks. While looking at how widely it is going to apply, I noticed > that the default, throwing operator new has attribute malloc and everything, > but the non-throwing variant declared in doesn't, so it won't benefit > from the new predictor. I don't know if there is a good reason for this > disparity... > Well in case somebody uses operator new: int* p1 = new int; if (p1) delete p1; we optimize out that to if (true), even when one has used defined operator new. Thus it's probably OK. Martin
Re: [PATCH] Add malloc predictor (PR middle-end/83023).
On 07/27/2018 02:38 PM, Marc Glisse wrote: > On Fri, 27 Jul 2018, Martin Liška wrote: > >> So answer is yes, the builtin can be then removed. > > Good, thanks. While looking at how widely it is going to apply, I noticed > that the default, throwing operator new has attribute malloc and everything, > but the non-throwing variant declared in doesn't, so it won't benefit > from the new predictor. I don't know if there is a good reason for this > disparity... > Jonathan? Martin
Re: [PATCH] Add malloc predictor (PR middle-end/83023).
> Hi. > > Following patch implements new predictors that annotates malloc-like > functions. > These almost every time return a non-null value. > > Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. > > Ready to be installed? > Martin > > gcc/ChangeLog: > > 2018-07-26 Martin Liska > > PR middle-end/83023 > * predict.c (expr_expected_value_1): Handle DECL_IS_MALLOC > declarations. > * predict.def (PRED_MALLOC_NONNULL): New predictor. > > gcc/testsuite/ChangeLog: > > 2018-07-26 Martin Liska > > PR middle-end/83023 > * gcc.dg/predict-16.c: New test. These are two conceptually different things - wether you return new memory and whether the return value is commonly non-null. While it goes together for majority of malloc function I wonder if this is safe WRT the auto-detected malloc attributes. I do not know how common is code that returns new memory only under some conditions? Honza
Re: [PATCH] Add malloc predictor (PR middle-end/83023).
On Fri, 27 Jul 2018, Martin Liška wrote: So answer is yes, the builtin can be then removed. Good, thanks. While looking at how widely it is going to apply, I noticed that the default, throwing operator new has attribute malloc and everything, but the non-throwing variant declared in doesn't, so it won't benefit from the new predictor. I don't know if there is a good reason for this disparity... -- Marc Glisse
Re: [PATCH] Add malloc predictor (PR middle-end/83023).
On 07/26/2018 05:00 PM, Marc Glisse wrote:
> On Thu, 26 Jul 2018, Martin Liška wrote:
>
>> Following patch implements new predictors that annotates malloc-like
>> functions.
>> These almost every time return a non-null value.
>
> Out of curiosity (the __builtin_expect there doesn't hurt and we don't need
> to remove it), does it make __builtin_expect unnecessary in the
> implementation of operator new (libstdc++-v3/libsupc++/new_op.cc)? It looks
> like
>
> while (__builtin_expect ((p = malloc (sz)) == 0, false))
> {
> new_handler handler = std::get_new_handler ();
> if (! handler)
> _GLIBCXX_THROW_OR_ABORT(bad_alloc());
> handler ();
> }
>
> where being in a loop may trigger opposite heuristics.
>
Thanks Marc for the pointer, it actually showed one problem with newly added
predictor.
So first, current trunk does:
Predictions for bb 5
first match heuristics: 10.00%
combined heuristics: 10.00%
__builtin_expect heuristics of edge 5->6: 10.00%
call heuristics of edge 5->6 (ignored): 33.00%
loop exit heuristics of edge 5->9 (ignored): 5.50%
removal of the __builtin_expect wrongly selected a different first march
predictor:
Predictions for bb 5
first match heuristics: 94.50%
combined heuristics: 94.50%
pointer (on trees) heuristics of edge 5->6 (ignored): 30.00%
malloc returned non-NULL heuristics of edge 5->6 (ignored): 0.04%
call heuristics of edge 5->6 (ignored): 33.00%
loop exit heuristics of edge 5->9: 5.50%
I fixed that by moving PRED_MALLOC_NONNULL up in the list, now it's fine:
1 edges in bb 4 predicted to even probabilities
Predictions for bb 5
first match heuristics: 0.04%
combined heuristics: 0.04%
pointer (on trees) heuristics of edge 5->6 (ignored): 30.00%
malloc returned non-NULL heuristics of edge 5->6: 0.04%
call heuristics of edge 5->6 (ignored): 33.00%
loop exit heuristics of edge 5->9 (ignored): 5.50%
So answer is yes, the builtin can be then removed.
Martin
>From ba2aa6cb7367f529ad96ece92e25cd0366a28735 Mon Sep 17 00:00:00 2001
From: marxin
Date: Thu, 26 Jul 2018 15:25:00 +0200
Subject: [PATCH] Add malloc predictor (PR middle-end/83023).
gcc/ChangeLog:
2018-07-26 Martin Liska
PR middle-end/83023
* predict.c (expr_expected_value_1): Handle DECL_IS_MALLOC
declarations.
* predict.def (PRED_MALLOC_NONNULL): New predictor.
gcc/testsuite/ChangeLog:
2018-07-26 Martin Liska
PR middle-end/83023
* gcc.dg/predict-16.c: New test.
---
gcc/predict.c | 8
gcc/predict.def | 5 -
gcc/testsuite/gcc.dg/predict-16.c | 31 +++
3 files changed, 43 insertions(+), 1 deletion(-)
create mode 100644 gcc/testsuite/gcc.dg/predict-16.c
diff --git a/gcc/predict.c b/gcc/predict.c
index a6769eda1c7..a7b2223c697 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -2380,6 +2380,14 @@ expr_expected_value_1 (tree type, tree op0, enum tree_code code,
}
return NULL;
}
+
+ if (DECL_IS_MALLOC (decl))
+ {
+ if (predictor)
+ *predictor = PRED_MALLOC_NONNULL;
+ return boolean_true_node;
+ }
+
if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
switch (DECL_FUNCTION_CODE (decl))
{
diff --git a/gcc/predict.def b/gcc/predict.def
index 4ed97ed165c..426c17f26fd 100644
--- a/gcc/predict.def
+++ b/gcc/predict.def
@@ -88,6 +88,10 @@ DEF_PREDICTOR (PRED_NORETURN, "noreturn call", PROB_VERY_LIKELY,
DEF_PREDICTOR (PRED_COLD_FUNCTION, "cold function call", PROB_VERY_LIKELY,
PRED_FLAG_FIRST_MATCH)
+/* Return value of malloc function is almost always non-null. */
+DEF_PREDICTOR (PRED_MALLOC_NONNULL, "malloc returned non-NULL", \
+ PROB_VERY_LIKELY, PRED_FLAG_FIRST_MATCH)
+
/* Edge causing loop to terminate is probably not taken. */
DEF_PREDICTOR (PRED_LOOP_EXIT, "loop exit", HITRATE (89),
PRED_FLAG_FIRST_MATCH)
@@ -169,7 +173,6 @@ DEF_PREDICTOR (PRED_HOT_LABEL, "hot label", HITRATE (85), 0)
DEF_PREDICTOR (PRED_COLD_LABEL, "cold label", PROB_VERY_LIKELY,
PRED_FLAG_FIRST_MATCH)
-
/* The following predictors are used in Fortran. */
/* Branch leading to an integer overflow are extremely unlikely. */
diff --git a/gcc/testsuite/gcc.dg/predict-16.c b/gcc/testsuite/gcc.dg/predict-16.c
new file mode 100644
index 000..3a3e943bb79
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/predict-16.c
@@ -0,0 +1,31 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+#include
+#include
+
+void *r;
+void *r2;
+void *r3;
+void *r4;
+
+void *m (size_t s, int c)
+{
+ r = malloc (s);
+ if (r)
+memset (r, 0, s);
+
+ r2 = calloc (s, 0);
+ if (r2)
+memset (r2, 0, s);
+
+ r3 = __builtin_malloc (s);
+ if (r3)
+memset (r3, 0, s);
+
+ r4 = __builtin_calloc (s, 0);
+ if (r4)
+memset (r4, 0, s);
+}
+
+/* { dg-final { scan-tree-dump-times "malloc returned non-NULL heuristics of edge\[^:\]*: 99.96%" 4
Re: [PATCH] Add malloc predictor (PR middle-end/83023).
On Thu, 26 Jul 2018, Martin Liška wrote:
Following patch implements new predictors that annotates malloc-like functions.
These almost every time return a non-null value.
Out of curiosity (the __builtin_expect there doesn't hurt and we don't
need to remove it), does it make __builtin_expect unnecessary in the
implementation of operator new (libstdc++-v3/libsupc++/new_op.cc)? It
looks like
while (__builtin_expect ((p = malloc (sz)) == 0, false))
{
new_handler handler = std::get_new_handler ();
if (! handler)
_GLIBCXX_THROW_OR_ABORT(bad_alloc());
handler ();
}
where being in a loop may trigger opposite heuristics.
--
Marc Glisse
