MLIR  16.0.0git
SymbolTable.h
Go to the documentation of this file.
1 //===- SymbolTable.h - MLIR Symbol Table Class ------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #ifndef MLIR_IR_SYMBOLTABLE_H
10 #define MLIR_IR_SYMBOLTABLE_H
11 
12 #include "mlir/IR/Attributes.h"
13 #include "mlir/IR/OpDefinition.h"
14 #include "llvm/ADT/SetVector.h"
15 #include "llvm/ADT/StringMap.h"
16 
17 namespace mlir {
18 
19 /// This class allows for representing and managing the symbol table used by
20 /// operations with the 'SymbolTable' trait. Inserting into and erasing from
21 /// this SymbolTable will also insert and erase from the Operation given to it
22 /// at construction.
23 class SymbolTable {
24 public:
25  /// Build a symbol table with the symbols within the given operation.
26  SymbolTable(Operation *symbolTableOp);
27 
28  /// Look up a symbol with the specified name, returning null if no such
29  /// name exists. Names never include the @ on them.
30  Operation *lookup(StringRef name) const;
31  template <typename T>
32  T lookup(StringRef name) const {
33  return dyn_cast_or_null<T>(lookup(name));
34  }
35 
36  /// Look up a symbol with the specified name, returning null if no such
37  /// name exists. Names never include the @ on them.
38  Operation *lookup(StringAttr name) const;
39  template <typename T>
40  T lookup(StringAttr name) const {
41  return dyn_cast_or_null<T>(lookup(name));
42  }
43 
44  /// Remove the given symbol from the table, without deleting it.
45  void remove(Operation *op);
46 
47  /// Erase the given symbol from the table and delete the operation.
48  void erase(Operation *symbol);
49 
50  /// Insert a new symbol into the table, and rename it as necessary to avoid
51  /// collisions. Also insert at the specified location in the body of the
52  /// associated operation if it is not already there. It is asserted that the
53  /// symbol is not inside another operation. Return the name of the symbol
54  /// after insertion as attribute.
55  StringAttr insert(Operation *symbol, Block::iterator insertPt = {});
56 
57  /// Return the name of the attribute used for symbol names.
58  static StringRef getSymbolAttrName() { return "sym_name"; }
59 
60  /// Returns the associated operation.
61  Operation *getOp() const { return symbolTableOp; }
62 
63  /// Return the name of the attribute used for symbol visibility.
64  static StringRef getVisibilityAttrName() { return "sym_visibility"; }
65 
66  //===--------------------------------------------------------------------===//
67  // Symbol Utilities
68  //===--------------------------------------------------------------------===//
69 
70  /// An enumeration detailing the different visibility types that a symbol may
71  /// have.
72  enum class Visibility {
73  /// The symbol is public and may be referenced anywhere internal or external
74  /// to the visible references in the IR.
75  Public,
76 
77  /// The symbol is private and may only be referenced by SymbolRefAttrs local
78  /// to the operations within the current symbol table.
79  Private,
80 
81  /// The symbol is visible to the current IR, which may include operations in
82  /// symbol tables above the one that owns the current symbol. `Nested`
83  /// visibility allows for referencing a symbol outside of its current symbol
84  /// table, while retaining the ability to observe all uses.
85  Nested,
86  };
87 
88  /// Returns the name of the given symbol operation, aborting if no symbol is
89  /// present.
90  static StringAttr getSymbolName(Operation *symbol);
91 
92  /// Sets the name of the given symbol operation.
93  static void setSymbolName(Operation *symbol, StringAttr name);
94  static void setSymbolName(Operation *symbol, StringRef name) {
95  setSymbolName(symbol, StringAttr::get(symbol->getContext(), name));
96  }
97 
98  /// Returns the visibility of the given symbol operation.
100  /// Sets the visibility of the given symbol operation.
101  static void setSymbolVisibility(Operation *symbol, Visibility vis);
102 
103  /// Returns the nearest symbol table from a given operation `from`. Returns
104  /// nullptr if no valid parent symbol table could be found.
106 
107  /// Walks all symbol table operations nested within, and including, `op`. For
108  /// each symbol table operation, the provided callback is invoked with the op
109  /// and a boolean signifying if the symbols within that symbol table can be
110  /// treated as if all uses within the IR are visible to the caller.
111  /// `allSymUsesVisible` identifies whether all of the symbol uses of symbols
112  /// within `op` are visible.
113  static void walkSymbolTables(Operation *op, bool allSymUsesVisible,
114  function_ref<void(Operation *, bool)> callback);
115 
116  /// Returns the operation registered with the given symbol name with the
117  /// regions of 'symbolTableOp'. 'symbolTableOp' is required to be an operation
118  /// with the 'OpTrait::SymbolTable' trait.
119  static Operation *lookupSymbolIn(Operation *op, StringAttr symbol);
120  static Operation *lookupSymbolIn(Operation *op, StringRef symbol) {
121  return lookupSymbolIn(op, StringAttr::get(op->getContext(), symbol));
122  }
123  static Operation *lookupSymbolIn(Operation *op, SymbolRefAttr symbol);
124  /// A variant of 'lookupSymbolIn' that returns all of the symbols referenced
125  /// by a given SymbolRefAttr. Returns failure if any of the nested references
126  /// could not be resolved.
127  static LogicalResult lookupSymbolIn(Operation *op, SymbolRefAttr symbol,
129 
130  /// Returns the operation registered with the given symbol name within the
131  /// closest parent operation of, or including, 'from' with the
132  /// 'OpTrait::SymbolTable' trait. Returns nullptr if no valid symbol was
133  /// found.
134  static Operation *lookupNearestSymbolFrom(Operation *from, StringAttr symbol);
136  SymbolRefAttr symbol);
137  template <typename T>
138  static T lookupNearestSymbolFrom(Operation *from, StringAttr symbol) {
139  return dyn_cast_or_null<T>(lookupNearestSymbolFrom(from, symbol));
140  }
141  template <typename T>
142  static T lookupNearestSymbolFrom(Operation *from, SymbolRefAttr symbol) {
143  return dyn_cast_or_null<T>(lookupNearestSymbolFrom(from, symbol));
144  }
145 
146  /// This class represents a specific symbol use.
147  class SymbolUse {
148  public:
149  SymbolUse(Operation *op, SymbolRefAttr symbolRef)
150  : owner(op), symbolRef(symbolRef) {}
151 
152  /// Return the operation user of this symbol reference.
153  Operation *getUser() const { return owner; }
154 
155  /// Return the symbol reference that this use represents.
156  SymbolRefAttr getSymbolRef() const { return symbolRef; }
157 
158  private:
159  /// The operation that this access is held by.
160  Operation *owner;
161 
162  /// The symbol reference that this use represents.
163  SymbolRefAttr symbolRef;
164  };
165 
166  /// This class implements a range of SymbolRef uses.
167  class UseRange {
168  public:
169  UseRange(std::vector<SymbolUse> &&uses) : uses(std::move(uses)) {}
170 
171  using iterator = std::vector<SymbolUse>::const_iterator;
172  iterator begin() const { return uses.begin(); }
173  iterator end() const { return uses.end(); }
174  bool empty() const { return uses.empty(); }
175 
176  private:
177  std::vector<SymbolUse> uses;
178  };
179 
180  /// Get an iterator range for all of the uses, for any symbol, that are nested
181  /// within the given operation 'from'. This does not traverse into any nested
182  /// symbol tables. This function returns None if there are any unknown
183  /// operations that may potentially be symbol tables.
186 
187  /// Get all of the uses of the given symbol that are nested within the given
188  /// operation 'from'. This does not traverse into any nested symbol tables.
189  /// This function returns None if there are any unknown operations that may
190  /// potentially be symbol tables.
191  static Optional<UseRange> getSymbolUses(StringAttr symbol, Operation *from);
192  static Optional<UseRange> getSymbolUses(Operation *symbol, Operation *from);
193  static Optional<UseRange> getSymbolUses(StringAttr symbol, Region *from);
194  static Optional<UseRange> getSymbolUses(Operation *symbol, Region *from);
195 
196  /// Return if the given symbol is known to have no uses that are nested
197  /// within the given operation 'from'. This does not traverse into any nested
198  /// symbol tables. This function will also return false if there are any
199  /// unknown operations that may potentially be symbol tables. This doesn't
200  /// necessarily mean that there are no uses, we just can't conservatively
201  /// prove it.
202  static bool symbolKnownUseEmpty(StringAttr symbol, Operation *from);
203  static bool symbolKnownUseEmpty(Operation *symbol, Operation *from);
204  static bool symbolKnownUseEmpty(StringAttr symbol, Region *from);
205  static bool symbolKnownUseEmpty(Operation *symbol, Region *from);
206 
207  /// Attempt to replace all uses of the given symbol 'oldSymbol' with the
208  /// provided symbol 'newSymbol' that are nested within the given operation
209  /// 'from'. This does not traverse into any nested symbol tables. If there are
210  /// any unknown operations that may potentially be symbol tables, no uses are
211  /// replaced and failure is returned.
212  static LogicalResult replaceAllSymbolUses(StringAttr oldSymbol,
213  StringAttr newSymbol,
214  Operation *from);
215  static LogicalResult replaceAllSymbolUses(Operation *oldSymbol,
216  StringAttr newSymbolName,
217  Operation *from);
218  static LogicalResult replaceAllSymbolUses(StringAttr oldSymbol,
219  StringAttr newSymbol, Region *from);
220  static LogicalResult replaceAllSymbolUses(Operation *oldSymbol,
221  StringAttr newSymbolName,
222  Region *from);
223 
224 private:
225  Operation *symbolTableOp;
226 
227  /// This is a mapping from a name to the symbol with that name. They key is
228  /// always known to be a StringAttr.
230 
231  /// This is used when name conflicts are detected.
232  unsigned uniquingCounter = 0;
233 };
234 
235 raw_ostream &operator<<(raw_ostream &os, SymbolTable::Visibility visibility);
236 
237 //===----------------------------------------------------------------------===//
238 // SymbolTableCollection
239 //===----------------------------------------------------------------------===//
240 
241 /// This class represents a collection of `SymbolTable`s. This simplifies
242 /// certain algorithms that run recursively on nested symbol tables. Symbol
243 /// tables are constructed lazily to reduce the upfront cost of constructing
244 /// unnecessary tables.
246 public:
247  /// Look up a symbol with the specified name within the specified symbol table
248  /// operation, returning null if no such name exists.
249  Operation *lookupSymbolIn(Operation *symbolTableOp, StringAttr symbol);
250  Operation *lookupSymbolIn(Operation *symbolTableOp, SymbolRefAttr name);
251  template <typename T, typename NameT>
252  T lookupSymbolIn(Operation *symbolTableOp, NameT &&name) {
253  return dyn_cast_or_null<T>(
254  lookupSymbolIn(symbolTableOp, std::forward<NameT>(name)));
255  }
256  /// A variant of 'lookupSymbolIn' that returns all of the symbols referenced
257  /// by a given SymbolRefAttr when resolved within the provided symbol table
258  /// operation. Returns failure if any of the nested references could not be
259  /// resolved.
260  LogicalResult lookupSymbolIn(Operation *symbolTableOp, SymbolRefAttr name,
262 
263  /// Returns the operation registered with the given symbol name within the
264  /// closest parent operation of, or including, 'from' with the
265  /// 'OpTrait::SymbolTable' trait. Returns nullptr if no valid symbol was
266  /// found.
267  Operation *lookupNearestSymbolFrom(Operation *from, StringAttr symbol);
268  Operation *lookupNearestSymbolFrom(Operation *from, SymbolRefAttr symbol);
269  template <typename T>
270  T lookupNearestSymbolFrom(Operation *from, StringAttr symbol) {
271  return dyn_cast_or_null<T>(lookupNearestSymbolFrom(from, symbol));
272  }
273  template <typename T>
274  T lookupNearestSymbolFrom(Operation *from, SymbolRefAttr symbol) {
275  return dyn_cast_or_null<T>(lookupNearestSymbolFrom(from, symbol));
276  }
277 
278  /// Lookup, or create, a symbol table for an operation.
280 
281 private:
282  /// The constructed symbol tables nested within this table.
284 };
285 
286 //===----------------------------------------------------------------------===//
287 // SymbolUserMap
288 //===----------------------------------------------------------------------===//
289 
290 /// This class represents a map of symbols to users, and provides efficient
291 /// implementations of symbol queries related to users; such as collecting the
292 /// users of a symbol, replacing all uses, etc.
294 public:
295  /// Build a user map for all of the symbols defined in regions nested under
296  /// 'symbolTableOp'. A reference to the provided symbol table collection is
297  /// kept by the user map to ensure efficient lookups, thus the lifetime should
298  /// extend beyond that of this map.
299  SymbolUserMap(SymbolTableCollection &symbolTable, Operation *symbolTableOp);
300 
301  /// Return the users of the provided symbol operation.
303  auto it = symbolToUsers.find(symbol);
304  return it != symbolToUsers.end() ? it->second.getArrayRef() : llvm::None;
305  }
306 
307  /// Return true if the given symbol has no uses.
308  bool useEmpty(Operation *symbol) const {
309  return !symbolToUsers.count(symbol);
310  }
311 
312  /// Replace all of the uses of the given symbol with `newSymbolName`.
313  void replaceAllUsesWith(Operation *symbol, StringAttr newSymbolName);
314 
315 private:
316  /// A reference to the symbol table used to construct this map.
317  SymbolTableCollection &symbolTable;
318 
319  /// A map of symbol operations to symbol users.
321 };
322 
323 //===----------------------------------------------------------------------===//
324 // SymbolTable Trait Types
325 //===----------------------------------------------------------------------===//
326 
327 namespace detail {
328 LogicalResult verifySymbolTable(Operation *op);
329 LogicalResult verifySymbol(Operation *op);
330 } // namespace detail
331 
332 namespace OpTrait {
333 /// A trait used to provide symbol table functionalities to a region operation.
334 /// This operation must hold exactly 1 region. Once attached, all operations
335 /// that are directly within the region, i.e not including those within child
336 /// regions, that contain a 'SymbolTable::getSymbolAttrName()' StringAttr will
337 /// be verified to ensure that the names are uniqued. These operations must also
338 /// adhere to the constraints defined by the `Symbol` trait, even if they do not
339 /// inherit from it.
340 template <typename ConcreteType>
341 class SymbolTable : public TraitBase<ConcreteType, SymbolTable> {
342 public:
345  }
346 
347  /// Look up a symbol with the specified name, returning null if no such
348  /// name exists. Symbol names never include the @ on them. Note: This
349  /// performs a linear scan of held symbols.
350  Operation *lookupSymbol(StringAttr name) {
351  return mlir::SymbolTable::lookupSymbolIn(this->getOperation(), name);
352  }
353  template <typename T>
354  T lookupSymbol(StringAttr name) {
355  return dyn_cast_or_null<T>(lookupSymbol(name));
356  }
357  Operation *lookupSymbol(SymbolRefAttr symbol) {
358  return mlir::SymbolTable::lookupSymbolIn(this->getOperation(), symbol);
359  }
360  template <typename T>
361  T lookupSymbol(SymbolRefAttr symbol) {
362  return dyn_cast_or_null<T>(lookupSymbol(symbol));
363  }
364 
365  Operation *lookupSymbol(StringRef name) {
366  return mlir::SymbolTable::lookupSymbolIn(this->getOperation(), name);
367  }
368  template <typename T>
369  T lookupSymbol(StringRef name) {
370  return dyn_cast_or_null<T>(lookupSymbol(name));
371  }
372 };
373 
374 } // namespace OpTrait
375 
376 //===----------------------------------------------------------------------===//
377 // Visibility parsing implementation.
378 //===----------------------------------------------------------------------===//
379 
380 namespace impl {
381 /// Parse an optional visibility attribute keyword (i.e., public, private, or
382 /// nested) without quotes in a string attribute named 'attrName'.
383 ParseResult parseOptionalVisibilityKeyword(OpAsmParser &parser,
384  NamedAttrList &attrs);
385 } // namespace impl
386 
387 } // namespace mlir
388 
389 /// Include the generated symbol interfaces.
390 #include "mlir/IR/SymbolInterfaces.h.inc"
391 
392 #endif // MLIR_IR_SYMBOLTABLE_H
OpListType::iterator iterator
Definition: Block.h:129
A trait used to provide symbol table functionalities to a region operation.
Definition: SymbolTable.h:341
Operation * lookupSymbol(SymbolRefAttr symbol)
Definition: SymbolTable.h:357
Operation * lookupSymbol(StringRef name)
Definition: SymbolTable.h:365
T lookupSymbol(SymbolRefAttr symbol)
Definition: SymbolTable.h:361
T lookupSymbol(StringAttr name)
Definition: SymbolTable.h:354
T lookupSymbol(StringRef name)
Definition: SymbolTable.h:369
Operation * lookupSymbol(StringAttr name)
Look up a symbol with the specified name, returning null if no such name exists.
Definition: SymbolTable.h:350
static LogicalResult verifyRegionTrait(Operation *op)
Definition: SymbolTable.h:343
Helper class for implementing traits.
Definition: OpDefinition.h:310
Operation * getOperation()
Return the ultimate Operation being worked on.
Definition: OpDefinition.h:313
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:31
MLIRContext * getContext()
Return the context this operation is associated with.
Definition: Operation.h:147
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
This class represents a collection of SymbolTables.
Definition: SymbolTable.h:245
T lookupNearestSymbolFrom(Operation *from, StringAttr symbol)
Definition: SymbolTable.h:270
T lookupSymbolIn(Operation *symbolTableOp, NameT &&name)
Definition: SymbolTable.h:252
Operation * lookupNearestSymbolFrom(Operation *from, StringAttr symbol)
Returns the operation registered with the given symbol name within the closest parent operation of,...
T lookupNearestSymbolFrom(Operation *from, SymbolRefAttr symbol)
Definition: SymbolTable.h:274
Operation * lookupSymbolIn(Operation *symbolTableOp, StringAttr symbol)
Look up a symbol with the specified name within the specified symbol table operation,...
SymbolTable & getSymbolTable(Operation *op)
Lookup, or create, a symbol table for an operation.
This class represents a specific symbol use.
Definition: SymbolTable.h:147
SymbolUse(Operation *op, SymbolRefAttr symbolRef)
Definition: SymbolTable.h:149
SymbolRefAttr getSymbolRef() const
Return the symbol reference that this use represents.
Definition: SymbolTable.h:156
Operation * getUser() const
Return the operation user of this symbol reference.
Definition: SymbolTable.h:153
This class implements a range of SymbolRef uses.
Definition: SymbolTable.h:167
UseRange(std::vector< SymbolUse > &&uses)
Definition: SymbolTable.h:169
iterator begin() const
Definition: SymbolTable.h:172
std::vector< SymbolUse >::const_iterator iterator
Definition: SymbolTable.h:171
This class allows for representing and managing the symbol table used by operations with the 'SymbolT...
Definition: SymbolTable.h:23
static Visibility getSymbolVisibility(Operation *symbol)
Returns the visibility of the given symbol operation.
static StringRef getSymbolAttrName()
Return the name of the attribute used for symbol names.
Definition: SymbolTable.h:58
static void setSymbolVisibility(Operation *symbol, Visibility vis)
Sets the visibility of the given symbol operation.
Operation * getOp() const
Returns the associated operation.
Definition: SymbolTable.h:61
static T lookupNearestSymbolFrom(Operation *from, SymbolRefAttr symbol)
Definition: SymbolTable.h:142
static LogicalResult replaceAllSymbolUses(StringAttr oldSymbol, StringAttr newSymbol, Operation *from)
Attempt to replace all uses of the given symbol 'oldSymbol' with the provided symbol 'newSymbol' that...
Visibility
An enumeration detailing the different visibility types that a symbol may have.
Definition: SymbolTable.h:72
@ Nested
The symbol is visible to the current IR, which may include operations in symbol tables above the one ...
@ Public
The symbol is public and may be referenced anywhere internal or external to the visible references in...
@ Private
The symbol is private and may only be referenced by SymbolRefAttrs local to the operations within the...
static StringRef getVisibilityAttrName()
Return the name of the attribute used for symbol visibility.
Definition: SymbolTable.h:64
static T lookupNearestSymbolFrom(Operation *from, StringAttr symbol)
Definition: SymbolTable.h:138
void erase(Operation *symbol)
Erase the given symbol from the table and delete the operation.
static void setSymbolName(Operation *symbol, StringRef name)
Definition: SymbolTable.h:94
static Operation * lookupSymbolIn(Operation *op, StringAttr symbol)
Returns the operation registered with the given symbol name with the regions of 'symbolTableOp'.
Operation * lookup(StringRef name) const
Look up a symbol with the specified name, returning null if no such name exists.
T lookup(StringRef name) const
Definition: SymbolTable.h:32
SymbolTable(Operation *symbolTableOp)
Build a symbol table with the symbols within the given operation.
static Operation * lookupNearestSymbolFrom(Operation *from, StringAttr symbol)
Returns the operation registered with the given symbol name within the closest parent operation of,...
static Operation * lookupSymbolIn(Operation *op, StringRef symbol)
Definition: SymbolTable.h:120
static void setSymbolName(Operation *symbol, StringAttr name)
Sets the name of the given symbol operation.
static bool symbolKnownUseEmpty(StringAttr symbol, Operation *from)
Return if the given symbol is known to have no uses that are nested within the given operation 'from'...
static void walkSymbolTables(Operation *op, bool allSymUsesVisible, function_ref< void(Operation *, bool)> callback)
Walks all symbol table operations nested within, and including, op.
static StringAttr getSymbolName(Operation *symbol)
Returns the name of the given symbol operation, aborting if no symbol is present.
static Optional< UseRange > getSymbolUses(Operation *from)
Get an iterator range for all of the uses, for any symbol, that are nested within the given operation...
T lookup(StringAttr name) const
Definition: SymbolTable.h:40
StringAttr insert(Operation *symbol, Block::iterator insertPt={})
Insert a new symbol into the table, and rename it as necessary to avoid collisions.
void remove(Operation *op)
Remove the given symbol from the table, without deleting it.
static Operation * getNearestSymbolTable(Operation *from)
Returns the nearest symbol table from a given operation from.
This class represents a map of symbols to users, and provides efficient implementations of symbol que...
Definition: SymbolTable.h:293
bool useEmpty(Operation *symbol) const
Return true if the given symbol has no uses.
Definition: SymbolTable.h:308
void replaceAllUsesWith(Operation *symbol, StringAttr newSymbolName)
Replace all of the uses of the given symbol with newSymbolName.
ArrayRef< Operation * > getUsers(Operation *symbol) const
Return the users of the provided symbol operation.
Definition: SymbolTable.h:302
SymbolUserMap(SymbolTableCollection &symbolTable, Operation *symbolTableOp)
Build a user map for all of the symbols defined in regions nested under 'symbolTableOp'.
LogicalResult verifySymbol(Operation *op)
LogicalResult verifySymbolTable(Operation *op)
ParseResult parseOptionalVisibilityKeyword(OpAsmParser &parser, NamedAttrList &attrs)
Parse an optional visibility attribute keyword (i.e., public, private, or nested) without quotes in a...
Include the generated interface declarations.
raw_ostream & operator<<(raw_ostream &os, const AliasResult &result)
Definition: AliasAnalysis.h:78
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26