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