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