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

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

Carry Manager progress

File size: 16.2 KB
RevLine 
[4644]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 <carry_data.h>
11#include <codegenstate.h>
12#include <carry_manager.h>
13#include <pabloAST.h>
[4647]14#include <iostream>
[4644]15
16namespace pablo {
17 
18
19unsigned CarryManager::initialize(PabloBlock * pb, Value * carryPtr) {
20 
21    mPabloRoot = pb;
[4670]22    mCurrentScope = pb;
23    mCurrentScopeIndex = 0;
24   
[4644]25    mCarryDataPtr = carryPtr;
[4670]26    mCarryInfo = &(pb->carryData);
27    mTotalCarryDataSize = mCarryInfo->enumerate(*pb)/BLOCK_SIZE + 1;   // One extra element for the block no.
[4644]28    mBlockNoPtr = mBuilder->CreateBitCast(mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(mTotalCarryDataSize - 1)), Type::getInt64PtrTy(mBuilder->getContext()));
29    mBlockNo = mBuilder->CreateLoad(mBlockNoPtr);
30    mCarryInVector.resize(mTotalCarryDataSize);
31    mCarryInPhis.resize(mTotalCarryDataSize);
32    mCarryOutAccumPhis.resize(mTotalCarryDataSize);
33    mCarryOutVector.resize(mTotalCarryDataSize);
34   
35    return mTotalCarryDataSize;
36}
37
38void CarryManager::generateBlockNoIncrement() {
39    mBuilder->CreateStore(mBuilder->CreateAdd(mBlockNo, mBuilder->getInt64(1)), mBlockNoPtr);
40}
41
42Value * CarryManager::getBlockNoPtr() {
43    return mBlockNoPtr;
44}
45
[4670]46/* Entering and leaving blocks. */
[4644]47
[4670]48void CarryManager::enterScope(PabloBlock * blk) {
49   
50    mCurrentScope = blk;
51    mCarryInfo = & (blk->carryData);
52    mCurrentScopeIndex += mCarryInfo->getBlockCarryDataIndex();
53    //std::cerr << "enterScope:  mCurrentScopeIndex = " << mCurrentScopeIndex << std::endl;
54}
55
56void CarryManager::leaveScope() {
57    mCurrentScopeIndex -= mCarryInfo->getBlockCarryDataIndex();
58    mCurrentScope = mCurrentScope->getParent();
59    mCarryInfo = & (mCurrentScope->carryData);
60    //std::cerr << "leaveScope:  mCurrentScopeIndex = " << mCurrentScopeIndex << std::endl;
61}
62
63
64
[4644]65    /* Methods for getting and setting individual carry values. */
66   
[4670]67Value * CarryManager::getCarryOpCarryIn(int localIndex) {
68    if (mCarryInfo->getWhileDepth() == 0) {
69       Value * packPtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(mCurrentScopeIndex + mCarryInfo->carryOpCarryDataOffset(localIndex)));
70       mCarryInVector[mCarryInfo->carryOpCarryDataOffset(localIndex)] = mBuilder->CreateAlignedLoad(packPtr, BLOCK_SIZE/8);
[4647]71    }
[4670]72    return mCarryInVector[mCarryInfo->carryOpCarryDataOffset(localIndex)];
[4644]73}
74
[4670]75void CarryManager::setCarryOpCarryOut(unsigned localIndex, Value * carry_out) {
76    unsigned cd_index = mCurrentScopeIndex + mCarryInfo->carryOpCarryDataOffset(localIndex);
77    mCarryOutVector[cd_index] = carry_out;
78    if (mCarryInfo->getWhileDepth() == 0) {
79       Value * packPtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(cd_index));
[4654]80       mBuilder->CreateAlignedStore(carry_out, packPtr, BLOCK_SIZE/8);
[4647]81    }
[4644]82}
83
[4654]84   
[4670]85Value * CarryManager::advanceCarryInCarryOut(int localIndex, int shift_amount, Value * strm) {
[4654]86    if (shift_amount == 1) {
[4670]87        return unitAdvanceCarryInCarryOut(localIndex, strm);
[4647]88    }
[4654]89    else if (shift_amount < LongAdvanceBase) {
[4670]90        return shortAdvanceCarryInCarryOut(localIndex, shift_amount, strm);
[4654]91    }
92    else {
[4670]93        return longAdvanceCarryInCarryOut(localIndex, shift_amount, strm);
[4654]94    }
[4644]95}
96
[4670]97Value * CarryManager::unitAdvanceCarryInCarryOut(int localIndex, Value * strm) {
98    unsigned carryDataIndex = mCurrentScopeIndex + mCarryInfo->unitAdvanceCarryDataOffset(localIndex);
[4654]99    mCarryOutVector[carryDataIndex] = strm; 
[4670]100    if (mCarryInfo->getWhileDepth() == 0) {
[4654]101        Value * packPtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(carryDataIndex));
102        mCarryInVector[carryDataIndex] = mBuilder->CreateAlignedLoad(packPtr, BLOCK_SIZE/8);
103        mBuilder->CreateAlignedStore(strm, packPtr, BLOCK_SIZE/8);
104       
[4647]105    }
[4654]106    Value * carry_in = mCarryInVector[carryDataIndex];
107    Value* result_value;
108   
109#if (BLOCK_SIZE == 128) && !defined(USE_LONG_INTEGER_SHIFT)
[4663]110    Value * ahead64 = iBuilder->mvmd_dslli(64, carry_in, strm, 1);
111    result_value = mBuilder->CreateOr(iBuilder->simd_srli(64, ahead64, 63), iBuilder->simd_slli(64, strm, 1));
[4654]112#else
113    Value* advanceq_longint = mBuilder->CreateBitCast(carry_in, mBuilder->getIntNTy(BLOCK_SIZE));
114    Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(BLOCK_SIZE));
115    Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, 1), mBuilder->CreateLShr(advanceq_longint, BLOCK_SIZE - 1), "advance");
116    result_value = mBuilder->CreateBitCast(adv_longint, mBitBlockType);
117   
118#endif
119    return result_value;
[4644]120}
121
[4670]122Value * CarryManager::shortAdvanceCarryInCarryOut(int localIndex, int shift_amount, Value * strm) {
123    unsigned carryDataIndex = mCurrentScopeIndex + mCarryInfo->shortAdvanceCarryDataOffset(localIndex);
[4654]124    mCarryOutVector[carryDataIndex] = strm; 
[4670]125    if (mCarryInfo->getWhileDepth() == 0) {
[4654]126        Value * packPtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(carryDataIndex));
127        mCarryInVector[carryDataIndex] = mBuilder->CreateAlignedLoad(packPtr, BLOCK_SIZE/8);
128        mBuilder->CreateAlignedStore(strm, packPtr, BLOCK_SIZE/8);
129       
[4647]130    }
[4654]131    Value * carry_in = mCarryInVector[carryDataIndex];
132    Value* advanceq_longint = mBuilder->CreateBitCast(carry_in, mBuilder->getIntNTy(BLOCK_SIZE));
133    Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(BLOCK_SIZE));
134    Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, shift_amount), mBuilder->CreateLShr(advanceq_longint, BLOCK_SIZE - shift_amount), "advance");
135    return mBuilder->CreateBitCast(adv_longint, mBitBlockType);
[4644]136}
[4654]137   
[4647]138
[4654]139/*  currently defined in carry_data.h
140 
[4647]141 static unsigned power2ceil (unsigned v) {
142 unsigned ceil = 1;
143 while (ceil < v) ceil *= 2;
144 return ceil;
145 }
146 
147 unsigned longAdvanceEntries(unsigned shift_amount) const {
148 return (shift_amount + BLOCK_SIZE - 1)/BLOCK_SIZE;
149 }
150 
151 unsigned longAdvanceBufferSize(unsigned shift_amount)  const {
152 return power2ceil(longAdvanceEntries(shift_amount));
153 }
154 */
[4644]155
[4654]156   
[4670]157Value * CarryManager::longAdvanceCarryInCarryOut(int localIndex, int shift_amount, Value * carry_out) {
158    unsigned carryDataIndex = mCurrentScopeIndex + mCarryInfo->longAdvanceCarryDataOffset(localIndex);
159    Value * advBaseIndex = mBuilder->getInt64(carryDataIndex);
[4647]160    if (shift_amount <= BLOCK_SIZE) {
161        // special case using a single buffer entry and the carry_out value.
162        Value * advanceDataPtr = mBuilder->CreateGEP(mCarryDataPtr, advBaseIndex);
163        Value * carry_block0 = mBuilder->CreateAlignedLoad(advanceDataPtr, BLOCK_SIZE/8);
164        mBuilder->CreateAlignedStore(carry_out, advanceDataPtr, BLOCK_SIZE/8);
165        /* Very special case - no combine */
166        if (shift_amount == BLOCK_SIZE) return carry_block0;
167        Value* block0_shr = mBuilder->CreateLShr(mBuilder->CreateBitCast(carry_block0, mBuilder->getIntNTy(BLOCK_SIZE)), BLOCK_SIZE - shift_amount);
168        Value* block1_shl = mBuilder->CreateShl(mBuilder->CreateBitCast(carry_out, mBuilder->getIntNTy(BLOCK_SIZE)), shift_amount);
169        return mBuilder->CreateBitCast(mBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
170    }
171    // We need a buffer of at least two elements for storing the advance data.
[4644]172    const unsigned block_shift = shift_amount % BLOCK_SIZE;
[4670]173    const unsigned advanceEntries = mCarryInfo->longAdvanceEntries(shift_amount);
174    const unsigned bufsize = mCarryInfo->longAdvanceBufferSize(shift_amount);
[4644]175    Value * indexMask = mBuilder->getInt64(bufsize - 1);  // A mask to implement circular buffer indexing
176    Value * loadIndex0 = mBuilder->CreateAdd(mBuilder->CreateAnd(mBuilder->CreateSub(mBlockNo, mBuilder->getInt64(advanceEntries)), indexMask), advBaseIndex);
[4647]177    Value * storeIndex = mBuilder->CreateAdd(mBuilder->CreateAnd(mBlockNo, indexMask), advBaseIndex);
[4644]178    Value * carry_block0 = mBuilder->CreateAlignedLoad(mBuilder->CreateGEP(mCarryDataPtr, loadIndex0), BLOCK_SIZE/8);
179    // If the long advance is an exact multiple of BLOCK_SIZE, we simply return the oldest
[4647]180    // block in the long advance carry data area. 
181    if (block_shift == 0) {
182        mBuilder->CreateAlignedStore(carry_out, mBuilder->CreateGEP(mCarryDataPtr, storeIndex), BLOCK_SIZE/8);
183        return carry_block0;
[4644]184    }
185    // Otherwise we need to combine data from the two oldest blocks.
186    Value * loadIndex1 = mBuilder->CreateAdd(mBuilder->CreateAnd(mBuilder->CreateSub(mBlockNo, mBuilder->getInt64(advanceEntries-1)), indexMask), advBaseIndex);
187    Value * carry_block1 = mBuilder->CreateAlignedLoad(mBuilder->CreateGEP(mCarryDataPtr, loadIndex1), BLOCK_SIZE/8);
[4647]188    Value* block0_shr = mBuilder->CreateLShr(mBuilder->CreateBitCast(carry_block0, mBuilder->getIntNTy(BLOCK_SIZE)), BLOCK_SIZE - block_shift);
[4644]189    Value* block1_shl = mBuilder->CreateShl(mBuilder->CreateBitCast(carry_block1, mBuilder->getIntNTy(BLOCK_SIZE)), block_shift);
[4647]190    mBuilder->CreateAlignedStore(carry_out, mBuilder->CreateGEP(mCarryDataPtr, storeIndex), BLOCK_SIZE/8);
[4644]191    return mBuilder->CreateBitCast(mBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
192}
[4647]193   
[4644]194
195/* Methods for getting and setting carry summary values */
196   
[4670]197bool CarryManager::blockHasCarries(){
198    return mCarryInfo->blockHasCarries();
[4644]199} 
200
[4670]201
202Value * CarryManager::getCarrySummaryExpr() {
203    unsigned summary_idx = mCurrentScopeIndex + mCarryInfo->summaryCarryDataIndex();
204    Value * packPtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(summary_idx));
[4644]205    Value * summary_expr = mBuilder->CreateAlignedLoad(packPtr, BLOCK_SIZE/8);
206    // If the totalCarryDataSize is 1, then the carry summary is also the pack expr.
[4670]207    mCarryInVector[summary_idx] = summary_expr;
[4644]208    return summary_expr;
209}
210
[4670]211bool CarryManager::summaryNeededInParentBlock(){
212    return mCarryInfo->summaryNeededInParentBlock();
[4644]213} 
214
[4670]215void CarryManager::addSummaryPhi(BasicBlock * ifEntryBlock, BasicBlock * ifBodyFinalBlock) {
216    const unsigned carrySummaryIndex = mCurrentScopeIndex + mCarryInfo->summaryCarryDataIndex();
[4644]217    PHINode * summary_phi = mBuilder->CreatePHI(mBitBlockType, 2, "summary");
218    summary_phi->addIncoming(mZeroInitializer, ifEntryBlock);
219    summary_phi->addIncoming(mCarryOutVector[carrySummaryIndex], ifBodyFinalBlock);
220    mCarryOutVector[carrySummaryIndex] = summary_phi;
221}
222
[4670]223void CarryManager::generateCarryOutSummaryCode() {
[4644]224   
[4670]225    const unsigned carrySummaryIndex = mCurrentScopeIndex + mCarryInfo->summaryCarryDataIndex();
[4644]226   
[4670]227    if (mCarryInfo->getTotalCarryDataSize() == 1) {
[4644]228        // If totalCarryDataSize == 1, then we have one pack which serves as
229        // the summary.   It should already be stored.   
230        return;
231    }
232   
233    Value * carry_summary = mZeroInitializer;
234   
[4670]235    if (mCarryInfo->blockHasLongAdvances()) { // Force if entry
[4644]236        carry_summary = mOneInitializer;
237    }
238    else {
[4670]239        auto localCarryPacks = mCarryInfo->getLocalCarryDataSize();
[4644]240        if (localCarryPacks > 0) {
[4670]241            carry_summary = mCarryOutVector[mCurrentScopeIndex];
[4644]242            for (auto i = 1; i < localCarryPacks; i++) {
243                //carry_summary = mBuilder->CreateOr(carry_summary, mPabloBlock->mCarryOutPack[i]);           
[4670]244                carry_summary = mBuilder->CreateOr(carry_summary, mCarryOutVector[mCurrentScopeIndex+i]);
[4644]245            }
[4647]246        }
[4670]247        for (Statement * stmt : *mCurrentScope) {
[4644]248            if (If * innerIf = dyn_cast<If>(stmt)) {
[4670]249                PabloBlock * inner_blk = & innerIf->getBody();
250                enterScope(inner_blk);
251                if (blockHasCarries()) {
252                  carry_summary = mBuilder->CreateOr(carry_summary, mCarryOutVector[mCurrentScopeIndex + mCarryInfo->summaryCarryDataIndex()]);
[4644]253                }
[4670]254                leaveScope();
[4644]255            }
256            else if (While * innerWhile = dyn_cast<While>(stmt)) {
[4670]257                PabloBlock * inner_blk = & innerWhile->getBody();
258                enterScope(inner_blk);
259                if (blockHasCarries()) {
260                    carry_summary = mBuilder->CreateOr(carry_summary, mCarryOutVector[mCurrentScopeIndex + mCarryInfo->summaryCarryDataIndex()]);
261                }
262                leaveScope();
[4644]263            }
264        }
265    }
266    // Calculation of the carry out summary is complete.   Store it and make it
267    // available in case it must included by parent blocks.
268    mCarryOutVector[carrySummaryIndex] = carry_summary;
269    Value * packPtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(carrySummaryIndex));
270    mBuilder->CreateAlignedStore(carry_summary, packPtr, BLOCK_SIZE/8);
271}
272
[4670]273void CarryManager::ensureCarriesLoadedLocal() {
[4647]274#if 0
[4644]275    const PabloBlockCarryData & cd = blk.carryData;
276    const unsigned baseCarryDataIdx = cd.getBlockCarryDataIndex();
277    const unsigned localCarryDataSize = cd.getLocalCarryDataSize();
278    const unsigned totalCarryDataSize = cd.getTotalCarryDataSize();
279    if (totalCarryDataSize == 0) return;
280    if ((cd.getIfDepth() > 0) && (totalCarryDataSize == 1)) return;
281    if (cd.getWhileDepth() > 0) return;
282    for (auto i = baseCarryDataIdx; i < baseCarryDataIdx + localCarryDataSize; ++i) {
283        mCarryInVector[i] = mBuilder->CreateAlignedLoad(mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(i)), BLOCK_SIZE/8, false);
284    }
[4647]285#endif
[4644]286}
287
[4670]288void CarryManager::ensureCarriesStoredLocal() {
[4647]289#if 0
[4644]290    const PabloBlockCarryData & cd = blk.carryData;
291    const unsigned baseCarryDataIdx = cd.getBlockCarryDataIndex();
292    const unsigned localCarryDataSize = cd.getLocalCarryDataSize();
293    const unsigned totalCarryDataSize = cd.getTotalCarryDataSize();
294    const unsigned carrySummaryIndex = cd.summaryCarryDataIndex();
295    if (totalCarryDataSize == 0) return;
296    if (cd.getWhileDepth() > 0) return;
297    for (auto i = baseCarryDataIdx; i < baseCarryDataIdx + localCarryDataSize; ++i) {
298        Value * storePtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(i));
299        mBuilder->CreateAlignedStore(mCarryOutVector[i], storePtr, BLOCK_SIZE/8, false);
300    }
301    if (totalCarryDataSize > 1) {
302        Value * summaryPtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(carrySummaryIndex));
303        mBuilder->CreateAlignedStore(mCarryOutVector[carrySummaryIndex], summaryPtr, BLOCK_SIZE/8, false);
304    }
[4647]305#endif
[4644]306}
307
308
[4670]309
310void CarryManager::ensureCarriesLoadedRecursive() {
311    const unsigned totalCarryDataSize = mCarryInfo->getTotalCarryDataSize();
312    if (mCarryInfo->getWhileDepth() == 1) {
313        for (auto i = mCurrentScopeIndex; i < mCurrentScopeIndex + totalCarryDataSize; ++i) {
[4644]314            mCarryInVector[i] = mBuilder->CreateAlignedLoad(mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(i)), BLOCK_SIZE/8, false);
315        }
316    }
317}
318
319
[4670]320void CarryManager::initializeCarryDataPhisAtWhileEntry(BasicBlock * whileEntryBlock) {
321    const unsigned totalCarryDataSize = mCarryInfo->getTotalCarryDataSize();
322    for (unsigned index = mCurrentScopeIndex; index < mCurrentScopeIndex + totalCarryDataSize; ++index) {
[4644]323#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
324        PHINode * phi_in = mBuilder->CreatePHI(mBitBlockType, 2);
325        phi_in->addIncoming(mCarryInVector[index], whileEntryBlock);
326        mCarryInPhis[index] = phi_in;
327#endif
328        PHINode * phi_out = mBuilder->CreatePHI(mBitBlockType, 2);
329        phi_out->addIncoming(mZeroInitializer, whileEntryBlock);
330        mCarryOutAccumPhis[index] = phi_out;
331    }
332}
333
334
[4670]335void CarryManager::extendCarryDataPhisAtWhileBodyFinalBlock(BasicBlock * whileBodyFinalBlock) {
336    const unsigned totalCarryDataSize = mCarryInfo->getTotalCarryDataSize();
337    for (unsigned index = mCurrentScopeIndex; index < mCurrentScopeIndex + totalCarryDataSize; ++index) {
[4644]338#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
339        mCarryInPhis[index]->addIncoming(mZeroInitializer, whileBodyFinalBlock);
340#endif
341        PHINode * phi = mCarryOutAccumPhis[index];
342        Value * carryOut = mBuilder->CreateOr(phi, mCarryOutVector[index]);
343        phi->addIncoming(carryOut, whileBodyFinalBlock);
344        mCarryOutVector[index] = carryOut;
345    }
346}
347
[4670]348void CarryManager::ensureCarriesStoredRecursive() {
349    const unsigned totalCarryDataSize = mCarryInfo->getTotalCarryDataSize();
350    if (mCarryInfo->getWhileDepth() == 1) {
351        for (auto i = mCurrentScopeIndex; i < mCurrentScopeIndex + totalCarryDataSize; ++i) {
[4644]352            Value * storePtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(i));
353            mBuilder->CreateAlignedStore(mCarryOutVector[i], storePtr, BLOCK_SIZE/8, false);
354        }
355    }
356}
357
358}
359
Note: See TracBrowser for help on using the repository browser.