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
RevLine 
[4244]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>
[4280]11#include <llvm/Support/Compiler.h>
[4885]12#include <boost/iterator/iterator_facade.hpp>
13#include <iterator>
[4272]14#include <slab_allocator.h>
[4885]15#include <type_traits>
[4284]16#include <unordered_map>
[4885]17#include <vector>
[4244]18
19using namespace llvm;
20
21namespace pablo {
22
[4270]23class PabloBlock;
[4438]24class String;
[4856]25class Statement;
[4270]26
[4244]27class PabloAST {
[4414]28    friend class Statement;
[4876]29    friend class Variadic;
[4860]30    friend class StatementList;
[4414]31    friend class Var;
[4656]32    friend class If;   
[4404]33    friend class While;
34    friend class PabloBlock;
[4680]35    friend class Prototype;
[4657]36    friend class PabloFunction;
[4404]37    friend class SymbolGenerator;
[4244]38public:
[4416]39
[4510]40    using Allocator = SlabAllocator<u_int8_t>;
[4860]41    using VectorAllocator = Allocator::rebind<PabloAST *>::other;
[4876]42    using Users = std::vector<PabloAST *, VectorAllocator>;
43    using user_iterator = Users::iterator;
44    using const_user_iterator = Users::const_iterator;
[4416]45
[4244]46    enum class ClassTypeId : unsigned {
[4711]47        /** Non-statements **/
[4656]48        // Constants
49        Zeroes
50        , Ones
[4711]51        // Internal types
52        , Var
53        , Integer
54        , String
55        , Block
56        , Function
57        , Prototype
58        /** Statements **/
[4656]59        // Boolean operations
[4244]60        , And
[4656]61        , Or
62        , Not
63        , Xor
64        , Sel
65        // Stream operations
66        , Advance
67        , ScanThru
68        , MatchStar
[4717]69        // Mod 64 approximate stream operations
70        , Mod64Advance
71        , Mod64ScanThru
72        , Mod64MatchStar
[4718]73        // Statistics operations
74        , Count
[4656]75        // Variable assignments
[4252]76        , Assign
[4656]77        , Next
[4244]78        , Call
[4699]79        , SetIthBit
[4656]80        // Scope blocks
[4252]81        , If
[4656]82        , While
[4244]83    };
84    inline ClassTypeId getClassTypeId() const {
85        return mClassTypeId;
86    }
[4280]87
[4443]88    inline user_iterator user_begin() {
[4416]89        return mUsers.begin();
90    }
91
[4443]92    inline user_iterator user_end() {
[4416]93        return mUsers.end();
94    }
95
[4443]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
[4878]104    inline unsigned getNumUsers() const {
105        return mUsers.size();
106    }
107
[4876]108    inline Users & users() {
[4416]109        return mUsers;
110    }
111
[4876]112    inline const Users & users() const {
[4416]113        return mUsers;
114    }
115
116    void replaceAllUsesWith(PabloAST * expr);
117
[4876]118    inline Users::size_type getNumUses() const {
[4416]119        return mUsers.size();
120    }
121
[4284]122    void* operator new (std::size_t size) noexcept {
123        return mAllocator.allocate(size);
124    }
[4860]125
126    void operator delete (void * ptr) {
127        mAllocator.deallocate(static_cast<Allocator::value_type *>(ptr));
128    }
129
[4244]130protected:
131    inline PabloAST(const ClassTypeId id)
[4270]132    : mClassTypeId(id)
[4860]133    , mUsers(reinterpret_cast<VectorAllocator &>(mAllocator))
[4270]134    {
[4244]135
136    }
[4876]137    void addUser(PabloAST * user);
138    void removeUser(PabloAST * user);
[4432]139    virtual ~PabloAST() {
140        mUsers.clear();
141    }
[4404]142    static Allocator        mAllocator;
[4244]143private:
[4404]144    const ClassTypeId       mClassTypeId;
[4876]145    Users                   mUsers;
[4244]146};
147
148bool equals(const PabloAST * expr1, const PabloAST *expr2);
149
[4280]150class StatementList;
151
[4410]152class String;
153
[4276]154class Statement : public PabloAST {
155    friend class StatementList;
[4280]156    friend class If;
157    friend class While;
[4416]158    friend class Simplifier;
[4404]159    friend class PabloBlock;
[4856]160    template <class ValueType, class ValueList>
[4871]161    friend void checkEscapedValueList(const Statement *, const PabloAST * const, PabloAST * const, ValueList &);
[4276]162public:
[4280]163    static inline bool classof(const PabloAST * e) {
164        switch (e->getClassTypeId()) {
[4416]165            case PabloAST::ClassTypeId::Zeroes:
166            case PabloAST::ClassTypeId::Ones:
167            case PabloAST::ClassTypeId::Var:
[4711]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:
[4410]173                return false;
174            default:
[4280]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
[4856]185    void replaceUsesOfWith(PabloAST * const from, PabloAST * const to);
[4410]186
[4416]187    inline PabloAST * getOperand(const unsigned index) const {
[4414]188        assert (index < getNumOperands());
189        return mOperand[index];
190    }
[4410]191
[4432]192    void setOperand(const unsigned index, PabloAST * const value);
[4415]193
[4416]194    inline unsigned getNumOperands() const {
[4432]195        return mOperands;
[4414]196    }
[4410]197
[4404]198    void insertBefore(Statement * const statement);
199    void insertAfter(Statement * const statement);
[4416]200    Statement * removeFromParent();
201    Statement * eraseFromParent(const bool recursively = false);
[4586]202    Statement * replaceWith(PabloAST * const expr, const bool rename = true, const bool recursively = false);
[4404]203
[4410]204    inline const String * getName() const {
205        return mName;
206    }
[4841]207    inline void setName(const String * const name) {
208        mName = name;
209    }
[4284]210    inline Statement * getNextNode() const {
211        return mNext;
212    }
213    inline Statement * getPrevNode() const {
214        return mPrev;
215    }
[4404]216    inline PabloBlock * getParent() const {
[4284]217        return mParent;
218    }
[4432]219    virtual ~Statement() {}
[4280]220protected:
[4650]221    Statement(const ClassTypeId id, std::initializer_list<PabloAST *> operands, const String * const name)
[4276]222    : PabloAST(id)
[4410]223    , mName(name)
[4276]224    , mNext(nullptr)
225    , mPrev(nullptr)
[4650]226    , mParent(nullptr)
[4432]227    , mOperands(operands.size())
[4650]228    , mOperand(reinterpret_cast<PabloAST**>(mAllocator.allocate(mOperands * sizeof(PabloAST *)))) {
[4432]229        unsigned i = 0;
[4878]230        for (PabloAST * const value : operands) {
231            assert (value);
232            mOperand[i] = value;
233            value->addUser(this);
234            ++i;
[4414]235        }
[4885]236    }
[4878]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    }
[4885]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    }
[4856]267private:
268    template <class ValueType, class ValueList>
[4871]269    void checkEscapedValueList(Statement * branch, PabloAST * const from, PabloAST * const to, ValueList & list);
[4432]270protected:   
[4873]271    const String *  mName;
272    Statement *     mNext;
273    Statement *     mPrev;
274    PabloBlock *    mParent;
275    unsigned        mOperands;
276    PabloAST **     mOperand;
[4276]277};
278
[4873]279class Variadic : public Statement {
280public:
[4876]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; }
[4878]306        inline void advance(const std::ptrdiff_t n) { mCurrent += n; }
[4876]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
[4885]322    bool deleteOperand(const PabloAST * const expr);
[4880]323
[4876]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
[4873]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    }
[4878]346    Variadic(const ClassTypeId id, const unsigned operands, PabloAST * value, String * name)
347    : Statement(id, operands, value, name)
348    , mCapacity(operands) {
349
350    }
[4885]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    }
[4873]357private:
358    unsigned        mCapacity;
359};
360
[4774]361bool escapes(const Statement * statement);
362
[4276]363class StatementList {
[4280]364    friend class Statement;
[4650]365    friend class PabloBlock;
[4280]366public:
[4276]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;
[4358]438        friend struct iterator;
[4276]439    };
440
[4280]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;
[4358]512        friend struct iterator;
[4280]513    };
514
[4276]515public:
516
517    StatementList()
[4415]518    : mInsertionPoint(nullptr)
519    , mFirst(nullptr)
[4876]520    , mLast(nullptr) {
[4276]521
522    }
523
524    StatementList(StatementList && other)
[4876]525    : mInsertionPoint(nullptr)
526    , mFirst(other.mFirst)
527    , mLast(other.mLast) {
528        other.mInsertionPoint = nullptr;
[4276]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
[4280]541    reverse_iterator rbegin() {
542        return reverse_iterator(mLast);
543    }
544
545    reverse_iterator rend() {
546        return reverse_iterator(nullptr);
547    }
548
[4276]549    const_iterator begin() const {
550        return const_iterator(mFirst);
551    }
552
553    const_iterator end() const {
554        return const_iterator(nullptr);
555    }
556
[4280]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
[4276]565    const_iterator cbegin() const {
566        return const_iterator(mFirst);
567    }
568
569    const_iterator cend() const {
570        return const_iterator(nullptr);
571    }
572
[4280]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
[4416]581    inline Statement * front() const {
[4280]582        return mFirst;
583    }
584
[4416]585    inline Statement * back() const {
[4280]586        return mLast;
587    }
588
[4416]589    inline void setInsertPoint(Statement * const statement) {
[4775]590        assert (statement == nullptr || contains(statement));
[4416]591        mInsertionPoint = statement;
592    }
[4276]593
[4416]594    inline Statement * getInsertPoint() const {
[4415]595        return mInsertionPoint;
596    }
597
[4775]598    bool contains(Statement * const statement);
599
[4876]600protected:
601
602    ~StatementList() = default;
603
[4276]604private:
[4415]605
606    Statement   * mInsertionPoint;
[4404]607    Statement   * mFirst;
[4415]608    Statement   * mLast;   
[4276]609};
610
[4876]611/** ------------------------------------------------------------------------------------------------------------- *
612 * @brief addUser
613 ** ------------------------------------------------------------------------------------------------------------- */
614inline void PabloAST::addUser(PabloAST *user) {
[4878]615    assert (user);   
[4876]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);
[4244]618}
619
[4876]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}
[4244]629
[4880]630/** ------------------------------------------------------------------------------------------------------------- *
631 * @brief removeOperand
632 ** ------------------------------------------------------------------------------------------------------------- */
[4885]633inline bool Variadic::deleteOperand(const PabloAST * const expr) {
[4880]634    for (unsigned i = 0; i != getNumOperands(); ++i) {
635        if (getOperand(i) == expr) {
636            removeOperand(i);
[4885]637            return true;
[4880]638        }
639    }
[4885]640    return false;
[4876]641}
[4244]642
[4880]643}
644
[4876]645#endif // PE_PabloAST_H
Note: See TracBrowser for help on using the repository browser.