1 // -*- mode: C++; c-file-style: "cc-mode" -*- 2 //************************************************************************* 3 // DESCRIPTION: Verilator: Scoreboards for thread partitioner 4 // 5 // Provides scoreboard classes: 6 // 7 // * SortByValueMap 8 // * V3Scoreboard 9 // 10 // See details below 11 // 12 // Code available from: https://verilator.org 13 // 14 //************************************************************************* 15 // 16 // Copyright 2003-2021 by Wilson Snyder. This program is free software; you 17 // can redistribute it and/or modify it under the terms of either the GNU 18 // Lesser General Public License Version 3 or the Perl Artistic License 19 // Version 2.0. 20 // SPDX-License-Identifier: LGPL-3.0-only OR Artistic-2.0 21 // 22 //************************************************************************* 23 24 #ifndef VERILATOR_V3SCOREBOARD_H_ 25 #define VERILATOR_V3SCOREBOARD_H_ 26 27 #include "config_build.h" 28 #include "verilatedos.h" 29 30 #include "V3Error.h" 31 32 #include <set> 33 #include <map> 34 #include <unordered_map> 35 36 //###################################################################### 37 // SortByValueMap 38 39 /// A generic key-value map, except it also supports iterating in 40 /// value-sorted order. Values need not be unique. Uses T_KeyCompare to 41 /// break ties in the sort when values collide. 42 43 template <typename T_Key, typename T_Value, class T_KeyCompare = std::less<T_Key>> 44 class SortByValueMap final { 45 // TYPES 46 private: 47 using KeySet = std::set<T_Key, T_KeyCompare>; 48 using Val2Keys = std::map<T_Value, KeySet>; 49 50 // MEMBERS 51 std::unordered_map<T_Key, T_Value> m_keys; // Map each key to its value. Not sorted. 52 Val2Keys m_vals; // Map each value to its keys. Sorted. 53 54 public: 55 // CONSTRUCTORS 56 SortByValueMap() = default; 57 58 class const_iterator VL_NOT_FINAL { 59 // TYPES 60 public: 61 using value_type = const_iterator; 62 using reference = const_iterator; // See comment on operator*() 63 using pointer = void; 64 using difference_type = std::ptrdiff_t; 65 using iterator_category = std::bidirectional_iterator_tag; 66 67 protected: 68 friend class SortByValueMap; 69 70 // MEMBERS 71 typename KeySet::iterator m_keyIt; 72 typename Val2Keys::iterator m_valIt; 73 SortByValueMap* m_sbvmp; 74 bool m_end = true; // At the end() 75 76 // CONSTRUCTORS const_iterator(SortByValueMap * sbmvp)77 explicit const_iterator(SortByValueMap* sbmvp) // for end() 78 : m_sbvmp{sbmvp} {} const_iterator(typename Val2Keys::iterator valIt,typename KeySet::iterator keyIt,SortByValueMap * sbvmp)79 const_iterator(typename Val2Keys::iterator valIt, typename KeySet::iterator keyIt, 80 SortByValueMap* sbvmp) 81 : m_keyIt{keyIt} 82 , m_valIt{valIt} 83 , m_sbvmp{sbvmp} 84 , m_end{false} {} 85 86 // METHODS advanceUntilValid()87 void advanceUntilValid() { 88 ++m_keyIt; 89 if (m_keyIt != m_valIt->second.end()) { // Valid iterator, done. 90 return; 91 } 92 // Try the next value? 93 ++m_valIt; 94 if (m_valIt == m_sbvmp->m_vals.end()) { // No more values 95 m_end = true; 96 return; 97 } 98 // Should find a value here, as every value bucket is supposed 99 // to have at least one key, even after keys get removed. 100 m_keyIt = m_valIt->second.begin(); 101 UASSERT(m_keyIt != m_valIt->second.end(), "Algorithm should have key left"); 102 } reverseUntilValid()103 void reverseUntilValid() { 104 if (m_end) { 105 UASSERT(!m_sbvmp->m_vals.empty(), "Reverse iterator causes underflow"); 106 m_valIt = m_sbvmp->m_vals.end(); 107 --m_valIt; 108 109 UASSERT(!m_valIt->second.empty(), "Reverse iterator causes underflow"); 110 m_keyIt = m_valIt->second.end(); 111 --m_keyIt; 112 113 m_end = false; 114 return; 115 } 116 if (m_keyIt != m_valIt->second.begin()) { 117 // Valid iterator, we're done. 118 --m_keyIt; 119 return; 120 } 121 // Try the previous value? 122 if (VL_UNCOVERABLE(m_valIt == m_sbvmp->m_vals.begin())) { 123 // No more values but it's not defined to decrement an 124 // iterator past the beginning. 125 v3fatalSrc("Decremented iterator past beginning"); 126 return; // LCOV_EXCL_LINE 127 } 128 --m_valIt; 129 // Should find a value here, as Every value bucket is supposed 130 // to have at least one key, even after keys get removed. 131 UASSERT(!m_valIt->second.empty(), "Value bucket should have key"); 132 m_keyIt = m_valIt->second.end(); 133 --m_keyIt; 134 UASSERT(m_keyIt != m_valIt->second.end(), "Value bucket should have key"); 135 } 136 137 public: key()138 const T_Key& key() const { return *m_keyIt; } value()139 const T_Value& value() const { return m_valIt->first; } 140 const_iterator& operator++() { 141 advanceUntilValid(); 142 return *this; 143 } 144 const_iterator& operator--() { 145 reverseUntilValid(); 146 return *this; 147 } 148 bool operator==(const const_iterator& other) const { 149 // It's not legal to compare iterators from different 150 // sequences. So check m_end before comparing m_valIt, and 151 // compare m_valIt's before comparing m_keyIt to ensure nothing 152 // here is undefined. 153 if (m_end || other.m_end) return m_end && other.m_end; 154 return ((m_valIt == other.m_valIt) && (m_keyIt == other.m_keyIt)); 155 } 156 bool operator!=(const const_iterator& other) const { return (!this->operator==(other)); } 157 158 // WARNING: Cleverness. 159 // 160 // The "reference" returned by *it must remain valid after 'it' 161 // gets destroyed. The reverse_iterator relies on this for its 162 // operator*(), so it's not just a theoretical requirement, it's a 163 // real requirement. 164 // 165 // To make that work, define the "reference" type to be the 166 // iterator itself. So clients can do (*it).key() and 167 // (*it).value(). This is the clever part. 168 // 169 // That's mostly useful for a reverse iterator, where *rit returns 170 // the forward iterator pointing the to same element, so 171 // (*rit).key() and (*rit).value() work where rit.key() and 172 // rit.value() cannot. 173 // 174 // It would be nice to support it->key() and it->value(), however 175 // uncertain what would be an appropriate 'pointer' type define 176 // that makes this work safely through a reverse iterator. So this 177 // class does not provide an operator->(). 178 // 179 // Q) Why not make our value_type be a pair<T_Key, T_Value> like a 180 // normal map, and return a reference to that? This could 181 // return a reference to one of the pairs inside m_keys, that 182 // would satisfy the constraint above. 183 // 184 // A) It would take a lookup to find that pair within m_keys. This 185 // iterator is designed to minimize the number of hashtable and 186 // tree lookups. Increment, decrement, key(), value(), erase() 187 // by iterator, begin(), end() -- none of these require a 188 // container lookup. That's true for reverse_iterators too. 189 reference operator*() const { 190 UASSERT(!m_end, "Dereferencing iterator that is at end()"); 191 return *this; 192 } 193 }; 194 195 class iterator final : public const_iterator { 196 public: 197 // TYPES 198 using value_type = iterator; 199 using reference = iterator; 200 // pointer, difference_type, and iterator_category inherit from 201 // const_iterator 202 203 // CONSTRUCTORS iterator(SortByValueMap * sbvmp)204 explicit iterator(SortByValueMap* sbvmp) 205 : const_iterator{sbvmp} {} iterator(typename Val2Keys::iterator valIt,typename KeySet::iterator keyIt,SortByValueMap * sbvmp)206 iterator(typename Val2Keys::iterator valIt, typename KeySet::iterator keyIt, 207 SortByValueMap* sbvmp) 208 : const_iterator{valIt, keyIt, sbvmp} {} 209 210 // METHODS 211 iterator& operator++() { 212 this->advanceUntilValid(); 213 return *this; 214 } 215 iterator& operator--() { 216 this->reverseUntilValid(); 217 return *this; 218 } 219 reference operator*() const { 220 UASSERT(!this->m_end, "Dereferencing iterator that is at end()"); 221 return *this; 222 } 223 }; 224 225 using reverse_iterator = std::reverse_iterator<iterator>; 226 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 227 228 // METHODS 229 private: removeKeyFromOldVal(const T_Key & k,const T_Value & oldVal)230 void removeKeyFromOldVal(const T_Key& k, const T_Value& oldVal) { 231 // The value of 'k' is about to change, or, 'k' is about to be 232 // removed from the map. 233 // Clear the m_vals mapping for k. 234 KeySet& keysAtOldVal = m_vals[oldVal]; 235 const size_t erased = keysAtOldVal.erase(k); 236 UASSERT(erased == 1, "removeKeyFromOldVal() removal key not found"); 237 if (keysAtOldVal.empty()) { 238 // Don't keep empty sets in the value map. 239 m_vals.erase(oldVal); 240 } 241 } removeKeyFromOldVal(iterator it)242 void removeKeyFromOldVal(iterator it) { 243 it.m_valIt->second.erase(it.m_keyIt); 244 if (it.m_valIt->second.empty()) m_vals.erase(it.m_valIt); 245 } 246 247 public: begin()248 iterator begin() { 249 const auto valIt = m_vals.begin(); 250 if (valIt == m_vals.end()) return end(); 251 const auto keyIt = valIt->second.begin(); 252 return iterator(valIt, keyIt, this); 253 } begin()254 const_iterator begin() const { 255 SortByValueMap* const mutp = const_cast<SortByValueMap*>(this); 256 const auto valIt = mutp->m_vals.begin(); 257 if (valIt == mutp->m_vals.end()) return end(); 258 const auto keyIt = valIt->second.begin(); 259 return const_iterator(valIt, keyIt, mutp); 260 } end()261 iterator end() { return iterator(this); } end()262 const_iterator end() const { 263 // Safe to cast away const; the const_iterator will still enforce 264 // it. Same for the const begin() below. 265 return const_iterator(const_cast<SortByValueMap*>(this)); 266 } rbegin()267 reverse_iterator rbegin() { return reverse_iterator(end()); } rend()268 reverse_iterator rend() { return reverse_iterator(begin()); } rbegin()269 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } rend()270 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 271 find(const T_Key & k)272 iterator find(const T_Key& k) { 273 const auto kvit = m_keys.find(k); 274 if (kvit == m_keys.end()) return end(); 275 276 const auto valIt = m_vals.find(kvit->second); 277 const auto keyIt = valIt->second.find(k); 278 return iterator(valIt, keyIt, this); 279 } find(const T_Key & k)280 const_iterator find(const T_Key& k) const { 281 SortByValueMap* const mutp = const_cast<SortByValueMap*>(this); 282 const auto kvit = mutp->m_keys.find(k); 283 if (kvit == mutp->m_keys.end()) return end(); 284 285 const auto valIt = mutp->m_vals.find(kvit->second); 286 const auto keyIt = valIt->second.find(k); 287 return const_iterator(valIt, keyIt, mutp); 288 } set(const T_Key & k,const T_Value & v)289 void set(const T_Key& k, const T_Value& v) { 290 const auto kvit = m_keys.find(k); 291 if (kvit != m_keys.end()) { 292 if (kvit->second == v) { 293 return; // LCOV_EXCL_LINE // Same value already present; stop. 294 } 295 // Must remove element from m_vals[oldValue] 296 removeKeyFromOldVal(k, kvit->second); 297 } 298 m_keys[k] = v; 299 m_vals[v].insert(k); 300 } erase(const T_Key & k)301 size_t erase(const T_Key& k) { 302 const auto kvit = m_keys.find(k); 303 if (kvit == m_keys.end()) return 0; 304 removeKeyFromOldVal(k, kvit->second); 305 m_keys.erase(kvit); 306 return 1; 307 } erase(const iterator & it)308 void erase(const iterator& it) { 309 m_keys.erase(it.key()); 310 removeKeyFromOldVal(it); 311 } erase(const reverse_iterator & it)312 void erase(const reverse_iterator& it) { 313 erase(*it); // Dereferencing returns a copy of the forward iterator 314 } has(const T_Key & k)315 bool has(const T_Key& k) const { return (m_keys.find(k) != m_keys.end()); } empty()316 bool empty() const { return m_keys.empty(); } 317 // Look up a value. Returns a reference for efficiency. Note this must 318 // be a const reference, otherwise the client could corrupt the sorted 319 // order of m_byValue by reaching through and changing the value. at(const T_Key & k)320 const T_Value& at(const T_Key& k) const { 321 const auto kvit = m_keys.find(k); 322 UASSERT(kvit != m_keys.end(), "at() lookup key not found"); 323 return kvit->second; 324 } 325 326 private: 327 VL_UNCOPYABLE(SortByValueMap); 328 }; 329 330 //###################################################################### 331 332 /// V3Scoreboard takes a set of Elem*'s, each having some score. 333 /// Scores are assigned by a user-supplied scoring function. 334 /// 335 /// At any time, the V3Scoreboard can return the elem with the "best" score 336 /// among those elements whose scores are known. 337 /// 338 /// The best score is the _lowest_ score. This makes sense in contexts 339 /// where scores represent costs. 340 /// 341 /// The Scoreboard supports mutating element scores efficiently. The client 342 /// must hint to the V3Scoreboard when an element's score may have 343 /// changed. When it receives this hint, the V3Scoreboard will move the 344 /// element into the set of elements whose scores are unknown. Later the 345 /// client can tell V3Scoreboard to re-sort the list, which it does 346 /// incrementally, by re-scoring all elements whose scores are unknown, and 347 /// then moving these back into the score-sorted map. This is efficient 348 /// when the subset of elements whose scores change is much smaller than 349 /// the full set size. 350 351 template <typename T_Elem, typename T_Score, class T_ElemCompare = std::less<T_Elem>> 352 class V3Scoreboard final { 353 private: 354 // TYPES 355 class CmpElems final { 356 public: operator()357 bool operator()(const T_Elem* const& ap, const T_Elem* const& bp) const { 358 const T_ElemCompare cmp; 359 return cmp.operator()(*ap, *bp); 360 } 361 }; 362 using SortedMap = SortByValueMap<const T_Elem*, T_Score, CmpElems>; 363 using UserScoreFnp = T_Score (*)(const T_Elem*); 364 365 // MEMBERS 366 // Below uses set<> not an unordered_set<>. unordered_set::clear() and 367 // construction results in a 491KB clear operation to zero all the 368 // buckets. Since the set size is generally small, and we iterate the 369 // set members, set is better performant. 370 std::set<const T_Elem*> m_unknown; // Elements with unknown scores 371 SortedMap m_sorted; // Set of elements with known scores 372 const UserScoreFnp m_scoreFnp; // Scoring function 373 const bool m_slowAsserts; // Do some asserts that require extra lookups 374 375 public: 376 // CONSTRUCTORS V3Scoreboard(UserScoreFnp scoreFnp,bool slowAsserts)377 explicit V3Scoreboard(UserScoreFnp scoreFnp, bool slowAsserts) 378 : m_scoreFnp{scoreFnp} 379 , m_slowAsserts{slowAsserts} {} 380 ~V3Scoreboard() = default; 381 382 // METHODS 383 384 // Add an element to the scoreboard. 385 // Element begins in needs-rescore state; it won't be returned by 386 // bestp() until after the next rescore(). addElem(const T_Elem * elp)387 void addElem(const T_Elem* elp) { 388 if (m_slowAsserts) { 389 UASSERT(!contains(elp), "Adding element to scoreboard that was already in scoreboard"); 390 } 391 m_unknown.insert(elp); 392 } 393 394 // Remove elp from scoreboard. removeElem(const T_Elem * elp)395 void removeElem(const T_Elem* elp) { 396 if (0 == m_sorted.erase(elp)) { 397 UASSERT(m_unknown.erase(elp), 398 "Could not find requested elem to remove from scoreboard"); 399 } 400 } 401 402 // Returns true if elp is present in the scoreboard, false otherwise. 403 // 404 // Note: every other V3Scoreboard routine that takes an T_Elem* has 405 // undefined behavior if the element is not in the scoreboard. contains(const T_Elem * elp)406 bool contains(const T_Elem* elp) const { 407 if (m_unknown.find(elp) != m_unknown.end()) return true; 408 return (m_sorted.find(elp) != m_sorted.end()); 409 } 410 411 // Get the best element, with the lowest score (lower is better), among 412 // elements whose scores are known. Returns nullptr if no elements with 413 // known scores exist. 414 // 415 // Note: This does not automatically rescore. Client must call 416 // rescore() periodically to ensure all elems in the scoreboard are 417 // reflected in the result of bestp(). Otherwise, bestp() only 418 // considers elements that aren't pending rescore. bestp()419 const T_Elem* bestp() { 420 const auto result = m_sorted.begin(); 421 if (VL_UNLIKELY(result == m_sorted.end())) return nullptr; 422 return (*result).key(); 423 } 424 425 // Tell the scoreboard that this element's score may have changed. 426 // 427 // At the time of this call, the element's score becomes "unknown" 428 // to the V3Scoreboard. Unknown elements won't be returned by bestp(). 429 // The element's score will remain unknown until the next rescore(). 430 // 431 // The client MUST call this for each element whose score has changed. 432 // 433 // The client MAY call this for elements whose score has not changed. 434 // Doing so incurs some compute cost (to re-sort the element back to 435 // its original location) and still makes it ineligible to be returned 436 // by bestp() until the next rescore(). hintScoreChanged(const T_Elem * elp)437 void hintScoreChanged(const T_Elem* elp) { 438 m_unknown.insert(elp); 439 m_sorted.erase(elp); 440 } 441 442 // True if any element's score is unknown to V3Scoreboard. needsRescore()443 bool needsRescore() { return !m_unknown.empty(); } 444 // False if elp's score is known to V3Scoreboard, 445 // else true if elp's score is unknown until the next rescore(). needsRescore(const T_Elem * elp)446 bool needsRescore(const T_Elem* elp) { return (m_unknown.find(elp) != m_unknown.end()); } 447 // Retrieve the last known score for an element. cachedScore(const T_Elem * elp)448 T_Score cachedScore(const T_Elem* elp) { 449 const auto result = m_sorted.find(elp); 450 UASSERT(result != m_sorted.end(), "V3Scoreboard::cachedScore() failed to find element"); 451 return (*result).value(); 452 } 453 // For each element whose score is unknown to V3Scoreboard, 454 // call the client's scoring function to get a new score, 455 // and sort all elements by their current score. rescore()456 void rescore() { 457 for (const T_Elem* elp : m_unknown) { 458 const T_Score sortScore = m_scoreFnp(elp); 459 m_sorted.set(elp, sortScore); 460 } 461 m_unknown.clear(); 462 } 463 464 private: 465 VL_UNCOPYABLE(V3Scoreboard); 466 }; 467 468 //###################################################################### 469 470 namespace V3ScoreboardBase { 471 void selfTest(); 472 } // namespace V3ScoreboardBase 473 474 #endif // Guard 475