1 //===- SymbolTable.cpp - MLIR Symbol Table Class --------------------------===//
2 //
3 // Copyright 2019 The MLIR Authors.
4 //
5 // Licensed under the Apache License, Version 2.0 (the "License");
6 // you may not use this file except in compliance with the License.
7 // You may obtain a copy of the License at
8 //
9 //   http://www.apache.org/licenses/LICENSE-2.0
10 //
11 // Unless required by applicable law or agreed to in writing, software
12 // distributed under the License is distributed on an "AS IS" BASIS,
13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 // See the License for the specific language governing permissions and
15 // limitations under the License.
16 // =============================================================================
17 
18 #include "mlir/IR/SymbolTable.h"
19 #include "llvm/ADT/SmallString.h"
20 
21 using namespace mlir;
22 
23 /// Build a symbol table with the symbols within the given operation.
24 SymbolTable::SymbolTable(Operation *op) : context(op->getContext()) {
25   assert(op->hasTrait<OpTrait::SymbolTable>() &&
26          "expected operation to have SymbolTable trait");
27   assert(op->getNumRegions() == 1 &&
28          "expected operation to have a single region");
29 
30   for (auto &block : op->getRegion(0)) {
31     for (auto &op : block) {
32       auto nameAttr = op.getAttrOfType<StringAttr>(getSymbolAttrName());
33       if (!nameAttr)
34         continue;
35 
36       auto inserted = symbolTable.insert({nameAttr.getValue(), &op});
37       (void)inserted;
38       assert(inserted.second &&
39              "expected region to contain uniquely named symbol operations");
40     }
41   }
42 }
43 
44 /// Look up a symbol with the specified name, returning null if no such name
45 /// exists. Names never include the @ on them.
46 Operation *SymbolTable::lookup(StringRef name) const {
47   return symbolTable.lookup(name);
48 }
49 
50 /// Erase the given symbol from the table.
51 void SymbolTable::erase(Operation *symbol) {
52   auto nameAttr = symbol->getAttrOfType<StringAttr>(getSymbolAttrName());
53   assert(nameAttr && "expected valid 'name' attribute");
54 
55   auto it = symbolTable.find(nameAttr.getValue());
56   if (it != symbolTable.end() && it->second == symbol)
57     symbolTable.erase(it);
58 }
59 
60 /// Insert a new symbol into the table, and rename it as necessary to avoid
61 /// collisions.
62 void SymbolTable::insert(Operation *symbol) {
63   auto nameAttr = symbol->getAttrOfType<StringAttr>(getSymbolAttrName());
64   assert(nameAttr && "expected valid 'name' attribute");
65 
66   // Add this symbol to the symbol table, uniquing the name if a conflict is
67   // detected.
68   if (symbolTable.insert({nameAttr.getValue(), symbol}).second)
69     return;
70 
71   // If a conflict was detected, then the symbol will not have been added to
72   // the symbol table. Try suffixes until we get to a unique name that works.
73   SmallString<128> nameBuffer(nameAttr.getValue());
74   unsigned originalLength = nameBuffer.size();
75 
76   // Iteratively try suffixes until we find one that isn't used.
77   do {
78     nameBuffer.resize(originalLength);
79     nameBuffer += '_';
80     nameBuffer += std::to_string(uniquingCounter++);
81   } while (!symbolTable.insert({nameBuffer, symbol}).second);
82   symbol->setAttr(getSymbolAttrName(), StringAttr::get(nameBuffer, context));
83 }
84 
85 /// Returns the operation registered with the given symbol name with the
86 /// regions of 'symbolTableOp'. 'symbolTableOp' is required to be an operation
87 /// with the 'OpTrait::SymbolTable' trait. Returns nullptr if no valid symbol
88 /// was found.
89 Operation *SymbolTable::lookupSymbolIn(Operation *symbolTableOp,
90                                        StringRef symbol) {
91   assert(symbolTableOp->hasTrait<OpTrait::SymbolTable>());
92 
93   // Look for a symbol with the given name.
94   for (auto &block : symbolTableOp->getRegion(0)) {
95     for (auto &op : block) {
96       auto nameAttr = op.template getAttrOfType<StringAttr>(
97           mlir::SymbolTable::getSymbolAttrName());
98       if (nameAttr && nameAttr.getValue() == symbol)
99         return &op;
100     }
101   }
102   return nullptr;
103 }
104 
105 /// Returns the operation registered with the given symbol name within the
106 /// closes parent operation with the 'OpTrait::SymbolTable' trait. Returns
107 /// nullptr if no valid symbol was found.
108 Operation *SymbolTable::lookupNearestSymbolFrom(Operation *from,
109                                                 StringRef symbol) {
110   while (from && !from->hasTrait<OpTrait::SymbolTable>())
111     from = from->getParentOp();
112   return from ? lookupSymbolIn(from, symbol) : nullptr;
113 }
114 
115 //===----------------------------------------------------------------------===//
116 // SymbolTable Trait Types
117 //===----------------------------------------------------------------------===//
118 
119 LogicalResult OpTrait::impl::verifySymbolTable(Operation *op) {
120   if (op->getNumRegions() != 1)
121     return op->emitOpError()
122            << "Operations with a 'SymbolTable' must have exactly one region";
123 
124   // Check that all symboles are uniquely named within child regions.
125   llvm::StringMap<Location> nameToOrigLoc;
126   for (auto &block : op->getRegion(0)) {
127     for (auto &op : block) {
128       // Check for a symbol name attribute.
129       auto nameAttr =
130           op.getAttrOfType<StringAttr>(mlir::SymbolTable::getSymbolAttrName());
131       if (!nameAttr)
132         continue;
133 
134       // Try to insert this symbol into the table.
135       auto it = nameToOrigLoc.try_emplace(nameAttr.getValue(), op.getLoc());
136       if (!it.second)
137         return op.emitError()
138             .append("redefinition of symbol named '", nameAttr.getValue(), "'")
139             .attachNote(it.first->second)
140             .append("see existing symbol definition here");
141     }
142   }
143   return success();
144 }
145