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

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

Clean-ups

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