value_analysis

value_reg_edge(EA:address, Reg:register, EA_reg1:address, Reg1:register, Multiplier:number, Offset:number)

This module performs a basic value analysis.

The value of a register at a point (ea) is expressed as the value of another at another point (EA_reg1) multiplied by a multiplier plus an offset:

val(Reg,EA) = val(Reg1,EA_reg1)* Multiplier+ Offset

In some cases we can obtain a term of the form:

val(Reg,EA) = Offset

If we can obtain that the register is assigned a constant

val(Reg,EA) = Unknown * Multiplier+ Offset

If we detect a loop where the register gets incremented ‘Multiplier’ in each iteration

The analysis first computes value_reg_edge which are facts of the form above defined for different instruction and using the def-use chains.

Then, we have a propagation phase where value_reg is computed. This phase chains individual value_reg_edge together. In addition to chaining edges together it takes care of cases such as two registers added together or substracted if it turns out that they can be expressed in terms of the same register. It also detects possible loops.

This propagation is limited in the number of steps using step_limit to ensure termination and efficiency.

As a result, we might obtain more than one ‘value’ for a certain register at a certain location. best_value_reg selects only one of these values prioritizing the two special cases from above (constant or loop) and considering the value with most steps.

Uses: arch.memory_access, arch.move_reg_reg, arch.reg_arithmetic_operation, instruction, instruction_get_dest_op, next, op_regdirect_contains_reg, track_register

Recursive: cmp_defines, first_block_in_byte_interval, overlapping_instruction, split_load_for_symbolization, relocation_adjustment, call_tls_get_addr, simple_data_access_pattern, reg_def_use.def_used, base_relative_operand, split_load_total_points, block, litpool_confidence, reg_has_got, value_reg_limit, stack_def_use.live_var_used, split_load_point, split_load_operand, flags_and_jump_pair, wis_schedule_iter, unresolved_interval, code_in_block, compare_and_jump_indirect_op_valid, __agg_subclause3, inferred_main_in_reg, reg_used_for, is_padding, resolved_reaches, compare_and_jump_indirect, __agg_subclause2, padding_block_candidate, reg_reg_arithmetic_operation_defs, def_used_for_address, impossible_block, plt_block, arm_jump_table_block_instruction, composite_data_access, possible_target_from, jump_table_candidate_refined, base_relative_operation, split_load, __agg_single3, reg_has_base_image, no_value_reg_limit, relative_address_start, wis_schedule, plt_entry, reg_def_use.used_in_block, adjusts_stack_in_block, possible_target, initialized_data_segment, reg_def_use.live_var_at_block_end, cmp_reg_to_reg, indefinite_litpool_ref, negative_block_heuristic, contains_implausible_instr_seq, indexed_pc_relative_load, next_block_in_byte_interval, code_in_block_candidate, symbolic_expr_from_relocation, unlikely_have_symbolic_immediate, incomplete_block, arm_jump_table_data_block_limit, inferred_main_dispatch, arch.simple_data_load, data_block_limit, block_total_points, invalid_jump_table_candidate, stack_def_use.live_var_def, reg_def_use.live_var_def, arm_jump_table_block_start, block_overlap, stack_base_reg_move, may_fallthrough, __agg_single2, block_heuristic, __agg_subclause9, block_implies_block, segment_target_range, stack_def_use.live_var_at_prior_used, cinf_ldr_add_pc, no_return_call_propagated, unresolved_block_overlap, jump_table_max, common_tail, unresolved_interval_order, tls_get_addr, block_points_proportional, likely_fallthrough, block_boundaries, jump_table_element_access, block_points, invalid, jump_table_target, reg_def_use.used, arm_jump_table_candidate, reg_def_use.live_var_at_prior_used, no_return_call, arm_jump_table_skip_first_entry, stack_def_use.defined_in_block, split_load_conflict, arm_jump_table_candidate_start, stack_def_use.live_var_at_block_end, reg_def_use.last_def_in_block, arm_jump_table_cmp_limit, data_in_code, candidate_block_is_not_padding, inter_procedural_edge, known_block, instruction_memory_access_size, overlap_with_litpool, block_limit, function_inference.function_entry_initial, init_symbol_minus_symbol_candidate_arm, const_value_reg_used, self_contained_segment, stack_def_use.last_def_in_block, must_fallthrough, straight_line_last_def, padding_block_limit, jump_table_candidate, no_return_call_refined, block_candidate_dependency_edge, split_load_candidate, stack_def_use.block_last_def, last_value_reg_limit, relative_address, no_return_block, litpool_ref, symbol_minus_symbol_litpool_access_pattern, block_last_instruction, gp_relative_operand, data_in_code_propagate, block_candidate_boundaries, basic_target, compare_and_jump_immediate, wis_memo, __agg_subclause6, nop_in_padding_candidate, reg_def_use.defined_in_block, __agg_single6, relocation_adjustment_total, candidate_block_is_padding, wis_prior, reg_def_use.live_var_used, __agg_subclause7, wis_has_prior, compare_and_jump_register, block_instruction_next, arm_jump_table_data_block, value_reg, contains_plausible_instr_seq, relative_jump_table_entry_candidate, adrp_used, stack_def_use.def_used, got_relative_operand, __agg_subclause10, value_reg_edge, arch.reg_relative_load, reg_def_use.flow_def, hi_load_prop, jump_table_start, branch_to_calculated_pc_rel_addr, tls_desc_call, discarded_block, stack_def_use.live_var_used_in_block, data_segment, value_reg_unsupported, block_next, discarded_split_load, indexed_pc_relative_load_relative, litpool_symbolic_operand, data_block_candidate, reg_def_use.return_block_end, code_in_block_candidate_refined, after_end, jump_table_signed, reg_def_use.block_last_def, base_relative_jump, unresolved_interval_best_block, straight_line_def_used, unresolved_block, data_access, correlated_live_reg, jump_table_prelude, litpool_boundaries, init_ldr_add_pc, arch.extend_load, stack_def_use.used_in_block, stack_def_use.ref_in_block, reg_def_use.ref_in_block, reg_def_use.return_val_used

