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

Last change on this file since 5172 was 5172, checked in by lindanl, 3 years ago

Add Edit Distance App

  • Property svn:executable set to *
File size: 4.4 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
45std::vector<Assign *> optimizer(std::string patt, std::vector<pablo::Var *> basisBits, std::vector<std::vector<Assign*>>  & e, int i, PabloAST * cond, PabloBuilder & pb, int dist, int stepSize){
46    PabloBuilder it = PabloBuilder::Create(pb);
47    std::vector<Assign *> var_list;
48    for(int n = 0; n < stepSize; n++){
49        // PabloAST * name = cast<Name>(seq->at(i))->getCompiled();
50        int pi = (patt[i] >> 1) & 0x3;
51        PabloAST * name = basisBits[pi];       
52       
53        e[i][0] = it.createAssign(make_e(i,0), it.createAnd(it.createAdvance(e[i-1][0],1), name));
54        for(int j = 1; j <= dist; j++){ 
55            auto tmp1 = it.createAssign("tmp1", it.createAnd(it.createAdvance(e[i-1][j],1), name));
56            auto tmp2 = it.createAssign("tmp2", it.createAnd(it.createAdvance(e[i-1][j-1],1), it.createNot(name)));
57            auto tmp3 = it.createAssign("tmp3", it.createOr(it.createAdvance(e[i][j-1],1), e[i-1][j-1]));
58            e[i][j] = it.createAssign(make_e(i,j), it.createOr(it.createOr(tmp1,tmp2),tmp3));
59        }
60       
61        i++;
62        if(i >= patt.length()) break;
63    } 
64    i--; 
65
66    if(i < patt.length()-1){ 
67        var_list = optimizer(patt, basisBits, e, i+1, e[i][dist], it, dist, stepSize);
68    }
69
70    for(int j = 0; j <= dist; j++){ 
71        var_list.push_back(e[i][j]);
72    }
73
74    std::vector<Assign *> new_var_list = var_list;
75    pb.createIf(cond, std::move(var_list), it);
76    return new_var_list;
77}
78
79void Pattern_Compiler::compile(std::vector<std::string> patts, PabloBuilder & pb, std::vector<pablo::Var *> basisBits, int dist, int optPosition, int stepSize) {
80    std::vector<std::vector<Assign*>> e(patts[0].length()*2, std::vector<Assign*>(dist+1));
81    std::vector<PabloAST*> E(dist+1);
82    int i = 0;
83    int pi = 0;
84
85    for(int d=0; d<=dist; d++){
86        E[d] = pb.createZeroes();
87    }
88
89    for(int r=0; r< patts.size(); r++){
90        std::string patt = patts[r];
91        pi = (patt[0] >> 1) & 0x3;
92        PabloAST * name = basisBits[pi];
93
94        e[0][0] = pb.createAssign(make_e(0, 0), name);
95        for(int j = 1; j <= dist; j++){
96          e[0][j] = pb.createAssign(make_e(0, j), pb.createOnes());
97        }
98
99        i++;
100        while (i < patt.length()) {
101            pi = (patt[i] >> 1) & 0x3;
102            name = basisBits[pi];
103
104            e[i][0] = pb.createAssign(make_e(i,0), pb.createAnd(pb.createAdvance(e[i-1][0],1), name));
105            for(int j = 1; j <= dist; j++){     
106                auto tmp1 = pb.createAssign("tmp1", pb.createAnd(pb.createAdvance(e[i-1][j],1), name));
107                auto tmp2 = pb.createAssign("tmp2", pb.createAnd(pb.createAdvance(e[i-1][j-1],1), pb.createNot(name)));
108                auto tmp3 = pb.createAssign("tmp3", pb.createOr(pb.createAdvance(e[i][j-1],1), e[i-1][j-1]));
109                e[i][j] = pb.createAssign(make_e(i,j), pb.createOr(pb.createOr(tmp1,tmp2),tmp3));
110            }
111           
112            i++;
113            if(i >= optPosition) break;
114        }
115
116        //Optimize from optPosition
117        if(i >= optPosition){
118            optimizer(patt, basisBits, e, i, e[i-1][dist], pb, dist, stepSize);
119        }
120
121        E[0] = pb.createOr(E[0], e[patt.length()-1][0]);
122        for(int d=1; d<=dist; d++){
123            E[d] = pb.createOr(E[d], pb.createAnd(e[patt.length()-1][d], pb.createNot(e[patt.length()-1][d-1])));
124        }
125
126        i = 0;
127    }
128    for(int d=0; d<=dist; d++){
129        mFunction.setResult(d, pb.createAssign("E" + std::to_string(d), E[d]));
130    }
131}
132
133}//end of re namespace
Note: See TracBrowser for help on using the repository browser.