source: icGREP/icgrep-devel/icgrep/editd/pattern_compiler.cpp @ 5215

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

Initial work on adding types to PabloAST and mutable Var objects.

  • Property svn:executable set to *
File size: 4.1 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 "pattern_compiler.h"
8//Regular Expressions
9#include <re/re_name.h>
10#include <re/re_any.h>
11#include <re/re_start.h>
12#include <re/re_end.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_diff.h>
18#include <re/re_intersect.h>
19#include <re/re_assertion.h>
20#include <re/re_analysis.h>
21#include <pablo/codegenstate.h>
22#include <pablo/function.h>
23
24#include <assert.h>
25#include <stdexcept>
26#include <iostream>
27
28#include "llvm/Support/CommandLine.h"
29
30using namespace pablo;
31
32namespace re {
33
34
35Pattern_Compiler::Pattern_Compiler(pablo::PabloFunction & function)
36: mFunction(function)
37{
38
39}
40
41
42inline std::string make_e(int i, int j) {return ("e_"+std::to_string(i)+"_"+std::to_string(j));}
43
44
45void optimizer(const std::string & patt, PabloAST * basisBits[], std::vector<std::vector<PabloAST *>> & e, unsigned i, PabloAST * cond, PabloBuilder & main, PabloBuilder & pb, int dist, int stepSize){
46    PabloBuilder it = PabloBuilder::Create(pb);
47
48    Zeroes * zeroes = pb.createZeroes();
49
50    for(int n = 0; n < stepSize; n++){
51
52        PabloAST * name = basisBits[(patt[i] >> 1) & 0x3];
53       
54        e[i][0] = it.createAnd(it.createAdvance(e[i - 1][0], 1), name, make_e(i, 0));
55        for(int j = 1; j <= dist; j++){
56            auto tmp1 = it.createAnd(it.createAdvance(e[i-1][j],1), name);
57            auto tmp2 = it.createAnd(it.createAdvance(e[i-1][j-1],1), it.createNot(name));
58            auto tmp3 = it.createOr(it.createAdvance(e[i][j-1],1), e[i-1][j-1]);
59            e[i][j] = it.createOr(it.createOr(tmp1, tmp2), tmp3, make_e(i, j));
60        }
61       
62        i++;
63        if (i >= patt.length()) break;
64    } 
65
66    if (i < patt.length()) {
67       optimizer(patt, basisBits, e, i, e[i - 1][dist], main, it, dist, stepSize);
68    } else {
69        const auto i = patt.length() - 1;
70        for(int j = 0; j <= dist; j++){
71            auto eij = main.createVar("m" + std::to_string(j), zeroes);
72            it.createAssign(eij, e[i][j]);
73            e[i][j] = eij;
74        }
75    }
76
77    pb.createIf(cond, it);
78}
79
80void Pattern_Compiler::compile(const std::vector<std::string> & patts, PabloBuilder & pb, PabloAST * basisBits[], int dist, unsigned optPosition, int stepSize) {
81    std::vector<std::vector<PabloAST *>> e(patts[0].length() * 2, std::vector<PabloAST *>(dist+1));
82    std::vector<PabloAST*> E(dist + 1);
83
84    for(int d=0; d<=dist; d++){
85        E[d] = pb.createZeroes();
86    }
87
88    for(unsigned r = 0; r < patts.size(); r++){
89        const std::string & patt = patts[r];
90
91        PabloAST * name = basisBits[(patt[0] >> 1) & 0x3];
92
93        e[0][0] = name;
94        for(int j = 1; j <= dist; j++){
95          e[0][j] = pb.createOnes();
96        }
97
98        unsigned i = 1;
99        while (i < patt.length() && i < optPosition) {
100
101            name = basisBits[(patt[i] >> 1) & 0x3];
102
103            e[i][0] = pb.createAnd(pb.createAdvance(e[i-1][0], 1), name, make_e(i, 0));
104            for(int j = 1; j <= dist; j++){     
105                auto tmp1 = pb.createAnd(pb.createAdvance(e[i-1][j],1), name);
106                auto tmp2 = pb.createAnd(pb.createAdvance(e[i-1][j-1],1), pb.createNot(name));
107                auto tmp3 = pb.createOr(pb.createAdvance(e[i][j-1],1), e[i-1][j-1]);
108                e[i][j] = pb.createOr(pb.createOr(tmp1,tmp2),tmp3, make_e(i, j));
109            }
110           
111            i++;
112        }
113
114        //Optimize from optPosition
115        if (i >= optPosition) {
116            optimizer(patt, basisBits, e, i, e[i-1][dist], pb, pb, dist, stepSize);
117        }
118
119        E[0] = pb.createOr(E[0], e[patt.length() - 1][0]);
120        for(int d=1; d<=dist; d++){
121            E[d] = pb.createOr(E[d], pb.createAnd(e[patt.length()-1][d], pb.createNot(e[patt.length()-1][d-1])));
122        }
123
124    }
125
126    Var * output = mFunction.addResult("E", getStreamTy(1, dist + 1));
127
128    for(int d=0; d<=dist; d++){
129        pb.createAssign(pb.createExtract(output, d), E[d]);
130        // mFunction.setResult(d, pb.createAssign("E" + std::to_string(d), E[d]));
131    }
132}
133
134}//end of re namespace
Note: See TracBrowser for help on using the repository browser.