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