Lines Matching refs:sol
152 struct isl_sol *sol;
191 void (*add)(struct isl_sol *sol,
193 void (*add_empty)(struct isl_sol *sol, struct isl_basic_set *bset);
194 void (*free)(struct isl_sol *sol);
198 static void sol_free(struct isl_sol *sol)
201 if (!sol)
203 for (partial = sol->partial; partial; partial = next) {
209 isl_space_free(sol->space);
210 if (sol->context)
211 sol->context->op->free(sol->context);
212 sol->free(sol);
213 free(sol);
216 /* Add equality constraint "eq" to the context of "sol".
220 static void sol_context_add_eq(struct isl_sol *sol, isl_int *eq, int check,
223 sol->context->op->add_eq(sol->context, eq, check, update);
224 if (!sol->context->op->is_ok(sol->context))
225 sol->error = 1;
228 /* Add inequality constraint "ineq" to the context of "sol".
232 static void sol_context_add_ineq(struct isl_sol *sol, isl_int *ineq, int check,
235 if (sol->error)
237 sol->context->op->add_ineq(sol->context, ineq, check, update);
238 if (!sol->context->op->is_ok(sol->context))
239 sol->error = 1;
247 static void sol_push_sol(struct isl_sol *sol,
252 if (sol->error || !dom)
259 partial->level = sol->level;
262 partial->next = sol->partial;
264 sol->partial = partial;
270 sol->error = 1;
354 static void sol_push_sol_mat(struct isl_sol *sol,
365 n_known = n_div - sol->context->n_unknown;
367 ma = isl_multi_aff_alloc(isl_space_copy(sol->space));
375 sol_push_sol(sol, dom, ma);
380 sol_push_sol(sol, NULL, NULL);
384 * pass it on to sol->add or sol->add_empty.
386 static void sol_pop_one(struct isl_sol *sol)
390 partial = sol->partial;
391 sol->partial = partial->next;
394 sol->add(sol, partial->dom, partial->ma);
396 sol->add_empty(sol, partial->dom);
402 static struct isl_basic_set *sol_domain(struct isl_sol *sol)
406 if (sol->error)
409 bset = isl_basic_set_dup(sol->context->op->peek_basic_set(sol->context));
411 sol->context->op->peek_tab(sol->context));
429 /* Swap the initial two partial solutions in "sol".
433 * sol->partial = p1; p1->next = p2; p2->next = p3
437 * sol->partial = p2; p2->next = p1; p1->next = p3
439 static void swap_initial(struct isl_sol *sol)
443 partial = sol->partial;
444 sol->partial = partial->next;
446 sol->partial->next = partial;
449 /* Combine the initial two partial solution of "sol" into
450 * a partial solution with the current context domain of "sol" and
455 * replaced by (D,M2), where D is the domain of "sol", which is assumed
459 static isl_stat combine_initial_into_second(struct isl_sol *sol)
464 partial = sol->partial;
466 bset = sol_domain(sol);
469 partial->next->level = sol->level;
474 sol->partial = partial->next;
507 /* The initial two partial solutions of "sol" are known to be at
522 static isl_stat combine_initial_if_equal(struct isl_sol *sol)
527 partial = sol->partial;
533 return combine_initial_into_second(sol);
540 return combine_initial_into_second(sol);
544 swap_initial(sol);
545 return combine_initial_into_second(sol);
549 sol_pop_one(sol);
550 sol_pop_one(sol);
564 static void sol_pop(struct isl_sol *sol)
568 if (sol->error)
571 partial = sol->partial;
575 if (partial->level == 0 && sol->level == 0) {
576 for (partial = sol->partial; partial; partial = sol->partial)
577 sol_pop_one(sol);
581 if (partial->level <= sol->level)
585 if (combine_initial_if_equal(sol) < 0)
588 sol_pop_one(sol);
590 if (sol->level == 0) {
591 for (partial = sol->partial; partial; partial = sol->partial)
592 sol_pop_one(sol);
597 error: sol->error = 1;
600 static void sol_dec_level(struct isl_sol *sol)
602 if (sol->error)
605 sol->level--;
607 sol_pop(sol);
614 sol_dec_level(callback->sol);
616 return callback->sol->error ? isl_stat_error : isl_stat_ok;
625 static void sol_inc_level(struct isl_sol *sol)
629 if (sol->error)
632 sol->level++;
633 tab = sol->context->op->peek_tab(sol->context);
634 if (isl_tab_push_callback(tab, &sol->dec_level.callback) < 0)
635 sol->error = 1;
698 static void sol_add(struct isl_sol *sol, struct isl_tab *tab)
706 if (sol->error || !tab)
709 if (tab->empty && !sol->add_empty)
711 if (sol->context->op->is_empty(sol->context))
714 bset = sol_domain(sol);
717 sol_push_sol(sol, bset, NULL);
723 mat = isl_mat_alloc(tab->mat->ctx, 1 + sol->n_out,
732 for (row = 0; row < sol->n_out; ++row) {
770 if (sol->max)
777 sol_push_sol_mat(sol, bset, mat);
784 sol->error = 1;
788 struct isl_sol sol;
793 static void sol_map_free(struct isl_sol *sol)
795 struct isl_sol_map *sol_map = (struct isl_sol_map *) sol;
804 static void sol_map_add_empty(struct isl_sol_map *sol,
807 if (!bset || !sol->empty)
810 sol->empty = isl_set_grow(sol->empty, 1);
813 sol->empty = isl_set_add_basic_set(sol->empty, isl_basic_set_copy(bset));
814 if (!sol->empty)
820 sol->sol.error = 1;
823 static void sol_map_add_empty_wrap(struct isl_sol *sol,
826 sol_map_add_empty((struct isl_sol_map *)sol, bset);
833 static void sol_map_add(struct isl_sol_map *sol,
838 if (sol->sol.error || !dom || !ma)
841 bmap = isl_basic_map_from_multi_aff2(ma, sol->sol.rational);
843 sol->map = isl_map_grow(sol->map, 1);
844 sol->map = isl_map_add_basic_map(sol->map, bmap);
845 if (!sol->map)
846 sol->sol.error = 1;
851 sol->sol.error = 1;
854 static void sol_map_add_wrap(struct isl_sol *sol,
857 sol_map_add((struct isl_sol_map *)sol, dom, ma);
1998 /* Check if the context tableau of sol has any integer points.
3698 /* Initialize some common fields of "sol", which keeps track
3705 static isl_stat sol_init(struct isl_sol *sol, __isl_keep isl_basic_map *bmap,
3708 sol->rational = ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL);
3709 sol->dec_level.callback.run = &sol_dec_level_wrap;
3710 sol->dec_level.sol = sol;
3711 sol->max = max;
3712 sol->n_out = isl_basic_map_dim(bmap, isl_dim_out);
3713 sol->space = isl_basic_map_get_space(bmap);
3715 sol->context = isl_context_alloc(dom);
3716 if (sol->n_out < 0 || !sol->space || !sol->context)
3742 sol_map->sol.free = &sol_map_free;
3743 if (sol_init(&sol_map->sol, bmap, dom, max) < 0)
3745 sol_map->sol.add = &sol_map_add_wrap;
3746 sol_map->sol.add_empty = track_empty ? &sol_map_add_empty_wrap : NULL;
3747 space = isl_space_copy(sol_map->sol.space);
3760 return &sol_map->sol;
3763 sol_free(&sol_map->sol);
3866 struct isl_sol *sol, int row)
3893 res = sol->context->op->ineq_sign(sol->context, ineq->el,
3902 feasible = sol->context->op->test_ineq(sol->context, ineq->el);
3922 feasible = sol->context->op->test_ineq(sol->context, ineq->el);
3936 static void find_solutions(struct isl_sol *sol, struct isl_tab *tab);
3952 static void find_in_pos(struct isl_sol *sol, struct isl_tab *tab, isl_int *ineq)
3956 if (!sol->context)
3963 saved = sol->context->op->save(sol->context);
3965 sol_context_add_ineq(sol, ineq, 0, 1);
3967 find_solutions(sol, tab);
3969 if (!sol->error)
3970 sol->context->op->restore(sol->context, saved);
3972 sol->context->op->discard(saved);
3975 sol->error = 1;
3981 static void no_sol_in_strict(struct isl_sol *sol,
3987 if (!sol->context || sol->error)
3989 saved = sol->context->op->save(sol->context);
3993 sol_context_add_ineq(sol, ineq->el, 1, 0);
3997 sol_add(sol, tab);
4002 sol->context->op->restore(sol->context, saved);
4003 if (!sol->context->op->is_ok(sol->context))
4007 sol->error = 1;
4026 * tableau "tab" within the context "sol->context_tab".
4119 static void find_solutions(struct isl_sol *sol, struct isl_tab *tab)
4124 if (!tab || sol->error)
4127 context = sol->context;
4144 sgn = row_sign(tab, sol, row);
4169 sol_inc_level(sol);
4170 find_in_pos(sol, tab, ineq->el);
4174 sol_context_add_ineq(sol, ineq->el, 0, 1);
4176 if (sol->error)
4206 sol_inc_level(sol);
4207 no_sol_in_strict(sol, tab, ineq);
4209 sol_context_add_ineq(sol, ineq->el, 1, 1);
4211 if (sol->error || !context->op->is_ok(context))
4224 sol_add(sol, tab);
4229 sol->error = 1;
4232 /* Does "sol" contain a pair of partial solutions that could potentially
4235 * We currently only check that "sol" is not in an error state
4239 static int sol_has_mergeable_solutions(struct isl_sol *sol)
4241 if (sol->error)
4243 if (!sol->partial)
4245 if (!sol->partial->next)
4247 return sol->partial->level == sol->partial->next->level;
4251 * tableau "tab" within the context "sol->context_tab".
4270 static void find_solutions_main(struct isl_sol *sol, struct isl_tab *tab)
4278 sol->level = 0;
4299 sol_inc_level(sol);
4300 no_sol_in_strict(sol, tab, eq);
4303 sol_inc_level(sol);
4304 no_sol_in_strict(sol, tab, eq);
4307 sol_context_add_eq(sol, eq->el, 1, 1);
4314 if (sol->context->op->is_empty(sol->context))
4320 saved = sol->context->op->save(sol->context);
4322 find_solutions(sol, tab);
4324 if (sol_has_mergeable_solutions(sol))
4325 sol->context->op->restore(sol->context, saved);
4327 sol->context->op->discard(saved);
4329 sol->level = 0;
4330 sol_pop(sol);
4335 sol->error = 1;
4452 struct isl_sol *sol = NULL;
4459 sol = init(bmap, dom, !!empty, max);
4460 if (!sol)
4463 context = sol->context;
4467 if (sol->add_empty)
4468 sol->add_empty(sol,
4474 find_solutions_main(sol, tab);
4476 if (sol->error)
4480 return sol;
4482 sol_free(sol);
4497 struct isl_sol *sol;
4500 sol = basic_map_partial_lexopt_base_sol(bmap, dom, empty, max,
4502 if (!sol)
4504 sol_map = (struct isl_sol_map *) sol;
4509 sol_free(&sol_map->sol);
5077 * "sol" contains the best solution found so far.
5089 isl_vec *sol;
5115 static int is_optimal(__isl_keep isl_vec *sol, int n_op)
5120 if (!isl_int_is_zero(sol->el[1 + i]))
5126 * better than that represented by "sol". That is, find the first
5140 __isl_keep isl_vec *sol, int n_op, int n_zero)
5146 if (!sol)
5150 if (!isl_int_is_zero(sol->el[1 + i]))
5159 ctx = isl_vec_get_ctx(sol);
5281 data->sol = isl_vec_alloc(ctx, 0);
5384 isl_vec_free(data->sol);
5385 data->sol = isl_tab_get_sample_value(data->tab);
5386 if (!data->sol)
5388 if (is_optimal(data->sol, data->n_op))
5425 data->sol, data->n_op, local->n_zero);
5567 return data.sol;
5571 isl_vec_free(data.sol);
5690 struct isl_sol sol;
5695 static void sol_pma_free(struct isl_sol *sol)
5697 struct isl_sol_pma *sol_pma = (struct isl_sol_pma *) sol;
5706 static void sol_pma_add_empty(struct isl_sol_pma *sol,
5709 if (!bset || !sol->empty)
5712 sol->empty = isl_set_grow(sol->empty, 1);
5715 sol->empty = isl_set_add_basic_set(sol->empty, bset);
5716 if (!sol->empty)
5717 sol->sol.error = 1;
5721 sol->sol.error = 1;
5729 static void sol_pma_add(struct isl_sol_pma *sol,
5737 sol->pma = isl_pw_multi_aff_add_disjoint(sol->pma, pma);
5738 if (!sol->pma)
5739 sol->sol.error = 1;
5742 static void sol_pma_add_empty_wrap(struct isl_sol *sol,
5745 sol_pma_add_empty((struct isl_sol_pma *)sol, bset);
5748 static void sol_pma_add_wrap(struct isl_sol *sol,
5751 sol_pma_add((struct isl_sol_pma *)sol, dom, ma);
5774 sol_pma->sol.free = &sol_pma_free;
5775 if (sol_init(&sol_pma->sol, bmap, dom, max) < 0)
5777 sol_pma->sol.add = &sol_pma_add_wrap;
5778 sol_pma->sol.add_empty = track_empty ? &sol_pma_add_empty_wrap : NULL;
5779 space = isl_space_copy(sol_pma->sol.space);
5792 return &sol_pma->sol;
5795 sol_free(&sol_pma->sol);
5809 struct isl_sol *sol;
5812 sol = basic_map_partial_lexopt_base_sol(bmap, dom, empty, max,
5814 if (!sol)
5816 sol_pma = (struct isl_sol_pma *) sol;
5821 sol_free(&sol_pma->sol);
Indexes created Sun Jun 28 00:24:58 UTC 2026