llvm/polly/lib/External/isl/basis_reduction_templ.c

/*
 * Copyright 2006-2007 Universiteit Leiden
 * Copyright 2008-2009 Katholieke Universiteit Leuven
 *
 * Use of this software is governed by the MIT license
 *
 * Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science,
 * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
 * and K.U.Leuven, Departement Computerwetenschappen, Celestijnenlaan 200A,
 * B-3001 Leuven, Belgium
 */

#include <stdlib.h>
#include <isl_ctx_private.h>
#include <isl_map_private.h>
#include <isl_vec_private.h>
#include <isl_options_private.h>
#include "isl_basis_reduction.h"

static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha)
{ … }

/* Compute a reduced basis for the set represented by the tableau "tab".
 * tab->basis, which must be initialized by the calling function to an affine
 * unimodular basis, is updated to reflect the reduced basis.
 * The first tab->n_zero rows of the basis (ignoring the constant row)
 * are assumed to correspond to equalities and are left untouched.
 * tab->n_zero is updated to reflect any additional equalities that
 * have been detected in the first rows of the new basis.
 * The final tab->n_unbounded rows of the basis are assumed to correspond
 * to unbounded directions and are also left untouched.
 * In particular this means that the remaining rows are assumed to
 * correspond to bounded directions.
 *
 * This function implements the algorithm described in
 * "An Implementation of the Generalized Basis Reduction Algorithm
 *  for Integer Programming" of Cook el al. to compute a reduced basis.
 * We use \epsilon = 1/4.
 *
 * If ctx->opt->gbr_only_first is set, the user is only interested
 * in the first direction.  In this case we stop the basis reduction when
 * the width in the first direction becomes smaller than 2.
 */
struct isl_tab *isl_tab_compute_reduced_basis(struct isl_tab *tab)
{ … }

/* Compute an affine form of a reduced basis of the given basic
 * non-parametric set, which is assumed to be bounded and not
 * include any integer divisions.
 * The first column and the first row correspond to the constant term.
 *
 * If the input contains any equalities, we first create an initial
 * basis with the equalities first.  Otherwise, we start off with
 * the identity matrix.
 */
__isl_give isl_mat *isl_basic_set_reduced_basis(__isl_keep isl_basic_set *bset)
{ … }