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

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

esimd_mergel 4 argument order fix

File size: 37.0 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_ule(unsigned fw, Value * a, Value * b) {
143    if (fw == 1) return simd_or(simd_not(a), b);
144    if (fw < 8) {
145        Value * hi_rslt = simd_and(simd_himask(2*fw), simd_ule(2*fw, simd_and(simd_himask(2*fw), a), b));
146        Value * lo_rslt = simd_and(simd_lomask(2*fw), simd_ule(2*fw, simd_and(simd_lomask(2*fw), a), simd_and(simd_lomask(2*fw), b)));
147        return simd_or(hi_rslt, lo_rslt);
148    }
149    return CreateSExt(CreateICmpULE(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
150}
151
152Value * IDISA_Builder::simd_uge(unsigned fw, Value * a, Value * b) {
153    if (fw == 1) return simd_or(a, simd_not(b));
154    if (fw < 8) {
155        Value * hi_rslt = simd_and(simd_himask(2*fw), simd_uge(2*fw, a, simd_and(simd_himask(2*fw), b)));
156        Value * lo_rslt = simd_and(simd_lomask(2*fw), simd_uge(2*fw, simd_and(simd_lomask(2*fw), a), simd_and(simd_lomask(2*fw), b)));
157        return simd_or(hi_rslt, lo_rslt);
158    }
159    if (fw < 8) report_fatal_error("Unsupported field width: ult " + std::to_string(fw));
160    return CreateSExt(CreateICmpUGE(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
161}
162
163Value * IDISA_Builder::simd_max(unsigned fw, Value * a, Value * b) {
164    if (fw < 8) report_fatal_error("Unsupported field width: max " + std::to_string(fw));
165    Value * aVec = fwCast(fw, a);
166    Value * bVec = fwCast(fw, b);
167    return CreateSelect(CreateICmpSGT(aVec, bVec), aVec, bVec);
168}
169
170Value * IDISA_Builder::simd_umax(unsigned fw, Value * a, Value * b) {
171    if (fw == 1) return simd_or(a, b);
172    if (fw < 8) {
173        Value * hi_rslt = simd_and(simd_himask(2*fw), simd_umax(2*fw, a, b));
174        Value * lo_rslt = simd_umax(2*fw, simd_and(simd_lomask(2*fw), a), simd_and(simd_lomask(2*fw), b));
175        return simd_or(hi_rslt, lo_rslt);
176    }
177    Value * aVec = fwCast(fw, a);
178    Value * bVec = fwCast(fw, b);
179    return CreateSelect(CreateICmpUGT(aVec, bVec), aVec, bVec);
180}
181
182Value * IDISA_Builder::simd_min(unsigned fw, Value * a, Value * b) {
183    if (fw < 8) report_fatal_error("Unsupported field width: min " + std::to_string(fw));
184    Value * aVec = fwCast(fw, a);
185    Value * bVec = fwCast(fw, b);
186    return CreateSelect(CreateICmpSLT(aVec, bVec), aVec, bVec);
187}
188
189Value * IDISA_Builder::simd_umin(unsigned fw, Value * a, Value * b) {
190    if (fw == 1) return simd_and(a, b);
191    if (fw < 8) {
192        Value * hi_rslt = simd_and(simd_himask(2*fw), simd_umin(2*fw, a, b));
193        Value * lo_rslt = simd_umin(2*fw, simd_and(simd_lomask(2*fw), a), simd_and(simd_lomask(2*fw), b));
194        return simd_or(hi_rslt, lo_rslt);
195    }
196    Value * aVec = fwCast(fw, a);
197    Value * bVec = fwCast(fw, b);
198    return CreateSelect(CreateICmpULT(aVec, bVec), aVec, bVec);
199}
200
201Value * IDISA_Builder::mvmd_sll(unsigned fw, Value * value, Value * shift) {
202    VectorType * const vecTy = cast<VectorType>(value->getType());
203    IntegerType * const intTy = getIntNTy(vecTy->getBitWidth());
204    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
205        Type * const ty = shift->getType();
206        Value * const scaled = CreateMul(shift, ConstantInt::get(ty, fw));
207        Value * const inbounds = CreateICmpULE(scaled, ConstantInt::get(ty, vecTy->getBitWidth()));
208        CreateAssert(inbounds, "shift exceeds vector width");
209    }
210    value = CreateBitCast(value, intTy);
211    shift = CreateZExtOrTrunc(CreateMul(shift, ConstantInt::get(shift->getType(), fw)), intTy);
212    return CreateBitCast(CreateShl(value, shift), vecTy);
213}
214
215Value * IDISA_Builder::mvmd_dsll(unsigned fw, Value * a, Value * b, Value * shift) {
216    if (fw < 8) report_fatal_error("Unsupported field width: mvmd_dsll " + std::to_string(fw));
217    const auto field_count = mBitBlockWidth/fw;
218    Type * fwTy = getIntNTy(fw);
219   
220    Constant * Idxs[field_count];
221    for (unsigned i = 0; i < field_count; i++) {
222        Idxs[i] = ConstantInt::get(fwTy, i + field_count);
223    }
224    Value * shuffle = simd_sub(fw, ConstantVector::get({Idxs, field_count}), simd_fill(fw, shift));
225    Value * rslt = mvmd_shuffle2(fw, fwCast(fw, a), fwCast(fw, b), shuffle);
226    return rslt;
227}
228
229Value * IDISA_Builder::mvmd_srl(unsigned fw, Value * value, Value * shift) {
230    VectorType * const vecTy = cast<VectorType>(value->getType());
231    IntegerType * const intTy = getIntNTy(vecTy->getBitWidth());
232    if (LLVM_UNLIKELY(codegen::DebugOptionIsSet(codegen::EnableAsserts))) {
233        Type * const ty = shift->getType();
234        Value * const scaled = CreateMul(shift, ConstantInt::get(ty, fw));
235        Value * const inbounds = CreateICmpULE(scaled, ConstantInt::get(ty, vecTy->getBitWidth()));
236        CreateAssert(inbounds, "shift exceeds vector width");
237    }
238    value = CreateBitCast(value, intTy);
239    shift = CreateZExtOrTrunc(CreateMul(shift, ConstantInt::get(shift->getType(), fw)), intTy);
240    return CreateBitCast(CreateLShr(value, shift), vecTy);
241}
242
243Value * IDISA_Builder::simd_slli(unsigned fw, Value * a, unsigned shift) {
244    if (fw < 16) {
245        Constant * value_mask = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
246                                                          APInt::getSplat(mBitBlockWidth, APInt::getLowBitsSet(fw, fw-shift)));
247        return CreateShl(fwCast(32, simd_and(a, value_mask)), shift);
248    }
249    return CreateShl(fwCast(fw, a), shift);
250}
251
252Value * IDISA_Builder::simd_srli(unsigned fw, Value * a, unsigned shift) {
253    if (fw < 16) {
254        Constant * value_mask = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
255                                                          APInt::getSplat(mBitBlockWidth, APInt::getHighBitsSet(fw, fw-shift)));
256        return CreateLShr(fwCast(32, simd_and(a, value_mask)), shift);
257    }
258    return CreateLShr(fwCast(fw, a), shift);
259}
260
261Value * IDISA_Builder::simd_srai(unsigned fw, Value * a, unsigned shift) {
262    if (fw < 8) report_fatal_error("Unsupported field width: srai " + std::to_string(fw));
263    return CreateAShr(fwCast(fw, a), shift);
264}
265   
266Value * IDISA_Builder::simd_sllv(unsigned fw, Value * v, Value * shifts) {
267    if (fw >= 8) return CreateShl(fwCast(fw, v), fwCast(fw, shifts));
268    Value * w = v;
269    for (unsigned shft_amt = 1; shft_amt < fw; shft_amt *= 2) {
270        APInt bit_in_field(fw, shft_amt);
271        // To simulate shift within a fw, we need to mask off the high shft_amt bits of each element.
272        Constant * value_mask = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
273                                                          APInt::getSplat(mBitBlockWidth, APInt::getLowBitsSet(fw, fw-shft_amt)));
274        Constant * bit_select = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
275                                                          APInt::getSplat(mBitBlockWidth, bit_in_field));
276        Value * unshifted_field_mask = simd_eq(fw, simd_and(bit_select, shifts), allZeroes());
277        Value * fieldsToShift = simd_and(w, simd_and(value_mask, simd_not(unshifted_field_mask)));
278        w = simd_or(simd_and(w, unshifted_field_mask), simd_slli(32, fieldsToShift, shft_amt));
279    }
280    return w;
281}
282
283Value * IDISA_Builder::simd_srlv(unsigned fw, Value * v, Value * shifts) {
284    if (fw >= 8) return CreateLShr(fwCast(fw, v), fwCast(fw, shifts));
285    Value * w = v;
286    for (unsigned shft_amt = 1; shft_amt < fw; shft_amt *= 2) {
287        APInt bit_in_field(fw, shft_amt);
288        // To simulate shift within a fw, we need to mask off the low shft_amt bits of each element.
289        Constant * value_mask = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
290                                                          APInt::getSplat(mBitBlockWidth, APInt::getHighBitsSet(fw, fw-shft_amt)));
291        Constant * bit_select = Constant::getIntegerValue(getIntNTy(mBitBlockWidth),
292                                                          APInt::getSplat(mBitBlockWidth, bit_in_field));
293        Value * unshifted_field_mask = simd_eq(fw, simd_and(bit_select, shifts), allZeroes());
294        Value * fieldsToShift = simd_and(w, simd_and(value_mask, simd_not(unshifted_field_mask)));
295        w = simd_or(simd_and(w, unshifted_field_mask), simd_srli(32, fieldsToShift, shft_amt));
296    }
297    return w;
298}
299
300Value * IDISA_Builder::simd_pext(unsigned fieldwidth, Value * v, Value * extract_mask) {
301    Value * delcounts = CreateNot(extract_mask);  // initially deletion counts per 1-bit field
302    Value * w = simd_and(extract_mask, v);
303    for (unsigned fw = 2; fw < fieldwidth; fw = fw * 2) {
304        Value * shift_fwd_field_mask = simd_lomask(fw*2);
305        Value * shift_back_field_mask = simd_himask(fw*2);
306        Value * shift_back_count_mask = simd_and(shift_back_field_mask, simd_lomask(fw));
307        Value * shift_fwd_amts = simd_srli(fw, simd_and(shift_fwd_field_mask, delcounts), fw/2);
308        Value * shift_back_amts = simd_and(shift_back_count_mask, delcounts);
309        w = simd_or(simd_sllv(fw, simd_and(w, shift_fwd_field_mask), shift_fwd_amts),
310                    simd_srlv(fw, simd_and(w, shift_back_field_mask), shift_back_amts));
311        delcounts = simd_add(fw, simd_and(simd_lomask(fw), delcounts), simd_srli(fw, delcounts, fw/2));
312    }
313    // Now shift back all fw fields.
314    Value * shift_back_amts = simd_and(simd_lomask(fieldwidth), delcounts);
315    w = simd_srlv(fieldwidth, w, shift_back_amts);
316    return w;
317}
318
319Value * IDISA_Builder::simd_pdep(unsigned fieldwidth, Value * v, Value * deposit_mask) {
320    // simd_pdep is implemented by reversing the process of simd_pext.
321    // First determine the deletion counts necessary for each stage of the process.
322    std::vector<Value *> delcounts;
323    delcounts.push_back(simd_not(deposit_mask)); // initially deletion counts per 1-bit field
324    for (unsigned fw = 2; fw < fieldwidth; fw = fw * 2) {
325        delcounts.push_back(simd_add(fw, simd_and(simd_lomask(fw), delcounts.back()), simd_srli(fw, delcounts.back(), fw/2)));
326    }
327    //
328    // Now reverse the pext process.  First reverse the final shift_back.
329    Value * pext_shift_back_amts = simd_and(simd_lomask(fieldwidth), delcounts.back());
330    Value * w = simd_sllv(fieldwidth, v, pext_shift_back_amts);
331    //
332    // No work through the smaller field widths.
333    for (unsigned fw = fieldwidth/2; fw >= 2; fw = fw/2) {
334        delcounts.pop_back();
335        Value * pext_shift_fwd_field_mask = simd_lomask(fw*2);
336        Value * pext_shift_back_field_mask = simd_himask(fw*2);
337        Value * pext_shift_back_count_mask = simd_and(pext_shift_back_field_mask, simd_lomask(fw));
338        Value * pext_shift_fwd_amts = simd_srli(fw, simd_and(pext_shift_fwd_field_mask, delcounts.back()), fw/2);
339        Value * pext_shift_back_amts = simd_and(pext_shift_back_count_mask, delcounts.back());
340        w = simd_or(simd_srlv(fw, simd_and(w, pext_shift_fwd_field_mask), pext_shift_fwd_amts),
341                    simd_sllv(fw, simd_and(w, pext_shift_back_field_mask), pext_shift_back_amts));
342    }
343    return CreateAnd(w, deposit_mask);
344}
345
346Value * IDISA_Builder::simd_popcount(unsigned fw, Value * a) {
347    if (fw == 1) {
348        return a;
349    } else if (fw == 2) {
350        // For each 2-bit field ab we can use the subtraction ab - 0a to generate
351        // the popcount without carry/borrow from the neighbouring 2-bit field.
352        // case 00:  ab - 0a = 00 - 00 = 00
353        // case 01:  ab - 0a = 01 - 00 = 01
354        // case 10:  ab - 0a = 10 - 01 = 01 (no borrow)
355        // case 11:  ab - 0a = 11 - 01 = 10
356        return simd_sub(64, a, simd_srli(64, simd_and(simd_himask(2), a), 1));
357    } else if (fw <= 8) {
358        Value * c = simd_popcount(fw/2, a);
359        c = simd_add(64, simd_and(c, simd_lomask(fw)), simd_srli(fw, c, fw/2));
360        return c;
361    } else {
362        return CreatePopcount(fwCast(fw, a));
363    }
364}
365
366Value * IDISA_Builder::simd_bitreverse(unsigned fw, Value * a) {
367    /*  Pure sequential solution too slow!
368     Value * func = Intrinsic::getDeclaration(getModule(), Intrinsic::bitreverse, fwVectorType(fw));
369     return CreateCall(func, fwCast(fw, a));
370     */
371    if (fw > 8) {
372        // Reverse the bits of each byte and then use a byte shuffle to complete the job.
373        Value * bitrev8 = fwCast(8, simd_bitreverse(8, a));
374        const auto bytes_per_field = fw/8;
375        const auto byte_count = mBitBlockWidth / 8;
376        Constant * Idxs[byte_count];
377        for (unsigned i = 0; i < byte_count; i += bytes_per_field) {
378            for (unsigned j = 0; j < bytes_per_field; j++) {
379                Idxs[i + j] = getInt32(i + bytes_per_field - j - 1);
380            }
381        }
382        return CreateShuffleVector(bitrev8, UndefValue::get(fwVectorType(8)), ConstantVector::get({Idxs, byte_count}));
383    }
384    else {
385        if (fw > 2) {
386            a = simd_bitreverse(fw/2, a);
387        }
388        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));
389    }
390}
391
392Value * IDISA_Builder::simd_if(unsigned fw, Value * cond, Value * a, Value * b) {
393    if (fw == 1) {
394        Value * a1 = bitCast(a);
395        Value * b1 = bitCast(b);
396        Value * c = bitCast(cond);
397        return CreateOr(CreateAnd(a1, c), CreateAnd(CreateXor(c, b1), b1));
398    } else {
399        if (fw < 8) report_fatal_error("Unsupported field width: simd_if " + std::to_string(fw));
400        Value * aVec = fwCast(fw, a);
401        Value * bVec = fwCast(fw, b);
402        return CreateSelect(CreateICmpSLT(cond, mZeroInitializer), aVec, bVec);
403    }
404}
405   
406Value * IDISA_Builder::esimd_mergeh(unsigned fw, Value * a, Value * b) {   
407    if (fw == 4) {
408        Value * abh = simd_or(simd_and(simd_himask(fw*2), b), simd_srli(32, simd_and(simd_himask(fw*2), a), fw));
409        Value * abl = simd_or(simd_slli(32, simd_and(simd_lomask(fw*2), b), fw), simd_and(simd_lomask(fw*2), a));
410        return esimd_mergeh(fw * 2, abl, abh);
411    }
412    if (fw < 4) report_fatal_error("Unsupported field width: mergeh " + std::to_string(fw));
413    const auto field_count = mBitBlockWidth / fw;
414    Constant * Idxs[field_count];
415    for (unsigned i = 0; i < field_count / 2; i++) {
416        Idxs[2 * i] = getInt32(i + field_count / 2); // selects elements from first reg.
417        Idxs[2 * i + 1] = getInt32(i + field_count / 2 + field_count); // selects elements from second reg.
418    }
419    return CreateShuffleVector(fwCast(fw, a), fwCast(fw, b), ConstantVector::get({Idxs, field_count}));
420}
421
422Value * IDISA_Builder::esimd_mergel(unsigned fw, Value * a, Value * b) {
423    if (fw == 4) {
424        Value * abh = simd_or(simd_and(simd_himask(fw*2), b), simd_srli(32, simd_and(simd_himask(fw*2), a), fw));
425        Value * abl = simd_or(simd_slli(32, simd_and(simd_lomask(fw*2), b), fw), simd_and(simd_lomask(fw*2), a));
426        return esimd_mergel(fw * 2, abl, abh);
427    }
428    if (fw < 4) report_fatal_error("Unsupported field width: mergel " + std::to_string(fw));
429    const auto field_count = mBitBlockWidth / fw;
430    Constant * Idxs[field_count];
431    for (unsigned i = 0; i < field_count / 2; i++) {
432        Idxs[2 * i] = getInt32(i); // selects elements from first reg.
433        Idxs[2 * i + 1] = getInt32(i + field_count); // selects elements from second reg.
434    }
435    return CreateShuffleVector(fwCast(fw, a), fwCast(fw, b), ConstantVector::get({Idxs, field_count}));
436}
437
438Value * IDISA_Builder::esimd_bitspread(unsigned fw, Value * bitmask) {
439    if (fw < 8) report_fatal_error("Unsupported field width: bitspread " + std::to_string(fw));
440    const auto field_count = mBitBlockWidth / fw;
441    Type * field_type = getIntNTy(fw);
442    Value * spread_field = CreateBitCast(CreateZExtOrTrunc(bitmask, field_type), VectorType::get(getIntNTy(fw), 1));
443    Value * undefVec = UndefValue::get(VectorType::get(getIntNTy(fw), 1));
444    Value * broadcast = CreateShuffleVector(spread_field, undefVec, Constant::getNullValue(VectorType::get(getInt32Ty(), field_count)));
445    Constant * bitSel[field_count];
446    Constant * bitShift[field_count];
447    for (unsigned i = 0; i < field_count; i++) {
448        bitSel[i] = ConstantInt::get(field_type, 1 << i);
449        bitShift[i] = ConstantInt::get(field_type, i);
450    }
451    Value * bitSelVec = ConstantVector::get({bitSel, field_count});
452    Value * bitShiftVec = ConstantVector::get({bitShift, field_count});
453    return CreateLShr(CreateAnd(bitSelVec, broadcast), bitShiftVec);
454}
455
456Value * IDISA_Builder::hsimd_packh(unsigned fw, Value * a, Value * b) {
457    if (fw <= 8) {
458        const unsigned fw_wkg = 32;
459        Value * aLo = simd_srli(fw_wkg, a, fw/2);
460        Value * bLo = simd_srli(fw_wkg, b, fw/2);
461        return hsimd_packl(fw, aLo, bLo);
462    }
463    Value * aVec = fwCast(fw/2, a);
464    Value * bVec = fwCast(fw/2, b);
465    const auto field_count = 2 * mBitBlockWidth / fw;
466    Constant * Idxs[field_count];
467    for (unsigned i = 0; i < field_count; i++) {
468        Idxs[i] = getInt32(2 * i + 1);
469    }
470    return CreateShuffleVector(aVec, bVec, ConstantVector::get({Idxs, field_count}));
471}
472
473Value * IDISA_Builder::hsimd_packl(unsigned fw, Value * a, Value * b) {
474    if (fw <= 8) {
475        const unsigned fw_wkg = 32;
476        Value * aLo = simd_srli(fw_wkg, a, fw/2);
477        Value * bLo = simd_srli(fw_wkg, b, fw/2);
478        return hsimd_packl(fw*2,
479                           bitCast(simd_or(simd_and(simd_himask(fw), aLo), simd_and(simd_lomask(fw), a))),
480                           bitCast(simd_or(simd_and(simd_himask(fw), bLo), simd_and(simd_lomask(fw), b))));
481    }
482    Value * aVec = fwCast(fw/2, a);
483    Value * bVec = fwCast(fw/2, b);
484    const auto field_count = 2 * mBitBlockWidth / fw;
485    Constant * Idxs[field_count];
486    for (unsigned i = 0; i < field_count; i++) {
487        Idxs[i] = getInt32(2 * i);
488    }
489    return CreateShuffleVector(aVec, bVec, ConstantVector::get({Idxs, field_count}));
490}
491
492Value * IDISA_Builder::hsimd_packh_in_lanes(unsigned lanes, unsigned fw, Value * a, Value * b) {
493    if (fw < 16) report_fatal_error("Unsupported field width: packh_in_lanes " + std::to_string(fw));
494    const unsigned fw_out = fw / 2;
495    const unsigned fields_per_lane = mBitBlockWidth / (fw_out * lanes);
496    const unsigned field_offset_for_b = mBitBlockWidth / fw_out;
497    const unsigned field_count = mBitBlockWidth / fw_out;
498    Constant * Idxs[field_count];
499    for (unsigned lane = 0, j = 0; lane < lanes; lane++) {
500        const unsigned first_field_in_lane = lane * fields_per_lane; // every second field
501        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
502            Idxs[j++] = getInt32(first_field_in_lane + (2 * i) + 1);
503        }
504        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
505            Idxs[j++] = getInt32(field_offset_for_b + first_field_in_lane + (2 * i) + 1);
506        }
507    }
508    return CreateShuffleVector(fwCast(fw_out, a), fwCast(fw_out, b), ConstantVector::get({Idxs, field_count}));
509}
510
511Value * IDISA_Builder::hsimd_packl_in_lanes(unsigned lanes, unsigned fw, Value * a, Value * b) {
512    if (fw < 16) report_fatal_error("Unsupported field width: packl_in_lanes " + std::to_string(fw));
513    const unsigned fw_out = fw / 2;
514    const unsigned fields_per_lane = mBitBlockWidth / (fw_out * lanes);
515    const unsigned field_offset_for_b = mBitBlockWidth / fw_out;
516    const unsigned field_count = mBitBlockWidth / fw_out;
517    Constant * Idxs[field_count];
518    for (unsigned lane = 0, j = 0; lane < lanes; lane++) {
519        const unsigned first_field_in_lane = lane * fields_per_lane; // every second field
520        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
521            Idxs[j++] = getInt32(first_field_in_lane + (2 * i));
522        }
523        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
524            Idxs[j++] = getInt32(field_offset_for_b + first_field_in_lane + (2 * i));
525        }
526    }
527    return CreateShuffleVector(fwCast(fw_out, a), fwCast(fw_out, b), ConstantVector::get({Idxs, field_count}));
528}
529
530Value * IDISA_Builder::hsimd_signmask(unsigned fw, Value * a) {
531    if (fw < 8) report_fatal_error("Unsupported field width: hsimd_signmask " + std::to_string(fw));
532    Value * mask = CreateICmpSLT(fwCast(fw, a), ConstantAggregateZero::get(fwVectorType(fw)));
533    mask = CreateBitCast(mask, getIntNTy(mBitBlockWidth/fw));
534    if (mBitBlockWidth/fw < 32) return CreateZExt(mask, getInt32Ty());
535    else return mask;
536}
537
538Value * IDISA_Builder::mvmd_extract(unsigned fw, Value * a, unsigned fieldIndex) {
539    if (fw < 8) {
540        unsigned byte_no = (fieldIndex * fw) / 8;
541        unsigned intrabyte_shift = (fieldIndex * fw) % 8;
542        Value * byte = CreateExtractElement(fwCast(8, a), getInt32(byte_no));
543        return CreateTrunc(CreateLShr(byte, getInt8(intrabyte_shift)), getIntNTy(fw));
544    }
545    return CreateExtractElement(fwCast(fw, a), getInt32(fieldIndex));
546}
547
548Value * IDISA_Builder::mvmd_insert(unsigned fw, Value * a, Value * elt, unsigned fieldIndex) {
549    if (fw < 8) {
550        unsigned byte_no = (fieldIndex * fw) / 8;
551        unsigned intrabyte_shift = (fieldIndex * fw) % 8;
552        unsigned field_mask = ((1 << fw) - 1) << intrabyte_shift;
553        Value * byte = CreateAnd(CreateExtractElement(fwCast(8, a), getInt32(byte_no)), getInt8(0xFF &~ field_mask));
554        byte = CreateOr(byte, CreateShl(CreateZExtOrTrunc(elt, getInt8Ty()), getInt8(intrabyte_shift)));
555        return CreateInsertElement(fwCast(8, a), byte, getInt32(byte_no));
556    }
557    return CreateInsertElement(fwCast(fw, a), elt, getInt32(fieldIndex));
558}
559
560Value * IDISA_Builder::mvmd_slli(unsigned fw, Value * a, unsigned shift) {
561    if (fw < 8) report_fatal_error("Unsupported field width: mvmd_slli " + std::to_string(fw));
562    Value * shifted = mvmd_dslli(fw, a, Constant::getNullValue(fwVectorType(fw)), shift);
563    return shifted;
564}
565
566Value * IDISA_Builder::mvmd_srli(unsigned fw, Value * a, unsigned shift) {
567    if (fw < 8) report_fatal_error("Unsupported field width: mvmd_srli " + std::to_string(fw));
568    const auto field_count = mBitBlockWidth / fw;
569    return mvmd_dslli(fw, Constant::getNullValue(fwVectorType(fw)), a, field_count - shift);
570}
571
572Value * IDISA_Builder::mvmd_dslli(unsigned fw, Value * a, Value * b, unsigned shift) {
573    if (fw < 8) report_fatal_error("Unsupported field width: mvmd_dslli " + std::to_string(fw));
574    const auto field_count = mBitBlockWidth/fw;
575    Constant * Idxs[field_count];
576    for (unsigned i = 0; i < field_count; i++) {
577        Idxs[i] = getInt32(i + field_count - shift);
578    }
579    return CreateShuffleVector(fwCast(fw, b), fwCast(fw, a), ConstantVector::get({Idxs, field_count}));
580}
581
582Value * IDISA_Builder::mvmd_shuffle(unsigned fw, Value * a, Value * shuffle_table) {
583    report_fatal_error("Unsupported field width: mvmd_shuffle " + std::to_string(fw));
584}
585   
586Value * IDISA_Builder::mvmd_shuffle2(unsigned fw, Value * a, Value *b, Value * shuffle_table) {
587    //  Use two shuffles, with selection by the bit value within the shuffle_table.
588    const auto field_count = mBitBlockWidth/fw;
589    Constant * selectorSplat = ConstantVector::getSplat(field_count, ConstantInt::get(getIntNTy(fw), field_count));
590    Value * selectMask = simd_eq(fw, simd_and(shuffle_table, selectorSplat), selectorSplat);
591    Value * tbl = simd_and(shuffle_table, simd_not(selectorSplat));
592    Value * rslt= simd_or(simd_and(mvmd_shuffle(fw, a, tbl), simd_not(selectMask)), simd_and(mvmd_shuffle(fw, b, tbl), selectMask));
593    return rslt;
594}
595   
596
597llvm::Value * IDISA_Builder::mvmd_compress(unsigned fw, llvm::Value * a, llvm::Value * select_mask) {
598    report_fatal_error("Unsupported field width: mvmd_compress " + std::to_string(fw));
599}
600
601Value * IDISA_Builder::bitblock_any(Value * a) {
602    Type * iBitBlock = getIntNTy(mBitBlockWidth);
603    return CreateICmpNE(CreateBitCast(a, iBitBlock),  ConstantInt::getNullValue(iBitBlock));
604}
605
606// full add producing {carryout, sum}
607std::pair<Value *, Value *> IDISA_Builder::bitblock_add_with_carry(Value * a, Value * b, Value * carryin) {
608    Value * carrygen = simd_and(a, b);
609    Value * carryprop = simd_or(a, b);
610    Value * sum = simd_add(mBitBlockWidth, simd_add(mBitBlockWidth, a, b), carryin);
611    Value * carryout = CreateBitCast(simd_or(carrygen, simd_and(carryprop, CreateNot(sum))), getIntNTy(mBitBlockWidth));
612    return std::pair<Value *, Value *>(bitCast(simd_srli(mBitBlockWidth, carryout, mBitBlockWidth - 1)), bitCast(sum));
613}
614
615// full shift producing {shiftout, shifted}
616std::pair<Value *, Value *> IDISA_Builder::bitblock_advance(Value * a, Value * shiftin, unsigned shift) {
617    Value * shiftin_bitblock = CreateBitCast(shiftin, getIntNTy(mBitBlockWidth));
618    Value * a_bitblock = CreateBitCast(a, getIntNTy(mBitBlockWidth));
619    Value * shifted = bitCast(CreateOr(CreateShl(a_bitblock, shift), shiftin_bitblock));
620    Value * shiftout = bitCast(CreateLShr(a_bitblock, mBitBlockWidth - shift));
621    return std::pair<Value *, Value *>(shiftout, shifted);
622}
623
624// full shift producing {shiftout, shifted}
625std::pair<Value *, Value *> IDISA_Builder::bitblock_indexed_advance(Value * strm, Value * index_strm, Value * shiftIn, unsigned shiftAmount) {
626    const unsigned bitWidth = getSizeTy()->getBitWidth();
627    Type * const iBitBlock = getIntNTy(getBitBlockWidth());
628    Value * const shiftVal = getSize(shiftAmount);
629    Value * extracted_bits = simd_pext(bitWidth, strm, index_strm);
630    Value * ix_popcounts = simd_popcount(bitWidth, index_strm);
631    const auto n = getBitBlockWidth() / bitWidth;
632    VectorType * const vecTy = VectorType::get(getSizeTy(), n);
633    if (LLVM_LIKELY(shiftAmount < bitWidth)) {
634        Value * carry = mvmd_extract(bitWidth, shiftIn, 0);
635        Value * result = UndefValue::get(vecTy);
636        for (unsigned i = 0; i < n; i++) {
637            Value * ix_popcnt = mvmd_extract(bitWidth, ix_popcounts, i);
638            Value * bits = mvmd_extract(bitWidth, extracted_bits, i);
639            Value * adv = CreateOr(CreateShl(bits, shiftAmount), carry);
640            // We have two cases depending on whether the popcount of the index pack is < shiftAmount or not.
641            Value * popcount_small = CreateICmpULT(ix_popcnt, shiftVal);
642            Value * carry_if_popcount_small =
643                CreateOr(CreateShl(bits, CreateSub(shiftVal, ix_popcnt)),
644                            CreateLShr(carry, ix_popcnt));
645            Value * carry_if_popcount_large = CreateLShr(bits, CreateSub(ix_popcnt, shiftVal));
646            carry = CreateSelect(popcount_small, carry_if_popcount_small, carry_if_popcount_large);
647            result = mvmd_insert(bitWidth, result, adv, i);
648        }
649        Value * carryOut = mvmd_insert(bitWidth, allZeroes(), carry, 0);
650        return std::pair<Value *, Value *>{bitCast(carryOut), simd_pdep(bitWidth, result, index_strm)};
651    }
652    else if (shiftAmount <= mBitBlockWidth) {
653        // The shift amount is always greater than the popcount of the individual
654        // elements that we deal with.   This simplifies some of the logic.
655        Value * carry = CreateBitCast(shiftIn, iBitBlock);
656        Value * result = UndefValue::get(vecTy);
657        for (unsigned i = 0; i < n; i++) {
658            Value * ix_popcnt = mvmd_extract(bitWidth, ix_popcounts, i);
659            Value * bits = mvmd_extract(bitWidth, extracted_bits, i);  // All these bits are shifted out (appended to carry).
660            result = mvmd_insert(bitWidth, result, mvmd_extract(bitWidth, carry, 0), i);
661            carry = CreateLShr(carry, CreateZExt(ix_popcnt, iBitBlock)); // Remove the carry bits consumed, make room for new bits.
662            carry = CreateOr(carry, CreateShl(CreateZExt(bits, iBitBlock), CreateZExt(CreateSub(shiftVal, ix_popcnt), iBitBlock)));
663        }
664        return std::pair<Value *, Value *>{bitCast(carry), simd_pdep(bitWidth, result, index_strm)};
665    }
666    else {
667        // The shift amount is greater than the total popcount.   We will consume popcount
668        // bits from the shiftIn value only, and produce a carry out value of the selected bits.
669        Value * carry = CreateBitCast(shiftIn, iBitBlock);
670        Value * result = UndefValue::get(vecTy);
671        Value * carryOut = ConstantInt::getNullValue(iBitBlock);
672        Value * generated = getSize(0);
673        for (unsigned i = 0; i < n; i++) {
674            Value * ix_popcnt = mvmd_extract(bitWidth, ix_popcounts, i);
675            Value * bits = mvmd_extract(bitWidth, extracted_bits, i);  // All these bits are shifted out (appended to carry).
676            result = mvmd_insert(bitWidth, result, mvmd_extract(bitWidth, carry, 0), i);
677            carry = CreateLShr(carry, CreateZExt(ix_popcnt, iBitBlock)); // Remove the carry bits consumed.
678            carryOut = CreateOr(carryOut, CreateShl(CreateZExt(bits, iBitBlock), CreateZExt(generated, iBitBlock)));
679            generated = CreateAdd(generated, ix_popcnt);
680        }
681        return std::pair<Value *, Value *>{bitCast(carryOut), simd_pdep(bitWidth, result, index_strm)};
682    }
683}
684
685
686Value * IDISA_Builder::bitblock_mask_from(Value * pos) {
687    Value * p = CreateZExtOrTrunc(pos, getSizeTy());
688    const unsigned fw = getSizeTy()->getBitWidth();
689    const auto field_count = mBitBlockWidth / fw;
690    Constant * fwVal = ConstantInt::get(getSizeTy(), fw);
691    Constant * poaBase[field_count];
692    for (unsigned i = 0; i < field_count; i++) {
693        poaBase[i] = ConstantInt::get(getSizeTy(), fw * i);
694    }
695    Value * posBaseVec = ConstantVector::get({poaBase, field_count});
696    Value * mask1 = CreateSExt(CreateICmpUGT(posBaseVec, simd_fill(fw, pos)), fwVectorType(fw));
697    Value * bitField = CreateShl(ConstantInt::getAllOnesValue(getSizeTy()), CreateURem(p, fwVal));
698    Value * inBitBlock = CreateICmpULT(p, getSize(mBitBlockWidth));
699    Value * fieldNo = CreateUDiv(p, fwVal);
700    Value * const final_mask = CreateSelect(inBitBlock, CreateInsertElement(mask1, bitField, fieldNo), mask1);
701    return bitCast(final_mask);
702}
703
704Value * IDISA_Builder::bitblock_set_bit(Value * pos) {
705    Value * p = CreateZExtOrTrunc(pos, getSizeTy());
706    const unsigned fw = getSizeTy()->getBitWidth();
707    Constant * fwVal = ConstantInt::get(getSizeTy(), fw);
708    Value * bitField = CreateShl(ConstantInt::get(getSizeTy(), 1), CreateURem(p, fwVal));
709    Value * fieldNo = CreateUDiv(p, fwVal);
710    return bitCast(CreateInsertElement(Constant::getNullValue(fwVectorType(fw)), bitField, fieldNo));
711}
712
713Value * IDISA_Builder::bitblock_popcount(Value * const to_count) {
714    const auto fieldWidth = getSizeTy()->getBitWidth();
715    auto fields = (getBitBlockWidth() / fieldWidth);
716    Value * fieldCounts = simd_popcount(fieldWidth, to_count);
717    while (fields > 1) {
718        fields /= 2;
719        fieldCounts = CreateAdd(fieldCounts, mvmd_srli(fieldWidth, fieldCounts, fields));
720    }
721    return mvmd_extract(fieldWidth, fieldCounts, 0);
722}
723
724Value * IDISA_Builder::simd_and(Value * a, Value * b) {
725    return a->getType() == b->getType() ? CreateAnd(a, b) : CreateAnd(bitCast(a), bitCast(b));
726}
727
728Value * IDISA_Builder::simd_or(Value * a, Value * b) {
729    return a->getType() == b->getType() ? CreateOr(a, b) : CreateOr(bitCast(a), bitCast(b));
730}
731   
732Value * IDISA_Builder::simd_xor(Value * a, Value * b) {
733    return a->getType() == b->getType() ? CreateXor(a, b) : CreateXor(bitCast(a), bitCast(b));
734}
735
736Value * IDISA_Builder::simd_not(Value * a) {
737    return simd_xor(a, Constant::getAllOnesValue(a->getType()));
738}
739
740IDISA_Builder::IDISA_Builder(LLVMContext & C, unsigned vectorWidth, unsigned stride)
741: CBuilder(C)
742, mBitBlockWidth(vectorWidth)
743, mStride(stride)
744, mBitBlockType(VectorType::get(IntegerType::get(C, 64), vectorWidth / 64))
745, mZeroInitializer(Constant::getNullValue(mBitBlockType))
746, mOneInitializer(Constant::getAllOnesValue(mBitBlockType))
747, mPrintRegisterFunction(nullptr) {
748
749}
750
751IDISA_Builder::~IDISA_Builder() {
752
753}
754
755}
Note: See TracBrowser for help on using the repository browser.