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

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

Progress on multi-target UCD compiler.

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