value_reg(EA:address, Reg:register, EA_reg1:address, Reg1:reg_nullable, Multiplier:number, Offset:number, Steps:unsigned)

best_value_reg(EA:address, Reg:register, EA_from:address, Multiplier:number, Offset:number, type:symbol)

bshru_wrapper(Lhs:number, Rhs:number, Res:number)

For logical right shift in 32-bit ISA, the LHS value’s upper 32-bit needs to be masked out.

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

value_reg_unsupported(EA:address, Reg:register)

A register is defined using an unknown value This predicate is used to create trivial leaf edges in the value_reg graph step_limit .

Uses: arch.call, arch.memory_access, arch.move_reg_reg, track_register

Recursive: cmp_defines, first_block_in_byte_interval, overlapping_instruction, split_load_for_symbolization, relocation_adjustment, call_tls_get_addr, simple_data_access_pattern, reg_def_use.def_used, base_relative_operand, split_load_total_points, block, litpool_confidence, reg_has_got, value_reg_limit, stack_def_use.live_var_used, split_load_point, split_load_operand, flags_and_jump_pair, wis_schedule_iter, unresolved_interval, code_in_block, compare_and_jump_indirect_op_valid, __agg_subclause3, inferred_main_in_reg, reg_used_for, is_padding, resolved_reaches, compare_and_jump_indirect, __agg_subclause2, padding_block_candidate, reg_reg_arithmetic_operation_defs, def_used_for_address, impossible_block, plt_block, arm_jump_table_block_instruction, composite_data_access, possible_target_from, jump_table_candidate_refined, base_relative_operation, split_load, __agg_single3, reg_has_base_image, no_value_reg_limit, relative_address_start, wis_schedule, plt_entry, reg_def_use.used_in_block, adjusts_stack_in_block, possible_target, initialized_data_segment, reg_def_use.live_var_at_block_end, cmp_reg_to_reg, indefinite_litpool_ref, negative_block_heuristic, contains_implausible_instr_seq, indexed_pc_relative_load, next_block_in_byte_interval, code_in_block_candidate, symbolic_expr_from_relocation, unlikely_have_symbolic_immediate, incomplete_block, arm_jump_table_data_block_limit, inferred_main_dispatch, arch.simple_data_load, data_block_limit, block_total_points, invalid_jump_table_candidate, stack_def_use.live_var_def, reg_def_use.live_var_def, arm_jump_table_block_start, block_overlap, stack_base_reg_move, may_fallthrough, __agg_single2, block_heuristic, __agg_subclause9, block_implies_block, segment_target_range, stack_def_use.live_var_at_prior_used, cinf_ldr_add_pc, no_return_call_propagated, unresolved_block_overlap, jump_table_max, common_tail, unresolved_interval_order, tls_get_addr, block_points_proportional, likely_fallthrough, block_boundaries, jump_table_element_access, block_points, invalid, jump_table_target, reg_def_use.used, arm_jump_table_candidate, reg_def_use.live_var_at_prior_used, no_return_call, arm_jump_table_skip_first_entry, stack_def_use.defined_in_block, split_load_conflict, arm_jump_table_candidate_start, stack_def_use.live_var_at_block_end, reg_def_use.last_def_in_block, arm_jump_table_cmp_limit, data_in_code, candidate_block_is_not_padding, inter_procedural_edge, known_block, instruction_memory_access_size, overlap_with_litpool, block_limit, function_inference.function_entry_initial, init_symbol_minus_symbol_candidate_arm, const_value_reg_used, self_contained_segment, stack_def_use.last_def_in_block, must_fallthrough, straight_line_last_def, padding_block_limit, jump_table_candidate, no_return_call_refined, block_candidate_dependency_edge, split_load_candidate, stack_def_use.block_last_def, last_value_reg_limit, relative_address, no_return_block, litpool_ref, symbol_minus_symbol_litpool_access_pattern, block_last_instruction, gp_relative_operand, data_in_code_propagate, block_candidate_boundaries, basic_target, compare_and_jump_immediate, wis_memo, __agg_subclause6, nop_in_padding_candidate, reg_def_use.defined_in_block, __agg_single6, relocation_adjustment_total, candidate_block_is_padding, wis_prior, reg_def_use.live_var_used, __agg_subclause7, wis_has_prior, compare_and_jump_register, block_instruction_next, arm_jump_table_data_block, value_reg, contains_plausible_instr_seq, relative_jump_table_entry_candidate, adrp_used, stack_def_use.def_used, got_relative_operand, __agg_subclause10, value_reg_edge, arch.reg_relative_load, reg_def_use.flow_def, hi_load_prop, jump_table_start, branch_to_calculated_pc_rel_addr, tls_desc_call, discarded_block, stack_def_use.live_var_used_in_block, data_segment, value_reg_unsupported, block_next, discarded_split_load, indexed_pc_relative_load_relative, litpool_symbolic_operand, data_block_candidate, reg_def_use.return_block_end, code_in_block_candidate_refined, after_end, jump_table_signed, reg_def_use.block_last_def, base_relative_jump, unresolved_interval_best_block, straight_line_def_used, unresolved_block, data_access, correlated_live_reg, jump_table_prelude, litpool_boundaries, init_ldr_add_pc, arch.extend_load, stack_def_use.used_in_block, stack_def_use.ref_in_block, reg_def_use.ref_in_block, reg_def_use.return_val_used

