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

Last change on this file was 6295, checked in by cameron, 4 months ago

Merge branch 'feat-simd-ternary' into 'master'

Implementing both simd_binary and simd_ternary operations

See merge request cameron/parabix-devel!1

File size: 46.6 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#include <unistd.h>
17
18using namespace llvm;
19
20namespace IDISA {
21
22unsigned getVectorBitWidth(Value * a) {
23    Type * aTy = a->getType();
24    if (isa<IntegerType>(aTy)) return aTy->getPrimitiveSizeInBits();
25    return cast<VectorType>(aTy)->getBitWidth();
26}
27   
28VectorType * IDISA_Builder::fwVectorType(const unsigned fw) {
29    return VectorType::get(getIntNTy(fw), mBitBlockWidth / fw);
30}
31
32Value * IDISA_Builder::fwCast(const unsigned fw, Value * const a) {
33    unsigned vecWidth = getVectorBitWidth(a);
34    return CreateBitCast(a, VectorType::get(getIntNTy(fw), vecWidth / fw));
35}
36
37void IDISA_Builder::UnsupportedFieldWidthError(const unsigned fw, std::string op_name) {
38    report_fatal_error(op_name + ": Unsupported field width: " +  std::to_string(fw));
39}
40
41void IDISA_Builder::CallPrintRegisterCond(StringRef regName, Value * const value, Value * const cond, const STD_FD fd) {
42    BasicBlock * const insertBefore = GetInsertBlock()->getNextNode();
43    BasicBlock* const callBlock = CreateBasicBlock("callBlock", insertBefore);
44    BasicBlock* const exitBlock = CreateBasicBlock("exitBlock", insertBefore);
45    CreateCondBr(cond, callBlock, exitBlock);
46    CallPrintRegister(regName, value, fd);
47    CreateBr(exitBlock);
48    SetInsertPoint(exitBlock);
49}
50
51void IDISA_Builder::CallPrintRegister(StringRef name, Value * const value, const STD_FD fd) {
52    Module * const m = getModule();
53    Constant * printRegister = m->getFunction("print_register");
54    if (LLVM_UNLIKELY(printRegister == nullptr)) {
55        FunctionType *FT = FunctionType::get(getVoidTy(), { getInt32Ty(), getInt8PtrTy(0), getBitBlockType() }, false);
56        Function * function = Function::Create(FT, Function::InternalLinkage, "print_register", m);
57        auto arg = function->arg_begin();
58        std::string tmp;
59        raw_string_ostream out(tmp);
60        out << "%-40s =";
61        for(unsigned i = 0; i < (getBitBlockWidth() / 8); ++i) {
62            out << " %02x";
63        }
64        out << '\n';
65        BasicBlock * entry = BasicBlock::Create(m->getContext(), "entry", function);
66        IRBuilder<> builder(entry);
67        Value * const fdInt = &*(arg++);
68        Value * const name = &*(arg++);
69        name->setName("name");
70        Value * value = &*arg;
71        value->setName("value");
72        Type * const byteVectorType = VectorType::get(getInt8Ty(), (mBitBlockWidth / 8));
73        value = builder.CreateBitCast(value, byteVectorType);
74
75        std::vector<Value *> args;
76        args.push_back(fdInt);
77        args.push_back(GetString(out.str()));
78        args.push_back(name);
79        for(unsigned i = (getBitBlockWidth() / 8); i != 0; --i) {
80            args.push_back(builder.CreateZExt(builder.CreateExtractElement(value, builder.getInt32(i - 1)), builder.getInt32Ty()));
81        }
82        builder.CreateCall(GetDprintf(), args);
83        builder.CreateRetVoid();
84        printRegister = function;
85    }
86    CreateCall(printRegister, {getInt32(static_cast<uint32_t>(fd)), GetString(name), CreateBitCast(value, getBitBlockType())});
87}
88
89Constant * IDISA_Builder::simd_himask(unsigned fw) {
90    return ConstantVector::getSplat(mBitBlockWidth/fw, Constant::getIntegerValue(getIntNTy(fw), APInt::getHighBitsSet(fw, fw/2)));
91}
92
93Constant * IDISA_Builder::simd_lomask(unsigned fw) {
94    return ConstantVector::getSplat(mBitBlockWidth/fw, Constant::getIntegerValue(getIntNTy(fw), APInt::getLowBitsSet(fw, fw/2)));
95}
96
97Value * IDISA_Builder::simd_select_hi(unsigned fw, Value * a) {
98    const unsigned vectorWidth = getVectorBitWidth(a);
99    Constant * maskField = Constant::getIntegerValue(getIntNTy(fw), APInt::getHighBitsSet(fw, fw/2));
100    return simd_and(a, ConstantVector::getSplat(vectorWidth/fw, maskField));
101}
102
103Value * IDISA_Builder::simd_select_lo(unsigned fw, Value * a) {
104    const unsigned vectorWidth = getVectorBitWidth(a);
105    Constant * maskField = Constant::getIntegerValue(getIntNTy(fw), APInt::getLowBitsSet(fw, fw/2));
106    return simd_and(a, ConstantVector::getSplat(vectorWidth/fw, maskField));
107}
108
109Constant * IDISA_Builder::getConstantVectorSequence(unsigned fw, unsigned first, unsigned last, unsigned by) {
110    const unsigned seqLgth = (last - first)/by + 1;
111    assert(((first + (seqLgth - 1) * by) == last) && "invalid element sequence");
112    Type * fwTy = getIntNTy(fw);
113    Constant * elements[seqLgth];
114    for (unsigned i = 0; i < seqLgth; i++) {
115        elements[i] = ConstantInt::get(fwTy, i*by + first);
116    }
117    return ConstantVector::get({elements, seqLgth});
118}
119
120Value * IDISA_Builder::CreateHalfVectorHigh(Value * vec) {
121    Value * v = fwCast(mLaneWidth, vec);
122    const unsigned N = getVectorBitWidth(v)/mLaneWidth;
123    return CreateShuffleVector(v, UndefValue::get(v->getType()), getConstantVectorSequence(32, N/2, N-1));
124}
125
126Value * IDISA_Builder::CreateHalfVectorLow(Value * vec) {
127    Value * v = fwCast(mLaneWidth, vec);
128    const unsigned N = getVectorBitWidth(v)/mLaneWidth;
129    return CreateShuffleVector(v, UndefValue::get(v->getType()), getConstantVectorSequence(32, 0, N/2-1));
130}
131
132Value * IDISA_Builder::CreateDoubleVector(Value * lo, Value * hi) {
133    const unsigned N = getVectorBitWidth(lo)/mLaneWidth;
134    return CreateShuffleVector(fwCast(mLaneWidth, lo), fwCast(mLaneWidth, hi), getConstantVectorSequence(32, 0, 2*N-1));
135}
136
137Value * IDISA_Builder::simd_fill(unsigned fw, Value * a) {
138    if (fw < 8) UnsupportedFieldWidthError(fw, "simd_fill");
139    const unsigned field_count = mBitBlockWidth/fw;
140    Type * singleFieldVecTy = VectorType::get(getIntNTy(fw), 1);
141    Value * aVec = CreateBitCast(CreateZExtOrTrunc(a, getIntNTy(fw)), singleFieldVecTy);
142    return CreateShuffleVector(aVec, UndefValue::get(singleFieldVecTy), Constant::getNullValue(VectorType::get(getInt32Ty(), field_count)));
143}
144
145Value * IDISA_Builder::simd_add(unsigned fw, Value * a, Value * b) {
146    if (fw == 1) {
147        return simd_xor(a, b);
148    } else if (fw < 8) {
149        Constant * hi_bit_mask = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
150                                                           APInt::getSplat(mBitBlockWidth, APInt::getHighBitsSet(fw, 1)));
151        Constant * lo_bit_mask = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
152                                                           APInt::getSplat(mBitBlockWidth, APInt::getLowBitsSet(fw, fw-1)));
153        Value * hi_xor = simd_xor(simd_and(a, hi_bit_mask), simd_and(b, hi_bit_mask));
154        Value * part_sum = simd_add(32, simd_and(a, lo_bit_mask), simd_and(b, lo_bit_mask));
155        return simd_xor(part_sum, hi_xor);
156    }
157    return CreateAdd(fwCast(fw, a), fwCast(fw, b));
158}
159
160Value * IDISA_Builder::simd_sub(unsigned fw, Value * a, Value * b) {
161    if (fw == 1) {
162        return simd_xor(a, b);
163    }
164    if (fw < 8) UnsupportedFieldWidthError(fw, "sub");
165    return CreateSub(fwCast(fw, a), fwCast(fw, b));
166}
167
168Value * IDISA_Builder::simd_mult(unsigned fw, Value * a, Value * b) {
169    if (fw < 8) UnsupportedFieldWidthError(fw, "mult");
170    return CreateMul(fwCast(fw, a), fwCast(fw, b));
171}
172
173Value * IDISA_Builder::simd_eq(unsigned fw, Value * a, Value * b) {
174    if (fw < 8) {
175        Value * eq_bits = simd_not(simd_xor(a, b));
176        if (fw == 1) return eq_bits;
177        eq_bits = simd_or(simd_and(simd_srli(32, simd_select_hi(2, eq_bits), 1), eq_bits),
178                          simd_and(simd_slli(32, simd_select_lo(2, eq_bits), 1), eq_bits));
179        if (fw == 2) return eq_bits;
180        eq_bits = simd_or(simd_and(simd_srli(32, simd_select_hi(4, eq_bits), 2), eq_bits),
181                          simd_and(simd_slli(32, simd_select_lo(4, eq_bits), 2), eq_bits));
182        return eq_bits;
183    }
184    Value * a1 = fwCast(fw, a);
185    Value * b1 = fwCast(fw, b);
186    return CreateSExt(CreateICmpEQ(a1, b1), a1->getType());
187}
188
189Value * IDISA_Builder::simd_gt(unsigned fw, Value * a, Value * b) {
190    if (fw < 8) UnsupportedFieldWidthError(fw, "gt");
191    Value * a1 = fwCast(fw, a);
192    Value * b1 = fwCast(fw, b);
193    return CreateSExt(CreateICmpSGT(a1, b1), a1->getType());
194}
195
196Value * IDISA_Builder::simd_ugt(unsigned fw, Value * a, Value * b) {
197    if (fw == 1) return simd_and(a, simd_not(b));
198    if (fw < 8) {
199        Value * half_ugt = simd_ugt(fw/2, a, b);
200        Value * half_eq = simd_eq(fw/2, a, b);
201        Value * ugt_0 = simd_or(simd_srli(fw, half_ugt, fw/2), simd_and(half_ugt, simd_srli(fw, half_eq, fw/2)));
202        return simd_or(ugt_0, simd_slli(32, ugt_0, fw/2));
203    }
204    if (fw < 8) UnsupportedFieldWidthError(fw, "ugt");
205    Value * a1 = fwCast(fw, a);
206    Value * b1 = fwCast(fw, b);
207    return CreateSExt(CreateICmpUGT(a1, b1), a1->getType());
208}
209
210Value * IDISA_Builder::simd_lt(unsigned fw, Value * a, Value * b) {
211    if (fw < 8) UnsupportedFieldWidthError(fw, "lt");
212    Value * a1 = fwCast(fw, a);
213    Value * b1 = fwCast(fw, b);
214    return CreateSExt(CreateICmpSLT(a1, b1), a1->getType());
215}
216
217Value * IDISA_Builder::simd_ult(unsigned fw, Value * a, Value * b) {
218    if (fw < 8) UnsupportedFieldWidthError(fw, "ult");
219    Value * a1 = fwCast(fw, a);
220    Value * b1 = fwCast(fw, b);
221    return CreateSExt(CreateICmpULT(a1, b1), a1->getType());
222}
223
224Value * IDISA_Builder::simd_ule(unsigned fw, Value * a, Value * b) {
225    if (fw == 1) return simd_or(simd_not(a), b);
226    if (fw < 8) {
227        Value * hi_rslt = simd_select_hi(2*fw, simd_ule(2*fw, simd_select_hi(2*fw, a), b));
228        Value * lo_rslt = simd_select_lo(2*fw, simd_ule(2*fw, simd_select_lo(2*fw, a), simd_select_lo(2*fw, b)));
229        return simd_or(hi_rslt, lo_rslt);
230    }
231    Value * a1 = fwCast(fw, a);
232    Value * b1 = fwCast(fw, b);
233    return CreateSExt(CreateICmpULE(a1, b1), a1->getType());
234}
235
236Value * IDISA_Builder::simd_uge(unsigned fw, Value * a, Value * b) {
237    if (fw == 1) return simd_or(a, simd_not(b));
238    if (fw < 8) {
239        Value * hi_rslt = simd_select_hi(2*fw, simd_uge(2*fw, a, simd_select_hi(2*fw, b)));
240        Value * lo_rslt = simd_select_lo(2*fw, simd_uge(2*fw, simd_select_lo(2*fw, a), simd_select_lo(2*fw, b)));
241        return simd_or(hi_rslt, lo_rslt);
242    }
243    if (fw < 8) UnsupportedFieldWidthError(fw, "ult");
244    Value * a1 = fwCast(fw, a);
245    Value * b1 = fwCast(fw, b);
246    return CreateSExt(CreateICmpUGE(a1, b1), a1->getType());
247}
248
249Value * IDISA_Builder::simd_max(unsigned fw, Value * a, Value * b) {
250    if (fw < 8) UnsupportedFieldWidthError(fw, "max");
251    Value * aVec = fwCast(fw, a);
252    Value * bVec = fwCast(fw, b);
253    return CreateSelect(CreateICmpSGT(aVec, bVec), aVec, bVec);
254}
255
256Value * IDISA_Builder::simd_umax(unsigned fw, Value * a, Value * b) {
257    if (fw == 1) return simd_or(a, b);
258    if (fw < 8) {
259        Value * hi_rslt = simd_select_hi(2*fw, simd_umax(2*fw, a, b));
260        Value * lo_rslt = simd_umax(2*fw, simd_select_lo(2*fw, a), simd_select_lo(2*fw, b));
261        return simd_or(hi_rslt, lo_rslt);
262    }
263    Value * aVec = fwCast(fw, a);
264    Value * bVec = fwCast(fw, b);
265    return CreateSelect(CreateICmpUGT(aVec, bVec), aVec, bVec);
266}
267
268Value * IDISA_Builder::simd_min(unsigned fw, Value * a, Value * b) {
269    if (fw < 8) UnsupportedFieldWidthError(fw, "min");
270    Value * aVec = fwCast(fw, a);
271    Value * bVec = fwCast(fw, b);
272    return CreateSelect(CreateICmpSLT(aVec, bVec), aVec, bVec);
273}
274
275Value * IDISA_Builder::simd_umin(unsigned fw, Value * a, Value * b) {
276    if (fw == 1) return simd_and(a, b);
277    if (fw < 8) {
278        Value * hi_rslt = simd_select_hi(2*fw, simd_umin(2*fw, a, b));
279        Value * lo_rslt = simd_umin(2*fw, simd_select_lo(2*fw, a), simd_select_lo(2*fw, b));
280        return simd_or(hi_rslt, lo_rslt);
281    }
282    Value * aVec = fwCast(fw, a);
283    Value * bVec = fwCast(fw, b);
284    return CreateSelect(CreateICmpULT(aVec, bVec), aVec, bVec);
285}
286
287Value * IDISA_Builder::mvmd_sll(unsigned fw, Value * value, Value * shift, const bool safe) {
288    VectorType * const vecTy = fwVectorType(fw);
289    IntegerType * const intTy = getIntNTy(vecTy->getBitWidth());
290    Constant * const FIELD_WIDTH = ConstantInt::get(shift->getType(), fw);
291//    Constant * const BLOCK_WIDTH = ConstantInt::get(shift->getType(), vecTy->getBitWidth());
292    shift = CreateMul(shift, FIELD_WIDTH);
293//    if (LLVM_UNLIKELY(safe && codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
294//        Value * const inbounds = CreateICmpULT(shift, BLOCK_WIDTH);
295//        CreateAssert(inbounds, "poison shift value: >= vector width");
296//    }
297    Value * result = nullptr;
298    value = CreateBitCast(value, intTy);
299//    if (safe) {
300        shift = CreateZExtOrTrunc(shift, intTy);
301        result = CreateShl(value, shift);
302//    } else {
303//        // TODO: check the ASM generated by this to see what the select generates
304//        Value * const moddedShift = CreateURem(shift, BLOCK_WIDTH);
305//        Value * const inbounds = CreateICmpEQ(moddedShift, shift);
306//        shift = CreateZExtOrTrunc(moddedShift, intTy);
307//        Constant * const ZEROES = Constant::getNullValue(intTy);
308//        result = CreateShl(value, shift);
309//        result = CreateSelect(inbounds, result, ZEROES);
310//    }
311    return CreateBitCast(result, vecTy);
312}
313
314Value * IDISA_Builder::mvmd_dsll(unsigned fw, Value * a, Value * b, Value * shift) {
315    if (fw < 8) UnsupportedFieldWidthError(fw, "mvmd_dsll");
316    const auto field_count = mBitBlockWidth/fw;
317    Type * fwTy = getIntNTy(fw);
318   
319    Constant * Idxs[field_count];
320    for (unsigned i = 0; i < field_count; i++) {
321        Idxs[i] = ConstantInt::get(fwTy, i + field_count);
322    }
323    Value * shuffle_indexes = simd_sub(fw, ConstantVector::get({Idxs, field_count}), simd_fill(fw, shift));
324    Value * rslt = mvmd_shuffle2(fw, fwCast(fw, b), fwCast(fw, a), shuffle_indexes);
325    return rslt;
326}
327
328Value * IDISA_Builder::mvmd_srl(unsigned fw, Value * value, Value * shift, const bool safe) {
329    VectorType * const vecTy = fwVectorType(fw);
330    IntegerType * const intTy = getIntNTy(vecTy->getBitWidth());
331    Constant * const FIELD_WIDTH = ConstantInt::get(shift->getType(), fw);
332//    Constant * const BLOCK_WIDTH = ConstantInt::get(shift->getType(), vecTy->getBitWidth());
333    shift = CreateMul(shift, FIELD_WIDTH);
334//    if (LLVM_UNLIKELY(safe && codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
335//        Value * const inbounds = CreateICmpULT(shift, BLOCK_WIDTH);
336//        CreateAssert(inbounds, "poison shift value: >= vector width");
337//    }
338    Value * result = nullptr;
339    value = CreateBitCast(value, intTy);
340//    if (safe) {
341        shift = CreateZExtOrTrunc(shift, intTy);
342        result = CreateLShr(value, shift);
343//    } else {
344//        // TODO: check the ASM generated by this to see what the select generates
345//        Value * const moddedShift = CreateURem(shift, BLOCK_WIDTH);
346//        Value * const inbounds = CreateICmpEQ(moddedShift, shift);
347//        shift = CreateZExtOrTrunc(moddedShift, intTy);
348//        Constant * const ZEROES = Constant::getNullValue(intTy);
349//        result = CreateLShr(value, shift);
350//        result = CreateSelect(inbounds, result, ZEROES);
351//    }
352    return CreateBitCast(result, vecTy);
353}
354
355Value * IDISA_Builder::simd_slli(unsigned fw, Value * a, unsigned shift) {
356    if (fw < 16) {
357        Constant * value_mask = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
358                                                          APInt::getSplat(mBitBlockWidth, APInt::getLowBitsSet(fw, fw-shift)));
359        return CreateShl(fwCast(32, simd_and(a, value_mask)), shift);
360    }
361    return CreateShl(fwCast(fw, a), shift);
362}
363
364Value * IDISA_Builder::simd_srli(unsigned fw, Value * a, unsigned shift) {
365    if (fw < 16) {
366        Constant * value_mask = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
367                                                          APInt::getSplat(mBitBlockWidth, APInt::getHighBitsSet(fw, fw-shift)));
368        return CreateLShr(fwCast(32, simd_and(a, value_mask)), shift);
369    }
370    return CreateLShr(fwCast(fw, a), shift);
371}
372
373Value * IDISA_Builder::simd_srai(unsigned fw, Value * a, unsigned shift) {
374    if (fw < 8) UnsupportedFieldWidthError(fw, "srai");
375    return CreateAShr(fwCast(fw, a), shift);
376}
377   
378Value * IDISA_Builder::simd_sllv(unsigned fw, Value * v, Value * shifts) {
379    if (fw >= 8) return CreateShl(fwCast(fw, v), fwCast(fw, shifts));
380    Value * w = v;
381    for (unsigned shft_amt = 1; shft_amt < fw; shft_amt *= 2) {
382        APInt bit_in_field(fw, shft_amt);
383        // To simulate shift within a fw, we need to mask off the high shft_amt bits of each element.
384        Constant * value_mask = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
385                                                          APInt::getSplat(mBitBlockWidth, APInt::getLowBitsSet(fw, fw-shft_amt)));
386        Constant * bit_select = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
387                                                          APInt::getSplat(mBitBlockWidth, bit_in_field));
388        Value * unshifted_field_mask = simd_eq(fw, simd_and(bit_select, shifts), allZeroes());
389        Value * fieldsToShift = simd_and(w, simd_and(value_mask, simd_not(unshifted_field_mask)));
390        w = simd_or(simd_and(w, unshifted_field_mask), simd_slli(32, fieldsToShift, shft_amt));
391    }
392    return w;
393}
394
395Value * IDISA_Builder::simd_srlv(unsigned fw, Value * v, Value * shifts) {
396    if (fw >= 8) return CreateLShr(fwCast(fw, v), fwCast(fw, shifts));
397    Value * w = v;
398    for (unsigned shft_amt = 1; shft_amt < fw; shft_amt *= 2) {
399        APInt bit_in_field(fw, shft_amt);
400        // To simulate shift within a fw, we need to mask off the low shft_amt bits of each element.
401        Constant * value_mask = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
402                                                          APInt::getSplat(mBitBlockWidth, APInt::getHighBitsSet(fw, fw-shft_amt)));
403        Constant * bit_select = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
404                                                          APInt::getSplat(mBitBlockWidth, bit_in_field));
405        Value * unshifted_field_mask = simd_eq(fw, simd_and(bit_select, shifts), allZeroes());
406        Value * fieldsToShift = simd_and(w, simd_and(value_mask, simd_not(unshifted_field_mask)));
407        w = simd_or(simd_and(w, unshifted_field_mask), simd_srli(32, fieldsToShift, shft_amt));
408    }
409    return w;
410}
411
412Value * IDISA_Builder::simd_pext(unsigned fieldwidth, Value * v, Value * extract_mask) {
413    Value * delcounts = CreateNot(extract_mask);  // initially deletion counts per 1-bit field
414    Value * w = simd_and(extract_mask, v);
415    for (unsigned fw = 2; fw < fieldwidth; fw = fw * 2) {
416        Value * shift_fwd_amts = simd_srli(fw, simd_select_lo(fw*2, delcounts), fw/2);
417        Value * shift_back_amts = simd_select_lo(fw, simd_select_hi(fw*2, delcounts));
418      w = simd_or(simd_sllv(fw, simd_select_lo(fw*2, w), shift_fwd_amts),
419                    simd_srlv(fw, simd_select_hi(fw*2, w), shift_back_amts));
420        delcounts = simd_add(fw, simd_select_lo(fw, delcounts), simd_srli(fw, delcounts, fw/2));
421    }
422    // Now shift back all fw fields.
423    Value * shift_back_amts = simd_select_lo(fieldwidth, delcounts);
424    w = simd_srlv(fieldwidth, w, shift_back_amts);
425    return w;
426}
427
428Value * IDISA_Builder::simd_pdep(unsigned fieldwidth, Value * v, Value * deposit_mask) {
429    // simd_pdep is implemented by reversing the process of simd_pext.
430    // First determine the deletion counts necessary for each stage of the process.
431    std::vector<Value *> delcounts;
432    delcounts.push_back(simd_not(deposit_mask)); // initially deletion counts per 1-bit field
433    for (unsigned fw = 2; fw < fieldwidth; fw = fw * 2) {
434        delcounts.push_back(simd_add(fw, simd_select_lo(fw, delcounts.back()), simd_srli(fw, delcounts.back(), fw/2)));
435    }
436    //
437    // Now reverse the pext process.  First reverse the final shift_back.
438    Value * pext_shift_back_amts = simd_select_lo(fieldwidth, delcounts.back());
439    Value * w = simd_sllv(fieldwidth, v, pext_shift_back_amts);
440    //
441    // No work through the smaller field widths.
442    for (unsigned fw = fieldwidth/2; fw >= 2; fw = fw/2) {
443        delcounts.pop_back();
444        Value * pext_shift_fwd_amts = simd_srli(fw, simd_select_lo(fw * 2, delcounts.back()), fw/2);
445        Value * pext_shift_back_amts = simd_select_lo(fw, simd_select_hi(fw*2, delcounts.back()));
446        w = simd_or(simd_srlv(fw, simd_select_lo(fw * 2, w), pext_shift_fwd_amts),
447                    simd_sllv(fw, simd_select_hi(fw * 2, w), pext_shift_back_amts));
448    }
449    return simd_and(w, deposit_mask);
450}
451
452Value * IDISA_Builder::simd_popcount(unsigned fw, Value * a) {
453    if (fw == 1) {
454        return a;
455    } else if (fw == 2) {
456        // For each 2-bit field ab we can use the subtraction ab - 0a to generate
457        // the popcount without carry/borrow from the neighbouring 2-bit field.
458        // case 00:  ab - 0a = 00 - 00 = 00
459        // case 01:  ab - 0a = 01 - 00 = 01
460        // case 10:  ab - 0a = 10 - 01 = 01 (no borrow)
461        // case 11:  ab - 0a = 11 - 01 = 10
462        return simd_sub(64, a, simd_srli(64, simd_select_hi(2, a), 1));
463    } else if (fw <= 8) {
464        Value * c = simd_popcount(fw/2, a);
465        c = simd_add(64, simd_select_lo(fw, c), simd_srli(fw, c, fw/2));
466        return c;
467    } else {
468        return CreatePopcount(fwCast(fw, a));
469    }
470}
471
472Value * IDISA_Builder::simd_cttz(unsigned fw, Value * a) {
473    if (fw == 1) {
474        return simd_not(a);
475    } else {
476        Value* v = simd_sub(fw, a, simd_fill(fw, getIntN(fw, 1)));
477        v = simd_or(v, a);
478        v = simd_xor(v, a);
479        v = simd_popcount(fw, v);
480        return v;
481    }
482}
483
484Value * IDISA_Builder::simd_bitreverse(unsigned fw, Value * a) {
485    /*  Pure sequential solution too slow!
486     Value * func = Intrinsic::getDeclaration(getModule(), Intrinsic::bitreverse, fwVectorType(fw));
487     return CreateCall(func, fwCast(fw, a));
488     */
489    if (fw > 8) {
490        // Reverse the bits of each byte and then use a byte shuffle to complete the job.
491        Value * bitrev8 = fwCast(8, simd_bitreverse(8, a));
492        const auto bytes_per_field = fw/8;
493        const unsigned vectorWidth = getVectorBitWidth(a);
494        const auto byte_count = vectorWidth / 8;
495        Constant * Idxs[byte_count];
496        for (unsigned i = 0; i < byte_count; i += bytes_per_field) {
497            for (unsigned j = 0; j < bytes_per_field; j++) {
498                Idxs[i + j] = getInt32(i + bytes_per_field - j - 1);
499            }
500        }
501        return CreateShuffleVector(bitrev8, UndefValue::get(bitrev8->getType()), ConstantVector::get({Idxs, byte_count}));
502    }
503    else {
504        if (fw > 2) {
505            a = simd_bitreverse(fw/2, a);
506        }
507        return simd_or(simd_srli(16, simd_select_hi(fw, a), fw/2), simd_slli(16, simd_select_lo(fw, a), fw/2));
508    }
509}
510
511Value * IDISA_Builder::simd_if(unsigned fw, Value * cond, Value * a, Value * b) {
512    if (fw == 1) {
513        Value * a1 = bitCast(a);
514        Value * b1 = bitCast(b);
515        Value * c = bitCast(cond);
516        return CreateOr(CreateAnd(a1, c), CreateAnd(CreateXor(c, b1), b1));
517    } else {
518        if (fw < 8) UnsupportedFieldWidthError(fw, "simd_if");
519        Value * aVec = fwCast(fw, a);
520        Value * bVec = fwCast(fw, b);
521        return CreateSelect(CreateICmpSLT(cond, mZeroInitializer), aVec, bVec);
522    }
523}
524
525Value * IDISA_Builder::simd_binary(unsigned char mask, Value * a, Value * b) {
526    // Form the 4-bit table for based on the bitwise values from a and b
527    // a b | mask = 0b1000
528    // 0 0 | 0
529    // 0 1 | 0
530    // 1 0 | 0
531    // 1 1 | 1
532    switch(mask) {
533        case 0b00000000: return allZeroes();
534        case 0b00000001: return CreateNot(CreateOr(a, b));
535        case 0b00000010: return CreateAnd(CreateNot(a), b);
536        case 0b00000011: return CreateNot(a);
537        case 0b00000100: return CreateAnd(a, CreateNot(b));
538        case 0b00000101: return CreateNot(b);
539        case 0b00000110: return CreateXor(a, b);
540        case 0b00000111: return CreateNot(CreateAnd(a, b));
541        case 0b00001000: return CreateAnd(a, b);
542        case 0b00001001: return CreateNot(CreateXor(a, b));
543        case 0b00001010: return b;
544        case 0b00001011: return CreateOr(CreateNot(a), b);
545        case 0b00001100: return a;
546        case 0b00001101: return CreateOr(a, CreateNot(b));
547        case 0b00001110: return CreateOr(a, b);
548        case 0b00001111: return allOnes();
549        default: report_fatal_error("simd_binary mask is in wrong format!");
550    }
551}
552
553Value * IDISA_Builder::simd_ternary(unsigned char mask, Value * a, Value * b, Value * c) {
554    if (mask == 0) return allZeroes();
555    else if (mask == 0xFF) return allOnes();
556
557    unsigned char not_a_mask = mask & 0x0F;
558    unsigned char a_mask = (mask >> 4) & 0x0F;
559
560    if (a_mask == not_a_mask) return simd_binary(a_mask, b, c);
561    else if ((a_mask ^ not_a_mask) == 0x0F) return CreateXor(a, simd_binary(not_a_mask, b, c));
562
563    Value * bc_hi = simd_binary(a_mask, b, c);
564    Value * bc_lo = simd_binary(not_a_mask, b, c);
565    Value * a_bc = CreateAnd(a, bc_hi);
566    Value * not_a_bc = CreateAnd(CreateNot(a), bc_lo);
567    return CreateOr(a_bc, not_a_bc);
568}
569   
570Value * IDISA_Builder::esimd_mergeh(unsigned fw, Value * a, Value * b) {
571    if (fw < 8) {
572        if (getVectorBitWidth(a) > mNativeBitBlockWidth) {
573            Value * a_hi = CreateHalfVectorHigh(a);
574            Value * b_hi = CreateHalfVectorHigh(b);
575            return CreateDoubleVector(esimd_mergel(fw, a_hi, b_hi), esimd_mergeh(fw, a_hi, b_hi));
576        }
577        Value * abh = simd_or(simd_select_hi(fw*2, b), simd_srli(32, simd_select_hi(fw*2, a), fw));
578        Value * abl = simd_or(simd_slli(32, simd_select_lo(fw*2, b), fw), simd_select_lo(fw*2, a));
579        return esimd_mergeh(fw * 2, abl, abh);
580    }
581    const auto field_count = getVectorBitWidth(a) / fw;
582    Constant * Idxs[field_count];
583    for (unsigned i = 0; i < field_count / 2; i++) {
584        Idxs[2 * i] = getInt32(i + field_count / 2); // selects elements from first reg.
585        Idxs[2 * i + 1] = getInt32(i + field_count / 2 + field_count); // selects elements from second reg.
586    }
587    return CreateShuffleVector(fwCast(fw, a), fwCast(fw, b), ConstantVector::get({Idxs, field_count}));
588}
589
590Value * IDISA_Builder::esimd_mergel(unsigned fw, Value * a, Value * b) {
591    if (fw < 8) {
592        if (getVectorBitWidth(a) > mNativeBitBlockWidth) {
593            Value * a_lo = CreateHalfVectorLow(a);
594            Value * b_lo = CreateHalfVectorLow(b);
595            return CreateDoubleVector(esimd_mergel(fw, a_lo, b_lo), esimd_mergeh(fw, a_lo, b_lo));
596        }
597        Value * abh = simd_or(simd_select_hi(fw*2, b), simd_srli(32, simd_select_hi(fw*2, a), fw));
598        Value * abl = simd_or(simd_slli(32, simd_select_lo(fw*2, b), fw), simd_select_lo(fw*2, a));
599        return esimd_mergel(fw * 2, abl, abh);
600    }
601    const auto field_count = getVectorBitWidth(a) / fw;
602    Constant * Idxs[field_count];
603    for (unsigned i = 0; i < field_count / 2; i++) {
604        Idxs[2 * i] = getInt32(i); // selects elements from first reg.
605        Idxs[2 * i + 1] = getInt32(i + field_count); // selects elements from second reg.
606    }
607    return CreateShuffleVector(fwCast(fw, a), fwCast(fw, b), ConstantVector::get({Idxs, field_count}));
608}
609
610Value * IDISA_Builder::esimd_bitspread(unsigned fw, Value * bitmask) {
611    if (fw < 8) UnsupportedFieldWidthError(fw, "bitspread");
612    const auto field_count = mBitBlockWidth / fw;
613    Type * field_type = getIntNTy(fw);
614    Value * spread_field = CreateBitCast(CreateZExtOrTrunc(bitmask, field_type), VectorType::get(getIntNTy(fw), 1));
615    Value * undefVec = UndefValue::get(VectorType::get(getIntNTy(fw), 1));
616    Value * broadcast = CreateShuffleVector(spread_field, undefVec, Constant::getNullValue(VectorType::get(getInt32Ty(), field_count)));
617    Constant * bitSel[field_count];
618    Constant * bitShift[field_count];
619    for (unsigned i = 0; i < field_count; i++) {
620        bitSel[i] = ConstantInt::get(field_type, 1 << i);
621        bitShift[i] = ConstantInt::get(field_type, i);
622    }
623    Value * bitSelVec = ConstantVector::get({bitSel, field_count});
624    Value * bitShiftVec = ConstantVector::get({bitShift, field_count});
625    return CreateLShr(CreateAnd(bitSelVec, broadcast), bitShiftVec);
626}
627
628Value * IDISA_Builder::hsimd_packh(unsigned fw, Value * a, Value * b) {
629    if (fw <= 8) {
630        const unsigned fw_wkg = 32;
631        Value * aLo = simd_srli(fw_wkg, a, fw/2);
632        Value * bLo = simd_srli(fw_wkg, b, fw/2);
633        return hsimd_packl(fw, aLo, bLo);
634    }
635    Value * aVec = fwCast(fw/2, a);
636    Value * bVec = fwCast(fw/2, b);
637    const auto field_count = 2 * mBitBlockWidth / fw;
638    Constant * Idxs[field_count];
639    for (unsigned i = 0; i < field_count; i++) {
640        Idxs[i] = getInt32(2 * i + 1);
641    }
642    return CreateShuffleVector(aVec, bVec, ConstantVector::get({Idxs, field_count}));
643}
644
645Value * IDISA_Builder::hsimd_packl(unsigned fw, Value * a, Value * b) {
646    if (fw <= 8) {
647        const unsigned fw_wkg = 32;
648        Value * aLo = simd_srli(fw_wkg, a, fw/2);
649        Value * bLo = simd_srli(fw_wkg, b, fw/2);
650        return hsimd_packl(fw*2,
651                           bitCast(simd_or(simd_select_hi(fw, aLo), simd_select_lo(fw, a))),
652                           bitCast(simd_or(simd_select_hi(fw, bLo), simd_select_lo(fw, b))));
653    }
654    Value * aVec = fwCast(fw/2, a);
655    Value * bVec = fwCast(fw/2, b);
656    const auto field_count = 2 * mBitBlockWidth / fw;
657    Constant * Idxs[field_count];
658    for (unsigned i = 0; i < field_count; i++) {
659        Idxs[i] = getInt32(2 * i);
660    }
661    return CreateShuffleVector(aVec, bVec, ConstantVector::get({Idxs, field_count}));
662}
663
664Value * IDISA_Builder::hsimd_packh_in_lanes(unsigned lanes, unsigned fw, Value * a, Value * b) {
665    if (fw < 16) UnsupportedFieldWidthError(fw, "packh_in_lanes");
666    const unsigned fw_out = fw / 2;
667    const unsigned fields_per_lane = mBitBlockWidth / (fw_out * lanes);
668    const unsigned field_offset_for_b = mBitBlockWidth / fw_out;
669    const unsigned field_count = mBitBlockWidth / fw_out;
670    Constant * Idxs[field_count];
671    for (unsigned lane = 0, j = 0; lane < lanes; lane++) {
672        const unsigned first_field_in_lane = lane * fields_per_lane; // every second field
673        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
674            Idxs[j++] = getInt32(first_field_in_lane + (2 * i) + 1);
675        }
676        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
677            Idxs[j++] = getInt32(field_offset_for_b + first_field_in_lane + (2 * i) + 1);
678        }
679    }
680    return CreateShuffleVector(fwCast(fw_out, a), fwCast(fw_out, b), ConstantVector::get({Idxs, field_count}));
681}
682
683Value * IDISA_Builder::hsimd_packl_in_lanes(unsigned lanes, unsigned fw, Value * a, Value * b) {
684    if (fw < 16) UnsupportedFieldWidthError(fw, "packl_in_lanes");
685    const unsigned fw_out = fw / 2;
686    const unsigned fields_per_lane = mBitBlockWidth / (fw_out * lanes);
687    const unsigned field_offset_for_b = mBitBlockWidth / fw_out;
688    const unsigned field_count = mBitBlockWidth / fw_out;
689    Constant * Idxs[field_count];
690    for (unsigned lane = 0, j = 0; lane < lanes; lane++) {
691        const unsigned first_field_in_lane = lane * fields_per_lane; // every second field
692        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
693            Idxs[j++] = getInt32(first_field_in_lane + (2 * i));
694        }
695        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
696            Idxs[j++] = getInt32(field_offset_for_b + first_field_in_lane + (2 * i));
697        }
698    }
699    return CreateShuffleVector(fwCast(fw_out, a), fwCast(fw_out, b), ConstantVector::get({Idxs, field_count}));
700}
701
702Value * IDISA_Builder::hsimd_signmask(unsigned fw, Value * a) {
703    if (fw < 8) UnsupportedFieldWidthError(fw, "hsimd_signmask");
704    Value * a1 = fwCast(fw, a);
705    Value * mask = CreateICmpSLT(a1, ConstantAggregateZero::get(a1->getType()));
706    mask = CreateBitCast(mask, getIntNTy(mBitBlockWidth/fw));
707    if (mBitBlockWidth/fw < 32) return CreateZExt(mask, getInt32Ty());
708    else return mask;
709}
710
711Value * IDISA_Builder::mvmd_extract(unsigned fw, Value * a, unsigned fieldIndex) {
712    if (fw < 8) {
713        unsigned byte_no = (fieldIndex * fw) / 8;
714        unsigned intrabyte_shift = (fieldIndex * fw) % 8;
715        Value * byte = CreateExtractElement(fwCast(8, a), getInt32(byte_no));
716        return CreateTrunc(CreateLShr(byte, getInt8(intrabyte_shift)), getIntNTy(fw));
717    }
718    return CreateExtractElement(fwCast(fw, a), getInt32(fieldIndex));
719}
720
721Value * IDISA_Builder::mvmd_insert(unsigned fw, Value * a, Value * elt, unsigned fieldIndex) {
722    if (fw < 8) {
723        unsigned byte_no = (fieldIndex * fw) / 8;
724        unsigned intrabyte_shift = (fieldIndex * fw) % 8;
725        unsigned field_mask = ((1 << fw) - 1) << intrabyte_shift;
726        Value * byte = CreateAnd(CreateExtractElement(fwCast(8, a), getInt32(byte_no)), getInt8(0xFF &~ field_mask));
727        byte = CreateOr(byte, CreateShl(CreateZExtOrTrunc(elt, getInt8Ty()), getInt8(intrabyte_shift)));
728        return CreateInsertElement(fwCast(8, a), byte, getInt32(byte_no));
729    }
730    return CreateInsertElement(fwCast(fw, a), elt, getInt32(fieldIndex));
731}
732
733Value * IDISA_Builder::mvmd_slli(unsigned fw, Value * a, unsigned shift) {
734    if (fw < 8) UnsupportedFieldWidthError(fw, "mvmd_slli");
735    Value * a1 = fwCast(fw, a);
736    Value * shifted = mvmd_dslli(fw, a1, Constant::getNullValue(a1->getType()), shift);
737    return shifted;
738}
739
740Value * IDISA_Builder::mvmd_srli(unsigned fw, Value * a, unsigned shift) {
741    if (fw < 8) UnsupportedFieldWidthError(fw, "mvmd_srli");
742    const auto field_count = getVectorBitWidth(a) / fw;
743    Value * a1 = fwCast(fw, a);
744    return mvmd_dslli(fw, Constant::getNullValue(a1->getType()), a1, field_count - shift);
745}
746
747Value * IDISA_Builder::mvmd_dslli(unsigned fw, Value * a, Value * b, unsigned shift) {
748    if (fw < 8) UnsupportedFieldWidthError(fw, "mvmd_dslli");
749    const auto field_count = getVectorBitWidth(a) / fw;
750    Constant * Idxs[field_count];
751    for (unsigned i = 0; i < field_count; i++) {
752        Idxs[i] = getInt32(i + field_count - shift);
753    }
754    return CreateShuffleVector(fwCast(fw, b), fwCast(fw, a), ConstantVector::get({Idxs, field_count}));
755}
756
757Value * IDISA_Builder::mvmd_shuffle(unsigned fw, Value * table, Value * index_vector) {
758    UnsupportedFieldWidthError(fw, "mvmd_shuffle");
759}
760   
761Value * IDISA_Builder::mvmd_shuffle2(unsigned fw, Value * table0, Value * table1, Value * index_vector) {
762    //  Use two shuffles, with selection by the bit value within the shuffle_table.
763    const auto field_count = mBitBlockWidth/fw;
764    Constant * selectorSplat = ConstantVector::getSplat(field_count, ConstantInt::get(getIntNTy(fw), field_count));
765    Value * selectMask = simd_eq(fw, simd_and(index_vector, selectorSplat), selectorSplat);
766    Value * idx = simd_and(index_vector, simd_not(selectorSplat));
767    Value * rslt= simd_or(simd_and(mvmd_shuffle(fw, table0, idx), simd_not(selectMask)), simd_and(mvmd_shuffle(fw, table1, idx), selectMask));
768    return rslt;
769}
770   
771
772Value * IDISA_Builder::mvmd_compress(unsigned fw, Value * a, Value * select_mask) {
773    UnsupportedFieldWidthError(fw, "mvmd_compress");
774}
775
776Value * IDISA_Builder::bitblock_any(Value * a) {
777    Type * iBitBlock = getIntNTy(getVectorBitWidth(a));
778    return CreateICmpNE(CreateBitCast(a, iBitBlock),  ConstantInt::getNullValue(iBitBlock));
779}
780
781// full add producing {carryout, sum}
782std::pair<Value *, Value *> IDISA_Builder::bitblock_add_with_carry(Value * a, Value * b, Value * carryin) {
783    Value * carrygen = simd_and(a, b);
784    Value * carryprop = simd_or(a, b);
785    Value * sum = simd_add(mBitBlockWidth, simd_add(mBitBlockWidth, a, b), carryin);
786    Value * carryout = CreateBitCast(simd_or(carrygen, simd_and(carryprop, CreateNot(sum))), getIntNTy(mBitBlockWidth));
787    return std::pair<Value *, Value *>(bitCast(simd_srli(mBitBlockWidth, carryout, mBitBlockWidth - 1)), bitCast(sum));
788}
789
790// full shift producing {shiftout, shifted}
791std::pair<Value *, Value *> IDISA_Builder::bitblock_advance(Value * a, Value * shiftin, unsigned shift) {
792    Value * shiftin_bitblock = CreateBitCast(shiftin, getIntNTy(mBitBlockWidth));
793    Value * a_bitblock = CreateBitCast(a, getIntNTy(mBitBlockWidth));
794    Value * shifted = bitCast(CreateOr(CreateShl(a_bitblock, shift), shiftin_bitblock));
795    Value * shiftout = bitCast(CreateLShr(a_bitblock, mBitBlockWidth - shift));
796    return std::pair<Value *, Value *>(shiftout, shifted);
797}
798
799// full shift producing {shiftout, shifted}
800std::pair<Value *, Value *> IDISA_Builder::bitblock_indexed_advance(Value * strm, Value * index_strm, Value * shiftIn, unsigned shiftAmount) {
801    const unsigned bitWidth = getSizeTy()->getBitWidth();
802    Type * const iBitBlock = getIntNTy(getBitBlockWidth());
803    Value * const shiftVal = getSize(shiftAmount);
804    Value * extracted_bits = simd_pext(bitWidth, strm, index_strm);
805    Value * ix_popcounts = simd_popcount(bitWidth, index_strm);
806    const auto n = getBitBlockWidth() / bitWidth;
807    VectorType * const vecTy = VectorType::get(getSizeTy(), n);
808    if (LLVM_LIKELY(shiftAmount < bitWidth)) {
809        Value * carry = mvmd_extract(bitWidth, shiftIn, 0);
810        Value * result = UndefValue::get(vecTy);
811        for (unsigned i = 0; i < n; i++) {
812            Value * ix_popcnt = mvmd_extract(bitWidth, ix_popcounts, i);
813            Value * bits = mvmd_extract(bitWidth, extracted_bits, i);
814            Value * adv = CreateOr(CreateShl(bits, shiftAmount), carry);
815            // We have two cases depending on whether the popcount of the index pack is < shiftAmount or not.
816            Value * popcount_small = CreateICmpULT(ix_popcnt, shiftVal);
817            Value * carry_if_popcount_small =
818                CreateOr(CreateShl(bits, CreateSub(shiftVal, ix_popcnt)),
819                            CreateLShr(carry, ix_popcnt));
820            Value * carry_if_popcount_large = CreateLShr(bits, CreateSub(ix_popcnt, shiftVal));
821            carry = CreateSelect(popcount_small, carry_if_popcount_small, carry_if_popcount_large);
822            result = mvmd_insert(bitWidth, result, adv, i);
823        }
824        Value * carryOut = mvmd_insert(bitWidth, allZeroes(), carry, 0);
825        return std::pair<Value *, Value *>{bitCast(carryOut), simd_pdep(bitWidth, result, index_strm)};
826    }
827    else if (shiftAmount <= mBitBlockWidth) {
828        // The shift amount is always greater than the popcount of the individual
829        // elements that we deal with.   This simplifies some of the logic.
830        Value * carry = CreateBitCast(shiftIn, iBitBlock);
831        Value * result = UndefValue::get(vecTy);
832        for (unsigned i = 0; i < n; i++) {
833            Value * ix_popcnt = mvmd_extract(bitWidth, ix_popcounts, i);
834            Value * bits = mvmd_extract(bitWidth, extracted_bits, i);  // All these bits are shifted out (appended to carry).
835            result = mvmd_insert(bitWidth, result, mvmd_extract(bitWidth, carry, 0), i);
836            carry = CreateLShr(carry, CreateZExt(ix_popcnt, iBitBlock)); // Remove the carry bits consumed, make room for new bits.
837            carry = CreateOr(carry, CreateShl(CreateZExt(bits, iBitBlock), CreateZExt(CreateSub(shiftVal, ix_popcnt), iBitBlock)));
838        }
839        return std::pair<Value *, Value *>{bitCast(carry), simd_pdep(bitWidth, result, index_strm)};
840    }
841    else {
842        // The shift amount is greater than the total popcount.   We will consume popcount
843        // bits from the shiftIn value only, and produce a carry out value of the selected bits.
844        Value * carry = CreateBitCast(shiftIn, iBitBlock);
845        Value * result = UndefValue::get(vecTy);
846        Value * carryOut = ConstantInt::getNullValue(iBitBlock);
847        Value * generated = getSize(0);
848        for (unsigned i = 0; i < n; i++) {
849            Value * ix_popcnt = mvmd_extract(bitWidth, ix_popcounts, i);
850            Value * bits = mvmd_extract(bitWidth, extracted_bits, i);  // All these bits are shifted out (appended to carry).
851            result = mvmd_insert(bitWidth, result, mvmd_extract(bitWidth, carry, 0), i);
852            carry = CreateLShr(carry, CreateZExt(ix_popcnt, iBitBlock)); // Remove the carry bits consumed.
853            carryOut = CreateOr(carryOut, CreateShl(CreateZExt(bits, iBitBlock), CreateZExt(generated, iBitBlock)));
854            generated = CreateAdd(generated, ix_popcnt);
855        }
856        return std::pair<Value *, Value *>{bitCast(carryOut), simd_pdep(bitWidth, result, index_strm)};
857    }
858}
859
860Value * IDISA_Builder::bitblock_mask_from(Value * const position, const bool safe) {
861    Value * const originalPos = CreateZExtOrTrunc(position, getSizeTy());
862    if (LLVM_UNLIKELY(safe && codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
863        Constant * const BLOCK_WIDTH = getSize(mBitBlockWidth);
864        CreateAssert(CreateICmpULT(originalPos, BLOCK_WIDTH), "position exceeds block width");
865    }
866    Value * const pos = safe ? position : CreateAnd(originalPos, getSize(mBitBlockWidth - 1));
867    const unsigned fieldWidth = getSizeTy()->getBitWidth();
868    const auto fieldCount = mBitBlockWidth / fieldWidth;
869    Constant * posBase[fieldCount];
870    for (unsigned i = 0; i < fieldCount; i++) {
871        posBase[i] = ConstantInt::get(getSizeTy(), fieldWidth * i);
872    }
873    Value * const posBaseVec = ConstantVector::get({posBase, fieldCount});
874    Value * const positionVec = simd_fill(fieldWidth, pos);
875    Value * const fullFieldWidthMasks = CreateSExt(CreateICmpUGT(posBaseVec, positionVec), fwVectorType(fieldWidth));
876    Constant * const FIELD_ONES = ConstantInt::getAllOnesValue(getSizeTy());
877    Value * const bitField = CreateShl(FIELD_ONES, CreateAnd(pos, getSize(fieldWidth - 1)));
878    Value * const fieldNo = CreateLShr(pos, getSize(std::log2(fieldWidth)));   
879    Value * result = CreateInsertElement(fullFieldWidthMasks, bitField, fieldNo);
880    if (!safe) { // if the originalPos doesn't match the moddedPos then the originalPos must exceed the block width.
881        Constant * const VECTOR_ZEROES = Constant::getNullValue(fwVectorType(fieldWidth));
882        result = CreateSelect(CreateICmpEQ(originalPos, pos), result, VECTOR_ZEROES);
883    }
884    return bitCast(result);
885}
886
887Value * IDISA_Builder::bitblock_mask_to(Value * const position, const bool safe) {
888    Value * const originalPos = CreateZExtOrTrunc(position, getSizeTy());
889    if (LLVM_UNLIKELY(safe && codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
890        Constant * const BLOCK_WIDTH = getSize(mBitBlockWidth);
891        CreateAssert(CreateICmpULT(originalPos, BLOCK_WIDTH), "position exceeds block width");
892    }
893    Value * const pos = safe ? position : CreateAnd(originalPos, getSize(mBitBlockWidth - 1));
894    const unsigned fieldWidth = getSizeTy()->getBitWidth();
895    const auto fieldCount = mBitBlockWidth / fieldWidth;
896    Constant * posBase[fieldCount];
897    for (unsigned i = 0; i < fieldCount; i++) {
898        posBase[i] = ConstantInt::get(getSizeTy(), fieldWidth * i);
899    }
900    Value * const posBaseVec = ConstantVector::get({posBase, fieldCount});
901    Value * const positionVec = simd_fill(fieldWidth, pos);
902    Value * const fullFieldWidthMasks = CreateSExt(CreateICmpULT(posBaseVec, positionVec), fwVectorType(fieldWidth));
903    Constant * const FIELD_ONES = ConstantInt::getAllOnesValue(getSizeTy());
904    Value * const bitField = CreateLShr(FIELD_ONES, CreateAnd(getSize(fieldWidth - 1), CreateNot(pos)));
905    Value * const fieldNo = CreateLShr(pos, getSize(std::log2(fieldWidth)));
906    Value * result = CreateInsertElement(fullFieldWidthMasks, bitField, fieldNo);
907    if (!safe) { // if the originalPos doesn't match the moddedPos then the originalPos must exceed the block width.
908        Constant * const VECTOR_ONES = Constant::getAllOnesValue(fwVectorType(fieldWidth));
909        result = CreateSelect(CreateICmpEQ(originalPos, pos), result, VECTOR_ONES);
910    }
911    return bitCast(result);
912}
913
914Value * IDISA_Builder::bitblock_set_bit(Value * const position, const bool safe) {
915    Value * const originalPos = CreateZExtOrTrunc(position, getSizeTy());
916    if (LLVM_UNLIKELY(safe && codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
917        Constant * const BLOCK_WIDTH = getSize(mBitBlockWidth);
918        CreateAssert(CreateICmpULT(originalPos, BLOCK_WIDTH), "position exceeds block width");
919    }
920    const unsigned fieldWidth = getSizeTy()->getBitWidth();
921    Value * const bitField = CreateShl(getSize(1), CreateAnd(originalPos, getSize(fieldWidth - 1)));
922    Value * const pos = safe ? position : CreateAnd(originalPos, getSize(mBitBlockWidth - 1));
923    Value * const fieldNo = CreateLShr(pos, getSize(std::log2(fieldWidth)));
924    Constant * const VECTOR_ZEROES = Constant::getNullValue(fwVectorType(fieldWidth));
925    Value * result = CreateInsertElement(VECTOR_ZEROES, bitField, fieldNo);
926    if (!safe) { // If the originalPos doesn't match the moddedPos then the originalPos must exceed the block width.
927        result = CreateSelect(CreateICmpEQ(originalPos, pos), result, VECTOR_ZEROES);
928    }
929    return bitCast(result);
930}
931
932Value * IDISA_Builder::bitblock_popcount(Value * const to_count) {
933    const auto fieldWidth = getSizeTy()->getBitWidth();
934    auto fields = (getBitBlockWidth() / fieldWidth);
935    Value * fieldCounts = simd_popcount(fieldWidth, to_count);
936    while (fields > 1) {
937        fields /= 2;
938        fieldCounts = CreateAdd(fieldCounts, mvmd_srli(fieldWidth, fieldCounts, fields));
939    }
940    return mvmd_extract(fieldWidth, fieldCounts, 0);
941}
942
943Value * IDISA_Builder::simd_and(Value * a, Value * b, StringRef s) {
944    return a->getType() == b->getType() ? CreateAnd(a, b, s) : CreateAnd(bitCast(a), bitCast(b), s);
945}
946
947Value * IDISA_Builder::simd_or(Value * a, Value * b, StringRef s) {
948    return a->getType() == b->getType() ? CreateOr(a, b, s) : CreateOr(bitCast(a), bitCast(b), s);
949}
950   
951Value * IDISA_Builder::simd_xor(Value * a, Value * b, StringRef s) {
952    return a->getType() == b->getType() ? CreateXor(a, b, s) : CreateXor(bitCast(a), bitCast(b), s);
953}
954
955Value * IDISA_Builder::simd_not(Value * a, StringRef s) {
956    return simd_xor(a, Constant::getAllOnesValue(a->getType()), s);
957}
958
959Constant * IDISA_Builder::bit_interleave_byteshuffle_table(unsigned fw) {
960    const unsigned fieldCount = mNativeBitBlockWidth/8;
961    if (fw > 2) report_fatal_error("bit_interleave_byteshuffle_table requires fw == 1 or fw == 2");
962    // Bit interleave using shuffle.
963    // Make a shuffle table that translates the lower 4 bits of each byte in
964    // order to spread out the bits: xxxxdcba => .d.c.b.a (fw = 1)
965    Constant * bit_interleave[fieldCount];
966    for (unsigned i = 0; i < fieldCount; i++) {
967        if (fw == 1)
968            bit_interleave[i] = getInt8((i & 1) | ((i & 2) << 1) | ((i & 4) << 2) | ((i & 8) << 3));
969        else bit_interleave[i] = getInt8((i & 3) | ((i & 0x0C) << 2));
970    }
971    return ConstantVector::get({bit_interleave, fieldCount});
972}
973
974IDISA_Builder::IDISA_Builder(LLVMContext & C, unsigned nativeVectorWidth, unsigned vectorWidth, unsigned laneWidth)
975: CBuilder(C)
976, mNativeBitBlockWidth(nativeVectorWidth)
977, mBitBlockWidth(vectorWidth)
978, mLaneWidth(laneWidth)
979, mBitBlockType(VectorType::get(IntegerType::get(C, mLaneWidth), vectorWidth / mLaneWidth))
980, mZeroInitializer(Constant::getNullValue(mBitBlockType))
981, mOneInitializer(Constant::getAllOnesValue(mBitBlockType))
982, mPrintRegisterFunction(nullptr) {
983
984}
985
986IDISA_Builder::~IDISA_Builder() {
987
988}
989
990}
Note: See TracBrowser for help on using the repository browser.