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

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

Fix for SCX and updated property objects.

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