dependence_graph_relation.cc

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