dependence_graph_relation.cc

   1 #include <isl/ctx.h>
   2 #include <isl/space.h>
   3 #include <isl/set.h>
   4 #include <isl/map.h>
   5 #include <isl/union_map.h>
   6 #include <isl/printer.h>
   7 #include "version.h"
   8 #include <isa/pdg.h>
   9 #include "da.h"
  10 #include "dependence_graph_relation_options.h"
  11
  12 /* Print the dependence graph of the input program as a single relation.
  13  * If type is "mem" (the default), then memory based dependences are
  14  * computed, i.e., there is a dependence between two statement iterations
  15  * if they (may) access the same memory location, where at least one
  16  * of the accesses is a write, and if the first statement iteration is
  17  * executed before the second.
  18  * If type is "val", then value based dependence are computed.
  19  * If type is "flow", then value based flow dependence are computed.
  20  */
  21
  22 using pdg::PDG;
  23 using namespace da;
  24
  25 /* Compute and return the maximal iteration domain dimension.
  26  */
  27 int get_max_dim(PDG *pdg)
  28 {
  29         int max_dim = -1;
  30         isl_ctx *ctx = pdg->get_isl_ctx();
  31
  32         for (int i = 0; i < pdg->nodes.size(); ++i) {
  33                 isl_set *dom;
  34                 int dim;
  35
  36                 dom = pdg->nodes[i]->source->get_isl_set(ctx);
  37
  38                 dim = isl_set_dim(dom, isl_dim_set);
  39                 if (dim > max_dim)
  40                         max_dim = dim;
  41
  42                 isl_set_free(dom);
  43         }
  44
  45         return max_dim;
  46 }
  47
  48 /* Return 2 * d + b, where d is the shared nesting level and b
  49  * is true is first textually appears before second.
  50  */
  51 static int precedes_level_nodes(pdg::node *first, pdg::node *second)
  52 {
  53         int d = 0;
  54         int cmp = 0;
  55         for (int i = 0; i < first->prefix.size(); ++i) {
  56                 if (i >= second->prefix.size())
  57                         break;
  58                 cmp = first->prefix[i] - second->prefix[i];
  59                 if (cmp)
  60                         break;
  61                 if (first->prefix[i] == -1)
  62                         ++d;
  63         }
  64         return 2 * d + (cmp < 0);
  65 }
  66
  67 /* Pad either the input or the output dimension of the map to max_dim
  68  * and add an extra dimension with as fixed value "nr".
  69  */
  70 isl_map *normalize_dim(isl_map *map, enum isl_dim_type type, int nr,
  71         int max_dim, struct options *options)
  72 {
  73         if (options->named) {
  74                 char s[20];
  75                 sprintf(s, "N_%d", nr);
  76                 map = isl_map_set_tuple_name(map, type, s);
  77         } else {
  78                 unsigned dim = isl_map_dim(map, type);
  79                 map = isl_map_add_dims(map, type, max_dim - dim + 1);
  80                 for (int i = dim; i < max_dim; ++i)
  81                         isl_map_fix_si(map, type, i, 0);
  82                 isl_map_fix_si(map, type, max_dim, nr);
  83         }
  84         return map;
  85 }
  86
  87 /* Compute memory based dependences from the given access to any
  88  * other access and add them to "graph".
  89  *
  90  * If there are any data-dependent accesses, i.e., with nested
  91  * accesses, then the nested access values are projected out.
  92  */
  93 isl_union_map *add_dependences_from(isl_union_map *graph, PDG *pdg,
  94         pdg::node *from_node, pdg::access *from, int max_dim,
  95         struct options *options)
  96 {
  97         isl_ctx *ctx = pdg->get_isl_ctx();
  98
  99         for (int i = 0; i < pdg->nodes.size(); ++i) {
 100                 pdg::node *to_node = pdg->nodes[i];
 101                 pdg::statement *s = pdg->nodes[i]->statement;
 102                 int level = precedes_level_nodes(from_node, to_node);
 103                 int before = level % 2;
 104                 level >>= 1;
 105
 106                 for (int j = 0; j < s->accesses.size(); ++j) {
 107                         pdg::access *to = s->accesses[j];
 108                         isl_map *r_from;
 109                         isl_map *r_to;
 110                         isl_map *dep;
 111                         isl_map *order;
 112                         int from_space, to_dim;
 113
 114                         if (to->array != from->array)
 115                                 continue;
 116                         if (to->type == pdg::access::read &&
 117                             from->type == pdg::access::read)
 118                                 continue;
 119
 120                         r_from = from->map->get_isl_map(ctx);
 121                         r_to = to->map->get_isl_map(ctx);
 122
 123                         from_space = from_node->source->dim();
 124                         r_from = isl_map_project_out(r_from,
 125                                     isl_dim_in, from_space,
 126                                     from->map->input() - from_space);
 127                         to_dim = to_node->source->dim();
 128                         r_to = isl_map_project_out(r_to,
 129                                     isl_dim_in, to_dim,
 130                                     to->map->input() - to_dim);
 131
 132                         r_from = isl_map_intersect_domain(r_from,
 133                                         from_node->source->get_isl_set(ctx));
 134                         r_to = isl_map_intersect_domain(r_to,
 135                                         to_node->source->get_isl_set(ctx));
 136
 137                         dep = isl_map_apply_range(r_from, isl_map_reverse(r_to));
 138                         if (before)
 139                                 order = isl_map_lex_le_first(
 140                                         isl_map_get_space(dep), level);
 141                         else
 142                                 order = isl_map_lex_lt_first(
 143                                         isl_map_get_space(dep), level);
 144                         dep = isl_map_intersect(dep, order);
 145                         dep = normalize_dim(dep, isl_dim_in,
 146                                                 from_node->nr, max_dim, options);
 147                         dep = normalize_dim(dep, isl_dim_out,
 148                                                 to_node->nr, max_dim, options);
 149
 150                         graph = isl_union_map_add_map(graph, dep);
 151                 }
 152         }
 153
 154         return graph;
 155 }
 156
 157 /* Compute all memory based dependences and add them to "graph".
 158  */
 159 isl_union_map *add_mem_dependences(isl_union_map *graph, PDG *pdg, int max_dim,
 160         struct options *options)
 161 {
 162         for (int i = 0; i < pdg->nodes.size(); ++i) {
 163                 pdg::node *node = pdg->nodes[i];
 164                 pdg::statement *s = pdg->nodes[i]->statement;
 165
 166                 for (int j = 0; j < s->accesses.size(); ++j) {
 167                         pdg::access *access = s->accesses[j];
 168                         graph = add_dependences_from(graph, pdg, node, access,
 169                                                         max_dim, options);
 170                 }
 171         }
 172
 173         return graph;
 174 }
 175
 176 /* Compute all value based flow dependences and add them to "graph".
 177  *
 178  * If there are any data-dependent accesses, i.e., with nested
 179  * accesses, then the nested access values are projected out.
 180  */
 181 isl_union_map *add_val_dependences(isl_union_map *graph, PDG *pdg, int max_dim,
 182         struct options *options)
 183 {
 184         isl_ctx *ctx = pdg->get_isl_ctx();
 185
 186         for (int i = 0; i < pdg->arrays.size(); ++i)
 187                 find_deps(pdg, pdg->arrays[i], flow);
 188         if (options->type != TYPE_FLOW) {
 189                 for (int i = 0; i < pdg->arrays.size(); ++i)
 190                         find_deps(pdg, pdg->arrays[i], anti);
 191                 for (int i = 0; i < pdg->arrays.size(); ++i)
 192                         find_deps(pdg, pdg->arrays[i], output);
 193         }
 194
 195         for (int i = 0; i < pdg->dependences.size(); ++i) {
 196                 int from_space, to_dim;
 197                 pdg::dependence *dep = pdg->dependences[i];
 198                 if (dep->type == pdg::dependence::uninitialized)
 199                         continue;
 200
 201                 isl_map *map = dep->relation->get_isl_map(ctx);
 202                 from_space = dep->from->source->dim();
 203                 to_dim = dep->to->source->dim();
 204                 map = isl_map_project_out(map, isl_dim_in, from_space,
 205                                 dep->relation->input() - from_space);
 206                 map = isl_map_project_out(map, isl_dim_out, to_dim,
 207                                 dep->relation->output() - to_dim);
 208                 map = normalize_dim(map, isl_dim_in, dep->from->nr, max_dim,
 209                                         options);
 210                 map = normalize_dim(map, isl_dim_out, dep->to->nr, max_dim,
 211                                         options);
 212
 213                 graph = isl_union_map_add_map(graph, map);
 214         }
 215
 216         return graph;
 217 }
 218
 219 int main(int argc, char *argv[])
 220 {
 221         FILE *in = stdin;
 222         isl_ctx *ctx = isl_ctx_alloc();
 223         PDG *pdg;
 224         int nparam;
 225         int max_dim;
 226         isl_space *dim;
 227         isl_union_map *graph;
 228         isl_printer *p;
 229         struct options *options = options_new_with_defaults();
 230
 231         argc = options_parse(options, argc, argv, ISL_ARG_ALL);
 232
 233         if (options->input && strcmp(options->input, "-"))
 234                 in = fopen(options->input, "r");
 235         assert(in);
 236
 237         pdg = PDG::Load(in, ctx);
 238
 239         max_dim = get_max_dim(pdg);
 240
 241         nparam = pdg->params.size();
 242         dim = isl_space_alloc(pdg->get_isl_ctx(), nparam, max_dim + 1, max_dim + 1);
 243         isl_dim_set_parameter_names(dim, pdg->params);
 244         graph = isl_union_map_empty(dim);
 245
 246         if (options->type == TYPE_MEM)
 247                 graph = add_mem_dependences(graph, pdg, max_dim, options);
 248         else
 249                 graph = add_val_dependences(graph, pdg, max_dim, options);
 250
 251         p = isl_printer_to_file(pdg->get_isl_ctx(), stdout);
 252         p = isl_printer_set_output_format(p, ISL_FORMAT_ISL);
 253         p = isl_printer_print_union_map(p, graph);
 254         p = isl_printer_end_line(p);
 255         isl_printer_free(p);
 256
 257         isl_union_map_free(graph);
 258
 259         pdg->free();
 260         delete pdg;
 261         isl_ctx_free(ctx);
 262
 263         return 0;
 264 }