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`](LangRef.md#functions). `func` defines a symbol name, which is 35[referred to](#referencing-a-symbol) by operations like 36[`std.call`](Dialects/Standard.md#call). 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`](LangRef.md#symbol-reference-attribute) 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](LangRef.md#dictionary-attribute), 122 [array attributes](LangRef.md#array-attribute), 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) is one example of 142such an operation. 143 144See the `LangRef` definition of the 145[`SymbolRefAttr`](LangRef.md#symbol-reference-attribute) 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