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 |
Members