scoplib_isl.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #include "scoplib_isl.h"
  12
  13 /* Set the dimension names of type "type" according to the elements
  14  * in the array "names".
  15  */
  16 __isl_give isl_dim *set_dim_names(__isl_take isl_dim *dim,
  17         enum isl_dim_type type, char **names)
  18 {
  19         int i;
  20
  21         for (i = 0; i < isl_dim_size(dim, type); ++i)
  22                 dim = isl_dim_set_name(dim, type, i, names[i]);
  23
  24         return dim;
  25 }
  26
  27
  28 /* Convert a scoplib_matrix_p containing the constraints of a domain
  29  * to an isl_set.
  30  */
  31 __isl_give isl_set *scoplib_matrix_to_isl_set(scoplib_matrix_p matrix,
  32         __isl_take isl_dim *dim)
  33 {
  34     int i, j;
  35     int n_eq = 0, n_ineq = 0;
  36     isl_ctx *ctx;
  37     isl_mat *eq, *ineq;
  38     isl_int v;
  39     isl_basic_set *bset;
  40
  41     isl_int_init(v);
  42
  43     ctx = isl_dim_get_ctx(dim);
  44
  45     for (i = 0; i < matrix->NbRows; ++i)
  46         if (SCOPVAL_zero_p(matrix->p[i][0]))
  47             n_eq++;
  48         else
  49             n_ineq++;
  50
  51     eq = isl_mat_alloc(ctx, n_eq, matrix->NbColumns - 1);
  52     ineq = isl_mat_alloc(ctx, n_ineq, matrix->NbColumns - 1);
  53
  54     n_eq = n_ineq = 0;
  55     for (i = 0; i < matrix->NbRows; ++i) {
  56         isl_mat **m;
  57         int row;
  58
  59         if (SCOPVAL_zero_p(matrix->p[i][0])) {
  60             m = &eq;
  61             row = n_eq++;
  62         } else {
  63             m = &ineq;
  64             row = n_ineq++;
  65         }
  66
  67         for (j = 0; j < matrix->NbColumns - 1; ++j) {
  68             int t = SCOPVAL_get_si(matrix->p[i][1 + j]);
  69             isl_int_set_si(v, t);
  70             *m = isl_mat_set_element(*m, row, j, v);
  71         }
  72     }
  73
  74     isl_int_clear(v);
  75
  76     bset = isl_basic_set_from_constraint_matrices(dim, eq, ineq,
  77                 isl_dim_set, isl_dim_div, isl_dim_param, isl_dim_cst);
  78     return isl_set_from_basic_set(bset);
  79 }
  80
  81
  82 /* Convert a scoplib_matrix_list_p describing a union of domains
  83  * to an isl_set.
  84  */
  85 __isl_give isl_set *scoplib_matrix_list_to_isl_set(
  86         scoplib_matrix_list_p list, __isl_take isl_dim *dim)
  87 {
  88     isl_set *set;
  89
  90     set = isl_set_empty(isl_dim_copy(dim));
  91     for (; list; list = list->next) {
  92         isl_set *set_i;
  93         set_i = scoplib_matrix_to_isl_set(list->elt, isl_dim_copy(dim));
  94         set = isl_set_union(set, set_i);
  95     }
  96
  97     isl_dim_free(dim);
  98     return set;
  99 }
 100
 101
 102 /* Return the number of lines until the next non-zero element
 103  * in the first column of "access" or until the end of the matrix.
 104  */
 105 static int access_len(scoplib_matrix_p access, int first)
 106 {
 107     int i;
 108
 109     for (i = first + 1; i < access->NbRows; ++i)
 110         if (!SCOPVAL_zero_p(access->p[i][0]))
 111             break;
 112
 113     return i - first;
 114 }
 115
 116
 117 /* Convert an m x (1 + n + 1) scoplib_matrix_p [d A c]
 118  * to an m x (m + n + 1) isl_mat [-I A c].
 119  */
 120 static __isl_give isl_mat *extract_equalities(isl_ctx *ctx,
 121         scoplib_matrix_p matrix, int first, int n)
 122 {
 123     int i, j;
 124     int n_col;
 125     isl_int v;
 126     isl_mat *eq;
 127
 128     n_col = matrix->NbColumns;
 129
 130     isl_int_init(v);
 131     eq = isl_mat_alloc(ctx, n, n + n_col - 1);
 132
 133     for (i = 0; i < n; ++i) {
 134         isl_int_set_si(v, 0);
 135         for (j = 0; j < n; ++j)
 136             eq = isl_mat_set_element(eq, i, j, v);
 137         isl_int_set_si(v, -1);
 138         eq = isl_mat_set_element(eq, i, i, v);
 139         for (j = 0; j < n_col - 1; ++j) {
 140             int t = SCOPVAL_get_si(matrix->p[first + i][1 + j]);
 141             isl_int_set_si(v, t);
 142             eq = isl_mat_set_element(eq, i, n + j, v);
 143         }
 144     }
 145
 146     isl_int_clear(v);
 147
 148     return eq;
 149 }
 150
 151
 152 /* Convert a scoplib_matrix_p describing a series of accesses
 153  * to an isl_union_map with domain "dom" (in space "D").
 154  * Each access in "access" has a non-zero integer in the first column
 155  * of the first row identifying the array being accessed.  The remaining
 156  * entries of the first column are zero.
 157  * Let "A" be array identified by the first entry.
 158  * The remaining columns have the form [B c].
 159  * Each such access is converted to a map { D[i] -> A[B i + c] } * dom.
 160  *
 161  * Note that each access in the input is described by at least one row,
 162  * which means that there is no way of distinguishing between an access
 163  * to a scalar and an access to the first element of a 1-dimensional array.
 164  */
 165 __isl_give isl_union_map *scoplib_access_to_isl_union_map(
 166         scoplib_matrix_p access, __isl_take isl_set *dom, char **arrays)
 167 {
 168     int i, len, n_col;
 169     isl_ctx *ctx;
 170     isl_dim *dim;
 171     isl_mat *eq, *ineq;
 172     isl_union_map *res;
 173
 174     ctx = isl_set_get_ctx(dom);
 175
 176     dim = isl_set_get_dim(dom);
 177     dim = isl_dim_drop(dim, isl_dim_set, 0, isl_dim_size(dim, isl_dim_set));
 178     res = isl_union_map_empty(dim);
 179
 180     n_col = access->NbColumns;
 181
 182     for (i = 0; i < access->NbRows; i += len) {
 183         isl_basic_map *bmap;
 184         isl_map *map;
 185         int arr = SCOPVAL_get_si(access->p[i][0]) - 1;
 186
 187         len = access_len(access, i);
 188
 189         dim = isl_set_get_dim(dom);
 190         dim = isl_dim_from_domain(dim);
 191         dim = isl_dim_add(dim, isl_dim_out, len);
 192         dim = isl_dim_set_tuple_name(dim, isl_dim_out, arrays[arr]);
 193
 194         ineq = isl_mat_alloc(ctx, 0, len + n_col - 1);
 195         eq = extract_equalities(ctx, access, i, len);
 196
 197         bmap = isl_basic_map_from_constraint_matrices(dim, eq, ineq,
 198             isl_dim_out, isl_dim_in, isl_dim_div, isl_dim_param, isl_dim_cst);
 199         map = isl_map_from_basic_map(bmap);
 200         map = isl_map_intersect_domain(map, isl_set_copy(dom));
 201         res = isl_union_map_union(res, isl_union_map_from_map(map));
 202     }
 203
 204     isl_set_free(dom);
 205
 206     return res;
 207 }
 208
 209
 210 /* Convert a scoplib_matrix_p schedule [0 A c] to
 211  * the isl_map { i -> A i + c } in the space prescribed by "dim".
 212  */
 213 __isl_give isl_map *scoplib_schedule_to_isl_map(
 214         scoplib_matrix_p schedule, __isl_take isl_dim *dim)
 215 {
 216     int n_row, n_col;
 217     isl_ctx *ctx;
 218     isl_mat *eq, *ineq;
 219     isl_basic_map *bmap;
 220
 221     ctx = isl_dim_get_ctx(dim);
 222     n_row = schedule->NbRows;
 223     n_col = schedule->NbColumns;
 224
 225     ineq = isl_mat_alloc(ctx, 0, n_row + n_col - 1);
 226     eq = extract_equalities(ctx, schedule, 0, n_row);
 227
 228     bmap = isl_basic_map_from_constraint_matrices(dim, eq, ineq,
 229             isl_dim_out, isl_dim_in, isl_dim_div, isl_dim_param, isl_dim_cst);
 230     return isl_map_from_basic_map(bmap);
 231 }