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

Last change on this file since 5235 was 5230, checked in by nmedfort, 3 years ago

Multi-threading support for PabloAST / PabloCompiler?. Requires unique LLVM Context / Module for each thread.

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