analysis

Documentation

Overview

Package analysis provides pure graph analysis algorithms for CFGs.

Index

• func ComputeDominanceFrontier(g basecfg.Graph, idom map[basecfg.Point]basecfg.Point) map[basecfg.Point][]basecfg.Point
• func ComputeDominators(g basecfg.Graph) (idom map[basecfg.Point]basecfg.Point, ...)
• func ComputePostDominators(graph basecfg.Graph) (map[basecfg.Point]basecfg.Point, map[basecfg.Point][]basecfg.Point)
• func Dominates(idom map[basecfg.Point]basecfg.Point, pointA, pointB basecfg.Point) bool
• func PostDominates(postIdom map[basecfg.Point]basecfg.Point, pointA, pointB basecfg.Point) bool
• func StrictlyDominates(idom map[basecfg.Point]basecfg.Point, pointA, pointB basecfg.Point) bool
• type DomInfo
  • func ComputeDomInfo(g basecfg.Graph) *DomInfo

Functions

func ComputeDominanceFrontier

func ComputeDominanceFrontier(g basecfg.Graph, idom map[basecfg.Point]basecfg.Point) map[basecfg.Point][]basecfg.Point

ComputeDominanceFrontier computes the dominance frontier for each node. DF[n] contains all nodes y such that n dominates a predecessor of y but does not strictly dominate y.

func ComputeDominators

func ComputeDominators(g basecfg.Graph) (idom map[basecfg.Point]basecfg.Point, domTree map[basecfg.Point][]basecfg.Point)

ComputeDominators computes immediate dominators and the dominator tree. Uses the Cooper-Harvey-Kennedy algorithm with RPO iteration.

func ComputePostDominators

func ComputePostDominators(graph basecfg.Graph) (map[basecfg.Point]basecfg.Point, map[basecfg.Point][]basecfg.Point)

ComputePostDominators computes post-dominators by running the dominator algorithm on the reversed CFG.

func Dominates

func Dominates(idom map[basecfg.Point]basecfg.Point, pointA, pointB basecfg.Point) bool

Dominates returns true if a dominates b (a is on every path from entry to b).

func PostDominates

func PostDominates(postIdom map[basecfg.Point]basecfg.Point, pointA, pointB basecfg.Point) bool

PostDominates returns true if a post-dominates b (a is on every path from b to exit).

func StrictlyDominates

func StrictlyDominates(idom map[basecfg.Point]basecfg.Point, pointA, pointB basecfg.Point) bool

StrictlyDominates returns true if a strictly dominates b (a dominates b and a != b).

Types

type DomInfo

type DomInfo struct {
	ImmediateDominators map[basecfg.Point]basecfg.Point   // idom[n] = immediate dominator of n
	DominatorTree       map[basecfg.Point][]basecfg.Point // children in dominator tree
	DominanceFrontier   map[basecfg.Point][]basecfg.Point // DF[n] = dominance frontier of n
}

DomInfo holds dominator tree and dominance frontier information.

func ComputeDomInfo

func ComputeDomInfo(g basecfg.Graph) *DomInfo

ComputeDomInfo computes all dominator information in one call.