A "supernode" stands for a collection of one or more nodes (basic
blocks) that have been coalesced by the Hecht-Ullman algorithm. A
collection in a supernode constitutes a
reducible subgraph of a
control-flow graph. (When an entire control-flow graph is collapsed to
a single supernode, the flow graph is reducible.)
The idea of node splitting is to collapse a control-flow graph down to
a single supernode, then materialize (`
inflate') the
reducible equivalent graph from that supernode. The
Supernode
class defines only the methods needed to collapse; rematerialization
is the responsibility of the client.
During the Hecht-Ullman algorithm, every supernode has a unique entry
point, which is given by
superLabel. But this invariant is not
guaranteed by the class methods and is not a law of the class. The
mapLabels function rewrites all labels that appear in a
supernode (both definitions and uses). The
freshen function
replaces every appearance of a
defined label with a fresh
label. (Appearances include both definitions and uses.)
Laws:
superLabel (n <> n') == superLabel n blocks (n
<> n') == blocks n union blocks n' mapLabels f (n
<> n') = mapLabels f n <> mapLabels f n' mapLabels id ==
id mapLabels (f . g) == mapLabels f . mapLabels g
(We expect
freshen to distribute over
<>, but
because of the fresh names involved, formulating a precise law is a
bit challenging.)