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

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

Upload of an untested (inactive) UCD compiler.

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