diff mbox series

Ranger : Do not process abnormal ssa-names.

Message ID 65efdb72-260a-e5a3-5b28-f536f86bd5e6@redhat.com
State New
Headers show
Series Ranger : Do not process abnormal ssa-names. | expand

Commit Message

Andrew MacLeod Oct. 15, 2021, 1:50 p.m. UTC
I've been looking at the pathological time issue ranger has with the 
testcase from, uuuuuh..  PR 97623 I think.  I've lost the details, but 
kept the file since it was showing unpleasant behaviour.

Most of the time is spent in callbacks from substitute_and_fold to 
value_on_edge()  dealing with PHI results and arguments.  Turns out, its 
virtually all wasted time dealing with SSA_NAMES with the 
OCCURS_IN_ABNORMAL_PHI flag set..

This patch tells ranger not to consider any SSA_NAMEs which occur in 
abnormal PHIs.  This reduces the memory footprint of all the caches, and 
also has a ripple effect with the new threader code which uses the GORI 
exports and imports tables, making it faster as well as no ssa-name with 
the abnormal flag set will be entered into the tables.

That alone was not quite enough, as all the sheer volume of call backs 
still took time,  so I added checks in the value_of_* class of routines 
used by substitute_and_fold to indicate there is no constant value 
available for any SSA_NAME with that flag set.

On my x86_64 box, before this change, that test case looked like:

tree VRP                           :   7.76 (  4%)   0.23 ( 5%)   8.02 
(  4%)   537k (  0%)
tree VRP threader                  :   7.20 (  4%)   0.08 (  2%) 7.28 (  
4%)   392k (  0%)
tree Early VRP                     :  39.22 ( 22%)   0.07 (  2%) 39.44 ( 
22%)  1142k (  0%)

And with this patch , the results are:

  tree VRP                           :   7.57 (  6%)   0.26 ( 5%)   7.85 
(  6%)   537k (  0%)
  tree VRP threader                  :   0.62 (  0%)   0.02 ( 0%)   0.65 
(  0%)   392k (  0%)
  tree Early VRP                     :   4.00 (  3%)   0.01 ( 0%)   4.03 
(  3%)  1142k (  0%)

Which is a significant improvement, both for EVRP and the threader..

The patch adjusts the ranger folder, as well as the hybrid folder.

bootstrapped on x86_64-pc-linux-gnu with no regressions and no missed 
cases that I have been able to find.

I don't want to push it quite yet as I wanted feedback to make sure we 
don't actually do anything I'm not aware of with SSA_NAMES which have 
the ABNORMAL_PHI flag set.  Most of the code i can find in VRP and 
vr-values appears to punt, so I presume not even considering those names 
is fine?

This also seems like something that might be worth back-porting, 
especially the hybrid pass parts...

Andrew

Comments

Jeff Law Oct. 15, 2021, 2:17 p.m. UTC | #1
On 10/15/2021 7:50 AM, Andrew MacLeod via Gcc-patches wrote:
> I've been looking at the pathological time issue ranger has with the 
> testcase from, uuuuuh..  PR 97623 I think.  I've lost the details, but 
> kept the file since it was showing unpleasant behaviour.
>
> Most of the time is spent in callbacks from substitute_and_fold to 
> value_on_edge()  dealing with PHI results and arguments.  Turns out, 
> its virtually all wasted time dealing with SSA_NAMES with the 
> OCCURS_IN_ABNORMAL_PHI flag set..
>
> This patch tells ranger not to consider any SSA_NAMEs which occur in 
> abnormal PHIs.  This reduces the memory footprint of all the caches, 
> and also has a ripple effect with the new threader code which uses the 
> GORI exports and imports tables, making it faster as well as no 
> ssa-name with the abnormal flag set will be entered into the tables.
>
> That alone was not quite enough, as all the sheer volume of call backs 
> still took time,  so I added checks in the value_of_* class of 
> routines used by substitute_and_fold to indicate there is no constant 
> value available for any SSA_NAME with that flag set.
>
> On my x86_64 box, before this change, that test case looked like:
>
> tree VRP                           :   7.76 (  4%)   0.23 ( 5%) 8.02 
> (  4%)   537k (  0%)
> tree VRP threader                  :   7.20 (  4%)   0.08 (  2%) 7.28 
> (  4%)   392k (  0%)
> tree Early VRP                     :  39.22 ( 22%)   0.07 (  2%) 39.44 
> ( 22%)  1142k (  0%)
>
> And with this patch , the results are:
>
>  tree VRP                           :   7.57 (  6%)   0.26 ( 5%) 7.85 
> (  6%)   537k (  0%)
>  tree VRP threader                  :   0.62 (  0%)   0.02 ( 0%) 0.65 
> (  0%)   392k (  0%)
>  tree Early VRP                     :   4.00 (  3%)   0.01 ( 0%) 4.03 
> (  3%)  1142k (  0%)
>
> Which is a significant improvement, both for EVRP and the threader..
>
> The patch adjusts the ranger folder, as well as the hybrid folder.
>
> bootstrapped on x86_64-pc-linux-gnu with no regressions and no missed 
> cases that I have been able to find.
>
> I don't want to push it quite yet as I wanted feedback to make sure we 
> don't actually do anything I'm not aware of with SSA_NAMES which have 
> the ABNORMAL_PHI flag set.  Most of the code i can find in VRP and 
> vr-values appears to punt, so I presume not even considering those 
> names is fine?
>
> This also seems like something that might be worth back-porting, 
> especially the hybrid pass parts...
Punting on the abnormals seems perfectly fine to me.  They rarely, if 
ever, provide information that improves optimization.

