GHC's graph representations do not provide access to predecessors
Some algorithms that operate on control-flow graphs---in particular, the "node-splitting" algorithm that converts an irreducible control-flow graph to a reducible control-flow graph---require access to the predecessors of a node. But GHC's representations of graphs, such as the CmmGraph
and the Graph
type of GHC.CmmToAsm.CFG.Dominators
, represent a graph as a finite map from each node to its successors. This representation provides fast access only to the successors of a node, not the predecessors.
When the graph in question is unchanging, as it is for some dominator and loop analyses, it is not too difficult to compute the successor relation and to invert it, providing fast access to the predecessors. But when the graph is changing, as is the case in the node splitter, maintaining the two relations can become a little awkward.
This issue could be addressed ad hoc in every part of the compiler that needs to manipulate graphs, but a better solution might be to have a common representation that is already designed to deal with such issues. Such as, for example, the representation in Martin Erwig's Functional Graph Library.
(N.B. the issue is mentioned as one of the bullet points in #21200 (closed).)