1# Symbols and Symbol Tables
2
3[TOC]
4
5With [Regions](LangRef.md/#regions), the multi-level aspect of MLIR is structural
6in the IR. A lot of infrastructure within the compiler is built around this
7nesting structure; including the processing of operations within the
8[pass manager](PassManagement.md/#pass-manager). One advantage of the MLIR design
9is that it is able to process operations in parallel, utilizing multiple
10threads. This is possible due to a property of the IR known as
11[`IsolatedFromAbove`](Traits.md/#isolatedfromabove).
12
13Without this property, any operation could affect or mutate the use-list of
14operations defined above. Making this thread-safe requires expensive locking in
15some of the core IR data structures, which becomes quite inefficient. To enable
16multi-threaded compilation without this locking, MLIR uses local pools for
17constant values as well as `Symbol` accesses for global values and variables.
18This document details the design of `Symbol`s, what they are and how they fit
19into the system.
20
21The `Symbol` infrastructure essentially provides a non-SSA mechanism in which to
22refer to an operation symbolically with a name. This allows for referring to
23operations defined above regions that were defined as `IsolatedFromAbove` in a
24safe way. It also allows for symbolically referencing operations define below
25other regions as well.
26
27## Symbol
28
29A `Symbol` is a named operation that resides immediately within a region that
30defines a [`SymbolTable`](#symbol-table). The name of a symbol *must* be unique
31within the parent `SymbolTable`. This name is semantically similarly to an SSA
32result value, and may be referred to by other operations to provide a symbolic
33link, or use, to the symbol. An example of a `Symbol` operation is
34[`func`](Dialects/Builtin.md/#func-mlirfuncop). `func` defines a symbol name, which is
35[referred to](#referencing-a-symbol) by operations like
36[`std.call`](Dialects/Standard.md/#stdcall-callop).
37
38### Defining or declaring a Symbol
39
40A `Symbol` operation should use the `SymbolOpInterface` interface to provide the
41necessary verification and accessors; it also supports
42operations, such as `module`, that conditionally define a symbol. `Symbol`s must
43have the following properties:
44
45*   A `StringAttr` attribute named
46    'SymbolTable::getSymbolAttrName()'(`sym_name`).
47    -   This attribute defines the symbolic 'name' of the operation.
48*   An optional `StringAttr` attribute named
49    'SymbolTable::getVisibilityAttrName()'(`sym_visibility`)
50    -   This attribute defines the [visibility](#symbol-visibility) of the
51        symbol, or more specifically in-which scopes it may be accessed.
52*   No SSA results
53    -   Intermixing the different ways to `use` an operation quickly becomes
54        unwieldy and difficult to analyze.
55*   Whether this operation is a declaration or definition (`isDeclaration`)
56    -   Declarations do not define a new symbol but reference a symbol defined
57        outside the visible IR.
58
59## Symbol Table
60
61Described above are `Symbol`s, which reside within a region of an operation
62defining a `SymbolTable`. A `SymbolTable` operation provides the container for
63the [`Symbol`](#symbol) operations. It verifies that all `Symbol` operations
64have a unique name, and provides facilities for looking up symbols by name.
65Operations defining a `SymbolTable` must use the `OpTrait::SymbolTable` trait.
66
67### Referencing a Symbol
68
69`Symbol`s are referenced symbolically by name via the
70[`SymbolRefAttr`](Dialects/Builtin.md/#symbolrefattr) attribute. A symbol
71reference attribute contains a named reference to an operation that is nested
72within a symbol table. It may optionally contain a set of nested references that
73further resolve to a symbol nested within a different symbol table. When
74resolving a nested reference, each non-leaf reference must refer to a symbol
75operation that is also a [symbol table](#symbol-table).
76
77Below is an example of how an operation can reference a symbol operation:
78
79```mlir
80// This `func` operation defines a symbol named `symbol`.
81func @symbol()
82
83// Our `foo.user` operation contains a SymbolRefAttr with the name of the
84// `symbol` func.
85"foo.user"() {uses = [@symbol]} : () -> ()
86
87// Symbol references resolve to the nearest parent operation that defines a
88// symbol table, so we can have references with arbitrary nesting levels.
89func @other_symbol() {
90  affine.for %i0 = 0 to 10 {
91    // Our `foo.user` operation resolves to the same `symbol` func as defined
92    // above.
93    "foo.user"() {uses = [@symbol]} : () -> ()
94  }
95  return
96}
97
98// Here we define a nested symbol table. References within this operation will
99// not resolve to any symbols defined above.
100module {
101  // Error. We resolve references with respect to the closest parent operation
102  // that defines a symbol table, so this reference can't be resolved.
103  "foo.user"() {uses = [@symbol]} : () -> ()
104}
105
106// Here we define another nested symbol table, except this time it also defines
107// a symbol.
108module @module_symbol {
109  // This `func` operation defines a symbol named `nested_symbol`.
110  func @nested_symbol()
111}
112
113// Our `foo.user` operation may refer to the nested symbol, by resolving through
114// the parent.
115"foo.user"() {uses = [@module_symbol::@nested_symbol]} : () -> ()
116```
117
118Using an attribute, as opposed to an SSA value, has several benefits:
119
120*   References may appear in more places than the operand list; including
121    [nested attribute dictionaries](Dialects/Builtin.md/dictionaryattr),
122    [array attributes](Dialects/Builtin.md/#arrayattr), etc.
123
124*   Handling of SSA dominance remains unchanged.
125
126    -   If we were to use SSA values, we would need to create some mechanism in
127        which to opt-out of certain properties of it such as dominance.
128        Attributes allow for referencing the operations irregardless of the
129        order in which they were defined.
130    -   Attributes simplify referencing operations within nested symbol tables,
131        which are traditionally not visible outside of the parent region.
132
133The impact of this choice to use attributes as opposed to SSA values is that we
134now have two mechanisms with reference operations. This means that some dialects
135must either support both `SymbolRefs` and SSA value references, or provide
136operations that materialize SSA values from a symbol reference. Each has
137different trade offs depending on the situation. A function call may directly
138use a `SymbolRef` as the callee, whereas a reference to a global variable might
139use a materialization operation so that the variable can be used in other
140operations like `std.addi`.
141[`llvm.mlir.addressof`](Dialects/LLVM.md/#llvmmliraddressof-mlirllvmaddressofop) is one example of
142such an operation.
143
144See the `LangRef` definition of the
145[`SymbolRefAttr`](Dialects/Builtin.md/#symbolrefattr) for more information
146about the structure of this attribute.
147
148Operations that reference a `Symbol` and want to perform verification and
149general mutation of the symbol should implement the `SymbolUserOpInterface` to
150ensure that symbol accesses are legal and efficient.
151
152### Manipulating a Symbol
153
154As described above, `SymbolRefs` act as an auxiliary way of defining uses of
155operations to the traditional SSA use-list. As such, it is imperative to provide
156similar functionality to manipulate and inspect the list of uses and the users.
157The following are a few of the utilities provided by the `SymbolTable`:
158
159*   `SymbolTable::getSymbolUses`
160
161    -   Access an iterator range over all of the uses on and nested within a
162        particular operation.
163
164*   `SymbolTable::symbolKnownUseEmpty`
165
166    -   Check if a particular symbol is known to be unused within a specific
167        section of the IR.
168
169*   `SymbolTable::replaceAllSymbolUses`
170
171    -   Replace all of the uses of one symbol with a new one within a specific
172        section of the IR.
173
174*   `SymbolTable::lookupNearestSymbolFrom`
175
176    -   Lookup the definition of a symbol in the nearest symbol table from some
177        anchor operation.
178
179## Symbol Visibility
180
181Along with a name, a `Symbol` also has a `visibility` attached to it. The
182`visibility` of a symbol defines its structural reachability within the IR. A
183symbol has one of the following visibilities:
184
185*   Public (Default)
186
187    -   The symbol may be referenced from outside of the visible IR. We cannot
188        assume that all of the uses of this symbol are observable. If the
189        operation declares a symbol (as opposed to defining it), public
190        visibility is not allowed because symbol declarations are not intended
191        to be used from outside the visible IR.
192
193*   Private
194
195    -   The symbol may only be referenced from within the current symbol table.
196
197*   Nested
198
199    -   The symbol may be referenced by operations outside of the current symbol
200        table, but not outside of the visible IR, as long as each symbol table
201        parent also defines a non-private symbol.
202
203For Functions, the visibility is printed after the operation name without a
204quote. A few examples of what this looks like in the IR are shown below:
205
206```mlir
207module @public_module {
208  // This function can be accessed by 'live.user', but cannot be referenced
209  // externally; all uses are known to reside within parent regions.
210  func nested @nested_function()
211
212  // This function cannot be accessed outside of 'public_module'.
213  func private @private_function()
214}
215
216// This function can only be accessed from within the top-level module.
217func private @private_function()
218
219// This function may be referenced externally.
220func @public_function()
221
222"live.user"() {uses = [
223  @public_module::@nested_function,
224  @private_function,
225  @public_function
226]} : () -> ()
227```
228