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

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

Temporary check-in.

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