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

Last change on this file since 5217 was 5217, checked in by nmedfort, 2 years ago

Merged PabloFunction? and PabloKernel? classes. Updated projects where necessary.

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