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

Last change on this file since 5510 was 5510, checked in by nmedfort, 2 years ago

Back up check-in. Should have no effect on current programs.

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