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

Last change on this file since 5493 was 5493, checked in by cameron, 2 years ago

Restore check-ins from the last several days

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