[Analyzer] Transform a region 't[i]' to its svalue form '&t + (i * element_size)'

[Analyzer] Transform a region 't[i]' to its svalue form '&t + (i * element_size)'

[Pierrick Philippe]

[-- Attachment #1: Type: text/plain, Size: 2215 bytes --]

Hi all, hi David,

I am trying to use the analyzer API to transform an element_region (such 
as 't[1]') to a binop_svalue with an inner region_svalue (such as '&t + 
4' in case of integers array) for analysis purpose.

I managed to do it the other way around (i.e. from a binop_svalue to an 
element_region) using the analyzer API (code is in attached file 
offset_to_elm.cc).
And everything is working as intended within the analyzer and my analysis.

The problem I'm having here is probably due to a mistake I'm doing on 
some argument to a function call, but I cannot see it to be honest (code 
misbehaving is in elm_to_offset.cc).

I attached a commented sample code I'd like to be able to analyze 
(test.c), alongside the commented GIMPLE code seen by the analyzer 
(test.c.075i.analyzer obtained through '-fdump-ipa-analyzer').
Feel free to ask question if needed of course.

I manage to rebuild a binop_sval from an element_region (code is in 
attached file elm_to_offset.cc), but resulting object is not the same 
than the one already within the state_map of my state machine.
To be clear, the svalue's pointer resulting from the code in 
elm_to_offset.cc is deifferent, though when they're logged with simple 
set to false, no difference seem to exist.
And I really do have the intuition that the problem might be related to 
the call to region_model_manager::get_ptr_svalue on elm_to_offset.cc:17.
I do think that the key is not find within 
region_model_manager::m_pointer_values_map is not found and the call to 
region_svalue constructor is performed within 
region_model_manager::get_ptr_svalue implementation.
But still, I have no idea why.

I did modified the analyzer state_map class to be able to also track 
regions states alongside svalues one (working on a patch, code is not 
respecting GCC's coding standard so far and most probably not optimized).

Any idea on what I'm doing wrong here would really be appreciated.

Beside this, I do think that enhancing the analyzer by allowing to track 
regions states could allow for a broader set of possible analysis. What 
do you think ?

Thank you,

Pierrick

P.S.: @David, sorry for double send. I did a mistake in the gcc's 
mailing list address.

[-- Attachment #2: elm_to_offset.cc --]
[-- Type: text/x-c++src, Size: 1196 bytes --]

const svalue *elm_to_offset(sm_context *sm_ctx, const region *reg, logger *logger) {
    
  const svalue* res = nullptr;

  if (logger)
    LOG_SCOPE(logger);

  auto model = sm_ctx->get_new_program_state()->m_region_model;
  auto mgr = model->get_manager();

  bit_offset_t offset;
  const svalue *offset_sval = nullptr;
  if (reg->get_relative_concrete_offset(&offset)) {
    auto offset_byte = offset / BITS_PER_UNIT;
    offset_sval = mgr->get_or_create_constant_svalue(wide_int_to_tree(sizetype, offset_byte));
    auto base = reg->get_base_region();
    auto base_sval = mgr->get_ptr_svalue(TYPE_POINTER_TO(base->get_type()), base);
    res = mgr->get_or_create_binop(base->get_type(), POINTER_PLUS_EXPR, base_sval, offset_sval);
  }
  // TODO: symbolic offset
  else if (logger)
      logger->log("Offset is symbolic, not implemented.");

  if (logger) {
    logger->start_log_line();
    logger->log_partial("res: %p | ", res);
    res ? res->dump_to_pp(logger->get_printer(), false) : logger->log_partial("nullptr");
    logger->log_partial(" | ");
    res ? res->dump_to_pp(logger->get_printer(), true) : logger->log_partial("nullptr");
    logger->end_log_line();
  }

  return res;
}

[-- Attachment #3: offset_to_elm.cc --]
[-- Type: text/x-c++src, Size: 1560 bytes --]

const region *offset_to_elm(sm_context * sm_ctx, const svalue *sval, logger *logger) {

  const region * res = nullptr;

  if (logger)
    LOG_SCOPE(logger);

  auto model = sm_ctx->get_new_program_state()->m_region_model;

  if (const region *deref = model->deref_rvalue(sval, NULL_TREE, nullptr)) {
    if (logger) {
      logger->start_log_line();
      logger->log_partial("deref: ");
      deref->dump_to_pp(logger->get_printer(), false);
      logger->end_log_line();
    }
    auto base = deref->get_base_region();
    bit_offset_t offset;
    bit_size_t size;
    if (deref->get_relative_concrete_offset(&offset)
      && deref->get_bit_size(&size)) {
      auto index = offset / size;
      auto model_mgr = model->get_manager();
      auto index_sized = wide_int_to_tree(sizetype, index);
      auto sval_index_sized = model_mgr->get_or_create_constant_svalue(index_sized);
      res = model_mgr->get_element_region(base, TREE_TYPE(base->get_type()), sval_index_sized);
    }
    // TODO: symbolic offset
    else if (logger)
        logger->log("Offset is symbolic, not implemented.");
  }

  if (logger) {
    logger->start_log_line();
    logger->log_partial("input: %p | ", sval);
    sval->dump_to_pp(logger->get_printer(), true);
    logger->log_partial(" | ");
    sval->dump_to_pp(logger->get_printer(), false);
    logger->end_log_line();
    logger->start_log_line();
    logger->log_partial("res: ");
    res ? res->dump_to_pp(logger->get_printer(), true) : logger->log_partial("nullptr");
    logger->end_log_line();
  }

  return res;
}

[-- Attachment #4: test.c --]
[-- Type: text/x-csrc, Size: 424 bytes --]

void some_func(void) {
  // var's value should not be used in certain instructions such as conditions
  int var = 42; // var is here tracked as source within the state_map, i.e. no origin
  int t[4] = { 0 };
  int *y = t + 1;
  *y = var; // y's svalue, i.e. '&t + 4' is here correctly tracked in the state map
  // I would like to correlate the tracked state of y's svalue to the region 't[1]'
  if (t[1])
    do_stuff();
}

[-- Attachment #5: test.c.075i.analyzer --]
[-- Type: text/plain, Size: 405 bytes --]

void some_func ()
{
  int * y;
  int t[4];
  int var;
  int _1;

  <bb 2> :
  var_3 = 42; // var_3 is tracked, no origin
  t = {};
  y_6 = &t + 4;
  *y_6 = var_3; // y_6 svalue is tracked, origin var_3
  _1 = t[1]; // _1 should be tracked with y_6 as origin
  if (_1 != 0)
    goto <bb 3>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 3> :
  do_stuff ();

  <bb 4> :
  t ={v} {CLOBBER(eol)};
  return;

}