source: icGREP/icgrep-devel/icgrep/editd/editd.cpp

Last change on this file was 6288, checked in by cameron, 3 months ago

Repeat of prior check in

  • Property svn:executable set to *
File size: 17.9 KB
Line 
1/*
2 *  Copyright (c) 2015 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 <string>
8#include <iostream>
9#include <fstream>
10#include <toolchain/toolchain.h>
11#include <pablo/pablo_toolchain.h>
12#include <llvm/IR/Function.h>
13#include <llvm/IR/Module.h>
14#include <llvm/Support/CommandLine.h>
15#include <cc/cc_compiler.h>
16#include <pablo/pablo_compiler.h>
17#include <pablo/pablo_kernel.h>
18#include <kernels/kernel_builder.h>
19#include <IR_Gen/idisa_target.h>
20#include <kernels/streamset.h>
21#include <kernels/source_kernel.h>
22#include <kernels/s2p_kernel.h>
23#include <cc/cc_kernel.h>
24#include <editd/editdscan_kernel.h>
25#include <kernels/streams_merge.h>
26#include <editd/pattern_compiler.h>
27#include <toolchain/cpudriver.h>
28#include <sys/stat.h>
29#include <fcntl.h>
30#include <mutex>
31#include <editd/editd_cpu_kernel.h>
32#include <kernels/pipeline_builder.h>
33#include <util/aligned_allocator.h>
34
35using namespace llvm;
36
37static cl::list<std::string> inputFiles(cl::Positional, cl::desc("<regex> <input file ...>"), cl::OneOrMore);
38
39static cl::list<std::string> pattVector("e", cl::desc("pattern"), cl::ZeroOrMore);
40static cl::opt<std::string> PatternFilename("f", cl::desc("Take patterns (one per line) from a file"), cl::value_desc("regex file"), cl::init(""));
41
42static cl::opt<bool> CaseInsensitive("i", cl::desc("Ignore case distinctions in the pattern and the file."));
43
44static cl::opt<int> editDistance("edit-dist", cl::desc("Edit Distance Value"), cl::init(2));
45static cl::opt<int> optPosition("opt-pos", cl::desc("Optimize position"), cl::init(0));
46static cl::opt<int> stepSize("step-size", cl::desc("Step Size"), cl::init(3));
47static cl::opt<int> prefixLen("prefix", cl::desc("Prefix length"), cl::init(3));
48static cl::opt<int> groupSize("groupPatterns", cl::desc("Number of pattern segments per group."), cl::init(1));
49static cl::opt<bool> ShowPositions("display", cl::desc("Display the match positions."), cl::init(false));
50
51static cl::opt<int> Threads("threads", cl::desc("Total number of threads."), cl::init(1));
52
53static cl::opt<bool> MultiEditdKernels("enable-multieditd-kernels", cl::desc("Construct multiple editd kernels in one pipeline."));
54static cl::opt<bool> EditdIndexPatternKernels("enable-index-kernels", cl::desc("Use pattern index method."));
55
56using namespace kernel;
57using namespace pablo;
58
59struct matchPosition
60{
61    size_t pos;
62    size_t dist;
63};
64
65std::vector<struct matchPosition> matchList;
66std::vector<std::vector<std::string>> pattGroups;
67
68void run_second_filter(int pattern_segs, int total_len, float errRate){
69
70    if(matchList.empty()) return;
71
72    //Sort match position
73    bool exchanged = true;
74    while(exchanged){
75        exchanged = false;
76        for (unsigned i=0; i<matchList.size()-1; i++){
77            if(matchList[i].pos > matchList[i+1].pos){
78                size_t tmp_pos = matchList[i].pos;
79                size_t tmp_dist = matchList[i].dist;
80                matchList[i].pos = matchList[i+1].pos;
81                matchList[i].dist = matchList[i+1].dist;
82                matchList[i+1].pos = tmp_pos;
83                matchList[i+1].dist = tmp_dist;
84                exchanged = true;
85            }
86        }
87    }
88
89    //remove the duplicates
90    bool cleared = true;
91    while(cleared){
92        cleared = false;
93        for (unsigned i=0; i<matchList.size()-1; i++){
94            if(matchList[i].pos == matchList[i+1].pos && matchList[i].dist == matchList[i+1].dist){
95                matchList.erase(matchList.begin() + i);
96                cleared = true;
97            }
98        }
99    }
100
101    std::cout << "pattern_segs = " << pattern_segs << ", total_len = " << total_len << std::endl;
102
103    int v = pattern_segs * (editDistance+1) - total_len * errRate;
104
105    int startPos = matchList[0].pos;
106    int sum = matchList[0].dist;
107    int curIdx = 0;
108    unsigned i = 0;
109    int count = 0;
110    while (i < matchList.size()){
111        if(matchList[i].pos - startPos < total_len * (errRate+1)){
112            sum += matchList[i].dist;
113            i++;
114        }
115        else{
116            if(sum > v) count++;
117            sum -= matchList[curIdx].dist;
118            curIdx++;
119            startPos = matchList[curIdx].pos;
120        }
121    }
122
123    std::cout << "total candidate from the first filter is " << matchList.size() << std::endl;
124    std::cout << "total candidate from the second filter is " << count << std::endl;
125}
126
127void get_editd_pattern(int & pattern_segs, int & total_len) {
128
129    if (PatternFilename != "") {
130        std::ifstream pattFile(PatternFilename.c_str());
131        std::string r;
132        if (pattFile.is_open()) {
133            while (std::getline(pattFile, r)) {
134                pattVector.push_back(r);
135                pattern_segs ++;
136                total_len += r.size();
137            }
138            std::sort(pattVector.begin(), pattVector.end());
139            unsigned i = 0;
140            while(i < pattVector.size()){
141                std::vector<std::string> pattGroup;
142                std::string prefix = pattVector[i].substr(0, prefixLen);
143                while(i < pattVector.size() && pattVector[i].substr(0, prefixLen) == prefix){
144                    pattGroup.push_back(pattVector[i]);
145                    i++;
146                }
147                pattGroups.push_back(pattGroup);
148            }
149            pattFile.close();
150        }
151        codegen::GroupNum = pattVector.size()/groupSize;
152    }
153
154    // if there are no regexes specified through -e or -f, the first positional argument
155    // must be a regex, not an input file.
156
157    if (pattVector.size() == 0 && inputFiles.size() > 1) {
158        pattVector.push_back(inputFiles[0]);
159        inputFiles.erase(inputFiles.begin());
160    }
161}
162
163#warning make a "CBuffer" class to abstract away the complexity of making these function typedefs.
164
165typedef void (*preprocessFunctionType)(char * output_data, size_t * output_produced, size_t output_size, const uint32_t fd);
166
167static char * chStream;
168static size_t size;
169
170class PreprocessKernel final: public pablo::PabloKernel {
171public:
172    PreprocessKernel(const std::unique_ptr<KernelBuilder> & b, StreamSet * BasisBits, StreamSet * CCResults);
173    bool isCachable() const override { return true; }
174    bool hasSignature() const override { return false; }
175protected:
176    void generatePabloMethod() override;
177};
178
179PreprocessKernel::PreprocessKernel(const std::unique_ptr<KernelBuilder> & b, StreamSet * BasisBits, StreamSet * CCResults)
180: PabloKernel(b, "editd_preprocess", {{"basis", BasisBits}}, {{"pat", CCResults}}) {
181
182}
183
184void PreprocessKernel::generatePabloMethod() {
185    PabloBuilder pb(getEntryScope());
186    cc::Parabix_CC_Compiler ccc(getEntryScope(), getInputStreamSet("basis"));
187    PabloAST * A = ccc.compileCC(re::makeCC(re::makeCC(0x41), re::makeCC(0x61)));
188    PabloAST * C = ccc.compileCC(re::makeCC(re::makeCC(0x43), re::makeCC(0x63)));
189    PabloAST * T = ccc.compileCC(re::makeCC(re::makeCC(0x54), re::makeCC(0x74)));
190    PabloAST * G = ccc.compileCC(re::makeCC(re::makeCC(0x47), re::makeCC(0x67)));
191    Var * const pat = getOutputStreamVar("pat");
192    pb.createAssign(pb.createExtract(pat, 0), A);
193    pb.createAssign(pb.createExtract(pat, 1), C);
194    pb.createAssign(pb.createExtract(pat, 2), T);
195    pb.createAssign(pb.createExtract(pat, 3), G);
196}
197
198preprocessFunctionType preprocessPipeline(CPUDriver & pxDriver) {
199    StreamSet * const CCResults = pxDriver.CreateStreamSet(4);
200    auto & b = pxDriver.getBuilder();
201    Type * const int32Ty = b->getInt32Ty();
202    auto P = pxDriver.makePipelineWithIO({}, {{"CCResults", CCResults}}, {{int32Ty, "fileDescriptor"}});
203    Scalar * const fileDescriptor = P->getInputScalar("fileDescriptor");
204    StreamSet * const ByteStream = P->CreateStreamSet(1, 8);
205    P->CreateKernelCall<MMapSourceKernel>(fileDescriptor, ByteStream);
206    StreamSet * const BasisBits = P->CreateStreamSet(8);
207    P->CreateKernelCall<S2PKernel>(ByteStream, BasisBits);
208    P->CreateKernelCall<PreprocessKernel>(BasisBits, CCResults);
209    return reinterpret_cast<preprocessFunctionType>(P->compile());
210}
211
212size_t file_size(const int fd) {
213    struct stat st;
214    if (LLVM_UNLIKELY(fstat(fd, &st) != 0)) {
215        st.st_size = 0;
216    }
217    return st.st_size;
218}
219
220#define ALIGNMENT (512 / 8)
221
222inline bool is_power_2(const size_t n) {
223    return ((n & (n - 1)) == 0) && n;
224}
225
226inline size_t round_up_to(const size_t x, const size_t y) {
227    assert(is_power_2(y));
228    return (x + y - 1) & -y;
229}
230
231char * preprocess(preprocessFunctionType preprocess) {
232    std::string fileName = inputFiles[0];
233    const auto fd = open(inputFiles[0].c_str(), O_RDONLY);
234    if (LLVM_UNLIKELY(fd == -1)) {
235        std::cerr << "Error: cannot open " << fileName << " for processing.\n";
236        exit(-1);
237    }
238    size = file_size(fd);
239
240    // Given a 8-bit bytestream of length n, we need space for 4 bitstreams of length n ...
241    AlignedAllocator<char, ALIGNMENT> alloc;
242    const size_t n = round_up_to(size, 8 * ALIGNMENT);
243    chStream = alloc.allocate((4 * n) / 8);
244    size_t length = 0;
245    preprocess(chStream, &length, n, fd);
246    close(fd);
247    return chStream;
248}
249
250
251std::string createName(const std::vector<std::string> & patterns) {
252    std::string name = "";
253    for(unsigned i=0; i<patterns.size(); i++)
254        name += patterns[i];
255    return name + std::to_string(editDistance);
256}
257
258class PatternKernel final: public pablo::PabloKernel {
259public:
260    PatternKernel(const std::unique_ptr<KernelBuilder> & b, const std::vector<std::string> & patterns, StreamSet * pat, StreamSet * E);
261    std::string makeSignature(const std::unique_ptr<KernelBuilder> &) override;
262    bool isCachable() const override { return true;}
263protected:
264    void generatePabloMethod() override;
265private:
266    const std::vector<std::string> & mPatterns;
267};
268
269PatternKernel::PatternKernel(const std::unique_ptr<KernelBuilder> & b, const std::vector<std::string> & patterns, StreamSet * pat, StreamSet * E)
270: PabloKernel(b, getStringHash(createName(patterns)),
271{{"pat", pat}},
272{{"E", E}})
273, mPatterns(patterns) {
274
275}
276
277std::string PatternKernel::makeSignature(const std::unique_ptr<KernelBuilder> &) {
278    return getName();
279}
280
281void PatternKernel::generatePabloMethod() {
282    PabloBuilder entry(getEntryScope());
283    Var * const pat = getInputStreamVar("pat");
284    PabloAST * basisBits[4];
285    basisBits[0] = entry.createExtract(pat, 0, "A");
286    basisBits[1] = entry.createExtract(pat, 1, "C");
287    basisBits[2] = entry.createExtract(pat, 2, "T");
288    basisBits[3] = entry.createExtract(pat, 3, "G");
289    re::Pattern_Compiler pattern_compiler(*this);
290    if (optPosition == 0) optPosition = editDistance + 6;
291    pattern_compiler.compile(mPatterns, entry, basisBits, editDistance, optPosition, stepSize);
292}
293
294std::mutex store_mutex;
295extern "C" void wrapped_report_pos(size_t match_pos, int dist) {
296    struct matchPosition curMatch;
297    curMatch.pos = match_pos;
298    curMatch.dist = dist;
299
300    store_mutex.lock();
301    matchList.push_back(curMatch);
302    if(ShowPositions)
303        std::cout << "pos: " << match_pos << ", dist:" << dist << "\n";
304    store_mutex.unlock();
305}
306
307typedef void (*editdFunctionType)(char * byte_data, size_t filesize);
308
309editdFunctionType editdPipeline(CPUDriver & pxDriver, const std::vector<std::string> & patterns) {
310    auto & b = pxDriver.getBuilder();
311    Type * const sizeTy = b->getSizeTy();
312    Type * const inputType = b->getIntNTy(1)->getPointerTo();
313    auto P = pxDriver.makePipeline({Binding{inputType, "input"}, Binding{sizeTy, "fileSize"}});
314    Scalar * const inputStream = P->getInputScalar("input");
315    Scalar * const fileSize = P->getInputScalar("fileSize");
316    b->LinkFunction("wrapped_report_pos", wrapped_report_pos);
317    StreamSet * const ChStream = P->CreateStreamSet(4);
318    P->CreateKernelCall<MemorySourceKernel>(inputStream, fileSize, ChStream);
319    StreamSet * const MatchResults = P->CreateStreamSet(editDistance + 1);
320    P->CreateKernelCall<PatternKernel>(patterns, ChStream, MatchResults);
321    P->CreateKernelCall<editdScanKernel>(MatchResults);
322    return reinterpret_cast<editdFunctionType>(P->compile());
323}
324
325typedef void (*multiEditdFunctionType)(const int fd);
326
327multiEditdFunctionType multiEditdPipeline(CPUDriver & pxDriver) {
328
329    auto & b = pxDriver.getBuilder();
330    auto P = pxDriver.makePipeline({Binding{b->getInt32Ty(), "fileDescriptor"}});
331    b->LinkFunction("wrapped_report_pos", wrapped_report_pos);
332    Scalar * const fileDescriptor = P->getInputScalar("fileDescriptor");
333
334    StreamSet * const ByteStream = P->CreateStreamSet(1, 8);
335    P->CreateKernelCall<MMapSourceKernel>(fileDescriptor, ByteStream);
336
337    std::vector<re::CC *> ccs;
338    ccs.emplace_back(re::makeCC(re::makeCC(0x41), re::makeCC(0x61)));
339    ccs.emplace_back(re::makeCC(re::makeCC(0x43), re::makeCC(0x63)));
340    ccs.emplace_back(re::makeCC(re::makeCC(0x47), re::makeCC(0x67)));
341    ccs.emplace_back(re::makeCC(re::makeCC(0x54), re::makeCC(0x74)));
342
343    StreamSet * const ChStream = P->CreateStreamSet(4);
344    P->CreateKernelCall<CharacterClassKernelBuilder>("editd_cc", ccs, ByteStream, ChStream);
345
346    const auto n = pattGroups.size();
347    std::vector<StreamSet *> MatchResults(n);
348    for(unsigned i = 0; i < n; ++i){
349        MatchResults[i] = P->CreateStreamSet(editDistance + 1);
350        P->CreateKernelCall<PatternKernel>(pattGroups[i], ChStream, MatchResults[i]);
351    }
352
353    StreamSet * MergedResults = MatchResults[0];
354    if (n > 1) {
355        StreamSet * const MergedResults = P->CreateStreamSet();
356        P->CreateKernelCall<StreamsMerge>(MatchResults, MergedResults);
357    }
358    P->CreateKernelCall<editdScanKernel>(MergedResults);
359
360    return reinterpret_cast<multiEditdFunctionType>(P->compile());
361}
362
363typedef void (*editdIndexFunctionType)(char * byte_data, size_t filesize, const char * pattern);
364
365editdIndexFunctionType editdIndexPatternPipeline(CPUDriver & pxDriver, unsigned patternLen) {
366
367    auto & b = pxDriver.getBuilder();
368
369    Type * const inputType = b->getIntNTy(1)->getPointerTo();
370    Type * const sizeTy = b->getSizeTy();
371    Type * const patternPtrTy = PointerType::get(b->getInt8Ty(), 0);
372
373    auto P = pxDriver.makePipeline({Binding{inputType, "input"}, Binding{sizeTy, "fileSize"}, Binding{patternPtrTy, "pattStream"}});
374    Scalar * const inputStream = P->getInputScalar("input");
375    Scalar * const fileSize = P->getInputScalar("fileSize");
376    Scalar * const pattStream = P->getInputScalar("pattStream");
377
378    b->LinkFunction("wrapped_report_pos", wrapped_report_pos);
379
380    StreamSet * const ChStream = P->CreateStreamSet(4);
381    P->CreateKernelCall<MemorySourceKernel>(inputStream, fileSize, ChStream);
382
383    StreamSet * const MatchResults = P->CreateStreamSet(editDistance + 1);
384
385    P->CreateKernelCall<editdCPUKernel>(patternLen, groupSize, pattStream, ChStream, MatchResults);
386
387    P->CreateKernelCall<editdScanKernel>(MatchResults);
388
389    return reinterpret_cast<editdIndexFunctionType>(P->compile());
390}
391
392std::mutex count_mutex;
393size_t groupCount;
394void * DoEditd(void *)
395{
396    size_t groupIdx;
397    count_mutex.lock();
398    groupIdx = groupCount;
399    groupCount++;
400    count_mutex.unlock();
401
402    while (groupIdx < pattGroups.size()){
403
404        CPUDriver pxDriver("editd");
405        auto editd = editdPipeline(pxDriver, pattGroups[groupIdx]);
406        editd(chStream, size);
407
408        count_mutex.lock();
409        groupIdx = groupCount;
410        groupCount++;
411        count_mutex.unlock();
412    }
413
414    pthread_exit(NULL);
415}
416
417int main(int argc, char *argv[]) {
418    codegen::ParseCommandLineOptions(argc, argv);
419    int pattern_segs = 0;
420    int total_len = 0;
421
422    get_editd_pattern(pattern_segs, total_len);
423
424    if (MultiEditdKernels) {
425        CPUDriver pxDriver("editd");
426        auto editd = multiEditdPipeline(pxDriver);
427
428        std::string fileName = inputFiles[0];
429        const int fd = open(inputFiles[0].c_str(), O_RDONLY);
430        if (LLVM_UNLIKELY(fd == -1)) {
431            std::cerr << "Error: cannot open " << fileName << " for processing. Skipped.\n";
432            exit(-1);
433        }
434        editd(fd);
435        close(fd);
436        run_second_filter(pattern_segs, total_len, 0.15);
437        return 0;
438    }
439
440    CPUDriver pxDriver("preprocess");
441    auto preprocess_ptr = preprocessPipeline(pxDriver);
442    preprocess(preprocess_ptr);
443
444    if(pattVector.size() == 1){
445
446        CPUDriver pxDriver("editd");
447        auto editd = editdPipeline(pxDriver, pattVector);
448        editd(chStream, size);
449        std::cout << "total matches is " << matchList.size() << std::endl;
450    }
451    else{
452        if (Threads == 1) {
453            if (EditdIndexPatternKernels) {
454                CPUDriver pxDriver("editd");
455                auto editd_ptr = editdIndexPatternPipeline(pxDriver, pattVector[0].length());
456
457                for(unsigned i=0; i<pattVector.size(); i+=groupSize){
458                    std::string pattern = "";
459                    for (int j=0; j<groupSize; j++){
460                        pattern += pattVector[i+j];
461                    }
462                    editd_ptr(chStream, size, pattern.c_str());
463                }
464            }
465            else {
466                for(unsigned i=0; i<pattGroups.size(); i++){
467
468                    CPUDriver pxDriver("editd");
469                    auto editd = editdPipeline(pxDriver, pattGroups[i]);
470                    editd(chStream, size);
471                }
472            }
473        }
474        else{
475            const unsigned numOfThreads = Threads;
476            pthread_t threads[numOfThreads];
477            groupCount = 0;
478
479            for(unsigned long i = 0; i < numOfThreads; ++i){
480                const int rc = pthread_create(&threads[i], NULL, DoEditd, (void *)i);
481                if (rc) {
482                    llvm::report_fatal_error("Failed to create thread: code " + std::to_string(rc));
483                }
484            }
485
486            for(unsigned i = 0; i < numOfThreads; ++i) {
487                void * status = nullptr;
488                const int rc = pthread_join(threads[i], &status);
489                if (rc) {
490                    llvm::report_fatal_error("Failed to join thread: code " + std::to_string(rc));
491                }
492            }
493
494        }
495        run_second_filter(pattern_segs, total_len, 0.15);
496    }
497
498    AlignedAllocator<char, 32> alloc;
499    alloc.deallocate(chStream, 0);
500
501    return 0;
502}
Note: See TracBrowser for help on using the repository browser.