3#ifndef LALA_CORE_SIMPLIFIER_HPP
4#define LALA_CORE_SIMPLIFIER_HPP
9#include "battery/dynamic_bitset.hpp"
23template<
class A,
class Allocator>
34 constexpr static const bool sequential = universe_type::sequential;
43 constexpr static const char*
name =
"Simplifier";
45 template<
class A2,
class Alloc2>
61 battery::dynamic_bitset<memory_type, allocator_type> eliminated_variables;
63 battery::dynamic_bitset<memory_type, allocator_type> eliminated_formulas;
65 battery::vector<ZDec<int, memory_type>,
allocator_type> equivalence_classes;
67 battery::vector<universe_type, allocator_type> constants;
73 : atype(atype), sub(sub), env(alloc)
74 , formulas(alloc), simplified_formulas(alloc)
75 , eliminated_variables(alloc), eliminated_formulas(alloc)
76 , equivalence_classes(alloc), constants(alloc)
80 : atype(other.atype), sub(std::move(other.sub)), env(other.env)
81 , formulas(std::move(other.formulas)), simplified_formulas(std::move(other.simplified_formulas))
82 , eliminated_variables(std::move(other.eliminated_variables)), eliminated_formulas(std::move(other.eliminated_formulas))
83 , equivalence_classes(std::move(other.equivalence_classes)), constants(std::move(other.constants))
89 template<
class A2,
class Alloc2>
93 , env(other.env, alloc)
94 , equivalence_classes(other.equivalence_classes, alloc)
95 , constants(other.constants, alloc)
99 return formulas.get_allocator();
112 return equivalence_classes.size();
115 template <
class Alloc>
126 template <
bool diagnose = false,
class F,
class Env,
class Alloc2>
130 if(env.interpret(f.map_atype(
aty()), avar, diagnostics)) {
138 tell.formulas.push_back(f);
144 template <IKind kind,
bool diagnose = false,
class F,
class Env,
class Alloc2>
146 return interpret_tell<diagnose>(f, env,
tell, diagnostics);
149 template <
class Alloc2,
class Mem>
151 assert(t.env !=
nullptr);
153 eliminated_variables.resize(t.num_vars);
154 eliminated_formulas.resize(t.formulas.size());
155 constants.resize(t.num_vars);
156 equivalence_classes.resize(t.num_vars);
157 for(
int i = 0; i < equivalence_classes.size(); ++i) {
160 formulas = std::move(t.formulas);
161 simplified_formulas.resize(formulas.size());
166 template <
class Alloc2>
169 return tell(std::move(t), has_changed);
175 CUDA
AVar to_sub_var(
AVar x)
const {
176 assert(env[x].avars.size() > 0);
177 return env[x].avars[0];
180 CUDA AVar to_sub_var(
size_t vid)
const {
181 return to_sub_var(AVar{
aty(), vid});
185 CUDA AVar var_of(
const TFormula<allocator_type>& f)
const {
186 using F = TFormula<allocator_type>;
194 assert(env[f.v()].avar_of(
aty()).has_value());
195 return env[f.v()].avar_of(
aty()).value();
202 template <
class Alloc,
class B,
class Env>
205 int rep = equivalence_classes[local_var.avar_of(
aty())->vid()];
207 const auto& benv_variable = benv.variable_of(rep_name);
208 if(benv_variable.has_value()) {
209 benv_variable->sort.print_value(b.project(benv_variable->avars[0]));
212 local_var.sort.print_value(constants[rep]);
218 CUDA
void eliminate(battery::dynamic_bitset<memory_type, allocator_type>& mask,
size_t i,
BInc<Mem>& has_changed) {
227 CUDA
void vrefine(
size_t i, BInc<Mem>& has_changed) {
228 const auto& u = sub->project(to_sub_var(i));
229 size_t j = equivalence_classes[i];
230 constants[j].
tell(u, has_changed);
231 if(constants[j].lb().value() == constants[j].ub().value()) {
232 eliminate(eliminated_variables, j, has_changed);
237 CUDA
void crefine(
size_t i, BInc<Mem>& has_changed) {
238 using F = TFormula<allocator_type>;
241 AVar x = var_of(formulas[i].seq(0));
242 AVar y = var_of(formulas[i].seq(1));
243 equivalence_classes[x.vid()].tell(
local::ZDec(equivalence_classes[y.vid()]), has_changed);
244 equivalence_classes[y.vid()].tell(
local::ZDec(equivalence_classes[x.vid()]), has_changed);
245 eliminate(eliminated_formulas, i, has_changed);
249 IDiagnostics diagnostics;
250 typename sub_type::template ask_type<allocator_type> ask;
252 if(sub->interpret_ask(formulas[i], env, ask, diagnostics)) {
254 if(sub->template interpret_ask(formulas[i], env, ask, diagnostics)) {
257 eliminate(eliminated_formulas, i, has_changed);
264 auto f = formulas[i].map([&](
const F& f,
const F& parent) {
265 if(f.is_variable()) {
267 if(eliminated_variables.test(x.vid())) {
268 auto k = constants[x.vid()].template deinterpret<F>();
269 if(env[x].sort.is_bool() && k.is(F::Z) && parent.is_logical()) {
270 return k.z() == 0 ? F::make_false() : F::make_true();
274 else if(equivalence_classes[x.vid()] != x.vid()) {
275 return F::make_lvar(UNTYPED, env.name_of(AVar{aty(), equivalence_classes[x.vid()]}));
283 eliminate(eliminated_formulas, i, has_changed);
285 if(f != simplified_formulas[i]) {
286 simplified_formulas[i] = f;
287 has_changed.tell_top();
295 return constants.size() + formulas.size();
300 assert(i < num_refinements());
301 if(i < constants.size()) {
302 vrefine(i, has_changed);
305 crefine(i - constants.size(), has_changed);
311 for(
int i = 0; i < equivalence_classes.size(); ++i) {
312 if(equivalence_classes[i] == i && !eliminated_variables.test(i)) {
316 return equivalence_classes.size() - keep;
320 return eliminated_formulas.count();
325 typename F::Sequence seq(get_allocator());
328 for(
int i = 0; i < equivalence_classes.size(); ++i) {
329 eliminated_variables.set(equivalence_classes[i], eliminated_variables.test(equivalence_classes[i]) && eliminated_variables.test(i));
333 for(
int i = 0; i < equivalence_classes.size(); ++i) {
334 if(equivalence_classes[i] == i && !eliminated_variables.test(i)) {
335 const auto& x = env[
AVar{aty(), i}];
336 seq.push_back(F::make_exists(
UNTYPED, x.name, x.sort));
337 auto domain_constraint = constants[i].deinterpret(
AVar(aty(), i), env);
339 seq.push_back(domain_constraint);
344 for(
int i = 0; i < simplified_formulas.size(); ++i) {
345 if(!eliminated_formulas.test(i)) {
346 seq.push_back(simplified_formulas[i]);
349 if(seq.size() == 0) {
350 return F::make_true();
353 return F::make_nary(
AND, std::move(seq));
Definition diagnostics.hpp:19
Definition primitive_upset.hpp:118
CUDA constexpr local::BInc is_top() const
Definition primitive_upset.hpp:224
CUDA constexpr this_type & tell_top()
Definition primitive_upset.hpp:233
Definition simplifier.hpp:24
CUDA allocator_type get_allocator() const
Definition simplifier.hpp:98
static constexpr const bool preserve_bot
Definition simplifier.hpp:37
CUDA Simplifier(this_type &&other)
Definition simplifier.hpp:79
Allocator allocator_type
Definition simplifier.hpp:26
CUDA void refine(size_t i, BInc< Mem > &has_changed)
Definition simplifier.hpp:299
CUDA this_type & tell(tell_type< Alloc2 > &&t)
Definition simplifier.hpp:167
CUDA size_t num_refinements() const
Definition simplifier.hpp:294
A sub_type
Definition simplifier.hpp:27
CUDA size_t vars() const
Definition simplifier.hpp:111
CUDA this_type & tell(tell_type< Alloc2 > &&t, BInc< Mem > &has_changed)
Definition simplifier.hpp:150
static constexpr const bool preserve_join
Definition simplifier.hpp:39
static constexpr const bool injective_concretization
Definition simplifier.hpp:41
CUDA local::BInc is_top() const
Definition simplifier.hpp:106
CUDA NI bool interpret_tell(const F &f, Env &env, tell_type< Alloc2 > &tell, IDiagnostics &diagnostics) const
Definition simplifier.hpp:127
CUDA size_t num_eliminated_variables() const
Definition simplifier.hpp:309
battery::vector< TFormula< allocator_type >, allocator_type > formula_sequence
Definition simplifier.hpp:48
CUDA bool interpret(const F &f, Env &env, tell_type< Alloc2 > &tell, IDiagnostics &diagnostics) const
Definition simplifier.hpp:145
CUDA AType aty() const
Definition simplifier.hpp:102
static constexpr const bool preserve_top
Definition simplifier.hpp:38
CUDA void print_variable(const LVar< Alloc > &vname, const Env &benv, const B &b) const
Definition simplifier.hpp:203
static constexpr const char * name
Definition simplifier.hpp:43
static constexpr const bool is_abstract_universe
Definition simplifier.hpp:33
static constexpr const bool is_totally_ordered
Definition simplifier.hpp:35
typename sub_type::allocator_type sub_allocator_type
Definition simplifier.hpp:28
typename universe_type::memory_type memory_type
Definition simplifier.hpp:30
CUDA NI TFormula< allocator_type > deinterpret()
Definition simplifier.hpp:323
CUDA Simplifier(AType atype, abstract_ptr< sub_type > sub, const allocator_type &alloc=allocator_type())
Definition simplifier.hpp:70
CUDA size_t num_eliminated_formulas() const
Definition simplifier.hpp:319
CUDA Simplifier(const Simplifier< A2, Alloc2 > &other, light_copy_tag tag, abstract_ptr< sub_type > sub, const allocator_type &alloc=allocator_type())
Definition simplifier.hpp:90
static constexpr const bool sequential
Definition simplifier.hpp:34
typename sub_type::universe_type universe_type
Definition simplifier.hpp:29
static constexpr const bool preserve_concrete_covers
Definition simplifier.hpp:42
static constexpr const bool preserve_meet
Definition simplifier.hpp:40
CUDA NI thrust::optional< const variable_type & > variable_of(const char *lv) const
Definition env.hpp:456
CUDA const bstring & name_of(AVar av) const
Definition env.hpp:495
::lala::ZDec< int, battery::local_memory > ZDec
Definition primitive_upset.hpp:82
Definition abstract_deps.hpp:14
CUDA NI void map_avar_to_lvar(F &f, const Env &env, bool erase_type=false)
Definition algorithm.hpp:418
int AType
Definition sort.hpp:18
@ AND
Unary arithmetic function symbols.
Definition ast.hpp:114
CUDA NI bool is_var_equality(const TFormula< Allocator, ExtendedSig > &f)
Definition algorithm.hpp:32
battery::string< Allocator > LVar
Definition ast.hpp:25
battery::shared_ptr< A, typename A::allocator_type > abstract_ptr
Definition abstract_deps.hpp:17
CUDA NI F eval(const F &f)
Definition algorithm.hpp:794
#define UNTYPED
Definition sort.hpp:21
Definition simplifier.hpp:86
Definition simplifier.hpp:116
tell_type(const Alloc &alloc=Alloc())
Definition simplifier.hpp:120
int num_vars
Definition simplifier.hpp:117
VarEnv< Alloc > * env
Definition simplifier.hpp:119
formula_sequence formulas
Definition simplifier.hpp:118