Jeff
Aldy Hernandez Oct. 15, 2021, 2:21 p.m. UTC | #2
On 10/15/21 3:50 PM, Andrew MacLeod wrote:
> I've been looking at the pathological time issue ranger has with the 
> testcase from, uuuuuh..  PR 97623 I think.  I've lost the details, but 
> kept the file since it was showing unpleasant behaviour.
> 
> Most of the time is spent in callbacks from substitute_and_fold to 
> value_on_edge()  dealing with PHI results and arguments.  Turns out, its 
> virtually all wasted time dealing with SSA_NAMES with the 
> OCCURS_IN_ABNORMAL_PHI flag set..
> 
> This patch tells ranger not to consider any SSA_NAMEs which occur in 
> abnormal PHIs.  This reduces the memory footprint of all the caches, and 
> also has a ripple effect with the new threader code which uses the GORI 
> exports and imports tables, making it faster as well as no ssa-name with 
> the abnormal flag set will be entered into the tables.
> 
> That alone was not quite enough, as all the sheer volume of call backs 
> still took time,  so I added checks in the value_of_* class of routines 
> used by substitute_and_fold to indicate there is no constant value 
> available for any SSA_NAME with that flag set.
> 
> On my x86_64 box, before this change, that test case looked like:
> 
> tree VRP                           :   7.76 (  4%)   0.23 ( 5%)   8.02 
> (  4%)   537k (  0%)
> tree VRP threader                  :   7.20 (  4%)   0.08 (  2%) 7.28 ( 
> 4%)   392k (  0%)
> tree Early VRP                     :  39.22 ( 22%)   0.07 (  2%) 39.44 ( 
> 22%)  1142k (  0%)
> 
> And with this patch , the results are:
> 
>   tree VRP                           :   7.57 (  6%)   0.26 ( 5%)   7.85 
> (  6%)   537k (  0%)
>   tree VRP threader                  :   0.62 (  0%)   0.02 ( 0%)   0.65 
> (  0%)   392k (  0%)
>   tree Early VRP                     :   4.00 (  3%)   0.01 ( 0%)   4.03 
> (  3%)  1142k (  0%)
> 
> Which is a significant improvement, both for EVRP and the threader..
> 
> The patch adjusts the ranger folder, as well as the hybrid folder.
> 
> bootstrapped on x86_64-pc-linux-gnu with no regressions and no missed 
> cases that I have been able to find.
> 
> I don't want to push it quite yet as I wanted feedback to make sure we 
> don't actually do anything I'm not aware of with SSA_NAMES which have 
> the ABNORMAL_PHI flag set.  Most of the code i can find in VRP and 
> vr-values appears to punt, so I presume not even considering those names 
> is fine?

The backward threader skips both edges with EDGE_ABNORMAL set as well as 
phi results to have SSA_NAME_OCCURS_IN_ABNORMAL_PHI.

The forward threader skips out on all abnormal edges as well.  It seems 
to even avoid threading through blocks where one of the 2 outgoing edges 
is abnormal.  Dunno if this was an oversight, or just being extra careful.

Anywhoooo, at least from the threaders you're safe.

