Changeset 4595 for icGREP


Ignore:
Timestamp:
Jun 5, 2015, 8:40:28 AM (4 years ago)
Author:
cameron
Message:

Restructure compilation of while statements.

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

Legend:

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

    r4566 r4595  
    4545    }
    4646    unsigned localCarryDataIndex = localCarries + unitAdvances + shortAdvances + longAdvanceTotalBlocks;
     47    localCarryDataSize = localCarryDataIndex;
    4748    /*
    4849    totalCarryDataSize = longAdvanceTotalBlocks * BLOCK_SIZE;
  • icGREP/icgrep-devel/icgrep/pablo/carry_data.h

    r4568 r4595  
    4040                           longAdvances(0), longAdvanceTotalBlocks(0),
    4141                           nestedBlockCount(0), nestedCarryDataSize(0),
    42                            totalCarryDataSize(0),
     42                           localCarryDataSize(0), totalCarryDataSize(0),
    4343                           carryOffset(0), unitAdvanceOffset(0),
    4444                           shortAdvanceOffset(0), longAdvanceOffset(0)
     
    100100    }
    101101   
     102    unsigned getLocalCarryDataSize()  const {
     103        return localCarryDataSize;
     104    }
     105   
    102106    unsigned getTotalCarryDataSize()  const {
    103107        return totalCarryDataSize;
     
    116120    unsigned nestedBlockCount;
    117121    unsigned nestedCarryDataSize;
     122    unsigned localCarryDataSize;
    118123    unsigned totalCarryDataSize;
    119124    unsigned carryOffset;
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r4593 r4595  
    499499            PHINode * phi = bEnd.CreatePHI(mBitBlockType, 2, assign->getName()->value());
    500500            auto f = mMarkerMap.find(assign);
    501             if (LLVM_UNLIKELY(f == mMarkerMap.end())) {
    502                 throw std::runtime_error("Fatal error during compileIf: could not find \"" + assign->getName()->to_string() + "\" in the marker map.");
    503             }
     501            assert (f != mMarkerMap.end());
    504502            phi->addIncoming(mZeroInitializer, ifEntryBlock);
    505503            phi->addIncoming(f->second, mBasicBlock);
     
    518516}
    519517
     518// If the following preload is turned off, we have incorrect results with the
     519// ./icgrep -c '[A-Z]((([a-zA-Z]*a[a-zA-Z]*[ ])*[a-zA-Z]*e[a-zA-Z]*[ ])*[a-zA-Z]*s[a-zA-Z]*[ ])*[.?!]' ../performance/data/howto
     520   
     521#define PRELOAD_WHILE_CARRIES_AT_TOP_LEVEL 1
     522//#define SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
     523
    520524void PabloCompiler::compileWhile(const While * whileStatement) {
     525        BasicBlock* whileEntryBlock = mBasicBlock;
     526        BasicBlock* whileBodyBlock = BasicBlock::Create(mMod->getContext(), "while.body", mFunction, 0);
     527        BasicBlock* whileEndBlock = BasicBlock::Create(mMod->getContext(), "while.end", mFunction, 0);
     528   
     529   
    521530        const PabloBlockCarryData & cd = whileStatement -> getBody().carryData;
    522531        const unsigned baseCarryDataIdx = cd.getBlockCarryDataIndex();
     532
     533#ifdef PRELOAD_WHILE_CARRIES_AT_TOP_LEVEL
    523534        const unsigned carryDataSize = cd.getTotalCarryDataSize();
    524    
    525         if (mWhileDepth == 0) {
    526             for (auto i = 0; i < carryDataSize; ++i) {
    527                 genCarryDataLoad(baseCarryDataIdx + i);
     535        if (mWhileDepth == 0)
     536#else
     537        const unsigned carryDataSize = cd.getLocalCarryDataSize();
     538#endif
     539        {
     540            for (auto i = baseCarryDataIdx; i < baseCarryDataIdx + carryDataSize; ++i) {
     541                IRBuilder<> b(mBasicBlock);
     542                mCarryInVector[i] = b.CreateAlignedLoad(b.CreateGEP(mCarryDataPtr, b.getInt64(i)), BLOCK_SIZE/8, false);
    528543            }
    529544        }
    530 
    531545        SmallVector<const Next*, 4> nextNodes;
    532546        SmallVector<PHINode *, 4> nextPhis;
     
    536550            }
    537551        }
    538 
    539         // Compile the initial iteration statements; the calls to genCarryDataStore will update the
    540         // mCarryOutVector with the appropriate values. Although we're not actually entering a new basic
    541         // block yet, increment the nesting depth so that any calls to genCarryDataLoad or genCarryDataStore
    542         // will refer to the previous value.
    543 
    544         ++mWhileDepth;
    545 
    546         compileBlock(whileStatement->getBody());
    547         // Reset the carry queue index. Note: this ought to be changed in the future. Currently this assumes
    548         // that compiling the while body twice will generate the equivalent IR. This is not necessarily true
    549         // but works for now.
    550 
    551         BasicBlock* whileCondBlock = BasicBlock::Create(mMod->getContext(), "while.cond", mFunction, 0);
    552         BasicBlock* whileBodyBlock = BasicBlock::Create(mMod->getContext(), "while.body", mFunction, 0);
    553         BasicBlock* whileEndBlock = BasicBlock::Create(mMod->getContext(), "while.end", mFunction, 0);
    554 
    555         // Note: compileBlock may update the mBasicBlock pointer if the body contains nested loops. It
    556         // may not be same one that we entered the function with.
     552   
     553        // On entry to the while structure, proceed to execute the first iteration
     554        // of the loop body unconditionally.   The while condition is tested at the end of
     555        // the loop.
     556
    557557        IRBuilder<> bEntry(mBasicBlock);
    558 #ifdef WHILE_MULTI_CARRY
    559         Value * secondCarryFramePtr = bEntry.CreateGEP(mCarryFramePtr, bEntry.getInt64(WHILEBODYCARRYTOTALSIZE));
    560         mCarryFramePtr = secondCarryFramePtr;
    561 #endif       
    562 
    563         bEntry.CreateBr(whileCondBlock);
    564 
    565         // CONDITION BLOCK
    566         IRBuilder<> bCond(whileCondBlock);
    567         // generate phi nodes for any carry propogating instruction
    568         std::vector<PHINode*> phiNodes(carryDataSize);
    569         unsigned index = 0;
    570         for (index = 0; index < carryDataSize; ++index) {
    571             PHINode * phi = bCond.CreatePHI(mBitBlockType, 2);
    572             phi->addIncoming(mCarryOutVector[baseCarryDataIdx + index], mBasicBlock);
    573             mCarryInVector[baseCarryDataIdx + index] = mZeroInitializer; // (use phi for multi-carry mode.)
    574             phiNodes[index] = phi;
    575         }
    576         // and for any Next nodes in the loop body
     558        // Jump to the while body block immediately.
     559        bEntry.CreateBr(whileBodyBlock);
     560        mBasicBlock = whileBodyBlock;
     561        IRBuilder<> bBody(whileBodyBlock);
     562   
     563        //
     564        // There are 3 sets of Phi nodes for the while loop.
     565        // (1) Carry-ins: (a) incoming carry data first iterations, (b) zero thereafter
     566        // (2) Carry-out accumulators: (a) zero first iteration, (b) |= carry-out of each iteration
     567        // (3) Next nodes: (a) values set up before loop, (b) modified values calculated in loop.
     568
     569#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
     570        std::vector<PHINode *> carryInPhis(carryDataSize);
     571#endif
     572        std::vector<PHINode *> carryOutAccumPhis(carryDataSize);
     573   
     574        // Set initial values of phi nodes for loop body using values at while entry.
     575        for (unsigned index = 0; index < carryDataSize; ++index) {
     576#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
     577            PHINode * phi_in = bBody.CreatePHI(mBitBlockType, 2);
     578            phi_in->addIncoming(mCarryInVector[baseCarryDataIdx + index], whileEntryBlock);
     579            carryInPhis[index] = phi_in;
     580            mCarryInVector[baseCarryDataIdx + index] = phi_in;
     581#endif
     582            PHINode * phi_out = bBody.CreatePHI(mBitBlockType, 2);
     583            phi_out->addIncoming(mZeroInitializer, whileEntryBlock);
     584            carryOutAccumPhis[index] = phi_out;
     585            mCarryOutVector[baseCarryDataIdx + index] = mZeroInitializer;
     586        }
     587   
     588        // for any Next nodes in the loop body, initialize to (a) pre-loop value.
    577589        for (const Next * n : nextNodes) {
    578             PHINode * phi = bCond.CreatePHI(mBitBlockType, 2, n->getName()->value());
     590            PHINode * phi = bBody.CreatePHI(mBitBlockType, 2, n->getName()->value());
    579591            auto f = mMarkerMap.find(n->getInitial());
    580592            assert (f != mMarkerMap.end());
    581             phi->addIncoming(f->second, mBasicBlock);
     593            phi->addIncoming(f->second, whileEntryBlock);
    582594            mMarkerMap[n->getInitial()] = phi;
    583595            nextPhis.push_back(phi);
    584596        }
    585 #ifdef WHILE_MULTI_CARRY
    586         //  CarryFramePtr
    587         PHINode * carryFramePtrPhi = bCond.CreatePHI(mBitBlockType, 2, "CarryFramePtr");
    588         carryFramePtrPhi->addIncoming(mCarryFramePtr, mBasicBlock);
    589         mCarryFramePtr = carryFramePtrPhi;
    590 #endif       
    591         mBasicBlock = whileCondBlock;
    592         bCond.CreateCondBr(genBitBlockAny(compileExpression(whileStatement->getCondition())), whileEndBlock, whileBodyBlock);
    593 
    594         // BODY BLOCK
    595         //std::cerr << "Compile loop body\n";
    596         mBasicBlock = whileBodyBlock;
     597
     598        //
     599        // Now compile the loop body proper.  Carry-out accumulated values
     600        // and iterated values of Next nodes will be computed.
     601        ++mWhileDepth;
    597602        compileBlock(whileStatement->getBody());
    598        
    599         // update phi nodes for any carry propogating instruction
    600         IRBuilder<> bWhileBody(mBasicBlock);
    601         for (index = 0; index < carryDataSize; ++index) {
    602             PHINode * phi = phiNodes[index];
    603             Value * carryOut = bWhileBody.CreateOr(phi, mCarryOutVector[baseCarryDataIdx + index]);
    604             phi->addIncoming(carryOut, mBasicBlock);
    605             mCarryOutVector[baseCarryDataIdx + index] = phi;
    606         }
    607        
     603   
     604        //  The while body might involve separate blocks depending on compile;
     605        //  identify the final block generated.
     606        BasicBlock * whileBodyFinalBlock = mBasicBlock;
     607        IRBuilder<> bBodyFinal(mBasicBlock);
     608   
     609        // Add the phiNode branches for carry in, carry out nodes.
     610        for (unsigned index = 0; index < carryDataSize; ++index) {
     611#ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
     612            carryInPhis[index]->addIncoming(mZeroInitializer, whileBodyFinalBlock);
     613#endif
     614            PHINode * phi = carryOutAccumPhis[index];
     615            Value * carryOut = bBodyFinal.CreateOr(phi, mCarryOutVector[baseCarryDataIdx + index]);
     616            phi->addIncoming(carryOut, whileBodyFinalBlock);
     617            mCarryOutVector[baseCarryDataIdx + index] = carryOut;
     618        }
     619
     620        // Terminate the while loop body with a conditional branch back.
     621        bBodyFinal.CreateCondBr(genBitBlockAny(compileExpression(whileStatement->getCondition())), whileEndBlock, whileBodyBlock);
     622
    608623        // and for any Next nodes in the loop body
    609         for (int i = 0; i < nextNodes.size(); i++) {
     624        for (unsigned i = 0; i < nextNodes.size(); i++) {
    610625            const Next * n = nextNodes[i];
    611626            auto f = mMarkerMap.find(n->getInitial());
    612627            assert (f != mMarkerMap.end());
    613628            PHINode * phi = nextPhis[i];
    614             phi->addIncoming(f->second, mBasicBlock);
    615             mMarkerMap[n->getInitial()] = phi;
    616         }
    617 #ifdef WHILE_MULTI_CARRY
    618         Value * nextCarryFramePtr = bWhileBody.CreateGEP(mCarryFramePtr, bWhileBody.getInt64(WHILEBODYCARRYTOTALSIZE));
    619         carryFramePtrPhi->addIncoming(nextCarryFramePtr, mBasicBlock);
    620 #endif       
    621         bWhileBody.CreateBr(whileCondBlock);
     629            if (LLVM_UNLIKELY(f->second == phi)) {
     630                throw std::runtime_error("Unexpected Phi node for Next node.");
     631            }
     632            phi->addIncoming(f->second, whileBodyFinalBlock);
     633            //mMarkerMap[n->getInitial()] = f->second;
     634        }
    622635
    623636        // EXIT BLOCK
    624637        mBasicBlock = whileEndBlock;
    625         if (--mWhileDepth == 0) {
    626             for (index = 0; index < carryDataSize; ++index) {
    627                 genCarryDataStore(phiNodes[index], baseCarryDataIdx + index);
     638        IRBuilder<> bEnd(whileEndBlock);
     639        --mWhileDepth;
     640
     641#ifdef PRELOAD_WHILE_CARRIES_AT_TOP_LEVEL
     642        if (mWhileDepth == 0)
     643#endif
     644        {
     645            for (unsigned index = baseCarryDataIdx; index < baseCarryDataIdx + carryDataSize; ++index) {
     646                bEnd.CreateAlignedStore(mCarryOutVector[index], bEnd.CreateGEP(mCarryDataPtr, bEnd.getInt64(index)), BLOCK_SIZE/8, false);
    628647            }
    629648        }
    630  
    631649}
    632650
     
    10031021}
    10041022                   
    1005                     //
     1023//
    10061024// Generate code for long advances >= LongAdvanceBase
    10071025//
     
    10121030    const unsigned advanceEntries = cd.longAdvanceEntries(shift_amount);
    10131031    const unsigned bufsize = cd.longAdvanceBufferSize(shift_amount);
    1014 
     1032    //std::cerr << "shift_amount = " << shift_amount << " bufsize = " << bufsize << std::endl;
    10151033    Value * indexMask = b.getInt64(bufsize - 1);  // A mask to implement circular buffer indexing
    10161034    Value * advBaseIndex = b.getInt64(cd.longAdvanceCarryDataOffset(localIndex));
Note: See TracChangeset for help on using the changeset viewer.