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

Last change on this file since 5676 was 5676, checked in by cameron, 22 months ago

MatchAccumulator? objects to collect match results

File size: 14.2 KB
Line 
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>
8#include <llvm/IR/Module.h>
9#include <kernels/kernel_builder.h>
10#include <IR_Gen/FunctionTypeBuilder.h>
11#include <llvm/Support/raw_ostream.h>
12
13using namespace llvm;
14
15inline static unsigned floor_log2(const unsigned v) {
16    assert ("log2(0) is undefined!" && v != 0);
17    return 31 - __builtin_clz(v);
18}
19
20namespace kernel {
21
22inline std::string getGrepTypeId(const GrepType grepType) {
23    switch (grepType) {
24        case GrepType::Normal:
25            return "N";
26        case GrepType::NameExpression:
27            return "E";
28        case GrepType::PropertyValue:
29            return "P";
30        case GrepType::CallBack:
31            return "C";
32        default:
33            llvm_unreachable("unknown grep type!");
34    }
35}
36   
37void accumulate_match_wrapper(intptr_t accum_addr, const size_t lineNum, size_t line_start, size_t line_end) {
38    reinterpret_cast<MatchAccumulator *>(accum_addr)->accumulate_match(lineNum, line_start, line_end);
39}
40
41
42void ScanMatchKernel::generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> &iBuilder) {
43
44    Module * const m = iBuilder->getModule();
45   
46    BasicBlock * const entryBlock = iBuilder->GetInsertBlock();
47    BasicBlock * const initialBlock = iBuilder->CreateBasicBlock("initialBlock");
48    BasicBlock * const scanWordIteration = iBuilder->CreateBasicBlock("ScanWordIteration");
49    BasicBlock * const matches_test_block = iBuilder->CreateBasicBlock("matches_test_block");
50    BasicBlock * const processMatchesEntry = iBuilder->CreateBasicBlock("process_matches_loop");
51    BasicBlock * const prior_breaks_block = iBuilder->CreateBasicBlock("prior_breaks_block");
52    BasicBlock * const loop_final_block = iBuilder->CreateBasicBlock("loop_final_block");
53    BasicBlock * const processMatchesExit = iBuilder->CreateBasicBlock("matches_done_block");
54    BasicBlock * const remaining_breaks_block = iBuilder->CreateBasicBlock("remaining_breaks_block");
55    BasicBlock * const return_block = iBuilder->CreateBasicBlock("return_block");
56    BasicBlock * const scanWordExit = iBuilder->CreateBasicBlock("ScanWordExit");
57    BasicBlock * const blocksExit = iBuilder->CreateBasicBlock("blocksExit");
58    IntegerType * const sizeTy = iBuilder->getSizeTy();
59    const unsigned fieldCount = iBuilder->getBitBlockWidth() / sizeTy->getBitWidth();
60    VectorType * const scanwordVectorType =  VectorType::get(sizeTy, fieldCount);
61    Constant * blockSize = iBuilder->getSize(iBuilder->getBitBlockWidth());
62    Constant * blockSizeLess1 = iBuilder->getSize(iBuilder->getBitBlockWidth() - 1);
63
64    Function::arg_iterator args = mCurrentMethod->arg_begin();
65    /* self = */ args++;
66    Value * itemsToDo = &*(args++);
67    /* inputStreamAvail = */ args++;
68    Value * match_result = &*(args++);
69    Value * line_break = &*(args++);
70    /* input_stream = */ args++;
71
72    Value * blocksToDo = iBuilder->CreateUDiv(iBuilder->CreateAdd(itemsToDo, blockSizeLess1), blockSize);
73   
74    Value * match_result_ptr = iBuilder->CreateBitCast(match_result, scanwordVectorType->getPointerTo());
75    Value * line_break_ptr = iBuilder->CreateBitCast(line_break, scanwordVectorType->getPointerTo());
76
77    iBuilder->CreateCondBr(iBuilder->CreateICmpUGT(blocksToDo, iBuilder->getSize(0)), initialBlock, blocksExit);
78
79    iBuilder->SetInsertPoint(initialBlock);
80    PHINode * const blockBase = iBuilder->CreatePHI(iBuilder->getSizeTy(), 2);
81    blockBase->addIncoming(iBuilder->getSize(0), entryBlock);
82    Value * const blockNo = iBuilder->getScalarField("BlockNo");
83    Value * const scanwordPos = iBuilder->CreateShl(blockNo, floor_log2(iBuilder->getBitBlockWidth()));
84    Value * const lastRecordStart = iBuilder->getProcessedItemCount("InputStream");
85    Value * const lastRecordNum = iBuilder->getScalarField("LineNum");
86    iBuilder->CreateBr(scanWordIteration);
87
88    iBuilder->SetInsertPoint(scanWordIteration);
89
90        // while (phiIndex < words per stride)
91        PHINode * const phiIndex = iBuilder->CreatePHI(iBuilder->getInt32Ty(), 2, "index");
92        phiIndex->addIncoming(iBuilder->getInt32(0), initialBlock);
93        PHINode * const phiScanwordPos = iBuilder->CreatePHI(scanwordPos->getType(), 2, "pos");
94        phiScanwordPos->addIncoming(scanwordPos, initialBlock);
95        PHINode * const phiLineStart = iBuilder->CreatePHI(lastRecordStart->getType(), 2, "recordstart");
96        phiLineStart->addIncoming(lastRecordStart, initialBlock);
97        PHINode * const phiLineNum = iBuilder->CreatePHI(lastRecordNum->getType(), 2, "recordnum");
98        phiLineNum->addIncoming(lastRecordNum, initialBlock);
99        Value * const matches = iBuilder->CreateLoad(iBuilder->CreateGEP(match_result_ptr, blockBase));
100        Value * const linebreaks = iBuilder->CreateLoad(iBuilder->CreateGEP(line_break_ptr, blockBase));
101        Value * const matchWord = iBuilder->CreateExtractElement(matches, phiIndex);
102        Value * const recordBreaks = iBuilder->CreateExtractElement(linebreaks, phiIndex);
103
104        // The match scanner works with a loop involving four variables:
105        // (a) the bit stream scanword of matches marking the ends of selected records,
106        // (b) the bit stream scanword of record_breaks marking the ends of all records,
107        // (c) the integer lastRecordNum indicating the number of records processed so far,
108        // (d) the index lastRecordStart indicating the file position of the last record.
109        // We set up a loop structure, in which a set of 4 phi nodes initialize these
110        // variables from either the input to the scanner or the computed values within
111        // the loop body.
112
113        iBuilder->CreateBr(matches_test_block);
114
115        // LOOP Test Block
116        iBuilder->SetInsertPoint(matches_test_block);
117        PHINode * phiMatchWord = iBuilder->CreatePHI(sizeTy, 2, "matches");
118        PHINode * phiRecordBreaks = iBuilder->CreatePHI(sizeTy, 2, "recordbreaks");
119        PHINode * phiRecordStart = iBuilder->CreatePHI(sizeTy, 2, "recordstart");
120        PHINode * phiRecordNum = iBuilder->CreatePHI(sizeTy, 2, "recordnum");
121        phiMatchWord->addIncoming(matchWord, scanWordIteration);
122        phiRecordBreaks->addIncoming(recordBreaks, scanWordIteration);
123        phiRecordNum->addIncoming(phiLineNum, scanWordIteration);
124        phiRecordStart->addIncoming(phiLineStart, scanWordIteration);
125        Value * anyMatches = iBuilder->CreateICmpNE(phiMatchWord, ConstantInt::getNullValue(sizeTy));
126        iBuilder->CreateCondBr(anyMatches, processMatchesEntry, processMatchesExit);
127
128            // LOOP BODY
129            // The loop body is entered if we have more matches to process.
130            iBuilder->SetInsertPoint(processMatchesEntry);
131            Value * prior_breaks = iBuilder->CreateAnd(iBuilder->CreateMaskToLowestBitExclusive(phiMatchWord), phiRecordBreaks);
132            // Within the loop we have a conditional block that is executed if there are any prior record breaks.
133            Value * prior_breaks_cond = iBuilder->CreateICmpNE(prior_breaks, ConstantInt::getNullValue(sizeTy));
134            iBuilder->CreateCondBr(prior_breaks_cond, prior_breaks_block, loop_final_block);
135
136                // PRIOR_BREAKS_BLOCK
137                // If there are prior breaks, we count them and compute the record start position.
138                iBuilder->SetInsertPoint(prior_breaks_block);
139                Value * matchedRecordNum = iBuilder->CreateAdd(iBuilder->CreatePopcount(prior_breaks), phiRecordNum);
140                Value * reverseDistance = iBuilder->CreateCountReverseZeroes(prior_breaks);
141                Value * width = ConstantInt::get(sizeTy, sizeTy->getBitWidth());
142                Value * priorRecordStart = iBuilder->CreateAdd(phiScanwordPos, iBuilder->CreateSub(width, reverseDistance));
143                iBuilder->CreateBr(loop_final_block);
144
145            // LOOP FINAL BLOCK
146            // The prior breaks, if any have been counted.  Set up phi nodes for the recordNum
147            // and recortStart depending on whether the conditional execution of prior_breaks_block.
148            iBuilder->SetInsertPoint(loop_final_block);
149            PHINode * matchRecordNum = iBuilder->CreatePHI(sizeTy, 2, "matchRecordNum");
150            matchRecordNum->addIncoming(phiRecordNum, processMatchesEntry);
151            matchRecordNum->addIncoming(matchedRecordNum, prior_breaks_block);
152            phiRecordNum->addIncoming(matchRecordNum, loop_final_block);
153
154            PHINode * matchRecordStart = iBuilder->CreatePHI(sizeTy, 2, "matchRecordStart");
155            matchRecordStart->addIncoming(phiRecordStart, processMatchesEntry);
156            matchRecordStart->addIncoming(priorRecordStart, prior_breaks_block);
157            phiRecordStart->addIncoming(matchRecordStart, loop_final_block);
158            Value * matchRecordEnd = iBuilder->CreateAdd(phiScanwordPos, iBuilder->CreateCountForwardZeroes(phiMatchWord));
159            if (mGrepType == GrepType::CallBack) {
160                Function * dispatcher = iBuilder->LinkFunction<void (intptr_t, size_t, size_t, size_t)>("accumulate_match_wrapper", & accumulate_match_wrapper);
161                Value * accumulator = iBuilder->getScalarField("accumulator_address");
162                iBuilder->CreateCall(dispatcher, {accumulator, matchRecordNum, matchRecordStart, matchRecordEnd});
163            }
164            else {
165                Function * matcher = m->getFunction("matcher"); assert (matcher);
166                auto args_matcher = matcher->arg_begin();
167                Value * const mrn = iBuilder->CreateZExtOrTrunc(matchRecordNum, args_matcher->getType());
168                Value * const mrs = iBuilder->CreateZExtOrTrunc(matchRecordStart, (++args_matcher)->getType());
169                Value * const mre = iBuilder->CreateZExtOrTrunc(matchRecordEnd, (++args_matcher)->getType());
170                Value * const inputStream = iBuilder->getRawInputPointer("InputStream", iBuilder->getInt32(0), iBuilder->getInt32(0));
171                Value * const is = iBuilder->CreatePointerCast(inputStream, (++args_matcher)->getType());
172                if (mGrepType == GrepType::Normal) {
173                    Value * const sz = iBuilder->CreateZExtOrTrunc(iBuilder->getBufferedSize("InputStream"), (++args_matcher)->getType());
174                    Value * const fi = iBuilder->CreateZExtOrTrunc(iBuilder->getScalarField("FileIdx"), (++args_matcher)->getType());
175                    iBuilder->CreateCall(matcher, {mrn, mrs, mre, is, sz, fi});
176                } else {
177                    iBuilder->CreateCall(matcher, {mrn, mrs, mre, is});
178                }
179            }
180            Value * remaining_matches = iBuilder->CreateResetLowestBit(phiMatchWord);
181            phiMatchWord->addIncoming(remaining_matches, loop_final_block);
182
183            Value * remaining_breaks = iBuilder->CreateXor(phiRecordBreaks, prior_breaks);
184            phiRecordBreaks->addIncoming(remaining_breaks, loop_final_block);
185
186            iBuilder->CreateBr(matches_test_block);
187
188        // LOOP EXIT/MATCHES_DONE
189        iBuilder->SetInsertPoint(processMatchesExit);
190        // When the matches are done, there may be additional record breaks remaining
191        Value * more_breaks_cond = iBuilder->CreateICmpNE(phiRecordBreaks, ConstantInt::getNullValue(sizeTy));
192        iBuilder->CreateCondBr(more_breaks_cond, remaining_breaks_block, return_block);
193
194            // REMAINING_BREAKS_BLOCK: process remaining record breaks after all matches are processed
195            iBuilder->SetInsertPoint(remaining_breaks_block);
196            Value * break_count = iBuilder->CreatePopcount(phiRecordBreaks);
197            Value * final_record_num = iBuilder->CreateAdd(phiRecordNum, break_count);
198            Value * reverseZeroes = iBuilder->CreateCountReverseZeroes(phiRecordBreaks);
199            Value * pendingLineStart = iBuilder->CreateAdd(phiScanwordPos, iBuilder->CreateSub(width, reverseZeroes));
200            iBuilder->CreateBr(return_block);
201
202        // RETURN block
203        iBuilder->SetInsertPoint(return_block);
204        PHINode * phiFinalRecordNum = iBuilder->CreatePHI(sizeTy, 2, "finalRecordCount");
205        PHINode * phiFinalRecordStart = iBuilder->CreatePHI(sizeTy, 2, "finalRecordStart");
206
207        phiFinalRecordNum->addIncoming(phiRecordNum, processMatchesExit);
208        phiFinalRecordNum->addIncoming(final_record_num, remaining_breaks_block);
209        phiLineNum->addIncoming(phiFinalRecordNum, return_block);
210
211        phiFinalRecordStart->addIncoming(phiRecordStart, processMatchesExit);
212        phiFinalRecordStart->addIncoming(pendingLineStart, remaining_breaks_block);
213        phiLineStart->addIncoming(phiFinalRecordStart, return_block);
214
215        Value * nextScanwordPos = iBuilder->CreateAdd(phiScanwordPos, ConstantInt::get(sizeTy, sizeTy->getBitWidth()));
216        phiScanwordPos->addIncoming(nextScanwordPos, return_block);
217        Value * nextIndex = iBuilder->CreateAdd(phiIndex, iBuilder->getInt32(1));
218        phiIndex->addIncoming(nextIndex, return_block);
219        iBuilder->CreateLikelyCondBr(iBuilder->CreateICmpNE(nextIndex, iBuilder->getInt32(fieldCount)), scanWordIteration, scanWordExit);
220
221    iBuilder->SetInsertPoint(scanWordExit);
222    iBuilder->setScalarField("BlockNo", iBuilder->CreateAdd(blockNo, ConstantInt::get(blockNo->getType(), 1)));
223    iBuilder->setScalarField("LineNum", phiFinalRecordNum);
224    iBuilder->setProcessedItemCount("InputStream", phiFinalRecordStart);
225    Value * blockBaseNext = iBuilder->CreateAdd(blockBase, ConstantInt::get(iBuilder->getSizeTy(), 1));
226    blockBase->addIncoming(blockBaseNext, scanWordExit);
227    iBuilder->CreateLikelyCondBr(iBuilder->CreateICmpNE(blockBaseNext, blocksToDo), initialBlock, blocksExit);
228
229    iBuilder->SetInsertPoint(blocksExit);
230}
231
232ScanMatchKernel::ScanMatchKernel(const std::unique_ptr<kernel::KernelBuilder> & b, GrepType grepType, const unsigned codeUnitWidth)
233: MultiBlockKernel("scanMatch" + getGrepTypeId(grepType) + std::to_string(codeUnitWidth),
234    {Binding{b->getStreamSetTy(1, 1), "matchResult"}, Binding{b->getStreamSetTy(1, 1), "lineBreak"}, Binding{b->getStreamSetTy(1, 8), "InputStream", UnknownRate()}},
235    {},
236    {},
237    {},
238    {Binding{b->getSizeTy(), "BlockNo"}, Binding{b->getSizeTy(), "LineNum"}})
239, mGrepType(grepType) {
240    if (mGrepType == GrepType::CallBack) {
241        mScalarInputs.push_back(Binding{b->getIntAddrTy(), "accumulator_address"});
242    }
243    else {
244        mScalarInputs.push_back(Binding{b->getInt32Ty(), "FileIdx"});
245    }
246}
247
248}
Note: See TracBrowser for help on using the repository browser.