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

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

Work towards testing reassociation + multiplexing.

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