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

Last change on this file since 4602 was 4602, checked in by nmedfort, 4 years ago

Fixed PabloBuilder? and intergrated it into CC Compiler.

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