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

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

Temporary check-in.

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