Aldy
Jeff Law Oct. 15, 2021, 2:23 p.m. UTC | #3
On 10/15/2021 8:21 AM, Aldy Hernandez wrote:
>
>
> On 10/15/21 3:50 PM, Andrew MacLeod wrote:
>> I've been looking at the pathological time issue ranger has with the 
>> testcase from, uuuuuh..  PR 97623 I think.  I've lost the details, 
>> but kept the file since it was showing unpleasant behaviour.
>>
>> Most of the time is spent in callbacks from substitute_and_fold to 
>> value_on_edge()  dealing with PHI results and arguments. Turns out, 
>> its virtually all wasted time dealing with SSA_NAMES with the 
>> OCCURS_IN_ABNORMAL_PHI flag set..
>>
>> This patch tells ranger not to consider any SSA_NAMEs which occur in 
>> abnormal PHIs.  This reduces the memory footprint of all the caches, 
>> and also has a ripple effect with the new threader code which uses 
>> the GORI exports and imports tables, making it faster as well as no 
>> ssa-name with the abnormal flag set will be entered into the tables.
>>
>> That alone was not quite enough, as all the sheer volume of call 
>> backs still took time,  so I added checks in the value_of_* class of 
>> routines used by substitute_and_fold to indicate there is no constant 
>> value available for any SSA_NAME with that flag set.
>>
>> On my x86_64 box, before this change, that test case looked like:
>>
>> tree VRP                           :   7.76 (  4%)   0.23 ( 5%)   
>> 8.02 (  4%)   537k (  0%)
>> tree VRP threader                  :   7.20 (  4%)   0.08 (  2%) 7.28 
>> ( 4%)   392k (  0%)
>> tree Early VRP                     :  39.22 ( 22%)   0.07 (  2%) 
>> 39.44 ( 22%)  1142k (  0%)
>>
>> And with this patch , the results are:
>>
>>   tree VRP                           :   7.57 (  6%)   0.26 ( 5%)   
>> 7.85 (  6%)   537k (  0%)
>>   tree VRP threader                  :   0.62 (  0%)   0.02 ( 0%)   
>> 0.65 (  0%)   392k (  0%)
>>   tree Early VRP                     :   4.00 (  3%)   0.01 ( 0%)   
>> 4.03 (  3%)  1142k (  0%)
>>
>> Which is a significant improvement, both for EVRP and the threader..
>>
>> The patch adjusts the ranger folder, as well as the hybrid folder.
>>
>> bootstrapped on x86_64-pc-linux-gnu with no regressions and no missed 
>> cases that I have been able to find.
>>
>> I don't want to push it quite yet as I wanted feedback to make sure 
>> we don't actually do anything I'm not aware of with SSA_NAMES which 
>> have the ABNORMAL_PHI flag set.  Most of the code i can find in VRP 
>> and vr-values appears to punt, so I presume not even considering 
>> those names is fine?
>
> The backward threader skips both edges with EDGE_ABNORMAL set as well 
> as phi results to have SSA_NAME_OCCURS_IN_ABNORMAL_PHI.
>
> The forward threader skips out on all abnormal edges as well.  It 
> seems to even avoid threading through blocks where one of the 2 
> outgoing edges is abnormal.  Dunno if this was an oversight, or just 
> being extra careful.
Being extra careful.   I couldn't convince myself that copying a block 
with an abnormal edge (incoming or outgoing) was going to be reliably safe.

jeff
Andrew MacLeod Oct. 15, 2021, 4:05 p.m. UTC | #4
On 10/15/21 10:17 AM, Jeff Law wrote:
>
>>
>> I don't want to push it quite yet as I wanted feedback to make sure 
>> we don't actually do anything I'm not aware of with SSA_NAMES which 
>> have the ABNORMAL_PHI flag set.  Most of the code i can find in VRP 
>> and vr-values appears to punt, so I presume not even considering 
>> those names is fine?
>>
>> This also seems like something that might be worth back-porting, 
>> especially the hybrid pass parts...
> Punting on the abnormals seems perfectly fine to me.  They rarely, if 
> ever, provide information that improves optimization.
>
> Jeff
>
pushed as commit  93ac832f1846e4867aa6537f76f510fab8e3e87d

