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

Last change on this file since 5160 was 5160, checked in by nmedfort, 3 years ago

Initial work for incorporating Types into Pablo AST.

File size: 8.7 KB
Line 
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"
8
9//Pablo Expressions
10#include <re/re_alt.h>
11#include <re/re_cc.h>
12#include <re/re_seq.h>
13#include <re/re_rep.h>
14#include <re/re_name.h>
15#include <re/re_diff.h>
16#include <re/re_intersect.h>
17#include <re/re_assertion.h>
18#include <pablo/codegenstate.h>
19#include <pablo/builder.hpp>
20#include <pablo/function.h>
21#include <stdexcept>
22
23using namespace re;
24using namespace pablo;
25
26namespace cc {
27
28CC_Compiler::CC_Compiler(PabloFunction & function, const unsigned encodingBits, const std::string prefix)
29: mBuilder(function.getEntryBlock())
30, mBasisBit(encodingBits)
31, mEncodingBits(encodingBits) {
32    const PabloType * streamType = getPabloType(PabloType::Stream, 1);
33    for (unsigned i = 0; i != mEncodingBits; i++) {
34        Var * var = mBuilder.createVar(prefix + std::to_string(i), streamType);
35        function.setParameter(i, var);
36        mBasisBit[i] = var;
37    }
38    mEncodingMask = (static_cast<unsigned>(1) << encodingBits) - static_cast<unsigned>(1);
39}
40
41Assign * CC_Compiler::compileCC(const std::string && canonicalName, const CC *cc, PabloBlock & block) {
42    return block.createAssign(std::move(canonicalName), charset_expr(cc, block));
43}
44
45Assign * CC_Compiler::compileCC(const std::string && canonicalName, const CC *cc, PabloBuilder & builder) {
46    return builder.createAssign(std::move(canonicalName), charset_expr(cc, builder));
47}
48
49
50   
51template<typename PabloBlockOrBuilder>
52PabloAST * CC_Compiler::charset_expr(const CC * cc, PabloBlockOrBuilder & pb) {
53    if (cc->empty()) {
54        return pb.createZeroes();
55    }
56    if (cc->size() > 2) {
57        bool combine = true;
58        for (const interval_t & i : *cc) {
59            if (lo_codepoint(i) != hi_codepoint(i)) {
60                combine = false;
61                break;
62            }
63        }
64        if (combine) {
65            auto i = cc->begin(), e = cc->end();
66            for (auto j = i; ++j != e; i = j) {
67                if ((lo_codepoint(i) + 2) != lo_codepoint(j)) {
68                    combine  = false;
69                    break;
70                }
71            }
72            if (combine) {
73                codepoint_t lo = lo_codepoint(cc->front());
74                codepoint_t hi = lo_codepoint(cc->back());
75                lo &= (mEncodingMask - 1);
76                hi |= (mEncodingMask ^ (mEncodingMask - 1));
77                PabloAST * expr = make_range(lo, hi, pb);
78                PabloAST * bit0 = getBasisVar(0);
79                if ((lo & 1) == 0) {
80                    bit0 = pb.createNot(bit0);
81                }
82                return pb.createAnd(expr, bit0);
83            }
84        }
85    }
86    PabloAST * expr = nullptr;
87    for (const interval_t & i : *cc) {
88        PabloAST * temp = char_or_range_expr(lo_codepoint(i), hi_codepoint(i), pb);
89        expr = (expr == nullptr) ? temp : pb.createOr(expr, temp);
90    }
91    return expr;
92   
93}
94
95template<typename PabloBlockOrBuilder>
96PabloAST * CC_Compiler::bit_pattern_expr(const unsigned pattern, unsigned selected_bits, PabloBlockOrBuilder & pb) {
97    if (LLVM_UNLIKELY(selected_bits == 0)) {
98        return pb.createOnes();
99    } else {
100        std::vector<PabloAST*> terms;
101        for (unsigned i = 0; selected_bits; ++i) {
102            unsigned test_bit = static_cast<unsigned>(1) << i;
103            PabloAST * term = pb.createOnes();
104            if (selected_bits & test_bit) {
105                term = getBasisVar(i);
106                if ((pattern & test_bit) == 0) {
107                    term = pb.createNot(term);
108                }
109                selected_bits ^= test_bit;
110            }
111            terms.push_back(term);
112        }
113        if (terms.size() > 1) {
114            //Reduce the list so that all of the expressions are contained within a single expression.
115            std::vector<PabloAST*> temp;
116            temp.reserve(terms.size());
117            do {
118                for (unsigned i = 0; i < (terms.size() / 2); i++) {
119                    temp.push_back(pb.createAnd(terms[2 * i], terms[(2 * i) + 1]));
120                }
121                if (terms.size() % 2 == 1) {
122                    temp.push_back(terms.back());
123                }
124                terms.swap(temp);
125                temp.clear();
126            }
127            while (terms.size() > 1);
128        }
129        assert (terms.size() == 1);
130        return terms.front();
131    }
132}
133
134template<typename PabloBlockOrBuilder>
135inline PabloAST * CC_Compiler::char_test_expr(const codepoint_t ch, PabloBlockOrBuilder &pb) {
136    return bit_pattern_expr(ch, mEncodingMask, pb);
137}
138
139template<typename PabloBlockOrBuilder>
140PabloAST * CC_Compiler::make_range(const codepoint_t n1, const codepoint_t n2, PabloBlockOrBuilder & pb) {
141    codepoint_t diff_count = 0;
142
143    for (codepoint_t diff_bits = n1 ^ n2; diff_bits; diff_count++, diff_bits >>= 1);
144
145    if ((n2 < n1) || (diff_count > mEncodingBits))
146    {
147        throw std::runtime_error("Bad Range: [" + std::to_string(n1) + "," + std::to_string(n2) + "]");
148    }
149
150    const codepoint_t mask0 = (static_cast<codepoint_t>(1) << diff_count) - 1;
151
152    PabloAST * common = bit_pattern_expr(n1 & ~mask0, mEncodingMask ^ mask0, pb);
153
154    if (diff_count == 0) return common;
155
156    const codepoint_t mask1 = (static_cast<codepoint_t>(1) << (diff_count - 1)) - 1;
157
158    PabloAST* lo_test = GE_Range(diff_count - 1, n1 & mask1, pb);
159    PabloAST* hi_test = LE_Range(diff_count - 1, n2 & mask1, pb);
160
161    return pb.createAnd(common, pb.createSel(getBasisVar(diff_count - 1), hi_test, lo_test));
162}
163
164template<typename PabloBlockOrBuilder>
165PabloAST * CC_Compiler::GE_Range(const unsigned N, const unsigned n, PabloBlockOrBuilder &pb) {
166    if (N == 0) {
167        return pb.createOnes(); //Return a true literal.
168    }
169    else if (((N % 2) == 0) && ((n >> (N - 2)) == 0)) {
170        return pb.createOr(pb.createOr(getBasisVar(N - 1), getBasisVar(N - 2)), GE_Range(N - 2, n, pb));
171    }
172    else if (((N % 2) == 0) && ((n >> (N - 2)) == 3)) {
173        return pb.createAnd(pb.createAnd(getBasisVar(N - 1), getBasisVar(N - 2)), GE_Range(N - 2, n - (3 << (N - 2)), pb));
174    }
175    else if (N >= 1)
176    {
177        int hi_bit = n & (1 << (N - 1));
178        int lo_bits = n - hi_bit;
179        PabloAST * lo_range = GE_Range(N - 1, lo_bits, pb);
180        if (hi_bit == 0)
181        {
182            /*
183              If the hi_bit of n is not set, then whenever the corresponding bit
184              is set in the target, the target will certaily be >=.  Otherwise,
185              the value of GE_range(N-1), lo_range) is required.
186            */
187            return pb.createOr(getBasisVar(N - 1), lo_range);
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            */
195            return pb.createAnd(getBasisVar(N - 1), lo_range);
196        }
197    }
198    throw std::runtime_error("Unexpected input given to ge_range: " + std::to_string(N) + ", " + std::to_string(n));
199}
200
201template<typename PabloBlockOrBuilder>
202PabloAST * CC_Compiler::LE_Range(const unsigned N, const unsigned n, PabloBlockOrBuilder &pb)
203{
204    /*
205      If an N-bit pattern is all ones, then it is always true that any n-bit value is LE this pattern.
206      Handling this as a special case avoids an overflow issue with n+1 requiring more than N bits.
207    */
208    if ((n + 1) == (1UL << N)) {
209        return pb.createOnes(); //True.
210    }
211    else {
212        return pb.createNot(GE_Range(N, n + 1, pb));
213    }
214}
215
216template<typename PabloBlockOrBuilder>
217inline PabloAST * CC_Compiler::char_or_range_expr(const codepoint_t lo, const codepoint_t hi, PabloBlockOrBuilder &pb) {
218    if (lo == hi) {
219        return char_test_expr(lo, pb);
220    }
221    else if (lo < hi) {
222        return make_range(lo, hi, pb);
223    }
224    throw std::runtime_error(std::string("Invalid Character Set Range: [") + std::to_string(lo) + "," + std::to_string(hi) + "]");
225}
226
227inline Var * CC_Compiler::getBasisVar(const unsigned i) const {
228    assert (i < mEncodingBits);
229    return mBasisBit[mEncodingBits - i - 1];
230}
231   
232pablo::PabloFunction * ParabixCharacterClassFunction(std::string ccSetName, std::vector<re::CC *> charClasses, unsigned basisBitsCount) {
233       
234    pablo::PabloFunction * cc_function = pablo::PabloFunction::Create(ccSetName + "_fn", basisBitsCount, charClasses.size());
235    CC_Compiler ccc(* cc_function, basisBitsCount);
236   
237    pablo::PabloBuilder pBuilder(ccc.getBuilder().getPabloBlock(), ccc.getBuilder());
238    const std::vector<pablo::Var *> bits = ccc.getBasisBits();
239   
240    for (unsigned i = 0; i < charClasses.size(); i++) {
241        cc_function->setResult(i, ccc.compileCC(charClasses[i]));
242    }
243    return cc_function;
244}
245
246} // end of namespace cc
Note: See TracBrowser for help on using the repository browser.