| 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/go/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 |
type Switch struct { |
| 59 |
Start *ir.BasicBlock // block containing start of if/else chain |
| 60 |
X ir.Value // the switch operand |
| 61 |
ConstCases []ConstCase // ordered list of constant comparisons |
| 62 |
TypeCases []TypeCase // ordered list of type assertions |
| 63 |
Default *ir.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.Name(), 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 |
// ir.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 ir.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 IR.) |
| 105 |
func Switches(fn *ir.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[*ir.BasicBlock]bool) // TODO(adonovan): opt: use ir.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 isSameX(x1 ir.Value, x2 ir.Value) bool { |
| 133 |
if x1 == x2 { |
| 134 |
return true |
| 135 |
} |
| 136 |
if x2, ok := x2.(*ir.Sigma); ok { |
| 137 |
return isSameX(x1, x2.X) |
| 138 |
} |
| 139 |
return false |
| 140 |
} |
| 141 |
|
| 142 |
func valueSwitch(sw *Switch, k *ir.Const, seen map[*ir.BasicBlock]bool) { |
| 143 |
b := sw.Start |
| 144 |
x := sw.X |
| 145 |
for isSameX(sw.X, x) { |
| 146 |
if seen[b] { |
| 147 |
break |
| 148 |
} |
| 149 |
seen[b] = true |
| 150 |
|
| 151 |
sw.ConstCases = append(sw.ConstCases, ConstCase{ |
| 152 |
Block: b, |
| 153 |
Body: b.Succs[0], |
| 154 |
Value: k, |
| 155 |
}) |
| 156 |
b = b.Succs[1] |
| 157 |
n := 0 |
| 158 |
for _, instr := range b.Instrs { |
| 159 |
switch instr.(type) { |
| 160 |
case *ir.If, *ir.BinOp: |
| 161 |
n++ |
| 162 |
case *ir.Sigma, *ir.Phi, *ir.DebugRef: |
| 163 |
default: |
| 164 |
n += 1000 |
| 165 |
} |
| 166 |
} |
| 167 |
if n != 2 { |
| 168 |
// Block b contains not just 'if x == k' and σ/ϕ nodes, |
| 169 |
// so it may have side effects that |
| 170 |
// make it unsafe to elide. |
| 171 |
break |
| 172 |
} |
| 173 |
if len(b.Preds) != 1 { |
| 174 |
// Block b has multiple predecessors, |
| 175 |
// so it cannot be treated as a case. |
| 176 |
break |
| 177 |
} |
| 178 |
x, k = isComparisonBlock(b) |
| 179 |
} |
| 180 |
sw.Default = b |
| 181 |
} |
| 182 |
|
| 183 |
func typeSwitch(sw *Switch, y ir.Value, T types.Type, seen map[*ir.BasicBlock]bool) { |
| 184 |
b := sw.Start |
| 185 |
x := sw.X |
| 186 |
for isSameX(sw.X, x) { |
| 187 |
if seen[b] { |
| 188 |
break |
| 189 |
} |
| 190 |
seen[b] = true |
| 191 |
|
| 192 |
sw.TypeCases = append(sw.TypeCases, TypeCase{ |
| 193 |
Block: b, |
| 194 |
Body: b.Succs[0], |
| 195 |
Type: T, |
| 196 |
Binding: y, |
| 197 |
}) |
| 198 |
b = b.Succs[1] |
| 199 |
n := 0 |
| 200 |
for _, instr := range b.Instrs { |
| 201 |
switch instr.(type) { |
| 202 |
case *ir.TypeAssert, *ir.Extract, *ir.If: |
| 203 |
n++ |
| 204 |
case *ir.Sigma, *ir.Phi: |
| 205 |
default: |
| 206 |
n += 1000 |
| 207 |
} |
| 208 |
} |
| 209 |
if n != 4 { |
| 210 |
// Block b contains not just |
| 211 |
// {TypeAssert; Extract #0; Extract #1; If} |
| 212 |
// so it may have side effects that |
| 213 |
// make it unsafe to elide. |
| 214 |
break |
| 215 |
} |
| 216 |
if len(b.Preds) != 1 { |
| 217 |
// Block b has multiple predecessors, |
| 218 |
// so it cannot be treated as a case. |
| 219 |
break |
| 220 |
} |
| 221 |
y, x, T = isTypeAssertBlock(b) |
| 222 |
} |
| 223 |
sw.Default = b |
| 224 |
} |
| 225 |
|
| 226 |
// isComparisonBlock returns the operands (v, k) if a block ends with |
| 227 |
// a comparison v==k, where k is a compile-time constant. |
| 228 |
func isComparisonBlock(b *ir.BasicBlock) (v ir.Value, k *ir.Const) { |
| 229 |
if n := len(b.Instrs); n >= 2 { |
| 230 |
if i, ok := b.Instrs[n-1].(*ir.If); ok { |
| 231 |
if binop, ok := i.Cond.(*ir.BinOp); ok && binop.Block() == b && binop.Op == token.EQL { |
| 232 |
if k, ok := binop.Y.(*ir.Const); ok { |
| 233 |
return binop.X, k |
| 234 |
} |
| 235 |
if k, ok := binop.X.(*ir.Const); ok { |
| 236 |
return binop.Y, k |
| 237 |
} |
| 238 |
} |
| 239 |
} |
| 240 |
} |
| 241 |
return |
| 242 |
} |
| 243 |
|
| 244 |
// isTypeAssertBlock returns the operands (y, x, T) if a block ends with |
| 245 |
// a type assertion "if y, ok := x.(T); ok {". |
| 246 |
func isTypeAssertBlock(b *ir.BasicBlock) (y, x ir.Value, T types.Type) { |
| 247 |
if n := len(b.Instrs); n >= 4 { |
| 248 |
if i, ok := b.Instrs[n-1].(*ir.If); ok { |
| 249 |
if ext1, ok := i.Cond.(*ir.Extract); ok && ext1.Block() == b && ext1.Index == 1 { |
| 250 |
if ta, ok := ext1.Tuple.(*ir.TypeAssert); ok && ta.Block() == b { |
| 251 |
// hack: relies upon instruction ordering. |
| 252 |
if ext0, ok := b.Instrs[n-3].(*ir.Extract); ok { |
| 253 |
return ext0, ta.X, ta.AssertedType |
| 254 |
} |
| 255 |
} |
| 256 |
} |
| 257 |
} |
| 258 |
} |
| 259 |
return |
| 260 |
} |