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

Last change on this file since 5646 was 5646, checked in by nmedfort, 22 months 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
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
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]);
28    }
29    mEncodingMask = (static_cast<unsigned>(1) << mEncodingBits) - static_cast<unsigned>(1);
30}
31
32PabloAST * CC_Compiler::compileCC(const std::string & canonicalName, const CC *cc, PabloBlock & block) {   
33    PabloAST * const var = charset_expr(cc, block);
34    if (LLVM_LIKELY(isa<Statement>(var))) {
35        cast<Statement>(var)->setName(block.makeName(canonicalName));
36    }
37    return var;
38}
39
40PabloAST * CC_Compiler::compileCC(const std::string & canonicalName, const CC *cc, PabloBuilder & builder) {
41    PabloAST * const var = charset_expr(cc, builder);
42    if (LLVM_LIKELY(isa<Statement>(var))) {
43        cast<Statement>(var)->setName(builder.makeName(canonicalName));
44    }
45    return var;
46}
47   
48template<typename PabloBlockOrBuilder>
49PabloAST * CC_Compiler::charset_expr(const CC * cc, PabloBlockOrBuilder & pb) {
50    if (cc->empty()) {
51        return pb.createZeroes();
52    }
53    if (cc->size() > 2) {
54        bool combine = true;
55        for (const interval_t & i : *cc) {
56            if (lo_codepoint(i) != hi_codepoint(i)) {
57                combine = false;
58                break;
59            }
60        }
61        if (combine) {
62            auto i = cc->begin(), e = cc->end();
63            for (auto j = i; ++j != e; i = j) {
64                if ((lo_codepoint(i) + 2) != lo_codepoint(j)) {
65                    combine  = false;
66                    break;
67                }
68            }
69            if (combine) {
70                codepoint_t lo = lo_codepoint(cc->front());
71                codepoint_t hi = lo_codepoint(cc->back());
72                lo &= (mEncodingMask - 1);
73                hi |= (mEncodingMask ^ (mEncodingMask - 1));
74                PabloAST * expr = make_range(lo, hi, pb);
75                PabloAST * bit0 = getBasisVar(0);
76                if ((lo & 1) == 0) {
77                    bit0 = pb.createNot(bit0);
78                }
79                return pb.createAnd(expr, bit0);
80            }
81        }
82    }
83    PabloAST * expr = nullptr;
84    for (const interval_t & i : *cc) {
85        PabloAST * temp = char_or_range_expr(lo_codepoint(i), hi_codepoint(i), pb);
86        expr = (expr == nullptr) ? temp : pb.createOr(expr, temp);
87    }
88    return expr;
89   
90}
91
92template<typename PabloBlockOrBuilder>
93PabloAST * CC_Compiler::bit_pattern_expr(const unsigned pattern, unsigned selected_bits, PabloBlockOrBuilder & pb) {
94    if (LLVM_UNLIKELY(selected_bits == 0)) {
95        return pb.createOnes();
96    } else {
97        std::vector<PabloAST*> terms;
98        for (unsigned i = 0; selected_bits; ++i) {
99            unsigned test_bit = static_cast<unsigned>(1) << i;
100            PabloAST * term = pb.createOnes();
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;
107            }
108            terms.push_back(term);
109        }
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();
123            }
124            while (terms.size() > 1);
125        }
126        assert (terms.size() == 1);
127        return terms.front();
128    }
129}
130
131template<typename PabloBlockOrBuilder>
132inline PabloAST * CC_Compiler::char_test_expr(const codepoint_t ch, PabloBlockOrBuilder &pb) {
133    return bit_pattern_expr(ch, mEncodingMask, pb);
134}
135
136template<typename PabloBlockOrBuilder>
137PabloAST * CC_Compiler::make_range(const codepoint_t n1, const codepoint_t n2, PabloBlockOrBuilder & pb) {
138    codepoint_t diff_count = 0;
139
140    for (codepoint_t diff_bits = n1 ^ n2; diff_bits; diff_count++, diff_bits >>= 1);
141
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");
146    }
147
148    const codepoint_t mask0 = (static_cast<codepoint_t>(1) << diff_count) - 1;
149
150    PabloAST * common = bit_pattern_expr(n1 & ~mask0, mEncodingMask ^ mask0, pb);
151
152    if (diff_count == 0) return common;
153
154    const codepoint_t mask1 = (static_cast<codepoint_t>(1) << (diff_count - 1)) - 1;
155
156    PabloAST* lo_test = GE_Range(diff_count - 1, n1 & mask1, pb);
157    PabloAST* hi_test = LE_Range(diff_count - 1, n2 & mask1, pb);
158
159    return pb.createAnd(common, pb.createSel(getBasisVar(diff_count - 1), hi_test, lo_test));
160}
161
162template<typename PabloBlockOrBuilder>
163PabloAST * CC_Compiler::GE_Range(const unsigned N, const unsigned n, PabloBlockOrBuilder &pb) {
164    if (N == 0) {
165        return pb.createOnes(); //Return a true literal.
166    }
167    else if (((N % 2) == 0) && ((n >> (N - 2)) == 0)) {
168        return pb.createOr(pb.createOr(getBasisVar(N - 1), getBasisVar(N - 2)), GE_Range(N - 2, n, pb));
169    }
170    else if (((N % 2) == 0) && ((n >> (N - 2)) == 3)) {
171        return pb.createAnd(pb.createAnd(getBasisVar(N - 1), getBasisVar(N - 2)), GE_Range(N - 2, n - (3 << (N - 2)), pb));
172    }
173    else if (N >= 1)
174    {
175        int hi_bit = n & (1 << (N - 1));
176        int lo_bits = n - hi_bit;
177        PabloAST * lo_range = GE_Range(N - 1, lo_bits, pb);
178        if (hi_bit == 0)
179        {
180            /*
181              If the hi_bit of n is not set, then whenever the corresponding bit
182              is set in the target, the target will certaily be >=.  Otherwise,
183              the value of GE_range(N-1), lo_range) is required.
184            */
185            return pb.createOr(getBasisVar(N - 1), lo_range);
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            */
193            return pb.createAnd(getBasisVar(N - 1), lo_range);
194        }
195    }
196    throw std::runtime_error("Unexpected input given to ge_range: " + std::to_string(N) + ", " + std::to_string(n));
197}
198
199template<typename PabloBlockOrBuilder>
200PabloAST * CC_Compiler::LE_Range(const unsigned N, const unsigned n, PabloBlockOrBuilder & pb) {
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    */
205    if ((n + 1) == (1UL << N)) {
206        return pb.createOnes(); //True.
207    } else {
208        return pb.createNot(GE_Range(N, n + 1, pb));
209    }
210}
211
212template<typename PabloBlockOrBuilder>
213inline PabloAST * CC_Compiler::char_or_range_expr(const codepoint_t lo, const codepoint_t hi, PabloBlockOrBuilder &pb) {
214    if (lo == hi) {
215        return char_test_expr(lo, pb);
216    } else if (lo < hi) {
217        return make_range(lo, hi, pb);
218    }
219    throw std::runtime_error(std::string("Invalid Character Set Range: [") + std::to_string(lo) + "," + std::to_string(hi) + "]");
220}
221
222inline PabloAST * CC_Compiler::getBasisVar(const unsigned i) const {
223    assert (i < mEncodingBits);
224    const unsigned index = mEncodingBits - i - 1; assert (index < mEncodingBits);
225    assert (mBasisBit[index]);
226    return mBasisBit[index];
227}
228
229} // end of namespace cc
Note: See TracBrowser for help on using the repository browser.