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