backthreader: use a BB flag for the visited-block set
Replaces hash set with a basic block flag for tracking visited blocks, improving performance.
The backwards threader pass in GCC previously used a hash_set<basic_block> to track visited blocks during path exploration. This incurred a hash lookup cost on entry and exit of each basic block. This commit replaces the hash set with a simple flag on the basic block itself, as the set’s usage is confined to the current function and the control flow graph doesn’t change. This change reduces overhead and simplifies the implementation.
In Details
The back_threader's find_paths_to_names function previously used m_visited_bbs (a hash_set<basic_block>) to track visited blocks during path traversal. This commit replaces it with m_visited_flag (a bb_auto_flag). Since the flag is only used to check membership within the current function's CFG and is reset appropriately by find_paths_to_names (making the per-block reset in maybe_thread_block redundant), the flag offers better performance with no loss of correctness. It avoids heap allocation and hash lookups.
- backthreader
- A GCC pass that performs backward analysis, starting from a destination and working backward through the control flow graph.
- basic block
- A sequence of instructions in a program with a single entry point and a single exit point. Control flow graphs are composed of basic blocks.
- CFG
- Control Flow Graph, a directed graph representing all execution paths within a program or function. Nodes are basic blocks, and edges represent jumps or transfers of control.
- hash set
- A data structure that stores unique elements and provides fast average-time complexity for insertion, deletion, and lookup operations using a hash function.