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

Last change on this file since 5994 was 5836, checked in by nmedfort, 20 months ago

Added PabloBlock/Builder? createScope() methods + minor code changes.

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