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

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

Use #include <pablo/...> syntax uniformally for all pablo headers

File size: 16.8 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 <pablo/carry_data.h>
11#include <pablo/codegenstate.h>
12#include <pablo/carry_manager.h>
13#include <pablo/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    /* Methods for getting and setting individual carry values. */
65   
66//#define LOAD_STORE_ON_BLOCK_ENTRY_EXIT   
67Value * CarryManager::getCarryOpCarryIn(int localIndex) {
68    unsigned cd_index = mCurrentScopeIndex + mCarryInfo->carryOpCarryDataOffset(localIndex);
69#ifndef LOAD_STORE_ON_BLOCK_ENTRY_EXIT
70    if (mCarryInfo->getWhileDepth() == 0) {
71       Value * packPtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(cd_index));
72       mCarryInVector[cd_index] = mBuilder->CreateAlignedLoad(packPtr, BLOCK_SIZE/8);
73    }
74#endif
75    return mCarryInVector[cd_index];
76}
77
78void CarryManager::setCarryOpCarryOut(unsigned localIndex, Value * carry_out) {
79    unsigned cd_index = mCurrentScopeIndex + mCarryInfo->carryOpCarryDataOffset(localIndex);
80    mCarryOutVector[cd_index] = carry_out;
81#ifndef LOAD_STORE_ON_BLOCK_ENTRY_EXIT
82    if (mCarryInfo->getWhileDepth() == 0) {
83       Value * packPtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(cd_index));
84       mBuilder->CreateAlignedStore(carry_out, packPtr, BLOCK_SIZE/8);
85    }
86#endif
87}
88
89   
90Value * CarryManager::advanceCarryInCarryOut(int localIndex, int shift_amount, Value * strm) {
91    if (shift_amount == 1) {
92        return unitAdvanceCarryInCarryOut(localIndex, strm);
93    }
94    else if (shift_amount < LongAdvanceBase) {
95        return shortAdvanceCarryInCarryOut(localIndex, shift_amount, strm);
96    }
97    else {
98        return longAdvanceCarryInCarryOut(localIndex, shift_amount, strm);
99    }
100}
101
102Value * CarryManager::unitAdvanceCarryInCarryOut(int localIndex, Value * strm) {
103    unsigned carryDataIndex = mCurrentScopeIndex + mCarryInfo->unitAdvanceCarryDataOffset(localIndex);
104    mCarryOutVector[carryDataIndex] = strm; 
105#ifndef LOAD_STORE_ON_BLOCK_ENTRY_EXIT
106    if (mCarryInfo->getWhileDepth() == 0) {
107        Value * packPtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(carryDataIndex));
108        mCarryInVector[carryDataIndex] = mBuilder->CreateAlignedLoad(packPtr, BLOCK_SIZE/8);
109        mBuilder->CreateAlignedStore(strm, packPtr, BLOCK_SIZE/8);
110    }
111#endif
112    Value * carry_in = mCarryInVector[carryDataIndex];
113    Value* result_value;
114   
115#if (BLOCK_SIZE == 128) && !defined(USE_LONG_INTEGER_SHIFT)
116    Value * ahead64 = iBuilder->mvmd_dslli(64, carry_in, strm, 1);
117    result_value = mBuilder->CreateOr(iBuilder->simd_srli(64, ahead64, 63), iBuilder->simd_slli(64, strm, 1));
118#else
119    Value* advanceq_longint = mBuilder->CreateBitCast(carry_in, mBuilder->getIntNTy(BLOCK_SIZE));
120    Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(BLOCK_SIZE));
121    Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, 1), mBuilder->CreateLShr(advanceq_longint, BLOCK_SIZE - 1), "advance");
122    result_value = mBuilder->CreateBitCast(adv_longint, mBitBlockType);
123   
124#endif
125    return result_value;
126}
127
128Value * CarryManager::shortAdvanceCarryInCarryOut(int localIndex, int shift_amount, Value * strm) {
129    unsigned carryDataIndex = mCurrentScopeIndex + mCarryInfo->shortAdvanceCarryDataOffset(localIndex);
130    mCarryOutVector[carryDataIndex] = strm; 
131#ifndef LOAD_STORE_ON_BLOCK_ENTRY_EXIT
132    if (mCarryInfo->getWhileDepth() == 0) {
133        Value * packPtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(carryDataIndex));
134        mCarryInVector[carryDataIndex] = mBuilder->CreateAlignedLoad(packPtr, BLOCK_SIZE/8);
135        mBuilder->CreateAlignedStore(strm, packPtr, BLOCK_SIZE/8);
136    }
137#endif
138    Value * carry_in = mCarryInVector[carryDataIndex];
139    Value* advanceq_longint = mBuilder->CreateBitCast(carry_in, mBuilder->getIntNTy(BLOCK_SIZE));
140    Value* strm_longint = mBuilder->CreateBitCast(strm, mBuilder->getIntNTy(BLOCK_SIZE));
141    Value* adv_longint = mBuilder->CreateOr(mBuilder->CreateShl(strm_longint, shift_amount), mBuilder->CreateLShr(advanceq_longint, BLOCK_SIZE - shift_amount), "advance");
142    return mBuilder->CreateBitCast(adv_longint, mBitBlockType);
143}
144   
145
146/*  currently defined in carry_data.h
147 
148 static unsigned power2ceil (unsigned v) {
149 unsigned ceil = 1;
150 while (ceil < v) ceil *= 2;
151 return ceil;
152 }
153 
154 unsigned longAdvanceEntries(unsigned shift_amount) const {
155 return (shift_amount + BLOCK_SIZE - 1)/BLOCK_SIZE;
156 }
157 
158 unsigned longAdvanceBufferSize(unsigned shift_amount)  const {
159 return power2ceil(longAdvanceEntries(shift_amount));
160 }
161 */
162
163   
164Value * CarryManager::longAdvanceCarryInCarryOut(int localIndex, int shift_amount, Value * carry_out) {
165    unsigned carryDataIndex = mCurrentScopeIndex + mCarryInfo->longAdvanceCarryDataOffset(localIndex);
166    Value * advBaseIndex = mBuilder->getInt64(carryDataIndex);
167    if (shift_amount <= BLOCK_SIZE) {
168        // special case using a single buffer entry and the carry_out value.
169        Value * advanceDataPtr = mBuilder->CreateGEP(mCarryDataPtr, advBaseIndex);
170        Value * carry_block0 = mBuilder->CreateAlignedLoad(advanceDataPtr, BLOCK_SIZE/8);
171        mBuilder->CreateAlignedStore(carry_out, advanceDataPtr, BLOCK_SIZE/8);
172        /* Very special case - no combine */
173        if (shift_amount == BLOCK_SIZE) return carry_block0;
174        Value* block0_shr = mBuilder->CreateLShr(mBuilder->CreateBitCast(carry_block0, mBuilder->getIntNTy(BLOCK_SIZE)), BLOCK_SIZE - shift_amount);
175        Value* block1_shl = mBuilder->CreateShl(mBuilder->CreateBitCast(carry_out, mBuilder->getIntNTy(BLOCK_SIZE)), shift_amount);
176        return mBuilder->CreateBitCast(mBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
177    }
178    // We need a buffer of at least two elements for storing the advance data.
179    const unsigned block_shift = shift_amount % BLOCK_SIZE;
180    const unsigned advanceEntries = mCarryInfo->longAdvanceEntries(shift_amount);
181    const unsigned bufsize = mCarryInfo->longAdvanceBufferSize(shift_amount);
182    Value * indexMask = mBuilder->getInt64(bufsize - 1);  // A mask to implement circular buffer indexing
183    Value * loadIndex0 = mBuilder->CreateAdd(mBuilder->CreateAnd(mBuilder->CreateSub(mBlockNo, mBuilder->getInt64(advanceEntries)), indexMask), advBaseIndex);
184    Value * storeIndex = mBuilder->CreateAdd(mBuilder->CreateAnd(mBlockNo, indexMask), advBaseIndex);
185    Value * carry_block0 = mBuilder->CreateAlignedLoad(mBuilder->CreateGEP(mCarryDataPtr, loadIndex0), BLOCK_SIZE/8);
186    // If the long advance is an exact multiple of BLOCK_SIZE, we simply return the oldest
187    // block in the long advance carry data area. 
188    if (block_shift == 0) {
189        mBuilder->CreateAlignedStore(carry_out, mBuilder->CreateGEP(mCarryDataPtr, storeIndex), BLOCK_SIZE/8);
190        return carry_block0;
191    }
192    // Otherwise we need to combine data from the two oldest blocks.
193    Value * loadIndex1 = mBuilder->CreateAdd(mBuilder->CreateAnd(mBuilder->CreateSub(mBlockNo, mBuilder->getInt64(advanceEntries-1)), indexMask), advBaseIndex);
194    Value * carry_block1 = mBuilder->CreateAlignedLoad(mBuilder->CreateGEP(mCarryDataPtr, loadIndex1), BLOCK_SIZE/8);
195    Value* block0_shr = mBuilder->CreateLShr(mBuilder->CreateBitCast(carry_block0, mBuilder->getIntNTy(BLOCK_SIZE)), BLOCK_SIZE - block_shift);
196    Value* block1_shl = mBuilder->CreateShl(mBuilder->CreateBitCast(carry_block1, mBuilder->getIntNTy(BLOCK_SIZE)), block_shift);
197    mBuilder->CreateAlignedStore(carry_out, mBuilder->CreateGEP(mCarryDataPtr, storeIndex), BLOCK_SIZE/8);
198    return mBuilder->CreateBitCast(mBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
199}
200   
201
202/* Methods for getting and setting carry summary values */
203   
204bool CarryManager::blockHasCarries(){
205    return mCarryInfo->blockHasCarries();
206} 
207
208
209Value * CarryManager::getCarrySummaryExpr() {
210    unsigned summary_idx = mCurrentScopeIndex + mCarryInfo->summaryCarryDataIndex();
211    Value * packPtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(summary_idx));
212    Value * summary_expr = mBuilder->CreateAlignedLoad(packPtr, BLOCK_SIZE/8);
213    // If the scopeCarryDataSize is 1, then the carry summary is also the pack expr.
214    mCarryInVector[summary_idx] = summary_expr;
215    return summary_expr;
216}
217
218void CarryManager::addSummaryPhiIfNeeded(BasicBlock * ifEntryBlock, BasicBlock * ifBodyFinalBlock) {
219    if ((mCarryInfo->getIfDepth() <= 1) || !mCarryInfo->blockHasCarries()){
220        // For ifDepth == 1, the parent does not need a summary as it is not itself within an if.
221        // Therefore, it doesn't need access to this block's summary in building its own.
222        return;
223    }
224    const unsigned carrySummaryIndex = mCurrentScopeIndex + mCarryInfo->summaryCarryDataIndex();
225    PHINode * summary_phi = mBuilder->CreatePHI(mBitBlockType, 2, "summary");
226    summary_phi->addIncoming(mZeroInitializer, ifEntryBlock);
227    summary_phi->addIncoming(mCarryOutVector[carrySummaryIndex], ifBodyFinalBlock);
228    mCarryOutVector[carrySummaryIndex] = summary_phi;
229}
230
231void CarryManager::generateCarryOutSummaryCodeIfNeeded() {
232   
233    if (!mCarryInfo->explicitSummaryRequired()) {
234        // An explicit summary may not be required, if there is a single carry
235        // operation within the block, or the carries are packed and all carry
236        // bits fit within a single pack.
237        return;
238    }
239   
240    const unsigned carrySummaryIndex = mCurrentScopeIndex + mCarryInfo->summaryCarryDataIndex();
241   
242    Value * carry_summary = mZeroInitializer;
243   
244    if (mCarryInfo->blockHasLongAdvances()) { // Force if entry
245        carry_summary = mOneInitializer;
246    }
247    else {
248        auto localCarryIndex = mCurrentScopeIndex + mCarryInfo->getLocalCarryPackIndex();
249        auto localCarryPacks = mCarryInfo->getLocalCarryDataSize();
250        if (localCarryPacks > 0) {
251            carry_summary = mCarryOutVector[localCarryIndex];
252            for (auto i = 1; i < localCarryPacks; i++) {
253                //carry_summary = mBuilder->CreateOr(carry_summary, mPabloBlock->mCarryOutPack[i]);           
254                carry_summary = mBuilder->CreateOr(carry_summary, mCarryOutVector[localCarryIndex+i]);
255            }
256        }
257        for (Statement * stmt : *mCurrentScope) {
258            if (If * innerIf = dyn_cast<If>(stmt)) {
259                PabloBlock * inner_blk = & innerIf->getBody();
260                enterScope(inner_blk);
261                if (blockHasCarries()) {
262                  carry_summary = mBuilder->CreateOr(carry_summary, mCarryOutVector[mCurrentScopeIndex + mCarryInfo->summaryCarryDataIndex()]);
263                }
264                leaveScope();
265            }
266            else if (While * innerWhile = dyn_cast<While>(stmt)) {
267                PabloBlock * inner_blk = & innerWhile->getBody();
268                enterScope(inner_blk);
269                if (blockHasCarries()) {
270                    carry_summary = mBuilder->CreateOr(carry_summary, mCarryOutVector[mCurrentScopeIndex + mCarryInfo->summaryCarryDataIndex()]);
271                }
272                leaveScope();
273            }
274        }
275    }
276    // Calculation of the carry out summary is complete.   Store it and make it
277    // available in case it must included by parent blocks.
278    mCarryOutVector[carrySummaryIndex] = carry_summary;
279    Value * packPtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(carrySummaryIndex));
280    mBuilder->CreateAlignedStore(carry_summary, packPtr, BLOCK_SIZE/8);
281}
282
283
284void CarryManager::ensureCarriesLoadedLocal() {
285#ifdef LOAD_STORE_ON_BLOCK_ENTRY_EXIT
286    if ((mCarryInfo->getScopeCarryDataSize() == 0 ) || (mCarryInfo->getWhileDepth() > 0)) return;
287    if ((mCarryInfo->getIfDepth() == 0) || mCarryInfo->explicitSummaryRequired()) {
288        auto localCarryIndex = mCurrentScopeIndex + mCarryInfo->getLocalCarryPackIndex();
289        auto localCarryPacks = mCarryInfo->getLocalCarryDataSize();
290        //std::cerr << "ensureCarriesLoadedLocal: localCarryIndex =  " << localCarryIndex << "localCarryPacks =  " << localCarryPacks << std::endl;
291        for (auto i = localCarryIndex; i < localCarryIndex + localCarryPacks; i++) {       
292            mCarryInVector[i] = mBuilder->CreateAlignedLoad(mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(i)), BLOCK_SIZE/8, false);
293        }
294    }
295#endif
296}
297
298void CarryManager::ensureCarriesStoredLocal() {
299#ifdef LOAD_STORE_ON_BLOCK_ENTRY_EXIT
300    if ((mCarryInfo->getScopeCarryDataSize() == 0 ) || (mCarryInfo->getWhileDepth() > 0)) return;
301    auto localCarryIndex = mCurrentScopeIndex + mCarryInfo->getLocalCarryPackIndex();
302    auto localCarryPacks = mCarryInfo->getLocalCarryDataSize();
303    //std::cerr << "ensureCarriesStoredLocal: localCarryIndex =  " << localCarryIndex << "localCarryPacks =  " << localCarryPacks << std::endl;
304    for (auto i = localCarryIndex; i < localCarryIndex + localCarryPacks; i++) {       
305        Value * storePtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(i));
306        mBuilder->CreateAlignedStore(mCarryOutVector[i], storePtr, BLOCK_SIZE/8, false);
307    }
308#endif
309}
310
311
312
313void CarryManager::ensureCarriesLoadedRecursive() {
314    const unsigned scopeCarryDataSize = mCarryInfo->getScopeCarryDataSize();
315    if (mCarryInfo->getWhileDepth() == 1) {
316        for (auto i = mCurrentScopeIndex; i < mCurrentScopeIndex + scopeCarryDataSize; ++i) {
317            mCarryInVector[i] = mBuilder->CreateAlignedLoad(mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(i)), BLOCK_SIZE/8, false);
318        }
319    }
320}
321
322
323void CarryManager::initializeCarryDataPhisAtWhileEntry(BasicBlock * whileEntryBlock) {
324    const unsigned scopeCarryDataSize = mCarryInfo->getScopeCarryDataSize();
325    for (unsigned index = mCurrentScopeIndex; index < mCurrentScopeIndex + scopeCarryDataSize; ++index) {
326#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
327        PHINode * phi_in = mBuilder->CreatePHI(mBitBlockType, 2);
328        phi_in->addIncoming(mCarryInVector[index], whileEntryBlock);
329        mCarryInPhis[index] = phi_in;
330#endif
331        PHINode * phi_out = mBuilder->CreatePHI(mBitBlockType, 2);
332        phi_out->addIncoming(mZeroInitializer, whileEntryBlock);
333        mCarryOutAccumPhis[index] = phi_out;
334    }
335}
336
337
338void CarryManager::extendCarryDataPhisAtWhileBodyFinalBlock(BasicBlock * whileBodyFinalBlock) {
339    const unsigned scopeCarryDataSize = mCarryInfo->getScopeCarryDataSize();
340    for (unsigned index = mCurrentScopeIndex; index < mCurrentScopeIndex + scopeCarryDataSize; ++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() {
352    const unsigned scopeCarryDataSize = mCarryInfo->getScopeCarryDataSize();
353    if (mCarryInfo->getWhileDepth() == 1) {
354        for (auto i = mCurrentScopeIndex; i < mCurrentScopeIndex + scopeCarryDataSize; ++i) {
355            Value * storePtr = mBuilder->CreateGEP(mCarryDataPtr, mBuilder->getInt64(i));
356            mBuilder->CreateAlignedStore(mCarryOutVector[i], storePtr, BLOCK_SIZE/8, false);
357        }
358    }
359}
360
361}
362
Note: See TracBrowser for help on using the repository browser.