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