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

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

UnicodeSet? bug fix and compile warning clean-up.

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