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

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

Prepare for non-bitblock carry summaries; use IDISA bitblock_any

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