Documentation

Overview

Package cfa implements control flow analysis of control flow graphs.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func FindPrim

func FindPrim(g graph.Directed, dom cfg.DominatorTree) (*primitive.Primitive, error)

FindPrim locates a control flow primitive in the provided control flow graph and merges its nodes into a single node.

func Merge

func Merge(g *cfg.Graph, prim *primitive.Primitive) error

Merge merges the nodes of the primitive into a single node, which is assigned the basic block label of the entry node.

Types

type If

type If struct {
	// Condition node (A).
	Cond graph.Node
	// Body node (B).
	Body graph.Node
	// Exit node (C).
	Exit graph.Node
}

If represents a 1-way conditional statement.

Pseudo-code:

if (A) {
   B
}
C

func FindIf

func FindIf(g graph.Directed, dom cfg.DominatorTree) (prim If, ok bool)

FindIf returns the first occurrence of a 1-way conditional statement in g, and a boolean indicating if such a primitive was found.

func (If) IsValid

func (prim If) IsValid(g graph.Directed, dom cfg.DominatorTree) bool

IsValid reports whether the cond, body and exit node candidates of prim form a valid 1-way conditional statement in g.

Control flow graph:

cond
↓   ↘
↓    body
↓   ↙
exit

func (If) Prim

func (prim If) Prim() *primitive.Primitive

Prim returns a representation of the high-level control flow primitive, as a mapping from control flow primitive node names to control flow graph node names.

Example mapping:

"cond": "A"
"body": "B"
"exit": "C"

func (If) String

func (prim If) String() string

String returns a string representation of prim in DOT format.

Example output:

digraph if {
   cond -> body
   cond -> exit
   body -> exit
}

type IfElse

type IfElse struct {
	// Condition node (A).
	Cond graph.Node
	// Body node of the true branch (B).
	BodyTrue graph.Node
	// Body node of the false branch (C).
	BodyFalse graph.Node
	// Exit node (D).
	Exit graph.Node
}

IfElse represents a 2-way conditional statement.

Pseudo-code:

if (A) {
   B
} else {
   C
}
D

func FindIfElse

func FindIfElse(g graph.Directed, dom cfg.DominatorTree) (prim IfElse, ok bool)

FindIfElse returns the first occurrence of a 2-way conditional statement in g, and a boolean indicating if such a primitive was found.

func (IfElse) IsValid

func (prim IfElse) IsValid(g graph.Directed, dom cfg.DominatorTree) bool

IsValid reports whether the cond, body_true, body_false and exit node candidates of prim form a valid 2-way conditional statement in g.

Control flow graph:

          cond
         ↙    ↘
body_true      body_false
         ↘    ↙
          exit

func (IfElse) Prim

func (prim IfElse) Prim() *primitive.Primitive

Prim returns a representation of the high-level control flow primitive, as a mapping from control flow primitive node names to control flow graph node names.

Example mapping:

"cond":       "A"
"body_true":  "B"
"body_false": "C"
"exit":       "D"

func (IfElse) String

func (prim IfElse) String() string

String returns a string representation of prim in DOT format.

Example output:

digraph if_else {
   cond -> body_true
   cond -> body_false
   body_true -> exit
   body_false -> exit
}

type IfReturn

type IfReturn struct {
	// Condition node (A).
	Cond graph.Node
	// Body node with return statement (B).
	Body graph.Node
	// Exit node (C).
	Exit graph.Node
}

IfReturn represents a 1-way conditional with a body return statement.

Pseudo-code:

if (A) {
   B
   return
}
C

func FindIfReturn

func FindIfReturn(g graph.Directed, dom cfg.DominatorTree) (prim IfReturn, ok bool)

FindIfReturn returns the first occurrence of a 1-way conditional with a body return statement in g, and a boolean indicating if such a primitive was found.

func (IfReturn) IsValid

func (prim IfReturn) IsValid(g graph.Directed, dom cfg.DominatorTree) bool

IsValid reports whether the cond, body and exit node candidates of prim form a valid 1-way conditional with a body return statement in g.

Control flow graph:

cond
↓   ↘
↓    body
↓
exit

func (IfReturn) Prim

