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

Last change on this file since 5267 was 5267, checked in by nmedfort, 3 years ago

Code clean-up. Removed Pablo Call, SetIthBit? and Prototype.

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