isl_sample.c File Reference

#include <isl_ctx_private.h>
#include <isl_map_private.h>
#include "isl_sample.h"
#include <isl/vec.h>
#include <isl/mat.h>
#include <isl_seq.h>
#include "isl_equalities.h"
#include "isl_tab.h"
#include "isl_basis_reduction.h"
#include <isl_factorization.h>
#include <isl_point_private.h>
#include <isl_options_private.h>
#include <isl_vec_private.h>
#include <bset_from_bmap.c>
#include <set_to_map.c>

Go to the source code of this file.

Classes
struct	isl_factored_sample_data

Functions
static __isl_give isl_vec *	isl_basic_set_sample_bounded (__isl_take isl_basic_set *bset)
static __isl_give isl_vec *	empty_sample (__isl_take isl_basic_set *bset)
static __isl_give isl_vec *	zero_sample (__isl_take isl_basic_set *bset)
static __isl_give isl_vec *	interval_sample (__isl_take isl_basic_set *bset)
static __isl_give isl_vec *	sample_eq (__isl_take isl_basic_set *bset, __isl_give isl_vec *(*recurse)(__isl_take isl_basic_set *))
static struct isl_mat *	tab_equalities (struct isl_tab *tab)
static struct isl_mat *	initial_basis (struct isl_tab *tab)
static enum isl_lp_result	compute_min (isl_ctx *ctx, struct isl_tab *tab, __isl_keep isl_vec *min, int level)
static enum isl_lp_result	compute_max (isl_ctx *ctx, struct isl_tab *tab, __isl_keep isl_vec *max, int level)
static int	greedy_search (isl_ctx *ctx, struct isl_tab *tab, __isl_keep isl_vec *min, __isl_keep isl_vec *max, int level)
__isl_give isl_vec *	isl_tab_sample (struct isl_tab *tab)
static __isl_give isl_vec *	sample_bounded (__isl_take isl_basic_set *bset)
static isl_bool	factor_sample (__isl_keep isl_basic_set *bset, void *user)
static __isl_give isl_vec *	factored_sample (__isl_take isl_basic_set *bset, __isl_take isl_factorizer *f)
static __isl_give isl_basic_set *	plug_in (__isl_take isl_basic_set *bset, __isl_take isl_vec *sample)
static __isl_give isl_vec *	rational_sample (__isl_take isl_basic_set *bset)
static __isl_give isl_basic_set *	shift_cone (__isl_take isl_basic_set *cone, __isl_take isl_vec *vec)
static __isl_give isl_vec *	round_up_in_cone (__isl_take isl_vec *vec, __isl_take isl_basic_set *cone, __isl_take isl_mat *U)
static __isl_give isl_vec *	vec_concat (__isl_take isl_vec *vec1, __isl_take isl_vec *vec2)
__isl_give isl_vec *	isl_basic_set_sample_with_cone (__isl_take isl_basic_set *bset, __isl_take isl_basic_set *cone)
static void	vec_sum_of_neg (__isl_keep isl_vec *v, isl_int *s)
static int	tab_shift_cone (struct isl_tab *tab, struct isl_tab *tab_cone, struct isl_mat *U)
int	isl_tab_set_initial_basis_with_cone (struct isl_tab *tab, struct isl_tab *tab_cone)
static __isl_give isl_vec *	gbr_sample (__isl_take isl_basic_set *bset)
static __isl_give isl_vec *	basic_set_sample (__isl_take isl_basic_set *bset, int bounded)
__isl_give isl_vec *	isl_basic_set_sample_vec (__isl_take isl_basic_set *bset)
__isl_give isl_basic_set *	isl_basic_set_from_vec (__isl_take isl_vec *vec)
__isl_give isl_basic_map *	isl_basic_map_sample (__isl_take isl_basic_map *bmap)
__isl_give isl_basic_set *	isl_basic_set_sample (__isl_take isl_basic_set *bset)
__isl_give isl_basic_map *	isl_map_sample (__isl_take isl_map *map)
__isl_give isl_basic_set *	isl_set_sample (__isl_take isl_set *set)
__isl_give isl_point *	isl_basic_set_sample_point (__isl_take isl_basic_set *bset)
__isl_give isl_point *	isl_set_sample_point (__isl_take isl_set *set)

