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

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

Added vector support for If defined vars back.

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