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

Last change on this file since 5630 was 5620, checked in by nmedfort, 22 months ago

Bug fixes for multigrep mode. Optional PabloKernel? branch hit counter added. Minor optimizations.

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
15
16using namespace re;
17using namespace pablo;
18using namespace llvm;
19
20namespace cc {
21
22//    CC_Compiler::CC_Compiler(PabloKernel * kernel, const unsigned encodingBits, const std::string prefix)
23//    : mBuilder(kernel->getEntryBlock())
24//    , mEncodingBits(encodingBits)
25//    , mBasisBit(encodingBits) {
26       
27//        // TODO: basisBits should be defined prior and only retrieved here.
28//        Var * const basisBits = kernel->addInput(prefix, kernel->getStreamSetTy(encodingBits));
29//        for (unsigned i = 0; i != mEncodingBits; i++) {
30//            mBasisBit[i] = mBuilder.createExtract(basisBits, mBuilder.getInteger(i)); assert (mBasisBit[i]);
31//        }
32//        mEncodingMask = (static_cast<unsigned>(1) << encodingBits) - static_cast<unsigned>(1);
33//    }
34   
35   
36CC_Compiler::CC_Compiler(pablo::PabloKernel * kernel, pablo::Var * basisBits)
37: mBuilder(kernel->getEntryBlock())
38, mEncodingBits(basisBits->getType()->getArrayNumElements())
39, mBasisBit(mEncodingBits) {
40    for (unsigned i = 0; i != mEncodingBits; i++) {
41        mBasisBit[i] = mBuilder.createExtract(basisBits, mBuilder.getInteger(i)); assert (mBasisBit[i]);
42    }
43    mEncodingMask = (static_cast<unsigned>(1) << mEncodingBits) - static_cast<unsigned>(1);
44}
45
46PabloAST * CC_Compiler::compileCC(const std::string & canonicalName, const CC *cc, PabloBlock & block) {   
47    PabloAST * const var = charset_expr(cc, block);
48    if (LLVM_LIKELY(isa<Statement>(var))) {
49        cast<Statement>(var)->setName(block.makeName(canonicalName));
50    }
51    return var;
52}
53
54PabloAST * CC_Compiler::compileCC(const std::string & canonicalName, const CC *cc, PabloBuilder & builder) {
55    PabloAST * const var = charset_expr(cc, builder);
56    if (LLVM_LIKELY(isa<Statement>(var))) {
57        cast<Statement>(var)->setName(builder.makeName(canonicalName));
58    }
59    return var;
60}
61   
62template<typename PabloBlockOrBuilder>
63PabloAST * CC_Compiler::charset_expr(const CC * cc, PabloBlockOrBuilder & pb) {
64    if (cc->empty()) {
65        return pb.createZeroes();
66    }
67    if (cc->size() > 2) {
68        bool combine = true;
69        for (const interval_t & i : *cc) {
70            if (lo_codepoint(i) != hi_codepoint(i)) {
71                combine = false;
72                break;
73            }
74        }
75        if (combine) {
76            auto i = cc->begin(), e = cc->end();
77            for (auto j = i; ++j != e; i = j) {
78                if ((lo_codepoint(i) + 2) != lo_codepoint(j)) {
79                    combine  = false;
80                    break;
81                }
82            }
83            if (combine) {
84                codepoint_t lo = lo_codepoint(cc->front());
85                codepoint_t hi = lo_codepoint(cc->back());
86                lo &= (mEncodingMask - 1);
87                hi |= (mEncodingMask ^ (mEncodingMask - 1));
88                PabloAST * expr = make_range(lo, hi, pb);
89                PabloAST * bit0 = getBasisVar(0);
90                if ((lo & 1) == 0) {
91                    bit0 = pb.createNot(bit0);
92                }
93                return pb.createAnd(expr, bit0);
94            }
95        }
96    }
97    PabloAST * expr = nullptr;
98    for (const interval_t & i : *cc) {
99        PabloAST * temp = char_or_range_expr(lo_codepoint(i), hi_codepoint(i), pb);
100        expr = (expr == nullptr) ? temp : pb.createOr(expr, temp);
101    }
102    return expr;
103   
104}
105
106template<typename PabloBlockOrBuilder>
107PabloAST * CC_Compiler::bit_pattern_expr(const unsigned pattern, unsigned selected_bits, PabloBlockOrBuilder & pb) {
108    if (LLVM_UNLIKELY(selected_bits == 0)) {
109        return pb.createOnes();
110    } else {
111        std::vector<PabloAST*> terms;
112        for (unsigned i = 0; selected_bits; ++i) {
113            unsigned test_bit = static_cast<unsigned>(1) << i;
114            PabloAST * term = pb.createOnes();
115            if (selected_bits & test_bit) {
116                term = getBasisVar(i);
117                if ((pattern & test_bit) == 0) {
118                    term = pb.createNot(term);
119                }
120                selected_bits ^= test_bit;
121            }
122            terms.push_back(term);
123        }
124        if (terms.size() > 1) {
125            //Reduce the list so that all of the expressions are contained within a single expression.
126            std::vector<PabloAST*> temp;
127            temp.reserve(terms.size());
128            do {
129                for (unsigned i = 0; i < (terms.size() / 2); i++) {
130                    temp.push_back(pb.createAnd(terms[2 * i], terms[(2 * i) + 1]));
131                }
132                if (terms.size() % 2 == 1) {
133                    temp.push_back(terms.back());
134                }
135                terms.swap(temp);
136                temp.clear();
137            }
138            while (terms.size() > 1);
139        }
140        assert (terms.size() == 1);
141        return terms.front();
142    }
143}
144
145template<typename PabloBlockOrBuilder>
146inline PabloAST * CC_Compiler::char_test_expr(const codepoint_t ch, PabloBlockOrBuilder &pb) {
147    return bit_pattern_expr(ch, mEncodingMask, pb);
148}
149
150template<typename PabloBlockOrBuilder>
151PabloAST * CC_Compiler::make_range(const codepoint_t n1, const codepoint_t n2, PabloBlockOrBuilder & pb) {
152    codepoint_t diff_count = 0;
153
154    for (codepoint_t diff_bits = n1 ^ n2; diff_bits; diff_count++, diff_bits >>= 1);
155
156    if ((n2 < n1) || (diff_count > mEncodingBits)) {
157        throw std::runtime_error("Bad Range: [" + std::to_string(n1) + "," +
158                                 std::to_string(n2) + "] for " +
159                                 std::to_string(mEncodingBits) + "-bit encoding");
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.