cmd/compile: fix min/max builtin code generation

Our large-function phi placement algorithm is incompatible with phi
opcodes already existing in the SSA representation. Instead, use simple
variable assignments and have the phi placement algorithm place the phis
we need for min/max.

Turns out the small-function phi placement algorithm doesn't have this
sensitivity, so this bug only occurs in large functions (>500 basic blocks).

Maybe we should document/check that no phis are present when we start
phi placement (regardless of size).  Leaving for a potential separate CL.

We should probably also fix the placement algorithm to handle existing
phis correctly.  But this CL is probably a lot smaller/safer than
messing with phi placement.

Fixes #60982

Change-Id: I59ba7f506c72b22bc1485099a335d96315ebef67
Reviewed-on: https://go-review.googlesource.com/c/go/+/505756
Reviewed-by: Keith Randall <khr@google.com>
Run-TryBot: Keith Randall <khr@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>

2 files changed, 2030 insertions, 3 deletions

diff --git a/src/cmd/compile/internal/ssagen/ssa.go b/src/cmd/compile/internal/ssagen/ssa.go
index 88fee51d33..4aedf9cd35 100644
--- a/src/cmd/compile/internal/ssagen/ssa.go
+++ b/src/cmd/compile/internal/ssagen/ssa.go
@@ -949,6 +949,7 @@ var (
 	typVar       = ssaMarker("typ")
 	okVar        = ssaMarker("ok")
 	deferBitsVar = ssaMarker("deferBits")
+	ternaryVar   = ssaMarker("ternary")
 )
 
 // startBlock sets the current block we're generating code in to b.
