Debian Codegraph @

go/ir/ssa.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 // This package defines a high-level intermediate representation for
8 // Go programs using static single-information (SSI) form.
9
10 import (
11 "fmt"
12 "go/ast"
13 "go/constant"
14 "go/token"
15 "go/types"
16 "math/big"
17 "sync"
18
19 "honnef.co/go/tools/go/types/typeutil"
20 )
21
22 const (
23 // Replace CompositeValue with only constant values with AggregateConst. Currently disabled because it breaks field
24 // tracking in U1000.
25 doSimplifyConstantCompositeValues = false
26 )
27
28 type ID int
29
30 // A Program is a partial or complete Go program converted to IR form.
31 type Program struct {
32 Fset *token.FileSet // position information for the files of this Program
33 PrintFunc string // create ir.html for function specified in PrintFunc
34 imported map[string]*Package // all importable Packages, keyed by import path
35 packages map[*types.Package]*Package // all loaded Packages, keyed by object
36 mode BuilderMode // set of mode bits for IR construction
37 MethodSets typeutil.MethodSetCache // cache of type-checker's method-sets
38
39 methodsMu sync.Mutex // guards the following maps:
40 methodSets typeutil.Map[*methodSet] // maps type to its concrete methodSet
41 runtimeTypes typeutil.Map[bool] // types for which rtypes are needed
42 canon typeutil.Map[types.Type] // type canonicalization map
43
44 noReturn func(*types.Func) bool
45 }
46
47 // A Package is a single analyzed Go package containing Members for
48 // all package-level functions, variables, constants and types it
49 // declares. These may be accessed directly via Members, or via the
50 // type-specific accessor methods Func, Type, Var and Const.
51 //
52 // Members also contains entries for "init" (the synthetic package
53 // initializer) and "init#%d", the nth declared init function,
54 // and unspecified other things too.
55 type Package struct {
56 Prog *Program // the owning program
57 Pkg *types.Package // the corresponding go/types.Package
58 Members map[string]Member // all package members keyed by name (incl. init and init#%d)
59 Functions []*Function // all functions, excluding anonymous ones
60 values map[types.Object]Value // package members (incl. types and methods), keyed by object
61 init *Function // Func("init"); the package's init function
62 debug bool // include full debug info in this package
63 printFunc string // which function to print in HTML form
64
65 // The following fields are set transiently, then cleared
66 // after building.
67 buildOnce sync.Once // ensures package building occurs once
68 ninit int32 // number of init functions
69 info *types.Info // package type information
70 files []*ast.File // package ASTs
71 initVersion map[ast.Expr]string // goversion to use for each global var init expr
72 }
73
74 // A Member is a member of a Go package, implemented by *NamedConst,
75 // *Global, *Function, or *Type; they are created by package-level
76 // const, var, func and type declarations respectively.
77 type Member interface {
78 Name() string // declared name of the package member
79 String() string // package-qualified name of the package member
80 RelString(*types.Package) string // like String, but relative refs are unqualified
81 Object() types.Object // typechecker's object for this member, if any
82 Type() types.Type // type of the package member
83 Token() token.Token // token.{VAR,FUNC,CONST,TYPE}
84 Package() *Package // the containing package
85 }
86
87 // A Type is a Member of a Package representing a package-level named type.
88 type Type struct {
89 object *types.TypeName
90 pkg *Package
91 }
92
93 // A NamedConst is a Member of a Package representing a package-level
94 // named constant.
95 //
96 // Pos() returns the position of the declaring ast.ValueSpec.Names[*]
97 // identifier.
98 //
99 // NB: a NamedConst is not a Value; it contains a constant Value, which
100 // it augments with the name and position of its 'const' declaration.
101 type NamedConst struct {
102 object *types.Const
103 Value *Const
104 pkg *Package
105 }
106
107 // A Value is an IR value that can be referenced by an instruction.
108 type Value interface {
109 setID(ID)
110
111 // Name returns the name of this value, and determines how
112 // this Value appears when used as an operand of an
113 // Instruction.
114 //
115 // This is the same as the source name for Parameters,
116 // Builtins, Functions, FreeVars, Globals.
117 // For constants, it is a representation of the constant's value
118 // and type. For all other Values this is the name of the
119 // virtual register defined by the instruction.
120 //
121 // The name of an IR Value is not semantically significant,
122 // and may not even be unique within a function.
123 Name() string
124
125 // ID returns the ID of this value. IDs are unique within a single
126 // function and are densely numbered, but may contain gaps.
127 // Values and other Instructions share the same ID space.
128 // Globally, values are identified by their addresses. However,
129 // IDs exist to facilitate efficient storage of mappings between
130 // values and data when analysing functions.
131 //
132 // NB: IDs are allocated late in the IR construction process and
133 // are not available to early stages of said process.
134 ID() ID
135
136 // If this value is an Instruction, String returns its
137 // disassembled form; otherwise it returns unspecified
138 // human-readable information about the Value, such as its
139 // kind, name and type.
140 String() string
141
142 // Type returns the type of this value. Many instructions
143 // (e.g. IndexAddr) change their behaviour depending on the
144 // types of their operands.
145 Type() types.Type
146
147 // Parent returns the function to which this Value belongs.
148 // It returns nil for named Functions, Builtin and Global.
149 Parent() *Function
150
151 // Referrers returns the list of instructions that have this
152 // value as one of their operands; it may contain duplicates
153 // if an instruction has a repeated operand.
154 //
155 // Referrers actually returns a pointer through which the
156 // caller may perform mutations to the object's state.
157 //
158 // Referrers is currently only defined if Parent()!=nil,
159 // i.e. for the function-local values FreeVar, Parameter,
160 // Functions (iff anonymous) and all value-defining instructions.
161 // It returns nil for named Functions, Builtin and Global.
162 //
163 // Instruction.Operands contains the inverse of this relation.
164 Referrers() *[]Instruction
165
166 Operands(rands []*Value) []*Value // nil for non-Instructions
167
168 // Source returns the AST node responsible for creating this
169 // value. A single AST node may be responsible for more than one
170 // value, and not all values have an associated AST node.
171 //
172 // Do not use this method to find a Value given an ast.Expr; use
173 // ValueForExpr instead.
174 Source() ast.Node
175
176 // Pos returns Source().Pos() if Source is not nil, else it
177 // returns token.NoPos.
178 Pos() token.Pos
179 }
180
181 // An Instruction is an IR instruction that computes a new Value or
182 // has some effect.
183 //
184 // An Instruction that defines a value (e.g. BinOp) also implements
185 // the Value interface; an Instruction that only has an effect (e.g. Store)
186 // does not.
187 type Instruction interface {
188 setSource(ast.Node)
189 setID(ID)
190
191 Comment() string
192
193 // String returns the disassembled form of this value.
194 //
195 // Examples of Instructions that are Values:
196 // "BinOp <int> {+} t1 t2" (BinOp)
197 // "Call <int> len t1" (Call)
198 // Note that the name of the Value is not printed.
199 //
200 // Examples of Instructions that are not Values:
201 // "Return t1" (Return)
202 // "Store {int} t2 t1" (Store)
203 //
204 // (The separation of Value.Name() from Value.String() is useful
205 // for some analyses which distinguish the operation from the
206 // value it defines, e.g., 'y = local int' is both an allocation
207 // of memory 'local int' and a definition of a pointer y.)
208 String() string
209
210 // ID returns the ID of this instruction. IDs are unique within a single
211 // function and are densely numbered, but may contain gaps.
212 // Globally, instructions are identified by their addresses. However,
213 // IDs exist to facilitate efficient storage of mappings between
214 // instructions and data when analysing functions.
215 //
216 // NB: IDs are allocated late in the IR construction process and
217 // are not available to early stages of said process.
218 ID() ID
219
220 // Parent returns the function to which this instruction
221 // belongs.
222 Parent() *Function
223
224 // Block returns the basic block to which this instruction
225 // belongs.
226 Block() *BasicBlock
227
228 // setBlock sets the basic block to which this instruction belongs.
229 setBlock(*BasicBlock)
230
231 // Operands returns the operands of this instruction: the
232 // set of Values it references.
233 //
234 // Specifically, it appends their addresses to rands, a
235 // user-provided slice, and returns the resulting slice,
236 // permitting avoidance of memory allocation.
237 //
238 // The operands are appended in undefined order, but the order
239 // is consistent for a given Instruction; the addresses are
240 // always non-nil but may point to a nil Value. Clients may
241 // store through the pointers, e.g. to effect a value
242 // renaming.
243 //
244 // Value.Referrers is a subset of the inverse of this
245 // relation. (Referrers are not tracked for all types of
246 // Values.)
247 Operands(rands []*Value) []*Value
248
249 Referrers() *[]Instruction // nil for non-Values
250
251 // Source returns the AST node responsible for creating this
252 // instruction. A single AST node may be responsible for more than
253 // one instruction, and not all instructions have an associated
254 // AST node.
255 Source() ast.Node
256
257 // Pos returns Source().Pos() if Source is not nil, else it
258 // returns token.NoPos.
259 Pos() token.Pos
260 }
261
262 // A Node is a node in the IR value graph. Every concrete type that
263 // implements Node is also either a Value, an Instruction, or both.
264 //
265 // Node contains the methods common to Value and Instruction, plus the
266 // Operands and Referrers methods generalized to return nil for
267 // non-Instructions and non-Values, respectively.
268 //
269 // Node is provided to simplify IR graph algorithms. Clients should
270 // use the more specific and informative Value or Instruction
271 // interfaces where appropriate.
272 type Node interface {
273 setID(ID)
274
275 // Common methods:
276 ID() ID
277 String() string
278 Source() ast.Node
279 Pos() token.Pos
280 Parent() *Function
281
282 // Partial methods:
283 Operands(rands []*Value) []*Value // nil for non-Instructions
284 Referrers() *[]Instruction // nil for non-Values
285 }
286
287 type Synthetic int
288
289 const (
290 SyntheticLoadedFromExportData Synthetic = iota + 1
291 SyntheticPackageInitializer
292 SyntheticThunk
293 SyntheticWrapper
294 SyntheticBound
295 SyntheticGeneric
296 SyntheticRangeOverFuncYield
297 )
298
299 func (syn Synthetic) String() string {
300 switch syn {
301 case SyntheticLoadedFromExportData:
302 return "loaded from export data"
303 case SyntheticPackageInitializer:
304 return "package initializer"
305 case SyntheticThunk:
306 return "thunk"
307 case SyntheticWrapper:
308 return "wrapper"
309 case SyntheticBound:
310 return "bound"
311 case SyntheticGeneric:
312 return "generic"
313 case SyntheticRangeOverFuncYield:
314 return "range-over-func yield"
315 default:
316 return fmt.Sprintf("Synthetic(%d)", syn)
317 }
318 }
319
320 // Function represents the parameters, results, and code of a function
321 // or method.
322 //
323 // If Blocks is nil, this indicates an external function for which no
324 // Go source code is available. In this case, FreeVars, Locals, and
325 // Params are nil too. Clients performing whole-program analysis must
326 // handle external functions specially.
327 //
328 // Blocks contains the function's control-flow graph (CFG).
329 // Blocks[0] is the function entry point; block order is not otherwise
330 // semantically significant, though it may affect the readability of
331 // the disassembly.
332 // To iterate over the blocks in dominance order, use DomPreorder().
333 //
334 // A nested function (Parent()!=nil) that refers to one or more
335 // lexically enclosing local variables ("free variables") has FreeVars.
336 // Such functions cannot be called directly but require a
337 // value created by MakeClosure which, via its Bindings, supplies
338 // values for these parameters.
339 //
340 // If the function is a method (Signature.Recv() != nil) then the first
341 // element of Params is the receiver parameter.
342 //
343 // A Go package may declare many functions called "init".
344 // For each one, Object().Name() returns "init" but Name() returns
345 // "init#1", etc, in declaration order.
346 //
347 // Pos() returns the declaring ast.FuncLit.Type.Func or the position
348 // of the ast.FuncDecl.Name, if the function was explicit in the
349 // source. Synthetic wrappers, for which Synthetic != "", may share
350 // the same position as the function they wrap.
351 // Syntax.Pos() always returns the position of the declaring "func" token.
352 //
353 // When the operand of a range statement is an iterator function,
354 // the loop body is transformed into a synthetic anonymous function
355 // that is passed as the yield argument in a call to the iterator.
356 // In that case, Function.Source() is the ast.RangeStmt.
357 //
358 // Synthetic functions, for which Synthetic != "", are functions
359 // that do not appear in the source AST. These include:
360 // - method wrappers,
361 // - thunks,
362 // - bound functions,
363 // - empty functions built from loaded type information,
364 // - yield functions created from range-over-func loops, and
365 // - package init functions.
366 //
367 // Type() returns the function's Signature.
368 type Function struct {
369 node
370
371 name string
372 object *types.Func // symbol for declared function (nil for FuncLit or synthetic init)
373 method *types.Selection // info about provenance of synthetic methods
374 Signature *types.Signature
375 generics instanceWrapperMap
376
377 Synthetic Synthetic // provenance of synthetic function; 0 for true source functions
378 parent *Function // enclosing function if anon; nil if global
379 Pkg *Package // enclosing package; nil for shared funcs (wrappers and error.Error)
380 Prog *Program // enclosing program
381
382 // These fields are populated only when the function body is built:
383
384 Params []*Parameter // function parameters; for methods, includes receiver
385 FreeVars []*FreeVar // free variables whose values must be supplied by closure
386 Locals []*Alloc // frame-allocated variables of this function
387 Blocks []*BasicBlock // basic blocks of the function; nil => external
388 Exit *BasicBlock // The function's exit block
389 AnonFuncs []*Function // anonymous functions (from FuncLit, RangeStmt) directly beneath this one
390 referrers []Instruction // referring instructions (iff Parent() != nil)
391
392 goversion string // Go version of syntax (NB: init is special)
393
394 // uniq is not stored in functionBody because we need it after function building finishes
395 uniq int64 // source of unique ints within the source tree while building
396
397 *functionBody
398 }
399
400 type instanceWrapperMap struct {
401 h typeutil.Hasher
402 entries map[uint32][]struct {
403 key *types.TypeList
404 val *Function
405 }
406 len int
407 }
408
409 func typeListIdentical(l1, l2 *types.TypeList) bool {
410 if l1.Len() != l2.Len() {
411 return false
412 }
413 for i := 0; i < l1.Len(); i++ {
414 t1 := l1.At(i)
415 t2 := l2.At(i)
416 if !types.Identical(t1, t2) {
417 return false
418 }
419 }
420 return true
421 }
422
423 func (m *instanceWrapperMap) At(key *types.TypeList) *Function {
424 if m.entries == nil {
425 m.entries = make(map[uint32][]struct {
426 key *types.TypeList
427 val *Function
428 })
429 m.h = typeutil.MakeHasher()
430 }
431
432 var hash uint32
433 for t := range key.Types() {
434 hash += m.h.Hash(t)
435 }
436
437 for _, e := range m.entries[hash] {
438 if typeListIdentical(e.key, key) {
439 return e.val
440 }
441 }
442 return nil
443 }
444
445 func (m *instanceWrapperMap) Set(key *types.TypeList, val *Function) {
446 if m.entries == nil {
447 m.entries = make(map[uint32][]struct {
448 key *types.TypeList
449 val *Function
450 })
451 m.h = typeutil.MakeHasher()
452 }
453
454 var hash uint32
455 for t := range key.Types() {
456 hash += m.h.Hash(t)
457 }
458 for i, e := range m.entries[hash] {
459 if typeListIdentical(e.key, key) {
460 m.entries[hash][i].val = val
461 return
462 }
463 }
464 m.entries[hash] = append(m.entries[hash], struct {
465 key *types.TypeList
466 val *Function
467 }{key, val})
468 m.len++
469 }
470
471 func (m *instanceWrapperMap) Len() int {
472 return m.len
473 }
474
475 type constValue struct {
476 c Constant
477 idx int
478 }
479
480 type functionBody struct {
481 // The following fields are set transiently during building,
482 // then cleared.
483 currentBlock *BasicBlock // where to emit code
484 vars map[*types.Var]Value // addresses of local variables
485 results []*Alloc // result allocations of the current function
486 returnVars []*types.Var // variables for a return statement. Either results or for range-over-func a parent's results
487 targets *targets // linked stack of branch targets
488 lblocks map[*types.Label]*lblock // labelled blocks
489 jump *types.Var // synthetic variable for the yield state (non-nil => range-over-func)
490 deferstack *types.Var // synthetic variable holding enclosing ssa:deferstack()
491 sourceFn *Function // nearest enclosing source function
492 exits []*exit // exits of the function that need to be resolved
493
494 consts map[constKey]constValue
495 aggregateConsts typeutil.Map[[]*AggregateConst]
496
497 wr *HTMLWriter
498 fakeExits BlockSet
499 blocksets [5]BlockSet
500 hasDefer bool
501
502 // a contiguous block of instructions that will be used by blocks,
503 // to avoid making multiple allocations.
504 scratchInstructions []Instruction
505 }
506
507 // BasicBlock represents an IR basic block.
508 //
509 // The final element of Instrs is always an explicit transfer of
510 // control (If, Jump, Return, Panic, or Unreachable).
511 //
512 // A block may contain no Instructions only if it is unreachable,
513 // i.e., Preds is nil. Empty blocks are typically pruned.
514 //
515 // BasicBlocks and their Preds/Succs relation form a (possibly cyclic)
516 // graph independent of the IR Value graph: the control-flow graph or
517 // CFG. It is illegal for multiple edges to exist between the same
518 // pair of blocks.
519 //
520 // Each BasicBlock is also a node in the dominator tree of the CFG.
521 // The tree may be navigated using Idom()/Dominees() and queried using
522 // Dominates().
523 //
524 // The order of Preds and Succs is significant (to Phi and If
525 // instructions, respectively).
526 type BasicBlock struct {
527 Index int // index of this block within Parent().Blocks
528 Comment string // optional label; no semantic significance
529 parent *Function // parent function
530 Instrs []Instruction // instructions in order
531 Preds, Succs []*BasicBlock // predecessors and successors
532 succs2 [2]*BasicBlock // initial space for Succs
533 dom domInfo // dominator tree info
534 pdom domInfo // post-dominator tree info
535 post int
536 gaps int // number of nil Instrs (transient)
537 rundefers int // number of rundefers (transient)
538 }
539
540 // Pure values ----------------------------------------
541
542 // A FreeVar represents a free variable of the function to which it
543 // belongs.
544 //
545 // FreeVars are used to implement anonymous functions, whose free
546 // variables are lexically captured in a closure formed by
547 // MakeClosure. The value of such a free var is an Alloc or another
548 // FreeVar and is considered a potentially escaping heap address, with
549 // pointer type.
550 //
551 // FreeVars are also used to implement bound method closures. Such a
552 // free var represents the receiver value and may be of any type that
553 // has concrete methods.
554 //
555 // Pos() returns the position of the value that was captured, which
556 // belongs to an enclosing function.
557 type FreeVar struct {
558 node
559
560 name string
561 typ types.Type
562 parent *Function
563 referrers []Instruction
564
565 // Transiently needed during building.
566 outer Value // the Value captured from the enclosing context.
567 }
568
569 // A Parameter represents an input parameter of a function.
570 type Parameter struct {
571 register
572
573 name string
574 object *types.Var // non-nil
575 }
576
577 // A Const represents the value of a constant expression.
578 //
579 // The underlying type of a constant may be any boolean, numeric, or
580 // string type. In addition, a Const may represent the nil value of
581 // any reference type---interface, map, channel, pointer, slice, or
582 // function---but not "untyped nil".
583 //
584 // All source-level constant expressions are represented by a Const
585 // of the same type and value.
586 //
587 // Value holds the exact value of the constant, independent of its
588 // Type(), using the same representation as package go/constant uses for
589 // constants, or nil for a typed nil value.
590 //
591 // Pos() returns token.NoPos.
592 //
593 // Example printed form:
594 //
595 // Const <int> {42}
596 // Const <untyped string> {"test"}
597 // Const <MyComplex> {(3 + 4i)}
598 type Const struct {
599 register
600
601 Value constant.Value
602 }
603
604 type AggregateConst struct {
605 register
606
607 Values []Value
608 }
609
610 type CompositeValue struct {
611 register
612
613 // Bitmap records which elements were explicitly provided. For example, [4]byte{2: x} would have a bitmap of 0010.
614 Bitmap big.Int
615 // The number of bits set in Bitmap
616 NumSet int
617 // Dense list of values in the composite literal. Omitted elements are filled in with zero values.
618 Values []Value
619 }
620
621 // TODO add the element's zero constant to ArrayConst
622 type ArrayConst struct {
623 register
624 }
625
626 type GenericConst struct {
627 register
628 }
629
630 type Constant interface {
631 Instruction
632 Value
633 aConstant()
634 RelString(*types.Package) string
635 equal(Constant) bool
636 setType(types.Type)
637 }
638
639 func (*Const) aConstant() {}
640 func (*AggregateConst) aConstant() {}
641 func (*ArrayConst) aConstant() {}
642 func (*GenericConst) aConstant() {}
643
644 // A Global is a named Value holding the address of a package-level
645 // variable.
646 //
647 // Pos() returns the position of the ast.ValueSpec.Names[*]
648 // identifier.
649 type Global struct {
650 node
651
652 name string
653 object types.Object // a *types.Var; may be nil for synthetics e.g. init$guard
654 typ types.Type
655
656 Pkg *Package
657 }
658
659 // A Builtin represents a specific use of a built-in function, e.g. len.
660 //
661 // Builtins are immutable values. Builtins do not have addresses.
662 // Builtins can only appear in CallCommon.Func.
663 //
664 // Name() indicates the function: one of the built-in functions from the
665 // Go spec (excluding "make" and "new") or one of these ir-defined
666 // intrinsics:
667 //
668 // // wrapnilchk returns ptr if non-nil, panics otherwise.
669 // // (For use in indirection wrappers.)
670 // func ir:wrapnilchk(ptr *T, recvType, methodName string) *T
671 //
672 // // noreturnWasPanic returns true if the previously called
673 // // function panicked, false if it exited the process.
674 // func ir:noreturnWasPanic() bool
675 //
676 // Object() returns a *types.Builtin for built-ins defined by the spec,
677 // nil for others.
678 //
679 // Type() returns a *types.Signature representing the effective
680 // signature of the built-in for this call.
681 type Builtin struct {
682 node
683
684 name string
685 sig *types.Signature
686 }
687
688 // Value-defining instructions ----------------------------------------
689
690 // The Alloc instruction reserves space for a variable of the given type,
691 // zero-initializes it, and yields its address.
692 //
693 // Alloc values are always addresses, and have pointer types, so the
694 // type of the allocated variable is actually
695 // Type().Underlying().(*types.Pointer).Elem().
696 //
697 // If Heap is false, Alloc zero-initializes the same local variable in
698 // the call frame and returns its address; in this case the Alloc must
699 // be present in Function.Locals. We call this a "local" alloc.
700 //
701 // If Heap is true, Alloc allocates a new zero-initialized variable
702 // each time the instruction is executed. We call this a "new" alloc.
703 //
704 // When Alloc is applied to a channel, map or slice type, it returns
705 // the address of an uninitialized (nil) reference of that kind; store
706 // the result of MakeSlice, MakeMap or MakeChan in that location to
707 // instantiate these types.
708 //
709 // Pos() returns the ast.CompositeLit.Lbrace for a composite literal,
710 // or the ast.CallExpr.Rparen for a call to new() or for a call that
711 // allocates a varargs slice.
712 //
713 // Example printed form:
714 //
715 // t1 = StackAlloc <*int>
716 // t2 = HeapAlloc <*int> (new)
717 type Alloc struct {
718 register
719 Heap bool
720 index int // dense numbering; for lifting
721 }
722
723 var _ Instruction = (*Sigma)(nil)
724 var _ Value = (*Sigma)(nil)
725
726 // The Sigma instruction represents an SSI σ-node, which splits values
727 // at branches in the control flow.
728 //
729 // Conceptually, σ-nodes exist at the end of blocks that branch and
730 // constitute parallel assignments to one value per destination block.
731 // However, such a representation would be awkward to work with, so
732 // instead we place σ-nodes at the beginning of branch targets. The
733 // From field denotes to which incoming edge the node applies.
734 //
735 // Within a block, all σ-nodes must appear before all non-σ nodes.
736 //
737 // Example printed form:
738 //
739 // t2 = Sigma <int> [#0] t1 (x)
740 type Sigma struct {
741 register
742 From *BasicBlock
743 X Value
744
745 live bool // used during lifting
746 }
747
748 type CopyInfo uint64
749
750 const (
751 CopyInfoUnspecified CopyInfo = 0
752 CopyInfoNotNil CopyInfo = 1 << iota
753 CopyInfoNotZeroLength
754 CopyInfoNotNegative
755 CopyInfoSingleConcreteType
756 CopyInfoClosed
757 )
758
759 type Copy struct {
760 register
761 X Value
762 Why Instruction
763 Info CopyInfo
764 }
765
766 // The Phi instruction represents an SSA φ-node, which combines values
767 // that differ across incoming control-flow edges and yields a new
768 // value. Within a block, all φ-nodes must appear before all non-φ, non-σ
769 // nodes.
770 //
771 // Pos() returns the position of the && or || for short-circuit
772 // control-flow joins, or that of the *Alloc for φ-nodes inserted
773 // during SSA renaming.
774 //
775 // Example printed form:
776 //
777 // t3 = Phi <int> 2:t1 4:t2 (x)
778 type Phi struct {
779 register
780 Edges []Value // Edges[i] is value for Block().Preds[i]
781
782 live bool // used during lifting
783 }
784
785 // The Call instruction represents a function or method call.
786 //
787 // The Call instruction yields the function result if there is exactly
788 // one. Otherwise it returns a tuple, the components of which are
789 // accessed via Extract.
790 //
791 // See CallCommon for generic function call documentation.
792 //
793 // Pos() returns the ast.CallExpr.Lparen, if explicit in the source.
794 //
795 // Example printed form:
796 //
797 // t3 = Call <()> println t1 t2
798 // t4 = Call <()> foo$1
799 // t6 = Invoke <string> t5.String
800 type Call struct {
801 register
802 Call CallCommon
803 }
804
805 // The BinOp instruction yields the result of binary operation X Op Y.
806 //
807 // Pos() returns the ast.BinaryExpr.OpPos, if explicit in the source.
808 //
809 // Example printed form:
810 //
811 // t3 = BinOp <int> {+} t2 t1
812 type BinOp struct {
813 register
814 // One of:
815 // ADD SUB MUL QUO REM + - * / %
816 // AND OR XOR SHL SHR AND_NOT & | ^ << >> &^
817 // EQL NEQ LSS LEQ GTR GEQ == != < <= < >=
818 Op token.Token
819 X, Y Value
820 }
821
822 // The UnOp instruction yields the result of Op X.
823 // XOR is bitwise complement.
824 // SUB is negation.
825 // NOT is logical negation.
826 //
827 // Example printed form:
828 //
829 // t2 = UnOp <int> {^} t1
830 type UnOp struct {
831 register
832 Op token.Token // One of: NOT SUB XOR ! - ^
833 X Value
834 }
835
836 // The Load instruction loads a value from a memory address.
837 //
838 // For implicit memory loads, Pos() returns the position of the
839 // most closely associated source-level construct; the details are not
840 // specified.
841 //
842 // Example printed form:
843 //
844 // t2 = Load <int> t1
845 type Load struct {
846 register
847 X Value
848 }
849
850 // The ChangeType instruction applies to X a value-preserving type
851 // change to Type().
852 //
853 // Type changes are permitted:
854 // - between a named type and its underlying type.
855 // - between two named types of the same underlying type.
856 // - between (possibly named) pointers to identical base types.
857 // - from a bidirectional channel to a read- or write-channel,
858 // optionally adding/removing a name.
859 //
860 // This operation cannot fail dynamically.
861 //
862 // Pos() returns the ast.CallExpr.Lparen, if the instruction arose
863 // from an explicit conversion in the source.
864 //
865 // Example printed form:
866 //
867 // t2 = ChangeType <*T> t1
868 type ChangeType struct {
869 register
870 X Value
871 }
872
873 // The Convert instruction yields the conversion of value X to type
874 // Type(). One or both of those types is basic (but possibly named).
875 //
876 // A conversion may change the value and representation of its operand.
877 // Conversions are permitted:
878 // - between real numeric types.
879 // - between complex numeric types.
880 // - between string and []byte or []rune.
881 // - between pointers and unsafe.Pointer.
882 // - between unsafe.Pointer and uintptr.
883 // - from (Unicode) integer to (UTF-8) string.
884 //
885 // A conversion may imply a type name change also.
886 //
887 // This operation cannot fail dynamically.
888 //
889 // Conversions of untyped string/number/bool constants to a specific
890 // representation are eliminated during IR construction.
891 //
892 // Pos() returns the ast.CallExpr.Lparen, if the instruction arose
893 // from an explicit conversion in the source.
894 //
895 // Example printed form:
896 //
897 // t2 = Convert <[]byte> t1
898 type Convert struct {
899 register
900 X Value
901 }
902
903 // The MultiConvert instruction yields the conversion of value X to type
904 // Type(). Either X.Type() or Type() must be a type parameter. Each
905 // type in the type set of X.Type() can be converted to each type in the
906 // type set of Type().
907 //
908 // See the documentation for Convert, ChangeType, SliceToArray, and SliceToArrayPointer
909 // for the conversions that are permitted.
910 //
911 // This operation can fail dynamically (see SliceToArrayPointer).
912 //
913 // Example printed form:
914 //
915 // t1 = multiconvert D <- S (t0) [*[2]rune <- []rune | string <- []rune]
916 type MultiConvert struct {
917 register
918 X Value
919 from typeutil.TypeSet
920 to typeutil.TypeSet
921 }
922
923 // ChangeInterface constructs a value of one interface type from a
924 // value of another interface type known to be assignable to it.
925 // This operation cannot fail.
926 //
927 // Pos() returns the ast.CallExpr.Lparen if the instruction arose from
928 // an explicit T(e) conversion; the ast.TypeAssertExpr.Lparen if the
929 // instruction arose from an explicit e.(T) operation; or token.NoPos
930 // otherwise.
931 //
932 // Example printed form:
933 //
934 // t2 = ChangeInterface <I1> t1
935 type ChangeInterface struct {
936 register
937 X Value
938 }
939
940 // The SliceToArrayPointer instruction yields the conversion of slice X to
941 // array pointer.
942 //
943 // Pos() returns the ast.CallExpr.Lparen, if the instruction arose
944 // from an explicit conversion in the source.
945 //
946 // Example printed form:
947 //
948 // t2 = SliceToArrayPointer <*[4]byte> t1
949 type SliceToArrayPointer struct {
950 register
951 X Value
952 }
953
954 // The SliceToArray instruction yields the conversion of slice X to
955 // array.
956 //
957 // Pos() returns the ast.CallExpr.Lparen, if the instruction arose
958 // from an explicit conversion in the source.
959 //
960 // Example printed form:
961 //
962 // t2 = SliceToArray <[4]byte> t1
963 type SliceToArray struct {
964 register
965 X Value
966 }
967
968 // MakeInterface constructs an instance of an interface type from a
969 // value of a concrete type.
970 //
971 // Use Program.MethodSets.MethodSet(X.Type()) to find the method-set
972 // of X, and Program.MethodValue(m) to find the implementation of a method.
973 //
974 // To construct the zero value of an interface type T, use:
975 //
976 // NewConst(constant.MakeNil(), T, pos)
977 //
978 // Pos() returns the ast.CallExpr.Lparen, if the instruction arose
979 // from an explicit conversion in the source.
980 //
981 // Example printed form:
982 //
983 // t2 = MakeInterface <interface{}> t1
984 type MakeInterface struct {
985 register
986 X Value
987 }
988
989 // The MakeClosure instruction yields a closure value whose code is
990 // Fn and whose free variables' values are supplied by Bindings.
991 //
992 // Type() returns a (possibly named) *types.Signature.
993 //
994 // Pos() returns the ast.FuncLit.Type.Func for a function literal
995 // closure or the ast.SelectorExpr.Sel for a bound method closure.
996 //
997 // Example printed form:
998 //
999 // t1 = MakeClosure <func()> foo$1 t1 t2
1000 // t5 = MakeClosure <func(int)> (T).foo$bound t4
1001 type MakeClosure struct {
1002 register
1003 Fn Value // always a *Function
1004 Bindings []Value // values for each free variable in Fn.FreeVars
1005 }
1006
1007 // The MakeMap instruction creates a new hash-table-based map object
1008 // and yields a value of kind map.
1009 //
1010 // Type() returns a (possibly named) *types.Map.
1011 //
1012 // Pos() returns the ast.CallExpr.Lparen, if created by make(map), or
1013 // the ast.CompositeLit.Lbrack if created by a literal.
1014 //
1015 // Example printed form:
1016 //
1017 // t1 = MakeMap <map[string]int>
1018 // t2 = MakeMap <StringIntMap> t1
1019 type MakeMap struct {
1020 register
1021 Reserve Value // initial space reservation; nil => default
1022 }
1023
1024 // The MakeChan instruction creates a new channel object and yields a
1025 // value of kind chan.
1026 //
1027 // Type() returns a (possibly named) *types.Chan.
1028 //
1029 // Pos() returns the ast.CallExpr.Lparen for the make(chan) that
1030 // created it.
1031 //
1032 // Example printed form:
1033 //
1034 // t3 = MakeChan <chan int> t1
1035 // t4 = MakeChan <chan IntChan> t2
1036 type MakeChan struct {
1037 register
1038 Size Value // int; size of buffer; zero => synchronous.
1039 }
1040
1041 // The MakeSlice instruction yields a slice of length Len backed by a
1042 // newly allocated array of length Cap.
1043 //
1044 // Both Len and Cap must be non-nil Values of integer type.
1045 //
1046 // (Alloc(types.Array) followed by Slice will not suffice because
1047 // Alloc can only create arrays of constant length.)
1048 //
1049 // Type() returns a (possibly named) *types.Slice.
1050 //
1051 // Pos() returns the ast.CallExpr.Lparen for the make([]T) that
1052 // created it.
1053 //
1054 // Example printed form:
1055 //
1056 // t3 = MakeSlice <[]string> t1 t2
1057 // t4 = MakeSlice <StringSlice> t1 t2
1058 type MakeSlice struct {
1059 register
1060 Len Value
1061 Cap Value
1062 }
1063
1064 // The Slice instruction yields a slice of an existing string, slice
1065 // or *array X between optional integer bounds Low and High.
1066 //
1067 // Dynamically, this instruction panics if X evaluates to a nil *array
1068 // pointer.
1069 //
1070 // Type() returns string if the type of X was string, otherwise a
1071 // *types.Slice with the same element type as X.
1072 //
1073 // Pos() returns the ast.SliceExpr.Lbrack if created by a x[:] slice
1074 // operation, the ast.CompositeLit.Lbrace if created by a literal, or
1075 // NoPos if not explicit in the source (e.g. a variadic argument slice).
1076 //
1077 // Example printed form:
1078 //
1079 // t4 = Slice <[]int> t3 t2 t1 <nil>
1080 type Slice struct {
1081 register
1082 X Value // slice, string, or *array
1083 Low, High, Max Value // each may be nil
1084 }
1085
1086 // The FieldAddr instruction yields the address of Field of *struct X.
1087 //
1088 // The field is identified by its index within the field list of the
1089 // struct type of X.
1090 //
1091 // Dynamically, this instruction panics if X evaluates to a nil
1092 // pointer.
1093 //
1094 // Type() returns a (possibly named) *types.Pointer.
1095 //
1096 // Pos() returns the position of the ast.SelectorExpr.Sel for the
1097 // field, if explicit in the source.
1098 //
1099 // Example printed form:
1100 //
1101 // t2 = FieldAddr <*int> [0] (X) t1
1102 type FieldAddr struct {
1103 register
1104 X Value // *struct
1105 Field int // field is X.Type().Underlying().(*types.Pointer).Elem().Underlying().(*types.Struct).Field(Field)
1106 }
1107
1108 // The Field instruction yields the Field of struct X.
1109 //
1110 // The field is identified by its index within the field list of the
1111 // struct type of X; by using numeric indices we avoid ambiguity of
1112 // package-local identifiers and permit compact representations.
1113 //
1114 // Pos() returns the position of the ast.SelectorExpr.Sel for the
1115 // field, if explicit in the source.
1116 //
1117 // Example printed form:
1118 //
1119 // t2 = FieldAddr <int> [0] (X) t1
1120 type Field struct {
1121 register
1122 X Value // struct
1123 Field int // index into X.Type().(*types.Struct).Fields
1124 }
1125
1126 // The IndexAddr instruction yields the address of the element at
1127 // index Index of collection X. Index is an integer expression.
1128 //
1129 // The elements of maps and strings are not addressable; use StringLookup, MapLookup or
1130 // MapUpdate instead.
1131 //
1132 // Dynamically, this instruction panics if X evaluates to a nil *array
1133 // pointer.
1134 //
1135 // Type() returns a (possibly named) *types.Pointer.
1136 //
1137 // Pos() returns the ast.IndexExpr.Lbrack for the index operation, if
1138 // explicit in the source.
1139 //
1140 // Example printed form:
1141 //
1142 // t3 = IndexAddr <*int> t2 t1
1143 type IndexAddr struct {
1144 register
1145 X Value // slice or *array,
1146 Index Value // numeric index
1147 }
1148
1149 // The Index instruction yields element Index of array X.
1150 //
1151 // Pos() returns the ast.IndexExpr.Lbrack for the index operation, if
1152 // explicit in the source.
1153 //
1154 // Example printed form:
1155 //
1156 // t3 = Index <int> t2 t1
1157 type Index struct {
1158 register
1159 X Value // array
1160 Index Value // integer index
1161 }
1162
1163 // The MapLookup instruction yields element Index of collection X, a map.
1164 //
1165 // If CommaOk, the result is a 2-tuple of the value above and a
1166 // boolean indicating the result of a map membership test for the key.
1167 // The components of the tuple are accessed using Extract.
1168 //
1169 // Pos() returns the ast.IndexExpr.Lbrack, if explicit in the source.
1170 //
1171 // Example printed form:
1172 //
1173 // t4 = MapLookup <string> t3 t1
1174 // t6 = MapLookup <(string, bool)> t3 t2
1175 type MapLookup struct {
1176 register
1177 X Value // map
1178 Index Value // key-typed index
1179 CommaOk bool // return a value,ok pair
1180 }
1181
1182 // The StringLookup instruction yields element Index of collection X, a string.
1183 // Index is an integer expression.
1184 //
1185 // Pos() returns the ast.IndexExpr.Lbrack, if explicit in the source.
1186 //
1187 // Example printed form:
1188 //
1189 // t3 = StringLookup <uint8> t2 t1
1190 type StringLookup struct {
1191 register
1192 X Value // string
1193 Index Value // numeric index
1194 }
1195
1196 // SelectState is a helper for Select.
1197 // It represents one goal state and its corresponding communication.
1198 type SelectState struct {
1199 Dir types.ChanDir // direction of case (SendOnly or RecvOnly)
1200 Chan Value // channel to use (for send or receive)
1201 Send Value // value to send (for send)
1202 Pos token.Pos // position of token.ARROW
1203 DebugNode ast.Node // ast.SendStmt or ast.UnaryExpr(<-) [debug mode]
1204 }
1205
1206 // The Select instruction tests whether (or blocks until) one
1207 // of the specified sent or received states is entered.
1208 //
1209 // Let n be the number of States for which Dir==RECV and Tᵢ (0 ≤ i < n)
1210 // be the element type of each such state's Chan.
1211 // Select returns an n+2-tuple
1212 //
1213 // (index int, recvOk bool, râ‚€ Tâ‚€, ... râ‚™-1 Tâ‚™-1)
1214 //
1215 // The tuple's components, described below, must be accessed via the
1216 // Extract instruction.
1217 //
1218 // If Blocking, select waits until exactly one state holds, i.e. a
1219 // channel becomes ready for the designated operation of sending or
1220 // receiving; select chooses one among the ready states
1221 // pseudorandomly, performs the send or receive operation, and sets
1222 // 'index' to the index of the chosen channel.
1223 //
1224 // If !Blocking, select doesn't block if no states hold; instead it
1225 // returns immediately with index equal to -1.
1226 //
1227 // If the chosen channel was used for a receive, the ráµ¢ component is
1228 // set to the received value, where i is the index of that state among
1229 // all n receive states; otherwise ráµ¢ has the zero value of type Táµ¢.
1230 // Note that the receive index i is not the same as the state
1231 // index index.
1232 //
1233 // The second component of the triple, recvOk, is a boolean whose value
1234 // is true iff the selected operation was a receive and the receive
1235 // successfully yielded a value.
1236 //
1237 // Pos() returns the ast.SelectStmt.Select.
1238 //
1239 // Example printed form:
1240 //
1241 // t6 = SelectNonBlocking <(index int, ok bool, int)> [<-t4, t5<-t1]
1242 // t11 = SelectBlocking <(index int, ok bool)> []
1243 type Select struct {
1244 register
1245 States []*SelectState
1246 Blocking bool
1247 }
1248
1249 // The Range instruction yields an iterator over the domain and range
1250 // of X, which must be a string or map.
1251 //
1252 // Elements are accessed via Next.
1253 //
1254 // Type() returns an opaque and degenerate "rangeIter" type.
1255 //
1256 // Pos() returns the ast.RangeStmt.For.
1257 //
1258 // Example printed form:
1259 //
1260 // t2 = Range <iter> t1
1261 type Range struct {
1262 register
1263 X Value // string or map
1264 }
1265
1266 // The Next instruction reads and advances the (map or string)
1267 // iterator Iter and returns a 3-tuple value (ok, k, v). If the
1268 // iterator is not exhausted, ok is true and k and v are the next
1269 // elements of the domain and range, respectively. Otherwise ok is
1270 // false and k and v are undefined.
1271 //
1272 // Components of the tuple are accessed using Extract.
1273 //
1274 // The IsString field distinguishes iterators over strings from those
1275 // over maps, as the Type() alone is insufficient: consider
1276 // map[int]rune.
1277 //
1278 // Type() returns a *types.Tuple for the triple (ok, k, v).
1279 // The types of k and/or v may be types.Invalid.
1280 //
1281 // Example printed form:
1282 //
1283 // t5 = Next <(ok bool, k int, v rune)> t2
1284 // t5 = Next <(ok bool, k invalid type, v invalid type)> t2
1285 type Next struct {
1286 register
1287 Iter Value
1288 IsString bool // true => string iterator; false => map iterator.
1289 }
1290
1291 // The TypeAssert instruction tests whether interface value X has type
1292 // AssertedType.
1293 //
1294 // If !CommaOk, on success it returns v, the result of the conversion
1295 // (defined below); on failure it panics.
1296 //
1297 // If CommaOk: on success it returns a pair (v, true) where v is the
1298 // result of the conversion; on failure it returns (z, false) where z
1299 // is AssertedType's zero value. The components of the pair must be
1300 // accessed using the Extract instruction.
1301 //
1302 // If AssertedType is a concrete type, TypeAssert checks whether the
1303 // dynamic type in interface X is equal to it, and if so, the result
1304 // of the conversion is a copy of the value in the interface.
1305 //
1306 // If AssertedType is an interface, TypeAssert checks whether the
1307 // dynamic type of the interface is assignable to it, and if so, the
1308 // result of the conversion is a copy of the interface value X.
1309 // If AssertedType is a superinterface of X.Type(), the operation will
1310 // fail iff the operand is nil. (Contrast with ChangeInterface, which
1311 // performs no nil-check.)
1312 //
1313 // Type() reflects the actual type of the result, possibly a
1314 // 2-types.Tuple; AssertedType is the asserted type.
1315 //
1316 // Pos() returns the ast.CallExpr.Lparen if the instruction arose from
1317 // an explicit T(e) conversion; the ast.TypeAssertExpr.Lparen if the
1318 // instruction arose from an explicit e.(T) operation; or the
1319 // ast.CaseClause.Case if the instruction arose from a case of a
1320 // type-switch statement.
1321 //
1322 // Example printed form:
1323 //
1324 // t2 = TypeAssert <int> t1
1325 // t4 = TypeAssert <(value fmt.Stringer, ok bool)> t1
1326 type TypeAssert struct {
1327 register
1328 X Value
1329 AssertedType types.Type
1330 CommaOk bool
1331 }
1332
1333 // The Extract instruction yields component Index of Tuple.
1334 //
1335 // This is used to access the results of instructions with multiple
1336 // return values, such as Call, TypeAssert, Next, Recv,
1337 // MapLookup and others.
1338 //
1339 // Example printed form:
1340 //
1341 // t7 = Extract <bool> [1] (ok) t4
1342 type Extract struct {
1343 register
1344 Tuple Value
1345 Index int
1346 }
1347
1348 // Instructions executed for effect. They do not yield a value. --------------------
1349
1350 // The Jump instruction transfers control to the sole successor of its
1351 // owning block.
1352 //
1353 // A Jump must be the last instruction of its containing BasicBlock.
1354 //
1355 // Pos() returns NoPos.
1356 //
1357 // Example printed form:
1358 //
1359 // Jump → b1
1360 type Jump struct {
1361 anInstruction
1362 }
1363
1364 // The Unreachable pseudo-instruction signals that execution cannot
1365 // continue after the preceding function call because it terminates
1366 // the process.
1367 //
1368 // The instruction acts as a control instruction, jumping to the exit
1369 // block. However, this jump will never execute.
1370 //
1371 // An Unreachable instruction must be the last instruction of its
1372 // containing BasicBlock.
1373 //
1374 // Example printed form:
1375 //
1376 // Unreachable → b1
1377 type Unreachable struct {
1378 anInstruction
1379 }
1380
1381 // The If instruction transfers control to one of the two successors
1382 // of its owning block, depending on the boolean Cond: the first if
1383 // true, the second if false.
1384 //
1385 // An If instruction must be the last instruction of its containing
1386 // BasicBlock.
1387 //
1388 // Pos() returns the *ast.IfStmt, if explicit in the source.
1389 //
1390 // Example printed form:
1391 //
1392 // If t2 → b1 b2
1393 type If struct {
1394 anInstruction
1395 Cond Value
1396 }
1397
1398 type ConstantSwitch struct {
1399 anInstruction
1400 Tag Value
1401 // Constant branch conditions. A nil Value denotes the (implicit
1402 // or explicit) default branch.
1403 Conds []Value
1404 }
1405
1406 type TypeSwitch struct {
1407 register
1408 Tag Value
1409 Conds []types.Type
1410 }
1411
1412 // The Return instruction returns values and control back to the calling
1413 // function.
1414 //
1415 // len(Results) is always equal to the number of results in the
1416 // function's signature.
1417 //
1418 // If len(Results) > 1, Return returns a tuple value with the specified
1419 // components which the caller must access using Extract instructions.
1420 //
1421 // There is no instruction to return a ready-made tuple like those
1422 // returned by a "value,ok"-mode TypeAssert, MapLookup or Recv or
1423 // a tail-call to a function with multiple result parameters.
1424 //
1425 // Return must be the last instruction of its containing BasicBlock.
1426 // Such a block has no successors.
1427 //
1428 // Pos() returns the ast.ReturnStmt.Return, if explicit in the source.
1429 //
1430 // Example printed form:
1431 //
1432 // Return
1433 // Return t1 t2
1434 type Return struct {
1435 anInstruction
1436 Results []Value
1437 }
1438
1439 // The RunDefers instruction pops and invokes the entire stack of
1440 // procedure calls pushed by Defer instructions in this function.
1441 //
1442 // It is legal to encounter multiple 'rundefers' instructions in a
1443 // single control-flow path through a function; this is useful in
1444 // the combined init() function, for example.
1445 //
1446 // Pos() returns NoPos.
1447 //
1448 // Example printed form:
1449 //
1450 // RunDefers
1451 type RunDefers struct {
1452 anInstruction
1453 }
1454
1455 // The Panic instruction initiates a panic with value X.
1456 //
1457 // A Panic instruction must be the last instruction of its containing
1458 // BasicBlock, which must have one successor, the exit block.
1459 //
1460 // NB: 'go panic(x)' and 'defer panic(x)' do not use this instruction;
1461 // they are treated as calls to a built-in function.
1462 //
1463 // Pos() returns the ast.CallExpr.Lparen if this panic was explicit
1464 // in the source.
1465 //
1466 // Example printed form:
1467 //
1468 // Panic t1
1469 type Panic struct {
1470 anInstruction
1471 X Value // an interface{}
1472 }
1473
1474 // The Go instruction creates a new goroutine and calls the specified
1475 // function within it.
1476 //
1477 // See CallCommon for generic function call documentation.
1478 //
1479 // Pos() returns the ast.GoStmt.Go.
1480 //
1481 // Example printed form:
1482 //
1483 // Go println t1
1484 // Go t3
1485 // GoInvoke t4.Bar t2
1486 type Go struct {
1487 anInstruction
1488 Call CallCommon
1489 }
1490
1491 // The Defer instruction pushes the specified call onto a stack of
1492 // functions to be called by a RunDefers instruction or by a panic.
1493 //
1494 // If _DeferStack != nil, it indicates the defer list that the defer is
1495 // added to. Defer list values come from the Builtin function
1496 // ssa:deferstack. Calls to ssa:deferstack() produces the defer stack
1497 // of the current function frame. _DeferStack allows for deferring into an
1498 // alternative function stack than the current function.
1499 //
1500 // See CallCommon for generic function call documentation.
1501 //
1502 // Pos() returns the ast.DeferStmt.Defer.
1503 //
1504 // Example printed form:
1505 //
1506 // Defer println t1
1507 // Defer t3
1508 // DeferInvoke t4.Bar t2
1509 type Defer struct {
1510 anInstruction
1511 Call CallCommon
1512 _DeferStack Value // stack (from ssa:deferstack() intrinsic) onto which this function is pushed
1513
1514 // TODO: Exporting _DeferStack and possibly making _DeferStack != nil awaits proposal https://github.com/golang/go/issues/66601.
1515 }
1516
1517 // The Send instruction sends X on channel Chan.
1518 //
1519 // Pos() returns the ast.SendStmt.Arrow, if explicit in the source.
1520 //
1521 // Example printed form:
1522 //
1523 // Send t2 t1
1524 type Send struct {
1525 anInstruction
1526 Chan, X Value
1527 }
1528
1529 // The Recv instruction receives from channel Chan.
1530 //
1531 // If CommaOk, the result is a 2-tuple of the value above
1532 // and a boolean indicating the success of the receive. The
1533 // components of the tuple are accessed using Extract.
1534 //
1535 // Pos() returns the ast.UnaryExpr.OpPos, if explicit in the source.
1536 // For receive operations implicit in ranging over a channel,
1537 // Pos() returns the ast.RangeStmt.For.
1538 //
1539 // Example printed form:
1540 //
1541 // t2 = Recv <int> t1
1542 // t3 = Recv <(int, bool)> t1
1543 type Recv struct {
1544 register
1545 Chan Value
1546 CommaOk bool
1547 }
1548
1549 // The Store instruction stores Val at address Addr.
1550 // Stores can be of arbitrary types.
1551 //
1552 // Pos() returns the position of the source-level construct most closely
1553 // associated with the memory store operation.
1554 // Since implicit memory stores are numerous and varied and depend upon
1555 // implementation choices, the details are not specified.
1556 //
1557 // Example printed form:
1558 //
1559 // Store {int} t2 t1
1560 type Store struct {
1561 anInstruction
1562 Addr Value
1563 Val Value
1564 }
1565
1566 // The BlankStore instruction is emitted for assignments to the blank
1567 // identifier.
1568 //
1569 // BlankStore is a pseudo-instruction: it has no dynamic effect.
1570 //
1571 // Pos() returns NoPos.
1572 //
1573 // Example printed form:
1574 //
1575 // BlankStore t1
1576 type BlankStore struct {
1577 anInstruction
1578 Val Value
1579 }
1580
1581 // The MapUpdate instruction updates the association of Map[Key] to
1582 // Value.
1583 //
1584 // Pos() returns the ast.KeyValueExpr.Colon or ast.IndexExpr.Lbrack,
1585 // if explicit in the source.
1586 //
1587 // Example printed form:
1588 //
1589 // MapUpdate t3 t1 t2
1590 type MapUpdate struct {
1591 anInstruction
1592 Map Value
1593 Key Value
1594 Value Value
1595 }
1596
1597 // A DebugRef instruction maps a source-level expression Expr to the
1598 // IR value X that represents the value (!IsAddr) or address (IsAddr)
1599 // of that expression.
1600 //
1601 // DebugRef is a pseudo-instruction: it has no dynamic effect.
1602 //
1603 // Pos() returns Expr.Pos(), the start position of the source-level
1604 // expression. This is not the same as the "designated" token as
1605 // documented at Value.Pos(). e.g. CallExpr.Pos() does not return the
1606 // position of the ("designated") Lparen token.
1607 //
1608 // DebugRefs are generated only for functions built with debugging
1609 // enabled; see Package.SetDebugMode() and the GlobalDebug builder
1610 // mode flag.
1611 //
1612 // DebugRefs are not emitted for ast.Idents referring to constants or
1613 // predeclared identifiers, since they are trivial and numerous.
1614 // Nor are they emitted for ast.ParenExprs.
1615 //
1616 // (By representing these as instructions, rather than out-of-band,
1617 // consistency is maintained during transformation passes by the
1618 // ordinary SSA renaming machinery.)
1619 //
1620 // Example printed form:
1621 //
1622 // ; *ast.CallExpr @ 102:9 is t5
1623 // ; var x float64 @ 109:72 is x
1624 // ; address of *ast.CompositeLit @ 216:10 is t0
1625 type DebugRef struct {
1626 anInstruction
1627 Expr ast.Expr // the referring expression (never *ast.ParenExpr)
1628 object types.Object // the identity of the source var/func
1629 IsAddr bool // Expr is addressable and X is the address it denotes
1630 X Value // the value or address of Expr
1631 }
1632
1633 // Embeddable mix-ins and helpers for common parts of other structs. -----------
1634
1635 // register is a mix-in embedded by all IR values that are also
1636 // instructions, i.e. virtual registers, and provides a uniform
1637 // implementation of most of the Value interface: Value.Name() is a
1638 // numbered register (e.g. "t0"); the other methods are field accessors.
1639 //
1640 // Temporary names are automatically assigned to each register on
1641 // completion of building a function in IR form.
1642 type register struct {
1643 anInstruction
1644 typ types.Type // type of virtual register
1645 referrers []Instruction
1646 }
1647
1648 type node struct {
1649 source ast.Node
1650 id ID
1651 }
1652
1653 func (n *node) setID(id ID) { n.id = id }
1654 func (n node) ID() ID { return n.id }
1655
1656 func (n *node) setSource(source ast.Node) { n.source = source }
1657 func (n *node) Source() ast.Node { return n.source }
1658
1659 func (n *node) Pos() token.Pos {
1660 if n.source != nil {
1661 return n.source.Pos()
1662 }
1663 return token.NoPos
1664 }
1665
1666 // anInstruction is a mix-in embedded by all Instructions.
1667 // It provides the implementations of the Block and setBlock methods.
1668 type anInstruction struct {
1669 node
1670 block *BasicBlock // the basic block of this instruction
1671 comment string
1672 }
1673
1674 func (instr anInstruction) Comment() string {
1675 return instr.comment
1676 }
1677
1678 // CallCommon is contained by Go, Defer and Call to hold the
1679 // common parts of a function or method call.
1680 //
1681 // Each CallCommon exists in one of two modes, function call and
1682 // interface method invocation, or "call" and "invoke" for short.
1683 //
1684 // 1. "call" mode: when Method is nil (!IsInvoke), a CallCommon
1685 // represents an ordinary function call of the value in Value,
1686 // which may be a *Builtin, a *Function or any other value of kind
1687 // 'func'.
1688 //
1689 // Value may be one of:
1690 //
1691 // (a) a *Function, indicating a statically dispatched call
1692 // to a package-level function, an anonymous function, or
1693 // a method of a named type.
1694 // (b) a *MakeClosure, indicating an immediately applied
1695 // function literal with free variables.
1696 // (c) a *Builtin, indicating a statically dispatched call
1697 // to a built-in function.
1698 // (d) any other value, indicating a dynamically dispatched
1699 // function call.
1700 //
1701 // StaticCallee returns the identity of the callee in cases
1702 // (a) and (b), nil otherwise.
1703 //
1704 // Args contains the arguments to the call. If Value is a method,
1705 // Args[0] contains the receiver parameter.
1706 //
1707 // Example printed form:
1708 //
1709 // t3 = Call <()> println t1 t2
1710 // Go t3
1711 // Defer t3
1712 //
1713 // 2. "invoke" mode: when Method is non-nil (IsInvoke), a CallCommon
1714 // represents a dynamically dispatched call to an interface method.
1715 // In this mode, Value is the interface value and Method is the
1716 // interface's abstract method. Note: an abstract method may be
1717 // shared by multiple interfaces due to embedding; Value.Type()
1718 // provides the specific interface used for this call.
1719 //
1720 // Value is implicitly supplied to the concrete method implementation
1721 // as the receiver parameter; in other words, Args[0] holds not the
1722 // receiver but the first true argument.
1723 //
1724 // Example printed form:
1725 //
1726 // t6 = Invoke <string> t5.String
1727 // GoInvoke t4.Bar t2
1728 // DeferInvoke t4.Bar t2
1729 //
1730 // For all calls to variadic functions (Signature().Variadic()),
1731 // the last element of Args is a slice.
1732 type CallCommon struct {
1733 Value Value // receiver (invoke mode) or func value (call mode)
1734 Method *types.Func // abstract method (invoke mode)
1735 Args []Value // actual parameters (in static method call, includes receiver)
1736 TypeArgs []types.Type
1737 Results Value
1738 }
1739
1740 // IsInvoke returns true if this call has "invoke" (not "call") mode.
1741 func (c *CallCommon) IsInvoke() bool {
1742 return c.Method != nil
1743 }
1744
1745 // Signature returns the signature of the called function.
1746 //
1747 // For an "invoke"-mode call, the signature of the interface method is
1748 // returned.
1749 //
1750 // In either "call" or "invoke" mode, if the callee is a method, its
1751 // receiver is represented by sig.Recv, not sig.Params().At(0).
1752 func (c *CallCommon) Signature() *types.Signature {
1753 if c.Method != nil {
1754 return c.Method.Type().(*types.Signature)
1755 }
1756 return typeutil.CoreType(c.Value.Type()).(*types.Signature)
1757 }
1758
1759 // StaticCallee returns the callee if this is a trivially static
1760 // "call"-mode call to a function.
1761 func (c *CallCommon) StaticCallee() *Function {
1762 switch fn := c.Value.(type) {
1763 case *Function:
1764 return fn
1765 case *MakeClosure:
1766 return fn.Fn.(*Function)
1767 }
1768 return nil
1769 }
1770
1771 // Description returns a description of the mode of this call suitable
1772 // for a user interface, e.g., "static method call".
1773 func (c *CallCommon) Description() string {
1774 switch fn := c.Value.(type) {
1775 case *Builtin:
1776 return "built-in function call"
1777 case *MakeClosure:
1778 return "static function closure call"
1779 case *Function:
1780 if fn.Signature.Recv() != nil {
1781 return "static method call"
1782 }
1783 return "static function call"
1784 }
1785 if c.IsInvoke() {
1786 return "dynamic method call" // ("invoke" mode)
1787 }
1788 return "dynamic function call"
1789 }
1790
1791 // The CallInstruction interface, implemented by *Go, *Defer and *Call,
1792 // exposes the common parts of function-calling instructions,
1793 // yet provides a way back to the Value defined by *Call alone.
1794 type CallInstruction interface {
1795 Instruction
1796 Common() *CallCommon // returns the common parts of the call
1797 Value() *Call
1798 }
1799
1800 func (s *Call) Common() *CallCommon { return &s.Call }
1801 func (s *Defer) Common() *CallCommon { return &s.Call }
1802 func (s *Go) Common() *CallCommon { return &s.Call }
1803
1804 func (s *Call) Value() *Call { return s }
1805 func (s *Defer) Value() *Call { return nil }
1806 func (s *Go) Value() *Call { return nil }
1807
1808 func (v *Builtin) Type() types.Type { return v.sig }
1809 func (v *Builtin) Name() string { return v.name }
1810 func (*Builtin) Referrers() *[]Instruction { return nil }
1811 func (v *Builtin) Pos() token.Pos { return token.NoPos }
1812 func (v *Builtin) Object() types.Object { return types.Universe.Lookup(v.name) }
1813 func (v *Builtin) Parent() *Function { return nil }
1814
1815 func (v *FreeVar) Type() types.Type { return v.typ }
1816 func (v *FreeVar) Name() string { return v.name }
1817 func (v *FreeVar) Referrers() *[]Instruction { return &v.referrers }
1818 func (v *FreeVar) Parent() *Function { return v.parent }
1819
1820 func (v *Global) Type() types.Type { return v.typ }
1821 func (v *Global) Name() string { return v.name }
1822 func (v *Global) Parent() *Function { return nil }
1823 func (v *Global) Referrers() *[]Instruction { return nil }
1824 func (v *Global) Token() token.Token { return token.VAR }
1825 func (v *Global) Object() types.Object { return v.object }
1826 func (v *Global) String() string { return v.RelString(nil) }
1827 func (v *Global) Package() *Package { return v.Pkg }
1828 func (v *Global) RelString(from *types.Package) string { return relString(v, from) }
1829
1830 func (v *Function) Name() string { return v.name }
1831 func (v *Function) Type() types.Type { return v.Signature }
1832 func (v *Function) Token() token.Token { return token.FUNC }
1833 func (v *Function) Object() types.Object {
1834 if v.object != nil {
1835 return types.Object(v.object)
1836 }
1837 return nil
1838 }
1839 func (v *Function) String() string { return v.RelString(nil) }
1840 func (v *Function) Package() *Package { return v.Pkg }
1841 func (v *Function) Parent() *Function { return v.parent }
1842 func (v *Function) Referrers() *[]Instruction {
1843 if v.parent != nil {
1844 return &v.referrers
1845 }
1846 return nil
1847 }
1848
1849 func (v *Parameter) Object() types.Object { return v.object }
1850
1851 func (v *Alloc) Type() types.Type { return v.typ }
1852 func (v *Alloc) Referrers() *[]Instruction { return &v.referrers }
1853
1854 func (v *register) Type() types.Type { return v.typ }
1855 func (v *register) setType(typ types.Type) { v.typ = typ }
1856 func (v *register) Name() string { return fmt.Sprintf("t%d", v.id) }
1857 func (v *register) Referrers() *[]Instruction { return &v.referrers }
1858
1859 func (v *anInstruction) Parent() *Function { return v.block.parent }
1860 func (v *anInstruction) Block() *BasicBlock { return v.block }
1861 func (v *anInstruction) setBlock(block *BasicBlock) { v.block = block }
1862 func (v *anInstruction) Referrers() *[]Instruction { return nil }
1863
1864 func (t *Type) Name() string { return t.object.Name() }
1865 func (t *Type) Pos() token.Pos { return t.object.Pos() }
1866 func (t *Type) Type() types.Type { return t.object.Type() }
1867 func (t *Type) Token() token.Token { return token.TYPE }
1868 func (t *Type) Object() types.Object { return t.object }
1869 func (t *Type) String() string { return t.RelString(nil) }
1870 func (t *Type) Package() *Package { return t.pkg }
1871 func (t *Type) RelString(from *types.Package) string { return relString(t, from) }
1872
1873 func (c *NamedConst) Name() string { return c.object.Name() }
1874 func (c *NamedConst) Pos() token.Pos { return c.object.Pos() }
1875 func (c *NamedConst) String() string { return c.RelString(nil) }
1876 func (c *NamedConst) Type() types.Type { return c.object.Type() }
1877 func (c *NamedConst) Token() token.Token { return token.CONST }
1878 func (c *NamedConst) Object() types.Object { return c.object }
1879 func (c *NamedConst) Package() *Package { return c.pkg }
1880 func (c *NamedConst) RelString(from *types.Package) string { return relString(c, from) }
1881
1882 // Func returns the package-level function of the specified name,
1883 // or nil if not found.
1884 func (p *Package) Func(name string) (f *Function) {
1885 f, _ = p.Members[name].(*Function)
1886 return
1887 }
1888
1889 // Var returns the package-level variable of the specified name,
1890 // or nil if not found.
1891 func (p *Package) Var(name string) (g *Global) {
1892 g, _ = p.Members[name].(*Global)
1893 return
1894 }
1895
1896 // Const returns the package-level constant of the specified name,
1897 // or nil if not found.
1898 func (p *Package) Const(name string) (c *NamedConst) {
1899 c, _ = p.Members[name].(*NamedConst)
1900 return
1901 }
1902
1903 // Type returns the package-level type of the specified name,
1904 // or nil if not found.
1905 func (p *Package) Type(name string) (t *Type) {
1906 t, _ = p.Members[name].(*Type)
1907 return
1908 }
1909
1910 func (s *DebugRef) Pos() token.Pos { return s.Expr.Pos() }
1911
1912 // Operands.
1913
1914 func (v *Alloc) Operands(rands []*Value) []*Value {
1915 return rands
1916 }
1917
1918 func (v *BinOp) Operands(rands []*Value) []*Value {
1919 return append(rands, &v.X, &v.Y)
1920 }
1921
1922 func (c *CallCommon) Operands(rands []*Value) []*Value {
1923 rands = append(rands, &c.Value)
1924 for i := range c.Args {
1925 rands = append(rands, &c.Args[i])
1926 }
1927 return rands
1928 }
1929
1930 func (s *Go) Operands(rands []*Value) []*Value {
1931 return s.Call.Operands(rands)
1932 }
1933
1934 func (s *Call) Operands(rands []*Value) []*Value {
1935 return s.Call.Operands(rands)
1936 }
1937
1938 func (s *Defer) Operands(rands []*Value) []*Value {
1939 return append(s.Call.Operands(rands), &s._DeferStack)
1940 }
1941
1942 func (v *ChangeInterface) Operands(rands []*Value) []*Value {
1943 return append(rands, &v.X)
1944 }
1945
1946 func (v *ChangeType) Operands(rands []*Value) []*Value {
1947 return append(rands, &v.X)
1948 }
1949
1950 func (v *Convert) Operands(rands []*Value) []*Value {
1951 return append(rands, &v.X)
1952 }
1953
1954 func (v *MultiConvert) Operands(rands []*Value) []*Value {
1955 return append(rands, &v.X)
1956 }
1957
1958 func (v *SliceToArrayPointer) Operands(rands []*Value) []*Value {
1959 return append(rands, &v.X)
1960 }
1961
1962 func (v *SliceToArray) Operands(rands []*Value) []*Value {
1963 return append(rands, &v.X)
1964 }
1965
1966 func (s *DebugRef) Operands(rands []*Value) []*Value {
1967 return append(rands, &s.X)
1968 }
1969
1970 func (s *Copy) Operands(rands []*Value) []*Value {
1971 return append(rands, &s.X)
1972 }
1973
1974 func (v *Extract) Operands(rands []*Value) []*Value {
1975 return append(rands, &v.Tuple)
1976 }
1977
1978 func (v *Field) Operands(rands []*Value) []*Value {
1979 return append(rands, &v.X)
1980 }
1981
1982 func (v *FieldAddr) Operands(rands []*Value) []*Value {
1983 return append(rands, &v.X)
1984 }
1985
1986 func (s *If) Operands(rands []*Value) []*Value {
1987 return append(rands, &s.Cond)
1988 }
1989
1990 func (s *ConstantSwitch) Operands(rands []*Value) []*Value {
1991 rands = append(rands, &s.Tag)
1992 for i := range s.Conds {
1993 rands = append(rands, &s.Conds[i])
1994 }
1995 return rands
1996 }
1997
1998 func (s *TypeSwitch) Operands(rands []*Value) []*Value {
1999 rands = append(rands, &s.Tag)
2000 return rands
2001 }
2002
2003 func (v *Index) Operands(rands []*Value) []*Value {
2004 return append(rands, &v.X, &v.Index)
2005 }
2006
2007 func (v *IndexAddr) Operands(rands []*Value) []*Value {
2008 return append(rands, &v.X, &v.Index)
2009 }
2010
2011 func (*Jump) Operands(rands []*Value) []*Value {
2012 return rands
2013 }
2014
2015 func (*Unreachable) Operands(rands []*Value) []*Value {
2016 return rands
2017 }
2018
2019 func (v *MapLookup) Operands(rands []*Value) []*Value {
2020 return append(rands, &v.X, &v.Index)
2021 }
2022
2023 func (v *StringLookup) Operands(rands []*Value) []*Value {
2024 return append(rands, &v.X, &v.Index)
2025 }
2026
2027 func (v *MakeChan) Operands(rands []*Value) []*Value {
2028 return append(rands, &v.Size)
2029 }
2030
2031 func (v *MakeClosure) Operands(rands []*Value) []*Value {
2032 rands = append(rands, &v.Fn)
2033 for i := range v.Bindings {
2034 rands = append(rands, &v.Bindings[i])
2035 }
2036 return rands
2037 }
2038
2039 func (v *MakeInterface) Operands(rands []*Value) []*Value {
2040 return append(rands, &v.X)
2041 }
2042
2043 func (v *MakeMap) Operands(rands []*Value) []*Value {
2044 return append(rands, &v.Reserve)
2045 }
2046
2047 func (v *MakeSlice) Operands(rands []*Value) []*Value {
2048 return append(rands, &v.Len, &v.Cap)
2049 }
2050
2051 func (v *MapUpdate) Operands(rands []*Value) []*Value {
2052 return append(rands, &v.Map, &v.Key, &v.Value)
2053 }
2054
2055 func (v *Next) Operands(rands []*Value) []*Value {
2056 return append(rands, &v.Iter)
2057 }
2058
2059 func (s *Panic) Operands(rands []*Value) []*Value {
2060 return append(rands, &s.X)
2061 }
2062
2063 func (v *Sigma) Operands(rands []*Value) []*Value {
2064 return append(rands, &v.X)
2065 }
2066
2067 func (v *Phi) Operands(rands []*Value) []*Value {
2068 for i := range v.Edges {
2069 rands = append(rands, &v.Edges[i])
2070 }
2071 return rands
2072 }
2073
2074 func (v *Range) Operands(rands []*Value) []*Value {
2075 return append(rands, &v.X)
2076 }
2077
2078 func (s *Return) Operands(rands []*Value) []*Value {
2079 for i := range s.Results {
2080 rands = append(rands, &s.Results[i])
2081 }
2082 return rands
2083 }
2084
2085 func (*RunDefers) Operands(rands []*Value) []*Value {
2086 return rands
2087 }
2088
2089 func (v *Select) Operands(rands []*Value) []*Value {
2090 for i := range v.States {
2091 rands = append(rands, &v.States[i].Chan, &v.States[i].Send)
2092 }
2093 return rands
2094 }
2095
2096 func (s *Send) Operands(rands []*Value) []*Value {
2097 return append(rands, &s.Chan, &s.X)
2098 }
2099
2100 func (recv *Recv) Operands(rands []*Value) []*Value {
2101 return append(rands, &recv.Chan)
2102 }
2103
2104 func (v *Slice) Operands(rands []*Value) []*Value {
2105 return append(rands, &v.X, &v.Low, &v.High, &v.Max)
2106 }
2107
2108 func (s *Store) Operands(rands []*Value) []*Value {
2109 return append(rands, &s.Addr, &s.Val)
2110 }
2111
2112 func (s *BlankStore) Operands(rands []*Value) []*Value {
2113 return append(rands, &s.Val)
2114 }
2115
2116 func (v *TypeAssert) Operands(rands []*Value) []*Value {
2117 return append(rands, &v.X)
2118 }
2119
2120 func (v *UnOp) Operands(rands []*Value) []*Value {
2121 return append(rands, &v.X)
2122 }
2123
2124 func (v *Load) Operands(rands []*Value) []*Value {
2125 return append(rands, &v.X)
2126 }
2127
2128 func (v *AggregateConst) Operands(rands []*Value) []*Value {
2129 for i := range v.Values {
2130 rands = append(rands, &v.Values[i])
2131 }
2132 return rands
2133 }
2134
2135 func (v *CompositeValue) Operands(rands []*Value) []*Value {
2136 for i := range v.Values {
2137 rands = append(rands, &v.Values[i])
2138 }
2139 return rands
2140 }
2141
2142 // Non-Instruction Values:
2143 func (v *Builtin) Operands(rands []*Value) []*Value { return rands }
2144 func (v *FreeVar) Operands(rands []*Value) []*Value { return rands }
2145 func (v *Const) Operands(rands []*Value) []*Value { return rands }
2146 func (v *ArrayConst) Operands(rands []*Value) []*Value { return rands }
2147 func (v *GenericConst) Operands(rands []*Value) []*Value { return rands }
2148 func (v *Function) Operands(rands []*Value) []*Value { return rands }
2149 func (v *Global) Operands(rands []*Value) []*Value { return rands }
2150 func (v *Parameter) Operands(rands []*Value) []*Value { return rands }