1 // Copyright 2016 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 // Package cfg constructs a simple control-flow graph (CFG) of the
6 // statements and expressions within a single function.
8 // Use cfg.New to construct the CFG for a function body.
10 // The blocks of the CFG contain all the function's non-control
11 // statements. The CFG does not contain control statements such as If,
12 // Switch, Select, and Branch, but does contain their subexpressions.
13 // For example, this source code:
15 // if x := f(); x != nil {
32 // The CFG does contain Return statements; even implicit returns are
33 // materialized (at the position of the function's closing brace).
35 // The CFG does not record conditions associated with conditional branch
36 // edges, nor the short-circuit semantics of the && and || operators,
37 // nor abnormal control flow caused by panic. If you need this
38 // information, use golang.org/x/tools/go/ssa instead.
50 // A CFG represents the control-flow graph of a single function.
52 // The entry point is Blocks[0]; there may be multiple return blocks.
54 Blocks []*Block // block[0] is entry; order otherwise undefined
57 // A Block represents a basic block: a list of statements and
58 // expressions that are always evaluated sequentially.
60 // A block may have 0-2 successors: zero for a return block or a block
61 // that calls a function such as panic that never returns; one for a
62 // normal (jump) block; and two for a conditional (if) block.
64 Nodes []ast.Node // statements, expressions, and ValueSpecs
65 Succs []*Block // successor nodes in the graph
66 Index int32 // index within CFG.Blocks
67 Live bool // block is reachable from entry
69 comment string // for debugging
70 succs2 [2]*Block // underlying array for Succs
73 // New returns a new control-flow graph for the specified function body,
74 // which must be non-nil.
76 // The CFG builder calls mayReturn to determine whether a given function
77 // call may return. For example, calls to panic, os.Exit, and log.Fatal
78 // do not return, so the builder can remove infeasible graph edges
79 // following such calls. The builder calls mayReturn only for a
80 // CallExpr beneath an ExprStmt.
81 func New(body *ast.BlockStmt, mayReturn func(*ast.CallExpr) bool) *CFG {
86 b.current = b.newBlock("entry")
89 // Compute liveness (reachability from entry point), breadth-first.
90 q := make([]*Block, 0, len(b.cfg.Blocks))
91 q = append(q, b.cfg.Blocks[0]) // entry point
98 q = append(q, b.Succs...)
102 // Does control fall off the end of the function's body?
103 // Make implicit return explicit.
104 if b.current != nil && b.current.Live {
105 b.add(&ast.ReturnStmt{
106 Return: body.End() - 1,
113 func (b *Block) String() string {
114 return fmt.Sprintf("block %d (%s)", b.Index, b.comment)
117 // Return returns the return statement at the end of this block if present, nil otherwise.
118 func (b *Block) Return() (ret *ast.ReturnStmt) {
119 if len(b.Nodes) > 0 {
120 ret, _ = b.Nodes[len(b.Nodes)-1].(*ast.ReturnStmt)
125 // Format formats the control-flow graph for ease of debugging.
126 func (g *CFG) Format(fset *token.FileSet) string {
128 for _, b := range g.Blocks {
129 fmt.Fprintf(&buf, ".%d: # %s\n", b.Index, b.comment)
130 for _, n := range b.Nodes {
131 fmt.Fprintf(&buf, "\t%s\n", formatNode(fset, n))
133 if len(b.Succs) > 0 {
134 fmt.Fprintf(&buf, "\tsuccs:")
135 for _, succ := range b.Succs {
136 fmt.Fprintf(&buf, " %d", succ.Index)
145 func formatNode(fset *token.FileSet, n ast.Node) string {
147 format.Node(&buf, fset, n)
148 // Indent secondary lines by a tab.
149 return string(bytes.Replace(buf.Bytes(), []byte("\n"), []byte("\n\t"), -1))