/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_pw_union_opt.c

Source (jump to first uncovered line)
/*
 * Copyright 2011      INRIA Saclay
 * Copyright 2012      Ecole Normale Superieure
 *
 * Use of this software is governed by the MIT license
 *
 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
 * 91893 Orsay, France
 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
 */

#include <isl_pw_macro.h>

/* Given a function "cmp" that returns the set of elements where
 * "el1" is "better" than "el2", return this set.
 */
static __isl_give isl_set *FN(PW,better)(__isl_keep EL *el1, __isl_keep EL *el2,
  __isl_give isl_set *(*cmp)(__isl_take EL *el1, __isl_take EL *el2))
{
  return cmp(FN(EL,copy)(el1), FN(EL,copy)(el2));
}

/* Return a list containing the domains of the pieces of "pw".
 */
static __isl_give isl_set_list *FN(PW,extract_domains)(__isl_keep PW *pw)
{
  int i;
  isl_ctx *ctx;
  isl_set_list *list;

  if (!pw)
    return NULL;
  ctx = FN(PW,get_ctx)(pw);
  list = isl_set_list_alloc(ctx, pw->n);
  for (i = 0; i < pw->n; ++i6.61k)
    list = isl_set_list_add(list, isl_set_copy(pw->p[i].set));

  return list;
}

/* Given sets B ("set"), C ("better") and A' ("out"), return
 *
 *  (B \cap C) \cup ((B \setminus C) \setminus A')
 */
static __isl_give isl_set *FN(PW,better_or_out)(__isl_take isl_set *set,
  __isl_take isl_set *better, __isl_take isl_set *out)
{
  isl_set *set_better, *set_out;

  set_better = isl_set_intersect(isl_set_copy(set), isl_set_copy(better));
  set_out = isl_set_subtract(isl_set_subtract(set, better), out);

  return isl_set_union(set_better, set_out);
}

/* Given sets A ("set"), C ("better") and B' ("out"), return
 *
 *  (A \setminus C) \cup ((A \cap C) \setminus B')
 */
static __isl_give isl_set *FN(PW,worse_or_out)(__isl_take isl_set *set,
  __isl_take isl_set *better, __isl_take isl_set *out)
{
  isl_set *set_worse, *set_out;

  set_worse = isl_set_subtract(isl_set_copy(set), isl_set_copy(better));
  set_out = isl_set_subtract(isl_set_intersect(set, better), out);

  return isl_set_union(set_worse, set_out);
}

/* Given two piecewise expressions "pw1" and "pw2", replace their domains
 * by the sets in "list1" and "list2" and combine the results into
 * a single piecewise expression.
 * The pieces of "pw1" and "pw2" are assumed to have been sorted
 * according to the function value expressions.
 * The pieces of the result are also sorted in this way.
 *
 * Run through the pieces of "pw1" and "pw2" in order until they
 * have both been exhausted, picking the piece from "pw1" or "pw2"
 * depending on which should come first, together with the corresponding
 * domain from "list1" or "list2".  In cases where the next pieces
 * in both "pw1" and "pw2" have the same function value expression,
 * construct only a single piece in the result with as domain
 * the union of the domains in "list1" and "list2".
 */
static __isl_give PW *FN(PW,merge)(__isl_take PW *pw1, __isl_take PW *pw2,
  __isl_take isl_set_list *list1, __isl_take isl_set_list *list2)
{
  int i, j;
  PW *res;

  if (!pw1 || !pw2)
    goto error;

  res = FN(PW,alloc_size)(isl_space_copy(pw1->dim), pw1->n + pw2->n);

  i = 0; j = 0;
  while (i < pw1->n || j < pw2->n2.43k) {
    int cmp;
    isl_set *set;
    EL *el;

    if (i < pw1->n && j < pw2->n5.37k)
      cmp = FN(EL,plain_cmp)(pw1->p[i].FIELD,
            pw2->p[j].FIELD);
    else
      cmp = i < pw1->n ? -11.77k : 1693;

    if (cmp < 0) {
      set = isl_set_list_get_set(list1, i);
      el = FN(EL,copy)(pw1->p[i].FIELD);
      ++i;
    } else if (1.84kcmp > 01.84k) {
      set = isl_set_list_get_set(list2, j);
      el = FN(EL,copy)(pw2->p[j].FIELD);
      ++j;
    } else {
      set = isl_set_union(isl_set_list_get_set(list1, i),
              isl_set_list_get_set(list2, j));
      el = FN(EL,copy)(pw1->p[i].FIELD);
      ++i;
      ++j;
    }
    res = FN(PW,add_piece)(res, set, el);
  }

  isl_set_list_free(list1);
  isl_set_list_free(list2);
  FN(PW,free)(pw1);
  FN(PW,free)(pw2);
  return res;
error:
  isl_set_list_free(list1);
  isl_set_list_free(list2);
  FN(PW,free)(pw1);
  FN(PW,free)(pw2);
  return NULL;
}

