Left: | ||
Right: |
OLD | NEW |
---|---|
(Empty) | |
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 low-level switch and | |
8 // typeswitch control-flow constructs. | |
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 values, and the hardware. | |
13 // Some examples: | |
14 // - a lookup table (for a switch that maps constants to constants) | |
15 // - a computed goto | |
16 // - a binary tree | |
17 // - a perfect hash | |
18 // - a two-level switch (to partition constant strings by their first byte). | |
gri1
2013/12/05 18:04:35
what happens if there are fallthroughs?
adonovan
2013/12/05 19:26:58
Comment is now:
// The optimal choice will
// depe
| |
19 | |
20 import ( | |
21 "bytes" | |
22 "fmt" | |
23 "go/token" | |
24 | |
25 "code.google.com/p/go.tools/go/types" | |
26 "code.google.com/p/go.tools/ssa" | |
27 ) | |
28 | |
29 // A ConstCase represents a single constant comparison. | |
30 // It is part of a Switch. | |
31 type ConstCase struct { | |
32 Block *ssa.BasicBlock // block performing the comparison | |
33 Body *ssa.BasicBlock // body of the case | |
34 Value *ssa.Const // case comparand | |
35 } | |
36 | |
37 // A TypeCase represents a single type assertion. | |
38 // It is part of a Switch. | |
39 type TypeCase struct { | |
40 Block *ssa.BasicBlock // block performing the type assert | |
41 Body *ssa.BasicBlock // body of the case | |
42 Type types.Type // case type | |
43 Binding ssa.Value // value bound by this case | |
44 } | |
45 | |
46 // A Switch is a logical high-level control flow operation | |
47 // (a multiway branch) discovered by analysis of a CFG containing | |
48 // only if/else chains. It is not part of the ssa.Instruction set. | |
49 // | |
50 // Exactly one of ConstCases and TypeCases is non-empty. | |
gri1
2013/12/05 18:04:35
non-empty or non-nil?
adonovan
2013/12/05 19:26:58
Changed to be excruciatingly specific:
// One of
| |
51 // | |
52 // In a value switch, the list of cases may contain duplicate constants. | |
53 // A type switch may contain duplicate types, or types assignable | |
54 // to an interface type also in the list. | |
55 // TODO(adonovan): eliminate such duplicates. | |
56 // | |
57 type Switch struct { | |
58 Start *ssa.BasicBlock // block containing start of if/else chain | |
59 X ssa.Value // the switch operand | |
gri1
2013/12/05 18:04:35
s/X/Value/
gri1
2013/12/05 18:04:35
// value to switch on
adonovan
2013/12/05 19:26:58
We use X liberally in ast.Expr and ssa.Instruction
| |
60 ConstCases []ConstCase // ordered list of constant comparisons | |
61 TypeCases []TypeCase // ordered list of type assertions | |
62 Default *ssa.BasicBlock // successor if all comparisons fail | |
63 } | |
64 | |
65 func (sw *Switch) String() string { | |
66 // We represent each block by the String() of its | |
gri1
2013/12/05 18:04:35
s/by/with/ ?
adonovan
2013/12/05 19:26:58
Isn't "by" better here? Merriam Webster has "repr
| |
67 // first Instruction, e.g. "print(42:int)". | |
68 // This is a favour to the tests. | |
gri1
2013/12/05 18:04:35
leave last sentence away - no need
adonovan
2013/12/05 19:26:58
Removed. (My point was that using the basic block
| |
69 var buf bytes.Buffer | |
70 if sw.ConstCases != nil { | |
gri1
2013/12/05 18:04:35
here you're checking against nil, not len(sw.Const
adonovan
2013/12/05 19:26:58
Clarified as suggested.
| |
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.Instr s[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 // FindSwitches 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 // | |
106 func FindSwitches(fn *ssa.Function) []Switch { | |
107 // Traverse the CFG in dominance order, so we don't | |
108 // enter an if/else-chain in the middle. | |
109 var switches []Switch | |
110 seen := make(map[*ssa.BasicBlock]bool) // TODO(adonovan): opt: use block Set | |
111 for _, b := range fn.DomPreorder() { | |
112 if x, k := isComparisonBlock(b); x != nil { | |
113 // Block b starts a switch. | |
114 sw := Switch{Start: b, X: x} | |
115 findValueSwitch(&sw, k, seen) | |
116 if len(sw.ConstCases) > 1 { | |
117 switches = append(switches, sw) | |
118 } | |
119 } | |
120 | |
121 if y, x, T := isTypeAssertBlock(b); y != nil { | |
122 // Block b starts a type switch. | |
123 sw := Switch{Start: b, X: x} | |
124 findTypeSwitch(&sw, y, T, seen) | |
125 if len(sw.TypeCases) > 1 { | |
126 switches = append(switches, sw) | |
127 } | |
128 } | |
129 } | |
130 return switches | |
131 } | |
132 | |
133 func findValueSwitch(sw *Switch, k *ssa.Const, seen map[*ssa.BasicBlock]bool) { | |
134 b := sw.Start | |
135 x := sw.X | |
136 for x == sw.X { | |
137 if seen[b] { | |
138 break | |
139 } | |
140 seen[b] = true | |
141 | |
142 sw.ConstCases = append(sw.ConstCases, ConstCase{ | |
143 Block: b, | |
144 Body: b.Succs[0], | |
145 Value: k, | |
146 }) | |
147 b = b.Succs[1] | |
148 if len(b.Instrs) > 2 { | |
149 // Block b contains not just 'if x == k', | |
150 // so it may have side effects that | |
151 // make it unsafe to elide. | |
152 break | |
153 } | |
154 if len(b.Preds) != 1 { | |
155 // Block b has multiple predecessors, | |
156 // so it cannot be treated as a case. | |
157 break | |
158 } | |
159 x, k = isComparisonBlock(b) | |
160 } | |
161 sw.Default = b | |
162 } | |
163 | |
164 func findTypeSwitch(sw *Switch, y ssa.Value, T types.Type, seen map[*ssa.BasicBl ock]bool) { | |
165 b := sw.Start | |
166 x := sw.X | |
167 for x == sw.X { | |
168 if seen[b] { | |
169 break | |
170 } | |
171 seen[b] = true | |
172 | |
173 sw.TypeCases = append(sw.TypeCases, TypeCase{ | |
174 Block: b, | |
175 Body: b.Succs[0], | |
176 Type: T, | |
177 Binding: y, | |
178 }) | |
179 b = b.Succs[1] | |
180 if len(b.Instrs) > 4 { | |
181 // Block b contains not just | |
182 // {TypeAssert; Extract #0; Extract #1; If} | |
183 // so it may have side effects that | |
184 // make it unsafe to elide. | |
185 break | |
186 } | |
187 if len(b.Preds) != 1 { | |
188 // Block b has multiple predecessors, | |
189 // so it cannot be treated as a case. | |
190 break | |
191 } | |
192 y, x, T = isTypeAssertBlock(b) | |
193 } | |
194 sw.Default = b | |
195 } | |
196 | |
197 // isComparisonBlock returns the operands (v, k) if a block ends with | |
198 // a comparison v==k, where k is a compile-time constant. | |
199 // | |
200 func isComparisonBlock(b *ssa.BasicBlock) (v ssa.Value, k *ssa.Const) { | |
201 if n := len(b.Instrs); n >= 2 { | |
202 if i, ok := b.Instrs[n-1].(*ssa.If); ok { | |
203 if binop, ok := i.Cond.(*ssa.BinOp); ok && binop.Block() == b && binop.Op == token.EQL { | |
204 if k, ok := binop.Y.(*ssa.Const); ok { | |
205 return binop.X, k | |
206 } | |
207 if k, ok := binop.X.(*ssa.Const); ok { | |
208 return binop.Y, k | |
209 } | |
210 } | |
211 } | |
212 } | |
213 return | |
214 } | |
215 | |
216 // isTypeAssertBlock returns the operands (y, x, T) if a block ends with | |
217 // a type assertion "if y, ok := x.(T); ok {". | |
218 // | |
219 func isTypeAssertBlock(b *ssa.BasicBlock) (y, x ssa.Value, T types.Type) { | |
220 if n := len(b.Instrs); n >= 4 { | |
221 if i, ok := b.Instrs[n-1].(*ssa.If); ok { | |
222 if ext1, ok := i.Cond.(*ssa.Extract); ok && ext1.Block() == b && ext1.Index == 1 { | |
223 if ta, ok := ext1.Tuple.(*ssa.TypeAssert); ok && ta.Block() == b { | |
224 // hack: relies upon instruction orderin g. | |
225 if ext0, ok := b.Instrs[n-3].(*ssa.Extra ct); ok { | |
226 return ext0, ta.X, ta.AssertedTy pe | |
227 } | |
228 } | |
229 } | |
230 } | |
231 } | |
232 return | |
233 } | |
OLD | NEW |