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

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

Rewrite of the CarryManager? to support non-carry-collapsing loops.

File size: 16.8 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 <IDISA/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<u_int8_t>;
41    using VectorAllocator = SlabAllocator<PabloAST *>;
42    using Users = std::vector<PabloAST *, VectorAllocator>;
43    using user_iterator = Users::iterator;
44    using const_user_iterator = Users::const_iterator;
45
46    static inline bool classof(const PabloAST *) {
47        return true;
48    }
49    static inline bool classof(const void *) {
50        return false;
51    }
52
53    enum class ClassTypeId : unsigned {
54        /** Non-statements **/
55        // Constants
56        Zeroes
57        , Ones
58        // Internal types
59        , Var       
60        , Integer
61        , String
62        , Block
63        , Function
64        , Prototype
65        // Arithmetic expressions
66        , Add
67        , Subtract
68        // Relational expressions
69        , LessThan
70        , LessThanEquals
71        , Equals
72        , GreaterThanEquals
73        , GreaterThan
74        , NotEquals
75        /** Statements **/
76        // Boolean operations
77        , And
78        , Or
79        , Xor
80        , Not       
81        , Sel
82        // Stream operations
83        , Advance
84        , ScanThru
85        , Lookahead
86        , MatchStar
87        , InFile
88        , AtEOF
89        // Statistics operations
90        , Count
91        // Variable assignments
92        , Assign
93        , Extract     
94        , Call
95        , SetIthBit
96        // Scope blocks
97        , If
98        , While
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(Type * type) noexcept {
110        mType = type;
111    }
112
113    inline const String * getName() const noexcept {
114        return mName;
115    }
116
117    inline void setName(const String * const name) noexcept {
118        mName = name;
119    }
120
121    inline user_iterator user_begin() {
122        return mUsers.begin();
123    }
124
125    inline user_iterator user_end() {
126        return mUsers.end();
127    }
128
129    inline const_user_iterator user_begin() const {
130        return mUsers.cbegin();
131    }
132
133    inline const_user_iterator user_end() const {
134        return mUsers.cend();
135    }
136
137    inline Users & users() {
138        return mUsers;
139    }
140
141    inline const Users & users() const {
142        return mUsers;
143    }
144
145    void replaceAllUsesWith(PabloAST * const expr);
146
147    inline Users::size_type getNumUses() const {
148        return mUsers.size();
149    }
150
151    void * operator new (std::size_t size) noexcept {
152        return mAllocator.allocate(size);
153    }
154
155    void operator delete (void * ptr) {
156        mAllocator.deallocate(static_cast<Allocator::value_type *>(ptr));
157    }
158
159    void print(raw_ostream & O) const;
160
161protected:
162    inline PabloAST(const ClassTypeId id, Type * const type, const String * name)
163    : mClassTypeId(id)
164    , mType(type)
165    , mName(name)
166    , mUsers(mVectorAllocator)
167    {
168
169    }
170    bool addUser(PabloAST * const user);
171    bool removeUser(PabloAST * const user);
172    virtual ~PabloAST() {
173        mUsers.clear();
174    }   
175    static Allocator        mAllocator;
176    static VectorAllocator  mVectorAllocator;
177private:
178    const ClassTypeId       mClassTypeId;
179    Type *                  mType;
180    const String *          mName;
181    Users                   mUsers;
182};
183
184bool equals(const PabloAST * const expr1, const PabloAST * const expr2);
185
186bool dominates(const PabloAST * const expr1, const PabloAST * const expr2);
187
188bool postdominates(const PabloAST * const expr1, const PabloAST * const expr2);
189
190class StatementList;
191
192class String;
193
194class Statement : public PabloAST {
195    friend class StatementList;
196    friend class If;
197    friend class While;
198    friend class Simplifier;
199    friend class PabloBlock;
200public:
201    static inline bool classof(const PabloAST * e) {
202        return ((unsigned)e->getClassTypeId() >= (unsigned)PabloAST::ClassTypeId::And);
203    }
204    static inline bool classof(const Statement *) {
205        return true;
206    }
207    static inline bool classof(const void *) {
208        return false;
209    }
210
211    void replaceUsesOfWith(PabloAST * const from, PabloAST * const to);
212
213    inline PabloAST * getOperand(const unsigned index) const {
214        assert (index < getNumOperands());
215        return mOperand[index];
216    }
217
218    void setOperand(const unsigned index, PabloAST * const value);
219
220    inline unsigned getNumOperands() const {
221        return mOperands;
222    }
223
224    void insertBefore(Statement * const statement);
225    void insertAfter(Statement * const statement);
226    Statement * removeFromParent();
227    Statement * eraseFromParent(const bool recursively = false);
228    Statement * replaceWith(PabloAST * const expr, const bool rename = true, const bool recursively = false);
229
230    inline Statement * getNextNode() const {
231        return mNext;
232    }
233    inline Statement * getPrevNode() const {
234        return mPrev;
235    }
236    inline PabloBlock * getParent() const {
237        return mParent;
238    }
239    virtual ~Statement() {}
240protected:
241    explicit Statement(const ClassTypeId id, Type * const type, std::initializer_list<PabloAST *> operands, const String * const name)
242    : PabloAST(id, type, name)
243    , mNext(nullptr)
244    , mPrev(nullptr)
245    , mParent(nullptr)
246    , mOperands(operands.size())
247    , mOperand(reinterpret_cast<PabloAST**>(mAllocator.allocate(mOperands * sizeof(PabloAST *)))) {
248        unsigned i = 0;
249        for (PabloAST * const value : operands) {
250            assert (value);
251            mOperand[i] = value;
252            value->addUser(this);
253            ++i;
254        }
255    }
256    explicit Statement(const ClassTypeId id, Type * const type, const unsigned reserved, const String * const name)
257    : PabloAST(id, type, name)
258    , mNext(nullptr)
259    , mPrev(nullptr)
260    , mParent(nullptr)
261    , mOperands(0)
262    , mOperand(reinterpret_cast<PabloAST**>(mAllocator.allocate(reserved * sizeof(PabloAST *)))) {
263        std::memset(mOperand, 0, reserved * sizeof(PabloAST *));
264    }
265    template<typename iterator>
266    explicit Statement(const ClassTypeId id, Type * const type, iterator begin, iterator end, const String * const name)
267    : PabloAST(id, type, name)
268    , mNext(nullptr)
269    , mPrev(nullptr)
270    , mParent(nullptr)
271    , mOperands(std::distance(begin, end))
272    , mOperand(reinterpret_cast<PabloAST**>(mAllocator.allocate(mOperands * sizeof(PabloAST *)))) {
273        unsigned i = 0;
274        for (auto value = begin; value != end; ++value, ++i) {
275            assert (*value);
276            mOperand[i] = *value;
277            (*value)->addUser(this);
278        }
279    }
280protected:   
281    Statement *     mNext;
282    Statement *     mPrev;
283    PabloBlock *    mParent;
284    unsigned        mOperands;
285    PabloAST **     mOperand;
286};
287
288class Variadic : public Statement {
289public:
290
291    static inline bool classof(const PabloAST * e) {
292        switch (e->getClassTypeId()) {
293            case PabloAST::ClassTypeId::And:
294            case PabloAST::ClassTypeId::Or:
295            case PabloAST::ClassTypeId::Xor:
296                return true;
297            default: return false;
298        }
299    }
300    static inline bool classof(const Variadic *) {
301        return true;
302    }
303    static inline bool classof(const void *) {
304        return false;
305    }
306
307    class iterator : public boost::iterator_facade<iterator, PabloAST *, boost::random_access_traversal_tag> {
308        friend class Variadic;
309        friend class boost::iterator_core_access;
310    protected:
311
312        iterator(PabloAST ** pointer) : mCurrent(pointer) { }
313        inline void increment() { ++mCurrent; }
314        inline void decrement() { --mCurrent; }
315        inline void advance(const std::ptrdiff_t n) { mCurrent += n; }
316        inline std::ptrdiff_t distance_to(const iterator & other) const { return other.mCurrent - mCurrent; }
317        inline PabloAST *& dereference() const { return *mCurrent; }
318
319        inline bool equal(const iterator & other) const { return (mCurrent == other.mCurrent); }
320
321    private:
322        PabloAST **        mCurrent;
323    };
324
325    using const_iterator = iterator;
326
327    void addOperand(PabloAST * const expr);
328
329    PabloAST * removeOperand(const unsigned index);
330
331    bool deleteOperand(const PabloAST * const expr);
332
333    iterator begin() {
334        return iterator(mOperand);
335    }
336
337    const_iterator begin() const {
338        return iterator(mOperand);
339    }
340
341    iterator end() {
342        return iterator(mOperand + mOperands);
343    }
344
345    const_iterator end() const {
346        return iterator(mOperand + mOperands);
347    }
348
349protected:
350    explicit Variadic(const ClassTypeId id, Type * const type, std::initializer_list<PabloAST *> operands, const String * const name)
351    : Statement(id, type, operands, name)
352    , mCapacity(operands.size()) {
353
354    }
355    explicit Variadic(const ClassTypeId id, Type * const type, const unsigned reserved, const String * name)
356    : Statement(id, type, reserved, name)
357    , mCapacity(reserved) {
358
359    }
360    template<typename iterator>
361    explicit Variadic(const ClassTypeId id, Type * const type, iterator begin, iterator end, const String * name)
362    : Statement(id, type, begin, end, name)
363    , mCapacity(std::distance(begin, end)) {
364
365    }
366private:
367    unsigned        mCapacity;
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.