source: icGREP/icgrep-devel/icgrep/kernels/lzparabix/LZParabixCompressionKernel.cpp @ 6116

Last change on this file since 6116 was 6116, checked in by xwa163, 10 months ago

Small bug fix for LZParabix Compression kernel

File size: 21.4 KB
Line 
1
2#include "LZParabixCompressionKernel.h"
3
4#include <kernels/kernel_builder.h>
5#include <iostream>
6#include <string>
7#include <llvm/Support/raw_ostream.h>
8#include <kernels/streamset.h>
9#include <cstdint>
10
11
12#define HASHLOG (12)
13#define HASHNBCELLS4 (1 << HASHLOG)
14
15
16using namespace llvm;
17using namespace kernel;
18using namespace std;
19
20namespace kernel{
21
22
23
24
25    LZParabixCompressionKernel::LZParabixCompressionKernel(const std::unique_ptr<kernel::KernelBuilder> &b)
26    :SegmentOrientedKernel("LZParabixAioKernel",
27            // Inputs
28                           {
29                                   Binding{b->getStreamSetTy(1, 8), "byteStream", FixedRate()},
30                           },
31            //Outputs
32                           {
33                                   Binding{b->getStreamSetTy(1, 8), "outputStream", BoundedRate(0, 1)}
34                           },
35            //Arguments
36                           {
37                                   Binding{b->getSizeTy(), "fileSize"}
38                           },
39                           {},
40            //Internal states:
41                           {
42                                   // Two hashmap to optimize the performance of matching
43                                   Binding(ArrayType::get(b->getInt64Ty(), HASHNBCELLS4), "strToBlockIndex"),
44                                   Binding(ArrayType::get(b->getInt32Ty(), HASHNBCELLS4), "strToMatchPos")
45
46                           }),
47     mLzParabixBlockSize(4 * 1024 * 1024)
48    {
49        this->setStride(mLzParabixBlockSize);
50        addAttribute(MustExplicitlyTerminate());
51    }
52
53    void LZParabixCompressionKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> &b) {
54        Value* inputCursor = b->getProcessedItemCount("byteStream");
55        Value* inputEndPos = b->CreateAdd(inputCursor, b->getSize(mLzParabixBlockSize));
56        Value* fileSize = b->getScalarField("fileSize");
57        inputEndPos = b->CreateUMin(inputEndPos, fileSize);
58        Value* outputCursor = b->getProducedItemCount("outputStream");
59        this->encodeBlock(b, inputCursor, inputEndPos, outputCursor);
60
61        b->setTerminationSignal(b->CreateICmpEQ(inputEndPos, fileSize));
62        b->setProcessedItemCount("byteStream", inputEndPos);
63    }
64
65    void LZParabixCompressionKernel::encodeBlock(const std::unique_ptr<KernelBuilder> &b, llvm::Value *inputCursor,
66                                                 llvm::Value *inputEndPos, llvm::Value *outputPos) {
67        // Constant
68        ConstantInt* SIZE_64 = b->getSize(64);
69
70        // ---- EntryBlock
71        BasicBlock* entryBlock = b->GetInsertBlock();
72
73        BasicBlock* encodeBlockCon = b->CreateBasicBlock("encodeBlockCon");
74        BasicBlock* encodeBlockBody = b->CreateBasicBlock("encodeBlockBody");
75        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
76
77        Value* blockSizePos = outputPos;
78
79        Value* initOutputCursor = b->CreateAdd(outputPos, b->getSize(4)); // blockSize takes 4 bytes
80        Value* initBlockIndex = b->CreateUDiv(inputCursor, b->getSize(64));
81
82
83        b->CreateBr(encodeBlockCon);
84
85        // ---- encodeBlockCon
86        b->SetInsertPoint(encodeBlockCon);
87
88        PHINode* phiInputCursorPos = b->CreatePHI(b->getSizeTy(), 3);
89        phiInputCursorPos->addIncoming(inputCursor, entryBlock);
90        PHINode* phiPreviousInputCursorPos = b->CreatePHI(b->getSizeTy(), 3);
91        phiPreviousInputCursorPos->addIncoming(inputCursor, entryBlock);
92        PHINode* phiPreviousBlockIndex = b->CreatePHI(b->getSizeTy(), 3);
93        phiPreviousBlockIndex->addIncoming(initBlockIndex, entryBlock);
94        PHINode* phiOutputCursorPos = b->CreatePHI(b->getSizeTy(), 3);
95        phiOutputCursorPos->addIncoming(initOutputCursor, entryBlock);
96
97        b->CreateCondBr(
98                b->CreateICmpULT(phiInputCursorPos, inputEndPos),
99                encodeBlockBody,
100                exitBlock
101        );
102
103        // ---- encodeBlockBody
104        b->SetInsertPoint(encodeBlockBody);
105
106        BasicBlock* updateCacheBlock = b->CreateBasicBlock("updateCacheBlock");
107        BasicBlock* extractMatchInfoBlock = b->CreateBasicBlock("extractMatchInfoBlock");
108
109        Value* newBlockIndex = b->CreateUDiv(phiInputCursorPos, SIZE_64);
110        b->CreateCondBr(
111                b->CreateICmpNE(newBlockIndex, phiPreviousBlockIndex),
112                updateCacheBlock,
113                extractMatchInfoBlock
114        );
115
116        // ---- updateCacheBlock
117        b->SetInsertPoint(updateCacheBlock);
118
119        this->updateCache(b, phiPreviousBlockIndex, initBlockIndex);
120
121        b->CreateBr(extractMatchInfoBlock);
122
123        // ---- encodeProcessBlock
124        b->SetInsertPoint(extractMatchInfoBlock);
125
126        MatchInfo retMatchInfo = this->extractMatchInfo(b, phiInputCursorPos, initBlockIndex, inputEndPos);
127//        b->CallPrintInt("matchLength", retMatchInfo.matchLength);
128        BasicBlock* noAppendOutputBlock = b->CreateBasicBlock("noAppendOutputBlock");
129        BasicBlock* appendOutputBlock = b->CreateBasicBlock("appendOutputBlock");
130
131        b->CreateCondBr(
132                b->CreateICmpUGE(
133                    retMatchInfo.matchLength,
134                    b->getSize(9)
135                ),
136                appendOutputBlock,
137                noAppendOutputBlock
138        );
139
140        // ---- appendOutputBlock
141        b->SetInsertPoint(appendOutputBlock);
142
143        Value* outputCursorPosAfterLiteral = this->appendLiteralSequence(b, phiPreviousInputCursorPos, phiInputCursorPos, phiOutputCursorPos);
144        Value* outputCursorPosAfterMatch = this->appendMatchSequence(b, retMatchInfo, outputCursorPosAfterLiteral);
145        Value* nextCursorPos = b->CreateAdd(phiInputCursorPos, retMatchInfo.matchLength);
146
147        phiInputCursorPos->addIncoming(nextCursorPos, b->GetInsertBlock());
148        phiPreviousInputCursorPos->addIncoming(nextCursorPos, b->GetInsertBlock());
149        phiPreviousBlockIndex->addIncoming(newBlockIndex, b->GetInsertBlock());
150        phiOutputCursorPos->addIncoming(outputCursorPosAfterMatch, b->GetInsertBlock());
151        b->CreateBr(encodeBlockCon);
152
153
154        // ---- noAppendOutputBlock
155        b->SetInsertPoint(noAppendOutputBlock);
156
157        Value* newInputCursorPos = b->CreateSelect(
158                b->CreateICmpEQ(phiPreviousInputCursorPos, phiInputCursorPos),
159                b->CreateAdd(phiInputCursorPos, b->getSize(8)),
160                b->CreateAdd(phiInputCursorPos, b->getSize(1))
161        );
162        newInputCursorPos = b->CreateUMin(newInputCursorPos, inputEndPos);
163
164        phiInputCursorPos->addIncoming(newInputCursorPos, b->GetInsertBlock());
165        phiPreviousInputCursorPos->addIncoming(phiPreviousInputCursorPos, b->GetInsertBlock());
166        phiPreviousBlockIndex->addIncoming(newBlockIndex, b->GetInsertBlock());
167        phiOutputCursorPos->addIncoming(phiOutputCursorPos, b->GetInsertBlock());
168        b->CreateBr(encodeBlockCon);
169
170        // ---- exitBlock
171        b->SetInsertPoint(exitBlock);
172
173
174        Value* finalOutputPos = this->appendLiteralSequence(b, phiPreviousInputCursorPos, inputEndPos, phiOutputCursorPos);
175        Value* blockSize = b->CreateSub(finalOutputPos, initOutputCursor);
176//        blockSizePos
177        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8Ty()->getPointerTo());
178        b->CreateStore(b->CreateTrunc(blockSize, b->getInt32Ty()), b->CreatePointerCast(b->CreateGEP(outputBasePtr, b->CreateURem(blockSizePos, b->getCapacity("outputStream"))), b->getInt32Ty()->getPointerTo()));
179
180        b->setProducedItemCount("outputStream", finalOutputPos);
181
182    }
183
184    void LZParabixCompressionKernel::updateCache(const std::unique_ptr<KernelBuilder> &b, llvm::Value *i64BlockGlobalIndex, llvm::Value *initBlockGlobalIndex) {
185        // Constant
186        ConstantInt* SIZE_64 = b->getSize(64);
187        ConstantInt* INT_64_16 = b->getInt64(16);
188        ConstantInt* INT_32_8 = b->getInt32(8);
189
190        // Type
191        Type* i64PtrTy = b->getInt64Ty()->getPointerTo();
192        Type* i32PtrTy = b->getInt32Ty()->getPointerTo();
193
194        Value* localI64BlockIndex = b->CreateSub(i64BlockGlobalIndex, initBlockGlobalIndex);
195
196
197        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
198
199        Value* startPos = b->CreateMul(i64BlockGlobalIndex, SIZE_64);
200        for (unsigned i = 0; i + 4 < 64; ++i) {
201            Value* targetPos = b->CreateAdd(startPos, b->getSize(i));
202            Value* valuePtr = b->CreatePointerCast(b->CreateGEP(inputBasePtr, targetPos), i32PtrTy);
203            Value* inputValue = b->CreateLoad(valuePtr);
204
205            Value* hashedKey = this->hashKey(b, inputValue);
206
207            // Update mStrToBlockIndex
208            Value* strToBlockIndexBasePtr = b->CreatePointerCast(b->getScalarFieldPtr("strToBlockIndex"), i64PtrTy);
209            Value* strToBlockIndexTargetPtr = b->CreateGEP(strToBlockIndexBasePtr, hashedKey);
210            Value* newBlockIndexCacheValue = b->CreateOr(b->CreateShl(b->CreateLoad(strToBlockIndexTargetPtr), INT_64_16), localI64BlockIndex);
211            b->CreateStore(newBlockIndexCacheValue, strToBlockIndexTargetPtr);
212
213            // Update mStrToMatchPos
214            Value* strToMatchPosBasePtr = b->CreatePointerCast(b->getScalarFieldPtr("strToMatchPos"), i32PtrTy);
215            Value* strToMatchPosTargetPtr = b->CreateGEP(strToMatchPosBasePtr, hashedKey);
216            Value* newMatchPosCacheValue = b->CreateOr(b->CreateShl(b->CreateLoad(strToMatchPosTargetPtr), INT_32_8), b->getInt32(i));
217            b->CreateStore(newMatchPosCacheValue, strToMatchPosTargetPtr);
218        }
219    }
220
221    llvm::Value *LZParabixCompressionKernel::hashKey(const std::unique_ptr<KernelBuilder> &b, llvm::Value *v) {
222        //  (((v) * 2654435761U) >> ((4 * 8) - HASHLOG))
223        ConstantInt* magicNumber = b->getInt32(2654435761); // 2654435761 here is a Magic Number for hash
224        return b->CreateLShr(
225                b->CreateMul(v, magicNumber),
226                b->getInt32(4 * 8 - HASHLOG)
227        );
228    }
229
230
231
232    MatchInfo LZParabixCompressionKernel::extractMatchInfo(const std::unique_ptr<KernelBuilder> &b, llvm::Value *cursorPos, llvm::Value *initBlockGlobalIndex, llvm::Value* inputEndPos) {
233        // ---- EntryBlock
234        Value* SIZE_0 = b->getSize(0);
235        MatchInfo retInfo = {SIZE_0, SIZE_0, SIZE_0, SIZE_0};
236
237        BasicBlock* entryBlock = b->GetInsertBlock();
238        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
239
240        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
241
242        auto retMatchInfo = this->getPossibleMatchInfo(b, cursorPos);
243
244        Value* possibleBlockIndexes = retMatchInfo.first;
245        Value* possibleMatchPos = retMatchInfo.second;
246
247        Value* currentGlobalInputBlockIndex = b->CreateUDiv(cursorPos, b->getSize(64));
248
249
250
251        for (unsigned i = 0; i < 4; i++) {
252            BasicBlock* extractMatchInfoEntryBlock = b->CreateBasicBlock("extractMatchInfoEntryBlock");
253            b->CreateBr(extractMatchInfoEntryBlock);
254
255            // ---- extractMatchInfoEntryBlock
256            b->SetInsertPoint(extractMatchInfoEntryBlock);
257
258
259            Value* localMatchBlockIndex = b->CreateAnd(b->CreateLShr(possibleBlockIndexes, b->getInt64(i * 16)), b->getInt64(0xffff));
260            Value* globalMatchBlockIndex = b->CreateAdd(localMatchBlockIndex, initBlockGlobalIndex);
261
262            Value* matchPos = b->CreateAnd(b->CreateLShr(possibleMatchPos, b->getInt32(i * 8)), b->getInt32(0xff));
263            matchPos = b->CreateZExt(matchPos, b->getInt64Ty());
264
265            Value* blockOffset = b->CreateSub(currentGlobalInputBlockIndex, globalMatchBlockIndex);
266
267            Value* isNoMatch = b->CreateOr(
268                    b->CreateICmpUGE(globalMatchBlockIndex, currentGlobalInputBlockIndex),
269                    b->CreateICmpUGE(blockOffset, b->getSize(128))
270            );
271
272//            b->CallPrintInt("isNoMatch", isNoMatch);
273
274            BasicBlock* scanMatchConBlock = b->CreateBasicBlock("scanMatchConBlock");
275            BasicBlock* scanMatchBodyBlock = b->CreateBasicBlock("scanMatchBodyBlock");
276            BasicBlock* scanMatchExitBlock = b->CreateBasicBlock("scanMatchExitBlock");
277
278//            b->CreateCondBr(isNoMatch, scanMatchExitBlock, scanMatchConBlock);
279            b->CreateBr(scanMatchConBlock);
280
281            // ---- scanMatchConBlock
282            b->SetInsertPoint(scanMatchConBlock);
283
284            PHINode* phiForwardMatchLength = b->CreatePHI(b->getSizeTy(), 2);
285            phiForwardMatchLength->addIncoming(b->getSize(0), extractMatchInfoEntryBlock);
286            PHINode* phiMatchPos = b->CreatePHI(b->getSizeTy(), 2);
287            phiMatchPos->addIncoming(matchPos, extractMatchInfoEntryBlock);
288            PHINode* phiMatchMask = b->CreatePHI(b->getInt64Ty(), 2);
289            phiMatchMask->addIncoming(b->getInt64(0), extractMatchInfoEntryBlock);
290
291            b->CreateCondBr(
292                    b->CreateAnd(
293                            b->CreateAnd(
294                                    b->CreateICmpULT(phiMatchPos, b->getInt64(64)),
295                                    b->CreateICmpULT(b->CreateAdd(cursorPos, phiForwardMatchLength), inputEndPos)
296                            ),
297                            b->CreateNot(isNoMatch)
298                    ),
299                    scanMatchBodyBlock,
300                    scanMatchExitBlock
301            );
302
303            // ---- scanMatchBodyBlock
304            b->SetInsertPoint(scanMatchBodyBlock);
305
306            Value* isMatch = b->CreateICmpEQ(
307                    b->CreateLoad(b->CreateGEP(inputBasePtr, b->CreateAdd(b->CreateMul(globalMatchBlockIndex, b->getInt64(64)), phiMatchPos))),
308                    b->CreateLoad(b->CreateGEP(inputBasePtr, b->CreateAdd(cursorPos, phiForwardMatchLength)))
309            );
310
311
312            phiForwardMatchLength->addIncoming(
313                    b->CreateSelect(isMatch, b->CreateAdd(phiForwardMatchLength, b->getSize(1)), phiForwardMatchLength),
314                    b->GetInsertBlock()
315            );
316            phiMatchPos->addIncoming(
317                    b->CreateAdd(phiMatchPos, b->getSize(1)),
318                    b->GetInsertBlock()
319            );
320
321            phiMatchMask->addIncoming(
322                    b->CreateSelect(
323                            isMatch,
324                            b->CreateOr(phiMatchMask, b->CreateShl(b->getInt64(1), phiMatchPos)),
325                            phiMatchMask
326                    ),
327                    b->GetInsertBlock()
328            );
329
330            b->CreateBr(scanMatchConBlock);
331
332            // ---- scanMatchExitBlock
333            b->SetInsertPoint(scanMatchExitBlock);
334
335            Value* isBetterMatch = b->CreateICmpUGT(phiForwardMatchLength, retInfo.matchLength);
336            retInfo.matchLength = b->CreateSelect(isBetterMatch, phiForwardMatchLength, retInfo.matchLength);
337            retInfo.matchMask = b->CreateSelect(isBetterMatch, phiMatchMask, retInfo.matchMask);
338            retInfo.matchOffset = b->CreateSelect(isBetterMatch, blockOffset, retInfo.matchOffset);
339            retInfo.matchStart = b->CreateSelect(isBetterMatch, cursorPos, retInfo.matchOffset);
340
341            // TODO search back and adjust match start
342        }
343        b->CreateBr(exitBlock);
344        b->SetInsertPoint(exitBlock);
345
346        return retInfo;
347
348    }
349
350    std::pair<llvm::Value *, llvm::Value *>
351    LZParabixCompressionKernel::getPossibleMatchInfo(const std::unique_ptr<KernelBuilder> &b, llvm::Value *cursorPos) {
352        // Type
353        Type* i64PtrTy = b->getInt64Ty()->getPointerTo();
354        Type* i32PtrTy = b->getInt32Ty()->getPointerTo();
355
356        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
357        Value* targetPtr = b->CreateGEP(inputBasePtr, cursorPos);
358        targetPtr = b->CreatePointerCast(targetPtr, b->getInt32Ty()->getPointerTo());
359        Value* hashedKey = this->hashKey(b, b->CreateLoad(targetPtr));
360//        b->CallPrintInt("hashedKey", hashedKey);
361        Value* strToBlockIndexBasePtr = b->CreatePointerCast(b->getScalarFieldPtr("strToBlockIndex"), i64PtrTy);
362        Value* strToBlockIndexTargetPtr = b->CreateGEP(strToBlockIndexBasePtr, hashedKey);
363
364        Value* strToMatchPosBasePtr = b->CreatePointerCast(b->getScalarFieldPtr("strToMatchPos"), i32PtrTy);
365        Value* strToMatchPosTargetPtr = b->CreateGEP(strToMatchPosBasePtr, hashedKey);
366
367        return std::make_pair(
368                b->CreateLoad(strToBlockIndexTargetPtr),
369                b->CreateLoad(strToMatchPosTargetPtr)
370        );
371    }
372
373    Value *LZParabixCompressionKernel::appendLiteralSequence(const unique_ptr<KernelBuilder> &b, Value *literalStart,
374                                                             Value *literalEnd, Value *outputPos) {
375        // Constant
376        Value* SIZE_0 = b->getSize(0);
377        Value* SIZE_1 = b->getSize(1);
378        Value* SIZE_64 = b->getSize(64);
379        Type* i8PtrTy = b->getInt8PtrTy();
380
381
382        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", SIZE_0), i8PtrTy);
383        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", SIZE_0), i8PtrTy);
384        Value* outputCapacity = b->getCapacity("outputStream");
385
386
387        // ---- EntryBlock
388        BasicBlock* entryBlock = b->GetInsertBlock();
389        BasicBlock* appendLiteralConBlock = b->CreateBasicBlock("AppendLiteralConBlock");
390        BasicBlock* appendLiteralBodyBlock = b->CreateBasicBlock("AppendLiteralBodyBlock");
391        BasicBlock* appendLiteralExitBlock = b->CreateBasicBlock("AppendLiteralExitBlock");
392
393        b->CreateBr(appendLiteralConBlock);
394
395        // ---- AppendLiteralConBlock
396        b->SetInsertPoint(appendLiteralConBlock);
397        PHINode* phiOutputPos = b->CreatePHI(b->getSizeTy(), 2);
398        phiOutputPos->addIncoming(outputPos, entryBlock);
399        PHINode* phiLiteralStart = b->CreatePHI(b->getSizeTy(), 2);
400        phiLiteralStart->addIncoming(literalStart, entryBlock);
401
402        Value* remainingLiteralLength = b->CreateSub(literalEnd, phiLiteralStart);
403
404        b->CreateCondBr(b->CreateICmpUGT(remainingLiteralLength, b->getSize(0)), appendLiteralBodyBlock, appendLiteralExitBlock);
405
406        // ---- AppendLiteralBodyBlock
407        b->SetInsertPoint(appendLiteralBodyBlock);
408
409        Value* outputPosRem = b->CreateURem(phiOutputPos, outputCapacity);
410        Value* outputNextPosRem = b->CreateAdd(outputPosRem, b->getSize(1));
411
412        Value* maxLiteralLength = b->CreateSub(SIZE_64, b->CreateURem(outputNextPosRem, SIZE_64));
413        Value* literalLength = b->CreateUMin(remainingLiteralLength, maxLiteralLength);
414
415        Value* literalToken = b->CreateOr(b->CreateTrunc(literalLength, b->getInt8Ty()), b->getInt8(1 << 7));
416
417        b->CreateStore(literalToken, b->CreateGEP(outputBasePtr, outputPosRem));
418        outputNextPosRem = b->CreateURem(outputNextPosRem, b->getCapacity("outputStream"));
419        b->CreateMemCpy(
420                b->CreateGEP(outputBasePtr, outputNextPosRem),
421                b->CreateGEP(inputBasePtr, phiLiteralStart),
422                literalLength,
423                1
424        );
425
426        phiLiteralStart->addIncoming(b->CreateAdd(phiLiteralStart, literalLength), b->GetInsertBlock());
427        phiOutputPos->addIncoming(b->CreateAdd(phiOutputPos, b->CreateAdd(literalLength, SIZE_1)), b->GetInsertBlock());
428        b->CreateBr(appendLiteralConBlock);
429
430        // ---- AppendLiteralExitBlock
431        b->SetInsertPoint(appendLiteralExitBlock);
432
433        return phiOutputPos;
434    }
435
436    Value* LZParabixCompressionKernel::appendMatchSequence(const unique_ptr<KernelBuilder> &b, const MatchInfo& matchInfo, Value* outputPos) {
437        // Constant
438        Value* SIZE_0 = b->getSize(0);
439        Value* SIZE_1 = b->getSize(1);
440        Value* SIZE_64 = b->getSize(64);
441        Type* i8PtrTy = b->getInt8PtrTy();
442
443        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", SIZE_0), i8PtrTy);
444        Value* outputCapacity = b->getCapacity("outputStream");
445
446        // MatchOffset
447        b->CreateStore(b->CreateTrunc(matchInfo.matchOffset, b->getInt8Ty()), b->CreateGEP(outputBasePtr, b->CreateURem(outputPos, outputCapacity)));
448
449        Value* outputOneBitIndexPos = b->CreateAdd(outputPos, SIZE_1);
450        Value* outputZeroBitIndexPos = b->CreateAdd(outputOneBitIndexPos, SIZE_1);
451
452        Value* outputBitMaskPos = b->CreateAdd(outputZeroBitIndexPos, SIZE_1);
453
454        Value* oneBitIndex = b->getInt8(0);
455        Value* zeroBitIndex = b->getInt8(0);
456
457        for (unsigned i = 0; i < 8; i++) {
458            Value* currentBitIndex = b->CreateTrunc(b->CreateLShr(matchInfo.matchMask, b->getInt64(i * 8)), b->getInt8Ty());
459            Value* newOneBit = b->CreateICmpEQ(currentBitIndex, b->getInt8(0xff));
460            Value* newZeroBit = b->CreateICmpEQ(currentBitIndex, b->getInt8(0));
461
462            oneBitIndex = b->CreateSelect(
463                    newOneBit,
464                    b->CreateOr(oneBitIndex, b->getInt8(1 << i)),
465                    oneBitIndex
466            );
467
468            zeroBitIndex = b->CreateSelect(
469                    newZeroBit,
470                    b->CreateOr(zeroBitIndex, b->getInt8(1 << i)),
471                    zeroBitIndex
472            );
473            b->CreateStore(currentBitIndex, b->CreateGEP(outputBasePtr, b->CreateURem(outputBitMaskPos, outputCapacity)));
474            outputBitMaskPos = b->CreateSelect(
475                    b->CreateOr(newOneBit, newZeroBit),
476                    outputBitMaskPos,
477                    b->CreateAdd(outputBitMaskPos, SIZE_1)
478            );
479        }
480        b->CreateStore(oneBitIndex, b->CreateGEP(outputBasePtr, b->CreateURem(outputOneBitIndexPos, outputCapacity)));
481        b->CreateStore(zeroBitIndex, b->CreateGEP(outputBasePtr, b->CreateURem(outputZeroBitIndexPos, outputCapacity)));
482
483        return outputBitMaskPos;
484    }
485
486}
Note: See TracBrowser for help on using the repository browser.