translation.cc

   1 #include <iostream>
   2 #include <set>
   3 #include <limits.h>
   4
   5 #include <isa/yaml.h>
   6 #include <isa/pdg.h>
   7 #include "da.h"
   8 #include <isl/val.h>
   9 #include <isl/space.h>
  10 #include <isl/set.h>
  11 #include <isl/map.h>
  12 #include <isl/aff.h>
  13 #include <isl/mat.h>
  14 #include <isl/ilp.h>
  15 #include "translation.h"
  16
  17 using namespace std;
  18
  19 namespace pdg {
  20
  21 static void set_prefix(pdg::node *node, const vector<int>& prefix, int l)
  22 {
  23     node->prefix.resize(0);
  24     for (int j = 0; j < l-1; ++j) {
  25         node->prefix.push_back(prefix[j]);
  26         node->prefix.push_back(-1);
  27     }
  28     node->prefix.push_back(prefix[l-1]);
  29 }
  30
  31 /* A comparison function for sorting pdg::nodes based on their prefix.
  32  */
  33 struct earlier_prefix :
  34                 public std::binary_function<pdg::node *, pdg::node *, bool> {
  35         bool operator()(pdg::node *x, pdg::node *y) {
  36                 for (int i = 0; i < x->prefix.size(); ++i) {
  37                         if (x->prefix[i] == -1 && y->prefix[i] == -1)
  38                                 continue;
  39                         assert(x->prefix[i] != -1 && y->prefix[i] != -1);
  40                         if (x->prefix[i] < y->prefix[i])
  41                                 return true;
  42                         if (x->prefix[i] > y->prefix[i])
  43                                 return false;
  44                 }
  45                 return false;
  46         }
  47 };
  48
  49 /* Normalize prefix to be an alternation between statement
  50  * level dimensions and loop level dimensions.
  51  * Return the number of statement level dimension.
  52  *
  53  * Since the algorithm assumes the input prefixes are ordered
  54  * lexicographically, we perform it on a sorted list of nodes.
  55  */
  56 int normalize_prefix(PDG *pdg)
  57 {
  58     int i, l, maxl;
  59     vector<int> prefix;
  60     vector<pdg::node *> nodes;
  61
  62     if (pdg->nodes.size() == 0)
  63         return 0;
  64
  65     for (int i = 0; i < pdg->nodes.size(); ++i)
  66         nodes.push_back(pdg->nodes[i]);
  67     std::sort(nodes.begin(), nodes.end(), earlier_prefix());
  68
  69     l = 1;
  70     for (int j = 0; j < nodes[0]->prefix.size(); ++j)
  71         if (nodes[0]->prefix[j] == -1)
  72             ++l;
  73     prefix.resize(l);
  74     maxl = l;
  75     for (i = 1; i < nodes.size(); ++i) {
  76         int old_l = l;
  77         pdg::node *old_node = nodes[i-1];
  78         pdg::node *node = nodes[i];
  79         int change_l;
  80         l = 1;
  81         change_l = -1;
  82         for (int j = 0; j < node->prefix.size(); ++j) {
  83             if (change_l == -1) {
  84                 assert(old_node->prefix[j] <= node->prefix[j]);
  85                 if (old_node->prefix[j] != node->prefix[j])
  86                     change_l = l;
  87             }
  88             if (node->prefix[j] == -1)
  89                 ++l;
  90         }
  91         if (l > maxl) {
  92             maxl = l;
  93             prefix.resize(l);
  94         }
  95         set_prefix(old_node, prefix, old_l);
  96         if (change_l == -1)
  97             continue;
  98         prefix[change_l-1]++;
  99         for (int j = change_l+1; j < prefix.size(); ++j)
 100             prefix[j] = 0;
 101     }
 102     pdg::node *node = nodes[nodes.size()-1];
 103     set_prefix(node, prefix, l);
 104     return maxl;
 105 }
 106
 107 void set_schedule_from_prefix(PDG *pdg)
 108 {
 109     int statement_dims = normalize_prefix(pdg);
 110     int dim = 2 * statement_dims - 1;
 111     int nparam = pdg->params.size();
 112     isl_ctx *ctx = pdg->get_isl_ctx();
 113
 114     assert(pdg->dimension == 0);
 115     assert(pdg->dimension == pdg->statement_dimensions.size());
 116     pdg->dimension = dim;
 117     for (int i = 0; i < dim; ++i)
 118         pdg->statement_dimensions.push_back(1-(i%2));
 119
 120     for (int i = 0; i < pdg->nodes.size(); ++i) {
 121         pdg::node *node = pdg->nodes[i];
 122         isl_set *set = node->source->get_isl_set(ctx);
 123         isl_space *space = isl_set_get_space(set);
 124         isl_map *map;
 125         isl_set_free(set);
 126         if (isl_space_is_wrapping(space))
 127             space = isl_space_domain(isl_space_unwrap(space));
 128         map = isl_map_identity(isl_space_map_from_set(space));
 129         for (int j = 0; 2 * j < node->prefix.size(); ++j) {
 130             map = isl_map_insert_dims(map, isl_dim_out, 2 * j, 1);
 131             map = isl_map_fix_si(map, isl_dim_out, 2 * j, node->prefix[2*j]);
 132         }
 133         map = isl_map_add_dims(map, isl_dim_out,
 134                                 2 * statement_dims - 1 - node->prefix.size());
 135         for (int j = node->prefix.size(); j < 2 * statement_dims - 1; ++j)
 136             map = isl_map_fix_si(map, isl_dim_out, j, 0);
 137         node->schedule = new pdg::IslMap(map);
 138     }
 139 }
 140
 141 /* Create a schedule for the domains "source" based on "pos" and "scale".
 142  * The "extra" dimensions of source do not appear in the schedule
 143  * since they have a unique value determined by the values of the "actual"
 144  * dimensions.
 145  * If "source" has filters (in the range of the wrapped map), then
 146  * we project out the filters so that the created schedule only applies
 147  * to the actual iteration domain.
 148  */
 149 static pdg::IslMap *create_schedule(PDG *pdg, pdg::IslSet *source,
 150                                         vector<int>& pos, vector<int>& scale)
 151 {
 152         pdg::IslMap *s;
 153         isl_ctx *ctx = pdg->get_isl_ctx();
 154         isl_set *set = source->get_isl_set(ctx);
 155         isl_space *space = isl_set_get_space(set);
 156         isl_multi_aff *ma;
 157         isl_map *map;
 158
 159         if (isl_space_is_wrapping(space))
 160                 space = isl_space_domain(isl_space_unwrap(space));
 161         space = isl_space_from_domain(space);
 162         isl_set_free(set);
 163         space = isl_space_add_dims(space, isl_dim_out, pdg->dimension);
 164         ma = isl_multi_aff_zero(space);
 165         for (int i = 0; i < pdg->dimension; ++i) {
 166                 isl_aff *aff;
 167
 168                 if (pos[i] < 0)
 169                         continue;
 170                 aff = isl_multi_aff_get_aff(ma, i);
 171                 aff = isl_aff_set_coefficient_si(aff, isl_dim_in,
 172                                                             pos[i], scale[i]);
 173                 ma = isl_multi_aff_set_aff(ma, i, aff);
 174         }
 175
 176         map = isl_map_from_multi_aff(ma);
 177         s = new pdg::IslMap(map);
 178
 179         return s;
 180 }
 181
 182 static pdg::IslMap *pull_back_schedule(PDG *pdg, pdg::IslSet *source,
 183         pdg::IslMap *schedule, __isl_keep isl_map *map)
 184 {
 185         isl_ctx *ctx = pdg->get_isl_ctx();
 186         isl_map *scat = schedule->get_isl_map(ctx);
 187         isl_basic_map *aff;
 188         isl_mat *mat;
 189         int dim = pdg->dimension;
 190         int this_dim = isl_map_dim(map, isl_dim_in);
 191         vector<int> pos(dim);
 192         vector<int> scale(dim);
 193         // k: position in pos
 194         int k = 0, j = 0;
 195         isl_val *v;
 196
 197         map = isl_map_copy(map);
 198         map = isl_map_apply_range(map, scat);
 199         aff = isl_map_affine_hull(map);
 200         aff = isl_basic_map_remove_divs(aff);
 201         mat = isl_basic_map_equalities_matrix(aff, isl_dim_in, isl_dim_out,
 202                                     isl_dim_div, isl_dim_param, isl_dim_cst);
 203         isl_basic_map_free(aff);
 204
 205         for (j = 0; j < this_dim; ++j) {
 206                 int s;
 207                 int m;
 208                 int min_m = k;
 209                 int max_m = j + dim - this_dim;
 210
 211                 for (m = min_m; m <= max_m; ++m) {
 212                         int row;
 213                         for (row = 0; row < isl_mat_rows(mat); ++row) {
 214                                 int s_v, i_v;
 215                                 v = isl_mat_get_element_val(mat,
 216                                                             row, this_dim + m);
 217                                 s_v = isl_val_get_num_si(v);
 218                                 isl_val_free(v);
 219                                 if (s_v == 0)
 220                                         continue;
 221                                 v = isl_mat_get_element_val(mat, row, j);
 222                                 i_v = isl_val_get_num_si(v);
 223                                 isl_val_free(v);
 224                                 if (i_v == 0)
 225                                         continue;
 226                                 if (s_v < 0)
 227                                         s_v = -s_v;
 228                                 if (i_v < 0)
 229                                         i_v = -i_v;
 230                                 if (s_v == 1)
 231                                         s = i_v;
 232                                 else if (i_v % s_v == 0)
 233                                         s = i_v / s_v;
 234                                 else
 235                                         s = 1;
 236                                 break;
 237                         }
 238                         if (row < isl_mat_rows(mat))
 239                                 break;
 240                 }
 241                 if (m > max_m)
 242                         break;
 243                 for ( ; k < m; ++k)
 244                         pos[k] = -1;
 245                 scale[k] = s;
 246                 pos[k++] = j;
 247         }
 248
 249         isl_mat_free(mat);
 250
 251         for ( ; j < this_dim; ++j) {
 252                 scale[k] = 1;
 253                 pos[k++] = j;
 254         }
 255         for ( ; k < dim; ++k)
 256                 pos[k] = -1;
 257
 258         return create_schedule(pdg, source, pos, scale);
 259 }
 260
 261 /* Return the dimension of the iteration domain of "node".
 262  * If node->source is a wrapped map, then the iteration domain
 263  * is in the domain of that map.
 264  */
 265 static int source_dim(pdg::node *node)
 266 {
 267         isl_space *space = node->source->get_dim();
 268         int d;
 269
 270         if (isl_space_is_wrapping(space)) {
 271                 space = isl_space_unwrap(space);
 272                 d = isl_space_dim(space, isl_dim_in);
 273         } else
 274                 d = isl_space_dim(space, isl_dim_set);
 275         isl_space_free(space);
 276         return d;
 277 }
 278
 279 void common_dimension(PDG *pdg)
 280 {
 281     isl_ctx *ctx = pdg->get_isl_ctx();
 282     int dim = pdg->dimension;
 283     for (int i = 0; i < pdg->nodes.size(); ++i) {
 284         pdg::node *node = pdg->nodes[i];
 285         int dim_i = source_dim(node);
 286         if (dim_i > dim)
 287             dim = dim_i;
 288     }
 289     assert(pdg->dimension == pdg->statement_dimensions.size());
 290     for (int i = pdg->dimension; i < dim; ++i)
 291         pdg->statement_dimensions.push_back(0);
 292     pdg->dimension = dim;
 293     vector<int> pos(dim);
 294     vector<int> scale(dim);
 295     for (int i = 0; i < dim; ++i) {
 296         scale[i] = 1;
 297         pos[i] = i;
 298     }
 299
 300     int todo = pdg->nodes.size();
 301     for (int i = 0; i < pdg->nodes.size(); ++i) {
 302         pdg::node *node = pdg->nodes[i];
 303         if (source_dim(node) != dim)
 304             continue;
 305         node->schedule = create_schedule(pdg, node->source, pos, scale);
 306         --todo;
 307         break;
 308     }
 309
 310     while (todo) {
 311         pdg::dependence *maxdep = NULL;
 312         vector<int> maxw(4);
 313         vector<int> w(4);
 314         maxw[0] = -1;
 315         maxw[1] = -1;
 316         maxw[2] = -1;
 317         maxw[3] = -1;
 318         w[0] = -1;
 319         w[1] = -1;
 320         w[2] = -1;
 321         w[3] = -1;
 322         for (int i = 0; i < pdg->dependences.size(); ++i) {
 323             pdg::dependence *dep = pdg->dependences[i];
 324             if (dep->type == pdg::dependence::uninitialized)
 325                 continue;
 326             pdg::IslMap *rel = dep->relation;
 327             if (dep->to->schedule && !dep->from->schedule) {
 328                 w[0] = rel->output();
 329                 w[1] = rel->input();
 330                 w[2] = 1;
 331             } else if (dep->from->schedule && !dep->to->schedule) {
 332                 w[0] = rel->input();
 333                 w[1] = rel->output();
 334                 w[2] = 1;
 335             } else
 336                 continue;
 337             w[3] = dep->array ? dep->array->dims.size() : 0;
 338             if (maxw < w) {
 339                 maxw = w;
 340                 maxdep = dep;
 341             }
 342         }
 343         pdg::dependence *dep = maxdep;
 344         if (!dep) {
 345             int maxi = -1;
 346             int maxdim = -1;
 347             for (int i = 0; i < pdg->nodes.size(); ++i) {
 348                 pdg::node *node = pdg->nodes[i];
 349                 int dim_i;
 350                 if (node->schedule)
 351                     continue;
 352                 dim_i = source_dim(node);
 353                 if (dim_i > maxdim) {
 354                     maxdim = dim_i;
 355                     maxi = i;
 356                 }
 357             }
 358             assert(maxi != -1);
 359             pdg::node *node = pdg->nodes[maxi];
 360             for (int i = node->source->dim(); i < pos.size(); ++i)
 361                 pos[i] = -1;
 362             node->schedule = create_schedule(pdg, node->source, pos, scale);
 363             for (int i = node->source->dim(); i < pos.size(); ++i)
 364                 pos[i] = i;
 365             fprintf(stderr, "WARNING: disconnected dependence graph\n");
 366         } else {
 367             isl_map *dep_map = dep->relation->get_isl_map(ctx);
 368             if (dep->to->schedule) {
 369                 dep->from->schedule = pull_back_schedule(pdg,
 370                                         dep->from->source,
 371                                         dep->to->schedule, dep_map);
 372             } else {
 373                 dep_map = isl_map_reverse(dep_map);
 374                 dep->to->schedule = pull_back_schedule(pdg,
 375                                         dep->to->source,
 376                                         dep->from->schedule, dep_map);
 377             }
 378             isl_map_free(dep_map);
 379         }
 380         --todo;
 381     }
 382 }
 383
 384
 385 struct dvector {
 386         isl_set *d;
 387
 388         dvector() : d(NULL) {}
 389         dvector(__isl_take isl_set *d) : d(d) {}
 390         dvector(const dvector &copy) {
 391                 d = isl_set_copy(copy.d);
 392         }
 393         dvector &operator= (const dvector &other) {
 394                 isl_set_free(d);
 395                 d = isl_set_copy(other.d);
 396                 return *this;
 397         }
 398         virtual ~dvector() {
 399                 isl_set_free(d);
 400         }
 401
 402         bool combine(const dvector &dv, const dvector &offset);
 403 };
 404
 405 void operator-= (dvector &d1, const dvector &d2)
 406 {
 407         isl_set *neg = isl_set_neg(isl_set_copy(d2.d));
 408         d1.d = isl_set_sum(d1.d, neg);
 409 }
 410
 411 dvector operator- (const dvector &d)
 412 {
 413         return dvector(isl_set_neg(isl_set_copy(d.d)));
 414 }
 415
 416 void operator+= (dvector &d1, const dvector &d2)
 417 {
 418         d1.d = isl_set_sum(d1.d, isl_set_copy(d2.d));
 419 }
 420
 421 dvector operator+ (const dvector &d1, const dvector &d2)
 422 {
 423         return dvector(isl_set_sum(isl_set_copy(d1.d), isl_set_copy(d2.d)));
 424 }
 425
 426 /* replace by dv + offset if dv + offset is smaller
 427  * return true if dv + offset was smaller
 428  */
 429 bool dvector::combine(const dvector &dv, const dvector &offset)
 430 {
 431         int equal;
 432         dvector new_v = dv + offset;
 433         new_v.d = isl_set_union(new_v.d, isl_set_copy(d));
 434         new_v.d = isl_set_lexmin(new_v.d);
 435         equal = isl_set_is_equal(new_v.d, d);
 436         assert(equal >= 0);
 437         if (equal)
 438                 return false;
 439         new_v.d = isl_set_remove_divs(new_v.d);
 440         new_v.d = isl_set_lexmin(new_v.d);
 441         *this = new_v;
 442         return true;
 443 }
 444
 445 struct wdvector : dvector {
 446         int     w;
 447
 448         wdvector() : w(0), dvector(NULL) {}
 449         wdvector(int w, __isl_take isl_set *d) : w(w), dvector(d) {}
 450 };
 451
 452 wdvector operator+ (const wdvector &d1, const dvector &d2)
 453 {
 454         return wdvector(d1.w,
 455                         isl_set_sum(isl_set_copy(d1.d), isl_set_copy(d2.d)));
 456 }
 457
 458 /* Fairly arbitrary, but deterministic sorting of the nodes.
 459  * In particular, the order does not depend on pointer values.
 460  */
 461 struct smaller_node_nr
 462 {
 463         bool operator()(const pdg::node* n1, const pdg::node* n2) const {
 464                 return n1->nr < n2->nr;
 465         }
 466 };
 467
 468 typedef map<pdg::node *,
 469             map<pdg::node *, wdvector, smaller_node_nr>,
 470             smaller_node_nr>::iterator d_graph_iterator;
 471
 472 struct d_graph {
 473         map<pdg::node *,
 474             map<pdg::node *, wdvector, smaller_node_nr>, smaller_node_nr> data;
 475
 476         void update(pdg::node *from, pdg::node *to, __isl_take isl_set *ddv,
 477                     int weight);
 478
 479         void minimize();
 480         void collect_related_nodes(set<pdg::node *> &nodes, pdg::node *node);
 481 };
 482
 483 void d_graph::update(pdg::node *from, pdg::node *to,
 484         __isl_take isl_set *ddv, int weight)
 485 {
 486         assert(ddv);
 487         if (data[from].find(to) == data[from].end())
 488                 data[from][to] = wdvector(weight, ddv);
 489         else {
 490                 data[from][to].w += weight;
 491                 data[from][to].d = isl_set_union(data[from][to].d, ddv);
 492         }
 493 }
 494
 495 void d_graph::minimize()
 496 {
 497         d_graph_iterator i;
 498         for (i = data.begin(); i != data.end(); ++i) {
 499                 pdg::node *from = (*i).first;
 500                 map<pdg::node *, wdvector>::iterator j;
 501                 for (j = data[from].begin(); j != data[from].end(); ++j) {
 502                         (*j).second.d = isl_set_lexmin((*j).second.d);
 503                         (*j).second.d = isl_set_remove_divs((*j).second.d);
 504                         (*j).second.d = isl_set_lexmin((*j).second.d);
 505                         (*j).second.d = isl_set_coalesce((*j).second.d);
 506                 }
 507         }
 508 }
 509
 510 void d_graph::collect_related_nodes(set<pdg::node *> &nodes,
 511         pdg::node *node)
 512 {
 513         vector<pdg::node *> todo;
 514
 515         todo.push_back(node);
 516
 517         while (!todo.empty()) {
 518                 pdg::node *node = todo.back();
 519                 todo.pop_back();
 520                 if (nodes.find(node) != nodes.end())
 521                         continue;
 522
 523                 nodes.insert(node);
 524
 525                 d_graph_iterator i;
 526                 map<pdg::node *, wdvector>::iterator j;
 527                 for (j = data[node].begin(); j != data[node].end(); ++j) {
 528                         pdg::node *node2 = (*j).first;
 529                         if (nodes.find(node2) != nodes.end())
 530                                 continue;
 531                         todo.push_back(node2);
 532                 }
 533                 for (i = data.begin(); i != data.end(); ++i) {
 534                         pdg::node *node2 = (*i).first;
 535                         if (nodes.find(node2) != nodes.end())
 536                                 continue;
 537                         if ((*i).second.find(node) == (*i).second.end())
 538                                 continue;
 539                         todo.push_back(node2);
 540                 }
 541         }
 542 }
 543
 544 struct combiner {
 545         PDG *pdg;
 546         d_graph &graph;
 547         /* dependence distance offsets used during moving */
 548         map<pdg::node *, dvector> move_offsets;
 549         /* the relative offsets */
 550         map<pdg::node *, map<pdg::node *, dvector> > delays;
 551         /* the original distance vectors */
 552         map<pdg::node *, map<pdg::node *, dvector> > distances;
 553         /* the final offsets */
 554         map<pdg::node *, dvector> offsets;
 555         int         n_nodes;
 556         bool        move;
 557         /* space of schedule domain */
 558         isl_space  *space;
 559
 560         combiner(PDG *pdg, d_graph& distances, int n_nodes, bool move,
 561             __isl_keep isl_space *space) :
 562             pdg(pdg), graph(distances), n_nodes(n_nodes), move(move),
 563             space(space) {}
 564
 565         void combine();
 566
 567         void compute_move_offsets();
 568         dvector compute_relative_offset(pdg::node* from, pdg::node *to,
 569                                              bool do_move);
 570         void set_relative_offset(pdg::node* from, pdg::node *to);
 571         void update_graph(pdg::node* from, pdg::node *to);
 572         void compute_absolute_offsets();
 573         void handle_zero_dependences();
 574         void handle_negative_offsets();
 575 };
 576
 577 static __isl_give isl_set *zero_set(__isl_take isl_space *dim)
 578 {
 579         isl_set *set;
 580         int n = isl_space_dim(dim, isl_dim_set);
 581         set = isl_set_universe(dim);
 582         for (int i = 0; i < n; ++i)
 583                 set = isl_set_fix_si(set, isl_dim_set, i, 0);
 584         return set;
 585 }
 586
 587 dvector combiner::compute_relative_offset(pdg::node* from,
 588         pdg::node *to, bool do_move)
 589 {
 590         dvector delay;
 591         map<pdg::node *, dvector> d;
 592         bool progress = true;
 593         map<pdg::node *, dvector>::iterator i;
 594
 595         d[from] = dvector(zero_set(isl_set_get_space(graph.data[from][to].d)));
 596
 597         for (int k = 0; k < n_nodes && progress; ++k) {
 598                 map<pdg::node *, wdvector>::iterator j;
 599                 progress = false;
 600                 for (i = d.begin(); i != d.end(); ++i) {
 601                         pdg::node *a = (*i).first;
 602                         for (j = graph.data[a].begin();
 603                              j != graph.data[a].end(); ++j) {
 604                                 pdg::node *b = (*j).first;
 605                                 if (do_move &&
 606                                     move_offsets.find(a) != move_offsets.end())
 607                                         (*j).second -= move_offsets[a];
 608                                 if (d.find(b) == d.end()) {
 609                                         progress = true;
 610                                         d[b] = (*j).second + d[a];
 611                                 } else {
 612                                         bool p;
 613                                         p = d[b].combine((*j).second, d[a]);
 614                                         progress = progress || p;
 615                                 }
 616                                 if (do_move &&
 617                                     move_offsets.find(a) != move_offsets.end())
 618                                         (*j).second += move_offsets[a];
 619                         }
 620                 }
 621         }
 622
 623         /* d[from] + d[from] < d[from] iff d[from] < 0 */
 624         bool lexneg = d[from].combine(d[from], d[from]);
 625         if (!do_move)
 626                 assert(!lexneg);
 627
 628         if (!lexneg)
 629                 delay = -d[to];
 630
 631         return delay;
 632 }
 633
 634 void combiner::set_relative_offset(pdg::node* from, pdg::node *to)
 635 {
 636         dvector delay;
 637         if (move)
 638                 delay = compute_relative_offset(from, to, true);
 639         if (!delay.d)
 640                 delay = compute_relative_offset(from, to, false);
 641         assert(delay.d);
 642         delays[from][to] = delay;
 643 }
 644
 645 void combiner::update_graph(pdg::node* from, pdg::node *to)
 646 {
 647         dvector offset = delays[from][to];
 648         dvector neg_offset = -offset;
 649
 650         map<pdg::node *, wdvector>::iterator j;
 651         for (j = graph.data[to].begin(); j != graph.data[to].end(); ++j) {
 652                 if ((*j).first == from)
 653                         continue;
 654                 if (graph.data[from].find((*j).first) == graph.data[from].end())
 655                         graph.data[from][(*j).first] = (*j).second + neg_offset;
 656                 else
 657                         graph.data[from][(*j).first].combine((*j).second,
 658                                                              neg_offset);
 659         }
 660
 661         graph.data.erase(to);
 662
 663         d_graph_iterator i;
 664         for (i = graph.data.begin(); i != graph.data.end(); ++i) {
 665                 if ((*i).second.find(to) == (*i).second.end())
 666                     continue;
 667                 if ((*i).first != from) {
 668                     if ((*i).second.find(from) == (*i).second.end())
 669                             (*i).second[from] = (*i).second[to] + offset;
 670                     else
 671                             (*i).second[from].combine((*i).second[to], offset);
 672                 }
 673                 (*i).second.erase(to);
 674         }
 675
 676         --n_nodes;
 677 }
 678
 679 void combiner::compute_absolute_offsets()
 680 {
 681         pdg::node *init = (*graph.data.begin()).first;
 682         vector<pdg::node *> todo;
 683         todo.push_back(init);
 684         offsets[init] = dvector(zero_set(isl_space_copy(space)));
 685
 686         while (!todo.empty()) {
 687                 pdg::node *n = todo.back();
 688                 todo.pop_back();
 689                 if (delays.find(n) == delays.end())
 690                         continue;
 691
 692                 map<pdg::node *, dvector>::iterator i;
 693                 for (i = delays[n].begin(); i != delays[n].end(); ++i) {
 694                         offsets[(*i).first] = offsets[n] + (*i).second;
 695                         todo.push_back((*i).first);
 696                 }
 697         }
 698 }
 699
 700 void combiner::handle_zero_dependences()
 701 {
 702         map<pdg::node *, set<pdg::node *> > succ;
 703         map<pdg::node *, int > prec;
 704         map<pdg::node *, map<pdg::node *, dvector> >::iterator i;
 705         map<pdg::node *, dvector>::iterator j;
 706         for (j = offsets.begin(); j != offsets.end(); ++j)
 707                 prec[(*j).first] = 0;
 708
 709         for (i = distances.begin(); i != distances.end(); ++i)
 710                 for (j = (*i).second.begin(); j != (*i).second.end(); ++j) {
 711                         distances[(*i).first][(*j).first] +=
 712                                 offsets[(*j).first];
 713                         distances[(*i).first][(*j).first] -=
 714                                 offsets[(*i).first];
 715                         isl_set *test = distances[(*i).first][(*j).first].d;
 716                         isl_set *zero = zero_set(isl_set_get_space(test));
 717                         zero = isl_set_intersect(zero, isl_set_copy(test));
 718                         int has_zero = !isl_set_is_empty(zero);
 719                         isl_set_free(zero);
 720                         if (has_zero) {
 721                                 succ[(*i).first].insert((*j).first);
 722                                 prec[(*j).first]++;
 723                         }
 724                 }
 725
 726         map<pdg::node *, int> final;
 727         for (j = offsets.begin(); j != offsets.end(); ++j) {
 728                 final[(*j).first] = 0;
 729         }
 730
 731         while (!prec.empty()) {
 732                 map<pdg::node *, int >::iterator i;
 733                 for (i = prec.begin(); (*i).second > 0; ++i)
 734                         ;
 735                 set<pdg::node *>::iterator j;
 736                 for (j = succ[(*i).first].begin();
 737                      j != succ[(*i).first].end(); ++j) {
 738                         prec[(*j)]--;
 739                         if (final[(*j)] <= final[(*i).first])
 740                                 final[(*j)] = final[(*i).first] + 1;
 741                 }
 742                 prec.erase(i);
 743         }
 744
 745         int dim = isl_set_dim((*offsets.begin()).second.d, isl_dim_set);
 746         for (j = offsets.begin(); j != offsets.end(); ++j) {
 747                 (*j).second.d = isl_set_add_dims((*j).second.d, isl_dim_set, 1);
 748                 (*j).second.d = isl_set_fix_si((*j).second.d, isl_dim_set, dim,
 749                                                 final[(*j).first]);
 750         }
 751 }
 752
 753 /* Remove negative offsets by shifting all offsets over the opposite
 754  * of the most negative offsets in each direction.
 755  */
 756 void combiner::handle_negative_offsets()
 757 {
 758         int dim = isl_set_dim((*offsets.begin()).second.d, isl_dim_set);
 759         isl_space *space;
 760         isl_set *shift;
 761         isl_set *set;
 762         map<pdg::node *, dvector>::iterator j;
 763
 764         space = isl_set_get_space((*offsets.begin()).second.d);
 765         set = isl_set_universe(isl_space_copy(space));
 766         space = isl_space_params(space);
 767         space = isl_space_add_dims(space, isl_dim_set, 0);
 768         shift = isl_set_universe(space);
 769
 770         for (int i = 0; i < dim; ++i)
 771                 set = isl_set_fix_si(set, isl_dim_set, i, 0);
 772
 773         for (j = offsets.begin(); j != offsets.end(); ++j)
 774                 set = isl_set_union(set, isl_set_copy((*j).second.d));
 775
 776         for (int i = 0; i < dim; ++i) {
 777                 isl_pw_aff *pa = isl_set_dim_min(isl_set_copy(set), i);
 778                 pa = isl_pw_aff_coalesce(pa);
 779                 isl_set *shift_i = isl_set_from_pw_aff(pa);
 780                 shift = isl_set_flat_product(shift, shift_i);
 781         }
 782
 783         shift = isl_set_neg(shift);
 784         shift = isl_set_gist_params(shift, pdg->get_context_isl_set());
 785         for (j = offsets.begin(); j != offsets.end(); ++j)
 786                 (*j).second.d = isl_set_sum((*j).second.d, isl_set_copy(shift));
 787
 788         isl_set_free(set);
 789         isl_set_free(shift);
 790 }
 791
 792 /* Builds a relation that connects iterations of D to the next iteration */
 793 static __isl_give isl_map *next_iteration_map(__isl_take isl_set *dom)
 794 {
 795         isl_space *dims = isl_set_get_space(dom);
 796         isl_map *lt = isl_map_lex_lt(dims);
 797         lt = isl_map_intersect_domain(lt, isl_set_copy(dom));
 798         lt = isl_map_intersect_range(lt, isl_set_copy(dom));
 799         lt = isl_map_partial_lexmax(lt, dom, NULL);
 800         return lt;
 801 }
 802
 803 void combiner::compute_move_offsets()
 804 {
 805         d_graph_iterator i;
 806         isl_ctx *ctx = pdg->get_isl_ctx();
 807
 808         for (i = graph.data.begin(); i != graph.data.end(); ++i) {
 809                 pdg::node *node = (*i).first;
 810                 isl_set *dom = node->source->get_isl_set(ctx);
 811                 isl_set *context = pdg->get_context_isl_set();
 812                 dom = isl_set_intersect_params(dom, context);
 813                 isl_map *scat = (*i).first->schedule->get_isl_map(ctx);
 814                 dom = isl_set_apply(dom, scat);
 815                 isl_map *next = next_iteration_map(dom);
 816                 isl_set *step = isl_map_deltas(next);
 817                 step = isl_set_lexmin(step);
 818                 if (isl_set_is_empty(step))
 819                         isl_set_free(step);
 820                 else
 821                         move_offsets[node] = dvector(step);
 822         }
 823 }
 824
 825 void combiner::combine()
 826 {
 827         d_graph_iterator i;
 828         map<pdg::node *, wdvector>::iterator j;
 829
 830         if (move)
 831                 compute_move_offsets();
 832
 833         for (i = graph.data.begin(); i != graph.data.end(); ++i)
 834                 for (j = (*i).second.begin(); j != (*i).second.end(); ++j)
 835                         distances[(*i).first][(*j).first] = (*j).second;
 836
 837         while (n_nodes > 1) {
 838                 int max = -1;
 839                 pdg::node* max_from = NULL;
 840                 pdg::node* max_to = NULL;
 841                 d_graph_iterator i;
 842                 map<pdg::node *, wdvector>::iterator j;
 843                 for (i = graph.data.begin(); i != graph.data.end(); ++i)
 844                         for (j = (*i).second.begin();
 845                              j != (*i).second.end(); ++j) {
 846                                 if ((*j).second.w <= max)
 847                                         continue;
 848                                 max = (*j).second.w;
 849                                 max_from = (*i).first;
 850                                 max_to = (*j).first;
 851                         }
 852                 assert(max_from);
 853                 assert(max_to);
 854                 set_relative_offset(max_from, max_to);
 855                 update_graph(max_from, max_to);
 856         }
 857
 858         compute_absolute_offsets();
 859         handle_zero_dependences();
 860         handle_negative_offsets();
 861 }
 862
 863 bool translate(PDG *pdg, bool move)
 864 {
 865         isl_ctx *ctx = pdg->get_isl_ctx();
 866         isl_space *space;
 867         d_graph distances;
 868
 869         if (pdg->nodes.size() == 0)
 870                 return true;
 871
 872         space = isl_map_get_space(pdg->nodes[0]->schedule->map);
 873         space = isl_space_range(space);
 874
 875         for (int i = 0; i < pdg->dependences.size(); ++i) {
 876                 pdg::dependence *dep = pdg->dependences[i];
 877                 if (dep->type == pdg::dependence::uninitialized)
 878                         continue;
 879                 if (dep->from == dep->to)
 880                         continue;
 881                 int weight = dep->type == pdg::dependence::anti ? 0 : 1;
 882                 pdg::node* from = dep->from;
 883                 pdg::node* to = dep->to;
 884                 isl_set *ddv;
 885                 isl_map *scat;
 886                 isl_map *dep_map = dep->relation->get_isl_map(ctx);
 887                 scat = from->schedule->get_isl_map(ctx);
 888                 dep_map = isl_map_apply_domain(dep_map, scat);
 889                 scat = to->schedule->get_isl_map(ctx);
 890                 dep_map = isl_map_apply_range(dep_map, scat);
 891                 ddv = isl_map_deltas(dep_map);
 892                 distances.update(from, to, ddv, weight);
 893         }
 894
 895         distances.minimize();
 896
 897         set<pdg::node *> nodes_done;
 898         /* split the dependence graph into connected subgraphs
 899          * and compute offsets in each subgraph
 900          */
 901         while (nodes_done.size() < pdg->nodes.size()) {
 902                 set<pdg::node *> current_nodes;
 903                 d_graph current_distances;
 904                 pdg::node *node;
 905
 906                 for (int i = 0; i < pdg->nodes.size(); ++i) {
 907                         node = pdg->nodes[i];
 908                         if (nodes_done.find(node) != nodes_done.end())
 909                                 continue;
 910                         break;
 911                 }
 912
 913                 distances.collect_related_nodes(current_nodes, node);
 914
 915                 set<pdg::node *>::iterator i;
 916                 for (i = current_nodes.begin(); i != current_nodes.end(); ++i) {
 917                         current_distances.data[(*i)] = distances.data[(*i)];
 918                 }
 919
 920                 combiner c(pdg, current_distances, current_nodes.size(),
 921                                 move, space);
 922                 c.combine();
 923
 924                 for (i = current_nodes.begin(); i != current_nodes.end(); ++i) {
 925                         pdg::node *node = *i;
 926                         nodes_done.insert(node);
 927
 928                         isl_map *s = node->schedule->get_isl_map(ctx);
 929
 930                         isl_space *dim = isl_set_get_space(c.offsets[node].d);
 931                         int d = isl_space_dim(dim, isl_dim_set) - 1;
 932                         isl_map *id = isl_map_identity(
 933                                 isl_space_map_from_set(isl_space_copy(dim)));
 934                         isl_set *u = isl_set_universe(dim);
 935                         isl_map *off = isl_map_from_domain_and_range(u,
 936                                             isl_set_copy(c.offsets[node].d));
 937                         id = isl_map_project_out(id, isl_dim_in, d, 1);
 938                         id = isl_map_fix_si(id, isl_dim_out, d, 0);
 939                         off = isl_map_project_out(off, isl_dim_in, d, 1);
 940                         off = isl_map_sum(id, off);
 941                         s = isl_map_apply_range(s, off);
 942
 943                         delete node->schedule;
 944                         node->schedule = new IslMap(s);
 945                 }
 946         }
 947
 948         pdg->statement_dimensions.push_back(1);
 949         pdg->dimension++;
 950
 951         isl_space_free(space);
 952
 953         return true;
 954 }
 955
 956 }