如何使用 boolector 为我的代码生成模型？

Question

我正在对 boolector 进行一些试验，因此我正在尝试为简单代码创建模型。假设我有以下伪代码：

int a = 5;
int b = 4;
int c = 3;

对于这组简单的说明，我可以创建模型并且一切正常。问题是当我在那之后有其他指令时

b = 10;
c = 20;

显然它无法生成模型，因为 b 不能等于同一模块内的 4 和 10。其中一位维护者建议我使用 boolector_push 和 boolector_pop 以便在需要时创建新的 Context。

boolector_push 的代码是：

void
boolector_push (Btor *btor, uint32_t level)
{
  BTOR_ABORT_ARG_NULL (btor);
  BTOR_TRAPI ("%u", level);
  BTOR_ABORT (!btor_opt_get (btor, BTOR_OPT_INCREMENTAL),
              "incremental usage has not been enabled");

  if (level == 0) return;

  uint32_t i;
  for (i = 0; i < level; i++)
  {
    BTOR_PUSH_STACK (btor->assertions_trail,
                     BTOR_COUNT_STACK (btor->assertions));
  }
  btor->num_push_pop++;
}

而不是 boolector_pop 是

void
boolector_pop (Btor *btor, uint32_t level)
{
  BTOR_ABORT_ARG_NULL (btor);
  BTOR_TRAPI ("%u", level);
  BTOR_ABORT (!btor_opt_get (btor, BTOR_OPT_INCREMENTAL),
              "incremental usage has not been enabled");
  BTOR_ABORT (level > BTOR_COUNT_STACK (btor->assertions_trail),
              "can not pop more levels (%u) than created via push (%u).",
              level,
              BTOR_COUNT_STACK (btor->assertions_trail));

  if (level == 0) return;

  uint32_t i, pos;
  BtorNode *cur;

  for (i = 0, pos = 0; i < level; i++)
    pos = BTOR_POP_STACK (btor->assertions_trail);

  while (BTOR_COUNT_STACK (btor->assertions) > pos)
  {
    cur = BTOR_POP_STACK (btor->assertions);
    btor_hashint_table_remove (btor->assertions_cache, btor_node_get_id (cur));
    btor_node_release (btor, cur);
  }
  btor->num_push_pop++;
}

在我看来，这两个函数会跟踪使用 boolector_assert 生成的断言，因此考虑到这一点，如何使用 boolector_push 和 boolector_pop 获得最终和正确的模型约束会相同吗？

我错过了什么？

谢谢

Answer 1

如您所料，解算器的 push 和 pop 方法不是您要查找的内容。相反，您必须将正在建模的程序转换为所谓的 SSA（静态单一分配）形式。这是关于它的维基百科文章，内容非常丰富：https://en.wikipedia.org/wiki/Static_single_assignment_form

基本思想是 "treat" 可变变量作为时变值，并在对它们进行多次赋值时赋予它们唯一的名称。因此，以下内容：

a = 5
b = a + 2
c = b + 3
c = c + 1
b = c + 6

变为：

a0 = 5
b0 = a0 + 2
c0 = b0 + 3
c1 = c0 + 1
b1 = c1 + 6

等请注意，条件语句很难处理，并且通常需要所谓的 phi 节点。（即，合并分支的值。）大多数编译器会自动为您进行这种转换，因为它可以实现许多优化。您可以手动完成，也可以使用算法为您完成，具体取决于您的具体问题。

这是关于堆栈溢出的另一个问题，本质上是在询问类似的问题：Z3 Conditional Statement

希望对您有所帮助！

如何使用 boolector 为我的代码生成模型？

How to generate a model for my code using boolector?

smt