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

Last change on this file since 4936 was 4936, checked in by cameron, 4 years ago

Revert scanmatchgen changes

File size: 14.4 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
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/*
36       
37void write_matches_ending_in_segment(scanword_t matches, scanword_t lbreaks, ssize_t segmentPos, ssize_t & pendingLineStart, int & lineNum) {
38    scanword_t remaining_matches = matches;
39    scanword_t remaining_LBs = lbreaks;
40    while (remaining_matches != 0) {
41        // Find all the line marks prior to the match position
42        scanword_t priorLineMarks = ForwardZeroesMask(remaining_matches) & remaining_LBs;
43        if (priorLineMarks != 0) {
44            int matchLineNum = lineNum + popcount(priorLineMarks);
45            // The last of these line marks prior to the match position is the
46            // starting positions of the matched line.
47            matchLineStart = segmentPos + segmentBitWidth - CountReverseZeroes(priorLineMarks);
48        }
49        else {
50            matchLineNum = lineNum;
51            matchLineStart = pendingLineStart;
52        }
53        // The line end is marked by the match posiiton.
54        matchLineEnd = segmentPos + CountForwardZeroes(remaining_matches);
55        call write_match(matchLineNum, matchLineStart, matchLineEnd);
56       
57        remaining_matches = ResetLowestBit(remaining_matches);
58        remaining_LBs = remaining_LBs ^ priorLineMarks;
59        lineNum = matchLineNum;
60    }
61    if (remaining_LBs != 0) {
62        lineNum += popcount(remaining_LBs);
63        pendingLineStart = segmentPos + segmentBitWidth - CountReverseZeroes(remaining_LBs);
64    }
65}   
66        */
67
68       
69       
70void generateScanSegmentRoutine(Module * m, IDISA::IDISA_Builder * iBuilder, int segBitWidth) {
71    LLVMContext & ctxt = m->getContext();
72    Type * T = iBuilder->getIntNTy(segBitWidth);
73    Type * returnType = StructType::get(ctxt, std::vector<Type *>({T, T}));
74    FunctionType * functionType = FunctionType::get(returnType, std::vector<Type *>({T, T, T, T, T}), false);
75    Function * sFunction;
76       
77    SmallVector<AttributeSet, 6> Attrs;
78    Attrs.push_back(AttributeSet::get(ctxt, ~0U, std::vector<Attribute::AttrKind>({ Attribute::NoUnwind, Attribute::UWTable })));
79    Attrs.push_back(AttributeSet::get(ctxt, 1, std::vector<Attribute::AttrKind>({})));
80    Attrs.push_back(AttributeSet::get(ctxt, 2, std::vector<Attribute::AttrKind>({})));
81    Attrs.push_back(AttributeSet::get(ctxt, 3, std::vector<Attribute::AttrKind>({})));
82    Attrs.push_back(AttributeSet::get(ctxt, 4, std::vector<Attribute::AttrKind>({})));
83    Attrs.push_back(AttributeSet::get(ctxt, 5, std::vector<Attribute::AttrKind>({})));
84    AttributeSet AttrSet = AttributeSet::get(ctxt, Attrs);
85   
86    sFunction = Function::Create(functionType, GlobalValue::ExternalLinkage, "scan_matches_in_segment", m);
87    sFunction->setCallingConv(CallingConv::C);
88    sFunction->setAttributes(AttrSet);
89       
90    Function::arg_iterator args = sFunction->arg_begin();
91    Value * matches_input_parm = args++;
92    matches_input_parm->setName("matches");
93    Value * record_breaks_input_parm = args++;
94    record_breaks_input_parm->setName("breaks");
95    Value * segmentPos = args++;
96    segmentPos->setName("segmentPos");
97    Value * recordStart_input_parm = args++;
98    recordStart_input_parm->setName("pendingLineStart");
99    Value * recordNum_input_parm = args++;
100    recordNum_input_parm->setName("lineNum");
101   
102    Constant * matchProcessor = m->getOrInsertFunction("wrapped_report_match", Type::getVoidTy(ctxt), T, T, T, NULL);
103
104   
105    iBuilder->SetInsertPoint(BasicBlock::Create(ctxt, "entry", sFunction,0));
106
107    BasicBlock * entry_block = iBuilder->GetInsertBlock();
108    BasicBlock * matches_test_block = BasicBlock::Create(ctxt, "matches_test_block", sFunction, 0);
109    BasicBlock * process_matches_loop_entry = BasicBlock::Create(ctxt, "process_matches_loop", sFunction, 0);
110    BasicBlock * prior_breaks_block = BasicBlock::Create(ctxt, "prior_breaks_block", sFunction, 0);
111    BasicBlock * loop_final_block = BasicBlock::Create(ctxt, "loop_final_block", sFunction, 0);
112    BasicBlock * matches_done_block = BasicBlock::Create(ctxt, "matches_done_block", sFunction, 0);
113    BasicBlock * remaining_breaks_block = BasicBlock::Create(ctxt, "remaining_breaks_block", sFunction, 0);
114    BasicBlock * return_block = BasicBlock::Create(ctxt, "return_block", sFunction, 0);
115       
116       
117    // The match scanner works with a loop involving four variables:
118    // (a) the bit stream segment of matches marking the ends of selected records,
119    // (b) the bit stream segment of record_breaks marking the ends of all records,
120    // (c) the integer lastRecordNum indicating the number of records processed so far,
121    // (d) the index lastRecordStart indicating the file position of the last record.
122    // We set up a loop structure, in which a set of 4 phi nodes initialize these
123    // variables from either the input to the scanner or the computed values within
124    // the loop body.
125
126   
127    iBuilder->CreateBr(matches_test_block);
128
129    // LOOP Test Block
130    iBuilder->SetInsertPoint(matches_test_block);
131    PHINode * matches_phi = iBuilder->CreatePHI(T, 2, "matches");
132    PHINode * record_breaks_phi = iBuilder->CreatePHI(T, 2, "record_breaks");
133    PHINode * recordNum_phi = iBuilder->CreatePHI(T, 2, "recordNum");
134    PHINode * recordStart_phi = iBuilder->CreatePHI(T, 2, "recordStart");
135    matches_phi->addIncoming(matches_input_parm, entry_block);
136    record_breaks_phi->addIncoming(record_breaks_input_parm, entry_block);
137    recordNum_phi->addIncoming(recordNum_input_parm, entry_block);
138    recordStart_phi->addIncoming(recordStart_input_parm, entry_block);
139    Value * have_matches_cond = iBuilder->CreateICmpNE(matches_phi, ConstantInt::get(T, 0));
140    iBuilder->CreateCondBr(have_matches_cond, process_matches_loop_entry, matches_done_block);
141   
142    // LOOP BODY
143    // The loop body is entered if we have more matches to process.
144    iBuilder->SetInsertPoint(process_matches_loop_entry);
145    Value * prior_breaks = iBuilder->CreateAnd(generateForwardZeroesMask(iBuilder, matches_phi), record_breaks_phi);
146    // Within the loop we have a conditional block that is executed if there are any prior
147    // record breaks.
148    Value * prior_breaks_cond = iBuilder->CreateICmpNE(prior_breaks, ConstantInt::get(T, 0));
149    iBuilder->CreateCondBr(prior_breaks_cond, prior_breaks_block, loop_final_block);
150
151    // PRIOR_BREAKS_BLOCK
152    // If there are prior breaks, we count them and compute the record start position.
153    iBuilder->SetInsertPoint(prior_breaks_block);
154    Value * matchRecordNum = iBuilder->CreateAdd(generatePopcount(iBuilder, prior_breaks), recordNum_phi);
155    Value * reverseDistance = generateCountReverseZeroes(iBuilder, prior_breaks);
156    Value * width = ConstantInt::get(T, segBitWidth);
157    Value * matchRecordStart = iBuilder->CreateAdd(segmentPos, iBuilder->CreateSub(width, reverseDistance));
158    iBuilder->CreateBr(loop_final_block);
159   
160    // LOOP FINAL BLOCK
161    // The prior breaks, if any have been counted.  Set up phi nodes for the recordNum
162    // and recortStart depending on whether the conditional execution of prior_breaks_block.
163    iBuilder->SetInsertPoint(loop_final_block);
164    PHINode * matchRecordNum_phi = iBuilder->CreatePHI(T, 2, "matchRecordNum");
165    PHINode * matchRecordStart_phi = iBuilder->CreatePHI(T, 2, "matchRecordStart");
166    matchRecordNum_phi->addIncoming(recordNum_phi, process_matches_loop_entry);
167    matchRecordNum_phi->addIncoming(matchRecordNum, prior_breaks_block);
168    matchRecordStart_phi->addIncoming(recordStart_phi, process_matches_loop_entry);
169    matchRecordStart_phi->addIncoming(matchRecordStart, prior_breaks_block);
170    Value * matchRecordEnd = iBuilder->CreateAdd(segmentPos, generateCountForwardZeroes(iBuilder, matches_phi));
171    iBuilder->CreateCall(matchProcessor, std::vector<Value *>({matchRecordNum_phi, matchRecordStart_phi, matchRecordEnd}));
172    Value * remaining_matches = generateResetLowestBit(iBuilder, matches_phi);
173    Value * remaining_breaks = iBuilder->CreateXor(record_breaks_phi, prior_breaks);
174    matches_phi->addIncoming(remaining_matches, loop_final_block);
175    record_breaks_phi->addIncoming(remaining_breaks, loop_final_block);
176    recordNum_phi->addIncoming(matchRecordNum_phi, loop_final_block);
177    recordStart_phi->addIncoming(matchRecordStart_phi, loop_final_block);
178    iBuilder->CreateBr(matches_test_block);
179   
180   
181    // LOOP EXIT/MATCHES_DONE
182    iBuilder->SetInsertPoint(matches_done_block);
183    // When the matches are done, there may be additional record breaks remaining
184    Value * more_breaks_cond = iBuilder->CreateICmpNE(record_breaks_phi, ConstantInt::get(T, 0));
185    iBuilder->CreateCondBr(more_breaks_cond, remaining_breaks_block, return_block);
186   
187    // REMAINING_BREAKS_BLOCK: process remaining record breaks after all matches are processed
188    iBuilder->SetInsertPoint(remaining_breaks_block);
189    Value * break_count = generatePopcount(iBuilder, record_breaks_phi);
190    Value * final_record_num = iBuilder->CreateAdd(recordNum_phi, break_count);
191    Value * reverseZeroes = generateCountReverseZeroes(iBuilder, record_breaks_phi);
192    Value * pendingLineStart = iBuilder->CreateAdd(segmentPos, iBuilder->CreateSub(width, reverseZeroes));
193    iBuilder->CreateBr(return_block);
194   
195    // RETURN block
196    iBuilder->SetInsertPoint(return_block);
197    PHINode * finalRecordCount_phi = iBuilder->CreatePHI(T, 2, "finalRecordCount");
198    PHINode * finalRecordStart_phi = iBuilder->CreatePHI(T, 2, "finalRecordStart");
199    finalRecordCount_phi->addIncoming(recordNum_phi, matches_done_block);
200    finalRecordCount_phi->addIncoming(final_record_num, remaining_breaks_block);
201    finalRecordStart_phi->addIncoming(recordStart_phi, matches_done_block);
202    finalRecordStart_phi->addIncoming(pendingLineStart, remaining_breaks_block);
203    Value * retVal = UndefValue::get(returnType);
204    retVal = iBuilder->CreateInsertValue(retVal, finalRecordCount_phi, 0);
205    retVal = iBuilder->CreateInsertValue(retVal, finalRecordStart_phi, 1);
206    iBuilder->CreateRet(retVal);
207   
208}
209
210
211void generateScanBitBlockRoutine(Module * m, IDISA::IDISA_Builder * iBuilder, int segBitWidth) {
212    LLVMContext & ctxt = m->getContext();
213    Type * B = iBuilder->getBitBlockType();
214    Type * T = iBuilder->getIntNTy(segBitWidth);
215    generateScanSegmentRoutine(m, iBuilder, segBitWidth);
216    int fieldCount = iBuilder->getBitBlockWidth()/segBitWidth;
217    Type * segmentVectorType =  VectorType::get(T, fieldCount);
218   
219   
220    Type * returnType = StructType::get(ctxt, std::vector<Type *>({T, T}));
221    FunctionType * functionType = FunctionType::get(returnType, std::vector<Type *>({B, B, T, T, T}), false);
222    Function * sFunction;
223   
224    SmallVector<AttributeSet, 6> Attrs;
225    Attrs.push_back(AttributeSet::get(ctxt, ~0U, std::vector<Attribute::AttrKind>({ Attribute::NoUnwind, Attribute::UWTable })));
226    Attrs.push_back(AttributeSet::get(ctxt, 1, std::vector<Attribute::AttrKind>({})));
227    Attrs.push_back(AttributeSet::get(ctxt, 2, std::vector<Attribute::AttrKind>({})));
228    Attrs.push_back(AttributeSet::get(ctxt, 3, std::vector<Attribute::AttrKind>({})));
229    Attrs.push_back(AttributeSet::get(ctxt, 4, std::vector<Attribute::AttrKind>({})));
230    Attrs.push_back(AttributeSet::get(ctxt, 5, std::vector<Attribute::AttrKind>({})));
231    AttributeSet AttrSet = AttributeSet::get(ctxt, Attrs);
232    sFunction = Function::Create(functionType, GlobalValue::ExternalLinkage, "scan_matches_in_bitblock", m);
233    sFunction->setCallingConv(CallingConv::C);
234    sFunction->setAttributes(AttrSet);
235   
236   
237   
238    Function::arg_iterator args = sFunction->arg_begin();
239    Value * matches_input_parm = args++;
240    matches_input_parm->setName("matches");
241    Value * record_breaks_input_parm = args++;
242    record_breaks_input_parm->setName("breaks");
243    Value * blockPos = args++;
244    blockPos->setName("blockPos");
245    Value * recordStart_input_parm = args++;
246    recordStart_input_parm->setName("pendingLineStart");
247    Value * recordNum_input_parm = args++;
248    recordNum_input_parm->setName("lineNum");
249   
250    iBuilder->SetInsertPoint(BasicBlock::Create(ctxt, "entry", sFunction,0));
251   
252    Value * matchSegVector = iBuilder->CreateBitCast(matches_input_parm, segmentVectorType);
253    Value * breakSegVector = iBuilder->CreateBitCast(record_breaks_input_parm, segmentVectorType);
254    Value * segmentPos = blockPos;
255    Value * recordStart = recordStart_input_parm;
256    Value * recordNum = recordNum_input_parm;
257    Value * segResult = nullptr;
258    Function * segScanFcn = m->getFunction("scan_matches_in_segment");
259    for (uint64_t i = 0; i < iBuilder->getBitBlockWidth()/segBitWidth; i++) {
260        Value * matchSeg = iBuilder->CreateExtractElement(matchSegVector, ConstantInt::get(T, i));
261        Value * recordBreaksSeg = iBuilder->CreateExtractElement(breakSegVector, ConstantInt::get(T, i));
262        segResult = iBuilder->CreateCall(segScanFcn, std::vector<Value *>({matchSeg, recordBreaksSeg, segmentPos, recordStart, recordNum}));
263        segmentPos = iBuilder->CreateAdd(segmentPos, ConstantInt::get(T, segBitWidth));
264        recordStart = iBuilder->CreateExtractValue(segResult, std::vector<unsigned>({0}));
265        recordNum = iBuilder->CreateExtractValue(segResult, std::vector<unsigned>({1}));
266    }
267    iBuilder->CreateRet(segResult);
268}
269
270
271
272
Note: See TracBrowser for help on using the repository browser.