https://gcc.gnu.org/bugzilla/show_bug.cgi?id=125758
--- Comment #7 from Andrew Macleod <amacleod at redhat dot com> --- (In reply to Richard Biener from comment #6) > Looks like we need some kind of recursion limit here? Ugh. This appears to be an unfortunate interaction that prevents the dependency pre-fill mechanism from avoiding deep stack recursion. The testcase contains thousands of blocks like this: <bb 10319>: _30968 = _30965 + 48; _30969 = _30966 + -1; ... <bb 10320>: _30971 = _30968 + 48; _30972 = _30969 + -1; ... <bb 10321>: _30974 = _30971 + 48; _30975 = _30972 + -1; ... There is also a PHI node with thousands of arguments referring to the + -1 SSA names from each block, such as _30969, _30972, _30975, and so on. These names form a cross-block dependency chain where each value depends on the value from the previous block. Normally this is not a problem. The dependency pre-calculator is designed to ensure that dependencies are evaluated before the requested SSA name goes through the normal demand-driven query path. It pops names from a stack, writes an initial global value to avoid cycles, checks whether each dependency already has a global value, and pushes missing dependencies onto the stack so they are processed first. This normally gives dependencies older timestamps than the value currently being calculated. The problem here is the PHI node. For PHIs, we do not analyze each argument’s dependencies before pushing them. We simply push each PHI argument onto the stack to ensure that each argument has a calculated value before calculating the PHI. In this case, the PHI arguments happen to be processed in bottom-to-top order. So the PHI causes us to process _30975, then _30972, then _30969. When _30975 is processed, it depends on _30972, but _30972 is already on the calculation stack and already has a temporary global value written to avoid cycles. As a result, _30975 is calculated and saved first. Then _30972 is popped and calculated, and the same pattern repeats. The issue is that when _30972 is later written, its timestamp becomes newer than _30975. After pre-filling completes, the requested value of _30975 is calculated normally. Usually all dependencies are already satisfied with older timestamps, so the cached values are used and recursion is avoided. In this case, however, the dependencies now have newer timestamps than the requested value, so the normal query path decides the value is stale and recurses through the whole chain anyway. Had the PHI arguments been processed in the opposite order, the timestamps would have lined up naturally and the pre-fill would have done its job. I considered ordering the PHI arguments, but that does not seem worthwhile. This is not normally an issue, and paying the cost to order every large PHI would probably be wasted work in the common case. I have a thought which I am going to look into over the next couple of days. I think the weakness is in the timestamp mechanism. Right now we cannot distinguish between when a value was recalculated and when the value actually changed. When a dependency has a newer timestamp, we currently recalculate and always update the LHS timestamp, even if the resulting value is identical to the previous one. The alternative would be to leave the old timestamp if the value did not change, but then the dependency would remain newer and we would end up recalculating the same value every time it is requested. I am going to experiment with splitting this into two timestamps: a value timestamp, representing when the current value actually changed a recalculation timestamp, representing when the expression was last evaluated If a recalculation produces the same value, only the recalculation timestamp would be updated, while the value timestamp would remain unchanged. In the problematic PHI case above, this should avoid repeated recursion. Once the value stabilizes, subsequent requests would see that the value itself is not stale, even if dependencies have been revisited. Names depending on this value would also avoid unnecessary updates because the value timestamp would not change. This should be fairly cheap and may also address a few other marginal timestamp-related issues that have shown up in the past.
