switch.go

Documentation: golang.org/x/tools/go/ssa/ssautil

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