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

Last change on this file since 5400 was 5400, checked in by cameron, 2 years ago

Eliminate struct/class and unused variable warnings

File size: 43.2 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#include "carry_manager.h"
8#include <pablo/carry_data.h>
9#include <pablo/codegenstate.h>
10#include <llvm/IR/BasicBlock.h>
11#include <IR_Gen/idisa_builder.h>
12#include <llvm/IR/DerivedTypes.h>
13#include <pablo/branch.h>
14#include <pablo/pe_advance.h>
15#include <pablo/pe_scanthru.h>
16#include <pablo/pe_matchstar.h>
17#include <pablo/pe_var.h>
18
19#include <llvm/Support/raw_ostream.h>
20
21using namespace llvm;
22
23namespace pablo {
24
25inline static unsigned ceil_log2(const unsigned v) {
26    assert ("log2(0) is undefined!" && v != 0);
27    return 32 - __builtin_clz(v - 1);
28}
29
30inline static unsigned floor_log2(const unsigned v) {
31    assert ("log2(0) is undefined!" && v != 0);
32    return 31 - __builtin_clz(v);
33}
34
35inline static unsigned nearest_pow2(const unsigned v) {
36    assert(v > 0 && v < (UINT32_MAX / 2));
37    return (v < 2) ? 1 : (1 << ceil_log2(v));
38}
39
40inline static unsigned ceil_udiv(const unsigned x, const unsigned y) {
41    return (((x - 1) | (y - 1)) + 1) / y;
42}
43
44using TypeId = PabloAST::ClassTypeId;
45
46inline static bool isNonAdvanceCarryGeneratingStatement(const Statement * const stmt) {
47    switch (stmt->getClassTypeId()) {
48        case TypeId::ScanThru:
49        case TypeId::AdvanceThenScanThru:
50        case TypeId::ScanTo:
51        case TypeId::AdvanceThenScanTo:
52        case TypeId::MatchStar:
53            return true;
54        default:
55            return false;
56    }
57}
58
59#define LONG_ADVANCE_BREAKPOINT 64
60
61/** ------------------------------------------------------------------------------------------------------------- *
62 * @brief initializeCarryData
63 ** ------------------------------------------------------------------------------------------------------------- */
64void CarryManager::initializeCarryData(PabloKernel * const kernel) {
65
66    // Each scope constructs its own CarryData struct, which will be added to the final "carries" struct
67    // that is added to the Kernel. The scope index will indicate which struct to access.
68
69    // A CarryData struct either contains an array of CarryPackBlocks or an integer indicating the capacity of
70    // the variable length CarryData struct and pointer. A variable length CarryData struct is required whenever
71    // the streams accessed by a loop could vary between iterations. When resizing a CarryData struct for a
72    // particular loop, the current loop struct and all nested structs need to be resized. This accommodates
73    // the fact every pablo While loop must be executed at least once.
74
75    // A nested loop may also contain a variable length CarryData struct
76
77    // To determine whether we require a variable length CarryData struct, we test the escaped variables of
78    // each loop branch to see whether they are used as the index parameter of a nested Extract statement.
79    // Any scope that requires variable length CarryData, requires that all nested branches have a unique
80    // set of carries for that iteration.
81
82    mKernel = kernel;
83
84    mCurrentScope = kernel->getEntryBlock();
85
86    mCarryScopes = 0;
87
88    mCarryMetadata.resize(getScopeCount(kernel->getEntryBlock()));
89
90    Type * const carryStateTy = analyse(kernel->getEntryBlock());
91
92    mKernel->addScalar(carryStateTy, "carries");
93
94    if (mHasLoop) {
95        mKernel->addScalar(iBuilder->getInt32Ty(), "selector");
96    }
97    if (mHasLongAdvance) {
98        mKernel->addScalar(iBuilder->getSizeTy(), "CarryBlockIndex");
99    }
100}
101
102/** ------------------------------------------------------------------------------------------------------------- *
103 * @brief initializeCodeGen
104 ** ------------------------------------------------------------------------------------------------------------- */
105void CarryManager::initializeCodeGen() {
106
107    assert(!mCarryMetadata.empty());
108    mCarryInfo = &mCarryMetadata[0];
109    assert (!mCarryInfo->hasSummary());
110
111    mCurrentFrame = mKernel->getScalarFieldPtr("carries");
112    mCurrentFrameIndex = 0;
113    mCarryScopes = 0;
114    mCarryScopeIndex.push_back(0);
115
116    assert (mCarryFrameStack.empty());
117
118    assert (mCarrySummaryStack.empty());
119    mCarrySummaryStack.push_back(Constant::getNullValue(mCarryPackType));
120
121    if (mHasLoop) {
122        mLoopSelector = mKernel->getScalarField("selector");
123        mNextLoopSelector = iBuilder->CreateXor(mLoopSelector, ConstantInt::get(mLoopSelector->getType(), 1));
124    }
125}
126
127/** ------------------------------------------------------------------------------------------------------------- *
128 * @brief finalizeCodeGen
129 ** ------------------------------------------------------------------------------------------------------------- */
130void CarryManager::finalizeCodeGen() {
131    if (mHasLoop) {
132        mKernel->setScalarField("selector", mNextLoopSelector);
133    }
134    if (mHasLongAdvance) {
135        Value * idx = mKernel->getScalarField("CarryBlockIndex");
136        idx = iBuilder->CreateAdd(idx, iBuilder->getSize(1));
137        mKernel->setScalarField("CarryBlockIndex", idx);
138    }
139    assert (mCarryFrameStack.empty());   
140    assert ("base summary value was deleted!" && mCarrySummaryStack.size() == 1);
141    assert ("base summary value was overwritten with non-zero value!" && isa<Constant>(mCarrySummaryStack[0]) && cast<Constant>(mCarrySummaryStack[0])->isNullValue());
142    mCarrySummaryStack.clear();
143    assert (mCarryScopeIndex.size() == 1);
144    mCarryScopeIndex.clear();
145}
146
147/** ------------------------------------------------------------------------------------------------------------- *
148 * @brief enterLoopScope
149 ** ------------------------------------------------------------------------------------------------------------- */
150void CarryManager::enterLoopScope(const PabloBlock * const scope) {
151    assert (scope);
152    assert (mHasLoop);
153    ++mLoopDepth;
154    enterScope(scope);
155}
156
157/** ------------------------------------------------------------------------------------------------------------- *
158 * @brief enterLoopBody
159 ** ------------------------------------------------------------------------------------------------------------- */
160void CarryManager::enterLoopBody(BasicBlock * const entryBlock) {
161    if (mCarryInfo->hasSummary()) {
162        PHINode * phiCarryOutSummary = iBuilder->CreatePHI(mCarryPackType, 2, "summary");
163        assert (!mCarrySummaryStack.empty());
164        phiCarryOutSummary->addIncoming(mCarrySummaryStack.back(), entryBlock);
165        // Replace the incoming carry summary with the phi node and add the phi node to the stack  so that we can
166        // properly OR it into the outgoing summary value.
167        // NOTE: this may change the base summary value; when exiting to the base scope, replace this summary with
168        // a null value to prevent subsequent nested scopes from inheriting the summary of this scope.
169        mCarrySummaryStack.back() = phiCarryOutSummary;
170        mCarrySummaryStack.push_back(phiCarryOutSummary);
171    }
172    if (LLVM_UNLIKELY(mCarryInfo->nonCarryCollapsingMode())) {
173
174        assert (mCarryInfo->hasSummary());
175
176        // Check whether we need to resize the carry state
177        PHINode * index = iBuilder->CreatePHI(iBuilder->getSizeTy(), 2);
178        mLoopIndicies.push_back(index);
179        index->addIncoming(iBuilder->getSize(0), entryBlock);
180
181        Value * capacityPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(0)});
182        Value * capacity = iBuilder->CreateLoad(capacityPtr, false, "capacity");
183        Constant * const ONE = ConstantInt::get(capacity->getType(), 1);
184        Value * arrayPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(1)});
185        Value * array = iBuilder->CreateLoad(arrayPtr, false, "array");
186
187        BasicBlock * const entry = iBuilder->GetInsertBlock();
188        BasicBlock * const resizeCarryState = mKernel->CreateBasicBlock("ResizeCarryState");
189        BasicBlock * const reallocExisting = mKernel->CreateBasicBlock("ReallocExisting");
190        BasicBlock * const createNew = mKernel->CreateBasicBlock("CreateNew");
191        BasicBlock * const resumeKernel = mKernel->CreateBasicBlock("ResumeKernel");
192
193        iBuilder->CreateLikelyCondBr(iBuilder->CreateICmpULT(index, capacity), resumeKernel, resizeCarryState);
194
195        // RESIZE CARRY BLOCK
196        iBuilder->SetInsertPoint(resizeCarryState);
197        const auto BlockWidth = mCarryPackType->getPrimitiveSizeInBits() / 8;
198        const auto Log2BlockWidth = floor_log2(BlockWidth);
199        Constant * const carryStateWidth = ConstantExpr::getIntegerCast(ConstantExpr::getSizeOf(array->getType()->getPointerElementType()), iBuilder->getSizeTy(), false);
200        Value * summaryPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(2)});
201
202        Value * const hasCarryState = iBuilder->CreateICmpNE(array, ConstantPointerNull::get(cast<PointerType>(array->getType())));
203
204        iBuilder->CreateLikelyCondBr(hasCarryState, reallocExisting, createNew);
205
206        // REALLOCATE EXISTING
207        iBuilder->SetInsertPoint(reallocExisting);
208
209        Value * const capacitySize = iBuilder->CreateMul(capacity, carryStateWidth);
210        Value * const newCapacitySize = iBuilder->CreateShl(capacitySize, 1); // x 2
211
212
213        Value * newArray = iBuilder->CreateAlignedMalloc(newCapacitySize, iBuilder->getCacheAlignment());
214        iBuilder->CreateMemCpy(newArray, array, capacitySize, BlockWidth);
215        iBuilder->CreateMemZero(iBuilder->CreateGEP(newArray, capacitySize), capacitySize, BlockWidth);
216        iBuilder->CreateAlignedFree(array);
217        newArray = iBuilder->CreatePointerCast(newArray, array->getType());
218        iBuilder->CreateStore(newArray, arrayPtr);
219
220        Value * const log2capacity = iBuilder->CreateAdd(iBuilder->CreateCeilLog2(capacity), ONE);
221        Value * const summarySize = iBuilder->CreateShl(log2capacity, Log2BlockWidth + 1); // x 2(BlockWidth)
222        Value * const newLog2Capacity = iBuilder->CreateAdd(log2capacity, ONE);
223        Value * const newSummarySize = iBuilder->CreateShl(newLog2Capacity, Log2BlockWidth + 1); // x 2(BlockWidth)
224
225        Value * const summary = iBuilder->CreateLoad(summaryPtr, false);
226        Value * newSummary = iBuilder->CreateAlignedMalloc(newSummarySize, BlockWidth);
227        iBuilder->CreateMemCpy(newSummary, summary, summarySize, BlockWidth);
228        iBuilder->CreateMemZero(iBuilder->CreateGEP(newSummary, summarySize), iBuilder->getSize(2 * BlockWidth), BlockWidth);
229        iBuilder->CreateAlignedFree(summary);
230
231        Value * ptr1 = iBuilder->CreateGEP(newSummary, summarySize);
232        ptr1 = iBuilder->CreatePointerCast(ptr1, mCarryPackType->getPointerTo());
233
234        Value * ptr2 = iBuilder->CreateGEP(newSummary, iBuilder->CreateAdd(summarySize, iBuilder->getSize(BlockWidth)));
235        ptr2 = iBuilder->CreatePointerCast(ptr2, mCarryPackType->getPointerTo());
236
237        newSummary = iBuilder->CreatePointerCast(newSummary, mCarryPackType->getPointerTo());
238        iBuilder->CreateStore(newSummary, summaryPtr);
239        Value * const newCapacity = iBuilder->CreateShl(ONE, log2capacity);
240
241        iBuilder->CreateStore(newCapacity, capacityPtr);
242
243        iBuilder->CreateBr(resumeKernel);
244
245        // CREATE NEW
246        iBuilder->SetInsertPoint(createNew);
247
248        Constant * const initialLog2Capacity = iBuilder->getInt64(4);
249        Constant * const initialCapacity = ConstantExpr::getShl(ONE, initialLog2Capacity);
250        Constant * const initialCapacitySize = ConstantExpr::getMul(initialCapacity, carryStateWidth);
251
252        Value * initialArray = iBuilder->CreateAlignedMalloc(initialCapacitySize, iBuilder->getCacheAlignment());
253        iBuilder->CreateMemZero(initialArray, initialCapacitySize, BlockWidth);
254        initialArray = iBuilder->CreatePointerCast(initialArray, array->getType());
255        iBuilder->CreateStore(initialArray, arrayPtr);
256
257        Constant * initialSummarySize = ConstantExpr::getShl(ConstantExpr::getAdd(initialLog2Capacity, iBuilder->getInt64(1)), iBuilder->getInt64(Log2BlockWidth + 1));
258        Value * initialSummary = iBuilder->CreateAlignedMalloc(initialSummarySize, BlockWidth);
259        iBuilder->CreateMemZero(initialSummary, initialSummarySize, BlockWidth);
260        initialSummary = iBuilder->CreatePointerCast(initialSummary, mCarryPackType->getPointerTo());
261        iBuilder->CreateStore(initialSummary, summaryPtr);
262
263        iBuilder->CreateStore(initialCapacity, capacityPtr);
264
265        iBuilder->CreateBr(resumeKernel);
266
267        // RESUME KERNEL
268        iBuilder->SetInsertPoint(resumeKernel);
269        // Load the appropriate carry stat block
270        PHINode * phiArrayPtr = iBuilder->CreatePHI(array->getType(), 3);
271        phiArrayPtr->addIncoming(array, entry);
272        phiArrayPtr->addIncoming(initialArray, createNew);
273        phiArrayPtr->addIncoming(newArray, reallocExisting);
274
275        // NOTE: the 3 here is only to pass the assertion later. It refers to the number of elements in the carry data struct.
276        mCarryFrameStack.emplace_back(mCurrentFrame, 3);
277        mCurrentFrame = iBuilder->CreateGEP(phiArrayPtr, index);
278    }
279}
280
281/** ------------------------------------------------------------------------------------------------------------- *
282 * @brief leaveLoopBody
283 ** ------------------------------------------------------------------------------------------------------------- */
284void CarryManager::leaveLoopBody(BasicBlock * /* exitBlock */) {
285
286    if (LLVM_UNLIKELY(mCarryInfo->nonCarryCollapsingMode())) {
287
288        assert (mCarryInfo->hasSummary());
289
290        ConstantInt * const summaryIndex = iBuilder->getInt32(mCarryInfo->hasExplicitSummary() ? mCurrentFrameIndex : (mCurrentFrameIndex - 1));
291
292        Value * const carryInAccumulator = readCarryInSummary(summaryIndex);
293        Value * const carryOutAccumulator = mCarrySummaryStack.back();
294
295        if (mCarryInfo->hasExplicitSummary()) {
296            writeCarryOutSummary(carryOutAccumulator, summaryIndex);
297        }
298
299        std::tie(mCurrentFrame, mCurrentFrameIndex) = mCarryFrameStack.back();
300        mCarryFrameStack.pop_back();
301
302        // In non-carry-collapsing mode, we cannot rely on the fact that performing a single iteration of this
303        // loop will consume all of the incoming carries from the prior block. We need to subtract the carries
304        // consumed by this iteration from our carry summary state. To do so in parallel, we use the the half-
305        // subtractor circuit to do it in ceil log2 steps. Similarly, we compute our carry out summary state
306        // (for the subsequent block to subtract) using a half-adder circuit.
307
308        // NOTE: this requires that, for all loop iterations, i, and all block iterations, j, the carry in
309        // summary, CI_i,j, matches the carry out summary of the prior block iteration, CO_i,j - 1.
310        // Otherwise we may end up with an incorrect result or being trapped in an infinite loop.
311
312        Value * capacityPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(0)});
313        Value * capacity = iBuilder->CreateLoad(capacityPtr, false);
314        Value * summaryPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(2)});
315        Value * summary = iBuilder->CreateLoad(summaryPtr, false);
316
317        Constant * const ONE = ConstantInt::get(capacity->getType(), 1);
318
319        Value * loopSelector = iBuilder->CreateZExt(mLoopSelector, capacity->getType());
320
321        BasicBlock * entry = iBuilder->GetInsertBlock();
322        BasicBlock * update = mKernel->CreateBasicBlock("UpdateNonCarryCollapsingSummary");
323        BasicBlock * resume = mKernel->CreateBasicBlock("ResumeAfterUpdatingNonCarryCollapsingSummary");
324
325        iBuilder->CreateBr(update);
326
327        iBuilder->SetInsertPoint(update);
328        PHINode * i = iBuilder->CreatePHI(capacity->getType(), 2);
329        i->addIncoming(ConstantInt::getNullValue(capacity->getType()), entry);
330        PHINode * const borrow = iBuilder->CreatePHI(carryInAccumulator->getType(), 2);
331        borrow->addIncoming(carryInAccumulator, entry);
332        PHINode * const carry = iBuilder->CreatePHI(carryOutAccumulator->getType(), 2);
333        carry->addIncoming(carryOutAccumulator, entry);
334        // OR the updated carry in summary later for the summaryTest
335        PHINode * const carryInSummary = iBuilder->CreatePHI(mCarryPackType, 2);
336        carryInSummary->addIncoming(Constant::getNullValue(mCarryPackType), entry);
337
338        // half subtractor
339        Value * const carryInOffset = iBuilder->CreateOr(iBuilder->CreateShl(i, 1), loopSelector);
340        Value * const carryInPtr = iBuilder->CreateGEP(summary, carryInOffset);
341        Value * const carryIn = iBuilder->CreateBlockAlignedLoad(carryInPtr);
342        Value * const nextCarryIn = iBuilder->CreateXor(carryIn, borrow);
343        Value * const nextSummary = iBuilder->CreateOr(carryInSummary, nextCarryIn);
344        iBuilder->CreateBlockAlignedStore(nextCarryIn, carryInPtr);
345        carryInSummary->addIncoming(nextSummary, update);
346        Value * finalBorrow = iBuilder->CreateAnd(iBuilder->CreateNot(carryIn), borrow);
347        borrow->addIncoming(finalBorrow, update);
348
349        // half adder
350        Value * const carryOutOffset = iBuilder->CreateXor(carryInOffset, ConstantInt::get(carryInOffset->getType(), 1));
351        Value * const carryOutPtr = iBuilder->CreateGEP(summary, carryOutOffset);
352        Value * const carryOut = iBuilder->CreateBlockAlignedLoad(carryOutPtr);
353        Value * const nextCarryOut = iBuilder->CreateXor(carryOut, carry);
354        iBuilder->CreateBlockAlignedStore(nextCarryOut, carryOutPtr);
355        Value * finalCarry = iBuilder->CreateAnd(carryOut, carry);
356        carry->addIncoming(finalCarry, update);
357
358        // loop condition
359        i->addIncoming(iBuilder->CreateAdd(i, ONE), update);
360        iBuilder->CreateCondBr(iBuilder->CreateICmpNE(iBuilder->CreateShl(ONE, i), capacity), update, resume);
361
362        iBuilder->SetInsertPoint(resume);
363
364        IntegerType * ty = IntegerType::get(iBuilder->getContext(), mCarryPackType->getPrimitiveSizeInBits());
365        iBuilder->CreateAssert(iBuilder->CreateICmpEQ(iBuilder->CreateBitCast(finalBorrow, ty), ConstantInt::getNullValue(ty)), "finalBorrow != 0");
366        iBuilder->CreateAssert(iBuilder->CreateICmpEQ(iBuilder->CreateBitCast(finalCarry, ty), ConstantInt::getNullValue(ty)), "finalCarry != 0");
367
368        assert (!mLoopIndicies.empty());
369        PHINode * index = mLoopIndicies.back();
370        index->addIncoming(iBuilder->CreateAdd(index, iBuilder->getSize(1)), resume);
371        mLoopIndicies.pop_back();
372
373        mNextSummaryTest = nextSummary;
374    }
375    if (mCarryInfo->hasSummary()) {
376        const auto n = mCarrySummaryStack.size(); assert (n > 1);
377        Value * carryOut = mCarrySummaryStack.back();
378        mCarrySummaryStack.pop_back();
379        PHINode * phiCarryOut = cast<PHINode>(mCarrySummaryStack.back());
380        phiCarryOut->addIncoming(carryOut, iBuilder->GetInsertBlock());
381        // If we're returning to the base scope, reset our accumulated summary value.
382        if (n == 2) {
383            carryOut = Constant::getNullValue(mCarryPackType);
384        }
385        mCarrySummaryStack.back() = carryOut;
386    }
387}
388
389/** ------------------------------------------------------------------------------------------------------------- *
390 * @brief leaveLoopScope
391 ** ------------------------------------------------------------------------------------------------------------- */
392void CarryManager::leaveLoopScope(BasicBlock * const /* entryBlock */, BasicBlock * const /* exitBlock */) {
393    assert (mLoopDepth > 0);
394    --mLoopDepth;
395    leaveScope();
396}
397
398/** ------------------------------------------------------------------------------------------------------------- *
399 * @brief enterIfScope
400 ** ------------------------------------------------------------------------------------------------------------- */
401void CarryManager::enterIfScope(const PabloBlock * const scope) {
402    ++mIfDepth;
403    enterScope(scope);
404    // We zero-initialized the nested summary value and later OR in the current summary into the escaping summary
405    // so that upon processing the subsequent block iteration, we branch into this If scope iff a carry out was
406    // generated by a statement within this If scope and not by a dominating statement in the outer scope.
407    if (LLVM_LIKELY(mCarryInfo->hasSummary())) {
408        assert (mCurrentFrameIndex == 0);
409        mNextSummaryTest = readCarryInSummary(iBuilder->getInt32(0));
410        if (mCarryInfo->hasExplicitSummary()) {
411            mCurrentFrameIndex = 1;
412        }
413    }
414    mCarrySummaryStack.push_back(Constant::getNullValue(mCarryPackType));
415}
416
417/** ------------------------------------------------------------------------------------------------------------- *
418 * @brief generateSummaryTest
419 ** ------------------------------------------------------------------------------------------------------------- */
420Value * CarryManager::generateSummaryTest(Value * condition) {
421    if (LLVM_LIKELY(mCarryInfo->hasSummary())) {
422        assert ("summary test was not generated" && mNextSummaryTest);
423        condition = iBuilder->simd_or(condition, mNextSummaryTest);
424        mNextSummaryTest = nullptr;
425    }
426    assert ("summary test was not consumed" && (mNextSummaryTest == nullptr));
427    return condition;
428}
429
430/** ------------------------------------------------------------------------------------------------------------- *
431 * @brief enterIfBody
432 ** ------------------------------------------------------------------------------------------------------------- */
433void CarryManager::enterIfBody(BasicBlock * const entryBlock) {
434    assert (entryBlock);
435}
436
437/** ------------------------------------------------------------------------------------------------------------- *
438 * @brief leaveIfBody
439 ** ------------------------------------------------------------------------------------------------------------- */
440void CarryManager::leaveIfBody(BasicBlock * const exitBlock) {
441    assert (exitBlock);
442    const auto n = mCarrySummaryStack.size();
443    if (LLVM_LIKELY(mCarryInfo->hasExplicitSummary())) {
444        writeCarryOutSummary(mCarrySummaryStack[n - 1], iBuilder->getInt32(0));
445    }
446    if (n > 2) {
447        mCarrySummaryStack[n - 1] = iBuilder->CreateOr(mCarrySummaryStack[n - 1], mCarrySummaryStack[n - 2], "summary");
448    }
449}
450
451/** ------------------------------------------------------------------------------------------------------------- *
452 * @brief leaveIfScope
453 ** ------------------------------------------------------------------------------------------------------------- */
454void CarryManager::leaveIfScope(BasicBlock * const entryBlock, BasicBlock * const exitBlock) {
455    assert (mIfDepth > 0);
456    if (LLVM_LIKELY(mCarryInfo->hasSummary())) {
457        const auto n = mCarrySummaryStack.size(); assert (n > 0);
458        if (n > 2) {
459            // When leaving a nested If scope with a summary value, phi out the summary to ensure the
460            // appropriate summary is stored in the outer scope.
461            Value * nested = mCarrySummaryStack[n - 1];
462            Value * outer = mCarrySummaryStack[n - 2];
463            assert (nested->getType() == outer->getType());
464            PHINode * const phi = iBuilder->CreatePHI(nested->getType(), 2, "summary");
465            phi->addIncoming(outer, entryBlock);
466            phi->addIncoming(nested, exitBlock);
467            mCarrySummaryStack[n - 2] = phi;
468        }
469    }
470    --mIfDepth;
471    leaveScope();
472    mCarrySummaryStack.pop_back();
473}
474
475/** ------------------------------------------------------------------------------------------------------------ *
476 * @brief enterScope
477 ** ------------------------------------------------------------------------------------------------------------- */
478void CarryManager::enterScope(const PabloBlock * const scope) {
479    assert (scope);
480    // Store the state of the current frame and update the scope state
481    mCarryFrameStack.emplace_back(mCurrentFrame, mCurrentFrameIndex + 1);
482    mCurrentScope = scope;
483    mCarryScopeIndex.push_back(++mCarryScopes);
484    mCarryInfo = &mCarryMetadata[mCarryScopes];
485    // Check whether we're still within our struct bounds; if this fails, either the Pablo program changed during
486    // compilation or a memory corruption has occured.
487    assert (mCurrentFrameIndex < mCurrentFrame->getType()->getPointerElementType()->getStructNumElements());
488    mCurrentFrame = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex)});
489    // Verify we're pointing to a carry frame struct
490    assert(mCurrentFrame->getType()->getPointerElementType()->isStructTy());
491    mCurrentFrameIndex = 0;
492}
493
494/** ------------------------------------------------------------------------------------------------------------- *
495 * @brief leaveScope
496 ** ------------------------------------------------------------------------------------------------------------- */
497void CarryManager::leaveScope() {
498
499    // Did we use all of the packs in this carry struct?
500    assert (mCurrentFrameIndex == mCurrentFrame->getType()->getPointerElementType()->getStructNumElements());
501    // Sanity test: are there remaining carry frames?
502    assert (!mCarryFrameStack.empty());
503
504    std::tie(mCurrentFrame, mCurrentFrameIndex) = mCarryFrameStack.back();
505
506    assert(mCurrentFrame->getType()->getPointerElementType()->isStructTy());
507
508    mCarryFrameStack.pop_back();
509    mCarryScopeIndex.pop_back();
510    assert (!mCarryScopeIndex.empty());
511    mCurrentScope = mCurrentScope->getPredecessor();
512    assert (mCurrentScope);
513    mCarryInfo = &mCarryMetadata[mCarryScopeIndex.back()];
514}
515
516/** ------------------------------------------------------------------------------------------------------------- *
517 * @brief addCarryInCarryOut
518 ** ------------------------------------------------------------------------------------------------------------- */
519Value * CarryManager::addCarryInCarryOut(const Statement * const operation, Value * const e1, Value * const e2) {
520    assert (operation && (isNonAdvanceCarryGeneratingStatement(operation)));
521    Value * const carryIn = getNextCarryIn();
522    Value * carryOut, * result;
523    std::tie(carryOut, result) = iBuilder->bitblock_add_with_carry(e1, e2, carryIn);
524    setNextCarryOut(carryOut);
525    assert (result->getType() == mBitBlockType);
526    return result;
527}
528
529/** ------------------------------------------------------------------------------------------------------------- *
530 * @brief advanceCarryInCarryOut
531 ** ------------------------------------------------------------------------------------------------------------- */
532Value * CarryManager::advanceCarryInCarryOut(const Advance * const advance, Value * const value) {
533    const auto shiftAmount = advance->getAmount();
534    if (LLVM_LIKELY(shiftAmount < LONG_ADVANCE_BREAKPOINT)) {
535        Value * const carryIn = getNextCarryIn();
536        Value * carryOut, * result;
537        std::tie(carryOut, result) = iBuilder->bitblock_advance(value, carryIn, shiftAmount);
538        setNextCarryOut(carryOut);
539        assert (result->getType() == mBitBlockType);
540        return result;
541    } else {
542        return longAdvanceCarryInCarryOut(value, shiftAmount);
543    }
544}
545
546/** ------------------------------------------------------------------------------------------------------------- *
547 * @brief longAdvanceCarryInCarryOut
548 ** ------------------------------------------------------------------------------------------------------------- */
549inline Value * CarryManager::longAdvanceCarryInCarryOut(Value * const value, const unsigned shiftAmount) {
550
551    assert (mHasLongAdvance);
552    assert (shiftAmount >= LONG_ADVANCE_BREAKPOINT);
553
554    Type * const streamTy = iBuilder->getIntNTy(mBitBlockWidth);
555
556    if (mIfDepth > 0) {
557        if (shiftAmount > mBitBlockWidth) {
558            const auto frameIndex = mCurrentFrameIndex++;
559            Value * carry = iBuilder->CreateZExt(iBuilder->bitblock_any(value), streamTy);
560            const unsigned summarySize = ceil_udiv(shiftAmount, mBitBlockWidth * mBitBlockWidth);
561            for (unsigned i = 0;;++i) {
562                Value * const ptr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(frameIndex), iBuilder->getInt32(i)});
563                Value * const prior = iBuilder->CreateBitCast(iBuilder->CreateBlockAlignedLoad(ptr), streamTy);
564                Value * const stream = iBuilder->CreateBitCast(iBuilder->CreateOr(iBuilder->CreateShl(prior, 1), carry), mBitBlockType);
565                if (LLVM_LIKELY(i == summarySize)) {
566                    Value * const maskedStream = iBuilder->CreateAnd(stream, iBuilder->bitblock_mask_from(iBuilder->getInt32(summarySize % mBitBlockWidth)));
567                    addToCarryOutSummary(maskedStream);
568                    iBuilder->CreateBlockAlignedStore(maskedStream, ptr);
569                    break;
570                }
571                addToCarryOutSummary(stream);
572                iBuilder->CreateBlockAlignedStore(stream, ptr);
573                carry = iBuilder->CreateLShr(prior, mBitBlockWidth - 1);
574            }
575        } else if (LLVM_LIKELY(mCarryInfo->hasExplicitSummary())) {
576            addToCarryOutSummary(value);
577        }
578    }
579    const auto frameIndex = mCurrentFrameIndex++;
580    // special case using a single buffer entry and the carry_out value.
581    if (LLVM_LIKELY((shiftAmount < mBitBlockWidth) && (mLoopDepth == 0))) {
582        Value * const buffer = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(frameIndex), iBuilder->getInt32(0)});
583        assert (buffer->getType()->getPointerElementType() == mBitBlockType);
584        Value * carryIn = iBuilder->CreateBlockAlignedLoad(buffer);       
585        iBuilder->CreateBlockAlignedStore(value, buffer);
586        /* Very special case - no combine */
587        if (LLVM_UNLIKELY(shiftAmount == mBitBlockWidth)) {
588            return iBuilder->CreateBitCast(carryIn, mBitBlockType);
589        }
590        Value* block0_shr = iBuilder->CreateLShr(iBuilder->CreateBitCast(carryIn, streamTy), mBitBlockWidth - shiftAmount);
591        Value* block1_shl = iBuilder->CreateShl(iBuilder->CreateBitCast(value, streamTy), shiftAmount);
592        return iBuilder->CreateBitCast(iBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
593    } else { //
594        const unsigned blockShift = shiftAmount % mBitBlockWidth;
595        const unsigned blocks = ceil_udiv(shiftAmount, mBitBlockWidth);
596        // Create a mask to implement circular buffer indexing
597        Value * indexMask = iBuilder->getSize(nearest_pow2(blocks + ((mLoopDepth != 0) ? 1 : 0)) - 1);
598        Value * blockIndex = mKernel->getScalarField("CarryBlockIndex");
599        Value * carryIndex0 = iBuilder->CreateSub(blockIndex, iBuilder->getSize(blocks));
600        Value * loadIndex0 = iBuilder->CreateAnd(carryIndex0, indexMask);
601        Value * const carryInPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(frameIndex), loadIndex0});
602        Value * carryIn = iBuilder->CreateBlockAlignedLoad(carryInPtr);
603
604        Value * storeIndex = iBuilder->CreateAnd(blockIndex, indexMask);
605        Value * const carryOutPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(frameIndex), storeIndex});
606        assert (carryIn->getType() == mBitBlockType);
607
608        // If the long advance is an exact multiple of BitBlockWidth, we simply return the oldest
609        // block in the long advance carry data area.
610        if (LLVM_UNLIKELY(blockShift == 0)) {
611            iBuilder->CreateBlockAlignedStore(value, carryOutPtr);
612            return carryIn;
613        } else { // Otherwise we need to combine data from the two oldest blocks.
614            Value * carryIndex1 = iBuilder->CreateSub(blockIndex, iBuilder->getSize(blocks - 1));
615            Value * loadIndex1 = iBuilder->CreateAnd(carryIndex1, indexMask);
616            Value * const carryInPtr2 = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(frameIndex), loadIndex1});
617            Value * carry_block1 = iBuilder->CreateBlockAlignedLoad(carryInPtr2);
618            Value * block0_shr = iBuilder->CreateLShr(iBuilder->CreateBitCast(carryIn, streamTy), mBitBlockWidth - blockShift);
619            Value * block1_shl = iBuilder->CreateShl(iBuilder->CreateBitCast(carry_block1, streamTy), blockShift);
620            iBuilder->CreateBlockAlignedStore(value, carryOutPtr);
621            return iBuilder->CreateBitCast(iBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
622        }
623    }
624}
625
626/** ------------------------------------------------------------------------------------------------------------- *
627 * @brief getNextCarryIn
628 ** ------------------------------------------------------------------------------------------------------------- */
629Value * CarryManager::getNextCarryIn() {
630    assert (mCurrentFrameIndex < mCurrentFrame->getType()->getPointerElementType()->getStructNumElements());
631    if (mLoopDepth == 0) {
632        mCarryPackPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex)});
633    } else {
634        mCarryPackPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex), mLoopSelector});
635    }
636    assert (mCarryPackPtr->getType()->getPointerElementType() == mCarryPackType);
637    Value * const carryIn = iBuilder->CreateBlockAlignedLoad(mCarryPackPtr);
638    if (mLoopDepth > 0) {
639        iBuilder->CreateBlockAlignedStore(Constant::getNullValue(mCarryPackType), mCarryPackPtr);
640    }
641    return carryIn;
642}
643
644/** ------------------------------------------------------------------------------------------------------------- *
645 * @brief setNextCarryOut
646 ** ------------------------------------------------------------------------------------------------------------- */
647void CarryManager::setNextCarryOut(Value * carryOut) {
648    assert (mCurrentFrameIndex < mCurrentFrame->getType()->getPointerElementType()->getStructNumElements());
649    carryOut = iBuilder->CreateBitCast(carryOut, mCarryPackType);
650    if (mCarryInfo->hasSummary()) {
651        addToCarryOutSummary(carryOut);
652    }
653    if (mLoopDepth != 0) {
654        mCarryPackPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex), mNextLoopSelector});
655        if (LLVM_LIKELY(!mCarryInfo->nonCarryCollapsingMode())) {
656            Value * accum = iBuilder->CreateBlockAlignedLoad(mCarryPackPtr);
657            carryOut = iBuilder->CreateOr(carryOut, accum);
658        }
659    }
660    ++mCurrentFrameIndex;
661    assert (mCarryPackPtr->getType()->getPointerElementType() == mCarryPackType);
662    iBuilder->CreateBlockAlignedStore(carryOut, mCarryPackPtr);
663}
664
665/** ------------------------------------------------------------------------------------------------------------- *
666 * @brief readCarryInSummary
667 ** ------------------------------------------------------------------------------------------------------------- */
668Value * CarryManager::readCarryInSummary(ConstantInt * index) const {
669    assert (mCarryInfo->hasSummary());
670
671    unsigned count = 2;
672    if (LLVM_UNLIKELY(mCarryInfo->hasBorrowedSummary())) {
673        Type * frameTy = mCurrentFrame->getType()->getPointerElementType();
674        count = 1;
675        while (frameTy->isStructTy()) {
676            ++count;
677            frameTy = frameTy->getStructElementType(0);
678        }
679    }
680    const unsigned length = (mLoopDepth == 0) ? count : (count + 1);
681    Value * indicies[length];
682    std::fill(indicies, indicies + count - 1, iBuilder->getInt32(0));
683    indicies[count - 1] = index;
684    if (mLoopDepth != 0) {
685        indicies[count] = mLoopSelector;
686    }
687
688    ArrayRef<Value *> ar(indicies, length);
689    Value * const ptr = iBuilder->CreateGEP(mCurrentFrame, ar);
690    Value * const summary = iBuilder->CreateBlockAlignedLoad(ptr);
691    if (mLoopDepth != 0 && mCarryInfo->hasExplicitSummary()) {
692        iBuilder->CreateBlockAlignedStore(Constant::getNullValue(mCarryPackType), ptr);
693    }
694    return summary;
695}
696
697/** ------------------------------------------------------------------------------------------------------------- *
698 * @brief writeCarryOutSummary
699 ** ------------------------------------------------------------------------------------------------------------- */
700inline void CarryManager::writeCarryOutSummary(Value * const summary, ConstantInt * index) const {
701    Value * ptr = nullptr;
702    assert (mCarryInfo->hasExplicitSummary());
703    if (mLoopDepth > 0) {
704        ptr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), index, mNextLoopSelector});
705    } else {
706        ptr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), index});
707    }
708    iBuilder->CreateBlockAlignedStore(summary, ptr);
709}
710
711/** ------------------------------------------------------------------------------------------------------------- *
712 * @brief addToCarryOutSummary
713 ** ------------------------------------------------------------------------------------------------------------- */
714inline void CarryManager::addToCarryOutSummary(Value * const value) {
715    assert ("cannot add null summary value!" && value);   
716    assert ("summary stack is empty!" && !mCarrySummaryStack.empty());
717    assert (mCarryInfo->hasSummary());
718    mCarrySummaryStack.back() = iBuilder->CreateOr(value, mCarrySummaryStack.back());
719}
720
721/** ------------------------------------------------------------------------------------------------------------- *
722 * @brief enumerate
723 ** ------------------------------------------------------------------------------------------------------------- */
724unsigned CarryManager::getScopeCount(PabloBlock * const scope, unsigned index) {
725    for (Statement * stmt : *scope) {
726        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
727            index = getScopeCount(cast<Branch>(stmt)->getBody(), index);
728        }
729    }
730    return index + 1;
731}
732
733/** ------------------------------------------------------------------------------------------------------------- *
734 * @brief hasIterationSpecificAssignment
735 ** ------------------------------------------------------------------------------------------------------------- */
736bool CarryManager::hasIterationSpecificAssignment(const PabloBlock * const scope) {
737    if (const While * const br = dyn_cast_or_null<While>(scope->getBranch())) {
738        for (const Var * var : br->getEscaped()) {
739            for (const PabloAST * user : var->users()) {
740                if (const Extract * e = dyn_cast<Extract>(user)) {
741                    if (LLVM_UNLIKELY(e->getIndex() == var)) {
742                        // If we assign this Var a value and read the value as the index parameter
743                        // of a nested Extract statement, then we cannot collapse the carries.
744                        const PabloBlock * parent = e->getParent();
745                        for (;;) {
746                            if (parent == scope) {
747                                return true;
748                            }
749                            parent = parent->getPredecessor();
750                            if (parent == nullptr) {
751                                break;
752                            }
753                        }
754                    }
755                }
756            }
757        }
758    }
759    return false;
760}
761
762/** ------------------------------------------------------------------------------------------------------------- *
763 * @brief analyse
764 ** ------------------------------------------------------------------------------------------------------------- */
765StructType * CarryManager::analyse(PabloBlock * const scope, const unsigned ifDepth, const unsigned loopDepth, const bool isNestedWithinNonCarryCollapsingLoop) {
766
767    assert (scope != mKernel->getEntryBlock() || mCarryScopes == 0);
768    assert (mCarryScopes < mCarryMetadata.size());
769    assert (mCarryPackType);
770
771    const unsigned carryScopeIndex = mCarryScopes++;
772    const bool nonCarryCollapsingMode = hasIterationSpecificAssignment(scope);
773    Type * const carryPackType = (loopDepth == 0) ? mCarryPackType : ArrayType::get(mCarryPackType, 2);
774    std::vector<Type *> state;
775
776    for (Statement * stmt : *scope) {
777        if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
778            const auto amount = cast<Advance>(stmt)->getAmount();
779            Type * type = carryPackType;
780            if (LLVM_UNLIKELY(amount >= LONG_ADVANCE_BREAKPOINT)) {
781                const unsigned blocks = ceil_udiv(amount, mBitBlockWidth);
782                type = ArrayType::get(mBitBlockType, nearest_pow2(blocks + ((loopDepth != 0) ? 1 : 0)));
783                if (LLVM_UNLIKELY(ifDepth > 0 && amount > mBitBlockWidth)) {
784                    // 1 bit will mark the presense of any bit in each block.
785                    Type * carryType = ArrayType::get(mBitBlockType, ceil_udiv(amount, mBitBlockWidth * mBitBlockWidth));
786                    state.push_back(carryType);
787                }
788                mHasLongAdvance = true;               
789            }
790            state.push_back(type);
791        } else if (LLVM_UNLIKELY(isNonAdvanceCarryGeneratingStatement(stmt))) {
792            state.push_back(carryPackType);
793        } else if (LLVM_UNLIKELY(isa<If>(stmt))) {
794            state.push_back(analyse(cast<If>(stmt)->getBody(), ifDepth + 1, loopDepth, nonCarryCollapsingMode | isNestedWithinNonCarryCollapsingLoop));
795        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
796            mHasLoop = true;
797            state.push_back(analyse(cast<While>(stmt)->getBody(), ifDepth, loopDepth + 1, nonCarryCollapsingMode | isNestedWithinNonCarryCollapsingLoop));
798        }
799    }
800    // Build the carry state struct and add the summary pack if needed.
801    CarryData & cd = mCarryMetadata[carryScopeIndex];
802    StructType * carryState = nullptr;
803    CarryData::SummaryType summaryType = CarryData::NoSummary;
804    if (LLVM_UNLIKELY(state.empty())) {
805        carryState = StructType::get(iBuilder->getContext());
806    } else {
807        //if (ifDepth > 0 || (nonCarryCollapsingMode | isNestedWithinNonCarryCollapsingLoop)) {
808        if (dyn_cast_or_null<If>(scope->getBranch()) || nonCarryCollapsingMode || isNestedWithinNonCarryCollapsingLoop) {
809            if (LLVM_LIKELY(state.size() > 1)) {
810                summaryType = CarryData::ExplicitSummary;
811                // NOTE: summaries are stored differently depending whether we're entering an If or While branch. With an If branch, they
812                // preceed the carry state data and with a While loop they succeed it. This is to help cache prefectching performance.
813                state.insert(isa<If>(scope->getBranch()) ? state.begin() : state.end(), carryPackType);
814            } else {
815                summaryType = CarryData::ImplicitSummary;
816                if (state[0]->isStructTy()) {
817                    summaryType = CarryData::BorrowedSummary;
818                }
819            }           
820        }
821        carryState = StructType::get(iBuilder->getContext(), state);
822        // If we're in a loop and cannot use collapsing carry mode, convert the carry state struct into a capacity,
823        // carry state pointer, and summary pointer struct.
824        if (LLVM_UNLIKELY(nonCarryCollapsingMode)) {
825            carryState = StructType::get(iBuilder->getSizeTy(), carryState->getPointerTo(), mCarryPackType->getPointerTo(), nullptr);
826        }
827        cd.setNonCollapsingCarryMode(nonCarryCollapsingMode);
828    }
829    cd.setSummaryType(summaryType);
830    return carryState;
831}
832
833/** ------------------------------------------------------------------------------------------------------------- *
834 * @brief constructor
835 ** ------------------------------------------------------------------------------------------------------------- */
836CarryManager::CarryManager(IDISA::IDISA_Builder * idb) noexcept
837: iBuilder(idb)
838, mKernel(nullptr)
839, mBitBlockType(idb->getBitBlockType())
840, mBitBlockWidth(idb->getBitBlockWidth())
841, mCurrentFrame(nullptr)
842, mCurrentFrameIndex(0)
843, mCurrentScope(nullptr)
844, mCarryInfo(nullptr)
845, mCarryPackType(mBitBlockType)
846, mNextSummaryTest(nullptr)
847, mIfDepth(0)
848, mHasLongAdvance(false)
849, mHasLoop(false)
850, mLoopDepth(0)
851, mLoopSelector(nullptr)
852, mNextLoopSelector(nullptr)
853, mCarryPackPtr(nullptr)
854, mCarryScopes(0) {
855
856}
857
858}
Note: See TracBrowser for help on using the repository browser.