## Coverage Report

#### Created: 2017-03-24 03:18

`/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/External/isl/isl_ilp.c`
 `Line` `Count` `Source (jump to first uncovered line)` `1` `/*` `2` ` * Copyright 2008-2009 Katholieke Universiteit Leuven` `3` ` *` `4` ` * Use of this software is governed by the MIT license` `5` ` *` `6` ` * Written by Sven Verdoolaege, K.U.Leuven, Departement` `7` ` * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium` `8` ` */` `9` `10` `#include ` `11` `#include ` `12` `#include ` `13` `#include ` `14` `#include "isl_sample.h"` `15` `#include ` `16` `#include "isl_equalities.h"` `17` `#include ` `18` `#include ` `19` `#include ` `20` `#include ` `21` `#include ` `22` `#include ` `23` `#include ` `24` `#include ` `25` `26` `/* Given a basic set "bset", construct a basic set U such that for` `27` ` * each element x in U, the whole unit box positioned at x is inside` `28` ` * the given basic set.` `29` ` * Note that U may not contain all points that satisfy this property.` `30` ` *` `31` ` * We simply add the sum of all negative coefficients to the constant` `32` ` * term. This ensures that if x satisfies the resulting constraints,` `33` ` * then x plus any sum of unit vectors satisfies the original constraints.` `34` ` */` `35` `static struct isl_basic_set *unit_box_base_points(struct isl_basic_set *bset)` `36` `200` `{` `37` `200` `  int i, j, k;` `38` `200` `  struct isl_basic_set *unit_box = NULL;` `39` `200` `  unsigned total;` `40` `200` `41` `200` `  if (!bset)` `42` `0` `    goto error;` `43` `200` `44` `200` `  if (200bset->n_eq != 0200) {0` `45` `0` `    isl_space *space = isl_basic_set_get_space(bset);` `46` `0` `    isl_basic_set_free(bset);` `47` `0` `    return isl_basic_set_empty(space);` `48` `0` `  }` `49` `200` `50` `200` `  total = isl_basic_set_total_dim(bset);` `51` `200` `  unit_box = isl_basic_set_alloc_space(isl_basic_set_get_space(bset),` `52` `200` `          0, 0, bset->n_ineq);` `53` `200` `54` `626` `  for (i = 0; i < bset->n_ineq626; ++i426) {426` `55` `426` `    k = isl_basic_set_alloc_inequality(unit_box);` `56` `426` `    if (k < 0)` `57` `0` `      goto error;` `58` `426` `    isl_seq_cpy(unit_box->ineq[k], bset->ineq[i], 1 + total);` `59` `2.55k` `    for (j = 0; j < total2.55k; ++j2.12k) {2.12k` `60` `2.12k` `      if (isl_int_is_nonneg(unit_box->ineq[k][1 + j]))` `61` `1.89k` `        continue;` `62` `229` `      isl_int_add229(unit_box->ineq[k][0],229` `63` `229` `        unit_box->ineq[k][0], unit_box->ineq[k][1 + j]);` `64` `229` `    }` `65` `426` `  }` `66` `200` `67` `200` `  isl_basic_set_free(bset);` `68` `200` `  return unit_box;` `69` `0` `error:` `70` `0` `  isl_basic_set_free(bset);` `71` `0` `  isl_basic_set_free(unit_box);` `72` `0` `  return NULL;` `73` `200` `}` `74` `75` `/* Find an integer point in "bset", preferably one that is` `76` ` * close to minimizing "f".` `77` ` *` `78` ` * We first check if we can easily put unit boxes inside bset.` `79` ` * If so, we take the best base point of any of the unit boxes we can find` `80` ` * and round it up to the nearest integer.` `81` ` * If not, we simply pick any integer point in "bset".` `82` ` */` `83` `static struct isl_vec *initial_solution(struct isl_basic_set *bset, isl_int *f)` `84` `200` `{` `85` `200` `  enum isl_lp_result res;` `86` `200` `  struct isl_basic_set *unit_box;` `87` `200` `  struct isl_vec *sol;` `88` `200` `89` `200` `  unit_box = unit_box_base_points(isl_basic_set_copy(bset));` `90` `200` `91` `200` `  res = isl_basic_set_solve_lp(unit_box, 0, f, bset->ctx->one,` `92` `200` `          NULL, NULL, &sol);` `93` `200` `  if (res == isl_lp_ok200) {4` `94` `4` `    isl_basic_set_free(unit_box);` `95` `4` `    return isl_vec_ceil(sol);` `96` `4` `  }` `97` `200` `98` `196` `  isl_basic_set_free(unit_box);` `99` `196` `100` `196` `  return isl_basic_set_sample_vec(isl_basic_set_copy(bset));` `101` `200` `}` `102` `103` `/* Restrict "bset" to those points with values for f in the interval [l, u].` `104` ` */` `105` `static struct isl_basic_set *add_bounds(struct isl_basic_set *bset,` `106` `  isl_int *f, isl_int l, isl_int u)` `107` `35` `{` `108` `35` `  int k;` `109` `35` `  unsigned total;` `110` `35` `111` `35` `  total = isl_basic_set_total_dim(bset);` `112` `35` `  bset = isl_basic_set_extend_constraints(bset, 0, 2);` `113` `35` `114` `35` `  k = isl_basic_set_alloc_inequality(bset);` `115` `35` `  if (k < 0)` `116` `0` `    goto error;` `117` `35` `  isl_seq_cpy(bset->ineq[k], f, 1 + total);` `118` `35` `  isl_int_sub(bset->ineq[k][0], bset->ineq[k][0], l);` `119` `35` `120` `35` `  k = isl_basic_set_alloc_inequality(bset);` `121` `35` `  if (k < 0)` `122` `0` `    goto error;` `123` `35` `  isl_seq_neg(bset->ineq[k], f, 1 + total);` `124` `35` `  isl_int_add(bset->ineq[k][0], bset->ineq[k][0], u);` `125` `35` `126` `35` `  return bset;` `127` `0` `error:` `128` `0` `  isl_basic_set_free(bset);` `129` `0` `  return NULL;` `130` `35` `}` `131` `132` `/* Find an integer point in "bset" that minimizes f (in any) such that` `133` ` * the value of f lies inside the interval [l, u].` `134` ` * Return this integer point if it can be found.` `135` ` * Otherwise, return sol.` `136` ` *` `137` ` * We perform a number of steps until l > u.` `138` ` * In each step, we look for an integer point with value in either` `139` ` * the whole interval [l, u] or half of the interval [l, l+floor(u-l-1/2)].` `140` ` * The choice depends on whether we have found an integer point in the` `141` ` * previous step. If so, we look for the next point in half of the remaining` `142` ` * interval.` `143` ` * If we find a point, the current solution is updated and u is set` `144` ` * to its value minus 1.` `145` ` * If no point can be found, we update l to the upper bound of the interval` `146` ` * we checked (u or l+floor(u-l-1/2)) plus 1.` `147` ` */` `148` `static struct isl_vec *solve_ilp_search(struct isl_basic_set *bset,` `149` `  isl_int *f, isl_int *opt, struct isl_vec *sol, isl_int l, isl_int u)` `150` `5` `{` `151` `5` `  isl_int tmp;` `152` `5` `  int divide = 1;` `153` `5` `154` `5` `  isl_int_init(tmp);` `155` `5` `156` `36` `  while (isl_int_le36(l, u)) {35` `157` `35` `    struct isl_basic_set *slice;` `158` `35` `    struct isl_vec *sample;` `159` `35` `160` `35` `    if (!divide)` `161` `4` `      isl_int_set(tmp, u);` `162` `31` `    else {` `163` `31` `      isl_int_sub(tmp, u, l);` `164` `31` `      isl_int_fdiv_q_ui(tmp, tmp, 2);` `165` `31` `      isl_int_add(tmp, tmp, l);` `166` `31` `    }` `167` `35` `    slice = add_bounds(isl_basic_set_copy(bset), f, l, tmp);` `168` `35` `    sample = isl_basic_set_sample_vec(slice);` `169` `35` `    if (!sample35) {0` `170` `0` `      isl_vec_free(sol);` `171` `0` `      sol = NULL;` `172` `0` `      break;` `173` `0` `    }` `174` `35` `    if (35sample->size > 035) {27` `175` `27` `      isl_vec_free(sol);` `176` `27` `      sol = sample;` `177` `27` `      isl_seq_inner_product(f, sol->el, sol->size, opt);` `178` `27` `      isl_int_sub_ui(u, *opt, 1);` `179` `27` `      divide = 1;` `180` `8` `    } else {` `181` `8` `      isl_vec_free(sample);` `182` `8` `      if (!divide)` `183` `4` `        break;` `184` `4` `      isl_int_add_ui4(l, tmp, 1);4` `185` `4` `      divide = 0;` `186` `4` `    }` `187` `35` `  }` `188` `5` `189` `5` `  isl_int_clear(tmp);` `190` `5` `191` `5` `  return sol;` `192` `5` `}` `193` `194` `/* Find an integer point in "bset" that minimizes f (if any).` `195` ` * If sol_p is not NULL then the integer point is returned in *sol_p.` `196` ` * The optimal value of f is returned in *opt.` `197` ` *` `198` ` * The algorithm maintains a currently best solution and an interval [l, u]` `199` ` * of values of f for which integer solutions could potentially still be found.` `200` ` * The initial value of the best solution so far is any solution.` `201` ` * The initial value of l is minimal value of f over the rationals` `202` ` * (rounded up to the nearest integer).` `203` ` * The initial value of u is the value of f at the initial solution minus 1.` `204` ` *` `205` ` * We then call solve_ilp_search to perform a binary search on the interval.` `206` ` */` `207` `static enum isl_lp_result solve_ilp(struct isl_basic_set *bset,` `208` `         isl_int *f, isl_int *opt,` `209` `         struct isl_vec **sol_p)` `210` `969` `{` `211` `969` `  enum isl_lp_result res;` `212` `969` `  isl_int l, u;` `213` `969` `  struct isl_vec *sol;` `214` `969` `215` `969` `  res = isl_basic_set_solve_lp(bset, 0, f, bset->ctx->one,` `216` `969` `          opt, NULL, &sol);` `217` `969` `  if (res == isl_lp_ok && 969isl_int_is_one773(sol->el[0])) {768` `218` `768` `    if (sol_p)` `219` `0` `      *sol_p = sol;` `220` `768` `    else` `221` `768` `      isl_vec_free(sol);` `222` `768` `    return isl_lp_ok;` `223` `768` `  }` `224` `201` `  isl_vec_free(sol);` `225` `201` `  if (res == isl_lp_error || 201res == isl_lp_empty201)` `226` `1` `    return res;` `227` `201` `228` `200` `  sol = initial_solution(bset, f);` `229` `200` `  if (!sol)` `230` `0` `    return isl_lp_error;` `231` `200` `  if (200sol->size == 0200) {0` `232` `0` `    isl_vec_free(sol);` `233` `0` `    return isl_lp_empty;` `234` `0` `  }` `235` `200` `  if (200res == isl_lp_unbounded200) {195` `236` `195` `    isl_vec_free(sol);` `237` `195` `    return isl_lp_unbounded;` `238` `195` `  }` `239` `200` `240` `5` `  isl_int_init5(l);5` `241` `5` `  isl_int_init(u);` `242` `5` `243` `5` `  isl_int_set(l, *opt);` `244` `5` `245` `5` `  isl_seq_inner_product(f, sol->el, sol->size, opt);` `246` `5` `  isl_int_sub_ui(u, *opt, 1);` `247` `5` `248` `5` `  sol = solve_ilp_search(bset, f, opt, sol, l, u);` `249` `5` `  if (!sol)` `250` `0` `    res = isl_lp_error;` `251` `5` `252` `5` `  isl_int_clear(l);` `253` `5` `  isl_int_clear(u);` `254` `5` `255` `5` `  if (sol_p)` `256` `0` `    *sol_p = sol;` `257` `5` `  else` `258` `5` `    isl_vec_free(sol);` `259` `5` `260` `5` `  return res;` `261` `200` `}` `262` `263` `static enum isl_lp_result solve_ilp_with_eq(struct isl_basic_set *bset, int max,` `264` `         isl_int *f, isl_int *opt,` `265` `         struct isl_vec **sol_p)` `266` `597` `{` `267` `597` `  unsigned dim;` `268` `597` `  enum isl_lp_result res;` `269` `597` `  struct isl_mat *T = NULL;` `270` `597` `  struct isl_vec *v;` `271` `597` `272` `597` `  bset = isl_basic_set_copy(bset);` `273` `597` `  dim = isl_basic_set_total_dim(bset);` `274` `597` `  v = isl_vec_alloc(bset->ctx, 1 + dim);` `275` `597` `  if (!v)` `276` `0` `    goto error;` `277` `597` `  isl_seq_cpy(v->el, f, 1 + dim);` `278` `597` `  bset = isl_basic_set_remove_equalities(bset, &T, NULL);` `279` `597` `  v = isl_vec_mat_product(v, isl_mat_copy(T));` `280` `597` `  if (!v)` `281` `0` `    goto error;` `282` `597` `  res = isl_basic_set_solve_ilp(bset, max, v->el, opt, sol_p);` `283` `597` `  isl_vec_free(v);` `284` `597` `  if (res == isl_lp_ok && 597sol_p596) {0` `285` `0` `    *sol_p = isl_mat_vec_product(T, *sol_p);` `286` `0` `    if (!*sol_p)` `287` `0` `      res = isl_lp_error;` `288` `0` `  } else` `289` `597` `    isl_mat_free(T);` `290` `597` `  isl_basic_set_free(bset);` `291` `597` `  return res;` `292` `0` `error:` `293` `0` `  isl_mat_free(T);` `294` `0` `  isl_basic_set_free(bset);` `295` `0` `  return isl_lp_error;` `296` `597` `}` `297` `298` `/* Find an integer point in "bset" that minimizes (or maximizes if max is set)` `299` ` * f (if any).` `300` ` * If sol_p is not NULL then the integer point is returned in *sol_p.` `301` ` * The optimal value of f is returned in *opt.` `302` ` *` `303` ` * If there is any equality among the points in "bset", then we first` `304` ` * project it out. Otherwise, we continue with solve_ilp above.` `305` ` */` `306` `enum isl_lp_result isl_basic_set_solve_ilp(struct isl_basic_set *bset, int max,` `307` `         isl_int *f, isl_int *opt,` `308` `         struct isl_vec **sol_p)` `309` `1.56k` `{` `310` `1.56k` `  unsigned dim;` `311` `1.56k` `  enum isl_lp_result res;` `312` `1.56k` `313` `1.56k` `  if (!bset)` `314` `0` `    return isl_lp_error;` `315` `1.56k` `  if (1.56ksol_p1.56k)` `316` `0` `    *sol_p = NULL;` `317` `1.56k` `318` `1.56k` `  isl_assert(bset->ctx, isl_basic_set_n_param(bset) == 0,` `319` `1.56k` `    return isl_lp_error);` `320` `1.56k` `321` `1.56k` `  if (1.56kisl_basic_set_plain_is_empty(bset)1.56k)` `322` `1` `    return isl_lp_empty;` `323` `1.56k` `324` `1.56k` `  if (1.56kbset->n_eq1.56k)` `325` `597` `    return solve_ilp_with_eq(bset, max, f, opt, sol_p);` `326` `1.56k` `327` `969` `  dim = isl_basic_set_total_dim(bset);` `328` `969` `329` `969` `  if (max)` `330` `965` `    isl_seq_neg(f, f, 1 + dim);` `331` `969` `332` `969` `  res = solve_ilp(bset, f, opt, sol_p);` `333` `969` `334` `969` `  if (max969) {965` `335` `965` `    isl_seq_neg(f, f, 1 + dim);` `336` `965` `    isl_int_neg(*opt, *opt);` `337` `965` `  }` `338` `969` `339` `969` `  return res;` `340` `1.56k` `}` `341` `342` `static enum isl_lp_result basic_set_opt(__isl_keep isl_basic_set *bset, int max,` `343` `  __isl_keep isl_aff *obj, isl_int *opt)` `344` `970` `{` `345` `970` `  enum isl_lp_result res;` `346` `970` `347` `970` `  if (!obj)` `348` `0` `    return isl_lp_error;` `349` `970` `  bset = isl_basic_set_copy(bset);` `350` `970` `  bset = isl_basic_set_underlying_set(bset);` `351` `970` `  res = isl_basic_set_solve_ilp(bset, max, obj->v->el + 1, opt, NULL);` `352` `970` `  isl_basic_set_free(bset);` `353` `970` `  return res;` `354` `970` `}` `355` `356` `static __isl_give isl_mat *extract_divs(__isl_keep isl_basic_set *bset)` `357` `5` `{` `358` `5` `  int i;` `359` `5` `  isl_ctx *ctx = isl_basic_set_get_ctx(bset);` `360` `5` `  isl_mat *div;` `361` `5` `362` `5` `  div = isl_mat_alloc(ctx, bset->n_div,` `363` `5` `       1 + 1 + isl_basic_set_total_dim(bset));` `364` `5` `  if (!div)` `365` `0` `    return NULL;` `366` `5` `367` `10` `  for (i = 0; 5i < bset->n_div10; ++i5)` `368` `5` `    isl_seq_cpy(div->row[i], bset->div[i], div->n_col);` `369` `5` `370` `5` `  return div;` `371` `5` `}` `372` `373` `enum isl_lp_result isl_basic_set_opt(__isl_keep isl_basic_set *bset, int max,` `374` `  __isl_keep isl_aff *obj, isl_int *opt)` `375` `970` `{` `376` `970` `  int *exp1 = NULL;` `377` `970` `  int *exp2 = NULL;` `378` `970` `  isl_ctx *ctx;` `379` `970` `  isl_mat *bset_div = NULL;` `380` `970` `  isl_mat *div = NULL;` `381` `970` `  enum isl_lp_result res;` `382` `970` `  int bset_n_div, obj_n_div;` `383` `970` `384` `970` `  if (!bset || 970!obj970)` `385` `0` `    return isl_lp_error;` `386` `970` `387` `970` `  ctx = isl_aff_get_ctx(obj);` `388` `970` `  if (!isl_space_is_equal(bset->dim, obj->ls->dim))` `389` `0` `    isl_die(ctx, isl_error_invalid,` `390` `970` `      "spaces don't match", return isl_lp_error);` `391` `970` `  if (970!970isl_int_is_one970(obj->v->el[0]))` `392` `0` `    isl_die(ctx, isl_error_unsupported,` `393` `970` `      "expecting integer affine expression",` `394` `970` `      return isl_lp_error);` `395` `970` `396` `970` `  bset_n_div = isl_basic_set_dim(bset, isl_dim_div);` `397` `970` `  obj_n_div = isl_aff_dim(obj, isl_dim_div);` `398` `970` `  if (bset_n_div == 0 && 970obj_n_div == 0965)` `399` `965` `    return basic_set_opt(bset, max, obj, opt);` `400` `970` `401` `5` `  bset = isl_basic_set_copy(bset);` `402` `5` `  obj = isl_aff_copy(obj);` `403` `5` `404` `5` `  bset_div = extract_divs(bset);` `405` `5` `  exp1 = isl_alloc_array(ctx, int, bset_n_div);` `406` `5` `  exp2 = isl_alloc_array(ctx, int, obj_n_div);` `407` `5` `  if (!bset_div || 5(bset_n_div && 5!exp15) || (obj_n_div && 5!exp25))` `408` `0` `    goto error;` `409` `5` `410` `5` `  div = isl_merge_divs(bset_div, obj->ls->div, exp1, exp2);` `411` `5` `412` `5` `  bset = isl_basic_set_expand_divs(bset, isl_mat_copy(div), exp1);` `413` `5` `  obj = isl_aff_expand_divs(obj, isl_mat_copy(div), exp2);` `414` `5` `415` `5` `  res = basic_set_opt(bset, max, obj, opt);` `416` `5` `417` `5` `  isl_mat_free(bset_div);` `418` `5` `  isl_mat_free(div);` `419` `5` `  free(exp1);` `420` `5` `  free(exp2);` `421` `5` `  isl_basic_set_free(bset);` `422` `5` `  isl_aff_free(obj);` `423` `5` `424` `5` `  return res;` `425` `0` `error:` `426` `0` `  isl_mat_free(div);` `427` `0` `  isl_mat_free(bset_div);` `428` `0` `  free(exp1);` `429` `0` `  free(exp2);` `430` `0` `  isl_basic_set_free(bset);` `431` `0` `  isl_aff_free(obj);` `432` `0` `  return isl_lp_error;` `433` `5` `}` `434` `435` `/* Compute the minimum (maximum if max is set) of the integer affine` `436` ` * expression obj over the points in set and put the result in *opt.` `437` ` *` `438` ` * The parameters are assumed to have been aligned.` `439` ` */` `440` `static enum isl_lp_result isl_set_opt_aligned(__isl_keep isl_set *set, int max,` `441` `  __isl_keep isl_aff *obj, isl_int *opt)` `442` `963` `{` `443` `963` `  int i;` `444` `963` `  enum isl_lp_result res;` `445` `963` `  int empty = 1;` `446` `963` `  isl_int opt_i;` `447` `963` `448` `963` `  if (!set || 963!obj963)` `449` `0` `    return isl_lp_error;` `450` `963` `  if (963set->n == 0963)` `451` `0` `    return isl_lp_empty;` `452` `963` `453` `963` `  res = isl_basic_set_opt(set->p[0], max, obj, opt);` `454` `963` `  if (res == isl_lp_error || 963res == isl_lp_unbounded963)` `455` `195` `    return res;` `456` `768` `  if (768set->n == 1768)` `457` `762` `    return res;` `458` `6` `  if (6res == isl_lp_ok6)` `459` `6` `    empty = 0;` `460` `6` `461` `6` `  isl_int_init(opt_i);` `462` `12` `  for (i = 1; i < set->n12; ++i6) {6` `463` `6` `    res = isl_basic_set_opt(set->p[i], max, obj, &opt_i);` `464` `6` `    if (res == isl_lp_error || 6res == isl_lp_unbounded6) {0` `465` `0` `      isl_int_clear(opt_i);` `466` `0` `      return res;` `467` `0` `    }` `468` `6` `    if (6res == isl_lp_empty6)` `469` `1` `      continue;` `470` `5` `    empty = 0;` `471` `5` `    if (max ? 5isl_int_gt4(opt_i, *opt) : isl_int_lt1(opt_i, *opt))` `472` `1` `      isl_int_set(*opt, opt_i);` `473` `5` `  }` `474` `6` `  isl_int_clear6(opt_i);6` `475` `6` `476` `6` `  return empty ? isl_lp_empty0 : isl_lp_ok6;` `477` `6` `}` `478` `479` `/* Compute the minimum (maximum if max is set) of the integer affine` `480` ` * expression obj over the points in set and put the result in *opt.` `481` ` */` `482` `enum isl_lp_result isl_set_opt(__isl_keep isl_set *set, int max,` `483` `  __isl_keep isl_aff *obj, isl_int *opt)` `484` `963` `{` `485` `963` `  enum isl_lp_result res;` `486` `963` `  isl_bool aligned;` `487` `963` `488` `963` `  if (!set || 963!obj963)` `489` `0` `    return isl_lp_error;` `490` `963` `491` `963` `  aligned = isl_set_space_has_equal_params(set, obj->ls->dim);` `492` `963` `  if (aligned < 0)` `493` `0` `    return isl_lp_error;` `494` `963` `  if (963aligned963)` `495` `963` `    return isl_set_opt_aligned(set, max, obj, opt);` `496` `963` `497` `0` `  set = isl_set_copy(set);` `498` `0` `  obj = isl_aff_copy(obj);` `499` `0` `  set = isl_set_align_params(set, isl_aff_get_domain_space(obj));` `500` `0` `  obj = isl_aff_align_params(obj, isl_set_get_space(set));` `501` `0` `502` `0` `  res = isl_set_opt_aligned(set, max, obj, opt);` `503` `0` `504` `0` `  isl_set_free(set);` `505` `0` `  isl_aff_free(obj);` `506` `0` `507` `0` `  return res;` `508` `963` `}` `509` `510` `enum isl_lp_result isl_basic_set_max(__isl_keep isl_basic_set *bset,` `511` `  __isl_keep isl_aff *obj, isl_int *opt)` `512` `0` `{` `513` `0` `  return isl_basic_set_opt(bset, 1, obj, opt);` `514` `0` `}` `515` `516` `enum isl_lp_result isl_set_max(__isl_keep isl_set *set,` `517` `  __isl_keep isl_aff *obj, isl_int *opt)` `518` `0` `{` `519` `0` `  return isl_set_opt(set, 1, obj, opt);` `520` `0` `}` `521` `522` `enum isl_lp_result isl_set_min(__isl_keep isl_set *set,` `523` `  __isl_keep isl_aff *obj, isl_int *opt)` `524` `0` `{` `525` `0` `  return isl_set_opt(set, 0, obj, opt);` `526` `0` `}` `527` `528` `/* Convert the result of a function that returns an isl_lp_result` `529` ` * to an isl_val. The numerator of "v" is set to the optimal value` `530` ` * if lp_res is isl_lp_ok. "max" is set if a maximum was computed.` `531` ` *` `532` ` * Return "v" with denominator set to 1 if lp_res is isl_lp_ok.` `533` ` * Return NULL on error.` `534` ` * Return a NaN if lp_res is isl_lp_empty.` `535` ` * Return infinity or negative infinity if lp_res is isl_lp_unbounded,` `536` ` * depending on "max".` `537` ` */` `538` `static __isl_give isl_val *convert_lp_result(enum isl_lp_result lp_res,` `539` `  __isl_take isl_val *v, int max)` `540` `964` `{` `541` `964` `  isl_ctx *ctx;` `542` `964` `543` `964` `  if (lp_res == isl_lp_ok964) {768` `544` `768` `    isl_int_set_si(v->d, 1);` `545` `768` `    return isl_val_normalize(v);` `546` `768` `  }` `547` `196` `  ctx = isl_val_get_ctx(v);` `548` `196` `  isl_val_free(v);` `549` `196` `  if (lp_res == isl_lp_error)` `550` `0` `    return NULL;` `551` `196` `  if (196lp_res == isl_lp_empty196)` `552` `1` `    return isl_val_nan(ctx);` `553` `195` `  if (195max195)` `554` `195` `    return isl_val_infty(ctx);` `555` `195` `  else` `556` `0` `    return isl_val_neginfty(ctx);` `557` `195` `}` `558` `559` `/* Return the minimum (maximum if max is set) of the integer affine` `560` ` * expression "obj" over the points in "bset".` `561` ` *` `562` ` * Return infinity or negative infinity if the optimal value is unbounded and` `563` ` * NaN if "bset" is empty.` `564` ` *` `565` ` * Call isl_basic_set_opt and translate the results.` `566` ` */` `567` `__isl_give isl_val *isl_basic_set_opt_val(__isl_keep isl_basic_set *bset,` `568` `  int max, __isl_keep isl_aff *obj)` `569` `1` `{` `570` `1` `  isl_ctx *ctx;` `571` `1` `  isl_val *res;` `572` `1` `  enum isl_lp_result lp_res;` `573` `1` `574` `1` `  if (!bset || 1!obj1)` `575` `0` `    return NULL;` `576` `1` `577` `1` `  ctx = isl_aff_get_ctx(obj);` `578` `1` `  res = isl_val_alloc(ctx);` `579` `1` `  if (!res)` `580` `0` `    return NULL;` `581` `1` `  lp_res = isl_basic_set_opt(bset, max, obj, &res->n);` `582` `1` `  return convert_lp_result(lp_res, res, max);` `583` `1` `}` `584` `585` `/* Return the maximum of the integer affine` `586` ` * expression "obj" over the points in "bset".` `587` ` *` `588` ` * Return infinity or negative infinity if the optimal value is unbounded and` `589` ` * NaN if "bset" is empty.` `590` ` */` `591` `__isl_give isl_val *isl_basic_set_max_val(__isl_keep isl_basic_set *bset,` `592` `  __isl_keep isl_aff *obj)` `593` `1` `{` `594` `1` `  return isl_basic_set_opt_val(bset, 1, obj);` `595` `1` `}` `596` `597` `/* Return the minimum (maximum if max is set) of the integer affine` `598` ` * expression "obj" over the points in "set".` `599` ` *` `600` ` * Return infinity or negative infinity if the optimal value is unbounded and` `601` ` * NaN if "set" is empty.` `602` ` *` `603` ` * Call isl_set_opt and translate the results.` `604` ` */` `605` `__isl_give isl_val *isl_set_opt_val(__isl_keep isl_set *set, int max,` `606` `  __isl_keep isl_aff *obj)` `607` `963` `{` `608` `963` `  isl_ctx *ctx;` `609` `963` `  isl_val *res;` `610` `963` `  enum isl_lp_result lp_res;` `611` `963` `612` `963` `  if (!set || 963!obj963)` `613` `0` `    return NULL;` `614` `963` `615` `963` `  ctx = isl_aff_get_ctx(obj);` `616` `963` `  res = isl_val_alloc(ctx);` `617` `963` `  if (!res)` `618` `0` `    return NULL;` `619` `963` `  lp_res = isl_set_opt(set, max, obj, &res->n);` `620` `963` `  return convert_lp_result(lp_res, res, max);` `621` `963` `}` `622` `623` `/* Return the minimum of the integer affine` `624` ` * expression "obj" over the points in "set".` `625` ` *` `626` ` * Return infinity or negative infinity if the optimal value is unbounded and` `627` ` * NaN if "set" is empty.` `628` ` */` `629` `__isl_give isl_val *isl_set_min_val(__isl_keep isl_set *set,` `630` `  __isl_keep isl_aff *obj)` `631` `2` `{` `632` `2` `  return isl_set_opt_val(set, 0, obj);` `633` `2` `}` `634` `635` `/* Return the maximum of the integer affine` `636` ` * expression "obj" over the points in "set".` `637` ` *` `638` ` * Return infinity or negative infinity if the optimal value is unbounded and` `639` ` * NaN if "set" is empty.` `640` ` */` `641` `__isl_give isl_val *isl_set_max_val(__isl_keep isl_set *set,` `642` `  __isl_keep isl_aff *obj)` `643` `961` `{` `644` `961` `  return isl_set_opt_val(set, 1, obj);` `645` `961` `}` `646` `647` `/* Return the optimum (min or max depending on "max") of "v1" and "v2",` `648` ` * where either may be NaN, signifying an uninitialized value.` `649` ` * That is, if either is NaN, then return the other one.` `650` ` */` `651` `static __isl_give isl_val *val_opt(__isl_take isl_val *v1,` `652` `  __isl_take isl_val *v2, int max)` `653` `0` `{` `654` `0` `  if (!v1 || 0!v20)` `655` `0` `    goto error;` `656` `0` `  if (0isl_val_is_nan(v1)0) {0` `657` `0` `    isl_val_free(v1);` `658` `0` `    return v2;` `659` `0` `  }` `660` `0` `  if (0isl_val_is_nan(v2)0) {0` `661` `0` `    isl_val_free(v2);` `662` `0` `    return v1;` `663` `0` `  }` `664` `0` `  if (0max0)` `665` `0` `    return isl_val_max(v1, v2);` `666` `0` `  else` `667` `0` `    return isl_val_min(v1, v2);` `668` `0` `error:` `669` `0` `  isl_val_free(v1);` `670` `0` `  isl_val_free(v2);` `671` `0` `  return NULL;` `672` `0` `}` `673` `674` `/* Internal data structure for isl_set_opt_pw_aff.` `675` ` *` `676` ` * "max" is set if the maximum should be computed.` `677` ` * "set" is the set over which the optimum should be computed.` `678` ` * "res" contains the current optimum and is initialized to NaN.` `679` ` */` `680` `struct isl_set_opt_data {` `681` `  int max;` `682` `  isl_set *set;` `683` `684` `  isl_val *res;` `685` `};` `686` `687` `/* Update the optimum in data->res with respect to the affine function` `688` ` * "aff" defined over "set".` `689` ` */` `690` `static isl_stat piece_opt(__isl_take isl_set *set, __isl_take isl_aff *aff,` `691` `  void *user)` `692` `0` `{` `693` `0` `  struct isl_set_opt_data *data = user;` `694` `0` `  isl_val *opt;` `695` `0` `696` `0` `  set = isl_set_intersect(set, isl_set_copy(data->set));` `697` `0` `  opt = isl_set_opt_val(set, data->max, aff);` `698` `0` `  isl_set_free(set);` `699` `0` `  isl_aff_free(aff);` `700` `0` `701` `0` `  data->res = val_opt(data->res, opt, data->max);` `702` `0` `  if (!data->res)` `703` `0` `    return isl_stat_error;` `704` `0` `705` `0` `  return isl_stat_ok;` `706` `0` `}` `707` `708` `/* Return the minimum (maximum if "max" is set) of the integer piecewise affine` `709` ` * expression "obj" over the points in "set".` `710` ` *` `711` ` * Return infinity or negative infinity if the optimal value is unbounded and` `712` ` * NaN if the intersection of "set" with the domain of "obj" is empty.` `713` ` *` `714` ` * Initialize the result to NaN and then update it for each of the pieces` `715` ` * in "obj".` `716` ` */` `717` `static __isl_give isl_val *isl_set_opt_pw_aff(__isl_keep isl_set *set, int max,` `718` `  __isl_keep isl_pw_aff *obj)` `719` `0` `{` `720` `0` `  struct isl_set_opt_data data = { max, set };` `721` `0` `722` `0` `  data.res = isl_val_nan(isl_set_get_ctx(set));` `723` `0` `  if (isl_pw_aff_foreach_piece(obj, &piece_opt, &data) < 0)` `724` `0` `    return isl_val_free(data.res);` `725` `0` `726` `0` `  return data.res;` `727` `0` `}` `728` `729` `/* Internal data structure for isl_union_set_opt_union_pw_aff.` `730` ` *` `731` ` * "max" is set if the maximum should be computed.` `732` ` * "obj" is the objective function that needs to be optimized.` `733` ` * "res" contains the current optimum and is initialized to NaN.` `734` ` */` `735` `struct isl_union_set_opt_data {` `736` `  int max;` `737` `  isl_union_pw_aff *obj;` `738` `739` `  isl_val *res;` `740` `};` `741` `742` `/* Update the optimum in data->res with the optimum over "set".` `743` ` * Do so by first extracting the matching objective function` `744` ` * from data->obj.` `745` ` */` `746` `static isl_stat set_opt(__isl_take isl_set *set, void *user)` `747` `0` `{` `748` `0` `  struct isl_union_set_opt_data *data = user;` `749` `0` `  isl_space *space;` `750` `0` `  isl_pw_aff *pa;` `751` `0` `  isl_val *opt;` `752` `0` `753` `0` `  space = isl_set_get_space(set);` `754` `0` `  space = isl_space_from_domain(space);` `755` `0` `  space = isl_space_add_dims(space, isl_dim_out, 1);` `756` `0` `  pa = isl_union_pw_aff_extract_pw_aff(data->obj, space);` `757` `0` `  opt = isl_set_opt_pw_aff(set, data->max, pa);` `758` `0` `  isl_pw_aff_free(pa);` `759` `0` `  isl_set_free(set);` `760` `0` `761` `0` `  data->res = val_opt(data->res, opt, data->max);` `762` `0` `  if (!data->res)` `763` `0` `    return isl_stat_error;` `764` `0` `765` `0` `  return isl_stat_ok;` `766` `0` `}` `767` `768` `/* Return the minimum (maximum if "max" is set) of the integer piecewise affine` `769` ` * expression "obj" over the points in "uset".` `770` ` *` `771` ` * Return infinity or negative infinity if the optimal value is unbounded and` `772` ` * NaN if the intersection of "uset" with the domain of "obj" is empty.` `773` ` *` `774` ` * Initialize the result to NaN and then update it for each of the sets` `775` ` * in "uset".` `776` ` */` `777` `static __isl_give isl_val *isl_union_set_opt_union_pw_aff(` `778` `  __isl_keep isl_union_set *uset, int max,` `779` `  __isl_keep isl_union_pw_aff *obj)` `780` `0` `{` `781` `0` `  struct isl_union_set_opt_data data = { max, obj };` `782` `0` `783` `0` `  data.res = isl_val_nan(isl_union_set_get_ctx(uset));` `784` `0` `  if (isl_union_set_foreach_set(uset, &set_opt, &data) < 0)` `785` `0` `    return isl_val_free(data.res);` `786` `0` `787` `0` `  return data.res;` `788` `0` `}` `789` `790` `/* Return a list of minima (maxima if "max" is set) over the points in "uset"` `791` ` * for each of the expressions in "obj".` `792` ` *` `793` ` * An element in the list is infinity or negative infinity if the optimal` `794` ` * value of the corresponding expression is unbounded and` `795` ` * NaN if the intersection of "uset" with the domain of the expression` `796` ` * is empty.` `797` ` *` `798` ` * Iterate over all the expressions in "obj" and collect the results.` `799` ` */` `800` `static __isl_give isl_multi_val *isl_union_set_opt_multi_union_pw_aff(` `801` `  __isl_keep isl_union_set *uset, int max,` `802` `  __isl_keep isl_multi_union_pw_aff *obj)` `803` `0` `{` `804` `0` `  int i, n;` `805` `0` `  isl_multi_val *mv;` `806` `0` `807` `0` `  if (!uset || 0!obj0)` `808` `0` `    return NULL;` `809` `0` `810` `0` `  n = isl_multi_union_pw_aff_dim(obj, isl_dim_set);` `811` `0` `  mv = isl_multi_val_zero(isl_multi_union_pw_aff_get_space(obj));` `812` `0` `813` `0` `  for (i = 0; i < n0; ++i0) {0` `814` `0` `    isl_val *v;` `815` `0` `    isl_union_pw_aff *upa;` `816` `0` `817` `0` `    upa = isl_multi_union_pw_aff_get_union_pw_aff(obj, i);` `818` `0` `    v = isl_union_set_opt_union_pw_aff(uset, max, upa);` `819` `0` `    isl_union_pw_aff_free(upa);` `820` `0` `    mv = isl_multi_val_set_val(mv, i, v);` `821` `0` `  }` `822` `0` `823` `0` `  return mv;` `824` `0` `}` `825` `826` `/* Return a list of minima over the points in "uset"` `827` ` * for each of the expressions in "obj".` `828` ` *` `829` ` * An element in the list is infinity or negative infinity if the optimal` `830` ` * value of the corresponding expression is unbounded and` `831` ` * NaN if the intersection of "uset" with the domain of the expression` `832` ` * is empty.` `833` ` */` `834` `__isl_give isl_multi_val *isl_union_set_min_multi_union_pw_aff(` `835` `  __isl_keep isl_union_set *uset, __isl_keep isl_multi_union_pw_aff *obj)` `836` `0` `{` `837` `0` `  return isl_union_set_opt_multi_union_pw_aff(uset, 0, obj);` `838` `0` `}`