Source file src/cmd/compile/internal/ssa/check.go

Documentation: cmd/compile/internal/ssa

     1  // Copyright 2015 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  import (
     8  	"math"
     9  	"math/bits"
    10  )
    11  
    12  // checkFunc checks invariants of f.
    13  func checkFunc(f *Func) {
    14  	blockMark := make([]bool, f.NumBlocks())
    15  	valueMark := make([]bool, f.NumValues())
    16  
    17  	for _, b := range f.Blocks {
    18  		if blockMark[b.ID] {
    19  			f.Fatalf("block %s appears twice in %s!", b, f.Name)
    20  		}
    21  		blockMark[b.ID] = true
    22  		if b.Func != f {
    23  			f.Fatalf("%s.Func=%s, want %s", b, b.Func.Name, f.Name)
    24  		}
    25  
    26  		for i, e := range b.Preds {
    27  			if se := e.b.Succs[e.i]; se.b != b || se.i != i {
    28  				f.Fatalf("block pred/succ not crosslinked correctly %d:%s %d:%s", i, b, se.i, se.b)
    29  			}
    30  		}
    31  		for i, e := range b.Succs {
    32  			if pe := e.b.Preds[e.i]; pe.b != b || pe.i != i {
    33  				f.Fatalf("block succ/pred not crosslinked correctly %d:%s %d:%s", i, b, pe.i, pe.b)
    34  			}
    35  		}
    36  
    37  		switch b.Kind {
    38  		case BlockExit:
    39  			if len(b.Succs) != 0 {
    40  				f.Fatalf("exit block %s has successors", b)
    41  			}
    42  			if b.Control == nil {
    43  				f.Fatalf("exit block %s has no control value", b)
    44  			}
    45  			if !b.Control.Type.IsMemory() {
    46  				f.Fatalf("exit block %s has non-memory control value %s", b, b.Control.LongString())
    47  			}
    48  		case BlockRet:
    49  			if len(b.Succs) != 0 {
    50  				f.Fatalf("ret block %s has successors", b)
    51  			}
    52  			if b.Control == nil {
    53  				f.Fatalf("ret block %s has nil control", b)
    54  			}
    55  			if !b.Control.Type.IsMemory() {
    56  				f.Fatalf("ret block %s has non-memory control value %s", b, b.Control.LongString())
    57  			}
    58  		case BlockRetJmp:
    59  			if len(b.Succs) != 0 {
    60  				f.Fatalf("retjmp block %s len(Succs)==%d, want 0", b, len(b.Succs))
    61  			}
    62  			if b.Control == nil {
    63  				f.Fatalf("retjmp block %s has nil control", b)
    64  			}
    65  			if !b.Control.Type.IsMemory() {
    66  				f.Fatalf("retjmp block %s has non-memory control value %s", b, b.Control.LongString())
    67  			}
    68  			if b.Aux == nil {
    69  				f.Fatalf("retjmp block %s has nil Aux field", b)
    70  			}
    71  		case BlockPlain:
    72  			if len(b.Succs) != 1 {
    73  				f.Fatalf("plain block %s len(Succs)==%d, want 1", b, len(b.Succs))
    74  			}
    75  			if b.Control != nil {
    76  				f.Fatalf("plain block %s has non-nil control %s", b, b.Control.LongString())
    77  			}
    78  		case BlockIf:
    79  			if len(b.Succs) != 2 {
    80  				f.Fatalf("if block %s len(Succs)==%d, want 2", b, len(b.Succs))
    81  			}
    82  			if b.Control == nil {
    83  				f.Fatalf("if block %s has no control value", b)
    84  			}
    85  			if !b.Control.Type.IsBoolean() {
    86  				f.Fatalf("if block %s has non-bool control value %s", b, b.Control.LongString())
    87  			}
    88  		case BlockDefer:
    89  			if len(b.Succs) != 2 {
    90  				f.Fatalf("defer block %s len(Succs)==%d, want 2", b, len(b.Succs))
    91  			}
    92  			if b.Control == nil {
    93  				f.Fatalf("defer block %s has no control value", b)
    94  			}
    95  			if !b.Control.Type.IsMemory() {
    96  				f.Fatalf("defer block %s has non-memory control value %s", b, b.Control.LongString())
    97  			}
    98  		case BlockFirst:
    99  			if len(b.Succs) != 2 {
   100  				f.Fatalf("plain/dead block %s len(Succs)==%d, want 2", b, len(b.Succs))
   101  			}
   102  			if b.Control != nil {
   103  				f.Fatalf("plain/dead block %s has a control value", b)
   104  			}
   105  		}
   106  		if len(b.Succs) != 2 && b.Likely != BranchUnknown {
   107  			f.Fatalf("likeliness prediction %d for block %s with %d successors", b.Likely, b, len(b.Succs))
   108  		}
   109  
   110  		for _, v := range b.Values {
   111  			// Check to make sure argument count makes sense (argLen of -1 indicates
   112  			// variable length args)
   113  			nArgs := opcodeTable[v.Op].argLen
   114  			if nArgs != -1 && int32(len(v.Args)) != nArgs {
   115  				f.Fatalf("value %s has %d args, expected %d", v.LongString(),
   116  					len(v.Args), nArgs)
   117  			}
   118  
   119  			// Check to make sure aux values make sense.
   120  			canHaveAux := false
   121  			canHaveAuxInt := false
   122  			switch opcodeTable[v.Op].auxType {
   123  			case auxNone:
   124  			case auxBool:
   125  				if v.AuxInt < 0 || v.AuxInt > 1 {
   126  					f.Fatalf("bad bool AuxInt value for %v", v)
   127  				}
   128  				canHaveAuxInt = true
   129  			case auxInt8:
   130  				if v.AuxInt != int64(int8(v.AuxInt)) {
   131  					f.Fatalf("bad int8 AuxInt value for %v", v)
   132  				}
   133  				canHaveAuxInt = true
   134  			case auxInt16:
   135  				if v.AuxInt != int64(int16(v.AuxInt)) {
   136  					f.Fatalf("bad int16 AuxInt value for %v", v)
   137  				}
   138  				canHaveAuxInt = true
   139  			case auxInt32:
   140  				if v.AuxInt != int64(int32(v.AuxInt)) {
   141  					f.Fatalf("bad int32 AuxInt value for %v", v)
   142  				}
   143  				canHaveAuxInt = true
   144  			case auxInt64, auxFloat64:
   145  				canHaveAuxInt = true
   146  			case auxInt128:
   147  				// AuxInt must be zero, so leave canHaveAuxInt set to false.
   148  			case auxFloat32:
   149  				canHaveAuxInt = true
   150  				if !isExactFloat32(v.AuxFloat()) {
   151  					f.Fatalf("value %v has an AuxInt value that is not an exact float32", v)
   152  				}
   153  			case auxString, auxSym, auxTyp:
   154  				canHaveAux = true
   155  			case auxSymOff, auxSymValAndOff, auxTypSize:
   156  				canHaveAuxInt = true
   157  				canHaveAux = true
   158  			case auxSymInt32:
   159  				if v.AuxInt != int64(int32(v.AuxInt)) {
   160  					f.Fatalf("bad int32 AuxInt value for %v", v)
   161  				}
   162  				canHaveAuxInt = true
   163  				canHaveAux = true
   164  			case auxCCop:
   165  				if _, ok := v.Aux.(Op); !ok {
   166  					f.Fatalf("bad type %T for CCop in %v", v.Aux, v)
   167  				}
   168  				canHaveAux = true
   169  			default:
   170  				f.Fatalf("unknown aux type for %s", v.Op)
   171  			}
   172  			if !canHaveAux && v.Aux != nil {
   173  				f.Fatalf("value %s has an Aux value %v but shouldn't", v.LongString(), v.Aux)
   174  			}
   175  			if !canHaveAuxInt && v.AuxInt != 0 {
   176  				f.Fatalf("value %s has an AuxInt value %d but shouldn't", v.LongString(), v.AuxInt)
   177  			}
   178  
   179  			for i, arg := range v.Args {
   180  				if arg == nil {
   181  					f.Fatalf("value %s has nil arg", v.LongString())
   182  				}
   183  				if v.Op != OpPhi {
   184  					// For non-Phi ops, memory args must be last, if present
   185  					if arg.Type.IsMemory() && i != len(v.Args)-1 {
   186  						f.Fatalf("value %s has non-final memory arg (%d < %d)", v.LongString(), i, len(v.Args)-1)
   187  					}
   188  				}
   189  			}
   190  
   191  			if valueMark[v.ID] {
   192  				f.Fatalf("value %s appears twice!", v.LongString())
   193  			}
   194  			valueMark[v.ID] = true
   195  
   196  			if v.Block != b {
   197  				f.Fatalf("%s.block != %s", v, b)
   198  			}
   199  			if v.Op == OpPhi && len(v.Args) != len(b.Preds) {
   200  				f.Fatalf("phi length %s does not match pred length %d for block %s", v.LongString(), len(b.Preds), b)
   201  			}
   202  
   203  			if v.Op == OpAddr {
   204  				if len(v.Args) == 0 {
   205  					f.Fatalf("no args for OpAddr %s", v.LongString())
   206  				}
   207  				if v.Args[0].Op != OpSB {
   208  					f.Fatalf("bad arg to OpAddr %v", v)
   209  				}
   210  			}
   211  
   212  			if v.Op == OpLocalAddr {
   213  				if len(v.Args) != 2 {
   214  					f.Fatalf("wrong # of args for OpLocalAddr %s", v.LongString())
   215  				}
   216  				if v.Args[0].Op != OpSP {
   217  					f.Fatalf("bad arg 0 to OpLocalAddr %v", v)
   218  				}
   219  				if !v.Args[1].Type.IsMemory() {
   220  					f.Fatalf("bad arg 1 to OpLocalAddr %v", v)
   221  				}
   222  			}
   223  
   224  			if f.RegAlloc != nil && f.Config.SoftFloat && v.Type.IsFloat() {
   225  				f.Fatalf("unexpected floating-point type %v", v.LongString())
   226  			}
   227  
   228  			// Check types.
   229  			// TODO: more type checks?
   230  			switch c := f.Config; v.Op {
   231  			case OpSP, OpSB:
   232  				if v.Type != c.Types.Uintptr {
   233  					f.Fatalf("bad %s type: want uintptr, have %s",
   234  						v.Op, v.Type.String())
   235  				}
   236  			}
   237  
   238  			// TODO: check for cycles in values
   239  		}
   240  	}
   241  
   242  	// Check to make sure all Blocks referenced are in the function.
   243  	if !blockMark[f.Entry.ID] {
   244  		f.Fatalf("entry block %v is missing", f.Entry)
   245  	}
   246  	for _, b := range f.Blocks {
   247  		for _, c := range b.Preds {
   248  			if !blockMark[c.b.ID] {
   249  				f.Fatalf("predecessor block %v for %v is missing", c, b)
   250  			}
   251  		}
   252  		for _, c := range b.Succs {
   253  			if !blockMark[c.b.ID] {
   254  				f.Fatalf("successor block %v for %v is missing", c, b)
   255  			}
   256  		}
   257  	}
   258  
   259  	if len(f.Entry.Preds) > 0 {
   260  		f.Fatalf("entry block %s of %s has predecessor(s) %v", f.Entry, f.Name, f.Entry.Preds)
   261  	}
   262  
   263  	// Check to make sure all Values referenced are in the function.
   264  	for _, b := range f.Blocks {
   265  		for _, v := range b.Values {
   266  			for i, a := range v.Args {
   267  				if !valueMark[a.ID] {
   268  					f.Fatalf("%v, arg %d of %s, is missing", a, i, v.LongString())
   269  				}
   270  			}
   271  		}
   272  		if b.Control != nil && !valueMark[b.Control.ID] {
   273  			f.Fatalf("control value for %s is missing: %v", b, b.Control)
   274  		}
   275  	}
   276  	for b := f.freeBlocks; b != nil; b = b.succstorage[0].b {
   277  		if blockMark[b.ID] {
   278  			f.Fatalf("used block b%d in free list", b.ID)
   279  		}
   280  	}
   281  	for v := f.freeValues; v != nil; v = v.argstorage[0] {
   282  		if valueMark[v.ID] {
   283  			f.Fatalf("used value v%d in free list", v.ID)
   284  		}
   285  	}
   286  
   287  	// Check to make sure all args dominate uses.
   288  	if f.RegAlloc == nil {
   289  		// Note: regalloc introduces non-dominating args.
   290  		// See TODO in regalloc.go.
   291  		sdom := f.sdom()
   292  		for _, b := range f.Blocks {
   293  			for _, v := range b.Values {
   294  				for i, arg := range v.Args {
   295  					x := arg.Block
   296  					y := b
   297  					if v.Op == OpPhi {
   298  						y = b.Preds[i].b
   299  					}
   300  					if !domCheck(f, sdom, x, y) {
   301  						f.Fatalf("arg %d of value %s does not dominate, arg=%s", i, v.LongString(), arg.LongString())
   302  					}
   303  				}
   304  			}
   305  			if b.Control != nil && !domCheck(f, sdom, b.Control.Block, b) {
   306  				f.Fatalf("control value %s for %s doesn't dominate", b.Control, b)
   307  			}
   308  		}
   309  	}
   310  
   311  	// Check loop construction
   312  	if f.RegAlloc == nil && f.pass != nil { // non-nil pass allows better-targeted debug printing
   313  		ln := f.loopnest()
   314  		if !ln.hasIrreducible {
   315  			po := f.postorder() // use po to avoid unreachable blocks.
   316  			for _, b := range po {
   317  				for _, s := range b.Succs {
   318  					bb := s.Block()
   319  					if ln.b2l[b.ID] == nil && ln.b2l[bb.ID] != nil && bb != ln.b2l[bb.ID].header {
   320  						f.Fatalf("block %s not in loop branches to non-header block %s in loop", b.String(), bb.String())
   321  					}
   322  					if ln.b2l[b.ID] != nil && ln.b2l[bb.ID] != nil && bb != ln.b2l[bb.ID].header && !ln.b2l[b.ID].isWithinOrEq(ln.b2l[bb.ID]) {
   323  						f.Fatalf("block %s in loop branches to non-header block %s in non-containing loop", b.String(), bb.String())
   324  					}
   325  				}
   326  			}
   327  		}
   328  	}
   329  
   330  	// Check use counts
   331  	uses := make([]int32, f.NumValues())
   332  	for _, b := range f.Blocks {
   333  		for _, v := range b.Values {
   334  			for _, a := range v.Args {
   335  				uses[a.ID]++
   336  			}
   337  		}
   338  		if b.Control != nil {
   339  			uses[b.Control.ID]++
   340  		}
   341  	}
   342  	for _, b := range f.Blocks {
   343  		for _, v := range b.Values {
   344  			if v.Uses != uses[v.ID] {
   345  				f.Fatalf("%s has %d uses, but has Uses=%d", v, uses[v.ID], v.Uses)
   346  			}
   347  		}
   348  	}
   349  
   350  	memCheck(f)
   351  }
   352  
   353  func memCheck(f *Func) {
   354  	// Check that if a tuple has a memory type, it is second.
   355  	for _, b := range f.Blocks {
   356  		for _, v := range b.Values {
   357  			if v.Type.IsTuple() && v.Type.FieldType(0).IsMemory() {
   358  				f.Fatalf("memory is first in a tuple: %s\n", v.LongString())
   359  			}
   360  		}
   361  	}
   362  
   363  	// Single live memory checks.
   364  	// These checks only work if there are no memory copies.
   365  	// (Memory copies introduce ambiguity about which mem value is really live.
   366  	// probably fixable, but it's easier to avoid the problem.)
   367  	// For the same reason, disable this check if some memory ops are unused.
   368  	for _, b := range f.Blocks {
   369  		for _, v := range b.Values {
   370  			if (v.Op == OpCopy || v.Uses == 0) && v.Type.IsMemory() {
   371  				return
   372  			}
   373  		}
   374  		if b != f.Entry && len(b.Preds) == 0 {
   375  			return
   376  		}
   377  	}
   378  
   379  	// Compute live memory at the end of each block.
   380  	lastmem := make([]*Value, f.NumBlocks())
   381  	ss := newSparseSet(f.NumValues())
   382  	for _, b := range f.Blocks {
   383  		// Mark overwritten memory values. Those are args of other
   384  		// ops that generate memory values.
   385  		ss.clear()
   386  		for _, v := range b.Values {
   387  			if v.Op == OpPhi || !v.Type.IsMemory() {
   388  				continue
   389  			}
   390  			if m := v.MemoryArg(); m != nil {
   391  				ss.add(m.ID)
   392  			}
   393  		}
   394  		// There should be at most one remaining unoverwritten memory value.
   395  		for _, v := range b.Values {
   396  			if !v.Type.IsMemory() {
   397  				continue
   398  			}
   399  			if ss.contains(v.ID) {
   400  				continue
   401  			}
   402  			if lastmem[b.ID] != nil {
   403  				f.Fatalf("two live memory values in %s: %s and %s", b, lastmem[b.ID], v)
   404  			}
   405  			lastmem[b.ID] = v
   406  		}
   407  		// If there is no remaining memory value, that means there was no memory update.
   408  		// Take any memory arg.
   409  		if lastmem[b.ID] == nil {
   410  			for _, v := range b.Values {
   411  				if v.Op == OpPhi {
   412  					continue
   413  				}
   414  				m := v.MemoryArg()
   415  				if m == nil {
   416  					continue
   417  				}
   418  				if lastmem[b.ID] != nil && lastmem[b.ID] != m {
   419  					f.Fatalf("two live memory values in %s: %s and %s", b, lastmem[b.ID], m)
   420  				}
   421  				lastmem[b.ID] = m
   422  			}
   423  		}
   424  	}
   425  	// Propagate last live memory through storeless blocks.
   426  	for {
   427  		changed := false
   428  		for _, b := range f.Blocks {
   429  			if lastmem[b.ID] != nil {
   430  				continue
   431  			}
   432  			for _, e := range b.Preds {
   433  				p := e.b
   434  				if lastmem[p.ID] != nil {
   435  					lastmem[b.ID] = lastmem[p.ID]
   436  					changed = true
   437  					break
   438  				}
   439  			}
   440  		}
   441  		if !changed {
   442  			break
   443  		}
   444  	}
   445  	// Check merge points.
   446  	for _, b := range f.Blocks {
   447  		for _, v := range b.Values {
   448  			if v.Op == OpPhi && v.Type.IsMemory() {
   449  				for i, a := range v.Args {
   450  					if a != lastmem[b.Preds[i].b.ID] {
   451  						f.Fatalf("inconsistent memory phi %s %d %s %s", v.LongString(), i, a, lastmem[b.Preds[i].b.ID])
   452  					}
   453  				}
   454  			}
   455  		}
   456  	}
   457  
   458  	// Check that only one memory is live at any point.
   459  	if f.scheduled {
   460  		for _, b := range f.Blocks {
   461  			var mem *Value // the current live memory in the block
   462  			for _, v := range b.Values {
   463  				if v.Op == OpPhi {
   464  					if v.Type.IsMemory() {
   465  						mem = v
   466  					}
   467  					continue
   468  				}
   469  				if mem == nil && len(b.Preds) > 0 {
   470  					// If no mem phi, take mem of any predecessor.
   471  					mem = lastmem[b.Preds[0].b.ID]
   472  				}
   473  				for _, a := range v.Args {
   474  					if a.Type.IsMemory() && a != mem {
   475  						f.Fatalf("two live mems @ %s: %s and %s", v, mem, a)
   476  					}
   477  				}
   478  				if v.Type.IsMemory() {
   479  					mem = v
   480  				}
   481  			}
   482  		}
   483  	}
   484  
   485  	// Check that after scheduling, phis are always first in the block.
   486  	if f.scheduled {
   487  		for _, b := range f.Blocks {
   488  			seenNonPhi := false
   489  			for _, v := range b.Values {
   490  				switch v.Op {
   491  				case OpPhi:
   492  					if seenNonPhi {
   493  						f.Fatalf("phi after non-phi @ %s: %s", b, v)
   494  					}
   495  				default:
   496  					seenNonPhi = true
   497  				}
   498  			}
   499  		}
   500  	}
   501  }
   502  
   503  // domCheck reports whether x dominates y (including x==y).
   504  func domCheck(f *Func, sdom SparseTree, x, y *Block) bool {
   505  	if !sdom.isAncestorEq(f.Entry, y) {
   506  		// unreachable - ignore
   507  		return true
   508  	}
   509  	return sdom.isAncestorEq(x, y)
   510  }
   511  
   512  // isExactFloat32 reports whether x can be exactly represented as a float32.
   513  func isExactFloat32(x float64) bool {
   514  	// Check the mantissa is in range.
   515  	if bits.TrailingZeros64(math.Float64bits(x)) < 52-23 {
   516  		return false
   517  	}
   518  	// Check the exponent is in range. The mantissa check above is sufficient for NaN values.
   519  	return math.IsNaN(x) || x == float64(float32(x))
   520  }
   521  

View as plain text