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

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

Move logic for advance operations entirely within carry manager.

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