On Tue, Nov 23, 2021 at 6:04 PM Andrew MacLeod via Gcc-patches <gcc-patches@gcc.gnu.org> wrote: > > This is the second patch in the series. > > Ranger uses its own API to recursively satisfy dependencies. When > range_of_stmt is called on _1482 = _1154 + _1177; it picks up the > ranges of _1154 and _1177 from it's cache. If those statements have not > been seen yet, it recursively calls range_of_stmt on each one to resolve > the answer. Each main API call can trigger up to 5 other calls to get > to the next API point: > > gimple_ranger::fold_range_internal (...) > gimple_ranger::range_of_stmt (_1154,...) > gimple_ranger::range_of_expr (_1154,....) > fold_using_range::range_of_range_op (..) > fold_using_range::fold_stmt (...) > gimple_ranger::fold_range_internal (...) > gimple_ranger::range_of_stmt (_1482,...) > > For a normal forward walk, values tend to already be in the cache, but > when we try to answer a range_on_edge question on a back edge, it can > trigger a very long series of queries. I spent some time analyzing > these patterns, and found that regardless of which API entry point was > used, ultimately range_of_stmt is invoked in a predictable order to > initiate the cache values. > > This patch implements a dependency resolver which when range_of_stmt > uses when it is called on something which does not have a cache entry > yet (thus the disambiguation of the temporal failure vs lack of cache > entry in the previous patch) > > This looks at each operand, and if that operand does not have a cache > entry, pushes it on a stack. Names are popped from the stack and > fold_using_range() is invoked once all the operands have been > resolved. When we do get to call fold_using_range::fold_stmt(), we are > sure the operands are cached and the value will simply be calculated. > This is ultimately the exact series of events that would have happened > had the main API been used... except we don't involve the call stack > anymore for each one. > > Well, mostly :-). For this fix, we only do this with operands of stmts > which have a range-ops handler.. meaning we do not use the API for > anything range-ops understands. We will still use the main API for > resolving PHIS and other statements as they are encountered. We could > do this for PHIS as well, but for the most part it was the chains of > stmts within a block that were causing the vast majority of the issue. > If we later discover large chains of PHIs are causing issues as well, > then I can easily add them to this as well. I avoided them this time > because there is extra overhead involved in traversing all the PHI > arguments extra times. Sticking with range-ops limits us to 2 operands > to check, and the overhead is very minimal. > > I have tested this with PHIs as well and we could just include them > upfront. The overhead is more than doubled, but the increased compile > time of a VRP pass is still under 1%. > > Bootstrapped on x86_64-pc-linux-gnu with no regressions. OK?
OK. Richard. > Andrew > > >
