retdec
Protected Member Functions | Private Member Functions | Static Private Member Functions | Friends | List of all members
retdec::bin2llvmir::IdiomsMagicDivMod Class Reference

Division and modulo using magic number. More...

#include <idioms_magicdivmod.h>

Inheritance diagram for retdec::bin2llvmir::IdiomsMagicDivMod:
Inheritance graph
[legend]
Collaboration diagram for retdec::bin2llvmir::IdiomsMagicDivMod:
Collaboration graph
[legend]

Protected Member Functions

llvm::Instruction * magicUnsignedDiv1 (llvm::BasicBlock::iterator iter) const
 
llvm::Instruction * magicUnsignedDiv2 (llvm::BasicBlock::iterator iter) const
 
llvm::Instruction * magicSignedDiv1 (llvm::BasicBlock::iterator iter) const
 
llvm::Instruction * magicSignedDiv2 (llvm::BasicBlock::iterator iter) const
 
llvm::Instruction * magicSignedDiv3 (llvm::BasicBlock::iterator iter) const
 
llvm::Instruction * magicSignedDiv4 (llvm::BasicBlock::iterator iter) const
 
llvm::Instruction * magicSignedDiv5 (llvm::BasicBlock::iterator iter) const
 
llvm::Instruction * magicSignedDiv6 (llvm::BasicBlock::iterator iter) const
 
llvm::Instruction * magicSignedDiv7pos (llvm::BasicBlock::iterator iter) const
 
llvm::Instruction * magicSignedDiv7neg (llvm::BasicBlock::iterator iter) const
 
llvm::Instruction * magicSignedDiv8pos (llvm::BasicBlock::iterator iter) const
 
llvm::Instruction * magicSignedDiv8neg (llvm::BasicBlock::iterator iter) const
 
llvm::Instruction * signedMod1 (llvm::BasicBlock::iterator iter) const
 
llvm::Instruction * signedMod2 (llvm::BasicBlock::iterator iter) const
 
llvm::Instruction * unsignedMod (llvm::BasicBlock::iterator iter) const
 
- Protected Member Functions inherited from retdec::bin2llvmir::IdiomsAbstract
 IdiomsAbstract ()
 
void init (llvm::Module *M, CC_compiler cc, CC_arch arch)
 
CC_compiler getCompiler () const
 
CC_arch getArch () const
 
llvm::Module * getModule () const
 
virtual bool doAnalysis (llvm::Function &, llvm::Pass *)=0
 
virtual ~IdiomsAbstract ()=default
 
bool findBranchDependingOn (llvm::BranchInst **br, llvm::BasicBlock &bb, const llvm::Value *val) const
 

Private Member Functions

llvm::Instruction * magicSignedDiv7 (llvm::BasicBlock::iterator iter, bool negative) const
 
llvm::Instruction * magicSignedDiv8 (llvm::BasicBlock::iterator iter, bool negative) const
 

Static Private Member Functions

static unsigned divisorByMagicNumberUnsigned (unsigned magic_number, unsigned sh_pre, unsigned sh_post)
 
static unsigned divisorByMagicNumberUnsigned2 (unsigned magic_number, unsigned sh_post)
 
static int divisorByMagicNumberSigned (int magic_number, unsigned sh_post)
 
static int divisorByMagicNumberSigned2 (int magic_number, unsigned sh_post)
 
static unsigned divisorByMagicNumberSigned3 (unsigned magic_number, unsigned shift)
 
static unsigned divisorByMagicNumberSigned4 (unsigned magic_number, unsigned shift)
 

Friends

class IdiomsAnalysis
 

Additional Inherited Members

- Static Protected Member Functions inherited from retdec::bin2llvmir::IdiomsAbstract
static void eraseInstFromBasicBlock (llvm::Value *val, llvm::BasicBlock *bb)
 
static bool isPowerOfTwo (unsigned x)
 
static bool isPowerOfTwoRepresentable (const llvm::ConstantInt *cnst)
 

Detailed Description

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

Member Function Documentation

◆ divisorByMagicNumberSigned()

int retdec::bin2llvmir::IdiomsMagicDivMod::divisorByMagicNumberSigned ( int  magic_number,
unsigned  sh_post 
)
staticprivate

Calculate original divisor from ‘signed magic number multiplication’ form.

Parameters
magic_numbera magic number used when multiply
sh_posta 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_numbera magic number used when multiply
sh_posta 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_numbera magic number used when multiply
shifta 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_numbera magic number used when multiply
shifta 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_numbera magic number used when multiply
sh_prea shift before multiplication
sh_posta 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_numbera magic number used when multiply
sh_posta 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
itervalue to visit
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
itervalue to visit
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
itervalue to visit
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
itervalue to visit
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
itervalue to visit
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
itervalue to visit
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
itervalue to visit
negativesearch 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
itervalue to visit
Returns
replaced Instruction, otherwise nullptr

◆ magicSignedDiv7pos()

Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::magicSignedDiv7pos ( llvm::BasicBlock::iterator  iter) const
protected

Wrapper of magicSignedDiv7 for positive values.

Parameters
itervalue to visit
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
itervalue to visit
negativesearch 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
itervalue to visit
Returns
replaced Instruction, otherwise nullptr

◆ magicSignedDiv8pos()

Instruction * retdec::bin2llvmir::IdiomsMagicDivMod::magicSignedDiv8pos ( llvm::BasicBlock::iterator  iter) const
protected

Wrapper of magicSignedDiv8 for positive values.

Parameters
itervalue to visit
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
itervalue to visit
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
itervalue to visit
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
itervalue to visit
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
itervalue to visit
Returns
replaced Instruction, otherwise nullptr

Friends And Related Function Documentation

◆ IdiomsAnalysis

friend class IdiomsAnalysis
friend

The documentation for this class was generated from the following files: