ghc-9.10.3: The GHC API

Safe Haskell | None
Language | GHC2021

GHC.Cmm.Reducibility

Description

Test a Cmm control-flow graph for reducibility. And provide a function that, when given an arbitrary control-flow graph, returns an equivalent, reducible control-flow graph. The equivalent graph is obtained by "splitting" (copying) nodes of the original graph. The resulting equivalent graph has the same dynamic behavior as the original, but it is larger.

Documentation uses the language of control-flow analysis, in which a basic block is called a "node." These "nodes" are `CmmBlock`s or equivalent; they have nothing to do with a `CmmNode`.

For more on reducibility and related analyses and algorithms, see Note [Reducibility resources]

Synopsis

- data Reducibility
  - = Reducible
  - | Irreducible
- reducibility :: forall (node :: Extensibility -> Extensibility -> Type). NonLocal node => GraphWithDominators node -> Reducibility
- asReducible :: GraphWithDominators CmmNode -> UniqSM (GraphWithDominators CmmNode)

# Documentation

data Reducibility Source #

Represents the result of a reducibility analysis.

Constructors

Reducible |
Irreducible |

#### Instances

Instances details

Show Reducibility Source # |
Instance details Defined in GHC.Cmm.Reducibility Methods showsPrec :: Int -> Reducibility -> ShowS # show :: Reducibility -> String # showList :: [Reducibility] -> ShowS #
Eq Reducibility Source # |
Instance details Defined in GHC.Cmm.Reducibility Methods (==) :: Reducibility -> Reducibility -> Bool # (/=) :: Reducibility -> Reducibility -> Bool #

reducibility :: forall (node :: Extensibility -> Extensibility -> Type). NonLocal node => GraphWithDominators node -> Reducibility Source #

Given a graph, say whether the graph is reducible. The graph must be bundled with a dominator analysis and a reverse postorder numbering, as these results are needed to perform the test.

asReducible :: GraphWithDominators CmmNode -> UniqSM (GraphWithDominators CmmNode) Source #

Given a graph, return an equivalent reducible graph, by "splitting" (copying) nodes if necessary. The input graph must be bundled with a dominator analysis and a reverse postorder numbering. The computation is monadic because when a node is split, the new copy needs a fresh label.

Use this function whenever a downstream algorithm needs a reducible control-flow graph.