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

Last change on this file since 5436 was 5436, checked in by nmedfort, 2 years ago

Continued refactoring work. PabloKernel? now abstract base type with a 'generatePabloMethod' hook to generate Pablo code.

File size: 16.2 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 <sys/stat.h>
9#include <fcntl.h>
10
11using namespace llvm;
12
13inline static size_t round_up_to_nearest(const size_t x, const size_t y) {
14    return (((x - 1) | (y - 1)) + 1);
15}
16
17uint64_t file_size(const uint32_t fd) {
18    struct stat st;
19    if (LLVM_UNLIKELY(fstat(fd, &st) != 0)) {
20        st.st_size = 0;
21    }
22    return st.st_size;
23}
24
25namespace kernel {
26
27/// MMAP SOURCE KERNEL
28
29void MMapSourceKernel::linkExternalMethods() {
30    mFileSizeFunction = iBuilder->LinkFunction("file_size", &file_size);
31}
32
33void MMapSourceKernel::generateInitializeMethod() {
34    BasicBlock * const emptyFile = CreateBasicBlock("EmptyFile");
35    BasicBlock * const nonEmptyFile = CreateBasicBlock("NonEmptyFile");
36    BasicBlock * const exit = CreateBasicBlock("Exit");
37    IntegerType * const sizeTy = iBuilder->getSizeTy();
38    Value * const fd = getScalarField("fileDescriptor");
39    assert (mFileSizeFunction);
40    Value * fileSize = iBuilder->CreateCall(mFileSizeFunction, fd);
41    fileSize = iBuilder->CreateZExtOrTrunc(fileSize, sizeTy);
42    if (mCodeUnitWidth > 8) {
43        fileSize = iBuilder->CreateUDiv(fileSize, iBuilder->getSize(mCodeUnitWidth / 8));
44    }
45    Value * const isEmpty = iBuilder->CreateICmpEQ(fileSize, ConstantInt::getNullValue(fileSize->getType()));
46    iBuilder->CreateUnlikelyCondBr(isEmpty, emptyFile, nonEmptyFile);
47    // we cannot mmap a 0 length file; just create a 1-page sized fake file buffer for simplicity
48    iBuilder->SetInsertPoint(emptyFile);
49    Constant * pageSize = iBuilder->getSize(getpagesize());
50    Value * fakeFileBuffer = iBuilder->CreateAnonymousMMap(pageSize);
51    iBuilder->CreateBr(exit);
52
53    iBuilder->SetInsertPoint(nonEmptyFile);
54    Value * fileBackedBuffer = iBuilder->CreateFileSourceMMap(fd, fileSize);
55    iBuilder->CreateBr(exit);
56
57    iBuilder->SetInsertPoint(exit);
58    PHINode * buffer = iBuilder->CreatePHI(fileBackedBuffer->getType(), 2);
59    buffer->addIncoming(fakeFileBuffer, emptyFile);
60    buffer->addIncoming(fileBackedBuffer, nonEmptyFile);
61    PHINode * size = iBuilder->CreatePHI(sizeTy, 2);
62    size->addIncoming(pageSize, emptyFile);
63    size->addIncoming(fileSize, nonEmptyFile);
64
65    setBaseAddress("sourceBuffer", buffer);
66    setBufferedSize("sourceBuffer", size);
67    setScalarField("readableBuffer", buffer);
68    setScalarField("fileSize", fileSize);
69    iBuilder->CreateMAdvise(buffer, fileSize, CBuilder::ADVICE_WILLNEED);
70
71}
72
73void MMapSourceKernel::generateDoSegmentMethod() {
74
75    BasicBlock * dropPages = CreateBasicBlock("dropPages");
76    BasicBlock * processSegment = CreateBasicBlock("produceData");
77    BasicBlock * setTermination = CreateBasicBlock("setTermination");
78    BasicBlock * mmapSourceExit = CreateBasicBlock("mmapSourceExit");
79
80    // instruct the OS that it can safely drop any fully consumed pages
81    Value * consumed = getConsumedItemCount("sourceBuffer");
82    Type * const consumedTy = consumed->getType();
83    Type * const voidPtrTy = iBuilder->getVoidPtrTy();
84
85    // multiply the consumed count by the code unit size then mask off any partial pages
86    if (mCodeUnitWidth > 8) {
87        consumed = iBuilder->CreateMul(consumed, iBuilder->getSize(mCodeUnitWidth / 8));
88    }
89    const auto pageSize = getpagesize();
90    if (LLVM_LIKELY((pageSize & (pageSize - 1)) == 0)) {
91        consumed = iBuilder->CreateAnd(consumed, ConstantExpr::getNot(ConstantInt::get(consumedTy, pageSize - 1)));
92    } else {
93        consumed = iBuilder->CreateSub(consumed, iBuilder->CreateURem(consumed, ConstantInt::get(consumedTy, pageSize)));
94    }
95    Value * sourceBuffer = getBaseAddress("sourceBuffer");
96    sourceBuffer = iBuilder->CreatePtrToInt(sourceBuffer, consumedTy);
97    Value * consumedBuffer = iBuilder->CreateAdd(sourceBuffer, consumed);
98
99
100
101
102    Value * readableBuffer = getScalarField("readableBuffer");
103    readableBuffer = iBuilder->CreatePtrToInt(readableBuffer, consumedTy);
104    Value * unnecessaryBytes = iBuilder->CreateSub(consumedBuffer, readableBuffer);
105
106
107
108    // avoid calling madvise unless an actual page table change could occur
109    Value * hasPagesToDrop = iBuilder->CreateICmpEQ(unnecessaryBytes, ConstantInt::getNullValue(unnecessaryBytes->getType()));
110    iBuilder->CreateLikelyCondBr(hasPagesToDrop, processSegment, dropPages);
111
112    iBuilder->SetInsertPoint(dropPages);
113    iBuilder->CreateMAdvise(iBuilder->CreateIntToPtr(readableBuffer, voidPtrTy), unnecessaryBytes, CBuilder::ADVICE_DONTNEED);
114    readableBuffer = iBuilder->CreateIntToPtr(iBuilder->CreateAdd(readableBuffer, unnecessaryBytes), voidPtrTy);
115    setScalarField("readableBuffer", readableBuffer);
116    iBuilder->CreateBr(processSegment);
117
118    // determine whether or not we've exhausted the file buffer
119    iBuilder->SetInsertPoint(processSegment);
120    ConstantInt * segmentItems = iBuilder->getSize(mSegmentBlocks * iBuilder->getBitBlockWidth());
121    Value * const fileSize = getScalarField("fileSize");
122    Value * const produced = iBuilder->CreateAdd(getProducedItemCount("sourceBuffer"), segmentItems);
123    Value * const lessThanFullSegment = iBuilder->CreateICmpULT(fileSize, produced);
124    iBuilder->CreateUnlikelyCondBr(lessThanFullSegment, setTermination, mmapSourceExit);
125    iBuilder->SetInsertPoint(setTermination);
126
127    setTerminationSignal();
128    iBuilder->CreateBr(mmapSourceExit);
129
130    // finally, set the "produced" count to reflect current position in the file
131    iBuilder->SetInsertPoint(mmapSourceExit);
132    PHINode * itemsRead = iBuilder->CreatePHI(produced->getType(), 2);
133    itemsRead->addIncoming(produced, processSegment);
134    itemsRead->addIncoming(fileSize, setTermination);
135    setProducedItemCount("sourceBuffer", itemsRead);
136}
137
138void MMapSourceKernel::generateFinalizeMethod() {
139    iBuilder->CreateMUnmap(getBaseAddress("sourceBuffer"), getBufferedSize("sourceBuffer"));
140}
141
142MMapSourceKernel::MMapSourceKernel(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, unsigned blocksPerSegment, unsigned codeUnitWidth)
143: SegmentOrientedKernel("mmap_source" + std::to_string(blocksPerSegment) + "@" + std::to_string(codeUnitWidth),
144{},
145{Binding{iBuilder->getStreamSetTy(1, codeUnitWidth), "sourceBuffer"}},
146{Binding{iBuilder->getInt32Ty(), "fileDescriptor"}},
147{Binding{iBuilder->getSizeTy(), "fileSize"}}, {Binding{iBuilder->getVoidPtrTy(), "readableBuffer"}})
148, mSegmentBlocks(blocksPerSegment)
149, mCodeUnitWidth(codeUnitWidth)
150, mFileSizeFunction(nullptr) {
151
152}
153
154/// READ SOURCE KERNEL
155
156void ReadSourceKernel::generateInitializeMethod() {
157    ConstantInt * const bufferSize = iBuilder->getSize(64 * getpagesize());
158    Value * const buffer = iBuilder->CreateAlignedMalloc(bufferSize, iBuilder->getCacheAlignment());
159    setScalarField("buffer", buffer);
160    setScalarField("capacity", bufferSize);
161    setBaseAddress("sourceBuffer", buffer);
162    setBufferedSize("sourceBuffer", iBuilder->getSize(0));
163}
164
165void ReadSourceKernel::generateDoSegmentMethod() {
166
167    ConstantInt * const pageSize = iBuilder->getSize(getpagesize());
168    PointerType * const codeUnitPtrTy = IntegerType::get(iBuilder->getContext(), mCodeUnitWidth)->getPointerTo();
169    BasicBlock * const entryBlock = iBuilder->GetInsertBlock();
170    BasicBlock * const exhaustedBuffer = CreateBasicBlock("ExhaustedBuffer");
171    BasicBlock * const waitOnConsumers = CreateBasicBlock("WaitOnConsumers");
172    BasicBlock * const readData = CreateBasicBlock("ReadData");
173    BasicBlock * const stdInExit = CreateBasicBlock("StdInExit");
174
175    // The ReadSourceKernel begins by checking whether it needs to read another page of data
176    ConstantInt * const segmentSize = iBuilder->getSize(mSegmentBlocks * iBuilder->getBitBlockWidth());
177    Value * bufferedSize = getBufferedSize("sourceBuffer");
178    Value * const produced = getProducedItemCount("sourceBuffer");
179    Value * unreadSize = iBuilder->CreateSub(bufferedSize, produced);
180    iBuilder->CreateUnlikelyCondBr(iBuilder->CreateICmpULT(unreadSize, segmentSize), exhaustedBuffer, stdInExit);
181
182    // If so, it checks whether it can simply append another page to the existing buffer or whether
183    // we need to perform a copyback.
184
185    iBuilder->SetInsertPoint(exhaustedBuffer);
186
187    // Otherwise, we're going to have to perform a copy back...
188
189    // Let L be the logical buffer address (i.e., the position of the "first byte" of the input stream)
190    // and B be the address pointing to the beginning of our actual buffer. Check whether:
191
192    //     L + produced + pagesize < B + capacity
193
194    // If so, we can append to our existing buffer without impacting any subsequent kernel.
195
196    Value * inputStream = getRawOutputPointer("sourceBuffer", iBuilder->getInt32(0), iBuilder->getInt32(0));
197    inputStream = iBuilder->CreatePointerCast(inputStream, codeUnitPtrTy);
198    Value * const originalPtr = iBuilder->CreateGEP(inputStream, produced);
199    Value * const buffer = iBuilder->CreatePointerCast(getScalarField("buffer"), codeUnitPtrTy);
200    Value * const capacity = getScalarField("capacity");
201    Value * const canAppend = iBuilder->CreateICmpULT(iBuilder->CreateGEP(originalPtr, pageSize), iBuilder->CreateGEP(buffer, capacity));
202    iBuilder->CreateLikelyCondBr(canAppend, readData, waitOnConsumers);
203
204    // First wait on any consumers to finish processing then check how much data has been consumed.
205    iBuilder->SetInsertPoint(waitOnConsumers);
206    CreateWaitForConsumers();
207    // Then determine how much data has been consumed and how much needs to be copied back, noting
208    // that our "unproduced" data must be block aligned.
209    const auto alignment = iBuilder->getBitBlockWidth() / 8;
210    Constant * const alignmentMask = ConstantExpr::getNeg(iBuilder->getSize(alignment));
211    Value * const consumed = iBuilder->CreateAnd(getConsumedItemCount("sourceBuffer"), alignmentMask);
212    Value * const remaining = iBuilder->CreateSub(bufferedSize, consumed);
213    Value * const unconsumedPtr = iBuilder->CreateGEP(inputStream, consumed);
214    Value * const consumedMajority = iBuilder->CreateICmpULT(iBuilder->CreateGEP(buffer, remaining), unconsumedPtr);
215    BasicBlock * const copyBack = CreateBasicBlock("CopyBack");
216    BasicBlock * const expandAndCopyBack = CreateBasicBlock("ExpandAndCopyBack");
217    BasicBlock * const calculateLogicalAddress = CreateBasicBlock("CalculateLogicalAddress");
218    // Have we consumed enough data that we can safely copy back the unconsumed data without needing
219    // a temporary buffer? (i.e., B + remaining < L + consumed)
220    iBuilder->CreateLikelyCondBr(consumedMajority, copyBack, expandAndCopyBack);
221    iBuilder->SetInsertPoint(copyBack);
222    // If so, just copy the data ...
223    iBuilder->CreateMemCpy(buffer, unconsumedPtr, remaining, alignment);
224    iBuilder->CreateBr(calculateLogicalAddress);
225    // Otherwise, allocate a buffer with twice the capacity and copy the unconsumed data back into it
226    iBuilder->SetInsertPoint(expandAndCopyBack);
227    Value * const expandedCapacity = iBuilder->CreateShl(capacity, 1);
228    Value * const expandedBuffer = iBuilder->CreateAlignedMalloc(expandedCapacity, iBuilder->getCacheAlignment());
229    Value * const expandedPtr = iBuilder->CreatePointerCast(expandedBuffer, codeUnitPtrTy);
230    iBuilder->CreateMemCpy(expandedPtr, unconsumedPtr, remaining, alignment);
231    iBuilder->CreateAlignedFree(buffer);
232    setScalarField("buffer", expandedBuffer);
233    setScalarField("capacity", expandedCapacity);   
234    iBuilder->CreateBr(calculateLogicalAddress);
235    // Update the logical address for this buffer....
236    iBuilder->SetInsertPoint(calculateLogicalAddress);
237    PHINode * const baseAddress = iBuilder->CreatePHI(codeUnitPtrTy, 2);
238    baseAddress->addIncoming(buffer, copyBack);
239    baseAddress->addIncoming(expandedPtr, expandAndCopyBack);
240    Value * const modifiedPtr = iBuilder->CreateGEP(baseAddress, remaining);
241    Value * const logicalAddress = iBuilder->CreateGEP(modifiedPtr, iBuilder->CreateNeg(produced));
242    setBaseAddress("sourceBuffer", logicalAddress);
243    iBuilder->CreateBr(readData);
244    // Regardless of whether we're simply appending data or had to allocate a new buffer, read a new page
245    // of data into the input source buffer. If we fail to read a full segment ...
246    readData->moveAfter(calculateLogicalAddress);
247    iBuilder->SetInsertPoint(readData);
248    calculateLogicalAddress->moveAfter(calculateLogicalAddress);
249    PHINode * const addr = iBuilder->CreatePHI(codeUnitPtrTy, 2);
250    addr->addIncoming(originalPtr, exhaustedBuffer);
251    addr->addIncoming(modifiedPtr, calculateLogicalAddress);
252    Value * bytesRead = iBuilder->CreateReadCall(getScalarField("fileDescriptor"), addr, pageSize);
253    unreadSize = iBuilder->CreateAdd(unreadSize, bytesRead);
254    bufferedSize = iBuilder->CreateAdd(bufferedSize, bytesRead);
255    setBufferedSize("sourceBuffer", bufferedSize);
256    Value * const exhaustedInputSource = iBuilder->CreateICmpULT(unreadSize, segmentSize);
257    BasicBlock * const setTermination = CreateBasicBlock("SetTermination");
258    iBuilder->CreateUnlikelyCondBr(exhaustedInputSource, setTermination, stdInExit);
259
260    // ... zero out the remaining bytes and set the termination signal.
261    iBuilder->SetInsertPoint(setTermination);
262    Value * const bytesToZero = iBuilder->CreateSub(segmentSize, unreadSize);
263    iBuilder->CreateMemZero(iBuilder->CreateGEP(addr, unreadSize), bytesToZero);
264    setTerminationSignal();
265    iBuilder->CreateBr(stdInExit);
266
267    // finally add the segment item count to the produced item count to inform the subsequent kernels how
268    // much data is available for processing
269    iBuilder->SetInsertPoint(stdInExit);
270    stdInExit->moveAfter(setTermination);
271    PHINode * const items = iBuilder->CreatePHI(produced->getType(), 3);
272    items->addIncoming(segmentSize, entryBlock);
273    items->addIncoming(segmentSize, readData);
274    items->addIncoming(unreadSize, setTermination);
275    setProducedItemCount("sourceBuffer", iBuilder->CreateAdd(produced, items));
276}
277
278void ReadSourceKernel::generateFinalizeMethod() {
279    iBuilder->CreateAlignedFree(getScalarField("buffer"));
280}
281
282ReadSourceKernel::ReadSourceKernel(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, unsigned blocksPerSegment, unsigned codeUnitWidth)
283: SegmentOrientedKernel("read_source"
284, {}
285, {Binding{iBuilder->getStreamSetTy(1, codeUnitWidth), "sourceBuffer"}}
286, {Binding{iBuilder->getInt32Ty(), "fileDescriptor"}}
287, {}
288, {Binding{iBuilder->getVoidPtrTy(), "buffer"}, Binding{iBuilder->getSizeTy(), "capacity"}})
289, mSegmentBlocks(blocksPerSegment)
290, mCodeUnitWidth(codeUnitWidth) {
291
292}
293
294/// MEMORY SOURCE KERNEL
295
296void MemorySourceKernel::generateInitializeMethod() {
297    setBaseAddress("sourceBuffer", iBuilder->CreatePointerCast(getScalarField("fileSource"), iBuilder->getVoidPtrTy()));
298    setBufferedSize("sourceBuffer", getScalarField("fileSize"));
299}
300
301void MemorySourceKernel::generateDoSegmentMethod() {
302
303    BasicBlock * entryBlock = iBuilder->GetInsertBlock();
304    BasicBlock * setTermination = CreateBasicBlock("setTermination");
305    BasicBlock * mmapSourceExit = CreateBasicBlock("sourceExit");
306    ConstantInt * segmentItems = iBuilder->getSize(mSegmentBlocks * iBuilder->getBitBlockWidth());
307    Value * fileItems = getScalarField("fileSize");
308    if (mCodeUnitWidth > 8) {
309        fileItems = iBuilder->CreateUDiv(fileItems, iBuilder->getSize(mCodeUnitWidth / 8));
310    }
311    Value * produced = getProducedItemCount("sourceBuffer");
312    produced = iBuilder->CreateAdd(produced, segmentItems);
313    Value * lessThanFullSegment = iBuilder->CreateICmpULT(fileItems, produced);
314    iBuilder->CreateCondBr(lessThanFullSegment, setTermination, mmapSourceExit);
315    iBuilder->SetInsertPoint(setTermination);
316    setTerminationSignal();
317    iBuilder->CreateBr(mmapSourceExit);
318
319    iBuilder->SetInsertPoint(mmapSourceExit);
320
321    PHINode * itemsRead = iBuilder->CreatePHI(produced->getType(), 2);
322    itemsRead->addIncoming(produced, entryBlock);
323    itemsRead->addIncoming(fileItems, setTermination);
324    setProducedItemCount("sourceBuffer", itemsRead);
325}
326
327MemorySourceKernel::MemorySourceKernel(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, Type * type, unsigned blocksPerSegment, unsigned codeUnitWidth)
328: SegmentOrientedKernel("memory_source",
329    {},
330    {Binding{iBuilder->getStreamSetTy(1, codeUnitWidth), "sourceBuffer"}},
331    {Binding{cast<PointerType>(type), "fileSource"}, Binding{iBuilder->getSizeTy(), "fileSize"}}, {}, {})
332, mSegmentBlocks(blocksPerSegment)
333, mCodeUnitWidth(codeUnitWidth) {
334
335}
336
337}
Note: See TracBrowser for help on using the repository browser.