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

Last change on this file since 5828 was 5828, checked in by nmedfort, 22 months ago

Pablo support for byte comparisions; LineFeed? kernel processes byte streams directly. Some clean up of PabloBuilder? functionality.

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