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

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

Replaced dynamic_cast with llvm::dyn_cast in pablo code; implemented make functions for pablo constructors. Disabled RTTI.

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