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

Last change on this file since 6004 was 6004, checked in by cameron, 16 months ago

Restructuring step for DeletionKernel?: move partial sum popcount in p2sWithCompress

File size: 8.7 KB
RevLine 
[4987]1#include "p2s_kernel.h"
[5267]2#include <kernels/streamset.h>
[5436]3#include <kernels/kernel_builder.h>
[5771]4#include <toolchain/toolchain.h>
5#include <llvm/Support/Compiler.h>
[5436]6
[5267]7namespace llvm { class Value; }
[4987]8
[5260]9using namespace llvm;
[5303]10using namespace parabix;
[5040]11
[4987]12namespace kernel{
13       
[5440]14void p2s_step(const std::unique_ptr<KernelBuilder> & iBuilder, Value * p0, Value * p1, Value * hi_mask, unsigned shift, Value * &s1, Value * &s0) {
[4987]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
[5440]21inline void p2s(const std::unique_ptr<KernelBuilder> & iBuilder, Value * p[], Value * s[]) {
[4987]22    Value * bit00004444[2];
23    Value * bit22226666[2];
24    Value * bit11115555[2];
25    Value * bit33337777[2];
26    p2s_step(iBuilder, p[0], p[4], iBuilder->simd_himask(8), 4, bit00004444[1], bit00004444[0]);
27    p2s_step(iBuilder, p[1], p[5], iBuilder->simd_himask(8), 4, bit11115555[1], bit11115555[0]);
28    p2s_step(iBuilder, p[2], p[6], iBuilder->simd_himask(8), 4, bit22226666[1], bit22226666[0]);
29    p2s_step(iBuilder, p[3], p[7], iBuilder->simd_himask(8), 4, bit33337777[1], bit33337777[0]);
30    Value * bit00224466[4];
31    Value * bit11335577[4];
32    for (unsigned j = 0; j<2; j++) {
33        p2s_step(iBuilder, bit00004444[j], bit22226666[j],iBuilder->simd_himask(4), 2, bit00224466[2*j+1], bit00224466[2*j]);
34        p2s_step(iBuilder, bit11115555[j], bit33337777[j],iBuilder->simd_himask(4), 2, bit11335577[2*j+1], bit11335577[2*j]);
35    }
36    for (unsigned j = 0; j<4; j++) {
37        p2s_step(iBuilder, bit00224466[j], bit11335577[j], iBuilder->simd_himask(2), 1, s[2*j+1], s[2*j]);
38    }
39}
40               
[5755]41void P2SKernel::generateDoBlockMethod(const std::unique_ptr<KernelBuilder> & b) {
[5071]42    Value * p_bitblock[8];
43    for (unsigned i = 0; i < 8; i++) {
[5755]44        p_bitblock[i] = b->loadInputStreamBlock("basisBits", b->getInt32(i));
[4987]45    }
[5071]46    Value * s_bytepack[8];
[5755]47    p2s(b, p_bitblock, s_bytepack);
[4987]48    for (unsigned j = 0; j < 8; ++j) {
[5755]49        b->storeOutputStreamPack("byteStream", b->getInt32(0), b->getInt32(j), s_bytepack[j]);
[4987]50    }
51}
[5260]52
[6004]53inline Value * partial_sum_popcounts(const std::unique_ptr<KernelBuilder> & iBuilder, const unsigned fw, Value * popcounts) {
54    Value * summed_counts = popcounts;
55    const auto count = iBuilder->getBitBlockWidth() / fw;
56    for (unsigned move = 1; move < count; move *= 2) {
57        summed_counts = iBuilder->simd_add(fw, summed_counts, iBuilder->mvmd_slli(fw, summed_counts, move));
58    }
59    return summed_counts;
60}
61
[5755]62void P2SKernelWithCompressedOutput::generateDoBlockMethod(const std::unique_ptr<KernelBuilder> & b) {
63    IntegerType * i32 = b->getInt32Ty();
64    PointerType * bitBlockPtrTy = PointerType::get(b->getBitBlockType(), 0);
[6004]65    unsigned const unitsPerRegister = b->getBitBlockWidth()/8;
[5260]66
[5246]67    Value * basisBits[8];
[5079]68    for (unsigned i = 0; i < 8; i++) {
[5755]69        basisBits[i] = b->loadInputStreamBlock("basisBits", b->getInt32(i));
[5079]70    }
[5246]71    Value * bytePack[8];
[5755]72    p2s(b, basisBits, bytePack);
[5260]73
[6004]74    Value * const fieldCounts = b->loadInputStreamBlock("fieldCounts", b->getInt32(0));
75    Value * unitCounts = partial_sum_popcounts(b, unitsPerRegister, fieldCounts);
[5260]76
[5755]77    Value * output_ptr = b->getOutputStreamBlockPtr("byteStream", b->getInt32(0));
78    output_ptr = b->CreatePointerCast(output_ptr, b->getInt8PtrTy());
79    Value * offset = b->getInt32(0);
[5079]80    for (unsigned j = 0; j < 8; ++j) {
[5755]81        b->CreateStore(bytePack[j], b->CreateBitCast(b->CreateGEP(output_ptr, offset), bitBlockPtrTy));
[6004]82        offset = b->CreateZExt(b->CreateExtractElement(unitCounts, b->getInt32(j)), i32);
[5079]83    }
[5307]84
[5755]85    Value * unitsGenerated = b->getProducedItemCount("byteStream"); // units generated to buffer
86    unitsGenerated = b->CreateAdd(unitsGenerated, b->CreateZExt(offset, b->getSizeTy()));
87    b->setProducedItemCount("byteStream", unitsGenerated);
[5079]88}
[5261]89
[5755]90void P2S16Kernel::generateDoBlockMethod(const std::unique_ptr<KernelBuilder> & b) {
[5006]91    Value * hi_input[8];
92    for (unsigned j = 0; j < 8; ++j) {
[5755]93        hi_input[j] = b->loadInputStreamBlock("basisBits", b->getInt32(j));
[5006]94    }
95    Value * hi_bytes[8];
[5755]96    p2s(b, hi_input, hi_bytes);
[5006]97    Value * lo_input[8];
98    for (unsigned j = 0; j < 8; ++j) {
[5755]99        lo_input[j] = b->loadInputStreamBlock("basisBits", b->getInt32(j + 8));
[5006]100    }
101    Value * lo_bytes[8];
[5755]102    p2s(b, lo_input, lo_bytes);
[5006]103    for (unsigned j = 0; j < 8; ++j) {
[5755]104        Value * merge0 = b->bitCast(b->esimd_mergel(8, hi_bytes[j], lo_bytes[j]));
105        Value * merge1 = b->bitCast(b->esimd_mergeh(8, hi_bytes[j], lo_bytes[j]));
106        b->storeOutputStreamPack("i16Stream", b->getInt32(0), b->getInt32(2 * j), merge0);
107        b->storeOutputStreamPack("i16Stream", b->getInt32(0), b->getInt32(2 * j + 1), merge1);
[5006]108    }
[4987]109}
[6004]110   
[5755]111void P2S16KernelWithCompressedOutput::generateDoBlockMethod(const std::unique_ptr<KernelBuilder> & b) {
112    IntegerType * i32Ty = b->getInt32Ty();
113    PointerType * int16PtrTy = b->getInt16Ty()->getPointerTo();
114    PointerType * bitBlockPtrTy = b->getBitBlockType()->getPointerTo();
115    ConstantInt * blockMask = b->getSize(b->getBitBlockWidth() - 1);
[6004]116    unsigned const unitsPerRegister = b->getBitBlockWidth()/16;
117   
[5009]118    Value * hi_input[8];
119    for (unsigned j = 0; j < 8; ++j) {
[5755]120        hi_input[j] = b->loadInputStreamBlock("basisBits", b->getInt32(j));
[5009]121    }
122    Value * hi_bytes[8];
[5755]123    p2s(b, hi_input, hi_bytes);
[5297]124
[5009]125    Value * lo_input[8];
126    for (unsigned j = 0; j < 8; ++j) {
[5755]127        lo_input[j] = b->loadInputStreamBlock("basisBits", b->getInt32(j + 8));
[5009]128    }
129    Value * lo_bytes[8];
[5755]130    p2s(b, lo_input, lo_bytes);
[5297]131
[6004]132    Value * const fieldCounts = b->loadInputStreamBlock("fieldCounts", b->getInt32(0));
133    Value * unitCounts = partial_sum_popcounts(b, unitsPerRegister, fieldCounts);
134   
[5755]135    Value * outputPtr = b->getOutputStreamBlockPtr("i16Stream", b->getInt32(0));
136    outputPtr = b->CreatePointerCast(outputPtr, int16PtrTy);
137    Value * const i16UnitsGenerated = b->getProducedItemCount("i16Stream"); // units generated to buffer
138    outputPtr = b->CreateGEP(outputPtr, b->CreateAnd(i16UnitsGenerated, blockMask));
[5297]139
[5755]140    Value * offset = b->getInt32(0);
[5297]141
[5009]142    for (unsigned j = 0; j < 8; ++j) {
[5755]143        Value * const merge0 = b->bitCast(b->esimd_mergel(8, hi_bytes[j], lo_bytes[j]));
144        b->CreateAlignedStore(merge0, b->CreateBitCast(b->CreateGEP(outputPtr, offset), bitBlockPtrTy), 1);
145        Value * const nextOffset1 = b->CreateZExt(b->CreateExtractElement(unitCounts, b->getInt32(2 * j)), i32Ty);
[5771]146        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
147            b->CreateAssert(b->CreateICmpULE(offset, nextOffset1), "deletion offset is not monotonically non-decreasing");
148        }
[5755]149        Value * const merge1 = b->bitCast(b->esimd_mergeh(8, hi_bytes[j], lo_bytes[j]));
150        b->CreateAlignedStore(merge1, b->CreateBitCast(b->CreateGEP(outputPtr, nextOffset1), bitBlockPtrTy), 1);
151        Value * const nextOffset2 = b->CreateZExt(b->CreateExtractElement(unitCounts, b->getInt32(2 * j + 1)), i32Ty);
[5771]152        if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
153            b->CreateAssert(b->CreateICmpULE(nextOffset1, nextOffset2), "deletion offset is not monotonically non-decreasing");
154        }
[5755]155        offset = nextOffset2;
[5706]156    }
157
[5755]158    Value * const i16UnitsFinal = b->CreateAdd(i16UnitsGenerated, b->CreateZExt(offset, b->getSizeTy()));
159    b->setProducedItemCount("i16Stream", i16UnitsFinal);
[5006]160}
[5347]161
[5755]162P2SKernel::P2SKernel(const std::unique_ptr<kernel::KernelBuilder> & b)
[5435]163: BlockOrientedKernel("p2s",
[5755]164              {Binding{b->getStreamSetTy(8, 1), "basisBits"}},
165              {Binding{b->getStreamSetTy(1, 8), "byteStream"}},
[5347]166              {}, {}, {}) {
167}
168
[5755]169P2SKernelWithCompressedOutput::P2SKernelWithCompressedOutput(const std::unique_ptr<kernel::KernelBuilder> & b)
[5435]170: BlockOrientedKernel("p2s_compress",
[6004]171              {Binding{b->getStreamSetTy(8, 1), "basisBits"}, Binding{b->getStreamSetTy(1, 1), "fieldCounts"}},
[5755]172              {Binding{b->getStreamSetTy(1, 8), "byteStream", BoundedRate(0, 1)}},
[5347]173              {}, {}, {}) {
174}
175
[5755]176P2S16Kernel::P2S16Kernel(const std::unique_ptr<kernel::KernelBuilder> & b)
[5435]177: BlockOrientedKernel("p2s_16",
[5755]178              {Binding{b->getStreamSetTy(16, 1), "basisBits"}},
179              {Binding{b->getStreamSetTy(1, 16), "i16Stream"}},
[5347]180              {}, {}, {}) {
181}
182
183
[5436]184P2S16KernelWithCompressedOutput::P2S16KernelWithCompressedOutput(const std::unique_ptr<kernel::KernelBuilder> & b)
[5435]185: BlockOrientedKernel("p2s_16_compress",
[6004]186              {Binding{b->getStreamSetTy(16, 1), "basisBits"}, Binding{b->getStreamSetTy(1, 1), "fieldCounts"}},
[5706]187              {Binding{b->getStreamSetTy(1, 16), "i16Stream", BoundedRate(0, 1)}},
[5283]188              {},
189              {},
[5325]190              {}) {
[5347]191
[5109]192}
[5261]193   
194   
195}
Note: See TracBrowser for help on using the repository browser.