Debian Codegraph @

go/ir/irutil/switch.go

raw
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 }