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

Last change on this file since 6132 was 6132, checked in by xwa163, 8 months ago
  1. More experiment on lz4 grep
  2. Improve performance of lzparabix grep
File size: 15.6 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
6#include "s2p_kernel.h"
7#include <kernels/kernel_builder.h>
8#include <pablo/pabloAST.h>
9#include <pablo/builder.hpp>
10#include <pablo/pe_pack.h>
11
12#include <llvm/Support/raw_ostream.h>
13
14using namespace llvm;
15
16namespace kernel {
17
18const int PACK_LANES = 2;
19
20void s2p_step(const std::unique_ptr<KernelBuilder> & iBuilder, Value * s0, Value * s1, Value * hi_mask, unsigned shift, Value * &p0, Value * &p1) {
21    Value * t0 = nullptr;
22    Value * t1 = nullptr;
23    if ((iBuilder->getBitBlockWidth() == 256) && (PACK_LANES == 2)) {
24        Value * x0 = iBuilder->esimd_mergel(128, s0, s1);
25        Value * x1 = iBuilder->esimd_mergeh(128, s0, s1);
26
27        t0 = iBuilder->hsimd_packh_in_lanes(PACK_LANES, 16, x0, x1); // TODO 4䞪bit streams时这里的16改䞺8?
28        t1 = iBuilder->hsimd_packl_in_lanes(PACK_LANES, 16, x0, x1);
29
30    } else {
31        t0 = iBuilder->hsimd_packh(16, s0, s1);
32        t1 = iBuilder->hsimd_packl(16, s0, s1);
33    }
34    if (shift == 1) {
35//        iBuilder->CallPrintRegister("t0", t0);
36//        iBuilder->CallPrintRegister("t1", t1);
37    }
38
39    p0 = iBuilder->simd_if(1, hi_mask, t0, iBuilder->simd_srli(16, t1, shift));
40    p1 = iBuilder->simd_if(1, hi_mask, iBuilder->simd_slli(16, t0, shift), t1);
41}
42
43void s2p(const std::unique_ptr<KernelBuilder> & iBuilder, Value * input[], Value * output[], cc::BitNumbering basisNumbering) {
44    {
45        //input[0 - 3]
46        Value* bit3311[2];
47        Value* bit2200[2];
48        for (unsigned i = 0; i < 2; i++) {
49            s2p_step(iBuilder, input[2 * i], input[2 * i + 1], iBuilder->simd_himask(2), 1, bit3311[i], bit2200[i]);
50        }
51
52        Value* out[4];
53        s2p_step(iBuilder, bit3311[0], bit3311[1],
54                 iBuilder->simd_himask(4), 2, out[3], out[1]);
55
56        s2p_step(iBuilder, bit2200[0], bit2200[1],
57                 iBuilder->simd_himask(4), 2, out[2], out[0]);
58        for (unsigned i = 0; i < 4; i++) {
59//            iBuilder->CallPrintRegister("input" + std::to_string(i), input[i]);
60        }
61        for (unsigned i = 0; i < 4; i++) {
62//            iBuilder->CallPrintRegister("out" + std::to_string(i), out[i]);
63        }
64    }
65
66
67    // Little-endian bit number is used for variables.
68    Value * bit66442200[4];
69    Value * bit77553311[4];
70//    iBuilder->CallPrintRegister("himask2", iBuilder->simd_himask(2));
71//    iBuilder->CallPrintRegister("himask4", iBuilder->simd_himask(4));
72//    iBuilder->CallPrintRegister("himask8", iBuilder->simd_himask(8));
73
74    for (unsigned i = 0; i < 4; i++) {
75        Value * s0 = input[2 * i];
76        Value * s1 = input[2 * i + 1];
77//        iBuilder->CallPrintRegister("s0_" + std::to_string(2 * i), s0);
78//        iBuilder->CallPrintRegister("s1_" + std::to_string(2 * i + 1), s1);
79        s2p_step(iBuilder, s0, s1, iBuilder->simd_himask(2), 1, bit77553311[i], bit66442200[i]);
80//        iBuilder->CallPrintRegister("bit77553311", bit77553311[i]);
81//        iBuilder->CallPrintRegister("bit66442200", bit66442200[i]);
82    }
83    Value * bit44440000[2];
84    Value * bit66662222[2];
85    Value * bit55551111[2];
86    Value * bit77773333[2];
87    for (unsigned j = 0; j<2; j++) {
88        s2p_step(iBuilder, bit66442200[2*j], bit66442200[2*j+1],
89                 iBuilder->simd_himask(4), 2, bit66662222[j], bit44440000[j]);
90        s2p_step(iBuilder, bit77553311[2*j], bit77553311[2*j+1],
91                 iBuilder->simd_himask(4), 2, bit77773333[j], bit55551111[j]);
92    }
93    if (basisNumbering == cc::BitNumbering::LittleEndian) {
94        s2p_step(iBuilder, bit44440000[0], bit44440000[1], iBuilder->simd_himask(8), 4, output[4], output[0]);
95        s2p_step(iBuilder, bit55551111[0], bit55551111[1], iBuilder->simd_himask(8), 4, output[5], output[1]);
96        s2p_step(iBuilder, bit66662222[0], bit66662222[1], iBuilder->simd_himask(8), 4, output[6], output[2]);
97        s2p_step(iBuilder, bit77773333[0], bit77773333[1], iBuilder->simd_himask(8), 4, output[7], output[3]);
98    }
99    else {
100        s2p_step(iBuilder, bit44440000[0], bit44440000[1], iBuilder->simd_himask(8), 4, output[3], output[7]);
101        s2p_step(iBuilder, bit55551111[0], bit55551111[1], iBuilder->simd_himask(8), 4, output[2], output[6]);
102        s2p_step(iBuilder, bit66662222[0], bit66662222[1], iBuilder->simd_himask(8), 4, output[1], output[5]);
103        s2p_step(iBuilder, bit77773333[0], bit77773333[1], iBuilder->simd_himask(8), 4, output[0], output[4]);
104    }
105
106    for (unsigned i = 0; i < 8; i++) {
107//        iBuilder->CallPrintRegister("input" + std::to_string(i), input[i]);
108    }
109    for (unsigned i = 0; i < 8; i++) {
110//        iBuilder->CallPrintRegister("output" + std::to_string(i), output[i]);
111    }
112}
113
114/* Alternative transposition model, but small field width packs are problematic. */
115#if 0
116void s2p_ideal(const std::unique_ptr<KernelBuilder> & iBuilder, Value * input[], Value * output[], cc::BitNumbering basisNumbering) {
117    Value * hi_nybble[4];
118    Value * lo_nybble[4];
119    for (unsigned i = 0; i<4; i++) {
120        Value * s0 = input[2*i];
121        Value * s1 = input[2*i+1];
122        hi_nybble[i] = iBuilder->hsimd_packh(8, s0, s1);
123        lo_nybble[i] = iBuilder->hsimd_packl(8, s0, s1);
124    }
125    Value * pair76[2];
126    Value * pair54[2];
127    Value * pair32[2];
128    Value * pair10[2];
129    for (unsigned i = 0; i<2; i++) {
130        pair76[i] = iBuilder->hsimd_packh(4, hi_nybble[2*i], hi_nybble[2*i+1]);
131        pair54[i] = iBuilder->hsimd_packl(4, hi_nybble[2*i], hi_nybble[2*i+1]);
132        pair32[i] = iBuilder->hsimd_packh(4, lo_nybble[2*i], lo_nybble[2*i+1]);
133        pair10[i] = iBuilder->hsimd_packl(4, lo_nybble[2*i], lo_nybble[2*i+1]);
134    }
135    if (basisNumbering == cc::BitNumbering::LittleEndian) {
136        output[7] = iBuilder->hsimd_packh(2, pair76[0], pair76[1]);
137        output[6] = iBuilder->hsimd_packl(2, pair76[0], pair76[1]);
138        output[5] = iBuilder->hsimd_packh(2, pair54[0], pair54[1]);
139        output[4] = iBuilder->hsimd_packl(2, pair54[0], pair54[1]);
140        output[3] = iBuilder->hsimd_packh(2, pair32[0], pair32[1]);
141        output[2] = iBuilder->hsimd_packl(2, pair32[0], pair32[1]);
142        output[1] = iBuilder->hsimd_packh(2, pair10[0], pair10[1]);
143        output[0] = iBuilder->hsimd_packl(2, pair10[0], pair10[1]);
144    } else {
145        output[0] = iBuilder->hsimd_packh(2, pair76[0], pair76[1]);
146        output[1] = iBuilder->hsimd_packl(2, pair76[0], pair76[1]);
147        output[2] = iBuilder->hsimd_packh(2, pair54[0], pair54[1]);
148        output[3] = iBuilder->hsimd_packl(2, pair54[0], pair54[1]);
149        output[4] = iBuilder->hsimd_packh(2, pair32[0], pair32[1]);
150        output[5] = iBuilder->hsimd_packl(2, pair32[0], pair32[1]);
151        output[6] = iBuilder->hsimd_packh(2, pair10[0], pair10[1]);
152        output[7] = iBuilder->hsimd_packl(2, pair10[0], pair10[1]);
153    }
154}
155#endif
156
157
158    S2P4StreamByPEXTKernel::S2P4StreamByPEXTKernel(const std::unique_ptr<kernel::KernelBuilder> & b)
159            :BlockOrientedKernel("s2p4StreamByPEXT",
160                                 {
161                                         Binding{b->getStreamSetTy(1, 4), "byteStream", FixedRate(), Principal()}
162                                 },
163                                 {
164                                         Binding{b->getStreamSetTy(4, 1), "basisBits"}
165                                 }, {}, {}, {}) {
166
167    }
168
169    void S2P4StreamByPEXTKernel::generateDoBlockMethod(const std::unique_ptr<KernelBuilder> & b) {
170        Function* PEXT_func = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_bmi_pext_64);
171        uint64_t pextBaseMask = 0x1111111111111111;
172
173        Value* inputBasePtr = b->CreatePointerCast(b->getInputStreamBlockPtr("byteStream", b->getSize(0)), b->getInt64Ty()->getPointerTo());
174
175        Value* outputBlocks[4];
176        for (unsigned i = 0; i < 4; i++) {
177            outputBlocks[i] = ConstantVector::getNullValue(b->getBitBlockType());
178        }
179
180        for (unsigned i = 0; i < b->getBitBlockWidth() / 64; i++) {
181            Value* currentOutput[4];
182            for (unsigned iIndex = 0; iIndex < 4; iIndex++) {
183                currentOutput[iIndex] = b->getInt64(0);
184            }
185
186            for (unsigned j = 0; j < 4; j++) {
187                unsigned inputIndex = i * 4 + j;
188
189                Value* currentInput = b->CreateLoad(b->CreateGEP(inputBasePtr, b->getInt32(inputIndex)));
190                for (unsigned k = 0; k < 4; k++) {
191
192                    Value* newBits = b->CreateCall(
193                            PEXT_func,{
194                                    currentInput,
195                                    b->getInt64(pextBaseMask << k)
196                            }
197                    );
198
199                    currentOutput[k] = b->CreateOr(currentOutput[k], b->CreateShl(newBits, 16 * j));
200                }
201            }
202
203            for (unsigned iIndex = 0; iIndex < 4; iIndex++) {
204                outputBlocks[iIndex] = b->CreateInsertElement(outputBlocks[iIndex], currentOutput[iIndex], i);
205            }
206        }
207
208        for (unsigned i = 0; i < 4; i++) {
209            b->storeOutputStreamBlock("basisBits", b->getInt32(i), outputBlocks[i]);
210//            b->CallPrintRegister("outputBlocks" + std::to_string(i), outputBlocks[i]);
211        }
212    }
213
214void S2PKernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & kb, Value * const numOfBlocks) {
215    BasicBlock * entry = kb->GetInsertBlock();
216    BasicBlock * processBlock = kb->CreateBasicBlock("processBlock");
217    BasicBlock * s2pDone = kb->CreateBasicBlock("s2pDone");
218    Constant * const ZERO = kb->getSize(0);
219
220    kb->CreateBr(processBlock);
221   
222    kb->SetInsertPoint(processBlock);
223    PHINode * blockOffsetPhi = kb->CreatePHI(kb->getSizeTy(), 2); // block offset from the base block, e.g. 0, 1, 2, ...
224    blockOffsetPhi->addIncoming(ZERO, entry);
225
226    Value * bytepack[8];
227    for (unsigned i = 0; i < 8; i++) {
228        if (mAligned) {
229            bytepack[i] = kb->loadInputStreamPack("byteStream", ZERO, kb->getInt32(i), blockOffsetPhi);
230        } else {
231            Value * ptr = kb->getInputStreamPackPtr("byteStream", ZERO, kb->getInt32(i), blockOffsetPhi);
232            // CreateLoad defaults to aligned here, so we need to force the alignment to 1 byte.
233            bytepack[i] = kb->CreateAlignedLoad(ptr, 1);
234        }
235    }
236    Value * basisbits[8];
237    s2p(kb, bytepack, basisbits, mBasisSetNumbering);
238    for (unsigned i = 0; i < mNumOfStreams; ++i) {
239        kb->storeOutputStreamBlock("basisBits", kb->getInt32(i), blockOffsetPhi, basisbits[i]);
240    }
241    Value * nextBlk = kb->CreateAdd(blockOffsetPhi, kb->getSize(1));
242    blockOffsetPhi->addIncoming(nextBlk, processBlock);
243    Value * moreToDo = kb->CreateICmpNE(nextBlk, numOfBlocks);
244    kb->CreateCondBr(moreToDo, processBlock, s2pDone);
245    kb->SetInsertPoint(s2pDone);
246}
247
248S2PKernel::S2PKernel(const std::unique_ptr<KernelBuilder> & b, cc::BitNumbering numbering, bool aligned, std::string prefix, unsigned numOfStreams)
249    : MultiBlockKernel(aligned ? prefix + "s2p" + cc::numberingSuffix(numbering): prefix + "s2p_unaligned" + cc::numberingSuffix(numbering),
250    {Binding{b->getStreamSetTy(1, 8), "byteStream", FixedRate(), Principal()}},
251    {Binding{b->getStreamSetTy(numOfStreams, 1), "basisBits"}}, {}, {}, {}),
252  mBasisSetNumbering(numbering),
253  mAligned(aligned),
254  mNumOfStreams(numOfStreams)
255{
256    if (!aligned) {
257        mStreamSetInputs[0].addAttribute(Misaligned());
258    }
259}
260   
261S2P_21Kernel::S2P_21Kernel(const std::unique_ptr<KernelBuilder> & b, cc::BitNumbering numbering)
262: MultiBlockKernel("s2p_21" + cc::numberingSuffix(numbering),
263                   {Binding{b->getStreamSetTy(1, 32), "codeUnitStream", FixedRate(), Principal()}},
264                   {Binding{b->getStreamSetTy(21, 1), "basisBits"}}, {}, {}, {}),
265    mBasisSetNumbering(numbering) {
266}
267
268void S2P_21Kernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & kb, Value * const numOfBlocks) {
269    BasicBlock * entry = kb->GetInsertBlock();
270    BasicBlock * processBlock = kb->CreateBasicBlock("s2p21_loop");
271    BasicBlock * s2pDone = kb->CreateBasicBlock("s2p21_done");
272    Constant * const ZERO = kb->getSize(0);
273   
274    kb->CreateBr(processBlock);
275    kb->SetInsertPoint(processBlock);
276    PHINode * blockOffsetPhi = kb->CreatePHI(kb->getSizeTy(), 2); // block offset from the base block, e.g. 0, 1, 2, ...
277    blockOffsetPhi->addIncoming(ZERO, entry);
278    Value * u32byte0[8];
279    Value * u32byte1[8];
280    Value * u32byte2[8];
281    for (unsigned i = 0; i < 8; i++) {
282        Value * UTF32units[4];
283        for (unsigned j = 0; j < 4; j++) {
284            UTF32units[j] = kb->loadInputStreamPack("codeUnitStream", ZERO, kb->getInt32(4*i + j), blockOffsetPhi);
285        }
286        Value * u32lo16_0 = kb->hsimd_packl(32, UTF32units[0], UTF32units[1]);
287        Value * u32lo16_1 = kb->hsimd_packl(32, UTF32units[2], UTF32units[3]);
288        Value * u32hi16_0 = kb->hsimd_packh(32, UTF32units[0], UTF32units[1]);
289        Value * u32hi16_1 = kb->hsimd_packh(32, UTF32units[2], UTF32units[3]);
290        u32byte0[i] = kb->hsimd_packl(16, u32lo16_0, u32lo16_1);
291        u32byte1[i] = kb->hsimd_packh(16, u32lo16_0, u32lo16_1);
292        u32byte2[i] = kb->hsimd_packl(16, u32hi16_0, u32hi16_1);
293    #ifdef VALIDATE_U32
294        //  Validation should ensure that none of the high 11 bits are
295        //  set for any UTF-32 code unit.   We simply combine the bits
296        //  of code units together with bitwise-or, and then perform a
297        //  single check at the end.
298        u32_check = simd_or(u32_check, simd_or(u32hi16_0, u32hi16_1));
299    #endif
300    }
301    Value * basisbits[24];
302    s2p(kb, u32byte0, basisbits, cc::BitNumbering::LittleEndian);
303    s2p(kb, u32byte1, &basisbits[8], cc::BitNumbering::LittleEndian);
304    s2p(kb, u32byte2, &basisbits[16], cc::BitNumbering::LittleEndian);
305    for (unsigned i = 0; i < 21; ++i) {
306        const unsigned bitIdx = mBasisSetNumbering == cc::BitNumbering::LittleEndian ? i : 21 - i;
307        kb->storeOutputStreamBlock("basisBits", kb->getInt32(i), blockOffsetPhi, basisbits[bitIdx]);
308    }
309    Value * nextBlk = kb->CreateAdd(blockOffsetPhi, kb->getSize(1));
310    blockOffsetPhi->addIncoming(nextBlk, processBlock);
311    Value * moreToDo = kb->CreateICmpNE(nextBlk, numOfBlocks);
312    kb->CreateCondBr(moreToDo, processBlock, s2pDone);
313    kb->SetInsertPoint(s2pDone);
314}
315
316void S2P_PabloKernel::generatePabloMethod() {
317    pablo::PabloBlock * const pb = getEntryScope();
318    const unsigned steps = std::log2(mCodeUnitWidth);
319    std::vector<PabloAST *> streamSet[steps + 1];
320    for (unsigned i = 0; i <= steps; i++) {
321        streamSet[i].resize(1<<i);
322    }
323    streamSet[0][0] = pb->createExtract(getInputStreamVar("codeUnitStream"), pb->getInteger(0));
324    unsigned streamWidth = mCodeUnitWidth;
325    for (unsigned i = 1; i <= steps; i++) {
326        for (unsigned j = 0; j < streamSet[i-1].size(); j++) {
327            auto strm = streamSet[i-1][j];
328            streamSet[i][2*j] = pb->createPackL(pb->getInteger(streamWidth), strm);
329            streamSet[i][2*j+1] = pb->createPackH(pb->getInteger(streamWidth), strm);
330        }
331        streamWidth = streamWidth/2;
332    }
333    for (unsigned bit = 0; bit < mCodeUnitWidth; bit++) {
334        const unsigned bitIndex = mBasisSetNumbering == cc::BitNumbering::LittleEndian ? bit : mCodeUnitWidth-1-bit;
335        pb->createAssign(pb->createExtract(getOutputStreamVar("basisBits"), pb->getInteger(bitIndex)), streamSet[steps][bit]);
336    }
337}
338
339S2P_PabloKernel::S2P_PabloKernel(const std::unique_ptr<kernel::KernelBuilder> & b, const unsigned codeUnitWidth, cc::BitNumbering numbering)
340: PabloKernel(b, "s2p_pablo" + std::to_string(codeUnitWidth) + cc::numberingSuffix(numbering),
341    {Binding{b->getStreamSetTy(1, codeUnitWidth), "codeUnitStream"}},
342    {Binding{b->getStreamSetTy(codeUnitWidth, 1), "basisBits"}}),
343  mCodeUnitWidth(codeUnitWidth),
344  mBasisSetNumbering(numbering) {
345}
346
347}
Note: See TracBrowser for help on using the repository browser.