Function Documentation

basic_set_sample()

__isl_give isl_vec * basic_set_sample ( __isl_take isl_basic_set * bset, int bounded )

static

Definition at line 1153 of file isl_sample.c.

References __isl_give, __isl_take, contains(), empty_sample(), gbr_sample(), interval_sample(), isl_basic_set, isl_basic_set_check_no_locals(), isl_basic_set_check_no_params(), isl_basic_set_contains(), isl_basic_set_dim(), isl_basic_set_free(), isl_basic_set_plain_is_empty(), isl_basic_set_sample_bounded(), isl_basic_set_sample_vec(), isl_dim_set, isl_vec_copy(), isl_vec_free(), sample_bounded(), sample_eq(), and zero_sample().

Referenced by isl_basic_set_sample_bounded(), and isl_basic_set_sample_vec().

compute_max()

enum isl_lp_result compute_max ( isl_ctx * ctx, struct isl_tab * tab, __isl_keep isl_vec * max, int level )

static

Definition at line 240 of file isl_sample.c.

References __isl_keep, isl_tab::basis, isl_mat::ctx, isl_int_neg, isl_seq_neg(), isl_tab_min(), isl_tab::n_var, isl_ctx::one, res, and isl_mat::row.

Referenced by greedy_search(), and isl_tab_sample().

compute_min()

enum isl_lp_result compute_min ( isl_ctx * ctx, struct isl_tab * tab, __isl_keep isl_vec * min, int level )

static

Definition at line 227 of file isl_sample.c.

References __isl_keep, isl_tab::basis, isl_mat::ctx, isl_tab_min(), isl_ctx::one, and isl_mat::row.

Referenced by greedy_search(), and isl_tab_sample().

empty_sample()

__isl_give isl_vec * empty_sample ( __isl_take isl_basic_set * bset )

static

Definition at line 30 of file isl_sample.c.

References __isl_give, __isl_take, isl_basic_set, isl_basic_set_free(), and isl_vec_alloc().

Referenced by basic_set_sample(), interval_sample(), and sample_bounded().

factor_sample()

isl_bool factor_sample ( __isl_keep isl_basic_set * bset, void * user )

static

Definition at line 553 of file isl_sample.c.

References __isl_keep, isl_vec::el, isl_basic_set, isl_basic_set_copy(), isl_basic_set_dim(), isl_bool_error, isl_bool_false, isl_bool_true, isl_dim_set, isl_seq_cpy(), isl_vec_free(), n, isl_factored_sample_data::pos, isl_factored_sample_data::sample, sample_bounded(), isl_vec::size, and user.

Referenced by factored_sample().

factored_sample()

__isl_give isl_vec * factored_sample ( __isl_take isl_basic_set * bset, __isl_take isl_factorizer * f )

static

Definition at line 581 of file isl_sample.c.

References __isl_give, __isl_take, isl_vec::el, f, factor_sample(), isl_basic_set, isl_basic_set_dim(), isl_basic_set_free(), isl_basic_set_get_ctx(), isl_dim_all, isl_factorizer_every_factor_basic_set(), isl_factorizer_free(), isl_int_set_si, isl_morph_copy(), isl_morph_inverse(), isl_morph_vec(), isl_vec_alloc(), isl_vec_free(), isl_factored_sample_data::pos, isl_factored_sample_data::sample, and total().

Referenced by sample_bounded().

gbr_sample()

__isl_give isl_vec * gbr_sample ( __isl_take isl_basic_set * bset )

static

Definition at line 1130 of file isl_sample.c.

References __isl_give, __isl_take, cone, isl_basic_set, isl_basic_set_copy(), isl_basic_set_dim(), isl_basic_set_free(), isl_basic_set_recession_cone(), isl_basic_set_sample_with_cone(), isl_dim_all, and sample_bounded().

Referenced by basic_set_sample().

greedy_search()

