| 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 defines a representation of the elements of Go programs |
| 6 |
// (packages, types, functions, variables and constants) using a |
| 7 |
// static single-information (SSI) 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, upon which SSI builds, see |
| 13 |
// https://en.wikipedia.org/wiki/Static_single_assignment_form. |
| 14 |
// This page provides a broader reading list: |
| 15 |
// https://www.dcs.gla.ac.uk/~jsinger/ssa.html. |
| 16 |
// |
| 17 |
// For an introduction to SSI form, see The static single information |
| 18 |
// form by C. Scott Ananian. |
| 19 |
// |
| 20 |
// The level of abstraction of the IR form is intentionally close to |
| 21 |
// the source language to facilitate construction of source analysis |
| 22 |
// tools. It is not intended for machine code generation. |
| 23 |
// |
| 24 |
// The simplest way to create the IR of a package is |
| 25 |
// to load typed syntax trees using golang.org/x/tools/go/packages, then |
| 26 |
// invoke the irutil.Packages helper function. See ExampleLoadPackages |
| 27 |
// and ExampleWholeProgram for examples. |
| 28 |
// The resulting ir.Program contains all the packages and their |
| 29 |
// members, but IR 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 IR form in which all local |
| 33 |
// variables are addresses of stack locations with explicit loads and |
| 34 |
// stores. Registerization 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 IR 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 |
// *BlankStore ✔ |
| 55 |
// *Builtin ✔ |
| 56 |
// *Call ✔ ✔ |
| 57 |
// *ChangeInterface ✔ ✔ |
| 58 |
// *ChangeType ✔ ✔ |
| 59 |
// *Const ✔ ✔ |
| 60 |
// *Convert ✔ ✔ |
| 61 |
// *DebugRef ✔ |
| 62 |
// *Defer ✔ ✔ |
| 63 |
// *Extract ✔ ✔ |
| 64 |
// *Field ✔ ✔ |
| 65 |
// *FieldAddr ✔ ✔ |
| 66 |
// *FreeVar ✔ |
| 67 |
// *Function ✔ ✔ (func) |
| 68 |
// *Global ✔ ✔ (var) |
| 69 |
// *Go ✔ ✔ |
| 70 |
// *If ✔ |
| 71 |
// *Index ✔ ✔ |
| 72 |
// *IndexAddr ✔ ✔ |
| 73 |
// *Jump ✔ |
| 74 |
// *Load ✔ ✔ |
| 75 |
// *MakeChan ✔ ✔ |
| 76 |
// *MakeClosure ✔ ✔ |
| 77 |
// *MakeInterface ✔ ✔ |
| 78 |
// *MakeMap ✔ ✔ |
| 79 |
// *MakeSlice ✔ ✔ |
| 80 |
// *MapLookup ✔ ✔ |
| 81 |
// *MapUpdate ✔ ✔ |
| 82 |
// *MultiConvert ✔ ✔ |
| 83 |
// *NamedConst ✔ (const) |
| 84 |
// *Next ✔ ✔ |
| 85 |
// *Panic ✔ |
| 86 |
// *Parameter ✔ ✔ |
| 87 |
// *Phi ✔ ✔ |
| 88 |
// *Range ✔ ✔ |
| 89 |
// *Recv ✔ ✔ |
| 90 |
// *Return ✔ |
| 91 |
// *RunDefers ✔ |
| 92 |
// *Select ✔ ✔ |
| 93 |
// *Send ✔ ✔ |
| 94 |
// *Sigma ✔ ✔ |
| 95 |
// *Slice ✔ ✔ |
| 96 |
// *SliceToArrayPointer ✔ ✔ |
| 97 |
// *SliceToArray ✔ ✔ |
| 98 |
// *Store ✔ ✔ |
| 99 |
// *StringLookup ✔ ✔ |
| 100 |
// *Type ✔ (type) |
| 101 |
// *TypeAssert ✔ ✔ |
| 102 |
// *UnOp ✔ ✔ |
| 103 |
// *Unreachable ✔ |
| 104 |
// |
| 105 |
// Other key types in this package include: Program, Package, Function |
| 106 |
// and BasicBlock. |
| 107 |
// |
| 108 |
// The program representation constructed by this package is fully |
| 109 |
// resolved internally, i.e. it does not rely on the names of Values, |
| 110 |
// Packages, Functions, Types or BasicBlocks for the correct |
| 111 |
// interpretation of the program. Only the identities of objects and |
| 112 |
// the topology of the IR and type graphs are semantically |
| 113 |
// significant. (There is one exception: Ids, used to identify field |
| 114 |
// and method names, contain strings.) Avoidance of name-based |
| 115 |
// operations simplifies the implementation of subsequent passes and |
| 116 |
// can make them very efficient. Many objects are nonetheless named |
| 117 |
// to aid in debugging, but it is not essential that the names be |
| 118 |
// either accurate or unambiguous. The public API exposes a number of |
| 119 |
// name-based maps for client convenience. |
| 120 |
// |
| 121 |
// The ir/irutil package provides various utilities that depend only |
| 122 |
// on the public API of this package. |
| 123 |
// |
| 124 |
// TODO(adonovan): Consider the exceptional control-flow implications |
| 125 |
// of defer and recover(). |
| 126 |
// |
| 127 |
// TODO(adonovan): write a how-to document for all the various cases |
| 128 |
// of trying to determine corresponding elements across the four |
| 129 |
// domains of source locations, ast.Nodes, types.Objects, |
| 130 |
// ir.Values/Instructions. |
| 131 |
package ir |