retdec
Public Member Functions | Static Public Member Functions | Public Attributes | Private Member Functions | Private Attributes | Static Private Attributes | Friends | List of all members
retdec::bin2llvmir::SymbolicTree Class Reference

#include <symbolic_tree.h>

Collaboration diagram for retdec::bin2llvmir::SymbolicTree:
Collaboration graph
[legend]

Public Member Functions

 SymbolicTree (const SymbolicTree &other)=default
 
 SymbolicTree (SymbolicTree &&other)=default
 
SymbolicTreeoperator= (SymbolicTree &&other)
 
bool operator== (const SymbolicTree &o) const
 
bool operator!= (const SymbolicTree &o) const
 
std::string print (unsigned indent=0) const
 
bool isNullary () const
 
bool isUnary () const
 
bool isBinary () const
 
bool isTernary () const
 
bool isNary (unsigned N) const
 
unsigned getLevel () const
 
void simplifyNode ()
 
void solveMemoryLoads (FileImage *image)
 
SymbolicTreegetMaxIntValue ()
 
std::vector< SymbolicTree * > getPreOrder () const
 
std::vector< SymbolicTree * > getPostOrder () const
 
std::vector< SymbolicTree * > getLevelOrder () const
 
 SymbolicTree (ReachingDefinitionsAnalysis *rda, llvm::Value *v, llvm::Value *u, unsigned nodeLevel, unsigned maxNodeLevel, std::map< llvm::Value *, llvm::Value * > *v2v, bool linear)
 

Static Public Member Functions

static SymbolicTree PrecomputedRda (ReachingDefinitionsAnalysis &rda, llvm::Value *v, unsigned maxNodeLevel=10)
 
static SymbolicTree PrecomputedRdaWithValueMap (ReachingDefinitionsAnalysis &rda, llvm::Value *v, std::map< llvm::Value *, llvm::Value * > *val2val, unsigned maxNodeLevel=10)
 
static SymbolicTree OnDemandRda (llvm::Value *v, unsigned maxNodeLevel=10)
 
static SymbolicTree Linear (llvm::Value *v, unsigned maxNodeLevel=10)
 
static void clear ()
 
static bool isVal2ValMapUsed ()
 
static void setAbi (Abi *abi)
 
static void setConfig (Config *config)
 
static void setToDefaultConfiguration ()
 
static void setTrackThroughAllocaLoads (bool b)
 
static void setTrackThroughGeneralRegisterLoads (bool b)
 
static void setTrackOnlyFlagRegisters (bool b)
 
static void setSimplifyAtCreation (bool b)
 
static void setNaryLimit (unsigned n)
 

Public Attributes

llvm::Value * value = nullptr
 
llvm::Value * user = nullptr
 
std::vector< SymbolicTreeops
 

Private Member Functions

void expandNode (ReachingDefinitionsAnalysis *RDA, std::map< llvm::Value *, llvm::Value * > *val2val, unsigned maxNodeLevel, bool linear)
 
void _simplifyNode ()
 
void fixLevel (unsigned level=0)
 
void _getPreOrder (std::vector< SymbolicTree * > &res) const
 
void _getPostOrder (std::vector< SymbolicTree * > &res) const
 

Private Attributes

unsigned _level = 1
 

Static Private Attributes

static Abi_abi = nullptr
 
static Config_config = nullptr
 
static bool _val2valUsed = false
 
static bool _trackThroughAllocaLoads = true
 
static bool _trackThroughGeneralRegisterLoads = true
 
static bool _trackOnlyFlagRegisters = false
 
static bool _simplifyAtCreation = true
 
static unsigned _naryLimit = 3
 

Friends

std::ostream & operator<< (std::ostream &out, const SymbolicTree &s)
 

Detailed Description

Tracking values through load/store operations using reaching definition analysis.

For optimization reasons, some data members of this structure are static, i.e. common for all instances. The typical usage of this class is: creation -> simplification -> pattern detection -> action based on pattern -> throwing away the current instance before creating and processing the new one. In such a case, global data members and global behaviour configuration is not a problem. If you, for whatever reason, want to store instances, keep this in mind.

Constructor & Destructor Documentation

◆ SymbolicTree() [1/3]

retdec::bin2llvmir::SymbolicTree::SymbolicTree ( const SymbolicTree other)
default

◆ SymbolicTree() [2/3]

retdec::bin2llvmir::SymbolicTree::SymbolicTree ( SymbolicTree &&  other)
default