int greedy_search ( isl_ctx * ctx, struct isl_tab * tab, __isl_keep isl_vec * min, __isl_keep isl_vec * max, int level )

static

Definition at line 280 of file isl_sample.c.

References __isl_keep, isl_tab::basis, compute_max(), compute_min(), isl_die, isl_error_internal, isl_int_add, isl_int_fdiv_q_ui, isl_int_le, isl_int_neg, isl_int_set_si, isl_lp_error, isl_lp_ok, isl_tab_add_valid_eq(), isl_tab_rollback(), isl_tab_sample_is_integer(), isl_tab_snap(), isl_tab::n_unbounded, isl_tab::n_var, res, and isl_mat::row.

Referenced by isl_tab_sample().

initial_basis()

struct isl_mat * initial_basis ( struct isl_tab * tab )

static

Definition at line 200 of file isl_sample.c.

References isl_mat::ctx, isl_tab::empty, isl_mat_free(), isl_mat_identity(), isl_mat_left_hermite(), isl_mat_lin_to_aff(), isl_tab::mat, isl_tab::n_col, isl_tab::n_dead, isl_tab::n_unbounded, isl_tab::n_var, isl_tab::n_zero, and tab_equalities().

Referenced by isl_tab_sample(), and isl_tab_set_initial_basis_with_cone().

interval_sample()

__isl_give isl_vec * interval_sample ( __isl_take isl_basic_set * bset )

static

Definition at line 63 of file isl_sample.c.

References __isl_give, __isl_take, isl_vec::block, isl_blk::data, isl_vec::el, empty_sample(), isl_assert, isl_basic_set, isl_basic_set_free(), isl_basic_set_plain_is_empty(), isl_basic_set_simplify(), isl_int_clear, isl_int_init, isl_int_is_neg, isl_int_is_negone, isl_int_is_one, isl_int_neg, isl_int_set, isl_int_set_si, isl_seq_inner_product(), isl_vec_alloc(), isl_vec_free(), t, and zero_sample().

Referenced by basic_set_sample(), and sample_bounded().

isl_basic_map_sample()

__isl_give isl_basic_map * isl_basic_map_sample

(

__isl_take isl_basic_map *

bmap

)

Definition at line 1243 of file isl_sample.c.

References __isl_give, __isl_take, isl_basic_map_copy(), isl_basic_map_free(), isl_basic_map_overlying_set(), isl_basic_map_set_to_empty(), isl_basic_map_underlying_set(), isl_basic_set, isl_basic_set_from_vec(), isl_basic_set_sample_vec(), isl_vec_copy(), isl_vec_free(), and isl_vec::size.

Referenced by isl_basic_set_sample(), isl_map_sample(), and isl::basic_map::sample().

isl_basic_set_from_vec()

__isl_give isl_basic_set * isl_basic_set_from_vec

(

__isl_take isl_vec *

vec

)

Definition at line 1209 of file isl_sample.c.

References __isl_give, __isl_take, isl_ctx::error, isl_assert, isl_basic_set, isl_basic_set_alloc(), isl_basic_set_alloc_equality(), isl_basic_set_dim(), isl_basic_set_free(), isl_dim_set, isl_int_neg, isl_int_set, isl_seq_clr(), and isl_vec_free().

Referenced by add_adjacent_points(), extend_affine_hull(), initialize_hull(), isl_basic_map_sample(), isl_basic_set_from_point(), isl_tab_detect_equalities(), and scan_one().

isl_basic_set_sample()

__isl_give isl_basic_set * isl_basic_set_sample

(

__isl_take isl_basic_set *

bset

)

Definition at line 1265 of file isl_sample.c.

References __isl_give, __isl_take, isl_basic_map_sample(), and isl_basic_set.

Referenced by isl::basic_set::sample(), and test_sample().

isl_basic_set_sample_bounded()

__isl_give isl_vec * isl_basic_set_sample_bounded ( __isl_take isl_basic_set * bset )

static

Definition at line 1204 of file isl_sample.c.

References __isl_give, __isl_take, basic_set_sample(), and isl_basic_set.

Referenced by basic_set_sample().

