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 a 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 in the same function, 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 = ast.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 addMakeInterfaceType(f.Prog, t)
253 }
254 255 mi := &MakeInterface{X: val}
256 mi.setType(typ)
257 return f.emit(mi)
258 }
259 260 // conversionCase describes an instruction pattern that maybe emitted to
261 // model d <- s for d in dst_terms and s in src_terms.
262 // Multiple conversions can match the same pattern.
263 type conversionCase uint8
264 const (
265 changeType conversionCase = 1 << iota
266 sliceToArray
267 sliceToArrayPtr
268 sliceTo0Array
269 sliceTo0ArrayPtr
270 convert
271 )
272 // classify the conversion case of a source type us to a destination type ud.
273 // us and ud are underlying types (not *Named or *Alias)
274 classify := func(us, ud types.Type) conversionCase {
275 // Just a change of type, but not value or representation?
276 if isValuePreserving(us, ud) {
277 return changeType
278 }
279 280 // Conversion from slice to array or slice to array pointer?
281 if slice, ok := us.(*types.Slice); ok {
282 var arr *types.Array
283 var ptr bool
284 // Conversion from slice to array pointer?
285 switch d := ud.(type) {
286 case *types.Array:
287 arr = d
288 case *types.Pointer:
289 arr, _ = d.Elem().Underlying().(*types.Array)
290 ptr = true
291 }
292 if arr != nil && types.Identical(slice.Elem(), arr.Elem()) {
293 if arr.Len() == 0 {
294 if ptr {
295 return sliceTo0ArrayPtr
296 } else {
297 return sliceTo0Array
298 }
299 }
300 if ptr {
301 return sliceToArrayPtr
302 } else {
303 return sliceToArray
304 }
305 }
306 }
307 308 // The only remaining case in well-typed code is a representation-
309 // changing conversion of basic types (possibly with []byte/[]rune).
310 if !isBasic(us) && !isBasic(ud) {
311 panic(fmt.Sprintf("in %s: cannot convert term %s (%s [within %s]) to type %s [within %s]", f, val, val.Type(), us, typ, ud))
312 }
313 return convert
314 }
315 316 var classifications conversionCase
317 underIs(ut_src, func(us types.Type) bool {
318 return underIs(ut_dst, func(ud types.Type) bool {
319 if us != nil && ud != nil {
320 classifications |= classify(us, ud)
321 }
322 return classifications != 0
323 })
324 })
325 if classifications == 0 {
326 panic(fmt.Sprintf("in %s: cannot convert %s (%s) to %s", f, val, val.Type(), typ))
327 }
328 329 // Conversion of a compile-time constant value?
330 if c, ok := val.(*Const); ok {
331 // Conversion to a basic type?
332 if isBasic(ut_dst) {
333 // Conversion of a compile-time constant to
334 // another constant type results in a new
335 // constant of the destination type and
336 // (initially) the same abstract value.
337 // We don't truncate the value yet.
338 return NewConst(c.Value, typ)
339 }
340 // Can we always convert from zero value without panicking?
341 const mayPanic = sliceToArray | sliceToArrayPtr
342 if c.Value == nil && classifications&mayPanic == 0 {
343 return NewConst(nil, typ)
344 }
345 346 // We're converting from constant to non-constant type,
347 // e.g. string -> []byte/[]rune.
348 }
349 350 switch classifications {
351 case changeType: // representation-preserving change
352 c := &ChangeType{X: val}
353 c.setType(typ)
354 return f.emit(c)
355 356 case sliceToArrayPtr, sliceTo0ArrayPtr: // slice to array pointer
357 c := &SliceToArrayPointer{X: val}
358 c.setType(typ)
359 return f.emit(c)
360 361 case sliceToArray: // slice to arrays (not zero-length)
362 ptype := types.NewPointer(typ)
363 p := &SliceToArrayPointer{X: val}
364 p.setType(ptype)
365 x := f.emit(p)
366 unOp := &UnOp{Op: token.MUL, X: x}
367 unOp.setType(typ)
368 return f.emit(unOp)
369 370 case sliceTo0Array: // slice to zero-length arrays (constant)
371 return zeroConst(typ)
372 373 case convert: // representation-changing conversion
374 c := &Convert{X: val}
375 c.setType(typ)
376 return f.emit(c)
377 378 default: // The conversion represents a cross product.
379 c := &MultiConvert{X: val, from: t_src, to: typ}
380 c.setType(typ)
381 return f.emit(c)
382 }
383 }
384 385 // emitTypeCoercion emits to f code to coerce the type of a
386 // Value v to exactly type typ, and returns the coerced value.
387 //
388 // Requires that coercing v.Typ() to typ is a value preserving change.
389 //
390 // Currently used only when v.Type() is a type instance of typ or vice versa.
391 // A type v is a type instance of a type t if there exists a
392 // type parameter substitution σ s.t. σ(v) == t. Example:
393 //
394 // σ(func(T) T) == func(int) int for σ == [T ↦ int]
395 //
396 // This happens in instantiation wrappers for conversion
397 // from an instantiation to a parameterized type (and vice versa)
398 // with σ substituting f.typeparams by f.typeargs.
399 func emitTypeCoercion(f *Function, v Value, typ types.Type) Value {
400 if types.Identical(v.Type(), typ) {
401 return v // no coercion needed
402 }
403 // TODO(taking): for instances should we record which side is the instance?
404 c := &ChangeType{
405 X: v,
406 }
407 c.setType(typ)
408 f.emit(c)
409 return c
410 }
411 412 // emitStore emits to f an instruction to store value val at location
413 // addr, applying implicit conversions as required by assignability rules.
414 func emitStore(f *Function, addr, val Value, pos token.Pos) *Store {
415 typ := typeparams.MustDeref(addr.Type())
416 s := &Store{
417 Addr: addr,
418 Val: emitConv(f, val, typ),
419 pos: pos,
420 }
421 f.emit(s)
422 return s
423 }
424 425 // emitJump emits to f a jump to target, and updates the control-flow graph.
426 // Postcondition: f.currentBlock is nil.
427 func emitJump(f *Function, target *BasicBlock) {
428 b := f.currentBlock
429 b.emit(new(Jump))
430 addEdge(b, target)
431 f.currentBlock = nil
432 }
433 434 // emitIf emits to f a conditional jump to tblock or fblock based on
435 // cond, and updates the control-flow graph.
436 // Postcondition: f.currentBlock is nil.
437 func emitIf(f *Function, cond Value, tblock, fblock *BasicBlock) {
438 b := f.currentBlock
439 b.emit(&If{Cond: cond})
440 addEdge(b, tblock)
441 addEdge(b, fblock)
442 f.currentBlock = nil
443 }
444 445 // emitExtract emits to f an instruction to extract the index'th
446 // component of tuple. It returns the extracted value.
447 func emitExtract(f *Function, tuple Value, index int) Value {
448 e := &Extract{Tuple: tuple, Index: index}
449 e.setType(tuple.Type().(*types.Tuple).At(index).Type())
450 return f.emit(e)
451 }
452 453 // emitTypeAssert emits to f a type assertion value := x.(t) and
454 // returns the value. x.Type() must be an interface.
455 func emitTypeAssert(f *Function, x Value, t types.Type, pos token.Pos) Value {
456 a := &TypeAssert{X: x, AssertedType: t}
457 a.setPos(pos)
458 a.setType(t)
459 return f.emit(a)
460 }
461 462 // emitTypeTest emits to f a type test value,ok := x.(t) and returns
463 // a (value, ok) tuple. x.Type() must be an interface.
464 func emitTypeTest(f *Function, x Value, t types.Type, pos token.Pos) Value {
465 a := &TypeAssert{
466 X: x,
467 AssertedType: t,
468 CommaOk: true,
469 }
470 a.setPos(pos)
471 a.setType(types.NewTuple(
472 newVar("value", t),
473 varOk,
474 ))
475 return f.emit(a)
476 }
477 478 // emitTailCall emits to f a function call in tail position. The
479 // caller is responsible for all fields of 'call' except its type.
480 // Intended for wrapper methods.
481 // Precondition: f does/will not use deferred procedure calls.
482 // Postcondition: f.currentBlock is nil.
483 func emitTailCall(f *Function, call *Call) {
484 tresults := f.Signature.Results()
485 nr := tresults.Len()
486 if nr == 1 {
487 call.typ = tresults.At(0).Type()
488 } else {
489 call.typ = tresults
490 }
491 tuple := emitCall(f, call)
492 var ret Return
493 switch nr {
494 case 0:
495 // no-op
496 case 1:
497 ret.Results = []Value{tuple}
498 default:
499 for i := range nr {
500 v := emitExtract(f, tuple, i)
501 // TODO(adonovan): in principle, this is required:
502 // v = emitConv(f, o.Type, f.Signature.Results[i].Type)
503 // but in practice emitTailCall is only used when
504 // the types exactly match.
505 ret.Results = append(ret.Results, v)
506 }
507 }
508 f.emit(&ret)
509 f.currentBlock = nil
510 }
511 512 // emitCall emits a call instruction. If the callee is "no return",
513 // it also emits a panic to eliminate infeasible CFG edges.
514 func emitCall(fn *Function, call *Call) Value {
515 res := fn.emit(call)
516 517 callee := call.Call.StaticCallee()
518 if callee != nil &&
519 callee.object != nil &&
520 fn.Prog.noReturn != nil &&
521 fn.Prog.noReturn(callee.object) {
522 // Call cannot return. Insert a panic after it.
523 fn.emit(&Panic{
524 X: emitConv(fn, vNoReturn, tEface),
525 pos: call.Pos(),
526 })
527 fn.currentBlock = fn.newBasicBlock("unreachable.noreturn")
528 }
529 530 return res
531 }
532 533 // emitImplicitSelections emits to f code to apply the sequence of
534 // implicit field selections specified by indices to base value v, and
535 // returns the selected value.
536 //
537 // If v is the address of a struct, the result will be the address of
538 // a field; if it is the value of a struct, the result will be the
539 // value of a field.
540 func emitImplicitSelections(f *Function, v Value, indices []int, pos token.Pos) Value {
541 for _, index := range indices {
542 if isPointerCore(v.Type()) {
543 fld := fieldOf(typeparams.MustDeref(v.Type()), index)
544 instr := &FieldAddr{
545 X: v,
546 Field: index,
547 }
548 instr.setPos(pos)
549 instr.setType(types.NewPointer(fld.Type()))
550 v = f.emit(instr)
551 // Load the field's value iff indirectly embedded.
552 if isPointerCore(fld.Type()) {
553 v = emitLoad(f, v)
554 }
555 } else {
556 fld := fieldOf(v.Type(), index)
557 instr := &Field{
558 X: v,
559 Field: index,
560 }
561 instr.setPos(pos)
562 instr.setType(fld.Type())
563 v = f.emit(instr)
564 }
565 }
566 return v
567 }
568 569 // emitFieldSelection emits to f code to select the index'th field of v.
570 //
571 // If wantAddr, the input must be a pointer-to-struct and the result
572 // will be the field's address; otherwise the result will be the
573 // field's value.
574 // Ident id is used for position and debug info.
575 func emitFieldSelection(f *Function, v Value, index int, wantAddr bool, id *ast.Ident) Value {
576 if isPointerCore(v.Type()) {
577 fld := fieldOf(typeparams.MustDeref(v.Type()), index)
578 instr := &FieldAddr{
579 X: v,
580 Field: index,
581 }
582 instr.setPos(id.Pos())
583 instr.setType(types.NewPointer(fld.Type()))
584 v = f.emit(instr)
585 // Load the field's value iff we don't want its address.
586 if !wantAddr {
587 v = emitLoad(f, v)
588 }
589 } else {
590 fld := fieldOf(v.Type(), index)
591 instr := &Field{
592 X: v,
593 Field: index,
594 }
595 instr.setPos(id.Pos())
596 instr.setType(fld.Type())
597 v = f.emit(instr)
598 }
599 emitDebugRef(f, id, v, wantAddr)
600 return v
601 }
602 603 // createRecoverBlock emits to f a block of code to return after a
604 // recovered panic, and sets f.Recover to it.
605 //
606 // If f's result parameters are named, the code loads and returns
607 // their current values, otherwise it returns the zero values of their
608 // type.
609 //
610 // Idempotent.
611 func createRecoverBlock(f *Function) {
612 if f.Recover != nil {
613 return // already created
614 }
615 saved := f.currentBlock
616 617 f.Recover = f.newBasicBlock("recover")
618 f.currentBlock = f.Recover
619 620 var results []Value
621 // Reload NRPs to form value tuple.
622 for _, nr := range f.results {
623 results = append(results, emitLoad(f, nr))
624 }
625 626 f.emit(&Return{Results: results})
627 628 f.currentBlock = saved
629 }
630