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

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

More work towards n-ary And/Or/Xor? functions.

File size: 15.8 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#include <boost/iterator/iterator_facade.hpp>
17
18using namespace llvm;
19
20namespace pablo {
21
22class PabloBlock;
23class String;
24class Statement;
25
26class PabloAST {
27    friend class Statement;
28    friend class Variadic;
29    friend class StatementList;
30    friend class Var;
31    friend class If;   
32    friend class While;
33    friend class PabloBlock;
34    friend class Prototype;
35    friend class PabloFunction;
36    friend class SymbolGenerator;
37public:
38
39    using Allocator = SlabAllocator<u_int8_t>;
40    using VectorAllocator = Allocator::rebind<PabloAST *>::other;
41    using Users = std::vector<PabloAST *, VectorAllocator>;
42    using user_iterator = Users::iterator;
43    using const_user_iterator = Users::const_iterator;
44
45    enum class ClassTypeId : unsigned {
46        /** Non-statements **/
47        // Constants
48        Zeroes
49        , Ones
50        // Internal types
51        , Var
52        , Integer
53        , String
54        , Block
55        , Function
56        , Prototype
57        /** Statements **/
58        // Boolean operations
59        , And
60        , Or
61        , Not
62        , Xor
63        , Sel
64        // Stream operations
65        , Advance
66        , ScanThru
67        , MatchStar
68        // Mod 64 approximate stream operations
69        , Mod64Advance
70        , Mod64ScanThru
71        , Mod64MatchStar
72        // Statistics operations
73        , Count
74        // Variable assignments
75        , Assign
76        , Next
77        , Call
78        , SetIthBit
79        // Scope blocks
80        , If
81        , While
82    };
83    inline ClassTypeId getClassTypeId() const {
84        return mClassTypeId;
85    }
86
87    inline user_iterator user_begin() {
88        return mUsers.begin();
89    }
90
91    inline user_iterator user_end() {
92        return mUsers.end();
93    }
94
95    inline const_user_iterator user_begin() const {
96        return mUsers.cbegin();
97    }
98
99    inline const_user_iterator user_end() const {
100        return mUsers.cend();
101    }
102
103    inline Users & users() {
104        return mUsers;
105    }
106
107    inline const Users & users() const {
108        return mUsers;
109    }
110
111    void replaceAllUsesWith(PabloAST * expr);
112
113    inline Users::size_type getNumUses() const {
114        return mUsers.size();
115    }
116
117    void* operator new (std::size_t size) noexcept {
118        return mAllocator.allocate(size);
119    }
120
121    void operator delete (void * ptr) {
122        mAllocator.deallocate(static_cast<Allocator::value_type *>(ptr));
123    }
124
125protected:
126    inline PabloAST(const ClassTypeId id)
127    : mClassTypeId(id)
128    , mUsers(reinterpret_cast<VectorAllocator &>(mAllocator))
129    {
130
131    }
132    void addUser(PabloAST * user);
133    void removeUser(PabloAST * user);
134    virtual ~PabloAST() {
135        mUsers.clear();
136    }
137    static Allocator        mAllocator;
138private:
139    const ClassTypeId       mClassTypeId;
140    Users                   mUsers;
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;
155    template <class ValueType, class ValueList>
156    friend void checkEscapedValueList(const Statement *, const PabloAST * const, PabloAST * const, ValueList &);
157public:
158    static inline bool classof(const PabloAST * e) {
159        switch (e->getClassTypeId()) {
160            case PabloAST::ClassTypeId::Zeroes:
161            case PabloAST::ClassTypeId::Ones:
162            case PabloAST::ClassTypeId::Var:
163            case PabloAST::ClassTypeId::String:
164            case PabloAST::ClassTypeId::Integer:
165            case PabloAST::ClassTypeId::Block:
166            case PabloAST::ClassTypeId::Function:
167            case PabloAST::ClassTypeId::Prototype:
168                return false;
169            default:
170                return true;
171        }
172    }
173    static inline bool classof(const Statement *) {
174        return true;
175    }
176    static inline bool classof(const void *) {
177        return false;
178    }
179
180    void replaceUsesOfWith(PabloAST * const from, PabloAST * const to);
181
182    inline PabloAST * getOperand(const unsigned index) const {
183        assert (index < getNumOperands());
184        return mOperand[index];
185    }
186
187    void setOperand(const unsigned index, PabloAST * const value);
188
189    inline unsigned getNumOperands() const {
190        return mOperands;
191    }
192
193    void insertBefore(Statement * const statement);
194    void insertAfter(Statement * const statement);
195    Statement * removeFromParent();
196    Statement * eraseFromParent(const bool recursively = false);
197    Statement * replaceWith(PabloAST * const expr, const bool rename = true, const bool recursively = false);
198
199    inline const String * getName() const {
200        return mName;
201    }
202    inline void setName(const String * const name) {
203        mName = name;
204    }
205    inline Statement * getNextNode() const {
206        return mNext;
207    }
208    inline Statement * getPrevNode() const {
209        return mPrev;
210    }
211    inline PabloBlock * getParent() const {
212        return mParent;
213    }
214    virtual ~Statement() {}
215protected:
216    Statement(const ClassTypeId id, std::initializer_list<PabloAST *> operands, const String * const name)
217    : PabloAST(id)
218    , mName(name)
219    , mNext(nullptr)
220    , mPrev(nullptr)
221    , mParent(nullptr)
222    , mOperands(operands.size())
223    , mOperand(reinterpret_cast<PabloAST**>(mAllocator.allocate(mOperands * sizeof(PabloAST *)))) {
224        unsigned i = 0;
225        for (PabloAST * const op : operands) {
226            mOperand[i++] = op;
227            if (LLVM_LIKELY(op != nullptr)) {
228                op->addUser(this);
229            }
230        }
231    } 
232private:
233    template <class ValueType, class ValueList>
234    void checkEscapedValueList(Statement * branch, PabloAST * const from, PabloAST * const to, ValueList & list);
235protected:   
236    const String *  mName;
237    Statement *     mNext;
238    Statement *     mPrev;
239    PabloBlock *    mParent;
240    unsigned        mOperands;
241    PabloAST **     mOperand;
242};
243
244class Variadic : public Statement {
245public:
246
247    static inline bool classof(const PabloAST * e) {
248        switch (e->getClassTypeId()) {
249            case PabloAST::ClassTypeId::And:
250            case PabloAST::ClassTypeId::Or:
251            case PabloAST::ClassTypeId::Xor:
252                return true;
253            default: return false;
254        }
255    }
256    static inline bool classof(const Variadic *) {
257        return true;
258    }
259    static inline bool classof(const void *) {
260        return false;
261    }
262
263    class iterator : public boost::iterator_facade<iterator, PabloAST *, boost::random_access_traversal_tag> {
264        friend class Variadic;
265        friend class boost::iterator_core_access;
266    protected:
267
268        iterator(PabloAST ** pointer) : mCurrent(pointer) { }
269        inline void increment() { ++mCurrent; }
270        inline void decrement() { --mCurrent; }
271        inline void advance(const unsigned n) { mCurrent += n; }
272        inline std::ptrdiff_t distance_to(const iterator & other) const { return other.mCurrent - mCurrent; }
273        inline PabloAST *& dereference() const { return *mCurrent; }
274
275        inline bool equal(const iterator & other) const { return (mCurrent == other.mCurrent); }
276
277    private:
278        PabloAST **        mCurrent;
279    };
280
281    using const_iterator = iterator;
282
283    void addOperand(PabloAST * const expr);
284
285    PabloAST * removeOperand(const unsigned index);
286
287    inline iterator erase(iterator itr) {
288        removeOperand(itr.distance_to(begin()));
289        return itr;
290    }
291
292    iterator begin() {
293        return iterator(mOperand);
294    }
295
296    const_iterator begin() const {
297        return iterator(mOperand);
298    }
299
300    iterator end() {
301        return iterator(mOperand + mOperands);
302    }
303
304    const_iterator end() const {
305        return iterator(mOperand + mOperands);
306    }
307
308protected:
309    Variadic(const ClassTypeId id, std::initializer_list<PabloAST *> operands, const String * const name)
310    : Statement(id, operands, name)
311    , mCapacity(operands.size()) {
312
313    }
314private:
315    unsigned        mCapacity;
316};
317
318bool escapes(const Statement * statement);
319
320class StatementList {
321    friend class Statement;
322    friend class PabloBlock;
323public:
324    class iterator: public std::iterator<std::forward_iterator_tag, Statement> {
325    public:
326        iterator(): mCurrent(nullptr) {}
327
328        iterator(Statement* base): mCurrent(base) {}
329
330        iterator(const iterator& other): mCurrent(other.mCurrent) {}
331
332        const iterator& operator=(const iterator& other) {
333            mCurrent = other.mCurrent; return other;
334        }
335
336        inline iterator& operator++() {
337            assert (mCurrent);
338            mCurrent = mCurrent->mNext;
339            return *this;
340        }
341
342        iterator  operator++(int) {
343            iterator tmp(*this);
344            ++(*this);
345            return tmp;
346        }
347
348        bool operator==(const iterator& other) const {
349            return  mCurrent == other.mCurrent;
350        }
351
352        bool operator!=(const iterator& other) const {
353            return  mCurrent != other.mCurrent;
354        }
355
356        Statement* operator*() {return mCurrent;}
357        Statement* operator->(){return mCurrent;}
358
359    private:
360        Statement * mCurrent;
361        friend class const_iterator;
362    };
363
364    class const_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
365    public:
366        const_iterator(): mCurrent(nullptr) {}
367        const_iterator(const Statement* base): mCurrent(base) {}
368        const_iterator(const const_iterator& other): mCurrent(other.mCurrent) {}
369        const const_iterator& operator=(const const_iterator& other) {mCurrent = other.mCurrent; return other;}
370
371        inline const_iterator& operator++() {
372            assert (mCurrent);
373            mCurrent = mCurrent->mNext;
374            return *this;
375        }
376
377        const_iterator  operator++(int) {
378            const_iterator tmp(*this);
379            ++(*this);
380            return tmp;
381        }
382
383        bool operator==(const const_iterator & other) const {
384            return  mCurrent == other.mCurrent;
385        }
386        bool operator!=(const const_iterator & other) const {
387            return  mCurrent != other.mCurrent;
388        }
389
390        const Statement* operator*() {return mCurrent;}
391        const Statement* operator->(){return mCurrent;}
392
393    private:
394        const Statement * mCurrent;
395        friend struct iterator;
396    };
397
398    class reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
399    public:
400        reverse_iterator(): mCurrent(nullptr) {}
401
402        reverse_iterator(Statement* base): mCurrent(base) {}
403
404        reverse_iterator(const reverse_iterator& other): mCurrent(other.mCurrent) {}
405
406        const reverse_iterator& operator=(const reverse_iterator& other) {
407            mCurrent = other.mCurrent; return other;
408        }
409
410        inline reverse_iterator& operator++() {
411            assert (mCurrent);
412            mCurrent = mCurrent->mPrev;
413            return *this;
414        }
415
416        reverse_iterator operator++(int) {
417            reverse_iterator tmp(*this);
418            ++(*this);
419            return tmp;
420        }
421
422        bool operator==(const reverse_iterator& other) const {
423            return  mCurrent == other.mCurrent;
424        }
425
426        bool operator!=(const reverse_iterator& other) const {
427            return  mCurrent != other.mCurrent;
428        }
429
430        Statement* operator*() {return mCurrent;}
431        Statement* operator->(){return mCurrent;}
432
433    private:
434        Statement * mCurrent;
435        friend class const_reverse_iterator;
436    };
437
438    class const_reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
439    public:
440        const_reverse_iterator(): mCurrent(nullptr) {}
441        const_reverse_iterator(const Statement* base): mCurrent(base) {}
442        const_reverse_iterator(const const_reverse_iterator& other): mCurrent(other.mCurrent) {}
443        const const_reverse_iterator& operator=(const const_reverse_iterator& other) {mCurrent = other.mCurrent; return other;}
444
445        inline const_reverse_iterator& operator++() {
446            assert (mCurrent);
447            mCurrent = mCurrent->mPrev;
448            return *this;
449        }
450
451        const_reverse_iterator  operator++(int) {
452            const_reverse_iterator tmp(*this);
453            ++(*this);
454            return tmp;
455        }
456
457        bool operator==(const const_reverse_iterator & other) const {
458            return  mCurrent == other.mCurrent;
459        }
460        bool operator!=(const const_reverse_iterator & other) const {
461            return  mCurrent != other.mCurrent;
462        }
463
464        const Statement* operator*() {return mCurrent;}
465        const Statement* operator->(){return mCurrent;}
466
467    private:
468        const Statement * mCurrent;
469        friend struct iterator;
470    };
471
472public:
473
474    StatementList()
475    : mInsertionPoint(nullptr)
476    , mFirst(nullptr)
477    , mLast(nullptr) {
478
479    }
480
481    StatementList(StatementList && other)
482    : mInsertionPoint(nullptr)
483    , mFirst(other.mFirst)
484    , mLast(other.mLast) {
485        other.mInsertionPoint = nullptr;
486        other.mFirst = nullptr;
487        other.mLast = nullptr;
488    }
489
490    iterator begin() {
491        return iterator(mFirst);
492    }
493
494    iterator end() {
495        return iterator(nullptr);
496    }
497
498    reverse_iterator rbegin() {
499        return reverse_iterator(mLast);
500    }
501
502    reverse_iterator rend() {
503        return reverse_iterator(nullptr);
504    }
505
506    const_iterator begin() const {
507        return const_iterator(mFirst);
508    }
509
510    const_iterator end() const {
511        return const_iterator(nullptr);
512    }
513
514    const_reverse_iterator rbegin() const {
515        return const_reverse_iterator(mLast);
516    }
517
518    const_reverse_iterator rend() const {
519        return const_reverse_iterator(nullptr);
520    }
521
522    const_iterator cbegin() const {
523        return const_iterator(mFirst);
524    }
525
526    const_iterator cend() const {
527        return const_iterator(nullptr);
528    }
529
530    const_reverse_iterator crbegin() const {
531        return const_reverse_iterator(mLast);
532    }
533
534    const_reverse_iterator crend() const {
535        return const_reverse_iterator(nullptr);
536    }
537
538    inline Statement * front() const {
539        return mFirst;
540    }
541
542    inline Statement * back() const {
543        return mLast;
544    }
545
546    inline void setInsertPoint(Statement * const statement) {
547        assert (statement == nullptr || contains(statement));
548        mInsertionPoint = statement;
549    }
550
551    inline Statement * getInsertPoint() const {
552        return mInsertionPoint;
553    }
554
555    bool contains(Statement * const statement);
556
557protected:
558
559    ~StatementList() = default;
560
561private:
562
563    Statement   * mInsertionPoint;
564    Statement   * mFirst;
565    Statement   * mLast;   
566};
567
568/** ------------------------------------------------------------------------------------------------------------- *
569 * @brief addUser
570 ** ------------------------------------------------------------------------------------------------------------- */
571inline void PabloAST::addUser(PabloAST *user) {
572    assert (user);
573    // Note: for the rare situation that this node is used multiple times by a statement, duplicates are allowed.
574    mUsers.insert(std::lower_bound(mUsers.begin(), mUsers.end(), user), user);
575}
576
577/** ------------------------------------------------------------------------------------------------------------- *
578 * @brief removeUser
579 ** ------------------------------------------------------------------------------------------------------------- */
580inline void PabloAST::removeUser(PabloAST * user) {
581    assert (user);
582    auto pos = std::lower_bound(mUsers.begin(), mUsers.end(), user);
583    assert ("Could not find user to remove!" && (pos != mUsers.end() && *pos == user));
584    mUsers.erase(pos);
585}
586
587}
588
589#endif // PE_PabloAST_H
Note: See TracBrowser for help on using the repository browser.