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

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

Bug fix for use-def correctness regarding escaping values of If and While nodes.

File size: 13.3 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 <vector>
13#include <slab_allocator.h>
14#include <iterator>
15#include <unordered_map>
16
17using namespace llvm;
18
19namespace pablo {
20
21class PabloBlock;
22class String;
23class Statement;
24
25class PabloAST {
26    friend class Statement;
27    friend class Var;
28    friend class If;   
29    friend class While;
30    friend class PabloBlock;
31    friend class Prototype;
32    friend class PabloFunction;
33    friend class SymbolGenerator;
34public:
35
36    using Allocator = SlabAllocator<u_int8_t>;
37    using VectorAllocator = SlabAllocator<PabloAST *>;
38    using Vector = std::vector<PabloAST*, VectorAllocator>;
39    using user_iterator = Vector::iterator;
40    using const_user_iterator = Vector::const_iterator;
41
42    enum class ClassTypeId : unsigned {
43        /** Non-statements **/
44        // Constants
45        Zeroes
46        , Ones
47        // Internal types
48        , Var
49        , Integer
50        , String
51        , Block
52        , Function
53        , Prototype
54        /** Statements **/
55        // Boolean operations
56        , And
57        , Or
58        , Not
59        , Xor
60        , Sel
61        // Stream operations
62        , Advance
63        , ScanThru
64        , MatchStar
65        // Mod 64 approximate stream operations
66        , Mod64Advance
67        , Mod64ScanThru
68        , Mod64MatchStar
69        // Statistics operations
70        , Count
71        // Variable assignments
72        , Assign
73        , Next
74        , Call
75        , SetIthBit
76        // Scope blocks
77        , If
78        , While
79    };
80    inline ClassTypeId getClassTypeId() const {
81        return mClassTypeId;
82    }
83
84    inline user_iterator user_begin() {
85        return mUsers.begin();
86    }
87
88    inline user_iterator user_end() {
89        return mUsers.end();
90    }
91
92    inline const_user_iterator user_begin() const {
93        return mUsers.cbegin();
94    }
95
96    inline const_user_iterator user_end() const {
97        return mUsers.cend();
98    }
99
100    inline Vector & users() {
101        return mUsers;
102    }
103
104    inline const Vector & users() const {
105        return mUsers;
106    }
107
108    void replaceAllUsesWith(PabloAST * expr);
109
110    inline Vector::size_type getNumUses() const {
111        return mUsers.size();
112    }
113
114    void* operator new (std::size_t size) noexcept {
115        return mAllocator.allocate(size);
116    }
117protected:
118    inline PabloAST(const ClassTypeId id)
119    : mClassTypeId(id)
120    , mUsers(mVectorAllocator)
121    {
122
123    }
124    inline void addUser(PabloAST * user) {
125        assert (user);
126        auto pos = std::lower_bound(mUsers.begin(), mUsers.end(), user);
127        if (LLVM_UNLIKELY(pos != mUsers.end() && *pos == user)) {
128            return;
129        }
130        mUsers.insert(pos, user);
131    }
132    inline void removeUser(PabloAST * user) {
133        assert (user);
134        if (mUsers.empty()) {
135            return;
136        }
137        auto pos = std::lower_bound(mUsers.begin(), mUsers.end(), user);
138        if (LLVM_UNLIKELY(pos == mUsers.end() || *pos != user)) {
139            return;
140        }
141        mUsers.erase(pos);
142    }
143    virtual ~PabloAST() {
144        mUsers.clear();
145    }
146    static Allocator        mAllocator;
147private:
148    const ClassTypeId       mClassTypeId;
149    Vector                  mUsers;
150    static VectorAllocator  mVectorAllocator;
151};
152
153bool equals(const PabloAST * expr1, const PabloAST *expr2);
154
155class StatementList;
156
157class String;
158
159class Statement : public PabloAST {
160    friend class StatementList;
161    friend class If;
162    friend class While;
163    friend class Simplifier;
164    friend class PabloBlock;
165    template <class ValueType, class ValueList>
166    friend void checkForReplacementInEscapedValueList(const Statement *, const PabloAST * const, PabloAST * const, ValueList &);
167public:
168    static inline bool classof(const PabloAST * e) {
169        switch (e->getClassTypeId()) {
170            case PabloAST::ClassTypeId::Zeroes:
171            case PabloAST::ClassTypeId::Ones:
172            case PabloAST::ClassTypeId::Var:
173            case PabloAST::ClassTypeId::String:
174            case PabloAST::ClassTypeId::Integer:
175            case PabloAST::ClassTypeId::Block:
176            case PabloAST::ClassTypeId::Function:
177            case PabloAST::ClassTypeId::Prototype:
178                return false;
179            default:
180                return true;
181        }
182    }
183    static inline bool classof(const Statement *) {
184        return true;
185    }
186    static inline bool classof(const void *) {
187        return false;
188    }
189
190    void replaceUsesOfWith(PabloAST * const from, PabloAST * const to);
191
192    inline PabloAST * getOperand(const unsigned index) const {
193        assert (index < getNumOperands());
194        return mOperand[index];
195    }
196
197    void setOperand(const unsigned index, PabloAST * const value);
198
199    inline unsigned getNumOperands() const {
200        return mOperands;
201    }
202
203    void insertBefore(Statement * const statement);
204    void insertAfter(Statement * const statement);
205    Statement * removeFromParent();
206    Statement * eraseFromParent(const bool recursively = false);
207    Statement * replaceWith(PabloAST * const expr, const bool rename = true, const bool recursively = false);
208
209    inline const String * getName() const {
210        return mName;
211    }
212    inline void setName(const String * const name) {
213        mName = name;
214    }
215    inline Statement * getNextNode() const {
216        return mNext;
217    }
218    inline Statement * getPrevNode() const {
219        return mPrev;
220    }
221    inline PabloBlock * getParent() const {
222        return mParent;
223    }
224    virtual ~Statement() {}
225protected:
226    Statement(const ClassTypeId id, std::initializer_list<PabloAST *> operands, const String * const name)
227    : PabloAST(id)
228    , mName(name)
229    , mNext(nullptr)
230    , mPrev(nullptr)
231    , mParent(nullptr)
232    , mOperands(operands.size())
233    , mOperand(reinterpret_cast<PabloAST**>(mAllocator.allocate(mOperands * sizeof(PabloAST *)))) {
234        unsigned i = 0;
235        for (PabloAST * const op : operands) {
236            mOperand[i++] = op;
237            if (LLVM_LIKELY(op != nullptr)) {
238                op->addUser(this);
239            }
240        }
241    } 
242private:
243    template <class ValueType, class ValueList>
244    void checkForReplacementInEscapedValueList(Statement * branch, PabloAST * const from, PabloAST * const to, ValueList & list);
245protected:   
246    const String *              mName;
247    Statement *                 mNext;
248    Statement *                 mPrev;
249    PabloBlock *                mParent;
250    const unsigned              mOperands;
251    // If we knew prior to construction how many operands were needed, we could
252    // eliminate the mOperand pointer and simply use this[1] instead.
253    PabloAST **                 mOperand;
254};
255
256bool escapes(const Statement * statement);
257
258class StatementList {
259    friend class Statement;
260    friend class PabloBlock;
261public:
262    class iterator: public std::iterator<std::forward_iterator_tag, Statement> {
263    public:
264        iterator(): mCurrent(nullptr) {}
265
266        iterator(Statement* base): mCurrent(base) {}
267
268        iterator(const iterator& other): mCurrent(other.mCurrent) {}
269
270        const iterator& operator=(const iterator& other) {
271            mCurrent = other.mCurrent; return other;
272        }
273
274        inline iterator& operator++() {
275            assert (mCurrent);
276            mCurrent = mCurrent->mNext;
277            return *this;
278        }
279
280        iterator  operator++(int) {
281            iterator tmp(*this);
282            ++(*this);
283            return tmp;
284        }
285
286        bool operator==(const iterator& other) const {
287            return  mCurrent == other.mCurrent;
288        }
289
290        bool operator!=(const iterator& other) const {
291            return  mCurrent != other.mCurrent;
292        }
293
294        Statement* operator*() {return mCurrent;}
295        Statement* operator->(){return mCurrent;}
296
297    private:
298        Statement * mCurrent;
299        friend class const_iterator;
300    };
301
302    class const_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
303    public:
304        const_iterator(): mCurrent(nullptr) {}
305        const_iterator(const Statement* base): mCurrent(base) {}
306        const_iterator(const const_iterator& other): mCurrent(other.mCurrent) {}
307        const const_iterator& operator=(const const_iterator& other) {mCurrent = other.mCurrent; return other;}
308
309        inline const_iterator& operator++() {
310            assert (mCurrent);
311            mCurrent = mCurrent->mNext;
312            return *this;
313        }
314
315        const_iterator  operator++(int) {
316            const_iterator tmp(*this);
317            ++(*this);
318            return tmp;
319        }
320
321        bool operator==(const const_iterator & other) const {
322            return  mCurrent == other.mCurrent;
323        }
324        bool operator!=(const const_iterator & other) const {
325            return  mCurrent != other.mCurrent;
326        }
327
328        const Statement* operator*() {return mCurrent;}
329        const Statement* operator->(){return mCurrent;}
330
331    private:
332        const Statement * mCurrent;
333        friend struct iterator;
334    };
335
336    class reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
337    public:
338        reverse_iterator(): mCurrent(nullptr) {}
339
340        reverse_iterator(Statement* base): mCurrent(base) {}
341
342        reverse_iterator(const reverse_iterator& other): mCurrent(other.mCurrent) {}
343
344        const reverse_iterator& operator=(const reverse_iterator& other) {
345            mCurrent = other.mCurrent; return other;
346        }
347
348        inline reverse_iterator& operator++() {
349            assert (mCurrent);
350            mCurrent = mCurrent->mPrev;
351            return *this;
352        }
353
354        reverse_iterator operator++(int) {
355            reverse_iterator tmp(*this);
356            ++(*this);
357            return tmp;
358        }
359
360        bool operator==(const reverse_iterator& other) const {
361            return  mCurrent == other.mCurrent;
362        }
363
364        bool operator!=(const reverse_iterator& other) const {
365            return  mCurrent != other.mCurrent;
366        }
367
368        Statement* operator*() {return mCurrent;}
369        Statement* operator->(){return mCurrent;}
370
371    private:
372        Statement * mCurrent;
373        friend class const_reverse_iterator;
374    };
375
376    class const_reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
377    public:
378        const_reverse_iterator(): mCurrent(nullptr) {}
379        const_reverse_iterator(const Statement* base): mCurrent(base) {}
380        const_reverse_iterator(const const_reverse_iterator& other): mCurrent(other.mCurrent) {}
381        const const_reverse_iterator& operator=(const const_reverse_iterator& other) {mCurrent = other.mCurrent; return other;}
382
383        inline const_reverse_iterator& operator++() {
384            assert (mCurrent);
385            mCurrent = mCurrent->mPrev;
386            return *this;
387        }
388
389        const_reverse_iterator  operator++(int) {
390            const_reverse_iterator tmp(*this);
391            ++(*this);
392            return tmp;
393        }
394
395        bool operator==(const const_reverse_iterator & other) const {
396            return  mCurrent == other.mCurrent;
397        }
398        bool operator!=(const const_reverse_iterator & other) const {
399            return  mCurrent != other.mCurrent;
400        }
401
402        const Statement* operator*() {return mCurrent;}
403        const Statement* operator->(){return mCurrent;}
404
405    private:
406        const Statement * mCurrent;
407        friend struct iterator;
408    };
409
410public:
411
412    StatementList()
413    : mInsertionPoint(nullptr)
414    , mFirst(nullptr)
415    , mLast(nullptr)
416    {
417
418    }
419
420    StatementList(StatementList && other)
421    : mFirst(other.mFirst)
422    , mLast(other.mLast)
423    {
424        other.mFirst = nullptr;
425        other.mLast = nullptr;
426    }
427
428    iterator begin() {
429        return iterator(mFirst);
430    }
431
432    iterator end() {
433        return iterator(nullptr);
434    }
435
436    reverse_iterator rbegin() {
437        return reverse_iterator(mLast);
438    }
439
440    reverse_iterator rend() {
441        return reverse_iterator(nullptr);
442    }
443
444    const_iterator begin() const {
445        return const_iterator(mFirst);
446    }
447
448    const_iterator end() const {
449        return const_iterator(nullptr);
450    }
451
452    const_reverse_iterator rbegin() const {
453        return const_reverse_iterator(mLast);
454    }
455
456    const_reverse_iterator rend() const {
457        return const_reverse_iterator(nullptr);
458    }
459
460    const_iterator cbegin() const {
461        return const_iterator(mFirst);
462    }
463
464    const_iterator cend() const {
465        return const_iterator(nullptr);
466    }
467
468    const_reverse_iterator crbegin() const {
469        return const_reverse_iterator(mLast);
470    }
471
472    const_reverse_iterator crend() const {
473        return const_reverse_iterator(nullptr);
474    }
475
476    inline Statement * front() const {
477        return mFirst;
478    }
479
480    inline Statement * back() const {
481        return mLast;
482    }
483
484    inline void setInsertPoint(Statement * const statement) {
485        assert (statement == nullptr || contains(statement));
486        mInsertionPoint = statement;
487    }
488
489    inline Statement * getInsertPoint() const {
490        return mInsertionPoint;
491    }
492
493    ~StatementList();
494
495    bool contains(Statement * const statement);
496
497private:
498
499    Statement   * mInsertionPoint;
500    Statement   * mFirst;
501    Statement   * mLast;   
502};
503
504}
505
506#endif // PE_PabloAST_H
507
508
509
Note: See TracBrowser for help on using the repository browser.