Safe Haskell	None
Language	GHC2021

Language.QBE.Analysis.CDG

Description

This module implements a control dependency analysis, using a control dependency graph (CDG) for more information on the concept refer to https://doi.org/10.1145/24039.24041. Roughly speaking, a node A is control dependent on B if there is an edge B → A so that the node is taken, as well as an edge so that it is not taken.

Synopsis

data CDG = CDG {
- cdgCfg :: CFG
- cdgRoot :: Label
- cdgGraph :: Graph
}
build :: CFG -> Label -> CDG
edges :: CDG -> [(Label, Label)]
ctrlDeps :: CDG -> Label -> Maybe IntSet

Documentation

data CDG Source #

A CDG signifying control-dependence between nodes in the CFG.

Constructors

CDG
Fields cdgCfg :: CFG Underlying `CFG` for which the CDG was built. cdgRoot :: Label Root node of the `CDG`, used for determining post-dominance. cdgGraph :: Graph Graph representation of control-dependence.

build :: CFG -> Label -> CDG Source #

Construct a new CDG from an existing CFG. The CDG is build based on the given Label from the CFG, which is used to as the root of a post-dominator tree to establish a post-dominance relationship between nodes.

edges :: CDG -> [(Label, Label)] Source #

All edges of the CDG, in an unspecified order.

ctrlDeps :: CDG -> Label -> Maybe IntSet Source #

Returns the control dependencies of a given node in the CFG. If the node doesn't have any control dependencies, Nothing is returned.