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

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

New kernel infrastructure

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