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

Last change on this file since 5486 was 5486, checked in by nmedfort, 2 years ago

Initial attempt to improve debugging capabilities with compilation stack traces on error.

File size: 18.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 <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
171bool postdominates(const PabloAST * const expr1, const PabloAST * const expr2);
172
173class StatementList;
174
175class String;
176
177class Statement : public PabloAST {
178    friend class StatementList;
179    friend class If;
180    friend class While;
181    friend class Simplifier;
182    friend class PabloBlock;
183public:
184    static inline bool classof(const PabloAST * e) {
185        return ((unsigned)e->getClassTypeId() >= (unsigned)PabloAST::ClassTypeId::And);
186    }
187    static inline bool classof(const Statement *) {
188        return true;
189    }
190    static inline bool classof(const void *) {
191        return false;
192    }
193
194    void replaceUsesOfWith(PabloAST * const from, PabloAST * const to);
195
196    const String & getName() const noexcept {
197        return *mName;
198    }
199
200    void setName(const String * const name) noexcept;
201
202    inline PabloAST * getOperand(const unsigned index) const {
203        assert (index < getNumOperands());
204        return mOperand[index];
205    }
206
207    void setOperand(const unsigned index, PabloAST * const value);
208
209    inline unsigned getNumOperands() const {
210        return mOperands;
211    }
212
213    void insertBefore(Statement * const statement);
214    void insertAfter(Statement * const statement);
215    Statement * removeFromParent();
216    Statement * eraseFromParent(const bool recursively = false);
217    Statement * replaceWith(PabloAST * const expr, const bool rename = true, const bool recursively = false);
218
219    inline Statement * getNextNode() const {
220        return mNext;
221    }
222    inline Statement * getPrevNode() const {
223        return mPrev;
224    }
225    inline PabloBlock * getParent() const {
226        return mParent;
227    }
228    virtual ~Statement() = default;
229
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(reserved))
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 CarryProducingStatement : public Statement {
287public:
288
289    static inline bool classof(const PabloAST * e) {
290        switch (e->getClassTypeId()) {
291            case PabloAST::ClassTypeId::Advance:
292            case PabloAST::ClassTypeId::ScanThru:
293            case PabloAST::ClassTypeId::AdvanceThenScanThru:
294            case PabloAST::ClassTypeId::ScanTo:
295            case PabloAST::ClassTypeId::AdvanceThenScanTo:
296            case PabloAST::ClassTypeId::MatchStar:
297                return true;
298            default: return false;
299        }
300    }
301    static inline bool classof(const CarryProducingStatement *) {
302        return true;
303    }
304    static inline bool classof(const void *) {
305        return false;
306    }
307
308    unsigned getCarryGroup() const {
309        return mCarryGroup;
310    }
311
312    void setCarryGroup(const unsigned carryGroup) {
313        mCarryGroup = carryGroup;
314    }
315
316    virtual ~CarryProducingStatement() = default;
317
318protected:
319
320    explicit CarryProducingStatement(const ClassTypeId id, llvm::Type * const type, std::initializer_list<PabloAST *> operands, const String * const name, Allocator & allocator)
321    : Statement(id, type, operands, name, allocator)
322    , mCarryGroup(0) {
323
324    }
325
326    explicit CarryProducingStatement(const ClassTypeId id, llvm::Type * const type, const unsigned reserved, const String * name, Allocator & allocator)
327    : Statement(id, type, reserved, name, allocator)
328    , mCarryGroup(0) {
329
330    }
331
332    template<typename iterator>
333    explicit CarryProducingStatement(const ClassTypeId id, llvm::Type * const type, iterator begin, iterator end, const String * name, Allocator & allocator)
334    : Statement(id, type, begin, end, name, allocator)
335    , mCarryGroup(0) {
336
337    }
338
339private:
340
341    unsigned mCarryGroup;
342};
343
344
345class Variadic : public Statement {
346public:
347
348    static inline bool classof(const PabloAST * e) {
349        switch (e->getClassTypeId()) {
350            case PabloAST::ClassTypeId::And:
351            case PabloAST::ClassTypeId::Or:
352            case PabloAST::ClassTypeId::Xor:
353                return true;
354            default: return false;
355        }
356    }
357    static inline bool classof(const Variadic *) {
358        return true;
359    }
360    static inline bool classof(const void *) {
361        return false;
362    }
363
364    class iterator : public boost::iterator_facade<iterator, PabloAST *, boost::random_access_traversal_tag> {
365        friend class Variadic;
366        friend class boost::iterator_core_access;
367    protected:
368
369        iterator(PabloAST ** pointer) : mCurrent(pointer) { }
370        inline void increment() { ++mCurrent; }
371        inline void decrement() { --mCurrent; }
372        inline void advance(const std::ptrdiff_t n) { mCurrent += n; }
373        inline std::ptrdiff_t distance_to(const iterator & other) const { return other.mCurrent - mCurrent; }
374        inline PabloAST *& dereference() const { return *mCurrent; }
375
376        inline bool equal(const iterator & other) const { return (mCurrent == other.mCurrent); }
377
378    private:
379        PabloAST **        mCurrent;
380    };
381
382    using const_iterator = iterator;
383
384    void addOperand(PabloAST * const expr);
385
386    PabloAST * removeOperand(const unsigned index);
387
388    bool deleteOperand(const PabloAST * const expr);
389
390    iterator begin() {
391        return iterator(mOperand);
392    }
393
394    const_iterator begin() const {
395        return iterator(mOperand);
396    }
397
398    iterator end() {
399        return iterator(mOperand + mOperands);
400    }
401
402    const_iterator end() const {
403        return iterator(mOperand + mOperands);
404    }
405
406    virtual ~Variadic() = default;
407
408protected:
409    explicit Variadic(const ClassTypeId id, llvm::Type * const type, std::initializer_list<PabloAST *> operands, const String * const name, Allocator & allocator)
410    : Statement(id, type, operands, name, allocator)
411    , mCapacity(operands.size())
412    , mAllocator(allocator) {
413
414    }
415    explicit Variadic(const ClassTypeId id, llvm::Type * const type, const unsigned reserved, const String * name, Allocator & allocator)
416    : Statement(id, type, reserved, name, allocator)
417    , mCapacity(reserved)
418    , mAllocator(allocator) {
419
420    }
421    template<typename iterator>
422    explicit Variadic(const ClassTypeId id, llvm::Type * const type, iterator begin, iterator end, const String * name, Allocator & allocator)
423    : Statement(id, type, begin, end, name, allocator)
424    , mCapacity(std::distance(begin, end))
425    , mAllocator(allocator) {
426
427    }
428private:
429    unsigned        mCapacity;
430    Allocator &     mAllocator;
431};
432
433class StatementList {
434    friend class Statement;
435    friend class PabloBlock;
436public:
437    class iterator: public std::iterator<std::forward_iterator_tag, Statement> {
438    public:
439        iterator(): mCurrent(nullptr) {}
440
441        iterator(Statement* base): mCurrent(base) {}
442
443        iterator(const iterator& other): mCurrent(other.mCurrent) {}
444
445        const iterator& operator=(const iterator& other) {
446            mCurrent = other.mCurrent; return other;
447        }
448
449        inline iterator& operator++() {
450            assert (mCurrent);
451            mCurrent = mCurrent->mNext;
452            return *this;
453        }
454
455        iterator  operator++(int) {
456            iterator tmp(*this);
457            ++(*this);
458            return tmp;
459        }
460
461        bool operator==(const iterator& other) const {
462            return  mCurrent == other.mCurrent;
463        }
464
465        bool operator!=(const iterator& other) const {
466            return  mCurrent != other.mCurrent;
467        }
468
469        Statement* operator*() {return mCurrent;}
470        Statement* operator->(){return mCurrent;}
471
472    private:
473        Statement * mCurrent;
474        friend class const_iterator;
475    };
476
477    class const_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
478    public:
479        const_iterator(): mCurrent(nullptr) {}
480        const_iterator(const Statement* base): mCurrent(base) {}
481        const_iterator(const const_iterator& other): mCurrent(other.mCurrent) {}
482        const const_iterator& operator=(const const_iterator& other) {mCurrent = other.mCurrent; return other;}
483
484        inline const_iterator& operator++() {
485            assert (mCurrent);
486            mCurrent = mCurrent->mNext;
487            return *this;
488        }
489
490        const_iterator  operator++(int) {
491            const_iterator tmp(*this);
492            ++(*this);
493            return tmp;
494        }
495
496        bool operator==(const const_iterator & other) const {
497            return  mCurrent == other.mCurrent;
498        }
499        bool operator!=(const const_iterator & other) const {
500            return  mCurrent != other.mCurrent;
501        }
502
503        const Statement* operator*() {return mCurrent;}
504        const Statement* operator->(){return mCurrent;}
505
506    private:
507        const Statement * mCurrent;
508        friend struct iterator;
509    };
510
511    class reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
512    public:
513        reverse_iterator(): mCurrent(nullptr) {}
514
515        reverse_iterator(Statement* base): mCurrent(base) {}
516
517        reverse_iterator(const reverse_iterator& other): mCurrent(other.mCurrent) {}
518
519        const reverse_iterator& operator=(const reverse_iterator& other) {
520            mCurrent = other.mCurrent; return other;
521        }
522
523        inline reverse_iterator& operator++() {
524            assert (mCurrent);
525            mCurrent = mCurrent->mPrev;
526            return *this;
527        }
528
529        reverse_iterator operator++(int) {
530            reverse_iterator tmp(*this);
531            ++(*this);
532            return tmp;
533        }
534
535        bool operator==(const reverse_iterator& other) const {
536            return  mCurrent == other.mCurrent;
537        }
538
539        bool operator!=(const reverse_iterator& other) const {
540            return  mCurrent != other.mCurrent;
541        }
542
543        Statement* operator*() {return mCurrent;}
544        Statement* operator->(){return mCurrent;}
545
546    private:
547        Statement * mCurrent;
548        friend class const_reverse_iterator;
549    };
550
551    class const_reverse_iterator: public std::iterator<std::forward_iterator_tag, Statement> {
552    public:
553        const_reverse_iterator(): mCurrent(nullptr) {}
554        const_reverse_iterator(const Statement* base): mCurrent(base) {}
555        const_reverse_iterator(const const_reverse_iterator& other): mCurrent(other.mCurrent) {}
556        const const_reverse_iterator& operator=(const const_reverse_iterator& other) {mCurrent = other.mCurrent; return other;}
557
558        inline const_reverse_iterator& operator++() {
559            assert (mCurrent);
560            mCurrent = mCurrent->mPrev;
561            return *this;
562        }
563
564        const_reverse_iterator  operator++(int) {
565            const_reverse_iterator tmp(*this);
566            ++(*this);
567            return tmp;
568        }
569
570        bool operator==(const const_reverse_iterator & other) const {
571            return  mCurrent == other.mCurrent;
572        }
573        bool operator!=(const const_reverse_iterator & other) const {
574            return  mCurrent != other.mCurrent;
575        }
576
577        const Statement* operator*() {return mCurrent;}
578        const Statement* operator->(){return mCurrent;}
579
580    private:
581        const Statement * mCurrent;
582        friend struct iterator;
583    };
584
585public:
586
587    StatementList()
588    : mInsertionPoint(nullptr)
589    , mFirst(nullptr)
590    , mLast(nullptr) {
591
592    }
593
594    StatementList(StatementList && other)
595    : mInsertionPoint(nullptr)
596    , mFirst(other.mFirst)
597    , mLast(other.mLast) {
598        other.mInsertionPoint = nullptr;
599        other.mFirst = nullptr;
600        other.mLast = nullptr;
601    }
602
603    iterator begin() {
604        return iterator(mFirst);
605    }
606
607    iterator end() {
608        return iterator(nullptr);
609    }
610
611    reverse_iterator rbegin() {
612        return reverse_iterator(mLast);
613    }
614
615    reverse_iterator rend() {
616        return reverse_iterator(nullptr);
617    }
618
619    const_iterator begin() const {
620        return const_iterator(mFirst);
621    }
622
623    const_iterator end() const {
624        return const_iterator(nullptr);
625    }
626
627    const_reverse_iterator rbegin() const {
628        return const_reverse_iterator(mLast);
629    }
630
631    const_reverse_iterator rend() const {
632        return const_reverse_iterator(nullptr);
633    }
634
635    const_iterator cbegin() const {
636        return const_iterator(mFirst);
637    }
638
639    const_iterator cend() const {
640        return const_iterator(nullptr);
641    }
642
643    const_reverse_iterator crbegin() const {
644        return const_reverse_iterator(mLast);
645    }
646
647    const_reverse_iterator crend() const {
648        return const_reverse_iterator(nullptr);
649    }
650
651    inline Statement * front() const {
652        return mFirst;
653    }
654
655    inline Statement * back() const {
656        return mLast;
657    }
658
659    inline void setInsertPoint(Statement * const statement) {
660        assert (statement == nullptr || contains(statement));
661        mInsertionPoint = statement;
662    }
663
664    inline Statement * getInsertPoint() const {
665        return mInsertionPoint;
666    }
667
668    bool contains(Statement * const statement);
669
670protected:
671
672    ~StatementList() = default;
673
674private:
675
676    Statement   * mInsertionPoint;
677    Statement   * mFirst;
678    Statement   * mLast;   
679};
680
681/** ------------------------------------------------------------------------------------------------------------- *
682 * @brief deleteOperand
683 ** ------------------------------------------------------------------------------------------------------------- */
684inline bool Variadic::deleteOperand(const PabloAST * const expr) {
685    for (unsigned i = 0; i != getNumOperands(); ++i) {
686        if (LLVM_UNLIKELY(getOperand(i) == expr)) {
687            removeOperand(i);
688            return true;
689        }
690    }
691    return false;
692}
693
694}
695
696#endif // PE_PabloAST_H
Note: See TracBrowser for help on using the repository browser.