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

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

Mod64Advance, Mod64MatchStar, Mod64ScanThru ops; -mod64-approximate command-line option

File size: 19.2 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
141
142/// BINARY CREATE FUNCTIONS
143
144Next * PabloBlock::createNext(Assign * assign, PabloAST * expr) {
145    assert (assign && expr);
146    return insertAtInsertionPoint(new Next(assign, expr));
147}
148
149PabloAST * PabloBlock::createMatchStar(PabloAST * marker, PabloAST * charclass) {
150    assert (marker && charclass);
151    if (isa<Zeroes>(marker) || isa<Zeroes>(charclass)) {
152        return marker;
153    }
154    return insertAtInsertionPoint(new MatchStar(marker, charclass, makeName("matchstar")));
155}
156
157PabloAST * PabloBlock::createMatchStar(PabloAST * marker, PabloAST * charclass, const std::string prefix) {
158    assert (marker && charclass);
159    if (isa<Zeroes>(marker) || isa<Zeroes>(charclass)) {
160        return renameNonNamedNode(marker, std::move(prefix));
161    }
162    return insertAtInsertionPoint(new MatchStar(marker, charclass, makeName(prefix, false)));
163}
164
165PabloAST * PabloBlock::createScanThru(PabloAST * from, PabloAST * thru) {
166    assert (from && thru);
167    if (isa<Zeroes>(from) || isa<Zeroes>(thru)) {
168        return from;
169    }
170    return insertAtInsertionPoint(new ScanThru(from, thru, makeName("scanthru")));
171}
172
173PabloAST * PabloBlock::createScanThru(PabloAST * from, PabloAST * thru, const std::string prefix) {
174    assert (from && thru);
175    if (isa<Zeroes>(from) || isa<Zeroes>(thru)) {       
176        return renameNonNamedNode(from, std::move(prefix));
177    }
178    return insertAtInsertionPoint(new ScanThru(from, thru, makeName(prefix, false)));
179}
180
181PabloAST * PabloBlock::createMod64MatchStar(PabloAST * marker, PabloAST * charclass) {
182    assert (marker && charclass);
183    if (isa<Zeroes>(marker) || isa<Zeroes>(charclass)) {
184        return marker;
185    }
186    return insertAtInsertionPoint(new Mod64MatchStar(marker, charclass, makeName("matchstar")));
187}
188
189PabloAST * PabloBlock::createMod64MatchStar(PabloAST * marker, PabloAST * charclass, const std::string prefix) {
190    assert (marker && charclass);
191    if (isa<Zeroes>(marker) || isa<Zeroes>(charclass)) {
192        return renameNonNamedNode(marker, std::move(prefix));
193    }
194    return insertAtInsertionPoint(new Mod64MatchStar(marker, charclass, makeName(prefix, false)));
195}
196
197PabloAST * PabloBlock::createMod64ScanThru(PabloAST * from, PabloAST * thru) {
198    assert (from && thru);
199    if (isa<Zeroes>(from) || isa<Zeroes>(thru)) {
200        return from;
201    }
202    return insertAtInsertionPoint(new Mod64ScanThru(from, thru, makeName("scanthru")));
203}
204
205PabloAST * PabloBlock::createMod64ScanThru(PabloAST * from, PabloAST * thru, const std::string prefix) {
206    assert (from && thru);
207    if (isa<Zeroes>(from) || isa<Zeroes>(thru)) {       
208        return renameNonNamedNode(from, std::move(prefix));
209    }
210    return insertAtInsertionPoint(new Mod64ScanThru(from, thru, makeName(prefix, false)));
211}
212
213
214
215
216PabloAST * PabloBlock::createAnd(PabloAST * expr1, PabloAST * expr2) {
217    assert (expr1 && expr2);
218    if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
219        return expr2;
220    }
221    else if (isa<Zeroes>(expr1) || isa<Ones>(expr2) || equals(expr1, expr2)){
222        return expr1;
223    }
224    else if (Not * not1 = dyn_cast<Not>(expr1)) {
225        if (Not * not2 = dyn_cast<Not>(expr2)) {
226            return createNot(createOr(not1->getExpr(), not2->getExpr()));
227        }
228        else if (equals(not1->getExpr(), expr2)) {
229            return createZeroes();
230        }
231    }
232    else if (Not * not2 = dyn_cast<Not>(expr2)) {
233        if (equals(expr1, not2->getExpr())) {
234            return createZeroes();
235        }
236    }
237    if (isa<Not>(expr1) || expr1 > expr2) {
238        std::swap(expr1, expr2);
239    }
240    return insertAtInsertionPoint(new And(expr1, expr2, makeName("and_")));
241}
242
243
244PabloAST * PabloBlock::createAnd(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
245    assert (expr1 && expr2);
246    if (isa<Zeroes>(expr2) || isa<Ones>(expr1)) {
247        return renameNonNamedNode(expr2, std::move(prefix));
248    }
249    else if (isa<Zeroes>(expr1) || isa<Ones>(expr2) || equals(expr1, expr2)){
250        return renameNonNamedNode(expr1, std::move(prefix));
251    }
252    else if (Not * not1 = dyn_cast<Not>(expr1)) {
253        if (Not * not2 = dyn_cast<Not>(expr2)) {
254            return createNot(createOr(not1->getExpr(), not2->getExpr()), prefix);
255        }
256        else if (equals(not1->getExpr(), expr2)) {
257            return createZeroes();
258        }
259    }
260    else if (Not * not2 = dyn_cast<Not>(expr2)) {
261        if (equals(expr1, not2->getExpr())) {
262            return createZeroes();
263        }
264    }
265    if (isa<Not>(expr1) || expr1 > expr2) {
266        std::swap(expr1, expr2);
267    }
268    return insertAtInsertionPoint(new And(expr1, expr2, makeName(prefix, false)));
269}
270
271PabloAST * PabloBlock::createOr(PabloAST * expr1, PabloAST * expr2) {
272    assert (expr1 && expr2);
273    if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
274        return expr2;
275    }
276    if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
277        return expr1;
278    }
279    else if (Not * not1 = dyn_cast<Not>(expr1)) {
280        // ¬a√b = ¬¬(¬a√b) = ¬(a ∧ ¬b)
281        return createNot(createAnd(not1->getExpr(), createNot(expr2)));
282    }
283    else if (Not * not2 = dyn_cast<Not>(expr2)) {
284        // a√¬b = ¬¬(¬b√a) = ¬(b ∧ ¬a)
285        return createNot(createAnd(not2->getExpr(), createNot(expr1)));
286    }
287    else if (equals(expr1, expr2)) {
288        return expr1;
289    }
290    else if (And * and_expr1 = dyn_cast<And>(expr1)) {
291        if (And * and_expr2 = dyn_cast<And>(expr2)) {
292            PabloAST * const expr1a = and_expr1->getExpr1();
293            PabloAST * const expr1b = and_expr1->getExpr2();
294            PabloAST * const expr2a = and_expr2->getExpr1();
295            PabloAST * const expr2b = and_expr2->getExpr2();
296            //These optimizations factor out common components that can occur when sets are formed by union
297            //(e.g., union of [a-z] and [A-Z].
298            if (equals(expr1a, expr2a)) {
299                return createAnd(expr1a, createOr(expr1b, expr2b));
300            }
301            else if (equals(expr1b, expr2b)) {
302                return createAnd(expr1b, createOr(expr1a, expr2a));
303            }
304            else if (equals(expr1a, expr2b)) {
305                return createAnd(expr1a, createOr(expr1b, expr2a));
306            }
307            else if (equals(expr1b, expr2a)) {
308                return createAnd(expr1b, createOr(expr1a, expr2b));
309            }
310        }
311    }
312    if (expr1 > expr2) {
313        std::swap(expr1, expr2);
314    }
315    return insertAtInsertionPoint(new Or(expr1, expr2, makeName("or_")));
316}
317
318PabloAST * PabloBlock::createOr(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
319    assert (expr1 && expr2);
320    if (isa<Zeroes>(expr1) || isa<Ones>(expr2)){
321        return renameNonNamedNode(expr2, std::move(prefix));
322    }
323    if (isa<Zeroes>(expr2) || isa<Ones>(expr1) || equals(expr1, expr2)) {
324        return renameNonNamedNode(expr1, std::move(prefix));
325    }
326    else if (Not * not1 = dyn_cast<Not>(expr1)) {
327        // ¬a√b = ¬¬(¬a√b) = ¬(a ∧ ¬b)
328        return createNot(createAnd(not1->getExpr(), createNot(expr2)), prefix);
329    }
330    else if (Not * not2 = dyn_cast<Not>(expr2)) {
331        // a√¬b = ¬¬(¬b√a) = ¬(b ∧ ¬a)
332        return createNot(createAnd(not2->getExpr(), createNot(expr1)), prefix);
333    }
334    else if (And * and_expr1 = dyn_cast<And>(expr1)) {
335        if (And * and_expr2 = dyn_cast<And>(expr2)) {
336            PabloAST * const expr1a = and_expr1->getExpr1();
337            PabloAST * const expr1b = and_expr1->getExpr2();
338            PabloAST * const expr2a = and_expr2->getExpr1();
339            PabloAST * const expr2b = and_expr2->getExpr2();
340            //These optimizations factor out common components that can occur when sets are formed by union
341            //(e.g., union of [a-z] and [A-Z].
342            if (equals(expr1a, expr2a)) {
343                return createAnd(expr1a, createOr(expr1b, expr2b), prefix);
344            }
345            else if (equals(expr1b, expr2b)) {
346                return createAnd(expr1b, createOr(expr1a, expr2a), prefix);
347            }
348            else if (equals(expr1a, expr2b)) {
349                return createAnd(expr1a, createOr(expr1b, expr2a), prefix);
350            }
351            else if (equals(expr1b, expr2a)) {
352                return createAnd(expr1b, createOr(expr1a, expr2b), prefix);
353            }
354        }
355    }
356    if (expr1 > expr2) {
357        std::swap(expr1, expr2);
358    }
359    return insertAtInsertionPoint(new Or(expr1, expr2, makeName(prefix, false)));
360}
361
362PabloAST * PabloBlock::createXor(PabloAST * expr1, PabloAST * expr2) {
363    assert (expr1 && expr2);
364    if (isa<Ones>(expr1)) {
365        return createNot(expr2);
366    }
367    else if (isa<Zeroes>(expr1)){
368        return expr2;
369    }
370    else if (isa<Ones>(expr2)) {
371        return createNot(expr1);
372    }
373    else if (isa<Zeroes>(expr2)){
374        return expr1;
375    }
376    else if (Not * not1 = dyn_cast<Not>(expr1)) {
377        if (Not * not2 = dyn_cast<Not>(expr2)) {
378            return createXor(not1->getExpr(), not2->getExpr());
379        }
380    }
381    if (expr1 > expr2) {
382        std::swap(expr1, expr2);
383    }
384    return insertAtInsertionPoint(new Xor(expr1, expr2, makeName("xor_")));
385}
386
387PabloAST * PabloBlock::createXor(PabloAST * expr1, PabloAST * expr2, const std::string prefix) {
388    assert (expr1 && expr2);
389    if (isa<Ones>(expr1)) {
390        return createNot(expr2, prefix);
391    }
392    else if (isa<Zeroes>(expr1)){
393        return expr2;
394    }
395    else if (isa<Ones>(expr2)) {
396        return createNot(expr1, prefix);
397    }
398    else if (isa<Zeroes>(expr2)){
399        return expr1;
400    }
401    else if (Not * not1 = dyn_cast<Not>(expr1)) {
402        if (Not * not2 = dyn_cast<Not>(expr2)) {
403            return createXor(not1->getExpr(), not2->getExpr(), prefix);
404        }
405    }
406    if (expr1 > expr2) {
407        std::swap(expr1, expr2);
408    }
409    return insertAtInsertionPoint(new Xor(expr1, expr2, makeName(prefix, false)));
410}
411
412/// TERNARY CREATE FUNCTION
413
414PabloAST * PabloBlock::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr) {
415    assert (condition && trueExpr && falseExpr);
416    if (isa<Ones>(condition)) {
417        return trueExpr;
418    }
419    else if (isa<Zeroes>(condition)){
420        return falseExpr;
421    }
422    else if (isa<Ones>(trueExpr)) {
423        return createOr(condition, falseExpr);
424    }
425    else if (isa<Zeroes>(trueExpr)){
426        return createAnd(createNot(condition), falseExpr);
427    }
428    else if (isa<Ones>(falseExpr)) {
429        return createOr(createNot(condition), trueExpr);
430    }
431    else if (isa<Zeroes>(falseExpr)){
432        return createAnd(condition, trueExpr);
433    }
434    else if (equals(trueExpr, falseExpr)) {
435        return trueExpr;
436    }
437    else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getExpr(), falseExpr)) {
438        return createXor(condition, falseExpr);
439    }
440    else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getExpr())){
441        return createXor(condition, falseExpr);
442    }
443    return insertAtInsertionPoint(new Sel(condition, trueExpr, falseExpr, makeName("sel")));
444}
445
446PabloAST * PabloBlock::createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr, const std::string prefix) {
447    assert (condition && trueExpr && falseExpr);
448
449    if (isa<Zeroes>(condition)){
450        return renameNonNamedNode(falseExpr, std::move(prefix));
451    }
452    else if (isa<Ones>(condition) || equals(trueExpr, falseExpr)) {
453        return renameNonNamedNode(trueExpr, std::move(prefix));
454    }
455    else if (isa<Ones>(trueExpr)) {
456        return createOr(condition, falseExpr, prefix);
457    }
458    else if (isa<Zeroes>(trueExpr)){
459        return createAnd(createNot(condition), falseExpr, prefix);
460    }
461    else if (isa<Ones>(falseExpr)) {
462        return createOr(createNot(condition), trueExpr, prefix);
463    }
464    else if (isa<Zeroes>(falseExpr)){
465        return createAnd(condition, trueExpr, prefix);
466    }
467    else if (isa<Not>(trueExpr) && equals(cast<Not>(trueExpr)->getExpr(), falseExpr)) {
468        return createXor(condition, falseExpr, prefix);
469    }
470    else if (isa<Not>(falseExpr) && equals(trueExpr, cast<Not>(falseExpr)->getExpr())){
471        return createXor(condition, falseExpr, prefix);
472    }
473    return insertAtInsertionPoint(new Sel(condition, trueExpr, falseExpr, makeName(prefix, false)));
474}
475
476If * PabloBlock::createIf(PabloAST * condition, const std::initializer_list<Assign *> definedVars, PabloBlock & body) {
477    assert (condition);
478    return insertAtInsertionPoint(new If(condition, definedVars, body));
479}
480
481If * PabloBlock::createIf(PabloAST * condition, const std::vector<Assign *> & definedVars, PabloBlock & body) {
482    assert (condition);
483    return insertAtInsertionPoint(new If(condition, definedVars, body));
484}
485
486If * PabloBlock::createIf(PabloAST * condition, std::vector<Assign *> && definedVars, PabloBlock & body) {
487    assert (condition);
488    return insertAtInsertionPoint(new If(condition, definedVars, body));
489}
490
491While * PabloBlock::createWhile(PabloAST * condition, const std::initializer_list<Next *> nextVars, PabloBlock & body) {
492    assert (condition);
493    return insertAtInsertionPoint(new While(condition, nextVars, body));
494}
495
496While * PabloBlock::createWhile(PabloAST * condition, const std::vector<Next *> & nextVars, PabloBlock & body) {
497    assert (condition);
498    return insertAtInsertionPoint(new While(condition, nextVars, body));
499}
500
501While * PabloBlock::createWhile(PabloAST * condition, std::vector<Next *> && nextVars, PabloBlock & body) {
502    assert (condition);
503    return insertAtInsertionPoint(new While(condition, nextVars, body));
504}
505
506// Assign sequential scope indexes, returning the next unassigned index   
507
508unsigned PabloBlock::enumerateScopes(unsigned baseScopeIndex) {
509    mScopeIndex = baseScopeIndex;
510    unsigned nextScopeIndex = baseScopeIndex + 1;
511    for (Statement * stmt : *this) {
512        if (If * ifStatement = dyn_cast<If>(stmt)) {
513            nextScopeIndex = ifStatement->getBody().enumerateScopes(nextScopeIndex);
514        }
515        else if (While * whileStatement = dyn_cast<While>(stmt)) {
516            nextScopeIndex = whileStatement->getBody().enumerateScopes(nextScopeIndex);
517        }
518    }
519    return nextScopeIndex;
520}   
521           
522   
523       
524   
525/// CONSTRUCTOR
526
527PabloBlock::PabloBlock(SymbolGenerator & symbolGenerator)
528: PabloAST(PabloAST::ClassTypeId::Block)
529, mZeroes(new Zeroes())
530, mOnes(new Ones())
531, mSymbolGenerator(symbolGenerator)
532, mParent(nullptr)
533, mScopeIndex(0)
534{
535
536}
537
538PabloBlock::PabloBlock(PabloBlock * predecessor)
539: PabloAST(PabloAST::ClassTypeId::Block)
540, mZeroes(predecessor->mZeroes) // inherit the original "Zeroes" variable for simplicity
541, mOnes(predecessor->mOnes) // inherit the original "Ones" variable for simplicity
542, mSymbolGenerator(predecessor->mSymbolGenerator)
543, mParent(predecessor)
544, mScopeIndex(0)
545{
546
547}
548
549PabloBlock::~PabloBlock() {
550
551}
552
553}
Note: See TracBrowser for help on using the repository browser.