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

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

Added pablo Prototype to compiler. All Calls must be given one instead of a Name.

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