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

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

More work on n-ary operations.

File size: 16.4 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 unsigned getNumUsers() const {
104        return mUsers.size();
105    }
106
107    inline Users & users() {
108        return mUsers;
109    }
110
111    inline const Users & users() const {
112        return mUsers;
113    }
114
115    void replaceAllUsesWith(PabloAST * expr);
116
117    inline Users::size_type getNumUses() const {
118        return mUsers.size();
119    }
120
121    void* operator new (std::size_t size) noexcept {
122        return mAllocator.allocate(size);
123    }
124
125    void operator delete (void * ptr) {
126        mAllocator.deallocate(static_cast<Allocator::value_type *>(ptr));
127    }
128
129protected:
130    inline PabloAST(const ClassTypeId id)
131    : mClassTypeId(id)
132    , mUsers(reinterpret_cast<VectorAllocator &>(mAllocator))
133    {
134
135    }
136    void addUser(PabloAST * user);
137    void removeUser(PabloAST * user);
138    virtual ~PabloAST() {
139        mUsers.clear();
140    }
141    static Allocator        mAllocator;
142private:
143    const ClassTypeId       mClassTypeId;
144    Users                   mUsers;
145};
146
147bool equals(const PabloAST * expr1, const PabloAST *expr2);
148
149class StatementList;
150
151class String;
152
153class Statement : public PabloAST {
154    friend class StatementList;
155    friend class If;
156    friend class While;
157    friend class Simplifier;
158    friend class PabloBlock;
159    template <class ValueType, class ValueList>
160    friend void checkEscapedValueList(const Statement *, const PabloAST * const, PabloAST * const, ValueList &);
161public:
162    static inline bool classof(const PabloAST * e) {
163        switch (e->getClassTypeId()) {
164            case PabloAST::ClassTypeId::Zeroes:
165            case PabloAST::ClassTypeId::Ones:
166            case PabloAST::ClassTypeId::Var:
167            case PabloAST::ClassTypeId::String:
168            case PabloAST::ClassTypeId::Integer:
169            case PabloAST::ClassTypeId::Block:
170            case PabloAST::ClassTypeId::Function:
171            case PabloAST::ClassTypeId::Prototype:
172                return false;
173            default:
174                return true;
175        }
176    }
177    static inline bool classof(const Statement *) {
178        return true;
179    }
180    static inline bool classof(const void *) {
181        return false;
182    }
183
184    void replaceUsesOfWith(PabloAST * const from, PabloAST * const to);
185
186    inline PabloAST * getOperand(const unsigned index) const {
187        assert (index < getNumOperands());
188        return mOperand[index];
189    }
190
191    void setOperand(const unsigned index, PabloAST * const value);
192
193    inline unsigned getNumOperands() const {
194        return mOperands;
195    }
196
197    void insertBefore(Statement * const statement);
198    void insertAfter(Statement * const statement);
199    Statement * removeFromParent();
200    Statement * eraseFromParent(const bool recursively = false);
201    Statement * replaceWith(PabloAST * const expr, const bool rename = true, const bool recursively = false);
202
203    inline const String * getName() const {
204        return mName;
205    }
206    inline void setName(const String * const name) {
207        mName = name;
208    }
209    inline Statement * getNextNode() const {
210        return mNext;
211    }
212    inline Statement * getPrevNode() const {
213        return mPrev;
214    }
215    inline PabloBlock * getParent() const {
216        return mParent;
217    }
218    virtual ~Statement() {}
219protected:
220    Statement(const ClassTypeId id, std::initializer_list<PabloAST *> operands, const String * const name)
221    : PabloAST(id)
222    , mName(name)
223    , mNext(nullptr)
224    , mPrev(nullptr)
225    , mParent(nullptr)
226    , mOperands(operands.size())
227    , mOperand(reinterpret_cast<PabloAST**>(mAllocator.allocate(mOperands * sizeof(PabloAST *)))) {
228        unsigned i = 0;
229        for (PabloAST * const value : operands) {
230            assert (value);
231            mOperand[i] = value;
232            value->addUser(this);
233            ++i;
234        }
235    } 
236    Statement(const ClassTypeId id, unsigned operands, PabloAST * value, const String * const name)
237    : PabloAST(id)
238    , mName(name)
239    , mNext(nullptr)
240    , mPrev(nullptr)
241    , mParent(nullptr)
242    , mOperands(operands)
243    , mOperand(reinterpret_cast<PabloAST**>(mAllocator.allocate(mOperands * sizeof(PabloAST *)))) {
244        for (unsigned i = 0; i != operands; ++i) {
245            assert (value);
246            mOperand[i] = value;
247            value->addUser(this);
248        }
249    }
250private:
251    template <class ValueType, class ValueList>
252    void checkEscapedValueList(Statement * branch, PabloAST * const from, PabloAST * const to, ValueList & list);
253protected:   
254    const String *  mName;
255    Statement *     mNext;
256    Statement *     mPrev;
257    PabloBlock *    mParent;
258    unsigned        mOperands;
259    PabloAST **     mOperand;
260};
261
262class Variadic : public Statement {
263public:
264
265    static inline bool classof(const PabloAST * e) {
266        switch (e->getClassTypeId()) {
267            case PabloAST::ClassTypeId::And:
268            case PabloAST::ClassTypeId::Or:
269            case PabloAST::ClassTypeId::Xor:
270                return true;
271            default: return false;
272        }
273    }
274    static inline bool classof(const Variadic *) {
275        return true;
276    }
277    static inline bool classof(const void *) {
278        return false;
279    }
280
281    class iterator : public boost::iterator_facade<iterator, PabloAST *, boost::random_access_traversal_tag> {
282        friend class Variadic;
283        friend class boost::iterator_core_access;
284    protected:
285
286        iterator(PabloAST ** pointer) : mCurrent(pointer) { }
287        inline void increment() { ++mCurrent; }
288        inline void decrement() { --mCurrent; }
289        inline void advance(const std::ptrdiff_t n) { mCurrent += n; }
290        inline std::ptrdiff_t distance_to(const iterator & other) const { return other.mCurrent - mCurrent; }
291        inline PabloAST *& dereference() const { return *mCurrent; }
292
293        inline bool equal(const iterator & other) const { return (mCurrent == other.mCurrent); }
294
295    private:
296        PabloAST **        mCurrent;
297    };
298
299    using const_iterator = iterator;
300
301    void addOperand(PabloAST * const expr);
302
303    PabloAST * removeOperand(const unsigned index);
304
305    iterator begin() {
306        return iterator(mOperand);
307    }
308
309    const_iterator begin() const {
310        return iterator(mOperand);
311    }
312
313    iterator end() {
314        return iterator(mOperand + mOperands);
315    }
316
317    const_iterator end() const {
318        return iterator(mOperand + mOperands);
319    }
320
321protected:
322    Variadic(const ClassTypeId id, std::initializer_list<PabloAST *> operands, const String * const name)
323    : Statement(id, operands, name)
324    , mCapacity(operands.size()) {
325
326    }
327    Variadic(const ClassTypeId id, const unsigned operands, PabloAST * value, String * name)
328    : Statement(id, operands, value, name)
329    , mCapacity(operands) {
330
331    }
332private:
333    unsigned        mCapacity;
334};
335
336bool escapes(const Statement * statement);
337
338class StatementList {
339    friend class Statement;
340    friend class PabloBlock;
341public:
342    class iterator: public std::iterator<std::forward_iterator_tag, Statement> {
343    public:
344        iterator(): mCurrent(nullptr) {}
345
346        iterator(Statement* base): mCurrent(base) {}
347
348        iterator(const iterator& other): mCurrent(other.mCurrent) {}
349
350        const iterator& operator=(const iterator& other) {
351            mCurrent = other.mCurrent; return other;
352        }
353
354        inline iterator& operator++() {
355            assert (mCurrent);
356            mCurrent = mCurrent->mNext;
357            return *this;
358        }
359
360        iterator  operator++(int) {
361            iterator tmp(*this);
362            ++(*this);
363            return tmp;
364        }
365
366        bool operator==(const iterator& other) const {
367            return  mCurrent == other.mCurrent;
368        }
369
370        bool operator!=(const iterator& other) const {
371            return  mCurrent != other.mCurrent;
372        }
373
374        Statement* operator*() {return mCurrent;}
375        Statement* operator->(){return mCurrent;}
376
377    private:
378        Statement * mCurrent;
379        friend class const_iterator;
380    };
381
382    class const_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
383    public:
384        const_iterator(): mCurrent(nullptr) {}
385        const_iterator(const Statement* base): mCurrent(base) {}
386        const_iterator(const const_iterator& other): mCurrent(other.mCurrent) {}
387        const const_iterator& operator=(const const_iterator& other) {mCurrent = other.mCurrent; return other;}
388
389        inline const_iterator& operator++() {
390            assert (mCurrent);
391            mCurrent = mCurrent->mNext;
392            return *this;
393        }
394
395        const_iterator  operator++(int) {
396            const_iterator tmp(*this);
397            ++(*this);
398            return tmp;
399        }
400
401        bool operator==(const const_iterator & other) const {
402            return  mCurrent == other.mCurrent;
403        }
404        bool operator!=(const const_iterator & other) const {
405            return  mCurrent != other.mCurrent;
406        }
407
408        const Statement* operator*() {return mCurrent;}
409        const Statement* operator->(){return mCurrent;}
410
411    private:
412        const Statement * mCurrent;
413        friend struct iterator;
414    };
415
416    class reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
417    public:
418        reverse_iterator(): mCurrent(nullptr) {}
419
420        reverse_iterator(Statement* base): mCurrent(base) {}
421
422        reverse_iterator(const reverse_iterator& other): mCurrent(other.mCurrent) {}
423
424        const reverse_iterator& operator=(const reverse_iterator& other) {
425            mCurrent = other.mCurrent; return other;
426        }
427
428        inline reverse_iterator& operator++() {
429            assert (mCurrent);
430            mCurrent = mCurrent->mPrev;
431            return *this;
432        }
433
434        reverse_iterator operator++(int) {
435            reverse_iterator tmp(*this);
436            ++(*this);
437            return tmp;
438        }
439
440        bool operator==(const reverse_iterator& other) const {
441            return  mCurrent == other.mCurrent;
442        }
443
444        bool operator!=(const reverse_iterator& other) const {
445            return  mCurrent != other.mCurrent;
446        }
447
448        Statement* operator*() {return mCurrent;}
449        Statement* operator->(){return mCurrent;}
450
451    private:
452        Statement * mCurrent;
453        friend class const_reverse_iterator;
454    };
455
456    class const_reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
457    public:
458        const_reverse_iterator(): mCurrent(nullptr) {}
459        const_reverse_iterator(const Statement* base): mCurrent(base) {}
460        const_reverse_iterator(const const_reverse_iterator& other): mCurrent(other.mCurrent) {}
461        const const_reverse_iterator& operator=(const const_reverse_iterator& other) {mCurrent = other.mCurrent; return other;}
462
463        inline const_reverse_iterator& operator++() {
464            assert (mCurrent);
465            mCurrent = mCurrent->mPrev;
466            return *this;
467        }
468
469        const_reverse_iterator  operator++(int) {
470            const_reverse_iterator tmp(*this);
471            ++(*this);
472            return tmp;
473        }
474
475        bool operator==(const const_reverse_iterator & other) const {
476            return  mCurrent == other.mCurrent;
477        }
478        bool operator!=(const const_reverse_iterator & other) const {
479            return  mCurrent != other.mCurrent;
480        }
481
482        const Statement* operator*() {return mCurrent;}
483        const Statement* operator->(){return mCurrent;}
484
485    private:
486        const Statement * mCurrent;
487        friend struct iterator;
488    };
489
490public:
491
492    StatementList()
493    : mInsertionPoint(nullptr)
494    , mFirst(nullptr)
495    , mLast(nullptr) {
496
497    }
498
499    StatementList(StatementList && other)
500    : mInsertionPoint(nullptr)
501    , mFirst(other.mFirst)
502    , mLast(other.mLast) {
503        other.mInsertionPoint = nullptr;
504        other.mFirst = nullptr;
505        other.mLast = nullptr;
506    }
507
508    iterator begin() {
509        return iterator(mFirst);
510    }
511
512    iterator end() {
513        return iterator(nullptr);
514    }
515
516    reverse_iterator rbegin() {
517        return reverse_iterator(mLast);
518    }
519
520    reverse_iterator rend() {
521        return reverse_iterator(nullptr);
522    }
523
524    const_iterator begin() const {
525        return const_iterator(mFirst);
526    }
527
528    const_iterator end() const {
529        return const_iterator(nullptr);
530    }
531
532    const_reverse_iterator rbegin() const {
533        return const_reverse_iterator(mLast);
534    }
535
536    const_reverse_iterator rend() const {
537        return const_reverse_iterator(nullptr);
538    }
539
540    const_iterator cbegin() const {
541        return const_iterator(mFirst);
542    }
543
544    const_iterator cend() const {
545        return const_iterator(nullptr);
546    }
547
548    const_reverse_iterator crbegin() const {
549        return const_reverse_iterator(mLast);
550    }
551
552    const_reverse_iterator crend() const {
553        return const_reverse_iterator(nullptr);
554    }
555
556    inline Statement * front() const {
557        return mFirst;
558    }
559
560    inline Statement * back() const {
561        return mLast;
562    }
563
564    inline void setInsertPoint(Statement * const statement) {
565        assert (statement == nullptr || contains(statement));
566        mInsertionPoint = statement;
567    }
568
569    inline Statement * getInsertPoint() const {
570        return mInsertionPoint;
571    }
572
573    bool contains(Statement * const statement);
574
575protected:
576
577    ~StatementList() = default;
578
579private:
580
581    Statement   * mInsertionPoint;
582    Statement   * mFirst;
583    Statement   * mLast;   
584};
585
586/** ------------------------------------------------------------------------------------------------------------- *
587 * @brief addUser
588 ** ------------------------------------------------------------------------------------------------------------- */
589inline void PabloAST::addUser(PabloAST *user) {
590    assert (user);   
591    // Note: for the rare situation that this node is used multiple times by a statement, duplicates are allowed.
592    mUsers.insert(std::lower_bound(mUsers.begin(), mUsers.end(), user), user);
593}
594
595/** ------------------------------------------------------------------------------------------------------------- *
596 * @brief removeUser
597 ** ------------------------------------------------------------------------------------------------------------- */
598inline void PabloAST::removeUser(PabloAST * user) {
599    assert (user);
600    auto pos = std::lower_bound(mUsers.begin(), mUsers.end(), user);
601    assert ("Could not find user to remove!" && (pos != mUsers.end() && *pos == user));
602    mUsers.erase(pos);
603}
604
605}
606
607#endif // PE_PabloAST_H
Note: See TracBrowser for help on using the repository browser.