/* * 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 a list containing the domains of the pieces of "pw". */ static __isl_give isl_set_list *FN(PW,extract_domains)(__isl_keep PW *pw) { … } /* 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) { … } /* 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) { … } /* 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) { … }; /* Free all memory allocated for "data". */ static void FN(PW,union_opt_cmp_data_clear)(S(PW,union_opt_cmp_data) *data) { … } /* 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) { … } /* 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)) { … } /* 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)) { … } /* 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) { … } /* 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)) { … }
Codebase Browser
llvm