Source file src/pkg/cmd/compile/internal/ssa/nilcheck.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		"cmd/internal/objabi"
     9		"cmd/internal/src"
    10	)
    11	
    12	// nilcheckelim eliminates unnecessary nil checks.
    13	// runs on machine-independent code.
    14	func nilcheckelim(f *Func) {
    15		// A nil check is redundant if the same nil check was successful in a
    16		// dominating block. The efficacy of this pass depends heavily on the
    17		// efficacy of the cse pass.
    18		sdom := f.sdom()
    19	
    20		// TODO: Eliminate more nil checks.
    21		// We can recursively remove any chain of fixed offset calculations,
    22		// i.e. struct fields and array elements, even with non-constant
    23		// indices: x is non-nil iff x.a.b[i].c is.
    24	
    25		type walkState int
    26		const (
    27			Work     walkState = iota // process nil checks and traverse to dominees
    28			ClearPtr                  // forget the fact that ptr is nil
    29		)
    30	
    31		type bp struct {
    32			block *Block // block, or nil in ClearPtr state
    33			ptr   *Value // if non-nil, ptr that is to be cleared in ClearPtr state
    34			op    walkState
    35		}
    36	
    37		work := make([]bp, 0, 256)
    38		work = append(work, bp{block: f.Entry})
    39	
    40		// map from value ID to bool indicating if value is known to be non-nil
    41		// in the current dominator path being walked. This slice is updated by
    42		// walkStates to maintain the known non-nil values.
    43		nonNilValues := make([]bool, f.NumValues())
    44	
    45		// make an initial pass identifying any non-nil values
    46		for _, b := range f.Blocks {
    47			for _, v := range b.Values {
    48				// a value resulting from taking the address of a
    49				// value, or a value constructed from an offset of a
    50				// non-nil ptr (OpAddPtr) implies it is non-nil
    51				// We also assume unsafe pointer arithmetic generates non-nil pointers. See #27180.
    52				// We assume that SlicePtr is non-nil because we do a bounds check
    53				// before the slice access (and all cap>0 slices have a non-nil ptr). See #30366.
    54				if v.Op == OpAddr || v.Op == OpLocalAddr || v.Op == OpAddPtr || v.Op == OpOffPtr || v.Op == OpAdd32 || v.Op == OpAdd64 || v.Op == OpSub32 || v.Op == OpSub64 || v.Op == OpSlicePtr {
    55					nonNilValues[v.ID] = true
    56				}
    57			}
    58		}
    59	
    60		for changed := true; changed; {
    61			changed = false
    62			for _, b := range f.Blocks {
    63				for _, v := range b.Values {
    64					// phis whose arguments are all non-nil
    65					// are non-nil
    66					if v.Op == OpPhi {
    67						argsNonNil := true
    68						for _, a := range v.Args {
    69							if !nonNilValues[a.ID] {
    70								argsNonNil = false
    71								break
    72							}
    73						}
    74						if argsNonNil {
    75							if !nonNilValues[v.ID] {
    76								changed = true
    77							}
    78							nonNilValues[v.ID] = true
    79						}
    80					}
    81				}
    82			}
    83		}
    84	
    85		// allocate auxiliary date structures for computing store order
    86		sset := f.newSparseSet(f.NumValues())
    87		defer f.retSparseSet(sset)
    88		storeNumber := make([]int32, f.NumValues())
    89	
    90		// perform a depth first walk of the dominee tree
    91		for len(work) > 0 {
    92			node := work[len(work)-1]
    93			work = work[:len(work)-1]
    94	
    95			switch node.op {
    96			case Work:
    97				b := node.block
    98	
    99				// First, see if we're dominated by an explicit nil check.
   100				if len(b.Preds) == 1 {
   101					p := b.Preds[0].b
   102					if p.Kind == BlockIf && p.Control.Op == OpIsNonNil && p.Succs[0].b == b {
   103						ptr := p.Control.Args[0]
   104						if !nonNilValues[ptr.ID] {
   105							nonNilValues[ptr.ID] = true
   106							work = append(work, bp{op: ClearPtr, ptr: ptr})
   107						}
   108					}
   109				}
   110	
   111				// Next, order values in the current block w.r.t. stores.
   112				b.Values = storeOrder(b.Values, sset, storeNumber)
   113	
   114				pendingLines := f.cachedLineStarts // Holds statement boundaries that need to be moved to a new value/block
   115				pendingLines.clear()
   116	
   117				// Next, process values in the block.
   118				i := 0
   119				for _, v := range b.Values {
   120					b.Values[i] = v
   121					i++
   122					switch v.Op {
   123					case OpIsNonNil:
   124						ptr := v.Args[0]
   125						if nonNilValues[ptr.ID] {
   126							if v.Pos.IsStmt() == src.PosIsStmt { // Boolean true is a terrible statement boundary.
   127								pendingLines.add(v.Pos)
   128								v.Pos = v.Pos.WithNotStmt()
   129							}
   130							// This is a redundant explicit nil check.
   131							v.reset(OpConstBool)
   132							v.AuxInt = 1 // true
   133						}
   134					case OpNilCheck:
   135						ptr := v.Args[0]
   136						if nonNilValues[ptr.ID] {
   137							// This is a redundant implicit nil check.
   138							// Logging in the style of the former compiler -- and omit line 1,
   139							// which is usually in generated code.
   140							if f.fe.Debug_checknil() && v.Pos.Line() > 1 {
   141								f.Warnl(v.Pos, "removed nil check")
   142							}
   143							if v.Pos.IsStmt() == src.PosIsStmt { // About to lose a statement boundary
   144								pendingLines.add(v.Pos)
   145							}
   146							v.reset(OpUnknown)
   147							f.freeValue(v)
   148							i--
   149							continue
   150						}
   151						// Record the fact that we know ptr is non nil, and remember to
   152						// undo that information when this dominator subtree is done.
   153						nonNilValues[ptr.ID] = true
   154						work = append(work, bp{op: ClearPtr, ptr: ptr})
   155						fallthrough // a non-eliminated nil check might be a good place for a statement boundary.
   156					default:
   157						if pendingLines.contains(v.Pos) && v.Pos.IsStmt() != src.PosNotStmt {
   158							v.Pos = v.Pos.WithIsStmt()
   159							pendingLines.remove(v.Pos)
   160						}
   161					}
   162				}
   163				if pendingLines.contains(b.Pos) {
   164					b.Pos = b.Pos.WithIsStmt()
   165					pendingLines.remove(b.Pos)
   166				}
   167				for j := i; j < len(b.Values); j++ {
   168					b.Values[j] = nil
   169				}
   170				b.Values = b.Values[:i]
   171	
   172				// Add all dominated blocks to the work list.
   173				for w := sdom[node.block.ID].child; w != nil; w = sdom[w.ID].sibling {
   174					work = append(work, bp{op: Work, block: w})
   175				}
   176	
   177			case ClearPtr:
   178				nonNilValues[node.ptr.ID] = false
   179				continue
   180			}
   181		}
   182	}
   183	
   184	// All platforms are guaranteed to fault if we load/store to anything smaller than this address.
   185	//
   186	// This should agree with minLegalPointer in the runtime.
   187	const minZeroPage = 4096
   188	
   189	// faultOnLoad is true if a load to an address below minZeroPage will trigger a SIGSEGV.
   190	var faultOnLoad = objabi.GOOS != "aix"
   191	
   192	// nilcheckelim2 eliminates unnecessary nil checks.
   193	// Runs after lowering and scheduling.
   194	func nilcheckelim2(f *Func) {
   195		unnecessary := f.newSparseSet(f.NumValues())
   196		defer f.retSparseSet(unnecessary)
   197	
   198		pendingLines := f.cachedLineStarts // Holds statement boundaries that need to be moved to a new value/block
   199	
   200		for _, b := range f.Blocks {
   201			// Walk the block backwards. Find instructions that will fault if their
   202			// input pointer is nil. Remove nil checks on those pointers, as the
   203			// faulting instruction effectively does the nil check for free.
   204			unnecessary.clear()
   205			pendingLines.clear()
   206			// Optimization: keep track of removed nilcheck with smallest index
   207			firstToRemove := len(b.Values)
   208			for i := len(b.Values) - 1; i >= 0; i-- {
   209				v := b.Values[i]
   210				if opcodeTable[v.Op].nilCheck && unnecessary.contains(v.Args[0].ID) {
   211					if f.fe.Debug_checknil() && v.Pos.Line() > 1 {
   212						f.Warnl(v.Pos, "removed nil check")
   213					}
   214					if v.Pos.IsStmt() == src.PosIsStmt {
   215						pendingLines.add(v.Pos)
   216					}
   217					v.reset(OpUnknown)
   218					firstToRemove = i
   219					continue
   220				}
   221				if v.Type.IsMemory() || v.Type.IsTuple() && v.Type.FieldType(1).IsMemory() {
   222					if v.Op == OpVarKill || v.Op == OpVarLive || (v.Op == OpVarDef && !v.Aux.(GCNode).Typ().HasHeapPointer()) {
   223						// These ops don't really change memory.
   224						continue
   225						// Note: OpVarDef requires that the defined variable not have pointers.
   226						// We need to make sure that there's no possible faulting
   227						// instruction between a VarDef and that variable being
   228						// fully initialized. If there was, then anything scanning
   229						// the stack during the handling of that fault will see
   230						// a live but uninitialized pointer variable on the stack.
   231						//
   232						// If we have:
   233						//
   234						//   NilCheck p
   235						//   VarDef x
   236						//   x = *p
   237						//
   238						// We can't rewrite that to
   239						//
   240						//   VarDef x
   241						//   NilCheck p
   242						//   x = *p
   243						//
   244						// Particularly, even though *p faults on p==nil, we still
   245						// have to do the explicit nil check before the VarDef.
   246						// See issue #32288.
   247					}
   248					// This op changes memory.  Any faulting instruction after v that
   249					// we've recorded in the unnecessary map is now obsolete.
   250					unnecessary.clear()
   251				}
   252	
   253				// Find any pointers that this op is guaranteed to fault on if nil.
   254				var ptrstore [2]*Value
   255				ptrs := ptrstore[:0]
   256				if opcodeTable[v.Op].faultOnNilArg0 && (faultOnLoad || v.Type.IsMemory()) {
   257					// On AIX, only writing will fault.
   258					ptrs = append(ptrs, v.Args[0])
   259				}
   260				if opcodeTable[v.Op].faultOnNilArg1 && (faultOnLoad || (v.Type.IsMemory() && v.Op != OpPPC64LoweredMove)) {
   261					// On AIX, only writing will fault.
   262					// LoweredMove is a special case because it's considered as a "mem" as it stores on arg0 but arg1 is accessed as a load and should be checked.
   263					ptrs = append(ptrs, v.Args[1])
   264				}
   265	
   266				for _, ptr := range ptrs {
   267					// Check to make sure the offset is small.
   268					switch opcodeTable[v.Op].auxType {
   269					case auxSymOff:
   270						if v.Aux != nil || v.AuxInt < 0 || v.AuxInt >= minZeroPage {
   271							continue
   272						}
   273					case auxSymValAndOff:
   274						off := ValAndOff(v.AuxInt).Off()
   275						if v.Aux != nil || off < 0 || off >= minZeroPage {
   276							continue
   277						}
   278					case auxInt32:
   279						// Mips uses this auxType for atomic add constant. It does not affect the effective address.
   280					case auxInt64:
   281						// ARM uses this auxType for duffcopy/duffzero/alignment info.
   282						// It does not affect the effective address.
   283					case auxNone:
   284						// offset is zero.
   285					default:
   286						v.Fatalf("can't handle aux %s (type %d) yet\n", v.auxString(), int(opcodeTable[v.Op].auxType))
   287					}
   288					// This instruction is guaranteed to fault if ptr is nil.
   289					// Any previous nil check op is unnecessary.
   290					unnecessary.add(ptr.ID)
   291				}
   292			}
   293			// Remove values we've clobbered with OpUnknown.
   294			i := firstToRemove
   295			for j := i; j < len(b.Values); j++ {
   296				v := b.Values[j]
   297				if v.Op != OpUnknown {
   298					if v.Pos.IsStmt() != src.PosNotStmt && pendingLines.contains(v.Pos) {
   299						v.Pos = v.Pos.WithIsStmt()
   300						pendingLines.remove(v.Pos)
   301					}
   302					b.Values[i] = v
   303					i++
   304				}
   305			}
   306	
   307			if pendingLines.contains(b.Pos) {
   308				b.Pos = b.Pos.WithIsStmt()
   309			}
   310	
   311			for j := i; j < len(b.Values); j++ {
   312				b.Values[j] = nil
   313			}
   314			b.Values = b.Values[:i]
   315	
   316			// TODO: if b.Kind == BlockPlain, start the analysis in the subsequent block to find
   317			// more unnecessary nil checks.  Would fix test/nilptr3.go:159.
   318		}
   319	}
   320	

View as plain text