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.
7 // This file implements discovery of switch and type-switch constructs
8 // from low-level control flow.
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.
15 // - a lookup table (for a switch that maps constants to constants)
19 // - a two-level switch (to partition constant strings by their first byte).
27 "golang.org/x/tools/go/ssa"
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
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
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.
51 // One of ConstCases and TypeCases has length >= 2;
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.
60 Start *ssa.BasicBlock // block containing start of if/else chain
61 X ssa.Value // the switch operand
62 ConstCases []ConstCase // ordered list of constant comparisons
63 TypeCases []TypeCase // ordered list of type assertions
64 Default *ssa.BasicBlock // successor if all comparisons fail
67 func (sw *Switch) String() string {
68 // We represent each block by the String() of its
69 // first Instruction, e.g. "print(42:int)".
71 if sw.ConstCases != nil {
72 fmt.Fprintf(&buf, "switch %s {\n", sw.X.Name())
73 for _, c := range sw.ConstCases {
74 fmt.Fprintf(&buf, "case %s: %s\n", c.Value, c.Body.Instrs[0])
77 fmt.Fprintf(&buf, "switch %s.(type) {\n", sw.X.Name())
78 for _, c := range sw.TypeCases {
79 fmt.Fprintf(&buf, "case %s %s: %s\n",
80 c.Binding.Name(), c.Type, c.Body.Instrs[0])
83 if sw.Default != nil {
84 fmt.Fprintf(&buf, "default: %s\n", sw.Default.Instrs[0])
86 fmt.Fprintf(&buf, "}")
90 // Switches examines the control-flow graph of fn and returns the
91 // set of inferred value and type switches. A value switch tests an
92 // ssa.Value for equality against two or more compile-time constant
93 // values. Switches involving link-time constants (addresses) are
94 // ignored. A type switch type-asserts an ssa.Value against two or
97 // The switches are returned in dominance order.
99 // The resulting switches do not necessarily correspond to uses of the
100 // 'switch' keyword in the source: for example, a single source-level
101 // switch statement with non-constant cases may result in zero, one or
102 // many Switches, one per plural sequence of constant cases.
103 // Switches may even be inferred from if/else- or goto-based control flow.
104 // (In general, the control flow constructs of the source program
105 // cannot be faithfully reproduced from the SSA representation.)
107 func Switches(fn *ssa.Function) []Switch {
108 // Traverse the CFG in dominance order, so we don't
109 // enter an if/else-chain in the middle.
110 var switches []Switch
111 seen := make(map[*ssa.BasicBlock]bool) // TODO(adonovan): opt: use ssa.blockSet
112 for _, b := range fn.DomPreorder() {
113 if x, k := isComparisonBlock(b); x != nil {
114 // Block b starts a switch.
115 sw := Switch{Start: b, X: x}
116 valueSwitch(&sw, k, seen)
117 if len(sw.ConstCases) > 1 {
118 switches = append(switches, sw)
122 if y, x, T := isTypeAssertBlock(b); y != nil {
123 // Block b starts a type switch.
124 sw := Switch{Start: b, X: x}
125 typeSwitch(&sw, y, T, seen)
126 if len(sw.TypeCases) > 1 {
127 switches = append(switches, sw)
134 func valueSwitch(sw *Switch, k *ssa.Const, seen map[*ssa.BasicBlock]bool) {
143 sw.ConstCases = append(sw.ConstCases, ConstCase{
149 if len(b.Instrs) > 2 {
150 // Block b contains not just 'if x == k',
151 // so it may have side effects that
152 // make it unsafe to elide.
155 if len(b.Preds) != 1 {
156 // Block b has multiple predecessors,
157 // so it cannot be treated as a case.
160 x, k = isComparisonBlock(b)
165 func typeSwitch(sw *Switch, y ssa.Value, T types.Type, seen map[*ssa.BasicBlock]bool) {
174 sw.TypeCases = append(sw.TypeCases, TypeCase{
181 if len(b.Instrs) > 4 {
182 // Block b contains not just
183 // {TypeAssert; Extract #0; Extract #1; If}
184 // so it may have side effects that
185 // make it unsafe to elide.
188 if len(b.Preds) != 1 {
189 // Block b has multiple predecessors,
190 // so it cannot be treated as a case.
193 y, x, T = isTypeAssertBlock(b)
198 // isComparisonBlock returns the operands (v, k) if a block ends with
199 // a comparison v==k, where k is a compile-time constant.
201 func isComparisonBlock(b *ssa.BasicBlock) (v ssa.Value, k *ssa.Const) {
202 if n := len(b.Instrs); n >= 2 {
203 if i, ok := b.Instrs[n-1].(*ssa.If); ok {
204 if binop, ok := i.Cond.(*ssa.BinOp); ok && binop.Block() == b && binop.Op == token.EQL {
205 if k, ok := binop.Y.(*ssa.Const); ok {
208 if k, ok := binop.X.(*ssa.Const); ok {
217 // isTypeAssertBlock returns the operands (y, x, T) if a block ends with
218 // a type assertion "if y, ok := x.(T); ok {".
220 func isTypeAssertBlock(b *ssa.BasicBlock) (y, x ssa.Value, T types.Type) {
221 if n := len(b.Instrs); n >= 4 {
222 if i, ok := b.Instrs[n-1].(*ssa.If); ok {
223 if ext1, ok := i.Cond.(*ssa.Extract); ok && ext1.Block() == b && ext1.Index == 1 {
224 if ta, ok := ext1.Tuple.(*ssa.TypeAssert); ok && ta.Block() == b {
225 // hack: relies upon instruction ordering.
226 if ext0, ok := b.Instrs[n-3].(*ssa.Extract); ok {
227 return ext0, ta.X, ta.AssertedType