| Message ID | d1ac90ce-0aa9-f342-2b5e-f4ae01517056@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | [COMMITTED] Use EDGE_EXECUTABLE in ranger and return UNDEFINED for those edges. | expand |
On Tue, Sep 21, 2021 at 12:01 AM Andrew MacLeod via Gcc-patches <gcc-patches@gcc.gnu.org> wrote: > > > The patch sets the EXECUTABLE property on edges like VRP does, and then > removes that flag when an edge is determined to be un-executable. > > This information is then used to return UNDEFINED for any requests on > un-executable edges, and to register equivalencies if all executable > edges of a PHI node are the same SSA_NAME. > > This catches up a number of the cases VRP gets that ranger was missing, > and reduces the EVRP discrepancies to almost 0. > > On a side note, is there any interest/value in reversing the meaning of > that flag? It seems to me that we could assume edges are EXECUTABLE by > default, then set a NON_EXECUTABLE flag when a pass determines the edge > cannot be executed. This would rpevent a number fo passes from having > to loop through all the edges and set the EXECUTABLE property... It > just seems backwards to me. The flag is simply not kept up-to-date and it's the passes responsibility to make use of it (aka install a default state upon entry). To me not having EDGE_EXECUTABLE set on entry is more natural for optimistic propagation passes, but yes, if you do on-demand greedy processing then you need a conservative default. But then how do you denote a 'VARYING' (executable) state that may not drop back to 'CONSTANT" (not executable)? For optimistic propagation EDGE_EXECUTABLE set is simply the varying state and since we never clear it again there's no chance of oscillation. Richard. > Anyway, bootstrapped on x86_64-pc-linux-gnu with no regressions. pushed. > > Andrew >
On Tue, Sep 21, 2021 at 8:09 AM Richard Biener <richard.guenther@gmail.com> wrote: > > On Tue, Sep 21, 2021 at 12:01 AM Andrew MacLeod via Gcc-patches > <gcc-patches@gcc.gnu.org> wrote: > > > > > > The patch sets the EXECUTABLE property on edges like VRP does, and then > > removes that flag when an edge is determined to be un-executable. > > > > This information is then used to return UNDEFINED for any requests on > > un-executable edges, and to register equivalencies if all executable > > edges of a PHI node are the same SSA_NAME. > > > > This catches up a number of the cases VRP gets that ranger was missing, > > and reduces the EVRP discrepancies to almost 0. > > > > On a side note, is there any interest/value in reversing the meaning of > > that flag? It seems to me that we could assume edges are EXECUTABLE by > > default, then set a NON_EXECUTABLE flag when a pass determines the edge > > cannot be executed. This would rpevent a number fo passes from having > > to loop through all the edges and set the EXECUTABLE property... It > > just seems backwards to me. > > The flag is simply not kept up-to-date and it's the passes responsibility to > make use of it (aka install a default state upon entry). > > To me not having EDGE_EXECUTABLE set on entry is more natural > for optimistic propagation passes, but yes, if you do on-demand greedy > processing then you need a conservative default. But then how do you > denote a 'VARYING' (executable) state that may not drop back to 'CONSTANT" > (not executable)? For optimistic propagation EDGE_EXECUTABLE set is > simply the varying state and since we never clear it again there's no chance > of oscillation. Btw, I fail to see how the patch makes ranger assure a sane initial state of EDGE_EXECUTABLE (or make its use conditional). Is the code you patched not also used on-demand? That is, are you sure you're not running into wrong-code issues if you for example in passes.c:execute_one_pass right before passes initialize EDGE_EXECUTABLE to a random state on each edge of the function? Richard. > Richard. > > > Anyway, bootstrapped on x86_64-pc-linux-gnu with no regressions. pushed. > > > > Andrew > >
On 9/21/21 2:14 AM, Richard Biener wrote: > On Tue, Sep 21, 2021 at 8:09 AM Richard Biener > <richard.guenther@gmail.com> wrote: >> On Tue, Sep 21, 2021 at 12:01 AM Andrew MacLeod via Gcc-patches >> <gcc-patches@gcc.gnu.org> wrote: >>> >>> The patch sets the EXECUTABLE property on edges like VRP does, and then >>> removes that flag when an edge is determined to be un-executable. >>> >>> This information is then used to return UNDEFINED for any requests on >>> un-executable edges, and to register equivalencies if all executable >>> edges of a PHI node are the same SSA_NAME. >>> >>> This catches up a number of the cases VRP gets that ranger was missing, >>> and reduces the EVRP discrepancies to almost 0. >>> >>> On a side note, is there any interest/value in reversing the meaning of >>> that flag? It seems to me that we could assume edges are EXECUTABLE by >>> default, then set a NON_EXECUTABLE flag when a pass determines the edge >>> cannot be executed. This would rpevent a number fo passes from having >>> to loop through all the edges and set the EXECUTABLE property... It >>> just seems backwards to me. >> The flag is simply not kept up-to-date and it's the passes responsibility to >> make use of it (aka install a default state upon entry). >> >> To me not having EDGE_EXECUTABLE set on entry is more natural >> for optimistic propagation passes, but yes, if you do on-demand greedy >> processing then you need a conservative default. But then how do you >> denote a 'VARYING' (executable) state that may not drop back to 'CONSTANT" >> (not executable)? For optimistic propagation EDGE_EXECUTABLE set is >> simply the varying state and since we never clear it again there's no chance >> of oscillation. Different model, we dont have a lattice whereby we track state and move form one to another.. we just track currently best known values for everything and recalculate them when the old values are stale. We move the edge to unexecutable when those values allow us to rewrite a branch such that an edge can no longer be taken. everything else is executable. Any values on an unexecutable edge are then considered UNDEFINED when combined with other values.. > Btw, I fail to see how the patch makes ranger assure a sane initial state of > EDGE_EXECUTABLE (or make its use conditional). Is the code you patched > not also used on-demand? THe constructor for a ranger makes everything executable to start. Calls the same routine VRP does. gimple_ranger::gimple_ranger () : tracer ("") { @@ -41,6 +42,7 @@ gimple_ranger::gimple_ranger () : tracer ("") m_oracle = m_cache.oracle (); if (dump_file && (param_evrp_mode & EVRP_MODE_TRACE)) tracer.enable_trace (); + set_all_edges_as_executable (cfun); } and EVRP also goes to this same effort at the start: evrp_range_analyzer::evrp_range_analyzer (bool update_global_ranges) : stack (10), m_update_global_ranges (update_global_ranges) { edge e; edge_iterator ei; basic_block bb; FOR_EACH_BB_FN (bb, cfun) { bb->flags &= ~BB_VISITED; FOR_EACH_EDGE (e, ei, bb->preds) e->flags |= EDGE_EXECUTABLE; } } Ranger isn't doing anything different than the ciurrent VRP's do, so I don't see any distinguishing difference between optimistic and pessimistic. We can guarantee that we will only clear the EXECUTABLE flag if the edge is 100% guaranteed to be not executable. Perhaps other passes/approaches aren't able to provide such guarantees in which case having a persistent flag wouldnt work very well.. > That is, are you sure you're not running into wrong-code issues if you > for example in passes.c:execute_one_pass right before passes > initialize EDGE_EXECUTABLE to a random state on each edge of the function? > > Richard. We dont really have multiple instances running, and I'm not sure that should be encouraged either. Worst case is that a new instantiation would "undo" some of the edges that may have been marked as unexecutable We'd only run into problems if we try to use a ranger from some pass that is using EXECUTABLE in a different way.. ie,. to not mean EXECUTABLE. but that seems even more problematic to me, and those uses ought to be fixed. >> Richard. >> >>> Anyway, bootstrapped on x86_64-pc-linux-gnu with no regressions. pushed. >>> >>> Andrew >>>
On Tue, Sep 21, 2021 at 2:57 PM Andrew MacLeod <amacleod@redhat.com> wrote: > > On 9/21/21 2:14 AM, Richard Biener wrote: > > On Tue, Sep 21, 2021 at 8:09 AM Richard Biener > > <richard.guenther@gmail.com> wrote: > >> On Tue, Sep 21, 2021 at 12:01 AM Andrew MacLeod via Gcc-patches > >> <gcc-patches@gcc.gnu.org> wrote: > >>> > >>> The patch sets the EXECUTABLE property on edges like VRP does, and then > >>> removes that flag when an edge is determined to be un-executable. > >>> > >>> This information is then used to return UNDEFINED for any requests on > >>> un-executable edges, and to register equivalencies if all executable > >>> edges of a PHI node are the same SSA_NAME. > >>> > >>> This catches up a number of the cases VRP gets that ranger was missing, > >>> and reduces the EVRP discrepancies to almost 0. > >>> > >>> On a side note, is there any interest/value in reversing the meaning of > >>> that flag? It seems to me that we could assume edges are EXECUTABLE by > >>> default, then set a NON_EXECUTABLE flag when a pass determines the edge > >>> cannot be executed. This would rpevent a number fo passes from having > >>> to loop through all the edges and set the EXECUTABLE property... It > >>> just seems backwards to me. > >> The flag is simply not kept up-to-date and it's the passes responsibility to > >> make use of it (aka install a default state upon entry). > >> > >> To me not having EDGE_EXECUTABLE set on entry is more natural > >> for optimistic propagation passes, but yes, if you do on-demand greedy > >> processing then you need a conservative default. But then how do you > >> denote a 'VARYING' (executable) state that may not drop back to 'CONSTANT" > >> (not executable)? For optimistic propagation EDGE_EXECUTABLE set is > >> simply the varying state and since we never clear it again there's no chance > >> of oscillation. > Different model, we dont have a lattice whereby we track state and move > form one to another.. we just track currently best known values for > everything and recalculate them when the old values are stale. We move > the edge to unexecutable when those values allow us to rewrite a branch > such that an edge can no longer be taken. everything else is executable. > Any values on an unexecutable edge are then considered UNDEFINED when > combined with other values.. > > > Btw, I fail to see how the patch makes ranger assure a sane initial state of > > EDGE_EXECUTABLE (or make its use conditional). Is the code you patched > > not also used on-demand? > > THe constructor for a ranger makes everything executable to start. > Calls the same routine VRP does. > > gimple_ranger::gimple_ranger () : tracer ("") > { > @@ -41,6 +42,7 @@ gimple_ranger::gimple_ranger () : tracer ("") > m_oracle = m_cache.oracle (); > if (dump_file && (param_evrp_mode & EVRP_MODE_TRACE)) > tracer.enable_trace (); > + set_all_edges_as_executable (cfun); > } Ah, I see. I had the impression that with ranger we can now do a cheap query everywhere on the range of an SSA name. But then the above is O(CFG size)... I guess I'm confusing something - but yes, clearly in a ranger VRP "pass" that all sounds OK. Richard. > and EVRP also goes to this same effort at the start: > > evrp_range_analyzer::evrp_range_analyzer (bool update_global_ranges) > : stack (10), m_update_global_ranges (update_global_ranges) > { > edge e; > edge_iterator ei; > basic_block bb; > FOR_EACH_BB_FN (bb, cfun) > { > bb->flags &= ~BB_VISITED; > FOR_EACH_EDGE (e, ei, bb->preds) > e->flags |= EDGE_EXECUTABLE; > } > } > > Ranger isn't doing anything different than the ciurrent VRP's do, so I > don't see any distinguishing difference between optimistic and > pessimistic. We can guarantee that we will only clear the EXECUTABLE > flag if the edge is 100% guaranteed to be not executable. Perhaps other > passes/approaches aren't able to provide such guarantees in which case > having a persistent flag wouldnt work very well.. > > > That is, are you sure you're not running into wrong-code issues if you > > for example in passes.c:execute_one_pass right before passes > > initialize EDGE_EXECUTABLE to a random state on each edge of the function? > > > > Richard. > > We dont really have multiple instances running, and I'm not sure that > should be encouraged either. Worst case is that a new instantiation > would "undo" some of the edges that may have been marked as unexecutable > > We'd only run into problems if we try to use a ranger from some pass > that is using EXECUTABLE in a different way.. ie,. to not mean > EXECUTABLE. but that seems even more problematic to me, and those uses > ought to be fixed. > > > > >> Richard. > >> > >>> Anyway, bootstrapped on x86_64-pc-linux-gnu with no regressions. pushed. > >>> > >>> Andrew > >>> >
On 9/21/21 9:32 AM, Richard Biener wrote: > On Tue, Sep 21, 2021 at 2:57 PM Andrew MacLeod <amacleod@redhat.com> wrote: >> On 9/21/21 2:14 AM, Richard Biener wrote: >>> On Tue, Sep 21, 2021 at 8:09 AM Richard Biener >>> <richard.guenther@gmail.com> wrote: >>>> On Tue, Sep 21, 2021 at 12:01 AM Andrew MacLeod via Gcc-patches >>>> <gcc-patches@gcc.gnu.org> wrote: >>>>> The patch sets the EXECUTABLE property on edges like VRP does, and then >>>>> removes that flag when an edge is determined to be un-executable. >>>>> >>>>> This information is then used to return UNDEFINED for any requests on >>>>> un-executable edges, and to register equivalencies if all executable >>>>> edges of a PHI node are the same SSA_NAME. >>>>> >>>>> This catches up a number of the cases VRP gets that ranger was missing, >>>>> and reduces the EVRP discrepancies to almost 0. >>>>> >>>>> On a side note, is there any interest/value in reversing the meaning of >>>>> that flag? It seems to me that we could assume edges are EXECUTABLE by >>>>> default, then set a NON_EXECUTABLE flag when a pass determines the edge >>>>> cannot be executed. This would rpevent a number fo passes from having >>>>> to loop through all the edges and set the EXECUTABLE property... It >>>>> just seems backwards to me. >>>> The flag is simply not kept up-to-date and it's the passes responsibility to >>>> make use of it (aka install a default state upon entry). >>>> >>>> To me not having EDGE_EXECUTABLE set on entry is more natural >>>> for optimistic propagation passes, but yes, if you do on-demand greedy >>>> processing then you need a conservative default. But then how do you >>>> denote a 'VARYING' (executable) state that may not drop back to 'CONSTANT" >>>> (not executable)? For optimistic propagation EDGE_EXECUTABLE set is >>>> simply the varying state and since we never clear it again there's no chance >>>> of oscillation. >> Different model, we dont have a lattice whereby we track state and move >> form one to another.. we just track currently best known values for >> everything and recalculate them when the old values are stale. We move >> the edge to unexecutable when those values allow us to rewrite a branch >> such that an edge can no longer be taken. everything else is executable. >> Any values on an unexecutable edge are then considered UNDEFINED when >> combined with other values.. >> >>> Btw, I fail to see how the patch makes ranger assure a sane initial state of >>> EDGE_EXECUTABLE (or make its use conditional). Is the code you patched >>> not also used on-demand? >> THe constructor for a ranger makes everything executable to start. >> Calls the same routine VRP does. >> >> gimple_ranger::gimple_ranger () : tracer ("") >> { >> @@ -41,6 +42,7 @@ gimple_ranger::gimple_ranger () : tracer ("") >> m_oracle = m_cache.oracle (); >> if (dump_file && (param_evrp_mode & EVRP_MODE_TRACE)) >> tracer.enable_trace (); >> + set_all_edges_as_executable (cfun); >> } > Ah, I see. I had the impression that with ranger we can now > do a cheap query everywhere on the range of an SSA name. But then > the above is O(CFG size)... One of the reasons I'd like to see it persistent :-) We could alternatively add another new one, something like EDGE_NEVER_EXECUTED which is cleared by default when created and only ranger/other interested passes utilize it and it is kept persistent. Just seems more appropriate to "fix" the current flag. I took a quick look at that, but it seemed like one or more of the propagation passes may use the flag for other nefarious purposes. It would require fixing everyone to maintain the value properly. Queries are still "cheap", but there are varying amounts of lookups and allocations that are done. If the lack of a persistent EXECUTABLE edge flag continues, I may make some further tweaks and make it sensitive to whether EXECUTABLE is to be looked at or not and perhaps only have the VRPs initiate that. I prefer avoiding different modes when possible tho. Currently most/all uses of ranger are instantiated and used for the duration of a pass, so the O(cfg) is pretty minimal with all the CFG traversing and caching required. > > I guess I'm confusing something - but yes, clearly in a ranger VRP "pass" > that all sounds OK. > > Richard. >
On Tue, Sep 21, 2021 at 3:50 PM Andrew MacLeod <amacleod@redhat.com> wrote: > > On 9/21/21 9:32 AM, Richard Biener wrote: > > On Tue, Sep 21, 2021 at 2:57 PM Andrew MacLeod <amacleod@redhat.com> wrote: > >> On 9/21/21 2:14 AM, Richard Biener wrote: > >>> On Tue, Sep 21, 2021 at 8:09 AM Richard Biener > >>> <richard.guenther@gmail.com> wrote: > >>>> On Tue, Sep 21, 2021 at 12:01 AM Andrew MacLeod via Gcc-patches > >>>> <gcc-patches@gcc.gnu.org> wrote: > >>>>> The patch sets the EXECUTABLE property on edges like VRP does, and then > >>>>> removes that flag when an edge is determined to be un-executable. > >>>>> > >>>>> This information is then used to return UNDEFINED for any requests on > >>>>> un-executable edges, and to register equivalencies if all executable > >>>>> edges of a PHI node are the same SSA_NAME. > >>>>> > >>>>> This catches up a number of the cases VRP gets that ranger was missing, > >>>>> and reduces the EVRP discrepancies to almost 0. > >>>>> > >>>>> On a side note, is there any interest/value in reversing the meaning of > >>>>> that flag? It seems to me that we could assume edges are EXECUTABLE by > >>>>> default, then set a NON_EXECUTABLE flag when a pass determines the edge > >>>>> cannot be executed. This would rpevent a number fo passes from having > >>>>> to loop through all the edges and set the EXECUTABLE property... It > >>>>> just seems backwards to me. > >>>> The flag is simply not kept up-to-date and it's the passes responsibility to > >>>> make use of it (aka install a default state upon entry). > >>>> > >>>> To me not having EDGE_EXECUTABLE set on entry is more natural > >>>> for optimistic propagation passes, but yes, if you do on-demand greedy > >>>> processing then you need a conservative default. But then how do you > >>>> denote a 'VARYING' (executable) state that may not drop back to 'CONSTANT" > >>>> (not executable)? For optimistic propagation EDGE_EXECUTABLE set is > >>>> simply the varying state and since we never clear it again there's no chance > >>>> of oscillation. > >> Different model, we dont have a lattice whereby we track state and move > >> form one to another.. we just track currently best known values for > >> everything and recalculate them when the old values are stale. We move > >> the edge to unexecutable when those values allow us to rewrite a branch > >> such that an edge can no longer be taken. everything else is executable. > >> Any values on an unexecutable edge are then considered UNDEFINED when > >> combined with other values.. > >> > >>> Btw, I fail to see how the patch makes ranger assure a sane initial state of > >>> EDGE_EXECUTABLE (or make its use conditional). Is the code you patched > >>> not also used on-demand? > >> THe constructor for a ranger makes everything executable to start. > >> Calls the same routine VRP does. > >> > >> gimple_ranger::gimple_ranger () : tracer ("") > >> { > >> @@ -41,6 +42,7 @@ gimple_ranger::gimple_ranger () : tracer ("") > >> m_oracle = m_cache.oracle (); > >> if (dump_file && (param_evrp_mode & EVRP_MODE_TRACE)) > >> tracer.enable_trace (); > >> + set_all_edges_as_executable (cfun); > >> } > > Ah, I see. I had the impression that with ranger we can now > > do a cheap query everywhere on the range of an SSA name. But then > > the above is O(CFG size)... > > One of the reasons I'd like to see it persistent :-) We could > alternatively add another new one, something like EDGE_NEVER_EXECUTED > which is cleared by default when created and only ranger/other > interested passes utilize it and it is kept persistent. Just seems > more appropriate to "fix" the current flag. I took a quick look at that, > but it seemed like one or more of the propagation passes may use the > flag for other nefarious purposes. It would require fixing everyone to > maintain the value properly. > > Queries are still "cheap", but there are varying amounts of lookups > and allocations that are done. If the lack of a persistent EXECUTABLE > edge flag continues, I may make some further tweaks and make it > sensitive to whether EXECUTABLE is to be looked at or not and perhaps > only have the VRPs initiate that. I prefer avoiding different modes > when possible tho. > > Currently most/all uses of ranger are instantiated and used for the > duration of a pass, so the O(cfg) is pretty minimal with all the CFG > traversing and caching required. Btw, there's auto_edge_flag (fun) that gets you a new flag allocated and it's supposed to be cleared on all edges (but I don't think we actually verify that - I suppose we should). The downside is you have to clear it after use - but it would in theory be possible to elide that by keeping a set of "dirty" flags and only clear all of those when we run out of non-dirty free flags. Richard. > > > > > I guess I'm confusing something - but yes, clearly in a ranger VRP "pass" > > that all sounds OK. > > > > Richard. > > >
On 9/22/21 4:25 AM, Richard Biener wrote: > On Tue, Sep 21, 2021 at 3:50 PM Andrew MacLeod <amacleod@redhat.com> wrote: >> On 9/21/21 9:32 AM, Richard Biener wrote: >>> On Tue, Sep 21, 2021 at 2:57 PM Andrew MacLeod <amacleod@redhat.com> wrote: >>>> On 9/21/21 2:14 AM, Richard Biener wrote: >>>>> On Tue, Sep 21, 2021 at 8:09 AM Richard Biener >>>>> <richard.guenther@gmail.com> wrote: >>>>>> On Tue, Sep 21, 2021 at 12:01 AM Andrew MacLeod via Gcc-patches >>>>>> <gcc-patches@gcc.gnu.org> wrote: >>>>>>> The patch sets the EXECUTABLE property on edges like VRP does, and then >>>>>>> removes that flag when an edge is determined to be un-executable. >>>>>>> >>>>>>> This information is then used to return UNDEFINED for any requests on >>>>>>> un-executable edges, and to register equivalencies if all executable >>>>>>> edges of a PHI node are the same SSA_NAME. >>>>>>> >>>>>>> This catches up a number of the cases VRP gets that ranger was missing, >>>>>>> and reduces the EVRP discrepancies to almost 0. >>>>>>> >>>>>>> On a side note, is there any interest/value in reversing the meaning of >>>>>>> that flag? It seems to me that we could assume edges are EXECUTABLE by >>>>>>> default, then set a NON_EXECUTABLE flag when a pass determines the edge >>>>>>> cannot be executed. This would rpevent a number fo passes from having >>>>>>> to loop through all the edges and set the EXECUTABLE property... It >>>>>>> just seems backwards to me. >>>>>> The flag is simply not kept up-to-date and it's the passes responsibility to >>>>>> make use of it (aka install a default state upon entry). >>>>>> >>>>>> To me not having EDGE_EXECUTABLE set on entry is more natural >>>>>> for optimistic propagation passes, but yes, if you do on-demand greedy >>>>>> processing then you need a conservative default. But then how do you >>>>>> denote a 'VARYING' (executable) state that may not drop back to 'CONSTANT" >>>>>> (not executable)? For optimistic propagation EDGE_EXECUTABLE set is >>>>>> simply the varying state and since we never clear it again there's no chance >>>>>> of oscillation. >>>> Different model, we dont have a lattice whereby we track state and move >>>> form one to another.. we just track currently best known values for >>>> everything and recalculate them when the old values are stale. We move >>>> the edge to unexecutable when those values allow us to rewrite a branch >>>> such that an edge can no longer be taken. everything else is executable. >>>> Any values on an unexecutable edge are then considered UNDEFINED when >>>> combined with other values.. >>>> >>>>> Btw, I fail to see how the patch makes ranger assure a sane initial state of >>>>> EDGE_EXECUTABLE (or make its use conditional). Is the code you patched >>>>> not also used on-demand? >>>> THe constructor for a ranger makes everything executable to start. >>>> Calls the same routine VRP does. >>>> >>>> gimple_ranger::gimple_ranger () : tracer ("") >>>> { >>>> @@ -41,6 +42,7 @@ gimple_ranger::gimple_ranger () : tracer ("") >>>> m_oracle = m_cache.oracle (); >>>> if (dump_file && (param_evrp_mode & EVRP_MODE_TRACE)) >>>> tracer.enable_trace (); >>>> + set_all_edges_as_executable (cfun); >>>> } >>> Ah, I see. I had the impression that with ranger we can now >>> do a cheap query everywhere on the range of an SSA name. But then >>> the above is O(CFG size)... >> One of the reasons I'd like to see it persistent :-) We could >> alternatively add another new one, something like EDGE_NEVER_EXECUTED >> which is cleared by default when created and only ranger/other >> interested passes utilize it and it is kept persistent. Just seems >> more appropriate to "fix" the current flag. I took a quick look at that, >> but it seemed like one or more of the propagation passes may use the >> flag for other nefarious purposes. It would require fixing everyone to >> maintain the value properly. >> >> Queries are still "cheap", but there are varying amounts of lookups >> and allocations that are done. If the lack of a persistent EXECUTABLE >> edge flag continues, I may make some further tweaks and make it >> sensitive to whether EXECUTABLE is to be looked at or not and perhaps >> only have the VRPs initiate that. I prefer avoiding different modes >> when possible tho. >> >> Currently most/all uses of ranger are instantiated and used for the >> duration of a pass, so the O(cfg) is pretty minimal with all the CFG >> traversing and caching required. > Btw, there's auto_edge_flag (fun) that gets you a new flag > allocated and it's supposed to be cleared on all edges > (but I don't think we actually verify that - I suppose we should). > The downside is you have to clear it after use - but it would > in theory be possible to elide that by keeping a set of > "dirty" flags and only clear all of those when we run out of > non-dirty free flags. > > Richard. Huh, I did not know that. Yeah, that looks like it might be a decent solution.. I'll take a closer look today. Thanks Andrew
From 73cf73af2392e00917de042a4692f6a0b6329ee8 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod <amacleod@redhat.com> Date: Tue, 24 Aug 2021 12:13:24 -0400 Subject: [PATCH 2/2] Use EDGE_EXECUTABLE in ranger and return UNDEFINED for those edges. If an incoming edge is UNDEFINED, don't process it. Track if other edges equate to a single value, and add an equivalence if appropriate. gcc/ * gimple-range-fold.cc (fold_using_range::range_of_phi): Ignore undefined edges, apply an equivalence if appropriate. * gimple-range-gori.cc (gori_compute::outgoing_edge_range_p): Return UNDEFINED if EDGE_EXECUTABLE is not set. * gimple-range.cc (gimple_ranger::gimple_ranger): Set all edges as EXECUTABLE upon startup. (gimple_ranger::range_on_edge): Return UNDEFINED for edges without EDGE_EXECUTABLE set. * vr-values.c (set_and_propagate_unexecutable): New. (simplify_using_ranges::fold_cond): Call set_and_propagate. (simplify_using_ranges::simplify_switch_using_ranges): Ditto. * vr-values.h: Add prototype. gcc/testsuite/ * gcc.dg/tree-ssa/evrp-ignore.c: New. --- gcc/gimple-range-fold.cc | 47 ++++++++++++++++++--- gcc/gimple-range-gori.cc | 25 ++++------- gcc/gimple-range.cc | 36 +++++++++++----- gcc/testsuite/gcc.dg/tree-ssa/evrp-ignore.c | 28 ++++++++++++ gcc/vr-values.c | 39 ++++++++++++++++- gcc/vr-values.h | 1 + 6 files changed, 140 insertions(+), 36 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/evrp-ignore.c diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index 997d02dd4b9..80cc5c0dc0c 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -760,6 +760,10 @@ fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src) if (!type) return false; + // Track if all executable arguments are the same. + tree single_arg = NULL_TREE; + bool seen_arg = false; + // Start with an empty range, unioning in each argument's range. r.set_undefined (); for (x = 0; x < gimple_phi_num_args (phi); x++) @@ -767,19 +771,48 @@ fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src) tree arg = gimple_phi_arg_def (phi, x); edge e = gimple_phi_arg_edge (phi, x); - // Register potential dependencies for stale value tracking. - if (gimple_range_ssa_p (arg) && src.gori ()) - src.gori ()->register_dependency (phi_def, arg); - // Get the range of the argument on its edge. src.get_phi_operand (arg_range, arg, e); - // If we're recomputing the argument elsewhere, try to refine it. - r.union_ (arg_range); + + if (!arg_range.undefined_p ()) + { + // Register potential dependencies for stale value tracking. + r.union_ (arg_range); + if (gimple_range_ssa_p (arg) && src.gori ()) + src.gori ()->register_dependency (phi_def, arg); + + // Track if all arguments are the same. + if (!seen_arg) + { + seen_arg = true; + single_arg = arg; + } + else if (single_arg != arg) + single_arg = NULL_TREE; + } + // Once the value reaches varying, stop looking. - if (r.varying_p ()) + if (r.varying_p () && single_arg == NULL_TREE) break; } + // If the PHI boils down to a single effective argument, look at it. + if (single_arg) + { + // Symbolic arguments are equivalences. + if (gimple_range_ssa_p (single_arg)) + src.register_relation (phi, EQ_EXPR, phi_def, single_arg); + else if (src.get_operand (arg_range, single_arg) + && arg_range.singleton_p ()) + { + // Numerical arguments that are a constant can be returned as + // the constant. This can help fold later cases where even this + // constant might have been UNDEFINED via an unreachable edge. + r = arg_range; + return true; + } + } + // If SCEV is available, query if this PHI has any knonwn values. if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def))) { diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index f78829595dc..f5a35287bed 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -1214,6 +1214,15 @@ gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name, int_range_max lhs; unsigned idx; + if ((e->flags & EDGE_EXECUTABLE) == 0) + { + r.set_undefined (); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Outgoing edge %d->%d unexecutable.\n", + e->src->index, e->dest->index); + return true; + } + gcc_checking_assert (gimple_range_ssa_p (name)); // Determine if there is an outgoing edge. gimple *stmt = outgoing.edge_range_p (lhs, e); @@ -1221,22 +1230,6 @@ gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name, return false; fur_stmt src (stmt, &q); - - // If this edge is never taken, return undefined. - gcond *gc = dyn_cast<gcond *> (stmt); - if (gc) - { - if (((e->flags & EDGE_TRUE_VALUE) && gimple_cond_false_p (gc)) - || ((e->flags & EDGE_FALSE_VALUE) && gimple_cond_true_p (gc))) - { - r.set_undefined (); - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Outgoing edge %d->%d unexecutable.\n", - e->src->index, e->dest->index); - return true; - } - } - // If NAME can be calculated on the edge, use that. if (is_export_p (name, e->src)) { diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index d74cea3451e..625d13647f7 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -34,6 +34,7 @@ along with GCC; see the file COPYING3. If not see #include "cfgloop.h" #include "tree-scalar-evolution.h" #include "gimple-range.h" +#include "domwalk.h" gimple_ranger::gimple_ranger () : tracer ("") { @@ -41,6 +42,7 @@ gimple_ranger::gimple_ranger () : tracer ("") m_oracle = m_cache.oracle (); if (dump_file && (param_evrp_mode & EVRP_MODE_TRACE)) tracer.enable_trace (); + set_all_edges_as_executable (cfun); } bool @@ -164,10 +166,6 @@ 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))); - // PHI arguments can be constants, catch these here. - if (!gimple_range_ssa_p (name)) - return range_of_expr (r, name); - unsigned idx; if ((idx = tracer.header ("range_on_edge ("))) { @@ -175,16 +173,32 @@ gimple_ranger::range_on_edge (irange &r, edge e, tree name) fprintf (dump_file, ") on edge %d->%d\n", e->src->index, e->dest->index); } - range_on_exit (r, e->src, name); - gcc_checking_assert (r.undefined_p () - || range_compatible_p (r.type(), TREE_TYPE (name))); + // Check to see if the edge is executable. + if ((e->flags & EDGE_EXECUTABLE) == 0) + { + r.set_undefined (); + if (idx) + tracer.trailer (idx, "range_on_edge [Unexecutable] ", true, + name, r); + return true; + } - // Check to see if NAME is defined on edge e. - if (m_cache.range_on_edge (edge_range, e, name)) - r.intersect (edge_range); + bool res = true; + if (!gimple_range_ssa_p (name)) + res = range_of_expr (r, name); + else + { + range_on_exit (r, e->src, name); + gcc_checking_assert (r.undefined_p () + || range_compatible_p (r.type(), TREE_TYPE (name))); + + // Check to see if NAME is defined on edge e. + if (m_cache.range_on_edge (edge_range, e, name)) + r.intersect (edge_range); + } if (idx) - tracer.trailer (idx, "range_on_edge", true, name, r); + tracer.trailer (idx, "range_on_edge", res, name, r); return true; } diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp-ignore.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp-ignore.c new file mode 100644 index 00000000000..9bfaed6a50a --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp-ignore.c @@ -0,0 +1,28 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp -fno-tree-fre -fdisable-tree-ethread" } */ + +void kill(void); + +void foo (int x, int y, int z) +{ + // Establish y = [-INF, 54] + if (y < 55) + return; + + // Establish z == x + if (z != x) + return; + + // EVRP should transform this to if (0 != 0) + if (y < 30) + x = 0; + + // # x_1 = PHI <x_5(D)(6), 0(7)> + // The earlier transformation should make the edge from bb7 + // unexecutable, allowing x_1 == x_5 to be registered, and + // then fold away this condition as well. + if (x != z) + kill(); + +} +/* { dg-final { scan-tree-dump-not "kill" "evrp" } } */ diff --git a/gcc/vr-values.c b/gcc/vr-values.c index c999ca80f03..3b8d0674471 100644 --- a/gcc/vr-values.c +++ b/gcc/vr-values.c @@ -3454,6 +3454,32 @@ range_fits_type_p (const value_range *vr, return true; } +// Clear edge E of EDGE_EXECUTABLE (it is unexecutable). If it wasn't +// previously clear, propagate to successor blocks if appropriate. + +void +simplify_using_ranges::set_and_propagate_unexecutable (edge e) +{ + // If EXECUUTABLE is already clear, we're done. + if ((e->flags & EDGE_EXECUTABLE) == 0) + return; + + e->flags &= ~EDGE_EXECUTABLE; + + // Check if the destination block needs to propagate the property. + basic_block bb = e->dest; + + // If any entry edge is marked EXECUTABLE, we are done. + edge_iterator ei; + FOR_EACH_EDGE (e, ei, bb->preds) + if (e->flags & EDGE_EXECUTABLE) + return; + + // This block is also unexecutable, propagate to all exit edges as well. + FOR_EACH_EDGE (e, ei, bb->succs) + set_and_propagate_unexecutable (e); +} + /* If COND can be folded entirely as TRUE or FALSE, rewrite the conditional as such, and return TRUE. */ @@ -3467,18 +3493,27 @@ simplify_using_ranges::fold_cond (gcond *cond) if (TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME && TREE_CODE (gimple_cond_rhs (cond)) != SSA_NAME) return false; - + edge e0 = EDGE_SUCC (gimple_bb (cond), 0); + edge e1 = EDGE_SUCC (gimple_bb (cond), 1); if (r.zero_p ()) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "\nPredicate evaluates to: 0\n"); gimple_cond_make_false (cond); + if (e0->flags & EDGE_TRUE_VALUE) + set_and_propagate_unexecutable (e0); + else + set_and_propagate_unexecutable (e1); } else { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "\nPredicate evaluates to: 1\n"); gimple_cond_make_true (cond); + if (e0->flags & EDGE_FALSE_VALUE) + set_and_propagate_unexecutable (e0); + else + set_and_propagate_unexecutable (e1); } update_stmt (cond); return true; @@ -3769,7 +3804,7 @@ simplify_using_ranges::simplify_switch_using_ranges (gswitch *stmt) fprintf (dump_file, "removing unreachable case label\n"); } to_remove_edges.safe_push (e); - e->flags &= ~EDGE_EXECUTABLE; + set_and_propagate_unexecutable (e); e->flags |= EDGE_IGNORE; } diff --git a/gcc/vr-values.h b/gcc/vr-values.h index 7fdefef2fdf..46939081c61 100644 --- a/gcc/vr-values.h +++ b/gcc/vr-values.h @@ -66,6 +66,7 @@ private: tree vrp_evaluate_conditional_warnv_with_ops_using_ranges (enum tree_code, tree, tree, bool *, gimple *s); + void set_and_propagate_unexecutable (edge e); void cleanup_edges_and_switches (void); /* Vectors of edges that need removing and switch statements that -- 2.17.2