Backthreader skips candidate scan when no path can start it.
Optimizes the backthreader by skipping candidate scans if no registered paths start on the same edge, improving performance by up to 96.7% in some cases.
The backthreader’s adjust_paths_after_duplication function previously performed a quadratic scan for candidate paths on every duplication. This commit optimizes this by maintaining a count of registered paths starting on each edge. If a count is one, it means no other paths start there, and the scan is skipped, significantly reducing runtime for code with many registered paths.
In Details
This change optimizes back_jt_path_registry::adjust_paths_after_duplication. The function iterates through registered paths to find candidates that start on the same edge as the path being adjusted. By adding jt_path_registry::first_edge_count, it can quickly determine if any other paths share the starting edge. If not, the expensive scan is skipped, improving performance where gimple-match-* and insn-* generated code creates numerous registered paths.
- backthreader
- A GCC pass that optimizes control flow by identifying and threading common execution paths, aiming to reduce execution time and improve instruction cache locality.
- candidate scan
- In the context of the backthreader, this refers to the process of searching for existing registered paths that could potentially be merged or used to optimize the current path being processed.
- duplication
- Refers to a state or operation within the backthreader where a path is duplicated, possibly to explore alternative execution flows or optimize different segments of code.
- registered path
- A control flow path that has been identified and stored within the backthreader's registry for potential reuse or optimization.