lib/External/isl/isl_pw_union_opt.c - llvm-project/polly - Git at Google

 /*
  * Copyright 2011      INRIA Saclay
  * Copyright 2012      Ecole Normale Superieure
  * Copyright 2020      Cerebras Systems
  *
  * 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
  * and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA
  */

 #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; ++i)
 		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);
 }

 /* Internal data structure used by isl_pw_*_union_opt_cmp
  * that keeps track of a piecewise expression with updated cells.
  * "pw" holds the original piecewise expression.
  * "list" holds the updated cells.
  */
 S(PW,union_opt_cmp_data) {
 	PW *pw;
 	isl_set_list *cell;
 };

 /* Free all memory allocated for "data".
  */
 static void FN(PW,union_opt_cmp_data_clear)(S(PW,union_opt_cmp_data) *data)
 {
 	isl_set_list_free(data->cell);
 	FN(PW,free)(data->pw);
 }

 /* Given (potentially) updated cells "i" of data_i->pw and "j" of data_j->pw and
  * a set "better" where the piece from data_j->pw is better
  * than the piece from data_i->pw,
  * (further) update the specified cells such that only the better elements
  * remain on the (non-empty) intersection.
  *
  * Let C be the set "better".
  * Let A be the cell data_i->cell[i] and B the cell data_j->cell[j].
  *
  * 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 data_i->cell[i] and data_j->cell[j]), 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.
  */
 static isl_stat FN(PW,union_opt_cmp_split)(S(PW,union_opt_cmp_data) *data_i,
 	int i, S(PW,union_opt_cmp_data) *data_j, int j,
 	__isl_take isl_set *better)
 {
 	isl_set *set_i, *set_j;

 	set_i = isl_set_list_get_set(data_i->cell, i);
 	set_j = FN(PW,get_domain_at)(data_j->pw, j);
 	set_i = FN(PW,worse_or_out)(set_i, isl_set_copy(better), set_j);
 	data_i->cell = isl_set_list_set_set(data_i->cell, i, set_i);
 	set_i = FN(PW,get_domain_at)(data_i->pw, i);
 	set_j = isl_set_list_get_set(data_j->cell, j);
 	set_j = FN(PW,better_or_out)(set_j, better, set_i);
 	data_j->cell = isl_set_list_set_set(data_j->cell, j, set_j);

 	return isl_stat_ok;
 }

 /* Given (potentially) updated cells "i" of data_i->pw and "j" of data_j->pw and
  * a function "cmp" that returns the set of elements where
  * "el1" is "better" than "el2",
  * (further) update the specified cells such that only the "better" elements
  * remain on the (non-empty) intersection.
  */
 static isl_stat FN(PW,union_opt_cmp_pair)(S(PW,union_opt_cmp_data) *data_i,
 	int i, S(PW,union_opt_cmp_data) *data_j, int j,
 	__isl_give isl_set *(*cmp)(__isl_take EL *el1, __isl_take EL *el2))
 {
 	isl_set *better;
 	EL *el_i, *el_j;

 	el_i = FN(PW,peek_base_at)(data_i->pw, i);
 	el_j = FN(PW,peek_base_at)(data_j->pw, j);
 	better = FN(PW,better)(el_j, el_i, cmp);
 	return FN(PW,union_opt_cmp_split)(data_i, i, data_j, j, better);
 }

 /* Given (potentially) updated cells "i" of data_i->pw and "j" of data_j->pw and
  * a function "cmp" that returns the set of elements where
  * "el1" is "better" than "el2",
  * (further) update the specified cells such that only the "better" elements
  * remain on the (non-empty) intersection.
  *
  * The base computation is performed by isl_pw_*_union_opt_cmp_pair,
  * which splits the cells according to the set of elements
  * where the piece from data_j->pw is better than the piece from data_i->pw.
  *
  * In some cases, there may be a subset of the intersection
  * where both pieces have the same value and can therefore
  * both be considered to be "better" than the other.
  * This can result in unnecessary splitting on this subset.
  * Avoid some of these cases by checking whether
  * data_i->pw is always better than data_j->pw on the intersection.
  * In particular, do this for the special case where this intersection
  * is equal to the cell "j" and data_i->pw is better on its entire cell.
  *
  * Similarly, if data_i->pw is never better than data_j->pw,
  * then no splitting will occur and there is no need to check
  * where data_j->pw is better than data_i->pw.
  */
 static isl_stat FN(PW,union_opt_cmp_two)(S(PW,union_opt_cmp_data) *data_i,
 	int i, S(PW,union_opt_cmp_data) *data_j, int j,
 	__isl_give isl_set *(*cmp)(__isl_take EL *el1, __isl_take EL *el2))
 {
 	isl_bool is_subset, is_empty;
 	isl_set *better, *set_i, *set_j;
 	EL *el_i, *el_j;

 	set_i = FN(PW,peek_domain_at)(data_i->pw, i);
 	set_j = FN(PW,peek_domain_at)(data_j->pw, j);
 	is_subset = isl_set_is_subset(set_j, set_i);
 	if (is_subset < 0)
 		return isl_stat_error;
 	if (!is_subset)
 		return FN(PW,union_opt_cmp_pair)(data_i, i, data_j, j, cmp);

 	el_i = FN(PW,peek_base_at)(data_i->pw, i);
 	el_j = FN(PW,peek_base_at)(data_j->pw, j);
 	better = FN(PW,better)(el_i, el_j, cmp);
 	is_empty = isl_set_is_empty(better);
 	if (is_empty >= 0 && is_empty)
 		return FN(PW,union_opt_cmp_split)(data_j, j, data_i, i, better);
 	is_subset = isl_set_is_subset(set_i, better);
 	if (is_subset >= 0 && is_subset)
 		return FN(PW,union_opt_cmp_split)(data_j, j, data_i, i, better);
 	isl_set_free(better);
 	if (is_empty < 0 || is_subset < 0)
 		return isl_stat_error;

 	return FN(PW,union_opt_cmp_pair)(data_i, i, data_j, j, cmp);
 }

 /* Given two piecewise expressions data1->pw and data2->pw, replace
  * their domains
  * by the sets in data1->cell and data2->cell and combine the results into
  * a single piecewise expression.
  * The pieces of data1->pw and data2->pw 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 data1->pw and data2->pw in order until they
  * have both been exhausted, picking the piece from data1->pw or data2->pw
  * depending on which should come first, together with the corresponding
  * domain from data1->cell or data2->cell.  In cases where the next pieces
  * in both data1->pw and data2->pw have the same function value expression,
  * construct only a single piece in the result with as domain
  * the union of the domains in data1->cell and data2->cell.
  */
 static __isl_give PW *FN(PW,merge)(S(PW,union_opt_cmp_data) *data1,
 	S(PW,union_opt_cmp_data) *data2)
 {
 	int i, j;
 	PW *res;
 	PW *pw1 = data1->pw;
 	PW *pw2 = data2->pw;
 	isl_set_list *list1 = data1->cell;
 	isl_set_list *list2 = data2->cell;

 	if (!pw1 || !pw2)
 		return NULL;

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

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

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

 		if (cmp < 0) {
 			set = isl_set_list_get_set(list1, i);
 			el = FN(EL,copy)(pw1->p[i].FIELD);
 			++i;
 		} else if (cmp > 0) {
 			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);
 	}

 	return res;
 }

 /* 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".
  *
  * After the updated domains have been computed, the result is constructed
  * from "pw1", "pw2", data[0].cell and data[1].cell.  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))
 {
 	S(PW,union_opt_cmp_data) data[2] = { { pw1, NULL }, { pw2, NULL } };
 	int i, j;
 	isl_size n1, n2;
 	PW *res = NULL;
 	isl_ctx *ctx;

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

 	ctx = isl_space_get_ctx(pw1->dim);
 	if (!isl_space_is_equal(pw1->dim, pw2->dim))
 		isl_die(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;
 	}

 	for (i = 0; i < 2; ++i) {
 		data[i].pw = FN(PW,sort_unique)(data[i].pw);
 		data[i].cell = FN(PW,extract_domains)(data[i].pw);
 	}

 	n1 = FN(PW,n_piece)(data[0].pw);
 	n2 = FN(PW,n_piece)(data[1].pw);
 	if (n1 < 0 || n2 < 0)
 		goto error;
 	for (i = 0; i < n1; ++i) {
 		for (j = 0; j < n2; ++j) {
 			isl_bool disjoint;
 			isl_set *set_i, *set_j;

 			set_i = FN(PW,peek_domain_at)(data[0].pw, i);
 			set_j = FN(PW,peek_domain_at)(data[1].pw, j);
 			disjoint = isl_set_is_disjoint(set_i, set_j);
 			if (disjoint < 0)
 				goto error;
 			if (disjoint)
 				continue;
 			if (FN(PW,union_opt_cmp_two)(&data[0], i,
 							&data[1], j, cmp) < 0)
 				goto error;
 		}
 	}

 	res = FN(PW,merge)(&data[0], &data[1]);
 	for (i = 0; i < 2; ++i)
 		FN(PW,union_opt_cmp_data_clear)(&data[i]);

 	return res;
 error:
 	for (i = 0; i < 2; ++i)
 		FN(PW,union_opt_cmp_data_clear)(&data[i]);
 	return FN(PW,free)(res);
 }
	/*
	* Copyright 2011 INRIA Saclay
	* Copyright 2012 Ecole Normale Superieure
	* Copyright 2020 Cerebras Systems
	*
	* 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
	* and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA
	*/

	#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; ++i)
	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);
	}

	/* Internal data structure used by isl_pw_*_union_opt_cmp
	* that keeps track of a piecewise expression with updated cells.
	* "pw" holds the original piecewise expression.
	* "list" holds the updated cells.
	*/
	S(PW,union_opt_cmp_data) {
	PW *pw;
	isl_set_list *cell;
	};

	/* Free all memory allocated for "data".
	*/
	static void FN(PW,union_opt_cmp_data_clear)(S(PW,union_opt_cmp_data) *data)
	{
	isl_set_list_free(data->cell);
	FN(PW,free)(data->pw);
	}

	/* Given (potentially) updated cells "i" of data_i->pw and "j" of data_j->pw and
	* a set "better" where the piece from data_j->pw is better
	* than the piece from data_i->pw,
	* (further) update the specified cells such that only the better elements
	* remain on the (non-empty) intersection.
	*
	* Let C be the set "better".
	* Let A be the cell data_i->cell[i] and B the cell data_j->cell[j].
	*
	* 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 data_i->cell[i] and data_j->cell[j]), 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.
	*/
	static isl_stat FN(PW,union_opt_cmp_split)(S(PW,union_opt_cmp_data) *data_i,
	int i, S(PW,union_opt_cmp_data) *data_j, int j,
	__isl_take isl_set *better)
	{
	isl_set set_i, set_j;

	set_i = isl_set_list_get_set(data_i->cell, i);
	set_j = FN(PW,get_domain_at)(data_j->pw, j);
	set_i = FN(PW,worse_or_out)(set_i, isl_set_copy(better), set_j);
	data_i->cell = isl_set_list_set_set(data_i->cell, i, set_i);
	set_i = FN(PW,get_domain_at)(data_i->pw, i);
	set_j = isl_set_list_get_set(data_j->cell, j);
	set_j = FN(PW,better_or_out)(set_j, better, set_i);
	data_j->cell = isl_set_list_set_set(data_j->cell, j, set_j);

	return isl_stat_ok;
	}

	/* Given (potentially) updated cells "i" of data_i->pw and "j" of data_j->pw and
	* a function "cmp" that returns the set of elements where
	* "el1" is "better" than "el2",
	* (further) update the specified cells such that only the "better" elements
	* remain on the (non-empty) intersection.
	*/
	static isl_stat FN(PW,union_opt_cmp_pair)(S(PW,union_opt_cmp_data) *data_i,
	int i, S(PW,union_opt_cmp_data) *data_j, int j,
	__isl_give isl_set (cmp)(__isl_take EL el1, __isl_take EL el2))
	{
	isl_set *better;
	EL el_i, el_j;

	el_i = FN(PW,peek_base_at)(data_i->pw, i);
	el_j = FN(PW,peek_base_at)(data_j->pw, j);
	better = FN(PW,better)(el_j, el_i, cmp);
	return FN(PW,union_opt_cmp_split)(data_i, i, data_j, j, better);
	}

	/* Given (potentially) updated cells "i" of data_i->pw and "j" of data_j->pw and
	* a function "cmp" that returns the set of elements where
	* "el1" is "better" than "el2",
	* (further) update the specified cells such that only the "better" elements
	* remain on the (non-empty) intersection.
	*
	* The base computation is performed by isl_pw_*_union_opt_cmp_pair,
	* which splits the cells according to the set of elements
	* where the piece from data_j->pw is better than the piece from data_i->pw.
	*
	* In some cases, there may be a subset of the intersection
	* where both pieces have the same value and can therefore
	* both be considered to be "better" than the other.
	* This can result in unnecessary splitting on this subset.
	* Avoid some of these cases by checking whether
	* data_i->pw is always better than data_j->pw on the intersection.
	* In particular, do this for the special case where this intersection
	* is equal to the cell "j" and data_i->pw is better on its entire cell.
	*
	* Similarly, if data_i->pw is never better than data_j->pw,
	* then no splitting will occur and there is no need to check
	* where data_j->pw is better than data_i->pw.
	*/
	static isl_stat FN(PW,union_opt_cmp_two)(S(PW,union_opt_cmp_data) *data_i,
	int i, S(PW,union_opt_cmp_data) *data_j, int j,
	__isl_give isl_set (cmp)(__isl_take EL el1, __isl_take EL el2))
	{
	isl_bool is_subset, is_empty;
	isl_set better, set_i, *set_j;
	EL el_i, el_j;

	set_i = FN(PW,peek_domain_at)(data_i->pw, i);
	set_j = FN(PW,peek_domain_at)(data_j->pw, j);
	is_subset = isl_set_is_subset(set_j, set_i);
	if (is_subset < 0)
	return isl_stat_error;
	if (!is_subset)
	return FN(PW,union_opt_cmp_pair)(data_i, i, data_j, j, cmp);

	el_i = FN(PW,peek_base_at)(data_i->pw, i);
	el_j = FN(PW,peek_base_at)(data_j->pw, j);
	better = FN(PW,better)(el_i, el_j, cmp);
	is_empty = isl_set_is_empty(better);
	if (is_empty >= 0 && is_empty)
	return FN(PW,union_opt_cmp_split)(data_j, j, data_i, i, better);
	is_subset = isl_set_is_subset(set_i, better);
	if (is_subset >= 0 && is_subset)
	return FN(PW,union_opt_cmp_split)(data_j, j, data_i, i, better);
	isl_set_free(better);
	if (is_empty < 0 \|\| is_subset < 0)
	return isl_stat_error;

	return FN(PW,union_opt_cmp_pair)(data_i, i, data_j, j, cmp);
	}

	/* Given two piecewise expressions data1->pw and data2->pw, replace
	* their domains
	* by the sets in data1->cell and data2->cell and combine the results into
	* a single piecewise expression.
	* The pieces of data1->pw and data2->pw 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 data1->pw and data2->pw in order until they
	* have both been exhausted, picking the piece from data1->pw or data2->pw
	* depending on which should come first, together with the corresponding
	* domain from data1->cell or data2->cell. In cases where the next pieces
	* in both data1->pw and data2->pw have the same function value expression,
	* construct only a single piece in the result with as domain
	* the union of the domains in data1->cell and data2->cell.
	*/
	static __isl_give PW FN(PW,merge)(S(PW,union_opt_cmp_data) data1,
	S(PW,union_opt_cmp_data) *data2)
	{
	int i, j;
	PW *res;
	PW *pw1 = data1->pw;
	PW *pw2 = data2->pw;
	isl_set_list *list1 = data1->cell;
	isl_set_list *list2 = data2->cell;

	if (!pw1 \|\| !pw2)
	return NULL;

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

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

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

	if (cmp < 0) {
	set = isl_set_list_get_set(list1, i);
	el = FN(EL,copy)(pw1->p[i].FIELD);
	++i;
	} else if (cmp > 0) {
	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);
	}

	return res;
	}

	/* 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".
	*
	* After the updated domains have been computed, the result is constructed
	* from "pw1", "pw2", data[0].cell and data[1].cell. 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))
	{
	S(PW,union_opt_cmp_data) data[2] = { { pw1, NULL }, { pw2, NULL } };
	int i, j;
	isl_size n1, n2;
	PW *res = NULL;
	isl_ctx *ctx;

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

	ctx = isl_space_get_ctx(pw1->dim);
	if (!isl_space_is_equal(pw1->dim, pw2->dim))
	isl_die(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;
	}

	for (i = 0; i < 2; ++i) {
	data[i].pw = FN(PW,sort_unique)(data[i].pw);
	data[i].cell = FN(PW,extract_domains)(data[i].pw);
	}

	n1 = FN(PW,n_piece)(data[0].pw);
	n2 = FN(PW,n_piece)(data[1].pw);
	if (n1 < 0 \|\| n2 < 0)
	goto error;
	for (i = 0; i < n1; ++i) {
	for (j = 0; j < n2; ++j) {
	isl_bool disjoint;
	isl_set set_i, set_j;

	set_i = FN(PW,peek_domain_at)(data[0].pw, i);
	set_j = FN(PW,peek_domain_at)(data[1].pw, j);
	disjoint = isl_set_is_disjoint(set_i, set_j);
	if (disjoint < 0)
	goto error;
	if (disjoint)
	continue;
	if (FN(PW,union_opt_cmp_two)(&data[0], i,
	&data[1], j, cmp) < 0)
	goto error;
	}
	}

	res = FN(PW,merge)(&data[0], &data[1]);
	for (i = 0; i < 2; ++i)
	FN(PW,union_opt_cmp_data_clear)(&data[i]);

	return res;
	error:
	for (i = 0; i < 2; ++i)
	FN(PW,union_opt_cmp_data_clear)(&data[i]);
	return FN(PW,free)(res);
	}