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

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

Bug fix for CC_Compiler

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