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

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

First attempt at inlining all DoBlock? and FinalBlock? functions by using indirect jumps. Disabled for NVPTX until Linda can check whether they're supported by the LLVM NVPTX library.

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