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

Last change on this file since 5757 was 5757, checked in by nmedfort, 16 months ago

Bug fixes + more assertions to prevent similar errors.

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