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

Last change on this file since 4415 was 4410, checked in by nmedfort, 5 years ago

Changes to support 3-operand form for all instructions. CSE disabled but partially redundant now.

File size: 11.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 "utf_encoding.h"
9
10//Pablo Expressions
11#include <pablo/codegenstate.h>
12#include <pablo/pe_metadata.h>
13#include <re/re_alt.h>
14#include <re/re_cc.h>
15#include <re/re_seq.h>
16#include <re/re_rep.h>
17#include <re/re_name.h>
18#include <re/re_diff.h>
19#include <re/re_intersect.h>
20#include <re/re_assertion.h>
21#include <re/printer_re.h>
22#include <cc/cc_namemap.hpp>
23#include <pablo/printer_pablos.h>
24#include <utility>
25#include <string>
26#include <list>
27#include <map>
28#include <algorithm>
29#include <boost/graph/adjacency_list.hpp>
30#include <cassert>
31#include <stdlib.h>
32#include <stdexcept>
33
34using namespace re;
35using namespace pablo;
36using namespace boost;
37
38namespace cc {
39
40CC_Compiler::CC_Compiler(PabloBlock & cg, const Encoding encoding, const bool annotateVariableConstraints, const std::string basis_pattern)
41: mCG(cg)
42//, mAnnotateVariableConstraints(annotateVariableConstraints)
43, mBasisBit(encoding.getBits())
44, mEncoding(encoding)
45{
46    for (int i = 0; i < mEncoding.getBits(); i++) {
47        mBasisBit[i] = mCG.createVar(basis_pattern + std::to_string(i));
48    }
49}
50
51pablo::Assign * CC_Compiler::compileCC(const re::CC *cc) {
52     return compileCC(cc, mCG); 
53}
54
55pablo::Assign * CC_Compiler::compileCC(const re::CC *cc, pablo::PabloBlock & pb) {
56     return pb.createAssign(cc->canonicalName(ByteClass), charset_expr(cc, pb));
57}
58
59std::vector<Var *> CC_Compiler::getBasisBits(const CC_NameMap & nameMap) {
60    return mBasisBit;
61}
62
63void CC_Compiler::compileByteClasses(RE * re) {
64    if (Alt * alt = dyn_cast<Alt>(re)) {
65        for (auto i = alt->begin(); i != alt->end(); ++i) {
66            compileByteClasses(*i);
67        }
68    }
69    else if (Seq * seq = dyn_cast<Seq>(re)) {
70        for (auto i = seq->begin(); i != seq->end(); ++i) {
71            compileByteClasses(*i);
72        }
73    }
74    else if (Rep * rep = dyn_cast<Rep>(re)) {
75        compileByteClasses(rep->getRE());
76    }
77    else if (Assertion * a = dyn_cast<Assertion>(re)) {
78        compileByteClasses(a->getAsserted());
79    }
80    else if (Diff * diff = dyn_cast<Diff>(re)) {
81        compileByteClasses(diff->getRH());
82        compileByteClasses(diff->getLH());
83    }
84    else if (Intersect * e = dyn_cast<Intersect>(re)) {
85        compileByteClasses(e->getRH());
86        compileByteClasses(e->getLH());
87    }
88    else if (Name * name = dyn_cast<Name>(re)) {
89        RE * d = name->getDefinition();
90        if (d && !isa<CC>(d)) {
91            compileByteClasses(d);
92        }
93        else if (d && isa<CC>(d)) {
94            name->setCompiled(compileCC(cast<CC>(d), mCG));
95        }
96    }
97    else if (isa<CC>(re)) {
98        std::cerr << "Shouldn't get here\n";
99        exit(-1);
100    }
101}
102
103
104
105PabloAST * CC_Compiler::charset_expr(const CC * cc, pablo::PabloBlock & pb) {
106    if (cc->empty()) {
107        return pb.createZeroes();
108    }
109    if (cc->size() > 2) {
110        bool combine = true;
111        for (const CharSetItem & item : *cc) {
112            if (item.lo_codepoint != item.hi_codepoint) {
113                combine = false;
114                break;
115            }
116        }
117        if (combine) {
118            auto i = cc->cbegin();
119            for (auto j = i; ++j != cc->cend(); i = j) {
120                const CharSetItem & curr_item = *i;
121                const CharSetItem & next_item = *j;
122                if ((curr_item.lo_codepoint + 2) != next_item.lo_codepoint) {
123                    combine  = false;
124                    break;
125                }
126            }
127            if (combine) {
128                CodePointType lo = cc->front().lo_codepoint;
129                CodePointType hi = cc->back().lo_codepoint;
130                const CodePointType mask = mEncoding.getMask();
131                lo &= (mask - 1);
132                hi |= (mask ^ (mask - 1));
133                PabloAST * expr = make_range(lo, hi, pb);
134                PabloAST * bit0 = getBasisVar(0);
135                if ((lo & 1) == 0) {
136                    bit0 = pb.createNot(bit0);
137                }
138                return pb.createAnd(expr, bit0);
139            }
140        }
141    }
142    PabloAST * expr = nullptr;
143    for (const CharSetItem & item : *cc) {
144        PabloAST * temp = char_or_range_expr(item.lo_codepoint, item.hi_codepoint, pb);
145        expr = (expr == nullptr) ? temp : pb.createOr(expr, temp);
146    }
147    return expr;
148}
149
150PabloAST * CC_Compiler::bit_pattern_expr(const unsigned pattern, unsigned selected_bits, pablo::PabloBlock & pb)
151{
152    if (selected_bits == 0) {
153        return pb.createOnes();
154    }
155
156    std::vector<PabloAST*> bit_terms;
157    unsigned i = 0;
158
159    while (selected_bits)
160    {
161        unsigned test_bit = 1 << i;
162        if (selected_bits & test_bit)
163        {
164            if ((pattern & test_bit) == 0)
165            {
166                bit_terms.push_back(mCG.createNot(getBasisVar(i)));
167            }
168            else
169            {
170                bit_terms.push_back(getBasisVar(i));
171            }
172        }
173        else
174        {
175            bit_terms.push_back(pb.createOnes());
176        }
177        selected_bits &= ~test_bit;
178        i++;
179    }
180
181    //Reduce the list so that all of the expressions are contained within a single expression.
182    while (bit_terms.size() > 1)
183    {
184        std::vector<PabloAST*> new_terms;
185        for (auto i = 0; i < (bit_terms.size()/2); i++)
186        {
187            new_terms.push_back(pb.createAnd(bit_terms[(2 * i) + 1], bit_terms[2 * i]));
188        }
189        if (bit_terms.size() % 2 == 1)
190        {
191            new_terms.push_back(bit_terms[bit_terms.size() -1]);
192        }
193        bit_terms.swap(new_terms);
194    }
195    return bit_terms[0];
196}
197
198inline PabloAST * CC_Compiler::char_test_expr(const CodePointType ch, pablo::PabloBlock & pb)
199{
200    return bit_pattern_expr(ch, mEncoding.getMask(), pb);
201}
202
203PabloAST * CC_Compiler::make_range(const CodePointType n1, const CodePointType n2, pablo::PabloBlock & pb)
204{
205    CodePointType diff_count = 0;
206
207    for (CodePointType diff_bits = n1 ^ n2; diff_bits; diff_count++, diff_bits >>= 1);
208
209    if ((n2 < n1) || (diff_count > mEncoding.getBits()))
210    {
211        throw std::runtime_error("Bad Range: [" + std::to_string(n1) + "," + std::to_string(n2) + "]");
212    }
213
214    const CodePointType mask0 = (static_cast<CodePointType>(1) << diff_count) - 1;
215
216    PabloAST * common = bit_pattern_expr(n1 & ~mask0, mEncoding.getMask() ^ mask0, pb);
217
218    if (diff_count == 0) return common;
219
220    const CodePointType mask1 = (static_cast<CodePointType>(1) << (diff_count - 1)) - 1;
221
222    PabloAST* lo_test = GE_Range(diff_count - 1, n1 & mask1, pb);
223    PabloAST* hi_test = LE_Range(diff_count - 1, n2 & mask1, pb);
224
225    return pb.createAnd(common, pb.createSel(getBasisVar(diff_count - 1), hi_test, lo_test));
226}
227
228PabloAST * CC_Compiler::GE_Range(const unsigned N, const unsigned n, pablo::PabloBlock & pb) {
229    if (N == 0) {
230        return pb.createOnes(); //Return a true literal.
231    }
232    else if (((N % 2) == 0) && ((n >> (N - 2)) == 0)) {
233        return pb.createOr(pb.createOr(getBasisVar(N - 1), getBasisVar(N - 2)), GE_Range(N - 2, n, pb));
234    }
235    else if (((N % 2) == 0) && ((n >> (N - 2)) == 3)) {
236        return pb.createAnd(pb.createAnd(getBasisVar(N - 1), getBasisVar(N - 2)), GE_Range(N - 2, n - (3 << (N - 2)), pb));
237    }
238    else if (N >= 1)
239    {
240        int hi_bit = n & (1 << (N - 1));
241        int lo_bits = n - hi_bit;
242        PabloAST * lo_range = GE_Range(N - 1, lo_bits, pb);
243        if (hi_bit == 0)
244        {
245            /*
246              If the hi_bit of n is not set, then whenever the corresponding bit
247              is set in the target, the target will certaily be >=.  Oterwise,
248              the value of GE_range(N-1), lo_range) is required.
249            */
250            return pb.createOr(getBasisVar(N - 1), lo_range);
251        }
252        else
253        {
254            /*
255              If the hi_bit of n is set, then the corresponding bit must be set
256              in the target for >= and GE_range(N-1, lo_bits) must also be true.
257            */
258            return pb.createAnd(getBasisVar(N - 1), lo_range);
259        }
260    }
261    throw std::runtime_error("Unexpected input given to ge_range: " + std::to_string(N) + ", " + std::to_string(n));
262}
263
264PabloAST * CC_Compiler::LE_Range(const unsigned N, const unsigned n, pablo::PabloBlock & pb)
265{
266    /*
267      If an N-bit pattern is all ones, then it is always true that any n-bit value is LE this pattern.
268      Handling this as a special case avoids an overflow issue with n+1 requiring more than N bits.
269    */
270    if ((n + 1) == (1 << N)) {
271        return pb.createOnes(); //True.
272    }
273    else {
274        return pb.createNot(GE_Range(N, n + 1, pb));
275    }
276}
277
278inline PabloAST * CC_Compiler::char_or_range_expr(const CodePointType lo, const CodePointType hi, pablo::PabloBlock & pb) {
279    if (lo == hi) {
280        return char_test_expr(lo, pb);
281    }
282    else if (lo < hi) {
283        return make_range(lo, hi, pb);
284    }
285    throw std::runtime_error(std::string("Invalid Character Set Range: [") + std::to_string(lo) + "," + std::to_string(hi) + "]");
286}
287
288inline Var * CC_Compiler::getBasisVar(const int i) const {
289    return mBasisBit[(mEncoding.getBits() - 1) - i];
290}
291
292void CC_Compiler::computeVariableConstraints() {
293    typedef adjacency_list<vecS, vecS, directedS> ConstraintGraph;
294    typedef adjacency_list<vecS, vecS, directedS> SubsetGraph;
295
296    typedef graph_traits<ConstraintGraph>::out_edge_iterator ConstraintEdgeIterator;
297    typedef graph_traits<SubsetGraph>::out_edge_iterator SubsetEdgeIterator;
298
299    const auto n = mVariableVector.size();
300
301    if (n == 0) {
302        return;
303    }
304
305    // Compute the constraint and subset graphs.
306    ConstraintGraph C(n);
307    SubsetGraph S(n);
308
309    for (auto i = 0; i != n; ++i) {
310        const CC * const cc1 = mVariableVector[i].first;
311
312        for (auto j = i + 1; j != n; ++j) {
313            const CC * const cc2 = mVariableVector[j].first;
314            switch(cc1->compare(cc2)) {
315                case CC::SetRelationship::OVERLAPPING:
316                    add_edge(i, j, C);
317                    add_edge(j, i, C);
318                    break;
319                case CC::SetRelationship::SUBSET:
320                    add_edge(i, j, S);
321                    break;
322                case CC::SetRelationship::SUPERSET:
323                    add_edge(j, i, S);
324                    break;
325                default:
326                    /* do nothing; here just to prevent warning */
327                    break;
328            }
329        }
330    }
331
332    // Write out the constraints and subset relationships as metadata
333    for (auto i = 0; i != n; ++i) {
334        std::vector<PabloAST *> constraints;
335        ConstraintEdgeIterator ci, ci_end;
336        for (std::tie(ci, ci_end) = out_edges(i, C); ci != ci_end; ++ci) {
337            constraints.push_back(mVariableVector[target(*ci, C)].second);
338        }
339
340        std::vector<PabloAST *> subsets;
341        SubsetEdgeIterator si, si_end;
342        for (std::tie(si, si_end) = out_edges(i, S); si != si_end; ++si) {
343            subsets.push_back(mVariableVector[target(*si, S)].second);
344        }
345
346        Assign * assign = mVariableVector[i].second;
347        if (!constraints.empty()) {
348            assign->setMetadata("constraints", PMDSet::get(constraints.begin(), constraints.end()));
349        }
350        if (!subsets.empty()) {
351            assign->setMetadata("subsets", PMDSet::get(subsets.begin(), subsets.end()));
352        }
353    }
354}
355
356} // end of namespace cc
Note: See TracBrowser for help on using the repository browser.