emit.go

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

     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 ssa
     6  
     7  // Helpers for emitting SSA instructions.
     8  
     9  import (
    10  	"fmt"
    11  	"go/ast"
    12  	"go/token"
    13  	"go/types"
    14  
    15  	"golang.org/x/tools/internal/typeparams"
    16  )
    17  
    18  // emitNew emits to f a new (heap Alloc) instruction allocating an
    19  // object of type typ.  pos is the optional source location.
    20  func emitNew(f *Function, typ types.Type, pos token.Pos) *Alloc {
    21  	v := &Alloc{Heap: true}
    22  	v.setType(types.NewPointer(typ))
    23  	v.setPos(pos)
    24  	f.emit(v)
    25  	return v
    26  }
    27  
    28  // emitLoad emits to f an instruction to load the address addr into a
    29  // new temporary, and returns the value so defined.
    30  func emitLoad(f *Function, addr Value) *UnOp {
    31  	v := &UnOp{Op: token.MUL, X: addr}
    32  	v.setType(deref(typeparams.CoreType(addr.Type())))
    33  	f.emit(v)
    34  	return v
    35  }
    36  
    37  // emitDebugRef emits to f a DebugRef pseudo-instruction associating
    38  // expression e with value v.
    39  func emitDebugRef(f *Function, e ast.Expr, v Value, isAddr bool) {
    40  	if !f.debugInfo() {
    41  		return // debugging not enabled
    42  	}
    43  	if v == nil || e == nil {
    44  		panic("nil")
    45  	}
    46  	var obj types.Object
    47  	e = unparen(e)
    48  	if id, ok := e.(*ast.Ident); ok {
    49  		if isBlankIdent(id) {
    50  			return
    51  		}
    52  		obj = f.objectOf(id)
    53  		switch obj.(type) {
    54  		case *types.Nil, *types.Const, *types.Builtin:
    55  			return
    56  		}
    57  	}
    58  	f.emit(&DebugRef{
    59  		X:      v,
    60  		Expr:   e,
    61  		IsAddr: isAddr,
    62  		object: obj,
    63  	})
    64  }
    65  
    66  // emitArith emits to f code to compute the binary operation op(x, y)
    67  // where op is an eager shift, logical or arithmetic operation.
    68  // (Use emitCompare() for comparisons and Builder.logicalBinop() for
    69  // non-eager operations.)
    70  func emitArith(f *Function, op token.Token, x, y Value, t types.Type, pos token.Pos) Value {
    71  	switch op {
    72  	case token.SHL, token.SHR:
    73  		x = emitConv(f, x, t)
    74  		// y may be signed or an 'untyped' constant.
    75  
    76  		// There is a runtime panic if y is signed and <0. Instead of inserting a check for y<0
    77  		// and converting to an unsigned value (like the compiler) leave y as is.
    78  
    79  		if isUntyped(y.Type().Underlying()) {
    80  			// Untyped conversion:
    81  			// Spec https://go.dev/ref/spec#Operators:
    82  			// The right operand in a shift expression must have integer type or be an untyped constant
    83  			// representable by a value of type uint.
    84  			y = emitConv(f, y, types.Typ[types.Uint])
    85  		}
    86  
    87  	case token.ADD, token.SUB, token.MUL, token.QUO, token.REM, token.AND, token.OR, token.XOR, token.AND_NOT:
    88  		x = emitConv(f, x, t)
    89  		y = emitConv(f, y, t)
    90  
    91  	default:
    92  		panic("illegal op in emitArith: " + op.String())
    93  
    94  	}
    95  	v := &BinOp{
    96  		Op: op,
    97  		X:  x,
    98  		Y:  y,
    99  	}
   100  	v.setPos(pos)
   101  	v.setType(t)
   102  	return f.emit(v)
   103  }
   104  
   105  // emitCompare emits to f code compute the boolean result of
   106  // comparison comparison 'x op y'.
   107  func emitCompare(f *Function, op token.Token, x, y Value, pos token.Pos) Value {
   108  	xt := x.Type().Underlying()
   109  	yt := y.Type().Underlying()
   110  
   111  	// Special case to optimise a tagless SwitchStmt so that
   112  	// these are equivalent
   113  	//   switch { case e: ...}
   114  	//   switch true { case e: ... }
   115  	//   if e==true { ... }
   116  	// even in the case when e's type is an interface.
   117  	// TODO(adonovan): opt: generalise to x==true, false!=y, etc.
   118  	if x == vTrue && op == token.EQL {
   119  		if yt, ok := yt.(*types.Basic); ok && yt.Info()&types.IsBoolean != 0 {
   120  			return y
   121  		}
   122  	}
   123  
   124  	if types.Identical(xt, yt) {
   125  		// no conversion necessary
   126  	} else if isNonTypeParamInterface(x.Type()) {
   127  		y = emitConv(f, y, x.Type())
   128  	} else if isNonTypeParamInterface(y.Type()) {
   129  		x = emitConv(f, x, y.Type())
   130  	} else if _, ok := x.(*Const); ok {
   131  		x = emitConv(f, x, y.Type())
   132  	} else if _, ok := y.(*Const); ok {
   133  		y = emitConv(f, y, x.Type())
   134  	} else {
   135  		// other cases, e.g. channels.  No-op.
   136  	}
   137  
   138  	v := &BinOp{
   139  		Op: op,
   140  		X:  x,
   141  		Y:  y,
   142  	}
   143  	v.setPos(pos)
   144  	v.setType(tBool)
   145  	return f.emit(v)
   146  }
   147  
   148  // isValuePreserving returns true if a conversion from ut_src to
   149  // ut_dst is value-preserving, i.e. just a change of type.
   150  // Precondition: neither argument is a named type.
   151  func isValuePreserving(ut_src, ut_dst types.Type) bool {
   152  	// Identical underlying types?
   153  	if structTypesIdentical(ut_dst, ut_src) {
   154  		return true
   155  	}
   156  
   157  	switch ut_dst.(type) {
   158  	case *types.Chan:
   159  		// Conversion between channel types?
   160  		_, ok := ut_src.(*types.Chan)
   161  		return ok
   162  
   163  	case *types.Pointer:
   164  		// Conversion between pointers with identical base types?
   165  		_, ok := ut_src.(*types.Pointer)
   166  		return ok
   167  	}
   168  	return false
   169  }
   170  
   171  // isSliceToArrayPointer reports whether ut_src is a slice type
   172  // that can be converted to a pointer to an array type ut_dst.
   173  // Precondition: neither argument is a named type.
   174  func isSliceToArrayPointer(ut_src, ut_dst types.Type) bool {
   175  	if slice, ok := ut_src.(*types.Slice); ok {
   176  		if ptr, ok := ut_dst.(*types.Pointer); ok {
   177  			if arr, ok := ptr.Elem().Underlying().(*types.Array); ok {
   178  				return types.Identical(slice.Elem(), arr.Elem())
   179  			}
   180  		}
   181  	}
   182  	return false
   183  }
   184  
   185  // isSliceToArray reports whether ut_src is a slice type
   186  // that can be converted to an array type ut_dst.
   187  // Precondition: neither argument is a named type.
   188  func isSliceToArray(ut_src, ut_dst types.Type) bool {
   189  	if slice, ok := ut_src.(*types.Slice); ok {
   190  		if arr, ok := ut_dst.(*types.Array); ok {
   191  			return types.Identical(slice.Elem(), arr.Elem())
   192  		}
   193  	}
   194  	return false
   195  }
   196  
   197  // emitConv emits to f code to convert Value val to exactly type typ,
   198  // and returns the converted value.  Implicit conversions are required
   199  // by language assignability rules in assignments, parameter passing,
   200  // etc.
   201  func emitConv(f *Function, val Value, typ types.Type) Value {
   202  	t_src := val.Type()
   203  
   204  	// Identical types?  Conversion is a no-op.
   205  	if types.Identical(t_src, typ) {
   206  		return val
   207  	}
   208  	ut_dst := typ.Underlying()
   209  	ut_src := t_src.Underlying()
   210  
   211  	dst_types := typeSetOf(ut_dst)
   212  	src_types := typeSetOf(ut_src)
   213  
   214  	// Just a change of type, but not value or representation?
   215  	preserving := underIs(src_types, func(s types.Type) bool {
   216  		return underIs(dst_types, func(d types.Type) bool {
   217  			return s != nil && d != nil && isValuePreserving(s, d) // all (s -> d) are value preserving.
   218  		})
   219  	})
   220  	if preserving {
   221  		c := &ChangeType{X: val}
   222  		c.setType(typ)
   223  		return f.emit(c)
   224  	}
   225  
   226  	// Conversion to, or construction of a value of, an interface type?
   227  	if isNonTypeParamInterface(typ) {
   228  		// Assignment from one interface type to another?
   229  		if isNonTypeParamInterface(t_src) {
   230  			c := &ChangeInterface{X: val}
   231  			c.setType(typ)
   232  			return f.emit(c)
   233  		}
   234  
   235  		// Untyped nil constant?  Return interface-typed nil constant.
   236  		if ut_src == tUntypedNil {
   237  			return zeroConst(typ)
   238  		}
   239  
   240  		// Convert (non-nil) "untyped" literals to their default type.
   241  		if t, ok := ut_src.(*types.Basic); ok && t.Info()&types.IsUntyped != 0 {
   242  			val = emitConv(f, val, types.Default(ut_src))
   243  		}
   244  
   245  		mi := &MakeInterface{X: val}
   246  		mi.setType(typ)
   247  		return f.emit(mi)
   248  	}
   249  
   250  	// Conversion of a compile-time constant value?
   251  	if c, ok := val.(*Const); ok {
   252  		if isBasic(ut_dst) || c.Value == nil {
   253  			// Conversion of a compile-time constant to
   254  			// another constant type results in a new
   255  			// constant of the destination type and
   256  			// (initially) the same abstract value.
   257  			// We don't truncate the value yet.
   258  			return NewConst(c.Value, typ)
   259  		}
   260  
   261  		// We're converting from constant to non-constant type,
   262  		// e.g. string -> []byte/[]rune.
   263  	}
   264  
   265  	// Conversion from slice to array pointer?
   266  	slice2ptr := underIs(src_types, func(s types.Type) bool {
   267  		return underIs(dst_types, func(d types.Type) bool {
   268  			return s != nil && d != nil && isSliceToArrayPointer(s, d) // all (s->d) are slice to array pointer conversion.
   269  		})
   270  	})
   271  	if slice2ptr {
   272  		c := &SliceToArrayPointer{X: val}
   273  		c.setType(typ)
   274  		return f.emit(c)
   275  	}
   276  
   277  	// Conversion from slice to array?
   278  	slice2array := underIs(src_types, func(s types.Type) bool {
   279  		return underIs(dst_types, func(d types.Type) bool {
   280  			return s != nil && d != nil && isSliceToArray(s, d) // all (s->d) are slice to array conversion.
   281  		})
   282  	})
   283  	if slice2array {
   284  		return emitSliceToArray(f, val, typ)
   285  	}
   286  
   287  	// A representation-changing conversion?
   288  	// All of ut_src or ut_dst is basic, byte slice, or rune slice?
   289  	if isBasicConvTypes(src_types) || isBasicConvTypes(dst_types) {
   290  		c := &Convert{X: val}
   291  		c.setType(typ)
   292  		return f.emit(c)
   293  	}
   294  
   295  	panic(fmt.Sprintf("in %s: cannot convert %s (%s) to %s", f, val, val.Type(), typ))
   296  }
   297  
   298  // emitTypeCoercion emits to f code to coerce the type of a
   299  // Value v to exactly type typ, and returns the coerced value.
   300  //
   301  // Requires that coercing v.Typ() to typ is a value preserving change.
   302  //
   303  // Currently used only when v.Type() is a type instance of typ or vice versa.
   304  // A type v is a type instance of a type t if there exists a
   305  // type parameter substitution σ s.t. σ(v) == t. Example:
   306  //
   307  //	σ(func(T) T) == func(int) int for σ == [T ↦ int]
   308  //
   309  // This happens in instantiation wrappers for conversion
   310  // from an instantiation to a parameterized type (and vice versa)
   311  // with σ substituting f.typeparams by f.typeargs.
   312  func emitTypeCoercion(f *Function, v Value, typ types.Type) Value {
   313  	if types.Identical(v.Type(), typ) {
   314  		return v // no coercion needed
   315  	}
   316  	// TODO(taking): for instances should we record which side is the instance?
   317  	c := &ChangeType{
   318  		X: v,
   319  	}
   320  	c.setType(typ)
   321  	f.emit(c)
   322  	return c
   323  }
   324  
   325  // emitStore emits to f an instruction to store value val at location
   326  // addr, applying implicit conversions as required by assignability rules.
   327  func emitStore(f *Function, addr, val Value, pos token.Pos) *Store {
   328  	s := &Store{
   329  		Addr: addr,
   330  		Val:  emitConv(f, val, deref(addr.Type())),
   331  		pos:  pos,
   332  	}
   333  	f.emit(s)
   334  	return s
   335  }
   336  
   337  // emitJump emits to f a jump to target, and updates the control-flow graph.
   338  // Postcondition: f.currentBlock is nil.
   339  func emitJump(f *Function, target *BasicBlock) {
   340  	b := f.currentBlock
   341  	b.emit(new(Jump))
   342  	addEdge(b, target)
   343  	f.currentBlock = nil
   344  }
   345  
   346  // emitIf emits to f a conditional jump to tblock or fblock based on
   347  // cond, and updates the control-flow graph.
   348  // Postcondition: f.currentBlock is nil.
   349  func emitIf(f *Function, cond Value, tblock, fblock *BasicBlock) {
   350  	b := f.currentBlock
   351  	b.emit(&If{Cond: cond})
   352  	addEdge(b, tblock)
   353  	addEdge(b, fblock)
   354  	f.currentBlock = nil
   355  }
   356  
   357  // emitExtract emits to f an instruction to extract the index'th
   358  // component of tuple.  It returns the extracted value.
   359  func emitExtract(f *Function, tuple Value, index int) Value {
   360  	e := &Extract{Tuple: tuple, Index: index}
   361  	e.setType(tuple.Type().(*types.Tuple).At(index).Type())
   362  	return f.emit(e)
   363  }
   364  
   365  // emitTypeAssert emits to f a type assertion value := x.(t) and
   366  // returns the value.  x.Type() must be an interface.
   367  func emitTypeAssert(f *Function, x Value, t types.Type, pos token.Pos) Value {
   368  	a := &TypeAssert{X: x, AssertedType: t}
   369  	a.setPos(pos)
   370  	a.setType(t)
   371  	return f.emit(a)
   372  }
   373  
   374  // emitTypeTest emits to f a type test value,ok := x.(t) and returns
   375  // a (value, ok) tuple.  x.Type() must be an interface.
   376  func emitTypeTest(f *Function, x Value, t types.Type, pos token.Pos) Value {
   377  	a := &TypeAssert{
   378  		X:            x,
   379  		AssertedType: t,
   380  		CommaOk:      true,
   381  	}
   382  	a.setPos(pos)
   383  	a.setType(types.NewTuple(
   384  		newVar("value", t),
   385  		varOk,
   386  	))
   387  	return f.emit(a)
   388  }
   389  
   390  // emitTailCall emits to f a function call in tail position.  The
   391  // caller is responsible for all fields of 'call' except its type.
   392  // Intended for wrapper methods.
   393  // Precondition: f does/will not use deferred procedure calls.
   394  // Postcondition: f.currentBlock is nil.
   395  func emitTailCall(f *Function, call *Call) {
   396  	tresults := f.Signature.Results()
   397  	nr := tresults.Len()
   398  	if nr == 1 {
   399  		call.typ = tresults.At(0).Type()
   400  	} else {
   401  		call.typ = tresults
   402  	}
   403  	tuple := f.emit(call)
   404  	var ret Return
   405  	switch nr {
   406  	case 0:
   407  		// no-op
   408  	case 1:
   409  		ret.Results = []Value{tuple}
   410  	default:
   411  		for i := 0; i < nr; i++ {
   412  			v := emitExtract(f, tuple, i)
   413  			// TODO(adonovan): in principle, this is required:
   414  			//   v = emitConv(f, o.Type, f.Signature.Results[i].Type)
   415  			// but in practice emitTailCall is only used when
   416  			// the types exactly match.
   417  			ret.Results = append(ret.Results, v)
   418  		}
   419  	}
   420  	f.emit(&ret)
   421  	f.currentBlock = nil
   422  }
   423  
   424  // emitImplicitSelections emits to f code to apply the sequence of
   425  // implicit field selections specified by indices to base value v, and
   426  // returns the selected value.
   427  //
   428  // If v is the address of a struct, the result will be the address of
   429  // a field; if it is the value of a struct, the result will be the
   430  // value of a field.
   431  func emitImplicitSelections(f *Function, v Value, indices []int, pos token.Pos) Value {
   432  	for _, index := range indices {
   433  		fld := typeparams.CoreType(deref(v.Type())).(*types.Struct).Field(index)
   434  
   435  		if isPointer(v.Type()) {
   436  			instr := &FieldAddr{
   437  				X:     v,
   438  				Field: index,
   439  			}
   440  			instr.setPos(pos)
   441  			instr.setType(types.NewPointer(fld.Type()))
   442  			v = f.emit(instr)
   443  			// Load the field's value iff indirectly embedded.
   444  			if isPointer(fld.Type()) {
   445  				v = emitLoad(f, v)
   446  			}
   447  		} else {
   448  			instr := &Field{
   449  				X:     v,
   450  				Field: index,
   451  			}
   452  			instr.setPos(pos)
   453  			instr.setType(fld.Type())
   454  			v = f.emit(instr)
   455  		}
   456  	}
   457  	return v
   458  }
   459  
   460  // emitFieldSelection emits to f code to select the index'th field of v.
   461  //
   462  // If wantAddr, the input must be a pointer-to-struct and the result
   463  // will be the field's address; otherwise the result will be the
   464  // field's value.
   465  // Ident id is used for position and debug info.
   466  func emitFieldSelection(f *Function, v Value, index int, wantAddr bool, id *ast.Ident) Value {
   467  	fld := typeparams.CoreType(deref(v.Type())).(*types.Struct).Field(index)
   468  	if isPointer(v.Type()) {
   469  		instr := &FieldAddr{
   470  			X:     v,
   471  			Field: index,
   472  		}
   473  		instr.setPos(id.Pos())
   474  		instr.setType(types.NewPointer(fld.Type()))
   475  		v = f.emit(instr)
   476  		// Load the field's value iff we don't want its address.
   477  		if !wantAddr {
   478  			v = emitLoad(f, v)
   479  		}
   480  	} else {
   481  		instr := &Field{
   482  			X:     v,
   483  			Field: index,
   484  		}
   485  		instr.setPos(id.Pos())
   486  		instr.setType(fld.Type())
   487  		v = f.emit(instr)
   488  	}
   489  	emitDebugRef(f, id, v, wantAddr)
   490  	return v
   491  }
   492  
   493  // emitSliceToArray emits to f code to convert a slice value to an array value.
   494  //
   495  // Precondition: all types in type set of typ are arrays and convertible to all
   496  // types in the type set of val.Type().
   497  func emitSliceToArray(f *Function, val Value, typ types.Type) Value {
   498  	// Emit the following:
   499  	// if val == nil && len(typ) == 0 {
   500  	//    ptr = &[0]T{}
   501  	// } else {
   502  	//	  ptr = SliceToArrayPointer(val)
   503  	// }
   504  	// v = *ptr
   505  
   506  	ptype := types.NewPointer(typ)
   507  	p := &SliceToArrayPointer{X: val}
   508  	p.setType(ptype)
   509  	ptr := f.emit(p)
   510  
   511  	nilb := f.newBasicBlock("slicetoarray.nil")
   512  	nonnilb := f.newBasicBlock("slicetoarray.nonnil")
   513  	done := f.newBasicBlock("slicetoarray.done")
   514  
   515  	cond := emitCompare(f, token.EQL, ptr, zeroConst(ptype), token.NoPos)
   516  	emitIf(f, cond, nilb, nonnilb)
   517  	f.currentBlock = nilb
   518  
   519  	zero := f.addLocal(typ, token.NoPos)
   520  	emitJump(f, done)
   521  	f.currentBlock = nonnilb
   522  
   523  	emitJump(f, done)
   524  	f.currentBlock = done
   525  
   526  	phi := &Phi{Edges: []Value{zero, ptr}, Comment: "slicetoarray"}
   527  	phi.pos = val.Pos()
   528  	phi.setType(typ)
   529  	x := f.emit(phi)
   530  	unOp := &UnOp{Op: token.MUL, X: x}
   531  	unOp.setType(typ)
   532  	return f.emit(unOp)
   533  }
   534  
   535  // zeroValue emits to f code to produce a zero value of type t,
   536  // and returns it.
   537  func zeroValue(f *Function, t types.Type) Value {
   538  	switch t.Underlying().(type) {
   539  	case *types.Struct, *types.Array:
   540  		return emitLoad(f, f.addLocal(t, token.NoPos))
   541  	default:
   542  		return zeroConst(t)
   543  	}
   544  }
   545  
   546  // createRecoverBlock emits to f a block of code to return after a
   547  // recovered panic, and sets f.Recover to it.
   548  //
   549  // If f's result parameters are named, the code loads and returns
   550  // their current values, otherwise it returns the zero values of their
   551  // type.
   552  //
   553  // Idempotent.
   554  func createRecoverBlock(f *Function) {
   555  	if f.Recover != nil {
   556  		return // already created
   557  	}
   558  	saved := f.currentBlock
   559  
   560  	f.Recover = f.newBasicBlock("recover")
   561  	f.currentBlock = f.Recover
   562  
   563  	var results []Value
   564  	if f.namedResults != nil {
   565  		// Reload NRPs to form value tuple.
   566  		for _, r := range f.namedResults {
   567  			results = append(results, emitLoad(f, r))
   568  		}
   569  	} else {
   570  		R := f.Signature.Results()
   571  		for i, n := 0, R.Len(); i < n; i++ {
   572  			T := R.At(i).Type()
   573  
   574  			// Return zero value of each result type.
   575  			results = append(results, zeroValue(f, T))
   576  		}
   577  	}
   578  	f.emit(&Return{Results: results})
   579  
   580  	f.currentBlock = saved
   581  }
   582
View as plain text