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

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

Work on non carry collapsing mode. Beginning work on pablo-level phi nodes.

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