.config/coc/extensions/coc-go-data/tools/pkg/mod/honnef.co/go/tools@v0.0.1-2020.1.5/ir/irutil/switch.go

   1 // Copyright 2013 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 irutil
   6
   7 // This file implements discovery of switch and type-switch constructs
   8 // from low-level control flow.
   9 //
  10 // Many techniques exist for compiling a high-level switch with
  11 // constant cases to efficient machine code.  The optimal choice will
  12 // depend on the data type, the specific case values, the code in the
  13 // body of each case, and the hardware.
  14 // Some examples:
  15 // - a lookup table (for a switch that maps constants to constants)
  16 // - a computed goto
  17 // - a binary tree
  18 // - a perfect hash
  19 // - a two-level switch (to partition constant strings by their first byte).
  20
  21 import (
  22         "bytes"
  23         "fmt"
  24         "go/token"
  25         "go/types"
  26
  27         "honnef.co/go/tools/ir"
  28 )
  29
  30 // A ConstCase represents a single constant comparison.
  31 // It is part of a Switch.
  32 type ConstCase struct {
  33         Block *ir.BasicBlock // block performing the comparison
  34         Body  *ir.BasicBlock // body of the case
  35         Value *ir.Const      // case comparand
  36 }
  37
  38 // A TypeCase represents a single type assertion.
  39 // It is part of a Switch.
  40 type TypeCase struct {
  41         Block   *ir.BasicBlock // block performing the type assert
  42         Body    *ir.BasicBlock // body of the case
  43         Type    types.Type     // case type
  44         Binding ir.Value       // value bound by this case
  45 }
  46
  47 // A Switch is a logical high-level control flow operation
  48 // (a multiway branch) discovered by analysis of a CFG containing
  49 // only if/else chains.  It is not part of the ir.Instruction set.
  50 //
  51 // One of ConstCases and TypeCases has length >= 2;
  52 // the other is nil.
  53 //
  54 // In a value switch, the list of cases may contain duplicate constants.
  55 // A type switch may contain duplicate types, or types assignable
  56 // to an interface type also in the list.
  57 // TODO(adonovan): eliminate such duplicates.
  58 //
  59 type Switch struct {
  60         Start      *ir.BasicBlock // block containing start of if/else chain
  61         X          ir.Value       // the switch operand
  62         ConstCases []ConstCase    // ordered list of constant comparisons
  63         TypeCases  []TypeCase     // ordered list of type assertions
  64         Default    *ir.BasicBlock // successor if all comparisons fail
  65 }
  66
  67 func (sw *Switch) String() string {
  68         // We represent each block by the String() of its
  69         // first Instruction, e.g. "print(42:int)".
  70         var buf bytes.Buffer
  71         if sw.ConstCases != nil {
  72                 fmt.Fprintf(&buf, "switch %s {\n", sw.X.Name())
  73                 for _, c := range sw.ConstCases {
  74                         fmt.Fprintf(&buf, "case %s: %s\n", c.Value.Name(), c.Body.Instrs[0])
  75                 }
  76         } else {
  77                 fmt.Fprintf(&buf, "switch %s.(type) {\n", sw.X.Name())
  78                 for _, c := range sw.TypeCases {
  79                         fmt.Fprintf(&buf, "case %s %s: %s\n",
  80                                 c.Binding.Name(), c.Type, c.Body.Instrs[0])
  81                 }
  82         }
  83         if sw.Default != nil {
  84                 fmt.Fprintf(&buf, "default: %s\n", sw.Default.Instrs[0])
  85         }
  86         fmt.Fprintf(&buf, "}")
  87         return buf.String()
  88 }
  89
  90 // Switches examines the control-flow graph of fn and returns the
  91 // set of inferred value and type switches.  A value switch tests an
  92 // ir.Value for equality against two or more compile-time constant
  93 // values.  Switches involving link-time constants (addresses) are
  94 // ignored.  A type switch type-asserts an ir.Value against two or
  95 // more types.
  96 //
  97 // The switches are returned in dominance order.
  98 //
  99 // The resulting switches do not necessarily correspond to uses of the
 100 // 'switch' keyword in the source: for example, a single source-level
 101 // switch statement with non-constant cases may result in zero, one or
 102 // many Switches, one per plural sequence of constant cases.
 103 // Switches may even be inferred from if/else- or goto-based control flow.
 104 // (In general, the control flow constructs of the source program
 105 // cannot be faithfully reproduced from the IR.)
 106 //
 107 func Switches(fn *ir.Function) []Switch {
 108         // Traverse the CFG in dominance order, so we don't
 109         // enter an if/else-chain in the middle.
 110         var switches []Switch
 111         seen := make(map[*ir.BasicBlock]bool) // TODO(adonovan): opt: use ir.blockSet
 112         for _, b := range fn.DomPreorder() {
 113                 if x, k := isComparisonBlock(b); x != nil {
 114                         // Block b starts a switch.
 115                         sw := Switch{Start: b, X: x}
 116                         valueSwitch(&sw, k, seen)
 117                         if len(sw.ConstCases) > 1 {
 118                                 switches = append(switches, sw)
 119                         }
 120                 }
 121
 122                 if y, x, T := isTypeAssertBlock(b); y != nil {
 123                         // Block b starts a type switch.
 124                         sw := Switch{Start: b, X: x}
 125                         typeSwitch(&sw, y, T, seen)
 126                         if len(sw.TypeCases) > 1 {
 127                                 switches = append(switches, sw)
 128                         }
 129                 }
 130         }
 131         return switches
 132 }
 133
 134 func isSameX(x1 ir.Value, x2 ir.Value) bool {
 135         if x1 == x2 {
 136                 return true
 137         }
 138         if x2, ok := x2.(*ir.Sigma); ok {
 139                 return isSameX(x1, x2.X)
 140         }
 141         return false
 142 }
 143
 144 func valueSwitch(sw *Switch, k *ir.Const, seen map[*ir.BasicBlock]bool) {
 145         b := sw.Start
 146         x := sw.X
 147         for isSameX(sw.X, x) {
 148                 if seen[b] {
 149                         break
 150                 }
 151                 seen[b] = true
 152
 153                 sw.ConstCases = append(sw.ConstCases, ConstCase{
 154                         Block: b,
 155                         Body:  b.Succs[0],
 156                         Value: k,
 157                 })
 158                 b = b.Succs[1]
 159                 n := 0
 160                 for _, instr := range b.Instrs {
 161                         switch instr.(type) {
 162                         case *ir.If, *ir.BinOp:
 163                                 n++
 164                         case *ir.Sigma, *ir.Phi, *ir.DebugRef:
 165                         default:
 166                                 n += 1000
 167                         }
 168                 }
 169                 if n != 2 {
 170                         // Block b contains not just 'if x == k' and σ/ϕ nodes,
 171                         // so it may have side effects that
 172                         // make it unsafe to elide.
 173                         break
 174                 }
 175                 if len(b.Preds) != 1 {
 176                         // Block b has multiple predecessors,
 177                         // so it cannot be treated as a case.
 178                         break
 179                 }
 180                 x, k = isComparisonBlock(b)
 181         }
 182         sw.Default = b
 183 }
 184
 185 func typeSwitch(sw *Switch, y ir.Value, T types.Type, seen map[*ir.BasicBlock]bool) {
 186         b := sw.Start
 187         x := sw.X
 188         for isSameX(sw.X, x) {
 189                 if seen[b] {
 190                         break
 191                 }
 192                 seen[b] = true
 193
 194                 sw.TypeCases = append(sw.TypeCases, TypeCase{
 195                         Block:   b,
 196                         Body:    b.Succs[0],
 197                         Type:    T,
 198                         Binding: y,
 199                 })
 200                 b = b.Succs[1]
 201                 n := 0
 202                 for _, instr := range b.Instrs {
 203                         switch instr.(type) {
 204                         case *ir.TypeAssert, *ir.Extract, *ir.If:
 205                                 n++
 206                         case *ir.Sigma, *ir.Phi:
 207                         default:
 208                                 n += 1000
 209                         }
 210                 }
 211                 if n != 4 {
 212                         // Block b contains not just
 213                         //  {TypeAssert; Extract #0; Extract #1; If}
 214                         // so it may have side effects that
 215                         // make it unsafe to elide.
 216                         break
 217                 }
 218                 if len(b.Preds) != 1 {
 219                         // Block b has multiple predecessors,
 220                         // so it cannot be treated as a case.
 221                         break
 222                 }
 223                 y, x, T = isTypeAssertBlock(b)
 224         }
 225         sw.Default = b
 226 }
 227
 228 // isComparisonBlock returns the operands (v, k) if a block ends with
 229 // a comparison v==k, where k is a compile-time constant.
 230 //
 231 func isComparisonBlock(b *ir.BasicBlock) (v ir.Value, k *ir.Const) {
 232         if n := len(b.Instrs); n >= 2 {
 233                 if i, ok := b.Instrs[n-1].(*ir.If); ok {
 234                         if binop, ok := i.Cond.(*ir.BinOp); ok && binop.Block() == b && binop.Op == token.EQL {
 235                                 if k, ok := binop.Y.(*ir.Const); ok {
 236                                         return binop.X, k
 237                                 }
 238                                 if k, ok := binop.X.(*ir.Const); ok {
 239                                         return binop.Y, k
 240                                 }
 241                         }
 242                 }
 243         }
 244         return
 245 }
 246
 247 // isTypeAssertBlock returns the operands (y, x, T) if a block ends with
 248 // a type assertion "if y, ok := x.(T); ok {".
 249 //
 250 func isTypeAssertBlock(b *ir.BasicBlock) (y, x ir.Value, T types.Type) {
 251         if n := len(b.Instrs); n >= 4 {
 252                 if i, ok := b.Instrs[n-1].(*ir.If); ok {
 253                         if ext1, ok := i.Cond.(*ir.Extract); ok && ext1.Block() == b && ext1.Index == 1 {
 254                                 if ta, ok := ext1.Tuple.(*ir.TypeAssert); ok && ta.Block() == b {
 255                                         // hack: relies upon instruction ordering.
 256                                         if ext0, ok := b.Instrs[n-3].(*ir.Extract); ok {
 257                                                 return ext0, ta.X, ta.AssertedType
 258                                         }
 259                                 }
 260                         }
 261                 }
 262         }
 263         return
 264 }