Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(484)

Side by Side Diff: ssa/ssautil/findswitch.go

Issue 36710043: code review 36710043: go.tools/ssa: FindSwitches() utility infers multiway br... (Closed)
Patch Set: diff -r 5ff8080945aa https://code.google.com/p/go.tools Created 10 years, 3 months ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View unified diff | Download patch
« no previous file with comments | « no previous file | ssa/ssautil/findswitch_test.go » ('j') | ssa/ssautil/testdata/findswitches.go » ('J')
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(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 }
OLDNEW
« no previous file with comments | « no previous file | ssa/ssautil/findswitch_test.go » ('j') | ssa/ssautil/testdata/findswitches.go » ('J')

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b