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

Last change on this file since 5721 was 5713, checked in by cameron, 21 months ago

Moving indexed advance operation into IDISA builder

File size: 16.2 KB
RevLine 
[4651]1/*
[5117]2 *  Copyright (c) 2016 International Characters.
[4651]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>
[5260]12#include <llvm/IR/Module.h>
[4974]13#include <llvm/Support/raw_ostream.h>
[5227]14#include <llvm/IR/TypeBuilder.h>
[5425]15#include <toolchain/toolchain.h>
[4651]16
[5260]17using namespace llvm;
18
[4665]19namespace IDISA {
[4651]20
[5377]21VectorType * IDISA_Builder::fwVectorType(const unsigned fw) {
22    return VectorType::get(getIntNTy(fw), mBitBlockWidth / fw);
[4651]23}
24
[5377]25Value * IDISA_Builder::fwCast(const unsigned fw, Value * const a) {
26    VectorType * const ty = fwVectorType(fw);
[5378]27    assert (a->getType()->getPrimitiveSizeInBits() == ty->getPrimitiveSizeInBits());
[5377]28    return CreateBitCast(a, ty);
[4651]29}
30
[4974]31void IDISA_Builder::CallPrintRegister(const std::string & name, Value * const value) {
[5440]32    Module * const m = getModule();
33    Constant * printRegister = m->getFunction("PrintRegister");
[4974]34    if (LLVM_UNLIKELY(printRegister == nullptr)) {
[5245]35        FunctionType *FT = FunctionType::get(getVoidTy(), { PointerType::get(getInt8Ty(), 0), getBitBlockType() }, false);
[5440]36        Function * function = Function::Create(FT, Function::InternalLinkage, "PrintRegister", m);
[4974]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';
[5440]45        BasicBlock * entry = BasicBlock::Create(m->getContext(), "entry", function);
[4974]46        IRBuilder<> builder(entry);
47        std::vector<Value *> args;
[5398]48        args.push_back(GetString(out.str().c_str()));
[5014]49        Value * const name = &*(arg++);
[4974]50        name->setName("name");
51        args.push_back(name);
[5014]52        Value * value = &*arg;
[4974]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.CreateExtractElement(value, builder.getInt32(i - 1)));
58        }
[5239]59        builder.CreateCall(GetPrintf(), args);
[4974]60        builder.CreateRetVoid();
[4942]61
[4974]62        printRegister = function;
63    }
[5398]64    CreateCall(printRegister, {GetString(name.c_str()), CreateBitCast(value, mBitBlockType)});
[4942]65}
66
67Constant * IDISA_Builder::simd_himask(unsigned fw) {
68    return Constant::getIntegerValue(getIntNTy(mBitBlockWidth), APInt::getSplat(mBitBlockWidth, APInt::getHighBitsSet(fw, fw/2)));
[4651]69}
70
[4942]71Constant * IDISA_Builder::simd_lomask(unsigned fw) {
72    return Constant::getIntegerValue(getIntNTy(mBitBlockWidth), APInt::getSplat(mBitBlockWidth, APInt::getLowBitsSet(fw, fw/2)));
73}
74
[5140]75Value * IDISA_Builder::simd_fill(unsigned fw, Value * a) {
76    unsigned field_count = mBitBlockWidth/fw;
77    Type * singleFieldVecTy = VectorType::get(getIntNTy(fw), 1);
78    Value * aVec = CreateBitCast(a, singleFieldVecTy);
79    return CreateShuffleVector(aVec, UndefValue::get(singleFieldVecTy), Constant::getNullValue(VectorType::get(getInt32Ty(), field_count)));
80}
81
[4942]82Value * IDISA_Builder::simd_add(unsigned fw, Value * a, Value * b) {
[5140]83    return CreateAdd(fwCast(fw, a), fwCast(fw, b));
[4942]84}
85
[4651]86Value * IDISA_Builder::simd_sub(unsigned fw, Value * a, Value * b) {
[4898]87    return CreateSub(fwCast(fw, a), fwCast(fw, b));
[4651]88}
89
90Value * IDISA_Builder::simd_mult(unsigned fw, Value * a, Value * b) {
[4898]91    return CreateMul(fwCast(fw, a), fwCast(fw, b));
[4651]92}
93
94Value * IDISA_Builder::simd_eq(unsigned fw, Value * a, Value * b) {
[4898]95    return CreateSExt(CreateICmpEQ(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
[4651]96}
97
98Value * IDISA_Builder::simd_gt(unsigned fw, Value * a, Value * b) {
[4898]99    return CreateSExt(CreateICmpSGT(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
[4651]100}
101
102Value * IDISA_Builder::simd_ugt(unsigned fw, Value * a, Value * b) {
[4898]103    return CreateSExt(CreateICmpUGT(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
[4651]104}
105
106Value * IDISA_Builder::simd_lt(unsigned fw, Value * a, Value * b) {
[4898]107    return CreateSExt(CreateICmpSLT(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
[4651]108}
109
110Value * IDISA_Builder::simd_ult(unsigned fw, Value * a, Value * b) {
[4898]111    return CreateSExt(CreateICmpULT(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
[4651]112}
113
114Value * IDISA_Builder::simd_max(unsigned fw, Value * a, Value * b) {
115    Value * aVec = fwCast(fw, a);
116    Value * bVec = fwCast(fw, b);
[4898]117    return CreateSelect(CreateICmpSGT(aVec, bVec), aVec, bVec);
[4651]118}
119
120Value * IDISA_Builder::simd_umax(unsigned fw, Value * a, Value * b) {
121    Value * aVec = fwCast(fw, a);
122    Value * bVec = fwCast(fw, b);
[4898]123    return CreateSelect(CreateICmpUGT(aVec, bVec), aVec, bVec);
[4651]124}
125
126Value * IDISA_Builder::simd_min(unsigned fw, Value * a, Value * b) {
127    Value * aVec = fwCast(fw, a);
128    Value * bVec = fwCast(fw, b);
[4898]129    return CreateSelect(CreateICmpSLT(aVec, bVec), aVec, bVec);
[4651]130}
131
132Value * IDISA_Builder::simd_umin(unsigned fw, Value * a, Value * b) {
133    Value * aVec = fwCast(fw, a);
134    Value * bVec = fwCast(fw, b);
[4898]135    return CreateSelect(CreateICmpULT(aVec, bVec), aVec, bVec);
[4651]136}
137
138Value * IDISA_Builder::simd_slli(unsigned fw, Value * a, unsigned shift) {
[4898]139    return CreateShl(fwCast(fw, a), shift);
[4651]140}
141
142Value * IDISA_Builder::simd_srli(unsigned fw, Value * a, unsigned shift) {
[4898]143    return CreateLShr(fwCast(fw, a), shift);
[4651]144}
145
146Value * IDISA_Builder::simd_srai(unsigned fw, Value * a, unsigned shift) {
[4898]147    return CreateAShr(fwCast(fw, a), shift);
[4651]148}
149
150Value * IDISA_Builder::simd_cttz(unsigned fw, Value * a) {
[5440]151    Value * cttzFunc = Intrinsic::getDeclaration(getModule(), Intrinsic::cttz, fwVectorType(fw));
[5309]152    return CreateCall(cttzFunc, {fwCast(fw, a), ConstantInt::get(getInt1Ty(), 0)});
[4651]153}
154
[4720]155Value * IDISA_Builder::simd_popcount(unsigned fw, Value * a) {
[5440]156    Value * ctpopFunc = Intrinsic::getDeclaration(getModule(), Intrinsic::ctpop, fwVectorType(fw));
[5309]157    return CreateCall(ctpopFunc, fwCast(fw, a));
[4720]158}
159
[5488]160Value * IDISA_Builder::simd_bitreverse(unsigned fw, Value * a) {
161    /*  Pure sequential solution too slow!
162     Value * func = Intrinsic::getDeclaration(getModule(), Intrinsic::bitreverse, fwVectorType(fw));
163     return CreateCall(func, fwCast(fw, a));
164     */
165    if (fw > 8) {
166        // Reverse the bits of each byte and then use a byte shuffle to complete the job.
167        Value * bitrev8 = fwCast(8, simd_bitreverse(8, a));
168        const auto bytes_per_field = fw/8;
169        const auto byte_count = mBitBlockWidth / 8;
170        Constant * Idxs[byte_count];
171        for (unsigned i = 0; i < byte_count; i += bytes_per_field) {
172            for (unsigned j = 0; j < bytes_per_field; j++) {
173                Idxs[i + j] = getInt32(i + bytes_per_field - j - 1);
174            }
175        }
176        return CreateShuffleVector(bitrev8, UndefValue::get(fwVectorType(8)), ConstantVector::get({Idxs, byte_count}));
177    }
178    else {
179        if (fw > 2) {
180            a = simd_bitreverse(fw/2, a);
181        }
182        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));
183    }
184}
185
[4891]186Value * IDISA_Builder::simd_if(unsigned fw, Value * cond, Value * a, Value * b) {
[4900]187    if (fw == 1) {
[4957]188        Value * a1 = bitCast(a);
189        Value * b1 = bitCast(b);
[4900]190        Value * c = bitCast(cond);
[4957]191        return CreateOr(CreateAnd(a1, c), CreateAnd(CreateXor(c, b1), b1));
[5309]192    } else {
[4900]193        Value * aVec = fwCast(fw, a);
194        Value * bVec = fwCast(fw, b);
195        return CreateSelect(CreateICmpSLT(cond, mZeroInitializer), aVec, bVec);
196    }
[4891]197}
198   
[5309]199Value * IDISA_Builder::esimd_mergeh(unsigned fw, Value * a, Value * b) {   
200    const auto field_count = mBitBlockWidth / fw;
201    Constant * Idxs[field_count];
202    for (unsigned i = 0; i < field_count / 2; i++) {
203        Idxs[2 * i] = getInt32(i + field_count / 2); // selects elements from first reg.
204        Idxs[2 * i + 1] = getInt32(i + field_count / 2 + field_count); // selects elements from second reg.
[4652]205    }
[5309]206    return CreateShuffleVector(fwCast(fw, a), fwCast(fw, b), ConstantVector::get({Idxs, field_count}));
[4652]207}
208
[5309]209Value * IDISA_Builder::esimd_mergel(unsigned fw, Value * a, Value * b) {   
210    const auto field_count = mBitBlockWidth / fw;
211    Constant * Idxs[field_count];
212    for (unsigned i = 0; i < field_count / 2; i++) {
213        Idxs[2 * i] = getInt32(i); // selects elements from first reg.
214        Idxs[2 * i + 1] = getInt32(i + field_count); // selects elements from second reg.
[4652]215    }
[5309]216    return CreateShuffleVector(fwCast(fw, a), fwCast(fw, b), ConstantVector::get({Idxs, field_count}));
[4652]217}
218
[4892]219Value * IDISA_Builder::esimd_bitspread(unsigned fw, Value * bitmask) {
[5309]220    const auto field_count = mBitBlockWidth / fw;
[4898]221    Type * field_type = getIntNTy(fw);
[5309]222    Value * spread_field = CreateBitCast(CreateZExtOrTrunc(bitmask, field_type), VectorType::get(getIntNTy(fw), 1));
[4898]223    Value * undefVec = UndefValue::get(VectorType::get(getIntNTy(fw), 1));
224    Value * broadcast = CreateShuffleVector(spread_field, undefVec, Constant::getNullValue(VectorType::get(getInt32Ty(), field_count)));
[5309]225    Constant * bitSel[field_count];
226    Constant * bitShift[field_count];
[4879]227    for (unsigned i = 0; i < field_count; i++) {
[5309]228        bitSel[i] = ConstantInt::get(field_type, 1 << i);
229        bitShift[i] = ConstantInt::get(field_type, i);
[4879]230    }
[5309]231    Value * bitSelVec = ConstantVector::get({bitSel, field_count});
232    Value * bitShiftVec = ConstantVector::get({bitShift, field_count});
[4898]233    return CreateLShr(CreateAnd(bitSelVec, broadcast), bitShiftVec);
[4879]234}
235
[4653]236Value * IDISA_Builder::hsimd_packh(unsigned fw, Value * a, Value * b) {
237    Value * aVec = fwCast(fw/2, a);
238    Value * bVec = fwCast(fw/2, b);
[5309]239    const auto field_count = 2 * mBitBlockWidth / fw;
240    Constant * Idxs[field_count];
[4653]241    for (unsigned i = 0; i < field_count; i++) {
[5309]242        Idxs[i] = getInt32(2 * i + 1);
[4653]243    }
[5309]244    return CreateShuffleVector(aVec, bVec, ConstantVector::get({Idxs, field_count}));
[4653]245}
[4652]246
[4653]247Value * IDISA_Builder::hsimd_packl(unsigned fw, Value * a, Value * b) {
248    Value * aVec = fwCast(fw/2, a);
249    Value * bVec = fwCast(fw/2, b);
[5309]250    const auto field_count = 2 * mBitBlockWidth / fw;
251    Constant * Idxs[field_count];
[4653]252    for (unsigned i = 0; i < field_count; i++) {
[5309]253        Idxs[i] = getInt32(2 * i);
[4653]254    }
[5309]255    return CreateShuffleVector(aVec, bVec, ConstantVector::get({Idxs, field_count}));
[4653]256}
[4652]257
[4957]258Value * IDISA_Builder::hsimd_packh_in_lanes(unsigned lanes, unsigned fw, Value * a, Value * b) {
[5309]259    const unsigned fw_out = fw / 2;
260    const unsigned fields_per_lane = mBitBlockWidth / (fw_out * lanes);
261    const unsigned field_offset_for_b = mBitBlockWidth / fw_out;
262    const unsigned field_count = mBitBlockWidth / fw_out;
263    Constant * Idxs[field_count];
264    for (unsigned lane = 0, j = 0; lane < lanes; lane++) {
265        const unsigned first_field_in_lane = lane * fields_per_lane; // every second field
266        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
267            Idxs[j++] = getInt32(first_field_in_lane + (2 * i) + 1);
[4957]268        }
[5309]269        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
270            Idxs[j++] = getInt32(field_offset_for_b + first_field_in_lane + (2 * i) + 1);
[4957]271        }
272    }
[5309]273    return CreateShuffleVector(fwCast(fw_out, a), fwCast(fw_out, b), ConstantVector::get({Idxs, field_count}));
[4957]274}
275
276Value * IDISA_Builder::hsimd_packl_in_lanes(unsigned lanes, unsigned fw, Value * a, Value * b) {
[5309]277    const unsigned fw_out = fw / 2;
278    const unsigned fields_per_lane = mBitBlockWidth / (fw_out * lanes);
279    const unsigned field_offset_for_b = mBitBlockWidth / fw_out;
280    const unsigned field_count = mBitBlockWidth / fw_out;
281    Constant * Idxs[field_count];
282    for (unsigned lane = 0, j = 0; lane < lanes; lane++) {
283        const unsigned first_field_in_lane = lane * fields_per_lane; // every second field
284        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
285            Idxs[j++] = getInt32(first_field_in_lane + (2 * i));
[4957]286        }
[5309]287        for (unsigned i = 0; i < fields_per_lane / 2; i++) {
288            Idxs[j++] = getInt32(field_offset_for_b + first_field_in_lane + (2 * i));
[4957]289        }
290    }
[5309]291    return CreateShuffleVector(fwCast(fw_out, a), fwCast(fw_out, b), ConstantVector::get({Idxs, field_count}));
[4957]292}
293
[4653]294Value * IDISA_Builder::hsimd_signmask(unsigned fw, Value * a) {
[4898]295    Value * mask = CreateICmpSLT(fwCast(fw, a), ConstantAggregateZero::get(fwVectorType(fw)));
296    return CreateZExt(CreateBitCast(mask, getIntNTy(mBitBlockWidth/fw)), getInt32Ty());
[4653]297}
298
[4697]299Value * IDISA_Builder::mvmd_extract(unsigned fw, Value * a, unsigned fieldIndex) {
[5202]300    return CreateExtractElement(fwCast(fw, a), getInt32(fieldIndex));
[4697]301}
302
[4881]303Value * IDISA_Builder::mvmd_insert(unsigned fw, Value * blk, Value * elt, unsigned fieldIndex) {
[5309]304    return CreateInsertElement(fwCast(fw, blk), elt, getInt32(fieldIndex));
[4881]305}
306
[5007]307Value * IDISA_Builder::mvmd_slli(unsigned fw, Value * a, unsigned shift) {
[5309]308    const auto field_count = mBitBlockWidth / fw;
[5007]309    return mvmd_dslli(fw, a, Constant::getNullValue(fwVectorType(fw)), field_count - shift);
310}
311
312Value * IDISA_Builder::mvmd_srli(unsigned fw, Value * a, unsigned shift) {
313    return mvmd_dslli(fw, Constant::getNullValue(fwVectorType(fw)), a, shift);
314}
315
[4655]316Value * IDISA_Builder::mvmd_dslli(unsigned fw, Value * a, Value * b, unsigned shift) {
[5309]317    const auto field_count = mBitBlockWidth/fw;
318    Constant * Idxs[field_count];
[4845]319    for (unsigned i = 0; i < field_count; i++) {
[5309]320        Idxs[i] = getInt32(i + shift);
[4655]321    }
[5309]322    return CreateShuffleVector(fwCast(fw, b), fwCast(fw, a), ConstantVector::get({Idxs, field_count}));
[4655]323}
[4653]324
[4662]325Value * IDISA_Builder::bitblock_any(Value * a) {
[4898]326    Type * iBitBlock = getIntNTy(mBitBlockWidth);
[5309]327    return CreateICmpNE(CreateBitCast(a, iBitBlock),  ConstantInt::getNullValue(iBitBlock));
[4662]328}
[4665]329
[5114]330// full add producing {carryout, sum}
[5115]331std::pair<Value *, Value *> IDISA_Builder::bitblock_add_with_carry(Value * a, Value * b, Value * carryin) {
[5114]332    Value * carrygen = simd_and(a, b);
333    Value * carryprop = simd_or(a, b);
334    Value * sum = simd_add(mBitBlockWidth, simd_add(mBitBlockWidth, a, b), carryin);
335    Value * carryout = CreateBitCast(simd_or(carrygen, simd_and(carryprop, CreateNot(sum))), getIntNTy(mBitBlockWidth));
336    return std::pair<Value *, Value *>(bitCast(simd_srli(mBitBlockWidth, carryout, mBitBlockWidth - 1)), bitCast(sum));
337}
338
339// full shift producing {shiftout, shifted}
340std::pair<Value *, Value *> IDISA_Builder::bitblock_advance(Value * a, Value * shiftin, unsigned shift) {
341    Value * shiftin_bitblock = CreateBitCast(shiftin, getIntNTy(mBitBlockWidth));
342    Value * a_bitblock = CreateBitCast(a, getIntNTy(mBitBlockWidth));
[5117]343    Value * shifted = bitCast(CreateOr(CreateShl(a_bitblock, shift), shiftin_bitblock));
344    Value * shiftout = bitCast(CreateLShr(a_bitblock, mBitBlockWidth - shift));
[5114]345    return std::pair<Value *, Value *>(shiftout, shifted);
346}
347
[5713]348// full shift producing {shiftout, shifted}
349std::pair<Value *, Value *> IDISA_Builder::bitblock_indexed_advance(Value * a, Value * index, Value * shiftin, unsigned shift) {
350    llvm::report_fatal_error("bitblock_indexed_advance unimplemented for this architecture");
351}
352
[5121]353Value * IDISA_Builder::bitblock_mask_from(Value * pos) {
354    Type * bitBlockInt = getIntNTy(getBitBlockWidth());
355    return bitCast(CreateShl(ConstantInt::getAllOnesValue(bitBlockInt), CreateZExt(pos, bitBlockInt)));
356   
357}
358Value * IDISA_Builder::bitblock_set_bit(Value * pos) {
359    Type * bitBlockInt = getIntNTy(getBitBlockWidth());
360    return bitCast(CreateShl(ConstantInt::get(bitBlockInt, 1), CreateZExt(pos, bitBlockInt)));
361}
362
[4837]363Value * IDISA_Builder::simd_and(Value * a, Value * b) {
[4898]364    return a->getType() == b->getType() ? CreateAnd(a, b) : CreateAnd(bitCast(a), bitCast(b));
[4665]365}
[4837]366
367Value * IDISA_Builder::simd_or(Value * a, Value * b) {
[4898]368    return a->getType() == b->getType() ? CreateOr(a, b) : CreateOr(bitCast(a), bitCast(b));
[4837]369}
370   
371Value * IDISA_Builder::simd_xor(Value * a, Value * b) {
[4898]372    return a->getType() == b->getType() ? CreateXor(a, b) : CreateXor(bitCast(a), bitCast(b));
[4837]373}
374
375Value * IDISA_Builder::simd_not(Value * a) {
376    return simd_xor(a, Constant::getAllOnesValue(a->getType()));
377}
378
[5489]379IDISA_Builder::IDISA_Builder(llvm::LLVMContext & C, unsigned vectorWidth, unsigned stride)
380: CBuilder(C)
381, mBitBlockWidth(vectorWidth)
[5240]382, mStride(stride)
[5489]383, mBitBlockType(VectorType::get(IntegerType::get(C, 64), vectorWidth / 64))
[5240]384, mZeroInitializer(Constant::getNullValue(mBitBlockType))
385, mOneInitializer(Constant::getAllOnesValue(mBitBlockType))
386, mPrintRegisterFunction(nullptr) {
387
[5230]388}
[5240]389
390IDISA_Builder::~IDISA_Builder() {
[5298]391
[5240]392}
393
394}
Note: See TracBrowser for help on using the repository browser.