func (prim IfReturn) Prim() *primitive.Primitive

Prim returns a representation of the high-level control flow primitive, as a mapping from control flow primitive node names to control flow graph node names.

Example mapping:

"cond": "A"
"body": "B"
"exit": "C"

func (IfReturn) String

func (prim IfReturn) String() string

String returns a string representation of prim in DOT format.

Example output:

digraph if_return {
   cond -> body
   cond -> exit
}

type PostLoop

type PostLoop struct {
	// Condition node (A).
	Cond graph.Node
	// Exit node (B).
	Exit graph.Node
}

PostLoop represents a post-test loop.

Pseudo-code:

do {
} while (A)
B

func FindPostLoop

func FindPostLoop(g graph.Directed, dom cfg.DominatorTree) (prim PostLoop, ok bool)

FindPostLoop returns the first occurrence of a post-test loop in g, and a boolean indicating if such a primitive was found.

func (PostLoop) IsValid

func (prim PostLoop) IsValid(g graph.Directed, dom cfg.DominatorTree) bool

IsValid reports whether the cond and exit node candidates of prim form a valid post-test loop in g.

Control flow graph:

cond ↘
↓   ↖↲
↓
exit

func (PostLoop) Prim

func (prim PostLoop) Prim() *primitive.Primitive

Prim returns a representation of the high-level control flow primitive, as a mapping from control flow primitive node names to control flow graph node names.

Example mapping:

"cond": "A"
"exit": "B"

func (PostLoop) String

func (prim PostLoop) String() string

String returns a string representation of prim in DOT format.

Example output:

digraph post_loop {
   cond -> cond
   cond -> exit
}

type PreLoop

type PreLoop struct {
	// Condition node (A).
	Cond graph.Node
	// Body node (B).
	Body graph.Node
	// Exit node (C).
	Exit graph.Node
}

PreLoop represents a pre-test loop.

Pseudo-code:

while (A) {
   B
}
C

func FindPreLoop

func FindPreLoop(g graph.Directed, dom cfg.DominatorTree) (prim PreLoop, ok bool)

FindPreLoop returns the first occurrence of a pre-test loop in g, and a boolean indicating if such a primitive was found.

func (PreLoop) IsValid

func (prim PreLoop) IsValid(g graph.Directed, dom cfg.DominatorTree) bool

IsValid reports whether the cond, body and exit node candidates of prim form a valid pre-test loop in g.

Control flow graph:

cond
↓  ↖↘
↓   body
↓
exit

func (PreLoop) Prim

func (prim PreLoop) Prim() *primitive.Primitive

Prim returns a representation of the high-level control flow primitive, as a mapping from control flow primitive node names to control flow graph node names.

Example mapping:

"cond": "A"
"body": "B"
"exit": "C"

func (PreLoop) String

func (prim PreLoop) String() string

String returns a string representation of prim in DOT format.

Example output:

digraph pre_loop {
   cond -> body
   cond -> exit
   body -> cond
}

type Seq

type Seq struct {
	// Entry node (A).
	Entry graph.Node
	// Exit node (B).
	Exit graph.Node
}

Seq represents a sequence of two statements.

Pseudo-code:

A
B

func FindSeq

func FindSeq(g graph.Directed, dom cfg.DominatorTree) (prim Seq, ok bool)

FindSeq returns the first occurrence of a sequence of two statements in g, and a boolean indicating if such a primitive was found.

func (Seq) IsValid

func (prim Seq) IsValid(g graph.Directed, dom cfg.DominatorTree) bool

IsValid reports whether the entry and exit node candidates of prim form a valid sequence of two statements in g.

Control flow graph:

entry
↓
exit

func (Seq) Prim

func (prim Seq) Prim() *primitive.Primitive

Prim returns a representation of the high-level control flow primitive, as a mapping from control flow primitive node names to control flow graph node names.

Example mapping:

"entry": "A"
"exit":  "B"

func (Seq) String

func (prim Seq) String() string

String returns a string representation of prim in DOT format.

Example output:

digraph seq {
   entry -> exit
}

Directories

Path Synopsis
primitive Package primitive defines the types used to represent high-level control flow primitives.