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

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

Removed string based CC lookup in CC Compiler.

File size: 8.9 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 <re/re_alt.h>
13#include <re/re_cc.h>
14#include <re/re_seq.h>
15#include <re/re_rep.h>
16#include <re/re_name.h>
17
18#include <utility>
19#include <string>
20#include <list>
21#include <map>
22#include <algorithm>
23
24#include <cassert>
25#include <stdlib.h>
26#include <stdexcept>
27
28using namespace re;
29using namespace pablo;
30
31namespace cc {
32
33CC_Compiler::CC_Compiler(CodeGenState & cg, const Encoding encoding, const std::string basis_pattern, const std::string gensym_pattern)
34: mCG(cg)
35, mBasisBit(encoding.getBits())
36, mEncoding(encoding)
37, mGenSymPattern(gensym_pattern)
38, mBasisPattern(basis_pattern)
39{
40    for (int i = 0; i < mEncoding.getBits(); i++) {
41        mBasisBit[i] = mCG.createVar(mBasisPattern + std::to_string((mEncoding.getBits() - 1) - i));
42        mCG.push_back(mBasisBit[i]);
43    }
44}
45
46inline Var * CC_Compiler::getBasisVar(const int i) const {
47    return mBasisBit[i];
48}
49
50void CC_Compiler::compile(const REMap & re_map) {
51    for (auto i =  re_map.cbegin(); i != re_map.cend(); ++i) {
52        process_re(i->second);
53    }
54    for (auto i =  re_map.cbegin(); i != re_map.cend(); ++i) {
55        //This is specifically for the utf8 multibyte character classes.
56        if (Seq * seq = dyn_cast<Seq>(i->second)) {
57            if (seq->getType() == Seq::Type::Byte) {
58                PabloE * marker = nullptr;
59                auto j = seq->begin();
60                while (true) {
61                    Name * name = dyn_cast<Name>(*j);
62                    assert (name);
63                    CharClass * cc = mCG.createCharClass(name->getName());
64                    PabloE * sym = marker ? mCG.createAnd(marker, cc) : cc;
65                    if (++j != seq->end()) {
66                        marker = mCG.createAdvance(sym);
67                        mCG.push_back(marker);
68                        continue;
69                    }
70                    mCG.push_back(mCG.createAssign(seq->getName(), sym));
71                    break;
72                }
73            }
74        }
75    }
76}
77
78void CC_Compiler::process_re(const RE * re) {
79    if (const Alt * alt = dyn_cast<const Alt>(re)) {
80        for (const RE * re : *alt) {
81            process_re(re);
82        }
83    }
84    else if (const CC * cc = dyn_cast<const CC>(re)) {
85        process(cc);
86    }
87    else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
88        process_re(re_rep->getRE());
89    }
90    else if (const Seq* re_seq = dyn_cast<const Seq>(re)) {
91        for (const RE * re : *re_seq) {
92            process_re(re);
93        }
94    }
95}
96
97inline void CC_Compiler::process(const CC * cc) {
98    if (mComputedSet.insert(cc->getName()).second) {
99        //Add the new mapping to the list of pablo statements:
100        mCG.push_back(mCG.createAssign(cc->getName(), charset_expr(cc)));
101    }
102}
103
104PabloE* CC_Compiler::bit_pattern_expr(int pattern, int selected_bits)
105{
106    if (selected_bits == 0) {
107        return mCG.createAll(1);
108    }
109
110    std::vector<PabloE*> bit_terms;
111    int bit_no = 0;
112
113    while (selected_bits)
114    {
115        char test_bit = 1 << bit_no;
116        if (selected_bits & test_bit)
117        {
118            if ((pattern & test_bit) == 0)
119            {
120                bit_terms.push_back(mCG.createNot(getBasisVar(bit_no)));
121            }
122            else
123            {
124                bit_terms.push_back(getBasisVar(bit_no));
125            }
126        }
127        else
128        {
129            bit_terms.push_back(mCG.createAll(1));
130        }
131        selected_bits &= ~test_bit;
132        bit_no++;
133    }
134
135    //Reduce the list so that all of the expressions are contained within a single expression.
136    while (bit_terms.size() > 1)
137    {
138        std::vector<PabloE*> new_terms;
139        for (unsigned long i = 0; i < (bit_terms.size()/2); i++)
140        {
141            new_terms.push_back(mCG.createAnd(bit_terms[(2 * i) + 1], bit_terms[2 * i]));
142        }
143        if (bit_terms.size() % 2 == 1)
144        {
145            new_terms.push_back(bit_terms[bit_terms.size() -1]);
146        }
147        bit_terms.assign(new_terms.begin(), new_terms.end());
148    }
149    return bit_terms[0];
150}
151
152PabloE* CC_Compiler::char_test_expr(const CodePointType ch)
153{
154    return bit_pattern_expr(ch, mEncoding.getMask());
155}
156
157PabloE* CC_Compiler::make_range(const CodePointType n1, const CodePointType n2)
158{
159    CodePointType diff_count = 0;
160
161    for (CodePointType diff_bits = n1 ^ n2; diff_bits; diff_count++, diff_bits >>= 1);
162
163    if ((n2 < n1) || (diff_count > mEncoding.getBits()))
164    {
165        throw std::runtime_error(std::string("Bad Range: [") + std::to_string(n1) + "," + std::to_string(n2) + "]");
166    }
167
168    const CodePointType mask0 = (static_cast<CodePointType>(1) << diff_count) - 1;
169
170    PabloE * common = bit_pattern_expr(n1 & ~mask0, mEncoding.getMask() ^ mask0);
171
172    if (diff_count == 0) return common;
173
174    const CodePointType mask1 = (static_cast<CodePointType>(1) << (diff_count - 1)) - 1;
175
176    PabloE* lo_test = GE_Range(diff_count - 1, n1 & mask1);
177    PabloE* hi_test = LE_Range(diff_count - 1, n2 & mask1);
178
179    return mCG.createAnd(common, mCG.createSel(getBasisVar(diff_count - 1), hi_test, lo_test));
180}
181
182PabloE * CC_Compiler::GE_Range(int N, int n) {
183    if (N == 0)
184    {
185        return mCG.createAll(1); //Return a true literal.
186    }
187    else if (((N % 2) == 0) && ((n >> (N - 2)) == 0))
188    {
189        return mCG.createOr(mCG.createOr(getBasisVar(N - 1), getBasisVar(N - 2)), GE_Range(N - 2, n));
190    }
191    else if (((N % 2) == 0) && ((n >> (N - 2)) == 3))
192    {
193        return mCG.createAnd(mCG.createAnd(getBasisVar(N - 1), getBasisVar(N - 2)), GE_Range(N - 2, n - (3 << (N - 2))));
194    }
195    else if (N >= 1)
196    {
197        int hi_bit = n & (1 << (N-1));
198        int lo_bits = n - hi_bit;
199        PabloE* lo_range = GE_Range(N-1, lo_bits);
200        if (hi_bit == 0)
201        {
202            /*
203              If the hi_bit of n is not set, then whenever the corresponding bit
204              is set in the target, the target will certaily be >=.  Oterwise,
205              the value of GE_range(N-1), lo_range) is required.
206            */
207            return mCG.createOr(getBasisVar(N - 1), lo_range);
208        }
209        else
210        {
211            /*
212              If the hi_bit of n is set, then the corresponding bit must be set
213              in the target for >= and GE_range(N-1, lo_bits) must also be true.
214            */
215            return mCG.createAnd(getBasisVar(N - 1), lo_range);
216        }
217    }
218    throw std::runtime_error("Unexpected input given to ge_range: " + std::to_string(N) + ", " + std::to_string(n));
219}
220
221PabloE * CC_Compiler::LE_Range(int N, int n)
222{
223    /*
224      If an N-bit pattern is all ones, then it is always true that any n-bit value is LE this pattern.
225      Handling this as a special case avoids an overflow issue with n+1 requiring more than N bits.
226    */
227    if ((n + 1) == (1 << N)) {
228        return mCG.createAll(1); //True.
229    }
230    else {
231        return mCG.createNot(GE_Range(N, n + 1));
232    }
233}
234
235PabloE* CC_Compiler::charset_expr(const CC * cc) {
236    if (cc->empty()) {
237        return mCG.createAll(0);
238    }
239    if (cc->size() > 2) {
240        bool combine = true;
241        for (const CharSetItem & item : *cc) {
242            if (item.lo_codepoint != item.hi_codepoint) {
243                combine = false;
244                break;
245            }
246        }
247        if (combine) {
248            auto i = cc->cbegin();
249            for (auto j = i; ++j != cc->cend(); i = j) {
250                const CharSetItem & curr_item = *i;
251                const CharSetItem & next_item = *j;
252                if ((curr_item.lo_codepoint + 2) != next_item.lo_codepoint) {
253                    combine  = false;
254                    break;
255                }
256            }
257            if (combine) {
258                CodePointType lo = cc->front().lo_codepoint;
259                CodePointType hi = cc->back().lo_codepoint;
260                const CodePointType mask = mEncoding.getMask();
261                lo &= (mask - 1);
262                hi |= (mask ^ (mask - 1));
263                PabloE * expr = make_range(lo, hi);
264                PabloE * bit0 = getBasisVar(0);
265                if ((lo & 1) == 0) {
266                    bit0 = mCG.createNot(bit0);
267                }
268                return mCG.createAnd(expr, bit0);
269            }
270        }
271    }
272    PabloE * expr = nullptr;
273    for (const CharSetItem & item : *cc) {
274        PabloE * temp = char_or_range_expr(item.lo_codepoint, item.hi_codepoint);
275        expr = (expr == nullptr) ? temp : mCG.createOr(expr, temp);
276    }
277    return expr;
278}
279
280inline PabloE * CC_Compiler::char_or_range_expr(const CodePointType lo, const CodePointType hi) {
281    if (lo == hi) {
282        return char_test_expr(lo);
283    }
284    else if (lo < hi) {
285        return make_range(lo, hi);
286    }
287    throw std::runtime_error(std::string("Invalid Character Set Range: [") + std::to_string(lo) + "," + std::to_string(hi) + "]");
288}
289
290} // end of namespace cc
Note: See TracBrowser for help on using the repository browser.