| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // Copyright Contributors to the OpenVDB Project | ||
| 2 | // SPDX-License-Identifier: MPL-2.0 | ||
| 3 | |||
| 4 | /// @file codegen/SymbolTable.h | ||
| 5 | /// | ||
| 6 | /// @authors Nick Avramoussis | ||
| 7 | /// | ||
| 8 | /// @brief Contains the symbol table which holds mappings of variables names | ||
| 9 | /// to llvm::Values. | ||
| 10 | /// | ||
| 11 | |||
| 12 | #ifndef OPENVDB_AX_CODEGEN_SYMBOL_TABLE_HAS_BEEN_INCLUDED | ||
| 13 | #define OPENVDB_AX_CODEGEN_SYMBOL_TABLE_HAS_BEEN_INCLUDED | ||
| 14 | |||
| 15 | #include <openvdb/version.h> | ||
| 16 | |||
| 17 | #include <llvm/IR/Value.h> | ||
| 18 | |||
| 19 | #include <string> | ||
| 20 | #include <map> | ||
| 21 | #include <unordered_map> | ||
| 22 | |||
| 23 | namespace openvdb { | ||
| 24 | OPENVDB_USE_VERSION_NAMESPACE | ||
| 25 | namespace OPENVDB_VERSION_NAME { | ||
| 26 | |||
| 27 | namespace ax { | ||
| 28 | namespace codegen { | ||
| 29 | |||
| 30 | /// @brief A symbol table which can be used to represent a single scoped set of | ||
| 31 | /// a programs variables. This is simply an unordered map of strings to | ||
| 32 | /// llvm::Values | ||
| 33 | /// @note Consider using llvm's ValueSymbolTable | ||
| 34 | /// | ||
| 35 | struct SymbolTable | ||
| 36 | { | ||
| 37 | using MapType = std::unordered_map<std::string, llvm::Value*>; | ||
| 38 | |||
| 39 |
1/2✓ Branch 1 taken 756 times.
✗ Branch 2 not taken.
|
4570 | SymbolTable() : mMap() {} |
| 40 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
|
1 | ~SymbolTable() = default; |
| 41 | |||
| 42 | /// @brief Get a llvm::Value from this symbol table with the given name | ||
| 43 | /// mapping. It it does not exist, a nullptr is returned. | ||
| 44 | /// @param name The name of the variable | ||
| 45 | /// | ||
| 46 | 51840 | inline llvm::Value* get(const std::string& name) const | |
| 47 | { | ||
| 48 |
2/2✓ Branch 0 taken 46312 times.
✓ Branch 1 taken 5528 times.
|
51840 | const auto iter = mMap.find(name); |
| 49 |
2/2✓ Branch 0 taken 46312 times.
✓ Branch 1 taken 5528 times.
|
51840 | if (iter == mMap.end()) return nullptr; |
| 50 | 46312 | return iter->second; | |
| 51 | } | ||
| 52 | |||
| 53 | /// @brief Returns true if a variable exists in this symbol table with the | ||
| 54 | /// given name. | ||
| 55 | /// @param name The name of the variable | ||
| 56 | /// | ||
| 57 | inline bool exists(const std::string& name) const | ||
| 58 | { | ||
| 59 |
7/11✓ Branch 0 taken 29019 times.
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 7 times.
✓ Branch 14 taken 1 times.
|
29037 | const auto iter = mMap.find(name); |
| 60 | return (iter != mMap.end()); | ||
| 61 | } | ||
| 62 | |||
| 63 | /// @brief Insert a variable to this symbol table if it does not exist. Returns | ||
| 64 | /// true if successfully, false if a variable already exists with the | ||
| 65 | /// given name. | ||
| 66 | /// @param name The name of the variable | ||
| 67 | /// @param value The llvm::Value corresponding to this variable | ||
| 68 | /// | ||
| 69 | 29030 | inline bool insert(const std::string& name, llvm::Value* value) | |
| 70 | { | ||
| 71 |
2/2✓ Branch 0 taken 29026 times.
✓ Branch 1 taken 4 times.
|
29030 | if (exists(name)) return false; |
| 72 | 29026 | mMap[name] = value; | |
| 73 | 29026 | return true; | |
| 74 | } | ||
| 75 | |||
| 76 | /// @brief Replace a variable in this symbol table. Returns true if the variable | ||
| 77 | /// previously existed and false if not. In both cases, the variable is | ||
| 78 | /// inserted. | ||
| 79 | /// @param name The name of the variable | ||
| 80 | /// @param value The llvm::Value corresponding to this variable | ||
| 81 | /// | ||
| 82 | 3 | inline bool replace(const std::string& name, llvm::Value* value) | |
| 83 | { | ||
| 84 | const bool existed = exists(name); | ||
| 85 | 3 | mMap[name] = value; | |
| 86 | 3 | return existed; | |
| 87 | } | ||
| 88 | |||
| 89 | /// @brief Clear all symbols in this table | ||
| 90 | /// | ||
| 91 | inline void clear() { mMap.clear(); } | ||
| 92 | |||
| 93 | /// @brief Access to the underlying map | ||
| 94 | /// | ||
| 95 | inline const MapType& map() const { return mMap; } | ||
| 96 | |||
| 97 | private: | ||
| 98 | MapType mMap; | ||
| 99 | }; | ||
| 100 | |||
| 101 | |||
| 102 | /// @brief A map of unique ids to symbol tables which can be used to represent local | ||
| 103 | /// variables within a program. New scopes can be added and erased where necessary | ||
| 104 | /// and iterated through using find(). Find assumes that tables are added through | ||
| 105 | /// parented ascending ids. | ||
| 106 | /// | ||
| 107 | /// @note The zero id is used to represent global variables | ||
| 108 | /// @note The block symbol table is fairly simple and currently only supports insertion | ||
| 109 | /// by integer ids. Scopes that exist at the same level are expected to be built | ||
| 110 | /// in isolation and erase and re-create the desired ids where necessary. | ||
| 111 | /// | ||
| 112 | struct SymbolTableBlocks | ||
| 113 | { | ||
| 114 | using MapType = std::map<size_t, SymbolTable>; | ||
| 115 | |||
| 116 |
4/8✓ Branch 1 taken 1817 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1817 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1817 times.
✓ Branch 7 taken 1817 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
|
7268 | SymbolTableBlocks() : mTables({{0, SymbolTable()}}) {} |
| 117 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
|
1817 | ~SymbolTableBlocks() = default; |
| 118 | |||
| 119 | /// @brief Access to the list of global variables which are always accessible | ||
| 120 | /// | ||
| 121 |
12/19✓ Branch 1 taken 5916 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 5062 times.
✓ Branch 4 taken 5839 times.
✓ Branch 5 taken 77 times.
✓ Branch 6 taken 5062 times.
✓ Branch 7 taken 752 times.
✓ Branch 8 taken 77 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 752 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 757 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 757 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 757 times.
✗ Branch 20 not taken.
✓ Branch 22 taken 757 times.
✗ Branch 23 not taken.
|
11814 | inline SymbolTable& globals() { return mTables.at(0); } |
| 122 | inline const SymbolTable& globals() const { return mTables.at(0); } | ||
| 123 | |||
| 124 | /// @brief Erase a given scoped indexed SymbolTable from the list of held | ||
| 125 | /// SymbolTables. Returns true if the table previously existed. | ||
| 126 | /// @note If the zero index is supplied, this function throws a runtime error | ||
| 127 | /// | ||
| 128 | /// @param index The SymbolTable index to erase | ||
| 129 | /// | ||
| 130 | 2271 | inline bool erase(const size_t index) | |
| 131 | { | ||
| 132 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 2270 times.
|
2271 | if (index == 0) { |
| 133 |
1/2✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
|
1 | throw std::runtime_error("Attempted to erase global variables which is disallowed."); |
| 134 | } | ||
| 135 | |||
| 136 | 2270 | const bool existed = (mTables.find(index) != mTables.end()); | |
| 137 | mTables.erase(index); | ||
| 138 | 2270 | return existed; | |
| 139 | } | ||
| 140 | |||
| 141 | /// @brief Get or insert and get a SymbolTable with a unique index | ||
| 142 | /// | ||
| 143 | /// @param index The SymbolTable index | ||
| 144 | /// | ||
| 145 | inline SymbolTable* getOrInsert(const size_t index) | ||
| 146 | { | ||
| 147 |
8/15✓ Branch 1 taken 1 times.
✓ Branch 2 taken 763 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 1 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 1 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 1 times.
✗ Branch 20 not taken.
|
10362 | return &(mTables[index]); |
| 148 | } | ||
| 149 | |||
| 150 | /// @brief Get a SymbolTable with a unique index. If it doesn't exist, nullptr is returned | ||
| 151 | /// | ||
| 152 | /// @param index The SymbolTable index | ||
| 153 | /// | ||
| 154 | inline SymbolTable* get(const size_t index) | ||
| 155 | { | ||
| 156 |
4/6✓ Branch 0 taken 5063 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 5062 times.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 751 times.
✗ Branch 5 not taken.
|
10877 | auto iter = mTables.find(index); |
| 157 |
4/6✓ Branch 0 taken 5063 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 5062 times.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 751 times.
✗ Branch 5 not taken.
|
10877 | if (iter == mTables.end()) return nullptr; |
| 158 | 10876 | return &(iter->second); | |
| 159 | } | ||
| 160 | |||
| 161 | /// @brief Find a variable within the program starting at a given table index. If | ||
| 162 | /// the given index does not exist, the next descending index is used. | ||
| 163 | /// @note This function assumes that tables have been added in ascending order | ||
| 164 | /// dictating their nested structure. | ||
| 165 | /// | ||
| 166 | /// @param name The variable name to find | ||
| 167 | /// @param startIndex The start SymbolTable index | ||
| 168 | /// | ||
| 169 | 13745 | inline llvm::Value* find(const std::string& name, const size_t startIndex) const | |
| 170 | { | ||
| 171 | // Find the lower bound start index and if necessary, decrement into | ||
| 172 | // the first block where the search will be started. Note that this | ||
| 173 | // is safe as the global block 0 will always exist | ||
| 174 | |||
| 175 |
2/2✓ Branch 0 taken 13744 times.
✓ Branch 1 taken 1 times.
|
13745 | auto it = mTables.lower_bound(startIndex); |
| 176 |
4/4✓ Branch 0 taken 13744 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 2051 times.
✓ Branch 3 taken 11693 times.
|
13745 | if (it == mTables.end() || it->first != startIndex) --it; |
| 177 | |||
| 178 | // reverse the iterator (which also make it point to the preceding | ||
| 179 | // value, hence the crement) | ||
| 180 | |||
| 181 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 13745 times.
|
13745 | assert(it != mTables.end()); |
| 182 | 13745 | MapType::const_reverse_iterator iter(++it); | |
| 183 | |||
| 184 |
2/2✓ Branch 0 taken 15614 times.
✓ Branch 1 taken 3577 times.
|
19191 | for (; iter != mTables.crend(); ++iter) { |
| 185 | 15614 | llvm::Value* value = iter->second.get(name); | |
| 186 |
2/2✓ Branch 0 taken 5446 times.
✓ Branch 1 taken 10168 times.
|
15614 | if (value) return value; |
| 187 | } | ||
| 188 | |||
| 189 | return nullptr; | ||
| 190 | } | ||
| 191 | |||
| 192 | /// @brief Find a variable within the program starting at the lowest level | ||
| 193 | /// SymbolTable | ||
| 194 | /// | ||
| 195 | /// @param name The variable name to find | ||
| 196 | /// | ||
| 197 | 10151 | inline llvm::Value* find(const std::string& name) const | |
| 198 | { | ||
| 199 | 10151 | return this->find(name, mTables.crbegin()->first); | |
| 200 | } | ||
| 201 | |||
| 202 | /// @brief Replace the first occurrance of a variable with a given name with a | ||
| 203 | /// replacement value. Returns true if a replacement occurred. | ||
| 204 | /// | ||
| 205 | /// @param name The variable name to find and replace | ||
| 206 | /// @param value The llvm::Value to replace | ||
| 207 | /// | ||
| 208 | 2 | inline bool replace(const std::string& name, llvm::Value* value) | |
| 209 | { | ||
| 210 |
2/2✓ Branch 0 taken 6 times.
✓ Branch 1 taken 1 times.
|
7 | for (auto it = mTables.rbegin(); it != mTables.rend(); ++it) { |
| 211 |
2/2✓ Branch 1 taken 1 times.
✓ Branch 2 taken 5 times.
|
6 | if (it->second.get(name)) { |
| 212 | 1 | it->second.replace(name, value); | |
| 213 | 1 | return true; | |
| 214 | } | ||
| 215 | } | ||
| 216 | |||
| 217 | 1 | return false; | |
| 218 | } | ||
| 219 | |||
| 220 | private: | ||
| 221 | MapType mTables; | ||
| 222 | }; | ||
| 223 | |||
| 224 | } // namespace codegen | ||
| 225 | } // namespace ax | ||
| 226 | } // namespace OPENVDB_VERSION_NAME | ||
| 227 | } // namespace openvdb | ||
| 228 | |||
| 229 | #endif // OPENVDB_AX_CODEGEN_SYMBOL_TABLE_HAS_BEEN_INCLUDED | ||
| 230 | |||
| 231 |