cprover
solver_hardness.h
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: measure and track the complexity of solver queries
4 
5 Author: Diffblue Ltd.
6 
7 \*******************************************************************/
8 
9 #ifndef CPROVER_SOLVERS_SOLVER_HARDNESS_H
10 #define CPROVER_SOLVERS_SOLVER_HARDNESS_H
11 
12 #include <solvers/prop/literal.h>
13 
14 #include <fstream>
15 #include <string>
16 #include <unordered_map>
17 #include <unordered_set>
18 #include <vector>
19 
21 
22 #include <util/optional.h>
23 
42 {
43  // From SAT solver we collect the number of clauses, the number of literals
44  // and the number of distinct variables that were used in all clauses.
46  {
47  size_t clauses = 0;
48  size_t literals = 0;
49  std::unordered_set<size_t> variables = {};
50  std::vector<size_t> clause_set = {};
51 
52  sat_hardnesst &operator+=(const sat_hardnesst &other);
53  };
54 
55  // Associate an SSA step expression (the one passed to the solver: the guard
56  // for GOTO; equality for ASSIGN, etc.) with the SAT hardness of the resulting
57  // query. The GOTO and source level instructions are stored as \ref
58  // goto_programt::const_targett.
60  {
61  std::string ssa_expression;
63 
64  bool operator==(const hardness_ssa_keyt &other) const;
65  };
66 
67  // As above but for the special case of multiple assertions, which are
68  // presented to the solver as a single disjunction. Hence we have one SSA
69  // expression (the whole disjunction) and multiple program counters.
71  {
73  std::string ssa_expression;
74  std::vector<goto_programt::const_targett> pcs;
75 
76  bool empty() const;
77  };
78 
85  void register_ssa(
86  std::size_t ssa_index,
87  const exprt ssa_expression,
89 
90  void register_ssa_size(std::size_t size);
91 
100  const exprt ssa_expression,
101  const std::vector<goto_programt::const_targett> &pcs);
102 
110  void register_clause(
111  const bvt &bv,
112  const bvt &cnf,
113  const size_t cnf_clause_index,
114  bool register_cnf);
115 
116  void set_outfile(const std::string &file_name);
117 
119  void produce_report();
120 
121  solver_hardnesst() = default;
122 
123  // copying this isn’t really a meaningful operation
126 
127  // copying this isn’t really a meaningful operation
130 
131 private:
132  // A minor modification of \ref goto_programt::output_instruction
134 
135  static std::string expr2string(const exprt expr);
136 
137  std::string outfile;
138  std::vector<std::unordered_map<hardness_ssa_keyt, sat_hardnesst>>
143  std::size_t max_ssa_set_size;
144 };
145 
146 // NOLINTNEXTLINE(readability/namespace)
147 namespace std
148 {
149 template <>
150 // NOLINTNEXTLINE(readability/identifiers)
151 struct hash<solver_hardnesst::hardness_ssa_keyt>
152 {
153  std::size_t
155  {
156  return std::hash<std::string>{}(
157  hashed_stats.ssa_expression +
158  hashed_stats.pc->source_location.as_string());
159  }
160 };
161 } // namespace std
162 
163 #endif // CPROVER_SOLVERS_SOLVER_HARDNESS_H
Base class for all expressions.
Definition: expr.h:54
instructionst::const_iterator const_targett
Definition: goto_program.h:647
Concrete Goto Program.
std::vector< literalt > bvt
Definition: literal.h:201
std::vector< goto_programt::const_targett > pcs
goto_programt::const_targett pc
bool operator==(const hardness_ssa_keyt &other) const
sat_hardnesst & operator+=(const sat_hardnesst &other)
std::vector< size_t > clause_set
std::unordered_set< size_t > variables
A structure that facilitates collecting the complexity statistics from a decision procedure.
sat_hardnesst current_hardness
assertion_statst assertion_stats
void set_outfile(const std::string &file_name)
void register_ssa(std::size_t ssa_index, const exprt ssa_expression, goto_programt::const_targett pc)
Called from the symtex_target_equationt::convert_*, this function associates an SSA step to all the s...
static std::string expr2string(const exprt expr)
solver_hardnesst & operator=(const solver_hardnesst &)=delete
void register_clause(const bvt &bv, const bvt &cnf, const size_t cnf_clause_index, bool register_cnf)
Called e.g.
hardness_ssa_keyt current_ssa_key
void register_assertion_ssas(const exprt ssa_expression, const std::vector< goto_programt::const_targett > &pcs)
Called from the symtex_target_equationt::convert_assertions, this function associates the disjunction...
solver_hardnesst()=default
solver_hardnesst & operator=(solver_hardnesst &&)=default
std::string outfile
std::vector< std::unordered_map< hardness_ssa_keyt, sat_hardnesst > > hardness_stats
std::size_t max_ssa_set_size
void produce_report()
Print the statistics to a JSON file (specified via command-line option).
solver_hardnesst(solver_hardnesst &&)=default
static std::string goto_instruction2string(goto_programt::const_targett pc)
solver_hardnesst(const solver_hardnesst &)=delete
void register_ssa_size(std::size_t size)
std::size_t operator()(const solver_hardnesst::hardness_ssa_keyt &hashed_stats) const