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

Last change on this file since 5647 was 5647, checked in by nmedfort, 19 months ago

Minor bug fixes and removal of inadvertent check in for StreamSet?.cpp/h

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