Safe Haskell | None |
---|

Tools to compute dominance information for functions. Includes postdominators.

A node `m`

postdominates a node `n`

iff every path from `n`

to
`exit`

passes through `m`

.

This implementation is based on the dominator implementation in fgl, which is based on the algorithm from Cooper, Harvey, and Kennedy:

http:www.cs.rice.edu*~keith*Embed/dom.pdf

- data DominatorTree
- data PostdominatorTree
- class HasDomTree a where
- getDomTree :: a -> DominatorTree

- class HasPostdomTree a where
- getPostdomTree :: a -> PostdominatorTree

- dominatorTree :: HasCFG cfg => cfg -> DominatorTree
- postdominatorTree :: HasCFG f => f -> PostdominatorTree
- dominates :: HasDomTree t => t -> Instruction -> Instruction -> Bool
- dominators :: HasDomTree t => t -> [(Instruction, [Instruction])]
- dominatorsFor :: HasDomTree t => t -> Instruction -> [Instruction]
- immediateDominatorFor :: HasDomTree t => t -> Instruction -> Maybe Instruction
- immediateDominators :: HasDomTree t => t -> [(Instruction, Instruction)]
- postdominates :: HasPostdomTree t => t -> Instruction -> Instruction -> Bool
- postdominators :: HasPostdomTree t => t -> [(Instruction, [Instruction])]
- postdominatorsFor :: HasPostdomTree t => t -> Instruction -> [Instruction]
- immediatePostdominatorFor :: HasPostdomTree t => t -> Instruction -> Maybe Instruction
- immediatePostdominators :: HasPostdomTree t => t -> [(Instruction, Instruction)]

# Types

data DominatorTree Source

data PostdominatorTree Source

HasFunction PostdominatorTree | |

ToGraphviz PostdominatorTree | |

HasCFG PostdominatorTree | |

HasPostdomTree PostdominatorTree | |

HasCDG PostdominatorTree | Warning, this is an expensive instance to invoke as it constructs the CDG. |

class HasDomTree a whereSource

getDomTree :: a -> DominatorTreeSource

HasDomTree CFG | Note, this instance constructs the dominator tree and could be expensive |

HasDomTree DominatorTree |

class HasPostdomTree a whereSource

HasPostdomTree CFG | Note that this instance constructs the postdominator tree from scratch. |

HasPostdomTree PostdominatorTree | |

HasPostdomTree CDG |

# Constructors

dominatorTree :: HasCFG cfg => cfg -> DominatorTreeSource

Construct a DominatorTree from something that behaves like a control flow graph.

postdominatorTree :: HasCFG f => f -> PostdominatorTreeSource

Construct a PostdominatorTree from something that behaves like a control flow graph.

# Queries

dominates :: HasDomTree t => t -> Instruction -> Instruction -> BoolSource

Check whether n dominates m

dominators :: HasDomTree t => t -> [(Instruction, [Instruction])]Source

dominatorsFor :: HasDomTree t => t -> Instruction -> [Instruction]Source

immediateDominatorFor :: HasDomTree t => t -> Instruction -> Maybe InstructionSource

immediateDominators :: HasDomTree t => t -> [(Instruction, Instruction)]Source

postdominates :: HasPostdomTree t => t -> Instruction -> Instruction -> BoolSource

Tests whether or not an Instruction n postdominates Instruction m

postdominators :: HasPostdomTree t => t -> [(Instruction, [Instruction])]Source

postdominatorsFor :: HasPostdomTree t => t -> Instruction -> [Instruction]Source

immediatePostdominatorFor :: HasPostdomTree t => t -> Instruction -> Maybe InstructionSource

immediatePostdominators :: HasPostdomTree t => t -> [(Instruction, Instruction)]Source