sanity.go

Documentation: golang.org/x/tools/go/ssa

     1  // Copyright 2013 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 ssa
     6  
     7  // An optional pass for sanity-checking invariants of the SSA representation.
     8  // Currently it checks CFG invariants but little at the instruction level.
     9  
    10  import (
    11  	"bytes"
    12  	"fmt"
    13  	"go/types"
    14  	"io"
    15  	"os"
    16  	"strings"
    17  )
    18  
    19  type sanity struct {
    20  	reporter io.Writer
    21  	fn       *Function
    22  	block    *BasicBlock
    23  	instrs   map[Instruction]struct{}
    24  	insane   bool
    25  }
    26  
    27  // sanityCheck performs integrity checking of the SSA representation
    28  // of the function fn and returns true if it was valid.  Diagnostics
    29  // are written to reporter if non-nil, os.Stderr otherwise.  Some
    30  // diagnostics are only warnings and do not imply a negative result.
    31  //
    32  // Sanity-checking is intended to facilitate the debugging of code
    33  // transformation passes.
    34  func sanityCheck(fn *Function, reporter io.Writer) bool {
    35  	if reporter == nil {
    36  		reporter = os.Stderr
    37  	}
    38  	return (&sanity{reporter: reporter}).checkFunction(fn)
    39  }
    40  
    41  // mustSanityCheck is like sanityCheck but panics instead of returning
    42  // a negative result.
    43  func mustSanityCheck(fn *Function, reporter io.Writer) {
    44  	if !sanityCheck(fn, reporter) {
    45  		fn.WriteTo(os.Stderr)
    46  		panic("SanityCheck failed")
    47  	}
    48  }
    49  
    50  func (s *sanity) diagnostic(prefix, format string, args ...interface{}) {
    51  	fmt.Fprintf(s.reporter, "%s: function %s", prefix, s.fn)
    52  	if s.block != nil {
    53  		fmt.Fprintf(s.reporter, ", block %s", s.block)
    54  	}
    55  	io.WriteString(s.reporter, ": ")
    56  	fmt.Fprintf(s.reporter, format, args...)
    57  	io.WriteString(s.reporter, "\n")
    58  }
    59  
    60  func (s *sanity) errorf(format string, args ...interface{}) {
    61  	s.insane = true
    62  	s.diagnostic("Error", format, args...)
    63  }
    64  
    65  func (s *sanity) warnf(format string, args ...interface{}) {
    66  	s.diagnostic("Warning", format, args...)
    67  }
    68  
    69  // findDuplicate returns an arbitrary basic block that appeared more
    70  // than once in blocks, or nil if all were unique.
    71  func findDuplicate(blocks []*BasicBlock) *BasicBlock {
    72  	if len(blocks) < 2 {
    73  		return nil
    74  	}
    75  	if blocks[0] == blocks[1] {
    76  		return blocks[0]
    77  	}
    78  	// Slow path:
    79  	m := make(map[*BasicBlock]bool)
    80  	for _, b := range blocks {
    81  		if m[b] {
    82  			return b
    83  		}
    84  		m[b] = true
    85  	}
    86  	return nil
    87  }
    88  
    89  func (s *sanity) checkInstr(idx int, instr Instruction) {
    90  	switch instr := instr.(type) {
    91  	case *If, *Jump, *Return, *Panic:
    92  		s.errorf("control flow instruction not at end of block")
    93  	case *Phi:
    94  		if idx == 0 {
    95  			// It suffices to apply this check to just the first phi node.
    96  			if dup := findDuplicate(s.block.Preds); dup != nil {
    97  				s.errorf("phi node in block with duplicate predecessor %s", dup)
    98  			}
    99  		} else {
   100  			prev := s.block.Instrs[idx-1]
   101  			if _, ok := prev.(*Phi); !ok {
   102  				s.errorf("Phi instruction follows a non-Phi: %T", prev)
   103  			}
   104  		}
   105  		if ne, np := len(instr.Edges), len(s.block.Preds); ne != np {
   106  			s.errorf("phi node has %d edges but %d predecessors", ne, np)
   107  
   108  		} else {
   109  			for i, e := range instr.Edges {
   110  				if e == nil {
   111  					s.errorf("phi node '%s' has no value for edge #%d from %s", instr.Comment, i, s.block.Preds[i])
   112  				} else if !types.Identical(instr.typ, e.Type()) {
   113  					s.errorf("phi node '%s' has a different type (%s) for edge #%d from %s (%s)",
   114  						instr.Comment, instr.Type(), i, s.block.Preds[i], e.Type())
   115  				}
   116  			}
   117  		}
   118  
   119  	case *Alloc:
   120  		if !instr.Heap {
   121  			found := false
   122  			for _, l := range s.fn.Locals {
   123  				if l == instr {
   124  					found = true
   125  					break
   126  				}
   127  			}
   128  			if !found {
   129  				s.errorf("local alloc %s = %s does not appear in Function.Locals", instr.Name(), instr)
   130  			}
   131  		}
   132  
   133  	case *BinOp:
   134  	case *Call:
   135  		if common := instr.Call; common.IsInvoke() {
   136  			if !types.IsInterface(common.Value.Type()) {
   137  				s.errorf("invoke on %s (%s) which is not an interface type (or type param)", common.Value, common.Value.Type())
   138  			}
   139  		}
   140  	case *ChangeInterface:
   141  	case *ChangeType:
   142  	case *SliceToArrayPointer:
   143  	case *Convert:
   144  		if from := instr.X.Type(); !isBasicConvTypes(typeSetOf(from)) {
   145  			if to := instr.Type(); !isBasicConvTypes(typeSetOf(to)) {
   146  				s.errorf("convert %s -> %s: at least one type must be basic (or all basic, []byte, or []rune)", from, to)
   147  			}
   148  		}
   149  	case *MultiConvert:
   150  	case *Defer:
   151  	case *Extract:
   152  	case *Field:
   153  	case *FieldAddr:
   154  	case *Go:
   155  	case *Index:
   156  	case *IndexAddr:
   157  	case *Lookup:
   158  	case *MakeChan:
   159  	case *MakeClosure:
   160  		numFree := len(instr.Fn.(*Function).FreeVars)
   161  		numBind := len(instr.Bindings)
   162  		if numFree != numBind {
   163  			s.errorf("MakeClosure has %d Bindings for function %s with %d free vars",
   164  				numBind, instr.Fn, numFree)
   165  
   166  		}
   167  		if recv := instr.Type().(*types.Signature).Recv(); recv != nil {
   168  			s.errorf("MakeClosure's type includes receiver %s", recv.Type())
   169  		}
   170  
   171  	case *MakeInterface:
   172  	case *MakeMap:
   173  	case *MakeSlice:
   174  	case *MapUpdate:
   175  	case *Next:
   176  	case *Range:
   177  	case *RunDefers:
   178  	case *Select:
   179  	case *Send:
   180  	case *Slice:
   181  	case *Store:
   182  	case *TypeAssert:
   183  	case *UnOp:
   184  	case *DebugRef:
   185  		// TODO(adonovan): implement checks.
   186  	default:
   187  		panic(fmt.Sprintf("Unknown instruction type: %T", instr))
   188  	}
   189  
   190  	if call, ok := instr.(CallInstruction); ok {
   191  		if call.Common().Signature() == nil {
   192  			s.errorf("nil signature: %s", call)
   193  		}
   194  	}
   195  
   196  	// Check that value-defining instructions have valid types
   197  	// and a valid referrer list.
   198  	if v, ok := instr.(Value); ok {
   199  		t := v.Type()
   200  		if t == nil {
   201  			s.errorf("no type: %s = %s", v.Name(), v)
   202  		} else if t == tRangeIter {
   203  			// not a proper type; ignore.
   204  		} else if b, ok := t.Underlying().(*types.Basic); ok && b.Info()&types.IsUntyped != 0 {
   205  			s.errorf("instruction has 'untyped' result: %s = %s : %s", v.Name(), v, t)
   206  		}
   207  		s.checkReferrerList(v)
   208  	}
   209  
   210  	// Untyped constants are legal as instruction Operands(),
   211  	// for example:
   212  	//   _ = "foo"[0]
   213  	// or:
   214  	//   if wordsize==64 {...}
   215  
   216  	// All other non-Instruction Values can be found via their
   217  	// enclosing Function or Package.
   218  }
   219  
   220  func (s *sanity) checkFinalInstr(instr Instruction) {
   221  	switch instr := instr.(type) {
   222  	case *If:
   223  		if nsuccs := len(s.block.Succs); nsuccs != 2 {
   224  			s.errorf("If-terminated block has %d successors; expected 2", nsuccs)
   225  			return
   226  		}
   227  		if s.block.Succs[0] == s.block.Succs[1] {
   228  			s.errorf("If-instruction has same True, False target blocks: %s", s.block.Succs[0])
   229  			return
   230  		}
   231  
   232  	case *Jump:
   233  		if nsuccs := len(s.block.Succs); nsuccs != 1 {
   234  			s.errorf("Jump-terminated block has %d successors; expected 1", nsuccs)
   235  			return
   236  		}
   237  
   238  	case *Return:
   239  		if nsuccs := len(s.block.Succs); nsuccs != 0 {
   240  			s.errorf("Return-terminated block has %d successors; expected none", nsuccs)
   241  			return
   242  		}
   243  		if na, nf := len(instr.Results), s.fn.Signature.Results().Len(); nf != na {
   244  			s.errorf("%d-ary return in %d-ary function", na, nf)
   245  		}
   246  
   247  	case *Panic:
   248  		if nsuccs := len(s.block.Succs); nsuccs != 0 {
   249  			s.errorf("Panic-terminated block has %d successors; expected none", nsuccs)
   250  			return
   251  		}
   252  
   253  	default:
   254  		s.errorf("non-control flow instruction at end of block")
   255  	}
   256  }
   257  
   258  func (s *sanity) checkBlock(b *BasicBlock, index int) {
   259  	s.block = b
   260  
   261  	if b.Index != index {
   262  		s.errorf("block has incorrect Index %d", b.Index)
   263  	}
   264  	if b.parent != s.fn {
   265  		s.errorf("block has incorrect parent %s", b.parent)
   266  	}
   267  
   268  	// Check all blocks are reachable.
   269  	// (The entry block is always implicitly reachable,
   270  	// as is the Recover block, if any.)
   271  	if (index > 0 && b != b.parent.Recover) && len(b.Preds) == 0 {
   272  		s.warnf("unreachable block")
   273  		if b.Instrs == nil {
   274  			// Since this block is about to be pruned,
   275  			// tolerating transient problems in it
   276  			// simplifies other optimizations.
   277  			return
   278  		}
   279  	}
   280  
   281  	// Check predecessor and successor relations are dual,
   282  	// and that all blocks in CFG belong to same function.
   283  	for _, a := range b.Preds {
   284  		found := false
   285  		for _, bb := range a.Succs {
   286  			if bb == b {
   287  				found = true
   288  				break
   289  			}
   290  		}
   291  		if !found {
   292  			s.errorf("expected successor edge in predecessor %s; found only: %s", a, a.Succs)
   293  		}
   294  		if a.parent != s.fn {
   295  			s.errorf("predecessor %s belongs to different function %s", a, a.parent)
   296  		}
   297  	}
   298  	for _, c := range b.Succs {
   299  		found := false
   300  		for _, bb := range c.Preds {
   301  			if bb == b {
   302  				found = true
   303  				break
   304  			}
   305  		}
   306  		if !found {
   307  			s.errorf("expected predecessor edge in successor %s; found only: %s", c, c.Preds)
   308  		}
   309  		if c.parent != s.fn {
   310  			s.errorf("successor %s belongs to different function %s", c, c.parent)
   311  		}
   312  	}
   313  
   314  	// Check each instruction is sane.
   315  	n := len(b.Instrs)
   316  	if n == 0 {
   317  		s.errorf("basic block contains no instructions")
   318  	}
   319  	var rands [10]*Value // reuse storage
   320  	for j, instr := range b.Instrs {
   321  		if instr == nil {
   322  			s.errorf("nil instruction at index %d", j)
   323  			continue
   324  		}
   325  		if b2 := instr.Block(); b2 == nil {
   326  			s.errorf("nil Block() for instruction at index %d", j)
   327  			continue
   328  		} else if b2 != b {
   329  			s.errorf("wrong Block() (%s) for instruction at index %d ", b2, j)
   330  			continue
   331  		}
   332  		if j < n-1 {
   333  			s.checkInstr(j, instr)
   334  		} else {
   335  			s.checkFinalInstr(instr)
   336  		}
   337  
   338  		// Check Instruction.Operands.
   339  	operands:
   340  		for i, op := range instr.Operands(rands[:0]) {
   341  			if op == nil {
   342  				s.errorf("nil operand pointer %d of %s", i, instr)
   343  				continue
   344  			}
   345  			val := *op
   346  			if val == nil {
   347  				continue // a nil operand is ok
   348  			}
   349  
   350  			// Check that "untyped" types only appear on constant operands.
   351  			if _, ok := (*op).(*Const); !ok {
   352  				if basic, ok := (*op).Type().Underlying().(*types.Basic); ok {
   353  					if basic.Info()&types.IsUntyped != 0 {
   354  						s.errorf("operand #%d of %s is untyped: %s", i, instr, basic)
   355  					}
   356  				}
   357  			}
   358  
   359  			// Check that Operands that are also Instructions belong to same function.
   360  			// TODO(adonovan): also check their block dominates block b.
   361  			if val, ok := val.(Instruction); ok {
   362  				if val.Block() == nil {
   363  					s.errorf("operand %d of %s is an instruction (%s) that belongs to no block", i, instr, val)
   364  				} else if val.Parent() != s.fn {
   365  					s.errorf("operand %d of %s is an instruction (%s) from function %s", i, instr, val, val.Parent())
   366  				}
   367  			}
   368  
   369  			// Check that each function-local operand of
   370  			// instr refers back to instr.  (NB: quadratic)
   371  			switch val := val.(type) {
   372  			case *Const, *Global, *Builtin:
   373  				continue // not local
   374  			case *Function:
   375  				if val.parent == nil {
   376  					continue // only anon functions are local
   377  				}
   378  			}
   379  
   380  			// TODO(adonovan): check val.Parent() != nil <=> val.Referrers() is defined.
   381  
   382  			if refs := val.Referrers(); refs != nil {
   383  				for _, ref := range *refs {
   384  					if ref == instr {
   385  						continue operands
   386  					}
   387  				}
   388  				s.errorf("operand %d of %s (%s) does not refer to us", i, instr, val)
   389  			} else {
   390  				s.errorf("operand %d of %s (%s) has no referrers", i, instr, val)
   391  			}
   392  		}
   393  	}
   394  }
   395  
   396  func (s *sanity) checkReferrerList(v Value) {
   397  	refs := v.Referrers()
   398  	if refs == nil {
   399  		s.errorf("%s has missing referrer list", v.Name())
   400  		return
   401  	}
   402  	for i, ref := range *refs {
   403  		if _, ok := s.instrs[ref]; !ok {
   404  			s.errorf("%s.Referrers()[%d] = %s is not an instruction belonging to this function", v.Name(), i, ref)
   405  		}
   406  	}
   407  }
   408  
   409  func (s *sanity) checkFunction(fn *Function) bool {
   410  	// TODO(adonovan): check Function invariants:
   411  	// - check params match signature
   412  	// - check transient fields are nil
   413  	// - warn if any fn.Locals do not appear among block instructions.
   414  
   415  	// TODO(taking): Sanity check origin, typeparams, and typeargs.
   416  	s.fn = fn
   417  	if fn.Prog == nil {
   418  		s.errorf("nil Prog")
   419  	}
   420  
   421  	var buf bytes.Buffer
   422  	_ = fn.String()               // must not crash
   423  	_ = fn.RelString(fn.relPkg()) // must not crash
   424  	WriteFunction(&buf, fn)       // must not crash
   425  
   426  	// All functions have a package, except delegates (which are
   427  	// shared across packages, or duplicated as weak symbols in a
   428  	// separate-compilation model), and error.Error.
   429  	if fn.Pkg == nil {
   430  		if strings.HasPrefix(fn.Synthetic, "from type information (on demand)") ||
   431  			strings.HasPrefix(fn.Synthetic, "wrapper ") ||
   432  			strings.HasPrefix(fn.Synthetic, "bound ") ||
   433  			strings.HasPrefix(fn.Synthetic, "thunk ") ||
   434  			strings.HasSuffix(fn.name, "Error") ||
   435  			strings.HasPrefix(fn.Synthetic, "instance ") ||
   436  			strings.HasPrefix(fn.Synthetic, "instantiation ") ||
   437  			(fn.parent != nil && len(fn.typeargs) > 0) /* anon fun in instance */ {
   438  			// ok
   439  		} else {
   440  			s.errorf("nil Pkg")
   441  		}
   442  	}
   443  	if src, syn := fn.Synthetic == "", fn.Syntax() != nil; src != syn {
   444  		if len(fn.typeargs) > 0 && fn.Prog.mode&InstantiateGenerics != 0 {
   445  			// ok (instantiation with InstantiateGenerics on)
   446  		} else if fn.topLevelOrigin != nil && len(fn.typeargs) > 0 {
   447  			// ok (we always have the syntax set for instantiation)
   448  		} else {
   449  			s.errorf("got fromSource=%t, hasSyntax=%t; want same values", src, syn)
   450  		}
   451  	}
   452  	for i, l := range fn.Locals {
   453  		if l.Parent() != fn {
   454  			s.errorf("Local %s at index %d has wrong parent", l.Name(), i)
   455  		}
   456  		if l.Heap {
   457  			s.errorf("Local %s at index %d has Heap flag set", l.Name(), i)
   458  		}
   459  	}
   460  	// Build the set of valid referrers.
   461  	s.instrs = make(map[Instruction]struct{})
   462  	for _, b := range fn.Blocks {
   463  		for _, instr := range b.Instrs {
   464  			s.instrs[instr] = struct{}{}
   465  		}
   466  	}
   467  	for i, p := range fn.Params {
   468  		if p.Parent() != fn {
   469  			s.errorf("Param %s at index %d has wrong parent", p.Name(), i)
   470  		}
   471  		// Check common suffix of Signature and Params match type.
   472  		if sig := fn.Signature; sig != nil {
   473  			j := i - len(fn.Params) + sig.Params().Len() // index within sig.Params
   474  			if j < 0 {
   475  				continue
   476  			}
   477  			if !types.Identical(p.Type(), sig.Params().At(j).Type()) {
   478  				s.errorf("Param %s at index %d has wrong type (%s, versus %s in Signature)", p.Name(), i, p.Type(), sig.Params().At(j).Type())
   479  
   480  			}
   481  		}
   482  		s.checkReferrerList(p)
   483  	}
   484  	for i, fv := range fn.FreeVars {
   485  		if fv.Parent() != fn {
   486  			s.errorf("FreeVar %s at index %d has wrong parent", fv.Name(), i)
   487  		}
   488  		s.checkReferrerList(fv)
   489  	}
   490  
   491  	if fn.Blocks != nil && len(fn.Blocks) == 0 {
   492  		// Function _had_ blocks (so it's not external) but
   493  		// they were "optimized" away, even the entry block.
   494  		s.errorf("Blocks slice is non-nil but empty")
   495  	}
   496  	for i, b := range fn.Blocks {
   497  		if b == nil {
   498  			s.warnf("nil *BasicBlock at f.Blocks[%d]", i)
   499  			continue
   500  		}
   501  		s.checkBlock(b, i)
   502  	}
   503  	if fn.Recover != nil && fn.Blocks[fn.Recover.Index] != fn.Recover {
   504  		s.errorf("Recover block is not in Blocks slice")
   505  	}
   506  
   507  	s.block = nil
   508  	for i, anon := range fn.AnonFuncs {
   509  		if anon.Parent() != fn {
   510  			s.errorf("AnonFuncs[%d]=%s but %s.Parent()=%s", i, anon, anon, anon.Parent())
   511  		}
   512  		if i != int(anon.anonIdx) {
   513  			s.errorf("AnonFuncs[%d]=%s but %s.anonIdx=%d", i, anon, anon, anon.anonIdx)
   514  		}
   515  	}
   516  	s.fn = nil
   517  	return !s.insane
   518  }
   519  
   520  // sanityCheckPackage checks invariants of packages upon creation.
   521  // It does not require that the package is built.
   522  // Unlike sanityCheck (for functions), it just panics at the first error.
   523  func sanityCheckPackage(pkg *Package) {
   524  	if pkg.Pkg == nil {
   525  		panic(fmt.Sprintf("Package %s has no Object", pkg))
   526  	}
   527  	_ = pkg.String() // must not crash
   528  
   529  	for name, mem := range pkg.Members {
   530  		if name != mem.Name() {
   531  			panic(fmt.Sprintf("%s: %T.Name() = %s, want %s",
   532  				pkg.Pkg.Path(), mem, mem.Name(), name))
   533  		}
   534  		obj := mem.Object()
   535  		if obj == nil {
   536  			// This check is sound because fields
   537  			// {Global,Function}.object have type
   538  			// types.Object.  (If they were declared as
   539  			// *types.{Var,Func}, we'd have a non-empty
   540  			// interface containing a nil pointer.)
   541  
   542  			continue // not all members have typechecker objects
   543  		}
   544  		if obj.Name() != name {
   545  			if obj.Name() == "init" && strings.HasPrefix(mem.Name(), "init#") {
   546  				// Ok.  The name of a declared init function varies between
   547  				// its types.Func ("init") and its ssa.Function ("init#%d").
   548  			} else {
   549  				panic(fmt.Sprintf("%s: %T.Object().Name() = %s, want %s",
   550  					pkg.Pkg.Path(), mem, obj.Name(), name))
   551  			}
   552  		}
   553  		if obj.Pos() != mem.Pos() {
   554  			panic(fmt.Sprintf("%s Pos=%d obj.Pos=%d", mem, mem.Pos(), obj.Pos()))
   555  		}
   556  	}
   557  }
   558
View as plain text