1 package ssa 2 3 import ( 4 "cmd/compile/internal/types" 5 "strconv" 6 "testing" 7 ) 8 9 func BenchmarkNilCheckDeep1(b *testing.B) { benchmarkNilCheckDeep(b, 1) } 10 func BenchmarkNilCheckDeep10(b *testing.B) { benchmarkNilCheckDeep(b, 10) } 11 func BenchmarkNilCheckDeep100(b *testing.B) { benchmarkNilCheckDeep(b, 100) } 12 func BenchmarkNilCheckDeep1000(b *testing.B) { benchmarkNilCheckDeep(b, 1000) } 13 func BenchmarkNilCheckDeep10000(b *testing.B) { benchmarkNilCheckDeep(b, 10000) } 14 15 // benchmarkNilCheckDeep is a stress test of nilcheckelim. 16 // It uses the worst possible input: A linear string of 17 // nil checks, none of which can be eliminated. 18 // Run with multiple depths to observe big-O behavior. 19 func benchmarkNilCheckDeep(b *testing.B, depth int) { 20 c := testConfig(b) 21 ptrType := c.config.Types.BytePtr 22 23 var blocs []bloc 24 blocs = append(blocs, 25 Bloc("entry", 26 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 27 Valu("sb", OpSB, types.TypeInvalid, 0, nil), 28 Goto(blockn(0)), 29 ), 30 ) 31 for i := 0; i < depth; i++ { 32 blocs = append(blocs, 33 Bloc(blockn(i), 34 Valu(ptrn(i), OpAddr, ptrType, 0, nil, "sb"), 35 Valu(booln(i), OpIsNonNil, c.config.Types.Bool, 0, nil, ptrn(i)), 36 If(booln(i), blockn(i+1), "exit"), 37 ), 38 ) 39 } 40 blocs = append(blocs, 41 Bloc(blockn(depth), Goto("exit")), 42 Bloc("exit", Exit("mem")), 43 ) 44 45 fun := c.Fun("entry", blocs...) 46 47 CheckFunc(fun.f) 48 b.SetBytes(int64(depth)) // helps for eyeballing linearity 49 b.ResetTimer() 50 b.ReportAllocs() 51 52 for i := 0; i < b.N; i++ { 53 nilcheckelim(fun.f) 54 } 55 } 56 57 func blockn(n int) string { return "b" + strconv.Itoa(n) } 58 func ptrn(n int) string { return "p" + strconv.Itoa(n) } 59 func booln(n int) string { return "c" + strconv.Itoa(n) } 60 61 func isNilCheck(b *Block) bool { 62 return b.Kind == BlockIf && b.Control.Op == OpIsNonNil 63 } 64 65 // TestNilcheckSimple verifies that a second repeated nilcheck is removed. 66 func TestNilcheckSimple(t *testing.T) { 67 c := testConfig(t) 68 ptrType := c.config.Types.BytePtr 69 fun := c.Fun("entry", 70 Bloc("entry", 71 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 72 Valu("sb", OpSB, types.TypeInvalid, 0, nil), 73 Goto("checkPtr")), 74 Bloc("checkPtr", 75 Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"), 76 Valu("bool1", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"), 77 If("bool1", "secondCheck", "exit")), 78 Bloc("secondCheck", 79 Valu("bool2", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"), 80 If("bool2", "extra", "exit")), 81 Bloc("extra", 82 Goto("exit")), 83 Bloc("exit", 84 Exit("mem"))) 85 86 CheckFunc(fun.f) 87 nilcheckelim(fun.f) 88 89 // clean up the removed nil check 90 fuse(fun.f) 91 deadcode(fun.f) 92 93 CheckFunc(fun.f) 94 for _, b := range fun.f.Blocks { 95 if b == fun.blocks["secondCheck"] && isNilCheck(b) { 96 t.Errorf("secondCheck was not eliminated") 97 } 98 } 99 } 100 101 // TestNilcheckDomOrder ensures that the nil check elimination isn't dependent 102 // on the order of the dominees. 103 func TestNilcheckDomOrder(t *testing.T) { 104 c := testConfig(t) 105 ptrType := c.config.Types.BytePtr 106 fun := c.Fun("entry", 107 Bloc("entry", 108 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 109 Valu("sb", OpSB, types.TypeInvalid, 0, nil), 110 Goto("checkPtr")), 111 Bloc("checkPtr", 112 Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"), 113 Valu("bool1", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"), 114 If("bool1", "secondCheck", "exit")), 115 Bloc("exit", 116 Exit("mem")), 117 Bloc("secondCheck", 118 Valu("bool2", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"), 119 If("bool2", "extra", "exit")), 120 Bloc("extra", 121 Goto("exit"))) 122 123 CheckFunc(fun.f) 124 nilcheckelim(fun.f) 125 126 // clean up the removed nil check 127 fuse(fun.f) 128 deadcode(fun.f) 129 130 CheckFunc(fun.f) 131 for _, b := range fun.f.Blocks { 132 if b == fun.blocks["secondCheck"] && isNilCheck(b) { 133 t.Errorf("secondCheck was not eliminated") 134 } 135 } 136 } 137 138 // TestNilcheckAddr verifies that nilchecks of OpAddr constructed values are removed. 139 func TestNilcheckAddr(t *testing.T) { 140 c := testConfig(t) 141 ptrType := c.config.Types.BytePtr 142 fun := c.Fun("entry", 143 Bloc("entry", 144 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 145 Valu("sb", OpSB, types.TypeInvalid, 0, nil), 146 Goto("checkPtr")), 147 Bloc("checkPtr", 148 Valu("ptr1", OpAddr, ptrType, 0, nil, "sb"), 149 Valu("bool1", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"), 150 If("bool1", "extra", "exit")), 151 Bloc("extra", 152 Goto("exit")), 153 Bloc("exit", 154 Exit("mem"))) 155 156 CheckFunc(fun.f) 157 nilcheckelim(fun.f) 158 159 // clean up the removed nil check 160 fuse(fun.f) 161 deadcode(fun.f) 162 163 CheckFunc(fun.f) 164 for _, b := range fun.f.Blocks { 165 if b == fun.blocks["checkPtr"] && isNilCheck(b) { 166 t.Errorf("checkPtr was not eliminated") 167 } 168 } 169 } 170 171 // TestNilcheckAddPtr verifies that nilchecks of OpAddPtr constructed values are removed. 172 func TestNilcheckAddPtr(t *testing.T) { 173 c := testConfig(t) 174 ptrType := c.config.Types.BytePtr 175 fun := c.Fun("entry", 176 Bloc("entry", 177 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 178 Valu("sb", OpSB, types.TypeInvalid, 0, nil), 179 Goto("checkPtr")), 180 Bloc("checkPtr", 181 Valu("off", OpConst64, c.config.Types.Int64, 20, nil), 182 Valu("ptr1", OpAddPtr, ptrType, 0, nil, "sb", "off"), 183 Valu("bool1", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"), 184 If("bool1", "extra", "exit")), 185 Bloc("extra", 186 Goto("exit")), 187 Bloc("exit", 188 Exit("mem"))) 189 190 CheckFunc(fun.f) 191 nilcheckelim(fun.f) 192 193 // clean up the removed nil check 194 fuse(fun.f) 195 deadcode(fun.f) 196 197 CheckFunc(fun.f) 198 for _, b := range fun.f.Blocks { 199 if b == fun.blocks["checkPtr"] && isNilCheck(b) { 200 t.Errorf("checkPtr was not eliminated") 201 } 202 } 203 } 204 205 // TestNilcheckPhi tests that nil checks of phis, for which all values are known to be 206 // non-nil are removed. 207 func TestNilcheckPhi(t *testing.T) { 208 c := testConfig(t) 209 ptrType := c.config.Types.BytePtr 210 fun := c.Fun("entry", 211 Bloc("entry", 212 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 213 Valu("sb", OpSB, types.TypeInvalid, 0, nil), 214 Valu("sp", OpSP, types.TypeInvalid, 0, nil), 215 Valu("baddr", OpAddr, c.config.Types.Bool, 0, "b", "sp"), 216 Valu("bool1", OpLoad, c.config.Types.Bool, 0, nil, "baddr", "mem"), 217 If("bool1", "b1", "b2")), 218 Bloc("b1", 219 Valu("ptr1", OpAddr, ptrType, 0, nil, "sb"), 220 Goto("checkPtr")), 221 Bloc("b2", 222 Valu("ptr2", OpAddr, ptrType, 0, nil, "sb"), 223 Goto("checkPtr")), 224 // both ptr1 and ptr2 are guaranteed non-nil here 225 Bloc("checkPtr", 226 Valu("phi", OpPhi, ptrType, 0, nil, "ptr1", "ptr2"), 227 Valu("bool2", OpIsNonNil, c.config.Types.Bool, 0, nil, "phi"), 228 If("bool2", "extra", "exit")), 229 Bloc("extra", 230 Goto("exit")), 231 Bloc("exit", 232 Exit("mem"))) 233 234 CheckFunc(fun.f) 235 nilcheckelim(fun.f) 236 237 // clean up the removed nil check 238 fuse(fun.f) 239 deadcode(fun.f) 240 241 CheckFunc(fun.f) 242 for _, b := range fun.f.Blocks { 243 if b == fun.blocks["checkPtr"] && isNilCheck(b) { 244 t.Errorf("checkPtr was not eliminated") 245 } 246 } 247 } 248 249 // TestNilcheckKeepRemove verifies that duplicate checks of the same pointer 250 // are removed, but checks of different pointers are not. 251 func TestNilcheckKeepRemove(t *testing.T) { 252 c := testConfig(t) 253 ptrType := c.config.Types.BytePtr 254 fun := c.Fun("entry", 255 Bloc("entry", 256 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 257 Valu("sb", OpSB, types.TypeInvalid, 0, nil), 258 Goto("checkPtr")), 259 Bloc("checkPtr", 260 Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"), 261 Valu("bool1", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"), 262 If("bool1", "differentCheck", "exit")), 263 Bloc("differentCheck", 264 Valu("ptr2", OpLoad, ptrType, 0, nil, "sb", "mem"), 265 Valu("bool2", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr2"), 266 If("bool2", "secondCheck", "exit")), 267 Bloc("secondCheck", 268 Valu("bool3", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"), 269 If("bool3", "extra", "exit")), 270 Bloc("extra", 271 Goto("exit")), 272 Bloc("exit", 273 Exit("mem"))) 274 275 CheckFunc(fun.f) 276 nilcheckelim(fun.f) 277 278 // clean up the removed nil check 279 fuse(fun.f) 280 deadcode(fun.f) 281 282 CheckFunc(fun.f) 283 foundDifferentCheck := false 284 for _, b := range fun.f.Blocks { 285 if b == fun.blocks["secondCheck"] && isNilCheck(b) { 286 t.Errorf("secondCheck was not eliminated") 287 } 288 if b == fun.blocks["differentCheck"] && isNilCheck(b) { 289 foundDifferentCheck = true 290 } 291 } 292 if !foundDifferentCheck { 293 t.Errorf("removed differentCheck, but shouldn't have") 294 } 295 } 296 297 // TestNilcheckInFalseBranch tests that nil checks in the false branch of an nilcheck 298 // block are *not* removed. 299 func TestNilcheckInFalseBranch(t *testing.T) { 300 c := testConfig(t) 301 ptrType := c.config.Types.BytePtr 302 fun := c.Fun("entry", 303 Bloc("entry", 304 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 305 Valu("sb", OpSB, types.TypeInvalid, 0, nil), 306 Goto("checkPtr")), 307 Bloc("checkPtr", 308 Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"), 309 Valu("bool1", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"), 310 If("bool1", "extra", "secondCheck")), 311 Bloc("secondCheck", 312 Valu("bool2", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"), 313 If("bool2", "extra", "thirdCheck")), 314 Bloc("thirdCheck", 315 Valu("bool3", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"), 316 If("bool3", "extra", "exit")), 317 Bloc("extra", 318 Goto("exit")), 319 Bloc("exit", 320 Exit("mem"))) 321 322 CheckFunc(fun.f) 323 nilcheckelim(fun.f) 324 325 // clean up the removed nil check 326 fuse(fun.f) 327 deadcode(fun.f) 328 329 CheckFunc(fun.f) 330 foundSecondCheck := false 331 foundThirdCheck := false 332 for _, b := range fun.f.Blocks { 333 if b == fun.blocks["secondCheck"] && isNilCheck(b) { 334 foundSecondCheck = true 335 } 336 if b == fun.blocks["thirdCheck"] && isNilCheck(b) { 337 foundThirdCheck = true 338 } 339 } 340 if !foundSecondCheck { 341 t.Errorf("removed secondCheck, but shouldn't have [false branch]") 342 } 343 if !foundThirdCheck { 344 t.Errorf("removed thirdCheck, but shouldn't have [false branch]") 345 } 346 } 347 348 // TestNilcheckUser verifies that a user nil check that dominates a generated nil check 349 // wil remove the generated nil check. 350 func TestNilcheckUser(t *testing.T) { 351 c := testConfig(t) 352 ptrType := c.config.Types.BytePtr 353 fun := c.Fun("entry", 354 Bloc("entry", 355 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 356 Valu("sb", OpSB, types.TypeInvalid, 0, nil), 357 Goto("checkPtr")), 358 Bloc("checkPtr", 359 Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"), 360 Valu("nilptr", OpConstNil, ptrType, 0, nil), 361 Valu("bool1", OpNeqPtr, c.config.Types.Bool, 0, nil, "ptr1", "nilptr"), 362 If("bool1", "secondCheck", "exit")), 363 Bloc("secondCheck", 364 Valu("bool2", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"), 365 If("bool2", "extra", "exit")), 366 Bloc("extra", 367 Goto("exit")), 368 Bloc("exit", 369 Exit("mem"))) 370 371 CheckFunc(fun.f) 372 // we need the opt here to rewrite the user nilcheck 373 opt(fun.f) 374 nilcheckelim(fun.f) 375 376 // clean up the removed nil check 377 fuse(fun.f) 378 deadcode(fun.f) 379 380 CheckFunc(fun.f) 381 for _, b := range fun.f.Blocks { 382 if b == fun.blocks["secondCheck"] && isNilCheck(b) { 383 t.Errorf("secondCheck was not eliminated") 384 } 385 } 386 } 387 388 // TestNilcheckBug reproduces a bug in nilcheckelim found by compiling math/big 389 func TestNilcheckBug(t *testing.T) { 390 c := testConfig(t) 391 ptrType := c.config.Types.BytePtr 392 fun := c.Fun("entry", 393 Bloc("entry", 394 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 395 Valu("sb", OpSB, types.TypeInvalid, 0, nil), 396 Goto("checkPtr")), 397 Bloc("checkPtr", 398 Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"), 399 Valu("nilptr", OpConstNil, ptrType, 0, nil), 400 Valu("bool1", OpNeqPtr, c.config.Types.Bool, 0, nil, "ptr1", "nilptr"), 401 If("bool1", "secondCheck", "couldBeNil")), 402 Bloc("couldBeNil", 403 Goto("secondCheck")), 404 Bloc("secondCheck", 405 Valu("bool2", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"), 406 If("bool2", "extra", "exit")), 407 Bloc("extra", 408 // prevent fuse from eliminating this block 409 Valu("store", OpStore, types.TypeMem, 0, ptrType, "ptr1", "nilptr", "mem"), 410 Goto("exit")), 411 Bloc("exit", 412 Valu("phi", OpPhi, types.TypeMem, 0, nil, "mem", "store"), 413 Exit("phi"))) 414 415 CheckFunc(fun.f) 416 // we need the opt here to rewrite the user nilcheck 417 opt(fun.f) 418 nilcheckelim(fun.f) 419 420 // clean up the removed nil check 421 fuse(fun.f) 422 deadcode(fun.f) 423 424 CheckFunc(fun.f) 425 foundSecondCheck := false 426 for _, b := range fun.f.Blocks { 427 if b == fun.blocks["secondCheck"] && isNilCheck(b) { 428 foundSecondCheck = true 429 } 430 } 431 if !foundSecondCheck { 432 t.Errorf("secondCheck was eliminated, but shouldn't have") 433 } 434 } 435
