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

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

First stage in making And/Or/Xor? statements n-ary statements.

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