Andrew
Andrew Pinski Oct. 16, 2021, 9:27 a.m. UTC | #5
On Fri, Oct 15, 2021 at 6:53 AM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> I've been looking at the pathological time issue ranger has with the
> testcase from, uuuuuh..  PR 97623 I think.  I've lost the details, but
> kept the file since it was showing unpleasant behaviour.
>
> Most of the time is spent in callbacks from substitute_and_fold to
> value_on_edge()  dealing with PHI results and arguments.  Turns out, its
> virtually all wasted time dealing with SSA_NAMES with the
> OCCURS_IN_ABNORMAL_PHI flag set..
>
> This patch tells ranger not to consider any SSA_NAMEs which occur in
> abnormal PHIs.  This reduces the memory footprint of all the caches, and
> also has a ripple effect with the new threader code which uses the GORI
> exports and imports tables, making it faster as well as no ssa-name with
> the abnormal flag set will be entered into the tables.
>
> That alone was not quite enough, as all the sheer volume of call backs
> still took time,  so I added checks in the value_of_* class of routines
> used by substitute_and_fold to indicate there is no constant value
> available for any SSA_NAME with that flag set.
>
> On my x86_64 box, before this change, that test case looked like:
>
> tree VRP                           :   7.76 (  4%)   0.23 ( 5%)   8.02
> (  4%)   537k (  0%)
> tree VRP threader                  :   7.20 (  4%)   0.08 (  2%) 7.28 (
> 4%)   392k (  0%)
> tree Early VRP                     :  39.22 ( 22%)   0.07 (  2%) 39.44 (
> 22%)  1142k (  0%)
>
> And with this patch , the results are:
>
>   tree VRP                           :   7.57 (  6%)   0.26 ( 5%)   7.85
> (  6%)   537k (  0%)
>   tree VRP threader                  :   0.62 (  0%)   0.02 ( 0%)   0.65
> (  0%)   392k (  0%)
>   tree Early VRP                     :   4.00 (  3%)   0.01 ( 0%)   4.03
> (  3%)  1142k (  0%)
>
> Which is a significant improvement, both for EVRP and the threader..
>
> The patch adjusts the ranger folder, as well as the hybrid folder.
>
> bootstrapped on x86_64-pc-linux-gnu with no regressions and no missed
> cases that I have been able to find.

Did you test it with go enabled?
Because others and myself are now running into a bootstrap failure
most likely due to this patch.
The number of SSA_NAME_OCCURS_IN_ABNORMAL_PHI in go is increased due
to -fnon-call-exceptions being true there.

Thanks,
Andrew Pinski
PS here is the ICE for me:
libtool: compile:
/home/apinski/src/upstream-gcc/gcc/objdir/./gcc/gccgo
-B/home/apinski/src/upstream-gcc/gcc/objdir/./gcc/
-B/home/apinski/upstream-gcc/x86_64-pc-linux-gnu/bin/
-B/home/apinski/upstream-gcc/x86_64-pc-linux-gnu/lib/ -isystem
/home/apinski/upstream-gcc/x86_64-pc-linux-gnu/include -isystem
/home/apinski/upstream-gcc/x86_64-pc-linux-gnu/sys-include
-fchecking=1 -minline-all-stringops -O2 -g -m32 -I . -c
-fgo-pkgpath=cmd/go/internal/modget
/home/apinski/src/upstream-gcc/gcc/libgo/go/cmd/go/internal/modget/get.go
/home/apinski/src/upstream-gcc/gcc/libgo/go/cmd/go/internal/modget/query.go
-o cmd/go/internal/modget.o
during GIMPLE pass: evrp
In function ‘cmd/go/internal/modget.resolver.resolveQueries’:
go1: internal compiler error: tree check: expected class ‘type’, have
‘exceptional’ (error_mark) in useless_type_conversion_p, at
gimple-expr.c:87
0x862719 tree_class_check_failed(tree_node const*, tree_code_class,
char const*, int, char const*)
        /home/apinski/src/upstream-gcc/gcc/gcc/tree.c:8739
0x7910ed tree_class_check(tree_node*, tree_code_class, char const*,
int, char const*)
        /home/apinski/src/upstream-gcc/gcc/gcc/tree.h:3556
0x7910ed useless_type_conversion_p(tree_node*, tree_node*)
        /home/apinski/src/upstream-gcc/gcc/gcc/gimple-expr.c:87
0xf81a58 verify_gimple_phi
        /home/apinski/src/upstream-gcc/gcc/gcc/tree-cfg.c:5128
0xf81a58 verify_gimple_in_cfg(function*, bool)
        /home/apinski/src/upstream-gcc/gcc/gcc/tree-cfg.c:5457
0xe54a57 execute_function_todo
        /home/apinski/src/upstream-gcc/gcc/gcc/passes.c:2042
0xe5546e execute_todo
        /home/apinski/src/upstream-gcc/gcc/gcc/passes.c:2096
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <https://gcc.gnu.org/bugs/> for instructions.


