source: icGREP/icgrep-devel/icgrep/UCD/ucd_compiler.cpp @ 4771

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

Initial stages of a simple boolean equation reassociation pass.

File size: 20.5 KB
Line 
1#include "ucd_compiler.hpp"
2#include <cc/cc_compiler.h>
3#include <UCD/unicode_set.h>
4#include <utf8_encoder.h>
5
6using namespace cc;
7using namespace re;
8using namespace pablo;
9
10namespace UCD {
11
12/** ------------------------------------------------------------------------------------------------------------- *
13 * @brief generateWithDefaultIfHierarchy
14 * @param set the unicode set to generate
15 * @param the entry block to the function we're filling
16 * @return the output stream with a 1-bit in any position of a character in the unicode set
17 ** ------------------------------------------------------------------------------------------------------------- */
18PabloAST * UCDCompiler::generateWithIfHierarchy(const RangeList & ifRanges, const UnicodeSet & set, PabloBuilder & entry) {
19    // Pregenerate the suffix var outside of the if ranges. The DCE pass will either eliminate it if it's not used or the
20    // code sinking pass will move appropriately into an inner if block.
21    mSuffixVar = mCharacterClassCompiler.compileCC(makeCC(0x80, 0xBF), entry);
22    return generateWithIfHierarchy(ifRanges, set, 0, CC::UNICODE_MAX, entry);
23}
24
25/** ------------------------------------------------------------------------------------------------------------- *
26 * @brief generateCharClassDefsInIfHierarchy
27 * @param ifRangeList
28 ** ------------------------------------------------------------------------------------------------------------- */
29PabloAST * UCDCompiler::generateWithIfHierarchy(const RangeList & ifRanges, const UnicodeSet & set, const codepoint_t lo, const codepoint_t hi, PabloBuilder & builder) {
30
31    PabloAST * target = builder.createZeroes();
32    // Codepoints in unenclosed ranges will be computed unconditionally.
33    // Generate them first so that computed subexpressions may be shared
34    // with calculations within the if hierarchy.
35
36    const auto enclosed = rangeIntersect(ifRanges, lo, hi);
37
38    for (const auto rg : rangeGaps(enclosed, lo, hi)) {
39        target = generateSubRanges(set, lo_codepoint(rg), hi_codepoint(rg), builder, target);
40    }
41
42    const auto outer = outerRanges(enclosed);
43    const auto inner = innerRanges(enclosed);
44    for (const auto range : outer) {
45        codepoint_t lo, hi;
46        std::tie(lo, hi) = range;
47        if (set.intersects(lo, hi)) {
48            PabloBuilder inner_block = PabloBuilder::Create(builder);
49            PabloAST * inner_target = generateWithIfHierarchy(inner, set, lo, hi, inner_block);
50            // If this range is empty, just skip creating the if block
51            if (LLVM_UNLIKELY(isa<Zeroes>(inner_target))) {
52                continue;
53            }
54            Assign * matches = inner_block.createAssign("m", inner_target);
55            builder.createIf(ifTestCompiler(lo, hi, builder), {matches}, inner_block);
56            target = builder.createOr(target, matches);
57        }
58    }
59
60    return target;
61}
62
63/** ------------------------------------------------------------------------------------------------------------- *
64 * @brief generateCharClassSubDefs
65 * @param ifRangeList
66 ** ------------------------------------------------------------------------------------------------------------- */
67PabloAST * UCDCompiler::generateSubRanges(const UnicodeSet & set, const codepoint_t lo, const codepoint_t hi, PabloBuilder & builder, PabloAST * target) {
68    const auto range = rangeIntersect(set, lo, hi);
69    // Divide by UTF-8 length, separating out E0, ED, F0 and F4 ranges
70    const std::array<interval_t, 9> ranges =
71        {{{0, 0x7F}, {0x80, 0x7FF}, {0x800, 0xFFF}, {0x1000, 0xD7FF}, {0xD800, 0xDFFF},
72         {0xE000, 0xFFFF}, {0x10000, 0x3FFFF}, {0x40000, 0xFFFFF}, {0x100000, 0x10FFFF}}};
73    for (auto r : ranges) {
74        const auto subrange = rangeIntersect(range, lo_codepoint(r), hi_codepoint(r));
75        target = sequenceGenerator(std::move(subrange), 1, builder, target, nullptr);
76    }
77    return target;
78}
79
80/** ------------------------------------------------------------------------------------------------------------- *
81 * @brief sequenceGenerator
82 * @param ifRangeList
83 *
84 *
85 * Generate remaining code to match UTF-8 code sequences within the codepoint set cpset, assuming that the code
86 * matching the sequences up to byte number byte_no have been generated.
87 ** ------------------------------------------------------------------------------------------------------------- */
88PabloAST * UCDCompiler::sequenceGenerator(const RangeList && ranges, const unsigned byte_no, PabloBuilder & builder, PabloAST * target, PabloAST * prefix) {
89
90    if (LLVM_LIKELY(!ranges.empty())) {
91
92        codepoint_t lo, hi;
93        std::tie(lo, hi) = ranges[0];
94
95        const auto min = UTF8_Encoder::length(lo_codepoint(ranges.front()));
96        const auto max = UTF8_Encoder::length(hi_codepoint(ranges.back()));
97
98        if (min != max) {
99            const auto mid = UTF8_Encoder::maxCodePoint(min);
100            target = sequenceGenerator(std::move(rangeIntersect(ranges, lo, mid)), byte_no, builder, target, prefix);
101            target = sequenceGenerator(std::move(rangeIntersect(ranges, mid + 1, hi)), byte_no, builder, target, prefix);
102        }
103        else if (min == byte_no) {
104            // We have a single byte remaining to match for all code points in this CC.
105            // Use the byte class compiler to generate matches for these codepoints.
106            const auto bytes = byteDefinitions(ranges, byte_no);
107            PabloAST * var = mCharacterClassCompiler.compileCC(makeCC(bytes), builder);
108            if (byte_no > 1) {
109                var = builder.createAnd(var, builder.createAdvance(makePrefix(lo, byte_no, builder, prefix), 1));
110            }
111            target = builder.createOr(target, var);
112        }
113        else {
114            for (auto rg : ranges) {
115                codepoint_t lo, hi;
116                std::tie(lo, hi) = rg;
117                const auto lo_byte = UTF8_Encoder::encodingByte(lo, byte_no);
118                const auto hi_byte = UTF8_Encoder::encodingByte(hi, byte_no);
119                if (lo_byte != hi_byte) {
120                    if (!UTF8_Encoder::isLowCodePointAfterByte(lo, byte_no)) {
121                        const codepoint_t mid = lo | ((1 << (6 * (min - byte_no))) - 1);
122                        target = sequenceGenerator(lo, mid, byte_no, builder, target, prefix);
123                        target = sequenceGenerator(mid + 1, hi, byte_no, builder, target, prefix);
124                    }
125                    else if (!UTF8_Encoder::isHighCodePointAfterByte(hi, byte_no)) {
126                        const codepoint_t mid = hi & ~((1 << (6 * (min - byte_no))) - 1);
127                        target = sequenceGenerator(lo, mid - 1, byte_no, builder, target, prefix);
128                        target = sequenceGenerator(mid, hi, byte_no, builder, target, prefix);
129                    }
130                    else { // we have a prefix group of type (a)
131                        PabloAST * var = mCharacterClassCompiler.compileCC(makeCC(lo_byte, hi_byte), builder);
132                        if (byte_no > 1) {
133                            var = builder.createAnd(builder.createAdvance(prefix, 1), var);
134                        }
135                        for (unsigned i = byte_no; i != UTF8_Encoder::length(lo); ++i) {
136                            var = builder.createAnd(mSuffixVar, builder.createAdvance(var, 1));
137                        }
138                        target = builder.createOr(target, var);
139                    }
140                }
141                else { // lbyte == hbyte
142                    PabloAST * var = mCharacterClassCompiler.compileCC(makeCC(lo_byte, hi_byte), builder);
143                    if (byte_no > 1) {
144                        var = builder.createAnd(builder.createAdvance(prefix ? prefix : var, 1), var);
145                    }
146                    if (byte_no < UTF8_Encoder::length(lo)) {
147                        target = sequenceGenerator(lo, hi, byte_no + 1, builder, target, var);
148                    }
149                }
150            }
151        }
152    }
153    return target;
154}
155
156/** ------------------------------------------------------------------------------------------------------------- *
157 * @brief sequenceGenerator
158 ** ------------------------------------------------------------------------------------------------------------- */
159inline PabloAST * UCDCompiler::sequenceGenerator(const codepoint_t lo, const codepoint_t hi, const unsigned byte_no, PabloBuilder & builder, PabloAST * target, PabloAST * prefix) {
160    return sequenceGenerator({{ lo, hi }}, byte_no, builder, target, prefix);
161}
162
163/** ------------------------------------------------------------------------------------------------------------- *
164 * @brief ifTestCompiler
165 ** ------------------------------------------------------------------------------------------------------------- */
166inline PabloAST * UCDCompiler::ifTestCompiler(const codepoint_t lo, const codepoint_t hi, PabloBuilder & builder) {
167    return ifTestCompiler(lo, hi, 1, builder, builder.createOnes());
168}
169
170/** ------------------------------------------------------------------------------------------------------------- *
171 * @brief ifTestCompiler
172 ** ------------------------------------------------------------------------------------------------------------- */
173PabloAST * UCDCompiler::ifTestCompiler(const codepoint_t lo, const codepoint_t hi, const unsigned byte_no, PabloBuilder & builder, PabloAST * target) {
174
175    codepoint_t lo_byte = UTF8_Encoder::encodingByte(lo, byte_no);
176    codepoint_t hi_byte = UTF8_Encoder::encodingByte(hi, byte_no);
177    const bool at_lo_boundary = (lo == 0 || UTF8_Encoder::encodingByte(lo - 1, byte_no) != lo_byte);
178    const bool at_hi_boundary = (hi == 0x10FFFF || UTF8_Encoder::encodingByte(hi + 1, byte_no) != hi_byte);
179
180    if (at_lo_boundary && at_hi_boundary) {
181        if (lo_byte != hi_byte) {
182            if (lo == 0x80) lo_byte = 0xC0;
183            if (hi == 0x10FFFF) hi_byte = 0xFF;
184        }
185        PabloAST * cc = mCharacterClassCompiler.compileCC(makeCC(lo_byte, hi_byte), builder);
186        target = builder.createAnd(cc, target);
187    }
188    else if (lo_byte == hi_byte) {
189        PabloAST * cc = mCharacterClassCompiler.compileCC(makeCC(lo_byte, hi_byte), builder);
190        target = builder.createAnd(cc, target);
191        target = builder.createAdvance(target, 1);
192        target = ifTestCompiler(lo, hi, byte_no + 1, builder, target);
193    }
194    else if (!at_hi_boundary) {
195        const auto mid = UTF8_Encoder::minCodePointWithCommonBytes(hi, byte_no);
196        PabloAST * e1 = ifTestCompiler(lo, mid - 1, byte_no, builder, target);
197        PabloAST * e2 = ifTestCompiler(mid, hi, byte_no, builder, target);
198        target = builder.createOr(e1, e2);
199    }
200    else {
201        const auto mid = UTF8_Encoder::maxCodePointWithCommonBytes(lo, byte_no);
202        PabloAST * e1 = ifTestCompiler(lo, mid, byte_no, builder, target);
203        PabloAST * e2 = ifTestCompiler(mid + 1, hi, byte_no, builder, target);
204        target = builder.createOr(e1, e2);
205    }
206    return target;
207}
208
209/** ------------------------------------------------------------------------------------------------------------- *
210 * @brief definePrecedingPrefix
211 * @param ifRangeList
212 *
213 *
214 * Ensure the sequence of preceding bytes is defined, up to, but not including the given byte_no
215 ** ------------------------------------------------------------------------------------------------------------- */
216PabloAST * UCDCompiler::makePrefix(const codepoint_t cp, const unsigned byte_no, PabloBuilder & builder, PabloAST * prefix) {
217    assert (byte_no >= 1 && byte_no <= 4);
218    assert (byte_no == 1 || prefix != nullptr);
219    for (unsigned i = 1; i != byte_no; ++i) {
220        const CC * const cc = makeCC(UTF8_Encoder::encodingByte(cp, i));
221        PabloAST * var = mCharacterClassCompiler.compileCC(cc, builder);
222        if (i > 1) {
223            var = builder.createAnd(var, builder.createAdvance(prefix, 1));
224        }
225        prefix = var;
226    }
227    return prefix;
228}
229
230/** ------------------------------------------------------------------------------------------------------------- *
231 * @brief definePrecedingPrefix
232 * @param ifRangeList
233 *
234 *
235 * Ensure the sequence of preceding bytes is defined, up to, but not including the given byte_no
236 ** ------------------------------------------------------------------------------------------------------------- */
237UCDCompiler::RangeList UCDCompiler::byteDefinitions(const RangeList & list, const unsigned byte_no) {
238    RangeList result;
239    result.reserve(list.size());
240    for (const auto & i : list) {
241        result.emplace_back(UTF8_Encoder::encodingByte(lo_codepoint(i), byte_no), UTF8_Encoder::encodingByte(hi_codepoint(i), byte_no));
242    }
243    return result;
244}
245
246/** ------------------------------------------------------------------------------------------------------------- *
247 * @brief rangeIntersect
248 * @param list
249 * @param lo
250 * @param hi
251 ** ------------------------------------------------------------------------------------------------------------- */
252template <typename RangeListOrUnicodeSet>
253UCDCompiler::RangeList UCDCompiler::rangeIntersect(const RangeListOrUnicodeSet & list, const codepoint_t lo, const codepoint_t hi) {
254    RangeList result;
255    for (const auto i : list) {
256        if ((lo_codepoint(i) <= hi) && (hi_codepoint(i) >= lo)) {
257            result.emplace_back(std::max(lo, lo_codepoint(i)), std::min(hi, hi_codepoint(i)));
258        }
259    }
260    return result;
261}
262
263/** ------------------------------------------------------------------------------------------------------------- *
264 * @brief rangeGaps
265 * @param cc
266 * @param lo
267 * @param hi
268 ** ------------------------------------------------------------------------------------------------------------- */
269UCDCompiler::RangeList UCDCompiler::rangeGaps(const RangeList & list, const codepoint_t lo, const codepoint_t hi) {
270    RangeList gaps;
271    if (LLVM_LIKELY(lo < hi)) {
272        if (LLVM_UNLIKELY(list.empty())) {
273            gaps.emplace_back(lo, hi);
274        }
275        else {
276            codepoint_t cp = lo;
277            for (const auto & i : list) {
278                if (hi_codepoint(i) < cp) {
279                    continue;
280                }
281                else if (lo_codepoint(i) > cp) {
282                    gaps.emplace_back(cp, lo_codepoint(i) - 1);
283                }
284                else if (hi_codepoint(i) >= hi) {
285                    continue;
286                }
287                cp = hi_codepoint(i) + 1;
288            }
289        }
290    }
291    return gaps;
292}
293
294/** ------------------------------------------------------------------------------------------------------------- *
295 * @brief outerRanges
296 * @param list
297 ** ------------------------------------------------------------------------------------------------------------- */
298UCDCompiler::RangeList UCDCompiler::outerRanges(const RangeList & list) {
299    RangeList ranges;
300    if (LLVM_LIKELY(list.size() > 0)) {
301        auto i = list.cbegin();
302        for (auto j = i + 1; j != list.cend(); ++j) {
303            if (hi_codepoint(*j) > hi_codepoint(*i)) {
304                ranges.emplace_back(lo_codepoint(*i), hi_codepoint(*i));
305                i = j;
306            }
307        }
308        if (LLVM_LIKELY(i != list.end())) {
309            ranges.emplace_back(lo_codepoint(*i), hi_codepoint(*i));
310        }
311    }
312    return ranges;
313}
314
315/** ------------------------------------------------------------------------------------------------------------- *
316 * @brief innerRanges
317 * @param list
318 ** ------------------------------------------------------------------------------------------------------------- */
319UCDCompiler::RangeList UCDCompiler::innerRanges(const RangeList & list) {
320    RangeList ranges;
321    if (LLVM_LIKELY(list.size() > 0)) {
322        for (auto i = list.cbegin(), j = i + 1; j != list.cend(); ++j) {
323            if (hi_codepoint(*j) <= hi_codepoint(*i)) {
324                ranges.emplace_back(lo_codepoint(*j), hi_codepoint(*j));
325            }
326            else {
327                i = j;
328            }
329        }
330    }
331    return ranges;
332}
333
334/** ------------------------------------------------------------------------------------------------------------- *
335 * @brief generateWithDefaultIfHierarchy
336 * @param set the unicode set to generate
337 * @param the entry block to the function we're filling
338 * @return the output stream with a 1-bit in any position of a character in the unicode set
339 ** ------------------------------------------------------------------------------------------------------------- */
340PabloAST * UCDCompiler::generateWithDefaultIfHierarchy(const UnicodeSet & set, PabloBuilder & entry) {
341
342    const RangeList defaultIfHierachy = {
343        // Non-ASCII
344        {0x80, 0x10FFFF},
345        // Two-byte sequences
346        {0x80, 0x7FF},
347        {0x100, 0x3FF},
348        // 0100..017F; Latin Extended-A
349        // 0180..024F; Latin Extended-B
350        // 0250..02AF; IPA Extensions
351        // 02B0..02FF; Spacing Modifier Letters
352        {0x100, 0x2FF}, {0x100, 0x24F}, {0x100, 0x17F}, {0x180, 0x24F}, {0x250, 0x2AF}, {0x2B0, 0x2FF},
353        // 0300..036F; Combining Diacritical Marks
354        // 0370..03FF; Greek and Coptic
355        {0x300, 0x36F}, {0x370, 0x3FF},
356        // 0400..04FF; Cyrillic
357        // 0500..052F; Cyrillic Supplement
358        // 0530..058F; Armenian
359        // 0590..05FF; Hebrew
360        // 0600..06FF; Arabic
361        {0x400, 0x5FF}, {0x400, 0x4FF}, {0x500, 0x058F}, {0x500, 0x52F}, {0x530, 0x58F}, {0x590, 0x5FF}, {0x600, 0x6FF},
362        // 0700..074F; Syriac
363        // 0750..077F; Arabic Supplement
364        // 0780..07BF; Thaana
365        // 07C0..07FF; NKo
366        {0x700, 0x77F}, {0x700, 0x74F}, {0x750, 0x77F}, {0x780, 0x7FF}, {0x780, 0x7BF}, {0x7C0, 0x7FF},
367        // Three-byte sequences
368        {0x800, 0xFFFF}, {0x800, 0x4DFF}, {0x800, 0x1FFF}, {0x800, 0x0FFF},
369        // 0800..083F; Samaritan
370        // 0840..085F; Mandaic
371        // 08A0..08FF; Arabic Extended-A
372        // 0900..097F; Devanagari
373        // 0980..09FF; Bengali
374        // 0A00..0A7F; Gurmukhi
375        // 0A80..0AFF; Gujarati
376        // 0B00..0B7F; Oriya
377        // 0B80..0BFF; Tamil
378        // 0C00..0C7F; Telugu
379        // 0C80..0CFF; Kannada
380        // 0D00..0D7F; Malayalam
381        // 0D80..0DFF; Sinhala
382        // 0E00..0E7F; Thai
383        // 0E80..0EFF; Lao
384        // 0F00..0FFF; Tibetan
385        {0x1000, 0x1FFF},
386        // 1000..109F; Myanmar
387        // 10A0..10FF; Georgian
388        // 1100..11FF; Hangul Jamo
389        // 1200..137F; Ethiopic
390        // 1380..139F; Ethiopic Supplement
391        // 13A0..13FF; Cherokee
392        // 1400..167F; Unified Canadian Aboriginal Syllabics
393        // 1680..169F; Ogham
394        // 16A0..16FF; Runic
395        // 1700..171F; Tagalog
396        // 1720..173F; Hanunoo
397        // 1740..175F; Buhid
398        // 1760..177F; Tagbanwa
399        // 1780..17FF; Khmer
400        // 1800..18AF; Mongolian
401        // 18B0..18FF; Unified Canadian Aboriginal Syllabics Extended
402        // 1900..194F; Limbu
403        // 1950..197F; Tai Le
404        // 1980..19DF; New Tai Lue
405        // 19E0..19FF; Khmer Symbols
406        // 1A00..1A1F; Buginese
407        // 1A20..1AAF; Tai Tham
408        // 1AB0..1AFF; Combining Diacritical Marks Extended
409        // 1B00..1B7F; Balinese
410        // 1B80..1BBF; Sundanese
411        // 1BC0..1BFF; Batak
412        // 1C00..1C4F; Lepcha
413        // 1C50..1C7F; Ol Chiki
414        // 1CC0..1CCF; Sundanese Supplement
415        // 1CD0..1CFF; Vedic Extensions
416        // 1D00..1D7F; Phonetic Extensions
417        // 1D80..1DBF; Phonetic Extensions Supplement
418        // 1DC0..1DFF; Combining Diacritical Marks Supplement
419        // 1E00..1EFF; Latin Extended Additional
420        // 1F00..1FFF; Greek Extended
421        {0x2000, 0x4DFF}, {0x2000, 0x2FFF},
422        {0x3000, 0x4DFF},
423        {0x4E00, 0x9FFF},
424        // 4E00..9FFF; CJK Unified Ideographs
425        {0xA000, 0xFFFF},
426
427        {0x10000, 0x10FFFF}};
428
429    return generateWithIfHierarchy(defaultIfHierachy, set, entry);
430}
431
432/** ------------------------------------------------------------------------------------------------------------- *
433 * @brief generateWithoutIfHierarchy
434 * @param set the unicode set to generate
435 * @param the entry block to the function we're filling
436 * @return the output stream with a 1-bit in any position of a character in the unicode set
437 ** ------------------------------------------------------------------------------------------------------------- */
438PabloAST * UCDCompiler::generateWithoutIfHierarchy(const UnicodeSet & set, PabloBuilder & entry) {
439
440    const RangeList defaultIfHierachy = {{0x10000, 0x10FFFF}};
441
442    return generateWithIfHierarchy(defaultIfHierachy, set, entry);
443}
444
445/** ------------------------------------------------------------------------------------------------------------- *
446 * @brief constructor
447 ** ------------------------------------------------------------------------------------------------------------- */
448UCDCompiler::UCDCompiler(cc::CC_Compiler & ccCompiler)
449: mCharacterClassCompiler(ccCompiler)
450, mSuffixVar(nullptr) { }
451
452}
Note: See TracBrowser for help on using the repository browser.