MLIR-AIE 1.4.6.dev
AIEBoundedMemo.h
Go to the documentation of this file.
1//===- AIEBoundedMemo.h -----------------------------------------*- C++ -*-===//
2//
3// Copyright (C) 2026 Advanced Micro Devices, Inc.
4// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5//
6//===----------------------------------------------------------------------===//
7
8#ifndef AIE_DIALECT_AIE_TRANSFORMS_AIEBOUNDEDMEMO_H
9#define AIE_DIALECT_AIE_TRANSFORMS_AIEBOUNDEDMEMO_H
10
11#include "llvm/ADT/Hashing.h"
12
13#include <list>
14#include <unordered_map>
15#include <vector>
16
17namespace xilinx::AIE {
18
19/// Hashes a vector key by its elements.
21 template <typename T>
22 size_t operator()(const std::vector<T> &key) const {
23 return llvm::hash_combine_range(key.begin(), key.end());
24 }
25};
26
27/// A memo that keeps its `capacity` most recently used results, each key
28/// stored once.
29template <typename Key, typename Value, typename Hash = VectorKeyHash>
31public:
32 explicit BoundedMemo(size_t capacity) : capacity(capacity) {}
33
34 /// The result recorded for `key`, now the most recently used, or null.
35 /// Valid until the next record().
36 const Value *find(const Key &key) {
37 auto it = entries.find(key);
38 if (it == entries.end())
39 return nullptr;
40 order.splice(order.begin(), order, it->second.used);
41 return &it->second.value;
42 }
43
44 /// Records `value` for `key`, replacing any result it had, and forgets the
45 /// least recently used result past `capacity`.
46 void record(Key key, Value value) {
47 auto [it, added] = entries.try_emplace(std::move(key));
48 it->second.value = std::move(value);
49 if (!added) {
50 order.splice(order.begin(), order, it->second.used);
51 return;
52 }
53 order.push_front(&it->first);
54 it->second.used = order.begin();
55 if (entries.size() > capacity) {
56 auto oldest = entries.find(*order.back());
57 order.pop_back();
58 entries.erase(oldest);
59 }
60 }
61
62 void clear() {
63 order.clear();
64 entries.clear();
65 }
66
67private:
68 // Keys live in `entries`' nodes, which never move; `order` points at them,
69 // most recently used first.
70 struct Entry {
71 Value value;
72 typename std::list<const Key *>::iterator used;
73 };
74 size_t capacity;
75 std::unordered_map<Key, Entry, Hash> entries;
76 std::list<const Key *> order;
77};
78
79} // namespace xilinx::AIE
80
81#endif // AIE_DIALECT_AIE_TRANSFORMS_AIEBOUNDEDMEMO_H
void record(Key key, Value value)
Records value for key, replacing any result it had, and forgets the least recently used result past c...
const Value * find(const Key &key)
The result recorded for key, now the most recently used, or null.
BoundedMemo(size_t capacity)
Hashes a vector key by its elements.
size_t operator()(const std::vector< T > &key) const