schedule.c

   1 /*
   2  * Copyright 2010-2011 INRIA Saclay
   3  *
   4  * Use of this software is governed by the MIT 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 <assert.h>
  12 #include <ctype.h>
  13 #include <string.h>
  14
  15 #include <isl/set.h>
  16 #include <isl/map.h>
  17 #include <isl/constraint.h>
  18
  19 #include "schedule.h"
  20
  21 /* Construct a map from a len-dimensional domain to
  22  * a (len-n)-dimensional domain that projects out the n coordinates
  23  * starting at first.
  24  * "dim" prescribes the parameters.
  25  */
  26 __isl_give isl_map *project_out(__isl_take isl_space *dim,
  27     int len, int first, int n)
  28 {
  29     int i, j;
  30     isl_basic_map *bmap;
  31
  32     dim = isl_space_add_dims(dim, isl_dim_in, len);
  33     dim = isl_space_add_dims(dim, isl_dim_out, len - n);
  34     bmap = isl_basic_map_universe(dim);
  35
  36     for (i = 0, j = 0; i < len; ++i) {
  37         if (i >= first && i < first + n)
  38             continue;
  39         bmap = isl_basic_map_equate(bmap, isl_dim_in, i, isl_dim_out, j);
  40         ++j;
  41     }
  42
  43     return isl_map_from_basic_map(bmap);
  44 }
  45
  46 /* Construct a projection that maps a src_len dimensional domain
  47  * to its first dst_len coordinates.
  48  * "dim" prescribes the parameters.
  49  */
  50 __isl_give isl_map *projection(__isl_take isl_space *dim,
  51     int src_len, int dst_len)
  52 {
  53     return project_out(dim, src_len, dst_len, src_len - dst_len);
  54 }
  55
  56 /* Extend "set" with unconstrained coordinates to a total length of "dst_len".
  57  */
  58 __isl_give isl_set *extend(__isl_take isl_set *set, int dst_len)
  59 {
  60     int n_set;
  61     isl_space *dim;
  62     isl_map *map;
  63
  64     dim = isl_set_get_space(set);
  65     n_set = isl_space_dim(dim, isl_dim_set);
  66     dim = isl_space_drop_dims(dim, isl_dim_set, 0, n_set);
  67     map = projection(dim, dst_len, n_set);
  68     map = isl_map_reverse(map);
  69
  70     return isl_set_apply(set, map);
  71 }
  72
  73 /* Set max_out to the maximal number of output dimensions over
  74  * all maps.
  75  */
  76 static int update_max_out(__isl_take isl_map *map, void *user)
  77 {
  78         int *max_out = user;
  79         int n_out = isl_map_dim(map, isl_dim_out);
  80
  81         if (n_out > *max_out)
  82                 *max_out = n_out;
  83
  84         isl_map_free(map);
  85         return 0;
  86 }
  87
  88 struct align_range_data {
  89         int max_out;
  90         isl_union_map *res;
  91 };
  92
  93 /* Extend the dimension of the range of the given map to data->max_out and
  94  * then add the result to data->res.
  95  */
  96 static int map_align_range(__isl_take isl_map *map, void *user)
  97 {
  98         struct align_range_data *data = user;
  99         int i;
 100         isl_space *dim;
 101         isl_map *proj;
 102         int n_out = isl_map_dim(map, isl_dim_out);
 103
 104         dim = isl_union_map_get_space(data->res);
 105         proj = isl_map_reverse(projection(dim, data->max_out, n_out));
 106         for (i = n_out; i < data->max_out; ++i)
 107                 proj = isl_map_fix_si(proj, isl_dim_out, i, 0);
 108
 109         map = isl_map_apply_range(map, proj);
 110
 111         data->res = isl_union_map_add_map(data->res, map);
 112
 113         return 0;
 114 }
 115
 116 /* Extend the ranges of the maps in the union map such they all have
 117  * the same dimension.
 118  */
 119 __isl_give isl_union_map *align_range(__isl_take isl_union_map *umap)
 120 {
 121         struct align_range_data data;
 122
 123         data.max_out = 0;
 124         isl_union_map_foreach_map(umap, &update_max_out, &data.max_out);
 125
 126         data.res = isl_union_map_empty(isl_union_map_get_space(umap));
 127         isl_union_map_foreach_map(umap, &map_align_range, &data);
 128
 129         isl_union_map_free(umap);
 130         return data.res;
 131 }