@@ -3622,6 +3623,7 @@ func (s *state) minMax(n *ir.CallExpr) *ssa.Value {
 func (s *state) ternary(cond, x, y *ssa.Value) *ssa.Value {
 	bThen := s.f.NewBlock(ssa.BlockPlain)
 	bElse := s.f.NewBlock(ssa.BlockPlain)
+	bEnd := s.f.NewBlock(ssa.BlockPlain)
 
 	b := s.endBlock()
 	b.Kind = ssa.BlockIf
@@ -3629,11 +3631,18 @@ func (s *state) ternary(cond, x, y *ssa.Value) *ssa.Value {
 	b.AddEdgeTo(bThen)
 	b.AddEdgeTo(bElse)
 
+	s.startBlock(bThen)
+	s.vars[ternaryVar] = x
+	s.endBlock().AddEdgeTo(bEnd)
+
 	s.startBlock(bElse)
-	s.endBlock().AddEdgeTo(bThen)
+	s.vars[ternaryVar] = y
+	s.endBlock().AddEdgeTo(bEnd)
 
-	s.startBlock(bThen)
-	return s.newValue2(ssa.OpPhi, x.Type, x, y)
+	s.startBlock(bEnd)
+	r := s.variable(ternaryVar, x.Type)
+	delete(s.vars, ternaryVar)
+	return r
 }
 
 // condBranch evaluates the boolean expression cond and branches to yes
diff --git a/test/fixedbugs/issue60982.go b/test/fixedbugs/issue60982.go
new file mode 100644
index 0000000000..11c3af214f
--- /dev/null
+++ b/test/fixedbugs/issue60982.go
@@ -0,0 +1,2018 @@
+// compile
+
+// Copyright 2023 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 main
+
+func f(x int) int {
+	if x >= 1000 {
+		return max(x, 2000)
+	}
+	// generate 1000 basic blocks to put this function
+	// well into the "large function" phi generation algorithm.
+	switch x {
+	case 0:
+		return 0
+	case 1:
+		return 1
+	case 2:
+		return 2
+	case 3:
+		return 3
+	case 4:
+		return 4
+	case 5:
+		return 5
+	case 6:
+		return 6
+	case 7:
+		return 7
+	case 8:
+		return 8
+	case 9:
+		return 9
+	case 10:
+		return 10
+	case 11:
+		return 11
+	case 12:
+		return 12
+	case 13:
+		return 13
+	case 14:
+		return 14
+	case 15:
+		return 15
+	case 16:
+		return 16
+	case 17:
+		return 17
+	case 18:
+		return 18
+	case 19:
+		return 19
+	case 20:
+		return 20
+	case 21:
+		return 21
+	case 22:
+		return 22
+	case 23:
+		return 23
+	case 24:
+		return 24
+	case 25:
+		return 25
+	case 26:
+		return 26
+	case 27:
+		return 27
+	case 28:
+		return 28
+	case 29:
+		return 29
+	case 30:
+		return 30
+	case 31:
+		return 31
+	case 32:
+		return 32
+	case 33:
+		return 33
+	case 34:
+		return 34
+	case 35:
+		return 35
+	case 36:
+		return 36
+	case 37:
+		return 37
+	case 38:
+		return 38
+	case 39:
+		return 39
+	case 40:
+		return 40
+	case 41:
+		return 41
+	case 42:
+		return 42
+	case 43:
+		return 43
+	case 44:
+		return 44
+	case 45:
+		return 45
+	case 46:
+		return 46
+	case 47:
+		return 47
+	case 48:
+		return 48
+	case 49:
+		return 49
+	case 50:
+		return 50
+	case 51:
+		return 51
+	case 52:
+		return 52
+	case 53:
+		return 53
+	case 54:
+		return 54
+	case 55:
+		return 55
+	case 56:
+		return 56
+	case 57:
+		return 57
+	case 58:
+		return 58
+	case 59:
+		return 59
+	case 60:
+		return 60
+	case 61:
+		return 61
+	case 62:
+		return 62
+	case 63:
+		return 63
+	case 64:
+		return 64
+	case 65:
+		return 65
+	case 66:
+		return 66
+	case 67:
+		return 67
+	case 68:
+		return 68
+	case 69:
+		return 69
+	case 70:
+		return 70
+	case 71:
+		return 71
+	case 72:
+		return 72
+	case 73:
+		return 73
+	case 74:
+		return 74
+	case 75:
+		return 75
+	case 76:
+		return 76
+	case 77:
+		return 77
+	case 78:
+		return 78
+	case 79:
+		return 79
+	case 80:
+		return 80
+	case 81:
+		return 81
+	case 82:
+		return 82
+	case 83:
+		return 83
+	case 84:
+		return 84
+	case 85:
+		return 85
+	case 86:
+		return 86
+	case 87:
+		return 87
+	case 88:
+		return 88
+	case 89:
+		return 89
+	case 90:
+		return 90
+	case 91:
+		return 91
+	case 92:
+		return 92
+	case 93:
+		return 93
+	case 94:
+		return 94
+	case 95:
+		return 95
+	case 96:
+		return 96
+	case 97:
+		return 97
+	case 98:
+		return 98
+	case 99:
+		return 99
+	case 100:
+		return 100
+	case 101:
+		return 101
+	case 102:
+		return 102
+	case 103:
+		return 103
+	case 104:
+		return 104
+	case 105:
+		return 105
+	case 106:
+		return 106
+	case 107:
+		return 107
+	case 108:
+		return 108
+	case 109:
+		return 109
+	case 110:
+		return 110
+	case 111:
+		return 111
+	case 112:
+		return 112
+	case 113:
+		return 113
+	case 114:
+		return 114
+	case 115:
+		return 115
+	case 116:
+		return 116
+	case 117:
+		return 117
+	case 118:
+		return 118
+	case 119:
+		return 119
+	case 120:
+		return 120
+	case 121:
+		return 121
+	case 122:
+		return 122
+	case 123:
+		return 123
+	case 124:
+		return 124
+	case 125:
+		return 125
+	case 126:
+		return 126
+	case 127:
+		return 127
+	case 128:
+		return 128
+	case 129:
+		return 129
+	case 130:
+		return 130
+	case 131:
+		return 131
+	case 132:
+		return 132
+	case 133:
+		return 133
+	case 134:
+		return 134
+	case 135:
+		return 135
+	case 136:
+		return 136
+	case 137:
+		return 137
+	case 138:
+		return 138
+	case 139:
+		return 139
+	case 140:
+		return 140
+	case 141:
+		return 141
+	case 142:
+		return 142
+	case 143:
+		return 143
+	case 144:
+		return 144
+	case 145:
+		return 145
+	case 146:
+		return 146
+	case 147:
+		return 147
+	case 148:
+		return 148
+	case 149:
+		return 149
+	case 150:
+		return 150
+	case 151:
+		return 151
+	case 152:
+		return 152
+	case 153:
+		return 153
+	case 154:
+		return 154
+	case 155:
+		return 155
+	case 156:
+		return 156
+	case 157:
+		return 157
+	case 158:
+		return 158
+	case 159:
+		return 159
+	case 160:
+		return 160
+	case 161:
+		return 161
+	case 162:
+		return 162
+	case 163:
+		return 163
+	case 164:
+		return 164
+	case 165:
+		return 165
+	case 166:
+		return 166
+	case 167:
+		return 167
+	case 168:
+		return 168
+	case 169:
+		return 169
+	case 170:
+		return 170
+	case 171:
+		return 171
+	case 172:
+		return 172
+	case 173:
+		return 173
+	case 174:
+		return 174
+	case 175:
+		return 175
+	case 176:
+		return 176
+	case 177:
+		return 177
+	case 178:
+		return 178
+	case 179:
+		return 179
+	case 180:
+		return 180
+	case 181:
+		return 181
+	case 182:
+		return 182
+	case 183:
+		return 183
+	case 184:
+		return 184
+	case 185:
+		return 185
+	case 186:
+		return 186
+	case 187:
+		return 187
+	case 188:
+		return 188
+	case 189:
+		return 189
+	case 190:
+		return 190
+	case 191:
+		return 191
+	case 192:
+		return 192
+	case 193:
+		return 193
+	case 194:
+		return 194
+	case 195:
+		return 195
+	case 196:
+		return 196
+	case 197:
+		return 197
+	case 198:
+		return 198
+	case 199:
+		return 199
+	case 200:
+		return 200
+	case 201:
+		return 201
+	case 202:
+		return 202
+	case 203:
+		return 203
+	case 204:
+		return 204
+	case 205:
+		return 205
+	case 206:
+		return 206
+	case 207:
+		return 207
+	case 208:
+		return 208
+	case 209:
+		return 209
+	case 210:
+		return 210
+	case 211:
+		return 211
+	case 212:
+		return 212
+	case 213:
+		return 213
+	case 214:
+		return 214
+	case 215:
+		return 215
+	case 216:
+		return 216
+	case 217:
+		return 217
+	case 218:
+		return 218
+	case 219:
+		return 219
+	case 220:
+		return 220
+	case 221:
+		return 221
+	case 222:
+		return 222
+	case 223:
+		return 223
+	case 224:
+		return 224
+	case 225:
+		return 225
+	case 226:
+		return 226
+	case 227:
+		return 227
+	case 228:
+		return 228
+	case 229:
+		return 229
+	case 230:
+		return 230
+	case 231:
+		return 231
+	case 232:
+		return 232
+	case 233:
+		return 233
+	case 234:
+		return 234
+	case 235:
+		return 235
+	case 236:
+		return 236
+	case 237:
+		return 237
+	case 238:
+		return 238
+	case 239:
+		return 239
+	case 240:
+		return 240
+	case 241:
+		return 241
+	case 242:
+		return 242
+	case 243:
+		return 243
+	case 244:
+		return 244
+	case 245:
+		return 245
+	case 246:
+		return 246
+	case 247:
+		return 247
+	case 248:
+		return 248
+	case 249:
+		return 249
+	case 250:
+		return 250
+	case 251:
+		return 251
+	case 252:
+		return 252
+	case 253:
+		return 253
+	case 254:
+		return 254
+	case 255:
+		return 255
+	case 256:
+		return 256
+	case 257:
+		return 257
+	case 258:
+		return 258
+	case 259:
+		return 259
+	case 260:
+		return 260
+	case 261:
+		return 261
+	case 262:
+		return 262
+	case 263:
+		return 263
+	case 264:
+		return 264
+	case 265:
+		return 265
+	case 266:
+		return 266
+	case 267:
+		return 267
+	case 268:
+		return 268
+	case 269:
+		return 269
+	case 270:
+		return 270
+	case 271:
+		return 271
+	case 272:
+		return 272
+	case 273:
+		return 273
+	case 274:
+		return 274
+	case 275:
+		return 275
+	case 276:
+		return 276
+	case 277:
+		return 277
+	case 278:
+		return 278
+	case 279:
+		return 279
+	case 280:
+		return 280
+	case 281:
+		return 281
+	case 282:
+		return 282
+	case 283:
+		return 283
+	case 284:
+		return 284
+	case 285:
+		return 285
+	case 286:
+		return 286
+	case 287:
+		return 287
+	case 288:
+		return 288
+	case 289:
+		return 289
+	case 290:
+		return 290
+	case 291:
+		return 291
+	case 292:
+		return 292
+	case 293:
+		return 293
+	case 294:
+		return 294
+	case 295:
+		return 295
+	case 296:
+		return 296
+	case 297:
+		return 297
+	case 298:
+		return 298
+	case 299:
+		return 299
+	case 300:
+		return 300
+	case 301:
+		return 301
+	case 302:
+		return 302
+	case 303:
+		return 303
+	case 304:
+		return 304
+	case 305:
+		return 305
+	case 306:
+		return 306
+	case 307:
+		return 307
+	case 308:
+		return 308
+	case 309:
+		return 309
+	case 310:
+		return 310
+	case 311:
+		return 311
+	case 312:
+		return 312
+	case 313:
+		return 313
+	case 314:
+		return 314
+	case 315:
+		return 315
+	case 316:
+		return 316
+	case 317:
+		return 317
+	case 318:
+		return 318
+	case 319:
+		return 319
+	case 320:
+		return 320
+	case 321:
+		return 321
+	case 322:
+		return 322
+	case 323:
+		return 323
+	case 324:
+		return 324
+	case 325:
+		return 325
+	case 326:
+		return 326
+	case 327:
+		return 327
+	case 328:
+		return 328
+	case 329:
+		return 329
+	case 330:
+		return 330
+	case 331:
+		return 331
+	case 332:
+		return 332
+	case 333:
+		return 333
+	case 334:
+		return 334
+	case 335:
+		return 335
+	case 336:
+		return 336
+	case 337:
+		return 337
+	case 338:
+		return 338
+	case 339:
+		return 339
+	case 340:
+		return 340
+	case 341:
+		return 341
+	case 342:
+		return 342
+	case 343:
+		return 343
+	case 344:
+		return 344
+	case 345:
+		return 345
+	case 346:
+		return 346
+	case 347:
+		return 347
+	case 348:
+		return 348
+	case 349:
+		return 349
+	case 350:
+		return 350
+	case 351:
+		return 351
+	case 352:
+		return 352
+	case 353:
+		return 353
+	case 354:
+		return 354
+	case 355:
+		return 355
+	case 356:
+		return 356
+	case 357:
+		return 357
+	case 358:
+		return 358
+	case 359:
+		return 359
+	case 360:
+		return 360
+	case 361:
+		return 361
+	case 362:
+		return 362
+	case 363:
+		return 363
+	case 364:
+		return 364
+	case 365:
+		return 365
+	case 366:
+		return 366
+	case 367:
+		return 367
+	case 368:
+		return 368
+	case 369:
+		return 369
+	case 370:
+		return 370
+	case 371:
+		return 371
+	case 372:
+		return 372
+	case 373:
+		return 373
+	case 374:
+		return 374
+	case 375:
+		return 375
+	case 376:
+		return 376
+	case 377:
+		return 377
+	case 378:
+		return 378
+	case 379:
+		return 379
+	case 380:
+		return 380
+	case 381:
+		return 381
+	case 382:
+		return 382
+	case 383:
+		return 383
+	case 384:
+		return 384
+	case 385:
+		return 385
+	case 386:
+		return 386
+	case 387:
+		return 387
+	case 388:
+		return 388
+	case 389:
+		return 389
+	case 390:
+		return 390
+	case 391:
+		return 391
+	case 392:
+		return 392
+	case 393:
+		return 393
+	case 394:
+		return 394
+	case 395:
+		return 395
+	case 396:
+		return 396
+	case 397:
+		return 397
+	case 398:
+		return 398
+	case 399:
+		return 399
+	case 400:
+		return 400
+	case 401:
+		return 401
+	case 402:
+		return 402
+	case 403:
+		return 403
+	case 404:
+		return 404
+	case 405:
+		return 405
+	case 406:
+		return 406
+	case 407:
+		return 407
+	case 408:
+		return 408
+	case 409:
+		return 409
+	case 410:
+		return 410
+	case 411:
+		return 411
+	case 412:
+		return 412
+	case 413:
+		return 413
+	case 414:
+		return 414
+	case 415:
+		return 415
+	case 416:
+		return 416
+	case 417:
+		return 417
+	case 418:
+		return 418
+	case 419:
+		return 419
+	case 420:
+		return 420
+	case 421:
+		return 421
+	case 422:
+		return 422
+	case 423:
+		return 423
+	case 424:
+		return 424
+	case 425:
+		return 425
+	case 426:
+		return 426
+	case 427:
+		return 427
+	case 428:
+		return 428
+	case 429:
+		return 429
+	case 430:
+		return 430
+	case 431:
+		return 431
+	case 432:
+		return 432
+	case 433:
+		return 433
+	case 434:
+		return 434
+	case 435:
+		return 435
+	case 436:
+		return 436
+	case 437:
+		return 437
+	case 438:
+		return 438
+	case 439:
+		return 439
+	case 440:
+		return 440
+	case 441:
+		return 441
+	case 442:
+		return 442
+	case 443:
+		return 443
+	case 444:
+		return 444
+	case 445:
+		return 445
+	case 446:
+		return 446
+	case 447:
+		return 447
+	case 448:
+		return 448
+	case 449:
+		return 449
+	case 450:
+		return 450
+	case 451:
+		return 451
+	case 452:
+		return 452
+	case 453:
+		return 453
+	case 454:
+		return 454
+	case 455:
+		return 455
+	case 456:
+		return 456
+	case 457:
+		return 457
+	case 458:
+		return 458
+	case 459:
+		return 459
+	case 460:
+		return 460
+	case 461:
+		return 461
+	case 462:
+		return 462
+	case 463:
+		return 463
+	case 464:
+		return 464
+	case 465:
+		return 465
+	case 466:
+		return 466
+	case 467:
+		return 467
+	case 468:
+		return 468
+	case 469:
+		return 469
+	case 470:
+		return 470
+	case 471:
+		return 471
+	case 472:
+		return 472
+	case 473:
+		return 473
+	case 474:
+		return 474
+	case 475:
+		return 475
+	case 476:
+		return 476
+	case 477:
+		return 477
+	case 478:
+		return 478
+	case 479:
+		return 479
+	case 480:
+		return 480
+	case 481:
+		return 481
+	case 482:
+		return 482
+	case 483:
+		return 483
+	case 484:
+		return 484
+	case 485:
+		return 485
+	case 486:
+		return 486
+	case 487:
+		return 487
+	case 488:
+		return 488
+	case 489:
+		return 489
+	case 490:
+		return 490
+	case 491:
+		return 491
+	case 492:
+		return 492
+	case 493:
+		return 493
+	case 494:
+		return 494
+	case 495:
+		return 495
+	case 496:
+		return 496
+	case 497:
+		return 497
+	case 498:
+		return 498
+	case 499:
+		return 499
+	case 500:
+		return 500
+	case 501:
+		return 501
+	case 502:
+		return 502
+	case 503:
+		return 503
+	case 504:
+		return 504
+	case 505:
+		return 505
+	case 506:
+		return 506
+	case 507:
+		return 507
+	case 508:
+		return 508
+	case 509:
+		return 509
+	case 510:
+		return 510
+	case 511:
+		return 511
+	case 512:
+		return 512
+	case 513:
+		return 513
+	case 514:
+		return 514
+	case 515:
+		return 515
+	case 516:
+		return 516
+	case 517:
+		return 517
+	case 518:
+		return 518
+	case 519:
+		return 519
+	case 520:
+		return 520
+	case 521:
+		return 521
+	case 522:
+		return 522
+	case 523:
+		return 523
+	case 524:
+		return 524
+	case 525:
+		return 525
+	case 526:
+		return 526
+	case 527:
+		return 527
+	case 528:
+		return 528
+	case 529:
+		return 529
+	case 530:
+		return 530
+	case 531:
+		return 531
+	case 532:
+		return 532
+	case 533:
+		return 533
+	case 534:
+		return 534
+	case 535:
+		return 535
+	case 536:
+		return 536
+	case 537:
+		return 537
+	case 538:
+		return 538
+	case 539:
+		return 539
+	case 540:
+		return 540
+	case 541:
+		return 541
+	case 542:
+		return 542
+	case 543:
+		return 543
+	case 544:
+		return 544
+	case 545:
+		return 545
+	case 546:
+		return 546
+	case 547:
+		return 547
+	case 548:
+		return 548
+	case 549:
+		return 549
+	case 550:
+		return 550
+	case 551:
+		return 551
+	case 552:
+		return 552
+	case 553:
+		return 553
+	case 554:
+		return 554
+	case 555:
+		return 555
+	case 556:
+		return 556
+	case 557:
+		return 557
+	case 558:
+		return 558
+	case 559:
+		return 559
+	case 560:
+		return 560
+	case 561:
+		return 561
+	case 562:
+		return 562
+	case 563:
+		return 563
+	case 564:
+		return 564
+	case 565:
+		return 565
+	case 566:
+		return 566
+	case 567:
+		return 567
+	case 568:
+		return 568
+	case 569:
+		return 569
+	case 570:
+		return 570
+	case 571:
+		return 571
+	case 572:
+		return 572
+	case 573:
+		return 573
+	case 574:
+		return 574
+	case 575:
+		return 575
+	case 576:
+		return 576
+	case 577:
+		return 577
+	case 578:
+		return 578
+	case 579:
+		return 579
+	case 580:
+		return 580
+	case 581:
+		return 581
+	case 582:
+		return 582
+	case 583:
+		return 583
+	case 584:
+		return 584
+	case 585:
+		return 585
+	case 586:
+		return 586
+	case 587:
+		return 587
+	case 588:
+		return 588
+	case 589:
+		return 589
+	case 590:
+		return 590
+	case 591:
+		return 591
+	case 592:
+		return 592
+	case 593:
+		return 593
+	case 594:
+		return 594
+	case 595:
+		return 595
+	case 596:
+		return 596
+	case 597:
+		return 597
+	case 598:
+		return 598
+	case 599:
+		return 599
+	case 600:
+		return 600
+	case 601:
+		return 601
+	case 602:
+		return 602
+	case 603:
+		return 603
+	case 604:
+		return 604
+	case 605:
+		return 605
+	case 606:
+		return 606
+	case 607:
+		return 607
+	case 608:
+		return 608
+	case 609:
+		return 609
+	case 610:
+		return 610
+	case 611:
+		return 611
+	case 612:
+		return 612
+	case 613:
+		return 613
+	case 614:
+		return 614
+	case 615:
+		return 615
+	case 616:
+		return 616
+	case 617:
+		return 617
+	case 618:
+		return 618
+	case 619:
+		return 619
+	case 620:
+		return 620
+	case 621:
+		return 621
+	case 622:
+		return 622
+	case 623:
+		return 623
+	case 624:
+		return 624
+	case 625:
+		return 625
+	case 626:
+		return 626
+	case 627:
+		return 627
+	case 628:
+		return 628
+	case 629:
+		return 629
+	case 630:
+		return 630
+	case 631:
+		return 631
+	case 632:
+		return 632
+	case 633:
+		return 633
+	case 634:
+		return 634
+	case 635:
+		return 635
+	case 636:
+		return 636
+	case 637:
+		return 637
+	case 638:
+		return 638
+	case 639:
+		return 639
+	case 640:
+		return 640
+	case 641:
+		return 641
+	case 642:
+		return 642
+	case 643:
+		return 643
+	case 644:
+		return 644
+	case 645:
+		return 645
+	case 646:
+		return 646
+	case 647:
+		return 647
+	case 648:
+		return 648
+	case 649:
+		return 649
+	case 650:
+		return 650
+	case 651:
+		return 651
+	case 652:
+		return 652
+	case 653:
+		return 653
+	case 654:
+		return 654
+	case 655:
+		return 655
+	case 656:
+		return 656
+	case 657:
+		return 657
+	case 658:
+		return 658
+	case 659:
+		return 659
+	case 660:
+		return 660
+	case 661:
+		return 661
+	case 662:
+		return 662
+	case 663:
+		return 663
+	case 664:
+		return 664
+	case 665:
+		return 665
+	case 666:
+		return 666
+	case 667:
+		return 667
+	case 668:
+		return 668
+	case 669:
+		return 669
+	case 670:
+		return 670
+	case 671:
+		return 671
+	case 672:
+		return 672
+	case 673:
+		return 673
+	case 674:
+		return 674
+	case 675:
+		return 675
+	case 676:
+		return 676
+	case 677:
+		return 677
+	case 678:
+		return 678
+	case 679:
+		return 679
+	case 680:
+		return 680
+	case 681:
+		return 681
+	case 682:
+		return 682
+	case 683:
+		return 683
+	case 684:
+		return 684
+	case 685:
+		return 685
+	case 686:
+		return 686
+	case 687:
+		return 687
+	case 688:
+		return 688
+	case 689:
+		return 689
+	case 690:
+		return 690
+	case 691:
+		return 691
+	case 692:
+		return 692
+	case 693:
+		return 693
+	case 694:
+		return 694
+	case 695:
+		return 695
+	case 696:
+		return 696
+	case 697:
+		return 697
+	case 698:
+		return 698
+	case 699:
+		return 699
+	case 700:
+		return 700
+	case 701:
+		return 701
+	case 702:
+		return 702
+	case 703:
+		return 703
+	case 704:
+		return 704
+	case 705:
+		return 705
+	case 706:
+		return 706
+	case 707:
+		return 707
+	case 708:
+		return 708
+	case 709:
+		return 709
+	case 710:
+		return 710
+	case 711:
+		return 711
+	case 712:
+		return 712
+	case 713:
+		return 713
+	case 714:
+		return 714
+	case 715:
+		return 715
+	case 716:
+		return 716
+	case 717:
+		return 717
+	case 718:
+		return 718
+	case 719:
+		return 719
+	case 720:
+		return 720
+	case 721:
+		return 721
+	case 722:
+		return 722
+	case 723:
+		return 723
+	case 724:
+		return 724
+	case 725:
+		return 725
+	case 726:
+		return 726
+	case 727:
+		return 727
+	case 728:
+		return 728
+	case 729:
+		return 729
+	case 730:
+		return 730
+	case 731:
+		return 731
+	case 732:
+		return 732
+	case 733:
+		return 733
+	case 734:
+		return 734
+	case 735:
+		return 735
+	case 736:
+		return 736
+	case 737:
+		return 737
+	case 738:
+		return 738
+	case 739:
+		return 739
+	case 740:
+		return 740
+	case 741:
+		return 741
+	case 742:
+		return 742
+	case 743:
+		return 743
+	case 744:
+		return 744
+	case 745:
+		return 745
+	case 746:
+		return 746
+	case 747:
+		return 747
+	case 748:
+		return 748
+	case 749:
+		return 749
+	case 750:
+		return 750
+	case 751:
+		return 751
+	case 752:
+		return 752
+	case 753:
+		return 753
+	case 754:
+		return 754
+	case 755:
+		return 755
+	case 756:
+		return 756
+	case 757:
+		return 757
+	case 758:
+		return 758
+	case 759:
+		return 759
+	case 760:
+		return 760
+	case 761:
+		return 761
+	case 762:
+		return 762
+	case 763:
+		return 763
+	case 764:
+		return 764
+	case 765:
+		return 765
+	case 766:
+		return 766
+	case 767:
+		return 767
+	case 768:
+		return 768
+	case 769:
+		return 769
+	case 770:
+		return 770
+	case 771:
+		return 771
+	case 772:
+		return 772
+	case 773:
+		return 773
+	case 774:
+		return 774
+	case 775:
+		return 775
+	case 776:
+		return 776
+	case 777:
+		return 777
+	case 778:
+		return 778
+	case 779:
+		return 779
+	case 780:
+		return 780
+	case 781:
+		return 781
+	case 782:
+		return 782
+	case 783:
+		return 783
+	case 784:
+		return 784
+	case 785:
+		return 785
+	case 786:
+		return 786
+	case 787:
+		return 787
+	case 788:
+		return 788
+	case 789:
+		return 789
+	case 790:
+		return 790
+	case 791:
+		return 791
+	case 792:
+		return 792
+	case 793:
+		return 793
+	case 794:
+		return 794
+	case 795:
+		return 795
+	case 796:
+		return 796
+	case 797:
+		return 797
+	case 798:
+		return 798
+	case 799:
+		return 799
+	case 800:
+		return 800
+	case 801:
+		return 801
+	case 802:
+		return 802
+	case 803:
+		return 803
+	case 804:
+		return 804
+	case 805:
+		return 805
+	case 806:
+		return 806
+	case 807:
+		return 807
+	case 808:
+		return 808
+	case 809:
+		return 809
+	case 810:
+		return 810
+	case 811:
+		return 811
+	case 812:
+		return 812
+	case 813:
+		return 813
+	case 814:
+		return 814
+	case 815:
+		return 815
+	case 816:
+		return 816
+	case 817:
+		return 817
+	case 818:
+		return 818
+	case 819:
+		return 819
+	case 820:
+		return 820
+	case 821:
+		return 821
+	case 822:
+		return 822
+	case 823:
+		return 823
+	case 824:
+		return 824
+	case 825:
+		return 825
+	case 826:
+		return 826
+	case 827:
+		return 827
+	case 828:
+		return 828
+	case 829:
+		return 829
+	case 830:
+		return 830
+	case 831:
+		return 831
+	case 832:
+		return 832
+	case 833:
+		return 833
+	case 834:
+		return 834
+	case 835:
+		return 835
+	case 836:
+		return 836
+	case 837:
+		return 837
+	case 838:
+		return 838
+	case 839:
+		return 839
+	case 840:
+		return 840
+	case 841:
+		return 841
+	case 842:
+		return 842
+	case 843:
+		return 843
+	case 844:
+		return 844
+	case 845:
+		return 845
+	case 846:
+		return 846
+	case 847:
+		return 847
+	case 848:
+		return 848
+	case 849:
+		return 849
+	case 850:
+		return 850
+	case 851:
+		return 851
+	case 852:
+		return 852
+	case 853:
+		return 853
+	case 854:
+		return 854
+	case 855:
+		return 855
+	case 856:
+		return 856
+	case 857:
+		return 857
+	case 858:
+		return 858
+	case 859:
+		return 859
+	case 860:
+		return 860
+	case 861:
+		return 861
+	case 862:
+		return 862
+	case 863:
+		return 863
+	case 864:
+		return 864
+	case 865:
+		return 865
+	case 866:
+		return 866
+	case 867:
+		return 867
+	case 868:
+		return 868
+	case 869:
+		return 869
+	case 870:
+		return 870
+	case 871:
+		return 871
+	case 872:
+		return 872
+	case 873:
+		return 873
+	case 874:
+		return 874
+	case 875:
+		return 875
+	case 876:
+		return 876
+	case 877:
+		return 877
+	case 878:
+		return 878
+	case 879:
+		return 879
+	case 880:
+		return 880
+	case 881:
+		return 881
+	case 882:
+		return 882
+	case 883:
+		return 883
+	case 884:
+		return 884
+	case 885:
+		return 885
+	case 886:
+		return 886
+	case 887:
+		return 887
+	case 888:
+		return 888
+	case 889:
+		return 889
+	case 890:
+		return 890
+	case 891:
+		return 891
+	case 892:
+		return 892
+	case 893:
+		return 893
+	case 894:
+		return 894
+	case 895:
+		return 895
+	case 896:
+		return 896
+	case 897:
+		return 897
+	case 898:
+		return 898
+	case 899:
+		return 899
+	case 900:
+		return 900
+	case 901:
+		return 901
+	case 902:
+		return 902
+	case 903:
+		return 903
+	case 904:
+		return 904
+	case 905:
+		return 905
+	case 906:
+		return 906
+	case 907:
+		return 907
+	case 908:
+		return 908
+	case 909:
+		return 909
+	case 910:
+		return 910
+	case 911:
+		return 911
+	case 912:
+		return 912
+	case 913:
+		return 913
+	case 914:
+		return 914
+	case 915:
+		return 915
+	case 916:
+		return 916
+	case 917:
+		return 917
+	case 918:
+		return 918
+	case 919:
+		return 919
+	case 920:
+		return 920
+	case 921:
+		return 921
+	case 922:
+		return 922
+	case 923:
+		return 923
+	case 924:
+		return 924
+	case 925:
+		return 925
+	case 926:
+		return 926
+	case 927:
+		return 927
+	case 928:
+		return 928
+	case 929:
+		return 929
+	case 930:
+		return 930
+	case 931:
+		return 931
+	case 932:
+		return 932
+	case 933:
+		return 933
+	case 934:
+		return 934
+	case 935:
+		return 935
+	case 936:
+		return 936
+	case 937:
+		return 937
+	case 938:
+		return 938
+	case 939:
+		return 939
+	case 940:
+		return 940
+	case 941:
+		return 941
+	case 942:
+		return 942
+	case 943:
+		return 943
+	case 944:
+		return 944
+	case 945:
+		return 945
+	case 946:
+		return 946
+	case 947:
+		return 947
+	case 948:
+		return 948
+	case 949:
+		return 949
+	case 950:
+		return 950
+	case 951:
+		return 951
+	case 952:
+		return 952
+	case 953:
+		return 953
+	case 954:
+		return 954
+	case 955:
+		return 955
+	case 956:
+		return 956
+	case 957:
+		return 957
+	case 958:
+		return 958
+	case 959:
+		return 959
+	case 960:
+		return 960
+	case 961:
+		return 961
+	case 962:
+		return 962
+	case 963:
+		return 963
+	case 964:
+		return 964
+	case 965:
+		return 965
+	case 966:
+		return 966
+	case 967:
+		return 967
+	case 968:
+		return 968
+	case 969:
+		return 969
+	case 970:
+		return 970
+	case 971:
+		return 971
+	case 972:
+		return 972
+	case 973:
+		return 973
+	case 974:
+		return 974
+	case 975:
+		return 975
+	case 976:
+		return 976
+	case 977:
+		return 977
+	case 978:
+		return 978
+	case 979:
+		return 979
+	case 980:
+		return 980
+	case 981:
+		return 981
+	case 982:
+		return 982
+	case 983:
+		return 983
+	case 984:
+		return 984
+	case 985:
+		return 985
+	case 986:
+		return 986
+	case 987:
+		return 987
+	case 988:
+		return 988
+	case 989:
+		return 989
+	case 990:
+		return 990
+	case 991:
+		return 991
+	case 992:
+		return 992
+	case 993:
+		return 993
+	case 994:
+		return 994
+	case 995:
+		return 995
+	case 996:
+		return 996
+	case 997:
+		return 997
+	case 998:
+		return 998
+	case 999:
+		return 999
+	}
+	return 0
+}