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

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

Minor revisions

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