From 830a993b704b0cadc05fe956d1174d87fb92270d Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Wed, 2 Apr 2008 23:23:24 +0200 Subject: [PATCH] omega/convert.cc: relation2Domain: only collect set variables That is, don't collect existentially quantified variables. --- barvinok_enumerate_e.cc | 10 ++++++---- omega/convert.cc | 33 ++++++++++++++++++++++++++------- omega/convert.h | 3 ++- omega/count.cc | 22 +++++++++++++--------- omega/polyfunc.cc | 9 +++++---- omega/vertices.cc | 2 +- 6 files changed, 53 insertions(+), 26 deletions(-) diff --git a/barvinok_enumerate_e.cc b/barvinok_enumerate_e.cc index afe80ef..ea9ef6c 100644 --- a/barvinok_enumerate_e.cc +++ b/barvinok_enumerate_e.cc @@ -98,17 +98,19 @@ error_t parse_opt(int key, char *arg, struct argp_state *state) #ifdef HAVE_OMEGA Polyhedron *Omega_simplify(Polyhedron *P, - unsigned exist, unsigned nparam, char **parms) + unsigned exist, unsigned nparam, char **parms, + unsigned MaxRays) { varvector varv; varvector paramv; Relation r = Polyhedron2relation(P, exist, nparam, parms); Polyhedron_Free(P); - return relation2Domain(r, varv, paramv); + return relation2Domain(r, varv, paramv, MaxRays); } #else Polyhedron *Omega_simplify(Polyhedron *P, - unsigned exist, unsigned nparam, char **parms) + unsigned exist, unsigned nparam, char **parms, + unsigned MaxRays) { return P; } @@ -213,7 +215,7 @@ int main(int argc, char **argv) param_name = Read_ParamNames(stdin, nparam); nvar = A->Dimension - exist - nparam; if (arguments.omega) { - A = Omega_simplify(A, exist, nparam, param_name); + A = Omega_simplify(A, exist, nparam, param_name, options->MaxRays); assert(!A->next); exist = A->Dimension - nvar - nparam; } diff --git a/omega/convert.cc b/omega/convert.cc index b8a6be1..48e1c7d 100644 --- a/omega/convert.cc +++ b/omega/convert.cc @@ -1,8 +1,5 @@ -#include #include "omega/convert.h" -#define MAXRAYS POL_NO_DUAL - static void max_index(Constraint_Handle c, varvector& vv, varvector& params) { for (Constr_Vars_Iter cvi(c); cvi; ++cvi) { @@ -22,9 +19,13 @@ static void set_constraint(Matrix *M, int row, value_set_si(M->p[row][1+vv.size()], c.get_const()); } -Polyhedron *relation2Domain(Relation& r, varvector& vv, varvector& params) +Polyhedron *relation2Domain(Relation& r, varvector& vv, varvector& params, + unsigned MaxRays) { + unsigned dim; + unsigned max_size; Polyhedron *D = NULL; + Polyhedron **next = &D; r.simplify(); @@ -37,13 +38,28 @@ Polyhedron *relation2Domain(Relation& r, varvector& vv, varvector& params) for (int j = 1; j <= r.n_out(); ++j) vv.push_back(r.output_var(j)); } + dim = vv.size(); const Variable_ID_Tuple * globals = r.global_decls(); for (int i = 0; i < globals->size(); ++i) params.push_back(r.get_local((*globals)[i+1])); + max_size = dim; + for (DNF_Iterator di(r.query_DNF()); di; ++di) { + vv.resize(dim); + for (EQ_Iterator ei = (*di)->EQs(); ei; ++ei) + max_index((*ei), vv, params); + for (GEQ_Iterator gi = (*di)->GEQs(); gi; ++gi) + max_index((*gi), vv, params); + if (vv.size() > max_size) + max_size = vv.size(); + } + for (DNF_Iterator di(r.query_DNF()); di; ++di) { int c = 0; + + vv.resize(dim); + for (EQ_Iterator ei = (*di)->EQs(); ei; ++ei, ++c) max_index((*ei), vv, params); for (GEQ_Iterator gi = (*di)->GEQs(); gi; ++gi, ++c) @@ -57,10 +73,11 @@ Polyhedron *relation2Domain(Relation& r, varvector& vv, varvector& params) set_constraint(M, row++, (*ei), vv, 0); for (GEQ_Iterator gi = (*di)->GEQs(); gi; ++gi) set_constraint(M, row++, (*gi), vv, 1); - Polyhedron *P = Constraints2Polyhedron(M, MAXRAYS); + *next = Constraints2Polyhedron(M, MaxRays); Matrix_Free(M); - D = DomainConcat(P, D); + next = &(*next)->next; } + vv.resize(dim); return D; } @@ -99,7 +116,8 @@ void dump(Relation& r) { varvector vv; varvector params; - Polyhedron *D = relation2Domain(r, vv, params); + struct barvinok_options *options = barvinok_options_new_with_defaults(); + Polyhedron *D = relation2Domain(r, vv, params, options->MaxRays); unsigned dim = r.is_set() ? r.n_set() : r.n_inp() + r.n_out(); if (D->next) { @@ -114,4 +132,5 @@ void dump(Relation& r) } Domain_Free(D); + barvinok_options_free(options); } diff --git a/omega/convert.h b/omega/convert.h index 9e5e199..e048f5d 100644 --- a/omega/convert.h +++ b/omega/convert.h @@ -4,7 +4,8 @@ typedef std::vector varvector; -Polyhedron *relation2Domain(Relation& r, varvector& vv, varvector& params); +Polyhedron *relation2Domain(Relation& r, varvector& vv, varvector& params, + unsigned MaxRays); Relation Polyhedron2relation(Polyhedron *P, unsigned exist, unsigned nparam, char **params); void dump(Relation& r); diff --git a/omega/count.cc b/omega/count.cc index 29fc66c..7b1880c 100644 --- a/omega/count.cc +++ b/omega/count.cc @@ -8,13 +8,12 @@ #include using namespace std; -#define MAXRAYS POL_NO_DUAL - evalue *count_relation(Relation& r) { varvector vv; varvector params; - Polyhedron *D = relation2Domain(r, vv, params); + struct barvinok_options *options = barvinok_options_new_with_defaults(); + Polyhedron *D = relation2Domain(r, vv, params, options->MaxRays); int dim = r.is_set() ? r.n_set() : r.n_inp() + r.n_out(); int d = 0; @@ -22,10 +21,11 @@ evalue *count_relation(Relation& r) for (Polyhedron *P = D; P; P = P->next, ++d) { assert(d == 0); int exist = P->Dimension - params.size() - dim; - EP = barvinok_enumerate_e(P, exist, params.size(), MAXRAYS); + EP = barvinok_enumerate_e(P, exist, params.size(), options->MaxRays); } reduce_evalue(EP); Domain_Free(D); + barvinok_options_free(options); return EP; } @@ -33,17 +33,19 @@ evalue *rank_relation(Relation& r) { varvector vv; varvector params; - Polyhedron *D = relation2Domain(r, vv, params); + struct barvinok_options *options = barvinok_options_new_with_defaults(); + Polyhedron *D = relation2Domain(r, vv, params, options->MaxRays); int dim = r.is_set() ? r.n_set() : r.n_inp() + r.n_out(); evalue *EP = NULL; if (D) { assert(D->next == NULL); Polyhedron *C = Universe_Polyhedron(params.size()); - EP = barvinok_lexsmaller_ev(D, D, dim, C, MAXRAYS); + EP = barvinok_lexsmaller_ev(D, D, dim, C, options->MaxRays); Polyhedron_Free(C); } Domain_Free(D); + barvinok_options_free(options); return EP; } @@ -53,9 +55,10 @@ evalue *count_lexsmaller(Relation& r, Relation& domain) varvector P_params; varvector D_vv; varvector D_params; - Polyhedron *P = relation2Domain(r, P_vv, P_params); + struct barvinok_options *options = barvinok_options_new_with_defaults(); + Polyhedron *P = relation2Domain(r, P_vv, P_params, options->MaxRays); int P_dim = r.is_set() ? r.n_set() : r.n_inp() + r.n_out(); - Polyhedron *D = relation2Domain(domain, D_vv, D_params); + Polyhedron *D = relation2Domain(domain, D_vv, D_params, options->MaxRays); int D_dim = r.is_set() ? r.n_set() : r.n_inp() + r.n_out(); assert(P_dim == D_dim); @@ -64,10 +67,11 @@ evalue *count_lexsmaller(Relation& r, Relation& domain) assert(P->next == NULL); assert(D->next == NULL); Polyhedron *C = Universe_Polyhedron(D_params.size()); - EP = barvinok_lexsmaller_ev(P, D, D_dim, C, MAXRAYS); + EP = barvinok_lexsmaller_ev(P, D, D_dim, C, options->MaxRays); Polyhedron_Free(C); } Domain_Free(P); Domain_Free(D); + barvinok_options_free(options); return EP; } diff --git a/omega/polyfunc.cc b/omega/polyfunc.cc index 09bbd1a..222dd7d 100644 --- a/omega/polyfunc.cc +++ b/omega/polyfunc.cc @@ -24,7 +24,8 @@ void maximize(PolyFunc *polyfunc, Map& variableMap) polyfunc->domain.simplify(); polyfunc->domain.print(stdout); - Polyhedron *D = relation2Domain(polyfunc->domain, vv, params); + Polyhedron *D = relation2Domain(polyfunc->domain, vv, params, + options->MaxRays); assert(!D->next); assert(polyfunc->domain.is_set()); int dim = polyfunc->domain.n_set(); @@ -42,8 +43,8 @@ void maximize(PolyFunc *polyfunc, Map& variableMap) assert(var != 0); exvars.push_back(var); } - for (int i = dim; i < vv.size(); ++i) { - Global_Var_ID global = vv[i]->get_global_var(); + for (int i = 0; i < params.size(); ++i) { + Global_Var_ID global = params[i]->get_global_var(); ex var = 0; foreach_map(vr,Variable_Ref *,s,ex,variableMap, { if (vr->g == global) { @@ -54,7 +55,7 @@ void maximize(PolyFunc *polyfunc, Map& variableMap) if (var != 0) exparams.push_back(var); else - exparams.push_back(symbol(vv[i]->char_name())); + exparams.push_back(symbol(params[i]->char_name())); } PP = Polyhedron2Param_Polyhedron(D, ctx, options); diff --git a/omega/vertices.cc b/omega/vertices.cc index 87b99b5..a68902c 100644 --- a/omega/vertices.cc +++ b/omega/vertices.cc @@ -14,7 +14,7 @@ void vertices(Relation& r) Param_Polyhedron *PP; struct barvinok_options *options = barvinok_options_new_with_defaults(); - Polyhedron *D = relation2Domain(r, vv, params); + Polyhedron *D = relation2Domain(r, vv, params, options->MaxRays); assert(!D->next); Polyhedron *ctx = Universe_Polyhedron(params.size()); -- 2.11.4.GIT