Relation query changes to db style frontier search
GCC's relation oracle adopts a 'db style' frontier search, improving performance by performing transitivity discovery on demand instead of eagerly.
GCC’s relation oracle has been refactored to use a ‘db style’ frontier search, moving away from eager transitivity computation. The previous approach scaled poorly with the number of registered relations, often leading to facts being dropped. The new method computes transitivity only when queried, using a bidirectional dominator search bounded by a work limit. This makes the cost proportional to actual queries and prevents unnecessary work.
In Details
The value-relation.cc and value-query.cc are significantly reworked to replace the eager register_relation transitivity expansion with a demand-driven frontier search. This involves new structures (frontier_data) and methods (dom_oracle::relation_search) that employ a bidirectional dominator search. The goal is to bound query cost by the number of actual queries, improving performance and memory usage, especially for dense relation sets. Deprecated parameters and functionalities related to eager transitives are removed.
- relation oracle
- A component in GCC that answers queries about relationships between values, such as equality or inequality, used in optimizations.
- transitivity
- A property where if relation R holds between A and B, and between B and C, then R also holds between A and C. E.g., if a=b and b=c, then a=c.
- dominator search
- An algorithm to find relationships or paths within a control flow graph by utilizing the dominance relation between basic blocks.
- frontier search
- A search algorithm used in graph traversal, particularly in dominance algorithms, that explores nodes adjacent to the currently processed set.
- ranger-debug
- A debugging parameter for GCC's range analysis and propagation tools, allowing finer control and visibility into their operation.