Fix sorted_array_from_bitmap_set to compute value graph entries first
Improve topological sorting of expressions by ensuring value graph entries are computed before building the sorted set, reducing iteration.
The sorted_array_from_bitmap_set function in tree-ssa-pre.cc has been modified to fix an issue where it failed to correctly topologically sort expressions. Previously, it lacked knowledge of the value graph’s entries. The update ensures these entries are computed first, which should reduce the amount of iteration needed for sorting.
In Details
The sorted_array_from_bitmap_set function, used within tree-ssa-pre.cc, aims to provide a topological sort of expressions represented in a bitmap set. This commit addresses a flaw where the required knowledge of the value graph's entries was missing, leading to incomplete sorting. By pre-computing these entries, the pass can now correctly order expressions, potentially improving the efficiency of subsequent optimizations that rely on this ordering.
- topological sorting
- An ordering of nodes in a directed acyclic graph such that for every directed edge from node A to node B, node A comes before node B in the ordering. In compilers, this is often used to order operations or expressions based on their dependencies.
- bitmap set
- A data structure that represents a set of elements using a bit array. Each bit corresponds to a potential element, and its value (0 or 1) indicates whether the element is present in the set. This is memory-efficient for dense sets.
- value graph
- A graph representation where nodes represent values or expressions, and edges represent relationships between them, such as data flow or dependencies. It's used in compiler optimizations to analyze and manipulate program values.
- tree-ssa-pre
- A compiler pass within GCC that performs optimizations on the SSA (Static Single Assignment) form of the code. 'pre' likely refers to 'pre-pass' or 'preprocessing' within the SSA framework, focusing on initial transformations.