From 3ed9ff6353e84fbb07ecc846bf8137cfeecac884 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sun, 3 Jul 2011 14:33:43 +0200 Subject: [PATCH] remove evalue_split_periods Signed-off-by: Sven Verdoolaege --- barvinok/evalue.h | 1 - evalue.c | 168 ------------------------------------------------------ testlib.cc | 25 -------- 3 files changed, 194 deletions(-) diff --git a/barvinok/evalue.h b/barvinok/evalue.h index 307ea8b..6c6676c 100644 --- a/barvinok/evalue.h +++ b/barvinok/evalue.h @@ -132,7 +132,6 @@ void evalue_mul_div(evalue *e, Value n, Value d); void evalue_negate(evalue *e); void evalue_add_constant(evalue *e, const Value cst); void evalue_split_domains_into_orthants(evalue *e, unsigned MaxRays); -void evalue_split_periods(evalue *e, int max_periods, unsigned int MaxRays); void evalue_extract_affine(const evalue *e, Value *coeff, Value *cst, Value *d); evalue *affine2evalue(Value *coeff, Value denom, int nvar); void evalue_substitute(evalue *e, evalue **subs); diff --git a/evalue.c b/evalue.c index 0be05e6..bb7a0b2 100644 --- a/evalue.c +++ b/evalue.c @@ -3996,174 +3996,6 @@ void evalue_split_domains_into_orthants(evalue *e, unsigned MaxRays) } } -static evalue *find_fractional_with_max_periods(evalue *e, Polyhedron *D, - int max_periods, - Matrix **TT, - Value *min, Value *max) -{ - Matrix *T; - evalue *f = NULL; - Value d; - int i; - - if (value_notzero_p(e->d)) - return NULL; - - if (e->x.p->type == fractional) { - Polyhedron *I; - int bounded; - - value_init(d); - I = polynomial_projection(e->x.p, D, &d, &T); - bounded = line_minmax(I, min, max); /* frees I */ - if (bounded) { - Value mp; - value_init(mp); - value_set_si(mp, max_periods); - mpz_fdiv_q(*min, *min, d); - mpz_fdiv_q(*max, *max, d); - value_assign(T->p[1][D->Dimension], d); - value_subtract(d, *max, *min); - if (value_ge(d, mp)) - Matrix_Free(T); - else - f = evalue_dup(&e->x.p->arr[0]); - value_clear(mp); - } else - Matrix_Free(T); - value_clear(d); - if (f) { - *TT = T; - return f; - } - } - - for (i = type_offset(e->x.p); i < e->x.p->size; ++i) - if ((f = find_fractional_with_max_periods(&e->x.p->arr[i], D, max_periods, - TT, min, max))) - return f; - - return NULL; -} - -static void replace_fract_by_affine(evalue *e, evalue *f, Value val) -{ - int i, offset; - - if (value_notzero_p(e->d)) - return; - - offset = type_offset(e->x.p); - for (i = e->x.p->size-1; i >= offset; --i) - replace_fract_by_affine(&e->x.p->arr[i], f, val); - - if (e->x.p->type != fractional) - return; - - if (!eequal(&e->x.p->arr[0], f)) - return; - - replace_by_affine(e, val); -} - -/* Look for fractional parts that can be removed by splitting the corresponding - * domain into at most max_periods parts. - * We use a very simply strategy that looks for the first fractional part - * that satisfies the condition, performs the split and then continues - * looking for other fractional parts in the split domains until no - * such fractional part can be found anymore. - */ -void evalue_split_periods(evalue *e, int max_periods, unsigned int MaxRays) -{ - int i, j, n; - Value min; - Value max; - Value d; - - if (EVALUE_IS_ZERO(*e)) - return; - if (value_notzero_p(e->d) || e->x.p->type != partition) { - fprintf(stderr, - "WARNING: evalue_split_periods called on incorrect evalue type\n"); - return; - } - - value_init(min); - value_init(max); - value_init(d); - - for (i = 0; i < e->x.p->size/2; ++i) { - enode *p; - evalue *f; - Matrix *T; - Matrix *M; - Polyhedron *D = EVALUE_DOMAIN(e->x.p->arr[2*i]); - Polyhedron *E; - f = find_fractional_with_max_periods(&e->x.p->arr[2*i+1], D, max_periods, - &T, &min, &max); - if (!f) - continue; - - M = Matrix_Alloc(2, 2+D->Dimension); - - value_subtract(d, max, min); - n = VALUE_TO_INT(d)+1; - - value_set_si(M->p[0][0], 1); - Vector_Copy(T->p[0], M->p[0]+1, D->Dimension+1); - value_multiply(d, max, T->p[1][D->Dimension]); - value_subtract(M->p[0][1+D->Dimension], M->p[0][1+D->Dimension], d); - value_set_si(d, -1); - value_set_si(M->p[1][0], 1); - Vector_Scale(T->p[0], M->p[1]+1, d, D->Dimension+1); - value_addmul(M->p[1][1+D->Dimension], max, T->p[1][D->Dimension]); - value_addto(M->p[1][1+D->Dimension], M->p[1][1+D->Dimension], - T->p[1][D->Dimension]); - value_decrement(M->p[1][1+D->Dimension], M->p[1][1+D->Dimension]); - - p = new_enode(partition, e->x.p->size + (n-1)*2, e->x.p->pos); - for (j = 0; j < 2*i; ++j) { - value_clear(p->arr[j].d); - p->arr[j] = e->x.p->arr[j]; - } - for (j = 2*i+2; j < e->x.p->size; ++j) { - value_clear(p->arr[j+2*(n-1)].d); - p->arr[j+2*(n-1)] = e->x.p->arr[j]; - } - for (j = n-1; j >= 0; --j) { - if (j == 0) { - value_clear(p->arr[2*i+1].d); - p->arr[2*i+1] = e->x.p->arr[2*i+1]; - } else - evalue_copy(&p->arr[2*(i+j)+1], &e->x.p->arr[2*i+1]); - if (j != n-1) { - value_subtract(M->p[1][1+D->Dimension], M->p[1][1+D->Dimension], - T->p[1][D->Dimension]); - value_addto(M->p[0][1+D->Dimension], M->p[0][1+D->Dimension], - T->p[1][D->Dimension]); - } - replace_fract_by_affine(&p->arr[2*(i+j)+1], f, max); - E = DomainAddConstraints(D, M, MaxRays); - EVALUE_SET_DOMAIN(p->arr[2*(i+j)], E); - if (evalue_range_reduction_in_domain(&p->arr[2*(i+j)+1], E)) - reduce_evalue(&p->arr[2*(i+j)+1]); - value_decrement(max, max); - } - value_clear(e->x.p->arr[2*i].d); - Domain_Free(D); - Matrix_Free(M); - Matrix_Free(T); - evalue_free(f); - free(e->x.p); - e->x.p = p; - --i; - } - - value_clear(d); - value_clear(min); - value_clear(max); -} - void evalue_extract_affine(const evalue *e, Value *coeff, Value *cst, Value *d) { value_set_si(*d, 1); diff --git a/testlib.cc b/testlib.cc index cd5319f..28914d7 100644 --- a/testlib.cc +++ b/testlib.cc @@ -201,30 +201,6 @@ int test_substitute(struct barvinok_options *options) return 0; } -int test_split_periods(struct barvinok_options *options) -{ - unsigned nvar, nparam; - const char **all_vars; - evalue *e; - - e = evalue_read_from_str("U + 2V + 3 >= 0\n- U -2V >= 0\n- U 10 >= 0\n" - "U >= 0\n\n({( 1/3 * U + ( 2/3 * V + 0 ))})", - NULL, &all_vars, &nvar, &nparam, - options->MaxRays); - Free_ParamNames(all_vars, nvar+nparam); - - evalue_split_periods(e, 2, options->MaxRays); - assert(value_zero_p(e->d)); - assert(e->x.p->type == partition); - assert(e->x.p->size == 4); - assert(value_zero_p(e->x.p->arr[1].d)); - assert(e->x.p->arr[1].x.p->type == polynomial); - assert(value_zero_p(e->x.p->arr[3].d)); - assert(e->x.p->arr[3].x.p->type == polynomial); - evalue_free(e); - return 0; -} - int test_specialization(struct barvinok_options *options) { Value v; @@ -782,7 +758,6 @@ int main(int argc, char **argv) test_eadd(options); test_evalue(options); test_substitute(options); - test_split_periods(options); test_specialization(options); test_lattice_points(options); test_icounter(options); -- 2.11.4.GIT