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

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

Back up check in. Memory leaks should be fixed.

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 checkForReplacementInEscapedValueList(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 checkForReplacementInEscapedValueList(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    const unsigned              mOperands;
256    // If we knew prior to construction how many operands were needed, we could
257    // eliminate the mOperand pointer and simply use this[1] instead.
258    PabloAST **                 mOperand;
259};
260
261bool escapes(const Statement * statement);
262
263class StatementList {
264    friend class Statement;
265    friend class PabloBlock;
266public:
267    class iterator: public std::iterator<std::forward_iterator_tag, Statement> {
268    public:
269        iterator(): mCurrent(nullptr) {}
270
271        iterator(Statement* base): mCurrent(base) {}
272
273        iterator(const iterator& other): mCurrent(other.mCurrent) {}
274
275        const iterator& operator=(const iterator& other) {
276            mCurrent = other.mCurrent; return other;
277        }
278
279        inline iterator& operator++() {
280            assert (mCurrent);
281            mCurrent = mCurrent->mNext;
282            return *this;
283        }
284
285        iterator  operator++(int) {
286            iterator tmp(*this);
287            ++(*this);
288            return tmp;
289        }
290
291        bool operator==(const iterator& other) const {
292            return  mCurrent == other.mCurrent;
293        }
294
295        bool operator!=(const iterator& other) const {
296            return  mCurrent != other.mCurrent;
297        }
298
299        Statement* operator*() {return mCurrent;}
300        Statement* operator->(){return mCurrent;}
301
302    private:
303        Statement * mCurrent;
304        friend class const_iterator;
305    };
306
307    class const_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
308    public:
309        const_iterator(): mCurrent(nullptr) {}
310        const_iterator(const Statement* base): mCurrent(base) {}
311        const_iterator(const const_iterator& other): mCurrent(other.mCurrent) {}
312        const const_iterator& operator=(const const_iterator& other) {mCurrent = other.mCurrent; return other;}
313
314        inline const_iterator& operator++() {
315            assert (mCurrent);
316            mCurrent = mCurrent->mNext;
317            return *this;
318        }
319
320        const_iterator  operator++(int) {
321            const_iterator tmp(*this);
322            ++(*this);
323            return tmp;
324        }
325
326        bool operator==(const const_iterator & other) const {
327            return  mCurrent == other.mCurrent;
328        }
329        bool operator!=(const const_iterator & other) const {
330            return  mCurrent != other.mCurrent;
331        }
332
333        const Statement* operator*() {return mCurrent;}
334        const Statement* operator->(){return mCurrent;}
335
336    private:
337        const Statement * mCurrent;
338        friend struct iterator;
339    };
340
341    class reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
342    public:
343        reverse_iterator(): mCurrent(nullptr) {}
344
345        reverse_iterator(Statement* base): mCurrent(base) {}
346
347        reverse_iterator(const reverse_iterator& other): mCurrent(other.mCurrent) {}
348
349        const reverse_iterator& operator=(const reverse_iterator& other) {
350            mCurrent = other.mCurrent; return other;
351        }
352
353        inline reverse_iterator& operator++() {
354            assert (mCurrent);
355            mCurrent = mCurrent->mPrev;
356            return *this;
357        }
358
359        reverse_iterator operator++(int) {
360            reverse_iterator tmp(*this);
361            ++(*this);
362            return tmp;
363        }
364
365        bool operator==(const reverse_iterator& other) const {
366            return  mCurrent == other.mCurrent;
367        }
368
369        bool operator!=(const reverse_iterator& other) const {
370            return  mCurrent != other.mCurrent;
371        }
372
373        Statement* operator*() {return mCurrent;}
374        Statement* operator->(){return mCurrent;}
375
376    private:
377        Statement * mCurrent;
378        friend class const_reverse_iterator;
379    };
380
381    class const_reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
382    public:
383        const_reverse_iterator(): mCurrent(nullptr) {}
384        const_reverse_iterator(const Statement* base): mCurrent(base) {}
385        const_reverse_iterator(const const_reverse_iterator& other): mCurrent(other.mCurrent) {}
386        const const_reverse_iterator& operator=(const const_reverse_iterator& other) {mCurrent = other.mCurrent; return other;}
387
388        inline const_reverse_iterator& operator++() {
389            assert (mCurrent);
390            mCurrent = mCurrent->mPrev;
391            return *this;
392        }
393
394        const_reverse_iterator  operator++(int) {
395            const_reverse_iterator tmp(*this);
396            ++(*this);
397            return tmp;
398        }
399
400        bool operator==(const const_reverse_iterator & other) const {
401            return  mCurrent == other.mCurrent;
402        }
403        bool operator!=(const const_reverse_iterator & other) const {
404            return  mCurrent != other.mCurrent;
405        }
406
407        const Statement* operator*() {return mCurrent;}
408        const Statement* operator->(){return mCurrent;}
409
410    private:
411        const Statement * mCurrent;
412        friend struct iterator;
413    };
414
415public:
416
417    StatementList()
418    : mInsertionPoint(nullptr)
419    , mFirst(nullptr)
420    , mLast(nullptr)
421    {
422
423    }
424
425    StatementList(StatementList && other)
426    : mFirst(other.mFirst)
427    , mLast(other.mLast)
428    {
429        other.mFirst = nullptr;
430        other.mLast = nullptr;
431    }
432
433    iterator begin() {
434        return iterator(mFirst);
435    }
436
437    iterator end() {
438        return iterator(nullptr);
439    }
440
441    reverse_iterator rbegin() {
442        return reverse_iterator(mLast);
443    }
444
445    reverse_iterator rend() {
446        return reverse_iterator(nullptr);
447    }
448
449    const_iterator begin() const {
450        return const_iterator(mFirst);
451    }
452
453    const_iterator end() const {
454        return const_iterator(nullptr);
455    }
456
457    const_reverse_iterator rbegin() const {
458        return const_reverse_iterator(mLast);
459    }
460
461    const_reverse_iterator rend() const {
462        return const_reverse_iterator(nullptr);
463    }
464
465    const_iterator cbegin() const {
466        return const_iterator(mFirst);
467    }
468
469    const_iterator cend() const {
470        return const_iterator(nullptr);
471    }
472
473    const_reverse_iterator crbegin() const {
474        return const_reverse_iterator(mLast);
475    }
476
477    const_reverse_iterator crend() const {
478        return const_reverse_iterator(nullptr);
479    }
480
481    inline Statement * front() const {
482        return mFirst;
483    }
484
485    inline Statement * back() const {
486        return mLast;
487    }
488
489    void clear();
490
491    inline void setInsertPoint(Statement * const statement) {
492        assert (statement == nullptr || contains(statement));
493        mInsertionPoint = statement;
494    }
495
496    inline Statement * getInsertPoint() const {
497        return mInsertionPoint;
498    }
499
500    ~StatementList();
501
502    bool contains(Statement * const statement);
503
504private:
505
506    Statement   * mInsertionPoint;
507    Statement   * mFirst;
508    Statement   * mLast;   
509};
510
511}
512
513#endif // PE_PabloAST_H
514
515
516
Note: See TracBrowser for help on using the repository browser.