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

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

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

File size: 19.6 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 <util/slab_allocator.h>
14#include <type_traits>
15#include <vector>
16namespace llvm { class Type; }
17namespace llvm { class raw_ostream; }
18namespace pablo { class PabloBlock; }
19namespace pablo { class String; }
20
21namespace pablo {
22
23class PabloAST {
24    friend class Statement;
25    friend class Variadic;
26    friend class StatementList;
27    friend class Branch;
28    friend class PabloBlock;
29    friend class SymbolGenerator;
30    friend class Count;
31    friend class Var;
32    friend class Operator;
33public:
34
35    using Allocator = SlabAllocator<PabloAST *>;
36    using Users = std::vector<PabloAST *, ProxyAllocator<PabloAST *>>;
37    using user_iterator = Users::iterator;
38    using const_user_iterator = Users::const_iterator;
39
40    static inline bool classof(const PabloAST *) {
41        return true;
42    }
43    static inline bool classof(const void *) {
44        return false;
45    }
46
47    enum class ClassTypeId : unsigned {
48        /** Expressions and Constants **/
49        // Constants
50        Zeroes
51        , Ones
52        // Arithmetic expressions
53        , Add
54        , Subtract
55        // Relational operators
56        , LessThan
57        , LessThanEquals
58        , Equals
59        , GreaterThanEquals
60        , GreaterThan
61        , NotEquals
62        // Internal types
63        , Var
64        , Integer
65        , String
66        , Block
67        , Kernel
68        , Extract
69        /** Statements **/
70        // Boolean operations
71        , And
72        , Or
73        , Xor
74        , Not       
75        , Sel
76        // Stream operations
77        , Advance
78        , IndexedAdvance
79        , ScanThru
80        , AdvanceThenScanThru
81        , ScanTo
82        , AdvanceThenScanTo
83        , Lookahead
84        , MatchStar
85        , InFile
86        , AtEOF
87        // Statistics operations
88        , Count
89        // Variable assignments
90        , Assign
91        // Scope branch statements
92        , If
93        , While
94        // Misc. operations
95        , Fill
96        , PackH
97        , PackL
98    };
99
100    inline ClassTypeId getClassTypeId() const noexcept {
101        return mClassTypeId;
102    }
103
104    inline llvm::Type * getType() const noexcept {
105        return mType;
106    }
107
108    inline void setType(llvm::Type * type) noexcept {
109        mType = type;
110    }
111
112    inline user_iterator user_begin() noexcept {
113        return mUsers.begin();
114    }
115
116    inline user_iterator user_end() noexcept {
117        return mUsers.end();
118    }
119
120    inline const_user_iterator user_begin() const noexcept {
121        return mUsers.cbegin();
122    }
123
124    inline const_user_iterator user_end() const noexcept {
125        return mUsers.cend();
126    }
127
128    inline Users & users() noexcept {
129        return mUsers;
130    }
131
132    inline const Users & users() const noexcept {
133        return mUsers;
134    }
135
136    void replaceAllUsesWith(PabloAST * const expr) noexcept;
137
138    inline Users::size_type getNumUses() const noexcept {
139        return mUsers.size();
140    }
141
142    void * operator new (std::size_t size, Allocator & allocator) noexcept {
143        return allocator.allocate<uint8_t>(size);
144    }
145
146//    void operator delete (void * ptr) {
147//        mAllocator.deallocate(static_cast<Allocator::value_type *>(ptr));
148//    }
149
150    void print(llvm::raw_ostream & O) const;
151
152protected:
153    inline PabloAST(const ClassTypeId id, llvm::Type * const type, Allocator & allocator)
154    : mClassTypeId(id)
155    , mType(type)
156    , mUsers(allocator) {
157
158    }
159    bool addUser(PabloAST * const user) noexcept;
160
161    bool removeUser(PabloAST * const user) noexcept;
162
163    virtual ~PabloAST() = default;
164
165private:
166    const ClassTypeId       mClassTypeId;
167    llvm::Type *            mType;
168    Users                   mUsers;
169};
170
171bool equals(const PabloAST * const expr1, const PabloAST * const expr2);
172
173bool dominates(const PabloAST * const expr1, const PabloAST * const expr2);
174
175inline bool strictly_dominates(const PabloAST * const expr1, const PabloAST * const expr2) {
176    return (expr1 != expr2) && dominates(expr1, expr2);
177}
178
179bool postdominates(const PabloAST * const expr1, const PabloAST * const expr2);
180
181inline bool strictly_postdominates(const PabloAST * const expr1, const PabloAST * const expr2) {
182    return (expr1 != expr2) && postdominates(expr1, expr2);
183}
184
185class StatementList;
186
187class String;
188
189class Statement : public PabloAST {
190    friend class StatementList;
191    friend class If;
192    friend class While;
193    friend class Simplifier;
194    friend class PabloBlock;
195public:
196    static inline bool classof(const PabloAST * e) {
197        return ((unsigned)e->getClassTypeId() >= (unsigned)PabloAST::ClassTypeId::And);
198    }
199    static inline bool classof(const Statement *) {
200        return true;
201    }
202    static inline bool classof(const void *) {
203        return false;
204    }
205
206    void replaceUsesOfWith(PabloAST * const from, PabloAST * const to);
207
208    const String & getName() const noexcept {
209        return *mName;
210    }
211
212    void setName(const String * const name) noexcept;
213
214    inline PabloAST * getOperand(const unsigned index) const noexcept {
215        assert (index < getNumOperands());
216        return mOperand[index];
217    }
218
219    void setOperand(const unsigned index, PabloAST * const value);
220
221    inline unsigned getNumOperands() const {
222        return mOperands;
223    }
224
225    void insertBefore(Statement * const statement);
226    void insertAfter(Statement * const statement);
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;
230
231    inline Statement * getNextNode() const {
232        return mNext;
233    }
234    inline Statement * getPrevNode() const {
235        return mPrev;
236    }
237    inline PabloBlock * getParent() const {
238        return mParent;
239    }
240    virtual ~Statement() = default;
241
242protected:
243
244    explicit Statement(const ClassTypeId id, llvm::Type * const type, std::initializer_list<PabloAST *> operands, const String * const name, Allocator & allocator)
245    : PabloAST(id, type, allocator)
246    , mOperands(operands.size())
247    , mOperand(allocator.allocate(mOperands))
248    , mNext(nullptr)
249    , mPrev(nullptr)
250    , mName(name)
251    , mParent(nullptr) {
252        unsigned i = 0;
253        for (PabloAST * const value : operands) {
254            assert (value);
255            mOperand[i] = value;
256            value->addUser(this);
257            ++i;
258        }
259    }
260
261    explicit Statement(const ClassTypeId id, llvm::Type * const type, const unsigned reserved, const String * const name, Allocator & allocator)
262    : PabloAST(id, type, allocator)
263    , mOperands(0)
264    , mOperand(allocator.allocate(reserved))
265    , mNext(nullptr)
266    , mPrev(nullptr)
267    , mName(name)
268    , mParent(nullptr) {
269        std::memset(mOperand, 0, reserved * sizeof(PabloAST *));
270    }
271
272    template<typename iterator>
273    explicit Statement(const ClassTypeId id, llvm::Type * const type, iterator begin, iterator end, const String * const name, Allocator & allocator)
274    : PabloAST(id, type, allocator)
275    , mOperands(std::distance(begin, end))
276    , mOperand(allocator.allocate(mOperands))
277    , mNext(nullptr)
278    , mPrev(nullptr)
279    , mName(name)
280    , mParent(nullptr) {
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    }
288
289protected:   
290    unsigned        mOperands;
291    PabloAST **     mOperand;
292    Statement *     mNext;
293    Statement *     mPrev;
294    const String *  mName;
295    PabloBlock *    mParent;
296};
297
298class CarryProducingStatement : public Statement {
299public:
300
301    static inline bool classof(const PabloAST * e) {
302        switch (e->getClassTypeId()) {
303            case PabloAST::ClassTypeId::Advance:
304            case PabloAST::ClassTypeId::IndexedAdvance:
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
329    unsigned getCarryWidth() const {
330        return mCarryWidth;
331    }
332
333    void setCarryWidth(const unsigned carryWidth) {
334        mCarryWidth = carryWidth;
335    }
336
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)
343    , mCarryGroup(0)
344    , mCarryWidth(0) {
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)
350    , mCarryGroup(0)
351    , mCarryWidth(0) {
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)
358    , mCarryGroup(0)
359    , mCarryWidth(0) {
360
361    }
362
363private:
364
365    unsigned mCarryGroup;
366    unsigned mCarryWidth;
367};
368
369
370class Variadic : public Statement {
371public:
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; }
397        inline void advance(const std::ptrdiff_t n) { mCurrent += n; }
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
409    void addOperand(PabloAST * const expr) noexcept;
410
411    PabloAST * removeOperand(const unsigned index) noexcept;
412
413    bool deleteOperand(const PabloAST * const expr) noexcept;
414
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
431    virtual ~Variadic() = default;
432
433protected:
434    explicit Variadic(const ClassTypeId id, llvm::Type * const type, std::initializer_list<PabloAST *> operands, const String * const name, Allocator & allocator)
435    : Statement(id, type, operands, name, allocator)
436    , mCapacity(operands.size())
437    , mAllocator(allocator) {
438
439    }
440    explicit Variadic(const ClassTypeId id, llvm::Type * const type, const unsigned reserved, const String * name, Allocator & allocator)
441    : Statement(id, type, reserved, name, allocator)
442    , mCapacity(reserved)
443    , mAllocator(allocator) {
444
445    }
446    template<typename iterator>
447    explicit Variadic(const ClassTypeId id, llvm::Type * const type, iterator begin, iterator end, const String * name, Allocator & allocator)
448    : Statement(id, type, begin, end, name, allocator)
449    , mCapacity(std::distance(begin, end))
450    , mAllocator(allocator) {
451
452    }
453private:
454    unsigned        mCapacity;
455    Allocator &     mAllocator;
456};
457
458class StatementList {
459    friend class Statement;
460    friend class PabloBlock;
461public:
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
468        iterator(const iterator & other): mCurrent(other.mCurrent) {}
469
470        iterator & operator=(const iterator & other) {
471            mCurrent = other.mCurrent;
472            return *this;
473        }
474
475        inline iterator& operator++() {
476            assert (mCurrent);
477            mCurrent = mCurrent->mNext;
478            return *this;
479        }
480
481        iterator operator++(int) {
482            iterator tmp(*this);
483            ++(*this);
484            return tmp;
485        }
486
487        bool operator==(const iterator & other) const {
488            return  mCurrent == other.mCurrent;
489        }
490
491        bool operator!=(const iterator & other) const {
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) {}
508        const_iterator& operator=(const const_iterator & other) {
509            mCurrent = other.mCurrent;
510            return *this;
511        }
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;
537        friend struct iterator;
538    };
539
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
548        reverse_iterator & operator=(const reverse_iterator & other) {
549            mCurrent = other.mCurrent;
550            return *this;
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) {}
585        const_reverse_iterator(const const_reverse_iterator & other): mCurrent(other.mCurrent) {}
586
587        const_reverse_iterator& operator=(const const_reverse_iterator & other) {
588            mCurrent = other.mCurrent;
589            return *this;
590        }
591
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;
616        friend struct iterator;
617    };
618
619public:
620
621    StatementList()
622    : mInsertionPoint(nullptr)
623    , mFirst(nullptr)
624    , mLast(nullptr) {
625
626    }
627
628    StatementList(StatementList && other)
629    : mInsertionPoint(nullptr)
630    , mFirst(other.mFirst)
631    , mLast(other.mLast) {
632        other.mInsertionPoint = nullptr;
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
645    reverse_iterator rbegin() {
646        return reverse_iterator(mLast);
647    }
648
649    reverse_iterator rend() {
650        return reverse_iterator(nullptr);
651    }
652
653    const_iterator begin() const {
654        return const_iterator(mFirst);
655    }
656
657    const_iterator end() const {
658        return const_iterator(nullptr);
659    }
660
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
669    const_iterator cbegin() const {
670        return const_iterator(mFirst);
671    }
672
673    const_iterator cend() const {
674        return const_iterator(nullptr);
675    }
676
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
685    inline Statement * front() const {
686        return mFirst;
687    }
688
689    inline Statement * back() const {
690        return mLast;
691    }
692
693    inline void setInsertPoint(Statement * const statement) {
694        assert (statement == nullptr || contains(statement));
695        mInsertionPoint = statement;
696    }
697
698    inline Statement * getInsertPoint() const {
699        return mInsertionPoint;
700    }
701
702    bool contains(const Statement * const statement) const;
703
704protected:
705
706    ~StatementList() = default;
707
708private:
709
710    Statement   * mInsertionPoint;
711    Statement   * mFirst;
712    Statement   * mLast;   
713};
714
715/** ------------------------------------------------------------------------------------------------------------- *
716 * @brief deleteOperand
717 ** ------------------------------------------------------------------------------------------------------------- */
718inline bool Variadic::deleteOperand(const PabloAST * const expr) noexcept {
719    for (unsigned i = 0; i != getNumOperands(); ++i) {
720        if (LLVM_UNLIKELY(getOperand(i) == expr)) {
721            removeOperand(i);
722            return true;
723        }
724    }
725    return false;
726}
727
728}
729
730#endif // PE_PabloAST_H
Note: See TracBrowser for help on using the repository browser.