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

Last change on this file since 4970 was 4970, checked in by nmedfort, 3 years ago

Added ability to name internal state types; removed unnecessary predefined states. Some progress towards supporting segment size > 1

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