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

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

Initial work for incorporating Types into Pablo AST.

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