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

Last change on this file since 5023 was 5023, checked in by cameron, 3 years ago

pablo.InFile? initial support

File size: 8.2 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"
[4132]8#include "utf_encoding.h"
[4194]9
10//Pablo Expressions
[4199]11#include <re/re_alt.h>
12#include <re/re_cc.h>
13#include <re/re_seq.h>
14#include <re/re_rep.h>
[4210]15#include <re/re_name.h>
[4337]16#include <re/re_diff.h>
17#include <re/re_intersect.h>
[4406]18#include <re/re_assertion.h>
[4602]19#include <pablo/codegenstate.h>
20#include <pablo/builder.hpp>
[4657]21#include <pablo/function.h>
[4187]22#include <stdexcept>
[4132]23
[4194]24using namespace re;
[4198]25using namespace pablo;
[4194]26
[4198]27namespace cc {
28
[4657]29CC_Compiler::CC_Compiler(PabloFunction & function, const Encoding & encoding, const std::string prefix)
30: mBuilder(function.getEntryBlock())
[4215]31, mBasisBit(encoding.getBits())
[4657]32, mEncoding(encoding) {
33    for (unsigned i = 0; i != encoding.getBits(); i++) {
34        Var * var = mBuilder.createVar(prefix + std::to_string(i));
[4680]35        function.setParameter(i, var);
[4681]36        mBasisBit[i] = var;
[3850]37    }
[4132]38}
[3850]39
[4612]40Assign * CC_Compiler::compileCC(const std::string && canonicalName, const CC *cc, PabloBlock & block) {
41    return block.createAssign(std::move(canonicalName), charset_expr(cc, block));
[4334]42}
43
[4612]44Assign * CC_Compiler::compileCC(const std::string && canonicalName, const CC *cc, PabloBuilder & builder) {
45    return builder.createAssign(std::move(canonicalName), charset_expr(cc, builder));
[4357]46}
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    }
[5023]53    bool includes_codepoint_zero = lo_codepoint(cc->begin()) == 0;
[4242]54    if (cc->size() > 2) {
55        bool combine = true;
[4614]56        for (const interval_t & i : *cc) {
57            if (lo_codepoint(i) != hi_codepoint(i)) {
[4242]58                combine = false;
59                break;
60            }
[3850]61        }
[4242]62        if (combine) {
[4812]63            auto i = cc->begin(), e = cc->end();
64            for (auto j = i; ++j != e; i = j) {
[4614]65                if ((lo_codepoint(i) + 2) != lo_codepoint(j)) {
[4242]66                    combine  = false;
67                    break;
68                }
69            }
70            if (combine) {
[4614]71                codepoint_t lo = lo_codepoint(cc->front());
72                codepoint_t hi = lo_codepoint(cc->back());
[4612]73                const codepoint_t mask = mEncoding.getMask();
[4242]74                lo &= (mask - 1);
75                hi |= (mask ^ (mask - 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    }
[5023]90    if (includes_codepoint_zero) {
91        return pb.createInFile(expr);
92    }
93    else {
94        return expr;
95    }
[4211]96}
97
[4612]98template<typename PabloBlockOrBuilder>
[4797]99PabloAST * CC_Compiler::bit_pattern_expr(const unsigned pattern, unsigned selected_bits, PabloBlockOrBuilder & pb) {
100    if (LLVM_UNLIKELY(selected_bits == 0)) {
101        return PabloBlock::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 = PabloBlock::createOnes();
107            if (selected_bits & test_bit) {
108                term = getBasisVar(i);
109                if ((pattern & test_bit) == 0) {
110                    term = pb.createNot(term);
111                }
112                selected_bits ^= test_bit;
[3850]113            }
[4797]114            terms.push_back(term);
[3850]115        }
[4797]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();
[4511]129            }
[4797]130            while (terms.size() > 1);
[3850]131        }
[4797]132        assert (terms.size() == 1);
133        return terms.front();
[3850]134    }
135}
136
[4612]137template<typename PabloBlockOrBuilder>
138inline PabloAST * CC_Compiler::char_test_expr(const codepoint_t ch, PabloBlockOrBuilder &pb) {
[4357]139    return bit_pattern_expr(ch, mEncoding.getMask(), pb);
[3850]140}
141
[4612]142template<typename PabloBlockOrBuilder>
143PabloAST * CC_Compiler::make_range(const codepoint_t n1, const codepoint_t n2, PabloBlockOrBuilder & pb) {
144    codepoint_t diff_count = 0;
[3850]145
[4612]146    for (codepoint_t diff_bits = n1 ^ n2; diff_bits; diff_count++, diff_bits >>= 1);
[3850]147
148    if ((n2 < n1) || (diff_count > mEncoding.getBits()))
149    {
[4286]150        throw std::runtime_error("Bad Range: [" + std::to_string(n1) + "," + std::to_string(n2) + "]");
[3850]151    }
152
[4612]153    const codepoint_t mask0 = (static_cast<codepoint_t>(1) << diff_count) - 1;
[3850]154
[4357]155    PabloAST * common = bit_pattern_expr(n1 & ~mask0, mEncoding.getMask() ^ mask0, pb);
[4194]156
[3850]157    if (diff_count == 0) return common;
158
[4612]159    const codepoint_t mask1 = (static_cast<codepoint_t>(1) << (diff_count - 1)) - 1;
[3850]160
[4357]161    PabloAST* lo_test = GE_Range(diff_count - 1, n1 & mask1, pb);
162    PabloAST* hi_test = LE_Range(diff_count - 1, n2 & mask1, pb);
[3850]163
[4357]164    return pb.createAnd(common, pb.createSel(getBasisVar(diff_count - 1), hi_test, lo_test));
[3850]165}
166
[4612]167template<typename PabloBlockOrBuilder>
168PabloAST * CC_Compiler::GE_Range(const unsigned N, const unsigned n, PabloBlockOrBuilder &pb) {
[4249]169    if (N == 0) {
[4357]170        return pb.createOnes(); //Return a true literal.
[3850]171    }
[4249]172    else if (((N % 2) == 0) && ((n >> (N - 2)) == 0)) {
[4357]173        return pb.createOr(pb.createOr(getBasisVar(N - 1), getBasisVar(N - 2)), GE_Range(N - 2, n, pb));
[3850]174    }
[4249]175    else if (((N % 2) == 0) && ((n >> (N - 2)) == 3)) {
[4357]176        return pb.createAnd(pb.createAnd(getBasisVar(N - 1), getBasisVar(N - 2)), GE_Range(N - 2, n - (3 << (N - 2)), pb));
[3850]177    }
[4200]178    else if (N >= 1)
[3850]179    {
[4220]180        int hi_bit = n & (1 << (N - 1));
[3850]181        int lo_bits = n - hi_bit;
[4357]182        PabloAST * lo_range = GE_Range(N - 1, lo_bits, pb);
[3850]183        if (hi_bit == 0)
184        {
185            /*
186              If the hi_bit of n is not set, then whenever the corresponding bit
[4890]187              is set in the target, the target will certaily be >=.  Otherwise,
[3850]188              the value of GE_range(N-1), lo_range) is required.
189            */
[4357]190            return pb.createOr(getBasisVar(N - 1), lo_range);
[3850]191        }
192        else
193        {
194            /*
195              If the hi_bit of n is set, then the corresponding bit must be set
196              in the target for >= and GE_range(N-1, lo_bits) must also be true.
197            */
[4357]198            return pb.createAnd(getBasisVar(N - 1), lo_range);
[3850]199        }
200    }
[4200]201    throw std::runtime_error("Unexpected input given to ge_range: " + std::to_string(N) + ", " + std::to_string(n));
[3850]202}
203
[4612]204template<typename PabloBlockOrBuilder>
205PabloAST * CC_Compiler::LE_Range(const unsigned N, const unsigned n, PabloBlockOrBuilder &pb)
[3850]206{
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    */
[4187]211    if ((n + 1) == (1 << N)) {
[4357]212        return pb.createOnes(); //True.
[3850]213    }
[4187]214    else {
[4357]215        return pb.createNot(GE_Range(N, n + 1, pb));
[3850]216    }
217}
218
[4612]219template<typename PabloBlockOrBuilder>
220inline PabloAST * CC_Compiler::char_or_range_expr(const codepoint_t lo, const codepoint_t hi, PabloBlockOrBuilder &pb) {
[4187]221    if (lo == hi) {
[4357]222        return char_test_expr(lo, pb);
[3850]223    }
[4187]224    else if (lo < hi) {
[4357]225        return make_range(lo, hi, pb);
[4187]226    }
227    throw std::runtime_error(std::string("Invalid Character Set Range: [") + std::to_string(lo) + "," + std::to_string(hi) + "]");
[3850]228}
229
[4242]230inline Var * CC_Compiler::getBasisVar(const int i) const {
[4797]231    assert (i >= 0 && i < mEncoding.getBits());
[4681]232    return mBasisBit[mEncoding.getBits() - i - 1];
[4242]233}
234
[4198]235} // end of namespace cc
Note: See TracBrowser for help on using the repository browser.