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

Last change on this file since 5834 was 5834, checked in by nmedfort, 17 months ago

Removed Variadic functionality; allowed for deferred creation of statement names

File size: 15.1 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);
173
174bool dominates(const PabloAST * const expr1, const PabloAST * const expr2);
175
176inline bool strictly_dominates(const PabloAST * const expr1, const PabloAST * const expr2) {
177    return (expr1 != expr2) && dominates(expr1, expr2);
178}
179
180bool postdominates(const PabloAST * const expr1, const PabloAST * const expr2);
181
182inline bool strictly_postdominates(const PabloAST * const expr1, const PabloAST * const expr2) {
183    return (expr1 != expr2) && postdominates(expr1, expr2);
184}
185
186class StatementList;
187
188class String;
189
190class Statement : public PabloAST {
191    friend class StatementList;
192    friend class If;
193    friend class While;
194    friend class Simplifier;
195    friend class PabloBlock;
196public:
197    static inline bool classof(const PabloAST * e) {
198        return ((unsigned)e->getClassTypeId() >= (unsigned)PabloAST::ClassTypeId::And);
199    }
200    static inline bool classof(const Statement *) {
201        return true;
202    }
203    static inline bool classof(const void *) {
204        return false;
205    }
206
207    void replaceUsesOfWith(PabloAST * const from, PabloAST * const to);
208
209    // NOTE: getName() can generate a default name if one is does not exist for it
210    const String & getName() const;
211
212    inline PabloAST * getOperand(const unsigned index) const noexcept {
213        assert (index < getNumOperands());
214        return mOperand[index];
215    }
216
217    void setOperand(const unsigned index, PabloAST * const value);
218
219    inline unsigned getNumOperands() const {
220        return mOperands;
221    }
222
223    void insertBefore(Statement * const statement);
224    void insertAfter(Statement * const statement);
225    Statement * removeFromParent() noexcept;
226    Statement * eraseFromParent(const bool recursively = false) noexcept;
227    Statement * replaceWith(PabloAST * const expr, const bool rename = true, const bool recursively = false) noexcept;
228
229    inline Statement * getNextNode() const {
230        return mNext;
231    }
232    inline Statement * getPrevNode() const {
233        return mPrev;
234    }
235    inline PabloBlock * getParent() const {
236        return mParent;
237    }
238
239    virtual ~Statement() = default;
240
241    void setName(const String * const name);
242
243protected:
244
245    explicit Statement(const ClassTypeId id, llvm::Type * const type, std::initializer_list<PabloAST *> operands, const String * const name, Allocator & allocator)
246    : PabloAST(id, type, allocator)
247    , mOperands(operands.size())
248    , mOperand(allocator.allocate(mOperands))
249    , mNext(nullptr)
250    , mPrev(nullptr)
251    , mName(name)
252    , mParent(nullptr) {
253        unsigned i = 0;
254        for (PabloAST * const value : operands) {
255            assert (value);
256            mOperand[i] = value;
257            value->addUser(this);
258            ++i;
259        }
260    }
261
262protected:   
263    unsigned                mOperands;
264    PabloAST **             mOperand;
265    Statement *             mNext;
266    Statement *             mPrev;
267    mutable const String *  mName;
268    PabloBlock *            mParent;
269};
270
271class CarryProducingStatement : public Statement {
272public:
273
274    static inline bool classof(const PabloAST * e) {
275        switch (e->getClassTypeId()) {
276            case PabloAST::ClassTypeId::Advance:
277            case PabloAST::ClassTypeId::IndexedAdvance:
278            case PabloAST::ClassTypeId::ScanThru:
279            case PabloAST::ClassTypeId::AdvanceThenScanThru:
280            case PabloAST::ClassTypeId::ScanTo:
281            case PabloAST::ClassTypeId::AdvanceThenScanTo:
282            case PabloAST::ClassTypeId::MatchStar:
283                return true;
284            default: return false;
285        }
286    }
287    static inline bool classof(const CarryProducingStatement *) {
288        return true;
289    }
290    static inline bool classof(const void *) {
291        return false;
292    }
293
294    unsigned getCarryGroup() const {
295        return mCarryGroup;
296    }
297
298    void setCarryGroup(const unsigned carryGroup) {
299        mCarryGroup = carryGroup;
300    }
301
302    unsigned getCarryWidth() const {
303        return mCarryWidth;
304    }
305
306    void setCarryWidth(const unsigned carryWidth) {
307        mCarryWidth = carryWidth;
308    }
309
310    virtual ~CarryProducingStatement() = default;
311
312protected:
313
314    explicit CarryProducingStatement(const ClassTypeId id, llvm::Type * const type, std::initializer_list<PabloAST *> operands, const String * const name, Allocator & allocator)
315    : Statement(id, type, operands, name, allocator)
316    , mCarryGroup(0)
317    , mCarryWidth(0) {
318
319    }
320
321private:
322
323    unsigned mCarryGroup;
324    unsigned mCarryWidth;
325};
326
327class StatementList {
328    friend class Statement;
329    friend class PabloBlock;
330public:
331    class iterator: public std::iterator<std::forward_iterator_tag, Statement> {
332    public:
333        iterator(): mCurrent(nullptr) {}
334
335        iterator(Statement* base): mCurrent(base) {}
336
337        iterator(const iterator & other): mCurrent(other.mCurrent) {}
338
339        iterator & operator=(const iterator & other) {
340            mCurrent = other.mCurrent;
341            return *this;
342        }
343
344        inline iterator& operator++() {
345            assert (mCurrent);
346            mCurrent = mCurrent->mNext;
347            return *this;
348        }
349
350        iterator operator++(int) {
351            iterator tmp(*this);
352            ++(*this);
353            return tmp;
354        }
355
356        bool operator==(const iterator & other) const {
357            return  mCurrent == other.mCurrent;
358        }
359
360        bool operator!=(const iterator & other) const {
361            return  mCurrent != other.mCurrent;
362        }
363
364        Statement* operator*() {return mCurrent;}
365        Statement* operator->(){return mCurrent;}
366
367    private:
368        Statement * mCurrent;
369        friend class const_iterator;
370    };
371
372    class const_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
373    public:
374        const_iterator(): mCurrent(nullptr) {}
375        const_iterator(const Statement* base): mCurrent(base) {}
376        const_iterator(const const_iterator& other): mCurrent(other.mCurrent) {}
377        const_iterator& operator=(const const_iterator & other) {
378            mCurrent = other.mCurrent;
379            return *this;
380        }
381
382        inline const_iterator& operator++() {
383            assert (mCurrent);
384            mCurrent = mCurrent->mNext;
385            return *this;
386        }
387
388        const_iterator  operator++(int) {
389            const_iterator tmp(*this);
390            ++(*this);
391            return tmp;
392        }
393
394        bool operator==(const const_iterator & other) const {
395            return  mCurrent == other.mCurrent;
396        }
397        bool operator!=(const const_iterator & other) const {
398            return  mCurrent != other.mCurrent;
399        }
400
401        const Statement* operator*() {return mCurrent;}
402        const Statement* operator->(){return mCurrent;}
403
404    private:
405        const Statement * mCurrent;
406        friend struct iterator;
407    };
408
409    class reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
410    public:
411        reverse_iterator(): mCurrent(nullptr) {}
412
413        reverse_iterator(Statement* base): mCurrent(base) {}
414
415        reverse_iterator(const reverse_iterator& other): mCurrent(other.mCurrent) {}
416
417        reverse_iterator & operator=(const reverse_iterator & other) {
418            mCurrent = other.mCurrent;
419            return *this;
420        }
421
422        inline reverse_iterator& operator++() {
423            assert (mCurrent);
424            mCurrent = mCurrent->mPrev;
425            return *this;
426        }
427
428        reverse_iterator operator++(int) {
429            reverse_iterator tmp(*this);
430            ++(*this);
431            return tmp;
432        }
433
434        bool operator==(const reverse_iterator& other) const {
435            return  mCurrent == other.mCurrent;
436        }
437
438        bool operator!=(const reverse_iterator& other) const {
439            return  mCurrent != other.mCurrent;
440        }
441
442        Statement* operator*() {return mCurrent;}
443        Statement* operator->(){return mCurrent;}
444
445    private:
446        Statement * mCurrent;
447        friend class const_reverse_iterator;
448    };
449
450    class const_reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
451    public:
452        const_reverse_iterator(): mCurrent(nullptr) {}
453        const_reverse_iterator(const Statement* base): mCurrent(base) {}
454        const_reverse_iterator(const const_reverse_iterator & other): mCurrent(other.mCurrent) {}
455
456        const_reverse_iterator& operator=(const const_reverse_iterator & other) {
457            mCurrent = other.mCurrent;
458            return *this;
459        }
460
461        inline const_reverse_iterator& operator++() {
462            assert (mCurrent);
463            mCurrent = mCurrent->mPrev;
464            return *this;
465        }
466
467        const_reverse_iterator  operator++(int) {
468            const_reverse_iterator tmp(*this);
469            ++(*this);
470            return tmp;
471        }
472
473        bool operator==(const const_reverse_iterator & other) const {
474            return  mCurrent == other.mCurrent;
475        }
476        bool operator!=(const const_reverse_iterator & other) const {
477            return  mCurrent != other.mCurrent;
478        }
479
480        const Statement* operator*() {return mCurrent;}
481        const Statement* operator->(){return mCurrent;}
482
483    private:
484        const Statement * mCurrent;
485        friend struct iterator;
486    };
487
488public:
489
490    StatementList()
491    : mInsertionPoint(nullptr)
492    , mFirst(nullptr)
493    , mLast(nullptr) {
494
495    }
496
497    StatementList(StatementList && other)
498    : mInsertionPoint(nullptr)
499    , mFirst(other.mFirst)
500    , mLast(other.mLast) {
501        other.mInsertionPoint = nullptr;
502        other.mFirst = nullptr;
503        other.mLast = nullptr;
504    }
505
506    iterator begin() {
507        return iterator(mFirst);
508    }
509
510    iterator end() {
511        return iterator(nullptr);
512    }
513
514    reverse_iterator rbegin() {
515        return reverse_iterator(mLast);
516    }
517
518    reverse_iterator rend() {
519        return reverse_iterator(nullptr);
520    }
521
522    const_iterator begin() const {
523        return const_iterator(mFirst);
524    }
525
526    const_iterator end() const {
527        return const_iterator(nullptr);
528    }
529
530    const_reverse_iterator rbegin() const {
531        return const_reverse_iterator(mLast);
532    }
533
534    const_reverse_iterator rend() const {
535        return const_reverse_iterator(nullptr);
536    }
537
538    const_iterator cbegin() const {
539        return const_iterator(mFirst);
540    }
541
542    const_iterator cend() const {
543        return const_iterator(nullptr);
544    }
545
546    const_reverse_iterator crbegin() const {
547        return const_reverse_iterator(mLast);
548    }
549
550    const_reverse_iterator crend() const {
551        return const_reverse_iterator(nullptr);
552    }
553
554    inline Statement * front() const {
555        return mFirst;
556    }
557
558    inline Statement * back() const {
559        return mLast;
560    }
561
562    inline void setInsertPoint(Statement * const statement) {
563        assert (statement == nullptr || contains(statement));
564        mInsertionPoint = statement;
565    }
566
567    inline Statement * getInsertPoint() const {
568        return mInsertionPoint;
569    }
570
571    bool contains(const Statement * const statement) const;
572
573protected:
574
575    ~StatementList() = default;
576
577private:
578
579    Statement   * mInsertionPoint;
580    Statement   * mFirst;
581    Statement   * mLast;   
582};
583
584}
585
586#endif // PE_PabloAST_H
Note: See TracBrowser for help on using the repository browser.