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 defines a representation of the elements of Go programs
6 // (packages, types, functions, variables and constants) using a
7 // static single-assignment (SSA) form intermediate representation
8 // (IR) for the bodies of functions.
9 //
10 // For an introduction to SSA form, see
11 // http://en.wikipedia.org/wiki/Static_single_assignment_form.
12 // This page provides a broader reading list:
13 // http://www.dcs.gla.ac.uk/~jsinger/ssa.html.
14 //
15 // The level of abstraction of the SSA form is intentionally close to
16 // the source language to facilitate construction of source analysis
17 // tools. It is not intended for machine code generation.
18 //
19 // All looping, branching and switching constructs are replaced with
20 // unstructured control flow. Higher-level control flow constructs
21 // such as multi-way branch can be reconstructed as needed; see
22 // [golang.org/x/tools/go/ssa/ssautil.Switches] for an example.
23 //
24 // The simplest way to create the SSA representation of a package is
25 // to load typed syntax trees using [golang.org/x/tools/go/packages], then
26 // invoke the [golang.org/x/tools/go/ssa/ssautil.Packages] helper function.
27 // (See the package-level Examples named LoadPackages and LoadWholeProgram.)
28 // The resulting [ssa.Program] contains all the packages and their
29 // members, but SSA code is not created for function bodies until a
30 // subsequent call to [Package.Build] or [Program.Build].
31 //
32 // The builder initially builds a naive SSA form in which all local
33 // variables are addresses of stack locations with explicit loads and
34 // stores. Registerisation of eligible locals and φ-node insertion
35 // using dominance and dataflow are then performed as a second pass
36 // called "lifting" to improve the accuracy and performance of
37 // subsequent analyses; this pass can be skipped by setting the
38 // NaiveForm builder flag.
39 //
40 // The primary interfaces of this package are:
41 //
42 // - [Member]: a named member of a Go package.
43 // - [Value]: an expression that yields a value.
44 // - [Instruction]: a statement that consumes values and performs computation.
45 // - [Node]: a [Value] or [Instruction] (emphasizing its membership in the SSA value graph)
46 //
47 // A computation that yields a result implements both the [Value] and
48 // [Instruction] interfaces. The following table shows for each
49 // concrete type which of these interfaces it implements.
50 //
51 // Value? Instruction? Member?
52 // *Alloc ✔ ✔
53 // *BinOp ✔ ✔
54 // *Builtin ✔
55 // *Call ✔ ✔
56 // *ChangeInterface ✔ ✔
57 // *ChangeType ✔ ✔
58 // *Const ✔
59 // *Convert ✔ ✔
60 // *DebugRef ✔
61 // *Defer ✔
62 // *Extract ✔ ✔
63 // *Field ✔ ✔
64 // *FieldAddr ✔ ✔
65 // *FreeVar ✔
66 // *Function ✔ ✔ (func)
67 // *Global ✔ ✔ (var)
68 // *Go ✔
69 // *If ✔
70 // *Index ✔ ✔
71 // *IndexAddr ✔ ✔
72 // *Jump ✔
73 // *Lookup ✔ ✔
74 // *MakeChan ✔ ✔
75 // *MakeClosure ✔ ✔
76 // *MakeInterface ✔ ✔
77 // *MakeMap ✔ ✔
78 // *MakeSlice ✔ ✔
79 // *MapUpdate ✔
80 // *MultiConvert ✔ ✔
81 // *NamedConst ✔ (const)
82 // *Next ✔ ✔
83 // *Panic ✔
84 // *Parameter ✔
85 // *Phi ✔ ✔
86 // *Range ✔ ✔
87 // *Return ✔
88 // *RunDefers ✔
89 // *Select ✔ ✔
90 // *Send ✔
91 // *Slice ✔ ✔
92 // *SliceToArrayPointer ✔ ✔
93 // *Store ✔
94 // *Type ✔ (type)
95 // *TypeAssert ✔ ✔
96 // *UnOp ✔ ✔
97 //
98 // Other key types in this package include: [Program], [Package], [Function]
99 // and [BasicBlock].
100 //
101 // The program representation constructed by this package is fully
102 // resolved internally, i.e. it does not rely on the names of Values,
103 // Packages, Functions, Types or BasicBlocks for the correct
104 // interpretation of the program. Only the identities of objects and
105 // the topology of the SSA and type graphs are semantically
106 // significant. (There is one exception: [types.Id] values, which identify field
107 // and method names, contain strings.) Avoidance of name-based
108 // operations simplifies the implementation of subsequent passes and
109 // can make them very efficient. Many objects are nonetheless named
110 // to aid in debugging, but it is not essential that the names be
111 // either accurate or unambiguous. The public API exposes a number of
112 // name-based maps for client convenience.
113 //
114 // The [golang.org/x/tools/go/ssa/ssautil] package provides various
115 // helper functions, for example to simplify loading a Go program into
116 // SSA form.
117 //
118 // TODO(adonovan): write a how-to document for all the various cases
119 // of trying to determine corresponding elements across the four
120 // domains of source locations, ast.Nodes, types.Objects,
121 // ssa.Values/Instructions.
122 package ssa // import "golang.org/x/tools/go/ssa"
123