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

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

Minor changes and hopefully a fix for bug exposed by base64 test

File size: 18.4 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    Value * const itemsBuffered = b->CreateAdd(buffered, itemsRead);
235    b->setBufferedSize("sourceBuffer", itemsBuffered);
236    b->CreateUnlikelyCondBr(b->CreateICmpULT(itemsBuffered, itemsPending), setTermination, readExit);
237
238    // ... set the termination signal.   
239    b->SetInsertPoint(setTermination);
240    Value * const bytesToZero = b->CreateMul(b->CreateSub(itemsPending, itemsBuffered), codeUnitBytes);
241    b->CreateMemZero(b->getRawOutputPointer("sourceBuffer", itemsBuffered), bytesToZero);
242    b->setTerminationSignal();
243    b->CreateBr(readExit);
244
245    readExit->moveAfter(setTermination);
246    b->SetInsertPoint(readExit);
247    PHINode * const itemsProduced = b->CreatePHI(itemsPending->getType(), 3);
248    itemsProduced->addIncoming(itemsPending, entry);
249    itemsProduced->addIncoming(itemsPending, readData);
250    itemsProduced->addIncoming(itemsBuffered, setTermination);
251    b->setProducedItemCount("sourceBuffer", itemsProduced);
252}
253
254void ReadSourceKernel::freeBuffer(const std::unique_ptr<KernelBuilder> & kb) {
255    kb->CreateFree(kb->getScalarField("buffer"));
256}
257
258ReadSourceKernel::ReadSourceKernel(const std::unique_ptr<kernel::KernelBuilder> & b, const unsigned stridesPerSegment, const unsigned codeUnitWidth)
259: SegmentOrientedKernel("read_source"  + std::to_string(stridesPerSegment) + "@" + std::to_string(codeUnitWidth)
260, {}
261, {Binding{b->getStreamSetTy(1, codeUnitWidth), "sourceBuffer", FixedRate(), Deferred()}}
262, {Binding{b->getInt32Ty(), "fileDescriptor"}}
263, {}
264, {Binding{b->getIntNTy(codeUnitWidth)->getPointerTo(), "buffer"}})
265, mStridesPerSegment(stridesPerSegment)
266, mCodeUnitWidth(codeUnitWidth) {
267
268}
269
270/// Hybrid MMap/Read source kernel
271
272void FDSourceKernel::linkExternalMethods(const std::unique_ptr<kernel::KernelBuilder> & kb) {
273    mFileSizeFunction = MMapSourceKernel::linkFileSizeMethod(kb);
274}
275
276void FDSourceKernel::generateFinalizeMethod(const std::unique_ptr<KernelBuilder> & kb) {
277    BasicBlock * finalizeRead = kb->CreateBasicBlock("finalizeRead");
278    BasicBlock * finalizeMMap = kb->CreateBasicBlock("finalizeMMap");
279    BasicBlock * finalizeDone = kb->CreateBasicBlock("finalizeDone");
280    // if the fileDescriptor is 0, the file is stdin, use readSource kernel logic, otherwise use mmap logic.
281    kb->CreateCondBr(kb->CreateICmpEQ(kb->getScalarField("fileDescriptor"), kb->getInt32(STDIN_FILENO)), finalizeRead, finalizeMMap);
282    kb->SetInsertPoint(finalizeRead);
283    ReadSourceKernel::freeBuffer(kb);
284    kb->CreateBr(finalizeDone);
285    kb->SetInsertPoint(finalizeMMap);
286    MMapSourceKernel::unmapSourceBuffer(kb);
287    kb->CreateBr(finalizeDone);
288    kb->SetInsertPoint(finalizeDone);
289}
290
291void FDSourceKernel::generateInitializeMethod(const std::unique_ptr<KernelBuilder> & kb) {
292    BasicBlock * initializeRead = kb->CreateBasicBlock("initializeRead");
293    BasicBlock * initializeMMap = kb->CreateBasicBlock("initializeMMap");
294    BasicBlock * initializeDone = kb->CreateBasicBlock("initializeDone");
295    // if the fileDescriptor is 0, the file is stdin, use readSource kernel logic, otherwise use MMap logic.
296    kb->CreateCondBr(kb->CreateICmpEQ(kb->getScalarField("fileDescriptor"), kb->getInt32(STDIN_FILENO)), initializeRead, initializeMMap);
297    kb->SetInsertPoint(initializeRead);
298    ReadSourceKernel::generateInitializeMethod(mCodeUnitWidth, mStride * mStridesPerSegment, kb);
299    kb->CreateBr(initializeDone);
300    kb->SetInsertPoint(initializeMMap);
301    MMapSourceKernel::generateInitializeMethod(mFileSizeFunction, mCodeUnitWidth, mStride * mStridesPerSegment, kb);
302    kb->CreateBr(initializeDone);
303    kb->SetInsertPoint(initializeDone);
304}
305
306void FDSourceKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> & kb) {
307    BasicBlock * DoSegmentRead = kb->CreateBasicBlock("DoSegmentRead");
308    BasicBlock * DoSegmentMMap = kb->CreateBasicBlock("DoSegmentMMap");
309    BasicBlock * DoSegmentDone = kb->CreateBasicBlock("DoSegmentDone");
310    // if the fileDescriptor is 0, the file is stdin, use readSource kernel logic, otherwise use MMap logic.
311    kb->CreateCondBr(kb->CreateICmpEQ(kb->getScalarField("fileDescriptor"), kb->getInt32(STDIN_FILENO)), DoSegmentRead, DoSegmentMMap);
312    kb->SetInsertPoint(DoSegmentRead);
313    ReadSourceKernel::generateDoSegmentMethod(mCodeUnitWidth, mStride * mStridesPerSegment, kb);
314    kb->CreateBr(DoSegmentDone);
315    kb->SetInsertPoint(DoSegmentMMap);
316    MMapSourceKernel::generateDoSegmentMethod(mCodeUnitWidth, mStride * mStridesPerSegment, kb);
317    kb->CreateBr(DoSegmentDone);
318    kb->SetInsertPoint(DoSegmentDone);
319}
320
321FDSourceKernel::FDSourceKernel(const std::unique_ptr<kernel::KernelBuilder> & kb, const unsigned stridesPerSegment, const unsigned codeUnitWidth)
322: SegmentOrientedKernel("FD_source" + std::to_string(stridesPerSegment) + "@" + std::to_string(codeUnitWidth)
323, {}
324, {Binding{kb->getStreamSetTy(1, codeUnitWidth), "sourceBuffer", FixedRate(), Deferred()}}
325, {Binding{kb->getInt32Ty(), "fileDescriptor"}}
326, {}
327, {Binding{kb->getIntNTy(codeUnitWidth)->getPointerTo(), "buffer"}, Binding{kb->getSizeTy(), "fileSize"}})
328, mStridesPerSegment(stridesPerSegment)
329, mCodeUnitWidth(codeUnitWidth)
330, mFileSizeFunction(nullptr) {
331
332}
333
334/// MEMORY SOURCE KERNEL
335
336void MemorySourceKernel::generateInitializeMethod(const std::unique_ptr<KernelBuilder> & kb) {
337    Value * const fileSource = kb->getScalarField("fileSource");
338    kb->setBaseAddress("sourceBuffer", fileSource);
339    Value * const fileSize = kb->getScalarField("fileSize");
340    Value * const fileItems = kb->CreateUDiv(fileSize, kb->getSize(mCodeUnitWidth / 8));
341    kb->setBufferedSize("sourceBuffer", fileItems);
342    kb->setCapacity("sourceBuffer", fileItems);
343}
344
345void MemorySourceKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> & kb) {
346
347    BasicBlock * entryBlock = kb->GetInsertBlock();
348    BasicBlock * setTermination = kb->CreateBasicBlock("setTermination");
349    BasicBlock * mmapSourceExit = kb->CreateBasicBlock("sourceExit");
350
351    ConstantInt * const segmentItems = kb->getSize(mStride * mStridesPerSegment);
352    Value * const fileItems = kb->getBufferedSize("sourceBuffer");
353    Value * const produced = kb->CreateAdd(kb->getProducedItemCount("sourceBuffer"), segmentItems);
354
355    kb->CreateUnlikelyCondBr(kb->CreateICmpULT(fileItems, produced), setTermination, mmapSourceExit);
356
357    kb->SetInsertPoint(setTermination);
358    kb->setTerminationSignal();
359    kb->CreateBr(mmapSourceExit);
360
361    kb->SetInsertPoint(mmapSourceExit);
362    PHINode * itemsRead = kb->CreatePHI(produced->getType(), 2);
363    itemsRead->addIncoming(produced, entryBlock);
364    itemsRead->addIncoming(fileItems, setTermination);
365    kb->setProducedItemCount("sourceBuffer", itemsRead);
366}
367
368MemorySourceKernel::MemorySourceKernel(const std::unique_ptr<kernel::KernelBuilder> & kb, Type * const type, const unsigned stridesPerSegment, const unsigned codeUnitWidth)
369: SegmentOrientedKernel("memory_source",
370    {},
371    {Binding{kb->getStreamSetTy(1, codeUnitWidth), "sourceBuffer"}},
372    {Binding{cast<PointerType>(type), "fileSource"}, Binding{kb->getSizeTy(), "fileSize"}}, {}, {})
373, mStridesPerSegment(stridesPerSegment)
374, mCodeUnitWidth(codeUnitWidth) {
375
376}
377
378}
Note: See TracBrowser for help on using the repository browser.