source: icGREP/icgrep-devel/icgrep/cc_compiler.cpp @ 4129

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

Revert CR introduction; eliminate unused code for 'predefined' syms

File size: 12.8 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.h"
8
9CC_Compiler::CC_Compiler(UTF_Encoding encoding)
10{
11    mEncoding = encoding;
12}
13
14std::list<PabloS*> CC_Compiler::compile(std::string basis_pattern,
15                                        std::string gensym_pattern,
16                                        const std::map<std::string, RE*>& re_map)
17{
18    mEncoding.setBasisPattern(basis_pattern);
19
20    CC_CodeGenObject cgo(gensym_pattern);
21
22    for (int i = 0; i < mEncoding.getBits(); i++)
23    {
24        std::string b_pattern = bit_var((mEncoding.getBits() -1) - i);
25        Expression* expr = new Expression();
26        expr->expr_string  =  b_pattern;
27        expr->pablo_expr = make_bitv(i);
28        cgo.add_predefined(b_pattern, expr);
29    }
30
31    process_re_map(cgo, re_map);
32
33    return cgo.get_stmtsl();
34}
35
36void CC_Compiler::process_re_map(CC_CodeGenObject &cgo,const std::map<std::string, RE*>& re_map)
37{
38    for (auto it =  re_map.rbegin(); it != re_map.rend(); ++it)
39    {
40        process_re(cgo, it->second);
41    }
42}
43
44void CC_Compiler::process_re(CC_CodeGenObject &cgo, RE* re)
45{
46
47    if (Alt* re_alt = dynamic_cast<Alt*>(re))
48    {
49        std::list<RE*>::iterator it;
50        for (it = re_alt->GetREList()->begin(); it != re_alt->GetREList()->end(); ++it)
51        {
52            process_re(cgo, *it);
53        }
54    }
55    else if (CC* re_cc = dynamic_cast<CC*>(re))
56    {
57        cgo = cc2pablos(cgo, re_cc);
58    }
59    else if (Rep* re_rep = dynamic_cast<Rep*>(re))
60    {
61        process_re(cgo, re_rep->getRE());
62    }
63    else if (Seq* re_seq = dynamic_cast<Seq*>(re))
64    {
65        std::list<RE*>::iterator it;
66        for (it = re_seq->GetREList()->begin(); it != re_seq->GetREList()->end(); ++it)
67        {
68            process_re(cgo, *it);
69        }
70    }
71}
72
73PabloE* CC_Compiler::bit_pattern_expr(int pattern, int selected_bits)
74{
75    if (selected_bits == 0) return new All(1);
76
77    std::vector<PabloE*> bit_terms;
78    int bit_no = 0;
79
80    while (selected_bits)
81    {
82        char test_bit = 1 << bit_no;
83        if (selected_bits & test_bit)
84        {
85            if ((pattern & test_bit) == 0)
86            {
87                bit_terms.push_back(CC_Compiler_Helper::make_not(make_bitv(bit_no)));
88            }
89            else
90            {
91                bit_terms.push_back(make_bitv(bit_no));
92            }
93        }
94        else
95        {
96            bit_terms.push_back(new All(1));
97        }
98        selected_bits &= ~test_bit;
99        bit_no++;
100    }
101/*
102    std::cout << "FIRST LOOP:" << std::endl;
103    for (int i = bit_terms.size() - 1; i >= 0; i--)
104    {
105        std::cout << StatementPrinter::ShowPabloE(bit_terms.at(i)) << std::endl;
106    }
107*/
108    //Reduce the list so that all of the expressions are contained within a single expression.
109    while (bit_terms.size() > 1)
110    {
111        std::vector<PabloE*> new_terms;
112        for (unsigned long i = 0; i < (bit_terms.size()/2); i++)
113        {
114            new_terms.push_back(CC_Compiler_Helper::make_and(bit_terms[(2 * i) + 1], bit_terms[2 * i]));
115        }
116        if (bit_terms.size() % 2 == 1)
117        {
118            new_terms.push_back(bit_terms[bit_terms.size() -1]);
119        }
120/*
121        std::cout << "\nNEW TERMS ITERATION:\n" << std::endl;
122        for (int i = new_terms.size() - 1; i >=0; i--)
123        {
124            std::cout <<  StatementPrinter::ShowPabloE(new_terms[i]) << std::endl;
125        }
126        std::cout << "\n" << std::endl;
127*/
128        std::vector<PabloE*>::iterator it;
129        bit_terms.assign(new_terms.begin(), new_terms.end());
130    }
131/*
132    std::cout << "bit_terms.size(): " << bit_terms.size() << std::endl;
133    std::cout << StatementPrinter::ShowPabloE(bit_terms[0]) << std::endl;
134*/
135    return bit_terms[0];
136}
137
138PabloE* CC_Compiler::char_test_expr(int ch)
139{
140    return bit_pattern_expr(ch, mEncoding.getMask());
141}
142
143PabloE* CC_Compiler::make_range(int n1, int n2)
144{
145    unsigned char diff_bits = n1 ^ n2;
146    int diff_count = 0;
147
148    while (diff_bits > 0)
149    {
150        diff_count++;
151        diff_bits >>= 1;
152    }
153
154    if ((n2 < n1) || (diff_count > mEncoding.getBits()))
155    {
156        int n1i = n1;
157        int n2i = n2;
158
159        std::cout << "n1: " << n1i << std::endl;
160        std::cout << "n2: " << n2i << std::endl;
161
162        std::cout << "Exception: Bad Range!" << std::endl;
163        return 0;
164    }
165
166    int mask = pow(2, diff_count) - 1;
167
168    PabloE* common = bit_pattern_expr(n1 & ~mask, mEncoding.getMask() ^ mask);
169    if (diff_count == 0) return common;
170
171    mask = pow(2, (diff_count - 1)) - 1;
172
173    PabloE* lo_test = GE_Range(diff_count - 1, n1 & mask);
174    PabloE* hi_test = LE_Range(diff_count - 1, n2 & mask);
175
176    return CC_Compiler_Helper::make_and(common, CC_Compiler_Helper::make_sel(make_bitv(diff_count - 1), hi_test, lo_test));
177}
178
179PabloE* CC_Compiler::GE_Range(int N, int n)
180{
181    if (N == 0)
182    {
183        return new All(1); //Return a true literal.
184    }
185    else if (((N % 2) == 0) && ((n >> (N - 2)) == 0))
186    {
187        return CC_Compiler_Helper::make_or(CC_Compiler_Helper::make_or(make_bitv(N-1), make_bitv(N-2)), GE_Range(N-2, n));
188    }
189    else if (((N % 2) == 0) && ((n >> (N - 2)) == 3))
190    {
191        return CC_Compiler_Helper::make_and(CC_Compiler_Helper::make_and(make_bitv(N-1), make_bitv(N-2)), GE_Range(N-2, n-(3<<(N-2))));
192    }
193    else if(N >= 1)
194    {
195        int hi_bit = n & (1 << (N-1));
196        int lo_bits = n - hi_bit;
197        PabloE* lo_range = GE_Range(N-1, lo_bits);
198        if (hi_bit == 0)
199        {
200            /*
201              If the hi_bit of n is not set, then whenever the corresponding bit
202              is set in the target, the target will certaily be >=.  Oterwise,
203              the value of GE_range(N-1), lo_range) is required.
204            */
205            return CC_Compiler_Helper::make_or(make_bitv(N-1), lo_range);
206        }
207        else
208        {
209            /*
210              If the hi_bit of n is set, then the corresponding bit must be set
211              in the target for >= and GE_range(N-1, lo_bits) must also be true.
212            */
213            return CC_Compiler_Helper::make_and(make_bitv(N-1), lo_range);
214        }
215    }
216    else
217    {
218        return 0;
219    }
220}
221
222PabloE* CC_Compiler::LE_Range(int N, int n)
223{
224    /*
225      If an N-bit pattern is all ones, then it is always true that any n-bit value is LE this pattern.
226      Handling this as a special case avoids an overflow issue with n+1 requiring more than N bits.
227    */
228    if ((n+1) == pow(2, N))
229    {
230        return new All(1); //True.
231    }
232    else
233    {
234        return CC_Compiler_Helper::make_not(GE_Range(N, n+1));
235    }
236}
237
238PabloE* CC_Compiler::char_or_range_expr(CharSetItem charset_item)
239{
240    if (charset_item.lo_codepoint == charset_item.hi_codepoint)
241    {
242        return char_test_expr(charset_item.lo_codepoint);
243    }
244    else
245    {
246        if (charset_item.lo_codepoint < charset_item.hi_codepoint)
247        {
248            return make_range(charset_item.lo_codepoint, charset_item.hi_codepoint);
249        }
250    }
251
252    std::cout << "Exception: Bad Character Set Item!" << std::endl;
253    return 0;
254}
255
256PabloE* CC_Compiler::charset_expr(CC* cc)
257{
258    if (cc->getItems().size() == 0)
259    {
260        return new All(0);
261    }
262
263    if (cc->getItems().size() > 1)
264    {
265        bool combine = true;
266
267        for (unsigned long i = 0; i < cc->getItems().size(); i++)
268        {
269            CharSetItem item = cc->getItems().at(i);
270            if (item.lo_codepoint != item.hi_codepoint)
271            {
272                combine = false;
273                break;
274            }
275        }
276
277        if (combine)
278        {
279            for (unsigned long i = 0; i < cc->getItems().size() - 1; i ++)
280            {
281                CharSetItem curr_item = cc->getItems().at(i);
282                CharSetItem next_item = cc->getItems().at(i + 1);
283                if (curr_item.lo_codepoint != next_item.lo_codepoint + 2)
284                {
285                    combine  = false;
286                    break;
287                }
288            }
289        }
290
291        if (combine)
292        {
293            CharSetItem first_item = cc->getItems().at(0);
294            CharSetItem last_item = cc->getItems().at(cc->getItems().size() - 1);
295            CharSetItem combined_item;
296            combined_item.lo_codepoint = (last_item.lo_codepoint & 0xFE);
297            combined_item.hi_codepoint = (first_item.hi_codepoint | 0x01);
298
299            return char_or_range_expr(combined_item);
300        }
301    }
302
303    PabloE* e1 = char_or_range_expr(cc->getItems().at(0));
304    if (cc->getItems().size() > 1)
305    {
306        for (unsigned long i = 1; i < cc->getItems().size(); i++)
307        {
308            e1 = CC_Compiler_Helper::make_or(e1, char_or_range_expr(cc->getItems().at(i)));
309        }
310    }
311
312    return e1;
313}
314
315Expression* CC_Compiler::expr2pabloe(CC_CodeGenObject &cgo, PabloE* expr)
316{
317    /*
318      Translate a Pablo Expression into three-address code using
319      the code generator object CC_CodeGenObject.
320    */
321
322    Expression* retExpr = new Expression();
323
324    if (All* all = dynamic_cast<All*>(expr))
325    {
326        if (all->getNum() == 1)
327        {
328            retExpr->expr_string = "All(1)";
329            retExpr->pablo_expr = new All(1);
330        }
331        else if (all->getNum() ==0)
332        {
333            retExpr->expr_string = "All(0)";
334            retExpr->pablo_expr = new All(0);
335        }
336    }
337    else if (Var * var = dynamic_cast<Var*>(expr))
338    {
339            retExpr->expr_string = var->getVar();
340            retExpr->pablo_expr = new Var(var->getVar());
341    }
342    else if (Not* pe_not = dynamic_cast<Not*>(expr))
343    {
344        Expression* ret = cgo.expr_to_variable(expr2pabloe(cgo, pe_not->getExpr()));
345        retExpr->expr_string =  "~" + ret->expr_string;
346        retExpr->pablo_expr = new Not(ret->pablo_expr);
347    }
348    else if(Or* pe_or = dynamic_cast<Or*>(expr))
349    {
350        Expression* ret1 = cgo.expr_to_variable(expr2pabloe(cgo, pe_or->getExpr1()));
351        Expression* ret2 = cgo.expr_to_variable(expr2pabloe(cgo, pe_or->getExpr2()));
352        retExpr->expr_string = "(" + ret1->expr_string + "|" + ret2->expr_string + ")";
353        retExpr->pablo_expr = new Or(ret1->pablo_expr, ret2->pablo_expr);
354    }
355    else if (Xor* pe_xor = dynamic_cast<Xor*>(expr))
356    {
357        Expression* ret1 = cgo.expr_to_variable(expr2pabloe(cgo, pe_xor->getExpr1()));
358        Expression* ret2 = cgo.expr_to_variable(expr2pabloe(cgo, pe_xor->getExpr2()));
359        retExpr->expr_string = "(" + ret1->expr_string + "^" + ret2->expr_string + ")";
360        retExpr->pablo_expr = new Xor(ret1->pablo_expr, ret2->pablo_expr);
361    }
362    else if (And* pe_and = dynamic_cast<And*>(expr))
363    {
364        if (Not* pe_not = dynamic_cast<Not*>(pe_and->getExpr1()))
365        {
366            Expression* ret1 = cgo.expr_to_variable(expr2pabloe(cgo, pe_not->getExpr()));
367            Expression* ret2 = cgo.expr_to_variable(expr2pabloe(cgo, pe_and->getExpr2()));
368            retExpr->expr_string = "(" + ret2->expr_string + "&~" + ret1->expr_string + ")";
369            retExpr->pablo_expr = new And(ret2->pablo_expr, new Not(ret1->pablo_expr));
370        }
371        else if (Not* pe_not = dynamic_cast<Not*>(pe_and->getExpr2()))
372        {
373            Expression* ret1 = cgo.expr_to_variable(expr2pabloe(cgo, pe_and->getExpr1()));
374            Expression* ret2 = cgo.expr_to_variable(expr2pabloe(cgo, pe_not->getExpr()));
375            retExpr->expr_string = "(" + ret1->expr_string  + "&~" + ret2->expr_string + ")";
376            retExpr->pablo_expr = new And(ret1->pablo_expr, new Not(ret2->pablo_expr));
377        }
378        else
379        {
380            Expression* ret1 = cgo.expr_to_variable(expr2pabloe(cgo, pe_and->getExpr1()));
381            Expression* ret2 = cgo.expr_to_variable(expr2pabloe(cgo, pe_and->getExpr2()));
382            retExpr->expr_string = "(" + ret1->expr_string + "&" + ret2->expr_string + ")";
383            retExpr->pablo_expr = new And(ret1->pablo_expr, ret2->pablo_expr);
384        }
385    }
386    else if (Sel * pe_sel = dynamic_cast<Sel*>(expr))
387    {
388        Expression* ret_sel = cgo.expr_to_variable(expr2pabloe(cgo, pe_sel->getIf_expr()));
389        Expression* ret_true = cgo.expr_to_variable(expr2pabloe(cgo, pe_sel->getT_expr()));
390        Expression* ret_false = cgo.expr_to_variable(expr2pabloe(cgo, pe_sel->getF_expr()));
391        retExpr->expr_string = "((" + ret_sel->expr_string + "&" + ret_true->expr_string + ")|(~("
392            + ret_sel->expr_string + ")&" + ret_false->expr_string + ")";
393        retExpr->pablo_expr = new Sel(ret_sel->pablo_expr, ret_true->pablo_expr, ret_false->pablo_expr);
394    }
395
396    return retExpr;
397}
398
399CC_CodeGenObject CC_Compiler::cc2pablos(CC_CodeGenObject cgo, CC* cc)
400{
401    cgo.add_assignment(cc->getName(), expr2pabloe(cgo, charset_expr(cc)));
402
403    return cgo;
404}
405
406std::string CC_Compiler::bit_var(int n)
407{
408    return  mEncoding.getBasisPattern(0) + std::to_string(n);
409}
410
411PabloE* CC_Compiler::make_bitv(int n)
412{
413    return new Var(bit_var((mEncoding.getBits() - 1) - n));
414}
Note: See TracBrowser for help on using the repository browser.