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

Last change on this file since 4717 was 4717, checked in by cameron, 4 years ago

Mod64Advance, Mod64MatchStar, Mod64ScanThru ops; -mod64-approximate command-line option

File size: 10.2 KB
RevLine 
[4416]1#ifndef EXPRESSION_MAP_HPP
2#define EXPRESSION_MAP_HPP
3
[4681]4#include <pablo/pabloAST.h>
[4684]5#include <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>
32    inline 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
43    inline std::pair<PabloAST *, bool> findOrAdd(PabloAST * object, const PabloAST::ClassTypeId type, Args... args) {
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
53    inline bool erase(const PabloAST::ClassTypeId type, Args... args) {
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
[4416]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:
[4681]91    Type *                      mPredecessor;
[4416]92    std::map<Key, PabloAST *>   mMap;
93};
94
[4684]95
96struct VarArgMap {
97
98    friend struct ExpressionTable;
99
[4692]100    using Allocator = LLVMAllocator;
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())
107        , mArg(allocator.Allocate<const PabloAST *>(mArgs)) {
108            unsigned i = 1;
109            mArg[0] = arg1;
110            for (PabloAST * arg : args) {
111                mArg[i++] = arg;
112            }
113        }
114
[4684]115        inline Key(const Key & key) = default;
[4692]116
[4684]117        inline Key(Key && key) = default;
[4692]118
[4684]119        inline bool operator < (const Key & other) const {
[4692]120            if (mType != other.mType) {
[4684]121                return mType < other.mType;
[4692]122            } else if (mArgs != other.mArgs) {
[4684]123                return mArgs < other.mArgs;
[4692]124            }
[4684]125            for (unsigned i = 0; i != mArgs; ++i) {
126                if (mArg[i] != other.mArg[i]) {
127                    return mArg[i] < other.mArg[i];
128                }
129            }
130            return false;
131        }
[4692]132
133        const PabloAST::ClassTypeId   mType;
134        const unsigned                mArgs;
135        const PabloAST **             mArg;
[4684]136    };
137
[4692]138    using Map = std::map<Key, PabloAST *>;
[4684]139
140    explicit VarArgMap(VarArgMap * predecessor = nullptr)
141    : mPredecessor(predecessor) {
142
143    }
144
145    explicit VarArgMap(VarArgMap && other) noexcept
146    : mPredecessor(other.mPredecessor)
147    , mMap(std::move(other.mMap)) {
148
149    }
150
151    VarArgMap & operator=(VarArgMap && other) {
152        mPredecessor = other.mPredecessor;
153        mMap = std::move(other.mMap);
154        return *this;
155    }
156
157    template <class Functor, typename... Params>
[4692]158    inline PabloAST * findOrCall(Functor && functor, const PabloAST::ClassTypeId type, const PabloAST * arg1, const std::vector<PabloAST *> & args, Params... params) {
159        Key key(type, arg1, args, mAllocator);
160        PabloAST * const f = find(key);
[4684]161        if (f) {
[4692]162            mAllocator.Deallocate<const PabloAST *>(key.mArg);
[4684]163            return f;
164        }
165        PabloAST * const object = functor(args, std::forward<Params>(params)...);
166        mMap.insert(std::make_pair(std::move(key), object));
167        return object;
168    }
169
[4692]170    inline std::pair<PabloAST *, bool> findOrAdd(PabloAST * object, const PabloAST::ClassTypeId type, PabloAST * arg1, const std::vector<PabloAST *> & args) {
171        Key key(type, arg1, args, mAllocator);
172        PabloAST * const entry = find(key);
[4684]173        if (entry) {
[4692]174            mAllocator.Deallocate<const PabloAST *>(key.mArg);
[4684]175            return std::make_pair(entry, false);
176        }
177        mMap.insert(std::make_pair(std::move(key), object));
178        return std::make_pair(object, true);
179    }
180
181private:
182
[4692]183    inline PabloAST * find(const Key & key) const {
[4684]184        // check this map to see if we have it
185        auto itr = mMap.find(key);
186        if (itr != mMap.end()) {
187            return itr->second;
188        }
189        // check any previous maps to see if it exists
190        auto * pred = mPredecessor;
191        while (pred) {
192            itr = pred->mMap.find(key);
193            if (itr == pred->mMap.end()) {
194                pred = pred->mPredecessor;
195                continue;
196            }
197            return itr->second;
198        }
199        return nullptr;
200    }
201
202private:
203    VarArgMap *     mPredecessor;
[4692]204    Map             mMap;
[4684]205    Allocator       mAllocator;
206};
207
[4416]208struct ExpressionTable {
209
[4681]210    explicit ExpressionTable(ExpressionTable * predecessor = nullptr) noexcept {
[4646]211        if (predecessor) {
212            mUnary.mPredecessor = &(predecessor->mUnary);
213            mBinary.mPredecessor = &(predecessor->mBinary);
214            mTernary.mPredecessor = &(predecessor->mTernary);
[4692]215            mVariable.mPredecessor = &(predecessor->mVariable);
[4646]216        }
[4416]217    }
218
[4646]219    explicit ExpressionTable(ExpressionTable & other) = delete;
[4416]220
[4646]221    explicit ExpressionTable(ExpressionTable && other) noexcept
222    : mUnary(std::move(other.mUnary))
223    , mBinary(std::move(other.mBinary))
[4681]224    , mTernary(std::move(other.mTernary))
[4692]225    , mVariable(std::move(other.mVariable)) {
[4646]226
[4416]227    }
228
[4646]229    ExpressionTable & operator=(ExpressionTable && other) {
230        mUnary = std::move(other.mUnary);
231        mBinary = std::move(other.mBinary);
232        mTernary = std::move(other.mTernary);
[4692]233        mVariable = std::move(other.mVariable);
[4646]234        return *this;
235    }
[4641]236
[4443]237    template <class Functor, typename... Params>
238    inline PabloAST * findUnaryOrCall(Functor && functor, const PabloAST::ClassTypeId type, PabloAST * expr, Params... params) {
[4684]239        return mUnary.findOrCall(std::move(functor), type,  expr , std::forward<Params>(params)...);
[4443]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
[4692]252    template <class Functor, typename... Params>
253    inline PabloAST * findVariableOrCall(Functor && functor, const PabloAST::ClassTypeId type, const PabloAST * arg1, const std::vector<PabloAST *> & args, Params... params) {
254        return mVariable.findOrCall(std::move(functor), type, arg1, args, std::forward<Params>(params)...);
255    }
[4681]256
[4443]257    std::pair<PabloAST *, bool> findOrAdd(Statement * stmt) {
[4432]258        switch (stmt->getClassTypeId()) {           
[4681]259            case PabloAST::ClassTypeId::Assign:           
[4416]260            case PabloAST::ClassTypeId::Var:
261            case PabloAST::ClassTypeId::Not:
[4443]262                return mUnary.findOrAdd(stmt, stmt->getClassTypeId(), stmt->getOperand(0));
[4416]263            case PabloAST::ClassTypeId::And:
264            case PabloAST::ClassTypeId::Or:
265            case PabloAST::ClassTypeId::Xor:
[4695]266                // test whether the communative version of this statement exists
267                if (PabloAST * commExpr = mBinary.find(stmt->getClassTypeId(), stmt->getOperand(1), stmt->getOperand(0))) {
268                    return std::make_pair(commExpr, false);
269                }
[4432]270            case PabloAST::ClassTypeId::Advance:
[4416]271            case PabloAST::ClassTypeId::ScanThru:
272            case PabloAST::ClassTypeId::MatchStar:
[4717]273            case PabloAST::ClassTypeId::Mod64Advance:
274            case PabloAST::ClassTypeId::Mod64ScanThru:
275            case PabloAST::ClassTypeId::Mod64MatchStar:
[4416]276            case PabloAST::ClassTypeId::Next:
[4443]277                return mBinary.findOrAdd(stmt, stmt->getClassTypeId(), stmt->getOperand(0), stmt->getOperand(1));
[4416]278            case PabloAST::ClassTypeId::Sel:
[4443]279                return mTernary.findOrAdd(stmt, stmt->getClassTypeId(), stmt->getOperand(0), stmt->getOperand(1), stmt->getOperand(2));
[4681]280            case PabloAST::ClassTypeId::Call:
281                // temporarily ignored
[4416]282            default:
283                return std::make_pair(stmt, true);
284        }
285    }
286
287
288private:
[4692]289    FixedArgMap<PabloAST *>                             mUnary;
290    FixedArgMap<PabloAST *, PabloAST *>                 mBinary;
291    FixedArgMap<PabloAST *, PabloAST *, PabloAST *>     mTernary;
292    VarArgMap                                           mVariable;
[4416]293};
294
295}
296
297#endif // EXPRESSION_MAP_HPP
Note: See TracBrowser for help on using the repository browser.