| 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 ssautil |
| 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 | "golang.org/x/tools/go/ssa" |
| 28 | ) |
| 29 | |
| 30 | // A ConstCase represents a single constant comparison. |
| 31 | // It is part of a Switch. |
| 32 | type ConstCase struct { |
| 33 | Block *ssa.BasicBlock // block performing the comparison |
| 34 | Body *ssa.BasicBlock // body of the case |
| 35 | Value *ssa.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 *ssa.BasicBlock // block performing the type assert |
| 42 | Body *ssa.BasicBlock // body of the case |
| 43 | Type types.Type // case type |
| 44 | Binding ssa.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 ssa.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 | type Switch struct { |
| 59 | Start *ssa.BasicBlock // block containing start of if/else chain |
| 60 | X ssa.Value // the switch operand |
| 61 | ConstCases []ConstCase // ordered list of constant comparisons |
| 62 | TypeCases []TypeCase // ordered list of type assertions |
| 63 | Default *ssa.BasicBlock // successor if all comparisons fail |
| 64 | } |
| 65 | |
| 66 | func (sw *Switch) String() string { |
| 67 | // We represent each block by the String() of its |
| 68 | // first Instruction, e.g. "print(42:int)". |
| 69 | var buf bytes.Buffer |
| 70 | if sw.ConstCases != nil { |
| 71 | fmt.Fprintf(&buf, "switch %s {\n", sw.X.Name()) |
| 72 | for _, c := range sw.ConstCases { |
| 73 | fmt.Fprintf(&buf, "case %s: %s\n", c.Value, c.Body.Instrs[0]) |
| 74 | } |
| 75 | } else { |
| 76 | fmt.Fprintf(&buf, "switch %s.(type) {\n", sw.X.Name()) |
| 77 | for _, c := range sw.TypeCases { |
| 78 | fmt.Fprintf(&buf, "case %s %s: %s\n", |
| 79 | c.Binding.Name(), c.Type, c.Body.Instrs[0]) |
| 80 | } |
| 81 | } |
| 82 | if sw.Default != nil { |
| 83 | fmt.Fprintf(&buf, "default: %s\n", sw.Default.Instrs[0]) |
| 84 | } |
| 85 | fmt.Fprintf(&buf, "}") |
| 86 | return buf.String() |
| 87 | } |
| 88 | |
| 89 | // Switches examines the control-flow graph of fn and returns the |
| 90 | // set of inferred value and type switches. A value switch tests an |
| 91 | // ssa.Value for equality against two or more compile-time constant |
| 92 | // values. Switches involving link-time constants (addresses) are |
| 93 | // ignored. A type switch type-asserts an ssa.Value against two or |
| 94 | // more types. |
| 95 | // |
| 96 | // The switches are returned in dominance order. |
| 97 | // |
| 98 | // The resulting switches do not necessarily correspond to uses of the |
| 99 | // 'switch' keyword in the source: for example, a single source-level |
| 100 | // switch statement with non-constant cases may result in zero, one or |
| 101 | // many Switches, one per plural sequence of constant cases. |
| 102 | // Switches may even be inferred from if/else- or goto-based control flow. |
| 103 | // (In general, the control flow constructs of the source program |
| 104 | // cannot be faithfully reproduced from the SSA representation.) |
| 105 | func Switches(fn *ssa.Function) []Switch { |
| 106 | // Traverse the CFG in dominance order, so we don't |
| 107 | // enter an if/else-chain in the middle. |
| 108 | var switches []Switch |
| 109 | seen := make(map[*ssa.BasicBlock]bool) // TODO(adonovan): opt: use ssa.blockSet |
| 110 | for _, b := range fn.DomPreorder() { |
| 111 | if x, k := isComparisonBlock(b); x != nil { |
| 112 | // Block b starts a switch. |
| 113 | sw := Switch{Start: b, X: x} |
| 114 | valueSwitch(&sw, k, seen) |
| 115 | if len(sw.ConstCases) > 1 { |
| 116 | switches = append(switches, sw) |
| 117 | } |
| 118 | } |
| 119 | |
| 120 | if y, x, T := isTypeAssertBlock(b); y != nil { |
| 121 | // Block b starts a type switch. |
| 122 | sw := Switch{Start: b, X: x} |
| 123 | typeSwitch(&sw, y, T, seen) |
| 124 | if len(sw.TypeCases) > 1 { |
| 125 | switches = append(switches, sw) |
| 126 | } |
| 127 | } |
| 128 | } |
| 129 | return switches |
| 130 | } |
| 131 | |
| 132 | func valueSwitch(sw *Switch, k *ssa.Const, seen map[*ssa.BasicBlock]bool) { |
| 133 | b := sw.Start |
| 134 | x := sw.X |
| 135 | for x == sw.X { |
| 136 | if seen[b] { |
| 137 | break |
| 138 | } |
| 139 | seen[b] = true |
| 140 | |
| 141 | sw.ConstCases = append(sw.ConstCases, ConstCase{ |
| 142 | Block: b, |
| 143 | Body: b.Succs[0], |
| 144 | Value: k, |
| 145 | }) |
| 146 | b = b.Succs[1] |
| 147 | if len(b.Instrs) > 2 { |
| 148 | // Block b contains not just 'if x == k', |
| 149 | // so it may have side effects that |
| 150 | // make it unsafe to elide. |
| 151 | break |
| 152 | } |
| 153 | if len(b.Preds) != 1 { |
| 154 | // Block b has multiple predecessors, |
| 155 | // so it cannot be treated as a case. |
| 156 | break |
| 157 | } |
| 158 | x, k = isComparisonBlock(b) |
| 159 | } |
| 160 | sw.Default = b |
| 161 | } |
| 162 | |
| 163 | func typeSwitch(sw *Switch, y ssa.Value, T types.Type, seen map[*ssa.BasicBlock]bool) { |
| 164 | b := sw.Start |
| 165 | x := sw.X |
| 166 | for x == sw.X { |
| 167 | if seen[b] { |
| 168 | break |
| 169 | } |
| 170 | seen[b] = true |
| 171 | |
| 172 | sw.TypeCases = append(sw.TypeCases, TypeCase{ |
| 173 | Block: b, |
| 174 | Body: b.Succs[0], |
| 175 | Type: T, |
| 176 | Binding: y, |
| 177 | }) |
| 178 | b = b.Succs[1] |
| 179 | if len(b.Instrs) > 4 { |
| 180 | // Block b contains not just |
| 181 | // {TypeAssert; Extract #0; Extract #1; If} |
| 182 | // so it may have side effects that |
| 183 | // make it unsafe to elide. |
| 184 | break |
| 185 | } |
| 186 | if len(b.Preds) != 1 { |
| 187 | // Block b has multiple predecessors, |
| 188 | // so it cannot be treated as a case. |
| 189 | break |
| 190 | } |
| 191 | y, x, T = isTypeAssertBlock(b) |
| 192 | } |
| 193 | sw.Default = b |
| 194 | } |
| 195 | |
| 196 | // isComparisonBlock returns the operands (v, k) if a block ends with |
| 197 | // a comparison v==k, where k is a compile-time constant. |
| 198 | func isComparisonBlock(b *ssa.BasicBlock) (v ssa.Value, k *ssa.Const) { |
| 199 | if n := len(b.Instrs); n >= 2 { |
| 200 | if i, ok := b.Instrs[n-1].(*ssa.If); ok { |
| 201 | if binop, ok := i.Cond.(*ssa.BinOp); ok && binop.Block() == b && binop.Op == token.EQL { |
| 202 | if k, ok := binop.Y.(*ssa.Const); ok { |
| 203 | return binop.X, k |
| 204 | } |
| 205 | if k, ok := binop.X.(*ssa.Const); ok { |
| 206 | return binop.Y, k |
| 207 | } |
| 208 | } |
| 209 | } |
| 210 | } |
| 211 | return |
| 212 | } |
| 213 | |
| 214 | // isTypeAssertBlock returns the operands (y, x, T) if a block ends with |
| 215 | // a type assertion "if y, ok := x.(T); ok {". |
| 216 | func isTypeAssertBlock(b *ssa.BasicBlock) (y, x ssa.Value, T types.Type) { |
| 217 | if n := len(b.Instrs); n >= 4 { |
| 218 | if i, ok := b.Instrs[n-1].(*ssa.If); ok { |
| 219 | if ext1, ok := i.Cond.(*ssa.Extract); ok && ext1.Block() == b && ext1.Index == 1 { |
| 220 | if ta, ok := ext1.Tuple.(*ssa.TypeAssert); ok && ta.Block() == b { |
| 221 | // hack: relies upon instruction ordering. |
| 222 | if ext0, ok := b.Instrs[n-3].(*ssa.Extract); ok { |
| 223 | return ext0, ta.X, ta.AssertedType |
| 224 | } |
| 225 | } |
| 226 | } |
| 227 | } |
| 228 | } |
| 229 | return |
| 230 | } |
| 231 |
Members