pdg.cc

   1 #include <isa/pdg.h>
   2 #include <algorithm>
   3 #include <vector>
   4 #include "version.h"
   5
   6 #include <isl/set.h>
   7 #include <isl/map.h>
   8
   9 using namespace pdg;
  10 using std::vector;
  11
  12 static at_init register_history_entry(history_entry::register_type);
  13
  14 void history_entry::register_type()
  15 {
  16     static struct_description d = { create };
  17     YAML_PTR_FIELD(d, history_entry, tool, str);
  18     YAML_PTR_FIELD(d, history_entry, version, str);
  19     YAML_SEQ_FIELD(d, history_entry, arguments, str);
  20     structure::register_type("perl/history_entry", &typeid(history_entry), &d.d);
  21 }
  22
  23 static at_init register_pdg(PDG::register_type);
  24
  25 void PDG::register_type()
  26 {
  27     static struct_description pdg_d = { create };
  28     YAML_INT_FIELD(pdg_d, PDG, dimension);
  29     YAML_INT_FIELD(pdg_d, PDG, cacheline);
  30     YAML_INT_FIELD(pdg_d, PDG, root);
  31     YAML_PTR_FIELD(pdg_d, PDG, placement, str);
  32     YAML_SEQ_FIELD(pdg_d, PDG, nodes, node);
  33     YAML_SEQ_FIELD(pdg_d, PDG, arrays, array);
  34     YAML_SEQ_FIELD(pdg_d, PDG, dependences, dependence);
  35     YAML_SEQ_FIELD(pdg_d, PDG, params, parameter);
  36     YAML_PTR_FIELD(pdg_d, PDG, context, IslSet);
  37     YAML_SEQ_FIELD(pdg_d, PDG, history, history_entry);
  38     YAML_PTR_FIELD(pdg_d, PDG, name, str);
  39     YAML_SEQ_FIELD(pdg_d, PDG, statement_dimensions, int);
  40     structure::register_type("perl/PDG", &typeid(PDG), &pdg_d.d);
  41 }
  42
  43 PDG *PDG::Load(char *str, isl_ctx *ctx)
  44 {
  45     return yaml::Load<PDG>(str, ctx);
  46 }
  47
  48 PDG *PDG::Load(FILE *fp, isl_ctx *ctx)
  49 {
  50     return yaml::Load<PDG>(fp, ctx);
  51 }
  52
  53 PDG::~PDG()
  54 {
  55     if (ctx_created)
  56         isl_ctx_free(ctx);
  57 }
  58
  59 isl_ctx *PDG::get_isl_ctx()
  60 {
  61     if (!ctx) {
  62         ctx = isl_ctx_alloc();
  63         assert(ctx);
  64         ctx_created = true;
  65     }
  66     return ctx;
  67 }
  68
  69 /* Return the context of this PDG.
  70  * If this PDG has no context, then return a universe parametric set
  71  * with the same parameters as this PDG.
  72  */
  73 isl_set *PDG::get_context_isl_set()
  74 {
  75     isl_ctx *ctx = get_isl_ctx();
  76     isl_set *set;
  77
  78     if (context) {
  79         set = context->get_isl_set(ctx);
  80     } else {
  81         isl_space *dims = isl_space_params_alloc(ctx, params.size());
  82         isl_dim_set_parameter_names(dims, params);
  83         set = isl_set_universe(dims);
  84     }
  85
  86     return set;
  87 }
  88
  89 void PDG::add_history_line(const char *tool, int argc, char * argv[])
  90 {
  91     history_entry *he = new history_entry();
  92     he->tool = new str(string(tool));
  93     he->version = new str(string(pdg_version()));
  94     for (int i = 1; i < argc; ++i)
  95         he->arguments.push_back(new str(argv[i]));
  96     history.push_back(he);
  97 }
  98
  99 static at_init register_array(array::register_type);
 100
 101 void array::register_type()
 102 {
 103     static const char *at_names[array::last];
 104     at_names[input] = "input";
 105     at_names[output] = "output";
 106     at_names[temp] = "temp";
 107     static struct_description d = { create };
 108     YAML_INT_FIELD(d, array, id);
 109     YAML_PTR_FIELD(d, array, name, str);
 110     YAML_SEQ_FIELD(d, array, dims, int);
 111     YAML_PTR_FIELD(d, array, element_type, str);
 112     YAML_ENUM_FIELD(d, array, type, at_names);
 113     YAML_SEQ_FIELD(d, array, analysis_performed, dependence_type);
 114     YAML_PTR_FIELD(d, array, value_bounds, IslSet);
 115     YAML_INT_FIELD(d, array, uniquely_defined);
 116     YAML_INT_FIELD(d, array, killed);
 117     structure::register_type("perl/array", &typeid(array), &d.d);
 118 }
 119
 120 static at_init register_parameter(parameter::register_type);
 121
 122 void parameter::register_type()
 123 {
 124     static struct_description d = { create };
 125     YAML_INT_FIELD(d, parameter, id);
 126     YAML_PTR_FIELD(d, parameter, name, str);
 127     YAML_PTR_FIELD(d, parameter, value, integer);
 128     structure::register_type("perl/parameter", &typeid(parameter), &d.d);
 129 }
 130
 131 void pdg::isl_dim_set_parameter_names(isl_space *dim,
 132                                         const seq<parameter>& params)
 133 {
 134         for (int i = 0; i < params.size(); ++i)
 135                 dim = isl_space_set_dim_name(dim, isl_dim_param, i,
 136                                         params[i]->name->s.c_str());
 137 }
 138
 139 isl_set *pdg::isl_set_set_parameter_names(isl_set *set,
 140                                             const seq<parameter>& params)
 141 {
 142         for (int i = 0; i < params.size(); ++i)
 143                 set = isl_set_set_dim_name(set, isl_dim_param, i,
 144                                             params[i]->name->s.c_str());
 145         return set;
 146 }
 147
 148 static at_init register_access(pdg::access::register_type);
 149
 150 void pdg::access::register_type()
 151 {
 152     static const char *at_names[access::last];
 153     at_names[write] = "write";
 154     at_names[read] = "read";
 155     static struct_description d = { create };
 156     YAML_PTR_FIELD(d, pdg::access, array, pdg::array);
 157     YAML_ENUM_FIELD(d, pdg::access, type, at_names);
 158     YAML_PTR_FIELD(d, pdg::access, map, IslMap);
 159     YAML_INT_FIELD(d, pdg::access, nr);
 160     YAML_PTR_FIELD(d, pdg::access, extension, IslMap);
 161     YAML_PTR_FIELD(d, pdg::access, extended_map, IslMap);
 162     YAML_SEQ_FIELD(d, pdg::access, nested, call_or_access);
 163     YAML_SEQ_FIELD(d, pdg::access, sources, IslMap);
 164     structure::register_type("perl/access", &typeid(pdg::access), &d.d);
 165 }
 166
 167 static at_init register_function_call(function_call::register_type);
 168
 169 void function_call::register_type()
 170 {
 171     static struct_description s_d = { create };
 172     YAML_SEQ_FIELD(s_d, function_call, arguments, call_or_access);
 173     YAML_PTR_FIELD(s_d, function_call, name, str);
 174     structure::register_type("perl/function_call", &typeid(function_call), &s_d.d);
 175 }
 176
 177 static at_init register_call_or_access(call_or_access::register_type);
 178
 179 void call_or_access::register_type()
 180 {
 181     static const char *cat_names[call_or_access::last];
 182     cat_names[t_access] = "access";
 183     cat_names[t_call] = "call";
 184     static struct_description s_d = { create };
 185     YAML_ENUM_FIELD(s_d, pdg::call_or_access, type, cat_names);
 186     YAML_PTR_FIELD(s_d, pdg::call_or_access, access, pdg::access);
 187     YAML_PTR_FIELD(s_d, pdg::call_or_access, call, function_call);
 188     structure::register_type("perl/call_or_access", &typeid(call_or_access), &s_d.d);
 189 }
 190
 191 static at_init register_stat(statement::register_type);
 192
 193 void statement::register_type()
 194 {
 195     static struct_description s_d = { create };
 196     YAML_INT_FIELD(s_d, statement, operation);
 197     YAML_INT_FIELD(s_d, statement, line);
 198     YAML_SEQ_FIELD(s_d, statement, accesses, access);
 199     YAML_PTR_FIELD(s_d, statement, top_function, function_call);
 200     YAML_SEQ_FIELD(s_d, statement, top_outputs, access);
 201     structure::register_type("perl/statement", &typeid(statement), &s_d.d);
 202 }
 203
 204 static at_init register_node(node::register_type);
 205
 206 void node::register_type()
 207 {
 208     static struct_description node_d = { create };
 209     YAML_INT_FIELD(node_d, node, nr);
 210     YAML_PTR_FIELD(node_d, node, name, str);
 211     YAML_PTR_FIELD(node_d, node, source, IslSet);
 212     YAML_PTR_FIELD(node_d, node, schedule, IslMap);
 213     YAML_PTR_FIELD(node_d, node, statement, pdg::statement);
 214     YAML_SEQ_FIELD(node_d, node, prefix, int);
 215     YAML_SEQ_FIELD(node_d, node, filters, call_or_access);
 216     structure::register_type("perl/node", &typeid(node), &node_d.d);
 217 }
 218
 219 static at_init register_dependence(dependence::register_type);
 220
 221 void dependence::register_type()
 222 {
 223     static const char *dt_names[dependence::last];
 224     dt_names[flow] = "flow";
 225     dt_names[anti] = "anti";
 226     dt_names[pn] = "pn";
 227     dt_names[pn_union] = "pn_union";
 228     dt_names[pn_part] = "pn_part";
 229     dt_names[pn_wire] = "pn_wire";
 230     dt_names[pn_hold] = "pn_hold";
 231     dt_names[pn_shift] = "pn_shift";
 232     dt_names[reuse] = "reuse";
 233     dt_names[reuse_pair] = "reuse_pair";
 234     dt_names[output] = "output";
 235     dt_names[uninitialized] = "uninitialized";
 236     static struct_description dependence_d = { create };
 237     YAML_PTR_FIELD(dependence_d, dependence, relation, IslMap);
 238     YAML_PTR_FIELD(dependence_d, dependence, extended_relation, IslMap);
 239     YAML_PTR_FIELD(dependence_d, dependence, controlled_relation, IslMap);
 240     YAML_PTR_FIELD(dependence_d, dependence, from, pdg::node);
 241     YAML_PTR_FIELD(dependence_d, dependence, to, pdg::node);
 242     YAML_PTR_FIELD(dependence_d, dependence, from_access, pdg::access);
 243     YAML_PTR_FIELD(dependence_d, dependence, to_access, pdg::access);
 244     YAML_ENUM_FIELD(dependence_d, dependence, type, dt_names);
 245     YAML_PTR_FIELD(dependence_d, dependence, array, pdg::array);
 246     YAML_SEQ_FIELD(dependence_d, dependence, from_controls, str);
 247     YAML_SEQ_FIELD(dependence_d, dependence, to_controls, str);
 248     YAML_INT_FIELD(dependence_d, dependence, reordering);
 249     YAML_INT_FIELD(dependence_d, dependence, multiplicity);
 250     YAML_PTR_FIELD(dependence_d, dependence, size, enumerator);
 251     YAML_PTR_FIELD(dependence_d, dependence, container, dependence);
 252     YAML_PTR_FIELD(dependence_d, dependence, value_size, integer);
 253     structure::register_type("perl/dependence", &typeid(dependence), &dependence_d.d);
 254
 255     static struct_description dependence_type_d = { dependence_type::create };
 256     YAML_ENUM_FIELD(dependence_type_d, dependence_type, type, dt_names);
 257     structure::register_type("perl/dependence_type", &typeid(dependence_type), &dependence_type_d.d);
 258 }
 259
 260 static at_init register_enumerator(pdg::enumerator::register_type);
 261
 262 void pdg::enumerator::register_type()
 263 {
 264     static struct_description e_d = { create, convert };
 265     structure::register_type("perl/PDG::enumerator", &typeid(enumerator), &e_d.d);
 266 }
 267
 268 void pdg::enumerator::init(SyckParser *p, SyckNode *n)
 269 {
 270     s = new string(n->data.str->ptr, n->data.str->len);
 271 }
 272
 273 serialize *pdg::enumerator::convert(anchor_map *am, serialize *node,
 274         const type_info *type)
 275 {
 276         str *s = dynamic_cast<str *>(node);
 277         pdg::enumerator *e;
 278
 279         if (!s)
 280                 return NULL;
 281
 282         e = new enumerator(new string(s->s));
 283
 284         delete node;
 285
 286         return e;
 287 }
 288
 289 void pdg::enumerator::dump(emitter& e)
 290 {
 291     if (s)
 292         yll_emitter_write_string(e.e, s->c_str());
 293     else if (value >= 0)
 294         yll_emitter_write_int(e.e, value);
 295     else
 296         assert(0);
 297 }
 298
 299 pdg::enumerator::~enumerator()
 300 {
 301     if (s)
 302         delete s;
 303 }
 304
 305 static at_init register_isl_set(IslSet::register_type);
 306
 307 void IslSet::register_type()
 308 {
 309         static struct_description s_d = { create, convert };
 310         structure::register_type("", &typeid(IslSet), &s_d.d);
 311 }
 312
 313 serialize *IslSet::convert(anchor_map *am, serialize *node,
 314         const type_info *type)
 315 {
 316         str *s = dynamic_cast<str *>(node);
 317         isl_ctx *ctx = (isl_ctx *) am->user;
 318         isl_set *set;
 319
 320         if (s) {
 321                 set = isl_set_read_from_str(ctx, s->s.c_str());
 322                 delete node;
 323                 return new IslSet(set);
 324         }
 325
 326         return NULL;
 327 }
 328
 329 void IslSet::dump(emitter &e)
 330 {
 331         isl_printer *p;
 332         char *s;
 333
 334         if (!set) {
 335                 yll_emitter_write_null(e.e);
 336                 return;
 337         }
 338
 339         p = isl_printer_to_str(isl_set_get_ctx(set));
 340         p = isl_printer_print_set(p, set);
 341         s = isl_printer_get_str(p);
 342         isl_printer_free(p);
 343
 344         yll_emitter_write_string(e.e, s);
 345
 346         ::free(s);
 347 }
 348
 349 static at_init register_isl_map(IslMap::register_type);
 350
 351 void IslMap::register_type()
 352 {
 353         static struct_description s_d = { create, convert };
 354         structure::register_type("", &typeid(IslMap), &s_d.d);
 355 }
 356
 357 serialize *IslMap::convert(anchor_map *am, serialize *node,
 358         const type_info *type)
 359 {
 360         str *s = dynamic_cast<str *>(node);
 361         isl_ctx *ctx = (isl_ctx *) am->user;
 362         isl_map *map;
 363
 364         if (s) {
 365                 map = isl_map_read_from_str(ctx, s->s.c_str());
 366                 delete node;
 367                 return new IslMap(map);
 368         }
 369
 370         return NULL;
 371 }
 372
 373 void IslMap::dump(emitter &e)
 374 {
 375         isl_printer *p;
 376         char *s;
 377
 378         if (!map) {
 379                 yll_emitter_write_null(e.e);
 380                 return;
 381         }
 382
 383         p = isl_printer_to_str(isl_map_get_ctx(map));
 384         p = isl_printer_print_map(p, map);
 385         s = isl_printer_get_str(p);
 386         isl_printer_free(p);
 387
 388         yll_emitter_write_string(e.e, s);
 389
 390         ::free(s);
 391 }
 392
 393 /* Schedule the given dependence relations "map" according to the schedules
 394  * of the source and target of "dep".
 395  */
 396 __isl_give isl_map *pdg::schedule_dependence(PDG *pdg, pdg::dependence *dep,
 397         __isl_take isl_map *map)
 398 {
 399         isl_map *sr = dep->to->schedule->get_isl_map();
 400         map = isl_map_apply_range(map, sr);
 401         if (dep->from) {
 402                 isl_map *sw = dep->from->schedule->get_isl_map();
 403                 map = isl_map_apply_domain(map, sw);
 404         }
 405
 406         return map;
 407 }
 408
 409 __isl_give isl_map *pdg::scatter_dependence(PDG *pdg, pdg::dependence *dep)
 410 {
 411         return schedule_dependence(pdg, dep, dep->relation->get_isl_map());
 412 }
 413
 414 /* Assuming this is a read access, construct a map from the domain
 415  * of the access relation to the access relation of the corresponding
 416  * writes.  If we are unable to determine the corresponding writes, then
 417  * return a map to the read access.
 418  *
 419  * For example, if the access relation is
 420  *
 421  *      S[i] -> A[]
 422  *
 423  * and there is a single source of the form
 424  *
 425  *      [W[0,i] -> A[]] -> [S[i] -> A[]]
 426  *
 427  * then the returned map is
 428  *
 429  *      S[i] -> [W[0,i] -> A[]]
 430  *
 431  * If there are multiple writes involved, then the range of the result lives
 432  * in different spaces.
 433  *
 434  * If no source was found then return
 435  *
 436  *      S[i] -> [S[i] -> A[]]
 437  */
 438 __isl_give isl_union_map *pdg::access::extract_access_map()
 439 {
 440         isl_ctx *ctx;
 441         isl_map *access_map;
 442         isl_union_map *res;
 443
 444         access_map = map->get_isl_map();
 445         access_map = isl_map_reverse(isl_map_domain_map(access_map));
 446
 447         if (sources.size() == 0)
 448                 return isl_union_map_from_map(access_map);
 449
 450         ctx = isl_map_get_ctx(access_map);
 451         res = isl_union_map_empty(isl_space_params_alloc(ctx, 0));
 452
 453         for (int i = 0; i < sources.size(); ++i) {
 454                 isl_map *source_map;
 455                 source_map = sources[i]->get_isl_map();
 456                 source_map = isl_map_reverse(source_map);
 457                 source_map = isl_map_apply_range(isl_map_copy(access_map),
 458                                                 source_map);
 459                 res = isl_union_map_add_map(res, source_map);
 460         }
 461
 462         isl_map_free(access_map);
 463
 464         return res;
 465 }
 466
 467 /* Return the number of outer loops that are affected by filters.
 468  *
 469  * A loop iterator is affected by a filter if it is involved
 470  * in any of the iteration domain constraints that also involves filters,
 471  * if any of the filter accesses depends on the loop iterator,
 472  * or if any of the sources of a filter depends on the loop iterator.
 473  * If no sources were recorded, then we conservatively assume that
 474  * all loops are affected by filters.
 475  */
 476 int node::get_filter_depth()
 477 {
 478         isl_map *value;
 479         isl_set *dom;
 480         int n_in, n_out;
 481
 482         if (filter_depth >= 0)
 483                 return filter_depth;
 484
 485         filter_depth = 0;
 486         value = isl_set_unwrap(source->get_isl_set());
 487         n_in = isl_map_dim(value, isl_dim_in);
 488         n_out = isl_map_dim(value, isl_dim_out);
 489
 490         dom = isl_map_domain(isl_map_copy(value));
 491         value = isl_map_gist_domain(value, isl_set_copy(dom));
 492         for (int j = n_in - 1; j >= 0; --j) {
 493                 if (!isl_map_involves_dims(value, isl_dim_in, j, 1))
 494                         continue;
 495                 if (j >= filter_depth)
 496                         filter_depth = j + 1;
 497                 break;
 498         }
 499
 500         for (int i = 0; i < n_out; ++i) {
 501                 pdg::call_or_access *coa;
 502
 503                 coa = filters[i];
 504                 assert(coa->type == pdg::call_or_access::t_access);
 505
 506                 if (coa->access->sources.size() == 0) {
 507                         filter_depth = n_in;
 508                         break;
 509                 }
 510
 511                 for (int j = 0; j < coa->access->sources.size(); ++j) {
 512                         isl_map *map;
 513                         map = coa->access->sources[j]->get_isl_map();
 514                         map = isl_map_zip(map);
 515                         map = isl_set_unwrap(isl_map_domain(map));
 516                         map = isl_map_gist_range(map, isl_set_copy(dom));
 517
 518                         for (int k = n_in - 1; k >= 0; --k) {
 519                                 if (!isl_map_involves_dims(map,
 520                                                             isl_dim_out, k, 1))
 521                                         continue;
 522                                 if (k >= filter_depth)
 523                                         filter_depth = k + 1;
 524                                 break;
 525                         }
 526
 527                         isl_map_free(map);
 528                 }
 529
 530                 for (int j = n_in - 1; j >= 0; --j) {
 531                         if (!isl_map_involves_dims(coa->access->map->map,
 532                                                     isl_dim_in, j, 1))
 533                                 continue;
 534                         if (j >= filter_depth)
 535                                 filter_depth = j + 1;
 536                         break;
 537                 }
 538
 539         }
 540         isl_set_free(dom);
 541         isl_map_free(value);
 542
 543         return filter_depth;
 544 }