source: icGREP/icgrep-devel/icgrep/pablo/expression_map.hpp @ 4685

Last change on this file since 4685 was 4684, checked in by nmedfort, 4 years ago

First attempt to intergrate 'generate_predefined_ucd_functions' into build process.

File size: 10.3 KB
Line 
1#ifndef EXPRESSION_MAP_HPP
2#define EXPRESSION_MAP_HPP
3
4#include <pablo/pabloAST.h>
5#include <slab_allocator.h>
6#include <map>
7
8namespace pablo {
9
10template<typename... Args>
11struct FixedArgMap {
12    enum {N = sizeof...(Args)};
13    typedef FixedArgMap<Args...> Type;
14    typedef std::tuple<PabloAST::ClassTypeId, Args...> Key;
15    friend struct ExpressionTable;
16
17    explicit FixedArgMap(Type * predecessor = nullptr) : mPredecessor(predecessor) { }
18
19    explicit FixedArgMap(Type && other) noexcept
20    : mPredecessor(other.mPredecessor)
21    , mMap(std::move(other.mMap)) {
22
23    }
24
25    FixedArgMap & operator=(Type && other) {
26        mPredecessor = other.mPredecessor;
27        mMap = std::move(other.mMap);
28        return *this;
29    }
30
31    template <class Functor, typename... Params>
32    inline PabloAST * findOrCall(Functor && functor, const PabloAST::ClassTypeId type, Args... args, Params... params) {
33        Key key = std::make_tuple(type, args...);
34        PabloAST * const f = find(key);
35        if (f) {
36            return f;
37        }
38        PabloAST * const object = functor(std::forward<Args>(args)..., std::forward<Params>(params)...);
39        mMap.insert(std::make_pair(std::move(key), object));
40        return object;
41    }
42
43    inline std::pair<PabloAST *, bool> findOrAdd(PabloAST * object, const PabloAST::ClassTypeId type, Args... args) {
44        Key key = std::make_tuple(type, args...);
45        PabloAST * const entry = find(key);
46        if (entry) {
47            return std::make_pair(entry, false);
48        }
49        mMap.insert(std::make_pair(std::move(key), object));
50        return std::make_pair(object, true);
51    }
52
53    inline bool erase(const PabloAST::ClassTypeId type, Args... args) {
54        Key key = std::make_tuple(type, args...);
55        for (Type * obj = this; obj; obj = obj->mPredecessor) {
56            auto itr = obj->mMap.find(key);
57            if (itr != mMap.end()) {
58                obj->mMap.erase(itr);
59                return true;
60            }
61        }
62        return false;
63    }
64
65    inline PabloAST * find(const PabloAST::ClassTypeId type, Args... args) const {
66        return find(std::make_tuple(type, args...));
67    }
68
69private:
70
71    inline PabloAST * find(const Key & key) const {
72        // check this map to see if we have it
73        auto itr = mMap.find(key);
74        if (itr != mMap.end()) {
75            return itr->second;
76        }
77        // check any previous maps to see if it exists
78        auto * pred = mPredecessor;
79        while (pred) {
80            itr = pred->mMap.find(key);
81            if (itr == pred->mMap.end()) {
82                pred = pred->mPredecessor;
83                continue;
84            }
85            return itr->second;
86        }
87        return nullptr;
88    }
89
90private:
91    Type *                      mPredecessor;
92    std::map<Key, PabloAST *>   mMap;
93};
94
95
96struct VarArgMap {
97
98    friend struct ExpressionTable;
99
100    struct Key {
101        inline Key(PabloAST::ClassTypeId type, unsigned args, PabloAST ** arg) : mType(type), mArgs(args), mArg(arg) {}
102        inline Key(const Key & key) = default;
103        inline Key(Key && key) = default;
104        inline bool operator < (const Key & other) const {
105            if (mType != other.mType)
106                return mType < other.mType;
107            if (mArgs != other.mArgs)
108                return mArgs < other.mArgs;
109            for (unsigned i = 0; i != mArgs; ++i) {
110                if (mArg[i] != other.mArg[i]) {
111                    return mArg[i] < other.mArg[i];
112                }
113            }
114            return false;
115        }
116    private:
117        PabloAST::ClassTypeId         mType;
118        unsigned                      mArgs;
119        PabloAST **                   mArg;
120    };
121
122    using Allocator = LLVMAllocator;
123    using MapAllocator = LLVMAllocatorProxy<std::pair<Key, PabloAST *>>;
124    using Map = std::map<Key, PabloAST *>; // , std::less<Key>, MapAllocator
125
126    explicit VarArgMap(VarArgMap * predecessor = nullptr)
127    : mPredecessor(predecessor) {
128
129    }
130
131    explicit VarArgMap(VarArgMap && other) noexcept
132    : mPredecessor(other.mPredecessor)
133    , mMap(std::move(other.mMap)) {
134
135    }
136
137    VarArgMap & operator=(VarArgMap && other) {
138        mPredecessor = other.mPredecessor;
139        mMap = std::move(other.mMap);
140        return *this;
141    }
142
143    template <class Functor, typename... Params>
144    inline PabloAST * findOrCall(Functor && functor, const PabloAST::ClassTypeId type, std::initializer_list<PabloAST *> args, Params... params) {
145        PabloAST * const f = find(type, args);
146        if (f) {
147            return f;
148        }
149        PabloAST * const object = functor(args, std::forward<Params>(params)...);
150        PabloAST ** const args_copy = mAllocator.Allocate<PabloAST *>(args.size());
151        std::copy(args.begin(), args.end(), args_copy);
152        Key key(type, args.size(), args_copy);
153        mMap.insert(std::make_pair(std::move(key), object));
154        return object;
155    }
156
157    inline std::pair<PabloAST *, bool> findOrAdd(PabloAST * object, const PabloAST::ClassTypeId type, std::initializer_list<PabloAST *> args) {
158        PabloAST * const entry = find(type, args);
159        if (entry) {
160            return std::make_pair(entry, false);
161        }
162        PabloAST ** const args_copy = mAllocator.Allocate<PabloAST *>(args.size());
163        std::copy(args.begin(), args.end(), args_copy);
164        Key key(type, args.size(), args_copy);
165        mMap.insert(std::make_pair(std::move(key), object));
166        return std::make_pair(object, true);
167    }
168
169    inline PabloAST * find(const PabloAST::ClassTypeId type, const std::initializer_list<PabloAST *> args) const {
170        PabloAST * value[args.size()];
171        std::copy(args.begin(), args.end(), value);
172        return find(std::move(Key(type, args.size(), value)));
173    }
174
175private:
176
177    inline PabloAST * find(Key && key) const {
178        // check this map to see if we have it
179        auto itr = mMap.find(key);
180        if (itr != mMap.end()) {
181            return itr->second;
182        }
183        // check any previous maps to see if it exists
184        auto * pred = mPredecessor;
185        while (pred) {
186            itr = pred->mMap.find(key);
187            if (itr == pred->mMap.end()) {
188                pred = pred->mPredecessor;
189                continue;
190            }
191            return itr->second;
192        }
193        return nullptr;
194    }
195
196private:
197    VarArgMap *     mPredecessor;
198    Allocator       mAllocator;
199    Map             mMap;
200};
201
202struct ExpressionTable {
203
204    explicit ExpressionTable(ExpressionTable * predecessor = nullptr) noexcept {
205        if (predecessor) {
206            mUnary.mPredecessor = &(predecessor->mUnary);
207            mBinary.mPredecessor = &(predecessor->mBinary);
208            mTernary.mPredecessor = &(predecessor->mTernary);
209            mUnaryVariable.mPredecessor = &(predecessor->mUnaryVariable);
210        }
211    }
212
213    explicit ExpressionTable(ExpressionTable & other) = delete;
214
215    explicit ExpressionTable(ExpressionTable && other) noexcept
216    : mUnary(std::move(other.mUnary))
217    , mBinary(std::move(other.mBinary))
218    , mTernary(std::move(other.mTernary))
219    , mUnaryVariable(std::move(other.mUnaryVariable)) {
220
221    }
222
223    ExpressionTable & operator=(ExpressionTable && other) {
224        mUnary = std::move(other.mUnary);
225        mBinary = std::move(other.mBinary);
226        mTernary = std::move(other.mTernary);
227        mUnaryVariable = std::move(other.mUnaryVariable);
228        return *this;
229    }
230
231
232    template <class Functor, typename... Params>
233    inline PabloAST * findUnaryOrCall(Functor && functor, const PabloAST::ClassTypeId type, PabloAST * expr, Params... params) {
234        return mUnary.findOrCall(std::move(functor), type,  expr , std::forward<Params>(params)...);
235    }
236
237    template <class Functor, typename... Params>
238    inline PabloAST * findUnaryVariableOrCall(Functor && functor, const PabloAST::ClassTypeId type, PabloAST * expr, const std::vector<PabloAST *> & args, Params... params) {
239        return mUnaryVariable.findOrCall(std::move(functor), type, expr, args, std::forward<Params>(params)...);
240    }
241
242    template <class Functor, typename... Params>
243    inline PabloAST * findBinaryOrCall(Functor && functor, const PabloAST::ClassTypeId type, PabloAST * expr1, PabloAST * expr2, Params... params) {
244        return mBinary.findOrCall(std::move(functor), type, expr1, expr2, std::forward<Params>(params)...);
245    }
246
247    template <class Functor, typename... Params>
248    inline PabloAST * findTernaryOrCall(Functor && functor, const PabloAST::ClassTypeId type, PabloAST * expr1, PabloAST * expr2, PabloAST * expr3, Params... params) {
249        return mTernary.findOrCall(std::move(functor), type, expr1, expr2, expr3, std::forward<Params>(params)...);
250    }
251
252
253    std::pair<PabloAST *, bool> findOrAdd(Statement * stmt) {
254        switch (stmt->getClassTypeId()) {           
255            case PabloAST::ClassTypeId::Assign:           
256            case PabloAST::ClassTypeId::Var:
257            case PabloAST::ClassTypeId::Not:
258                return mUnary.findOrAdd(stmt, stmt->getClassTypeId(), stmt->getOperand(0));
259            case PabloAST::ClassTypeId::And:
260            case PabloAST::ClassTypeId::Or:
261            case PabloAST::ClassTypeId::Xor:
262                // test whether the communative version of this statement exists
263                if (PabloAST * commExpr = mBinary.find(stmt->getClassTypeId(), stmt->getOperand(1), stmt->getOperand(0))) {
264                    return std::make_pair(commExpr, false);
265                }
266            case PabloAST::ClassTypeId::Advance:
267            case PabloAST::ClassTypeId::ScanThru:
268            case PabloAST::ClassTypeId::MatchStar:
269            case PabloAST::ClassTypeId::Next:
270                return mBinary.findOrAdd(stmt, stmt->getClassTypeId(), stmt->getOperand(0), stmt->getOperand(1));
271            case PabloAST::ClassTypeId::Sel:
272                return mTernary.findOrAdd(stmt, stmt->getClassTypeId(), stmt->getOperand(0), stmt->getOperand(1), stmt->getOperand(2));
273            case PabloAST::ClassTypeId::Call:
274                // temporarily ignored
275            default:
276                return std::make_pair(stmt, true);
277        }
278    }
279
280
281private:
282    FixedArgMap<PabloAST *>                                     mUnary;
283    FixedArgMap<PabloAST *, PabloAST *>                         mBinary;
284    FixedArgMap<PabloAST *, PabloAST *, PabloAST *>             mTernary;
285    FixedArgMap<PabloAST *, const std::vector<PabloAST *> &>    mUnaryVariable;
286};
287
288}
289
290#endif // EXPRESSION_MAP_HPP
Note: See TracBrowser for help on using the repository browser.