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

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

Initial check of carry manager - not yet enabled

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