isl_basic_set_sample_point()

__isl_give isl_point * isl_basic_set_sample_point

(

__isl_take isl_basic_set *

bset

)

Definition at line 1300 of file isl_sample.c.

References __isl_give, __isl_take, isl_basic_set, isl_basic_set_get_space(), isl_basic_set_sample_vec(), isl_basic_set_underlying_set(), and isl_point_alloc().

Referenced by ISL_ARG_CHOICE(), isl_set_sample_point(), isl_union_set_sample_point(), and isl::basic_set::sample_point().

isl_basic_set_sample_vec()

__isl_give isl_vec * isl_basic_set_sample_vec

(

__isl_take isl_basic_set *

bset

)

Definition at line 1196 of file isl_sample.c.

References __isl_give, __isl_take, basic_set_sample(), and isl_basic_set.

Referenced by basic_set_sample(), initial_solution(), isl_basic_map_is_empty(), isl_basic_map_sample(), isl_basic_set_sample_point(), main(), and solve_ilp_search().

isl_basic_set_sample_with_cone()

__isl_give isl_vec * isl_basic_set_sample_with_cone	(	__isl_take isl_basic_set *	bset,
		__isl_take isl_basic_set *	cone )

Definition at line 946 of file isl_sample.c.

References __isl_give, __isl_take, cone, isl_basic_set, isl_basic_set_copy(), isl_basic_set_dim(), isl_basic_set_drop_constraints_involving(), isl_basic_set_drop_dims(), isl_basic_set_free(), isl_basic_set_get_ctx(), isl_basic_set_preimage(), isl_dim_all, isl_mat_copy(), isl_mat_free(), isl_mat_left_hermite(), isl_mat_lin_to_aff(), isl_mat_sub_alloc6(), isl_mat_vec_product(), isl_vec_copy(), M(), plug_in(), rational_sample(), round_up_in_cone(), sample_bounded(), isl_vec::size, total(), and vec_concat().

Referenced by gbr_get_sample(), and gbr_sample().

isl_map_sample()

__isl_give isl_basic_map * isl_map_sample

(

__isl_take isl_map *

map

)

Definition at line 1270 of file isl_sample.c.

References __isl_give, __isl_take, isl_basic_map_copy(), ISL_BASIC_MAP_EMPTY, isl_basic_map_empty(), isl_basic_map_free(), isl_basic_map_sample(), ISL_F_ISSET, isl_map_free(), isl_map_get_space(), and map.

Referenced by isl_set_sample(), isl::map::sample(), and sample_entry().

isl_set_sample()

__isl_give isl_basic_set * isl_set_sample

(

__isl_take isl_set *

set

)

Definition at line 1295 of file isl_sample.c.

References __isl_give, __isl_take, bset_from_bmap(), isl_basic_set, isl_map_sample(), isl_set, set, and set_to_map.

Referenced by isl::set::sample().

isl_set_sample_point()

__isl_give isl_point * isl_set_sample_point

(

__isl_take isl_set *

set

)

Definition at line 1312 of file isl_sample.c.

References __isl_give, __isl_take, isl_basic_set_copy(), isl_basic_set_sample_point(), isl_point_free(), isl_point_is_void(), isl_point_void(), isl_set, isl_set_free(), isl_set_get_space(), and set.

Referenced by ISL_ARG_CHILD(), isl::set::sample_point(), test_eval_1(), test_eval_2(), test_eval_aff(), and verify_point().

isl_tab_sample()

__isl_give isl_vec * isl_tab_sample

(

struct isl_tab *

tab

)

Definition at line 381 of file isl_sample.c.

