source: icGREP/icgrep-devel/icgrep/cc/cc_compiler.cpp @ 4199

Last change on this file since 4199 was 4199, checked in by nmedfort, 5 years ago

First stage of refactoring PabloE classes.

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