Re: [COMMITTED] Use EDGE_EXECUTABLE in ranger and return UNDEFINED for those edges.
On 9/22/21 4:25 AM, Richard Biener wrote: On Tue, Sep 21, 2021 at 3:50 PM Andrew MacLeod wrote: On 9/21/21 9:32 AM, Richard Biener wrote: On Tue, Sep 21, 2021 at 2:57 PM Andrew MacLeod wrote: On 9/21/21 2:14 AM, Richard Biener wrote: On Tue, Sep 21, 2021 at 8:09 AM Richard Biener wrote: On Tue, Sep 21, 2021 at 12:01 AM Andrew MacLeod via Gcc-patches 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
Re: [COMMITTED] Use EDGE_EXECUTABLE in ranger and return UNDEFINED for those edges.
On Tue, Sep 21, 2021 at 3:50 PM Andrew MacLeod wrote: > > On 9/21/21 9:32 AM, Richard Biener wrote: > > On Tue, Sep 21, 2021 at 2:57 PM Andrew MacLeod wrote: > >> On 9/21/21 2:14 AM, Richard Biener wrote: > >>> On Tue, Sep 21, 2021 at 8:09 AM Richard Biener > >>> wrote: > On Tue, Sep 21, 2021 at 12:01 AM Andrew MacLeod via Gcc-patches > 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. > > >
Re: [COMMITTED] Use EDGE_EXECUTABLE in ranger and return UNDEFINED for those edges.
On 9/21/21 9:32 AM, Richard Biener wrote: On Tue, Sep 21, 2021 at 2:57 PM Andrew MacLeod wrote: On 9/21/21 2:14 AM, Richard Biener wrote: On Tue, Sep 21, 2021 at 8:09 AM Richard Biener wrote: On Tue, Sep 21, 2021 at 12:01 AM Andrew MacLeod via Gcc-patches 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.
Re: [COMMITTED] Use EDGE_EXECUTABLE in ranger and return UNDEFINED for those edges.
On Tue, Sep 21, 2021 at 2:57 PM Andrew MacLeod wrote: > > On 9/21/21 2:14 AM, Richard Biener wrote: > > On Tue, Sep 21, 2021 at 8:09 AM Richard Biener > > wrote: > >> On Tue, Sep 21, 2021 at 12:01 AM Andrew MacLeod via Gcc-patches > >> 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 > >>> >
Re: [COMMITTED] Use EDGE_EXECUTABLE in ranger and return UNDEFINED for those edges.
On 9/21/21 2:14 AM, Richard Biener wrote: On Tue, Sep 21, 2021 at 8:09 AM Richard Biener wrote: On Tue, Sep 21, 2021 at 12:01 AM Andrew MacLeod via Gcc-patches 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
Re: [COMMITTED] Use EDGE_EXECUTABLE in ranger and return UNDEFINED for those edges.
On Tue, Sep 21, 2021 at 8:09 AM Richard Biener wrote: > > On Tue, Sep 21, 2021 at 12:01 AM Andrew MacLeod via Gcc-patches > 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 > >
Re: [COMMITTED] Use EDGE_EXECUTABLE in ranger and return UNDEFINED for those edges.
On Tue, Sep 21, 2021 at 12:01 AM Andrew MacLeod via Gcc-patches 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 >