X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_tab.h;h=8b808f0da86c20f5f1d137f2fdfe402e8dc3a10a;hb=63fb8a7f484648c3caa25351c8c94ac2395ec563;hp=e76b0f02b2b42162789431bdfb153af6f62f4a4d;hpb=1fefe8b0498ece106ca798a18187e7d16d3f8c66;p=platform%2Fupstream%2Fisl.git diff --git a/isl_tab.h b/isl_tab.h index e76b0f0..8b808f0 100644 --- a/isl_tab.h +++ b/isl_tab.h @@ -1,10 +1,19 @@ +/* + * Copyright 2008-2009 Katholieke Universiteit Leuven + * + * Use of this software is governed by the MIT license + * + * Written by Sven Verdoolaege, K.U.Leuven, Departement + * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium + */ + #ifndef ISL_TAB_H #define ISL_TAB_H -#include "isl_lp.h" -#include "isl_map.h" -#include "isl_mat.h" -#include "isl_set.h" +#include +#include +#include +#include struct isl_tab_var { int index; @@ -22,19 +31,29 @@ enum isl_tab_undo_type { isl_tab_undo_empty, isl_tab_undo_nonneg, isl_tab_undo_redundant, + isl_tab_undo_freeze, isl_tab_undo_zero, isl_tab_undo_allocate, isl_tab_undo_relax, - isl_tab_undo_bset_ineq, - isl_tab_undo_bset_eq, - isl_tab_undo_bset_div, + isl_tab_undo_unrestrict, + isl_tab_undo_bmap_ineq, + isl_tab_undo_bmap_eq, + isl_tab_undo_bmap_div, isl_tab_undo_saved_basis, isl_tab_undo_drop_sample, + isl_tab_undo_saved_samples, + isl_tab_undo_callback, +}; + +struct isl_tab_callback { + int (*run)(struct isl_tab_callback *cb); }; union isl_tab_undo_val { int var_index; int *col_var; + int n; + struct isl_tab_callback *callback; }; struct isl_tab_undo { @@ -91,7 +110,7 @@ struct isl_tab_undo { * Dead columns and redundant rows are detected on the fly. * However, the basic operations do not ensure that all dead columns * or all redundant rows are detected. - * isl_tab_detect_equalities and isl_tab_detect_redundant can be used + * isl_tab_detect_implicit_equalities and isl_tab_detect_redundant can be used * to perform and exhaustive search for dead columns and redundant rows. * * The samples matrix contains "n_sample" integer points that have at some @@ -100,6 +119,9 @@ struct isl_tab_undo { * can be reinstated during rollback when the constraint that cut them * out is removed. These samples are only maintained for the context * tableau while solving PILP problems. + * + * If "preserve" is set, then we want to keep all constraints in the + * tableau, even if they turn out to be redundant. */ enum isl_tab_row_sign { isl_tab_row_unknown = 0, @@ -132,41 +154,66 @@ struct isl_tab { struct isl_tab_undo *top; struct isl_vec *dual; - struct isl_basic_set *bset; + struct isl_basic_map *bmap; unsigned n_sample; unsigned n_outside; + int *sample_index; struct isl_mat *samples; + int n_zero; + int n_unbounded; + struct isl_mat *basis; + + int (*conflict)(int con, void *user); + void *conflict_user; + + unsigned strict_redundant : 1; unsigned need_undo : 1; + unsigned preserve : 1; unsigned rational : 1; unsigned empty : 1; unsigned in_undo : 1; unsigned M : 1; + unsigned cone : 1; }; struct isl_tab *isl_tab_alloc(struct isl_ctx *ctx, unsigned n_row, unsigned n_var, unsigned M); void isl_tab_free(struct isl_tab *tab); -struct isl_tab *isl_tab_from_basic_map(struct isl_basic_map *bmap); -struct isl_tab *isl_tab_from_basic_set(struct isl_basic_set *bset); -struct isl_tab *isl_tab_from_recession_cone(struct isl_basic_set *bset); +isl_ctx *isl_tab_get_ctx(struct isl_tab *tab); + +__isl_give struct isl_tab *isl_tab_from_basic_map( + __isl_keep isl_basic_map *bmap, int track); +__isl_give struct isl_tab *isl_tab_from_basic_set( + __isl_keep isl_basic_set *bset, int track); +struct isl_tab *isl_tab_from_recession_cone(struct isl_basic_set *bset, + int parametric); int isl_tab_cone_is_bounded(struct isl_tab *tab); struct isl_basic_map *isl_basic_map_update_from_tab(struct isl_basic_map *bmap, struct isl_tab *tab); struct isl_basic_set *isl_basic_set_update_from_tab(struct isl_basic_set *bset, struct isl_tab *tab); -struct isl_tab *isl_tab_detect_equalities(struct isl_tab *tab); -struct isl_tab *isl_tab_detect_redundant(struct isl_tab *tab); +int isl_tab_detect_implicit_equalities(struct isl_tab *tab) WARN_UNUSED; +__isl_give isl_basic_map *isl_tab_make_equalities_explicit(struct isl_tab *tab, + __isl_take isl_basic_map *bmap); +int isl_tab_detect_redundant(struct isl_tab *tab) WARN_UNUSED; #define ISL_TAB_SAVE_DUAL (1 << 0) enum isl_lp_result isl_tab_min(struct isl_tab *tab, isl_int *f, isl_int denom, isl_int *opt, isl_int *opt_denom, - unsigned flags); + unsigned flags) WARN_UNUSED; -struct isl_tab *isl_tab_extend(struct isl_tab *tab, unsigned n_new); -struct isl_tab *isl_tab_add_ineq(struct isl_tab *tab, isl_int *ineq); -struct isl_tab *isl_tab_add_valid_eq(struct isl_tab *tab, isl_int *eq); +struct isl_tab *isl_tab_extend(struct isl_tab *tab, unsigned n_new) WARN_UNUSED; +int isl_tab_add_ineq(struct isl_tab *tab, isl_int *ineq) WARN_UNUSED; +int isl_tab_add_eq(struct isl_tab *tab, isl_int *eq) WARN_UNUSED; +int isl_tab_add_valid_eq(struct isl_tab *tab, isl_int *eq) WARN_UNUSED; + +int isl_tab_freeze_constraint(struct isl_tab *tab, int con) WARN_UNUSED; + +int isl_tab_track_bmap(struct isl_tab *tab, __isl_take isl_basic_map *bmap) WARN_UNUSED; +int isl_tab_track_bset(struct isl_tab *tab, __isl_take isl_basic_set *bset) WARN_UNUSED; +__isl_keep isl_basic_set *isl_tab_peek_bset(struct isl_tab *tab); int isl_tab_is_equality(struct isl_tab *tab, int con); int isl_tab_is_redundant(struct isl_tab *tab, int con); @@ -186,36 +233,72 @@ enum isl_ineq_type { enum isl_ineq_type isl_tab_ineq_type(struct isl_tab *tab, isl_int *ineq); struct isl_tab_undo *isl_tab_snap(struct isl_tab *tab); -int isl_tab_rollback(struct isl_tab *tab, struct isl_tab_undo *snap); +int isl_tab_rollback(struct isl_tab *tab, struct isl_tab_undo *snap) WARN_UNUSED; -struct isl_tab *isl_tab_relax(struct isl_tab *tab, int con); -struct isl_tab *isl_tab_select_facet(struct isl_tab *tab, int con); +struct isl_tab *isl_tab_relax(struct isl_tab *tab, int con) WARN_UNUSED; +int isl_tab_select_facet(struct isl_tab *tab, int con) WARN_UNUSED; +int isl_tab_unrestrict(struct isl_tab *tab, int con) WARN_UNUSED; -void isl_tab_dump(struct isl_tab *tab, FILE *out, int indent); +void isl_tab_dump(__isl_keep struct isl_tab *tab); struct isl_map *isl_tab_basic_map_partial_lexopt( struct isl_basic_map *bmap, struct isl_basic_set *dom, struct isl_set **empty, int max); +__isl_give isl_pw_multi_aff *isl_basic_map_partial_lexopt_pw_multi_aff( + __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *dom, + __isl_give isl_set **empty, int max); + +/* An isl_region represents a sequence of consecutive variables. + * pos is the location (starting at 0) of the first variable in the sequence. + */ +struct isl_region { + int pos; + int len; +}; + +__isl_give isl_vec *isl_tab_basic_set_non_trivial_lexmin( + __isl_take isl_basic_set *bset, int n_op, int n_region, + struct isl_region *region, + int (*conflict)(int con, void *user), void *user); +__isl_give isl_vec *isl_tab_basic_set_non_neg_lexmin( + __isl_take isl_basic_set *bset); /* private */ struct isl_tab_var *isl_tab_var_from_row(struct isl_tab *tab, int i); -int isl_tab_mark_redundant(struct isl_tab *tab, int row); -struct isl_tab *isl_tab_mark_empty(struct isl_tab *tab); +int isl_tab_mark_redundant(struct isl_tab *tab, int row) WARN_UNUSED; +int isl_tab_mark_empty(struct isl_tab *tab) WARN_UNUSED; struct isl_tab *isl_tab_dup(struct isl_tab *tab); -int isl_tab_extend_cons(struct isl_tab *tab, unsigned n_new); -int isl_tab_allocate_con(struct isl_tab *tab); -int isl_tab_extend_vars(struct isl_tab *tab, unsigned n_new); -int isl_tab_allocate_var(struct isl_tab *tab); -void isl_tab_pivot(struct isl_tab *tab, int row, int col); -int isl_tab_add_row(struct isl_tab *tab, isl_int *line); +struct isl_tab *isl_tab_product(struct isl_tab *tab1, struct isl_tab *tab2); +int isl_tab_extend_cons(struct isl_tab *tab, unsigned n_new) WARN_UNUSED; +int isl_tab_allocate_con(struct isl_tab *tab) WARN_UNUSED; +int isl_tab_extend_vars(struct isl_tab *tab, unsigned n_new) WARN_UNUSED; +int isl_tab_allocate_var(struct isl_tab *tab) WARN_UNUSED; +int isl_tab_pivot(struct isl_tab *tab, int row, int col) WARN_UNUSED; +int isl_tab_add_row(struct isl_tab *tab, isl_int *line) WARN_UNUSED; int isl_tab_row_is_redundant(struct isl_tab *tab, int row); int isl_tab_min_at_most_neg_one(struct isl_tab *tab, struct isl_tab_var *var); -int isl_tab_kill_col(struct isl_tab *tab, int col); +int isl_tab_sign_of_max(struct isl_tab *tab, int con); +int isl_tab_kill_col(struct isl_tab *tab, int col) WARN_UNUSED; + +int isl_tab_push(struct isl_tab *tab, enum isl_tab_undo_type type) WARN_UNUSED; +int isl_tab_push_var(struct isl_tab *tab, + enum isl_tab_undo_type type, struct isl_tab_var *var) WARN_UNUSED; +int isl_tab_push_basis(struct isl_tab *tab) WARN_UNUSED; + +struct isl_tab *isl_tab_init_samples(struct isl_tab *tab) WARN_UNUSED; +struct isl_tab *isl_tab_add_sample(struct isl_tab *tab, + __isl_take isl_vec *sample) WARN_UNUSED; +struct isl_tab *isl_tab_drop_sample(struct isl_tab *tab, int s); +int isl_tab_save_samples(struct isl_tab *tab) WARN_UNUSED; + +struct isl_tab *isl_tab_detect_equalities(struct isl_tab *tab, + struct isl_tab *tab_cone) WARN_UNUSED; + +int isl_tab_push_callback(struct isl_tab *tab, + struct isl_tab_callback *callback) WARN_UNUSED; -void isl_tab_push(struct isl_tab *tab, enum isl_tab_undo_type type); -void isl_tab_push_var(struct isl_tab *tab, - enum isl_tab_undo_type type, struct isl_tab_var *var); -void isl_tab_push_basis(struct isl_tab *tab); +int isl_tab_add_div(struct isl_tab *tab, __isl_keep isl_vec *div, + int (*add_ineq)(void *user, isl_int *), void *user); #endif