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