+++ /dev/null
-// Copyright 2016 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package cfg
-
-// This file implements the CFG construction pass.
-
-import (
- "fmt"
- "go/ast"
- "go/token"
-)
-
-type builder struct {
- cfg *CFG
- mayReturn func(*ast.CallExpr) bool
- current *Block
- lblocks map[*ast.Object]*lblock // labeled blocks
- targets *targets // linked stack of branch targets
-}
-
-func (b *builder) stmt(_s ast.Stmt) {
- // The label of the current statement. If non-nil, its _goto
- // target is always set; its _break and _continue are set only
- // within the body of switch/typeswitch/select/for/range.
- // It is effectively an additional default-nil parameter of stmt().
- var label *lblock
-start:
- switch s := _s.(type) {
- case *ast.BadStmt,
- *ast.SendStmt,
- *ast.IncDecStmt,
- *ast.GoStmt,
- *ast.DeferStmt,
- *ast.EmptyStmt,
- *ast.AssignStmt:
- // No effect on control flow.
- b.add(s)
-
- case *ast.ExprStmt:
- b.add(s)
- if call, ok := s.X.(*ast.CallExpr); ok && !b.mayReturn(call) {
- // Calls to panic, os.Exit, etc, never return.
- b.current = b.newBlock("unreachable.call")
- }
-
- case *ast.DeclStmt:
- // Treat each var ValueSpec as a separate statement.
- d := s.Decl.(*ast.GenDecl)
- if d.Tok == token.VAR {
- for _, spec := range d.Specs {
- if spec, ok := spec.(*ast.ValueSpec); ok {
- b.add(spec)
- }
- }
- }
-
- case *ast.LabeledStmt:
- label = b.labeledBlock(s.Label)
- b.jump(label._goto)
- b.current = label._goto
- _s = s.Stmt
- goto start // effectively: tailcall stmt(g, s.Stmt, label)
-
- case *ast.ReturnStmt:
- b.add(s)
- b.current = b.newBlock("unreachable.return")
-
- case *ast.BranchStmt:
- b.branchStmt(s)
-
- case *ast.BlockStmt:
- b.stmtList(s.List)
-
- case *ast.IfStmt:
- if s.Init != nil {
- b.stmt(s.Init)
- }
- then := b.newBlock("if.then")
- done := b.newBlock("if.done")
- _else := done
- if s.Else != nil {
- _else = b.newBlock("if.else")
- }
- b.add(s.Cond)
- b.ifelse(then, _else)
- b.current = then
- b.stmt(s.Body)
- b.jump(done)
-
- if s.Else != nil {
- b.current = _else
- b.stmt(s.Else)
- b.jump(done)
- }
-
- b.current = done
-
- case *ast.SwitchStmt:
- b.switchStmt(s, label)
-
- case *ast.TypeSwitchStmt:
- b.typeSwitchStmt(s, label)
-
- case *ast.SelectStmt:
- b.selectStmt(s, label)
-
- case *ast.ForStmt:
- b.forStmt(s, label)
-
- case *ast.RangeStmt:
- b.rangeStmt(s, label)
-
- default:
- panic(fmt.Sprintf("unexpected statement kind: %T", s))
- }
-}
-
-func (b *builder) stmtList(list []ast.Stmt) {
- for _, s := range list {
- b.stmt(s)
- }
-}
-
-func (b *builder) branchStmt(s *ast.BranchStmt) {
- var block *Block
- switch s.Tok {
- case token.BREAK:
- if s.Label != nil {
- if lb := b.labeledBlock(s.Label); lb != nil {
- block = lb._break
- }
- } else {
- for t := b.targets; t != nil && block == nil; t = t.tail {
- block = t._break
- }
- }
-
- case token.CONTINUE:
- if s.Label != nil {
- if lb := b.labeledBlock(s.Label); lb != nil {
- block = lb._continue
- }
- } else {
- for t := b.targets; t != nil && block == nil; t = t.tail {
- block = t._continue
- }
- }
-
- case token.FALLTHROUGH:
- for t := b.targets; t != nil && block == nil; t = t.tail {
- block = t._fallthrough
- }
-
- case token.GOTO:
- if s.Label != nil {
- block = b.labeledBlock(s.Label)._goto
- }
- }
- if block == nil {
- block = b.newBlock("undefined.branch")
- }
- b.jump(block)
- b.current = b.newBlock("unreachable.branch")
-}
-
-func (b *builder) switchStmt(s *ast.SwitchStmt, label *lblock) {
- if s.Init != nil {
- b.stmt(s.Init)
- }
- if s.Tag != nil {
- b.add(s.Tag)
- }
- done := b.newBlock("switch.done")
- if label != nil {
- label._break = done
- }
- // We pull the default case (if present) down to the end.
- // But each fallthrough label must point to the next
- // body block in source order, so we preallocate a
- // body block (fallthru) for the next case.
- // Unfortunately this makes for a confusing block order.
- var defaultBody *[]ast.Stmt
- var defaultFallthrough *Block
- var fallthru, defaultBlock *Block
- ncases := len(s.Body.List)
- for i, clause := range s.Body.List {
- body := fallthru
- if body == nil {
- body = b.newBlock("switch.body") // first case only
- }
-
- // Preallocate body block for the next case.
- fallthru = done
- if i+1 < ncases {
- fallthru = b.newBlock("switch.body")
- }
-
- cc := clause.(*ast.CaseClause)
- if cc.List == nil {
- // Default case.
- defaultBody = &cc.Body
- defaultFallthrough = fallthru
- defaultBlock = body
- continue
- }
-
- var nextCond *Block
- for _, cond := range cc.List {
- nextCond = b.newBlock("switch.next")
- b.add(cond) // one half of the tag==cond condition
- b.ifelse(body, nextCond)
- b.current = nextCond
- }
- b.current = body
- b.targets = &targets{
- tail: b.targets,
- _break: done,
- _fallthrough: fallthru,
- }
- b.stmtList(cc.Body)
- b.targets = b.targets.tail
- b.jump(done)
- b.current = nextCond
- }
- if defaultBlock != nil {
- b.jump(defaultBlock)
- b.current = defaultBlock
- b.targets = &targets{
- tail: b.targets,
- _break: done,
- _fallthrough: defaultFallthrough,
- }
- b.stmtList(*defaultBody)
- b.targets = b.targets.tail
- }
- b.jump(done)
- b.current = done
-}
-
-func (b *builder) typeSwitchStmt(s *ast.TypeSwitchStmt, label *lblock) {
- if s.Init != nil {
- b.stmt(s.Init)
- }
- if s.Assign != nil {
- b.add(s.Assign)
- }
-
- done := b.newBlock("typeswitch.done")
- if label != nil {
- label._break = done
- }
- var default_ *ast.CaseClause
- for _, clause := range s.Body.List {
- cc := clause.(*ast.CaseClause)
- if cc.List == nil {
- default_ = cc
- continue
- }
- body := b.newBlock("typeswitch.body")
- var next *Block
- for _, casetype := range cc.List {
- next = b.newBlock("typeswitch.next")
- // casetype is a type, so don't call b.add(casetype).
- // This block logically contains a type assertion,
- // x.(casetype), but it's unclear how to represent x.
- _ = casetype
- b.ifelse(body, next)
- b.current = next
- }
- b.current = body
- b.typeCaseBody(cc, done)
- b.current = next
- }
- if default_ != nil {
- b.typeCaseBody(default_, done)
- } else {
- b.jump(done)
- }
- b.current = done
-}
-
-func (b *builder) typeCaseBody(cc *ast.CaseClause, done *Block) {
- b.targets = &targets{
- tail: b.targets,
- _break: done,
- }
- b.stmtList(cc.Body)
- b.targets = b.targets.tail
- b.jump(done)
-}
-
-func (b *builder) selectStmt(s *ast.SelectStmt, label *lblock) {
- // First evaluate channel expressions.
- // TODO(adonovan): fix: evaluate only channel exprs here.
- for _, clause := range s.Body.List {
- if comm := clause.(*ast.CommClause).Comm; comm != nil {
- b.stmt(comm)
- }
- }
-
- done := b.newBlock("select.done")
- if label != nil {
- label._break = done
- }
-
- var defaultBody *[]ast.Stmt
- for _, cc := range s.Body.List {
- clause := cc.(*ast.CommClause)
- if clause.Comm == nil {
- defaultBody = &clause.Body
- continue
- }
- body := b.newBlock("select.body")
- next := b.newBlock("select.next")
- b.ifelse(body, next)
- b.current = body
- b.targets = &targets{
- tail: b.targets,
- _break: done,
- }
- switch comm := clause.Comm.(type) {
- case *ast.ExprStmt: // <-ch
- // nop
- case *ast.AssignStmt: // x := <-states[state].Chan
- b.add(comm.Lhs[0])
- }
- b.stmtList(clause.Body)
- b.targets = b.targets.tail
- b.jump(done)
- b.current = next
- }
- if defaultBody != nil {
- b.targets = &targets{
- tail: b.targets,
- _break: done,
- }
- b.stmtList(*defaultBody)
- b.targets = b.targets.tail
- b.jump(done)
- }
- b.current = done
-}
-
-func (b *builder) forStmt(s *ast.ForStmt, label *lblock) {
- // ...init...
- // jump loop
- // loop:
- // if cond goto body else done
- // body:
- // ...body...
- // jump post
- // post: (target of continue)
- // ...post...
- // jump loop
- // done: (target of break)
- if s.Init != nil {
- b.stmt(s.Init)
- }
- body := b.newBlock("for.body")
- done := b.newBlock("for.done") // target of 'break'
- loop := body // target of back-edge
- if s.Cond != nil {
- loop = b.newBlock("for.loop")
- }
- cont := loop // target of 'continue'
- if s.Post != nil {
- cont = b.newBlock("for.post")
- }
- if label != nil {
- label._break = done
- label._continue = cont
- }
- b.jump(loop)
- b.current = loop
- if loop != body {
- b.add(s.Cond)
- b.ifelse(body, done)
- b.current = body
- }
- b.targets = &targets{
- tail: b.targets,
- _break: done,
- _continue: cont,
- }
- b.stmt(s.Body)
- b.targets = b.targets.tail
- b.jump(cont)
-
- if s.Post != nil {
- b.current = cont
- b.stmt(s.Post)
- b.jump(loop) // back-edge
- }
- b.current = done
-}
-
-func (b *builder) rangeStmt(s *ast.RangeStmt, label *lblock) {
- b.add(s.X)
-
- if s.Key != nil {
- b.add(s.Key)
- }
- if s.Value != nil {
- b.add(s.Value)
- }
-
- // ...
- // loop: (target of continue)
- // if ... goto body else done
- // body:
- // ...
- // jump loop
- // done: (target of break)
-
- loop := b.newBlock("range.loop")
- b.jump(loop)
- b.current = loop
-
- body := b.newBlock("range.body")
- done := b.newBlock("range.done")
- b.ifelse(body, done)
- b.current = body
-
- if label != nil {
- label._break = done
- label._continue = loop
- }
- b.targets = &targets{
- tail: b.targets,
- _break: done,
- _continue: loop,
- }
- b.stmt(s.Body)
- b.targets = b.targets.tail
- b.jump(loop) // back-edge
- b.current = done
-}
-
-// -------- helpers --------
-
-// Destinations associated with unlabeled for/switch/select stmts.
-// We push/pop one of these as we enter/leave each construct and for
-// each BranchStmt we scan for the innermost target of the right type.
-//
-type targets struct {
- tail *targets // rest of stack
- _break *Block
- _continue *Block
- _fallthrough *Block
-}
-
-// Destinations associated with a labeled block.
-// We populate these as labels are encountered in forward gotos or
-// labeled statements.
-//
-type lblock struct {
- _goto *Block
- _break *Block
- _continue *Block
-}
-
-// labeledBlock returns the branch target associated with the
-// specified label, creating it if needed.
-//
-func (b *builder) labeledBlock(label *ast.Ident) *lblock {
- lb := b.lblocks[label.Obj]
- if lb == nil {
- lb = &lblock{_goto: b.newBlock(label.Name)}
- if b.lblocks == nil {
- b.lblocks = make(map[*ast.Object]*lblock)
- }
- b.lblocks[label.Obj] = lb
- }
- return lb
-}
-
-// newBlock appends a new unconnected basic block to b.cfg's block
-// slice and returns it.
-// It does not automatically become the current block.
-// comment is an optional string for more readable debugging output.
-func (b *builder) newBlock(comment string) *Block {
- g := b.cfg
- block := &Block{
- Index: int32(len(g.Blocks)),
- comment: comment,
- }
- block.Succs = block.succs2[:0]
- g.Blocks = append(g.Blocks, block)
- return block
-}
-
-func (b *builder) add(n ast.Node) {
- b.current.Nodes = append(b.current.Nodes, n)
-}
-
-// jump adds an edge from the current block to the target block,
-// and sets b.current to nil.
-func (b *builder) jump(target *Block) {
- b.current.Succs = append(b.current.Succs, target)
- b.current = nil
-}
-
-// ifelse emits edges from the current block to the t and f blocks,
-// and sets b.current to nil.
-func (b *builder) ifelse(t, f *Block) {
- b.current.Succs = append(b.current.Succs, t, f)
- b.current = nil
-}
projects / dotfiles / .git / blobdiff