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

Last change on this file since 5353 was 5329, checked in by nmedfort, 2 years ago

Continued work on parenthesis matching; addition of Pablo ScanTo? and AdvanceThenScanTo/Thru? statements. Bug fix for Pablo Compiler for escaping variables.

File size: 17.0 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        , Kernel
59        // Arithmetic expressions
60        , Add
61        , Subtract
62        // Relational expressions
63        , LessThan
64        , LessThanEquals
65        , Equals
66        , GreaterThanEquals
67        , GreaterThan
68        , NotEquals
69        /** Statements **/
70        // Boolean operations
71        , And
72        , Or
73        , Xor
74        , Not       
75        , Sel
76        // Stream operations
77        , Advance
78        , ScanThru
79        , AdvanceThenScanThru
80        , ScanTo
81        , AdvanceThenScanTo
82        , Lookahead
83        , MatchStar
84        , InFile
85        , AtEOF
86        // Statistics operations
87        , Count
88        // Variable assignments
89        , Assign
90        , Extract     
91        // Scope blocks
92        , If
93        , While
94    };
95
96    inline ClassTypeId getClassTypeId() const noexcept {
97        return mClassTypeId;
98    }
99
100    inline llvm::Type * getType() const noexcept {
101        return mType;
102    }
103
104    inline void setType(llvm::Type * type) noexcept {
105        mType = type;
106    }
107
108    inline user_iterator user_begin() {
109        return mUsers.begin();
110    }
111
112    inline user_iterator user_end() {
113        return mUsers.end();
114    }
115
116    inline const_user_iterator user_begin() const {
117        return mUsers.cbegin();
118    }
119
120    inline const_user_iterator user_end() const {
121        return mUsers.cend();
122    }
123
124    inline Users & users() {
125        return mUsers;
126    }
127
128    inline const Users & users() const {
129        return mUsers;
130    }
131
132    void replaceAllUsesWith(PabloAST * const expr);
133
134    inline Users::size_type getNumUses() const {
135        return mUsers.size();
136    }
137
138    void * operator new (std::size_t size, Allocator & allocator) noexcept {
139        return allocator.allocate<uint8_t>(size);
140    }
141
142//    void operator delete (void * ptr) {
143//        mAllocator.deallocate(static_cast<Allocator::value_type *>(ptr));
144//    }
145
146    void print(llvm::raw_ostream & O) const;
147
148protected:
149    inline PabloAST(const ClassTypeId id, llvm::Type * const type, Allocator & allocator)
150    : mClassTypeId(id)
151    , mType(type)
152    , mUsers(allocator) {
153
154    }
155    bool addUser(PabloAST * const user);
156    bool removeUser(PabloAST * const user);
157    virtual ~PabloAST() {
158        mUsers.clear();
159    }       
160private:
161    const ClassTypeId       mClassTypeId;
162    llvm::Type *            mType;
163    Users                   mUsers;
164};
165
166bool equals(const PabloAST * const expr1, const PabloAST * const expr2);
167
168bool dominates(const PabloAST * const expr1, const PabloAST * const expr2);
169
170bool postdominates(const PabloAST * const expr1, const PabloAST * const expr2);
171
172class StatementList;
173
174class String;
175
176class Statement : public PabloAST {
177    friend class StatementList;
178    friend class If;
179    friend class While;
180    friend class Simplifier;
181    friend class PabloBlock;
182public:
183    static inline bool classof(const PabloAST * e) {
184        return ((unsigned)e->getClassTypeId() >= (unsigned)PabloAST::ClassTypeId::And);
185    }
186    static inline bool classof(const Statement *) {
187        return true;
188    }
189    static inline bool classof(const void *) {
190        return false;
191    }
192
193    void replaceUsesOfWith(PabloAST * const from, PabloAST * const to);
194
195    const String & getName() const noexcept {
196        return *mName;
197    }
198
199    void setName(const String * const name) noexcept;
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
230    explicit Statement(const ClassTypeId id, llvm::Type * const type, std::initializer_list<PabloAST *> operands, const String * const name, Allocator & allocator)
231    : PabloAST(id, type, allocator)
232    , mOperands(operands.size())
233    , mOperand(allocator.allocate(mOperands))
234    , mNext(nullptr)
235    , mPrev(nullptr)
236    , mName(name)
237    , mParent(nullptr) {
238        unsigned i = 0;
239        for (PabloAST * const value : operands) {
240            assert (value);
241            mOperand[i] = value;
242            value->addUser(this);
243            ++i;
244        }
245    }
246
247    explicit Statement(const ClassTypeId id, llvm::Type * const type, const unsigned reserved, const String * const name, Allocator & allocator)
248    : PabloAST(id, type, allocator)
249    , mOperands(0)
250    , mOperand(allocator.allocate(mOperands))
251    , mNext(nullptr)
252    , mPrev(nullptr)
253    , mName(name)
254    , mParent(nullptr) {
255        std::memset(mOperand, 0, reserved * sizeof(PabloAST *));
256    }
257
258    template<typename iterator>
259    explicit Statement(const ClassTypeId id, llvm::Type * const type, iterator begin, iterator end, const String * const name, Allocator & allocator)
260    : PabloAST(id, type, allocator)
261    , mOperands(std::distance(begin, end))
262    , mOperand(allocator.allocate(mOperands))
263    , mNext(nullptr)
264    , mPrev(nullptr)
265    , mName(name)
266    , mParent(nullptr) {
267        unsigned i = 0;
268        for (auto value = begin; value != end; ++value, ++i) {
269            assert (*value);
270            mOperand[i] = *value;
271            (*value)->addUser(this);
272        }
273    }
274
275protected:   
276    unsigned        mOperands;
277    PabloAST **     mOperand;
278    Statement *     mNext;
279    Statement *     mPrev;
280    const String *  mName;
281    PabloBlock *    mParent;
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, llvm::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, llvm::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, llvm::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.