Ignore:
Timestamp:
Jun 6, 2017, 6:20:55 PM (2 years ago)
Author:
cameron
Message:

Restore check-ins from the last several days

Location:
icGREP/icgrep-devel/icgrep/pablo
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.cpp

    r5486 r5493  
    1616#include <pablo/pe_var.h>
    1717#include <kernels/kernel_builder.h>
    18 #include <llvm/Support/raw_ostream.h>
     18#include <toolchain/toolchain.h>
     19#include <array>
    1920
    2021using namespace llvm;
     
    2425inline static unsigned ceil_log2(const unsigned v) {
    2526    assert ("log2(0) is undefined!" && v != 0);
    26     return 32 - __builtin_clz(v - 1);
     27    return (sizeof(unsigned) * CHAR_BIT) - __builtin_clz(v - 1);
    2728}
    2829
    2930inline static unsigned floor_log2(const unsigned v) {
    3031    assert ("log2(0) is undefined!" && v != 0);
    31     return 31 - __builtin_clz(v);
     32    return ((sizeof(unsigned) * CHAR_BIT) - 1) - __builtin_clz(v);
    3233}
    3334
     
    8889        kernel->addScalar(iBuilder->getSizeTy(), "CarryBlockIndex");
    8990    }
    90 
     91}
     92
     93bool isDynamicallyAllocatedType(const Type * const ty) {
     94    if (isa<StructType>(ty) && ty->getStructNumElements() == 3) {
     95        return (ty->getStructElementType(1)->isPointerTy() && ty->getStructElementType(2)->isPointerTy() && ty->getStructElementType(0)->isIntegerTy());
     96    }
     97    return false;
     98}
     99
     100bool containsDynamicallyAllocatedType(const Type * const ty) {
     101    if (isa<StructType>(ty)) {
     102        for (unsigned i = 0; i < ty->getStructNumElements(); ++i) {
     103            if (isDynamicallyAllocatedType(ty->getStructElementType(i))) {
     104                return true;
     105            }
     106        }
     107    }
     108    return false;
     109}
     110
     111void freeDynamicallyAllocatedMemory(const std::unique_ptr<kernel::KernelBuilder> & idb, Value * const frame) {
     112    StructType * const ty = cast<StructType>(frame->getType()->getPointerElementType());
     113    std::array<Value *, 3> indices;
     114    indices[0] = idb->getInt32(0);
     115    for (unsigned i = 0; i < ty->getStructNumElements(); ++i) {
     116        if (isDynamicallyAllocatedType(ty->getStructElementType(i))) {
     117            indices[1] = idb->getInt32(i);
     118            indices[2] = idb->getInt32(1);
     119            Value * const innerFrame = idb->CreateLoad(idb->CreateGEP(frame, ArrayRef<Value*>(indices.data(), 3)));
     120            if (containsDynamicallyAllocatedType(innerFrame->getType())) {
     121                indices[2] = indices[0];
     122                Value *  const count = idb->CreateLoad(idb->CreateGEP(frame, ArrayRef<Value*>(indices.data(), 3)));
     123                BasicBlock * const entry = idb->GetInsertBlock();
     124                BasicBlock * const cond = idb->CreateBasicBlock("freeCarryDataCond");
     125                BasicBlock * const body = idb->CreateBasicBlock("freeCarryDataLoop");
     126                BasicBlock * const exit = idb->CreateBasicBlock("freeCarryDataExit");
     127                idb->CreateBr(cond);
     128                idb->SetInsertPoint(cond);
     129                PHINode * const index = idb->CreatePHI(count->getType(), 2);
     130                index->addIncoming(ConstantInt::getNullValue(count->getType()), entry);
     131                Value * test = idb->CreateICmpNE(index, count);
     132                idb->CreateCondBr(test, body, exit);
     133                idb->SetInsertPoint(body);
     134                freeDynamicallyAllocatedMemory(idb, idb->CreateGEP(innerFrame, index));
     135                index->addIncoming(idb->CreateAdd(index, ConstantInt::get(count->getType(), 1)), body);
     136                idb->CreateBr(cond);
     137                idb->SetInsertPoint(exit);
     138            }
     139            idb->CreateFree(innerFrame);
     140            indices[2] = idb->getInt32(2);
     141            Value *  const summary = idb->CreateLoad(idb->CreateGEP(frame, ArrayRef<Value*>(indices.data(), 3)));
     142            idb->CreateFree(summary);
     143        }
     144    }
    91145}
    92146
     
    94148 * @brief releaseCarryData
    95149 ** ------------------------------------------------------------------------------------------------------------- */
    96 void CarryManager::releaseCarryData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, PabloKernel * const kernel) {
    97 
    98 
     150void CarryManager::releaseCarryData(const std::unique_ptr<kernel::KernelBuilder> & idb) {
     151    if (mHasNonCarryCollapsingLoops) {
     152        freeDynamicallyAllocatedMemory(idb, idb->getScalarFieldPtr("carries"));
     153    }
    99154}
    100155
     
    186241        mLoopIndicies.push_back(index);
    187242        index->addIncoming(iBuilder->getSize(0), entryBlock);
    188 
    189243        Value * capacityPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(0)});
    190         Value * capacity = iBuilder->CreateLoad(capacityPtr, false, "capacity");
     244        Value * capacity = iBuilder->CreateLoad(capacityPtr, "capacity");
    191245        Constant * const ONE = ConstantInt::get(capacity->getType(), 1);
    192246        Value * arrayPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(1)});
    193         Value * array = iBuilder->CreateLoad(arrayPtr, false, "array");
    194 
     247        Value * array = iBuilder->CreateLoad(arrayPtr, "array");
    195248        BasicBlock * const entry = iBuilder->GetInsertBlock();
    196249        BasicBlock * const resizeCarryState = iBuilder->CreateBasicBlock("ResizeCarryState");
     
    198251        BasicBlock * const createNew = iBuilder->CreateBasicBlock("CreateNew");
    199252        BasicBlock * const resumeKernel = iBuilder->CreateBasicBlock("ResumeKernel");
    200 
    201         iBuilder->CreateLikelyCondBr(iBuilder->CreateICmpULT(index, capacity), resumeKernel, resizeCarryState);
     253        iBuilder->CreateLikelyCondBr(iBuilder->CreateICmpNE(index, capacity), resumeKernel, resizeCarryState);
    202254
    203255        // RESIZE CARRY BLOCK
    204256        iBuilder->SetInsertPoint(resizeCarryState);
    205         const auto BlockWidth = carryTy->getPrimitiveSizeInBits() / 8;
     257        const auto BlockWidth = iBuilder->getBitBlockWidth() / 8;
    206258        const auto Log2BlockWidth = floor_log2(BlockWidth);
    207259        Constant * const carryStateWidth = ConstantExpr::getIntegerCast(ConstantExpr::getSizeOf(array->getType()->getPointerElementType()), iBuilder->getSizeTy(), false);
    208         Value * summaryPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(2)});
    209 
     260        Value * const summaryPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(2)});
    210261        Value * const hasCarryState = iBuilder->CreateICmpNE(array, ConstantPointerNull::get(cast<PointerType>(array->getType())));
    211 
    212262        iBuilder->CreateLikelyCondBr(hasCarryState, reallocExisting, createNew);
    213263
    214264        // REALLOCATE EXISTING
    215265        iBuilder->SetInsertPoint(reallocExisting);
    216 
    217266        Value * const capacitySize = iBuilder->CreateMul(capacity, carryStateWidth);
    218267        Value * const newCapacitySize = iBuilder->CreateShl(capacitySize, 1); // x 2
    219 
    220         Value * newArray = iBuilder->CreateRealloc(array, newCapacitySize);
    221 
     268        Value * const newArray = iBuilder->CreateCacheAlignedMalloc(newCapacitySize);
     269        iBuilder->CreateMemCpy(newArray, array, capacitySize, iBuilder->getCacheAlignment());
     270        iBuilder->CreateFree(array);
     271        iBuilder->CreateStore(newArray, arrayPtr);
    222272        Value * const startNewArrayPtr = iBuilder->CreateGEP(iBuilder->CreatePointerCast(newArray, int8PtrTy), capacitySize);
    223273        iBuilder->CreateMemZero(startNewArrayPtr, capacitySize, BlockWidth);
    224 
    225         iBuilder->CreateStore(newArray, arrayPtr);
    226 
    227         Value * const log2capacity = iBuilder->CreateAdd(iBuilder->CreateCeilLog2(capacity), ONE);
    228         Value * const summarySize = iBuilder->CreateShl(log2capacity, Log2BlockWidth + 1); // x 2(BlockWidth)
    229         Value * const newLog2Capacity = iBuilder->CreateAdd(log2capacity, ONE);
    230         Value * const newSummarySize = iBuilder->CreateShl(newLog2Capacity, Log2BlockWidth + 1); // x 2(BlockWidth)
    231 
     274        Value * const newCapacity = iBuilder->CreateShl(capacity, 1);
     275        iBuilder->CreateStore(newCapacity, capacityPtr);
    232276        Value * const summary = iBuilder->CreateLoad(summaryPtr, false);
    233         Value * newSummary = iBuilder->CreateRealloc(summary, newSummarySize);
    234         Value * const startNewSummaryPtr = iBuilder->CreateGEP(iBuilder->CreatePointerCast(newArray, int8PtrTy), summarySize);
    235         iBuilder->CreateMemZero(startNewSummaryPtr, iBuilder->getSize(2 * BlockWidth), BlockWidth);
    236 
    237         Value * ptr1 = iBuilder->CreateGEP(newSummary, summarySize);
    238         ptr1 = iBuilder->CreatePointerCast(ptr1, carryPtrTy);
    239 
    240         Value * ptr2 = iBuilder->CreateGEP(newSummary, iBuilder->CreateAdd(summarySize, iBuilder->getSize(BlockWidth)));
    241         ptr2 = iBuilder->CreatePointerCast(ptr2, carryPtrTy);
    242 
    243         newSummary = iBuilder->CreatePointerCast(newSummary, carryPtrTy);
    244         iBuilder->CreateStore(newSummary, summaryPtr);
    245         Value * const newCapacity = iBuilder->CreateShl(ONE, log2capacity);
    246 
    247         iBuilder->CreateStore(newCapacity, capacityPtr);
    248 
     277        Value * const summarySize = iBuilder->CreateShl(iBuilder->CreateAdd(iBuilder->CreateCeilLog2(capacity), ONE), Log2BlockWidth + 1);
     278        Constant * const additionalSpace = iBuilder->getSize(2 * BlockWidth);
     279        Value * const newSummarySize = iBuilder->CreateAdd(summarySize, additionalSpace);
     280        Value * const newSummary = iBuilder->CreateBlockAlignedMalloc(newSummarySize);
     281        iBuilder->CreateMemCpy(newSummary, summary, summarySize, BlockWidth);
     282        iBuilder->CreateFree(summary);
     283        iBuilder->CreateStore(iBuilder->CreatePointerCast(newSummary, carryPtrTy), summaryPtr);
     284        Value * const startNewSummaryPtr = iBuilder->CreateGEP(iBuilder->CreatePointerCast(newSummary, int8PtrTy), summarySize);
     285        iBuilder->CreateMemZero(startNewSummaryPtr, additionalSpace, BlockWidth);
    249286        iBuilder->CreateBr(resumeKernel);
    250287
    251288        // CREATE NEW
    252289        iBuilder->SetInsertPoint(createNew);
    253 
    254290        Constant * const initialLog2Capacity = iBuilder->getInt64(4);
    255291        Constant * const initialCapacity = ConstantExpr::getShl(ONE, initialLog2Capacity);
     292        iBuilder->CreateStore(initialCapacity, capacityPtr);
    256293        Constant * const initialCapacitySize = ConstantExpr::getMul(initialCapacity, carryStateWidth);
    257 
    258         Value * initialArray = iBuilder->CreateAlignedMalloc(initialCapacitySize, iBuilder->getCacheAlignment());
     294        Value * initialArray = iBuilder->CreateCacheAlignedMalloc(initialCapacitySize);
    259295        iBuilder->CreateMemZero(initialArray, initialCapacitySize, BlockWidth);
    260296        initialArray = iBuilder->CreatePointerCast(initialArray, array->getType());
    261297        iBuilder->CreateStore(initialArray, arrayPtr);
    262 
    263298        Constant * initialSummarySize = ConstantExpr::getShl(ConstantExpr::getAdd(initialLog2Capacity, iBuilder->getInt64(1)), iBuilder->getInt64(Log2BlockWidth + 1));
    264         Value * initialSummary = iBuilder->CreateAlignedMalloc(initialSummarySize, BlockWidth);
     299        Value * initialSummary = iBuilder->CreateBlockAlignedMalloc(initialSummarySize);
    265300        iBuilder->CreateMemZero(initialSummary, initialSummarySize, BlockWidth);
    266301        initialSummary = iBuilder->CreatePointerCast(initialSummary, carryPtrTy);
    267302        iBuilder->CreateStore(initialSummary, summaryPtr);
    268 
    269         iBuilder->CreateStore(initialCapacity, capacityPtr);
    270 
    271303        iBuilder->CreateBr(resumeKernel);
    272304
    273305        // RESUME KERNEL
    274306        iBuilder->SetInsertPoint(resumeKernel);
    275         // Load the appropriate carry stat block
    276307        PHINode * phiArrayPtr = iBuilder->CreatePHI(array->getType(), 3);
    277308        phiArrayPtr->addIncoming(array, entry);
     
    316347        // NOTE: this requires that, for all loop iterations, i, and all block iterations, j, the carry in
    317348        // summary, CI_i,j, matches the carry out summary of the prior block iteration, CO_i,j - 1.
    318         // Otherwise we may end up with an incorrect result or being trapped in an infinite loop.
     349        // Otherwise we will end up with an incorrect result or being trapped in an infinite loop.
    319350
    320351        Value * capacityPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(0)});
     
    370401        iBuilder->SetInsertPoint(resume);
    371402
    372         IntegerType * ty = IntegerType::get(iBuilder->getContext(), carryTy->getPrimitiveSizeInBits());
    373         iBuilder->CreateAssert(iBuilder->CreateICmpEQ(iBuilder->CreateBitCast(finalBorrow, ty), ConstantInt::getNullValue(ty)), "finalBorrow != 0");
    374         iBuilder->CreateAssert(iBuilder->CreateICmpEQ(iBuilder->CreateBitCast(finalCarry, ty), ConstantInt::getNullValue(ty)), "finalCarry != 0");
     403        if (codegen::EnableAsserts) {
     404            iBuilder->CreateAssertZero(iBuilder->CreateOr(finalBorrow, finalCarry),
     405                                       "CarryManager: loop post-condition violated: final borrow and carry must be zero!");
     406        }
    375407
    376408        assert (!mLoopIndicies.empty());
     
    778810 * @brief analyse
    779811 ** ------------------------------------------------------------------------------------------------------------- */
    780 StructType * CarryManager::analyse(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const scope, const unsigned ifDepth, const unsigned loopDepth, const bool isNestedWithinNonCarryCollapsingLoop) {
     812StructType * CarryManager::analyse(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, const PabloBlock * const scope,
     813                                   const unsigned ifDepth, const unsigned loopDepth, const bool isNestedWithinNonCarryCollapsingLoop) {
    781814    assert ("scope cannot be null!" && scope);
    782     assert (mCarryScopes == 0 ? (scope == mKernel->getEntryBlock()) : (scope != mKernel->getEntryBlock()));
     815    assert ("entry scope (and only the entry scope) must be in scope 0"
     816            && (mCarryScopes == 0 ? (scope == mKernel->getEntryBlock()) : (scope != mKernel->getEntryBlock())));
    783817    assert (mCarryScopes < mCarryMetadata.size());
    784818    Type * const carryTy = iBuilder->getBitBlockType();
     
    821855        carryState = StructType::get(iBuilder->getContext());
    822856    } else {
    823         //if (ifDepth > 0 || (nonCarryCollapsingMode | isNestedWithinNonCarryCollapsingLoop)) {
    824857        if (dyn_cast_or_null<If>(scope->getBranch()) || nonCarryCollapsingMode || isNestedWithinNonCarryCollapsingLoop) {
    825858            if (LLVM_LIKELY(state.size() > 1)) {
     
    839872        // carry state pointer, and summary pointer struct.
    840873        if (LLVM_UNLIKELY(nonCarryCollapsingMode)) {
     874            mHasNonCarryCollapsingLoops = true;
    841875            carryState = StructType::get(iBuilder->getSizeTy(), carryState->getPointerTo(), carryTy->getPointerTo(), nullptr);
     876            assert (isDynamicallyAllocatedType(carryState));
    842877        }
    843878        cd.setNonCollapsingCarryMode(nonCarryCollapsingMode);
     
    859894, mIfDepth(0)
    860895, mHasLongAdvance(false)
     896, mHasNonCarryCollapsingLoops(false)
    861897, mHasLoop(false)
    862898, mLoopDepth(0)
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.h

    r5486 r5493  
    4848    void initializeCarryData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, PabloKernel * const kernel);
    4949
    50     void releaseCarryData(const std::unique_ptr<kernel::KernelBuilder> & iBuilder, PabloKernel * const kernel);
     50    void releaseCarryData(const std::unique_ptr<kernel::KernelBuilder> & idb);
    5151
    5252    void initializeCodeGen(const std::unique_ptr<kernel::KernelBuilder> & iBuilder);
     
    121121
    122122    bool                                            mHasLongAdvance;
    123 
     123    bool                                            mHasNonCarryCollapsingLoops;
    124124    bool                                            mHasLoop;
    125125    unsigned                                        mLoopDepth;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/distributivepass.cpp

    r5486 r5493  
    629629            cliques.emplace_back(std::move(Ai), std::move(*Bi));
    630630        }
    631         return std::move(cliques);
     631        return cliques;
    632632    }
    633633
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r5486 r5493  
    5252void PabloCompiler::releaseKernelData(const std::unique_ptr<kernel::KernelBuilder> &  iBuilder) {
    5353    assert ("PabloCompiler does not have a IDISA iBuilder" && iBuilder);
    54     mCarryManager->releaseCarryData(iBuilder, mKernel);
     54    mCarryManager->releaseCarryData(iBuilder);
    5555}
    5656
  • icGREP/icgrep-devel/icgrep/pablo/pablo_kernel.cpp

    r5486 r5493  
    176176                         std::vector<Binding> scalar_parameters,
    177177                         std::vector<Binding> scalar_outputs)
    178 : BlockOrientedKernel(std::move(annotateKernelNameWithDebugFlags(std::move(kernelName))),
     178: BlockOrientedKernel(annotateKernelNameWithDebugFlags(std::move(kernelName)),
    179179                      std::move(stream_inputs), std::move(stream_outputs),
    180180                      std::move(scalar_parameters), std::move(scalar_outputs),
Note: See TracChangeset for help on using the changeset viewer.