step_limit(Limit:unsigned)

reg_reg_arithmetic_operation_defs(EA:address, Reg_def:register, EA_def1:address, Reg1:register, EA_def2:address, Reg2:register, Mult:number, Offset:number)

This is an auxiliary predicate used for computing value_reg. It captures an instruction at EA that defines register Reg_def by operating with two register Reg1 and Reg2 defined at EA_def1 and EA_def1.

The operation is Reg_def = Reg1 + Reg2 * Mult + Offset.

Uses: arch.reg_reg_arithmetic_operation

Recursive: cmp_defines, first_block_in_byte_interval, overlapping_instruction, split_load_for_symbolization, relocation_adjustment, call_tls_get_addr, simple_data_access_pattern, reg_def_use.def_used, base_relative_operand, split_load_total_points, block, litpool_confidence, reg_has_got, value_reg_limit, stack_def_use.live_var_used, split_load_point, split_load_operand, flags_and_jump_pair, wis_schedule_iter, unresolved_interval, code_in_block, compare_and_jump_indirect_op_valid, __agg_subclause3, inferred_main_in_reg, reg_used_for, is_padding, resolved_reaches, compare_and_jump_indirect, __agg_subclause2, padding_block_candidate, reg_reg_arithmetic_operation_defs, def_used_for_address, impossible_block, plt_block, arm_jump_table_block_instruction, composite_data_access, possible_target_from, jump_table_candidate_refined, base_relative_operation, split_load, __agg_single3, reg_has_base_image, no_value_reg_limit, relative_address_start, wis_schedule, plt_entry, reg_def_use.used_in_block, adjusts_stack_in_block, possible_target, initialized_data_segment, reg_def_use.live_var_at_block_end, cmp_reg_to_reg, indefinite_litpool_ref, negative_block_heuristic, contains_implausible_instr_seq, indexed_pc_relative_load, next_block_in_byte_interval, code_in_block_candidate, symbolic_expr_from_relocation, unlikely_have_symbolic_immediate, incomplete_block, arm_jump_table_data_block_limit, inferred_main_dispatch, arch.simple_data_load, data_block_limit, block_total_points, invalid_jump_table_candidate, stack_def_use.live_var_def, reg_def_use.live_var_def, arm_jump_table_block_start, block_overlap, stack_base_reg_move, may_fallthrough, __agg_single2, block_heuristic, __agg_subclause9, block_implies_block, segment_target_range, stack_def_use.live_var_at_prior_used, cinf_ldr_add_pc, no_return_call_propagated, unresolved_block_overlap, jump_table_max, common_tail, unresolved_interval_order, tls_get_addr, block_points_proportional, likely_fallthrough, block_boundaries, jump_table_element_access, block_points, invalid, jump_table_target, reg_def_use.used, arm_jump_table_candidate, reg_def_use.live_var_at_prior_used, no_return_call, arm_jump_table_skip_first_entry, stack_def_use.defined_in_block, split_load_conflict, arm_jump_table_candidate_start, stack_def_use.live_var_at_block_end, reg_def_use.last_def_in_block, arm_jump_table_cmp_limit, data_in_code, candidate_block_is_not_padding, inter_procedural_edge, known_block, instruction_memory_access_size, overlap_with_litpool, block_limit, function_inference.function_entry_initial, init_symbol_minus_symbol_candidate_arm, const_value_reg_used, self_contained_segment, stack_def_use.last_def_in_block, must_fallthrough, straight_line_last_def, padding_block_limit, jump_table_candidate, no_return_call_refined, block_candidate_dependency_edge, split_load_candidate, stack_def_use.block_last_def, last_value_reg_limit, relative_address, no_return_block, litpool_ref, symbol_minus_symbol_litpool_access_pattern, block_last_instruction, gp_relative_operand, data_in_code_propagate, block_candidate_boundaries, basic_target, compare_and_jump_immediate, wis_memo, __agg_subclause6, nop_in_padding_candidate, reg_def_use.defined_in_block, __agg_single6, relocation_adjustment_total, candidate_block_is_padding, wis_prior, reg_def_use.live_var_used, __agg_subclause7, wis_has_prior, compare_and_jump_register, block_instruction_next, arm_jump_table_data_block, value_reg, contains_plausible_instr_seq, relative_jump_table_entry_candidate, adrp_used, stack_def_use.def_used, got_relative_operand, __agg_subclause10, value_reg_edge, arch.reg_relative_load, reg_def_use.flow_def, hi_load_prop, jump_table_start, branch_to_calculated_pc_rel_addr, tls_desc_call, discarded_block, stack_def_use.live_var_used_in_block, data_segment, value_reg_unsupported, block_next, discarded_split_load, indexed_pc_relative_load_relative, litpool_symbolic_operand, data_block_candidate, reg_def_use.return_block_end, code_in_block_candidate_refined, after_end, jump_table_signed, reg_def_use.block_last_def, base_relative_jump, unresolved_interval_best_block, straight_line_def_used, unresolved_block, data_access, correlated_live_reg, jump_table_prelude, litpool_boundaries, init_ldr_add_pc, arch.extend_load, stack_def_use.used_in_block, stack_def_use.ref_in_block, reg_def_use.ref_in_block, reg_def_use.return_val_used

