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

Last change on this file since 5239 was 5238, checked in by cameron, 3 years ago

IR_Gen subdirectory for all IR generation utility functions

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