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

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

Work on coalescing algorithm + minor changes.

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