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

Last change on this file since 5751 was 5705, checked in by cameron, 2 years ago

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

File size: 19.4 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 expressions
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        , Phi
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        , Extract     
92        // Scope blocks
93        , If
94        , While
95    };
96
97    inline ClassTypeId getClassTypeId() const noexcept {
98        return mClassTypeId;
99    }
100
101    inline llvm::Type * getType() const noexcept {
102        return mType;
103    }
104
105    inline void setType(llvm::Type * type) noexcept {
106        mType = type;
107    }
108
109    inline user_iterator user_begin() {
110        return mUsers.begin();
111    }
112
113    inline user_iterator user_end() {
114        return mUsers.end();
115    }
116
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
125    inline Users & users() {
126        return mUsers;
127    }
128
129    inline const Users & users() const {
130        return mUsers;
131    }
132
133    void replaceAllUsesWith(PabloAST * const expr);
134
135    inline Users::size_type getNumUses() const {
136        return mUsers.size();
137    }
138
139    void * operator new (std::size_t size, Allocator & allocator) noexcept {
140        return allocator.allocate<uint8_t>(size);
141    }
142
143//    void operator delete (void * ptr) {
144//        mAllocator.deallocate(static_cast<Allocator::value_type *>(ptr));
145//    }
146
147    void print(llvm::raw_ostream & O) const;
148
149protected:
150    inline PabloAST(const ClassTypeId id, llvm::Type * const type, Allocator & allocator)
151    : mClassTypeId(id)
152    , mType(type)
153    , mUsers(allocator) {
154
155    }
156    bool addUser(PabloAST * const user);
157
158    bool removeUser(PabloAST * const user);
159
160    virtual ~PabloAST() = default;
161
162private:
163    const ClassTypeId       mClassTypeId;
164    llvm::Type *            mType;
165    Users                   mUsers;
166};
167
168bool equals(const PabloAST * const expr1, const PabloAST * const expr2);
169
170bool dominates(const PabloAST * const expr1, const PabloAST * const expr2);
171
172inline bool strictly_dominates(const PabloAST * const expr1, const PabloAST * const expr2) {
173    return (expr1 != expr2) && dominates(expr1, expr2);
174}
175
176bool postdominates(const PabloAST * const expr1, const PabloAST * const expr2);
177
178inline bool strictly_postdominates(const PabloAST * const expr1, const PabloAST * const expr2) {
179    return (expr1 != expr2) && postdominates(expr1, expr2);
180}
181
182class StatementList;
183
184class String;
185
186class Statement : public PabloAST {
187    friend class StatementList;
188    friend class If;
189    friend class While;
190    friend class Simplifier;
191    friend class PabloBlock;
192public:
193    static inline bool classof(const PabloAST * e) {
194        return ((unsigned)e->getClassTypeId() >= (unsigned)PabloAST::ClassTypeId::And);
195    }
196    static inline bool classof(const Statement *) {
197        return true;
198    }
199    static inline bool classof(const void *) {
200        return false;
201    }
202
203    void replaceUsesOfWith(PabloAST * const from, PabloAST * const to);
204
205    const String & getName() const noexcept {
206        return *mName;
207    }
208
209    void setName(const String * const name) noexcept;
210
211    inline PabloAST * getOperand(const unsigned index) const {
212        assert (index < getNumOperands());
213        return mOperand[index];
214    }
215
216    void setOperand(const unsigned index, PabloAST * const value);
217
218    inline unsigned getNumOperands() const {
219        return mOperands;
220    }
221
222    void insertBefore(Statement * const statement);
223    void insertAfter(Statement * const statement);
224    Statement * removeFromParent();
225    Statement * eraseFromParent(const bool recursively = false);
226    Statement * replaceWith(PabloAST * const expr, const bool rename = true, const bool recursively = false);
227
228    inline Statement * getNextNode() const {
229        return mNext;
230    }
231    inline Statement * getPrevNode() const {
232        return mPrev;
233    }
234    inline PabloBlock * getParent() const {
235        return mParent;
236    }
237    virtual ~Statement() = default;
238
239protected:
240
241    explicit Statement(const ClassTypeId id, llvm::Type * const type, std::initializer_list<PabloAST *> operands, const String * const name, Allocator & allocator)
242    : PabloAST(id, type, allocator)
243    , mOperands(operands.size())
244    , mOperand(allocator.allocate(mOperands))
245    , mNext(nullptr)
246    , mPrev(nullptr)
247    , mName(name)
248    , mParent(nullptr) {
249        unsigned i = 0;
250        for (PabloAST * const value : operands) {
251            assert (value);
252            mOperand[i] = value;
253            value->addUser(this);
254            ++i;
255        }
256    }
257
258    explicit Statement(const ClassTypeId id, llvm::Type * const type, const unsigned reserved, const String * const name, Allocator & allocator)
259    : PabloAST(id, type, allocator)
260    , mOperands(0)
261    , mOperand(allocator.allocate(reserved))
262    , mNext(nullptr)
263    , mPrev(nullptr)
264    , mName(name)
265    , mParent(nullptr) {
266        std::memset(mOperand, 0, reserved * sizeof(PabloAST *));
267    }
268
269    template<typename iterator>
270    explicit Statement(const ClassTypeId id, llvm::Type * const type, iterator begin, iterator end, const String * const name, Allocator & allocator)
271    : PabloAST(id, type, allocator)
272    , mOperands(std::distance(begin, end))
273    , mOperand(allocator.allocate(mOperands))
274    , mNext(nullptr)
275    , mPrev(nullptr)
276    , mName(name)
277    , mParent(nullptr) {
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    }
285
286protected:   
287    unsigned        mOperands;
288    PabloAST **     mOperand;
289    Statement *     mNext;
290    Statement *     mPrev;
291    const String *  mName;
292    PabloBlock *    mParent;
293};
294
295class CarryProducingStatement : public Statement {
296public:
297
298    static inline bool classof(const PabloAST * e) {
299        switch (e->getClassTypeId()) {
300            case PabloAST::ClassTypeId::Advance:
301            case PabloAST::ClassTypeId::IndexedAdvance:
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
326    unsigned getCarryWidth() const {
327        return mCarryWidth;
328    }
329
330    void setCarryWidth(const unsigned carryWidth) {
331        mCarryWidth = carryWidth;
332    }
333
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)
340    , mCarryGroup(0)
341    , mCarryWidth(0) {
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)
347    , mCarryGroup(0)
348    , mCarryWidth(0) {
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)
355    , mCarryGroup(0)
356    , mCarryWidth(0) {
357
358    }
359
360private:
361
362    unsigned mCarryGroup;
363    unsigned mCarryWidth;
364};
365
366
367class Variadic : public Statement {
368public:
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; }
394        inline void advance(const std::ptrdiff_t n) { mCurrent += n; }
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
410    bool deleteOperand(const PabloAST * const expr);
411
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
428    virtual ~Variadic() = default;
429
430protected:
431    explicit Variadic(const ClassTypeId id, llvm::Type * const type, std::initializer_list<PabloAST *> operands, const String * const name, Allocator & allocator)
432    : Statement(id, type, operands, name, allocator)
433    , mCapacity(operands.size())
434    , mAllocator(allocator) {
435
436    }
437    explicit Variadic(const ClassTypeId id, llvm::Type * const type, const unsigned reserved, const String * name, Allocator & allocator)
438    : Statement(id, type, reserved, name, allocator)
439    , mCapacity(reserved)
440    , mAllocator(allocator) {
441
442    }
443    template<typename iterator>
444    explicit Variadic(const ClassTypeId id, llvm::Type * const type, iterator begin, iterator end, const String * name, Allocator & allocator)
445    : Statement(id, type, begin, end, name, allocator)
446    , mCapacity(std::distance(begin, end))
447    , mAllocator(allocator) {
448
449    }
450private:
451    unsigned        mCapacity;
452    Allocator &     mAllocator;
453};
454
455class StatementList {
456    friend class Statement;
457    friend class PabloBlock;
458public:
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
465        iterator(const iterator & other): mCurrent(other.mCurrent) {}
466
467        iterator & operator=(const iterator & other) {
468            mCurrent = other.mCurrent;
469            return *this;
470        }
471
472        inline iterator& operator++() {
473            assert (mCurrent);
474            mCurrent = mCurrent->mNext;
475            return *this;
476        }
477
478        iterator operator++(int) {
479            iterator tmp(*this);
480            ++(*this);
481            return tmp;
482        }
483
484        bool operator==(const iterator & other) const {
485            return  mCurrent == other.mCurrent;
486        }
487
488        bool operator!=(const iterator & other) const {
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) {}
505        const_iterator& operator=(const const_iterator & other) {
506            mCurrent = other.mCurrent;
507            return *this;
508        }
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;
534        friend struct iterator;
535    };
536
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
545        reverse_iterator & operator=(const reverse_iterator & other) {
546            mCurrent = other.mCurrent;
547            return *this;
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) {}
582        const_reverse_iterator(const const_reverse_iterator & other): mCurrent(other.mCurrent) {}
583
584        const_reverse_iterator& operator=(const const_reverse_iterator & other) {
585            mCurrent = other.mCurrent;
586            return *this;
587        }
588
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;
613        friend struct iterator;
614    };
615
616public:
617
618    StatementList()
619    : mInsertionPoint(nullptr)
620    , mFirst(nullptr)
621    , mLast(nullptr) {
622
623    }
624
625    StatementList(StatementList && other)
626    : mInsertionPoint(nullptr)
627    , mFirst(other.mFirst)
628    , mLast(other.mLast) {
629        other.mInsertionPoint = nullptr;
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
642    reverse_iterator rbegin() {
643        return reverse_iterator(mLast);
644    }
645
646    reverse_iterator rend() {
647        return reverse_iterator(nullptr);
648    }
649
650    const_iterator begin() const {
651        return const_iterator(mFirst);
652    }
653
654    const_iterator end() const {
655        return const_iterator(nullptr);
656    }
657
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
666    const_iterator cbegin() const {
667        return const_iterator(mFirst);
668    }
669
670    const_iterator cend() const {
671        return const_iterator(nullptr);
672    }
673
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
682    inline Statement * front() const {
683        return mFirst;
684    }
685
686    inline Statement * back() const {
687        return mLast;
688    }
689
690    inline void setInsertPoint(Statement * const statement) {
691        assert (statement == nullptr || contains(statement));
692        mInsertionPoint = statement;
693    }
694
695    inline Statement * getInsertPoint() const {
696        return mInsertionPoint;
697    }
698
699    bool contains(const Statement * const statement) const;
700
701protected:
702
703    ~StatementList() = default;
704
705private:
706
707    Statement   * mInsertionPoint;
708    Statement   * mFirst;
709    Statement   * mLast;   
710};
711
712/** ------------------------------------------------------------------------------------------------------------- *
713 * @brief deleteOperand
714 ** ------------------------------------------------------------------------------------------------------------- */
715inline bool Variadic::deleteOperand(const PabloAST * const expr) {
716    for (unsigned i = 0; i != getNumOperands(); ++i) {
717        if (LLVM_UNLIKELY(getOperand(i) == expr)) {
718            removeOperand(i);
719            return true;
720        }
721    }
722    return false;
723}
724
725}
726
727#endif // PE_PabloAST_H
Note: See TracBrowser for help on using the repository browser.