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

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

Temporary check in.

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