source: icGREP/icgrep-devel/icgrep/kernels/s2p_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: 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.