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

Last change on this file since 6046 was 6046, checked in by cameron, 15 months ago

Some fixes

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