◆ SymbolicTree() [3/3]

retdec::bin2llvmir::SymbolicTree::SymbolicTree ( ReachingDefinitionsAnalysis rda,
llvm::Value *  v,
llvm::Value *  u,
unsigned  nodeLevel,
unsigned  maxNodeLevel,
std::map< llvm::Value *, llvm::Value * > *  v2v,
bool  linear 
)

This is a private constructor, do not use it. It is made public only so it can be used in std::vector<>::emplace_back().

Member Function Documentation

◆ _getPostOrder()

void retdec::bin2llvmir::SymbolicTree::_getPostOrder ( std::vector< SymbolicTree * > &  res) const
private

◆ _getPreOrder()

void retdec::bin2llvmir::SymbolicTree::_getPreOrder ( std::vector< SymbolicTree * > &  res) const
private

◆ _simplifyNode()

void retdec::bin2llvmir::SymbolicTree::_simplifyNode ( )
private

◆ clear()

void retdec::bin2llvmir::SymbolicTree::clear ( )
static

◆ expandNode()

void retdec::bin2llvmir::SymbolicTree::expandNode ( ReachingDefinitionsAnalysis RDA,
std::map< llvm::Value *, llvm::Value * > *  val2val,
unsigned  maxNodeLevel,
bool  linear 
)
private

◆ fixLevel()

void retdec::bin2llvmir::SymbolicTree::fixLevel ( unsigned  level = 0)
private

◆ getLevel()

unsigned retdec::bin2llvmir::SymbolicTree::getLevel ( ) const

◆ getLevelOrder()

std::vector< SymbolicTree * > retdec::bin2llvmir::SymbolicTree::getLevelOrder ( ) const
Returns
Tree nodes linearized using a level-order traversal.

◆ getMaxIntValue()

SymbolicTree * retdec::bin2llvmir::SymbolicTree::getMaxIntValue ( )

◆ getPostOrder()

std::vector< SymbolicTree * > retdec::bin2llvmir::SymbolicTree::getPostOrder ( ) const
Returns
Tree nodes linearized using a post-order traversal.
Note
See note for getPreOrder(). The same holds here – you may damage vector's consistency if you make changes to nodes as you iterate over them. However, thanks to the bottom-up nature of post-order traversal, this may not be a problem if you modify only the actual node and its children – they were already iterated over.

◆ getPreOrder()

std::vector< SymbolicTree * > retdec::bin2llvmir::SymbolicTree::getPreOrder ( ) const
Returns
Tree nodes linearized using a pre-order traversal.
Note
You can change the nodes (they are not constant) but keep in mind that your changes might make the vector inconsistent – i.e. changes you make are not reflected in it. For example, if you change children of some node and then continue to iterate over the vector, vector elements will not be the real children after the change. Post-order vector is much more suitable for modifications.

◆ isBinary()

bool retdec::bin2llvmir::SymbolicTree::isBinary ( ) const

◆ isNary()

bool retdec::bin2llvmir::SymbolicTree::isNary ( unsigned  N) const

◆ isNullary()

bool retdec::bin2llvmir::SymbolicTree::isNullary ( ) const

◆ isTernary()

bool retdec::bin2llvmir::SymbolicTree::isTernary ( ) const

◆ isUnary()

bool retdec::bin2llvmir::SymbolicTree::isUnary ( ) const

◆ isVal2ValMapUsed()

bool retdec::bin2llvmir::SymbolicTree::isVal2ValMapUsed ( )
static

◆ Linear()

SymbolicTree retdec::bin2llvmir::SymbolicTree::Linear ( llvm::Value *  v,
unsigned  maxNodeLevel = 10 
)
static

A lightweight construction method where no RDA is used. Tree is successfully constructed only if it can be fully expanded using only linear control flow backtracking.

◆ OnDemandRda()

SymbolicTree retdec::bin2llvmir::SymbolicTree::OnDemandRda ( llvm::Value *  v,
unsigned  maxNodeLevel = 10 
)
static

SymbolicTree is constructed using on demand RDA features. I.e. RDA is not precomputed, but it is constructed as needed. This is useful if control flow changes between tree computations (i.e. RDA gets invalid), or if only a few trees need to be constructed. Otherwise, it is much more efficient to precompute RDA before trees are constructed.

◆ operator!=()

bool retdec::bin2llvmir::SymbolicTree::operator!= ( const SymbolicTree o) const

◆ operator=()

SymbolicTree & retdec::bin2llvmir::SymbolicTree::operator= ( SymbolicTree &&  other)

