/* * Copyright 2008-2009 Katholieke Universiteit Leuven * Copyright 2010 INRIA Saclay * Copyright 2011 Sven Verdoolaege * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, K.U.Leuven, Departement * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite, * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France */ #define xSF(TYPE,SUFFIX) … #define SF(TYPE,SUFFIX) … /* Given a basic map with at least two parallel constraints (as found * by the function parallel_constraints), first look for more constraints * parallel to the two constraint and replace the found list of parallel * constraints by a single constraint with as "input" part the minimum * of the input parts of the list of constraints. Then, recursively call * basic_map_partial_lexopt (possibly finding more parallel constraints) * and plug in the definition of the minimum in the result. * * As in parallel_constraints, only inequality constraints that only * involve input variables that do not occur in any other inequality * constraints are considered. * * More specifically, given a set of constraints * * a x + b_i(p) >= 0 * * Replace this set by a single constraint * * a x + u >= 0 * * with u a new parameter with constraints * * u <= b_i(p) * * Any solution to the new system is also a solution for the original system * since * * a x >= -u >= -b_i(p) * * Moreover, m = min_i(b_i(p)) satisfies the constraints on u and can * therefore be plugged into the solution. */ static TYPE *SF(basic_map_partial_lexopt_symm,SUFFIX)( __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *dom, __isl_give isl_set **empty, int max, int first, int second) { … } /* Recursive part of isl_tab_basic_map_partial_lexopt*, after detecting * equalities and removing redundant constraints. * * We first check if there are any parallel constraints (left). * If not, we are in the base case. * If there are parallel constraints, we replace them by a single * constraint in basic_map_partial_lexopt_symm_pma and then call * this function recursively to look for more parallel constraints. */ static __isl_give TYPE *SF(basic_map_partial_lexopt,SUFFIX)( __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *dom, __isl_give isl_set **empty, int max) { … } /* Compute the lexicographic minimum (or maximum if "flags" includes * ISL_OPT_MAX) of "bmap" over the domain "dom" and return the result as * either a map or a piecewise multi-affine expression depending on TYPE. * If "empty" is not NULL, then *empty is assigned a set that * contains those parts of the domain where there is no solution. * If "flags" includes ISL_OPT_FULL, then "dom" is NULL and the optimum * should be computed over the domain of "bmap". "empty" is also NULL * in this case. * If "bmap" is marked as rational (ISL_BASIC_MAP_RATIONAL), * then we compute the rational optimum. Otherwise, we compute * the integral optimum. * * We perform some preprocessing. As the PILP solver does not * handle implicit equalities very well, we first make sure all * the equalities are explicitly available. * * We also add context constraints to the basic map and remove * redundant constraints. This is only needed because of the * way we handle simple symmetries. In particular, we currently look * for symmetries on the constraints, before we set up the main tableau. * It is then no good to look for symmetries on possibly redundant constraints. * If the domain was extracted from the basic map, then there is * no need to add back those constraints again. */ __isl_give TYPE *SF(isl_tab_basic_map_partial_lexopt,SUFFIX)( __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *dom, __isl_give isl_set **empty, unsigned flags) { … }
Codebase Browser
llvm