31 static void swap_equality(__isl_keep isl_basic_map *bmap, int a, int b)  in swap_equality()  argument
33 	isl_int *t = bmap->eq[a];  in swap_equality()
34 	bmap->eq[a] = bmap->eq[b];  in swap_equality()
35 	bmap->eq[b] = t;  in swap_equality()
38 static void swap_inequality(__isl_keep isl_basic_map *bmap, int a, int b)  in swap_inequality()  argument
41 		isl_int *t = bmap->ineq[a];  in swap_inequality()
42 		bmap->ineq[a] = bmap->ineq[b];  in swap_inequality()
43 		bmap->ineq[b] = t;  in swap_inequality()
48 	__isl_take isl_basic_map *bmap)  in isl_basic_map_normalize_constraints()  argument
52 	isl_size total = isl_basic_map_dim(bmap, isl_dim_all);  in isl_basic_map_normalize_constraints()
55 		return isl_basic_map_free(bmap);  in isl_basic_map_normalize_constraints()
58 	for (i = bmap->n_eq - 1; i >= 0; --i) {  in isl_basic_map_normalize_constraints()
59 		isl_seq_gcd(bmap->eq[i]+1, total, &gcd);  in isl_basic_map_normalize_constraints()
61 			if (!isl_int_is_zero(bmap->eq[i][0])) {  in isl_basic_map_normalize_constraints()
62 				bmap = isl_basic_map_set_to_empty(bmap);  in isl_basic_map_normalize_constraints()
65 			if (isl_basic_map_drop_equality(bmap, i) < 0)  in isl_basic_map_normalize_constraints()
69 		if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))  in isl_basic_map_normalize_constraints()
70 			isl_int_gcd(gcd, gcd, bmap->eq[i][0]);  in isl_basic_map_normalize_constraints()
73 		if (!isl_int_is_divisible_by(bmap->eq[i][0], gcd)) {  in isl_basic_map_normalize_constraints()
74 			bmap = isl_basic_map_set_to_empty(bmap);  in isl_basic_map_normalize_constraints()
77 		isl_seq_scale_down(bmap->eq[i], bmap->eq[i], gcd, 1+total);  in isl_basic_map_normalize_constraints()
80 	for (i = bmap->n_ineq - 1; i >= 0; --i) {  in isl_basic_map_normalize_constraints()
81 		isl_seq_gcd(bmap->ineq[i]+1, total, &gcd);  in isl_basic_map_normalize_constraints()
83 			if (isl_int_is_neg(bmap->ineq[i][0])) {  in isl_basic_map_normalize_constraints()
84 				bmap = isl_basic_map_set_to_empty(bmap);  in isl_basic_map_normalize_constraints()
87 			if (isl_basic_map_drop_inequality(bmap, i) < 0)  in isl_basic_map_normalize_constraints()
91 		if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))  in isl_basic_map_normalize_constraints()
92 			isl_int_gcd(gcd, gcd, bmap->ineq[i][0]);  in isl_basic_map_normalize_constraints()
95 		isl_int_fdiv_q(bmap->ineq[i][0], bmap->ineq[i][0], gcd);  in isl_basic_map_normalize_constraints()
96 		isl_seq_scale_down(bmap->ineq[i]+1, bmap->ineq[i]+1, gcd, total);  in isl_basic_map_normalize_constraints()
100 	return bmap;  in isl_basic_map_normalize_constraints()
103 	isl_basic_map_free(bmap);  in isl_basic_map_normalize_constraints()
110 	isl_basic_map *bmap = bset_to_bmap(bset);  in isl_basic_set_normalize_constraints()  local
111 	return bset_from_bmap(isl_basic_map_normalize_constraints(bmap));  in isl_basic_set_normalize_constraints()
135 	__isl_take isl_basic_map *bmap, int div, int pos)  in reduce_coefficient_in_div()  argument
141 	isl_int_fdiv_r(shift, bmap->div[div][1 + pos], bmap->div[div][0]);  in reduce_coefficient_in_div()
143 	add_one = isl_int_gt(shift, bmap->div[div][0]);  in reduce_coefficient_in_div()
144 	isl_int_fdiv_q(shift, bmap->div[div][1 + pos], bmap->div[div][0]);  in reduce_coefficient_in_div()
148 	bmap = isl_basic_map_shift_div(bmap, div, pos, shift);  in reduce_coefficient_in_div()
151 	return bmap;  in reduce_coefficient_in_div()
160 static isl_bool needs_reduction(__isl_keep isl_basic_map *bmap, int div,  in needs_reduction()  argument
165 	if (isl_int_is_zero(bmap->div[div][1 + pos]))  in needs_reduction()
168 	isl_int_mul_ui(bmap->div[div][1 + pos], bmap->div[div][1 + pos], 2);  in needs_reduction()
169 	r = isl_int_abs_ge(bmap->div[div][1 + pos], bmap->div[div][0]) &&  in needs_reduction()
170 	    !isl_int_eq(bmap->div[div][1 + pos], bmap->div[div][0]);  in needs_reduction()
171 	isl_int_divexact_ui(bmap->div[div][1 + pos],  in needs_reduction()
172 			    bmap->div[div][1 + pos], 2);  in needs_reduction()
183 	__isl_take isl_basic_map *bmap, int div)  in reduce_div_coefficients_of_div()  argument
188 	total = isl_basic_map_dim(bmap, isl_dim_all);  in reduce_div_coefficients_of_div()
190 		return isl_basic_map_free(bmap);  in reduce_div_coefficients_of_div()
194 		reduce = needs_reduction(bmap, div, i);  in reduce_div_coefficients_of_div()
196 			return isl_basic_map_free(bmap);  in reduce_div_coefficients_of_div()
199 		bmap = reduce_coefficient_in_div(bmap, div, i);  in reduce_div_coefficients_of_div()
200 		if (!bmap)  in reduce_div_coefficients_of_div()
204 	return bmap;  in reduce_div_coefficients_of_div()
213 	__isl_take isl_basic_map *bmap)  in reduce_div_coefficients()  argument
217 	if (!bmap)  in reduce_div_coefficients()
219 	if (bmap->n_div == 0)  in reduce_div_coefficients()
220 		return bmap;  in reduce_div_coefficients()
222 	for (i = 0; i < bmap->n_div; ++i) {  in reduce_div_coefficients()
223 		if (isl_int_is_zero(bmap->div[i][0]))  in reduce_div_coefficients()
225 		bmap = reduce_div_coefficients_of_div(bmap, i);  in reduce_div_coefficients()
226 		if (!bmap)  in reduce_div_coefficients()
230 	return bmap;  in reduce_div_coefficients()
247 	__isl_take isl_basic_map *bmap, int div)  in normalize_div_expression()  argument
249 	isl_size total = isl_basic_map_dim(bmap, isl_dim_all);  in normalize_div_expression()
250 	isl_ctx *ctx = bmap->ctx;  in normalize_div_expression()
253 		return isl_basic_map_free(bmap);  in normalize_div_expression()
254 	if (isl_int_is_zero(bmap->div[div][0]))  in normalize_div_expression()
255 		return bmap;  in normalize_div_expression()
256 	isl_seq_gcd(bmap->div[div] + 2, total, &ctx->normalize_gcd);  in normalize_div_expression()
257 	isl_int_gcd(ctx->normalize_gcd, ctx->normalize_gcd, bmap->div[div][0]);  in normalize_div_expression()
259 		return bmap;  in normalize_div_expression()
260 	isl_int_fdiv_q(bmap->div[div][1], bmap->div[div][1],  in normalize_div_expression()
262 	isl_int_divexact(bmap->div[div][0], bmap->div[div][0],  in normalize_div_expression()
264 	isl_seq_scale_down(bmap->div[div] + 2, bmap->div[div] + 2,  in normalize_div_expression()
267 	return bmap;  in normalize_div_expression()
284 	__isl_take isl_basic_map *bmap)  in normalize_div_expressions()  argument
288 	if (!bmap)  in normalize_div_expressions()
290 	if (bmap->n_div == 0)  in normalize_div_expressions()
291 		return bmap;  in normalize_div_expressions()
293 	for (i = 0; i < bmap->n_div; ++i)  in normalize_div_expressions()
294 		bmap = normalize_div_expression(bmap, i);  in normalize_div_expressions()
296 	return bmap;  in normalize_div_expressions()
302 	__isl_take isl_basic_map *bmap,  in eliminate_var_using_equality()  argument
310 	total = isl_basic_map_dim(bmap, isl_dim_all);  in eliminate_var_using_equality()
311 	v_div = isl_basic_map_var_offset(bmap, isl_dim_div);  in eliminate_var_using_equality()
313 		return isl_basic_map_free(bmap);  in eliminate_var_using_equality()
314 	last_div = isl_seq_last_non_zero(eq + 1 + v_div, bmap->n_div);  in eliminate_var_using_equality()
315 	for (k = 0; k < bmap->n_eq; ++k) {  in eliminate_var_using_equality()
316 		if (bmap->eq[k] == eq)  in eliminate_var_using_equality()
318 		if (isl_int_is_zero(bmap->eq[k][1+pos]))  in eliminate_var_using_equality()
322 		isl_seq_elim(bmap->eq[k], eq, 1+pos, 1+total, NULL);  in eliminate_var_using_equality()
323 		isl_seq_normalize(bmap->ctx, bmap->eq[k], 1 + total);  in eliminate_var_using_equality()
326 	for (k = 0; k < bmap->n_ineq; ++k) {  in eliminate_var_using_equality()
327 		if (isl_int_is_zero(bmap->ineq[k][1+pos]))  in eliminate_var_using_equality()
331 		isl_seq_elim(bmap->ineq[k], eq, 1+pos, 1+total, NULL);  in eliminate_var_using_equality()
332 		isl_seq_normalize(bmap->ctx, bmap->ineq[k], 1 + total);  in eliminate_var_using_equality()
333 		ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);  in eliminate_var_using_equality()
334 		ISL_F_CLR(bmap, ISL_BASIC_MAP_SORTED);  in eliminate_var_using_equality()
337 	for (k = 0; k < bmap->n_div; ++k) {  in eliminate_var_using_equality()
338 		if (isl_int_is_zero(bmap->div[k][0]))  in eliminate_var_using_equality()
340 		if (isl_int_is_zero(bmap->div[k][1+1+pos]))  in eliminate_var_using_equality()
352 			isl_seq_elim(bmap->div[k]+1, eq,  in eliminate_var_using_equality()
353 					1+pos, 1+total, &bmap->div[k][0]);  in eliminate_var_using_equality()
354 			bmap = normalize_div_expression(bmap, k);  in eliminate_var_using_equality()
355 			if (!bmap)  in eliminate_var_using_equality()
358 			isl_seq_clr(bmap->div[k], 1 + total);  in eliminate_var_using_equality()
361 	return bmap;  in eliminate_var_using_equality()
366 static __isl_give isl_basic_map *eliminate_div(__isl_take isl_basic_map *bmap,  in eliminate_div()  argument
372 	v_div = isl_basic_map_var_offset(bmap, isl_dim_div);  in eliminate_div()
374 		return isl_basic_map_free(bmap);  in eliminate_div()
376 	bmap = eliminate_var_using_equality(bmap, pos, eq, keep_divs, NULL);  in eliminate_div()
378 	bmap = isl_basic_map_drop_div(bmap, div);  in eliminate_div()
380 	return bmap;  in eliminate_div()
386 static isl_bool ok_to_eliminate_div(__isl_keep isl_basic_map *bmap, isl_int *eq,  in ok_to_eliminate_div()  argument
394 	v_div = isl_basic_map_var_offset(bmap, isl_dim_div);  in ok_to_eliminate_div()
399 	last_div = isl_seq_last_non_zero(eq + 1 + v_div, bmap->n_div);  in ok_to_eliminate_div()
404 		if (isl_int_is_zero(bmap->div[k][0]))  in ok_to_eliminate_div()
406 		if (!isl_int_is_zero(bmap->div[k][1 + 1 + pos]))  in ok_to_eliminate_div()
416 	__isl_take isl_basic_map *bmap, int *progress)  in eliminate_divs_eq()  argument
423 	bmap = isl_basic_map_order_divs(bmap);  in eliminate_divs_eq()
425 	if (!bmap)  in eliminate_divs_eq()
428 	off = isl_basic_map_offset(bmap, isl_dim_div);  in eliminate_divs_eq()
430 	for (d = bmap->n_div - 1; d >= 0 ; --d) {  in eliminate_divs_eq()
431 		for (i = 0; i < bmap->n_eq; ++i) {  in eliminate_divs_eq()
434 			if (!isl_int_is_one(bmap->eq[i][off + d]) &&  in eliminate_divs_eq()
435 			    !isl_int_is_negone(bmap->eq[i][off + d]))  in eliminate_divs_eq()
437 			ok = ok_to_eliminate_div(bmap, bmap->eq[i], d);  in eliminate_divs_eq()
439 				return isl_basic_map_free(bmap);  in eliminate_divs_eq()
444 			bmap = eliminate_div(bmap, bmap->eq[i], d, 1);  in eliminate_divs_eq()
445 			if (isl_basic_map_drop_equality(bmap, i) < 0)  in eliminate_divs_eq()
446 				return isl_basic_map_free(bmap);  in eliminate_divs_eq()
451 		return eliminate_divs_eq(bmap, progress);  in eliminate_divs_eq()
452 	return bmap;  in eliminate_divs_eq()
458 	__isl_take isl_basic_map *bmap, int *progress)  in eliminate_divs_ineq()  argument
465 	if (!bmap)  in eliminate_divs_ineq()
468 	ctx = bmap->ctx;  in eliminate_divs_ineq()
469 	off = isl_basic_map_offset(bmap, isl_dim_div);  in eliminate_divs_ineq()
471 	for (d = bmap->n_div - 1; d >= 0 ; --d) {  in eliminate_divs_ineq()
472 		for (i = 0; i < bmap->n_eq; ++i)  in eliminate_divs_ineq()
473 			if (!isl_int_is_zero(bmap->eq[i][off + d]))  in eliminate_divs_ineq()
475 		if (i < bmap->n_eq)  in eliminate_divs_ineq()
477 		for (i = 0; i < bmap->n_ineq; ++i)  in eliminate_divs_ineq()
478 			if (isl_int_abs_gt(bmap->ineq[i][off + d], ctx->one))  in eliminate_divs_ineq()
480 		if (i < bmap->n_ineq)  in eliminate_divs_ineq()
483 		bmap = isl_basic_map_eliminate_vars(bmap, (off-1)+d, 1);  in eliminate_divs_ineq()
484 		if (!bmap || ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))  in eliminate_divs_ineq()
486 		bmap = isl_basic_map_drop_div(bmap, d);  in eliminate_divs_ineq()
487 		if (!bmap)  in eliminate_divs_ineq()
490 	return bmap;  in eliminate_divs_ineq()
497 static isl_bool bmap_eq_involves_unknown_divs(__isl_keep isl_basic_map *bmap,  in bmap_eq_involves_unknown_divs()  argument
503 	if (!bmap)  in bmap_eq_involves_unknown_divs()
506 	o_div = isl_basic_map_offset(bmap, isl_dim_div);  in bmap_eq_involves_unknown_divs()
510 		if (isl_int_is_zero(bmap->eq[eq][o_div + first + i]))  in bmap_eq_involves_unknown_divs()
512 		unknown = isl_basic_map_div_is_marked_unknown(bmap, first + i);  in bmap_eq_involves_unknown_divs()
545 static __isl_give isl_basic_map *set_div_from_eq(__isl_take isl_basic_map *bmap,  in set_div_from_eq()  argument
552 	if (!bmap)  in set_div_from_eq()
555 	if (!isl_int_is_zero(bmap->div[div][0]))  in set_div_from_eq()
556 		return bmap;  in set_div_from_eq()
558 	involves = bmap_eq_involves_unknown_divs(bmap, eq, 0, div);  in set_div_from_eq()
560 		return isl_basic_map_free(bmap);  in set_div_from_eq()
562 		return bmap;  in set_div_from_eq()
564 	total = isl_basic_map_dim(bmap, isl_dim_all);  in set_div_from_eq()
566 		return isl_basic_map_free(bmap);  in set_div_from_eq()
567 	o_div = isl_basic_map_offset(bmap, isl_dim_div);  in set_div_from_eq()
568 	isl_seq_neg(bmap->div[div] + 1, bmap->eq[eq], 1 + total);  in set_div_from_eq()
569 	isl_int_set_si(bmap->div[div][1 + o_div + div], 0);  in set_div_from_eq()
570 	isl_int_set(bmap->div[div][0], bmap->eq[eq][o_div + div]);  in set_div_from_eq()
574 	return bmap;  in set_div_from_eq()
596 __isl_give isl_basic_map *isl_basic_map_gauss5(__isl_take isl_basic_map *bmap,  in isl_basic_map_gauss5()  argument
609 		bmap = isl_basic_map_order_divs(bmap);  in isl_basic_map_gauss5()
611 	total = isl_basic_map_dim(bmap, isl_dim_all);  in isl_basic_map_gauss5()
613 		return isl_basic_map_free(bmap);  in isl_basic_map_gauss5()
615 	total_var = total - bmap->n_div;  in isl_basic_map_gauss5()
618 	for (done = 0; done < bmap->n_eq; ++done) {  in isl_basic_map_gauss5()
620 			for (k = done; k < bmap->n_eq; ++k)  in isl_basic_map_gauss5()
621 				if (!isl_int_is_zero(bmap->eq[k][1+last_var]))  in isl_basic_map_gauss5()
623 			if (k < bmap->n_eq)  in isl_basic_map_gauss5()
629 			swap_equality(bmap, k, done);  in isl_basic_map_gauss5()
631 				return isl_basic_map_free(bmap);  in isl_basic_map_gauss5()
633 		if (isl_int_is_neg(bmap->eq[done][1+last_var]))  in isl_basic_map_gauss5()
634 			isl_seq_neg(bmap->eq[done], bmap->eq[done], 1+total);  in isl_basic_map_gauss5()
636 		bmap = eliminate_var_using_equality(bmap, last_var,  in isl_basic_map_gauss5()
637 						bmap->eq[done], 1, progress);  in isl_basic_map_gauss5()
640 			bmap = set_div_from_eq(bmap, last_var - total_var,  in isl_basic_map_gauss5()
642 		if (!bmap)  in isl_basic_map_gauss5()
645 	if (done == bmap->n_eq)  in isl_basic_map_gauss5()
646 		return bmap;  in isl_basic_map_gauss5()
647 	for (k = done; k < bmap->n_eq; ++k) {  in isl_basic_map_gauss5()
648 		if (isl_int_is_zero(bmap->eq[k][0]))  in isl_basic_map_gauss5()
650 		if (drop && drop(bmap->n_eq, user) < 0)  in isl_basic_map_gauss5()
651 			return isl_basic_map_free(bmap);  in isl_basic_map_gauss5()
652 		return isl_basic_map_set_to_empty(bmap);  in isl_basic_map_gauss5()
654 	n_drop = bmap->n_eq - done;  in isl_basic_map_gauss5()
655 	bmap = isl_basic_map_free_equality(bmap, n_drop);  in isl_basic_map_gauss5()
657 		return isl_basic_map_free(bmap);  in isl_basic_map_gauss5()
658 	return bmap;  in isl_basic_map_gauss5()
661 __isl_give isl_basic_map *isl_basic_map_gauss(__isl_take isl_basic_map *bmap,  in isl_basic_map_gauss()  argument
664 	return isl_basic_map_gauss5(bmap, progress, NULL, NULL, NULL);  in isl_basic_map_gauss()
704 	__isl_keep isl_basic_map *bmap)  in create_constraint_index()  argument
709 	if (!bmap)  in create_constraint_index()
711 	ci->total = isl_basic_map_dim(bmap, isl_dim_all);  in create_constraint_index()
714 	if (bmap->n_ineq == 0)  in create_constraint_index()
716 	ci->size = round_up(4 * (bmap->n_ineq + 1) / 3 - 1);  in create_constraint_index()
718 	ctx = isl_basic_map_get_ctx(bmap);  in create_constraint_index()
758 	__isl_keep isl_basic_map *bmap, int k)  in hash_index()  argument
760 	return hash_index_ineq(ci, &bmap->ineq[k]);  in hash_index()
817 	__isl_take isl_basic_map *bmap, int *progress)  in remove_duplicate_divs()  argument
829 	bmap = isl_basic_map_order_divs(bmap);  in remove_duplicate_divs()
830 	if (!bmap || bmap->n_div <= 1)  in remove_duplicate_divs()
831 		return bmap;  in remove_duplicate_divs()
833 	v_div = isl_basic_map_var_offset(bmap, isl_dim_div);  in remove_duplicate_divs()
835 		return isl_basic_map_free(bmap);  in remove_duplicate_divs()
836 	total = v_div + bmap->n_div;  in remove_duplicate_divs()
838 	ctx = bmap->ctx;  in remove_duplicate_divs()
839 	for (k = bmap->n_div - 1; k >= 0; --k)  in remove_duplicate_divs()
840 		if (!isl_int_is_zero(bmap->div[k][0]))  in remove_duplicate_divs()
843 		return bmap;  in remove_duplicate_divs()
845 	size = round_up(4 * bmap->n_div / 3 - 1);  in remove_duplicate_divs()
847 		return bmap;  in remove_duplicate_divs()
848 	elim_for = isl_calloc_array(ctx, int, bmap->n_div);  in remove_duplicate_divs()
858 	index[isl_seq_get_hash_bits(bmap->div[k], 2+total, bits)] = k + 1;  in remove_duplicate_divs()
862 		if (isl_int_is_zero(bmap->div[k][0]))  in remove_duplicate_divs()
865 		hash = isl_seq_get_hash_bits(bmap->div[k], 2+total, bits);  in remove_duplicate_divs()
867 			if (isl_seq_eq(bmap->div[k],  in remove_duplicate_divs()
868 				       bmap->div[index[h]-1], 2+total))  in remove_duplicate_divs()
877 	for (l = bmap->n_div - 1; l >= 0; --l) {  in remove_duplicate_divs()
883 		bmap = eliminate_div(bmap, eq.data, l, 1);  in remove_duplicate_divs()
884 		if (!bmap)  in remove_duplicate_divs()
894 	return bmap;  in remove_duplicate_divs()
897 static int n_pure_div_eq(__isl_keep isl_basic_map *bmap)  in n_pure_div_eq()  argument
902 	v_div = isl_basic_map_var_offset(bmap, isl_dim_div);  in n_pure_div_eq()
905 	for (i = 0, j = bmap->n_div-1; i < bmap->n_eq; ++i) {  in n_pure_div_eq()
906 		while (j >= 0 && isl_int_is_zero(bmap->eq[i][1 + v_div + j]))  in n_pure_div_eq()
910 		if (isl_seq_first_non_zero(bmap->eq[i] + 1 + v_div, j) != -1)  in n_pure_div_eq()
964 static __isl_give isl_basic_map *normalize_divs(__isl_take isl_basic_map *bmap,  in normalize_divs()  argument
979 	if (!bmap)  in normalize_divs()
982 	if (bmap->n_div == 0)  in normalize_divs()
983 		return bmap;  in normalize_divs()
985 	if (bmap->n_eq == 0)  in normalize_divs()
986 		return bmap;  in normalize_divs()
988 	if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS))  in normalize_divs()
989 		return bmap;  in normalize_divs()
991 	v_div = isl_basic_map_var_offset(bmap, isl_dim_div);  in normalize_divs()
992 	div_eq = n_pure_div_eq(bmap);  in normalize_divs()
994 		return isl_basic_map_free(bmap);  in normalize_divs()
996 		return bmap;  in normalize_divs()
998 	if (div_eq < bmap->n_eq) {  in normalize_divs()
999 		B = isl_mat_sub_alloc6(bmap->ctx, bmap->eq, div_eq,  in normalize_divs()
1000 					bmap->n_eq - div_eq, 0, 1 + v_div);  in normalize_divs()
1005 			bmap = isl_basic_map_set_to_empty(bmap);  in normalize_divs()
1012 	d = isl_vec_alloc(bmap->ctx, div_eq);  in normalize_divs()
1015 	for (i = 0, j = bmap->n_div-1; i < div_eq; ++i) {  in normalize_divs()
1016 		while (j >= 0 && isl_int_is_zero(bmap->eq[i][1 + v_div + j]))  in normalize_divs()
1018 		isl_int_set(d->block.data[i], bmap->eq[i][1 + v_div + j]);  in normalize_divs()
1020 	B = isl_mat_sub_alloc6(bmap->ctx, bmap->eq, 0, div_eq, 0, 1 + v_div);  in normalize_divs()
1031 		bmap = isl_basic_map_set_to_empty(bmap);  in normalize_divs()
1044 	pos = isl_alloc_array(bmap->ctx, int, T->n_row);  in normalize_divs()
1049 	for (j = bmap->n_div - 1; j >= 0; --j) {  in normalize_divs()
1050 		for (i = 0; i < bmap->n_eq; ++i)  in normalize_divs()
1051 			if (!isl_int_is_zero(bmap->eq[i][1 + v_div + j]))  in normalize_divs()
1053 		if (i < bmap->n_eq) {  in normalize_divs()
1054 			bmap = isl_basic_map_drop_div(bmap, j);  in normalize_divs()
1055 			if (isl_basic_map_drop_equality(bmap, i) < 0)  in normalize_divs()
1069 		bmap = isl_basic_map_extend(bmap, needed, needed, 0);  in normalize_divs()
1070 		if (!bmap)  in normalize_divs()
1076 		k = isl_basic_map_alloc_div(bmap);  in normalize_divs()
1078 		isl_seq_clr(bmap->div[k] + 1, 1 + v_div + bmap->n_div);  in normalize_divs()
1079 		isl_int_set(bmap->div[k][0], T->row[i][i]);  in normalize_divs()
1081 			isl_seq_cpy(bmap->div[k] + 1, C2->row[i], 1 + v_div);  in normalize_divs()
1083 			isl_int_set_si(bmap->div[k][1 + i], 1);  in normalize_divs()
1088 				isl_seq_submul(bmap->div[k] + 1, T->row[i][j],  in normalize_divs()
1091 				isl_int_neg(bmap->div[k][1 + pos[j]],  in normalize_divs()
1094 		j = isl_basic_map_alloc_equality(bmap);  in normalize_divs()
1095 		isl_seq_neg(bmap->eq[j], bmap->div[k]+1, 1+v_div+bmap->n_div);  in normalize_divs()
1096 		isl_int_set(bmap->eq[j][pos[i]], bmap->div[k][0]);  in normalize_divs()
1105 	ISL_F_SET(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);  in normalize_divs()
1107 	return bmap;  in normalize_divs()
1113 	isl_basic_map_free(bmap);  in normalize_divs()
1118 	__isl_take isl_basic_map *bmap, int div, int ineq)  in set_div_from_lower_bound()  argument
1120 	unsigned total = isl_basic_map_offset(bmap, isl_dim_div);  in set_div_from_lower_bound()
1122 	isl_seq_neg(bmap->div[div] + 1, bmap->ineq[ineq], total + bmap->n_div);  in set_div_from_lower_bound()
1123 	isl_int_set(bmap->div[div][0], bmap->ineq[ineq][total + div]);  in set_div_from_lower_bound()
1124 	isl_int_add(bmap->div[div][1], bmap->div[div][1], bmap->div[div][0]);  in set_div_from_lower_bound()
1125 	isl_int_sub_ui(bmap->div[div][1], bmap->div[div][1], 1);  in set_div_from_lower_bound()
1126 	isl_int_set_si(bmap->div[div][1 + total + div], 0);  in set_div_from_lower_bound()
1128 	return bmap;  in set_div_from_lower_bound()
1137 static isl_bool ok_to_set_div_from_bound(__isl_keep isl_basic_map *bmap,  in ok_to_set_div_from_bound()  argument
1141 	unsigned total = isl_basic_map_offset(bmap, isl_dim_div);  in ok_to_set_div_from_bound()
1144 	for (j = 0; j < bmap->n_div; ++j) {  in ok_to_set_div_from_bound()
1147 		if (isl_int_is_zero(bmap->ineq[ineq][total + j]))  in ok_to_set_div_from_bound()
1149 		if (isl_int_is_zero(bmap->div[j][0]))  in ok_to_set_div_from_bound()
1154 	for (j = 0; j < bmap->n_div; ++j) {  in ok_to_set_div_from_bound()
1157 		if (isl_int_is_zero(bmap->div[j][0]))  in ok_to_set_div_from_bound()
1159 		if (!isl_int_is_zero(bmap->div[j][1 + total + div]))  in ok_to_set_div_from_bound()
1174 static isl_bool better_div_constraint(__isl_keep isl_basic_map *bmap,  in better_div_constraint()  argument
1177 	unsigned total = isl_basic_map_offset(bmap, isl_dim_div);  in better_div_constraint()
1181 	if (isl_int_is_zero(bmap->div[div][0]))  in better_div_constraint()
1184 	if (isl_seq_last_non_zero(bmap->ineq[ineq] + total + div + 1,  in better_div_constraint()
1185 				  bmap->n_div - (div + 1)) >= 0)  in better_div_constraint()
1188 	last_ineq = isl_seq_last_non_zero(bmap->ineq[ineq], total + div);  in better_div_constraint()
1189 	last_div = isl_seq_last_non_zero(bmap->div[div] + 1,  in better_div_constraint()
1190 					 total + bmap->n_div);  in better_div_constraint()
1208 	__isl_take isl_basic_map *bmap, int k, int l, isl_int sum,  in check_for_div_constraints()  argument
1212 	unsigned total = isl_basic_map_offset(bmap, isl_dim_div);  in check_for_div_constraints()
1214 	for (i = 0; i < bmap->n_div; ++i) {  in check_for_div_constraints()
1217 		if (isl_int_is_zero(bmap->ineq[k][total + i]))  in check_for_div_constraints()
1219 		if (isl_int_abs_ge(sum, bmap->ineq[k][total + i]))  in check_for_div_constraints()
1221 		set_div = better_div_constraint(bmap, i, k);  in check_for_div_constraints()
1223 			set_div = ok_to_set_div_from_bound(bmap, i, k);  in check_for_div_constraints()
1225 			return isl_basic_map_free(bmap);  in check_for_div_constraints()
1228 		if (isl_int_is_pos(bmap->ineq[k][total + i]))  in check_for_div_constraints()
1229 			bmap = set_div_from_lower_bound(bmap, i, k);  in check_for_div_constraints()
1231 			bmap = set_div_from_lower_bound(bmap, i, l);  in check_for_div_constraints()
1236 	return bmap;  in check_for_div_constraints()
1240 	__isl_take isl_basic_map *bmap, int *progress, int detect_divs)  in isl_basic_map_remove_duplicate_constraints()  argument
1244 	isl_size total = isl_basic_map_dim(bmap, isl_dim_all);  in isl_basic_map_remove_duplicate_constraints()
1247 	if (total < 0 || bmap->n_ineq <= 1)  in isl_basic_map_remove_duplicate_constraints()
1248 		return bmap;  in isl_basic_map_remove_duplicate_constraints()
1250 	if (create_constraint_index(&ci, bmap) < 0)  in isl_basic_map_remove_duplicate_constraints()
1251 		return bmap;  in isl_basic_map_remove_duplicate_constraints()
1253 	h = isl_seq_get_hash_bits(bmap->ineq[0] + 1, total, ci.bits);  in isl_basic_map_remove_duplicate_constraints()
1254 	ci.index[h] = &bmap->ineq[0];  in isl_basic_map_remove_duplicate_constraints()
1255 	for (k = 1; k < bmap->n_ineq; ++k) {  in isl_basic_map_remove_duplicate_constraints()
1256 		h = hash_index(&ci, bmap, k);  in isl_basic_map_remove_duplicate_constraints()
1258 			ci.index[h] = &bmap->ineq[k];  in isl_basic_map_remove_duplicate_constraints()
1263 		l = ci.index[h] - &bmap->ineq[0];  in isl_basic_map_remove_duplicate_constraints()
1264 		if (isl_int_lt(bmap->ineq[k][0], bmap->ineq[l][0]))  in isl_basic_map_remove_duplicate_constraints()
1265 			swap_inequality(bmap, k, l);  in isl_basic_map_remove_duplicate_constraints()
1266 		isl_basic_map_drop_inequality(bmap, k);  in isl_basic_map_remove_duplicate_constraints()
1270 	for (k = 0; bmap && k < bmap->n_ineq-1; ++k) {  in isl_basic_map_remove_duplicate_constraints()
1271 		isl_seq_neg(bmap->ineq[k]+1, bmap->ineq[k]+1, total);  in isl_basic_map_remove_duplicate_constraints()
1272 		h = hash_index(&ci, bmap, k);  in isl_basic_map_remove_duplicate_constraints()
1273 		isl_seq_neg(bmap->ineq[k]+1, bmap->ineq[k]+1, total);  in isl_basic_map_remove_duplicate_constraints()
1276 		l = ci.index[h] - &bmap->ineq[0];  in isl_basic_map_remove_duplicate_constraints()
1277 		isl_int_add(sum, bmap->ineq[k][0], bmap->ineq[l][0]);  in isl_basic_map_remove_duplicate_constraints()
1280 				bmap = check_for_div_constraints(bmap, k, l,  in isl_basic_map_remove_duplicate_constraints()
1292 			isl_basic_map_drop_inequality(bmap, l);  in isl_basic_map_remove_duplicate_constraints()
1293 			isl_basic_map_inequality_to_equality(bmap, k);  in isl_basic_map_remove_duplicate_constraints()
1295 			bmap = isl_basic_map_set_to_empty(bmap);  in isl_basic_map_remove_duplicate_constraints()
1301 	return bmap;  in isl_basic_map_remove_duplicate_constraints()
1310 	__isl_take isl_basic_map *bmap, int *progress)  in isl_basic_map_detect_inequality_pairs()  argument
1316 		bmap = isl_basic_map_remove_duplicate_constraints(bmap,  in isl_basic_map_detect_inequality_pairs()
1322 	return bmap;  in isl_basic_map_detect_inequality_pairs()
1361 	__isl_take isl_basic_map *bmap, int div, int *progress)  in eliminate_unit_div()  argument
1367 	v_div = isl_basic_map_var_offset(bmap, isl_dim_div);  in eliminate_unit_div()
1368 	dim = isl_basic_map_dim(bmap, isl_dim_all);  in eliminate_unit_div()
1370 		return isl_basic_map_free(bmap);  in eliminate_unit_div()
1372 	ctx = isl_basic_map_get_ctx(bmap);  in eliminate_unit_div()
1374 	for (j = 0; j < bmap->n_ineq; ++j) {  in eliminate_unit_div()
1377 		if (!isl_int_is_one(bmap->ineq[j][1 + v_div + div]) &&  in eliminate_unit_div()
1378 		    !isl_int_is_negone(bmap->ineq[j][1 + v_div + div]))  in eliminate_unit_div()
1384 		s = isl_int_sgn(bmap->ineq[j][1 + v_div + div]);  in eliminate_unit_div()
1385 		isl_int_set_si(bmap->ineq[j][1 + v_div + div], 0);  in eliminate_unit_div()
1387 			isl_seq_combine(bmap->ineq[j],  in eliminate_unit_div()
1388 				ctx->negone, bmap->div[div] + 1,  in eliminate_unit_div()
1389 				bmap->div[div][0], bmap->ineq[j], 1 + dim);  in eliminate_unit_div()
1391 			isl_seq_combine(bmap->ineq[j],  in eliminate_unit_div()
1392 				ctx->one, bmap->div[div] + 1,  in eliminate_unit_div()
1393 				bmap->div[div][0], bmap->ineq[j], 1 + dim);  in eliminate_unit_div()
1395 			isl_int_add(bmap->ineq[j][0],  in eliminate_unit_div()
1396 				bmap->ineq[j][0], bmap->div[div][0]);  in eliminate_unit_div()
1397 			isl_int_sub_ui(bmap->ineq[j][0],  in eliminate_unit_div()
1398 				bmap->ineq[j][0], 1);  in eliminate_unit_div()
1401 		bmap = isl_basic_map_extend_constraints(bmap, 0, 1);  in eliminate_unit_div()
1402 		bmap = isl_basic_map_add_div_constraint(bmap, div, s);  in eliminate_unit_div()
1403 		if (!bmap)  in eliminate_unit_div()
1407 	return bmap;  in eliminate_unit_div()
1423 	__isl_take isl_basic_map *bmap,  in eliminate_selected_unit_divs()  argument
1424 	isl_bool (*select)(__isl_keep isl_basic_map *bmap, int div),  in eliminate_selected_unit_divs()  argument
1429 	if (!bmap)  in eliminate_selected_unit_divs()
1432 	for (i = 0; i < bmap->n_div; ++i) {  in eliminate_selected_unit_divs()
1435 		if (isl_int_is_zero(bmap->div[i][0]))  in eliminate_selected_unit_divs()
1437 		if (isl_int_is_one(bmap->div[i][0]))  in eliminate_selected_unit_divs()
1439 		selected = select(bmap, i);  in eliminate_selected_unit_divs()
1441 			return isl_basic_map_free(bmap);  in eliminate_selected_unit_divs()
1444 		bmap = eliminate_unit_div(bmap, i, progress);  in eliminate_selected_unit_divs()
1445 		if (!bmap)  in eliminate_selected_unit_divs()
1449 	return bmap;  in eliminate_selected_unit_divs()
1455 static isl_bool is_any_div(__isl_keep isl_basic_map *bmap, int div)  in is_any_div()  argument
1466 	__isl_take isl_basic_map *bmap, int *progress)  in eliminate_unit_divs()  argument
1468 	return eliminate_selected_unit_divs(bmap, &is_any_div, progress);  in eliminate_unit_divs()
1476 static isl_bool is_pure_unit_div(__isl_keep isl_basic_map *bmap, int div)  in is_pure_unit_div()  argument
1481 	v_div = isl_basic_map_var_offset(bmap, isl_dim_div);  in is_pure_unit_div()
1482 	n_ineq = isl_basic_map_n_inequality(bmap);  in is_pure_unit_div()
1489 		if (isl_int_is_zero(bmap->ineq[i][1 + v_div + div]))  in is_pure_unit_div()
1491 		skip = isl_basic_map_is_div_constraint(bmap,  in is_pure_unit_div()
1492 							bmap->ineq[i], div);  in is_pure_unit_div()
1497 		if (!isl_int_is_one(bmap->ineq[i][1 + v_div + div]) &&  in is_pure_unit_div()
1498 		    !isl_int_is_negone(bmap->ineq[i][1 + v_div + div]))  in is_pure_unit_div()
1511 	__isl_take isl_basic_map *bmap)  in isl_basic_map_eliminate_pure_unit_divs()  argument
1513 	return eliminate_selected_unit_divs(bmap, &is_pure_unit_div, NULL);  in isl_basic_map_eliminate_pure_unit_divs()
1516 __isl_give isl_basic_map *isl_basic_map_simplify(__isl_take isl_basic_map *bmap)  in isl_basic_map_simplify()  argument
1519 	if (!bmap)  in isl_basic_map_simplify()
1525 		empty = isl_basic_map_plain_is_empty(bmap);  in isl_basic_map_simplify()
1527 			return isl_basic_map_free(bmap);  in isl_basic_map_simplify()
1530 		bmap = isl_basic_map_normalize_constraints(bmap);  in isl_basic_map_simplify()
1531 		bmap = reduce_div_coefficients(bmap);  in isl_basic_map_simplify()
1532 		bmap = normalize_div_expressions(bmap);  in isl_basic_map_simplify()
1533 		bmap = remove_duplicate_divs(bmap, &progress);  in isl_basic_map_simplify()
1534 		bmap = eliminate_unit_divs(bmap, &progress);  in isl_basic_map_simplify()
1535 		bmap = eliminate_divs_eq(bmap, &progress);  in isl_basic_map_simplify()
1536 		bmap = eliminate_divs_ineq(bmap, &progress);  in isl_basic_map_simplify()
1537 		bmap = isl_basic_map_gauss(bmap, &progress);  in isl_basic_map_simplify()
1539 		bmap = normalize_divs(bmap, &progress);  in isl_basic_map_simplify()
1540 		bmap = isl_basic_map_remove_duplicate_constraints(bmap,  in isl_basic_map_simplify()
1542 		if (bmap && progress)  in isl_basic_map_simplify()
1543 			ISL_F_CLR(bmap, ISL_BASIC_MAP_REDUCED_COEFFICIENTS);  in isl_basic_map_simplify()
1545 	return bmap;  in isl_basic_map_simplify()
1555 isl_bool isl_basic_map_is_div_constraint(__isl_keep isl_basic_map *bmap,  in isl_basic_map_is_div_constraint()  argument
1560 	if (!bmap)  in isl_basic_map_is_div_constraint()
1563 	pos = isl_basic_map_offset(bmap, isl_dim_div) + div;  in isl_basic_map_is_div_constraint()
1565 	if (isl_int_eq(constraint[pos], bmap->div[div][0])) {  in isl_basic_map_is_div_constraint()
1567 		isl_int_sub(bmap->div[div][1],  in isl_basic_map_is_div_constraint()
1568 				bmap->div[div][1], bmap->div[div][0]);  in isl_basic_map_is_div_constraint()
1569 		isl_int_add_ui(bmap->div[div][1], bmap->div[div][1], 1);  in isl_basic_map_is_div_constraint()
1570 		neg = isl_seq_is_neg(constraint, bmap->div[div]+1, pos);  in isl_basic_map_is_div_constraint()
1571 		isl_int_sub_ui(bmap->div[div][1], bmap->div[div][1], 1);  in isl_basic_map_is_div_constraint()
1572 		isl_int_add(bmap->div[div][1],  in isl_basic_map_is_div_constraint()
1573 				bmap->div[div][1], bmap->div[div][0]);  in isl_basic_map_is_div_constraint()
1577 					    bmap->n_div-div-1) != -1)  in isl_basic_map_is_div_constraint()
1579 	} else if (isl_int_abs_eq(constraint[pos], bmap->div[div][0])) {  in isl_basic_map_is_div_constraint()
1580 		if (!isl_seq_eq(constraint, bmap->div[div]+1, pos))  in isl_basic_map_is_div_constraint()
1583 					    bmap->n_div-div-1) != -1)  in isl_basic_map_is_div_constraint()
1599 static isl_bool div_is_redundant(__isl_keep isl_basic_map *bmap, int div)  in div_is_redundant()  argument
1602 	isl_size v_div = isl_basic_map_var_offset(bmap, isl_dim_div);  in div_is_redundant()
1608 	for (i = 0; i < bmap->n_eq; ++i)  in div_is_redundant()
1609 		if (!isl_int_is_zero(bmap->eq[i][pos]))  in div_is_redundant()
1612 	for (i = 0; i < bmap->n_ineq; ++i) {  in div_is_redundant()
1615 		if (isl_int_is_zero(bmap->ineq[i][pos]))  in div_is_redundant()
1617 		red = isl_basic_map_is_div_constraint(bmap, bmap->ineq[i], div);  in div_is_redundant()
1622 	for (i = 0; i < bmap->n_div; ++i) {  in div_is_redundant()
1623 		if (isl_int_is_zero(bmap->div[i][0]))  in div_is_redundant()
1625 		if (!isl_int_is_zero(bmap->div[i][1+pos]))  in div_is_redundant()
1639 	__isl_take isl_basic_map *bmap)  in remove_redundant_divs()  argument
1644 	v_div = isl_basic_map_var_offset(bmap, isl_dim_div);  in remove_redundant_divs()
1646 		return isl_basic_map_free(bmap);  in remove_redundant_divs()
1648 	for (i = bmap->n_div-1; i >= 0; --i) {  in remove_redundant_divs()
1651 		redundant = div_is_redundant(bmap, i);  in remove_redundant_divs()
1653 			return isl_basic_map_free(bmap);  in remove_redundant_divs()
1656 		bmap = isl_basic_map_drop_constraints_involving(bmap,  in remove_redundant_divs()
1658 		bmap = isl_basic_map_drop_div(bmap, i);  in remove_redundant_divs()
1660 	return bmap;  in remove_redundant_divs()
1668 	__isl_take isl_basic_map *bmap)  in isl_basic_map_mark_final()  argument
1670 	if (!bmap)  in isl_basic_map_mark_final()
1672 	ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);  in isl_basic_map_mark_final()
1673 	return bmap;  in isl_basic_map_mark_final()
1678 __isl_give isl_basic_map *isl_basic_map_finalize(__isl_take isl_basic_map *bmap)  in isl_basic_map_finalize()  argument
1680 	bmap = remove_redundant_divs(bmap);  in isl_basic_map_finalize()
1681 	bmap = isl_basic_map_mark_final(bmap);  in isl_basic_map_finalize()
1682 	return bmap;  in isl_basic_map_finalize()
1696 	__isl_take isl_basic_map *bmap, int pos)  in remove_dependent_vars()  argument
1700 	if (!bmap)  in remove_dependent_vars()
1703 	for (i = 0; i < bmap->n_div; ++i) {  in remove_dependent_vars()
1704 		if (isl_int_is_zero(bmap->div[i][0]))  in remove_dependent_vars()
1706 		if (isl_int_is_zero(bmap->div[i][1+1+pos]))  in remove_dependent_vars()
1708 		bmap = isl_basic_map_mark_div_unknown(bmap, i);  in remove_dependent_vars()
1709 		if (!bmap)  in remove_dependent_vars()
1712 	return bmap;  in remove_dependent_vars()
1719 	__isl_take isl_basic_map *bmap, unsigned pos, unsigned n)  in isl_basic_map_eliminate_vars()  argument
1727 		return bmap;  in isl_basic_map_eliminate_vars()
1728 	total = isl_basic_map_dim(bmap, isl_dim_all);  in isl_basic_map_eliminate_vars()
1730 		return isl_basic_map_free(bmap);  in isl_basic_map_eliminate_vars()
1732 	bmap = isl_basic_map_cow(bmap);  in isl_basic_map_eliminate_vars()
1734 		bmap = remove_dependent_vars(bmap, d);  in isl_basic_map_eliminate_vars()
1735 	if (!bmap)  in isl_basic_map_eliminate_vars()
1739 	     d >= 0 && d >= total - bmap->n_div && d >= pos; --d)  in isl_basic_map_eliminate_vars()
1740 		isl_seq_clr(bmap->div[d-(total-bmap->n_div)], 2+total);  in isl_basic_map_eliminate_vars()
1743 		if (!bmap)  in isl_basic_map_eliminate_vars()
1745 		for (i = 0; i < bmap->n_eq; ++i) {  in isl_basic_map_eliminate_vars()
1746 			if (isl_int_is_zero(bmap->eq[i][1+d]))  in isl_basic_map_eliminate_vars()
1748 			bmap = eliminate_var_using_equality(bmap, d,  in isl_basic_map_eliminate_vars()
1749 							bmap->eq[i], 0, NULL);  in isl_basic_map_eliminate_vars()
1750 			if (isl_basic_map_drop_equality(bmap, i) < 0)  in isl_basic_map_eliminate_vars()
1751 				return isl_basic_map_free(bmap);  in isl_basic_map_eliminate_vars()
1755 		if (i < bmap->n_eq)  in isl_basic_map_eliminate_vars()
1759 		for (i = 0; i < bmap->n_ineq; ++i) {  in isl_basic_map_eliminate_vars()
1760 			if (isl_int_is_pos(bmap->ineq[i][1+d]))  in isl_basic_map_eliminate_vars()
1762 			else if (isl_int_is_neg(bmap->ineq[i][1+d]))  in isl_basic_map_eliminate_vars()
1765 		bmap = isl_basic_map_extend_constraints(bmap,  in isl_basic_map_eliminate_vars()
1767 		if (!bmap)  in isl_basic_map_eliminate_vars()
1769 		for (i = bmap->n_ineq - 1; i >= 0; --i) {  in isl_basic_map_eliminate_vars()
1771 			if (isl_int_is_zero(bmap->ineq[i][1+d]))  in isl_basic_map_eliminate_vars()
1775 				if (isl_int_is_zero(bmap->ineq[j][1+d]))  in isl_basic_map_eliminate_vars()
1778 				if (isl_int_sgn(bmap->ineq[i][1+d]) ==  in isl_basic_map_eliminate_vars()
1779 				    isl_int_sgn(bmap->ineq[j][1+d]))  in isl_basic_map_eliminate_vars()
1781 				k = isl_basic_map_alloc_inequality(bmap);  in isl_basic_map_eliminate_vars()
1784 				isl_seq_cpy(bmap->ineq[k], bmap->ineq[i],  in isl_basic_map_eliminate_vars()
1786 				isl_seq_elim(bmap->ineq[k], bmap->ineq[j],  in isl_basic_map_eliminate_vars()
1789 			isl_basic_map_drop_inequality(bmap, i);  in isl_basic_map_eliminate_vars()
1793 			bmap = isl_basic_map_normalize_constraints(bmap);  in isl_basic_map_eliminate_vars()
1794 			bmap = isl_basic_map_remove_duplicate_constraints(bmap,  in isl_basic_map_eliminate_vars()
1796 			bmap = isl_basic_map_gauss(bmap, NULL);  in isl_basic_map_eliminate_vars()
1797 			bmap = isl_basic_map_remove_redundancies(bmap);  in isl_basic_map_eliminate_vars()
1799 			if (!bmap)  in isl_basic_map_eliminate_vars()
1801 			if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))  in isl_basic_map_eliminate_vars()
1806 		bmap = isl_basic_map_gauss(bmap, NULL);  in isl_basic_map_eliminate_vars()
1807 	return bmap;  in isl_basic_map_eliminate_vars()
1809 	isl_basic_map_free(bmap);  in isl_basic_map_eliminate_vars()
1826 	__isl_take isl_basic_map *bmap,  in isl_basic_map_eliminate()  argument
1831 	if (!bmap)  in isl_basic_map_eliminate()
1834 		return bmap;  in isl_basic_map_eliminate()
1836 	if (isl_basic_map_check_range(bmap, type, first, n) < 0)  in isl_basic_map_eliminate()
1837 		return isl_basic_map_free(bmap);  in isl_basic_map_eliminate()
1839 	if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {  in isl_basic_map_eliminate()
1840 		first += isl_basic_map_offset(bmap, type) - 1;  in isl_basic_map_eliminate()
1841 		bmap = isl_basic_map_eliminate_vars(bmap, first, n);  in isl_basic_map_eliminate()
1842 		return isl_basic_map_finalize(bmap);  in isl_basic_map_eliminate()
1845 	space = isl_basic_map_get_space(bmap);  in isl_basic_map_eliminate()
1846 	bmap = isl_basic_map_project_out(bmap, type, first, n);  in isl_basic_map_eliminate()
1847 	bmap = isl_basic_map_insert_dims(bmap, type, first, n);  in isl_basic_map_eliminate()
1848 	bmap = isl_basic_map_reset_space(bmap, space);  in isl_basic_map_eliminate()
1849 	return bmap;  in isl_basic_map_eliminate()
1871 	__isl_take isl_basic_map *bmap)  in isl_basic_map_drop_constraints_involving_unknown_divs()  argument
1877 	known = isl_basic_map_divs_known(bmap);  in isl_basic_map_drop_constraints_involving_unknown_divs()
1879 		return isl_basic_map_free(bmap);  in isl_basic_map_drop_constraints_involving_unknown_divs()
1881 		return bmap;  in isl_basic_map_drop_constraints_involving_unknown_divs()
1883 	n_div = isl_basic_map_dim(bmap, isl_dim_div);  in isl_basic_map_drop_constraints_involving_unknown_divs()
1885 		return isl_basic_map_free(bmap);  in isl_basic_map_drop_constraints_involving_unknown_divs()
1886 	o_div = isl_basic_map_offset(bmap, isl_dim_div) - 1;  in isl_basic_map_drop_constraints_involving_unknown_divs()
1889 		known = isl_basic_map_div_is_known(bmap, i);  in isl_basic_map_drop_constraints_involving_unknown_divs()
1891 			return isl_basic_map_free(bmap);  in isl_basic_map_drop_constraints_involving_unknown_divs()
1894 		bmap = remove_dependent_vars(bmap, o_div + i);  in isl_basic_map_drop_constraints_involving_unknown_divs()
1895 		bmap = isl_basic_map_drop_constraints_involving_dims(bmap,  in isl_basic_map_drop_constraints_involving_unknown_divs()
1897 		n_div = isl_basic_map_dim(bmap, isl_dim_div);  in isl_basic_map_drop_constraints_involving_unknown_divs()
1899 			return isl_basic_map_free(bmap);  in isl_basic_map_drop_constraints_involving_unknown_divs()
1903 	return bmap;  in isl_basic_map_drop_constraints_involving_unknown_divs()
1912 	isl_basic_map *bmap;  in isl_basic_set_drop_constraints_involving_unknown_divs()  local
1914 	bmap = bset_to_bmap(bset);  in isl_basic_set_drop_constraints_involving_unknown_divs()
1915 	bmap = isl_basic_map_drop_constraints_involving_unknown_divs(bmap);  in isl_basic_set_drop_constraints_involving_unknown_divs()
1916 	return bset_from_bmap(bmap);  in isl_basic_set_drop_constraints_involving_unknown_divs()
1958 static void compute_elimination_index(__isl_keep isl_basic_map *bmap, int *elim,  in compute_elimination_index()  argument
1965 	for (i = 0; i < bmap->n_eq; ++i) {  in compute_elimination_index()
1967 			if (isl_int_is_zero(bmap->eq[i][1+d]))  in compute_elimination_index()
1982 	__isl_keep isl_basic_map *bmap, int *elim, unsigned total)  in reduced_using_equalities()  argument
1996 		isl_seq_elim(dst, bmap->eq[elim[d]], 1 + d, 1 + total, NULL);  in reduced_using_equalities()
2140 	__isl_take isl_basic_map *bmap, __isl_take isl_basic_map *context)  in isl_basic_map_remove_shifted_constraints()  argument
2144 	if (!bmap || !context)  in isl_basic_map_remove_shifted_constraints()
2147 	if (bmap->n_ineq == 0 || context->n_ineq == 0) {  in isl_basic_map_remove_shifted_constraints()
2149 		return bmap;  in isl_basic_map_remove_shifted_constraints()
2152 	bmap = isl_basic_map_order_divs(bmap);  in isl_basic_map_remove_shifted_constraints()
2153 	context = isl_basic_map_align_divs(context, bmap);  in isl_basic_map_remove_shifted_constraints()
2154 	bmap = isl_basic_map_align_divs(bmap, context);  in isl_basic_map_remove_shifted_constraints()
2156 	bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));  in isl_basic_map_remove_shifted_constraints()
2161 	bmap = isl_basic_map_overlying_set(bset, bmap);  in isl_basic_map_remove_shifted_constraints()
2163 	return bmap;  in isl_basic_map_remove_shifted_constraints()
2165 	isl_basic_map_free(bmap);  in isl_basic_map_remove_shifted_constraints()
2191 	__isl_take isl_basic_map *bmap, int *relevant)  in drop_unrelated_constraints()  argument
2196 	dim = isl_basic_map_dim(bmap, isl_dim_all);  in drop_unrelated_constraints()
2198 		return isl_basic_map_free(bmap);  in drop_unrelated_constraints()
2203 		return bmap;  in drop_unrelated_constraints()
2205 	for (i = bmap->n_eq - 1; i >= 0; --i)  in drop_unrelated_constraints()
2206 		if (!is_related(bmap->eq[i] + 1, dim, relevant)) {  in drop_unrelated_constraints()
2207 			bmap = isl_basic_map_cow(bmap);  in drop_unrelated_constraints()
2208 			if (isl_basic_map_drop_equality(bmap, i) < 0)  in drop_unrelated_constraints()
2209 				return isl_basic_map_free(bmap);  in drop_unrelated_constraints()
2212 	for (i = bmap->n_ineq - 1; i >= 0; --i)  in drop_unrelated_constraints()
2213 		if (!is_related(bmap->ineq[i] + 1, dim, relevant)) {  in drop_unrelated_constraints()
2214 			bmap = isl_basic_map_cow(bmap);  in drop_unrelated_constraints()
2215 			if (isl_basic_map_drop_inequality(bmap, i) < 0)  in drop_unrelated_constraints()
2216 				return isl_basic_map_free(bmap);  in drop_unrelated_constraints()
2219 	return bmap;  in drop_unrelated_constraints()
2291 	__isl_take isl_basic_map *bmap, __isl_take int *group)  in isl_basic_map_drop_unrelated_constraints()  argument
2297 	dim = isl_basic_map_dim(bmap, isl_dim_all);  in isl_basic_map_drop_unrelated_constraints()
2299 		return isl_basic_map_free(bmap);  in isl_basic_map_drop_unrelated_constraints()
2307 		return bmap;  in isl_basic_map_drop_unrelated_constraints()
2310 	for (i = 0; i < bmap->n_eq; ++i)  in isl_basic_map_drop_unrelated_constraints()
2311 		update_groups(dim, group, bmap->eq[i] + 1);  in isl_basic_map_drop_unrelated_constraints()
2312 	for (i = 0; i < bmap->n_ineq; ++i)  in isl_basic_map_drop_unrelated_constraints()
2313 		update_groups(dim, group, bmap->ineq[i] + 1);  in isl_basic_map_drop_unrelated_constraints()
2322 	bmap = drop_unrelated_constraints(bmap, group);  in isl_basic_map_drop_unrelated_constraints()
2325 	return bmap;  in isl_basic_map_drop_unrelated_constraints()
2873 static int n_div_eq(__isl_keep isl_basic_map *bmap)  in n_div_eq()  argument
2878 	if (!bmap)  in n_div_eq()
2881 	if (bmap->n_eq == 0)  in n_div_eq()
2884 	total = isl_basic_map_dim(bmap, isl_dim_all);  in n_div_eq()
2885 	n_div = isl_basic_map_dim(bmap, isl_dim_div);  in n_div_eq()
2890 	for (i = 0; i < bmap->n_eq; ++i)  in n_div_eq()
2891 		if (isl_seq_first_non_zero(bmap->eq[i] + 1 + total,  in n_div_eq()
2895 	return bmap->n_eq;  in n_div_eq()
2906 	isl_basic_map *bmap = NULL;  in basic_map_from_equalities()  local
2916 	bmap = isl_basic_map_alloc_space(isl_space_copy(space),  in basic_map_from_equalities()
2919 		k = isl_basic_map_alloc_equality(bmap);  in basic_map_from_equalities()
2922 		isl_seq_cpy(bmap->eq[k], eq->row[i], eq->n_col);  in basic_map_from_equalities()
2927 	return bmap;  in basic_map_from_equalities()
2931 	isl_basic_map_free(bmap);  in basic_map_from_equalities()
2961 	isl_basic_map *bmap;  in combined_variable_compression()  local
2979 	bmap = basic_map_from_equalities(isl_basic_map_get_space(bmap1), E1);  in combined_variable_compression()
2980 	bmap = isl_basic_map_gauss(bmap, NULL);  in combined_variable_compression()
2981 	if (!bmap)  in combined_variable_compression()
2983 	E1 = isl_mat_sub_alloc6(ctx, bmap->eq, 0, bmap->n_eq, 0, 1 + total);  in combined_variable_compression()
2985 	isl_basic_map_free(bmap);  in combined_variable_compression()
3023 	__isl_keep isl_basic_map *bmap, int bmap_n_eq,  in extract_compressed_stride_constraints()  argument
3036 	ctx = isl_basic_map_get_ctx(bmap);  in extract_compressed_stride_constraints()
3038 	V = combined_variable_compression(bmap, bmap_n_eq,  in extract_compressed_stride_constraints()
3048 	n_div = isl_basic_map_dim(bmap, isl_dim_div);  in extract_compressed_stride_constraints()
3054 	A = isl_mat_sub_alloc6(ctx, bmap->eq,  in extract_compressed_stride_constraints()
3154 	__isl_take isl_basic_map *bmap, int n, __isl_keep isl_mat *A)  in reduce_stride_constraints()  argument
3161 	total = isl_basic_map_dim(bmap, isl_dim_all);  in reduce_stride_constraints()
3162 	n_div = isl_basic_map_dim(bmap, isl_dim_div);  in reduce_stride_constraints()
3164 		return isl_basic_map_free(bmap);  in reduce_stride_constraints()
3171 		div = isl_seq_first_non_zero(bmap->eq[i] + 1 + total, n_div);  in reduce_stride_constraints()
3173 			isl_die(isl_basic_map_get_ctx(bmap), isl_error_internal,  in reduce_stride_constraints()
3176 		if (isl_seq_first_non_zero(bmap->eq[i] + 1 + total + div + 1,  in reduce_stride_constraints()
3183 		remove_incomplete_powers(&gcd, bmap->eq[i][1 + total + div]);  in reduce_stride_constraints()
3186 		isl_int_divexact(bmap->eq[i][1 + total + div],  in reduce_stride_constraints()
3187 				bmap->eq[i][1 + total + div], gcd);  in reduce_stride_constraints()
3188 		bmap = isl_basic_map_mark_div_unknown(bmap, div);  in reduce_stride_constraints()
3189 		if (!bmap)  in reduce_stride_constraints()
3196 		bmap = isl_basic_map_gauss(bmap, NULL);  in reduce_stride_constraints()
3198 	return bmap;  in reduce_stride_constraints()
3201 	isl_basic_map_free(bmap);  in reduce_stride_constraints()
3214 static __isl_give isl_basic_map *gist_strides(__isl_take isl_basic_map *bmap,  in gist_strides()  argument
3220 	if (!bmap || !context)  in gist_strides()
3221 		return isl_basic_map_free(bmap);  in gist_strides()
3223 	bmap_n_eq = n_div_eq(bmap);  in gist_strides()
3227 		return isl_basic_map_free(bmap);  in gist_strides()
3229 		return bmap;  in gist_strides()
3231 	A = extract_compressed_stride_constraints(bmap, bmap_n_eq,  in gist_strides()
3233 	bmap = reduce_stride_constraints(bmap, bmap_n_eq, A);  in gist_strides()
3237 	return bmap;  in gist_strides()
3260 __isl_give isl_basic_map *isl_basic_map_gist(__isl_take isl_basic_map *bmap,  in isl_basic_map_gist()  argument
3268 	if (!bmap || !context)  in isl_basic_map_gist()
3271 	if (isl_basic_map_plain_is_universe(bmap)) {  in isl_basic_map_gist()
3273 		return bmap;  in isl_basic_map_gist()
3276 		isl_space *space = isl_basic_map_get_space(bmap);  in isl_basic_map_gist()
3277 		isl_basic_map_free(bmap);  in isl_basic_map_gist()
3281 	if (isl_basic_map_plain_is_empty(bmap)) {  in isl_basic_map_gist()
3283 		return bmap;  in isl_basic_map_gist()
3286 	bmap = isl_basic_map_remove_redundancies(bmap);  in isl_basic_map_gist()
3288 	bmap = isl_basic_map_order_divs(bmap);  in isl_basic_map_gist()
3289 	context = isl_basic_map_align_divs(context, bmap);  in isl_basic_map_gist()
3292 	total = isl_basic_map_dim(bmap, isl_dim_all);  in isl_basic_map_gist()
3293 	n_div_bmap = isl_basic_map_dim(bmap, isl_dim_div);  in isl_basic_map_gist()
3298 	bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));  in isl_basic_map_gist()
3307 		return isl_basic_map_overlying_set(bset, bmap);  in isl_basic_map_gist()
3317 	eq_bmap = isl_basic_map_overlying_set(eq, isl_basic_map_copy(bmap));  in isl_basic_map_gist()
3320 	bmap = isl_basic_map_overlying_set(bset, bmap);  in isl_basic_map_gist()
3321 	bmap = isl_basic_map_intersect(bmap, eq_bmap);  in isl_basic_map_gist()
3322 	bmap = isl_basic_map_remove_redundancies(bmap);  in isl_basic_map_gist()
3324 	return bmap;  in isl_basic_map_gist()
3326 	isl_basic_map_free(bmap);  in isl_basic_map_gist()
3391 	__isl_take isl_basic_map *bmap, __isl_keep isl_basic_map *context)  in drop_inequalities()  argument
3398 	bmap_total = isl_basic_map_dim(bmap, isl_dim_all);  in drop_inequalities()
3400 		return isl_basic_map_free(bmap);  in drop_inequalities()
3404 	i1 = bmap->n_ineq - 1;  in drop_inequalities()
3406 	while (bmap && i1 >= 0 && i2 >= 0) {  in drop_inequalities()
3409 		if (isl_seq_first_non_zero(bmap->ineq[i1] + 1 + total,  in drop_inequalities()
3414 		cmp = isl_basic_map_constraint_cmp(context, bmap->ineq[i1],  in drop_inequalities()
3424 		if (isl_int_eq(bmap->ineq[i1][0], context->ineq[i2][0])) {  in drop_inequalities()
3425 			bmap = isl_basic_map_cow(bmap);  in drop_inequalities()
3426 			if (isl_basic_map_drop_inequality(bmap, i1) < 0)  in drop_inequalities()
3427 				bmap = isl_basic_map_free(bmap);  in drop_inequalities()
3433 	return bmap;  in drop_inequalities()
3448 	__isl_take isl_basic_map *bmap, __isl_keep isl_basic_map *context)  in drop_equalities()  argument
3455 	bmap_total = isl_basic_map_dim(bmap, isl_dim_all);  in drop_equalities()
3457 		return isl_basic_map_free(bmap);  in drop_equalities()
3461 	i1 = bmap->n_eq - 1;  in drop_equalities()
3464 	while (bmap && i1 >= 0 && i2 >= 0) {  in drop_equalities()
3467 		if (isl_seq_first_non_zero(bmap->eq[i1] + 1 + total,  in drop_equalities()
3470 		last1 = isl_seq_last_non_zero(bmap->eq[i1] + 1, total);  in drop_equalities()
3480 		if (isl_seq_eq(bmap->eq[i1], context->eq[i2], 1 + total)) {  in drop_equalities()
3481 			bmap = isl_basic_map_cow(bmap);  in drop_equalities()
3482 			if (isl_basic_map_drop_equality(bmap, i1) < 0)  in drop_equalities()
3483 				bmap = isl_basic_map_free(bmap);  in drop_equalities()
3489 	return bmap;  in drop_equalities()
3501 	__isl_take isl_basic_map *bmap, __isl_take isl_basic_map *context)  in isl_basic_map_plain_gist()  argument
3507 		done = isl_basic_map_plain_is_universe(bmap);  in isl_basic_map_plain_gist()
3511 		done = isl_basic_map_plain_is_empty(bmap);  in isl_basic_map_plain_gist()
3516 		return bmap;  in isl_basic_map_plain_gist()
3522 		isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,  in isl_basic_map_plain_gist()
3526 	bmap = isl_basic_map_align_divs(bmap, context);  in isl_basic_map_plain_gist()
3527 	bmap = isl_basic_map_gauss(bmap, NULL);  in isl_basic_map_plain_gist()
3528 	bmap = isl_basic_map_sort_constraints(bmap);  in isl_basic_map_plain_gist()
3531 	bmap = drop_inequalities(bmap, context);  in isl_basic_map_plain_gist()
3532 	bmap = drop_equalities(bmap, context);  in isl_basic_map_plain_gist()
3535 	bmap = isl_basic_map_finalize(bmap);  in isl_basic_map_plain_gist()
3536 	return bmap;  in isl_basic_map_plain_gist()
3538 	isl_basic_map_free(bmap);  in isl_basic_map_plain_gist()
3548 	isl_basic_map *bmap;  in replace_by_disjunct()  local
3550 	bmap = isl_basic_map_copy(map->p[pos]);  in replace_by_disjunct()
3553 	return isl_map_from_basic_map(bmap);  in replace_by_disjunct()
3766 	__isl_take isl_basic_map *bmap, __isl_take isl_basic_set *context)  in isl_basic_map_gist_domain()  argument
3768 	isl_space *space = isl_basic_map_get_space(bmap);  in isl_basic_map_gist_domain()
3772 	return isl_basic_map_gist(bmap, bmap_context);  in isl_basic_map_gist_domain()
4100 static int is_opposite_part(__isl_keep isl_basic_map *bmap, int i, int j,  in is_opposite_part()  argument
4103 	return isl_seq_is_neg(bmap->ineq[i] + first, bmap->ineq[j] + first, n);  in is_opposite_part()
4109 static isl_bool is_opposite(__isl_keep isl_basic_map *bmap, int i, int j)  in is_opposite()  argument
4113 	total = isl_basic_map_dim(bmap, isl_dim_all);  in is_opposite()
4116 	return is_opposite_part(bmap, i, j, 1, total);  in is_opposite()
4150 static int div_find_coalesce(__isl_keep isl_basic_map *bmap, int *pairs,  in div_find_coalesce()  argument
4159 	n_div = isl_basic_map_dim(bmap, isl_dim_div);  in div_find_coalesce()
4162 	v_div = isl_basic_map_var_offset(bmap, isl_dim_div);  in div_find_coalesce()
4165 	if (isl_seq_first_non_zero(bmap->ineq[l] + 1 + v_div, div) != -1)  in div_find_coalesce()
4167 	if (isl_seq_first_non_zero(bmap->ineq[l] + 1 + v_div + div + 1,  in div_find_coalesce()
4170 	opp = is_opposite(bmap, l, u);  in div_find_coalesce()
4175 		if (isl_int_is_zero(bmap->div[i][0]))  in div_find_coalesce()
4177 		if (!isl_int_is_zero(bmap->div[i][1 + 1 + v_div + div]))  in div_find_coalesce()
4181 	isl_int_add(bmap->ineq[l][0], bmap->ineq[l][0], bmap->ineq[u][0]);  in div_find_coalesce()
4182 	if (isl_int_is_neg(bmap->ineq[l][0])) {  in div_find_coalesce()
4183 		isl_int_sub(bmap->ineq[l][0],  in div_find_coalesce()
4184 			    bmap->ineq[l][0], bmap->ineq[u][0]);  in div_find_coalesce()
4185 		bmap = isl_basic_map_copy(bmap);  in div_find_coalesce()
4186 		bmap = isl_basic_map_set_to_empty(bmap);  in div_find_coalesce()
4187 		isl_basic_map_free(bmap);  in div_find_coalesce()
4190 	isl_int_add_ui(bmap->ineq[l][0], bmap->ineq[l][0], 1);  in div_find_coalesce()
4198 			if (isl_int_is_zero(bmap->div[j][0]))  in div_find_coalesce()
4200 			if (!isl_int_is_zero(bmap->div[j][1 + 1 + v_div + i]))  in div_find_coalesce()
4205 		for (j = 0; j < bmap->n_ineq; ++j) {  in div_find_coalesce()
4209 			if (isl_int_is_zero(bmap->ineq[j][1 + v_div + div])) {  in div_find_coalesce()
4210 				if (is_zero_or_one(bmap->ineq[j][1 + v_div + i]))  in div_find_coalesce()
4214 			if (isl_int_is_zero(bmap->ineq[j][1 + v_div + i]))  in div_find_coalesce()
4216 			isl_int_mul(bmap->ineq[j][1 + v_div + div],  in div_find_coalesce()
4217 				    bmap->ineq[j][1 + v_div + div],  in div_find_coalesce()
4218 				    bmap->ineq[l][0]);  in div_find_coalesce()
4219 			valid = isl_int_eq(bmap->ineq[j][1 + v_div + div],  in div_find_coalesce()
4220 					   bmap->ineq[j][1 + v_div + i]);  in div_find_coalesce()
4221 			isl_int_divexact(bmap->ineq[j][1 + v_div + div],  in div_find_coalesce()
4222 					 bmap->ineq[j][1 + v_div + div],  in div_find_coalesce()
4223 					 bmap->ineq[l][0]);  in div_find_coalesce()
4227 		if (j < bmap->n_ineq)  in div_find_coalesce()
4232 	isl_int_sub_ui(bmap->ineq[l][0], bmap->ineq[l][0], 1);  in div_find_coalesce()
4233 	isl_int_sub(bmap->ineq[l][0], bmap->ineq[l][0], bmap->ineq[u][0]);  in div_find_coalesce()
4270 static isl_bool test_ineq_is_satisfied(__isl_keep isl_basic_map *bmap,  in test_ineq_is_satisfied()  argument
4276 	ctx = isl_basic_map_get_ctx(bmap);  in test_ineq_is_satisfied()
4278 		data->tab = isl_tab_from_basic_map(bmap, 0);  in test_ineq_is_satisfied()
4337 static isl_bool int_between_bounds(__isl_keep isl_basic_map *bmap, int i,  in int_between_bounds()  argument
4343 	offset = isl_basic_map_offset(bmap, isl_dim_div);  in int_between_bounds()
4344 	n_div = isl_basic_map_dim(bmap, isl_dim_div);  in int_between_bounds()
4349 		    bmap->ineq[l][offset + i], bmap->ineq[u][offset + i]);  in int_between_bounds()
4350 	isl_int_divexact(data->fl, bmap->ineq[l][offset + i], data->g);  in int_between_bounds()
4351 	isl_int_divexact(data->fu, bmap->ineq[u][offset + i], data->g);  in int_between_bounds()
4353 	isl_seq_combine(data->v->el, data->fl, bmap->ineq[u],  in int_between_bounds()
4354 			data->fu, bmap->ineq[l], offset + n_div);  in int_between_bounds()
4367 		return test_ineq_is_satisfied(bmap, data);  in int_between_bounds()
4377 	return test_ineq_is_satisfied(bmap, data);  in int_between_bounds()
4392 	__isl_take isl_basic_map *bmap, __isl_take int *pairs, int n)  in drop_more_redundant_divs()  argument
4404 	n_div = isl_basic_map_dim(bmap, isl_dim_div);  in drop_more_redundant_divs()
4408 	ctx = isl_basic_map_get_ctx(bmap);  in drop_more_redundant_divs()
4409 	off = isl_basic_map_offset(bmap, isl_dim_div);  in drop_more_redundant_divs()
4428 		for (l = 0; l < bmap->n_ineq; ++l) {  in drop_more_redundant_divs()
4429 			if (!isl_int_is_pos(bmap->ineq[l][off + i]))  in drop_more_redundant_divs()
4431 			if (isl_int_is_one(bmap->ineq[l][off + i]))  in drop_more_redundant_divs()
4433 			for (u = 0; u < bmap->n_ineq; ++u) {  in drop_more_redundant_divs()
4434 				if (!isl_int_is_neg(bmap->ineq[u][off + i]))  in drop_more_redundant_divs()
4436 				if (isl_int_is_negone(bmap->ineq[u][off + i]))  in drop_more_redundant_divs()
4438 				has_int = int_between_bounds(bmap, i, l, u,  in drop_more_redundant_divs()
4447 			if (u < bmap->n_ineq)  in drop_more_redundant_divs()
4451 			bmap = isl_basic_map_set_to_empty(bmap);  in drop_more_redundant_divs()
4454 		if (l == bmap->n_ineq) {  in drop_more_redundant_divs()
4467 		return bmap;  in drop_more_redundant_divs()
4469 	bmap = isl_basic_map_remove_dims(bmap, isl_dim_div, remove, 1);  in drop_more_redundant_divs()
4470 	return isl_basic_map_drop_redundant_divs(bmap);  in drop_more_redundant_divs()
4473 	isl_basic_map_free(bmap);  in drop_more_redundant_divs()
4527 static __isl_give isl_basic_map *coalesce_divs(__isl_take isl_basic_map *bmap,  in coalesce_divs()  argument
4536 	ctx = isl_basic_map_get_ctx(bmap);  in coalesce_divs()
4538 	v_div = isl_basic_map_var_offset(bmap, isl_dim_div);  in coalesce_divs()
4540 		return isl_basic_map_free(bmap);  in coalesce_divs()
4541 	total = 1 + v_div + bmap->n_div;  in coalesce_divs()
4544 	isl_int_add(m, bmap->ineq[l][0], bmap->ineq[u][0]);  in coalesce_divs()
4547 	for (i = 0; i < bmap->n_ineq; ++i) {  in coalesce_divs()
4550 		if (isl_int_is_zero(bmap->ineq[i][1 + v_div + div2]))  in coalesce_divs()
4552 		if (isl_int_is_zero(bmap->ineq[i][1 + v_div + div1])) {  in coalesce_divs()
4553 			if (isl_int_is_pos(bmap->ineq[i][1 + v_div + div2]))  in coalesce_divs()
4554 				isl_seq_combine(bmap->ineq[i], m, bmap->ineq[i],  in coalesce_divs()
4555 						ctx->one, bmap->ineq[l], total);  in coalesce_divs()
4557 				isl_seq_combine(bmap->ineq[i], m, bmap->ineq[i],  in coalesce_divs()
4558 						ctx->one, bmap->ineq[u], total);  in coalesce_divs()
4560 		isl_int_set(bmap->ineq[i][1 + v_div + div2],  in coalesce_divs()
4561 			    bmap->ineq[i][1 + v_div + div1]);  in coalesce_divs()
4562 		isl_int_set_si(bmap->ineq[i][1 + v_div + div1], 0);  in coalesce_divs()
4567 		isl_basic_map_drop_inequality(bmap, l);  in coalesce_divs()
4568 		isl_basic_map_drop_inequality(bmap, u);  in coalesce_divs()
4570 		isl_basic_map_drop_inequality(bmap, u);  in coalesce_divs()
4571 		isl_basic_map_drop_inequality(bmap, l);  in coalesce_divs()
4573 	bmap = isl_basic_map_mark_div_unknown(bmap, div2);  in coalesce_divs()
4574 	bmap = isl_basic_map_drop_div(bmap, div1);  in coalesce_divs()
4575 	return bmap;  in coalesce_divs()
4587 	__isl_take isl_basic_map *bmap, int *pairs, int n)  in coalesce_or_drop_more_redundant_divs()  argument
4593 	v_div = isl_basic_map_var_offset(bmap, isl_dim_div);  in coalesce_or_drop_more_redundant_divs()
4594 	n_div = isl_basic_map_dim(bmap, isl_dim_div);  in coalesce_or_drop_more_redundant_divs()
4596 		return isl_basic_map_free(bmap);  in coalesce_or_drop_more_redundant_divs()
4601 		for (l = 0; l < bmap->n_ineq; ++l) {  in coalesce_or_drop_more_redundant_divs()
4602 			if (!isl_int_is_one(bmap->ineq[l][1 + v_div + i]))  in coalesce_or_drop_more_redundant_divs()
4604 			for (u = 0; u < bmap->n_ineq; ++u) {  in coalesce_or_drop_more_redundant_divs()
4607 				if (!isl_int_is_negone(bmap->ineq[u][1+v_div+i]))  in coalesce_or_drop_more_redundant_divs()
4609 				c = div_find_coalesce(bmap, pairs, i, l, u);  in coalesce_or_drop_more_redundant_divs()
4615 				bmap = coalesce_divs(bmap, i, c, l, u);  in coalesce_or_drop_more_redundant_divs()
4616 				return isl_basic_map_drop_redundant_divs(bmap);  in coalesce_or_drop_more_redundant_divs()
4621 	if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY)) {  in coalesce_or_drop_more_redundant_divs()
4623 		return bmap;  in coalesce_or_drop_more_redundant_divs()
4626 	return drop_more_redundant_divs(bmap, pairs, n);  in coalesce_or_drop_more_redundant_divs()
4629 	isl_basic_map_free(bmap);  in coalesce_or_drop_more_redundant_divs()
4636 static int is_parallel_part(__isl_keep isl_basic_map *bmap, int i, int j,  in is_parallel_part()  argument
4639 	return isl_seq_eq(bmap->ineq[i] + first, bmap->ineq[j] + first, n);  in is_parallel_part()
4645 static isl_bool is_parallel_except(__isl_keep isl_basic_map *bmap, int i, int j,  in is_parallel_except()  argument
4650 	total = isl_basic_map_dim(bmap, isl_dim_all);  in is_parallel_except()
4653 	return is_parallel_part(bmap, i, j, 1, pos - 1) &&  in is_parallel_except()
4654 		is_parallel_part(bmap, i, j, pos + 1, total - pos);  in is_parallel_except()
4660 static isl_bool is_opposite_except(__isl_keep isl_basic_map *bmap, int i, int j,  in is_opposite_except()  argument
4665 	total = isl_basic_map_dim(bmap, isl_dim_all);  in is_opposite_except()
4668 	return is_opposite_part(bmap, i, j, 1, pos - 1) &&  in is_opposite_except()
4669 		is_opposite_part(bmap, i, j, pos + 1, total - pos);  in is_opposite_except()
4678 	__isl_take isl_basic_map *bmap, __isl_take int *pairs, int simplify)  in drop_redundant_divs_again()  argument
4681 		bmap = isl_basic_map_simplify(bmap);  in drop_redundant_divs_again()
4683 	return isl_basic_map_drop_redundant_divs(bmap);  in drop_redundant_divs_again()
4690 static isl_bool single_unknown(__isl_keep isl_basic_map *bmap, int ineq,  in single_unknown()  argument
4698 	known = isl_basic_map_div_is_known(bmap, div);  in single_unknown()
4701 	n_div = isl_basic_map_dim(bmap, isl_dim_div);  in single_unknown()
4706 	o_div = isl_basic_map_offset(bmap, isl_dim_div);  in single_unknown()
4712 		if (isl_int_is_zero(bmap->ineq[ineq][o_div + i]))  in single_unknown()
4714 		known = isl_basic_map_div_is_known(bmap, i);  in single_unknown()
4725 static isl_bool has_coef_one(__isl_keep isl_basic_map *bmap, int div, int ineq)  in has_coef_one()  argument
4729 	o_div = isl_basic_map_offset(bmap, isl_dim_div);  in has_coef_one()
4730 	if (isl_int_is_one(bmap->ineq[ineq][o_div + div]))  in has_coef_one()
4742 	__isl_take isl_basic_map *bmap, int ineq, __isl_take int *pairs)  in set_eq_and_try_again()  argument
4744 	bmap = isl_basic_map_cow(bmap);  in set_eq_and_try_again()
4745 	isl_basic_map_inequality_to_equality(bmap, ineq);  in set_eq_and_try_again()
4746 	return drop_redundant_divs_again(bmap, pairs, 1);  in set_eq_and_try_again()
4756 	__isl_take isl_basic_map *bmap, int div, int ineq1, int ineq2,  in drop_div_and_try_again()  argument
4760 		isl_basic_map_drop_inequality(bmap, ineq1);  in drop_div_and_try_again()
4761 		isl_basic_map_drop_inequality(bmap, ineq2);  in drop_div_and_try_again()
4763 		isl_basic_map_drop_inequality(bmap, ineq2);  in drop_div_and_try_again()
4764 		isl_basic_map_drop_inequality(bmap, ineq1);  in drop_div_and_try_again()
4766 	bmap = isl_basic_map_drop_div(bmap, div);  in drop_div_and_try_again()
4767 	return drop_redundant_divs_again(bmap, pairs, 0);  in drop_div_and_try_again()
4786 static void lower_bound_from_parallel(__isl_keep isl_basic_map *bmap,  in lower_bound_from_parallel()  argument
4789 	isl_int_neg(*l, bmap->ineq[ineq][0]);  in lower_bound_from_parallel()
4790 	isl_int_add(*l, *l, bmap->ineq[lower][0]);  in lower_bound_from_parallel()
4791 	isl_int_cdiv_q(*l, *l, bmap->ineq[ineq][pos]);  in lower_bound_from_parallel()
4810 static void lower_bound_from_opposite(__isl_keep isl_basic_map *bmap,  in lower_bound_from_opposite()  argument
4813 	isl_int_neg(*u, bmap->ineq[ineq][0]);  in lower_bound_from_opposite()
4814 	isl_int_sub(*u, *u, bmap->ineq[upper][0]);  in lower_bound_from_opposite()
4815 	isl_int_cdiv_q(*u, *u, bmap->ineq[ineq][pos]);  in lower_bound_from_opposite()
4845 static int lower_bound_is_cst(__isl_keep isl_basic_map *bmap, int div, int ineq)  in lower_bound_is_cst()  argument
4853 	o_div = isl_basic_map_offset(bmap, isl_dim_div);  in lower_bound_is_cst()
4854 	for (i = 0; i < bmap->n_ineq && (lower < 0 || upper < 0); ++i) {  in lower_bound_is_cst()
4859 		if (!isl_int_is_zero(bmap->ineq[i][o_div + div]))  in lower_bound_is_cst()
4863 			par = is_parallel_except(bmap, ineq, i, o_div + div);  in lower_bound_is_cst()
4872 			opp = is_opposite_except(bmap, ineq, i, o_div + div);  in lower_bound_is_cst()
4880 		return bmap->n_ineq;  in lower_bound_is_cst()
4885 	lower_bound_from_parallel(bmap, ineq, lower, o_div + div, &l);  in lower_bound_is_cst()
4886 	lower_bound_from_opposite(bmap, ineq, upper, o_div + div, &u);  in lower_bound_is_cst()
4893 	return equal ? lower : bmap->n_ineq;  in lower_bound_is_cst()
4915 static __isl_give isl_basic_map *fix_cst_lower(__isl_take isl_basic_map *bmap,  in fix_cst_lower()  argument
4923 	o_div = isl_basic_map_offset(bmap, isl_dim_div);  in fix_cst_lower()
4924 	lower_bound_from_parallel(bmap, ineq, lower, o_div + div, &c);  in fix_cst_lower()
4925 	bmap = isl_basic_map_fix(bmap, isl_dim_div, div, c);  in fix_cst_lower()
4930 	return isl_basic_map_drop_redundant_divs(bmap);  in fix_cst_lower()
4938 static isl_bool any_div_involves_div(__isl_keep isl_basic_map *bmap, int div)  in any_div_involves_div()  argument
4943 	v_div = isl_basic_map_var_offset(bmap, isl_dim_div);  in any_div_involves_div()
4944 	n_div = isl_basic_map_dim(bmap, isl_dim_div);  in any_div_involves_div()
4951 		unknown = isl_basic_map_div_is_marked_unknown(bmap, i);  in any_div_involves_div()
4956 		if (!isl_int_is_zero(bmap->div[i][1 + 1 + v_div + div]))  in any_div_involves_div()
5006 	__isl_take isl_basic_map *bmap)  in isl_basic_map_drop_redundant_divs_ineq()  argument
5014 	if (!bmap)  in isl_basic_map_drop_redundant_divs_ineq()
5016 	if (bmap->n_div == 0)  in isl_basic_map_drop_redundant_divs_ineq()
5017 		return bmap;  in isl_basic_map_drop_redundant_divs_ineq()
5019 	off = isl_basic_map_var_offset(bmap, isl_dim_div);  in isl_basic_map_drop_redundant_divs_ineq()
5021 		return isl_basic_map_free(bmap);  in isl_basic_map_drop_redundant_divs_ineq()
5022 	pairs = isl_calloc_array(bmap->ctx, int, bmap->n_div);  in isl_basic_map_drop_redundant_divs_ineq()
5026 	n_ineq = isl_basic_map_n_inequality(bmap);  in isl_basic_map_drop_redundant_divs_ineq()
5029 	for (i = 0; i < bmap->n_div; ++i) {  in isl_basic_map_drop_redundant_divs_ineq()
5036 		defined = !isl_int_is_zero(bmap->div[i][0]);  in isl_basic_map_drop_redundant_divs_ineq()
5037 		involves = any_div_involves_div(bmap, i);  in isl_basic_map_drop_redundant_divs_ineq()
5042 		for (j = 0; j < bmap->n_eq; ++j)  in isl_basic_map_drop_redundant_divs_ineq()
5043 			if (!isl_int_is_zero(bmap->eq[j][1 + off + i]))  in isl_basic_map_drop_redundant_divs_ineq()
5045 		if (j < bmap->n_eq)  in isl_basic_map_drop_redundant_divs_ineq()
5049 		for (j = 0; j < bmap->n_ineq; ++j) {  in isl_basic_map_drop_redundant_divs_ineq()
5050 			if (isl_int_is_pos(bmap->ineq[j][1 + off + i])) {  in isl_basic_map_drop_redundant_divs_ineq()
5054 			if (isl_int_is_neg(bmap->ineq[j][1 + off + i])) {  in isl_basic_map_drop_redundant_divs_ineq()
5061 			for (j = bmap->n_ineq - 1; j >= 0; --j)  in isl_basic_map_drop_redundant_divs_ineq()
5062 				if (!isl_int_is_zero(bmap->ineq[j][1+off+i]))  in isl_basic_map_drop_redundant_divs_ineq()
5063 					isl_basic_map_drop_inequality(bmap, j);  in isl_basic_map_drop_redundant_divs_ineq()
5064 			bmap = isl_basic_map_drop_div(bmap, i);  in isl_basic_map_drop_redundant_divs_ineq()
5065 			return drop_redundant_divs_again(bmap, pairs, 0);  in isl_basic_map_drop_redundant_divs_ineq()
5070 			opp = is_opposite(bmap, last_pos, last_neg);  in isl_basic_map_drop_redundant_divs_ineq()
5079 			single = single_unknown(bmap, last_pos, i);  in isl_basic_map_drop_redundant_divs_ineq()
5084 			one = has_coef_one(bmap, i, last_pos);  in isl_basic_map_drop_redundant_divs_ineq()
5088 				return set_eq_and_try_again(bmap, last_pos,  in isl_basic_map_drop_redundant_divs_ineq()
5090 			lower = lower_bound_is_cst(bmap, i, last_pos);  in isl_basic_map_drop_redundant_divs_ineq()
5094 				return fix_cst_lower(bmap, i, last_pos, lower,  in isl_basic_map_drop_redundant_divs_ineq()
5099 		isl_int_add(bmap->ineq[last_pos][0],  in isl_basic_map_drop_redundant_divs_ineq()
5100 			    bmap->ineq[last_pos][0], bmap->ineq[last_neg][0]);  in isl_basic_map_drop_redundant_divs_ineq()
5101 		isl_int_add_ui(bmap->ineq[last_pos][0],  in isl_basic_map_drop_redundant_divs_ineq()
5102 			       bmap->ineq[last_pos][0], 1);  in isl_basic_map_drop_redundant_divs_ineq()
5103 		redundant = isl_int_ge(bmap->ineq[last_pos][0],  in isl_basic_map_drop_redundant_divs_ineq()
5104 				bmap->ineq[last_pos][1+off+i]);  in isl_basic_map_drop_redundant_divs_ineq()
5105 		isl_int_sub_ui(bmap->ineq[last_pos][0],  in isl_basic_map_drop_redundant_divs_ineq()
5106 			       bmap->ineq[last_pos][0], 1);  in isl_basic_map_drop_redundant_divs_ineq()
5107 		isl_int_sub(bmap->ineq[last_pos][0],  in isl_basic_map_drop_redundant_divs_ineq()
5108 			    bmap->ineq[last_pos][0], bmap->ineq[last_neg][0]);  in isl_basic_map_drop_redundant_divs_ineq()
5110 			return drop_div_and_try_again(bmap, i,  in isl_basic_map_drop_redundant_divs_ineq()
5115 			set_div = ok_to_set_div_from_bound(bmap, i, last_pos);  in isl_basic_map_drop_redundant_divs_ineq()
5117 			return isl_basic_map_free(bmap);  in isl_basic_map_drop_redundant_divs_ineq()
5119 			bmap = set_div_from_lower_bound(bmap, i, last_pos);  in isl_basic_map_drop_redundant_divs_ineq()
5120 			return drop_redundant_divs_again(bmap, pairs, 1);  in isl_basic_map_drop_redundant_divs_ineq()
5127 		return coalesce_or_drop_more_redundant_divs(bmap, pairs, n);  in isl_basic_map_drop_redundant_divs_ineq()
5130 	return bmap;  in isl_basic_map_drop_redundant_divs_ineq()
5133 	isl_basic_map_free(bmap);  in isl_basic_map_drop_redundant_divs_ineq()
5169 	__isl_take isl_basic_map *bmap, unsigned pos, __isl_take isl_mat *T)  in isl_basic_map_preimage_vars()  argument
5174 	bmap = isl_basic_map_cow(bmap);  in isl_basic_map_preimage_vars()
5177 	if (!bmap || n_row < 0 || n_col < 0)  in isl_basic_map_preimage_vars()
5184 	if (isl_basic_map_check_range(bmap, isl_dim_all, pos, n_col) < 0)  in isl_basic_map_preimage_vars()
5187 	for (i = 0; i < bmap->n_eq; ++i)  in isl_basic_map_preimage_vars()
5188 		if (preimage(bmap->eq[i] + 1 + pos, T) < 0)  in isl_basic_map_preimage_vars()
5190 	for (i = 0; i < bmap->n_ineq; ++i)  in isl_basic_map_preimage_vars()
5191 		if (preimage(bmap->ineq[i] + 1 + pos, T) < 0)  in isl_basic_map_preimage_vars()
5193 	for (i = 0; i < bmap->n_div; ++i) {  in isl_basic_map_preimage_vars()
5194 		if (isl_basic_map_div_is_marked_unknown(bmap, i))  in isl_basic_map_preimage_vars()
5196 		if (preimage(bmap->div[i] + 1 + 1 + pos, T) < 0)  in isl_basic_map_preimage_vars()
5201 	return bmap;  in isl_basic_map_preimage_vars()
5203 	isl_basic_map_free(bmap);  in isl_basic_map_preimage_vars()
5250 	__isl_take isl_basic_map *bmap)  in isl_basic_map_drop_redundant_divs()  argument
5260 	if (!bmap)  in isl_basic_map_drop_redundant_divs()
5262 	if (isl_basic_map_divs_known(bmap))  in isl_basic_map_drop_redundant_divs()
5263 		return isl_basic_map_drop_redundant_divs_ineq(bmap);  in isl_basic_map_drop_redundant_divs()
5264 	if (bmap->n_eq == 0)  in isl_basic_map_drop_redundant_divs()
5265 		return isl_basic_map_drop_redundant_divs_ineq(bmap);  in isl_basic_map_drop_redundant_divs()
5266 	bmap = isl_basic_map_sort_divs(bmap);  in isl_basic_map_drop_redundant_divs()
5267 	if (!bmap)  in isl_basic_map_drop_redundant_divs()
5270 	first = isl_basic_map_first_unknown_div(bmap);  in isl_basic_map_drop_redundant_divs()
5272 		return isl_basic_map_free(bmap);  in isl_basic_map_drop_redundant_divs()
5274 	o_div = isl_basic_map_offset(bmap, isl_dim_div);  in isl_basic_map_drop_redundant_divs()
5275 	n_div = isl_basic_map_dim(bmap, isl_dim_div);  in isl_basic_map_drop_redundant_divs()
5277 		return isl_basic_map_free(bmap);  in isl_basic_map_drop_redundant_divs()
5279 	for (i = 0; i < bmap->n_eq; ++i) {  in isl_basic_map_drop_redundant_divs()
5280 		l = isl_seq_first_non_zero(bmap->eq[i] + o_div + first,  in isl_basic_map_drop_redundant_divs()
5285 		if (isl_seq_first_non_zero(bmap->eq[i] + o_div + l + 1,  in isl_basic_map_drop_redundant_divs()
5290 	if (i >= bmap->n_eq)  in isl_basic_map_drop_redundant_divs()
5291 		return isl_basic_map_drop_redundant_divs_ineq(bmap);  in isl_basic_map_drop_redundant_divs()
5293 	ctx = isl_basic_map_get_ctx(bmap);  in isl_basic_map_drop_redundant_divs()
5296 		return isl_basic_map_free(bmap);  in isl_basic_map_drop_redundant_divs()
5297 	isl_seq_cpy(T->row[0], bmap->eq[i] + o_div + l, n_div - l);  in isl_basic_map_drop_redundant_divs()
5303 		bmap = isl_basic_map_mark_div_unknown(bmap, i);  in isl_basic_map_drop_redundant_divs()
5304 	bmap = isl_basic_map_preimage_vars(bmap, o_div - 1 + l, T);  in isl_basic_map_drop_redundant_divs()
5305 	bmap = isl_basic_map_simplify(bmap);  in isl_basic_map_drop_redundant_divs()
5307 	return isl_basic_map_drop_redundant_divs(bmap);  in isl_basic_map_drop_redundant_divs()
5313 static isl_bool has_multiple_var_equality(__isl_keep isl_basic_map *bmap)  in has_multiple_var_equality()  argument
5318 	total = isl_basic_map_dim(bmap, isl_dim_all);  in has_multiple_var_equality()
5322 	for (i = 0; i < bmap->n_eq; ++i) {  in has_multiple_var_equality()
5325 		j = isl_seq_first_non_zero(bmap->eq[i] + 1, total);  in has_multiple_var_equality()
5328 		if (!isl_int_is_one(bmap->eq[i][1 + j]) &&  in has_multiple_var_equality()
5329 		    !isl_int_is_negone(bmap->eq[i][1 + j]))  in has_multiple_var_equality()
5333 		k = isl_seq_first_non_zero(bmap->eq[i] + 1 + j, total - j);  in has_multiple_var_equality()
5337 		if (!isl_int_is_one(bmap->eq[i][1 + j]) &&  in has_multiple_var_equality()
5338 		    !isl_int_is_negone(bmap->eq[i][1 + j]))  in has_multiple_var_equality()
5342 		k = isl_seq_first_non_zero(bmap->eq[i] + 1 + j, total - j);  in has_multiple_var_equality()
5410 	__isl_take isl_basic_map *bmap)  in isl_basic_map_reduce_coefficients()  argument
5420 	if (!bmap)  in isl_basic_map_reduce_coefficients()
5422 	if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_REDUCED_COEFFICIENTS))  in isl_basic_map_reduce_coefficients()
5423 		return bmap;  in isl_basic_map_reduce_coefficients()
5424 	if (isl_basic_map_is_rational(bmap))  in isl_basic_map_reduce_coefficients()
5425 		return bmap;  in isl_basic_map_reduce_coefficients()
5426 	if (bmap->n_eq == 0)  in isl_basic_map_reduce_coefficients()
5427 		return bmap;  in isl_basic_map_reduce_coefficients()
5428 	multi = has_multiple_var_equality(bmap);  in isl_basic_map_reduce_coefficients()
5430 		return isl_basic_map_free(bmap);  in isl_basic_map_reduce_coefficients()
5432 		return bmap;  in isl_basic_map_reduce_coefficients()
5434 	total = isl_basic_map_dim(bmap, isl_dim_all);  in isl_basic_map_reduce_coefficients()
5436 		return isl_basic_map_free(bmap);  in isl_basic_map_reduce_coefficients()
5437 	ctx = isl_basic_map_get_ctx(bmap);  in isl_basic_map_reduce_coefficients()
5440 		return isl_basic_map_free(bmap);  in isl_basic_map_reduce_coefficients()
5442 	eq = isl_mat_sub_alloc6(ctx, bmap->eq, 0, bmap->n_eq, 0, 1 + total);  in isl_basic_map_reduce_coefficients()
5450 		return isl_basic_map_set_to_empty(bmap);  in isl_basic_map_reduce_coefficients()
5453 	bmap = isl_basic_map_cow(bmap);  in isl_basic_map_reduce_coefficients()
5454 	if (!bmap)  in isl_basic_map_reduce_coefficients()
5458 	for (i = 0; i < bmap->n_ineq; ++i) {  in isl_basic_map_reduce_coefficients()
5459 		isl_seq_cpy(v->el, bmap->ineq[i], 1 + total);  in isl_basic_map_reduce_coefficients()
5465 		isl_seq_cpy(bmap->ineq[i], v->el, 1 + total);  in isl_basic_map_reduce_coefficients()
5472 	ISL_F_SET(bmap, ISL_BASIC_MAP_REDUCED_COEFFICIENTS);  in isl_basic_map_reduce_coefficients()
5477 		ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);  in isl_basic_map_reduce_coefficients()
5478 		bmap = isl_basic_map_detect_inequality_pairs(bmap, &progress);  in isl_basic_map_reduce_coefficients()
5480 			bmap = eliminate_divs_eq(bmap, &progress);  in isl_basic_map_reduce_coefficients()
5481 			bmap = isl_basic_map_gauss(bmap, NULL);  in isl_basic_map_reduce_coefficients()
5485 	return bmap;  in isl_basic_map_reduce_coefficients()
5490 	return isl_basic_map_free(bmap);  in isl_basic_map_reduce_coefficients()
5507 	__isl_take isl_basic_map *bmap, int div, int pos, isl_int shift)  in isl_basic_map_shift_div()  argument
5513 		return bmap;  in isl_basic_map_shift_div()
5514 	total = isl_basic_map_dim(bmap, isl_dim_all);  in isl_basic_map_shift_div()
5515 	n_div = isl_basic_map_dim(bmap, isl_dim_div);  in isl_basic_map_shift_div()
5518 		return isl_basic_map_free(bmap);  in isl_basic_map_shift_div()
5520 	isl_int_addmul(bmap->div[div][1 + pos], shift, bmap->div[div][0]);  in isl_basic_map_shift_div()
5522 	for (i = 0; i < bmap->n_eq; ++i) {  in isl_basic_map_shift_div()
5523 		if (isl_int_is_zero(bmap->eq[i][1 + total + div]))  in isl_basic_map_shift_div()
5525 		isl_int_submul(bmap->eq[i][pos],  in isl_basic_map_shift_div()
5526 				shift, bmap->eq[i][1 + total + div]);  in isl_basic_map_shift_div()
5528 	for (i = 0; i < bmap->n_ineq; ++i) {  in isl_basic_map_shift_div()
5529 		if (isl_int_is_zero(bmap->ineq[i][1 + total + div]))  in isl_basic_map_shift_div()
5531 		isl_int_submul(bmap->ineq[i][pos],  in isl_basic_map_shift_div()
5532 				shift, bmap->ineq[i][1 + total + div]);  in isl_basic_map_shift_div()
5534 	for (i = 0; i < bmap->n_div; ++i) {  in isl_basic_map_shift_div()
5535 		if (isl_int_is_zero(bmap->div[i][0]))  in isl_basic_map_shift_div()
5537 		if (isl_int_is_zero(bmap->div[i][1 + 1 + total + div]))  in isl_basic_map_shift_div()
5539 		isl_int_submul(bmap->div[i][1 + pos],  in isl_basic_map_shift_div()
5540 				shift, bmap->div[i][1 + 1 + total + div]);  in isl_basic_map_shift_div()
5543 	return bmap;  in isl_basic_map_shift_div()