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

Last change on this file since 6069 was 6069, checked in by cameron, 14 months ago

S2P_21 kernel for transposition of UTF-32; steps toward little-endian bit numbering throughout

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