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

Last change on this file since 6127 was 6127, checked in by xwa163, 10 months ago
  1. Improve RE_Compiler for multiplexing
  2. Use faster approach for LineBreakStream? generating in LZParabix_grep
File size: 11.7 KB
Line 
1/*
2 *  Copyright (c) 2018 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 <cc/alphabet.h>
9#include <pablo/codegenstate.h>
10#include <pablo/boolean.h>
11#include <pablo/pe_zeroes.h>
12#include <pablo/pe_ones.h>
13#include <pablo/pe_infile.h>
14#include <pablo/builder.hpp>
15#include <pablo/pablo_kernel.h>
16#include <llvm/IR/DerivedTypes.h>
17#include <llvm/Support/ErrorHandling.h>
18#include <llvm/Support/raw_ostream.h>
19
20using namespace re;
21using namespace pablo;
22using namespace llvm;
23
24namespace cc {
25    CC_Compiler::CC_Compiler(pablo::PabloBlock * scope)
26    : mBuilder(scope) {
27    }
28
29Parabix_CC_Compiler::Parabix_CC_Compiler(pablo::PabloBlock * scope, std::vector<pablo::PabloAST *> basisBitSet, cc::BitNumbering basisSetNumbering, bool fakeBasisBits)
30: CC_Compiler(scope)
31, mEncodingBits(basisBitSet.size())
32, mBasisSetNumbering(basisSetNumbering)
33, mBasisBit(basisBitSet)
34, mFakeBasisBits(fakeBasisBits) {
35    mEncodingMask = (static_cast<unsigned>(1) << mEncodingBits) - static_cast<unsigned>(1);
36}
37
38PabloAST * Parabix_CC_Compiler::compileCC(const std::string & canonicalName, const CC *cc, PabloBlock & block) {
39    PabloAST * const var = charset_expr(cc, block);
40    if (LLVM_LIKELY(isa<Statement>(var))) {
41        cast<Statement>(var)->setName(block.makeName(canonicalName));
42    }
43    return var;
44}
45
46PabloAST * Parabix_CC_Compiler::compileCC(const std::string & canonicalName, const CC *cc, PabloBuilder & builder) {
47    PabloAST * const var = charset_expr(cc, builder);
48    if (LLVM_LIKELY(isa<Statement>(var))) {
49        cast<Statement>(var)->setName(builder.makeName(canonicalName));
50    }
51    return var;
52}
53   
54template<typename PabloBlockOrBuilder>
55PabloAST * Parabix_CC_Compiler::charset_expr(const CC * cc, PabloBlockOrBuilder & pb) {
56    if (cc->empty()) {
57        return pb.createZeroes();
58    }
59    if (cc->size() > 2) {
60        bool combine = true;
61        for (const interval_t & i : *cc) {
62            if (lo_codepoint(i) != hi_codepoint(i)) {
63                combine = false;
64                break;
65            }
66        }
67        if (combine) {
68            auto i = cc->begin(), e = cc->end();
69            for (auto j = i; ++j != e; i = j) {
70                if ((lo_codepoint(i) + 2) != lo_codepoint(j)) {
71                    combine  = false;
72                    break;
73                }
74            }
75            if (combine) {
76                codepoint_t lo = lo_codepoint(cc->front());
77                codepoint_t hi = lo_codepoint(cc->back());
78                lo &= (mEncodingMask - 1);
79                hi |= (mEncodingMask ^ (mEncodingMask - 1));
80                PabloAST * expr = make_range(lo, hi, pb);
81                PabloAST * bit0 = getBasisVar(0, pb);
82                if ((lo & 1) == 0) {
83                    bit0 = pb.createNot(bit0);
84                }
85                return pb.createAnd(expr, bit0);
86            }
87        }
88    }
89    PabloAST * expr = nullptr;
90    for (const interval_t & i : *cc) {
91        PabloAST * temp = char_or_range_expr(lo_codepoint(i), hi_codepoint(i), pb);
92        expr = (expr == nullptr) ? temp : pb.createOr(expr, temp);
93    }
94    return pb.createInFile(expr);
95   
96}
97
98template<typename PabloBlockOrBuilder>
99PabloAST * Parabix_CC_Compiler::bit_pattern_expr(const unsigned pattern, unsigned selected_bits, PabloBlockOrBuilder & pb) {
100    if (LLVM_UNLIKELY(selected_bits == 0)) {
101        return pb.createOnes();
102    } else {
103        std::vector<PabloAST*> terms;
104        for (unsigned i = 0; selected_bits; ++i) {
105            unsigned test_bit = static_cast<unsigned>(1) << i;
106            PabloAST * term = pb.createOnes();
107            if (selected_bits & test_bit) {
108                term = getBasisVar(i, pb);
109                if ((pattern & test_bit) == 0) {
110                    term = pb.createNot(term);
111                }
112                selected_bits ^= test_bit;
113            }
114            terms.push_back(term);
115        }
116        if (terms.size() > 1) {
117            //Reduce the list so that all of the expressions are contained within a single expression.
118            std::vector<PabloAST*> temp;
119            temp.reserve(terms.size());
120            do {
121                for (unsigned i = 0; i < (terms.size() / 2); i++) {
122                    temp.push_back(pb.createAnd(terms[2 * i], terms[(2 * i) + 1]));
123                }
124                if (terms.size() % 2 == 1) {
125                    temp.push_back(terms.back());
126                }
127                terms.swap(temp);
128                temp.clear();
129            }
130            while (terms.size() > 1);
131        }
132        assert (terms.size() == 1);
133        return terms.front();
134    }
135}
136
137template<typename PabloBlockOrBuilder>
138inline PabloAST * Parabix_CC_Compiler::char_test_expr(const codepoint_t ch, PabloBlockOrBuilder &pb) {
139    return bit_pattern_expr(ch, mEncodingMask, pb);
140}
141
142template<typename PabloBlockOrBuilder>
143PabloAST * Parabix_CC_Compiler::make_range(const codepoint_t n1, const codepoint_t n2, PabloBlockOrBuilder & pb) {
144    codepoint_t diff_count = 0;
145
146    for (codepoint_t diff_bits = n1 ^ n2; diff_bits; diff_count++, diff_bits >>= 1);
147
148    if ((n2 < n1) || (diff_count > mEncodingBits)) {
149        llvm::report_fatal_error("Bad Range: [" + std::to_string(n1) + "," +
150                                 std::to_string(n2) + "] for " +
151                                 std::to_string(mEncodingBits) + "-bit encoding");
152    }
153
154    const codepoint_t mask0 = (static_cast<codepoint_t>(1) << diff_count) - 1;
155
156    PabloAST * common = bit_pattern_expr(n1 & ~mask0, mEncodingMask ^ mask0, pb);
157
158    if (diff_count == 0) return common;
159
160    const codepoint_t mask1 = (static_cast<codepoint_t>(1) << (diff_count - 1)) - 1;
161
162    PabloAST* lo_test = GE_Range(diff_count - 1, n1 & mask1, pb);
163    PabloAST* hi_test = LE_Range(diff_count - 1, n2 & mask1, pb);
164
165    return pb.createAnd(common, pb.createSel(getBasisVar(diff_count - 1, pb), hi_test, lo_test));
166}
167
168template<typename PabloBlockOrBuilder>
169PabloAST * Parabix_CC_Compiler::GE_Range(const unsigned N, const unsigned n, PabloBlockOrBuilder &pb) {
170    if (N == 0) {
171        return pb.createOnes(); //Return a true literal.
172    }
173    else if (((N % 2) == 0) && ((n >> (N - 2)) == 0)) {
174        return pb.createOr(pb.createOr(getBasisVar(N - 1, pb), getBasisVar(N - 2, pb)), GE_Range(N - 2, n, pb));
175    }
176    else if (((N % 2) == 0) && ((n >> (N - 2)) == 3)) {
177        return pb.createAnd(pb.createAnd(getBasisVar(N - 1, pb), getBasisVar(N - 2, pb)), GE_Range(N - 2, n - (3 << (N - 2)), pb));
178    }
179    else if (N >= 1)
180    {
181        int hi_bit = n & (1 << (N - 1));
182        int lo_bits = n - hi_bit;
183        PabloAST * lo_range = GE_Range(N - 1, lo_bits, pb);
184        if (hi_bit == 0)
185        {
186            /*
187              If the hi_bit of n is not set, then whenever the corresponding bit
188              is set in the target, the target will certaily be >=.  Otherwise,
189              the value of GE_range(N-1), lo_range) is required.
190            */
191            return pb.createOr(getBasisVar(N - 1, pb), lo_range);
192        }
193        else
194        {
195            /*
196              If the hi_bit of n is set, then the corresponding bit must be set
197              in the target for >= and GE_range(N-1, lo_bits) must also be true.
198            */
199            return pb.createAnd(getBasisVar(N - 1, pb), lo_range);
200        }
201    }
202    throw std::runtime_error("Unexpected input given to ge_range: " + std::to_string(N) + ", " + std::to_string(n));
203}
204
205template<typename PabloBlockOrBuilder>
206PabloAST * Parabix_CC_Compiler::LE_Range(const unsigned N, const unsigned n, PabloBlockOrBuilder & pb) {
207    /*
208      If an N-bit pattern is all ones, then it is always true that any n-bit value is LE this pattern.
209      Handling this as a special case avoids an overflow issue with n+1 requiring more than N bits.
210    */
211    if ((n + 1) == (1UL << N)) {
212        return pb.createOnes(); //True.
213    } else {
214        return pb.createNot(GE_Range(N, n + 1, pb));
215    }
216}
217
218template<typename PabloBlockOrBuilder>
219inline PabloAST * Parabix_CC_Compiler::char_or_range_expr(const codepoint_t lo, const codepoint_t hi, PabloBlockOrBuilder &pb) {
220    if (lo == hi) {
221        return char_test_expr(lo, pb);
222    } else if (lo < hi) {
223        return make_range(lo, hi, pb);
224    }
225    llvm::report_fatal_error(std::string("Invalid Character Set Range: [") + std::to_string(lo) + "," + std::to_string(hi) + "]");
226}
227
228template<typename PabloBlockOrBuilder>
229inline PabloAST * Parabix_CC_Compiler::getBasisVar(const unsigned i, PabloBlockOrBuilder & pb) const {
230    if (mFakeBasisBits) {
231        return pb.createZeroes();
232    } else {
233        assert (i < mEncodingBits);
234        if (mBasisSetNumbering == cc::BitNumbering::BigEndian)
235            return mBasisBit[mEncodingBits - i - 1];
236        else return mBasisBit[i];
237    }
238}
239
240   
241PabloAST * compileCCfromCodeUnitStream(const CC * cc, PabloAST * codeUnitStream, PabloBuilder & pb) {
242    const Alphabet * a = cc->getAlphabet();
243    if (!isa<CodeUnitAlphabet>(a)) {
244        llvm::report_fatal_error("compileCCfromCodeUnitStream must be applied to a CC with a CodeUnitAlphabet");
245    }
246    unsigned codeUnitWidth = cast<const CodeUnitAlphabet>(a)->getCodeUnitBitWidth();
247    unsigned topBit = 1 << (codeUnitWidth - 1);
248    unsigned maxCodeVal = (topBit - 1) | topBit;
249    //
250    // Optimization if there are isolated codepoints that are not in the set.
251    UCD::UnicodeSet negatedIsolates = (~(*cc)).isolates();
252    UCD::UnicodeSet withNegatedIsolates = (*cc + negatedIsolates);
253    PabloAST * ccStrm = pb.createZeroes();
254    for (const auto & interval : withNegatedIsolates) {
255        unsigned lo = re::lo_codepoint(interval);
256        unsigned hi = re::hi_codepoint(interval);
257        if (lo == hi) {
258            PabloAST * testVal = pb.createRepeat(codeUnitWidth, lo);
259            ccStrm = pb.createOr(ccStrm, pb.createEquals(codeUnitStream, testVal));
260        } else if (lo == 0) {
261            if (hi == maxCodeVal) {
262                // All code units
263                ccStrm = pb.createOnes();
264            } else {
265                PabloAST * testVal = pb.createRepeat(codeUnitWidth, hi+1);
266                ccStrm = pb.createOr(ccStrm, pb.createLessThan(codeUnitStream, testVal));
267            }
268        } else if (hi == maxCodeVal) {
269            PabloAST * testVal = pb.createRepeat(codeUnitWidth, lo);
270            ccStrm = pb.createOr(ccStrm, pb.createNot(pb.createLessThan(codeUnitStream, testVal)));
271        } else {
272            PabloAST * testVal_lo = pb.createRepeat(codeUnitWidth, lo);
273            PabloAST * testVal_hi = pb.createRepeat(codeUnitWidth, hi + 1);
274            ccStrm = pb.createOr(ccStrm, pb.createAnd(pb.createNot(pb.createLessThan(codeUnitStream, testVal_lo)),
275                                                      pb.createLessThan(codeUnitStream, testVal_hi)));
276        }
277    }
278    if (!negatedIsolates.empty()) {
279        PabloAST * toExclude = pb.createZeroes();
280        for (const auto & interval : negatedIsolates) {
281            PabloAST * testVal = pb.createRepeat(codeUnitWidth, re::lo_codepoint(interval));
282            toExclude = pb.createOr(toExclude, pb.createEquals(codeUnitStream, testVal));
283        }
284        ccStrm = pb.createAnd(ccStrm, pb.createNot(toExclude));
285    }
286    return pb.createInFile(ccStrm);
287}
288   
289Direct_CC_Compiler::Direct_CC_Compiler(pablo::PabloBlock * scope, pablo::PabloAST * codeUnitStream)
290: CC_Compiler(scope)
291, mCodeUnitStream(codeUnitStream) {
292}
293
294pablo::PabloAST * Direct_CC_Compiler::compileCC(const std::string & name, const re::CC *cc, pablo::PabloBlock & block) {
295    PabloBuilder pb(&block);
296    return compileCC(name, cc, pb);
297}
298
299pablo::PabloAST * Direct_CC_Compiler::compileCC(const std::string & name, const re::CC *cc, pablo::PabloBuilder & b) {
300    return compileCCfromCodeUnitStream(cc, mCodeUnitStream, b);
301}
302
303} // end of namespace cc
Note: See TracBrowser for help on using the repository browser.