cfa

Documentation

Overview

Package cfa implements control flow analysis of control flow graphs.

Index

• func FindPrim(g graph.Directed, dom cfg.DominatorTree) (*primitive.Primitive, error)
• func Merge(g *cfg.Graph, prim *primitive.Primitive) error
• type If
  • func FindIf(g graph.Directed, dom cfg.DominatorTree) (prim If, ok bool)
  • func (prim If) IsValid(g graph.Directed, dom cfg.DominatorTree) bool
  • func (prim If) Prim() *primitive.Primitive
  • func (prim If) String() string
• type IfElse
  • func FindIfElse(g graph.Directed, dom cfg.DominatorTree) (prim IfElse, ok bool)
  • func (prim IfElse) IsValid(g graph.Directed, dom cfg.DominatorTree) bool
  • func (prim IfElse) Prim() *primitive.Primitive
  • func (prim IfElse) String() string
• type IfReturn
  • func FindIfReturn(g graph.Directed, dom cfg.DominatorTree) (prim IfReturn, ok bool)
  • func (prim IfReturn) IsValid(g graph.Directed, dom cfg.DominatorTree) bool
  • func (prim IfReturn) Prim() *primitive.Primitive
  • func (prim IfReturn) String() string
• type PostLoop
  • func FindPostLoop(g graph.Directed, dom cfg.DominatorTree) (prim PostLoop, ok bool)
  • func (prim PostLoop) IsValid(g graph.Directed, dom cfg.DominatorTree) bool
  • func (prim PostLoop) Prim() *primitive.Primitive
  • func (prim PostLoop) String() string
• type PreLoop
  • func FindPreLoop(g graph.Directed, dom cfg.DominatorTree) (prim PreLoop, ok bool)
  • func (prim PreLoop) IsValid(g graph.Directed, dom cfg.DominatorTree) bool
  • func (prim PreLoop) Prim() *primitive.Primitive
  • func (prim PreLoop) String() string
• type Seq
  • func FindSeq(g graph.Directed, dom cfg.DominatorTree) (prim Seq, ok bool)
  • func (prim Seq) IsValid(g graph.Directed, dom cfg.DominatorTree) bool
  • func (prim Seq) Prim() *primitive.Primitive
  • func (prim Seq) String() string

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
}