builder.go

     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.
     4  
     5  package cfg
     6  
     7  // This file implements the CFG construction pass.
     8  
     9  import (
    10  	"fmt"
    11  	"go/ast"
    12  	"go/token"
    13  )
    14  
    15  type builder struct {
    16  	blocks    []*Block
    17  	mayReturn func(*ast.CallExpr) bool
    18  	current   *Block
    19  	lblocks   map[string]*lblock // labeled blocks
    20  	targets   *targets           // linked stack of branch targets
    21  }
    22  
    23  func (b *builder) stmt(_s ast.Stmt) {
    24  	// The label of the current statement.  If non-nil, its _goto
    25  	// target is always set; its _break and _continue are set only
    26  	// within the body of switch/typeswitch/select/for/range.
    27  	// It is effectively an additional default-nil parameter of stmt().
    28  	var label *lblock
    29  start:
    30  	switch s := _s.(type) {
    31  	case *ast.BadStmt,
    32  		*ast.SendStmt,
    33  		*ast.IncDecStmt,
    34  		*ast.GoStmt,
    35  		*ast.EmptyStmt,
    36  		*ast.AssignStmt:
    37  		// No effect on control flow.
    38  		b.add(s)
    39  
    40  	case *ast.DeferStmt:
    41  		b.add(s)
    42  		// Assume conservatively that this behaves like:
    43  		//    defer func() { recover() }
    44  		// so any subsequent panic may act like a return.
    45  		b.current.returns = true
    46  
    47  	case *ast.ExprStmt:
    48  		b.add(s)
    49  		if call, ok := s.X.(*ast.CallExpr); ok && !b.mayReturn(call) {
    50  			// Calls to panic, os.Exit, etc, never return.
    51  			b.current = b.newBlock(KindUnreachable, s)
    52  		}
    53  
    54  	case *ast.DeclStmt:
    55  		// Treat each var ValueSpec as a separate statement.
    56  		d := s.Decl.(*ast.GenDecl)
    57  		if d.Tok == token.VAR {
    58  			for _, spec := range d.Specs {
    59  				if spec, ok := spec.(*ast.ValueSpec); ok {
    60  					b.add(spec)
    61  				}
    62  			}
    63  		}
    64  
    65  	case *ast.LabeledStmt:
    66  		label = b.labeledBlock(s.Label, s)
    67  		b.jump(label._goto)
    68  		b.current = label._goto
    69  		_s = s.Stmt
    70  		goto start // effectively: tailcall stmt(g, s.Stmt, label)
    71  
    72  	case *ast.ReturnStmt:
    73  		b.current.returns = true
    74  		b.add(s)
    75  		b.current = b.newBlock(KindUnreachable, s)
    76  
    77  	case *ast.BranchStmt:
    78  		b.branchStmt(s)
    79  
    80  	case *ast.BlockStmt:
    81  		b.stmtList(s.List)
    82  
    83  	case *ast.IfStmt:
    84  		if s.Init != nil {
    85  			b.stmt(s.Init)
    86  		}
    87  		then := b.newBlock(KindIfThen, s)
    88  		done := b.newBlock(KindIfDone, s)
    89  		_else := done
    90  		if s.Else != nil {
    91  			_else = b.newBlock(KindIfElse, s)
    92  		}
    93  		b.add(s.Cond)
    94  		b.ifelse(then, _else)
    95  		b.current = then
    96  		b.stmt(s.Body)
    97  		b.jump(done)
    98  
    99  		if s.Else != nil {
   100  			b.current = _else
   101  			b.stmt(s.Else)
   102  			b.jump(done)
   103  		}
   104  
   105  		b.current = done
   106  
   107  	case *ast.SwitchStmt:
   108  		b.switchStmt(s, label)
   109  
   110  	case *ast.TypeSwitchStmt:
   111  		b.typeSwitchStmt(s, label)
   112  
   113  	case *ast.SelectStmt:
   114  		b.selectStmt(s, label)
   115  
   116  	case *ast.ForStmt:
   117  		b.forStmt(s, label)
   118  
   119  	case *ast.RangeStmt:
   120  		b.rangeStmt(s, label)
   121  
   122  	default:
   123  		panic(fmt.Sprintf("unexpected statement kind: %T", s))
   124  	}
   125  }
   126  
   127  func (b *builder) stmtList(list []ast.Stmt) {
   128  	for _, s := range list {
   129  		b.stmt(s)
   130  	}
   131  }
   132  
   133  func (b *builder) branchStmt(s *ast.BranchStmt) {
   134  	var block *Block
   135  	switch s.Tok {
   136  	case token.BREAK:
   137  		if s.Label != nil {
   138  			if lb := b.labeledBlock(s.Label, nil); lb != nil {
   139  				block = lb._break
   140  			}
   141  		} else {
   142  			for t := b.targets; t != nil && block == nil; t = t.tail {
   143  				block = t._break
   144  			}
   145  		}
   146  
   147  	case token.CONTINUE:
   148  		if s.Label != nil {
   149  			if lb := b.labeledBlock(s.Label, nil); lb != nil {
   150  				block = lb._continue
   151  			}
   152  		} else {
   153  			for t := b.targets; t != nil && block == nil; t = t.tail {
   154  				block = t._continue
   155  			}
   156  		}
   157  
   158  	case token.FALLTHROUGH:
   159  		for t := b.targets; t != nil && block == nil; t = t.tail {
   160  			block = t._fallthrough
   161  		}
   162  
   163  	case token.GOTO:
   164  		if s.Label != nil {
   165  			block = b.labeledBlock(s.Label, nil)._goto
   166  		}
   167  	}
   168  	if block == nil { // ill-typed (e.g. undefined label)
   169  		block = b.newBlock(KindUnreachable, s)
   170  	}
   171  	b.jump(block)
   172  	b.current = b.newBlock(KindUnreachable, s)
   173  }
   174  
   175  func (b *builder) switchStmt(s *ast.SwitchStmt, label *lblock) {
   176  	if s.Init != nil {
   177  		b.stmt(s.Init)
   178  	}
   179  	if s.Tag != nil {
   180  		b.add(s.Tag)
   181  	}
   182  	done := b.newBlock(KindSwitchDone, s)
   183  	if label != nil {
   184  		label._break = done
   185  	}
   186  	// We pull the default case (if present) down to the end.
   187  	// But each fallthrough label must point to the next
   188  	// body block in source order, so we preallocate a
   189  	// body block (fallthru) for the next case.
   190  	// Unfortunately this makes for a confusing block order.
   191  	var defaultBody *[]ast.Stmt
   192  	var defaultFallthrough *Block
   193  	var fallthru, defaultBlock *Block
   194  	ncases := len(s.Body.List)
   195  	for i, clause := range s.Body.List {
   196  		body := fallthru
   197  		if body == nil {
   198  			body = b.newBlock(KindSwitchCaseBody, clause) // first case only
   199  		}
   200  
   201  		// Preallocate body block for the next case.
   202  		fallthru = done
   203  		if i+1 < ncases {
   204  			fallthru = b.newBlock(KindSwitchCaseBody, s.Body.List[i+1])
   205  		}
   206  
   207  		cc := clause.(*ast.CaseClause)
   208  		if cc.List == nil {
   209  			// Default case.
   210  			defaultBody = &cc.Body
   211  			defaultFallthrough = fallthru
   212  			defaultBlock = body
   213  			continue
   214  		}
   215  
   216  		var nextCond *Block
   217  		for _, cond := range cc.List {
   218  			nextCond = b.newBlock(KindSwitchNextCase, cc)
   219  			b.add(cond) // one half of the tag==cond condition
   220  			b.ifelse(body, nextCond)
   221  			b.current = nextCond
   222  		}
   223  		b.current = body
   224  		b.targets = &targets{
   225  			tail:         b.targets,
   226  			_break:       done,
   227  			_fallthrough: fallthru,
   228  		}
   229  		b.stmtList(cc.Body)
   230  		b.targets = b.targets.tail
   231  		b.jump(done)
   232  		b.current = nextCond
   233  	}
   234  	if defaultBlock != nil {
   235  		b.jump(defaultBlock)
   236  		b.current = defaultBlock
   237  		b.targets = &targets{
   238  			tail:         b.targets,
   239  			_break:       done,
   240  			_fallthrough: defaultFallthrough,
   241  		}
   242  		b.stmtList(*defaultBody)
   243  		b.targets = b.targets.tail
   244  	}
   245  	b.jump(done)
   246  	b.current = done
   247  }
   248  
   249  func (b *builder) typeSwitchStmt(s *ast.TypeSwitchStmt, label *lblock) {
   250  	if s.Init != nil {
   251  		b.stmt(s.Init)
   252  	}
   253  	if s.Assign != nil {
   254  		b.add(s.Assign)
   255  	}
   256  
   257  	done := b.newBlock(KindSwitchDone, s)
   258  	if label != nil {
   259  		label._break = done
   260  	}
   261  	var default_ *ast.CaseClause
   262  	for _, clause := range s.Body.List {
   263  		cc := clause.(*ast.CaseClause)
   264  		if cc.List == nil {
   265  			default_ = cc
   266  			continue
   267  		}
   268  		body := b.newBlock(KindSwitchCaseBody, cc)
   269  		var next *Block
   270  		for _, casetype := range cc.List {
   271  			next = b.newBlock(KindSwitchNextCase, cc)
   272  			// casetype is a type, so don't call b.add(casetype).
   273  			// This block logically contains a type assertion,
   274  			// x.(casetype), but it's unclear how to represent x.
   275  			_ = casetype
   276  			b.ifelse(body, next)
   277  			b.current = next
   278  		}
   279  		b.current = body
   280  		b.typeCaseBody(cc, done)
   281  		b.current = next
   282  	}
   283  	if default_ != nil {
   284  		b.typeCaseBody(default_, done)
   285  	} else {
   286  		b.jump(done)
   287  	}
   288  	b.current = done
   289  }
   290  
   291  func (b *builder) typeCaseBody(cc *ast.CaseClause, done *Block) {
   292  	b.targets = &targets{
   293  		tail:   b.targets,
   294  		_break: done,
   295  	}
   296  	b.stmtList(cc.Body)
   297  	b.targets = b.targets.tail
   298  	b.jump(done)
   299  }
   300  
   301  func (b *builder) selectStmt(s *ast.SelectStmt, label *lblock) {
   302  	// First evaluate channel expressions.
   303  	// TODO(adonovan): fix: evaluate only channel exprs here.
   304  	for _, clause := range s.Body.List {
   305  		if comm := clause.(*ast.CommClause).Comm; comm != nil {
   306  			b.stmt(comm)
   307  		}
   308  	}
   309  
   310  	done := b.newBlock(KindSelectDone, s)
   311  	if label != nil {
   312  		label._break = done
   313  	}
   314  
   315  	var defaultBody *[]ast.Stmt
   316  	for _, cc := range s.Body.List {
   317  		clause := cc.(*ast.CommClause)
   318  		if clause.Comm == nil {
   319  			defaultBody = &clause.Body
   320  			continue
   321  		}
   322  		body := b.newBlock(KindSelectCaseBody, clause)
   323  		next := b.newBlock(KindSelectAfterCase, clause)
   324  		b.ifelse(body, next)
   325  		b.current = body
   326  		b.targets = &targets{
   327  			tail:   b.targets,
   328  			_break: done,
   329  		}
   330  		switch comm := clause.Comm.(type) {
   331  		case *ast.ExprStmt: // <-ch
   332  			// nop
   333  		case *ast.AssignStmt: // x := <-states[state].Chan
   334  			b.add(comm.Lhs[0])
   335  		}
   336  		b.stmtList(clause.Body)
   337  		b.targets = b.targets.tail
   338  		b.jump(done)
   339  		b.current = next
   340  	}
   341  	if defaultBody != nil {
   342  		b.targets = &targets{
   343  			tail:   b.targets,
   344  			_break: done,
   345  		}
   346  		b.stmtList(*defaultBody)
   347  		b.targets = b.targets.tail
   348  		b.jump(done)
   349  	}
   350  	b.current = done
   351  }
   352  
   353  func (b *builder) forStmt(s *ast.ForStmt, label *lblock) {
   354  	//	...init...
   355  	//      jump loop
   356  	// loop:
   357  	//      if cond goto body else done
   358  	// body:
   359  	//      ...body...
   360  	//      jump post
   361  	// post:				 (target of continue)
   362  	//      ...post...
   363  	//      jump loop
   364  	// done:                                 (target of break)
   365  	if s.Init != nil {
   366  		b.stmt(s.Init)
   367  	}
   368  	body := b.newBlock(KindForBody, s)
   369  	done := b.newBlock(KindForDone, s) // target of 'break'
   370  	loop := body                       // target of back-edge
   371  	if s.Cond != nil {
   372  		loop = b.newBlock(KindForLoop, s)
   373  	}
   374  	cont := loop // target of 'continue'
   375  	if s.Post != nil {
   376  		cont = b.newBlock(KindForPost, s)
   377  	}
   378  	if label != nil {
   379  		label._break = done
   380  		label._continue = cont
   381  	}
   382  	b.jump(loop)
   383  	b.current = loop
   384  	if loop != body {
   385  		b.add(s.Cond)
   386  		b.ifelse(body, done)
   387  		b.current = body
   388  	}
   389  	b.targets = &targets{
   390  		tail:      b.targets,
   391  		_break:    done,
   392  		_continue: cont,
   393  	}
   394  	b.stmt(s.Body)
   395  	b.targets = b.targets.tail
   396  	b.jump(cont)
   397  
   398  	if s.Post != nil {
   399  		b.current = cont
   400  		b.stmt(s.Post)
   401  		b.jump(loop) // back-edge
   402  	}
   403  	b.current = done
   404  }
   405  
   406  func (b *builder) rangeStmt(s *ast.RangeStmt, label *lblock) {
   407  	b.add(s.X)
   408  
   409  	if s.Key != nil {
   410  		b.add(s.Key)
   411  	}
   412  	if s.Value != nil {
   413  		b.add(s.Value)
   414  	}
   415  
   416  	//      ...
   417  	// loop:                                   (target of continue)
   418  	// 	if ... goto body else done
   419  	// body:
   420  	//      ...
   421  	// 	jump loop
   422  	// done:                                   (target of break)
   423  
   424  	loop := b.newBlock(KindRangeLoop, s)
   425  	b.jump(loop)
   426  	b.current = loop
   427  
   428  	body := b.newBlock(KindRangeBody, s)
   429  	done := b.newBlock(KindRangeDone, s)
   430  	b.ifelse(body, done)
   431  	b.current = body
   432  
   433  	if label != nil {
   434  		label._break = done
   435  		label._continue = loop
   436  	}
   437  	b.targets = &targets{
   438  		tail:      b.targets,
   439  		_break:    done,
   440  		_continue: loop,
   441  	}
   442  	b.stmt(s.Body)
   443  	b.targets = b.targets.tail
   444  	b.jump(loop) // back-edge
   445  	b.current = done
   446  }
   447  
   448  // -------- helpers --------
   449  
   450  // Destinations associated with unlabeled for/switch/select stmts.
   451  // We push/pop one of these as we enter/leave each construct and for
   452  // each BranchStmt we scan for the innermost target of the right type.
   453  type targets struct {
   454  	tail         *targets // rest of stack
   455  	_break       *Block
   456  	_continue    *Block
   457  	_fallthrough *Block
   458  }
   459  
   460  // Destinations associated with a labeled block.
   461  // We populate these as labels are encountered in forward gotos or
   462  // labeled statements.
   463  type lblock struct {
   464  	_goto     *Block
   465  	_break    *Block
   466  	_continue *Block
   467  }
   468  
   469  // labeledBlock returns the branch target associated with the
   470  // specified label, creating it if needed.
   471  func (b *builder) labeledBlock(label *ast.Ident, stmt *ast.LabeledStmt) *lblock {
   472  	lb := b.lblocks[label.Name]
   473  	if lb == nil {
   474  		lb = &lblock{_goto: b.newBlock(KindLabel, nil)}
   475  		if b.lblocks == nil {
   476  			b.lblocks = make(map[string]*lblock)
   477  		}
   478  		b.lblocks[label.Name] = lb
   479  	}
   480  	// Fill in the label later (in case of forward goto).
   481  	// Stmt may be set already if labels are duplicated (ill-typed).
   482  	if stmt != nil && lb._goto.Stmt == nil {
   483  		lb._goto.Stmt = stmt
   484  	}
   485  	return lb
   486  }
   487  
   488  // newBlock appends a new unconnected basic block to b.cfg's block
   489  // slice and returns it.
   490  // It does not automatically become the current block.
   491  // comment is an optional string for more readable debugging output.
   492  func (b *builder) newBlock(kind BlockKind, stmt ast.Stmt) *Block {
   493  	block := &Block{
   494  		Index: int32(len(b.blocks)),
   495  		Kind:  kind,
   496  		Stmt:  stmt,
   497  	}
   498  	block.Succs = block.succs2[:0]
   499  	b.blocks = append(b.blocks, block)
   500  	return block
   501  }
   502  
   503  func (b *builder) add(n ast.Node) {
   504  	b.current.Nodes = append(b.current.Nodes, n)
   505  }
   506  
   507  // jump adds an edge from the current block to the target block,
   508  // and sets b.current to nil.
   509  func (b *builder) jump(target *Block) {
   510  	b.current.Succs = append(b.current.Succs, target)
   511  	b.current = nil
   512  }
   513  
   514  // ifelse emits edges from the current block to the t and f blocks,
   515  // and sets b.current to nil.
   516  func (b *builder) ifelse(t, f *Block) {
   517  	b.current.Succs = append(b.current.Succs, t, f)
   518  	b.current = nil
   519  }
   520
View as plain text