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

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

Ability to set input/output signatures for Pablo functions in the constructor

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