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

Last change on this file since 5404 was 5398, checked in by nmedfort, 2 years ago

Continued work on processing stdin input. Partial integration of ParabixDriver? methods into icgrep and editd. Object cache does not currently work for recursive REs.

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