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

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

Refactored source kernels. icgrep from stdin should now be able to handle any file size.

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