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

Last change on this file since 5828 was 5828, checked in by nmedfort, 13 months ago

Pablo support for byte comparisions; LineFeed? kernel processes byte streams directly. Some clean up of PabloBuilder? functionality.

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