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

Last change on this file since 5239 was 5230, checked in by nmedfort, 3 years ago

Multi-threading support for PabloAST / PabloCompiler?. Requires unique LLVM Context / Module for each thread.

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