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

Last change on this file since 5705 was 5705, checked in by cameron, 21 months ago

Drop linebreak normalization; add1 attribute for grep kernel; pablo indexed advance initial check-in

File size: 19.4 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>
[4983]13#include <util/slab_allocator.h>
[4885]14#include <type_traits>
15#include <vector>
[5267]16namespace llvm { class Type; }
17namespace llvm { class raw_ostream; }
18namespace pablo { class PabloBlock; }
19namespace pablo { class String; }
[4244]20
21namespace pablo {
22
23class PabloAST {
[4414]24    friend class Statement;
[4876]25    friend class Variadic;
[4860]26    friend class StatementList;
[5202]27    friend class Branch;
[4404]28    friend class PabloBlock;
29    friend class SymbolGenerator;
[5063]30    friend class Count;
[5202]31    friend class Var;
[5227]32    friend class Operator;
[4244]33public:
[4416]34
[5230]35    using Allocator = SlabAllocator<PabloAST *>;
[5486]36    using Users = std::vector<PabloAST *, ProxyAllocator<PabloAST *>>;
[4876]37    using user_iterator = Users::iterator;
38    using const_user_iterator = Users::const_iterator;
[4416]39
[5202]40    static inline bool classof(const PabloAST *) {
41        return true;
42    }
43    static inline bool classof(const void *) {
44        return false;
45    }
46
[4244]47    enum class ClassTypeId : unsigned {
[5368]48        /** Expressions and Constants **/
[4656]49        // Constants
50        Zeroes
51        , Ones
[5227]52        // Arithmetic expressions
53        , Add
54        , Subtract
55        // Relational expressions
56        , LessThan
57        , LessThanEquals
58        , Equals
59        , GreaterThanEquals
60        , GreaterThan
61        , NotEquals
[5368]62        // Internal types
63        , Var
64        , Integer
65        , String
66        , Block
67        , Kernel
[5371]68        , Phi
[4711]69        /** Statements **/
[4656]70        // Boolean operations
[4244]71        , And
[4656]72        , Or
73        , Xor
[4896]74        , Not       
[4656]75        , Sel
76        // Stream operations
77        , Advance
[5705]78        , IndexedAdvance
[4656]79        , ScanThru
[5329]80        , AdvanceThenScanThru
81        , ScanTo
82        , AdvanceThenScanTo
[4959]83        , Lookahead
[4656]84        , MatchStar
[5023]85        , InFile
[5042]86        , AtEOF
[4718]87        // Statistics operations
88        , Count
[4656]89        // Variable assignments
[4252]90        , Assign
[5202]91        , Extract     
[4656]92        // Scope blocks
[4252]93        , If
[4656]94        , While
[4244]95    };
[5202]96
97    inline ClassTypeId getClassTypeId() const noexcept {
[4244]98        return mClassTypeId;
99    }
[4280]100
[5202]101    inline llvm::Type * getType() const noexcept {
102        return mType;
103    }
104
[5267]105    inline void setType(llvm::Type * type) noexcept {
[5202]106        mType = type;
107    }
108
[4443]109    inline user_iterator user_begin() {
[4416]110        return mUsers.begin();
111    }
112
[4443]113    inline user_iterator user_end() {
[4416]114        return mUsers.end();
115    }
116
[4443]117    inline const_user_iterator user_begin() const {
118        return mUsers.cbegin();
119    }
120
121    inline const_user_iterator user_end() const {
122        return mUsers.cend();
123    }
124
[4876]125    inline Users & users() {
[4416]126        return mUsers;
127    }
128
[4876]129    inline const Users & users() const {
[4416]130        return mUsers;
131    }
132
[4899]133    void replaceAllUsesWith(PabloAST * const expr);
[4416]134
[4876]135    inline Users::size_type getNumUses() const {
[4416]136        return mUsers.size();
137    }
138
[5230]139    void * operator new (std::size_t size, Allocator & allocator) noexcept {
140        return allocator.allocate<uint8_t>(size);
[4284]141    }
[4860]142
[5230]143//    void operator delete (void * ptr) {
144//        mAllocator.deallocate(static_cast<Allocator::value_type *>(ptr));
145//    }
[4860]146
[5267]147    void print(llvm::raw_ostream & O) const;
[5202]148
[4244]149protected:
[5283]150    inline PabloAST(const ClassTypeId id, llvm::Type * const type, Allocator & allocator)
[4270]151    : mClassTypeId(id)
[5160]152    , mType(type)
[5230]153    , mUsers(allocator) {
[4244]154
155    }
[5202]156    bool addUser(PabloAST * const user);
[5486]157
[5202]158    bool removeUser(PabloAST * const user);
[5486]159
160    virtual ~PabloAST() = default;
161
[4244]162private:
[4404]163    const ClassTypeId       mClassTypeId;
[5267]164    llvm::Type *            mType;
[4876]165    Users                   mUsers;
[4244]166};
167
[5156]168bool equals(const PabloAST * const expr1, const PabloAST * const expr2);
[4244]169
[5156]170bool dominates(const PabloAST * const expr1, const PabloAST * const expr2);
171
[5510]172inline bool strictly_dominates(const PabloAST * const expr1, const PabloAST * const expr2) {
173    return (expr1 != expr2) && dominates(expr1, expr2);
174}
175
[5202]176bool postdominates(const PabloAST * const expr1, const PabloAST * const expr2);
177
[5510]178inline bool strictly_postdominates(const PabloAST * const expr1, const PabloAST * const expr2) {
179    return (expr1 != expr2) && postdominates(expr1, expr2);
180}
181
[4280]182class StatementList;
183
[4410]184class String;
185
[4276]186class Statement : public PabloAST {
187    friend class StatementList;
[4280]188    friend class If;
189    friend class While;
[4416]190    friend class Simplifier;
[4404]191    friend class PabloBlock;
[4276]192public:
[4280]193    static inline bool classof(const PabloAST * e) {
[5227]194        return ((unsigned)e->getClassTypeId() >= (unsigned)PabloAST::ClassTypeId::And);
[4280]195    }
196    static inline bool classof(const Statement *) {
197        return true;
198    }
199    static inline bool classof(const void *) {
200        return false;
201    }
202
[4856]203    void replaceUsesOfWith(PabloAST * const from, PabloAST * const to);
[4410]204
[5283]205    const String & getName() const noexcept {
206        return *mName;
207    }
208
209    void setName(const String * const name) noexcept;
210
[4416]211    inline PabloAST * getOperand(const unsigned index) const {
[4414]212        assert (index < getNumOperands());
213        return mOperand[index];
214    }
[4410]215
[4432]216    void setOperand(const unsigned index, PabloAST * const value);
[4415]217
[4416]218    inline unsigned getNumOperands() const {
[4432]219        return mOperands;
[4414]220    }
[4410]221
[4404]222    void insertBefore(Statement * const statement);
223    void insertAfter(Statement * const statement);
[4416]224    Statement * removeFromParent();
225    Statement * eraseFromParent(const bool recursively = false);
[4586]226    Statement * replaceWith(PabloAST * const expr, const bool rename = true, const bool recursively = false);
[4404]227
[4284]228    inline Statement * getNextNode() const {
229        return mNext;
230    }
231    inline Statement * getPrevNode() const {
232        return mPrev;
233    }
[4404]234    inline PabloBlock * getParent() const {
[4284]235        return mParent;
236    }
[5486]237    virtual ~Statement() = default;
238
[4280]239protected:
[5283]240
[5267]241    explicit Statement(const ClassTypeId id, llvm::Type * const type, std::initializer_list<PabloAST *> operands, const String * const name, Allocator & allocator)
[5283]242    : PabloAST(id, type, allocator)
243    , mOperands(operands.size())
244    , mOperand(allocator.allocate(mOperands))
[4276]245    , mNext(nullptr)
246    , mPrev(nullptr)
[5283]247    , mName(name)
248    , mParent(nullptr) {
[4432]249        unsigned i = 0;
[4878]250        for (PabloAST * const value : operands) {
251            assert (value);
252            mOperand[i] = value;
253            value->addUser(this);
254            ++i;
[4414]255        }
[4885]256    }
[5283]257
[5267]258    explicit Statement(const ClassTypeId id, llvm::Type * const type, const unsigned reserved, const String * const name, Allocator & allocator)
[5283]259    : PabloAST(id, type, allocator)
260    , mOperands(0)
[5371]261    , mOperand(allocator.allocate(reserved))
[4878]262    , mNext(nullptr)
263    , mPrev(nullptr)
[5283]264    , mName(name)
265    , mParent(nullptr) {
[4965]266        std::memset(mOperand, 0, reserved * sizeof(PabloAST *));
[4878]267    }
[5283]268
[4885]269    template<typename iterator>
[5267]270    explicit Statement(const ClassTypeId id, llvm::Type * const type, iterator begin, iterator end, const String * const name, Allocator & allocator)
[5283]271    : PabloAST(id, type, allocator)
272    , mOperands(std::distance(begin, end))
273    , mOperand(allocator.allocate(mOperands))
[4885]274    , mNext(nullptr)
275    , mPrev(nullptr)
[5283]276    , mName(name)
277    , mParent(nullptr) {
[4885]278        unsigned i = 0;
279        for (auto value = begin; value != end; ++value, ++i) {
280            assert (*value);
281            mOperand[i] = *value;
282            (*value)->addUser(this);
283        }
284    }
[5283]285
[4432]286protected:   
[5283]287    unsigned        mOperands;
288    PabloAST **     mOperand;
[4873]289    Statement *     mNext;
290    Statement *     mPrev;
[5283]291    const String *  mName;
[4873]292    PabloBlock *    mParent;
[4276]293};
294
[5486]295class CarryProducingStatement : public Statement {
296public:
297
298    static inline bool classof(const PabloAST * e) {
299        switch (e->getClassTypeId()) {
300            case PabloAST::ClassTypeId::Advance:
[5705]301            case PabloAST::ClassTypeId::IndexedAdvance:
[5486]302            case PabloAST::ClassTypeId::ScanThru:
303            case PabloAST::ClassTypeId::AdvanceThenScanThru:
304            case PabloAST::ClassTypeId::ScanTo:
305            case PabloAST::ClassTypeId::AdvanceThenScanTo:
306            case PabloAST::ClassTypeId::MatchStar:
307                return true;
308            default: return false;
309        }
310    }
311    static inline bool classof(const CarryProducingStatement *) {
312        return true;
313    }
314    static inline bool classof(const void *) {
315        return false;
316    }
317
318    unsigned getCarryGroup() const {
319        return mCarryGroup;
320    }
321
322    void setCarryGroup(const unsigned carryGroup) {
323        mCarryGroup = carryGroup;
324    }
325
[5510]326    unsigned getCarryWidth() const {
327        return mCarryWidth;
328    }
329
330    void setCarryWidth(const unsigned carryWidth) {
331        mCarryWidth = carryWidth;
332    }
333
[5486]334    virtual ~CarryProducingStatement() = default;
335
336protected:
337
338    explicit CarryProducingStatement(const ClassTypeId id, llvm::Type * const type, std::initializer_list<PabloAST *> operands, const String * const name, Allocator & allocator)
339    : Statement(id, type, operands, name, allocator)
[5510]340    , mCarryGroup(0)
341    , mCarryWidth(0) {
[5486]342
343    }
344
345    explicit CarryProducingStatement(const ClassTypeId id, llvm::Type * const type, const unsigned reserved, const String * name, Allocator & allocator)
346    : Statement(id, type, reserved, name, allocator)
[5510]347    , mCarryGroup(0)
348    , mCarryWidth(0) {
[5486]349
350    }
351
352    template<typename iterator>
353    explicit CarryProducingStatement(const ClassTypeId id, llvm::Type * const type, iterator begin, iterator end, const String * name, Allocator & allocator)
354    : Statement(id, type, begin, end, name, allocator)
[5510]355    , mCarryGroup(0)
356    , mCarryWidth(0) {
[5486]357
358    }
359
360private:
361
362    unsigned mCarryGroup;
[5510]363    unsigned mCarryWidth;
[5486]364};
365
366
[4873]367class Variadic : public Statement {
368public:
[4876]369
370    static inline bool classof(const PabloAST * e) {
371        switch (e->getClassTypeId()) {
372            case PabloAST::ClassTypeId::And:
373            case PabloAST::ClassTypeId::Or:
374            case PabloAST::ClassTypeId::Xor:
375                return true;
376            default: return false;
377        }
378    }
379    static inline bool classof(const Variadic *) {
380        return true;
381    }
382    static inline bool classof(const void *) {
383        return false;
384    }
385
386    class iterator : public boost::iterator_facade<iterator, PabloAST *, boost::random_access_traversal_tag> {
387        friend class Variadic;
388        friend class boost::iterator_core_access;
389    protected:
390
391        iterator(PabloAST ** pointer) : mCurrent(pointer) { }
392        inline void increment() { ++mCurrent; }
393        inline void decrement() { --mCurrent; }
[4878]394        inline void advance(const std::ptrdiff_t n) { mCurrent += n; }
[4876]395        inline std::ptrdiff_t distance_to(const iterator & other) const { return other.mCurrent - mCurrent; }
396        inline PabloAST *& dereference() const { return *mCurrent; }
397
398        inline bool equal(const iterator & other) const { return (mCurrent == other.mCurrent); }
399
400    private:
401        PabloAST **        mCurrent;
402    };
403
404    using const_iterator = iterator;
405
406    void addOperand(PabloAST * const expr);
407
408    PabloAST * removeOperand(const unsigned index);
409
[4885]410    bool deleteOperand(const PabloAST * const expr);
[4880]411
[4876]412    iterator begin() {
413        return iterator(mOperand);
414    }
415
416    const_iterator begin() const {
417        return iterator(mOperand);
418    }
419
420    iterator end() {
421        return iterator(mOperand + mOperands);
422    }
423
424    const_iterator end() const {
425        return iterator(mOperand + mOperands);
426    }
427
[5486]428    virtual ~Variadic() = default;
429
[4873]430protected:
[5267]431    explicit Variadic(const ClassTypeId id, llvm::Type * const type, std::initializer_list<PabloAST *> operands, const String * const name, Allocator & allocator)
[5230]432    : Statement(id, type, operands, name, allocator)
433    , mCapacity(operands.size())
434    , mAllocator(allocator) {
[4873]435
436    }
[5267]437    explicit Variadic(const ClassTypeId id, llvm::Type * const type, const unsigned reserved, const String * name, Allocator & allocator)
[5230]438    : Statement(id, type, reserved, name, allocator)
439    , mCapacity(reserved)
440    , mAllocator(allocator) {
[4878]441
442    }
[4885]443    template<typename iterator>
[5267]444    explicit Variadic(const ClassTypeId id, llvm::Type * const type, iterator begin, iterator end, const String * name, Allocator & allocator)
[5230]445    : Statement(id, type, begin, end, name, allocator)
446    , mCapacity(std::distance(begin, end))
447    , mAllocator(allocator) {
[4885]448
449    }
[4873]450private:
451    unsigned        mCapacity;
[5230]452    Allocator &     mAllocator;
[4873]453};
454
[4276]455class StatementList {
[4280]456    friend class Statement;
[4650]457    friend class PabloBlock;
[4280]458public:
[4276]459    class iterator: public std::iterator<std::forward_iterator_tag, Statement> {
460    public:
461        iterator(): mCurrent(nullptr) {}
462
463        iterator(Statement* base): mCurrent(base) {}
464
[5647]465        iterator(const iterator & other): mCurrent(other.mCurrent) {}
[4276]466
[5647]467        iterator & operator=(const iterator & other) {
468            mCurrent = other.mCurrent;
469            return *this;
[4276]470        }
471
472        inline iterator& operator++() {
473            assert (mCurrent);
474            mCurrent = mCurrent->mNext;
475            return *this;
476        }
477
[5647]478        iterator operator++(int) {
[4276]479            iterator tmp(*this);
480            ++(*this);
481            return tmp;
482        }
483
[5647]484        bool operator==(const iterator & other) const {
[4276]485            return  mCurrent == other.mCurrent;
486        }
487
[5647]488        bool operator!=(const iterator & other) const {
[4276]489            return  mCurrent != other.mCurrent;
490        }
491
492        Statement* operator*() {return mCurrent;}
493        Statement* operator->(){return mCurrent;}
494
495    private:
496        Statement * mCurrent;
497        friend class const_iterator;
498    };
499
500    class const_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
501    public:
502        const_iterator(): mCurrent(nullptr) {}
503        const_iterator(const Statement* base): mCurrent(base) {}
504        const_iterator(const const_iterator& other): mCurrent(other.mCurrent) {}
[5647]505        const_iterator& operator=(const const_iterator & other) {
506            mCurrent = other.mCurrent;
507            return *this;
508        }
[4276]509
510        inline const_iterator& operator++() {
511            assert (mCurrent);
512            mCurrent = mCurrent->mNext;
513            return *this;
514        }
515
516        const_iterator  operator++(int) {
517            const_iterator tmp(*this);
518            ++(*this);
519            return tmp;
520        }
521
522        bool operator==(const const_iterator & other) const {
523            return  mCurrent == other.mCurrent;
524        }
525        bool operator!=(const const_iterator & other) const {
526            return  mCurrent != other.mCurrent;
527        }
528
529        const Statement* operator*() {return mCurrent;}
530        const Statement* operator->(){return mCurrent;}
531
532    private:
533        const Statement * mCurrent;
[4358]534        friend struct iterator;
[4276]535    };
536
[4280]537    class reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
538    public:
539        reverse_iterator(): mCurrent(nullptr) {}
540
541        reverse_iterator(Statement* base): mCurrent(base) {}
542
543        reverse_iterator(const reverse_iterator& other): mCurrent(other.mCurrent) {}
544
[5647]545        reverse_iterator & operator=(const reverse_iterator & other) {
546            mCurrent = other.mCurrent;
547            return *this;
[4280]548        }
549
550        inline reverse_iterator& operator++() {
551            assert (mCurrent);
552            mCurrent = mCurrent->mPrev;
553            return *this;
554        }
555
556        reverse_iterator operator++(int) {
557            reverse_iterator tmp(*this);
558            ++(*this);
559            return tmp;
560        }
561
562        bool operator==(const reverse_iterator& other) const {
563            return  mCurrent == other.mCurrent;
564        }
565
566        bool operator!=(const reverse_iterator& other) const {
567            return  mCurrent != other.mCurrent;
568        }
569
570        Statement* operator*() {return mCurrent;}
571        Statement* operator->(){return mCurrent;}
572
573    private:
574        Statement * mCurrent;
575        friend class const_reverse_iterator;
576    };
577
578    class const_reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
579    public:
580        const_reverse_iterator(): mCurrent(nullptr) {}
581        const_reverse_iterator(const Statement* base): mCurrent(base) {}
[5647]582        const_reverse_iterator(const const_reverse_iterator & other): mCurrent(other.mCurrent) {}
[4280]583
[5647]584        const_reverse_iterator& operator=(const const_reverse_iterator & other) {
585            mCurrent = other.mCurrent;
586            return *this;
587        }
588
[4280]589        inline const_reverse_iterator& operator++() {
590            assert (mCurrent);
591            mCurrent = mCurrent->mPrev;
592            return *this;
593        }
594
595        const_reverse_iterator  operator++(int) {
596            const_reverse_iterator tmp(*this);
597            ++(*this);
598            return tmp;
599        }
600
601        bool operator==(const const_reverse_iterator & other) const {
602            return  mCurrent == other.mCurrent;
603        }
604        bool operator!=(const const_reverse_iterator & other) const {
605            return  mCurrent != other.mCurrent;
606        }
607
608        const Statement* operator*() {return mCurrent;}
609        const Statement* operator->(){return mCurrent;}
610
611    private:
612        const Statement * mCurrent;
[4358]613        friend struct iterator;
[4280]614    };
615
[4276]616public:
617
618    StatementList()
[4415]619    : mInsertionPoint(nullptr)
620    , mFirst(nullptr)
[4876]621    , mLast(nullptr) {
[4276]622
623    }
624
625    StatementList(StatementList && other)
[4876]626    : mInsertionPoint(nullptr)
627    , mFirst(other.mFirst)
628    , mLast(other.mLast) {
629        other.mInsertionPoint = nullptr;
[4276]630        other.mFirst = nullptr;
631        other.mLast = nullptr;
632    }
633
634    iterator begin() {
635        return iterator(mFirst);
636    }
637
638    iterator end() {
639        return iterator(nullptr);
640    }
641
[4280]642    reverse_iterator rbegin() {
643        return reverse_iterator(mLast);
644    }
645
646    reverse_iterator rend() {
647        return reverse_iterator(nullptr);
648    }
649
[4276]650    const_iterator begin() const {
651        return const_iterator(mFirst);
652    }
653
654    const_iterator end() const {
655        return const_iterator(nullptr);
656    }
657
[4280]658    const_reverse_iterator rbegin() const {
659        return const_reverse_iterator(mLast);
660    }
661
662    const_reverse_iterator rend() const {
663        return const_reverse_iterator(nullptr);
664    }
665
[4276]666    const_iterator cbegin() const {
667        return const_iterator(mFirst);
668    }
669
670    const_iterator cend() const {
671        return const_iterator(nullptr);
672    }
673
[4280]674    const_reverse_iterator crbegin() const {
675        return const_reverse_iterator(mLast);
676    }
677
678    const_reverse_iterator crend() const {
679        return const_reverse_iterator(nullptr);
680    }
681
[4416]682    inline Statement * front() const {
[4280]683        return mFirst;
684    }
685
[4416]686    inline Statement * back() const {
[4280]687        return mLast;
688    }
689
[4416]690    inline void setInsertPoint(Statement * const statement) {
[4775]691        assert (statement == nullptr || contains(statement));
[4416]692        mInsertionPoint = statement;
693    }
[4276]694
[4416]695    inline Statement * getInsertPoint() const {
[4415]696        return mInsertionPoint;
697    }
698
[5647]699    bool contains(const Statement * const statement) const;
[4775]700
[4876]701protected:
702
703    ~StatementList() = default;
704
[4276]705private:
[4415]706
707    Statement   * mInsertionPoint;
[4404]708    Statement   * mFirst;
[4415]709    Statement   * mLast;   
[4276]710};
711
[4876]712/** ------------------------------------------------------------------------------------------------------------- *
[4922]713 * @brief deleteOperand
[4880]714 ** ------------------------------------------------------------------------------------------------------------- */
[4885]715inline bool Variadic::deleteOperand(const PabloAST * const expr) {
[4880]716    for (unsigned i = 0; i != getNumOperands(); ++i) {
[4922]717        if (LLVM_UNLIKELY(getOperand(i) == expr)) {
[4880]718            removeOperand(i);
[4885]719            return true;
[4880]720        }
721    }
[4885]722    return false;
[4876]723}
[4244]724
[4880]725}
726
[4876]727#endif // PE_PabloAST_H
Note: See TracBrowser for help on using the repository browser.