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

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

Large refactoring step. Removed IR generation code from Kernel (formally KernelBuilder?) and moved it into the new KernelBuilder? class.

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