Division and modulo using magic number.
More...
#include <idioms_magicdivmod.h>
|
llvm::Instruction * | magicSignedDiv7 (llvm::BasicBlock::iterator iter, bool negative) const |
|
llvm::Instruction * | magicSignedDiv8 (llvm::BasicBlock::iterator iter, bool negative) const |
|
Division and modulo using magic number.
References: GRANLUND, Torbjorn a Peter L. MONTGOMERY. Division by Invariant Integers Using Multiplication. 1994. Available online: http://gmplib.org/~tege/divcnst-pldi94.pdf
◆ divisorByMagicNumberSigned()
int retdec::bin2llvmir::IdiomsMagicDivMod::divisorByMagicNumberSigned |
( |
int |
magic_number, |
|
|
unsigned |
sh_post |
|
) |
| |
|
staticprivate |
Calculate original divisor from ‘signed magic number multiplication’ form.
- Parameters
-
magic_number | a magic number used when multiply |
sh_post | a shift after multiplication |
- Returns
- computed divisor
◆ divisorByMagicNumberSigned2()
int retdec::bin2llvmir::IdiomsMagicDivMod::divisorByMagicNumberSigned2 |
( |
int |
magic_number, |
|
|
unsigned |
sh_post |
|
) |
| |
|
staticprivate |
Calculate original divisor from ‘signed magic number multiplication’ form.
- Parameters
-
magic_number | a magic number used when multiply |
sh_post | a shift after multiplication |
- Returns
- computed divisor
◆ divisorByMagicNumberSigned3()
unsigned retdec::bin2llvmir::IdiomsMagicDivMod::divisorByMagicNumberSigned3 |
( |
unsigned |
magic_number, |
|
|
unsigned |
shift |
|
) |
| |
|
staticprivate |
Calculate original divisor from ‘signed magic number multiplication’ form. ( value * magic ) >> ( shift )
- Parameters
-
magic_number | a magic number used when multiply |
shift | a shift after multiplication |
- Returns
- computed divisor
◆ divisorByMagicNumberSigned4()
unsigned retdec::bin2llvmir::IdiomsMagicDivMod::divisorByMagicNumberSigned4 |
( |
unsigned |
magic_number, |
|
|
unsigned |
shift |
|
) |
| |
|
staticprivate |
Calculate original divisor from ‘signed magic number multiplication’ form. ( value * magic + value ) >> ( 32 + shift )
- Parameters
-
magic_number | a magic number used when multiply |
shift | a shift after multiplication |
- Returns
- computed divisor
◆ divisorByMagicNumberUnsigned()
unsigned retdec::bin2llvmir::IdiomsMagicDivMod::divisorByMagicNumberUnsigned |
( |
unsigned |
magic_number, |
|
|
unsigned |
sh_pre, |
|
|
unsigned |
sh_post |
|
) |
| |
|
staticprivate |
Calculate original divisor from ‘magic number multiplication’ form.
- Parameters
-
magic_number | a magic number used when multiply |
sh_pre | a shift before multiplication |
sh_post | a shift after multiplication |
- Returns
- computed divisor
◆ divisorByMagicNumberUnsigned2()
unsigned retdec::bin2llvmir::IdiomsMagicDivMod::divisorByMagicNumberUnsigned2 |
( |
unsigned |
magic_number, |
|
|
unsigned |
sh_post |
|
) |
| |
|
staticprivate |
Calculate original divisor from ‘magic number multiplication’ form.
- Parameters
-
magic_number | a magic number used when multiply |
sh_post | a shift after multiplication |
- Returns
- computed divisor
◆ magicSignedDiv1()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::magicSignedDiv1 |
( |
llvm::BasicBlock::iterator |
iter | ) |
const |
|
protected |
Exchange ((int32_t)((int64_t)magic_number * (int64_t)X >> 32) + X >> N) - (x >> 31)) with signed division
- Parameters
-
- Returns
- replaced Instruction, otherwise nullptr
◆ magicSignedDiv2()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::magicSignedDiv2 |
( |
llvm::BasicBlock::iterator |
iter | ) |
const |
|
protected |
Exchange ((int32_t)((int64_t)magic_number * (int64_t)X >> 32) >> 1) - (x >> 31)) with signed division
- Parameters
-
- Returns
- replaced Instruction, otherwise nullptr
◆ magicSignedDiv3()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::magicSignedDiv3 |
( |
llvm::BasicBlock::iterator |
iter | ) |
const |
|
protected |
Exchange (x >> 31) - ((int32_t)(magic_number * (int64_t)x >> 32) >> shift) with signed division
- Parameters
-
- Returns
- replaced Instruction, otherwise nullptr
◆ magicSignedDiv4()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::magicSignedDiv4 |
( |
llvm::BasicBlock::iterator |
iter | ) |
const |
|
protected |
Exchange (x >> 31) - ((int32_t)(magic_number * (int64_t)x >> 32) + x >> shift) with signed division
- Parameters
-
- Returns
- replaced Instruction, otherwise nullptr
◆ magicSignedDiv5()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::magicSignedDiv5 |
( |
llvm::BasicBlock::iterator |
iter | ) |
const |
|
protected |
Exchange (x >> 31) - (int32_t)(magic_number * (int64_t)x >> 32) with signed division
- Parameters
-
- Returns
- replaced Instruction, otherwise nullptr
◆ magicSignedDiv6()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::magicSignedDiv6 |
( |
llvm::BasicBlock::iterator |
iter | ) |
const |
|
protected |
Exchange (x >> 31) - (int32_t)(magic_number * (int64_t)x >> 32) with signed division
- Parameters
-
- Returns
- replaced Instruction, otherwise nullptr
◆ magicSignedDiv7()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::magicSignedDiv7 |
( |
llvm::BasicBlock::iterator |
iter, |
|
|
bool |
negative |
|
) |
| const |
|
private |
Exchange ((int32_t)(v2 / 0x100000000) / -0x80000000 & -0x40000000 | (int32_t)(v2 / 0x400000000)) - (v1 / -0x80000000 & -2 | (int32_t)(v1 < 0)); with signed division
- Parameters
-
iter | value to visit |
negative | search for the negative divisor |
- Returns
- replaced Instruction, otherwise nullptr
◆ magicSignedDiv7neg()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::magicSignedDiv7neg |
( |
llvm::BasicBlock::iterator |
iter | ) |
const |
|
protected |
Wrapper of magicSignedDiv7 for negative values.
- Parameters
-
- Returns
- replaced Instruction, otherwise nullptr
◆ magicSignedDiv7pos()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::magicSignedDiv7pos |
( |
llvm::BasicBlock::iterator |
iter | ) |
const |
|
protected |
Wrapper of magicSignedDiv7 for positive values.
- Parameters
-
- Returns
- replaced Instruction, otherwise nullptr
◆ magicSignedDiv8()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::magicSignedDiv8 |
( |
llvm::BasicBlock::iterator |
iter, |
|
|
bool |
negative |
|
) |
| const |
|
private |
Exchange int32_t v2 = v1 / -0x80000000; // 0x100004c0 return (v2 & -0x20000000 | v1 / 8) - (v2 & -2 | (int32_t)(v1 < 0)); with signed division. This is a similar version to magicSignedDiv7 except it is more simpler.
- Parameters
-
iter | value to visit |
negative | search for the negative divisor |
- Returns
- replaced Instruction, otherwise nullptr
◆ magicSignedDiv8neg()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::magicSignedDiv8neg |
( |
llvm::BasicBlock::iterator |
iter | ) |
const |
|
protected |
Wrapper of magicSignedDiv8 for negative values.
- Parameters
-
- Returns
- replaced Instruction, otherwise nullptr
◆ magicSignedDiv8pos()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::magicSignedDiv8pos |
( |
llvm::BasicBlock::iterator |
iter | ) |
const |
|
protected |
Wrapper of magicSignedDiv8 for positive values.
- Parameters
-
- Returns
- replaced Instruction, otherwise nullptr
◆ magicUnsignedDiv1()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::magicUnsignedDiv1 |
( |
llvm::BasicBlock::iterator |
iter | ) |
const |
|
protected |
Exchange (int32_t)((int64_t)X * (int64_t)magic_number >> N) with unsigned division
- Parameters
-
- Returns
- replaced Instruction, otherwise nullptr
◆ magicUnsignedDiv2()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::magicUnsignedDiv2 |
( |
llvm::BasicBlock::iterator |
iter | ) |
const |
|
protected |
Exchange int32_t y = 613566757 * (int64_t)x >> 32; res = ((x - y >> 1) + y) / 4; with unsigned division
- Parameters
-
- Returns
- replaced Instruction, otherwise nullptr
◆ signedMod1()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::signedMod1 |
( |
llvm::BasicBlock::iterator |
iter | ) |
const |
|
protected |
◆ signedMod2()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::signedMod2 |
( |
llvm::BasicBlock::iterator |
iter | ) |
const |
|
protected |
Exchange -k * (x / 16 - (int32_t)(x < 0)) + x; with x % k This idiom is similar to magicSignedDiv7pos.
- Parameters
-
- Returns
- replaced Instruction, otherwise nullptr
◆ unsignedMod()
Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::unsignedMod |
( |
llvm::BasicBlock::iterator |
iter | ) |
const |
|
protected |
Exchange x - x/k with x % k
- Parameters
-
- Returns
- replaced Instruction, otherwise nullptr
◆ IdiomsAnalysis
The documentation for this class was generated from the following files:
- /var/cache/acbs/build/acbs.6bu6osb6/retdec/include/retdec/bin2llvmir/optimizations/idioms/idioms_magicdivmod.h
- /var/cache/acbs/build/acbs.6bu6osb6/retdec/src/bin2llvmir/optimizations/idioms/idioms_magicdivmod.cpp