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

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

Initial introduction of a PabloFunction? type.

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 PabloFunction;
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            if (LLVM_LIKELY(op != nullptr)) {
224                op->addUser(this);
225            }
226        }
227    }
228    inline void setName(const String * const name) {
229        mName = name;
230    }   
231#ifndef NDEBUG
232    bool noRecursiveOperand(const PabloAST * const operand);
233#endif
234protected:   
235    const String *              mName;
236    Statement *                 mNext;
237    Statement *                 mPrev;
238    PabloBlock *                mParent;
239    const unsigned              mOperands;
240    // If we knew prior to construction how many operands were needed, we could
241    // eliminate the mOperand pointer and simply use this[1] instead.
242    PabloAST **                 mOperand;
243};
244
245class StatementList {
246    friend class Statement;
247    friend class PabloBlock;
248public:
249    class iterator: public std::iterator<std::forward_iterator_tag, Statement> {
250    public:
251        iterator(): mCurrent(nullptr) {}
252
253        iterator(Statement* base): mCurrent(base) {}
254
255        iterator(const iterator& other): mCurrent(other.mCurrent) {}
256
257        const iterator& operator=(const iterator& other) {
258            mCurrent = other.mCurrent; return other;
259        }
260
261        inline iterator& operator++() {
262            assert (mCurrent);
263            mCurrent = mCurrent->mNext;
264            return *this;
265        }
266
267        iterator  operator++(int) {
268            iterator tmp(*this);
269            ++(*this);
270            return tmp;
271        }
272
273        bool operator==(const iterator& other) const {
274            return  mCurrent == other.mCurrent;
275        }
276
277        bool operator!=(const iterator& other) const {
278            return  mCurrent != other.mCurrent;
279        }
280
281        Statement* operator*() {return mCurrent;}
282        Statement* operator->(){return mCurrent;}
283
284    private:
285        Statement * mCurrent;
286        friend class const_iterator;
287    };
288
289    class const_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
290    public:
291        const_iterator(): mCurrent(nullptr) {}
292        const_iterator(const Statement* base): mCurrent(base) {}
293        const_iterator(const const_iterator& other): mCurrent(other.mCurrent) {}
294        const const_iterator& operator=(const const_iterator& other) {mCurrent = other.mCurrent; return other;}
295
296        inline const_iterator& operator++() {
297            assert (mCurrent);
298            mCurrent = mCurrent->mNext;
299            return *this;
300        }
301
302        const_iterator  operator++(int) {
303            const_iterator tmp(*this);
304            ++(*this);
305            return tmp;
306        }
307
308        bool operator==(const const_iterator & other) const {
309            return  mCurrent == other.mCurrent;
310        }
311        bool operator!=(const const_iterator & other) const {
312            return  mCurrent != other.mCurrent;
313        }
314
315        const Statement* operator*() {return mCurrent;}
316        const Statement* operator->(){return mCurrent;}
317
318    private:
319        const Statement * mCurrent;
320        friend struct iterator;
321    };
322
323    class reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
324    public:
325        reverse_iterator(): mCurrent(nullptr) {}
326
327        reverse_iterator(Statement* base): mCurrent(base) {}
328
329        reverse_iterator(const reverse_iterator& other): mCurrent(other.mCurrent) {}
330
331        const reverse_iterator& operator=(const reverse_iterator& other) {
332            mCurrent = other.mCurrent; return other;
333        }
334
335        inline reverse_iterator& operator++() {
336            assert (mCurrent);
337            mCurrent = mCurrent->mPrev;
338            return *this;
339        }
340
341        reverse_iterator operator++(int) {
342            reverse_iterator tmp(*this);
343            ++(*this);
344            return tmp;
345        }
346
347        bool operator==(const reverse_iterator& other) const {
348            return  mCurrent == other.mCurrent;
349        }
350
351        bool operator!=(const reverse_iterator& other) const {
352            return  mCurrent != other.mCurrent;
353        }
354
355        Statement* operator*() {return mCurrent;}
356        Statement* operator->(){return mCurrent;}
357
358    private:
359        Statement * mCurrent;
360        friend class const_reverse_iterator;
361    };
362
363    class const_reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
364    public:
365        const_reverse_iterator(): mCurrent(nullptr) {}
366        const_reverse_iterator(const Statement* base): mCurrent(base) {}
367        const_reverse_iterator(const const_reverse_iterator& other): mCurrent(other.mCurrent) {}
368        const const_reverse_iterator& operator=(const const_reverse_iterator& other) {mCurrent = other.mCurrent; return other;}
369
370        inline const_reverse_iterator& operator++() {
371            assert (mCurrent);
372            mCurrent = mCurrent->mPrev;
373            return *this;
374        }
375
376        const_reverse_iterator  operator++(int) {
377            const_reverse_iterator tmp(*this);
378            ++(*this);
379            return tmp;
380        }
381
382        bool operator==(const const_reverse_iterator & other) const {
383            return  mCurrent == other.mCurrent;
384        }
385        bool operator!=(const const_reverse_iterator & other) const {
386            return  mCurrent != other.mCurrent;
387        }
388
389        const Statement* operator*() {return mCurrent;}
390        const Statement* operator->(){return mCurrent;}
391
392    private:
393        const Statement * mCurrent;
394        friend struct iterator;
395    };
396
397public:
398
399    StatementList()
400    : mInsertionPoint(nullptr)
401    , mFirst(nullptr)
402    , mLast(nullptr)
403    {
404
405    }
406
407    StatementList(StatementList && other)
408    : mFirst(other.mFirst)
409    , mLast(other.mLast)
410    {
411        other.mFirst = nullptr;
412        other.mLast = nullptr;
413    }
414
415    iterator begin() {
416        return iterator(mFirst);
417    }
418
419    iterator end() {
420        return iterator(nullptr);
421    }
422
423    reverse_iterator rbegin() {
424        return reverse_iterator(mLast);
425    }
426
427    reverse_iterator rend() {
428        return reverse_iterator(nullptr);
429    }
430
431    const_iterator begin() const {
432        return const_iterator(mFirst);
433    }
434
435    const_iterator end() const {
436        return const_iterator(nullptr);
437    }
438
439    const_reverse_iterator rbegin() const {
440        return const_reverse_iterator(mLast);
441    }
442
443    const_reverse_iterator rend() const {
444        return const_reverse_iterator(nullptr);
445    }
446
447    const_iterator cbegin() const {
448        return const_iterator(mFirst);
449    }
450
451    const_iterator cend() const {
452        return const_iterator(nullptr);
453    }
454
455    const_reverse_iterator crbegin() const {
456        return const_reverse_iterator(mLast);
457    }
458
459    const_reverse_iterator crend() const {
460        return const_reverse_iterator(nullptr);
461    }
462
463    inline Statement * front() const {
464        return mFirst;
465    }
466
467    inline Statement * back() const {
468        return mLast;
469    }
470
471    inline void setInsertPoint(Statement * const statement) {
472        mInsertionPoint = statement;
473    }
474
475    inline Statement * getInsertPoint() const {
476        return mInsertionPoint;
477    }
478
479    ~StatementList();
480
481private:
482
483    Statement   * mInsertionPoint;
484    Statement   * mFirst;
485    Statement   * mLast;   
486};
487
488}
489
490#endif // PE_PabloAST_H
491
492
493
Note: See TracBrowser for help on using the repository browser.