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

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

Bug fixes

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