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

Last change on this file since 6220 was 6220, checked in by cameron, 6 months ago

Trace facility initial check-in

File size: 44.8 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::esimd_mergeh(unsigned fw, Value * a, Value * b) {
526    if (fw < 8) {
527        if (getVectorBitWidth(a) > mNativeBitBlockWidth) {
528            Value * a_hi = CreateHalfVectorHigh(a);
529            Value * b_hi = CreateHalfVectorHigh(b);
530            return CreateDoubleVector(esimd_mergel(fw, a_hi, b_hi), esimd_mergeh(fw, a_hi, b_hi));
531        }
532        Value * abh = simd_or(simd_select_hi(fw*2, b), simd_srli(32, simd_select_hi(fw*2, a), fw));
533        Value * abl = simd_or(simd_slli(32, simd_select_lo(fw*2, b), fw), simd_select_lo(fw*2, a));
534        return esimd_mergeh(fw * 2, abl, abh);
535    }
536    const auto field_count = getVectorBitWidth(a) / fw;
537    Constant * Idxs[field_count];
538    for (unsigned i = 0; i < field_count / 2; i++) {
539        Idxs[2 * i] = getInt32(i + field_count / 2); // selects elements from first reg.
540        Idxs[2 * i + 1] = getInt32(i + field_count / 2 + field_count); // selects elements from second reg.
541    }
542    return CreateShuffleVector(fwCast(fw, a), fwCast(fw, b), ConstantVector::get({Idxs, field_count}));
543}
544
545Value * IDISA_Builder::esimd_mergel(unsigned fw, Value * a, Value * b) {
546    if (fw < 8) {
547        if (getVectorBitWidth(a) > mNativeBitBlockWidth) {
548            Value * a_lo = CreateHalfVectorLow(a);
549            Value * b_lo = CreateHalfVectorLow(b);
550            return CreateDoubleVector(esimd_mergel(fw, a_lo, b_lo), esimd_mergeh(fw, a_lo, b_lo));
551        }
552        Value * abh = simd_or(simd_select_hi(fw*2, b), simd_srli(32, simd_select_hi(fw*2, a), fw));
553        Value * abl = simd_or(simd_slli(32, simd_select_lo(fw*2, b), fw), simd_select_lo(fw*2, a));
554        return esimd_mergel(fw * 2, abl, abh);
555    }
556    const auto field_count = getVectorBitWidth(a) / fw;
557    Constant * Idxs[field_count];
558    for (unsigned i = 0; i < field_count / 2; i++) {
559        Idxs[2 * i] = getInt32(i); // selects elements from first reg.
560        Idxs[2 * i + 1] = getInt32(i + field_count); // selects elements from second reg.
561    }
562    return CreateShuffleVector(fwCast(fw, a), fwCast(fw, b), ConstantVector::get({Idxs, field_count}));
563}
564
565Value * IDISA_Builder::esimd_bitspread(unsigned fw, Value * bitmask) {
566    if (fw < 8) UnsupportedFieldWidthError(fw, "bitspread");
567    const auto field_count = mBitBlockWidth / fw;
568    Type * field_type = getIntNTy(fw);
569    Value * spread_field = CreateBitCast(CreateZExtOrTrunc(bitmask, field_type), VectorType::get(getIntNTy(fw), 1));
570    Value * undefVec = UndefValue::get(VectorType::get(getIntNTy(fw), 1));
571    Value * broadcast = CreateShuffleVector(spread_field, undefVec, Constant::getNullValue(VectorType::get(getInt32Ty(), field_count)));
572    Constant * bitSel[field_count];
573    Constant * bitShift[field_count];
574    for (unsigned i = 0; i < field_count; i++) {
575        bitSel[i] = ConstantInt::get(field_type, 1 << i);
576        bitShift[i] = ConstantInt::get(field_type, i);
577    }
578    Value * bitSelVec = ConstantVector::get({bitSel, field_count});
579    Value * bitShiftVec = ConstantVector::get({bitShift, field_count});
580    return CreateLShr(CreateAnd(bitSelVec, broadcast), bitShiftVec);
581}
582
583Value * IDISA_Builder::hsimd_packh(unsigned fw, Value * a, Value * b) {
584    if (fw <= 8) {
585        const unsigned fw_wkg = 32;
586        Value * aLo = simd_srli(fw_wkg, a, fw/2);
587        Value * bLo = simd_srli(fw_wkg, b, fw/2);
588        return hsimd_packl(fw, aLo, bLo);
589    }
590    Value * aVec = fwCast(fw/2, a);
591    Value * bVec = fwCast(fw/2, b);
592    const auto field_count = 2 * mBitBlockWidth / fw;
593    Constant * Idxs[field_count];
594    for (unsigned i = 0; i < field_count; i++) {
595        Idxs[i] = getInt32(2 * i + 1);
596    }
597    return CreateShuffleVector(aVec, bVec, ConstantVector::get({Idxs, field_count}));
598}
599
600Value * IDISA_Builder::hsimd_packl(unsigned fw, Value * a, Value * b) {
601    if (fw <= 8) {
602        const unsigned fw_wkg = 32;
603        Value * aLo = simd_srli(fw_wkg, a, fw/2);
604        Value * bLo = simd_srli(fw_wkg, b, fw/2);
605        return hsimd_packl(fw*2,
606                           bitCast(simd_or(simd_select_hi(fw, aLo), simd_select_lo(fw, a))),
607                           bitCast(simd_or(simd_select_hi(fw, bLo), simd_select_lo(fw, b))));
608    }
609    Value * aVec = fwCast(fw/2, a);
610    Value * bVec = fwCast(fw/2, b);
611    const auto field_count = 2 * mBitBlockWidth / fw;
612    Constant * Idxs[field_count];
613    for (unsigned i = 0; i < field_count; i++) {
614        Idxs[i] = getInt32(2 * i);
615    }
616    return CreateShuffleVector(aVec, bVec, ConstantVector::get({Idxs, field_count}));
617}
618
619Value * IDISA_Builder::hsimd_packh_in_lanes(unsigned lanes, unsigned fw, Value * a, Value * b) {
620    if (fw < 16) UnsupportedFieldWidthError(fw, "packh_in_lanes");
621    const unsigned fw_out = fw / 2;
622    const unsigned fields_per_lane = mBitBlockWidth / (fw_out * lanes);
623    const unsigned field_offset_for_b = mBitBlockWidth / fw_out;
624    const unsigned field_count = mBitBlockWidth / fw_out;
625    Constant * Idxs[field_count];
626    for (unsigned lane = 0, j = 0; lane < lanes; lane++) {
627        const unsigned first_field_in_lane = lane * fields_per_lane; // every second field
628        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
629            Idxs[j++] = getInt32(first_field_in_lane + (2 * i) + 1);
630        }
631        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
632            Idxs[j++] = getInt32(field_offset_for_b + first_field_in_lane + (2 * i) + 1);
633        }
634    }
635    return CreateShuffleVector(fwCast(fw_out, a), fwCast(fw_out, b), ConstantVector::get({Idxs, field_count}));
636}
637
638Value * IDISA_Builder::hsimd_packl_in_lanes(unsigned lanes, unsigned fw, Value * a, Value * b) {
639    if (fw < 16) UnsupportedFieldWidthError(fw, "packl_in_lanes");
640    const unsigned fw_out = fw / 2;
641    const unsigned fields_per_lane = mBitBlockWidth / (fw_out * lanes);
642    const unsigned field_offset_for_b = mBitBlockWidth / fw_out;
643    const unsigned field_count = mBitBlockWidth / fw_out;
644    Constant * Idxs[field_count];
645    for (unsigned lane = 0, j = 0; lane < lanes; lane++) {
646        const unsigned first_field_in_lane = lane * fields_per_lane; // every second field
647        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
648            Idxs[j++] = getInt32(first_field_in_lane + (2 * i));
649        }
650        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
651            Idxs[j++] = getInt32(field_offset_for_b + first_field_in_lane + (2 * i));
652        }
653    }
654    return CreateShuffleVector(fwCast(fw_out, a), fwCast(fw_out, b), ConstantVector::get({Idxs, field_count}));
655}
656
657Value * IDISA_Builder::hsimd_signmask(unsigned fw, Value * a) {
658    if (fw < 8) UnsupportedFieldWidthError(fw, "hsimd_signmask");
659    Value * a1 = fwCast(fw, a);
660    Value * mask = CreateICmpSLT(a1, ConstantAggregateZero::get(a1->getType()));
661    mask = CreateBitCast(mask, getIntNTy(mBitBlockWidth/fw));
662    if (mBitBlockWidth/fw < 32) return CreateZExt(mask, getInt32Ty());
663    else return mask;
664}
665
666Value * IDISA_Builder::mvmd_extract(unsigned fw, Value * a, unsigned fieldIndex) {
667    if (fw < 8) {
668        unsigned byte_no = (fieldIndex * fw) / 8;
669        unsigned intrabyte_shift = (fieldIndex * fw) % 8;
670        Value * byte = CreateExtractElement(fwCast(8, a), getInt32(byte_no));
671        return CreateTrunc(CreateLShr(byte, getInt8(intrabyte_shift)), getIntNTy(fw));
672    }
673    return CreateExtractElement(fwCast(fw, a), getInt32(fieldIndex));
674}
675
676Value * IDISA_Builder::mvmd_insert(unsigned fw, Value * a, Value * elt, unsigned fieldIndex) {
677    if (fw < 8) {
678        unsigned byte_no = (fieldIndex * fw) / 8;
679        unsigned intrabyte_shift = (fieldIndex * fw) % 8;
680        unsigned field_mask = ((1 << fw) - 1) << intrabyte_shift;
681        Value * byte = CreateAnd(CreateExtractElement(fwCast(8, a), getInt32(byte_no)), getInt8(0xFF &~ field_mask));
682        byte = CreateOr(byte, CreateShl(CreateZExtOrTrunc(elt, getInt8Ty()), getInt8(intrabyte_shift)));
683        return CreateInsertElement(fwCast(8, a), byte, getInt32(byte_no));
684    }
685    return CreateInsertElement(fwCast(fw, a), elt, getInt32(fieldIndex));
686}
687
688Value * IDISA_Builder::mvmd_slli(unsigned fw, Value * a, unsigned shift) {
689    if (fw < 8) UnsupportedFieldWidthError(fw, "mvmd_slli");
690    Value * a1 = fwCast(fw, a);
691    Value * shifted = mvmd_dslli(fw, a1, Constant::getNullValue(a1->getType()), shift);
692    return shifted;
693}
694
695Value * IDISA_Builder::mvmd_srli(unsigned fw, Value * a, unsigned shift) {
696    if (fw < 8) UnsupportedFieldWidthError(fw, "mvmd_srli");
697    const auto field_count = getVectorBitWidth(a) / fw;
698    Value * a1 = fwCast(fw, a);
699    return mvmd_dslli(fw, Constant::getNullValue(a1->getType()), a1, field_count - shift);
700}
701
702Value * IDISA_Builder::mvmd_dslli(unsigned fw, Value * a, Value * b, unsigned shift) {
703    if (fw < 8) UnsupportedFieldWidthError(fw, "mvmd_dslli");
704    const auto field_count = getVectorBitWidth(a) / fw;
705    Constant * Idxs[field_count];
706    for (unsigned i = 0; i < field_count; i++) {
707        Idxs[i] = getInt32(i + field_count - shift);
708    }
709    return CreateShuffleVector(fwCast(fw, b), fwCast(fw, a), ConstantVector::get({Idxs, field_count}));
710}
711
712Value * IDISA_Builder::mvmd_shuffle(unsigned fw, Value * table, Value * index_vector) {
713    UnsupportedFieldWidthError(fw, "mvmd_shuffle");
714}
715   
716Value * IDISA_Builder::mvmd_shuffle2(unsigned fw, Value * table0, Value * table1, Value * index_vector) {
717    //  Use two shuffles, with selection by the bit value within the shuffle_table.
718    const auto field_count = mBitBlockWidth/fw;
719    Constant * selectorSplat = ConstantVector::getSplat(field_count, ConstantInt::get(getIntNTy(fw), field_count));
720    Value * selectMask = simd_eq(fw, simd_and(index_vector, selectorSplat), selectorSplat);
721    Value * idx = simd_and(index_vector, simd_not(selectorSplat));
722    Value * rslt= simd_or(simd_and(mvmd_shuffle(fw, table0, idx), simd_not(selectMask)), simd_and(mvmd_shuffle(fw, table1, idx), selectMask));
723    return rslt;
724}
725   
726
727Value * IDISA_Builder::mvmd_compress(unsigned fw, Value * a, Value * select_mask) {
728    UnsupportedFieldWidthError(fw, "mvmd_compress");
729}
730
731Value * IDISA_Builder::bitblock_any(Value * a) {
732    Type * iBitBlock = getIntNTy(getVectorBitWidth(a));
733    return CreateICmpNE(CreateBitCast(a, iBitBlock),  ConstantInt::getNullValue(iBitBlock));
734}
735
736// full add producing {carryout, sum}
737std::pair<Value *, Value *> IDISA_Builder::bitblock_add_with_carry(Value * a, Value * b, Value * carryin) {
738    Value * carrygen = simd_and(a, b);
739    Value * carryprop = simd_or(a, b);
740    Value * sum = simd_add(mBitBlockWidth, simd_add(mBitBlockWidth, a, b), carryin);
741    Value * carryout = CreateBitCast(simd_or(carrygen, simd_and(carryprop, CreateNot(sum))), getIntNTy(mBitBlockWidth));
742    return std::pair<Value *, Value *>(bitCast(simd_srli(mBitBlockWidth, carryout, mBitBlockWidth - 1)), bitCast(sum));
743}
744
745// full shift producing {shiftout, shifted}
746std::pair<Value *, Value *> IDISA_Builder::bitblock_advance(Value * a, Value * shiftin, unsigned shift) {
747    Value * shiftin_bitblock = CreateBitCast(shiftin, getIntNTy(mBitBlockWidth));
748    Value * a_bitblock = CreateBitCast(a, getIntNTy(mBitBlockWidth));
749    Value * shifted = bitCast(CreateOr(CreateShl(a_bitblock, shift), shiftin_bitblock));
750    Value * shiftout = bitCast(CreateLShr(a_bitblock, mBitBlockWidth - shift));
751    return std::pair<Value *, Value *>(shiftout, shifted);
752}
753
754// full shift producing {shiftout, shifted}
755std::pair<Value *, Value *> IDISA_Builder::bitblock_indexed_advance(Value * strm, Value * index_strm, Value * shiftIn, unsigned shiftAmount) {
756    const unsigned bitWidth = getSizeTy()->getBitWidth();
757    Type * const iBitBlock = getIntNTy(getBitBlockWidth());
758    Value * const shiftVal = getSize(shiftAmount);
759    Value * extracted_bits = simd_pext(bitWidth, strm, index_strm);
760    Value * ix_popcounts = simd_popcount(bitWidth, index_strm);
761    const auto n = getBitBlockWidth() / bitWidth;
762    VectorType * const vecTy = VectorType::get(getSizeTy(), n);
763    if (LLVM_LIKELY(shiftAmount < bitWidth)) {
764        Value * carry = mvmd_extract(bitWidth, shiftIn, 0);
765        Value * result = UndefValue::get(vecTy);
766        for (unsigned i = 0; i < n; i++) {
767            Value * ix_popcnt = mvmd_extract(bitWidth, ix_popcounts, i);
768            Value * bits = mvmd_extract(bitWidth, extracted_bits, i);
769            Value * adv = CreateOr(CreateShl(bits, shiftAmount), carry);
770            // We have two cases depending on whether the popcount of the index pack is < shiftAmount or not.
771            Value * popcount_small = CreateICmpULT(ix_popcnt, shiftVal);
772            Value * carry_if_popcount_small =
773                CreateOr(CreateShl(bits, CreateSub(shiftVal, ix_popcnt)),
774                            CreateLShr(carry, ix_popcnt));
775            Value * carry_if_popcount_large = CreateLShr(bits, CreateSub(ix_popcnt, shiftVal));
776            carry = CreateSelect(popcount_small, carry_if_popcount_small, carry_if_popcount_large);
777            result = mvmd_insert(bitWidth, result, adv, i);
778        }
779        Value * carryOut = mvmd_insert(bitWidth, allZeroes(), carry, 0);
780        return std::pair<Value *, Value *>{bitCast(carryOut), simd_pdep(bitWidth, result, index_strm)};
781    }
782    else if (shiftAmount <= mBitBlockWidth) {
783        // The shift amount is always greater than the popcount of the individual
784        // elements that we deal with.   This simplifies some of the logic.
785        Value * carry = CreateBitCast(shiftIn, iBitBlock);
786        Value * result = UndefValue::get(vecTy);
787        for (unsigned i = 0; i < n; i++) {
788            Value * ix_popcnt = mvmd_extract(bitWidth, ix_popcounts, i);
789            Value * bits = mvmd_extract(bitWidth, extracted_bits, i);  // All these bits are shifted out (appended to carry).
790            result = mvmd_insert(bitWidth, result, mvmd_extract(bitWidth, carry, 0), i);
791            carry = CreateLShr(carry, CreateZExt(ix_popcnt, iBitBlock)); // Remove the carry bits consumed, make room for new bits.
792            carry = CreateOr(carry, CreateShl(CreateZExt(bits, iBitBlock), CreateZExt(CreateSub(shiftVal, ix_popcnt), iBitBlock)));
793        }
794        return std::pair<Value *, Value *>{bitCast(carry), simd_pdep(bitWidth, result, index_strm)};
795    }
796    else {
797        // The shift amount is greater than the total popcount.   We will consume popcount
798        // bits from the shiftIn value only, and produce a carry out value of the selected bits.
799        Value * carry = CreateBitCast(shiftIn, iBitBlock);
800        Value * result = UndefValue::get(vecTy);
801        Value * carryOut = ConstantInt::getNullValue(iBitBlock);
802        Value * generated = getSize(0);
803        for (unsigned i = 0; i < n; i++) {
804            Value * ix_popcnt = mvmd_extract(bitWidth, ix_popcounts, i);
805            Value * bits = mvmd_extract(bitWidth, extracted_bits, i);  // All these bits are shifted out (appended to carry).
806            result = mvmd_insert(bitWidth, result, mvmd_extract(bitWidth, carry, 0), i);
807            carry = CreateLShr(carry, CreateZExt(ix_popcnt, iBitBlock)); // Remove the carry bits consumed.
808            carryOut = CreateOr(carryOut, CreateShl(CreateZExt(bits, iBitBlock), CreateZExt(generated, iBitBlock)));
809            generated = CreateAdd(generated, ix_popcnt);
810        }
811        return std::pair<Value *, Value *>{bitCast(carryOut), simd_pdep(bitWidth, result, index_strm)};
812    }
813}
814
815Value * IDISA_Builder::bitblock_mask_from(Value * const position, const bool safe) {
816    Value * const originalPos = CreateZExtOrTrunc(position, getSizeTy());
817    if (LLVM_UNLIKELY(safe && codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
818        Constant * const BLOCK_WIDTH = getSize(mBitBlockWidth);
819        CreateAssert(CreateICmpULT(originalPos, BLOCK_WIDTH), "position exceeds block width");
820    }
821    Value * const pos = safe ? position : CreateAnd(originalPos, getSize(mBitBlockWidth - 1));
822    const unsigned fieldWidth = getSizeTy()->getBitWidth();
823    const auto fieldCount = mBitBlockWidth / fieldWidth;
824    Constant * posBase[fieldCount];
825    for (unsigned i = 0; i < fieldCount; i++) {
826        posBase[i] = ConstantInt::get(getSizeTy(), fieldWidth * i);
827    }
828    Value * const posBaseVec = ConstantVector::get({posBase, fieldCount});
829    Value * const positionVec = simd_fill(fieldWidth, pos);
830    Value * const fullFieldWidthMasks = CreateSExt(CreateICmpUGT(posBaseVec, positionVec), fwVectorType(fieldWidth));
831    Constant * const FIELD_ONES = ConstantInt::getAllOnesValue(getSizeTy());
832    Value * const bitField = CreateShl(FIELD_ONES, CreateAnd(pos, getSize(fieldWidth - 1)));
833    Value * const fieldNo = CreateLShr(pos, getSize(std::log2(fieldWidth)));   
834    Value * result = CreateInsertElement(fullFieldWidthMasks, bitField, fieldNo);
835    if (!safe) { // if the originalPos doesn't match the moddedPos then the originalPos must exceed the block width.
836        Constant * const VECTOR_ZEROES = Constant::getNullValue(fwVectorType(fieldWidth));
837        result = CreateSelect(CreateICmpEQ(originalPos, pos), result, VECTOR_ZEROES);
838    }
839    return bitCast(result);
840}
841
842Value * IDISA_Builder::bitblock_mask_to(Value * const position, const bool safe) {
843    Value * const originalPos = CreateZExtOrTrunc(position, getSizeTy());
844    if (LLVM_UNLIKELY(safe && codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
845        Constant * const BLOCK_WIDTH = getSize(mBitBlockWidth);
846        CreateAssert(CreateICmpULT(originalPos, BLOCK_WIDTH), "position exceeds block width");
847    }
848    Value * const pos = safe ? position : CreateAnd(originalPos, getSize(mBitBlockWidth - 1));
849    const unsigned fieldWidth = getSizeTy()->getBitWidth();
850    const auto fieldCount = mBitBlockWidth / fieldWidth;
851    Constant * posBase[fieldCount];
852    for (unsigned i = 0; i < fieldCount; i++) {
853        posBase[i] = ConstantInt::get(getSizeTy(), fieldWidth * i);
854    }
855    Value * const posBaseVec = ConstantVector::get({posBase, fieldCount});
856    Value * const positionVec = simd_fill(fieldWidth, pos);
857    Value * const fullFieldWidthMasks = CreateSExt(CreateICmpULT(posBaseVec, positionVec), fwVectorType(fieldWidth));
858    Constant * const FIELD_ONES = ConstantInt::getAllOnesValue(getSizeTy());
859    Value * const bitField = CreateLShr(FIELD_ONES, CreateAnd(getSize(fieldWidth - 1), CreateNot(pos)));
860    Value * const fieldNo = CreateLShr(pos, getSize(std::log2(fieldWidth)));
861    Value * result = CreateInsertElement(fullFieldWidthMasks, bitField, fieldNo);
862    if (!safe) { // if the originalPos doesn't match the moddedPos then the originalPos must exceed the block width.
863        Constant * const VECTOR_ONES = Constant::getAllOnesValue(fwVectorType(fieldWidth));
864        result = CreateSelect(CreateICmpEQ(originalPos, pos), result, VECTOR_ONES);
865    }
866    return bitCast(result);
867}
868
869Value * IDISA_Builder::bitblock_set_bit(Value * const position, const bool safe) {
870    Value * const originalPos = CreateZExtOrTrunc(position, getSizeTy());
871    if (LLVM_UNLIKELY(safe && codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
872        Constant * const BLOCK_WIDTH = getSize(mBitBlockWidth);
873        CreateAssert(CreateICmpULT(originalPos, BLOCK_WIDTH), "position exceeds block width");
874    }
875    const unsigned fieldWidth = getSizeTy()->getBitWidth();
876    Value * const bitField = CreateShl(getSize(1), CreateAnd(originalPos, getSize(fieldWidth - 1)));
877    Value * const pos = safe ? position : CreateAnd(originalPos, getSize(mBitBlockWidth - 1));
878    Value * const fieldNo = CreateLShr(pos, getSize(std::log2(fieldWidth)));
879    Constant * const VECTOR_ZEROES = Constant::getNullValue(fwVectorType(fieldWidth));
880    Value * result = CreateInsertElement(VECTOR_ZEROES, bitField, fieldNo);
881    if (!safe) { // If the originalPos doesn't match the moddedPos then the originalPos must exceed the block width.
882        result = CreateSelect(CreateICmpEQ(originalPos, pos), result, VECTOR_ZEROES);
883    }
884    return bitCast(result);
885}
886
887Value * IDISA_Builder::bitblock_popcount(Value * const to_count) {
888    const auto fieldWidth = getSizeTy()->getBitWidth();
889    auto fields = (getBitBlockWidth() / fieldWidth);
890    Value * fieldCounts = simd_popcount(fieldWidth, to_count);
891    while (fields > 1) {
892        fields /= 2;
893        fieldCounts = CreateAdd(fieldCounts, mvmd_srli(fieldWidth, fieldCounts, fields));
894    }
895    return mvmd_extract(fieldWidth, fieldCounts, 0);
896}
897
898Value * IDISA_Builder::simd_and(Value * a, Value * b, StringRef s) {
899    return a->getType() == b->getType() ? CreateAnd(a, b, s) : CreateAnd(bitCast(a), bitCast(b), s);
900}
901
902Value * IDISA_Builder::simd_or(Value * a, Value * b, StringRef s) {
903    return a->getType() == b->getType() ? CreateOr(a, b, s) : CreateOr(bitCast(a), bitCast(b), s);
904}
905   
906Value * IDISA_Builder::simd_xor(Value * a, Value * b, StringRef s) {
907    return a->getType() == b->getType() ? CreateXor(a, b, s) : CreateXor(bitCast(a), bitCast(b), s);
908}
909
910Value * IDISA_Builder::simd_not(Value * a, StringRef s) {
911    return simd_xor(a, Constant::getAllOnesValue(a->getType()), s);
912}
913
914Constant * IDISA_Builder::bit_interleave_byteshuffle_table(unsigned fw) {
915    const unsigned fieldCount = mNativeBitBlockWidth/8;
916    if (fw > 2) report_fatal_error("bit_interleave_byteshuffle_table requires fw == 1 or fw == 2");
917    // Bit interleave using shuffle.
918    // Make a shuffle table that translates the lower 4 bits of each byte in
919    // order to spread out the bits: xxxxdcba => .d.c.b.a (fw = 1)
920    Constant * bit_interleave[fieldCount];
921    for (unsigned i = 0; i < fieldCount; i++) {
922        if (fw == 1)
923            bit_interleave[i] = getInt8((i & 1) | ((i & 2) << 1) | ((i & 4) << 2) | ((i & 8) << 3));
924        else bit_interleave[i] = getInt8((i & 3) | ((i & 0x0C) << 2));
925    }
926    return ConstantVector::get({bit_interleave, fieldCount});
927}
928
929IDISA_Builder::IDISA_Builder(LLVMContext & C, unsigned nativeVectorWidth, unsigned vectorWidth, unsigned laneWidth)
930: CBuilder(C)
931, mNativeBitBlockWidth(nativeVectorWidth)
932, mBitBlockWidth(vectorWidth)
933, mLaneWidth(laneWidth)
934, mBitBlockType(VectorType::get(IntegerType::get(C, mLaneWidth), vectorWidth / mLaneWidth))
935, mZeroInitializer(Constant::getNullValue(mBitBlockType))
936, mOneInitializer(Constant::getAllOnesValue(mBitBlockType))
937, mPrintRegisterFunction(nullptr) {
938
939}
940
941IDISA_Builder::~IDISA_Builder() {
942
943}
944
945}
Note: See TracBrowser for help on using the repository browser.