Changeset 4566 for icGREP/icgrep-devel


Ignore:
Timestamp:
May 19, 2015, 1:09:35 PM (4 years ago)
Author:
cameron
Message:

Restructure to create separate carry data module

Location:
icGREP/icgrep-devel/icgrep
Files:
2 added
4 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/CMakeLists.txt

    r4522 r4566  
    5353find_package(Boost)
    5454
    55 add_library(PabloADT pablo/pabloAST.cpp pablo/ps_assign.cpp pablo/ps_if.cpp pablo/ps_while.cpp pablo/codegenstate.cpp pablo/symbol_generator.cpp pablo/printer_pablos.cpp pablo/pablo_compiler.cpp pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/pablo_codesinking.cpp)
     55add_library(PabloADT pablo/pabloAST.cpp pablo/ps_assign.cpp pablo/ps_if.cpp pablo/ps_while.cpp pablo/codegenstate.cpp pablo/symbol_generator.cpp pablo/printer_pablos.cpp pablo/pablo_compiler.cpp pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/pablo_codesinking.cpp pablo/carry_data.cpp)
    5656add_library(RegExpADT re/re_re.cpp re/re_cc.cpp re/re_parser.cpp re/re_rep.cpp re/parsefailure.cpp re/re_nullable.cpp re/re_simplifier.cpp re/re_compiler.cpp re/printer_re.cpp re/re_diff.cpp re/re_intersect.cpp re/re_analysis.cpp)
    5757add_library(CCADT cc/cc_namemap.cpp cc/cc_compiler.cpp utf8_encoder.cpp UCD/CaseFolding_txt.cpp)
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r4540 r4566  
    88#define PS_PABLOS_H
    99
     10#include <pablo/carry_data.h>
    1011#include <pablo/pabloAST.h>
    1112#include <pablo/symbol_generator.h>
     
    174175    }
    175176   
    176     inline void setCarryIndexBase(const unsigned idx) {
    177         mCarryIndexBase = idx;
    178     }
    179     inline unsigned getCarryIndexBase() const {
    180         return mCarryIndexBase;
    181     }
    182    
    183     inline void setLocalCarryCount(const unsigned c) {
    184         mLocalCarryCount = c;
    185     }
    186     inline unsigned getLocalCarryCount() const {
    187         return mLocalCarryCount;
    188     }
    189    
    190     inline void setLocalAdvanceCount(const unsigned c) {
    191         mLocalAdvanceCount = c;
    192     }
    193     inline unsigned getLocalAdvanceCount() const {
    194         return mLocalAdvanceCount;
    195     }
    196    
    197     inline void setTotalCarryDataSize(const unsigned sz) {
    198         mTotalCarryDataSize = sz;
    199     }
    200     inline unsigned getTotalCarryDataSize() const {
    201         return mTotalCarryDataSize;
    202     }
     177    PabloBlockCarryData carryData;
    203178   
    204179    virtual ~PabloBlock();
    205180
     181   
    206182protected:
    207183    PabloBlock(SymbolGenerator & symbolGenerator);
     
    224200    SymbolGenerator &                                   mSymbolGenerator;
    225201    PabloBlock *                                        mParent;
    226     unsigned                                            mCarryIndexBase;
     202    unsigned                                            mCarryVectorIndex;
     203    unsigned                                            mPackedCarryDataIndex;
    227204    unsigned                                            mLocalCarryCount;
    228205    unsigned                                            mLocalAdvanceCount;
     206    unsigned                                            mTotalCarryVectorSize;
    229207    unsigned                                            mTotalCarryDataSize;
    230208};
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r4552 r4566  
    77#include <pablo/pablo_compiler.h>
    88#include <pablo/codegenstate.h>
     9#include <pablo/carry_data.h>
    910#include <pablo/printer_pablos.h>
    1011#include <cc/cc_namemap.hpp>
     
    115116    mIfDepth = 0;
    116117    mMaxWhileDepth = 0;
    117     unsigned totalCarryDataSize = Examine(pb, 0);
     118    // Get the total number of carry entries; add 1 extra element for the block number.
     119    unsigned totalCarryDataSize = pb.carryData.enumerate(pb) + 1;
     120    Examine(pb);
    118121    mCarryInVector.resize(totalCarryDataSize);
    119122    mCarryOutVector.resize(totalCarryDataSize);
     
    184187
    185188    //Return the required size of the carry data area to the process_block function.
    186     // Reserve 1 element in the carry data area for current block number (future). TODO
    187     return CompiledPabloFunction((totalCarryDataSize + 1) * sizeof(BitBlock), mFunction, mExecutionEngine);
     189    return CompiledPabloFunction(totalCarryDataSize * sizeof(BitBlock), mFunction, mExecutionEngine);
    188190}
    189191
     
    365367}
    366368   
    367 uint64_t log2ceil (uint64_t v) {
    368     unsigned ceil = 1;
    369     while (ceil < v) ceil *= 2;
    370     return ceil;
    371 }
    372 
    373 unsigned const LongAdvanceBase = BLOCK_SIZE;
    374    
    375 
    376    
    377 // CarryDataNumbering
    378 //
    379 // For each PabloBlock, a contiguous CarryData area holds carry,
    380 // and advance values that are generated in one block for use in the
    381 // next.  For a given block, the carry data area contains the
    382 // carries, the advances and the nested data for contained blocks,
    383 // if any.
    384 // Notes:
    385 //   (a) an additional data entry is created for each if-statement
    386 //       having more than one carry or advance opreation within it.  This
    387 //       additional entry is a summary entry which must be nonzero to
    388 //       indicate that there are carry or advance bits associated with
    389 //       any operation within the if-structure (at any nesting level).
    390 //   (b) advancing by a large amount may require multiple advance entries.
    391 //       the number of advance entries for an operation Adv(x, n) is
    392 //       (n + BLOCK_SIZE - 1) / BLOCK_SIZE
    393 //
    394 // Examine precomputes some CarryNumbering and AdvanceNumbering, as
    395 // well as mMaxWhileDepth of while loops.
    396 //
    397 unsigned PabloCompiler::Examine(PabloBlock & blk, unsigned carryDataIndexIn) {
    398     // Count local carries and advances at this level.
    399     unsigned carryDataIndex = carryDataIndexIn;
    400     unsigned localCarries = 0;
    401     unsigned localAdvances = 0;
    402     unsigned nestedCarryDataSize = 0;
    403     for (Statement * stmt : blk) {
    404         if (Advance * adv = dyn_cast<Advance>(stmt)) {
    405             adv->setLocalAdvanceIndex(localAdvances);
    406             unsigned shift_amount = adv->getAdvanceAmount();
    407             if (shift_amount >= LongAdvanceBase) {
    408                 int advEntries = (shift_amount + BLOCK_SIZE - 1) / BLOCK_SIZE;
    409                 int advCeil = log2ceil(advEntries);
    410                 localAdvances += advCeil;
    411             }
    412             else {
    413                 localAdvances += (shift_amount + BLOCK_SIZE - 1) / BLOCK_SIZE;
    414             }
    415         }
    416         else if (MatchStar * m = dyn_cast<MatchStar>(stmt)) {
    417             m->setLocalCarryIndex(localCarries);
    418             ++localCarries;
    419         }
    420         else if (ScanThru * s = dyn_cast<ScanThru>(stmt)) {
    421             s->setLocalCarryIndex(localCarries);
    422             ++localCarries;
    423         }
    424     }
    425     carryDataIndex += localCarries + localAdvances;
     369void PabloCompiler::Examine(PabloBlock & blk) {
    426370    for (Statement * stmt : blk) {
    427371        if (Call * call = dyn_cast<Call>(stmt)) {
     
    430374        else if (If * ifStatement = dyn_cast<If>(stmt)) {
    431375            ++mIfDepth;
    432             const auto ifCarryDataSize = Examine(ifStatement->getBody(), carryDataIndex);
     376            Examine(ifStatement->getBody());
    433377            --mIfDepth;
    434             nestedCarryDataSize += ifCarryDataSize;
    435             carryDataIndex += ifCarryDataSize;
    436378        }
    437379        else if (While * whileStatement = dyn_cast<While>(stmt)) {
    438380            mMaxWhileDepth = std::max(mMaxWhileDepth, ++mWhileDepth);
    439             const auto whileCarryDataSize = Examine(whileStatement->getBody(), carryDataIndex);
     381            Examine(whileStatement->getBody());
    440382            --mWhileDepth;
    441             nestedCarryDataSize += whileCarryDataSize;
    442             carryDataIndex += whileCarryDataSize;
    443         }
    444     }
    445     blk.setCarryIndexBase(carryDataIndexIn);
    446     blk.setLocalCarryCount(localCarries);
    447     blk.setLocalAdvanceCount(localAdvances);
    448     unsigned totalCarryDataSize = localCarries + localAdvances + nestedCarryDataSize;
    449     if ((mIfDepth > 0) && (totalCarryDataSize > 1)) {
    450         // Need extra space for the summary variable, always the last
    451         // entry within an if block.
    452         totalCarryDataSize += 1;
    453     }
    454     blk.setTotalCarryDataSize(totalCarryDataSize);
    455     return totalCarryDataSize;
     383        }
     384    }
    456385}
    457386
     
    510439        IRBuilder<> b_entry(ifEntryBlock);
    511440        mBasicBlock = ifEntryBlock;
     441        const PabloBlockCarryData & cd = ifStatement -> getBody().carryData;
    512442   
    513         const unsigned baseCarryDataIdx = ifStatement->getBody().getCarryIndexBase();
    514         const unsigned carryDataSize = ifStatement->getBody().getTotalCarryDataSize();
    515         const unsigned carrySummaryIndex = baseCarryDataIdx + carryDataSize - 1;
     443        const unsigned baseCarryDataIdx = cd.getBlockCarryDataIndex();
     444        const unsigned carryDataSize = cd.getTotalCarryDataSize();
     445        const unsigned carrySummaryIndex = cd.summaryCarryDataIndex();
    516446       
    517447        Value* if_test_value = compileExpression(ifStatement->getCondition());
     
    577507
    578508void PabloCompiler::compileWhile(const While * whileStatement) {
    579         const unsigned baseCarryDataIdx = whileStatement->getBody().getCarryIndexBase();
    580         const unsigned carryDataSize = whileStatement->getBody().getTotalCarryDataSize();
     509        const PabloBlockCarryData & cd = whileStatement -> getBody().carryData;
     510        const unsigned baseCarryDataIdx = cd.getBlockCarryDataIndex();
     511        const unsigned carryDataSize = cd.getTotalCarryDataSize();
    581512   
    582513        if (mWhileDepth == 0) {
     
    871802Value* PabloCompiler::genAddWithCarry(Value* e1, Value* e2, unsigned localIndex, const PabloBlock * blk) {
    872803    IRBuilder<> b(mBasicBlock);
    873 
    874     //CarryQ - carry in.
    875     const int carryIdx = blk->getCarryIndexBase() + localIndex;
     804    const PabloBlockCarryData & cd = blk->carryData;
     805    const unsigned carryIdx = cd.carryOpCarryDataOffset(localIndex);
    876806    Value* carryq_value = genCarryDataLoad(carryIdx);
    877807#ifdef USE_TWO_UADD_OVERFLOW
     
    942872    }
    943873#ifdef CARRY_DEBUG
     874    std::cerr << "genCarryDataLoad " << index << std::endl;
    944875    genPrintRegister("carry_in_" + std::to_string(index), mCarryInVector[index]);
    945876#endif
     
    955886    }
    956887    mCarryDataSummaryIdx[index] = -1;
     888    mCarryOutVector[index] = carryOut;
    957889#ifdef CARRY_DEBUG
     890    std::cerr << "genCarryDataStore " << index << std::endl;
    958891    genPrintRegister("carry_out_" + std::to_string(index), mCarryOutVector[index]);
    959892#endif
    960     mCarryOutVector[index] = carryOut;
    961893    //std::cerr << "mCarryOutVector[" << index << "]]\n";
    962894}
     
    991923        return genLongAdvanceWithCarry(strm_value, shift_amount, localIndex, blk);
    992924    }
     925    else if (shift_amount == 1) {
     926        return genUnitAdvanceWithCarry(strm_value, localIndex, blk);
     927    }
    993928    IRBuilder<> b(mBasicBlock);
    994     const auto advanceIndex = blk->getCarryIndexBase() + blk->getLocalCarryCount() + localIndex;
     929    const PabloBlockCarryData & cd = blk->carryData;
     930    const auto advanceIndex = cd.shortAdvanceCarryDataOffset(localIndex);
    995931    Value* result_value;
    996932   
    997933    if (shift_amount == 0) {
    998934        result_value = genCarryDataLoad(advanceIndex);
    999         //b.CreateCall(mFunc_print_register, result_value);
    1000     }
    1001 #if (BLOCK_SIZE == 128) && !defined(USE_LONG_INTEGER_SHIFT)
    1002     if (shift_amount == 1) {
    1003         Value* advanceq_value = genShiftHighbitToLow(BLOCK_SIZE, genCarryDataLoad(advanceIndex));
    1004         Value* srli_1_value = b.CreateLShr(strm_value, 63);
    1005         Value* packed_shuffle;
    1006         Constant* const_packed_1_elems [] = {b.getInt32(0), b.getInt32(2)};
    1007         Constant* const_packed_1 = ConstantVector::get(const_packed_1_elems);
    1008         packed_shuffle = b.CreateShuffleVector(advanceq_value, srli_1_value, const_packed_1);
    1009        
    1010         Constant* const_packed_2_elems[] = {b.getInt64(1), b.getInt64(1)};
    1011         Constant* const_packed_2 = ConstantVector::get(const_packed_2_elems);
    1012        
    1013         Value* shl_value = b.CreateShl(strm_value, const_packed_2);
    1014         result_value = b.CreateOr(shl_value, packed_shuffle, "advance");
    1015     }
    1016     else { //if (block_shift < BLOCK_SIZE) {
    1017         // This is the preferred logic, but is too slow for the general case.
    1018         // We need to speed up our custom LLVM for this code.
     935    }
     936    else {
    1019937        Value* advanceq_longint = b.CreateBitCast(genCarryDataLoad(advanceIndex), b.getIntNTy(BLOCK_SIZE));
    1020938        Value* strm_longint = b.CreateBitCast(strm_value, b.getIntNTy(BLOCK_SIZE));
     
    1022940        result_value = b.CreateBitCast(adv_longint, mBitBlockType);
    1023941    }
     942    genCarryDataStore(strm_value, advanceIndex);
     943    return result_value;
     944}
     945                   
     946Value* PabloCompiler::genUnitAdvanceWithCarry(Value* strm_value, unsigned localIndex, const PabloBlock * blk) {
     947    IRBuilder<> b(mBasicBlock);
     948    const PabloBlockCarryData & cd = blk->carryData;
     949    const auto advanceIndex = cd.unitAdvanceCarryDataOffset(localIndex);
     950    Value* result_value;
     951   
     952#if (BLOCK_SIZE == 128) && !defined(USE_LONG_INTEGER_SHIFT)
     953    Value* advanceq_value = genShiftHighbitToLow(BLOCK_SIZE, genCarryDataLoad(advanceIndex));
     954    Value* srli_1_value = b.CreateLShr(strm_value, 63);
     955    Value* packed_shuffle;
     956    Constant* const_packed_1_elems [] = {b.getInt32(0), b.getInt32(2)};
     957    Constant* const_packed_1 = ConstantVector::get(const_packed_1_elems);
     958    packed_shuffle = b.CreateShuffleVector(advanceq_value, srli_1_value, const_packed_1);
     959   
     960    Constant* const_packed_2_elems[] = {b.getInt64(1), b.getInt64(1)};
     961    Constant* const_packed_2 = ConstantVector::get(const_packed_2_elems);
     962   
     963    Value* shl_value = b.CreateShl(strm_value, const_packed_2);
     964    result_value = b.CreateOr(shl_value, packed_shuffle, "advance");
    1024965#else
    1025966    Value* advanceq_longint = b.CreateBitCast(genCarryDataLoad(advanceIndex), b.getIntNTy(BLOCK_SIZE));
    1026967    Value* strm_longint = b.CreateBitCast(strm_value, b.getIntNTy(BLOCK_SIZE));
    1027     Value* adv_longint = b.CreateOr(b.CreateShl(strm_longint, shift_amount), b.CreateLShr(advanceq_longint, BLOCK_SIZE - shift_amount), "advance");
     968    Value* adv_longint = b.CreateOr(b.CreateShl(strm_longint, 1), b.CreateLShr(advanceq_longint, BLOCK_SIZE - 1), "advance");
    1028969    result_value = b.CreateBitCast(adv_longint, mBitBlockType);
    1029970   
     
    1032973    return result_value;
    1033974}
    1034 
    1035 //
     975                   
     976                    //
    1036977// Generate code for long advances >= LongAdvanceBase
    1037978//
    1038979Value* PabloCompiler::genLongAdvanceWithCarry(Value* strm_value, int shift_amount, unsigned localIndex, const PabloBlock * blk) {
    1039980    IRBuilder<> b(mBasicBlock);
    1040     const unsigned advanceIndex = blk->getCarryIndexBase() + blk->getLocalCarryCount() + localIndex;
    1041     const unsigned advanceEntries = (shift_amount + BLOCK_SIZE - 1) / BLOCK_SIZE;
     981    const PabloBlockCarryData & cd = blk->carryData;
    1042982    const unsigned block_shift = shift_amount % BLOCK_SIZE;
    1043     const unsigned advanceCeil = log2ceil(advanceEntries);
    1044     Value * indexMask = b.getInt64(advanceCeil - 1);
    1045     Value * advBaseIndex = b.getInt64(advanceIndex);
     983    const unsigned advanceEntries = cd.longAdvanceEntries(shift_amount);
     984    const unsigned bufsize = cd.longAdvanceBufferSize(shift_amount);
     985    std::cerr << "shift_amount = " << shift_amount << " bufsize = " << bufsize << std::endl;
     986    Value * indexMask = b.getInt64(bufsize - 1);  // A mask to implement circular buffer indexing
     987    Value * advBaseIndex = b.getInt64(cd.longAdvanceCarryDataOffset(localIndex));
    1046988    Value * storeIndex = b.CreateAdd(b.CreateAnd(mBlockNo, indexMask), advBaseIndex);
    1047989    Value * loadIndex = b.CreateAdd(b.CreateAnd(b.CreateSub(mBlockNo, b.getInt64(advanceEntries)), indexMask), advBaseIndex);
     
    10611003    else {
    10621004        // The advance is based on the two oldest bit blocks in the advance buffer.
    1063         // The buffer is maintained as a circular buffer of size advanceCeil.
     1005        // The buffer is maintained as a circular buffer of size bufsize.
    10641006        // Indexes within the buffer are computed by bitwise and with the indexMask.
    10651007        Value * loadIndex2 = b.CreateAdd(b.CreateAnd(b.CreateSub(mBlockNo, b.getInt64(advanceEntries-1)), indexMask), advBaseIndex);
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.h

    r4548 r4566  
    100100    void DefineTypes();
    101101    void DeclareFunctions();
    102     unsigned Examine(PabloBlock & blk, unsigned carryDataIndexIn);
     102    void Examine(PabloBlock & blk);
    103103    void DeclareCallFunctions();
    104104    void SetOutputValue(Value * marker, const unsigned index);
     
    114114    Value* genAddWithCarry(Value* e1, Value* e2, unsigned localIndex, const PabloBlock * blk);
    115115    Value* genAdvanceWithCarry(Value* e1, int shift_amount, unsigned localIndex, const PabloBlock * blk);
     116    Value* genUnitAdvanceWithCarry(Value* e1, unsigned localIndex, const PabloBlock * blk);
    116117    Value* genLongAdvanceWithCarry(Value* e1, int shift_amount, unsigned localIndex, const PabloBlock * blk);
    117118    Value* genBitBlockAny(Value* test);
Note: See TracChangeset for help on using the changeset viewer.