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

Last change on this file since 4543 was 4526, checked in by nmedfort, 5 years ago

Slab allocator now uses a single BumpPtrAllocator?.

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