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

Last change on this file since 4695 was 4692, checked in by nmedfort, 4 years ago

Temporary check in.

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