isl/dist/isl_sample.c

753 /* Given a linear cone "cone" and a rational point "vec",
754  * construct a polyhedron with shifted copies of the constraints in "cone",
755  * i.e., a polyhedron with "cone" as its recession cone, such that each
757  * lies entirely inside the affine cone 'vec + cone'.
759  * to yield an integer point that lies inside said affine cone.
761  * Denote the constraints of cone by "<a_i, x> >= 0" and the rational
763  * Let b_i = <a_i, v>.  Then the affine cone 'vec + cone' is given
765  * The polyhedron <a_i, x> - ceil{b/d} >= 0 is a subset of this affine cone.
766  * We prefer this polyhedron over the actual affine cone because it doesn't
769  * this polyhedron, then the whole unit cube at x lies inside the affine cone.
780  * Note that if cone were known to have only non-negative rays
786 static __isl_give isl_basic_set *shift_cone(__isl_take isl_basic_set *cone,
794 	total = isl_basic_set_dim(cone, isl_dim_all);
798 	isl_assert(cone->ctx, cone->n_eq == 0, goto error);
800 	shift = isl_basic_set_alloc_space(isl_basic_set_get_space(cone),
801 					0, 0, cone->n_ineq);
803 	for (i = 0; i < cone->n_ineq; ++i) {
807 		isl_seq_cpy(shift->ineq[k] + 1, cone->ineq[i] + 1, total);
821 	isl_basic_set_free(cone);
827 	isl_basic_set_free(cone);
833  * such that cone is the recession cone of the original basic set,
837  * If not, we transform the cone in the same way as the basic set,
838  * pick a point x in this cone shifted to the rational point such that
839  * the whole unit cube at x is also inside this affine cone.
844 	__isl_take isl_basic_set *cone, __isl_take isl_mat *U)
848 	if (!vec || !cone || !U)
854 		isl_basic_set_free(cone);
858 	total = isl_basic_set_dim(cone, isl_dim_all);
861 	cone = isl_basic_set_preimage(cone, U);
862 	cone = isl_basic_set_remove_dims(cone, isl_dim_set,
865 	cone = shift_cone(cone, vec);
867 	vec = rational_sample(cone);
873 	isl_basic_set_free(cone);
909 /* Give a basic set "bset" with recession cone "cone", compute and
912  * If the recession cone is full-dimensional, then we know that
915  * If the recession cone is not full-dimensional, then we first
919  * the equalities in the recession cone to equalities on the first
938  * a full-dimensional recession cone.
947 	__isl_take isl_basic_set *bset, __isl_take isl_basic_set *cone)
957 	total = isl_basic_set_dim(cone, isl_dim_all);
962 	cone_dim = total - cone->n_eq;
964 	M = isl_mat_sub_alloc6(ctx, cone->eq, 0, cone->n_eq, 1, total);
980 		isl_basic_set_free(cone);
986 	cone_sample = round_up_in_cone(cone_sample, cone, isl_mat_copy(U));
991 	isl_basic_set_free(cone);
1008  * to the recession cone and the inverse of a new basis U = inv(B),
1076  * for the corresponding recession cone.
1081  * If the tableau is bounded, i.e., if the recession cone
1085  * i.e., equalities in the recession cone.
1126  * recession cone.  If so, we perform some extra preprocessing in
1133 	struct isl_basic_set *cone;
1139 	cone = isl_basic_set_recession_cone(isl_basic_set_copy(bset));
1140 	if (!cone)
1143 	if (cone->n_eq < dim)
1144 		return isl_basic_set_sample_with_cone(bset, cone);
1146 	isl_basic_set_free(cone);