From 41e56526a598316c634d29e5ef56aa71c9e38a05 Mon Sep 17 00:00:00 2001 From: Raimondas Sasnauskas Date: Tue, 2 Dec 2014 12:59:27 -0700 Subject: Print nested let-abbreviations in ExprSMTLIBPrinter This patch introduces nested let-abbreviations in the ExprSMTLIBPrinter to reduce the size of the SMTLIBv2 queries and the corresponding processing time (bugfix for #170). The current implementation of the let abbreviation mode does not consider expression intra-dependencies and prints all abbreviations in the same let scope. For a (simplified) example, it prints (assert (let ( (?B1 (A + B)) (?B2 (A + B + C)) ) (= ?B1 ?B2) ) ). This is extremely inefficient if the expressions (and there many of these!) extensively reuse their subexpressions. Therefore, it's better to print the query with nested let-expressions by reusing existing expression bindings in the new let scope: (assert (let ( (?B1 (A + B)) ) (let ( (?B2 (?B1 + C)) ) (= ?B1 ?B2) ) ) ). This patch adds a new function ExprSMTLIBPrinter::scanBindingExprDeps() that scans bindings for expression dependencies. The result is a vector of new bindings (orderedBindings) that represents the expression dependency tree. When printing in the let-abbreviation mode, the new code starts with abbreviating expressions that have no dependencies and then gradually makes these new bindings available in the upcoming let-scopes where expressions with dependencies reuse them. The effect of nested let-abbreviations is comparable to :named abbreviations. However, the latter mode is not supported by the majority of the solvers. --- include/klee/util/ExprSMTLIBPrinter.h | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'include') diff --git a/include/klee/util/ExprSMTLIBPrinter.h b/include/klee/util/ExprSMTLIBPrinter.h index 48d300eb..a27d2bbc 100644 --- a/include/klee/util/ExprSMTLIBPrinter.h +++ b/include/klee/util/ExprSMTLIBPrinter.h @@ -223,6 +223,11 @@ protected: /// emitted, so it may be used. BindingMap bindings; + /// An ordered list of expression bindings. + /// Exprs in BindingMap at index i depend on Exprs in BindingMap at i-1. + /// Exprs in orderedBindings[0] have no dependencies. + std::vector orderedBindings; + /// Output stream to write to llvm::raw_ostream *o; @@ -287,6 +292,11 @@ protected: /// the usedArrays vector. void scan(const ref &e); + /// Scan bindings for expression intra-dependencies. The result is written + /// to the orderedBindings vector that is later used for nested expression + /// printing in the let abbreviation mode. + void scanBindingExprDeps(); + /* Rules of recursion for "Special Expression handlers" and *printSortArgsExpr() * -- cgit 1.4.1