Ignore:
Timestamp:
Mar 24, 2017, 4:01:22 PM (2 years ago)
Author:
nmedfort
Message:

Bug fix for long advance

Location:
icGREP/icgrep-devel/icgrep
Files:
19 edited

Legend:

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

    r5369 r5371  
    5656SET(PABLO_SRC ${PABLO_SRC} pablo/pablo_kernel.cpp pablo/pablo_compiler.cpp pablo/carry_manager.cpp)
    5757SET(PABLO_SRC ${PABLO_SRC} pablo/analysis/pabloverifier.cpp)
     58SET(PABLO_SRC ${PABLO_SRC} pablo/passes/ssapass.cpp)
    5859SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/codemotionpass.cpp pablo/passes/flattenif.cpp)
    5960IF(ENABLE_MULTIPLEXING)
  • icGREP/icgrep-devel/icgrep/IR_Gen/CBuilder.cpp

    r5368 r5371  
    397397}
    398398
    399 Value * CBuilder::CreateCeilLog2(Value * value) {
     399Value * CBuilder::CreateCeilLog2(Value * const value) {
    400400    IntegerType * ty = cast<IntegerType>(value->getType());
    401401    CreateAssert(value, "CreateCeilLog2: value cannot be zero");
    402     Value * m = CreateCall(Intrinsic::getDeclaration(mMod, Intrinsic::ctlz, ty), {value, ConstantInt::getFalse(getContext())});
    403     Value * isPowOf2 = CreateICmpEQ(CreateAnd(value, CreateSub(value, ConstantInt::get(ty, 1))), ConstantInt::getNullValue(ty));
    404     m = CreateSub(ConstantInt::get(m->getType(), ty->getBitWidth() - 1), m);
    405     return CreateSelect(isPowOf2, m, CreateAdd(m, ConstantInt::get(m->getType(), 1)));
     402    Value * v = CreateSub(value, ConstantInt::get(ty, 1));
     403    Value * m = CreateCall(Intrinsic::getDeclaration(mMod, Intrinsic::ctlz, ty), {v, ConstantInt::getFalse(getContext())});
     404    return CreateSub(ConstantInt::get(m->getType(), ty->getBitWidth()), m);
    406405}
    407406
  • icGREP/icgrep-devel/icgrep/array-test.cpp

    r5368 r5371  
    3434#include <iostream>
    3535
     36#include <pablo/passes/ssapass.h>
     37
    3638namespace llvm { class Type; }
    3739namespace pablo { class Integer; }
     
    7779    Var * matches = kernel->getOutputStreamVar("matches");
    7880
    79     PabloBuilder body = PabloBuilder::Create(pb);
    80 
    81     pb.createWhile(pending_lparen, body);
     81//    PabloBuilder outer = PabloBuilder::Create(pb);
     82
     83//    pb.createWhile(pending_lparen, outer);
     84
     85    PabloBuilder body = PabloBuilder::Create(pb); // outer
     86
     87    pb.createWhile(pending_lparen, body); // outer
    8288
    8389        PabloAST * adv_pending_lparen = body.createAdvance(pending_lparen, 1);
     
    117123
    118124}
    119 
    120 
    121 //void generate(PabloKernel * kernel) {
    122 
    123 //    PabloBuilder pb(kernel->getEntryBlock());
    124 
    125 //    Var * input = kernel->getInputStreamVar("input");
    126 
    127 //    PabloAST * basis[8];
    128 //    for (int i = 0; i < 8; ++i) {
    129 //        basis[i] = pb.createExtract(input, i);
    130 //    }
    131 
    132 //    PabloAST * temp1 = pb.createOr(basis[0], basis[1], "temp1");
    133 //    PabloAST * temp2 = pb.createAnd(basis[2], pb.createNot(basis[3]), "temp2");
    134 //    PabloAST * temp3 = pb.createAnd(temp2, pb.createNot(temp1), "temp3");
    135 //    PabloAST * temp4 = pb.createAnd(basis[4], pb.createNot(basis[5]), "temp4");
    136 //    PabloAST * temp5 = pb.createOr(basis[6], basis[7], "temp5");
    137 //    PabloAST * temp6 = pb.createAnd(temp4, pb.createNot(temp5), "temp6");
    138 //    PabloAST * lparen = pb.createAnd(temp3, temp6, "lparens");
    139 //    PabloAST * temp7 = pb.createAnd(basis[7], pb.createNot(basis[6]), "temp7");
    140 //    PabloAST * temp8 = pb.createAnd(temp4, temp7, "temp8");
    141 //    PabloAST * rparen = pb.createAnd(temp3, temp8, "rparens");
    142 //    PabloAST * parens = pb.createOr(lparen, rparen, "parens");
    143 
    144 
    145 //    Var * const pending_lparen = pb.createVar("pending_lparen", lparen);
    146 //    Var * const all_closed = pb.createVar("all_closed", pb.createZeroes());
    147 //    Var * const accumulated_errors = pb.createVar("accumulated_errors", pb.createZeroes());
    148 //    Var * const in_play = pb.createVar("in_play", parens);
    149 //    Var * const index = pb.createVar("i", pb.getInteger(0));
    150 
    151 //    Var * matches = kernel->getOutputStreamVar("matches");
    152 
    153 //    PabloBuilder body = PabloBuilder::Create(pb);
    154 
    155 //    pb.createWhile(pending_lparen, body);
    156 
    157 //        PabloAST * adv_pending_lparen = body.createAdvance(pending_lparen, 1);
    158 
    159 //        Var * closed_rparen = body.createVar("closed_rparen", pb.createZeroes());
    160 
    161 //        PabloBuilder ifPScan = PabloBuilder::Create(body);
    162 
    163 //        body.createIf(adv_pending_lparen, ifPScan); // <-- inefficient but tests whether we're probably calculating the summary later
    164 
    165 //            PabloAST * pscan = ifPScan.createScanTo(adv_pending_lparen, in_play, "pscan");
    166 
    167 //            ifPScan.createAssign(pending_lparen, ifPScan.createAnd(pscan, lparen));
    168 
    169 //            ifPScan.createAssign(closed_rparen, ifPScan.createAnd(pscan, rparen));
    170 
    171 //            ifPScan.createAssign(all_closed, ifPScan.createOr(all_closed, closed_rparen));
    172 
    173 //            // Mark any opening paren without a matching closer as an error.
    174 //            PabloAST * unmatched_lparen = ifPScan.createAtEOF(pscan, "unmatched_lparen");
    175 
    176 //            ifPScan.createAssign(accumulated_errors, ifPScan.createOr(accumulated_errors, unmatched_lparen));
    177 
    178 //            PabloAST * pending_rparen = ifPScan.createAnd(rparen, ifPScan.createNot(all_closed, "open_rparen"), "pending_rparen");
    179 
    180 //            ifPScan.createAssign(in_play, ifPScan.createOr(pending_lparen, pending_rparen));
    181 
    182 //        body.createAssign(body.createExtract(matches, index), closed_rparen);
    183 
    184 //        body.createAssign(index, body.createAdd(index, body.getInteger(1)));
    185 
    186 //    // Mark any closing paren that was not actually used to close an opener as an error.
    187 //    PabloAST * const unmatched_rparen = pb.createAnd(rparen, pb.createNot(all_closed), "unmatched_rparen");
    188 //    pb.createAssign(kernel->getOutputStreamVar("errors"), pb.createOr(accumulated_errors, unmatched_rparen));
    189 
    190 //}
    191 
    192 //void generate(PabloKernel * kernel) {
    193 
    194 //    PabloBuilder pb(kernel->getEntryBlock());
    195 
    196 //    Var * input = kernel->getInputStreamVar("input");
    197 
    198 //    PabloAST * basis[8];
    199 //    for (int i = 0; i < 8; ++i) {
    200 //        basis[i] = pb.createExtract(input, i);
    201 //    }
    202 
    203 //    PabloAST * temp1 = pb.createOr(basis[0], basis[1], "temp1");
    204 //    PabloAST * temp2 = pb.createAnd(basis[2], pb.createNot(basis[3]), "temp2");
    205 //    PabloAST * temp3 = pb.createAnd(temp2, pb.createNot(temp1), "temp3");
    206 //    PabloAST * temp4 = pb.createAnd(basis[4], pb.createNot(basis[5]), "temp4");
    207 //    PabloAST * temp5 = pb.createOr(basis[6], basis[7], "temp5");
    208 //    PabloAST * temp6 = pb.createAnd(temp4, pb.createNot(temp5), "temp6");
    209 //    PabloAST * lparen = pb.createAnd(temp3, temp6, "lparens");
    210 //    PabloAST * temp7 = pb.createAnd(basis[7], pb.createNot(basis[6]), "temp7");
    211 //    PabloAST * temp8 = pb.createAnd(temp4, temp7, "temp8");
    212 //    PabloAST * rparen = pb.createAnd(temp3, temp8, "rparens");
    213 //    PabloAST * parens = pb.createOr(lparen, rparen, "parens");
    214 
    215 
    216 //    Var * const pending_lparen = pb.createVar("pending_lparen", lparen);
    217 //    Var * const all_closed = pb.createVar("all_closed", pb.createZeroes());
    218 //    Var * const accumulated_errors = pb.createVar("accumulated_errors", pb.createZeroes());
    219 //    Var * const in_play = pb.createVar("in_play", parens);
    220 //    Var * const index = pb.createVar("i", pb.getInteger(0));
    221 
    222 //    Var * matches = kernel->getOutputStreamVar("matches");
    223 
    224 //    PabloBuilder body = PabloBuilder::Create(pb);
    225 
    226 //    pb.createWhile(pending_lparen, body);
    227 
    228 //        PabloAST * pscan = body.createAdvanceThenScanTo(pending_lparen, in_play, "pscan");
    229 
    230 //        Var * closed_rparen = body.createVar("closed_rparen", pb.createZeroes());
    231 
    232 //        body.createAssign(pending_lparen, body.createAnd(pscan, lparen));
    233 
    234 //        PabloBuilder ifPScan = PabloBuilder::Create(body);
    235 
    236 //        body.createIf(pscan, ifPScan);
    237 
    238 //            ifPScan.createAssign(closed_rparen, ifPScan.createAnd(pscan, rparen));
    239 
    240 //            ifPScan.createAssign(all_closed, ifPScan.createOr(all_closed, closed_rparen));
    241 
    242 //            // Mark any opening paren without a matching closer as an error.
    243 //            PabloAST * unmatched_lparen = ifPScan.createAtEOF(pscan, "unmatched_lparen");
    244 //            ifPScan.createAssign(accumulated_errors, ifPScan.createOr(accumulated_errors, unmatched_lparen));
    245 
    246 //            PabloAST * pending_rparen = ifPScan.createAnd(rparen, ifPScan.createNot(all_closed, "open_rparen"), "pending_rparen");
    247 
    248 //            ifPScan.createAssign(in_play, ifPScan.createOr(pending_lparen, pending_rparen));
    249 
    250 //            ifPScan.createAssign(ifPScan.createExtract(matches, index), closed_rparen);
    251 
    252 //        body.createAssign(index, body.createAdd(index, body.getInteger(1)));
    253 
    254 //    // Mark any closing paren that was not actually used to close an opener as an error.
    255 //    PabloAST * const unmatched_rparen = pb.createAnd(rparen, pb.createNot(all_closed), "unmatched_rparen");
    256 //    pb.createAssign(kernel->getOutputStreamVar("errors"), pb.createOr(accumulated_errors, unmatched_rparen));
    257 
    258 //}
    259 
    260 //void generate(PabloKernel * kernel) {
    261 
    262 //    PabloBuilder pb(kernel->getEntryBlock());
    263 
    264 //    Var * input = kernel->getInputStreamVar("input");
    265 
    266 //    PabloAST * basis[8];
    267 //    for (int i = 0; i < 8; ++i) {
    268 //        basis[i] = pb.createExtract(input, i);
    269 //    }
    270 
    271 //    PabloAST * temp1 = pb.createOr(basis[0], basis[1], "temp1");
    272 //    PabloAST * temp2 = pb.createAnd(basis[2], pb.createNot(basis[3]), "temp2");
    273 //    PabloAST * temp3 = pb.createAnd(temp2, pb.createNot(temp1), "temp3");
    274 //    PabloAST * temp4 = pb.createAnd(basis[4], pb.createNot(basis[5]), "temp4");
    275 //    PabloAST * temp5 = pb.createOr(basis[6], basis[7], "temp5");
    276 //    PabloAST * temp6 = pb.createAnd(temp4, pb.createNot(temp5), "temp6");
    277 //    PabloAST * lparen = pb.createAnd(temp3, temp6, "lparens");
    278 //    PabloAST * temp7 = pb.createAnd(basis[7], pb.createNot(basis[6]), "temp7");
    279 //    PabloAST * temp8 = pb.createAnd(temp4, temp7, "temp8");
    280 //    PabloAST * rparen = pb.createAnd(temp3, temp8, "rparens");
    281 //    PabloAST * parens = pb.createOr(lparen, rparen, "parens");
    282 
    283 
    284 //    Var * const pending_lparen = pb.createVar("pending_lparen", lparen);
    285 //    Var * const all_closed = pb.createVar("all_closed", pb.createZeroes());
    286 //    Var * const accumulated_errors = pb.createVar("accumulated_errors", pb.createZeroes());
    287 //    Var * const in_play = pb.createVar("in_play", parens);
    288 //    Var * const index = pb.createVar("i", pb.getInteger(0));
    289 
    290 //    Var * matches = kernel->getOutputStreamVar("matches");
    291 
    292 //    PabloBuilder body = PabloBuilder::Create(pb);
    293 
    294 //    pb.createWhile(pending_lparen, body);
    295 
    296 //        PabloAST * pscan = body.createAdvanceThenScanTo(pending_lparen, in_play, "pscan");
    297 
    298 //        PabloAST * closed_rparen = body.createAnd(pscan, rparen, "closed_rparen");
    299 //        body.createAssign(all_closed, body.createOr(all_closed, closed_rparen));
    300 
    301 //        body.createAssign(pending_lparen, body.createAnd(pscan, lparen));
    302 //        // Mark any opening paren without a matching closer as an error.
    303 //        PabloAST * unmatched_lparen = body.createAtEOF(pscan, "unmatched_lparen");
    304 //        body.createAssign(accumulated_errors, body.createOr(accumulated_errors, unmatched_lparen));
    305 
    306 //        body.createAssign(body.createExtract(matches, index), closed_rparen);
    307 
    308 //        PabloAST * pending_rparen = body.createAnd(rparen, body.createNot(all_closed, "open_rparen"), "pending_rparen");
    309 //        body.createAssign(in_play, body.createOr(pending_lparen, pending_rparen));
    310 //        body.createAssign(index, body.createAdd(index, body.getInteger(1)));
    311 
    312 //    // Mark any closing paren that was not actually used to close an opener as an error.
    313 //    PabloAST * const unmatched_rparen = pb.createAnd(rparen, pb.createNot(all_closed), "unmatched_rparen");
    314 //    pb.createAssign(kernel->getOutputStreamVar("errors"), pb.createOr(accumulated_errors, unmatched_rparen));
    315 
    316 //}
    317125
    318126Function * pipeline(IDISA::IDISA_Builder * iBuilder, const unsigned count) {
     
    350158
    351159    generate(&bm);
     160//    SSAPass::transform(&bm);
     161
    352162//    pablo_function_passes(&bm);
    353163
  • icGREP/icgrep-devel/icgrep/pablo/analysis/pabloverifier.cpp

    r5283 r5371  
    22#include <pablo/branch.h>
    33#include <pablo/pe_var.h>
     4#include <pablo/pe_phi.h>
    45#include <pablo/ps_assign.h>
    56#include <pablo/codegenstate.h>
  • icGREP/icgrep-devel/icgrep/pablo/branch.cpp

    r5283 r5371  
    1010
    1111namespace pablo {
    12 
    13 Branch::Branch(const ClassTypeId typeId, PabloAST * condition, PabloBlock * body, Allocator &allocator)
    14 : Statement(typeId, nullptr, {condition}, nullptr, allocator)
    15 , mBody(body) {
    16 
    17 }
    1812
    1913/** ------------------------------------------------------------------------------------------------------------- *
     
    9892}
    9993
     94/** ------------------------------------------------------------------------------------------------------------- *
     95 * @brief setBody
     96 ** ------------------------------------------------------------------------------------------------------------- */
    10097PabloBlock * Branch::setBody(PabloBlock * const body) {
    10198    body->setBranch(this);
     
    106103}
    107104
     105
     106/** ------------------------------------------------------------------------------------------------------------- *
     107 * @brief constructor
     108 ** ------------------------------------------------------------------------------------------------------------- */
     109Branch::Branch(const ClassTypeId typeId, PabloAST * condition, PabloBlock * body, Allocator &allocator)
     110: Statement(typeId, nullptr, {condition}, nullptr, allocator)
     111, mBody(body)
     112, mEscapedCount(0)
     113, mEscapedCapacity(0)
     114, mEscaped(nullptr)
     115{
     116
    108117}
     118
     119}
  • icGREP/icgrep-devel/icgrep/pablo/branch.h

    r5267 r5371  
    4141    EscapedVars getEscaped() const;
    4242protected:
     43    void addEscaped(PabloAST * const node);
     44    void removeEscaped(PabloAST * const node);
    4345    Branch(const ClassTypeId typeId, PabloAST * condition, PabloBlock * body, Allocator & allocator);
    4446protected:
    45     PabloBlock * mBody;
     47    PabloBlock *    mBody;
     48    unsigned        mEscapedCount;
     49    unsigned        mEscapedCapacity;
     50    PabloAST **     mEscaped;
    4651};
    4752
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.cpp

    r5368 r5371  
    1717#include <pablo/pe_var.h>
    1818
     19#include <llvm/Support/raw_ostream.h>
     20
    1921using namespace llvm;
    2022
    2123namespace 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}
    2229
    2330inline static unsigned floor_log2(const unsigned v) {
     
    2633}
    2734
    28 inline static unsigned nearest_pow2(const uint32_t v) {
     35inline static unsigned nearest_pow2(const unsigned v) {
    2936    assert(v > 0 && v < (UINT32_MAX / 2));
    30     return (v < 2) ? 1 : (1 << (32 - __builtin_clz(v - 1)));
     37    return (v < 2) ? 1 : (1 << ceil_log2(v));
    3138}
    3239
     
    5057}
    5158
     59#define LONG_ADVANCE_BREAKPOINT 64
     60
    5261/** ------------------------------------------------------------------------------------------------------------- *
    5362 * @brief initializeCarryData
     
    7988    mCarryMetadata.resize(getScopeCount(kernel->getEntryBlock()));
    8089
    81     Type * ty = analyse(kernel->getEntryBlock());
    82 
    83     mKernel->addScalar(ty, "carries");
     90    Type * const carryStateTy = analyse(kernel->getEntryBlock());
     91
     92    mKernel->addScalar(carryStateTy, "carries");
    8493
    8594    if (mHasLoop) {
     
    129138    }
    130139    assert (mCarryFrameStack.empty());   
    131     assert (mCarrySummaryStack.size() == 1);
    132     assert ("base summary value was overwritten!" && isa<Constant>(mCarrySummaryStack[0]) && cast<Constant>(mCarrySummaryStack[0])->isNullValue());
     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());
    133142    mCarrySummaryStack.clear();
    134 
    135143    assert (mCarryScopeIndex.size() == 1);
    136144    mCarryScopeIndex.clear();
     
    524532Value * CarryManager::advanceCarryInCarryOut(const Advance * const advance, Value * const value) {
    525533    const auto shiftAmount = advance->getAmount();
    526     if (LLVM_LIKELY(shiftAmount <= mBitBlockWidth)) {
     534    if (LLVM_LIKELY(shiftAmount < LONG_ADVANCE_BREAKPOINT)) {
    527535        Value * const carryIn = getNextCarryIn();
    528536        Value * carryOut, * result;
    529         if (LLVM_UNLIKELY(shiftAmount == mBitBlockWidth)) {
    530             result = carryIn;
    531             carryOut = value;
    532         } else {
    533             std::tie(carryOut, result) = iBuilder->bitblock_advance(value, carryIn, shiftAmount);
    534         }
     537        std::tie(carryOut, result) = iBuilder->bitblock_advance(value, carryIn, shiftAmount);
    535538        setNextCarryOut(carryOut);
    536539        assert (result->getType() == mBitBlockType);
     
    544547 * @brief longAdvanceCarryInCarryOut
    545548 ** ------------------------------------------------------------------------------------------------------------- */
    546 Value * CarryManager::longAdvanceCarryInCarryOut(Value * const value, const unsigned shiftAmount) {
    547 
    548     assert (shiftAmount > mBitBlockWidth);
     549inline Value * CarryManager::longAdvanceCarryInCarryOut(Value * const value, const unsigned shiftAmount) {
     550
    549551    assert (mHasLongAdvance);
    550 
    551     Type * const streamVectorTy = iBuilder->getIntNTy(mBitBlockWidth);
    552     Value * buffer = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex++), iBuilder->getInt32(0)});
    553 
    554     const unsigned blockShift = shiftAmount % mBitBlockWidth;
    555     const unsigned entries = ceil_udiv(shiftAmount, mBitBlockWidth);
    556 
    557     if (LLVM_LIKELY(mCarryInfo->hasExplicitSummary())) {
    558         Value * const summaryPtr = iBuilder->CreateGEP(buffer, iBuilder->getInt32(0));
    559         assert (summaryPtr->getType()->getPointerElementType() == mBitBlockType);
    560         Value * carry = iBuilder->CreateZExtOrBitCast(iBuilder->bitblock_any(value), streamVectorTy);
    561         const auto limit = ceil_udiv(shiftAmount, std::pow(mBitBlockWidth, 2));
    562         assert (limit == summaryPtr->getType()->getPointerElementType()->getArrayNumElements());
    563         for (unsigned i = 0;;++i) {
    564             Value * ptr = iBuilder->CreateGEP(summaryPtr, iBuilder->getInt32(i));
    565             Value * prior = iBuilder->CreateBitCast(iBuilder->CreateBlockAlignedLoad(ptr), streamVectorTy);
    566             Value * stream = iBuilder->CreateOr(iBuilder->CreateShl(prior, 1), carry);
    567             if (LLVM_LIKELY(i == limit)) {
    568                 stream = iBuilder->CreateAnd(stream, iBuilder->bitblock_mask_from(iBuilder->getInt32(entries % mBitBlockWidth)));
     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                }
    569571                addToCarryOutSummary(stream);
    570                 iBuilder->CreateBlockAlignedStore(stream, ptr);               
    571                 buffer = iBuilder->CreateGEP(buffer, iBuilder->getInt32(1));
    572                 break;
     572                iBuilder->CreateBlockAlignedStore(stream, ptr);
     573                carry = iBuilder->CreateLShr(prior, mBitBlockWidth - 1);
    573574            }
    574             addToCarryOutSummary(stream);
    575             iBuilder->CreateBlockAlignedStore(stream, ptr);
    576             carry = iBuilder->CreateLShr(prior, mBitBlockWidth - 1);
    577         }
    578     }
    579     assert (buffer->getType()->getPointerElementType() == mBitBlockType);
    580 
    581     // Create a mask to implement circular buffer indexing
    582     Value * indexMask = iBuilder->getSize(nearest_pow2(entries) - 1);   
    583     Value * blockIndex = mKernel->getScalarField("CarryBlockIndex");
    584     Value * carryIndex0 = iBuilder->CreateSub(blockIndex, iBuilder->getSize(entries));
    585     Value * loadIndex0 = iBuilder->CreateAnd(carryIndex0, indexMask);
    586     Value * storeIndex = iBuilder->CreateAnd(blockIndex, indexMask);
    587     Value * carryIn = iBuilder->CreateBlockAlignedLoad(iBuilder->CreateGEP(buffer, loadIndex0));
    588     assert (carryIn->getType() == mBitBlockType);
    589 
    590     // If the long advance is an exact multiple of BitBlockWidth, we simply return the oldest
    591     // block in the long advance carry data area. 
    592     if (blockShift == 0) {
    593         iBuilder->CreateBlockAlignedStore(value, iBuilder->CreateGEP(buffer, storeIndex));
    594         return carryIn;
    595     }
    596     // Otherwise we need to combine data from the two oldest blocks.
    597     Value * carryIndex1 = iBuilder->CreateSub(blockIndex, iBuilder->getSize(entries - 1));
    598     Value * loadIndex1 = iBuilder->CreateAnd(carryIndex1, indexMask);
    599     Value * carry_block1 = iBuilder->CreateBlockAlignedLoad(iBuilder->CreateGEP(buffer, loadIndex1));
    600     Value * block0_shr = iBuilder->CreateLShr(iBuilder->CreateBitCast(carryIn, streamVectorTy), mBitBlockWidth - blockShift);
    601     Value * block1_shl = iBuilder->CreateShl(iBuilder->CreateBitCast(carry_block1, streamVectorTy), blockShift);
    602     iBuilder->CreateBlockAlignedStore(value, iBuilder->CreateGEP(buffer, storeIndex));
    603     return iBuilder->CreateBitCast(iBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
     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    }
    604624}
    605625
     
    609629Value * CarryManager::getNextCarryIn() {
    610630    assert (mCurrentFrameIndex < mCurrentFrame->getType()->getPointerElementType()->getStructNumElements());
    611     Value * carryInPtr = nullptr;
    612631    if (mLoopDepth == 0) {
    613         carryInPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex)});
     632        mCarryPackPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex)});
    614633    } else {
    615         carryInPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex), mLoopSelector});
    616     }
    617     assert (carryInPtr->getType()->getPointerElementType() == mCarryPackType);
    618     Value * const carryIn = iBuilder->CreateBlockAlignedLoad(carryInPtr);
     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);
    619638    if (mLoopDepth > 0) {
    620         iBuilder->CreateBlockAlignedStore(Constant::getNullValue(mCarryPackType), carryInPtr);
     639        iBuilder->CreateBlockAlignedStore(Constant::getNullValue(mCarryPackType), mCarryPackPtr);
    621640    }
    622641    return carryIn;
     
    632651        addToCarryOutSummary(carryOut);
    633652    }
    634     Value * carryOutPtr = nullptr;
    635     if (mLoopDepth == 0) {
    636         carryOutPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex)});
    637     } else {
    638         carryOutPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex), mNextLoopSelector});
     653    if (mLoopDepth != 0) {
     654        mCarryPackPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex), mNextLoopSelector});
    639655        if (LLVM_LIKELY(!mCarryInfo->nonCarryCollapsingMode())) {
    640             Value * accum = iBuilder->CreateBlockAlignedLoad(carryOutPtr);
     656            Value * accum = iBuilder->CreateBlockAlignedLoad(mCarryPackPtr);
    641657            carryOut = iBuilder->CreateOr(carryOut, accum);
    642658        }
    643659    }
    644660    ++mCurrentFrameIndex;
    645     assert (carryOutPtr->getType()->getPointerElementType() == mCarryPackType);
    646     iBuilder->CreateBlockAlignedStore(carryOut, carryOutPtr);
     661    assert (mCarryPackPtr->getType()->getPointerElementType() == mCarryPackType);
     662    iBuilder->CreateBlockAlignedStore(carryOut, mCarryPackPtr);
    647663}
    648664
     
    652668Value * CarryManager::readCarryInSummary(ConstantInt * index) const {
    653669    assert (mCarryInfo->hasSummary());
     670
    654671    unsigned count = 2;
    655672    if (LLVM_UNLIKELY(mCarryInfo->hasBorrowedSummary())) {
     
    668685        indicies[count] = mLoopSelector;
    669686    }
     687
    670688    ArrayRef<Value *> ar(indicies, length);
    671689    Value * const ptr = iBuilder->CreateGEP(mCurrentFrame, ar);
     
    754772    const bool nonCarryCollapsingMode = hasIterationSpecificAssignment(scope);
    755773    Type * const carryPackType = (loopDepth == 0) ? mCarryPackType : ArrayType::get(mCarryPackType, 2);
    756     bool hasLongAdvances = false;
    757774    std::vector<Type *> state;
    758775
     
    761778            const auto amount = cast<Advance>(stmt)->getAmount();
    762779            Type * type = carryPackType;
    763             if (LLVM_UNLIKELY(amount > mBitBlockWidth)) {
    764                 const auto blocks = ceil_udiv(amount, mBitBlockWidth); assert (blocks > 1);
    765                 type = ArrayType::get(mBitBlockType, nearest_pow2(blocks));
    766                 if (LLVM_UNLIKELY(ifDepth > 0)) {
    767                     Type * carryType = ArrayType::get(mBitBlockType, ceil_udiv(amount, std::pow(mBitBlockWidth, 2)));
    768                     type = StructType::get(carryType, type, nullptr);
    769                     hasLongAdvances = true;                   
     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);
    770787                }
    771                 mHasLongAdvance = true;
     788                mHasLongAdvance = true;               
    772789            }
    773790            state.push_back(type);
     
    790807        //if (ifDepth > 0 || (nonCarryCollapsingMode | isNestedWithinNonCarryCollapsingLoop)) {
    791808        if (dyn_cast_or_null<If>(scope->getBranch()) || nonCarryCollapsingMode || isNestedWithinNonCarryCollapsingLoop) {
    792             if (LLVM_LIKELY(state.size() > 1 || hasLongAdvances)) {
     809            if (LLVM_LIKELY(state.size() > 1)) {
    793810                summaryType = CarryData::ExplicitSummary;
    794811                // NOTE: summaries are stored differently depending whether we're entering an If or While branch. With an If branch, they
     
    835852, mLoopSelector(nullptr)
    836853, mNextLoopSelector(nullptr)
     854, mCarryPackPtr(nullptr)
    837855, mCarryScopes(0) {
    838856
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.h

    r5368 r5371  
    126126    bool                                            mHasLoop;
    127127    unsigned                                        mLoopDepth;
    128     llvm::Value *                                   mLoopSelector;
     128    llvm::Value *                                   mLoopSelector;   
    129129    llvm::Value *                                   mNextLoopSelector;
     130    llvm::Value *                                   mCarryPackPtr;
    130131    std::vector<llvm::PHINode *>                    mLoopIndicies;
    131132
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.cpp

    r5368 r5371  
    3535
    3636
    37 Phi * PabloBlock::createPhi(Type * type, String * name) {
    38     if (type == nullptr) {
    39         type = getParent()->getBuilder()->getStreamTy();
    40     }
    41     if (name == nullptr) {
    42         name = makeName("phi");
    43     }
    44     return insertAtInsertionPoint(new (mAllocator) Phi(type, 2, name, mAllocator));
     37Phi * PabloBlock::createPhi(Type * type) {
     38    return new (mAllocator) Phi(type, mAllocator);
    4539}
    4640
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r5368 r5371  
    275275    While * createWhile(PabloAST * condition, PabloBlock * body);
    276276
    277     Phi * createPhi(llvm::Type * type = nullptr) {
    278         return createPhi(type, nullptr);
    279     }
    280 
    281     Phi * createPhi(llvm::Type * type, const llvm::StringRef & prefix) {
    282         return createPhi(type, makeName(prefix));
    283     }
    284 
    285     Phi * createPhi(llvm::Type * type, String * name);
     277    Phi * createPhi(llvm::Type * type);
    286278
    287279    llvm::Type * getStreamSetTy(const unsigned NumElements = 1, const unsigned FieldWidth = 1) {
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r5368 r5371  
    6767        , Block
    6868        , Kernel
     69        , Phi
    6970        /** Statements **/
    7071        // Boolean operations
     
    9293        , If
    9394        , While
    94         // Internal types
    95         , Phi
    9695    };
    9796
     
    250249    : PabloAST(id, type, allocator)
    251250    , mOperands(0)
    252     , mOperand(allocator.allocate(mOperands))
     251    , mOperand(allocator.allocate(reserved))
    253252    , mNext(nullptr)
    254253    , mPrev(nullptr)
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r5370 r5371  
    549549            std::string tmp;
    550550            raw_string_ostream out(tmp);
    551             out << "PabloCompiler: statement ";
     551            out << "PabloCompiler: ";
    552552            stmt->print(out);
    553553            out << " was not recognized by the compiler";
     
    614614        std::string tmp;
    615615        raw_string_ostream out(tmp);
     616        out << "PabloCompiler: ";
    616617        expr->print(out);
    617618        out << " is not a valid Operator";
     
    622623        std::string tmp;
    623624        raw_string_ostream out(tmp);
    624         out << "Compilation error: ";
     625        out << "PabloCompiler: ";
    625626        expr->print(out);
    626627        out << " was used before definition!";
  • icGREP/icgrep-devel/icgrep/pablo/pablo_kernel.h

    r5347 r5371  
    1212#include <util/slab_allocator.h>
    1313#include <llvm/ADT/StringRef.h>
    14 #include <boost/container/flat_map.hpp>      // for mScalarOutputNameMap
     14#include <boost/container/flat_map.hpp>
    1515
    1616namespace IDISA { class IDISA_Builder; }
  • icGREP/icgrep-devel/icgrep/pablo/passes/ssapass.cpp

    r5368 r5371  
    66#include <pablo/ps_assign.h>
    77#include <pablo/pe_var.h>
     8#include <pablo/pe_phi.h>
     9#include <boost/container/flat_map.hpp>
     10#include <boost/container/flat_set.hpp>
     11#include <boost/graph/adjacency_list.hpp>
     12#include <llvm/ADT/SmallVector.h>
     13
     14#include <llvm/Support/raw_ostream.h>
     15#include <pablo/printer_pablos.h>
     16
     17using namespace llvm;
     18using namespace boost;
    819
    920namespace pablo {
    1021
    11 static void SSAPass::toSSAForm(PabloBlock * const block) {
    12 
    13 
    14 
    15 }
    16 
    17 }
     22template<typename K, typename V>
     23using FlatMap = boost::container::flat_map<K, V>;
     24
     25template<typename V>
     26using FlatSet = boost::container::flat_set<V>;
     27
     28using DefinitionMap = FlatMap<PabloAST *, PabloAST *>;
     29using PhiMap = FlatMap<std::pair<PabloAST *, PabloAST *>, Phi *>;
     30using ReachingGraph = adjacency_list<vecS, vecS, bidirectionalS, Statement *, DefinitionMap::value_type>;
     31using Vertex = ReachingGraph::vertex_descriptor;
     32using InEdge = graph_traits<ReachingGraph>::in_edge_iterator;
     33
     34/*
     35 * Y = Y_0
     36 * X = 0                          ...
     37 * While Y:                       While phi(Y_0, Y_i):
     38 *   ...                             X' = phi(0, X'')
     39 *   If Z:                           If Z:
     40 *      X = A                           ...
     41 *   A = Z                           X'' = phi(X', A)
     42 *   Y = Y_i
     43 */
     44
     45/** ------------------------------------------------------------------------------------------------------------- *
     46 * @brief buildReachingGraph
     47 ** ------------------------------------------------------------------------------------------------------------- */
     48Vertex buildReachingGraph(PabloBlock * const block, Vertex entryPoint, ReachingGraph & G, DefinitionMap & D) {
     49    for (Statement * stmt : *block) {
     50        if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     51            PabloAST * const var = cast<Assign>(stmt)->getVariable();
     52            PabloAST * value = cast<Assign>(stmt)->getValue();
     53            if (isa<Var>(value)) {
     54                auto f = D.find(value);
     55                assert (f != D.end());
     56                value = f->second;
     57            }
     58            D[var] = value;
     59        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     60            const auto branchPoint = add_vertex(stmt, G);
     61            const auto resumePoint = add_vertex(stmt->getNextNode(), G);
     62            for (auto p : D) {
     63                add_edge(entryPoint, branchPoint, p, G);
     64                add_edge(branchPoint, resumePoint, p, G);
     65            }
     66            const Vertex endPoint = buildReachingGraph(cast<Branch>(stmt)->getBody(), branchPoint, G, D);
     67            if (isa<While>(stmt)) {
     68                for (auto p : D) {
     69                    add_edge(endPoint, branchPoint, p, G);
     70                }
     71            }
     72            for (auto p : D) {
     73                add_edge(endPoint, resumePoint, p, G);
     74            }
     75            entryPoint = resumePoint;
     76        }
     77    }
     78    return entryPoint;
     79}
     80
     81/** ------------------------------------------------------------------------------------------------------------- *
     82 * @brief getVariable
     83 ** ------------------------------------------------------------------------------------------------------------- */
     84inline PabloAST * getVariable(InEdge e, const ReachingGraph & G) {
     85    return std::get<0>(G[*e]);
     86}
     87
     88/** ------------------------------------------------------------------------------------------------------------- *
     89 * @brief getDefinition
     90 ** ------------------------------------------------------------------------------------------------------------- */
     91PabloAST * getDefinition(InEdge e, const ReachingGraph & G, DefinitionMap & D) {
     92    PabloAST * def = std::get<1>(G[*e]);
     93    if (LLVM_UNLIKELY(isa<Var>(def))) {
     94        const auto f = D.find(def);
     95        if (f != D.end()) {
     96            def = f->second;
     97        }
     98    }
     99    return def;
     100}
     101
     102/** ------------------------------------------------------------------------------------------------------------- *
     103 * @brief generatePhiNodeDefinitions
     104 ** ------------------------------------------------------------------------------------------------------------- */
     105void generatePhiNodeDefinitions(const Vertex v, PabloBlock * const block, const ReachingGraph & G, DefinitionMap & D, PhiMap & P) {
     106    FlatSet<PabloAST *> S;
     107    InEdge ei, end;
     108    std::vector<bool> processed(in_degree(v, G), false);
     109    unsigned i = 0;
     110    for (std::tie(ei, end) = in_edges(v, G); ei != end; ++ei, ++i) {
     111        if (processed[i]) {
     112            continue;
     113        }
     114        PabloAST * const var = getVariable(ei, G);
     115        S.insert(getDefinition(ei, G, D));
     116        unsigned j = i + 1;
     117        for (auto ej = ei + 1; ej != end; ++ej, ++j) {
     118            if (var == getVariable(ej, G)) {
     119                S.insert(getDefinition(ej, G, D));
     120            }
     121        }
     122        if (S.size() > 1) {
     123            assert (S.size() == 2);
     124            auto si = S.begin();
     125            auto def = std::make_pair(*si, *(si + 1));
     126            auto f = P.find(def);
     127            Phi * phi = nullptr;
     128            if (f == P.end()) {
     129                phi = block->createPhi(var->getType());
     130                for (PabloAST * incoming : S) {
     131                    phi->addIncomingValue(incoming);
     132                }
     133                P.emplace(def, phi);
     134            } else {
     135                phi = f->second;
     136            }
     137            D[var] = phi;
     138        }
     139        S.clear();
     140    }
     141}
     142
     143/** ------------------------------------------------------------------------------------------------------------- *
     144 * @brief generatePhiNodes
     145 ** ------------------------------------------------------------------------------------------------------------- */
     146Vertex generatePhiNodes(PabloBlock * const block, Vertex entryPoint, ReachingGraph & G, DefinitionMap & D, PhiMap & P) {
     147    for (Statement * stmt : *block) {
     148        if (LLVM_UNLIKELY(isa<Assign>(stmt))) {
     149            Assign * a = cast<Assign>(stmt);
     150            PabloAST * const var = a->getVariable();
     151            PabloAST * value = a->getValue();
     152            if (isa<Var>(value)) {
     153                auto f = D.find(value);
     154                assert (f != D.end());
     155                value = f->second;
     156                a->setValue(value);
     157            }
     158            D[var] = value;
     159        } else if (LLVM_UNLIKELY(isa<Extract>(stmt))) {
     160            continue;
     161        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     162            const auto branchPoint = entryPoint + 1;
     163            assert (G[branchPoint] == stmt);
     164            if (isa<While>(stmt)) {
     165                generatePhiNodeDefinitions(branchPoint, block, G, D, P);
     166            }
     167            Branch * br = cast<Branch>(stmt);
     168            if (isa<Var>(br->getCondition())) {
     169                auto f = D.find(br->getCondition());
     170                assert (f != D.end());
     171                br->setCondition(f->second);
     172            }
     173            const auto resumePoint = entryPoint + 2;
     174            assert (G[resumePoint] == stmt->getNextNode());
     175
     176            entryPoint = generatePhiNodes(cast<Branch>(stmt)->getBody(), resumePoint, G, D, P);
     177
     178            generatePhiNodeDefinitions(resumePoint, block, G, D, P);
     179
     180        } else {
     181            for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
     182                PabloAST * op = stmt->getOperand(i);
     183                if (isa<Var>(op)) {
     184                    auto f = D.find(op);
     185                    assert (f != D.end());
     186                    stmt->setOperand(i, f->second);
     187                }
     188            }
     189        }
     190    }
     191    return entryPoint;
     192}
     193
     194/** ------------------------------------------------------------------------------------------------------------- *
     195 * @brief toSSAForm
     196 ** ------------------------------------------------------------------------------------------------------------- */
     197inline void toSSAForm(PabloKernel * const kernel) {
     198    ReachingGraph G;
     199    DefinitionMap D;
     200    PabloBlock * entryBlock = kernel->getEntryBlock();
     201    const auto entryPoint = add_vertex(entryBlock->front(), G);
     202    buildReachingGraph(entryBlock, entryPoint, G, D);
     203    D.clear();
     204    PhiMap P;
     205    generatePhiNodes(entryBlock, entryPoint, G, D, P);
     206}
     207
     208/** ------------------------------------------------------------------------------------------------------------- *
     209 * @brief transform
     210 ** ------------------------------------------------------------------------------------------------------------- */
     211bool SSAPass::transform(PabloKernel * const kernel) {
     212    toSSAForm(kernel);
     213    return false;
     214}
     215
     216
     217}
  • icGREP/icgrep-devel/icgrep/pablo/passes/ssapass.h

    r5368 r5371  
    55
    66class PabloKernel;
    7 class PabloBlock;
    8 
    97
    108class SSAPass {
     
    1311protected:
    1412    SSAPass() = default;
    15 private:
    16     static void toSSAForm(PabloBlock * const block);
    1713};
    1814
     15}
     16
    1917#endif // SSAPASS_H
  • icGREP/icgrep-devel/icgrep/pablo/pe_phi.h

    r5368 r5371  
    33
    44#include <pablo/pabloAST.h>
    5 #include <pablo/pe_string.h>
    65
    76namespace pablo {
    87
    9 class Phi : public Variadic {
     8class Phi : public PabloAST {
    109    friend class PabloBlock;
    1110public:
     
    1817    virtual ~Phi(){
    1918    }
     19    void addIncomingValue(PabloAST * const value) {
     20        assert (getType() == value->getType());
     21        for (unsigned i = 0; i < getNumIncomingValues(); ++i) {
     22            if (LLVM_UNLIKELY(getIncomingValue(i) == value)) {
     23                return;
     24            }
     25        }
     26        assert (mNumIncomingValues < 2);
     27        mIncomingValue[mNumIncomingValues++] = value;
     28    }
    2029    PabloAST * getIncomingValue(const unsigned i) const {
    21         return getOperand(i);
     30        assert (i < mNumIncomingValues);
     31        return mIncomingValue[i];
     32    }
     33    unsigned getNumIncomingValues() const {
     34        return mNumIncomingValues;
    2235    }
    2336protected:
    24     Phi(llvm::Type * type, const unsigned NumReservedValues, const String * const name, Allocator & allocator)
    25     : Variadic(ClassTypeId::Phi, type, NumReservedValues, name, allocator) {
     37    Phi(llvm::Type * type, Allocator & allocator)
     38    : PabloAST(ClassTypeId::Phi, type, allocator)
     39    , mNumIncomingValues(0) {
    2640
    2741    }
     42private:
     43    unsigned   mNumIncomingValues;
     44    PabloAST * mIncomingValue[2];
    2845};
    2946
  • icGREP/icgrep-devel/icgrep/pablo/printer_pablos.cpp

    r5329 r5371  
    66
    77#include "printer_pablos.h"
     8#include <pablo/arithmetic.h>
     9#include <pablo/boolean.h>
     10#include <pablo/branch.h>
    811#include <pablo/codegenstate.h>
    9 #include <pablo/boolean.h>
    10 #include <pablo/arithmetic.h>
    11 #include <pablo/branch.h>
     12#include <pablo/pablo_kernel.h>
    1213#include <pablo/pe_advance.h>
     14#include <pablo/pe_count.h>
     15#include <pablo/pe_infile.h>
     16#include <pablo/pe_integer.h>
    1317#include <pablo/pe_lookahead.h>
    1418#include <pablo/pe_matchstar.h>
     19#include <pablo/pe_ones.h>
     20#include <pablo/pe_phi.h>
    1521#include <pablo/pe_scanthru.h>
    16 #include <pablo/pe_infile.h>
    17 #include <pablo/pe_count.h>
    18 #include <pablo/pe_integer.h>
    1922#include <pablo/pe_string.h>
     23#include <pablo/pe_var.h>
    2024#include <pablo/pe_zeroes.h>
    21 #include <pablo/pe_ones.h>
    22 #include <pablo/pe_var.h>
    2325#include <pablo/ps_assign.h>
    24 #include <pablo/pablo_kernel.h>
    2526#include <llvm/Support/raw_os_ostream.h>
    2627
     
    160161    } else if (const Var * var = dyn_cast<Var>(expr)) {
    161162        out << var->getName();
     163    } else if (const Phi * const phi = dyn_cast<Phi>(expr)) {
     164        out << "phi(";
     165        for (unsigned i = 0; i != phi->getNumIncomingValues(); ++i) {
     166            if (i) out << ", ";
     167            print(phi->getIncomingValue(i), out);
     168        }
     169        out << ")";
    162170    } else if (const If * ifstmt = dyn_cast<If>(expr)) {
    163171        out << "If ";
  • icGREP/icgrep-devel/icgrep/re/re_compiler.cpp

    r5357 r5371  
    433433    int total = repeat_count * length;
    434434    PabloAST * consecutive_i = repeated;
    435     while (i * 2 < total) {
     435    while ((i * 2) < total) {
    436436        PabloAST * v = consecutive_i;
    437437        PabloAST * v2 =  pb.createAdvance(v, i);
     
    439439        consecutive_i = pb.createAnd(v, v2, "at" + std::to_string(i) + "of" + std::to_string(total));
    440440    }
    441     if (i < total) {
     441    if (LLVM_LIKELY(i < total)) {
    442442        PabloAST * v = consecutive_i;
    443443        consecutive_i = pb.createAnd(v, pb.createAdvance(v, total - i), "at" + std::to_string(total));
     
    453453    }
    454454    PabloAST * reachable_i = pb.createOr(repeated, pb.createAdvance(repeated, 1), "within1");
    455     while (i * 2 < total_lgth) {
     455    while ((i * 2) < total_lgth) {
    456456        PabloAST * v = reachable_i;
    457457        PabloAST * v2 =  pb.createAdvance(v, i);
     
    459459        reachable_i = pb.createOr(v, v2, "within" + std::to_string(i));
    460460    }
    461     if (i < total_lgth) {
     461    if (LLVM_LIKELY(i < total_lgth)) {
    462462        PabloAST * v = reachable_i;
    463463        reachable_i = pb.createOr(v, pb.createAdvance(v, total_lgth - i), "within" + std::to_string(total_lgth));
     
    467467
    468468MarkerType RE_Compiler::processLowerBound(RE * repeated, int lb, MarkerType marker, PabloBuilder & pb) {
    469     if (lb == 0) return marker;
    470     if (!mGraphemeBoundaryRule && isByteLength(repeated) && !AlgorithmOptionIsSet(DisableLog2BoundedRepetition)) {
     469    if (lb == 0) {
     470        return marker;
     471    } else if (!mGraphemeBoundaryRule && isByteLength(repeated) && !AlgorithmOptionIsSet(DisableLog2BoundedRepetition)) {
    471472        PabloAST * cc = markerVar(compile(repeated, pb));
    472473        PabloAST * cc_lb = consecutive_matches(cc, 1, lb, pb);
     
    479480        marker = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
    480481    }
    481     if (lb == 1) return marker;
     482    if (lb == 1) {
     483        return marker;
     484    }
    482485    Var * m = pb.createVar("m", pb.createZeroes());
    483486    PabloBuilder nested = PabloBuilder::Create(pb);
     
    489492   
    490493MarkerType RE_Compiler::processBoundedRep(RE * repeated, int ub, MarkerType marker, PabloBuilder & pb) {
    491     if (ub == 0) return marker;
    492     if (!mGraphemeBoundaryRule && isByteLength(repeated) && ub > 1 && !AlgorithmOptionIsSet(DisableLog2BoundedRepetition)) {
     494    if (ub == 0) {
     495        return marker;
     496    } else if (!mGraphemeBoundaryRule && isByteLength(repeated) && ub > 1 && !AlgorithmOptionIsSet(DisableLog2BoundedRepetition)) {
    493497        // log2 upper bound for fixed length (=1) class
    494498        // Create a mask of positions reachable within ub from current marker.
     
    508512        marker = AdvanceMarker(marker, MarkerPosition::FinalPostPositionUnit, pb);
    509513    }
    510     if (ub == 1) return marker;
     514    if (ub == 1) {
     515        return marker;
     516    }
    511517    Var * m1a = pb.createVar("m", pb.createZeroes());
    512518    PabloBuilder nested = PabloBuilder::Create(pb);
  • icGREP/icgrep-devel/icgrep/toolchain.cpp

    r5364 r5371  
    171171
    172172ExecutionEngine * JIT_to_ExecutionEngine (Module * m) {
    173 
    174173    // Use the pass manager to optimize the function.
    175174    legacy::PassManager PM;
Note: See TracChangeset for help on using the changeset viewer.