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

Last change on this file since 5156 was 5156, checked in by nmedfort, 3 years ago

Work on multiplexing and distribution passes + a few AST modification bug fixes.

File size: 16.7 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 <boost/iterator/iterator_facade.hpp>
13#include <iterator>
14#include <util/slab_allocator.h>
15#include <type_traits>
16#include <unordered_map>
17#include <vector>
18
19using namespace llvm;
20
21namespace pablo {
22
23class PabloBlock;
24class String;
25class Statement;
26
27class PabloAST {
28    friend class Statement;
29    friend class Variadic;
30    friend class StatementList;
31    friend class Var;
32    friend class If;   
33    friend class While;
34    friend class PabloBlock;
35    friend class Prototype;
36    friend class PabloFunction;
37    friend class SymbolGenerator;
38    friend class Count;
39public:
40
41    using Allocator = SlabAllocator<u_int8_t>;
42    using VectorAllocator = SlabAllocator<PabloAST *>;
43    using Users = std::vector<PabloAST *, VectorAllocator>;
44    using user_iterator = Users::iterator;
45    using const_user_iterator = Users::const_iterator;
46
47    enum class ClassTypeId : unsigned {
48        /** Non-statements **/
49        // Constants
50        Zeroes
51        , Ones
52        // Internal types
53        , Var
54        , Integer
55        , String
56        , Block
57        , Function
58        , Prototype
59        /** Statements **/
60        // Boolean operations
61        , And
62        , Or
63        , Xor
64        , Not       
65        , Sel
66        // Stream operations
67        , Advance
68        , ScanThru
69        , Lookahead
70        , MatchStar
71        , InFile
72        , AtEOF
73        // Statistics operations
74        , Count
75        // Variable assignments
76        , Assign
77        , Next
78        , Call
79        , SetIthBit
80        // Scope blocks
81        , If
82        , While
83    };
84    inline ClassTypeId getClassTypeId() const {
85        return mClassTypeId;
86    }
87
88    inline user_iterator user_begin() {
89        return mUsers.begin();
90    }
91
92    inline user_iterator user_end() {
93        return mUsers.end();
94    }
95
96    inline const_user_iterator user_begin() const {
97        return mUsers.cbegin();
98    }
99
100    inline const_user_iterator user_end() const {
101        return mUsers.cend();
102    }
103
104    inline Users & users() {
105        return mUsers;
106    }
107
108    inline const Users & users() const {
109        return mUsers;
110    }
111
112    void replaceAllUsesWith(PabloAST * const expr);
113
114    inline Users::size_type getNumUses() const {
115        return mUsers.size();
116    }
117
118    void* operator new (std::size_t size) noexcept {
119        return mAllocator.allocate(size);
120    }
121
122    void operator delete (void * ptr) {
123        mAllocator.deallocate(static_cast<Allocator::value_type *>(ptr));
124    }
125
126protected:
127    inline PabloAST(const ClassTypeId id)
128    : mClassTypeId(id)
129    , mUsers(mVectorAllocator)
130    {
131
132    }
133    void addUser(PabloAST * const user);
134    void removeUser(PabloAST * const user);
135    virtual ~PabloAST() {
136        mUsers.clear();
137    }
138    static Allocator        mAllocator;
139    static VectorAllocator  mVectorAllocator;
140private:
141    const ClassTypeId       mClassTypeId;
142    Users                   mUsers;
143};
144
145bool equals(const PabloAST * const expr1, const PabloAST * const expr2);
146
147bool dominates(const PabloAST * const expr1, const PabloAST * const 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    explicit 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    explicit Statement(const ClassTypeId id, const unsigned reserved, const String * const name)
237    : PabloAST(id)
238    , mName(name)
239    , mNext(nullptr)
240    , mPrev(nullptr)
241    , mParent(nullptr)
242    , mOperands(0)
243    , mOperand(reinterpret_cast<PabloAST**>(mAllocator.allocate(reserved * sizeof(PabloAST *)))) {
244        std::memset(mOperand, 0, reserved * sizeof(PabloAST *));
245    }
246    template<typename iterator>
247    explicit Statement(const ClassTypeId id, iterator begin, iterator end, const String * const name)
248    : PabloAST(id)
249    , mName(name)
250    , mNext(nullptr)
251    , mPrev(nullptr)
252    , mParent(nullptr)
253    , mOperands(std::distance(begin, end))
254    , mOperand(reinterpret_cast<PabloAST**>(mAllocator.allocate(mOperands * sizeof(PabloAST *)))) {
255        unsigned i = 0;
256        for (auto value = begin; value != end; ++value, ++i) {
257            assert (*value);
258            mOperand[i] = *value;
259            (*value)->addUser(this);
260        }
261    }
262private:
263    template <class ValueType, class ValueList>
264    void checkEscapedValueList(Statement * branch, PabloAST * const from, PabloAST * const to, ValueList & list);
265protected:   
266    const String *  mName;
267    Statement *     mNext;
268    Statement *     mPrev;
269    PabloBlock *    mParent;
270    unsigned        mOperands;
271    PabloAST **     mOperand;
272};
273
274class Variadic : public Statement {
275public:
276
277    static inline bool classof(const PabloAST * e) {
278        switch (e->getClassTypeId()) {
279            case PabloAST::ClassTypeId::And:
280            case PabloAST::ClassTypeId::Or:
281            case PabloAST::ClassTypeId::Xor:
282                return true;
283            default: return false;
284        }
285    }
286    static inline bool classof(const Variadic *) {
287        return true;
288    }
289    static inline bool classof(const void *) {
290        return false;
291    }
292
293    class iterator : public boost::iterator_facade<iterator, PabloAST *, boost::random_access_traversal_tag> {
294        friend class Variadic;
295        friend class boost::iterator_core_access;
296    protected:
297
298        iterator(PabloAST ** pointer) : mCurrent(pointer) { }
299        inline void increment() { ++mCurrent; }
300        inline void decrement() { --mCurrent; }
301        inline void advance(const std::ptrdiff_t n) { mCurrent += n; }
302        inline std::ptrdiff_t distance_to(const iterator & other) const { return other.mCurrent - mCurrent; }
303        inline PabloAST *& dereference() const { return *mCurrent; }
304
305        inline bool equal(const iterator & other) const { return (mCurrent == other.mCurrent); }
306
307    private:
308        PabloAST **        mCurrent;
309    };
310
311    using const_iterator = iterator;
312
313    void addOperand(PabloAST * const expr);
314
315    PabloAST * removeOperand(const unsigned index);
316
317    bool deleteOperand(const PabloAST * const expr);
318
319    iterator begin() {
320        return iterator(mOperand);
321    }
322
323    const_iterator begin() const {
324        return iterator(mOperand);
325    }
326
327    iterator end() {
328        return iterator(mOperand + mOperands);
329    }
330
331    const_iterator end() const {
332        return iterator(mOperand + mOperands);
333    }
334
335protected:
336    explicit Variadic(const ClassTypeId id, std::initializer_list<PabloAST *> operands, const String * const name)
337    : Statement(id, operands, name)
338    , mCapacity(operands.size()) {
339
340    }
341    explicit Variadic(const ClassTypeId id, const unsigned reserved, String * name)
342    : Statement(id, reserved, name)
343    , mCapacity(reserved) {
344
345    }
346    template<typename iterator>
347    explicit Variadic(const ClassTypeId id, iterator begin, iterator end, String * name)
348    : Statement(id, begin, end, name)
349    , mCapacity(std::distance(begin, end)) {
350
351    }
352private:
353    unsigned        mCapacity;
354};
355
356bool escapes(const Statement * statement);
357
358class StatementList {
359    friend class Statement;
360    friend class PabloBlock;
361public:
362    class iterator: public std::iterator<std::forward_iterator_tag, Statement> {
363    public:
364        iterator(): mCurrent(nullptr) {}
365
366        iterator(Statement* base): mCurrent(base) {}
367
368        iterator(const iterator& other): mCurrent(other.mCurrent) {}
369
370        const iterator& operator=(const iterator& other) {
371            mCurrent = other.mCurrent; return other;
372        }
373
374        inline iterator& operator++() {
375            assert (mCurrent);
376            mCurrent = mCurrent->mNext;
377            return *this;
378        }
379
380        iterator  operator++(int) {
381            iterator tmp(*this);
382            ++(*this);
383            return tmp;
384        }
385
386        bool operator==(const iterator& other) const {
387            return  mCurrent == other.mCurrent;
388        }
389
390        bool operator!=(const iterator& other) const {
391            return  mCurrent != other.mCurrent;
392        }
393
394        Statement* operator*() {return mCurrent;}
395        Statement* operator->(){return mCurrent;}
396
397    private:
398        Statement * mCurrent;
399        friend class const_iterator;
400    };
401
402    class const_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
403    public:
404        const_iterator(): mCurrent(nullptr) {}
405        const_iterator(const Statement* base): mCurrent(base) {}
406        const_iterator(const const_iterator& other): mCurrent(other.mCurrent) {}
407        const const_iterator& operator=(const const_iterator& other) {mCurrent = other.mCurrent; return other;}
408
409        inline const_iterator& operator++() {
410            assert (mCurrent);
411            mCurrent = mCurrent->mNext;
412            return *this;
413        }
414
415        const_iterator  operator++(int) {
416            const_iterator tmp(*this);
417            ++(*this);
418            return tmp;
419        }
420
421        bool operator==(const const_iterator & other) const {
422            return  mCurrent == other.mCurrent;
423        }
424        bool operator!=(const const_iterator & other) const {
425            return  mCurrent != other.mCurrent;
426        }
427
428        const Statement* operator*() {return mCurrent;}
429        const Statement* operator->(){return mCurrent;}
430
431    private:
432        const Statement * mCurrent;
433        friend struct iterator;
434    };
435
436    class reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
437    public:
438        reverse_iterator(): mCurrent(nullptr) {}
439
440        reverse_iterator(Statement* base): mCurrent(base) {}
441
442        reverse_iterator(const reverse_iterator& other): mCurrent(other.mCurrent) {}
443
444        const reverse_iterator& operator=(const reverse_iterator& other) {
445            mCurrent = other.mCurrent; return other;
446        }
447
448        inline reverse_iterator& operator++() {
449            assert (mCurrent);
450            mCurrent = mCurrent->mPrev;
451            return *this;
452        }
453
454        reverse_iterator operator++(int) {
455            reverse_iterator tmp(*this);
456            ++(*this);
457            return tmp;
458        }
459
460        bool operator==(const reverse_iterator& other) const {
461            return  mCurrent == other.mCurrent;
462        }
463
464        bool operator!=(const reverse_iterator& other) const {
465            return  mCurrent != other.mCurrent;
466        }
467
468        Statement* operator*() {return mCurrent;}
469        Statement* operator->(){return mCurrent;}
470
471    private:
472        Statement * mCurrent;
473        friend class const_reverse_iterator;
474    };
475
476    class const_reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
477    public:
478        const_reverse_iterator(): mCurrent(nullptr) {}
479        const_reverse_iterator(const Statement* base): mCurrent(base) {}
480        const_reverse_iterator(const const_reverse_iterator& other): mCurrent(other.mCurrent) {}
481        const const_reverse_iterator& operator=(const const_reverse_iterator& other) {mCurrent = other.mCurrent; return other;}
482
483        inline const_reverse_iterator& operator++() {
484            assert (mCurrent);
485            mCurrent = mCurrent->mPrev;
486            return *this;
487        }
488
489        const_reverse_iterator  operator++(int) {
490            const_reverse_iterator tmp(*this);
491            ++(*this);
492            return tmp;
493        }
494
495        bool operator==(const const_reverse_iterator & other) const {
496            return  mCurrent == other.mCurrent;
497        }
498        bool operator!=(const const_reverse_iterator & other) const {
499            return  mCurrent != other.mCurrent;
500        }
501
502        const Statement* operator*() {return mCurrent;}
503        const Statement* operator->(){return mCurrent;}
504
505    private:
506        const Statement * mCurrent;
507        friend struct iterator;
508    };
509
510public:
511
512    StatementList()
513    : mInsertionPoint(nullptr)
514    , mFirst(nullptr)
515    , mLast(nullptr) {
516
517    }
518
519    StatementList(StatementList && other)
520    : mInsertionPoint(nullptr)
521    , mFirst(other.mFirst)
522    , mLast(other.mLast) {
523        other.mInsertionPoint = nullptr;
524        other.mFirst = nullptr;
525        other.mLast = nullptr;
526    }
527
528    iterator begin() {
529        return iterator(mFirst);
530    }
531
532    iterator end() {
533        return iterator(nullptr);
534    }
535
536    reverse_iterator rbegin() {
537        return reverse_iterator(mLast);
538    }
539
540    reverse_iterator rend() {
541        return reverse_iterator(nullptr);
542    }
543
544    const_iterator begin() const {
545        return const_iterator(mFirst);
546    }
547
548    const_iterator end() const {
549        return const_iterator(nullptr);
550    }
551
552    const_reverse_iterator rbegin() const {
553        return const_reverse_iterator(mLast);
554    }
555
556    const_reverse_iterator rend() const {
557        return const_reverse_iterator(nullptr);
558    }
559
560    const_iterator cbegin() const {
561        return const_iterator(mFirst);
562    }
563
564    const_iterator cend() const {
565        return const_iterator(nullptr);
566    }
567
568    const_reverse_iterator crbegin() const {
569        return const_reverse_iterator(mLast);
570    }
571
572    const_reverse_iterator crend() const {
573        return const_reverse_iterator(nullptr);
574    }
575
576    inline Statement * front() const {
577        return mFirst;
578    }
579
580    inline Statement * back() const {
581        return mLast;
582    }
583
584    inline void setInsertPoint(Statement * const statement) {
585        assert (statement == nullptr || contains(statement));
586        mInsertionPoint = statement;
587    }
588
589    inline Statement * getInsertPoint() const {
590        return mInsertionPoint;
591    }
592
593    bool contains(Statement * const statement);
594
595protected:
596
597    ~StatementList() = default;
598
599private:
600
601    Statement   * mInsertionPoint;
602    Statement   * mFirst;
603    Statement   * mLast;   
604};
605
606/** ------------------------------------------------------------------------------------------------------------- *
607 * @brief deleteOperand
608 ** ------------------------------------------------------------------------------------------------------------- */
609inline bool Variadic::deleteOperand(const PabloAST * const expr) {
610    for (unsigned i = 0; i != getNumOperands(); ++i) {
611        if (LLVM_UNLIKELY(getOperand(i) == expr)) {
612            removeOperand(i);
613            return true;
614        }
615    }
616    return false;
617}
618
619}
620
621#endif // PE_PabloAST_H
Note: See TracBrowser for help on using the repository browser.