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

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

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