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

Last change on this file since 4685 was 4684, checked in by nmedfort, 4 years ago

First attempt to intergrate 'generate_predefined_ucd_functions' into build process.

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