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

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

Partial removal of BlockNo?

File size: 13.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
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       
40void ScanMatchKernel::generateDoBlockMethod() {
41
42    auto savePoint = iBuilder->saveIP();
43    Function * scanWordFunction = generateScanWordRoutine(iBuilder->getModule());
44    iBuilder->restoreIP(savePoint);
45
46    IntegerType * T = iBuilder->getSizeTy();
47    const unsigned fieldCount = iBuilder->getBitBlockWidth() / T->getBitWidth();
48    Type * scanwordVectorType =  VectorType::get(T, fieldCount);
49    Value * blockNo = getBlockNo();
50    Value * scanwordPos = iBuilder->CreateMul(blockNo, ConstantInt::get(blockNo->getType(), iBuilder->getBitBlockWidth()));   
51    Value * recordStart = getScalarField("LineStart");
52    Value * recordNum = getScalarField("LineNum");
53    Value * matches = iBuilder->CreateBlockAlignedLoad(getInputStream("matchResults", iBuilder->getInt32(0)));
54    Value * linebreaks = iBuilder->CreateBlockAlignedLoad(getInputStream("matchResults", iBuilder->getInt32(1)));
55    Value * matchWordVector = iBuilder->CreateBitCast(matches, scanwordVectorType);
56    Value * breakWordVector = iBuilder->CreateBitCast(linebreaks, scanwordVectorType);
57    for(unsigned i = 0; i < fieldCount; ++i){
58        Value * matchWord = iBuilder->CreateExtractElement(matchWordVector, ConstantInt::get(T, i));
59        Value * recordBreaksWord = iBuilder->CreateExtractElement(breakWordVector, ConstantInt::get(T, i));
60        Value * wordResult = iBuilder->CreateCall(scanWordFunction, {getSelf(), matchWord, recordBreaksWord, scanwordPos, recordStart, recordNum});
61        scanwordPos = iBuilder->CreateAdd(scanwordPos, ConstantInt::get(T, T->getBitWidth()));
62        recordStart = iBuilder->CreateExtractValue(wordResult, std::vector<unsigned>({0}));
63        recordNum = iBuilder->CreateExtractValue(wordResult, std::vector<unsigned>({1}));
64    }
65    setScalarField("LineStart", recordStart);
66    setScalarField("LineNum", recordNum);
67}
68
69   
70Function * ScanMatchKernel::generateScanWordRoutine(Module * m) const {
71    Function * function = m->getFunction("scan_matches_in_scanword");
72    if (LLVM_UNLIKELY(function != nullptr)) {
73        return function;
74    }
75   
76    LLVMContext & ctxt = m->getContext();
77
78    IntegerType * T = iBuilder->getSizeTy();
79    Type * S = PointerType::get(iBuilder->getIntNTy(8), 0);
80    Type * returnType = StructType::get(ctxt, std::vector<Type *>({T, T}));
81    FunctionType * functionType = FunctionType::get(returnType, std::vector<Type *>({PointerType::get(mKernelStateType, 0), T, T, T, T, T}), false);
82   
83    SmallVector<AttributeSet, 6> Attrs;
84    Attrs.push_back(AttributeSet::get(ctxt, ~0U, std::vector<Attribute::AttrKind>({ Attribute::NoUnwind, Attribute::UWTable })));
85    Attrs.push_back(AttributeSet::get(ctxt, 1, std::vector<Attribute::AttrKind>({})));
86    Attrs.push_back(AttributeSet::get(ctxt, 2, std::vector<Attribute::AttrKind>({})));
87    Attrs.push_back(AttributeSet::get(ctxt, 3, std::vector<Attribute::AttrKind>({})));
88    Attrs.push_back(AttributeSet::get(ctxt, 4, std::vector<Attribute::AttrKind>({})));
89    Attrs.push_back(AttributeSet::get(ctxt, 5, std::vector<Attribute::AttrKind>({})));
90    AttributeSet AttrSet = AttributeSet::get(ctxt, Attrs);
91   
92    function = Function::Create(functionType, GlobalValue::ExternalLinkage, "scan_matches_in_scanword", m);
93    function->setCallingConv(CallingConv::C);
94    function->setAttributes(AttrSet);
95    function->addFnAttr(llvm::Attribute::AlwaysInline);
96   
97    Function::arg_iterator args = function->arg_begin();
98    Value * instance = &*(args++);
99    instance->setName("this");
100    Value * matches_input_parm = &*(args++);
101    matches_input_parm->setName("matches");
102    Value * record_breaks_input_parm = &*(args++);
103    record_breaks_input_parm->setName("breaks");
104    Value * scanwordPos = &*(args++);
105    scanwordPos->setName("scanwordPos");
106    Value * recordStart_input_parm = &*(args++);
107    recordStart_input_parm->setName("pendingLineStart");
108    Value * recordNum_input_parm = &*(args++);
109    recordNum_input_parm->setName("lineNum");
110   
111    Constant * matchProcessor = nullptr;
112    switch (mGrepType) {
113        case GrepType::Normal:
114            matchProcessor = m->getOrInsertFunction("wrapped_report_match", iBuilder->getVoidTy(), T, T, T, S, T, T, nullptr);
115            break;
116        case GrepType::NameExpression:
117            matchProcessor = m->getOrInsertFunction("insert_codepoints", iBuilder->getVoidTy(), T, T, T, S, nullptr);
118            break;
119        case GrepType::PropertyValue:
120            matchProcessor = m->getOrInsertFunction("insert_property_values", iBuilder->getVoidTy(), T, T, T, S, nullptr);
121            break;
122        default: llvm_unreachable("unknown grep type");
123    }
124    iBuilder->SetInsertPoint(BasicBlock::Create(ctxt, "entry", function,0));
125   
126    BasicBlock * entry_block = iBuilder->GetInsertBlock();
127    BasicBlock * matches_test_block = BasicBlock::Create(ctxt, "matches_test_block", function, 0);
128    BasicBlock * process_matches_loop_entry = BasicBlock::Create(ctxt, "process_matches_loop", function, 0);
129    BasicBlock * prior_breaks_block = BasicBlock::Create(ctxt, "prior_breaks_block", function, 0);
130    BasicBlock * loop_final_block = BasicBlock::Create(ctxt, "loop_final_block", function, 0);
131    BasicBlock * matches_done_block = BasicBlock::Create(ctxt, "matches_done_block", function, 0);
132    BasicBlock * remaining_breaks_block = BasicBlock::Create(ctxt, "remaining_breaks_block", function, 0);
133    BasicBlock * return_block = BasicBlock::Create(ctxt, "return_block", function, 0);
134   
135   
136    // The match scanner works with a loop involving four variables:
137    // (a) the bit stream scanword of matches marking the ends of selected records,
138    // (b) the bit stream scanword of record_breaks marking the ends of all records,
139    // (c) the integer lastRecordNum indicating the number of records processed so far,
140    // (d) the index lastRecordStart indicating the file position of the last record.
141    // We set up a loop structure, in which a set of 4 phi nodes initialize these
142    // variables from either the input to the scanner or the computed values within
143    // the loop body.
144   
145   
146    iBuilder->CreateBr(matches_test_block);
147   
148    // LOOP Test Block
149    iBuilder->SetInsertPoint(matches_test_block);
150    PHINode * matches_phi = iBuilder->CreatePHI(T, 2, "matches");
151    PHINode * record_breaks_phi = iBuilder->CreatePHI(T, 2, "record_breaks");
152    PHINode * recordNum_phi = iBuilder->CreatePHI(T, 2, "recordNum");
153    PHINode * recordStart_phi = iBuilder->CreatePHI(T, 2, "recordStart");
154    matches_phi->addIncoming(matches_input_parm, entry_block);
155    record_breaks_phi->addIncoming(record_breaks_input_parm, entry_block);
156    recordNum_phi->addIncoming(recordNum_input_parm, entry_block);
157    recordStart_phi->addIncoming(recordStart_input_parm, entry_block);
158    Value * have_matches_cond = iBuilder->CreateICmpNE(matches_phi, ConstantInt::get(T, 0));
159    iBuilder->CreateCondBr(have_matches_cond, process_matches_loop_entry, matches_done_block);
160   
161    // LOOP BODY
162    // The loop body is entered if we have more matches to process.
163    iBuilder->SetInsertPoint(process_matches_loop_entry);
164    Value * prior_breaks = iBuilder->CreateAnd(generateForwardZeroesMask(iBuilder, matches_phi), record_breaks_phi);
165    // Within the loop we have a conditional block that is executed if there are any prior
166    // record breaks.
167    Value * prior_breaks_cond = iBuilder->CreateICmpNE(prior_breaks, ConstantInt::get(T, 0));
168    iBuilder->CreateCondBr(prior_breaks_cond, prior_breaks_block, loop_final_block);
169   
170    // PRIOR_BREAKS_BLOCK
171    // If there are prior breaks, we count them and compute the record start position.
172    iBuilder->SetInsertPoint(prior_breaks_block);
173    Value * matchRecordNum = iBuilder->CreateAdd(generatePopcount(iBuilder, prior_breaks), recordNum_phi);
174    Value * reverseDistance = generateCountReverseZeroes(iBuilder, prior_breaks);
175    Value * width = ConstantInt::get(T, T->getBitWidth());
176    Value * matchRecordStart = iBuilder->CreateAdd(scanwordPos, iBuilder->CreateSub(width, reverseDistance));
177    iBuilder->CreateBr(loop_final_block);
178   
179    // LOOP FINAL BLOCK
180    // The prior breaks, if any have been counted.  Set up phi nodes for the recordNum
181    // and recortStart depending on whether the conditional execution of prior_breaks_block.
182    iBuilder->SetInsertPoint(loop_final_block);
183    PHINode * matchRecordNum_phi = iBuilder->CreatePHI(T, 2, "matchRecordNum");
184    PHINode * matchRecordStart_phi = iBuilder->CreatePHI(T, 2, "matchRecordStart");
185    matchRecordNum_phi->addIncoming(recordNum_phi, process_matches_loop_entry);
186    matchRecordNum_phi->addIncoming(matchRecordNum, prior_breaks_block);
187    matchRecordStart_phi->addIncoming(recordStart_phi, process_matches_loop_entry);
188    matchRecordStart_phi->addIncoming(matchRecordStart, prior_breaks_block);   
189    Value * matchRecordEnd = iBuilder->CreateAdd(scanwordPos, generateCountForwardZeroes(iBuilder, matches_phi));
190   
191
192    Value * fileBuf = getScalarField(instance, "FileBuf");
193    switch (mGrepType) {
194        case GrepType::Normal:
195        {
196            Value * fileSize = getScalarField(instance, "FileSize");
197            Value * fileIdx = getScalarField(instance, "FileIdx");
198            iBuilder->CreateCall(matchProcessor, std::vector<Value *>({matchRecordNum_phi, matchRecordStart_phi, matchRecordEnd, fileBuf, fileSize, fileIdx}));
199            break;
200        }
201        case GrepType::NameExpression:
202        case GrepType::PropertyValue:
203            iBuilder->CreateCall(matchProcessor, std::vector<Value *>({matchRecordNum_phi, matchRecordStart_phi, matchRecordEnd, fileBuf}));
204            break;
205        default: llvm_unreachable("unknown grep type");
206    }
207   
208    Value * remaining_matches = generateResetLowestBit(iBuilder, matches_phi);
209    Value * remaining_breaks = iBuilder->CreateXor(record_breaks_phi, prior_breaks);
210    matches_phi->addIncoming(remaining_matches, loop_final_block);
211    record_breaks_phi->addIncoming(remaining_breaks, loop_final_block);
212    recordNum_phi->addIncoming(matchRecordNum_phi, loop_final_block);
213    recordStart_phi->addIncoming(matchRecordStart_phi, loop_final_block);
214    iBuilder->CreateBr(matches_test_block);
215   
216   
217    // LOOP EXIT/MATCHES_DONE
218    iBuilder->SetInsertPoint(matches_done_block);
219    // When the matches are done, there may be additional record breaks remaining
220    Value * more_breaks_cond = iBuilder->CreateICmpNE(record_breaks_phi, ConstantInt::get(T, 0));
221    iBuilder->CreateCondBr(more_breaks_cond, remaining_breaks_block, return_block);
222   
223    // REMAINING_BREAKS_BLOCK: process remaining record breaks after all matches are processed
224    iBuilder->SetInsertPoint(remaining_breaks_block);
225    Value * break_count = generatePopcount(iBuilder, record_breaks_phi);
226    Value * final_record_num = iBuilder->CreateAdd(recordNum_phi, break_count);
227    Value * reverseZeroes = generateCountReverseZeroes(iBuilder, record_breaks_phi);
228    Value * pendingLineStart = iBuilder->CreateAdd(scanwordPos, iBuilder->CreateSub(width, reverseZeroes));
229    iBuilder->CreateBr(return_block);
230   
231    // RETURN block
232    iBuilder->SetInsertPoint(return_block);
233    PHINode * finalRecordCount_phi = iBuilder->CreatePHI(T, 2, "finalRecordCount");
234    PHINode * finalRecordStart_phi = iBuilder->CreatePHI(T, 2, "finalRecordStart");
235    finalRecordCount_phi->addIncoming(recordNum_phi, matches_done_block);
236    finalRecordCount_phi->addIncoming(final_record_num, remaining_breaks_block);
237    finalRecordStart_phi->addIncoming(recordStart_phi, matches_done_block);
238    finalRecordStart_phi->addIncoming(pendingLineStart, remaining_breaks_block);
239    Value * retVal = UndefValue::get(returnType);
240    retVal = iBuilder->CreateInsertValue(retVal, finalRecordStart_phi, 0);
241    retVal = iBuilder->CreateInsertValue(retVal, finalRecordCount_phi, 1);
242    iBuilder->CreateRet(retVal);
243   
244    return function;
245}
246
247ScanMatchKernel::ScanMatchKernel(IDISA::IDISA_Builder * iBuilder, GrepType grepType)
248: BlockOrientedKernel(iBuilder, "scanMatch",
249    {Binding{iBuilder->getStreamSetTy(2, 1), "matchResults"}},
250    {},
251    {Binding{iBuilder->getInt8PtrTy(), "FileBuf"}, Binding{iBuilder->getSizeTy(), "FileSize"}, Binding{iBuilder->getSizeTy(), "FileIdx"}},
252    {},
253    {Binding{iBuilder->getSizeTy(), "BlockNo"}, Binding{iBuilder->getSizeTy(), "LineStart"}, Binding{iBuilder->getSizeTy(), "LineNum"}})
254, mGrepType(grepType) {
255
256}
257
258}
Note: See TracBrowser for help on using the repository browser.