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

Last change on this file since 5055 was 5055, checked in by cameron, 3 years ago

scanmatch kernel using new infrastructure

File size: 25.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#include <IDISA/idisa_builder.h>
10#include <llvm/Support/raw_os_ostream.h>
11
12using namespace llvm;
13
14namespace kernel {
15
16Value * generateForwardZeroesMask(IDISA::IDISA_Builder * iBuilder, Value * bits) {
17    Value * bits_minus1 = iBuilder->CreateSub(bits, ConstantInt::get(bits->getType(), 1));
18    return iBuilder->CreateAnd(bits_minus1, iBuilder->CreateNot(bits));
19}
20
21Value * generatePopcount(IDISA::IDISA_Builder * iBuilder, Value * bits) {
22    Value * ctpopFunc = Intrinsic::getDeclaration(iBuilder->getModule(), Intrinsic::ctpop, bits->getType());
23    return iBuilder->CreateCall(ctpopFunc, std::vector<Value *>({bits}));
24}
25
26Value * generateCountForwardZeroes(IDISA::IDISA_Builder * iBuilder, Value * bits) {
27    Value * cttzFunc = Intrinsic::getDeclaration(iBuilder->getModule(), Intrinsic::cttz, bits->getType());
28    return iBuilder->CreateCall(cttzFunc, std::vector<Value *>({bits, ConstantInt::get(iBuilder->getInt1Ty(), 0)}));
29}
30
31Value * generateCountReverseZeroes(IDISA::IDISA_Builder * iBuilder, Value * bits) {
32    Value * ctlzFunc = Intrinsic::getDeclaration(iBuilder->getModule(), Intrinsic::ctlz, bits->getType());
33    return iBuilder->CreateCall(ctlzFunc, std::vector<Value *>({bits, ConstantInt::get(iBuilder->getInt1Ty(), 0)}));
34}
35
36Value * generateResetLowestBit(IDISA::IDISA_Builder * iBuilder, Value * bits) {
37    Value * bits_minus1 = iBuilder->CreateSub(bits, ConstantInt::get(bits->getType(), 1));
38    return iBuilder->CreateAnd(bits_minus1, bits);
39}
40
41Function * generateScanWordRoutine(Module * m, IDISA::IDISA_Builder * iBuilder, unsigned scanwordBitWidth, KernelBuilder * const kBuilder, bool isNameExpression) {
42
43    Function * function = m->getFunction("scan_matches_in_scanword");
44    if (LLVM_UNLIKELY(function != nullptr)) {
45        return function;
46    }
47
48    LLVMContext & ctxt = m->getContext();
49    Type * T = iBuilder->getIntNTy(scanwordBitWidth);
50    Type * S = PointerType::get(iBuilder->getIntNTy(8), 0);
51    Type * returnType = StructType::get(ctxt, std::vector<Type *>({T, T}));
52    FunctionType * functionType = FunctionType::get(returnType, std::vector<Type *>({PointerType::get(kBuilder->getKernelStateType(), 0), T, T, T, T, T}), false);
53
54    SmallVector<AttributeSet, 6> Attrs;
55    Attrs.push_back(AttributeSet::get(ctxt, ~0U, std::vector<Attribute::AttrKind>({ Attribute::NoUnwind, Attribute::UWTable })));
56    Attrs.push_back(AttributeSet::get(ctxt, 1, std::vector<Attribute::AttrKind>({})));
57    Attrs.push_back(AttributeSet::get(ctxt, 2, std::vector<Attribute::AttrKind>({})));
58    Attrs.push_back(AttributeSet::get(ctxt, 3, std::vector<Attribute::AttrKind>({})));
59    Attrs.push_back(AttributeSet::get(ctxt, 4, std::vector<Attribute::AttrKind>({})));
60    Attrs.push_back(AttributeSet::get(ctxt, 5, std::vector<Attribute::AttrKind>({})));
61    AttributeSet AttrSet = AttributeSet::get(ctxt, Attrs);
62
63    function = Function::Create(functionType, GlobalValue::ExternalLinkage, "scan_matches_in_scanword", m);
64    function->setCallingConv(CallingConv::C);
65    function->setAttributes(AttrSet);
66    function->addFnAttr(llvm::Attribute::AlwaysInline);
67
68    Function::arg_iterator args = function->arg_begin();
69    Value * instance = &*(args++);
70    instance->setName("this");
71    Value * matches_input_parm = &*(args++);
72    matches_input_parm->setName("matches");
73    Value * record_breaks_input_parm = &*(args++);
74    record_breaks_input_parm->setName("breaks");
75    Value * scanwordPos = &*(args++);
76    scanwordPos->setName("scanwordPos");
77    Value * recordStart_input_parm = &*(args++);
78    recordStart_input_parm->setName("pendingLineStart");
79    Value * recordNum_input_parm = &*(args++);
80    recordNum_input_parm->setName("lineNum");
81
82    Constant * matchProcessor;
83    if (isNameExpression) {
84        matchProcessor = m->getOrInsertFunction("insert_codepoints", Type::getVoidTy(ctxt), T, T, T, S, nullptr);
85    } else {
86        matchProcessor = m->getOrInsertFunction("wrapped_report_match", Type::getVoidTy(ctxt), T, T, T, S, T, T, nullptr);
87    }
88    iBuilder->SetInsertPoint(BasicBlock::Create(ctxt, "entry", function,0));
89
90    BasicBlock * entry_block = iBuilder->GetInsertBlock();
91    BasicBlock * matches_test_block = BasicBlock::Create(ctxt, "matches_test_block", function, 0);
92    BasicBlock * process_matches_loop_entry = BasicBlock::Create(ctxt, "process_matches_loop", function, 0);
93    BasicBlock * prior_breaks_block = BasicBlock::Create(ctxt, "prior_breaks_block", function, 0);
94    BasicBlock * loop_final_block = BasicBlock::Create(ctxt, "loop_final_block", function, 0);
95    BasicBlock * matches_done_block = BasicBlock::Create(ctxt, "matches_done_block", function, 0);
96    BasicBlock * remaining_breaks_block = BasicBlock::Create(ctxt, "remaining_breaks_block", function, 0);
97    BasicBlock * return_block = BasicBlock::Create(ctxt, "return_block", function, 0);
98
99
100    // The match scanner works with a loop involving four variables:
101    // (a) the bit stream scanword of matches marking the ends of selected records,
102    // (b) the bit stream scanword of record_breaks marking the ends of all records,
103    // (c) the integer lastRecordNum indicating the number of records processed so far,
104    // (d) the index lastRecordStart indicating the file position of the last record.
105    // We set up a loop structure, in which a set of 4 phi nodes initialize these
106    // variables from either the input to the scanner or the computed values within
107    // the loop body.
108
109
110    iBuilder->CreateBr(matches_test_block);
111
112    // LOOP Test Block
113    iBuilder->SetInsertPoint(matches_test_block);
114    PHINode * matches_phi = iBuilder->CreatePHI(T, 2, "matches");
115    PHINode * record_breaks_phi = iBuilder->CreatePHI(T, 2, "record_breaks");
116    PHINode * recordNum_phi = iBuilder->CreatePHI(T, 2, "recordNum");
117    PHINode * recordStart_phi = iBuilder->CreatePHI(T, 2, "recordStart");
118    matches_phi->addIncoming(matches_input_parm, entry_block);
119    record_breaks_phi->addIncoming(record_breaks_input_parm, entry_block);
120    recordNum_phi->addIncoming(recordNum_input_parm, entry_block);
121    recordStart_phi->addIncoming(recordStart_input_parm, entry_block);
122    Value * have_matches_cond = iBuilder->CreateICmpNE(matches_phi, ConstantInt::get(T, 0));
123    iBuilder->CreateCondBr(have_matches_cond, process_matches_loop_entry, matches_done_block);
124
125    // LOOP BODY
126    // The loop body is entered if we have more matches to process.
127    iBuilder->SetInsertPoint(process_matches_loop_entry);
128    Value * prior_breaks = iBuilder->CreateAnd(generateForwardZeroesMask(iBuilder, matches_phi), record_breaks_phi);
129    // Within the loop we have a conditional block that is executed if there are any prior
130    // record breaks.
131    Value * prior_breaks_cond = iBuilder->CreateICmpNE(prior_breaks, ConstantInt::get(T, 0));
132    iBuilder->CreateCondBr(prior_breaks_cond, prior_breaks_block, loop_final_block);
133
134    // PRIOR_BREAKS_BLOCK
135    // If there are prior breaks, we count them and compute the record start position.
136    iBuilder->SetInsertPoint(prior_breaks_block);
137    Value * matchRecordNum = iBuilder->CreateAdd(generatePopcount(iBuilder, prior_breaks), recordNum_phi);
138    Value * reverseDistance = generateCountReverseZeroes(iBuilder, prior_breaks);
139    Value * width = ConstantInt::get(T, scanwordBitWidth);
140    Value * matchRecordStart = iBuilder->CreateAdd(scanwordPos, iBuilder->CreateSub(width, reverseDistance));
141    iBuilder->CreateBr(loop_final_block);
142
143    // LOOP FINAL BLOCK
144    // The prior breaks, if any have been counted.  Set up phi nodes for the recordNum
145    // and recortStart depending on whether the conditional execution of prior_breaks_block.
146    iBuilder->SetInsertPoint(loop_final_block);
147    PHINode * matchRecordNum_phi = iBuilder->CreatePHI(T, 2, "matchRecordNum");
148    PHINode * matchRecordStart_phi = iBuilder->CreatePHI(T, 2, "matchRecordStart");
149    matchRecordNum_phi->addIncoming(recordNum_phi, process_matches_loop_entry);
150    matchRecordNum_phi->addIncoming(matchRecordNum, prior_breaks_block);
151    matchRecordStart_phi->addIncoming(recordStart_phi, process_matches_loop_entry);
152    matchRecordStart_phi->addIncoming(matchRecordStart, prior_breaks_block);   
153    Value * matchRecordEnd = iBuilder->CreateAdd(scanwordPos, generateCountForwardZeroes(iBuilder, matches_phi));
154
155    Value * fileBuf = iBuilder->CreateLoad(kBuilder->getInternalStateInternal(instance, "FileBuf"));
156    if (isNameExpression) {
157        iBuilder->CreateCall(matchProcessor, std::vector<Value *>({matchRecordNum_phi, matchRecordStart_phi, matchRecordEnd, fileBuf}));
158    } else {
159        Value * fileSize = iBuilder->CreateLoad(kBuilder->getInternalStateInternal(instance, "FileSize"));
160        Value * fileIdx = iBuilder->CreateLoad(kBuilder->getInternalStateInternal(instance, "FileIdx"));
161        iBuilder->CreateCall(matchProcessor, std::vector<Value *>({matchRecordNum_phi, matchRecordStart_phi, matchRecordEnd, fileBuf, fileSize, fileIdx}));
162    }
163
164    Value * remaining_matches = generateResetLowestBit(iBuilder, matches_phi);
165    Value * remaining_breaks = iBuilder->CreateXor(record_breaks_phi, prior_breaks);
166    matches_phi->addIncoming(remaining_matches, loop_final_block);
167    record_breaks_phi->addIncoming(remaining_breaks, loop_final_block);
168    recordNum_phi->addIncoming(matchRecordNum_phi, loop_final_block);
169    recordStart_phi->addIncoming(matchRecordStart_phi, loop_final_block);
170    iBuilder->CreateBr(matches_test_block);
171
172
173    // LOOP EXIT/MATCHES_DONE
174    iBuilder->SetInsertPoint(matches_done_block);
175    // When the matches are done, there may be additional record breaks remaining
176    Value * more_breaks_cond = iBuilder->CreateICmpNE(record_breaks_phi, ConstantInt::get(T, 0));
177    iBuilder->CreateCondBr(more_breaks_cond, remaining_breaks_block, return_block);
178
179    // REMAINING_BREAKS_BLOCK: process remaining record breaks after all matches are processed
180    iBuilder->SetInsertPoint(remaining_breaks_block);
181    Value * break_count = generatePopcount(iBuilder, record_breaks_phi);
182    Value * final_record_num = iBuilder->CreateAdd(recordNum_phi, break_count);
183    Value * reverseZeroes = generateCountReverseZeroes(iBuilder, record_breaks_phi);
184    Value * pendingLineStart = iBuilder->CreateAdd(scanwordPos, iBuilder->CreateSub(width, reverseZeroes));
185    iBuilder->CreateBr(return_block);
186
187    // RETURN block
188    iBuilder->SetInsertPoint(return_block);
189    PHINode * finalRecordCount_phi = iBuilder->CreatePHI(T, 2, "finalRecordCount");
190    PHINode * finalRecordStart_phi = iBuilder->CreatePHI(T, 2, "finalRecordStart");
191    finalRecordCount_phi->addIncoming(recordNum_phi, matches_done_block);
192    finalRecordCount_phi->addIncoming(final_record_num, remaining_breaks_block);
193    finalRecordStart_phi->addIncoming(recordStart_phi, matches_done_block);
194    finalRecordStart_phi->addIncoming(pendingLineStart, remaining_breaks_block);
195    Value * retVal = UndefValue::get(returnType);
196    retVal = iBuilder->CreateInsertValue(retVal, finalRecordStart_phi, 0);
197    retVal = iBuilder->CreateInsertValue(retVal, finalRecordCount_phi, 1);
198    iBuilder->CreateRet(retVal);
199
200    return function;
201}
202
203
204void generateScanMatch(Module * m, IDISA::IDISA_Builder * iBuilder, unsigned scanWordBitWidth, KernelBuilder * kBuilder, bool isNameExpression) {
205   
206    Type * T = iBuilder->getIntNTy(scanWordBitWidth);
207    Type * S = PointerType::get(iBuilder->getIntNTy(8), 0);
208    kBuilder->setInstanceParameters({{S, "FileBuf"}, {T, "FileSize"}, {T, "FileIdx"}});
209
210    const unsigned fieldCount = iBuilder->getBitBlockWidth() / scanWordBitWidth;
211    Type * scanwordVectorType =  VectorType::get(T, fieldCount);
212
213    kBuilder->addInputStream(1, "matches");
214    kBuilder->addInputStream(1, "breaks");
215    //use index
216    const unsigned lineStart = kBuilder->addInternalState(T, "LineStart");
217    const unsigned lineNum = kBuilder->addInternalState(T, "LineNum");
218   
219    kBuilder->createInitMethod();
220    Function * function = kBuilder->prepareFunction();
221
222
223    Function * scanWordFunction = generateScanWordRoutine(m, iBuilder, scanWordBitWidth, kBuilder, isNameExpression);
224   
225    iBuilder->SetInsertPoint(&function->getEntryBlock());
226
227    Value * kernelStuctParam = kBuilder->getKernelState();
228
229    Value * scanwordPos = iBuilder->CreateLoad(kBuilder->getInternalState("BlockNo"));
230    scanwordPos = iBuilder->CreateMul(scanwordPos, ConstantInt::get(scanwordPos->getType(), iBuilder->getBitBlockWidth()));
231   
232    Value * recordStart = iBuilder->CreateBlockAlignedLoad(kBuilder->getInternalState(lineStart));
233    Value * recordNum = iBuilder->CreateBlockAlignedLoad(kBuilder->getInternalState(lineNum));
234    Value * matchWordVector = iBuilder->CreateBitCast(iBuilder->CreateBlockAlignedLoad(kBuilder->getInputStream(0)), scanwordVectorType);
235    Value * breakWordVector = iBuilder->CreateBitCast(iBuilder->CreateBlockAlignedLoad(kBuilder->getInputStream(1)), scanwordVectorType);
236    for(unsigned i = 0; i < fieldCount; ++i){
237        Value * matchWord = iBuilder->CreateExtractElement(matchWordVector, ConstantInt::get(T, i));
238        Value * recordBreaksWord = iBuilder->CreateExtractElement(breakWordVector, ConstantInt::get(T, i));
239        Value * wordResult = iBuilder->CreateCall(scanWordFunction, {kernelStuctParam, matchWord, recordBreaksWord, scanwordPos, recordStart, recordNum});
240        scanwordPos = iBuilder->CreateAdd(scanwordPos, ConstantInt::get(T, scanWordBitWidth));
241        recordStart = iBuilder->CreateExtractValue(wordResult, std::vector<unsigned>({0}));
242        recordNum = iBuilder->CreateExtractValue(wordResult, std::vector<unsigned>({1}));
243    }
244    kBuilder->setInternalState(lineStart, recordStart);
245    kBuilder->setInternalState(lineNum, recordNum);
246    kBuilder->finalize();
247
248}
249       
250std::unique_ptr<llvm::Module> scanMatchKernel::createKernelModule() {
251    std::unique_ptr<llvm::Module> theModule = KernelInterface::createKernelModule();
252   
253    Function * scanWordFunction = generateScanWordRoutine(theModule.get());
254    const unsigned fieldCount = iBuilder->getBitBlockWidth() / mScanwordBitWidth;
255    Type * T = iBuilder->getIntNTy(mScanwordBitWidth);
256    Type * scanwordVectorType =  VectorType::get(T, fieldCount);
257
258    Function * doBlockFunction = theModule.get()->getFunction(mKernelName + "_DoBlock");
259
260    iBuilder->SetInsertPoint(BasicBlock::Create(iBuilder->getContext(), "entry", doBlockFunction, 0));
261    Value * kernelStuctParam = getParameter(doBlockFunction, "self");
262    Value * scanwordPos = getScalarField(kernelStuctParam, "BlockNo");
263    scanwordPos = iBuilder->CreateMul(scanwordPos, ConstantInt::get(scanwordPos->getType(), iBuilder->getBitBlockWidth()));
264   
265    Value * recordStart = getScalarField(kernelStuctParam, "LineStart");
266    Value * recordNum = getScalarField(kernelStuctParam, "LineNum");
267    Value * matchResultsPtr = getParameter(doBlockFunction, "matchResults");
268    Value * matches = iBuilder->CreateBlockAlignedLoad(matchResultsPtr, {iBuilder->getInt32(0), iBuilder->getInt32(0)});
269    Value * linebreaks = iBuilder->CreateBlockAlignedLoad(matchResultsPtr, {iBuilder->getInt32(0), iBuilder->getInt32(1)});
270    Value * matchWordVector = iBuilder->CreateBitCast(matches, scanwordVectorType);
271    Value * breakWordVector = iBuilder->CreateBitCast(linebreaks, scanwordVectorType);
272    for(unsigned i = 0; i < fieldCount; ++i){
273        Value * matchWord = iBuilder->CreateExtractElement(matchWordVector, ConstantInt::get(T, i));
274        Value * recordBreaksWord = iBuilder->CreateExtractElement(breakWordVector, ConstantInt::get(T, i));
275        Value * wordResult = iBuilder->CreateCall(scanWordFunction, {kernelStuctParam, matchWord, recordBreaksWord, scanwordPos, recordStart, recordNum});
276        scanwordPos = iBuilder->CreateAdd(scanwordPos, ConstantInt::get(T, mScanwordBitWidth));
277        recordStart = iBuilder->CreateExtractValue(wordResult, std::vector<unsigned>({0}));
278        recordNum = iBuilder->CreateExtractValue(wordResult, std::vector<unsigned>({1}));
279    }
280    setScalarField(kernelStuctParam, "LineStart", recordStart);
281    setScalarField(kernelStuctParam, "LineNum", recordNum);
282    setScalarField(kernelStuctParam, "BlockNo", iBuilder->CreateAdd(getScalarField(kernelStuctParam, "BlockNo"), iBuilder->getInt64(1)));
283    iBuilder -> CreateRetVoid();
284   
285    // scanMatch FinalBlock function simply dispatches to the DoBlock function
286    Function * finalBlockFunction = theModule.get()->getFunction(mKernelName + "_FinalBlock");
287    iBuilder->SetInsertPoint(BasicBlock::Create(iBuilder->getContext(), "fb_entry", finalBlockFunction, 0));
288    Value * self = getParameter(finalBlockFunction, "self");
289    Value * matchResults = getParameter(finalBlockFunction, "matchResults");
290    iBuilder->CreateCall(doBlockFunction, {self, matchResults});
291    iBuilder->CreateRetVoid();
292    //
293    return theModule;
294}
295
296   
297Function * scanMatchKernel::generateScanWordRoutine(Module * m) {
298    Function * function = m->getFunction("scan_matches_in_scanword");
299    if (LLVM_UNLIKELY(function != nullptr)) {
300        return function;
301    }
302   
303    LLVMContext & ctxt = m->getContext();
304    Type * T = iBuilder->getIntNTy(mScanwordBitWidth);
305    Type * S = PointerType::get(iBuilder->getIntNTy(8), 0);
306    Type * returnType = StructType::get(ctxt, std::vector<Type *>({T, T}));
307    FunctionType * functionType = FunctionType::get(returnType, std::vector<Type *>({PointerType::get(mKernelStateType, 0), T, T, T, T, T}), false);
308   
309    SmallVector<AttributeSet, 6> Attrs;
310    Attrs.push_back(AttributeSet::get(ctxt, ~0U, std::vector<Attribute::AttrKind>({ Attribute::NoUnwind, Attribute::UWTable })));
311    Attrs.push_back(AttributeSet::get(ctxt, 1, std::vector<Attribute::AttrKind>({})));
312    Attrs.push_back(AttributeSet::get(ctxt, 2, std::vector<Attribute::AttrKind>({})));
313    Attrs.push_back(AttributeSet::get(ctxt, 3, std::vector<Attribute::AttrKind>({})));
314    Attrs.push_back(AttributeSet::get(ctxt, 4, std::vector<Attribute::AttrKind>({})));
315    Attrs.push_back(AttributeSet::get(ctxt, 5, std::vector<Attribute::AttrKind>({})));
316    AttributeSet AttrSet = AttributeSet::get(ctxt, Attrs);
317   
318    function = Function::Create(functionType, GlobalValue::ExternalLinkage, "scan_matches_in_scanword", m);
319    function->setCallingConv(CallingConv::C);
320    function->setAttributes(AttrSet);
321    function->addFnAttr(llvm::Attribute::AlwaysInline);
322   
323    Function::arg_iterator args = function->arg_begin();
324    Value * instance = &*(args++);
325    instance->setName("this");
326    Value * matches_input_parm = &*(args++);
327    matches_input_parm->setName("matches");
328    Value * record_breaks_input_parm = &*(args++);
329    record_breaks_input_parm->setName("breaks");
330    Value * scanwordPos = &*(args++);
331    scanwordPos->setName("scanwordPos");
332    Value * recordStart_input_parm = &*(args++);
333    recordStart_input_parm->setName("pendingLineStart");
334    Value * recordNum_input_parm = &*(args++);
335    recordNum_input_parm->setName("lineNum");
336   
337    Constant * matchProcessor;
338    if (mIsNameExpression) {
339        matchProcessor = m->getOrInsertFunction("insert_codepoints", Type::getVoidTy(ctxt), T, T, T, S, nullptr);
340    } else {
341        matchProcessor = m->getOrInsertFunction("wrapped_report_match", Type::getVoidTy(ctxt), T, T, T, S, T, T, nullptr);
342    }
343    iBuilder->SetInsertPoint(BasicBlock::Create(ctxt, "entry", function,0));
344   
345    BasicBlock * entry_block = iBuilder->GetInsertBlock();
346    BasicBlock * matches_test_block = BasicBlock::Create(ctxt, "matches_test_block", function, 0);
347    BasicBlock * process_matches_loop_entry = BasicBlock::Create(ctxt, "process_matches_loop", function, 0);
348    BasicBlock * prior_breaks_block = BasicBlock::Create(ctxt, "prior_breaks_block", function, 0);
349    BasicBlock * loop_final_block = BasicBlock::Create(ctxt, "loop_final_block", function, 0);
350    BasicBlock * matches_done_block = BasicBlock::Create(ctxt, "matches_done_block", function, 0);
351    BasicBlock * remaining_breaks_block = BasicBlock::Create(ctxt, "remaining_breaks_block", function, 0);
352    BasicBlock * return_block = BasicBlock::Create(ctxt, "return_block", function, 0);
353   
354   
355    // The match scanner works with a loop involving four variables:
356    // (a) the bit stream scanword of matches marking the ends of selected records,
357    // (b) the bit stream scanword of record_breaks marking the ends of all records,
358    // (c) the integer lastRecordNum indicating the number of records processed so far,
359    // (d) the index lastRecordStart indicating the file position of the last record.
360    // We set up a loop structure, in which a set of 4 phi nodes initialize these
361    // variables from either the input to the scanner or the computed values within
362    // the loop body.
363   
364   
365    iBuilder->CreateBr(matches_test_block);
366   
367    // LOOP Test Block
368    iBuilder->SetInsertPoint(matches_test_block);
369    PHINode * matches_phi = iBuilder->CreatePHI(T, 2, "matches");
370    PHINode * record_breaks_phi = iBuilder->CreatePHI(T, 2, "record_breaks");
371    PHINode * recordNum_phi = iBuilder->CreatePHI(T, 2, "recordNum");
372    PHINode * recordStart_phi = iBuilder->CreatePHI(T, 2, "recordStart");
373    matches_phi->addIncoming(matches_input_parm, entry_block);
374    record_breaks_phi->addIncoming(record_breaks_input_parm, entry_block);
375    recordNum_phi->addIncoming(recordNum_input_parm, entry_block);
376    recordStart_phi->addIncoming(recordStart_input_parm, entry_block);
377    Value * have_matches_cond = iBuilder->CreateICmpNE(matches_phi, ConstantInt::get(T, 0));
378    iBuilder->CreateCondBr(have_matches_cond, process_matches_loop_entry, matches_done_block);
379   
380    // LOOP BODY
381    // The loop body is entered if we have more matches to process.
382    iBuilder->SetInsertPoint(process_matches_loop_entry);
383    Value * prior_breaks = iBuilder->CreateAnd(generateForwardZeroesMask(iBuilder, matches_phi), record_breaks_phi);
384    // Within the loop we have a conditional block that is executed if there are any prior
385    // record breaks.
386    Value * prior_breaks_cond = iBuilder->CreateICmpNE(prior_breaks, ConstantInt::get(T, 0));
387    iBuilder->CreateCondBr(prior_breaks_cond, prior_breaks_block, loop_final_block);
388   
389    // PRIOR_BREAKS_BLOCK
390    // If there are prior breaks, we count them and compute the record start position.
391    iBuilder->SetInsertPoint(prior_breaks_block);
392    Value * matchRecordNum = iBuilder->CreateAdd(generatePopcount(iBuilder, prior_breaks), recordNum_phi);
393    Value * reverseDistance = generateCountReverseZeroes(iBuilder, prior_breaks);
394    Value * width = ConstantInt::get(T, mScanwordBitWidth);
395    Value * matchRecordStart = iBuilder->CreateAdd(scanwordPos, iBuilder->CreateSub(width, reverseDistance));
396    iBuilder->CreateBr(loop_final_block);
397   
398    // LOOP FINAL BLOCK
399    // The prior breaks, if any have been counted.  Set up phi nodes for the recordNum
400    // and recortStart depending on whether the conditional execution of prior_breaks_block.
401    iBuilder->SetInsertPoint(loop_final_block);
402    PHINode * matchRecordNum_phi = iBuilder->CreatePHI(T, 2, "matchRecordNum");
403    PHINode * matchRecordStart_phi = iBuilder->CreatePHI(T, 2, "matchRecordStart");
404    matchRecordNum_phi->addIncoming(recordNum_phi, process_matches_loop_entry);
405    matchRecordNum_phi->addIncoming(matchRecordNum, prior_breaks_block);
406    matchRecordStart_phi->addIncoming(recordStart_phi, process_matches_loop_entry);
407    matchRecordStart_phi->addIncoming(matchRecordStart, prior_breaks_block);   
408    Value * matchRecordEnd = iBuilder->CreateAdd(scanwordPos, generateCountForwardZeroes(iBuilder, matches_phi));
409   
410
411    Value * fileBuf = getScalarField(instance, "FileBuf");
412    if (mIsNameExpression) {
413        iBuilder->CreateCall(matchProcessor, std::vector<Value *>({matchRecordNum_phi, matchRecordStart_phi, matchRecordEnd, fileBuf}));
414    } else {
415        Value * fileSize = getScalarField(instance, "FileSize");
416        Value * fileIdx = getScalarField(instance, "FileIdx");
417        iBuilder->CreateCall(matchProcessor, std::vector<Value *>({matchRecordNum_phi, matchRecordStart_phi, matchRecordEnd, fileBuf, fileSize, fileIdx}));
418    }
419   
420    Value * remaining_matches = generateResetLowestBit(iBuilder, matches_phi);
421    Value * remaining_breaks = iBuilder->CreateXor(record_breaks_phi, prior_breaks);
422    matches_phi->addIncoming(remaining_matches, loop_final_block);
423    record_breaks_phi->addIncoming(remaining_breaks, loop_final_block);
424    recordNum_phi->addIncoming(matchRecordNum_phi, loop_final_block);
425    recordStart_phi->addIncoming(matchRecordStart_phi, loop_final_block);
426    iBuilder->CreateBr(matches_test_block);
427   
428   
429    // LOOP EXIT/MATCHES_DONE
430    iBuilder->SetInsertPoint(matches_done_block);
431    // When the matches are done, there may be additional record breaks remaining
432    Value * more_breaks_cond = iBuilder->CreateICmpNE(record_breaks_phi, ConstantInt::get(T, 0));
433    iBuilder->CreateCondBr(more_breaks_cond, remaining_breaks_block, return_block);
434   
435    // REMAINING_BREAKS_BLOCK: process remaining record breaks after all matches are processed
436    iBuilder->SetInsertPoint(remaining_breaks_block);
437    Value * break_count = generatePopcount(iBuilder, record_breaks_phi);
438    Value * final_record_num = iBuilder->CreateAdd(recordNum_phi, break_count);
439    Value * reverseZeroes = generateCountReverseZeroes(iBuilder, record_breaks_phi);
440    Value * pendingLineStart = iBuilder->CreateAdd(scanwordPos, iBuilder->CreateSub(width, reverseZeroes));
441    iBuilder->CreateBr(return_block);
442   
443    // RETURN block
444    iBuilder->SetInsertPoint(return_block);
445    PHINode * finalRecordCount_phi = iBuilder->CreatePHI(T, 2, "finalRecordCount");
446    PHINode * finalRecordStart_phi = iBuilder->CreatePHI(T, 2, "finalRecordStart");
447    finalRecordCount_phi->addIncoming(recordNum_phi, matches_done_block);
448    finalRecordCount_phi->addIncoming(final_record_num, remaining_breaks_block);
449    finalRecordStart_phi->addIncoming(recordStart_phi, matches_done_block);
450    finalRecordStart_phi->addIncoming(pendingLineStart, remaining_breaks_block);
451    Value * retVal = UndefValue::get(returnType);
452    retVal = iBuilder->CreateInsertValue(retVal, finalRecordStart_phi, 0);
453    retVal = iBuilder->CreateInsertValue(retVal, finalRecordCount_phi, 1);
454    iBuilder->CreateRet(retVal);
455   
456    return function;
457}
458
459}
Note: See TracBrowser for help on using the repository browser.