source: icGREP/icgrep-devel/icgrep/pablo/carry_manager.cpp @ 4827

Last change on this file since 4827 was 4827, checked in by cameron, 4 years ago

Parameterize carry_manager to inherit BitBlockWidth? from idisa builder

File size: 32.6 KB
Line 
1/*
2 *  Copyright (c) 2015 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
8#include <include/simd-lib/bitblock.hpp>
9#include <stdexcept>
10#include <pablo/carry_data.h>
11#include <pablo/codegenstate.h>
12#include <pablo/carry_manager.h>
13#include <pablo/pabloAST.h>
14#include <iostream>
15#include <llvm/Support/CommandLine.h>
16#include <llvm/IR/BasicBlock.h>
17#include <llvm/IR/CallingConv.h>
18#include <llvm/IR/Function.h>
19
20
21static cl::opt<CarryManagerStrategy> Strategy(cl::desc("Choose carry management strategy:"),
22                                              cl::values(
23                                                         clEnumVal(BitBlockStrategy, "Unpacked, each carry in a separate bitblock."),
24                                                         clEnumVal(SequentialFullyPackedStrategy, "Sequential packing, up to 64 carries per pack."),
25                                                         clEnumValEnd));
26
27
28namespace pablo {
29 
30    unsigned doScopeCount(PabloBlock * pb) {
31        unsigned count = 1;
32       
33        for (Statement * stmt : *pb) {
34            if (If * ifStatement = dyn_cast<If>(stmt)) {
35                count += doScopeCount(&ifStatement->getBody());
36            }
37            else if (While * whileStatement = dyn_cast<While>(stmt)) {
38                count += doScopeCount(&whileStatement->getBody());
39            }
40        }
41        return count;
42       
43    }
44   
45void CarryManager::generateCarryDataInitializer(Module * m) {
46    FunctionType * functionType = FunctionType::get(Type::getVoidTy(m->getContext()), std::vector<Type *>({}), false);
47    SmallVector<AttributeSet, 1> Attrs;
48    Attrs.push_back(AttributeSet::get(m->getContext(), ~0U, std::vector<Attribute::AttrKind>({ Attribute::NoUnwind, Attribute::UWTable })));
49    AttributeSet AttrSet = AttributeSet::get(m->getContext(), Attrs);
50   
51    // Create the function that will be generated.
52    Function * f = Function::Create(functionType, GlobalValue::ExternalLinkage, "process_block_initialize_carries", m);
53    f->setCallingConv(CallingConv::C);
54    f->setAttributes(AttrSet);
55    llvm::IRBuilderBase::InsertPoint ip = mBuilder->saveIP();
56    mBuilder->SetInsertPoint(BasicBlock::Create(m->getContext(), "entry1", f,0));
57    mBuilder->CreateMemSet(mCarryBitBlockPtr, mBuilder->getInt8(0), mTotalCarryDataBitBlocks * mBITBLOCK_WIDTH/8, 4);
58    ReturnInst::Create(m->getContext(), mBuilder->GetInsertBlock());
59    mBuilder->restoreIP(ip);
60}
61   
62   
63
64void CarryManager::initialize(Module * m, PabloBlock * pb) {
65    mPabloRoot = pb;
66    unsigned scopeCount = doScopeCount(pb);
67    mCarryInfoVector.resize(scopeCount);
68    if (Strategy == SequentialFullyPackedStrategy) {
69        mPACK_SIZE = 64;
70        mITEMS_PER_PACK = 64;
71        mCarryPackType = mBuilder->getIntNTy(mPACK_SIZE);
72        mPackBuilder = new IDISA::IDISA_Builder(mCarryPackType);
73        mPackBuilder->initialize(m, mBuilder);
74    }
75    else {
76        mPACK_SIZE = mBITBLOCK_WIDTH;
77        mITEMS_PER_PACK = 1;
78        mCarryPackType = mBitBlockType;
79    }
80    unsigned totalCarryDataSize = enumerate(pb, 0, 0);
81   
82    unsigned totalPackCount = (totalCarryDataSize + mITEMS_PER_PACK - 1)/mITEMS_PER_PACK;
83
84    mCarryPackPtr.resize(totalPackCount);
85    mCarryInPack.resize(totalPackCount);
86    mCarryOutPack.resize(totalPackCount);
87    for (unsigned i = 0; i < totalPackCount; i++) mCarryInPack[i]=nullptr;
88
89    if (Strategy == SequentialFullyPackedStrategy) {
90        mTotalCarryDataBitBlocks = (totalCarryDataSize + mBITBLOCK_WIDTH - 1)/mBITBLOCK_WIDTH;       
91    }
92    else {
93        mTotalCarryDataBitBlocks = totalCarryDataSize;
94    }
95   
96    ArrayType* cdArrayTy = ArrayType::get(mBitBlockType, mTotalCarryDataBitBlocks);
97    GlobalVariable* cdArray = new GlobalVariable(*m, cdArrayTy, /*isConstant=*/false, GlobalValue::CommonLinkage, /*Initializer=*/0, "process_block_carry_data");
98    cdArray->setAlignment(mBITBLOCK_WIDTH/8);
99    ConstantAggregateZero* cdInitData = ConstantAggregateZero::get(cdArrayTy);
100    cdArray->setInitializer(cdInitData);
101   
102    mCarryPackBasePtr = mBuilder->CreateBitCast(cdArray, PointerType::get(mCarryPackType, 0));
103    mCarryBitBlockPtr = mBuilder->CreateBitCast(cdArray, PointerType::get(mBitBlockType, 0));
104   
105    generateCarryDataInitializer(m);
106   
107    // Popcount data is stored after all the carry data.
108    if (mPabloCountCount > 0) {
109        ArrayType* pcArrayTy = ArrayType::get(mBuilder->getIntNTy(64), mPabloCountCount);
110        GlobalVariable* pcArray = new GlobalVariable(*m, pcArrayTy, /*isConstant=*/false, GlobalValue::CommonLinkage, 0, "popcount_data");
111        cdArray->setAlignment(mBITBLOCK_WIDTH/8);
112        ConstantAggregateZero* pcInitData = ConstantAggregateZero::get(pcArrayTy);
113        pcArray->setInitializer(pcInitData);
114        mPopcountBasePtr = mBuilder->CreateBitCast(pcArray, Type::getInt64PtrTy(mBuilder->getContext()));
115    }
116    // Carry Data area will have one extra bit block to store the block number.
117    GlobalVariable* blkNo = new GlobalVariable(*m, mBuilder->getIntNTy(64), /*isConstant=*/false, GlobalValue::CommonLinkage, 0, "blockNo");
118    blkNo->setAlignment(16);
119    blkNo->setInitializer(mBuilder->getInt64(0));
120    mBlockNoPtr = blkNo;
121    mBlockNo = mBuilder->CreateLoad(mBlockNoPtr);
122    /*  Set the current scope to PabloRoot */
123    mCurrentScope = mPabloRoot;
124    mCurrentFrameIndex = 0;
125    mCarryInfo = mCarryInfoVector[0];
126}
127   
128void CarryManager::generateBlockNoIncrement() {
129    mBuilder->CreateStore(mBuilder->CreateAdd(mBlockNo, mBuilder->getInt64(1)), mBlockNoPtr);
130}
131
132Value * CarryManager::getBlockNoPtr() {
133    return mBlockNoPtr;
134}
135
136
137unsigned CarryManager::enumerate(PabloBlock * blk, unsigned ifDepth, unsigned whileDepth) {
138    llvm::raw_os_ostream cerr(std::cerr);
139    unsigned idx = blk->getScopeIndex();
140    PabloBlockCarryData * cd = new PabloBlockCarryData(blk, mPACK_SIZE, mITEMS_PER_PACK);
141    mCarryInfoVector[idx] = cd;
142
143    cd->setIfDepth(ifDepth);
144    cd->setWhileDepth(whileDepth);
145    unsigned nestedOffset = cd->nested.frameOffset;
146 
147    for (Statement * stmt : *blk) {
148        if (Count * c = dyn_cast<Count>(stmt)) {
149            c->setGlobalCountIndex(mPabloCountCount);
150            mPabloCountCount++;
151        }
152        else if (If * ifStatement = dyn_cast<If>(stmt)) {
153            const unsigned ifCarryDataBits = enumerate(&ifStatement->getBody(), ifDepth+1, whileDepth);
154            PabloBlockCarryData * nestedBlockData = mCarryInfoVector[ifStatement->getBody().getScopeIndex()];
155            if (mITEMS_PER_PACK == mPACK_SIZE) {  // PACKING
156                if (cd->roomInFinalPack(nestedOffset) < ifCarryDataBits) {
157                    nestedOffset = alignCeiling(nestedOffset, mPACK_SIZE);
158                }
159            }
160            nestedBlockData->setFramePosition(nestedOffset);
161
162            nestedOffset += ifCarryDataBits;
163            if (cd->maxNestingDepth <= nestedBlockData->maxNestingDepth) cd->maxNestingDepth = nestedBlockData->maxNestingDepth + 1;
164            cd->nested.entries++;
165#ifdef CARRY_DEBUG
166            nestedBlockData->dumpCarryData(cerr);
167#endif
168        }
169        else if (While * whileStatement = dyn_cast<While>(stmt)) {
170            const unsigned whileCarryDataBits = enumerate(&whileStatement->getBody(), ifDepth, whileDepth+1);
171            PabloBlockCarryData * nestedBlockData = mCarryInfoVector[whileStatement->getBody().getScopeIndex()];
172            //if (whileStatement->isMultiCarry()) whileCarryDataBits *= whileStatement->getMaxIterations();
173            if (mITEMS_PER_PACK == mPACK_SIZE) {  // PACKING
174                if (cd->roomInFinalPack(nestedOffset) < whileCarryDataBits) {
175                    nestedOffset = alignCeiling(nestedOffset, mPACK_SIZE);
176                }
177            }
178            nestedBlockData->setFramePosition(nestedOffset);
179            nestedOffset += whileCarryDataBits;
180            if (cd->maxNestingDepth <= nestedBlockData->maxNestingDepth) cd->maxNestingDepth = nestedBlockData->maxNestingDepth + 1;
181            cd->nested.entries++;
182#ifdef CARRY_DEBUG
183            nestedBlockData->dumpCarryData(cerr);
184#endif
185        }
186    }
187   
188    cd->scopeCarryDataSize = nestedOffset;
189   
190    if (cd->explicitSummaryRequired()) {
191        // Need extra space for the summary variable, always the last
192        // entry within an if block.
193        if (mITEMS_PER_PACK == mPACK_SIZE) {  // PACKING
194            cd->scopeCarryDataSize = alignCeiling(cd->scopeCarryDataSize, mPACK_SIZE);
195        }
196        cd->summary.frameOffset = cd->scopeCarryDataSize;
197        cd->scopeCarryDataSize += mITEMS_PER_PACK;  //  computed summary is a full pack.
198    }
199    else {
200        cd->summary.frameOffset = 0;
201    }
202#ifdef CARRY_DEBUG
203    if (cd->ifDepth == 0) cd->dumpCarryData(cerr);
204#endif
205    return cd->scopeCarryDataSize;
206}
207
208
209/* Entering and leaving blocks. */
210
211void CarryManager::enterScope(PabloBlock * blk) {
212   
213    mCurrentScope = blk;
214    mCarryInfo = mCarryInfoVector[blk->getScopeIndex()];
215    mCurrentFrameIndex += mCarryInfo->getFrameIndex();
216    //std::cerr << "enterScope:  blk->getScopeIndex() = " << blk->getScopeIndex() << ", mCurrentFrameIndex = " << mCurrentFrameIndex << std::endl;
217}
218
219void CarryManager::leaveScope() {
220    mCurrentFrameIndex -= mCarryInfo->getFrameIndex();
221    if (mCurrentScope != mPabloRoot) {
222        mCurrentScope = mCurrentScope->getParent();
223        mCarryInfo = mCarryInfoVector[mCurrentScope->getScopeIndex()];
224    }
225    //std::cerr << "leaveScope:  mCurrentFrameIndex = " << mCurrentFrameIndex << std::endl;
226}
227
228
229/* Helper routines */
230
231unsigned CarryManager::absPosition(unsigned frameOffset, unsigned relPos) {
232    return mCurrentFrameIndex + frameOffset + relPos;
233}
234
235
236unsigned CarryManager::carryOpPosition(unsigned localIndex) {
237    //std::cerr << "carryOpPosition: addWithCarry.frameOffset = " << mCarryInfo->addWithCarry.frameOffset << ", localIndex = " <<localIndex << std::endl;
238    return absPosition(mCarryInfo->addWithCarry.frameOffset, localIndex);
239}
240
241unsigned CarryManager::advance1Position(unsigned localIndex) {
242    //std::cerr << "unsigned CarryManager::advance1Position: advance1.frameOffset = " << mCarryInfo->advance1.frameOffset << ", localIndex = " <<localIndex << std::endl;
243    return absPosition(mCarryInfo->advance1.frameOffset, localIndex);
244}
245
246unsigned CarryManager::shortAdvancePosition(unsigned localIndex) {
247    return absPosition(mCarryInfo->shortAdvance.frameOffset, localIndex);
248}
249
250unsigned CarryManager::longAdvanceBitBlockPosition(unsigned localIndex) {
251    return (mCurrentFrameIndex + mCarryInfo->longAdvance.frameOffset) / mITEMS_PER_PACK + localIndex;
252}
253   
254unsigned CarryManager::localBasePack() {
255    return (mCurrentFrameIndex + mCarryInfo->shortAdvance.frameOffset) / mITEMS_PER_PACK;
256}
257   
258unsigned CarryManager::scopeBasePack() {
259    return mCurrentFrameIndex / mITEMS_PER_PACK;
260}
261   
262
263
264unsigned CarryManager::summaryPosition() {
265    return absPosition(mCarryInfo->summary.frameOffset, 0);
266}
267
268
269unsigned CarryManager::summaryPackIndex() {
270    return summaryPosition()/mITEMS_PER_PACK;
271}
272
273unsigned CarryManager::summaryBits() {
274    if (mCarryInfo->scopeCarryDataSize > mITEMS_PER_PACK) return mPACK_SIZE;
275    else return mCarryInfo->scopeCarryDataSize;
276}
277
278
279
280Value * CarryManager::getCarryPack(unsigned packIndex) {
281    if (mCarryInPack[packIndex] == nullptr) {
282        Value * packPtr = mBuilder->CreateGEP(mCarryPackBasePtr, mBuilder->getInt64(packIndex));
283        // Save the computed pointer - so that it can be used in storeCarryPack.
284        mCarryPackPtr[packIndex] = packPtr;
285        mCarryInPack[packIndex] = mBuilder->CreateAlignedLoad(packPtr, mPACK_SIZE/8);
286    }
287    return mCarryInPack[packIndex];
288}
289
290void CarryManager::storeCarryPack(unsigned packIndex) {
291    mBuilder->CreateAlignedStore(mCarryOutPack[packIndex], mCarryPackPtr[packIndex], mPACK_SIZE/8);
292}
293
294   
295/* maskSelectBitRange selects the bits of a pack from lo_bit through
296   lo_bit + bitCount - 1, setting all other bits to zero.  */
297   
298Value * CarryManager::maskSelectBitRange(Value * pack, unsigned lo_bit, unsigned bitCount) {
299    if (bitCount == mPACK_SIZE) {
300        assert(lo_bit == 0);
301        return pack;
302    }
303    uint64_t mask = ((((uint64_t) 1) << bitCount) - 1) << lo_bit;
304    return mBuilder->CreateAnd(pack, mBuilder->getInt64(mask));
305}
306   
307Value * CarryManager::getCarryInBits(unsigned carryBitPos, unsigned carryBitCount) {
308    unsigned packIndex = carryBitPos / mPACK_SIZE;
309    unsigned packOffset = carryBitPos % mPACK_SIZE;
310    Value * selected = maskSelectBitRange(getCarryPack(packIndex), packOffset, carryBitCount);
311    if (packOffset == 0) return selected;
312    return mBuilder->CreateLShr(selected, packOffset);
313}
314
315void CarryManager::extractAndSaveCarryOutBits(Value * bitblock, unsigned carryBit_pos, unsigned carryBitCount) {
316    unsigned packIndex = carryBit_pos / mPACK_SIZE;
317    unsigned packOffset = carryBit_pos % mPACK_SIZE;
318    unsigned rshift = mPACK_SIZE - packOffset - carryBitCount;
319    uint64_t mask = ((((uint64_t) 1) << carryBitCount) - 1)  << packOffset;
320    //std::cerr << "extractAndSaveCarryOutBits: packIndex =" << packIndex << ", packOffset = " << packOffset << ", mask = " << mask << std::endl;
321    Value * field = iBuilder->mvmd_extract(mPACK_SIZE, bitblock, mBITBLOCK_WIDTH/mPACK_SIZE - 1);
322    //Value * field = maskSelectBitRange(field, PACK_SIZE - carryBitCount, carryBitCount);
323    if (rshift != 0) {
324        field = mBuilder->CreateLShr(field, mBuilder->getInt64(rshift));
325    }
326    if (packOffset != 0) {
327        field = mBuilder->CreateAnd(field, mBuilder->getInt64(mask));
328    }
329    if (mCarryOutPack[packIndex] == nullptr) {
330        mCarryOutPack[packIndex] = field;
331    }
332    else {
333        mCarryOutPack[packIndex] = mBuilder->CreateOr(mCarryOutPack[packIndex], field);
334    }
335}
336
337Value * CarryManager::pack2bitblock(Value * pack) {
338    return mBuilder->CreateBitCast(mBuilder->CreateZExt(pack, mBuilder->getIntNTy(mBITBLOCK_WIDTH)), mBitBlockType);
339}
340   
341   
342/* Methods for getting and setting individual carry values. */
343   
344Value * CarryManager::getCarryOpCarryIn(int localIndex) {
345    unsigned posn = carryOpPosition(localIndex);
346    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
347        return pack2bitblock(getCarryInBits(posn, 1));
348    }
349    else {
350        return getCarryPack(posn);
351    }
352}
353
354   
355void CarryManager::setCarryOpCarryOut(unsigned localIndex, Value * carry_out_strm) {
356    unsigned posn = carryOpPosition(localIndex);
357    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
358        extractAndSaveCarryOutBits(carry_out_strm, posn, 1);
359    }
360    else {
361        Value * carry_bit = mBuilder->CreateLShr(mBuilder->CreateBitCast(carry_out_strm, mBuilder->getIntNTy(mBITBLOCK_WIDTH)), mBITBLOCK_WIDTH-1);
362        mCarryOutPack[posn] = mBuilder->CreateBitCast(carry_bit, mBitBlockType);
363        if (mCarryInfo->getWhileDepth() == 0) {
364            storeCarryPack(posn);
365        }
366    }
367}
368
369Value* CarryManager::genShiftLeft64(Value* e) {
370    Value* i128_val = mBuilder->CreateBitCast(e, mBuilder->getIntNTy(mBITBLOCK_WIDTH));
371    return mBuilder->CreateBitCast(mBuilder->CreateShl(i128_val, 64), mBitBlockType);
372}
373
374Value * CarryManager::addCarryInCarryOut(int localIndex, Value* e1, Value* e2) {
375#if (mBITBLOCK_WIDTH == 128)
376    Value * carryq_value = getCarryOpCarryIn(localIndex);
377    //calculate carry through logical ops
378    Value* carrygen = mBuilder->CreateAnd(e1, e2, "carrygen");
379    Value* carryprop = mBuilder->CreateOr(e1, e2, "carryprop");
380    Value* digitsum = mBuilder->CreateAdd(e1, e2, "digitsum");
381    Value* partial = mBuilder->CreateAdd(digitsum, carryq_value, "partial");
382    Value* digitcarry = mBuilder->CreateOr(carrygen, mBuilder->CreateAnd(carryprop, mBuilder->CreateNot(partial)));
383    Value* mid_carry_in = genShiftLeft64(mBuilder->CreateLShr(digitcarry, 63));
384    Value* sum = mBuilder->CreateAdd(partial, mBuilder->CreateBitCast(mid_carry_in, mBitBlockType), "sum");
385    Value* carry_out_strm = mBuilder->CreateOr(carrygen, mBuilder->CreateAnd(carryprop, mBuilder->CreateNot(sum)));
386    setCarryOpCarryOut(localIndex, carry_out_strm);
387    return sum;
388#else
389    //mBITBLOCK_WIDTH == 256, there is no other implementation
390    Value * carryq_value = getCarryOpCarryIn(localIndex);
391    Value* carrygen = mBuilder->CreateAnd(e1, e2, "carrygen");
392    Value* carryprop = mBuilder->CreateOr(e1, e2, "carryprop");
393    Value * sum = iBuilder->simd_add(mBITBLOCK_WIDTH, iBuilder->simd_add(mBITBLOCK_WIDTH, e1, e2), carryq_value);
394    Value* carry_out_strm = mBuilder->CreateOr(carrygen, mBuilder->CreateAnd(carryprop, mBuilder->CreateNot(sum)));
395    setCarryOpCarryOut(localIndex, carry_out_strm);
396    return sum;
397#endif         
398}
399
400
401Value * CarryManager::advanceCarryInCarryOut(int localIndex, unsigned shift_amount, Value * strm) {
402    if (shift_amount == 1) {
403        return unitAdvanceCarryInCarryOut(localIndex, strm);
404    }
405    else if (shift_amount < LongAdvanceBase) {
406        return shortAdvanceCarryInCarryOut(localIndex, shift_amount, strm);
407    }
408    else {
409        return longAdvanceCarryInCarryOut(localIndex, shift_amount, strm);
410    }
411}
412
413Value * CarryManager::unitAdvanceCarryInCarryOut(int localIndex, Value * strm) {
414    unsigned posn = advance1Position(localIndex);
415    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
416        extractAndSaveCarryOutBits(strm, posn, 1);
417        Value* carry_longint = mBuilder->CreateZExt(getCarryInBits(posn, 1), mBuilder->getIntNTy(mBITBLOCK_WIDTH));
418        Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(mBITBLOCK_WIDTH));
419        Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, 1), carry_longint);
420        Value* result_value = mBuilder->CreateBitCast(adv_longint, mBitBlockType);
421        return result_value;
422    }
423    mCarryOutPack[posn] = strm;
424    Value * carry_in = getCarryPack(posn);
425    if (mCarryInfo->getWhileDepth() == 0) {
426        storeCarryPack(posn);
427    }
428    Value* result_value;
429   
430#if (mBITBLOCK_WIDTH == 128) && !defined(USE_LONG_INTEGER_SHIFT)
431    Value * ahead64 = iBuilder->mvmd_dslli(64, carry_in, strm, 1);
432    result_value = mBuilder->CreateOr(iBuilder->simd_srli(64, ahead64, 63), iBuilder->simd_slli(64, strm, 1));
433#else
434    Value* advanceq_longint = mBuilder->CreateBitCast(carry_in, mBuilder->getIntNTy(mBITBLOCK_WIDTH));
435    Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(mBITBLOCK_WIDTH));
436    Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, 1), mBuilder->CreateLShr(advanceq_longint, mBITBLOCK_WIDTH - 1), "advance");
437    result_value = mBuilder->CreateBitCast(adv_longint, mBitBlockType);
438   
439#endif
440    return result_value;
441}
442
443Value * CarryManager::shortAdvanceCarryInCarryOut(int localIndex, unsigned shift_amount, Value * strm) {
444    unsigned posn = shortAdvancePosition(localIndex);
445    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
446        extractAndSaveCarryOutBits(strm, posn, shift_amount);
447        //std::cerr << "shortAdvanceCarryInCarryOut: posn = " << posn << ", shift_amount = " << shift_amount << std::endl;
448        Value* carry_longint = mBuilder->CreateZExt(getCarryInBits(posn, shift_amount), mBuilder->getIntNTy(mBITBLOCK_WIDTH));
449        Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(mBITBLOCK_WIDTH));
450        Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, shift_amount), carry_longint);
451        Value* result_value = mBuilder->CreateBitCast(adv_longint, mBitBlockType);
452        return result_value;
453    }
454    mCarryOutPack[posn] = strm;
455    Value * carry_in = getCarryPack(posn);
456    if (mCarryInfo->getWhileDepth() == 0) {
457        storeCarryPack(posn);
458    }
459    Value* advanceq_longint = mBuilder->CreateBitCast(carry_in, mBuilder->getIntNTy(mBITBLOCK_WIDTH));
460    Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(mBITBLOCK_WIDTH));
461    Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, shift_amount), mBuilder->CreateLShr(advanceq_longint, mBITBLOCK_WIDTH - shift_amount), "advance");
462    return mBuilder->CreateBitCast(adv_longint, mBitBlockType);
463}
464   
465
466/*  currently defined in carry_data.h
467 
468 static unsigned power2ceil (unsigned v) {
469 unsigned ceil = 1;
470 while (ceil < v) ceil *= 2;
471 return ceil;
472 }
473 
474 unsigned longAdvanceEntries(unsigned shift_amount) const {
475 return (shift_amount + mBITBLOCK_WIDTH - 1)/mBITBLOCK_WIDTH;
476 }
477 
478 unsigned longAdvanceBufferSize(unsigned shift_amount)  const {
479 return power2ceil(longAdvanceEntries(shift_amount));
480 }
481 */
482
483   
484Value * CarryManager::longAdvanceCarryInCarryOut(int localIndex, unsigned shift_amount, Value * carry_out) {
485    unsigned carryDataIndex = longAdvanceBitBlockPosition(localIndex);
486    Value * advBaseIndex = mBuilder->getInt64(carryDataIndex);
487    if (shift_amount <= mBITBLOCK_WIDTH) {
488        // special case using a single buffer entry and the carry_out value.
489        Value * advanceDataPtr = mBuilder->CreateGEP(mCarryBitBlockPtr, advBaseIndex);
490        Value * carry_block0 = mBuilder->CreateAlignedLoad(advanceDataPtr, mBITBLOCK_WIDTH/8);
491        mBuilder->CreateAlignedStore(carry_out, advanceDataPtr, mBITBLOCK_WIDTH/8);
492        /* Very special case - no combine */
493        if (shift_amount == mBITBLOCK_WIDTH) return carry_block0;
494        Value* block0_shr = mBuilder->CreateLShr(mBuilder->CreateBitCast(carry_block0, mBuilder->getIntNTy(mBITBLOCK_WIDTH)), mBITBLOCK_WIDTH - shift_amount);
495        Value* block1_shl = mBuilder->CreateShl(mBuilder->CreateBitCast(carry_out, mBuilder->getIntNTy(mBITBLOCK_WIDTH)), shift_amount);
496        return mBuilder->CreateBitCast(mBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
497    }
498    // We need a buffer of at least two elements for storing the advance data.
499    const unsigned block_shift = shift_amount % mBITBLOCK_WIDTH;
500    const unsigned advanceEntries = mCarryInfo->longAdvanceEntries(shift_amount);
501    const unsigned bufsize = mCarryInfo->longAdvanceBufferSize(shift_amount);
502    Value * indexMask = mBuilder->getInt64(bufsize - 1);  // A mask to implement circular buffer indexing
503    Value * loadIndex0 = mBuilder->CreateAdd(mBuilder->CreateAnd(mBuilder->CreateSub(mBlockNo, mBuilder->getInt64(advanceEntries)), indexMask), advBaseIndex);
504    Value * storeIndex = mBuilder->CreateAdd(mBuilder->CreateAnd(mBlockNo, indexMask), advBaseIndex);
505    Value * carry_block0 = mBuilder->CreateAlignedLoad(mBuilder->CreateGEP(mCarryBitBlockPtr, loadIndex0), mBITBLOCK_WIDTH/8);
506    // If the long advance is an exact multiple of mBITBLOCK_WIDTH, we simply return the oldest
507    // block in the long advance carry data area. 
508    if (block_shift == 0) {
509        mBuilder->CreateAlignedStore(carry_out, mBuilder->CreateGEP(mCarryBitBlockPtr, storeIndex), mBITBLOCK_WIDTH/8);
510        return carry_block0;
511    }
512    // Otherwise we need to combine data from the two oldest blocks.
513    Value * loadIndex1 = mBuilder->CreateAdd(mBuilder->CreateAnd(mBuilder->CreateSub(mBlockNo, mBuilder->getInt64(advanceEntries-1)), indexMask), advBaseIndex);
514    Value * carry_block1 = mBuilder->CreateAlignedLoad(mBuilder->CreateGEP(mCarryBitBlockPtr, loadIndex1), mBITBLOCK_WIDTH/8);
515    Value* block0_shr = mBuilder->CreateLShr(mBuilder->CreateBitCast(carry_block0, mBuilder->getIntNTy(mBITBLOCK_WIDTH)), mBITBLOCK_WIDTH - block_shift);
516    Value* block1_shl = mBuilder->CreateShl(mBuilder->CreateBitCast(carry_block1, mBuilder->getIntNTy(mBITBLOCK_WIDTH)), block_shift);
517    mBuilder->CreateAlignedStore(carry_out, mBuilder->CreateGEP(mCarryBitBlockPtr, storeIndex), mBITBLOCK_WIDTH/8);
518    return mBuilder->CreateBitCast(mBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
519}
520   
521
522/* Methods for getting and setting carry summary values */
523   
524bool CarryManager::blockHasCarries(){
525    return mCarryInfo->blockHasCarries();
526} 
527
528
529Value * CarryManager::getCarrySummaryExpr() {
530    unsigned summary_index = summaryPackIndex();
531    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
532        Value * pack = getCarryPack(summary_index);
533        Value * summary_bits = maskSelectBitRange(pack, summaryPosition() % mPACK_SIZE, summaryBits());
534        return mBuilder->CreateBitCast(mBuilder->CreateZExt(summary_bits, mBuilder->getIntNTy(mBITBLOCK_WIDTH)), mBitBlockType);
535    }
536    else {
537        return getCarryPack(summary_index);
538    }
539}
540
541void CarryManager::initializeCarryDataAtIfEntry() {
542    if (blockHasCarries()) {
543        if (mCarryOutPack[scopeBasePack()] == nullptr) {
544            mCarryInfo->ifEntryPack = mPackBuilder->allZeroes();
545        }
546        else {
547            mCarryInfo->ifEntryPack = mCarryOutPack[scopeBasePack()];
548        }
549    }
550}
551   
552void CarryManager::buildCarryDataPhisAfterIfBody(BasicBlock * ifEntryBlock, BasicBlock * ifBodyFinalBlock) {
553    if (mCarryInfo->getWhileDepth() > 0) {
554        // We need to phi out everything for the while carry accumulation process.
555        const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
556        const unsigned currentScopeBase = scopeBasePack();
557        for (unsigned index = currentScopeBase; index < currentScopeBase + scopeCarryPacks; ++index) {
558            PHINode * phi_out = mBuilder->CreatePHI(mCarryPackType, 2);
559            phi_out->addIncoming(mPackBuilder->allZeroes(),ifEntryBlock);
560            phi_out->addIncoming(mCarryOutPack[index],ifBodyFinalBlock);
561            mCarryOutPack[index] = phi_out;
562        }
563        return;
564    }
565    unsigned const ifScopeCarrySize = mCarryInfo->scopeCarryDataSize;
566    if (ifScopeCarrySize == 0) {
567        // No carry data, therefore no phi nodes.
568        return;
569    }
570    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
571        if (ifScopeCarrySize <= mPACK_SIZE) {
572            unsigned const ifPackIndex = scopeBasePack();
573            PHINode * ifPack_phi = mBuilder->CreatePHI(mCarryPackType, 2, "ifPack");
574            ifPack_phi->addIncoming(mCarryInfo->ifEntryPack, ifEntryBlock);
575            ifPack_phi->addIncoming(mCarryOutPack[ifPackIndex], ifBodyFinalBlock);
576            mCarryOutPack[ifPackIndex] = ifPack_phi;
577            return;
578        }
579    }
580    if (mCarryInfo->getIfDepth() > 1) {
581        // Our parent block is also an if.  It needs access to our summary to compute
582        // its own summary.
583        const unsigned summaryIndex = summaryPackIndex();
584        PHINode * summary_phi = mBuilder->CreatePHI(mCarryPackType, 2, "summary");
585        summary_phi->addIncoming(mPackBuilder->allZeroes(), ifEntryBlock);
586        summary_phi->addIncoming(mCarryOutPack[summaryIndex], ifBodyFinalBlock);
587        mCarryOutPack[summaryIndex] = summary_phi;
588    }
589}
590   
591void CarryManager::addSummaryPhiIfNeeded(BasicBlock * ifEntryBlock, BasicBlock * ifBodyFinalBlock) {
592    if ((mCarryInfo->getIfDepth() <= 1) || !mCarryInfo->blockHasCarries()){
593        // For ifDepth == 1, the parent does not need a summary as it is not itself within an if.
594        // Therefore, it doesn't need access to this block's summary in building its own.
595        return;
596    }
597    const unsigned carrySummaryIndex = summaryPackIndex();
598    PHINode * summary_phi = mBuilder->CreatePHI(mCarryPackType, 2, "summary");
599    summary_phi->addIncoming(mPackBuilder->allZeroes(), ifEntryBlock);
600    summary_phi->addIncoming(mCarryOutPack[carrySummaryIndex], ifBodyFinalBlock);
601    mCarryOutPack[carrySummaryIndex] = summary_phi;
602}
603   
604void CarryManager::generateCarryOutSummaryCodeIfNeeded() {
605   
606    if (!mCarryInfo->explicitSummaryRequired()) {
607        // An explicit summary may not be required, if there is a single carry
608        // operation within the block, or the carries are packed and all carry
609        // bits fit within a single pack.
610        return;
611    }
612   
613    const unsigned carrySummaryIndex = summaryPackIndex();
614   
615    Value * carry_summary = mPackBuilder->allZeroes();
616    if (mCarryInfo->blockHasLongAdvances()) { // Force if entry
617        carry_summary = mPackBuilder->allOnes();
618    }
619    else {
620        unsigned localCarryIndex = localBasePack();
621        unsigned localCarryPacks = mCarryInfo->getLocalCarryPackCount();
622        if (localCarryPacks > 0) {
623            carry_summary = mCarryOutPack[localCarryIndex];
624            for (unsigned i = 1; i < localCarryPacks; i++) {
625                carry_summary = mBuilder->CreateOr(carry_summary, mCarryOutPack[localCarryIndex+i]);
626            }
627        }
628        for (Statement * stmt : *mCurrentScope) {
629            if (If * innerIf = dyn_cast<If>(stmt)) {
630                PabloBlock * inner_blk = & innerIf->getBody();
631                enterScope(inner_blk);
632                if (blockHasCarries()) {
633                  carry_summary = mBuilder->CreateOr(carry_summary, mCarryOutPack[summaryPackIndex()]);
634                }
635                leaveScope();
636            }
637            else if (While * innerWhile = dyn_cast<While>(stmt)) {
638                PabloBlock * inner_blk = & innerWhile->getBody();
639                enterScope(inner_blk);
640                if (blockHasCarries()) {
641                    carry_summary = mBuilder->CreateOr(carry_summary, mCarryOutPack[summaryPackIndex()]);
642                }
643                leaveScope();
644            }
645        }
646    }
647    // Calculation of the carry out summary is complete.   Store it and make it
648    // available in case it must included by parent blocks.
649    mCarryOutPack[carrySummaryIndex] = carry_summary;
650    storeCarryPack(carrySummaryIndex);
651}
652
653void CarryManager::ensureCarriesLoadedRecursive() {
654    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
655    const unsigned currentScopeBase = scopeBasePack();
656    if (mCarryInfo->getWhileDepth() == 1) {
657        for (auto i = currentScopeBase; i < currentScopeBase + scopeCarryPacks; ++i) {
658            getCarryPack(i);
659        }
660    }
661}
662
663
664void CarryManager::initializeCarryDataPhisAtWhileEntry(BasicBlock * whileEntryBlock) {
665    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
666    mCarryOutAccumPhis.resize(scopeCarryPacks);
667#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
668    const unsigned currentScopeBase = scopeBasePack();
669    mCarryInPhis.resize(scopeCarryPacks);
670#endif
671    for (unsigned index = 0; index < scopeCarryPacks; ++index) {
672#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
673        PHINode * phi_in = mBuilder->CreatePHI(mCarryPackType, 2);
674        phi_in->addIncoming(mCarryInPack[currentScopeBase+index], whileEntryBlock);
675        mCarryInPhis[index] = phi_in;
676#endif
677        PHINode * phi_out = mBuilder->CreatePHI(mCarryPackType, 2);
678        phi_out->addIncoming(mPackBuilder->allZeroes(), whileEntryBlock);
679        mCarryOutAccumPhis[index] = phi_out;
680    }
681}
682
683
684void CarryManager::extendCarryDataPhisAtWhileBodyFinalBlock(BasicBlock * whileBodyFinalBlock) {
685    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
686    const unsigned currentScopeBase = scopeBasePack();
687    for (unsigned index = 0; index < scopeCarryPacks; ++index) {
688#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
689        mCarryInPhis[index]->addIncoming(mPackBuilder->allZeroes(), whileBodyFinalBlock);
690#endif
691        PHINode * phi = mCarryOutAccumPhis[index];
692        Value * carryOut = mBuilder->CreateOr(phi, mCarryOutPack[currentScopeBase+index]);
693        phi->addIncoming(carryOut, whileBodyFinalBlock);
694        mCarryOutPack[currentScopeBase+index] = carryOut;
695    }
696}
697
698void CarryManager::ensureCarriesStoredRecursive() {
699    const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
700    const unsigned currentScopeBase = scopeBasePack();
701    if (mCarryInfo->getWhileDepth() == 1) {
702        for (auto i = currentScopeBase; i < currentScopeBase + scopeCarryPacks; ++i) {
703            storeCarryPack(i);
704        }
705    }
706}
707
708/* Store all the full carry packs generated locally in this scope or the
709   single full pack for this scope*/
710void CarryManager::ensureCarriesStoredLocal() {
711    if (mITEMS_PER_PACK > 1) {// #ifdef PACKING
712        const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
713        if ((scopeCarryPacks > 0) && ((mCurrentFrameIndex % mPACK_SIZE) == 0)) {
714            // We have carry data and we are not in the middle of a pack.
715            // Write out all local packs.
716            auto localCarryIndex = localBasePack();
717            auto localCarryPacks = mCarryInfo->getLocalCarryPackCount();
718            for (auto i = localCarryIndex; i < localCarryIndex + localCarryPacks; i++) {
719                storeCarryPack(i);
720            }
721            if ((localCarryPacks == 0) && (scopeCarryPacks == 1) && (mCarryInfo->nested.entries > 1)) {
722                storeCarryPack(localCarryIndex);
723            }
724        }
725    }
726}
727
728Value * CarryManager::popCount(Value * to_count, unsigned globalIdx) {
729    Value * countPtr = mBuilder->CreateGEP(mPopcountBasePtr, mBuilder->getInt64(globalIdx));
730    Value * countSoFar = mBuilder->CreateAlignedLoad(countPtr, 8);
731    Value * fieldCounts = iBuilder->simd_popcount(64, to_count);
732    for (int i = 0; i < mBITBLOCK_WIDTH/64; i++) {
733        countSoFar = mBuilder->CreateAdd(countSoFar, iBuilder->mvmd_extract(64, fieldCounts, i));
734    }
735    mBuilder->CreateAlignedStore(countSoFar, countPtr, 8);
736    return mBuilder->CreateBitCast(mBuilder->CreateZExt(countSoFar, mBuilder->getIntNTy(mBITBLOCK_WIDTH)), mBitBlockType);
737}
738
739CarryManager::~CarryManager() {
740    for (auto * cd : mCarryInfoVector) {
741        delete cd;
742    }
743}
744
745}
746
Note: See TracBrowser for help on using the repository browser.