Language.JVM.CFG

Control Flow Graphs of JVM bytecode. For now, this module simply builds CFGs from instruction streams and does post-dominator analysis.

Basic blocks

Our notion of basic block is fairly standard: a maximal sequence of instructions that that can only be entered at the first of them and existed only from the last of them. I.e., a contiguous sequence of instructions that neither branch or are themselves branch targets.

The first instruction in a basic block (i.e., a leader) may be (a) a method entry point, (b) a branch target, or (c) an instruction immediately following a branch/return.

To identify constituent basic blocks of a given instruction sequence, we identify leaders and then, for each leader, include in its basic block all instructions, in order, that intervene it and the next leader or the end of the instruction sequence, whichever comes first.

data BasicBlock

A basic block consists of an identifier and the instructions contained in that block.

Instances

Eq BasicBlock

Show BasicBlock

data BBId

Identifies basic blocks by their position in the instruction stream, or by the special BBIdEntry or BBIdExit constructors.

Constructors

BBIdEntry

BBIdExit

BBId PC

Instances

Enum BBId

Eq BBId

Ord BBId

Show BBId

ppBBId :: BBId -> Doc

Control flow graphs

data CFG

Instances

Eq CFG

Show CFG

buildCFG :: ExceptionTable -> InstructionStream -> CFG

Build a control-flow graph from an instruction stream. We assume that the first instruction in the instruction stream is the only external entry point in the sequence (typically, the method entry point)

cfgInstByPC :: CFG -> PC -> Maybe Instruction

fetch an instruction from a CFG by position

ppBB :: BasicBlock -> String

ppInst :: Instruction -> String

cfgToDot

Arguments

:: ExceptionTable

-> CFG

-> String

method name

-> String

Render the CFG of a method into Graphviz .dot format

isImmediatePostDominator :: CFG -> BBId -> BBId -> Bool

isImmediatePostDominator g x y returns True if y immediately post-dominates x in control-flow graph g.

getPostDominators :: CFG -> BBId -> [BBId]

Calculate the post-dominators of a given basic block