source: icGREP/icgrep-devel/icgrep/kernels/symboltablepipeline.cpp @ 4968

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

Some fixes for threading and kernel builder.

File size: 15.5 KB
Line 
1#include "symboltablepipeline.h"
2
3/*
4 *  Copyright (c) 2016 International Characters.
5 *  This software is licensed to the public under the Open Software License 3.0.
6 */
7
8#include "pipeline.h"
9#include "toolchain.h"
10#include "utf_encoding.h"
11
12#include <kernels/scanmatchgen.h>
13#include <kernels/s2p_kernel.h>
14
15#include <pablo/function.h>
16#include <pablo/pablo_compiler.h>
17
18#include <re/re_cc.h>
19#include <re/re_rep.h>
20#include <re/re_name.h>
21#include <re/re_compiler.h>
22#include <re/printer_re.h>
23
24#include <cc/cc_compiler.h>
25
26#include <pablo/printer_pablos.h>
27#include <iostream>
28
29using namespace re;
30using namespace pablo;
31
32SymbolTableBuilder::SymbolTableBuilder(Module * m, IDISA::IDISA_Builder * b)
33: mMod(m)
34, iBuilder(b)
35, mFileBufIdx(7)
36, mFileSizeIdx(8)
37, mFileNameIdx(9)
38, mLongestLookahead(0)
39, mBitBlockType(b->getBitBlockType())
40, mBlockSize(b->getBitBlockWidth()){
41
42}
43
44/** ------------------------------------------------------------------------------------------------------------- *
45 * @brief generateLeadingFunction
46 ** ------------------------------------------------------------------------------------------------------------- */
47PabloFunction * SymbolTableBuilder::generateLeadingFunction(const std::vector<unsigned> & endpoints) {
48    PabloFunction * const function = PabloFunction::Create("leading", 8, endpoints.size() + 2);
49    Encoding enc(Encoding::Type::ASCII, 8);
50    cc::CC_Compiler ccCompiler(*function, enc);
51    re::RE_Compiler reCompiler(*function, ccCompiler);
52    RE * cc = makeName(makeCC(makeCC(65, 90), makeCC(97, 122)));
53    reCompiler.compileUnicodeNames(cc);
54    PabloAST * const matches = reCompiler.compile(cc).stream;
55    PabloBlock * const entry = function->getEntryBlock();
56    PabloAST * const adv = entry->createAdvance(matches, 1);
57    PabloAST * const starts = entry->createAnd(matches, entry->createNot(adv));
58    PabloAST * const ends = entry->createAnd(adv, entry->createNot(matches));
59
60    function->setResult(0, entry->createAssign("S", starts));
61    function->setResult(1, entry->createAssign("E", ends));
62
63    PabloAST * M = ends;
64    unsigned step = 1;
65    unsigned i = 0;
66    for (unsigned endpoint : endpoints) {
67        assert (endpoint >= step);
68        unsigned span = endpoint - step;
69        while (span > step) {
70            M = entry->createOr(entry->createAdvance(M, step), M);
71            span = span - step;
72            step *= 2;
73        }
74        M = entry->createOr(entry->createAdvance(M, span), M);
75        function->setResult(i + 2, entry->createAssign("M" + std::to_string(i), M));
76        ++i;
77        step += span;
78    }
79
80    return function;
81}
82
83/** ------------------------------------------------------------------------------------------------------------- *
84 * @brief generateSortingFunction
85 ** ------------------------------------------------------------------------------------------------------------- */
86PabloFunction * SymbolTableBuilder::generateSortingFunction(const PabloFunction * const leading, const std::vector<unsigned> & endpoints) {
87    PabloFunction * const function = PabloFunction::Create("sorting", leading->getNumOfResults(), leading->getNumOfResults() * 2);
88    PabloBlock * const entry = function->getEntryBlock();
89    function->setParameter(0, entry->createVar("S"));
90    function->setParameter(1, entry->createVar("E"));
91    for (unsigned i = 2; i < leading->getNumOfResults(); ++i) {
92        function->setParameter(i, entry->createVar("M" + std::to_string(i - 2)));
93    }
94    PabloAST * R = function->getParameter(0);
95    PabloAST * const E = entry->createNot(function->getParameter(1));
96    unsigned i = 1;
97    unsigned lowerbound = 0;
98    for (unsigned endpoint : endpoints) {
99        PabloAST * const M = function->getParameter(i + 1);
100        PabloAST * const L = entry->createLookahead(M, endpoint);
101        PabloAST * S = entry->createAnd(L, R);
102        Assign * Si = entry->createAssign("S_" + std::to_string(i), S);
103        R = entry->createXor(R, S);
104        PabloAST * F = entry->createScanThru(R, E);
105        Assign * Ei = entry->createAssign("E_" + std::to_string(i), F);
106        function->setResult(i * 2, Si);
107        function->setResult(i * 2 + 1, Ei);
108        ++i;
109        lowerbound = endpoint;
110    }
111    Assign * Si = entry->createAssign("S_n", R);
112    PabloAST * F = entry->createScanThru(R, E);
113    Assign * Ei = entry->createAssign("E_n", F);
114    function->setResult(i * 2, Si);
115    function->setResult(i * 2 + 1, Ei);
116    mLongestLookahead = lowerbound;
117    return function;
118}
119
120/** ------------------------------------------------------------------------------------------------------------- *
121 * @brief createKernels
122 ** ------------------------------------------------------------------------------------------------------------- */
123void SymbolTableBuilder::createKernels() {
124
125    std::vector<unsigned> endpoints;
126    endpoints.push_back(1);
127    endpoints.push_back(2);
128    endpoints.push_back(4);
129    endpoints.push_back(8);
130    endpoints.push_back(16);
131
132    PabloCompiler pablo_compiler(mMod, iBuilder);
133
134    raw_os_ostream out(std::cerr);
135
136    out << "LEADING:\n";
137    PabloFunction * const leading = generateLeadingFunction(endpoints);
138    PabloPrinter::print(*leading, out);
139
140    out << "\n\nSORTING:\n";
141    PabloFunction * const sorting = generateSortingFunction(leading, endpoints);
142    PabloPrinter::print(*sorting, out);
143
144    out.flush();
145
146    mS2PKernel = new KernelBuilder("s2p", mMod, iBuilder);
147    mLeadingKernel = new KernelBuilder("leading", mMod, iBuilder);
148    mSortingKernel = new KernelBuilder("sorting", mMod, iBuilder);
149
150    mLeadingKernel->setLongestLookaheadAmount(mLongestLookahead);
151    mSortingKernel->setLongestLookaheadAmount(mLongestLookahead);
152
153    generateS2PKernel(mMod, iBuilder, mS2PKernel);
154
155    pablo_compiler.setKernel(mLeadingKernel);
156    pablo_compiler.compile(leading);
157    pablo_compiler.setKernel(mSortingKernel);
158    pablo_compiler.compile(sorting);
159
160    delete leading;
161    delete sorting;
162
163    releaseSlabAllocatorMemory();
164}
165
166void SymbolTableBuilder::ExecuteKernels(){
167
168    Type * T = iBuilder->getIntNTy(64);
169    Type * S = PointerType::get(iBuilder->getIntNTy(8), 0);
170    Type * inputType = PointerType::get(ArrayType::get(StructType::get(mMod->getContext(), std::vector<Type *>({ArrayType::get(mBitBlockType, 8)})), 1), 0);
171    Function * const main = cast<Function>(mMod->getOrInsertFunction("Main", Type::getVoidTy(mMod->getContext()), inputType, T, nullptr));
172    main->setCallingConv(CallingConv::C);
173    Function::arg_iterator args = main->arg_begin();
174
175    Value * const input_param = args++;
176    input_param->setName("input");
177
178    Value * const bufferSize = args++;
179    bufferSize->setName("buffersize");
180
181    iBuilder->SetInsertPoint(BasicBlock::Create(mMod->getContext(), "entry", main,0));
182
183    BasicBlock * entryBlock = iBuilder->GetInsertBlock();
184
185    BasicBlock * leadingTestBlock = BasicBlock::Create(mMod->getContext(), "ltb", main, 0);
186    BasicBlock * leadingBodyBlock = BasicBlock::Create(mMod->getContext(), "lbb", main, 0);
187    BasicBlock * leadingExitBlock = BasicBlock::Create(mMod->getContext(), "leb", main, 0);
188
189    BasicBlock * regularTestBlock = BasicBlock::Create(mMod->getContext(), "rtb", main, 0);
190    BasicBlock * regularBodyBlock = BasicBlock::Create(mMod->getContext(), "rbb", main, 0);
191    BasicBlock * regularExitBlock = BasicBlock::Create(mMod->getContext(), "reb", main, 0);
192
193//    BasicBlock * pipeline_test_block = BasicBlock::Create(mMod->getContext(), "pipeline_test_block", main, 0);
194//    BasicBlock * pipeline_do_block = BasicBlock::Create(mMod->getContext(), "pipeline_do_block", main, 0);
195//    BasicBlock * pipeline_final_block = BasicBlock::Create(mMod->getContext(), "pipeline_final_block", main, 0);
196//    BasicBlock * pipeline_partial_block = BasicBlock::Create(mMod->getContext(), "pipeline_partial_block", main, 0);
197//    BasicBlock * pipeline_empty_block = BasicBlock::Create(mMod->getContext(), "pipeline_empty_block", main, 0);
198//    BasicBlock * pipeline_end_block = BasicBlock::Create(mMod->getContext(), "pipeline_end_block", main, 0);
199//    BasicBlock * pipeline_Unterminated_block = BasicBlock::Create(mMod->getContext(), "pipeline_Unterminated_block", main, 0);
200//    BasicBlock * pipeline_return_block = BasicBlock::Create(mMod->getContext(), "pipeline_return_block", main, 0);
201
202    Value * s2pKernelStruct = mS2PKernel->generateKernelInstance();
203    Value * leadingKernelStruct = mLeadingKernel->generateKernelInstance();
204    Value * sortingKernelStruct = mSortingKernel->generateKernelInstance();
205
206    Value * basis_bits = iBuilder->CreateGEP(s2pKernelStruct, {iBuilder->getInt32(0), iBuilder->getInt32(1)});
207    Value * leadingData = iBuilder->CreateGEP(leadingKernelStruct, {iBuilder->getInt32(0), iBuilder->getInt32(1)});
208
209
210    const unsigned leadingBlocks = (mLongestLookahead + iBuilder->getBitBlockWidth() - 1) / iBuilder->getBitBlockWidth();
211
212    // If the buffer size is smaller than our largest length group, only check up to the buffer size.
213    Value * safetyCheck = iBuilder->CreateICmpSLT(bufferSize, iBuilder->getInt64(leadingBlocks * iBuilder->getBitBlockWidth()));
214    iBuilder->CreateCondBr(safetyCheck, regularExitBlock, leadingTestBlock);
215
216    // Now process the leading blocks ...
217    iBuilder->SetInsertPoint(leadingTestBlock);
218    PHINode * remainingBytes = iBuilder->CreatePHI(T, 2, "remainingBytes");
219    PHINode * leadingOffset = iBuilder->CreatePHI(T, 2, "blockIndex");
220    remainingBytes->addIncoming(bufferSize, entryBlock);
221    leadingOffset->addIncoming(iBuilder->getInt64(0), entryBlock);
222    Value * remainingLeadingBlocksCond = iBuilder->CreateICmpULT(leadingOffset, iBuilder->getInt64(leadingBlocks));
223    iBuilder->CreateCondBr(remainingLeadingBlocksCond, leadingBodyBlock, leadingExitBlock);
224    iBuilder->SetInsertPoint(leadingBodyBlock);
225    Value * gep = iBuilder->CreateGEP(input_param, leadingOffset);
226    mS2PKernel->generateDoBlockCall(gep);
227    mLeadingKernel->generateDoBlockCall(basis_bits);
228    leadingOffset->addIncoming(iBuilder->CreateAdd(leadingOffset, iBuilder->getInt64(1)), leadingBodyBlock);
229    remainingBytes->addIncoming(iBuilder->CreateSub(remainingBytes, iBuilder->getInt64(mBlockSize)), leadingBodyBlock);
230    iBuilder->CreateBr(leadingTestBlock);
231    iBuilder->SetInsertPoint(leadingExitBlock);
232
233    // Now process the leading blocks ...
234    iBuilder->CreateBr(regularTestBlock);
235    iBuilder->SetInsertPoint(regularTestBlock);
236    PHINode * remainingBytes2 = iBuilder->CreatePHI(T, 2, "remainingBytes");
237    PHINode * leadingOffset2 = iBuilder->CreatePHI(T, 2, "blockIndex");
238    remainingBytes2->addIncoming(remainingBytes, leadingExitBlock);
239    leadingOffset2->addIncoming(leadingOffset, leadingExitBlock);
240    Value * remainingBytesCond = iBuilder->CreateICmpUGE(remainingBytes2, iBuilder->getInt64(mBlockSize));
241    iBuilder->CreateCondBr(remainingBytesCond, regularBodyBlock, regularExitBlock);
242    iBuilder->SetInsertPoint(regularBodyBlock);
243    Value * gep2 = iBuilder->CreateGEP(input_param, leadingOffset2);
244    mS2PKernel->generateDoBlockCall(gep2);
245    mLeadingKernel->generateDoBlockCall(basis_bits);
246    leadingOffset2->addIncoming(iBuilder->CreateAdd(leadingOffset2, iBuilder->getInt64(1)), regularBodyBlock);
247    remainingBytes2->addIncoming(iBuilder->CreateSub(remainingBytes2, iBuilder->getInt64(mBlockSize)), regularBodyBlock);
248    mSortingKernel->generateDoBlockCall(leadingData);
249    iBuilder->CreateBr(regularTestBlock);
250    iBuilder->SetInsertPoint(regularExitBlock);
251
252
253
254//    Value * gep = iBuilder->CreateGEP(sortingKernelStruct, {iBuilder->getInt32(0), iBuilder->getInt32(0), iBuilder->getInt32(mFileBufIdx)});
255//    Value* filebuf = iBuilder->CreateBitCast(input_param, S);
256//    iBuilder->CreateStore(filebuf, gep);
257
258//    gep = iBuilder->CreateGEP(sortingKernelStruct, {iBuilder->getInt32(0), iBuilder->getInt32(0), iBuilder->getInt32(mFileSizeIdx)});
259//    iBuilder->CreateStore(buffersize_param, gep);
260
261//    gep = iBuilder->CreateGEP(sortingKernelStruct, {iBuilder->getInt32(0), iBuilder->getInt32(0), iBuilder->getInt32(mFileNameIdx)});
262//    iBuilder->CreateStore(filename_param, gep);
263
264//    Value * basis_bits = iBuilder->CreateGEP(s2pKernelStruct, {iBuilder->getInt32(0), iBuilder->getInt32(1)});
265//    Value * results = iBuilder->CreateGEP(leadingKernelStruct, {iBuilder->getInt32(0), iBuilder->getInt32(1)});
266
267//    iBuilder->CreateBr(pipeline_test_block);
268
269//    iBuilder->SetInsertPoint(pipeline_test_block);
270//    PHINode * remaining_phi = iBuilder->CreatePHI(T, 2, "remaining");
271//    PHINode * blkNo_phi = iBuilder->CreatePHI(T, 2, "blkNo");
272//    remaining_phi->addIncoming(buffersize_param, entry_block);
273//    blkNo_phi->addIncoming(iBuilder->getInt64(0), entry_block);
274
275//    Value * final_block_cond = iBuilder->CreateICmpSLT(remaining_phi, ConstantInt::get(T, mBlockSize));
276//    iBuilder->CreateCondBr(final_block_cond, pipeline_final_block, pipeline_do_block);
277
278//    iBuilder->SetInsertPoint(pipeline_do_block);
279
280//    gep = iBuilder->CreateGEP(input_param, {blkNo_phi});
281//    Value * update_blkNo = iBuilder->CreateAdd(blkNo_phi, iBuilder->getInt64(1));
282//    blkNo_phi->addIncoming(update_blkNo, pipeline_do_block);
283
284//    mS2PKernel->generateDoBlockCall(gep);
285//    mICgrepKernel->generateDoBlockCall(basis_bits);
286//    mScanMatchKernel->generateDoBlockCall(results);
287
288//    Value * update_remaining = iBuilder->CreateSub(remaining_phi, iBuilder->getInt64(mBlockSize));
289//    remaining_phi->addIncoming(update_remaining, pipeline_do_block);
290//    iBuilder->CreateBr(pipeline_test_block);
291
292//    iBuilder->SetInsertPoint(pipeline_final_block);
293
294//    Value * empty_block_cond = iBuilder->CreateICmpEQ(remaining_phi, ConstantInt::get(T, 0));
295//    iBuilder->CreateCondBr(empty_block_cond, pipeline_empty_block, pipeline_partial_block);
296
297//    iBuilder->SetInsertPoint(pipeline_partial_block);
298
299//    gep = iBuilder->CreateGEP(input_param, {blkNo_phi});
300//    mS2PKernel->generateDoBlockCall(gep);
301//    iBuilder->CreateBr(pipeline_end_block);
302
303//    iBuilder->SetInsertPoint(pipeline_empty_block);
304
305//    iBuilder->CreateMemSet(basis_bits, iBuilder->getInt8(0), mBlockSize, 4);
306//    iBuilder->CreateBr(pipeline_end_block);
307
308//    iBuilder->SetInsertPoint(pipeline_end_block);
309
310//    Value * return_block_cond = iBuilder->CreateICmpEQ(finalLineUnterminated_param, ConstantInt::get(T, 0));
311//    iBuilder->CreateCondBr(return_block_cond, pipeline_return_block, pipeline_Unterminated_block);
312
313//    iBuilder->SetInsertPoint(pipeline_Unterminated_block);
314
315//    Value * remaining = iBuilder->CreateZExt(remaining_phi, iBuilder->getIntNTy(mBlockSize));
316//    Value * EOF_pos = iBuilder->CreateShl(ConstantInt::get(iBuilder->getIntNTy(mBlockSize), 1), remaining);
317//    EOF_pos = iBuilder->CreateBitCast(EOF_pos, mBitBlockType);
318
319//    Value * gep_bits4 = iBuilder->CreateGEP(basis_bits, {iBuilder->getInt32(0), iBuilder->getInt32(0), iBuilder->getInt32(4)});
320//    Value * bits4 = iBuilder->CreateAlignedLoad(gep_bits4, mBlockSize/8, false, "bits4");
321//    bits4 = iBuilder->CreateOr(bits4, EOF_pos);
322//    iBuilder->CreateAlignedStore(bits4, gep_bits4, mBlockSize/8, false);
323
324//    Value * gep_bits6 = iBuilder->CreateGEP(basis_bits, {iBuilder->getInt32(0), iBuilder->getInt32(0), iBuilder->getInt32(6)});
325//    Value * bits6 = iBuilder->CreateAlignedLoad(gep_bits6, mBlockSize/8, false, "bits6");
326//    bits6 = iBuilder->CreateOr(bits6, EOF_pos);
327//    iBuilder->CreateAlignedStore(bits6, gep_bits6, mBlockSize/8, false);
328//    iBuilder->CreateBr(pipeline_return_block);
329
330//    iBuilder->SetInsertPoint(pipeline_return_block);
331
332//    mICgrepKernel->generateDoBlockCall(basis_bits);
333//    mScanMatchKernel->generateDoBlockCall(results);
334    iBuilder->CreateRetVoid();
335
336
337    mMod->dump();
338}
339
340SymbolTableBuilder::~SymbolTableBuilder() {
341    delete mS2PKernel;
342    delete mLeadingKernel;
343    delete mSortingKernel;
344}
Note: See TracBrowser for help on using the repository browser.