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

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

Carry Manager system integrated into Pablo compiler

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