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

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

Cleanups to clear compiler warnings.

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