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

Last change on this file since 6083 was 6083, checked in by cameron, 11 months ago

PrintRegister? goes to stderr

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