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

Last change on this file since 5489 was 5489, checked in by nmedfort, 22 months ago

Bug fix for memory check and issues found parsing internal 'files'. Added backtrace option from execinfo.h

File size: 17.1 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.CreateExtractElement(value, builder.getInt32(i - 1)));
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    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
82Value * IDISA_Builder::simd_add(unsigned fw, Value * a, Value * b) {
83    return CreateAdd(fwCast(fw, a), fwCast(fw, b));
84}
85
86Value * IDISA_Builder::simd_sub(unsigned fw, Value * a, Value * b) {
87    return CreateSub(fwCast(fw, a), fwCast(fw, b));
88}
89
90Value * IDISA_Builder::simd_mult(unsigned fw, Value * a, Value * b) {
91    return CreateMul(fwCast(fw, a), fwCast(fw, b));
92}
93
94Value * IDISA_Builder::simd_eq(unsigned fw, Value * a, Value * b) {
95    return CreateSExt(CreateICmpEQ(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
96}
97
98Value * IDISA_Builder::simd_gt(unsigned fw, Value * a, Value * b) {
99    return CreateSExt(CreateICmpSGT(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
100}
101
102Value * IDISA_Builder::simd_ugt(unsigned fw, Value * a, Value * b) {
103    return CreateSExt(CreateICmpUGT(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
104}
105
106Value * IDISA_Builder::simd_lt(unsigned fw, Value * a, Value * b) {
107    return CreateSExt(CreateICmpSLT(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
108}
109
110Value * IDISA_Builder::simd_ult(unsigned fw, Value * a, Value * b) {
111    return CreateSExt(CreateICmpULT(fwCast(fw, a), fwCast(fw, b)), fwVectorType(fw));
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);
117    return CreateSelect(CreateICmpSGT(aVec, bVec), aVec, bVec);
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);
123    return CreateSelect(CreateICmpUGT(aVec, bVec), aVec, bVec);
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);
129    return CreateSelect(CreateICmpSLT(aVec, bVec), aVec, bVec);
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);
135    return CreateSelect(CreateICmpULT(aVec, bVec), aVec, bVec);
136}
137
138Value * IDISA_Builder::simd_slli(unsigned fw, Value * a, unsigned shift) {
139    return CreateShl(fwCast(fw, a), shift);
140}
141
142Value * IDISA_Builder::simd_srli(unsigned fw, Value * a, unsigned shift) {
143    return CreateLShr(fwCast(fw, a), shift);
144}
145
146Value * IDISA_Builder::simd_srai(unsigned fw, Value * a, unsigned shift) {
147    return CreateAShr(fwCast(fw, a), shift);
148}
149
150Value * IDISA_Builder::simd_cttz(unsigned fw, Value * a) {
151    Value * cttzFunc = Intrinsic::getDeclaration(getModule(), Intrinsic::cttz, fwVectorType(fw));
152    return CreateCall(cttzFunc, {fwCast(fw, a), ConstantInt::get(getInt1Ty(), 0)});
153}
154
155Value * IDISA_Builder::simd_popcount(unsigned fw, Value * a) {
156    Value * ctpopFunc = Intrinsic::getDeclaration(getModule(), Intrinsic::ctpop, fwVectorType(fw));
157    return CreateCall(ctpopFunc, fwCast(fw, a));
158}
159
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
186Value * IDISA_Builder::simd_if(unsigned fw, Value * cond, Value * a, Value * b) {
187    if (fw == 1) {
188        Value * a1 = bitCast(a);
189        Value * b1 = bitCast(b);
190        Value * c = bitCast(cond);
191        return CreateOr(CreateAnd(a1, c), CreateAnd(CreateXor(c, b1), b1));
192    } else {
193        Value * aVec = fwCast(fw, a);
194        Value * bVec = fwCast(fw, b);
195        return CreateSelect(CreateICmpSLT(cond, mZeroInitializer), aVec, bVec);
196    }
197}
198   
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.
205    }
206    return CreateShuffleVector(fwCast(fw, a), fwCast(fw, b), ConstantVector::get({Idxs, field_count}));
207}
208
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.
215    }
216    return CreateShuffleVector(fwCast(fw, a), fwCast(fw, b), ConstantVector::get({Idxs, field_count}));
217}
218
219Value * IDISA_Builder::esimd_bitspread(unsigned fw, Value * bitmask) {
220    const auto field_count = mBitBlockWidth / fw;
221    Type * field_type = getIntNTy(fw);
222    Value * spread_field = CreateBitCast(CreateZExtOrTrunc(bitmask, field_type), VectorType::get(getIntNTy(fw), 1));
223    Value * undefVec = UndefValue::get(VectorType::get(getIntNTy(fw), 1));
224    Value * broadcast = CreateShuffleVector(spread_field, undefVec, Constant::getNullValue(VectorType::get(getInt32Ty(), field_count)));
225    Constant * bitSel[field_count];
226    Constant * bitShift[field_count];
227    for (unsigned i = 0; i < field_count; i++) {
228        bitSel[i] = ConstantInt::get(field_type, 1 << i);
229        bitShift[i] = ConstantInt::get(field_type, i);
230    }
231    Value * bitSelVec = ConstantVector::get({bitSel, field_count});
232    Value * bitShiftVec = ConstantVector::get({bitShift, field_count});
233    return CreateLShr(CreateAnd(bitSelVec, broadcast), bitShiftVec);
234}
235
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);
239    const auto field_count = 2 * mBitBlockWidth / fw;
240    Constant * Idxs[field_count];
241    for (unsigned i = 0; i < field_count; i++) {
242        Idxs[i] = getInt32(2 * i + 1);
243    }
244    return CreateShuffleVector(aVec, bVec, ConstantVector::get({Idxs, field_count}));
245}
246
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);
250    const auto field_count = 2 * mBitBlockWidth / fw;
251    Constant * Idxs[field_count];
252    for (unsigned i = 0; i < field_count; i++) {
253        Idxs[i] = getInt32(2 * i);
254    }
255    return CreateShuffleVector(aVec, bVec, ConstantVector::get({Idxs, field_count}));
256}
257
258Value * IDISA_Builder::hsimd_packh_in_lanes(unsigned lanes, unsigned fw, Value * a, Value * b) {
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);
268        }
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);
271        }
272    }
273    return CreateShuffleVector(fwCast(fw_out, a), fwCast(fw_out, b), ConstantVector::get({Idxs, field_count}));
274}
275
276Value * IDISA_Builder::hsimd_packl_in_lanes(unsigned lanes, unsigned fw, Value * a, Value * b) {
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));
286        }
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));
289        }
290    }
291    return CreateShuffleVector(fwCast(fw_out, a), fwCast(fw_out, b), ConstantVector::get({Idxs, field_count}));
292}
293
294Value * IDISA_Builder::hsimd_signmask(unsigned fw, Value * a) {
295    Value * mask = CreateICmpSLT(fwCast(fw, a), ConstantAggregateZero::get(fwVectorType(fw)));
296    return CreateZExt(CreateBitCast(mask, getIntNTy(mBitBlockWidth/fw)), getInt32Ty());
297}
298
299Value * IDISA_Builder::mvmd_extract(unsigned fw, Value * a, unsigned fieldIndex) {
300    return CreateExtractElement(fwCast(fw, a), getInt32(fieldIndex));
301}
302
303Value * IDISA_Builder::mvmd_insert(unsigned fw, Value * blk, Value * elt, unsigned fieldIndex) {
304    return CreateInsertElement(fwCast(fw, blk), elt, getInt32(fieldIndex));
305}
306
307Value * IDISA_Builder::mvmd_slli(unsigned fw, Value * a, unsigned shift) {
308    const auto field_count = mBitBlockWidth / fw;
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
316Value * IDISA_Builder::mvmd_dslli(unsigned fw, Value * a, Value * b, unsigned shift) {
317    const auto field_count = mBitBlockWidth/fw;
318    Constant * Idxs[field_count];
319    for (unsigned i = 0; i < field_count; i++) {
320        Idxs[i] = getInt32(i + shift);
321    }
322    return CreateShuffleVector(fwCast(fw, b), fwCast(fw, a), ConstantVector::get({Idxs, field_count}));
323}
324
325Value * IDISA_Builder::bitblock_any(Value * a) {
326    Type * iBitBlock = getIntNTy(mBitBlockWidth);
327    return CreateICmpNE(CreateBitCast(a, iBitBlock),  ConstantInt::getNullValue(iBitBlock));
328}
329
330// full add producing {carryout, sum}
331std::pair<Value *, Value *> IDISA_Builder::bitblock_add_with_carry(Value * a, Value * b, Value * carryin) {
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));
343    Value * shifted = bitCast(CreateOr(CreateShl(a_bitblock, shift), shiftin_bitblock));
344    Value * shiftout = bitCast(CreateLShr(a_bitblock, mBitBlockWidth - shift));
345    return std::pair<Value *, Value *>(shiftout, shifted);
346}
347
348Value * IDISA_Builder::bitblock_mask_from(Value * pos) {
349    Type * bitBlockInt = getIntNTy(getBitBlockWidth());
350    return bitCast(CreateShl(ConstantInt::getAllOnesValue(bitBlockInt), CreateZExt(pos, bitBlockInt)));
351   
352}
353Value * IDISA_Builder::bitblock_set_bit(Value * pos) {
354    Type * bitBlockInt = getIntNTy(getBitBlockWidth());
355    return bitCast(CreateShl(ConstantInt::get(bitBlockInt, 1), CreateZExt(pos, bitBlockInt)));
356}
357
358Value * IDISA_Builder::simd_and(Value * a, Value * b) {
359    return a->getType() == b->getType() ? CreateAnd(a, b) : CreateAnd(bitCast(a), bitCast(b));
360}
361
362Value * IDISA_Builder::simd_or(Value * a, Value * b) {
363    return a->getType() == b->getType() ? CreateOr(a, b) : CreateOr(bitCast(a), bitCast(b));
364}
365   
366Value * IDISA_Builder::simd_xor(Value * a, Value * b) {
367    return a->getType() == b->getType() ? CreateXor(a, b) : CreateXor(bitCast(a), bitCast(b));
368}
369
370Value * IDISA_Builder::simd_not(Value * a) {
371    return simd_xor(a, Constant::getAllOnesValue(a->getType()));
372}
373
374LoadInst * IDISA_Builder::CreateBlockAlignedLoad(Value * const ptr) {
375    const auto alignment = mBitBlockWidth / 8;
376    if (codegen::EnableAsserts) {
377        DataLayout DL(getModule());
378        IntegerType * const intPtrTy = getIntPtrTy(DL);
379        Value * alignmentOffset = CreateURem(CreatePtrToInt(ptr, intPtrTy), ConstantInt::get(intPtrTy, alignment));
380        Value * alignmentCheck = CreateICmpEQ(alignmentOffset, ConstantInt::getNullValue(intPtrTy));
381        CreateAssert(alignmentCheck, "CreateBlockAlignedLoad: pointer is unaligned");
382    }
383    return CreateAlignedLoad(ptr, alignment);
384}
385
386void IDISA_Builder::CreateBlockAlignedStore(Value * const value, Value * const ptr) {
387    const auto alignment = mBitBlockWidth / 8;
388    if (codegen::EnableAsserts) {
389        DataLayout DL(getModule());
390        IntegerType * const intPtrTy = getIntPtrTy(DL);
391        Value * alignmentOffset = CreateURem(CreatePtrToInt(ptr, intPtrTy), ConstantInt::get(intPtrTy, alignment));
392        Value * alignmentCheck = CreateICmpEQ(alignmentOffset, ConstantInt::getNullValue(intPtrTy));
393        CreateAssert(alignmentCheck, "CreateBlockAlignedStore: pointer is not aligned");
394    }
395    CreateAlignedStore(value, ptr, alignment);
396}
397
398IDISA_Builder::IDISA_Builder(llvm::LLVMContext & C, unsigned vectorWidth, unsigned stride)
399: CBuilder(C)
400, mBitBlockWidth(vectorWidth)
401, mStride(stride)
402, mBitBlockType(VectorType::get(IntegerType::get(C, 64), vectorWidth / 64))
403, mZeroInitializer(Constant::getNullValue(mBitBlockType))
404, mOneInitializer(Constant::getAllOnesValue(mBitBlockType))
405, mPrintRegisterFunction(nullptr) {
406
407}
408
409IDISA_Builder::~IDISA_Builder() {
410
411}
412
413}
Note: See TracBrowser for help on using the repository browser.