References __isl_give, isl_tab::basis, compute_max(), compute_min(), isl_mat::ctx, isl_vec::el, isl_tab::empty, isl_options::gbr, isl_options::gbr_only_first, greedy_search(), init(), initial_basis(), isl_alloc_array, isl_assert, isl_die, isl_error_internal, ISL_GBR_ALWAYS, ISL_GBR_NEVER, ISL_GBR_ONCE, isl_int_add_ui, isl_int_gt, isl_int_is_one, isl_int_lt, isl_int_neg, isl_int_set_si, isl_lp_error, isl_lp_ok, isl_mat_copy(), isl_mat_vec_inverse_product(), isl_mat_vec_product(), isl_tab_add_valid_eq(), isl_tab_compute_reduced_basis(), isl_tab_extend_cons(), isl_tab_get_sample_value(), isl_tab_rollback(), isl_tab_sample_is_integer(), isl_tab_snap(), isl_vec_alloc(), isl_vec_ceil(), isl_vec_free(), isl_tab::mat, isl_mat::n_col, isl_mat::n_row, isl_tab::n_unbounded, isl_tab::n_var, isl_tab::n_zero, isl_ctx::opt, res, and isl_mat::row.

Referenced by gbr_get_sample(), outside_point(), sample_bounded(), and uset_affine_hull_bounded().

isl_tab_set_initial_basis_with_cone()

int isl_tab_set_initial_basis_with_cone	(	struct isl_tab *	tab,
		struct isl_tab *	tab_cone )

Definition at line 1088 of file isl_sample.c.

References isl_tab::basis, initial_basis(), isl_mat_concat(), isl_mat_free(), isl_mat_left_hermite(), isl_mat_lin_to_aff(), isl_tab::n_col, isl_tab::n_dead, isl_mat::n_row, isl_tab::n_unbounded, isl_tab::n_var, isl_tab::n_zero, tab_equalities(), and tab_shift_cone().

Referenced by isl_tab_detect_equalities().

plug_in()

__isl_give isl_basic_set * plug_in ( __isl_take isl_basic_set * bset, __isl_take isl_vec * sample )

static

Definition at line 700 of file isl_sample.c.

References __isl_give, __isl_take, isl_basic_set, isl_basic_set_dim(), isl_basic_set_free(), isl_basic_set_preimage(), isl_dim_all, isl_int_set, isl_int_set_si, isl_mat_alloc(), isl_seq_clr(), isl_vec_free(), isl_mat::n_col, isl_mat::row, and total().

Referenced by isl_basic_set_sample_with_cone().

rational_sample()

__isl_give isl_vec * rational_sample ( __isl_take isl_basic_set * bset )

static

Definition at line 736 of file isl_sample.c.

References __isl_give, __isl_take, isl_basic_set, isl_basic_set_free(), isl_tab_free(), isl_tab_from_basic_set(), and isl_tab_get_sample_value().

Referenced by isl_basic_set_sample_with_cone(), and round_up_in_cone().

round_up_in_cone()

__isl_give isl_vec * round_up_in_cone ( __isl_take isl_vec * vec, __isl_take isl_basic_set * cone, __isl_take isl_mat * U )

static

Definition at line 843 of file isl_sample.c.

References __isl_give, __isl_take, cone, isl_assert, isl_basic_set, isl_basic_set_dim(), isl_basic_set_free(), isl_basic_set_preimage(), isl_basic_set_remove_dims(), isl_dim_all, isl_dim_set, isl_int_is_one, isl_mat_free(), isl_vec_ceil(), isl_vec_free(), rational_sample(), shift_cone(), and total().

Referenced by isl_basic_set_sample_with_cone().

sample_bounded()

__isl_give isl_vec * sample_bounded ( __isl_take isl_basic_set * bset )

static

Definition at line 627 of file isl_sample.c.

References __isl_give, __isl_take, isl_tab::empty, empty_sample(), f, factored_sample(), interval_sample(), isl_basic_set, isl_basic_set_dim(), ISL_BASIC_SET_EMPTY, isl_basic_set_factorizer(), isl_basic_set_free(), isl_basic_set_get_ctx(), ISL_BASIC_SET_NO_IMPLICIT, isl_basic_set_plain_is_empty(), isl_dim_all, ISL_F_ISSET, ISL_F_SET, isl_factorizer_free(), isl_tab_detect_implicit_equalities(), isl_tab_free(), isl_tab_from_basic_set(), isl_tab_sample(), isl_vec_alloc(), isl_vec_copy(), isl_vec_free(), sample_bounded(), sample_eq(), isl_vec::size, and zero_sample().

