https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109695
--- Comment #22 from Andrew Macleod <amacleod at redhat dot com> --- OK, I've finished with my analysis. There are multiple vectors of attack here, and we should do them all. Some where already on my radar for this release anyway, but this gives a nice tidy place to track them all. First, the increased size of int_range_max needs to be addressed. Short term we could resolve this simply by making int_range<25> instead of int_range<255>. That of course papers over the real problem, but still needs addressing. Aldy and I are discussing. Next, prefill_stmt_dependencies exists to short-cut long chains of calls to range_of_stmt by managing it on a stack. It uses a *lot* less stack calls, but it is still subject to re-evaluating statements whose dependencies are updated. ssa-names that have not been calculated have no entry in rangers global cache. As soon as they get an entry, they are also given a monotonically increasing timestamp. This allows us to quickly see if a dependence has been updated since a value was last calculated. prefill_stmt_dependencies pushes un-evaluated names from statements onto a stack as they are seen, and evaluating those first, then finally evaluating the stmt. _1012 = PHI <_1947(2), _1011(1016)> we push _1012, then _1947 and _1011 on the stack to evaluate. _1011 and _1947 will be evaluated before _1012, thus allowing for a decent calculation of _1012. We avoid cycles by providing an initial value for a name when it is first registered. When we provide this initial value, we also set the timestamp to "always current" so we don't end up with flip flopping dependencies in cycles causing each other to be recalculated. When we store the newly calculated value, we set a proper timestamp. So, on to the issues that need to be addressed. 1) We unconditionally write the new value calculated to the global cache once the dependencies are resolved. This gives it a new timestamp, and thus makes any other values which used it out of date when they really aren't. This causes a lot of extra churn. TODO: This should be changed to only update it when it actually changes. Client code shouldn't have to do this, it shoud be handled right int the cache's set_global_value (). 2) The initial value we choose is simply VARYING. This is why 1) alone won't solve this problem. when we push _1947 on the stack, we set it to VARYING.. then proceed down along chain of other dependencies Driven by _1011 which are resolved first. When we get back to _1947 finally, we see: _1947 = 77; which evaluated to [77, 77], and is this different than VARYING, and thus would cause a new timestamp to be created even if (1) were implemented. TODO: When setting the initial value in the cache, rather than being lazy and using varying, we should invoke fold_stmt using get_global_range_query (). This will fold the stmt and produce a result which resolved any ssa-names just using known global values. THis should not be expensive, and gives us a reasonable first approximation. And for cases like _1947, the final result as well. 3) When we first set the intial value for _1947 and give it the ALWAYS_CURRENT timestamp, we lose the context of when the initial value was set. So even with 1) & 2) implemented, we are *still* need to set a timestamp for it when its finally calculated, even though it is the same as the original. This will cause any names already evaluated using its range to become stale because we can't leave it as ALWAYS_CURRENT. (There are other places where we do need to be able to re-evaluate.. there are 2 testsuite failures caused by this if we just leave it as always_current) TODO: Alter the implementation of ALWAYS_CURRENT such that a name is also given a timestamp at the time of setting the initial value. Then set_global_range() will clear the ALWAYS_CURRENT tag unconditionally, but leave the original timestamp if the value hasn't changed. This will then provide an accurate timestamp for the initial_value. 4) Finally, There are multiple ssa-names that are dependent on _1947. Given the stack oriented mechanism, the first such case will push the value on the stack to be resolved, and all the other names that depend on it will use the initial value. When we finally get back to evaluating it, if it DID come out different, then all those names would again be stale, and potentially get recalculated down the road. TODO: This impact could be reduced by increasing the priority of its evaluation. Instead of waiting for evaluation all the way back to the bottom of the stack for _1947, when a new stmt is dependent on it, we could instead move it to the top of the stack for consideration. We'll still be resolving dependencies, but it will be properly evaluated sooner than later. Cycles will have to be avoided by not re prioritizing any dependencies on statement which have been "bumped" like this. You have to put a stake in the ground at some point and use what you have. Summary: These 4 changes should fix the algorithmic issues exposed, and combined with fixing the memory footprint of int_range-max, we should see a big different in cases like this. The overhead of doing the extra work is likely to be offset by saving in not redoing work. we shall see. I will get to these when I return from vacation