>
> I don't want to push it quite yet as I wanted feedback to make sure we
> don't actually do anything I'm not aware of with SSA_NAMES which have
> the ABNORMAL_PHI flag set.  Most of the code i can find in VRP and
> vr-values appears to punt, so I presume not even considering those names
> is fine?
>
> This also seems like something that might be worth back-porting,
> especially the hybrid pass parts...
>
> Andrew
>
>
Iain Sandoe Oct. 16, 2021, 4:22 p.m. UTC | #6
> On 16 Oct 2021, at 10:27, Andrew Pinski via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
> 
> On Fri, Oct 15, 2021 at 6:53 AM Andrew MacLeod via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>> 
>> I've been looking at the pathological time issue ranger has with the
>> testcase from, uuuuuh..  PR 97623 I think.  I've lost the details, but
>> kept the file since it was showing unpleasant behaviour.
>> 
>> Most of the time is spent in callbacks from substitute_and_fold to
>> value_on_edge()  dealing with PHI results and arguments.  Turns out, its
>> virtually all wasted time dealing with SSA_NAMES with the
>> OCCURS_IN_ABNORMAL_PHI flag set..
>> 
>> This patch tells ranger not to consider any SSA_NAMEs which occur in
>> abnormal PHIs.  This reduces the memory footprint of all the caches, and
>> also has a ripple effect with the new threader code which uses the GORI
>> exports and imports tables, making it faster as well as no ssa-name with
>> the abnormal flag set will be entered into the tables.
>> 
>> That alone was not quite enough, as all the sheer volume of call backs
>> still took time,  so I added checks in the value_of_* class of routines
>> used by substitute_and_fold to indicate there is no constant value
>> available for any SSA_NAME with that flag set.
>> 
>> On my x86_64 box, before this change, that test case looked like:
>> 
>> tree VRP                           :   7.76 (  4%)   0.23 ( 5%)   8.02
>> (  4%)   537k (  0%)
>> tree VRP threader                  :   7.20 (  4%)   0.08 (  2%) 7.28 (
>> 4%)   392k (  0%)
>> tree Early VRP                     :  39.22 ( 22%)   0.07 (  2%) 39.44 (
>> 22%)  1142k (  0%)
>> 
>> And with this patch , the results are:
>> 
>>  tree VRP                           :   7.57 (  6%)   0.26 ( 5%)   7.85
>> (  6%)   537k (  0%)
>>  tree VRP threader                  :   0.62 (  0%)   0.02 ( 0%)   0.65
>> (  0%)   392k (  0%)
>>  tree Early VRP                     :   4.00 (  3%)   0.01 ( 0%)   4.03
>> (  3%)  1142k (  0%)
>> 
>> Which is a significant improvement, both for EVRP and the threader..
>> 
>> The patch adjusts the ranger folder, as well as the hybrid folder.
>> 
>> bootstrapped on x86_64-pc-linux-gnu with no regressions and no missed
>> cases that I have been able to find.
> 
> Did you test it with go enabled?
> Because others and myself are now running into a bootstrap failure
> most likely due to this patch.
> The number of SSA_NAME_OCCURS_IN_ABNORMAL_PHI in go is increased due
> to -fnon-call-exceptions being true there.

and, presumably for similar reasons, there are around 25 Ada regressions on several platforms.
the acats output is probably not as helpful as Andrew’s ICE.
Iain

(possibly, there are some D / libphobos regressions too - but I didn’t bisect those)

