source: icGREP/icgrep-devel/icgrep/kernels/source_kernel.cpp @ 5761

Last change on this file since 5761 was 5761, checked in by nmedfort, 17 months ago

Cache signature is now written into .kernel bitcode file. Minor bug fix and revision of GrepEngine::DoGrepThreadMethod?

File size: 18.5 KB
Line 
1/*
2 *  Copyright (c) 2017 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 */
5#include "source_kernel.h"
6#include <kernels/kernel_builder.h>
7#include <kernels/streamset.h>
8#include <llvm/IR/Module.h>
9#include <sys/stat.h>
10#include <fcntl.h>
11
12using namespace llvm;
13
14uint64_t file_size(const uint32_t fd) {
15    struct stat st;
16    if (LLVM_UNLIKELY(fstat(fd, &st) != 0)) {
17        st.st_size = 0;
18    }
19    return st.st_size;
20}
21
22namespace kernel {
23
24/// MMAP SOURCE KERNEL
25
26Function * MMapSourceKernel::linkFileSizeMethod(const std::unique_ptr<kernel::KernelBuilder> & kb) {
27    return kb->LinkFunction("file_size", &file_size);
28}
29
30void MMapSourceKernel::generateInitializeMethod(Function * const fileSizeMethod, const unsigned codeUnitWidth, const unsigned segmentSize, const std::unique_ptr<KernelBuilder> & kb) {
31    BasicBlock * const emptyFile = kb->CreateBasicBlock("EmptyFile");
32    BasicBlock * const nonEmptyFile = kb->CreateBasicBlock("NonEmptyFile");
33    BasicBlock * const exit = kb->CreateBasicBlock("Exit");
34    IntegerType * const sizeTy = kb->getSizeTy();
35    Value * const fd = kb->getScalarField("fileDescriptor");
36    assert (fileSizeMethod);
37    Value * fileSize = kb->CreateCall(fileSizeMethod, fd);
38    fileSize = kb->CreateZExtOrTrunc(fileSize, sizeTy);
39    if (codeUnitWidth > 8) {
40        fileSize = kb->CreateUDiv(fileSize, kb->getSize(codeUnitWidth / 8));
41    }
42    Value * const isEmpty = kb->CreateICmpEQ(fileSize, ConstantInt::getNullValue(fileSize->getType()));
43    kb->CreateUnlikelyCondBr(isEmpty, emptyFile, nonEmptyFile);
44    // we cannot mmap a 0 length file; just create a 1-page sized fake file buffer for simplicity
45    kb->SetInsertPoint(emptyFile);
46    Constant * const readSize = kb->getSize(segmentSize);
47    Value * const fakeFileBuffer = kb->CreateAnonymousMMap(readSize);
48    kb->CreateBr(exit);
49
50    kb->SetInsertPoint(nonEmptyFile);
51    Value * fileBackedBuffer = kb->CreateFileSourceMMap(fd, fileSize);
52    kb->CreateBr(exit);
53
54    kb->SetInsertPoint(exit);
55    PHINode * const buffer = kb->CreatePHI(fileBackedBuffer->getType(), 2);
56    buffer->addIncoming(fakeFileBuffer, emptyFile);
57    buffer->addIncoming(fileBackedBuffer, nonEmptyFile);
58    PHINode * const bufferSize = kb->CreatePHI(sizeTy, 2);
59    bufferSize->addIncoming(readSize, emptyFile);
60    bufferSize->addIncoming(fileSize, nonEmptyFile);
61
62    PointerType * const codeUnitPtrTy = kb->getIntNTy(codeUnitWidth)->getPointerTo();
63    Value * bufferPtr = kb->CreatePointerCast(buffer, codeUnitPtrTy);
64    kb->setScalarField("buffer", bufferPtr);
65    kb->setScalarField("fileSize", fileSize);
66
67    kb->setBaseAddress("sourceBuffer", bufferPtr);
68    kb->setBufferedSize("sourceBuffer", bufferSize);
69    kb->setCapacity("sourceBuffer", fileSize);
70    kb->CreateMAdvise(buffer, fileSize, CBuilder::ADVICE_WILLNEED);
71
72}
73
74void MMapSourceKernel::generateDoSegmentMethod(const unsigned codeUnitWidth, const unsigned segmentSize, const std::unique_ptr<KernelBuilder> & kb) {
75
76    BasicBlock * dropPages = kb->CreateBasicBlock("dropPages");
77    BasicBlock * processSegment = kb->CreateBasicBlock("produceData");
78    BasicBlock * setTermination = kb->CreateBasicBlock("setTermination");
79    BasicBlock * mmapSourceExit = kb->CreateBasicBlock("mmapSourceExit");
80
81    Constant * const readSize = kb->getSize(segmentSize);
82    Constant * const pageSize = kb->getSize(getpagesize());
83
84    Value * consumed = kb->getConsumedItemCount("sourceBuffer");
85    consumed = kb->CreateMul(consumed, kb->getSize(codeUnitWidth / 8));
86    consumed = kb->CreateAnd(consumed, ConstantExpr::getNeg(pageSize));
87
88    Value * const consumedBuffer = kb->getRawOutputPointer("sourceBuffer", consumed);
89    Value * const readableBuffer = kb->getScalarField("buffer");
90    Value * const unnecessaryBytes = kb->CreatePtrDiff(consumedBuffer, readableBuffer);
91
92    // avoid calling madvise unless an actual page table change could occur
93    kb->CreateLikelyCondBr(kb->CreateIsNotNull(unnecessaryBytes), processSegment, dropPages);
94
95    kb->SetInsertPoint(dropPages);
96    // instruct the OS that it can safely drop any fully consumed pages
97    kb->CreateMAdvise(readableBuffer, unnecessaryBytes, CBuilder::ADVICE_DONTNEED);
98    kb->setScalarField("buffer", kb->CreateGEP(readableBuffer, unnecessaryBytes));
99    kb->CreateBr(processSegment);
100
101    // determine whether or not we've exhausted the file buffer
102    kb->SetInsertPoint(processSegment);
103    Value * const fileSize = kb->getScalarField("fileSize");
104    Value * const produced = kb->CreateAdd(kb->getProducedItemCount("sourceBuffer"), readSize);
105    Value * const lessThanFullSegment = kb->CreateICmpULT(fileSize, produced);
106    kb->CreateUnlikelyCondBr(lessThanFullSegment, setTermination, mmapSourceExit);
107
108    kb->SetInsertPoint(setTermination);
109    kb->setTerminationSignal();
110    kb->CreateBr(mmapSourceExit);
111
112    // finally, set the "produced" count to reflect current position in the file
113    kb->SetInsertPoint(mmapSourceExit);
114    PHINode * itemsRead = kb->CreatePHI(produced->getType(), 2);
115    itemsRead->addIncoming(produced, processSegment);
116    itemsRead->addIncoming(fileSize, setTermination);
117    kb->setProducedItemCount("sourceBuffer", itemsRead);
118
119}
120
121void MMapSourceKernel::unmapSourceBuffer(const std::unique_ptr<KernelBuilder> & kb) {
122    kb->CreateMUnmap(kb->getBaseAddress("sourceBuffer"), kb->getBufferedSize("sourceBuffer"));
123}
124
125MMapSourceKernel::MMapSourceKernel(const std::unique_ptr<kernel::KernelBuilder> & kb, const unsigned stridesPerSegment, const unsigned codeUnitWidth)
126: SegmentOrientedKernel("mmap_source" + std::to_string(stridesPerSegment) + "@" + std::to_string(codeUnitWidth),
127{},
128{Binding{kb->getStreamSetTy(1, codeUnitWidth), "sourceBuffer", FixedRate(), Deferred()}},
129{Binding{kb->getInt32Ty(), "fileDescriptor"}},
130{Binding{kb->getSizeTy(), "fileSize"}}, {Binding{kb->getIntNTy(codeUnitWidth)->getPointerTo(), "buffer"}})
131, mStridesPerSegment(stridesPerSegment)
132, mCodeUnitWidth(codeUnitWidth)
133, mFileSizeFunction(nullptr) {
134
135}
136
137/// READ SOURCE KERNEL
138
139void ReadSourceKernel::generateInitializeMethod(const unsigned codeUnitWidth, const unsigned segmentSize, const std::unique_ptr<KernelBuilder> & b) {
140    const unsigned pageSize = getpagesize();
141    const auto bufferSize = std::max(pageSize * 8, segmentSize * 4);
142    ConstantInt * const bufferItems = b->getSize(bufferSize);
143    const auto codeUnitSize = codeUnitWidth / 8;
144    ConstantInt * const bufferBytes = b->getSize(bufferSize * codeUnitSize);
145    PointerType * const codeUnitPtrTy = b->getIntNTy(codeUnitWidth)->getPointerTo();
146    Value * const buffer = b->CreatePointerCast(b->CreateCacheAlignedMalloc(bufferBytes), codeUnitPtrTy);
147    b->setBaseAddress("sourceBuffer", buffer);
148    b->setScalarField("buffer", buffer);
149    b->setCapacity("sourceBuffer", bufferItems);
150}
151
152void ReadSourceKernel::generateDoSegmentMethod(const unsigned codeUnitWidth, const unsigned segmentSize, const std::unique_ptr<KernelBuilder> & b) {
153
154    const unsigned pageSize = getpagesize();
155    ConstantInt * const itemsToRead = b->getSize(std::max(pageSize, segmentSize * 2));
156    ConstantInt * const codeUnitBytes = b->getSize(codeUnitWidth / 8);
157    ConstantInt * const itemsPerSegment = b->getSize(segmentSize);
158
159    BasicBlock * const entry = b->GetInsertBlock();
160    BasicBlock * const checkData = b->CreateBasicBlock("CheckData");
161    BasicBlock * const moveData = b->CreateBasicBlock("MoveData");
162    BasicBlock * const prepareBuffer = b->CreateBasicBlock("PrepareBuffer");
163    BasicBlock * const readData = b->CreateBasicBlock("ReadData");
164    BasicBlock * const setTermination = b->CreateBasicBlock("SetTermination");
165    BasicBlock * const readExit = b->CreateBasicBlock("ReadExit");
166
167    // Do we have enough unread data to support one segment?
168    Value * const produced = b->getProducedItemCount("sourceBuffer");
169    Value * const buffered = b->getBufferedSize("sourceBuffer");
170    Value * const itemsPending = b->CreateAdd(produced, itemsPerSegment);
171
172    b->CreateLikelyCondBr(b->CreateICmpULT(itemsPending, buffered), readExit, checkData);
173
174    // Can we append to our existing buffer without impacting any subsequent kernel?
175    b->SetInsertPoint(checkData);
176    Value * const capacity = b->getCapacity("sourceBuffer");
177    Value * const readEnd = b->getRawOutputPointer("sourceBuffer", b->CreateAdd(buffered, itemsToRead));
178    Value * const baseBuffer = b->getScalarField("buffer");
179    Value * const bufferLimit = b->CreateGEP(baseBuffer, capacity);
180    b->CreateLikelyCondBr(b->CreateICmpULE(readEnd, bufferLimit), readData, moveData);
181
182    // First wait on any consumers to finish processing then check how much data has been consumed.
183    b->SetInsertPoint(moveData);
184    b->CreateConsumerWait();
185
186    // Then determine how much data has been consumed and how much needs to be copied back, noting
187    // that our "unproduced" data must be block aligned.
188    BasicBlock * const copyBack = b->CreateBasicBlock("CopyBack");
189    BasicBlock * const expandAndCopyBack = b->CreateBasicBlock("ExpandAndCopyBack");
190
191    const auto blockSize = b->getBitBlockWidth() / 8;
192    Constant * const blockSizeAlignmentMask = ConstantExpr::getNeg(b->getSize(blockSize));
193    Value * const consumed = b->getConsumedItemCount("sourceBuffer");
194    Value * const offset = b->CreateAnd(consumed, blockSizeAlignmentMask);
195    Value * const unreadData = b->getRawOutputPointer("sourceBuffer", offset);
196    Value * const remainingItems = b->CreateSub(buffered, offset);
197    Value * const remainingBytes = b->CreateMul(remainingItems, codeUnitBytes);
198
199    // Have we consumed enough data that we can safely copy back the unconsumed data without needing a temporary buffer?
200    Value * const canCopy = b->CreateICmpULT(b->CreateGEP(baseBuffer, remainingItems), b->getRawOutputPointer("sourceBuffer", offset));
201    b->CreateLikelyCondBr(canCopy, copyBack, expandAndCopyBack);
202
203    // If so, just copy the data ...
204    b->SetInsertPoint(copyBack);
205    b->CreateMemCpy(baseBuffer, unreadData, remainingBytes, blockSize);
206    b->CreateBr(prepareBuffer);
207
208    // Otherwise, allocate a buffer with twice the capacity and copy the unconsumed data back into it
209    b->SetInsertPoint(expandAndCopyBack);
210    Value * const expandedCapacity = b->CreateShl(capacity, 1);
211    Value * const expandedBytes = b->CreateMul(expandedCapacity, codeUnitBytes);
212    Value * const expandedBuffer = b->CreatePointerCast(b->CreateCacheAlignedMalloc(expandedBytes), unreadData->getType());
213    b->CreateMemCpy(expandedBuffer, unreadData, remainingBytes, blockSize);
214    b->setScalarField("buffer", expandedBuffer);
215    b->setCapacity("sourceBuffer", expandedCapacity); 
216    b->CreateFree(baseBuffer);
217    b->CreateBr(prepareBuffer);
218
219    b->SetInsertPoint(prepareBuffer);
220    PHINode * newBaseBuffer = b->CreatePHI(baseBuffer->getType(), 2);
221    newBaseBuffer->addIncoming(baseBuffer, copyBack);
222    newBaseBuffer->addIncoming(expandedBuffer, expandAndCopyBack);
223    b->setBaseAddress("sourceBuffer", b->CreateGEP(newBaseBuffer, b->CreateNeg(offset)));
224    b->CreateBr(readData);
225
226    // Regardless of whether we're simply appending data or had to allocate a new buffer, read a new page
227    // of data into the input source buffer. If we fail to read a full page ...
228    b->SetInsertPoint(readData);
229    Value * const sourceBuffer = b->getRawOutputPointer("sourceBuffer", buffered);
230    Value * const fd = b->getScalarField("fileDescriptor");
231    Constant * const bytesToRead = ConstantExpr::getMul(itemsToRead, codeUnitBytes);
232    Value * const bytesRead = b->CreateReadCall(fd, sourceBuffer, bytesToRead);
233    Value * const itemsRead = b->CreateUDiv(bytesRead, codeUnitBytes);
234    b->CreateAssert(b->CreateICmpULE(itemsRead, itemsToRead), "read more items than expected");
235    Value * const itemsBuffered = b->CreateAdd(buffered, itemsRead);
236    b->setBufferedSize("sourceBuffer", itemsBuffered);
237    b->CreateUnlikelyCondBr(b->CreateICmpULT(itemsBuffered, itemsPending), setTermination, readExit);
238
239    // ... set the termination signal.   
240    b->SetInsertPoint(setTermination);
241    Value * const bytesToZero = b->CreateMul(b->CreateSub(itemsPending, itemsBuffered), codeUnitBytes);
242    b->CreateMemZero(b->getRawOutputPointer("sourceBuffer", itemsBuffered), bytesToZero);
243    b->setTerminationSignal();
244    b->CreateBr(readExit);
245
246    readExit->moveAfter(setTermination);
247    b->SetInsertPoint(readExit);
248    PHINode * const itemsProduced = b->CreatePHI(itemsPending->getType(), 3);
249    itemsProduced->addIncoming(itemsPending, entry);
250    itemsProduced->addIncoming(itemsPending, readData);
251    itemsProduced->addIncoming(itemsBuffered, setTermination);
252    b->setProducedItemCount("sourceBuffer", itemsProduced);
253}
254
255void ReadSourceKernel::freeBuffer(const std::unique_ptr<KernelBuilder> & kb) {
256    kb->CreateFree(kb->getScalarField("buffer"));
257}
258
259ReadSourceKernel::ReadSourceKernel(const std::unique_ptr<kernel::KernelBuilder> & b, const unsigned stridesPerSegment, const unsigned codeUnitWidth)
260: SegmentOrientedKernel("read_source"  + std::to_string(stridesPerSegment) + "@" + std::to_string(codeUnitWidth)
261, {}
262, {Binding{b->getStreamSetTy(1, codeUnitWidth), "sourceBuffer", FixedRate(), Deferred()}}
263, {Binding{b->getInt32Ty(), "fileDescriptor"}}
264, {}
265, {Binding{b->getIntNTy(codeUnitWidth)->getPointerTo(), "buffer"}})
266, mStridesPerSegment(stridesPerSegment)
267, mCodeUnitWidth(codeUnitWidth) {
268
269}
270
271/// Hybrid MMap/Read source kernel
272
273void FDSourceKernel::linkExternalMethods(const std::unique_ptr<kernel::KernelBuilder> & kb) {
274    mFileSizeFunction = MMapSourceKernel::linkFileSizeMethod(kb);
275}
276
277void FDSourceKernel::generateFinalizeMethod(const std::unique_ptr<KernelBuilder> & kb) {
278    BasicBlock * finalizeRead = kb->CreateBasicBlock("finalizeRead");
279    BasicBlock * finalizeMMap = kb->CreateBasicBlock("finalizeMMap");
280    BasicBlock * finalizeDone = kb->CreateBasicBlock("finalizeDone");
281    // if the fileDescriptor is 0, the file is stdin, use readSource kernel logic, otherwise use mmap logic.
282    kb->CreateCondBr(kb->CreateICmpEQ(kb->getScalarField("fileDescriptor"), kb->getInt32(STDIN_FILENO)), finalizeRead, finalizeMMap);
283    kb->SetInsertPoint(finalizeRead);
284    ReadSourceKernel::freeBuffer(kb);
285    kb->CreateBr(finalizeDone);
286    kb->SetInsertPoint(finalizeMMap);
287    MMapSourceKernel::unmapSourceBuffer(kb);
288    kb->CreateBr(finalizeDone);
289    kb->SetInsertPoint(finalizeDone);
290}
291
292void FDSourceKernel::generateInitializeMethod(const std::unique_ptr<KernelBuilder> & kb) {
293    BasicBlock * initializeRead = kb->CreateBasicBlock("initializeRead");
294    BasicBlock * initializeMMap = kb->CreateBasicBlock("initializeMMap");
295    BasicBlock * initializeDone = kb->CreateBasicBlock("initializeDone");
296    // if the fileDescriptor is 0, the file is stdin, use readSource kernel logic, otherwise use MMap logic.
297    kb->CreateCondBr(kb->CreateICmpEQ(kb->getScalarField("fileDescriptor"), kb->getInt32(STDIN_FILENO)), initializeRead, initializeMMap);
298    kb->SetInsertPoint(initializeRead);
299    ReadSourceKernel::generateInitializeMethod(mCodeUnitWidth, mStride * mStridesPerSegment, kb);
300    kb->CreateBr(initializeDone);
301    kb->SetInsertPoint(initializeMMap);
302    MMapSourceKernel::generateInitializeMethod(mFileSizeFunction, mCodeUnitWidth, mStride * mStridesPerSegment, kb);
303    kb->CreateBr(initializeDone);
304    kb->SetInsertPoint(initializeDone);
305}
306
307void FDSourceKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> & kb) {
308    BasicBlock * DoSegmentRead = kb->CreateBasicBlock("DoSegmentRead");
309    BasicBlock * DoSegmentMMap = kb->CreateBasicBlock("DoSegmentMMap");
310    BasicBlock * DoSegmentDone = kb->CreateBasicBlock("DoSegmentDone");
311    // if the fileDescriptor is 0, the file is stdin, use readSource kernel logic, otherwise use MMap logic.
312    kb->CreateCondBr(kb->CreateICmpEQ(kb->getScalarField("fileDescriptor"), kb->getInt32(STDIN_FILENO)), DoSegmentRead, DoSegmentMMap);
313    kb->SetInsertPoint(DoSegmentRead);
314    ReadSourceKernel::generateDoSegmentMethod(mCodeUnitWidth, mStride * mStridesPerSegment, kb);
315    kb->CreateBr(DoSegmentDone);
316    kb->SetInsertPoint(DoSegmentMMap);
317    MMapSourceKernel::generateDoSegmentMethod(mCodeUnitWidth, mStride * mStridesPerSegment, kb);
318    kb->CreateBr(DoSegmentDone);
319    kb->SetInsertPoint(DoSegmentDone);
320}
321
322FDSourceKernel::FDSourceKernel(const std::unique_ptr<kernel::KernelBuilder> & kb, const unsigned stridesPerSegment, const unsigned codeUnitWidth)
323: SegmentOrientedKernel("FD_source" + std::to_string(stridesPerSegment) + "@" + std::to_string(codeUnitWidth)
324, {}
325, {Binding{kb->getStreamSetTy(1, codeUnitWidth), "sourceBuffer", FixedRate(), Deferred()}}
326, {Binding{kb->getInt32Ty(), "fileDescriptor"}}
327, {}
328, {Binding{kb->getIntNTy(codeUnitWidth)->getPointerTo(), "buffer"}, Binding{kb->getSizeTy(), "fileSize"}})
329, mStridesPerSegment(stridesPerSegment)
330, mCodeUnitWidth(codeUnitWidth)
331, mFileSizeFunction(nullptr) {
332
333}
334
335/// MEMORY SOURCE KERNEL
336
337void MemorySourceKernel::generateInitializeMethod(const std::unique_ptr<KernelBuilder> & kb) {
338    Value * const fileSource = kb->getScalarField("fileSource");
339    kb->setBaseAddress("sourceBuffer", fileSource);
340    Value * const fileSize = kb->getScalarField("fileSize");
341    Value * const fileItems = kb->CreateUDiv(fileSize, kb->getSize(mCodeUnitWidth / 8));
342    kb->setBufferedSize("sourceBuffer", fileItems);
343    kb->setCapacity("sourceBuffer", fileItems);
344}
345
346void MemorySourceKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> & kb) {
347
348    BasicBlock * entryBlock = kb->GetInsertBlock();
349    BasicBlock * setTermination = kb->CreateBasicBlock("setTermination");
350    BasicBlock * mmapSourceExit = kb->CreateBasicBlock("sourceExit");
351
352    ConstantInt * const segmentItems = kb->getSize(mStride * mStridesPerSegment);
353    Value * const fileItems = kb->getBufferedSize("sourceBuffer");
354    Value * const produced = kb->CreateAdd(kb->getProducedItemCount("sourceBuffer"), segmentItems);
355
356    kb->CreateUnlikelyCondBr(kb->CreateICmpULT(fileItems, produced), setTermination, mmapSourceExit);
357
358    kb->SetInsertPoint(setTermination);
359    kb->setTerminationSignal();
360    kb->CreateBr(mmapSourceExit);
361
362    kb->SetInsertPoint(mmapSourceExit);
363    PHINode * itemsRead = kb->CreatePHI(produced->getType(), 2);
364    itemsRead->addIncoming(produced, entryBlock);
365    itemsRead->addIncoming(fileItems, setTermination);
366    kb->setProducedItemCount("sourceBuffer", itemsRead);
367}
368
369MemorySourceKernel::MemorySourceKernel(const std::unique_ptr<kernel::KernelBuilder> & kb, Type * const type, const unsigned stridesPerSegment, const unsigned codeUnitWidth)
370: SegmentOrientedKernel("memory_source",
371    {},
372    {Binding{kb->getStreamSetTy(1, codeUnitWidth), "sourceBuffer"}},
373    {Binding{cast<PointerType>(type), "fileSource"}, Binding{kb->getSizeTy(), "fileSize"}}, {}, {})
374, mStridesPerSegment(stridesPerSegment)
375, mCodeUnitWidth(codeUnitWidth) {
376
377}
378
379}
Note: See TracBrowser for help on using the repository browser.