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

Last change on this file since 6133 was 6132, checked in by xwa163, 11 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.