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

Last change on this file since 4995 was 4983, checked in by cameron, 3 years ago

Move items to util directory

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