mlir/docs/SymbolsAndSymbolTables.md

   1 # Symbols and Symbol Tables
   2
   3 [TOC]
   4
   5 With [Regions](LangRef.md/#regions), the multi-level aspect of MLIR is
   6 structural in the IR. A lot of infrastructure within the compiler is built
   7 around this nesting structure; including the processing of operations within the
   8 [pass manager](PassManagement.md/#pass-manager). One advantage of the MLIR
   9 design is that it is able to process operations in parallel, utilizing multiple
  10 threads. This is possible due to a property of the IR known as
  11 [`IsolatedFromAbove`](Traits/#isolatedfromabove).
  12
  13 Without this property, any operation could affect or mutate the use-list of
  14 operations defined above. Making this thread-safe requires expensive locking in
  15 some of the core IR data structures, which becomes quite inefficient. To enable
  16 multi-threaded compilation without this locking, MLIR uses local pools for
  17 constant values as well as `Symbol` accesses for global values and variables.
  18 This document details the design of `Symbol`s, what they are and how they fit
  19 into the system.
  20
  21 The `Symbol` infrastructure essentially provides a non-SSA mechanism in which to
  22 refer to an operation symbolically with a name. This allows for referring to
  23 operations defined above regions that were defined as `IsolatedFromAbove` in a
  24 safe way. It also allows for symbolically referencing operations define below
  25 other regions as well.
  26
  27 ## Symbol
  28
  29 A `Symbol` is a named operation that resides immediately within a region that
  30 defines a [`SymbolTable`](#symbol-table). The name of a symbol *must* be unique
  31 within the parent `SymbolTable`. This name is semantically similarly to an SSA
  32 result value, and may be referred to by other operations to provide a symbolic
  33 link, or use, to the symbol. An example of a `Symbol` operation is
  34 [`func.func`](Dialects/Builtin.md/#func-mlirfuncop). `func.func` defines a
  35 symbol name, which is [referred to](#referencing-a-symbol) by operations like
  36 [`func.call`](Dialects/Func.md/#funccall-callop).
  37
  38 ### Defining or declaring a Symbol
  39
  40 A `Symbol` operation should use the `SymbolOpInterface` interface to provide the
  41 necessary verification and accessors; it also supports operations, such as
  42 `builtin.module`, that conditionally define a symbol. `Symbol`s must have the
  43 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
  61 Described above are `Symbol`s, which reside within a region of an operation
  62 defining a `SymbolTable`. A `SymbolTable` operation provides the container for
  63 the [`Symbol`](#symbol) operations. It verifies that all `Symbol` operations
  64 have a unique name, and provides facilities for looking up symbols by name.
  65 Operations 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
  71 reference attribute contains a named reference to an operation that is nested
  72 within a symbol table. It may optionally contain a set of nested references that
  73 further resolve to a symbol nested within a different symbol table. When
  74 resolving a nested reference, each non-leaf reference must refer to a symbol
  75 operation that is also a [symbol table](#symbol-table).
  76
  77 Below is an example of how an operation can reference a symbol operation:
  78
  79 ```mlir
  80 // This `func.func` operation defines a symbol named `symbol`.
  81 func.func @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.
  89 func.func @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.
 100 module {
 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.
 108 module @module_symbol {
 109   // This `func.func` operation defines a symbol named `nested_symbol`.
 110   func.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
 118 Using 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
 133 The impact of this choice to use attributes as opposed to SSA values is that we
 134 now have two mechanisms with reference operations. This means that some dialects
 135 must either support both `SymbolRefs` and SSA value references, or provide
 136 operations that materialize SSA values from a symbol reference. Each has
 137 different trade offs depending on the situation. A function call may directly
 138 use a `SymbolRef` as the callee, whereas a reference to a global variable might
 139 use a materialization operation so that the variable can be used in other
 140 operations like `arith.addi`.
 141 [`llvm.mlir.addressof`](Dialects/LLVM.md/#llvmmliraddressof-mlirllvmaddressofop)
 142 is one example of such an operation.
 143
 144 See the `LangRef` definition of the
 145 [`SymbolRefAttr`](Dialects/Builtin.md/#symbolrefattr) for more information about
 146 the structure of this attribute.
 147
 148 Operations that reference a `Symbol` and want to perform verification and
 149 general mutation of the symbol should implement the `SymbolUserOpInterface` to
 150 ensure that symbol accesses are legal and efficient.
 151
 152 ### Manipulating a Symbol
 153
 154 As described above, `SymbolRefs` act as an auxiliary way of defining uses of
 155 operations to the traditional SSA use-list. As such, it is imperative to provide
 156 similar functionality to manipulate and inspect the list of uses and the users.
 157 The 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
 181 Along 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
 183 symbol 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
 203 For Functions, the visibility is printed after the operation name without a
 204 quote. A few examples of what this looks like in the IR are shown below:
 205
 206 ```mlir
 207 module @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.func nested @nested_function()
 211
 212   // This function cannot be accessed outside of 'public_module'.
 213   func.func private @private_function()
 214 }
 215
 216 // This function can only be accessed from within the top-level module.
 217 func.func private @private_function()
 218
 219 // This function may be referenced externally.
 220 func.func @public_function()
 221
 222 "live.user"() {uses = [
 223   @public_module::@nested_function,
 224   @private_function,
 225   @public_function
 226 ]} : () -> ()
 227 ```