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

Last change on this file since 5440 was 5440, checked in by nmedfort, 23 months ago

Large refactoring step. Removed IR generation code from Kernel (formally KernelBuilder?) and moved it into the new KernelBuilder? class.

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 <llvm/IR/Module.h>
9#include <kernels/kernel_builder.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(const std::unique_ptr<KernelBuilder> &iBuilder) {
34
35    Module * const m = iBuilder->getModule();
36    BasicBlock * const entryBlock = iBuilder->GetInsertBlock();
37    BasicBlock * const scanWordIteration = iBuilder->CreateBasicBlock("ScanWordIteration");
38    BasicBlock * const matches_test_block = iBuilder->CreateBasicBlock("matches_test_block");
39    BasicBlock * const processMatchesEntry = iBuilder->CreateBasicBlock("process_matches_loop");
40    BasicBlock * const prior_breaks_block = iBuilder->CreateBasicBlock("prior_breaks_block");
41    BasicBlock * const loop_final_block = iBuilder->CreateBasicBlock("loop_final_block");
42    BasicBlock * const processMatchesExit = iBuilder->CreateBasicBlock("matches_done_block");
43    BasicBlock * const remaining_breaks_block = iBuilder->CreateBasicBlock("remaining_breaks_block");
44    BasicBlock * const return_block = iBuilder->CreateBasicBlock("return_block");
45    BasicBlock * const scanWordExit = iBuilder->CreateBasicBlock("ScanWordExit");
46    IntegerType * const sizeTy = iBuilder->getSizeTy();
47    const unsigned fieldCount = iBuilder->getBitBlockWidth() / sizeTy->getBitWidth();
48    VectorType * const scanwordVectorType =  VectorType::get(sizeTy, fieldCount);
49    Value * const blockNo = iBuilder->getScalarField("BlockNo");
50    Value * const scanwordPos = iBuilder->CreateShl(blockNo, floor_log2(iBuilder->getBitBlockWidth()));
51    Value * const lastRecordStart = iBuilder->getProcessedItemCount("InputStream");
52    Value * const lastRecordNum = iBuilder->getScalarField("LineNum");
53
54    Value * const matches = iBuilder->CreateBitCast(iBuilder->loadInputStreamBlock("matchResult", iBuilder->getInt32(0)), scanwordVectorType);
55    Value * const linebreaks = iBuilder->CreateBitCast(iBuilder->loadInputStreamBlock("lineBreak", iBuilder->getInt32(0)), scanwordVectorType);
56
57    iBuilder->CreateBr(scanWordIteration);
58
59    iBuilder->SetInsertPoint(scanWordIteration);
60
61        // while (phiIndex < words per stride)
62        PHINode * const phiIndex = iBuilder->CreatePHI(iBuilder->getInt32Ty(), 2, "index");
63        phiIndex->addIncoming(iBuilder->getInt32(0), entryBlock);
64        PHINode * const phiScanwordPos = iBuilder->CreatePHI(scanwordPos->getType(), 2, "pos");
65        phiScanwordPos->addIncoming(scanwordPos, entryBlock);
66        PHINode * const phiLineStart = iBuilder->CreatePHI(lastRecordStart->getType(), 2, "recordstart");
67        phiLineStart->addIncoming(lastRecordStart, entryBlock);
68        PHINode * const phiLineNum = iBuilder->CreatePHI(lastRecordNum->getType(), 2, "recordnum");
69        phiLineNum->addIncoming(lastRecordNum, entryBlock);
70        Value * const matchWord = iBuilder->CreateExtractElement(matches, phiIndex);
71        Value * const recordBreaks = iBuilder->CreateExtractElement(linebreaks, phiIndex);
72
73        // The match scanner works with a loop involving four variables:
74        // (a) the bit stream scanword of matches marking the ends of selected records,
75        // (b) the bit stream scanword of record_breaks marking the ends of all records,
76        // (c) the integer lastRecordNum indicating the number of records processed so far,
77        // (d) the index lastRecordStart indicating the file position of the last record.
78        // We set up a loop structure, in which a set of 4 phi nodes initialize these
79        // variables from either the input to the scanner or the computed values within
80        // the loop body.
81
82        iBuilder->CreateBr(matches_test_block);
83
84        // LOOP Test Block
85        iBuilder->SetInsertPoint(matches_test_block);
86        PHINode * phiMatchWord = iBuilder->CreatePHI(sizeTy, 2, "matches");
87        PHINode * phiRecordBreaks = iBuilder->CreatePHI(sizeTy, 2, "recordbreaks");
88        PHINode * phiRecordStart = iBuilder->CreatePHI(sizeTy, 2, "recordstart");
89        PHINode * phiRecordNum = iBuilder->CreatePHI(sizeTy, 2, "recordnum");
90        phiMatchWord->addIncoming(matchWord, scanWordIteration);
91        phiRecordBreaks->addIncoming(recordBreaks, scanWordIteration);
92        phiRecordNum->addIncoming(phiLineNum, scanWordIteration);
93        phiRecordStart->addIncoming(phiLineStart, scanWordIteration);
94        Value * anyMatches = iBuilder->CreateICmpNE(phiMatchWord, ConstantInt::getNullValue(sizeTy));
95        iBuilder->CreateCondBr(anyMatches, processMatchesEntry, processMatchesExit);
96
97            // LOOP BODY
98            // The loop body is entered if we have more matches to process.
99            iBuilder->SetInsertPoint(processMatchesEntry);
100            Value * prior_breaks = iBuilder->CreateAnd(iBuilder->CreateMaskToLowestBitExclusive(phiMatchWord), phiRecordBreaks);
101            // Within the loop we have a conditional block that is executed if there are any prior record breaks.
102            Value * prior_breaks_cond = iBuilder->CreateICmpNE(prior_breaks, ConstantInt::getNullValue(sizeTy));
103            iBuilder->CreateCondBr(prior_breaks_cond, prior_breaks_block, loop_final_block);
104
105                // PRIOR_BREAKS_BLOCK
106                // If there are prior breaks, we count them and compute the record start position.
107                iBuilder->SetInsertPoint(prior_breaks_block);
108                Value * matchedRecordNum = iBuilder->CreateAdd(iBuilder->CreatePopcount(prior_breaks), phiRecordNum);
109                Value * reverseDistance = iBuilder->CreateCountReverseZeroes(prior_breaks);
110                Value * width = ConstantInt::get(sizeTy, sizeTy->getBitWidth());
111                Value * priorRecordStart = iBuilder->CreateAdd(phiScanwordPos, iBuilder->CreateSub(width, reverseDistance));
112                iBuilder->CreateBr(loop_final_block);
113
114            // LOOP FINAL BLOCK
115            // The prior breaks, if any have been counted.  Set up phi nodes for the recordNum
116            // and recortStart depending on whether the conditional execution of prior_breaks_block.
117            iBuilder->SetInsertPoint(loop_final_block);
118            PHINode * matchRecordNum = iBuilder->CreatePHI(sizeTy, 2, "matchRecordNum");
119            matchRecordNum->addIncoming(phiRecordNum, processMatchesEntry);
120            matchRecordNum->addIncoming(matchedRecordNum, prior_breaks_block);
121            phiRecordNum->addIncoming(matchRecordNum, loop_final_block);
122
123            PHINode * matchRecordStart = iBuilder->CreatePHI(sizeTy, 2, "matchRecordStart");
124            matchRecordStart->addIncoming(phiRecordStart, processMatchesEntry);
125            matchRecordStart->addIncoming(priorRecordStart, prior_breaks_block);
126            phiRecordStart->addIncoming(matchRecordStart, loop_final_block);
127            Value * matchRecordEnd = iBuilder->CreateAdd(phiScanwordPos, iBuilder->CreateCountForwardZeroes(phiMatchWord));
128
129            Function * const matcher = m->getFunction("matcher"); assert (matcher);
130            auto args = matcher->arg_begin();
131            Value * const mrn = iBuilder->CreateZExtOrTrunc(matchRecordNum, args->getType());
132            Value * const mrs = iBuilder->CreateZExtOrTrunc(matchRecordStart, (++args)->getType());
133            Value * const mre = iBuilder->CreateZExtOrTrunc(matchRecordEnd, (++args)->getType());
134            Value * const inputStream = iBuilder->getRawInputPointer("InputStream", iBuilder->getInt32(0), iBuilder->getInt32(0));
135            Value * const is = iBuilder->CreatePointerCast(inputStream, (++args)->getType());
136            if (mGrepType == GrepType::Normal) {
137                Value * const sz = iBuilder->CreateZExtOrTrunc(iBuilder->getBufferedSize("InputStream"), (++args)->getType());
138                Value * const fi = iBuilder->CreateZExtOrTrunc(iBuilder->getScalarField("FileIdx"), (++args)->getType());
139                iBuilder->CreateCall(matcher, {mrn, mrs, mre, is, sz, fi});
140            } else {
141                iBuilder->CreateCall(matcher, {mrn, mrs, mre, is});
142            }
143
144            Value * remaining_matches = iBuilder->CreateResetLowestBit(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    iBuilder->setScalarField("BlockNo", iBuilder->CreateAdd(blockNo, ConstantInt::get(blockNo->getType(), 1)));
187    iBuilder->setScalarField("LineNum", phiFinalRecordNum);
188    iBuilder->setProcessedItemCount("InputStream", phiFinalRecordStart);
189}
190
191ScanMatchKernel::ScanMatchKernel(const std::unique_ptr<kernel::KernelBuilder> & b, GrepType grepType, const unsigned codeUnitWidth)
192: BlockOrientedKernel("scanMatch" + getGrepTypeId(grepType) + std::to_string(codeUnitWidth),
193    {Binding{b->getStreamSetTy(1, 1), "matchResult"}, Binding{b->getStreamSetTy(1, 1), "lineBreak"}, Binding{b->getStreamSetTy(1, 8), "InputStream", UnknownRate()}},
194    {},
195    {Binding{b->getInt32Ty(), "FileIdx"}},
196    {},
197    {Binding{b->getSizeTy(), "BlockNo"}, Binding{b->getSizeTy(), "LineNum"}})
198, mGrepType(grepType) {
199
200}
201
202}
Note: See TracBrowser for help on using the repository browser.