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