/* Given a function "cmp" that returns the set of elements where
 * "el1" is "better" than "el2", return a piecewise
 * expression defined on the union of the definition domains
 * of "pw1" and "pw2" that maps to the "best" of "pw1" and
 * "pw2" on each cell.  If only one of the two input functions
 * is defined on a given cell, then it is considered the best.
 *
 * Run through all pairs of pieces in "pw1" and "pw2".
 * If the domains of these pieces intersect, then the intersection
 * needs to be distributed over the two pieces based on "cmp".
 * Let C be the set where the piece from "pw2" is better (according to "cmp")
 * than the piece from "pw1".  Let A be the domain of the piece from "pw1" and
 * B the domain of the piece from "pw2".
 *
 * The elements in C need to be removed from A, except for those parts
 * that lie outside of B.  That is,
 *
 *  A <- (A \setminus C) \cup ((A \cap C) \setminus B')
 *
 * Conversely, the elements in B need to be restricted to C, except
 * for those parts that lie outside of A.  That is
 *
 *  B <- (B \cap C) \cup ((B \setminus C) \setminus A')
 *
 * Since all pairs of pieces are considered, the domains are updated
 * several times.  A and B refer to these updated domains
 * (kept track of in "list1" and "list2"), while A' and B' refer
 * to the original domains of the pieces.  It is safe to use these
 * original domains because the difference between, say, A' and A is
 * the domains of pw2-pieces that have been removed before and
 * those domains are disjoint from B.  A' is used instead of A
 * because the continued updating of A may result in this domain
 * getting broken up into more disjuncts.
 *
 * After the updated domains have been computed, the result is constructed
 * from "pw1", "pw2", "list1" and "list2".  If there are any pieces
 * in "pw1" and "pw2" with the same function value expression, then
 * they are combined into a single piece in the result.
 * In order to be able to do this efficiently, the pieces of "pw1" and
 * "pw2" are first sorted according to their function value expressions.
 */
static __isl_give PW *FN(PW,union_opt_cmp)(
  __isl_take PW *pw1, __isl_take PW *pw2,
  __isl_give isl_set *(*cmp)(__isl_take EL *el1, __isl_take EL *el2))
{
  int i, j;
  PW *res = NULL;
  isl_ctx *ctx;
  isl_set *set = NULL;
  isl_set_list *list1 = NULL, *list2 = NULL;

  if (!pw1 || !pw2)
    goto error;

  ctx = isl_space_get_ctx(pw1->dim);
  if (!isl_space_is_equal(pw1->dim, pw2->dim))
    isl_die0(ctx, isl_error_invalid,
      "arguments should live in the same space", goto error);

  if (FN(PW,is_empty)(pw1)) {
    FN(PW,free)(pw1);
    return pw2;
  }

  if (FN(PW,is_empty)(pw2)) {
    FN(PW,free)(pw2);
    return pw1;
  }

  pw1 = FN(PW,sort)(pw1);
  pw2 = FN(PW,sort)(pw2);
  if (!pw1 || !pw2)
    goto error;

  list1 = FN(PW,extract_domains)(pw1);
  list2 = FN(PW,extract_domains)(pw2);

  for (i = 0; i < pw1->n; ++i4.76k) {
    for (j = 0; j < pw2->n; ++j5.12k) {
      isl_bool disjoint;
      isl_set *better, *set_i, *set_j;

      disjoint = isl_set_is_disjoint(pw1->p[i].set,
              pw2->p[j].set);
      if (disjoint < 0)
        goto error;
      if (disjoint)
        continue;
      better = FN(PW,better)(pw2->p[j].FIELD,
            pw1->p[i].FIELD, cmp);
      set_i = isl_set_list_get_set(list1, i);
      set_j = isl_set_copy(pw2->p[j].set);
      set_i = FN(PW,worse_or_out)(set_i,
            isl_set_copy(better), set_j);
      list1 = isl_set_list_set_set(list1, i, set_i);
      set_i = isl_set_copy(pw1->p[i].set);
      set_j = isl_set_list_get_set(list2, j);
      set_j = FN(PW,better_or_out)(set_j, better, set_i);
      list2 = isl_set_list_set_set(list2, j, set_j);
    }
  }

  res = FN(PW,merge)(pw1, pw2, list1, list2);

  return res;
error:
  isl_set_list_free(list1);
  isl_set_list_free(list2);
  FN(PW,free)(pw1);
  FN(PW,free)(pw2);
  isl_set_free(set);
  return FN(PW,free)(res);
}

Coverage Report

Created: 2019-07-24 05:18