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

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

Restructure - collapse cc_codegenobject into cc_compiler

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