source: icGREP/icgrep-devel/icgrep/pablo/builder.cpp @ 5202

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

Initial work on adding types to PabloAST and mutable Var objects.

File size: 18.4 KB
Line 
1#include <pablo/builder.hpp>
2// #include <boost/current_function.hpp> // BOOST_CURRENT_FUNCTION
3
4namespace pablo {
5
6#define MAKE_UNARY(NAME, TYPE, ARGS...) \
7struct __##NAME { \
8    inline PabloAST * operator()(PabloAST * arg) { \
9        return mPb->NAME(arg); \
10    } \
11    inline __##NAME(PabloBlock * pb) : mPb(pb) {} \
12private: \
13    PabloBlock * mPb; \
14}; \
15__##NAME functor(mPb); \
16PabloAST * result = mExprTable.findUnaryOrCall(std::move(functor), TYPE, ARGS)
17
18#define MAKE_NAMED_UNARY(NAME, TYPE, PREFIX, ARGS...) \
19struct __##NAME { \
20    inline PabloAST * operator()(PabloAST * arg) { \
21        return mPb->NAME(arg, mPrefix); \
22    } \
23    inline __##NAME(PabloBlock * pb, const std::string & prefix) : mPb(pb), mPrefix(prefix) {} \
24private: \
25    PabloBlock * mPb; \
26    const std::string & mPrefix; \
27}; \
28__##NAME functor(mPb, prefix); \
29PabloAST * result = mExprTable.findUnaryOrCall(std::move(functor), TYPE, ARGS)
30
31#define MAKE_BINARY(NAME, TYPE, ARGS...) \
32struct __##NAME { \
33    inline PabloAST * operator()(PabloAST * arg1, PabloAST * arg2) { \
34        return mPb->NAME(arg1, arg2); \
35    } \
36    inline __##NAME(PabloBlock * pb) : mPb(pb) {} \
37private: \
38    PabloBlock * mPb; \
39}; \
40__##NAME functor(mPb); \
41PabloAST * result = mExprTable.findBinaryOrCall(std::move(functor), TYPE, ARGS)
42
43#define MAKE_NAMED_BINARY(NAME, TYPE, PREFIX, ARGS...) \
44struct __##NAME { \
45    inline PabloAST * operator()(PabloAST * arg1, PabloAST * arg2) { \
46        return mPb->NAME(arg1, arg2, mPrefix); \
47    } \
48    inline __##NAME(PabloBlock * pb, const std::string & prefix) : mPb(pb), mPrefix(prefix) {} \
49private: \
50    PabloBlock * mPb; \
51    const std::string & mPrefix; \
52}; \
53__##NAME functor(mPb, PREFIX); \
54PabloAST * result = mExprTable.findBinaryOrCall(std::move(functor), TYPE, ARGS)
55
56#define MAKE_TERNARY(NAME, TYPE, ARGS...) \
57struct __##NAME { \
58    inline PabloAST * operator()(PabloAST * arg1, PabloAST * arg2, PabloAST * arg3) { \
59        return mPb->NAME(arg1, arg2, arg3); \
60    } \
61    inline __##NAME(PabloBlock * pb) : mPb(pb) {} \
62private: \
63    PabloBlock * mPb; \
64}; \
65__##NAME functor(mPb); \
66PabloAST * result = mExprTable.findTernaryOrCall(std::move(functor), TYPE, ARGS)
67
68#define MAKE_NAMED_TERNARY(NAME, TYPE, PREFIX, ARGS...) \
69struct __##NAME { \
70    inline PabloAST * operator()(PabloAST * arg1, PabloAST * arg2, PabloAST * arg3) { \
71        return mPb->NAME(arg1, arg2, arg3, mPrefix); \
72    } \
73    inline __##NAME(PabloBlock * pb, const std::string & prefix) : mPb(pb), mPrefix(prefix) {} \
74private: \
75    PabloBlock * mPb; \
76    const std::string & mPrefix; \
77}; \
78__##NAME functor(mPb, PREFIX); \
79PabloAST * result = mExprTable.findTernaryOrCall(std::move(functor), TYPE, ARGS)
80
81#define MAKE_VARIABLE(NAME, TYPE, ARGS...) \
82struct __##NAME { \
83    inline PabloAST * operator()(const std::vector<PabloAST *> & args, PabloAST * prototype) { \
84        return mPb->NAME(prototype, args); \
85    } \
86    inline __##NAME(PabloBlock * pb) : mPb(pb) {} \
87private: \
88    PabloBlock * mPb; \
89}; \
90__##NAME functor(mPb); \
91PabloAST * result = mExprTable.findVariadicOrCall(std::move(functor), TYPE, ARGS)
92
93template<typename Type>
94static inline Type * isBinary(PabloAST * expr) {
95    if (isa<Type>(expr) && cast<Type>(expr)->getNumOperands() == 2) {
96        return cast<Type>(expr);
97    }
98    return nullptr;
99}
100
101using TypeId = PabloAST::ClassTypeId;
102
103Call * PabloBuilder::createCall(Prototype * prototype, const std::vector<PabloAST *> & args) {
104    if (prototype == nullptr) {
105        throw std::runtime_error("Call object cannot be created with a Null prototype!");
106    }
107    if (args.size() != cast<Prototype>(prototype)->getNumOfParameters()) {
108        throw std::runtime_error("Invalid number of arguments passed into Call object!");
109    }
110    MAKE_VARIABLE(createCall, TypeId::Call, prototype->getName(), args, prototype);
111    return cast<Call>(result);
112}
113
114PabloAST * PabloBuilder::createAdvance(PabloAST * expr, PabloAST * shiftAmount) {
115    if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
116        return expr;
117    }
118    MAKE_BINARY(createAdvance, TypeId::Advance, expr, shiftAmount);
119    return result;
120}
121
122PabloAST * PabloBuilder::createAdvance(PabloAST * expr, PabloAST * shiftAmount, const std::string & prefix) {
123    if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
124        return expr;
125    }
126    MAKE_NAMED_BINARY(createAdvance, TypeId::Advance, prefix, expr, shiftAmount);
127    return result;
128}
129
130Extract * PabloBuilder::createExtract(PabloAST * value, not_null<PabloAST *> index) {
131    MAKE_BINARY(createExtract, TypeId::Extract, value, index);
132    return cast<Extract>(result);
133}
134
135Extract * PabloBuilder::createExtract(PabloAST * value, not_null<PabloAST *> index, const std::string & prefix) {
136    MAKE_NAMED_BINARY(createExtract, TypeId::Extract, prefix, value, index);
137    return cast<Extract>(result);
138}
139
140PabloAST * PabloBuilder::createLookahead(PabloAST * expr, PabloAST * shiftAmount) {
141    if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
142        return expr;
143    }
144    MAKE_BINARY(createLookahead, TypeId::Lookahead, expr, shiftAmount);
145    return result;
146}
147
148PabloAST * PabloBuilder::createLookahead(PabloAST * expr, PabloAST * shiftAmount, const std::string & prefix) {
149    if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
150        return expr;
151    }
152    MAKE_NAMED_BINARY(createLookahead, TypeId::Lookahead, prefix, expr, shiftAmount);
153    return result;
154}
155
156PabloAST * PabloBuilder::createNot(PabloAST * expr) {
157    if (isa<Ones>(expr)) {
158        return createZeroes(expr->getType());
159    }
160    else if (isa<Zeroes>(expr)){
161        return createOnes(expr->getType());
162    }
163    else if (Not * not1 = dyn_cast<Not>(expr)) {
164        return not1->getOperand(0);
165    }
166    MAKE_UNARY(createNot, TypeId::Not, expr);
167    return result;
168}
169
170PabloAST * PabloBuilder::createNot(PabloAST * expr, const std::string & prefix) {
171    if (isa<Ones>(expr)) {
172        return createZeroes(expr->getType());
173    }
174    else if (isa<Zeroes>(expr)){
175        return createOnes(expr->getType());
176    }
177    else if (Not * not1 = dyn_cast<Not>(expr)) {
178        return not1->getOperand(0);
179    }
180    MAKE_NAMED_UNARY(createNot, TypeId::Not, prefix, expr);
181    return result;
182}
183
184PabloAST * PabloBuilder::createCount(PabloAST * expr) {
185    MAKE_UNARY(createCount, TypeId::Count, expr);
186    return result;
187}
188
189PabloAST * PabloBuilder::createCount(PabloAST * expr, const std::string & prefix) {
190    MAKE_NAMED_UNARY(createCount, TypeId::Count, prefix, expr);
191    return result;
192}
193
194PabloAST * PabloBuilder::createAssign(PabloAST * const variable, PabloAST * const value) {
195    MAKE_BINARY(createAssign, TypeId::Assign, variable, value);
196    return result;
197}
198
199PabloAST * PabloBuilder::createAnd(PabloAST * expr1, PabloAST * expr2) {
200    if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
201        return expr2;
202    } else if (isa<Zeroes>(expr1) || isa<Ones>(expr2) || equals(expr1, expr2)){
203        return expr1;
204    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
205        if (Not * not2 = dyn_cast<Not>(expr2)) {
206            return createNot(createOr(not1->getOperand(0), not2->getOperand(0)));
207        } else if (equals(not1->getOperand(0), expr2)) {
208            return createZeroes(expr1->getType());
209        }
210    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
211        if (equals(expr1, not2->getOperand(0))) {
212            return createZeroes(expr1->getType());
213        }
214    } else if (Or * or1 = isBinary<Or>(expr1)) {
215        if (equals(or1->getOperand(0), expr2) || equals(or1->getOperand(1), expr2)) {
216            return expr2;
217        }
218    } else if (Or * or2 = isBinary<Or>(expr2)) {
219        if (equals(or2->getOperand(0), expr1) || equals(or2->getOperand(1), expr1)) {
220            return expr1;
221        }
222    }
223    if (expr1 > expr2) {
224        std::swap(expr1, expr2);
225    }
226    MAKE_BINARY(createAnd, TypeId::And, expr1, expr2);
227    return result;
228}
229
230PabloAST * PabloBuilder::createAnd(PabloAST * expr1, PabloAST * expr2, const std::string & prefix) {
231    if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
232        return expr2;
233    } else if (isa<Zeroes>(expr1) || isa<Ones>(expr2) || equals(expr1, expr2)){
234        return expr1;
235    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
236        if (Not * not2 = dyn_cast<Not>(expr2)) {
237            return createNot(createOr(not1->getOperand(0), not2->getOperand(0)), prefix);
238        } else if (equals(not1->getOperand(0), expr2)) {
239            return createZeroes(expr1->getType());
240        }
241    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
242        if (equals(expr1, not2->getOperand(0))) {
243            return createZeroes(expr1->getType());
244        }
245    } else if (Or * or1 = isBinary<Or>(expr1)) {
246        if (equals(or1->getOperand(0), expr2) || equals(or1->getOperand(1), expr2)) {
247            return expr2;
248        }
249    } else if (Or * or2 = isBinary<Or>(expr2)) {
250        if (equals(or2->getOperand(0), expr1) || equals(or2->getOperand(1), expr1)) {
251            return expr1;
252        }
253    }
254    if (expr1 > expr2) {
255        std::swap(expr1, expr2);
256    }
257    MAKE_NAMED_BINARY(createAnd, TypeId::And, prefix, expr1, expr2);
258    return result;
259}
260
261PabloAST * PabloBuilder::createOr(PabloAST * expr1, PabloAST * expr2) {
262    if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
263        return expr2;
264    }
265    if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
266        return expr1;
267    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
268        // ¬a√b = ¬¬(¬a √ b) = ¬(a ∧ ¬b)
269        return createNot(createAnd(not1->getOperand(0), createNot(expr2)));
270    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
271        // a√¬b = ¬¬(¬b √ a) = ¬(b ∧ ¬a)
272        return createNot(createAnd(not2->getOperand(0), createNot(expr1)));
273    } else if (equals(expr1, expr2)) {
274        return expr1;
275    } else if (And * and1 = isBinary<And>(expr1)) {
276        PabloAST * const expr1a = and1->getOperand(0);
277        PabloAST * const expr1b = and1->getOperand(1);
278        if (And * and2 = isBinary<And>(expr2)) {
279            PabloAST * const expr2a = and2->getOperand(0);
280            PabloAST * const expr2b = and2->getOperand(1);
281            //These optimizations factor out common components that can occur when sets are formed by union
282            //(e.g., union of [a-z] and [A-Z].
283            if (equals(expr1a, expr2a)) {
284                return createAnd(expr1a, createOr(expr1b, expr2b));
285            } else if (equals(expr1b, expr2b)) {
286                return createAnd(expr1b, createOr(expr1a, expr2a));
287            } else if (equals(expr1a, expr2b)) {
288                return createAnd(expr1a, createOr(expr1b, expr2a));
289            } else if (equals(expr1b, expr2a)) {
290                return createAnd(expr1b, createOr(expr1a, expr2b));
291            }
292        } else if (equals(expr1a, expr2) || equals(expr1b, expr2)) {
293            // (a ∧ b) √ a = a
294            return expr2;
295        }
296    } else if (And * and2 = isBinary<And>(expr2)) {
297        if (equals(and2->getOperand(0), expr1) || equals(and2->getOperand(1), expr1)) {
298            return expr1;
299        }
300    }
301    if (expr1 > expr2) {
302        std::swap(expr1, expr2);
303    }
304    MAKE_BINARY(createOr, TypeId::Or, expr1, expr2);
305    return result;
306}
307
308PabloAST * PabloBuilder::createOr(PabloAST * expr1, PabloAST * expr2, const std::string & prefix) {
309    if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
310        return expr2;
311    }
312    if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
313        return expr1;
314    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
315        // ¬a√b = ¬¬(¬a √ b) = ¬(a ∧ ¬b)
316        return createNot(createAnd(not1->getOperand(0), createNot(expr2)), prefix);
317    } else if (Not * not2 = dyn_cast<Not>(expr2)) {
318        // a√¬b = ¬¬(¬b √ a) = ¬(b ∧ ¬a)
319        return createNot(createAnd(not2->getOperand(0), createNot(expr1)), prefix);
320    } else if (equals(expr1, expr2)) {
321        return expr1;
322    } else if (And * and1 = isBinary<And>(expr1)) {
323        PabloAST * const expr1a = and1->getOperand(0);
324        PabloAST * const expr1b = and1->getOperand(1);
325        if (And * and2 = isBinary<And>(expr2)) {
326            PabloAST * const expr2a = and2->getOperand(0);
327            PabloAST * const expr2b = and2->getOperand(1);
328            //These optimizations factor out common components that can occur when sets are formed by union
329            //(e.g., union of [a-z] and [A-Z].
330            if (equals(expr1a, expr2a)) {
331                return createAnd(expr1a, createOr(expr1b, expr2b), prefix);
332            } else if (equals(expr1b, expr2b)) {
333                return createAnd(expr1b, createOr(expr1a, expr2a), prefix);
334            } else if (equals(expr1a, expr2b)) {
335                return createAnd(expr1a, createOr(expr1b, expr2a), prefix);
336            } else if (equals(expr1b, expr2a)) {
337                return createAnd(expr1b, createOr(expr1a, expr2b), prefix);
338            }
339        } else if (equals(expr1a, expr2) || equals(expr1b, expr2)) {
340            // (a ∧ b) √ a = a
341            return expr2;
342        }
343    } else if (And * and2 = isBinary<And>(expr2)) {
344        if (equals(and2->getOperand(0), expr1) || equals(and2->getOperand(1), expr1)) {
345            return expr1;
346        }
347    }
348    if (expr1 > expr2) {
349        std::swap(expr1, expr2);
350    }
351    MAKE_NAMED_BINARY(createOr, TypeId::Or, prefix, expr1, expr2);
352    return result;
353}
354
355PabloAST * PabloBuilder::createXor(PabloAST * expr1, PabloAST * expr2) {
356    if (expr1 == expr2) {
357        return createZeroes(expr1->getType());
358    } else if (isa<Ones>(expr1)) {
359        return createNot(expr2);
360    } else if (isa<Zeroes>(expr1)){
361        return expr2;
362    } else if (isa<Ones>(expr2)) {
363        return createNot(expr1);
364    } else if (isa<Zeroes>(expr2)){
365        return expr1;
366    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
367        if (Not * not2 = dyn_cast<Not>(expr2)) {
368            return createXor(not1->getOperand(0), not2->getOperand(0));
369        }
370    }
371    if (expr1 > expr2) {
372        std::swap(expr1, expr2);
373    }
374    MAKE_BINARY(createXor, TypeId::Xor, expr1, expr2);
375    return result;
376}
377
378PabloAST * PabloBuilder::createXor(PabloAST * expr1, PabloAST * expr2, const std::string & prefix) {
379    if (expr1 == expr2) {
380        return createZeroes(expr1->getType());
381    } else if (isa<Ones>(expr1)) {
382        return createNot(expr2);
383    } else if (isa<Zeroes>(expr1)){
384        return expr2;
385    } else if (isa<Ones>(expr2)) {
386        return createNot(expr1);
387    } else if (isa<Zeroes>(expr2)){
388        return expr1;
389    } else if (Not * not1 = dyn_cast<Not>(expr1)) {
390        if (Not * not2 = dyn_cast<Not>(expr2)) {
391            return createXor(not1->getOperand(0), not2->getOperand(0), prefix);
392        }
393    }
394    if (expr1 > expr2) {
395        std::swap(expr1, expr2);
396    }
397    MAKE_NAMED_BINARY(createXor, TypeId::Xor, prefix, expr1, expr2);
398    return result;
399}
400
401PabloAST * PabloBuilder::createInFile(PabloAST * expr) {
402    MAKE_UNARY(createInFile, TypeId::InFile, expr);
403    return result;
404}
405
406PabloAST * PabloBuilder::createInFile(PabloAST * expr, const std::string & prefix) {
407    MAKE_NAMED_UNARY(createInFile, TypeId::InFile, prefix, expr);
408    return result;
409}
410
411PabloAST * PabloBuilder::createAtEOF(PabloAST * expr) {
412    MAKE_UNARY(createAtEOF, TypeId::AtEOF, expr);
413    return result;
414}
415
416PabloAST * PabloBuilder::createAtEOF(PabloAST * expr, const std::string & prefix) {
417    MAKE_NAMED_UNARY(createAtEOF, TypeId::AtEOF, prefix, expr);
418    return result;
419}
420
421PabloAST * PabloBuilder::createMatchStar(PabloAST * marker, PabloAST * charclass) {
422    if (isa<Zeroes>(marker) || isa<Zeroes>(charclass)) {
423        return marker;
424    }
425    MAKE_BINARY(createMatchStar, TypeId::MatchStar, marker, charclass);
426    return result;
427}
428
429PabloAST * PabloBuilder::createMatchStar(PabloAST * marker, PabloAST * charclass, const std::string & prefix) {
430    if (isa<Zeroes>(marker) || isa<Zeroes>(charclass)) {
431        return marker;
432    }
433    MAKE_NAMED_BINARY(createMatchStar, TypeId::MatchStar, prefix, marker, charclass);
434    return result;
435}
436
437PabloAST * PabloBuilder::createScanThru(PabloAST * from, PabloAST * thru) {
438    if (isa<Zeroes>(from) || isa<Zeroes>(thru)) {
439        return from;
440    }
441    MAKE_BINARY(createScanThru, TypeId::ScanThru, from, thru);
442    return result;
443}
444
445PabloAST * PabloBuilder::createScanThru(PabloAST * from, PabloAST * thru, const std::string & prefix) {
446    if (isa<Zeroes>(from) || isa<Zeroes>(thru)) {
447        return from;
448    }
449    MAKE_NAMED_BINARY(createScanThru, TypeId::ScanThru, prefix, from, thru);
450    return result;
451}
452
453
454PabloAST * PabloBuilder::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr) {
455    if (isa<Ones>(condition)) {
456        return trueExpr;
457    } else if (isa<Zeroes>(condition)){
458        return falseExpr;
459    } else if (isa<Ones>(trueExpr)) {
460        return createOr(condition, falseExpr);
461    } else if (isa<Zeroes>(trueExpr)){
462        return createAnd(createNot(condition), falseExpr);
463    } else if (isa<Ones>(falseExpr)) {
464        return createOr(createNot(condition), trueExpr);
465    } else if (isa<Zeroes>(falseExpr)){
466        return createAnd(condition, trueExpr);
467    } else if (equals(trueExpr, falseExpr)) {
468        return trueExpr;
469    } else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getOperand(0), falseExpr)) {
470        return createXor(condition, falseExpr);
471    } else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getOperand(0))){
472        return createXor(condition, trueExpr);
473    }
474    MAKE_TERNARY(createSel, TypeId::Sel, condition, trueExpr, falseExpr);
475    return result;
476}
477
478PabloAST * PabloBuilder::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr, const std::string & prefix) {
479    if (isa<Ones>(condition)) {
480        return trueExpr;
481    } else if (isa<Zeroes>(condition)){
482        return falseExpr;
483    } else if (isa<Ones>(trueExpr)) {
484        return createOr(condition, falseExpr);
485    } else if (isa<Zeroes>(trueExpr)){
486        return createAnd(createNot(condition), falseExpr);
487    } else if (isa<Ones>(falseExpr)) {
488        return createOr(createNot(condition), trueExpr);
489    } else if (isa<Zeroes>(falseExpr)){
490        return createAnd(condition, trueExpr);
491    } else if (equals(trueExpr, falseExpr)) {
492        return trueExpr;
493    } else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getOperand(0), falseExpr)) {
494        return createXor(condition, falseExpr);
495    } else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getOperand(0))){
496        return createXor(condition, trueExpr);
497    }
498    MAKE_NAMED_TERNARY(createSel, TypeId::Sel, prefix, condition, trueExpr, falseExpr);
499    return result;
500}
501
502}
Note: See TracBrowser for help on using the repository browser.