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

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

Bug fix for long advance

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