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

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

Initial work on adding types to PabloAST and mutable Var objects.

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