source: icGREP/icgrep-devel/icgrep/compiler_helper.cpp @ 4122

Last change on this file since 4122 was 3850, checked in by cameron, 5 years ago

icgrep-0.8 distribution

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