> 
> Thanks,
> Andrew Pinski
> PS here is the ICE for me:
> libtool: compile:
> /home/apinski/src/upstream-gcc/gcc/objdir/./gcc/gccgo
> -B/home/apinski/src/upstream-gcc/gcc/objdir/./gcc/
> -B/home/apinski/upstream-gcc/x86_64-pc-linux-gnu/bin/
> -B/home/apinski/upstream-gcc/x86_64-pc-linux-gnu/lib/ -isystem
> /home/apinski/upstream-gcc/x86_64-pc-linux-gnu/include -isystem
> /home/apinski/upstream-gcc/x86_64-pc-linux-gnu/sys-include
> -fchecking=1 -minline-all-stringops -O2 -g -m32 -I . -c
> -fgo-pkgpath=cmd/go/internal/modget
> /home/apinski/src/upstream-gcc/gcc/libgo/go/cmd/go/internal/modget/get.go
> /home/apinski/src/upstream-gcc/gcc/libgo/go/cmd/go/internal/modget/query.go
> -o cmd/go/internal/modget.o
> during GIMPLE pass: evrp
> In function ‘cmd/go/internal/modget.resolver.resolveQueries’:
> go1: internal compiler error: tree check: expected class ‘type’, have
> ‘exceptional’ (error_mark) in useless_type_conversion_p, at
> gimple-expr.c:87
> 0x862719 tree_class_check_failed(tree_node const*, tree_code_class,
> char const*, int, char const*)
>        /home/apinski/src/upstream-gcc/gcc/gcc/tree.c:8739
> 0x7910ed tree_class_check(tree_node*, tree_code_class, char const*,
> int, char const*)
>        /home/apinski/src/upstream-gcc/gcc/gcc/tree.h:3556
> 0x7910ed useless_type_conversion_p(tree_node*, tree_node*)
>        /home/apinski/src/upstream-gcc/gcc/gcc/gimple-expr.c:87
> 0xf81a58 verify_gimple_phi
>        /home/apinski/src/upstream-gcc/gcc/gcc/tree-cfg.c:5128
> 0xf81a58 verify_gimple_in_cfg(function*, bool)
>        /home/apinski/src/upstream-gcc/gcc/gcc/tree-cfg.c:5457
> 0xe54a57 execute_function_todo
>        /home/apinski/src/upstream-gcc/gcc/gcc/passes.c:2042
> 0xe5546e execute_todo
>        /home/apinski/src/upstream-gcc/gcc/gcc/passes.c:2096
> Please submit a full bug report,
> with preprocessed source if appropriate.
> Please include the complete backtrace with any bug report.
> See <https://gcc.gnu.org/bugs/> for instructions.
> 
> 
>> 
>> I don't want to push it quite yet as I wanted feedback to make sure we
>> don't actually do anything I'm not aware of with SSA_NAMES which have
>> the ABNORMAL_PHI flag set.  Most of the code i can find in VRP and
>> vr-values appears to punt, so I presume not even considering those names
>> is fine?
>> 
>> This also seems like something that might be worth back-porting,
>> especially the hybrid pass parts...
>> 
>> Andrew
Richard Biener Oct. 18, 2021, 9:49 a.m. UTC | #7
On Fri, Oct 15, 2021 at 3:50 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> I've been looking at the pathological time issue ranger has with the
> testcase from, uuuuuh..  PR 97623 I think.  I've lost the details, but
> kept the file since it was showing unpleasant behaviour.
>
> Most of the time is spent in callbacks from substitute_and_fold to
> value_on_edge()  dealing with PHI results and arguments.  Turns out, its
> virtually all wasted time dealing with SSA_NAMES with the
> OCCURS_IN_ABNORMAL_PHI flag set..
>
> This patch tells ranger not to consider any SSA_NAMEs which occur in
> abnormal PHIs.  This reduces the memory footprint of all the caches, and
> also has a ripple effect with the new threader code which uses the GORI
> exports and imports tables, making it faster as well as no ssa-name with
> the abnormal flag set will be entered into the tables.
>
> That alone was not quite enough, as all the sheer volume of call backs
> still took time,  so I added checks in the value_of_* class of routines
> used by substitute_and_fold to indicate there is no constant value
> available for any SSA_NAME with that flag set.
>
> On my x86_64 box, before this change, that test case looked like:
>
> tree VRP                           :   7.76 (  4%)   0.23 ( 5%)   8.02
> (  4%)   537k (  0%)
> tree VRP threader                  :   7.20 (  4%)   0.08 (  2%) 7.28 (
> 4%)   392k (  0%)
> tree Early VRP                     :  39.22 ( 22%)   0.07 (  2%) 39.44 (
> 22%)  1142k (  0%)
>
> And with this patch , the results are:
>
>   tree VRP                           :   7.57 (  6%)   0.26 ( 5%)   7.85
> (  6%)   537k (  0%)
>   tree VRP threader                  :   0.62 (  0%)   0.02 ( 0%)   0.65
> (  0%)   392k (  0%)
>   tree Early VRP                     :   4.00 (  3%)   0.01 ( 0%)   4.03
> (  3%)  1142k (  0%)
>
> Which is a significant improvement, both for EVRP and the threader..
>
> The patch adjusts the ranger folder, as well as the hybrid folder.
>
> bootstrapped on x86_64-pc-linux-gnu with no regressions and no missed
> cases that I have been able to find.
>
> I don't want to push it quite yet as I wanted feedback to make sure we
> don't actually do anything I'm not aware of with SSA_NAMES which have
> the ABNORMAL_PHI flag set.  Most of the code i can find in VRP and
> vr-values appears to punt, so I presume not even considering those names
> is fine?
>
> This also seems like something that might be worth back-porting,
> especially the hybrid pass parts...

Returning NULL in gimple_range_ssa_p is probably not a good idea.  The
name does carry a range it just has to be considered VARYING.

The issue with abnormal edges is that they do not have a jump
associated with them and thus we cannot insert code on the edge
because we cannot split it.  That has implications for coalescing
since we cannot even insert copies there so the PHI argument
and the PHI result have to be the same register for the arguments
on abnormal edges.

Otherwise they do carry a value and a range but forcing that to be
VARYING makes sense to avoid propagating constants to where
it is not allowed (though the substitution phase should be the one
checking).

Richard.

