P4C
The P4 Compiler
Loading...
Searching...
No Matches
z3_solver.h
1/*
2 * SPDX-FileCopyrightText: 2022 The P4 Language Consortium
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 */
6
7#ifndef BACKENDS_P4TOOLS_COMMON_CORE_Z3_SOLVER_H_
8#define BACKENDS_P4TOOLS_COMMON_CORE_Z3_SOLVER_H_
9
10#include <z3++.h>
11#include <z3.h>
12
13#include <cstddef>
14#include <iosfwd>
15#include <memory>
16#include <optional>
17#include <string>
18#include <unordered_map>
19#include <vector>
20
21#include "ir/ir.h"
22#include "ir/json_generator.h"
23#include "ir/solver.h"
24#include "lib/cstring.h"
25#include "lib/ordered_map.h"
26#include "lib/rtti.h"
27#include "lib/safe_vector.h"
28
29namespace P4::P4Tools {
30
34using Z3DeclaredVariablesMap = std::vector<ordered_map<unsigned, const IR::SymbolicVariable *>>;
35
37class Z3Solver : public AbstractSolver {
38 friend class Z3Translator;
39 friend class Z3JSON;
40 friend class Z3SolverAccessor;
41
42 public:
43 ~Z3Solver() override = default;
44
45 explicit Z3Solver(bool isIncremental = true,
46 std::optional<std::istream *> inOpt = std::nullopt);
47
48 void comment(cstring comment) override;
49
50 void seed(unsigned seed) override;
51
52 void timeout(unsigned tm) override;
53
54 std::optional<bool> checkSat(const std::vector<const Constraint *> &asserts) override;
55
58 std::optional<bool> checkSat(const z3::expr_vector &asserts);
59
62 std::optional<bool> checkSat();
63
64 [[nodiscard]] SymbolicMapping getSymbolicMapping() const override;
65
66 void toJSON(JSONGenerator & /*json*/) const override;
67
68 [[nodiscard]] bool isInIncrementalMode() const override;
69
71 [[nodiscard]] const z3::solver &getZ3Solver() const;
72
74 [[nodiscard]] z3::solver &mutableSolver();
75
77 [[nodiscard]] const z3::context &context() const;
78
80 [[nodiscard]] z3::context &mutableContext() const;
81
84
87 void reset();
88
90 void push();
91
93 void pop();
94
97 void clearMemory();
98
100 void asrt(const z3::expr &assert);
101
103 void asrt(const Constraint *assertion);
104
105 private:
107 z3::sort toSort(const IR::Type *type);
108
112 z3::expr declareVar(const IR::SymbolicVariable &var);
113
115 [[nodiscard]] static std::string generateName(const IR::SymbolicVariable &var);
116
118 static const IR::Literal *toLiteral(const z3::expr &e, const IR::Type *type);
119
124 // that is greater than or equal to @asrtIndex.
126 void addZ3Pushes(size_t &chkIndex, size_t asrtIndex);
127
129 static std::optional<bool> interpretSolverResult(z3::check_result result);
130
131 // Declared first so all Z3 objects are destroyed before their context.
132 std::unique_ptr<z3::context> ownedContext;
133
135 z3::solver z3solver;
136
139 Z3DeclaredVariablesMap declaredVarsById;
140
143
146 bool isIncremental;
147
150 std::vector<size_t> checkpoints;
151
153 z3::expr_vector z3Assertions;
154
156 std::optional<unsigned> seed_;
157
159 std::optional<unsigned> timeout_;
160
161 DECLARE_TYPEINFO(Z3Solver, AbstractSolver);
162};
163
165class Z3Translator : public virtual Inspector {
166 public:
169 explicit Z3Translator(Z3Solver &solver);
170
172 bool preorder(const IR::Node *node) override;
173
175 bool preorder(const IR::Cast *cast) override;
176
178 bool preorder(const IR::Constant *constant) override;
179 bool preorder(const IR::BoolLiteral *boolLiteral) override;
180 bool preorder(const IR::StringLiteral *stringLiteral) override;
181
183 bool preorder(const IR::SymbolicVariable *var) override;
184
185 // Translations for unary operations.
186 bool preorder(const IR::Neg *op) override;
187 bool preorder(const IR::Cmpl *op) override;
188 bool preorder(const IR::LNot *op) override;
189
190 // Translations for binary operations.
191 bool preorder(const IR::Equ *op) override;
192 bool preorder(const IR::Neq *op) override;
193 bool preorder(const IR::Lss *op) override;
194 bool preorder(const IR::Leq *op) override;
195 bool preorder(const IR::Grt *op) override;
196 bool preorder(const IR::Geq *op) override;
197 bool preorder(const IR::Mod *op) override;
198 bool preorder(const IR::Add *op) override;
199 bool preorder(const IR::Sub *op) override;
200 bool preorder(const IR::Mul *op) override;
201 bool preorder(const IR::Div *op) override;
202 bool preorder(const IR::Shl *op) override;
203 bool preorder(const IR::Shr *op) override;
204 bool preorder(const IR::BAnd *op) override;
205 bool preorder(const IR::BOr *op) override;
206 bool preorder(const IR::BXor *op) override;
207 bool preorder(const IR::LAnd *op) override;
208 bool preorder(const IR::LOr *op) override;
209 bool preorder(const IR::Concat *op) override;
210
211 // Translations for ternary operations.
212 bool preorder(const IR::Mux *op) override;
213 bool preorder(const IR::Slice *op) override;
214
216 z3::expr getResult();
217
219 z3::expr translate(const IR::Expression *expression);
220
221 private:
224 std::unordered_map<const IR::Expression *, z3::expr> translations;
225
226 profile_t init_apply(const IR::Node *root) override;
227 void end_apply() override;
228 z3::expr translateChild(const IR::Expression *expression);
229
231 using Z3UnaryOp = z3::expr (*)(const z3::expr &);
232
234 using Z3BinaryOp = z3::expr (*)(const z3::expr &, const z3::expr &);
235
237 using Z3TernaryOp = z3::expr (*)(const z3::expr &, const z3::expr &, const z3::expr &);
238
242 bool recurseUnary(const IR::Operation_Unary *unary, Z3UnaryOp f);
243
247 bool recurseBinary(const IR::Operation_Binary *binary, Z3BinaryOp f);
248
252 bool recurseTernary(const IR::Operation_Ternary *ternary, Z3TernaryOp f);
253
260 template <class ShiftType>
261 const ShiftType *rewriteShift(const ShiftType *shift) const;
262
264 z3::expr result;
265
267 std::reference_wrapper<Z3Solver> _solver;
268
270 [[nodiscard]] Z3Solver &solver();
271};
272
273} // namespace P4::P4Tools
274
275#endif /* BACKENDS_P4TOOLS_COMMON_CORE_Z3_SOLVER_H_ */
Provides a higher-level interface for an SMT solver.
Definition solver.h:30
Definition node.h:44
Definition json_generator.h:30
A Z3-based implementation of AbstractSolver. Encapsulates a z3::solver and a z3::context.
Definition z3_solver.h:37
std::optional< bool > checkSat()
Definition z3_solver.cpp:186
z3::solver & mutableSolver()
Return a version of the solver that is mutable.
Definition z3_solver.cpp:336
bool isInIncrementalMode() const override
Definition z3_solver.cpp:342
void toJSON(JSONGenerator &) const override
Saves solver state to the given JSON generator.
Definition z3_solver.cpp:312
const z3::solver & getZ3Solver() const
Get the actual Z3 solver backing this class.
Definition z3_solver.cpp:334
void pop()
Removes the last solver context.
Definition z3_solver.cpp:116
void asrt(const z3::expr &assert)
Adds a Z3 assertion to the solver context.
Definition z3_solver.cpp:232
void timeout(unsigned tm) override
Sets timeout for solver in milliseconds.
Definition z3_solver.cpp:162
void push()
Pushes new (empty) solver context.
Definition z3_solver.cpp:108
void reset()
Definition z3_solver.cpp:82
const z3::context & context() const
Get the actual Z3 context that this class uses.
Definition z3_solver.cpp:338
void seed(unsigned seed) override
Definition z3_solver.cpp:152
void clearMemory()
Definition z3_solver.cpp:92
z3::context & mutableContext() const
Get the actual Z3 context that this class uses. This context can be manipulated.
Definition z3_solver.cpp:340
SymbolicMapping getSymbolicMapping() const override
Definition z3_solver.cpp:245
void comment(cstring comment) override
Definition z3_solver.cpp:146
safe_vector< const Constraint * > getAssertions() const
Definition z3_solver.cpp:90
Z3Translator(Z3Solver &solver)
Definition z3_solver.cpp:377
z3::expr translate(const IR::Expression *expression)
Translate an P4C IR expression and return the Z3 equivalent.
Definition z3_solver.cpp:631
bool preorder(const IR::Node *node) override
Handles unexpected nodes.
Definition z3_solver.cpp:398
z3::expr getResult()
Definition z3_solver.cpp:629
Definition visitor.h:69
Definition cstring.h:76
Definition safe_vector.h:18
Definition common/compiler/compiler_result.cpp:7
std::vector< ordered_map< unsigned, const IR::SymbolicVariable * > > Z3DeclaredVariablesMap
Definition z3_solver.h:34
IR::Expression Constraint
Represents a constraint that can be shipped to and asserted within a solver.
Definition solver.h:23
P4::flat_map< const IR::SymbolicVariable *, const IR::Expression *, IR::SymbolicVariableLess > SymbolicMapping
This type maps symbolic variables to their value assigned by the solver.
Definition solver.h:26
Definition phv/solver/action_constraint_solver.cpp:34