value_reg_max_mult(EA:address, Reg:register, MaxMult:number)

const_value_reg_used(UsedEA:address, EADef:address, EARegDef:address, Reg:register, Value:number)

A constant value is used in a data access.

EADef: The address where Value was originally defined (which may not necessarily be where Reg is defined, if that value is moved to a different register later).

EARegDef: The address where Reg is defined as Value. Often EADef = EARegDef.

Used by: symbolic_operand_attribute, symbolic_operand_candidate, tls_relative_operand

Recursive: cmp_defines, first_block_in_byte_interval, overlapping_instruction, split_load_for_symbolization, relocation_adjustment, call_tls_get_addr, simple_data_access_pattern, reg_def_use.def_used, base_relative_operand, split_load_total_points, block, litpool_confidence, reg_has_got, value_reg_limit, stack_def_use.live_var_used, split_load_point, split_load_operand, flags_and_jump_pair, wis_schedule_iter, unresolved_interval, code_in_block, compare_and_jump_indirect_op_valid, __agg_subclause3, inferred_main_in_reg, reg_used_for, is_padding, resolved_reaches, compare_and_jump_indirect, __agg_subclause2, padding_block_candidate, reg_reg_arithmetic_operation_defs, def_used_for_address, impossible_block, plt_block, arm_jump_table_block_instruction, composite_data_access, possible_target_from, jump_table_candidate_refined, base_relative_operation, split_load, __agg_single3, reg_has_base_image, no_value_reg_limit, relative_address_start, wis_schedule, plt_entry, reg_def_use.used_in_block, adjusts_stack_in_block, possible_target, initialized_data_segment, reg_def_use.live_var_at_block_end, cmp_reg_to_reg, indefinite_litpool_ref, negative_block_heuristic, contains_implausible_instr_seq, indexed_pc_relative_load, next_block_in_byte_interval, code_in_block_candidate, symbolic_expr_from_relocation, unlikely_have_symbolic_immediate, incomplete_block, arm_jump_table_data_block_limit, inferred_main_dispatch, arch.simple_data_load, data_block_limit, block_total_points, invalid_jump_table_candidate, stack_def_use.live_var_def, reg_def_use.live_var_def, arm_jump_table_block_start, block_overlap, stack_base_reg_move, may_fallthrough, __agg_single2, block_heuristic, __agg_subclause9, block_implies_block, segment_target_range, stack_def_use.live_var_at_prior_used, cinf_ldr_add_pc, no_return_call_propagated, unresolved_block_overlap, jump_table_max, common_tail, unresolved_interval_order, tls_get_addr, block_points_proportional, likely_fallthrough, block_boundaries, jump_table_element_access, block_points, invalid, jump_table_target, reg_def_use.used, arm_jump_table_candidate, reg_def_use.live_var_at_prior_used, no_return_call, arm_jump_table_skip_first_entry, stack_def_use.defined_in_block, split_load_conflict, arm_jump_table_candidate_start, stack_def_use.live_var_at_block_end, reg_def_use.last_def_in_block, arm_jump_table_cmp_limit, data_in_code, candidate_block_is_not_padding, inter_procedural_edge, known_block, instruction_memory_access_size, overlap_with_litpool, block_limit, function_inference.function_entry_initial, init_symbol_minus_symbol_candidate_arm, const_value_reg_used, self_contained_segment, stack_def_use.last_def_in_block, must_fallthrough, straight_line_last_def, padding_block_limit, jump_table_candidate, no_return_call_refined, block_candidate_dependency_edge, split_load_candidate, stack_def_use.block_last_def, last_value_reg_limit, relative_address, no_return_block, litpool_ref, symbol_minus_symbol_litpool_access_pattern, block_last_instruction, gp_relative_operand, data_in_code_propagate, block_candidate_boundaries, basic_target, compare_and_jump_immediate, wis_memo, __agg_subclause6, nop_in_padding_candidate, reg_def_use.defined_in_block, __agg_single6, relocation_adjustment_total, candidate_block_is_padding, wis_prior, reg_def_use.live_var_used, __agg_subclause7, wis_has_prior, compare_and_jump_register, block_instruction_next, arm_jump_table_data_block, value_reg, contains_plausible_instr_seq, relative_jump_table_entry_candidate, adrp_used, stack_def_use.def_used, got_relative_operand, __agg_subclause10, value_reg_edge, arch.reg_relative_load, reg_def_use.flow_def, hi_load_prop, jump_table_start, branch_to_calculated_pc_rel_addr, tls_desc_call, discarded_block, stack_def_use.live_var_used_in_block, data_segment, value_reg_unsupported, block_next, discarded_split_load, indexed_pc_relative_load_relative, litpool_symbolic_operand, data_block_candidate, reg_def_use.return_block_end, code_in_block_candidate_refined, after_end, jump_table_signed, reg_def_use.block_last_def, base_relative_jump, unresolved_interval_best_block, straight_line_def_used, unresolved_block, data_access, correlated_live_reg, jump_table_prelude, litpool_boundaries, init_ldr_add_pc, arch.extend_load, stack_def_use.used_in_block, stack_def_use.ref_in_block, reg_def_use.ref_in_block, reg_def_use.return_val_used