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

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

More work on n-ary operations.

File size: 17.0 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    unsigned removeOperand(const PabloAST * const expr);
306
307    iterator begin() {
308        return iterator(mOperand);
309    }
310
311    const_iterator begin() const {
312        return iterator(mOperand);
313    }
314
315    iterator end() {
316        return iterator(mOperand + mOperands);
317    }
318
319    const_iterator end() const {
320        return iterator(mOperand + mOperands);
321    }
322
323protected:
324    Variadic(const ClassTypeId id, std::initializer_list<PabloAST *> operands, const String * const name)
325    : Statement(id, operands, name)
326    , mCapacity(operands.size()) {
327
328    }
329    Variadic(const ClassTypeId id, const unsigned operands, PabloAST * value, String * name)
330    : Statement(id, operands, value, name)
331    , mCapacity(operands) {
332
333    }
334private:
335    unsigned        mCapacity;
336};
337
338bool escapes(const Statement * statement);
339
340class StatementList {
341    friend class Statement;
342    friend class PabloBlock;
343public:
344    class iterator: public std::iterator<std::forward_iterator_tag, Statement> {
345    public:
346        iterator(): mCurrent(nullptr) {}
347
348        iterator(Statement* base): mCurrent(base) {}
349
350        iterator(const iterator& other): mCurrent(other.mCurrent) {}
351
352        const iterator& operator=(const iterator& other) {
353            mCurrent = other.mCurrent; return other;
354        }
355
356        inline iterator& operator++() {
357            assert (mCurrent);
358            mCurrent = mCurrent->mNext;
359            return *this;
360        }
361
362        iterator  operator++(int) {
363            iterator tmp(*this);
364            ++(*this);
365            return tmp;
366        }
367
368        bool operator==(const iterator& other) const {
369            return  mCurrent == other.mCurrent;
370        }
371
372        bool operator!=(const iterator& other) const {
373            return  mCurrent != other.mCurrent;
374        }
375
376        Statement* operator*() {return mCurrent;}
377        Statement* operator->(){return mCurrent;}
378
379    private:
380        Statement * mCurrent;
381        friend class const_iterator;
382    };
383
384    class const_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
385    public:
386        const_iterator(): mCurrent(nullptr) {}
387        const_iterator(const Statement* base): mCurrent(base) {}
388        const_iterator(const const_iterator& other): mCurrent(other.mCurrent) {}
389        const const_iterator& operator=(const const_iterator& other) {mCurrent = other.mCurrent; return other;}
390
391        inline const_iterator& operator++() {
392            assert (mCurrent);
393            mCurrent = mCurrent->mNext;
394            return *this;
395        }
396
397        const_iterator  operator++(int) {
398            const_iterator tmp(*this);
399            ++(*this);
400            return tmp;
401        }
402
403        bool operator==(const const_iterator & other) const {
404            return  mCurrent == other.mCurrent;
405        }
406        bool operator!=(const const_iterator & other) const {
407            return  mCurrent != other.mCurrent;
408        }
409
410        const Statement* operator*() {return mCurrent;}
411        const Statement* operator->(){return mCurrent;}
412
413    private:
414        const Statement * mCurrent;
415        friend struct iterator;
416    };
417
418    class reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
419    public:
420        reverse_iterator(): mCurrent(nullptr) {}
421
422        reverse_iterator(Statement* base): mCurrent(base) {}
423
424        reverse_iterator(const reverse_iterator& other): mCurrent(other.mCurrent) {}
425
426        const reverse_iterator& operator=(const reverse_iterator& other) {
427            mCurrent = other.mCurrent; return other;
428        }
429
430        inline reverse_iterator& operator++() {
431            assert (mCurrent);
432            mCurrent = mCurrent->mPrev;
433            return *this;
434        }
435
436        reverse_iterator operator++(int) {
437            reverse_iterator tmp(*this);
438            ++(*this);
439            return tmp;
440        }
441
442        bool operator==(const reverse_iterator& other) const {
443            return  mCurrent == other.mCurrent;
444        }
445
446        bool operator!=(const reverse_iterator& other) const {
447            return  mCurrent != other.mCurrent;
448        }
449
450        Statement* operator*() {return mCurrent;}
451        Statement* operator->(){return mCurrent;}
452
453    private:
454        Statement * mCurrent;
455        friend class const_reverse_iterator;
456    };
457
458    class const_reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
459    public:
460        const_reverse_iterator(): mCurrent(nullptr) {}
461        const_reverse_iterator(const Statement* base): mCurrent(base) {}
462        const_reverse_iterator(const const_reverse_iterator& other): mCurrent(other.mCurrent) {}
463        const const_reverse_iterator& operator=(const const_reverse_iterator& other) {mCurrent = other.mCurrent; return other;}
464
465        inline const_reverse_iterator& operator++() {
466            assert (mCurrent);
467            mCurrent = mCurrent->mPrev;
468            return *this;
469        }
470
471        const_reverse_iterator  operator++(int) {
472            const_reverse_iterator tmp(*this);
473            ++(*this);
474            return tmp;
475        }
476
477        bool operator==(const const_reverse_iterator & other) const {
478            return  mCurrent == other.mCurrent;
479        }
480        bool operator!=(const const_reverse_iterator & other) const {
481            return  mCurrent != other.mCurrent;
482        }
483
484        const Statement* operator*() {return mCurrent;}
485        const Statement* operator->(){return mCurrent;}
486
487    private:
488        const Statement * mCurrent;
489        friend struct iterator;
490    };
491
492public:
493
494    StatementList()
495    : mInsertionPoint(nullptr)
496    , mFirst(nullptr)
497    , mLast(nullptr) {
498
499    }
500
501    StatementList(StatementList && other)
502    : mInsertionPoint(nullptr)
503    , mFirst(other.mFirst)
504    , mLast(other.mLast) {
505        other.mInsertionPoint = nullptr;
506        other.mFirst = nullptr;
507        other.mLast = nullptr;
508    }
509
510    iterator begin() {
511        return iterator(mFirst);
512    }
513
514    iterator end() {
515        return iterator(nullptr);
516    }
517
518    reverse_iterator rbegin() {
519        return reverse_iterator(mLast);
520    }
521
522    reverse_iterator rend() {
523        return reverse_iterator(nullptr);
524    }
525
526    const_iterator begin() const {
527        return const_iterator(mFirst);
528    }
529
530    const_iterator end() const {
531        return const_iterator(nullptr);
532    }
533
534    const_reverse_iterator rbegin() const {
535        return const_reverse_iterator(mLast);
536    }
537
538    const_reverse_iterator rend() const {
539        return const_reverse_iterator(nullptr);
540    }
541
542    const_iterator cbegin() const {
543        return const_iterator(mFirst);
544    }
545
546    const_iterator cend() const {
547        return const_iterator(nullptr);
548    }
549
550    const_reverse_iterator crbegin() const {
551        return const_reverse_iterator(mLast);
552    }
553
554    const_reverse_iterator crend() const {
555        return const_reverse_iterator(nullptr);
556    }
557
558    inline Statement * front() const {
559        return mFirst;
560    }
561
562    inline Statement * back() const {
563        return mLast;
564    }
565
566    inline void setInsertPoint(Statement * const statement) {
567        assert (statement == nullptr || contains(statement));
568        mInsertionPoint = statement;
569    }
570
571    inline Statement * getInsertPoint() const {
572        return mInsertionPoint;
573    }
574
575    bool contains(Statement * const statement);
576
577protected:
578
579    ~StatementList() = default;
580
581private:
582
583    Statement   * mInsertionPoint;
584    Statement   * mFirst;
585    Statement   * mLast;   
586};
587
588/** ------------------------------------------------------------------------------------------------------------- *
589 * @brief addUser
590 ** ------------------------------------------------------------------------------------------------------------- */
591inline void PabloAST::addUser(PabloAST *user) {
592    assert (user);   
593    // Note: for the rare situation that this node is used multiple times by a statement, duplicates are allowed.
594    mUsers.insert(std::lower_bound(mUsers.begin(), mUsers.end(), user), user);
595}
596
597/** ------------------------------------------------------------------------------------------------------------- *
598 * @brief removeUser
599 ** ------------------------------------------------------------------------------------------------------------- */
600inline void PabloAST::removeUser(PabloAST * user) {
601    assert (user);
602    auto pos = std::lower_bound(mUsers.begin(), mUsers.end(), user);
603    assert ("Could not find user to remove!" && (pos != mUsers.end() && *pos == user));
604    mUsers.erase(pos);
605}
606
607/** ------------------------------------------------------------------------------------------------------------- *
608 * @brief removeOperand
609 ** ------------------------------------------------------------------------------------------------------------- */
610inline unsigned Variadic::removeOperand(const PabloAST * const expr) {
611    for (unsigned i = 0; i != getNumOperands(); ++i) {
612        if (getOperand(i) == expr) {
613            removeOperand(i);
614            return i;
615        }
616    }
617    return -1;
618}
619
620}
621
622#endif // PE_PabloAST_H
Note: See TracBrowser for help on using the repository browser.