src/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 // nilcheckelim eliminates unnecessary nil checks.
   8 // runs on machine-independent code.
   9 func nilcheckelim(f *Func) {
  10         // A nil check is redundant if the same nil check was successful in a
  11         // dominating block. The efficacy of this pass depends heavily on the
  12         // efficacy of the cse pass.
  13         sdom := f.sdom()
  14
  15         // TODO: Eliminate more nil checks.
  16         // We can recursively remove any chain of fixed offset calculations,
  17         // i.e. struct fields and array elements, even with non-constant
  18         // indices: x is non-nil iff x.a.b[i].c is.
  19
  20         type walkState int
  21         const (
  22                 Work     walkState = iota // process nil checks and traverse to dominees
  23                 ClearPtr                  // forget the fact that ptr is nil
  24         )
  25
  26         type bp struct {
  27                 block *Block // block, or nil in ClearPtr state
  28                 ptr   *Value // if non-nil, ptr that is to be cleared in ClearPtr state
  29                 op    walkState
  30         }
  31
  32         work := make([]bp, 0, 256)
  33         work = append(work, bp{block: f.Entry})
  34
  35         // map from value ID to bool indicating if value is known to be non-nil
  36         // in the current dominator path being walked. This slice is updated by
  37         // walkStates to maintain the known non-nil values.
  38         nonNilValues := make([]bool, f.NumValues())
  39
  40         // make an initial pass identifying any non-nil values
  41         for _, b := range f.Blocks {
  42                 // a value resulting from taking the address of a
  43                 // value, or a value constructed from an offset of a
  44                 // non-nil ptr (OpAddPtr) implies it is non-nil
  45                 for _, v := range b.Values {
  46                         if v.Op == OpAddr || v.Op == OpAddPtr {
  47                                 nonNilValues[v.ID] = true
  48                         } else if v.Op == OpPhi {
  49                                 // phis whose arguments are all non-nil
  50                                 // are non-nil
  51                                 argsNonNil := true
  52                                 for _, a := range v.Args {
  53                                         if !nonNilValues[a.ID] {
  54                                                 argsNonNil = false
  55                                         }
  56                                 }
  57                                 if argsNonNil {
  58                                         nonNilValues[v.ID] = true
  59                                 }
  60                         }
  61                 }
  62         }
  63
  64         // perform a depth first walk of the dominee tree
  65         for len(work) > 0 {
  66                 node := work[len(work)-1]
  67                 work = work[:len(work)-1]
  68
  69                 switch node.op {
  70                 case Work:
  71                         b := node.block
  72
  73                         // First, see if we're dominated by an explicit nil check.
  74                         if len(b.Preds) == 1 {
  75                                 p := b.Preds[0].b
  76                                 if p.Kind == BlockIf && p.Control.Op == OpIsNonNil && p.Succs[0].b == b {
  77                                         ptr := p.Control.Args[0]
  78                                         if !nonNilValues[ptr.ID] {
  79                                                 nonNilValues[ptr.ID] = true
  80                                                 work = append(work, bp{op: ClearPtr, ptr: ptr})
  81                                         }
  82                                 }
  83                         }
  84
  85                         // Next, process values in the block.
  86                         i := 0
  87                         for _, v := range b.Values {
  88                                 b.Values[i] = v
  89                                 i++
  90                                 switch v.Op {
  91                                 case OpIsNonNil:
  92                                         ptr := v.Args[0]
  93                                         if nonNilValues[ptr.ID] {
  94                                                 // This is a redundant explicit nil check.
  95                                                 v.reset(OpConstBool)
  96                                                 v.AuxInt = 1 // true
  97                                         }
  98                                 case OpNilCheck:
  99                                         ptr := v.Args[0]
 100                                         if nonNilValues[ptr.ID] {
 101                                                 // This is a redundant implicit nil check.
 102                                                 // Logging in the style of the former compiler -- and omit line 1,
 103                                                 // which is usually in generated code.
 104                                                 if f.Config.Debug_checknil() && v.Pos.Line() > 1 {
 105                                                         f.Config.Warnl(v.Pos, "removed nil check")
 106                                                 }
 107                                                 v.reset(OpUnknown)
 108                                                 i--
 109                                                 continue
 110                                         }
 111                                         // Record the fact that we know ptr is non nil, and remember to
 112                                         // undo that information when this dominator subtree is done.
 113                                         nonNilValues[ptr.ID] = true
 114                                         work = append(work, bp{op: ClearPtr, ptr: ptr})
 115                                 }
 116                         }
 117                         for j := i; j < len(b.Values); j++ {
 118                                 b.Values[j] = nil
 119                         }
 120                         b.Values = b.Values[:i]
 121
 122                         // Add all dominated blocks to the work list.
 123                         for w := sdom[node.block.ID].child; w != nil; w = sdom[w.ID].sibling {
 124                                 work = append(work, bp{op: Work, block: w})
 125                         }
 126
 127                 case ClearPtr:
 128                         nonNilValues[node.ptr.ID] = false
 129                         continue
 130                 }
 131         }
 132 }
 133
 134 // All platforms are guaranteed to fault if we load/store to anything smaller than this address.
 135 const minZeroPage = 4096
 136
 137 // nilcheckelim2 eliminates unnecessary nil checks.
 138 // Runs after lowering and scheduling.
 139 func nilcheckelim2(f *Func) {
 140         unnecessary := f.newSparseSet(f.NumValues())
 141         defer f.retSparseSet(unnecessary)
 142         for _, b := range f.Blocks {
 143                 // Walk the block backwards. Find instructions that will fault if their
 144                 // input pointer is nil. Remove nil checks on those pointers, as the
 145                 // faulting instruction effectively does the nil check for free.
 146                 unnecessary.clear()
 147                 for i := len(b.Values) - 1; i >= 0; i-- {
 148                         v := b.Values[i]
 149                         if opcodeTable[v.Op].nilCheck && unnecessary.contains(v.Args[0].ID) {
 150                                 if f.Config.Debug_checknil() && v.Pos.Line() > 1 {
 151                                         f.Config.Warnl(v.Pos, "removed nil check")
 152                                 }
 153                                 v.reset(OpUnknown)
 154                                 continue
 155                         }
 156                         if v.Type.IsMemory() || v.Type.IsTuple() && v.Type.FieldType(1).IsMemory() {
 157                                 if v.Op == OpVarDef || v.Op == OpVarKill || v.Op == OpVarLive {
 158                                         // These ops don't really change memory.
 159                                         continue
 160                                 }
 161                                 // This op changes memory.  Any faulting instruction after v that
 162                                 // we've recorded in the unnecessary map is now obsolete.
 163                                 unnecessary.clear()
 164                         }
 165
 166                         // Find any pointers that this op is guaranteed to fault on if nil.
 167                         var ptrstore [2]*Value
 168                         ptrs := ptrstore[:0]
 169                         if opcodeTable[v.Op].faultOnNilArg0 {
 170                                 ptrs = append(ptrs, v.Args[0])
 171                         }
 172                         if opcodeTable[v.Op].faultOnNilArg1 {
 173                                 ptrs = append(ptrs, v.Args[1])
 174                         }
 175                         for _, ptr := range ptrs {
 176                                 // Check to make sure the offset is small.
 177                                 switch opcodeTable[v.Op].auxType {
 178                                 case auxSymOff:
 179                                         if v.Aux != nil || v.AuxInt < 0 || v.AuxInt >= minZeroPage {
 180                                                 continue
 181                                         }
 182                                 case auxSymValAndOff:
 183                                         off := ValAndOff(v.AuxInt).Off()
 184                                         if v.Aux != nil || off < 0 || off >= minZeroPage {
 185                                                 continue
 186                                         }
 187                                 case auxInt32:
 188                                         // Mips uses this auxType for atomic add constant. It does not affect the effective address.
 189                                 case auxInt64:
 190                                         // ARM uses this auxType for duffcopy/duffzero/alignment info.
 191                                         // It does not affect the effective address.
 192                                 case auxNone:
 193                                         // offset is zero.
 194                                 default:
 195                                         v.Fatalf("can't handle aux %s (type %d) yet\n", v.auxString(), int(opcodeTable[v.Op].auxType))
 196                                 }
 197                                 // This instruction is guaranteed to fault if ptr is nil.
 198                                 // Any previous nil check op is unnecessary.
 199                                 unnecessary.add(ptr.ID)
 200                         }
 201                 }
 202                 // Remove values we've clobbered with OpUnknown.
 203                 i := 0
 204                 for _, v := range b.Values {
 205                         if v.Op != OpUnknown {
 206                                 b.Values[i] = v
 207                                 i++
 208                         }
 209                 }
 210                 for j := i; j < len(b.Values); j++ {
 211                         b.Values[j] = nil
 212                 }
 213                 b.Values = b.Values[:i]
 214
 215                 // TODO: if b.Kind == BlockPlain, start the analysis in the subsequent block to find
 216                 // more unnecessary nil checks.  Would fix test/nilptr3_ssa.go:157.
 217         }
 218 }