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

Last change on this file was 6215, checked in by cameron, 5 months ago

pablo.terminateAt

File size: 15.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 StatementList;
26    friend class Branch;
27    friend class PabloBlock;
28    friend class SymbolGenerator;
29    friend class Count;
30    friend class Var;
31    friend class Operator;
32public:
33
34    using Allocator = SlabAllocator<PabloAST *>;
35    using Users = std::vector<PabloAST *, ProxyAllocator<PabloAST *>>;
36    using user_iterator = Users::iterator;
37    using const_user_iterator = Users::const_iterator;
38
39    static inline bool classof(const PabloAST *) {
40        return true;
41    }
42    static inline bool classof(const void *) {
43        return false;
44    }
45
46    // NOTE: when adding new statement types, update Statement::getName() to generate
47    // a default name for the class.
48    enum class ClassTypeId : unsigned {
49        /** Expressions and Constants **/
50        // Constants
51        Zeroes
52        , Ones
53        // Arithmetic expressions
54        , Add
55        , Subtract
56        // Relational operators
57        , LessThan
58        , LessThanEquals
59        , Equals
60        , GreaterThanEquals
61        , GreaterThan
62        , NotEquals
63        // Internal types
64        , Var
65        , Integer
66        , String
67        , Block
68        , Kernel
69        , Extract
70        /** Statements **/
71        // Boolean operations
72        , And
73        , Or
74        , Xor
75        , Not       
76        , Sel
77        // Stream operations
78        , Advance
79        , IndexedAdvance
80        , ScanThru
81        , AdvanceThenScanThru
82        , ScanTo
83        , AdvanceThenScanTo
84        , Lookahead
85        , MatchStar
86        , InFile
87        , AtEOF
88        , TerminateAt
89        // Statistics operations
90        , Count
91        // Variable assignments
92        , Assign
93        // Scope branch statements
94        , If
95        , While
96        // Misc. operations
97        , Repeat
98        , PackH
99        , PackL
100    };
101
102    inline ClassTypeId getClassTypeId() const noexcept {
103        return mClassTypeId;
104    }
105
106    inline llvm::Type * getType() const noexcept {
107        return mType;
108    }
109
110    inline void setType(llvm::Type * type) noexcept {
111        mType = type;
112    }
113
114    inline user_iterator user_begin() noexcept {
115        return mUsers.begin();
116    }
117
118    inline user_iterator user_end() noexcept {
119        return mUsers.end();
120    }
121
122    inline const_user_iterator user_begin() const noexcept {
123        return mUsers.cbegin();
124    }
125
126    inline const_user_iterator user_end() const noexcept {
127        return mUsers.cend();
128    }
129
130    inline Users & users() noexcept {
131        return mUsers;
132    }
133
134    inline const Users & users() const noexcept {
135        return mUsers;
136    }
137
138    void replaceAllUsesWith(PabloAST * const expr) noexcept;
139
140    inline Users::size_type getNumUses() const noexcept {
141        return mUsers.size();
142    }
143
144    void * operator new (std::size_t size, Allocator & allocator) noexcept {
145        return allocator.allocate<uint8_t>(size);
146    }
147
148//    void operator delete (void * ptr) {
149//        mAllocator.deallocate(static_cast<Allocator::value_type *>(ptr));
150//    }
151
152    void print(llvm::raw_ostream & O) const;
153
154protected:
155    inline PabloAST(const ClassTypeId id, llvm::Type * const type, Allocator & allocator)
156    : mClassTypeId(id)
157    , mType(type)
158    , mUsers(allocator) {
159
160    }
161    bool addUser(PabloAST * const user) noexcept;
162
163    bool removeUser(PabloAST * const user) noexcept;
164
165    virtual ~PabloAST() = default;
166
167private:
168    const ClassTypeId       mClassTypeId;
169    llvm::Type *            mType;
170    Users                   mUsers;
171};
172
173bool equals(const PabloAST * const expr1, const PabloAST * const expr2) noexcept;
174
175bool dominates(const PabloAST * const expr1, const PabloAST * const expr2) noexcept;
176
177inline bool strictly_dominates(const PabloAST * const expr1, const PabloAST * const expr2) noexcept {
178    return (expr1 != expr2) && dominates(expr1, expr2);
179}
180
181bool postdominates(const PabloAST * const expr1, const PabloAST * const expr2) noexcept;
182
183inline bool strictly_postdominates(const PabloAST * const expr1, const PabloAST * const expr2) noexcept {
184    return (expr1 != expr2) && postdominates(expr1, expr2);
185}
186
187class String;
188
189class NamedPabloAST : public PabloAST {
190public:
191    virtual const String & getName() const = 0;
192    void setName(const String * const name);
193protected:
194    explicit NamedPabloAST(const ClassTypeId id, llvm::Type * const type, const String * const name, Allocator & allocator)
195    : PabloAST(id, type, allocator)
196    , mName(name) {
197
198    }
199protected:
200    mutable const String * mName;
201};
202
203class StatementList;
204
205class Statement : public NamedPabloAST {
206    friend class StatementList;
207    friend class If;
208    friend class While;
209    friend class Simplifier;
210    friend class PabloBlock;
211public:
212    static inline bool classof(const PabloAST * e) {
213        return ((unsigned)e->getClassTypeId() >= (unsigned)PabloAST::ClassTypeId::And);
214    }
215    static inline bool classof(const Statement *) {
216        return true;
217    }
218    static inline bool classof(const void *) {
219        return false;
220    }
221
222    void replaceUsesOfWith(PabloAST * const from, PabloAST * const to);
223
224    inline PabloAST * getOperand(const unsigned index) const noexcept {
225        assert (index < getNumOperands());
226        return mOperand[index];
227    }
228
229    void setOperand(const unsigned index, PabloAST * const value);
230
231    inline unsigned getNumOperands() const {
232        return mOperands;
233    }
234
235    void insertBefore(Statement * const statement);
236    void insertAfter(Statement * const statement);
237    Statement * removeFromParent() noexcept;
238    Statement * eraseFromParent(const bool recursively = false) noexcept;
239    Statement * replaceWith(PabloAST * const expr, const bool rename = true, const bool recursively = false) noexcept;
240
241    inline Statement * getNextNode() const {
242        return mNext;
243    }
244    inline Statement * getPrevNode() const {
245        return mPrev;
246    }
247    inline PabloBlock * getParent() const {
248        return mParent;
249    }
250
251    const String & getName() const final;
252
253    virtual ~Statement() = default;
254
255protected:
256
257    explicit Statement(const ClassTypeId id, llvm::Type * const type, std::initializer_list<PabloAST *> operands, const String * const name, Allocator & allocator)
258    : NamedPabloAST(id, type, name, allocator)
259    , mOperands(operands.size())
260    , mOperand(allocator.allocate(mOperands))
261    , mNext(nullptr)
262    , mPrev(nullptr)
263    , mParent(nullptr) {
264        unsigned i = 0;
265        for (PabloAST * const value : operands) {
266            assert (value);
267            mOperand[i] = value;
268            value->addUser(this);
269            ++i;
270        }
271    }
272
273protected:   
274    const unsigned          mOperands;
275    PabloAST ** const       mOperand;
276    Statement *             mNext;
277    Statement *             mPrev;
278    PabloBlock *            mParent;
279};
280
281class CarryProducingStatement : public Statement {
282public:
283
284    static inline bool classof(const PabloAST * e) {
285        switch (e->getClassTypeId()) {
286            case PabloAST::ClassTypeId::Advance:
287            case PabloAST::ClassTypeId::IndexedAdvance:
288            case PabloAST::ClassTypeId::ScanThru:
289            case PabloAST::ClassTypeId::AdvanceThenScanThru:
290            case PabloAST::ClassTypeId::ScanTo:
291            case PabloAST::ClassTypeId::AdvanceThenScanTo:
292            case PabloAST::ClassTypeId::MatchStar:
293                return true;
294            default: return false;
295        }
296    }
297    static inline bool classof(const CarryProducingStatement *) {
298        return true;
299    }
300    static inline bool classof(const void *) {
301        return false;
302    }
303
304    unsigned getCarryGroup() const {
305        return mCarryGroup;
306    }
307
308    void setCarryGroup(const unsigned carryGroup) {
309        mCarryGroup = carryGroup;
310    }
311
312    unsigned getCarryWidth() const {
313        return mCarryWidth;
314    }
315
316    void setCarryWidth(const unsigned carryWidth) {
317        mCarryWidth = carryWidth;
318    }
319
320    virtual ~CarryProducingStatement() = default;
321
322protected:
323
324    explicit CarryProducingStatement(const ClassTypeId id, llvm::Type * const type, std::initializer_list<PabloAST *> operands, const String * const name, Allocator & allocator)
325    : Statement(id, type, operands, name, allocator)
326    , mCarryGroup(0)
327    , mCarryWidth(0) {
328
329    }
330
331private:
332
333    unsigned mCarryGroup;
334    unsigned mCarryWidth;
335};
336
337class StatementList {
338    friend class Statement;
339    friend class PabloBlock;
340public:
341    class iterator: public std::iterator<std::forward_iterator_tag, Statement> {
342    public:
343        iterator(): mCurrent(nullptr) {}
344
345        iterator(Statement* base): mCurrent(base) {}
346
347        iterator(const iterator & other): mCurrent(other.mCurrent) {}
348
349        iterator & operator=(const iterator & other) {
350            mCurrent = other.mCurrent;
351            return *this;
352        }
353
354        inline iterator& operator++() {
355            assert (mCurrent);
356            mCurrent = mCurrent->mNext;
357            return *this;
358        }
359
360        iterator operator++(int) {
361            iterator tmp(*this);
362            ++(*this);
363            return tmp;
364        }
365
366        bool operator==(const iterator & other) const {
367            return  mCurrent == other.mCurrent;
368        }
369
370        bool operator!=(const iterator & other) const {
371            return  mCurrent != other.mCurrent;
372        }
373
374        Statement* operator*() {return mCurrent;}
375        Statement* operator->(){return mCurrent;}
376
377    private:
378        Statement * mCurrent;
379        friend class const_iterator;
380    };
381
382    class const_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
383    public:
384        const_iterator(): mCurrent(nullptr) {}
385        const_iterator(const Statement* base): mCurrent(base) {}
386        const_iterator(const const_iterator& other): mCurrent(other.mCurrent) {}
387        const_iterator& operator=(const const_iterator & other) {
388            mCurrent = other.mCurrent;
389            return *this;
390        }
391
392        inline const_iterator& operator++() {
393            assert (mCurrent);
394            mCurrent = mCurrent->mNext;
395            return *this;
396        }
397
398        const_iterator  operator++(int) {
399            const_iterator tmp(*this);
400            ++(*this);
401            return tmp;
402        }
403
404        bool operator==(const const_iterator & other) const {
405            return  mCurrent == other.mCurrent;
406        }
407        bool operator!=(const const_iterator & other) const {
408            return  mCurrent != other.mCurrent;
409        }
410
411        const Statement* operator*() {return mCurrent;}
412        const Statement* operator->(){return mCurrent;}
413
414    private:
415        const Statement * mCurrent;
416        friend struct iterator;
417    };
418
419    class reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
420    public:
421        reverse_iterator(): mCurrent(nullptr) {}
422
423        reverse_iterator(Statement* base): mCurrent(base) {}
424
425        reverse_iterator(const reverse_iterator& other): mCurrent(other.mCurrent) {}
426
427        reverse_iterator & operator=(const reverse_iterator & other) {
428            mCurrent = other.mCurrent;
429            return *this;
430        }
431
432        inline reverse_iterator& operator++() {
433            assert (mCurrent);
434            mCurrent = mCurrent->mPrev;
435            return *this;
436        }
437
438        reverse_iterator operator++(int) {
439            reverse_iterator tmp(*this);
440            ++(*this);
441            return tmp;
442        }
443
444        bool operator==(const reverse_iterator& other) const {
445            return  mCurrent == other.mCurrent;
446        }
447
448        bool operator!=(const reverse_iterator& other) const {
449            return  mCurrent != other.mCurrent;
450        }
451
452        Statement* operator*() {return mCurrent;}
453        Statement* operator->(){return mCurrent;}
454
455    private:
456        Statement * mCurrent;
457        friend class const_reverse_iterator;
458    };
459
460    class const_reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
461    public:
462        const_reverse_iterator(): mCurrent(nullptr) {}
463        const_reverse_iterator(const Statement* base): mCurrent(base) {}
464        const_reverse_iterator(const const_reverse_iterator & other): mCurrent(other.mCurrent) {}
465
466        const_reverse_iterator& operator=(const const_reverse_iterator & other) {
467            mCurrent = other.mCurrent;
468            return *this;
469        }
470
471        inline const_reverse_iterator& operator++() {
472            assert (mCurrent);
473            mCurrent = mCurrent->mPrev;
474            return *this;
475        }
476
477        const_reverse_iterator  operator++(int) {
478            const_reverse_iterator tmp(*this);
479            ++(*this);
480            return tmp;
481        }
482
483        bool operator==(const const_reverse_iterator & other) const {
484            return  mCurrent == other.mCurrent;
485        }
486        bool operator!=(const const_reverse_iterator & other) const {
487            return  mCurrent != other.mCurrent;
488        }
489
490        const Statement* operator*() {return mCurrent;}
491        const Statement* operator->(){return mCurrent;}
492
493    private:
494        const Statement * mCurrent;
495        friend struct iterator;
496    };
497
498public:
499
500    StatementList()
501    : mInsertionPoint(nullptr)
502    , mFirst(nullptr)
503    , mLast(nullptr) {
504
505    }
506
507    StatementList(StatementList && other)
508    : mInsertionPoint(nullptr)
509    , mFirst(other.mFirst)
510    , mLast(other.mLast) {
511        other.mInsertionPoint = nullptr;
512        other.mFirst = nullptr;
513        other.mLast = nullptr;
514    }
515
516    iterator begin() {
517        return iterator(mFirst);
518    }
519
520    iterator end() {
521        return iterator(nullptr);
522    }
523
524    reverse_iterator rbegin() {
525        return reverse_iterator(mLast);
526    }
527
528    reverse_iterator rend() {
529        return reverse_iterator(nullptr);
530    }
531
532    const_iterator begin() const {
533        return const_iterator(mFirst);
534    }
535
536    const_iterator end() const {
537        return const_iterator(nullptr);
538    }
539
540    const_reverse_iterator rbegin() const {
541        return const_reverse_iterator(mLast);
542    }
543
544    const_reverse_iterator rend() const {
545        return const_reverse_iterator(nullptr);
546    }
547
548    const_iterator cbegin() const {
549        return const_iterator(mFirst);
550    }
551
552    const_iterator cend() const {
553        return const_iterator(nullptr);
554    }
555
556    const_reverse_iterator crbegin() const {
557        return const_reverse_iterator(mLast);
558    }
559
560    const_reverse_iterator crend() const {
561        return const_reverse_iterator(nullptr);
562    }
563
564    inline Statement * front() const {
565        return mFirst;
566    }
567
568    inline Statement * back() const {
569        return mLast;
570    }
571
572    inline void setInsertPoint(Statement * const statement) {
573        assert (statement == nullptr || contains(statement));
574        mInsertionPoint = statement;
575    }
576
577    inline Statement * getInsertPoint() const {
578        return mInsertionPoint;
579    }
580
581    bool contains(const Statement * const statement) const noexcept;
582
583protected:
584
585    ~StatementList() = default;
586
587private:
588
589    Statement   * mInsertionPoint;
590    Statement   * mFirst;
591    Statement   * mLast;   
592};
593
594}
595
596#endif // PE_PabloAST_H
Note: See TracBrowser for help on using the repository browser.