> Andrew
>
>
Andrew MacLeod Oct. 18, 2021, 4:08 p.m. UTC | #8
On 10/16/21 5:27 AM, Andrew Pinski wrote:
> On Fri, Oct 15, 2021 at 6:53 AM Andrew MacLeod via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>> I've been looking at the pathological time issue ranger has with the
>> testcase from, uuuuuh..  PR 97623 I think.  I've lost the details, but
>> kept the file since it was showing unpleasant behaviour.
>>
>> Most of the time is spent in callbacks from substitute_and_fold to
>> value_on_edge()  dealing with PHI results and arguments.  Turns out, its
>> virtually all wasted time dealing with SSA_NAMES with the
>> OCCURS_IN_ABNORMAL_PHI flag set..
>>
>> This patch tells ranger not to consider any SSA_NAMEs which occur in
>> abnormal PHIs.  This reduces the memory footprint of all the caches, and
>> also has a ripple effect with the new threader code which uses the GORI
>> exports and imports tables, making it faster as well as no ssa-name with
>> the abnormal flag set will be entered into the tables.
>>
>> That alone was not quite enough, as all the sheer volume of call backs
>> still took time,  so I added checks in the value_of_* class of routines
>> used by substitute_and_fold to indicate there is no constant value
>> available for any SSA_NAME with that flag set.
>>
>> On my x86_64 box, before this change, that test case looked like:
>>
>> tree VRP                           :   7.76 (  4%)   0.23 ( 5%)   8.02
>> (  4%)   537k (  0%)
>> tree VRP threader                  :   7.20 (  4%)   0.08 (  2%) 7.28 (
>> 4%)   392k (  0%)
>> tree Early VRP                     :  39.22 ( 22%)   0.07 (  2%) 39.44 (
>> 22%)  1142k (  0%)
>>
>> And with this patch , the results are:
>>
>>    tree VRP                           :   7.57 (  6%)   0.26 ( 5%)   7.85
>> (  6%)   537k (  0%)
>>    tree VRP threader                  :   0.62 (  0%)   0.02 ( 0%)   0.65
>> (  0%)   392k (  0%)
>>    tree Early VRP                     :   4.00 (  3%)   0.01 ( 0%)   4.03
>> (  3%)  1142k (  0%)
>>
>> Which is a significant improvement, both for EVRP and the threader..
>>
>> The patch adjusts the ranger folder, as well as the hybrid folder.
>>
>> bootstrapped on x86_64-pc-linux-gnu with no regressions and no missed
>> cases that I have been able to find.
> Did you test it with go enabled?
> Because others and myself are now running into a bootstrap failure
> most likely due to this patch.
> The number of SSA_NAME_OCCURS_IN_ABNORMAL_PHI in go is increased due
> to -fnon-call-exceptions being true there.

I would have sworn upside down I did, but looking at my build script, 
somewhere along the way GO got turned off, so although I was building 
ada, GO was not being included.. sorry.

I'll get this resolved this afternoon.

Andrew
diff mbox series

Patch

From 146744fcde6a67f759ffc4aa3e8340861e229829 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Thu, 7 Oct 2021 10:12:29 -0400
Subject: [PATCH] Ranger : Do not process abnormal ssa-names.

	* gimple-range-fold.h (gimple_range_ssa_p): Don't process names
	that occur in abnormal phis.
	* gimple-range.cc (gimple_ranger::range_on_edge): Return false for
	abnormal and EH edges.
	* gimple-ssa-evrp.c (rvrp_folder::value_of_expr): Ditto.
	(rvrp_folder::value_on_edge): Ditto.
	(rvrp_folder::value_of_stmt): Ditto.
	(hybrid_folder::value_of_expr): Ditto for ranger queries.
	(hybrid_folder::value_on_edge): Ditto.
	(hybrid_folder::value_of_stmt): Ditto.
	* value-query.cc (gimple_range_global): Always return a range if
	the type is supported.
---
 gcc/gimple-range-fold.h |  1 +
 gcc/gimple-range.cc     |  4 ++++
 gcc/gimple-ssa-evrp.c   | 39 ++++++++++++++++++++++++++++++++-------
 gcc/value-query.cc      |  3 ++-
 4 files changed, 39 insertions(+), 8 deletions(-)

diff --git a/gcc/gimple-range-fold.h b/gcc/gimple-range-fold.h
index bc0874b5f31..350e2c4e039 100644
--- a/gcc/gimple-range-fold.h
+++ b/gcc/gimple-range-fold.h
@@ -93,6 +93,7 @@  gimple_range_ssa_p (tree exp)
 {
   if (exp && TREE_CODE (exp) == SSA_NAME &&
       !SSA_NAME_IS_VIRTUAL_OPERAND (exp) &&
+      !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) &&
       irange::supports_type_p (TREE_TYPE (exp)))
     return exp;
   return NULL_TREE;
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index 6eb3f71bbd3..85ef9745593 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -180,6 +180,10 @@  gimple_ranger::range_on_edge (irange &r, edge e, tree name)
   int_range_max edge_range;
   gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name)));
 
