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

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

Temporary check in.

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