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

Last change on this file since 6089 was 6089, checked in by cameron, 10 months ago

Little-endian/big-endian bit number options, default to little-endian

File size: 13.5 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        t0 = iBuilder->hsimd_packh_in_lanes(PACK_LANES, 16, x0, x1);
27        t1 = iBuilder->hsimd_packl_in_lanes(PACK_LANES, 16, x0, x1);
28    } else {
29        t0 = iBuilder->hsimd_packh(16, s0, s1);
30        t1 = iBuilder->hsimd_packl(16, s0, s1);
31    }
32    p0 = iBuilder->simd_if(1, hi_mask, t0, iBuilder->simd_srli(16, t1, shift));
33    p1 = iBuilder->simd_if(1, hi_mask, iBuilder->simd_slli(16, t0, shift), t1);
34}
35
36void s2p(const std::unique_ptr<KernelBuilder> & iBuilder, Value * input[], Value * output[], cc::BitNumbering basisNumbering) {
37    // Little-endian bit number is used for variables.
38    Value * bit66442200[4];
39    Value * bit77553311[4];
40
41    for (unsigned i = 0; i < 4; i++) {
42        Value * s0 = input[2 * i];
43        Value * s1 = input[2 * i + 1];
44        s2p_step(iBuilder, s0, s1, iBuilder->simd_himask(2), 1, bit77553311[i], bit66442200[i]);
45    }
46    Value * bit44440000[2];
47    Value * bit66662222[2];
48    Value * bit55551111[2];
49    Value * bit77773333[2];
50    for (unsigned j = 0; j<2; j++) {
51        s2p_step(iBuilder, bit66442200[2*j], bit66442200[2*j+1],
52                 iBuilder->simd_himask(4), 2, bit66662222[j], bit44440000[j]);
53        s2p_step(iBuilder, bit77553311[2*j], bit77553311[2*j+1],
54                 iBuilder->simd_himask(4), 2, bit77773333[j], bit55551111[j]);
55    }
56    if (basisNumbering == cc::BitNumbering::LittleEndian) {
57        s2p_step(iBuilder, bit44440000[0], bit44440000[1], iBuilder->simd_himask(8), 4, output[4], output[0]);
58        s2p_step(iBuilder, bit55551111[0], bit55551111[1], iBuilder->simd_himask(8), 4, output[5], output[1]);
59        s2p_step(iBuilder, bit66662222[0], bit66662222[1], iBuilder->simd_himask(8), 4, output[6], output[2]);
60        s2p_step(iBuilder, bit77773333[0], bit77773333[1], iBuilder->simd_himask(8), 4, output[7], output[3]);
61    }
62    else {
63        s2p_step(iBuilder, bit44440000[0], bit44440000[1], iBuilder->simd_himask(8), 4, output[3], output[7]);
64        s2p_step(iBuilder, bit55551111[0], bit55551111[1], iBuilder->simd_himask(8), 4, output[2], output[6]);
65        s2p_step(iBuilder, bit66662222[0], bit66662222[1], iBuilder->simd_himask(8), 4, output[1], output[5]);
66        s2p_step(iBuilder, bit77773333[0], bit77773333[1], iBuilder->simd_himask(8), 4, output[0], output[4]);
67    }
68}
69
70/* Alternative transposition model, but small field width packs are problematic. */
71#if 0
72void s2p_ideal(const std::unique_ptr<KernelBuilder> & iBuilder, Value * input[], Value * output[], cc::BitNumbering basisNumbering) {
73    Value * hi_nybble[4];
74    Value * lo_nybble[4];
75    for (unsigned i = 0; i<4; i++) {
76        Value * s0 = input[2*i];
77        Value * s1 = input[2*i+1];
78        hi_nybble[i] = iBuilder->hsimd_packh(8, s0, s1);
79        lo_nybble[i] = iBuilder->hsimd_packl(8, s0, s1);
80    }
81    Value * pair76[2];
82    Value * pair54[2];
83    Value * pair32[2];
84    Value * pair10[2];
85    for (unsigned i = 0; i<2; i++) {
86        pair76[i] = iBuilder->hsimd_packh(4, hi_nybble[2*i], hi_nybble[2*i+1]);
87        pair54[i] = iBuilder->hsimd_packl(4, hi_nybble[2*i], hi_nybble[2*i+1]);
88        pair32[i] = iBuilder->hsimd_packh(4, lo_nybble[2*i], lo_nybble[2*i+1]);
89        pair10[i] = iBuilder->hsimd_packl(4, lo_nybble[2*i], lo_nybble[2*i+1]);
90    }
91    if (basisNumbering == cc::BitNumbering::LittleEndian) {
92        output[7] = iBuilder->hsimd_packh(2, pair76[0], pair76[1]);
93        output[6] = iBuilder->hsimd_packl(2, pair76[0], pair76[1]);
94        output[5] = iBuilder->hsimd_packh(2, pair54[0], pair54[1]);
95        output[4] = iBuilder->hsimd_packl(2, pair54[0], pair54[1]);
96        output[3] = iBuilder->hsimd_packh(2, pair32[0], pair32[1]);
97        output[2] = iBuilder->hsimd_packl(2, pair32[0], pair32[1]);
98        output[1] = iBuilder->hsimd_packh(2, pair10[0], pair10[1]);
99        output[0] = iBuilder->hsimd_packl(2, pair10[0], pair10[1]);
100    } else {
101        output[0] = iBuilder->hsimd_packh(2, pair76[0], pair76[1]);
102        output[1] = iBuilder->hsimd_packl(2, pair76[0], pair76[1]);
103        output[2] = iBuilder->hsimd_packh(2, pair54[0], pair54[1]);
104        output[3] = iBuilder->hsimd_packl(2, pair54[0], pair54[1]);
105        output[4] = iBuilder->hsimd_packh(2, pair32[0], pair32[1]);
106        output[5] = iBuilder->hsimd_packl(2, pair32[0], pair32[1]);
107        output[6] = iBuilder->hsimd_packh(2, pair10[0], pair10[1]);
108        output[7] = iBuilder->hsimd_packl(2, pair10[0], pair10[1]);
109    }
110}
111#endif
112   
113void S2PKernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & kb, Value * const numOfBlocks) {
114    BasicBlock * entry = kb->GetInsertBlock();
115    BasicBlock * processBlock = kb->CreateBasicBlock("processBlock");
116    BasicBlock * s2pDone = kb->CreateBasicBlock("s2pDone");
117    Constant * const ZERO = kb->getSize(0);
118
119    kb->CreateBr(processBlock);
120   
121    kb->SetInsertPoint(processBlock);
122    PHINode * blockOffsetPhi = kb->CreatePHI(kb->getSizeTy(), 2); // block offset from the base block, e.g. 0, 1, 2, ...
123    blockOffsetPhi->addIncoming(ZERO, entry);
124
125    Value * bytepack[8];
126    for (unsigned i = 0; i < 8; i++) {
127        if (mAligned) {
128            bytepack[i] = kb->loadInputStreamPack("byteStream", ZERO, kb->getInt32(i), blockOffsetPhi);
129        } else {
130            Value * ptr = kb->getInputStreamPackPtr("byteStream", ZERO, kb->getInt32(i), blockOffsetPhi);
131            // CreateLoad defaults to aligned here, so we need to force the alignment to 1 byte.
132            bytepack[i] = kb->CreateAlignedLoad(ptr, 1);
133        }
134    }
135    Value * basisbits[8];
136    s2p(kb, bytepack, basisbits, mBasisSetNumbering);
137    for (unsigned i = 0; i < 8; ++i) {
138        kb->storeOutputStreamBlock("basisBits", kb->getInt32(i), blockOffsetPhi, basisbits[i]);
139    }
140    Value * nextBlk = kb->CreateAdd(blockOffsetPhi, kb->getSize(1));
141    blockOffsetPhi->addIncoming(nextBlk, processBlock);
142    Value * moreToDo = kb->CreateICmpNE(nextBlk, numOfBlocks);
143    kb->CreateCondBr(moreToDo, processBlock, s2pDone);
144    kb->SetInsertPoint(s2pDone);
145}
146
147S2PKernel::S2PKernel(const std::unique_ptr<KernelBuilder> & b, cc::BitNumbering numbering, bool aligned, std::string prefix)
148    : MultiBlockKernel(aligned ? prefix + "s2p" + cc::numberingSuffix(numbering): prefix + "s2p_unaligned" + cc::numberingSuffix(numbering),
149    {Binding{b->getStreamSetTy(1, 8), "byteStream", FixedRate(), Principal()}},
150    {Binding{b->getStreamSetTy(8, 1), "basisBits"}}, {}, {}, {}),
151  mBasisSetNumbering(numbering),
152  mAligned(aligned) {
153    if (!aligned) {
154        mStreamSetInputs[0].addAttribute(Misaligned());
155    }
156}
157   
158S2P_21Kernel::S2P_21Kernel(const std::unique_ptr<KernelBuilder> & b, cc::BitNumbering numbering)
159: MultiBlockKernel("s2p_21" + cc::numberingSuffix(numbering),
160                   {Binding{b->getStreamSetTy(1, 32), "codeUnitStream", FixedRate(), Principal()}},
161                   {Binding{b->getStreamSetTy(21, 1), "basisBits"}}, {}, {}, {}),
162    mBasisSetNumbering(numbering) {
163}
164
165void S2P_21Kernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & kb, Value * const numOfBlocks) {
166    BasicBlock * entry = kb->GetInsertBlock();
167    BasicBlock * processBlock = kb->CreateBasicBlock("s2p21_loop");
168    BasicBlock * s2pDone = kb->CreateBasicBlock("s2p21_done");
169    Constant * const ZERO = kb->getSize(0);
170   
171    kb->CreateBr(processBlock);
172    kb->SetInsertPoint(processBlock);
173    PHINode * blockOffsetPhi = kb->CreatePHI(kb->getSizeTy(), 2); // block offset from the base block, e.g. 0, 1, 2, ...
174    blockOffsetPhi->addIncoming(ZERO, entry);
175    Value * u32byte0[8];
176    Value * u32byte1[8];
177    Value * u32byte2[8];
178    for (unsigned i = 0; i < 8; i++) {
179        Value * UTF32units[4];
180        for (unsigned j = 0; j < 4; j++) {
181            UTF32units[j] = kb->loadInputStreamPack("codeUnitStream", ZERO, kb->getInt32(4*i + j), blockOffsetPhi);
182        }
183        Value * u32lo16_0 = kb->hsimd_packl(32, UTF32units[0], UTF32units[1]);
184        Value * u32lo16_1 = kb->hsimd_packl(32, UTF32units[2], UTF32units[3]);
185        Value * u32hi16_0 = kb->hsimd_packh(32, UTF32units[0], UTF32units[1]);
186        Value * u32hi16_1 = kb->hsimd_packh(32, UTF32units[2], UTF32units[3]);
187        u32byte0[i] = kb->hsimd_packl(16, u32lo16_0, u32lo16_1);
188        u32byte1[i] = kb->hsimd_packh(16, u32lo16_0, u32lo16_1);
189        u32byte2[i] = kb->hsimd_packl(16, u32hi16_0, u32hi16_1);
190    #ifdef VALIDATE_U32
191        //  Validation should ensure that none of the high 11 bits are
192        //  set for any UTF-32 code unit.   We simply combine the bits
193        //  of code units together with bitwise-or, and then perform a
194        //  single check at the end.
195        u32_check = simd_or(u32_check, simd_or(u32hi16_0, u32hi16_1));
196    #endif
197    }
198    Value * basisbits[24];
199    s2p(kb, u32byte0, basisbits, cc::BitNumbering::LittleEndian);
200    s2p(kb, u32byte1, &basisbits[8], cc::BitNumbering::LittleEndian);
201    s2p(kb, u32byte2, &basisbits[16], cc::BitNumbering::LittleEndian);
202    for (unsigned i = 0; i < 21; ++i) {
203        const unsigned bitIdx = mBasisSetNumbering == cc::BitNumbering::LittleEndian ? i : 21 - i;
204        kb->storeOutputStreamBlock("basisBits", kb->getInt32(i), blockOffsetPhi, basisbits[bitIdx]);
205    }
206    Value * nextBlk = kb->CreateAdd(blockOffsetPhi, kb->getSize(1));
207    blockOffsetPhi->addIncoming(nextBlk, processBlock);
208    Value * moreToDo = kb->CreateICmpNE(nextBlk, numOfBlocks);
209    kb->CreateCondBr(moreToDo, processBlock, s2pDone);
210    kb->SetInsertPoint(s2pDone);
211}
212
213void S2P_PabloKernel::generatePabloMethod() {
214    pablo::PabloBlock * const pb = getEntryScope();
215    const unsigned steps = std::log2(mCodeUnitWidth);
216    std::vector<PabloAST *> streamSet[steps + 1];
217    for (unsigned i = 0; i <= steps; i++) {
218        streamSet[i].resize(1<<i);
219    }
220    streamSet[0][0] = pb->createExtract(getInputStreamVar("codeUnitStream"), pb->getInteger(0));
221    unsigned streamWidth = mCodeUnitWidth;
222    for (unsigned i = 1; i <= steps; i++) {
223        for (unsigned j = 0; j < streamSet[i-1].size(); j++) {
224            auto strm = streamSet[i-1][j];
225            streamSet[i][2*j] = pb->createPackL(pb->getInteger(streamWidth), strm);
226            streamSet[i][2*j+1] = pb->createPackH(pb->getInteger(streamWidth), strm);
227        }
228        streamWidth = streamWidth/2;
229    }
230    for (unsigned bit = 0; bit < mCodeUnitWidth; bit++) {
231        const unsigned bitIndex = mBasisSetNumbering == cc::BitNumbering::LittleEndian ? bit : mCodeUnitWidth-1-bit;
232        pb->createAssign(pb->createExtract(getOutputStreamVar("basisBits"), pb->getInteger(bitIndex)), streamSet[steps][bit]);
233    }
234}
235
236S2P_PabloKernel::S2P_PabloKernel(const std::unique_ptr<kernel::KernelBuilder> & b, const unsigned codeUnitWidth, cc::BitNumbering numbering)
237: PabloKernel(b, "s2p_pablo" + std::to_string(codeUnitWidth) + cc::numberingSuffix(numbering),
238    {Binding{b->getStreamSetTy(1, codeUnitWidth), "codeUnitStream"}},
239    {Binding{b->getStreamSetTy(codeUnitWidth, 1), "basisBits"}}),
240  mCodeUnitWidth(codeUnitWidth),
241  mBasisSetNumbering(numbering) {
242}
243
244
245S2PByPextKernel::S2PByPextKernel(const std::unique_ptr<kernel::KernelBuilder> &b, cc::BitNumbering numbering, std::string prefix)
246        : BlockOrientedKernel(prefix + "s2pByPext" + cc::numberingSuffix(numbering),
247                           {Binding{b->getStreamSetTy(1, 8), "byteStream", FixedRate(), Principal()}},
248                           {Binding{b->getStreamSetTy(8, 1), "basisBits"}}, {}, {}, {}),
249    mBasisSetNumbering(numbering) {
250}
251
252void S2PByPextKernel::generateDoBlockMethod(const std::unique_ptr<KernelBuilder> &b) {
253    Value* inputBasePtr = b->CreatePointerCast(b->getInputStreamBlockPtr("byteStream", b->getSize(0)), b->getInt64Ty()->getPointerTo());
254    std::vector<Value*> outputPtrs(8, nullptr);
255    for (unsigned i = 0; i < 8; i++) {
256        outputPtrs[i] = b->CreatePointerCast(b->getOutputStreamBlockPtr("basisBits", b->getSize(i)), b->getInt64Ty()->getPointerTo());
257    }
258    uint64_t base_mask = 0x0101010101010101;
259
260    Constant * pext = Intrinsic::getDeclaration(b->getModule(), Intrinsic::x86_bmi_pext_64);
261
262    for (unsigned iBlockIndex = 0; iBlockIndex < 4; iBlockIndex++) {
263        std::vector<Value*> tempValues(8, b->getInt64(0));
264        for (size_t iDataIndex = 0; iDataIndex < 8; iDataIndex++) {
265            Value* inputData = b->CreateLoad(b->CreateGEP(inputBasePtr, b->getSize(iDataIndex + iBlockIndex * 8)));
266            for (unsigned iStreamIndex = 0; iStreamIndex < 8; iStreamIndex++) {
267                const unsigned bitIndex = mBasisSetNumbering == cc::BitNumbering::LittleEndian ? iStreamIndex : 7 - iStreamIndex;
268                Value* targetMask = b->getInt64(base_mask << bitIndex);
269                Value * const outputValue = b->CreateCall(pext, {inputData, targetMask});
270                tempValues[iStreamIndex] = b->CreateOr(tempValues[iStreamIndex], b->CreateShl(outputValue, b->getInt64(iDataIndex * 8)));
271            }
272        }
273        for (int iStreamIndex = 0; iStreamIndex < 8; iStreamIndex++) {
274            b->CreateStore(tempValues[iStreamIndex], b->CreateGEP(outputPtrs[iStreamIndex], b->getSize(iBlockIndex)));
275        }
276    }
277}
278}
Note: See TracBrowser for help on using the repository browser.