src/cmd/compile/internal/walk/switch.go

   1 // Copyright 2009 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 walk
   6
   7 import (
   8         "go/constant"
   9         "go/token"
  10         "math/bits"
  11         "sort"
  12
  13         "cmd/compile/internal/base"
  14         "cmd/compile/internal/ir"
  15         "cmd/compile/internal/ssagen"
  16         "cmd/compile/internal/typecheck"
  17         "cmd/compile/internal/types"
  18         "cmd/internal/src"
  19 )
  20
  21 // walkSwitch walks a switch statement.
  22 func walkSwitch(sw *ir.SwitchStmt) {
  23         // Guard against double walk, see #25776.
  24         if sw.Walked() {
  25                 return // Was fatal, but eliminating every possible source of double-walking is hard
  26         }
  27         sw.SetWalked(true)
  28
  29         if sw.Tag != nil && sw.Tag.Op() == ir.OTYPESW {
  30                 walkSwitchType(sw)
  31         } else {
  32                 walkSwitchExpr(sw)
  33         }
  34 }
  35
  36 // walkSwitchExpr generates an AST implementing sw.  sw is an
  37 // expression switch.
  38 func walkSwitchExpr(sw *ir.SwitchStmt) {
  39         lno := ir.SetPos(sw)
  40
  41         cond := sw.Tag
  42         sw.Tag = nil
  43
  44         // convert switch {...} to switch true {...}
  45         if cond == nil {
  46                 cond = ir.NewBool(base.Pos, true)
  47                 cond = typecheck.Expr(cond)
  48                 cond = typecheck.DefaultLit(cond, nil)
  49         }
  50
  51         // Given "switch string(byteslice)",
  52         // with all cases being side-effect free,
  53         // use a zero-cost alias of the byte slice.
  54         // Do this before calling walkExpr on cond,
  55         // because walkExpr will lower the string
  56         // conversion into a runtime call.
  57         // See issue 24937 for more discussion.
  58         if cond.Op() == ir.OBYTES2STR && allCaseExprsAreSideEffectFree(sw) {
  59                 cond := cond.(*ir.ConvExpr)
  60                 cond.SetOp(ir.OBYTES2STRTMP)
  61         }
  62
  63         cond = walkExpr(cond, sw.PtrInit())
  64         if cond.Op() != ir.OLITERAL && cond.Op() != ir.ONIL {
  65                 cond = copyExpr(cond, cond.Type(), &sw.Compiled)
  66         }
  67
  68         base.Pos = lno
  69
  70         s := exprSwitch{
  71                 pos:      lno,
  72                 exprname: cond,
  73         }
  74
  75         var defaultGoto ir.Node
  76         var body ir.Nodes
  77         for _, ncase := range sw.Cases {
  78                 label := typecheck.AutoLabel(".s")
  79                 jmp := ir.NewBranchStmt(ncase.Pos(), ir.OGOTO, label)
  80
  81                 // Process case dispatch.
  82                 if len(ncase.List) == 0 {
  83                         if defaultGoto != nil {
  84                                 base.Fatalf("duplicate default case not detected during typechecking")
  85                         }
  86                         defaultGoto = jmp
  87                 }
  88
  89                 for i, n1 := range ncase.List {
  90                         var rtype ir.Node
  91                         if i < len(ncase.RTypes) {
  92                                 rtype = ncase.RTypes[i]
  93                         }
  94                         s.Add(ncase.Pos(), n1, rtype, jmp)
  95                 }
  96
  97                 // Process body.
  98                 body.Append(ir.NewLabelStmt(ncase.Pos(), label))
  99                 body.Append(ncase.Body...)
 100                 if fall, pos := endsInFallthrough(ncase.Body); !fall {
 101                         br := ir.NewBranchStmt(base.Pos, ir.OBREAK, nil)
 102                         br.SetPos(pos)
 103                         body.Append(br)
 104                 }
 105         }
 106         sw.Cases = nil
 107
 108         if defaultGoto == nil {
 109                 br := ir.NewBranchStmt(base.Pos, ir.OBREAK, nil)
 110                 br.SetPos(br.Pos().WithNotStmt())
 111                 defaultGoto = br
 112         }
 113
 114         s.Emit(&sw.Compiled)
 115         sw.Compiled.Append(defaultGoto)
 116         sw.Compiled.Append(body.Take()...)
 117         walkStmtList(sw.Compiled)
 118 }
 119
 120 // An exprSwitch walks an expression switch.
 121 type exprSwitch struct {
 122         pos      src.XPos
 123         exprname ir.Node // value being switched on
 124
 125         done    ir.Nodes
 126         clauses []exprClause
 127 }
 128
 129 type exprClause struct {
 130         pos    src.XPos
 131         lo, hi ir.Node
 132         rtype  ir.Node // *runtime._type for OEQ node
 133         jmp    ir.Node
 134 }
 135
 136 func (s *exprSwitch) Add(pos src.XPos, expr, rtype, jmp ir.Node) {
 137         c := exprClause{pos: pos, lo: expr, hi: expr, rtype: rtype, jmp: jmp}
 138         if types.IsOrdered[s.exprname.Type().Kind()] && expr.Op() == ir.OLITERAL {
 139                 s.clauses = append(s.clauses, c)
 140                 return
 141         }
 142
 143         s.flush()
 144         s.clauses = append(s.clauses, c)
 145         s.flush()
 146 }
 147
 148 func (s *exprSwitch) Emit(out *ir.Nodes) {
 149         s.flush()
 150         out.Append(s.done.Take()...)
 151 }
 152
 153 func (s *exprSwitch) flush() {
 154         cc := s.clauses
 155         s.clauses = nil
 156         if len(cc) == 0 {
 157                 return
 158         }
 159
 160         // Caution: If len(cc) == 1, then cc[0] might not an OLITERAL.
 161         // The code below is structured to implicitly handle this case
 162         // (e.g., sort.Slice doesn't need to invoke the less function
 163         // when there's only a single slice element).
 164
 165         if s.exprname.Type().IsString() && len(cc) >= 2 {
 166                 // Sort strings by length and then by value. It is
 167                 // much cheaper to compare lengths than values, and
 168                 // all we need here is consistency. We respect this
 169                 // sorting below.
 170                 sort.Slice(cc, func(i, j int) bool {
 171                         si := ir.StringVal(cc[i].lo)
 172                         sj := ir.StringVal(cc[j].lo)
 173                         if len(si) != len(sj) {
 174                                 return len(si) < len(sj)
 175                         }
 176                         return si < sj
 177                 })
 178
 179                 // runLen returns the string length associated with a
 180                 // particular run of exprClauses.
 181                 runLen := func(run []exprClause) int64 { return int64(len(ir.StringVal(run[0].lo))) }
 182
 183                 // Collapse runs of consecutive strings with the same length.
 184                 var runs [][]exprClause
 185                 start := 0
 186                 for i := 1; i < len(cc); i++ {
 187                         if runLen(cc[start:]) != runLen(cc[i:]) {
 188                                 runs = append(runs, cc[start:i])
 189                                 start = i
 190                         }
 191                 }
 192                 runs = append(runs, cc[start:])
 193
 194                 // We have strings of more than one length. Generate an
 195                 // outer switch which switches on the length of the string
 196                 // and an inner switch in each case which resolves all the
 197                 // strings of the same length. The code looks something like this:
 198
 199                 // goto outerLabel
 200                 // len5:
 201                 //   ... search among length 5 strings ...
 202                 //   goto endLabel
 203                 // len8:
 204                 //   ... search among length 8 strings ...
 205                 //   goto endLabel
 206                 // ... other lengths ...
 207                 // outerLabel:
 208                 // switch len(s) {
 209                 //   case 5: goto len5
 210                 //   case 8: goto len8
 211                 //   ... other lengths ...
 212                 // }
 213                 // endLabel:
 214
 215                 outerLabel := typecheck.AutoLabel(".s")
 216                 endLabel := typecheck.AutoLabel(".s")
 217
 218                 // Jump around all the individual switches for each length.
 219                 s.done.Append(ir.NewBranchStmt(s.pos, ir.OGOTO, outerLabel))
 220
 221                 var outer exprSwitch
 222                 outer.exprname = ir.NewUnaryExpr(s.pos, ir.OLEN, s.exprname)
 223                 outer.exprname.SetType(types.Types[types.TINT])
 224
 225                 for _, run := range runs {
 226                         // Target label to jump to when we match this length.
 227                         label := typecheck.AutoLabel(".s")
 228
 229                         // Search within this run of same-length strings.
 230                         pos := run[0].pos
 231                         s.done.Append(ir.NewLabelStmt(pos, label))
 232                         stringSearch(s.exprname, run, &s.done)
 233                         s.done.Append(ir.NewBranchStmt(pos, ir.OGOTO, endLabel))
 234
 235                         // Add length case to outer switch.
 236                         cas := ir.NewInt(pos, runLen(run))
 237                         jmp := ir.NewBranchStmt(pos, ir.OGOTO, label)
 238                         outer.Add(pos, cas, nil, jmp)
 239                 }
 240                 s.done.Append(ir.NewLabelStmt(s.pos, outerLabel))
 241                 outer.Emit(&s.done)
 242                 s.done.Append(ir.NewLabelStmt(s.pos, endLabel))
 243                 return
 244         }
 245
 246         sort.Slice(cc, func(i, j int) bool {
 247                 return constant.Compare(cc[i].lo.Val(), token.LSS, cc[j].lo.Val())
 248         })
 249
 250         // Merge consecutive integer cases.
 251         if s.exprname.Type().IsInteger() {
 252                 consecutive := func(last, next constant.Value) bool {
 253                         delta := constant.BinaryOp(next, token.SUB, last)
 254                         return constant.Compare(delta, token.EQL, constant.MakeInt64(1))
 255                 }
 256
 257                 merged := cc[:1]
 258                 for _, c := range cc[1:] {
 259                         last := &merged[len(merged)-1]
 260                         if last.jmp == c.jmp && consecutive(last.hi.Val(), c.lo.Val()) {
 261                                 last.hi = c.lo
 262                         } else {
 263                                 merged = append(merged, c)
 264                         }
 265                 }
 266                 cc = merged
 267         }
 268
 269         s.search(cc, &s.done)
 270 }
 271
 272 func (s *exprSwitch) search(cc []exprClause, out *ir.Nodes) {
 273         if s.tryJumpTable(cc, out) {
 274                 return
 275         }
 276         binarySearch(len(cc), out,
 277                 func(i int) ir.Node {
 278                         return ir.NewBinaryExpr(base.Pos, ir.OLE, s.exprname, cc[i-1].hi)
 279                 },
 280                 func(i int, nif *ir.IfStmt) {
 281                         c := &cc[i]
 282                         nif.Cond = c.test(s.exprname)
 283                         nif.Body = []ir.Node{c.jmp}
 284                 },
 285         )
 286 }
 287
 288 // Try to implement the clauses with a jump table. Returns true if successful.
 289 func (s *exprSwitch) tryJumpTable(cc []exprClause, out *ir.Nodes) bool {
 290         const minCases = 8   // have at least minCases cases in the switch
 291         const minDensity = 4 // use at least 1 out of every minDensity entries
 292
 293         if base.Flag.N != 0 || !ssagen.Arch.LinkArch.CanJumpTable || base.Ctxt.Retpoline {
 294                 return false
 295         }
 296         if len(cc) < minCases {
 297                 return false // not enough cases for it to be worth it
 298         }
 299         if cc[0].lo.Val().Kind() != constant.Int {
 300                 return false // e.g. float
 301         }
 302         if s.exprname.Type().Size() > int64(types.PtrSize) {
 303                 return false // 64-bit switches on 32-bit archs
 304         }
 305         min := cc[0].lo.Val()
 306         max := cc[len(cc)-1].hi.Val()
 307         width := constant.BinaryOp(constant.BinaryOp(max, token.SUB, min), token.ADD, constant.MakeInt64(1))
 308         limit := constant.MakeInt64(int64(len(cc)) * minDensity)
 309         if constant.Compare(width, token.GTR, limit) {
 310                 // We disable jump tables if we use less than a minimum fraction of the entries.
 311                 // i.e. for switch x {case 0: case 1000: case 2000:} we don't want to use a jump table.
 312                 return false
 313         }
 314         jt := ir.NewJumpTableStmt(base.Pos, s.exprname)
 315         for _, c := range cc {
 316                 jmp := c.jmp.(*ir.BranchStmt)
 317                 if jmp.Op() != ir.OGOTO || jmp.Label == nil {
 318                         panic("bad switch case body")
 319                 }
 320                 for i := c.lo.Val(); constant.Compare(i, token.LEQ, c.hi.Val()); i = constant.BinaryOp(i, token.ADD, constant.MakeInt64(1)) {
 321                         jt.Cases = append(jt.Cases, i)
 322                         jt.Targets = append(jt.Targets, jmp.Label)
 323                 }
 324         }
 325         out.Append(jt)
 326         return true
 327 }
 328
 329 func (c *exprClause) test(exprname ir.Node) ir.Node {
 330         // Integer range.
 331         if c.hi != c.lo {
 332                 low := ir.NewBinaryExpr(c.pos, ir.OGE, exprname, c.lo)
 333                 high := ir.NewBinaryExpr(c.pos, ir.OLE, exprname, c.hi)
 334                 return ir.NewLogicalExpr(c.pos, ir.OANDAND, low, high)
 335         }
 336
 337         // Optimize "switch true { ...}" and "switch false { ... }".
 338         if ir.IsConst(exprname, constant.Bool) && !c.lo.Type().IsInterface() {
 339                 if ir.BoolVal(exprname) {
 340                         return c.lo
 341                 } else {
 342                         return ir.NewUnaryExpr(c.pos, ir.ONOT, c.lo)
 343                 }
 344         }
 345
 346         n := ir.NewBinaryExpr(c.pos, ir.OEQ, exprname, c.lo)
 347         n.RType = c.rtype
 348         return n
 349 }
 350
 351 func allCaseExprsAreSideEffectFree(sw *ir.SwitchStmt) bool {
 352         // In theory, we could be more aggressive, allowing any
 353         // side-effect-free expressions in cases, but it's a bit
 354         // tricky because some of that information is unavailable due
 355         // to the introduction of temporaries during order.
 356         // Restricting to constants is simple and probably powerful
 357         // enough.
 358
 359         for _, ncase := range sw.Cases {
 360                 for _, v := range ncase.List {
 361                         if v.Op() != ir.OLITERAL {
 362                                 return false
 363                         }
 364                 }
 365         }
 366         return true
 367 }
 368
 369 // endsInFallthrough reports whether stmts ends with a "fallthrough" statement.
 370 func endsInFallthrough(stmts []ir.Node) (bool, src.XPos) {
 371         if len(stmts) == 0 {
 372                 return false, src.NoXPos
 373         }
 374         i := len(stmts) - 1
 375         return stmts[i].Op() == ir.OFALL, stmts[i].Pos()
 376 }
 377
 378 // walkSwitchType generates an AST that implements sw, where sw is a
 379 // type switch.
 380 func walkSwitchType(sw *ir.SwitchStmt) {
 381         var s typeSwitch
 382         s.facename = sw.Tag.(*ir.TypeSwitchGuard).X
 383         sw.Tag = nil
 384
 385         s.facename = walkExpr(s.facename, sw.PtrInit())
 386         s.facename = copyExpr(s.facename, s.facename.Type(), &sw.Compiled)
 387         s.okname = typecheck.TempAt(base.Pos, ir.CurFunc, types.Types[types.TBOOL])
 388
 389         // Get interface descriptor word.
 390         // For empty interfaces this will be the type.
 391         // For non-empty interfaces this will be the itab.
 392         itab := ir.NewUnaryExpr(base.Pos, ir.OITAB, s.facename)
 393
 394         // For empty interfaces, do:
 395         //     if e._type == nil {
 396         //         do nil case if it exists, otherwise default
 397         //     }
 398         //     h := e._type.hash
 399         // Use a similar strategy for non-empty interfaces.
 400         ifNil := ir.NewIfStmt(base.Pos, nil, nil, nil)
 401         ifNil.Cond = ir.NewBinaryExpr(base.Pos, ir.OEQ, itab, typecheck.NodNil())
 402         base.Pos = base.Pos.WithNotStmt() // disable statement marks after the first check.
 403         ifNil.Cond = typecheck.Expr(ifNil.Cond)
 404         ifNil.Cond = typecheck.DefaultLit(ifNil.Cond, nil)
 405         // ifNil.Nbody assigned at end.
 406         sw.Compiled.Append(ifNil)
 407
 408         // Load hash from type or itab.
 409         dotHash := typeHashFieldOf(base.Pos, itab)
 410         s.hashname = copyExpr(dotHash, dotHash.Type(), &sw.Compiled)
 411
 412         br := ir.NewBranchStmt(base.Pos, ir.OBREAK, nil)
 413         var defaultGoto, nilGoto ir.Node
 414         var body ir.Nodes
 415         for _, ncase := range sw.Cases {
 416                 caseVar := ncase.Var
 417
 418                 // For single-type cases with an interface type,
 419                 // we initialize the case variable as part of the type assertion.
 420                 // In other cases, we initialize it in the body.
 421                 var singleType *types.Type
 422                 if len(ncase.List) == 1 && ncase.List[0].Op() == ir.OTYPE {
 423                         singleType = ncase.List[0].Type()
 424                 }
 425                 caseVarInitialized := false
 426
 427                 label := typecheck.AutoLabel(".s")
 428                 jmp := ir.NewBranchStmt(ncase.Pos(), ir.OGOTO, label)
 429
 430                 if len(ncase.List) == 0 { // default:
 431                         if defaultGoto != nil {
 432                                 base.Fatalf("duplicate default case not detected during typechecking")
 433                         }
 434                         defaultGoto = jmp
 435                 }
 436
 437                 for _, n1 := range ncase.List {
 438                         if ir.IsNil(n1) { // case nil:
 439                                 if nilGoto != nil {
 440                                         base.Fatalf("duplicate nil case not detected during typechecking")
 441                                 }
 442                                 nilGoto = jmp
 443                                 continue
 444                         }
 445
 446                         if singleType != nil && singleType.IsInterface() {
 447                                 s.Add(ncase.Pos(), n1, caseVar, jmp)
 448                                 caseVarInitialized = true
 449                         } else {
 450                                 s.Add(ncase.Pos(), n1, nil, jmp)
 451                         }
 452                 }
 453
 454                 body.Append(ir.NewLabelStmt(ncase.Pos(), label))
 455                 if caseVar != nil && !caseVarInitialized {
 456                         val := s.facename
 457                         if singleType != nil {
 458                                 // We have a single concrete type. Extract the data.
 459                                 if singleType.IsInterface() {
 460                                         base.Fatalf("singleType interface should have been handled in Add")
 461                                 }
 462                                 val = ifaceData(ncase.Pos(), s.facename, singleType)
 463                         }
 464                         if len(ncase.List) == 1 && ncase.List[0].Op() == ir.ODYNAMICTYPE {
 465                                 dt := ncase.List[0].(*ir.DynamicType)
 466                                 x := ir.NewDynamicTypeAssertExpr(ncase.Pos(), ir.ODYNAMICDOTTYPE, val, dt.RType)
 467                                 x.ITab = dt.ITab
 468                                 x.SetType(caseVar.Type())
 469                                 x.SetTypecheck(1)
 470                                 val = x
 471                         }
 472                         l := []ir.Node{
 473                                 ir.NewDecl(ncase.Pos(), ir.ODCL, caseVar),
 474                                 ir.NewAssignStmt(ncase.Pos(), caseVar, val),
 475                         }
 476                         typecheck.Stmts(l)
 477                         body.Append(l...)
 478                 }
 479                 body.Append(ncase.Body...)
 480                 body.Append(br)
 481         }
 482         sw.Cases = nil
 483
 484         if defaultGoto == nil {
 485                 defaultGoto = br
 486         }
 487         if nilGoto == nil {
 488                 nilGoto = defaultGoto
 489         }
 490         ifNil.Body = []ir.Node{nilGoto}
 491
 492         s.Emit(&sw.Compiled)
 493         sw.Compiled.Append(defaultGoto)
 494         sw.Compiled.Append(body.Take()...)
 495
 496         walkStmtList(sw.Compiled)
 497 }
 498
 499 // typeHashFieldOf returns an expression to select the type hash field
 500 // from an interface's descriptor word (whether a *runtime._type or
 501 // *runtime.itab pointer).
 502 func typeHashFieldOf(pos src.XPos, itab *ir.UnaryExpr) *ir.SelectorExpr {
 503         if itab.Op() != ir.OITAB {
 504                 base.Fatalf("expected OITAB, got %v", itab.Op())
 505         }
 506         var hashField *types.Field
 507         if itab.X.Type().IsEmptyInterface() {
 508                 // runtime._type's hash field
 509                 if rtypeHashField == nil {
 510                         rtypeHashField = runtimeField("hash", int64(2*types.PtrSize), types.Types[types.TUINT32])
 511                 }
 512                 hashField = rtypeHashField
 513         } else {
 514                 // runtime.itab's hash field
 515                 if itabHashField == nil {
 516                         itabHashField = runtimeField("hash", int64(2*types.PtrSize), types.Types[types.TUINT32])
 517                 }
 518                 hashField = itabHashField
 519         }
 520         return boundedDotPtr(pos, itab, hashField)
 521 }
 522
 523 var rtypeHashField, itabHashField *types.Field
 524
 525 // A typeSwitch walks a type switch.
 526 type typeSwitch struct {
 527         // Temporary variables (i.e., ONAMEs) used by type switch dispatch logic:
 528         facename ir.Node // value being type-switched on
 529         hashname ir.Node // type hash of the value being type-switched on
 530         okname   ir.Node // boolean used for comma-ok type assertions
 531
 532         done    ir.Nodes
 533         clauses []typeClause
 534 }
 535
 536 type typeClause struct {
 537         hash uint32
 538         body ir.Nodes
 539 }
 540
 541 func (s *typeSwitch) Add(pos src.XPos, n1 ir.Node, caseVar *ir.Name, jmp ir.Node) {
 542         typ := n1.Type()
 543         var body ir.Nodes
 544         if caseVar != nil {
 545                 l := []ir.Node{
 546                         ir.NewDecl(pos, ir.ODCL, caseVar),
 547                         ir.NewAssignStmt(pos, caseVar, nil),
 548                 }
 549                 typecheck.Stmts(l)
 550                 body.Append(l...)
 551         } else {
 552                 caseVar = ir.BlankNode
 553         }
 554
 555         // cv, ok = iface.(type)
 556         as := ir.NewAssignListStmt(pos, ir.OAS2, nil, nil)
 557         as.Lhs = []ir.Node{caseVar, s.okname} // cv, ok =
 558         switch n1.Op() {
 559         case ir.OTYPE:
 560                 // Static type assertion (non-generic)
 561                 dot := ir.NewTypeAssertExpr(pos, s.facename, typ) // iface.(type)
 562                 as.Rhs = []ir.Node{dot}
 563         case ir.ODYNAMICTYPE:
 564                 // Dynamic type assertion (generic)
 565                 dt := n1.(*ir.DynamicType)
 566                 dot := ir.NewDynamicTypeAssertExpr(pos, ir.ODYNAMICDOTTYPE, s.facename, dt.RType)
 567                 dot.ITab = dt.ITab
 568                 dot.SetType(typ)
 569                 dot.SetTypecheck(1)
 570                 as.Rhs = []ir.Node{dot}
 571         default:
 572                 base.Fatalf("unhandled type case %s", n1.Op())
 573         }
 574         appendWalkStmt(&body, as)
 575
 576         // if ok { goto label }
 577         nif := ir.NewIfStmt(pos, nil, nil, nil)
 578         nif.Cond = s.okname
 579         nif.Body = []ir.Node{jmp}
 580         body.Append(nif)
 581
 582         if n1.Op() == ir.OTYPE && !typ.IsInterface() {
 583                 // Defer static, noninterface cases so they can be binary searched by hash.
 584                 s.clauses = append(s.clauses, typeClause{
 585                         hash: types.TypeHash(n1.Type()),
 586                         body: body,
 587                 })
 588                 return
 589         }
 590
 591         s.flush()
 592         s.done.Append(body.Take()...)
 593 }
 594
 595 func (s *typeSwitch) Emit(out *ir.Nodes) {
 596         s.flush()
 597         out.Append(s.done.Take()...)
 598 }
 599
 600 func (s *typeSwitch) flush() {
 601         cc := s.clauses
 602         s.clauses = nil
 603         if len(cc) == 0 {
 604                 return
 605         }
 606
 607         sort.Slice(cc, func(i, j int) bool { return cc[i].hash < cc[j].hash })
 608
 609         // Combine adjacent cases with the same hash.
 610         merged := cc[:1]
 611         for _, c := range cc[1:] {
 612                 last := &merged[len(merged)-1]
 613                 if last.hash == c.hash {
 614                         last.body.Append(c.body.Take()...)
 615                 } else {
 616                         merged = append(merged, c)
 617                 }
 618         }
 619         cc = merged
 620
 621         if s.tryJumpTable(cc, &s.done) {
 622                 return
 623         }
 624         binarySearch(len(cc), &s.done,
 625                 func(i int) ir.Node {
 626                         return ir.NewBinaryExpr(base.Pos, ir.OLE, s.hashname, ir.NewInt(base.Pos, int64(cc[i-1].hash)))
 627                 },
 628                 func(i int, nif *ir.IfStmt) {
 629                         // TODO(mdempsky): Omit hash equality check if
 630                         // there's only one type.
 631                         c := cc[i]
 632                         nif.Cond = ir.NewBinaryExpr(base.Pos, ir.OEQ, s.hashname, ir.NewInt(base.Pos, int64(c.hash)))
 633                         nif.Body.Append(c.body.Take()...)
 634                 },
 635         )
 636 }
 637
 638 // Try to implement the clauses with a jump table. Returns true if successful.
 639 func (s *typeSwitch) tryJumpTable(cc []typeClause, out *ir.Nodes) bool {
 640         const minCases = 5 // have at least minCases cases in the switch
 641         if base.Flag.N != 0 || !ssagen.Arch.LinkArch.CanJumpTable || base.Ctxt.Retpoline {
 642                 return false
 643         }
 644         if len(cc) < minCases {
 645                 return false // not enough cases for it to be worth it
 646         }
 647         hashes := make([]uint32, len(cc))
 648         // b = # of bits to use. Start with the minimum number of
 649         // bits possible, but try a few larger sizes if needed.
 650         b0 := bits.Len(uint(len(cc) - 1))
 651         for b := b0; b < b0+3; b++ {
 652         pickI:
 653                 for i := 0; i <= 32-b; i++ { // starting bit position
 654                         // Compute the hash we'd get from all the cases,
 655                         // selecting b bits starting at bit i.
 656                         hashes = hashes[:0]
 657                         for _, c := range cc {
 658                                 h := c.hash >> i & (1<<b - 1)
 659                                 hashes = append(hashes, h)
 660                         }
 661                         // Order by increasing hash.
 662                         sort.Slice(hashes, func(j, k int) bool {
 663                                 return hashes[j] < hashes[k]
 664                         })
 665                         for j := 1; j < len(hashes); j++ {
 666                                 if hashes[j] == hashes[j-1] {
 667                                         // There is a duplicate hash; try a different b/i pair.
 668                                         continue pickI
 669                                 }
 670                         }
 671
 672                         // All hashes are distinct. Use these values of b and i.
 673                         h := s.hashname
 674                         if i != 0 {
 675                                 h = ir.NewBinaryExpr(base.Pos, ir.ORSH, h, ir.NewInt(base.Pos, int64(i)))
 676                         }
 677                         h = ir.NewBinaryExpr(base.Pos, ir.OAND, h, ir.NewInt(base.Pos, int64(1<<b-1)))
 678                         h = typecheck.Expr(h)
 679
 680                         // Build jump table.
 681                         jt := ir.NewJumpTableStmt(base.Pos, h)
 682                         jt.Cases = make([]constant.Value, 1<<b)
 683                         jt.Targets = make([]*types.Sym, 1<<b)
 684                         out.Append(jt)
 685
 686                         // Start with all hashes going to the didn't-match target.
 687                         noMatch := typecheck.AutoLabel(".s")
 688                         for j := 0; j < 1<<b; j++ {
 689                                 jt.Cases[j] = constant.MakeInt64(int64(j))
 690                                 jt.Targets[j] = noMatch
 691                         }
 692                         // This statement is not reachable, but it will make it obvious that we don't
 693                         // fall through to the first case.
 694                         out.Append(ir.NewBranchStmt(base.Pos, ir.OGOTO, noMatch))
 695
 696                         // Emit each of the actual cases.
 697                         for _, c := range cc {
 698                                 h := c.hash >> i & (1<<b - 1)
 699                                 label := typecheck.AutoLabel(".s")
 700                                 jt.Targets[h] = label
 701                                 out.Append(ir.NewLabelStmt(base.Pos, label))
 702                                 out.Append(c.body...)
 703                                 // We reach here if the hash matches but the type equality test fails.
 704                                 out.Append(ir.NewBranchStmt(base.Pos, ir.OGOTO, noMatch))
 705                         }
 706                         // Emit point to go to if type doesn't match any case.
 707                         out.Append(ir.NewLabelStmt(base.Pos, noMatch))
 708                         return true
 709                 }
 710         }
 711         // Couldn't find a perfect hash. Fall back to binary search.
 712         return false
 713 }
 714
 715 // binarySearch constructs a binary search tree for handling n cases,
 716 // and appends it to out. It's used for efficiently implementing
 717 // switch statements.
 718 //
 719 // less(i) should return a boolean expression. If it evaluates true,
 720 // then cases before i will be tested; otherwise, cases i and later.
 721 //
 722 // leaf(i, nif) should setup nif (an OIF node) to test case i. In
 723 // particular, it should set nif.Cond and nif.Body.
 724 func binarySearch(n int, out *ir.Nodes, less func(i int) ir.Node, leaf func(i int, nif *ir.IfStmt)) {
 725         const binarySearchMin = 4 // minimum number of cases for binary search
 726
 727         var do func(lo, hi int, out *ir.Nodes)
 728         do = func(lo, hi int, out *ir.Nodes) {
 729                 n := hi - lo
 730                 if n < binarySearchMin {
 731                         for i := lo; i < hi; i++ {
 732                                 nif := ir.NewIfStmt(base.Pos, nil, nil, nil)
 733                                 leaf(i, nif)
 734                                 base.Pos = base.Pos.WithNotStmt()
 735                                 nif.Cond = typecheck.Expr(nif.Cond)
 736                                 nif.Cond = typecheck.DefaultLit(nif.Cond, nil)
 737                                 out.Append(nif)
 738                                 out = &nif.Else
 739                         }
 740                         return
 741                 }
 742
 743                 half := lo + n/2
 744                 nif := ir.NewIfStmt(base.Pos, nil, nil, nil)
 745                 nif.Cond = less(half)
 746                 base.Pos = base.Pos.WithNotStmt()
 747                 nif.Cond = typecheck.Expr(nif.Cond)
 748                 nif.Cond = typecheck.DefaultLit(nif.Cond, nil)
 749                 do(lo, half, &nif.Body)
 750                 do(half, hi, &nif.Else)
 751                 out.Append(nif)
 752         }
 753
 754         do(0, n, out)
 755 }
 756
 757 func stringSearch(expr ir.Node, cc []exprClause, out *ir.Nodes) {
 758         if len(cc) < 4 {
 759                 // Short list, just do brute force equality checks.
 760                 for _, c := range cc {
 761                         nif := ir.NewIfStmt(base.Pos.WithNotStmt(), typecheck.DefaultLit(typecheck.Expr(c.test(expr)), nil), []ir.Node{c.jmp}, nil)
 762                         out.Append(nif)
 763                         out = &nif.Else
 764                 }
 765                 return
 766         }
 767
 768         // The strategy here is to find a simple test to divide the set of possible strings
 769         // that might match expr approximately in half.
 770         // The test we're going to use is to do an ordered comparison of a single byte
 771         // of expr to a constant. We will pick the index of that byte and the value we're
 772         // comparing against to make the split as even as possible.
 773         //   if expr[3] <= 'd' { ... search strings with expr[3] at 'd' or lower  ... }
 774         //   else              { ... search strings with expr[3] at 'e' or higher ... }
 775         //
 776         // To add complication, we will do the ordered comparison in the signed domain.
 777         // The reason for this is to prevent CSE from merging the load used for the
 778         // ordered comparison with the load used for the later equality check.
 779         //   if expr[3] <= 'd' { ... if expr[0] == 'f' && expr[1] == 'o' && expr[2] == 'o' && expr[3] == 'd' { ... } }
 780         // If we did both expr[3] loads in the unsigned domain, they would be CSEd, and that
 781         // would in turn defeat the combining of expr[0]...expr[3] into a single 4-byte load.
 782         // See issue 48222.
 783         // By using signed loads for the ordered comparison and unsigned loads for the
 784         // equality comparison, they don't get CSEd and the equality comparisons will be
 785         // done using wider loads.
 786
 787         n := len(ir.StringVal(cc[0].lo)) // Length of the constant strings.
 788         bestScore := int64(0)            // measure of how good the split is.
 789         bestIdx := 0                     // split using expr[bestIdx]
 790         bestByte := int8(0)              // compare expr[bestIdx] against bestByte
 791         for idx := 0; idx < n; idx++ {
 792                 for b := int8(-128); b < 127; b++ {
 793                         le := 0
 794                         for _, c := range cc {
 795                                 s := ir.StringVal(c.lo)
 796                                 if int8(s[idx]) <= b {
 797                                         le++
 798                                 }
 799                         }
 800                         score := int64(le) * int64(len(cc)-le)
 801                         if score > bestScore {
 802                                 bestScore = score
 803                                 bestIdx = idx
 804                                 bestByte = b
 805                         }
 806                 }
 807         }
 808
 809         // The split must be at least 1:n-1 because we have at least 2 distinct strings; they
 810         // have to be different somewhere.
 811         // TODO: what if the best split is still pretty bad?
 812         if bestScore == 0 {
 813                 base.Fatalf("unable to split string set")
 814         }
 815
 816         // Convert expr to a []int8
 817         slice := ir.NewConvExpr(base.Pos, ir.OSTR2BYTESTMP, types.NewSlice(types.Types[types.TINT8]), expr)
 818         slice.SetTypecheck(1) // legacy typechecker doesn't handle this op
 819         slice.MarkNonNil()
 820         // Load the byte we're splitting on.
 821         load := ir.NewIndexExpr(base.Pos, slice, ir.NewInt(base.Pos, int64(bestIdx)))
 822         // Compare with the value we're splitting on.
 823         cmp := ir.Node(ir.NewBinaryExpr(base.Pos, ir.OLE, load, ir.NewInt(base.Pos, int64(bestByte))))
 824         cmp = typecheck.DefaultLit(typecheck.Expr(cmp), nil)
 825         nif := ir.NewIfStmt(base.Pos, cmp, nil, nil)
 826
 827         var le []exprClause
 828         var gt []exprClause
 829         for _, c := range cc {
 830                 s := ir.StringVal(c.lo)
 831                 if int8(s[bestIdx]) <= bestByte {
 832                         le = append(le, c)
 833                 } else {
 834                         gt = append(gt, c)
 835                 }
 836         }
 837         stringSearch(expr, le, &nif.Body)
 838         stringSearch(expr, gt, &nif.Else)
 839         out.Append(nif)
 840
 841         // TODO: if expr[bestIdx] has enough different possible values, use a jump table.
 842 }