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

Last change on this file since 5646 was 5646, checked in by nmedfort, 2 years ago

Minor clean up. Bug fix for object cache when the same cached kernel is used twice in a single run. Improvement to RE Minimizer.

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