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

Last change on this file since 6104 was 6047, checked in by nmedfort, 15 months ago

Major refactoring of buffer types. Static buffers replace Circular and CircularCopyback?. External buffers unify Source/External?.

  • Property svn:executable set to *
File size: 31.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 <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(getEntryScope());
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;
225extern "C" void 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 = idb->getIntNTy(1)->getPointerTo();
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<ExternalBuffer>(idb, idb->getStreamSetTy(4));
260    auto mmapK = pxDriver.addKernelInstance<MemorySourceKernel>(idb, 4, 1);
261    mmapK->setInitialArguments({inputStream, fileSize});
262    pxDriver.makeKernelCall(mmapK, {}, {ChStream});
263
264    auto MatchResults = pxDriver.addBuffer<StaticBuffer>(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    PabloBuilder pb(getEntryScope());
294    cc::Parabix_CC_Compiler ccc(getEntryScope(), getInputStreamSet("basis"));
295    PabloAST * A = ccc.compileCC(re::makeCC(re::makeCC(0x41), re::makeCC(0x61)));
296    PabloAST * C = ccc.compileCC(re::makeCC(re::makeCC(0x43), re::makeCC(0x63)));
297    PabloAST * T = ccc.compileCC(re::makeCC(re::makeCC(0x54), re::makeCC(0x74)));
298    PabloAST * G = ccc.compileCC(re::makeCC(re::makeCC(0x47), re::makeCC(0x67)));
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<ExternalBuffer>(iBuilder, iBuilder->getStreamSetTy(1, 8));
330
331    auto mmapK = pxDriver.addKernelInstance<MMapSourceKernel>(iBuilder);
332    mmapK->setInitialArguments({fileDescriptor});
333    pxDriver.makeKernelCall(mmapK, {}, {ByteStream});
334
335    auto BasisBits = pxDriver.addBuffer<StaticBuffer>(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    // NOTE: CCResults are never consumed because they are written directly into an external buffer. This may make analysis difficult.
342    pxDriver.makeKernelCall(ccck, {BasisBits}, {CCResults});
343
344    pxDriver.generatePipelineIR();
345    pxDriver.deallocateBuffers();
346    iBuilder->CreateRetVoid();
347
348    pxDriver.finalizeObject();
349}
350
351void multiEditdPipeline(ParabixDriver & pxDriver) {
352    auto & idb = pxDriver.getBuilder();
353    Module * const m = idb->getModule();
354    Type * const voidTy = idb->getVoidTy();
355    Type * const int32Ty = idb->getInt32Ty();
356
357    idb->LinkFunction("wrapped_report_pos", &wrapped_report_pos);
358
359    const unsigned segmentSize = codegen::SegmentSize;
360    const unsigned bufferSegments = codegen::BufferSegments * codegen::ThreadNum;
361
362    Function * const main = cast<Function>(m->getOrInsertFunction("Main", voidTy, int32Ty, nullptr));
363    main->setCallingConv(CallingConv::C);
364    Function::arg_iterator args = main->arg_begin();
365
366    Value * const fileDescriptor = &*(args++);
367    fileDescriptor->setName("fileDescriptor");
368
369    idb->SetInsertPoint(BasicBlock::Create(m->getContext(), "entry", main,0));
370
371    auto ByteStream = pxDriver.addBuffer<ExternalBuffer>(idb, idb->getStreamSetTy(1, 8));
372
373    auto mmapK = pxDriver.addKernelInstance<MMapSourceKernel>(idb);
374    mmapK->setInitialArguments({fileDescriptor});
375    pxDriver.makeKernelCall(mmapK, {}, {ByteStream});
376
377    auto ChStream = pxDriver.addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(4), segmentSize * bufferSegments);
378    auto ccck = pxDriver.addKernelInstance<kernel::DirectCharacterClassKernelBuilder>(idb, "ccc", 
379        std::vector<re::CC *>{re::makeCC(re::makeCC(0x41), re::makeCC(0x61)),
380                              re::makeCC(re::makeCC(0x43), re::makeCC(0x63)),
381                              re::makeCC(re::makeCC(0x54), re::makeCC(0x74)),
382                              re::makeCC(re::makeCC(0x47), re::makeCC(0x67))});
383    pxDriver.makeKernelCall(ccck, {ByteStream}, {ChStream});
384
385    const auto n = pattGroups.size();
386   
387    std::vector<StreamSetBuffer *> MatchResultsBufs(n);
388   
389    for(unsigned i = 0; i < n; ++i){
390        auto MatchResults = pxDriver.addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(editDistance + 1), segmentSize * bufferSegments);
391        auto editdk = pxDriver.addKernelInstance<PatternKernel>(idb, pattGroups[i]);
392        pxDriver.makeKernelCall(editdk, {ChStream}, {MatchResults});
393        MatchResultsBufs[i] = MatchResults;
394    }
395    StreamSetBuffer * MergedResults = MatchResultsBufs[0];
396    if (n > 1) {
397        MergedResults = pxDriver.addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(editDistance + 1), segmentSize * bufferSegments);
398        kernel::Kernel * streamsMergeK = pxDriver.addKernelInstance<kernel::StreamsMerge>(idb, editDistance + 1, n);
399        pxDriver.makeKernelCall(streamsMergeK, MatchResultsBufs, {MergedResults});
400    }
401
402    auto editdScanK = pxDriver.addKernelInstance<editdScanKernel>(idb, editDistance);
403    pxDriver.makeKernelCall(editdScanK, {MergedResults}, {});
404
405    pxDriver.generatePipelineIR();
406    pxDriver.deallocateBuffers();
407    idb->CreateRetVoid();
408
409    pxDriver.finalizeObject();
410}
411
412
413void editdIndexPatternPipeline(ParabixDriver & pxDriver, unsigned patternLen) {
414
415    auto & idb = pxDriver.getBuilder();
416    Module * const m = idb->getModule();
417    Type * const sizeTy = idb->getSizeTy();
418    Type * const voidTy = idb->getVoidTy();
419    Type * const inputType = idb->getIntNTy(1)->getPointerTo();
420    Type * const patternPtrTy = PointerType::get(idb->getInt8Ty(), 0);
421
422    idb->LinkFunction("wrapped_report_pos", &wrapped_report_pos);
423
424    const unsigned segmentSize = codegen::SegmentSize;
425    const unsigned bufferSegments = codegen::BufferSegments * codegen::ThreadNum;
426
427    Function * const main = cast<Function>(m->getOrInsertFunction("Main", voidTy, inputType, sizeTy, patternPtrTy, nullptr));
428    main->setCallingConv(CallingConv::C);
429    auto args = main->arg_begin();
430    Value * const inputStream = &*(args++);
431    inputStream->setName("input");
432    Value * const fileSize = &*(args++);
433    fileSize->setName("fileSize");
434    Value * const pattStream = &*(args++);
435    pattStream->setName("pattStream");
436    idb->SetInsertPoint(BasicBlock::Create(m->getContext(), "entry", main,0));
437
438    auto ChStream = pxDriver.addBuffer<ExternalBuffer>(idb, idb->getStreamSetTy(4));
439    auto mmapK = pxDriver.addKernelInstance<MemorySourceKernel>(idb, 4, 1);
440    mmapK->setInitialArguments({inputStream, fileSize});
441    pxDriver.makeKernelCall(mmapK, {}, {ChStream});
442
443    auto MatchResults = pxDriver.addBuffer<StaticBuffer>(idb, idb->getStreamSetTy(editDistance + 1), segmentSize * bufferSegments);
444    auto editdk = pxDriver.addKernelInstance<kernel::editdCPUKernel>(idb, editDistance, patternLen, groupSize);
445
446    const unsigned numOfCarries = patternLen * (editDistance + 1) * 4 * groupSize;
447    Type * strideCarryTy = ArrayType::get(idb->getBitBlockType(), numOfCarries);
448    Value * strideCarry = idb->CreateAlloca(strideCarryTy);
449    idb->CreateStore(Constant::getNullValue(strideCarryTy), strideCarry);
450
451    editdk->setInitialArguments({pattStream, strideCarry});
452    pxDriver.makeKernelCall(editdk, {ChStream}, {MatchResults});
453
454    auto editdScanK = pxDriver.addKernelInstance<editdScanKernel>(idb, editDistance);
455    pxDriver.makeKernelCall(editdScanK, {MatchResults}, {});
456
457    pxDriver.generatePipelineIR();
458
459    idb->CreateRetVoid();
460
461    pxDriver.finalizeObject();
462}
463
464typedef void (*preprocessFunctionType)(const int fd, char * output_data);
465
466typedef void (*editdFunctionType)(char * byte_data, size_t filesize);
467
468typedef void (*multiEditdFunctionType)(const int fd);
469
470typedef void (*editdIndexFunctionType)(char * byte_data, size_t filesize, const char * pattern);
471
472static char * chStream;
473static size_t size;
474
475size_t file_size(const int fd) {
476    struct stat st;
477    if (LLVM_UNLIKELY(fstat(fd, &st) != 0)) {
478        st.st_size = 0;
479    }
480    return st.st_size;
481}
482
483char * preprocess(preprocessFunctionType fn_ptr) {
484    std::string fileName = inputFiles[0];
485    const int fd = open(inputFiles[0].c_str(), O_RDONLY);
486    if (LLVM_UNLIKELY(fd == -1)) {
487        std::cerr << "Error: cannot open " << fileName << " for processing. Skipped.\n";
488        exit(-1);
489    }
490    size = file_size(fd);
491    int ret = posix_memalign((void**)&chStream, 32, size);
492    if (ret) {
493        std::cerr << "Cannot allocate memory for output.\n";
494        exit(-2);
495    }
496    fn_ptr(fd, chStream);
497    close(fd);
498    return chStream;
499}
500
501void editd(editdFunctionType fn_ptr, char * inputStream, size_t size) {
502    fn_ptr(inputStream, size);
503}
504
505std::mutex count_mutex;
506size_t groupCount;
507void * DoEditd(void *)
508{
509    size_t groupIdx;
510    count_mutex.lock();
511    groupIdx = groupCount;
512    groupCount++;
513    count_mutex.unlock();
514
515    while (groupIdx < pattGroups.size()){
516
517        ParabixDriver pxDriver("editd");
518        editdPipeline(pxDriver, pattGroups[groupIdx]);
519        auto editd_ptr = reinterpret_cast<editdFunctionType>(pxDriver.getMain());
520        editd(editd_ptr, chStream, size);
521
522        count_mutex.lock();
523        groupIdx = groupCount;
524        groupCount++;
525        count_mutex.unlock();
526    }
527
528    pthread_exit(NULL);
529}
530
531#ifdef CUDA_ENABLED
532void editdGPUCodeGen(unsigned patternLen){
533    NVPTXDriver pxDriver("editd");
534    auto & iBuilder = pxDriver.getBuilder();
535    Module * M = iBuilder->getModule();
536
537    const unsigned segmentSize = codegen::SegmentSize;
538
539    Type * const mBitBlockType = iBuilder->getBitBlockType();
540    Type * const inputSizeTy = PointerType::get(iBuilder->getSizeTy(), 1);
541    Type * const int32ty = iBuilder->getInt32Ty();
542    Type * const voidTy = Type::getVoidTy(M->getContext());
543    Type * const inputTy = PointerType::get(ArrayType::get(mBitBlockType, 4), 1);
544    Type * const patternPtrTy = PointerType::get(iBuilder->getInt8Ty(), 1);
545    Type * const outputTy = PointerType::get(ArrayType::get(mBitBlockType, editDistance+1), 1);
546    Type * const stridesTy = PointerType::get(int32ty, 1);
547
548    Function * const main = cast<Function>(M->getOrInsertFunction("Main", voidTy, inputTy, inputSizeTy, patternPtrTy, outputTy, stridesTy, nullptr));
549    main->setCallingConv(CallingConv::C);
550    auto args = main->arg_begin();
551
552    Value * const inputStream = &*(args++);
553    inputStream->setName("input");
554    Value * const inputSizePtr = &*(args++);
555    inputSizePtr->setName("inputSizePtr");
556    Value * const pattStream = &*(args++);
557    pattStream->setName("pattStream");
558    Value * const resultStream = &*(args++);
559    resultStream->setName("resultStream");
560    Value * const stridesPtr = &*(args++);
561    stridesPtr->setName("stridesPtr");
562
563    iBuilder->SetInsertPoint(BasicBlock::Create(M->getContext(), "entry", main,0));
564
565    Function * tidFunc = M->getFunction("llvm.nvvm.read.ptx.sreg.tid.x");
566    Value * tid = iBuilder->CreateCall(tidFunc);
567    Function * bidFunc = cast<Function>(M->getOrInsertFunction("llvm.nvvm.read.ptx.sreg.ctaid.x", int32ty, nullptr));
568    Value * bid = iBuilder->CreateCall(bidFunc);
569
570    Value * inputThreadPtr = iBuilder->CreateGEP(inputStream, tid);
571    Value * strides = iBuilder->CreateLoad(stridesPtr);
572    Value * outputBlocks = iBuilder->CreateMul(strides, ConstantInt::get(int32ty, iBuilder->getStride() / iBuilder->getBitBlockWidth()));
573    Value * resultStreamPtr = iBuilder->CreateGEP(resultStream, iBuilder->CreateAdd(iBuilder->CreateMul(bid, outputBlocks), tid));
574    Value * inputSize = iBuilder->CreateLoad(inputSizePtr);
575
576    auto CCStream = pxDriver.addBuffer<ExternalBuffer>(iBuilder, iBuilder->getStreamSetTy(4), 1);
577    auto sourceK = pxDriver.addKernelInstance<kernel::MemorySourceKernel>(iBuilder, inputTy, segmentSize);
578    sourceK->setInitialArguments({inputThreadPtr, inputSize});
579    pxDriver.makeKernelCall(sourceK, {}, {CCStream});
580
581    auto ResultStream = pxDriver.addBuffer<ExternalBuffer>(iBuilder, iBuilder->getStreamSetTy(editDistance+1), resultStreamPtr, 1);
582    auto editdk = pxDriver.addKernelInstance<kernel::editdGPUKernel>(iBuilder, editDistance, patternLen, groupSize);
583     
584    const unsigned numOfCarries = patternLen * (editDistance + 1) * 4 * groupSize;
585    Type * strideCarryTy = ArrayType::get(mBitBlockType, numOfCarries);
586    Value * strideCarry = iBuilder->CreateAlloca(strideCarryTy);
587    iBuilder->CreateStore(Constant::getNullValue(strideCarryTy), strideCarry);
588
589    editdk->setInitialArguments({pattStream, strideCarry});
590    pxDriver.makeKernelCall(editdk, {CCStream}, {ResultStream});
591
592    pxDriver.generatePipelineIR();
593    pxDriver.deallocateBuffers();
594    iBuilder->CreateRetVoid();
595
596    pxDriver.finalizeObject();
597
598}
599
600void mergeGPUCodeGen(){
601    NVPTXDriver pxDriver("merge");
602    auto & iBuilder = pxDriver.getBuilder();
603    Module * M = iBuilder->getModule();
604
605    Type * const mBitBlockType = iBuilder->getBitBlockType();
606    Type * const int32ty = iBuilder->getInt32Ty();
607    Type * const voidTy = Type::getVoidTy(M->getContext());
608    Type * const resultTy = PointerType::get(ArrayType::get(mBitBlockType, editDistance+1), 1);
609    Type * const stridesTy = PointerType::get(int32ty, 1);
610
611    Function * const main = cast<Function>(M->getOrInsertFunction("Main", voidTy, resultTy, stridesTy, nullptr));
612    main->setCallingConv(CallingConv::C);
613    Function::arg_iterator args = main->arg_begin();
614
615    Value * const resultStream = &*(args++);
616    resultStream->setName("resultStream");
617    Value * const stridesPtr = &*(args++);
618    stridesPtr->setName("stridesPtr");
619
620    BasicBlock * entryBlock = BasicBlock::Create(iBuilder->getContext(), "entryBlock", main, 0);
621    BasicBlock * strideLoopCond = BasicBlock::Create(iBuilder->getContext(), "strideLoopCond", main, 0);
622    BasicBlock * strideLoopBody = BasicBlock::Create(iBuilder->getContext(), "strideLoopBody", main, 0);
623    BasicBlock * stridesDone = BasicBlock::Create(iBuilder->getContext(), "stridesDone", main, 0);
624
625    iBuilder->SetInsertPoint(entryBlock);
626
627    Function * tidFunc = M->getFunction("llvm.nvvm.read.ptx.sreg.tid.x");
628    Value * tid = iBuilder->CreateCall(tidFunc);
629    Function * bidFunc = cast<Function>(M->getOrInsertFunction("llvm.nvvm.read.ptx.sreg.ctaid.x", int32ty, nullptr));
630    Value * bid = iBuilder->CreateCall(bidFunc);
631
632    Value * strides = iBuilder->CreateLoad(stridesPtr);
633    Value * strideBlocks = ConstantInt::get(int32ty, iBuilder->getStride() / iBuilder->getBitBlockWidth());
634    Value * outputBlocks = iBuilder->CreateMul(strides, strideBlocks);
635    Value * resultStreamPtr = iBuilder->CreateGEP(resultStream, tid);
636
637    iBuilder->CreateBr(strideLoopCond);
638    iBuilder->SetInsertPoint(strideLoopCond);
639    PHINode * strideNo = iBuilder->CreatePHI(int32ty, 2, "strideNo");
640    strideNo->addIncoming(ConstantInt::get(int32ty, 0), entryBlock);
641    Value * notDone = iBuilder->CreateICmpULT(strideNo, strides);
642    iBuilder->CreateCondBr(notDone, strideLoopBody, stridesDone);
643
644    iBuilder->SetInsertPoint(strideLoopBody);
645    Value * myResultStreamPtr = iBuilder->CreateGEP(resultStreamPtr, {iBuilder->CreateMul(strideBlocks, strideNo)});
646    Value * myResultStream = iBuilder->CreateLoad(iBuilder->CreateGEP(myResultStreamPtr, {iBuilder->getInt32(0), bid}));
647    for (int i=1; i<codegen::GroupNum; i++){
648        Value * nextStreamPtr = iBuilder->CreateGEP(myResultStreamPtr, {iBuilder->CreateMul(outputBlocks, iBuilder->getInt32(i)), bid});
649        myResultStream = iBuilder->CreateOr(myResultStream, iBuilder->CreateLoad(nextStreamPtr));
650    }
651    iBuilder->CreateStore(myResultStream, iBuilder->CreateGEP(myResultStreamPtr, {iBuilder->getInt32(0), bid}));
652    strideNo->addIncoming(iBuilder->CreateAdd(strideNo, ConstantInt::get(int32ty, 1)), strideLoopBody);
653    iBuilder->CreateBr(strideLoopCond);
654
655    iBuilder->SetInsertPoint(stridesDone);
656    iBuilder->CreateRetVoid();
657
658    pxDriver.finalizeObject();
659
660}
661#endif
662
663editdFunctionType editdScanCPUCodeGen(ParabixDriver & pxDriver) {
664   
665    auto & iBuilder = pxDriver.getBuilder();
666    Module * M = iBuilder->getModule();
667
668    Type * mBitBlockType = iBuilder->getBitBlockType();
669    Type * const size_ty = iBuilder->getSizeTy();
670    Type * const voidTy = Type::getVoidTy(M->getContext());
671    Type * const inputType = PointerType::get(ArrayType::get(mBitBlockType, editDistance+1), 0);
672
673    Function * const main = cast<Function>(M->getOrInsertFunction("Main", voidTy, inputType, size_ty, nullptr));
674    main->setCallingConv(CallingConv::C);
675    iBuilder->SetInsertPoint(BasicBlock::Create(M->getContext(), "entry", main, 0));
676    Function::arg_iterator args = main->arg_begin();
677    Value * const inputStream = &*(args++);
678    inputStream->setName("input");
679    Value * const fileSize = &*(args++);
680    fileSize->setName("fileSize");
681
682    StreamSetBuffer * MatchResults = pxDriver.addBuffer<ExternalBuffer>(iBuilder, iBuilder->getStreamSetTy(editDistance + 1));
683    kernel::Kernel * sourceK = pxDriver.addKernelInstance<kernel::MemorySourceKernel>(iBuilder, editDistance + 1, 8);
684    sourceK->setInitialArguments({inputStream, fileSize});
685    pxDriver.makeKernelCall(sourceK, {}, {MatchResults});
686
687    auto editdScanK = pxDriver.addKernelInstance<editdScanKernel>(iBuilder, editDistance);
688    pxDriver.makeKernelCall(editdScanK, {MatchResults}, {});
689    pxDriver.LinkFunction(*editdScanK, "wrapped_report_pos", &wrapped_report_pos);
690    pxDriver.generatePipelineIR();
691    pxDriver.deallocateBuffers();
692    iBuilder->CreateRetVoid();
693
694    pxDriver.finalizeObject();
695
696    return reinterpret_cast<editdFunctionType>(pxDriver.getMain());
697
698}
699
700int main(int argc, char *argv[]) {
701    codegen::ParseCommandLineOptions(argc, argv);
702    int pattern_segs = 0;
703    int total_len = 0;
704
705    get_editd_pattern(pattern_segs, total_len);
706
707    if (MultiEditdKernels) {
708        ParabixDriver pxDriver("editd");
709        multiEditdPipeline(pxDriver);
710        auto editd_ptr = reinterpret_cast<multiEditdFunctionType>(pxDriver.getMain());
711
712        std::string fileName = inputFiles[0];
713        const int fd = open(inputFiles[0].c_str(), O_RDONLY);
714        if (LLVM_UNLIKELY(fd == -1)) {
715            std::cerr << "Error: cannot open " << fileName << " for processing. Skipped.\n";
716            exit(-1);
717        }
718        editd_ptr(fd);
719        close(fd);
720        run_second_filter(pattern_segs, total_len, 0.15);
721        return 0;
722    }
723
724#ifdef CUDA_ENABLED
725    if (codegen::NVPTX)
726        codegen::BlockSize = 64;
727#endif
728
729    ParabixDriver pxDriver("preprocess");
730    preprocessPipeline(pxDriver);
731    auto preprocess_ptr = reinterpret_cast<preprocessFunctionType>(pxDriver.getMain());
732    preprocess(preprocess_ptr);
733
734#ifdef CUDA_ENABLED
735    if(codegen::NVPTX){
736
737        std::ifstream t(PatternFilename);
738        if (!t.is_open()) {
739            std::cerr << "Error: cannot open " << PatternFilename << " for processing. Skipped.\n";
740            exit(-1);
741        }
742        std::string patterns((std::istreambuf_iterator<char>(t)), std::istreambuf_iterator<char>());
743
744        editdGPUCodeGen(pattVector[0].length());
745        mergeGPUCodeGen();
746        ulong * rslt = RunPTX(PTXFilename, chStream, size, patterns.c_str(), patterns.length(), editDistance);
747
748        ParabixDriver scanDriver("scan");
749        editdFunctionType editd_ptr = editdScanCPUCodeGen(scanDriver);
750        editd(editd_ptr, (char*)rslt, size);
751
752        run_second_filter(pattern_segs, total_len, 0.15);
753
754        return 0;
755    }
756#endif
757
758    if(pattVector.size() == 1){
759
760        ParabixDriver pxDriver("editd");
761        editdPipeline(pxDriver, pattVector);
762        auto editd_ptr = reinterpret_cast<editdFunctionType>(pxDriver.getMain());
763        editd(editd_ptr, chStream, size);
764        std::cout << "total matches is " << matchList.size() << std::endl;
765    }
766    else{
767        if (Threads == 1) { 
768            if (EditdIndexPatternKernels) {
769                ParabixDriver pxDriver("editd");
770                editdIndexPatternPipeline(pxDriver, pattVector[0].length());
771                auto editd_ptr = reinterpret_cast<editdIndexFunctionType>(pxDriver.getMain());
772
773                for(unsigned i=0; i<pattVector.size(); i+=groupSize){
774                    std::string pattern = "";
775                    for (int j=0; j<groupSize; j++){
776                        pattern += pattVector[i+j];
777                    }
778                    editd_ptr(chStream, size, pattern.c_str());
779                }
780            }
781            else {
782                for(unsigned i=0; i<pattGroups.size(); i++){
783
784                    ParabixDriver pxDriver("editd");
785                    editdPipeline(pxDriver, pattGroups[i]);
786                    auto editd_ptr = reinterpret_cast<editdFunctionType>(pxDriver.getMain());
787                    editd(editd_ptr, chStream, size);
788                }
789            }
790        }
791        else{
792            const unsigned numOfThreads = Threads;
793            pthread_t threads[numOfThreads];
794            groupCount = 0;
795
796            for(unsigned long i = 0; i < numOfThreads; ++i){
797                const int rc = pthread_create(&threads[i], NULL, DoEditd, (void *)i);
798                if (rc) {
799                    llvm::report_fatal_error("Failed to create thread: code " + std::to_string(rc));
800                }
801            }
802
803            for(unsigned i = 0; i < numOfThreads; ++i) {
804                void * status = nullptr;
805                const int rc = pthread_join(threads[i], &status);
806                if (rc) {
807                    llvm::report_fatal_error("Failed to join thread: code " + std::to_string(rc));
808                }
809            }
810
811        }
812        run_second_filter(pattern_segs, total_len, 0.15);
813    }
814
815    return 0;
816}
Note: See TracBrowser for help on using the repository browser.