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

Last change on this file since 5843 was 5843, checked in by cameron, 15 months ago

CC Compiler refactoring step

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