+  // Do not process values along abnormal or EH edges.
+  if (e->flags & (EDGE_ABNORMAL|EDGE_EH))
+    return false;
+
   unsigned idx;
   if ((idx = tracer.header ("range_on_edge (")))
     {
diff --git a/gcc/gimple-ssa-evrp.c b/gcc/gimple-ssa-evrp.c
index 437f19471f1..7f2055501a0 100644
--- a/gcc/gimple-ssa-evrp.c
+++ b/gcc/gimple-ssa-evrp.c
@@ -137,6 +137,9 @@  public:
 
   tree value_of_expr (tree name, gimple *s = NULL) OVERRIDE
   {
+    // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
+    if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
+      return NULL;
     tree ret = m_ranger->value_of_expr (name, s);
     if (!ret && supported_pointer_equiv_p (name))
       ret = m_pta->get_equiv (name);
@@ -145,6 +148,9 @@  public:
 
   tree value_on_edge (edge e, tree name) OVERRIDE
   {
+    // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
+    if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
+      return NULL;
     tree ret = m_ranger->value_on_edge (e, name);
     if (!ret && supported_pointer_equiv_p (name))
       ret = m_pta->get_equiv (name);
@@ -153,6 +159,9 @@  public:
 
   tree value_of_stmt (gimple *s, tree name = NULL) OVERRIDE
   {
+    // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
+    if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
+      return NULL;
     return m_ranger->value_of_stmt (s, name);
   }
 
@@ -283,9 +292,15 @@  tree
 hybrid_folder::value_of_expr (tree op, gimple *stmt)
 {
   tree evrp_ret = evrp_folder::value_of_expr (op, stmt);
-  tree ranger_ret = m_ranger->value_of_expr (op, stmt);
-  if (!ranger_ret && supported_pointer_equiv_p (op))
-    ranger_ret = m_pta->get_equiv (op);
+  tree ranger_ret;
+  if (TREE_CODE (op) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
+    ranger_ret = NULL;
+  else
+    {
+      ranger_ret = m_ranger->value_of_expr (op, stmt);
+      if (!ranger_ret && supported_pointer_equiv_p (op))
+	ranger_ret = m_pta->get_equiv (op);
+    }
   return choose_value (evrp_ret, ranger_ret);
 }
 
@@ -295,9 +310,15 @@  hybrid_folder::value_on_edge (edge e, tree op)
   // Call evrp::value_of_expr directly.  Otherwise another dual call is made
   // via hybrid_folder::value_of_expr, but without an edge.
   tree evrp_ret = evrp_folder::value_of_expr (op, NULL);
-  tree ranger_ret = m_ranger->value_on_edge (e, op);
-  if (!ranger_ret && supported_pointer_equiv_p (op))
-    ranger_ret = m_pta->get_equiv (op);
+  tree ranger_ret;
+  if (TREE_CODE (op) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
+    ranger_ret = NULL;
+  else
+    {
+      ranger_ret = m_ranger->value_on_edge (e, op);
+      if (!ranger_ret && supported_pointer_equiv_p (op))
+	ranger_ret = m_pta->get_equiv (op);
+    }
   return choose_value (evrp_ret, ranger_ret);
 }
 
@@ -312,7 +333,11 @@  hybrid_folder::value_of_stmt (gimple *stmt, tree op)
   else
     evrp_ret = NULL_TREE;
 
-  tree ranger_ret = m_ranger->value_of_stmt (stmt, op);
+  tree ranger_ret;
+  if (op && TREE_CODE (op) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
+    ranger_ret = NULL;
+  else
+    ranger_ret = m_ranger->value_of_stmt (stmt, op);
   return choose_value (evrp_ret, ranger_ret);
 }
 
diff --git a/gcc/value-query.cc b/gcc/value-query.cc
index 730a2149275..ab133aab114 100644
--- a/gcc/value-query.cc
+++ b/gcc/value-query.cc
@@ -416,8 +416,9 @@  get_range_global (irange &r, tree name)
 value_range
 gimple_range_global (tree name)
 {
-  gcc_checking_assert (gimple_range_ssa_p (name));
   tree type = TREE_TYPE (name);
+  gcc_checking_assert (TREE_CODE (name) == SSA_NAME
+		       && irange::supports_type_p (type));
 
   if (SSA_NAME_IS_DEFAULT_DEF (name) || (cfun && cfun->after_inlining)
       || is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
-- 
2.17.2