source: icGREP/icgrep-devel/icgrep/pablo/codegenstate.cpp @ 4718

Last change on this file since 4718 was 4718, checked in by cameron, 4 years ago

add Pablo count operation - not yet functional

File size: 19.5 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#include <pablo/codegenstate.h>
8
9namespace pablo {
10
11inline PabloAST * PabloBlock::renameNonNamedNode(PabloAST * expr, const std::string && prefix) {
12    if (Statement * stmt = dyn_cast<Statement>(expr)) {
13        if (stmt->getName()->isGenerated()) {
14            stmt->setName(makeName(prefix, false));
15        }
16    }
17    return expr;
18}
19
20void PabloBlock::insert(Statement * const statement) {
21    assert (statement);
22    if (LLVM_UNLIKELY(mInsertionPoint == nullptr)) {
23        if (mFirst) {
24            statement->insertBefore(mFirst);
25        }
26        else {
27            statement->removeFromParent();
28            statement->mParent = this;
29            mFirst = mLast = statement;
30        }
31    }
32    else {
33        statement->insertAfter(mInsertionPoint);
34        mLast = (mLast == mInsertionPoint) ? statement : mLast;
35        assert (statement->mPrev == mInsertionPoint);
36    }
37    mInsertionPoint = statement;
38}
39
40/// UNARY CREATE FUNCTIONS
41
42Assign * PabloBlock::createAssign(const std::string && prefix, PabloAST * expr)  {
43    return insertAtInsertionPoint(new Assign(expr, makeName(prefix, false)));
44}
45
46PabloAST * PabloBlock::createAdvance(PabloAST * expr, PabloAST * shiftAmount) {
47    if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
48        return expr;
49    }
50    return insertAtInsertionPoint(new Advance(expr, shiftAmount, makeName("advance")));
51}
52
53PabloAST * PabloBlock::createAdvance(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix) {
54    if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
55        return expr;
56    }
57    return insertAtInsertionPoint(new Advance(expr, shiftAmount, makeName(prefix, false)));
58}
59
60PabloAST * PabloBlock::createAdvance(PabloAST * expr, const Integer::Type shiftAmount) {
61    if (isa<Zeroes>(expr) || shiftAmount == 0) {
62        return expr;
63    }
64    return insertAtInsertionPoint(new Advance(expr, getInteger(shiftAmount), makeName("advance")));
65}
66
67PabloAST * PabloBlock::createAdvance(PabloAST * expr, const Integer::Type shiftAmount, const std::string prefix) {
68    if (isa<Zeroes>(expr) || shiftAmount == 0) {
69        return renameNonNamedNode(expr, std::move(prefix));
70    }   
71    return insertAtInsertionPoint(new Advance(expr, getInteger(shiftAmount), makeName(prefix, false)));
72}
73
74Call * PabloBlock::createCall(PabloAST * prototype, const std::vector<PabloAST *> &) {
75    assert (prototype);
76    return insertAtInsertionPoint(new Call(prototype));
77}
78
79
80PabloAST * PabloBlock::createNot(PabloAST * expr) {
81    assert (expr);
82    if (isa<Ones>(expr)) {
83        return createZeroes();
84    }
85    else if (isa<Zeroes>(expr)){
86        return createOnes();
87    }
88    else if (Not * not1 = dyn_cast<Not>(expr)) {
89        return not1->getExpr();
90    }
91    return insertAtInsertionPoint(new Not(expr, makeName("not_")));
92}
93
94PabloAST * PabloBlock::createNot(PabloAST * expr, const std::string prefix) {
95    assert (expr);
96    if (isa<Ones>(expr)) {
97        return createZeroes();
98    }
99    else if (isa<Zeroes>(expr)){
100        return createOnes();
101    }
102    else if (Not * not1 = dyn_cast<Not>(expr)) {       
103        return renameNonNamedNode(not1->getExpr(), std::move(prefix));
104    }
105    return insertAtInsertionPoint(new Not(expr, makeName(prefix, false)));
106}
107
108Var * PabloBlock::createVar(PabloAST * name) {
109    assert (name);
110    return new Var(name);
111}
112
113PabloAST * PabloBlock::createMod64Advance(PabloAST * expr, PabloAST * shiftAmount) {
114    if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
115        return expr;
116    }
117    return insertAtInsertionPoint(new Mod64Advance(expr, shiftAmount, makeName("advance")));
118}
119
120PabloAST * PabloBlock::createMod64Advance(PabloAST * expr, PabloAST * shiftAmount, const std::string prefix) {
121    if (isa<Zeroes>(expr) || cast<Integer>(shiftAmount)->value() == 0) {
122        return expr;
123    }
124    return insertAtInsertionPoint(new Mod64Advance(expr, shiftAmount, makeName(prefix, false)));
125}
126
127PabloAST * PabloBlock::createMod64Advance(PabloAST * expr, const Integer::Type shiftAmount) {
128    if (isa<Zeroes>(expr) || shiftAmount == 0) {
129        return expr;
130    }
131    return insertAtInsertionPoint(new Mod64Advance(expr, getInteger(shiftAmount), makeName("advance")));
132}
133
134PabloAST * PabloBlock::createMod64Advance(PabloAST * expr, const Integer::Type shiftAmount, const std::string prefix) {
135    if (isa<Zeroes>(expr) || shiftAmount == 0) {
136        return renameNonNamedNode(expr, std::move(prefix));
137    }   
138    return insertAtInsertionPoint(new Mod64Advance(expr, getInteger(shiftAmount), makeName(prefix, false)));
139}
140
141PabloAST * PabloBlock::createCount(PabloAST * expr) {
142    assert (expr);
143    return insertAtInsertionPoint(new Count(expr, makeName("count_")));
144}
145
146PabloAST * PabloBlock::createCount(PabloAST * expr, const std::string prefix) {
147    assert (expr);
148    return insertAtInsertionPoint(new Count(expr, makeName(prefix, false)));
149}
150
151   
152/// BINARY CREATE FUNCTIONS
153
154Next * PabloBlock::createNext(Assign * assign, PabloAST * expr) {
155    assert (assign && expr);
156    return insertAtInsertionPoint(new Next(assign, expr));
157}
158
159PabloAST * PabloBlock::createMatchStar(PabloAST * marker, PabloAST * charclass) {
160    assert (marker && charclass);
161    if (isa<Zeroes>(marker) || isa<Zeroes>(charclass)) {
162        return marker;
163    }
164    return insertAtInsertionPoint(new MatchStar(marker, charclass, makeName("matchstar")));
165}
166
167PabloAST * PabloBlock::createMatchStar(PabloAST * marker, PabloAST * charclass, const std::string prefix) {
168    assert (marker && charclass);
169    if (isa<Zeroes>(marker) || isa<Zeroes>(charclass)) {
170        return renameNonNamedNode(marker, std::move(prefix));
171    }
172    return insertAtInsertionPoint(new MatchStar(marker, charclass, makeName(prefix, false)));
173}
174
175PabloAST * PabloBlock::createScanThru(PabloAST * from, PabloAST * thru) {
176    assert (from && thru);
177    if (isa<Zeroes>(from) || isa<Zeroes>(thru)) {
178        return from;
179    }
180    return insertAtInsertionPoint(new ScanThru(from, thru, makeName("scanthru")));
181}
182
183PabloAST * PabloBlock::createScanThru(PabloAST * from, PabloAST * thru, const std::string prefix) {
184    assert (from && thru);
185    if (isa<Zeroes>(from) || isa<Zeroes>(thru)) {       
186        return renameNonNamedNode(from, std::move(prefix));
187    }
188    return insertAtInsertionPoint(new ScanThru(from, thru, makeName(prefix, false)));
189}
190
191PabloAST * PabloBlock::createMod64MatchStar(PabloAST * marker, PabloAST * charclass) {
192    assert (marker && charclass);
193    if (isa<Zeroes>(marker) || isa<Zeroes>(charclass)) {
194        return marker;
195    }
196    return insertAtInsertionPoint(new Mod64MatchStar(marker, charclass, makeName("matchstar")));
197}
198
199PabloAST * PabloBlock::createMod64MatchStar(PabloAST * marker, PabloAST * charclass, const std::string prefix) {
200    assert (marker && charclass);
201    if (isa<Zeroes>(marker) || isa<Zeroes>(charclass)) {
202        return renameNonNamedNode(marker, std::move(prefix));
203    }
204    return insertAtInsertionPoint(new Mod64MatchStar(marker, charclass, makeName(prefix, false)));
205}
206
207PabloAST * PabloBlock::createMod64ScanThru(PabloAST * from, PabloAST * thru) {
208    assert (from && thru);
209    if (isa<Zeroes>(from) || isa<Zeroes>(thru)) {
210        return from;
211    }
212    return insertAtInsertionPoint(new Mod64ScanThru(from, thru, makeName("scanthru")));
213}
214
215PabloAST * PabloBlock::createMod64ScanThru(PabloAST * from, PabloAST * thru, const std::string prefix) {
216    assert (from && thru);
217    if (isa<Zeroes>(from) || isa<Zeroes>(thru)) {       
218        return renameNonNamedNode(from, std::move(prefix));
219    }
220    return insertAtInsertionPoint(new Mod64ScanThru(from, thru, makeName(prefix, false)));
221}
222
223
224
225
226PabloAST * PabloBlock::createAnd(PabloAST * expr1, PabloAST * expr2) {
227    assert (expr1 && expr2);
228    if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
229        return expr2;
230    }
231    else if (isa<Zeroes>(expr1) || isa<Ones>(expr2) || equals(expr1, expr2)){
232        return expr1;
233    }
234    else if (Not * not1 = dyn_cast<Not>(expr1)) {
235        if (Not * not2 = dyn_cast<Not>(expr2)) {
236            return createNot(createOr(not1->getExpr(), not2->getExpr()));
237        }
238        else if (equals(not1->getExpr(), expr2)) {
239            return createZeroes();
240        }
241    }
242    else if (Not * not2 = dyn_cast<Not>(expr2)) {
243        if (equals(expr1, not2->getExpr())) {
244            return createZeroes();
245        }
246    }
247    if (isa<Not>(expr1) || expr1 > expr2) {
248        std::swap(expr1, expr2);
249    }
250    return insertAtInsertionPoint(new And(expr1, expr2, makeName("and_")));
251}
252
253
254PabloAST * PabloBlock::createAnd(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
255    assert (expr1 && expr2);
256    if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
257        return renameNonNamedNode(expr2, std::move(prefix));
258    }
259    else if (isa<Zeroes>(expr1) || isa<Ones>(expr2) || equals(expr1, expr2)){
260        return renameNonNamedNode(expr1, std::move(prefix));
261    }
262    else if (Not * not1 = dyn_cast<Not>(expr1)) {
263        if (Not * not2 = dyn_cast<Not>(expr2)) {
264            return createNot(createOr(not1->getExpr(), not2->getExpr()), prefix);
265        }
266        else if (equals(not1->getExpr(), expr2)) {
267            return createZeroes();
268        }
269    }
270    else if (Not * not2 = dyn_cast<Not>(expr2)) {
271        if (equals(expr1, not2->getExpr())) {
272            return createZeroes();
273        }
274    }
275    if (isa<Not>(expr1) || expr1 > expr2) {
276        std::swap(expr1, expr2);
277    }
278    return insertAtInsertionPoint(new And(expr1, expr2, makeName(prefix, false)));
279}
280
281PabloAST * PabloBlock::createOr(PabloAST * expr1, PabloAST * expr2) {
282    assert (expr1 && expr2);
283    if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
284        return expr2;
285    }
286    if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
287        return expr1;
288    }
289    else if (Not * not1 = dyn_cast<Not>(expr1)) {
290        // ¬a√b = ¬¬(¬a√b) = ¬(a ∧ ¬b)
291        return createNot(createAnd(not1->getExpr(), createNot(expr2)));
292    }
293    else if (Not * not2 = dyn_cast<Not>(expr2)) {
294        // a√¬b = ¬¬(¬b√a) = ¬(b ∧ ¬a)
295        return createNot(createAnd(not2->getExpr(), createNot(expr1)));
296    }
297    else if (equals(expr1, expr2)) {
298        return expr1;
299    }
300    else if (And * and_expr1 = dyn_cast<And>(expr1)) {
301        if (And * and_expr2 = dyn_cast<And>(expr2)) {
302            PabloAST * const expr1a = and_expr1->getExpr1();
303            PabloAST * const expr1b = and_expr1->getExpr2();
304            PabloAST * const expr2a = and_expr2->getExpr1();
305            PabloAST * const expr2b = and_expr2->getExpr2();
306            //These optimizations factor out common components that can occur when sets are formed by union
307            //(e.g., union of [a-z] and [A-Z].
308            if (equals(expr1a, expr2a)) {
309                return createAnd(expr1a, createOr(expr1b, expr2b));
310            }
311            else if (equals(expr1b, expr2b)) {
312                return createAnd(expr1b, createOr(expr1a, expr2a));
313            }
314            else if (equals(expr1a, expr2b)) {
315                return createAnd(expr1a, createOr(expr1b, expr2a));
316            }
317            else if (equals(expr1b, expr2a)) {
318                return createAnd(expr1b, createOr(expr1a, expr2b));
319            }
320        }
321    }
322    if (expr1 > expr2) {
323        std::swap(expr1, expr2);
324    }
325    return insertAtInsertionPoint(new Or(expr1, expr2, makeName("or_")));
326}
327
328PabloAST * PabloBlock::createOr(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
329    assert (expr1 && expr2);
330    if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
331        return renameNonNamedNode(expr2, std::move(prefix));
332    }
333    if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
334        return renameNonNamedNode(expr1, std::move(prefix));
335    }
336    else if (Not * not1 = dyn_cast<Not>(expr1)) {
337        // ¬a√b = ¬¬(¬a√b) = ¬(a ∧ ¬b)
338        return createNot(createAnd(not1->getExpr(), createNot(expr2)), prefix);
339    }
340    else if (Not * not2 = dyn_cast<Not>(expr2)) {
341        // a√¬b = ¬¬(¬b√a) = ¬(b ∧ ¬a)
342        return createNot(createAnd(not2->getExpr(), createNot(expr1)), prefix);
343    }
344    else if (And * and_expr1 = dyn_cast<And>(expr1)) {
345        if (And * and_expr2 = dyn_cast<And>(expr2)) {
346            PabloAST * const expr1a = and_expr1->getExpr1();
347            PabloAST * const expr1b = and_expr1->getExpr2();
348            PabloAST * const expr2a = and_expr2->getExpr1();
349            PabloAST * const expr2b = and_expr2->getExpr2();
350            //These optimizations factor out common components that can occur when sets are formed by union
351            //(e.g., union of [a-z] and [A-Z].
352            if (equals(expr1a, expr2a)) {
353                return createAnd(expr1a, createOr(expr1b, expr2b), prefix);
354            }
355            else if (equals(expr1b, expr2b)) {
356                return createAnd(expr1b, createOr(expr1a, expr2a), prefix);
357            }
358            else if (equals(expr1a, expr2b)) {
359                return createAnd(expr1a, createOr(expr1b, expr2a), prefix);
360            }
361            else if (equals(expr1b, expr2a)) {
362                return createAnd(expr1b, createOr(expr1a, expr2b), prefix);
363            }
364        }
365    }
366    if (expr1 > expr2) {
367        std::swap(expr1, expr2);
368    }
369    return insertAtInsertionPoint(new Or(expr1, expr2, makeName(prefix, false)));
370}
371
372PabloAST * PabloBlock::createXor(PabloAST * expr1, PabloAST * expr2) {
373    assert (expr1 && expr2);
374    if (isa<Ones>(expr1)) {
375        return createNot(expr2);
376    }
377    else if (isa<Zeroes>(expr1)){
378        return expr2;
379    }
380    else if (isa<Ones>(expr2)) {
381        return createNot(expr1);
382    }
383    else if (isa<Zeroes>(expr2)){
384        return expr1;
385    }
386    else if (Not * not1 = dyn_cast<Not>(expr1)) {
387        if (Not * not2 = dyn_cast<Not>(expr2)) {
388            return createXor(not1->getExpr(), not2->getExpr());
389        }
390    }
391    if (expr1 > expr2) {
392        std::swap(expr1, expr2);
393    }
394    return insertAtInsertionPoint(new Xor(expr1, expr2, makeName("xor_")));
395}
396
397PabloAST * PabloBlock::createXor(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
398    assert (expr1 && expr2);
399    if (isa<Ones>(expr1)) {
400        return createNot(expr2, prefix);
401    }
402    else if (isa<Zeroes>(expr1)){
403        return expr2;
404    }
405    else if (isa<Ones>(expr2)) {
406        return createNot(expr1, prefix);
407    }
408    else if (isa<Zeroes>(expr2)){
409        return expr1;
410    }
411    else if (Not * not1 = dyn_cast<Not>(expr1)) {
412        if (Not * not2 = dyn_cast<Not>(expr2)) {
413            return createXor(not1->getExpr(), not2->getExpr(), prefix);
414        }
415    }
416    if (expr1 > expr2) {
417        std::swap(expr1, expr2);
418    }
419    return insertAtInsertionPoint(new Xor(expr1, expr2, makeName(prefix, false)));
420}
421
422/// TERNARY CREATE FUNCTION
423
424PabloAST * PabloBlock::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr) {
425    assert (condition && trueExpr && falseExpr);
426    if (isa<Ones>(condition)) {
427        return trueExpr;
428    }
429    else if (isa<Zeroes>(condition)){
430        return falseExpr;
431    }
432    else if (isa<Ones>(trueExpr)) {
433        return createOr(condition, falseExpr);
434    }
435    else if (isa<Zeroes>(trueExpr)){
436        return createAnd(createNot(condition), falseExpr);
437    }
438    else if (isa<Ones>(falseExpr)) {
439        return createOr(createNot(condition), trueExpr);
440    }
441    else if (isa<Zeroes>(falseExpr)){
442        return createAnd(condition, trueExpr);
443    }
444    else if (equals(trueExpr, falseExpr)) {
445        return trueExpr;
446    }
447    else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getExpr(), falseExpr)) {
448        return createXor(condition, falseExpr);
449    }
450    else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getExpr())){
451        return createXor(condition, falseExpr);
452    }
453    return insertAtInsertionPoint(new Sel(condition, trueExpr, falseExpr, makeName("sel")));
454}
455
456PabloAST * PabloBlock::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr, const std::string prefix) {
457    assert (condition && trueExpr && falseExpr);
458
459    if (isa<Zeroes>(condition)){
460        return renameNonNamedNode(falseExpr, std::move(prefix));
461    }
462    else if (isa<Ones>(condition) || equals(trueExpr, falseExpr)) {
463        return renameNonNamedNode(trueExpr, std::move(prefix));
464    }
465    else if (isa<Ones>(trueExpr)) {
466        return createOr(condition, falseExpr, prefix);
467    }
468    else if (isa<Zeroes>(trueExpr)){
469        return createAnd(createNot(condition), falseExpr, prefix);
470    }
471    else if (isa<Ones>(falseExpr)) {
472        return createOr(createNot(condition), trueExpr, prefix);
473    }
474    else if (isa<Zeroes>(falseExpr)){
475        return createAnd(condition, trueExpr, prefix);
476    }
477    else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getExpr(), falseExpr)) {
478        return createXor(condition, falseExpr, prefix);
479    }
480    else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getExpr())){
481        return createXor(condition, falseExpr, prefix);
482    }
483    return insertAtInsertionPoint(new Sel(condition, trueExpr, falseExpr, makeName(prefix, false)));
484}
485
486If * PabloBlock::createIf(PabloAST * condition, const std::initializer_list<Assign *> definedVars, PabloBlock & body) {
487    assert (condition);
488    return insertAtInsertionPoint(new If(condition, definedVars, body));
489}
490
491If * PabloBlock::createIf(PabloAST * condition, const std::vector<Assign *> & definedVars, PabloBlock & body) {
492    assert (condition);
493    return insertAtInsertionPoint(new If(condition, definedVars, body));
494}
495
496If * PabloBlock::createIf(PabloAST * condition, std::vector<Assign *> && definedVars, PabloBlock & body) {
497    assert (condition);
498    return insertAtInsertionPoint(new If(condition, definedVars, body));
499}
500
501While * PabloBlock::createWhile(PabloAST * condition, const std::initializer_list<Next *> nextVars, PabloBlock & body) {
502    assert (condition);
503    return insertAtInsertionPoint(new While(condition, nextVars, body));
504}
505
506While * PabloBlock::createWhile(PabloAST * condition, const std::vector<Next *> & nextVars, PabloBlock & body) {
507    assert (condition);
508    return insertAtInsertionPoint(new While(condition, nextVars, body));
509}
510
511While * PabloBlock::createWhile(PabloAST * condition, std::vector<Next *> && nextVars, PabloBlock & body) {
512    assert (condition);
513    return insertAtInsertionPoint(new While(condition, nextVars, body));
514}
515
516// Assign sequential scope indexes, returning the next unassigned index   
517
518unsigned PabloBlock::enumerateScopes(unsigned baseScopeIndex) {
519    mScopeIndex = baseScopeIndex;
520    unsigned nextScopeIndex = baseScopeIndex + 1;
521    for (Statement * stmt : *this) {
522        if (If * ifStatement = dyn_cast<If>(stmt)) {
523            nextScopeIndex = ifStatement->getBody().enumerateScopes(nextScopeIndex);
524        }
525        else if (While * whileStatement = dyn_cast<While>(stmt)) {
526            nextScopeIndex = whileStatement->getBody().enumerateScopes(nextScopeIndex);
527        }
528    }
529    return nextScopeIndex;
530}   
531           
532   
533       
534   
535/// CONSTRUCTOR
536
537PabloBlock::PabloBlock(SymbolGenerator & symbolGenerator)
538: PabloAST(PabloAST::ClassTypeId::Block)
539, mZeroes(new Zeroes())
540, mOnes(new Ones())
541, mSymbolGenerator(symbolGenerator)
542, mParent(nullptr)
543, mScopeIndex(0)
544{
545
546}
547
548PabloBlock::PabloBlock(PabloBlock * predecessor)
549: PabloAST(PabloAST::ClassTypeId::Block)
550, mZeroes(predecessor->mZeroes) // inherit the original "Zeroes" variable for simplicity
551, mOnes(predecessor->mOnes) // inherit the original "Ones" variable for simplicity
552, mSymbolGenerator(predecessor->mSymbolGenerator)
553, mParent(predecessor)
554, mScopeIndex(0)
555{
556
557}
558
559PabloBlock::~PabloBlock() {
560
561}
562
563}
Note: See TracBrowser for help on using the repository browser.