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

     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