use_def_analysis

This modules computes def-uses chains for a subset of the registers (defined in track_register). and only if those chains are related eventually to an access to memory.

-‘def’ computes definitions of registers at each of the locations.

-‘def_used_for_address’ compute the set of live uses backwards at each of the locations.

However, it only computes uses starting at accesses to memory.

-‘def_used’ intersects the two previous facts to obtain def-use chains.

The traversal of def_used_for_address is kept intra-procedural (not following call edges).

local_next(ea:address, ea_next:address)

WARNING: Predicate not present in compiled Datalog program (Dead Code)

block_instruction_next(Block:address, Before:address, After:address)

next() for each instruction within a block.

inter_procedural_edge(Src:address, Dest:address)

block_next(Block:address, BlockEnd:address, NextBlock:address)

call_uses_reg(Call:address, Reg:register)

‘Call’ implicitly uses ‘Reg’, such as register parameters.

WARNING: Predicate not present in compiled Datalog program (Dead Code)

flow_def(EA:address, Var:T, EA_next:address, Value:number)

A <T> is implicitly defined by being compared to a constant and then jumping this definition only takes place in between the jump and the target that implies equality

ea_propagates_def(EA:address, Var:T)

A Var <T> can propagate through the instruction at EA.

Intended to be extended by child components to modify behavior of AdvancedDefUsed.

WARNING: Predicate not present in compiled Datalog program (Dead Code)

block_propagates_def(Block:address, Var:T)

A Var <T> can propagate through Block.

WARNING: Predicate not present in compiled Datalog program (Dead Code)

defined_in_block(Block:address, Var:T)

A Var <T> is defined in the Block

used_in_block(Block:address, EA_used:address, Var:T, Index:operand_index)

A Var <T> is used in the Block

block_last_def(EA:address, EA_def:address, Var:T)

The last address prior to EA where Var was defined within the block

last_def_in_block(Block:address, EA_def:address, Var:T)

The last definition(s) of <T> in a given block.

Multiple are possible in conditional cases.

ref_in_block(Block:address, Var:T)

A <T> is referenced in a block

live_var_def(Block:address, VarIdentity:T, LiveVar:T, EA_def:address)

A <T> is defined in a block, and is still live at the end of the block.

This can potentially be paired with a live_var_used if there is a path between the Blocks.

live_var_used(Block:address, LiveVar:T, UsedVar:T, EA_used:address, Index:operand_index, Moves:unsigned)

A <T> is used in a block, but a live definition for that use is not found within the block.

We consider a <T> to be live only if it is live for interblock edges. Intrablock cases are handled directly by the def_used relation.

To find the definition for this use, live_var_at_block_end will have to propagate backward from the block.

The Moves field, used only by stack var tracking, tracks the number of basic blocks that perform a stack variable transformation (where a stack variable descriptor is adjusted due to a change in the stack pointer). This prevents infinite loops.

live_var_at_block_end(Block:address, BlockUsed:address, Var:T)

The <T> is live at the end of Block, and will be used in BlockUsed.

Propagates backward from usages to search for defs.

This is faster than propagating forward from defs, since a used value should always be defined in well-behaved code. In addition, we know to stop propagating once the definition is found.

The alternative strategy of propagating forward from defs means that it must propagate indefinitely, in case it is used multiple times. Further, side-effect definitions are often unused.

To further optimize this strategy, if another use is encountered, we don’t propagate any further. Later, the relation live_var_at_prior_used() propagates defs forward through adjacent uses.

live_var_at_prior_used(EA_used:address, BlockUsed:address, Var:T)

The <T> is live at EA_used and at the beginning of BlockUsed, and holds the same value from the same definition. The <T> is used in BlockUsed.

Forms an edge between two used() that depend on the same def.

return_val_used(EA_call:address, Callee:address, Reg:register, EA_used:address, Index_used:operand_index)

A value returned from a function is used.

return_block_end(Callee:address, CalleeEnd:address, Block:address, BlockEnd:address)

A value is returned from a called procedure Callee, from the last Block with the last instruction at BlockEnd.

def_used(EA_def:address, Var:register, EA_used:address, Index_used:operand_index)

A <T> is defined in ‘EA_def’ and used in ‘EA_used’ in the operand with index ‘Index_used’

adjusts_stack_in_block(Block:address, EA:address, BaseReg:register, Offset:number)

An offset is added to a stack pointer register at EA.

stack_base_reg_move(Block:address, EA:address, Src:register, Dst:register)

A stack base register is moved to another potential stack base register.

def_used(EA_def:address, VarDef:stack_var, EA_used:address, VarUsed:stack_var, Index_used:operand_index)

A stack is defined in ‘EA_def’ and used in ‘EA_used’ in the operand with index ‘Index_used’

live_var_used_in_block(Block:address, EA:address, LiveVar:stack_var, UsedVar:stack_var, EA_used:address, Index:operand_index, Moves:unsigned)

Propagate live uses backwards within a block on a per-instruction basis.

moves_limit(Moves:unsigned)

Specify the number of moves of the stack register (the stack pointer or the frame pointer) that are tracked in the def-use stack analysis. This parameters is used to ensure rapid convergence

reg_used_for(EA:address, Reg:register, Type:symbol)

  • The register ‘Reg’ used as an address at address ‘EA’.

def_used_for_address(EA_def:address, Reg:register, Type:symbol)

  • The register ‘Reg’ as defined at address ‘EA_def’ is later used either as an address

  • or to compute an address.