source: icGREP/icgrep-devel/icgrep/kernels/p2s_kernel.cpp @ 6297

Last change on this file since 6297 was 6261, checked in by nmedfort, 8 months ago

Work on OptimizationBranch?; revisited pipeline termination

File size: 11.8 KB
Line 
1#include "p2s_kernel.h"
2#include <kernels/streamset.h>
3#include <kernels/kernel_builder.h>
4#include <toolchain/toolchain.h>
5#include <llvm/Support/Compiler.h>
6
7namespace llvm { class Value; }
8
9using namespace llvm;
10
11namespace kernel{
12
13void p2s_step(const std::unique_ptr<KernelBuilder> & iBuilder, Value * p0, Value * p1, Value * hi_mask, unsigned shift, Value * &s1, Value * &s0) {
14    Value * t0 = iBuilder->simd_if(1, hi_mask, p0, iBuilder->simd_srli(16, p1, shift));
15    Value * t1 = iBuilder->simd_if(1, hi_mask, iBuilder->simd_slli(16, p0, shift), p1);
16    s1 = iBuilder->esimd_mergeh(8, t1, t0);
17    s0 = iBuilder->esimd_mergel(8, t1, t0);
18}
19
20inline void p2s(const std::unique_ptr<KernelBuilder> & iBuilder, Value * p[], Value * s[], cc::BitNumbering basisNumbering = cc::BitNumbering::LittleEndian) {
21    Value * bit00004444[2];
22    Value * bit22226666[2];
23    Value * bit11115555[2];
24    Value * bit33337777[2];
25    if (basisNumbering == cc::BitNumbering::BigEndian) {
26        p2s_step(iBuilder, p[0], p[4], iBuilder->simd_himask(8), 4, bit00004444[1], bit00004444[0]);
27        p2s_step(iBuilder, p[1], p[5], iBuilder->simd_himask(8), 4, bit11115555[1], bit11115555[0]);
28        p2s_step(iBuilder, p[2], p[6], iBuilder->simd_himask(8), 4, bit22226666[1], bit22226666[0]);
29        p2s_step(iBuilder, p[3], p[7], iBuilder->simd_himask(8), 4, bit33337777[1], bit33337777[0]);
30    }  else {
31        p2s_step(iBuilder, p[7], p[3], iBuilder->simd_himask(8), 4, bit00004444[1], bit00004444[0]);
32        p2s_step(iBuilder, p[6], p[2], iBuilder->simd_himask(8), 4, bit11115555[1], bit11115555[0]);
33        p2s_step(iBuilder, p[5], p[1], iBuilder->simd_himask(8), 4, bit22226666[1], bit22226666[0]);
34        p2s_step(iBuilder, p[4], p[0], iBuilder->simd_himask(8), 4, bit33337777[1], bit33337777[0]);
35    }
36    Value * bit00224466[4];
37    Value * bit11335577[4];
38    for (unsigned j = 0; j<2; j++) {
39        p2s_step(iBuilder, bit00004444[j], bit22226666[j],iBuilder->simd_himask(4), 2, bit00224466[2*j+1], bit00224466[2*j]);
40        p2s_step(iBuilder, bit11115555[j], bit33337777[j],iBuilder->simd_himask(4), 2, bit11335577[2*j+1], bit11335577[2*j]);
41    }
42    for (unsigned j = 0; j<4; j++) {
43        p2s_step(iBuilder, bit00224466[j], bit11335577[j], iBuilder->simd_himask(2), 1, s[2*j+1], s[2*j]);
44    }
45}
46
47void P2SKernel::generateDoBlockMethod(const std::unique_ptr<KernelBuilder> & b) {
48    const auto numOfStreams = getInputStreamSet("basisBits")->getNumElements();
49    Value * p_bitblock[8];
50    // todo: generalize this to the nearest pow 2?
51    for (unsigned i = 0; i < 8; i++) {
52        if (i < numOfStreams) {
53            p_bitblock[i] = b->loadInputStreamBlock("basisBits", b->getInt32(i));
54        } else {
55            p_bitblock[i] = ConstantVector::getNullValue(b->getBitBlockType());
56        }
57
58    }
59    Value * s_bytepack[8];
60    p2s(b, p_bitblock, s_bytepack, mBasisSetNumbering);
61    for (unsigned j = 0; j < 8; ++j) {
62        b->storeOutputStreamPack("byteStream", b->getInt32(0), b->getInt32(j), s_bytepack[j]);
63    }
64}
65
66
67void P2SMultipleStreamsKernel::generateDoBlockMethod(const std::unique_ptr<kernel::KernelBuilder> &b) {
68    Value * input[8];
69    unsigned k = 0;
70    for (unsigned i = 0; i < getNumOfStreamInputs(); ++i) {
71        const auto m = getInputStreamSet(i)->getNumElements();
72        for (unsigned j = 0; j < m; j++) {
73            input[k++] = b->loadInputStreamBlock("basisBits_" + std::to_string(i), b->getInt32(j));
74        }
75    }
76    assert (k <= 8);
77    while (k < 8) {
78        input[k++] = ConstantVector::getNullValue(b->getBitBlockType());
79    }
80
81    Value * output[8];
82    p2s(b, input, output, mBasisSetNumbering);
83    for (unsigned j = 0; j < 8; ++j) {
84        b->storeOutputStreamPack("byteStream", b->getInt32(0), b->getInt32(j), output[j]);
85    }
86}
87
88
89inline Value * partial_sum_popcounts(const std::unique_ptr<KernelBuilder> & iBuilder, const unsigned fw, Value * popcounts) {
90    Value * summed_counts = popcounts;
91    const auto count = iBuilder->getBitBlockWidth() / fw;
92    for (unsigned move = 1; move < count; move *= 2) {
93        summed_counts = iBuilder->simd_add(fw, summed_counts, iBuilder->mvmd_slli(fw, summed_counts, move));
94    }
95    return summed_counts;
96}
97
98void P2SKernelWithCompressedOutput::generateDoBlockMethod(const std::unique_ptr<KernelBuilder> & b) {
99    IntegerType * i32 = b->getInt32Ty();
100    PointerType * bitBlockPtrTy = PointerType::get(b->getBitBlockType(), 0);
101    unsigned const unitsPerRegister = b->getBitBlockWidth()/8;
102
103    Value * basisBits[8];
104    for (unsigned i = 0; i < 8; i++) {
105        basisBits[i] = b->loadInputStreamBlock("basisBits", b->getInt32(i));
106    }
107    Value * bytePack[8];
108    p2s(b, basisBits, bytePack, mBasisSetNumbering);
109
110    Value * const fieldCounts = b->loadInputStreamBlock("fieldCounts", b->getInt32(0));
111    Value * unitCounts = partial_sum_popcounts(b, unitsPerRegister, fieldCounts);
112
113    Value * output_ptr = b->getOutputStreamBlockPtr("byteStream", b->getInt32(0));
114    output_ptr = b->CreatePointerCast(output_ptr, b->getInt8PtrTy());
115    Value * offset = b->getInt32(0);
116    for (unsigned j = 0; j < 8; ++j) {
117        b->CreateStore(bytePack[j], b->CreateBitCast(b->CreateGEP(output_ptr, offset), bitBlockPtrTy));
118        offset = b->CreateZExt(b->CreateExtractElement(unitCounts, b->getInt32(j)), i32);
119    }
120
121    Value * unitsGenerated = b->getProducedItemCount("byteStream"); // units generated to buffer
122    unitsGenerated = b->CreateAdd(unitsGenerated, b->CreateZExt(offset, b->getSizeTy()));
123    b->setProducedItemCount("byteStream", unitsGenerated);
124}
125
126void P2S16Kernel::generateDoBlockMethod(const std::unique_ptr<KernelBuilder> & b) {
127    Value * hi_input[8];
128    for (unsigned j = 0; j < 8; ++j) {
129        const unsigned idx = mBasisSetNumbering == cc::BitNumbering::LittleEndian ? j + 8 : j;
130        hi_input[j] = b->loadInputStreamBlock("basisBits", b->getInt32(idx));
131    }
132    Value * hi_bytes[8];
133    p2s(b, hi_input, hi_bytes, mBasisSetNumbering);
134    Value * lo_input[8];
135    for (unsigned j = 0; j < 8; ++j) {
136        const unsigned idx = mBasisSetNumbering == cc::BitNumbering::LittleEndian ? j : j + 8;
137        lo_input[j] = b->loadInputStreamBlock("basisBits", b->getInt32(idx));
138    }
139    Value * lo_bytes[8];
140    p2s(b, lo_input, lo_bytes, mBasisSetNumbering);
141    for (unsigned j = 0; j < 8; ++j) {
142        Value * merge0 = b->bitCast(b->esimd_mergel(8, hi_bytes[j], lo_bytes[j]));
143        Value * merge1 = b->bitCast(b->esimd_mergeh(8, hi_bytes[j], lo_bytes[j]));
144        b->storeOutputStreamPack("i16Stream", b->getInt32(0), b->getInt32(2 * j), merge0);
145        b->storeOutputStreamPack("i16Stream", b->getInt32(0), b->getInt32(2 * j + 1), merge1);
146    }
147}
148
149void P2S16KernelWithCompressedOutput::generateDoBlockMethod(const std::unique_ptr<KernelBuilder> & b) {
150    IntegerType * i32Ty = b->getInt32Ty();
151    PointerType * int16PtrTy = b->getInt16Ty()->getPointerTo();
152    PointerType * bitBlockPtrTy = b->getBitBlockType()->getPointerTo();
153    ConstantInt * blockMask = b->getSize(b->getBitBlockWidth() - 1);
154    unsigned const unitsPerRegister = b->getBitBlockWidth()/16;
155
156    Value * hi_input[8];
157    for (unsigned j = 0; j < 8; ++j) {
158        const unsigned idx = mBasisSetNumbering == cc::BitNumbering::LittleEndian ? j + 8 : j;
159        hi_input[j] = b->loadInputStreamBlock("basisBits", b->getInt32(idx));
160    }
161    Value * hi_bytes[8];
162    p2s(b, hi_input, hi_bytes, mBasisSetNumbering);
163
164    Value * lo_input[8];
165    for (unsigned j = 0; j < 8; ++j) {
166        const unsigned idx = mBasisSetNumbering == cc::BitNumbering::LittleEndian ? j : j + 8;
167        lo_input[j] = b->loadInputStreamBlock("basisBits", b->getInt32(idx));
168    }
169    Value * lo_bytes[8];
170    p2s(b, lo_input, lo_bytes, mBasisSetNumbering);
171    Value * const extractionMask = b->loadInputStreamBlock("extractionMask", b->getInt32(0));
172    Value * const fieldCounts = b->simd_popcount(unitsPerRegister, extractionMask);
173    Value * unitCounts = partial_sum_popcounts(b, unitsPerRegister, fieldCounts);
174    Value * outputPtr = b->getOutputStreamBlockPtr("i16Stream", b->getInt32(0));
175    outputPtr = b->CreatePointerCast(outputPtr, int16PtrTy);
176    Value * const i16UnitsGenerated = b->getProducedItemCount("i16Stream"); // units generated to buffer
177    outputPtr = b->CreateGEP(outputPtr, b->CreateAnd(i16UnitsGenerated, blockMask));
178
179    Value * offset = b->getInt32(0);
180
181    for (unsigned j = 0; j < 8; ++j) {
182        Value * const merge0 = b->bitCast(b->esimd_mergel(8, hi_bytes[j], lo_bytes[j]));
183        b->CreateAlignedStore(merge0, b->CreateBitCast(b->CreateGEP(outputPtr, offset), bitBlockPtrTy), 1);
184        Value * const nextOffset1 = b->CreateZExt(b->CreateExtractElement(unitCounts, b->getInt32(2 * j)), i32Ty);
185        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
186            b->CreateAssert(b->CreateICmpULE(offset, nextOffset1), "deletion offset is not monotonically non-decreasing");
187        }
188        Value * const merge1 = b->bitCast(b->esimd_mergeh(8, hi_bytes[j], lo_bytes[j]));
189        b->CreateAlignedStore(merge1, b->CreateBitCast(b->CreateGEP(outputPtr, nextOffset1), bitBlockPtrTy), 1);
190        Value * const nextOffset2 = b->CreateZExt(b->CreateExtractElement(unitCounts, b->getInt32(2 * j + 1)), i32Ty);
191        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
192            b->CreateAssert(b->CreateICmpULE(nextOffset1, nextOffset2), "deletion offset is not monotonically non-decreasing");
193        }
194        offset = nextOffset2;
195    }
196
197    Value * const i16UnitsFinal = b->CreateAdd(i16UnitsGenerated, b->CreateZExt(offset, b->getSizeTy()));
198    b->setProducedItemCount("i16Stream", i16UnitsFinal);
199}
200
201
202
203
204P2SKernel::P2SKernel(const std::unique_ptr<kernel::KernelBuilder> & b, StreamSet * basisBits, StreamSet * byteStream, cc::BitNumbering numbering)
205: BlockOrientedKernel(b, "p2s" + cc::numberingSuffix(numbering),
206{Binding{"basisBits", basisBits}},
207{Binding{"byteStream", byteStream}},
208{}, {}, {}),
209mBasisSetNumbering(numbering) {
210
211}
212
213P2SMultipleStreamsKernel::P2SMultipleStreamsKernel(const std::unique_ptr<kernel::KernelBuilder> &b,
214                                                   const StreamSets & inputStreams,
215                                                   StreamSet * const outputStream,
216                                                   cc::BitNumbering basisNumbering)
217: BlockOrientedKernel(b, "p2sMultipleStreams" + cc::numberingSuffix(basisNumbering),
218{},
219{Binding{"byteStream", outputStream}},
220{}, {}, {}),
221mBasisSetNumbering(basisNumbering) {
222    for (unsigned i = 0; i < inputStreams.size(); i++) {
223        mInputStreamSets.emplace_back("basisBits_" + std::to_string(i), inputStreams[i]);
224    }
225}
226
227P2SKernelWithCompressedOutput::P2SKernelWithCompressedOutput(const std::unique_ptr<kernel::KernelBuilder> & b, cc::BitNumbering numbering)
228: BlockOrientedKernel(b, "p2s_compress" + cc::numberingSuffix(numbering),
229{Binding{b->getStreamSetTy(8, 1), "basisBits"}, Binding{b->getStreamSetTy(1, 1), "extractionMask"}},
230{Binding{b->getStreamSetTy(1, 8), "byteStream", BoundedRate(0, 1)}},
231{}, {}, {}),
232mBasisSetNumbering(numbering) {
233
234}
235
236P2S16Kernel::P2S16Kernel(const std::unique_ptr<kernel::KernelBuilder> & b, StreamSet *u16bits, StreamSet *u16bytes, cc::BitNumbering numbering)
237: BlockOrientedKernel(b, "p2s_16" + cc::numberingSuffix(numbering),
238{Binding{"basisBits", u16bits}},
239{Binding{"i16Stream", u16bytes}},
240{}, {}, {}),
241mBasisSetNumbering(numbering) {
242
243}
244
245P2S16KernelWithCompressedOutput::P2S16KernelWithCompressedOutput(const std::unique_ptr<kernel::KernelBuilder> & b,
246                                                                 StreamSet * basisBits, StreamSet * extractionMask, StreamSet * i16Stream,
247                                                                 cc::BitNumbering numbering)
248: BlockOrientedKernel(b, "p2s_16_compress" + cc::numberingSuffix(numbering),
249{Binding{"basisBits", basisBits},
250Binding{"extractionMask", extractionMask}},
251{Binding{"i16Stream", i16Stream, BoundedRate(0, 1)}},
252{}, {}, {}),
253mBasisSetNumbering(numbering) {
254
255}
256
257
258}
Note: See TracBrowser for help on using the repository browser.