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

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

Support for stdin. Needs more testing.

File size: 13.6 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
13namespace kernel {
14
15Value * generateForwardZeroesMask(IDISA::IDISA_Builder * iBuilder, Value * bits) {
16    Value * bits_minus1 = iBuilder->CreateSub(bits, ConstantInt::get(bits->getType(), 1));
17    return iBuilder->CreateAnd(bits_minus1, iBuilder->CreateNot(bits));
18}
19
20Value * generatePopcount(IDISA::IDISA_Builder * iBuilder, Value * bits) {
21    Value * ctpopFunc = Intrinsic::getDeclaration(iBuilder->getModule(), Intrinsic::ctpop, bits->getType());
22    return iBuilder->CreateCall(ctpopFunc, std::vector<Value *>({bits}));
23}
24
25Value * generateCountForwardZeroes(IDISA::IDISA_Builder * iBuilder, Value * bits) {
26    Value * cttzFunc = Intrinsic::getDeclaration(iBuilder->getModule(), Intrinsic::cttz, bits->getType());
27    return iBuilder->CreateCall(cttzFunc, std::vector<Value *>({bits, ConstantInt::get(iBuilder->getInt1Ty(), 0)}));
28}
29
30Value * generateCountReverseZeroes(IDISA::IDISA_Builder * iBuilder, Value * bits) {
31    Value * ctlzFunc = Intrinsic::getDeclaration(iBuilder->getModule(), Intrinsic::ctlz, bits->getType());
32    return iBuilder->CreateCall(ctlzFunc, std::vector<Value *>({bits, ConstantInt::get(iBuilder->getInt1Ty(), 0)}));
33}
34
35Value * generateResetLowestBit(IDISA::IDISA_Builder * iBuilder, Value * bits) {
36    Value * bits_minus1 = iBuilder->CreateSub(bits, ConstantInt::get(bits->getType(), 1));
37    return iBuilder->CreateAnd(bits_minus1, bits);
38}
39       
40
41
42void ScanMatchKernel::generateDoBlockMethod() {
43
44    Module * const m = iBuilder->getModule();
45    BasicBlock * const entryBlock = iBuilder->GetInsertBlock();
46    BasicBlock * const scanWordIteration = CreateBasicBlock("ScanWordIteration");
47    BasicBlock * const matches_test_block = CreateBasicBlock("matches_test_block");
48    BasicBlock * const processMatchesEntry = CreateBasicBlock("process_matches_loop");
49    BasicBlock * const prior_breaks_block = CreateBasicBlock("prior_breaks_block");
50    BasicBlock * const loop_final_block = CreateBasicBlock("loop_final_block");
51    BasicBlock * const processMatchesExit = CreateBasicBlock("matches_done_block");
52    BasicBlock * const remaining_breaks_block = CreateBasicBlock("remaining_breaks_block");
53    BasicBlock * const return_block = CreateBasicBlock("return_block");
54    BasicBlock * const scanWordExit = CreateBasicBlock("ScanWordExit");
55    IntegerType * const sizeTy = iBuilder->getSizeTy();
56    PointerType * const codeUnitTy = iBuilder->getIntNTy(mCodeUnitWidth)->getPointerTo();
57    const unsigned fieldCount = iBuilder->getBitBlockWidth() / sizeTy->getBitWidth();
58    VectorType * const scanwordVectorType =  VectorType::get(sizeTy, fieldCount);
59    Value * const blockNo = getScalarField("BlockNo");
60    Value * const scanwordPos = iBuilder->CreateMul(blockNo, ConstantInt::get(blockNo->getType(), iBuilder->getBitBlockWidth()));
61    Value * const lastRecordStart = getScalarField("LineStart");
62    Value * const lastRecordNum = getScalarField("LineNum");
63    Value * const inputStream = iBuilder->CreatePointerCast(getRawInputPointer("InputStream", iBuilder->getInt32(0), iBuilder->getInt32(0)), codeUnitTy);
64
65    Value * fileSize = iBuilder->CreateAdd(getProcessedItemCount("InputStream"), getScalarField("PendingBytes"));
66
67    Constant * matchProcessor = nullptr;
68    Value * fileIdx = nullptr;
69    switch (mGrepType) {
70        case GrepType::Normal:
71            fileIdx = getScalarField("FileIdx");
72            matchProcessor = m->getOrInsertFunction("wrapped_report_match" + std::to_string(mCodeUnitWidth), iBuilder->getVoidTy(), sizeTy, sizeTy, sizeTy, codeUnitTy, sizeTy, sizeTy, nullptr);
73            break;
74        case GrepType::NameExpression:
75            matchProcessor = m->getOrInsertFunction("insert_codepoints", iBuilder->getVoidTy(), sizeTy, sizeTy, sizeTy, codeUnitTy, nullptr);
76            break;
77        case GrepType::PropertyValue:
78            matchProcessor = m->getOrInsertFunction("insert_property_values", iBuilder->getVoidTy(), sizeTy, sizeTy, sizeTy, codeUnitTy, nullptr);
79            break;
80        default: llvm_unreachable("unknown grep type");
81    }
82    Value * const matchesPtr = getInputStreamBlockPtr("matchResult", iBuilder->getInt32(0));
83    Value * const matches = iBuilder->CreateBitCast(iBuilder->CreateBlockAlignedLoad(matchesPtr), scanwordVectorType);
84
85    Value * const linebreaksPtr = getInputStreamBlockPtr("lineBreak", iBuilder->getInt32(0));
86    Value * const linebreaks = iBuilder->CreateBitCast(iBuilder->CreateBlockAlignedLoad(linebreaksPtr), scanwordVectorType);
87
88    iBuilder->CreateBr(scanWordIteration);
89
90    iBuilder->SetInsertPoint(scanWordIteration);
91
92        // while (phiIndex < words per stride)
93        PHINode * const phiIndex = iBuilder->CreatePHI(iBuilder->getInt32Ty(), 2, "index");
94        phiIndex->addIncoming(iBuilder->getInt32(0), entryBlock);
95        PHINode * const phiScanwordPos = iBuilder->CreatePHI(scanwordPos->getType(), 2, "pos");
96        phiScanwordPos->addIncoming(scanwordPos, entryBlock);
97        PHINode * const phiLineStart = iBuilder->CreatePHI(lastRecordStart->getType(), 2, "recordstart");
98        phiLineStart->addIncoming(lastRecordStart, entryBlock);
99        PHINode * const phiLineNum = iBuilder->CreatePHI(lastRecordNum->getType(), 2, "recordnum");
100        phiLineNum->addIncoming(lastRecordNum, entryBlock);
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(generateForwardZeroesMask(iBuilder, 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(generatePopcount(iBuilder, prior_breaks), phiRecordNum);
140                Value * reverseDistance = generateCountReverseZeroes(iBuilder, 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
159            Value * matchRecordEnd = iBuilder->CreateAdd(phiScanwordPos, generateCountForwardZeroes(iBuilder, phiMatchWord));
160            switch (mGrepType) {
161                case GrepType::Normal:
162                    iBuilder->CreateCall(matchProcessor, {matchRecordNum, matchRecordStart, matchRecordEnd, inputStream, fileSize, fileIdx});
163                    break;
164                case GrepType::NameExpression:
165                case GrepType::PropertyValue:
166                    iBuilder->CreateCall(matchProcessor, {matchRecordNum, matchRecordStart, matchRecordEnd, inputStream});
167                    break;
168                default: break;
169            }
170
171            Value * remaining_matches = generateResetLowestBit(iBuilder, phiMatchWord);
172            phiMatchWord->addIncoming(remaining_matches, loop_final_block);
173
174            Value * remaining_breaks = iBuilder->CreateXor(phiRecordBreaks, prior_breaks);
175            phiRecordBreaks->addIncoming(remaining_breaks, loop_final_block);
176
177            iBuilder->CreateBr(matches_test_block);
178
179        // LOOP EXIT/MATCHES_DONE
180        iBuilder->SetInsertPoint(processMatchesExit);
181        // When the matches are done, there may be additional record breaks remaining
182        Value * more_breaks_cond = iBuilder->CreateICmpNE(phiRecordBreaks, ConstantInt::getNullValue(sizeTy));
183        iBuilder->CreateCondBr(more_breaks_cond, remaining_breaks_block, return_block);
184
185            // REMAINING_BREAKS_BLOCK: process remaining record breaks after all matches are processed
186            iBuilder->SetInsertPoint(remaining_breaks_block);
187            Value * break_count = generatePopcount(iBuilder, phiRecordBreaks);
188            Value * final_record_num = iBuilder->CreateAdd(phiRecordNum, break_count);
189            Value * reverseZeroes = generateCountReverseZeroes(iBuilder, phiRecordBreaks);
190            Value * pendingLineStart = iBuilder->CreateAdd(phiScanwordPos, iBuilder->CreateSub(width, reverseZeroes));
191            iBuilder->CreateBr(return_block);
192
193        // RETURN block
194        iBuilder->SetInsertPoint(return_block);
195        PHINode * phiFinalRecordNum = iBuilder->CreatePHI(sizeTy, 2, "finalRecordCount");
196        PHINode * phiFinalRecordStart = iBuilder->CreatePHI(sizeTy, 2, "finalRecordStart");
197
198        phiFinalRecordNum->addIncoming(phiRecordNum, processMatchesExit);
199        phiFinalRecordNum->addIncoming(final_record_num, remaining_breaks_block);
200        phiLineNum->addIncoming(phiFinalRecordNum, return_block);
201
202        phiFinalRecordStart->addIncoming(phiRecordStart, processMatchesExit);
203        phiFinalRecordStart->addIncoming(pendingLineStart, remaining_breaks_block);
204        phiLineStart->addIncoming(phiFinalRecordStart, return_block);
205
206        Value * nextScanwordPos = iBuilder->CreateAdd(phiScanwordPos, ConstantInt::get(sizeTy, sizeTy->getBitWidth()));
207        phiScanwordPos->addIncoming(nextScanwordPos, return_block);
208
209        Value * nextIndex = iBuilder->CreateAdd(phiIndex, iBuilder->getInt32(1));
210        phiIndex->addIncoming(nextIndex, return_block);
211        iBuilder->CreateLikelyCondBr(iBuilder->CreateICmpNE(nextIndex, iBuilder->getInt32(fieldCount)), scanWordIteration, scanWordExit);
212
213    iBuilder->SetInsertPoint(scanWordExit);
214    setScalarField("BlockNo", iBuilder->CreateAdd(blockNo, ConstantInt::get(blockNo->getType(), 1)));
215    setScalarField("LineStart", phiFinalRecordStart);
216    setScalarField("LineNum", phiFinalRecordNum);
217}
218
219void ScanMatchKernel::generateInitMethod() {
220    setScalarField("PendingBytes", iBuilder->getSize(iBuilder->getBitBlockWidth() + 2));
221}
222
223void ScanMatchKernel::generateFinalBlockMethod(llvm::Value * remainingItems) {
224    setScalarField("PendingBytes", remainingItems);
225    CreateDoBlockMethodCall();
226}
227
228ScanMatchKernel::ScanMatchKernel(IDISA::IDISA_Builder * iBuilder, GrepType grepType, const unsigned codeUnitWidth)
229: BlockOrientedKernel(iBuilder, "scanMatch" + std::to_string(codeUnitWidth),
230    {Binding{iBuilder->getStreamSetTy(1, 8), "InputStream"}, Binding{iBuilder->getStreamSetTy(1, 1), "matchResult"}, Binding{iBuilder->getStreamSetTy(1, 1), "lineBreak"}},
231    {},
232    {Binding{iBuilder->getSizeTy(), "FileIdx"}},
233    {},
234    {Binding{iBuilder->getSizeTy(), "BlockNo"}, Binding{iBuilder->getSizeTy(), "LineStart"}, Binding{iBuilder->getSizeTy(), "LineNum"}, Binding{iBuilder->getSizeTy(), "PendingBytes"}})
235, mGrepType(grepType)
236, mCodeUnitWidth(codeUnitWidth) {
237}
238
239}
Note: See TracBrowser for help on using the repository browser.