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