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

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

Eliminate INT2STRING in favor of std::to_string

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