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

Last change on this file since 6004 was 5985, checked in by nmedfort, 17 months ago

Restructured MultiBlock? kernel. Removal of Swizzled buffers. Inclusion of PopCount? rates / non-linear access. Modifications to several kernels to better align them with the kernel and pipeline changes.

File size: 18.0 KB
Line 
1/*
2 *  Copyright (c) 2018 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#include <toolchain/toolchain.h>
12
13using namespace llvm;
14
15extern "C" uint64_t file_size(const uint32_t fd) {
16    struct stat st;
17    if (LLVM_UNLIKELY(fstat(fd, &st) != 0)) {
18        st.st_size = 0;
19    }
20    return st.st_size;
21}
22
23namespace kernel {
24
25/// MMAP SOURCE KERNEL
26
27Function * MMapSourceKernel::linkFileSizeMethod(const std::unique_ptr<kernel::KernelBuilder> & b) {
28    return b->LinkFunction("file_size", &file_size);
29}
30
31void MMapSourceKernel::generateInitializeMethod(Function * const fileSizeMethod, const unsigned codeUnitWidth, const std::unique_ptr<KernelBuilder> & b) {
32
33    BasicBlock * const emptyFile = b->CreateBasicBlock("emptyFile");
34    BasicBlock * const nonEmptyFile = b->CreateBasicBlock("NonEmptyFile");
35    BasicBlock * const exit = b->CreateBasicBlock("Exit");
36    IntegerType * const sizeTy = b->getSizeTy();
37    Value * const fd = b->getScalarField("fileDescriptor");
38    assert (fileSizeMethod);
39    Value * fileSize = b->CreateZExtOrTrunc(b->CreateCall(fileSizeMethod, fd), sizeTy);
40    b->CreateLikelyCondBr(b->CreateIsNotNull(fileSize), nonEmptyFile, emptyFile);
41
42    b->SetInsertPoint(nonEmptyFile);
43    PointerType * const codeUnitPtrTy = b->getIntNTy(codeUnitWidth)->getPointerTo();
44    Value * const fileBuffer = b->CreatePointerCast(b->CreateFileSourceMMap(fd, fileSize), codeUnitPtrTy);
45    b->setScalarField("buffer", fileBuffer);
46    b->setBaseAddress("sourceBuffer", fileBuffer);
47    b->CreateMAdvise(fileBuffer, fileSize, CBuilder::ADVICE_WILLNEED);
48    if (LLVM_UNLIKELY(codeUnitWidth > 8)) {
49        fileSize = b->CreateUDiv(fileSize, b->getSize(codeUnitWidth / 8));
50    }
51    b->setBufferedSize("sourceBuffer", fileSize);
52    b->setScalarField("fileSize", fileSize);
53    b->setProducedItemCount("sourceBuffer", fileSize);
54    b->setCapacity("sourceBuffer", fileSize);
55    b->CreateBr(exit);
56
57    b->SetInsertPoint(emptyFile);
58    ConstantInt * const PAGE_SIZE = b->getSize(getpagesize());
59    ConstantInt * const ZERO = b->getSize(0);
60    Value * const emptyFilePtr = b->CreatePointerCast(b->CreateAnonymousMMap(PAGE_SIZE), codeUnitPtrTy);
61    b->setScalarField("buffer", emptyFilePtr);
62    b->setBaseAddress("sourceBuffer", emptyFilePtr);
63    b->setScalarField("fileSize", ZERO);
64    b->setBufferedSize("sourceBuffer", PAGE_SIZE);
65    b->setCapacity("sourceBuffer", PAGE_SIZE);
66    b->setTerminationSignal();
67    b->CreateBr(exit);
68
69    b->SetInsertPoint(exit);
70}
71
72void MMapSourceKernel::generateDoSegmentMethod(const unsigned codeUnitWidth, const std::unique_ptr<KernelBuilder> & b) {
73
74    BasicBlock * const dropPages = b->CreateBasicBlock("dropPages");
75    BasicBlock * const checkRemaining = b->CreateBasicBlock("checkRemaining");
76    BasicBlock * const setTermination = b->CreateBasicBlock("setTermination");
77    BasicBlock * const exit = b->CreateBasicBlock("mmapSourceExit");
78
79    Value * const fileSize = b->getScalarField("fileSize");
80    Constant * const PAGE_SIZE = b->getSize(getpagesize());
81
82    Value * const consumedItems = b->getConsumedItemCount("sourceBuffer");
83    Value * const consumedBytes = b->CreateMul(consumedItems, b->getSize(codeUnitWidth / 8));
84    Value * const consumedPageOffset = b->CreateAnd(consumedBytes, ConstantExpr::getNeg(PAGE_SIZE));
85    Value * const consumedBuffer = b->getRawOutputPointer("sourceBuffer", consumedPageOffset);
86    Value * const readableBuffer = b->getScalarField("buffer");
87    Value * const unnecessaryBytes = b->CreatePtrDiff(consumedBuffer, readableBuffer);
88
89    // avoid calling madvise unless an actual page table change could occur
90    b->CreateLikelyCondBr(b->CreateIsNotNull(unnecessaryBytes), dropPages, checkRemaining);
91
92    b->SetInsertPoint(dropPages);
93    // instruct the OS that it can safely drop any fully consumed pages
94    b->CreateMAdvise(readableBuffer, unnecessaryBytes, CBuilder::ADVICE_DONTNEED);
95    b->setScalarField("buffer", b->CreateGEP(readableBuffer, unnecessaryBytes));
96    b->CreateBr(checkRemaining);
97
98    // determine whether or not we've exhausted the file buffer
99    b->SetInsertPoint(checkRemaining);
100    Value * const producedItems = b->getProducedItemCount("sourceBuffer");
101    Value * const pageItems = b->CreateUDiv(PAGE_SIZE, b->getSize(codeUnitWidth / 8));
102    Value * const nextProducedItems = b->CreateAdd(producedItems, pageItems);
103    Value * const lastPage = b->CreateICmpULE(fileSize, nextProducedItems);
104    b->CreateUnlikelyCondBr(lastPage, setTermination, exit);
105
106    b->SetInsertPoint(setTermination);
107    b->setTerminationSignal();
108    b->CreateBr(exit);
109
110    // finally, set the "produced" count to reflect current position in the file
111    b->SetInsertPoint(exit);
112    PHINode * const newProducedItems = b->CreatePHI(b->getSizeTy(), 2);
113    newProducedItems->addIncoming(nextProducedItems, checkRemaining);
114    newProducedItems->addIncoming(fileSize, setTermination);
115    b->setProducedItemCount("sourceBuffer", newProducedItems);
116}
117
118void MMapSourceKernel::unmapSourceBuffer(const unsigned codeUnitWidth, const std::unique_ptr<KernelBuilder> & b) {
119    Value * fileSize = b->getBufferedSize("sourceBuffer");
120    if (LLVM_UNLIKELY(codeUnitWidth > 8)) {
121        fileSize = b->CreateMul(fileSize, b->getSize(codeUnitWidth / 8));
122    }
123    b->CreateMUnmap(b->getBaseAddress("sourceBuffer"), fileSize);
124}
125
126/// READ SOURCE KERNEL
127
128void ReadSourceKernel::generateInitializeMethod(const unsigned codeUnitWidth, const unsigned stride, const std::unique_ptr<KernelBuilder> & b) {
129    const unsigned pageSize = getpagesize();
130    const auto bufferSize = std::max(pageSize * 8, codegen::SegmentSize * stride  * 4);
131    ConstantInt * const bufferItems = b->getSize(bufferSize);
132    const auto codeUnitSize = codeUnitWidth / 8;
133    ConstantInt * const bufferBytes = b->getSize(bufferSize * codeUnitSize);
134    PointerType * const codeUnitPtrTy = b->getIntNTy(codeUnitWidth)->getPointerTo();
135    Value * const buffer = b->CreatePointerCast(b->CreateCacheAlignedMalloc(bufferBytes), codeUnitPtrTy);
136    b->setBaseAddress("sourceBuffer", buffer);
137    b->setScalarField("buffer", buffer);
138    b->setCapacity("sourceBuffer", bufferItems);
139}
140
141void ReadSourceKernel::generateDoSegmentMethod(const unsigned codeUnitWidth, const unsigned stride, const std::unique_ptr<KernelBuilder> & b) {
142
143    const unsigned pageSize = getpagesize();
144    ConstantInt * const itemsToRead = b->getSize(std::max(pageSize, codegen::SegmentSize * stride * 2));
145    ConstantInt * const codeUnitBytes = b->getSize(codeUnitWidth / 8);
146    ConstantInt * const itemsPerSegment = b->getSize(codegen::SegmentSize * stride);
147
148    BasicBlock * const entry = b->GetInsertBlock();
149    BasicBlock * const checkData = b->CreateBasicBlock("CheckData");
150    BasicBlock * const moveData = b->CreateBasicBlock("MoveData");
151    BasicBlock * const prepareBuffer = b->CreateBasicBlock("PrepareBuffer");
152    BasicBlock * const readData = b->CreateBasicBlock("ReadData");
153    BasicBlock * const setTermination = b->CreateBasicBlock("SetTermination");
154    BasicBlock * const readExit = b->CreateBasicBlock("ReadExit");
155
156    // Do we have enough unread data to support one segment?
157    Value * const produced = b->getProducedItemCount("sourceBuffer");
158    Value * const buffered = b->getBufferedSize("sourceBuffer");
159    Value * const itemsPending = b->CreateAdd(produced, itemsPerSegment);
160
161    b->CreateLikelyCondBr(b->CreateICmpULT(itemsPending, buffered), readExit, checkData);
162
163    // Can we append to our existing buffer without impacting any subsequent kernel?
164    b->SetInsertPoint(checkData);
165    Value * const capacity = b->getCapacity("sourceBuffer");
166    Value * const readEnd = b->getRawOutputPointer("sourceBuffer", b->CreateAdd(buffered, itemsToRead));
167    Value * const baseBuffer = b->getScalarField("buffer");
168    Value * const bufferLimit = b->CreateGEP(baseBuffer, capacity);
169    b->CreateLikelyCondBr(b->CreateICmpULE(readEnd, bufferLimit), readData, moveData);
170
171    // First wait on any consumers to finish processing then check how much data has been consumed.
172    b->SetInsertPoint(moveData);
173    b->CreateConsumerWait();
174
175    // Then determine how much data has been consumed and how much needs to be copied back, noting
176    // that our "unproduced" data must be block aligned.
177    BasicBlock * const copyBack = b->CreateBasicBlock("CopyBack");
178    BasicBlock * const expandAndCopyBack = b->CreateBasicBlock("ExpandAndCopyBack");
179
180    const auto blockSize = b->getBitBlockWidth() / 8;
181    Constant * const blockSizeAlignmentMask = ConstantExpr::getNeg(b->getSize(blockSize));
182    Value * const consumed = b->getConsumedItemCount("sourceBuffer");
183    Value * const offset = b->CreateAnd(consumed, blockSizeAlignmentMask);
184    Value * const unreadData = b->getRawOutputPointer("sourceBuffer", offset);
185    Value * const remainingItems = b->CreateSub(buffered, offset);
186    Value * const remainingBytes = b->CreateMul(remainingItems, codeUnitBytes);
187
188    // Have we consumed enough data that we can safely copy back the unconsumed data without needing a temporary buffer?
189    Value * const canCopy = b->CreateICmpULT(b->CreateGEP(baseBuffer, remainingItems), b->getRawOutputPointer("sourceBuffer", offset));
190    b->CreateLikelyCondBr(canCopy, copyBack, expandAndCopyBack);
191
192    // If so, just copy the data ...
193    b->SetInsertPoint(copyBack);
194    b->CreateMemCpy(baseBuffer, unreadData, remainingBytes, blockSize);
195    b->CreateBr(prepareBuffer);
196
197    // Otherwise, allocate a buffer with twice the capacity and copy the unconsumed data back into it
198    b->SetInsertPoint(expandAndCopyBack);
199    Value * const expandedCapacity = b->CreateShl(capacity, 1);
200    Value * const expandedBytes = b->CreateMul(expandedCapacity, codeUnitBytes);
201    Value * const expandedBuffer = b->CreatePointerCast(b->CreateCacheAlignedMalloc(expandedBytes), unreadData->getType());
202    b->CreateMemCpy(expandedBuffer, unreadData, remainingBytes, blockSize);
203    b->setScalarField("buffer", expandedBuffer);
204    b->setCapacity("sourceBuffer", expandedCapacity);
205    b->CreateFree(baseBuffer);
206    b->CreateBr(prepareBuffer);
207
208    b->SetInsertPoint(prepareBuffer);
209    PHINode * newBaseBuffer = b->CreatePHI(baseBuffer->getType(), 2);
210    newBaseBuffer->addIncoming(baseBuffer, copyBack);
211    newBaseBuffer->addIncoming(expandedBuffer, expandAndCopyBack);
212    b->setBaseAddress("sourceBuffer", b->CreateGEP(newBaseBuffer, b->CreateNeg(offset)));
213    b->CreateBr(readData);
214
215    // Regardless of whether we're simply appending data or had to allocate a new buffer, read a new page
216    // of data into the input source buffer. If we fail to read a full page ...
217    b->SetInsertPoint(readData);
218    Value * const sourceBuffer = b->getRawOutputPointer("sourceBuffer", buffered);
219    Value * const fd = b->getScalarField("fileDescriptor");
220    Constant * const bytesToRead = ConstantExpr::getMul(itemsToRead, codeUnitBytes);
221    Value * const bytesRead = b->CreateReadCall(fd, sourceBuffer, bytesToRead);
222    Value * const itemsRead = b->CreateUDiv(bytesRead, codeUnitBytes);
223    Value * const itemsBuffered = b->CreateAdd(buffered, itemsRead);
224    b->setBufferedSize("sourceBuffer", itemsBuffered);
225    b->CreateUnlikelyCondBr(b->CreateICmpULT(itemsBuffered, itemsPending), setTermination, readExit);
226
227    // ... set the termination signal.
228    b->SetInsertPoint(setTermination);
229    Value * const bytesToZero = b->CreateMul(b->CreateSub(itemsPending, itemsBuffered), codeUnitBytes);
230    b->CreateMemZero(b->getRawOutputPointer("sourceBuffer", itemsBuffered), bytesToZero);
231    b->setTerminationSignal();
232    b->CreateBr(readExit);
233
234    readExit->moveAfter(setTermination);
235    b->SetInsertPoint(readExit);
236    PHINode * const itemsProduced = b->CreatePHI(itemsPending->getType(), 3);
237    itemsProduced->addIncoming(itemsPending, entry);
238    itemsProduced->addIncoming(itemsPending, readData);
239    itemsProduced->addIncoming(itemsBuffered, setTermination);
240    b->setProducedItemCount("sourceBuffer", itemsProduced);
241}
242
243void ReadSourceKernel::freeBuffer(const std::unique_ptr<KernelBuilder> & b) {
244    b->CreateFree(b->getScalarField("buffer"));
245}
246
247/// Hybrid MMap/Read source kernel
248
249void FDSourceKernel::linkExternalMethods(const std::unique_ptr<kernel::KernelBuilder> & b) {
250    mFileSizeFunction = MMapSourceKernel::linkFileSizeMethod(b);
251}
252
253void FDSourceKernel::generateFinalizeMethod(const std::unique_ptr<KernelBuilder> & b) {
254    BasicBlock * finalizeRead = b->CreateBasicBlock("finalizeRead");
255    BasicBlock * finalizeMMap = b->CreateBasicBlock("finalizeMMap");
256    BasicBlock * finalizeDone = b->CreateBasicBlock("finalizeDone");
257    b->CreateCondBr(b->CreateTrunc(b->getScalarField("useMMap"), b->getInt1Ty()), finalizeMMap, finalizeRead);
258    b->SetInsertPoint(finalizeMMap);
259    MMapSourceKernel::unmapSourceBuffer(mCodeUnitWidth, b);
260    b->CreateBr(finalizeDone);
261    b->SetInsertPoint(finalizeRead);
262    ReadSourceKernel::freeBuffer(b);
263    b->CreateBr(finalizeDone);
264    b->SetInsertPoint(finalizeDone);
265}
266
267void FDSourceKernel::generateInitializeMethod(const std::unique_ptr<KernelBuilder> & b) {
268    BasicBlock * initializeRead = b->CreateBasicBlock("initializeRead");
269    BasicBlock * tryMMap = b->CreateBasicBlock("tryMMap");
270    BasicBlock * initializeMMap = b->CreateBasicBlock("initializeMMap");
271    BasicBlock * initializeDone = b->CreateBasicBlock("initializeDone");
272
273    // The source will use MMapSource or readSoure kernel logic depending on the useMMap
274    // parameter, possibly overridden.
275    Value * useMMap = b->CreateTrunc(b->getScalarField("useMMap"), b->getInt1Ty());
276    // if the fileDescriptor is 0, the file is stdin, use readSource kernel logic.
277    Value * fd = b->getScalarField("fileDescriptor");
278    useMMap = b->CreateAnd(useMMap, b->CreateICmpNE(fd, b->getInt32(STDIN_FILENO)));
279    b->CreateCondBr(useMMap, tryMMap, initializeRead);
280
281    b->SetInsertPoint(tryMMap);
282    // If the fileSize is 0, we may have a virtual file such as /proc/cpuinfo
283    Value * fileSize = b->CreateZExtOrTrunc(b->CreateCall(mFileSizeFunction, fd), b->getSizeTy());
284    useMMap = b->CreateICmpNE(fileSize, b->getSize(0));
285    b->CreateCondBr(useMMap, initializeMMap, initializeRead);
286    b->SetInsertPoint(initializeMMap);
287    MMapSourceKernel::generateInitializeMethod(mFileSizeFunction, mCodeUnitWidth, b);
288    b->CreateBr(initializeDone);
289
290    b->SetInsertPoint(initializeRead);
291    // Ensure that readSource logic is used throughout.
292    b->setScalarField("useMMap", b->getInt8(0));
293    ReadSourceKernel::generateInitializeMethod(mCodeUnitWidth, getStride(), b);
294    b->CreateBr(initializeDone);
295    b->SetInsertPoint(initializeDone);
296}
297
298void FDSourceKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> & b) {
299    BasicBlock * DoSegmentRead = b->CreateBasicBlock("DoSegmentRead");
300    BasicBlock * DoSegmentMMap = b->CreateBasicBlock("DoSegmentMMap");
301    BasicBlock * DoSegmentDone = b->CreateBasicBlock("DoSegmentDone");
302    b->CreateCondBr(b->CreateTrunc(b->getScalarField("useMMap"), b->getInt1Ty()), DoSegmentMMap, DoSegmentRead);
303    b->SetInsertPoint(DoSegmentMMap);
304    MMapSourceKernel::generateDoSegmentMethod(mCodeUnitWidth, b);
305    b->CreateBr(DoSegmentDone);
306    b->SetInsertPoint(DoSegmentRead);
307    ReadSourceKernel::generateDoSegmentMethod(mCodeUnitWidth, getStride(), b);
308    b->CreateBr(DoSegmentDone);
309    b->SetInsertPoint(DoSegmentDone);
310}
311
312/// MEMORY SOURCE KERNEL
313
314void MemorySourceKernel::generateInitializeMethod(const std::unique_ptr<KernelBuilder> & b) {
315    Value * const fileSource = b->getScalarField("fileSource");
316    b->setBaseAddress("sourceBuffer", fileSource);
317    Value * const fileSize = b->getScalarField("fileSize");
318    Value * const fileItems = b->CreateUDiv(fileSize, b->getSize(mCodeUnitWidth / 8));
319    b->setBufferedSize("sourceBuffer", fileItems);
320    b->setCapacity("sourceBuffer", fileItems);
321    b->setProducedItemCount("sourceBuffer", fileItems);
322    b->setTerminationSignal();
323}
324
325void MemorySourceKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> & b) {
326
327}
328
329MMapSourceKernel::MMapSourceKernel(const std::unique_ptr<kernel::KernelBuilder> & b, const unsigned codeUnitWidth)
330: SegmentOrientedKernel("mmap_source@" + std::to_string(codeUnitWidth)
331, {}
332, {Binding{b->getStreamSetTy(1, codeUnitWidth), "sourceBuffer"}}
333, {Binding{b->getInt32Ty(), "fileDescriptor"}}
334, {Binding{b->getSizeTy(), "fileSize"}}
335, {Binding{b->getIntNTy(codeUnitWidth)->getPointerTo(), "buffer"}})
336, mCodeUnitWidth(codeUnitWidth)
337, mFileSizeFunction(nullptr) {
338    addAttribute(MustExplicitlyTerminate());
339    setStride((8 * getpagesize()) / codeUnitWidth);
340}
341
342ReadSourceKernel::ReadSourceKernel(const std::unique_ptr<kernel::KernelBuilder> & b, const unsigned codeUnitWidth)
343: SegmentOrientedKernel("read_source" + std::to_string(codegen::SegmentSize) + "@" + std::to_string(codeUnitWidth)
344, {}
345, {Binding{b->getStreamSetTy(1, codeUnitWidth), "sourceBuffer"}}
346, {Binding{b->getInt32Ty(), "fileDescriptor"}}
347, {}
348, {Binding{b->getIntNTy(codeUnitWidth)->getPointerTo(), "buffer"}})
349, mCodeUnitWidth(codeUnitWidth) {
350    addAttribute(MustExplicitlyTerminate());
351    setStride((8 * getpagesize()) / codeUnitWidth);
352}
353
354
355FDSourceKernel::FDSourceKernel(const std::unique_ptr<kernel::KernelBuilder> & b, const unsigned codeUnitWidth)
356: SegmentOrientedKernel("FD_source@" + std::to_string(codeUnitWidth)
357, {}
358// output
359, {Binding{b->getStreamSetTy(1, codeUnitWidth), "sourceBuffer"}}
360// input scalar
361, {Binding{b->getInt8Ty(), "useMMap"}, Binding{b->getInt32Ty(), "fileDescriptor"}}
362, {}
363, {Binding{b->getIntNTy(codeUnitWidth)->getPointerTo(), "buffer"}, Binding{b->getSizeTy(), "fileSize"}})
364, mCodeUnitWidth(codeUnitWidth)
365, mFileSizeFunction(nullptr) {
366    addAttribute(MustExplicitlyTerminate());
367    setStride((8 * getpagesize()) / codeUnitWidth);
368}
369
370MemorySourceKernel::MemorySourceKernel(const std::unique_ptr<kernel::KernelBuilder> & b, Type * const type, const unsigned codeUnitWidth)
371: SegmentOrientedKernel("memory_source",
372    {},
373    {Binding{b->getStreamSetTy(1, codeUnitWidth), "sourceBuffer"}},
374    {Binding{cast<PointerType>(type), "fileSource"}, Binding{b->getSizeTy(), "fileSize"}}, {}, {})
375, mCodeUnitWidth(codeUnitWidth) {
376    addAttribute(MustExplicitlyTerminate());
377}
378
379}
Note: See TracBrowser for help on using the repository browser.