source: icGREP/icgrep-devel/icgrep/array-test.cpp @ 5366

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

Continued work on non-carry-collapsing mode support.

File size: 15.6 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 <IR_Gen/idisa_builder.h>                  // for IDISA_Builder
8#include <IR_Gen/idisa_target.h>                   // for GetIDISA_Builder
9#include <kernels/mmap_kernel.h>                   // for MMapSourceKernel
10#include <kernels/s2p_kernel.h>                    // for S2PKernel
11#include <kernels/alignedprint.h>
12#include <kernels/streamset.h>                     // for SingleBlockBuffer
13#include <kernels/pipeline.h>
14#include <llvm/ExecutionEngine/ExecutionEngine.h>  // for ExecutionEngine
15#include <llvm/IR/Function.h>                      // for Function, Function...
16#include <llvm/IR/Module.h>                        // for Module
17#include <llvm/IR/Verifier.h>                      // for verifyModule
18#include <llvm/Support/CommandLine.h>              // for ParseCommandLineOp...
19#include <llvm/Support/raw_ostream.h>              // for errs
20#include <pablo/pablo_kernel.h>                    // for PabloKernel
21#include <pablo/pe_zeroes.h>
22#include <pablo/pe_ones.h>
23#include <toolchain.h>                             // for JIT_to_ExecutionEn...
24#include <pablo/builder.hpp>                       // for PabloBuilder
25#include <boost/filesystem.hpp>
26#include <boost/iostreams/device/mapped_file.hpp>
27#include "llvm/ADT/StringRef.h"                    // for StringRef
28#include "llvm/IR/CallingConv.h"                   // for ::C
29#include "llvm/IR/DerivedTypes.h"                  // for ArrayType
30#include "llvm/IR/LLVMContext.h"                   // for LLVMContext
31#include "llvm/IR/Value.h"                         // for Value
32#include "llvm/Support/Debug.h"                    // for dbgs
33#include <pablo/pablo_toolchain.h>
34#include <iostream>
35
36namespace llvm { class Type; }
37namespace pablo { class Integer; }
38namespace pablo { class Var; }
39
40using namespace pablo;
41using namespace kernel;
42using namespace parabix;
43using namespace llvm;
44
45static cl::list<std::string> inputFiles(cl::Positional, cl::desc("<input file ...>"), cl::OneOrMore);
46
47//void generate(PabloKernel * kernel) {
48
49//    PabloBuilder pb(kernel->getEntryBlock());
50
51//    Var * input = kernel->getInputStreamVar("input");
52
53//    PabloAST * basis[8];
54//    for (int i = 0; i < 8; ++i) {
55//        basis[i] = pb.createExtract(input, i);
56//    }
57
58//    PabloAST * temp1 = pb.createOr(basis[0], basis[1], "temp1");
59//    PabloAST * temp2 = pb.createAnd(basis[2], pb.createNot(basis[3]), "temp2");
60//    PabloAST * temp3 = pb.createAnd(temp2, pb.createNot(temp1), "temp3");
61//    PabloAST * temp4 = pb.createAnd(basis[4], pb.createNot(basis[5]), "temp4");
62//    PabloAST * temp5 = pb.createOr(basis[6], basis[7], "temp5");
63//    PabloAST * temp6 = pb.createAnd(temp4, pb.createNot(temp5), "temp6");
64//    PabloAST * lparen = pb.createAnd(temp3, temp6, "lparens");
65//    PabloAST * temp7 = pb.createAnd(basis[7], pb.createNot(basis[6]), "temp7");
66//    PabloAST * temp8 = pb.createAnd(temp4, temp7, "temp8");
67//    PabloAST * rparen = pb.createAnd(temp3, temp8, "rparens");
68//    PabloAST * parens = pb.createOr(lparen, rparen, "parens");
69
70
71//    Var * const pending_lparen = pb.createVar("pending_lparen", lparen);
72//    Var * const all_closed = pb.createVar("all_closed", pb.createZeroes());
73//    Var * const accumulated_errors = pb.createVar("accumulated_errors", pb.createZeroes());
74//    Var * const in_play = pb.createVar("in_play", parens);
75//    Var * const index = pb.createVar("i", pb.getInteger(0));
76
77//    Var * matches = kernel->getOutputStreamVar("matches");
78
79//    PabloBuilder body = PabloBuilder::Create(pb);
80//    PabloBuilder ifPScan = PabloBuilder::Create(body);
81
82//    pb.createWhile(pending_lparen, body);
83
84//        PabloAST * adv_pending_lparen = body.createAdvance(pending_lparen, 1);
85
86//        Var * closed_rparen = body.createVar("closed_rparen", pb.createZeroes());
87
88//        body.createIf(adv_pending_lparen, ifPScan); // <-- inefficient but tests whether we're probably calculating the summary later
89
90//            PabloAST * pscan = ifPScan.createScanTo(adv_pending_lparen, in_play, "pscan");
91
92//            ifPScan.createAssign(pending_lparen, ifPScan.createAnd(pscan, lparen));
93
94//            ifPScan.createAssign(closed_rparen, ifPScan.createAnd(pscan, rparen));
95
96//            ifPScan.createAssign(all_closed, ifPScan.createOr(all_closed, closed_rparen));
97
98//            // Mark any opening paren without a matching closer as an error.
99//            PabloAST * unmatched_lparen = ifPScan.createAtEOF(pscan, "unmatched_lparen");
100//            ifPScan.createAssign(accumulated_errors, ifPScan.createOr(accumulated_errors, unmatched_lparen));
101
102//            PabloAST * pending_rparen = ifPScan.createAnd(rparen, ifPScan.createNot(all_closed, "open_rparen"), "pending_rparen");
103
104//            ifPScan.createAssign(in_play, ifPScan.createOr(pending_lparen, pending_rparen));
105
106//        body.createAssign(body.createExtract(matches, index), closed_rparen);
107
108//        body.createAssign(index, body.createAdd(index, body.getInteger(1)));
109
110//    // Mark any closing paren that was not actually used to close an opener as an error.
111//    PabloAST * const unmatched_rparen = pb.createAnd(rparen, pb.createNot(all_closed), "unmatched_rparen");
112//    pb.createAssign(kernel->getOutputStreamVar("errors"), pb.createOr(accumulated_errors, unmatched_rparen));
113
114//}
115
116void generate(PabloKernel * kernel) {
117
118    PabloBuilder pb(kernel->getEntryBlock());
119
120    Var * input = kernel->getInputStreamVar("input");
121
122    PabloAST * basis[8];
123    for (int i = 0; i < 8; ++i) {
124        basis[i] = pb.createExtract(input, i);
125    }
126
127    PabloAST * temp1 = pb.createOr(basis[0], basis[1], "temp1");
128    PabloAST * temp2 = pb.createAnd(basis[2], pb.createNot(basis[3]), "temp2");
129    PabloAST * temp3 = pb.createAnd(temp2, pb.createNot(temp1), "temp3");
130    PabloAST * temp4 = pb.createAnd(basis[4], pb.createNot(basis[5]), "temp4");
131    PabloAST * temp5 = pb.createOr(basis[6], basis[7], "temp5");
132    PabloAST * temp6 = pb.createAnd(temp4, pb.createNot(temp5), "temp6");
133    PabloAST * lparen = pb.createAnd(temp3, temp6, "lparens");
134    PabloAST * temp7 = pb.createAnd(basis[7], pb.createNot(basis[6]), "temp7");
135    PabloAST * temp8 = pb.createAnd(temp4, temp7, "temp8");
136    PabloAST * rparen = pb.createAnd(temp3, temp8, "rparens");
137    PabloAST * parens = pb.createOr(lparen, rparen, "parens");
138
139
140    Var * const pending_lparen = pb.createVar("pending_lparen", lparen);
141    Var * const all_closed = pb.createVar("all_closed", pb.createZeroes());
142    Var * const accumulated_errors = pb.createVar("accumulated_errors", pb.createZeroes());
143    Var * const in_play = pb.createVar("in_play", parens);
144    Var * const index = pb.createVar("i", pb.getInteger(0));
145
146    Var * matches = kernel->getOutputStreamVar("matches");
147
148    PabloBuilder body = PabloBuilder::Create(pb);
149    PabloBuilder ifPScan = PabloBuilder::Create(body);
150
151    pb.createWhile(pending_lparen, body);
152
153        PabloAST * pscan = body.createAdvanceThenScanTo(pending_lparen, in_play, "pscan");
154
155        Var * closed_rparen = body.createVar("closed_rparen", pb.createZeroes());
156
157        body.createAssign(pending_lparen, body.createAnd(pscan, lparen));
158
159        body.createIf(pscan, ifPScan);
160
161            ifPScan.createAssign(closed_rparen, ifPScan.createAnd(pscan, rparen));
162
163            ifPScan.createAssign(all_closed, ifPScan.createOr(all_closed, closed_rparen));
164
165            // Mark any opening paren without a matching closer as an error.
166            PabloAST * unmatched_lparen = ifPScan.createAtEOF(pscan, "unmatched_lparen");
167            ifPScan.createAssign(accumulated_errors, ifPScan.createOr(accumulated_errors, unmatched_lparen));
168
169            PabloAST * pending_rparen = ifPScan.createAnd(rparen, ifPScan.createNot(all_closed, "open_rparen"), "pending_rparen");
170
171            ifPScan.createAssign(in_play, ifPScan.createOr(pending_lparen, pending_rparen));
172
173            ifPScan.createAssign(ifPScan.createExtract(matches, index), closed_rparen);
174
175        body.createAssign(index, body.createAdd(index, body.getInteger(1)));
176
177    // Mark any closing paren that was not actually used to close an opener as an error.
178    PabloAST * const unmatched_rparen = pb.createAnd(rparen, pb.createNot(all_closed), "unmatched_rparen");
179    pb.createAssign(kernel->getOutputStreamVar("errors"), pb.createOr(accumulated_errors, unmatched_rparen));
180
181}
182
183//void generate(PabloKernel * kernel) {
184
185//    PabloBuilder pb(kernel->getEntryBlock());
186
187//    Var * input = kernel->getInputStreamVar("input");
188
189//    PabloAST * basis[8];
190//    for (int i = 0; i < 8; ++i) {
191//        basis[i] = pb.createExtract(input, i);
192//    }
193
194//    PabloAST * temp1 = pb.createOr(basis[0], basis[1], "temp1");
195//    PabloAST * temp2 = pb.createAnd(basis[2], pb.createNot(basis[3]), "temp2");
196//    PabloAST * temp3 = pb.createAnd(temp2, pb.createNot(temp1), "temp3");
197//    PabloAST * temp4 = pb.createAnd(basis[4], pb.createNot(basis[5]), "temp4");
198//    PabloAST * temp5 = pb.createOr(basis[6], basis[7], "temp5");
199//    PabloAST * temp6 = pb.createAnd(temp4, pb.createNot(temp5), "temp6");
200//    PabloAST * lparen = pb.createAnd(temp3, temp6, "lparens");
201//    PabloAST * temp7 = pb.createAnd(basis[7], pb.createNot(basis[6]), "temp7");
202//    PabloAST * temp8 = pb.createAnd(temp4, temp7, "temp8");
203//    PabloAST * rparen = pb.createAnd(temp3, temp8, "rparens");
204//    PabloAST * parens = pb.createOr(lparen, rparen, "parens");
205
206
207//    Var * const pending_lparen = pb.createVar("pending_lparen", lparen);
208//    Var * const all_closed = pb.createVar("all_closed", pb.createZeroes());
209//    Var * const accumulated_errors = pb.createVar("accumulated_errors", pb.createZeroes());
210//    Var * const in_play = pb.createVar("in_play", parens);
211//    Var * const index = pb.createVar("i", pb.getInteger(0));
212
213//    Var * matches = kernel->getOutputStreamVar("matches");
214
215//    PabloBuilder body = PabloBuilder::Create(pb);
216
217//    pb.createWhile(pending_lparen, body);
218
219//        PabloAST * pscan = body.createAdvanceThenScanTo(pending_lparen, in_play, "pscan");
220
221//        PabloAST * closed_rparen = body.createAnd(pscan, rparen, "closed_rparen");
222//        body.createAssign(all_closed, body.createOr(all_closed, closed_rparen));
223
224//        body.createAssign(pending_lparen, body.createAnd(pscan, lparen));
225//        // Mark any opening paren without a matching closer as an error.
226//        PabloAST * unmatched_lparen = body.createAtEOF(pscan, "unmatched_lparen");
227//        body.createAssign(accumulated_errors, body.createOr(accumulated_errors, unmatched_lparen));
228
229//        body.createAssign(body.createExtract(matches, index), closed_rparen);
230
231//        PabloAST * pending_rparen = body.createAnd(rparen, body.createNot(all_closed, "open_rparen"), "pending_rparen");
232//        body.createAssign(in_play, body.createOr(pending_lparen, pending_rparen));
233//        body.createAssign(index, body.createAdd(index, body.getInteger(1)));
234
235//    // Mark any closing paren that was not actually used to close an opener as an error.
236//    PabloAST * const unmatched_rparen = pb.createAnd(rparen, pb.createNot(all_closed), "unmatched_rparen");
237//    pb.createAssign(kernel->getOutputStreamVar("errors"), pb.createOr(accumulated_errors, unmatched_rparen));
238
239//}
240
241Function * pipeline(IDISA::IDISA_Builder * iBuilder, const unsigned count) {
242
243    Type * byteStreamTy = iBuilder->getStreamSetTy(1, 8);
244
245    Module * const mod = iBuilder->getModule();
246
247    Function * const main = cast<Function>(mod->getOrInsertFunction("Main", iBuilder->getVoidTy(), byteStreamTy->getPointerTo(), iBuilder->getSizeTy(), nullptr));
248    main->setCallingConv(CallingConv::C);
249    Function::arg_iterator args = main->arg_begin();
250   
251    Value * const inputStream = &*(args++);
252    inputStream->setName("input");
253    Value * const fileSize = &*(args++);
254    fileSize->setName("fileSize");
255
256    const unsigned segmentSize = codegen::SegmentSize;
257    const unsigned bufferSegments = codegen::BufferSegments;
258   
259    ExternalFileBuffer ByteStream(iBuilder, iBuilder->getStreamSetTy(1, 8));
260
261    MMapSourceKernel mmapK(iBuilder, segmentSize);
262    mmapK.generateKernel({}, {&ByteStream});
263    mmapK.setInitialArguments({fileSize});
264
265    CircularBuffer BasisBits(iBuilder, iBuilder->getStreamSetTy(8), segmentSize * bufferSegments);
266
267    S2PKernel  s2pk(iBuilder);
268    s2pk.generateKernel({&ByteStream}, {&BasisBits});
269
270    PabloKernel bm(iBuilder, "MatchParens",
271        {Binding{iBuilder->getStreamSetTy(8), "input"}},
272        {Binding{iBuilder->getStreamSetTy(count), "matches"}, Binding{iBuilder->getStreamTy(), "errors"}});
273
274    generate(&bm);
275    pablo_function_passes(&bm);
276
277    ExpandableBuffer matches(iBuilder, iBuilder->getStreamSetTy(count), segmentSize * bufferSegments);
278    SingleBlockBuffer errors(iBuilder, iBuilder->getStreamTy());
279
280    bm.generateKernel({&BasisBits}, {&matches, &errors});
281
282    PrintStreamSet printer(iBuilder, {"matches", "errors"});
283    printer.generateKernel({&matches, &errors}, {});
284
285    iBuilder->SetInsertPoint(BasicBlock::Create(mod->getContext(), "entry", main, 0));
286
287    ByteStream.setStreamSetBuffer(inputStream, fileSize);
288    BasisBits.allocateBuffer();
289    matches.allocateBuffer();
290    errors.allocateBuffer();
291
292    generatePipeline(iBuilder, {&mmapK, &s2pk, &bm, &printer});
293    iBuilder->CreateRetVoid();
294
295    return main;
296}
297
298typedef void (*MatchParens)(char * byteStream, size_t fileSize);
299
300MatchParens generateAlgorithm() {
301    LLVMContext ctx;
302    Module * M = new Module("mp", ctx);
303    IDISA::IDISA_Builder * idb = IDISA::GetIDISA_Builder(M);
304
305    llvm::Function * f = pipeline(idb, 3);
306
307    verifyModule(*M, &dbgs());
308
309    ExecutionEngine * wcEngine = JIT_to_ExecutionEngine(M);
310
311    wcEngine->finalizeObject();
312
313    delete idb;
314
315    return reinterpret_cast<MatchParens>(wcEngine->getPointerToFunction(f));
316}
317
318template <typename T>
319std::ostream & operator<< (std::ostream& out, const std::vector<T>& v) {
320  if ( !v.empty() ) {
321    out << '[';
322    std::copy (v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
323    out << "\b\b]";
324  }
325  return out;
326}
327
328void check(const char * byteStream, const size_t fileSize) {
329
330    std::vector<size_t> unmatched_left;
331    std::vector<size_t> unmatched_right;
332    size_t maxDepth = 0;
333    for (size_t i = 0; i < fileSize; ++i) {
334        switch (byteStream[i]) {
335            case '(':
336                unmatched_left.push_back(i);
337                maxDepth = std::max<size_t>(maxDepth, unmatched_left.size());
338                break;
339            case ')':
340                if (unmatched_left.empty()) {
341                    unmatched_right.push_back(i);
342                } else {
343                    unmatched_left.pop_back();
344                }
345            default:
346                break;
347        }
348    }
349
350    std::cerr << "maximum depth:        " << maxDepth << "\n"
351                 "invalid left parens:  " << unmatched_left << "\n"
352                 "invalid right parens: " << unmatched_right <<
353                 std::endl;
354}
355
356void run(MatchParens match, const std::string & fileName) {
357    const boost::filesystem::path file(fileName);
358    if (exists(file)) {
359        if (is_directory(file)) {
360            return;
361        }
362        size_t fileSize = file_size(file);
363        boost::iostreams::mapped_file_source mappedFile;
364        if (fileSize > 0) {
365            mappedFile.open(fileName);
366            char * fileBuffer = const_cast<char *>(mappedFile.data());
367            check(fileBuffer, fileSize);
368            match(fileBuffer, fileSize);
369            mappedFile.close();
370        }
371    } else {
372        std::cerr << "Error: cannot open " << fileName << " for processing. Skipped.\n";
373    }
374}
375
376int main(int argc, char *argv[]) {
377    cl::ParseCommandLineOptions(argc, argv);
378    auto f = generateAlgorithm();
379    for (const auto & inputFile : inputFiles) {
380        run(f, inputFile);
381    }
382    return 0;
383}
Note: See TracBrowser for help on using the repository browser.