Referenced by basic_set_sample(), factor_sample(), gbr_sample(), isl_basic_set_sample_with_cone(), and sample_bounded().

sample_eq()

__isl_give isl_vec * sample_eq ( __isl_take isl_basic_set * bset, __isl_give isl_vec *(* recurse )(__isl_take isl_basic_set *) )

static

Definition at line 130 of file isl_sample.c.

References __isl_give, __isl_take, isl_basic_set, isl_basic_set_remove_equalities(), isl_mat_free(), isl_mat_vec_product(), recurse(), and isl_vec::size.

Referenced by basic_set_sample(), and sample_bounded().

shift_cone()

__isl_give isl_basic_set * shift_cone ( __isl_take isl_basic_set * cone, __isl_take isl_vec * vec )

static

Definition at line 786 of file isl_sample.c.

References __isl_give, __isl_take, cone, isl_assert, isl_basic_set, isl_basic_set_alloc_inequality(), isl_basic_set_alloc_space(), isl_basic_set_dim(), isl_basic_set_finalize(), isl_basic_set_free(), isl_basic_set_get_space(), isl_dim_all, isl_int_add, isl_int_cdiv_q, isl_int_is_nonneg, isl_int_neg, isl_seq_cpy(), isl_seq_inner_product(), isl_vec_free(), and total().

Referenced by round_up_in_cone().

tab_equalities()

struct isl_mat * tab_equalities ( struct isl_tab * tab )

static

Definition at line 152 of file isl_sample.c.

References isl_tab::con, isl_mat::ctx, isl_tab::empty, isl_tab_var::index, isl_tab_var::is_row, isl_assert, isl_basic_set, isl_mat_alloc(), isl_mat_free(), isl_mat_identity(), isl_seq_cpy(), isl_tab_peek_bset(), isl_tab::mat, isl_tab::n_col, isl_tab::n_con, isl_tab::n_dead, isl_tab::n_var, and isl_mat::row.

Referenced by initial_basis(), and isl_tab_set_initial_basis_with_cone().

tab_shift_cone()

int tab_shift_cone ( struct isl_tab * tab, struct isl_tab * tab_cone, struct isl_mat * U )

static

Definition at line 1024 of file isl_sample.c.

References isl_vec::el, isl_basic_set, isl_int_add, isl_int_clear, isl_int_init, isl_int_is_zero, isl_int_sub, isl_mat_copy(), isl_mat_drop_cols(), isl_mat_free(), isl_seq_cpy(), isl_tab_add_ineq(), isl_tab_extend_cons(), isl_tab_is_equality(), isl_tab_peek_bset(), isl_vec_alloc(), isl_vec_free(), isl_vec_mat_product(), isl_tab::n_eq, isl_tab::n_unbounded, isl_tab::n_var, and vec_sum_of_neg().

Referenced by isl_tab_set_initial_basis_with_cone().

vec_concat()

__isl_give isl_vec * vec_concat ( __isl_take isl_vec * vec1, __isl_take isl_vec * vec2 )

static

Definition at line 880 of file isl_sample.c.

References __isl_give, __isl_take, isl_vec::el, isl_assert, isl_int_is_one, isl_seq_cpy(), isl_vec_alloc(), and isl_vec_free().

Referenced by isl_basic_set_sample_with_cone().

vec_sum_of_neg()

void vec_sum_of_neg ( __isl_keep isl_vec * v, isl_int * s )

static

Definition at line 996 of file isl_sample.c.

References __isl_keep, isl_int_add, isl_int_is_neg, and isl_int_set_si.

Referenced by tab_shift_cone().

zero_sample()

__isl_give isl_vec * zero_sample ( __isl_take isl_basic_set * bset )

static

Definition at line 43 of file isl_sample.c.

References __isl_give, __isl_take, isl_vec::el, isl_basic_set, isl_basic_set_dim(), isl_basic_set_free(), isl_dim_all, isl_int_set_si, isl_seq_clr(), and isl_vec_alloc().

Referenced by basic_set_sample(), interval_sample(), and sample_bounded().