source: icGREP/icgrep-devel/icgrep/pablo/pablo_routines.cpp @ 4199

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

First stage of refactoring PabloE classes.

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