source: icGREP/icgrep-devel/icgrep/IR_Gen/idisa_builder.cpp @ 6059

Last change on this file since 6059 was 6059, checked in by xwa163, 12 months ago
  1. Enable swizzled match copy in multiplexing lz4_grep for some special case
  2. Implement some lz4 AIO (all-in-one) pipeline and related kernel
File size: 37.4 KB
Line 
1/*
2 *  Copyright (c) 2016 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#include "idisa_builder.h"
8#include <llvm/IR/IRBuilder.h>
9#include <llvm/IR/Constants.h>
10#include <llvm/IR/Intrinsics.h>
11#include <llvm/IR/Function.h>
12#include <llvm/IR/Module.h>
13#include <llvm/Support/raw_ostream.h>
14#include <llvm/IR/TypeBuilder.h>
15#include <toolchain/toolchain.h>
16
17using namespace llvm;
18
19namespace IDISA {
20
21VectorType * IDISA_Builder::fwVectorType(const unsigned fw) {
22    return VectorType::get(getIntNTy(fw), mBitBlockWidth / fw);
23}
24
25Value * IDISA_Builder::fwCast(const unsigned fw, Value * const a) {
26    VectorType * const ty = fwVectorType(fw);
27    assert (a->getType()->getPrimitiveSizeInBits() == ty->getPrimitiveSizeInBits());
28    return CreateBitCast(a, ty);
29}
30
31void IDISA_Builder::CallPrintRegisterCond(const std::string & regName, llvm::Value * const value, llvm::Value * const cond) {
32    BasicBlock* callBlock = this->CreateBasicBlock("callBlock");
33    BasicBlock* exitBlock = this->CreateBasicBlock("exitBlock");
34    this->CreateCondBr(cond, callBlock, exitBlock);
35
36    this->SetInsertPoint(callBlock);
37    this->CallPrintRegister(regName, value);
38
39    this->CreateBr(exitBlock);
40    this->SetInsertPoint(exitBlock);
41}
42
43void IDISA_Builder::CallPrintRegister(const std::string & name, Value * const value) {
44    Module * const m = getModule();
45    Constant * printRegister = m->getFunction("PrintRegister");
46    if (LLVM_UNLIKELY(printRegister == nullptr)) {
47        FunctionType *FT = FunctionType::get(getVoidTy(), { PointerType::get(getInt8Ty(), 0), getBitBlockType() }, false);
48        Function * function = Function::Create(FT, Function::InternalLinkage, "PrintRegister", m);
49        auto arg = function->arg_begin();
50        std::string tmp;
51        raw_string_ostream out(tmp);
52        out << "%-40s =";
53        for(unsigned i = 0; i < (mBitBlockWidth / 8); ++i) {
54            out << " %02x";
55        }
56        out << '\n';
57        BasicBlock * entry = BasicBlock::Create(m->getContext(), "entry", function);
58        IRBuilder<> builder(entry);
59        std::vector<Value *> args;
60        args.push_back(GetString(out.str().c_str()));
61        Value * const name = &*(arg++);
62        name->setName("name");
63        args.push_back(name);
64        Value * value = &*arg;
65        value->setName("value");
66        Type * const byteVectorType = VectorType::get(getInt8Ty(), (mBitBlockWidth / 8));
67        value = builder.CreateBitCast(value, byteVectorType);
68        for(unsigned i = (mBitBlockWidth / 8); i != 0; --i) {
69            args.push_back(builder.CreateZExt(builder.CreateExtractElement(value, builder.getInt32(i - 1)), builder.getInt32Ty()));
70        }
71        builder.CreateCall(GetPrintf(), args);
72        builder.CreateRetVoid();
73
74        printRegister = function;
75    }
76    CreateCall(printRegister, {GetString(name.c_str()), CreateBitCast(value, mBitBlockType)});
77}
78
79Constant * IDISA_Builder::simd_himask(unsigned fw) {
80    return Constant::getIntegerValue(getIntNTy(mBitBlockWidth), APInt::getSplat(mBitBlockWidth, APInt::getHighBitsSet(fw, fw/2)));
81}
82
83Constant * IDISA_Builder::simd_lomask(unsigned fw) {
84    return Constant::getIntegerValue(getIntNTy(mBitBlockWidth), APInt::getSplat(mBitBlockWidth, APInt::getLowBitsSet(fw, fw/2)));
85}
86
87Value * IDISA_Builder::simd_fill(unsigned fw, Value * a) {
88    if (fw < 8) report_fatal_error("Unsupported field width: simd_fill " + std::to_string(fw));
89    const unsigned field_count = mBitBlockWidth/fw;
90    Type * singleFieldVecTy = VectorType::get(getIntNTy(fw), 1);
91    Value * aVec = CreateBitCast(a, singleFieldVecTy);
92    return CreateShuffleVector(aVec, UndefValue::get(singleFieldVecTy), Constant::getNullValue(VectorType::get(getInt32Ty(), field_count)));
93}
94
95Value * IDISA_Builder::simd_add(unsigned fw, Value * a, Value * b) {
96    if (fw == 1) {
97        return simd_xor(a, b);
98    } else if (fw < 8) {
99        Constant * hi_bit_mask = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
100                                                           APInt::getSplat(mBitBlockWidth, APInt::getHighBitsSet(fw, 1)));
101        Constant * lo_bit_mask = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
102                                                           APInt::getSplat(mBitBlockWidth, APInt::getLowBitsSet(fw, fw-1)));
103        Value * hi_xor = simd_xor(simd_and(a, hi_bit_mask), simd_and(b, hi_bit_mask));
104        Value * part_sum = simd_add(32, simd_and(a, lo_bit_mask), simd_and(b, lo_bit_mask));
105        return simd_xor(part_sum, hi_xor);
106    }
107    return CreateAdd(fwCast(fw, a), fwCast(fw, b));
108}
109
110Value * IDISA_Builder::simd_sub(unsigned fw, Value * a, Value * b) {
111    if (fw < 8) report_fatal_error("Unsupported field width: sub " + std::to_string(fw));
112    return CreateSub(fwCast(fw, a), fwCast(fw, b));
113}
114
115Value * IDISA_Builder::simd_mult(unsigned fw, Value * a, Value * b) {
116    if (fw < 8) report_fatal_error("Unsupported field width: mult " + std::to_string(fw));
117    return CreateMul(fwCast(fw, a), fwCast(fw, b));
118}
119
120Value * IDISA_Builder::simd_eq(unsigned fw, Value * a, Value * b) {
121    if (fw < 8) {
122        Value * eq_bits = simd_not(simd_xor(a, b));
123        if (fw == 1) return eq_bits;
124        eq_bits = simd_or(simd_and(simd_srli(32, simd_and(simd_himask(2), eq_bits), 1), eq_bits),
125                          simd_and(simd_slli(32, simd_and(simd_lomask(2), eq_bits), 1), eq_bits));
126        if (fw == 2) return eq_bits;
127        eq_bits = simd_or(simd_and(simd_srli(32, simd_and(simd_himask(4), eq_bits), 2), eq_bits),
128                          simd_and(simd_slli(32, simd_and(simd_lomask(4), eq_bits), 2), eq_bits));
129        return eq_bits;
130    }
131    return CreateSExt(CreateICmpEQ(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
132}
133
134Value * IDISA_Builder::simd_gt(unsigned fw, Value * a, Value * b) {
135    if (fw < 8) report_fatal_error("Unsupported field width: gt " + std::to_string(fw));
136    return CreateSExt(CreateICmpSGT(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
137}
138
139Value * IDISA_Builder::simd_ugt(unsigned fw, Value * a, Value * b) {
140    if (fw < 8) report_fatal_error("Unsupported field width: ugt " + std::to_string(fw));
141    return CreateSExt(CreateICmpUGT(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
142}
143
144Value * IDISA_Builder::simd_lt(unsigned fw, Value * a, Value * b) {
145    if (fw < 8) report_fatal_error("Unsupported field width: lt " + std::to_string(fw));
146    return CreateSExt(CreateICmpSLT(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
147}
148
149Value * IDISA_Builder::simd_ult(unsigned fw, Value * a, Value * b) {
150    if (fw < 8) report_fatal_error("Unsupported field width: ult " + std::to_string(fw));
151    return CreateSExt(CreateICmpULT(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
152}
153
154Value * IDISA_Builder::simd_ule(unsigned fw, Value * a, Value * b) {
155    if (fw == 1) return simd_or(simd_not(a), b);
156    if (fw < 8) {
157        Value * hi_rslt = simd_and(simd_himask(2*fw), simd_ule(2*fw, simd_and(simd_himask(2*fw), a), b));
158        Value * lo_rslt = simd_and(simd_lomask(2*fw), simd_ule(2*fw, simd_and(simd_lomask(2*fw), a), simd_and(simd_lomask(2*fw), b)));
159        return simd_or(hi_rslt, lo_rslt);
160    }
161    return CreateSExt(CreateICmpULE(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
162}
163
164Value * IDISA_Builder::simd_uge(unsigned fw, Value * a, Value * b) {
165    if (fw == 1) return simd_or(a, simd_not(b));
166    if (fw < 8) {
167        Value * hi_rslt = simd_and(simd_himask(2*fw), simd_uge(2*fw, a, simd_and(simd_himask(2*fw), b)));
168        Value * lo_rslt = simd_and(simd_lomask(2*fw), simd_uge(2*fw, simd_and(simd_lomask(2*fw), a), simd_and(simd_lomask(2*fw), b)));
169        return simd_or(hi_rslt, lo_rslt);
170    }
171    if (fw < 8) report_fatal_error("Unsupported field width: ult " + std::to_string(fw));
172    return CreateSExt(CreateICmpUGE(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
173}
174
175Value * IDISA_Builder::simd_max(unsigned fw, Value * a, Value * b) {
176    if (fw < 8) report_fatal_error("Unsupported field width: max " + std::to_string(fw));
177    Value * aVec = fwCast(fw, a);
178    Value * bVec = fwCast(fw, b);
179    return CreateSelect(CreateICmpSGT(aVec, bVec), aVec, bVec);
180}
181
182Value * IDISA_Builder::simd_umax(unsigned fw, Value * a, Value * b) {
183    if (fw == 1) return simd_or(a, b);
184    if (fw < 8) {
185        Value * hi_rslt = simd_and(simd_himask(2*fw), simd_umax(2*fw, a, b));
186        Value * lo_rslt = simd_umax(2*fw, simd_and(simd_lomask(2*fw), a), simd_and(simd_lomask(2*fw), b));
187        return simd_or(hi_rslt, lo_rslt);
188    }
189    Value * aVec = fwCast(fw, a);
190    Value * bVec = fwCast(fw, b);
191    return CreateSelect(CreateICmpUGT(aVec, bVec), aVec, bVec);
192}
193
194Value * IDISA_Builder::simd_min(unsigned fw, Value * a, Value * b) {
195    if (fw < 8) report_fatal_error("Unsupported field width: min " + std::to_string(fw));
196    Value * aVec = fwCast(fw, a);
197    Value * bVec = fwCast(fw, b);
198    return CreateSelect(CreateICmpSLT(aVec, bVec), aVec, bVec);
199}
200
201Value * IDISA_Builder::simd_umin(unsigned fw, Value * a, Value * b) {
202    if (fw == 1) return simd_and(a, b);
203    if (fw < 8) {
204        Value * hi_rslt = simd_and(simd_himask(2*fw), simd_umin(2*fw, a, b));
205        Value * lo_rslt = simd_umin(2*fw, simd_and(simd_lomask(2*fw), a), simd_and(simd_lomask(2*fw), b));
206        return simd_or(hi_rslt, lo_rslt);
207    }
208    Value * aVec = fwCast(fw, a);
209    Value * bVec = fwCast(fw, b);
210    return CreateSelect(CreateICmpULT(aVec, bVec), aVec, bVec);
211}
212
213Value * IDISA_Builder::mvmd_sll(unsigned fw, Value * value, Value * shift) {
214    VectorType * const vecTy = cast<VectorType>(value->getType());
215    IntegerType * const intTy = getIntNTy(vecTy->getBitWidth());
216    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
217        Type * const ty = shift->getType();
218        Value * const scaled = CreateMul(shift, ConstantInt::get(ty, fw));
219        Value * const inbounds = CreateICmpULE(scaled, ConstantInt::get(ty, vecTy->getBitWidth()));
220        CreateAssert(inbounds, "shift exceeds vector width");
221    }
222    value = CreateBitCast(value, intTy);
223    shift = CreateZExtOrTrunc(CreateMul(shift, ConstantInt::get(shift->getType(), fw)), intTy);
224    return CreateBitCast(CreateShl(value, shift), vecTy);
225}
226
227Value * IDISA_Builder::mvmd_dsll(unsigned fw, Value * a, Value * b, Value * shift) {
228    if (fw < 8) report_fatal_error("Unsupported field width: mvmd_dsll " + std::to_string(fw));
229    const auto field_count = mBitBlockWidth/fw;
230    Type * fwTy = getIntNTy(fw);
231   
232    Constant * Idxs[field_count];
233    for (unsigned i = 0; i < field_count; i++) {
234        Idxs[i] = ConstantInt::get(fwTy, i + field_count);
235    }
236    Value * shuffle = simd_sub(fw, ConstantVector::get({Idxs, field_count}), simd_fill(fw, shift));
237    Value * rslt = mvmd_shuffle2(fw, fwCast(fw, a), fwCast(fw, b), shuffle);
238    return rslt;
239}
240
241Value * IDISA_Builder::mvmd_srl(unsigned fw, Value * value, Value * shift) {
242    VectorType * const vecTy = cast<VectorType>(value->getType());
243    IntegerType * const intTy = getIntNTy(vecTy->getBitWidth());
244    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
245        Type * const ty = shift->getType();
246        Value * const scaled = CreateMul(shift, ConstantInt::get(ty, fw));
247        Value * const inbounds = CreateICmpULE(scaled, ConstantInt::get(ty, vecTy->getBitWidth()));
248        CreateAssert(inbounds, "shift exceeds vector width");
249    }
250    value = CreateBitCast(value, intTy);
251    shift = CreateZExtOrTrunc(CreateMul(shift, ConstantInt::get(shift->getType(), fw)), intTy);
252    return CreateBitCast(CreateLShr(value, shift), vecTy);
253}
254
255Value * IDISA_Builder::simd_slli(unsigned fw, Value * a, unsigned shift) {
256    if (fw < 16) {
257        Constant * value_mask = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
258                                                          APInt::getSplat(mBitBlockWidth, APInt::getLowBitsSet(fw, fw-shift)));
259        return CreateShl(fwCast(32, simd_and(a, value_mask)), shift);
260    }
261    return CreateShl(fwCast(fw, a), shift);
262}
263
264Value * IDISA_Builder::simd_srli(unsigned fw, Value * a, unsigned shift) {
265    if (fw < 16) {
266        Constant * value_mask = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
267                                                          APInt::getSplat(mBitBlockWidth, APInt::getHighBitsSet(fw, fw-shift)));
268        return CreateLShr(fwCast(32, simd_and(a, value_mask)), shift);
269    }
270    return CreateLShr(fwCast(fw, a), shift);
271}
272
273Value * IDISA_Builder::simd_srai(unsigned fw, Value * a, unsigned shift) {
274    if (fw < 8) report_fatal_error("Unsupported field width: srai " + std::to_string(fw));
275    return CreateAShr(fwCast(fw, a), shift);
276}
277   
278Value * IDISA_Builder::simd_sllv(unsigned fw, Value * v, Value * shifts) {
279    if (fw >= 8) return CreateShl(fwCast(fw, v), fwCast(fw, shifts));
280    Value * w = v;
281    for (unsigned shft_amt = 1; shft_amt < fw; shft_amt *= 2) {
282        APInt bit_in_field(fw, shft_amt);
283        // To simulate shift within a fw, we need to mask off the high shft_amt bits of each element.
284        Constant * value_mask = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
285                                                          APInt::getSplat(mBitBlockWidth, APInt::getLowBitsSet(fw, fw-shft_amt)));
286        Constant * bit_select = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
287                                                          APInt::getSplat(mBitBlockWidth, bit_in_field));
288        Value * unshifted_field_mask = simd_eq(fw, simd_and(bit_select, shifts), allZeroes());
289        Value * fieldsToShift = simd_and(w, simd_and(value_mask, simd_not(unshifted_field_mask)));
290        w = simd_or(simd_and(w, unshifted_field_mask), simd_slli(32, fieldsToShift, shft_amt));
291    }
292    return w;
293}
294
295Value * IDISA_Builder::simd_srlv(unsigned fw, Value * v, Value * shifts) {
296    if (fw >= 8) return CreateLShr(fwCast(fw, v), fwCast(fw, shifts));
297    Value * w = v;
298    for (unsigned shft_amt = 1; shft_amt < fw; shft_amt *= 2) {
299        APInt bit_in_field(fw, shft_amt);
300        // To simulate shift within a fw, we need to mask off the low shft_amt bits of each element.
301        Constant * value_mask = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
302                                                          APInt::getSplat(mBitBlockWidth, APInt::getHighBitsSet(fw, fw-shft_amt)));
303        Constant * bit_select = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
304                                                          APInt::getSplat(mBitBlockWidth, bit_in_field));
305        Value * unshifted_field_mask = simd_eq(fw, simd_and(bit_select, shifts), allZeroes());
306        Value * fieldsToShift = simd_and(w, simd_and(value_mask, simd_not(unshifted_field_mask)));
307        w = simd_or(simd_and(w, unshifted_field_mask), simd_srli(32, fieldsToShift, shft_amt));
308    }
309    return w;
310}
311
312Value * IDISA_Builder::simd_pext(unsigned fieldwidth, Value * v, Value * extract_mask) {
313    Value * delcounts = CreateNot(extract_mask);  // initially deletion counts per 1-bit field
314    Value * w = simd_and(extract_mask, v);
315    for (unsigned fw = 2; fw < fieldwidth; fw = fw * 2) {
316        Value * shift_fwd_field_mask = simd_lomask(fw*2);
317        Value * shift_back_field_mask = simd_himask(fw*2);
318        Value * shift_back_count_mask = simd_and(shift_back_field_mask, simd_lomask(fw));
319        Value * shift_fwd_amts = simd_srli(fw, simd_and(shift_fwd_field_mask, delcounts), fw/2);
320        Value * shift_back_amts = simd_and(shift_back_count_mask, delcounts);
321        w = simd_or(simd_sllv(fw, simd_and(w, shift_fwd_field_mask), shift_fwd_amts),
322                    simd_srlv(fw, simd_and(w, shift_back_field_mask), shift_back_amts));
323        delcounts = simd_add(fw, simd_and(simd_lomask(fw), delcounts), simd_srli(fw, delcounts, fw/2));
324    }
325    // Now shift back all fw fields.
326    Value * shift_back_amts = simd_and(simd_lomask(fieldwidth), delcounts);
327    w = simd_srlv(fieldwidth, w, shift_back_amts);
328    return w;
329}
330
331Value * IDISA_Builder::simd_pdep(unsigned fieldwidth, Value * v, Value * deposit_mask) {
332    // simd_pdep is implemented by reversing the process of simd_pext.
333    // First determine the deletion counts necessary for each stage of the process.
334    std::vector<Value *> delcounts;
335    delcounts.push_back(simd_not(deposit_mask)); // initially deletion counts per 1-bit field
336    for (unsigned fw = 2; fw < fieldwidth; fw = fw * 2) {
337        delcounts.push_back(simd_add(fw, simd_and(simd_lomask(fw), delcounts.back()), simd_srli(fw, delcounts.back(), fw/2)));
338    }
339    //
340    // Now reverse the pext process.  First reverse the final shift_back.
341    Value * pext_shift_back_amts = simd_and(simd_lomask(fieldwidth), delcounts.back());
342    Value * w = simd_sllv(fieldwidth, v, pext_shift_back_amts);
343    //
344    // No work through the smaller field widths.
345    for (unsigned fw = fieldwidth/2; fw >= 2; fw = fw/2) {
346        delcounts.pop_back();
347        Value * pext_shift_fwd_field_mask = simd_lomask(fw*2);
348        Value * pext_shift_back_field_mask = simd_himask(fw*2);
349        Value * pext_shift_back_count_mask = simd_and(pext_shift_back_field_mask, simd_lomask(fw));
350        Value * pext_shift_fwd_amts = simd_srli(fw, simd_and(pext_shift_fwd_field_mask, delcounts.back()), fw/2);
351        Value * pext_shift_back_amts = simd_and(pext_shift_back_count_mask, delcounts.back());
352        w = simd_or(simd_srlv(fw, simd_and(w, pext_shift_fwd_field_mask), pext_shift_fwd_amts),
353                    simd_sllv(fw, simd_and(w, pext_shift_back_field_mask), pext_shift_back_amts));
354    }
355    return CreateAnd(w, deposit_mask);
356}
357
358Value * IDISA_Builder::simd_popcount(unsigned fw, Value * a) {
359    if (fw == 1) {
360        return a;
361    } else if (fw == 2) {
362        // For each 2-bit field ab we can use the subtraction ab - 0a to generate
363        // the popcount without carry/borrow from the neighbouring 2-bit field.
364        // case 00:  ab - 0a = 00 - 00 = 00
365        // case 01:  ab - 0a = 01 - 00 = 01
366        // case 10:  ab - 0a = 10 - 01 = 01 (no borrow)
367        // case 11:  ab - 0a = 11 - 01 = 10
368        return simd_sub(64, a, simd_srli(64, simd_and(simd_himask(2), a), 1));
369    } else if (fw <= 8) {
370        Value * c = simd_popcount(fw/2, a);
371        c = simd_add(64, simd_and(c, simd_lomask(fw)), simd_srli(fw, c, fw/2));
372        return c;
373    } else {
374        return CreatePopcount(fwCast(fw, a));
375    }
376}
377
378Value * IDISA_Builder::simd_bitreverse(unsigned fw, Value * a) {
379    /*  Pure sequential solution too slow!
380     Value * func = Intrinsic::getDeclaration(getModule(), Intrinsic::bitreverse, fwVectorType(fw));
381     return CreateCall(func, fwCast(fw, a));
382     */
383    if (fw > 8) {
384        // Reverse the bits of each byte and then use a byte shuffle to complete the job.
385        Value * bitrev8 = fwCast(8, simd_bitreverse(8, a));
386        const auto bytes_per_field = fw/8;
387        const auto byte_count = mBitBlockWidth / 8;
388        Constant * Idxs[byte_count];
389        for (unsigned i = 0; i < byte_count; i += bytes_per_field) {
390            for (unsigned j = 0; j < bytes_per_field; j++) {
391                Idxs[i + j] = getInt32(i + bytes_per_field - j - 1);
392            }
393        }
394        return CreateShuffleVector(bitrev8, UndefValue::get(fwVectorType(8)), ConstantVector::get({Idxs, byte_count}));
395    }
396    else {
397        if (fw > 2) {
398            a = simd_bitreverse(fw/2, a);
399        }
400        return simd_or(simd_srli(16, simd_and(a, simd_himask(fw)), fw/2), simd_slli(16, simd_and(a, simd_lomask(fw)), fw/2));
401    }
402}
403
404Value * IDISA_Builder::simd_if(unsigned fw, Value * cond, Value * a, Value * b) {
405    if (fw == 1) {
406        Value * a1 = bitCast(a);
407        Value * b1 = bitCast(b);
408        Value * c = bitCast(cond);
409        return CreateOr(CreateAnd(a1, c), CreateAnd(CreateXor(c, b1), b1));
410    } else {
411        if (fw < 8) report_fatal_error("Unsupported field width: simd_if " + std::to_string(fw));
412        Value * aVec = fwCast(fw, a);
413        Value * bVec = fwCast(fw, b);
414        return CreateSelect(CreateICmpSLT(cond, mZeroInitializer), aVec, bVec);
415    }
416}
417   
418Value * IDISA_Builder::esimd_mergeh(unsigned fw, Value * a, Value * b) {   
419    if (fw == 4) {
420        Value * abh = simd_or(simd_and(simd_himask(fw*2), b), simd_srli(32, simd_and(simd_himask(fw*2), a), fw));
421        Value * abl = simd_or(simd_slli(32, simd_and(simd_lomask(fw*2), b), fw), simd_and(simd_lomask(fw*2), a));
422        return esimd_mergeh(fw * 2, abl, abh);
423    }
424    if (fw < 4) report_fatal_error("Unsupported field width: mergeh " + std::to_string(fw));
425    const auto field_count = mBitBlockWidth / fw;
426    Constant * Idxs[field_count];
427    for (unsigned i = 0; i < field_count / 2; i++) {
428        Idxs[2 * i] = getInt32(i + field_count / 2); // selects elements from first reg.
429        Idxs[2 * i + 1] = getInt32(i + field_count / 2 + field_count); // selects elements from second reg.
430    }
431    return CreateShuffleVector(fwCast(fw, a), fwCast(fw, b), ConstantVector::get({Idxs, field_count}));
432}
433
434Value * IDISA_Builder::esimd_mergel(unsigned fw, Value * a, Value * b) {
435    if (fw == 4) {
436        Value * abh = simd_or(simd_and(simd_himask(fw*2), b), simd_srli(32, simd_and(simd_himask(fw*2), a), fw));
437        Value * abl = simd_or(simd_slli(32, simd_and(simd_lomask(fw*2), b), fw), simd_and(simd_lomask(fw*2), a));
438        return esimd_mergel(fw * 2, abl, abh);
439    }
440    if (fw < 4) report_fatal_error("Unsupported field width: mergel " + std::to_string(fw));
441    const auto field_count = mBitBlockWidth / fw;
442    Constant * Idxs[field_count];
443    for (unsigned i = 0; i < field_count / 2; i++) {
444        Idxs[2 * i] = getInt32(i); // selects elements from first reg.
445        Idxs[2 * i + 1] = getInt32(i + field_count); // selects elements from second reg.
446    }
447    return CreateShuffleVector(fwCast(fw, a), fwCast(fw, b), ConstantVector::get({Idxs, field_count}));
448}
449
450Value * IDISA_Builder::esimd_bitspread(unsigned fw, Value * bitmask) {
451    if (fw < 8) report_fatal_error("Unsupported field width: bitspread " + std::to_string(fw));
452    const auto field_count = mBitBlockWidth / fw;
453    Type * field_type = getIntNTy(fw);
454    Value * spread_field = CreateBitCast(CreateZExtOrTrunc(bitmask, field_type), VectorType::get(getIntNTy(fw), 1));
455    Value * undefVec = UndefValue::get(VectorType::get(getIntNTy(fw), 1));
456    Value * broadcast = CreateShuffleVector(spread_field, undefVec, Constant::getNullValue(VectorType::get(getInt32Ty(), field_count)));
457    Constant * bitSel[field_count];
458    Constant * bitShift[field_count];
459    for (unsigned i = 0; i < field_count; i++) {
460        bitSel[i] = ConstantInt::get(field_type, 1 << i);
461        bitShift[i] = ConstantInt::get(field_type, i);
462    }
463    Value * bitSelVec = ConstantVector::get({bitSel, field_count});
464    Value * bitShiftVec = ConstantVector::get({bitShift, field_count});
465    return CreateLShr(CreateAnd(bitSelVec, broadcast), bitShiftVec);
466}
467
468Value * IDISA_Builder::hsimd_packh(unsigned fw, Value * a, Value * b) {
469    if (fw <= 8) {
470        const unsigned fw_wkg = 32;
471        Value * aLo = simd_srli(fw_wkg, a, fw/2);
472        Value * bLo = simd_srli(fw_wkg, b, fw/2);
473        return hsimd_packl(fw, aLo, bLo);
474    }
475    Value * aVec = fwCast(fw/2, a);
476    Value * bVec = fwCast(fw/2, b);
477    const auto field_count = 2 * mBitBlockWidth / fw;
478    Constant * Idxs[field_count];
479    for (unsigned i = 0; i < field_count; i++) {
480        Idxs[i] = getInt32(2 * i + 1);
481    }
482    return CreateShuffleVector(aVec, bVec, ConstantVector::get({Idxs, field_count}));
483}
484
485Value * IDISA_Builder::hsimd_packl(unsigned fw, Value * a, Value * b) {
486    if (fw <= 8) {
487        const unsigned fw_wkg = 32;
488        Value * aLo = simd_srli(fw_wkg, a, fw/2);
489        Value * bLo = simd_srli(fw_wkg, b, fw/2);
490        return hsimd_packl(fw*2,
491                           bitCast(simd_or(simd_and(simd_himask(fw), aLo), simd_and(simd_lomask(fw), a))),
492                           bitCast(simd_or(simd_and(simd_himask(fw), bLo), simd_and(simd_lomask(fw), b))));
493    }
494    Value * aVec = fwCast(fw/2, a);
495    Value * bVec = fwCast(fw/2, b);
496    const auto field_count = 2 * mBitBlockWidth / fw;
497    Constant * Idxs[field_count];
498    for (unsigned i = 0; i < field_count; i++) {
499        Idxs[i] = getInt32(2 * i);
500    }
501    return CreateShuffleVector(aVec, bVec, ConstantVector::get({Idxs, field_count}));
502}
503
504Value * IDISA_Builder::hsimd_packh_in_lanes(unsigned lanes, unsigned fw, Value * a, Value * b) {
505    if (fw < 16) report_fatal_error("Unsupported field width: packh_in_lanes " + std::to_string(fw));
506    const unsigned fw_out = fw / 2;
507    const unsigned fields_per_lane = mBitBlockWidth / (fw_out * lanes);
508    const unsigned field_offset_for_b = mBitBlockWidth / fw_out;
509    const unsigned field_count = mBitBlockWidth / fw_out;
510    Constant * Idxs[field_count];
511    for (unsigned lane = 0, j = 0; lane < lanes; lane++) {
512        const unsigned first_field_in_lane = lane * fields_per_lane; // every second field
513        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
514            Idxs[j++] = getInt32(first_field_in_lane + (2 * i) + 1);
515        }
516        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
517            Idxs[j++] = getInt32(field_offset_for_b + first_field_in_lane + (2 * i) + 1);
518        }
519    }
520    return CreateShuffleVector(fwCast(fw_out, a), fwCast(fw_out, b), ConstantVector::get({Idxs, field_count}));
521}
522
523Value * IDISA_Builder::hsimd_packl_in_lanes(unsigned lanes, unsigned fw, Value * a, Value * b) {
524    if (fw < 16) report_fatal_error("Unsupported field width: packl_in_lanes " + std::to_string(fw));
525    const unsigned fw_out = fw / 2;
526    const unsigned fields_per_lane = mBitBlockWidth / (fw_out * lanes);
527    const unsigned field_offset_for_b = mBitBlockWidth / fw_out;
528    const unsigned field_count = mBitBlockWidth / fw_out;
529    Constant * Idxs[field_count];
530    for (unsigned lane = 0, j = 0; lane < lanes; lane++) {
531        const unsigned first_field_in_lane = lane * fields_per_lane; // every second field
532        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
533            Idxs[j++] = getInt32(first_field_in_lane + (2 * i));
534        }
535        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
536            Idxs[j++] = getInt32(field_offset_for_b + first_field_in_lane + (2 * i));
537        }
538    }
539    return CreateShuffleVector(fwCast(fw_out, a), fwCast(fw_out, b), ConstantVector::get({Idxs, field_count}));
540}
541
542Value * IDISA_Builder::hsimd_signmask(unsigned fw, Value * a) {
543    if (fw < 8) report_fatal_error("Unsupported field width: hsimd_signmask " + std::to_string(fw));
544    Value * mask = CreateICmpSLT(fwCast(fw, a), ConstantAggregateZero::get(fwVectorType(fw)));
545    mask = CreateBitCast(mask, getIntNTy(mBitBlockWidth/fw));
546    if (mBitBlockWidth/fw < 32) return CreateZExt(mask, getInt32Ty());
547    else return mask;
548}
549
550Value * IDISA_Builder::mvmd_extract(unsigned fw, Value * a, unsigned fieldIndex) {
551    if (fw < 8) {
552        unsigned byte_no = (fieldIndex * fw) / 8;
553        unsigned intrabyte_shift = (fieldIndex * fw) % 8;
554        Value * byte = CreateExtractElement(fwCast(8, a), getInt32(byte_no));
555        return CreateTrunc(CreateLShr(byte, getInt8(intrabyte_shift)), getIntNTy(fw));
556    }
557    return CreateExtractElement(fwCast(fw, a), getInt32(fieldIndex));
558}
559
560Value * IDISA_Builder::mvmd_insert(unsigned fw, Value * a, Value * elt, unsigned fieldIndex) {
561    if (fw < 8) {
562        unsigned byte_no = (fieldIndex * fw) / 8;
563        unsigned intrabyte_shift = (fieldIndex * fw) % 8;
564        unsigned field_mask = ((1 << fw) - 1) << intrabyte_shift;
565        Value * byte = CreateAnd(CreateExtractElement(fwCast(8, a), getInt32(byte_no)), getInt8(0xFF &~ field_mask));
566        byte = CreateOr(byte, CreateShl(CreateZExtOrTrunc(elt, getInt8Ty()), getInt8(intrabyte_shift)));
567        return CreateInsertElement(fwCast(8, a), byte, getInt32(byte_no));
568    }
569    return CreateInsertElement(fwCast(fw, a), elt, getInt32(fieldIndex));
570}
571
572Value * IDISA_Builder::mvmd_slli(unsigned fw, Value * a, unsigned shift) {
573    if (fw < 8) report_fatal_error("Unsupported field width: mvmd_slli " + std::to_string(fw));
574    Value * shifted = mvmd_dslli(fw, a, Constant::getNullValue(fwVectorType(fw)), shift);
575    return shifted;
576}
577
578Value * IDISA_Builder::mvmd_srli(unsigned fw, Value * a, unsigned shift) {
579    if (fw < 8) report_fatal_error("Unsupported field width: mvmd_srli " + std::to_string(fw));
580    const auto field_count = mBitBlockWidth / fw;
581    return mvmd_dslli(fw, Constant::getNullValue(fwVectorType(fw)), a, field_count - shift);
582}
583
584Value * IDISA_Builder::mvmd_dslli(unsigned fw, Value * a, Value * b, unsigned shift) {
585    if (fw < 8) report_fatal_error("Unsupported field width: mvmd_dslli " + std::to_string(fw));
586    const auto field_count = mBitBlockWidth/fw;
587    Constant * Idxs[field_count];
588    for (unsigned i = 0; i < field_count; i++) {
589        Idxs[i] = getInt32(i + field_count - shift);
590    }
591    return CreateShuffleVector(fwCast(fw, b), fwCast(fw, a), ConstantVector::get({Idxs, field_count}));
592}
593
594Value * IDISA_Builder::mvmd_shuffle(unsigned fw, Value * a, Value * shuffle_table) {
595    report_fatal_error("Unsupported field width: mvmd_shuffle " + std::to_string(fw));
596}
597   
598Value * IDISA_Builder::mvmd_shuffle2(unsigned fw, Value * a, Value *b, Value * shuffle_table) {
599    //  Use two shuffles, with selection by the bit value within the shuffle_table.
600    const auto field_count = mBitBlockWidth/fw;
601    Constant * selectorSplat = ConstantVector::getSplat(field_count, ConstantInt::get(getIntNTy(fw), field_count));
602    Value * selectMask = simd_eq(fw, simd_and(shuffle_table, selectorSplat), selectorSplat);
603    Value * tbl = simd_and(shuffle_table, simd_not(selectorSplat));
604    Value * rslt= simd_or(simd_and(mvmd_shuffle(fw, a, tbl), simd_not(selectMask)), simd_and(mvmd_shuffle(fw, b, tbl), selectMask));
605    return rslt;
606}
607   
608
609llvm::Value * IDISA_Builder::mvmd_compress(unsigned fw, llvm::Value * a, llvm::Value * select_mask) {
610    report_fatal_error("Unsupported field width: mvmd_compress " + std::to_string(fw));
611}
612
613Value * IDISA_Builder::bitblock_any(Value * a) {
614    Type * iBitBlock = getIntNTy(mBitBlockWidth);
615    return CreateICmpNE(CreateBitCast(a, iBitBlock),  ConstantInt::getNullValue(iBitBlock));
616}
617
618// full add producing {carryout, sum}
619std::pair<Value *, Value *> IDISA_Builder::bitblock_add_with_carry(Value * a, Value * b, Value * carryin) {
620    Value * carrygen = simd_and(a, b);
621    Value * carryprop = simd_or(a, b);
622    Value * sum = simd_add(mBitBlockWidth, simd_add(mBitBlockWidth, a, b), carryin);
623    Value * carryout = CreateBitCast(simd_or(carrygen, simd_and(carryprop, CreateNot(sum))), getIntNTy(mBitBlockWidth));
624    return std::pair<Value *, Value *>(bitCast(simd_srli(mBitBlockWidth, carryout, mBitBlockWidth - 1)), bitCast(sum));
625}
626
627// full shift producing {shiftout, shifted}
628std::pair<Value *, Value *> IDISA_Builder::bitblock_advance(Value * a, Value * shiftin, unsigned shift) {
629    Value * shiftin_bitblock = CreateBitCast(shiftin, getIntNTy(mBitBlockWidth));
630    Value * a_bitblock = CreateBitCast(a, getIntNTy(mBitBlockWidth));
631    Value * shifted = bitCast(CreateOr(CreateShl(a_bitblock, shift), shiftin_bitblock));
632    Value * shiftout = bitCast(CreateLShr(a_bitblock, mBitBlockWidth - shift));
633    return std::pair<Value *, Value *>(shiftout, shifted);
634}
635
636// full shift producing {shiftout, shifted}
637std::pair<Value *, Value *> IDISA_Builder::bitblock_indexed_advance(Value * strm, Value * index_strm, Value * shiftIn, unsigned shiftAmount) {
638    const unsigned bitWidth = getSizeTy()->getBitWidth();
639    Type * const iBitBlock = getIntNTy(getBitBlockWidth());
640    Value * const shiftVal = getSize(shiftAmount);
641    Value * extracted_bits = simd_pext(bitWidth, strm, index_strm);
642    Value * ix_popcounts = simd_popcount(bitWidth, index_strm);
643    const auto n = getBitBlockWidth() / bitWidth;
644    VectorType * const vecTy = VectorType::get(getSizeTy(), n);
645    if (LLVM_LIKELY(shiftAmount < bitWidth)) {
646        Value * carry = mvmd_extract(bitWidth, shiftIn, 0);
647        Value * result = UndefValue::get(vecTy);
648        for (unsigned i = 0; i < n; i++) {
649            Value * ix_popcnt = mvmd_extract(bitWidth, ix_popcounts, i);
650            Value * bits = mvmd_extract(bitWidth, extracted_bits, i);
651            Value * adv = CreateOr(CreateShl(bits, shiftAmount), carry);
652            // We have two cases depending on whether the popcount of the index pack is < shiftAmount or not.
653            Value * popcount_small = CreateICmpULT(ix_popcnt, shiftVal);
654            Value * carry_if_popcount_small =
655                CreateOr(CreateShl(bits, CreateSub(shiftVal, ix_popcnt)),
656                            CreateLShr(carry, ix_popcnt));
657            Value * carry_if_popcount_large = CreateLShr(bits, CreateSub(ix_popcnt, shiftVal));
658            carry = CreateSelect(popcount_small, carry_if_popcount_small, carry_if_popcount_large);
659            result = mvmd_insert(bitWidth, result, adv, i);
660        }
661        Value * carryOut = mvmd_insert(bitWidth, allZeroes(), carry, 0);
662        return std::pair<Value *, Value *>{bitCast(carryOut), simd_pdep(bitWidth, result, index_strm)};
663    }
664    else if (shiftAmount <= mBitBlockWidth) {
665        // The shift amount is always greater than the popcount of the individual
666        // elements that we deal with.   This simplifies some of the logic.
667        Value * carry = CreateBitCast(shiftIn, iBitBlock);
668        Value * result = UndefValue::get(vecTy);
669        for (unsigned i = 0; i < n; i++) {
670            Value * ix_popcnt = mvmd_extract(bitWidth, ix_popcounts, i);
671            Value * bits = mvmd_extract(bitWidth, extracted_bits, i);  // All these bits are shifted out (appended to carry).
672            result = mvmd_insert(bitWidth, result, mvmd_extract(bitWidth, carry, 0), i);
673            carry = CreateLShr(carry, CreateZExt(ix_popcnt, iBitBlock)); // Remove the carry bits consumed, make room for new bits.
674            carry = CreateOr(carry, CreateShl(CreateZExt(bits, iBitBlock), CreateZExt(CreateSub(shiftVal, ix_popcnt), iBitBlock)));
675        }
676        return std::pair<Value *, Value *>{bitCast(carry), simd_pdep(bitWidth, result, index_strm)};
677    }
678    else {
679        // The shift amount is greater than the total popcount.   We will consume popcount
680        // bits from the shiftIn value only, and produce a carry out value of the selected bits.
681        Value * carry = CreateBitCast(shiftIn, iBitBlock);
682        Value * result = UndefValue::get(vecTy);
683        Value * carryOut = ConstantInt::getNullValue(iBitBlock);
684        Value * generated = getSize(0);
685        for (unsigned i = 0; i < n; i++) {
686            Value * ix_popcnt = mvmd_extract(bitWidth, ix_popcounts, i);
687            Value * bits = mvmd_extract(bitWidth, extracted_bits, i);  // All these bits are shifted out (appended to carry).
688            result = mvmd_insert(bitWidth, result, mvmd_extract(bitWidth, carry, 0), i);
689            carry = CreateLShr(carry, CreateZExt(ix_popcnt, iBitBlock)); // Remove the carry bits consumed.
690            carryOut = CreateOr(carryOut, CreateShl(CreateZExt(bits, iBitBlock), CreateZExt(generated, iBitBlock)));
691            generated = CreateAdd(generated, ix_popcnt);
692        }
693        return std::pair<Value *, Value *>{bitCast(carryOut), simd_pdep(bitWidth, result, index_strm)};
694    }
695}
696
697
698Value * IDISA_Builder::bitblock_mask_from(Value * pos) {
699    Value * p = CreateZExtOrTrunc(pos, getSizeTy());
700    const unsigned fw = getSizeTy()->getBitWidth();
701    const auto field_count = mBitBlockWidth / fw;
702    Constant * fwVal = ConstantInt::get(getSizeTy(), fw);
703    Constant * poaBase[field_count];
704    for (unsigned i = 0; i < field_count; i++) {
705        poaBase[i] = ConstantInt::get(getSizeTy(), fw * i);
706    }
707    Value * posBaseVec = ConstantVector::get({poaBase, field_count});
708    Value * mask1 = CreateSExt(CreateICmpUGT(posBaseVec, simd_fill(fw, pos)), fwVectorType(fw));
709    Value * bitField = CreateShl(ConstantInt::getAllOnesValue(getSizeTy()), CreateURem(p, fwVal));
710    Value * inBitBlock = CreateICmpULT(p, getSize(mBitBlockWidth));
711    Value * fieldNo = CreateUDiv(p, fwVal);
712    Value * const final_mask = CreateSelect(inBitBlock, CreateInsertElement(mask1, bitField, fieldNo), mask1);
713    return bitCast(final_mask);
714}
715
716Value * IDISA_Builder::bitblock_set_bit(Value * pos) {
717    Value * p = CreateZExtOrTrunc(pos, getSizeTy());
718    const unsigned fw = getSizeTy()->getBitWidth();
719    Constant * fwVal = ConstantInt::get(getSizeTy(), fw);
720    Value * bitField = CreateShl(ConstantInt::get(getSizeTy(), 1), CreateURem(p, fwVal));
721    Value * fieldNo = CreateUDiv(p, fwVal);
722    return bitCast(CreateInsertElement(Constant::getNullValue(fwVectorType(fw)), bitField, fieldNo));
723}
724
725Value * IDISA_Builder::bitblock_popcount(Value * const to_count) {
726    const auto fieldWidth = getSizeTy()->getBitWidth();
727    auto fields = (getBitBlockWidth() / fieldWidth);
728    Value * fieldCounts = simd_popcount(fieldWidth, to_count);
729    while (fields > 1) {
730        fields /= 2;
731        fieldCounts = CreateAdd(fieldCounts, mvmd_srli(fieldWidth, fieldCounts, fields));
732    }
733    return mvmd_extract(fieldWidth, fieldCounts, 0);
734}
735
736Value * IDISA_Builder::simd_and(Value * a, Value * b) {
737    return a->getType() == b->getType() ? CreateAnd(a, b) : CreateAnd(bitCast(a), bitCast(b));
738}
739
740Value * IDISA_Builder::simd_or(Value * a, Value * b) {
741    return a->getType() == b->getType() ? CreateOr(a, b) : CreateOr(bitCast(a), bitCast(b));
742}
743   
744Value * IDISA_Builder::simd_xor(Value * a, Value * b) {
745    return a->getType() == b->getType() ? CreateXor(a, b) : CreateXor(bitCast(a), bitCast(b));
746}
747
748Value * IDISA_Builder::simd_not(Value * a) {
749    return simd_xor(a, Constant::getAllOnesValue(a->getType()));
750}
751
752IDISA_Builder::IDISA_Builder(LLVMContext & C, unsigned vectorWidth, unsigned stride)
753: CBuilder(C)
754, mBitBlockWidth(vectorWidth)
755, mStride(stride)
756, mBitBlockType(VectorType::get(IntegerType::get(C, 64), vectorWidth / 64))
757, mZeroInitializer(Constant::getNullValue(mBitBlockType))
758, mOneInitializer(Constant::getAllOnesValue(mBitBlockType))
759, mPrintRegisterFunction(nullptr) {
760
761}
762
763IDISA_Builder::~IDISA_Builder() {
764
765}
766
767}
Note: See TracBrowser for help on using the repository browser.