| 1 | //===- Namespace.h - Utilities for generating names -------------*- 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 | // This file provides utilities for generating new names that do not conflict |
| 10 | // with existing names. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #ifndef MLIR_SUPPORT_NAMESPACE_H |
| 15 | #define MLIR_SUPPORT_NAMESPACE_H |
| 16 | |
| 17 | #include "mlir/IR/BuiltinOps.h" |
| 18 | #include "mlir/Target/SMTLIB/SymCache.h" |
| 19 | #include "llvm/ADT/SmallString.h" |
| 20 | #include "llvm/ADT/StringSet.h" |
| 21 | #include "llvm/ADT/Twine.h" |
| 22 | |
| 23 | namespace mlir { |
| 24 | |
| 25 | /// A namespace that is used to store existing names and generate new names in |
| 26 | /// some scope within the IR. This exists to work around limitations of |
| 27 | /// SymbolTables. This acts as a base class providing facilities common to all |
| 28 | /// namespaces implementations. |
| 29 | class Namespace { |
| 30 | public: |
| 31 | Namespace() { |
| 32 | // This fills an entry for an empty string beforehand so that `newName` |
| 33 | // doesn't return an empty string. |
| 34 | nextIndex.insert(KV: {"" , 0}); |
| 35 | } |
| 36 | Namespace(const Namespace &other) = default; |
| 37 | Namespace(Namespace &&other) |
| 38 | : nextIndex(std::move(other.nextIndex)), locked(other.locked) {} |
| 39 | |
| 40 | Namespace &operator=(const Namespace &other) = default; |
| 41 | Namespace &operator=(Namespace &&other) { |
| 42 | nextIndex = std::move(other.nextIndex); |
| 43 | locked = other.locked; |
| 44 | return *this; |
| 45 | } |
| 46 | |
| 47 | void add(mlir::ModuleOp module) { |
| 48 | assert(module->getNumRegions() == 1); |
| 49 | for (auto &op : module.getBody(idx: 0)->getOperations()) |
| 50 | if (auto symbol = mlir::dyn_cast<mlir::SymbolOpInterface>(Val: &op)) |
| 51 | nextIndex.insert(KV: {symbol.getName(), 0}); |
| 52 | } |
| 53 | |
| 54 | /// SymbolCache initializer; initialize from every key that is convertible to |
| 55 | /// a StringAttr in the SymbolCache. |
| 56 | void add(SymbolCache &symCache) { |
| 57 | for (auto &&[attr, _] : symCache) |
| 58 | if (auto strAttr = dyn_cast<mlir::StringAttr>(Val&: attr)) |
| 59 | nextIndex.insert(KV: {strAttr.getValue(), 0}); |
| 60 | } |
| 61 | |
| 62 | void add(llvm::StringRef name) { nextIndex.insert(KV: {name, 0}); } |
| 63 | |
| 64 | /// Removes a symbol from the namespace. Returns true if the symbol was |
| 65 | /// removed, false if the symbol was not found. |
| 66 | /// This is only allowed to be called _before_ any call to newName. |
| 67 | bool erase(llvm::StringRef symbol) { |
| 68 | assert(!locked && "Cannot erase names from a locked namespace" ); |
| 69 | return nextIndex.erase(Key: symbol); |
| 70 | } |
| 71 | |
| 72 | /// Empty the namespace. |
| 73 | void clear() { |
| 74 | nextIndex.clear(); |
| 75 | locked = false; |
| 76 | } |
| 77 | |
| 78 | /// Return a unique name, derived from the input `name`, and add the new name |
| 79 | /// to the internal namespace. There are two possible outcomes for the |
| 80 | /// returned name: |
| 81 | /// |
| 82 | /// 1. The original name is returned. |
| 83 | /// 2. The name is given a `_<n>` suffix where `<n>` is a number starting from |
| 84 | /// `0` and incrementing by one each time (`_0`, ...). |
| 85 | llvm::StringRef newName(const llvm::Twine &name) { |
| 86 | locked = true; |
| 87 | // Special case the situation where there is no name collision to avoid |
| 88 | // messing with the SmallString allocation below. |
| 89 | llvm::SmallString<64> tryName; |
| 90 | auto inserted = nextIndex.insert(KV: {name.toStringRef(Out&: tryName), 0}); |
| 91 | if (inserted.second) |
| 92 | return inserted.first->getKey(); |
| 93 | |
| 94 | // Try different suffixes until we get a collision-free one. |
| 95 | if (tryName.empty()) |
| 96 | name.toVector(Out&: tryName); // toStringRef may leave tryName unfilled |
| 97 | |
| 98 | // Indexes less than nextIndex[tryName] are lready used, so skip them. |
| 99 | // Indexes larger than nextIndex[tryName] may be used in another name. |
| 100 | size_t &i = nextIndex[tryName]; |
| 101 | tryName.push_back(Elt: '_'); |
| 102 | size_t baseLength = tryName.size(); |
| 103 | do { |
| 104 | tryName.resize(N: baseLength); |
| 105 | llvm::Twine(i++).toVector(Out&: tryName); // append integer to tryName |
| 106 | inserted = nextIndex.insert(KV: {tryName, 0}); |
| 107 | } while (!inserted.second); |
| 108 | |
| 109 | return inserted.first->getKey(); |
| 110 | } |
| 111 | |
| 112 | /// Return a unique name, derived from the input `name` and ensure the |
| 113 | /// returned name has the input `suffix`. Also add the new name to the |
| 114 | /// internal namespace. |
| 115 | /// There are two possible outcomes for the returned name: |
| 116 | /// 1. The original name + `_<suffix>` is returned. |
| 117 | /// 2. The name is given a suffix `_<n>_<suffix>` where `<n>` is a number |
| 118 | /// starting from `0` and incrementing by one each time. |
| 119 | llvm::StringRef newName(const llvm::Twine &name, const llvm::Twine &suffix) { |
| 120 | locked = true; |
| 121 | // Special case the situation where there is no name collision to avoid |
| 122 | // messing with the SmallString allocation below. |
| 123 | llvm::SmallString<64> tryName; |
| 124 | auto inserted = nextIndex.insert( |
| 125 | KV: {name.concat(Suffix: "_" ).concat(Suffix: suffix).toStringRef(Out&: tryName), 0}); |
| 126 | if (inserted.second) |
| 127 | return inserted.first->getKey(); |
| 128 | |
| 129 | // Try different suffixes until we get a collision-free one. |
| 130 | tryName.clear(); |
| 131 | name.toVector(Out&: tryName); // toStringRef may leave tryName unfilled |
| 132 | tryName.push_back(Elt: '_'); |
| 133 | size_t baseLength = tryName.size(); |
| 134 | |
| 135 | // Get the initial number to start from. Since `:` is not a valid character |
| 136 | // in a verilog identifier, we use it separate the name and suffix. |
| 137 | // Next number for name+suffix is stored with key `name_:suffix`. |
| 138 | tryName.push_back(Elt: ':'); |
| 139 | suffix.toVector(Out&: tryName); |
| 140 | |
| 141 | // Indexes less than nextIndex[tryName] are already used, so skip them. |
| 142 | // Indexes larger than nextIndex[tryName] may be used in another name. |
| 143 | size_t &i = nextIndex[tryName]; |
| 144 | do { |
| 145 | tryName.resize(N: baseLength); |
| 146 | llvm::Twine(i++).toVector(Out&: tryName); // append integer to tryName |
| 147 | tryName.push_back(Elt: '_'); |
| 148 | suffix.toVector(Out&: tryName); |
| 149 | inserted = nextIndex.insert(KV: {tryName, 0}); |
| 150 | } while (!inserted.second); |
| 151 | |
| 152 | return inserted.first->getKey(); |
| 153 | } |
| 154 | |
| 155 | protected: |
| 156 | // The "next index" that will be tried when trying to unique a string within a |
| 157 | // namespace. It follows that all values less than the "next index" value are |
| 158 | // already used. |
| 159 | llvm::StringMap<size_t> nextIndex; |
| 160 | |
| 161 | // When true, no names can be erased from the namespace. This is to prevent |
| 162 | // erasing names after they have been used, thus leaving users of the |
| 163 | // namespace in an inconsistent state. |
| 164 | bool locked = false; |
| 165 | }; |
| 166 | |
| 167 | } // namespace mlir |
| 168 | |
| 169 | #endif // MLIR_SUPPORT_NAMESPACE_H |
| 170 | |