cfg

Documentation

Overview

Description

Pacakge cfg provides functionality to generate and analyze Control Frow Graph (CFG) for go-like grammar languages.

## Control Flow Graph (CFG)

A CFG is a representation, using graph notation, of all paths that might be traversed through a program during its execution. In a CFG:

• Each node in the graph represents a basic block (a straight-line piece of code without any jumps).
• The directed edges represent jumps in the control flow.

This package constructs CFGs for Go-like language functions, providing a powerful tool for various types of static analysis, including:

• Data flow analysis
• Dead code elimination
• Optimization opportunities identification
• Complex analysis

## Package Functionality

The main features of this package include:

1. CFG Construction: Generate a CFG from AST (Abstract Syntax Tree) nodes.
2. Use the `FromFunc` or `Build` methods to construct a CFG from the AST.
3. Analyze the CFG using provided methods or traverse it from custom analysis.

Index

• func NewBuilder() *builder
• type CFG
  • func AnalyzeFunction(file *ast.File, fname string) *CFG
  • func FromFunc(f *ast.FuncDecl) *CFG
  • func FromStmts(s []ast.Stmt) *CFG
  • func (c *CFG) Blocks() []ast.Stmt
  • func (c *CFG) Preds(s ast.Stmt) []ast.Stmt
  • func (c *CFG) PrintDot(f io.Writer, fset *token.FileSet, addl func(n ast.Stmt) string)
  • func (c *CFG) Sort(stmts []ast.Stmt)
  • func (c *CFG) Succs(s ast.Stmt) []ast.Stmt
• type CFGBuilder

Functions

func NewBuilder

func NewBuilder() *builder

NewBuilder constructs a CFG from the given slice of statements.

Types

type CFG

type CFG struct {
	// Sentinel nodes for single-entry CFG. Not in original AST.
	Entry *ast.BadStmt

	// Sentinel nodes for single-exit CFG. Not in original AST.
	Exit *ast.BadStmt

	// All defers found in CFG, disjoint from blocks. May be flowed to after Exit.
	Defers []*ast.DeferStmt
	// contains filtered or unexported fields
}

CFG defines a control flow graph with statement-level granularity, in which there is a 1-1 correspondence between a block in the CFG and an ast.Stmt.

func AnalyzeFunction

func AnalyzeFunction(file *ast.File, fname string) *CFG

func FromFunc

func FromFunc(f *ast.FuncDecl) *CFG

FromFunc is a convenience function for creating a CFG from a given function declaration.

func FromStmts

func FromStmts(s []ast.Stmt) *CFG

FromStmts returns the control-flow graph for the given sequence of statements.

func (*CFG) Blocks

func (c *CFG) Blocks() []ast.Stmt

Blocks returns a slice of all blocks in a CFG, including the Entry and Exit nodes. The blocks are roughly in the order they appear in the source code.

func (*CFG) Preds

func (c *CFG) Preds(s ast.Stmt) []ast.Stmt

Preds returns a slice of all immediate predecessors for the given statement. May include Entry node.

func (*CFG) PrintDot

func (c *CFG) PrintDot(f io.Writer, fset *token.FileSet, addl func(n ast.Stmt) string)

func (*CFG) Sort

func (c *CFG) Sort(stmts []ast.Stmt)

func (*CFG) Succs

func (c *CFG) Succs(s ast.Stmt) []ast.Stmt

Succs returns a slice of all immediate successors to the given statement. May include Exit node.

type CFGBuilder

type CFGBuilder interface {
	Build(stmts []ast.Stmt) *CFG
	Sort(stmts []ast.Stmt)
	PrintDot(f io.Writer, fset *token.FileSet, addl func(n ast.Stmt) string)
	BuildFromFunc(f *ast.FuncDecl) *CFG
}

CFGBuilder defines the interface for building a control flow graph (CFG).