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

Last change on this file since 4939 was 4939, checked in by lindanl, 3 years ago

new version using the kernels.

File size: 13.9 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 "kernel.h"
7#include "scanmatchgen.h"
8#include <llvm/IR/Intrinsics.h>
9
10Value * generateForwardZeroesMask(IDISA::IDISA_Builder * iBuilder, Value * bits) {
11    Value * bits_minus1 = iBuilder->CreateSub(bits, ConstantInt::get(bits->getType(), 1));
12    return iBuilder->CreateAnd(bits_minus1, iBuilder->CreateNot(bits));
13}
14
15Value * generatePopcount(IDISA::IDISA_Builder * iBuilder, Value * bits) {
16    Value * ctpopFunc = Intrinsic::getDeclaration(iBuilder->getModule(), Intrinsic::ctpop, bits->getType());
17    return iBuilder->CreateCall(ctpopFunc, std::vector<Value *>({bits}));
18}
19
20Value * generateCountForwardZeroes(IDISA::IDISA_Builder * iBuilder, Value * bits) {
21    Value * cttzFunc = Intrinsic::getDeclaration(iBuilder->getModule(), Intrinsic::cttz, bits->getType());
22    return iBuilder->CreateCall(cttzFunc, std::vector<Value *>({bits, ConstantInt::get(iBuilder->getInt1Ty(), 0)}));
23}
24
25Value * generateCountReverseZeroes(IDISA::IDISA_Builder * iBuilder, Value * bits) {
26    Value * ctlzFunc = Intrinsic::getDeclaration(iBuilder->getModule(), Intrinsic::ctlz, bits->getType());
27    return iBuilder->CreateCall(ctlzFunc, std::vector<Value *>({bits, ConstantInt::get(iBuilder->getInt1Ty(), 0)}));
28}
29
30Value * generateResetLowestBit(IDISA::IDISA_Builder * iBuilder, Value * bits) {
31    Value * bits_minus1 = iBuilder->CreateSub(bits, ConstantInt::get(bits->getType(), 1));
32    return iBuilder->CreateAnd(bits_minus1, bits);
33}
34       
35       
36void generateScanWordRoutine(Module * m, IDISA::IDISA_Builder * iBuilder, int scanwordBitWidth, Type * kernelStuctType, bool isNameExpression) {
37    LLVMContext & ctxt = m->getContext();
38    Type * T = iBuilder->getIntNTy(scanwordBitWidth);   
39    Type * S = PointerType::get(iBuilder->getIntNTy(8), 0);
40    Type * returnType = StructType::get(ctxt, std::vector<Type *>({T, T}));
41    FunctionType * functionType = FunctionType::get(returnType, std::vector<Type *>({kernelStuctType, T, T, T, T, T}), false);
42    Function * sFunction;
43       
44    SmallVector<AttributeSet, 6> Attrs;
45    Attrs.push_back(AttributeSet::get(ctxt, ~0U, std::vector<Attribute::AttrKind>({ Attribute::NoUnwind, Attribute::UWTable })));
46    Attrs.push_back(AttributeSet::get(ctxt, 1, std::vector<Attribute::AttrKind>({})));
47    Attrs.push_back(AttributeSet::get(ctxt, 2, std::vector<Attribute::AttrKind>({})));
48    Attrs.push_back(AttributeSet::get(ctxt, 3, std::vector<Attribute::AttrKind>({})));
49    Attrs.push_back(AttributeSet::get(ctxt, 4, std::vector<Attribute::AttrKind>({})));
50    Attrs.push_back(AttributeSet::get(ctxt, 5, std::vector<Attribute::AttrKind>({})));
51    AttributeSet AttrSet = AttributeSet::get(ctxt, Attrs);
52   
53    sFunction = Function::Create(functionType, GlobalValue::ExternalLinkage, "scan_matches_in_scanword", m);
54    sFunction->setCallingConv(CallingConv::C);
55    sFunction->setAttributes(AttrSet);
56       
57    Function::arg_iterator args = sFunction->arg_begin();
58    Value * this_input_parm = args++;
59    this_input_parm->setName("this");
60    Value * matches_input_parm = args++;
61    matches_input_parm->setName("matches");
62    Value * record_breaks_input_parm = args++;
63    record_breaks_input_parm->setName("breaks");
64    Value * scanwordPos = args++;
65    scanwordPos->setName("scanwordPos");
66    Value * recordStart_input_parm = args++;
67    recordStart_input_parm->setName("pendingLineStart");
68    Value * recordNum_input_parm = args++;
69    recordNum_input_parm->setName("lineNum");
70    Constant * matchProcessor;
71    if(isNameExpression)
72        matchProcessor = m->getOrInsertFunction("insert_codepoints", Type::getVoidTy(ctxt), T, T, T, S, nullptr);
73    else
74        matchProcessor = m->getOrInsertFunction("wrapped_report_match", Type::getVoidTy(ctxt), T, T, T, S, T, S, nullptr);
75   
76    iBuilder->SetInsertPoint(BasicBlock::Create(ctxt, "entry", sFunction,0));
77
78    BasicBlock * entry_block = iBuilder->GetInsertBlock();
79    BasicBlock * matches_test_block = BasicBlock::Create(ctxt, "matches_test_block", sFunction, 0);
80    BasicBlock * process_matches_loop_entry = BasicBlock::Create(ctxt, "process_matches_loop", sFunction, 0);
81    BasicBlock * prior_breaks_block = BasicBlock::Create(ctxt, "prior_breaks_block", sFunction, 0);
82    BasicBlock * loop_final_block = BasicBlock::Create(ctxt, "loop_final_block", sFunction, 0);
83    BasicBlock * matches_done_block = BasicBlock::Create(ctxt, "matches_done_block", sFunction, 0);
84    BasicBlock * remaining_breaks_block = BasicBlock::Create(ctxt, "remaining_breaks_block", sFunction, 0);
85    BasicBlock * return_block = BasicBlock::Create(ctxt, "return_block", sFunction, 0);
86       
87       
88    // The match scanner works with a loop involving four variables:
89    // (a) the bit stream scanword of matches marking the ends of selected records,
90    // (b) the bit stream scanword of record_breaks marking the ends of all records,
91    // (c) the integer lastRecordNum indicating the number of records processed so far,
92    // (d) the index lastRecordStart indicating the file position of the last record.
93    // We set up a loop structure, in which a set of 4 phi nodes initialize these
94    // variables from either the input to the scanner or the computed values within
95    // the loop body.
96
97   
98    iBuilder->CreateBr(matches_test_block);
99
100    // LOOP Test Block
101    iBuilder->SetInsertPoint(matches_test_block);
102    PHINode * matches_phi = iBuilder->CreatePHI(T, 2, "matches");
103    PHINode * record_breaks_phi = iBuilder->CreatePHI(T, 2, "record_breaks");
104    PHINode * recordNum_phi = iBuilder->CreatePHI(T, 2, "recordNum");
105    PHINode * recordStart_phi = iBuilder->CreatePHI(T, 2, "recordStart");
106    matches_phi->addIncoming(matches_input_parm, entry_block);
107    record_breaks_phi->addIncoming(record_breaks_input_parm, entry_block);
108    recordNum_phi->addIncoming(recordNum_input_parm, entry_block);
109    recordStart_phi->addIncoming(recordStart_input_parm, entry_block);
110    Value * have_matches_cond = iBuilder->CreateICmpNE(matches_phi, ConstantInt::get(T, 0));
111    iBuilder->CreateCondBr(have_matches_cond, process_matches_loop_entry, matches_done_block);
112   
113    // LOOP BODY
114    // The loop body is entered if we have more matches to process.
115    iBuilder->SetInsertPoint(process_matches_loop_entry);
116    Value * prior_breaks = iBuilder->CreateAnd(generateForwardZeroesMask(iBuilder, matches_phi), record_breaks_phi);
117    // Within the loop we have a conditional block that is executed if there are any prior
118    // record breaks.
119    Value * prior_breaks_cond = iBuilder->CreateICmpNE(prior_breaks, ConstantInt::get(T, 0));
120    iBuilder->CreateCondBr(prior_breaks_cond, prior_breaks_block, loop_final_block);
121
122    // PRIOR_BREAKS_BLOCK
123    // If there are prior breaks, we count them and compute the record start position.
124    iBuilder->SetInsertPoint(prior_breaks_block);
125    Value * matchRecordNum = iBuilder->CreateAdd(generatePopcount(iBuilder, prior_breaks), recordNum_phi);
126    Value * reverseDistance = generateCountReverseZeroes(iBuilder, prior_breaks);
127    Value * width = ConstantInt::get(T, scanwordBitWidth);
128    Value * matchRecordStart = iBuilder->CreateAdd(scanwordPos, iBuilder->CreateSub(width, reverseDistance));
129    iBuilder->CreateBr(loop_final_block);
130   
131    // LOOP FINAL BLOCK
132    // The prior breaks, if any have been counted.  Set up phi nodes for the recordNum
133    // and recortStart depending on whether the conditional execution of prior_breaks_block.
134    iBuilder->SetInsertPoint(loop_final_block);
135    PHINode * matchRecordNum_phi = iBuilder->CreatePHI(T, 2, "matchRecordNum");
136    PHINode * matchRecordStart_phi = iBuilder->CreatePHI(T, 2, "matchRecordStart");
137    matchRecordNum_phi->addIncoming(recordNum_phi, process_matches_loop_entry);
138    matchRecordNum_phi->addIncoming(matchRecordNum, prior_breaks_block);
139    matchRecordStart_phi->addIncoming(recordStart_phi, process_matches_loop_entry);
140    matchRecordStart_phi->addIncoming(matchRecordStart, prior_breaks_block);
141    Value * matchRecordEnd = iBuilder->CreateAdd(scanwordPos, generateCountForwardZeroes(iBuilder, matches_phi));
142
143    Value* filebuf_gep = iBuilder->CreateGEP(this_input_parm, {iBuilder->getInt64(0), iBuilder->getInt32(0), iBuilder->getInt32(7)});
144    Value* filebufptr = iBuilder->CreateLoad(filebuf_gep, "filebuf");
145
146    Value* filesize_gep = iBuilder->CreateGEP(this_input_parm, {iBuilder->getInt64(0), iBuilder->getInt32(0), iBuilder->getInt32(8)});
147    Value* filesize = iBuilder->CreateLoad(filesize_gep, "filensize");
148
149    Value* filename_gep = iBuilder->CreateGEP(this_input_parm, {iBuilder->getInt64(0), iBuilder->getInt32(0), iBuilder->getInt32(9)});
150    Value* filenameptr = iBuilder->CreateLoad(filename_gep, "filename");
151
152    if(isNameExpression)
153        iBuilder->CreateCall(matchProcessor, std::vector<Value *>({matchRecordNum_phi, matchRecordStart_phi, matchRecordEnd, filebufptr}));
154    else
155        iBuilder->CreateCall(matchProcessor, std::vector<Value *>({matchRecordNum_phi, matchRecordStart_phi, matchRecordEnd, filebufptr, filesize, filenameptr}));
156    Value * remaining_matches = generateResetLowestBit(iBuilder, matches_phi);
157    Value * remaining_breaks = iBuilder->CreateXor(record_breaks_phi, prior_breaks);
158    matches_phi->addIncoming(remaining_matches, loop_final_block);
159    record_breaks_phi->addIncoming(remaining_breaks, loop_final_block);
160    recordNum_phi->addIncoming(matchRecordNum_phi, loop_final_block);
161    recordStart_phi->addIncoming(matchRecordStart_phi, loop_final_block);
162    iBuilder->CreateBr(matches_test_block);
163   
164   
165    // LOOP EXIT/MATCHES_DONE
166    iBuilder->SetInsertPoint(matches_done_block);
167    // When the matches are done, there may be additional record breaks remaining
168    Value * more_breaks_cond = iBuilder->CreateICmpNE(record_breaks_phi, ConstantInt::get(T, 0));
169    iBuilder->CreateCondBr(more_breaks_cond, remaining_breaks_block, return_block);
170   
171    // REMAINING_BREAKS_BLOCK: process remaining record breaks after all matches are processed
172    iBuilder->SetInsertPoint(remaining_breaks_block);
173    Value * break_count = generatePopcount(iBuilder, record_breaks_phi);
174    Value * final_record_num = iBuilder->CreateAdd(recordNum_phi, break_count);
175    Value * reverseZeroes = generateCountReverseZeroes(iBuilder, record_breaks_phi);
176    Value * pendingLineStart = iBuilder->CreateAdd(scanwordPos, iBuilder->CreateSub(width, reverseZeroes));
177    iBuilder->CreateBr(return_block);
178   
179    // RETURN block
180    iBuilder->SetInsertPoint(return_block);
181    PHINode * finalRecordCount_phi = iBuilder->CreatePHI(T, 2, "finalRecordCount");
182    PHINode * finalRecordStart_phi = iBuilder->CreatePHI(T, 2, "finalRecordStart");
183    finalRecordCount_phi->addIncoming(recordNum_phi, matches_done_block);
184    finalRecordCount_phi->addIncoming(final_record_num, remaining_breaks_block);
185    finalRecordStart_phi->addIncoming(recordStart_phi, matches_done_block);
186    finalRecordStart_phi->addIncoming(pendingLineStart, remaining_breaks_block);
187    Value * retVal = UndefValue::get(returnType);
188    retVal = iBuilder->CreateInsertValue(retVal, finalRecordStart_phi, 0);
189    retVal = iBuilder->CreateInsertValue(retVal, finalRecordCount_phi, 1);
190    iBuilder->CreateRet(retVal);
191   
192}
193
194
195void generateScanMatch(Module * m, IDISA::IDISA_Builder * iBuilder, int scanwordBitWidth, KernelBuilder * kBuilder, bool isNameExpression){
196   
197   
198    Type * T = iBuilder->getIntNTy(scanwordBitWidth);
199    Type * S = PointerType::get(iBuilder->getIntNTy(8), 0);
200    int fieldCount = iBuilder->getBitBlockWidth()/scanwordBitWidth;
201    Type * scanwordVectorType =  VectorType::get(T, fieldCount);
202
203    kBuilder->addKernelInputStream(1, "matches");
204    kBuilder->addKernelInputStream(1, "breaks");
205    //use index
206    int blockPosIdx = kBuilder->extendKernelInternalStateType(T);
207    int lineStartIdx = kBuilder->extendKernelInternalStateType(T);
208    int lineNumIdx = kBuilder->extendKernelInternalStateType(T);
209    kBuilder->extendKernelInternalStateType(S);
210    kBuilder->extendKernelInternalStateType(T);
211    kBuilder->extendKernelInternalStateType(S);
212
213    int segBlocks = kBuilder->getSegmentBlocks();
214
215    kBuilder->PrepareDoBlockFunction();
216
217    Type * kernelStuctType = PointerType::get(kBuilder->getKernelStructType(), 0);
218    generateScanWordRoutine(m, iBuilder, scanwordBitWidth, kernelStuctType, isNameExpression);
219
220    struct Inputs inputs = kBuilder->openDoBlock();
221    struct Outputs outputs;   
222    Value * kernelStuctParam = kBuilder->getKernelStructParam();
223   
224    Value * scanwordPos = kBuilder->getKernelInternalState(blockPosIdx);
225    Value * recordStart = kBuilder->getKernelInternalState(lineStartIdx);
226    Value * recordNum = kBuilder->getKernelInternalState(lineNumIdx);
227    Value * wordResult = nullptr;
228
229    Function * wordScanFcn = m->getFunction("scan_matches_in_scanword");
230    for(int j=0; j<segBlocks; j++){
231        Value * matchWordVector = iBuilder->CreateBitCast(inputs.streams[j][0], scanwordVectorType);
232        Value * breakWordVector = iBuilder->CreateBitCast(inputs.streams[j][1], scanwordVectorType);
233        for(int i=0; i<segBlocks*iBuilder->getBitBlockWidth()/scanwordBitWidth; i++){
234
235            Value * matchWord = iBuilder->CreateExtractElement(matchWordVector, ConstantInt::get(T, i));
236            Value * recordBreaksWord = iBuilder->CreateExtractElement(breakWordVector, ConstantInt::get(T, i));
237            wordResult = iBuilder->CreateCall(wordScanFcn, std::vector<Value *>({kernelStuctParam, matchWord, recordBreaksWord, scanwordPos, recordStart, recordNum}));
238            scanwordPos = iBuilder->CreateAdd(scanwordPos, ConstantInt::get(T, scanwordBitWidth));
239            recordStart = iBuilder->CreateExtractValue(wordResult, std::vector<unsigned>({0}));
240            recordNum = iBuilder->CreateExtractValue(wordResult, std::vector<unsigned>({1}));
241        }
242    }
243
244    kBuilder->changeKernelInternalState(blockPosIdx, scanwordPos);
245    kBuilder->changeKernelInternalState(lineStartIdx, recordStart);
246    kBuilder->changeKernelInternalState(lineNumIdx, recordNum);
247
248    kBuilder->closeDoBlock(outputs);
249
250    kBuilder->finalizeMethods();
251}
252
253
254
Note: See TracBrowser for help on using the repository browser.