Debian Codegraph @

go/ir/emit.go

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