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