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

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

pablo.InFile? initial support

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