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

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