◆ operator==()

bool retdec::bin2llvmir::SymbolicTree::operator== ( const SymbolicTree o) const

◆ PrecomputedRda()

SymbolicTree retdec::bin2llvmir::SymbolicTree::PrecomputedRda ( ReachingDefinitionsAnalysis rda,
llvm::Value *  v,
unsigned  maxNodeLevel = 10 
)
static

The basic SymbolicTree construction method uses a precomputed Reaching Definition Analysis (RDA) in order to fully expand the value in question up to the maximal tree node level.

◆ PrecomputedRdaWithValueMap()

SymbolicTree retdec::bin2llvmir::SymbolicTree::PrecomputedRdaWithValueMap ( ReachingDefinitionsAnalysis rda,
llvm::Value *  v,
std::map< llvm::Value *, llvm::Value * > *  val2val,
unsigned  maxNodeLevel = 10 
)
static

The same as the basic SymbolicTree construction method, but an additional value to value mapping is used for node expansion. If the node to be expanded is a key in the map, an associated value is used as its expansion. Otherwise, the node is expanded as usual.

◆ print()

std::string retdec::bin2llvmir::SymbolicTree::print ( unsigned  indent = 0) const

◆ setAbi()

void retdec::bin2llvmir::SymbolicTree::setAbi ( Abi abi)
static

◆ setConfig()

void retdec::bin2llvmir::SymbolicTree::setConfig ( Config config)
static

◆ setNaryLimit()

void retdec::bin2llvmir::SymbolicTree::setNaryLimit ( unsigned  n)
static

◆ setSimplifyAtCreation()

void retdec::bin2llvmir::SymbolicTree::setSimplifyAtCreation ( bool  b)
static

◆ setToDefaultConfiguration()

void retdec::bin2llvmir::SymbolicTree::setToDefaultConfiguration ( )
static

◆ setTrackOnlyFlagRegisters()

void retdec::bin2llvmir::SymbolicTree::setTrackOnlyFlagRegisters ( bool  b)
static

◆ setTrackThroughAllocaLoads()

void retdec::bin2llvmir::SymbolicTree::setTrackThroughAllocaLoads ( bool  b)
static

◆ setTrackThroughGeneralRegisterLoads()

void retdec::bin2llvmir::SymbolicTree::setTrackThroughGeneralRegisterLoads ( bool  b)
static

◆ simplifyNode()

void retdec::bin2llvmir::SymbolicTree::simplifyNode ( )

◆ solveMemoryLoads()

void retdec::bin2llvmir::SymbolicTree::solveMemoryLoads ( FileImage image)

If at address 33888 in image is value 76092 then transform: >| u6_83f0 = load i32, i32* inttoptr (i32 33888 to i32*), align 32 >| i32 33888 Into: >| 76092

Friends And Related Function Documentation

◆ operator<<

std::ostream& operator<< ( std::ostream &  out,
const SymbolicTree s 
)
friend

Member Data Documentation

◆ _abi

Abi * retdec::bin2llvmir::SymbolicTree::_abi = nullptr
staticprivate

◆ _config

Config * retdec::bin2llvmir::SymbolicTree::_config = nullptr
staticprivate

◆ _level

unsigned retdec::bin2llvmir::SymbolicTree::_level = 1
private

◆ _naryLimit

unsigned retdec::bin2llvmir::SymbolicTree::_naryLimit = 3
staticprivate

◆ _simplifyAtCreation

bool retdec::bin2llvmir::SymbolicTree::_simplifyAtCreation = true
staticprivate

◆ _trackOnlyFlagRegisters

bool retdec::bin2llvmir::SymbolicTree::_trackOnlyFlagRegisters = false
staticprivate

◆ _trackThroughAllocaLoads

bool retdec::bin2llvmir::SymbolicTree::_trackThroughAllocaLoads = true
staticprivate

◆ _trackThroughGeneralRegisterLoads

bool retdec::bin2llvmir::SymbolicTree::_trackThroughGeneralRegisterLoads = true
staticprivate

◆ _val2valUsed

bool retdec::bin2llvmir::SymbolicTree::_val2valUsed = false
staticprivate

◆ ops

std::vector<SymbolicTree> retdec::bin2llvmir::SymbolicTree::ops

◆ user

llvm::Value* retdec::bin2llvmir::SymbolicTree::user = nullptr

◆ value

llvm::Value* retdec::bin2llvmir::SymbolicTree::value = nullptr

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