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

Last change on this file since 4965 was 4965, checked in by hongpum, 3 years ago

Fix a memset which has arguments in wrong order

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