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

Last change on this file since 5772 was 5755, checked in by nmedfort, 19 months ago

Bug fixes and simplified MultiBlockKernel? logic

  • Property svn:executable set to *
File size: 32.0 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 <kernels/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 <boost/uuid/sha1.hpp>
32#include <editd/editd_cpu_kernel.h>
33
34#ifdef CUDA_ENABLED
35#include <toolchain/NVPTXDriver.h>
36#include <editd/editd_gpu_kernel.h>
37#include <editd/EditdCudaDriver.h>
38#endif
39
40using namespace llvm;
41
42static cl::list<std::string> inputFiles(cl::Positional, cl::desc("<regex> <input file ...>"), cl::OneOrMore);
43
44static cl::list<std::string> pattVector("e", cl::desc("pattern"), cl::ZeroOrMore);
45static cl::opt<std::string> PatternFilename("f", cl::desc("Take patterns (one per line) from a file"), cl::value_desc("regex file"), cl::init(""));
46
47static cl::opt<bool> CaseInsensitive("i", cl::desc("Ignore case distinctions in the pattern and the file."));
48
49static cl::opt<int> editDistance("edit-dist", cl::desc("Edit Distance Value"), cl::init(2));
50static cl::opt<int> optPosition("opt-pos", cl::desc("Optimize position"), cl::init(0));
51static cl::opt<int> stepSize("step-size", cl::desc("Step Size"), cl::init(3));
52static cl::opt<int> prefixLen("prefix", cl::desc("Prefix length"), cl::init(3));
53static cl::opt<int> groupSize("groupPatterns", cl::desc("Number of pattern segments per group."), cl::init(1));
54static cl::opt<bool> ShowPositions("display", cl::desc("Display the match positions."), cl::init(false));
55
56static cl::opt<int> Threads("threads", cl::desc("Total number of threads."), cl::init(1));
57
58static cl::opt<bool> MultiEditdKernels("enable-multieditd-kernels", cl::desc("Construct multiple editd kernels in one pipeline."));
59static cl::opt<bool> EditdIndexPatternKernels("enable-index-kernels", cl::desc("Use pattern index method."));
60
61using namespace kernel;
62using namespace pablo;
63using namespace parabix;
64
65#ifdef CUDA_ENABLED
66const static std::string PTXFilename = "editd.ptx";
67#endif
68
69struct matchPosition
70{
71    size_t pos;
72    size_t dist;
73};
74
75std::vector<struct matchPosition> matchList;
76std::vector<std::vector<std::string>> pattGroups;
77
78void run_second_filter(int pattern_segs, int total_len, float errRate){
79
80    if(matchList.empty()) return;
81
82    //Sort match position
83    bool exchanged = true;
84    while(exchanged){
85        exchanged = false;
86        for (unsigned i=0; i<matchList.size()-1; i++){
87            if(matchList[i].pos > matchList[i+1].pos){
88                size_t tmp_pos = matchList[i].pos;
89                size_t tmp_dist = matchList[i].dist;
90                matchList[i].pos = matchList[i+1].pos;
91                matchList[i].dist = matchList[i+1].dist;
92                matchList[i+1].pos = tmp_pos;
93                matchList[i+1].dist = tmp_dist;
94                exchanged = true;
95            }
96        }
97    }
98
99    //remove the duplicates
100    bool cleared = true;
101    while(cleared){
102        cleared = false;
103        for (unsigned i=0; i<matchList.size()-1; i++){
104            if(matchList[i].pos == matchList[i+1].pos && matchList[i].dist == matchList[i+1].dist){
105                matchList.erase(matchList.begin() + i);
106                cleared = true;
107            }
108        }
109    }
110
111    std::cout << "pattern_segs = " << pattern_segs << ", total_len = " << total_len << std::endl;
112
113    int v = pattern_segs * (editDistance+1) - total_len * errRate;
114
115    int startPos = matchList[0].pos;
116    int sum = matchList[0].dist;
117    int curIdx = 0;
118    unsigned i = 0;
119    int count = 0;
120    while (i < matchList.size()){
121        if(matchList[i].pos - startPos < total_len * (errRate+1)){
122            sum += matchList[i].dist;
123            i++;
124        }
125        else{
126            if(sum > v) count++;
127            sum -= matchList[curIdx].dist;
128            curIdx++;
129            startPos = matchList[curIdx].pos;
130        }
131    }
132
133    std::cout << "total candidate from the first filter is " << matchList.size() << std::endl;
134    std::cout << "total candidate from the second filter is " << count << std::endl;
135}
136
137void get_editd_pattern(int & pattern_segs, int & total_len) {
138
139    if (PatternFilename != "") {
140        std::ifstream pattFile(PatternFilename.c_str());
141        std::string r;
142        if (pattFile.is_open()) {
143            while (std::getline(pattFile, r)) {
144                pattVector.push_back(r);
145                pattern_segs ++;
146                total_len += r.size();
147            }
148            std::sort(pattVector.begin(), pattVector.end());
149            unsigned i = 0;
150            while(i < pattVector.size()){
151                std::vector<std::string> pattGroup;
152                std::string prefix = pattVector[i].substr(0, prefixLen);
153                while(i < pattVector.size() && pattVector[i].substr(0, prefixLen) == prefix){
154                    pattGroup.push_back(pattVector[i]);
155                    i++;
156                }
157                pattGroups.push_back(pattGroup);
158            }
159            pattFile.close();
160        }
161        codegen::GroupNum = pattVector.size()/groupSize;
162    }
163
164    // if there are no regexes specified through -e or -f, the first positional argument
165    // must be a regex, not an input file.
166
167    if (pattVector.size() == 0 && inputFiles.size() > 1) {
168        pattVector.push_back(inputFiles[0]);
169        inputFiles.erase(inputFiles.begin());
170    }
171}
172
173inline static std::string sha1sum(const std::string & str) {
174    char buffer[41];    // 40 hex-digits and the terminating null
175    uint32_t digest[5]; // 160 bits in total
176    boost::uuids::detail::sha1 sha1;
177    sha1.process_bytes(str.c_str(), str.size());
178    sha1.get_digest(digest);
179    snprintf(buffer, sizeof(buffer), "%.8x%.8x%.8x%.8x%.8x",
180             digest[0], digest[1], digest[2], digest[3], digest[4]);
181    return std::string(buffer);
182}
183
184std::string createName(const std::vector<std::string> & patterns) {
185    std::string name = "";
186    for(unsigned i=0; i<patterns.size(); i++)
187        name += patterns[i];
188    return name + std::to_string(editDistance);
189}
190
191class PatternKernel final: public pablo::PabloKernel {
192public:
193    PatternKernel(const std::unique_ptr<kernel::KernelBuilder> & b, const std::vector<std::string> & patterns);
194    std::string makeSignature(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) override;
195    bool isCachable() const override { return true;}
196protected:
197    void generatePabloMethod() override;
198private:
199    const std::vector<std::string> & mPatterns;
200};
201
202PatternKernel::PatternKernel(const std::unique_ptr<kernel::KernelBuilder> & b, const std::vector<std::string> & patterns)
203: PabloKernel(b, sha1sum(createName(patterns)), {{b->getStreamSetTy(4), "pat"}}, {{b->getStreamSetTy(editDistance + 1), "E"}})
204, mPatterns(patterns) { 
205}
206
207std::string PatternKernel::makeSignature(const std::unique_ptr<kernel::KernelBuilder> &) {
208    return getName();
209}
210
211void PatternKernel::generatePabloMethod() {
212    PabloBuilder entry(getEntryBlock());
213    Var * const pat = getInputStreamVar("pat");
214    PabloAST * basisBits[4];
215    basisBits[0] = entry.createExtract(pat, 0, "A");
216    basisBits[1] = entry.createExtract(pat, 1, "C");
217    basisBits[2] = entry.createExtract(pat, 2, "T");
218    basisBits[3] = entry.createExtract(pat, 3, "G");
219    re::Pattern_Compiler pattern_compiler(*this);
220    if (optPosition == 0) optPosition = editDistance + 6;
221    pattern_compiler.compile(mPatterns, entry, basisBits, editDistance, optPosition, stepSize);
222}
223
224std::mutex store_mutex;
225void wrapped_report_pos(size_t match_pos, int dist) {
226    struct matchPosition curMatch;
227    curMatch.pos = match_pos;
228    curMatch.dist = dist;
229
230    store_mutex.lock();
231    matchList.push_back(curMatch);
232    if(ShowPositions)
233        std::cout << "pos: " << match_pos << ", dist:" << dist << "\n";
234    store_mutex.unlock();
235}
236
237void editdPipeline(ParabixDriver & pxDriver, const std::vector<std::string> & patterns) {
238
239    auto & idb = pxDriver.getBuilder();
240    Module * const m = idb->getModule();
241    Type * const sizeTy = idb->getSizeTy();
242    Type * const voidTy = idb->getVoidTy();
243    Type * const inputType = PointerType::get(ArrayType::get(ArrayType::get(idb->getBitBlockType(), 8), 1), 0);
244
245    idb->LinkFunction("wrapped_report_pos", &wrapped_report_pos);
246
247    const unsigned segmentSize = codegen::SegmentSize;
248    const unsigned bufferSegments = codegen::BufferSegments * codegen::ThreadNum;
249
250    Function * const main = cast<Function>(m->getOrInsertFunction("Main", voidTy, inputType, sizeTy, nullptr));
251    main->setCallingConv(CallingConv::C);
252    auto args = main->arg_begin();
253    Value * const inputStream = &*(args++);
254    inputStream->setName("input");
255    Value * const fileSize = &*(args++);
256    fileSize->setName("fileSize");
257    idb->SetInsertPoint(BasicBlock::Create(m->getContext(), "entry", main,0));
258
259    auto ChStream = pxDriver.addBuffer<SourceBuffer>(idb, idb->getStreamSetTy(4));
260    auto mmapK = pxDriver.addKernelInstance<MemorySourceKernel>(idb, inputType, segmentSize);
261    mmapK->setInitialArguments({inputStream, fileSize});
262    pxDriver.makeKernelCall(mmapK, {}, {ChStream});
263
264    auto MatchResults = pxDriver.addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(editDistance + 1), segmentSize * bufferSegments);
265    auto editdk = pxDriver.addKernelInstance<PatternKernel>(idb, patterns);
266    pxDriver.makeKernelCall(editdk, {ChStream}, {MatchResults});
267
268    auto editdScanK = pxDriver.addKernelInstance<editdScanKernel>(idb, editDistance);
269    pxDriver.makeKernelCall(editdScanK, {MatchResults}, {});
270
271    pxDriver.generatePipelineIR();
272    pxDriver.deallocateBuffers();
273    idb->CreateRetVoid();
274
275    pxDriver.finalizeObject();
276}
277
278class PreprocessKernel final: public pablo::PabloKernel {
279public:
280    PreprocessKernel(const std::unique_ptr<kernel::KernelBuilder> & b);
281    bool isCachable() const override { return true; }
282    bool hasSignature() const override { return false; }
283protected:
284    void generatePabloMethod() override;
285};
286
287PreprocessKernel::PreprocessKernel(const std::unique_ptr<kernel::KernelBuilder> & b)
288: PabloKernel(b, "ccc", {{b->getStreamSetTy(8), "basis"}}, {{b->getStreamSetTy(4), "pat"}}) {
289
290}
291
292void PreprocessKernel::generatePabloMethod() {
293    cc::CC_Compiler ccc(this, getInputStreamVar("basis"));
294    PabloBuilder & pb = ccc.getBuilder();
295    PabloAST * A = ccc.compileCC(re::makeCC(re::makeCC(0x41), re::makeCC(0x61)), pb);
296    PabloAST * C = ccc.compileCC(re::makeCC(re::makeCC(0x43), re::makeCC(0x63)), pb);
297    PabloAST * T = ccc.compileCC(re::makeCC(re::makeCC(0x54), re::makeCC(0x74)), pb);
298    PabloAST * G = ccc.compileCC(re::makeCC(re::makeCC(0x47), re::makeCC(0x67)), pb);
299    Var * const pat = getOutputStreamVar("pat");
300    pb.createAssign(pb.createExtract(pat, 0), A);
301    pb.createAssign(pb.createExtract(pat, 1), C);
302    pb.createAssign(pb.createExtract(pat, 2), T);
303    pb.createAssign(pb.createExtract(pat, 3), G);
304}
305
306void preprocessPipeline(ParabixDriver & pxDriver) {
307
308    auto & iBuilder = pxDriver.getBuilder();
309    Module * m = iBuilder->getModule();
310
311    Type * const voidTy = iBuilder->getVoidTy();
312    Type * const int32Ty = iBuilder->getInt32Ty();
313    Type * const outputType = PointerType::get(ArrayType::get(iBuilder->getBitBlockType(), 4), 0);
314
315    const unsigned segmentSize = codegen::SegmentSize;
316    const unsigned bufferSegments = codegen::BufferSegments * codegen::ThreadNum;
317
318    Function * const main = cast<Function>(m->getOrInsertFunction("Main", voidTy, int32Ty, outputType, nullptr));
319    main->setCallingConv(CallingConv::C);
320    Function::arg_iterator args = main->arg_begin();
321
322    Value * const fileDescriptor = &*(args++);
323    fileDescriptor->setName("fileDescriptor");
324    Value * const outputStream = &*(args++);
325    outputStream->setName("output");
326
327    iBuilder->SetInsertPoint(BasicBlock::Create(m->getContext(), "entry", main));
328
329    auto ByteStream = pxDriver.addBuffer<SourceBuffer>(iBuilder, iBuilder->getStreamSetTy(1, 8));
330
331    auto mmapK = pxDriver.addKernelInstance<MMapSourceKernel>(iBuilder, segmentSize);
332    mmapK->setInitialArguments({fileDescriptor});
333    pxDriver.makeKernelCall(mmapK, {}, {ByteStream});
334
335    auto BasisBits = pxDriver.addBuffer<CircularBuffer>(iBuilder, iBuilder->getStreamSetTy(8), segmentSize * bufferSegments);
336    auto s2pk = pxDriver.addKernelInstance<S2PKernel>(iBuilder);
337    pxDriver.makeKernelCall(s2pk, {ByteStream}, {BasisBits});
338
339    auto CCResults = pxDriver.addBuffer<ExternalBuffer>(iBuilder, iBuilder->getStreamSetTy(4), outputStream);
340    auto ccck = pxDriver.addKernelInstance<PreprocessKernel>(iBuilder);
341    pxDriver.makeKernelCall(ccck, {BasisBits}, {CCResults});
342
343    pxDriver.generatePipelineIR();
344    pxDriver.deallocateBuffers();
345    iBuilder->CreateRetVoid();
346
347    pxDriver.finalizeObject();
348}
349
350void multiEditdPipeline(ParabixDriver & pxDriver) {
351    auto & idb = pxDriver.getBuilder();
352    Module * const m = idb->getModule();
353    Type * const voidTy = idb->getVoidTy();
354    Type * const int32Ty = idb->getInt32Ty();
355
356    idb->LinkFunction("wrapped_report_pos", &wrapped_report_pos);
357
358    const unsigned segmentSize = codegen::SegmentSize;
359    const unsigned bufferSegments = codegen::BufferSegments * codegen::ThreadNum;
360
361    Function * const main = cast<Function>(m->getOrInsertFunction("Main", voidTy, int32Ty, nullptr));
362    main->setCallingConv(CallingConv::C);
363    Function::arg_iterator args = main->arg_begin();
364
365    Value * const fileDescriptor = &*(args++);
366    fileDescriptor->setName("fileDescriptor");
367
368    idb->SetInsertPoint(BasicBlock::Create(m->getContext(), "entry", main,0));
369
370    auto ByteStream = pxDriver.addBuffer<SourceBuffer>(idb, idb->getStreamSetTy(1, 8));
371
372    auto mmapK = pxDriver.addKernelInstance<MMapSourceKernel>(idb, segmentSize);
373    mmapK->setInitialArguments({fileDescriptor});
374    pxDriver.makeKernelCall(mmapK, {}, {ByteStream});
375
376    auto ChStream = pxDriver.addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(4), segmentSize * bufferSegments);
377    auto ccck = pxDriver.addKernelInstance<kernel::DirectCharacterClassKernelBuilder>(idb, "ccc", 
378        std::vector<re::CC *>{re::makeCC(re::makeCC(0x41), re::makeCC(0x61)),
379                              re::makeCC(re::makeCC(0x43), re::makeCC(0x63)),
380                              re::makeCC(re::makeCC(0x54), re::makeCC(0x74)),
381                              re::makeCC(re::makeCC(0x47), re::makeCC(0x67))}, 1);
382    pxDriver.makeKernelCall(ccck, {ByteStream}, {ChStream});
383
384    const auto n = pattGroups.size();
385   
386    std::vector<StreamSetBuffer *> MatchResultsBufs(n);
387   
388    for(unsigned i = 0; i < n; ++i){
389        auto MatchResults = pxDriver.addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(editDistance + 1), segmentSize * bufferSegments);
390        auto editdk = pxDriver.addKernelInstance<PatternKernel>(idb, pattGroups[i]);
391        pxDriver.makeKernelCall(editdk, {ChStream}, {MatchResults});
392        MatchResultsBufs[i] = MatchResults;
393    }
394    StreamSetBuffer * MergedResults = MatchResultsBufs[0];
395    if (n > 1) {
396        MergedResults = pxDriver.addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(editDistance + 1), segmentSize * bufferSegments);
397        kernel::Kernel * streamsMergeK = pxDriver.addKernelInstance<kernel::StreamsMerge>(idb, editDistance + 1, n);
398        pxDriver.makeKernelCall(streamsMergeK, MatchResultsBufs, {MergedResults});
399    }
400
401    auto editdScanK = pxDriver.addKernelInstance<editdScanKernel>(idb, editDistance);
402    pxDriver.makeKernelCall(editdScanK, {MergedResults}, {});
403
404    pxDriver.generatePipelineIR();
405    pxDriver.deallocateBuffers();
406    idb->CreateRetVoid();
407
408    pxDriver.finalizeObject();
409}
410
411
412void editdIndexPatternPipeline(ParabixDriver & pxDriver, unsigned patternLen) {
413
414    auto & idb = pxDriver.getBuilder();
415    Module * const m = idb->getModule();
416    Type * const sizeTy = idb->getSizeTy();
417    Type * const voidTy = idb->getVoidTy();
418    Type * const inputType = PointerType::get(ArrayType::get(ArrayType::get(idb->getBitBlockType(), 8), 1), 0);
419    Type * const patternPtrTy = PointerType::get(idb->getInt8Ty(), 0);
420
421    idb->LinkFunction("wrapped_report_pos", &wrapped_report_pos);
422
423    const unsigned segmentSize = codegen::SegmentSize;
424    const unsigned bufferSegments = codegen::BufferSegments * codegen::ThreadNum;
425
426    Function * const main = cast<Function>(m->getOrInsertFunction("Main", voidTy, inputType, sizeTy, patternPtrTy, nullptr));
427    main->setCallingConv(CallingConv::C);
428    auto args = main->arg_begin();
429    Value * const inputStream = &*(args++);
430    inputStream->setName("input");
431    Value * const fileSize = &*(args++);
432    fileSize->setName("fileSize");
433    Value * const pattStream = &*(args++);
434    pattStream->setName("pattStream");
435    idb->SetInsertPoint(BasicBlock::Create(m->getContext(), "entry", main,0));
436
437    auto ChStream = pxDriver.addBuffer<SourceBuffer>(idb, idb->getStreamSetTy(4));
438    auto mmapK = pxDriver.addKernelInstance<MemorySourceKernel>(idb, inputType, segmentSize);
439    mmapK->setInitialArguments({inputStream, fileSize});
440    pxDriver.makeKernelCall(mmapK, {}, {ChStream});
441
442    auto MatchResults = pxDriver.addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(editDistance + 1), segmentSize * bufferSegments);
443    auto editdk = pxDriver.addKernelInstance<kernel::editdCPUKernel>(idb, editDistance, patternLen, groupSize);
444
445    const unsigned numOfCarries = patternLen * (editDistance + 1) * 4 * groupSize;
446    Type * strideCarryTy = ArrayType::get(idb->getBitBlockType(), numOfCarries);
447    Value * strideCarry = idb->CreateAlloca(strideCarryTy);
448    idb->CreateStore(Constant::getNullValue(strideCarryTy), strideCarry);
449
450    editdk->setInitialArguments({pattStream, strideCarry});
451    pxDriver.makeKernelCall(editdk, {ChStream}, {MatchResults});
452
453    auto editdScanK = pxDriver.addKernelInstance<editdScanKernel>(idb, editDistance);
454    pxDriver.makeKernelCall(editdScanK, {MatchResults}, {});
455
456    pxDriver.generatePipelineIR();
457
458    idb->CreateRetVoid();
459
460    pxDriver.finalizeObject();
461}
462
463typedef void (*preprocessFunctionType)(const int fd, char * output_data);
464
465typedef void (*editdFunctionType)(char * byte_data, size_t filesize);
466
467typedef void (*multiEditdFunctionType)(const int fd);
468
469typedef void (*editdIndexFunctionType)(char * byte_data, size_t filesize, const char * pattern);
470
471static char * chStream;
472static size_t size;
473
474size_t file_size(const int fd) {
475    struct stat st;
476    if (LLVM_UNLIKELY(fstat(fd, &st) != 0)) {
477        st.st_size = 0;
478    }
479    return st.st_size;
480}
481
482char * preprocess(preprocessFunctionType fn_ptr) {
483    std::string fileName = inputFiles[0];
484    const int fd = open(inputFiles[0].c_str(), O_RDONLY);
485    if (LLVM_UNLIKELY(fd == -1)) {
486        std::cerr << "Error: cannot open " << fileName << " for processing. Skipped.\n";
487        exit(-1);
488    }
489    size = file_size(fd);
490    int ret = posix_memalign((void**)&chStream, 32, size);
491    if (ret) {
492        std::cerr << "Cannot allocate memory for output.\n";
493        exit(-2);
494    }
495    fn_ptr(fd, chStream);
496    close(fd);
497    return chStream;
498}
499
500void editd(editdFunctionType fn_ptr, char * inputStream, size_t size) {
501    fn_ptr(inputStream, size);
502}
503
504std::mutex count_mutex;
505size_t groupCount;
506void * DoEditd(void *)
507{
508    size_t groupIdx;
509    count_mutex.lock();
510    groupIdx = groupCount;
511    groupCount++;
512    count_mutex.unlock();
513
514    while (groupIdx < pattGroups.size()){
515
516        ParabixDriver pxDriver("editd");
517        editdPipeline(pxDriver, pattGroups[groupIdx]);
518        auto editd_ptr = reinterpret_cast<editdFunctionType>(pxDriver.getMain());
519        editd(editd_ptr, chStream, size);
520
521        count_mutex.lock();
522        groupIdx = groupCount;
523        groupCount++;
524        count_mutex.unlock();
525    }
526
527    pthread_exit(NULL);
528}
529
530#ifdef CUDA_ENABLED
531void editdGPUCodeGen(unsigned patternLen){
532    NVPTXDriver pxDriver("editd");
533    auto & iBuilder = pxDriver.getBuilder();
534    Module * M = iBuilder->getModule();
535
536    const unsigned segmentSize = codegen::SegmentSize;
537
538    Type * const mBitBlockType = iBuilder->getBitBlockType();
539    Type * const inputSizeTy = PointerType::get(iBuilder->getSizeTy(), 1);
540    Type * const int32ty = iBuilder->getInt32Ty();
541    Type * const voidTy = Type::getVoidTy(M->getContext());
542    Type * const inputTy = PointerType::get(ArrayType::get(mBitBlockType, 4), 1);
543    Type * const patternPtrTy = PointerType::get(iBuilder->getInt8Ty(), 1);
544    Type * const outputTy = PointerType::get(ArrayType::get(mBitBlockType, editDistance+1), 1);
545    Type * const stridesTy = PointerType::get(int32ty, 1);
546
547    Function * const main = cast<Function>(M->getOrInsertFunction("Main", voidTy, inputTy, inputSizeTy, patternPtrTy, outputTy, stridesTy, nullptr));
548    main->setCallingConv(CallingConv::C);
549    auto args = main->arg_begin();
550
551    Value * const inputStream = &*(args++);
552    inputStream->setName("input");
553    Value * const inputSizePtr = &*(args++);
554    inputSizePtr->setName("inputSizePtr");
555    Value * const pattStream = &*(args++);
556    pattStream->setName("pattStream");
557    Value * const resultStream = &*(args++);
558    resultStream->setName("resultStream");
559    Value * const stridesPtr = &*(args++);
560    stridesPtr->setName("stridesPtr");
561
562    iBuilder->SetInsertPoint(BasicBlock::Create(M->getContext(), "entry", main,0));
563
564    Function * tidFunc = M->getFunction("llvm.nvvm.read.ptx.sreg.tid.x");
565    Value * tid = iBuilder->CreateCall(tidFunc);
566    Function * bidFunc = cast<Function>(M->getOrInsertFunction("llvm.nvvm.read.ptx.sreg.ctaid.x", int32ty, nullptr));
567    Value * bid = iBuilder->CreateCall(bidFunc);
568
569    Value * inputThreadPtr = iBuilder->CreateGEP(inputStream, tid);
570    Value * strides = iBuilder->CreateLoad(stridesPtr);
571    Value * outputBlocks = iBuilder->CreateMul(strides, ConstantInt::get(int32ty, iBuilder->getStride() / iBuilder->getBitBlockWidth()));
572    Value * resultStreamPtr = iBuilder->CreateGEP(resultStream, iBuilder->CreateAdd(iBuilder->CreateMul(bid, outputBlocks), tid));
573    Value * inputSize = iBuilder->CreateLoad(inputSizePtr);
574
575    auto CCStream = pxDriver.addBuffer<SourceBuffer>(iBuilder, iBuilder->getStreamSetTy(4), 1);
576    auto sourceK = pxDriver.addKernelInstance<kernel::MemorySourceKernel>(iBuilder, inputTy, segmentSize);
577    sourceK->setInitialArguments({inputThreadPtr, inputSize});
578    pxDriver.makeKernelCall(sourceK, {}, {CCStream});
579
580    auto ResultStream = pxDriver.addBuffer<ExternalBuffer>(iBuilder, iBuilder->getStreamSetTy(editDistance+1), resultStreamPtr, 1);
581    auto editdk = pxDriver.addKernelInstance<kernel::editdGPUKernel>(iBuilder, editDistance, patternLen, groupSize);
582     
583    const unsigned numOfCarries = patternLen * (editDistance + 1) * 4 * groupSize;
584    Type * strideCarryTy = ArrayType::get(mBitBlockType, numOfCarries);
585    Value * strideCarry = iBuilder->CreateAlloca(strideCarryTy);
586    iBuilder->CreateStore(Constant::getNullValue(strideCarryTy), strideCarry);
587
588    editdk->setInitialArguments({pattStream, strideCarry});
589    pxDriver.makeKernelCall(editdk, {CCStream}, {ResultStream});
590
591    pxDriver.generatePipelineIR();
592    pxDriver.deallocateBuffers();
593    iBuilder->CreateRetVoid();
594
595    pxDriver.finalizeObject();
596
597}
598
599void mergeGPUCodeGen(){
600    NVPTXDriver pxDriver("merge");
601    auto & iBuilder = pxDriver.getBuilder();
602    Module * M = iBuilder->getModule();
603
604    Type * const mBitBlockType = iBuilder->getBitBlockType();
605    Type * const int32ty = iBuilder->getInt32Ty();
606    Type * const voidTy = Type::getVoidTy(M->getContext());
607    Type * const resultTy = PointerType::get(ArrayType::get(mBitBlockType, editDistance+1), 1);
608    Type * const stridesTy = PointerType::get(int32ty, 1);
609
610    Function * const main = cast<Function>(M->getOrInsertFunction("Main", voidTy, resultTy, stridesTy, nullptr));
611    main->setCallingConv(CallingConv::C);
612    Function::arg_iterator args = main->arg_begin();
613
614    Value * const resultStream = &*(args++);
615    resultStream->setName("resultStream");
616    Value * const stridesPtr = &*(args++);
617    stridesPtr->setName("stridesPtr");
618
619    BasicBlock * entryBlock = BasicBlock::Create(iBuilder->getContext(), "entryBlock", main, 0);
620    BasicBlock * strideLoopCond = BasicBlock::Create(iBuilder->getContext(), "strideLoopCond", main, 0);
621    BasicBlock * strideLoopBody = BasicBlock::Create(iBuilder->getContext(), "strideLoopBody", main, 0);
622    BasicBlock * stridesDone = BasicBlock::Create(iBuilder->getContext(), "stridesDone", main, 0);
623
624    iBuilder->SetInsertPoint(entryBlock);
625
626    Function * tidFunc = M->getFunction("llvm.nvvm.read.ptx.sreg.tid.x");
627    Value * tid = iBuilder->CreateCall(tidFunc);
628    Function * bidFunc = cast<Function>(M->getOrInsertFunction("llvm.nvvm.read.ptx.sreg.ctaid.x", int32ty, nullptr));
629    Value * bid = iBuilder->CreateCall(bidFunc);
630
631    Value * strides = iBuilder->CreateLoad(stridesPtr);
632    Value * strideBlocks = ConstantInt::get(int32ty, iBuilder->getStride() / iBuilder->getBitBlockWidth());
633    Value * outputBlocks = iBuilder->CreateMul(strides, strideBlocks);
634    Value * resultStreamPtr = iBuilder->CreateGEP(resultStream, tid);
635
636    iBuilder->CreateBr(strideLoopCond);
637    iBuilder->SetInsertPoint(strideLoopCond);
638    PHINode * strideNo = iBuilder->CreatePHI(int32ty, 2, "strideNo");
639    strideNo->addIncoming(ConstantInt::get(int32ty, 0), entryBlock);
640    Value * notDone = iBuilder->CreateICmpULT(strideNo, strides);
641    iBuilder->CreateCondBr(notDone, strideLoopBody, stridesDone);
642
643    iBuilder->SetInsertPoint(strideLoopBody);
644    Value * myResultStreamPtr = iBuilder->CreateGEP(resultStreamPtr, {iBuilder->CreateMul(strideBlocks, strideNo)});
645    Value * myResultStream = iBuilder->CreateLoad(iBuilder->CreateGEP(myResultStreamPtr, {iBuilder->getInt32(0), bid}));
646    for (int i=1; i<codegen::GroupNum; i++){
647        Value * nextStreamPtr = iBuilder->CreateGEP(myResultStreamPtr, {iBuilder->CreateMul(outputBlocks, iBuilder->getInt32(i)), bid});
648        myResultStream = iBuilder->CreateOr(myResultStream, iBuilder->CreateLoad(nextStreamPtr));
649    }
650    iBuilder->CreateStore(myResultStream, iBuilder->CreateGEP(myResultStreamPtr, {iBuilder->getInt32(0), bid}));
651    strideNo->addIncoming(iBuilder->CreateAdd(strideNo, ConstantInt::get(int32ty, 1)), strideLoopBody);
652    iBuilder->CreateBr(strideLoopCond);
653
654    iBuilder->SetInsertPoint(stridesDone);
655    iBuilder->CreateRetVoid();
656
657    pxDriver.finalizeObject();
658
659}
660#endif
661
662editdFunctionType editdScanCPUCodeGen(ParabixDriver & pxDriver) {
663   
664    auto & iBuilder = pxDriver.getBuilder();
665    Module * M = iBuilder->getModule();
666
667    const unsigned segmentSize = codegen::SegmentSize;
668    const unsigned bufferSegments = codegen::BufferSegments * codegen::ThreadNum;
669
670    Type * mBitBlockType = iBuilder->getBitBlockType();
671    Type * const size_ty = iBuilder->getSizeTy();
672    Type * const voidTy = Type::getVoidTy(M->getContext());
673    Type * const inputType = PointerType::get(ArrayType::get(mBitBlockType, editDistance+1), 0);
674
675    Function * const main = cast<Function>(M->getOrInsertFunction("Main", voidTy, inputType, size_ty, nullptr));
676    main->setCallingConv(CallingConv::C);
677    iBuilder->SetInsertPoint(BasicBlock::Create(M->getContext(), "entry", main, 0));
678    Function::arg_iterator args = main->arg_begin();
679    Value * const inputStream = &*(args++);
680    inputStream->setName("input");
681    Value * const fileSize = &*(args++);
682    fileSize->setName("fileSize");
683
684    StreamSetBuffer * MatchResults = pxDriver.addBuffer<SourceBuffer>(iBuilder, iBuilder->getStreamSetTy(editDistance+1));
685    kernel::Kernel * sourceK = pxDriver.addKernelInstance<kernel::MemorySourceKernel>(iBuilder, inputType, segmentSize * bufferSegments);
686    sourceK->setInitialArguments({inputStream, fileSize});
687    pxDriver.makeKernelCall(sourceK, {}, {MatchResults});
688
689    auto editdScanK = pxDriver.addKernelInstance<editdScanKernel>(iBuilder, editDistance);
690    pxDriver.makeKernelCall(editdScanK, {MatchResults}, {});
691    pxDriver.LinkFunction(*editdScanK, "wrapped_report_pos", &wrapped_report_pos);
692    pxDriver.generatePipelineIR();
693    pxDriver.deallocateBuffers();
694    iBuilder->CreateRetVoid();
695
696    pxDriver.finalizeObject();
697
698    return reinterpret_cast<editdFunctionType>(pxDriver.getMain());
699
700}
701
702int main(int argc, char *argv[]) {
703    codegen::ParseCommandLineOptions(argc, argv);
704    int pattern_segs = 0;
705    int total_len = 0;
706
707    get_editd_pattern(pattern_segs, total_len);
708
709    if (MultiEditdKernels) {
710        ParabixDriver pxDriver("editd");
711        multiEditdPipeline(pxDriver);
712        auto editd_ptr = reinterpret_cast<multiEditdFunctionType>(pxDriver.getMain());
713
714        std::string fileName = inputFiles[0];
715        const int fd = open(inputFiles[0].c_str(), O_RDONLY);
716        if (LLVM_UNLIKELY(fd == -1)) {
717            std::cerr << "Error: cannot open " << fileName << " for processing. Skipped.\n";
718            exit(-1);
719        }
720        editd_ptr(fd);
721        close(fd);
722        run_second_filter(pattern_segs, total_len, 0.15);
723        return 0;
724    }
725
726#ifdef CUDA_ENABLED
727    if (codegen::NVPTX)
728        codegen::BlockSize = 64;
729#endif
730
731    ParabixDriver pxDriver("preprocess");
732    preprocessPipeline(pxDriver);
733    auto preprocess_ptr = reinterpret_cast<preprocessFunctionType>(pxDriver.getMain());
734    preprocess(preprocess_ptr);
735
736#ifdef CUDA_ENABLED
737    if(codegen::NVPTX){
738
739        std::ifstream t(PatternFilename);
740        if (!t.is_open()) {
741            std::cerr << "Error: cannot open " << PatternFilename << " for processing. Skipped.\n";
742            exit(-1);
743        }
744        std::string patterns((std::istreambuf_iterator<char>(t)), std::istreambuf_iterator<char>());
745
746        editdGPUCodeGen(pattVector[0].length());
747        mergeGPUCodeGen();
748        ulong * rslt = RunPTX(PTXFilename, chStream, size, patterns.c_str(), patterns.length(), editDistance);
749
750        ParabixDriver scanDriver("scan");
751        editdFunctionType editd_ptr = editdScanCPUCodeGen(scanDriver);
752        editd(editd_ptr, (char*)rslt, size);
753
754        run_second_filter(pattern_segs, total_len, 0.15);
755
756        return 0;
757    }
758#endif
759
760    if(pattVector.size() == 1){
761
762        ParabixDriver pxDriver("editd");
763        editdPipeline(pxDriver, pattVector);
764        auto editd_ptr = reinterpret_cast<editdFunctionType>(pxDriver.getMain());
765        editd(editd_ptr, chStream, size);
766        std::cout << "total matches is " << matchList.size() << std::endl;
767    }
768    else{
769        if (Threads == 1) { 
770            if (EditdIndexPatternKernels) {
771                ParabixDriver pxDriver("editd");
772                editdIndexPatternPipeline(pxDriver, pattVector[0].length());
773                auto editd_ptr = reinterpret_cast<editdIndexFunctionType>(pxDriver.getMain());
774
775                for(unsigned i=0; i<pattVector.size(); i+=groupSize){
776                    std::string pattern = "";
777                    for (int j=0; j<groupSize; j++){
778                        pattern += pattVector[i+j];
779                    }
780                    editd_ptr(chStream, size, pattern.c_str());
781                }
782            }
783            else {
784                for(unsigned i=0; i<pattGroups.size(); i++){
785
786                    ParabixDriver pxDriver("editd");
787                    editdPipeline(pxDriver, pattGroups[i]);
788                    auto editd_ptr = reinterpret_cast<editdFunctionType>(pxDriver.getMain());
789                    editd(editd_ptr, chStream, size);
790                }
791            }
792        }
793        else{
794            const unsigned numOfThreads = Threads;
795            pthread_t threads[numOfThreads];
796            groupCount = 0;
797
798            for(unsigned long i = 0; i < numOfThreads; ++i){
799                const int rc = pthread_create(&threads[i], NULL, DoEditd, (void *)i);
800                if (rc) {
801                    llvm::report_fatal_error("Failed to create thread: code " + std::to_string(rc));
802                }
803            }
804
805            for(unsigned i = 0; i < numOfThreads; ++i) {
806                void * status = nullptr;
807                const int rc = pthread_join(threads[i], &status);
808                if (rc) {
809                    llvm::report_fatal_error("Failed to join thread: code " + std::to_string(rc));
810                }
811            }
812
813        }
814        run_second_filter(pattern_segs, total_len, 0.15);
815    }
816
817    return 0;
818}
Note: See TracBrowser for help on using the repository browser.