source: icGREP/icgrep-devel/icgrep/pablo/pabloAST.h @ 4718

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

add Pablo count operation - not yet functional

File size: 13.0 KB
Line 
1/*
2 *  Copyright (c) 2014 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#ifndef PE_PabloAST_H
8#define PE_PabloAST_H
9
10#include <llvm/Support/Casting.h>
11#include <llvm/Support/Compiler.h>
12#include <vector>
13#include <slab_allocator.h>
14#include <iterator>
15#include <unordered_map>
16
17using namespace llvm;
18
19namespace pablo {
20
21class PabloBlock;
22class String;
23
24class PabloAST {
25    friend class Statement;
26    friend class Var;
27    friend class If;   
28    friend class While;
29    friend class PabloBlock;
30    friend class Prototype;
31    friend class PabloFunction;
32    friend class SymbolGenerator;
33public:
34
35    using Allocator = SlabAllocator<u_int8_t>;
36    using VectorAllocator = SlabAllocator<PabloAST *>;
37    using Vector = std::vector<PabloAST*, VectorAllocator>;
38    using user_iterator = Vector::iterator;
39    using const_user_iterator = Vector::const_iterator;
40
41    enum class ClassTypeId : unsigned {
42        /** Non-statements **/
43        // Constants
44        Zeroes
45        , Ones
46        // Internal types
47        , Var
48        , Integer
49        , String
50        , Block
51        , Function
52        , Prototype
53        /** Statements **/
54        // Boolean operations
55        , And
56        , Or
57        , Not
58        , Xor
59        , Sel
60        // Stream operations
61        , Advance
62        , ScanThru
63        , MatchStar
64        // Mod 64 approximate stream operations
65        , Mod64Advance
66        , Mod64ScanThru
67        , Mod64MatchStar
68        // Statistics operations
69        , Count
70        // Variable assignments
71        , Assign
72        , Next
73        , Call
74        , SetIthBit
75        // Scope blocks
76        , If
77        , While
78    };
79    inline ClassTypeId getClassTypeId() const {
80        return mClassTypeId;
81    }
82
83    inline user_iterator user_begin() {
84        return mUsers.begin();
85    }
86
87    inline user_iterator user_end() {
88        return mUsers.end();
89    }
90
91    inline const_user_iterator user_begin() const {
92        return mUsers.cbegin();
93    }
94
95    inline const_user_iterator user_end() const {
96        return mUsers.cend();
97    }
98
99    inline Vector & users() {
100        return mUsers;
101    }
102
103    inline const Vector & users() const {
104        return mUsers;
105    }
106
107    void replaceAllUsesWith(PabloAST * expr);
108
109    inline Vector::size_type getNumUses() const {
110        return mUsers.size();
111    }
112
113    void* operator new (std::size_t size) noexcept {
114        return mAllocator.allocate(size);
115    }
116protected:
117    inline PabloAST(const ClassTypeId id)
118    : mClassTypeId(id)
119    , mUsers(mVectorAllocator)
120    {
121
122    }
123    inline void addUser(PabloAST * user) {
124        assert (user);
125        auto pos = std::lower_bound(mUsers.begin(), mUsers.end(), user);
126        if (LLVM_UNLIKELY(pos != mUsers.end() && *pos == user)) {
127            return;
128        }
129        mUsers.insert(pos, user);
130    }
131    inline void removeUser(PabloAST * user) {
132        assert (user);
133        if (mUsers.empty()) {
134            return;
135        }
136        auto pos = std::lower_bound(mUsers.begin(), mUsers.end(), user);
137        if (LLVM_UNLIKELY(pos == mUsers.end() || *pos != user)) {
138            return;
139        }
140        mUsers.erase(pos);
141    }
142    virtual ~PabloAST() {
143        mUsers.clear();
144    }
145    static Allocator        mAllocator;
146private:
147    const ClassTypeId       mClassTypeId;
148    Vector                  mUsers;
149    static VectorAllocator  mVectorAllocator;
150};
151
152bool equals(const PabloAST * expr1, const PabloAST *expr2);
153
154class StatementList;
155
156class String;
157
158class Statement : public PabloAST {
159    friend class StatementList;
160    friend class If;
161    friend class While;
162    friend class Simplifier;
163    friend class PabloBlock;
164public:
165    static inline bool classof(const PabloAST * e) {
166        switch (e->getClassTypeId()) {
167            case PabloAST::ClassTypeId::Zeroes:
168            case PabloAST::ClassTypeId::Ones:
169            case PabloAST::ClassTypeId::Var:
170            case PabloAST::ClassTypeId::String:
171            case PabloAST::ClassTypeId::Integer:
172            case PabloAST::ClassTypeId::Block:
173            case PabloAST::ClassTypeId::Function:
174            case PabloAST::ClassTypeId::Prototype:
175                return false;
176            default:
177                return true;
178        }
179    }
180    static inline bool classof(const Statement *) {
181        return true;
182    }
183    static inline bool classof(const void *) {
184        return false;
185    }
186
187    inline void replaceUsesOfWith(const PabloAST * const from, PabloAST * const to) {
188        for (unsigned i = 0; i != getNumOperands(); ++i) {
189            if (getOperand(i) == from) {
190                setOperand(i, to);
191            }
192        }
193    }
194
195    inline PabloAST * getOperand(const unsigned index) const {
196        assert (index < getNumOperands());
197        return mOperand[index];
198    }
199
200    void setOperand(const unsigned index, PabloAST * const value);
201
202    inline unsigned getNumOperands() const {
203        return mOperands;
204    }
205
206    void insertBefore(Statement * const statement);
207    void insertAfter(Statement * const statement);
208    Statement * removeFromParent();
209    Statement * eraseFromParent(const bool recursively = false);
210    Statement * replaceWith(PabloAST * const expr, const bool rename = true, const bool recursively = false);
211
212    inline const String * getName() const {
213        return mName;
214    }
215    inline Statement * getNextNode() const {
216        return mNext;
217    }
218    inline Statement * getPrevNode() const {
219        return mPrev;
220    }
221    inline PabloBlock * getParent() const {
222        return mParent;
223    }
224    virtual ~Statement() {}
225protected:
226    Statement(const ClassTypeId id, std::initializer_list<PabloAST *> operands, const String * const name)
227    : PabloAST(id)
228    , mName(name)
229    , mNext(nullptr)
230    , mPrev(nullptr)
231    , mParent(nullptr)
232    , mOperands(operands.size())
233    , mOperand(reinterpret_cast<PabloAST**>(mAllocator.allocate(mOperands * sizeof(PabloAST *)))) {
234        unsigned i = 0;
235        for (PabloAST * const op : operands) {
236            mOperand[i++] = op;
237            if (LLVM_LIKELY(op != nullptr)) {
238                op->addUser(this);
239            }
240        }
241    }
242    inline void setName(const String * const name) {
243        mName = name;
244    }   
245#ifndef NDEBUG
246    bool noRecursiveOperand(const PabloAST * const operand);
247#endif
248protected:   
249    const String *              mName;
250    Statement *                 mNext;
251    Statement *                 mPrev;
252    PabloBlock *                mParent;
253    const unsigned              mOperands;
254    // If we knew prior to construction how many operands were needed, we could
255    // eliminate the mOperand pointer and simply use this[1] instead.
256    PabloAST **                 mOperand;
257};
258
259class StatementList {
260    friend class Statement;
261    friend class PabloBlock;
262public:
263    class iterator: public std::iterator<std::forward_iterator_tag, Statement> {
264    public:
265        iterator(): mCurrent(nullptr) {}
266
267        iterator(Statement* base): mCurrent(base) {}
268
269        iterator(const iterator& other): mCurrent(other.mCurrent) {}
270
271        const iterator& operator=(const iterator& other) {
272            mCurrent = other.mCurrent; return other;
273        }
274
275        inline iterator& operator++() {
276            assert (mCurrent);
277            mCurrent = mCurrent->mNext;
278            return *this;
279        }
280
281        iterator  operator++(int) {
282            iterator tmp(*this);
283            ++(*this);
284            return tmp;
285        }
286
287        bool operator==(const iterator& other) const {
288            return  mCurrent == other.mCurrent;
289        }
290
291        bool operator!=(const iterator& other) const {
292            return  mCurrent != other.mCurrent;
293        }
294
295        Statement* operator*() {return mCurrent;}
296        Statement* operator->(){return mCurrent;}
297
298    private:
299        Statement * mCurrent;
300        friend class const_iterator;
301    };
302
303    class const_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
304    public:
305        const_iterator(): mCurrent(nullptr) {}
306        const_iterator(const Statement* base): mCurrent(base) {}
307        const_iterator(const const_iterator& other): mCurrent(other.mCurrent) {}
308        const const_iterator& operator=(const const_iterator& other) {mCurrent = other.mCurrent; return other;}
309
310        inline const_iterator& operator++() {
311            assert (mCurrent);
312            mCurrent = mCurrent->mNext;
313            return *this;
314        }
315
316        const_iterator  operator++(int) {
317            const_iterator tmp(*this);
318            ++(*this);
319            return tmp;
320        }
321
322        bool operator==(const const_iterator & other) const {
323            return  mCurrent == other.mCurrent;
324        }
325        bool operator!=(const const_iterator & other) const {
326            return  mCurrent != other.mCurrent;
327        }
328
329        const Statement* operator*() {return mCurrent;}
330        const Statement* operator->(){return mCurrent;}
331
332    private:
333        const Statement * mCurrent;
334        friend struct iterator;
335    };
336
337    class reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
338    public:
339        reverse_iterator(): mCurrent(nullptr) {}
340
341        reverse_iterator(Statement* base): mCurrent(base) {}
342
343        reverse_iterator(const reverse_iterator& other): mCurrent(other.mCurrent) {}
344
345        const reverse_iterator& operator=(const reverse_iterator& other) {
346            mCurrent = other.mCurrent; return other;
347        }
348
349        inline reverse_iterator& operator++() {
350            assert (mCurrent);
351            mCurrent = mCurrent->mPrev;
352            return *this;
353        }
354
355        reverse_iterator operator++(int) {
356            reverse_iterator tmp(*this);
357            ++(*this);
358            return tmp;
359        }
360
361        bool operator==(const reverse_iterator& other) const {
362            return  mCurrent == other.mCurrent;
363        }
364
365        bool operator!=(const reverse_iterator& other) const {
366            return  mCurrent != other.mCurrent;
367        }
368
369        Statement* operator*() {return mCurrent;}
370        Statement* operator->(){return mCurrent;}
371
372    private:
373        Statement * mCurrent;
374        friend class const_reverse_iterator;
375    };
376
377    class const_reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
378    public:
379        const_reverse_iterator(): mCurrent(nullptr) {}
380        const_reverse_iterator(const Statement* base): mCurrent(base) {}
381        const_reverse_iterator(const const_reverse_iterator& other): mCurrent(other.mCurrent) {}
382        const const_reverse_iterator& operator=(const const_reverse_iterator& other) {mCurrent = other.mCurrent; return other;}
383
384        inline const_reverse_iterator& operator++() {
385            assert (mCurrent);
386            mCurrent = mCurrent->mPrev;
387            return *this;
388        }
389
390        const_reverse_iterator  operator++(int) {
391            const_reverse_iterator tmp(*this);
392            ++(*this);
393            return tmp;
394        }
395
396        bool operator==(const const_reverse_iterator & other) const {
397            return  mCurrent == other.mCurrent;
398        }
399        bool operator!=(const const_reverse_iterator & other) const {
400            return  mCurrent != other.mCurrent;
401        }
402
403        const Statement* operator*() {return mCurrent;}
404        const Statement* operator->(){return mCurrent;}
405
406    private:
407        const Statement * mCurrent;
408        friend struct iterator;
409    };
410
411public:
412
413    StatementList()
414    : mInsertionPoint(nullptr)
415    , mFirst(nullptr)
416    , mLast(nullptr)
417    {
418
419    }
420
421    StatementList(StatementList && other)
422    : mFirst(other.mFirst)
423    , mLast(other.mLast)
424    {
425        other.mFirst = nullptr;
426        other.mLast = nullptr;
427    }
428
429    iterator begin() {
430        return iterator(mFirst);
431    }
432
433    iterator end() {
434        return iterator(nullptr);
435    }
436
437    reverse_iterator rbegin() {
438        return reverse_iterator(mLast);
439    }
440
441    reverse_iterator rend() {
442        return reverse_iterator(nullptr);
443    }
444
445    const_iterator begin() const {
446        return const_iterator(mFirst);
447    }
448
449    const_iterator end() const {
450        return const_iterator(nullptr);
451    }
452
453    const_reverse_iterator rbegin() const {
454        return const_reverse_iterator(mLast);
455    }
456
457    const_reverse_iterator rend() const {
458        return const_reverse_iterator(nullptr);
459    }
460
461    const_iterator cbegin() const {
462        return const_iterator(mFirst);
463    }
464
465    const_iterator cend() const {
466        return const_iterator(nullptr);
467    }
468
469    const_reverse_iterator crbegin() const {
470        return const_reverse_iterator(mLast);
471    }
472
473    const_reverse_iterator crend() const {
474        return const_reverse_iterator(nullptr);
475    }
476
477    inline Statement * front() const {
478        return mFirst;
479    }
480
481    inline Statement * back() const {
482        return mLast;
483    }
484
485    inline void setInsertPoint(Statement * const statement) {
486        mInsertionPoint = statement;
487    }
488
489    inline Statement * getInsertPoint() const {
490        return mInsertionPoint;
491    }
492
493    ~StatementList();
494
495private:
496
497    Statement   * mInsertionPoint;
498    Statement   * mFirst;
499    Statement   * mLast;   
500};
501
502}
503
504#endif // PE_PabloAST_H
505
506
507
Note: See TracBrowser for help on using the repository browser.