| Message ID | d68f5646-1823-1a47-7baf-467c9471c3e1@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | PR tree-optimization/100512: Once a range becomes constant, make it invariant. | expand |
On Tue, May 18, 2021 at 1:23 AM Andrew MacLeod via Gcc-patches <gcc-patches@gcc.gnu.org> wrote: > > The code in PR 100512 triggers an interaction between ranger and the > propagation engine related to undefined values. > > I put the detailed analysis in the PR, but it boils down to the early > VRP pass has concluded that something is a constant and can be replaced, > and removes the definition expecting the constant to be propagated > everywhere. > > > If the code is in an undefined region that the CFG is going to remove, > we can find impossible situations,a nd ranger then changes that value ot > UNDEFINED.. because, well, it is. But then the propagation engine > panics because it doesnt have a constant any more, so odesnt replace it, > and now we have a used but not defined value. > > Once we get to a globally constant range where further refinements can > only end up in an UNDEFINED state, stop further evaluating the range. > This is typically in places which are about to be removed by CFG cleanup > anyway, and it will make the propagation engine happy with no surprises. Yeah, the propagation engine and EVRP as I know it relies on not visiting "unexecutable" (as figured by anaysis) paths in the CFG and thus considering edges coming from such regions not contributing conditions/values/etc. that would cause such "undefinedness" to appear. Not sure how it works with ranger, maybe that can as well get a mode where it does only traverse EDGE_EXECUTABLE edges. Might be a bit difficult since IIRC it works with SSA edges and not CFG edges. > Bootstraps on x86_64-pc-linux-gnu with no regressions, and fixes the PR. So that means the lattice isn't an optimistic lattice, right? EVRPs wasn't optimistic either, but VRPs is/was. Whatever this means in this context ;) Richard. > Pushed. > > Andrew > > >
On 5/18/21 3:22 AM, Richard Biener wrote: > On Tue, May 18, 2021 at 1:23 AM Andrew MacLeod via Gcc-patches > <gcc-patches@gcc.gnu.org> wrote: >> The code in PR 100512 triggers an interaction between ranger and the >> propagation engine related to undefined values. >> >> I put the detailed analysis in the PR, but it boils down to the early >> VRP pass has concluded that something is a constant and can be replaced, >> and removes the definition expecting the constant to be propagated >> everywhere. >> >> >> If the code is in an undefined region that the CFG is going to remove, >> we can find impossible situations,a nd ranger then changes that value ot >> UNDEFINED.. because, well, it is. But then the propagation engine >> panics because it doesnt have a constant any more, so odesnt replace it, >> and now we have a used but not defined value. >> >> Once we get to a globally constant range where further refinements can >> only end up in an UNDEFINED state, stop further evaluating the range. >> This is typically in places which are about to be removed by CFG cleanup >> anyway, and it will make the propagation engine happy with no surprises. > Yeah, the propagation engine and EVRP as I know it relies on not visiting > "unexecutable" (as figured by anaysis) paths in the CFG and thus considering > edges coming from such regions not contributing conditions/values/etc. that > would cause such "undefinedness" to appear. Not sure how it works with > ranger, maybe that can as well get a mode where it does only traverse > EDGE_EXECUTABLE edges. Might be a bit difficult since IIRC it works > with SSA edges and not CFG edges. Well it does do CFG based work as well, and I do not currently check EDGE_EXECUTABLE... I just tried checking the EXECUTABLE_EDGE flag and not processing it, but it doesn't resolve the problem. I think its because the edge has not been determined unexecutable until after the pass is done.. which is too late. > >> Bootstraps on x86_64-pc-linux-gnu with no regressions, and fixes the PR. > So that means the lattice isn't an optimistic lattice, right? EVRPs wasn't > optimistic either, but VRPs is/was. Whatever this means in this context ;) > > It is optimistic, this just tells it to stop being optimistic if we get to a constant so we don't mess up propagation. Any further evaluation which causes it to become undefined has to be a result of this being an undefined hunk of code, and I *think* that it will be eliminated by the CFG cleanup due to change elsewhere. The only thing I can imagine where we might miss something is if the ssa_name we are leaving as a constant now were used elsewhere in a PHI node. That PHI node will get a constant instead of an undefined range.. and we would no longer make the optimistic assumption that that PHI edge no longer contributes to the result. When the block of code/edge is then eliminated by CFG cleanup, then that constant would be removed since the edge is gone... but it would delay finding that situation. We'll find out when we look at replacing VRP if that actually happens anywhere. Eventually I hope to tweak the propagation engine (or use an alternative) so that deciding something is a constant and eliminating the definition doesn't cause problems if we later discover the result is actually undefined.. that what this boils down to. Following the linear decision making of substituting constants doesn't work quite so well in a more optimistic iterative environment. That will make us fully optimistic again. Andrew
On 5/18/21 3:22 AM, Richard Biener wrote: > On Tue, May 18, 2021 at 1:23 AM Andrew MacLeod via Gcc-patches > <gcc-patches@gcc.gnu.org> wrote: >> The code in PR 100512 triggers an interaction between ranger and the >> propagation engine related to undefined values. >> >> I put the detailed analysis in the PR, but it boils down to the early >> VRP pass has concluded that something is a constant and can be replaced, >> and removes the definition expecting the constant to be propagated >> everywhere. >> >> >> If the code is in an undefined region that the CFG is going to remove, >> we can find impossible situations,a nd ranger then changes that value ot >> UNDEFINED.. because, well, it is. But then the propagation engine >> panics because it doesnt have a constant any more, so odesnt replace it, >> and now we have a used but not defined value. >> >> Once we get to a globally constant range where further refinements can >> only end up in an UNDEFINED state, stop further evaluating the range. >> This is typically in places which are about to be removed by CFG cleanup >> anyway, and it will make the propagation engine happy with no surprises. > Yeah, the propagation engine and EVRP as I know it relies on not visiting > "unexecutable" (as figured by anaysis) paths in the CFG and thus considering > edges coming from such regions not contributing conditions/values/etc. that > would cause such "undefinedness" to appear. Not sure how it works with > ranger, maybe that can as well get a mode where it does only traverse > EDGE_EXECUTABLE edges. Might be a bit difficult since IIRC it works > with SSA edges and not CFG edges. > >> Bootstraps on x86_64-pc-linux-gnu with no regressions, and fixes the PR. > So that means the lattice isn't an optimistic lattice, right? EVRPs wasn't > optimistic either, but VRPs is/was. Whatever this means in this context ;) > > Richard. > Comparing in a gcc build, and out of the 4586 extra cases ranger finds across 400 files, this patch does cost us 1 of them. So I suspect it probably costs a few more compared to VRP proper. May have to deal with the propagation issue better when we get to that point. Andrew
On Tue, May 18, 2021 at 6:35 PM Andrew MacLeod <amacleod@redhat.com> wrote: > > On 5/18/21 3:22 AM, Richard Biener wrote: > > On Tue, May 18, 2021 at 1:23 AM Andrew MacLeod via Gcc-patches > > <gcc-patches@gcc.gnu.org> wrote: > >> The code in PR 100512 triggers an interaction between ranger and the > >> propagation engine related to undefined values. > >> > >> I put the detailed analysis in the PR, but it boils down to the early > >> VRP pass has concluded that something is a constant and can be replaced, > >> and removes the definition expecting the constant to be propagated > >> everywhere. > >> > >> > >> If the code is in an undefined region that the CFG is going to remove, > >> we can find impossible situations,a nd ranger then changes that value ot > >> UNDEFINED.. because, well, it is. But then the propagation engine > >> panics because it doesnt have a constant any more, so odesnt replace it, > >> and now we have a used but not defined value. > >> > >> Once we get to a globally constant range where further refinements can > >> only end up in an UNDEFINED state, stop further evaluating the range. > >> This is typically in places which are about to be removed by CFG cleanup > >> anyway, and it will make the propagation engine happy with no surprises. > > Yeah, the propagation engine and EVRP as I know it relies on not visiting > > "unexecutable" (as figured by anaysis) paths in the CFG and thus considering > > edges coming from such regions not contributing conditions/values/etc. that > > would cause such "undefinedness" to appear. Not sure how it works with > > ranger, maybe that can as well get a mode where it does only traverse > > EDGE_EXECUTABLE edges. Might be a bit difficult since IIRC it works > > with SSA edges and not CFG edges. > > > Well it does do CFG based work as well, and I do not currently check > EDGE_EXECUTABLE... I just tried checking the EXECUTABLE_EDGE flag and > not processing it, but it doesn't resolve the problem. I think its > because the edge has not been determined unexecutable until after the > pass is done.. which is too late. > > > > >> Bootstraps on x86_64-pc-linux-gnu with no regressions, and fixes the PR. > > So that means the lattice isn't an optimistic lattice, right? EVRPs wasn't > > optimistic either, but VRPs is/was. Whatever this means in this context ;) > > > > > It is optimistic, this just tells it to stop being optimistic if we get > to a constant so we don't mess up propagation. Guess I'm confused - in classical terms an optimistic lattice propagator only allows downward transitions UNDEF -> CONSTANT -> VARYING while a non-optimistic one doesn't need to iterate and thus by definition has no lattice "transition" other than from the initial VARYING to the possibly non-VARYING but final state. > Any further evaluation > which causes it to become undefined has to be a result of this being an > undefined hunk of code, and I *think* that it will be eliminated by the > CFG cleanup due to change elsewhere. > > The only thing I can imagine where we might miss something is if the > ssa_name we are leaving as a constant now were used elsewhere in a PHI > node. That PHI node will get a constant instead of an undefined > range.. and we would no longer make the optimistic assumption that that > PHI edge no longer contributes to the result. When the block of > code/edge is then eliminated by CFG cleanup, then that constant would be > removed since the edge is gone... but it would delay finding that > situation. We'll find out when we look at replacing VRP if that > actually happens anywhere. > > Eventually I hope to tweak the propagation engine (or use an > alternative) so that deciding something is a constant and eliminating > the definition doesn't cause problems if we later discover the result is > actually undefined.. that what this boils down to. Following the linear > decision making of substituting constants doesn't work quite so well in > a more optimistic iterative environment. That will make us fully > optimistic again. > > Andrew > > > > > >
On 5/19/21 5:13 AM, Richard Biener wrote: > On Tue, May 18, 2021 at 6:35 PM Andrew MacLeod <amacleod@redhat.com> wrote: >> On 5/18/21 3:22 AM, Richard Biener wrote: >>> On Tue, May 18, 2021 at 1:23 AM Andrew MacLeod via Gcc-patches >>> <gcc-patches@gcc.gnu.org> wrote: >>>> The code in PR 100512 triggers an interaction between ranger and the >>>> propagation engine related to undefined values. >>>> >>>> I put the detailed analysis in the PR, but it boils down to the early >>>> VRP pass has concluded that something is a constant and can be replaced, >>>> and removes the definition expecting the constant to be propagated >>>> everywhere. >>>> >>>> >>>> If the code is in an undefined region that the CFG is going to remove, >>>> we can find impossible situations,a nd ranger then changes that value ot >>>> UNDEFINED.. because, well, it is. But then the propagation engine >>>> panics because it doesnt have a constant any more, so odesnt replace it, >>>> and now we have a used but not defined value. >>>> >>>> Once we get to a globally constant range where further refinements can >>>> only end up in an UNDEFINED state, stop further evaluating the range. >>>> This is typically in places which are about to be removed by CFG cleanup >>>> anyway, and it will make the propagation engine happy with no surprises. >>> Yeah, the propagation engine and EVRP as I know it relies on not visiting >>> "unexecutable" (as figured by anaysis) paths in the CFG and thus considering >>> edges coming from such regions not contributing conditions/values/etc. that >>> would cause such "undefinedness" to appear. Not sure how it works with >>> ranger, maybe that can as well get a mode where it does only traverse >>> EDGE_EXECUTABLE edges. Might be a bit difficult since IIRC it works >>> with SSA edges and not CFG edges. >> >> Well it does do CFG based work as well, and I do not currently check >> EDGE_EXECUTABLE... I just tried checking the EXECUTABLE_EDGE flag and >> not processing it, but it doesn't resolve the problem. I think its >> because the edge has not been determined unexecutable until after the >> pass is done.. which is too late. >> >>>> Bootstraps on x86_64-pc-linux-gnu with no regressions, and fixes the PR. >>> So that means the lattice isn't an optimistic lattice, right? EVRPs wasn't >>> optimistic either, but VRPs is/was. Whatever this means in this context ;) >>> >>> >> It is optimistic, this just tells it to stop being optimistic if we get >> to a constant so we don't mess up propagation. > Guess I'm confused - in classical terms an optimistic lattice > propagator only allows downward transitions UNDEF -> CONSTANT -> VARYING > while a non-optimistic one doesn't need to iterate and thus by definition > has no lattice "transition" other than from the initial VARYING to the > possibly non-VARYING but final state. well, its not really a lattice, but to use those terms, we have aspects of both. We start with the global range which is calculated as best we can. That forms the initial value (which may well be varying). We may later find a better range for one or more inputs and recalculate that global range and refine it. It only ever moves towards the UNDEFINED state from that point.. When we initially propagate a value through the CFG via the on-entry cache, we start with all affected blocks at UNDEFINED, mark the block(s) which may generate/affect a range. We then calculate the range at each of those points, and push those values thru the CFG. the range on entry at each block is the union of all ranges on predecessor edges. This means the propagator iteratively moves things from UNDEFINED towards the initial global value... which provides the optimistic aspect of the algorithm when setting the values in blocks. If we later update the range of the ssa-name because we've discovered a more refined range for an input, we "push" that new range into the cache. That change is propagated thru the affected blocks in the CFG. We look at each successor and see if this new value would affect its value, and push it there if needed. That is the iterative aspect. At this point, we are back to taking an existing known range, and further refining it. The on-demand part is that we only visit blocks that are needed between the request and the Definition. We may later ask for a range in a different part of the CFG, and we do the initial propagation from UNDEFINED on just those blocks which haven't been previously calcluated and do the optimistic propagation. That is what is happening in that PR. we have started with a range, evolved it to a constant, and then further refined it to undefined. In general terms, I would say that is our model, but we have an optimistic propagator which catches all the stuff VRP does with it optimistic lattice. I will do a full on writeup of this eventually... complete with drawings :-) Andrew
commit 3f476de7fd274f619a0b04c2e2f7077ee8ab17a5
Author: Andrew MacLeod <amacleod@redhat.com>
Date: Mon May 17 15:53:39 2021 -0400
Once a range becomes constant, make it invariant.
Once a range is forced to a constant globally, simply make it invariant.
Unify this with the code which makes non-zero pointer ranges invariant.
gcc/
PR tree-optimization/100512
* gimple-range-cache.cc (ranger_cache::set_global_range): Mark const
and non-zero pointer ranges as invariant.
* gimple-range.cc (gimple_ranger::range_of_stmt): Remove pointer
processing from here.
gcc/testsuite/
PR tree-optimization/100512
* gcc.dg/pr100512.c: New.
diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 60e5d66c52d..2c922e32913 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -703,8 +703,19 @@ ranger_cache::set_global_range (tree name, const irange &r)
propagate_updated_value (name, bb);
}
- // Mark the value as up-to-date.
- m_temporal->set_timestamp (name);
+ // Constants no longer need to tracked. Any further refinement has to be
+ // undefined. Propagation works better with constants. PR 100512.
+ // Pointers which resolve to non-zero also do not need
+ // tracking in the cache as they will never change. See PR 98866.
+ // Otherwise mark the value as up-to-date.
+ if (r.singleton_p ()
+ || (POINTER_TYPE_P (TREE_TYPE (name)) && r.nonzero_p ()))
+ {
+ set_range_invariant (name);
+ m_temporal->set_always_current (name);
+ }
+ else
+ m_temporal->set_timestamp (name);
}
// Register a dependency on DEP to name. If the timestamp for DEP is ever
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index 5b288d8e6a7..710bc7f9632 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -1082,11 +1082,6 @@ gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name)
r.intersect (tmp);
m_cache.set_global_range (name, r);
- // Pointers which resolve to non-zero at the defintion point do not need
- // tracking in the cache as they will never change. See PR 98866.
- if (POINTER_TYPE_P (TREE_TYPE (name)) && r.nonzero_p ())
- m_cache.set_range_invariant (name);
-
return true;
}
diff --git a/gcc/testsuite/gcc.dg/pr100512.c b/gcc/testsuite/gcc.dg/pr100512.c
new file mode 100644
index 00000000000..70b90e04be9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr100512.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -w" } */
+
+#include <stdint.h>
+int a;
+void b() {
+ int16_t *c;
+ uint16_t d = 2;
+ if (0 == d) {
+ uint64_t e;
+ uint64_t *f = &e;
+ for (;;) {
+ if (e += 0 >= 0)
+ for (;;)
+ ;
+ g:
+ for (; a;) {
+ int16_t i = &d;
+ *c = i && *f;
+ }
+ }
+ }
+ goto g;
+}
+