source: icGREP/icgrep-devel/icgrep/kernels/scanmatchgen.cpp @ 5805

Last change on this file since 5805 was 5782, checked in by nmedfort, 17 months ago

Initial check-in of LookAhead? support; modified LineBreakKernel? to compute CR+LF using LookAhead?(1) + misc. fixes.

File size: 13.3 KB
RevLine 
[4907]1/*
2 *  Copyright (c) 2015 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 */
5
6#include "scanmatchgen.h"
7#include <llvm/IR/Intrinsics.h>
[5260]8#include <llvm/IR/Module.h>
[5436]9#include <kernels/kernel_builder.h>
[5676]10#include <IR_Gen/FunctionTypeBuilder.h>
11#include <llvm/Support/raw_ostream.h>
[5678]12#include <grep_engine.h>
[4907]13
[4959]14using namespace llvm;
15
[5398]16inline static unsigned floor_log2(const unsigned v) {
17    assert ("log2(0) is undefined!" && v != 0);
18    return 31 - __builtin_clz(v);
[4907]19}
20
[5398]21namespace kernel {
[4907]22
[5755]23Value * ScanMatchKernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> &iBuilder, Value * const numOfStrides) {
[4959]24
[5377]25    Module * const m = iBuilder->getModule();
[5676]26   
[5377]27    BasicBlock * const entryBlock = iBuilder->GetInsertBlock();
[5526]28    BasicBlock * const initialBlock = iBuilder->CreateBasicBlock("initialBlock");
[5440]29    BasicBlock * const scanWordIteration = iBuilder->CreateBasicBlock("ScanWordIteration");
30    BasicBlock * const matches_test_block = iBuilder->CreateBasicBlock("matches_test_block");
31    BasicBlock * const processMatchesEntry = iBuilder->CreateBasicBlock("process_matches_loop");
32    BasicBlock * const prior_breaks_block = iBuilder->CreateBasicBlock("prior_breaks_block");
33    BasicBlock * const loop_final_block = iBuilder->CreateBasicBlock("loop_final_block");
34    BasicBlock * const processMatchesExit = iBuilder->CreateBasicBlock("matches_done_block");
35    BasicBlock * const remaining_breaks_block = iBuilder->CreateBasicBlock("remaining_breaks_block");
36    BasicBlock * const return_block = iBuilder->CreateBasicBlock("return_block");
37    BasicBlock * const scanWordExit = iBuilder->CreateBasicBlock("ScanWordExit");
[5526]38    BasicBlock * const blocksExit = iBuilder->CreateBasicBlock("blocksExit");
[5694]39    BasicBlock * const callFinalizeScan = iBuilder->CreateBasicBlock("callFinalizeScan");
40    BasicBlock * const scanReturn = iBuilder->CreateBasicBlock("scanReturn");
[5377]41    IntegerType * const sizeTy = iBuilder->getSizeTy();
42    const unsigned fieldCount = iBuilder->getBitBlockWidth() / sizeTy->getBitWidth();
43    VectorType * const scanwordVectorType =  VectorType::get(sizeTy, fieldCount);
[5757]44    Constant * const ZERO = ConstantInt::getNullValue(sizeTy);
[5526]45
[5706]46    Value * match_result = iBuilder->getInputStreamBlockPtr("matchResult", iBuilder->getInt32(0));
47    Value * line_break = iBuilder->getInputStreamBlockPtr("lineBreak", iBuilder->getInt32(0));
[5526]48
[5706]49    Value * blocksToDo = iBuilder->CreateAdd(numOfStrides, iBuilder->CreateZExt(mIsFinal, numOfStrides->getType()));
50    blocksToDo = iBuilder->CreateMul(blocksToDo, iBuilder->getSize(mStride / iBuilder->getBitBlockWidth()));
[5526]51   
52    Value * match_result_ptr = iBuilder->CreateBitCast(match_result, scanwordVectorType->getPointerTo());
53    Value * line_break_ptr = iBuilder->CreateBitCast(line_break, scanwordVectorType->getPointerTo());
[5695]54    Value * accumulator = iBuilder->getScalarField("accumulator_address");
[5526]55
56    iBuilder->CreateCondBr(iBuilder->CreateICmpUGT(blocksToDo, iBuilder->getSize(0)), initialBlock, blocksExit);
57
58    iBuilder->SetInsertPoint(initialBlock);
59    PHINode * const blockBase = iBuilder->CreatePHI(iBuilder->getSizeTy(), 2);
60    blockBase->addIncoming(iBuilder->getSize(0), entryBlock);
[5440]61    Value * const blockNo = iBuilder->getScalarField("BlockNo");
[5398]62    Value * const scanwordPos = iBuilder->CreateShl(blockNo, floor_log2(iBuilder->getBitBlockWidth()));
[5440]63    Value * const lastRecordStart = iBuilder->getProcessedItemCount("InputStream");
64    Value * const lastRecordNum = iBuilder->getScalarField("LineNum");
[5377]65    iBuilder->CreateBr(scanWordIteration);
66
67    iBuilder->SetInsertPoint(scanWordIteration);
68
69        // while (phiIndex < words per stride)
70        PHINode * const phiIndex = iBuilder->CreatePHI(iBuilder->getInt32Ty(), 2, "index");
[5526]71        phiIndex->addIncoming(iBuilder->getInt32(0), initialBlock);
[5377]72        PHINode * const phiScanwordPos = iBuilder->CreatePHI(scanwordPos->getType(), 2, "pos");
[5526]73        phiScanwordPos->addIncoming(scanwordPos, initialBlock);
[5377]74        PHINode * const phiLineStart = iBuilder->CreatePHI(lastRecordStart->getType(), 2, "recordstart");
[5526]75        phiLineStart->addIncoming(lastRecordStart, initialBlock);
[5377]76        PHINode * const phiLineNum = iBuilder->CreatePHI(lastRecordNum->getType(), 2, "recordnum");
[5526]77        phiLineNum->addIncoming(lastRecordNum, initialBlock);
78        Value * const matches = iBuilder->CreateLoad(iBuilder->CreateGEP(match_result_ptr, blockBase));
79        Value * const linebreaks = iBuilder->CreateLoad(iBuilder->CreateGEP(line_break_ptr, blockBase));
[5377]80        Value * const matchWord = iBuilder->CreateExtractElement(matches, phiIndex);
81        Value * const recordBreaks = iBuilder->CreateExtractElement(linebreaks, phiIndex);
82
83        // The match scanner works with a loop involving four variables:
84        // (a) the bit stream scanword of matches marking the ends of selected records,
85        // (b) the bit stream scanword of record_breaks marking the ends of all records,
86        // (c) the integer lastRecordNum indicating the number of records processed so far,
87        // (d) the index lastRecordStart indicating the file position of the last record.
88        // We set up a loop structure, in which a set of 4 phi nodes initialize these
89        // variables from either the input to the scanner or the computed values within
90        // the loop body.
91
92        iBuilder->CreateBr(matches_test_block);
93
94        // LOOP Test Block
95        iBuilder->SetInsertPoint(matches_test_block);
96        PHINode * phiMatchWord = iBuilder->CreatePHI(sizeTy, 2, "matches");
97        PHINode * phiRecordBreaks = iBuilder->CreatePHI(sizeTy, 2, "recordbreaks");
98        PHINode * phiRecordStart = iBuilder->CreatePHI(sizeTy, 2, "recordstart");
99        PHINode * phiRecordNum = iBuilder->CreatePHI(sizeTy, 2, "recordnum");
100        phiMatchWord->addIncoming(matchWord, scanWordIteration);
101        phiRecordBreaks->addIncoming(recordBreaks, scanWordIteration);
102        phiRecordNum->addIncoming(phiLineNum, scanWordIteration);
103        phiRecordStart->addIncoming(phiLineStart, scanWordIteration);
[5757]104        Value * anyMatches = iBuilder->CreateICmpNE(phiMatchWord, ZERO);
[5377]105        iBuilder->CreateCondBr(anyMatches, processMatchesEntry, processMatchesExit);
106
107            // LOOP BODY
108            // The loop body is entered if we have more matches to process.
109            iBuilder->SetInsertPoint(processMatchesEntry);
[5427]110            Value * prior_breaks = iBuilder->CreateAnd(iBuilder->CreateMaskToLowestBitExclusive(phiMatchWord), phiRecordBreaks);
[5377]111            // Within the loop we have a conditional block that is executed if there are any prior record breaks.
[5757]112            Value * prior_breaks_cond = iBuilder->CreateICmpNE(prior_breaks, ZERO);
[5377]113            iBuilder->CreateCondBr(prior_breaks_cond, prior_breaks_block, loop_final_block);
114
115                // PRIOR_BREAKS_BLOCK
116                // If there are prior breaks, we count them and compute the record start position.
[5440]117                iBuilder->SetInsertPoint(prior_breaks_block);
[5398]118                Value * matchedRecordNum = iBuilder->CreateAdd(iBuilder->CreatePopcount(prior_breaks), phiRecordNum);
[5757]119                Value * reverseDistance = iBuilder->CreateCountReverseZeroes(prior_breaks, true);
[5377]120                Value * width = ConstantInt::get(sizeTy, sizeTy->getBitWidth());
[5757]121                Value * priorRecordStart = iBuilder->CreateAdd(phiScanwordPos, iBuilder->CreateSub(width, reverseDistance));               
[5377]122                iBuilder->CreateBr(loop_final_block);
123
124            // LOOP FINAL BLOCK
125            // The prior breaks, if any have been counted.  Set up phi nodes for the recordNum
126            // and recortStart depending on whether the conditional execution of prior_breaks_block.
127            iBuilder->SetInsertPoint(loop_final_block);
128            PHINode * matchRecordNum = iBuilder->CreatePHI(sizeTy, 2, "matchRecordNum");
129            matchRecordNum->addIncoming(phiRecordNum, processMatchesEntry);
130            matchRecordNum->addIncoming(matchedRecordNum, prior_breaks_block);
131            phiRecordNum->addIncoming(matchRecordNum, loop_final_block);
132
[5757]133            PHINode * const matchRecordStart = iBuilder->CreatePHI(sizeTy, 2, "matchRecordStart");
[5377]134            matchRecordStart->addIncoming(phiRecordStart, processMatchesEntry);
135            matchRecordStart->addIncoming(priorRecordStart, prior_breaks_block);
136            phiRecordStart->addIncoming(matchRecordStart, loop_final_block);
[5758]137            Value * matchRecordEnd = iBuilder->CreateAdd(phiScanwordPos, iBuilder->CreateCountForwardZeroes(phiMatchWord, true));
138            // It is possible that the matchRecordEnd position is one past EOF.  Make sure not
139            // to access past EOF.
140            Value * bufLimit = iBuilder->CreateSub(iBuilder->getBufferedSize("InputStream"), ConstantInt::get(sizeTy, 1));
141            matchRecordEnd = iBuilder->CreateSelect(iBuilder->CreateICmpULT(matchRecordEnd, bufLimit), matchRecordEnd, bufLimit);
[5757]142            Function * const dispatcher = m->getFunction("accumulate_match_wrapper"); assert (dispatcher);
143            Value * const startPtr = iBuilder->getRawInputPointer("InputStream", matchRecordStart);
144            Value * const endPtr = iBuilder->getRawInputPointer("InputStream", matchRecordEnd);
145            iBuilder->CreateCall(dispatcher, {accumulator, matchRecordNum, startPtr, endPtr});
[5427]146            Value * remaining_matches = iBuilder->CreateResetLowestBit(phiMatchWord);
[5377]147            phiMatchWord->addIncoming(remaining_matches, loop_final_block);
148
149            Value * remaining_breaks = iBuilder->CreateXor(phiRecordBreaks, prior_breaks);
150            phiRecordBreaks->addIncoming(remaining_breaks, loop_final_block);
151
152            iBuilder->CreateBr(matches_test_block);
153
154        // LOOP EXIT/MATCHES_DONE
155        iBuilder->SetInsertPoint(processMatchesExit);
156        // When the matches are done, there may be additional record breaks remaining
[5757]157        Value * more_breaks_cond = iBuilder->CreateICmpNE(phiRecordBreaks, ZERO);
[5377]158        iBuilder->CreateCondBr(more_breaks_cond, remaining_breaks_block, return_block);
159
160            // REMAINING_BREAKS_BLOCK: process remaining record breaks after all matches are processed
161            iBuilder->SetInsertPoint(remaining_breaks_block);
[5398]162            Value * break_count = iBuilder->CreatePopcount(phiRecordBreaks);
[5377]163            Value * final_record_num = iBuilder->CreateAdd(phiRecordNum, break_count);
[5398]164            Value * reverseZeroes = iBuilder->CreateCountReverseZeroes(phiRecordBreaks);
[5377]165            Value * pendingLineStart = iBuilder->CreateAdd(phiScanwordPos, iBuilder->CreateSub(width, reverseZeroes));
166            iBuilder->CreateBr(return_block);
167
168        // RETURN block
169        iBuilder->SetInsertPoint(return_block);
170        PHINode * phiFinalRecordNum = iBuilder->CreatePHI(sizeTy, 2, "finalRecordCount");
171        PHINode * phiFinalRecordStart = iBuilder->CreatePHI(sizeTy, 2, "finalRecordStart");
172
173        phiFinalRecordNum->addIncoming(phiRecordNum, processMatchesExit);
174        phiFinalRecordNum->addIncoming(final_record_num, remaining_breaks_block);
175        phiLineNum->addIncoming(phiFinalRecordNum, return_block);
176
177        phiFinalRecordStart->addIncoming(phiRecordStart, processMatchesExit);
178        phiFinalRecordStart->addIncoming(pendingLineStart, remaining_breaks_block);
179        phiLineStart->addIncoming(phiFinalRecordStart, return_block);
180
181        Value * nextScanwordPos = iBuilder->CreateAdd(phiScanwordPos, ConstantInt::get(sizeTy, sizeTy->getBitWidth()));
182        phiScanwordPos->addIncoming(nextScanwordPos, return_block);
183        Value * nextIndex = iBuilder->CreateAdd(phiIndex, iBuilder->getInt32(1));
184        phiIndex->addIncoming(nextIndex, return_block);
185        iBuilder->CreateLikelyCondBr(iBuilder->CreateICmpNE(nextIndex, iBuilder->getInt32(fieldCount)), scanWordIteration, scanWordExit);
186
187    iBuilder->SetInsertPoint(scanWordExit);
[5440]188    iBuilder->setScalarField("BlockNo", iBuilder->CreateAdd(blockNo, ConstantInt::get(blockNo->getType(), 1)));
189    iBuilder->setScalarField("LineNum", phiFinalRecordNum);
190    iBuilder->setProcessedItemCount("InputStream", phiFinalRecordStart);
[5526]191    Value * blockBaseNext = iBuilder->CreateAdd(blockBase, ConstantInt::get(iBuilder->getSizeTy(), 1));
192    blockBase->addIncoming(blockBaseNext, scanWordExit);
193    iBuilder->CreateLikelyCondBr(iBuilder->CreateICmpNE(blockBaseNext, blocksToDo), initialBlock, blocksExit);
194
195    iBuilder->SetInsertPoint(blocksExit);
[5706]196    iBuilder->CreateCondBr(mIsFinal, callFinalizeScan, scanReturn);
197
[5694]198    iBuilder->SetInsertPoint(callFinalizeScan);
[5695]199    Value * bufSize = iBuilder->getBufferedSize("InputStream");
200    Function * finalizer = m->getFunction("finalize_match_wrapper"); assert (finalizer);
[5706]201    Value * const buffer_base = iBuilder->getRawInputPointer("InputStream", iBuilder->getInt32(0));
[5695]202    Value * buffer_end_address = iBuilder->CreateGEP(buffer_base, bufSize);
203    iBuilder->CreateCall(finalizer, {accumulator, buffer_end_address});
[5694]204    iBuilder->CreateBr(scanReturn);
[5706]205
[5694]206    iBuilder->SetInsertPoint(scanReturn);
[5755]207    return numOfStrides;
[5055]208}
209
[5695]210ScanMatchKernel::ScanMatchKernel(const std::unique_ptr<kernel::KernelBuilder> & b)
211: MultiBlockKernel("scanMatch",
[5782]212// inputs
213{Binding{b->getStreamSetTy(1, 1), "matchResult", FixedRate(), Principal()}
214,Binding{b->getStreamSetTy(1, 1), "lineBreak"}
215,Binding{b->getStreamSetTy(1, 8), "InputStream", FixedRate(), Deferred()}},
216// outputs
217{},
218// input scalars
219{Binding{b->getIntAddrTy(), "accumulator_address"}},
220// output scalars
221{},
222// kernel state
223{Binding{b->getSizeTy(), "BlockNo"}
224,Binding{b->getSizeTy(), "LineNum"}}) {
225
[5055]226}
[5782]227
228}
Note: See TracBrowser for help on using the repository browser.