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