source: icGREP/icgrep-devel/icgrep/cc_compiler_helper.cpp @ 4197

Last change on this file since 4197 was 4197, checked in by nmedfort, 5 years ago

More refactoring of the RE system; moved the original re/RE_Compiler to compiler.cpp and the PBIX_Compiler to the re/RE_Compiler.

File size: 9.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 "cc_compiler_helper.h"
8//Pablo Expressions
9#include "pe_advance.h"
10#include "pe_all.h"
11#include "pe_and.h"
12#include "pe_call.h"
13#include "pe_charclass.h"
14#include "pe_matchstar.h"
15#include "pe_not.h"
16#include "pe_or.h"
17#include "pe_pabloe.h"
18#include "pe_scanthru.h"
19#include "pe_sel.h"
20#include "pe_var.h"
21#include "pe_xor.h"
22// #include "pe_pabloe.h"
23// #include "cc_compiler.h"
24
25CC_Compiler_Helper::CC_Compiler_Helper(){}
26
27/*
28    Optimizing Constructors for Boolean Expressions
29
30     -Maintaining Assembler Instruction Form:
31       -All boolean algebraic rules involving true/false applied.
32
33       -Negations restricted:
34         -no negations within or (DeMorgan's to nand)
35         -at most one negation within and.
36*/
37
38PabloE * CC_Compiler_Helper::make_not(PabloE* expr)
39{
40    if (All* all = dynamic_cast<All*>(expr)) {
41        if (all->getNum() == 1) //If true literal.
42        {
43            return new All(0); //Set to false literal.
44        }
45        else //if (all->getNum() == 0) //If false literal.
46        {
47            return new All(1); //Set to true literal.
48        }
49    }
50    else if (Not* pe_not = dynamic_cast<Not*>(expr)) {
51        PabloE * expr = pe_not->getExpr();
52        pe_not->setExpr(nullptr);
53        delete pe_not;
54        return expr;
55    }
56    else {
57        return new Not(expr);
58    }
59}
60
61PabloE * CC_Compiler_Helper::make_and(PabloE * expr1, PabloE *expr2)
62{
63    if (All* all = dynamic_cast<All*>(expr1)) {
64        if (all->getNum() == 1) {
65            delete all;
66            return expr2;
67        }
68        else { //if (all->getNum() == 0)
69            delete expr1;
70            delete expr2;
71            return new All(0);
72        }
73    }
74    else if (All* all = dynamic_cast<All*>(expr2)) {
75        if (all->getNum() == 1) {
76            delete expr2;
77            return expr1;
78        }
79        else { //if (all->getNum() == 0)
80            delete expr1;
81            delete expr2;
82            return new All(0);
83        }
84    }
85    else if (equals(expr1, expr2)) {
86        delete expr2;
87        return expr1;
88    }
89    else if (Not* pe_not_e1 = dynamic_cast<Not*>(expr1)) {
90        if (Not* pe_not_e2 = dynamic_cast<Not*>(expr2)) {
91
92            PabloE * e1 = pe_not_e1->getExpr();
93            pe_not_e1->setExpr(nullptr);
94            delete pe_not_e1;
95
96            PabloE * e2 = pe_not_e2->getExpr();
97            pe_not_e2->setExpr(nullptr);
98            delete pe_not_e2;
99
100            return make_not(make_or(e1, e2));
101        }
102        else if (equals(pe_not_e1->getExpr(), expr2)) {
103            delete expr1;
104            delete expr2;
105            return new All(0); //Return false literal.
106        }
107    }
108    else if (Not * pe_not_e2 = dynamic_cast<Not*>(expr2)) {
109        if (equals(expr1, pe_not_e2->getExpr())) {
110            delete expr1;
111            delete expr2;
112            return new All(0);
113        }
114    }
115    return new And(expr1, expr2);
116}
117
118PabloE * CC_Compiler_Helper::make_or(PabloE * expr1, PabloE * expr2)
119{
120    if (All * all = dynamic_cast<All*>(expr1)) {
121        if (all->getNum() == 1) {
122            delete expr2;
123            return all; //Return a true literal.
124        }
125        else { //if (all->getNum() == 0)
126            delete all;
127            return expr2;
128        }
129    }
130    else if (All * all = dynamic_cast<All*>(expr2)) {
131        if (all->getNum() == 1) {
132            delete expr1;
133            return all; //Return a true literal.
134        }
135        else { //if (all->getNum() == 0)
136            delete all;
137            return expr1;
138        }
139    }
140    else if (Not* pe_not_e1 = dynamic_cast<Not*>(expr1)) {
141        // ¬a||b = ¬¬(¬a||b) = ¬(a ∧ ¬b)
142        PabloE * expr1 = pe_not_e1->getExpr();
143        pe_not_e1->setExpr(nullptr);
144        delete pe_not_e1;
145        return make_not(make_and(expr1, make_not(expr2)));
146    }
147    else if (Not* pe_not_e2 = dynamic_cast<Not*>(expr2)) {
148        PabloE * expr2 = pe_not_e1->getExpr();
149        pe_not_e2->setExpr(nullptr);
150        delete pe_not_e2;
151        return make_not(make_and(expr2, make_not(expr1)));
152    }
153    else if (equals(expr1, expr2)) {
154        delete expr2;
155        return expr1;
156    }
157
158    if (And* and_expr1 = dynamic_cast<And*>(expr1))
159    {
160        if (And* and_expr2 = dynamic_cast<And*>(expr2))
161        {
162            PabloE * expr1a = and_expr1->getExpr1();
163            PabloE * expr1b = and_expr1->getExpr2();
164            PabloE * expr2a = and_expr2->getExpr1();
165            PabloE * expr2b = and_expr2->getExpr1();
166
167            //These optimizations factor out common components that can occur when sets are formed by union
168            //(e.g., union of [a-z] and [A-Z].
169            if (equals(expr1a, expr2a))
170            {
171                return make_and(expr1a, make_or(expr1b, expr2b));
172            }
173            else if (equals(expr1b, expr2b))
174            {
175                return make_and(expr1b, make_or(expr1a, expr2a));
176            }
177            else if (equals(expr1a, expr2b))
178            {
179                return make_and(expr1a, make_or(expr1b, expr2a));
180            }
181            else if (equals(expr1b, expr2a))
182            {
183                return make_and(expr1b, make_or(expr1a, expr2b));
184            }
185        }
186    }
187
188    return new Or(expr1, expr2);
189}
190
191PabloE* CC_Compiler_Helper::make_sel(PabloE *if_expr, PabloE *t_expr, PabloE *f_expr)
192{
193    if (All* all_if_expr = dynamic_cast<All*>(if_expr))
194    {
195        if (all_if_expr->getNum() == 1)
196        {
197            return t_expr;
198        }
199        else //if (all_if_expr->getNum() == 0)
200        {
201            return f_expr;
202        }
203    }
204    else if (All* all_t_expr = dynamic_cast<All*>(t_expr))
205    {
206        if (all_t_expr->getNum() == 1)
207        {
208            return make_or(if_expr, f_expr);
209        }
210        else //if (all_t_expr->getNum() == 0)
211        {
212            return make_and(make_not(if_expr), f_expr);
213        }
214    }
215    else if (All* all_f_expr = dynamic_cast<All*>(f_expr))
216    {
217        if (all_f_expr->getNum() == 1)
218        {
219            return make_or(make_not(if_expr), t_expr);
220        }
221        else //if (all_f_expr->getNum() == 0)
222        {
223            return make_and(if_expr, t_expr);
224        }
225    }
226    else if (equals(t_expr, f_expr))
227    {
228        return t_expr;
229    }
230    else
231    {
232        return new Sel(if_expr, t_expr, f_expr);
233    }
234}
235
236PabloE* CC_Compiler_Helper::make_xor(PabloE *expr1, PabloE *expr2)
237{
238    if (All* all_expr1 = dynamic_cast<All*>(expr1))
239    {
240        if (all_expr1->getNum() == 1)
241        {
242            return make_not(expr2);
243        }
244        else //if (all_expr1->getNum() == 0)
245        {
246            return expr2;
247        }
248    }
249    else if (All* all_expr2 = dynamic_cast<All*>(expr2))
250    {
251        if (all_expr2->getNum() == 1)
252        {
253            return make_not(expr1);
254        }
255        else //if (all_expr2->getNum() == 0)
256        {
257            return expr1;
258        }
259    }
260
261    if (Not* not_expr1 = dynamic_cast<Not*>(expr1))
262    {
263        if (Not* not_expr2 = dynamic_cast<Not*>(expr2))
264        {
265            return make_xor(not_expr1->getExpr(), not_expr2->getExpr());
266        }
267    }
268
269    return new Xor(expr1, expr2);
270}
271
272/*
273
274    Return true if expr1 and expr2 can be proven equivalent according to some rules,
275    false otherwise.  Note that false may be returned i some cases when the exprs are
276    equivalent.
277
278*/
279
280bool CC_Compiler_Helper::equals(const PabloE * expr1, const PabloE * expr2)
281{
282    if (const All * all1 = dynamic_cast<const All*>(expr1)) {
283        if (const All * all2 = dynamic_cast<const All*>(expr2)) {
284            return all1->getNum() == all2->getNum();
285        }
286    }
287    else if (const Var * var1 = dynamic_cast<const Var*>(expr1)) {
288        if (const Var * var2 = dynamic_cast<const Var*>(expr2)) {
289            return (var1->getVar() == var2->getVar());
290        }
291    }
292    else if (const Not* not1 = dynamic_cast<const Not*>(expr1)) {
293        if (const Not* not2 = dynamic_cast<const Not*>(expr2)) {
294            return equals(not1->getExpr(), not2->getExpr());
295        }
296    }
297    else if (const And* and1 = dynamic_cast<const And*>(expr1)) {
298        if (const And* and2 = dynamic_cast<const And*>(expr2)) {
299            if (equals(and1->getExpr1(), and2->getExpr1())) {
300                return equals(and1->getExpr2(), and2->getExpr2());
301            }
302            else if (equals(and1->getExpr1(), and2->getExpr2())) {
303                return equals(and1->getExpr2(), and2->getExpr1());
304            }
305        }
306    }
307    else if (const Or * or1 = dynamic_cast<const Or*>(expr1)) {
308        if (const Or* or2 = dynamic_cast<const Or*>(expr2)) {
309            if (equals(or1->getExpr1(), or2->getExpr1())) {
310                return equals(or1->getExpr2(), or2->getExpr2());
311            }
312            else if (equals(or1->getExpr1(), or2->getExpr2())) {
313                return equals(or1->getExpr2(), or2->getExpr1());
314            }
315        }
316    }
317    else if (const Xor * xor1 = dynamic_cast<const Xor *>(expr1)) {
318        if (const Xor * xor2 = dynamic_cast<const Xor *>(expr2)) {
319            if (equals(xor1->getExpr1(), xor2->getExpr1())) {
320                return equals(xor1->getExpr2(), xor2->getExpr2());
321            }
322            else if (equals(xor1->getExpr1(), xor2->getExpr2())) {
323                return equals(xor1->getExpr2(), xor2->getExpr1());
324            }
325        }
326    }
327    else if (const Sel* sel1 = dynamic_cast<const Sel*>(expr1)) {
328        if (const Sel* sel2 = dynamic_cast<const Sel*>(expr2)) {
329            if (equals(sel1->getIf_expr(), sel2->getIf_expr())) {
330                if (equals(sel1->getT_expr(), sel2->getT_expr())) {
331                    return equals(sel1->getF_expr(), sel2->getF_expr());
332                }
333            }
334        }
335    }
336
337    return false;
338}
Note: See TracBrowser for help on using the repository browser.