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

Last change on this file since 4885 was 4885, checked in by nmedfort, 4 years ago

More work on n-ary operations. Unresolved bug in DistributionPass?.

File size: 17.8 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    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    Statement(const ClassTypeId id, unsigned operands, PabloAST * value, const String * const name)
238    : PabloAST(id)
239    , mName(name)
240    , mNext(nullptr)
241    , mPrev(nullptr)
242    , mParent(nullptr)
243    , mOperands(operands)
244    , mOperand(reinterpret_cast<PabloAST**>(mAllocator.allocate(mOperands * sizeof(PabloAST *)))) {
245        for (unsigned i = 0; i != operands; ++i) {
246            assert (value);
247            mOperand[i] = value;
248            value->addUser(this);
249        }
250    }
251    template<typename iterator>
252    explicit Statement(const ClassTypeId id, iterator begin, iterator end, const String * const name)
253    : PabloAST(id)
254    , mName(name)
255    , mNext(nullptr)
256    , mPrev(nullptr)
257    , mParent(nullptr)
258    , mOperands(std::distance(begin, end))
259    , mOperand(reinterpret_cast<PabloAST**>(mAllocator.allocate(mOperands * sizeof(PabloAST *)))) {
260        unsigned i = 0;
261        for (auto value = begin; value != end; ++value, ++i) {
262            assert (*value);
263            mOperand[i] = *value;
264            (*value)->addUser(this);
265        }
266    }
267private:
268    template <class ValueType, class ValueList>
269    void checkEscapedValueList(Statement * branch, PabloAST * const from, PabloAST * const to, ValueList & list);
270protected:   
271    const String *  mName;
272    Statement *     mNext;
273    Statement *     mPrev;
274    PabloBlock *    mParent;
275    unsigned        mOperands;
276    PabloAST **     mOperand;
277};
278
279class Variadic : public Statement {
280public:
281
282    static inline bool classof(const PabloAST * e) {
283        switch (e->getClassTypeId()) {
284            case PabloAST::ClassTypeId::And:
285            case PabloAST::ClassTypeId::Or:
286            case PabloAST::ClassTypeId::Xor:
287                return true;
288            default: return false;
289        }
290    }
291    static inline bool classof(const Variadic *) {
292        return true;
293    }
294    static inline bool classof(const void *) {
295        return false;
296    }
297
298    class iterator : public boost::iterator_facade<iterator, PabloAST *, boost::random_access_traversal_tag> {
299        friend class Variadic;
300        friend class boost::iterator_core_access;
301    protected:
302
303        iterator(PabloAST ** pointer) : mCurrent(pointer) { }
304        inline void increment() { ++mCurrent; }
305        inline void decrement() { --mCurrent; }
306        inline void advance(const std::ptrdiff_t n) { mCurrent += n; }
307        inline std::ptrdiff_t distance_to(const iterator & other) const { return other.mCurrent - mCurrent; }
308        inline PabloAST *& dereference() const { return *mCurrent; }
309
310        inline bool equal(const iterator & other) const { return (mCurrent == other.mCurrent); }
311
312    private:
313        PabloAST **        mCurrent;
314    };
315
316    using const_iterator = iterator;
317
318    void addOperand(PabloAST * const expr);
319
320    PabloAST * removeOperand(const unsigned index);
321
322    bool deleteOperand(const PabloAST * const expr);
323
324    iterator begin() {
325        return iterator(mOperand);
326    }
327
328    const_iterator begin() const {
329        return iterator(mOperand);
330    }
331
332    iterator end() {
333        return iterator(mOperand + mOperands);
334    }
335
336    const_iterator end() const {
337        return iterator(mOperand + mOperands);
338    }
339
340protected:
341    Variadic(const ClassTypeId id, std::initializer_list<PabloAST *> operands, const String * const name)
342    : Statement(id, operands, name)
343    , mCapacity(operands.size()) {
344
345    }
346    Variadic(const ClassTypeId id, const unsigned operands, PabloAST * value, String * name)
347    : Statement(id, operands, value, name)
348    , mCapacity(operands) {
349
350    }
351    template<typename iterator>
352    explicit Variadic(const ClassTypeId id, iterator begin, iterator end, String * name)
353    : Statement(id, begin, end, name)
354    , mCapacity(std::distance(begin, end)) {
355
356    }
357private:
358    unsigned        mCapacity;
359};
360
361bool escapes(const Statement * statement);
362
363class StatementList {
364    friend class Statement;
365    friend class PabloBlock;
366public:
367    class iterator: public std::iterator<std::forward_iterator_tag, Statement> {
368    public:
369        iterator(): mCurrent(nullptr) {}
370
371        iterator(Statement* base): mCurrent(base) {}
372
373        iterator(const iterator& other): mCurrent(other.mCurrent) {}
374
375        const iterator& operator=(const iterator& other) {
376            mCurrent = other.mCurrent; return other;
377        }
378
379        inline iterator& operator++() {
380            assert (mCurrent);
381            mCurrent = mCurrent->mNext;
382            return *this;
383        }
384
385        iterator  operator++(int) {
386            iterator tmp(*this);
387            ++(*this);
388            return tmp;
389        }
390
391        bool operator==(const iterator& other) const {
392            return  mCurrent == other.mCurrent;
393        }
394
395        bool operator!=(const iterator& other) const {
396            return  mCurrent != other.mCurrent;
397        }
398
399        Statement* operator*() {return mCurrent;}
400        Statement* operator->(){return mCurrent;}
401
402    private:
403        Statement * mCurrent;
404        friend class const_iterator;
405    };
406
407    class const_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
408    public:
409        const_iterator(): mCurrent(nullptr) {}
410        const_iterator(const Statement* base): mCurrent(base) {}
411        const_iterator(const const_iterator& other): mCurrent(other.mCurrent) {}
412        const const_iterator& operator=(const const_iterator& other) {mCurrent = other.mCurrent; return other;}
413
414        inline const_iterator& operator++() {
415            assert (mCurrent);
416            mCurrent = mCurrent->mNext;
417            return *this;
418        }
419
420        const_iterator  operator++(int) {
421            const_iterator tmp(*this);
422            ++(*this);
423            return tmp;
424        }
425
426        bool operator==(const const_iterator & other) const {
427            return  mCurrent == other.mCurrent;
428        }
429        bool operator!=(const const_iterator & other) const {
430            return  mCurrent != other.mCurrent;
431        }
432
433        const Statement* operator*() {return mCurrent;}
434        const Statement* operator->(){return mCurrent;}
435
436    private:
437        const Statement * mCurrent;
438        friend struct iterator;
439    };
440
441    class reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
442    public:
443        reverse_iterator(): mCurrent(nullptr) {}
444
445        reverse_iterator(Statement* base): mCurrent(base) {}
446
447        reverse_iterator(const reverse_iterator& other): mCurrent(other.mCurrent) {}
448
449        const reverse_iterator& operator=(const reverse_iterator& other) {
450            mCurrent = other.mCurrent; return other;
451        }
452
453        inline reverse_iterator& operator++() {
454            assert (mCurrent);
455            mCurrent = mCurrent->mPrev;
456            return *this;
457        }
458
459        reverse_iterator operator++(int) {
460            reverse_iterator tmp(*this);
461            ++(*this);
462            return tmp;
463        }
464
465        bool operator==(const reverse_iterator& other) const {
466            return  mCurrent == other.mCurrent;
467        }
468
469        bool operator!=(const reverse_iterator& other) const {
470            return  mCurrent != other.mCurrent;
471        }
472
473        Statement* operator*() {return mCurrent;}
474        Statement* operator->(){return mCurrent;}
475
476    private:
477        Statement * mCurrent;
478        friend class const_reverse_iterator;
479    };
480
481    class const_reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
482    public:
483        const_reverse_iterator(): mCurrent(nullptr) {}
484        const_reverse_iterator(const Statement* base): mCurrent(base) {}
485        const_reverse_iterator(const const_reverse_iterator& other): mCurrent(other.mCurrent) {}
486        const const_reverse_iterator& operator=(const const_reverse_iterator& other) {mCurrent = other.mCurrent; return other;}
487
488        inline const_reverse_iterator& operator++() {
489            assert (mCurrent);
490            mCurrent = mCurrent->mPrev;
491            return *this;
492        }
493
494        const_reverse_iterator  operator++(int) {
495            const_reverse_iterator tmp(*this);
496            ++(*this);
497            return tmp;
498        }
499
500        bool operator==(const const_reverse_iterator & other) const {
501            return  mCurrent == other.mCurrent;
502        }
503        bool operator!=(const const_reverse_iterator & other) const {
504            return  mCurrent != other.mCurrent;
505        }
506
507        const Statement* operator*() {return mCurrent;}
508        const Statement* operator->(){return mCurrent;}
509
510    private:
511        const Statement * mCurrent;
512        friend struct iterator;
513    };
514
515public:
516
517    StatementList()
518    : mInsertionPoint(nullptr)
519    , mFirst(nullptr)
520    , mLast(nullptr) {
521
522    }
523
524    StatementList(StatementList && other)
525    : mInsertionPoint(nullptr)
526    , mFirst(other.mFirst)
527    , mLast(other.mLast) {
528        other.mInsertionPoint = nullptr;
529        other.mFirst = nullptr;
530        other.mLast = nullptr;
531    }
532
533    iterator begin() {
534        return iterator(mFirst);
535    }
536
537    iterator end() {
538        return iterator(nullptr);
539    }
540
541    reverse_iterator rbegin() {
542        return reverse_iterator(mLast);
543    }
544
545    reverse_iterator rend() {
546        return reverse_iterator(nullptr);
547    }
548
549    const_iterator begin() const {
550        return const_iterator(mFirst);
551    }
552
553    const_iterator end() const {
554        return const_iterator(nullptr);
555    }
556
557    const_reverse_iterator rbegin() const {
558        return const_reverse_iterator(mLast);
559    }
560
561    const_reverse_iterator rend() const {
562        return const_reverse_iterator(nullptr);
563    }
564
565    const_iterator cbegin() const {
566        return const_iterator(mFirst);
567    }
568
569    const_iterator cend() const {
570        return const_iterator(nullptr);
571    }
572
573    const_reverse_iterator crbegin() const {
574        return const_reverse_iterator(mLast);
575    }
576
577    const_reverse_iterator crend() const {
578        return const_reverse_iterator(nullptr);
579    }
580
581    inline Statement * front() const {
582        return mFirst;
583    }
584
585    inline Statement * back() const {
586        return mLast;
587    }
588
589    inline void setInsertPoint(Statement * const statement) {
590        assert (statement == nullptr || contains(statement));
591        mInsertionPoint = statement;
592    }
593
594    inline Statement * getInsertPoint() const {
595        return mInsertionPoint;
596    }
597
598    bool contains(Statement * const statement);
599
600protected:
601
602    ~StatementList() = default;
603
604private:
605
606    Statement   * mInsertionPoint;
607    Statement   * mFirst;
608    Statement   * mLast;   
609};
610
611/** ------------------------------------------------------------------------------------------------------------- *
612 * @brief addUser
613 ** ------------------------------------------------------------------------------------------------------------- */
614inline void PabloAST::addUser(PabloAST *user) {
615    assert (user);   
616    // Note: for the rare situation that this node is used multiple times by a statement, duplicates are allowed.
617    mUsers.insert(std::lower_bound(mUsers.begin(), mUsers.end(), user), user);
618}
619
620/** ------------------------------------------------------------------------------------------------------------- *
621 * @brief removeUser
622 ** ------------------------------------------------------------------------------------------------------------- */
623inline void PabloAST::removeUser(PabloAST * user) {
624    assert (user);
625    auto pos = std::lower_bound(mUsers.begin(), mUsers.end(), user);
626    assert ("Could not find user to remove!" && (pos != mUsers.end() && *pos == user));
627    mUsers.erase(pos);
628}
629
630/** ------------------------------------------------------------------------------------------------------------- *
631 * @brief removeOperand
632 ** ------------------------------------------------------------------------------------------------------------- */
633inline bool Variadic::deleteOperand(const PabloAST * const expr) {
634    for (unsigned i = 0; i != getNumOperands(); ++i) {
635        if (getOperand(i) == expr) {
636            removeOperand(i);
637            return true;
638        }
639    }
640    return false;
641}
642
643}
644
645#endif // PE_PabloAST_H
Note: See TracBrowser for help on using the repository browser.